On Graph Reconstruction via Empirical Risk Minimization: Fast Learning Rates and Scalability

Guillaume Papa 1 Stéphan Clémençon 1 Aurélien Bellet 2
2 MAGNET - Machine Learning in Information Networks
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : The problem of predicting connections between a set of data points finds many applications, in systems biology and social network analysis among others. This paper focuses on the \textit{graph reconstruction} problem, where the prediction rule is obtained by minimizing the average error over all n(n-1)/2 possible pairs of the n nodes of a training graph. Our first contribution is to derive learning rates of order O(log n / n) for this problem, significantly improving upon the slow rates of order O(1/√n) established in the seminal work of Biau & Bleakley (2006). Strikingly, these fast rates are universal, in contrast to similar results known for other statistical learning problems (e.g., classification, density level set estimation, ranking, clustering) which require strong assumptions on the distribution of the data. Motivated by applications to large graphs, our second contribution deals with the computational complexity of graph reconstruction. Specifically, we investigate to which extent the learning rates can be preserved when replacing the empirical reconstruction risk by a computationally cheaper Monte-Carlo version, obtained by sampling with replacement B << n² pairs of nodes. Finally, we illustrate our theoretical results by numerical experiments on synthetic and real graphs.
Type de document :
Communication dans un congrès
Annual Conference on Neural Information Processing Systems (NIPS 2016), Dec 2016, Barcelone, Spain. 〈https://nips.cc/Conferences/2016〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01367546
Contributeur : Aurélien Bellet <>
Soumis le : mardi 3 janvier 2017 - 12:03:16
Dernière modification le : mardi 3 juillet 2018 - 11:45:24

Fichiers

nips16.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01367546, version 2

Citation

Guillaume Papa, Stéphan Clémençon, Aurélien Bellet. On Graph Reconstruction via Empirical Risk Minimization: Fast Learning Rates and Scalability. Annual Conference on Neural Information Processing Systems (NIPS 2016), Dec 2016, Barcelone, Spain. 〈https://nips.cc/Conferences/2016〉. 〈hal-01367546v2〉

Partager

Métriques

Consultations de la notice

390

Téléchargements de fichiers

161