Temporal Generalization Estimation in Evolving Graphs
Authors: Bin Lu
Tingyan Ma
Xiaoying Gan
Xinbing Wang
Yunqiang Zhu
Chenghu Zhou
Shiyu Liang
Venue: ICLR 2024 poster (2024)
Keywords: Generalization Estimation
Evolving Graph
Graph Neural Network
Primary area: learning on graphs and other geometries & topologies

Abstract: Graph Neural Networks (GNNs) are widely deployed in vast fields, but they often struggle to maintain accurate representations as graphs evolve. We theoretically establish a lower bound, proving that under mild conditions, representation distortion inevitably occurs over time. To estimate the temporal distortion without human annotation after deployment, one naive approach is to pre-train a recurrent model (e.g., RNN) before deployment and use this model afterwards, but the estimation is far from satisfactory. In this paper, we analyze the representation distortion from an information theory perspective, and attribute it primarily to inaccurate feature extraction during evolution. Consequently, we introduce Smart, a straightforward and effective baseline enhanced by an adaptive feature extractor through self-supervised graph reconstruction. In synthetic random graphs, we further refine the former lower bound to show the inevitable distortion over time and empirically observe that Smart achieves good estimation performance. Moreover, we observe that Smart consistently shows outstanding generalization estimation on four real-world evolving graphs. The ablation studies underscore the necessity of graph reconstruction. For example, on OGB-arXiv dataset, the estimation metric MAPE deteriorates from 2.19% to 8.00% without reconstruction.

Published as a conference paper at ICLR 2024
TEMPORAL GENERALIZATION ESTIMATION IN EVOLVING GRAPHS
Bin Lu', Tingyan Ma', Xiaoying Gan', Xinbing Wang'
Yunqiang Zhu", Chenghu Zhou², Shiyu Liang
"Department of Electronic Engineering, Shanghai Jiao Tong University
Insttitute of Geographic Sciences and Natural Resources Research, Chinese Academy of Sciences 3 John Hoperoft Center for Computer Science, Shanghai Jiao Tong University frobinlu1209, xiackeaiyan, ganxiaoying, xwang 0 s jtu. edu, en (zhuyg, zhouchJe (iichhe@gssrre.. wwwiiisgrrrrc.oo acc. cn,
edu. cn
ABSTRACT
Graph Neural Networks (GNNs) widely deployed in vast fields, but they often struggle to maintain accurate representations as graphs evolve. We theoretically establish a lower bound, proving that under mild conditions, representation dis- tortion inevitably occurs over time. To estimate the temporal distortion without human annotation after deployment, one naive approach to pre-train recur- rent model (e.g.. RNN) before deployment and use this model afterwards, but the estimation far from satisfactory. this paper, we analyze the representation distortion from an information theory perspective, and attribute it primarily to in- accurate feature extraction during evolution. Consequently, we introduce SMART, straightforward and effective baseline enhanced by an adaptive feature extractor through sepe-suue graph reconstruction. In synthetic random graphs, we fur- ther refine the former lower bound to show the inevitable distortion over time and empirically observe that SMART achieves good estimation performance. More- over, observe that SMART consistently shows outstanding generalization esti- mation on four real-world evolving graphs. The ablation studies underscore the necessity of graph reconstruction. For example, on OGB-arXiv dataset, the esti- mation metric MAPE deteriorates from 2. 19% to 8.00% without reconstruction.
INTRODUCTION
The rapid rising of Graph Neural Networks (GNN) leads to widely deployment various applica- tions, e.g. social network, smart cities, drug discovery (Yang & Han 2023 Lu et al. 2022 Xu al., 2023). However, recent studies have uncovered a notable challenge: as the distribution of the graph shifts continuously after deployment, GNNs may suffer from the representation distortion
time, which further leads to continuing performance degradation (Liang et al.) 2018 Wu et al. 2022 Lu al. 2023), as shown in Figure T This distribution shift may come from the continuous addition of nodes and edges, changes in network structure or the introduction of new features. This issue becomes particularly salient in applications where the graph evolves rapidly over time.
60000
Consequently, a practical and urgent need is to monitor the representation distortion of GNN. An obvious method to regularly label and test online data. However, constant human annotation difficult to withstand the rapidly ever-growing evolution of graph after deployment. Therefore, how to proac- tively estimate the temporal generalization performance with- out annotation after deployment a challenging problem.
0.35
Accuracy
#/oodo
50000
0.30
40000
30000
20000
10000
0.20
1985 1995
To solve this problem, naive way is to collect the generaliza- tion changes through cartially-observed labels before deploy- ment, and train a recurrent neural network (RNN) (Mikolov et al.] 2010) in supervised manner. However, existing stud-
Year
Figure 1: GNN performance tinues to decline with the rapid growth over 30 years.
"Correspondence Shiyu Liang (Isy (Isy 1w60088881110iinnnddnl...o

---

