Technical Program

Paper Detail

Paper IDG.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

Visit Website!