Dear Reviewer M4v2,

Thank you for recognizing the novelty of the PIC loss, the theoretical guarantees of AdaRC, and the effectiveness of the algorithm demonstrated through experiments on both synthetic and real-world datasets. Your acknowledgment of these contributions is greatly appreciated. Below, we address your questions and concerns:

W1. High-level Intuitions of Math

The paper is not easy to follow, especially for readers without years of experiences in graph neural networks. It would be nice if the authors could provide high level intuitions behind their algorithms, before giving mathematical statements.

Thank you for your suggestion. We agree that providing high-level intuitions alongside mathematical statements can make the paper more accessible. Below, we outline the intuitive explanations behind the key components of our theoretical analysis:

• Attribute shifts and structure shifts have different impact patterns (Proposition 3.3 and 3.4). We visually illustrated this distinction in Figure 2. Attribute shifts cause a translational change in the overall distribution, where nodes from different classes remain separable. In contrast, structure shifts mix the distributions of node representations from different classes, leading to reduced discriminative power.
• Adjusting the hop-aggregation parameter can restore the quality of degraded node representations (Proposition 3.5). We provided two examples (lines 267 - 286) to demonstrate how adjusting the hop-aggregation parameter $\gamma$ can mitigate the degradation in node representation quality caused by structure shifts. To further enhance clarity, we included visualizations for these examples in Appendix A.2, and also this anonymous repo for your convenience. In the visualizations, the first row represents homophily shifts, while the second row represents degree shifts. The first column shows the source graph, the second column shows the target graph before adjusting $\gamma$, and the third column shows the target graph after adjusting $\gamma$. These visualizations show that while homophily shifts and degree shifts degrade representation quality, tuning $\gamma$ effectively alleviates this degradation, improving the separability of node representations.

W2. Assumptions

To my best guess, the proposed method is not data driven. The algorithm relies on several theoretical assumptions in order to extract an invariant node embedding on the shifted graph structure. The major concern is that, such assumptions may not hold in real-world tasks. It is also hard to verify whether the assumptions hold or not for a given task. This greatly limits the practical value of the algorithm.

Thank you for your thoughtful feedback. We would like to address your concern from three perspectives:

• CSBM Framework as a Common Analytical Framework. The CSBM framework is widely used [1,2,3] and captures two key types of shifts we consider: homophily shift and degree shift. It provides an interpretable way to analyze these important challenges.
• AdaRC does not depend on CSBM Assumptions. Our algorithm does not rely on CSBM. We use it solely for theoretical analysis to explain why attribute and structure shifts impact GNNs differently and why adjusting $\gamma$ can restore representation qualities. This does not restrict AdaRC to CSBM scenarios. In practice, AdaRC only requires the graph to exhibit structure shifts, which are common and can often be identified through task knowledge or a validation set.
• Verification on Real-World Datasets. We have also tested our algorithm on various real-world datasets in Table 2 and observed that AdaRC consistently demonstrates its effectiveness, supporting the general applicability of our approach.

[1] Yao Ma, Xiaorui Liu, Neil Shah, Jiliang Tang: Is Homophily a Necessity for Graph Neural Networks? ICLR 2022

[2] Haitao Mao, Zhikai Chen, Wei Jin, Haoyu Han, Yao Ma, Tong Zhao, Neil Shah, Jiliang Tang: Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All? NeurIPS 2023

[3] Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, Danai Koutra: Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks. ICDM 2022

Dear Reviewer KHiD,

We sincerely thank you for your thoughtful review and for recognizing the strengths of our work, including the introduction of the PIC loss for improving node representation quality, and the extensibility of AdaRC as a plug-and-play framework. Below, we address your concerns and suggestions:

W1. Comparison with Existing Graph TTA and DA Methods

The authors mention that traditional TTA methods rely on the quality of node representations, but there are also existing works in graph TTA and DA that similarly address the impact of structure shifts. It is recommended to further discuss the differences and advantages of AdaRC in comparison to these methods, particularly in handling heterophilic graphs or complex structure shifts.

Thank you for raising this important point. We have provided a general discussion of graph domain adaptation (GDA) and graph test-time adaptation (GTTA) methods in the related work section. We are happy to elaborate further and clarify how AdaRC differs from and improves upon these methods:

