# SPONGE: A generalized eigenproblem for clustering signed networks

Source: [SPONGE: A generalized eigenproblem for clustering signed networks](<https://www.sota2.com/research/paper/68fa55da1e209131ce997937>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T13:48:43.673Z

Authors: Mihai Cucuringu, Peter Davies, Aldo Glielmo, Hemant Tyagi

Published: 2019-04-18T02:55:22.000Z

## 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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Polarized Community Discovery on WikiV](<https://www.sota2.com/research/sota/polarized-community-discovery-on-wikiv.md>): Polarized Community Discovery; WikiV; POL Score: 15.8.

- [Polarized Community Discovery on REF](<https://www.sota2.com/research/sota/polarized-community-discovery-on-ref.md>): Polarized Community Discovery; REF; POL: 41.5.

- [Polarized Community Discovery on BTC](<https://www.sota2.com/research/sota/polarized-community-discovery-on-btc.md>): Polarized Community Discovery; BTC; POL Score: 5.1.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1904.08575>)

[PDF](<https://arxiv.org/pdf/1904.08575.pdf>)