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

2022-04-06 · Stefan Klus, Natasa Djurdjevac Conrad

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.

📄 PDF Abstract BibTeX arXiv:2204.02951

Code (0)

등록된 구현이 없습니다.

Tasks

ClusteringImage Segmentation Semantic Segmentation

Methods 이 논문이 사용한 방법론

Spectral Clustering Spectral clustering has attracted increasing attention due to the promising ability in dealing with nonlinearly separable datasets [15], [16]. In spectral clustering, the…

Transfer operators on graphs: Spectral clustering and beyond

2023-05-19 · Stefan Klus, Maia Trower

Graphs and networks play an important role in modeling and analyzing complex interconnected systems such as transportation networks, integrated circuits, power grids, citation graphs, and biological and artificial neural…

Clustering Graph Clustering

Clustering Time-Evolving Networks Using the Spatio-Temporal Graph Laplacian

2024-07-12 · Maia Trower, Nataša Djurdjevac Conrad, Stefan Klus

Time-evolving graphs arise frequently when modeling complex dynamical systems such as social networks, traffic flow, and biological processes. Developing techniques to identify and analyze communities in these time-varyi…

Clustering

Spectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models

2024-03-28 · Ning Zhang, Xiaowen Dong, Mihai Cucuringu

Graph clustering is a fundamental task in unsupervised learning with broad real-world applications. While spectral clustering methods for undirected graphs are well-established and guided by a minimum cut optimization co…

Clustering Graph Clustering Stochastic Block Model

Learning Spatio-Temporal Dynamics via Operator-Valued RKHS and Kernel Koopman Methods

2025-08-23 · Mahishanka Withanachchi arxiv

We introduce a unified framework for learning the spatio-temporal dynamics of vector valued functions by combining operator valued reproducing kernel Hilbert spaces (OV-RKHS) with kernel based Koopman operator methods. T…

Generalized Spectral Clustering for Directed and Undirected Graphs

2022-03-07 · Harry Sevi, Matthieu Jonckheere, Argyris Kalogeratos

Spectral clustering is a popular approach for clustering undirected graphs, but its extension to directed graphs (digraphs) is much more challenging. A typical workaround is to naively symmetrize the adjacency matrix of …

Clustering graph partitioning