|Community Detection with Secondary Latent Variables
|Mohammad Esmaeili, Aria Nosratinia, The University of Texas at Dallas, United States
|G.1: Graph Analytics
|Graphs, Games, Sparsity, and Signal Processing
|Click here to download the manuscript
|Click here to watch in the Virtual Symposium
|Community detection refers to recovering a (latent) label on which the distribution of the observed graph depends. Recent work has also investigated the impact of additionally knowing the value of another variable at each node that is correlated with the node label (side information), while assuming side information is independent of the graph edges conditioned on the label. This work extends the scope of community detection in two ways. First, we consider a side information that does not form a Markov chain with the label and graph, and analyze the detection threshold of semidefinite programming subject to knowledge of this side information, which is a non-label latent variable on which the graph edges also depend. In the second part of the work, we consider aside from node labels a second latent variable that is unknown both in realization and in distribution. We then investigate the performance of the semidefinite programming community detection as a function of the (unknown) composition of the nuisance latent variable. In both cases, it is shown that semidefinite programming can achieve exact recovery down to the optimal (information theoretic) threshold.