Temporal Graph Neural Tangent Kernel with Graphon-Guaranteed
Authors: Katherine Tieu
Dongqi Fu
Yada Zhu
Hendrik Hamann
Jingrui He
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Kernel
Temporal Graph
Neural Tangent Kernel
Primary area: graph_neural_networks

Abstract: _Graph Neural Tangent Kernel_ (GNTK) fuses graph neural networks and graph kernels, simplifies the process of graph representation learning, interprets the training dynamics of graph neural networks, and serves various applications like protein identification, image segmentation, and social network analysis. In practice, graph data carries complex information among entities that inevitably evolves over time, and previous static graph neural tangent kernel methods may be stuck in the sub-optimal solution in terms of both effectiveness and efficiency. As a result, extending the advantage of GNTK to temporal graphs becomes a critical problem. To this end, we propose the temporal graph neural tangent kernel, which not only extends the simplicity and interpretation ability of GNTK to the temporal setting but also leads to rigorous temporal graph classification error bounds. Furthermore, we prove that when the input temporal graph grows over time in the number of nodes, our temporal graph neural tangent kernel will converge in the limit to the _graphon_ NTK value, which implies the transferability and robustness of the proposed kernel method, named **Temp**oral **G**raph **N**eural **T**angent **K**ernel with **G**raphon-**G**uaranteed or **Temp-G$^3$NTK**. In addition to the theoretical analysis, we also perform extensive experiments, not only demonstrating the superiority of Temp-G$^3$NTK in the temporal graph classification task, but also showing that Temp-G^3NTK can achieve very competitive performance in node-level tasks like node classification compared with various SOTA graph kernel and representation learning baselines. Our code is available at https://github.com/kthrn22/TempGNTK.

Temporal Graph Neural Tangent Kernel with Graphon-Guaranted
Katherine Tieu*
Dongqi Fu" Meta AI
University of Illinois Ltrann-Chaapaln kt420illinois edu
com
Yada Zhu
Hendrik Hamann IBM Research hendrikh@us ibm com
Jingrui He
IBM Research
University of Illinois Urbana-Champaign jingrui@illnne edu
yzhu@us. ibm. com
Abstract
Graph Neurul Tangent Kernel (GNTK) fuses graph neural networks and graph kernels, simplifies the process of graph representation learning, interprets the training dynamics of graph neural networks, and serves various applications like protein identification, image segmentation, and social network analysis. In practice, graph data carries complex information among entities that inevitably evolves over time, and previous static graph neural tangent kernel methods may be stuck in the sub-optimal solution in terms of both effectiveness and efficiency. As a result, extending the advantage of GNTK to temporal graphs becomes critical problem. To this end, we propose the temporal graph neural tangent kernel, which not only extends the simplicity and interpretation ability of GNTK to the temporal setting but also leads to rigorous temporal graph classification emror bounds. Furthermore, prove that when the input temporal graph grows time in the number of nodes, our temporal graph neural tangent kernel will converge in the limit to the graphon NTK value, which implies the transferability and robustness of the proposed kernel method, named Temporal Graph Neural Tangent Kernel with Graphon-Guarantee
Temp-G"NTK. In addition the theoretical analysis, we also perform extensive experiments, not only demonstrating the superiority Temp-G*NTK the temporal graph classification task, but also showing that Temp-G'NTV can achieve very competitive performance in node-level tasks like node classification compared with various SOTA graph kernel and representation learning baselines. Our code is available at https: htt///gtttutt com honnkthrn22//
TempGNTK
Introduction
Graphs, relational structure, model the complex relationships among entities and have attracted much research attention nowadays. To serve various applications, graph neural networks have been extensively studied for their representation learning ability. On the one hand, graph neural networks usually need to build complex neural architectures with hyperparameters to achieve their powerful expressive ability, which typically nonlinear process and hard interpret (50] 13 21
On the other hand, graph kernels enjoy the explicit formula and can be convex, leading to solid theoretical results, although their specific form often hand-crafted and may not be powerful enough to support complicated application scenarios 23 34 [2]. Hence, graph neural lungent kernel (GNTK) [9] has been proposed to fuse graph neural networks and graph kernels, enjoying the benefits of both
Equal Contribution
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

