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

Understand

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.