mlsanityData to 14 Oct 2026

Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks

arXiv 1810.02244 ↗First posted 4 Oct 2018cs.LG cs.AI cs.CVcited by 881

Not on the map. Why?

Abstract (arXiv)

In recent years, graph neural networks (GNNs) have emerged as a powerful neural architecture to learn vector representations of nodes and graphs in a supervised, end-to-end fashion. Up to now, GNNs have only been evaluated empirically -- showing promising results. The following work investigates GNNs from a theoretical point of view and relates them to the 1-dimensional Weisfeiler-Leman graph isomorphism heuristic (1-WL). We show that GNNs have the same expressiveness as the 1-WL in terms of distinguishing non-isomorphic (sub-)graphs. Hence, both algorithms also have the same shortcomings. Based on this, we propose a generalization of GNNs, so-called k-dimensional GNNs (k-GNNs), which can take higher-order graph structures at multiple scales into account. These higher-order structures play an essential role in the characterization of social networks and molecule graphs. Our experimental evaluation confirms our theoretical findings as well as confirms that higher-order information is useful in the task of graph classification and regression.

Key facts. Cited by 881 papers in the map (data through 14 Oct 2026). First posted on arXiv 4 Oct 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 127; 2022: 171; 2023: 187; 2024: 184; 2025: 122; 2026: 90.

881 papers.

Sort:

By area:

  1. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
  2. 2022DiGress: Discrete Denoising diffusion for graph generationcited by 520
  3. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 478
  4. 2021Rethinking Graph Transformers with Spectral Attentioncited by 473
  5. 2021GemNet: Universal Directional Graph Neural Networks for Moleculescited by 343
  6. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 333
  7. 2021Combinatorial optimization and reasoning with graph neural networkscited by 268
  8. 2022Long Range Graph Benchmarkcited by 263
  9. 2023One for All: Towards Training One Graph Model for All Classification Taskscited by 243
  10. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 221
  11. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  12. 2022Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNscited by 214
38 more
  1. 2021Large-Scale Chemical Language Representations Capture Molecular Structure and Propertiescited by 206
  2. 2021Adversarial Graph Augmentation to Improve Graph Contrastive Learningcited by 200
  3. 2021Identity-aware Graph Neural Networkscited by 198
  4. 2022Structure-Aware Transformer for Graph Representation Learningcited by 194
  5. 2022Discovering Invariant Rationales for Graph Neural Networkscited by 188
  6. 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
  7. 2022Graph neural networks for materials science and chemistrycited by 182
  8. 2023Exphormer: Sparse Transformers for Graphscited by 170
  9. 2022How Powerful are Spectral Graph Neural Networkscited by 169
  10. 2021Frame Averaging for Invariant and Equivariant Network Designcited by 168
  11. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 166
  12. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 155
  13. 2021Equivariant Subgraph Aggregation Networkscited by 154
  14. 2023Graph Inductive Biases in Transformers without Message Passingcited by 153
  15. 2022Learning Causally Invariant Representations for Out-of-Distribution Generalization on Graphscited by 144
  16. 2021Nested Graph Neural Networkscited by 137
  17. 2022Data Augmentation for Deep Graph Learning: A Surveycited by 133
  18. 2023Representational Strengths and Limitations of Transformerscited by 133
  19. 2021UniGNN: a Unified Framework for Graph and Hypergraph Neural Networkscited by 130
  20. 2021Scalars are universal: Equivariant machine learning, structured like classical physicscited by 127
  21. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 122
  22. 2021Accurate Learning of Graph Representations with Graph Multiset Poolingcited by 120
  23. 2021A Unified Lottery Ticket Hypothesis for Graph Neural Networkscited by 118
  24. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 118
  25. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  26. 2023Equivariant Architectures for Learning in Deep Weight Spacescited by 107
  27. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 105
  28. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  29. 2022Universal Prompt Tuning for Graph Neural Networkscited by 100
  30. 2021MMGCN: Multimodal Fusion via Deep Graph Convolution Network for Emotion Recognition in Conversationcited by 99
  31. 2022SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generatorscited by 99
  32. 2021Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patternscited by 95
  33. 2022Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networkscited by 94
  34. 2022A Generalization of ViT/MLP-Mixer to Graphscited by 93
  35. 2021GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddingscited by 90
  36. 2022How Powerful are K-hop Message Passing Graph Neural Networkscited by 90
  37. 2023On the Expressive Power of Geometric Graph Neural Networkscited by 90
  38. 2023Edge Directionality Improves Learning on Heterophilic Graphscited by 90

50 most cited of 881 All 881 (JSON)