Graph domain adaptation (GDA) aims to transfer knowledge from a labeled source graph to an unlabeled target graph with access to both graphs. Most of the GDA algorithms focus on learning invariant representations over the source and target graphs by adversarial learning or minimizing the distance between source and target. For example, SRGNN [1] minimizes the central moment discrepancy of node representations, and DANE [2] aligns the distribution via adversarial learning. However, these methods do not explicitly differentiate between attribute shifts and structure shifts, treating them as a single issue to be solved through invariant representation learning. Recently, StruRW [3] addresses structure shifts explicitly by reweighting edge weights in the source graph to align with the target graph. While these approaches offer useful insights, they rely heavily on access to both source and target graphs simultaneously, making them inapplicable to TTA scenarios where only the target graph is available during adaptation.

Graph test-time adaptation (GTTA) aims to adapt a pre-trained GNN to an unlabeled target graph, without re-accessing the source domain during adaptation. Recent works such as GTrans, SOGA, and GraphPatcher take varied approaches to this problem. GTrans [4] modifies the target graph’s features and adjacency matrix during testing by minimizing a contrastive loss. While flexible and data-centric, it suffers from high computational complexity and a large parameter space. SOGA [5] maximizes mutual information between inputs and outputs and enforces consistency between neighboring or structurally similar nodes. However, SOGA is designed for homophilic graphs and thus performs relatively poorly on heterophilic graphs. GraphPatcher [6] focuses primarily on degree shifts, generating virtual nodes to improve predictions on low-degree nodes. In comparison, AdaRC is designed to handle a broad range of structure shifts, including homophily and degree shifts. Additionally, AdaRC achieves this with better computational efficiency, making it a practical and effective solution for TTA scenarios.

[1] Qi Zhu, Natalia Ponomareva, Jiawei Han, Bryan Perozzi: Shift-Robust GNNs: Overcoming the Limitations of Localized Graph Training data. NeurIPS 2021

[2] Yizhou Zhang, Guojie Song, Lun Du, Shuwen Yang, Yilun Jin: DANE: Domain Adaptive Network Embedding. IJCAI 2019

[3] Shikun Liu, Tianchun Li, Yongbin Feng, Nhan Tran, Han Zhao, Qiang Qiu, Pan Li: Structural Re-weighting Improves Graph Domain Adaptation. ICML 2023

[4] Wei Jin, Tong Zhao, Jiayuan Ding, Yozen Liu, Jiliang Tang, Neil Shah: Empowering Graph Representation Learning with Test-Time Graph Transformation. ICLR 2023

[5] Haitao Mao, Lun Du, Yujia Zheng, Qiang Fu, Zelin Li, Xu Chen, Shi Han, Dongmei Zhang: Source Free Graph Unsupervised Domain Adaptation. WSDM 2024

[6] Mingxuan Ju, Tong Zhao, Wenhao Yu, Neil Shah, Yanfang Ye: GraphPatcher: Mitigating Degree Bias for Graph Neural Networks via Test-time Augmentation. NeurIPS 2023

Dear Reviewer KHid,

Thank you for your insightful questions and for taking the time to review our work and rebuttal in detail. Below, we provide detailed responses to your questions.

Q1. Homophilic and Heterophilic Graphs

As mentioned in the rebuttal, SOGA is designed for homophilic graphs and thus performs relatively poorly on heterophilic graphs. So, how about the proposed SOGA on the homophilic graphs and heterophilic graphs?

We understand your question as asking how our proposed AdaRC performs on homophilic and heterophilic graphs.

Our AdaRC algorithm does not rely on any homophily assumption. Instead, it dynamically adapts the hop-aggregation parameter to make node representations more discriminative. This adaptability ensures that AdaRC can handle both homophilic and heterophilic graphs effectively, as long as the chosen GNN backbone has sufficient expressiveness to model these graph types. For instance, when using a single-layer GCN as the backbone, AdaRC learns a positive $\gamma$ for homophilic graphs and a negative $\gamma$ for heterophilic graphs, aligning the aggregation process with the underlying graph structure.

