An Empirical Study of Realized GNN Expressiveness

Yanbo Wang, Muhan Zhang

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:

  1. Saturation: They are too easy. Most modern models achieve near 100% accuracy, making it impossible to meaningfully compare them.
  2. 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.
  3. Small Scale: They often involve only a handful of essentially different graph structures.
Samples from existing datasets like EXP, CSL, and SR25

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.
A pair of complex, highly similar graphs

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

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, most methods do not have a uniform expressiveness measure except for a few that strictly follow the $k$-dimensional Weisfeiler-Lehman ($k$-WL) test hierarchy, leading to difficulties in quantitatively comparing their expressiveness. Previous research has attempted to use datasets for measurement, but facing 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 involved). To address these limitations, we study the realized expressive power that a practical model instance can achieve using a novel expressiveness dataset, BREC, which poses greater difficulty (with up to 4-WL-indistinguishable graphs), finer granularity (enabling comparison of models between 1-WL and 3-WL), a larger scale (consisting of 800 1-WL-indistinguishable graphs that are non-isomorphic to each other). We synthetically test 23 models with higher-than-1-WL expressiveness on BREC. Our experiment gives the first thorough measurement of the realized expressiveness of those state-of-the-art beyond-1-WL GNN models and reveals the gap between theoretical and realized expressiveness. Dataset and evaluation codes are released at: https://github.com/GraphPKU/BREC.
BibTeX
@inproceedings{wang2024empirical,
  author = {Yanbo Wang and Muhan Zhang},
  title = {{An Empirical Study of Realized GNN Expressiveness}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=WIaZFk02fI},
}
Figure