Solving sparse non-negative tensor equations: algorithms and applications

Abstract

We study iterative methods for solving a set of sparse non-negative tensor equations (multivariate polynomial systems) arising from data mining applications such as information retrieval by query search and community discovery in multi-dimensional networks. By making use of sparse and non-negative tensor structure, we develop Jacobi and Gauss-Seidel methods for solving tensor equations. The multiplication of tensors with vectors are required at each iteration of these iterative methods, the cost per iteration depends on the number of non-zeros in the sparse tensors. We show linear convergence of the Jacobi and Gauss-Seidel methods under suitable conditions, and therefore, the set of sparse non-negative tensor equations can be solved very efficiently. Experimental results on information retrieval by query search and community discovery in multi-dimensional networks are presented to illustrate the application of tensor equations and the effectiveness of the proposed methods.

Keywords

Nonnegative tensor / multi-dimensional network / information retrieval / community / iterative method / multivariate polynomial equation

References

[1] Buchberger B. Gröbner basis: an algorithmic method in polynomial ideal theory. In: Bose N K, ed. Multidimensional System Theory. Dordrecht, Boston, Lancaster: D Reidel Publishing Company, 1985, 184−232

[2] Cai D, He X, Han J. Tensor space model for document analysis. In: International Conference on Research and Development in Information Retrieval. 2006, 625−626

[3] Chang K, Pearson K, Zhang T. Perron-Frobenius theorem for nonnegative tensors. Commun Math Sci, 2008, 6: 507−520

[4] Chang K, Zhang T. On the uniqueness and non-uniqueness of the Z-eigenvector for transition probability tensors. J Math Anal Appl, 2013, 408: 525−540

[5] Clauset A. Finding local community structure in networks. Phys Rev E, 2005, 72: 026132

[6] Comon P, Luciani X, De Almeida A. Tensor decompositions, alternating least squares and other tales. J Chemometrics, 2009, 23(7−8): 393−405

[7] Drexler F. Eine Methode zur Berechnung sämtlicher Lösungen von Polynomgleichungssystemen. Numer Math, 1977, 29(1): 45−58

[8] Garcia C, Zangwill W. Finding all solutions to polynomial systems and other systems of equations. Math Program, 1979, 16(1): 159−176

[9] Haveliwala T. Topic-sensitive PageRank. In: Proceedings of the 11th International World Wide Web Conference, 2002

[10] Hu S, Qi L. Convergence of a second order Markov chain. http://arxiv.org/abs/1307.6919

[11] Istratescu V. Fixed Point Theory: An Introduction. Dordrecht: D Reidel Publishing Company, 1981

[12] Kellogg R. Uniqueness in the Schauder fixed point theorem. Proc Amer Math Soc, 1976, 60(1): 207−210

[13] Kleinberg J. Authoritative sources in a hyperlinked environment. J ACM, 1999, 46(5): 604−632

[14] Kolda T, Bader B. The TOPHITS model for higher-order web link analysis. In: Workshop on Link Analysis, Counterterrorism and Security. 2006, 26−29

[15] Kolda T, Bader B. Tensor decompositions and applications. SIAM Rev, 2009, 51: 455−500

[16] Kolda T, Bader B, Kenny J. Higher-order web link analysis using multilinear algebra. In: Proceedings of the 5th International Conference on Data Mining. 2005

[17] Lathauwer L, Moor B, Vandewalle J. A multilinear singular value decomposition. SIAM J Matrix Anal Appl, 2000, 21: 1253−1278

[18] Li Q, Shi X, Schonfeld D. A general framework for robust HOSVD-based indexing and retrieval with high-order tensor data. ICASSP, 2011, 873−876

[19] Li T. Numerical solution of multivariate polynomial systems by homotopy continuation methods. Acta Numer, 1997, 6: 399−436

[20] Li T, Ding C, Wang F. Guest editorial: special issue on data mining with matrices, graphs and tensors. Data Min Knowl Discov, 2011, 22(3): 337−339

[21] Li W, Ng M. On the limiting probability distribution of a transition probability tensor. Linear Multilinear Algebra, 2013, 20: 985−1000

[22] Li X, Ng M, Ye Y. Har: hub, authority and relevance scores in multi-relational data for query search. In: Proceedings of the 12th SIAM International Conference on Data Mining. 2012, 141−152

[23] Li X, Ng M, Ye Y. MultiComm: finding community structures in multi-dimensional networks. IEEE Trans Knowl Data Engineering, 2014, 26(4): 929−941

[24] Lin Y, Sun J, Castro P, Konuru R, Sundaram H, Kelliher A. MetaFac: community discovery via relational hypergraph factorization. In: Proceedings of the 15th ACM SIGKDD on Knowledge Discovery and Data Mining. 2009, 527−536

[25] Liu N, Zhang B, Yan J, Chen Z, Liu W, Bai F, Chien L. Text representation: from vector to tensor. In: Proceedings of the Fifth IEEE International Conference on Data Mining. 2005

[26] Maruhashi K, Guo F, Faloutsos C. MultiAspectForensics: pattern mining on largescale heterogeneous networks with tensor analysis. In: International Conference on Advances in Social Networks Analysis and Mining. 2011, 203−210

[27] Newman M. The structure and function of complex networks. SIAM Rev, 2003, 45: 167−256

[28] Ng M, Li X, Ye Y. MultiRank: co-ranking scheme for objects and relations in multi-dimensional data. In: Proceedings of the 17th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2011, 1217−1225

[29] Robertson S E, Walker S. Some simple effective approximations to the 2-Poisson model for probabilistic weighted retrieval. In: Proceedings of the 17th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. 1994, 232−241

[30] Savas B, Eldén L. Krylov subspace methods for tensor computations. LITH-MAT-R-2009-02-SE, Preprint

[31] Sun J, Papadimitriou S, Lin C, Cao N, Liu S, Qian W. Multivis: Content-based social network exploration through multi-way visual analysis. In: Proceedings of the 9^th SIAM International Conference on Data Mining. 2009, 1063−1074

[32] Sun J, Tao D, Faloutsos C. Beyond streams and graphs: dynamic tensor analysis. In: Proceedings of the 12th ACM SIGKDD on Knowledge Discovery and Data Mining. 2006, 374−383

[33] Sun J, Tao D, Papadimitriou S, Yu P, Faloutsos C. Incremental tensor analysis: theory and applications. ACM Trans Knowl Discov from Data, 2008, 2(3): 1−37

[34] Sun J, Zeng H, Liu H, Lu Y, Chen Z. CubeSVD: A novel approach to personalized web search. In: International Conference on WWW. 2005, 382−390

[35] Tao D, Li X, Wu X, Maybank S. General tensor discriminant analysis and Gabor features for gait recognition. IEEE Trans Pattern Anal Machine Intelligence, 2007, 29: 1700−1715

[36] Tong H, Faloutsos C, Pan J. Random walk with restart: fast solutions and applications. Knowledge and Information Systems, 2008, 14(3): 327−346

[37] Verschelde J, Verlinden P, Cools R. Homotopies exploiting Newton polytopes for solving sparse polynomial systems. SIAM J Numer Anal, 1994, 31(3): 915−930

[38] Voorhees E, Harman D. TREC: Experiment and Evaluation in Information Retrieval. Cambridge: MIT Press, 2005

[39] Wermser H, Rettinger A, Tresp V. Modeling and learning context-aware recommendation scenarios using tensor decomposition. In: International Conference on Advances in Social Networks Analysis and Mining. 2011, 137−144

RIGHTS & PERMISSIONS

2015 Higher Education Press and Springer-Verlag Berlin Heidelberg