Introduction
While the theoretical expressiveness of Graph Neural Networks (GNNs) is traditionally measured by the Weisfeiler-Lehman (WL) hierarchy, there is a massive gap between what a model can distinguish in theory and what it actually distinguishes in practice. To bridge this gap, researchers have introduced BREC, a high-difficulty dataset of 400 graph pairs, and RPC (Reliable Paired Comparison), a statistically rigorous evaluation framework. Together, they provide the first comprehensive measurement of "realized" GNN expressiveness.
The Evaluation Bottleneck
For years, the GNN community has chased "beyond-1-WL" expressiveness—the ability to distinguish graphs that the standard 1-WL isomorphism test cannot. However, evaluating these advanced models has been a major bottleneck.
Existing benchmarks like EXP, CSL, and SR25 suffer from three main flaws:
- Saturation: They are too easy. Most modern models achieve near 100% accuracy, making it impossible to meaningfully compare them.
- Coarse Granularity: Models tend to either pass or fail completely, offering no insight into the nuanced "shades of gray" between 1-WL and 3-WL power.
- Small Scale: They often involve only a handful of essentially different graph structures.
Without a harder, more nuanced yardstick, researchers cannot determine if their theoretically superior models deliver more power in practical implementations.
Introducing BREC and RPC
To fix GNN evaluation, the authors propose two major contributions:
The BREC Dataset
BREC is a collection of 800 non-isomorphic graphs organized into 400 pairs. These pairs are specifically designed to be indistinguishable by the 1-WL test, with some remaining indistinguishable up to 4-WL. The dataset spans four categories:
- Basic & Regular: Including complex strongly regular and distance-regular graphs.
- Extension: Designed to test specific GNN architectural features.
- CFI: Highly complex graphs generated via the Cai-Furer-Immerman algorithm, representing the frontier of graph isomorphism difficulty.
Reliable Paired Comparison (RPC)
Instead of a standard classification task, the authors use a Siamese network architecture. The model is trained to minimize the cosine similarity between the embeddings of a non-isomorphic pair. To ensure that a model's ability to distinguish a pair isn't just due to random numerical noise, they employ Hotelling’s T-square test. This provides a formal confidence interval to verify if the differences in graph embeddings are statistically significant.
Key Insights: The Theory-Practice Gap
Testing 23 state-of-the-art models on BREC revealed several critical insights about realized expressiveness:
- Theoretical vs. Realized Power: Theoretical upper bounds are often optimistic. A model might be "theoretically 3-WL," but due to optimization challenges or architectural bottlenecks, its realized power on BREC might be much lower. In fact, several "beyond-1-WL" GNNs performed worse than the standard 3-WL baseline (which distinguishes 67.5% of the pairs) in practice.
- The "Dilution" Effect: Increasing the subgraph radius or the number of layers doesn't always help. It can sometimes decrease realized expressiveness because the receptive field becomes cluttered with extraneous or noisy data, leading to over-smoothing.
- Distance Encoding is Crucial: Models that explicitly encode distances (like $I^2$-GNN and DE+NGNN) show significantly higher realized expressiveness. Out of the 23 models tested, $I^2$-GNN achieved the highest overall accuracy at 70.2%. This suggests that how structural information is encoded is just as important as the underlying message-passing logic.
- CFI Graphs are the "Final Boss": Most current GNNs, even those claiming high theoretical power, struggle immensely with the CFI category.
Crucially, unlike previous datasets, no model came close to 100% accuracy on BREC. The results showed a wide spread of accuracies (from 41.5% to 70.2%), successfully providing the fine-grained comparison the authors sought and confirming ample headroom for future research.
Limitations and Future Directions
While BREC and RPC offer a massive leap forward, the approach has limitations. The RPC evaluation requires training a Siamese model for each pair of graphs. While this ensures the model is "trying its best" to distinguish them, it is computationally expensive compared to standard benchmarking. Additionally, the study focuses on the Graph Isomorphism (GI) problem as a proxy for expressiveness; it does not capture everything about a GNN's performance on downstream real-world tasks like node classification or link prediction.
Moving forward, BREC can serve as a rigorous testbed for searching optimal hyperparameters and inspiring new architectures capable of cracking the most difficult graph pairs.
Summary updated