Test-time Adaptation on Graphs via Adaptive Subgraph-based Selection and Regularized Prototypes
Authors: Yusheng Zhao
Qixin Zhang
Xiao Luo
Junyu Luo
Wei Ju
Zhiping Xiao
Ming Zhang
Venue: ICML 2025 poster (2025)
Keywords: test-time adaptation
graph neural networks
Primary area: general_machine_learning->transfer_multitask_and_metalearning
TL;DR: This paper explores a novel yet under-explored problem of test-time adaptation on graphs and proposes a novel method named Adaptive Subgraph-based Selection and Regularized Prototype Supervision (ASSESS) to solve the problem.

Abstract: Test-time adaptation aims to adapt a well-trained model using test data only, without accessing training data. It is a crucial topic in machine learning, enabling a wide range of applications in the real world, especially when it comes to data privacy. While existing works on test-time adaptation primarily focus on Euclidean data, research on non-Euclidean graph data remains scarce. Prevalent graph neural network methods could encounter serious performance degradation in the face of test-time domain shifts. In this work, we propose a novel method named Adaptive Subgraph-based Selection and Regularized Prototype Supervision (ASSESS) for reliable test-time adaptation on graphs. Specifically, to achieve flexible selection of reliable test graphs, ASSESS adopts an adaptive selection strategy based on fine-grained individual-level subgraph mutual information. Moreover, to utilize the information from both training and test graphs, ASSESS constructs semantic prototypes from the well-trained model as prior knowledge from the unknown training graphs and optimizes the posterior given the unlabeled test graphs. We also provide a theoretical analysis of the proposed algorithm. Extensive experiments verify the effectiveness of ASSESS against various baselines.

Test-time Adaptation on Graphs via Adaptive Subgraph-based Selection and Regularized Prototypes
Yusheng Zhao Qixin Zhang?
Xiao Luo #3
Junyu Luo'
Wei Ju
Zhiping Xiao #4 Ming Zhang
Abstract
1. Introduction
Learning from non- non-Euclidean graph-structured data has re- cently received increasing attention, with wide range of applications in knowledge graph representation learning (Chen et al., 2020; Xu et al., 2020), social network analysis (Fan et al., 2020; Singh et al., 2024), molecular property prediction (Godwin et al., 2021; Cai et al., 2022; Stärk et al., 2022), novel drug discovery (Jiang et al., 2021; Bongini et al., 2021), 1. and traffic flow forecasting (Zhao et al., 2023; Ju et al., 2024b). Graph neural networks (GNNs) (Kipf & Welling, 2017: Hamilton et al., 2017; Veličković et al., 2018) have achieved promising performance on learning rep- resentations on graph-structured data via message passing, Subsequently, graph-level features are obtained by pooling operations, enabling a plethora of downstream tasks.
Test-time adaptation aims to adapt well-trained model using test data only, without accessing training data. It a crucial topic in machine learning, enabling a wide range of applications in the real world, especially when comes to data privacy. While existing works on test-time adaptation primarily focus on Euclidean data, research non-Euclidean graph data remains scarce. Prevalent graph neural network meth- ods could encounter serious performance degra- dation in the face of test-time domain shifts. In this work, we propose a novel method named Adaptive Subgraph-bai based SElection and Regular- ized Prototype SuperviSion (ASSESS) for reli- able test-time adaptation on graphs. Specifically, to achieve flexible selection of reliable test graphs, ASSESS adopts an adaptive selection strategy based on fineigraiedd individual-level subgraph mutual information. Moreover, to utilize the in- formation from both training and test graphs, AS- SESS constructs semantic prototypes from the well-trained model as prior knowledge from the unknown training graphs and optimizes the pos- terior given the unlabeled test graphs. We also provide a theoretical analysis of the proposed al- gorithm. Extensive experiments verify the effec- tiveness of ASSESS against various baselines.
Despite their superior performance, GNNs mostly assume that test graphs come from the same distribution training graphs, which is often violated in real-worke scenarios (Gui et al., 2022). Distribution shifts during test time are often inevitable, and some prior works (Wu et al., 2020; Zhang et al., 2021b; Yin et al., 2022; Liu et al., 2024) investigate the problem of unsupervised graph domain adaptation that attempt transfer the knowledge from the labeled training graphs unlabeled test graphs via domain discrepancy min- imization. However, these methods typically require labeled source graphs to perform domain alignment, which is of- ten impractical when facing data privacy issues (Tan et al., 2023). a common practice for institutions to disclose their pretrained models for downstream tasks, while keeping the training dataset private. Towards this end, this paper investigates a more realistic yet under-explored problem of test-time adaptation graphs, which aims adapt the off-the-sheed well-trained model using test-time data only, without accessing training data.
'School of Computer Science, State Key Laboratory for Mul- timedia Information Processing, PKU-Anner I.LM I Lab, Peking University, Beijing, China CColeeee of Computing and Data Sci- ence, Nanyang Technological University, Singapore 'Department of Computer Science, University of Califoriia, Los Angeles, CA, USA "Paul G. Allen School of Computer Science and Engineer- ing. University of Washington, Seattle, WA, USA. Correspon- dence to: Xiao Luo Exiaoluo@ss.uclle edu>, Zhiping Xiao <patx- i uw.edu>, Ming Zhang <mzhang .csaanggeseee cittaann.ss@uuu.ccu.cc..... pku.edu.cn
Previously, several solutions have been proposed to tackle the problem of test-time adaptation (Sun et al., 2020b; Liang et al., 2020; Nado et al., 2020; Gao al., 2023; Litrico et al., 2023; Karmanov et al., 2024). These methods often adopt self- self-training with pseudo- or use data-centric meth- ods on the test data. However, these works focus mainly on Euclidean data while research on non-Euclidean graph- structured data remains scarce. Specifically, test-time adap-
Proceedings of the nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Test-time Adaptation on Graphs via Adaptive Subgraph-based Selection and Regularized Prototypes
tation on graphs faces two important challenges: (1) How to overcome the label scarcity of test graphs more reliably in the face of structural shifts? As the adaptation of the model is performed during test time, the labels of graphs are unknown. Existing methods (Liang et al., 2020; Wang et al., 2020a) often utilize pscudo labels or entropy minimization for supervision. However, the shift on both node attributes and graph structures would deteriorate the performance of GNNs (Bao al., 2025), making the model's prediction unreliable and pseudo labels noisy. (2) How to utilize the knowledge from unknown training graphs and the informa- tion from unlabeled test graphs more effectively? Adapting the model during test time faces a dilemma: when the model flexibly adapts to self-training signals, may easily overfit and lose the knowledge learned from the unknown training graphs. On the other hand, when the model is not flexible enough, it may not fully utilize the information from the unlabeled test graphs.
While the idea of prototype adjustment has been used in pre- vious literature (Iwasawa & Matsuo, 2021), we formulate this from the theoretical foundation of Bayesian theory.
The contribution of this paper is summarized as follows. (1) We explore a practical yet under-explored problem of test- time adaptation on graphs, which aims to adapt the model with unlabeled test graphs without accessing training data, (2) We propose ASSESS that introduces adaptive subgraph- based selection (ASBS) for choosing reliable test graphs, and regularized prototype supervision (RPS) for balancing the prior knowledge from unknown training graphs and the information of unlabeled test graphs. (3) We provide theo- retical analysis of the proposed ASSESS. (4) We perform extensive experiments to show that ASSESS outperforms otate-of-the-art baselines, confirming its effectiveness.
2. Related Works
To tackle these two challenges, this paper proposes novel method named Adaptive Subgraph-basee based SElection and Regularized Prototype SuperviSion (ASSESS) for test-time adaptation on graphs. The idea behind ASSESS is to first select reliable test graphs and then use them for effective self-supervised learning balancing prior knowledge from unknown training graphs and posterior information from unlabeled test graphs. More specifically, to achieve reliable test graph selection, we adopt a fine-grained, individual- level and graph-specific selection strategy named Adaptive Subgraph- based Selection (ASBS) that considers both the model's confidence and individuul-level subgraph structure information. Prior works (Xu et al., 2021; Zhang et al., 2021a; Guo & Li, 2022) typically select confident test data using a single threshold or class-wise thresholds. In con- trast, we propose a more fine-grained selection strategy that utilizes the mutual information between subgraphs and orig- inal graphs to construct individual- and structure aware thresholds. This allows us to flexibly differentiate hard test- ing samples whose inherent graph structures are difficult for the model to classify. Thus, reliable test graphs can be selected and used for self-supervised learning.
Graph Neural Networks. Graph neural networks (GNNs) (Kipf & Welling, 2017; Hamilton et al., 2017; Chen et al., 2018) is a powerful tool for learning representations of graph structured data, with a wide range of applications in recommendation (Wang et al., 2020b; Chang et al., 2021), social network analysis (Yoo et al., 2022), molecule property prediction (Lu et al., 2019; Kim et al., 2023), and traffic flow forecasting (Zhao et al., 2023; 2024). The mainstream of GNNs is message passing neural networks that aggregate the neighborhood information to form representations of each node (Ju et al., 2024a). Subsequently, the feature vectors of nodes are aggregated using various pooling techniques (Zhang al., 2019; Bianchi et al., 2020) form graph- level representations. Despite their superior performance, they usually assume that the same distribution is shared across the training graphs and test graphs (Li et al., 2019; Zhao et al., 2025b), which fails to hold in various real- world scenarios (Shi et al., 2023; Dai et al., 2022). When distribution shifts become inevitable among test graphs, test-time adaptation emerges as a viable tool for adapting the model to the test graphs. Therefore, in this work, we investigate the problem of test-time adaptation on graphs and propose a novel method named ASSESS to solve this important problem.
Moreover, to achieve effective self- training that preserves the prior knowledge from the unknown training graphs and adapts to the unlabeled test graphs. we propose a novel method called Regularized Prototype Supervision (RPS). Concretely, we construct semantic prototypes of each class according to the well-trained model and use them as prior knowledge from the unknown training graphs. Then, we optimize the posterior of the prototypes given the unlabeled test graphs. The maximum a posteriori objective is then approximated by a self-supervised objective with regular- ization of the prototypes. This leads to a trade-off between fully utilizing the information of unlabeled testing graphs and retaining the knowledge of unknown training graphs.
Test-time Adaptation. Test-time adaptation (Chen et al., 2022: Zhang et al., 2022; Karmanov et al., 2024; Zhang et al., 2024; Zhao et al., 2025a), sometimes referred to as source-free domain adaptation (Kundu et al., 2020; Liu et al., 2021; Yang et al., 2021), has received increasing attention due to its ability to adapt to test data distributions without accessing the training data. This is a more realistic set- ting since training data is not always available, considering data privacy issues (Wang al., 2020a; Tan al., 2023). Most existing methods of test-time adaptation roughly fall into one of the two categories, i.e. self-training and data-
2

---

