Booth Id:
SOFT053
Category:
Systems Software
Year:
2024
Finalist Names:
Hadzhi-Manich, Deyan (School: High School of Mathematics "Dr Petar Beron")
Abstract:
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.