Empowering Graph Representation Learning with Test-Time Graph Transformation
Authors: Wei Jin
Tong Zhao
Jiayuan Ding
Yozen Liu
Jiliang Tang
Neil Shah
Venue: ICLR 2023 poster (2023)
Keywords: graph neural networks
out-of-distribution generalization
adversarial robustness

Abstract: As powerful tools for representation learning on graphs, graph neural networks (GNNs) have facilitated various applications from drug discovery to recommender systems. Nevertheless, the effectiveness of GNNs is immensely challenged by issues related to data quality, such as distribution shift, abnormal features and adversarial attacks. Recent efforts have been made on tackling these issues from a modeling perspective which requires additional cost of changing model architectures or re-training model parameters. In this work, we provide a data-centric view to tackle these issues and propose a graph transformation framework named GTrans which adapts and refines graph data at test time to achieve better performance. We provide theoretical analysis on the design of the framework and discuss why adapting graph data works better than adapting the model. Extensive experiments have demonstrated the effectiveness of GTrans on three distinct scenarios for eight benchmark datasets where suboptimal data is presented. Remarkably, GTrans performs the best in most cases with improvements up to 2.8%, 8.2% and 3.8% over the best baselines on three experimental settings. 

Published as a conference paper at ICLR 2023
EMPOWERING GRAPH REPRESENTATION LEARNING WITH TEST- GRAPH TRANSFORMATION
Wei Jin Tong Z Jiayuan Ding', Yozen Liu?, Jiliann Tang' and Neil Shah?
Miihhian State University SSnap Inc. {i (jinwei2, cingjia5, tangjiiiiiii (emejilllmmsueeee.. {tzhao, yliu2, nshaa)jesnap.com
ABSTRACT
As powerful tools for representation learning on graphs, graph neural networks (GNNs) have facilitated various applications from drug discovery to recommender systems. Nevertheless, the effectiveness of GNNs is immensely challenged by is- sues related to data quality, such as distribution shift, abnormal features and ad- versarial attacks. Recent efforts have been made tackling these issues from a modeling perspective which requires additional cost of changing model archi- tectures re-training model parameters. In this work, provide a data-centric view to tackle these issues and propose a graph transformation framework named GTRANS which adapts and refines graph data test time achieve better per- formance. We provide theoretical analysis on the design of the framework and discuss why adapting graph data works better than adapting the model. Exten- sive experiments have demonstrated the effectiveness of GTRANS on three dis- tinct scenarios for eight benchmark datasets where suboptimal data presented. Remarkably, GTRRANS performs the best in most cases with improvements up to 2.8%, 8.2% and 3.8% over the best baselines on three experimental settings. Code is released at https: / thu......... com CCmm//handd e erBang/ /GT
INTRODUCTION
Graph representation learning has been the center of various real-world upplications, such drug discovery (Duvenaud et al., 2015; Guo et al., 2022), recommender systems (Ying et al., 2018; Fan al., 2019; Sankar al., 2021), forecasting (Tang al., 2020; Derrow-Pinion et al., 2021) and outlier detection (Zhao et al., 202 Deng & Hooi, 2021). In recent years, there has been a surge of interest in developing graph neural networks (GNNs) as powerful tools for graph representation learning (Kipf & Welling, 2016a; Veličković et al., 2018; Hamilton et al., 2017; Wu et al., 2019). Remarkably, GNNs have achieved state-of-the-art performance on numerous graph-related tasks including node classification, graph classification and link prediction (Chien et al., 2021; You et al., 2021; Zhao et al., 2022b).
Despite the enormous success of GNNs, recent studies have revealed that their generalization and robustness are immensely challenged by the data quality (Jin et al., 2021b; Li al., 2022). In particular, GNNs can behave unreliably in scenarios where sub-optimal data is presented:
Distribution shift (Wu et al., 2022a; Zhu et al., 2021a), GNNs tend to yield inferior performance when the distributions of training and test data are not aligned (due to corruption or inconsistent collection procedure of test data).
2. Abnormal features (Liu et al., 2021a). GNNs suffer from high classification errors when data contains abnormal features, e.g., incorrect user profile information in social networks.
3. Adversarial structure attack (Zügner al., 2018; Li et al., 2021). GNNs vulnerable to imper- ceptible perturbations on the graph structure which can lead to severe performance degradation.
To tackle these problems, significant efforts have been made developing new techniques from the modeling perspective, e.g., designing new architectures and employing adversarial training strate- gies (Xu et al., 2019; Wu al., 2022a). However, employing these methods in practice may be
"Wok done while author was on internship Snap Inc.

---

Published as a conference paper at ICLR 2023
F1
Test Accuracy GCN: 44. 3%
Test Accuracy GCN: 67 4%
DA
Transform
GAT: 21
GAT: -8.558.8.% 8%
APPNP:
Node connectinn
APPNP: 70.7%
AirGNN: 58.5%
[lH Noda fealura
AIGGNN: 70. 70.8%
Original Graph
Refined Graph
Figure I: We study the test-time graph transformation problem, which seeks to learn a refined graph such that pre-trained GNNs can perform better on the new graph compared to the original. Shown: An illustration of our proposed approach's 's empirical performance transforming noisy graph.
infeasible, as they require additional cost of changing model architectures or re-training model pa- rameters, especially for well- large-scale models. The problem is further exacerbated when adopting these techniques for multiple architectures. By contrast, this paper seeks to investigate approaches that can be readily used with wide variety of pre-trained models and test settings for improving model generalization and robustness. Essentially, we provide a data-centric perspective to address the aforementioned issues by modifying the graph data presented test-time. Such mod- ification aims to bridge the gap between training data and test data, and thus enable GNNs to achieve better generalization and robust performance on the new graph. Figure I visually describes this idea: we are originally given with a test graph with abnormal features where multiple GNN architectures yield poor performance; however, by transforming the graph prior to inference (at test-time), we enable these GNNs to achieve much higher accuracy.
In this work, we aim to develop a data-centric framework that transforms the test graph to enhance model generalization and robustness, without altering the pre-trained model. In essence, we are faced with two challenges: (1) how to model and optimize the transformed graph data, and (2) how to formulate an objective that can guide the transformation process. First, we model the graph transformation as injecting perturbation on the node features and graph structure, and optimize them alternatively via gradient descent. Second, inspired by the recent progress of contrastive learning, we propose a parameter-free free surrogate loss which does not affect the pre-training process while effectively guiding the graph adaptation. Our contributions can be summarized as follows:
1. For the first time, we provide a data-centric perspective to improve the generalization and robust- ness of GNNs with test-time graph transformation.
2. We establish a novel framework GTRANS for test-time graph transformation by jointly learning the features and adjacency structure to minimize proposed surrogate loss.
3. Our theoretical analysis provides insights on what surrogate losses we should use during test-ting usst-time graph transformation and sheds light on the power of data- adapatttatnnnnnn over model- -ddettadapt
4. Extensive experimental results on three settings (distribution shift, abnormal features and ad- versarial structure attacks) have demonstrated the superiority of test-time graph transformation. Particularly, GTRANS performs the best in most cases with improvements up to 2.8%, 8.2% and 3.8% over the best baselines on three experimental settings.
Moreover, we note: (1) GTRANS is flexible and versatile. It can be equipped with any pre-trained GNNs and the outcome (the refined graph data) can be deployed with any model given its favorable transferability. (2) GTRANS provides a degree of interpretability, as it can show which kinds of graph modifications can help improve performance by visualizing the data.
2 RELATED WORK
Distribution shift in GNNs. GNNs have revolutionized graph representation learning and achieved state-of-the-art results on diverse graph-related tasks (Kipf & Welling, 2016a; Veličković et al., 2018; Hamilton et al., 2017; Chien et al., 2021; Klicpera et al., 2018; Wu et al., 2019). However, recent studies have demonstrated that GNNs yield sub-optimal performance on out-of-distribbtioo data for node classification (Zhu et al., 202 Wu et al., 2022a; Liu et al., 2022a) and graph classi- fication (Chen et al., 2022; Buffelli et al., 2022; Gui et al., 2022; Wu et al., 2022b; You et al., 2023). These studies have introduced solutions tackle distribution shifts by altering model training be- havior or model architectures. For a thorough review, we refer the readers to a recent survey (Li et al., 2022). Unlike existing works, target modifying the inputs via test-time adaption.
Robustness of GNNs. Recent studies have demonstrated the vulnerability of GNNs to graph ad- versarial attacks (Züggnrr et al., 2018; Zügner & Günneeann, 2019; Xu et al., 2019; Geisler et al.,
2

---

Published as a conference paper at ICLR 2023
2021), i.., small perturbations the input graph can mislead GNNs into making wrong predic- tions. Several works make efforts towards developing new GNNs or adversarial training strategies to defend against attacks (Xu et al., 2019; Zhu et al., 2019; Jin et al., 2021a:b). Instead of altering model training behavior, our work aims to modify the test graph to correct adversarial patterns.
Graph Structure Learning& & Graph Data Augmentation. Graph structure learning and graph data augmentation both aim to improve GNNs' generalization performance by augmenting the (training) graph data (Zhao et al., 2022a), either learning the graph from scratch (Franceschi al., 2019; Jin et al., 2020; Chen et al., 2020; Zhao et al., 2021b) or perturbing the graph in a rule-based way (Rong et al., 2020; Feng et al., 2020; Ding et al., 2022). While our work also modifies the graph data, we focus on modifying the test data and not impacting the model training process.
Test-time Training. Our work also related to test-time training (Sun et al., 2020; Wang et al., 2021; Liu et al., 2021b; Zhang et al., 2021; 2022), which has raised surge of interest in computer vision recently. To handle out-of-distribution data, Sun et al. (2020) propose the pioneer work of test-time training (TTT) by optimizing feature extractor via auxiliary task loss. However, TTT alters training to jointly optimize the supervised loss and auxiliary task loss. To remove the need for training auxiliary task, Tent (Wang et al., 2021) proposes to minimize the prediction entropy at test-time. Tent works by adapting the parameters in batch normalization layers, which may not always be employed by modern GNNs. In this work, we focus on a novel perspective of adapting the test graph data, which makes no assumptions about the particular training procedure or architecture.
METHODOLOGY
We start by introducing the general problem of test-time graph transformation (TTGT). While our discussion mainly focuses on the node classification task where the goal is to predict the labels of nodes in the graph, it can be easily extended to other tasks. Consider that we have training graph GT and a test graph GTe. and the corresponding set of node labels are denoted as Y', and Vre- respectively. Note that the node sets in GT, and GT: can either be disjoint or overlapping, and they are not necessarily drawn from the same distribution. Further, let fa(:) denote the mapping function of a GNN model parameterized by 0, which maps a graph into the space of node labels.
Definition 1 (Test-Tinee Graph Transformation (TTGT)). TTGT requires learn a graph transfor- mation function g(-) which refines the test graph GT. such that the pre- pre-trained fa can yield better test performance on g(GTe) than that on GT: arg min L (fe- (g(GTe)),
s.t. g(Gu)) E P(GT))
(1)
with 6" = arg min L (J))))
9
where L denotes the loss function measuring downstream performance; P(G is the space of the modified graph, e.g., we may constrain the change on the graph to be small.
To optimize the TTGT problem, we are faced with two critical challenges: (1) how to parameterize and optimize the graph transformation function g()); and (2) how to formulate a surrogate loss to guide the learning process, since we do not have access to the ground-truth labels of test nodes. Therefore, we propose GTRANS and claborate on how addresses these challenges as follows.
3.1 CONSTRUCTING GRAPH TRANSFORMATION
Let GRe- = {A, denote the test graph, where A E {0, 1 is the adjacency matrix, N is the number of nodes, and X E IR xd is the d-dimensional node feature matrix. Since the pre-trained GNN parameters are fixed at test time and we only care about the test graph, we drop the subscript in GTe and P'e to simplify notations in the rest of the paper.
Construction. We are interested in obtaining the transformed test graph G =((A,X) = (A'x')) Specifically, we model feature modification as an additive function which injects pertur- bation to node features, i.e., X' = X + x we model the structure modification as A' = A @ AA where 4 stands for an element wise exclusive OR operation and A E {0, 1) N is a binary ma- trix. In other words, (Aa). k; = indicates an edge flip. Formally, we seek to find A and Ax that
(A @ AA)i can be implemented as
(A AAAy if (A + AAJy 2 1, otherwise (A AAlij-
3

---

Published as a conference paper at ICLR 2023
can minimize the objective function:
arg min & (A + A X Ax),)) s.t. (A Ax) X)A,
(2)
AA.Ax
where AA E {0, 1j and Ax E RNxd are treated as free parameters. Further, to ensure we do not heavily violate the original graph structure, we constrain the number of changed entries in the adjacency matrix be smaller than budget B on the graph structure, i.e., Σ AA S B. We do not impose constraints on the node features to ease optimization. In this context, P can be viewed as constraining A A to a binary space as well as restricting the number of changes.
The optimization for Ax is easy since the node features are continuous. The opti- mization for A A is particularly difficult in that (1) A binary and constrained; and (2) the search space of N2 entries is too large especially when we are learning on large-scale graphs
Optimization.
To cope with the first challenge, we relax the binary space to [0, 1 and then can employ projected gradient descent (PGD) (Xu et al., 2019; Geisler et al., 2021) to update AA:
A + 1Ip (AA 17 [V A)) where we first perform gradient descent with step size 1) and call a projection Hp to project the variable to the space P. Specifically, given an input vector p. (-) is expressed as:
(3)
(P).
If 1 (o. S B;
(p) - (P - -11 with 1 LT - -11 = B, otherwise,
(4)
where 10 clamps the input values to [0, 1]. stands for vector of all ones, and is obtained >1) B with the bisection method (Liu et al., 2015). To
by solving the equation 1 io
keep the adjacency structure discrete and sparse, we view each entry in A @ AA as a Bernoulli distribution and sample the learned graph as A' ~'~ Bernoulli(A + A
Furthermore, to enable efficient graph structure learning, it is desired to reduce the search space of updated adjacency matrix. One recent approach of graph adversarial attack (Geisler et al., 2021) proposes to sample a small block of possible entries from the adjacency matrix and update them each iteration. This solution still computationally intensive as it requires hundreds of steps to achieve good performance. Instead, we constrain the search space to only the existing edges of the graph, which is typically sparse. Empirically, we observe that this simpler strategy still learns useful structure information when combined with feature modification.
3.2 PARAMETER-FRES SURROGATE LOSS
As diseussed earlier, the proposed framework GTRANS aims improve the model generalization and robustness by learning to transform the test graph. Ideally, when we have test ground-truth labels, the problem can be readily solved by adapting the graph to result in the minimum cross en- tropy loss on test samples. However, as we do not have such information at test-time, it motivates us investigate feasible surrogate losses to guide the graph transformation process. In the absence of labeled data, recently emerging self-supervised learning techniques (Xie et al., 2021: Liu et al., 2022b) have paved the way for providing self-supervision for TTGT. However, not every surrogate self-supervised task and loss is suitable for our transformation process, as some tasks are more pow- erful and some are weaker. To choose a suitable surrogate loss, we provide the following theorem.
Let Le denote the classification loss and L. denote the surrogate loss, respectively. Let P(G) denote the correlation between V (G.)) and (G), and let e denote the learning rate for gradient descent. Assume that C. is wwice-differentiable and its Hessian matrix satisfies HH,)))) I M for all G. When p(G) > and 2p(G)) ValG) C.l.))))
Theorem 1.
[[]Va., we have
Le (G cV GL (G) )) C. (G,)).
(5)
The proof can be found in Appendix A. Theorem suggests that when the gradients from classi- fication loss and surrogate loss have positive correlation, i.e., p (G) > O, we can update the test graph by performing gradient descent with a sufficiently small learning rate such that the classifica- tion loss on the test samples is reduced. Hence, is imperative to find a surrogate task that shares relevant information with the classification task. To empirically verify the effectiveness of Theorem 1, we adopt the surrogate loss in Equation (6) as L. and plot the values of p(G) and L. on one test graph in Cora in Figure? 2. We can observe that a positive P(G) generally reduces the test loss. Results on different losses can be found in Appendix D.9 and similar patterns are exhibited.
4

