Scalable Label Propagation for Multi-relational Learning on the Tensor Product of Graphs
This work addresses scalability and accuracy challenges in multi-relational learning for applications like publication analysis and medical imaging, though it is incremental as it builds on existing label propagation methods.
The paper tackles multi-relational learning on knowledge graphs by generalizing label propagation to normalized tensor product graphs, proposing LowrankTLP for scalable inference in hyperlink prediction and graph alignment tasks, achieving results like processing 100 graphs of size 1000 in under half an hour with improved accuracy.
Multi-relational learning on knowledge graphs infers high-order relations among the entities across the graphs. This learning task can be solved by label propagation on the tensor product of the knowledge graphs to learn the high-order relations as a tensor. In this paper, we generalize a widely used label propagation model to the normalized tensor product graph, and propose an optimization formulation and a scalable Low-rank Tensor-based Label Propagation algorithm (LowrankTLP) to infer multi-relations for two learning tasks, hyperlink prediction and multiple graph alignment. The optimization formulation minimizes the upper bound of the noisy tensor estimation error for multiple graph alignment, by learning with a subset of the eigen-pairs in the spectrum of the normalized tensor product graph. We also provide a data-dependent transductive Rademacher bound for binary hyperlink prediction. We accelerate LowrankTLP with parallel tensor computation which enables label propagation on a tensor product of 100 graphs each of size 1000 in less than half hour in the simulation. LowrankTLP was also applied to predicting the author-paper-venue hyperlinks in publication records, alignment of segmented regions across up to 26 CT-scan images and alignment of protein-protein interaction networks across multiple species. The experiments demonstrate that LowrankTLP indeed well approximates the original label propagation with better scalability and accuracy.