# Finding large balanced subgraphs in signed networks

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Feb 2020.

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

- [MSGNN: A Spectral Graph Neural Network Based on a Novel Magnetic Signed Laplacian](https://mlsanity.com/paper/2209.00546/) (2022)
- [PyTorch Geometric Signed Directed: A Software Package on Graph Neural Networks for Signed and Directed Graphs](https://mlsanity.com/paper/2202.10793/) (2022)
- [LightDiC: A Simple yet Effective Approach for Large-scale Digraph Representation Learning](https://mlsanity.com/paper/2401.11772/) (2024)
- [Characterizing Polarization in Social Networks using the Signed Relational Latent Distance Model](https://mlsanity.com/paper/2301.09507/) (2023)
- [Signed Graph Autoencoder for Explainable and Polarization-Aware Network Embeddings](https://mlsanity.com/paper/2409.10452/) (2024)
- [Sublinear-Time Clustering Oracle for Signed Graphs](https://mlsanity.com/paper/2206.13813/) (2022)
- [An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks](https://mlsanity.com/paper/2502.02197/) (2025)
- [A Hybrid Membership Latent Distance Model for Unsigned and Signed Integer Weighted Networks](https://mlsanity.com/paper/2308.15293/) (2023)
- [Rethinking Link Prediction for Directed Graphs](https://mlsanity.com/paper/2502.05724/) (2025)
- [Toward Data-centric Directed Graph Learning: An Entropy-driven Approach](https://mlsanity.com/paper/2505.00983/) (2025)

## Abstract (arXiv)

Signed networks are graphs whose edges are labelled with either a positive or a negative sign, and can be used to capture nuances in interactions that are missed by their unsigned counterparts. The concept of balance in signed graph theory determines whether a network can be partitioned into two perfectly opposing subsets, and is therefore useful for modelling phenomena such as the existence of polarized communities in social networks. While determining whether a graph is balanced is easy, finding a large balanced subgraph is hard. The few heuristics available in the literature for this purpose are either ineffective or non-scalable. In this paper we propose an efficient algorithm for finding large balanced subgraphs in signed networks. The algorithm relies on signed spectral theory and a novel bound for perturbations of the graph Laplacian. In a wide variety of experiments on real-world data we show that our algorithm can find balanced subgraphs much larger than those detected by existing methods, and in addition, it is faster. We test its scalability on graphs of up to 34 million edges.