Matcha: Mitigating Graph Structure Shifts with Test-Time Adaptation
Authors: Wenxuan Bao
Zhichen Zeng
Zhining Liu
Hanghang Tong
Jingrui He
Venue: ICLR 2025 Poster (2025)
Keywords: test-time adaptation
distribution shifts
structure shifts
graph neural networks
Primary area: transfer learning, meta learning, and lifelong learning
TL;DR: We propose AdaRC, an innovative framework designed for effective and efficient adaptation to structure shifts by adjusting the hop-aggregation parameters in GNNs.

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.

Published as a conference paper at ICLR 2025
MATCHA: MITIGATING GRAPH STRUCTURE SHIFTS WITH TEST-TIME ADAPTATION
Wenxuan Bao', Zhichen Zeng', Zhining Liu', Hanghang Tong', Jingrui He University of Illinois Urbana- OabbanaChhampigi {wba04, zhichenz, 1iu326, htong, jingruijeillinoii
ABSTRACT
Powerful as they are, graph neural networks (GNNs) are known 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 graph data that experience structure shifts, where node connec- tivity differs between source and target graphs. We attribute this performance gap the distinct impact of node attribute shifts versus graph structure shifts: the lat- ter significantly degrades the quality of node representations and blurs the bound- aries between different node categories. To address structure shifts in graphs. we propose Mat cha, an innovative framework designed for effective and effi- cient adaptation structure shifts by adjusting the hop-aggregation parameters GNNs. To enhance the representation quality, we design a prediction-infomeee clustering loss to encourage the formation of distinct clusters for different node categories. Additionally, Matcha seamlessly integrates with existing TTA algo- rithms, allowing to handle attribute shifts effectively while improving overall performance under combined structure and attribute shifts. We validate the effec- tiveness of Mat cha on both synthetic and real-world datasets, demonstrating its robustness across various combinations of structure and attribute shifts. Our code is available at htttps: //gi thub. com http://...oobb.www..aa.aa. wttpb//wwwwwwxxae waaaanaaaaaaaaataaeaeea Maatcha
INTRODUCTION
Graph neural networks (GNNs) have shown great success in various graph applications such as social networks (Rozemberezki et al. 2021). scientific literature networks (Hu et al. 22020, and financial fraud detection (Pareja al. 2020 Their success heavily relies on the assumption that training and testing graphs are identically distributed (Li et al. 2022a). However, real-world graphs usually involve distribution shifts in both node attributes and graph structures (Liu et al., 2023 Wu ct al. 2023a b). For example, given two social networks (c.g., Linkedln for professional networking and Instagram for casual content sharing), the user profiles likely to vary due to the different functionalities of two graphs, resulting in attribute shifts. Besides, as LinkedIn users tend to connect with professional colleges, while users on Instagram often connect with family and friends, the connectivity patterns vary across different networks, introducing structure shifts. The co-existence of these complex shifts significantly undermines GNN model performance (Li (Liet al. 2022a).
Various approaches have been proposed to tackle distribution shifts between the source and target domains, e.g., domain adaptation (Wang & Deng 2018) and domain generalization (Wang et al., 2023b). But most of these approaches require access to either target labels (Wu et al.) 2023a or source domain during adaptation (Liu et al. 2023, Xiao et al., (023). which often impractical in real-world applications. For example, when a model is deployed for fraud detection, the original transaction data used for training may no longer be accessible. Test-time adaptation (TTA) has emerged promising solution, allowing models to adapt to unlabeled target domain without accessing the source domain (Liang et al. 2023). These algorithms demonstrate robustness against various image corruptions and style shifts in vision tasks (Wang et al., 2021; Iwasawa & Matsuo, 2021 Zhang et al. 2023). However, applying TTA to graph data presents significant challenges, especially under structure shifts. As shown in Figure T both attribute and structure shifts (e.g..

---

Published as a conference paper at ICLR 2025
MAVIR EOG Sharr
Cscalen Bounday
Paalzed Cara
Vaguboe Clas
Structure
134
M
02
32-
Frojcted Ripresntaaetss
Atritate Shi
Stacture SHIt
Hillogrrms of Projected Representations Under Different Distribution Snifts
Figure 1: Generic TTA algorithms (T3A, Tent, AdaNPC) are significantly less effec- tive under structure shifts (right) than at- tribute shifts (left). On the contrary, our proposed Mat cha could significantly im- prove the performance of generie TTA (gray shaded area). The dataset used is CSBM.
Figure 2: Attribute shifts and structure shifts have different impact patterns. Compared to attribute shifts (b), structure shifts (c) mix the distributions of node representations from different classes, which cannot be alleviated by adapting the decision bound- ary. This explains the limitations of existing generic TTA algorithms. The dataset used is CSBM.
homophily and degree shifts) lead to performance drops on target graphs, but current TTA methods provide only marginal accuracy improvements under structure shifts compared to attribute shifts.
In this paper, we seek to understand why generic TTA algorithms perform poorly under structure shifts. Through both theoretical analysis and empirical evaluation, we reveal that while both attribute and structure shifts affect model accuracy, they impact GNNs in different ways. Attribute shifts mainly affect the decision boundary and can often be addressed by adapting the downstream clas- sifier. In contrast, structure shifts degrade the upstream featurizer, causing node representations to mix and become less distinguishable, which significantly hampers performance. Figure 2 illustrates this distinction. Since most generic TTA algorithms rely high-quality representations (Iwasawa & Matsuo 2021; Wang et al. 2021 Zhang et al. 2023), they struggle to improve GNN performance under structure shifts.
To address these limitations, we propose that the key to mitigating structure shifts lies in restoring the quality of node representations, making the representations of different classes distinct again. Guided by theoretical insights, we propose adjusting the hop-aggregation parameters which con- trol how GNNs integrate node features with neighbor information across different hops. Many
GNN designs include such hop-aggregation parameters, egg., GPRGNN (Chien et al. 2021 APPNP (Klicpera et al.] 2019), JKNet (Xu al.) 2018), and GCNII (Chen al.] 2020). Build- ing on this, we introduce Matcha, framework to Mitigate grAph sTruCture sHifts with test-time Adaptation. restores representation quality by adapting agggegggnnn parameters via minimiz- ing prediction-informed clustering (PIC) loss, promoting discriminative node representations with- out falling into trivial solutions as with traditional entropy loss. Additionally, our framework can be seamlessly integated with existing TTA algorithms to harness their capability to handle attribute shifts. We empirically evaluate Matcha with a wide range of datasets and TTA algorithms. Exten- sive experiments both synthetic and real-world datasets show that Matcha can handle a variety of structure shifts, including homophily shifts and degree shifts. Moreover, is compatible to a wide range of TTA algorithms and is able to enhance their performance under various combinations of attribute shifts and structure shifts. We summarize our contributions as follows:
Theoretical analysis reveals the distinct impact patterns of attribute and structure shifts on GNNs, which limits the effectiveness of generic TTA methods in graphs. Compared to attribute shifts, structure shifts more significantly impair the node representation quality.
A novel framework Mat cha is proposed to restore the quality of node representations and boost existing TTA algorithms by adjusting the hop-aggregattin parameters.
Empirical evaluation on both synthetic and real-world scenarios demonstrates the effectiveness of Matcha under various distribution shifts. When applied alone, Matcha enhances the source model performance by up to 31 .95.. When integrated with existing TTA methods, Matcha further boosts their performance by up to 40.61%.
RELATED WORKS
Test-time adaptation (TTA) aims to adapt a pre-trained model from the source domain to an unla- beled target domain without re-accessing the source domain during adaptation (Liang et al. 2023
2

---

Published as a conference paper at ICLR 2025
For i.i.d. data like images, several recent works propose to perform image TTA by entropy mini- mization Wang et al. 2021| Zhang et al. 2022), )
(Iwasawa & Matsuo 2021 Zhang
et al.] 2023), consistency regularization (Boudiaf et al.] 2022), etc. However, graph TTA more challenging due to the co-existence of attribute shifts and structure shifts. To address this issue, GTTrans (Jin et al.] (023) proposes to refine the target graph at test time by minimizing a surrogate loss. SOGA (Mao et al., 2024) maximizes the mutual information between model inputs and out- puts, and encourages consisteney between neighboring or structurally similar nodes, but it is only applicable to homophilic graphs. Focusing on degree shift, GraphPatcher (Ju et al.) (023) learns to generate virtual nodes to improve the prediction on low-degree nodes. In addition, GAPGC (Chen) al. 2022) and GT3 (Wang et al. (022)) follow self-supervised learning (SSL) scheme to fine-tune the pre-trained model for graph classífication.
Graph domain adaptation (GDA) aims to transfer knowledge from a labeled source graph to an unlabeled target graph with access both graphs. Most of the GDA algorithms focus on learning invariant representations over the source and target graphs by adversarial learning (Zhang et al.
2019 Wu et al.] 2020; Xiao et al., 2023) or minimizing the distance between source and target graphs (Zhu et al. 2021b Wu et al. 2023b). More recent works (Liu al. 2023 2024a) address the co-existence of structure and node attribute shifts by reweighing the edge weights of the source graphs. However, GDA methods require simultaneous access both the source and target graphs, and thus cannot be extended to TTA scenarios.
We also discuss related works in (1) graph out-of-distribution generalization and (2) homophily- adaptive GNN models in Appendix E.1
ANALYSIS
In this section, we explore how different types of distribution shifts affect GNN performance. We first introduce the concepts of attribute shifts and structure shifts in Subsection 3.1 Subsequently, in Subsection 3.2] we analyze how attribute shifts and structure shifts affect the GNN performance in different ways, which explain the limitation of generic TTA methods. Finally, in Subsection B.3
we propose that adapting the hop-aggregation parameters can effectively handle structure shifts.
3.1 PRELIMINARIES
In this paper, we focus on graph test-time adaptation (GTTA) for node classification. A labeled source graph is denoted as S = (Xs, As) with node attribute matrix Xs E NxD and adjacency matrix Ag E {0, NxN. The corresponding node label matrix is denoted as Ys E {0, 1) Nx For a node vi, we denote its neighbors as N(e:) and node degree as d,. A GNN model is pre-trained on the source graph, where Is is the featurizer extracting node-level representations, and gs is the classifier, which is usually a linear layer. The goal of GTTA is to adapt the pre-trained
o fs(()
GNN model enhance node classification accuracy on an unlabeled target graph with different distribution, while the source graph S are not accessible during adaptation
(X Tr. Ar)
Compared with TTA on regular data like images, GTTA is more challenging due to the co-existence
of attribute shifts and structure shifts (Li al. 2022a Wu et al. 2023b), which are formally defned as follows (Liu et al. 2023).
Attribute shift. We assume that the node attributes æ. for each node (given its label y:) are i.i.d. sampled from a class-conditioned distribution Paly- The attribute shift is defined as ps # PT æzyy
a/y Structure shift. We consider the joint distribution of adjacency matrix and labels IP PAXY. The structure shift is defined as IP5 PyY + P Specifically, we focus two types of structure shifts: degree shift and homophily shift.
Degree shift. Degree shift refers to the difference in degree distribution, particularly the aver- age degree, between the source graph and the target graph. For instance, in the context of a user co-purchase graph, in more mature business regions, the degree of each user node may be rela-
'This setting is also referred to as source-free unsupervised graph domain adaptation (Mao et al. 2024 Here, we primarily follow the terminology used by Jin et al. 22023) is important to note that, unlike the online setting often adopted in image TTA, graph TTA allows manultanouus access to the entire unlabeled target graph T (Liang et al. 2023
3

---

Published as a conference paper at ICLR 2025
tively higher due to multiple purchases on the platform. However, when the company expands its operations to a new country where users are relatively new, the degree may be comparatively lower.
Homophily shift. Homophily refers to the phenomenon that node tends to connect with nodes with the same labels. Formally, the node homophily of a graph & is defined as (Pei et al. 2020):
Σ has h(g) N
Σ
where h; = Ke E E(u,): yj =
(1)
dg
where ||| denotes the cardinality of set. Homophily shift refers the phenomenon that the source and target graphs have different levels of homophily. For example, with node labels as occupation, business social networks (e.g., LinkedIn) are likely to be more homophilic than other social networks (e.g., Pinterest, Instagram).
Although structure shifts do not directly change the distribution of each single node's attribute, they change the distribution of each node's neighbors, and thus affects the distribution of node representations encoded by GNNs.
3.2 IMPACTS OF DISTRIBUTION SHIFTS
As observed in Figure ! both attribute shifts and structure shifts can impact the performance of GNNs. However, the same TTA algorithm demonstrates remarkably different behaviors when ad- dressing these two types of shifts. We posit that this is due to the distinct ways in which attribute shifts and structure shifts affect GNN performance. We adopt the contextual stochastic block model (CSBM) and single-layer GCNs to elucidate these differences.
CSBM (Deshpande et al. 2018 a random graph generator widely used in the analysis of GNNs
(Ma et al.) 2022, Mao et al. 2023 Yan et al., (022). Specifically, we consider a CSBM with two N nodes. The attributes NN,, I), where H4 - 44 for U, E C+ and μ4; μ- for v; E C_. Each pair of nodes are connected with probability
classes C+ {t/ : V/ +1 and C_ {v; V/: 1)), each having
for each node v; are independently sampled from Gaussian distribution 2
p if they are from the same class, otherwise q. As result, the average degree is d N(p+g)
and
2 node homophily h p We denote the graph as CSBM M_,d, .d,h). where μ4, μ- encode p-- the node attributes and d, encode the graph structure.
Single-layer GCN. We consider a single-layer GCN, whose featurizer is denoted Z f(X,A) X + D-1AX = (1 7 D- A)), where D is the degree matrix. Equiva- lently, for each node v, its node representation is z; x; 7 z. EeyeN(e.) Tj. The parameter y controls the mixture between the node's own representation and its one-hop neighbors' average representation. We consider 7 as a fixed parameter for now, and adapt it later in Subsection 3.3 We consider linear classifier as g( ( Zu + 1b, which predicts node En positive 2, and vise versa.
In Proposition 3.1 and Corollary 3.2 below, we derive the distribution of node representations
{ AN J. and give the analytical form of the optimal parameters and expected accuracy.
dd d.,,,,,,, h), the node representation 2, of node 0 E C. generated by single-layer GCN follows Gaussian distribution of
Proposition 3.1. For graphs generated by CSBM(H+ 1
S. (1++)))) + (1-11h))ppp- ho)
(1+
(1+2,)) (1+
2, ~
where di is the degree of node Vi, and h2 is the homophily of node defined in Eq. results hold for U, C_ after swapping μ. and μ...
7
Similar
Corollary 3.2. When μ4 =, -M, and all nodes huve the same homophily h = , and
degree d N(p+g), the classifier maximizes the expected accuracy when sign(1+ 1))
1 and b 0. gives linear decision boundary of {z =x1 w = 0} and the expected accuracy TAlla
d Acc = 2 1 1)1 ||11|2
(3)
where Tb is the CDF of the standard normal distribution.
4