---

Published as a conference paper at ICLR 2023
Test c: Commistion p(o)
Parameter-Free Surrogate Loss. As one popular self supervise paradigm, graph contrastive learning has achieved promising perfor- mance in various tasks (Hassani & Khasahmadi, 2020; You et al., 2021; Zhu et al., 2021b), which indicates that graph contrastive learning tasks often highly correlated with downstream tasks. This property is de- sirable for guiding TTGT as suggested by Theorem 1. At its core lies the contrasting scheme, where the similarity between two augmented views from the same sample is maximized, while the similarity between views from two different samples is minimized. However, the majority of existing graph contrastive learning methods cannot be directly applied to our scenario, as they often require parameterized projection head to map augmented representations to another latent space, which inevitably alters the model architecture. Thus, we design a parameter-free surrogate loss which removes the projec- tion head. Specifically, we apply an augmentation function A(-) on input graph G and obtain an augmented graph A(G). The node representations obtained from the two graphs are denoted as Z and 2, respectively; z; and é, stand for the i-th node representation taken from them, respectively. We adopt DropEdge (Rong et al., 2020) as the augmentation function A(-), and the node repre- sentations are taken from the second last layer of the trained model. Essentially, we maximize the similarity between original nodes and their augmented view while penalizing the similarity between the nodes and their negative samples:
14
Epoch
Figure 2: Positive p(G) can
help reduce test loss.
N
N
min Lg - Σ
2
Zi
(1 Σ i=1
2 2i
(6)
12,
2
12, 12,1
1=1
where (ž.li 1, 1,.... N} are the negative samples for corresponding nodes, which are generated by shuffling node features (Velickovic et al., 2019). In Eq. (6), the first term encourages each node to be close while the second term pushes each node away from the corresponding negative sample. Note that (I) Ls is parameter-free and does not require modification of the model architecture, or affect the pre-training process; (2) there could be other self-supervised signals for guiding the graph transformation, and we empirically compare them with the contrastive loss in Appendix D.9. We also highlight that our unique contribution is not the loss in Eq. (6) but the proposed TTGT framework as well as the theoretical and empirical insights on how to choose a suitable surrogate loss. Furthermore, the algorithm of GTRANS provided in Appendix B.
3.3 FURTHER ANALYSIS
In this subsection, study the theoretical property of Eq. (6) and compare the strategy of adapting data versus that of adapting model. We first demonstrate the rationality of the proposed surrogate loss through the following theorem.
Theorem 2. Assume that the augmentation function A(-) generates a data view of the same class for the test nodes and the node classes are balanced. Assume for each class, the mean of the repre- sentations obtained from Z and Z are the same. Minimizing the first term in Eq. (6) is approximately minimizing the class-conditional entropy H(Z)Y) between features 7 and labels Y.
The proof can be found in Appendix A.2. Theorem 2 indicates that minimizing the first term in Eq. (6) will approximately minimize HZ which encourages high intra-class compactness, i.e., learning a low-entropy cluster in the embedded space for each class. Notably, // (Z can be rewritten as HZ)YY- = (Z) (2, Y). It indicates that minimizing Eq. (6) can also help promote [[Z, Y). the mutual information between the hidden representation and downstream class. However, we note that only optimizing this term can result in collapse (mapping all data points to a single point in the embedded space), which stresses the necessity of the second term in Eq. (6).
Next, we use an illustrative example to show that adapting data at test-time can be more useful than adapting model in some cases. Given test samples (xli = 1...., K). we consider linearized GNN fe which first performs aggregation through function Agg(.,)) and then transforms the aggregated features via a function Trans(-). Hence, only the function Trans(-) parameterized by 0.
Example. Let Nú denote the neighbors for node x,. If there exist two nodes with the same aggre- gated features but different labels, i.e., Agg(x1, {xşli A11) = Agg(xe, {xyli N2)). y1 # y2, adapting the data fx.li = 1,..., K} can achieve lower classification error than adapting the model fo at test stage.
illustration. Letx, Agg(xi, (x:li E Ni)) and x2 Agg(x2, (xyli E NN2). For simplicity, we
5

---

Published as a conference paper at ICLR 2023
consider the following mean square loss the classification error:
l t= (Trans(x))) - y1)² + (Tan)((x2= - -2))))
It is easy to see that l reaches its minimum when Trans( ) - y1 and Trans y2- In this context, it is impossible to find 0 such that Trans(-) can map xI, X2 to different labels since it is not a one-to-many function. However, since y1 and y/2 are in the label space of training data, we can always modify the test graph to obtain newly aggregated features x X22 such that Trans(x1) = yn and Trans(X;) = y/. which minimizes f. In the extreme case, we may drop all node connections for the two nodes, and let X1 <- X and X2 < X/2 where X and x/2 are the aggregated features taken from the training set. Hence, adapting data can achieve lower classification loss.
Remark 1. Note that the existence of two nodes with the same aggregated features but different labels is not rare when considering adversarial attack or abnormal features. We provide figurative example in Figure 6 in Appendix A.3: the attacker injects one adversarial edge into the graph and changes the aggregated features X1 and X2 to be the same.
Remark 2. When we consider X # X2, 1/1 # y2, whether we can find 0 satisfying Trans(x]) = yi and Txa) 3/2 depends on the expressiveness of the the transformation function. If it is not powerful enough (e.g., an aander-prameterizee neural network), it could fail to map different data points to different labels. On the contrary, adapting the data does not suffer this problem as we can always modify the test graph to satisfy Trans (x) = yı and Tr,ns(X;) = y2-
Remark 3. The above discussion can be easily extended to nonlinear GNN by considering &1, 82 as the output before the last linear layer of GNN.
4 EXPERIMENT
4.1 GENERALIZATION ON OUT-OF-DISTRIBUTTO DATA
Setup. Following the settings in EERM (Wu et al., 2022a), which is designed for node-level tasks on OOD data, we validate GTRANS on three types of distribution shifts with six benchmark datasets:
(1) artificial transformation for Cora (Yang et al., 2016) and Amazon-Photd (Shchur et al., 2018), (2) cross-domain transfers for Twitch-E and FB-100 (Rozemberezki et al., 2021a) (Lim et al., 2021), and (3) temporal evolution for Elliptic (Pareja et al., 2020) and OGB-Arxiv (Hu et al., 2020). Moreoever, Cora and Amazon Photo have 1/1/8 graphs for trainingfallidationnees sets. The splits are 1/1/5 on Twitch-E, 3/2/3 on FB-100, 5/5/33 on Elliptic, and 1/1/3 on OGB-Arxiv. More details on the datasets are provided in Appendix C. We compare GTRANS with four baselines: empirical risk minimization (ERM, standard training), data augmentation technique DropEdge (Rong et al., 2020), test-time- training method Tent (Wang et al., 2021). and the recent SOTA method EERM (Wu et al., 2022a) which is exclusively developed for graph OOD issue. Further, we evaluate all the methods with four popular GNN backbones including GCN (Kipf & Welling, 20), GraphS (Hamilton et al., 2017), GAT (Veličković et al., 2018), and GPR (Chien et al., 2021). Their default setup follows that in EERM We refer the readers to Appendix C.I for more implementation details of baselines and GTRANS. Notably, all experiments in this paper are repeated 10 times with different random seeds. Due to page limit, include more baselines such SR-GNN (Zhu et al., 2021a) and UDA-GCN (Wu et al., 2020) in Appendix D.I.
Results. Table reports the averaged performance over the test graphs for each dataset as well as the averaged rank of each algorithm. From the table, we make the following observations:
(a) Overall Performance. The proposed framework consistently achieves strong performance across the datasets: GTRANS achieves average ranks of 1.0, 1.7, 2.0 and 1.7 with GCN, SAGE, GAT and GPR, respectively, while the corresponding ranks for the best baseline EERM are 2.9, 3.4, 3.0 and 2.0. Furthermore, in most of the cases, GTRANS significantly improves the vanilla baseline (ERM) by a large margin. Particularly, when using GCN as backbone, GTRANS outperforms ERM by 3.1%. 5.0% and 2.0% Cora, Elliptic and OGB-Arxiv, respectively. These results demonstrate the effectiveness of GTRANS in tackling diverse types of distribution shifts.
(b) Comparison to other baselines. Both DropEdge and EERM modify the training process to im- prove model generalization. Nonetheless, they are less effective than GTRANS, GTRANS takes
2 We note that the GCN used in the experiments of EERM does not normalize the adjacency matrix according its open-source code. Here we normalize the adjacency matrix make it consistent with the original GCN.

---

