  We study the problem of prediction for evolving graph data. We formulate the
problem as the minimization of a convex objective encouraging sparsity and
low-rank of the solution, that reflect natural graph properties. The convex
formulation allows to obtain oracle inequalities and efficient solvers. We
provide empirical results for our algorithm and comparison with competing
methods, and point out two open questions related to compressed sensing and
algebra of low-rank and sparse matrices.
