mlsanityData to 14 Oct 2026

On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters

arXiv 2309.17053 ↗First posted 29 Sep 2023cs.LGcited by 6

Not on the map. Why?

Abstract (arXiv)

Seminal research in the field of graph neural networks (GNNs) has revealed a direct correspondence between the expressive capabilities of GNNs and the k-dimensional Weisfeiler-Leman (kWL) test, a widely-recognized method for verifying graph isomorphism. This connection has reignited interest in comprehending the specific graph properties effectively distinguishable by the kWL test. A central focus of research in this field revolves around determining the least dimensionality k, for which kWL can discern graphs with different number of occurrences of a pattern graph P. We refer to such a least k as the WL-dimension of this pattern counting problem. This inquiry traditionally delves into two distinct counting problems related to patterns: subgraph counting and induced subgraph counting. Intriguingly, despite their initial appearance as separate challenges with seemingly divergent approaches, both of these problems are interconnected components of a more comprehensive problem: "graph motif parameters". In this paper, we provide a precise characterization of the WL-dimension of labeled graph motif parameters. As specific instances of this result, we obtain characterizations of the WL-dimension of the subgraph counting and induced subgraph counting problem for every labeled pattern P. We additionally demonstrate that in cases where the kWL test distinguishes between graphs with varying occurrences of a pattern P, the exact number of occurrences of P can be computed uniformly using only local information of the last layer of a corresponding GNN. We finally delve into the challenge of recognizing the WL-dimension of various graph parameters. We give a polynomial time algorithm for determining the WL-dimension of the subgraph counting problem for given pattern P, answering an open question from previous work.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 27 of its 57 references that are in the map. First posted on arXiv 29 Sep 2023.

Builds on

27 of 57 references.

References · 27

  1. 2018How Powerful are Graph Neural Networks?cited by 4,393
  2. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  3. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,919
  4. 2017Modeling Relational Data with Graph Convolutional Networkscited by 1,694
  5. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,576
  6. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,138
  7. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  8. 2020Knowledge Graphscited by 621
  9. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  10. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 313
  11. 2021Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Predictioncited by 275
  12. 2019A Fair Comparison of Graph Neural Networks for Graph Classificationcited by 244
15 more
  1. 2019Inductive Relation Prediction by Subgraph Reasoningcited by 239
  2. 2020Can Graph Neural Networks Count Substructures?cited by 236
  3. 2017Encoding Sentences with Graph Convolutional Networks for Semantic Role Labelingcited by 137
  4. 2018On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Propertiescited by 63
  5. 2021Graph Neural Networks with Local Graph Parameterscited by 52
  6. 2023A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphscited by 32
  7. 2022Weisfeiler and Leman Go Relationalcited by 28
  8. 2018Lov'asz Meets Weisfeiler and Lemancited by 27
  9. 2022Inductive Logical Query Answering in Knowledge Graphscited by 26
  10. 2017On the Combinatorial Power of the Weisfeiler-Lehman Algorithmcited by 18
  11. 2017Homomorphisms Are a Good Basis for Counting Small Subgraphscited by 14
  12. 2020Message Passing Query Embeddingcited by 8
  13. 2018Network Global Testing by Counting Graphletscited by 5
  14. 2016Counting Answers to Existential Positive Queries: A Complexity Classificationcited by 3
  15. 2023Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minorscited by 3

Built on by

Cited by year

Citing papers per year: 2024: 4; 2025: 2.

6 papers.

  1. 2024Homomorphism Counts for Graph Neural Networks: All About That Basiscited by 16
  2. 2024Towards Bridging Generalization and Expressivity of Graph Neural Networkscited by 12
  3. 2024Homomorphism Counts as Structural Encodings for Graph Learningcited by 7
  4. 2024Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learningcited by 2
  5. 2025Studying and Improving Graph Neural Network-based Motif Estimationcited by 1
  6. 2025Message Passing on the Edge: Towards Scalable and Expressive GNNscited by 0