Towards Better Evaluation of GNN Expressiveness with BREC Dataset

Yanbo Wang, Muhan ZhangSubmission to ICLR 2024 · Rejected

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:

  1. Low difficulty: Most beyond-1-WL models easily score 100% on CSL and EXP.
  2. Coarse granularity: Datasets rely on single graph families, turning model performance into an all-or-nothing step function (either random guess or 100%).
  3. 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

Abstract

Research on the theoretical expressiveness of Graph Neural Networks (GNNs) has developed rapidly, and many methods have been proposed to enhance the expressiveness. However, unifying all kinds of models into one framework is untractable, making it hard to measure and compare their expressiveness quantitatively. In contrast to theoretical analysis, another way to measure expressiveness is by evaluating model performance on certain datasets containing 1-WL-indistinguishable graphs. Previous datasets specifically designed for this purpose, however, face problems with difficulty (any model surpassing 1-WL has nearly 100\% accuracy), granularity (models tend to be either 100\% correct or near random guess), and scale (only several essentially different graphs in each dataset). To address these limitations, we propose a new expressiveness dataset, **BREC**, including 400 pairs of non-isomorphic graphs carefully selected from four primary categories (Basic, Regular, Extension, and CFI). These graphs have higher difficulty (up to 4-WL-indistinguishable), finer granularity (can compare models between 1-WL and 3-WL), and a larger scale (400 pairs or extend to 319600 pairs or even more). Further, we synthetically test 23 models with higher-than-1-WL expressiveness on our BREC dataset. Our experiment gives the first thorough measurement of the expressiveness of those state-of-the-art beyond-1-WL GNN models and reveals the gap between theoretical and practical expressiveness. We expect this dataset to serve as a benchmark for testing the expressiveness of future GNNs. Dataset and evaluation codes are released at: https://github.com/brec-iclr2024/brec-iclr2024.
BibTeX
@inproceedings{wang2024towards,
  author = {Yanbo Wang and Muhan Zhang},
  title = {{Towards Better Evaluation of GNN Expressiveness with BREC Dataset}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=WIaZFk02fI},
}
Figure