Beyond Spatio-Temporal Representations: Evolving Fourier Transform for Temporal Graphs
Authors: Anson Bastos
Kuldeep Singh
Abhishek Nadgeri
Manish Singh
Toyotaro Suzumura
Venue: ICLR 2024 poster (2024)
Keywords: Temporal Dynamic Graphs
Spectral Transform
GNN
Primary area: learning on graphs and other geometries & topologies
TL;DR: First work that proposes a concept to transform an evolving temporal graph to its frequency domain; we call it "Evolving Graph Fourier Transform (EFT)".

Abstract: We present the Evolving Graph Fourier Transform (EFT), the first invertible spectral transform that captures evolving representations on temporal graphs. We motivate our work by the inadequacy of existing methods for capturing the evolving graph spectra, which are also computationally expensive due to the temporal aspect along with the graph vertex domain. We view the problem as an optimization over the Laplacian of the continuous time dynamic graph. Additionally, we propose pseudo-spectrum relaxations that decompose the transformation process, making it highly computationally efficient. The EFT method adeptly captures the evolving graph's structural and positional properties, making it effective for downstream tasks on evolving graphs. Hence, as a reference implementation, we develop a simple neural model induced with \eft for capturing evolving graph spectra. We empirically validate our theoretical findings on a number of large-scale and standard temporal graph benchmarks and demonstrate that our model achieves state-of-the-art performance.

Published as a conference paper at ICLR 2024
BEYOND SPATIO-TEMPORAL REPRESENTATIONS: EVOLVING FOURIER TRANSFORM FOR TEMPORAL GRAPHS
Anson Bastos Kuldeep Singh", Abhishek Nadgeri', Manish Singh", Toyotaro Suzumura² HERE Technologies, India PIdiin Institute of Technology Hyderabad, India RRWTH Aachen, Germany *Cerence Gmbh, Germany The University of Tokyo, Japan ansonbastos@gmail. com, singh1ee weccerence.comm com, ahek nadger madgeri@rwth-aae wwwwthhahhhhhennnneeeeaaaaaa msinghêcse. iith. ac. in, suzumura@acm. org
ABSTRACT
We present the Evolving Graph Fourier Transform (EFT), the first invertible spectral transform that captures evolving representations on temporal graphs. We motivate our work by the inadequacy of existing methods for capturing the evolving graph spectra, which are also computationally expensive due to the temporal aspect along with the graph vertex domain. We view the problem as an optimization over the Laplacian of the continuous time dynamic graph. Additionally, we propose pseudo-spectrum relaxations that decompose the transforratiin process, making it highly computationally efficient. The EFT method adeptly captures the evolving graph's 's structural and positional properties, making it effective for downstream tasks evolving graphs. Hence, a simple neural model induced with EFT for capturing evolving graph spectra. We empirically validate theoretical findings number of large-scale and standard temporal graph benchmarks and demonstrate that our model achieves state-of-the-ar performance.
reference implementation,
develop
INTRODUCTION
In numerous practical situations, graphs exhibit temporal characteristics, as seen in applications like social networks, citation graphs, and bank transactions, among others (Kazemi et al.) 2020). These temporal graphs can be divided into two types: 1) temporal graphs with constant graph structure (Grassi et al. 2017 Cao et al., 2020). and 2) temporal graphs with dynamic structures (Zhou et al. Bastos et al. 2023 da Xu et al. 2020). Our focus in this work the latter case.
2022
The evolving graphs have been comprehensively studied from the opatio-temporn graph-neural network (GNN) perspective, focusing on propagating local information (Pareja et al. 20200 Shi et al., 2021 Xiang al. 2022; da Xu al., 2020). Albeit the success of spectral GNNs for static graphs for capturing non-local dependencies in graph signals (Wang& & Zhang 2022). they have not been applied to temporal graphs with evolving structure. To make spectral GNN work for temporal graphs effectively and efficiently, there is a necessity for an invertible transform that collectively captures evolving spectra along the graph vertex and time domain. To the best of knowledge, there exists no such transform in the spectral domain for temporal graphs with evolving structures.
In the present literature, Graph Fourier Transform (GFT), which is a generalization of Fourier Transform, exists for static graphs but can not capture spectra of evolving graph structure (Shuman af. 2013). Hence, it cannot be applied to temporal graphs due to the additional temporal aspect. One naive extension would be to treat the time direction as temporal edge, construct a directed graph with newly added nodes at each timestep, and find the Eigenvalue Decomposition (EVD) of the joint graph. However, this would lose the distinction between variation along temporal and vertex domains. Moreover, such an approach would incur an added computational cost by a multiplicative factor of ((T)), which would be prohibitively high for the temporal setting with large number of timesteps. Thus, in this paper, we attempt to find an approximation to the dynamic graph transform that would capture its evolving spectra and be efficient to compute.

---