Published as a conference paper at ICLR 2024
ies (Li et al. 2018 Pareja al. 2020) have shown that RNN itself have insufficient representa- tion power, thereby usually concatenating a well-designed feature extractor. Unluckily. the rep- resentation distortion of static feature extractor still suffers during evolution. Other methods con- sider measuring the distribution distance between training and testing data through average con- fidence (Guillory et al., (02T). representation distance Deng & Zheng (202T) and conformal test martingales (Voyk et al. 2021). However, these methods do not directly estimate generalization performance. Meanwhile, graph evolution can be very fast and the evolving graphs are usually very different from their initial states. Hence, to deal with this problem, we propose SMART (Self- supervised teMporAl geneRalization esTimation). Since it is hard to gather label information in a rapid graph evolution after deployment, our SMART resorts to adaptive feature extractor through self-supervised graph feature and structure reconstruction, eliminating the information gap due to the evolving distribution drift.
We summarize the main contributions as follows:
We theoretically prove the representation distortion is unavoidable during evolution. We con- sider a single-layer GCN with Leaky ReLU activation function and establish a lower bound of distortion, which indicates it strictly increasing under mild conditions. (see Section 2.3
We propose straightforward and effective baseline SMART for this underexplored problem, which is enhanced with self-supervised graph reconstruction to minimize the information loss in estimating the generalization performance in evolving graphs. (see Section 3)
Under a synthetic Barabási-Alhert random graph setting, we refine the lower bound to derive a closed-form generalization eπror of GNN on whole graph after deployment, and our SMART achieves satisfied prediction performance. (see Section 4)
We conduct extensive experiments on four real-world evolving graphs and our SMART consis- tently shows outstanding performance on different backhones and time spans. The ablation stud- ies indicate the augmented graph reconstruction is of vital importance, e.g., our method reduces the MAPE from 8.00% to 2. 19% on OGB-arXiv citation graphs. (see Section 5
PRELIMINARY
2.1 NOTATIONS
Graph. Let X E guxd denote the feature matrix where each row z; E Idd of the matrix X denotes the feature vector of the node i in the graph. Let E Rn denote the label matrix where each element y/ E R of the matrix Y denotes the label of the node i. Let A E {0, 10.1) denote the adjacency matrix where the element aiy = 1 denotes the existence of an edge between node and j. while a,j = 0 denotes the absence of an edge. Let À = A + I denote the self-looped adjacency Diag(d1, ...., d,) denotes the self-looped degree matrix, where d, Σドボ Aiy denotes the degree of node i. Let I. D-1 Á denote standard normalized self-looped adjacency matrix (Perozzi et al. 2014).
matrix, while the diagonal matrix D
Graph Evolution Process. We use G, (A₁, Y,) to denote the graph at time l. We consider an ever-growing evolution process g (G, t N). where N denotes set of all natural numbers. We use n4 to denote the number of nodes in the graph G.. We use the conditional probability P (o,19o .... Gr-1) ) to denote the underlying transition probability of the graph state G. at time t conditioned on the history state Gu...., G--1-
2.2 PROBLEM FORMULATION
As shown in Figure 2 before the deployment time faeploy, we are given with pre-trained graph neural network G that outputs label for each node in the graph, based on the graph adjacency matrix A E {0, 1] xne and feature matrix X₃ E R at each time kt Additionally, we are given an observation set D {(AN, XR, H (t km consisting of (1) series of fully observed graph adjacency matrices Ao...., Ar and node feature matrices Xo. ".,.. (2) a series of par- tially observed label vectors HoYo, H,,Y,, where each observation matrix H₃ {0, 1) 1 x is diagonal. Specifically, the diagonal element on the i-th row in matrix H₃ is non the label of the node is observed.
non-zero zero and only
2

---

Published as a conference paper at ICLR 2024
At each time after deployment at time Edeploys we aim to predict the expected temporal generaliza- tion performance of the model G on the state 9- (A,, Y+), i.c., predicting the generalization error E (+,) Y.) A,, X²]. given full observation on the ad- jacency matrix A, and feature ma- trix X,, Obviously, the problem
Before Deployment
Edegtoy
After Deployment
time
Structure 7
Feature
Lobel
Structure
Feature
Lobei
Figure 2: Illustration for generalization estimation.
not hard if we have a sufficient amount of labeled samples drawn from the distribution x) However, it is costly to obtain the human annotation on the constant portion of the whole graph after deployment, especially many real-world graphs grow exponentially fast. Therefore, the problem arises if try to design post-deployment testing performance pre- dictor M without further human annotations after deployment. More precisely, we try to ensure that the accumulated performance prediction error is small within period of length T ddeploy after deployment time /deplay, where the accumulated performance prediction error is defined as
P 1,,-...,,, A,,
E(M;G) & EARY
Σ 1-
((G(A,)))((((A,,)))))
(1)
where the random matrix sequence A (Aram ..., Ar), sequence X (X Capon +1 +1, m.y XT) and sequence (Veginy .... Yr) contain all adjacency matrices, all feature matrices and all label vectors from time Edpploy + to T separately.
2.3 UNAVOIDABLE REPRESENTATION DISTORTION AS GRAPH EVOLVES
One may ask, then, what impact the pre-trained graph neural network may have the node rep- resentation over time? In this subsection, we show that as the graph evolves, the distortion of representation unavoidable, which might further lead potential performance damage.
First, as shown in Figure 3 we plot the performance variation on the OGB-arXiv dataset (Hu et al. 2020a) with 30 different GNN checkpoints. We observe that GNN prediction perfor- mance continues to deteriorate over time. Additionally, we prove that the representation distortion strictly increasing with probability one. Before presenting the results, we first present the following several assumptions.
3.50
Prediction Loss
3.25
3.00
Assumption 1 (Graph Evolution Process). The initial graph Go = (Ag, Xo. Yo) has n nodes. (I) We assume that the feature matrix X, drawn from a continuous probability distribution supported on Rxx (2) At each time t in the process, new node indexed by
2.75
2,50
Timestep
appears in the graph. We assume that this node connects with each node in the existing graph with positive probability and that edges the graph not vanish in the process. (3) We assume that the feature vector In+t has a zero mean conditioned on all previous graph states, i.e., E[r,++ 19, .. Oa for all f 1.
Figure 3: Test loss changes time of 30 pre-trained GNN check- points on OGB-arXiv dataset.
Remark 1. Assumption states the following: (1) For any given subspace in the continuous prob- ability distribution, the probability that X, appears is zero. (2) The wver-growing graph assump- tion common in both random graph analysis, like the Barahási-Albert graph (Albert & Barabási] 2002), and real-world scenarios. For example, in citation network, paper may have a citation relationships with other papers in the network, and this relationships will not disappear over time. Similarly, the purchasing relationships between users and products in e-commerce trading networks are the same. (3) The pero-mean assumption always holds, as it is convention in deep learning to normalize the features.
In this subsection, we consider the pre-trained graph model as Lingle-laeer GCN with Leaky ReLU activation function parameterized 0. The optimal parameters for the model are 0" However, due
3

---

Published as a conference paper at ICLR 2024
to the stochastic gradient descent in optimization and quantization of models, we always obtain sub-optimal parameter drawn from a uniform distribution U ( E). .Pr We define the expected distor- tion of the model output node at time t as the expected difference between the model output at time and time zero on the node i, i.e., (i) = Be.g. (i: - fo(2; 0)1
Theorem 1. O is the vectorization of the parameter set {[a 5 b,)35-1 and its i-th coordinate is drawn from the uniform distribution ( E) centering the i-th coordinate of the vector 0; the expected deviation & (i) of the perturbed GCN model at the time 2 on the node E [1...., lower bounded by
g4
1
( (1)
E
Σ IKk
9
(1)
do(i)
kENO(()
where the set (i) denotes the neighborhood set of the node time O, B is is the slope ratio for negative values in Leaky ReLU. Additionally, Φr (i) is strictly increasing with respect to T 2 1.
Remark 2. Proofs of Theorem T can be found in Appendix B This theorem shows that for any node the expected distortion of the model output is strictly increasing time, especially when the width N of the model is quite large in the current era of large models. Note that the continuous probability distribution and the ever-growing assumption in Assumption [ are necessary. Otherwise,
Σ (kEN(()) 2k might be zero for some choice of Xo. which would lead to the lower bound being zero for all and further indicate that the lower bound is not strictly increasing.
METHODOLOGG
3.1 A NAIVE WAY OF ESTIMATING GENERALIZATION LOss
Before deployment, we are given an observation set D {(Ak: XR, H&Y))) Happley Now, we want to construct temporal generalization loss estimator that takes the adjacency matrices and feature matrices as its input and predicts the difference between the outputs the graph neural network G and the observed true labels at time k, i.e., la (HRG((AR. Xx), Hx).).
order to capture the temporal variation, we adopt a recurrent neural network-based model M(=:RRNM estimate generalization loss in the future. The RNN model sequentially takes the output of the GNN G(A,, Xx) as its input and outputs the estimation l time k. To enhance the representation power of RNN, we usually add non-linear feature extractor yp to capture the principal features in the inputs and the RNN model becomes
Ex h4
Me G(Ar, bw),k-1)) Mr (p G(Ac, Xx), ).
where h2 denotes the hidden state in the RNN, transferring the historical information. During train- ing, we are trying to find the optimal model M 4* such that the following empirical risk mini- mization problem is solved,
(M", = arg miim
M.5
After deployment time teeplay a naive and straightforward way of using the generalization loss es- timator is directly applying the model on the graph sequence (g- > teeeloa).. ). This results in population loss prediction error E, at time given by
(,M, EJMM (v² G(As Xx), hx-1) Xx),
Before deployment, however, we are not able to get sufficient training frames. This indicates & may only have good feature extraction performance graphs similar the first several graphs. After deployment, the graphs undergo significant changes, and thereby have unavoidable representation distortion, which makes the generalization estimator perform worse and worse
4

---

Published as a conference paper at ICLR 2024
3.2 INFORMATION LOSS BY REPRESENTATION DISTORTIONS
To further investigate this problem, let us consider the information loss within the input graph series and the output prediction after the GNN is deployed.
Information Loss r([(Ar, X+) X D;(x) 1 T(lx; bx),
where IU; V) is the mutual information of two random variables U and V. The learning process is equivalent to minimizing the above information loss. Furthermore, it can be divided into parts:
Information Loss = I(tt X
D; )- I(fx: Ex)
@ Information Loss Induced by RNN
(2)
+ +I(GG(A,, x+)1 Aaddo 4; - I(( G X,) Raspls +1 D; (.).
Information Loss Induced by Representation Distortion
Information Loss Induced by RNN. The first part induced by the insufficient representation power of the RNN. Specifically, & function of the current state and the hidden state vector hx-1- Here, there exists information loss if h cannot fully capture all the historical information. However, this is usually inevitable due to the insufficient representation power of the RNN, limited RNN hidden dimension, and inadequate training data.
Information Loss Induced by Reprentation Distortion. The second part indicates the informa- tion loss by the representation distortion of y. Especially as the graph continues to evolve over time, the information loss correspondingly increases due to the distribution shift. According to the data-processing inequality (Beaudry & Renner] 2012) in information theory, post-processing cannot increase information. Therefore, the second part of Equation 2 hoold for any time 7,
T((G(Ar, X+)) D; ()) T(lpp G(A,, X+) (
+1 +1, D; (4) 0.
The equality holds if and only if G(A,.X,) is a one-to-one mapping with G(A,, Xy). To minimize the information loss and achieve equality, we have choose a bijective mapping y. which further indicates min Σ, (A,, - Φ yp G(A-, X+) O. Therefore, to minimize the information loss, equivalent to solve the graph representation reconstruction problem. In the next subsection, we propose reconstruction algorithm to update feature extractor and adapt to the significant graph distribution shift after deployment.
3.3 SMART: SELF-SUPERVISED TEMPORAL GENERALIZATION ESTIMATION
In this section, we present our method, SMART, for generalization estimation in evolving graph as shown in Figure 4 After deployment, since there augmented graph reconstruction to obtain self-supervised signals to finetune the adaptive feature extractor & at post-deployment time, thereby reducing the information loss during the dynamic graph evolution. Compared with directly graph reconstruction, our method generates more views through data augmentation, which can learn more principal and robust representations.
human-annotated label, we design the
Post-deployment Graph Reconstruction. Given the pre-trained graph model G and evolving graph (A,, X&) at time k. we first obtain the feature embedding matrix O₃ G(A,, X&). order to capture the evolution property of graphs, we define two reconstruction loss on augmented feature graph, which denoted as (T(Ax), O+), where T(.) the structure transformation function, i.e.
randomly add or drop edges (You et al. 2020 Rong et al. 2020 Liu et al. 2023).
Structure Reconstruction Loss C.. First of all, we detine the structure reconstruction loss C.. Given the augmented feature graph (T(As), Oz), we perform reconstruction on adja- cency matrix Ag. Specifically, it computes the reconstructed adjacency matrix Åg by Å o FF)) F3. = (T(s,,,, Ok), where F, E N a the sigmoid activation function. Here we utilize one-layer graph attention network (GAT) model &o (Velickovic et al. 2018). and it is optimized by binary cross entropy loss between Aş and Åg as link prediction task, i.c.
C, LBCE(As, As).
5

---

Published as a conference paper at ICLR 2024
Siructure Reconstuction
g
Ap-1
1
A!
g
GNV
Fenture Extractor 94,
RNN M
4
hr
Feuture
g
Reconstruction
SMART: Sclf-supervised TeMporAl geneRalization es cimmatiion
Figure 4: Overview of our proposed SMART for generalization estimation in evolving graph.
Feature Reconstruction Loss Ly. Moreover, perform the node-level feature reconstruction on the corrupted adjacency matrix T(As). We utilize a single-layer decoder to obtain the reconstructed feature O₂ by Ó₂ Fga" FR (T(()),, where IR Bx and it is optimized by mean squared error loss Ly 110 - 0x11².
To sum up, the reconstruction loss Lg is the composition of structure reconstruction loss C, and feature reconstruction loss L as
(g(p)= + + X)C,,
(3)
where À is the proportional weight ratio to balance two loss functions.
Pre-deployment Graph Reconstruction. We note here that, before deployment, combine the same graph reconstruction with the supervised learning to improve the performance of feature extraction. Algorithm in Appendix [ outlines the pre-deployment warm-up training and post- deployment finetuning process of SMART in detail.
4 A CLOSER LOOK AT BARABÁSI-ALBER' RANDOM GRAPH
To theoretically verify the effectiveness of SMART, we first consider the synthetic random graphs, ie., Barabási-Alhert (BA) graph model, (Gt I N) (Barabási 2009). Please refer to Appendix B for the details.
Assumption 2 (Preferential Attachment Evolving Graphs). Here we consider a node regression task. The initial graph Go has No nodes. (1) We assume the node feature matrix X₃, is Gaussian random variable with (0, LB), where Lg E B, (2) The node label of each node is generated by Xi Xim. 2 O, which is satisfied like node degree, closeness centrality coefficients, etc. (3) A single-layer GCN f(g)= LXW given as the pre-trained graph model G.
Theorem 2. If at each time-slot the Barabási-Alberi random graph is grown by attaching one new node with m edges that are preferentially attached to existing nodes with high degree. To quantify the performance of GNN, the mean graph-level generalization relative error under the stationary degree distribution Q is determined by
Eg 2m
No + (C2 20-4 2CIEd a-44 EEQd
where d the degree of nodes.
= (Egda-1)) (B)d==))/(BEodd and d; is the degree of node U;.
Remark 3. Proofs of Theorem Can be found in the Appendix([] This theorem shows that when the node scale No of initial graph Go quite large, the graph-level error loss is approximately linearly related to time and continues to deteriorate.
To verify the above propositions, we generate a Barabási-Allert (BA) scale-free model with the fol- lowing setting: the initial scale of the graph is No 1000, and the evolution period is 180 timesteps. At each timestep, one vertex is added with m 5 edges. The label of each node is the closeness centrality coefficients. The historical training time period is only 9. As we derived in Theorem 2 the actual graph-level generalization error approximates a linear growth pattern. Therefore, we consider to compare SMART with linear regression model to estimate the generalization performance.
Does Linear Regression Model Work? We conduct experiments with random seeds and present the empirical results in Figure (1) Generalization error exhibits linear growth, consistent with

---

Published as a conference paper at ICLR 2024
Table 1:
Performance comparison on different Barabási-Albert graph setting. We use Mean Abso- lute Percentage Error (MAPE) + Standard Error to evaluate the estimation on different scenarios.
Barahávi-Alber (Ng = 1000)
Dual Barabási Albert (No = 1000, m, = 1)
5
10
m2
712 5
Trgg 10
Lincar 79.2431
74.1083
82.1677
61.8048
67.6442
38.4884
SMART
7.1817a1.2300
4.260220.3116
9.1173t0.1331
7.9038a1.808
3.8288:0.1766
1.994720.1682
Pre-tainaa Porforance
0.20
Pre-traine GNN Performanc
Oiservation
Prodiction (%)
Regresiion
0.4
Smart (Ours)
15
150
0.15
Smar (ibm)
wro Recorstracton
Finchminn
0.2
0.10
0.1
50
0.05
0.0
60
120
150
180
30
90
120
150
180
-0.02
0.00
0.02
Timestop
Timestep
Roduction of Reconstrction Loss AC.
Performance comparison with Linear Regression and SMART.
(b) Ablation study of removing
(c) Prediction improvement during the graph reconstruction.
graph reconstruction SMART.
Figure 5: Experimental results of SMART and its variation on BA random graph.
theorem (the blue solid line). (2) Our SMART method performs significantly well in long testing period, with mean prediction percentage error of 4.2602% and collapses into a roughly linear model. (3) However, the linear regression model, based on the first 9-step partial observations (the green solid line), exhibits extremely poor performance. Due to limited human annotation, partial observations cannot accurately represent the performance degradation of the entire graph. We also adjust parameters in the BA graph model and introduced dual BA graph model (Moshiri 2018) for further experiments (see T.. Our proposed SMART model effectively captures the evolutionary characteristics across various settings and significantly outperforms the linear regression model.
Effectiveness Graph Reconstruction. To further validate the effectiveness of graph reconstruc- tion in SMART, we conduct following two experiments. (1) As shown in Figure 5b] we remove the graph reconstruction module and repeat the experiment with 10 random seeds. Due to the tempo- ral distribution shift caused by the graph evolution, the generalization estimation shows significant deviations and instability. (2) We track the intermediate results during post-deployment fine-tuning, i.e. the reduction of reconstruction loss and prediction improvements. As depicted in Figure [cc] in the early stage of reconstruction (scatter points light color), the prediction performance opti- mization is fluctuating. As the optimization continues (scatter points in dark color), the prediction performance is effectively boosted and concentrated in the upper-right corner, with an average per- formance improvement of 10%.
EXPERIMENTS ON REAL-WORLD EVOLVING GRAPHS
5.1 EXPERIMENT SETTINGS
Datasets. We use two citation datasets, a co-authorship network dataset and series of social network datasets for evaluation. The statstics and more details are provided in Appendix P OGB- arXiv (Hu et al. 2020a): A citation network between aixiv papers of 40 subject areas, and we divide the temporal evolution into 14 timesteps. DBLP (Galke et al.) 2021): A citation network focused on computer science. We divide the temporal evolution into timesteps, and the task is to predict 6 venues. Pharmabio (Galke et al. 2021) A co-authorship graph, which records paper that share common authors. We divide the graph into 30 timesteps, and predict 7 different journal categories. Facebook 100 (Lim al., 20211: A social network from Facebook of 5 different university: Penn, Amherst, Reed, Johns Hopkins and Cornell. The task is to predict the reported gender.
Evaluation Metrics. To evaluate the performance, we adopt following metrics. (1) Mean Ab- solute Percentage Error (MAPE) quantifies the average relative difference between the predicted
7

---

Published as a conference paper at ICLR 2024
generalization loss and the actual observed generalization loss, which is calculated as MAPE
100%. (2) Standard Error (SE) measures the variability of sample mean and estimates how much the sample mean likely to deviate from the true population mean, which is calculated as SE //,n,, where a is the standard deviation, is the number of samples. In addition, we conduct the performance comparison on Root Mean Squared Error (RMSE) and Mean Absolute Error (MAE), please refer to Appendix G.I
Tapppy Fdeploy
Experiment Configurations. We adopt the vanilla graph convolution network as the pre-trained graph model G, which is trained the initial timestep of the graph with 10% labeling. During training. we only select the next 3 historical timesteps, where we randomly label 10% of the newly- arrived nodes. The remaining timesteps reserved for testing, where we have no observations of the label. We run SMART and baselines 20 times with different random seeds.
5.2 EXPERIMENTAL RESULTS
Comparison with Baselines. Table 2 we report the performance comparison with two exist- ing baselines, linear regression and DoC (Guillory et al., 202T). Moreover, compare SMART with a supervised baseline, which requires new node labels and retrain the model on the new data after deployment. We observed that SMART consistently outperforms the other two self-supervised methods (linear regression and DoC) on different evaluation metrics, demonstrating the superior temporal generalization estimation of our methods. On OGB-arXiv dataset, our SMART achieves comparable performance with Supervised.
Table 2: Performance comparison on three academic network datasets and four GNN backbones. We use MAPE + Standard Error to evaluate the estimation on different scenarios. The complete experimental results can be found in Appendix G.3
ariv (1)
DBLP (L)
Pharmahin (L)
Backhone
Linear
DoC
Supervised
SMART
Linear
SMART
Linear
SMART
GCN
10.5224
9,5277+1 4887
2. 4.1354.0450
2.1897-0,221
16.4991
3.4992.0.150
32.3653
4.3405
GAT
12.3652
12.2138s1
3.1481
17.6388
6.6459e1.301
29.0404
1.2197
GraphSage
19,5480
L0.589
1.691 850455
5.2733:2.2635
23.7363
9.965
31.7033
3.1444800677
TransConv
14.9552
10.09994a.197
2.0473
3.5275e1.142
18.2188
6.421241.908
31.8249
2.7357
Estimation on Different Test Time Period. Table 3 we demonstrate the performance of SMART over time during the evolution of graphs in five social network datasets from Facebook 100. As the evolving pattern gradually deviates from the pre-trained model on the initial graph, generalization estimation becomes more challenging. Consequently, the error in linear estimation increases. However, our SMART method maintains overall stable prediction performance.
Table 3: Performance comparison on five social network datasets Facebook 100. We divide the test time Tisa into 3 periods and evaluate the estimation performance separately.
[0, Ties/ /3]
(Trea/ /,, 2Tiea/ 33]
(2Tiea/33 3,, Twsal
Facebook 100
Linear
SMART
Linear
SMART
Linear
SMART
Penn
1.9428
0.0193+0.0041
2.0432
0.612720.030
2.7219
2.2745
Amherst
31.1095
1 1.4489+0.2455 2450
49.2363
38280+0.9527
73.5709
4.3320 8799
Reed
55.6071
0.0453
65.7536
0.0987+0.0078
73.6452
0.0318+0.0085
Johns Hopkins
8.1043
0.589320.0491
10.2035
0.860720.166
11.5206
0.906 20.2795
Cornell 4.5655
0.4663+0.0275
8.6622
1.046720.8817
12.3263
1.731 20.1175
5.3 ABLATION STUDY
To verify the effectiveness of different modules in SMART, conducted ablation studies four datasets with the following variants: (M1) w/o augmented graph reconstruction: Removing graph reconstruction, using RNN only for estimation. (M2) w/o RNN: Replacing RNN with an MLP for processing current step input. (M3) w/ structure or feature reconstruction: Removing either structure or feature reconstruction, using the complementary method in post-deployment fine-tuning.
8

---

Published as a conference paper at ICLR 2024
MI w/o augmented graph reconstruction
M3a w/o structure reconstruction
Smart (Ours)
M2 : w/o RNN
M3b w/o feature reconstruction
OGB-arXiv
DBLP
Pharmabio
Comell
MAPE (%)
M2 M3aM3hOurs
M2 M3aMrbuurs
MI M2 M3aM3hOurs
MI M2 M3aMibOurs
Figure 6: Ablation study on four representative evolving datasets.
arivarXiv
(b) DRLP
(c) PharmaRio
(d) Corell
MAPE (5)
1.5
1.5
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
Loss
Loss
Loss ratio
Loss casio
OGB
(I) DBLP
(g) PharmaBio
Cornell
MAPE (6)
4
2,5
16
32 64
128
16
32
64
128
4
16
32
64
128
4
16
32
64
128
RNN Dimension
RNN Dimession
RNN Dimession
RNN Dimersion
Figure 7: Hyperparamter study on proportional weight ratio À and RNN input dimension.
As seen in Figure 6 make the following observations: (1) Comparing (MI) with our method, augmented graph reconstruction significantly impacts accurate generalization estimation, particu- larly evident in the OGB-arXiv and Pharmabio datasets, where the (M1) variant exhibits substantial performance gap. (2) In the case of (M2), generalization estimation based on historical multi-step information improves prediction accuracy and stability. For instance, in the Cornell dataset, pre- dictions using single-step information result in larger standard error. (3) As shown by (M3a) and (M3b), removing either of the reconstruction losses leads to performance decrease in SMART. Since evolving graphs display temporal drift in both structure and features, both graph augmented reconstruction losses are essential for mitigating information loss over time.
5.4 HYPERPARAMETER SENSITIVITY
Proportional Ratio of Two Reconstruction Loss. We evaluate performance using different weight ratios À E {0, 1, 0.3, 0.5, 0.7, 0.93. as shown in Figure (d)- Our method is generally insensitive to the choice of X, with X = 0.5 being a balanced option in most cases. However, larger A values can yield better results in specific datasets, such DBLP and PharmaBio, especially when the node features are simple, like one-hot encoding or TF-IDF representations. Feature Dimen- sion of RNN Input. We compared RNN feature dimensions ranging from {4, 8, 16, 32, 64, 128), as shown in Figure -h) Performance remains stable across four datasets when the feature dimen- sion is set between 4 and 64. However, a significant performance drop occurs on the Cornell dataset when the dimension is set to 128. Setting the RNN feature dimension too high is discouraged for two reasons: (1) As shown in Equation 2 RNN input represents compressed node information over time. To enhance historical information density and effectiveness, the input dimension should be re- duced, facilitated by the reconstruction loss. (2) Given limited observation samples during training, reducing the RNN input dimension helps alleviate training pressure.
CONCLUSIONS
In this paper, we investigate a practical but underexplored problem of temporal generalization es- timation in evolving graph. To this end, we theoretically show that the representation distortion is unavoidable and further propose a straightforward and effective baseline SMART. Both synthetic and real-world experiments demonstrate the effectiveness of our methods. Future work involves exploring our methods in more complicated scenarios such as evolving graph with changing label, heterogeneous graphs and spatio-temporal graphs.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
This work was partially supported by National Key R&D Program of China (No.2022YPB33944200.
NSF China (No. 62306179, 62272301, 62272301,20501005 42050105, 62020106005, 146002, 61 61960206002), and the Deep-time Digital Earth (DDE) Science Program. Shiyu Liang is also supported by National Natural Science Fund for Excellent Young Scientists Fund Program (Overseas) "Optimizing and Analyzing Deep Residual Networks".
REFERENCES
Réka Albert and Albert-Lászld Barabási. Statistical mechanics of complex networks. Reviews of modern physics, (441):47, 2002.
Albert-Lászíó Barabási. Scale-free networks: decade and beyond. Science, 325(5939):412-413, 2009.
Normand J. Beaudry and Renato Renner. An intuitive proof of the data processing inequality. 12 (5-6):4324441 may 2012. ISSN 1533-7146.
Weijian Deng and Liang Zheng. Are labels always necessary for classifier accuracy evaluation? In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, virtual, June 19-25, 2021, pp. 15069-15078. Computer Vision Foundation IEEE, 2021.
Weijian Deng, Stephen Gould, and Liang Zheng. What does rotation prediction tell us about clas- sifier accuracy under varying testing environments? In Proceedings of the 38th International Conference on Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 2579-2589 PMLR, 2021.
Weijian Deng. Stephen Gould, and Liang Zheng. On the strong correlation between model invari- ance and generalization. In NeurIPS, 2022.
Lukas Galke, Benedikt Franke, Tobias Zielke, and Ansgar Scherp. Lifelong learning of graph neural networks for open-world node classification. In 2021 International Joint Conference on Neural Networks (IJCN), pp. 1-8. IEEE, 2021.
Alex Graves and Jürgen Schmidhuber. Framewise phoneme classification with bidirectional Istm and other neural network architectures. Neural networks, 18(5-6):602-61,, 2005.
Devin Guillory, Vaishaal Shankar, Sayna Ebrahimi, Trevor Darrell, and Ludwig Schmidt. Predicting with confidence on unseen distributions. In 2021 IEEE/CVF International Conference Com- puter Vision, ICCV 2021, Montreal, QC. Canada, October 10-17, 2021, pp. 1114-1124. IEEE, 2021.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 1024- 1034, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs. In Ad- vances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020a.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In International Conference on Learning Representations, 2020b. URL https: http:::://peeewiiieee net fontt/formm?dd
HJ WRJSFDH
Neha Hulkund, Nicoló Fusi, Jennifer Wortman Vaughan, and David Alvarez-Melis. Interpretable distribution shift detection using optimal transport. ArXiv, abs/2208. 028896 2022.
10

---

Published as a conference paper at ICLR 2024
Thomas N. Kipf and Max Welling. Semi- Semi-supervised classification with graph convolutional net- works. In 5th International Conference on Learning Representations. ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Colin Lea, Michael D Flynn, Rene Vidal, Austin Reiter, and Gregory D Hager. Temporal convolu- tional networks for action segmentation and detection. In proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 156-165, 2017.
Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural net- work: Data-driven traffic forecasting. In 6th International Conference on Learning Representa- fions, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceed- ings, 2018.
Shiyu Liang, Yixuan Li, and R. Srikant. Enhancing the reliability of out-of-diisrribtiio image detection in neural networks. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - -May 3, 2018, Conference Track Proceedings, 2018.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser-Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 20887-20902, 2021.
Yixin Liu, Ming Jin, Shirui Pan, Chuan Zhou, Yu Zheng, Feng Xia, and Philip S. Yu. Graph self- supervised learning: A survey. IEEE Trans. Knowl. Duta Eng., 35(6):5879-5335 2023.
Yunkai Lou, Chaokun Wang. Tiankai Gu, Hao Feng, Jun Chen, and Jeffrey Xu Yu. Time-topology analysis on temporal graphs. VLDB J., 32(4):815 843, 2023.
Bin Lu. Xiaoying Gan, Weinan Zhang, Huaxiu Yao, Luoyi Fu, and Xinbing Wang. Spatio- teaiootaemprall graph few-shot learning with cross-city knowledge transfer. In KDD '22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 14 18, 2022, pp. 1172-1172. ACM, 2022.
Bin Lu, Xiaoying Gan, Ze Zhao, Shiyu Liang, Luoyi Fu, Xinbing Wang, and Chenghu Zhou, Graph ouitt--distiibutiin generalization with controllable data augmentation. CoRR, abs/2308.08344 2023.
Yuanfu Lu, Xiao Wang, Chuan Shi, Philip S. Yu, and Yanfang Ye. Temporal network embedding with micro- and macro-dynamies. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management. CIKM 2019, Beijing, China, November 3-7, 2019, pp. 469-478. ACM, 2019.
Tomás Mikolov, Martin Karafiát, Lukás Burget, Jan Cernocký, and Sanjeev Khudanpur. Recurrent neural network based language model. In INTERSPEECH 2010, 11th Annual Conference of the International Speech Communication Association, Makuhari, Chiba, Japan, September 26-30, 2010, pp. 1045-1048. ISCA, 2010.
Niema Moshiri. The dual-barabásii-aleer model. arXiv preprint arXiv: 2018.
Pál András Papp, Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnn: Random dropouts increase the expressiveness of graph neural networks. An in Neural Information Processing Systems, NewrlPS 2021, December 6- 14, 2021, virtual, pp. 21997-22009, 2021.
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao B. Schardl, and Charles E. Leiserson. Evolvegen: Evolving graph convolutional networks for dynamic graphs. In The Thirty-Fourte AAAI Conference on Artificial Intelligence, AAAI 2020, The ThirlySecond Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pp. 5363-5370. AAAI Press, 2020.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: online learning of social representa- tions. In The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD) '44 New York, NY, USA- August 24 27, 2014, pp. 701-710. ACM, 2014.

---

Published as a conference paper at ICLR 2024
Stephan Rabanser, Stephan Günnemann, and Zachary C. Lipton. Failing loudly: An empirical study of methods for detecting dataset shift. In Advances in Neural Information Processing Systems 32: Annual Conference Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 1394-1406, 2019.
Yu Rong. Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In 8th International Conference on Learning Rep- resentations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. Dysat: Deep neural repre- sentation learning on dynamic graphs via self-attention networks. WSDM '20: The Thirteenth ACM International Conference on Web Search and Data Mining, Houston, TX, USA, February 3-7, 2020, pp. 519-527. ACM, 2020.
Min Shi, Yu Huang, Xingquan Zhu, Yufei Tang, Yuan Zhuang, and Jianxun Liu. GAEN: graph attention evolving networks. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event Montreal, Canada, 19-27 August 2021, pp- 1541-1547. orcai.org, 202
Yunsheng Shi, Zhengjie Huang. Shikun Feng, Hui Zhong, Wenjing Wang, and Yu Sun. Masked label prediction: Unified message passing model for semi-supervised classification. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreall Canada, 19-27 August 2021, pp.
ijcai.org, 2021b.
Rakshit Trivedi, Mchrdad Farajtabar, Prasenject Biswal, and Hongyuan Zha. Dyrep: Learning rep- resentations over dynamic graphs. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018.
Vladimir Vovk, Ivan Petej, Ilia Nouretdinov, Ernst Ahlberg, Lars Carlsson, and Alex Gammerman. Retrain not retrain: conformal test martingales for change-point detection. In Conformal and Probabilistic Prediction and Applications, 8-10 September 2021, Virtual Event, volume 152 of Proceedings of Machine Learning Research, pp. 191-210. PMLR, 2021.
Yanbang Wang, Yen-Yu Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
Zhihao Wen and Yuan Fang. Trend: Temporal event and node dynamics for graph representation learning. In Proceedings of the ACM Web Conference 2022, pp. 1159-1169, 2022.
Yingxin Wu, Xiang Wang, An Zhang, Xiangnan Hc, and Sat- Chua. Discovering invariant rationales for graph neural networks. In International Conference Learning Representations, 2022.
Minkai Xu, Alexander S. Powers, Ron O. Dror, Stefano Ermon, and Jure Leskovec. Geometric latent diffuusio models for 3d molecule generation. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honoludu, Hawaii, USA, volume 202 of Proceedings of Machine PMLR, 2023.
Learning Research, pp.
Carl Yang and Jiawei Han. Revisiting citation prediction with cluster-aware text-enhanced hetero- geneous graph neural networks. In 39th IEEE International Conference Data Engineering, ICDE 2023, Anaheim, CA, USA, April 3-7, 2023, pp. 682-695. IEEE, 2023.
Jiaxuan You, Tianyu Du, and Jure Leskovec. ROLAND: graph learning framework for dynamic graphs. In KDD 22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 14 18, 2022, pp. 2358-2366. ACM, 2022.
12

---

Published as a conference paper at ICLR 2024
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, Decem- ber 6-12, 2020, virtual, 2020.
Le-kui Zhou, Yang Yang, Xiang Ren, Fei Wu, and Yueting Zhuang. Dynamic network embedding by modeling triadic closure process. In Proceedings of the Thirty-Second AAAI Conference Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI- 18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pp. 571-578. AAAI Press, 2018.
Dingyuan Zhu, Peng Cui, Ziwei Zhang, Jian Pei, and Wenwu Zhu. High-order proximity preserved embedding for dynamic networks. IEEE Trans. Knowl. Data Eng., 30( 30:11)211442114 2018.
A ALGORITHM
We illustrate the details of our proposed SMART in Algorithm [ The learning process of SMART divided into two stage: pre-deployment warmup training and post-deployment finetuning. Before the deployment, conduct both the supervised learning the generalization loss prediction with the partially-observe labels and self-supervised learning on the evolving graph structure. After the deployment, since
longer have the label information over time, we design two augmented graph reconstruction task as a self-supervised manner to actively finetuning the feature extractor yp
Algorithm SMART: Self-supervised Temporal Generalization Estimation
Input: Pre-trained graph model G, observation data D, evolving graph (As, X²) at time k.
Output: Update generalization performance predictor .M and &p with paramter A = [|MM.0*]. while not converged or maximum epochs not reached do Pree-deployment Warmup Training
2: Compute loss [(0) = La M[ G(A,, X,). hy-1) - (H,, H,Y,,,, 1P:
3: Compute graph self-supervised Cg via Equation 3
4: Update - + Vo Ly);
5:
end while
6: for k k= Ideploy + ,,...,,7 do
b Post-deployment Finetuning
7:
Get the newly-arrival graph (As, Xx):
8: while not converged or maximum epochs not reached do
9:
Compute graph self- self-supervised Lg via Equation 3
10: Update of + o% + V Bg Cgi
11: end while
end for
B PROOF FOR THEOREM
Proof. Let (i; denote the output of the GCN on the node time 5 2 Therefore, we have
N
(+
Σ ajo
Σ
x W, + bi
(4)
(i)
1=1
KEN-
Thus, the expected loss of the parameter 6* on the node at time т is
(i)
E
(fr (i:
fo(i: 0))
1)
E
aj
(i)
1
Σ
x W;
+b;
do(i)
Σ
T[W, + by
kEM.(
kENo(1
13

---

Published as a conference paper at ICLR 2024
Furthermore, recall that each parameter aj U(a3.5) {) and each element j.c. in the weight vector W3 also satisfies W,e U(W,,E). Therefore, the differences a, aj and Wg,s W are all i..d. random variables drawn from distribution E). Therefore, we have
2 W + b1) 1)
(1) =
Σ
Jj
0
di)
Σ (EN
Ik W
W +,, +b₃
-0
do(
Σ kENo(1)
j=1
))
E
Σ
aaj 05)
1
Σ
Fy W, + +b3
Σ
Fx W + by)
dr (i)
do(i)
kEN-(()
kENa(()
Σ
T I W W bj
Σ
T W +
IK
(i)
do(i)
(1)
kENo(1)
E
Σ
0g az)
0
Σ
I W + bj
Σ
x W W bb
(i)
do(()
(E),
keNol1)
N
+ E
Σ
1 Σ
W + bj -
Σ
2
2J W + by
d,
do(i)
kEN+(1)
kENo(()
The third equality holds by the fact that the differences (a, - aa)'s 's are all i.i.d. random variables drawn from the uniform distribution E). Therefore, we have
( (11100
)
((1) 2 E Σ agj ag)
Σ
x T + bj
W bb Σ
a (E)
(+)
do(()
keNo(1)
Furthermore, since the differences (a, - -az) are i.i.d. random variable drawn from the distribution UO, E), we must further have
a (11
N
(+(1) 2 E
Σ
(aj - a5))
(1211) di)
Σ
of W, + bbj - a do(i)
Σ
I W + by
1=1
KEN-(()
kENo(t)
27
Σ
[a, - A Xrl
1
Σ
It T W,, + +b;
Σ
T W3 + bj
dr(()
do(i)
KEN-(0
RENO(E)
2 E
Σ
zT + b,
1
Σ
x ITW, bb
σ
3
(1)
do(i) kENa(a)
kEN-(1)
14

---

Published as a conference paper at ICLR 2024
Furthermore, the leaky ReLU satisfies that [o((u) a(o)] 3 u v/. The above inequality further implies
27
N
(i)
2
3
E
0
(i)
Σ
o W +bg
do(i)
Σ
I& W
+
kEN,(i)
kENo(()
27
82
2
Σ
IR 5 + bj - do(i)
Σ
IR W bj
3
(1)
kEN-(1)
kE>oo(f)
g2
M
Σ
5 W +
1
Σ
on W
3
(i)
(i)
do(i)
(i)
keNool))
2
8252
R
Σ
W
+
1
Σ
Rg W
3
(i(1)
(1
do(i)
(EN-)))
kENo(()
g25²
E
Σ
W W
3
(i)
do(i)
kENo(()
Therefore, we have
32
N
(1)
E
Σ
Ig T W
d (i)
(i)
kENo(t)
B²52
E
Σ
I (W, - W + W3)
3
dr (1)
di)
kENo(1)
8252 E
Σ
Σ
x T[ - W3)
3
d+ (1)
do(i)
kENo(
32
+
E
Σ
Σ kENo()
2g WJ
(i)
do(t)
j=1
where the last equality comes from the fact that random vectors (W, Wj)'s 's are an i.i.d. ran- dom variables drawn from the uniform distribution U(0,E) {) and are also independent of the graph evolution process. Therefore, we have
(()) 2
Σ kENo(()
ot (W, Wj)
3
d, (i)
do(?)
2
1
Σ
Ik
d (1)
do(
(E
where the last equality comes from the fact that each element in the random vector (W, WF) is i..d. random variable drawn from the uniform distribution U(. Since the initial feature matrix Xa = (nn) are drawn from continuous distribution supported Rdd must have with
15

---

Published as a conference paper at ICLR 2024
probability one,
Σ 2k (E)
>>
Furthermore, we have
Eg, (al1) do(i)) ) 9o
1
2
Eg,
90
d, (i)
du (i)
1
1
Esr
Go
(o
dr
To prove (i) is strictly increasing, it suffices to prove that Eg, respect to r. Since
90
is decreasing with
d. (6)
1
1
Bg.
90
R.G
9o
d+
(i)
d+
(2)
I
90
dr
(1)
P
(1)
<
90
dr
P
d-
(1)
dr,
where the last inequality comes from the fact that
1
P
dr
< Go
<
P
1
dr
<
9n
C PROOF FOR THEOREM
Proof. Assuming a regression task with single-layer GCN, we compute mean squared error be- tween prediction and ground truth as the learning objective as follows
min |LXW 1 = min Ex ((LXW) LXW 2(LXW) + +| W
(5)
W
min Ex X" 2W X L-Y + |
(6)
Since D 2 is a diagonal matrix, (L) = matrix A. Each node feature is independently Gaussian distributed.
= a D- where a; is the i-th row in
When ドj.
Ex 1X =
When = j.
Ex LX Ex LL Lx:) = Ex
Tzg (L" Lmm
(8)
m=1
Similarly, when and only when j m. Ex [XT T LX 8s #
16

---

Published as a conference paper at ICLR 2024
Ex 1X la
Ex (c))) = -I.
(9)
where ( 1)3s = ンزー ((D A)" D A)ss = (A" = شزز 1 c5 B
Consequently, the learning objective is equal to
min Ex LXW 2 W W
min B W - -2 (x" + ||
(10)
Meanwhile, the optimal parameter of GCN equals to W =EX (X*
1
W
Bx
XX"L"Y):
(11)
B
1
Ex
(X" 1
Jm Ym
(12)
B
Ex
(LX)
)
m Xmn
(13)
B
m=
N
Ex
Toms X X d X
(14)
B
1=
Ex
Luman X mit X mn
(15)
B
Therefore, only if = k, W = 1 Σ
Lmm d
1 Em=L d C, and otherwise W? = 0.
m=1
3
For any given node 2; we have
B (LXW"); Yill
B(LXW (LXW"),, + |YI|
(16)
B|
To be specific,
N
(LXW"),- Σ
(LX)x& = =c> Σ Lis =
(17)
5=1
N V = Σ
Tii X sk 12 X Cddf Tiis = Cd
(18)
E(LXW*) B(C Σ Lis X sk == = Σ (Tis x C2 Σ
12 C²
(19)
d;
8=1
2 Edt" = Rr"
(20)
Therefore, plugging to Eq. 16
E(d) c2 2Cd 1 + cea
(21)
La
= C2d - +1
(22)
We denote the error of node as 6, Therefore, the overall enror of graph G under the stationary degree distribution Q is calculated Eg (g) Here assume the inherent graph model
17

---

Published as a conference paper at ICLR 2024
follows the equals to
model (Albert & Barabási 2002).
where the probability of node degree
P(d) = 2m
(23)
No +t d8
No is the initial scale of graphs, m is the newly-arrival number of nodes of each time Conse- quently, the error of graph 9 can be further deduced as:
Eg = Eo 22m²
t 1 No tt (C² d 2-22-11 -20 .oddds da-l + +1)
(24)
2m
EC' 20-4 -2CEed 20-4 B2d
(25)
No
D RELATED WORK
D.1 DISTRIBUTION SHIFT ESTIMATION
Deep learning models are sensitive the data distribution (Deng 2022). Especially when these models are deployed online, how to accurately estimate generalization error and make decisions advance crucial issue. Deng & Zheng (202T); Deng et al. (202I) estimate the recogniion performance by learning accuracy regression model with image distribution statistics. Raaaanser al. (2019) conduct an empirical study of dataset shift by two-sample tests on pre-trained classifier. Hulkund et al. (2022) use optimal transport to identify distribution shifts in classification tasks. Vovk et al. (2021) propose conformal test martingales to detect the change-poii point of retraining the model. However, all these methods are designed for images, while evolving graph shows significant different characteristics due to its ever-growing topology. To our best of knowledge, we are the first investigate the temporal generalization estimation in graphs.
D.2 EVOLVING GRAPH REPRESENTATION
Real world graphs show dynamic properties of both feature and topology continuously evolving over time. Existing research can be categorized into two types: (1) Temporal Graph Snapshots. Intuitively, the evolving graph can be splited into graph time series, thereby taking a recurrent model for temporal encoding (Shi et al. 2021a; Sankar et al. 2020). DHPE (Zhu et al. 2018) gets simple dynamic model base SVD, which only preserves the first-order proximity between nodes. Dynamic Triad (Zhou et al.) 2018) models the triadic closure process to capture dynamics and learns RNN to evolve the parameter of GCN while ROLAND (You et al.) 2022) recurrently updates hierarchical node embeddings. (2) Temporal Graph Events. Some other studies convert the graph representation by grouping the node and edges with time steps in a given period (Wang et al. 2021 Trivedi et al., 2019). TREND (Wen Fang
node embeddings at each time step. EvolveGCN (Pareja et al. 2020) proposes
2022) borrows the idea of Hawkes temporal point process in time series analysis, capturing both individual and collective temporal characteristies of dynamic link formation. MCDNE (Lu al. 2019) proposes novel temporal network embedding with micro- and macro-dynamics, where temporal attention point process is designed to capture structural and temporal properties a fine- ane-grrined level. Lou et al. (2023) propose to evaluate the cohesiveness of temporal graphs in both topology and time dimensions.
E EXPERIMENT DETAILS OF BARABÁSI- RANDOM GRAPH
Barabási-Albert (BA) random graph (Barabási 2009 Albert & Barabási, 2002), also known the preferential attachment model, is type random graph used to model complex networks, particu- larly those that exhibit scale-free properties. BA graphs often used to model various real-world networks, such as the World Wide Web, social networks, citation networks, etc.
BA random graph has two important concepts: growth and preferential attachment. Growth means that the number of nodes in the network increases over time. Preferential attachment means that the more connected node is, the more likely it is receive links. Start with initial graph Go
18

---

Published as a conference paper at ICLR 2024
BA (m =2) 2)
BA (m 55)
BA (m 10)
10
10"
Frequency
Frequency
Frequency
10
10
10
10
10"
10
10'
10'
10
10
Degree 10
Degree
Degree
Figure 8: Degree Distribution of BA graphs
that consists of a number of nodes and edges. At each time step т, a new node introduced into the graph, and it forms edges existing nodes in the graph. The probability that existing node receives an edge from the new node is proportional to the degree (number of edges) in the current graph -1 This means that nodes with higher degrees are more likely receive new edges, exhibiting preferential attachment.
Dual Barabási-Allert (Dual BA) random graph (Moshini 2018) is an extension of BA model that better capture properties of real networks of social contact. Dual BA model is parameterized by No inital number of nodes, probability my new edges are added, and with probability 1 p. m2 new edges are added. The new edges are added in the same manner as the BA model.
mi, m2, N, and probability S S 1. For each new vertex, with
In our experiment, we adopt above two different BA model as test datasets. We use wwwabbaialbbbrrggreeee.
and dual.barabasi.cd wtabbaaiiabbbrtgrapppp implementation pro- vided by NetworkX. The detailed experiment parameter settings (Table Table 5) and the degree distribution (Figure 8 Figure 9 are shown as follows.
Table 4: Parameter setting of BA graph in synthetic experiments.
Table 5: Parameter setting of Dual BA graph in synthetic experiments
Barabási-Albe model
Dual Barabási-Albert model
mi
m2
1000
2
1000
2
1000
5
1000
5
1000
10
1000
Here, we present the complete experiment results on 4 evaluation metrics (MAPE, RMSE, MAE and Standard Error) in T Since the DoC method only applies to classification problems using the average confidence, we thus do not compare it with our SMART on the synthetic setting.
F REAL-WORLD DATASETS
We use two citation datasets, a co-authorship network dataset and a series of social network datasets evaluate our model's performance. We utilize inductive learning, wherein nodes and edges that emerge during testing remain unobserved during the training phase. The detailed statistics are shown Table
Please refer to the implementation in httpers//eeuoook..ooooooooooeees reference/ wwwpre/ncegggnertteeeeeeeeeeeeee http://www...aaaaoooooooooooooor
9 graph html
Please refer to the implementation in httppp///eeooalccooooooooetetted
re reference/gue hawaan///ggeerrtee/eetttooo orrae random www.duaaaaababbaabaaaaaaa
generators.
bbbrt_graphhhor html
19

---

Published as a conference paper at ICLR 2024
DBA (m, 22)
DBA (m, 55)
DBA (m, - 10)
10
10
10
Frequency
Frequency
Frequency
10"
10
10"
10a
10"
10'
10'
10'
10"
10
Degree
Degree
Degree
Figure Degree Distribution of DBA graphs
Table 6: Performance comparison on different Barabási Albbert graph setting.
Barebási-Albert (BA)
Linear
SMART
Random Graph
MAPE
RMSE
MAR
MAPR
RMSE
MAE
m 2
79.2431
0.0792
0.0705
7.181 2550
0.0057+0000
0.0042+00016
BA
m = 5
74.1083
0.0407
0.0398
4.2602+0.5316
0.0039a0.0004
0.0035$0.004
(No 1000)
10
82.1677
0.1045
0.0925
9.1173+0.133
0.0077+0.0010
0,007 #0.0009
Dual BA
m2 =
61.8048
0.0676
0.0615
7,9038a1 8008
0. 0.0088.0.0022
0.006920.017
(No 1000, mI=1)
m2
67.6442
0.0827
0.0771
3.8288+0 1706
0.0049+0.0013
0,0040+0.000
172 10
38.4884
0.0298
0.0297
1.9947+0 1682
0.0026+00000
0.0023+0.00
OGB-arXiv (Hu et al. 2020a): The OGB-arXiv dataset is a citation network where each node represents an arXiv paper, and each edge signifies the citation relationship between these papers. Within this dataset, we conduct node classification tasks, encompassing a total of 40 distinct subject areas. Our experiment spans the years from 2007 to 2020. In its initial state in 2007, OGB-arXiv comprises 4,980 nodes and 6, 103 edges. As the graph evolves over time, the citation network boasts 169,343 nodes and 1,166,243 edges. We commence by pretraining graph neural networks on the graph in 2007. Subsequently, we employ data from the years 2008 to 2010 to train our generalization estimation model SMART. Following this training, we predict the generalization performance of the pretrained graph neural network on graphs spanning the years 2011 2020.
DBLP Galke et al. 2021): DBLP is also citation network and this dataset use the conferences and journals as classes. In our experiment, DBLP starts from 1999 2015 with classes. Throughout the evolution of DBLP, the number of nodes increase from 6,968 to 45,407, while the number of edges grow from 25,748 to 267,227. We pretrain the graph neural network on the graph in 1999 and train model on the next three years. We employ the graph spanning from 2004 to 2015 to assess the performance of our model.
Pharmabio (alke et al. 202T): : Pharmabio a co-authorship graph dataset, and each node rep- resents paper with normalized TF-IDF representations of the publication title as its feature. If two papers share common authors, an edge is established between the corresponding nodes. We conduct node classification tasks on this dataset, comprising a total of seven classes, with each class representing a journal category. The range of Pharmabio is 1985 to 2016. The pretrained graph neural network is based the graph of the year 1985 with 620 nodes and 57.559 edges. Then we train our estimation model by using graph data from 1986 to 1988. We evaluate our model consecutive 26 years starting form 1989. At the last year 2016, the graph has evolved to 2,820 nodes with 3,005,421 edges.
Facebook 100 (Lim et al. 2021): Facebook 100 a social network which models the friendship of users within five university. We perform binary node classification this dataset, with the classes representing the gender of the users. Among these datasets, Amherst, Reed and Johns Hopkins are of smaller scale, while Penn and Comell are larger in size. We sequentially evaluate
20

---

Published as a conference paper at ICLR 2024
Table 7: Overview of real-world evolving graph datasets
Facehook
100
Datasets
OGB-arXiv
DBLP
Pharmabio
Penn
Amherst
Reed
Johns Hopkins
Cornell
#Node (Start)
4980
6968
620
5385
107
85
368
1360
#Node (End)
169343
45407
57559
38815
2032
4762
16822
#Edge (Start)
6103
25748
2820
47042
192
188
1782
8148
#Edge (End)
1166243
267227
3005421
2498498
157466
31896
338256
1370660
Time Span
14
17
30
18
11
13
14
14
#Class
40
6
7
2
2
2
2
2
OGB-arXiv
Pharmabio
Penn
Homagerety Ratto (N0
0.75
Rallo (N)
Camegerreo Resto 28
0.510
0.90
0.700
0.505
0.70
0.675
0.500
0.65
0.85
0.625
0.60
2020
0.80
20100
2015
0.600
0.490
Year
Amherst
Cornell
Johns Hopkins
Reed
Homigenntty Battn (8)
0.54
Homogersity Dalla (%)
0.52
Homogerelty Ratto (N)
0.52
0.52
0.50
0.50
Homogeretty
0.52
0.48
0.48
0.46
0.46
0.50
0.46
Year
Figure 10: Homophily ratio analysis different datasets.
our model's adaptability to datasets different scales. All these datasets end the year of 2010 with the number of nodes varying from 865 38,815 and edges from 31,896 2,498,498.
In addition, research on the homogeneity and heterogeneity of graphs has received widespread tention in recent years. In the context of graph data, homogeneity and heterogeneity refer to whether the nodes and edges in the graph are of the same type (homogeneous) or different types (heteroge- neous). For example, in social network, a homogeneous graph might represent individuals (nodes) and friendships (edges), where all nodes and edges are of the same type. On the other hand, a het- erogeneous graph could represent individuals, events, and organizations as different types of nodes, with edges representing relationships like "attended," "organized," or "works for." In our work, we do not limit pre-define the homogeneity and heterogeneity in the data. Moreover, we calculate the homophily ratio of nodes on different experiment datasets, as shown in Figure I0 According to the distribution of homogeneity, there is significant difference in the proportion of homogeneity among different datasets, and varies greatly over time.
G ADDITIONAL EXPERIMENTAL RESULTS OF SMART
In this section, we provide a comprehensive illustration of the experiment details for temporal gen- eralization estimation in evolving graphs, including the experiment settings, implementation details and completed results.
G.1 EXPERIMENT SETTINGS
Baselines.
We compare the performance of SMART with following three baselines.
Linear: Linear regression is straightforward statistical learning methods for modeling the relationship between a scalar and variables. We observe that the performance degradation of Barebási-Allert random graph shows approximate linear process. Therefore, to estimate the
21

---

Published as a conference paper at ICLR 2024
GNN performance degradation real-world datasets, adopt linear regression baseline to predict the performance changes.
Differences of confidences (DoC) approach (Guillory et al., 2021 proposes to estimate the performance variation on distribution that slightly differs from training data with average confidence. DoC yields effective estimation image classification over a variety shifts and model architecture, outperforming common distributional distances such Frechet distance Maximum Mean Discrepancy.
DoC:
Smilarit
Regressor
Score
Base Distribut
Target Distribution
Figure 11: System framework of DoC for temporal generalization estimation in graphs. (Modifica- tion of Figure in paper (Guillory et al. 2021)
Supervised: Moreover, design a comparison method for temporal generalization estimation with supervised signals. Although we are unable to access the labeled data over acquire new node labels and retrain the model on the
the time during
post-deployment, in experiment new data, which is approximately a upper performance limit of this problem.
GNN Architectures. To fully validate and compare the effectiveness of different methods, we select four different graph neural network architectures follows.
GCN (Kipf & Welling 2017 GCN is one of the most classic graph neural network architecture, which operates localized first-order approximation of spectral graph convolutions.
GAT Velickovic et al.) 2018) Graph Attention Network (GAT) leverages attention mechanism
to selectively focus on different neighboring nodes of the graph when aggregating information.
GraphSage (Hamilton et al., 2017): GraphSage is graph neural network architecture designed for scalable and efficient learning on large graphs. addresses challenge by sampling and aggregating information from node's local neighborhood.
TransformerConv (Shi al. 2021b): In light of the superior performance of Transformer in NLP, TransformerCony adopt transformer architecture into graph learning with taking into ac- count the edge features. The Multi-head attention matrix replaces the original normalized adja- cency matrix as transition matrix for message passing.
Evaluation Metrics. To evaluate the performance, we adopt following four metrics to measure the effectiveness of temporal generalization estimation over time.
Mean Absolute Percentage Error (MAPE) quantifies the average relative difference between the predicted generalization loss and the actual observed generalization loss, which is calculated as
T
ex x 100%.
MAPE T
deploy Tomfasakes ++1
E
Root Mean Squared Error (RMSE) is calculated by taking the square root of the average of the squared differences between predicted and actual generalization loss, which calculated as
T
RMSE
Σ
(e- - 2,)
T
deploy r r= +1
22

---

Published as a conference paper at ICLR 2024
Table 8: Hyperparameter setting in our experiments
Facebook 100
Datascts
OGB-arXiv
DBLP
Pharmabio
Penn
Amherst
Reed
Johns Hopkins
Comell
GNN Layer
3
2
2
2
2
GNN dimension
256
256
256
256
256
256
256
RNN Layer
1
RNN dimension
64
8
64
64
64
32
64
8
loss lambda
0.5
0.9
0.7
0.3
0.9
0.7
0.1
0.5
learning rate
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
Mean Absolute Error (MAE) measures the average absolute difference between the predicted generalization loss and the actual generalization loss, which is calculated as
T Σ Eeplly fordgpay
1
MAE-
T
Standard Error (SE) measures the variability of sample mean and estimates how much the sample mean is likely to deviate from the true population mean, which is calculated as SE = a //,n, where a the standard deviation, n is the number of samples.
G.2 IMPLEMENTATION DETAILS
Data Labeling. To simulate real-world human annotation scenarios, randomly labeled 10% of the samples during the training of the pre-trained graph neural network model. Prior to deployment, each time step, additionally labeled 10% of the newly appearing nodes. After deployment, no additional labeling information was available for newly added nodes. For consistency, we use only the first three frames obtain few labels for all real-world datasets, which relatively small sample size. Further enhancing the labeled data can yield additional improvements in temporal generalization estimation.
Hyperparameter Setting. We use Adam optimizer for all the experiments, and the learning rate for all datasets are uniformly set to be 1e-3. In all experiments, the pre-trained graph neural networks are equipped with batch normalization and residual connections, with dropout rate set to 0.1. Meanwhile, We employed ReLU activation function. We set hyperparameter each datasets and specify the details in Table
Hardware. All the evaluated models are implemented on a server with two CPUs (Intel Xeon Platinum 8336C 2) and four GPUs (NVIDIA GeForce RTX 4090 8).
G.3 EXPERIMENTAL RESULTS
Comparison with different baselines. We conduct performance comparison of SMART and other three baselines on three academic network datasets. As shown in Table we observe strikingly prediction improvement. Our proposed SMART consistently outperforms linear regression and DoC on different evaluation metrics, which demonstrates the superior temporal generalization estimation of our methods. For example, on Pharmabio datasets, due to its long-term temporal evolution, the vanilla linear regression and DoC shows inferior prediction due to the severe GNN representation distortion. Our SMART shows advanced performance due to our self-supervised parameter update over the time.
In addition, when comparing with supervised method, due to its continuous acquisition of annotation information and retraining during the testing phase, is approximately the upper limit of the estima- tion performance. On OGB-arXiv dataset, our SMART achieves close performance with Supervised, indicating our strong ability to cope with evolving distribution shift. However, on Pharmabio dataset, accurately estimating its generalization performance remains challenge due to its long-term lution (30 timesteps). Thereby, temporal generalization estimation an important and challenging issue, and still deserves further extensive research.
23

---

Published as a conference paper at ICLR 2024
Table 9: Performance comparison of SMART and baselines on three academic network datasets. MAPE, RMSE, MAE and Standard Error are utilized to evaluate the estimation performance on different datasets. The smaller the value, the better the performance.
Dataset
Metric
Linear
DoC
SMART (Ours)
Supervised
MAPE
10.5224
9.5277=14877
2.189720.2211
2.1354:0:500
OGB-arXiv
RMSE
0,4764
0.3689=0.04000
0.1129x0.0157
0.0768=0.0155
MAE
0.4014
0.3839=0.0404
0.0383+0.0083
0.02 8#0.0199
MАPE 16,4991
1.3910=0.1322
3.4992+0.1502
2.5359+0.4289
DBLP
RMSE
0.5531
0.1334=0.0058
0.1165#0.0444
0.0914:0..0
MAE
0.431
0.1162:0.0300
0.097820.0344
0.0852a0.0038
MAPE 32.3653
8.1753+0.0745
1.3405
0.4827=0.0798
Pharmabio
RMSE
0.7152
0.152 1 =0.0014
0.0338:0.01336
0.0101
MAE
0.6025
0
0.0282:0.0120
0.008820.0026
Table 10: Performance comparison of different GNN architectures, including GCN, GAT, Graph-
SAGE and TransformerCovv. We use MAPE Standard Error evaluate the estimation on different scenarios.
GNN architecture
Dataset
Method
GCN
GAT
GraphSAGE
TransformerConv
Linear
10.5224
12,3652
19.5480
14.9552
OGB-arXiv
DoC.
13.5277+14857
12.2138+1.222
20.5891 +0.4553
10.0999#0.1972
SMART
2.1897#0.2211
3.1481 #0.4079
5.2733
3.5275x1.1462
Linear 16.4991
17.6388
23.7363
18.2188
DBLP
DoC
4.3910aa.1380
13.873524.1744
11.900 1.9003=1.8249
9.0127+2.661
SMART
3.4992+0.150
6.6459x1.3401
9.9651
6.4212
Linear
32.3653
29.0404
31.7033
31.8249
Pharmabio
DoC
8. 3.17055057745
7.4942+0.0702
6.6376=0.0194
5.3498:0
SMART
1.3405
1.21977a.2241
3.1448:0.6855
2.7357
Comparison with different GNN architectures. To evaluate the applicability of proposed algo- rithm, we conduct temporal generalization estimation on different GNN architectures. As shown in Table I0, first of all, our SMART shows consistent best performance among different architectures. Besides, for different graph neural network architectures, they tend to capture the structure and fea- ture information from different aspects. Due to the simple model structure of GCN, SMART shows advanced prediction performance among other architectures, which is also consistent with the theory of classical statistical machine learning.
Comparison with different time series model. To capture the temporal drift of GNN generaliza- tion variation, propose an RNN-based method (i.e. LSTM). Moreover, we additionally replace the LSTM with other two time series model Bi-LSTM and TCN as follows:
Long Short- Term Memory (LSTM) is type of recurrent neural network (RNN) archi- tecture designed address the vanishing gradient problem in traditional RNNs. The ability of LSTTs to selectively remember or forget information makes them well-suited for tasks involy- ing long-term dependencies, and become standard architecture in the field of deep learning for sequential data.
LSTM:
Bi-LSTM Graves & Schmidhuber (2055: Bidirectional Long Short-Term Memory (Bi-LSTM) is an extension of the traditional LSTM architecture that enhances its ability to capture informa- tion from both past and future context.
TCN (Lea et al. 2017h: Temporal Convolutional Network (TCN) use ID convolutional layers to capture dependencies across different time steps in sequence. Unlike traditional CNNs, TCNs
24

---

Published as a conference paper at ICLR 2024
OGB-arXiv
DBLP
Pharmabio
TCN
Smart Beseline
TCN
Smart
TCN
Smart
Baseline
BILS
BILSTM
BI-LSTM
DoC
Linea
Linea
5
10
15
10
15
2
MAPE
MAPE
MAPE
Figure 12: Comparison with different time series model, i.c., LSTM, Bi-LSTM and TCN.
use dilated convolutions to extend the receptive field without significantly increasing the number of parameters.
Different time series methods worth trying out, since we hope to capture the temporal changes based on a small number of training snapshots. In our experiment, as depicted in Figure 12 our SMART achieves the optimal performance using three different time series models on both OGB- arXiv and Pharmabio datasets. On DBLP dataset, SMART achieve the best performance using LSTM, while SMART equipped with Bi-LSTM and TCN show close performance with DoC. In order to maintain consistency in the experiment, we adopted the same hyperparameter settings. From the perspective of parameter size, the parameter quantity of Bi-LSTM is nearly twice that of LSTM, while the parameter quantity of TCN is very small. It can be seen that as the parameter size increases, the prediction error generally decreases first and then increases. Therefore, it is very important to choose appropriate models and parameter settings based on the complexity of the data.
Comparison with different graph data augmentation methods. Self-supervised learning is a popular and effective learning strategy to enrich the supervised signals.
Recent success of self supf-super learning on image datasets heavily rely on various data augmenta- tion methods. Due the irregular structure of graphs, existing graph augmentation methods can be categorized into topological- -baseeed augmentation and attributive-base augmentation. our work, adopt three familiar and effective graph data augmentation methods to generate different views for self-supervised graph reconstruction, shown as follows:
DropEdge (Rong et al. 2020): Randomly delete some edges with a certain probability, thereby changing the graph structure as the input of GNN.
2021): Instead of randomly delete some edges, DropNode randomly delete some nodes with a certain probability.
DropNode (Papp et al.)
Feature Mask (Hu et 2020b): Randomly mask features of portion of nodes with a certain probability, thereby changing the node feature of graphs.
Figure ?? shows experimental results, and our SMART shows the best performance on three datasets. Due to consideration of both structure prediction and feature reconstruction, the overall impact of different data augmentation methods on performance is relatively stable.
Ablation study and Hyperparameter Study. In the main text, due space constraints, we have chosen to present representative experimental results from some selected datasets. In order to pro- vide more comprehensive demonstration of the effectiveness of SMART, we have included com- plete experimental results for eight datasets, including ablation experiments and hyperparameter experiments, in the appendix.
The correspondence between figures and experiment settings is as follows:
Figure
13
Ablation Study of SMART on all datasets.
Figure
Hyperparameter Study on proportional weight ratio À of SMART on all datasets.
Figure 15
Hyperparameter Study on RNN dimension of SMART on all datasets.
25

---

Published as a conference paper at ICLR 2024
M1 wio augmentad graph reconstraction
M3n wio structure reconstruction
Smart (Curs)
wi RNN
M36 : wio feature reconscraction
OGB-arXiv
DBLP
Pharmabio
Peun
10.0
MAPE
7.5
0.75
5.0
2.5
0.25
M4
M2
Mia
M33 Ous
M1
M3N
MSD Oues
M1
M2
MSa MB6 Ours
M1
M2
Mãa M36 Ouss
Hopkins
Cornell
0.000
1.5
MAPE (N)
1.0
00,000
M1
M7
Min
Mi1h
Ours
0.005
M1
M7
M4s
M55
Oure
0.0
M2
Mib
Ouri
M7
Mfn
Milh
Oues
Figure 13: Ablation Study of SMART on all datasets.
DBLP
Pharmabio
(MPE((5)
2.0
0.50
4
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
Loos mitoo
Loss catio
Loss mili
Loss ratio
Amherst
Read
Johns Hopkins
Cornell
MAPE (9)
0.095
1.2
1.50
1.0
5.0
0.090
1.25
2.5
Ditilo
ratio
Figure 14: Hyperparameter Study on proportional weight ratio À of SMART all datasets.
OGB-arXiv
DBLP
Pharmabio
Penn
0.9
MAPE
0.8
64
16
32
64
128
128
RNN dimension
RNN dimension
RNN dimension
RNN dimension
Ammeertt
Reed
Johns Hopkins
Coreel
0.100
1.5
MAPE
0.095
5.0
1.0
2.5
16
32
64
128
8
16
32
64
128
8
16
32
64
128
128
RNN dimension
RNN dimension
RNN dimension
RNN dimension
Figure 15: Hyperparameter Study on RNN dimension of SMART on all datasets.
26


Reviews:
[{"review_id": "OeJ4aKUBVH", "reviewer": "Reviewer_jJDp", "summary": "This study investigates the representation distortion of graphs during evolution. The authors proposed SMART to estimate the temporal generalization performance of GNN. The authors provided theoretical proofs as well as numerical experiments, showing the distortion of representation is inevitable and providing a way of estimating generalization loss.", "questions": "Figure 1 is a bit confusing: what’s the x axis? And what are the nodes at each year?\n\nFor the information loss, the authors considered the loss from RNN as well as from representation distortion. Can the authors comment on the loss of information from graphs to their low dimensional representations and their effects on the model.\n\nMore evaluation metrics besides MAPE should be considered for the synthetic datasets.\n\nInterestingly GCN seems achieved the best performance in the three compared GNNs, can the authors comment on the contribution of different GNN structures to the performance?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is a novel study trying to analyze the representation distortion from an information theory perspective, which I think is an important and interesting question.  The authors theoretically establish a lower bound and conducted various numerical experiments using both synthetic datasets and real world datasets. Introduction is straightforward. The results seem promising. The ablation study is convincing and sufficient.", "weaknesses": "The authors mainly compared their results with linear regression. The authors may add more model comparisons to make the results more convincing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FJYcX0AdRa", "reviewer": "Reviewer_btk3", "summary": "This paper studies the problem of estimating the generalization performance of GNNs on evolving graphs. The authors propose SMART, which estimates the generalization performance of GNNs without the need for manual annotation post-deployment. SMART employs self-supervised contrastive graph reconstruction to update the feature extractor, minimizing information loss during the dynamic evolution process.", "questions": "See W1-W3 for details.", "limitations": "", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. The problem is of significant importance in dynamic graph learning, and the authors provide theoretical proofs to demonstrate that representation distortion is inevitable.\n\nS2. The authors derive a closed-form expression of the generalization error bound on synthetic data and verify the effectiveness of the proposed method.\n\nS3. The paper is well-written, and I have no complaint about the presentation of the paper.", "weaknesses": "W1. The theoretical analysis is limited to single-layer GCN models. It would be nice to see an extension to more complex models.\n\nW2. The baseline only includes simple linear regression models. However, a better baseline should be a model that continuously acquires new node labels and gets retrained on the new data, to examine whether the generalization curve of such retraining is close to the prediction of the proposed method. This can more intuitively demonstrate the advantages of the method.\n\nW3. The paper shows that in the citation networks, the performance drop of pretrained models is mainly due to the increase of nodes and edges, while the category distribution does not change significantly. However, in real-world applications, changes in labels are very common, which will lead to concept drift and cause the model's performance to decrease dramatically. It is worth discussing whether the proposed method is applicable to such scenarios with frequent label changes and concept drift.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GyYYHmFUaB", "reviewer": "Reviewer_qkRe", "summary": "This paper proposes a method (SMART) for performing generalization error estimation on temporal node classification tasks. The authors show that representations will become increasingly distorted as time increases, and propose to use both a structure graph reconstruction and feature construction loss to improve representation quality. The adapted features are feed into an RNN that is trained to predict the loss. The authors also propose two theorems: one which shows that distortion is strictly increasing over time, and the other one is specific to the Barbasi Albert graph and is used to argue the benefits of SMART.", "questions": "Please see the weaknesses above.\n\nI'd appreciate some clarifications about the theorems and potential baselines as mentioned above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- This paper studies an interesting problem (generalization gap prediction for temporal node classification) that has not been well-studied in the graph representation learning literature before. \n\n- The authors conduct experiments across a variety of datasets, and conduct several ablations to demonstrate the benefits of each of the components of SMART. \n\n- The authors attempt to provide some theoretical bounds and use these, as well as an information theory framework, to ground the proposed method.", "weaknesses": "- The authors only compared to a single linear regression baseline. While other methods for generalization prediction are not specific to temporal graph data, it should still be possible to consider some. Maybe some from [1] could be adapted? In this vein, I think there should be more citations to other generalization error predictors and a dedicated related works section in the main paper. \n\n- The theorems need to be discussed more. For example, in theorem 1, I don't think that beta has been defined. Furthermore, while the authors make the strong but acceptable assumption that the graph will only add edges, I was wondering if it was also assumed that the underlying graphs were homophilous. Do the authors expect the proposed method to work on heterophilus graphs as well? \n\n- The writing could be improved. For example, its not clear why the approach is referred to as \"constrastive.\" From my understanding the authors do augment the graph, but the overall loss is purely reconstruction based. \n\n[1] Predicting with Confidence, Guillory et al. ICCV 2021(https://arxiv.org/abs/2107.03315)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZYBcLdPgIN", "reviewer": "Reviewer_JYus", "summary": "The paper presents an important question: how to ensure that GNN gives a good prediction for graphs that are rapidly evolving in time. The authors first give a theoretical proof to show that under mild conditions, as graph evolves, graph representation distortion is not avoidable (the loss is lower bounded). Secondly, the authors propose information losses in two phases: (1) information loss induced by RNN and (2) information loss induced by representation distortion. Then, the authors have proposed SMART that contains contrastive graph construction. The augmented feature graphs is randomly adding or dropping edges, and then structure reconstruction loss and feature reconstruction loss are used on the contrasted examples. The authors have verified the effectiveness of SMART on the barabasi-albert random graph, and performed extensive experiments to showcase SMART's effectiveness with evolving graphs.", "questions": "Q1. Theorem 1 is evaluated only for one layer GNN with a Leaky ReLU activation. Is Theorem 1 adjustable to multi-layer GNN and different GNN backbone structures such as GCN/GAT/GraphSage?\n\nQ2. Figure 3, what is the y-axis prediction loss? Why not use other evaluation metrics to showcase the GNN prediction performances deterioration?\n\nQ3. Is there a particular reason that RNN is used instead of other time-series model to capture the temporal variation?\n\nQ4. Will the contrastive graph reconstruction improve the feature extractor during the pre-deployment phase? Why just limit the contrastive learning and reconstruction to post-deployment?\n\nQ5. How will the proposed algorithm be used towards more complex real-time graphs? For example, how to deal with graphs that contain changing node labels and changing edge labels? How to apply the methods to heterogeneous graphs or spatial temporal graphs?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "S1. The paper targets evolving graph prediction, which is a challenging problem in the research community. It is novel to consider the evolving graph using information loss perspective, and the contrastive solution to resolve such problem is very convincing.\n\nS2. The paper is clearly written. The authors give a clear problem definition with theoretical justification. There are several architecture and losses considerations in the methodology, yet each component is clearly addressed. The author has also provided a theoretical proof on the barabasi-albert random graph to showcase the effectiveness of SMART.\n\nS3. The empirical results presented in the paper show that the proposed method SMART outperforms linear regression model, using the same GCN/GAT/GraphSage backbone structures and evaluated on four different datasets, showcasing the quality and robustness of SMART. \n\nS4. Given the ubiquity and increasing reliance on evolving graph in real-world applications, the capability to adapt to evolving graph is important. SMART can adapt to various graph learning architectures and has potential impact for studying the changing graphs in time.\n\nS5.  The ablation study is well-written and consider various loss configurations and hyper-parameter configueratons.", "weaknesses": "W1. The paper does not have a related work section. There should be at least some descriptions of the previous work which showcases that GNNs performances can suffer from the representation distortion over time, and the performance degradation occurs.\n\nW2. There appears to be an inconsistency of mentioning the information loss in Section 3.2 and introducing SMART with contrastive loss in Section 3.3. The information loss is introduced, but not used in experiment settings (MPAE and standard error are used instead) or the later contrastive loss calculation. There should at least some experiments and measurements that connect information loss to contrastive learning post deployment, and to show that SMART is able to reduce the information loss induced by representation distortion. A theoretical justification is also fine.\n\nW3. The data augmentation in graph is too naive. The authors have only considered to randomly add or drop edges, which should only work for graphs without edge labels. While the random data augmentation technique works for barabasi-albert random graphs, it should not be effective for the cases where edge labels are also changing (for example, people change their relationship status with other people). The authors should consider more complex data augmentation techniques in graphs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uwdoMDNSCs", "reviewer": "Reviewer_e5fg", "summary": "The paper analyzes and tackles the challenge of temporal representation distortion in GNNs as the graph evolves over time, so as to yield better generalization estimation. Based on a few assumptions, the authors theoretically establish that such distortion is strictly increasing over time with a lower bound. Furthermore, based on the pre-trained GNN and an RNN that performs temporal generalization estimation, the authors propose a solution that incorporates an adaptive feature extractor that operates through self-supervised graph reconstruction, aiming to estimate and adjust for the distortion. Under a synthetic random graph setting,  a closed-form generalization error is also derived. Experiments on synthetic and real-world benchmarks demonstrate the effectiveness of the proposed method in terms of substantially improving estimation accuracy and generalization ability.", "questions": "Please see the weaknesses.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.\tThe general motivation for analyzing the generalization of evolving graphs is interesting and important. It is also interesting to see the theoretical analysis with a synthetic random graph demonstration with a closed-form generalization error.\n2.\tThe presentation quality of this paper is in general satisfactory, in terms of the organization and figure demonstration.\n3.\tThe experiments and analysis on the proposed method itself are relatively sufficient including model component ablation and hyper-parameter study.", "weaknesses": "1.\tOne major concern is the lack of baseline methods. The proposed method is only compared with a linear regression, which turns out to be a naive baseline. The methods mentioned in the related work D.2 are not compared. Moreover, only the MAPE with standard error is evaluated. More evaluation metrics are expected.\n2.\tIt will be better if the methods are evaluated on a few more state-of-the-art backbones to further enhance the effectiveness of the proposed method.\n3.\tThe assumptions made to conduct theoretical analysis and bound derivation could be a concern as they are often too strong. Evolving graphs also contain nodes disappearing in many cases(e.g. sensor networks with possible malfunction over time), which means the assumption of an ever-growing network can be often invalid. Moreover, the zero-mean requires a non-min-max preprocessing of features. The authors need to be specific about the claims.\n4.\tIt would be better to sketch the connection between the information loss and the form in Equation 2, section 3.2.\n5.\tIt would be better to define some notations such as the function l, and generalization error beforehand for better understanding of the idea.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)