nips nips2012 nips2012-199 nips2012-199-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Emile Richard, Stephane Gaiffas, Nicolas Vayatis
Abstract: In the paper, we consider the problem of link prediction in time-evolving graphs. We assume that certain graph features, such as the node degree, follow a vector autoregressive (VAR) model and we propose to use this information to improve the accuracy of prediction. Our strategy involves a joint optimization procedure over the space of adjacency matrices and VAR matrices which takes into account both sparsity and low rank properties of the matrices. Oracle inequalities are derived and illustrate the trade-offs in the choice of smoothing parameters when modeling the joint effect of sparsity and low rank property. The estimate is computed efficiently using proximal methods through a generalized forward-backward agorithm. 1
[1] J. Abernethy, F. Bach, Th. Evgeniou, and J.-Ph. Vert. A new approach to collaborative filtering: operator estimation with spectral regularization. JMLR, 10:803–826, 2009.
[2] A. Argyriou, M. Pontil, Ch. Micchelli, and Y. Ying. A spectral regularization framework for multi-task structure learning. Proceedings of Neural Information Processing Systems (NIPS), 2007.
[3] P. J. Bickel, Y. Ritov, and A. B. Tsybakov. Simultaneous analysis of lasso and dantzig selector. Annals of Statistics, 37, 2009.
[4] L. Breiman and J. H. Friedman. Predicting multivariate responses in multiple linear regression. Journal of the Royal Statistical Society (JRSS): Series B (Statistical Methodology), 59:3–54, 1997. 8
[5] E.J. Candès and T. Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Transactions on Information Theory, 56(5), 2009.
[6] Candès E. and Tao T. Decoding by linear programming. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2005.
[7] Th. Evgeniou, Ch. A. Micchelli, and M. Pontil. Learning multiple tasks with kernel methods. Journal of Machine Learning Research, 6:615–637, 2005.
[8] S. Gaiffas and G. Lecue. Sharp oracle inequalities for high-dimensional matrix prediction. Information Theory, IEEE Transactions on, 57(10):6942 –6957, oct. 2011.
[9] M. Kolar and E. P. Xing. On time varying undirected graphs. in Proceedings of the 14th International Conference on Artifical Intelligence and Statistics AISTATS, 2011.
[10] V. Koltchinskii. The Dantzig selector and sparsity oracle inequalities. Bernoulli, 15(3):799– 828, 2009.
[11] V. Koltchinskii. Sparsity in penalized empirical risk minimization. Ann. Inst. Henri Poincaré Probab. Stat., 45(1):7–57, 2009.
[12] V. Koltchinskii, K. Lounici, and A. Tsybakov. Nuclear norm penalization and optimal rates for noisy matrix completion. Annals of Statistics, 2011.
[13] Y. Koren. Factorization meets the neighborhood: a multifaceted collaborative filtering model. In Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 426–434. ACM, 2008.
[14] Y. Koren. Collaborative filtering with temporal dynamics. Communications of the ACM, 53(4):89–97, 2010.
[15] D. Liben-Nowell and J. Kleinberg. The link-prediction problem for social networks. Journal of the American society for information science and technology, 58(7):1019–1031, 2007.
[16] S.A. Myers and Jure Leskovec. On the convexity of latent social network inference. In NIPS, 2010.
[17] H. Raguet, J. Fadili, and G. Peyré. Generalized forward-backward splitting. Arxiv preprint arXiv:1108.4404, 2011.
[18] E. Richard, N. Baskiotis, Th. Evgeniou, and N. Vayatis. Link discovery using graph feature tracking. Proceedings of Neural Information Processing Systems (NIPS), 2010.
[19] E. Richard, P.-A. Savalle, and N. Vayatis. Estimation of simultaneously sparse and low-rank matrices. In Proceeding of 29th Annual International Conference on Machine Learning, 2012.
[20] P. Sarkar, D. Chakrabarti, and A.W. Moore. Theoretical justification of popular link prediction heuristics. In International Conference on Learning Theory (COLT), pages 295–307, 2010.
[21] N. Srebro, J. D. M. Rennie, and T. S. Jaakkola. Maximum-margin matrix factorization. In Lawrence K. Saul, Yair Weiss, and Léon Bottou, editors, in Proceedings of Neural Information Processing Systems 17, pages 1329–1336. MIT Press, Cambridge, MA, 2005.
[22] B. Taskar, M.F. Wong, P. Abbeel, and D. Koller. Link prediction in relational data. In Neural Information Processing Systems, volume 15, 2003.
[23] R. S. Tsay. Analysis of Financial Time Series. Wiley-Interscience; 3rd edition, 2005.
[24] S. A. van de Geer and P. Bühlmann. On the conditions used to prove oracle results for the Lasso. Electron. J. Stat., 3:1360–1392, 2009.
[25] D.Q. Vu, A. Asuncion, D. Hunter, and P. Smyth. Continuous-time regression models for longitudinal networks. In Advances in Neural Information Processing Systems. MIT Press, 2011. 9