Spectral Clustering of Signed Graphs via Matrix Power Means
  Signed graphs encode positive (attractive) and negative (repulsive) relations
between nodes. We extend spectral clustering to signed graphs via the
one-parameter family of Signed Power Mean Laplacians, defined as the matrix
power mean of normalized standard and signless Laplacians of positive and
negative edges. We provide a thorough analysis of the proposed approach in the
setting of a general Stochastic Block Model that includes models such as the
Labeled Stochastic Block Model and the Censored Block Model. We show that in
expectation the signed power mean Laplacian captures the ground truth clusters
under reasonable settings where state-of-the-art approaches fail. Moreover, we
prove that the eigenvalues and eigenvector of the signed power mean Laplacian
concentrate around their expectation under reasonable conditions in the general
Stochastic Block Model. Extensive experiments on random graphs and real world
datasets confirm the theoretically predicted behaviour of the signed power mean
Laplacian and show that it compares favourably with state-of-the-art methods.
