We sincerely appreciate your careful review and insightful feedback. Below we provide point-by-point responses to address all raised concerns.

Performance when there is no shift during testing

Thank you for your insightful suggestions!

We compare TAR with several typical robust optimization methods, and the results are presented in the table below. Our key observations are as follows:

• On the CBAS and Twitch datasets, TAR consistently outperforms baselines in both IID (no shift) and OOD (covariate shift) settings. Notably, the performance improvements under OOD are significantly more pronounced than those under IID.
• Some methods, such as VREx, while achieving notable gains on CBAS and Twitch under the OOD setting, exhibit substantial performance degradation in the IID setting.
• On the Cora dataset, TAR shows a slight, statistically insignificant drop in performance under IID. However, it achieves the best performance under the OOD setting, surpassing all other methods.

These results highlight TAR's robustness and effectiveness across different scenarios.

Performance of different graph sparsity levels

Thank you for your question! As shown in the table below, the five benchmark datasets we employed exhibit diverse degree distributions, with average node degrees ranging from 1.52 to 26.15. Our method demonstrates consistently strong performance across all these varying degree distributions as you can see in Tables 1 and 2 in our paper.

Performance on heterophilic graphs

Thank you for your insightful question! As shown in the table above, our evaluation covers datasets with varying levels of homophily. Notably, WebKB represents a standard heterophilic graph benchmark. We additionally contruct an another OOD dataset chameleon, following the same priciple of GOOD benchmark [1] and using node degree as split type. As demonstrated in the results table below, TAR consistently achieves top performance on both heterophilic graphs, further validating its robustness across different homophily regimes.

Performance on contrastive loss

Thank you for your insightful question! TAR can be applied to different loss type. We apply TAR to two graph contrastive learning methods——GRACE [2] and COSTA [3]——to verify its effectiveness on contrastive loss. Specifically, we apply TAR in the pretrain stage and keep the finetune stage the same as the raw contrastive learning method. As shown in the table below, TAR consistenly improves the performance of different graph contrastive learning under distribution shifts.

[1] S. Gui, et al., Good: Agraph out-of-distribution benchmark. Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track.

[2] Y. Zhu, et al. Deep Graph Contrastive Representation Learning. ICML Workshop on Graph Representation Learning and Beyond, 2020.

[3] Y. Zhang, et al. Costa: Covariance-preserving feature augmentation for graph contrastive learning. SIGKDD 2022.

Training Cost Analysis

We compared the time cost (epoch/s) of our method with other methods, as shown in the table below. It can be observed that our method, similar to Group DRO and KLDRO, introduces only little overhead, demonstrating excellent scalability. For a comprehensive complexity analysis, please see Appendix F of our paper.

Should you have any additional concerns, please do not hesitate to let us know.

We sincerely appreciate your careful review and insightful feedback. Below we provide point-by-point responses to address all raised concerns.

Analysis of Graph Extrapolation

1.Interaction between GE and Reweighting

Graph Extrapolation (GE) is a crucial component of TAR. Without GE, TAR reweighting can only simulate potential worst-case distributions by adjusting sample weights of existing data, which is limited by the coverage of current graph. In contrast, GE expands the potential distribution by transforming the graph. Specifically, while OOD samples may not appear during training, GE may construct such samples, allowing TAR reweighting to assign them higher weights and simulate potential distribution shifts.

2.Comparison with Mixup

We use both Drop Edge and Mask Feature as GE since they transform the graph's topology and node features, respectively. These techniques are also utilized in other graph OOD methods like FLOOD. For comparison, we replace GE with Mixup, which only interpolates node features. The results show that GE consistently outperforms Mixup.

Performance when there is no shift during testing

Thank you for your suggestion! Below are the comparative results and key observations:

• On CBAS and Twitch datasets, TAR consistently outperforms baselines in both IID (no shift) and OOD (covariate shift) settings, with significantly larger gains under covariate shift.
• On Cora dataset, TAR shows a slight, statistically insignificant drop in IID performance but achieves the best results under OOD, surpassing other methods.

Sensitivity analysis of other parameters

Thank you for your insightful suggestion! We want to clrify that "the coefficient of the topology penalty" is not a hyperparameter, we set it to $\frac{1}{2\tau}$ in our optimization (page 3, line 163), and $\tau$ is exactly the TAR inner learning rate (page 4, equation 5). Due to space constraints, additional analysis figures for other parameters are provided in this anonymous link. Please refer to it for more details.

Training Cost Analysis

Compared to empirical risk minimization (ERM), TAR introduces minimal overhead. Our paper (Appendix F) includes complexity analysis, and we provide additional details here.

For an $l$-layer, $d$-dimensional GCN on a graph with $n$ nodes and $m$ edges, the time cost of TAR includes:

• Outer Training: $O(ld^2n + lm)$, which encompasses feature transformation and neighbor aggregation.
• Inner Loop: The $k$ iterations have a time complexity of $O(kn + km)$.

Real-world graphs are typically sparse, with small node degrees and larger GNN dimensions (e.g., $d=300$, max average degree $m/n=26$ in Twitch). Thus, $ld^2n \gg lm$, and since $k \ll ld^2$, TAR's additional computation is negligible. Besides, the inner loop operates in a message-passing style and is parameter-free, ensuring scalability for large-scale graphs.

The table below compares TAR's runtime (epoch/s) with other methods, showing it introduces slight overhead over ERM, demonstrating excellent scalability.

Q: Why does this paper additionally consider concept shift?

We would like to clarify that we follow the terminology used in GOOD benchmark, where distribution shifts are categorized into concept shift and covariate shift, with datasets specifically constructed for these cases. Our experiments strictly follow this benchmark setting, and results show that our method effectively enhances performance across both types of shifts.

Thank you for your question, and we will incorporate this into our final version to avoid any misunderstandings.

Q: The bi-level optimization of min and max may lead to high training costs and instability.

For TAR's training cost, we refer the reviewer to the "Training Cost Analysis" above. Regarding instability concerns, we provide additional loss visualizations at this link. These results demonstrate that TAR achieves a smaller generalization loss without significant training instability.

Should you have any additional concerns, please do not hesitate to let us know.

Thank you for the insights in the evaluation and the hints for revising manuscripts.

Graph extrapolation could have been mentioned earlier in the paper.

Thank you for your suggestion. We will add a summary in the methodology section to introduce GE earlier.

Once again, thank you for your careful review. We will thoroughly check our manuscript to avoid any grammar or spelling errors!