Towards Better Evaluation of GNN Expressiveness with BREC Dataset

We thank reviewer D7WE for acknowledging the intricate design and insightful evaluation techniques. We answer your questions and address your concerns as follows:

W1: While the work is valuable, I believe that it is not novel enough in its current state. The tasks are very synthetic and even though I agree with the authors that the BREC dataset seems more interesting than existing benchmarks such as CSL, in my opinion it seems to be a marginal improvement over such datasets in terms of the novelty factor. There is definitely a need for such datasets in the community and the new evaluation technique is interesting, but I am not convinced that in its current state the work is fit for ICLR. Overall, this feels more of an "extension" to current datasets than something very novel.

R1:

We thank the reviewer for highlighting a pivotal criterion concerning benchmarks. BREC is not limited to an upgraded version of previous datasets but provides many additional perspectives in expressive power analysis. A critical difference between BREC and previous datasets is that BREC is a benchmark for testing "practical expressiveness" for the first time. However, previous datasets only serve to verify "theoretical expressiveness". We explain their difference in the following.

1. Previous expressiveness analysis mainly focused on "theoretical expressiveness", which represents the theoretical upper bound of the model under strong assumptions (deep enough layers, universal approximation of MLP, etc.). However, whether these models' practical implementations can achieve their theoretical power is constantly questioned and worth studying. Previous expressiveness datasets only served as a simple and incomplete verification due to their toy and repetitive components, making models tend to easily achieve 100% accuracy. Still, BREC is designed to test the "practical expressiveness", i.e., whether the theoretically powerful models can practically reach their expressiveness under more diverse, more difficult and larger scale settings than previous datasets.
2. The "practical expressiveness" results also lead to many interesting findings. For detailed analysis, please refer to R2.

Further, we would like to highlight again that BREC fundamentally differs from existing datasets in multiple aspects:

1. New evaluation method. Previous datasets do not consider evaluation techniques from an expressiveness perspective. They assign a label for each graph and consider it a classification task. It fundamentally restricts extending a toy dataset to a practical one.
2. Diversity in graphs. Previous toy datasets have too few components/graphs, where one set of hyperparameters can achieve perfect accuracy. BREC has many more pairs of distinct non-isomorphic graphs advanced in difficulty, granularity, and scale, which can test models' true expressivity.
3. Worthwhile experiment results. BREC not only verifies theoretical expressiveness but also provides more insightful findings. For example, BREC can test models without theoretical expressiveness characterizations. Half of the baselines we tested in Table 2 do not have a precise expressiveness analysis, but our experiment results make the quantification and comparison feasible. In contrast, previous datasets are restricted to 1-WL and 3-WL bounded models as their graphs are designed strictly following 1-WL/3-WL distinguishability. They cannot compare models between 1-WL and 3-WL, or beyond 3-WL.

Q1: “Would the authors be able to clarify any interesting findings that come from Table 2? It is a bit challenging for me to spot any significant trends the way it is currently ordered. It might be useful to further group the models based on their type.”

R2:

We thank the reviewer for the valuable suggestion. We have revised Table 2 in the updated paper by grouping each type of model. We also summarize the findings below.

1. There is gap between theoretical expressiveness and practical accuracy in many models. For example, PPGN is theoretically the same as 3-WL. However, our tests firstly show that it cannot reach its theoretical expressive power, even weaker than some models proven to be less powerful than 3-WL (e.g., SSWL_P). The gap can also explain why some models with high theoretical expressiveness do not perform well in real-world graphs.
2. Some techniques are very useful for improving the practical expressiveness. For example, distance encoding [1] greatly improves the performance of NGNN+DE, KPGNN, I2-GNN, SSWL_P, etc. In comparison, node labeling, which is proved to bring the same expressiveness improvement for subgraph-based models [2] as distance encoding, do not perform as well in practice. These findings can inspire new research on designing practically more powerful positional/structural encodings.
3. Generally, higher expressive power leads to better real-world performance. For example, subgraph-based models show excellent expressiveness results in our experiments, which align well with their state-of-art real-world performance [3]. Our results can serve as an efficient tool for analysis. A more detailed analysis can be found at R2 to reviewer ZHhj.