Published as a conference paper at ICLR 2024
We aim to propose novel transform for temporal graph to its frequency domain. For this consider the Laplacian of the dynamic graph and find the orthogonal basis of maximum variation to obtain the spectral transform (Hammond et al. 201T). We view this variational form of the Laplacian such that the optimal value is within the 6- pseudospectrum (Tao) 2008). We then show that such optimization gives simple and efficient to compute solution while also being close to the exact solution of the variational form under certain conditions of Lipschitz continuous dynamic graphs. Effectively, we propose a method to simultancously perform spectral transform along both the time and vertex dimensions of a dynamic graph. This solves the following challenges over the natural extension of EVD over dynamic graphs: 1) The proposed transformation is computationally efficient compared to the direct eigendecomposition of the joint Laplacian. 2) Distinction between time and vertex domain frequency components with the proposed transform provides interpretability to the transformed spectral domain. We term the proposed concept as "Evolving Graph Fourier Transform" " (EFT). )
optimization of the
In summary, we make the following key contributions:
We propose EFT (grounded on theoretical foundations), that transforms a temporal graph to its frequency domain for capturing evolving spectra.
We provide the theoretical bounds of the difference between EFT and the exact solution to the variational form and analyze its properties.
As reference implementation, we develop a simple neural model induced with the proposed transform to process and filter the signals on the dynamic graphs for downstream tasks. We perform extensive experimentation on large-scale and standard datasets for dynamic graphs to show that our method can effectively filter out the noise signals and enhance task performance against baselines.
2 RELATED WORK
Spectral Graph Transforms: Work by (Hammond et al. 2011) was among the first propose computationally efficient algorithm to compute the Fourier Transform for static graphs. Loukas et al. (Loukas & Foucard 2016) conceptualized Joint Fourier Transform (JFT) over graphs which the signals change with time. JFT has been generalized in (Kartal et al. 2022) by proposing the Joint Fractional Fourier Transform (JFRT). However, JFT and JFRT does not consider graph structures evolving with time. (Cao et al.] (202T) apply JFT and propose a model for time series forecasting. (Villffahe-Delaado & Aviyente| 2017) summarized graphs over time by using Tucker decomposition to the dynamic graph Laplacian in order to obtain an orthogonal matrix and further applies it to a cognitive control experiment. However, this method does not fully capture the varying graph information in a lossless sense. Researchers have also proposed spectral methods for spapooltemporal applications such as action recognition (Yan et al.] [2018] Pan et al., [2020), traffic forecasting (Yu et al. 2017) etc. Other works such as (Mahyari & Aviyente | Chen et al.. 2022] Sarkar et al., 2012. Kurokawa et al. 2017 Jiang et al.) | et al., 2023) also consider temporal graphs but ignore the evolving strueture. We position
work the novel spectral graph transform for
temporal graphs which is currently a gap in existing literature.
Since static graph methods do not work well with dynamic graphs (Pareja et al. 2020), researchers have proposed a slew of methods (Pareja et al. 2020 et al. 2020 Xiang al. 2022), for learning on dynamic graphs for problems such as link prediction and node classification. One elementary way to adapt methods developed for static graphs on dynamic graphs is to use RNN modules in conjunction with GNN modules capture the evolving graph dynamics. Researchers (Seo et al. 2016 Narayan & Roe 2018 Manessi et al. 2020) have explored this idea extensively. Some other recent approaches model several real world phenomena, however, these methods rely on an RNN for encoding temporal information such as Bastas et al.] 2019)). da Xu et al. (2020). Ma et al. (2020), etc. Most generic among these works is TGN (Temporal Graph Networks) (Rossi et al. (020)) that remembers nodes and connections it has seen in the past, and then uses that memory to update new nodes and connections that it hasn't 't seen before. However, the memory updater uses GRU which may have issues such as vanishing gradient limiting the ability to capture long term information. Also, these models have been studied for small-gre small-graphs spread over limited time duration (c.g., one month).
Temporal Graph Representation Learning:
Considering large scale temporal graphs with evolving structures, one such application is that of sequential recommendation (SR) with decades of temporal information (1996-2018) (Zhang et al.
2

---

transform simulation (transform can be simulated by using Published as a conference paper at ICLR 2024
Figure 1: Left circular figure shows equivalence between EFT and existing transformations (DFT (Sundararajan 2023). JFT (Loukas & Foucard, 2016), GFT (Ortega et al. 2018 Each directed arrow (e.g, to B), interprets
edge annotations). Right part shows timestamp-wise product between signals and graph structure.
Here, nodes of next timestep are connected by dotted arrows obtain the graph JD which can be used by GFT to simulate EFT (if graph is static).
2022, Huang et al.) 2023). Researchers (Li et al. 2020b Zhang et al. 2022 Jing al. 2022) have attempted to model the sequential recommendation task as a link prediction over dynamic graphs. DGSR (Zang et al. (022) is work that considers generic dynamic graphs over user-item interactions. However, the GNN-based methods described in this section including DGSR majorly employ low pass GNNs that limit the ability to model complex relations and are fundamentally restricted to focus on local neighborhood interactions (Balcilar et al.) 2020).
PRELIMINARIES
is employed obtain the frequency representation of sequence of signal values sampled at equal intervals of time. Consider signal sampled N intervals of time E [0, N 1] to obtain the sequence (r.). The DFT of x; is then given by X5 = Et= T&e -ie-ick with of the signal in the frequency domain. If we represent X the vector form of the signal, we can define the DFT matrix y such that X2 Tr
Discrete Fourier Transform (DFT) (Sundararajan 2023)
2st The transformed sequence Xs gives the values NN
Graph Fourier Transform (GFT) (Ortega et al. 2018 is a generalization of the Discrete Fourier Transform (DFT) to graphs. We represent graph as E) where V is the set of N nodes and & represents the edges between them. Denote the adjacency matrix by A. D the degree matrix, defined as (D); = E, (A) which is diagonal. The graph Laplacian graph is given by f. D A and the normalized Laplacian is defined eigendecomposition as: AP... Let X E R xd be the signal on the nodes of the graph. The Graph Fourier Transform X of X is then given as: X V.X.
= D AD- 1. The Laplacian(() (L) has the
The spectrum of a graph (of N nodes) a finite set consisting of N points À that form the eigenvalues of the graph's matrix representation M i.e. {} E [I ||| x. Similarly we can think of the (e=ppseudospectrum of a graph to the larger set (containing these N points) such that A Al has the least singular value at most Formally the pscudospectrum can be defined by the set {A C
Pseudospectrum:
||M - Z }.
Common Notations:
We denote by & the Kronecker sum, product respectively. (M) refers to the i-th row and j-th column matrix M. {.} refers to a sequence, of elements, time. M B refer to the Kronecker product and sum respectively, applied timestep wise.
4 THEORETICAL FRAMEWORK: AN OPTIMIZATION PERSPECTIVE
We begin by striving for a physical interpretation of frequency for dynamic graph systems. For this, we draw inspiration from energy diffusion processes and establish similarities with the vari- ation of signals static graphs. Consider graph G2 at time with node n; E V and nj & n, denoting the neighbors of n; at time t. We define a directed graph Tp with the graphs at all timesteps taken is and directed edge added from node at time (modulo T) to its
3

---

Published as a conference paper at ICLR 2024
corresponding node at time t. For continuous time dynamic graph the previous time would be represented by t -- dt (modulo T). Let Xx,.t represent the energy of the signal on node n, at time t. The flow of energy to the node n, time t can be represented by the divergence of the gradient (An,. X) of the energy. We define the variation of the signals at time and node n4 as follows:
nj Rn; |
27 (DEA),)
ax Denin
= (Xnj,t - xmn.)² (eaa))+((00))) ( dt
27
where
8x is the discrete edge derivative the collective dynamic graph JD. Considering A to be the Bengnj
finite difference between neighboring nodes in the joint graph, the global notion of variation (Sp (X) can be given by the p-Dirichlet form as follows
4
(x) = 1 P -= 1-
N
14
X
-
Σ
- (Xnne-Xn.n)) + (6Xm,,)) Sin
dt
Define Lr to be the Laplacian of the continuous ring graph representing the nodes at each timestep t E [0, 7i and connecting consequent nodes. Let Lg, be the Laplacian of the sampled graph at time t. In the discrete case the Laplacian LJp of TD can shown to be
(L3D)} = (Lr @ IN); + (Ir @ (L For the case of continuous time, this can be generalized to
(Lr @ b
(I)
(Lop) = LT @ IN + [|T @ {La.Hl = LLT
(2)
where R, E refers to the timestep wise Kronecker product and sum respectively and [1] refers to the matricization operation.
the discrete case this operation would convert RNTXTXN + RNTxNT, ordering from the last dimension first. We can now characterize the variation of signals JD similar to static graphs by the following result:
Lemma 1. (Variational Characterization of JD) The 2-Dirichlet S2(X) of the signals X on JD is the quadratic form of the Laplacian Lop of JD i.e.
(x = J NT
1 L Lxs((,,)vee(X)(())dd) Le 1=0
NT
(i)(X)
(3)
This implies that L 2 0 since (x) 2 O. which assures us of the existence of the eigenvalue decomposition. Additionally, the value of (x) is lower when the signal changes slower along the dynamic graph and higher when the signal changes faster. Hence, we can define notion of signal variation on the dynamic graph that similar to the variation of signals on static graphs. Consequently, the cigendecomposition of L characterizes signals the dynamic graph by projecting them onto the optimizers of (2().. This means that high- high-frequency components of the evolving dynamic graph represent sharply varying signals, whereas smoother signals will have higher magnitude in the now-frequency components. From an optimization perspective, we can view the maximum frequency as the optimal value for the below equation, i.e.,
NT
NT
Smax
max -.||=||||
(r(
J=0 Lo Lin(i,)a(()dddi--
max
The optimal solution I provides the basis for transforming a dynamic graph signal to obtain its maximum frequency component, denoted by Smax. We can obtain the next frequency values by optimizing equation in orthogonal directions. However, this approach has an issue the eigenvalue decomposition would have to be performed over large number of nodes. In a real world setting of temporal graphs with T' timesteps, this method would have complexity of (((NT))), which would be prohibitive considering large number of timesteps. To address this issue, we relax the objective in equation 4 to include solutions in the pseudospectrum. The solution is presented in the following result, upon which we can formulate a transformation method for temporal graphs.
Lemma 2. Consider the variational form x" L S x(i) 1 L (i. j)x(j)didj. The optimization problem f min
_g Xal- c+ has the optimal solution as you @ 2f, where
=.I[=||11
Xe is the optimal value of equation 4 you is the with optimal solution of the variational form of the ring graph, 2f is the I-th optimal solution to the variational form of the graph at time t, [s] + = max(s, 0) and (6).
4

---

Published as a conference paper at ICLR 2024
5 CONSTRUCTING AN EVOLVING GRAPH FOURIER TRANSFORM
In the previous section, we have outlined the theoretical framework for the evolving graph Fourier transform. We also obtained a sketch of the transform as solution to the optimization problem of the variational characterization with pseudospectrum relaxations. This enables us to obtain a simple and efficient form to compute. In this section, building upon the theoretical framework, we propose our formulation of the Evolving Graph Fourier Transform (EFT). From lemma 2 we obtain the orthogonal basis vectors of the desired transform matrix in terms of the kronecker product of the basis vectors of the Fourier Transform (P) and Graph Fourier Transform ()) Thus, lemma 2 helps to define the EPT in terms of the graph and time Fourier transforms:
EFT(S;:W) = Evo(fo:n) S t)e
(5)
where fg. w are the graph and temporal frequency components respectively, Sa(n, 4) the signal at node and time t. In terms of the matrix representation, the EFT could be expressed, using the Einstein notation (Albert al. 1916), as Kronecker product of DFT and GFT as (VD),
L r @ a. ,) [ which when applied to the columnwise vectorized signal fa gives the transform in the spectral space.
EFT is one of the solutions in the pseudospectrum of I,p as shown in lemma 2 There also exists other solutions and specifically considering the case where O obtain the solution to the exact EVD of LJD. Let V AD be the matrix whose rows form the right eigenvectors of LTD. Since V AD the absolute decomposition of LJp we term this as AD for brevity. We now define error bounds between L D and L AD-
Theorem 1. Considering bounded changes in graph G with N nodes over time T, the norm of the difference between EFT ( D) and AD ( AD) is bounded as follows: | - V ADIl ll S O (N TeWmazz: (DNG)mins (AAJ)min) the minimum difference between the eigenvalues of matrices LG and L respectivellll Le is the rate of change of LG and Wmaz = 2n and E E(Wmars AAG, AA2) =
(|icc)
where (AAj)min and (AAJ)min refer to
max
22
wmax AAO Ax,
-max.
The above theorem states that as the structure on the graph evolves infinitesimally, the difference between D and L AD is bounded from above by the change in the graph matrix representation (laplacian/adjacenny)) This property is desirable since it allows to approximate V AD. which is formed by the eigendecomposition of Lyp and has a physical interpretation, using the defined D that is easy to compute. The above bound is finite if 1) The rate of change of the graph with time is bounded. 2) The eigenvalues have a multiplicity of 1. In such cases, EFT characterizes signals on the dynamic graph by their proximity (projection) to the optimizers of S2 S2(X) defined in lemma 1 The physical implication of this is that applying EFT, the high-frequency components correspond to sharply varying signals on a dynamic graph, while frefureuenccy components correspond to smoother signals. Hence, the norm of the difference between EFT and AD are bounded from above by the rate of evolution of the graphs.
For computational purpose in real-world applications, the sampled form of EFT can be obtained by sampling T snapshots of the dynamic graph signal at uniform time intervals. We now get a dynamic graph {(),, &.), E {0. T) the edges (Ex) of which by definition evolves with time. We consider the node set V to be fixed, i.e., no new nodes are added. All the nodes (|V) = N) are known from the start, and the graph may contain isolated nodes. In case of node editions, we could create dummy isolated nodes with varying node signals and edge connectivity information. Without loss of generality, consider I-dimensional temporal signal, uniformly sampled at T intervals, residing on the graph nodes. Let E RN xT represent the temporal signal on the graph nodes. The Fourier transform (DFT) (with DFT matrix T independently for each node is DFT(X) = X Further, the GFT for the graph G, (V,, E,) at time t is given GFT(X,) L X,, where X, R is the signal on the graph nodes at time t. In order to compute the dynamic graph transform along the graph domain well as the temporal dimension, can collectively perform both the operations.
5

---

Published as a conference paper at ICLR 2024
Consider G E RNXNNT as the tensor containing the graph Fourier basis at each timestep. Then using Einstein notation (Albert et al. 1916), we write EFT as
EFF ((TT((()):))
X), (v7)
(6)
where j, k are tensor indices. Next, we aim to define a transformation matrix for EFT as in DFT and GFT. For this we make use of the Kronecker product (&) between tensors. We then get the matrix form of EFT as the following expression:
km (EFT(()):))) (0xn)(xxxx)) (Xo) (v (), (VT) (vr T 60 ( ( Tk
(7)
Thus, we have Jj-N+i = (Vr @ (v (G.))) 2h or = pz. In the above equations, X is the EFT of signal X over dynamic graph {G,), 2, E RNT are the columnwise vectorized form of X, &G RNNX and | DD RNNNNT is the EFT matrix over dynamic graph {Gr} with (VD) T Mc),
We remark from equation of EFT, that the following desirable properties (over the exact eigen- decompostion of the joint laplacian) are satisfied: 1) The equation imparts interpretibility to the frequency components, whether belonging to the time or vertex domain, as compared to the exact eigendecomposition. This is possible because we able to decompose the transform into the indi- vidual transforms of each domain. 2) The transform equation is computationally efficient as compared to the exact eigendecomposition of the joint laplacian. Specifically EFT reduces the computational complexity for the dynamic graph (I" timesteps) from a factor of ") to OT + T log(T)).
Having derived the EFT transform, we state and prove its properties in the appendix C The illustration between EFT and other transforms is in Figure | The figure shows transforms (GFT, JFT, DFT, EFT) in a circle, and arrows from one transform the next indicate that the source transform can be obtained by the destination transform using the simulation annotated on the edges. For example, the GFT of a ring graph (T) gives the DFT and thus the DFT can be simulated by GFT using graph T. Similarly DFT can be simulated by EFT when the number of nodes N = 1. Also the GFT of the temporal ring of static graph (topologically equivalent to a torus), where the nodes and edges remain constant with time, gives the EFT and vice versa (when time T 1). However when the graph structure changes with time GFT cannot be used to simultae EFT, Thus, we can also look at the EFT as generalization of the previous transforms. We briefly explain the task specific implementation of these modules in the below subsection and focus more on the representations and results in the following sections.
5.1 IMPLEMENTATION DETAILS
Having obtained the representations using the proposed transform, we intend to perform filtering in spectral space for dynamic graphs. Since our idea to perform collective filtering along the vertex and temporal domain in EFT, we need two modules to compute Y.. (vertex aspect) and yr (temporal aspect), respectively, equation 6 of EFT. We now briefly explain these modules with details in appendix [.2]
Filtering along the Vertex Domain: This module computes the convolution matrix D.. in equation -o Tx (Å), where O
6 The frequency response of the desired filter is approximated as À = k is the polynomial/fittr order, Tj is the Chebyshev polynomial basis, À 2A maximum eigenvalue and C₁ is the corresponding filter coefficients. The convolution of the graph signal X with the filter (X A4) gives the desired filter response in the vertex domain.
Amaz I, Amaz is the
Filtering along the Temporal Domain: After performing filtering in the vertex domain, aim to filter over the temporal signals using T as in equation 6 Formally, let X, E Rd be the signal of a node time f. Let X (X,) R. be the time ordered matrix of embeddings of the node. This converted the frequency domain (X E RT'dd using the matrix 7 as X X. Then we multiply X element-wise by a temporal filter Fr E RTxx to obtain the filtered signal X3 Fr X which is then converted back to the temporal domain by using the inverse transform V to get X, V X. X, is the filtered signal in the time-vertex domain of the dynamic graph.

---

Published as a conference paper at ICLR 2024
6 EXPERIMENTAL SETUP
Model Implementation and Datasets: Considering EFT is a spectral transform, we need a base model to induce EFT in it. We select transformer the base model inspired from (Zhou al.) 2022 Bastos et al. 2022) that induce learnable filters into a vanilla transformer for downstream tasks (implementation is inspired from (Zhou et al. 2022). hence, details are in appendix). To illustrate the efficacy of the representations obtained from EFT, we consider eight datasets. We name our model EFT-T. The first three (Amazon Beauty, Games, CD in Table 3 are large continuous time dynamic graph datasets from sequential recommendation (SR) setting (Huang et al. (023). spread over two decades. We inherit these datasets, dynamic graph construction process in SR setting, and metric from (Zhang et al., 2022). Other datasets (Pareja al. (020) (UCI, AS, SBM, Elliptic, Brain) are standard (discrete) dynamic graph datasets to understand the generalizability of our method and contain sequence of time-ordered graphs. Details on datasets, metries, and experiment settings are in Appendix (cf., Table 4). Experiment code and associated datasets are on Github: https: thub. com/ ansonb/EFT
Baselines:
We use baselines depending on the experiment setting for fairness. For SR link prediction,
strong baselines from previous best (Zhang al.) [002);; BPR-MF (Rendle et al. 2009).
FPMC (Rendle et al., 2010), GRU4Rec+ (Hidasi & Karatzoglou 2018). Caser (Tang & Wang 2018 J
SASRec (Kang& & McAuley 2018), HGN (Ma et al. 2019), TiSASRec (Li et al. (020a)), . SRGNN
(Wu et al. 2019). HyperRec Wang et al., 2020). FML (Zhou et al. 2022). and DGSR (Zhang al. 2022). For link prediction, node classification on discrete dynamic graph datasets, we rely on
state of the art approaches of this setting (Xiang et al. (022): GCN (Kipl & Welling (017). GAT
(Veličković et al. 2018). GCN-GRU (Pareja et al. 2020), DynGEM (Goyal et 2017). GAEN (Shi
et al. 2021 EvolveGCN (Pareja et al. 2020), dyngraph2vec (dg2vec) (Goyal et al. 2020).
7 RESULTS AND DISCUSSION
This section reports the various experiment results, supporting our theoretical contributions.
Denoising and reconstruction on synthetic dataset with pertur- Here, we aim to study whether EFT can better filter out noise from a dynamic graph than DFT (Sundararajan (023) and GFT (Ortega et al. 2018). The graphs are generated by sampling edge weights from a random normal distribution and evolved by perturbing the edge weights from the previous timestep. The graph signals are sampled from the eigenvectors of the graphs cach timestep, while the temporal signals are sampled from a sinusoidal signal. To add an element of complexity and realism, noise is induced along both the graph vertex and time signals (details in appendix D). As a result, the dynamic graph signals evolve with time while being induced with noise along both dimensions. We hypothesize that using EFT, which transforms collectively across time and vertex dimensions, will result in better denoising and signal reconstruction compared to using GFT or DFT, which only performs filtering in one dimension. Our hypothesis confirmed in Figure 2 which shows a decrease in error as the spectral energy of the signal is preserved while noise is filtered. Moreover, EFT yields comparable results to absolute transform (AD) while requiring less computational resources.
AD
bation:
DFT
0.00
1.00 Filtered Spectral Energy Fraction
0.25
0.50
0.75
Figure 2: Reconstruction er- ror on noisy synthetic data.
Compactness of EFT: Compaction refers to the ability of the transform to summarize the data compactly. transform with good compaction desirable as it summarizes the signals well in the frequency components, which can be used for efficient processing by downstream models. In this experiment, we verify the compaction properties of the proposed transform for the time-vertex frequencies the temporal mesh graphs (Grassi et al. 2017) concerning GFT and DFT. In order to test this, we remove varying percentile of the frequency components from the transformed frequency domain of signal X. We then apply the inverse transform obtain the signal X,.. We plot the error
XX-X-1 E vs the percentile of components removed. From figure 3a 3b we can see that EFT has a ||
lower error and better compaction and thus is able to summarize the data better than the baselines that only transform along a single dimension of vertex or time.
7

---

Published as a conference paper at ICLR 2024
Table I:
For link prediction on large temporal graphs of sequential recommendation setting, table shows our model comparison (EFT-T) on the metrics Recall @ 10 and NDCG@ 10. The best results are shown in boldface. The second best result has been underlined. The improvement of our method over the best-performing baseline is statistically significant with 0.05.
GRU4Rec+
SASRec
HGN
TiSASRec
FMLPRec
SRGNN
HyperRec
DGSR
EFFT
Recall@ 10
Beauty
43,98
42.64
48.54
48.63
46.87
47,47
48.62
34.71
52,40
53.23
Games
67.15
68.83
73.98
71.42
71.85
73.62
73.49
71.24
75.57
77.78
71.32
71.02
72.43
75.42
NDCG@10
Beauy
26.42
25.47
32.19
32.47
30.45
32.38
32.33
23.26
35.90
37.10
Games
45.64
43.93
53,60
49.34
50.19
51.26
53.35
48.96
35.70
58.65
CDs
45.85
49.23
49.34
48,97
53.31
48.95
47.16
51.22
54.99
Illustration of fil- tering tempo- ral mesh Figure 3c shows example of collective filter- ing of dynamic mesh representing dancer (Grassi et al.) 2017). Similar to Grassi et al. (017).
DFT
GFF
10a
10"
22
30
50
20
60
80
100
porcentile removad entios
porcentie of removed eriines
Original
Low Paac
Ware
(a) Dog
(b) Dancer
(c) Dancer
Figure 3: Representations on dynamic mesh datasets. Left (a,b): Reconstruc-
tion eтror on the datasets illustrating the compactness of EFT Right (c):
we implement the
following filters: (a) a low-pass filter that jointly attenuates high frequency components of the dynamic graph, and (b) a wave filter whose frequency response is described in Eq. (19) of Grassi et al. (2017). The former filter gives the frame the mesh with stiff manoeuvers, whereas the fluid filter produces fluid movements. This experiment shows that EFT enhance the frequency components non-linearly. This also hints towards why EFT performs better on evolving temporal graphs in subsequent experiments.
Illustration of filtering using EFT on dynamic mesh of a Dancer.
Performance comparison (continuous) large-scale tempo- ral graph datasets: The results on the large-scale SR datasets are in Table Jnd EFT-7 outperforms baselines all datasets. We note that our gains to the best base- line are higher in CDs, followed by the Games and Beauty dataset. We observe that the density of the graph and length sequences in the data increases (e.g., CD dataset), the performance of EFT: T enhances. We believe that as graph density increases, higher- order connections may encompass
Table Results for Link Prediction (UCI, SBM, AS) and Node Classification (Bm, Ell) tasks. Best values are in bold and second bests are underlined.
Datasets Metrics
SBM
UCI
AS
Ell F1
Bm
MAP
MRR
MAP
MRR
MAP
MRR
FI
GCN
0.189
0.014
0.000
0.047
0.001
0.181
0.434
0.232
DynGEM
0.168
0.014
0.021
0.106
0.053
0.103
0.502
0.225
GCN-GRU
0.575
0.186
dg2vec
0.098
0.008
0.004
0.054
0.033
0.070
0.464
0.191
dg2vee v:
0.159
0.012
0.020
0.071
0.071
0.049
0.442
0.215
GAEN
0.1828
0.008
0.000
0.049
0.130
0.051
0.492
0.205
EGCN-H
0.195
0.014
0.013
0.090
0.153
0.363
0.391
0.225
EGCN O
0.200
0.014
0.027
0.138
0.114
0.275
0.544
0.192
LED-GCN
0.196
0.015
0.032
0.163
0.193
0.469
0.471
0.261
LED GAT
0.182
0.012
0.026
0.149
0.233
0.384
0.503
0.150
EFT-T
0.250
0.024
0.055
0.181
0.672
0.689
0.616
0.308
noisy relations, challenge conventional baselines struggle to filter out, whereas our method ef- fectively handles this noise. Also, EFT effectively captures global interactions as considers the temporal aspect in the collective filtering module. Furthermore, compared to the FMLPRec model that induces DFT into transformer, EFT-T performs significantly better, concluding the necessity of capturing evolving spectra of temporal graphs. We also note that among the graph-based methods, SRGNN only considers connectivity information from the sequence graph, whereas HyperRec uses higher-order connectivity information. This indicates that not using the graph information effectively hampers performance but using higher-order connectivity without filtering to remove noise also degrades the results.
8

---

Published as a conference paper at ICLR 2024
Spyeni Dopt Thee
Oprer
Games
(a) 10call@10
(b) NDCG@10
(c) Recall@10
(d) NDCC@10
Figure 4: Effect of inducing 1) semantic noise in embeddings with and without filters (a-b) 2) structural noise in the form of graph perturbations with and without graph filters (c-d), on the performance of EFT. We consider large-scale SR setting.
Performance comparison on discrete temporal graph datasets: Zablle]summartt link prediction and node classification results. Across datasets, our model significantly outperforms all baselines, which focus on learning local dependencies. It illustrates our framework's effectiveness in filtering noise and amplifying useful signals in evolving temporal graphs.
Effectiveness of filtering module (Figure 4 Our approach focuses on capturing use- ful frequencies along vertex and time dimensions collectively while filtering the noise. Hence, in this experiment, we aim to understand effectiveness of the filters along both graphs (vertex) and time dimension in the presence of explicitly added noise.
Finstly, we induce semantic noise into the sys- tem by adding a random vector (sampled from normal distribution) to the node embeddings. Then, we run experiments on our model with and without learnable collective graph-time filters. To ensure a fair comparison, we keep the parameters in both models the same and simulate the no-filter configuration by using uniform distribution for the frequency re- sponse (all-pass filter). In the presence of noise, the performance configuration with filters is much better (p < 0.01) than that without any filtering. Next, we induce struc- tural noise into the system by adding random nodes/edges. We observe that on inducing structural noise, the performance of the con- figuration with graph filters is statistically better (p < 0.01 using a paired t-test) compared to the one without, confirming that collective filtering is needed to be robust structural noise in dynamic graphs. Additionally, we plotted the filter frequency responses of EFT on the Games and CDs datasets in Figure The figure shows dominating low-frequency response and higher-frequency components, indicating global aggregation for the long-range interactions.
06
05
06
04
02
2g
Time Freet
Vertez Fron
10
2
Veiter
05
10
15
(a) Games
(b) CDs
Figure 5: Filter frequency responses learnt by EFT on dynamic graph datasets. The x-axis shows vertex frequency (0-2), y axis shows the normalized temporal frequency and z axis shows the magnitudes of the normalized frequency response.
CONCLUSION
In this paper, we introduce a novel approach to transform temporal graphs into the frequency domain, grounded on theoretical foundations. We propose pseudospectrum relaxations to the variational objective obtaining a simplified transformation, making it computationally efficient for real-world applications. We show that the error between the proposed transform and the exact solution to the variational objective is bounded from above and study its properties. We further demonstrate the practical effectiveness for temporal graphs. the current scope, we do not consider generic signed and directed graphs. To mitigate this, we suggest future works explore generalizing the Laplacian and the resulting transform to such graphs, leveraging techniques proposed in (Mercado al.] [2066] Cucuringu al. (221). Our work opens up possibilities for dynamic graph analysis and representation learning, and we encourage researchers to explore potential of EFT as a spectral representation of the evolving graph in downstream graph representation learning models.

---

Published as a conference paper at ICLR 2024
REFERENCES
Einstein Albert, W Perrett, and G Jeffery, The foundation of the general theory of relativity, Ann. Der Phys, 49:769-822,, 1916.
Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in spectral perspective. In International Conference on Learning Representations, 2020.
Nikolaos Bastas, Theodoros Semertzidis, Apostolos Axenopoulos, and Petros Daras. evolve2vec: Learning network representations using temporal unfolding. In MultiMedia Modeling: 25th International Conference, MMM 2019, Thessaloniki, Greece, January 8-11, 1, 2019, Proceedings, Springer, 2019.
Part 25, pp. 447-458
Anson Bastos, Abhishek Nadgeri. Kuldeep Singh, Hiroki Kanezashi, Toyotaro Suzumura, and Isaiah Onando Mulang'. How expressive are transformers in spectral domain for graphs? Transac- fions on Machine Learning Research, 2022. ISSN 2835-8856. URI. https://openrevieewnnee
foorm??dd-RRsettmm
Anson Bastos, Abhishek Nadgeri, Kuldeep Singh, Toyotaro Suzumura, and Manish Singh. Learnable spectral wavelets on dynamic graphs to capture global interactions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp- 6779-6787, 2023.
Jonathan M. Blackledge. Chapter 2 2d fourier theory. In Digital Image Processing, Woodhead Publishing Series in Electronic and Optical Materials, pp. 30-49. Woodhead Publishing, 2005.
Defu Cao, Yujing Wang, Juanyong Duan, Ce Zhang, Xia Zhu, Congrui Huang, Yunhai Tong, Bixiong Xu, Jing Bai, Jie Tong, et al. Spectral temporal graph neural network for multivariate time-series forecasting, Advances in neural information processing systems,
2020.
Defu Cao, Yujing Wang, Juanyong Duan, Ce Zhang, Xia Zhu, Conguri Huang, Yunhai Tong, Bixiong Xu, Jing Bai, Jie Tong, and Qi Zhang. Spectral temporal graph neural network for multivariate time-series forecasting, 2021.
Jinyin Chen, Xucke Wang, and Xuanheng Xu. Gc-lstm: Graph convolution embedded Istm for dynamic network link prediction. Applied Intelligence, pp. 1-16, 2022.
Cheng Cheng, Yang Chen, Yeon Ju Lee, and Qiyu Sun. Svd-based graph fourier transforms on directed product graphs. IEEE Transactions on Signal and Information Processing over Networks, 9:531-541, 2023. doi: N0.1199//IINN.2233329955
Mihai Cucuringu, Apoorv Vikram Singh, Déborah Sulem, and Hemant Tyagi. Regularized spectral methods for clustering signed networks. The Journal of Machine Learning Research, 22(1): 12057-12135, 2021.
da Xu, chuanwei ruan, evren korpeoglu, sushant kumar, and kannan achan. Inductive representation learning on temporal graphs. In International Conference on Learning Representations, 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 19.3844-38522 2016.
Saul I. Gass and Michael C. Fu (eds.). US, Boston, MA, 2013. ISBN 978-1-4419-1153-7.
Kuhn-Tucker (KKT) Conditions, pp. 833 133.834. Springer
Palash Goyal, Nitin Kamra, Xinran He, and Yan Liu. Dyngem: Deep embedding method for dynamic graphs. IJCAI Workshop on Representation Learning for Graphs, 2017.
Palash Goyal, Sujit Rokka Chhetri, and Arquimedes Canedo. dyngraph2vec: Capturing network dynamics using dynamic graph representation learning. Knowl. Based Syst. 187, 2020.
Francesco Grassi, Andreas Loukas, Nathanaël Perraudin, and Benjamin Ricaud. A tire-vertex signal processing framework: Scalable processing and meaningful representations for time-series on graphs. IEEE Transactions on Signal Processing, 66(3):817-829 2017.
10

---

Published as a conference paper at ICLR 2024
David K Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129-150, 2011.
Balázs Hidasi and Alexandros Karatzoglou. Recurrent neural networks with top-k gains for session- based recommendations. Proceedings of the 27th ACM international conference on information and knowledge management, pp. 843-852, 2018.
Shenyang Huang, Farimah Poursafaei, Jacob Danovitch, Matthias Fey, Weihua Hu, Emanuele Rossi, Jure Leskovec, Michael Bronstein, Guillaume Rabusseau, and Reihaneh Rabbany. Temporal graph benchmark for machine learning on temporal graphs. arXiv preprint arXiv:2307.01000 2023.
Junzheng Jiang, Hairong Feng, David B. Tay, and Shuwen Xu. Theory and design of joint time-vertes nonsubsampled filter banks. IEEE Transactions on Signal Processing, 69:1968-1988 1982, 2021. doi: N0.1109/TSP.2221.33666
Mengyuan Jing, Yanmin Zhu, Yanan Xu, Haobing Liu, Tianzi Zang, Chunyang Wang, and Jiadi Yu. Learning shared representations for recommendation with dynamic heterogeneous graph convolutional networks. ACM Transactions Knowledge Discovery from Data (TKDD), 2022.
Wang- Cheng Kang and Julian McAuley. Self-attentive sequential recommendation, In 2018 IEEE international conference on data mining (ICDM), pp. 197-206. IEEE, 2018.
Bünyamin Kartal, Eray Özgünay, and Aykut Koç. Joint time-vertex fractional fourier transform, 2022.
Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth, and Pascal Poupart. Representation learning for dynamic graphs: A survey. J. Mach. Learn. Res., 21 (70):1-73, 2020.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, 2017.
Takashi Kurokawa, Taihei Oki, and Hiromichi Nagao. Multi-dimennional graph fourier transform, 2017.
P. Lancaster and H. K. Farahat. Norms on direct sums and tensor products. Mathematics of Computatioo, 26(118):401441 1972. ISSN 00255718, 10886842.
Jiacheng Li, Yujie Wang, and Julian McAuley. Time interval aware self-attention for sequential recommendation. In Proceedings of the 1 13th international conference on web search and data mining, pp. 322-330, 2020a.
Xiaohan Li. Mengqi Zhang, Shu Wu. Zheng Liu, Liang Wang, and S Yu Philip. Dynamic graph collaborative filtering. In 2020 IEEE International Conference on Data Mining (ICDM), pp. 331. IEEE, 2020b.
Andreas Loukas and Damien Foucard. Frequency analysis of time-varying graph signals. In 2016 IEEE Global Conference on Signal and Information Processing (GlobalSIP), pp. 346-350. IEEE, 2016.
Chen Ma, Peng Kang, and Xue Liu. Hicrarchical gating networks for sequential recommendation. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 825 825-833, 2019.
Yao Ma, Ziyi Guo, Zhaocun Ren, Jiliang Tang, and Dawei Yin. Streaming graph neural networks. In Proceedings of the 43rd international ACM SIGIR conference on research and development in information retrieval, pp. 719-728, 2020.
Arash Golibagh Mahyari and Selin Aviyente. Fourier transform for signals on dynamic graphs. In 2014 48th Asilomar Conference on Signals, Systems and Computers, pp. 2001-2004. IEEE, 2014.
Franco Manessi, Alessandro Rozza, and Mario Manzo. Dynamic graph convolutional networks. Pattern Recognit., 97, 2020.
11

---

Published as a conference paper at ICLR 2024
Pedro Mercado, Francesco Tudisco, and Matthias Hein. Clustering signed networks with the geometric mean laplacians. Advances in neural information processing systems, 29, 2016.
Apurva Narayan and Peter HO'N Roe. Learning graph dynamics using deep neural networks. PPAC--PppesOOnLine, 510liine,,1100 51(2):433-438, 2018.
Antonio Ortega, Pascal Frossard, Jelena Kovačevié, José MF Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106 (5):808-824) 2018.
Chao Pan, Siheng Chen, and Antonio Ortega. Spatio-temporal graph scattering transform. In International Conference on Learning Representations, 2020.
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma. Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao B. Schardl, and Charles E. Leiserson. Evolvegen: Evolving graph convolutional networks for dynamic graphs. The Thirty-Fourrty AAAI Conference on Artificial Intelligence, AAAI Press, 2020.
AAAI 2020, pp.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary Vito,,, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and I Lars Schmidt-Thieme. Bpr: Bayesian personalized ranking from implicit feedback. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pp. 452-461, 2009.
Steffen Rendle, Christoph Freudenthaler, and Lars Schmidt-Thieme. Factorizing personalized markov chains for next-basket recommendation. In Proceedings of the 19th international conference on World wide web, pp. 81 311-220, 2010.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning dynamic graphs. arXiv preprint N00.:2000.10637, 2020.
Purnamrita Sarkar, Deepayan Chakrabarti, and Michael Jordan. Nonparametric link prediction in dynamic networks. arXiv preprint 1206::2006.6394 2012.
Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson. Structured sequence modeling with graph convolutional recurrent networks. CoRR, abs/1612.07659, 2016. URL
Min Shi, Yu Huang, Xingquan Zhu, Yufei Tang, Yuan Zhuang, and Jianxun Liu. Gaen: Graph attention evolving networks. IJCAI, pp. 1541-1547, 2021.
David I Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst.
The emerging field of signal processing graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine, 30(3):83-98, 2013.
Duraisamy Sundararajan. The discrete fourier transform. In Signals and Systems, pp. 125-160. Springer, 2023.
Jiaxi Tang and Ke Wang, Personalized top-n sequential recommendation via convolutional sequence embedding. In Proceedings of the eleventh ACM international conference on web search and data mining, pp. 565-573, 2018
Terrence Tao. When are eigenvalues stable?, 2008. URL https::/teerryttoovooorrrrsss com/
stable//
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Marisel Dillafañe-eelgatee and Selin Aviyente. Dynamic graph fourier transform temporal functional connectivity networks. In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 949-953, 2017.
12

---

Published as a conference paper at ICLR 2024
Jianling Wang. Kaize Ding, Liangjie Hong, Huan Liu, and James Caverlee. Next-item recommenda- tion with sequential hypergraphs. In Proceedings of the 43rd international ACM SIGIR conference research and development in information retrieval, pp. 1101-1110, 2020.
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: graph-centric, highly-performan package for graph neural networks. arXiv preprint #rXiv:1909.0/311 2019.
Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. In International Conference on Machine Learning, pp. 23341 -23412 PMLR, 2022.
Shu Wu, Yuyuan Tang, Yanqiao Zhu, Liang Wang. Xing Xie, and Tieniu Tan. Session-basee recommendation with graph neural networks. In Proceedings of the AAAI conference artificial intelligence, volume 33, pp. 346-353, 2019.
Xintao Xiang. Tiancheng Huang, and Donglin Wang. Learning to evolve on dynamic graphs (sa). In Phirty-Sixth AAA/ Conference on Artificial Intelligence, AAAI 2022. AAAI Press, 2022. URL /ttps://arxiv. wwtg///////p///// /2110000022100000.2.2. pdf
Sijie Yan, Yuanjun Xiong, and Dahua Lin. Spatial temporal graph convolutional networks for skeleton-based action recognition. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018
Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. arXiv preprint 1XXiv:170.004777 2017.
Menggi Zhang, Shu Wu, Xueli Yu, Qiang Liu, and Liang Wang. Dynamic graph neural networks for sequential recommendation. IEEE Transactions on Knowledge and Data Engineering, 2022.
Kun Zhou, Hui Yu, Wayne Xin Zhao, and Ji-Rong Wen. Filter-enhanced mlp is all you need for sequential recommendation. In Proceedings of the ACM Web Conference 2022, pp. 2388-2282 23999, 2022.
13

---

Published as a conference paper at ICLR 2024
A PRELIMINARIES
Here we give an extended discussion of the preliminarics which could not be accommodated in the main paper due to space constraints.
A.1 DISCRETE FOURIER TRANSFORM
The Discrete Fourier Transform (DFT) is used to obtain the frequency representation of sequence of signal values sampled at equal intervals of time. The magnitude and phase of the frequency components are obtained by multiplying the signal values by complex sinusoids of the respective frequencies. Consider signal sampled N intervals of time t [0, N obtain the sequence {. The DFT of 2₁ is then given by,
2nt
X
Σ
24C Tickhuik Kork
W.
8
The transformed sequence X3 gives the values of the signal in the frequency domain. If we represent X as the vector form of the signal we can define the DFT matrix y such that Xx = r Thus X the complex valued spectrum of {0a} at frequency w/. We can perform filtering by removal of noisy frequencies in this spectral domain. As required by signal processing applications we can then obtain the signal sequence in the time domain from the frequency domain {Xx} using the Inverse Discrete Fourier Transform (IDFT) as,
2nk N
Xeetwat
N
k=0
A.2 GRAPH FOURIER TRANSFORM
Graph Fourier Transform (GFT) a generalization of the Discrete Fourier Transform to graphs. We represent graph (V.& E) where V is the set of N nodes and & represents the edges between them. Denote the adjacency matrix by A. In the setting of an undirected graph A would be a symmetric matrix. D is the degree matrix, defined (D) E, (A)is. which is diagonal. The Laplacian of the
graph is given by L D-A A and the normalized Laplacian L is defined L / -- D ADD The Laplacian(L) L) can be decomposed into its orthogonal basis, namely the eigenvectors and eigenvalues as:L T A where U is N x N matrix whose columns the eigenvectors corresponding to the eigenvalues λ1, ........ AN and A diag(()) (()1, Ag,.... on the nodes of the graph. The Fourier Transform X of X is then given as: X VG Similarly, the inverse Fourier Transform defined as: X L G Note Ii is the transposed conjugate of G... By the convolution theorem [Blackledge] 2005), the convolution of the signal X with filter G having its frequency response as G is given by (below, represents the mhth node in the graph, G represents the tt eigenvector or column of &))
(a.....,,.), An]). Let X e Nxd be the signal
N
(X ()
Σ X()))(4)
k=
(10)
* (m)) (H)))))))))
G NCG-VaCh CV
Note that sequence can be considered as grid graph and for this graph the GFT specializes to the DFT i. V Va.
B THEORETICAL PROOFS
In this section outline the proofs stated in the main paper and briefly diseuss the implications etc. that could not be accommodated in the main paper due to space constraints. For completeness we restate the results.
14

