Towards Better Evaluation of GNN Expressiveness with BREC Dataset

Yanbo Wang, Muhan Zhang

While Graph Neural Networks (GNNs) are theoretically bounded by the Weisfeiler-Lehman ($k$-WL) hierarchy, their realized power in practice often falls short of these mathematical limits. This paper introduces BREC, a massive new dataset of 400 graph pairs, and RPC, a robust statistical evaluation framework, to finally provide a granular, reliable measurement of how expressive modern GNNs actually are.

The Theory-Practice Gap

For years, the gold standard for GNN expressiveness has been the $k$-WL test—a hierarchy of algorithms used to determine if two graphs are isomorphic (identical in structure). Most research focuses on proving a model is "theoretically as powerful as 3-WL."

However, the community has hit a wall in empirical testing. Existing benchmarks like EXP, CSL, and SR25 are either too small, too easy (modern models hit 100% accuracy instantly), or too coarse. If every new model gets 100% on the old tests, we can't tell which one is actually better. Furthermore, theoretical capacity doesn't guarantee that a model—constrained by numerical precision and optimization—can actually distinguish complex structures in the real world. There is a significant gap between what a model can do in theory and what it does do in practice.

The BREC Dataset

The paper introduces BREC (Benchmark for Realized Expressiveness Connection), which categorizes graphs into four levels of difficulty. The dataset consists of 800 non-isomorphic graphs organized into 400 pairs. These pairs are specifically designed to be indistinguishable by lower-order WL tests (up to 4-WL), providing a much higher "ceiling" for evaluation.

Examples of graph types in the BREC dataset, ranging from basic regular graphs to complex structures.

BREC categorizes graphs into four levels:

  • Basic: 60 pairs of 1-WL-indistinguishable graphs.
  • Regular: 140 pairs including strongly regular and distance-regular graphs (where 3-WL often fails).
  • Extension: 100 pairs designed to test specific GNN extensions like subgraph counting.
  • CFI: 100 pairs based on the Cai-Fürer-Immerman algorithm, pushing difficulty up to 4-WL indistinguishability.

Reliable Paired Comparison (RPC)

Traditional classification accuracy is a poor metric for pure expressiveness because it relies on generalization. Instead, the authors propose RPC (Reliable Paired Comparison). They use a Siamese Network architecture to train a GNN to maximize the distance between the embeddings of two non-isomorphic graphs using a contrastive loss.

A pair of complex, non-isomorphic graphs from the BREC dataset that are difficult for standard GNNs to distinguish.

To ensure that a model isn't just "guessing" due to random weight initialization or numerical noise, they use Hotelling’s T-square test. This allows them to statistically verify if the difference in embeddings is a result of the model actually "seeing" the structural difference or just floating-point fluctuations.

Key Insights and Results

The authors tested 23 representative GNN models, leading to several striking insights:

  • The Theory-Practice Gap: Many models with the same theoretical upper bound perform very differently on BREC. Theoretical "equivalence" does not mean practical "equality."
  • Saturation is Gone: While models hit 100% on old benchmarks, the best-performing model on BREC ($I^2$-GNN) only reached 70.2% accuracy. This proves the dataset is far from "saturated" and provides room for future research.
  • The 3-WL Barrier: Most standard GNNs struggle immensely with the CFI graphs (the hardest category), with many models scoring near 0% or 10% on these pairs.
  • Design Matters: Features like distance encoding (used in DE+NGNN and $I^2$-GNN) significantly amplify realized expressiveness, even if they don't always change the theoretical $k$-WL ranking.

Limitations and Future Work

While BREC is excellent for measuring structural discrimination (isomorphism), it doesn't directly measure how well these models perform on property prediction tasks like drug toxicity. Additionally, the RPC method is computationally expensive as it requires training a separate model for each graph pair. Future work should focus on developing models that can handle high-difficulty CFI graphs and investigating why certain "theoretically powerful" models fail to realize that power in practice.

Summary updated

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