Multiaspect data are ubiquitous in modern Big Data applications. For instance, different aspects of a social network are the different types of communication between people, the time stamp of each interaction, and the location associated to each individual. How can we jointly model all those aspects and leverage the additional information that they introduce to our analysis? Tensors, which are multidimensional extensions of matrices, are a principled and mathematically sound way of modeling such multiaspect data. In this article, our goal is to popularize tensors and tensor decompositions to Big Data practitioners by demonstrating their effectiveness, outlining challenges that pertain to their application in Big Data scenarios, and presenting our recent work that tackles those challenges. We view this work as a step toward a fully automated, unsupervised tensor mining tool that can be easily and broadly adopted by practitioners in academia and industry.
Get full access to this article
View all access options for this article.
References
1.
KoldaTG, BaderBW. Tensor decompositions and applications. SIAM Rev. 2009; 51:455–500.
2.
AcarE, YenerB. Unsupervised multiway data analysis: A literature survey. IEEE Trans Knowl Data Eng. 2009; 21:6–20.
3.
HarshmanRA. Foundations of the PARAFAC procedure: Models and conditions for an “explanatory” multimodal factor analysis. Los Angeles, CA: University of California at Los Angeles, 1970.
4.
PapalexakisEE, SidiropoulosND, BroR. From k-means to higher-way co-clustering: Multilinear decomposition with sparse latent factors. IEEE Trans Signal Process. 2013; 61:493–506.
KoldaTG, BaderBW, KennyJP. Higher-order web link analysis using multilinear algebra. In ICDM, New Orleans, LA, IEEE, 2005. 8 pp.
9.
KleinbergJM. Authoritative sources in a hyperlinked environment. J ACM. 1999; 46:604–632.
10.
AgrawalR, GolshanB, PapalexakisE. A study of distinctiveness in web results of two search engines. In 24th International Conference on World Wide Web, Web Science Track, Florence, Italy, ACM, May 2015.
11.
AgrawalR, GolshanB, PapalexakisE. Whither social networks for web search? In 21st ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Sydney, Australia, August 2015.
12.
PapalexakisEE, AkogluL, IencoD. Do more views of a graph help? Community detection and clustering in multi-graphs. In FUSION, Istanbul, Turkey, IEEE, 2013. pp. 899–905.
13.
WangY, ZhengY, XueY. Travel time estimation of a path using sparse trajectories. In KDD, New York, NY, USA: ACM, 2014. pp. 25–34.
14.
AcarE, Aykut-BingolC, BingolH, et al.Multiway analysis of epilepsy tensors. Bioinformatics. 2007; 23:i10–i18.
15.
DavidsonI, GilpinS, CarmichaelO, WalkerP. Network discovery via constrained tensor analysis of fmri data. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Chicago, IL, ACM, 2013. pp. 194–202.
16.
PapalexakisEE, MitchellTM, SidiropoulosND, et al.Turbo-smt: Accelerating coupled sparse matrix-tensor factorizations by 200x. In SIAM SDM, 2014. pp. 118–126.
17.
MaruhashiK, GuoF, FaloutsosC. Multiaspectforensics: Pattern mining on large-scale heterogeneous networks with tensor analysis. In Proceedings of the Third International Conference on Advances in Social Network Analysis and Mining. IEEE, 2011.
18.
MaoCH, WuCJ, PapalexakisEE, et al.Malspot: Multi2 malicious network behavior patterns analysis. In Advances in Knowledge Discovery and Data Mining, Tainan, Taiwan, Springer, 2014. pp. 1–14.
19.
HoJC, et al.Marble: High-throughput phenotyping from electronic health records via sparse nonnegative tensor factorization. In KDD, New York, NY, ACM, 2014. pp. 115–124.
20.
BaderBW, KoldaTG. Efficient MATLAB computations with sparse and factored tensors. SIAM J Sci Comput. 2007; 30:205–231.
21.
KangU, et al.Gigatensor: Scaling tensor analysis up by 100 times-algorithms and discoveries. In KDD, Beijing, China, ACM, 2012. pp. 316–324.
22.
PapalexakisEE, FaloutsosC, SidiropoulosND. Parcube: Sparse parallelizable tensor decompositions. In Machine Learning and Knowledge Discovery in Databases, Bristol, UK, Springer, 2012. pp. 521–536.
23.
ErdosD, MiettinenP. Walk'n'merge: A scalable algorithm for Boolean tensor factorization. In ICDM, Dallas, TX, IEEE, 2013. pp. 1037–1042.
24.
SidiropoulosN, PapalexakisE, FaloutsosC. Parallel randomly compressed cubes: A scalable distributed architecture for big tensor decomposition. IEEE Signal Process Mag. 2014; 31:57–70.
25.
AggourKS, YenerB. A parallel PARAFAC implementation and scalability testing for large-scale dense tensor decomposition. Technical report, Rensselaer Polytechnic Institute. 2016.
26.
BroR, KiersHAL. A new efficient method for determining the number of components in PARAFAC models. J Chemom. 2003; 17:274–286.
27.
PapalexakisEE, FaloutsosC. Fast efficient and scalable core consistency diagnostic for the PARAFAC decomposition for big sparse tensors. In ICASSP. IEEE, 2015.
28.
PapalexakisEE. Automatic unsupervised tensor mining with quality assessment. In SIAM SDM, 2016.
29.
ChiEC, KoldaTG. On tensors, sparsity, and nonnegative factorizations. SIAM J Matrix Anal Appl. 2012; 33:1272–1299.
30.
ZhaoQ, ZhangL, CichockiA. Bayesian CP factorization of incomplete tensors with automatic rank determination. IEEE Trans Pattern Anal Mach Intell. 2015; 37:1751–1763.
KruskalJB. Three-way arrays: Rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics. Linear Algebra Appl. 1977; 18:95–138.
35.
StegemanA, ten BergeJMF, De LathauwerL. Sufficient conditions for uniqueness in CANDECOMP/PARAFAC and INDSCAL with random component matrices. Psychometrika. 2006; 71:219–229.
36.
ChiantiniL, OttavianiG. On generic identifiability of 3-tensors of small rank. SIAM J Matrix Anal Appl. 2012; 33:1018–1037.
AnderssonCA, BroR. The n-way toolbox for matlab. Chemom Intell Lab Syst. 2000; 52:1–4.
39.
HeiserWJ. Convergent computation by iterative majorization: Theory and applications in multidimensional data analysis. In: Recent Advances in Descriptive Multivariate Analysis. Clarendon Press, 1995. pp. 157–189.
40.
FévotteC, IdierJ. Algorithms for nonnegative matrix factorization with the β-divergence. Neural Comput. 2011; 23:2421–2456.
