Local Vertex Colouring Graph Neural Networks
Shouheng Li Dongwoo Kim Qing Wang
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 vertex colouring scheme and
demonstrate that classical search algorithms can efficiently compute graph
representations that extend beyond the 1-WL. We show the colouring scheme
inherits useful properties from graph search that can help solve problems like
graph biconnectivity. Furthermore, we show that under certain conditions, the
expressivity of GNNs increases hierarchically with the radius of the search
neighbourhood. To further investigate the proposed scheme, we develop a new
type of GNN based on two search strategies, breadth-first search and
depth-first search, highlighting the graph properties they can capture on top
of 1-WL. Our code is available at https://github.com/seanli3/lvc.