  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. Their theoretical analyses are often
limited to distinguishing certain families of non-isomorphic graphs, leading to
difficulties in quantitatively comparing their expressiveness. 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 a few essentially different graphs in each dataset). To address
these limitations, we propose a new expressiveness dataset, $\textbf{BREC}$,
which includes 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 (able to
compare models between 1-WL and 3-WL), and a larger scale (400 pairs). Further,
we synthetically test 23 models with higher-than-1-WL expressiveness on our
BREC dataset. Our experiment gives the first thorough comparison of the
expressiveness of those state-of-the-art beyond-1-WL GNN models. We expect this
dataset to serve as a benchmark for testing the expressiveness of future GNNs.
Our dataset and evaluation code are released at:
https://github.com/GraphPKU/BREC.

Machine Learning;Artificial Intelligence