Spectral clustering under degree heterogeneity: a case for the random walk Laplacian

Abstract

This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. Under a generalised random dot product graph, the embedding provides uniformly consistent estimates of degree-corrected latent positions, with asymptotically Gaussian error. In the special case of a degree-corrected stochastic block model, the embedding concentrates about K distinct points, representing communities. These can be recovered perfectly, asymptotically, through a subsequent clustering step, without spherical projection, as commonly required by algorithms based on the adjacency or normalised, symmetric Laplacian matrices. While the estimand does not depend on degree, the asymptotic variance of its estimate does -- higher degree nodes are embedded more accurately than lower degree nodes. Our central limit theorem therefore suggests fitting a weighted Gaussian mixture model as the subsequent clustering step, for which we provide an expectation-maximisation algorithm.

arXiv comment22 pages, 10 figures

References in corpus (9)

• Statistical mechanics of complex networks
• Cooperative Game Theory Approaches for Network Partitioning
• Stochastic blockmodels and community structure in networks
• Fast community detection by SCORE
• Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
• Vertex nomination schemes for membership prediction
• CSNE: Conditional Signed Network Embedding
• Spectral clustering on spherical coordinates under the degree-corrected stochastic blockmodel
• Persistent Homology of Graph Embeddings

Cited by in corpus (2)

• Latent structure blockmodels for Bayesian spectral graph clustering
• Matrix factorisation and the interpretation of geodesic distance