approaches, i.e., achieving the excellent representation ability while relying on simple computation processes.
However, in the real world, the graph topology and features are inevitably evolving over time, e.g.; the user connections and interests in social networks. This temporal evolution brings new challenges to GNTK research as to how the similarity of temporal graphs is measured and how the corresponding kernel matrix derived. To be more specific, how can we design a temporal graph neural tangent kernel, which not only has a superior representation ability than temporal graph neural networks [39 g but also inherits the expression simplicity and analysis rigorousness of graph neural tangent kernels 99 24
Hence, we propose Temporal Graph Neural Tangent Kemel with Graphon- Graphon-Guaranteer Guaranteed, or Temp- GANTK. First, we propose the kernel matrix computation formula for temporal graphs with time- evolving structures and time-evolving node features, and the corresponding kernel value can be used for classification tasks with generalization error bounded. This proposed kernel method addresses how measure the similarity between temporal graphs to achieve the accuracy of graph neural networks but without complex neural computational procedures like gradient descent. Second, considering the property of temporal graphs, we also prove that when the temporal graph is growing, i.e., the number of nodes increases over time, our Temp-G*NTK kernel will converge in the limit to the graphon NTK value. This result addresses the challenge of adapting graphon neural network 41 and graphon neural tangent kernel (4 to the temporal setting, and, more importantly, demonstrates that Temp-G NTK has the excellent potential to transfer large-scale temporal graph data with robust performance. Third, in addition to the theoretical analysis, we also design extensive experiments for not only temporal graph classification but also temporal node classification, illustrating the effectiveness of the proposed Temp-G2NTK NTK compared with various state-of fatte-of-the -htt temporal graph representation learning and graph kernel methods.
2 Temporal Graph Modeling
To begin with, we first denote a static undirected graph as G (V, where V and E are sets of vertices and edges, respectively. We also denote the node features of node (v E V) as h, E Rd, the neighborhood as (w),, and edge features of an edge (u, v) as euv-
In order extend to the temporal setting, researchers usually model the temporal graph G as continuous- -imme dynamic graph (CTDG) (22), which is mathematically represented as a stream of events, G {(u, u. (t),), (t), (t) (T where an event (u, v, h (t), hy (t), ewe t) indicates that at time an edge exists between node and v, and (t), h, (f), and ewo are the features of u, v, and (u, v) at time t, respectively. To support different computation requirements, CTDG G can also be transferred into discrete-time dynamic graph (DTDG) (22), which is collection of snapshots G To be specific, a snapshot of G at any time 2 to. is denoted as G(),, which can be obtained by sequentially updating the initial state of (ta) with the event stream, i.e., G()) {u, v, bn (f), h, (f), ewv (f), () given (to S S t), and temporal graph equals to the last time snapshot, i.e., G G(T) given the last timestamp is denoted by T.
Let V (t()) be the sets of vertices and edges of G(O). We denote the temporal neighborhood of node e at time t as (z) = {u, f) ((u, v. h, (t), h, Cuvt) E G i.e., set of nodes u that are involved in an event with at any time (to S sts t). Note that, in the rest of the paper,
G' to denote an entire temporal graph, and (t)) as snapshot. For simplicity, we denote to 0.
3 Preliminaries of TeTK
3.1 Temporal Graph Representation Learning
Graph Neural Networks (GNN) are a family of neural architectures for graph representation learning. In general, most GNNs leverage a message-passing framework compute node v's representation ( at the g layer. In the static setting, h can be obtained by applying a neighborhood aggregation operator on h (1-1) Vu E (v)),, then transforming the aggregated neighborhood information. The graph-level representation can be obtained by applying a pooling function on representations of all nodes, e.g., the summation of all node representations.

---

h (1) V 2 J (w h(- To derive our first step is to compute node representations at time t and then apply pooling function over all nodes obtain the graph-level (or snapshot-level) representation. Specifi- cally, we obtain the node representation of v at time ht),,, by aggregating information from its temporal neighborhood N
as
(1) = c.
Σ (w.
Lena(l -
where (t) is the node feature at time t, tene R 4 is the time encoding function that can be instantiated [8] as (ene (At) cos (As()))), and E Rd with its 7th entry [w]; (i-1)/8 and de is the dimension of the time representation vector. Operation [-]]-] denotes the concatenation. c is the scaling factor, and if we set e = 1, then Eq. is simply the sum neighborhood aggregation; and if c = [o then Eq. would be the average neighborhood aggregation. Note that if the edge
features do not exist then we simply set eur (t) = 0. Similarly, if node features are not available then we let x (t) O.
After aggregating information from node e's neighborhood at time as Eq. we can input (t) into L layers of Multilayer Perceptrons (MLPs), where the representation of node after the 1t MLP projection is as
where dj the output dimension of the 1th MLP layer, or is non-linear activation function that can be instantiated as the Rectified Linear Units (ReLU) function.
Furthermore, we denote the graph-level representation of ((t) as ho(() = Evevio ( (t).
3.2 Graph Neural Tangent Kernel
Next, we provide some background on the infinite- width limit of fully connected deep neural network frn and derive the definition of NTK and its properties on graphs.
Consider the following settings: given a training dataset of samples f(x; vil where x; Rd and its label denoted by ys R. Let fren (x, f) be the output of a fully-comnected neural network, with parameters 9 E R2 and x as the input. We train fre by minimizing the squared loss over the training dataset.
" ((0) - Σ (Jin -
Let X TRaxd (where X]: x,) and y TRn (where [y,]= yi), such that fun (X, 0) would be the prediction of frn. with parameters 0, over all x; of the training set.
Suppose that é is minimized by gradient descent, so the output fmn((, 0) evolves with respect to the training time 7 as follows [.
d fnn (x,(X, 6(T)) = (H (Fnn (X, 0(T)) y)
dr
where 0(T) is the parameters being updated at training time 7 based on gradient descent, and H(T) positive definite matrix with its (i, j)th entry follows
Ofn (xi, O(T)) pm (xj, ((T))
(5)
00
00
Existing works on over- parameterized neural networks 2]
and [19 have proven that for infinite-width neural networks, the matrix H(T) remains constant during training, and under random initialization parameters, the matrix H()) converges in probability to certain deterministic kernel matrix H', which is named as Neural Tangent Kernel [19]. Moreover, as proven in [I 2
the prediction of fully-trained sufficiently wide ReI.U neural network is equivalent the kernel regression predictor with the kernel matrix H"
3

---

For the temporal setting, similar to the NTK and the infinite-width neural networks, let fiemp denote the aforementioned temporal GNN in Section 3.1 and ftemp(Gtt W) be the output of ftemp with the imput GK*) and parameters W. Given two temporal graphs G and G', time t, the NTK value corresponds to infinite-width fremp. ie., in the limit that di + oo, where dj is the output dimension stated in Eq. 2 I [L]. such that
OffCe) W) Of(G"M) W) (W)) OW
K K ('(, Ew--N(01))
(6)
OW
Then, the rest of this paper, we can refer to this value K ((G(), G*(t)) as the Temp-G value of G' and G" at time t. In the next section, we ready to introduce how to compute the defined kernel as Eq. without training neural networks.
4 Proposed Temp-GPNTK
Given two temporal graphs G and G', we propose to compute the Temp-G*NTK value at time t, ic., (GG(), G) with L BLOCK operations We discuss the detailed computation procedure of Temp-G*NTH here and leave the theoretical derivation in Section
In general, similar to [19, we first recursively compute the node pairwise covariance matrix ( its derivative {0)) and the node-pairwing kernel matrix ( that correspond to the 1th BLOCK transformation. Finally, the Temp-G'NTK value is obtained by the summation of all of the entries in the kernel matrix the last BLOCK transformation, i.c., (L))
To begin with, we initialize the node pairwise covariance matrix E and the kernel matrix E at entries u, w' (u E V(O, w' & V*()) as the inner product of node representations of u, u' at time 4 respectively,
(0) (G(t) ((())))(()) Jun'
x (G()) ("(t))anr ha(()" h.
where (t) and h', (t) are computed by Eq.
Next, we need to compute ( and (4) that correspond to the 1th BLOCK operator with ReLU activation function a. As (xx max(0, x). the derivative of (x) = 1[x 2 0), where the
indicator vector") For 1(1 < < L), we first define an intermediate covariance matrix
Σ (G(()) GO( Juw
E (G-1( (()) un
A (C GO()))
(8)
E 1 (11) (G Ge
D ( ( ('(l))
and A (1) (G(t), ()(!))))) E 2
As the covariance matrix Σ transformed by BLOCK operations, we can compute (() and (1) based on the aforementioned intermediate covariance matrix as
(0) represents the i.i.d centered Gaussian Processes of (t)(t) and (f, after
0 (G!)) Gd(()) Juw' E (GD))
o(b)
arccos ( (I()))(((1) (1(()) V1 (1-11) (G(O))(() G'(t)) )w )2
2π
2T
(9)
with (G00 ( )ew -E
(b((a) o(b)
arccos D (1-1) (G() (*(() )ww) )m(())
(10)
2x
We follow the name "BLOCK" 9.. which can be understood as an iterative transformation operation. new version for temporal graphs is expressed Eq. [ Eq. with the pseudo derivative at
Eq. TO and Eq.

---

Eq. and Eq. hold due to the closed form of the kernel function with ReLU activation g(x,
Em (o' (wo x " (w"y)) y)] = arcros
2x
Then, the 1th kernel matrix, e is obtained
(G Go yu e (t- D (((())
(G(),,
+ (G(O,, G)(l)) (11)
Finally, the Temp-GeNTK G value of G, G' at time t is
K(G(), G*
Σ Σ vEV(O ('EV())
e (G(t), )ol
(12)
We perform summation over all entries since in proposed neural architecture in Section 3.1 can obtain the graph embedding by applying a pooling function, c.g., sum pooling, on node-level representations.
The pseudo-code of computing the Temp G NTK kernel as above is shown in Appendix A
Theoretical Analysis of Temp-G-NTK
5.1 Kernel Properties of Temp-G'NTK
To begin with, we first show that our proposed kernal function Cemp-G9NTK satisfies symmetric and semi-definite below, and the full proof can be found in Appendix
Theorem 5.1. Temp- NTK is symmetric.
Theorem 5.2. Temp-G is positive semi-definite.
5.2 Generalization Bound of Temp-GSNTK
We first state how to utilize classification task; then, we establish data-dependent generalization error bound of the function class of kernel regression predictors that are associated with Temp-GåNTK.
as kemnel regression predictor for the temporal graph
To be specifie, ii.d training set of n temporal graphs {G1, GG,...,,,, and their labels {11, 92....,..... J. our goal predict the label of testing temporal graph Grest- Then, the prediction of Glo any time I by a kernel regression predictor fkernel associated with Temp-G kernel K(-, is expressed as follows.
instantiate the problem of temporal graph classification, where, given
[kernel (Grr (( = [KCC G()),... K(G G(O))
(t) ( I-yy
(13)
where K train is a positive definite n x n kernel matrix, whose j-th entry is the Temp-G* NTK [K(t] (e K(G(t) G(t) and y R= is the label space of temporal
value of (())) (()) i.c., graphs, whose ith entry is [y]; - ys.
Then, we consider any loss function E : R R [0, 1] that is a-Lipschitz. We define the generalization error of the predictor Skernel in Eq. 13 at time that acts on a temporal graph labeled by y
[ie[fcerett(G)) (()))))) ..... G(I-1))) e(fkernet (G()),
(14)
where the expectation is taken over all (Gt)) drawn from the stochastic process IP ( ...., (.t,, conditioned on all previous snapshots before time of temporal graph G. The following theorem establishes the generalization error bound on all snapshot G(() of G.
G(t-1))
Theorem 5.3. Given n i.i.d training samples and their labels (G,,i and G, has timestamps,
(+) let train E Raxn be the kernel matrix of pairwise Temp- NTK values between graphs of the training set at time t and fkernet be the kernel regression predictor based on the training set and
'Wttoout loss of generality, we assume snapshot (1()) shares the label with its temporal graph G for clear notation.
5

---

K train: Consider any loss function t: RR x IR [0, 1] that is ar L-iischhitz, the generalization error of the fkernel predictor can be upper bounded as
T
Ble(Seernel (G BD)GG G( G. -a:pa))-[[(aaaaa {[Skernet ([]kernet(Gt)) (G()),)))
sup REC
T
(15)
S o
sup
K
(t) train
J tr(K(tt (rasn)
where L is the class containing all a - ce.iiichit,fuucctioo the expectation is taken over all G( that drawn from (.(.)G()) ,..., (.t,). G(t-))).
In brief, inspired by existing works generalization bounds for kernel classes bound our generalization error by the Sequential Rademacher Complexity [8 26 of F (i.e.,
4 we first
the function class containing kernel such fkernei), and then bound this complexity measure by (sup, y [ train -yy-tr(k (rain): where sup, y" [Krainn
train) gives maximum value of yd K train l-yy tr(K train)) over all timestamps of the training temporal graphs. The classification the temporal graph G is the max-aggregation of fketne((G(t)). The full proof is in Appendix C
tr(K(())
tr(k
(t)
5.3 Convergence of Temp-G'NTK.
In this part, we investigate our TeT value on two growing temporal graphs, G and G'. "Growing" means the number of nodes in G and G' would increase with time, and the following theorem shows that the proposed Temp-G&NTK enjoys a rigorous convergence. To verify this, we first adopt the definition of Graphon NTK on single growing graph (24) and then extend the concept to different and temporal graphs to establish the convergence of Temp-G"NTK value of G, G" as follows. The full proof is provided in Appendix D
Theorem 5.4. Given two growing temporal graphs G and G' and two graphons W and W suppose snapshots of (i.e., GO) converge to W and snapshots of G' (i.e. G converge to W", as I + co. Then, the graphon nearal kangent kernel induced by Temp-G" NTK of G, G' at time iee, Kw (W()), W"(),, converges the limil of the operator norm to the graphon neural tangent kernel of W and W i.e. Kw (W, W"), as follows:
lim K[ (W(!), (W()), - Kw (W, W + 1-000
(16)
where Kw denotes the graphon NTK value.
This theorem addresses the convergence limitations of previous work (24) in terms of different temporal graphs. In other words, besides temporal dependencies between snapshots of different evolving graphs, the work [24] only establishes a limit object for different stages of a single growing graph. An empirical visualization can be seen Figure and the detailed comparison and illustration are delivered in the Appendix D.3
5.4 Time Complexity of TeTT-GeNTK
Here, the following table shows the time complexity comparison between our Temp-G*NTK with other graph kernel and graph representation learning methods for measuring pairs of temporal graphs at a certain timestamp 1.
In the above table, we first need to declare some mathematical notation as follows. [V], F denote the maximum size of the vertex set and edge set among n given graphs. Then, for the time complexity of WL-Subtree [42), Graph2 [33 and GL2Vec (6), denotes the number of iterations in WL- Subtree algorithms; for Graph2Vec [33 and GL2Vec [6], D represents the maximum degree of the rooted subgraphs that used to compute graph embeddings; and for the time complexity of NetLSD 455 & denotes the number of eigenvalues (obtained from the graph Laplacian matrix) used to compute the graph embeddings; for TGN (3). Lnop denotes the number of neighbor hops that
node aggregate information from; for our Temp-G*NTK, based on Section 4 and Appendix A L

---

Table 1: Total Runtime Complexity of Computing Similarity for Pairs of Graphs at Timestamp t.
METHOD
RUNTIME COMPLEXITY
WL-SUBTREE 42
O(nh) EI Fa O(1IVI")
SHORTEST PATH
RANDOM WALK 46
O
GRAPH2VEC 33
V(n'VVIDD B
NETLSD 45
((n K (VD)
GL2VEC
+ + Db) B
GRAPHMIXER 8
(n + KV) B
TGN
30
O(n" + Toop)
TEMP- G NTN (OURS)
On E))
represents the number BLOCK operations; and B denotes the number training epochs for all neural representation learning algorithms.
Notably, our method Temp-G*NTV falls into the category of graph kernels, and its computational
Also, compared with graph neural representation methods (6] the computation iteration of Temp-GG HHappGGNNKKK does not rely on neural computation like gradient descent and backpropagation, such that the empirical execution time of our method is still faster. Moreover, we further demonstrate our Temp-G'NTK" efficiency by providing empirical runtime comparison in Table 3 and the detailed empirical effectiveness comparison of these methods shown in the next section.
complexity is cheaper than 5 46
33 45 39
Experiments
In this section, demonstrate the performance of Temp-G"NTK by crucial tasks of temporal graph learning. More extra experiments about ablation study, parameter analysis, and robustness can be referred to Appendix
6.1 Graph-Level Experiments
Datasets.
Targeting temporal graph classification, we conduct experiments on one the most advanced temporal graph benchmarks that have graph-level labels, i.e., TUDataset (32, the four datasets are INFECTIOUS, DBLP, FACEBOOK, and TUMBLR, the detailed dataset statisties can also be found in Appendix G.I Additionally, we also leveraged the more large-scale temporal datasets REDDIT, WIKIPEDIA, LASTEM, and MOOC from [25 6 Those datasets are large but do not have graph-level labels, we use them to demonstrate the scalability of Temp-G*NTK on temporal graph similarity measurement. The detailed dataset statistics can found in Appendix G. and corresponding experimental results can be found in Appendix F3 Below, focus on introducing
temporal graph classification experiments and findings.
Problem Setting. For each dataset above, we evaluate the temporal graph classification accuracy by conducting 5-fold cross- validation and then report the mean and standard deviation of test accuracy. To be specific, given dataset of temporal graphs [G1, G2, .... G, } and their labels (11, V2, ... Vn. }. and in all four datasets, label y: of the temporal graph G, already time-aware, which means the value does not change with respect to time. Also, edge features are not provided in these four datasets, and we apply the Temp-G"NTK formula with plain time encoding as stated Eq.
We compare NTNK-G with a range of graph classification algorithms: (1) Graph Kernels, including WL-Subtree Kernel [42], Random Walk Kernel [46), and Shortest-Path Kernel [5]
Baselines.
(2) Graph Representation Learning methods, including Graph2Vec [33], NetLSD 45), GL2Vec 6
and (3) Temporal Graph Representation Learning algorithms, including TGN (3) GraphMixer
EvolveGCN 35 Details about the implementation and parameters of each algorithm are deferred to
Appendix G
httpe://chremrrs. /itpghi...//aaaatttt//////aaaaae
https://snap... stanford, sttnn///o wtw.ssto....dddd//ddeeeee.e...e. edu/jodie/
7

---

Table 2: Comparison of Temporal Graph Classification Accuracy.
METHOD
INFECTIOUS
DBLP
FACEBOOK
TUMBLR
"U--SUBTREE 42
0.600 = 0.044
0.520 + 0.068
0,650 + 0.075
0.570 + 0.121
SHORTEST PATH 5
0,670 = 0.075
0.560 = 0.049
0.560 = 0.086
0.580 = 0.143
RANDOM WALK 46
0.670 = 0.073
0.530 = 0.058
0.590 + 0.093
0.580 + 0.112
GRAPH2VEC
33
0.565 + 0.081
0.539 + 0.031
0.538 + 0.028
0.547 + 0.071
NETLSD 45
0.625 + 0.061
0.558 + 0.035
0.535 + 0.011
0.552 + 0.046
GL2VEC
0.545 + 0.051
0.562 + 0.030
0.538 + 0.031
0.558 0.080
GRAPHMIXER 8
0,500 + 0.000
0.563 + 0.011
0.561 + 0.023
0.509 + 0.508
TGN (3]
0,520 = 0.019
0,580 = 0.003
0.559 + 0.018
0.517 = 0.025
EVOLVEGCN
35
0.521 = 0.093
0,400 = 0.089
0,516 + 0.075
0.395 + 0.089
TEMP-G*NTK (OURS)
0.740 + 0.058
0.600 1 0.063
0.700 + 0.138
0.630 + 0.068
Results. The graph classification results are shown in Table and the best test accuracy is highlighted in bold. Our method, Temp-G'NTK, NTK, outperforms the other methods on all four datasets. In particular, the most notable gap between Temp-GPNTK and the other methods lies in the FACEBOOK dataset, where Temp- Sarp--Gh NTK gains 70% accuracy. In addition, as the label for each graph remains unchanged, we evaluate the performance of baseline algorithms on different timestamps until the end of the temporal graph, and report their highest accuracy score in Table 2
We also provide better illustration of how baseline algorithms perform at different timestamps of the INFECTIOUS and FACEBOOK datasets through Figure For Figure | as stated in our problem setting, each temporal graph is associated with label, and the label is fixed across timestamps. Therefore, we expect our method to perform well, i.e., achieve a competitive accuracy score across all timestamps. As illustrated, Figure 1 shows that Temp-G*NTK performs robustly across all timestamps and achieves the highest accuracy at most times, which also recalls the convergence ability of Temp- NTK as proved in Section 5.3
TEMP G trx lcual
Random Walk craphivee
Net.DD
Crechituer
GLeVec
TOR
Sherlest Palt
0.70
0.65
0.4
0.00
0.5
0.55
02
0.0
0.-
0.-
1.5
2/5
125
infectious
facebook
Figure 1: Comparison of test accuracy with respect to different stages of temporal graphs from the INFECTIOUS and FACEBOOK datasets. The y-axis in each plot is the accuracy, and the 2-axis represents what percentage of timestamps have been taken into account. For example, at x = 1/5, the accuracy obtained by performing classification on the first 1/5 timestamps of each graph.
we present the runtime comparison for four datasets, INFECTIOUS, DBLP, FACEBOOK, and TUMBLR. Overall, the empirical running time aligns with our theoretical analysis of time complexity in Table That is, our method belongs to the graph kernel category, where the node-wise comparison is usually inevitable, and time complexity is lower. Compared to the neural baselines, since our method does not rely on complex neural training like gradient descent and backpropagation, method is still efficient.
Further, in Table 3
Given our method achieved the best classification accuracy, as shown Table according to the corresponding running time reported in Table 3 our method is (1) more than 10x 20x faster then
complex temporal graph neural network methods like GraphMixer [ and TGN [39]: ; (2) similarly
efficient simple kernel methods like WL-Subtree [42] and Shortest Path 5 and embedding
8

---

Table 3: Runtime of Baselines for Each Dataset in Seconds
METHOD
INFECTIOUS
DBLP
FACEBOOK
TUMBLR
WL-SUBTREE
16.04
10.93
13.88
9.80
SHORTEST PATH
20.36
16.13
32.29
16.29
RANDOM WALK
489.65
566.64
5380.26
972.929
GRAPH2VEC
3.43
3.45
3.87
3.42
NETLSD
14.82
15.20
33.90
15.06
GL2VEC
17.75
14.36
23.95
13.77
GRAPHMIXER
217.70
537.22
720.16
219.29
TGN
254.59
873.03
1101.66
394.34
TEMP-G'NTK (OURS)
23.04
21.00
25.86
21.04
methods like NetLSD 45] and GL2Vec [6:; and only Graph2Vec method, but our performance is roughly 1.4x better.
33 is rumning faster than our
6.2 Node-Level Experiments
In this section, we evaluate the performance of Temp-G*NTK for the temporal node property prediction task. Specifically, we leverage the final node-pairwise kernel matrix computed by Eq. [I i... (4), and obtain node predictions by performing kernel regression with (L))
Datasets. We demonstrate Temp-G'NTK's capability of performing dynamic node prediction on the tran-trade dataset from the Temporal Graph Learning Benchmark (TGB) [17], and the details of TGB can be found at this link 7 The training, validation, and test sets of tgbn-trade are defined in the TGB package with 70% 1115 15% chronological splits. To assess the performance of method igbn-trade, we use the normalized discounted cumulative gain (NDCG) metric that is assigned to tgbn-trade in the TGB package.
Problem Setting. Given a temporal graph with node labels that change with respect to time, the Node Property Prediction task requires the prediction of labels of some nodes certain time t, given that our predictor can leverage all information about the temporal graphs from the initial timestamps up to certain timestamp f with & < t. To be specific, the predictor for node labels by using Temp-G"NTK at time t would be:
e (G (e (G " 'y(()
(17)
where y() E Rexdiiaa is a whose ,th entry is the label of node time I, and diabet the dimension of node labels.
Through the lens of kernel regression, [@ (e( (GL), GO) acts the gram matrix, similar to the role the kernel values between the test and training NTK for node property prediction, we perform kernel regression with C-SVM and employ (L) as the pre-computed kernel. The regularization parameter, C, of our SVM predictor is searched over 120 values evenly sampled from the interval [10-2 10 in log scale. The number of BLOCK operations, L,, is searched over (1, 2, 3). and we obtain the best NDCG score with =
of Ktroin in Eq. 13 and (G(()) g()) samples. In order to effectively utilize Temp-G* (eNK-G"NTK--
Baselines. We compare Temp-G NTK with deep learning algorithms on the igbn-trade's leaderboard, which include TGN (39], DyRep 44 and DyGFormer [49]. TGN (39 is discussed in the temporal is a deep temporal point process model, which is parameterized by temporal-ane cemporal-attentive representation network encoding time evolving struetural information into node representations. DyGFormer
graph classification task. DyRep 44
49 is a Transformer-baat based architecture for dynamic graph learning, which learns from nodes" historical first-hop interactions by the neighbor co-occurrence sampling and patching scheme with the Transformer neural architecture.
With selected temporal graph representation learning baseline methods, we then report the NDCG scores of baseline algorithms based on tgbn-trade's leaderboard.
Results. The results for temporal node property prediction on tgbn-trade are shown in Table 4 and the best NDCG score is highlighted in bold. Temp-G'NTH achieves very competitive results, with
hattps://tgh httpss///gbb.ommllxtttaabbb complexdaaallllleeeooccmocc wwwpp//waaaatl.l..cocooo////eeee con/tocssnooeerrp//

---

Table 4: NDCG Score for Node Property Prediction on the tgbn-trade Dataset.
METHOD
VALIDATION
TEST
DYGFORMER [49
0.408 + 0.006
0.388 + 0.006
TGN 39
0.395 + 0.002
0.374 + 0.001
DYREP
0.394 + 0.001
0.374 + 0.001
TEMP- NTK (OURS)
0.397 = 0.039
0.380 + 0.008
the test NDCG score of 0.380, outperforming TGN and DyRep and approaching DyGFormer very closely, despite that baselines rely on heavy graph neural architectures like graph neural network or graph transformer. These results show that Temp-G9NTIH has the potential to extend to the temporal node property prediction task and capture node-level information.
7 Related Work
Graph neural representation learning attracts many research interests and serves for many interesting
tasks like recommendation 36 37], time series forecasting [5], and social network analy- sis [28 14 27]. In which research domain, many efforts have been devoted to develop non-neural computations and temporal settings. Graph Neural Tangent Kernel. Graph Neural Tangent Kernel (GNTK) [9] introduces a class of graph kernels that corresponds to infinite-width GNNs with sum neighborhood aggregator, Building upon the foundations of GNTK, a line of works unveil different theoretical aspects of GNTK. For example, (20 improves the computation time of constructing the gram matrix GNTK; (18] studies the behavior of GNTK that aligns with GNNs with large depth; and most relevant to our theoretical results (Theorem (.44. 24 combines GNTK with the concept of graphons to derive the Graphon Neural Tangent Kernel. Graphons, Graphon Neural Network, and Graphon Neural Tangent Kernel. A graphon is symmetrie, bounded, and measurable function W [0, 1]2 + [0. 1] that acts as the limit object of dense graph sequences and defines a family of similar graphs. Similarly, Graphon Neural Networks (WNNs) 4I] are proven to be the limit object of GNNs that operates on a sequence of graphs as the graph's ' size grows. Graphon Neural Tangent Kernel (WNTK) 24 defines the NTK that resonates with the indinite-width WNNs and proves that the GNTK converges to the corresponding WNTK as the size of the graph grows. Temporal Graph Learning. Most temporal graph learning methods are comprised of complex architectures that leverage the message passing framework. a time encoding function that captures time repre- sentation and distinguishes different timestamps. Some works also employ recurrent architecture to capture past information and update the node or edge representation at a current time based on representations of previous time where update the history representation of at time f. TGAT [47] utilizes the self-attenion mechanism
f.. For example, JODIE (25) employs RNN to
(SAM) to compute the temporal representation of node c. TGN [39 employs recurrent architecture to capture the history representation of (t) (similar JODIE (25) and then performs neighborhood aggregation to obtain the temporal node representation
at time f, which is similar to TGAT (77. GraphMixer [8] first constructs edge representation by aggregating raw edge features and then con- catenates them with relative difference time encoding. Then, the temporal node representation is determined by aggregating the aforementioned edge representation, (t). The node representation is further transformed by MLP and Mixer MaM layers. For a more comprehensive comparison between Somp--G&NTK and previous recurrent neural network works on Temporal Graph Learning, we refer readers to Appendix E. where we provide detailed illustration of more Temporal Graph Learning methods, DGNN 31
EvolveGCN 33). ROLAND 48. and SSGNN 7
Conclusion
In this paper, we study the graph neural tangent kernel within the temporal graph setting and propose a temporal graph neural tangent kernel named Temp-G2NTH which allows the input graph structure and node features to evolve over time and output the pairwise similarity. The proposed Temp- G enjoys the computational efficiency. expressive representation ability of temporal graph neural networks, and rigorous error bound. Moreover, the proposed TeTT-G also follows the graphon convergence property. Empirically, we not only test Temp-G in the temporal graph-level experiments and demonstrate its superior accuracy but also extend it to deal with temporal node-level tasks, where NTTK also shows competitive performance.
10

---

Acknowledgements
This work is supported by National Science Foundation under Award No. IIS-2117902, the U.S. Department of Homeland Security under Grant Award Number 17STQAC0000| -00-001, MIT-IBM Watson AI Lab, and IBM-IIlinois Discovery Accelerator Institute new model of an academic- industry partnership designed to increase access technology education and skill development to spur breakthroughs in emerging areas of technology. The views and conclusions are those of the authors and should not be interpreted representing the official policies of the funding agencies or the government.
References
[1] Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 1139-81483 2019.
[2] Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 322-332. PMLR, 2019.
[3] Yikun Ban, Yuchen Yan, Arindam Banerjee, and Jingrui He. Ee-net: Exploitation-explraattt neural networks in contextual bandits. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
[4] Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities Risk bounds and structural results. J. Mach. Learn. Res., 3:463-482, 2002.
(5) Karsten M. Borgwardt and Hans-Peter Kriegel. Shortest-path kernels on graphs. In Proceedings of the Sth IEEE International Conference on Data Mining (ICDM 2005), 27-30 November 2005, Houston, Texas, USA, pages 74-81. IEEE Computer Society, 2005.
[6] Hong Chen and Hisashi Koga. Gl2vec: Graph embedding enriched by line graphs with edge features. In Tom Gedeon, Kok Wai Wong, and Minho Lee, editors, Neural Information Processing 26th International Conference, ICONIP 2019, Sydney, NSW, Australia, December 12-15, 2019, Proceedings, Part III, volume 11955 of Lecture Notes in Computer Science, pages 3-14. Springer, 2019.
[7] Andrea Cini, Ivan Marisca, Filippo Maria Bianchi, and Cesare Alippi. Scalable spatiotem- poral graph neural networks. Brian Williams, Yiling Chen, and Jennifer Neville, editors, Shirty-Seventh AAAI Conference Artificial Intelligence, AAAI 2023, Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence, IAAI 2023. Thirteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2023, Washington, DC, USA, February 7-14, 2023, pages 7218-7226. AAAI Press, 2023.
[8] Weilin Cong, Si Zhang, Jian Kang, Baichuan Yuan, Hao Wu, Xin Zhou, Hanghang Tong, and Mehrdad Mahdavi. Do we really need complicated model architectures for temporal networks? In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net. 2023.
[9] Simon S. Du, Kangcheng Hou, Ruslan Salakhutdinov, Barnabás Póczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc Buc, Emily B. Fox, and Roman Gamett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8- 14, 2019, Vancouver, BC, Canada, pages 5724-5734 2019.

---

[10] Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov. editors, Proceedings of the 36th International Conference on Machine Learning, ICMI. 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 1675-1685. PMLR, 2019.
[11] Simon S. Du, Xiyu Zhai, Barnabás Póczos, and Aarti Singh. Gradient descent provably optimizes aver-parameterized neural networks. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[12] Dongqi Fu, Liri Fang, Ross Maciejewski, Vetle I. Torvik, and Jingrui He. Meta-learned metrics over multi-vvolution temporal graphs. In Aidong Zhang and Huzefa Rangwala, editors, KDD '22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 14 18, 2022, pages 367-377. ACM, 2022.
[13] Dongqi Fu. Zhigang Hua, Yan Xie, Jin Fang, Si Zhang, Kaan Sancak, Hao Wu, Andrey Malevich, Jingrui He, and Bo Long. Ver-graphormer: A mini-batch graph transformer via virtual connections. CoRR, abs/2403.16030, 2024.
[14] Dongqi Fu, Dawei Zhou, Ross Maciejewski, Arie Croitoru, Mareus Boyd, and Jingrui He. Fairness-aware clique-preed preeuurigrseriigggg spectral clustering of temporal graphs. In Proceedings of the ACM Web Conference 2023, WWW 2023, Austin, TX, USA, 30 April 2023 - 4 May 2023, pages 3755-3765. ACM, 2023.
[15] Dongqi Fu, Yada Zhu, Hanghang Tong, Kommy Weldemariam, Onkar Bhardwaj, and Jingrui He. Generating fine-grate fine-grained causality climate time series data for forecasting and anomaly detection. CoRR, abs/2408.0422. 044544, 2024.
[16] Xiaoxin He. Bryan Hooi, Thomas Laurent, Adam Perold, Yann LeCun, and Xavier Bresson. A generalization of vit/mlp-mixer to graphs. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 12724-12745. PMLR, 2023.
[17] Shenyang Huang, Farimah Poursafaei, Jacob Danovitch, Matthias Fey, Weihua Hu, Emanuele Rossi, Jure Leskovec, Michael Bronstein, Guillaume Rabusseau, and Reihaneh Rabbany. Tempo- ral graph benchmark for machine learning on temporal graphs. Advances in Neural Information Processing Systems, 2023.
[18] Wei Huang. Yayong Li, Weitao Du, Richard Y. D. Xu, Jie Yin, Ling Chen, and Miao Zhang. Towards deepening graph neural networks: gatk-based optimization perspective. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
[19] Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernel: Convergence and generalization in neural networks. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Anmual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 8580 8589, 2018.
[20] Shunhua Jiang, Yunze Man, Zhao Song. Zheng Yu, and Danyang Zhuo Fast graph neural tangent kernel via kronecker sketching. In Thirty-Sixth Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Phirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22- - March 1, 2022, pages 7033-7041. AAAI Press, 2022.
[21] Wei Ju, Siyu Yi, Yifan Wang, Zhiping Xiao, Zhengyang Mao, Hourun Li, Yiyang Gu, Yifang Qin, Nan Yin, Senzhang Wang, Xinwang Liu, Xiao Luo, Philip S. Yu, and Ming Zhang. A survey of graph neural networks in real world: Imbalance, noise, privacy and OOD challenges. CoRR, 055/2243.04445. 2024.
[22] Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth, and Pascal Poupart. Representation learning for dynamic graphs: survey. J. Mach. Learn. Res., 21:70:1-70:73, 2020.
12

---

[23] Nils M. Kriege, Fredrik D. Johansson, and Christopher Morris. A survey on graph kemels.. Appl. Netw: Sci., 5(1):6, 2020.
[24] Sanjukta Krishnagopal and Luana Ruiz. Graph neural tangent kernel: Convergence on large graphs. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 17827-17841, PMLR, 2023.
[25] Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal interaction networks. In Ankur Teredesai, Vipin Kumar, Ying Li, Rómer Rosales, Evi- maria Terzi, and George Karypis, editors, Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pages 1269-1278. ACM, 2019.
[26] Vitaly Kuznetsov and Mehryar Mohri. Time series prediction and online learning, In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, Proceedings of the 29th Conference on Learning Theory. COLT 2016, New York, USA, June 23-26, 2016, volume 49 of JMLR Workshop and Conference Proceedings, pages 1190-1213 1213. JMLR.org, 2016.
[27] Zihao Li, Dongqi Fu, and Jingrui He. Everything evolves in personalized pagerank. In Ying Ding, Jie Tang. Juan F. Sequeda, Lora Aroyo, Carlos Castillo, and Geert-Jan Houben, editors, Proceedings of the ACM Web Conference 2023, WWW 2023, Austin, TX, USA, 30 April 2023- 4 May 2023, pages 3342-3352. ACM, 2023.
[28] Xiao Lin, Jian Kang, Weilin Cong, and Hanghang Tong. Bemap: Balanced message passing for fair graph neural network. Learning on Graphs Conference, pages 37-1. PMLR, 2024.
[29] Xiao Lin, Zhining Liu, Dongqi Fu, Ruizhong Qiu, and Hanghang Tong. Backtime: Backdoor attacks on multivariate time series forecasting. arXiv preprint arXiv:2410.02195. 2024.
[30] Antonio Longa, Veronica Lachi, Gabriele Santin, Monica Bianchini, Bruno Lepri, Pictro Lio, Franco Scarselli, and Andrea Passerini. Graph neural networks for temporal graphs: State of the art, open challenges, and opportunities. Trans. Mach. Learn. Res., 2023, 2023.
[31] Yao Ma, Ziyi Guo, Zhaochun Ren, Jiliang Tang, and Dawei Yin. Streaming graph neural networks. In Jimmy X. Huang, Yi Chang, Xueqi Cheng, Jaap Kamps, Vanessa Murdock, Ji-Rong Wen, and Yiqun Liu, editors, Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, SIGIR 2020, Virtual Event, China, July 25-30, 2020, pages 719-728. ACM, 2020.
[32] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. CoRR, 0bs/2007.08666 2020.
[33] Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal. graph2vec: Learning distributed representations of graphs. CoRR, 2017.
[34] Giannis Nikolentzos, Giannis Siglidis, and Michalis Vazirgiannis. Graph kernels: A survey. J. Artif. Intell. Res., 72:943-1027, 2021.
[35] Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kaneza- shi, Tim Kaler, Tao B. Schardl, and Charles E. Leiserson. Evolvegen: Evolving graph con- volutional networks for dynamic graphs. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty- -Scroy Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 5363-5370. AAAI Press, 2020.
[36] Yunzhe Qi, Yikun Ban, and Jingrui He. Neural bandit with arm group graph. In Aidong Zhang and Huzefa Rangwala, editors, KDD '22: The 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, Washington, DC, USA, August 14 18, 2022, pages 1379-1389. ACM, 2022.
13

---

[37] Yunzhe Qi, Yikun Ban, and Jingrui He. Graph neural bandits. In Ambuj K. Singh, Yizhou Sun, Leman Akoglu, Dimitrios Gunopulos. Xifeng Yan, Ravi Kumar, Fatma Ozcan, and Jieping Ye. editors, Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023, Long Beach, CA, USA, August 6- 6-10, 2023, pages 1920-1931. ACM, 2023.
[38] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning via sequential complexities. J. Mach. Learn. Res., 16:155-186, 2015.
[39] Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard. Federico Monti, and Michael M. Bronstein. Temporal graph networks for deep learning dynamic graphs. CoRR, abs/2006. 10637, 2020.
[40] Benedek Rozemberezki, Oliver Kiss, and Rik Sarkar. Karate Club: source Python Framework for Unsupervised Learning on Graphs. In Proceedings of the 29th ACM International Conference on Information and Knowledge Management (CIKM '20), page 3125-3132. ACM, 2020.
An API Oriented Open-
[41] Luana Ruiz, Luiz F. O. Chamon, and Alejandro Ribeiro. Graphon neural networks and the transferability of graph neural networks. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tiew Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[42] Nino Shervashidze, Pascal Schweitzer, Erik Jan Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-lehman graph kernels. J. Mach. Learn. Res., 12:2539-2561 2011.
[43] Giannis Siglidis, Giannis Nikolentzos, Stratis Limnios, Christos Giatsidis, Konstantinos Skianis, and Michalis Vazirgiannis. Grakel: A graph kernel library in python. Journal of Machine Learning Research, 21(54):1-5, 2020.
[44] Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha. Dyrep: Learning representations over dynamic graphs. In 7th International Conference on Learning Representa- tions, ICLR 2019, New Orleans, LA,, USA, May 6-9, 2019. OpenReview.net, 2019.
[45] Anton Tsitsulin, Davide Mottin, Panagiotis Karras, Alexander M. Bronstein, and Emmanuel Müller. Netlsd: Hearing the shape of graph. In Yike Guo and Faisal Farooq, editors, Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018, pages 2347-2356. ACM, 2018.
[46] S. V. N. Vishwanathan, Karsten M. Borgwardt, Imre Risi Kondor, and Nicol N. Schraudolph. Graph kernels. CoRR, fbbs/0807.0093, 2008.
[47] Da Xu, Chuanwei Ruan, Evren Körpeoglu, Sushant Kumar, and Kannan Achan. Inductive representation learning on temporal graphs. In 8th International Conference on Learning Representations, ICIR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[48] Jiaxuan You, Tianyu Du, and Jure Leskovec. ROLAND: graph learning framework for dynamic graphs. In Aidong Zhang and Huzefa Rangwala, editors, KDD '22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Washington, DC, USA, August 14 18, 2022, pages
ACM, 2022.
[49] Le Yu. Leilei Sun, Bowen Du, and Weifeng Lv. Towards better dynamic graph learning: New architecture and unified library. CoRR, abs/2303.13047, 2023.
[50] Dawei Zhou, Lecheng Zheng, Dongqi Fu, Jiawei Han, and Jingrui He. Mentorgnn: Deriving curriculum for pre-training gnns. In Mohammad Al Hasan and Li Xiong, editors, Proceedings of the 31st ACM International Conference on Information Knowledge Management, Atlanta, GA, USA, October 17-21, 2022, pages 2721-2731 ACM, 2022.
[51] Hongkuan Zhou, Da Zheng, Israt Nisa, Vasileios loannidis, Xiang Song, and George Karypis. TGL: A general framework for temporal GNN training on billion-scal scale graphs. CoRR, abs/2203.1488 2022.
14

---

A
Pseudo Code of NTT
The pseudo-code of Temp-G"NTK provided below.
Algorithm 1 Pscudo-code for computing Temp-G"NTK value between G, G" at time
Input: node embeddings of G, G' at time t: h(t), ht);;; number of BLOCK operations L. Output: Temp-G"NTK value between G, at time t: K
1: K =
2: for V(t) do
3:
for u' E V'( do
4:
u,a f (t) hh (t); (
5:
u, + (t(() T h (t):
6:
for / E [1, Li do
(D ())
(1)
arrccoss
7:
",a""
2 )
8:
O a.a'
2x 11!l! (11-1)
(1)
O (1-1) uww
9:
10: end for
11: end for
end for
13:
for
E (1) do
14:
for n' V*( do
15:
K + K + o n,u
16: end for
end for
B Theoretical proof for Kernel Properties of Temp-GoNTK
Here, we present the full proof for Theorem 5.1 and Theorem 5.2
Proof. For Theorem 5.1
5.1 we aim to prove that ((G())G"()) = K(G ((O)).
Given our proposed kernel function, K(G()) ()()) Evev()) EveV (G0), )or) we first write down another equation, where the internal order is flipped, ie.. K(G'(), ((!)) Evevr Evev()) (L)(())) (())) Dr'
first prove that
C (4 (G((t) (*(()) you! (C 11 1.1SI1
15

---

> For = 1, we have
θ ((G((),(())))) e (G G yov' E td) (Ct0, )ot))) + (
π - arccos [ (Gtt, )our)
= (bb((t) (o.(t)"n,((
h. (t))
2m
arccos ( C )oo')
(1)) (GW), G'
2x
2x
(L) hy (1)) (h, hw (t))
π arccos hew (t))
/1 - (h) tow (t))²
2x
2R
2x
(1) T (()) π - arccos( (1) (h)()))))))
ा arccos (1) kn)
vI (h (1) (1))
2x
2x
2x
= (t) (t)(t)) π arccos (0)0 (1)) (G"(t, Doro)
2n
arccos Σ ( (G'(), (()) V1 ( (G'()) 2
2x
(G (()) (1)) (G (()) + E )ov θ ( (Gt(t) ((0))²)
(2)
Suppose 3k E N,15ks < L, such that ( (C (((")))()))on )or (K)(( (())
Thus,
+ (C+)) ((()))))))))..). you' (()( )"(l))o! E ((++1) (G(1), Gt10) ((())) )ol0)
(C(0,,"))) Joy' π. - arcoos Σ (G(), )ow())
(b)) GO(d)
2x
+ arccos Σ (k) (G )or)
(²) (G(t, G((t))
2x
2x
θ (k) (G ,,(() Do' (())))))) arccos D (k) (G'lt), (((t))
2x
V1 (()) (G'()) G
π arccos ( (k) (G'(), G()))o)))
+
2T @ (G()),G(1)
2
Therefore, if @ (k)) (GL), Go10) )oo
(k) (G G(O) y'' then @(++)(((()) GO()) mm
O ((+())(G(() erre Moreover, we have proven that @ (1) (G )o))))) = ( (G((((()) (t) (
Thus, by induction, we have:
e 19 (G()), (((t) You' 2 ( ((t) )or, 11, S1S T..
Finally,
((G()))(())= = Σ Σ (6(1), (000)
Σ
Σ
).)) (I,
('EV
V'EV'(() vEV(t)
The proof for Theorem 5.1 is completed.
Next, we elaborate on the proof for Theorem 5.2 To be specific, we prepared options to demonstrate the proof.
Option #1:
16

---

Proof. In order to prove that Temp-Gr NTNK is positive semi-definice we need to prove the following statement. Given n temporal graphs G....., G, and any .I.....co Co R then
" n
ΣΣ i=1j=1
) 20
(18)
Intuitively, we can view the right-hand side of Eq matrix,
18 as the summation of all entries of the following
GG G(t) 02cK( G
(GrK(G G(
2202k( G2)
k G(l)
K
E R
(19)
K G(D)
C (
G.cK(G (
whose (i entry is Gaj ( G.
Then, can re-write Eq. 18 by Temp- GTTK's formula stated in Eq. 12 follows
m2
ΣΣ cit Geck K(G G. = ΣΣΣΣ GO
(4) " (
(20)
where m; is the number of nodes of G2, Vi (1......m).
Next, we consider the graph G U U U...!!!!!! whose vertex, edge is the union of all G vertex, edge set (Vi n.), respectively. Then the number of nodes of G UG2 U...
Σm= my Additionally, we re-index the nodes ((O)) U Gft) U... G(tt as follows. The 5th node of graph G(") is the (Ea mp)
+ j)th node of G U (t) U...U ((t) Then,
my
Σ
Ge,
Gcj + (L)
(G )or )
(21)
m
m
agd
(L) (Gf)) UG! UC. c uG! u.....G!))
)o 20
20
where a, a if E my < S pp11 m, for (i 2 1), and if m, then a, C1- Intuitively, the right-hand side of Eq.
21 is the summation of all entries of the following matrix O:
crc (L) (G())
02 o ( G(l))
(G()) G(
e
(1) ( G()
O (L)
(c
Cgci
O
E R m
(t) (())
(
c((
Gne,
(22)
whose (h entry an m, m, matrix c.e, ( G((") and O (C G(tt) is the kernel
matrix defined iteratively via Eq. 11 for all pair of nodes from G and G( We can regard O (defined in Eq. 22 the "node-view" expansion of K in Eq. 19
As 01, 01..... Om R. and e (4) is the kernel matrix constructed feature vector of each pair of nodes of G U...U..UU (()) so the last inequality in Eq. 21 holds, as (L) is positive semi-definite on the space of node features vector [19].
17

---

Finally, we conclude that
city KeyKKG (,)
(23)
m
a. 0 (4) uG! u....u of uc! U...U )
... No 20
Therefore, the proof for Theorem 5.2 is completed.
> Option #2:
Proof. In order prove that Temp-G*NTK is positive semi-definite, we need prove the following statement. Given n temporal graphs Gi,...; Gn and any Cl.-..,Cr E R then
Cn.
C.2y k ,
(24)
j1j=1
We re-write Eq. 24 as follows
C.t. K
, &oakiaff ..())
G), (CC,CCCHHCCCCCC,C))))C++))CCCCC
Gc KG kc) = ΣΣ --GG
=1
Σ
GO K(G (0) , = 2n. Σ (-2))
- - GKKGG (K())
+ Ge, (o ". +ooK(o)) o(9)
F1
Next, we aim to prove that (1) for each i.j E nI,
ΣΣ
c.))) 20 (25)
=1
by proving that for each i, E [1....,m}
k ,. + ( ,( + ae K(G + "c,") 20
and (2) for each E nI.
18

---

a KG ,0.0) 2 0
2n
(26)
1=1
by proving that for each E nI......).
(-G)) ) 20
> For proving (1):
For each j, E [L....,n] suppose that Gi Gj have p, nodes, respectively, then we have the following equality
&KIG (0)
) + &KGK ) t toekKc )
ov +
(G)) )ort
=====
49 Σ
LL) (G ( De + cjc Σ
( (G G
==lv=1
o==1==
p+g
and θ (1) (G! UG (t) c u _o!/) Joo 20
Here, we can regard G U of graph, whose vertex, edge set is the union of G( vertex, edge set and G s vertex, edge set, respectively, while au d' is either e; cj. Therefore, since a1.... Uptg E R. and (c u c UGG"))er v' {I,..., (p + 4)} is equivalent to constructing kernel matrix the (p + q) node feature vectors of G( UG so the last inequality holds, as (L) is positive semi-definite on the space of node features vector 19 Therefore, we can infer that
n ΣΣ<
2 ( + tao, +ocKK)) ,..0) 2 0 (27)
D For proving (2):
Next, for each i, suppose G2 has k nodes then
& θ (G. ,.
& vv
(- (()))
b, θ (G()) (
voo 2 0
11=1
v=l==1
(28)
where bj .... by = (-c2).
As bi...., by E R. and e (L) (C!!) ((0)) )ov') Ve, v' E [I,...,k) ., is equivalent to the wair-wise kernel matrix constructed on the set of node features of G, so the inequality holds, due to the positive
semi-definite on the node feature space property of (1) 19 This results
2n
(G ,. 2 0
(29)
From Eq. 29 and Eq.
27 we now have
19

---

1
2
2 2n
2
G9 Ge k
Σ
(-)))
j=1
K .. + 2 tocK("" + 2
j=1
KocK .c))))
Therefore, the proof for Theorem 5.2 is now completed.
C Genralization Bound of G.NK
In this section, we provide the full proof for Theorem 5.3 We first provide some background
knowledge on the Sequential Rademacher Complexity measures 38 26], and then we derive the full proof of Theorem 5.3
C.1 Preliminaries
In our Temporal Graph Classification setting, given temporal G and its label y, if we want to make predictions about G at time then we apply our predictor on the snapshot Gt i.e., we leverage all information previous timestamps (f < t).
Suppose that has T unique timestamps .1....,,7 lr, then we can obtain snapshots G Gr, where G, G(t+,, Therefore, we can re-formulate our setting as follows: we consider general time series prediction, where the predictor receives realization (G1,,1),... (GT, (r)) generated by some stochastic processes.
To simplify notations, we let f be the regression kernel predictor, i.e., fkernel- The objective of our predictor ʃ is, any timestamp 4, achieving small error (Gi-1,4-1))) (G.,..,,,,,,,,, E[C[S((G) 44), v)](( ()),)) 41), function 8 IR IR R.
conditioned on previous snapshots, given loss
Z and let the family function G {[(G,, t(), y) + [(f((G,,,t) ((),,,,),))) contain such functions g. We assume bounded, a- L-Lisschitz loss function, that is g( Z) E [0. for any Z E Z. Finally, we use Z to denote the sequences Za, Za+t,..., Zo. where Z, = (G,,44))))
For shorter notation, we let g( = (t)((G,,,)..v)) for Z = ((G,,
In order to derive the Sequential Rademacher Complexity, we first introduce the definition of complete binary tree.
We adopt the following definition of a complete binary tree from 38 26 a --vuledd complete
binary tree z is sequence of (21....,zy) of T mappings, where { 1-1 + Z. A path in the tree is a = (o1,...,
To simplify the notation, we write
(, = 01-1).
Next, we introduce how to sample sequential data Zi...,, Z; using the aforementioned binary tree. We adopt the sampling process from [38 26 as follows: given a stochastic process distributed to the distribution P with P; (.(.
denoting the conditional distribution based on ø1. 24-1, we sample a Z x Z based on the following procedure. We start by drawing two independent samples Z, Zi from P,, then, in the left child of the root we sample Zz, Z22 P2 (2( and in the right child of the root, we sample 7z, 7/2 ~ (2)))
More generally, for node that be reached by path (01, (01,..., 0-11), (0,-0;;1), where the indicator (1(1) = Z, 1-1-) = Zz. In this manner, we derive the Sequential Rademacher Complexity of a function class & that acts on is defined as follows [88
draw Z,, 7
T (9, = sup gEG
Σ ((()(()))
(30)
T
i=1
20

---

where z is 2-lalued complete binary trees with depth T and or is sequence of Rademacher random variables.
As stated in Theorem 5.3
the key quantity of interest in our analysis is
T Σ
El, v)) ti).... (G, -
sup REc
2=1
and we can re-write this quantity follows and establish data-dependent bound for this term in Appendix C.2
sup
Big(Z.) g(Z))
(31)
gEG
T
For more details about the Sequential Complexity measure, we defer readers to 38 and 26
C.2 Detailed Proofs
We first bound Eq. 31 by the Sequential Rademacher complexity of F, the family function class contains functions such our kernel regression predictor, fkernels (Lemma C.I) then continue to bound the Sequential Rademacher complexity of by the data-dependent term (Lemma. C.2 Lemma C.1.
T
sup gEg
Σ
Eig (Z.
0- "1 o(Zi)
< 22 (F)
(32)
Proof. We first state that the following inequalities hold: - )] Z,, Z are indepedently drawn from (-(((ZZ))) )) and Eig(Z,) 7 = Eig(Z,) Z7], and g (Z,) only depends on Z Therefore. we obtain the following:
since
T
E
sup .EG
Big (2:))
( (Z)(Z))
((4))
T
EE
sup 9Eg
(o(Zz) ,(2)))17
T
i=1
< IE
sup
(g(2)) g(2.)))
9E9
Σ (g(Z)) - -
sup gEg
T
where the first inequality holds by using Jensen's inequality, and the last expectation is taken over all joint sequences Z Z
Since g(Z.) = ((((, 44,, y) and é a Lipschiit, thus we obtain the following:
(o(()) - -((z)))
E
sup BEG
(U((G) -(U(()
sup
EEC 1=1
(33)
sup o fET
(U(()) I((G),
=E
sup JEF
-(x)))
21

---

The first inequality holds, due to the fact that e is Liiiscchit..
where X; (G1,4); X (G²; 4)- Note that since y is fixed with respect (1 < T), so 74 = +X Therefore, we can derive at a v-valued complete binary tree x, x;(o), and the sequences X1 X" that are similar to the manner of deriving z, (i(o), Z z' respectively. Simply say, x when omitting the label y. Since the last expectation taken over all joint sequences X x so given Rademacher random variables, 01,-.., OT,
E
Σ ( fEJ
sup
E(sup
Σ fet
-x) s(xi))
Thus, we have:
T (f(x)) - -(x)))
sup
SEF 1=1
= E
sup
(f((())
JEF 1m1
o.(f(X)) - o s(x1))
Ex
E -.)
sup
SEF
Eg [()
sup SEF
a (J(x)) - -(xx))
Eg ((xxx')TTTP
sup SEF
axl[(x((( -(x(()))))(((())))
where x ~ T(P) denotes sampling a X' valued complete binary tree x with given stochastic process
P. Thus, Eq. 33
equivalent to:
aE
sup SEF
(F(X) - f(Xi))
T
aEg (xxx"xX
sup FEF
o.(f((((o)) f(xx(o))
T
I {x
(x,''
sup feF
oxf(x((o)) + sup Σ /EF
o ox(((((())
(34)
T Σ axf((((())
T
-
sup
+ (x
sup fEF
- orf((x
feF i=1
2al TohBBExTTii Bx
sup oxf(x((o)) SEF 1=1
-2aBxx-T@P
( x)
which completes the proof for Lemma
Next, we establish data-dependent bound for the Sequential Complexity measure Reeq Lemma C.2. Given n i.idd time series samples drawn from underlying stochastic processes P,
((X)), (), Mj }5)) Then
2 <
R
(F,x
x(1))
yd -iy tr(K(0))
(35)
77
n 1=1
22

---

where, x(i) is the binary tree corresponding to the time series XU), K is the n x n. kernel gram matrix, whose pq-th entry the Temp- NTK value of the thth snapshot of X(r) and the i-th snapshot of X (1),, and is the vector of labels, in which the j-th entry is [y]; Uj-
Proof.
T
gaee (F,
x
x11)
Σ Σ
sup
(x
71
fEF i=1
1=1
==1
T
(x = Σ (F,
sup FEF
n
j=1
where Rt, (F, is the empirical Rademacher complexity F with the i-th snapshot of n i.i.d
samples X ,,..,,'"' -..,,,, x Since F is function class of kernel regression function, as proven in 4
we can bound R. (F, as follows:
2 R S n
/ tr(K(())
which completes the proof for Lemma C.2
Thus, using the results Lemma
we can bound Eq. 34 as follows:
20 TT))
Ri (F,x) x)
20 2
Mt (xx(0))
j=1
2
2aE
yd ( tr(K(t)
T1
4
S assup
1 - tr(((())))))))
n
which completes the proof for Theorem 5.3
D Convergence to Graphon Neural Tangent Kernel
In this section, first provide some background knowledge on Graphons, Graphons Neural Net- works, and Graphons Neural Tangent Kernel, and then derive at the full proof for Theorem. 5.4
D.1 Preliminaries
We adopt the definition of Graphons, Graphons Neural Networks (WNN) 24 and Graphons Neural Tangent Kernel (WNTK) 24]. and then extend these concepts to the settings of CTDGs.
Graphons
Graphons defined as bounded, symmetric, measurable function W [0, [0, representing limits of sequences of dense graphs.
Given graph sequence {G,), where the i-th graph in the sequence G; has i nodes, let F = (V', E") be an undirected graph, then the graph sequence {G,, is said to converge to the graphon in the sense that
lim ((F, G.)) = ((F, W)) n0
(36)
where t(F, G.) hom(F, V.', where hom(F, G,)) is the number of homomorphisms be- tween F and G.,, and ((F, W) can be similarly defined.
Thus, (F,, G..) is the density homomorphisms between and G. We can think of as motifs such k-cycles, or & -ccliques, so if the graph sequence {Gn) converges to the graphon W, then
23

---

we can think of GI...., GT, of the graph sequence } belongs to graph family that has certain amount of density of homomorphisms from F, and that graph family is represented by W.
Therefore, the graphon W can be seen as a generative model for stochastic graphs. In order to use W generate graph G, (Vn, Fe.) with nodes, first map each node E V1 S i S n) the unit interval, i.c. [0, 1]. by uniformly sampling points uy (u, E [O, 1J), and the probability of nodes j.j are connected in G, W [u4, uz), hence we can regard W is weighted adjacency matrix for Gn.
Graphons Neural Network
Next, we would define a continuous message passing framework for graphon that corresponds to the neural architecture proposed in Section 3.1
Firstly, we introduce the definition of Graphon signals as follows: Graphon signals are function X : [0, 1]2 + IR, and X has finite energy, i.e., X E (00, 1J3). In this way, ((, u,) as the edge representation of an edge ji. We adopt the definition graphon signals from [24] and extend edge features, instead of graphon signals function for node feature as stated in (24).
think of
Analogous to the neighborhood aggregation operation in equation (1), the aggregation operation for graphon W and graphon signal X can be defined as the function X [0, 1] + R
Tw X()) (w) (w)==( W(u, ( v)dv
(37)
Let X. the aggregated information is further transformed by L layers of MLPs (similar to Eq. 2 then for E [L]. (1)) is determined as follows:
(w) o (H (HO))))
(38)
where (0) = h, H. is the linear transformation and a is the non-linear ReLU activation function. Induced Graphon Neural Network for CTDGs
We adopt the definition of induced graphon and induced graphon signals from 24, extend them to the CTDGs setting, and determine an induced graphon neural network that correspond to our proposed temporal graph learning algorithm in Section 3.1
Given a CTDG G and the graphon W that represents graph family of G, we would leverage the aforementioned graphon W to determine the induced graphon and induced graphon signals that correspond to snapshots of CTDG. At time let the number of nodes of ((t) be n(t), let W(';; [0, 1J2 [0, 1] and (+) [0, 1]2 - Rd denotes the induced graphon and induced graphon signals correspond to ((t), respectively. We determine W(t), and (+) the followings:
For any u E [0, let 4, = (i - 1)/n((), i/n(t)). S S re(t) and = [
1)/n((), i/m(O) issss n(i). If E I, E Ij. where 1 < i,j j S n((). then
(1, () (10 u5 uj)l(i S n(T))(() S n(t) + (1,, uz)
(39)
2 I(i S (())I(i S n()))
where f < xt, u4
II is the indicator function, and A (u, Uz)
Ber(W(( (u, u,)), where Ber indicates the Bernoulli distribution. The initial state, i.c., t = 0 would simply be W(() = A (u; uz), and we define the temporal graphon signal function at time f as:
( u) = (" 1 u5 uz) S (n))(( S n(F))
(40)
and we let the graphon signals function that associated with W be X X(u, u) In similar manner to Equation (1), the sum aggregation opertaion time would be:
T (1) = f/" w(9 v) x() (u, v)
(41)
24

---

and the final result is T ( after L layers of MLP transformation, similar as Eq
Graphon NTK and Induced Graphon Temp-G2NTH NTK
Let sunn be the WNN defined by Eq. networks defined by Eq. 39 and 40 Similar to Eq. given graphons W, W and their signals
38 and Stemp-wne be the induced graphon neural
X, X' that correspond to CTDGs G, G", respectively, also given parameters H. then the NTK of fwmn (X, W, H) and funn (X', W' H) would be:
wnn (X, W, W') = (0.1))))) ffmn (X, W. W.H) f (X', W" H))
0H
ÖH
and the NTmK-GGNTK of the induced graphon neural network at time t would be:
0 Oftemp wnp (X1), W H) o wan (X W
H
① wnn (x (x))),,, w(t), W(()) Eн~N(O.1
0H
0H
D.2 Detailed Proofs
We let Kw (W, W = @ @unn W. W and Kw(W"), W
Otemp-umm (X X W(O, W as we derive at the graphon signals X, X' by W,W' W and the induced graphon signals (*), x by w(tt, Wh(t), so in Theorem Section 5.4 we decide to denote the NTK by Kw (W, W and the induced NTK by Kw (W((), W for simpler notation. For simplicity, we let the number of BLOCK operations be L =
Proof.
|[ (W, W - (w w/(0)|
| wnn (', W, W H) + temp--umn (x(1), x'(0) w() w((() Hill
||o (HTw (HTwxX/Ww>> X ('TW.X')Twx X' - d'H x ww. o HHT Way Two
|HO((HTW X)Tw x (HTW (')TTTX'TTT....... X'>Tw,X' X' - wxe X Twa X ('TT:X') X'YTwiX'
+ oo' ('HH X X . (HI X')Tw:X' - (HT Xw o' (HT way x Twits
S 110/ WHT X)TW X of (HTW (
(HT X')Tx.X'
+ 11o' HHH X I
X' wHH x of w (wrss
HHTTWW)II o' HT WO [I WH X')TwxX''
(HTT:: - - (HT +
OHT wan
x(1))
of OHT wao x (ToT
((HHTXX]IWX - d'HT - (O) yT 1 X'T
('HHTT σ' oo x x())
(42)
The first inequality holds due to the triangle inequality, and the second inequality holds due to the property of the operator norm.
can see that, in order to prove Theorem 5.4 it sufficient to prove that:
( (HI
(43)
and
(o (HTTHTT.x'')TT ((HTwaa X'(1) T
Twee Xx))
(44)
25

---

Since Eq. 43 and Eq. are essentially the same, we would focus on proving Eq. 43 We further
applying algebraic manipulation Eq. 44 as follows:
(HTWX)Twe (HT ( y Twox
0' (HTWw))Tre o' ('HTw X X)T wio (0)
+o'(HT XwT x - d' x y Two. x
0 (HIW o' W
+ of (W -o'HH (
(HTTW x)||
|w Two Twox x + 0 (HTW X) - o' WH Ho |//Twioo x
(45)
The first inequality holds due the triangle inequality, and the second inequality holds due to the property the operator norm.
Therefore, from here, in order to prove Eq. 43 it is sufficient to prove that
|T X - x
+0
(46)
and
oo (HTTT - of (HT wis woxx x(t)
+
(47)
Since Eq 46
implies Eq. 47
so we would focus on proving Eq.
46
We further transform Eq.
46 as
follows:
Tw X Twoo
|/ X X(1)) + +Tw
- T Two Twoo x
(48)
Tix Tw.x(0/
Twx(()) - X()
|T |w 1x-X-x1111 |[T Two || ||
Similar to Eq. 45| we first apply the triangle inequality to obtain the first inequality, and apply the property of the operator norm to determine the second inequailty. From here, is sufficient prove that
|| 1x1011 +
(49)
and
[Tw - Twooll +
(50)
We observe that
|| - xx1 S I[ W/
(51)
the inequality holds due the definition of (0) thus by Lemma D.I Eq. 49 holds.
As proven in 24 if both ||X - x(( and || W(1|| converges to 0 as t + oc, then Eq. 50
holds.
Therefore, the proof for Theorem 5.4 is now completed.
26

---

Lemma D.1. |W - | is bounded by 1/n(t)² and 1/n(f)² and thus,
|| 1 - 0, as r + oc
(52)
since 1/n(t)2 + 0 as + 0
Proof. In order to prove the convergence of this lemma, we will need prove the convergence in L2 norm, ie..
I 10 -0
We first prove that
48 n2t)²
IIW 112 S
(53)
I - 11 L-' L' (W(u,)) A dudo
m(t) n(t)
s//(l))
(Since)
(W(u, - AA 2
(1-1)/m(t) (-1)//n())
n(t) m(t)
s/al))
(S/n())
(W(,,v) - W(w;, u,))) dudv
((-1)/m())
(G-1)/m(0)
n())
s/m(0)
(3/1())
8
(Iu uil + 10 uz]) dudd
(54)
i=
(1-1)/(())
(-11/nm()
n(t) 2(t)(())
s/m(()
(sla(t)
4
3
n(1)2 dudu
(1-1)/m(1) J (-11//0(0
*(t) n(t)
4
n(t)2
(n(1) n(t)
nt))
The first inequality holds due the fact that W. W are 8 Lipsschitz
Next, prove the lemma using mathematical induction.
For f = 0, then (0)) = (0), thus the lemma holds for W since || - [( = I| - A is 48 bounded by m(Of=. Therefore, the Lemma holds for t = 0.
Given that fix some timestamp and suppose that the Lemma holds for every timestamp in the interval [0, F). We would focus on proving that the Lemma also holds for t >
I[ - 11
2 IW W(0
+ W -A
1
(55)
JIW w(
+ 2 -
1
2
1 |W w(0l|+
2,3
nt)²
The first term is bounded by 1/n(I)² by our induction hypothesis, and second term is also bounded
by 1/n(1)2, and as - oo, [ - oo then 1/n(1)2, 1/n(1)2 + and thus || - W + as t + oo, which completes the proof.
27

---

D.3 Detailed Comparison with Previous Work
In short, we break through the convergence limitations of previous work [24]. For instance, besides temporal dependencies between snapshots of the evolving graphs, the work 24 that is most closely related to our theoretical results does not account for any dependencies between static graphs and does not establish limit object for two different graphs. The detailed illustration is delivered as follows.
We first summarize the setting about the convergence of static graphs to graphons and the theoretical findings of [24]: the previous work that is most closely to theoretical findings in Theorem 5.4 is 24) [24] proves that if a graph sequence of static random graphs {G,) with growing number of nodes, Le., the number of nodes in G; is less than equal G, with i < j. converges to a graphon W, and the graph signal sequences {zn), {ar converge the graphon signal X, X', respectively, then the induced graphon neural tangent kernel between graph G: with signal I; and graph G; with signal oy converges to the graphon neural tangent kernel between W with signal X and W with signal X", as the number of nodes in the graphs of the sequence }G.} goes to infinity.
Therefore, we notice that the theoretical findings in 22 do not account for any dependencies between static graphs in the graph sequence, and (24) establishes the results of convergence for the neural tangent kernel between the same graph, but with different signals.
Next, we point out how evolving graphs can be represented as a sequence of graphs with growing number of nodes. Suppose have evolving graphs G that has snapshots, G(h)
in ((t) ..... (ttm)) and the number of nodes in ((+) is less than or equal the number of nodes i <jj- j. Then the snapshots of G can be regarded as a graph sequence with the growing number of nodes. However, unlike the graph sequence in 224, there are temporal dependencies between graphs in the graph sequence of G.
Similar to the result of [24] for static graphs, we establish a limit object on the graph sequence representation of the evolving graph, and overcome the limitations of (24. as we take the temporal dependencies between graphs in the graph sequence of the evolving graph into account, and derive at the limit object for the graphon neural tangent kernel of 2 different evolving graphs.
E Detailed Comparison with Previous Temporal Graph Representation Learning Works
In this section, we provide detailed comparison between our Temp- Temp-G&NTH NTK and previous traditional temporal graph learning methods, DGNN (31), EvolveGCN (35), ROLAND 488) and SSGNN (7), that rely on neural network training (c.g, stacking neural layers, gradient descent, and backpropaga- tion) to obtain neural representations support corresponding graph downstream tasks. However, our Temp-G>NTT does not rely on neural network structure but can achieve the expressive power of graph neural networks, as our theoretical analysis and experiments demonstrate.
To be specific, DGNN BII, EvolveGCN (35, ROLAND 48), and SSGNN [ belong to the category of recurrent graph neural architectures that handle temporal information (e.g., the learnable weight level like EvolveGCN 31 or hidden representation level like ROLAND 48) This is indeed an effective direction, but it requires heavy time complexity.
Facing this problem, an emerging direction appears, i.c., MLP-Mixer on Static Graphs [66] or GraphMixer on temporal graphs [8]. Especially, GraphMixer aggregates information from recent temporal neighbors and processes them with MLP-Mixe layers. Motivated by this direction, we propose our temporal graph neural tangent kernel. Also, we would like to note that, even without recurrent neural architectures, temporal information can also be preserved in our method.
To be more specific, in our method, temporal dependencies are captured in Eq. where we construct the temporal node representations for a node at time by aggregating information (e.g., node features, edge features, and time difference) from its previous temporal neighbors. And the entire process does not involve neural training but just depends on mathematical time kernel functions. other words, this process records the current state of based on its own neighborhood at the previous time
28

---

and can be retrieved for future state computation. Besides theoretical derivation, especially, Table 2 and Figure visualize our method's 's effectiveness.
To support our above statement, we list the detailed illustration below.
DGNN 31 is designed to execute the link prediction task (while ours is mainly for temporal graph classification and can be easily adapted to temporal node classification). In order to obtain the link predictions, nodes are categorized as interacting or influenced as follows, If nodes are involved in (directed) interaction (u, v, t). then u, are interacting nodes and nodes that are nearby this interaction are referred to as "influenced nodes". On the other hand, If two nodes u and interact at certain time, then DGNN [31] updates their temporal representation. First, process each of u and e separately by employing recurrent architecture their previous temporal representations and finally combine with time encoding the difference between the current time and the last interaction time of that node. Then, merge the two representations and obtain two new representations for u and v. If two nodes interact, nearby nodes ("influenced nodes") would be affected. DGNN [3I also updates "influenced nodes", i.c., applying recurrent architecture on their previous representation, combining with two representations from interacting nodes, and the time encoding of difference between current time and last interacting time.
EvolveGCN B5 is link prediction and node classification method. Specifically, EvolveGCN 351 operates on graph snapshots and uses recurrent architecture (e.g. LSTM) to update the weight of each neural layer across time. Then, at certain time t, EvolveGCN [35 gets node representation by applying the current snapshot's adjacency matrix, learnable weights, and representation from the previous recurrent layer.
ROLAND (88 is also method designed for link prediction. Different from EvolveGCN 31, the the recurrent architectures in ROLAND 48 are added on the hidden representation vectors other than learnable weights across timestamps. Then the components in recurrent architectures get simplified in ROLAND [48). which can be mainly based on MLPs and simple GNNs.
SSGNN 7 is performs the time series forecasting task. To be more specific, SSGNN 7 first uses a deep randomized recurrent neural network to encode the history of each node encodings into high-dimensional vector embeddings, and then uses powers of the graph adjacency matrix to build informative node representations of the spatiotemporal dynamics at different scales. Then, the decoder maps the node representations into the desired output, e.g., future values of the time series.
Next, we state the position of our method in temporal graph learning. A recent temporal graph learning survey 30 reviewed temporal graph learning methods, including EvolveGCN (35. SSGNN 77 and DGNN [31, their taxonomy, as plotted in its Figure 2 (00
In that taxonomy, according to the best of our knowledge, our method belongs to the category "Event-based", and is the child node of "Temporal Embedding" and "Temporal Neighborhood", the position is close to the work TGL [51].
However, different from TGL (51). large-scale graph neural network, to our best knowledge, method is the first temporal graph neural tangent kernel method.
F
Extra Temporal Graph-Level Experiments
F.1 Ablation Study of Temporal Graph Classification
We conduct an ablation study to investigate how different time encoding functions affect the perfor- mance of TeNK-G We select the infectious dataset to perform our ablation study.
Here, we examine how the usage of the time encoding function and its variations affect the perfor- mance of our predictor. Recall that we leverage tene to encode the raw relative difference between timestamps, (L - 1) in Eq. For our ablation study, instead of the relative time difference encoding, i.e., (l - 1), we also consider the raw relative difference, (l - Z), the absolute time encoding, bene (1), and the absolute timestamp, L. The results are presented in Table 5 and the best accuracy is highlighted in bold. As we can see, the utilization of the time encoding Tunction (first and second
29

---

Table 5: Ablation Study of Different Time Encoding Functions Classification Accuracy the INFECTIOUS Dataset.
METHOD
ACCURACY
ABSOLUTE DIFFERENCE
0,600 = 0.114 0,570 = 0,081
ABSOLUTE DIFFERENCE ENCODING
RELATIVE DIFFERENCE
0,620 0.060
TEMP-G (RelatiVE DIFFERENCE ENCODING)
0.740 + 0.058
Table 6: Parameter Analysis of Different Number of Recent Neighbors on Classification Accuracy on the INFECTIOUS Dataset.
NUMBER OF RECENT NEIGHBORS
ACCURACY
NEIGHBORS
0.690 + 0.115
10 NEIGHBORS
0.700 = 0.126
15 NEIGHBORS
0.730 = 0.103
20 NEIGHBORS
0.710 + 0.097
NEIGHBORS
0.720 + 0.103
TEMP-G'NTK (ALL NEIGHRORS)
0.740 + 0.058
rows) yields higher accuracy than using raw timestamps, with 74% and 62% improvement, respec- tively. This suggests the ability and efficiency tene in distinguishing different timestamps, which enhances the classification result.
F.2 Parameter Analysis of Temporal Graph Classification
We conduct parameter analysis to investigate how different numbers of neighbors affect the perfor- mance of Temp-G"NTK We also select the infectious dataset to perform our parameter analysis.
Thus, we delve into how the Temp-G&NTK performs with respect to the number of temporal neighbors. Specifically, in practice, most temporal graph representation learning methods aggregate information from the most K recent neighbors
39 instead of the full temporal neighborhood, A/((( (v). For our parameter analysis, we vary the number of recent neighbors from {5, 10, 15, 20, 25}. perform the neighborhood aggregation (Eq. [ on these recent neighbors, and report the classification accuracy of Temp-Cr G NTK for the infectious dataset. The results are shown in Table 6 and the best results are highlighted bold. Integrating all temporal neighbors into node representation yields higher accuracy than accounting for some recent neighbors, shown in Table 6 These findings further suggest Cemp-G&NTK is able leverage and capture the information the full temporal neighborhood.
F.3 Temporal Graph Similarity
Here, we use four unlabeled large real-world temporal graphs, WIKI, REDDIT, MOOC, and LASTFM to demonstrate the scalability of our Temp-G*NTK, shown in Figure and Figure where æ-axis is the timestamp, and the y-axis the similarity between two temporal graphs at a certain timestamp.
For each pair of temporal graphs, we compute the neural tangent kernel values with respect to time and plot the values as below. For each plot, the y-axis represents the Temp- NTK value and the z-axis represents the timestamp. Although the timestamp ranges for each temporal graph are different, we rescale the æ-axis to [O; 1000] for better illustration. For each pair of graphs, the corresponding plot shows different curve, suggesting that our Temp-G"NTK can distinguish different pairs of temporal graphs. More interestingly, the corresponding observations align with our theoretical assumptions that the similarity of different growing temporal graphs tends to converge.
30

---

4.500
13322
$2A41
5382
205
200
100
080
620
800
(a) WikiPedia and LastFM
(b) WikiPedia and MOOC
(c) WikiPedia and Reddit
Figure 2: Similarity of Different Temporal Graphs With Time Increased (Part I). y-axis represents the Temp-G"NTK value, and the z-axis represents the timestamp
60912
6300
85435
05579
0204
090
6382
05072
205
200
1000
60
(a) Reddit and MOOC
(b) MOOC and LastEM
Reddit and LastFM
Figure 3: Similarity of Different Temporal Graphs With Time Increased (Part IT). y-axis represents the Temp- G GTK value, and the r-axis represents the timestamp
G Reproducibility
G.1 Datasets Details
The detailed statistics of small and large temporal graph datasets for graph-level experiments are shown in Table and Table g
Table 7: Small Temporal Graph Dataset Statistics
DATASET
# GRAPHS
# CLASSES
# AvG NODES
# AvG EDGES
INFECTIOUS
200
2
50.00
459.72 72
DBLP
755
2
52.87
99.78
FACEBOOK
995
2
95.72
101.72
TUMBLR
53.11
71.63
G.2 Temporal Graph Classification
Next, we provide details on how we conduct our experiments and the implementations of baseline algorithms in Section 6.1 In general, upon obtaining the time representation in Eq. let the dimension of the time representation be d, 25 and a = vd.
In order to leverage Temp-G*NTK for graph classification, predictor with the gram matrix of pairwise Temp-G'sN values of the training set as the pre- computed kernel. The regularization parameter C' of the SVM classifier is sampled evenly from 120 values in the interval [10 2 10*], log scale, and set the number of maximum iterations to 5 5.10 For the number of BLOCK operations in our NTK formula, L, we search for L over (1, and we notice that the validation accuracy remains unchanged while the varies.
employ C-SVM kernel regression
For Graph Kernels and Graph Representation Learning methods, we first obtain the representation of each graph in the training set and then compute the pair-wise gram matrix, where each entry is the dot product of the representation of graph pair. We then perform graph classification by
31

---

Table Large Temporal Graph Dataset Statistics
DATASET
# USERS
# ITEMS
# INTERACTIONS
REDDIT
10,000
984
672,447
WIKIPEDIA
8,227
1,000
157,474
LASTEM
980
1,000
1,293,103
MOOC
7.047
97
411,749
leveraging C-SVM as our predictor and the pre-compputed kernel as the aformentioned gram matrix. For the classifier regularization parameter C, we also determine this value by even sampling over the interval [10-2 2 10"]. in log scale, and the number of iterations be 5 -10. We adopt the implementations of Graph Kernels from GRAKEL library 45 and the implementations Graph Representation Learning methods from the Karate Club library [40] parameters from implementations of both libraries.
We adopt the default hyper-
For TGL methods, which are TGN and GraphMixer, we first obtain node representations in each graph of the training set using the official code released by authors of TGN and GraphMixer" then we determine the graph representation by performing sum pooling over the node representations. In the process of obtaining node representations, we adopt default and GraphMixer. Finally, we implement a simple linear classifier that consists of layer of linear transformation and ReLU activation function, and the final output is determined by the Sigmoid function, as all datasets are binary classification. We train and optimize these models by the Adam optimizer, with the learning rate of 0.001, (31, 82) (0.9, 0.999), and the Binary Cross Entropy loss function. We adopt default hyper-parameters.
in the code of TGN
TEMP- G/NTK
Draplatiscr
0.53
0.51
030
0.0
054
0.46
0.4
030
1.5
6. 12
101
dbip
tumbll
Figure 4: Plots of testing classification accuracy score of baseline algorithms with respect different stages of temporal graphs from the dblp and tumblr datasets. The y-axis in each plot states the accuracy score, and the values in the r-axis represent how many percentages of timestamps have been taken into account. For example, at x = 1/5, the score is obtained by performing classification on the first 1/5 timestamps of each graph.
In addition, we also provide the plot that illustrates the performance of baseline algorithms at different timestamps of the DBLP and TUMBLR datasets in Figure
G.3 Temporal Node Property Prediction
In order to utilize Temp-G N for node property prediction, we first compute the node pair-wise gram matrix the last MI.P layer in the Temp-G formula, i.e the kernel matrix ((4) in (9). Similar to performing graph classification task, we perform kernel regression with C-SVM and employ e ()) as the pre-computed kernel, and C' is also searched over [10-2, 10 in log scale. We
&The code for TGN is available at: https:/githhh.coom/ooo http://ggiihh..comm//vveeeeeeeet 9The code for GraphMixer is available at: http://ggthbbbbommm/oogcwilhaaaa
32

---

also vary the number of BLOCK Operations, L, by (1,2,3) to find the best NCDG score, which is obtained by = 1.
NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the
relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset used"). In general, answering "[No] or "[NA]" is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often
nuanced, so please just use your best, judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in Appendix If you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: the paper, the authors made clear statements for specifying the paper's contribution and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
33

---

Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [NA]
Justification: To the best of the authors' knowledge, there is no important limitation that needs to be highlighted here.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texx system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The authors tried their best to provide sufficient assumption and proof for the proposed theory in the paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in Appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
34

---

The paper shares the important information clearly for the experiment details. The code promised be released after the paper's publication.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The authors provide enough instructions for the main experimental results in the main content and the Appendix The code is promised to be released after the paper's publication.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (nttps://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
/nips.cc/ppull wttp:ccpppppccpeeeteeteeee...clt oog.aadeeeCoeeebbbassisioooo....
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
35

---

The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes)
Justification: The paper contains those details. The code is promised to released after the paper's publication.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in Appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The above factors are included the paper, and the code is promised to be released after the paper's publication.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative eтror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
36

---

Justification:
The paper includes this kind of information, and the code is promised to be released after the paper's publication.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
To the best of the authors' knowledge, the paper obeys the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: To the best of the authors' knowledge, they did not see the important socictal impacts of the paper. However, the authors discuss the outcome of this work in the graph learning community.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
37

---

11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
To the best of the authors' knowledge, the authors did see this kind of risk.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The authors made clear citations.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. cow datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [No]
Justification:
No new assets are the paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
38

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This work did not have crowdsourcing and research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
To the best of the authors' knowledge, this concern do not apply to this work.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
39


Reviews:
[{"review_id": "GMfTaoSEX5", "reviewer": "Reviewer_mhZJ", "summary": "This paper introduces the graph tangent kernel for temporal graph, thus enabling the learning task on time-evolving graph structures. The authors generalized the concepts of graph tangent kernel to incorporate the time domain information. They derived the generalization bound for the corresponding kernel predictor, and that their kernel approximates the graphon neural tangent kernel.", "questions": "1. Formula (1) defines the node feature. In this definition, the time instance $t$ is encoded by the function $t_{\\text {enc }}$. From the construction it seems that $t_{\\text {enc }}$ aims to make the time difference between $t-\\bar{t}$ as a vector. However, $t-\\bar{t}$ is already simple enough as a scalar. Can you explain the motivation of using $t_{\\text {enc }}$ instead of $t-\\bar{t}$ directly? What does $\\cos (\\Delta t \\mathbf{w})$ indicate?\n2. As the node feature is defined by formula (1), the authors suppose that there are no node features given in the beginning (from the dataset), and only edge features are accessible. Does the whole framework still work well if the node features are given by the dataset? In other words, does the conclusions in this paper rely on the specific construction method of the node features (i.e., formula (1))?\n3. Formula (12) provides the definition of the proposed \"kernel\", but the authors did not prove that this \"kernel\" satisfies the usual definition of kernel, i.e., it is symmetric and semi-definite.\n4. Theorem 5.1 and 5.2 assume the case that we indeed use the designed kernel and formula (13) to learn the task. However, there should be theoretical proofs that the proposed method (1) and (2) indeed converge to the Gaussian process or kernel method, like in [12].", "limitations": "N.A.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors generalized the concepts of graph tangent kernel to incorporate the time domain information. They derived the generalization bound for the corresponding kernel predictor, and that their kernel approximates the graphon neural tangent kernel.", "weaknesses": "See the questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks very much for the review! We greatly appreciate your acknowledgment of our paper's theoretical analysis. We address your questions in the form of Q&A below.\n\nMoreover, for the length limit, we distillate our answer and provide brief but important answers, more detailed intermediate steps, reasonings, and derivations can be provided during the upcoming author-reviewer discussion phase. All the detailed reply and supplementary experiments will be added to our updated paper.\n\n> **Q1. Explain using $\\mathbf{t}_{enc}$ instead of $t - \\bar{t}$ directly? What does $\\cos(\\Delta t \\mathbf{w})$ indicate?**\n\nTheoretically, mapping a discrete scalar to a continuous high-dimensional vector space has two unique advantages. First, the embedding vector can capture more complex information like non-linear relationships. Moreover, the embedding does not hurt the original scalar representation, i.e., close time scalars still have similar embedding vectors, and the embedding vectors can also capture periodic behaviors [1]. Second, the embedding vector can jointly work with deep learning models, i.e., embedding vectors for time can be potentially used within any neural architecture’s representation learning process, which is incapable of using discrete time scalars.\n\nIn our case, $\\mathbf{t}\\_{enc}(\\Delta t) = \\cos(\\Delta t \\mathbf{w})$ maps a scalar $\\Delta t$ to an $d_t-$dimensional vector, whose $i-$th entry is $\\cos(\\Delta t \\cdot \\alpha^{-(i-1) / \\beta})$. Given two real positive numbers $p, q > 0$ such that $p > q$. As $i \\rightarrow d\\_t$, the $i-$th entries of $\\mathbf{t}\\_{enc}(p), \\mathbf{t}\\_{enc}(q)$ go towards $0$. Since $p < q$, it is likely that $\\mathbf{t}\\_{enc}(p)$ contains more $0$ entries than $\\mathbf{t}\\_{enc}(q)$. \n\nMoreover, there are many choices for time encoding. However, most functions require trainable parameters that add extra computational burden. But our $\\mathbf{t}\\_{enc}(.)$ relies on mathematical properties and only needs fixed parameters ($\\alpha, \\beta$), which is suitable for kernel-based methods.\n\nEmpirically, as shown in Table 4 of our paper, using relative difference $t - \\bar{t}$ (3rd line of Table 4) directly yields a lower accuracy than using $\\mathbf{t}\\_{enc}(t - \\bar{t})$, justifying the effectiveness of $\\mathbf{t}\\_{enc}(.)$.\n\nReference: [1] Time2Vec: Learning a Vector Representation of Time\n\n> **Q2. Does the whole framework still work well if the node features are given by the dataset?**\n\nThe reason we omit node features in formula (1) is that prevalent benchmarks only support time-aware edge features.\n\nBut if node features are given, our framework still works. Theoretically, formula (1) can be extended as follows: $h_v(t) = c \\cdot \\sum_{(u, \\bar{t})}[\\mathbf{t}\\_{enc}(t - \\bar{t}) || \\mathbf{e}\\_{uv}(t) || \\mathbf{x}\\_{u}(\\bar{t})]$, where $\\mathbf{x}\\_{u}(\\bar{t})$ is the node features of $u$ at time $\\bar{t}$.\n\nAdding node features will not affect our conclusions and framework, as the construction of our kernel depends on $h_v(t)$ as a general term, instead of its components, such as node / edge features. Moreover, Theorem 5.1 and Theorem 5.2 still hold if node features are given.\n\n> **Q3. Proof of symmetric and semi-definite properties.**\n\nWe have proved the symmetric and semi-definite properties of our method. Due to the rebuttal length limit, the detailed proof will be uploaded during the author-reviewer discussion phase via the “official comment” channel.\n\n> **Q4. However, there should be theoretical proof that the proposed method (1) and (2) indeed converge to the Gaussian process or kernel method, like in [12].**\n\nIn short, our proposed method naturally enjoys the convergence in [12].\n\n```\nFirst, we provide some preliminary.\n```\n\nLet $f_{nn}(\\mathbf{x}, \\theta)$ be the output of a fully connected neural network, with parameters $\\theta \\in \\mathbb{R}^{p}$ and $\\mathbf{x} \\in \\mathbb{R}^d$ as the input. \n\nThen the Neural Tangent Kernel (NTK) corresponds to $f$, and any arbitrary input $\\mathbf{x}, \\mathbf{x'}$ would be \n$\\nabla_{\\theta}f_{nn}(\\mathbf{x}, \\theta)^ \\top \\nabla_{\\theta}f_{nn}(\\mathbf{x}', \\theta)$\n\nSuppose that $f_{nn}$ has $L$ layers, the $l-$th layer's width is denoted as $d_l$. Theorem 1 from [12] states that in the limit of $d_1, \\dots, d_L \\rightarrow \\infty$, the NTK converges in probability to a deterministic limiting kernel.\n\n```\nNext, we analyze these terms in our paper's context.\n```\n\nIf we apply Theorem 1 from [12], then the NTK (defined in [12]) associating with a deep neural network consisting of $L$ layers applying on temporal node representation $v, v'$ converges, with high probability, to the deterministic limiting kernel $\\boldsymbol{\\Theta}^{(L)}(G^{(t)}, G^{(t)})\\_{vv'} \\otimes \\text{Id}\\_{dL}$, (where $\\text{Id}\\_{d_L}$ is the identity matrix with dimension $d_L$ and $d_L$ is the width of the $L$-layer MLP), if $d_1, \\dots, d_L \\rightarrow \\infty$, and $\\boldsymbol{\\Theta}^{(L)}$ is denoted as a scalar kernel. To be clear, the kernel value between two graphs in Equation (13) is defined based on the summation of limiting scalar kernel $\\boldsymbol{\\Theta}^{(L)}$ taken over all node pairs $v, v'$.\n\nRegarding Gaussian process, based on Proposition 1 from [12], the output of the deep neural network consisting of $L$ layers operating on temporal node representations defined in Section 3.1 converges to Gaussian process of covariance $\\boldsymbol{\\Sigma}^{(L)}$, with $d_1, \\dots, d_{L - 1} \\rightarrow \\infty$ (as defined in Equation 9).\n```\nTo better sum up for understanding, our method is constructed based on limiting objects of the NTK convergence theories.\n```\nWe will add the above derivation to our updated paper.", "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": "IdqMumW6yv", "reviewer": "Reviewer_cL5q", "summary": "The proposed Temporal Graph Neural Tangent Kernel with Graphon-Guaranteed or Temp-G3\nNTK method is a novel temporal graph learning method with provable error bounds. It extends the the simplicity and interpretation ability of Graph Neural Tangent Kernel to the temporal graph setting leading to rigorous error bounds for the temporal graph classification task. Furthermore, in the case of growing networks, the proposed method will converge in the limit to the graphon NTK value. Temp-G3NTK method achieves strong performance on both temporal graph classification and the node property prediction task.", "questions": "- might be good to add plots or table showing the compute time for each dataset. \n- Is it possible to adapt the method to continuous time dynamic graphs (CTDGs)? \n- How would the model convergence be if the network both grows and shrinks over time. This is quite common in real world temporal graphs.", "limitations": "Missing discussion on limitations for current work as well as discussions on societal impact. Note that it is possible to lead to negative societal impact when temporal graph learning methods are deployed in applications such as anomaly detection, brain activity classification and more.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- **novel method with theoretical bounds**: the proposed method is one of the first methods in temporal graph learning with provable error bounds. This is novel and opens up research for more future methods with provable bounds.\n\n- **strong performance**. The  Temp-G3NTK method shows strong performance on the temporal graph classification task and competitive performance for the node property prediction task from TGB.   Additional ablation studies are also provided in the appendix. \n\n- **clear presentation**: overall the paper is clearly presented and also with discussion on the time complexity of the method.", "weaknesses": "The main concern I have is the **time complexity**. The $O(n^2L|V|^2 + n|E|)$ complexity is quite high thus limiting the scalability of the method to networks with millions of nodes. The node pair wise covariance matrix would be expensive to compute. \n\nAdditionally, there is no limitation and societal impact discussion in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks very much for the review! We greatly appreciate your acknowledgment of our paper's novelty, presentation, and model performance. We address your questions in the form of Q&A below.\n\nMoreover, for the length limit, we distillate our answer and provide brief but important answers, more detailed intermediate steps, reasonings, and derivations can be provided during the upcoming author-reviewer discussion phase. All the detailed reply and supplementary experiments will be added to our updated paper.\n\n> **Q1. Might be good to add plots or tables showing the compute time for each dataset**\n\nWe have added the empirical running time of our method and 8 other baselines on 4 benchmark datasets. _The table is plotted as Table 1 in the 1-page pdf file in the “general rebuttal”_.\n\nOverall, the empirical running time aligns with our theoretical analysis of time complexity in Table 1 in the paper. That is, our method belongs to the graph kernel category, where the node-wise comparison is usually inevitable, and our time complexity is lower. Compared to the neural baselines, since our method does not rely on complex neural training like backpropagation, our method is still efficient.\n\nGiven our method achieved the best classification accuracy, as shown in Table 2 in the paper, according to the corresponding running time reported in Table 1 of the uploaded 1-page pdf during the rebuttal, our method is (1) more than 10x - 20x faster then complex temporal graph neural network methods like GraphMixer [6] and TGN [24]; (2) similarly efficient as simple kernel methods like WL-Subtree [27] and Shortest Path [4] and embedding methods like NetLSD [30] and GL2Vec [5]; and only Graph2Vec [21] is running faster than our method, but our performance is roughly 1.4x better.\n\n> **Q2. Is it possible to adapt our method to continuous time dynamic graphs (CTDGs)?**\n\nThe answer is yes.\n\nIn the paper, we choose discrete time just for a better illustration of the proposed method. The transformation between discrete time and continuous time is possible, as described in lines 63-65 of the paper. \n\nIn other words, given 2 CTDGs $G, G'$, suppose that we already computed the Temp-G$^{3}$NTK value between $G, G'$ at time $t$. If new links occurring at time $t', t' > t$ are added into $G, G'$, then we update the neighborhood of each node in $G, G'$, and re-compute the Temp-G$^{3}$NTK value for $(G, G')$ at time $t'$.\n\nAn extreme case needs more caution, i.e., _spare_ continuous time dynamic graph. For example, only one edge is updated per timestamp. This scenario will make our method run slower, because more snapshots are emerging. But multiple edges updated per timestamps can be adapted seamlessly. Moreover, one edge update per timestamp is very rare no matter in the real-world setting.\n\n> **Q3. How would the model convergence be if the network both grows and shrinks over time. This is quite common in real world temporal graphs.**\n\nIn brief, our method handles the case if some graph shrinks at the intermediate timestamp, and our theoretical findings hold as long as the life-long pattern is growing.\n\nIn other words, for a graph that has some growing stages and some shrinking stages in its life, if its number of nodes follow an overall growing trend, then Theorem 5.2 holds.\n\nTo be more specific, let the number of nodes of a temporal graph snapshot at time $t$, $G^{(t)}$, be $n(t)$, then Theorem 5.2 holds if $n(t) \\rightarrow \\infty$ as $t \\rightarrow \\infty$. Intuitively, the term $||K_W(W^{(t)}, W'^{(t)}) - K_W(W, W')||$ could be decomposed and bounded by terms that depend on $||W^{(t)} - W||, ||W'^{(t)} - W'||$ and $||X^{(t)} - X||, ||X'^{(t)} - X'||$ (where $X$ is $W$'s signal function and $X^{(t)}, W^{(t)}$ denote the induced graphon and induced graphon corresponds to temporal snapshot $G^{(t)}$). Then, $||W^{(t)} - W||, ||X^{(t)} - X||$ are bounded by terms that depend on the number of nodes $1 / n(t)$, so $||W^{(t)} - W||, ||X^{(t)} - X|| \\rightarrow 0$ as $n(t) \\rightarrow \\infty$.\n\nMoreover, according to the real-world temporal graph dataset benchmark like (https://snap.stanford.edu/data/index.html), especially social graphs and citation graphs, a growing pattern is usually more common.\n\n> **Q4. Possible negative societal impact**\n\nIn general, graph deep learning often involves analyzing complex networks, which can include sensitive personal information. If not managed properly, this can lead to privacy violations, especially when dealing with social networks, financial systems, or medical data. Also, if the data used to train graph models contains biases, these biases can be propagated and even amplified by the algorithms. \n\nTo the best of the authors’ knowledge, we do not discern specific negative societal impacts caused by this proposed method. However, we will add the above general discussions regarding the risks of graph deep learning in our updated paper.", "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": "UAWH7WFUrn", "reviewer": "Reviewer_yH9B", "summary": "This paper proposes a graph neural tangent kernel method that extends the advantages from static graphs to temporal graphs. Theoretical analyses are conducted to prove the transferability and robustness of the model. Experiments are performed on graph-level tasks as well as node-level tasks.", "questions": "This is good work. Is it possible to use more graph neural architecture-based methods in experiments for two-level tasks? Also the datasets selection can be more inclusive.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1: The motivation for the paper is strong. Temporal graphs are quite a hot topic these days, and transferring graph tangent kernel method to temporal graphs shows clear intuition. \n\n2: The theoretical analysis regarding the generalization bound,  convergence and time complexity are comprehensive.\n\n3: Experiments show the competitive results, which demonstrate the potential and effectiveness of the proposed method.", "weaknesses": "The related work section is a bit condensed, which may decrease the persuasiveness of the paper.\n\nThe explanation regarding the simplicity and interpretation ability of the proposed method is unclear. I wonder if the authors can further clarify.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks very much for the review! We greatly appreciate your acknowledgment of our paper's motivation, theoretical analysis, and experiments. We address your questions in the form of Q&A below.\n\nMoreover, for the length limit, we distillate our answer and provide brief but important answers, more detailed intermediate steps, reasonings, and derivations can be provided during the upcoming author-reviewer discussion phase. All the detailed reply and supplementary experiments will be added to our updated paper.\n\n> **W1. Expanding the related work section**\n\nOn one hand, we expand the detailed introduction to Graphons, Graphon Neural Network, and Graphon Neural Tangent Kernel.\n\nFor example, following details will be added to Section C.1 of our Appendix.\n```\nGraphons. A graphon is a symmetric, bounded, and measurable function $W : [0, 1]^2 \\rightarrow [0, 1]$ that acts as the limit object of dense graph sequences and defines a family of similar graphs. Specifically, given an undirected graph $\\mathbf{F}$ and a graph sequence $\\{G_n\\}$, whose $i$-th graph in the sequence, $G_i$, has $i$ nodes, then $\\{G_n\\}$ converges to $W$ if $\\lim_{n \\rightarrow \\infty} t(\\mathbf{F}, G_n) = t(\\mathbf{F}, W)$, where $t(\\mathbf{F}, G_n)$ defines the density of homomorphisms between $\\mathbf{F}$ and $G_n$, and $t(\\mathbf{F}, W)$ can be defined similarly. In this way, $W$ can also be regarded as a generative models for a certain graph family.\n\nGraphon Neural Networks (WNNs) [26]. Similar to how GNNs perform graph convolutions on a graph given the adjacency matrix, $A$, and node / edge features $H$, Graphon Neural Networks (WNNs) also perform graphon convolutions using $W$ and $X$, where $X: [0, 1] \\rightarrow \\mathbb{R}$ (corresponds to node-level) or $X: [0, 1]^2 \\rightarrow \\mathbb{R}$ (corresponds to edge-level) is graphon signals. Intuitively, we could consider WNNs as the counterpart of GNNs that operate on graphons. As proven in [26], as the graph's size of the graph sequence $\\{(G_n, H_n)\\}$ generated by $W, X$ grows, i.e $n \\rightarrow \\infty$, the output of GNNs operating on $\\{(G_n, H_n)\\}$ converges to the output of WNNs operating on $W, X$. More details can be found in Section C.1 in our Appendix.\n```\n\nOn the other hand, we include more temporal graph representation learning methods discussion in our paper, like CAWN [1], and DySAT [2].\n\nFor example, following details will be added to Related Work of our paper.\n```\n* CAWN obtains the causal walks for each node, anonymize the node indices on each walk, further process these walks with recurrent architectures, and the final temporal node representation is determined by aggregating walks encodings.\n\n* DySAT first transforms the given CTDG into discrete temporal graph snapshots, then applies Graph Attention Network (GAT) on each snapshots to obtain the spatial information, $\\mathbf{X}(t)$, where $t$-th corresponds to the graph snapshot at time $t$, and denote the spatial information for node $u$ in the $t-$th graph snapshot as $[\\mathbf{X}(t)]_u$. Then $u$'s temporal representation is obtained by applying Transformer on its spatial information at different timestamps: $h_u(t_k), h_u(t_{k - 1}), \\dots, h_u(t_0) = \\text{Transformer}([\\mathbf{X}(t_k)]_u, [\\mathbf{X}(t_{k - 1})]_u, \\dots, [\\mathbf{X}(t_0)]_u)$.\n```\n\nFinally, we would be more than willing to discuss any related work the reviewer recommend during the upcoming author-reviewer discussion phase.\n\nReference:\n\n[1] Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks, ICLR 2021\n \n[2] DySAT: Deep Neural Representation Learning on Dynamic Graphs via Self-Attention Networks, WSDM 2020\n\n> **W2. More explanation regrading the simplicity and interpretation of the proposed method**\n\nFor _simplicity_, as stated in the paper, our kernel method does not involve complex neural architecture or training algorithms. Moreover, all terms appearing in the method can be computed in an iterative manner as shown from Equation 7 to Equation 11.\n\nAdditionally, we added the empirical running time for comparing the efficiency of our method and 8 baselines across 4 datasets, as shown in Table 1 in the 1-page pdf in \"general rebuttal\". Overall, the empirical running time aligns with our theoretical analysis of time complexity in Table 1 of the paper. That is, our method belongs to the graph kernel category, where the node-wise comparison is usually inevitable, and our time complexity is lower; Compared to the neural baselines, since our method does not rely on complex neural training like backpropagation, our method is still efficient.\n\nIn brief, the _interpretation_ of our graph neural tangent kernel relates to the training dynamics of the temporal graph neural architecture that is defined in Section 3.1. Specifically, in the limit that the layer width of MLPs goes towards infinity, then the graph prediction using the architecture defined in Section 3.1 is equivalent to the prediction of using kernel regression, as stated in Equation 13.\n\n> **Q1. This is good work. Is it possible to use more graph neural architecture-based methods in experiments for two-level tasks? Also the datasets selection can be more inclusive.**\n\nAs stated in Section 6.1, for graph-level datasets, we cover a variety of different domains from DBLP (citation graph), Facebook (social graph), Infectious (human-contact graph), and Tumblr (social graph). Moreover, in Appendix D.4, we also show how our methods can scale on larger datasets (Wiki, Reddit, MOOC, LastFM), in terms of number of nodes and edges.\n\nOur baselines include static graph kernel methods, static GNN methods, temporal GNN methods, and ours stand for the temporal graph kernel method.\n\nDuring the rebuttal, we also include all baselines into a new graph dataset from https://chrsmrrs.github.io/datasets/docs/datasets/, the performance is shown in Table 2 in 1-page pdf in “general rebuttal”. According to the new results, our method still achieves the best performance.", "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": "3D7qC5EoY3", "reviewer": "Reviewer_YEfB", "summary": "This is a theoretical paper that studies graph neural tangent kernels in the context of temporal graphs. The authors propose a temporal GNTK model and proves rigorous error bounds. This work also links the convergence of the temporal GNTK to the graphon GNTK.", "questions": "1. Equation (1) is confusing. Are node features not given as the input in your discussion of CTDG in Section 2? How do you deal with the node features in (1)?\n\n1. To obtain (6), you have not mentioned that the weights $\\mathbf{W}$ are initialized as i.i.d. standard normals. Furthermore\n\n1. To obtain (6) and (13), aren't you actually training a different GNN for each time $t$? \n    - Your notation should be $f_{kernel}^{(t)}$ and $f_{temp}^{(t)}$, otherwise it misleads the reader. I.e., $f_{temp}^{(t)}$ (possibly based on $f_{temp}^{(t-1)}, \\ldots, f_{temp}^{(1)}$) is trained using $\\lbrace G_i^{(t)}  \\rbrace_{i=1}^n$.\n    - This is not the usual way temporal GNNs are trained. It also requires the strong assumption that all $G_i$ are synchronized (in terms of the inference data and task) in snapshot times $t$. \n\n1. The kernel (12) does not capture the temporal relationships between different time instances. I am not sure how this models or compares with typical temporal graph learning approaches that may use LSTM, RNN or transformers to capture temporal interactions.\n\n1. In relation to the above points, why do you not consider the kernel that takes the whole temporal graph sequence $G$ and $G'$ as inputs? I can understand that this is more sophisticated and complex but seems like a more fruitful approach.\n\n1. Table 1: I fail to see why Temp-G3NTK is computationally cheaper than GraphMixer. (Also, you have not defined $K$ for GraphMixer.) For graphs with large $|V|$, Temp-G3NTK is more expensive according to your table. \n\n1. GraphMixer is not included in Figure 1 because it is \"designed to directly process continuous-time dynamic graphs, which require observing the entire length of the input temporal graph instead of processing snapshots\". I don't think this claim is accurate. You can easily implement GraphMixer by restricting it to the snapshots. \n\nMinor:\n1. Theorem 5.1: should be $G_i$ has $T$ timestamps.\n\n1. Can you explain the meaning of the model name? What is \"Graphon-Guaranteed\"? It also does not sound grammatically correct.", "limitations": "I did not find a discussion on this.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "To the best of my knowledge, this is the first work that attempts to apply the NTK theory to continuous-time dynamic graphs. Despite the issues I raise below, I enjoyed the paper, which provides interesting insights into how NTK can be used to analyze temporal graph learning. However, this approach may not be SOTA.", "weaknesses": "1. The theory is an incremental modification of [7] to temporal graphs by including the time index $t$ to each graph. \n\n1. It is unclear how this approach compares with traditional temporal graph learning methods that capture temporal relationships. \n\n1. The assumptions made are quite strong, and some claims are dubious.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks very much for the review! We greatly appreciate your enjoy on our paper's insights, theoretical analysis, and experiments. We address your questions in the form of Q&A below.\n\nMoreover, for the length limit, we distillate our answer and provide brief but important answers, more detailed intermediate steps, reasonings, and derivations can be provided during the upcoming author-reviewer discussion phase. All the detailed reply and supplementary experiments will be added to our updated paper.\n\n> **Q1. How do you deal with the node features in Equation (1)?**\n\nThe reason we omit node features in Equation (1) is that prevalent benchmarks only support time-aware edge features.\n\nBut if node features are given, our framework still works. Theoretically, Equation (1) can be extended as follows: $h_v(t) = c \\cdot \\sum_{(u, \\bar{t})}[\\mathbf{t}\\_{enc}(t - \\bar{t}) || \\mathbf{e}\\_{uv}(t) || \\mathbf{x}_{u}(\\bar{t})]$, where $\\mathbf{x}_u(\\bar{t})$ is the node features of $u$ at time $\\bar{t}$.\n\nAdding node features will not affect our conclusions and framework, as the construction of our kernel depends on $h_v(t)$ as a general term, instead of its components, such as node / edge features. Moreover, Theorem 5.1 and Theorem 5.2 still hold if node features are given.\n\n> **Q2. How weights W in Equation (6) are initialized**\n\nFor Equation (6), the weights $\\mathbf{W}$ are initialized i.i.d from the normal distribution $\\mathcal{N}(0, 1)$.\n\n> **Q3. To obtain (6) and (13), aren't you actually training a different GNN for each time $t$?**\n\nWe want to clarify that our method does not involve training GNNs. \n\nThe kernel function in Equation 6 is just a starter and illustrated by a temporal graph neural network for easy interpretation, because the temporal graph neural network exists earlier than the proposed temporal graph neural tangent kernel (i.e., ours).\n\nThe derivation of our kernel function is given in Sec. 4, especially in Equation (12), which just relies on the covariance matrix computation through Equation (11), to Equation (10), to Equation (9), to Equation (8), and finally to Equation (7).\n\nA typo is found during the rebuttal. For the last term in Eq (11), $l-1$ should be $l$.\n\nWe will strengthen the above derivation in the updated paper.\n\n> **Q4. The kernel (12) does not capture the temporal relationships between different time instances. I am not sure how this models or compares with typical temporal graph learning approaches ...**\n\nTemporal dependencies are captured in Equation (1), where we construct the temporal node representations for a node $v$ at time $t$ by aggregating information (node, edge features, and time difference) from its previous temporal neighbors $(u, \\bar{t}), \\bar{t} < t$. Intuitively, this models the current state of $v$'s neighborhood at time $t$ based on its own neighborhood at the previous time $\\bar{t}$. Since we would want a vector representation for $v$, we perform vector summation over all information of temporal neighbors $(u, \\bar{t})$.\n\nIt is true that there is an established line of works in temporal graph learning using recurrent architecture and attention to learn temporal dependencies like TGN and TGAT, but there are works employing simpler architectures, such as GraphMixer, which aggregates information from recent temporal neighbors and processes them with MLP-Mixer layers.\n\n> **Q5. Why do you not consider the kernel that takes the whole temporal graph sequence and as inputs? I can understand that this is more sophisticated ...**\n\nIf we understand your question correctly, your concern is about Equation (13) that current time prediction only depends on other samples at the current time.\n\nWe admit that taking the historical behavior as you suggested is a promising approach, and actually this is what we have done in the paper. Instead of taking each past snapshot individually, recall our Equation (1), temporal dependencies are captured, where we construct the temporal node representations for a node $v$ at time $t$ by aggregating information (node, edge features, and time difference) from its previous temporal neighbors $(u, \\bar{t}), \\bar{t} < t$. Hence, the current time representation is the cumulation of the past. In this angle, the sequence of the temporal graph is observed by our method.\n\n> **Q6. Table 1: I fail to see why Temp-G3NTK is computationally cheaper than GraphMixer. (Also, you have not defined $K$ for GraphMixer.) ...**\n\nFirst, $K$ for GraphMixer is the padding length, i.e., the maximum number of recent interactions a node can sample.\n\nThe theoretical complexity compassion is not that straightforward by only looking at the power to number of nodes. As we stated in the paper, GraphMixer needs the complex neural computation like gradient descent and back propagation, but our method does not. That’s why we claim our method is faster.\n\nTo in-depth verify our claim, we added empirical running time comparison of all baselines across all datasets. The results are reported as Table 1 in the 1-page pdf in “general rebuttal”. According to the result, our method is roughly 10x-20x faster than GraphMixer, and also faster than most baselines.\n\nWe will include these new results in our paper to in-depth verify my hypothesis.\n\n> **Q7. GraphMixer is not included in Figure 1 because it is \"designed to directly process continuous-time dynamic graphs, which require observing the entire length of the input temporal graph instead of processing snapshots\". I don't think this claim is accurate. You can easily implement GraphMixer by restricting it to snapshots.**\n\nTechnically, GraphMixer can process discrete time dynamic graphs, by only considering part of the past snapshots as the continuous dynamic graphs, although it was originally designed for continuous graphs.\n\nSince we can use snapshot timestamp as edge timestamp for each edge in this snapshot, then we are now running GraphMixer and will add its plot during the author-reviewer discussion phase.", "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:
First of all, we want to sincerely thank the time and review of all reviewers and chairs, and we are very glad to learn the reviewers' appreciation for this paper.

Also, the reviewers' raised questions are very actionable and helpful to improve our paper. We have uploaded the answers individually to each reviewer.

Here, we upload a 1-page PDF file that contains Figures and Tables, which are required by reviewers for additional theoretical analysis and experiments.

Thanks again!

Meta-review: This paper introduces the Temporal Graph Neural Tangent Kernel (Temp-G3NTK) for learning on time-evolving graph structures. The method extends the Graph Neural Tangent Kernel (GNTK) to temporal graphs, incorporating time-domain information and deriving generalization bounds. Additionally, the work establishes a connection between the convergence of the temporal GNTK and the graphon GNTK.
While none of the reviewers opposed the acceptance of the paper, two expressed reservations. Their concerns centered on (1) the method being seen as an incremental extension of GNTK, and (2) doubts about the effectiveness of how temporal information is represented, despite the authors' detailed explanations.

I believe these concerns are not sufficient grounds for rejection. Most reviewers acknowledged that this is one of the first attempts to generalize GNTK to temporal graphs, and they recognized the theoretical rigor, solid results, and competitive performance of the method, which were further supported by additional experiments provided during the discussion.

Overall, I recommend this work for acceptance.
Decision: Accept (poster)