Skip to Main content Skip to Navigation
Conference papers

SPONGE: A generalized eigenproblem for clustering signed networks

Mihai Cucuringu 1 Peter Davies 2 Aldo Glielmo 3 Hemant Tyagi 4
4 MODAL - MOdel for Data Analysis and Learning
LPP - Laboratoire Paul Painlevé - UMR 8524, Université de Lille, Sciences et Technologies, Inria Lille - Nord Europe, METRICS - Evaluation des technologies de santé et des pratiques médicales - ULR 2694, Polytech Lille - École polytechnique universitaire de Lille
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 dis-joint 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/hal-02379505
Contributor : Hemant Tyagi <>
Submitted on : Monday, November 25, 2019 - 5:00:55 PM
Last modification on : Friday, November 27, 2020 - 2:18:02 PM
Long-term archiving on: : Wednesday, February 26, 2020 - 9:50:26 PM

File

418-supp.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02379505, version 1

Collections

Citation

Mihai Cucuringu, Peter Davies, Aldo Glielmo, Hemant Tyagi. SPONGE: A generalized eigenproblem for clustering signed networks. AISTATS, Apr 2019, Okinawa, Japan. ⟨hal-02379505⟩

Share

Metrics

Record views

40

Files downloads

326