References

[1] Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning https://arxiv.org/abs/2009.00142

[2] A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests http://arxiv.org/abs/2302.07090

[3] Towards Arbitrarily Expressive GNNs in O(n2) Space by Rethinking Folklore Weisfeiler-Lehman https://arxiv.org/abs/2306.03266

Q2: “Would it be possible to clarify the contributions of the work? I understand that the work is proposing a new dataset and a new evaluation technique for it (which I find to be interesting and valid), but are there further novel contributions?”

R3:

We thank the reviewer for the valuable question. Other than the new dataset and evaluation technique (our major contributions), we summarize some other contributions as follows.

1. Discovering flaws of existing datasets: Previous datasets have limitations in their difficulty, granularity and scale. They cannot be used to evaluate newly proposed expressive models. As we pointed out in motivation, we are the first to discover inherent flaws of current datasets and propose a solution.
2. Revealing the gap between "theoretical expressiveness" and "practical expressiveness": Our dataset provides many additional perspectives in expressive power analysis. By revealing the gap between theoretical and practical expressiveness, we can find the influence of different strategies, components, frameworks, and other factors that may be underestimated.
3. We give the first and most thorough empirical expressiveness measurement results. The quantification is especially useful for models without precise expressiveness analysis. By comparing it with broader experiment results on real-world datasets, we can also capture what is needed regarding expressiveness. We hope users can utilize it and aid further research.

Finally, we would like to respectfully point out that ICLR welcomes a broad range of subject areas, including datasets and benchmarks (explicitly listed in topics). As a benchmark paper, our BREC has a clear motivation, intricate designs, and a sound evaluation pipeline, and it also addresses an urgent need of the community, which makes us believe that BREC meets the acceptance bar of ICLR. We appreciate the review's invaluable questions and advice, and kindly request the reviewer to reevaluate the contribution and novelty of our paper, possibly from a benchmark paper standard. We are profoundly thankful for your time and effort!

We appreciate Reviewer Bpfn's valuable questions and address the concerns as follows:

W1: Why do the authors adopt cosine similarity instead of other contrastive loss? Will this loss be possible to introduce any spurious correlation leading to biased results?

R1:

We appreciate the reviewer's meticulous examination of our evaluation methodology.Our choice of cosine similarity in the contrastive learning setting is notably simplified compared to common scenarios where batches of samples need to be separated. In our case, the objective is to distinguish only one sample from another, eliminating the necessity for certain properties, particularly the control of differences in one type. Unlike typical contrastive learning, which aims to maintain alignment and uniformity, and often introduces additional terms to regulate the distance between samples in one batch, such considerations are rendered unnecessary in our context. Consequently, we adhere to the simplest method to streamline the evaluation process.

W2: Since PPGN was compared, I'm wondering why "INVARIANT AND EQUIVARIANT GRAPH NETWORKS" was not included in the comparisons.

R2:

We appreciate the reviewer's observation regarding the exclusion of "INVARIANT AND EQUIVARIANT GRAPH NETWORKS" from our comparisons. While this model introduces invariant and equivariant layers and holds significance in expressiveness analysis [1, 2, 3], the original model it proposes, IGN, does not exhibit high expressiveness. As highlighted in [1], the k-IGN variant can implement k-WL but is constrained by the need for iterating k-th and 2k-th bell numbers' operations (the 4th bell number is 15, and the 6th bell number is 203), limiting its applicability and scalability to k <= 2. Furthermore, 2-WL is only as expressive as 1-WL, indicating that 2-IGN cannot distinguish any pairs of graphs in BREC. Consequently, we have chosen not to include IGN in our testing. Instead, we have evaluated several models inspired by IGN, such as PPGN [1], ESAN (DSS-GNN) [2], SUN [3], among others.

