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.