Learning Time-Varying Graph Signals via Koopman

Sivaram Krishnan, Jinho Choi, Jihong Park · 2025

Read Learning Time-Varying Graph Signals via Koopman by Sivaram Krishnan, Jinho Choi, Jihong Park (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-06493.txt.

Introduction

Sivaram Krishnan, Jinho Choi, and Jihong Park forecast and fill gaps in data that lives on changing networks. Sensor readings, ocean measurements, and drone trajectories all form graph signals whose wiring itself shifts over time. Predicting how such a network signal evolves, or rebuilding missing pieces, calls for a model of the hidden dynamics.

Their framework embeds each graph snapshot into a fixed vector, turning the sequence into an ordinary time series. A Koopman autoencoder then learns the nonlinear rules governing that series inside the latent space, where evolution becomes easier to handle. The learned dynamics support both forecasting future graph states and reconstructing values that were never observed.

Catalog record

CREATORSivaram Krishnan, Jinho Choi, Jihong Park
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-06493

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Learning Time-Varying Graph Signals via Koopman Sivaram Krishnan, Jinho Choi, Jihong Park Abstract A wide variety of real-world data, such as sea measurements, e.g., temperatures collected by distributed sensors and multiple unmanned aerial vehicles (UAV) trajectories, can be naturally represented as graphs, often exhibiting non-Euclidean structures. These graph representations may evolve over time, forming time-varying graphs. Effectively modeling and analyzing such dynamic graph data is critical for tasks like predicting graph evolution and reconstructing missing graph data. In this paper, we propose a framework based on the Koopman autoencoder (KAE) to handle time-varying graph data. Specifically, we assume the existence of a hidden non-linear dynamical system, where the state vector corresponds to the graph embedding of the time-varying graph signals. To capture the evolving graph structures, the graph data is first converted into a vector time series through graph embedding, representing the structural information in a finite-dimensional latent space. In this latent space, the KAE is applied to learn the underlying non-linear dynamics governing the temporal evolution of graph features, enabling both prediction and reconstruction tasks. I Introduction I-A Motivation Graphs are fundamental data structures for modeling the structure and interactions within complex systems [ 1 ] across a variety of domains, including, but not limited to, social networks [ 2 ] , biological systems [ 3 ] , transportation networks [ 4 ] , and communication systems [ 5 ] . These data structures provide a versatile framework for representing relationships and dependencies, enabling insights into the organization and behavior of complex systems. In many real-world applications, the underlying graph data is not static; instead they evolve over time. Time-varying graphs [ 6 ] are a type of graph data characterized by temporal variations in their components or overall configuration. Unlike the commonly studied static graph structures, analyzing time-varying graph data introduces additional challenges. In this work, we consider two application scenarios involving time-varying graphs, as follows: • the reconstruction of graph signals • the prediction of graph signals. While the reconstruction of graph signals is necessary for recovering missing information, which is common in real-world sensor networks or data transmission scenarios, prediction, on the other hand, enables forecasting the future states of the systems and thus supports planning, decision-making, and control in dynamical environments. While several methods exist in the literature for graph signal reconstruction, which is based on the graph signal processing (GSP) [ 7 , 8 ] or graph neural network (GNN) paradigm [ 9 ] , most of the formulation is limited to time-varying graphs with a fixed structure. While another for graph signal prediction is that most of the data-driven methods are computationally heavy and often fail to capture the non-linear dynamics inherent in time-varying graphs. To address these limitations, we propose a novel framework leveraging the Koopman operator theory [ 10 ] . This theory demonstrates that non-linear dynamics can be represented linearly by focusing on functions (observables) of the system’s state, enabling linear modeling in a higher-dimensional latent space. The Koopman autoencoder (KAE) [ 10 , 11 , 12 ] offers a data-driven approach to linearize complex non-linear dynamical systems by learning such linear representations in a lifted (latent) space. This physics-informed approach ensures predictions adhere to a consistent and interpretable dynamic structure, rather than merely fitting data in a black-box manner. Finite-dimensional approximations [ 13 ] and Koopman invariant subspaces [ 14 ] have further advanced this field, with comprehensive reviews available in [ 15 , 16 ] and deep learning applications explored in [ 17 , 12 ] . Building upon our previous work on Koopman-theoretic graph embeddings and the graph KAE (GKAE) [ 18 , 19 ] 1 1 1 This paper is an extended version of [ 19 ] , providing a generalized framework for prediction and reconstruction with comprehensive exposition and extensive experimental validation. , we introduce a robust framework for predicting time-varying graphs and reconstructing missing graph data. Our approach assumes the observed graph sequence arises from an underlying, unknown non-linear dynamical system. For learning on these graphs, the data is first embedded into a latent space (graph embedding) as a multivariate time series, capturing structural information. The GKAE then learns the linear dynamics governing the evolution of these graph embeddings, enabling both tasks. The contributions of this paper are summarized as follows: C1) We formally categorize time-varying graphs into two broad types: those with time-varying graph signals and those with time-varying graph structures. We highlight the limitations of existing GSP-based and GNN-based approaches for reconstructing time-varying graph signals, which is majorly limited to only time-varying graph signals with a static graph structure. C2) We propose the GKAE as a robust framework for reconstruction and prediction in time-varying graphs, capable of handling diverse types of time-varying graphs. The GKAE leverages GNN and Koopman theory, operating in the latent space to model non-linear dynamics through a linear Koopman matrix, making it applicable to all types of time-varying graphs. C3) We evaluate our method against established baselines. For reconstruction tasks, we compare it with GSP among other approaches, while for prediction tasks, we benchmark it against other data-driven Koopman-based methods and GNN-based state-of-the-art methods. Our results demonstrate superior performance in terms of both reconstruction error and prediction error using GKAE across various types of time-varying graphs. TABLE I : Glossary of Notations Symbol Description Graph Notations G(t) Graph at time step t . {\cal V} Set of nodes. {\bf x}(t) Graph signals at time step t . {\cal E}(t) Edge set at time step t . {\bf A}(t),{\bf W}(t) Binary/Weighted Adjacency matrix at time t . {\cal N}_{l}(t) Neighborhood of node l at time t . {\bf L}(t)={\bf D}(t)-{\bf A}(t) Laplacian matrix Model Notations {\bf g}(t) Graph embedding/state vector at time t . {\bf K} Koopman matrix of dimension M . {\bf h}(t) Koopman variable at time t . L Maximum prediction step during training. {\cal E},{\cal D} Encoder and decoder function. \theta_{\text{GNN}},\theta_{\text{KAE}},\theta_{\text{LC}} Parameters for encoder functions. \phi_{\text{GNN}},\phi_{\text{KAE}},\phi_{\text{LC}} Parameters for decoder functions. POOL (\cdot) Pooling function. {\bf Y} Sampled graph signals. {\bf J} Sampling matrix. {\bf y}^{\prime}(t) Sampled graph signals at time t . {\bf W}^{\prime}(t) Sampled adjacency matrix at time t . Loss Functions and Performance Metrics {\cal L}_{\text{GKAE}} Loss function for the graph Koopman autoencoder. {\cal L}_{\text{LC}} Loss function for the Latent consistency autoencoder. \epsilon_{\text{pred}} Average prediction error. \epsilon_{\text{reco}} Average reconstruction error. P Total number of prediction steps after training. \beta_{1},\beta_{2} Loss hyperparameters. Dataset N Total number of nodes. k Number of neighbors using k -nearest neighbors. r Communication radius for determining the neighborhood. The comprehensive glossary of notations used throughout the paper is summarized in Table. I . I-B Related Work We begin by reviewing methods developed for graph signal reconstruction, with a particular emphasis on approaches grounded in GSP. We then examine prediction methods—often used interchangeably with forecasting in the literature—which are majorly data-driven approaches, particularly deep learning and GNN-based models Reconstruction of Graph Signals GSP extends traditional signal processing concepts to graph-based data [ 20 ] [ 21 ] . Unlike traditional signal processing, which operates on regular grids with established frameworks like Fourier transforms and sampling theories (e.g., the Nyquist rate), GSP addresses signals defined on non-uniform and often dynamic graph structures

Read the complete text