Spectral Clustering of Signed Graphs via Matrix Power Means
Pedro Mercado · Francesco Tudisco · Matthias Hein

Thu Jun 13th 11:30 -- 11:35 AM @ Room 103

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.

Author Information

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)