Matcha: Mitigating Graph Structure Shifts with Test-Time Adaptation

Authors: Wenxuan Bao, Zhichen Zeng, Zhining Liu, Hanghang Tong, Jingrui He
Primary area: transfer learning, meta learning, and lifelong learning
Keywords: test-time adaptation, distribution shifts, structure shifts, graph neural networks

Abstract:
Powerful as they are, graph neural networks (GNNs) are known to be vulnerable to distribution shifts. Recently, test-time adaptation (TTA) has attracted attention due to its ability to adapt a pre-trained model to a target domain, without re-accessing the source domain. However, existing TTA algorithms are primarily designed for attribute shifts in vision tasks, where samples are independent. These methods perform poorly on graph data that experience structure shifts, where node connectivity differs between source and target graphs. We attribute this performance gap to the distinct impact of node attribute shifts versus graph structure shifts: the latter significantly degrades the quality of node representations and blurs the boundaries between different node categories. To address structure shifts in graphs, we propose Matcha, an innovative framework designed for effective and efficient adaptation to structure shifts by adjusting the htop-aggregation parameters in GNNs. To enhance the representation quality, we design a prediction-informed clustering loss to encourage the formation of distinct clusters for different node categories. Additionally, Matcha seamlessly integrates with existing TTA algorithms, allowing it to handle attribute shifts effectively while improving overall performance under combined structure and attribute shifts. We validate the effectiveness of Matcha on both synthetic and real-world datasets, demonstrating its robustness across various combinations of structure and attribute shifts. Our code
is available at https://github.com/baowenxuan/Matcha.

Decision: accept (poster)
Reviewer scores: 6, 6, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1730176339852

thread_type:
official_review

<thread_object>
creator: reviewer_m4v2

<content>
summary:
[Update]
Thanks for the authors'  feedback. My concerns have been addressed. I raised my vote accordingly.

The authors present a method called AdaRC, which is designed to improve the accuracy of Graph Neural Networks (GNNs) under testing time graph structure shifting conditions. It achieves this by adapting GNN architectures in real-time based on the changing graph structure during testing.  The key idea is to introduce a prediction-informed clustering loss which leads to a better learned node representation. The authors demonstrate the superiority of AdaRC algorithm on several popular benchmark datasets with comparisons to popular baseline methods.

strengths:
* Propose a novel loss (PIC loss) to improve the robustness of learned graph embedding when structure shifting is presented.
* The algorithm comes with theoretical guarantees, although I did not check the correctness of the proof.
* Experiments on both controlled synthetic datasets and real-world datasets show the effectiveness of the proposed algorithm.

weaknesses:
* 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.

* 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.

questions:
* If the graph structure is shifting in real-time, that is, there is no stable distribution in testing time, will the proposed algorithm still work well?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730512957570

thread_type:
official_review

<thread_object>
creator: reviewer_khid

<content>
summary:
This paper proposes a method to mitigate the impact of structure shifts on graph neural networks (GNNs) during test-time adaptation (TTA). The core innovation lies in the introduction of the prediction-informed clustering (PIC) loss to enhance node representation quality during TTA, alongside adjusting hop-aggregation parameters to handle structure shifts. The approach is designed to be compatible with existing TTA algorithms and shows promising results.

strengths:
1. The introduction of the PIC loss to improve node representation quality without labels is a promising approach. This loss function helps better separate classes by minimizing intra-class variance and maximizing inter-class variance, providing a reliable alternative to traditional entropy-based methods.

2. AdaRC is a plug&play framework that can be seamlessly integrated into existing TTA algorithms, making the approach highly extensible.

weaknesses:
1. 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.

2. In Section 3.2, the authors discuss the distinct impacts of attribute and structure shifts; however, using a single-layer GCN as an example may not be sufficient. Given that adjusting hop-aggregation parameters typically involves integrating multi-layer GCNs and broader neighborhood information, it would be beneficial to explore the impact of multi-layer GCNs in the model.

