SPONGE: A generalized eigenproblem for clustering signed networks

Mihai Cucuringu, Peter Davies, Aldo Glielmo, Hemant Tyagi
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:1088-1098, 2019.

Abstract

We introduce a principled and theoretically sound spectral method for k-way clustering in signed graphs, where the affinity measure between nodes takes either positive or negative values. Our approach is motivated by social balance theory, where the task of clustering aims to decompose the network into disjoint groups such that individuals within the same group are connected by as many positive edges as possible, while individuals from different groups are connected by as many negative edges as possible. Our algorithm relies on a generalized eigenproblem formulation inspired by recent work on constrained clustering. We provide theoretical guarantees for our approach in the setting of a signed stochastic block model, by leveraging tools from matrix perturbation theory and random matrix theory. An extensive set of numerical experiments on both synthetic and real data shows that our approach compares favorably with state-of-the-art methods for signed clustering, especially for large number of clusters and sparse measurement graphs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-cucuringu19a, title = {SPONGE: A generalized eigenproblem for clustering signed networks}, author = {Cucuringu, Mihai and Davies, Peter and Glielmo, Aldo and Tyagi, Hemant}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {1088--1098}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/cucuringu19a/cucuringu19a.pdf}, url = {https://proceedings.mlr.press/v89/cucuringu19a.html}, abstract = {We introduce a principled and theoretically sound spectral method for k-way clustering in signed graphs, where the affinity measure between nodes takes either positive or negative values. Our approach is motivated by social balance theory, where the task of clustering aims to decompose the network into disjoint groups such that individuals within the same group are connected by as many positive edges as possible, while individuals from different groups are connected by as many negative edges as possible. Our algorithm relies on a generalized eigenproblem formulation inspired by recent work on constrained clustering. We provide theoretical guarantees for our approach in the setting of a signed stochastic block model, by leveraging tools from matrix perturbation theory and random matrix theory. An extensive set of numerical experiments on both synthetic and real data shows that our approach compares favorably with state-of-the-art methods for signed clustering, especially for large number of clusters and sparse measurement graphs.} }
Endnote
%0 Conference Paper %T SPONGE: A generalized eigenproblem for clustering signed networks %A Mihai Cucuringu %A Peter Davies %A Aldo Glielmo %A Hemant Tyagi %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-cucuringu19a %I PMLR %P 1088--1098 %U https://proceedings.mlr.press/v89/cucuringu19a.html %V 89 %X We introduce a principled and theoretically sound spectral method for k-way clustering in signed graphs, where the affinity measure between nodes takes either positive or negative values. Our approach is motivated by social balance theory, where the task of clustering aims to decompose the network into disjoint groups such that individuals within the same group are connected by as many positive edges as possible, while individuals from different groups are connected by as many negative edges as possible. Our algorithm relies on a generalized eigenproblem formulation inspired by recent work on constrained clustering. We provide theoretical guarantees for our approach in the setting of a signed stochastic block model, by leveraging tools from matrix perturbation theory and random matrix theory. An extensive set of numerical experiments on both synthetic and real data shows that our approach compares favorably with state-of-the-art methods for signed clustering, especially for large number of clusters and sparse measurement graphs.
APA
Cucuringu, M., Davies, P., Glielmo, A. & Tyagi, H.. (2019). SPONGE: A generalized eigenproblem for clustering signed networks. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:1088-1098 Available from https://proceedings.mlr.press/v89/cucuringu19a.html.

Related Material