Published as a conference paper at ICLR 2023
Table 1: Average classification performance (%) on the test graphs. Rank indicates the average rank of each algorithm for each backbone. OOM indicates out-of-memory error on 32 GB GPU memory.
The proposed GTRANS consistently ranks the best compared with the baselines. */"* indicates that
GTrans outperforms ERM at the confidence level 1/0.05 from paired t-test.
Backbone
Method
Amz-Photo
Cora
Elliptic
FB-100
OGB-Arxiv
Twitch-E
Rank
GCN
ERM
93.79:0.97
91.59+1 44
50,90 1,51
54.04=0.94
38.59
59.89+0.50
3.8
DropEdge
92.11a0.31
81.0141.33
53.9614.91
53.0010.50
41.2611092
59.9510.39
Tent
94.03+1.07
91.87 1.36
51.71+2.00
54.16+1.00 .00
39.33+1.40
59 49.4560.55
EERM
94.0540.40
87.2140.53
53.9620.65
54.2420.55
0OM
59.85+0.88
2.9
GTRANS
94.13=0.77
94.66++0.63
55.88+3.10"
54.32+0.60
41.59=1.20"
60.42200.86
SAGE
ERM
35.09+0.60
99.6740.14
56.12+4.47
54,70=0.47
39.56+1
22.06+00.0
DropEdge
92.61=0.56
95 85+0.30
52.38+3.1 11
#0.69
38. 19+1.74
62.14+0.11 14
4.2
Tent
95.7240.43
19.80+00.10
85.8944.87
54.N6+0.34
39.58+1.22 26
22.09+0.09
2.3
EERM
13.57=0.13
98.77+0.14
58,20+3.55
54.28+0.97
0OM
62.11
GTRANS
96.91200.68"
99.45+0.13
60.81+5.19"
54.64=0.62
40.39=1.44"
62.15
1.7
GAT
ERM
96.30.0.79
94.8121.28
65, 65.3612.70
$1.77&1.41
40.6311.57
58.5311.00
3.0
Ddge
90.70+00229
76.91+1.55
63.78+2.39
52.65+0.88
42.48+0.33
58.84+101
Tent
95.99 15.9910.46
95.9111.14
66.0741.66
51.47&1.70
40.0611.19
58.3311.18
3.3
EERM
95.57=1.32
85 00
58, 18+411
53,30=0,77
OOM
59 84,001
3.0
GTRANS
96.6720.74
96.3771100
66.43+2.57
51.1611.72
43.7621.25"'
58 58.5911007
2.0
GPR
ERM
91.87+0.65
93.00+2.17
64.59+3.52
54.51=0.33
44.38=0.59
59.72+0.40
Drge
88.81+1.48
79.27+ 1,39
61.0221.78 1.78
55.04+0.33
43 43.65+0.77
89,895
3.3
Tent' 90.78+0.52
FERM
1008243.10 93.05+2.02
67.27+0.98 69.03+2.333
55,95+0.03 OOM 54.38+0.31
61.57:0012
GTRANS
91.93++0.73
46.10=00.46"
60.11+00,33*
1.7
Tent cannot be applied to models which do not contain batch normalization layers.
Extra Running Time (s)
Total GPU Mcmory (GB)
Accuracy
0.90
Cora Photo Ellip. Arxiv Cora Photo
Ellip.
Arxiv
EERM 25.9
396.4
607.9
2.5
10.5
12,8
>32
GTrams
GTRANS 0.3
0.5
0.6
2.6
1.4
1.5
1.3
3.9
T8 Results on Cora under OOD. Table 2: Efficiency comparison. GTRANS is more GTRANS improves GCN most test graphs. time- and memory-efficient than EERM.
T1
T2
T3
T4
T5
T6
T7
Figure
advantage of the information from test graphs. As test-time training method, Tent also performs well in some cases, but Tent only adapts the parameters in batch normalization layers and cannot be applied to models without batch normalization.
We further show the performance on each test graph on Cora with GCN in Figure 3 and the results for other datasets are provided in Appendix D.4. We observe that GTRANS generally improves over individual test graphs within each dataset, which validates the effectiveness of GTRANS.
Efficiency Comparison. Since EERM performs the best among baselines, Table 2 showcases the efficiency comparison between our proposed GTRANS and EERM on the largest test graph in each dataset. The additional running time of GTTRAN ANS majorly depends on the number of gradient descent steps. As we only use a small number (5 or 10) throughout all the experiments, the time overhead brought by GTRANS is negligible. Compared with the re-training method EERM, GTRANS avoids the complex bilevel optimization and thus is significantly more efficient. Furthermore, EERM im- poses a considerably heavier memory burden.
4.2 ROBUSTNESS TO ABNORMAL FEATURES
Setup. Following the setup in AirGNN (Liu al., 2021a), we evaluate the robustness in the case of abnormal features. Specifically, we simulate abnormal features by assigning random features taken from a multivariate standard Gaussian distribution to a portion of randomly selected test nodes. Note that the abnormal features are injected after model training (at test time) and we vary the ra- tio noisy nodes from 0.1 to 0.4 with a step size of 0.05. This process is performed for four datasets: the original version of Cora, Citeseer, Pubmed, and OGB-Arxiv. In these four datasets, the training graph and the test graph have the same graph structure but the node features are dif- ferent. Hence, to optimize GTRANS. We use GCN as the backbone model and adopt four GNNs as the basclines including GAT (Veličković et al., 2018), APPNP (Klicpera et al., 2018), AirGNN and AirGNN-t.
the training classification loss combined with the proposed contrastive loss
7

---

Published as a conference paper at ICLR 2023
05
E7
94
50h
0C4
SCM
C11
011
of hodes
00
030
5:0
Noly Nodes
0.5
80
211
Rudo Nosy
axd
0.33
023
Noby
423
2:00
(a) Cora
(b) Citeseer
(c) Pubmed
(d) OGB-Arxiv
Figure 4: Node classification accuracy on abnormal (noisy) nodes.
Andy Ote..
Coch Pubm AnN
DMe
Cor PUSYT
Tee Modes
Aeconnal Maden
(a) Abnormal Graph (b) Refined Graph
(c) OOD Setting
(d) Abnormal Features
Figure 5: (a)(b) T-SNE visualizations of embedding ohtained from abnormal graph and transformed
graph Cora. (c) Comparison between adapting data and adapting model test time.
Note that AirGNN-t tunes the cesssagepasssing hyper-parameter in AirGNN at test time. For fair comparison, we tune AirGNN-t based on the performance on both training and validation nodes.
Results. For each model, present the node classification accuracy on both abnormal nodes and all test nodes (i.e., both normal and abnormal ones) in Figure 4 and Figure 8 (See Appendix D.5), respectively. From these figures, we have two observations. First, GTRANS significantly improves GCN in terms of the performance on abnormal nodes and all test nodes for all datasets across all noise ratios. For example, on Cora with 30% noisy nodes, GTRANS improves GCN by 48.2% on abnormal nodes and 31.0% on overall test accuracy. This demonstrates the effectiveness of the graph transformation process in GTRANS in alleviating the effect of abnormal features. Second, GTRANS shows comparable or better performance with AirGNNs, which are the SOTA defense methods for tackling abnormal features. It is worth mentioning that AirGNN-t improves AirGNN by tuning its Syper-parameter at test time, which aligns with our motivation that test-time adaptation can enhance model test performance. To further understand the effect of graph transformation, we provide the visualization of the test node embeddings obtained from abnormal graph (0.3 noise ratio) and transformed graph for Cora in Figures 5a and 5b, respectively. We observe that the transformed graph results in well-clustered node representations, which indicates that GTRANS can promote intra-class compactness and counteract the effect of abnormal patterns.
4.3 ROBUSTNESS TO ADVERSARIAL ATTACK
Setup. We further evaluate GTRANS under the setting of adversarial attack where perturb the test graph, i... evasion attack. Specifically, we use PR-BCD (Geisler et al., 2021), a scalable at- tack method, to attack the test graph in OGB-Arxiv. We focus on structural attacks, and vary the perturbation rate, i.e., the ratio of changed edges, from 5% to 25% with a step of 5%. Similar to Section 4.2, we adopt the training classification loss together with the proposed contrastive loss to optimize GTRANS. We use GCN as the backbone and employ four robust baselines implemented by the adversarial attack repository DeepRobust (Li et al., 2020) including GAT (Veličković al., 2018), RobustGCN (Zhu et al., 2019), SimPGCN (Jin et al., 2021a) and GCNJaccard (Xu et al., 2019) as comparisons. Among them, GCNJaccard pre-processes the attacked graph by removing edges where the similarities of connected nodes are less than a threshold; we tune this threshold at test time based on the performance on both training and validation nodes.
repositor
Results. Table 3 reports the performances under structural evasion attack. We observe that GTRANS consistently improves the performance of GCN under different perturbation rates of adversarial at- tack. Particularly, GTRANS improves GCN by a larger margin when the perturbation rate is higher. For example, GTRANS outperforms GCN by over 40% under the 25% perturbation rate. Such ob- servation suggests that GTRANS can counteract the devastating effect of adversarial attacks. In ad- dition, the best performing baseline GCNJaccard also modifies the graph at test time, which demon- strates the importance of test-time graph adaptation. Nonetheless, it consistently underperforms
8

---

Published as a conference paper at ICLR 2023
Table 3: Node classification accuracy (%) under different perturbation (Ptb.) rates of structure attack.
Ptb. Rate
GCN
GAT
RobustGCN
SimPGCN
GCNaccard
GTRANS
5%
57.47=0.54
64.56+0.49
61.55=1.20
61.30:0.42
65.01=0.26
66.2920.25
10%
47.97=0.65
61.2040.70
58. 18.55
57.01=0.70
63,25=0.30
65.16=0.52
15%
38.04=1.22
58.96+0.59
55.91=1.27
54.13+0.73
61.83=0.29
64.40::0388
20%
29.05=0.73
57.29+0.44
54.39=1.09
52.26+0087
60.57=0.34
63.44:0.50
25%
19.58+2.32
55.86+0.53
52.76=1.44
50.46+0.85
59.17=0.39
62.95=0.67
proposed GTRANS, indicating that a learnable transformation function is needed to achieve better robustness under adversarial attacks, which GCNJaccard does not employ.
Interpretation. To understand the modifications made on the graph, we compare several proper- ties among clean graph, attacked graph (20% perturbation rate), graph obtained by GCNJaccard, and graph obtained by GTRANS in Table 13 in Appendix D.6, First, adversarial attack decreases ho- mophily and feature similarity, but GTRANS and GCNJaccard promote such information to alleivate the adversaria patterns. Our experiment also shows that GTRANS removes 77% adversarial edges while removing 30% existing edges from the attacked graph. Second, both GTRANS and GCNJac- card focus on deleting edges from the attacked graph, but GCNJaccard removes substantially larger amount of edges, which may destroy clean graph structure and lead to sub-optimal performance.
4.4 FURTHER ANALYSIS
Cross-Architecture Transferability. Since the outcome of GTRANS is a refined graph, it can conceptually be employed by any GNN model. Thus, we can transform the graph based
Table 4: Transferability.
Tri
GCN APPNP AirGNN GAT
on one pre-trained GNN and test the transformed graph on another pre-trained GNN. To examine such transferability, we perform experiments GCN, APPNP, AirGNN and GAT under the abnormal feature setting with 30% noisy nodes on Cora. The results on all test nodes in Table 4. Note that
GCN
67.36
70.65
70.84
58.62
APPNP
67.87
70.39
69.59
64.46
AirGNN 68.00
70.37
72.68
64.93
GAT
54.85
60.37
65.22
$4.60
Noisy 44.29
48.26
58.51
21.23
"Tr" stands for GNNs used in TTGT while "Te" denotes GNNs used for obtaining predictions on the transformed graph; "Noisy" indicates the performance the transformed graph yields good performance even outside the scope it was optimized for. We anticipate that such transferability can alleviate the need for costly re-training new GNNs.
the noisy graph. We observe that
Adapting Model vs. Adapting Data. We empirically compare the performance between adapting data and adapting model and consider the OOD and abnormal feature settings. Specifically, use GCN as the backbone and adapt the model parameters by optimizing the same loss function as used in GTRANS. The results are shown in Figures 5c and 5d. In OOD setting, both adapting model and adapting data can generally improve GCN's performance. Since their performances are still close, is hard to give a definite answer on which strategy is better. However, we can observe significant performance differences when the graph contains abnormal features: adapting data outperforms adapting model on 3 out of 4 datasets. This suggests that adapting data can be more powerful when the data is perturbed, which aligns with our analysis in Section 3.3.
Learning Features v.s. Learning Structure. Since our framework learns both node features and graph structure, we investigate when one component plays a more important role than the other. Our results are shown in Tables 16 and 17 in Appendix D.8. From the tables, we observe that (1) while each component can improve the vanilla performance, feature learning is more crucial for counteracting feature corruption and structure learning more important for defending structure corruption; and (2) combining them generally yields better or comparable performance.
5 CONCLUSION
GNNs tend to yield unsatisfying performance when the presented data is sub-optimal. To tackle this issue, we seek to enhance GNNs from a data-centric perspective by transforming the graph data at test time. We propose GTRANS which optimizes contrastive surrogate loss to transform graph structure and node features, and provide theoretical analysis with deeper discussion to under- stand this framework. Experimental results on distribution shift, abnormal features and adversarial attack have demonstrated the effectiveness of our method, In the future, we plan to explore more applications of our framework such as mitigating degree bias and long-range dependency.

---

Published as a conference paper at ICLR 2023
ACKNOLWEDGEMENT
This research is supported by the National Science Foundation (NSF) under grant numbers IIS IIS1845081, I1S1928278, IIS1955285, IIS2212032, I1S2212144, IOS2107215, and IOS2035472, the Army Research Office (ARO) under grant number W91 1N---11----198, MSU Foundation, the Home Depot, Cisco Systems Inc, Amazon Faculty Award, Johnson & Johnson and Snap Inc.
ETHICS STATEMENT
To the best of our knowledge, there are no ethical issues with this paper.
REPRODUCIBILITY STATEMENT
To ensure reproducibility of our experiments, we provide our source code at https: Com/Chandles erBang GTrans.. The hyper-parameters described in details in the appendix. We also provide a pseudo-code implementation of our framework in the appendix.
REFERENCES
Malik Boudiaf, Jérôme Rony, Imtiaz Masud Ziko, Eric Granger, Marco Pedersoli, Pablo Piantanida, and Ismail Ben Ayed. A unifying mutual information view metric learning: cross-entropy vs. pairwise losses. In European conference computer vision, pp. 548-564. Springer, 2020.
Davide Buffelli, Pietro Liò, and Fabio Vandin. Sizeshiftreg: a regularization method for improv- ing size-gnneralization in graph neural networks. Advances in Neural Information Processing Systems, 2022.
Yongqiang Chen, Yonggang Zhang, Han Yang, Kaili Ma, Binghui Xie, Tongliang Liu, Bo Han, and James Cheng. Invariance principle meets -fitt--distri generalization on graphs. arXiv preprint arXiv:2202.05444 2022.
Yu Chen, Lingfei Wu, and Mohammed Zaki. Iterative deep graph learning for graph neural net- works: Better and robust node embeddings. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systemx, volume 33, pp. 19314-19326, 2020.
Eli Chien, Jianhao Peng. Pan Li, and Olgica Milenkovic. Adaptive universal generalized pager- ank graph neural network. In ICLR, 2021. URL httph:ttp//ccc https::/opeereviieeee net wttp:eew.eew.teeeee//eeeeee forum? id= 16
Ailin Deng and Bryan Hooi. Graph neural network-based anomaly detection in multivariate time series. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 4027- 4035, 2021.
Austin Derrow-Pinion Jennifer She, David Wong, Oliver Lange, Todd Hester, Luis Perez, Mare Nunkesser, Seongjae Lee, Xueying Guo, Bret Wiltshire, al. Eta prediction with graph neural networks in google maps. In Proceedings of the 30th ACM International Conference on Informa- tion & Knowledge Management, pp. 3767-3776, 2021.
Kaize Ding, Zhe Xu, Hanghang Tong, and Huan Liu. Data augmentation for deep graph learning: A survey, arXiv preprint arXiv:2202.0823: 082355 2022.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks graphs for learning molecular fingerprints. Advances in neural information processing systems, 28, 2015.
Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalexakis. All you need is low (rank) defending against adversarial attacks on graphs. In Proceedings of the 13th International Conference Web Search and Data Mining, pp. 169-177, 2020.
10