3. Given that the process of using the PIC loss to update hop-aggregation parameters intuitively focuses on optimizing the distinction of node representations (i.e., separating node attribute boundaries), it is recommended to further explore the specific mechanisms by which various structural shifts affect GNN performance. This would help to enhance the theoretical depth and rigor of the analysis.

questions:
see weakness
</content>
</thread_object>

</thread>
<thread>
creation date:
1730648892614

thread_type:
official_review

<thread_object>
creator: reviewer_qcfu

<content>
summary:
This paper proposes AdaRC, a novel framework aimed at improving graph neural networks (GNNs) under distribution shifts, particularly those involving changes in graph structure. Traditional test-time adaptation (TTA) methods are typically designed to handle shifts in node attributes, but they perform poorly with structure shifts, where connectivity patterns vary significantly between training and test data. AdaRC addresses this gap by dynamically adjusting the hop-aggregation parameters in GNNs, effectively enhancing node representation quality under structure shifts. Additionally, a prediction-informed clustering (PIC) loss is introduced to encourage clear separations between node categories, further improving adaptation. Extensive experiments demonstrate AdaRC's compatibility with existing TTA methods, yielding notable performance improvements on both synthetic and real-world datasets.

strengths:
- AdaRC introduces a new approach to handling structure shifts by adapting hop-aggregation parameters, which allows the model to improve node representation quality in ways traditional TTA methods cannot.

- The experimental evaluation is comprehensive, covering both synthetic and real-world datasets, and demonstrates substantial improvements in accuracy and robustness across different shifts, particularly structure shifts.

- The theoretical insights into the impact of structure and attribute shifts are clearly explained, and the figures and visualizations effectively illustrate the method's impact.

weaknesses:
- 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.

- 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.

- 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.

- The performance of AdaRC's clustering approach may be sensitive to the quality of initial predictions, particularly in cases where pseudo-labeling accuracy is low, potentially affecting the model’s stability in scenarios with noisy initial data.

questions:
- Can AdaRC be adapted to handle continuously evolving graphs where node connectivity changes over time?

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

- Could PIC loss performance be enhanced by integrating more robust initialization methods for pseudo-labeling in low-confidence scenarios?

- Does the framework support automated tuning of hop-aggregation parameters across different GNN architectures, or would manual tuning be required for optimal results?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730658641245

thread_type:
official_review

<thread_object>
creator: reviewer_ewx1

<content>
summary:
This work proposes the AdaRC framework, a test-time adaptation approach for graph neural networks (GNNs). At the core of AdaRC is a prediction-informed clustering (PIC) loss, designed to seamlessly integrate with existing methods. Experimental results demonstrate the effectiveness of PIC in enhancing GNN performance.

strengths:
The paper analyzes the performance gap in a simple single-layer Graph Convolutional Network (GCN) using graphs generated from the Community Structure Benchmark Model (CSBM). It effectively investigates the impacts of attribute shifts and structural shifts on performance.

The proposed PIC loss is both simple and effective, allowing for seamless integration with existing frameworks and methods. Its effectiveness is validated through experimental results.

weaknesses:
It is worth noting that, as I am not deeply familiar with this specific area, my comments here may lack technical depth. I will rely on the insights from other expert reviewers and will focus primarily on their evaluations. Here, a few potential concerns include:

- 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 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?

questions:
See weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730667471089

thread_type:
official_review

<thread_object>
creator: reviewer_jasf

<content>
summary:
This paper addresses the issue of structure shifts in Graph Neural Networks at test time.  The authors claim that existing test-time adaptation methods are primarily designed for attribute shifts rather than structure shifts. Based on theoretical analysis, they propose a framework called AdaRC, which aggregates hop parameters to restore good node representation, alleviating the negative impact of structure shifts. They also employ pseudo-class labels to optimize the hop-aggregation parameters.

strengths:
1. The paper points out the problem of structure shifts, which is indeed overlooked in previous research on TTA, or not focused explicitly at least. 

2. The proposed AdaRC framework provides a simple yet effective solution for graphs with structure shifts at test time. It is compatible with existing Test-Time Adaptation algorithms, which allows better adaption.

