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

2 Scopus citations

Abstract

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 the 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 estimating 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)
Pages (from-to)5964-5978
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Volume34
Issue number12
DOIs
StateAccepted/In press - 2021

Bibliographical note

Publisher Copyright:
IEEE

Keywords

  • Multi-relational learning
  • hyperlink prediction
  • label propagation
  • 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