---

Published as a conference paper at ICLR 2024
Lemma 1. (Variational Characterization of JD) The 2-Dirichlet S2(X) of the signals X on JD is the quadratie form of the Laplacian Lyg of JD i.e.
S2(X) = veel ( I.Jo vee(X)
Proof. The p-Dirichlet form is given by
1 Sp(X)
D X1,
p
@xxmn Ol
2
Σ
(Xnsa - Xmmo)2+ +
dt
P
Ny
Thus the 2-Dirichlet form is
S2(X)
1=0
1
Σ
(Xujit Xmni)² +
(8Xmit
dt Öt
2
N
(6Xmar)?
Gi 55
1
Xn Xmne)?
+
2
1=0
n=l
We consider the above sum in two parts. Taking the first part we have
N
2/
Σ
(Xngd
-Xm.))²
2
1=0
==1
Gr
N
x2 -2 =nx Xmnt + x2 X2.is)
2 0
nky MR:
x2 nyit Xny,t # Xayx Xny.t Xnyt + X2
2 )
mest)
(=0
N
(Xnyit (Xnz, - Xnus) + Xnnd (Xnit Xny.))
2 t=0
n=
1 T
Σ
(Xnje (Xnjit Xnni))
Snn,
N
(Xnsit (Xnzit - Xnne))
1=0 n=1
Go
125
vec(X) (Ir @ LG. )vc((X)
15

---

Published as a conference paper at ICLR 2024
Considering the second part which is the ring graph along the time dimension we have
Xn Xneit)
2
x2
Ri Ri Xm Xnnt + X2 nid
2
N
2x
Didt-dt - 22 Xmst-de # Xniit)
... Redistribbuiing terms
2
1=0
n=l
N
x2
R X Xn Xnnt
1=
n=1
Xn (Xn,,t-t Xnsit)
xee(X) (X) (Io s0 IN ux))ee(X)
Combining the results of the 2 parts get the below result
S2(X) vec(X) (IT @ (eE))e(() vec(X) ( (LT @ IN)uec(X)
ved(X) (IT & La, + + @ IN) vea(X)
vec(X) L.p
as required.
This implies that L5p = O. We can see that slower the changes in the signals along the dynamic graph smaller the value of (2) and vice versa. Thus we have notion of variation of signals the dynamic graph similar to the case of static graphs. The eigen decomposition of L therefore characterizes signals on the dynamic graph by its projection the optimizers of (2 ). In other words, high collective dynamic graph frequency components inform of the presence of sharply varying signals and smoother signals will have higher magnitude in the low frequency components. Next we provide solution to the relaxed pseudospectrum objective i
Lemma 2. Consider the variational form x Lgn = S xii) 1 LJo (1.j)) The optimization problem f min
||x L.gL >al--ee... has the optimal solution yo @ 2t, where ..|[=||S)
Ag the optimal value of equation optimal solution of the graph at time t and c 06)).
4 Vo is the w-th optimal solution the ring graph, 2f is the 1-th
Proof. We begin by considering the variational characterization of I.Jp which given by the below equation
NT
1 1-0
NT
X Mar 2.1|*||51
LJo (oo((.))x()ddid max x" L 0.11a1111
(11)
1=0
Note that in the objective, x²' LJo is convex since LJD 2 0 and thus V2 (x" LTDz) 2L.Jo > 0.
Also, we can check that ||= is convex. Thus applying the KKT conditions (Gass & Fu 2013)
to the lagrangian L = x² L., + A([1=||2 - -1), we get the below equation
==
(12)
We recognize from the above equation that X, is the eigenvalue of LJD and is the correspond- ing eigenvector. However the computation of this exact solution is computationally costly and here ineterested in finding an efficient form of the solution to the objective with the pscudospectrum relaxation. As already seen, the pseudospectrum can be defined by the set
(A C
[[Tpp A 2 }} or equivalently (A E C [[(Top - >/)I| & c), where
16

---

Published as a conference paper at ICLR 2024
||-I| is the operator norm. Thus we have that for the pseudospectrum, there exists unit vector e such that [L Af)ul I and so Ι - > S c. This shows that the <- neighborhood of the spectrum of Lig is contained in the pseudospeetrum i.c. if À is in the pseudospectrum of L it is in the neighborhood Aç. We would now like to find a solution residing in the pseudospectrum of L.pp
We have {Lg, } RNNNNT to be the Laplacian of the graphs at each timestep with eigenvalues X where E N, E (0, LT E RT'x be the Laplacian of the time adjacency matrix with eigenvalues H4 where j E T. The Laplacian the collective graph JD is expressed as
Ltp Lr + {LG.} = Lr IN [IT X {LG.)l
In the above equation, M is the timestep wise Kronecker product and operator [.] represents the vectorization. If is discrete this vectorization can be thought of as a reordering from RATXTXN - NNTxNT Consider 01, O2....ap to be the linearly independent right eigenvectors of Ly and bi, b6,bg bg. ... .,.,,,, to be the linearly independent right eigenvectors of LG,- Consider the vector y lax œ {6f where {b{} represents the set of eigenvectors of Laplacian at time i.e. LG, and the operator & is again timestep wise followed by vectorization. Then we have
LJo Lr @
INY + [/r X HL
=Lr [ox X {b/ [r & (La. Ma {bA)
=(LT {Ix) [b(1)) + (Ir @ (La. Ja X (b)))
[LTuR X [Ix)D((M)]++ [/raa & (La,D(0))
(uulax X (((1)) + Iax 8 (АК(Н))
(uulax X [b(E)] [ax (Н
(lax X (6))]diag((x=))+ + [ax & (1) Jdiag( ((A))
([ax X (6)) +
where D indicates timestep (column) wise product and diag(-) operator converts a vector to a diagonal matrix. Now considering the graph the O-th timestep having eigenvalue A9, we interested in verifying the pseudospectrum condition for μu + {9). We thus have to find the upper bound for
[L.0 (μx + \|
In order to bound the above expression we consider the vector [ax & (b/))- We have from the above equations,
L - (ux + >P)yl = ([ax M (b))diag((ux + X - (14 + xP))))
(13)
We would like study the rate of change of the eigenvalues the graph changes. Consider a normal matrix A of which the eigenvectors ..,.... Un form basis of C", Also we consider wi,..., Wn. be the dual basis, i.e. wI 0h 6zk for all < j, k < n, where 8jk the Kronecker delta and
1, j
65h = 0,
otherwise
Since the eigenvectors form a basis we can represent any vector as linear combination of as u Σy=1 Oz Also we have w E==r,wuf aj. We thus have the below Un .,....,
equation
Σ (wf
(14)
for any vector u E C". We know the below relation due to Vi being the eigenvector of A with eigen value 2ς
Are- = Agei
(15)
We also can write the following in terms of the dual basis (since A is normal matrix)
w Σ Ayuiuru
(16)
w = A
17

---

Published as a conference paper at ICLR 2024
We now differentiate 21 using the product rule of differentiation to get
Av + Adg ' + Ag.i%
(17)
Taking the inner product of the equation 23 with wT. and using 22 we obtain:
Au + Adx = dRok + A
" Aux + / Adx = widRre + wid
Ar Aw ix inwRon AuugiN
(18)
w Avx = d
ds w Avx
Assuming Xg be the eigenvalue the start, we can get the value after time by simply integrating as follows,
\ Xl + L wK dt
(19)
Thus from the above result and equation
13 we have
|| | 1/ (uu + X w/|l
|| [ax X {bi)diog + Xi - (ux + (
[ax X (bi)) -PD))|
lax {b]]]diag( l' wx wAdn
||| lax & [bi3]l diag( ( ALAcen dt)
1 L. wxAuen dtat
1-" J [Ilan deet
1-" L." ['Ilallaaad
8
1 T
8NTdt
S 2
(6))
[L y (14: >p)e/| cc
|LD (#k + XP)l| S
Thus μe + X is in the pseudospectrum of L and so [ag X {b is one of the solutions to the objective with the pseudospectrum relaxation. Thus it follows that [ { Lt G. }l forms basis of the solution to the defined objective, where y and L G. have aj and bf as their row spaces respectively.
The above result gives the definition of EFT in terms of the Kronecker product of the Time Fourier Transform and the Graph Fourier Transform of the graph at each time. While both EFT and AD are solutions the pseudospectrum relaxed objectives they are not equal in general. To see this,
18

---

Published as a conference paper at ICLR 2024
first need to look at the cigenvectors of L. Let V AD be the matrix whose rows form the right eigenvectors L3p. Below we state and prove the result of equivalence between V D and v AD for the general case of dynamic graphs using counter example
Remark 1. In general, the collective dynamic graph fourier transform defined by the operator L D does not form the eigenspace of the spectrum of Ljp i.e. D + V AD-
Proof. it is sufficient to show a single counter example to conclude the statement.
Consider the below weighted adjacency matrix for a certain graph at time to
1
0.5
Go
0.5
1
Let this change to the following in the next timestep t
1
0.6
G1
0.6
1
The Laplacian LJp given by
1.5
- 0.5
-1.
-0.
00.
1.5
-0.
-1.
Ltp
-1.
0.
1.6
00.6
0.
1.
0.6
1.6
The EFT matrix v D is
50.5
00.5
0.5
0.5
0.5
0.5
00.
-0.5
T
0.5
0.5
0.5
00.5
0.5
0.5
0.5
0.5
Similarly the matrix V AD comes out be the following (upto sign and row wise permutations)
00.47
-0.47
-0.52
0.52
0.5
0.5
-0.5
-0.5
AD
0.52
-0.52
0.47
-0.47
0.5
0.5
0.5
0.5
From the above we can see the two matrices differ and so we have a counter example.
From the above result we can see that in the general case of dynamic graphs the defined EFT and the eigen decomposition the defined Laplacian I,pp are not the same. Thus we can have an alternate definition of the collective dynamic graph fourier transform in terms of the decomposition of the joint Laplacian L We term V AD as the Absolute Drcomposition or AD for brevity.
Both EFT and AD have their advantages. EFT has simple primal definition and is easy to compute whereas AD has beautiful physical interpretation. Even though EFT and AD are not exactly the same, in order have desirable properties of both under what conditions the two transforms can be used interchangeably upto the approximation error. We work under the below assumptions for weighted graphs in order bound the two transforms:
define approximation bounds that inform
The rate of change of the graph with time is bounded
2. The eigenvalues of the graph Laplacian any given timestep and between timesteps has multiplicity of 1
The condition is required for stability of the bound and can be enforced for example by adding random perturbations to the matrix.
Based these assumptions state and prove the bounds between EFT and AD below
19

---

Published as a conference paper at ICLR 2024
Theorem 1. Considering bounded changes in graph G with N nodes over time T, the norm of the difference between EFT D) and AD ( AD) is bounded as follows: D - v AD S
o NiTwher N (AAG)min (AAJ)min
((
where (AAG)min and (AXj)ma refer to the minimum
max
difference between the eigenvalues of matrices Lg and Tog, respectively, Tg is the rate of change of LG and Wmax 2T.
Proof. Consider L, to be the Laplacian of collective graph when the graphs are static with time. We can show this, in a similar manner as Ly,to be L, = LT @ IN + IT @ Lc. where LG is the Laplacian of the static graph. Let y be the matrix whose rows form the left eigenvectors of LJ. Now we consider the graph to change infinitesimally with Lg as the starting state the Laplacian. We intend to bound the frobenius norm
L D ADDII We can manipulate this as follows
V D
1 ADDl
= / D AD + 1 M/ll
P V V, ADl
< PD P + _ 1 ADI
We thus find the bound in two parts first for the error between v D. v and second for the error between J, AD.
In order to bound the matrices (which are formed by the eigenvectors) we first attempt to bound the vectors forming the matrix. For this we study the rate change of the vectors with time (as the graph evolves) using the language of calculus. For deeper insights into this and the stability of cigenvectors/values we refer the interested reader to (Tao 2008). Consider a normal matrix of which the eigenvectors U1 U1..... Un form basis of C" Also consider Wi....; Wh be the dual basis, i.e. wfth Uk = 6zk for all 1 S j, < n, where dJز is the Kronecker delta and
f1 0,
1, if = k
85*
otherwise
Since the eigenvectors form basis we can represent any vector as linear combination of U1...., Un as u Σj=1 ayoz. Also we have wÿu Iل= = aj. We thus have the below
equation
Σ (wfu)oy
(20)
for any vector u E C We know the below relation due to U2 being the eigenvector of A with eigen value Aş
Are AR We also can write the following in terms of the dual basis (since A is normal matrix)
(21)
w A Σ Ayoeura
(22)
w A = AuuF
We now differentiate 21 using the product rule differentiation to get
Av + Adg de + Ag
(23)
Taking the inner product of the equation
23 with ww. and using 22 we obtain:
Ave + Add deen dedi
wx Avn + wi Adx = widkan + wfAnis
wrAor + \ iz = nnwbor Auwfis
(24)
1 ArA = dn
Ås = w An
20

---

Published as a conference paper at ICLR 2024
In our since A is normal, we have the eigenbasis Up orthonormal set, and the dual basis wk identical to Uj.
We are interested in how the eigenvectors change with time. Taking the inner product of equation 23 with 3 for j # h, we get
Avn Adx ANVR + Au dx
w3 A + wfAdx = w 1e02 + uz dx is
wr Avx Azw3 the dawfen + w An
u3 + Awweex the = wg Avdi
(25)
w Aus + Ayw3ix wz de = 0
w _n + (2y - ) őu = O
w Ave wjdx (Ax Xy)
Using the above in 20 we obtain the following
0z =
(wfix)) )
02
(w iu)uz + (wfin)ox
(26)
Σ w Av
Ak X3 Vy (widx)en
1
We consider the change in A so that the resulting matrix also normal. Thus the eigenvectors of the resulting matrix will also be orthonormal. This imples all the vectors lie on the surface of the unit sphere in C" and so the change in the eigenvectors should be along the surface of this sphere. As such Årg will be tangential to the sphere at U and so etg Uh = O. Note this need not be the case in general if we consider non-unit vectors (that could also be eigenvectors). Thus can represent dn = Ouk + jek by Thus we have
0k +
Ebioj biuj jzk
whon
wt
Σ byug
Σ
by byuttu
Jock
wiikk
21

---

Published as a conference paper at ICLR 2024
Using the above equations and the consideration that ||uy||
1 we have
: AvR
AR
Xj
57t
W Aus
||
Σ
AK X3* 0/
jy
W Auk
A X3 U/
Au
$ Σ
|10/| 11
A A/
jy
Since consider orthonormal vectors ||0y|| = 1
3 AvR
|
5fk
W Avn
1 Σ
1 21
((A)
1 ا31l
jz
A
D Xللl
A
min
N
1
AA
AAA)
min
where (.) is the operator norm and (AX) min the absolute of the minimum difference between the eigenvalues of A. in the above we have seen how the change in eigenvectors is bounded by the change in the matrix. Using this result we now attempt to bound the change in the required transform matrices.
For the first part we bound D Fll Let Ae represent the (infinitesimal) change in the eigenvec- tors of Le in time t and let Au; be the infinitesimal change per unit time in the vector at step i. Thus using the triangle inequality we have the below equations
|
Σ
|
S f1
|
22

---

Published as a conference paper at ICLR 2024
Using the above derived incquality || - (AA) min
N-1
| for LG we have
A - S.1 (AN) miin
N 1
| dt
J. N -
(1(
dl
(AX) min
max
Finally taking the maximum norm of the rate of change LG over the entire time duration we have the following
N-1
(1 maz J. dt
|
min
N -1 (1]
|| | S (A)) min
maxr
O - 1)T
(|Lo))
AA)
max
where (io) is the maximum of the norm of the rate of change of LG over all timesteps considered and we absorb the total time into the constant factor considering finite time. Thus we have,
1 c
Σ |1ul1 2
VN(N - LYT
(ic)
(A)G) min
mar
(NNTT) (i.))
(DGG) min
Thus using theorem from 1 D
Lancaster & Farahat
1972) and the fact that || 1 have,
L J
p (1 G &G)))
N 8 (Y va)ll
1011111 =c))l²)) $
|
1(VG. (al)lP)
$ (Awc.11)
O(NET)
(AAG) mnn
max
O(NTT)
La
Wmar
(AdG)men
max
O
D 1
Lc
(AAG)
max
23

---

Published as a conference paper at ICLR 2024
where T is the time duration over which the evolution ghof the graphs is considered. For the second part we can show that
ADI
V
Namus
||0il
NWmax
Numax - 1)T (Ln)
(Ads)min
((NWmez)) (
(is)
(A)J) A min
max
Also we have,
L Lr 1 LG
LT @ IN + Ir @ La
L, IT & La
ty Ir 2 LG
[ || |K
| (dw) 3 |
v w
LG
O(N3)
(irs)
M PADl - (AAs) mein
O w22 (io)
(A))) min
mas
Combining the two parts we get the result
I L Abl
F + [ L ADDl
N N warr
NET T max
(|EEd)) man
(27)
Jmin
(A)s) main
For the discrete case this bound becomes
D V AADI 0o
(NT) (AAG) mmi
2NT
(|
(28)
(AAJ)min
max
We thus see that as the graph evolves infinitesimally the difference between WD and AD is bounded from above by the change in the graph matrix representation. This is desirable since it allows to approximate V AD (formed by the eigendecomposition L which has a physical interpretation using the defined V D which is simple to compute, when the graph changes in a stable manner. In such cases, EFT therefore characterizes signals on the dynamic graph by its proximity (projection) to the optimizers of S2(X) meaning high (collective dynamic graph) frequency components correspond to sharply varying signals and low frequency components to smoother signals. Having derived the transform, next state and prove the properties of the proposed transform in the next section.
24

---

Published as a conference paper at ICLR 2024
C PROPERTIES OF PROPOSED TRANSFORM
Having designed the Evolving Graph Fourier Transform, the transform. The below defines some properties of EFT before learning its representations and applying to downstream tasks (proofs are in appendix section Bp.
look at some of the properties of
Property 1. (Equivalence in special case) Consider D to be the time Fourier transform and GG to be the Graph Fourier transform time Let V Jo be the Graph fourier transform of JD. In the special case of Ge G1 Vi,j E {T} we have JWJ.) (V n)² = T &
Property 2. EFT is an invertible transform and the inverse is given by EFT -FTT+(X) - [ kk (VT),, in matrix form and EFT (a) ( 8 joN+i dg in vector
form.
Property 3. EFT is unitary transform if and only if GFT is unitary at all timesteps considered i.e. D " = INT iff M. V. = IN. vt.
Property 4. EFT invariant to the order of application of DFT or GFT on signal X.
Property 3 allows us to define the stability of the proposed transform. Consider the EFT matrix E and the signal vector x' (normalized). The transform would be given by Ex. Now consider the perturbed matrix E
where is the (fixed) perturbation. The relative difference between the output would ||xr| Fxrl.. Since orthogonal, x is not in the null space of E and so the relative difference is bounded by e. So a small change in E should cause a small change in the output as desired.
be [ + t)
Faa|] Fx]l|
As seen in property [ EFT can be simulated by GFT in the special case that the graph structure does not change with time. The illustration between other transforms is in Figure ] The figure shows transforms (GFT, JFT, DFT, EFT) in circle, and arrows from transform to the next indicate that the source transform can be obtained by the destination transform using the simulation annotated on the edges. Please note that the analysis has been performed for one-dimensional signals. However, the same holds true for higher dimensions as well by conducting the EFT dimension-wise. Here dimension-wise means the feature dimension of a node. Each node may have multidimensional signal residing on it and the EFT can be independently applied to each channel or dimension of the node signals the dynamic graph. Below subsection provides proof's for the above stated properties.
C.I PROOFS OF PROPERTIES
In this section we now prove the properties stated above. We repeat the statements for completeness. Though EFT and AD are not same in the general case they are equivalent when the graph structure does not change with time. Below result proves the result for the discrete case with graphs sampled at uniform timesteps
Property 5. (Special Equivalence between AD and EFT ) Consider DT to be the time fourier transform and G., to be the Graph fourier transform at time t. Let W Jo be the Graph fourier transform of Jo. the special case of G = G. ji, E (T} we have (V = (VD) = (LT & (Vo.))
Proof. As before consider (LGG) NNNNXT to be the Laplacian of the graphs at each timestep with eigenvalues X where E N, E T. Let Lr E RTxT be the Laplacian of the time adjacency matrix with eigenvalues μj where j E T. The Laplacian of the collective graph Tn expressed as
(Loo) (Lr @ (La. = Lr & IN + (Ir @ (La. 1)
Consider 3T, ..,,...22 be the linearly independent right eigenvectors of Lt and #f, 2/.... ... 2y be the linearly independent right eigenvectors of L.G,- Consider the vector yj (xn(3=f)) [b] RN.
25

---

Published as a conference paper at ICLR 2024
Then we have
(LbbU)) (IT & TN)iuS (Ir & (1a.))11111
= -Irr 10 (Ix3) 1+1 (IE 20 + + (Ir s (T. 1), + (ox s0 +
= =Lr @ (IN Ja & zf), + (LT @ LL.. L @ x
(Lr @ (z,, [+]
= -LLTx @ (IN [IN]
(JEDR =){ |
+ (an (M+1))
= (HETT @ o + 2 @ ( 11 [
= (I @ zjdiag {px }} + 2E @ (2f)diag(( {+
((1) s diigg (ux +
where D indicates timestep (column) wise product and diag(.) operator converts vector to a diagonal matrix. In the special case where G.,- GiyVi, E T we have X/2 X². Thus we get
(LJoy); = ((I @ a()diag( (wn + {1
(JuR + Ae(xx & zi)diag((77))) [
=
(Ju + >1(2xx @ +
+ is the cigenvector of LJp with eigenvalue μ4 + A4. But y is nothing but
Thus y, = (oyg @ 21), one the columns of D. By the rank nullity theorem, the row spaces of the transform matrices V D and GFT of JD share the same orthogonal basis. Thus the two transforms are equivalent in this case.
Note the eigenvalues (Ar @ Ac) obtained in the result above are exactly the ones used for plotting the frequency response of EFT as we compress the sequence of graphs into a single dynamic graph.
Next we prove some properties of EFT as stated in the main paper
Property 6.
EFT is an invertible transform and the inverse given by EFT (xy
kk
1) |
G
x
L (TT")) in matrix form and EFT (()T"(()) (L) L
JoN++ St in vector
form.
Proof. We begin by noting the expression for EFT (L))
DD)) = (Tr & L (..))1 [
where Mc, E NNN is the graph fourier transform of the graph at time f, Fy E RTXT is the time fourier transform. Let LG. v G. be the inverse graph fourier transform of the graph at timestep / and Φ = y be the inverse time fourier transform.
We write L D block matrix in the following form
D [CB*, CB CB.T CB
Vi @ VG.
where L is the i-th column of V and CB NTXN
26

---

Published as a conference paper at ICLR 2024
Consider D in similar but row block format follows
RB1 RB2
D :
(29)
RRBT.
RB: TT; & D..
(30)
where Dr; is the i-th row of क and RB; E RNNNT Now taking the matrix product of & and v D get
RB
RB2
Φn n
[CB
CB ...CBB]
[RBr]
RB,CB'
RB.CB²...
RB.CB²
RB.BB².
CB RB
We can verify that RB,CB/ evaluates to the following
RBCCB = (PPrs X &c.)
1 Vc,)
(31)
= p V
@ 1 GG,)
(32)
(33)
Now the columns of 인 form the eigenvectors of circulant matrix (LT). Also know that if columns form basis of column space then rows form the basis of the row space. Thus we have
1,
if
T
(34)
0.
otherwise
DG. V..
IN
(35)
IN.
if
RB,CB
(36)
0,
otherwise
(37)
Thus we have shown that 2, Mp D = INT. Thus pp is a left inverse of M p. We know that for a square matrix left inverse is also the right inverse and can be readily verified in similar manner. Thus EFT
is invertible and the inverse of the transformed signal in vector form is (pr ( (VF (2) + Ey. Similarly for the matrix form the signal we have the inverse of the
di
transform given as (1) 35 (TT), (( 13 (
Property 7. EFT is a unitary transform if and only if GFT is unitary at all timesteps considered i.e. I VD = Ivr iff L. V. IIN Vt
Proof. This property can be proved in a similar manner as in proof of property 6 The only difference
here is consider 4 be the transposed conjugate of v p rather than inverse i.e. & V and
27

---

Published as a conference paper at ICLR 2024
also PG. V a. Similar to the previous proof we have the following
RBT
RB2
DD
[CBI
CB
...CBB]
[BBT]
RBBCB
RB,CB²
RB.BB
RByCB²
LBBCBB
RBTCB²...
1 vc,) RB,CB (T X @G.)
T V.
@ vG;))
T 4
8 Pa Va.)
P v @ Pa Vo
12 v
@ Pg.. v...)
@T 2
(c. G
p D
o TT 17)
@ c C
@ pc. G
18 Pa v Vo
00
PG Voz
08 PG.
10 PG
Ga2)
08 p V Vc
x p L
V VGi
0...
Part 1: If Va, is unitary then Vi v G. Thus in this case DD InT which implies
T V = J implying D is unitary.
Part Considering v unitary whic means t V V Thus dn V INT and so G D... = IN + Ja = =V, D.. is unitary proving the 2nd part and completing the proof.
Property 8. EFT is invariant to the order of application of DFT or GFT signal X.
The above property can be observed from equation ussing the fact that matrix multiplication is associative.
28

---

Published as a conference paper at ICLR 2024
D DATASETS
Continuous Time Dynamic Graph link prediction dataset in sequential recommendation setting: For showing the efficacy of our method on large dynamic graphs, we perform experiments on three real-world e-commerce datasets (cf., Table 3 for sequential rec- ommendation. Specifically, we pose the sequential recommendation as a link prediction problem on tem- poral graphs. The penultimate and last interactions are used for validation and testing, respectively. The graphs at each interaction timestamp is constructed as detailed in (Zhang et al.) 2022) i.e., at time f, the sub- graph (G,) containing all interactions till & is consid- ered. Then the m-hop neighborhood GTn(u) around the user u is sampled from it. The next item to predict is the item (fe+1) interacted with at time + Thus the training set would con- tain (GT (2), d2), (GT((u) is) (GT-2 (2)) ; éT-1) and the test set would have ( ir). The graph construction is done the preprocessing phase speed-up training and testing.
Table 3: The statistics of the Large scale Dynamic graph datasets for link predic- tion.
SR Datasets
Beauty
Games
CDs
of Users
52,024
31,013
17,052
# of Items
57,289
23,715
35,118
# of Interactions
394,908
287.107
472,265
Average length
7.6
9.3
27.6
Density 0.01%
0.04%
0.08%
Benchmark Dynamic Graph Datasets: Table sum- marizes datasets for link prediction on benchmark dy- namic graph datasets. Each dataset contains a sequence of time-ordered graphs. SBM is a synthetic dataset to simulate evolving community structures. UCI dataset is a student community network where nodes represent the students, and the edges represent the messages ex- changed between them. AS dataset summarizes a tem- poral communication network indicating traffic flow be- tween routers. The Elliptic (EIl) dataset delineates le- gitimate versus unlawful transactions within the elliptic network of Bitcoin transactions. In this context, nodes symbolize individual transactions, while edges corre- spond to the pathways of monetary transfers. The Brain (Bm) dataset focuses on nodes representing minuscule cerebral regions or cubes, with the edges signifying their interconnections.
Table 4: Statistics and details for link pre- diction on the benchmark dynamic graph datasets. LP is the abbreviation for Link Prediction and NC is for Node Classifica- tion.
Nodss
Fddge
F'line Steps (Train Text)
SBM
1200
4,700,661
35757
LF
UCI
1,390
59,835
62/9/17
LP
AS
6.474
13,895
70/10/20
LP
Ellipccc
203,769
234,355
31/5/13
NC
Brain
5,000
1,955,588
10/1/1
NC
Synthetic Dataset Consider the dynamic graph over T timesteps. Thus we have T graph snapshots. We compute the eigenvectors at each snapshot and place them over the graph's 's nodes. Moreover, for each node (spread over T timesteps) we compute a periodic signal that is added to the eigenvector component Evve(G.)) So the expression for the noise added to the signal would be: X(i,t) = Σn og EvEeeveCGaa k] + 3, * efur((t) [t]. In our experiments, we have used only one randomly chosen eigenvector. Also we consider only a single sinusoid frequency W. ake, By are parameters and are set to 1 in our experiments. For noise, we add to Xii, t) a signal taken from Gaussian distribution with 0 mean i.e. X t) = Xii + +O,, 6), where is the standard deviation.
D.1 EXPERIMENTAL SETUP
We implement our models using the DGL framework (Wang et al. 2019) in the pytorch library (Paszke et al. 2017). The hyperparameters are selected from the following search space: learning rate E 0.01, 0.0003]. l2 regularization parameter a e [0.01, 0.00001], embedding and hidden layer dimensions E {32, 64, 128). filter order E {2, 4, 8, 16), subgraph size E {1, 2, 3, 4). The experiments are run on a single Tesla P100 GPU. We run our method for 5 runs per dataset and report the mean of the results. For the baselines we report the best results that have been reported unless mentioned otherwise. If results are not available we run baselines by using the implementation provided with default parameters and optimizing the hidden size (width) and layer number (depth) of the network. Regarding graph construction, for the Sequential Recommendation (SR) datasets we similar to (Zhang al. (022). For the Session Based Recommendation (SBR) setting we use the transition graph of the items in the sequence as in (Wu et al. 2019). We also try with higher order graphs, albeit without any gains, as reported in (Wu et al. 2019). Moreover, since for SBR the last
29

---

Published as a conference paper at ICLR 2024
item is of more significance to the prediction task and the datasets suffer from overfitting modify the prediction layer accordingly and incorporate appropriate changes from baselines.
D.2 IMPLEMENTATION
We intend perform filtering in spectral space for dynamic graphs using EFT. Since our idea is to perform collective filtering along the vertex and temporal domain in EFT, we need two modules to compute G, (vertex aspect) and r (temporal aspect), respectively, in equation of EFT. We now explain these modules in detail.
Filtering along the vertex domain: This module computes the convolution matrix G., in equation 6, Consider the filter response A which is a diagonal matrix with diagonal values representing the magnitude of the corresoondigg frequency(eigenvalle) In order to avoid the computational cost of the eigendecomposition. we choose to approximate the it using polynomials. In this work, use the Chebyshev polynomials (Defferrard et al. 2016). Specifically, the frequency response of the desired filter is approximated as A = - (A)),(A), where Oy is the polynomial/filtrr 2A -1, I, Amaz is the maximum eigenvalue order, Tk is the Chebyshev polynomial basis, A Amaz
and Cj is the corresponding filter coefficients. Thus, we can approximate the filtering operation as: Xx * A = U (E o (TT(( U*X = End cg (UA(U" )x Edd Ct T (L)X. Having the filter coefficients Ck learnable parameters enables learning of filter for the task. The convolution X * A gives the desired filtered response.
Filtering along the temporal Domain: After performing filtering in the vertex domain, we aim to filter over the temporal signals using yr as in equation 6 To apply the yr (Fourier transform), we must first ensure that the signals in sequences are sampled at uniform intervals. In the continuous time setting, interactions between nodes could occur at anytime or the sampling could be non- uniform, Thus, we perform mapping from R2'xd RT'xd that aims map the input space to uniformly sampled space. For compurational reasons, we select the current and next embeddings (with positional information) along with the timestamp information (t) E Ra) for getting the mapped embedding akin to interpolation. Formally, let X; E Rd be the embeddings of the node at time t. This is first mapped to the interpolated space using a universal approximator: X, = WWi'(Wi[X [X;; X/41: (t) + b() + b2g. where Wi, W2. bf. bf are learnable parameters and o² is a non-linearity. We call this module the time encoding layer, which is essential for applying Fourier transform along the temporal dimension. Let X = X, E RR'xd be the interpolated sequence of embeddings of the node. This is converted to the frequency domain (X E RT'x)) using the DFT matrix 1 as X X, Then we multiply X element-wise by temporal filter Fr E R to obtain the filtered signal X, Fr X which is then converted back to the temporal domain by using the inverse transform 7 to get X, = Xy Xy is the equivalent of X in equation 6 that is the output of EFT. In practice, the fast Fourier transform is used that can perform the computations in order (TT) Hence, overall time complexity of the architecture is O(N + E)T + NTlogT)). To map the output back to the original space from the interpolated space would need further mapping layers. Similar to (Zhou et al. 2022), we use the standard layer normalization (LN) and feedforward (FFN) layers: XF LN (LN (X, + D(X,)) + D (FFN (LN (X, + D(Xx)) ()))), where W:', w bf. b/ are learnable parameters and D(.) represents dropout. We could stack filter layers with the node embeddings obtained from previous layers inputs. XF is the final filtered signal that is used in the downstream prediction. For the concerned node n we denote this as X
D.3 COMPUTATIONAL COMPLEXITY
Considering the spectral transform. the exact eigendecomposition of the joint laplacian would take order ((NT)) whereas our method of EFT would take O(VT + Vogg') Thus we reduce the complexity from a factor of T to T lT). This would be beneficial in cases where there are many timesteps considered. For the model at the implementation level since we have made use of a function approximator that runs in time linear to the number of edges (e), the time complexity is O( + WoTlog(T) (T)). We have performed wall clock run time analysis for the training of our method and the results in table 5 shows that is comparable to a dynamic graph based baseline (that doesn't t use any spectral transform):
30

---

Published as a conference paper at ICLR 2024
Table Wall clock running (sec/epoch) time of our and baseline method on SR datasets
Dataset
Method
Wall clock time (sec/epoch)
Beauty
DGSR
565
Beauty
EFT
753
Games
DGSR
1719
Games
EFT
2535
CD
DGSR
5415
CD
EFT
12637
(a) Games
(b) Beauty
(c) Games
(d) Beauty
Figure 6: Effect of the parameters (filter order and subgraph size) on EFT performance.
E
ABLATION STUDY
Component ablation: In our first ab- lation study, we study the effect of various modules of the EFT archi- tecture by systematically removing model components. Table summa- rizes our findings. For example, per- formance declines when we remove the graph filtering module ("w/o graph filter" Table 6). confirms that the graph filters help to reduce long- range noise and positively impact per- formance. Next, we replace learnable filters of EFT with several static filters such highpass, bandpass, lowpass, etc. Performance with static filters less than that of dynamic filters, supporting our choice of having learnalle filters in EFT.
Table 6: Ablation study of our model. We report Recall 10 (R@ @ 10) and NDCG@ 10 on Beauty and Games datasets.
Beauty
Games
R 10
NDCG 10
R 10
NDCG@ 10
EFT
53.23
37.10
77.78
58.75
w/o Temporal filier
52.42
36.12
76.33
56.95
w/o Graph filter
58.36
+High Pass Filter
47.53
31.10
76.88
57.24
+Low Pass Filter
52.71
36.76
77.74
58.49
+Band Pass Filter
52.27
36.09
76.67
56.98
+Band Stop Filter
45.34
29.09
77.63
58.42
Parameter Selection: this experiment, we study the effect filter and graph construction parameters that will help select optimal parameters for the model. Specifically, for 1) the order of the graph filter and 2) subgraph size, which is the number of hops considered around the given user node for constructing the graph. The results in Figure 7 with apt transform of the 2 metric scales for comprehension. For the filter order, we observe that for both datasets, there exists an optimal filter order which the best performance is achieved. We observe that increasing filter order further causes overfitting on these datasets. For the subgraph size, we observe an increasing trend the results, indicating that higher subgraph sizes (> 1) benefit the performance over single hop (which is the sequence itself). This shows that modeling the SR as graph learning problem is helpful over considering only sequence. We conclude that beyond the subgraph size of two, the results saturate for these datasets.
run experiments
31


Reviews:
[{"review_id": "UZUJKa0CEe", "reviewer": "Reviewer_YfD5", "summary": "This work proposes an invertible spectral transform that captures evolving representations on temporal graphs. EFT is built upon the approximation of the exact solution to the variational form. They provide theoretical bounds of the difference between EFT and the exact solution to the variational form. Their experiments show that EFT effectively filter out the noise signals and enhance task performance against the baselines.", "questions": "The question is how is the complexity of computing this transform. The reviewer did not see how fast it can be computed compared with other baselines and would like to see if it can be efficiently computed empirically.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The strengths of this work are summarized as follows:\n\n(1) The idea of evolving graph Fourier transform is interesting, which provides an alternative way of extracting the information within spatial temporal graphs.\n\n(2) The theoretical properties are analyzed with provable guarantees on the approximation properties of EFT.\n\n(3) The benchmarks comparing this method with the baselines look promising.", "weaknesses": "The weakness of this work are summarized as follows:\n\n(1) Despite giving guarantees on the approximation part, this work does not address the theoretical guarantees of learning under this module. Hence this makes this work more like heuristic. The reviewer believes that this might be quite difficult though.\n\n(2) The font size of the tables should be improved. This makes it hard to read. The reviewer suggests reducing presentation on the properties of EFT in proposition 5.1 to make up for the space and delay the properties of this transform to the appendix instead.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5wWpzLTjDM", "reviewer": "Reviewer_sEtv", "summary": "This paper proposes a method called evolving Fourier transform (EFT) for spectral analysis of dynamic graphs that is formulated as an optimization problem over the Laplacian of the continuous time dynamic graph. At implementation level it performs vertex domain filtering via Chebyshev polynomial approximation of graph filters followed by a classical time domain filtering via Fourier transform. Although the experiments are limited but the method is novel. The paper is dense and difficult to read at times. It is a novel work but could have been presented in a more elaborated way by providing more examples, intuitions, connections to FT and GFT via examples.", "questions": "It would help the readers if more insights are given in terms of small toy examples. What will be harmonics for ring of ring graphs (no edge addition or dropping over time)? Does this have some relation to classical Fourier transform?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "Although the experiments are limited, the method is novel.", "weaknesses": "The paper is dense and difficult to read at times. It is a novel work but could have been presented in a more elaborated way by providing more examples, intuitions, connections to FT and GFT via examples.\n\nA table or example for clarifying the notations will significantly improve the readability. Please provide explanations/intuitions of all the terms in Equation (4) when the EFT is defined first. \n\nThe coupling of filtering in vertex and time domains is explained in Appendix C.2 which should be moved to the main text. \n\nThe paper does not state its limitations, for example non-applicability to dynamic graphs with node addition or node drops.\n\nGraph signal variation equations can be displayed with number since it the the basic term used in further analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yRfzi9plTJ", "reviewer": "Reviewer_4jzq", "summary": "This paper designed a new form of (approximated) Fourier Transform to analyze spatio-temporal graph signals with low computational complexity. The gist of the proposed approach lies in the decomposition of the spatial/graph domain and the temporal domain, reducing the computational complexity from $O((NT)^3)$ (performing GFT/SVD over the entire spatio-temporal domain) to $O(N^3T + NT \\log(T))$. Furthermore, the proposed transform was shown to be robust to structural perturbations, and comprehensive simulations verified the utility of the transform when combined with some vanilla transformer models to perform link prediction tasks.", "questions": "1. In addition to the Fourier Transform, there appears to be research interests in performing spectral clustering for dynamic networks as well [6, 7]. Since node clustering can also be used to predict missing links, what advantages and disadvantages do you think EFT will have compared to spectral clustering?\n\n2. Just curious, beyond link prediction, what changes would we need if we also want to predict node features?\n\n[6] Liu, Fuchen, et al. \"Global spectral clustering in dynamic networks.\" Proceedings of the National Academy of Sciences 115.5 (2018): 927-932.\n\n[7] Martin, Lionel, Andreas Loukas, and Pierre Vandergheynst. \"Fast approximate spectral clustering for dynamic networks.\" International Conference on Machine Learning. PMLR, 2018.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Just like in classical signal processing, it is not surprising that denoising and then reconstructing (predicting) the signal from the spectral domain can be much easier than dealing with the spatio-temporal signal directly. However, performing GFT over the entire spatio-temporal graph is typically computationally expensive, which hinders the spectrum analysis of spatio-temporal signals. This paper provided solid theoretical guarantees for using Evolving Graph Fourier Transform (EFT: DFT+GFT in order) to approximate the absolute decomposition (AD) with reasonably low approximation error. Standard properties of the transform are established in section 5.1 as well. For the simulations, it is also very interesting to see that EFT can be used within transformer models to perform sequential link prediction tasks in practice.", "weaknesses": "The idea of decoupling spatial and temporal domains in spatio-temporal data analysis is actually not new, especially for the spatio-temporal graph neural networks (ST-GCN) community. As a matter of fact, most existing ST-GCN models, no matter their design come from empirical perspectives [1, 2, 3] or theoretical perspectives [4, 5], all share the idea of graph-time decoupling to reduce the computational complexity. However, only a handful of prior works on ST-GCNs have been mentioned and discussed in the paper. I understand that the authors are considering graphs that change with time, for which most ST-GCNs are not directly applicable as they deal with static graphs, but I still believe related discussions should be added so that the readers are clearer about the contribution of this paper. Furthermore, the complexity of the proposed approach seems quite similar to those in [5]. The authors may also want to have some comments on that as well.\n\nIn addition, for the approximation of EFT to work, two extra assumptions are needed in place: 1) The rate of change of the graph with time is bounded; 2) The eigenvalues of the graph Laplacian at any given timestep and between timesteps have a multiplicity of 1. I think it is better to state these assumptions in the main text instead of the appendix to help the readers better understand the limit of the approach, as the assumptions are quite important (and intuitive) for the EFT to work.\n\n[1] Yan, Sijie, Yuanjun Xiong, and Dahua Lin. \"Spatial temporal graph convolutional networks for skeleton-based action recognition.\" Proceedings of the AAAI conference on artificial intelligence. Vol. 32. No. 1. 2018.\n\n[2] Yu, Bing, Haoteng Yin, and Zhanxing Zhu. \"Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting.\" arXiv preprint arXiv:1709.04875 (2017).\n\n[3] Cao, Defu, et al. \"Spectral temporal graph neural network for multivariate time-series forecasting.\" Advances in neural information processing systems 33 (2020): 17766-17778.\n\n[4] Pan, Chao, Siheng Chen, and Antonio Ortega. \"Spatio-temporal graph scattering transform.\" arXiv preprint arXiv:2012.03363 (2020).\n\n[5] Kartal, Bünyamin, Eray Özgünay, and Aykut Koç. \"Joint time-vertex fractional fourier transform.\" arXiv preprint arXiv:2203.07655 (2022).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ttQUZnfarF", "reviewer": "Reviewer_qJBV", "summary": "This paper proposes a new approach, EFT, to transform temporal graphs into the frequency domain, which can capture spectra of evolving graph structures. EFT provides solid theoretical proof of utilizing the Laplacian of the continuous time dynamic graph and pseudo-spectrum relaxations to decrease the computation cost. The downstream experiments on large-scale and standard dynamic graph datasets demonstrate the superior performance and efficiency of the proposed model.", "questions": "1. The timespan of edges is a natural attribute of a temporal graph. Some recurrent works [1] [2] show that embedding the timespan of edges is important, especially in the sequential recommendation. I am wondering whether EFT could embed the timespan of edges and how. Such discussion may help the audience have better ideas on applying or extending EFT in solving their own problems in different application domains.\n[1] Time-aware Dynamic Graph Embedding for Asynchronous Structural Evolution, TKDE'23.\n[2] Time lag aware sequential recommendation, CIKM'22\n2. In section 5.1, ”However, the same holds true for higher dimensions as well by conducting the EFT dimension-wise.” What does the dimension-wise mean?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This work proposed EFT to transform the evolving temporal graphs into the spectral domain, grounded on theoretical foundations. The EFT is very effective with the computational complexity of O(T+Tlog(T)).\n2. The experiments in simulating scenarios clearly demonstrate that EFT is effective in filtering noise and amplifying useful signals in evolving temporal graphs.\n3. EFT is of good interpretability; it can decompose the transform into the individual transforms of each domain to give clear relations from both the time and vertex domains.", "weaknesses": "The generalization of the proposed method needs to be clarified further. Even considering Theorem 1, the proposed method depends on the approximate \\Psi_{AD}, the eigendecomposition of L_{J_d}. It is unclear whether any limitations associated with this will be introduced.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)