Map to Optimal: Adapting Graph Out-of-Distribution in Test Time

Dear reviewer 32n6,

We appreciate your comments and your support for our work. We hope our response can address your concerns. Please find our detailed response below.

(Weakness 1 & Question 1) Extended Tasks of our method

We are happy to do more research in the future to improve our method so that it can be used in graph classification or edge prediction. It should be noted that the test-time environment with OOD issue for graph classification may be different from that in node classification, because the distribution shift of graph classification may be more based on the graph level rather than the node level. Therefore, when generating augmented views, it may be necessary to consider whether to use a single test graph as an augmentation anchor or a batch of OOD graphs as the augmentation anchor. This will be a very interesting topic and future research direction.

Moreover, our method can be extended to OOD detection, as we showed in Section 4.2, after tuning the adaptor with our unsupervised loss $L_{\text{A2A}}$, the representation generated from our LROG module can be used as an indicator of the OOD degree of this test graph. After some special designs, it can also be used in knowledge graph completion to help entities have a better embedding, for unsupervised graph anomaly detection, community detection, etc.

(Weakness 2 & Question 2) More theoretical analysis and insights As shown in Fig 2, a toy example, and Appendix B, our theoretical analysis demonstrates that adding input-level bias to graph node features can lead to better predictions within the decision boundary of pre-trained GNNs after feature aggregation and projection.

The key insight of our approach lies in how we conceptualize and address the distribution shift problem in test-time graph adaptation. Our method can be viewed as adaptively adjusting the decision boundary of pre-trained GNNs according to test graph distributions. The design of our symmetric loss function with the L2 norm shares a profound connection with minimizing model variance in the test environment. However, as demonstrated in our ablation studies, optimizing this loss alone is insufficient for effective adaptation.

The fundamental reason behind this observation is that the additional parameters introduced during training, which act as input-level bias, must maintain structural alignment with the GNN's feature extraction process. This motivation led to our design of the consistency loss, which is theoretically grounded in the mathematical concept of isomorphisms. As demonstrated in our two-view optimization formulation in Appendix A, while our relaxed optimization objective could potentially be replaced by alternative loss functions, two critical assumptions must hold:

1. The environment generating the graphs must be treated as a random variable
2. There exist one or multiple optimal graphs that enable the pre-trained GNN to achieve superior performance

This theoretical framework provides a principled approach to adaptation while maintaining the structural information learned during pre-training. The interplay between symmetric and consistency losses ensures that the adaptation process respects both the global distribution alignment and local structural preservation.

Thank you again for your comment. We hope our explanation can dispel your concerns. If you have any other questions or concerns, please feel free to let us know.

Dear reviewer bxGo,

We appreciate your comments and your support for our work. We hope our response can address your concerns. Please find our detailed response below.

(Weakness 1) Our contribution & More details of implementation.

Limitations of previous methods

• GTrans and the other methods with the direct modification on the graph’s edge require a hyperparameter to control the edge adjustment ratio, as considering all possible edge combinations would result in a combinatorial explosion due to the discrete search space over $N^{[0,1]}$ for each edge.
• Previous test-time methods (GraphCTA, GraphTTA, and GTrans) rely on conventional contrastive losses in their self-supervised learning framework, which necessitates careful selection or design of positive and negative samples. For instance, GTrans specifically designs different data augmentation methods for node classification tasks to sample positive-negative pairs, where positive samples are generated through DropEdge while negative samples are obtained via Node Shuffling with specific augmentation parameters. Although this approach effectively captures discriminative features in the embeddings, it places excessive emphasis on embedding differences while neglecting the crucial consistency (invariance) property of the conditional distribution that underlies out-of-distribution shifts.
• Although some train-time methods (EERM[1], MoleOOD[2]) utilize invariance learning by maximizing data variance in existing graph generation environments while minimizing their supervised losses, these methods require supervised training and consume substantial computational resources. These training-time approaches result in significant overhead in terms of both GPU memory consumption and training time.

In contrast to these limitations, our work presents specific contributions that address each of these challenges one by one, as detailed in our key contributions:

Contribution

