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

arXiv: https://arxiv.org/abs/2105.00987 · HTML: https://mlsanity.com/paper/2105.00987/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 52 references that are in the map.
- First posted on arXiv 3 May 2021.

## Builds on (most cited first, 20 of 20)

- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Cooperative Game Theory Approaches for Network Partitioning](https://mlsanity.com/paper/1707.03587/) (2017)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [A statistical interpretation of spectral embedding: the generalised random dot product graph](https://mlsanity.com/paper/1709.05506/) (2017)
- [Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel](https://mlsanity.com/paper/1309.4111/) (2013)
- [Scale-free networks are rare](https://mlsanity.com/paper/1801.03400/) (2018)
- [Community Detection in Degree-Corrected Block Models](https://mlsanity.com/paper/1607.06993/) (2016)
- [Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embedding](https://mlsanity.com/paper/1310.0532/) (2013)
- [Community Detection and Classification in Hierarchical Stochastic Blockmodels](https://mlsanity.com/paper/1503.02115/) (2015)
- [Limit theorems for eigenvectors of the normalized Laplacian for random graphs](https://mlsanity.com/paper/1607.08601/) (2016)
- [Convexified Modularity Maximization for Degree-corrected Stochastic Block Models](https://mlsanity.com/paper/1512.08425/) (2015)
- [Extraction and Analysis of Fictional Character Networks: A Survey](https://mlsanity.com/paper/1907.02704/) (2019)
- [Spectral clustering on spherical coordinates under the degree-corrected stochastic blockmodel](https://mlsanity.com/paper/2011.04558/) (2020)
- [Vertex nomination schemes for membership prediction](https://mlsanity.com/paper/1312.2638/) (2013)
- [Role of normalization in spectral clustering for stochastic blockmodels](https://mlsanity.com/paper/1310.1495/) (2013)
- [A spectral method for community detection in moderately-sparse degree-corrected stochastic block models](https://mlsanity.com/paper/1506.08621/) (2015)
- [CSNE: Conditional Signed Network Embedding](https://mlsanity.com/paper/2005.10701/) (2020)
- [Bayesian Degree-Corrected Stochastic Blockmodels for Community Detection](https://mlsanity.com/paper/1309.4796/) (2013)

## Built on by (most cited first, 7 of 7)

- [Matrix factorisation and the interpretation of geodesic distance](https://mlsanity.com/paper/2106.01260/) (2021)
- [Centrality Graph Shift Operators for Graph Neural Networks](https://mlsanity.com/paper/2411.04655/) (2024)
- [Latent structure blockmodels for Bayesian spectral graph clustering](https://mlsanity.com/paper/2107.01734/) (2021)
- [Spectral embedding and the latent geometry of multipartite networks](https://mlsanity.com/paper/2202.03945/) (2022)
- [Adjacency Spectral Embeddings of Correlation Networks](https://mlsanity.com/paper/2602.21055/) (2026)
- [The ASE-LSE Disagreement Landscape: An End-to-End Characterisation of Extremes and Structural Drivers](https://mlsanity.com/paper/2605.22346/) (2026)
- [Spectral Embeddings of Degree-α Laplacians in Random Dot Product Graphs](https://mlsanity.com/paper/2608.10845/) (2026)

## Abstract (arXiv)

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.