Graph Learning Over Partially Observed Diffusion Networks: Role of Degree Concentration
Vincenzo Matta, Augusto Santos, Ali H. Sayed
IEEE Open Journal of Signal Processing · 2022
doi:10.1109/ojsp.2022.3189315 (opens in a new tab)
We email you when a new notice or a question about this paper appears.
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 (<italic>partial observability</italic>). 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 <italic>identifiability gap</italic>, 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 <italic>universal</italic> clustering algorithm inspired by the <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-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 <italic>random</italic> graph under <italic>statistical concentration</italic> 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 <italic>dense</italic> regime where the probed nodes are influenced by many connections coming from the latent (hidden) part of the graph. Second, we answer a <italic>sample complexity</italic> question and establish that the number of samples for the Granger estimator scales almost <italic>quadratically</italic> 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.
Abstract licence: CC BY-NC-ND
Reads
Read by people on this page
None yet.
Checked or read by AI through naulon
None yet.
A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.
Are you an author?
Is this your paper?
Claim it to add your note and be paid when agents cite it. Free.