Scalable Label Propagation for Multi-relational Learning on the Tensor Product of Graphs

Zhuliu Li, Raphael Petegrosso, Shaden Smith, David Sterling, George Karypis, Rui Kuang

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
JournalIEEE Transactions on Knowledge and Data Engineering
StateAccepted/In press - 2021

Bibliographical note

Publisher Copyright:


  • Approximation algorithms
  • Hypertext systems
  • Optimization
  • Prediction algorithms
  • Scalability
  • Task analysis
  • Tensors
  • hyperlink prediction
  • label propagation
  • multi-relational learning
  • multiple graph alignment
  • tensor decomposition and completion
  • tensor product graph

Fingerprint Dive into the research topics of 'Scalable Label Propagation for Multi-relational Learning on the Tensor Product of Graphs'. Together they form a unique fingerprint.

Cite this