Beyond Spatio-Temporal Representations: Evolving Fourier Transform for Temporal Graphs

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. 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. 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., 2022; Bastos et al., 2023; da Xu et al., 2020). Our focus in this work is the latter case. The evolving graphs have been comprehensively studied from the spatio-temporal graph-neural network (GNN) perspective, focusing on propagating local information (Pareja et al., 2020; Shi et al., 2021; Xiang et al., 2022; da Xu et 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.