mlsanityData to 7 Oct 2026

On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties

arXiv 1811.04801 ↗First posted 9 Nov 2018cs.DM cs.CC cs.LOcited by 63

Not on the map. Why?

Abstract (arXiv)

The k-dimensional Weisfeiler-Leman algorithm (k-WL) is a fruitful approach to the Graph Isomorphism problem. 2-WL corresponds to the original algorithm suggested by Weisfeiler and Leman over 50 years ago. 1-WL is the classical color refinement routine. Indistinguishability by k-WL is an equivalence relation on graphs that is of fundamental importance for isomorphism testing, descriptive complexity theory, and graph similarity testing which is also of some relevance in artificial intelligence. Focusing on dimensions k=1,2, we investigate subgraph patterns whose counts are k-WL invariant, and whose occurrence is k-WL invariant. We achieve a complete description of all such patterns for dimension k=1 and considerably extend the previous results known for k=2.

Key facts. Cited by 63 papers in the map (data through 7 Oct 2026). First posted on arXiv 9 Nov 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 14; 2023: 16; 2024: 12; 2025: 8; 2026: 1.

63 papers.

Sort:

  1. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  2. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 176
  3. 2021Equivariant Subgraph Aggregation Networkscited by 154
  4. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
  5. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  6. 2021Topological Graph Neural Networkscited by 86
  7. 2021Size-Invariant Graph Representations for Graph Classification Extrapolationscited by 82
  8. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 55
  9. 2021Graph Neural Networks with Local Graph Parameterscited by 51
  10. 2022A Theoretical Comparison of Graph Neural Network Extensionscited by 47
  11. 2021Autobahn: Automorphism-based Graph Neural Netscited by 39
  12. 2022Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networkscited by 39
38 more
  1. 2023Equivariant Polynomials for Graph Neural Networkscited by 38
  2. 2022SpeqNets: Sparsity-aware Permutation-equivariant Graph Networkscited by 37
  3. 2023On the Stability of Expressive Positional Encodings for Graphscited by 31
  4. 2023WL meet VCcited by 30
  5. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  6. 2023Fine-grained Expressivity of Graph Neural Networkscited by 25
  7. 2025Relational Deep Learning: Challenges, Foundations and Next-Generation Architecturescited by 22
  8. 2022A Practical, Progressively-Expressive GNNcited by 20
  9. 2021Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernelscited by 19
  10. 2021The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphscited by 19
  11. 2023On Structural Expressive Power of Graph Transformerscited by 19
  12. 2023Curvature Filtrations for Graph Generative Model Evaluationcited by 18
  13. 2021Ego-GNNs: Exploiting Ego Structures in Graph Neural Networkscited by 17
  14. 2023An Efficient Subgraph GNN with Provable Substructure Counting Powercited by 13
  15. 2023Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehmancited by 13
  16. 2023Distance-Restricted Folklore Weisfeiler-Leman GNNs with Provable Cycle Counting Powercited by 11
  17. 2023Discrete Graph Auto-Encodercited by 10
  18. 2023Cycle Invariant Positional Encoding for Graph Representation Learningcited by 8
  19. 2024Molecular Topological Profile (MOLTOP) -- Simple and Strong Baseline for Molecular Graph Classificationcited by 7
  20. 2025Towards A Universal Graph Structural Encodercited by 7
  21. 2023State of the Art and Potentialities of Graph-level Learningcited by 6
  22. 2023On the Power of the Weisfeiler-Leman Test for Graph Motif Parameterscited by 6
  23. 2025Enhancing Graph Representation Learning with Localized Topological Featurescited by 6
  24. 2024GEFL: Extended Filtration Learning for Graph Classificationcited by 5
  25. 2025Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centralitycited by 5
  26. 2022Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithmcited by 4
  27. 2023Improving Subgraph-GNNs via Edge-Level Ego-Network Encodingscited by 4
  28. 2025Homomorphism Expressivity of Spectral Invariant Graph Neural Networkscited by 4
  29. 2022Graph Representation Learning with Individualization and Refinementcited by 3
  30. 2024PF-GNN: Differentiable particle filtering based approximation of universal graph representationscited by 3
  31. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  32. 2022Uplifting Message Passing Neural Network with Graph Original Informationcited by 2
  33. 2022Beyond 1-WL with Local Ego-Network Encodingscited by 2
  34. 2024Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learningcited by 2
  35. 2024Harnessing Collective Structure Knowledge in Data Augmentation for Graph Neural Networkscited by 2
  36. 2024Theoretical Insights into Line Graph Transformation on Graph Learningcited by 2
  37. 2025Open Your Eyes: Vision Enhances Message Passing Neural Networks in Link Predictioncited by 2
  38. 2026Weisfeiler and Lehman Go Categoricalcited by 1

50 most cited of 63 All 63 (JSON)