# A Correlation Clustering Approach to Link Classification in Signed Networks -- Full Version --

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jan 2013.

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

- [Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oracle](https://mlsanity.com/paper/2106.10374/) (2021)
- [CoRet: Improved Retriever for Code Editing](https://mlsanity.com/paper/2505.24715/) (2025)
- [Sublinear-Time Clustering Oracle for Signed Graphs](https://mlsanity.com/paper/2206.13813/) (2022)
- [Active clustering for labeling training data](https://mlsanity.com/paper/2110.14521/) (2021)

## Abstract (arXiv)

Motivated by social balance theory, we develop a theory of link classification in signed networks using the correlation clustering index as measure of label regularity. We derive learning bounds in terms of correlation clustering within three fundamental transductive learning settings: online, batch and active. Our main algorithmic contribution is in the active setting, where we introduce a new family of efficient link classifiers based on covering the input graph with small circuits. These are the first active algorithms for link classification with mistake bounds that hold for arbitrary signed networks.