Local Vertex Colouring Graph Neural Networks
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 33 of its 65 references that are in the map. First posted on arXiv 10 Mar 2024.
Builds on
33 of 65 references.
References · 33
- 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
- 2017Graph Attention Networkscited by 8,854
- 2017Inductive Representation Learning on Large Graphscited by 6,284
- 2018How Powerful are Graph Neural Networks?cited by 4,355
- 2017Neural Message Passing for Quantum Chemistrycited by 3,460
- 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
- 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
- 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 987
- 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
- 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 821
- 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 786
- 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 592
21 more
- 2019Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological Viewcited by 544
- 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
- 2019Provably Powerful Graph Networkscited by 385
- 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
- 2017Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphscited by 307
- 2019PairNorm: Tackling Oversmoothing in GNNscited by 297
- 2019A Fair Comparison of Graph Neural Networks for Graph Classificationcited by 244
- 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 219
- 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
- 2019Position-aware Graph Neural Networkscited by 203
- 2019What graph neural networks cannot learn: depth vs widthcited by 195
- 2021BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximationcited by 195
- 2019What Can Neural Networks Reason About?cited by 155
- 2021Equivariant Subgraph Aggregation Networkscited by 154
- 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
- 2019Neural Execution of Graph Algorithmscited by 118
- 2018On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Propertiescited by 63
- 2022Expressiveness and Approximation Properties of Graph Neural Networkscited by 63
- 2020Neural Bipartite Matchingcited by 16
- 2021Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networkscited by 3
- 2023Modeling Edge Features with Deep Bayesian Graph Networkscited by 1
Built on by
Not cited yet.