Perfect Spectral Clustering with Discrete Covariates
Among community detection methods, spectral clustering enjoys two desirable
properties: computational efficiency and theoretical guarantees of consistency.
Most studies of spectral clustering consider only the edges of a network as
input to the algorithm. Here we consider the problem of performing community
detection in the presence of discrete node covariates, where network structure
is determined by a combination of a latent block model structure and homophily
on the observed covariates. We propose a spectral algorithm that we prove
achieves perfect clustering with high probability on a class of large, sparse
networks with discrete covariates, effectively separating latent network
structure from homophily on observed covariates. To our knowledge, our method
is the first to offer a guarantee of consistent latent structure recovery using
spectral clustering in the setting where edge formation is dependent on both
latent and observed factors.