Dynamic Spectral Methods for Community Detection using Grassmann Geodesics

Abstract

Detecting and tracking evolving communities is an important task in network sci- ence and machine learning, with applications e.g. in neuroscience and sociology. Many classical algorithms for static community detection arise as spectral relaxations of parti- tion objectives that reward higher intra-community edge densities alongside lower (than expected) inter-community edge densities. In this report we review derivations of such algorithms, interpreting each as a flavor of principal component analysis applied to node embeddings. In this light it becomes natural to consider dynamic generalizations as subspace tracking problems. We focus in particular on a dynamic generalization of spectral clustering, formulated as a subspace tracking problem wherein the sequence of graph Laplacian subspaces is constrained to trace a suitably regular trajectory along the Grassmann manifold. Our work uses a recently developed subspace tracking approach that learns the Grassmann geodesic parameters which best fit the data. Performance on synthetic data and real data is benchmarked against various dynamic community detection algorithms, as well as against other Grassmann subspace tracking methods, which we adapt for this application. These preliminary experiments indicate that our algorithms generally perform well relative to the benchmarks.