  This work examines the problem of graph learning over a diffusion network
when data can be collected from a limited portion of the network (partial
observability). The main question is to establish technical guarantees of
consistent recovery of the subgraph of probed network nodes, i) despite the
presence of unobserved nodes; and ii) under different connectivity regimes,
including the dense regime where the probed nodes are influenced by many
connections coming from the unobserved ones. We ascertain that suitable
estimators of the combination matrix (i.e., the matrix that quantifies the
pairwise interaction between nodes) possess an identifiability gap that enables
the discrimination between connected and disconnected nodes. Fundamental
conditions are established under which the subgraph of monitored nodes can be
recovered, with high probability as the network size increases, through
universal clustering algorithms. This claim is proved for three matrix
estimators: i) the Granger estimator that adapts to the partial observability
setting the solution that is exact under full observability ; ii) the one-lag
correlation matrix; and iii) the residual estimator based on the difference
between two consecutive time samples. A detailed characterization of the
asymptotic behavior of these estimators is established in terms of an error
bias and of the identifiability gap, and a sample complexity analysis is
performed to establish how the number of samples scales with the network size
to achieve consistent learning. Comparison among the estimators is performed
through illustrative examples that show how estimators that are not optimal in
the full observability regime can outperform the Granger estimator in the
partial observability regime. The analysis reveals that the fundamental
property enabling consistent graph learning is the statistical concentration of
node degrees.