References

[1] Provably Powerful Graph Networks https://arxiv.org/abs/1905.11136

[2] Equivariant Subgraph Aggregation Networks https://arxiv.org/abs/2110.02910

[3] Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries https://arxiv.org/abs/2206.11140

We appreciate Reviewer ZHhj's insightful comments and address the concerns as follows:

W1: One concern is about the evaluation. It shows in Table 2 that only 400 samples are included in total. Including more samples in the datasets would make the experiments more convincing.

R1:

We thank the reviewer for emphasizing the importance of dataset size. We carefully considered how to construct the datasets initially and decided to use 400 pairs for coming reasons:

1. 400 samples are not small for expressiveness. Recalling that each sample includes 2 quite similar but non-isomorphic graphs, and all 800 graphs are non-isomorphic. Thus, generating 319,600 pairs of graphs (from CSL and SR25 settings) or even more by adding noisy components (from EXP settings) will be easy. However, we limit the number to 400 pairs (each graph appears only once) to keep the most essential and difficult comparisons.
2. Unlike large-scale real-world datasets, which require as many graphs as possible splited into train/val/test for testing generalization and scalability, our datasets aim to test expressiveness, where we do not need the model to generalize by training on big data. Instead, expressiveness datasets purely aim to measure models’ distinguishing power. Furthermore, we provide a reliable and precise evaluation method to obtain the exact distinguishable number of graphs with nearly no variance. This indicates that the current number of graphs is sufficient to reflect the expressiveness gap between different methods.
3. While it is feasible to expand the datasets by seamlessly sampling more graphs, certain graph types, such as Basic and Extension, lend themselves to exhaustive search sampling. However, this approach is not universally applicable, particularly for graphs like CFI or distance regular graphs, which are too rare to procure in larger quantities. Furthermore, enlarging the dataset in this manner may lead to an unbalanced distribution, disproportionately favoring simple graphs. Consequently, we have chosen to retain a set of 800 graphs.

W2: What about the relationship about the performance on the proposed synthetic datasets and real-world datasets? In other words, is the model that shows to more expressive in the benchmark performing better in real-world tasks? It would be better to provide more fine-grained analyses.

R2:

We thank the reviewer for underscoring the significance of practical utility concerning expressiveness. Generally, graphs in chemical areas tend to have high expressiveness demand. There exist some structures that standard MPNNs can hardly recognize. For example, the benzene ring (6-cycle) is a common and essential molecule component that most simple GNNs (including all MPNNs) cannot recognize. It is inevitable those GNNs might learn some statistical patterns correlated to benzene rings, but they fundamentally fail to understand the structure and fail to make predictions causally. In real-world datasets, expressive GNNs also perform remarkably in molecular datasets. ZINC [1] is a widely used molecular property regression benchmark. Currently, the 2 SOTA models are GRIT [2] and N$^2$-GNN [3], both focusing on expressiveness.

We collect our tested models' performance on ZINC:

Observably, N$^2$-GNN and SSWL_P outperform other models on the ZINC dataset. Both models exhibit commendable performance on BREC, particularly on CFI Graph, known for its substantial size and asymmetric composition, necessitating the model to discover graph pattern differences in its layers iteratively. The ZINC dataset, with its regression target "constrained solubility," incorporating water-octanol partition coefficient, synthetic accessibility score, and the number of cycles with more than six atoms, requires structure learning from a molecular accessibility perspective. Expressiveness, therefore, plays a pivotal role in enhancing model performance in the ZINC dataset.

References

[1] Benchmarking Graph Neural Networks https://arxiv.org/abs/2003.00982

[2] Graph Inductive Biases in Transformers without Message Passing http://arxiv.org/abs/2305.17589

[3] Towards Arbitrarily Expressive GNNs in O(n2) Space by Rethinking Folklore Weisfeiler-Lehman https://arxiv.org/abs/2306.03266