mlsanityData to 7 Oct 2026

Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing

arXiv 2102.08786 ↗First posted 17 Feb 2021cs.LG cs.SIcited by 46

Not on the map. Why?

Abstract (arXiv)

We propose CRaWl, a novel neural network architecture for graph learning. Like graph neural networks, CRaWl layers update node features on a graph and thus can freely be combined or interleaved with GNN layers. Yet CRaWl operates fundamentally different from message passing graph neural networks. CRaWl layers extract and aggregate information on subgraphs appearing along random walks through a graph using 1D Convolutions. Thereby it detects long range interactions and computes non-local features. As the theoretical basis for our approach, we prove a theorem stating that the expressiveness of CRaWl is incomparable with that of the Weisfeiler Leman algorithm and hence with graph neural networks. That is, there are functions expressible by CRaWl, but not by GNNs and vice versa. This result extends to higher levels of the Weisfeiler Leman hierarchy and thus to higher-order GNNs. Empirically, we show that CRaWl matches state-of-the-art GNN architectures across a multitude of benchmark datasets for classification and regression on graphs.

Key facts. Cited by 46 papers in the map (data through 7 Oct 2026). Builds on 40 of its 72 references that are in the map. First posted on arXiv 17 Feb 2021.

Builds on

40 of 72 references.

References · 40

  1. 2017Attention Is All You Needcited by 59,932
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  3. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  4. 2017Graph Attention Networkscited by 8,854
  5. 2017Inductive Representation Learning on Large Graphscited by 6,284
  6. 2018How Powerful are Graph Neural Networks?cited by 4,355
  7. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  8. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  9. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  10. 2016Xception: Deep Learning with Depthwise Separable Convolutionscited by 2,320
  11. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  12. 2016node2vec: Scalable Feature Learning for Networkscited by 1,913
28 more
  1. 2017MoleculeNet: A Benchmark for Molecular Machine Learningcited by 1,037
  2. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  3. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  4. 2020Benchmarking Graph Neural Networkscited by 672
  5. 2020A Generalization of Transformer Networks to Graphscited by 653
  6. 2020Principal Neighbourhood Aggregation for Graph Netscited by 477
  7. 2019Provably Powerful Graph Networkscited by 385
  8. 2018Invariant and Equivariant Graph Networkscited by 339
  9. 2016Learning Convolutional Neural Networks for Graphscited by 314
  10. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  11. 2020Can Graph Neural Networks Count Substructures?cited by 235
  12. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  13. 2021Inductive Representation Learning in Temporal Networks via Causal Anonymous Walkscited by 188
  14. 2020Random Features Strengthen Graph Neural Networkscited by 184
  15. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 160
  16. 2019Relational Pooling for Graph Representationscited by 150
  17. 2019A Survey on Graph Kernelscited by 148
  18. 2020Directional Graph Networkscited by 132
  19. 2020Hierarchical Inter-Message Passing for Learning on Molecular Graphscited by 59
  20. 2020Wasserstein Embedding for Graph Learningcited by 56
  21. 2018Anonymous Walk Embeddingscited by 46
  22. 2017Learning Graph-Level Representation for Drug Discoverycited by 43
  23. 2020Path Integral Based Convolution and Pooling for Graph Neural Networkscited by 35
  24. 2020Graph convolutions that can finally model local structurecited by 31
  25. 2020Beyond Localized Graph Neural Networks: An Attributed Motif Regularization Frameworkcited by 10
  26. 2017Motif-based Convolutional Neural Network on Graphscited by 7
  27. 2021Node2Seq: Towards Trainable Convolutions in Graph Neural Networkscited by 5
  28. 2020Walk Message Passing Neural Networks and Second-Order Graph Neural Networkscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 2; 2023: 6; 2024: 14; 2025: 15; 2026: 6.

46 papers.

Sort:

