UC Riverside

During the past few decades machine learning researchers and practitioners have managed to leverage the power of graph theory with great success in virtually every aspect of a machine learning workflow. However, very recently it has started to become increasingly clear that classical graph theory cannot adequately model the complex structure of networks that modern machine learning problems have to deal with. Multi-relational graphs are an example of such networks that describe the pairwise relationships of their nodes while also allowing different types of such relationships to exist as well. Among the various frameworks that have attempted to provide increased modeling capabilities for such networks, tensor decompositions are arguably among the most natural modeling choices and have in fact enjoyed particular success in this area. For this reason, the main focus of this dissertation will be the design and analysis of novel tensor-based methods aiming to offer a more effective means for modeling multi-relational networks. In the first work, we present a novel technique for estimating the number of components of the PARAFAC tensor decomposition that is most appropriate for best describing the low-rank structure in tensor data. This is particularly important in graph clustering as the number of components of PARAFAC can be closely related to the number of node clusters. In the second work, we study the successful RESCAL tensor decomposition which has been specifically designed for multi-relational networks and we propose an improved reformulation. Specifically, we introduce an outlier resistant reformulation based on the L1 norm along with a numerically robust and computationally efficient solver. In our last work, we propose an extension of the popular spectral clustering framework to multi-relational networks for which different groups of relationships may exhibit different node grouping structures. Finally, we derive a novel framework that unifies our proposed method with a series of other existing clustering methods. This framework reveals interesting connections between these methods, which in turn can help provide more insightful interpretations of their behavior.