Scalable Label Propagation for Multi-relational Learning on Tensor Product Graph.

Label propagation on the tensor product of multiple graphs can infermulti-relations among the entities across the graphs by learning labels in atensor. However, the tensor formulation is only empirically scalable up tothree graphs due to the exponential complexity of computing tensors. In thispaper, we propose an optimization formulation and a scalable LowrankTensor-based Label Propagation algorithm (LowrankTLP). The optimizationformulation minimizes the rank-k approximation error for computing theclosed-form solution of label propagation on a tensor product graph withefficient tensor computations used in LowrankTLP. LowrankTLP takes either asparse tensor of known multi-relations or pairwise relations between each pairof graphs as the input to infer unknown multi-relations by semi-supervisedlearning on the tensor product graph. We also accelerate LowrankTLP withparallel tensor computation which enabled label propagation on a tensor productof 100 graphs of size 1000 within 150 seconds in simulation. LowrankTLP wasalso successfully applied to multi-relational learning for predictingauthor-paper-venue in publication records, alignment of several protein-proteininteraction networks across species and alignment of segmented regions acrossup to 7 CT scan images. The experiments prove that LowrankTLP indeed wellapproximates the original label propagation with high scalability. Source code:https://github.com/kuanglab/LowrankTLP