mlsanityData to 7 Oct 2026

Weisfeiler-Leman at the margin: When more expressivity matters

arXiv 2402.07568 ↗First posted 12 Feb 2024cs.LG cs.DM cs.NEcited by 13

Not on the map. Why?

Abstract (arXiv)

The Weisfeiler-Leman algorithm (1-WL) is a well-studied heuristic for the graph isomorphism problem. Recently, the algorithm has played a prominent role in understanding the expressive power of message-passing graph neural networks (MPNNs) and being effective as a graph kernel. Despite its success, 1-WL faces challenges in distinguishing non-isomorphic graphs, leading to the development of more expressive MPNN and kernel architectures. However, the relationship between enhanced expressivity and improved generalization performance remains unclear. Here, we show that an architecture's expressivity offers limited insights into its generalization performance when viewed through graph isomorphism. Moreover, we focus on augmenting 1-WL and MPNNs with subgraph information and employ classical margin theory to investigate the conditions under which an architecture's increased expressivity aligns with improved generalization performance. In addition, we show that gradient flow pushes the MPNN's weights toward the maximum margin solution. Further, we introduce variations of expressive 1-WL-based kernel and MPNN architectures with provable generalization properties. Our empirical study confirms the validity of our theoretical findings.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). Builds on 78 of its 127 references that are in the map. First posted on arXiv 12 Feb 2024.

Builds on

78 of 127 references.

References · 78

  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. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  7. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,097
  8. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
  9. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  10. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
  11. 2016Geometric deep learning on graphs and manifolds using mixture model CNNscited by 468
  12. 2019Provably Powerful Graph Networkscited by 385
38 more
  1. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  2. 2017Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphscited by 307
  3. 2018On the Optimization of Deep Networks: Implicit Acceleration by Overparameterizationcited by 280
  4. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  5. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  6. 2017CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filterscited by 203
  7. 2021Identity-aware Graph Neural Networkscited by 197
  8. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  9. 2022Pure Transformers are Powerful Graph Learnerscited by 188
  10. 2020Random Features Strengthen Graph Neural Networkscited by 184
  11. 2018Gradient descent aligns the layers of deep linear networkscited by 182
  12. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  13. 2021Equivariant Subgraph Aggregation Networkscited by 154
  14. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
  15. 2019Relational Pooling for Graph Representationscited by 150
  16. 2019A Survey on Graph Kernelscited by 148
  17. 2021Nested Graph Neural Networkscited by 136
  18. 2020Directional Graph Networkscited by 132
  19. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  20. 2020From Local Structures to Size Generalization in Graph Neural Networkscited by 119
  21. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  22. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  23. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  24. 2020Building powerful and equivariant graph neural networks with structural message-passingcited by 95
  25. 2018Convolutional Neural Network Architectures for Signals Supported on Graphscited by 94
  26. 2022How Powerful are K-hop Message Passing Graph Neural Networkscited by 90
  27. 2021Topological Graph Neural Networkscited by 86
  28. 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 84
  29. 2019Stability and Generalization of Graph Convolutional Neural Networkscited by 81
  30. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  31. 2021Reconstruction for Powerful Graph Representationscited by 65
  32. 2023A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Testscited by 64
  33. 2020Graph Kernels: State-of-the-Art and Future Challengescited by 63
  34. 2022Expressiveness and Approximation Properties of Graph Neural Networkscited by 63
  35. 2021A Theory of PAC Learnability of Partial Concept Classescited by 59
  36. 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 58
  37. 2022Ordered Subgraph Aggregation Networkscited by 57
  38. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 55

50 most cited of 78 All 78 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 5; 2025: 6; 2026: 2.

13 papers.

Sort:

  1. 2024Generalization Bounds for Message Passing Networks on Mixture of Graphonscited by 16
  2. 2024Towards Bridging Generalization and Expressivity of Graph Neural Networkscited by 12
  3. 2024Even Sparser Graph Transformerscited by 12
  4. 2024Synchronous Diffusion for Unsupervised Smooth Non-Rigid 3D Shape Matchingcited by 7
  5. 2024Towards Graph Foundation Models: A Study on the Generalization of Positional and Structural Encodingscited by 4
  6. 2025Graph Representational Learning: When Does More Expressivity Hurt Generalization?cited by 4
  7. 2025Performance Heterogeneity in Graph Neural Networks: Lessons for Architecture Design and Preprocessingcited by 2
  8. 2025Weisfeiler and Leman Follow the Arrow of Time: Expressive Power of Message Passing in Temporal Event Graphscited by 2
  9. 2025Understanding Generalization in Node and Link Predictioncited by 2
  10. 2025On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometrycited by 1
  11. 2025WILTing Trees: Interpreting the Distance Between MPNN Embeddingscited by 0
  12. 2026When and How to Canonize: A Generalization Perspectivecited by 0
1 more
  1. 2026AutoGrable: What Is a Good Graph for a Table?cited by 0