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.
WOS:000489100301081
2019-01-01
978-1-5386-9291-2
New York
IEEE International Symposium on Information Theory
1312
1316
REVIEWED
Event name | Event place | Event date |
Paris, FRANCE | Jul 07-12, 2019 | |