Test-time Adaptation on Graphs via Adaptive Subgraph-basd Selection and Regularized Prototypes
Corrected Threshold
Graph
fo(G)
Base Threshold To
G
Encoder
GNN
fo(G)
Ta.((G (G;
5 (fo, G)
Subgraph
G
Graph-level Embeddings
Mutual Information Estimation
Threshold Correction Estimation
Unlabeled Test
Graph Dataset
(a) Adaptive Subgraph-based Selection
z
G1
F1
W1
GNN Encoder
G2
r2
W2
GN
G1
G2
GN
rC
WC
Prototype Priors
G1, G2,, GN E D (t) ASBS
Embeddings
Prototypes
Reliable Test
Sampled Graphs
Prototype Supervision
Prototype
Graph Set
(b) Regularized Prototype Supervision
Regularization
Figure 1. The overall framework of the proposed method. We first select reliable graphs in the unlabeled test graph dataset using adaptive subgraph-based selection (ASBS), where we utilize mutual information to generate structure-aware, individual-level thresholds. Subsequently, utilize these graphs for self-training with regularized prototype supervision (RPS), where the prototypes regularized by prior knowledge and used for supervising the learned embedding of test graphs.
centric approaches. Self-training approaches (Sun et al., 2020b; Liang al., 2020; Chen et al., 2022) aim struct self-supervising signals via contrastive learning or pscudo-labeling. These methods often involve selecting reliable data for efficient liff-training. By comparison, data- centric methods (Mocerino et al., 2021: Zhang et al., 2022; Tomar al., 2023) aim construct virtual samples related the distribution data augmentation. spite of their effectiveness in Euclidean data, test-time adaptation is still under-explored in non-Fuclidean graph-structured data. Therefore, in this paper, we focus on test-time adaptation graphs and propose ASSESS that adaptively selects reliable test graphs based on subgraph mutual information and uses them for effective self-training.
graph, and No. is the number of test graphs. The label set {1, C). In test-time adaptation, the model is initially trained with labeled training (source) data Dtr, and then adapted to the test (target) data t under distribution shifts, without access to D We denote the GNN backbone and the following MLP as fe. and the graph features are gener- ated as G fo(G). Then, class probabilities are generated as D softmax 2'T=G) 2G). The entire model is denoted M. pd M(G).
Overview. During test-time adaptation, the model first selects reliable test graphs based on the model's ability to handle the inherent structure of test data. To achieve this, we propose adaptive subgraph- based selection that utilizes mutual information of subgraph structures and the entire graph measure this ability. Then the confi- dence threshold for each graph is adjusted accordingly for fine-grained, individual-leved and structure-aware selection. Subsequently, we adopt self onff-training supervised by regular- ized prototypes balancing prior knowledge from unknown training graphs and the posterior information from unlabeled test graphs. The delection-supervviii iteratively. The overall framework is illustrated in Figure 1. The upper part displays the adaptive subgraph-basee se- lection (ASBS), while the lower part shows the regularized prototype supervision (RPS).
3. Methodology
Problem Formulation. We denote a graph as G (V, A, X), where V is the set of nodes, A E IR V is the adjacency matrix, and X E R Vixd' is the node attribute matrix with df the number of attributes. We denote labeled training graph dataset D = {(G)", """""""" Mir where G is the i-th training graph, o is its label and Nr the number of training graphs. The unlabeled test graph {G )1 where Gie denotes the jth test
process is performed
dataset Dee
3

---

Test-time Adaptation on Graphs via Adaptive Subgraph-based Selection and Regularized Prototypes
3.1. Adaptive Subgraph-based Selection
where 9á is the discriminator instantiated with a multi-layer perceptron, and sp(x) log(1 + +e*) ( is the softplus function. The estimated mutual information Le (G; G) is then used for calculating the threshold correction function as follows,
Adapting the model during test time often involves self- training on unlabeled test data, in which the output predic- tion of the model is often used to construct self-supervising signals. However, as the model inevitably yields inaccu- rate predictions, it is crucial to carefully select reliable data, which can promise the success of these self-training ap- proaches, especially for graph data that involves complex structures. Existing methods (Xu et al., 2021; Zhang al., 2021a; Guo & Li, 2022) often adopt shared threshold or class-wise thresholds to select data, i.e.
S(G -
(4)
where is a hyperparameter balancing the relative impor- tance of mutual information in the threshold.
Moreover, as accurate and stable estimation of mutual infor- mation requires sampling a number of graphs from the test graphs D which can be computationally expensive, we adopt the temporal ensembling technique (Hao et al., 2015; Laine & Aila, 2016) that gradually updates the threshold correction function as follows,
G max $ iE(1.-.Cy .C p Deons= = =GG E Dle|soon) > Th
(1)
where S / is the confidence score of graph G, pf is the predicted probability of graph G belonging to class i, and r is the threshold, which can be shared threshold To or class-wise threshold 7 = r
f-1 8t (G. w > 3(1 3) (G:
(5)
However, this simple strategy can be problematic, as the model can be inaccurate in exploring the unlabeled test data, especially when it comes to graphs with complex inherent structures. Therefore, it is reasonable to use different se- lection thresholds for graph structures with different levels of complexity. Graphs with complex structures are hard to learn for the model, and the model tends to be inaccu- rate. Thus, a higher threshold should be used, and vice versa. Towards this end, we propose an adaptive selection strategy that considers both the model's confidence and the model's s ability to handle the inherent structures of the graph. Specifically, instead of a shared threshold, we adopt graph-specific, individual level threshold, iee
where (G, fo) is the threshold correction epoch t, 1( (G; G) is the estimated mutual information at epoch 1, and B3 is the parameter controlling the speed of updates, which set to 0.2. The above formula can be computed re- cursively, similar the exponential moving average, which leads to a stable estimation of mutual information. With this, reliable test graphs can be selected as follows:
((1) ASBS = {G E D Dio| f > - = To + +5500 fo)}-
(6)
3.2. Regularized Prototype Supervision
Once reliable test graphs are selected, self-training can be subsequently performed. While previous methods directly fine-tune the model's parameters on the test data using self- supervising signals (e.g. pseudo labels, entropy minimiza- tion), it can drastically change the model and overfit the self-training objectives. Self-training faces a trade-off be- tween preserving prior knowledge of the unknown train- ing graphs and the posterior information of unlabeled test graphs. Liang et al. (Liang et al., 2020) freeze the classifier head of the model so as to avoid forgetting prior knowledge. In this subsection, we propose a more flexible alternative that combines prior knowledge and posterior information.
= + 5(G, fo).
(2)
where G is the confidence threshold for graph G, To is the base threshold, and 8G, fo) is the correction function taking into account the model's ability to yield an accurate prediction from G.
In order to measure this ability, we propose to use mutual information (MI) between graph G and its subgraph G = (Vide, Aidz,dz X idd..). The idæ is the randomly selected subgraph indices, which is simple yet effective strategy. A high MI between a graph and its subgraphs indicates that the graph representation encodes information shared across its subgraphs. In other words, the encoder is able handle the inherent structure of this graph. Once the subgraph à' is obtained, we approximate the MI between G and its subgraph G as follows, using Jensen-Shannel MI estimator (Sun et al., 2020a),
Specifically, we first construct semantic prototypes of each class as and initialize them with the weight matrix of the last layer of the model, i.e. r; w. We denote the stacked prototypes as R = [21.r2. r2, ... rrc E R4xC where is the dimension of prototypes. The goal is to optimize the prototypes given the information about the test graphs. This objective can be written as:
To.o δ) = EEG (pc- Bec.ppr..r..oosssppoooooooo
Rd argmax (R G E D (0) R
ASBS
(7)

---

Test-time Adaptation on Graphs via Adaptive Subgraph-based Selection and Regularized Prototypes
Using the Bayes rule, this objective can be further decom- posed into prior and likelihood, which is
however, requires solving large linear program (Genevay et al., 2019), and common workaround is to add entropy regularization that encourages the diversity of assignment. A Lagrangian objective can be written as follows
log pl (RIG) log ((R) + R)) Co.
(8)
N
where Co is a constant. For the first term, we assume that the prototypes R follow isotropic Gaussian distribution, i.e. R ~ (R: W. of where the mean is set the initial values of the prototypes, and of is the shared variance of the prototypes. Under this assumption, the prior knowledge constraint of the prototypes can be written as:
E t-trQQ"Re Rd Z) eH(()) (a. QIN clc)
C
(13)
+(b, Q0 - 1N),
where & is the objective to be minimized, is the tem- perature parameters controlling the degree of regular- ization, and b are Lagrangian multipliers, H(Q) Ei. Qig Qi - 1) is the entropy regularization. We take the derivative with respect to Qú,j which gives the following result:
po R = log (
exp (-
1 20
R W
/ V2
= =CilRR- 1
df iQ..j
[R Z). e log Qi, a; bj.
(14)
(9)
where C1 and C2 are constants.
Therefore, the closed-form solution can be written as:
For the second term, we transform it into a self-supervised objective. Inspired by the mixture models (MeLachlan & Basford, 1988; Reynolds al., 2009), we have:
a
R² Z
Q' = diag (exp
exp
diag exp
(15)
In practice, we utilize the iterative Sinkhorn-Knopp algo- rithm (Asano et al., 2019; Caron et al., 2020; Zheng et al., 2021) to solve this problem (more details in Appendix B). Specifically, repeated row normalization and column nor- malization are conducted on exp R² and the algorithm converges quickly. Previous studies (Genevay al., 2019; Luo et al., 2023) indicate satisfactory performance within 3 iterations, and the soft assignment of the entropy is benefi- cial.
log ( R) = log log
log Σ q(G ()I()))))
2 Σ (oG.
(10) where i) denotes the assignment of graph G belonging to prototype Tı, and the inequality comes from Jensen's inequality. Thus, we have lower bound for the likeli- hood. For the estimation of q(G, i). a common approach is to compute the similarity between the representation of the graph z and the prototypes r; Denoting qd = Ig(G; q), 2)...... .. C)J"" this simple objective can be written
Then, we provide an estimation of p(G Although this probability takes the form of generative modeling, actually training a generative model can be costly, and when fac- ing insufficient data, it can be inaccurate. Therefore, we estimate this term in the latent space using the feature ex- tractor fo with isotropic Gaussian distribution, which is p(G]rs) x exp (- 2, [looGG rilß).. where of is the shared variance of the latent features. Combining the two terms, the loss function can be written as
argmin RRRRT20) (.t. 1c) = 1, (11) d
where ( denotes inner product measuring the similarity,
and l E RCC is an all-one vector. However, this simple ob- jective can result in unbalanced estimation, where the num- ber of assignments to some classes is substantially larger than others. To solve this problem, another constraint is needed. Concretely, given a set of graphs G1, G2.... GN. where N is the number of graphs, we hope to achieve balanced assignment, which can be written as
LRPS = Σ (G, - W WI2, (16) 1=1
where ((G, i) is obtained via the Sinkhorn- KiikhornnKKoppp iterations within batch of graphs, and a' is the hyperparameter bal- ancing the two terms. The first term serves as self-training objective utilizing the posterior information from the unla- beled data, whereas the second term serves as regularization from the prior knowledge of the unknown training graphs. As the prototypes r; (with their matrix form R) are used to provide supervision signals in the self-training and regular- ized by the prior knowledge, we call this method regularized prototype supervision.
argmin tr trQ (Q"RRZ) S.t.QIN = lo. 10 = 1N Q
(12) where Q = [9 c1 C2 GN| E CxN is the stacked assignments, and Z 22 2 202 ..... 2GN] E N is the stacked graph representations. Solving this problem,
5

---

Test-time Adaptation on Graphs via Adaptive Subgraph-based Selection and Regularized Prototypes
Algorithm 1 Optimization Algorithm of ASSESS
we extract the pivotal elements of the ASSESS algorithm and make them more math-friendly. We start by defining as the data pair, namely, < _ (G, y) where the symbol G is an input graph and y represents the corresponding label of G. The training graph set Dee is supposed to follow an underlying distribution P. The objective of our ASSESS algorithm to reduce the expected loss function [(w) as much as possible, that to say, we hope to solve the follow- ing stochastic optimization:
The well-trained GNN-based model on the training graphs M) (-), test graphs D
Input:
Output: GNN-based model after 7 epochs (()
1: Initialize the prototypes R +- W;
2: Initialize the reliable test graph set ASBS Dronf using Eq. 1;
[0)
3: for i= 1, 2, ... do
4: for each batch do
5: Sample a mini-batch of target graphs;
min [(w) == Ee-Pl((w;E)) w
(18)
6: Calculate LrpS using Eq. 16 over (
ASBSi
7: Calculate LMr using Eq. 3 over D'e;
where & ~ P denotes the graph-label tuple & - (G. y) comes from the distribution P. w represents the model pa- rameters and I(w;;) {) is the loss objective associated with the data pair &. For the test pair from the unlabeled graphs D we assume it originates from mixture of two distributions P (with a probability of q) and Q (with 1 q). Formally, for any test pair 5 = (G. E ~ qp + (1 q) The class y in test pair & can be considered as a pseudo label gener- ated by the pretrained model. To distinguish the former two distributions, adopt the Tsybakov noisy condition:
8: Calculate the loss objective using Eq. 17;
9: Update parameters of _M through back- propagation;
10: end for
11: Update the threshold correction function using Eq. 5;
12: Obtain reliable graphs D((+1) using Eq. 6;
13: end for
3.3. Summarization
Assumption (Tsybakov Condition (Tsybakov, 2004)). For any model parameter w, if the expected loss L(w) less than a threshold "a", the following inequality holds:
The algorithm is performed iteratively. In each iteration, we first adopt adaptive subgraph-bast based selection to obtain reliable test graph set D(4) ASBS- Subsequently, regularized prototype supervision training is performed on the reliable graphs. The two steps are performed iteratively. As accu- rate estimations of mutual information require optimized parameters f, é, we also put the mutual information as part of the objective, and the final loss is:
Eg (BWW:))) S (w),
(19)
where the symbol Is(E) stands for the standard indicator function that equals 1 if & E S and O otherwise, is a positive scaling constant and m 2 1 is a fixed constant.
L= LRPS + O2LMM,
(17)
Next, we make some frequently used assumptions about the smoothness and boundedness of (stochastic) gradient, i.e.,
where ag is the hyperparameter balancing the two terms and LMi (e: G) is the objective of optimizing the mutual information. The first term Lars is calculated with the reliable graphs ((t) ASBS. while the second term is calculated with the entire test graph set Dee to encourage participation from graphs that are initially regarded as un- reliable. Moreover, we also adopt a curriculum learning strategy that gradually increase To, since we want more participation during the initial stages of adaptation to fully utilize unlabeled test graphs and more reliability when the adaptation proceeds to avoid noisy signals. The learning algorithm is summarized in Algorithm 1. To demonstrate the efficiency of the proposed algorithm, we provide com- prehensive time complexity analysis (which shows that the proposed algorithm has the same time complexity as most GNNs) and running time information in Appendix C.
Assumption 2 (Boundedness). The stochastic gradient Vi(w; is bounded, i.e., [Vl((;;)) & G where the sym- bol || denotes the Euclidean distance.
Assumption 3 (Smoothness). [(w) is smooth with an L- Lipchitz continuous gradient, i.e., L(w) is differentiable and there exists a positive constant L such that
[V (ow))VL(in (()) S L|[w-u] =/l.
(20)
Assumption 4 (Polsaktt.jassewwicz condition (Polyak, 1963)). There exists constant μ > 0 such that
2x([(w) - L(w")) < VL()))
where w is a optimal solution problem minw L(w).
The
condition has garnered atten- tion in deep learning research. Particularly, (Allen et al., 2019) offers theoretical proof of its ability to guarantce lin- ear convergence of gradient- based methods in non-convex
3.4. Theoretical Analysis
In this subsection, we aim to provide a detailed theoretical analysis of our proposed ASSESS method. For simplicity,
6

---

Test-time Adaptation on Graphs via Adaptive Subgraph-based Selection and Regularized Prototypes
Table 1. The classification accuracy (in %, training - test) on FRANKENSTEIN (FO, F1, F2) and Mutangenicity (MO, M1, M2).
FRANKENSTEIN
Mutangenicity
Methods
FO-FI
FO-F2 FI-FO F1-F2 F2-FO F2-FI
AVG
M0-MI M0-M2 MI-M0 MI M1-M2 M2-MO
M2-MM
AVG
GCN
5..
52.2.0.88
56.2:0.77
55.612.0
54.212.3
55.8118
554114
72.7=1.3 59.211.2 74.310.2
70.7.11.8
66.312.4
7..4 69.311.44
GraphSACi
61.3-188
56.5+0.66
580-1199 56.742.99 55.241.8
588++15
57.7+1.7
74.6=1.8 58.0+18
75.4+1.6
66.440.8
63.8+4400
72.8+5.9
68.542.6
GIN
61.7=114 54.121.5
57.741.3
58.1=12 56.21144
60.114.6
58.0#19
75.1=32 59.7=0.8
74.9=1.1
67.611.1
65,3428
70.8114
68.91117
GAT
58.1=2.1
51.3+155
58.0+2.2
57.0=1.6
53.2+14
58.1225
56.0=19
73.1=03 59.2=177 73.6+20
67.1+2.3
59,3+188
70.642.0
67.1
Mean Teacher
61.2::100
58.111.7 58.7.106 59.6:29
55.71144
54.0119
17
67.9140
61.0441 71.5:43
68.11244
70.711.6
74.811.2 69.0129
GraphC1.
60.6+117
56.5+1. 54.743.0
57.0-18
53.742.5
60,9222
57.2421
70.9443
64.0+13
66.745.7
715+-11
65.4429
73444. 68.61322
SHOT
60.4:117 59.7#2.3 55.6109
57.2=18 55.7119
59.1225 58.0#18
74.4=15
60.7=28
72.0=24
63.0:40
69.2:233
72.014.1 68.61288
TAST
62.6=113 55,4+0077 52.945.9
52.9=377
57.0+1.8
59,4#3.0 56.7+28
74.2=3.2
59.7=0.4
73,4+05
68.5+20
70.6+08
77.2+0.5
70.6112
RNA
62.4.109 1..51:13 19.1 59.1 57.810.3 60.412.4
59.0124
71.9117
58.8149
72.3120 67.5 61.61444 73.210.3 67.61188
Ours 64.1=14 56.1119 59.211.0 61.42.11 59.311. 61.813.9 60.3:19
78.9
63.1216 77.0116 72.5+2. 68.711. 80.910.9 73.5
optimization. Moreover, (Yuan et al., 2019) have also fur- nished empirical evidence of the PL condition's 's presence during the training of deep neural networks.
our ASSESS algorithm can progressively reduce the loss to adapt to the test-time distribution shifts. More specifically,
after O log( # iterations, our ASSESS algorithm is capable (og(
The above assumptions are common in machine learning (Akhavan et al., 2024; Yuan et al., 2019; Allen-Zhu et al., 2019). With these standard assumptions of the loss function, we now show the convergence for ASSESS. Prior to that, let us present a more detailed characterization of the algorithm: i) At each epoch & E {I, T',, we suppose the total size of the sampled target graphs is n, = n17²=1 and we also use Dfe to denote the set of considered test graphs at l; ii) The loss function L incorporates the mutual information for subgraph selection, as detailed in Section 3.3. Thus, we can, approximate the graph selection strategy as follows:
of attaining an 6 optimization error.
Remark 3.3. It important to emphasize that the proof of Theorem 3.1 primarily draws from Theorem 1 presented in (Xu et al., 2021). However, in sharp contrast with Theorem of (Xu et al., 2021), our Theorem 3.1 incorporates a more precise Tsybakov condition and a threshold range assump- tion of Pt E [cL(we), b.())) which enables it to cover a broader range of application scenarios. Furthermore, the re- fined Tsybakov condition and the specified range of Pt allow us to better adapt to probabilistic incqualities in different directions, e.g., (25) and (28) in Appendix A.
D(1) ASBS R {G E "D;")[(W;E(CS) S Pt. Pt. E(G) = (G,w),,
4. Experiment
(21) where Pe is the dynamic threshold and y is the pseudo label of the test graph G; iii) At each iteration t E {1,2...., TT). we assume the model w, is updated via the stochastic gradi- ent descent (SGD), i.e., W = Wg where 7) > 0 is the step size and g, is the average gradient over all reliable and considered graphs. With these detailed characterizations and assumptions, we have the following theorem:
4.1. Experimental Settings
Datasets. We perform experiments on a number of real- world datasets with the test-time adaptation setting. Con- cretely, choose five representative datasets, including FRANKENSTEIN (Orsini et al., 2015), Mutangenicity (Kazius et al., 2005), PROTEINS (Borgwardt et al., 2005), NCT1 (Wale et al., 2008), and IMDB-BINARY (Yanardag & Vishwanathan, 2015). The datasets are split into three subsets according to graph density, leading to distribution shifts across splits. The datasets cover wide range of fields, including chemistry, biology, and social networks. We evaluate our methods under the offline test-time adap- tation setting (Wang et al.. 2022), where all test inputs are available for adaptation. More details about the datasets are shown in Appendix D.
Theorem 3.1 (Proofs are deferred to Appendix A). Under Assumption 1-4, if we suppose L(w*)= = O and I(w;E) E) E [0, 1] for any parameter w and data pair E, when L(w1)= I a, Pe E (cC(w,)) b[(w))),
n4 = -177" 1-1 nI. S 1 where Y >> 1 and ni max [log(2/8) log(2/6) 1og(2/8) 24 2(1-g3* 7(1---172)
for any 8 E (0,1),c (0, b). we can show that the final model parameter WT+1 produced by our ASSESS algorithm satisfies that, with a probability 1 - (4T + 1)6, ō E 10,
[(Wr+1)=00 = 0(
(22)
We compare our method with a wide range of baselines listed as follows: (a) Graph neural networks, including GCN (Kipf & Welling, 2017), Graph- SAGE (Hamilton et al., 2017), GIN (Xu et al., 2019), and GAT (Veličković et al., 2018). (b) Unsupervised / Semi- supervised training methods, including -eacher (Tar- vainen & Valpola, 2017) and GraphCL (You et al., 2020). (c) Test-time adaptation methods, including SHOT (Liang et al.,
Compared Baselines.
Remark 3.2. Theorem 3.1 provides theoretical valida- tion that when the pretrained model Wi satisfies certain generalization property, such as [(w1) < a, if we can con- tinuously adjust the batch size (e.g. n; = - and efficiently select the high-quality test graphs (e.g. the dy- namic threshold Pt is within the range (cL(w.)), ((W.)),
7

---

Test-time Adaptation on Graphs via Adaptive Subgraph-based Selection and Regularized Prototypes
Table 2. The classification accuracy (in %, training - test) on PROTEINS (PO, P1, P2) and NCTI (NO, NI, N2).
PROTEINS
NC11
Methods
PO-PPI PO-+P2 PI-PO PI-P2 P2-PP P2-P1
AVG
NO-NI NO-N2 N1-NN NI-N2 N2-NO N2-N1 AVG
GCN
57.0=48
41,9=0,7 64.8+2.0 54,7=3,3 62.5+133 61.7=3.5
57.1426
70.1=31
54.8+13 $2.6#2.0
56,3+19
50.1+3.3
63.0#1.5
57.8+2.
GraphSAGE
53.9=5.3
41,5=0,,5 70.3+3.2 57.3=19 69.0+0.9 62.1=2.1 59.0#2.3
69.2=10
55.8+08 51,2+1.2
59.5+2.7
48.8+0.8
61.6#3.7
57.7
GIN
58.9+1.1 41.7:+0.6 64.241.9 53,1+2,2 59.240.7 68.2424 57.6+1.5
73.0-25
56.9+15
55.6+44.7
59.1+22
50,340.9
64.5+1.9 59.94233
GAT
63.2++4.3 41,5+0055 77.1+29 63.8=411 64.4229
61.0+18 61,8+28
70.5=69
55.6+0.4 51,9+14
17.4+19
50.7+12
63,942.9 58 58.3425
MeanTeacher
72.017.2 65.3.15.2 70.51228 66.5.7.33 73.315.1
67.2.166 69.115.0
71.5_86
61.913.7 64.7110.5
75.412.5
59,41123
66.1 66.5.66.5
GraphCI.
79.2:::.0 73.7:1644 75.22.52 73.9:4.1 73.515.1
77.0474
75.415.7
76.2:33
67.611.3 69.0.111
77.3
66,213.2
73.1 71.61233
SHOT
68.2:5.4 62.9:4.2 71.61422 65.9=7.0 67.816.0 68.847.0
67,5+56
64.4=44
56.6126
73,9111
65.5#34
69.6+2.7
64.0=2.8 65.7228
TAST
68.917.5 41.9:1.0 75.1+22 62.1=2.6 63.812.5
61.91166 62.3+2.9
72.2=5.1
56.51088
55,2420
57.7+23
48.910.7
66.0.3.7
594424
RNA
61.8+9.1 65.8+4.1 79.1+2.3 71.1=9.1 74.243.1 69.3=1.9 70.2+4.9
72.0=18
61.3+4.7 76,443.7
72.4+111
65.744.4
74.9+0.5
70.5+227
Ours
81.9337 74.7=4.1 86.7+17 77.3=2.8 82.4+:40 70.4 78.913.8
79.6=2.1 69.1+2.5 81.9=2.0 18.5 73.4+2.0 70.3#1.1 75.5=18
Table 3. The classification results (in %, training - test) on IMDB-
Table 4, Ablation studies on three datasets, Lee FRANKENSTEIN (FRAN), Mutangenicity (MUTA), and NCII. Average accuracy over six settings (in %) is reported.
BINARY (I0, I1, 12).
Methods
10-+11 10-12
11-10
11-122
12-100
12-11
AVG
GCN
78.5e2.0
66.0e2.9
60.6118
62.4e1.7
58.2+1.3
$7.0aa3
63.3+22
Experiments
FRAN
MUTA
NC11
AVG
GraphSAGE
78.221.8
60.624.1
58.553.2
63.9215
56.720.9
56.7427
62.42244
GIN
75.8.17 66.612.2 58.156
61.5117
51.30077
56.7121 6288124
w/o ASBS
$9.812.00
72.411..
73.9.1..4
68.7
GAT
77.3+1.1 64.5t117 63.600.7
62.1+2.0 549:22
5884007 63.5
MeanTeacher
70.1+668 66.2+225 63.2+-13
70.1+2.4
59.7+2,4
61.2+422 64.+388
w/o RPS-a
59.411.5
71.31:11
74.0
68.2
GraphCL
66.2::.1 70.6#a.1 61.7a19
70.12244 61.7449
46.144. 628saa
SHOT
68.9-5.1 66.6-4.5
65,7-34
67.8-68
61.5+73
606694 65.2+6.1
w/o RPS-b
19,4+1122
70.6+
74.1+118
68.0
TAST
50.3-222 65.1=38 58.2-2.1
64.2a1.9
57.6.0.7 58.222 63.9222
Full Model
60.3=1.9
73.5+1.5
75.5+1.8
69.8
RNA
61.2.322 67.2.4.9 59.7.332 69.2.2.5 61.7135 68.713.2 65.1
Ows
82.1=377 66.7=3.7 63.7=19 63.7=1. 69.7=3.1 61.2+3.2 67.8+29
remains limited, which can be attributed to their lack of consideration of test-time distribution shifts. Thirdly, test- time adaptation methods designed for Euclidean data (Liang et al., 2020; Jang et al., 2023) are also not very satisfactory on graphs. Although they experience modest improvements on some datasets, their performance is still weaker than AS- SESS, which can be attributed to their lack of consideration of complex structures of graph data.
2020), TAST (Jang et al., 2023) and RNA (Luo et al., 2024). More details about the baseline methods are in Appendix E.
Implementation Details. By default, we utilize two GIN (Xu et al., 2019) layers to learn graph representation, and then mean pooling is applied followed by a two-layer MLP to obtain the graph level features (i.e. zO). For the dis- criminator Jo. the two inputs are concatenated and pro- cessed by a two-layer MLP to obtain a scalar-valued out- put. To is selected such that 80% of the samples are re- garded as reliable in the first epoch and linearly decrease so that 60% of the samples are deemed reliable. As for hyperparameters, we set the following values by default. is set 0.1, 01 is set to 0.1, and 02 is set to 10-2 The learning rate is set to 10-4, For optimization, we adopt Adam optimizer (Kingma & Ba, 2014), with learn- ing rate of 10-4. The experiments can be performed on an NVIDIA A40 GPU. The code is publicly available at com/ Yusheng ASSESS.
4.3. Ablation Study
We now investigate the impact of the proposed adaptive subgraph-based selection (ASBS) and regularized proto- type supervision (RPS). For RPS, we denote "RPS-a" as the first term of the loss function (Eq. 16), and "RPS-b" as its second term. The results are shown in Table 4, from which we have the following observations: (1) All of the pro- posed components contribute to the model's 's performance, since the improvement decreases without each of the ablated modules. (2) The performance drops by 1.1% on average without ASBS, showing the necessity of selecting reliable graphs adaptively during test time adaptation, as unreliable graphs might introduce noisy signals during self-training. (3) The model is suboptimal without supervision signals of the prototypes (removing the first term in Eq. 16, i.e. "w/o RPS-a"). Without proper supervision, the accuracy decreases by 1.6% average, showing the importance of exploiting test graphs. (4) Removing the regularization on the prototypes (the second term in Eq. 16, "w/o RPS (2)"") causes a considerable performance drop, demonstrating the importance of preserving prior knowledge of the model, which prevents catastrophic forgetting.
4.2. Performance Comparison
The prediction accuracy on the test graphs is shown in Table 1, 2, and 3, from which we have the following observations: Firstly, ASSESS achieves a consistent improvement com- pared to all the baseline methods on average across all five datasets, which demonstrates the overall effectiveness of the proposed method. Secondly, the unsupervised / semi- supervised learning methods (Tarvainen & Valpola, 2017; You et al., 2020) are not the optimal solution. Although they experience improvement on some datasets like PRO- TEINS and NCT1, the performance gain on other datasets
8

---

Test-time Adaptation on Graphs via Adaptive Subgraph-basee Selection and Regularized Prototypes
00
PRAN
NUTA
XCI
PBAN
MUSA
NCE:
79-
75
65-
65
0,005
0.01
0.05
10-1
10-4
10-1
10-2
10-1
Before Adaptation
After Adaptation
Figure The model's sensitivity to hyperparameters (i.e. 0n
Figure 3. Visualization of learned representations on the PRO-
and (2). The experiments are performed on FRANKENSTEIN (FRAN), Mutangenicity (MUTA), and NCII. Average accuracy (in %) are reported over six settings.
TEINS dataset, before and after adaptation in the P1 P1-PO setting.
Selection Accuracy
0.8
0.7
4.4. Parameter Sensitivity
0.6
Uniform Threshold
We then investigate the model's sensitivity to hyperparam- eters. Specifically, we focus on two of them: 0r, which balances the relative importance of prior prototype regular- ization in Eq. 16, and 022, which is the weight of informa- tion maximization loss in Eq. 17. The results are shown in Figure 2, and we can see that the model is generally not sensitive to hyperparameters, as slight perturbations around optimal values yield similar accuracy. Specifically, setting on to yields the best performance. When on is small, the weight of the prior prototype regularization small, lacking regularization to the prototypes. Conversely, when (i is too large, strong constraint from the prior prevents adaptation to test graphs under distributional shifts. As for az2, it balances the relative importance of LRPS and LMI. This hyperpa- rameter achieves its best at 10-3 or 10 Generally, when 02 is too small, falls short in proper supervision the MI training, leading to sub-optimal performance. Conversely, larger weights decrease the relative importance of the self- training loss, resulting in sub-optimal adaptation.
0.5
Class wise Thresbold
ASBS
0.4
0
10
15
20
Adaptation Epochs
Figure 4. The selection accuracy using uniform threshold, class- wise threshold, and the proposed ASBS on the PROTEINS dataset.
old selection and class-wise threshold selection, and we show the selection accuracy (i.e. the accuracy of pseudo- labels of selected graphs) under varying epochs in Figure 4. As can be seen from the results, the selection accuracy of ASBS is significantly higher than those of others. The selection accuracy of the uniform threshold is much lower than ASBS, and it drops considerably after the 15th epoch. Using class-wise thresholds helps with the selection accu- racy slightly, reaching 0.7. By comparison, ASBS reaches a high accuracy of nearly 0.8 and stabilizes as the adaptation proceeds, demonstrating that ASBS is better at identifying reliable test graphs during adaptation.
5. Conclusion
4.5. Visualization of Learned Representations
This paper investigates test- tist-time adaptation on graphs, and proposes a novel method named Adaptive Subgraph-based SElection and Regularized Prototype SuperviSion (AS- SESS). To select reliable test graphs for self seff-training, AS- SESS utilizes subgraph mutual information and selects test graphs adaptively. To fully utilize the information of un- labeled test graphs while preserving the knowledge from unknown training graphs, ASSESS adopts regularized pro- totype supervision that constructs semantic prototypes and performs self-training with regularization from the prior. Extensive experiments across various datasets validate the effectiveness of ASSESS.
We also use t-SNE (Rauber al., 2016) to visualize the learned representations of the test graphs. The results are shown in Figure 3, where we adapt the model initially trained on the P1 subset of the PROTEINS dataset to the PO subset. The learned representations the test graphs before and after adaptation are compared, As can be seen from the figure, the proposed method yields more clustered and condensed representations. This can be attributed to adaptive subgraph-basse based selection that filters out unreliable test graphs, and regularized prototype supervision that hetter utilizes unlabeled test graphs with self-training while pre- serving the knowledge learned from the inaccessible training graphs. More visualization about the learned representations can be found in Appendix F.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
4.6. Analysis of Selection Results
In this subsection, we compare the selection results adap- tive Sabgraph-based selection (ASBS) with uniform thresh-

---

Test-time Adaptation on Graphs via Adaptive Subgraph-based Selection and Regularized Prototypes
Acknowledgment
ACM SIGIR conference on research and development in information retrieval, pp. 378-387 2021.
This paper is partially supported by grants from the Na- tional Key Research and Development Program of China with Grant No. 2023YFC3341203 and the National Nat- ural Science Foundation of China (NSFC Grant Number 62276002). The authors are grateful to the anonymous reviewers for critically reading this article and for giving important suggestions to improve this article.
Chen, D., Wang, D., Darrell, T., and Ebrahimi, S. Con- trastive test-time adaptation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 295-305, 2022.
Chen, J., Ma, T., and Xiao, C. FastGCN: Fast learning with graph convolutional networks via importance sampling. International Conference on Learning Representations, 2018.
References
Akhavan, A., Chzhen, E., Pontil, M., and Tsybakov, A. B. Gradient-fiee optimization of highly smooth functions: improved analysis and new algorithm. Journal of Ma- chine Learning Research, 25(370): 2024.
Chen, X., Jia, S., and Xiang, Y. A review: Knowledge reasoning over knowledge graph. Expert systems with applications, 11244,,, 2020.
Dai, Q.. Wu, X.-M,, Xiao, J., Shen, X., and Wang, D. Graph transfer learning via adversarial domain adaptation with graph convolution. JEEE Transactions Knowledge and Data Engineering, (5(5):4908-4922 2022.
Allen-Zhu, Z., Li, Y., and Song, Z. convergence theory for deep learning via paraaaetttttiitiinnn. In International conference on machine learning, pp. 242-252. PMLR, 2019.
Fan, W., Ma, Y., Li, Q., Wang, J., Cai, G., Tang, J., and Yin, D. A graph neural network framework for social recommendations. IEEE Transactions Knowledge and Data Engineering, 34(5):2033-2000 2027,
Asano, Y. M., Rupprecht, C., and Vedaldi, A. Self-labelling via simultancous clustering and representation learning. arXiv preprint arXiv: 19t:::991// 1.05371, 2019.
Bao, W., Zeng, Z., Liu, Z., Tong, H., and He, J. Matcha: Mitigating graph structure shifts with test-time adaptation. In The Thirteenth International Conference on Learning Representations, 2025.
Gao, J., Zhang, J., Liu, X., Darrell, T., Shelhamer, E., and Wang. D. Back to the source: Diffusion- adaptation test-time corruption. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, 2023.
Bianchi, F. M., Grattarola, D., and Alippi, C. Spectral clus- tering with graph neural networks for graph pooling. In Proc. of International Conference on Muchine Leurning, 2020.
Genevay, A., Dulac-Aroold, G., and Vert, J.-P. Differen- tiable deep clustering with cluster size constraints. arXiv preprint urXiv:1910.0000
2019.
Bongini, P., Bianchini, M., and Scarselli, F. Molecular gen- crative graph neural networks for drug discovery. Neuro- computing, 450:242-252, 2021.
Godwin, J., Schaarschmidt, M., Gaunt, A., Sanchez- Gonzalez, A., Rubanova, Y., Veličković, P., Kirkpatrick, J., and Battaglia, P. Simple gnn regularisation for 3d molecular property prediction beyond. arXiv preprint 1XXx::20660097),, 2021.
Borgwardt, K. M., Ong, C. S., Schönauer, S., Vishwanathan, S., Smola, A. J., and Kriegel, H.-P Protein function prediction via graph kernels. Bioinformatics, 21(uupp__)): i47-i56, 2005.
Gui, S.. Li. X., Wang, L., and Ji, S. Good: A graph out-of- distribution benchmark. Advances in Neural Information Processing Systems, 35:2059-2073, 2022.
Cai, H., Zhang, H., Zhao, D., Wu, J., and Wang, L. Fp-gnn: a versatile deep learning architecture for enhanced molec- ular property prediction. Briefings in bioinformatics, 23 (6):bbac408, 2022.
Guo, L.-Z. and Li, Y.-F. Class-imbalanced semi-supervised learning with adaptive thresholding. In International Con- ference on Machine Learning. pp. 8082-8094. PMLR, 2022.
Caron, M., Misra, I., Mairal, J., Goyal, P., Bojanowski, P., and Joulin, A. Unsupervised learning of visual features by contrasting cluster assignments. Advances Neural Information Processing Systems, 2020.
Hamilton, W. L., Ying, R., and Leskovee, Inductive representation learning large graphs. In Advances in Neural Information Processing Systems, 2017.
Chang. J., Gao, C., Zheng, Y., Hui, Y., Niu, Y., Song, Y., Jin, D., and Li, Y. Sequential recommendation with graph neural networks. In Proceedings of the 44th international
Hao, L., Healey, C. G., and Bass, S. A. Effective visual- ization of temporal ensembles. IEEE Transactions on
10

---

Test-time Adaptation on Graphs via Adaptive Subgraph-based Selection and Regularized Prototypes
Visualization and Computer Graphics, 22(1):787-796 2015.
Laine, S. and Aila, T. Temporal ensembling for semi- supervised learning. arXiv preprint arXiv: 2016.
Iwasawa, Y. and Matsuo, Test-time classifier adjustment module for model-agnostic domain generalization. Ad- vances in Neural Information Processing Systems, 34: 2427-2440, 2021.
Li, J.. Rong, Y., Cheng, H., Meng, H., Huang, W., and Huang, J. Semi-supervised graph classification: A hi- erarchical graph perspective. In The World Wide Web Conference, pp. 972-982, 2019.
Jang, M., Chung, S.-Y., and Chung, H. W. Test-time adapta- tion via self-training with nearest neighbor information. In The Eleventh International Conference on Learning Representations. 2023.
Liang, J., Hu, D., and Feng, J. Do we really need to access the source data? source hypothesis transfer for unsu- pervised domain adaptation. In Proc. of International Conference on Machine Learning, 2020.
Jiang, D., Wu, Z., Hsieh, C.-Y., Chen, G., Liao, B., Wang, Z., Shen, C., Cao, D., Wu, J., and Hou, T. Could graph neural networks learn better molecular representation for drug discovery? a comparison study of descriptor-baut based and graph-based models. Journal of cheminformatics, 13: 1-23, 2021.
Litrico, M., Del Bue, A., and Morerio, P. Guiding pseudo- labels with uncertainty estimation for source-free un- supervised domain adaptation. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, 2023.
Liu, M., Fang, Z., Zhang, Z., Gu, M., Zhou, S., Wang, X., and Bu, J. Rethinking propagation for unsupervised graph domain adaptation. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 38. pp. 13963- 13971, 2024.
Ju, W., Fang, Z., Gu. Y., Liu, Z., Long, Q. Qiao, Z., Qin, Y., Shen, J., Sun, F., Xiao, Z., et al. A comprehensive survey on deep graph representation learning. Neural Networks, pp. 106207, 2024a.
Liu, Y., Zhang, W., and Wang. Source-free domain adap- tation for semantic segmentation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1215-1224, 2021.
Ju, W., Zhao, Y., Qin, Y., Yi, S., Yuan, J., Xiao, Z., Luo, X., Yan, X., and Zhang, M. Cool: a conjoint perspec- tive on spatio-temporal graph neural network for traffic forecasting. Information Fusion, 107:102341, 2024b. 2024b..
Lu, C., Liu, Q. Wang, C., Huang, Z., Lin, P., and He, L. Molecular property prediction: A multilevel quantum interactions modeling perspective. In Proceedings of the AAAI Conference on Artificial Intelligence, 2019.
Karmanov, A., Guan, D., Lu, S., El Saddik, A., and Xing, F. Efficient test-time adaptation of vision-language models. In Proceedings of the IEEE/CVF Conference on Com- puter Vision and Pattern Recognition, pp. 14162-14171, 2024.
Luo, J., Xiao, Z., Wang, Y., Luo, X., Yuan, J., Ju, W., Liu, L., and Zhang, M. Rank and align: Towards effective source-free graph domain adaptation. arXiv preprint arXiv:2408. 2024.
Kazius, J., McGuire, R., and Bursi, R. Derivation and validation of toxicophores for mutagenicity prediction. Journal of medicinal chemistry, 4811):312-320, 2005.
Luo, X., Zhao, Y., Qin, Y., Ju, W., and Zhang, M. Towards semi-supervised universal graph classification. IEEE Transactions on Knowledge and Data Engineering, 2023.
Kim, S., Lee, D., Kang, S., Lee, S., and Yu, H. Learning aapology-speciife experts for molecular property predic- tion. In Proceedings of the AAAI Conference on Artificial Intelligence, 2023.
achlaan, G. and Basford, K. E. Mixture models: In- ference and applications to clustering, volume 38. M. Dekker New York, 1988.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Mocerino, L., Rizzo, R. G., Peluso, V., Calimera, A., and Macii, E. Adaptta: adaptive test-time augmentation for reliable embedded convnets. In 2021 IFIP/IEFE 29th International Conference on Very Large Scale Integration (VLSI-SoC), pp. 1-6. IEEE, 2021.
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. In International Conference on Learning Representations, 2017.
Kundu, J. N., Venkat, N., Babu, R. source-free domain adaptation. In Proceedings of the JEEE/CVF conference on computer vision and pattern recognition, pp. 4553, 2020.
V., et al. Universal
Nado, Z., Padhy, S., Sculley, D., D' Amour, A., Lakshmi- narayanan, B., and Snoek, J. Evaluating prediction-timg batch normalization for robustness under covariate shift. arXiv preprint arXiv:2006. 10963, 2020.

---

Test-time Adaptation on Graphs via Adaptive Subgraph-based Selection and Regularized Prototypes
Orsini, F,, Frasconi, P., and De Raedt, L. Graph invariant kernels. In Proceedings of the twenty-fourth international joint conference artificial intelligence, volume 2015, 2015.
Tsybakov, A. B. Optimal aggregation of classifiers in sta- tistical learning. The Annals of Statistics, 32(1):135- 166, 2004. doi: 10/ 1214 /ttp//////////////
URL https:
pp.
Polyak, B. T. Gradient methods for minimizing function- als. Zhurnal vychislitel noi matematiki i matematicheskoi fiziki, 3(4):643-653, 1963.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In International Conference on Learning Representations, 2018.
Rauber, P. E., Falcão, A. X., and Telea A. C. Visualizing Time-Dependee Data Using Dynamic t-SNE. In Euro pp. 73-77, 2016.
Wale, N., Watson, A., and Karypis, G. Comparison of descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems, 14: 347-375, 2008
Reynolds, D. A. et al. Gaussian mixture models. Encyclo- pedia of biometrics, (65666666),) 2009.
Shi, B., Wang, Y., Guo, F., Shao, J., Shen, H., and Cheng, X. Improving graph domain adaptation with network hierarchy. Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pp. 1249-2255 2023.
Wang, D., Shelhamer, E.,, Liu, S., Olshausen, B., and Darrell, T. Tent: Fully test-time adaptation by entropy minimiza- tion. arXiv preprint arXiv:2006. 10726, 2020a.
Wang, Y., Li, C., Jin, W. Li, R., Zhao, J., Tang, J., and Xie, X. Test-time training for graph neural networks. arXiv preprint arXiv:22 N0.:22200088133, 2022.
Singh, S., Muhuri, S., Mishra, S., Srivastava, D., Shakya, H. K. and Kumar, N. Social network analysis: A sur- vey process, tools, and application. ACM Computing Surveys, 56(8):1-39, 2024.
Wang. Z., Wei, W., Cong, G., Li, X.-L., Mao, X.-L., and Qiu, M. Global context enhanced graph neural networks for session-based recommendation. In Proceedings of the 43rd international ACM SIGIR conference research and development in information retrieval, pp. 179-178, 2020b.
Stärk, H., Beaini, D., Corso, G., Tossou, P., Dallago, C., Günnemann, S., and Liò, P. 3d infomax improves gnns for molecular property prediction. In International Con- ference on Machine Learning, pp. 2022.
PMLR,
Wu, M., Pan, S., Zhou, C., Chang, X., and Zhu, X. Unsu- pervised domain adaptive graph convolutional networks. In www, 2020.
Sun, F-Y., Hoffmann, J., Verma, V., and Tang. J. Infograph: Unsupervised and cemi-supervised graph-level represen- tation learning via mutual information maximization. In International Conference on Learning Representations, 2020a.
Xu, J., Kim, S., Song, M., Jeong, M., Kim, D., Kang, J., Rousseau, F., Li, X., Xu, W., Torvik, V. I. et al. Build- ing pubmed knowledge graph. Scientific data, 7(1):205, 2020.
Sun, Y., Wang, X., Liu, Z., Miller, J., Efros, A., and Hardt, M. Test-time training with self-supervision for general- ization under distribution shifts. Proc. of International Conference on Machine Learning, 2020b.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
Tan, Y., Liu, Y., Long, G., Jiang. J., Lu, Q., and Zhang, C. Federated learning on non-iid graphs via structural knowl- edge sharing. In Proceedings of the AAAI Conference on Artificial Intelligence, 2023.
Xu, Y., Shang, L., Ye, J., Qian, Q.. Li, Y.-.,, Sun, B., Li, H., and Jin, R. Dash: Semi-supervised learning with dynamic thresholding. In International Conference on Machine Learning, pp. 11525-11536, PMLR, 2021.
Tarvainen, A. and Valpola, H. Mean teachers are better role models: Weight- consistency targets improve supi-supe deep learning results. In Advances in Neural Information Processing Systems, 2017.
Yanardag, and Vishwanathan, Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference knowledge discovery and data mining, pp. 1365-1374, 2015.
Tomar, D., Vray. G., Bozorgtabar, B., and Thiran, J. Tesla: Test-time self-learning with automatic adversarial aug- mentation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 20341- 20350, 2023.
Yang, S., Wang, Y., Van De Weijer, J., Herranz, L., and Jui, S. Generalized source-free domain adaptation. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 8978-8988 2021.
12

---

Test-time Adaptation on Graphs via Adaptive Subgraph-based Selection and Regularized Prototypes
Yin, N., Shen, L., Li, B., Wang, M., Luo, X., Chen, C., Luo, Z.., and Hua, X.-S. Deal: An unsupervised domain adaptive framework for graph-level classification. In Proc. of ACM International Conference on Multimedia, 2022.
Zhao, Y., Wang, C., Luo, X., Luo, J., Ju, W., Xiao, Z., and Zhang, M. Traci: A data-centric approach for multi- domain generalization graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pp. 13401-13409, 2025b.
Yoo, J., Shim, S., and Kang, U. agdel-ag augmenta- tion for accurate graph classification. In Proc. of ACM Web Conference, 2022.
Zheng, K., Liu, W., He, I.., Mei, T., Luo, J., and Zha, Z.-J. Group-aware label transfer for domain adaptive person re-identification. In Proceedings of the IEEE/CVF Con- ference on Computer Vision and Pattern Recognition, 2021.
You, Y., Chen, T., Sui, Y., Chen, T., Wang, Z., and Shen, Graph contrastive learning with augmentations. 2020.
Yuan, Z., Yan, Y., Jin, R., and Yang, T. Stagewise training accelerates convergence of testing error over sgd. Ad- vances in Neural Information Processing Systems, 32, 2019.
Zhang, B.. Wang, Y.. Hou, W. Wu, H., Wang, J., Oku- mura, M., and Shinozaki, T. Flexmatch: Boosting semi- supervised learning with curriculum pseudo labeling. In Advances in Neural Information Processing Systems, 2021a.
Zhang, M., Liu, K., Li, Y., Guo, S., Duan, H., Long, Y., and Jin, Y. Unsupervised domain adaptation for person re-identification via heterogeneous graph alignment. Proceedings of the AAAI conference on artificial intelli- gence, volume 35, pp.
2021b.
Zhang. M., Levine, S., and Finn, C. Memo: Test time robustness via adaptation and augmentation. Advances in neural information processing systems, 35:38629-38642, 2022.
Zhang. Z., Bu, J., Ester, M., Zhang, J., Yao, C., Yu, 7 and Wang, C. Hierarchical graph pooling with structure learning. arXiv preprint 191i 1.05954, 2019.
Zhang, Z., Liu, M., Wang, A., Chen, H., Li, Z., Bu, J., and He, B. Collaborate to adapt: Source-free graph domain adaptation via bi-directional adaptation. In Proceedings of the ACM on Web Conference 2024, pp. 664 675, 2024.
Zhao, Y., Luo, X., Ju, W., Chen, C., Hua, X.-S., and Zhang, M. Dynamic hypergraph structure learning for traffic flow forecasting, In 2023 IEEE 39th International Con- ference on Data Engineering (ICDE), pp. 2303-2316. IEEE, 2023.
Zhao, Y., Luo, X., Wen, H., Xiao, Z., Ju, W., and Zhang, M. Embracing large language models in traffic flow forecast- ing. arXiv preprint arXiv:2412. 12201, 2024.
Zhao, Y., Luo, J., Luo, X., Huang, J., Yuan, J., Xiao, Z., and Zhang, M. Attention bootstrapping for multi-modal test- time adaptation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pp. 28849-22557, 2025a.
13

---

Test-time Adaptation on Graphs via Adaptive Subgraph-based Selection and Regularized Prototypes
A. Proofs of Theorem 3.1
Proof. Before going into the details, we firstly introduce some auxiliary constants, that is,
12g(2/5)
a qmi(1 c- 1=
log(2/8)
log(2/0/
B = max
2q
1
2(1 4)²
60 (1 c )1 - B)(1
cr)g:
T [(W1), 4G
bu
00 2 ((1 q)(1 + 3T +log(1/)))
1
8aom
Note that when n1
max
106(2/6) 1og(2/8) 2q²
(2/(2/6) 2( (11-)22
q(1 172
for any E (0, 1) and < c < 6, a S and $ 1.
Next, we prove the Theorem 3.1 by showing that L(w,) I (t-1), At first, when 1 = 1, we have
((w1) ST= max (((wi).
4G² 1 + bo
do ))
δagm
This establishes the initial bound the induction. For the inductive step, we suppose that at some iteration T, with probability (4t + 1)8, the following inequality holds, namely, [(w;) S my Ty (t-1), We will show that this implies the bound on I(W.+1).
From the assumption of Theorem 3.1, we know that, at each time step I,, the total number of test graphs under consideration is given by n4 := n For the purpose of our analysis, we categorize all test graphs into two distinct classes based on their derivation. The first class, denoted as At, comprises samples originating from the distribution consists of samples drawn from the distribution P. while the second class, Bt, consists of test graphs from the distribution Q. Subsequently. we further refine both A, and B, by identifying those samples whose associated loss values fall below the predetermined threshold Pr. Mathematically, these subsets can be expressed as:
Aft = (E A, ((W,E)) pt).
D = (g E B, ((wr:)) S pt)
By leveraging the standard concentration inequalities in probability theory and recognizing the true that all sampling graphs used to compute the gradient g: are derived from the elements of A!" and B we can show the following results: With a probability 25,
log(2/5)
|A, 2 q7
1
(23)
2q
log(2/5)
B S (1 - g)mz
1+ | 2(1 9)
(24)
Next, based on the well-known inequality Pr(X 2 a) < that
E(X) for any nonnegative random variable X, we also can show
PTe~p(((Wr:E) 2 pr) E Egwp(((We:)) E)
[(we)
<
(25)
Pr
where the final inequality follows from ((ws)
< From the (25), we also can show that Prgap(((ww:)) S p.) 2 1 1-1
P1
14

---

Test-time Adaptation on Graphs via Adaptive Subgraph-based Selection and Regularized Prototypes
As result, have that, with probability 1 26,
log(2/8)
|4 PPPe- S pr)lArl
1 V (Prewpl (I(wi:)))
(26)
(1-2 Axl (1-
1
(2g(2/6)
2 2 2) |Aal
Merging Eq.(23) into (2,( we then can show that
1401 - :) (1
(1- (1-v)
1og(2/0) 2q
(1
log(2/5)
m4 2 a0717
(27)
(1 -1-1)3
Then, according the Tsybakov Condition, we derive that
Prewo (l(wriE) & pc) =Prewe (((v::)) _ Pt.
-((w))
[(w.) = PPesee & bl(ww))
E (I (I(w;it) S bL(w,))] < (w,)
(28)
I (Ty-(--)))" m
where the first inequality uses the assumption that Pt S bl(w) and L(w)) [0, 1], the second inequality utilizes the Tsybakov condition and the final inequality from the assumption of induction.
It is worth noting that, compared with (45) in (Xu et al., 2021), our former (28) utilizes more precise Tsybakov condition and threshold range assumption of Pt E [cC(w.). bc(w) to effectively bound the probability of random event (I(we:)) g) S pt)-
Like the (26), with (28), we also can show that
Eg [B(h
[B.
E // (l(Wri&s) S Pc)]
(29)
[B Pig-o(((Wi:E)) pi)
i=1
< By| (r7-
With this inequality Eq,(, according to the concentration inequality, we also can show that, with a probability - 25,
|B(1 < E EE
BB + log(1 (1/5) + V 1og2(1 (1/8) + 2
< <|Bil rr (1-2))
+ log(1/5) + Vg (1/8) 2100 (Fy (r)) B (Ty-((-1)
+ log(1/6)
(30)
log(2/5)
(1>-((-1)) m
<(1 "-1
1 1 V 2(1 nm
+ 2log((1))
<2(11 - 9) (1 + B) m log(1/0)) n
-byn.
15

---

Test-time Adaptation on Graphs via Adaptive Subgraph-based Selection and Regularized Prototypes Therefore, according the results of both (27) and Eq.(30), with a probability 48, we show that (t-1), [B S byrt1
A 2 (/
(31)
Our analysis of (31( reveals a striking pattern in the dynamics of the sample subsets. As iterations proceed, the size of the subset | exhibits exponential growth, while the subset [B remains tightly constrained within a fixed upper bound. This observation underscores the efficacy of our dynamic thresholding mechanism in progressively identifying and incorporating highly relevant unlabeled examples that align closely with the labeled data distribution.
Moreover, the selection process demonstrates remarkable stability, with the number of potential misclassifications maintained constant level throughout iterations. This balance between expansion and control enables our optimization framework to leverage increasing volume of informative unlabeled data without compromising the integrity of the learning process. In the subsequent analysis, we will demonstrate that these properties translate to significant improvements in model performance. Specifically, we will show that with high probability, the expected loss of the model parameters at each iteration satisfies the bound ((w+1)) & Ty
Before that, we also introduce some new auxiliary notations:
vi(weiE);;
IA
SEAT!
6
1
Σ
vi(we:E);
gi D
SEB"
|A |
by
1
7 (1-1),
7
[3
A
ag
With these new symbols, we can rewrite g: as = (1 by bz) + b.g.
Following L-smoothness of Assumption 3, we can have that
[(w) L(u)= S (VL(u), w u} + L w u u1/
(32)
According to (3., we also can have that
[( L(W:)
< <(VL(w)), w w.) + I.
2 | - well?
! (L(w)) - 1:112 2= - (IV + +1 (1- (11-11) L) 1|8:11²)
2
11 ((1 - VL((:) g bellV((w.) - gill²)
2
(IVL(()))] + (1-n4) ||g: 12)
2
" ((1 - b.)) V VL (w.) e + 4b, G2) m)[(w,)
where the first first equality follows the update of W(+1 Wt w the final inequality follows from Assumption 2, Assumption and 1 < 1. Then, we derive a bound for the expectation of ||V gf namely,
EguP
lg
VL(w:))l
1
=EgnP
vi(We:)) V(((W)
|AP'
SEAP"
1
402
EgNP [IV((WeiE) VL(w:)) <
SEA:
16

---

Test-time Adaptation on Graphs via Adaptive Subgraph-based Selection and Regularized Prototypes
Algorithm 2 Sinkhorn-Knopp Algorithm for Regularized Prototype Supervision
Input: scores S, temperature e, number of iterations n,
Output: Q as an approximation of Q"
1: Initialize the assignment Q t exp (S/e);
2: for i= ..,, n do
3: Normalize each row of Q to sum to N/C; 4: Normalize each column of Q to sum 1;
5: end for
6: return Q
Then, according concentration inequality, we have with probability 1 - 1-5
4G2
4G
I VL(w:)]l S
814
80gn1
As result,
[(W(+1) [(w.)
4G2
7 (1-b,)- Jaon + 41b,G2 :)/[(we)
(33)
2 saun1yt-1 + 44
"
402
bp
& 7111-)) nul(ww)
a0
+ to
-2n
y 7-(1-1) nul(w.),
(34)
dagni
ao
where the second inequality follows from the Finally, we have that
S ln (t-1)
ao
[(we41) $ (1-m)))((w)) + 2n ( (8amm) tbi -(1-1)
(35)
Then, we y = I-nu/2 we know that
1
bo
((W(+1) ST(1 - +
--
8anni
ag
Mu/2
mH//2
4G²
bo
Ty- +
7
1-11122
7/1/22
/
8aga1
do
where the first inequality follows from the induction assumption and the final inequality follows from
1G²
+
baony
ao
B. Details of the Sinkhorn-Knopp Algorithm
In this section, we provide introduction of the Sinkhorn- Knopp algorithm. Specifically, compute the matching score of the prototypes and the graph-level representations as S = Rº Z, and initialize the assignment as Q exp(S/t), where e is the temperature. Then, we iteratively perform row normalization and column normalization of the assignment matrix such that it follows the constraints in Eq. 12. After n iterations, we obtain an approximation the optimal assignment Q' as Q. The algorithm is summarized in Algorithm 2. Prior studies (Caron et al., 2020; Asano et al., 2019; Zheng et al., 2021) suggest that this algorithm converges quickly, and in practice setting n to 3 yields decent approximations.
17

---

Test-time Adaptation on Graphs via Adaptive Subgraph-based Selection and Regularized Prototypes
Table 5. Adaptation time (slepoch) and the number of epochs converge of the proposed ASSESS.
Dataset
FRAN
MUTA
PROT
NCI1
IMDB
Time (s/epoch)
0.21
0.11
0.06
0.14
0.04
Epochs
~0
10~-20
10~20
10~20
~03
C. Time Complexity and Efficiency Analysis
For the GNN backbone, the time complexity is E), where Nie is the number of test graphs and E is the average number of edges. For ASBS, Eq. 10 has a time complexity of (NNNe,), where B is the batch size. Then the model updates the threshold correction fuucciin recursively (Eq. 12), and selects reliable graphs (Eq. 13), which leads to O(Ne).. ). In RPS, Sinkhorn- Sankhom-Knopp algorithm has a time complexity of O(BC) for each batch, where C' is the number of classes. Eq. 23 also has a time complexity of (BBC) for each batch. For each epoch, the time complexity is (CNNe)). The whole algorithm has a time complexity of O(N(e F),, assuming constant batch size B and number of classes C, which is equivalent to most GNNs. In practice, the adaptation converges few seconds, shown in Table 5.
D. Details of the Datasets and Dataset Splits
In this paper, we perform extensive experiments on five representative datasets, i.e. FRANKENSTEIN (Orsini et al., 2015), Mutangenicity (Kazius et al., 2005), PROTEINS (Borgwardt et al., 2005), NCI1 (Wale et al., 2008), and IMDB- BINARY (Yanardag& & Vishwanathan, 2015). We split each dataset into three subsets, i.e. FRANKENSTEIN (FO, F1, F2), Mutangenicity (MO, M1, M2), PROTEINS (PO, P1, P2), NCI1 (NO, N1, N2), and IMDB-BINARY (IO, I1, 12). The datasets partitioned according to the density of the graphs, which is defined as
2
D V
(36)
where D denotes density, EE| denotes the number of edges, and [V| denotes the number of nodes. The graphs are then sorted in ascending order according to the density and then partitioned into three dataset splits. Among the dataset partitions, FO, MO, PO, NO, and I0 have the smallest density values, while F2, M2, P2, N2, and 12 have the largest density values. We provide a detailed description of the datasets as follows:
FRANKENSTEI (Orsini al., 2015) is dataset created by combining the BURSI and MNIST datasets. FRANKEN- STEIN modifies the BURSI dataset by removing bond type information and replacing the most common atom symbols with MNIST digit images. The original atom symbols are now encoded in the MNIST images' pixel intensity vectors, making it a challenging dataset.
Mutagenicity (Kazius et al., 2005) is proposed by Kazius et al. and involves a wide range of molecular structures, each intricately associated with its respective Ames test data, totaling 4,337 molecular structures.
PROTEINS (Borgwardt et al., 2005) is proposed by Borgwardt et al., and comprises protein data represented graphs, with each graph's 's label identifying if a protein is a non-enzyme. In this dataset, amino acids are depicted as nodes, and edges are drawn between nodes when the distance between two amino acids is less than 6 angstroms.
NCI1 (Wale et al., 2008) is derived from the National Cancer Institute (NCI) database, which includes large collection of compounds. Each graph in the NCI1 dataset has a label indicating whether a compound is active or inactive.
IMDB-BINARY (Yanardag & Vishwanathan, 2015) consists of graphs derived from IMDB, the Internet Movie Database, where each graph represents the ego-network of movie. In these graphs, nodes represent actors/actresses, and edges indicate that two actors appeared in the same movie. The primary objective with this dataset is to classify each graph into one of two categories based on the genre of the movie.
18

---

Test-time Adaptation on Graphs via Adaptive Subgraph-basee Selection and Regularized Prototypes
Before Adaptation
After Adaptation
PO -
PO - P2
P2 - PO
P2 -
Figure Additional visualization learned representations test graphs under distribution shifts on the PROTEINS dataset. The learned embeddings before and after adaptation is displayed.
E. Details of the Baseline Methods
The proposed method is compared to wide range of baseline methods, including graph neural networks (GCN (Kipf Welling, 2017), GraphSAGE (Hamilton et al., 2017). GIN (Xu al., 2019). and GAT (Veličković al., 2018)), unsupervised semi-supervised training methods Teachrr (Tarvainen & Valpola, 2017) and GraphCI. (You al., 2020)), test-time adaptation methods (SHOT (Liang et al., 2020) and TAST (Jang al., 2023)). We introduce these methods in more detail as follows:
GCN (Kipf & Welling, 2017) is foundational model that generalizes convolutional neural networks (CNNs) to graphs, efficiently aggregating neighborhood information to generate node representations,
GraphSAGE (Hamilton al., 2017) extends GCN by sampling and aggregating vectorized representations from the node's neighborhood, enabling handle large graphs dynamically.
GIN (Xu et al., 2019) is proposed by Xu et al. and addresses the limitation of existing graph neural network models in distinguishing graph structures by learning to represent graphs in a way that preserves the graph isomorphism property, which effectively captures the topology of the graph data.
GAT (Veličković et al., 2018) adopts the attention mechanism to the aggregation step in graph neural networks, enabling nodes to generate weights for the importance of their neighbors dynamically to achieve more effective feature integration.
McanTeacher (Tarvainen Valpola, 2017) is robust semi-supervised or unsupervised learning algorithm that utilizes student model for making predictions and teacher model to create training targets.
GraphCL (You et al., 2020) introduces graph contrastive learning framework aimed at advancing semi- cemi-supervised or unsupervised representation learning on graphs. It utilizes augmentations to embed various priors into the learning process.
SHOT (Liang al., 2020) (Source HypOthesis Transfer) fixes the classifier module (hypothesis) of the prediction model while learning feature extraction module specific the target domain. This process leverages information maximization and pseudo-labeling techniques for implicit alignment of the representations in target domains with the source hypothesis.
TAST (Jang et al., 2023) (Test-time Adaptation via Self- Seff-nrainin with nearest neighbor information) gathers valuable information for classifying test data under domain shifts by leveraging information from nearest neighbors and employing various randomly initialized adaptation modules.
19

---

Test-time Adaptation on Graphs via Adaptive Subgraph-based Selection and Regularized Prototypes
RNA (Luo al., 2024) (Rank and Align) ranks graph similarities achieve robust semantic learning, and then aligns inharmonic graphs with harmonic graphs for subgraph extraction.
F. A Aditional Visualization of Learned Representations
In this section, we provide more visualization results of learned representations on the test graphs. More specifically, we use t-SNE (Rauber et al., 2016) in alignment with Section 4.5, and the results are shown Figure 5. As can seen from the results, the representations after adaptation are more clustered, which leads better classification accuracy. Moreover, as we can see from the results, vanilla graph neural networks fall short in dealing with distribution shifts. The representations they learn from test graphs that experience distribution shifts mixed and hard differentiate. By comparison, the proposed method adapt the model to the test graphs, without any ground truth labels from the test graphs, and improve the learned representations significantly.
satisfactory, in that the embeddings of two classes
20


Reviews:
[{"review_id": "XShUYBr5g2", "reviewer": "Reviewer_kK35", "summary": "This paper proposes an algorithm ASSESS that handles graph test time domain adaptation for graph-level task. The algorithm mainly contain two components as the adaptive subgraph-based selection and regularized prototype supervision. The subgraph-based selection tends to select reliable test graphs by setting individual graph threshold using the mutual information between the subgraphs. Then, with the selected reliable sets of test graphs, they first construct the prior prototypes as the weight matrix of pretrained model as prior knowledge. Then, the prototype and model are updated with the self-supervised objective that enforces the matching of prototype with corresponding class embeddings of test graphs under the regularization enforcing close distance of updated prototypes to prior prototypes. This paper also provides the convergence analysis of the algorithm and demonstrate superior performance compared to GNN baselines and test-time adaptation baselines.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are truly grateful for the time you have taken to review our paper and your insightful review. Here we address your comments in the following.\n\n> Q1. Lack of illustration and more concrete motivation behind the unique challenge appear for graph TTA in the introduction. For instance, what can be the challenges of TTA under structural shifts within these datasets and why they cannot be addressed by previous algorithms. The second challenge seems to be non-unique to graph data.\n\n**A1**. Thanks for your comment. The shift on both node attributes and graph structures would deteriorate the performance of GNNs according to [A]. Previous works often select reliable samples for self-training using fixed thresholds shared across all graphs, which is not flexible enough to handle the complex distribution shifts (both attributes and structures).\n\nAs for the second part, our paper focuses on graph TTA. Compared with traditional TTA, the complexity of graph-level data makes the problem challenging. We will try to extend our method to other types of data, and leave it to future work. \n\n[A] Matcha: Mitigating Graph Structure Shifts with Test-Time Adaptation. ICLR'25\n\n\n> Q2. It could be better if we motivate the algorithm design in a more theoretical manner. For instance, why in principle checking the mutual information of subgraphs ... Also, is the random selection of subgraph to calculate mutual information the best way?\n\n**A2**. Thanks for your comment. A high MI between a graph and its subgraphs indicates that the graph representation encodes information shared across its subgraphs. In other words, the encoder is able to handle the inherent structure of this graph. To validate it, we compare our method with other variants and show that MI can achieve the best performance.\n\n|Indicators|PROTEINS|IMDB-BINARY|\n|-|-|-|\n|MI| 78.9 |67.8 |\n|Entropy|71.8|64.7|\n|Confidence|69.5|64.5|\n\nRandom selection is simple yet effective here. To validate it, we provide the empirical results (compared to edge perturbation, removing and adding edges with probability $p$).\n\n|Strategies|PROTEINS|IMDB-BINARY|\n|-|-|-|\n|Random Subgraph|78.9|67.8|\n|Edge perturbation, $p=0.1$|76.3|66.7|\n|Edge perturbation, $p=0.2$|75.7|66.1|\n|Edge perturbation, $p=0.3$|74.2|65.4|\n\n\n> Q3. The design of regularized prototype supervision is kind of independent to the graph structure and can also be applied to euclidean data. Also, the idea of similar prototype or template adjustment [1] has been used ...\n\n**A3**. Thanks for your comment. This work focuses on graph data, but our regularized prototype supervision is a universal design, which is incorporated into our graph TTA methods. We are committed to extending our design to other types of data, and leave it to future work. \n\nOur work is different from T3A (Iwasawa et al.) in the following aspects:\n* **Different Motivation**: T3A is motivated by the idea of support set, whereas our ASSESS is motivated by Bayesian theory.\n* **Different Methodology**: T3A maintains a support set for each class using the test samples, and uses the support set for classification. By comparison, we use optimal transport to obtain the prototypes, which are used as supervision signals with regularization from the prior.\n* **Different Scenario**: T3A focuses on the domain generalization of images, whereas we focus on test-time adaptation of graphs.\n\nMoreover, empirical results in A5 show that our method outperforms T3A.\n\n> Q4. I expect some more analysis in terms of the rationales of the algorithm as mentioned above.\n\n**A4**. Thanks for your comment. The overall rationale is to first select (ASBS, as discussed in A2) and then supervise (RPS, A3). Due to limited length, please refer to previous answers.\n\n\n> Q5. There are assumptions of the theorem that might be a bit oversimplified, e.g. the distribution of the test unlabeled graphs as the mixture of two distributions.\n\n**A5**. Thanks for your comment. Without loss of generality, we consider a mixture of two distributions, and it can easily be generalized to cases with multiple distributions.\n\n\n> Q6. Lack of TTA and GTTA baselines ...\n\n**A6**. Thanks for your comment. We add additional TTA (T3A) and GTTA (GAPGC, MATCHA) baselines as follows.\n\n|Methods|PROTEINS|IMDB-BINARY|\n|-|-|-|\n|ASSESS (ours)|78.9|67.8|\n|T3A|69.3|64.3|\n|GAPGC|71.9|65.1|\n|MATCHA|73.2|65.8|\n\n\n> Q7. The performance over different variants of the algorithms are very close, even within one std. ...\n\n**A7**. Thanks for your comment. We provide additional ablation studies on other datasets as follows, and we can find a clear improvement overall on these datasets. \n\n|Methods|PROTEINS|IMDB-BINARY|\n|-|-|-|\n|ASSESS|78.9 $\\pm$ 3.8|67.8 $\\pm$ 2.9|\n|w/o ASBS|66.7 $\\pm$ 3.5|63.9 $\\pm$ 2.6|\n|w/o RPS-a|69.2 $\\pm$ 3.9|64.1 $\\pm$ 2.9|\n|w/o RPS-b|70.9 $\\pm$ 4.0|64.2 $\\pm$ 2.8|\n\n**Others**: Related works and figure 1.\n\nThanks for your comment. We will add more related works (e.g., GAPGC, MATCHA, etc.) and details in Figure 1.", "claims_and_evidence": "**Strength:**\n- The test time adaptation on graph specifically for graph-level task is an under-explored direction that worth more investigation and understanding. \n- The selected datasets span a wide range of real world applications\n\n**Weakness:**\n- Lack of illustration and more concrete motivation behind the unique challenge appear for graph test-time adaptation in the introduction. For instance, what can be the challenges of test-time adaptation under structural shifts within these datasets and why they cannot be addressed by previous algorithms. The second challenge seems to be non-unique to graph data.", "methods_and_evaluation_criteria": "**Strength:**\n- The propose method is clear in objective regarding the two modules\n- The methodology is written clearly and easy to read\n\n**Weakness:**\n- It could be better if we motivate the algorithm design in a more theoretical manner. For instance, why in principle checking the mutual information of subgraphs and the whole graph can be a good indicator to select reliable test graphs. Also, is the random selection of subgraph to calculate mutual information the best way?\n- The design of regularized prototype supervision is kind of independent to the graph structure and can also be applied to euclidean data. Also, the idea of similar prototype or template adjustment [1] has been used in previous literature, which limits the novelty.\n\n[1]. Iwasawa, Yusuke, and Yutaka Matsuo. \"Test-time classifier adjustment module for model-agnostic domain generalization.\" Advances in Neural Information Processing Systems 34 (2021): 2427-2440.", "theoretical_claims": "- The theoretical analysis mainly targets the convergence, while I expect some more analysis in terms of the rationales of the algorithm as mentioned above. \n- There are assumptions of the theorem that might be a bit oversimplified, e.g. the distribution of the test unlabeled graphs as the mixture of two distributions.", "experimental_designs_or_analyses": "**Strength:**\n- The datasets span a wide range of fields\n- There is ablation study investigating the impact of different components\n\n**Weakness/Questions:**\n- Lack of TTA and GTTA baselines: over half of the baselines are not designated for test-time adaptations and there are only 2 non-graph TTA baselines and 1 graph TTA baseline. \n- The performance over different variants of the algorithms are very close, even within one std. Does that imply that there is no clear and significant difference in contribution from different components in ASSESS.", "relation_to_broader_scientific_literature": "This paper can let people pay more attention to the graph test time adaptation problem.", "essential_references_not_discussed": "More discussion of the graph test time adaptations are needed in the related work section in addition to the test-time adaptation for euclidean data.", "other_strengths_and_weaknesses": "Please refer to the above sections.", "other_comments_or_suggestions": "It might be better if you illustrate more details in pipeline design for figure 1.", "questions_for_authors": "Please refer to the above sections.", "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": "y8srtuYvCz", "reviewer": "Reviewer_reVF", "summary": "This paper investigates the problem of test-time adaptation on graphs, addressing the challenge of adapting a pre-trained graph neural network (GNN) to unseen test data without access to the original training set. The authors propose ASSESS (Adaptive Subgraph-based SElection and Regularized Prototype SuperviSion), a novel method that combines graph selection and prototype regularization to enhance adaptation performance under distribution shifts. The paper also presents a rigorous theoretical analysis about ASSESS. Empirical evaluations on five diverse graph datasets confirm the superior performance of ASSESS over state-of-the-art baselines, with ablation studies further highlighting the contributions of its components.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are truly grateful for the time you have taken to review our paper, your insightful comments and support. Your positive feedback is incredibly encouraging for us! In the following response, we would like to address your concerns and provide additional clarification.\n\n\n> Q1. While the paper focuses on test-time adaptation, it does not explicitly discuss connections to related topics such as graph domain adaptation and out-of-distribution (OOD) generalization. Since ASSESS deals with distribution shifts at test time, its relationship to existing methods in transfer learning should be discussed.\n\n**A1**. Thank you for your suggestion. We will add discussions to related topics in the revised version. Here we provide a brief comparison. TTA aims to adapt a well-trained model without accessing the source data. Domain adaptation allows access to source data, which is different from TTA. OOD generalization focuses on building generalizable models during training, whereas TTA focuses on the test phase.\n\n\n> Q2. The authors introduce a temporal ensembling strategy to stabilize the estimation of mutual information in the adaptive subgraph selection process (Eq. 5). However, the motivation for why this specific technique was chosen is not clearly explained.\n\n**A2**. Thanks for your comment. Temporal ensembling is used to stabilize the estimation of mutual information. It is costly to sample a lot of subgraphs to compute the mutual information estimation, and a lack of samples may lead to unstable MI estimation. Therefore, we use the temporal ensembling technique to stabilize the estimation of mutual information.\n\n\n> Q3. The paper does not specify whether the selected datasets cover both homophilic and heterophilic graphs. Homophilic graphs exhibit strong intra-class connectivity, while heterophilic graphs contain nodes that connect across different classes. Since GNN performance varies significantly based on graph structure, it is important to explicitly discuss the structural diversity of the datasets.\n\n**A3**. Thanks for your comment. The adopted datasets contain both homophilic and heterophilic graphs, and we show the homophily ratio of these datasets as follows:\n\n|Datasets|FRAN|MUTA|PROTEINS|NCI1|IMDB-BINARY|\n|-|-|-|-|-|-|\n|Homophily Ratio|0.04|0.37|0.92|0.62|0.67|\n\n\n> Q4. The paper presents inconsistent descriptions of how the ASBS and RPS components interact within the overall adaptation framework. Figure 1 suggests that ASBS and RPS operate in parallel, implying that reliable test graphs are selected and then immediately used for self-training. However, Section 3.4 and the provided loss formulation (Eq. 17) indicate an iterative execution, where ASBS first refines the test graph selection over multiple steps before RPS is applied.\n\n**A4**. Thanks for the comment. Selection and adaptation are performed iteratively. In each iteration, we select reliable test graphs using ASBS and then adapt the model using RPS. The ASBS is integrated in the overall optimization process, where the optimization computes losses (including the MI loss), and the MI loss is used to guide the reliable graph selection process in ASBS.\n\n**Other typos**:\n> The format of some equations could be improved (e.g. Eq 12-15).\n> In Line 223, \"large\" should be \"larger\".\n> In Line 253, \"closed form\" should be \"closed-form\".\n\nThank you for your careful review! We will correct these in the revised version.", "claims_and_evidence": "All the claims are supported by theoretical or experimental evidences.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes. I have checked the theoretical claims in section 3, including the proof in the appendix.", "experimental_designs_or_analyses": "Yes. I have checked the experimental designs, the use of datasets, ablation studies, etc.", "relation_to_broader_scientific_literature": "As graphs neural networks are widely used in processing non-Euclidean data, such as proteins or social networks, their performance under test-time distribution shifts is an important aspect of the robustness of many algorithms.", "essential_references_not_discussed": "This paper could benefit from a discussion of other works graph transfer learning, e.g. [1][2].\n\n[1] Structural Re-weighting Improves Graph Domain Adaptation (ICML’23)\n[2] Learning invariant graph representations for out-of-distribution generalization (NeurIPS’22)", "other_strengths_and_weaknesses": "Strengths:\n1. The paper provides a well-structured and comprehensive theoretical analysis of the proposed ASSESS algorithm, demonstrating its convergence properties under test-time adaptation settings. The analysis is grounded in established optimization assumptions, such as the Polyak-Łojasiewicz condition and the Tsybakov noisy condition, providing a strong mathematical foundation for the method’s effectiveness.\n2. The proposed method is evaluated on five real-world graph datasets, each of which represents different domains. The authors compare their approach against a diverse set of baselines, including graph neural networks, unsupervised/semi-supervised training methods, and test-time adaptation algorithms. The results consistently show improvements in classification accuracy.\n3. The ablation results provide strong empirical evidence that both components are crucial for achieving state-of-the-art performance in test-time adaptation on graphs.\n\nWeaknesses:\n1. While the paper focuses on test-time adaptation, it does not explicitly discuss connections to related topics such as graph domain adaptation and out-of-distribution (OOD) generalization. Since ASSESS deals with distribution shifts at test time, its relationship to existing methods in transfer learning should be discussed.\n2. The authors introduce a temporal ensembling strategy to stabilize the estimation of mutual information in the adaptive subgraph selection process (Eq. 5). However, the motivation for why this specific technique was chosen is not clearly explained.\n3. The paper does not specify whether the selected datasets cover both homophilic and heterophilic graphs. Homophilic graphs exhibit strong intra-class connectivity, while heterophilic graphs contain nodes that connect across different classes. Since GNN performance varies significantly based on graph structure, it is important to explicitly discuss the structural diversity of the datasets.\n4. The paper presents inconsistent descriptions of how the ASBS and RPS components interact within the overall adaptation framework. Figure 1 suggests that ASBS and RPS operate in parallel, implying that reliable test graphs are selected and then immediately used for self-training. However, Section 3.4 and the provided loss formulation (Eq. 17) indicate an iterative execution, where ASBS first refines the test graph selection over multiple steps before RPS is applied.", "other_comments_or_suggestions": "1. The format of some equations could be improved (e.g. Eq 12-15).\n2. In Line 223, \"large\" should be \"larger\".\n3. In Line 253, \"closed form\" should be \"closed-form\".", "questions_for_authors": "Please refer to the weakness section.\n\nI may change my score based on the authors' feedback regarding the weaknesses.", "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": "dC3XsxHPMS", "reviewer": "Reviewer_UR8t", "summary": "This paper find that existing graph neural network methods struggle with performance degradation when adapting to test-time domain shifts, and current test-time adaptation methods for graphs mainly focus on Euclidean data and face challenges with label scarcity and knowledge utilization. The authors propose ASSESS framework that enables fine-grained and structure-aware selection of reliable test graphs, effectively balances prior knowledge from unknown training graphs and posterior information from unlabeled test graphs, and achieves significant improvement in test-time adaptation on graphs.\n\n## update after rebuttal:\nThe authors' rebuttal address most of my concerns, so I keep my score to \"weak accept\".", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are truly grateful for the time you have taken to review our paper, your insightful comments and support. Your positive feedback is incredibly encouraging for us! In the following response, we would like to address your concerns and provide additional clarification.\n\n> Q1. However, I notice that the authors make lots of assumptions in the paper. I think a brief discussion of how these assumption affects the generality of the result would be helpful.\n\n**A1**. Thank you for your suggestion. The addition, multiplication, and the ReLU function can be found to satisfy these assumptions. Our full neural network is a combination of these operations, which satisfy these assumptions as well. Similar assumptions can be found in recent works [1], [2], [3], and [4].\n\n[1] A convergence theory for deep learning via over-parameterization, ICML'19\n\n[2] Stagewise training accelerates convergence of testing error over SGD, NeurIPS'19\n\n[3] Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm, JMLR'24\n\n[4] Efficient active learning halfspaces with Tsybakov noise: A non-convex optimization approach, AISTATS'24\n\n\nWe will discuss this in the revised version of the manuscript.\n\n\n> Q2. As far as I know, there are many different settings for TTA, such as online or offline, as well as batch size settings, and they should be different from source-free methods such as SHOT and RNA. I think the authors should provide a detailed explanation of their TTA settings and compare more TTA methods under the same settings.\n\n**A2**. Thank you for your suggestion. We follow the existing work [5] to adopt the offline setting of TTA. We compare additional TTA methods under the offline setting, and the results show that our method achieves better accuracy.\n\n|Methods|PROTEINS|IMDB-BINARY|\n|-|-|-|\n|ASSESS (ours)|78.9|67.8|\n|T3A [6]|69.3|64.3|\n|GAPGC [7]|71.9|65.1|\n|MATCHA [8]|73.2|65.8|\n\n[5] Test-Time Training for Graph Neural Networks, arXiv'22\n\n[6] Test-Time Classifier Adjustment Module for Model-Agnostic Domain Generalization, NeurIPS'21\n\n[7] GraphTTA: Test Time Adaptation on Graph Neural Networks, ICML'22\n\n[8] Matcha: Mitigating Graph Structure Shifts with Test-Time Adaptation, ICLR'25\n\n\n> Q3. The author only compared the methods related to source-free setting in the experimental comparison. I think the most advanced TTA methods should be compared under the graph setting.\n\n**A3**. Thank you for your comment. We evaluate additional TTA methods under the offline graph setting, and the results are shown in A2. We will add these in the revised manuscript.\n\n\n> Q4. The datasets (e.g., FRANKENSTEIN, Mutagenicity) focus on chemical and social graphs. Including other graph types (e.g., knowledge graphs, citation networks) would better demonstrate generalizability.\n\n**A4**. Thank you for your comment. We provide an additional citation network dataset (DBLP_v1), and the results are shown as follows:\n\n|Methods|ASSESS (ours)|T3A|GAPGC|MATCHA|\n|-|-|-|-|-|\n|DBLP_v1|89.4|83.1|84.6|86.7|\n\n\n> Q5. I think the author should use the entropy-based method and the subgraph-based method to compare the results during the selection stage, highlighting the advantages of subgraph-based selection.\n\n**A5**. Thank you for your suggestion. We compare our ASBS with entropy-based selection, and the results below show that our method outperforms entropy-based selection. \n\n|Selection Strategies|PROTEINS|IMDB-BINARY|\n|-|-|-|\n|ASBS| 78.9 |67.8 |\n|Entropy|71.8|64.7|\n\n\n> Q6. I would like to know how many subgraphs the author will choose for estimation calculation, as well as how the adaptation time of ASSESS compares to other baseline methods.\n\n**A6**. Thank you for your comment. We use one subgraph for the estimation, and rely on temporal ensembling (as mentioned in Line 192-197, around Eq. 5) to obtain stable estimation of mutual information. As for the adaptation time, we want to emphasize that GNNs are relatively light-weight, and computation is very fast. We compare the adaptation time of ASSESS with baselines below, and the results show that our computation time is comparable to other methods.\n\n|Methods|ASSESS (ours)|RNA|MATCHA|\n|-|-|-|-|\n|FRANKENSTEIN|2.1s|2.5s|2.0s|\n|Mutagenicity|1.7s|2.0s|1.5s|", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, the proof of Theorem 3.1 is correct and well-constructed. However, I notice that the authors make lots of assumptions in the paper. I think a brief discussion of how these assumption affects the generality of the result would be helpful.", "experimental_designs_or_analyses": "Yes, the paper evaluates ASSESS on five datasets spanning different domains and compares ASSESS with a range of baselines. As far as I know, there are many different settings for TTA, such as online or offline, as well as batch size settings, and they should be different from source-free methods such as SHOT and RNA. I think the authors should provide a detailed explanation of their TTA settings and compare more TTA methods under the same settings.", "relation_to_broader_scientific_literature": "The key distributions of this paper extend on graph representation learning, domain adaptation, self-supervised learning and test-time adaptation.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "**Strength:**\n1. The paper addresses an under-explored problem: test-time adaptation on graph-structured data.\n2. The proposed method, ASSESS, combines two innovative components: Adaptive Subgraph-based Selection (ASBS) and Regularized Prototype Supervision (RPS). The use of subgraph mutual information for adaptive thresholding and the construction of semantic prototypes are well-motivated ideas.\n3. The paper is well-written and logically structured.\n\n**Weakness:**\n1. The author only compared the methods related to source-free setting in the experimental comparison. I think the most advanced TTA methods should be compared under the graph setting.\n2. The author lacks specific settings for the TTA experiment, such as whether it is online or offline, and whether the sample is a streaming input, etc.\n3. The datasets (e.g., FRANKENSTEIN, Mutagenicity) focus on chemical and social graphs. Including other graph types (e.g., knowledge graphs, citation networks) would better demonstrate generalizability.", "other_comments_or_suggestions": "I think the author should use the entropy-based method and the subgraph-based method to compare the results during the selection stage, highlighting the advantages of subgraph-based selection.", "questions_for_authors": "I would like to know how many subgraphs the author will choose for estimation calculation, as well as how the adaptation time of ASSESS compares to other baseline methods.", "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:

Meta-review: This paper introduces ASSESS, an innovative framework for test-time adaptation (TTA) on graphs, addressing the under-explored challenge of domain shifts in non-Euclidean data. The method combines adaptive subgraph selection via mutual information and prototype regularization to balance prior knowledge from pretrained models with test-time data. 

Reviewers highlight several strengths: rigorous theoretical analysis of convergence properties, comprehensive empirical validation across diverse graph datasets (including homophilic/heterophilic structures), and clear performance gains over baselines like T3A and GAPGC. While concerns were raised about the theoretical motivation for subgraph mutual information and potential overlaps with prototype-based methods, the authors’ rebuttals address these via ablation studies and comparisons, demonstrating ASSESS’s unique value in graph-structured TTA. The authors are encouraged to carefully revise the paper according to the reviewers' concerns.
Decision: Accept (poster)