Size Generalization of Graph Neural Networks on Biological Data: Insights and Practices from the Spectral Perspective

We thank the reviewer for acknowledging the insights of our paper and the effectiveness of our proposed methods. We also thank the reviewer for appreciating the soundness and presentation of our work. We appreciate all the questions and feedback the reviewer raised. In the following, we carefully respond to each of the concerns and suggestions that the reviewer raised.

Q4.1 Transferability of results

As mentioned in the general response, one important insight brought up by this paper is that the covariate shifts caused by variations in sizes are dependent on the data domain. Thus, we restrict our attention to the biological domain. More importantly, most existing datasets for graph classification belong to the biological or chemistry domain.

Q4.2 Augmentation similar to prior approaches

We would like to acknowledge that augmentation is not a unique technique proposed by us and neither is that the main contribution of this paper. Instead, it provides tools to validate the main insights of this paper --- leveraging cycle information in GNN can improve size generalizability on biological data. Our insights are orthogonal to different methodology-driven papers and can be integrated with those methods.

Q4.3 Additional time for augmentation

In practice, our proposed strategies do not substantially increase training time. For cycle augmentation, we perform augmentations before training and thus do not incur overhead time during classification. For SIA, it incurs additional time due to the attention mechanism on each graph. We present per-epoch runtime statistics as below:

Q4.4 Other datasets

As mentioned in the general response, our selection of datasets is based on the biological domain, and the dataset should not suffer significantly from other issues that blur the focus on size generalization. More details can be found in the datasets section in the general response.

We thank the reviewer for acknowledging the novelty of the spectral analysis and the effectiveness of our proposed methods. We also thank the reviewer for carefully reading our paper and detailed comments. We appreciate all the questions and feedback the reviewer raised, especially the one on drawing our attention to expressive models and the number of related works provided. In the following, we carefully respond to each of the concerns and suggestions that the reviewer raised.

Q3.1 Size generalizability and the number of cycles

Thank you for your great suggestion. We present the following table to show the statistics of the average number of cycles that small and large graphs contain respective to their size.

It can be seen that the average num_cycle/num_nodes are highly similar for small and large graphs for most datasets. Due to this reason, it is unlikely that the number of cycles is closely related to size generalization.

Q3.2 Besides cycles, can there be any substructure that changes the spectrum according to changes in size and number?

There can be. The insights for our investigation into cycles are based on our discernment of variations in the peaks of specific frequencies within the graph spectrum, such as the frequency=1 in unnormalized Laplacian matrices. Many of these specific frequencies align with the frequencies of cycles, with cycles containing 5-7 nodes being particularly evident. As a reminder, the spectrum for a cycle with n nodes is given by the formula 2-2cos(2πj/n). We also computed the spectrum of other substructures such as lines, but their difference in small and large graphs is not consistent across different biological datasets.

Q3.4 Comparison with other baselines

We have added more baselines in Table 4 (including some expressive GNN models). For more details, please refer to the baseline section in the general response and Table 4 in our updated submission. In general, the proposed method SIA still achieves best performance and is model-agnostic. Thank you for your valuable suggestions, we do find that expressive model that excels at detecting cycles have good size generalizability on certain datasets.

Q3.5 performance in the class imbalance setting of the original data

In our experiments, we find that certain backbone models tend to be very biased towards the major class and thus result in an extremely skewed performance. For instance, the FAGCN and MLP backbone model always outputs a test accuracy (and thus unreliable F1 score) that is almost the same as the proportion of the larger class. In order to prevent such cases from happening, we decided to adopt upsampling.

Q3.6 Is size generalizability using cycle applicable to other data domains beyond the biological domain?

It might be also applicable to the chemistry domain. For the other domains, it relies on further investigation of the spectrums. However, most existing datasets for graph classification belong to the biological or chemistry domain.

We thank the reviewer for acknowledging the insight of this paper in identifying cycle-related information. We value the constructive feedback that the reviewer provided. In the following, we carefully respond to each of the concerns and questions that the reviewer raised.

Q2.1 Insufficient experiments and comparison with baselines

We have added more baselines in Table 4. For more details, please refer to the baseline section in the general response and Table 4 in our updated submission. In general, the proposed method SIA still achieves the best performance and is model-agnostic.

Q2.2 Novelty wrt. "From local structures to size generalization in graph neural networks"

Actually, the empirical findings of our paper are contradictory to the assumptions made by the paper "From local structures to size generalization in graph neural networks". In their paper, they hold the assumption that the degree patterns change with graph sizes. However, in Appendix G of our updated paper, we find that the degree distribution does not show a clear correlation with the graph size on biological datasets. Our main contribution is that we find cycle-related information (existence of cycles, average cycle length) is critical for size generalization for biological data, which has not been proposed before.

