2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | G.1.1 | ||
| Paper Title | Approximate Recovery Of Ising Models with Side Information | ||
| Authors | Saurabh Sihag, Ali Tajer, RPI, 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 | This paper considers the problem of recovering the edge structures of two partially identical graphs in the class of Ising models. It is assumed that both graphs have the same number of nodes and a known {\em subset} of nodes have identical structures in both graphs. Therefore, inferring the structure of one graph can provide the side information that could be leveraged for inference related to the other graph. The objective is to recover the connectivity of both graphs under an approximate recovery criterion. The degree- and edge-bounded subclass of Ising models is considered and necessary conditions (information-theoretic) and sufficient conditions for the sample complexity to achieve a bounded probability of error are established. Furthermore, the scaling behavior of the sample complexity is analyzed in different regimes and specific regimes are identified for which the necessary and sufficient conditions coincide, thus, establishing the optimal sample complexity. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