As shown in Table 1 of our experiments, we evaluated AdaRC with both homophilic target graphs (hetero $\to$ homo) and heterophilic target graphs (homo $\to$ hetero). AdaRC demonstrates strong performance in both cases. In contrast, SOGA, being designed specifically for homophilic graphs, shows significantly weaker performance on heterophilic target graphs compared to homophilic ones.

Q2. Mechanisms of How Structure Shifts Affect GNN Performance

The Mechanisms of How Structure Shifts Affect GNN Performance should be explained.

Thank you for your question. We understand that your inquiry follows up on W3 and seeks a standalone explanation of how homophily shift and degree shift individually lead to a decline in GNN performance. We are happy to provide a more intuitive explanation.

Theoretical analysis. Using the theoretical analysis of a single-layer GCN on a CSBM graph from our paper as an example, for a positive-class sample, its representation distribution can be expressed as:

$$\boldsymbol{z}\_i \sim \mathcal{N} \left( (1 + \gamma h\_i) \boldsymbol{\mu}\_+ + \gamma (1 - h\_i) \boldsymbol{\mu}\_-, \left( 1 + \frac{\gamma^2}{d\_i} \right) \boldsymbol{I} \right)$$

• Homophily shift: Changes in $h_i$ (node homophily) affect the mean of $\boldsymbol{z}_i$​, while the variance remains constant. This reduces the inter-class distance as the centroids of the two classes move closer together, but the intra-class variance does not change. Consequently, the representations of different classes overlap more, leading to decreased accuracy.
• Degree shift: Changes in $d_i$ (node degree) alter the variance of $\boldsymbol{z}_i$, without affecting the mean. This increases intra-class variance while keeping inter-class distance unchanged. Similarly, this increased overlap between class representations reduces the ability to distinguish between classes and degrades accuracy.

Both shifts lead to overlapping representations between different classes, which negatively impacts classification performance.

Visualization. To further illustrate, we provide two visualization examples in Appendix A.2 (also available in this anonymous repo for your convenience):

• Under homophily shift, the variance of the two class distributions remains constant, but the centroids of the two classes move closer together.
• Under degree shift, the centroids remain unchanged, but the intra-class variance increases.

Both scenarios clearly demonstrate how structure shifts result in greater overlap between class representations, ultimately reducing accuracy.

We hope this explanation provides a clear understanding of the mechanisms. Please let us know if further clarification or additional details are needed.

Dear Reviewer qcfU,

We sincerely thank you for your thoughtful review and for recognizing the strengths of our work, including AdaRC's novel approach to addressing structure shifts, its compatibility with existing TTA methods, the clarity of our theoretical insights, and the comprehensiveness of our experimental evaluations. Below, we address the concerns and questions raised in your review:

W1 & Q2. Scalability

W1. While the PIC loss offers advantages, its application may face scalability challenges with very large graphs due to the computational overhead introduced by clustering operations. The method's efficiency under extreme graph sizes could be explored further.

Q2. How does the computational efficiency of AdaRC scale when applied to graphs with millions of nodes?

Thank you for raising this important point. We would like to clarify that AdaRC does not perform additional clustering operations. Instead, it leverages the pseudo-labels from the BaseTTA method as the clustering results. This design ensures that the computational overhead of calculating the PIC loss is linear with respect to the number of nodes in the graph.

To further validate this, we have conducted experiments on graphs of varying sizes from 1 million to 10 million nodes. The result in given in Figure 12 of Appendix C.8, and also in this anonymous repo for your convenience. The results confirm that the computational time for AdaRC indeed scales linearly with graph size, demonstrating its efficiency even for large graphs.

W2 & Q4. Automated Tuning of Hop-Aggregation Parameters

W2. AdaRC's performance relies on the optimization of hop-aggregation parameters, which may not generalize across all GNN architectures without tuning. This reliance might limit its applicability for varied and complex GNN models.

Q4. Does the framework support automated tuning of hop-aggregation parameters across different GNN architectures, or would manual tuning be required for optimal results?

For the GNNs discussed in the paper (GPRGNN, APPNP, GCNII, JKNet), AdaRC supports automated tuning of hop-aggregation parameters by minimizing the PIC loss, without requiring any manual tuning. Specifically, while the original implementations of these frameworks may treat hop-aggregation parameters as hyperparameters (e.g., the teleport probability $\alpha$ in APPNP), we simply treat these parameters as trainable parameters. This allows us to optimize them automatically through gradient descent to minimize the PIC loss, effectively enabling automated adjustment of hop-aggregation parameters.