Q2.3 Why is the algorithm description incomplete in the text, such as the section 4.3? If not essential, it could be excluded as the part of the contributions.

This is primarily due to page limits. In fact, we have explained well about the motivation as well as the main function of this algorithm at the same paragraph. We leave the details of implementation in the Appendix for further interest.

Thank you for the detailed explanation, which addressed many of my concerns. However, I still have some concerns:

• What are the exact errors for loading the splits by Bevilacqua et al. 2021?
• As acknowledged by the authors, the focus of the paper is on the biological data. The class imbalance issue generically exists in biological data, and would affect all methods. If the proposed method could indeed address the graph size shifts, then there are still improvements expected to be observed. Otherwise, without experiments on real data, the scope of the paper could be very limited;
• I appreciate the authors' efforts in making the comparison with [3], but why [2] is neglected in comparison?

We thank the reviewer for appreciating the novelty of the spectral analysis and the writing of this paper. We also thank the reviewer for carefully reading our paper and detailed comments. We appreciate all the questions and feedback the reviewer raised, especially on the number of related works provided. In the following, we carefully respond to each of the concerns and suggestions that the reviewer raised.

Q1.1 Other confounders that jointly affect the graph size and cycle lengths.

There might be other confounders that jointly affect the graph size and cycle lengths. However, the method by Bevilacqua et al. 2021 cannot fully address the covariate shifts we found. In that paper, they assume that the density of induced k-sized subgraphs is invariant. However, based on our empirical observations, we actually found big cycles that do not appear in small graphs, suggesting that this density invariance does not hold for large cycles. In other words, their model cannot generalize from cycles of small lengths to cycles of large lengths.

Q1.2 To what extent can the three methods resolve the cycle issue? Will the operations affect the expressivity of GNNs?

Explicitly including cycle information can help distinguish more graphs, but will not fundamentally affect the expressiveness of the model. To understand this problem better, in Table 4, we also include two expressive models as our baselines: RPGNN[R2] and SMP[R3]. What we find is that the general expressive model can help size generalization to some extent, but is not as good as explicitly providing this information. The model that excels at cycle-related tasks, e.g. SMP, exhibits better size generalizability than other expressive models, such as RPGNN.

Q1.3 Why do experiments adopt different data splits?

Firstly, it's important to note that we did not utilize identical datasets as those referenced in Bevilacqua et al. 2021. Secondly, the data files we obtained proved to be incompatible with the current versions of PyTorch and CUDA, preventing us from successfully loading the data into our environments. Thirdly, when attempting the data processing using the identical original code provided in Bevilacqua et al. 2021, we encountered errors. Consequently, we were unable to replicate the exact data split presented by Bevilacqua et al. 2021. Despite this deviation, our experimental setup closely aligns with the overarching concept of partitioning datasets into larger and smaller subsets.

Q1.4 Performance on other large-scale datasets

We sincerely thank the reviewer for giving several dataset examples. Initially, we explored several other biological datasets, such as the HIV dataset you mentioned. However, we encountered a significant class imbalance issue (please refer to the dataset section in the general response for details). For instance, in the HIV dataset, the 50% smallest dataset contains 20054 class 0 samples and 510 class 1 samples, whereas its 10% largest dataset contains 3680 class 0 samples and 433 class samples. Other large-scale datasets from ogb and TU exhibit similar trends. Additionally, for the other dataset mentioned in your review, DrugOOD includes various covariate shifts other than graph sizes. For the one concerning size shift (DrugOOD-lbap-core-ic50-size), it adopts a different idea in splitting the data, where it uses the large datasets in the training and validation set and small datasets in the testing. Due to such differences, we did not conduct experiments on it.

Q1.5 Comparison with baselines

We thank you for your great suggestions. We have added more baselines in Table 4. For more details, please refer to the baseline section in the general response and Table 4 in our updated submission. In general, the proposed method SIA still achieves the best performance and is model-agnostic.

Q1.6 Related work in link prediction OOD

Thank you for your great suggestion! We have added this paper to our related work section.

Q1.7 Size generalization in algorithmic tasks

One important view this paper takes is that the size-induced distribution shift depends on the data domain, and that is why contradictory conclusions appear in prior works. Though our main empirical findings apply mainly to biological data, we can adopt a similar spectral analysis to other fields, and identify other patterns that lead to the spectral differences.

Thank you for the new results and discussion! I have increased my rating accordingly. I believe this work could be more impactful if the developed insights and methods could be generalized to realistic datasets.