Local Vertex Colouring Graph Neural Networks

arXiv:2403.06080v1 Announce Type: new
Abstract: In recent years, there has been a significant amount of research focused on expanding the expressivity of Graph Neural Networks (GNNs) beyond the Weisfeiler-Lehman (1-WL) framework. While many of these studies have yielded advancements in expressivity, they have frequently come at the expense of decreased efficiency or have been restricted to specific types of graphs. In this study, we investigate the expressivity of GNNs from the perspective of graph search. Specifically, we propose a new …

arxiv cs.lg graph graph neural networks networks neural networks type vertex