2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | G.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
