Technical Program

Paper Detail

Paper IDG.1.7
Paper Title Community Detection with Secondary Latent Variables
Authors Mohammad Esmaeili, Aria Nosratinia, The University of Texas at Dallas, United States
Session G.1: Graph Analytics
Presentation Lecture
Track Graphs, Games, Sparsity, and Signal Processing
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract 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.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!