Title: Learning latent structure of large random graphs,
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.