W3 & Q1. Performance on Evolving Graphs

W3. AdaRC has been evaluated on static graphs with controlled shifts. Its applicability to dynamic graphs, where structure shifts occur over time, is not explored, which could be crucial for certain real-time applications.

Q1. Can AdaRC be adapted to handle continuously evolving graphs where node connectivity changes over time?

While our experiments in the paper mainly focused on adapting to a single graph with a stable distribution, we also evaluated AdaRC’s performance on a stream of graphs with evolving structure shifts. Specifically, we used the Syn-Cora dataset, where the model was pre-trained on a source graph with a homophily of 0.8. It was then sequentially adapted to five target graphs with homophilies of 0.1, 0.7, 0.3, 0.9, and 0.2, simulating continuously changing homophily. The experimental setup, except for the sequence of target graphs, was identical to that in the Syn-Cora experiments described in the main text.

For example, in the column corresponding to the target graph with a homophily of 0.3, we compared two scenarios: (1) static: directly adapting from 0.8 → 0.3, and (2) evolving: sequentially adapting through 0.8 → 0.1 → 0.7 → 0.3.

Table A. Accuracy of AdaRC on static target graph and evolving target graph (mean ± s.d.)

The results, shown in Table A above, indicate that AdaRC achieves performance on evolving graphs highly comparable to that on static graphs. This demonstrates AdaRC’s ability to handle dynamic scenarios effectively, even under continuously changing graph structures.

Dear Reviewer eWx1,

We sincerely thank you for your thoughtful review and for highlighting the strengths of our work, including the effectiveness of the proposed PIC loss and its seamless integration with existing frameworks, as well as the comprehensive analysis of attribute and structure shifts using CSBM. Below, we address your concerns and questions:

W1. Performance on Real-World Graphs

The performance improvements on the Twitch-E and OGB-Arxiv datasets appear marginal. Could the authors provide further analysis to clarify the reasons behind these limited gains?

The relatively lower performance on Twitch-E and OGB-Arxiv datasets is due to the higher uncertainty and more complex distribution shifts present in these datasets, which make the classification task harder. This observation is consistent with results in related works [1]. We also experimented with using cross-entropy loss instead of PIC loss. Even when the model was aware of 1% of the testing labels, the accuracy achieved was only 58.21% on Twitch and 42.12% on Arxiv. In comparison, our PIC loss achieved 56.76% and 41.74% accuracy, respectively, without requiring any testing labels.

[1] Wei Jin, Tong Zhao, Jiayuan Ding, Yozen Liu, Jiliang Tang, Neil Shah: Empowering Graph Representation Learning with Test-Time Graph Transformation. ICLR 2023

W2. Gains Achieved Vary

The gains achieved seem to vary significantly across different methods and backbone models. For instance, the Tent method demonstrates the highest improvements. Could the authors offer insights into why this variation occurs?

Thank you for your observation. The variation in gains across different TTA methods primarily arises from the distinct designs of these algorithms, which make them suitable for different types of attribute shifts. For example, Tent adjusts the parameters of the batch normalization layer, making it particularly effective for handling attribute shifts that resemble large translational changes. On the other hand, T3A updates class prototypes using testing data, which may be more effective for complex shift patterns with smaller magnitudes. We believe that selecting the most appropriate TTA algorithm based on the specific nature of the attribute shift is an interesting direction for future research.

Dear Reviewer jAsf,

We sincerely thank you for your thoughtful review and for recognizing the strengths of our work, including the identification of structure shifts as an overlooked problem, the simplicity and effectiveness of the AdaRC framework, and the detailed theoretical analysis provided. Below, we address the concerns and questions raised in your review:

W1. Simplified Model for Theoretical Analysis

The theoretical analysis focuses on single-layer GCNs and CSBM-generated graphs, which represent a simplified model where structure shifts are easily identified. However, the evolving real-world graph structures are far more complex. It is unclear whether the findings on this simplified model still hold for real-world graphs, particularly in domains where the task accuracy is not high.