3. The authors conduct a detailed theoretical analysis of the impact of structure shifts on a single-layer GCN on a CSBM-generated graph.

weaknesses:
1. 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. 

2. 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. 

3. 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.  

4. 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.

questions:
1. AdaRC is a plug-and-play method, have you explored scenarios where it might conflict with other TTA methods? For instance, if a TTA method focuses on adapting to changes in node features while AdaRC adjusts to structure shifts, could their optimization goals lead them in opposite directions?

2. On Twitch-E and OGB-Arxiv, AdaRC shows only minor improvements without artificially injected structure shifts. Does this suggest that the impact of structure shift might be less significant in these real-world datasets?  Could this be because the type of structure shift addressed by AdaRC is less prevalent in these contexts?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732225059286

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Response to All Reviewers (Part 1)

comment:
Dear Reviewers, 

We sincerely thank you for your valuable feedback and for recognizing the strengths of our work. Below, we summarize the main contributions and key strengths of our paper: 
- **Addressing an Important Yet Overlooked Problem** (jAsf).  Our work focuses on the critical yet previously overlooked problem of structure shifts in graph data, in the context of TTA. 
- **Detailed Theoretical Analysis** (jAsf, eWx1, qcfU). We provide rigorous theoretical analysis of the impact of structure shifts on single-layer GCNs using CSBM graphs, offering deep insights into the challenges posed by these shifts. 
- **Simple, Effective, and Compatible Method** (all reviewers). Our proposed AdaRC framework is simple yet effective in improving node representation quality and addressing structure shifts. It is fully compatible with existing TTA algorithms, enabling broader applicability and enhanced performance.
- **Comprehensive Experiments** (qcfU, M4v2). Extensive experiments on both synthetic and real-world datasets validate the robustness and effectiveness of AdaRC across various types of shifts, particularly structure shifts.

We deeply appreciate your constructive suggestions and would like to address some common questions raised about our work 

# 1. Gap between CSBM and Real-World Graphs (jAsf, KHid)

