# Matcha: Mitigating Graph Structure Shifts with Test-Time Adaptation

arXiv: https://arxiv.org/abs/2410.06976 · HTML: https://mlsanity.com/paper/2410.06976/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 51 of its 72 references that are in the map.
- First posted on arXiv 9 Oct 2024.

## Builds on (most cited first, 30 of 51)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [AugMix: A Simple Data Processing Method to Improve Robustness and Uncertainty](https://mlsanity.com/paper/1912.02781/) (2019)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Do We Really Need to Access the Source Data? Source Hypothesis Transfer for Unsupervised Domain Adaptation](https://mlsanity.com/paper/2002.08546/) (2020)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Generalizing to Unseen Domains: A Survey on Domain Generalization](https://mlsanity.com/paper/2103.03097/) (2021)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [Deep Visual Domain Adaptation: A Survey](https://mlsanity.com/paper/1802.03601/) (2018)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs](https://mlsanity.com/paper/1902.10191/) (2019)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [MEMO: Test Time Robustness via Adaptation and Augmentation](https://mlsanity.com/paper/2110.09506/) (2021)
- [Beyond Low-frequency Information in Graph Convolutional Networks](https://mlsanity.com/paper/2101.00797/) (2021)
- [A Comprehensive Survey on Test-Time Adaptation under Distribution Shifts](https://mlsanity.com/paper/2303.15361/) (2023)
- [Graph Neural Networks with Heterophily](https://mlsanity.com/paper/2009.13566/) (2020)
- [Parameter-free Online Test-time Adaptation](https://mlsanity.com/paper/2201.05718/) (2022)
- [Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks](https://mlsanity.com/paper/2102.06462/) (2021)
- [How Powerful are Spectral Graph Neural Networks](https://mlsanity.com/paper/2205.11172/) (2022)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Data Augmentation for Deep Graph Learning: A Survey](https://mlsanity.com/paper/2202.08235/) (2022)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [Robustness of Graph Neural Networks at Scale](https://mlsanity.com/paper/2110.14038/) (2021)
- [Out-Of-Distribution Generalization on Graphs: A Survey](https://mlsanity.com/paper/2202.07987/) (2022)
- [Shift-Robust GNNs: Overcoming the Limitations of Localized Graph Training Data](https://mlsanity.com/paper/2108.01099/) (2021)

## Built on by (most cited first, 10 of 10)

- [Can Graph Neural Networks Learn Language with Extremely Weak Text Supervision?](https://mlsanity.com/paper/2412.08174/) (2024)
- [Breaking Silos: Adaptive Model Fusion Unlocks Better Time Series Forecasting](https://mlsanity.com/paper/2505.18442/) (2025)
- [PLANETALIGN: A Comprehensive Python Library for Benchmarking Network Alignment](https://mlsanity.com/paper/2505.21366/) (2025)
- [Mint: A Simple Test-Time Adaptation of Vision-Language Models against Common Corruptions](https://mlsanity.com/paper/2510.22127/) (2025)
- [Subspace Alignment for Vision-Language Model Test-time Adaptation](https://mlsanity.com/paper/2601.08139/) (2026)
- [PromptDyG: Test-Time Prompt Adaptation on Dynamic Graphs](https://mlsanity.com/paper/2606.22914/) (2026)
- [PlugSI: Plug-and-Play Test-Time Graph Adaptation for Spatial Interpolation](https://mlsanity.com/paper/2602.09824/) (2026)
- [Ramen: Robust Test-Time Adaptation of Vision-Language Models with Active Sample Selection](https://mlsanity.com/paper/2604.21728/) (2026)
- [Temporal Memory-Aware Online Test-Time Adaptation on Dynamic Graphs](https://mlsanity.com/paper/2608.27948/) (2026)
- [Reference-Tail Trust:Certified Probability Floors for Learned Updates Inside a Deployed Network](https://mlsanity.com/paper/2609.34904/) (2026)

## Abstract (arXiv)

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 .