We acknowledge that our theoretical analysis primarily focuses on single-layer GCNs and CSBM-generated graphs. This choice was intentional to provide a rigorous and interpretable foundation for understanding the impact of common structure shifts, including degree and homophily shifts.

We agree that real-world graphs exhibit structure shifts beyond homophily and degree, such as clustering coefficients, which can also impact the performance of multi-layer GNNs. To address this, we have further extended our analysis to $K$-hop GCNs, which aggregate information from nodes' own features as well as their 1-hop to $K$-hop neighbors. Detailed theoretical analysis is provided in Appendix A.7, and also this anonymous repo for your convenience. All our propositions naturally generalize to $K$-hop GCNs, capturing more complex structure shifts. Additionally, our analysis does not rely on assumptions about task accuracy, making it broadly applicable.

W2. Verification of Structure Shifts in Real-World Graphs

The experimental results, which show promising performance, are primarily based on synthetic datasets or real-world datasets with synthetic structure shifts. The verification that the structure shifts existence in the real-world graphs should be included.

Thank you for your suggestion. We agree that verifying the presence of structure shifts in real-world graphs is important and beneficial. Previous studies [1,2] have analyzed common real-world graphs and reported graph metrics such as homophily, degree, demonstrating the prevalence of structure shifts. Additionally, in our work, we have included the metrics for the datasets we used (see Appendix D.1) to provide further insights.

If there is a specific graph dataset that you are particularly interested in, we would be happy to calculate and provide the relevant graph metrics to verify the presence of structure shifts.

[1] Eli Chien, Jianhao Peng, Pan Li, Olgica Milenkovic: Adaptive Universal Generalized PageRank Graph Neural Network. ICLR 2021

[2] Shikun Liu, Tianchun Li, Yongbin Feng, Nhan Tran, Han Zhao, Qiang Qiu, Pan Li: Structural Re-weighting Improves Graph Domain Adaptation. ICML 2023

W3. Experiment Setup Details

The experimental setup for real-world datasets lacks transparency. The paper mentions injecting structure shifts by deleting a subset of homophilic edges. However, it did not specify the quantity of this deletion and the selection criteria.

Thank you for your comment. Due to page limits, detailed experimental setup is provided in Appendix D.1, including the number of edges left. Specifically, the selection of homophilic edges for deletion is performed using random sampling without replacement.

W4. GNN Backbones

The paper presents full results for only one GNN backbone. Presenting results for different GNN backbones, especially fundamental ones, would provide a more comprehensive understanding of AdaRC's effectiveness and applicability across various architectures.

Thank you for your valuable suggestion. We agree that full experiments with other GNN architectures can provide more comprehensive understandings. Following your advice, we have conducted full experiments with different GNN backbones on Syn-Cora. We include all BaseTTAs used in our paper, and their combination with AdaRC. The results are updated in Appendix C.9. The results show that, although different GNN architectures yield varying levels of performance on the target graph, AdaRC consistently enhances accuracy across all cases. This demonstrates that AdaRC is compatible with a wide range of GNN architectures, highlighting its broad applicability and effectiveness.

3. Performance on Evolving Graphs (qcfU, M4v2)

While our experiments in the paper mainly focused on adapting to a single graph with a stable distribution, we also evaluated AdaRC’s performance on a stream of graphs with evolving structure shifts. Specifically, we used the Syn-Cora dataset, where the model was pre-trained on a source graph with a homophily of 0.8. It was then sequentially adapted to five target graphs with homophilies of 0.1, 0.7, 0.3, 0.9, and 0.2, simulating continuously changing homophily. The experimental setup, except for the sequence of target graphs, was identical to that in the Syn-Cora experiments described in the main text.

For example, in the column corresponding to the target graph with a homophily of 0.3, we compared two scenarios: (1) static: directly adapting from 0.8 → 0.3, and (2) evolving: sequentially adapting through 0.8 → 0.1 → 0.7 → 0.3.

Table A. Accuracy of AdaRC on static target graph and evolving target graph (mean ± s.d.)

The results, shown in Table A above, indicate that AdaRC achieves performance on evolving graphs highly comparable to that on static graphs. This demonstrates AdaRC’s ability to handle dynamic scenarios effectively, even under continuously changing graph structures.