Our theoretical analysis primarily focuses on single-layer GCNs and CSBM graphs, which effectively capture homophily and degree shifts, two factors commonly observed in real-world scenarios that significantly influence GNN performance. Furthermore, reviewers' questions have inspired us to further extend our theoretical framework to multi-hop GCNs (in Appendix A.7, and also in [this anonymous repo](https://anonymous.4open.science/r/AdaRC-ICLR-Rebuttal-93E4/AdaRC_multihop_gcn.pdf)), allowing us to analyze more complex structure shifts beyond single-layer settings. 
- **CSBM Reflects Real-World Structure Shifts**. CSBM graphs have been frequently utilized in theoretical studies [1,2,3] of GNNs due to their ability to model two critical graph metrics, degree and homophily, that significantly influence GNN performance. We believe CSBM effectively captures the challenges posed by structure shifts commonly encountered in real-world applications.
- **Extending Analysis to Multi-Hop GCNs**. 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 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 in [this anonymous repo](https://anonymous.4open.science/r/AdaRC-ICLR-Rebuttal-93E4/AdaRC_multihop_gcn.pdf) for your convenience. All our propositions naturally generalize to $K$-hop GCNs, capturing more complex structure shifts. 

[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

# 2. Performance on Real-World Graphs (jAsf, eWx1)
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 [4]. 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. 

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

</thread>
<thread>
creation date:
1733078557440

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Friendly Reminder Regarding Rebuttal Discussion

comment:
Dear Reviewers,

Thank you for taking the time to provide thoughtful feedback on our submission, "AdaRC: Mitigating Graph Structure Shifts during Test-Time." We’ve greatly benefited from your comments and hope our rebuttal addressed your questions and concerns effectively.

As December 2 is the final day to post feedback to the authors, we wanted to kindly remind you that we are happy to engage in further discussions or clarify any remaining points if needed.

We appreciate your effort in reviewing our work and look forward to hearing your thoughts.

Best regards,

The Authors
</content>
</thread_object>

</thread>
<thread>
creation date:
1733264574233

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Brief Summary of Contributions and Modifications

comment:
We sincerely thank all reviewers for their constructive feedback and suggestions, which have greatly improved the quality of our paper. As the discussion period concludes, we would like to provide a brief summary of our paper’s contributions and the modifications made during the rebuttal:

# Contributions
1. **Addressing an Important Yet Overlooked Problem**: Our work focuses on the critical yet underexplored issue of structure shifts in graph data within the context of TTA.
2. **Detailed Theoretical Analysis**: We present rigorous theoretical analysis, uncovering the distinct impact patterns of attribute and structure shifts on GNNs.
3. **Simple, Effective, and Compatible Method**: Our proposed AdaRC framework is simple yet effective in improving node representation quality under structure shifts. It is fully compatible with existing TTA algorithms, enabling broader applicability and enhanced performance.
4. **Comprehensive Experiments**: Extensive experiments on synthetic and real-world datasets validate the robustness and effectiveness of AdaRC across various types of shifts, particularly structure shifts.

# Rebuttal Modifications
1. **Intuitive Examples**: To better illustrate our theoretical findings, we added visualizations in Appendix A.2.
2. **Extension of Theory**: We extended our theoretical analysis to multi-hop GCNs, to analyze the impact of structure shifts beyond homophily and degree shifts, as detailed in Appendix A.7.
3. **Additional Experiments**:
    1. **Scalability**: We evaluated AdaRC’s computational cost with increasing graph sizes (Appendix C.8).
    2. **More Architectures**: We provided additional full experiments combining AdaRC with various GNN architectures (Appendix C.9).
    3. **Evolving Graphs**: We tested AdaRC on streams of graphs with evolving structure shifts, with results presented in Table A of [this response](https://openreview.net/forum?id=EpgoFFUM2q&noteId=1aOTie6P7S).

We would also like to respectfully clarify that Reviewer M4v2's evaluation may partially stem from a misunderstanding of our theoretical analysis, as their stated confidence level is only 1. Specifically, they suggested that our algorithm relies on theoretical assumptions. However, AdaRC does not depend on these assumptions; rather, we use CSBM as a common analytical framework to study the challenges of homophily shift and degree shift. To demonstrate the generalizability of AdaRC, we have conducted extensive experiments on real-world datasets, as shown in Table 2.

That said, we are grateful for Reviewer M4v2's suggestion regarding high-level intuitions, which prompted us to include additional visualizations in Appendix A.2 to enhance accessibility and understanding.

Once again, we deeply appreciate the time and effort each reviewer has invested in providing valuable feedback.
</content>
</thread_object>

</thread>
<thread>
creation date:
1739384044375

thread_type:
public_comment

<thread_object>
creator: ~wenxuan_bao1

<content>
title:
Algorithm Name Change Notification

comment:
We have changed the algorithm name from **AdaRC** to **Matcha**. Please note that all previous reviews and rebuttals refer to the old name. We hope this clarification prevents any confusion.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes AdaRc for solving the structure shifts in graphs, which can adjust hop-aggregation parameters in GNN during test-time adaptation. 

The main strengths of the paper include: 1) study an overlooked problem of TTA; 2) the proposed AdaRc is simple yet effective; and 3) detailed theoretical analysis is provided.

Despite these, the reviewers also raised several drawbacks and concerns for this paper in the first round, including: 1) practicality in real-world; 2) experiments on real-world graphs, more GNN backbones and multi-layers; and 3) explanations for the gains among different datasets.

The authors have provided a rebuttal. Only one reviewer has attended the discussion-phase and all the reviewers kept their original ratings after rebuttal, i.e., four weak accepts. The AC has carefully checked the comments of the reviewers and the response of the authors. The AC thinks most of the concerns of the reviewers have been solved. Thus, considering the strengths of this paper, the AC thinks this paper could be a valuable work for TTA with graphs and thus recommends acceptance to this paper.