Graph Prediction in a Low-Rank and Autoregressive Setting
This work addresses graph prediction for applications like social networks or biological systems, but it appears incremental as it builds on existing convex optimization frameworks without a major breakthrough.
The authors tackled the problem of prediction for evolving graph data by formulating it as a convex optimization problem that encourages sparsity and low-rank properties, leading to oracle inequalities and efficient solvers. They provided empirical results and comparisons with competing methods, though no specific numerical gains were reported.
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.