A Graph Isomorphism Kernel Based on k-Vertex Connectivity and its Application in Graph Neural Networks
The most popular Graph Neural Networks (GNNs) rely on the message-passing paradigm, where the idea is to iteratively propagate the representation information of every node to its direct neighborhood. However, in their most natural version, their expressive power is limited due to their connection to the Weisfeiler-Lehman test, a problem closely tied to the one of graph isomorphism. 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 used 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.
Deyan Deyanov Hadzhi-Manich
Share this Project