• We achieve parameter efficiency through a low-rank adapter design. Unlike methods that modify graph edges directly, our approach avoids combinatorial explosion by using a low-rank adapter structure. With our proposed adapter, we can efficiently compute global attention on large-scale graphs, enabling fast test-time tuning without the need for edge-ratio hyperparameters. The additional parameters learned by our adapter are directly applied as an input-level bias to the node features, offering an efficient mechanism for representation adaptation.
• We propose a novel consistency-aware framework that goes beyond conventional contrastive learning. Our mathematical framework comprises Consistency Loss $\mathcal{L}_{\text{con.}}$, Regularization Loss $\mathcal{L}_{\text{R}}$, Symmetry Loss $\mathcal{L}_{\text{symm.}}$, and unified Augmentation-to-Augmentation Loss $\mathcal{L}_{\text{A2A}}$. This design explicitly addresses the consistency (invariance) property of conditional distributions in OOD settings, which was overlooked by previous test-time methods.
• We introduce GOAT, an efficient test-time tuning paradigm that achieves consistent learning without the computational overhead of training-time methods. Our framework integrates a self-supervised loss mechanism with a low-rank adapter, enabling unlabeled test graphs to adapt to distribution shifts with minimal computational resources effectively. The method is theoretically grounded in a relaxed optimization objective, where learning across augmented views guides the additional parameters to optimize the fixed pre-trained parameters' performance on the shifted distribution.

(Weakness 2) Problem Formulation & Why not Domain Adaptation.

We want to clarify that while domain adaptation can be viewed as a specific case of OOD problems, our work addresses a broader scope. In OOD scenarios, we may deal with data from the same domain, such as cases in OGB-ArXiv and Cora, but with different training and testing distributions, which is precisely our case.

We aim to present a unified framework for handling various distribution shifts in test-time graph adaptation. In our setting, each test graph is processed individually at test time using a pre-trained GNN model, where the test graphs are generated from different environments, leading to OOD challenges.

Importantly, we only have access to the graph data without corresponding labels during the adaptation process. Our experimental validation encompasses three real-world scenarios: artificial transformations, domain adaptation, and temporal evolution. Additionally, we provide comprehensive comparisons between our method and existing domain adaptation approaches in Table 7 & Table 8.

(Please check the following comment for more responses)

Dear reviewer 2CzR,

We appreciate your comments and your support for our work. In the following response, we have carefully addressed each point raised and hope to resolve any uncertainties.

(Weakness 1) Our Contribution & Contrast to Previous Methods.

Limitations of previous methods

• GTrans and the other methods with the direct modification on the graph’s edge require a hyperparameter to control the edge adjustment ratio, as considering all possible edge combinations would result in a combinatorial explosion due to the discrete search space over [0,1] for each edge.

• Previous test-time methods (GraphCTA, GraphTTA, and GTrans) rely on conventional contrastive losses in their self-supervised learning framework, which necessitates careful selection or design of positive and negative samples. For instance, GTrans specifically designs different data augmentation methods for node classification tasks to sample positive-negative pairs, where positive samples are generated through DropEdge while negative samples are obtained via Node Shuffling with specific augmentation parameters. Although this approach effectively captures discriminative features in the embeddings, it places excessive emphasis on embedding differences while neglecting the crucial consistency (invariance) property of the conditional distribution that underlies out-of-distribution shifts.

• Although some train-time methods (EERM[1], MoleOOD[2]) utilize invariance learning by maximizing data variance in existing graph generation environments while minimizing their supervised losses, these methods require supervised training and consume substantial computational resources. These training-time approaches result in significant overhead in terms of both GPU memory consumption and training time.

In contrast to these limitations, our work presents specific contributions that address each of these challenges one by one, as detailed in our key contributions:

Contribution

• We achieve parameter efficiency through a low-rank adapter design. Unlike methods that modify graph edges directly, our approach avoids combinatorial explosion by using a low-rank adapter structure. With our proposed adapter, we can efficiently compute global attention on large-scale graphs, enabling fast test-time tuning without the need for edge-ratio hyperparameters. The additional parameters learned by our adapter are directly applied as an input-level bias to the node features, offering an efficient mechanism for representation adaptation.
• We propose a novel consistency-aware framework that goes beyond conventional contrastive learning. Our mathematical framework comprises Consistency Loss $\mathcal{L}_{\text{con.}}$, Regularization Loss $\mathcal{L}_{\text{R}}$, Symmetry Loss $\mathcal{L}_{\text{symm.}}$, and unified Augmentation-to-Augmentation Loss $\mathcal{L}_{\text{A2A}}$. This design explicitly addresses the consistency (invariance) property of conditional distributions in OOD settings, which was overlooked by previous test-time methods.
• We introduce GOAT, an efficient test-time tuning paradigm that achieves consistent learning without the computational overhead of training-time methods. Our framework integrates a self-supervised loss mechanism with a low-rank adapter, enabling unlabeled test graphs to effectively adapt to distribution shifts with minimal computational resources. The method is theoretically grounded in a relaxed optimization objective, where learning across augmented views guides the additional parameters to optimize the fixed pre-trained parameters' performance on the shifted distribution.

