mlsanityData to 7 Oct 2026

Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks

arXiv 2211.03232 ↗First posted 6 Nov 2022cs.LG stat.MLcited by 20

Not on the map. Why?

Abstract (arXiv)

Recent work shows that the expressive power of Graph Neural Networks (GNNs) in distinguishing non-isomorphic graphs is exactly the same as that of the Weisfeiler-Lehman (WL) graph test. In particular, they show that the WL test can be simulated by GNNs. However, those simulations involve neural networks for the 'combine' function of size polynomial or even exponential in the number of graph nodes n, as well as feature vectors of length linear in n. We present an improved simulation of the WL test on GNNs with exponentially lower complexity. In particular, the neural network implementing the combine function in each node has only a polylogarithmic number of parameters in n, and the feature vectors exchanged by the nodes of GNN consists of only O(log n) bits. We also give logarithmic lower bounds for the feature vector length and the size of the neural networks, showing the (near)-optimality of our construction.

Key facts. Cited by 20 papers in the map (data through 7 Oct 2026). Builds on 32 of its 56 references that are in the map. First posted on arXiv 6 Nov 2022.

Builds on

32 of 56 references.

References · 32

  1. 2017Inductive Representation Learning on Large Graphscited by 6,284
  2. 2016PointNet: Deep Learning on Point Sets for 3D Classification and Segmentationcited by 5,223
  3. 2018How Powerful are Graph Neural Networks?cited by 4,355
  4. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  5. 2017Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecastingcited by 1,125
  6. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  7. 2016Geometric deep learning on graphs and manifolds using mixture model CNNscited by 468
  8. 2019Provably Powerful Graph Networkscited by 385
  9. 2014On the Number of Linear Regions of Deep Neural Networkscited by 378
  10. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  11. 2016On the Expressive Power of Deep Neural Networkscited by 302
  12. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
20 more
  1. 2016Benefits of depth in neural networkscited by 248
  2. 2019Graph Matching Networks for Learning the Similarity of Graph Structured Objectscited by 202
  3. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  4. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  5. 2020Random Features Strengthen Graph Neural Networkscited by 184
  6. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  7. 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
  8. 2019Relational Pooling for Graph Representationscited by 150
  9. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  10. 2020Building powerful and equivariant graph neural networks with structural message-passingcited by 95
  11. 2020Deep Graph Matching Consensuscited by 85
  12. 2021The Logic of Graph Neural Networkscited by 84
  13. 2021Reconstruction for Powerful Graph Representationscited by 65
  14. 2022Theory of Graph Neural Networks: Representation and Learningcited by 60
  15. 2022A Short Tutorial on The Weisfeiler-Lehman Test And Its Variantscited by 52
  16. 2021Graph Neural Networks with Local Graph Parameterscited by 51
  17. 2020Graph Homomorphism Convolutioncited by 27
  18. 2020Let's Agree to Degree: Comparing Graph Convolutional Networks in the Message-Passing Frameworkcited by 24
  19. 2021The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphscited by 19
  20. 2022Gradual Weisfeiler-Leman: Slow and Steady Wins the Racecited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 9; 2024: 7; 2025: 2; 2026: 2.

20 papers.

Sort:

By area:

  1. 2023Representational Strengths and Limitations of Transformerscited by 132
  2. 2024Understanding Transformer Reasoning Capabilities via Graph Algorithmscited by 64
  3. 2023Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theoremcited by 33
  4. 2023WL meet VCcited by 30
  5. 2023The Descriptive Complexity of Graph Neural Networkscited by 26
  6. 2023Fine-grained Expressivity of Graph Neural Networkscited by 25
  7. 2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
  8. 2023Complete Neural Networks for Complete Euclidean Graphscited by 10
  9. 2024FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Networkcited by 8
  10. 2023On the power of graph neural networks and the role of the activation functioncited by 7
  11. 2024On the Expressive Power of Sparse Geometric MPNNscited by 7
  12. 2024On dimensionality of feature vectors in MPNNscited by 6
8 more
  1. 2024Future Directions in the Theory of Graph Machine Learningcited by 5
  2. 2025Efficient Mixed Precision Quantization in Graph Neural Networkscited by 3
  3. 2024A note on the VC dimension of 1-dimensional GNNscited by 1
  4. 2023The logic of rational graph neural networkscited by 0
  5. 2023Attacking Graph Neural Networks with Bit Flips: Weisfeiler and Lehman Go Indifferentcited by 0
  6. 2025Message Passing on the Edge: Towards Scalable and Expressive GNNscited by 0
  7. 2026TFWaveFormer: Temporal-Frequency Collaborative Multi-level Wavelet Transformer for Dynamic Link Predictioncited by 0
  8. 2026Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networkscited by 0