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

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 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.