# Semi-supervised Community Detection via Structural Similarity Metrics

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 35 references that are in the map.
- First posted on arXiv 1 Jun 2023.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [A statistical interpretation of spectral embedding: the generalised random dot product graph](https://mlsanity.com/paper/1709.05506/) (2017)
- [Community Detection in Degree-Corrected Block Models](https://mlsanity.com/paper/1607.06993/) (2016)
- [Optimizing Generalized PageRank Methods for Seed-Expansion Community Detection](https://mlsanity.com/paper/1905.10881/) (2019)
- [Co-citation and Co-authorship Networks of Statisticians](https://mlsanity.com/paper/2204.11194/) (2022)
- [Convex Relaxation Methods for Community Detection](https://mlsanity.com/paper/1810.00315/) (2018)
- [Improvements on SCORE, Especially for Weak Signals](https://mlsanity.com/paper/1811.05927/) (2018)

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

- [Fundamental limits of community detection from multi-view data: multi-layer, dynamic and partially labeled block models](https://mlsanity.com/paper/2401.08167/) (2024)
- [Semi-supervised Vertex Hunting, with Applications in Network and Text Analysis](https://mlsanity.com/paper/2510.22526/) (2025)

## Abstract (arXiv)

Motivated by social network analysis and network-based recommendation systems, we study a semi-supervised community detection problem in which the objective is to estimate the community label of a new node using the network topology and partially observed community labels of existing nodes. The network is modeled using a degree-corrected stochastic block model, which allows for severe degree heterogeneity and potentially non-assortative communities. We propose an algorithm that computes a `structural similarity metric' between the new node and each of the K communities by aggregating labeled and unlabeled data. The estimated label of the new node corresponds to the value of k that maximizes this similarity metric. Our method is fast and numerically outperforms existing semi-supervised algorithms. Theoretically, we derive explicit bounds for the misclassification error and show the efficiency of our method by comparing it with an ideal classifier. Our findings highlight, to the best of our knowledge, the first semi-supervised community detection algorithm that offers theoretical guarantees.