Technical Program

Paper Detail

Paper Title Graph Learning with Partial Observations: Role of Degree Concentration
Paper IdentifierTU4.R5.4
Authors Vincenzo Matta, University of Salerno, Italy; Augusto Santos, Ali H. Sayed, École polytechnique fédérale de Lausanne (EPFL), Switzerland
Session Graphical Models
Location Saint Victor, Level 3
Session Time Tuesday, 09 July, 16:40 - 18:00
Presentation Time Tuesday, 09 July, 17:40 - 18:00
Manuscript  Click here to download the manuscript
Abstract In this work we consider the problem of learning an Erdös-Rényi 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 one-lag 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.