mlsanityData to 7 Oct 2026

Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings

arXiv 2201.13410 ↗First posted 31 Jan 2022cs.LG cs.DScited by 15

Not on the map. Why?

Abstract (arXiv)

Graph isomorphism testing is usually approached via the comparison of graph invariants. Two popular alternatives that offer a good trade-off between expressive power and computational efficiency are combinatorial (i.e., obtained via the Weisfeiler-Leman (WL) test) and spectral invariants. While the exact power of the latter is still an open question, the former is regularly criticized for its limited power, when a standard configuration of uniform pre-coloring is used. This drawback hinders the applicability of Message Passing Graph Neural Networks (MPGNNs), whose expressive power is upper bounded by the WL test. Relaxing the assumption of uniform pre-coloring, we show that one can increase the expressive power of the WL test ad infinitum. Following that, we propose an efficient pre-coloring based on spectral features that provably increase the expressive power of the vanilla WL test. The above claims are accompanied by extensive synthetic and real data experiments. The code to reproduce our experiments is available at https://github.com/TPFI22/Spectral-and-Combinatorial

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). Builds on 39 of its 56 references that are in the map. First posted on arXiv 31 Jan 2022.

Builds on

39 of 56 references.

References · 39

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2017Inductive Representation Learning on Large Graphscited by 6,284
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  6. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  7. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  8. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
  9. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  10. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  11. 2016Geometric deep learning: going beyond Euclidean datacited by 1,042
  12. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 970
27 more
  1. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  2. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
  3. 2020A Generalization of Transformer Networks to Graphscited by 653
  4. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  5. 2019Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological Viewcited by 544
  6. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
  7. 2021Rethinking Graph Transformers with Spectral Attentioncited by 468
  8. 2017Representation Learning on Graphs: Methods and Applicationscited by 456
  9. 2019Provably Powerful Graph Networkscited by 385
  10. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  11. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 219
  12. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  13. 2017struc2vec: Learning Node Representations from Structural Identitycited by 214
  14. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  15. 2020Random Features Strengthen Graph Neural Networkscited by 184
  16. 2021Equivariant Subgraph Aggregation Networkscited by 154
  17. 2017Predicting multicellular function through multi-layer tissue networkscited by 138
  18. 2017Deep Functional Maps: Structured Prediction for Dense Shape Correspondencecited by 134
  19. 2020Directional Graph Networkscited by 132
  20. 2020GraphNorm: A Principled Approach to Accelerating Graph Neural Network Trainingcited by 116
  21. 2019Fake News Detection on Social Media using Geometric Deep Learningcited by 115
  22. 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111
  23. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  24. 2020Wasserstein Embedding for Graph Learningcited by 56
  25. 2018Graph Neural Networks for IceCube Signal Classificationcited by 24
  26. 2017The Weisfeiler-Leman Dimension of Planar Graphs is at most 3cited by 10
  27. 2021Weisfeiler--Leman and Graph Spectracited by 5

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 6; 2024: 3; 2025: 4.

15 papers.

Sort:

  1. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 176
  2. 2023Graph Inductive Biases in Transformers without Message Passingcited by 150
  3. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  4. 2022Generalised Implicit Neural Representationscited by 31
  5. 2025Learning Efficient Positional Encodings with Graph Neural Networkscited by 21
  6. 2024On the Expressive Power of Spectral Invariant Graph Neural Networkscited by 15
  7. 2023Facilitating Graph Neural Networks with Random Walk on Simplicial Complexescited by 14
  8. 2023An Efficient Subgraph GNN with Provable Substructure Counting Powercited by 13
  9. 2023Cycle Invariant Positional Encoding for Graph Representation Learningcited by 8
  10. 2025Homomorphism Expressivity of Spectral Invariant Graph Neural Networkscited by 4
  11. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  12. 2025Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrumcited by 3
3 more
  1. 2023Centrality-Based Node Feature Augmentation for Robust Network Alignmentcited by 1
  2. 2024Edge Weight Prediction For Category-Agnostic Pose Estimationcited by 0
  3. 2025Density-aware Walks for Coordinated Campaign Detectioncited by 0