A Graph Isomorphism Kernel Based on k-Vertex Connectivity and Its Application in Graph Neural Networks
ISEF · 2024 Systems Software
Overview
The most popular Graph Neural Networks rely on the message-passing paradigm, where the idea is to iteratively propagate the representation information of every node to its direct neighborhood. Unfortunately, in their most natural version, their expressive power is inherently limited due to their connection to the Weisfeiler-Lehman graph isomorphism test. This problem is closely tied to the one of graph isomorphism, which has not been solved in polynomial time. In this work, we propose a new isomorphism kernel based on encoding structural properties of the graph, namely the k-Vertex Connected Components. Building upon it, we develop the k-FA layer that can be incorporated as an additional layer for exchanging global information in other GNNs. Further, we evaluate the model's expressivity and its performance on molecular datasets, where it shows improvement with little effort.
Competition history
- ISEF 2024
Resources
Related projects
ISEF · 2022
Predicting Structural Similarity Between Molecules Using Graph Neural Networks
ISEF · 2024
GraphChem: A Soft Graph Mixture of Experts Based Adversarial Variational Spectral Graph Autoencoder for De Novo Drug Design & Other Pharmacological Objectives
ISEF · 2021
A Two-Step Approach to Effectively Find Analogies in Knowledge Graphs
ISEF · 2026
Scalable Quantum Error Decoding With Sparse Graph Neural Networks
Closest projects by meaning, across every fair and year in the corpus.
Source: Regeneron International Science and Engineering Fair