Research map / Graph learning / GNN architectures
Weisfeiler-Leman at the margin: When more expressivity matters
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.
Shows that 1-WL expressivity says little about generalization, derives margin-based tight VC-dimension bounds for 1-WL kernels and MPNNs with subgraph-augmented variants, and proves gradient flow aligns linear MPNN weights to the max-margin solution.
Problem
Whether and when increased expressive power of 1-WL-based graph kernels and MPNNs translates into better generalization, since VC-dimension bounds tied to isomorphism classes predict the opposite of empirical trends.
Approach
Uses the data's geometric margin (via partial-concept VC theory) rather than graph-isomorphism expressivity to characterize generalization; augments 1-WL with subgraph-based initial labels (1-WL_F, 1-WLOA_F) and shows when this makes data linearly separable or increases the margin, and that gradient flow on linear MPNNs converges to the max-margin direction.
Key results
- On synthetic regular-graph datasets (n=16 to 128), 1-WL_F with cycles achieves 100% test accuracy with positive margin while 1-WL is not linearly separable (~47% accuracy).
- On TUDatasets, 1-WL_F with subgraph sets (e.g., C3-C4) improves MUTAG test accuracy to 40.6% kernel-based vs 34.1% for 1-WL in the table, and 1-WLOA_F variants match or exceed 1-WLOA on several datasets (e.g., PTC_FM 59.6% vs 58.2%).
- Theory: VC dimension of 1-WL-based kernels and MPNNs is Theta(r^2/lambda^2) under margin assumptions, and gradient flow on linear MPNNs converges to the max-margin solution.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add subgraph information to 1-WL | 1-WL · Synthetic graphs (16, 32, 64, and 128 vertices) | test accuracy: 46.6 { $\pm 1.1$} -> 100.0 { $\pm 0.0$}; 47.3 { $\pm 1.7$} -> 100.0 { $\pm 0.0$}; 47.1 { $\pm 1.1$} -> 100.0 { $\pm 0.0$ | Helped |
| Add subgraph information to 1-WLOA | 1-WLOA · Synthetic graphs (16, 32, 64, and 128 vertices) | test accuracy: 36.8 { $\pm 1.3$} -> 100.0; 37.4 { $\pm 1.7$} -> 100.0; 37.3 { $\pm 0.9$} -> 100.0; 37.8 { $\pm 1.2$} -> 100.0 | Helped |
| Add subgraph information to MPNN | MPNN · Synthetic graphs (16, 32, 64, and 128 vertices) | test accuracy: 47.9 { $\pm 0.7$} -> 100.0 { $\pm $0.1}; 49.0 { $\pm 1.6$} -> 100.0 { $\pm 0.1$}; 48.3 { $\pm 1.3$} -> 100.0 { $<0.1$}; | Helped |
| Use subgraph information in 1-WL_F | 1-WL · Synthetic graphs (16, 32, 64, and 128 vertices) | margin: 0.006; 0.014; 0.030; 0.062 | Helped |
Surprising findings
- Expressivity beyond 1-WL in terms of isomorphism does not by itself imply better generalization; adding subgraph information can shrink the margin for some data distributions.
- On several TUDatasets the gains from subgraph augmentation are small and within standard deviations, so the empirical benefit is modest.
Limitations
- Tight VC bounds for 1-WL-based embeddings require n large relative to r^2/lambda^2 and regular-graph constructions; the bounds lack explicit graph-structure dependence.
- Gradient flow convergence is proven only for linear MPNNs with exponential loss; nonlinear activations are left open.
- Empirical gains from subgraph augmentation on TUDatasets are often within standard deviations.
Experimental setup
Datasets: ENZYMES MUTAG PROTEINS PTC_FM PTC_MR synthetic graphs constructed per proof (regular graphs on 16-128 vertices) synthetic Erdos-Renyi graphs labeled by cycle/clique counts
Benchmarks: ENZYMES MUTAG PROTEINS PTC_FM PTC_MR synthetic separability datasets
Metrics: test accuracy train accuracy margin
Baselines: 1-WL kernel 1-WLOA GIN MPNN
Builds on: 1-WL WL optimal assignment kernel VC dimension of partial concepts GIN Tang and Liu-style gradient flow alignment results
Closest papers by meaning
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.92)
- Towards Bridging Generalization and Expressivity of Graph Neural Networks (ICLR 2025 · similarity 0.91)
- On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry (NeurIPS 2026 · similarity 0.90)
- Aligning Transformers with Weisfeiler-Leman (ICML 2024 · similarity 0.90)
- Homomorphism Expressivity of Spectral Invariant Graph Neural Networks (ICLR 2025 · similarity 0.89)
- Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them (NeurIPS 2026 · similarity 0.89)
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.