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

  • 2021-05-03 16:36:27
  • Alexander Modell, Patrick Rubin-Delanchy
  • 0


This paper shows that graph spectral embedding using the random walkLaplacian produces vector representations which are completely corrected fornode degree. Under a generalised random dot product graph, the embeddingprovides uniformly consistent estimates of degree-corrected latent positions,with asymptotically Gaussian error. In the special case of a degree-correctedstochastic 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 commonlyrequired by algorithms based on the adjacency or normalised, symmetricLaplacian matrices. While the estimand does not depend on degree, theasymptotic variance of its estimate does -- higher degree nodes are embeddedmore accurately than lower degree nodes. Our central limit theorem thereforesuggests fitting a weighted Gaussian mixture model as the subsequent clusteringstep, for which we provide an expectation-maximisation algorithm.


Quick Read (beta)

loading the full paper ...