A Dynamic Mode Decomposition Approach for Decentralized Spectral Clustering of Graphs

Abstract

We propose a novel robust decentralized graph clustering algorithm that is provably equivalent to the popular spectral clustering approach. Our proposed method uses the existing wave equation clustering algorithm that is based on propagating waves through the graph. However, instead of using a fast Fourier transform (FFT) computation at every node, our proposed approach exploits the Koopman operator framework. Specifically, we show that propagating waves in the graph followed by a local dynamic mode decomposition (DMD) computation at every node is capable of retrieving the eigenvalues and the local eigenvector components of the graph Laplacian, thereby providing local cluster assignments for all nodes. We demonstrate that the DMD computation is more robust than the existing FFT based approach and requires 20 times fewer steps of the wave equation to accurately recover the clustering information and reduces the relative error by orders of magnitude. We demonstrate the decentralized approach on a range of graph clustering problems.

arXiv commentAccepted by IEEE CCTA 2022

References in corpus (7)

• Community structure in social and biological networks
• Cooperative Game Theory Approaches for Network Partitioning
• On Dynamic Mode Decomposition: Theory and Applications
• Data-driven model reduction and transfer operator approximation
• On the Structure of Time-delay Embedding in Linear Models of Non-linear Dynamical Systems
• An efficient algorithm for the parallel solution of high-dimensional differential equations
• A Spectral Assignment Approach for the Graph Isomorphism Problem

Cited by in corpus (2)

• Advanced Unsupervised Learning: A Comprehensive Overview of Multi-View Clustering Techniques
• Koopman-based spectral clustering of directed and time-evolving graphs