We propose a novel distributed algorithm to decompose graphs or cluster data.
The algorithm recovers the solution obtained from spectral clustering without
need for expensive eigenvalue/ eigenvector computations. We demonstrate that by
solving the wave equation on the graph, every node can assign itself to a
cluster by performing a local fast Fourier transform. We prove the equivalence
of our algorithm to spectral clustering, derive convergence rates and
demonstrate it on examples.