Graph Learning Over Partially Observed Diffusion Networks: Role of Degree Concentration

Abstract

This work examines the problem of learning the topology of a network from the samples of a diffusion process evolving at the network nodes, under the restriction that a limited fraction thereof is probed (partial observability). We provide the following main contributions. Given an estimator of the combination matrix (i.e., the matrix that quantifies the pairwise interaction between nodes), we introduce the notion of identifiability gap, a minimum separation between the entries of the estimated matrix that is critical to enable discrimination between connected and unconnected node pairs. Then we focus on the popular Granger estimator. First, we prove that this matrix estimator, followed by a universal clustering algorithm inspired by the $k$-means algorithm, learns faithfully the probed subgraph as the network size increases. This result is proved for the case where the network topology is obtained through an Erdős-Rényi random graph under statistical concentration of the node degrees, and the combination matrix is symmetric with nonzero entries bounded in terms of the reciprocal of the maximal and minimal degree. The analysis explores different connectivity regimes, including the dense regime where the probed nodes are influenced by many connections coming from the latent (hidden) part of the graph. Second, we answer a sample complexity question and establish that the number of samples for the Granger estimator scales almost quadratically with the expected graph degree. We also propose three other estimators that are proved to achieve faithful graph learning, and compare them to the Granger estimator, gaining nontrivial insights especially for the case of directed graphs.

Keywords

• Graph learning
• network tomography
• dense networks
• Granger estimator
• diffusion network
• Erdős-Rényi graph