Regularization Methods for Prediction in Dynamic Graphs

Dr. Emile Richard
Postdoc, Centre de Bio-informatique
Ecole des Mines ParisTech Institut Curie
Given on: November 27, 2012


Predicting connections among objects, based either on a noisy observation or on a sequence of observations, is a problem of interest for numerous applications such as recommender systems for e-commerce and social networks, and also in system biology, for inferring interaction patterns among proteins. This work presents formulations of the graph prediction problem, in both dynamic and static scenarios, as regularization problems. In the static scenario we encode the mixture of two different kinds of structural assumptions in a convex penalty involving the L1 and the trace norm. In the dynamic setting we assume that certain graph features, such as the node degree, follow a vector autoregressive model and we propose to use this information to improve the accuracy of prediction. The solutions of the optimization problems are studied both from an algorithmic and statistical point of view. Empirical evidences on synthetic and real data are presented showing the benefit of using the suggested methods.


Emile Richard received an M.Sc. degree from Ecole Centrale Paris, and the M.Sc. and Ph.D degrees from Ecole Normale Superieure, Cachan. He is now a postdoc at the Centre de Bio-informatique at the Ecole des Mines ParisTech Institut Curie.