Non-Negative Tensor Based Computation for Analyzing Large-Scale and Multi-Relational Data

Evaluation of object importance or popularity is an important research problem in information retrieval that can assist in many data mining tasks. In the literature, there are several link analysis methods to evaluating object importance and information search such as PageRank, HITS and SALSA. However, in these link analysis methods, a single relation type is focused and studied. In this proposal, we are interested in data with multiple relation types represented by non-negative tensors. There are many data mining and information retrieval applications in multi-relational data which objects have interactions with the others based on different relations. For example, researchers cite the other researchers in different conferences based on different concepts/topics; papers cite the other papers based on text analysis such as title, abstract, keyword and authorship; and webpages link to the other webpages through different semantic meanings. Such additional links structure can provide a better way of incorporating multiple relations into objects for calculation of objects importance and information search. On the other hand, the number of objects in these applications can be very large, and easily be over a million. This research proposal is centered on the development of effective and efficient non-negative tensor based computational methods for analyzing large-scale and multi-relational data.

The main contribution of this proposal is to propose a framework to study and analyze non-negative rectangular tensors for the hub and authority scores of objects, and the relevance scores of relations in multi-relational data. The basic idea of our framework is to consider a random walk in non-negative rectangular tensors, and study in such random walk, limiting probabilities of visiting objects for hub and authority scores and using relations for relevance scores. By making use of these limiting probabilities, we can rank relations and objects as a hub and an authority, and perform query search in data mining applications. On the theoretical side, we will study and analyze existence and uniqueness of limiting probabilities in the tensor model. On the algorithmic side, we will develop efficient iterative algorithms to solve a set of tensor (multivariate polynomial) equations to obtain hub and authority scores and relevance scores, and also analyze the convergence of the proposed algorithm. Applications of our methods to community discovery will be considered, studied and analyzed. We extend our tensor model to multi-dimensional non-negative tenors for identification of interesting and explainable local communities in multi-dimensional network data.