Graph Learning with Partial Observations: Role of Degree Concentration

In this work we consider the problem of learning an Erdos-Renyi graph over a diffusion network when: i) data from only a limited subset of nodes are available (partial observation); ii) and the inferential goal is to discover the graph of interconnections linking the accessible nodes (local structure learning). We propose three matrix estimators, namely, the Granger, the onelag correlation, and the residual estimators, which, when followed by a universal clustering algorithm, are shown to retrieve the true subgraph in the limit of large network sizes. Remarkably, it is seen that a fundamental role is played by the uniform concentration of node degrees, rather than by sparsity.

Published in:
2019 IEEE International Symposium On Information Theory (Isit), 1312-1316
Presented at:
IEEE International Symposium on Information Theory (ISIT), Paris, FRANCE, Jul 07-12, 2019
Jan 01 2019
New York, IEEE

 Record created 2019-10-27, last modified 2019-10-28

Rate this document:

Rate this document:
(Not yet reviewed)