mlsanityData to 7 Oct 2026

The expressive power of kth-order invariant graph networks

arXiv 2007.12035 ↗First posted 23 Jul 2020cs.LG math.CO stat.MLcited by 34

Not on the map. Why?

Abstract (arXiv)

The expressive power of graph neural network formalisms is commonly measured by their ability to distinguish graphs. For many formalisms, the k-dimensional Weisfeiler-Leman (k-WL) graph isomorphism test is used as a yardstick. In this paper we consider the expressive power of kth-order invariant (linear) graph networks (k-IGNs). It is known that k-IGNs are expressive enough to simulate k-WL. This means that for any two graphs that can be distinguished by k-WL, one can find a k-IGN which also distinguishes those graphs. The question remains whether k-IGNs can distinguish more graphs than k-WL. This was recently shown to be false for k=2. Here, we generalise this result to arbitrary k. In other words, we show that k-IGNs are bounded in expressive power by k-WL. This implies that k-IGNs and k-WL are equally powerful in distinguishing graphs.

Key facts. Cited by 34 papers in the map (data through 7 Oct 2026). First posted on arXiv 23 Jul 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 11; 2023: 7; 2024: 5; 2025: 4; 2026: 1.

34 papers.

Sort:

By area:

  1. 2021Equivariant Subgraph Aggregation Networkscited by 154
  2. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  3. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  4. 2022How Powerful are K-hop Message Passing Graph Neural Networkscited by 90
  5. 2021Reconstruction for Powerful Graph Representationscited by 65
  6. 2022Expressiveness and Approximation Properties of Graph Neural Networkscited by 63
  7. 2022Theory of Graph Neural Networks: Representation and Learningcited by 60
  8. 2022Ordered Subgraph Aggregation Networkscited by 57
  9. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 55
  10. 2021Graph Neural Networks with Local Graph Parameterscited by 51
  11. 2021Autobahn: Automorphism-based Graph Neural Netscited by 39
  12. 2022SpeqNets: Sparsity-aware Permutation-equivariant Graph Networkscited by 37
22 more
  1. 2023WL meet VCcited by 30
  2. 2022Weisfeiler and Leman Go Relationalcited by 28
  3. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  4. 2021On the Universality of Graph Neural Networks on Large Random Graphscited by 26
  5. 2023Fine-grained Expressivity of Graph Neural Networkscited by 25
  6. 2022A Practical, Progressively-Expressive GNNcited by 20
  7. 2023An Efficient Subgraph GNN with Provable Substructure Counting Powercited by 13
  8. 2023Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehmancited by 13
  9. 2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
  10. 2022On the Ability of Graph Neural Networks to Model Interactions Between Verticescited by 12
  11. 2024Rethinking the Capacity of Graph Neural Networks for Branching Strategycited by 12
  12. 2022Convergence of Invariant Graph Networkscited by 8
  13. 2024On the Theoretical Expressive Power and the Design Space of Higher-Order Graph Transformerscited by 8
  14. 2023Improving Graph Neural Networks on Multi-node Tasks with the Labeling Trickcited by 4
  15. 2024Demystifying Higher-Order Graph Neural Networkscited by 4
  16. 2025Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualizationcited by 3
  17. 2025On Universality of Deep Equivariant Networkscited by 3
  18. 2023Local-to-global Perspectives on Graph Neural Networkscited by 2
  19. 2024Separation Power of Equivariant Neural Networkscited by 2
  20. 2025Generalization Performance of Hypergraph Neural Networkscited by 2
  21. 2025FS-KAN: Permutation Equivariant Kolmogorov-Arnold Networks via Function Sharingcited by 0
  22. 2026Graph Learning Should Move Beyond Restrictive Views of Spectral and Message-Passing GNNscited by 0