By area:

  1. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
  2. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  3. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  4. 2024Graph Mamba: Towards Learning on Graphs with State Space Modelscited by 84
  5. 2023Where Did the Gap Go? Reassessing the Long-Range Graph Benchmarkcited by 83
  6. 2022SpeqNets: Sparsity-aware Permutation-equivariant Graph Networkscited by 37
  7. 2023Cooperative Graph Neural Networkscited by 35
  8. 2023Path Neural Networks: Expressive and Accurate Graph Neural Networkscited by 32
  9. 2023Adaptive Message Passing: A General Framework to Mitigate Oversmoothing, Oversquashing, and Underreachingcited by 23
  10. 2024Learning Long Range Dependencies on Graphs via Random Walkscited by 18
  11. 2025Beyond Message Passing: Neural Graph Pattern Machinecited by 17
  12. 2024Understanding Virtual Nodes: Oversquashing and Node Heterogeneitycited by 14
34 more
  1. 2024Topology-Informed Graph Transformercited by 13
  2. 2024Revisiting Random Walks for Learning on Graphscited by 13
  3. 2024Benchmarking Positional Encodings for GNNs and Graph Transformerscited by 13
  4. 2021Implicit vs Unfolded Graph Neural Networkscited by 12
  5. 2025Flatten Graphs as Sequences: Transformers are Scalable Graph Generatorscited by 12
  6. 2024Towards Principled Graph Transformerscited by 11
  7. 2024Non-convolutional Graph Neural Networkscited by 11
  8. 2025Generative Graph Pattern Machinecited by 11
  9. 2024Unitary convolutions for learning on graphs and groupscited by 8
  10. 2025Flock: A Knowledge Graph Foundation Model via Learning on Random Walkscited by 8
  11. 2024Best of Both Worlds: Advantages of Hybrid Graph Sequence Modelscited by 6
  12. 2025Semantic Refinement with LLMs for Graph Representationscited by 6
  13. 2023Diffusing Graph Attentioncited by 5
  14. 2024CKGConv: General Graph Convolution with Continuous Kernelscited by 4
  15. 2024Automatic Graph Topology-Aware Transformercited by 4
  16. 2025Graph Representational Learning: When Does More Expressivity Hurt Generalization?cited by 4
  17. 2021Permute Me Softly: Learning Soft Permutations for Graph Representationscited by 3
  18. 2025Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNscited by 3
  19. 2025Plain Transformers Can be Powerful Graph Learnerscited by 2
  20. 2025Generalizable Insights for Graph Transformers in Theory and Practicecited by 2
  21. 2024GQWformer: A Quantum-based Transformer for Graph Representation Learningcited by 1
  22. 2025Random Search Neural Networks for Efficient and Expressive Graph Learningcited by 1
  23. 2026Capacity-Controlled Global Attention for Graph Transformerscited by 1
  24. 2026From Message-Passing to Linearized Graph Sequence Modelscited by 1
  25. 2026End-to-End Subgraph Detection with GraphDETRcited by 1
  26. 2024Learning From Simplicial Data Based on Random Walks and 1D Convolutionscited by 0
  27. 2025ExPath: Targeted Pathway Inference for Biological Knowledge Bases via Graph Learning and Explanationcited by 0
  28. 2025Caterpillar GNN: Replacing Message Passing with Efficient Aggregationcited by 0
  29. 2025TANGO: Graph Neural Dynamics via Learned Energy and Tangential Flowscited by 0
  30. 2025Learn to Jump: Adaptive Random Walks for Long-Range Propagation through Graph Hierarchiescited by 0
  31. 2025DARTS-GT: Differentiable Architecture Search for Graph Transformers with Quantifiable Instance-Specific Interpretability Analysiscited by 0
  32. 2026GCCM: Enhancing Generative Graph Prediction via Contrastive Consistency Modelcited by 0
  33. 2026Beyond Oversquashing: Understanding Signal Propagation in GNNs Via Observablescited by 0
  34. 2026HOPPER: Learnable Hop Extraction for Linearized Graph Sequence Modelscited by 0