(Weakness 3) More explanation of the environment in Assumption 1

In our assumption, the “Environment” $\mathrm{e}$ (as formally defined by Wu et al. [1] and Yang et al.[2] ) is treated as a random variable, which means it can be learned through back-propagation. The changes in the environment cause OOD phenomena in test graphs. This is why we aim to represent the 'Environment' to address graph OOD issues at test time. The visualization of our learned environment can be seen in Fig 5(c) and Fig 9.

(Weakness 4) Significance of our experiment.

Our experimental results in Table 2. demonstrate strong statistical significance and substantial performance improvements. Specifically, out of 24 experimental settings, our method achieves statistically significant improvements (validated by t-tests) in 19 cases, showing overwhelming advantages over the ERM baseline. Moreover, when compared with GTrans, the current state-of-the-art approach, our method achieves comparable or superior performance in 14 different settings. The magnitude of improvement is particularly noteworthy - our method outperforms GTrans by a considerable margin, achieving scores of 67.92 vs. 63.04(Elliptic) and 54.20 vs. 51.27(FB100) in the most significant cases.

(Please check the following comment for more responses)

(Question 1) $\hat{\mathcal{G}}_{te}$ in Eq.2

As we show on line 161, $\hat{\mathcal{G}}_{te}$ is the graph sampled from the test time environment with DropEdge, FlipEdge, subgraph sampling, or other augmentation methods.

(Question 2) “modifies the graph structure within the learned parameter space of a pre-trained GNN model $f_{\theta^*}$” in Proposition 1

In Proposition 1, $g_\psi$ is designed to operate beyond individual graph instances - it works with samples observed and collected from the environment generating the test graph. When we refer to “modifying the graph structure within the learned parameter space of $f_{\theta^*}$”, we are specifically highlighting how this function influences the GNN's learning process: it enables more accurate aggregation paths and information flow during node feature embedded by $f_{\theta^*}$. Notably, in our approach, rather than directly modifying the graph structure, we add learned bias (generated by our low-rank adapter) to node features. Through the GNN's message-passing mechanism, these biased node features effectively guide the structural information flow toward more accurate directions, achieving implicit graph structure modification.

(Question 3) Why does the module LROG catch both the change in graph structure and feature distribution shift?

It is because the input of the LORG module maintains information on the graph edge changes as the embedding of the node feature is actually aggregated by the pre-trained GNN network.

Our LROG module implements a cross-attention mechanism where:

1. Query (Q) is derived from raw input node features
2. Key (K) and Value (V) are obtained from node embeddings that have undergone GNN's aggregation and non-linear transformation, thus inherently encoding edge information through message passing

This design, coupled with our optimization objectives, allows us to simultaneously monitor and align both node and edge-level characteristics between the test graph and the pre-trained GNN's encoded knowledge, capturing both their discrepancies and consistencies.

(Question 4) $g_\psi(f\mathcal(G))\approx f(g_\psi\mathcal(G))$

We respectfully highlight that we defined the combination of the $g$ and $f$ in footnote 4 line 322:

(Question 5) Fair Comparison

Thank you for your careful observation of the ranking comparison. We acknowledge that the absolute performance differences in some cases are small. However, we would like to clarify that:

1. The average ranking is computed by first ranking methods within each dataset independently, then averaging these ranks across datasets. This approach helps normalize the varying scales of performance across different datasets.
2. More importantly, our method shows consistent improvements across diverse scenarios - from artificial transformations to temporal evolution, and across different backbones. The consistency of improvement, rather than just the magnitude, demonstrates the robustness of our approach.
3. Furthermore, on challenging datasets like Elliptic and OGB-ArXiv where distribution shifts are more severe, our method shows more substantial improvements (e.g., 67.92 vs 63.04 on Elliptic with SAGE backbone, 54.20 vs. 51.27 on FB100 with GAT backbone). It can be said that our method achieves comparable or superior performance to GTrans.

