Spectral Clustering of Signed Graphs via Matrix Power Means

Signed graphs can be used to encode positive (attractive) and negative (repulsive) relations between nodes. We propose to merge the information from positive and negative edges via the one-parameter family of signed power mean Laplacians defined as the matrix power mean of standard and signless Laplacians. We analyze the signed power mean Laplacian in the stochastic block model in expectation and show that it outperforms the state of the art in terms of conditions under which it recovers the ground truth clusters. Moreover, under the stochastic block model we show concentration around its expectation of eigenvalues and eigenvectors of the signed power mean Laplacian. Finally, we provide an extensive comparison to existing methods on real world datasets.