TL;DR
Existing benchmarks for testing whether Graph Neural Networks (GNNs) can distinguish non-isomorphic graphs are too small, too coarse, and saturated. To fix this, the authors introduce BREC, a benchmark of 400 carefully selected graph pairs spanning difficulty levels up to 4-WL-indistinguishable, paired with a statistically grounded evaluation framework called Reliable Paired Comparison (RPC). Benchmarking 23 beyond-1-WL models reveals that theoretical expressiveness does not always translate to practical performance, with the best model achieving only 70.2% accuracy.
What Problem Does This Paper Address?
Standard message-passing GNNs (MPNNs) are bounded by the 1-Weisfeiler-Lehman (1-WL) graph isomorphism test, meaning they fail to distinguish basic graph structures (such as certain regular graphs or rings). While many recent architectures claim expressiveness beyond 1-WL (using subgraphs, higher-order tensors, or substructure counting), comparing them theoretically is difficult because they operate under different mathematical abstractions.
Empirical evaluation on existing expressiveness benchmarks (EXP, CSL, SR25) is equally problematic:
- Low difficulty: Most beyond-1-WL models easily score 100% on CSL and EXP.
- Coarse granularity: Datasets rely on single graph families, turning model performance into an all-or-nothing step function (either random guess or 100%).
- Tiny scale: They contain only a handful of fundamentally distinct graph structures (e.g., 6 core pairs in EXP, 10 graphs in CSL, 15 graphs in SR25).
Methods
The paper introduces two major contributions: a dataset design and a statistical testing framework.
- Contrastive Siamese Architecture: Instead of casting expressiveness as multi-class classification (which introduces optimization and generalization confounds), models are trained on individual graph pairs using a Siamese network with cosine margin loss to directly maximize separation between non-isomorphic graphs.
- Reliable Paired Comparison (RPC): Comparing raw distances with an arbitrary threshold risks false positives (due to floating-point drift or permutation noise) or false negatives. RPC uses Hotelling's $T^2$-test:
- Major Procedure: Generates $q$ random permutations of $G$ and $H$, computes embedding differences, and checks if the mean difference $\mu \neq 0$ exceeds an $F$-distribution threshold ($T^2_{\text{test}} > \text{Threshold}$).
- Reliability Check: Repeats the procedure on isomorphic permutations of the same graph ($G$ vs. $G^\pi$). The test is valid only if internal fluctuations remain below the threshold ($T^2_{\text{reliability}} < \text{Threshold}$).
- A graph pair is deemed successfully distinguished only when $T^2_{\text{reliability}} < \text{Threshold} < T^2_{\text{test}}$.
Datasets
The authors propose BREC (800 non-isomorphic graphs organized into 400 pairs, with node counts up to 198):
- Basic (60 pairs): Non-regular, 10-node graphs where 1-WL fails, providing a baseline test.
- Regular (140 pairs): Contains 50 simple regular, 50 strongly regular (where 3-WL fails), 20 4-vertex condition, and 20 distance-regular graph pairs.
- Extension (100 pairs): Graphs specifically designed to differentiate theoretical extensions (substructure counting vs. $k$-hop subgraphs vs. marking).
- CFI (100 pairs): Built using the Cai-Fürer-Immerman construction, including pairs solely distinguishable by 3-WL (60 pairs), solely distinguishable by 4-WL (20 pairs), and pairs that even 4-WL cannot distinguish (20 pairs).
Key Insights and Ideas
- Theory vs. Practice Gap: High theoretical upper bounds do not guarantee high empirical distinguishability. For example, higher-order $k$-WL networks like PPGN and $\delta$-$k$-LGNN theoretically match or approach 3-WL, but struggle on large-diameter graphs (like CFI graphs) due to over-smoothing when scaled to sufficient depth.
- Distance Encodings Matter: Among subgraph GNNs, models with distance encodings (like $\text{I}^2$-GNN and DE+NGNN) maintain distinguishability across larger subgraph radii, whereas vanilla subgraph GNNs suffer from noise and informational smoothing as receptive fields expand.
- The Benchmark is Far From Solved: No tested model comes close to solving BREC. Even the strongest model fails on nearly 30% of the dataset, highlighting substantial room for architectural innovation.
Key Results
The authors evaluated 23 methods across 6 categories on BREC (400 total pairs):
| Category | Representative Model / Baseline | Total Accuracy (out of 400) | Basic (60) | Regular (140) | Extension (100) | CFI (100) |
|---|---|---|---|---|---|---|
| Non-GNN Baselines | 3-WL | 67.5% (270) | 100% | 35.7% | 100% | 60.0% |
| $N_2$ (2-hop neighborhood) | 74.5% (298) | 100% | 98.6% | 100% | 0.0% | |
| Subgraph GNNs | $\text{I}^2$-GNN (Best GNN) | 70.2% (281) | 100% | 71.4% | 100% | 21.0% |
| KP-GNN | 68.8% (275) | 100% | 75.7% | 98.0% | 11.0% | |
| SSWL_P | 62.0% (248) | 100% | 35.7% | 100% | 38.0% | |
| NGNN | 41.5% (166) | 98.3% | 34.3% | 59.0% | 0.0% | |
| $k$-WL GNNs | PPGN | 58.2% (233) | 100% | 35.7% | 100% | 23.0% |
| Substructure GNNs | GSN ($k=4$) | 63.5% (254) | 100% | 70.7% | 95.0% | 0.0% |
| Randomized GNNs | DropGNN | 44.2% (177) | 86.7% | 29.3% | 82.0% | 2.0% |
| Transformers | Graphormer | 19.8% (79) | 26.7% | 8.6% | 41.0% | 10.0% |
$\text{I}^2$-GNN achieved the top score among GNN architectures (70.2%), primarily due to enhanced cycle-counting capability on regular graphs.
Limitations and Future Work
- Focus on Isomorphism vs. Downstream Performance: BREC measures graph distinguishability under controlled pairwise comparisons; high expressiveness on BREC does not automatically guarantee superior generalization on noisy real-world property prediction tasks (e.g., molecular property regression).
- Pairwise Evaluation Overhead: Because evaluation trains Siamese networks over 400 distinct pairs (repeated over 10 random seeds), testing computationally expensive models is resource-intensive.
- Future Scope: The authors plan to investigate how fine-grained topological distinguishing capabilities transfer to real-world tasks and explore other expressiveness dimensions such as biconnectivity and diameter estimation.
Summary updated