Journal
2020 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT)
Volume -, Issue -, Pages 1319-1324Publisher
IEEE
DOI: 10.1109/isit44484.2020.9174062
Keywords
-
Funding
- U.S. National Science Foundation [DMS-1737976, ECCS-1933107]
Ask authors/readers for more resources
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 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available