# An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 48 references that are in the map.
- First posted on arXiv 4 Feb 2025.

## Builds on (most cited first, 13 of 13)

- [Fake News Detection on Social Media: A Data Mining Perspective](https://mlsanity.com/paper/1708.01967/) (2017)
- [Convergence Rate of Frank-Wolfe for Non-Convex Objectives](https://mlsanity.com/paper/1607.00345/) (2016)
- [Stochastic Frank-Wolfe Methods for Nonconvex Optimization](https://mlsanity.com/paper/1607.08254/) (2016)
- [A Survey of Signed Network Mining in Social Media](https://mlsanity.com/paper/1511.07569/) (2015)
- [SPONGE: A generalized eigenproblem for clustering signed networks](https://mlsanity.com/paper/1904.08575/) (2019)
- [Discovering Polarized Communities in Signed Networks](https://mlsanity.com/paper/1910.02438/) (2019)
- [SSSNET: Semi-Supervised Signed Network Clustering](https://mlsanity.com/paper/2110.06623/) (2021)
- [Spectral Clustering of Signed Graphs via Matrix Power Means](https://mlsanity.com/paper/1905.06230/) (2019)
- [Finding large balanced subgraphs in signed networks](https://mlsanity.com/paper/2002.00775/) (2020)
- [Correlation Clustering with Active Learning of Pairwise Similarities](https://mlsanity.com/paper/2302.10295/) (2023)
- [Shift of Pairwise Similarities for Data Clustering](https://mlsanity.com/paper/2110.13103/) (2021)
- [Searching for polarization in signed graphs: a local spectral approach](https://mlsanity.com/paper/2001.09410/) (2020)
- [Information-Theoretic Active Correlation Clustering](https://mlsanity.com/paper/2402.03587/) (2024)

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

- [Cold-Start Active Correlation Clustering](https://mlsanity.com/paper/2509.25376/) (2025)

## Abstract (arXiv)

Signed networks, where edges are labeled as positive or negative to represent friendly or antagonistic interactions, provide a natural framework for analyzing polarization, trust, and conflict in social systems. Detecting meaningful group structures in such networks is crucial for understanding online discourse, political divisions, and trust dynamics. A key challenge is to identify communities that are internally cohesive and externally antagonistic, while allowing for neutral or unaligned vertices. In this paper, we propose a method for identifying k polarized communities that addresses a major limitation of prior methods: their tendency to produce highly size-imbalanced solutions. We introduce a novel optimization objective that avoids such imbalance. In addition, it is well known that approximation algorithms based on local search are highly effective for clustering signed networks when neutral vertices are not allowed. We build on this idea and design the first local search algorithm that extends to the setting with neutral vertices while scaling to large networks. By connecting our approach to block-coordinate Frank-Wolfe optimization, we prove a linear convergence rate, enabled by the structure of our objective. Experiments on real-world and synthetic datasets demonstrate that our method consistently outperforms state-of-the-art baselines in solution quality, while remaining competitive in computational efficiency.