---

Published as a conference paper at ICLR 2023
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The world wide web conference, pp. 417-426, 2019.
Bahare Fatemi, Layla El Asri, and Seyed Mehran Kazemi. Slaps: Self-supervision improves struc- ture learning for graph neural networks. Advances in Neural Information Processing Systems, 34: 22667-2266 2021.
Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural networks for semi-supervised learning on graphs. Advances in neural information processing systems, 53:22092-221033. 2020.
Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. arXiv preprint arXiv:1903. 17960, 2019.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversarial training of neural net- works. The journal of machine learning research, (711):096-2033) 2016.
Simon Geisler, Tobias Schmidt, Hakan Şirin, Daniel Zügner, Aleksandar Bojchevski, and Stephan Günnemann. Robustness of graph neural networks at scale. Advances in Neural Information Processing Systems, 34:7637-7649, 2021.
Shurui Gui, Xiner Li. Limei Wang. and Shuiwang Ji. Good: A graph -ittt--ddittibttiion benchmark. arXiv preprint 2rxiv:2206.08452, 2022.
Zhichun Guo, Bozhao Nan, Yijun Tian, Olaf Wiest, Chuxu Zhang, and Nitesh V Chawla. Graph- based molecular representation learning. arXiv preprint arXiv:2207 (iXi:22207.04869, 2022.
Jonathan Halerow, Alexandru Mosoi, Sam Ruth, and Bryan Perozzi. Grale: Designing networks for graph learning. In Proceedings of the 26th ACM SIGKDD International Conference on Knowl- edge Discovery & Data Mining, pp. 2523-2532. 2020.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Kavch Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In International Conference Machine Learning, pp. 4116-4126, PMLR, 2020.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118-22133 2020.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. arXiv preprint arXiv:2005.10203: 2020.
Wei Jin, Tyler Derr, Yiqi Wang, Yao Ma, Zitao Liu, and Jiliang Tang. Node similarity preserving graph convolutional networks. In Proceedings of the 14th ACM international conference on web search and data mining, pp. 148-156, 2021a.
Wei Jin, Yaxing Li, Han Xu, Yiqi Wang, Shuiwang Ji, Charu Aggarwal, and Jiliang Tang. Ad- versarial attacks and defenses on graphs. ACM SIGKDD Explorations Newsletter, 22(2):19-34 2021b.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: www.ei.09000000 2016a.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308, 2016b.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate:
Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997, 2018.
Haoyang Li, Xin Wang. Ziwei Zhang, and Wenwu Zhu. Out-of-distribution generalization on graphs: A survey. arXiv preprint a7Xiv:2002.07987, 2022.

---

Published as a conference paper at ICLR 2023
Jintang Li, Tao Xie, Chen Liang, Fenfang Xie, Xiangnan He, and Zibin Zheng. Adversarial attack on large scale graph. IEEE Transactions on Knowledge and Data Engineering, 2021.
Yaxin Li, Wei Jin, Han Xu, and Jiliang Tang. Deeprobust: A pytorch library for adversarial attacks and defenses. arXiv preprint arXiv:2005.06149 2020.
Derek Lim, Xiuyu Li, Felix Hohne, and Ser-Nam Lim. New benchmarks for learning non- homophilous graphs. arXiv preprint arXiv:2104.014000 2021.
Hongrui Liu, Binbin Hu, Xiao Wang, Chuan Shi, Zhiqiang Zhang, and Jun Zhou. Confidence may cheat: Self-training on graph neural networks under distribution shift. In Proceedings of the ACM Web Conference 2022, pp. 1248-1258 2022a.
Sijia Liu, Swarnendu Kar, Makan Fardad, and Pramod Varshney. Sparsity-awar sensor collabora- tion for linear coherent estimation. IEEE Transactions on Signal Processing, 63(10):2582-2566 2015.
Xiaorui Liu, Jiayuan Ding, Wei Jin, Han Xu, Yao Ma, Zitao Liu, and Jiliang Tang. Graph ral networks with adaptive residual. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021a. URL https: / //openreview fert/forumm corommmiii wiidddh-kEER KJiNw.
Yixin Liu, Ming Jin, Shirui Pan, Chuan Zhou, Yu Zheng, Feng Xia, and Philip Yu. Graph self- supervised learning: A survey. IEEE Transactions on Knowledge and Data Engineering, 2022b.
Yuejiang Liu, Parth Kothari, Bastien van Delft, Baptiste Bellot-Gurlet, Taylor Mordan, and Alexan- dre Alahi. Ttt++: When does self-supervised test-time training fail or thrive? Advances in Neural Information Processing Systems, 34:2 1001-28882200 2021b.
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma. Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao Schardl, and Charles Leiserson. Evolvegen: Evolving graph convolutional net- works for dynamic graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5363-5370 2020.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Repre- sentations, 2020. URL https: pesttp:://pperevie// hwtp//wwwpweeeeeeeeeeeeeeeeeeeee net wttp://wwwwnn//uumnneeeeeeeeeeee wttprrmmmidiikkkkkkkkkkk.k
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9())cnabb11, 2021aa
Benedek Rozemberczki, Peter Englert, Amol Kapoor, Martin Blais, and Bryan Perozzi. Pathfinder discovery networks for neural message passing. In Proceedings of the Web Conference 2021, pp. 2547-2558, 2021b.
Aravind Sankar, Yozen Liu, Jun Yu, and Neil Shah. Graph neural networks for friend ranking in large-scale social platforms. In Proceedings of the Web Conference 2021, pp. 2535-2546, 2021.
Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint
2018
Xiao Shen, Quanyu Dai, Fu-lai Chung, Wei Lu, and Kup-Sze Choi. Adversarial deep network embedding for cross-network node classification. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 2991-29999 2020.
Yu Sun, Xiaolong Wang, Zhuang Liu, John Miller, Alexei Efros, and Moritz Hardt. Test-time train- ing with self-supervision for generalization under distribution shifts. In International conference on machine learning. pp. 9229-9248. PMLR, 2020.
Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation im- prove graph contrastive learning, Advances in Neural Information Processing Systems, 34:15920- 15933, 2021.
12

---

