TY - JOUR
T1 - Scalable Label Propagation for Multi-Relational Learning on the Tensor Product of Graphs
AU - Li, Zhuliu
AU - Petegrosso, Raphael
AU - Smith, Shaden
AU - Sterling, David
AU - Karypis, George
AU - Kuang, Rui
N1 - Publisher Copyright:
IEEE
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
KW - Multi-relational learning
KW - hyperlink prediction
KW - label propagation
KW - multiple graph alignment
KW - tensor decomposition and completion
KW - tensor product graph
UR - http://www.scopus.com/inward/record.url?scp=85102247556&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85102247556&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2021.3063985
DO - 10.1109/TKDE.2021.3063985
M3 - Article
AN - SCOPUS:85102247556
SN - 1041-4347
VL - 34
SP - 5964
EP - 5978
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 12
ER -