Statistical inference on graphs

The problem of graph inference, or graph reconstruction, is to predict the presence or absence of edges between a set of given points known to form the vertices of a graph. Motivated by various applications including communication networks and systems biology, we propose a general model for studying the problem of graph inference in a supervised learning framework. In our setting, both the graph vertices and edges are assumed to be random, with a probability distribution that possibly depends on the size of the graph. We show that the problem can be transformed into one where we can use statistical learning methods based on empirical minimization of natural estimates of the reconstruction risk.Convex risk minimizationmethods are also studied to provide a theoretical framework for reconstruction algorithms based on boosting and support vector machines. Our approach is illustrated on simulated graphs.