Research map / Graph learning / GNN architectures
Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness
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.
Introduces homomorphism expressivity as a complete, quantitative measure of GNN expressiveness and characterizes it for MPNN, Subgraph GNN, Local GNN and folklore-type GNNs via nested ear decompositions and treewidth, with subgraph counting implications and experiments.
Problem
Weisfeiler-Lehman hierarchy is coarse and qualitative and does not reflect practical GNN abilities such as substructure (subgraph) counting; a quantitative, complete expressivity measure is needed for comparing GNN architectures.
Approach
Define a GNN's expressivity as the family of patterns whose homomorphism counts the model's graph representation determines (homomorphism expressivity), prove it exists and is maximal for several GNN classes, and characterize these families by nested ear decompositions (and treewidth for k-FGNN); subgraph counting power then follows from spasm of patterns.
Key results
- Local 2-FGNN achieves the lowest error on all ZINC subset/full and Alchemy tasks (e.g., ZINC-subset MAE .064 vs MPNN .138).
- Local 2-(F)GNN counts all 3/4/5/6-cycles and chordal 4/5-cycles, performing significantly better than Subgraph GNN at equal cost.
- Theory: homomorphism expressivity of MPNN, Subgraph GNN, Local 2-GNN, Local 2-FGNN and 2-FGNN is characterized by forests, endpoint-shared/strong/almost-strong NED, and NED respectively, giving a strict hierarchy.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Local 2-FGNN instead of MPNN | GNN model · ZINC-subset | MAE: $.138 \pm .006$ -> $.064 \pm .002$ | Helped |
| Use Local 2-FGNN instead of MPNN | GNN model · ZINC-full | MAE: $.030 \pm .002$ -> $.023 \pm .001$ | Helped |
| Use Local 2-FGNN instead of MPNN | GNN model · Alchemy | MAE: $.122 \pm .002$ -> $.111 \pm .001$ | Helped |
Surprising findings
- Local 2-(F)GNN matches 2-FGNN in subgraph counting for all structures of moderate size, despite being much more efficient.
- Subgraph GNN cannot count rooted 5- and 6-cycles at node level, even though it can count 6-cycles at graph level.
Limitations
- Homomorphism expressivity of Local k-FGNN for k>2 lacks a NED-style description.
- Distance-based and spectral GNNs and some architectures (e.g., SpeqNet, I2-GNN) are not characterized.
- Existence of homomorphism expressivity for general refinement-based GNNs is only conjectured.
Experimental setup
Datasets: synthetic homomorphism counting benchmark cycle counting benchmark ZINC-subset ZINC-full Alchemy
Benchmarks: homomorphism counting synthetic task chordal cycle counting ZINC-subset ZINC-full Alchemy
Metrics: normalized MAE
Baselines: MPNN Subgraph GNN Local 2-GNN Local 2-FGNN
Builds on: 1-WL / Dell-Grohe-Rattan homomorphism characterization Subgraph GNN Local k-GNN k-FGNN
Closest papers by meaning
- Towards Bridging Generalization and Expressivity of Graph Neural Networks (ICLR 2025 · similarity 0.94)
- An Empirical Study of Realized GNN Expressiveness (ICML 2024 · similarity 0.94)
- Homomorphism Expressivity of Spectral Invariant Graph Neural Networks (ICLR 2025 · similarity 0.92)
- Bridging Theory and Practice in Link Representation with Graph Neural Networks (NeurIPS 2025 · similarity 0.92)
- On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry (NeurIPS 2026 · similarity 0.92)
- Weisfeiler-Leman at the margin: When more expressivity matters (ICML 2024 · similarity 0.92)
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.