# Community Detection with Known, Unknown, or Partially Known Auxiliary Latent Variables

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

## Key facts

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

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [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)
- [Network reconstruction and community detection from dynamics](https://mlsanity.com/paper/1903.10833/) (2019)
- [Community Detection via Random and Adaptive Sampling](https://mlsanity.com/paper/1402.3072/) (2014)
- [Information-theoretic Limits for Community Detection in Network Models](https://mlsanity.com/paper/1802.06104/) (2018)
- [Spectral Detection in the Censored Block Model](https://mlsanity.com/paper/1502.00163/) (2015)
- [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)
- [Semidefinite Programming for Community Detection with Side Information](https://mlsanity.com/paper/2105.02816/) (2021)
- [Exponential random graph models for networks with community structure](https://mlsanity.com/paper/1305.4014/) (2013)
- [Community Detection: Exact Recovery in Weighted Graphs](https://mlsanity.com/paper/2102.04439/) (2021)
- [A Preference Random Walk Algorithm for Link Prediction through Mutual Influence Nodes in Complex Networks](https://mlsanity.com/paper/2105.09494/) (2021)

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

- [Community Detection in the Multi-View Stochastic Block Model](https://mlsanity.com/paper/2401.09510/) (2024)

## Abstract (arXiv)

Empirical observations suggest that in practice, community membership does not completely explain the dependency between the edges of an observation graph. The residual dependence of the graph edges are modeled in this paper, to first order, by auxiliary node latent variables that affect the statistics of the graph edges but carry no information about the communities of interest. We then study community detection in graphs obeying the stochastic block model and censored block model with auxiliary latent variables. We analyze the conditions for exact recovery when these auxiliary latent variables are unknown, representing unknown nuisance parameters or model mismatch. We also analyze exact recovery when these secondary latent variables have been either fully or partially revealed. Finally, we propose a semidefinite programming algorithm for recovering the desired labels when the secondary labels are either known or unknown. We show that exact recovery is possible by semidefinite programming down to the respective maximum likelihood exact recovery threshold.