LINK PREDICTION USING TENSOR DECOMPOSITION

In recent years, tensor decomposition has gained increasing interest in the field of link prediction, which aims to estimate the likelihood of new connections forming between nodes in a network. This study highlights the potential of the Canonical Polyadic tensor decomposition in enhancing link prediction in complex networks. It suggests effective tensor decomposition algorithms that not only take into account the structural characteristics of the network but also its temporal evolution. During the process of tensor decomposition, the initial tensor is decomposed into two-way tensors, also known as factor matrices, representing different modes of the data. These factor matrices capture the underlying patterns or relationships within the network, providing insights into the structure and dynamics of the network. For evaluation, we examine a dataset derived from the WSDM. After preprocessing, the data is represented as a multi-way tensor, with each mode representing different aspects such as users, items, and time. Our primary objective is to make precise predictions about the links between users and items within specific time periods. The experimental results demonstrate that our approach significantly improves prediction accuracy for evolving networks, as measured by the AUC.

1. Hitchcock Frank L. (1927) The expression of a tensor or a polyadic as a sum of products, Journal of Mathematics and Physics, 6.1-4, pp. 164–189.

2. Sidiropoulos Nicholas D. et al. (2017) Tensor decomposition for signal processing and machine learning, IEEE Transactions on Signal Processing, 65.13, pp. 3551–3582.

3. Kolda Tamara G. and Brett W. Bader (2009) Tensor decompositions and applications, SIAM review, 51.3, pp. 455–500.

4. Tucker, Ledyard R. (1966) Some mathematical notes on three-mode factor analysis, Psychometrika, 31.3: 279–311.

5. Carroll, J. Douglas and Jih-Jie Chang (1970) Analysis of individual differences in multidimensional scaling via an N-way generalization of “Eckart-Young” decomposition, Psychometrika 35.3, pp. 283–319.

6. Harshman, Richard A. (1970) Foundations of the PARAFAC procedure: Models and conditions for an" explanatory" multimodal factor analysis, pp. 1–84.

7. Bader, Brett W., Richard A. Harshman and Tamara G. Kolda. Temporal analysis of semantic graphs using ASALSAN, Seventh IEEE international conference on data mining (ICDM 2007).

8. Nickel, Maximilian, Lorenzo Rosasco and Tomaso Poggio. (2016) Holographic embeddings of knowledge graphs, Proceedings of the AAAI Conference on Artificial Intelligence, vol. 30, no. 1.

9. Ma, Yunpu, Volker Tresp and Erik A. Daxberger. (2019) Embedding models for episodic knowledge graphs, Journal of Web Semantics 59: 100490.

10. Acar E., Dunlavy D.M., Kolda T.G. (2009) Link prediction on evolving data using matrix and tensor factorizations, IEEE International conference on data mining workshops, pp. 262–269.

11. Ermiş, Beyza, Evrim Acar and A. Taylan Cemgil. (2015) Link prediction in heterogeneous data via generalized coupled tensor factorization, Data Mining and Knowledge Discovery, 29, pp. 203–236.

12. Xiong, Liang et al. (2010) Temporal collaborative filtering with Bayesian probabilistic tensor factorization, Proceedings of the 2010 SIAM international conference on data mining, Society for Industrial and Applied Mathematics.

13. Gao S., Denoyer L., Gallinari P. (2010) Tensor decomposition model for link prediction in multi-relational networks, 2nd IEEE International Conference on Network Infrastructure and Digital Content, IEEE, pp. 298–302.

14. Chi, Eric C. and Tamara G. Kolda. (2012) On tensors, sparsity, and nonnegative factorizations, SIAM Journal on Matrix Analysis and Applications, 33.4, pp. 1272–1299.

15. de Araujo, Miguel Ramos, Pedro Manuel Pinto Ribeiro and Christos Faloutsos. Tensorcast: Forecasting with context using coupled tensors (best paper award), 2017 IEEE International Conference on Data Mining (ICDM).