We hope our explanation can dispel your concerns. If you have any other questions or concerns, please feel free to let us know.

Dear reviewer nBtR,

We appreciate your comments and your support for our work. We hope our response can address your concerns. Please find our detailed response below.

Weakness：

(Weakness 1 & 2) Main Contribution & Differences with GTrans

Limitations of previous methods

• GTrans and the other methods with the direct modification on the graph’s edge require a hyperparameter to control the edge adjustment ratio, as considering all possible edge combinations would result in a combinatorial explosion due to the discrete search space over $N^{[0,1]}$ for each edge.
• Previous test-time methods (GraphCTA, GraphTTA, and GTrans) rely on conventional contrastive losses in their self-supervised learning framework, which necessitates careful selection or design of positive and negative samples. For instance, GTrans specifically designs different data augmentation methods for node classification tasks to sample positive-negative pairs, where positive samples are generated through DropEdge while negative samples are obtained via Node Shuffling with specific augmentation parameters. Although this approach effectively captures discriminative features in the embeddings, it places excessive emphasis on embedding differences while neglecting the crucial consistency (invariance) property of the conditional distribution that underlies out-of-distribution shifts.
• Although some train-time methods (EERM[1], MoleOOD[2]) utilize invariance learning by maximizing data variance in existing graph generation environments while minimizing their supervised losses, these methods require supervised training and consume substantial computational resources. These training-time approaches result in significant overhead in terms of both GPU memory consumption and training time.

In contrast to these limitations, our work presents specific contributions that address each of these challenges one by one, as detailed in our key contributions:

Contribution

• We achieve parameter efficiency through a low-rank adapter design. Unlike methods that modify graph edges directly, our approach avoids combinatorial explosion by using a low-rank adapter structure. With our proposed adapter, we can efficiently compute global attention on large-scale graphs, enabling fast test-time tuning without the need for edge-ratio hyperparameters. The additional parameters learned by our adapter are directly applied as an input-level bias to the node features, offering an efficient mechanism for representation adaptation.
• We propose a novel consistency-aware framework that goes beyond conventional contrastive learning. Our mathematical framework comprises Consistency Loss $\mathcal{L}_{\text{con.}}$, Regularization Loss $\mathcal{L}_{\text{R}}$, Symmetry Loss $\mathcal{L}_{\text{symm.}}$, and unified Augmentation-to-Augmentation Loss $\mathcal{L}_{\text{A2A}}$. This design explicitly addresses the consistency (invariance) property of conditional distributions in OOD settings, which was overlooked by previous test-time methods.
• We introduce GOAT, an efficient test-time tuning paradigm that achieves consistent learning without the computational overhead of training-time methods. Our framework integrates a self-supervised loss mechanism with a low-rank adapter, enabling unlabeled test graphs to effectively adapt to distribution shifts with minimal computational resources. The method is theoretically grounded in a relaxed optimization objective, where learning across augmented views guides the additional parameters to optimize the fixed pre-trained parameters' performance on the shifted distribution.

(Weakness 3) Why optimizing the point estimation problem can minimize the expected supervised loss?

The connection between point estimation and supervised loss minimization can be explained through our theoretical framework:

1. According to Proposition b in Appendix A, for any test graph $\mathcal{G} \sim p(\mathrm{G}|\mathrm{e} = e_i)$, there exists an optimal OOD representation $E^*$ that maps the test graph to the distribution where the pre-trained GNN performs optimally, thus $G^*$.
2. Our formulation of point estimation aims to find this optimal mapping through the augmentation-to-augmentation strategy. Specifically:
   • The symmetric loss ensures the consistency between different views of the same test graph
   • The consistency loss maintains the structural alignment with GNN's feature extraction
   • The regularization term prevents degenerate solutions

As proved in Appendix A, under constraint $E[f(A'_2, X'_2 + E^{\*}_2) - f(A'_2, X'_2)] = 0$, the unsupervised objective ($P_{A2A}$) becomes equivalent to the supervised objective ($P_{A2S})$.

Therefore, by optimizing our point estimation objective, we are effectively minimizing an upper bound of the expected supervised loss without requiring access to labels."

(Please check the following comment for more responses)