Research map / Graph learning / GNN architectures
On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Characterizes the WL-dimension of labeled graph motif parameters via treewidth of their support, showing subgraph WL-dimension equals hereditary treewidth, induced subgraph WL-dimension equals pattern size minus 1, and gives a polynomial-time algorithm for subgraph WL-dimension.
Problem
Determining the least dimension k for which the k-dimensional Weisfeiler-Leman test can distinguish graphs with different numbers of occurrences of a pattern, both for subgraph and induced subgraph counting.
Approach
Shows the WL-dimension of a labeled graph motif parameter equals the maximum treewidth in its support, extends homomorphism-distinguishing closure results to labeled graphs, and shows exact counts can be computed by summing per-k-tuple local colour functions.
Key results
- WL-dimension of a labeled graph motif parameter equals the maximum treewidth of any graph in its support; subgraph counting WL-dimension equals hereditary treewidth of the pattern.
- Induced subgraph counting of a pattern H has WL-dimension equal to (number of nodes of H) minus 1, resolving an open question from prior work.
- Gives a polynomial-time algorithm to decide whether the WL-dimension of subgraph counting for a pattern is at most k.
Limitations
- Results concern worst-case behaviour; counterexamples are complicated and may not resemble practical graphs.
- Counting-to-colour result suggests but does not prove that k-dimensional MPGNNs can compute counts with suitable pooling.
Experimental setup
Builds on: Neuen's homomorphism-distinguishing closedness of bounded treewidth graphs Roberson's oddomorphisms Seppelt's motif parameter lemma Curticapean et al. homomorphism counting framework
Closest papers by meaning
- Homomorphism Counts for Graph Neural Networks: All About That Basis (ICML 2024 · similarity 0.90)
- Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning (NeurIPS 2024 · similarity 0.88)
- How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension (ICLR 2025 · similarity 0.87)
- Beyond Message Passing: Neural Graph Pattern Machine (ICML 2025 · similarity 0.86)
- Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them (NeurIPS 2026 · similarity 0.86)
- Generalizing Weisfeiler-Lehman Kernels to Subgraphs (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.