# Phase transitions in semisupervised clustering of sparse networks

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Apr 2014.

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

- [Homophily modulates double descent generalization in graph convolution networks](https://mlsanity.com/paper/2212.13069/) (2022)
- [Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries](https://mlsanity.com/paper/2102.00504/) (2021)
- [Neural-prior stochastic block model](https://mlsanity.com/paper/2303.09995/) (2023)
- [Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold](https://mlsanity.com/paper/2205.11677/) (2022)
- [PATTERN Can Be Solved from Memory: Generator-Aware Baselines for Synthetic Node Classification](https://mlsanity.com/paper/2610.15020/) (2026)

## Abstract (arXiv)

Predicting labels of nodes in a network, such as community memberships or demographic variables, is an important problem with applications in social and biological networks. A recently-discovered phase transition puts fundamental limits on the accuracy of these predictions if we have access only to the network topology. However, if we know the correct labels of some fraction α of the nodes, we can do better. We study the phase diagram of this "semisupervised" learning problem for networks generated by the stochastic block model. We use the cavity method and the associated belief propagation algorithm to study what accuracy can be achieved as a function of α. For k = 2 groups, we find that the detectability transition disappears for any α > 0, in agreement with previous work. For larger k where a hard but detectable regime exists, we find that the easy/hard transition (the point at which efficient algorithms can do better than chance) becomes a line of transitions where the accuracy jumps discontinuously at a critical value of α. This line ends in a critical point with a second-order transition, beyond which the accuracy is a continuous function of α. We demonstrate qualitatively similar transitions in two real-world networks.