# Koopman-based spectral clustering of directed and time-evolving graphs

arXiv: https://arxiv.org/abs/2204.02951 · HTML: https://mlsanity.com/paper/2204.02951/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 61 references that are in the map.
- First posted on arXiv 6 Apr 2022.

## Builds on (most cited first, 10 of 10)

- [Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys](https://mlsanity.com/paper/1506.03645/) (2015)
- [The structure and dynamics of multilayer networks](https://mlsanity.com/paper/1407.0742/) (2014)
- [Eigendecompositions of Transfer Operators in Reproducing Kernel Hilbert Spaces](https://mlsanity.com/paper/1712.01572/) (2017)
- [Clustering and Community Detection in Directed Networks: A Survey](https://mlsanity.com/paper/1308.0971/) (2013)
- [Random walks and diffusion on networks](https://mlsanity.com/paper/1612.03281/) (2016)
- [Hermitian matrices for clustering directed graphs: insights and applications](https://mlsanity.com/paper/1908.02096/) (2019)
- [Kernel methods for detecting coherent structures in dynamical data](https://mlsanity.com/paper/1904.07752/) (2019)
- [A kernel-based approach to molecular conformation analysis](https://mlsanity.com/paper/1809.11092/) (2018)
- [A Dynamic Mode Decomposition Approach for Decentralized Spectral Clustering of Graphs](https://mlsanity.com/paper/2203.00004/) (2022)
- [Spectral identification of networks using sparse measurements](https://mlsanity.com/paper/1601.04364/) (2016)

## Built on by (most cited first, 6 of 6)

- [Dynamical systems and complex networks: A Koopman operator perspective](https://mlsanity.com/paper/2405.08940/) (2024)
- [Laplace Transform Based Low-Complexity Learning of Continuous Markov Semigroups](https://mlsanity.com/paper/2410.14477/) (2024)
- [Transfer operators on graphs: Spectral clustering and beyond](https://mlsanity.com/paper/2305.11766/) (2023)
- [A Spectral-Grassmann Wasserstein metric for operator representations of dynamical systems](https://mlsanity.com/paper/2509.24920/) (2025)
- [Clustering Time-Evolving Networks Using the Spatio-Temporal Graph Laplacian](https://mlsanity.com/paper/2407.12864/) (2024)
- [Multi-View Spectral Clustering for Graphs with Multiple View Structures](https://mlsanity.com/paper/2501.11422/) (2025)

## Abstract (arXiv)

While spectral clustering algorithms for undirected graphs are well established and have been successfully applied to unsupervised machine learning problems ranging from image segmentation and genome sequencing to signal processing and social network analysis, clustering directed graphs remains notoriously difficult. Two of the main challenges are that the eigenvalues and eigenvectors of graph Laplacians associated with directed graphs are in general complex-valued and that there is no universally accepted definition of clusters in directed graphs. We first exploit relationships between the graph Laplacian and transfer operators and in particular between clusters in undirected graphs and metastable sets in stochastic dynamical systems and then use a generalization of the notion of metastability to derive clustering algorithms for directed and time-evolving graphs. The resulting clusters can be interpreted as coherent sets, which play an important role in the analysis of transport and mixing processes in fluid flows.