mlsanityData to 7 Oct 2026

Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithm

arXiv 2206.02059 ↗First posted 4 Jun 2022cs.LG cs.AIcited by 4

Not on the map. Why?

Abstract (arXiv)

Message passing graph neural networks (GNNs) are known to have their expressiveness upper-bounded by 1-dimensional Weisfeiler-Leman (1-WL) algorithm. To achieve more powerful GNNs, existing attempts either require ad hoc features, or involve operations that incur high time and space complexities. In this work, we propose a general and provably powerful GNN framework that preserves the scalability of the message passing scheme. In particular, we first propose to empower 1-WL for graph isomorphism test by considering edges among neighbors, giving rise to NC-1-WL. The expressiveness of NC-1-WL is shown to be strictly above 1-WL and below 3-WL theoretically. Further, we propose the NC-GNN framework as a differentiable neural version of NC-1-WL. Our simple implementation of NC-GNN is provably as powerful as NC-1-WL. Experiments demonstrate that our NC-GNN performs effectively and efficiently on various benchmarks.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 48 of its 68 references that are in the map. First posted on arXiv 4 Jun 2022.

Builds on

48 of 68 references.

References · 48

  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. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  7. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  8. 2017Deep Setscited by 1,394
  9. 2019Strategies for Pre-training Graph Neural Networkscited by 964
  10. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  11. 2015Gated Graph Sequence Neural Networkscited by 792
  12. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
36 more
  1. 2020Benchmarking Graph Neural Networkscited by 672
  2. 2020A Generalization of Transformer Networks to Graphscited by 653
  3. 2020Principal Neighbourhood Aggregation for Graph Netscited by 477
  4. 2021Rethinking Graph Transformers with Spectral Attentioncited by 468
  5. 2019Provably Powerful Graph Networkscited by 385
  6. 2018Invariant and Equivariant Graph Networkscited by 339
  7. 2017Community Detection and Stochastic Block Modelscited by 317
  8. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  9. 2020SIGN: Scalable Inception Graph Neural Networkscited by 283
  10. 2015Diffusion-Convolutional Neural Networkscited by 268
  11. 2020Can Graph Neural Networks Count Substructures?cited by 235
  12. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 219
  13. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  14. 2021Identity-aware Graph Neural Networkscited by 197
  15. 2022Structure-Aware Transformer for Graph Representation Learningcited by 191
  16. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  17. 2020Random Features Strengthen Graph Neural Networkscited by 184
  18. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  19. 2021Equivariant Subgraph Aggregation Networkscited by 154
  20. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
  21. 2019Relational Pooling for Graph Representationscited by 150
  22. 2021Nested Graph Neural Networkscited by 136
  23. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  24. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 117
  25. 2021Global Self-Attention as a Replacement for Graph Convolutioncited by 113
  26. 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111
  27. 2020Building powerful and equivariant graph neural networks with structural message-passingcited by 95
  28. 2022Decoupling the Depth and Scope of Graph Neural Networkscited by 94
  29. 2022How Powerful are K-hop Message Passing Graph Neural Networkscited by 90
  30. 2018MotifNet: a motif-based Graph Convolutional Network for directed graphscited by 63
  31. 2018On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Propertiescited by 63
  32. 2022Theory of Graph Neural Networks: Representation and Learningcited by 60
  33. 2019k-hop Graph Neural Networkscited by 57
  34. 2019Coloring graph neural networks for node disambiguationcited by 49
  35. 2022SpeqNets: Sparsity-aware Permutation-equivariant Graph Networkscited by 37
  36. 2021Ego-GNNs: Exploiting Ego Structures in Graph Neural Networkscited by 17

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 2; 2026: 2.

4 papers.

  1. 2025Depth-Adaptive Graph Neural Networks via Learnable Bakry-'Emery Curvaturecited by 8
  2. 2025Message Passing on the Edge: Towards Scalable and Expressive GNNscited by 0
  3. 2026Invariant-Stratified Propagation for Expressive Graph Neural Networkscited by 0
  4. 2026Treatment Effect Estimation with Differentiated Networked Effect on Graph Datacited by 0