# SPONGE: A generalized eigenproblem for clustering signed networks

arXiv: https://arxiv.org/abs/1904.08575 · HTML: https://mlsanity.com/paper/1904.08575/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Apr 2019.

## Built on by (most cited first, 24 of 24)

- [SSSNET: Semi-Supervised Signed Network Clustering](https://mlsanity.com/paper/2110.06623/) (2021)
- [PyTorch Geometric Signed Directed: A Software Package on Graph Neural Networks for Signed and Directed Graphs](https://mlsanity.com/paper/2202.10793/) (2022)
- [Ollivier-Ricci Curvature for Hypergraphs: A Unified Framework](https://mlsanity.com/paper/2210.12048/) (2022)
- [An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees](https://mlsanity.com/paper/2112.10467/) (2021)
- [Signed Graph Neural Networks: A Frequency Perspective](https://mlsanity.com/paper/2208.07323/) (2022)
- [Exact Community Recovery over Signed Graphs](https://mlsanity.com/paper/2202.12255/) (2022)
- [GegenNet: Spectral Convolutional Neural Networks for Link Sign Prediction in Signed Bipartite Graphs](https://mlsanity.com/paper/2508.19907/) (2025)
- [Federated Myopic Community Detection with One-shot Communication](https://mlsanity.com/paper/2106.07255/) (2021)
- [Sublinear-Time Clustering Oracle for Signed Graphs](https://mlsanity.com/paper/2206.13813/) (2022)
- [Statistical arbitrage in multi-pair trading strategy based on graph clustering algorithms in US equities market](https://mlsanity.com/paper/2406.10695/) (2024)
- [Robust Detection of Lead-Lag Relationships in Lagged Multi-Factor Models](https://mlsanity.com/paper/2305.06704/) (2023)
- [Signed Diverse Multiplex Networks: Clustering and Inference](https://mlsanity.com/paper/2402.10242/) (2024)
- [An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks](https://mlsanity.com/paper/2502.02197/) (2025)
- [Toward Quantum Utility in Finance: A Robust Data-Driven Algorithm for Asset Clustering](https://mlsanity.com/paper/2509.07766/) (2025)
- [A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy](https://mlsanity.com/paper/2102.08019/) (2021)
- [Signed Network Embedding with Application to Simultaneous Detection of Communities and Anomalies](https://mlsanity.com/paper/2207.09324/) (2022)
- [Defensive Alliances in Signed Networks](https://mlsanity.com/paper/2309.06801/) (2023)
- [Signed graphs in data sciences via communicability geometry](https://mlsanity.com/paper/2403.07493/) (2024)
- [A Spectral Framework for Tracking Communities in Evolving Networks](https://mlsanity.com/paper/2412.07378/) (2024)
- [Toward Robust Signed Graph Learning through Joint Input-Target Denoising](https://mlsanity.com/paper/2510.22513/) (2025)
- [Improving the Accuracy of Community Detection on Signed Networks via Community Refinement and Contrastive Learning](https://mlsanity.com/paper/2601.16372/) (2026)
- [Linking Scalar-Intensity Language to Structural Polarization with Validated Signed-Network Measures](https://mlsanity.com/paper/2605.12814/) (2026)
- [Recovering Candidate Circadian Regulators of Arrhythmic Pituitary Hormone Genes Using Reliability-Weighted Magnetic Laplacian with rwMagLap](https://mlsanity.com/paper/2607.06579/) (2026)
- [Signed Graph Pre-Training and Prompt Learning](https://mlsanity.com/paper/2609.25722/) (2026)

## Abstract (arXiv)

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.