Test-time Adaptation on Graphs via Adaptive Subgraph-based Selection and Regularized Prototypes

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.

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.

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

[1] A convergence theory for deep learning via over-parameterization, ICML'19

[2] Stagewise training accelerates convergence of testing error over SGD, NeurIPS'19

[3] Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm, JMLR'24

[4] Efficient active learning halfspaces with Tsybakov noise: A non-convex optimization approach, AISTATS'24

We will discuss this in the revised version of the manuscript.

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.

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.

[5] Test-Time Training for Graph Neural Networks, arXiv'22

[6] Test-Time Classifier Adjustment Module for Model-Agnostic Domain Generalization, NeurIPS'21

[7] GraphTTA: Test Time Adaptation on Graph Neural Networks, ICML'22

[8] Matcha: Mitigating Graph Structure Shifts with Test-Time Adaptation, ICLR'25

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.

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.

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.

A4. Thank you for your comment. We provide an additional citation network dataset (DBLP_v1), and the results are shown as follows:

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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:

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.

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.

Other typos:

The format of some equations could be improved (e.g. Eq 12-15). In Line 223, "large" should be "larger". In Line 253, "closed form" should be "closed-form".

Thank you for your careful review! We will correct these in the revised version.

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.

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.

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

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

[A] Matcha: Mitigating Graph Structure Shifts with Test-Time Adaptation. ICLR'25

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?

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.

Random 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$).

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

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.

Our work is different from T3A (Iwasawa et al.) in the following aspects:

• Different Motivation: T3A is motivated by the idea of support set, whereas our ASSESS is motivated by Bayesian theory.
• 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.
• Different Scenario: T3A focuses on the domain generalization of images, whereas we focus on test-time adaptation of graphs.

Moreover, empirical results in A5 show that our method outperforms T3A.

Q4. I expect some more analysis in terms of the rationales of the algorithm as mentioned above.

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.

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.

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.

Q6. Lack of TTA and GTTA baselines ...

A6. Thanks for your comment. We add additional TTA (T3A) and GTTA (GAPGC, MATCHA) baselines as follows.

Q7. The performance over different variants of the algorithms are very close, even within one std. ...

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.

Others: Related works and figure 1.

Thanks for your comment. We will add more related works (e.g., GAPGC, MATCHA, etc.) and details in Figure 1.