Performance Heterogeneity in Message-Passing and Transformer-based Graph Neural Networks

We thank the reviewer for reading our submission. We politely disagree with the reviewer’s assessment of the paper. We believe that there are several misunderstandings regarding the motivation, methodology and contributions of our paper.

We maintain that the paper’s focus on individual performance in graph-level learning offers a new perspective on performance heterogeneity. To the best of our knowledge, the selective rewiring approach and heuristic for the GNN depth are novel. This was also acknowledged by the other reviewers.

We respond to a few of the points that the reviewer raised.

The paper highlights the variance in GNN performance on graph-level tasks; however, I believe this contribution does not offer new insights to the community. It is already well-established that Graph Neural Networks (GNNs) exhibit performance inconsistencies and that the effectiveness of different models often varies across datasets [1, 2]. Furthermore, the paper fails to propose a concrete solution to address this phenomenon. Inconsistencies in evaluation across sections further undermine its findings, as I will elaborate in my next comment.

• We strongly disagree with the notion that there are no new insights to be gained here and believe that there is a misunderstanding. In fact, both of the papers pointed to by the reviewer focus on dataset-level accuracy (i.e. average over all nodes in node-level tasks and average over all graphs in graph-level tasks). They then study how model performance varies between datasets. This is fundamentally different from the graph-level approach we take: we focus on how performance varies within datasets, not between them. As such, our approach is similar to what [1] have proposed in the vision space. To the best of our knowledge, no comparable studies have been conducted for GNNs.

The authors investigate the inconsistency of performance on graph-level tasks by examining a range of models and datasets. However, the presentation lacks clarity regarding the consistency of their selections. For instance, in Section 3.2, three datasets are analyzed using two GNN architectures [...]

• Many of the experiments are conducted on LRGB, which is a state-of-the-art graph learning benchmark. Some experiments involving the computation of the TMD are only performed on small data sets. As stated in section 3.3 this is because TMD does not scale to larger datasets.
• We do not believe that testing rewiring methods with a global-attention based model like GPS would be insightful because the computation graph here is learned by the model (via attention) and is therefore not limited by the topology (unlike in message-passing). Our analysis based on consensus dynamics does therefore not immediately apply here. We would further like to point out that we are not aware of any papers in the literature that combine rewiring approaches with global-attention based models, most likely because those are usually assumed to not suffer from over-smoothing or over-squashing.
• In the next version, we will extend our investigation of heterogeneity in section 2 to include additional transformer architectures.

[1] Kaplun, Gal, et al. "Deconstructing Distributions: A Pointwise Framework of Learning." The Eleventh International Conference on Learning Representations.

We thank the reviewer for the feedback on our submission.

There is certainly merit in investigating the impact factors for the performance of GNN and I do like a more systematic approach. However, given the fact that GNN can be viewed as a function with the input of both structure and feature, it seems obvious that both feature and structure would affect the output/performance of GNNs. With this said, I am not convinced and not comfortable with the claim that topology is enough to explain node-level tasks (see [1] for an example).

• We would like to point the reviewer to [1] and [2], which show experimentally that node degree is highly indicative of GNN performance in many real-world datasets. [2] can even rigorously connect node separability (as a proxy for GNN performance) and node degree in certain stylized settings.

One of the claimed contribution is the so-called "heterogeneity profiles". I do not see a detailed introduction or discussion on this technique and why it is novel. Based on the description on Section 3, it seems a standard random experiments/k-fold validation. Please correct me if I am wrong

• We will provide a more explicit definition of heterogeneity profiles in the next version.
• We believe that there is a misunderstanding with our methodology. This is not k-fold validation: k-fold validation would randomly split the data and then report average accuracy on the test set. Instead, we look at individual graph-level accuracy.

The claimed research question investigates the factors that explain performance heterogeneity. However, the explained framework (tree mover distance) used in the paper is directly adopted from another paper. What is the new insight provided in this paper? In addition, there are many other distance metric such as FID can combine structure and feature. Why not consider those?

• Please note that while the TMD is indeed not novel (which is clearly stated in the paper), the notion of the class-distance ratio (CDR) is novel, as is the insight that CDR explains largely graph-level performance. We can think of the CDR as a notion of dataset separability derived from the TMD. Other graph distance measures could indeed also be used, but those generally scale even worse than TMD [3].

The paper tries to connect the experimental insight with graph rewiring and over-smoothing. The papers try to connect over-smoothing with the diffusion property of graph structure (fiddle eigenvalue of graph matrix). Despite being somewhat intuitive, it is not a strong explanation for over-smoothing as it is not clear how the diffusive property of graph structure would affect training or generalization. In addition, I think this diffusive property would largely affect node-level tasks. It is not entirely clear to me why this concept is applicable for graph-level tasks. Please explain. While I do think that selective graph rewiring could be a highlight of the paper, the paper does not go into detail in this regard. For example, how do you use the empirical result/theoretical result to obtain the proposed criteria for the selection?

• Over-smoothing is not a focus of this paper, but rather model and hyperparameter choices that account for performance heterogeneity in graph-level learning. While rewiring is used to mitigate over-smoothing, the spectral rewiring method that we consider (FoSR) only address over-squashing, not over-smoothing.

the presentation and organization of the paper need to be improved. I think the paper right now attempts to connect too many concepts and methods (performance heterogeneity, over-smoothing, graph rewiring e.t.c). I do admire the ambitious goal. However, in the current version of the paper, the connections among these concepts and methods are presented in a rather superficial way (this might be because of the page limit). I do encourage the authors to dive deeper into these connections as they are important for advancing GNN.

• We appreciate any feedback on improving the structure of the paper.

[1] Liang, Langzhang, et al. "Resnorm: Tackling long-tailed degree distribution issue in graph neural networks via normalization." arXiv preprint arXiv:2206.08181 (2022).

[2] Li, Ting Wei, Qiaozhu Mei, and Jiaqi Ma. "A metadata-driven approach to understand graph neural networks." Advances in Neural Information Processing Systems 36 (2024).

[3] Chuang, Ching-Yao, and Stefanie Jegelka. "Tree mover's distance: Bridging graph metrics and stability of graph neural networks." Advances in Neural Information Processing Systems 35 (2022): 2944-2957.

We thank the reviewer for the encouraging feedback.

• We provide details on hyperparameter choices in the appendix. We will expand this description in the next version.
• To the best of our knowledge, this work is the first to systematically study performance heterogeneity in graph-level learning. We would be grateful for any pointers to "other state-of-the-art methods" that the reviewer can provide.
• LRGB is a commonly used, large-scale benchmark. We will add additional results on the suggested OGB tasks in the next version of the manuscript.

Response to questions:

• We find heterogeneity to appear with various widths, depths, learning rates, activation functions, and dropout rates.
• We order the graphs by their indices in the datasets, allowing us to compare models.

We thank the reviewer for the feedback and suggestions on how to improve the paper. Regarding the weakness that the reviewer mentions:

• LRGB is the most common benchmark for testing how well models encode long-range interactions between nodes. It is generally considered a “challenging” benchmark. However, we will add additional results on the suggested OGB tasks in the next version of the manuscript.
• The selective rewiring approach and depth heuristic are informed by the graph’s topology (characterized by the spectrum of the Graph Laplacian) and should be computed for the data set at hand. Our experimental results corroborate the utility of those heuristics.