Research map / Graph learning / GNN architectures
An Empirical Study of Realized 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 BREC, a 400-pair (800-graph) expressiveness dataset spanning 1-WL to 4-WL-indistinguishable graphs, and a Reliable Paired Comparison (RPC) statistical test, then measures realized expressiveness of 23 beyond-1-WL GNN models.
Problem
Existing GNN expressiveness datasets (EXP, CSL, SR25) are too easy, too coarse-grained, and too small to quantitatively compare the realized expressiveness of practical GNN models beyond 1-WL, and fixed numerical thresholds for deciding distinguishability are unreliable.
Approach
Build a large, diverse, difficulty-graded set of non-isomorphic 1-WL-indistinguishable graph pairs (BREC) and decide pair distinguishability with a Hotelling T^2 paired-comparison test over random permutations, calibrated by a reliability check on isomorphic permutations, instead of a fixed embedding-distance threshold.
Key results
- I2-GNN achieves the highest accuracy on BREC at 70.2% (281/400 pairs), with GNN accuracies ranging from 41.5% to 70.2%.
- 3-WL distinguishes all Basic, Extension, and 60 CFI graphs, with 67.5% overall (270/400) accuracy.
- The RPC test yields reliable results where a fixed 1E-4 threshold misclassifies same-graph pairs (e.g., NGNN 'Same_1E-4' count of 160), supporting the reliability design.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use N₂ rather than other non-GNN baselines | non-GNN methods · BREC total | pair distinguishing accuracy: 74.5% | Helped |
| use I²-GNN rather than other evaluated GNNs | GNNs · BREC total | pair distinguishing accuracy: 70.2% | Helped |
| add training (ablation) | DS-GNN · BREC total | pairs distinguished: 80 -> 222 | Helped |
| add training (ablation) | I²-GNN · BREC total | pairs distinguished: 267 -> 281 | Helped |
| add training (ablation) | NGNN · BREC total | pairs distinguished: 166 -> 166 | No clear effect |
| increase 3-WL iterations from 1 to 5 (ablation) | 3-WL · BREC total | pairs distinguished: 193 -> 270 | Helped |
| increase subgraph radius from 3 to 6 (ablation) | Nₖ · BREC total | pairs distinguished: 300 -> 385 | Helped |
| increase subgraph radius beyond the best value | subgraph GNNs · BREC | realized expressiveness | Mixed |
| add distance encoding | DE+NGNN and I²-GNN · BREC | realized expressiveness | Helped |
| use a fixed threshold of 1E-4 instead of RPC (ablation) | GNN expressiveness evaluation · BREC | reliable pair evaluation: Same_1E-4 counts: 160 (NGNN), 214 (DE+NGNN), 400 (DropGNN) | Hurt |
| use RPC rather than a simple threshold strategy (ablation) | GNN expressiveness evaluation · BREC | reliable pair evaluation | Helped |
Surprising findings
- Realized expressiveness does not consistently increase with subgraph radius or number of layers, so radius and depth must be tuned.
- Some models (e.g., DE+NGNN, PPGN) at times fail to outperform 3-WL in realized expressiveness despite theoretical superiority.
Limitations
- Expressiveness measured via graph isomorphism distinguishability only, not other properties such as substructure counting.
- Results depend on hyperparameter tuning (subgraph radius, layers) per model, which may affect realized comparisons.
- RAPC's false-positive bound relies on distributional assumptions (Gaussian permutation noise) that are assumed rather than fully verified.
Experimental setup
Datasets: BREC EXP CSL SR25
Benchmarks: BREC
Metrics: pair distinguishing accuracy RPC T^2 test decision (reliability and distinguishability)
Baselines: 3-WL SPD-WL NGNN DE+NGNN DS-GNN DSS-GNN SUN SSWL_P
Builds on: Weisfeiler-Lehman test Paired Comparisons Hotelling's T-square test GNN extensions (Zhang et al. 2023) Cai-Furer-Immerman construction
Closest papers by meaning
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.94)
- Towards a Complete Logical Framework for GNN Expressiveness (ICLR 2025 · similarity 0.94)
- Towards Bridging Generalization and Expressivity of Graph Neural Networks (ICLR 2025 · similarity 0.91)
- Bridging Theory and Practice in Link Representation with Graph Neural Networks (NeurIPS 2025 · similarity 0.91)
- What Expressivity Theory Misses: Message Passing Complexity for GNNs (NeurIPS 2025 · similarity 0.90)
- Pruning for GNNs: Lower Complexity with Comparable Expressiveness (ICML 2025 · 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.