# Semidefinite Programming for Community Detection with Side Information

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 39 references that are in the map.
- First posted on arXiv 6 May 2021.

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

- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013)
- [A Proof Of The Block Model Threshold Conjecture](https://mlsanity.com/paper/1311.4115/) (2013)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming](https://mlsanity.com/paper/1412.6156/) (2014)
- [Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices](https://mlsanity.com/paper/1402.1267/) (2014)
- [Consistency Thresholds for the Planted Bisection Model](https://mlsanity.com/paper/1407.1591/) (2014)
- [On semidefinite relaxations for the block model](https://mlsanity.com/paper/1406.5647/) (2014)
- [Belief propagation, robust reconstruction and optimal recovery of block models](https://mlsanity.com/paper/1309.1380/) (2013)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions](https://mlsanity.com/paper/1502.07738/) (2015)
- [Community Detection via Random and Adaptive Sampling](https://mlsanity.com/paper/1402.3072/) (2014)
- [Local Algorithms for Block Models with Side Information](https://mlsanity.com/paper/1508.02344/) (2015)
- [Spectral Detection in the Censored Block Model](https://mlsanity.com/paper/1502.00163/) (2015)
- [Recovering a Single Community with Side Information](https://mlsanity.com/paper/1809.01738/) (2018)
- [Density Evolution in the Degree-correlated Stochastic Block Model](https://mlsanity.com/paper/1509.03281/) (2015)
- [Jointly Clustering Rows and Columns of Binary Matrices: Algorithms and Trade-offs](https://mlsanity.com/paper/1310.0512/) (2013)
- [Community Detection: Exact Recovery in Weighted Graphs](https://mlsanity.com/paper/2102.04439/) (2021)

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

- [Community Detection with Known, Unknown, or Partially Known Auxiliary Latent Variables](https://mlsanity.com/paper/2301.04088/) (2023)
- [Community Detection in the Multi-View Stochastic Block Model](https://mlsanity.com/paper/2401.09510/) (2024)
- [Exact Recovery in the Data Block Model](https://mlsanity.com/paper/2602.05852/) (2026)

## Abstract (arXiv)

This paper produces an efficient Semidefinite Programming (SDP) solution for community detection that incorporates non-graph data, which in this context is known as side information. SDP is an efficient solution for standard community detection on graphs. We formulate a semi-definite relaxation for the maximum likelihood estimation of node labels, subject to observing both graph and non-graph data. This formulation is distinct from the SDP solution of standard community detection, but maintains its desirable properties. We calculate the exact recovery threshold for three types of non-graph information, which in this paper are called side information: partially revealed labels, noisy labels, as well as multiple observations (features) per node with arbitrary but finite cardinality. We find that SDP has the same exact recovery threshold in the presence of side information as maximum likelihood with side information. Thus, the methods developed herein are computationally efficient as well as asymptotically accurate for the solution of community detection in the presence of side information. Simulations show that the asymptotic results of this paper can also shed light on the performance of SDP for graphs of modest size.