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.
Pedro Mercado (Saarland University / University of Tübingen)
Francesco Tudisco (University of Strathclyde)
Matthias Hein (University of Tübingen)
Related Events (a corresponding poster, oral, or spotlight)
2019 Poster: Spectral Clustering of Signed Graphs via Matrix Power Means »
Thu Jun 13th 06:30 -- 09:00 PM Room Pacific Ballroom