nips nips2010 nips2010-162 nips2010-162-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Emile Richard, Nicolas Baskiotis, Theodoros Evgeniou, Nicolas Vayatis
Abstract: We consider the problem of discovering links of an evolving undirected graph given a series of past snapshots of that graph. The graph is observed through the time sequence of its adjacency matrix and only the presence of edges is observed. The absence of an edge on a certain snapshot cannot be distinguished from a missing entry in the adjacency matrix. Additional information can be provided by examining the dynamics of the graph through a set of topological features, such as the degrees of the vertices. We develop a novel methodology by building on both static matrix completion methods and the estimation of the future state of relevant graph features. Our procedure relies on the formulation of an optimization problem which can be approximately solved by a fast alternating linearized algorithm whose properties are examined. We show experiments with both simulated and real data which reveal the interest of our methodology. 1
[1] A. L. Barab´ si, H. Jeong, Z. Nda, A. Schubert, and T. Vicsek. Evolution of the social network a of scientific collaborations. Physica A: Statistical Mechanics and its Applications, 311(34):590–614, 2002.
[2] Emmanuel J. Cand` s and Terence. Tao. A singular value thresholding algorithm for matrix e completion. SIAM Journal on Optimization, 20(4):1956–1982, 2008.
[3] Emmanuel J. Cand` s and Terence Tao. The power of convex relaxation: Near-optimal matrix e completion. IEEE Transactions on Information Theory, 56(5), 2009.
[4] Lise Getoor and Christopher P. Diehl. Link mining: a survey. SIGKDD Explorations Newsletter, 7(2):3–12, 2005.
[5] Donald Goldfarb and Shiqlan Ma. Fast alternating linearization methods for minimizing the sum of two convex functions. Technical Report, Department of IEOR, Columbia University, 2009.
[6] Yifan Hu, Yehuda Koren, and Chris Volinsky. Collaborative filtering for implicit feedback datasets. In Proceedings of the 8th IEEE International Conference on Data Mining (ICDM 2008), pages 263–272, 2008.
[7] Hisashi Kashima, Tsuyoshi Kato, Yoshihiro Yamanishi, Masashi Sugiyama, and Koji Tsuda. Link propagation: A fast semi-supervised learning algorithm for link prediction. In Proceedings of the SIAM International Conference on Data Mining, SDM 2009, pages 1099–1110, 2009.
[8] Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39–43, 1953.
[9] David Liben-Nowell and Jon Kleinberg. The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology, 58(7):1019–1031, 2007.
[10] Tanya Y. Berger-Wolf Mayank Lahiri. Structure prediction in temporal networks using frequent subgraphs. IEEE Symposium on Computational Intelligence and Data Mining (CIDM), 2007. 8
[11] Kurt Miller, Thomas Griffiths, and Michael Jordan. Nonparametric latent feature models for link prediction. In Y. Bengio, D. Schuurmans, J. Lafferty, C. K. I. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems 22, pages 1276–1284. 2009.
[12] Yu Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103(1):127–152, 2005.
[13] Purnamrita Sarkar, Sajid Siddiqi, and Geoffrey J. Gordon. A latent space approach to dynamic embedding of cooccurrence data. In In Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics (AI-STATS), 2007.
[14] Ashish Sood, Gareth M. James, and Gerard J. Tellis. Functional regression: A new model for predicting market penetration of new products. Marketing Science, 28(1):36–51, 2009.
[15] Nathan Srebro, Jason D. M. Rennie, and Tommi S. Jaakkola. Maximum-margin matrix factorization. In Lawrence K. Saul, Yair Weiss, and L´ on Bottou, editors, Advances in Neural e Information Processing Systems 17, pages 1329–1336. MIT Press, Cambridge, MA, 2005.
[16] Ben Taskar, Ming-Fai Wong, Pieter Abbeel, and Daphne Koller. Link prediction in relational data. In Sebastian Thrun, Lawrence Saul, and Bernhard Sch¨ lkopf, editors, Advances in Neural o Information Processing Systems 16. MIT Press, Cambridge, MA, 2004.
[17] Demetrios Vakratsas, Fred M. Feinberg, Frank M. Bass, and Gurumurthy Kalyanaram. The Shape of Advertising Response Functions Revisited: A Model of Dynamic Probabilistic Thresholds. Marketing Science, 23(1):109–119, 2004. 9