Timezone: »
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.
Author Information
Guillaume Papa (Télécom ParisTech)
Aurélien Bellet (INRIA)
Stephan Clémençon (Telecom ParisTech)
More from the Same Authors
-
2020 : Distributed Differentially Private Averaging with Improved Utility and Robustness to Malicious Parties »
Aurélien Bellet -
2020 : Privacy Amplification by Decentralization »
Aurélien Bellet -
2021 Poster: Federated Multi-Task Learning under a Mixture of Distributions »
Othmane Marfoq · Giovanni Neglia · Aurélien Bellet · Laetitia Kameni · Richard Vidal -
2020 Workshop: Privacy Preserving Machine Learning - PriML and PPML Joint Edition »
Borja Balle · James Bell · Aurélien Bellet · Kamalika Chaudhuri · Adria Gascon · Antti Honkela · Antti Koskela · Casey Meehan · Olga Ohrimenko · Mi Jung Park · Mariana Raykova · Mary Anne Smart · Yu-Xiang Wang · Adrian Weller -
2020 Session: Orals & Spotlights Track 10: Social/Privacy »
Yanan Sui · Aurélien Bellet -
2018 Workshop: Privacy Preserving Machine Learning »
Adria Gascon · Aurélien Bellet · Niki Kilbertus · Olga Ohrimenko · Mariana Raykova · Adrian Weller -
2018 : Aurélien Bellet »
Aurélien Bellet -
2018 Poster: On Binary Classification in Extreme Regions »
Hamid Jalalzai · Stephan Clémençon · Anne Sabourin -
2017 : Personalized and Private Peer-to-Peer Machine Learning »
Aurélien Bellet · Rachid Guerraoui · Marc Tommasi -
2016 Workshop: Private Multi-Party Machine Learning »
Borja Balle · Aurélien Bellet · David Evans · Adrià Gascón -
2015 Poster: SGD Algorithms based on Incomplete U-statistics: Large-Scale Minimization of Empirical Risk »
Guillaume Papa · Stéphan Clémençon · Aurélien Bellet -
2015 Poster: Extending Gossip Algorithms to Distributed Estimation of U-statistics »
Igor Colin · Aurélien Bellet · Joseph Salmon · Stéphan Clémençon -
2015 Spotlight: Extending Gossip Algorithms to Distributed Estimation of U-statistics »
Igor Colin · Aurélien Bellet · Joseph Salmon · Stéphan Clémençon -
2008 Poster: Empirical performance maximization for linear rank statistics »
Stephan Clémençon · Nicolas Vayatis -
2008 Poster: On Bootstrapping the ROC Curve »
Patrice Bertail · Stephan Clémençon · Nicolas Vayatis -
2008 Poster: Overlaying classifiers: a practical approach for optimal ranking »
Stephan Clémençon · Nicolas Vayatis