---

Published as a conference paper at ICLR 2025
To analyze the distinct impact patterns of attribute shifts and structure shifts, decompose the accuracy gap of GNNs between the source graph and the target graph into two parts as follows, Aces(gs fs) - Accr(gs fs) Accsigs fs) sup Acerlgr fs) + sup Acer o fs) Ager(gs o fs).
epuessstatioon degrndation A, where Accg, AcCT denote the accuracies on the source and target graphs, respectively. sup87 (ce fs) is the highest accuracy that a GNN can achieve on the target graph when the featurizer fs is frozen and the classifier gr is allowed adapt. Using this accuracy as a pivot, the accuracy gap is decomposed into representation degradation and classifier bias. A visualized illustration is shown in Figure
total accurccy sap
classitie bis
Representation degradation A quantifies the performance gap attributed to the suboptimality of the source featurizer fs. Intuitively, this term measures the minimal performance gap between the source and target graphs that the GNN model can achieve by tuning the classifier gr. Classifier bias Ag quantifies the performance gap attributed to the suboptimality of the source classifier gs. Intuitively, this term measures the part of performance gap the target graph the GNN model can reduce by tuning the classifier gr-
Proposition 3.3 (Impacts of attribute shifts). When training a single-layer GCN on a source graph of CSBM( -a, d, h), while testing it on target gruph of CSBM + Ap, -1 + Ap,d, with 1+*(hh1)
|| 2
||11|2 we have
147
-,
=
12),
where O indicates the same order, i.e. function ((x) O + there exists positive constants Cr,C2, s.A. C1 S Ux) S C2 for all x in its range. implies that the performance gap under attribute shifts mainly attribules to the classifier bias.
z
Proposition 3.4 (Impacts of structure shifts). When training a single-layer GCN a source graph of CSBM Js. -u, hs), while lesting it on target graph of CSBM(u, -M, dr, luT), where 1 S dr ds Ad dg and < hT hg Ah hs, if we have
= O + Ad),
=
(5)
which implies that the performance gap under structure shifts mainly attributes to the representation degradation.
Propositions 3.3 and 3.4 imply that attribute shifts and structure shifts impact the accuracy of GNN differently. Specifically, attribute shifts impact the decision boundary of the classifier, while struc- ture shifts significantly degrade the node representation quality. These propositions also match with our empirical findings in Figure 2 and Figure [0 (in Appendix C.I. Since generic TTA methods
(Wang et al. 2021] [wasawa & Matsuo 2021 Zhang et al.) 2023 usually rely on the representation quality and refine the decision boundary, their effectiveness is limited under structure shifts.
3.3 ADAPTING HOP-AGGREGATION PARAMETERS TO RESTORE REPRESENTATIONS
To mitigate the representation degradation caused by structure shifts, it becomes essential to adjust the featurizer of GNNs. In the following Proposition 3.5, we demonstrate that the degraded node representations due to structure shifts can be restored by adapting 7, the hop-aggregation param- eter. This is because 7 determines the way combine node's own attributes with its neighbors in GNNs. Notice that although our theory mainly focuses on single-layer GCNs, wide range of GNN models possess similar parameters for adaptation, e.g., the general PageRank parameters in GPRGNN (Chin et al. 2021), teleport probability in APPNP (Klicpera et al. 2019), layer aggrega-
tion JKNet (Xu al. 2018). We extend our analysis multi-hop GCNs in Appendix
Proposition 3.5 (Adapting 7). Under the same learning setting as Proposition 3.4 adapting the
source TS to the optimal "T = (2hT 1) on the target graph can alleviate the representation degradation and improve the target classification accuracy by (((A))² + (Ad)2).
Proposition 3.5 indicates that the optimal 7 depends on both node degree d and homophily h. For instance, consider a source graph with hg = and ds = 10. In this case, the optimal featurizer assigns equal weight to the node itself and each of its neighbors, resulting in optimal ?s 10.
5

---

Published as a conference paper at ICLR 2025
GPRGNN
EX
110))
BaseTTA
f
X
XYs
MLP
H
Ak
Forward
Lyuc
Matcha
<--- Backprop
Figure 3: Our proposed framework of Matcha (when combined with GPRGNN)
However, when the target graph's ss degree remains unchanged but the homophily decreases to hy 0.5, where each node's neighbors are equally likely to be positive or negative, the neighbors no longer provide reliable information for node classification, leading to optimal "r when the homophily remains the same. but the target graph's degree is reduced to dr = 1, overemphasizes the neighbor's representation by placing excessive weight on it, whereas the optimal yr in this case would be 1. A visualization of these examples are given in Appendix A.2 A.2
Similarly,
PROPOSED FRAMEWORK
So far, we have found that adjusting hop-aggregation parameters can address the issue of node representation degradation caused by structure shifts. However, translating this theoretical insight into a practical algorithm still faces two challenges:
In the absence of labels, how to update hop-aggregation parameters to handle structure shifts? How ensure that proposed algorithm is compatible with existing TTA algorithms (BaseTTA) in order to simultaneously address the co-existence structure and attribute shifts?
In this section, propose Matcha, including novel pediictioninfoormet clustering loss to courage high-quality node representations, and an adaptation framework compatible with a wide range of TTA algorithms. Figure 3 gives a general framework.
To adapt to graphs with different degree distributions and homophily, Matcha uses GNNs that are capable of adaptively integrating multi-hop information, e.g., GPRGNN (Chien et al. 2021). APPNP (Klicpera et al. 2019), JKNet (Xu et al. 2018), etc. Specifically, we illustrate our framework using GPRGNN representative case. Notably, our framework's applicability extends beyond this example, as demonstrated by the experimental results presented in Appendix C.10 showcasing its versatility across various network architectures.
GPRGNN. The featurizer of GPRGNN is an MLP followed by a general pagerank module. We denote the parameters for MIP as 0, and the parameters for the general pagerank module as = [7o," ... .7K] IR++ K The node representation of GPRGNN can be computed as 7h 7h (A),, where (0)) MX))
(0), Vk: 1,... K are the 0-hop and k-hop representations, Á the normalized adjacency matrix. linear layer with weight w following the featurizer serves the classifier.
Z >
4.1 PREDICCTION-INFOREER CLUSTERING LOSS
This subsection introduces how Mat ch updates the hop-aggregation parameters without labels. Previous TTA methods (Liang et al. 2020 Wang al. 2021 Zhang al.) [022] Bao et 2023) mainly adopt the entropy as a surrogate loss, as it measures the prediction uncertainty. However, we find that entropy minimization has limited effectiveness improving representation quality (see Figure 4 and Table Entropy is sensitive to the scale of logits rather than representation quality, often leading to trivial solutions. For instance, for a linear classifier, simply scaling up all the node representations can cause the entropy loss approach zero, without improving the separability of the node representations between different classes. To address this issue, we propose the prediction- informed clustering (PIC) loss, which can better reflect the quality of node representation under structure shifts. Minimizing the PIC loss encourages the representations of nodes from different classes be more distinct and less overlapping.

---

Published as a conference paper at ICLR 2025
RND denote the representation matrix and Y R denote the prediction of BaseTTa subject to E _.c = 1, where N is the number of nodes, is the dimension of the node representations and C' is the number of classes. We first compute p4, the centroid representation of each (pseudo-)clasee e, and ps, as the centroid representation for all nodes,
Let Z (1, _N]
Yi,zz Y
1. C,
2
We further define the intra-class variance o mira and inter-class variance oeerr as:
ΣΣ Yrollz Melle.
Σ
Yuo Σ
|| 10.12
inter
To obtain discriminative representations, it is natural to expect small intra-class variance i i.e., nodes with the same label are clustered together, and high inter-class variance of i.e., different classes are separated. Therefore, we propose the PIC loss follows:
2
CPcc
intr
intra
(8)
2
2
o²
intra
inter
where o² can be simplified as 0² of
intra
EN
|| 4.l12 (proof in Appendix A.8
inter
It should be noted that although the form of PIC loss seems not reusing the adjacency matrix A, still evaluates the suitability of the current hog-aggregntion parameters for the graph structure through the distribution of the representation Z. As shown in Figure Proposition 3.4, structure shifts cause node representations to overlap more, leading to smaller o and larger PIC loss. Alternatively, some algorithms, like SOGA (Mao et al. (024), incorporate edge information by promoting connected nodes to share the same label. These designs implicitly assume homophilic graph, limiting their applicability. As result, SOGA performs poorly heterophilic target graphs, as seen in Table T In contrast, our PIC loss directly targets GNN-encoded node representations, allowing generalize across different graph structures, whether homophilic or heterophilic.
By minimizing the PIC loss, we reduce intra-class variance while maximizing inter-class variance. Importantly, the ratio form of the PIC loss reduces sensitivity to the scale of representations; the norm increases, the loss does not converge to zero, thus avoiding trivial solutions. It is also worth noting that the proposed PIC loss differs from the Fisher score (Gu al., 2012) in two key aspects: First, PIC loss operates on model predictions, while Fisher score relies on true labels, making Fisher inapplicable in our setting where labels are unavailable. Second, PIC loss uses soft predictions for variance computation, which aids in the convergence of Mat cha. whereas the Fisher score uses hard labels, which can lead to poor convergence due to the unbounded Lipschitz constant, as we show in Theorem 4.1 We also provide an example in Appendix [C22 showing that Matcha with PIC loss improves accuracy even when initial predictions are highly noisy.
4.2 INTEGRATION OF GENERIC TTA METHODS
This subsection introduces how Matcha in- tegrates the adaptation of hop-aggregation pa- rameters with existing TTA algorithms to si- multaneously address the co-existence of struc- ture and attribute shifts. Our approach is mo- tivated by the complementary nature of adapt- ing the hop-aggregation parameter and exist- ing generic TTA methods. While the adapted aoo-aggregatiin parameter effectively manages structure shifts, generic TTA methods handle attribute shifts in various ways. Consequently, we design a simple yet effective framework that seamlessly integrates the adaptation of hop- aggregation parameter with broad range of existing generic TTA techniques.
Algorithm Matccha
Matcha (target graph T, featurizer fe.y, classifier
Lw. baseline TTA method BascTTA)
I: for epoch t to 7 do
Apply generic TTA:
Y BaseeTTTTTTT.. Jo.y::
Update hop-aggregation parameters:
7 7 CT, [e. gw. Y) 4: return Y +- BaseTTA(TT,Je.) (....
Our proposed Matcha framework is illustrated in Algorithm [ Given a pre-trained source GNN model fo, 2go and the target graph T, we first employ the baseline TTA method, named BaseTTA,
7

---

Published as a conference paper at ICLR 2025
to produce the soft prediction Y X as pseudo-classes, where Σe= Y.c. = 1. Equipped with pseudo-classes, the hop-aggregation parameters y is adapted by minimizing the PIC loss as described in Subsection 4.1 Intuitively, the predictions of BaseTTA are crucial for identifying pseudo-classes to cluster representations, and in return, better representations enhance the predic- tion accuracy of BaseTTA, Such synergy between representation quality and prediction accuracy mutually reinforces each other during the adaptation process, leading to much more effective out- comes, is worth noting that cha is plug-and-play method that can seamlessly integrate with various TTA algorithms, including Tent (Wang et al. 2021p, T3A (Iwasawa & Matsuo 2021 and AdaNPC (Zhang et al. (023).
Computational complexity. For each epoch, the computational complexity of the PIC loss is O(NCD), linear to the number of nodes. Compared SOGA (Mao al. 2024), which has quadratic complexity from comparing every node pair, PIC loss enjoys greater scalability to the graph size. For the whole Matcha framework, inevitably introduces additional computational overhead, which depends on both the GNN architecture and the baseline TTA algorithm. How- ever, in practice, the additional computational cost is generally minimal since intermediate results (e.g. (H)
(k) K ,) can be cached and reused. We empirically evaluate the efficiency of Mat chachai in
Subsection 5.3 Appendix C.8 and the scalability in Appendix C.9
Convergence analysis. Finally, we analyze the convergence property of Matcha in Theorem below. The formal theorem and complete proof's can be found in Appendix B
Theorem 4.1 (Convergence of Matcha), Let M = ())), ...... vec vec(( H ] E RRNDX((+1)
denote the concatenation of O-hop to K-hop node representations. Given base TTA algorithm, if (1) the prediction Y is L-Lipschitz w.r.l the (aggregated) node representation Z, and (2) the loss function is B-smooth w.r.l. Z, after T steps of gradient descent with step size 1 DIMM we have
Σ T
1
T
$2
M 12 L(
CT.2
T
where C a constant.
shows that Matcha is guaranteed to converge to a flat region with small gradients, with convergence rate + and error rate L.a. Essentially, the convergence of Matcha depends on the sensitivity of the BaseTTA algorithm. Intuitively, if BaseTTA has large Lipschitz constant L, it likely to make completely different predictions in each epoch, and thus hindering the convergence of Matcha. However, in general cases, I, is upper bounded. We give theoretical verification in Lemma B.9 under HRM, and further empirically verify the convergence of Ma Matcha in Figure
Theorem 4.1
EXPERIMENTS
We conduct extensive experiments on synthetic and real-world datasets to evaluate our proposed Mat cha from the following aspects:
RQI: How can Mat cha empower TTA algorithms and handle various structure shifts on graphs?
RQ2::
To what extent can Matcha restore the representation quality better than other methods?
5.1 MATCFA HANDLES VARIOUS STRUCTURE SHIFTS (RQ1)
Experiment setup. We first adopt CSBM (Deshpande et al. 2018 to generate synthetic graphs with controlled structure and attribute shifts. We consider hybrid of attribute shift, homophily shift and degree shift. For homophily shift, we generate a homophily graph with h 0.8 and a heterophily graph with h = 0.2. For degree shift, we generate a high-degree graph with d = 10 and a low-degree graph with d = For attribute shift, we transform the class centers / on the target graph. For real-world datasets, we adopt Syn-Cora (Zhu et al.) 2020). Syn-Products (Zhu) (ct al. 2020). Twitch-E (Rozemberczki et al. 2021), and OGB-Arxiv (Hu et al. 2020). For Syn-Cora and ProdPutuutss, use h 0.8 the source graph and h 0.2 has the target graph. For Twitch- and OGB-Arxiv, we delete a subset of homophilic edges in the target graph to inject both degree and homophily shifts. The detailed dataset statistics are provided in Appendix D.I
We adopt GPRGNN (Chien et al. 202T) as the backbone model for the main experiments. We also provide results other backbone models, including APPNP (Klicpera et al. 2019). JKNet (Xu
8

---

Published as a conference paper at ICLR 2025
Table 1: Accuracy (mean + s.d. %) on CSBM with structure shifts and attribute shifts.
Method
Homophily
Degree
Attribute
homophily shift
Attribute degree
bomoo -t hetero
hetero - homo
high -7 low
low - high
homo -+ hetero
hetero - bomo
high
- low
low -y high
ERM
73.62 1 0.44
76.72 a: 0.89
86.47 4: 0.38
92.92 4: 0.43
61.06 2: 1.67
72.61 = 0.38
77.63 4: 1.13
73.60 4: 3.53
Matcha
89.71 0.27
90.68 1 0.26
88.55 4: 0.44
93.76 1 0.71
85.34 2 4,68
71.70 0.99
78.29
1.41
73.86 1: 4.20
T3A
73.85
76.65
1,08
65.77 2:11
72.92
90.89
1.28
81.91
3:21
+ Mattcha
90.40 0.11
90.50 1: 0.24
88.42 1: 0.60
93.83 1: 0:41
88.49 0.58
79.34 1.85
81.82
1.36
82.12 1: 4,03
Tont
74,64 1: 0.38
79.40 1 0.57
86,49
1: 0.50
92.84
1: 0.18
74.42 2: 0.41
79:57 = 0.40
86.05 1: 0.33
93.06
1: 0.24
Matcha
89.93 0.16
91.26 0.08
89.20
0.20
94,88 0.09
90.12 =: 0.07
91.15 0.20
0.16 87.76
95.04
0.06
AdaNPC
76.03
81.66 0.17
0.38
0.39
63.96
76.33
77.69
76.24
3,06
+ Mat cha
90.03 1 0.33
50.36 1: 0.67
88.19 1: 0.31
92.81 1: 0.57
85.81 0.30
77.63 1.55
78.41
1.03
76.31 1. 3.68
GTrans
74,01 0.44
77.28 4: 0.56
86.58 1: 0.11
92.74 4: 0.13
71.60 2: 0.60
74,15 0.42
83.21 1: 0.25
89. 0.62
Matcha
89.47 0.20
90.31 0.31
87.88 1: 0.77
93:23
0.52
88.88 0.38
76.87 0.66
83,41
0.16
89,
0.93
SOGA
0.
0.35
0.37
0.21
70.45
76.41
81.31
1.03
88, 1,91
+ Mat cha
89.92 0.26
90.69 +: 0.27
88 18.83-2 +: 0.32
94.49 +: 0.23
92 0.28
90.14 0.33
87.11
0.28
93.38 1,06
SraphPatccher
79
0.62
82 14 +: 1.11
87.87 :: 0.18
93.64
:: 0.45
64. 16 16 3-49
76.98 1.04
76.99 :: 1.43
73.31 4: 4,48
+ Mat ihha
91.28 00.28
90.66 + 0.15
88.01 + 0.18
93.88
0.69
89.99 0.41
87.94 0.39
78.43
1.84
77,86 + 4,14
Table 2: Accuracy on real-world datasets.
Method
Syn-Cora
Syn-Products
Twith-
OGB-Ariv
ERM
65.67 = 0.35
37,80 a: 2.61
56.20 a: 0.63
41.06 a: 0.33
Natcha
78.96 100
69.75
0.93
56.76 1 0.22
41.74 1 0.34
1.10
47.59
0.20
38.17
+ Katcha
78.40 1.04
69.81
1 0.36
56,97
1: 0.28
1: 0.27 38.56
Tent
66.26 - 0.38
29.14
4.50
$8.16
1: 0.37
34.48
1 0.28
larget For
Katcha
78.87 1.07
68.45
1.
5M.57
+: 0.42
35
+: 0.27
AdaNPC
67.34 0.76
44.67
1.53
55.43 +: 0.50
40:20 0.35
+ Katcha
77.45 0.62
71.66
40.58
GTras
68.60 = 0:32
43.89
1.75
56.24 1: 0.41
41.28
0.31
+ Katcha
83.49 = 0.78
71.75
0.65
56.75
1:
0.10
41.81110
SOGA
67.16 - 0.72
10.96
1 2.87
56.12
1 0.30
41.23
0.34
Katcha
1.10
70.13
41.78
Figure 4: T-SNE visualization of node repre-
GrophPutcher
+ Katcha
63.01
80.99 = 0.50
2:29
69.39
36.94
1.50
1.29
57,05
57.41
1: 0.59
0.53
41.27
41,83
0.87
0.90
sentations on CSBM homo - hetero.
et al. 2018 and GCNII CChnn et al.
2020) in Appendix C.10 Details on model architectures are provided in Appendix D.2 We run each experiment five times with different random seeds and report the mean accuracy and standard deviation.
Baselines. We consider two groups of base TTA methods, including: (1) generic TTA methods:
T3A [Twasawa & Matsuo 2021), Tent (Wang et al. (02T). and AdaNPC (Zhang et al. 2023). and (2) graph TTA methods: GTrans (Jin et al. (023)). SOGA (Mao et al. 2024h and GraphPatcher (Ju et al,; 2023]. To ensure fair comparison, we focus TTA algorithms in the same setting, which adapt a pre-trained model to a target graph without re-accessing the source graph. We adopt Empirical Risk Minimization (ERM) to pre-train the model on the source graph without adaptation. We use the node classification accuracy on the target graph to evaluate the model performance.
Main Results. The experimental results the CSBM dataset are shown in Table I Under var- ious shifts, the proposed Matcha consistently enhances the performance of base TTA methods. Specifically, compared directly using the pre-trained model without adaptation (ERM), adopt- ing Mat cha (ERM+Mat cha) could significantly improve model performance, with up to 24.28% improvements. Compared with other baseline methods, Mat cha achieves the best performance in most cases, with up to 21. 21.88 improvements. Besides, since Mat is compatible and comple- mentary with the baseline TTA methods, we also compare the performance of baseline methods with and without Mat t cha. As the results show, Mat could further boost the performance of TTA baselines by up to 22.72%.
For real-world datasets, the experimental results are shown in Table 2 Compared with ERM, Matcha could significantly improve the model performance by up to 31.95%. Compared with other baseline methods, Matcha achieves comparable performance on Twitch-E, and significant improvements on Syn-Cora, Syn-Products and OGB-Arxiv, with up to 40.61% outperformance. When integrated with other TTA methods, Matcha can further enhance the performance by up to 39.31%. %. The significant outperformance verifies the effectiveness of the proposed Matcha.
Additional experiments. We also demonstrate that Mat exhibits robustness against (1) struc- ture shifts of varying levels, (2) evolving target graph, and (3) additional adversarial shifts in Ap- respectively.
pendix
C.4 and C.5

---

Published as a conference paper at ICLR 2025
A Accurayy Adppt Accumay, Masp +
Lens, SINE
Lons Aapp vond Acorncy Arppt and
100s, 23
Loss f- 16.0
189 0-
Accumay, a 23.0
Accurnyy 4 100
Acturayy 0
Acouracy Epachs
Accuracy Epechs
0.00
0.3
0.50
0.75
0.5-
0.50
0.7
0.70
0.700
0.8
tyoets
tyouts
Figure 5:
Ablation study on Syn-Products with different sets of parameters to adapt.
Figure 6: Convergence of Matcha on Syn- Cora with different learning rates 17.
5.2 MATCHA RESTORES THE REPRESENTATION QUALITY (RQ2)
Besides the superior performance of Matcha, we are also interested in whether Mat cha success- fully restores the quality of node representations under structure shifts. To explore this, we visualize the learned node representations on 2-class CSBM graphs Figure f Although the pre-trained model generates high-quality node representations (Figure 4 a)), node representations degrades dra- matically when directly deploying the source model to the target graph without adaptation (Fig- ure {b)). With our proposed PIC loss, Matcha successfully restores the representation quality with a clear cluster structure (Figure Moreover, compared to other common surrogate losses (entropy, leeulo-label), PIC loss results in significantly better representations.
5.3 MORE DISCUSSIONS
Ablation study. While Matcha adapts only the hop-aggregation parameters 7 to improve rep- resentation quality, other strategies exist, such as adapting the MLP parameters or both y and together. As shown in 5 adapting only 0 fails to significantly reduce the PIC loss or improve accuracy. Adapting both 7 and 0 minimizes the PIC loss but leads to model forgetting. causing an initial accuracy increase followed by decline. In contrast, adapting only 7 results in smooth loss convergence and stable accuracy, demonstrating that Matcha effectively adapts to structure shifts without forgetting source graph information. We also compare proposed PIC loss to other surrogate losses in Appendix C.6 Our PIC loss has better performance under four structure shifts.
Hy Hyperparameeerr sensitivity. Mat cha only introduces two hyperparameters including the learn- ing rate 1 and the number of epochs T. In Figure we explore different combinations of them. We observe that Matcha converges smoothly in just few epochs, and the final loss and accuracy quite robust to various choices of the learning rate. Additionally, as discussed in Appendix CC.7 we examine the effect of the dimension of hop-aggregation parameters K on Mat cha, and find that consistently provides stable accuracy gains across a wide range of K values.
Computational efficiency. We quantify the additional computation time introduced by Matcha during the test-time. Compared to the standard inference time, Matcha only adds an extra 1 11.9% in computation time for each epoch of adaptation. In comparison, GTrans and SOGA adds 486% and 247% in computation time. Mat cha enjoys great efficiency resulting from only updating the hop-aggregation parameters and efficient loss design. Please refer to Appendix for more details.
Compatibility to more GNN architectures. Besides GPRGNN, Matcha is compatible with various GNN architectures, e.g., JKNet (Xu al., 2018), APPNP (Klicpera et al., 2019). and GC- NII (Chen et al. 2020). In Appendix[C.I C. we test the performance of Matcha with these networks on Syn-Cora. Matcha consistently improves the accuracy.
CONCLUSION
In this paper, we explore why generic TTA algorithms perform poorly under structure shifts. The- oretical analysis reveals that attribute structure shifts on graphs bear distinct impact patterns on the GNN performance, where the attribute shifts introduce classifier bias while the structure shifts de- grade the node representation quality. Guided by this insight, propose Mat cha, a plug-and TTA framework that restores the node representation quality with convergence guarantee. Extensive experiments consistently and significantly demonstrate the effectiveness of Matcha.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENT
This work is supported by National Science Foundation under Award No. IIS- 2416070, and the U.S. Department of Homeland Security under Grant Award Number 17STQAC00001 -0-0000 The views and conclusions are those of the authors and should not be interpreted as representing the official policies of the funding agencies or the government.
REFERENCES
Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In Proceedings of the 36th International Con- ference Machine Leurning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, vol- ume Proceedings of Machine Learning Reseurch, pp. 21-29. PMLR, 2019.
Wenxuan Bao, Tianxin Wei, Haohan Wang, and Jingrui He. Adaptive test-time personalization for federated learning. In Advances in Neural Information Processing Systems 36: Annual Confer- ence on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
Deyu Bo, Xiao Wang. Chuan Shi, and Huawei Shen. Beyond low- low-frequency information in graph convolutional networks. In Thirty-Fifih AAAI Conference Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pp. 3950-3957. AAAI Press, 2021.
Malik Boudiaf, Romain Müller, Ismail Ben Ayed, and Luca Bertinetto. Parameter-free online test- time adaptation. In IEEF/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2022, New Orleans, LA, USA, June 18-24, 2022, pp. 8334-8343. IEEE, 2022.
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Found. Trends Mach. Learn., 8(3-4):231-337, 2015.
Guanzi Chen, Jiying Zhang, Xi Xiao, and Yang Li. Graphtta: Test time adaptation on graph neural networks. CoRR, abs/2208.09 126. 2022.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph con- volutional networks. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 1725-1735, PMLR, 2020.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block models. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NewrlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 8590-8602, 2018
Kaize Ding, Zhe Xu, Hanghang Tong, and Huan Liu. Data augmentation for deep graph learning: A survey. SIGKDD Explor, 24(2):61-77, 2022.
Shaohua Fan, Xiao Wang, Chuan Shi, Peng Cui, and Bai Wang. Generalizing graph neural networks outto--distribution graphs. IEEE Trans. Pattern Anal. Mach. Intell., 46(1):322-337, 2024.
Dongqi Fu, Zhe Xu, Hanghang Tong, and Jingrui He. Natural and artificial dynamics in gnns: A tutorial. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, WSDM 2023, Singapore, 27 February 2023 3 March 2023, pp. 1252-1255. ACM, 2023.
Simon Geisler, Tobias Schmidt, Hakan Sirin, Daniel Zügner, Aleksandar Bojchevski, and Stephan Günnemann. Robustness of graph neural networks at scale. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 7637-7649, 2021.

---

Published as a conference paper at ICLR 2025
Quanquan Gu, Zhenhui Li, and Jiawei Han. Generalized fisher score for feature selection. CoRR, abs/1202.3725, 2012.
Dan Hendrycks, Norman Mu, Ekin Dogus Cubuk, Barret Zoph, Justin Gilmer, and Balaji Lakshmi- narayanan. Augmix: simple data processing method to improve robustness and uncertainty. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Ad- vances Neural Information Processing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Yusuke Iwasawa and Yutaka Matsuo. Test-time classifier adjustment module for model-agnostic domain generalization. In Advances in Neural Information Processing Systems 34: Annual Con- ference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 2427-2440, 2021.
Wei Jin, Tong Zhao, Jiayuan Ding, Yozen Liu, Jiliang Tang, and Neil Shah. Empowering graph rep- resentation learning with test-time graph transformation. In The Eleventh International Confer- ence on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
Mingxuan Ju, Tong Zhao, Wenhao Yu, Neil Shah, and Yanfang Ye. Graphpatcher: Mitigating degree bias for graph neural networks via test-time augmentation. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023. New Orleans, LA, USA, December 10 16, 2023, 2023.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In 5th International Conference on Leurning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Haoyang Li, Xin Wang, Ziwei Zhang, and Wenwu Zhu. Out-of-distribution generalization on graphs: survey. CoRR, hts//202.00987,, 2022a.
Haoyang Li, Ziwei Zhang, Xin Wang. and Wenwu Zhu. Learning invariant graph representations for -fitt--distiiuuttinn generalization. In Advances in Neural Information Processing Systems 35: Anmual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28- December 2022, 2022b.
Haoyang Li, Xin Wang, Ziwei Zhang, and Wenwu Zhu. OOD-GNN: out-of-distribution generalized graph neural network. IEEE Trans. Knowl. Data Eng., 35(7):7328-73440 2023.
Jian Liang, Dapeng Hu, and Jiashi Feng. Do we really need to access the source data? source hypothesis transfer for unsupervised domain adaptation. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 6028-6039. PMLR, 2020.
Jian Liang, Ran He, and Tieniu Tan. A comprehensive survey on test-time adaptation under distri- bution shifts. CoRR, abs/2303. 2023.
Shikun Liu, Tianchun Li, Yongbin Feng, Nhan Tran, Han Zhao, Qiang Qiu, and Pan Li. Structural re- weighting improves graph domain adaptation. In International Conference on Machine Learning, ICMI. 2023, 23-29 July 2023, Honoludu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 21778-2179 PMLR, 2023.
Shikun Liu, Deyu Zou, Han Zhao, and Pan Li. Pairwise alignment improves graph domain adapta- tion. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024a.
12

---

Published as a conference paper at ICLR 2025
Zhining Liu, Ruizhong Qiu, Zhichen Zeng, Hyunsik Yoo, David Zhou, Zhe Xu, Yada Zhu, Kommy Weldemariam, Jingrui He, and Hanghang Tong. Class-imbalante insalanbbll graph learning without class rebalancing. In Forty-first first International Conference Machine Learning, ICML 2024, Vienna, Austria, July 21 21-27, 2024. OpenReview.net, 2024b.
Jianxin Ma, Peng Cui Kun Kuang. Xin Wang, and Wenwu Zhu. Disentangled graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 4212 4221. PMLR, 2019.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural networks? In The Tenth International Conference Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
Haitao Mao, Zhikai Chen, Wei Jin, Haoyu Han, Yao Ma, Tong Zhao, Neil Shah, and Jiliang Tang- Demystifying structural disparity in graph neural networks: Can one size fit all? In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Process- ing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
Haitao Mao, Lun Du, Yujia Zheng, Qiang Fu, Zelin Li, Xu Chen, Shi Han, and Dongmei Zhang. Source free graph unsupervised domain adaptation. In Proceedings of the 17th ACM International Conference on Web Search and Data Mining, WSDM 2024, Merida, Mexico, March 4-8, 2024, pp. 520-528. ACM, 2024.
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma. Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao B. Schardl, and Charles E. Leiserson. Evolvegen: Evolving graph convolutional networks for dynamic graphs. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY. USA, February 7-12, 2020. pp. 5363 5370. AAAI Press, 2020.
Hyeon-Jin Park, Seunghun Lee, Sihyeon Kim, Jinyoung Park, Jisu Jeong, Kyung-Min Min Kim, Jung- Woo Ha, and Hyunwoo Kim. Metropolis-hastie data augmentation for graph neural net- works. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6- 6-14, 2021, virtual. pp. 19010- 19020, 2021.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. DIMES: A differentiable meta solver for combina- torial optimization problems. In Advances in Neural Information Processing Systems 35, 2022.
Ruizhong Qiu, Dingsu Wang, Lei Ying, H. Vincent Poor, Yifang Zhang, and Hanghang Tong. Re- constructing graph diffusion history from single snapshot. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2023.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In 8th International Conference on Learning Rep- resentations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. J. Complex Networks, 9(2), 2021.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. CoRR, abs/1710. 10903, 2017.
Dequan Wang, Evan Shelhamer, Shaoteng Liu, Bruno A. Olshausen, and Trevor Darrell. Tent: Fully test-time adaptation by entropy minimization. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
13

---

Published as a conference paper at ICLR 2025
Dingsu Wang, Yuchen Yan, Ruizhong Qiu, Yada Zhu, Kaiyu Guan, Andrew Margenot, and Hang- hang Tong. Networked time series imputation via position-avye aware graph enhanced variational autoencoders. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2023a.
Jindong Wang, Cuiling Lan, Chang Liu, Yidong Ouyang, Tao Qin, Wang Lu, Yiqiang Chen, Wenjun Zeng, and Philipp S. Yu. Generalizing to unseen domains: A survey on domain generalization. IEEE Trans. Knowl. Data Eng., (5(8))80552-800) 8072, 2023b.
Mei Wang and Weihong Deng. Deep visual domain adaptation: A survey. Neurocomputing, 312: 135-153, 2018.
Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. In International Conference on Machine Learning, ICMI. 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 23341-23362. PMLR, 2022.
Yiqi Wang, Chaozhuo Li, Wei Jin, Rui Li, Jianan Zhao, Jiliang Tang, and Xing Xie. Test-time training for graph neural networks. CoRR, abs/2210.08813, 2022.
Jun Wu, Lisa Ainsworth, Andrew Leakey, Haixun Wang, and Jingrui He. Graph-structured gaussian processes for transferable graph learning. In Thirty-seventh Conference on Neural Information Processing Systems, 2023a.
Jun Wu, Jingrui He, and Elizabeth A. Ainsworth. Non-iid transfer learning on graphs. In Thirty- Seventh AAAI Conference on Artificial Intelligence, AAAI 2023, Thirty-Fifth Conference on Inno- vative Applications of Artificial Intelligence, IAAI 2023, Thirteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2023, Washington, DC, USA, February 7-14, 2023, pp- 10842-10350. AAAI Press, 2023b.
Lirong Wu, Haitao Lin. Yufei Huang, and Stan Z. Li. Knowledge distillation improves graph struc- ture augmentation for graph neural networks. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022.
Man Wu, Shirui Pan, Chuan Zhou, Xiaojun Chang, and Xingquan Zhu. Unsupervised domain adaptive graph convolutional networks. WWW '20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, pp. 1457-1467. ACM / IW3C2, 2020.
Jiaren Xiao, Quanyu Dai, Xiaochen Xie, Qi Dou, Ka- Wai Kwok, and James Lam. Domain adaptive graph infomax via conditional adversarial networks. IEEE Trans. Nefw. Sci. Eng., 10(1):35-52, 2023.
Haobo Xu, Yuchen Yan, Dingsu Wang, Zhe Xu, Zhichen Zeng, Tarek Abdelzaher, Jiawei Han, and Hanghang Tong. Slog: An inductive spectral graph neural network beyond polynomial filter. In Forty-first International Conference on Machine Learming, 2024.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmüssan, Stock- holm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 5449-5458. PMLR, 2018.
Zhe Xu, Boxin Du, and Hanghang Tong. Graph sanitation with application to node classification. In WWW '22 The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25. 29, 2022, pp. 1136-1147. ACM, 2022.
Zhe Xu, Yuzhong Chen, Qinghai Zhou, Yuhang Wu, Menghai Pan, Hao Yang, and Hanghang Tong. Node classification beyond homophily: Towards general solution. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023, Long Beach, CA, USA, August 6-10, 2023, pp. 2862-2873. ACM, 2023.
Yuchen Yan, Yuzhong Chen, Huiyuan Chen, Xiaoting Li, Zhe Xu, Zhichen Zeng, Zhining Liu, and Hanghang Tong. Thegen: Temporal heterophilic graph convolutional network. arXiv preprint arXiv:2412. 16435, 2024a.
14

---

Published as a conference paper at ICLR 2025
Yuchen Yan, Yuzhong Chen, Huiyuan Chen, Minghua Xu, Mahashweta Das, Hao Yang, and Hang- hang Tong. From trainable negative depth to edge heterophily in graphs. Advances in Neural Information Processing Systems, 36, 2024b.
Yuchen Yan, Yongyi Hu, Qinghai Zhou, Lihui Liu, Zhichen Zeng, Yuzhong Chen, Menghai Pan, Huiyuan Chen, Mahashweta Das, and Hanghang Tong. Pacer: Network embedding from posi- tional to structural. In Proceedings of the ACM on Web Conference 2024. pp. 2485-2490 2024c.
Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. In IEEE International Conferencee on Data Mining, ICDM 2022, Orlando, FL, USA, November 28- Dec.
1, 2022, pp. 1287-1292. IEEE, 2022.
Yiding Yang. Zunlei Feng, Mingli Song, and Xinchao Wang. Factorizable graph convolutional net- works. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
Zhichen Zeng, Ruike Zhu, Yinglong Xia, Hanqing Zeng, and Hanghang Tong. Generative graph dictionary learning. In International Conference on Machine Learning. pp. 40744 40769. PMLR, 2023.
Zhichen Zeng. Ruizhong Qiu, Zhe Xu, Zhining Liu, Yuchen Yan, Tianxin Wei, Lei Ying, Jingrui He, and Hanghang Tong. Graph mixup on approximate gromov-wasserste geodesics. In Forty-first International Conference on Machine Learning, 2024.
Marvin Zhang, Sergey Levine, and Chelsea Finn. MEMO: test time robustness via adaptation and augmentation. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 December 9, 2022, 2022.
Yifan Zhang, Xue Wang. Kexin Jin, Kun Yuan, Zhang Zhang. Liang Wang. Rong Jin, and Tieniu Tan. Adanpe: Exploring non-parametric classifier for test-time adaptation. In International Con- ference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii USA, volume 202 of Proceedings of Machine Learning Research, pp. 41647 41676. PMLR, 2023.
Yizhou Zhang, Guojie Song, Lun Du Shuwen Yang, and Yilun Jin. DANE: domain adaptive net- work embedding. In Proceedings of the Eighty-Egghth International Joint Conference on Ar- tificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pp. 4362-4368. ijeai.org, 2019.
Hao Zhao, Yuejiang Liu, Alexandre Alahi, and Tao Lin. On pitfalls of test-time adaptation. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 42058 42080. PMLR, 2023.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Process- ing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Jiong Zhu, Ryan A. Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K. Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Third Conference on Innovative Applications of Artificial Intel- ligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pp. 11116-111766 AAAI Press, 2021a.
Qi Zhu, Natalia Ponomareva, Jiawei Han, and Bryan Perozzi. Shift-robust gnns: Overcoming the limitations of localized graph training data. In Advances in Neural Information Processing Sys- tems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 179965279977 2021b.
15

---

Published as a conference paper at ICLR 2025
APPENDIX CONTENTS
Theoretical analysis
17
A.1
Illustration of representation degradation and classifier bias
17
A.2
Illustration of adapting
18
A.3
Proof of Proposition 3.1 and Corollary 3.2
19
A.4
Proof of Proposition
A.5
Proof of Proposition 3.4
23
A.6
Proof of Proposition 3.5
24
A.7
Generalization to multi-hop
GCNs
25
A.8
PIC loss decomposition
27
B
Convergence analysis
28
B.I
Convergence Matcha
28
B.2 Example: linear layer followed by sottmax
31
Additional experiments
32
Effect of attribute shifts and structure shifts
................................
32
Robustness to noisy prediction
32
Different levels of structure shift
................................
33
Evolving target graphs
33
Robustness to additional adversarial shift
................................
34
C.6
Ablation study with different loss functions
34
Hyperparameter sensitivity with different number of GPR steps K
.........
34
C.8
Computation time
35
C.9
Scalability
36
10
More architectures
36
D)
Reproducibility
37
D.I Datasets
37
D.2 Model architecture
38
D.3 Compute resources
38
More discussion
39
Additional related works
39
Limitations
39
Broader impacts
39
16

---

Published as a conference paper at ICLR 2025
A THEORETICAL ANALYSIS
A.1
ILLUSTRATION OF REPRESENTATION DEGRADATION AND CLASSIFIER BIAS
Degradation Only
Only
044
3,4
Pr00bbit Dredky
0-3
0.
0-2
12
0.0
3/0
Figure 7: An example of representation degradation and classifier bias. (b) Representation degrada-
tion blurs the boundary between two classes and increases their overlap. (c) Classifier bias translates the representation and makes the decision boundary sub-optimal.
Figure above visualizes representation degradation and classifier bias.
Under classifier bias, the representations are shifted to the left, making the decision boundary sub-optimal. However, by refining the decision boundary, the accuracy can be fully recovered.
Figure [))
Under representation degradation, however, even if we refine the decision boundary, the accuracy cannot be recovered without changing the node representations.
Figure b))
we can clearly conclude that attribute shifts mainly introduce classifier bias, while structure shift mainly introduce representation degradation.
Moreover, comparing Figure 7 with Figure 10
17

---

Published as a conference paper at ICLR 2025
A.2 ILLUSTRATION OF ADAPTING
In the end of subsection 3.3 we provide two examples to intuitively illustrate why the hop- aggregation parameter 7 should be adjusted based on the target graph's degree dr and homophily hy. To further demonstrate the effect of adapting 7, we visualize these examples:
TosE Class
Negalvvs Class
Decision Boundary
Target, 0.S, V5 10
Target,
Acturayy 100%
Acouary 62%
Acouary
Pobabbliy Densiay
0.01
0.06
0.04
0.02
1.
10
-10
Source.
Target,
01 Target.
Accuracy: 200%
Acourayy 87%
Acoursty 92%
Probabalty Dansiy
0.10
0.25
0.20
0.02
0.15
0.10
0.01
-20
-10
-50
-40
-20
40
-7.5
-5.0
-2.5
0.0
2.5
5.0
Node: Represontation
Node Represertation
Node Representation
Figure 8: Visualization of effect of structure shifts and adaptation of 7..
Source Graph: We consider a source graph with μ44 = L, م = - hg = 1, and dg = 10. In this case, the optimal featurizer assigns equal weight to the node itself and each of its neighbors, resulting in the optimal "s = 10. Figure S a) and (d) show the distribution of node representations on the source graph, where the two classes are well-separated.
Homophily Shift: In Figure b), the degree remains unchanged, but the homophily ht decreases to 0.5, meaning each node's 's neighbors are equally likely to belong to either class. The neighbors no longer provide reliable information for classification, introducing noise and reducing accuracy to 62%. However, in Figure 8 (c), after adjusting "/r to the optimal (2hr 1) 0, the accuracy improves significantly 84%.
Degree Shift: In Figure Me.. the homophily remains unchanged, but the degree dr de- creases to 1. The original overemphasizes the neighbors' representations, placing exces- sive weight them, leading to accuracy drop to 87%. By adjusting Yr the optimal
(2 1) = in Figure f), the accuracy improves to 92%.
18

---

Published as a conference paper at ICLR 2025
A.3 PROOF OF PROPOSITION 3.1 AND COROLLARY 3.2
Proposition 3.1. For graphs generated by CS ,-,,,,,,,, N). V/ E C+ generated by single-layer GCN follows a Gaussian distribution of
(d.d,h). the node representation 2, of node
2, ,,~ N (1 + +11 + (1)
(2)
d;
where is the degree of node vi and h; is the homophily of node vs defined Eq. results hold for U, C_ after swapping μ4 and pt..
7
Similar
Proof. For each node U; E Cc,, its representation is computed as
2: = 3 + 7 d2 Σ Øj
2yEN(NN)
The linear combination of Gaussian distribution is still Gaussian. Among the d, N(v)) neighbors of node there are h;d, nodes from C+ and (1 - h:jd, nodes from C_.. Therefore, the distribution of z;
72 21 ~ N (a+ (1+gha)a 711 ha)pe, 1 d, 1
Similarly, for each node C_, the distribution of 2, is
21 N (1+ +011- -h)pp 1+ 22 (1+ +++2) 1
Remark A.1. When 7 - xo, this proposition matches with the results in Ma et al. 2022
Notice that notation is slightly different: we the covariance matrix while they use the square root of in the multivariate Gaussian distribution.
19

---

Published as a conference paper at ICLR 2025
Corollary 3.2. When h4 M. -,, and all nodes have the same homophity h _ and
ptg
degree d N(pt-) the classifier maximizes the expected accuracy when sign(1 (201111-221111 1)) 1 and b 0. gives linear decision boundary of {z z = 0} and the expected accuracy TAlla
d Acc = Acc= (V 1)1 ||
(3)
where is the CDF of the standard normal distribution.
Proof. Given 44 μr, p -p and d; d, h4 = h, Vi, we have
24 N ( (1 (1+ 1))8:14, (1 2++2
where Yi E {+1} is the label of node 24 Given multivariate Gaussian distributions with identi- cal isotropic covariance matrix, the optimal decision boundary that maximize the expected accuracy the perpendicular bisector of the line segment connecting two distribution means, i.e.,
{= : I| - (1+ 72hh 1)) = || (1 7(2h - (-) = {= =T =00
The corresponding classifier is:
w sign(1 + 12h-
b
(10)
p |
To compute the expected accuracy for classification, we consider the distribution z w
2 w + bb N (11+ 1)1 ||el| + 22 We scale to unit identity variance,
d
(11)
d dd (z, w + ~ (Vatap 11 + +22h - 1)1 y: |114l12:
Therefore, the expected accuracy is
(v
d d dd |1h 1)1 1110/12
Acc = +
(V
(12)
where 4 is the CDF of the standard normal distribution.
20

---

Published as a conference paper at ICLR 2025
A.4 PROOF OF PROPOSITION 3.3
Proposition 3.3 (Impacts of attribute shifts). When training single-layer GCN source graph of CSBM μr, -1,, d, h), while testing on a target graph of CSBM + Ap, p + Au, h) with have
| 2 1++22h- 11
||
147
=, A - 12),
where indicates the same order, i.e., a function ((x) ( & there exists positive constants C₁,Cr C2. S.I. C₁ I Mz) < C2 for all x in its range. implies that the performance gap under attribute shifts mainly attributes to the classifier bias.
Proof. We can reuse the results in Corollary 3.2 by setting μ4 r + Apt and μ -u Ap. For each node hi we have
~ N (1+
1))a + (1 7) (1+ 2 21
Given the classifier in Corollary 3.2
we have
d
(z, w + b)
V + 72
N V d+nz 11 7(2h - 1)1 ||
V d+o2 signn1 + (2hh - 1)) (1+ cos Aplll Vus E C+
atnz |1+ 72h - 1)] |||||2+
sign(1 + 72hh 1)) (1+ cos (u, An))lAmll::1), Vuz C_
where cos cos_sim Ap) = 4 Au On the target graph, the expected accuracy is ||
1
d
d
ACCT
[1 (2h 1)1 ||1l +
+ 71 cos sim(p, Ap)ll +
VV
+ 72
V
+ -²
1
d
d
Φ 2
11 + 72h - 1)1 |114|12 - V d + 7
|1 + 7 cos sim Au)l|Au11
d x22
where + is the CDF of standard normal distribution. In order to compare the accuracy with the one
in Corollary 3.2 we use Taylor expansion with Lagrange remainder. Let 2ig = / V + 72h
1) ||al|2 and Ar
V
71 cos sim(ju, Aμ4) A/1122. The Taylor series of atzz
d 11 +
((x) at x = 2o is:
((x) ((00) + ((10)(())))))))))) Ar G' + +AA)) (Ax)?, 3X (0,
2
where p(x) = (()) -e 2 is the PDF of standard normal distribution and (c(c) (²(x))
2 is the derivative of (px)). Therefore, the accuracy gap is:
1
Aces - Acer = (xx) - +(x + Ar) 10x - Ar)
2
(50 + Arr)) + ''(200 >2Dx) (Ax)²,
iYvE A2 E (0,
We finally give lower and upper bound of ('so (22d)))))
Given |Appll2 S
4
[1+x 13] ||lle have 0 Az < Zo and thus 0 xo A2
A < 2zp-
1++
21

---

Published as a conference paper at ICLR 2025
When 0 < 50, we have constant:
V2re S (x(xx) < 0. Therefore can give an upper bound of the
(00 A1AT) (' )2Ax)
2v 2Te
and also lower bound
(' + Am) + (00 )2Aa)
40(10 + >1
max (2o) (2
4
4
Therefore, have
Accs - Accr = (((Ax))) 0(1App1
We finally derive representation degradation and classifier bias. On the target graph, the optimal classifier is,
w = sign(1++/0e
1))
b b= - - + r(2h
1)) (1 + +7) cos_sim( |
||l112
In this case, the distribution of 2; w + b will be identical to Eq. and the accuracy will be identical to Eq. (1)). It indicates that the representation degradation is 0, and Ag = (Accs
AccT) B = e A2))))
22

---

Published as a conference paper at ICLR 2025
A.5 PROOF OF PROPOSITION 3.4
Proposition 3.4 (Impacts of structure shifts). When training a single-layer GCN on source graph of CSBM (p. -u, ds, his) while testing on a target graph of CSBM( p, dr, hT), where 1 S dr ds Ad ds and < ht lig Ah his if 0, we have
A ( Ad),
=
(5)
which implies that the performance gap under structure shifts mainly altributes to the representation degradation.
Proof. Without loss of generality, consider case with y 0, 2 ho hg 1 and S dr < ds I N. In this case, decreases in both homophily and degree will lead to decreases in accuracy. Notice that our proposition can also be easily generalized heterophilic setting.
We can reuse the results in Corollary 3.2 Given 5 < hr < hg. we have sign(1 + ((hs 1)) = sign(1+ + (2hr 1)), and thus the opumal classifier we derived in Eq. (IO) remains optimal on the target graph. Therefore, we have Ag O, which means that the accuracy gap solely comes from the representation degradation. To calculate the accuracy gap, we consider the accuracy score as function of degree d and homophily h.
([a) (1]
(+== 4
d d 72
(V
72h
1)1 11111/1012
Its first order derivative is
OF
72
d 11 + 72h - 11)1-114l1 (V 7 11 + 72hh - 1)1 1|/aall
0d
2d2 (d + 222
0F
d
d (Vat 11 7(h 1)1 ||a||22
1 dd+ .27.277
27
Oh
Both partial derivatives have lower and upper bounds, the range of h E
[t. 1],d [1,N]:
OF
72
1
0d <
(1 (1+7)-11111)
2(1 + +2)
v 2m
OF
72
1
||11|12
0d
2N (N + 22)
/2T
OF
< 27
||1||2
0h
2t
OF 1
27
||1|||
ah
1 1+72
V2T
[ds] hs
Finally, to compare Accs and Accr, consider the Taylor expansion of F at
dr [r
( ds Ad hs Ah
[s VF
( [dr' (TT)
Ad Ah
r.
F
hhs
Ihs
dDh
YE (0,1)
Therefore,
Accs AccT = F [s
([trr)
F
hg
(Add + Ah)
and also A, (Aces- - ACCT) -A, -A==0(M) + Ah).
23

---

Published as a conference paper at ICLR 2025
A.6 PROOF OF PROPOSITION 3.5
In this part, instead of treating ? fixed hyperparameter (as in Proposition 3.3 and 3.4 we consider y as a trainable parameter that can be optimizer on both source and target graphs. derive the optimal for graph in Lemma
first
Lemma A.2. When training single-layer GCN graph generated from CSBM( -M, d, h). the optimal y that maximized the expected accuracy is d(2h - 1).
Proof. In Corollary 3.2 we have proved that with the optimal classifier, the accuracy is
Acc $ $ (v (V 722 1)1 11llllll2
d
We then optimize y reach the highest accuracy. Since ((x) is monotonely increasing, we only need find the y that maximize F(n) -イッ (2h 1)) Taking derivatives,
F'()) d. 2(1 7(hh 1)) (2h 1) (d+ d(1 + -(h 1))2 2
(d+
2d [1 + 72h 1)] (2h 17
(d + 7222
< 0, E (-00, 2h-1)
> 0, 7 (- 2 (2h 1)d)
< 0, 7 E ((2h 1)d, +00)
Therefore, F(7) can only take maximal at 7 (2h l)d or -0. We find that
lim F()) = (2h - 1)ad and P((2h 1)d) = 1 + (2h 1) > (2h d There-
fore, the optimal y that maximize the accuracy 7 (2h 1)d, and the corresponding accuracy
is
Acc +b (V1+ (2h 1)dd (1 1|a0122
Proposition 3.5 (Adapting 7). Under the same learning setting as Proposition 3.4 adapting the source "Is the optimal "T dy (2hg 1) the target graph alleviate the representation degradation and improve the target classification accuracy by (((A)) + (Ad)?).
Proof. As shown in Lemma
A.2
by adapting y, the target accuracy can be improved from
dr
dg + (V
11 72(2 1)1 ||a||/2 1)1-|11012
to
dr 7/ 11 (r 1)1 ||a||2| (8(1+ (2hr- 1)2d. -1/4112)
dr
Φb
(V
We know quantify this improvement. Let F(r) = +b (V Or is optimal on the target graph, we have F' F'(TT) = and 1" ("(TT) < O. Therefore, we have
ب5-ク 11 + 72h7 - 1)1 111l111ll)). since
dr
T (11 + (2hr - 1) (1mll2) ②b (v
dr
11 + 7s 1)1 || -(((r 72))
dr 7
Moreover, given 7s and or optimal on source graph and target graph, respectively, have is = 2(hg - 1)ds and "rr = 2(hr 1)dr, thereforem lyr - 7sl = O(Ah + Ad). Therefore, the accuracy improvement is @(Ah)) (Ad)²).
24

---

Published as a conference paper at ICLR 2025
A.7 GENERALIZATION MULTI-HOP GCNS
So far, our theoretical analysis has focused on single-layer GCNs and CSBM graphs, where ho- mophily and degree are used to parameterize structure shifts one-hop neighborhoods. In this section, we extend our analysis more general multi-hop scenarios.
For graph G and a node v; on the graph, we define k-hop neighbors as follows:
{wsh
k = 0
(wx) = Foy chortest-distancee 0;) = k}:
(13)
if k 2 1.
We further define
(kk)
(1)
where d!a) = |N
(14)
N
where n Hey E N! y = -4
(k)
N (k)
(15)
d(
For = 1, N corresponds to the standard definition of node neighbors, and de and h; align with node degree and homophily as defined in the main text. For l 2 2, df and h/ capture more complex structure shifts the egograph of v, For example:
(1)
If the 2-hop egograph of only contains d + 1 nodes and all nodes are fully-connected (clustering coefficient is 1), then d! ==)=0 =0.
If the 2-hop egograph of is a tree (clustering coefficient is 0) and each 1 1-hop neighbor of U; has degree d, then d(2) = d.d) (d-
This formulation allows us to model higher-order graph metrics, such as cluster coefficients, en- abling the analysis of more intricate structure shifts.
Inspired by methods like MixHop (Abu-El-Haija et al. 2019) and GPRGNN (Chien et al. 2021 consider K-hop GCN with featurizer defined as:
2,
7
Ftj.
(16)
d
()E)(k)(ss)
and the linear classifier is still x, w +
We denote 7 = (70. ... 7k]] [T] and similarly,
d = (0) d R
d. = (d
IT
(17)
h4 Proposition A.3. For graphs with two classes C+ and C_, and node attributes æ; N(p,, I) for each node Uú, where pi t4+ for E C+ and μ. -t- for E C_, the node representation z; of node Us C+ generated by a K-hop GCN follows Gaussian distribution of
h = [1)
h 1T
(18)
2i Z ((>TTh)) p4+ + (7 (1 - h.)) -p_ (Y diiag(d;)
1).
(19)
When p.+ = th, p.- -1,, and all nodes have the same d, and his the classifier maximizes the expected accuracy when an sign(y> (2h 1)) Talla and b = 0. It gives a linear decision
boundary of (z T to = 0} and the expected accuracy
(V 7T diag(d,) [|aale)
T2h 1))2
Acc = =
<ec=0((
(20)
where & is the CDF of the standard normal distribution.
Proposition A.3 is natural extension of Proposition 3.1 and corollary 3.2 from one-layer GCN to multi-hop GCN. Based on this proposition, we can similarly derive conclusions analogous to Propositions 3.3 and 3.4 in the main text.
Finally, we show that the optimal 7 should still be adapted based on d and h, reinforcing the theo- retical insights provided earlier.
25

---

Published as a conference paper at ICLR 2025
Lemma A.4. Under the same setting Proposition A.3 the optimal "y that maximized the expected accuracy is given by
Y x diag(d) 1) (2h 1),
(21)
where the element-wise multiplication. When 70- 1, this yields:
Tik = d (2h 1); 4k K,
(22)
which directly recovers the conclusion of Proposition 3.5
Proof. We aim to find that maximize the accuracy, equivalently, we optimize the following objec-
tive,
Y arg max Y (2h T(2h- 1)(2h 1
(23)
7 diag(d) 'y
Let diag(d) by, we solve
θ diag (2h 12 1) diag(d)à0
0- arg max 0
(24)
Therefore, l" is the first eigenvector of diag diag(d)=(2h, 1) 1) diag(d)=, which is 0" x diag(d) (2h - 1), and therefore " x diag (2h 1) = d @ (2h - 1).
When % 1, since ( 1, (()) = 1. we have > = d @ (2h 1).
26

---

Published as a conference paper at ICLR 2025
A.8 PIC LOSS DECOMPOSITION
Ex Yi
Notice that pec
Ve = ,,.
EN 1io0
N
2
1x 1
i=1
N
1 - 11.12
Y Zz pe pe
fel
N
c
P. - Mell2 +
Yic(z; - T - p.)) + Σ
(ME
Y 1e l - 11.11
i=1
N
N
C
1 - Mell2+ +
Mellieee - 11,11
t=1 c=
t=1
c=1
intra
+ inter
27

---

Published as a conference paper at ICLR 2025
B CONVERGENCE ANALYSIS
B.1 CONVERGENCE OF MATCHA
In this section, we give a convergence analysis of our Matcha framework. For the clarity of theo- retical derivation, we first introduce the notation used in our proof.
vec Z) RND is the vectorization of node representations, where Z NxD is the original node representation matrix, N is the number of nodes, and is the dimensionality of representations.
y = vec(YY RVC is the vectorization of predictions, where Y E RN is the original prediction of bascline TTA algorithm, given input Z, and C' is the number of classes.
h vec(H) E I is the vectorization of H, where H = MLP(X) E RNX is the (0-hop) node representations before propagation.
M = [ve (HH),, ....... vec( Á H)) E RNDx(K+1) is the stack of O-hop, 1-hop to K'-hop representations.
Y IK++1 is the hop-aggregation parameters for O-hop, 1-hop to K-hop representations. Notice that My =
copy
2TTA
- stop-grad
M
((i,7rc)) L(x)
ZPIC
Figure 9: Computation graph of Mat cha
Figure gives a computation graph of Mat cha.
In the forward propagation, the node representation is copied into two copies, one (2TTx) is used as the input of BaseттA to obtain predictions y. and the other (ZPIC) is used to calculate the PIC loss.
In the backward propagation, since some baseline TTA algorithms do not support the eval- uation of gradient, we do not compute the gradient through 2T1A, and only compute the gradient through ztear- This introduces small estimation errors in the gradient, and thus introduces the challenge of convergence.
We use
OC(z)
dÿ Öl(ÿ, ZPIc) Oğ
ØE(g. ZPic)
V T()
0z
δzTTa
Ozpic
to represent the "true" gradient of that consider the effects of both ZITA and ZPic- Meanwhile, we use
dE(ğ, ZPIC)
Spc Zric
Ózpic
to represent the update direction of cha.
Clearly, the convergence of Matcha depends on the property of the baseline TTA algorithm BaseTTA. In the worst scenario, when the BaseTTA is unreliable and makes completely differ- ent predictions in each epoch, the convergence of Mat cha could be challenging. However, in the more general case with mild assumptions the loss function and baseline TTA algorithm, we show that Matcha can guarantee to converge. We start our proof by introducing assumptions.
Assumption B.1 (Lipschitz and differentiable baseline TTA algorithm). The baseline TTA algo- rithm BaseTTA IRN2 + N is differentiable and L Lipschht on Z, i.e. there exists constant Li, S.t, for any 21, z2 E Z, where Z N the range of node representations,
[| BaseTTA(Zz)
La
|| 22|12
28

---

Published as a conference paper at ICLR 2025
Assumption B.2 (Lipschitz and differentiable loss function). The loss function {(U, zric): : RND x RND + R is differentiable and L2- -ipisccchitz on V. i.e., there exists a constant L2, s.t., for any 3r, 02. V/, where Y C CRDD is the range of node predictions,
[ ZPIC) l(z,, zrIc)]l2 S l22 l 92112
Remark B.3. Assumption B. indicates that small changes in the input of TTA algorithm will not cause large change in its output, while Assumption [B.2 indicates that small changes in the predic- tion will not significantly change the loss. These assumptions describe the robustness of the TTA algorithm and loss function. We verify in Lemma that standard linear layer followed by softmax activation satisfies these assumption.
Definition B.4 (6-smoothness). A function f R- + E is 3-smooth if for all x, E R
[[] V { S B| vll2
equivalently, for all æ, y E RR
f(y) S f(z) + ff(x) 2) + 2-1 || y1
Assumption B.5 (Smooth loss function). The loss function [(z): RND + R is 3-smooth to
Remark B.6. Assumption B.5 is a common assumption in the analysis of convergence (Bubeck)
2013).
Lemma B.7 (Convergence of noisy SGD on smooth loss). For any non-negative L-smooth loss function ((w) with parameters w, conducting SGD with noisy gradient g(w) and step size 1 = t If the gradient estimation error ( w (0), after T steps.
lel A² sor all w. then any weight initialization
T-1
())
11
3 s
(1 (0)) + +
I
T 1=
Proof. For any (!!)
[(w((+1)) s ((w(()) + V[(w(0)] (w - z0()) (2()) + L
( -w00 (L-smoothness)
2
(0) ()) [- (0(20(0) -V +V((co))))]
+ L
|| -1 ()( (06(0))v/40 ( + V /12
2 =L(wo(0)+
LIp
-
11= + *(To² - n) V(((o(1)) ((co01))V(((()
2
+ Tmp
)))
1
1|=
2
1
|((eo - \V
(1= +
+ 2L
2L
Equivalently,
1|2 < 2L (C(w(()) - ((w0(+t))) + -
2
())
2
Average over t = 0, 0.... ... T 1, we get
vL (L( )1)
11: s 2 L (C(vol0)) ((vo())))
+ - Σ
(( v(( /
1=
1 <(w +
L c(w
Σ
(((eo(0) vC(
7
< 2 L
29

---

Published as a conference paper at ICLR 2025
Lemma B.7 gives general convergence guarantee of noisy gradient descent smooth functions. Next, in Theorem B.8. we give the convergence analysis of Mat cha.
Theorem B.8 (Convergence of Matcha). With Assumption 7(0) and conduct steps of gradient descent with V smv (ÿ) ZPIC) and step size BMM we have
and B.5 held, if we start with
T-1 T
2 2 T ||
M 1 (() + 1 $
Proof. We first give an upper bound of the gradient estimation error
V amc ZPIC) Vz Spic)]l2
| xTTA
(ÿ. #PIC)
dÿ Ōl(g, #PIC)
θztTa
2
Oÿ
(ū ZPIC)
l
θ2TTA
1.2
(Assumption
B. B.2
Therefore, the gradient estimation error can be bounded by L1 L2 |M|2
Meanwhile, since the loss function is 9-smooth w.r.t. z, is 3 || M -msoooh to since
[v(((m) V,((2))l = |M T (V [(7) V 22, ((r))ll
$ M ll 3 ||| 22 l2
< M 1 3- Il 7/2 l2
Finally, by Lemma B.7 we have
T
)()()()))
1/
2
M 12 [(> (0)) + 13
30

---

Published as a conference paper at ICLR 2025
B.2 EXAMPLE: LINEAR LAYER FOLLOWED BY SOFTMAX
Lemma B.9. When using linear layer followed by a softmax as the BaseTTa, the function Zpic), as a function of ZTTA, is Lippsshi,,,,, where W is the weights for the linear layer.
Proof. We manually derive the gradient of É ZPic) w.r.t. TTTA. Denote E RNC as the out- put of the linear layer, a, as the linear layer output for the i-th node, and aie its e-th element (corresponding to label c). We have:
de daie
Σ c'=1
OY de
daic
OY
(&,c
V22 1,0!
|| Mell
Σ
2 Me
11
N
|| 14.11
2i=1 ||
pe. 113
s=1
e'cc
Yic 22
Mcl
22
Yi. Σe
Ki,c/ ||
Me 11
Σ 1=1
||
11112
Σ
2|
112
Therefore, as vector representation:
de
Y ž Me 1
Y 2 Me
+
1 1.0
aa
|| ue 12
|| M
12
iil
1.0
Fiml
Yel 2 - Mell2
Yioo
||
Me
Y
i=l || p 12
Mu ii ||
12
4.0
4,0
DC -= Yr,c || 2
1el13
N C
YIc
Le'=1
Yr.e ||
M
11
Σ ||2 Mx 112
E || 11.11 113
Σ c= Yicll 1ell1
Σ ====
Yr,e |zi - -Morl 1/
Σ/ 22 -1ta 11a112
|| 14 112
i=
2 inttra
x²
2
Notice that although the computation of He also uses Yi...
00
Yeo -2;) = 0
0pc d²
1=1
So there are no back propagating gradients through & - pe - Pio.
Finally, because for each node U/ a; W ZTTA, we have
ae
de Da 2
ll2
2 W112
θ2TTA
Remark 10 Lemma B.9 verifies assumption B.1 and B.2: L1 L2 W/2.. It also reveals the benefit of using soft-predictions instead of hard hard-predictions. Hard predictions can be seen as scaling up W. In this case, the Lipschitz constant will be much larger or even unbounded, which impedes the convergence of Matcha.
31

---

Published as a conference paper at ICLR 2025
C ADDITIONAL EXPERIMENTS
C.I EFFECT OF ATTRIBUTE SHIFTS AND STRUCTURE SHIFTS
We empirically verify that attribute shifts and structure shifts impact the GNN's accuracy target graph in different ways. We use t-SNE to visualize the node representations on CSBM dataset under attribute shifts and structure shifts (homophily shifts), As shown in Figure [0 under attribute shift (c), although the node representations are shifted from the source graph, two classes are still mostly discriminative, which is similar the without distribution shifts (c). However, under homophily shift (d), the node representations for two classes mix together. These results match with
theoretical analysis in Propositions 3.3 and 3,4
Source
Cistribution
Altribute
Torast, Structure
Figure 10: t-SNE visualization of node representations on CSBM dataset.
C.2 ROBUSTNESS TO NOISY PREDICTION
Matcha, representation quality and prediction accuracy mutually reinforce each other throughout the adaptation process. A natural question arises: if the model's 's predictions contain significant noise before adaptation, can Mat cha still be effective? To address this, we conducted an empirical study on the CSBM dataset with severe homophily shift. We visualize the logits distribution for two classes of nodes in Figure 11
Before adaptation, the predictions exhibit significant noise, with substantial overlap in the logits of two classes.
However, as adaptation progresses, Mat cha is still able to gradually refine the node repre- sentations and improve accuracy.
Decition
Portivve Cless
Meçaltae
Before
After Adaptation
After Acaptation
After Acsptation
0.25
0.93
FIC kSS 0.91
PC 1ops 986
0.70
0.79
Protasllyy Deentyy
0.25
0.20
5,15
5.20
2.15
5.12
0.20
0.55
0,05
0.00
Leghts
Ligis
Logis
Log
Figure 11: Matcha improves accuracy even when the initial predictions are highly noisy
32

---

Published as a conference paper at ICLR 2025
C.3 DIFFERENT LEVELS OF STRUCTURE SHIFT
In the main text, we evaluated the performance of Matccha under both homophily and degree shifts. In this section, we extend our evaluation by testing Mat across varying degrees of these structure shifts. For each scenario (e.g., homophily; homo + hetero, hetero + homo, and degree: high + low, low - high), we manipulate either the homophily or degree of the source graph while keeping the target graph fixed, thereby creating different levels of homophily degree shifts. The larger the discrepancy between the source and target graphs in terms of homophily or degree, the greater the level of structure shift. For instance, shift from 0.6 0.2 indicates training a model on source graph with homophily 0.6 and evaluating it on a target graph with homophily 0.2. By comparison, a shift from 0.8 0.2 represents more substantial homophily shift.
The results of our experiments are summarized in Tables 3 and 4 Across all four settings, as the magnitude of the structure shift increases, the performance of GNNs trained using ERM declines significantly. However, under all settings, Mat cha consistently improves model performance. For example, in the homo + hetero setting, when the homophily gap increases from 0.4 (0.6 0.2) to 0.6 (0.8- 0.2). the accuracy of ERM-trained models decreases by over 16%, while the accuracy of models trained with Matcha declines by less than 2%. This demonstrates that Ma cha effectively mitigates the negative impact of structure shifts on GNNs.
Table 3: Accuracy (mean + s.d. %) on CSBM under different levels of homophily shift
homo betero
betero homo
Method
0.4
0.6
0.8
0.2
0.4
0.6
ERM
90.05 + 0.15
82.51 + 0.28
73.62 + 0.44
76.72 + 0.89
83.55 + 0.50
89.34 + 0.03
Xatcha
90.79 + 0.17
89.55 + 0.21
89.71 + 0.27
90.68 + 0.26
90.59 + 0.24
91.14 = 0.17
Table 4: Accuracy (mean + s.d. %) on CSBM under different levels of degree shift
high - low
low - high
Method
5
10 2
20 - 2
2 20
5 20
10 20
FRM
88.67 +: 0.13
86.47 +: 0.38
85.55 +: 0.12
93.43 + 0.37
95.35 +: 0.84 97.24 = 1.11
97.31 4: 0.36 97.89 + 0.25
+ Xatcha
88,78 + 0.13
88.55 + 0.44
88.10 + 0.21
97.01 = 1.00
C.4 EVOLVING TARGET GRAPHS
Our experiments in the main text mainly focused on adapting to a single target graph with a stable distribution. In this section, we test Matcha shifts. Specifically, we used the Syn-Cora dataset, where the model was pre-trained on a source graph with homophily of 0.8. It was then sequentially adapted five target graphs with ho- mophilies of 0.1, 0.7, 0.3, 0.9, and 0.2, simulating continuously changing homophily. The ex- perimental setup, except for the sequence of target graphs, was identical to that the Syn-Cora experiments described in the main text.
stream of target graphs with evolving structure
For example, in the column corresponding to the target graph with homophily of 0.3, we compared two scenarios: (I) static: directly adapting from h = 0.8 to h = 0.3, and (2) evolving: sequentially adapting through (h- 0.8) + (h 0.1) - (h- = 0.7) > (h- 0.3).
Table 5: Accuracy (mean + s.d. %) on Syn-Cora with static target graph and evolving target graph
Target graph
Setting
Method
h = 0.1
h = 0.7
h = 0.3
h = 0.9
à = 0.2
Static
ERM
63.19 1.28
88.88 + 0.61
71.46 + 0.62
97.15 = 0.32
65.67 + 0.35
Static
Matcha
79.75 1: 1.04
90.57
1 0.47
79.68 1 0.73
97.40
0.28
78.96 1 1.08
Evolving
Matcha
79.75
1.04
90.65
0.33
77.43 1:433000 0.62
97.31 0.42
78.26
1.02
The results, shown in Table indicate that Matcha achieves performance on evolving graphs highly comparable to that on static graphs. This demonstrates Matcha 's ability to handle dynamic scenarios effectively, even under continuously changing graph structures.
33

---

Published as a conference paper at ICLR 2025
C.5 ROBUSTNESS TO ADDITIONAL ADVERSARIAL SHIFT
While Matcha primarily targets natural structure shifts, inspired by (Jin et al. 2023). we test the robustness of Mat cha against adversarial attacks by applying the PR-BCD attack (Geisler et al.) 2021 on the target graph in our Syn-Cora experiments, varying the perturbation rate from 5% to 20%. The results are shown in Table 6 We found that while the accuracy of ERM dropped by 20.2%, the performance of Matcha only decreased by 2.3%. This suggests that algorithm has some robustness to adversarial attacks, possibly due to the overlap between adversarial attacks and structure shifts. Specifically, we observed decrease in homophily in the target graph under adversarial attack, indicating a similarity to structure shifts.
Table Accuracy (%) on Syn-Cora with additional adversarial shift
Perturhation rate
No attack
5%
10%
15%
20%
ERM
65.67
60.00
55.25
50.22
45.47
+ MaLcha
78.96
78.43
78.17
77.21
76.61
Homophily
0.2052
0.1923
0.1800
0.1690
0.1658
C.6 ABLATION STUDY WITH DIFFERENT LOSS FUNCTIONS
We compare our proposed PIC loss with two existing surrogate losses: entropy (Wang et al. 2021 and pseudo-label (Liang et al. 2020 While PIC loss use the ratio form of figir and Ti also compare it with a difference form intr Oiter which also encourage larger Titer and smaller o The results are shown Table 7 scenarios.
Our PIC loss has better performance under four structure shift
Table 7: Accuracy (mean + s.d. %) on CSBM with different losses.
Homophily shift
Degree shift
Loss
homo + betero
betero - homo
high + low
low
high
(None)
73.62 +: 0.44
76.72 + 0.89
86.47 +: 0.38
92.92 + 0.43
Entropy
0.68
86.81
93.75
Pseudol ahel
77.29 +: 3.04
89.44 + 0.22
86.72
+ 0.31
93.68
4 0.69
76.10 +: 0.43
72.43 + 0.65
82.56 + 0.99
92.92
+ 0.44
(Ours)
0.27
90.68 0.26
88.55 + 0.44
93.78 + 0.74
C.7 HYPERPARAMETER SENSITIVITY WITH DIFFERENT NUMBER OF GPR STEPS K
Although the Matcha does not involve any hyperparameters other than the learning rate and number of adaptation rounds 7', may be combined with GNN models with different dimension of Therefore in this part, we combine Matcha with GPRGNN models using different K. i.e., the number of GPR steps, test the robustness to different hyperparameter selection of the GNN model. Specifically, we tried values of К ranging from 3 to 15 on Syn-Cora and Syn-Products datasets. Notice that in our experiments in 5.1 we use K 9. As shown in Table g Matcha remains effective under a wide range of K.
Table 8: Hyperparameter sensitivity of K
K
Dataset
Method
11
Syn-Cora
ERM
64.18 ::8::00 0.72
65.69
+ 0.88
66.01 + 0.89
65.67
+ 0.35
65.36
0.66
64.47
1.54
6491
0.97
Natcha
81.35 + 0.64
80.13
0.59
79.50 0.72
78.96 +: 1.08
78.42 = 0.85
78.60 + 081
77.92
0.87
ERM
42.69
1.03
41.86
2.11
39.71
2.75
37.52
2.93
35.06
2.27
33.17
+
35.57 0.55
Syn-Products
Natcha
72.09 1: 0.50
71.42 1: 0.65
70.58 + 1.01
69.69 1 1.06
69.48 + 1.16
69.35 + 0.66
69.72 1 0.70
34

---

Published as a conference paper at ICLR 2025
C.8 COMPUTATION TIME
Due to the need to adapt hop-aggregation parameters y, Matcha inevitably introduces additional computation costs, which vary depending on the chosen model, target graph, and base TTA algo- rithm. We documented the computation times for each component of ERM + Matcha and T3A Matcha in our CSBM experiments:
Intial inference involves the time required for the model's first prediction on the target graph, including the computation of O-hop K-hop representations (H()).... H())), their aggregation into = Σ Ni. H (k), and prediction using a linear layer classi- fier. This is also the time required for direct prediction without any adaptation. { [H H() is cached the initial inference.
Adaptation (for each epoch) accounts for the time required for each step of adaptation after the initial inference, and includes four stages:
Forward pass involves calculation of Z using the current 7 and cached H ((()) and prediction using the linear layer classifier (or with T3A al- gorithm). Since Matcha only updates 7, ( ..... HHK) can be cached without recomputation in each epoch. Note that other TTA algorithms could also adopt the same or similar caching strategies.
Computing PIC loss involves calculating PIC loss using node representations Z and the predictions Y.
Back propagation computes the gradients with respect to y. Similarly, as only y is updated, there no need for full GNN back propagation. Updating parameters, i.e., Y with the computed gradients.
Table 9: Computation time on CSBM
Method
Stuge
Computation (ms)
Additional computationn time
Initial Inference
27. 67.687 0.413
GTrans
Adaptation (for each epoch)
134.457 +: 2,478
485.60
SOGA
Adaptation (for each epoch)
68.500 1: 13.354
247.419%
Adaptation (for each epoch)
3.292 0.254
11.89%
Forward pass
1.224 1: 0.131
4.42%
Xatcha
Computing PIC
2.76%
Back propugation
1.189 1: 0.131
4,30%i
Updating parameter
0.41%
Adaptation (for each epoch)
6.496 1: 0.333
23.46%
Forward pass
4.464 0.248
16. 12%
T3A + Matcha
Computing PIC loss
0.743 = 0.011
2.68%
Back-propanttion
4.24%
Updating parameter
0.115 0.004
0,41%
We provide the computation time for each stage in Table 9 above. While the initial inference time 27.689 ms, each epoch of adaptation only introduce 3.292 ms (6.496 ms) additional computation time when combined with ERM (T3A), which is only 11.89% (23.46%) of the initial inference. This superior efficiency comes from (1) Mat cha only updating the hop-aggregation parameters and (2) the linear complexity of our PIC loss.
We also compare the computation time of Matcha with other graph TTA algorithms. A significant disparity is observed: while the computation time for each step of adaptation in other graph TTA algorithms is several times that of inference, the adaptation time of our algorithm is merely 1/9 (1/4) of the inference time, making it almost negligible in comparison.
35

---

Published as a conference paper at ICLR 2025
C.9 SCALABILITY
In the end of Section we show the computational complexity of Matcha is linear to the num- ber of nodes. To further validate this, we have conducted experiments on graphs of varying sizes from million to 10 million nodes, and record the computation time for each epoch of adaptation. The results confirm that the computation time for Mat cha indeed scales linearly with graph size, demonstrating its efficiency even for very large graphs.
Computation Time Matcha Imean
Computatio
6
10
Number of Nodes (million)
Figure 12: Scalability of Mat
C.10 MORE ARCUITECTURES
Besides GPRGNN (Chien et al. 2021), our proposed Matcha framework can also be integrated to more GNN architectures. We conduct experiments Syn-cora dataset with three additional GNNs: APPNP (Klicpera et al. 2019), JKNet (Xu et al. 2018), and GCNII (Chen et al. 2020).
For APPNP, adapt the teleport probability
For JKNet, each intermediate representations.
weighted average the layer aggregation, and adapt the weights for
For GCNII, we adapt the hyperparameter aj for each layer.
Notice that Tent can only be applied models with batch normalization layers, which are included for JKNet in GCNII in our implementation.
Table 10: Accuracy (mean + s.d.) Syn-Cora with different GNN architectures
Method
GPRGNN
APPNP
JKNet
GCNII
ERM
65.67 1 0.35
70.24 1 0.88
47.87 1. 0.90
67.95 1. 1.33
+ Matoha
78.96 + 1.08
80.63 + 0.35
51.57 +: 2.09
74.33 + 0.45
T3A
68.25 1: 1.10
70.98 1. 0.86
47.93
1 0.85
68.20 à: 1.31
+ Matcha
78.40 +:
51.84 +
74.96 +
Tent
66.26 1: 0.38
70.15 1: 1.08
+
78.87
AdaNPC
67.34 +
70.53 +
47.93 + 0.77
68.39 + 1.18
Matcha
77.45 = 0.62
80.11 + 0.61
48.32 + 0.69
74.44 = 0.35
GTrans
68.60 + 0.32
73.50 + 0.62
51.38 + 0.58
74.08 + 1.26
+ Matcha
83.49 + 0.78
85.17 + 0.43
53.76 =: 2.26
80.30 + 0.40
SOGA
67.16 - 0.72
78.62 + 0.48
47.96 + 0.55
66.87 + 1,50
+ Matcha
79.03 = 1.10
80.88 + 0.56
52.05 + 1.64
74.39 + 0.29
GraphPatcher
63.01 + 2.29
$7.49 + 1.83
45.38 + 1.00
67 07.05 + 1.54
Matcha
80.99
81.38
46.78
74.46
The result are shown in Table 10 above. Although different GNN architectures result in different performance on the target graph, Matcha can consistently improve the accuracy. It shows that Match cha is compatible with a wide range of GNN architectures.
36

---

Published as a conference paper at ICLR 2025
D REPRODUCIBILITY
In this section, we provide details on the datasets, model architecture, and experiment pipelines.
D.1 DATASETS
We provide more details on the datasets used in the paper, including CSBM synthetic dataset and real-world datasets (Syn-Cora (Zhu et al. 22020, Syn-Products (Zhu et al. 2020). Twitch-E (Rozem- (0200).
berezki et al. 2021). and Orxiv (Hu
CSBM (Deshpande al. 2018 We use N 5, 000 nodes both source and target graph with vB 1D. f = 0.03 vD 1D, and Au
2, 000 features. Let μ
0.03
0.02
vB 1p-
- -For homo + hetero, we conduct TTA between CSBM( ,e_d = 5, 0.8) and h 0.2).
CSBM
- For low + high, we conduct TTA between CSBM = 2, h = 0.8) and
CSBM --: 10, 0.8).
When there are additional attribute shift, we use 14, on the source graph, and replace them with μ4+ + Au, μ + Au on the target graph.
Syn-Cora (Zhu al. 2020) and Syn- Syn-Products (Zhu al. 2020) are widely used datasets to eval- uate model's ss capability in handling homophly and heterophily. The Syn-Cora dataset is generated with various heterophily ratios based on modified preferential attachment process. Starting from empty initial graph, new nodes are sequentially added into the graph to ensure the desired heterophily ratio. Node features are further generated by sampling node features from the corre- sponding class in the real-world Cora dataset. Syn-Produe Con-Products generated in similar way. For both dataset, we use
0.8 as the source graph and non-overlapping train-test split nodes on Syn-Cora to avoid label leakage.
0.2 as the target graph. We use
Twitch-E (Rozemberczki et al. 2021) is set of social networks, where nodes are Twitch users, and edges indicate friendships. Node attributes are the games liked, location and streaming habits of the user. We use 'DE' as the source graph and 'ENGB' as the target graph. We randomly drop a subset of homophily edges on the target graph to inject degree shift and homophily shift.
OGB-Arxiv (Hu et al. (2200) ARXIV papers and edges are citations between these papers. Node attributes indicate the subject each paper. We use subgraph consisting
paper citation network of ARXIV papers, where nodes are
papers from 1950 to 2011 as the source graph, 2011 2014 as the validation graph, and 2014 to 2020 the target graph. Similarly, randomly drop a subset of homophily edges on the target graph to inject degree shift and homophily shift.
Table 11: Statistics of datasets used in our experments
Dataset
Partition
#Nodes
#Edges
#Feetures
#Classes
Avg. degree
Nade homaphily h
source validation
0.8
Syn
2,968
1,433
target
0.2
0.8
Syn-Products
validation
10,000
59,648
100
10
11.93
0.4
target
0.2
source
76,569
Twitch-E
validation
4,648
15,588
3,170
2
6.71
0,183
larget
7.126
9,802
2.75
0.139
saurce
17,401
15,830
1.82
0.383
OGB-Arxiv
validation
18,436
128
target
169.343
251,410
2.97
0.130
37

---

Published as a conference paper at ICLR 2025
D.2 MODEL ARCHITECTURE
For CSBM, Syn-Cora, Syn-Products, we use GPRGNN with K = 9. The featurizer is linear layer, followed by batchnorm layer, and then the GPR module. The classifier a linear layer.
The dimension for representation is 32.
For Twitch-E and OGB-Arxiv, we use GPRGNN with K = 5. The dimension for representation 8 and 128, respectively.
More architectures. For APPNP, we use similar structure as the GPRGNN, while adapt the a for the personalized pagerank module. For JKNet, we use 2 layers with 32-dimension hidden representation. We adapt the combination layer. For GCNII, we use layers with 32-dimension hidden representation, and adapt the ag for each layer.
D.3 COMPUTE RESOURCES
We single Nvidia Tesla V100 with 32GB memory. However, for the majority of our experiments, the memory usage should not exceed 8GB. We switch to Intel(R) Xeon(R) Gold 6240R CPU @ 2.40GHz when recording the computation time.
38

---

Published as a conference paper at ICLR 2025
E MORE DISCUSSION
E.1
ADDITIONAL RELATED WORKS
Graph neural networks (GNNs) have shown great success in various graph applications (Kipf &
Welling 2017 Velickovic et 2017 Rozemberezki et al. 2021 Qiu et al., 2022 2023 Hu al.
2020 Wang et al., 2023a Pareja et al. 2020). In Section 2 we briefly introduced selected related
works in test-time adaptation and graph domain adaptation. Here with discuss more related works in test-time adaptation, graph out-of-distribution generalization, and homophily adaptive GNN mod-
els.
More test-time adaptation. Another important category of TTA algorithms, beyond those dis- cussed in the main text, leverages data augmentation (Ding et al., 2022. Fu et al. 2023). These methods apply multiple augmentations to the input and enhance prediction robustness through tech- niques such as ensembling (Hendrycks et al., 2020) or minimizing marginal entropy (Zhang et al, 2022). In the context of graphs, augmentation can also be utilized for test-time adaptation (Xu al.
2022 Liu et al. 2024b Zeng et al., 2024). For instance, GTrans (Jin et al.] (023) and DropEdge (Rong al. 2020) employ augmentation strategies for this purpose. GTrans adopts DropEdge as an augmentation technique and incorporates a contrastive loss that maximizes the similarity between original nodes and their augmented views while penalizing their similarity to negative samples. However, augmentation-base approaches inevitably introduce significant additional computational costs.
Graph out-of-distribution generalization (graph OOD) aims to train a GNN model on the source graph that performs well on the target graph with unknown distribution shifts <Li et al.] 2022a). Existing graph OOD methods improve the model generalization by manipulating the source graph (Park et al. 2021 Wu et 2022). designing disentangled (Ma et al. 2019 Yang et al. 2020 Yan et al. 2024c Zeng al., (023) sasuality-based (Li et al., [023] Fan al. 2024) models, and exploiting various learning strategies (Li ct al. 2022b Zhu et al. 2021b) However, graph OOD methods focus learning universal model source and target graphs, while not addressing model adaption to a specific target graph.
Homophily and heterophily. Most GNN models follow the homophily assumption that neigh- boring nodes tend to share similar labels (Kipf & Welling
2017] Velickovi et al.) 2017: Yan et al.]
2024a). Various peessage-passingg (Wang & Zhang] 2022 Zhu al.) 2021a] Xu et al. 2024 Yan et al. 2024b) and aggregation (Chien et al. [202]] Bo et al. [021] et al. 2020 Xu et al. 2018
2023 paradigms have been proposed extend GNN models to heterophilic graphs. These GNN structures often embrace additional parameters, e.g., the aggregation weights for GPRGNN (Chien al., 202T and H2GCN (Zhu et al. 2020), to handle both homophilic and heterophilic graphs. Such parameters provide the flexibility we need to adapt models to shifted graphs. However, these methods focus on the model design to handle either homophilic or heterophilic graph, without con- sidering distribution shifts.
E.2 LIMITATIONS
Assumption source model. Since mainly focus the challenge of distribution shifts. Our proposed algorithm assumes that the source model should be able to learn class-clustered rep- resentations the source graph, and should generalize well when there are distribution shifts. In applications with extremely low signal-to-noise ratio, our algorithm's 's improvement in accuracy might not be guaranteed. However, we would like point out that this is a challenge faced by almost all TTA algorithms (Zhao et al. (223)..
Computational efficiency and scalability. Our proposed algorithm introduce additional computa- tional overhead during testing. However, we quantify the additional computation time: it is minimal compared the GNN inference time. Also, Matcha is much more efficient that other graph TTA methods.
E.3 BROADER IMPACTS
Our paper is foundational research related to test-time adaptation graph data. It focus node classification as an existing task. We believe that there are no additional societal consequence that must be specifically highlighted here.
39


Reviews:
[{"review_id": "f4ujaucrlY", "reviewer": "Reviewer_jAsf", "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.", "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?\n\n2. 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?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "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. \n\n2. 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.\n\n3. 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. \n\n2. 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. \n\n3. 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.  \n\n4. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aQOX6FVWaU", "reviewer": "Reviewer_eWx1", "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.", "questions": "See weakness.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\nThe 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:\n\n- 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?\n\n- 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YtPoc1nawf", "reviewer": "Reviewer_qcfU", "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.", "questions": "- Can AdaRC be adapted to handle continuously evolving graphs where node connectivity changes over time?\n\n- How does the computational efficiency of AdaRC scale when applied to graphs with millions of nodes?\n\n- Could PIC loss performance be enhanced by integrating more robust initialization methods for pseudo-labeling in low-confidence scenarios?\n\n- Does the framework support automated tuning of hop-aggregation parameters across different GNN architectures, or would manual tuning be required for optimal results?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\n- 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.\n\n- 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.\n\n- 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.\n\n- 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.\n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gcRpUTlPp5", "reviewer": "Reviewer_KHid", "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.", "questions": "see weakness", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\n2. 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.\n\n2. 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.\n\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZXT3JwaApv", "reviewer": "Reviewer_M4v2", "summary": "[Update]\nThanks for the authors'  feedback. My concerns have been addressed. I raised my vote accordingly.\n\nThe 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.", "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?", "limitations": "", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* Propose a novel loss (PIC loss) to improve the robustness of learned graph embedding when structure shifting is presented.\n* The algorithm comes with theoretical guarantees, although I did not check the correctness of the proof.\n* 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.\n\n* 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)