Dynamic mode decomposition in vector-valued reproducing kernel Hilbert spaces for extracting dynamical structure among observables

Keisuke Fujii, Yoshinobu Kawahara

TL;DR

This paper introduces a novel extension of Dynamic Mode Decomposition (DMD) designed to analyze nonlinear dynamical systems where variables possess inherent structural dependencies, such as time-varying networks. By leveraging vector-valued reproducing kernel Hilbert spaces (vvRKHSs) and a stable reformulation of tensor-based DMD, the authors present "Graph DMD," an algorithm capable of extracting and visualizing global spatiotemporal dynamics directly from sequences of graph adjacency matrices.

What Problem Does This Paper Address?

Dynamic Mode Decomposition (DMD) is a popular data-driven technique used to analyze nonlinear dynamical systems by computing the eigenvalues and modes of the linear, infinite-dimensional Koopman operator. However, standard DMD algorithms require flattening data snapshots into scalar vectors.

This flattening process destroys any structural or relational context within the data—such as the topology of a social network, brain connectivity maps, or traffic flow graphs. When observables have dependent structures (e.g., a sequence of graphs), standard DMD fails to capture the global dynamics of these relationships. The authors address this gap by developing a framework that performs Koopman spectral analysis while natively preserving the structural dependencies among observables.

Methods

The authors introduce a framework that shifts the mathematical formulation of DMD from scalar function spaces to vector-valued Reproducing Kernel Hilbert Spaces (vvRKHSs).

  1. vvRKHS Formulation: By using matrix-valued kernels, the framework models the dependencies between multiple outputs directly within the function space, allowing the Koopman operator to act on vector-valued observation functions.
  2. Reformulated Tensor-based DMD (TDMD): To compute this formulation efficiently without breaking the tensor structure of the data, the authors improve upon existing Tensor-Train (TT) format DMD methods. They introduce a more direct and numerically stable pseudo-inverse computation using Singular Value Decomposition (SVD) on the final core matrix.
  3. Graph DMD: As a specialized case of their method, they introduce Graph DMD. This algorithm takes a sequence of graph adjacency matrices as an input tensor, treating the time-evolving network weights as a realization of the kernel structure.

Datasets

The method was evaluated on three distinct datasets:

  • Synthetic Data: A generated sequence of noisy, time-varying adjacency matrices ($64 \times 64$ and $256 \times 256$) embedded with two distinct temporal decay modes and Gaussian noise.
  • Bike-Sharing Data: Real-world data from Capital Bikeshare in Washington D.C. (2014). The dataset tracks bike trips between 348 stations, structured as a sequence of $348 \times 348$ adjacency matrices across 336 hourly snapshots.
  • Fish-Schooling Simulation: A multi-agent collective motion model simulating 64 fish agents. The simulation generates three distinct behavioral topologies (swarm, torus, and parallel) based on local interaction rules, which were converted into adjacency matrices using Gaussian kernels.

Key Insights and Ideas

  • Structure as an Implicit Regularizer: Retaining the tensor structure of network data rather than flattening it prevents the loss of relational information. This structural preservation acts as a regularizer, making the algorithm significantly more robust to noise.
  • The Power of the Tensor-Train Format: Utilizing the Tensor-Train format bypasses the curse of dimensionality. The TT-decomposition tolerance parameter ($\epsilon$) acts as a critical knob, filtering out high-frequency noise while isolating dominant global dynamics.
  • Dynamic Embeddings for Classification: Beyond visualization, the spectral features extracted by Graph DMD provide highly discriminative representations of complex system behaviors, making them valuable for downstream machine learning tasks like behavior recognition.

Key Results

  • Noise Resilience: On synthetic data, Graph DMD achieved lower relative eigenvalue estimation errors than standard exact DMD, particularly when dealing with larger matrix sizes and higher noise levels.
  • Real-World Periodicity Extraction: When applied to the bike-sharing dataset, Graph DMD successfully isolated daily ($\omega = 1/24$) and weekly ($\omega = 1/168$) traffic cycles. It visually distinguished tourist-heavy areas (like the Lincoln Memorial, which showed strong daily and weekly patterns) from commuter hubs (like Union Station, which dominated weekly patterns).
Method        Classification Error (Fish-Schooling)
---------------------------------------------------
Graph DMD     0.022
TDMD          0.311
Exact DMD     0.511
  • Behavior Recognition: In the fish-schooling simulation, a 3-nearest neighbor classifier trained on features extracted by Graph DMD achieved a 3-fold cross-validation error of 0.022, vastly outperforming standard TDMD (0.311) and exact DMD (0.511).

Limitations and Future Work

  • Undirected Graph Constraint: The current mathematical formulation relies on symmetric positive semi-definite kernel matrices. Consequently, Graph DMD is currently limited to undirected graphs and cannot naturally handle directed networks.
  • Computational Bottlenecks: While the Tensor-Train format scales well, the initial tensor-train decomposition still relies on sequential SVDs, which can become a computational bottleneck for exceptionally long time series or massive graphs.
  • Future Directions: The authors suggest extending the framework to accommodate directed graphs (non-symmetric matrices) and exploring applications in other complex network domains.

Summary updated

Abstract

Understanding nonlinear dynamical systems (NLDSs) is challenging in a variety of engineering and scientific fields. Dynamic mode decomposition (DMD), which is a numerical algorithm for the spectral analysis of Koopman operators, has been attracting attention as a way of obtaining global modal descriptions of NLDSs without requiring explicit prior knowledge. However, since existing DMD algorithms are in principle formulated based on the concatenation of scalar observables, it is not directly applicable to data with dependent structures among observables, which take, for example, the form of a sequence of graphs. In this paper, we formulate Koopman spectral analysis for NLDSs with structures among observables and propose an estimation algorithm for this problem. This method can extract and visualize the underlying low-dimensional global dynamics of NLDSs with structures among observables from data, which can be useful in understanding the underlying dynamics of such NLDSs. To this end, we first formulate the problem of estimating spectra of the Koopman operator defined in vector-valued reproducing kernel Hilbert spaces, and then develop an estimation procedure for this problem by reformulating tensor-based DMD. As a special case of our method, we propose the method named as Graph DMD, which is a numerical algorithm for Koopman spectral analysis of graph dynamical systems, using a sequence of adjacency matrices. We investigate the empirical performance of our method by using synthetic and real-world data.
BibTeX
@article{fujii2019dynamic,
  author = {Keisuke Fujii and Yoshinobu Kawahara},
  title = {{Dynamic mode decomposition in vector-valued reproducing kernel Hilbert spaces for extracting dynamical structure among observables}},
  journal = {Neural Networks},
  year = {2019},
  doi = {10.1016/j.neunet.2019.04.020},
}
Figure