A Topological characterisation of Weisfeiler-Leman equivalence classes
Not on the map. Why?
Abstract (arXiv)
Graph Neural Networks (GNNs) are learning models aimed at processing graphs and signals on graphs. The most popular and successful GNNs are based on message passing schemes. Such schemes inherently have limited expressive power when it comes to distinguishing two non-isomorphic graphs. In this article, we rely on the theory of covering spaces to fully characterize the classes of graphs that GNNs cannot distinguish. We then generate arbitrarily many non-isomorphic graphs that cannot be distinguished by GNNs, leading to the GraphCovers dataset. We also show that the number of indistinguishable graphs in our dataset grows super-exponentially with the number of nodes. Finally, we test the GraphCovers dataset on several GNN architectures, showing that none of them can distinguish any two graphs it contains.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 20 of its 34 references that are in the map. First posted on arXiv 23 Jun 2022.
Builds on
20 of 34 references.
References · 20
- 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
- 2017Graph Attention Networkscited by 8,923
- 2017Inductive Representation Learning on Large Graphscited by 6,320
- 2018How Powerful are Graph Neural Networks?cited by 4,393
- 2017Neural Message Passing for Quantum Chemistrycited by 3,487
- 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
- 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
- 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
- 2019Provably Powerful Graph Networkscited by 389
- 2020Can Graph Neural Networks Count Substructures?cited by 236
- 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 221
- 2020Generalization and Representational Limits of Graph Neural Networkscited by 218
8 more
- 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
- 2019What graph neural networks cannot learn: depth vs widthcited by 201
- 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 198
- 2020Random Features Strengthen Graph Neural Networkscited by 186
- 2021Equivariant Subgraph Aggregation Networkscited by 154
- 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 118
- 2021Topological Graph Neural Networkscited by 87
- 2019Approximation Ratios of Graph Neural Networks for Combinatorial Problemscited by 69
Built on by
Citing papers per year: 2022: 1; 2023: 0; 2024: 0; 2025: 2.
3 papers.