Dropout Graph Product for Improved Relationship Discovery Across Multiple Heterogeneous Graphs

Abstract

Relationship discovery across multiple heterogeneous graphs has recently attracted considerable interest. A major challenge is how to fuse and utilize the structure and properties of multiple heterogeneous graphs complementarily to improve relationship discovery between graph pairs where there are only a few observed relationships. In this paper, we seek to solve the problem through label propagation on dropout graph product. We first map multiple heterogeneous graphs onto a single homogeneous graph through graph product. The internal structure and properties of each individual graphs, as well as the observed inter-graph relationships across multiple graphs are fused losslessly via assigning edge weights and encoding node vectors of the graph product. As a result, the complex problem of relationship discovery across multiple heterogeneous graphs is transformed into a simple problem of node classification on homogeneous graph product. However, the size of graph product increases quickly with the size and the number of factor graphs, which leads to low accuracy and high computational cost. Dropout is therefore introduced to address this problem, which is applied to label propagation on graph product. Finally, we combine the results of a set of label propagations on different dropout graph products using a product of experts model. The proposed approach is characterized by flexibility in defining graph product, good generalization ability, high accuracy, and efficient computation. The experiments on real-world datasets show that the proposed approach significantly improves relationship discovery across multiple heterogeneous graphs, obtaining better results on the benchmark datasets than the baseline approaches.

Keywords

• Multiple graph fusion
• multi-entity relationship discovery
• dropout
• graph product
• label propagation