A Graph Isomorphism Kernel Based on k-Vertex Connectivity and Its Application in Graph Neural Networks
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
ISEF · 2026
Towards Completing and Annotating the Human Connectome With CGNN: Connectome Generation Neural Network
ISEF · 2017
Mapping Edges to Nodes by Utilizing Morton Codes in Stochastic Kronecker Graphs
ISEF · 2024
Predicting P-Glycoprotein Inhibition Using a Message-Passing Graph Neural Network
ISEF · 2022
Using Kleisli Morphisms for Malware Detection With Graph Convolution Networks
Closest projects by meaning, across every fair and year in the corpus.
Browse more like this
Source: Regeneron International Science and Engineering Fair