Spectral Clustering of Signed Graphs via Matrix Power Means

Pedro Mercado, Francesco Tudisco, Matthias Hein
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:4526-4536, 2019.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-mercado19a, title = {Spectral Clustering of Signed Graphs via Matrix Power Means}, author = {Mercado, Pedro and Tudisco, Francesco and Hein, Matthias}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {4526--4536}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/mercado19a/mercado19a.pdf}, url = {https://proceedings.mlr.press/v97/mercado19a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Spectral Clustering of Signed Graphs via Matrix Power Means %A Pedro Mercado %A Francesco Tudisco %A Matthias Hein %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-mercado19a %I PMLR %P 4526--4536 %U https://proceedings.mlr.press/v97/mercado19a.html %V 97 %X 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.
APA
Mercado, P., Tudisco, F. & Hein, M.. (2019). Spectral Clustering of Signed Graphs via Matrix Power Means. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:4526-4536 Available from https://proceedings.mlr.press/v97/mercado19a.html.

Related Material