Published as a conference paper at ICLR 2023
Xianfeng Tang, Yozen Liu, Neil Shah, Xiaolin Shi, Prasenjit Mitra, and Suhang Wang. Knowing your fate: Friendship, action and temporal explanations for user engagement prediction on social apps. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2269-2279 2020.
Amanda L Traud, Peter J Mucha, and Mason A Porter. Social structure of facebook networks.
Physica A: Statistical Mechanics and its Applications, 391(16)441554433) 2012.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. 2018.
Petar Velickovic, William Fedus, William L Hamilton, Pietro Liō, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. ICLR (Poster), 2(3):4, 2019.
Dequan Wang. Evan Shelhamer, Shaoteng Liu, Bruno Olshausen, and Trevor Darrell. Tent: Fully test-time adaptation by entropy minimization. In International Conference Learning Repre- sentations, 2021. URL :
Man Wu, Shirui Pan, Chuan Zhou, Xiaojun Chang, and Xingquan Zhu. Unsupervised domain adaptive graph convolutional networks. In Proceedings of The Web Conference 2020, pp. 1457- 1467, 2020.
Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. Handling distribution shifts graphs: An invariance perspective. In International Conference on Leurning Representations, 2022a. URL https: wwwprevieeeeeeeeeeeeeeeeeeeeeeee net/ /ttp://mmdddooo0o-----1 legI.
Yingxin Wu, Xiang Wang, An Zhang, Xiangnan He, and Tat-Seng Chua. Discovering invariant rationales for graph neural networks. In International Conference on Learning Representations, 2022b. URL https:ttp// /ppnneveeeeeeeeeeeeeeeeeeeeeeeee wet.iieww.eeeeeeeeeeeeeeeeeeeeee forum? di=iixiddiiiiiii j f
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. A comprehensive survey on graph neural networks. arXiv preprint 100.::::9001009900 2019.
Yaochen Xie, Zhao Xu, Jingtun Zhang, Zhengyang Wang, and Shuiwang Ji. Self- learning of graph neural networks: A unified review. arXiv preprint arXiv:2102.10757, 2021.
Kaidi Xu, Hongge Chen, Sijia Liu, Pin-Yo Yu Chen, Tsui-Wa Weng, Mingyi Hong, and Xue Lin. Topology attack and defense for graph neural networks: An optimization perspective. arXiv preprint 1906. 14, 2019.
Jingkang Yang, Kaiyang Zhou, Yixuan Li, and Ziwei Liu. Generalized out-of-distribution detection: A survey. arXiv preprint arXiv:2110.11334, 2021a.
Shuo Yang, Lu Liu, and Min Xu. Free lunch for few-shot learning: Distribution calibration. In International Conference on Learning Representations (ICLR), 2021b.
Shuo Yang. Songhua Wu, Tongliang Liu, and Min Xu. Bridging the gap between few-shot and many- shot learning via distribution calibration. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44( (4(12):9830-98) 9843, 2021c.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp. 40-48. PMLR, 2016.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 974 983, 2018.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in Neural Information Processing Systems, 33:5812-5823 2020.
Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning auto- mated. Proceedings of International Conference Machine Learning, 2021.
13

---

Published as a conference paper at ICLR 2023
Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. Graph domain adaptation via theory-gre grouuded spectral regularization. International Conference on Learning Representa- tions, 2023.
Werner Zellinger, Thomas Grubinger, Edwin Lughofer, Thomas Natschläger, and Susanne Saminger-Platz Central moment discrepancy (cmd) for domain-invariant representation learn- ing. arXiv preprint 1rXiv:1702.08811.22 2017.
Marvin Zhang, Sergey Levine, and Chelsea Finn. Memo: Test time robustness via adaptation and augmentation. arXiv preprint arXiv:2110.09506 2021.
Yifan Zhang, Bryan Hooi, Lanqing Hong, and Jiashi Feng. Self-supervised aggregation of diverse experts for test-agnostic long-tailed recognition. In Advances in Neural Information Processing Systems, 2022.
Tong Zhao, Tianwen Jiang, Neil Shah, and Meng Jiang. A synergistic approach for graph anomaly detection with pattern mining and feature learning. IEEE Transactions on Neural Networks and Learning Systems, 2021a.
Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data aug- mentation for graph neural networks. In AAAI, 2021b.
Tong Zhao, Wei Jin, Yozen Liu, Yingheng Wang, Gang Liu, Stephan Günneman, Neil Shah, and Meng Jiang. Graph data augmentation for graph machine learning: A survey. arXiv preprint arXiv:2202.08887/ 2022a.
Tong Zhao, Gang Liu, Daheng Wang, Wenhao Yu, and Meng Jiang. Learning from counterfactual links for link prediction. In International Conference on Machine Learning, pp. 26911-26922 PMLR, 2022b.
Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu. Robust graph convolutional networks against adversarial attacks. In Proceedings of the 25th ACM SIGKDD international conference 2019.
on knowledge discovery & data mining, pp.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33:7793-7804 2020.
Qi Zhu, Natalia Ponomareva, Jiawei Han, and Bryan Perozzi. Shift-robust gnns: Overcoming the limitations localized graph training data. Advances in Neural Information Processing Systems, 34, 2021a.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In Proceedings of the Web Conference 2021, pp. 2069-2080, 2021b.
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2847-2856, 2018.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In International Conference on Learning Representations, 2019. URL https:/ //
openreview n forrm//rrr////// ? id BddBBy1x2099Xx
14

---

Published as a conference paper at ICLR 2023
A PROOFS
A.1 THEREOM
Theorem 1. Let Le denote the classification loss and L. denote the surrogate loss, respectively, Let G) denote the correlation between VaLolG)) and (G), and let e denote the learning and its Hessian matrix satisfies [H()))) S M for all G. When p(G) and 2o(G]] V VaCe(G.)'l
rate for gradient descent. Assume that Le is wwice-differentin
we have
(G -
C. (G,)).
Proof. Given that L. is differentiable and twice-differreniabll we perform first-order Taylor expan- sion with Lagrange form of remainder at G - (G).
L. (G VaLL (G)
(9)
L. (G.3) - sp (C) Vo (G. (V (c)ll2 _ VG) ( - (VC.
where 9 E (0, 1) is a constant given by Lagrange form of the Taylor's remainder (here we slightly abuse the notation), and p (G) is the correlation between VaLe(G,)) and (G),(G):
VoL. (G.J) (G)
p (G) I[V (G, VV (G)
(10)
Before we proceed to the steps, we first show that given vector p and symmetric matrix A, holds:
the inequality Ap <
p Ap
Σ o. uuu.p P
(Performing SVD on A. A.e. A = Eo,,,
Σ o. V.
(Let U p. where U [ui U2j...; un!)
Σ mma v V; mmax v112 = 0 Jmax
pl2
max |pl (U an orthogonal matrix)
|p A
(11)
Since the Hessian matrix is symmetric, we can use the above inequality to derive:
L. (VoL....
(12)
L.. (c. (I (G, -4tp::/00...aa.///////....o11111 -
Then we rewrite Eq. (12) as:
L. (G - cV (G), , - (G,3)
VoL. < Vo. (C) - -
(13)
Given |H(G)))]| M, know
L. (G cV.L, (G) -
2M
(14)
$ - (G) (G, VoC., (G)l22 + 2 Vo
C. we have M V
By setting
Le (G VCL, (G), L. (G,J) = 0. I. and ((G) > have
(15)
Therefore, when
M (G)
L. (G cV (G) )) C. (G,)).
(16)
A.2 THEREOM
Theorem 2. Assume that the augmentation function A(-) generates a data view of the same class for the test nodes and the node classes are balanced. Assume for each class, the mean of the repre-
15

---

Published as a conference paper at ICLR 2023
sentations obtained from Z and Z are the same. Minimizing the first term in Eq. (6) is approximately minimizing the caas-connitional entropy (ZY) between features Z and labels Y.
Proof. For convenience, slightly abuse the notations replace 2, and R with 2; and 2; ||x,]|
respectively. Then we have ||z||| = || = 1. Let 2μ denote the set of test samples from class k; N thus Zil = K. Let E denote equality up to multiplicative and/or additive constant. Then the first term in Eq. (6) can be rewritten as:
N
N -
K
=
Σ
Σ
(-2,
2, 2i)
(17)
(=1
k=1
2,
Let C₁ be the mean of hidden representations from class k; then we have C₁ [2 Σ 2x 2i =
Enehh 2,. Now we build the connection between Eq. (17) and Σ Exie2 1z - 1
Σ
Σ 2
cEll
(18)
Z
K
|2:11 14il1-2 - Σ
2 2TC²k + |Z
Ek
Z,EZ#
1
1
2 -22
2
2 23 +
2
ZZ
ZRk
K1E22
RIEZE 2,E22
2. 2:E2
Σ
|
2
Σ
Σ
2 Zi
1ZAl
K
2,EZ2 2, Zi
|
E
Σ
2,
7
ZRk
Zz 2,E2
2,EZs 2,E
(lzz 12 2, zi)
[Zk
2, Zz E.
Σ E 7,E7% 2.E
(-2, zi)
(19)
[Zkl
By comparing Eq. (17) and Eq. (19), the only difference is that Eq. (19) includes more positive pairs for loss calculation. Hence, minimizing Eq. (17) can be viewed as approximately minimizing Eq. (19) or Eq. (18) through sampling positive pairs. As demonstrated in the work (Boudiaf et al., 2020). Eg. (18) can be interpreted as a conditional cross-entropy between Z and another random variable Z. whose conditional distribution given Y is standard Gaussian centered around cy Z
Y N~ N II:
12 = HH(Z Y) + ( Y) 2 H(Z YY)
(20)
Z:EZ
Hence, minimizing the first term in Eq. (6) is approximately minimizing HZZYY).
Discussion: We note that the assumption "the mean of the representations obtained from Z and 2 are the same" can be inferred by the first assumption about data augmentation. Let pa (X) denote the distribution of samples with class and let x (X( denote the sample with class Recall that we assume the data augmentation function A(-) is strong enough to generate data view that can simulate the test data from the same class. In this regard, the new data view can be regarded as an independent sample from the same class, i.e., A(x) ~ pa (X). Hence, the expectation of Z and Ż is the same and we would approximately have that "the mean of Z and 2 is the same for each class". Particularly, when the number of samples is relatively large, the mean of Z (2) would be
16

---

Published as a conference paper at ICLR 2023
close to the true distribution mean. For example, graph of Cora, the mean absolute difference between the two representations of Z and 2 are [0.018, 0.009, 0.021, 0.024, 0.016, 0.014, 0.0, 0.016, 0.023) for each class, which are actually very small.
A.3 A FIGURATIVE EXAMPLE
In Figure 6, we show an example of adversarial attack which causes the aggregated features for two nodes to be the same. Given two nodes and X2 and their connections, we are interested in predicting their labels. Assume mean aggregator used for aggregating features from the neighbors. Before attack, the aggregated features for them X 00.45 and X2 [0.53] while after attack the aggregated features become the same X = X2 [0.45]. In this context, it is impossible learn classifier that can distinguish the two nodes.
[0.3]
[0.2]
[0.3]
[0.2]
[0.2]
[0.7]
Attack
[0.2]
[0.7]
[0.3]
X2
[0.7]
[0.3]
X1
[0.7]
[0.8]
[0.8]
COL
1== [0.45] R2 [0.53]
X, [0.45]. [0.45]
Figure 6: Given two nodes and X2 and their connections, we are interested in predicting their labels. The color indicates the node label and "[0.3]" suggests that the associated node feature 0.3. Assume mean aggregator is used for aggregating features from the neighbors. Left: we show the clean graph without adversarial attack. The aggregated features for the two center nodes are x [0.45] and &2 10.53]. Right: show the attacked graph where the red edge indicates the adversarial edge injected by the attacker. The aggregated features for the two center nodes become
X [0.45] and X2 [0.45].
B ALGORITHM
We show the detailed algorithm of GTRANS in Algorithm 1. In detail, we first initialize A and Ax zero matrices and calculate L, based on Eq. (6). Since we alternatively optimize A^ and Ax', we update Ax' every Tı epochs and update A every т2 epochs. When the optimization done, sample the discrete graph structure for K times and select the one that results in the smallest C, as the final adjacency matrix.
C DATASETS AND
this section, we reveal the details reproducing the results the experiments. will release the source code upon acceptance.
C.1 OUT-OF-DISTRIBUTION (OOD) SETTING
The -iitof-distribution (OOD) problem indicates that the model does not generalize well to the test data due the distribution gap between training data and test data (Yang al., 2021a), which is also referred to as distribution shifts. Numerous research studies have been conducted to explore this problem and propose potential solutions (Ganin et al., 2016; Zhu al. 202 la; Yang al., 2021b;c; Wu et al., 2022a; Liu et al., 2022a; Chen et al., 2022; Buffelli et al., 2022; Gui et al., 2022; Wu et al., 2022b; You et al., 2023). In the following, we introduce the datasets used for evaluating the methods that tackle the OOD issue in graph domain.
Dataset Statistics. For the evaluation on OOD data, we use the datasets provided by Wu et al. (2022a). The dataset statistics are shown in Table 5, which includes three distinct type of distribu- tion shifts: (1) artificial transformation which indicates the node features are replaced by synthetic spurious features; (2) cross- transfers which means that graphs in the dataset from dif- ferent domains and (3) temporal evolution where the dataset a dynamic one with evolving na- ture. Notably,
the datasets provided by Wu et al. (2022a), which adopted from the
17

---

Published as a conference paper at ICLR 2023
Algorithm 1: GTRAAS for Test-Time Graph Transformation
Input: Pre-trained model fo test graph datasct G1. (A, X'). Output: Model prediction and transformed graph G² (A', xx). Initialize Aa and Ax as zero matrices do
for f O,...,
Compute A'
A and X' X Ax Compute (A(AA. A Ax) as shown in Eq. (6)
if (T(Ti + ra) < Ti then
L Update Ax <- Ax 1/1 VaxL.
else
10
Update AA + 11p (AA - nV ~o C.)
11
fres
the best loss
12
for =0=0, ..... - 1
13
Sample A Bernoulli(A A + AA)
14
Calculate L. with Ao as input if Cs < Eeer then A L.
15
16
17
A' A
X = Ax
Y T((A'X')
Return: Y, (A','')
aforementioned references with manually created distribution shifts. Note that there can mul- tiple Paining/validaitoonfes graphs. Specifically, Cora and Amazon-Photo have 1/1/8 graphs for soanning/yalidation/eee sets. Similarly, the splits are 1/1/5 on Twitch-E, 3/2/3 on FB-100, 5/5/33 on Elliptic, and 1/1/3 on OGB-Arxiv.
Table 5: Summary of the experimental datasets that entail diverse distribution shifts.
Distribution Shift
#Nodes
#Edges
#Classes
Train/Val Split
Adapted From
Artilicial fransiormation
Cora
2,703
5,278
10
Domain-Lovel
Accuracy
Yang et al. (2016)
Ama-Phoo Photo
7,650
119,081
10
Domain- Level
Accuracy
Shehur al. (2018)
Twitch-E
1.91294999 9,498
31,299
153.138
Domain-Level Domain Domain-Level
ROC-AUC
Rozemberezki
(2021a)
Cross-Domain Transfers
FB100
769 41,536
16,656
1,5990.655
Accuracy
Traud et al. (2012)
Temporal Evolution
Elliptic
203.769
234,355
Time-Aware Timee-Aware
FI Score
Pareja ct. (2020)
OGB Arxiv
169,343
1,166.243
Accuracy
Hu et al. (2020)
Hyper-Parameeerr Setting. For the setup of backbone GNNs, we majorly followed Wu et al. (2022a):
(a) GCN: the architecture setup is 5 layers with 32 hidden units for Elliptic and OGB-Arxiv, and layers with 32 hidden units for other datasets, and with batch normalization for all datasets. The learning rate is set to 0.001 for Cora and Amz-Photo. 0.01 for other datasets; the weight decay is 0 for Elliptic and OGB-Arxiv, and 0.001 for other datasets.
(b) GraphSAGE: the architecture setup is 5 layers with 32 hidden units for Elliptic and OGB-Arxiv, and 2 layers with 32 hidden units for other datasets, and with batch normalization for all datasets. The learning rate is set to 0.01 for all datasets; the weight decay is set to 0 for Elliptic and OGB- Arxiv, and 0.001 for other datasets.
(c) GAT: the architecture setup is 5 layers for Elliptic and OGB and 2 layers for other datasets, and with batch normalization for all datasets. Each layer contains 4 attention heads and each head is associated with 32 hidden units. The learning rate is set to 0.01 for all datasets; the weight decay is set to 0 for Elliptic and OGB-Arxiv, and 0.001 for other datasets.
(d) GPR: We use 10 propagation layers and 2 transformation layers with 32 hidden units. The learning rate is set to 0.01 for all datasets; the weight decay is set to 0 for Elliptic and OGB-Arxiv, and 0.001 for other datasets. Note that GPR does not contain batch normalization layers.
18

---

Published as a conference paper at ICLR 2023
For the baseline methods, we tuned their tlype--paaaeetern based the validation performance. For DropEdge, we search the drop ratio in the range of [0, 0.05, 0.1, 0.15, 0.2, 0.3, 0.5, 0.7]. For Tent, search the learning rate in the range of [1e-2, 1e-3, le-4, 1e-5, 1e-6] and the running epochs in [1, 10, 20, 30J. For EERM, we followed the instruction provided by the original paper. For GTRANS, alternatively optimize node features for 7i
epochs and optimize graph structure 72 = epoch. We adopt DropEdge as the augmentation function A(-) and set the drop ratio to 0.5. We use Adam optimizer for both feature learning and structure learning. We further search the learning rate of feature adaptation [0.5, 0.1, 0.01], the modification budget B [0.5%. %, 5%] of the original edges, total epochs T in [5, 10J. We note that the process of tuning hyper-parameters is quick due to the high efficiency of test-time adaptation as we demonstrated in Section 4.1.
in [5e-3, le-3, le-4, le-5, 1e-6], learning rate of structure adaptation in
Evaluation Protocol. For ERM (standard training), we train all the GNN backbones using the common cross entropy loss. For DropEdge, we drop a certain amount of edges at each training epoch. For EERM, it optimizes bi-level problem to obtain trained classifier. Note that the aforementioned three methods do not perform any test-time adaptation and their model parameters fixed during test. For the two test-time adaptation methods, Tent and GTRANS, the GNN backbones pre-trained from ERM and adapt the model parameters or graph data at test time, respectively. Furthermore, Tent minimizes the entropy loss while GTRANS minimizes the contrastive surrogate loss.
first obtain
Quantifying Distribution Shifts. Following SR-GNN (Zhu al.,, 2021a), we adopt central moment discrepancy (CMD) (Zellinger et al., 2017) as the measurement to quantify the distribution shifts in different graphs. Specifically, given a pre-trained model, we obtain its hidden representation on the training graph and test graphs, denoted as Zu and Zu. Then we calculate their distance by the CMD metric, i.e., CMD(Z,) Zu We show the results in Table 6 and we can observe certain distribution shifts as these values are not small. Let's 's take the OGB-Arxiv dataset as an example, where we select papers published before 2011 for training, 201 1014 for validation, and within 2014-2016/206 201 2018/2018-222 2020 for test. In this context, the distribution shift is from the temporal change. In Table 7, we show the CMD values, ERM performance and GTRANS performance. From the table, can find that (1) the CMD value on the validation graph is essentially smaller than those test graphs; and (2) GCN performances on test graphs (with larger shifts) are lower than that on the validation graph.
Table 6: CMD values on each individual graph based on the pre-trained GCN.
GraphID
Go
G
G2
G3
G4
G5
G6
G7
Gs
Amz-Photo
6.4
5.1
5,5
3.7
2.8
3.7
3,9
6,6
Cora
5.4
4.2
4.8
6.3
5.5
4.8
4.6
5,4
Elliptic
80.2
90.8
114.3
86.5
789.3
781.6
99.4
100.4
150.6
OGB-Arxiv
14.7
20.6
10.4
FB-100
29.7
16.9
32.9
Twitch-E
8.6
6.1
9.0
8.4
9.7
Table 7: CMD values and the performances of ERM and GTRANS on OGB-Arxiv
Method
2011-2014 (Val)
2014-2016
2014-2016
2016-2018
2018-2020
CMD
2.5
14.7
14.7
20.6
10.4
ERM
45.3240.50
41.29+1.13
41.29+1.13
38.69+1.33
35.78+1.88
GTRANS
45.82+0.38
44.03+0.95
44.03+0.95
41,90 1. 1.28
38.81+1.47
C.2 ABNORMAL FEATURES
Dataset Statistics. In these two settings, we choose the original version of popular benchmark datasets Cora, Citeseer, Pubmed and OGB-Arxiv. The statisties for these datasets are shown in Table Note that we only have one test graph, and the injection of abnormal features or adversarial attack happens after the training process of backbone model, which can be viewed evasion attack.
19

---

Published as a conference paper at ICLR 2023
Table 8: Dataset statistics for experiments on abnormal features and adversarial attack.
Dataset
Classes
Nodes
Edges
Features
Training Nodes
Validation Nodes
Test Nodes
Cora
7
2708
5278
1433
20 per class
500
1000
Citeseer
3327
4552
3703
20 per class
500
1000
Pubmed
19717
44324
500
20 per class
500
1000
OGB-Arxiv
40
169343
1166243
128
54%
18%
28%
Hyper-Parammeer Settings. We closely followed AirGNN (Liu et al., 2021a) to set up the hyper- parameters for the baselines:
(a) GCN: the architecture setup is 2 layers with 64 hidden units without batch normalization for Cora, Citeseer and Pubmed, and 3 layers with 256 hidden units with batch normalization for OGB-Arxiv. The learning rate is set to 0.01.
(b) GAT: the architecture setup is 2 layers with hidden units in each of the 8 heads without batch normalization for Cora, Citeseer and Pubmed, and 3 layers with 32 hidden units in each of the heads with batch normalization for OGB-Arxiv. The learning rate set to 0.005.
(c) APPNP: the architecture setup is 2-layer transformation with 64 hidden units and 10-layer prop- agation without batch normalization for Cora, Citeseer and Pubmed: the architecture is set to 3-layer transformation with 256 hidden units and 10-layer propagation with batch normalization for OGB-Arxiv. The learning rate is set to 0.01.
(d) AirGNN: The architecture setup is the same as APPNP and the hyper-parameter À is set to 0.3 for OGB-Arxiv and 0.5 for other datasets.
(e) AirGNN-t: The architecture setup the same AirGNN but we tune the hyper-parameter in AirGNN based on performance on the combination of training and validation nodes at test stage. This is because the test graph has the same graph structure as the training graph; thus we can take advantage of the label information of training nodes (as well as validation nodes) to tune the hyper-papce parr-pparaeters. Specifically, we search X in the range of [0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9) for each noise ratio.
For the setup of GTRANS, we alternatively optimize node features for T₁ 4 epochs and optimize graph structure drop ratio to 0.5. We use Adam optimizer for both feature learning and structure learning. We further search the learning rate of feature adaptation 171 in [I, 1c-1, 1e-2], total epochs T in [10, 20J. The modification budget B to 5% of the original edges and the learning rate of structure adaptation 7)2 set to 0.1. It is worth noting that we use a weighted combination of contrastive loss and training classification loss i.e., Luain + >L., instead of optimizing the contrastive loss alone. We adaopt this strategy because that the training graph and the test graph were the same graph before the injection of abnormal features. Here the X is tuned in the range of [le-2, le-3, le-4]. We study the effects of contrastive loss and training classification loss in Appendix D.7.
epoch. We adopt DropEdge as the augmentation function A(-) and set the
C.3 ADVERSARIAL ATTACK
Dataset Statisties. We used OGB-Arxiv for the adversarial attack experiments and the dataset statis- tics can be found in Table 8. Again, we only have one test graph for this dataset.
Hlype--Parameter Settings. The setup of GCN and GAT is the same that in the setting of abnor- mal features. For the defense methods including SimPGCN, RobustGCN and GCNJaccard, we use the DeepRobust (Li et al., 2020) library implement them. For GCNJaccard, we tune its threshold hyper-parameter in the range of [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9]. The hyper-parameter is also tuned based on the performance training and validation nodes (same as Appendix C.2). Note that the popular defenses ProGNN (Jin et al., 2020) and GCNSVD (Entezari et al., 2020) were not included because they throw OOM error due to the expensive eigen-decomposition operation.
We use the official implementation of the scalable attack PR-BCD (Geisler et al., 2021) l) to attack the test graph. We note that when performing adversarial attacks, the setting is more like transductive setting where the training graph and test graph are the same. However, the test graph becomes differ- ent from the training graph after the attack. Since the training graph and test graph were originally the same graph, we use weighted combination of contrastive loss and training classification loss,
20

---

Published as a conference paper at ICLR 2023
Le., Luain + XLe, instead of optimizing the contrastive loss alone. For the setup of GTRANS, alternatively optimize node features for 71 = epoch and optimize graph structure 72 = 4 epochs. We fix the learning rate of feature adaptation 7) to 1e-3, learning rate of structure adaptation 7/2 to 0.1, À to I, total epochs T to 50 and modification budget to 30% of the original edges.
C.4 HARDWARF AND SOFTWARE CONFIGURATIONS.
We perform experiments NVIDIA Tesla V100 GPUs. The GPU memory and running time ported in Table are measured on one single V100 GPU. Additionally, we use eight CPUs, with the model name Intel(R) Xeon(R) Platinum 8260 CPU @ 2.40GHz. The operating system use is CentOS Linux 7 (Core).
D MORE EXPERIMENTAL RESULTS
D.1 COMPARISON TO GRAPH DOMAIN ADAPTATION
Our work is related to graph domain adaptation (GraphDA) (Shen et al., 2020; Wu et al., 2020; Zhu et al., 2021a), but they are also highly different. In Table 9, we summarize the differences between GraphDA and GTRANS. In detail, there the following differences:
(a) Data and losses: GraphDA methods optimize the loss function based on both labeled source data (training data) and unlabeled target data (test data), while GTRANS only requires target data during inference. Hence, GraphDA methods are infeasible when access to the source data is prohibited such online service.
(b) Parameter: To our best knowledge, existing GraphDA methods are model-centric approaches while GTRANS a data-centric approach. GTRANS adapts the data instead of the model, which can be more useful in some settings as we showed in the Example of Section 3.3.
(c) Efficiency: GraphDA is indeed a training-timm -ime adaptation and for each given test graph, would require training the model on the source and target data. Thus, it is much less efficient than GTRANS, especially when we have multiple test graphs (e.g., 33 test graphs for Elliptic).
Table 9: Comparison between GraphDA and GTRANS. They differ by their data and losses.
Setting
Source
Target
Train Loss
Test Loss
Parameter
Efficiency
GraphDA
Gn
G G
C(G Vir L(Grr; Gie)
So
Low
GTRANS
(
GE
High
To compare their empirical performance, we include two GraphDA methods (SR-GNN (Zhu et al., 202 and UDA-GCN (Wu et al., 2020)) and one general domain adaptation method (DANN (Ganin et al., 2016)). SR-GNN regularizes the model's performance on the source and target domains. Note that SR-GNN is originally developed under the transductive setting where the training graph and test graph are the same. To apply SR-GNN in OOD setting, we assume the test graph is available during the training stage of SR-GNN, as typically done in domain adaptation methods. UDA-GCN another work that tackles graph data domain adaptation, which exploits local and global informa- tion for different domains. In addition, we also include DANN, which adopts an adversarial domain classifier to promote the similarity of feature distributions between different domains. We followed the authors' suggestions in their paper to tune the hyper-parameter and the results are shown in Table 10. On the one hand, we can observe that GraphDA methods generally improve the perfor- mance of GCN under distribution shift and SRGNN is the best performing baseline. On the other hand, GTRANS performs the best on all datasets except Amz-Photo. On Amz-Photo, GTRANS does not improve much as SR-GNN, which indicates that joint optimization over source and target is necessary for this dataset. However, recall that domain adaptation methods are less efficient due source and target: the adaptation time of SR-GNN on the graphs of
to the joint optimization Amz-Photo is 83.5s while that of GTRANS is 4.9s (plus pre-training time 10.1s). Overall, test-time time graph transformation exhibits strong advantages of effectiveness and efficiency.
21

---

Published as a conference paper at ICLR 2023
Table 10: Performance comparison between GTRANS and graph domain adaptation methods.
Method
Amz-Photo
Cora
Elliptic
FB-100
OGB-Arxiv
Twitch-E
ERM
93.79=0.97
91.59+1.44 .44
50.90=1.51
54.04=0.94
38.59+1.35
59.8940.50
UDA-GCN
91.70=0035
92.65+0.46
51.57=1.31
54.11=0.54
39.43+0.71
52.12+0.38
DANN
94.08+0.21
92.89=0.64
53.00=0.97
51.53=1.47
16.60+1.26
60.13+0.53
SRGNN
94.64:0.17
94.08+0.28
51.9440.81
54.08#1.10
38.92+0.65
59.21+0.51
GTRANS 94.13=0.77
94.6620.63
55.88+3.10
54.32+0.60
41.59+1.20
60.42+0.86
D.2 COMPARISON TO GRAPH STRUCTURE LEARNING
Our work is also relevant to graph structure learning (GSL) (Franceschi et al., 2019; Jin et al., 2020; Chen et al., 2020; Zhao al., 2021b; Rozemberczki et al., 2021b; Halcrow al., 2020; Fatemi et al., 2021) which learns the graph structure during the training time while not adapting the graph structure at test stage. Our proposed test-time graph transform essentially different from these works as we do not modify the training data but only the test data. It can be of interest to adopt GSL method at test time by also adapting the test graph structure. However, most existing GSL methods optimize the cross entropy loss defined on the labels to update graph structure, thus not applicable in the absence test labels. One exception is SLAPS (Fatemi et al., 2021) which utilizes a self- supervised loss together with the cross entropy loss to optimize the graph structure. However, the default setting in SLAPS is generating structure for raw data points (with no given graph structure). Hence, using SLAPS for our settings requires considerable changes. Furthermore, highlight two more weaknesses of SLAPS compared to GTRANS.
(a) Introducing additional parameters. SLAPS uses denoising loss self-supervision. In detail, it first injects noise into node features and trains a denoising autoencoder to denoise the noisy features. This introduces additional parameters from the denoising autoencoder and inevitably changes the model architecture.
(b) Not learning features. As other GSL methods, SLAPS does not learn node features. We argue that feature learning is highly important under the abnormal feature setting shown in Table 16. For example, structure learning only improves GCN by 2% on OGB-Arxiv while feature learning can improve GCN by 20%. Thus, without the feature learning component, the performance will significantly drop when encountering noisy features.
Since GTRANS is highly versatile and we can use any self-supervised loss as the surrogate loss, we can simply replace the contrastive loss in Eq. (6) with the denoising loss of SLAPS instead of paying considerable efforts in adjusting SLAPS. We refer to the loss used for denoising SLAPS loss and adopt it for TTGT. Note that we first train the parameters of the DAE used for denoising while keeping the pre-trale tre-trained model fixed. Then fix both DAE and the pre-trained model and optimize the test graph for TTGT. The results are shown in Table 11. From the table, we can observe that the SLAPS loss (or feature denoising loss) does not work as well as the contrastive loss.
Table 11: Comparison between SLAPS loss and our contrastive loss.
Amz-Photo
Cora
Elliptic
FB-100
OGB-Arxiv
Twitch-E
None
93.7940.97
91.59#1.44
50.90+1.51
54.0420.94
38.59+1.35
59.89+0.50
SLAPS
93.97+1.04
11.41+1.23 94.6620.63
50.54=1.81
54.08=0.76
59.85=0.68 11.38+1.35
L, in Eq. (6)
94.13+0.77
55.88+3.10
54.32+0.60
41.59+1.20
60.4220.86
D.3 COMPARISON TO AD-GCL
Next, we compare our method with graph contrastive learning method with learnable augmentation AD-GCL (Suresh et al., 2021). Since AD-GCL is originally designed for graph classification as a pre-training strategy, the direct empirical comparison between AD-GCL and GTRANS is not easy. However, due to the flexibility of GTRANS, we can integrate AD-GCL into our TTGT framework, denoted as TTGG-AD-GCI. We present the empirical results in Table 12. We can observe that
22

---

Published as a conference paper at ICLR 2023
TIGT+AD-GCL generally performs worse than GTRANS except on Amz-Photo, which indicates that GTRANS stronger realization of TTGT. Furthermore, we highlight some key differences between it and GTRANS.
(a) AD-GCL requires optimization of min-max problem which involves parameters of graph structure and model. Thus, adopting it for TTGT would change the pre-trained model archi- tecture.
(b) AD-GCL only augments the graph structure while learning the features. We argue that feature learning is highly important under the abnormal feature setting as shown in Table 16. For example, structure learning only improves GCN by 2% on OGB-Arxiv while feature learning can improve GCN by 20%. Thus, without the feature learning component, the performance will significantly drop when encountering noisy features.
(c) According to Eq. (9) in the AD-GCL paper, it calculates the similarities between all samples within each mini-batch. When we increase the batch size, we would easily get the out-of- memory issue while small mini-batch will slow down the learning process. As consequence, TTGT+AD-GCL is less efficient than GTRANS: the adaptation time of TTGT+AD-GCL on OGB-Arxiv 12.7s while that of GTRANS is 2.6s.
Table 12: Comparison between GTRANS and AD-GCL under the TTGT framework.
Amz-Photo
Cora
Elliptic
FB-100
OGB-Arxiv
Twitch-E
ERM
93.79=0.97
91.59:1.44
50.90=1.51
54.0440.94
38.59+1.35
59.89+0.50
TTGT+AD-GCL
94.96+0.52
9..38=1.35
54.38+2.77
53.8110.87
39.1620.98
59.78+0.65
GTRANS
94.13+0.77
94.6620.63
55.8843.10
54.32+0.60
41.59#1.20
60.42+0.86
D.4 OUT-OF-DDSTRIBUTION (OOD) SETTING
To show the performance on individual test graphs, we choose GCN the backbone model and include the box plot on all test graphs within each dataset in Figure 7. We observe that GTRANS generally improves over each test graph within each dataset, which validates the effectiveness of test-time graph transformation.
ERM GTrmms
0.860
Accuracy
0.7
Accuracy
0.825
0.800
0.875
ERM
0.5
0,850
T1
T2
T3
T4
T5
T6
17
T8
T1
T2
T3
T4
T5
T7
T8
T9
(a) Amz-Photo
(b) Elliptic
2.55
MW
2.4
Cheaa
0.4
142
8.9
152
132
CM
(c) OGB-Arxiv
(d) FB-100
(c)
Twitch-E
Figure 7: Classification performance on individual test graphs within each dataset for OOD setting.
D.5 ABNORMAL FEATURES
For each model, present the node classification accuracy all test nodes (i.e., both normal and abnormal ones) in Figure 8, GTRANS significantly improves GCN in terms of the performance on all test nodes for all datasets across all noise ratios. For example, Cora with 30% noisy nodes,
23

---

Published as a conference paper at ICLR 2023
GTRANS improves GCN by 31.0% on overall test accuracy. These results further validate that the proposed GTRANS can produce expressive and generalizable representations.
95
0-4
Ardls
07nm
Rato of No hodes
Rutoo of Nodes
Rado Nesy Nocia
Raie hosy Nodia
(a) Cora
(b) Citeseer
(c) Pubmed
(d) OGB-Arxiv
Figure 8: Overall node classification accuracy under the setting of abnormal features. GTRANS significantly improves the performance of GCN on both abnormal nodes and overall nodes.
D.6 INTERPRETATION THE REFINED GRAPH FOR ADVERSARIAL ATTACK SETTING
To understand the modifications made the graph, compare several properties among clean graph, attacked graph (20% perturbation rate), graph obtained by GCNJaccard, and graph obtained by GTRANS in Table 13. We follow the definition in (Zhu et al., 2020) to measure homophily; "Pairwise Feature Similarity" is the averaged feature similarity among all pairs of connected nodes; "#Edge+/-" indicates the number of edges that the modified graph adds/deletes compared to the clean graph. From Table 13, we observe that first, adversarial attack decreases homophily and feature similarity, but GTRANS and GCNJaccard promote such information to defend against adversarial patterns. Second, both GTRANS and GCNJaccard focus on deleting edges from the attacked graph, but GCNJaccard removes substantially larger amount of edges, which may destroy clean graph structure and lead to suboptimal performance.
Table 13: Statistics of modified graphs. GTRANS promotes homophily and feature similarity.
GTRANS GCNJaccard
Attacked
Clean
Homophily Pairwise Feature Similarity
0.689
0.636
0.548
0.654
0.825
0.863
0.809
0.827
#Edges
1,945k
1,754k
2,778k
2,316k
#Edge+
108k
118k
463k
#Edge-
479k
679k
0.6k
D.7 ABLATION STUDY ON SURROGATE LOss
Since we optimized combined loss in the settings of abnormal features and adversarial attack, we now perform ablation study to examine the effect of each component. We choose GCN as the back- bone model and choose 0.3 noise ratio for abnormal features. The results for abnormal features and adversarial attack are shown Tables 14 and 15, respectively. "None" indicates the vanilla GCN without any test-time adaptation and "Combined" indicates jointly optimizing combination of the two losses. From the two tables, we can conclude that (1) both L, and Lizan help counteract ab- normal features and adversarial attack; and (2) optimizing the combined loss generally outperforms optimizing L. or Liin alone.
D.8 ABLATION STUDY ON FEATURE LEARNING AND STRUCTURE LEARNING
In this subsection, we investigate the effects of the feature learning component and structure learning component. We show results for abnormal features and adversarial attack in Tables 16 and 17. respectively. Note that "None" indicates the vanilla GCN without any test-time adaptation; "A" or "X"" is the variants of GTRANS which solely learns structure node features; "Both" indicates the method GTRANS that learn both structure and node features. From Table 16, we observe that (1) while both feature learning and structure learning improve the vanilla performance, feature
24

---

Published as a conference paper at ICLR 2023
Table 14: Performance comparison when optimizing different losses for abnormal feature setting. Both Ls and Lusin help counteract abnormal features; optimizing the combined loss generally out- performs optimizing Lg or Luiin alone.
All Test Nodes
Abnormal Nodes
Dataset
None
L,
Luain
Combined
None
L,
Luiin
Combined
OGB-Arxiv
44.29=1.20
46.70+1.20
64.60+0.22
64.6420.24 31.50#1.12
35.22+1.17 57.5420.93 57.6940.93
Citeseer
39.26+2.02
45.4142.71
54.9741.55
52.54=1.08 17.30+1886
32.93+2.81
42.6742.78
44.10+2,99
Cora
36.35=1.87
48.7143.02
66.7742.54
44.29
15.8042.33
35.4024.05
61.6743.64 63,90+2.55
Pubmed
62.72=1.20
65.49*1.65 66.56+0.64
10.55=1.55 36.47=1.85 56.77=3.60 60.20+1.97 67. 67.93+2.11
Table 15: Performance comparison when optimizing different losses for adversarial attack setting.
Both C, and Luain help counteract adversarial attack: optimizing the combined loss generally out- performs optimizing Lg or Luiin alone. r denotes the perturbation rate.
I Loss
r=5%
r= 100
r=15%
r=20%
r=25%
None
57.47=0.54
47.97=0.65
38.04+1.22
29.05+0.73
19.58+2.32
L.
62.40=0.45
59.76=0.93
57.85+1.03
55.26+1.35
52.6442.35
Lrain Combined
65.5440.25
64.00+0.31
62.99+0.34
61.95+0.40
61.55+0.58
66.29=0.25
65.16+0.52
64.40++.38
63.4440.50
62.95+0.67
learning is more powerful than structure learning: (2) combining them does not seem to further improve the performance but it achieves comparable performance sole feature learning. From Table 17, we observe that (1) while both feature learning and structure learning can improve the vanilla performance, structure learning is more powerful than feature learning; and (2) combining them can further improve the performance. From these observations, learning is more crucial for counteracting feature corruption and structure learning is more important for defending structure corruption; and (2) combining them always yields better or comparable performance.
conclude that (I) feature
Table 16: Ablation study on feature learning and structure learning for abnormal feature setting. While both feature learning and structure learning can improve the vanilla performance, feature learning is more powerful than structure learning. Combining them does not seem to further improve the performance but it achieves comparable performance to sole feature learning.
All Test Nodes X'
Abnormal Nodes X'
Dataset
None
A'
Both
None
A'
Both
OGB-Are Arxiv 46.02+1.00 44.29=1.20
64.88+0.23
64.6420.24
31.50=1.12
31.96
12.1233.83
57.69+0.93
Citeseer
39.26=2.02
39.67+1.96
54.99=1.55
54.97=1.55
17.30=1.86
17.13=1.81
42.73+2.81
42.67+2.78
Cora
36.35+1.87
37.0241.82
67.40+1.62
67.29=1.44
15.80+2.33
15.67+2.15
64.1743.18
63,90+2.55
Pubmed
62.72+1.20
62.50+1.21
70.53+1.52 70.55+1.55 36.4721.85
36.57+1.96
67.9042.07
67.9342.11
D.9 COMPARING DIFFERENT SELF-SUPERVISED SIGNALS
As there can be other choices to guide our test-time graph transformation process, we examine the effects of other self-supervised signals. We choose the OOD setting to perform experiments and consider the following two parameter-fre self-supervised loss:
(a) Reconstruction Loss. Data reconstruction is considered as good self-supervised signal and we can adopt link reconstruction (Kipf & Welling, 2016b) as the guidance. Minimizing the recon- struction loss is equivalent to maximizing the similarity for connected nodes, which encourages the connected nodes to have similar representations.
(b) Entropy Loss. Entropy loss calculates the entropy of the model prediction. Minimizing the entropy can force the model to certain about the prediction. It has been demonstrated effective in Tent (Wang et al., 2021) when adapting batch normalization parameters.
25

---

Published as a conference paper at ICLR 2023
Table 17: Ablation study on feature learning and structure learning for adversarial structural attack setting. While both feature learning and structure learning can improve the vanilla performance, structure learning is more powerful than feature learning. Combining them can further improve the performance.
Param r=5%
7=10%
r= r=15%
r=20%
r=25%
None
57.47+0.55
47.97=0.65
38.04#1.22
29.05=0.73
19.58+2.32
X'
64.16+0.22
61.59+0.29
60.07=0.32
59.04=0.49
58.8240.68
A'
65.93+0.32
64.31+0.71
63.14+0.39
61.42+0.58
60.18+1.55
Both
66.29:0.25
65.16+0.52
64.40=0.38
63.44+0.50
62.95+0.67
(c) SLAPS Loss. SLAPS (Fatemi et al., 2021) utilizes self-supervision to guide the graph structure learning process. Specifically, it injects random noise into node features and employs denois- ing autoencoder (DAE) to denoise the node features. We refer to the loss used for denoising as SLAPS loss and adopt it for TTGT. Note that we first train the parameters of the DAE used for denoising while keeping the pre-trained model fixed. Then we fix both DAE and the pre-trained model and optimize the test graph for TTGT.
We summarize the results in Table 18. From the table, we observe that in most of the cases, the above three losses underperform our proposed surrogate loss and even degrade the vanilla performance. validates the effectiveness of our contrastive loss in guiding the test-time graph transformation.
Table 18:
Comparison of different sele-supervised signals for OOD setting. The reconstruction loss and entropy loss generally underperform our proposed loss.
Amz-Photo
Cora
Elliptic
FB-100
OGB-Arxiv
Twitch-E
None Recon
93.7940.97
91.59 .44
50.90=1.51
54.0420.94
38.59+1. 1.35
59.89+0.50
93.77+1.01
91.37=1.41
49.33=1.37
53.94+1.03
44.93+4.06
59.17+0.77
Entropy
93.67+0.98
91.54+1.14
49.93=1.56
54.2940.97
41.11+2.19
59.48=0.64
SLAPS
93.97+1.04
91.41+1.23
50.54=1.81
54.08+0.76
41.38+1.35
59.85+0.68
C, in Eq. (6)
94.13+0.77
94.6620.63
55,88+3.10
54.3220.60
41.59+1.20
60.4220.86
Gradient Correlation. In Figure 2, we have empirically verified the effectiveness of Theorem when adopting the surrogate loss in Eq. (6) as L., We further plot the values of p(G) with different surrogate losses (i.c., entropy, reconstruction and SLAPS) and C. on one test graph in Cora in Figure 9. We can observe that a positive p(G) generally reduces the test classification loss. For example, when using entropy loss, the test loss generally reduces when p(G) is positive and starts increase after p(G) becomes negative.
Tell
Considten
04
Conslation
Conelitor Teet
www.oltooeTToooo Teael
3.5
Tust 6. Commaatin (12)
Taxk Balk Compittion (CC)
2
0.1
0.0
(a) Entropy Loss
(b) Reconstruction Loss
(c) SLAPS Loss
Figure 9: The relationship between p(G') and L. when adopting different surrogate losses.
D.10 SENSITIVITY TO HYPER- HYPER-PARAMETTE PARAMETER B
In this subsection, we examine the sensitivity of GTRANS' performance with respect to the per- turbation budget, i.e., hyper-parameter B. Specifically, vary the value of B in the range of
26

---

Published as a conference paper at ICLR 2023
{0.5%, 1%, 5%, 10%, 20%, 30%} and perform experiments the OGB-Arxiv dataset for the three settings Table 19. Specifically, "Abn. Feat" stands for abnormal feature setting with 30% noisy feature while "Adv. Attack" stands for the adversarial attack setting with 20% perturbation rate. From the table, we can observe budget B has smaller effect on OOD and abnormal feature settings while highly impacting the performance under structural adversarial attack. This is because most of the changes made by adversarial attack are edge injections as shown in Table 13, and we need to use a large budget B to remove adversarial patterns. By contrast, GTRANS much less sensitive the value of B in the other two settings.
Table 19: The change of model performance when varying budget B on OGB-Arxiv.
Setting
B=0.5%
B=1%
B=5%
B=10%
B=20%
B=30%
OOD
40.52
40.69
41.32
41.40
41.70
41.65
Abn. Feat.
64.78
64.80
64.64
64.60
64.57
64.57
Adv. Attack
56.66
56.89
58.30
59.93
62.31
63.47
D.11 DIFFERENT AUGMENTATIONS USED IN CONTRASTIVE Loss
In Eq. (6), we used DropEdge the augmentation function A(-) to obtain the augmented view. In practice, the choice of augmentation can be flexible and here we explore two other choices: node dropping (You et al., 2020) and subgraph sampling (Zhu et al., 2021b). We perform experiments on OOD setting with GCN as the backbone model report
results in Table 20. Specifically, adopt ratio of 0.05 for node dropping, and ratios of 0.05 and 0.5 for DropEdge. From the table, we can observe that (1) GTRANS with any of the three augmentations can greatly improve the performance of GCN under distribution shift, and (2) different augmentations lead to slightly different performance on different datasets.
Table 20: Performance of GTRANS with different augmentation used in contrastive loss.
Augmentation
Amz-Phote
Cora
Elliptic
FB-100
OGB-Arxiv
Twitch-E
Node Dropping
94.45=0.70
95.0010.65
56.57+2.99
54.15+0.60
39.95+1.11
60.38+0.74
Subgraph Sampling
94.18+0.75
94.95+0.64
55.40=3.00
54.51+0.56
41.44
60.52+0.80
DropEdge (0.05)
94.43+0.68
95.10=0.66
56.78+2.86
54.1740.60
40.19+1.08
60.3110.74
DropEdge (0.5)
94.13+0.77
94.66+0.63
55.88+3.10
54.32+0.60
41.59#1.20
60.4240.86
ERM
93.79+0.97
91.59+1.44
50.90#1.51
54.0440.94
38.59+1.35
59.89+0.50
27


Reviews:
[{"review_id": "YvN2EbxCkI", "reviewer": "Reviewer_aTyX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper aims at improving the performance of GNN in the test time by transferring the node features and structure.\nMore specifically, the transformation is optimized by a contrastive surrogate loss with respect to the embedding from the pretrained model.\nExtensive experiments are conducted on different settings and datasets, the results somehow prove the effectiveness of the proposed method.", "summary_of_the_review": "My major concerns is the difference between the problem setting and the GraphDA methods.\nCurrently, I think they are quite similar so the technical contribution and baselines are somehow weak to me.\nHowever, if the authors can well address their difference, I will improve the final rating by reconsidering the technical contribution.", "strength_and_weaknesses": "**Strength**\n- The motivation of this paper is interesting, the authors consider several critical problems in the test time of GNN, including OOD, feature anomaly and adversarial attack.\n- The paper is overall easy to follow.\n- The experiments are extensive.\n\n**Weakness**\n- The overall problem setting is quite similar to the graph domain adaptation(GraphDA) where the source domain graph data provides a pre-trained model and target domain is the test graph without labels. However, the authors do not mention this active research field as well as the baseline methods. In the GraphDA field, the transformation on the target domain is a quite common operation. Concerning the Equation (6), it is directly computed on the pre-trained model and serves as a weight/guidance on the trasnformation learning, this is an explicit domain adaptation step where the knowledge from the source domain is transformed to the target domain. The authors are required to clarify the difference between this paper and GraphDA task.\n- The so-called parameter free transformation is quite common in contrastive learning. In this paper, the dropedge is only a classic one and many other transformations such as feature shuffling, subgraph sampling can be explored.\n- The Theorem 1. is somehow weired, in the test time the graph is unlabelled and the classification loss is no longer appliable. In this situation, will theorem 1 affect the model training and transformation selection?\n- In the OOD setting, the improvements is not significant and the authors are expected to explain on it, especailly without comparing the GraphDA methods.\n- In the nosiy feature setting, the proposed method only works on the small dataset and seems not working on the larger dataset, the authors are expected to discuss on it.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "AkcyVclzfX", "reviewer": "Reviewer_3Tit", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "GNN is a new technique that can be used in many areas such as recommendations, drug discovery, social computing, etc. How to learn the  graph representation is key issue in the area of GNNs. This paper proposes a new method to empower the graph representation learning with test-time graph transformation.  Aslo, this paper provides theoretical analysis on the design of the framework and discusses why adapting graph data works better than adapting the model. Extensive experiments on several datasets show its effectiveness. ", "summary_of_the_review": "GNN is a new technique that can be used in many areas such as recommendations, drug discovery, social computing, etc. How to learn the  graph representation is key issue in the area of GNNs. This paper proposes a new method to empower the graph representation learning with test-time graph transformation.  Aslo, this paper provides theoretical analysis on the design of the framework and discusses why adapting graph data works better than adapting the model. Extensive experiments on several datasets show its effectiveness. \n\nMost of prior work focuses on to improve graph representations via model structure design. Working on the test-time graph is new direction. This paper proposes a new method in this new direction, which will be useful to resolve the problem of dynamic graph learning. ", "strength_and_weaknesses": "Strength.\n1. The research is novel and interesting. \n2. The paper is well-written and easy to follow. \n\nWeakness.\n1. This paper does not provide runnable code to reproduce the result. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5vafF9_O3M", "reviewer": "Reviewer_7RMb", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a method which can adapt a testing graph for best performance with some pretrained GNN model.  It finds this change to the test graph by jointly optimizing the feature and adjacency matrices via projected gradient descent to maximize a self-supervised loss (basically drop edge + DGI) over the test graph itself.  Extensive experimental results are performed some synthetic distribution shift scenarios to illustrate the model's capabilities.\n\nThe paper seems like it could potentially be a nice contribution, but it could use a little refinement.\n", "summary_of_the_review": "The authors have addressed the majority of my concerns and provided substantially more evidence to support their method.", "strength_and_weaknesses": "Strengths:\n+ Interesting problem setting\n+ Nice experimental evaluation on a variety of real datasets.\n+ Theory almost convinces me.\n\nWeaknesses\n- All experiments are on datasets which use manually created distribution shifts.  The scale of the shifts (and therefore the difficulty of the task) are impossible to ascertain without reporting more about these tasks.  For instance, the distributional shift could be quantized for each dataset (per task).\n- One method which seemingly might work well in this scenario (SR-GNN) is suspiciously avoided.  But I think the method (or some similar domain shift regularization) would make a very natural baseline, and illustrate the difference between the case where the test is available (for SR-GNN) and when it is not (this paper).\n- Another method which assumes there is test data available (AirGNN-t) is similarly not \n- Theorem 1 doesn’t provide much value (and I can’t believe it's unique to this paper -- it's just a general statement about learning with a surrogate loss).  Might I suggest citing some sources for this here?  \n- I wonder if some more baselines could be added (even simpler ones).  This would add to the result.\n\nMinor comments\n- I would love a stronger emphasis on the connection between Theorem 1 and 2.  I’m not sure what to do here, but I had to revisit this a couple times.\n\n- $\\Delta A$ just feels hard to read, could you use a subscript or something? (e.g. $\\Delta_A$ or $A_\\Delta$)\n\n- There's some missing related work on graph structure learning (all of which makes the same sparsity assumption as this work iirc)\n\n  - “Grale: Designing networks for graph learning” - Halcrow et al\n  - “Pathfinder Discovery Networks for Neural Message Passing” - Rozemberczki et al\n  - \"SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networks\" - Fatemi et al\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3Ia4dSESTj", "reviewer": "Reviewer_2PUQ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents a test-time graph transformation approach to improve graph representation learning performance. Specifically, during test time, the structure and features of the test graph will be optimized through a contrastive learning objective. Experiments on node classification under various settings demonstrate the effectiveness of this data-centric approach over model adaptation approach.\n", "summary_of_the_review": "Overall I like the idea of employing test-time transformation to improve graph representation learning performance. However, there are some technical contributions that are slightly overclaimed. Experiments also only show very marginal improvements. Therefore, I recommend rejection at this time.", "strength_and_weaknesses": "Strengths:\n+ This paper proposes a novel idea that optimizes the graph structure and features of the test graph.\n+ The writing is satisfactory and the idea is clear to follow.\n\nWeaknesses:\n- Several claims are not fully substantiated.\n  1. Theorem 1 gives a criterion on selecting the surrogate objective while no empirical nor theoretical evidence is given to show that the contrastive learning (Eq. 6) approximates the classification loss. It could be better to show, for example on one dataset that the gradient paths of the contrastive learning indeed are close to that of the classification objective.\n  2. Theorem 2 relies on very strong assumptions that the mean of $Z$ and $\\hat{Z}$ remain the same for each class. Can authors further justify that this assumption is realistic?\n  3. For Eq. (6) the authors claim that existing contrastive learning objectives need extra prediction head that will alter the network architecture. It is not true. For example, the JSD loss and the triplet margin loss do not include additional parameters. Also, it is possible to use bootstrapping-based loss to update the graph structure.\n  4. There are also several graph contrastive learning approaches that leverage learnable graph augmentation, which should be considered as baselines as well. For example Adversarial Graph Augmentation to Improve Graph Contrastive Learning, NeurIPS 2021\n  Considering the above points, I believe the third contribution needs further elaboration. The technical contribution for the parameter-free surrogate objective is undermined.\n- From Table 1, it is very hard to say that GTrans achieves significantly better performance over baselines. Almost all performance gains fall into one sigma. Also, I am curious about how to select and how sensitive the model to the parameter B as it controls the overall degree of graph transformation. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "36ZL1E95Bdp", "reviewer": "Reviewer_WrUj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a data-centric approach for improving the test set performance of GNNs under distribution shift, abnormal features, and adversarial attacks. In particular, the approach assumes the existence of a pre-trained GNN model and aims at improving the test set performance by updating the graph structure and node attributes at the test time with a surrogate loss function. Some theoretical results have been provided to explain why the proposed approach works. A good set of experimental results have been also provided across different setups to show the benefit of the approach empirically.", "summary_of_the_review": "The paper shows strong results with a combination of two existing techniques (graph structure learning, and a contrastive surrogate loss function for self-supervised learning) during test time. While the empirical aspect of the paper is strong (expect for some possible GSL baselines), the theoretical aspect (and intuitions) are somewhat lagging. ", "strength_and_weaknesses": "Strengths: \n+ Good set of experiments across different tasks and with different GNNs as backbone\n+ Interesting analysis of the results (I like Table 4)\n+ Clarity of writing\n+ Good set of related work\n\nWeaknesses:\n- The surrogate loss function used in Eq. 6 has been previously used in multiple unsupervised graph representation learning approaches and its merit has been established. Moreover, modifying the graph structure and node features has also been vastly studied in previous work, but as far as I know in all works it has been done during training. So the main novelty of the presented work seems to be in using the combination of the above two **only at the test time** (in fact at a high-level the paper could be viewed as a generalization of the SLAPS model [1] applied only at the test time). This is fine given the high performance of the model. But that makes me wonder why the approach has not been tested against other graph structure learning (GSL) approaches when GSL is done both during training, and also during testing with a fixed model (only the structure changing)? This could have been done with SLAPS [1], IDGL [2], LDS [3], etc.\n\n- \\Delta A has been modelled as a full matrix of parameters making the approach not scalable to large graphs.\n\n- I was quite excited when I read theorem 2 but when I looked at the proof, I noticed that approximation between Eq. 17 and Eq. 19 is so coarse that I'm not sure if it even means much. While Eq. 17 requires that each node has a similar embedding across different views, Eq. 19 requires that the two embeddings for each pair of nodes within the same class have similar embeddings; the only connection between the two seems to that both embeddings of the same node should belong to the same class which is a very weak connection.\n\n- I found the example in 3.3 to be somewhat weak: while in theory one can modify the data so the model makes correct predictions for x_1 and x_2, in practice the modification is based on some predefined procedure (in the case of the current paper, the procedure being the optimization of Eq 6) so I would expect the data modifications will still result in the model making the same prediction for both nodes.\n\n- Some of the improvements in Table 1 are not statistically significant so the \"Rank\" column is misleading.\n\nQuestion:\n- It was not clear to me why the alternating optimizations are used. Why not optimize both losses at the same time?\n\n- How do you decide how many gradient descent steps to use at the test time?\n\n[1] SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networks\n[2] Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings\n[3] Learning Discrete Structures for Graph Neural Networks", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster