Dynamic Mode Decomposition (DMD) has become a cornerstone for analyzing nonlinear dynamical systems (NLDSs) by leveraging Koopman operator theory. By "lifting" nonlinear dynamics into a linear, infinite-dimensional space, DMD identifies eigenvalues and modes that characterize a system's evolution. However, standard DMD often treats observables as flat vectors, discarding the inherent relational structure—such as graph connectivity—present in complex systems like traffic networks or neural circuits.
In their 2019 paper, Keisuke Fujii and Yoshinobu Kawahara introduce a significant extension to this toolset, moving from scalar-valued to vector-valued function spaces to extract global dynamics from complex, structured data.
The vvRKHS Framework
The authors address the limitations of conventional DMD by reformulating Koopman spectral analysis within vector-valued Reproducing Kernel Hilbert Spaces (vvRKHS). Unlike traditional scalar kernels, matrix-valued kernels allow the model to explicitly account for the "structure among observables." This shift enables the extraction of global dynamics directly from structured data, such as sequences of adjacency matrices, without destroying the underlying geometry of the system.
By using vvRKHS, the relationship between variables (the graph) is treated as a dynamical observable itself. This allows researchers to treat an entire graph as a single point in a function space, facilitating the observation of how the connectivity of a system oscillates over time.
Technical Implementation: TDMD and Graph DMD
To manage the high dimensionality of structured data, the authors utilize two key technical strategies:
- Reformulated Tensor-based DMD (TDMD): To avoid the "curse of dimensionality," the authors employ the Tensor-Train (TT) format. This approach decomposes large tensors into smaller, manageable "cores," providing a more stable and direct estimation procedure for TDMD than previous iterations.
- Graph DMD: As a specific application, the authors propose Graph DMD. In this setup, a sequence of adjacency matrices representing a graph changing over time is treated as a realization of the kernel structure. This allows the algorithm to find "graph modes" that correspond to specific temporal frequencies or growth rates.
Experimental Validation
The authors validated their approach using three distinct datasets, ranging from synthetic benchmarks to real-world traffic patterns:
- Synthetic Data: Testing on noisy adjacency matrices (up to $256 \times 256$) showed that Graph DMD was significantly more accurate than "Exact DMD," with the performance gap widening as the dimensionality of the matrices increased.
- Bike-Sharing Dynamics: Using data from Washington D.C.’s Capital Bikeshare (348 stations), the method successfully identified daily (1/24 hr) and weekly (1/168 hr) periodicities. It mapped spatial coherence, distinguishing between traffic patterns at the Lincoln Memorial (coherent across both cycles) and Union Station (dominant in the weekly cycle).
- Fish-Schooling Simulation: In a multi-agent model simulating "fish" behaviors (swarm, torus, and parallel), Graph DMD achieved a classification error of only 0.022. This vastly outperformed Tensor DMD (0.311) and Exact DMD (0.511), demonstrating that preserving graph structure is critical for recognizing complex group behaviors.
Limitations and Future Directions
While the framework is powerful, it faces several practical challenges. Like all kernel methods, the choice of the matrix-valued kernel is crucial, and defining optimal kernels for diverse structured data remains an open research question. Additionally, the mathematical framework assumes symmetric positive semi-definite (SPSD) matrices; since real-world adjacency matrices often lack this property, the authors applied diagonal shifts to satisfy theoretical requirements. Finally, while the Tensor-Train format aids scaling, the reliance on sequential Singular Value Decompositions (SVDs) may present bottlenecks for extremely large-scale or real-time applications.
Conclusion
By integrating vvRKHS with Koopman theory, this research provides a robust method for analyzing systems where the relationship between variables is as vital as the variables themselves. Graph DMD represents a significant advancement in preserving structural integrity during dynamical analysis, offering a clearer lens into the rhythmic patterns of complex, networked systems.
Summary updated