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

Authors: Haoxiang Zhang, Zhuofeng Li, Qiannan Zhang, Ziyi Kou, Lianyong Qi, Juncheng Li, Shichao Pei
Primary area: learning on graphs and other geometries & topologies
Keywords: Out-of-distribution Generalizarion, Test-time Adaptation, Graph Neural Network, Self-supervision

Abstract:
Based on topological proximity message passing, graph neural networks (GNNs) can quickly model data patterns on graphs. However, at test time, when the node feature and topological structure of the graph data are out-of-distribution (OOD), the performance of pre-trained GNNs will be hindered. Existing test-time methods either fine-tune the pre-trained model or overlook the discrepancy between the prior knowledge in pre-trained models and the test graph. We propose a novel self-supervised test-time adaptation paradigm GOAT (*https://anonymous.4open.science/r/GOAT-5C0E*), through graph augmentation-to-augmentation strategy, that enables a simple adapter can mitigate the distribution gap of training data and test-time data. GOAT reduces generalization error for node classification in various pre-trained settings through experiments on six benchmark datasets spanning three distinct real-world OOD scenarios. Remarkably, GOAT outperforms state-of-the-art test-time methods, and our empirical study further demonstrates the interpretability of the OOD representation generated from our method.

Decision: reject
Reviewer scores: 3, 3, 5, 5

Reviews and discussion:
<thread>
creation date:
1729242659176

thread_type:
official_review

<thread_object>
creator: reviewer_32n6

<content>
summary:
This paper introduces GOAT, a self-supervised test-time adaptation framework that improves the generalization of pre-trained GNNs on out-of-distribution (OOD) graph data. GOAT uses a graph augmentation strategy with a simple adapter to bridge the distribution gap between training and test data, enhancing performance on node classification tasks. It demonstrates superior results across various real-world OOD scenarios and benchmark datasets, while also being efficient in time and memory. The authors highlight GOAT's interpretability and its insights into handling distribution shifts in GNNs.

strengths:
1. The paper emphasizes the interpretability of the OOD representations generated by GOAT, offering valuable insights into the model's adaptation process in out-of-distribution scenarios.
2. The paper presents a self-supervised strategy for adapting pre-trained GNNs to OOD scenarios without the need for labeled test data, which represents a significant practical contribution.
3. GOAT demonstrates superior computational and memory efficiency compared to several baseline methods, making it well-suited for large-scale graph datasets.

weaknesses:
1. The method is primarily focused on node classification tasks. While it demonstrates promising results, its applicability to other graph-related tasks, such as graph classification or link prediction, has not been fully explored.
2. The paper does not provide a theoretical analysis to support the effectiveness of GOAT, relying instead on empirical evidence from experimental results.

questions:
1. Is GOAT applicable to other graph tasks? If adjustments are required, are there any potential limitations?
2. Could a theoretical analysis or insights be provided to support the effectiveness of GOAT?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730204938087

thread_type:
official_review

<thread_object>
creator: reviewer_bxgo

<content>
summary:
The paper proposes to improve the OOD performance of GNN tasks through a learnable adaptor. The adaptor is designed akin to the attention mechanism, and trained with a self-supervised loss that considers symmetric and consistent losses.

strengths:
1. the method does not require the change of pre-trained weight. 
2. the self-supervised loss considers the domain specific requirements regarding e.g., the symmetricity. 
3. an explicit representation of the OOD as a matrix

weaknesses:
1. all the ingredients of the method, including utilising attention mechanism for adaptation, the contrastive style supervised loss function, and using another branch (i.e., a learnable adaptor) for domain adaptation, are not new. The paper is a combination of several known techniques to work in a specific task. 

2. I am not sure if this problem should be formulated as an OOD task, and it looks rather like a domain adaptation. The test time data is simply the data we may use in the new domain for adaptation. I assume for OOD tasks, we do not have test time data for learning the adaptor. 

3. The performance against existing methods is not always better.

questions:
Please see above the weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730382777131

thread_type:
official_review

<thread_object>
creator: reviewer_2czr

<content>
summary:
When using GNNs, it may be that graphs used at test time (or under deployment) are different in systemic and meaningful ways from the graphs the GNN was trained on due to changes in the data-generating environment, meaning test-time data may be too far out-of-distribution to be effectively classified by the GNN.  This paper introduces GOAT, an approach to modifying OOD test-time graphs so they can be accurately classified by a pre-trained GNN.

GOAT transforms the graph taking into account three things.  First, the transformed graph and original graph (? - see Questions) must perform well under some self-supervised task. Second, this is regularized by encouraging the transformed graph and original graphs to have similar GNN outputs ("Symmetry").  Third, the approach is "consistent," where the transformation of the GNN output on the original graph is encouraged to be similar to the GNN output of the transformation of the graph.

Performance on test-time graph classification is compared against other approaches, and GOAT is shown to outperform or compete closely with the other techniques.  An ablation study is done to show that each of the three portions are necessary.

strengths:
This is an appropriately important question, and state-of-the-art performance on these tasks is important.  The paper shows that the approach works, and runs quickly and with little memory usage.  This is the foundation of an appropriately impactful paper.

weaknesses:
- Overall, things are poorly explained, and I do not understand the approach well.  A few specific examples of these points of confusion follow here and in the Questions portion, but throughout, the storytelling needs to be clearer.  In particular, the intuitive explanations of Eqs 2, 8, and 10 are insufficient for the main contributions of the paper.
- Quite a bit of important notation is insufficiently explained (see questions).
- Wording in Assumption 1 is poor grammar and confusing. "Environment is the condition that generates graph".  "Environment" seems to be a vague idea of "things are changing, so the graphs are changing," but the environments are used quite mathematically.  For your approach, what makes an environment suddenly become the next environment in the sequence?
- The experimental results do show improvement, but not overwhelmingly so.  I don't feel these results earn the benefit of the doubt on confusing (to me) explanations.

Overall, I definitely do not understand key portions of this paper.  It is always possible this is my fault, but I believe in this case, it is due to poor and uncareful explanations.

**Minor thing**
- Repeated misspelling of "Augmentation to augmentation" with "augmentaion"

questions:
- In Equation 2, what is $ \hat G_{te} $ ?  Without an explanation of $\hat G_{te}$ and a differentiation from $G_{te}$ in line 161, the equation 2 makes little sense, making a poor foundation for the rest of the loss functions.
- What is $\textbf{H}$ on lines 211 and 240?  What is a "layer" in this context on line 240?
- How are $\textbf{K'}$ and $\textbf{V'}$ on line 243 learned?  Are they just linear projections?  The use of ``learned" suggests to me something more complex is happening, but it's never explained?
- Where do $W_Q, W_K, and W_V$ come from in the section containing equation 6?
- What is $L_R$ in Eqn 12?  Is that Eqn 2?
- On line 277, what makes $G_v$ augmented?  As written, aren't those just being drawn from the probability distribution natively?  Is some notation missing?  What are $p$ and $q$ on line 278?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730647441063

thread_type:
official_review

<thread_object>
creator: reviewer_nbtr

<content>
summary:
This paper addresses the challenge of out-of-distribution (OOD) graph data at test time and proposes a test-time adaptation method, called GOAT, for graph neural networks. The key idea is to capture the condition/environment that generates graphs. A low-rank adapter generates representations by which the test graph’s node features are modified to align with the training graph environment. The adapter is optimized using a self-supervised loss function that enforces symmetry and consistency between the different augmented views of the test graph. Empirical results on six benchmark datasets show the effectiveness of GOAT in handling various OOD scenarios.

strengths:
1. Introducing a low-rank adapter is a computationally efficient solution for large graphs. 

2. The authors offer a continuous formulation of the graph test-time adaption problem, as well as the optimization process.

3. The idea of enforcing symmetry and consistency between the different augmented views of the test graph is new.

weaknesses:
1. The proposed method shares many similarities with GTrans. Although this paper continuously formulates the problem, we can see from the discrete version in the Appendix that these two methods both consider modifying the node attribute by a representation that could catch the out-of-distribution drift. Both employ dropEdge as a sampling method for contrastive learning.  In fact, GTrans modifies both the node attributes and graph structures. The main differences lie in the low-rank adapter and the loss function. 

2. The technical novelty is somewhat limited. The low-rank adapter is a straightforward application of existing techniques. The self-supervised loss function is a common solution for test time adaption for graphs. 

3. In the problem formulation, the authors did not explain why the optimal parameter that minimizes the expected supervised loss could be obtained from optimizing the point estimation problem. This is a key problem since Y_te is not available at test time.

questions:
1. In Eq. (2), what $\hat{\cal G}_{te}$  means?

2. In Proposition 1, the statement that "modifies the graph structure within the learned parameter space of a pre-trained GNN model" is not clear. Could you explain how the graph structure is modified and how it relates to the learned parameter space? 

3. The instance on Page 5 of what LROG learns is not a substantial example to illustrate what LROG can learn. How LROG could capture the environment change? As well as Fig. 3, which is illustrative but does not provide the idea of why LROG could catch both the change in graph structure and feature distribution shift. 

4. In Section 3.3, the expression $g_\psi(f(\cal G)) \approx f(g_\psi(\cal G))$  is inaccurate because the input of $g_\psi$ is a graph, not the GNN's output.

5. In Table 2, the average rank may not be a fair comparison as different datasets have varying performance gaps, especially there are 94.35 vs 94.32, 94.79 vs 94.76, and 55.83 vs 55.82
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces GOAT, a self-supervised test-time adaptation framework for graph neural networks (GNNs) in out-of-distribution (OOD) settings. GOAT leverages a low-rank adapter and a consistency-aware loss to align test graphs with the training distribution. The reviewers acknowledged the importance of addressing OOD challenges and the computational efficiency of the method but raised concerns about limited novelty, inadequate theoretical grounding, and unclear presentation. While the authors provided detailed responses, additional experiments, and revised explanations, these efforts were insufficient to fully address the reviewers' major concerns.