Affordable Access

Learning latent structure of large random graphs

Authors
  • Diel, Roland
  • Le Corff, Sylvain
  • Lerasle, Matthieu
Publication Date
Jul 03, 2017
Source
HAL-UPMC
Keywords
Language
English
License
Unknown
External links

Abstract

In this paper, we estimate the distribution of hidden nodes weights in large random graphs from the observation of very few edges weights. In this very sparse setting, the first non-asymptotic risk bounds for maximum likelihood estimators (MLE) are established. The proof relies on the construction of a graphical model encoding conditional dependencies that is extremely efficient to study n-regular graphs obtained using a round-robin scheduling. This graphical model allows to prove geometric loss of memory properties and deduce the asymp-totic behavior of the likelihood function. Following a classical construction in learning theory, the asymptotic likelihood is used to define a measure of performance for the MLE. Risk bounds for the MLE are finally obtained by subgaussian deviation results derived from concentration inequalities for Markov chains applied to our graphical model.

Report this publication

Statistics

Seen <100 times