A Dynamic Mode Decomposition Approach for Decentralized Spectral
  Clustering of Graphs
  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.
