Inter-domain Multi-relational Link Prediction

Luu Huu Phuc, Koh Takeuchi, Seiji Okajima, Arseny Tolmachev, Tomoyoshi Takebayashi, Koji Maruhashi, Hisashi KashimaECML/PKDD 2021 · DOI · OpenReview

Abstract

Multi-relational graphs are ubiquitous data structures that allow for the flexible representation of complex interactions between entities. While link prediction is a well-established task for completing knowledge within a single graph (intra-domain), real-world scenarios often involve multiple related graphs where predicting connections between entities across different domains (inter-domain) is necessary. This paper addresses the challenge of inter-domain link prediction, where existing methods fail due to disjoint latent embedding spaces. We propose a novel approach that softly aligns entity distributions across domains using Optimal Transport (Wasserstein distance) and Maximum Mean Discrepancy regularizers. Our experiments on diverse real-world datasets demonstrate that the Optimal Transport regularizer significantly improves performance over baseline methods by bridging the gap between separate relational domains.

Introduction

Knowledge graphs and multi-relational data structures serve as the backbone for many modern AI applications, from recommendation engines to semantic search. Traditionally, the task of link prediction has focused on "intra-domain" completion—predicting missing relationships between entities within a single, isolated database. However, as data becomes increasingly fragmented across different platforms and sources (e.g., Freebase, DBpedia, or distinct e-commerce ecosystems), the need to integrate these "islands" of data becomes paramount.

Inter-domain link prediction involves predicting a relationship between an entity in Graph A and an entity in Graph B. This is inherently difficult because standard embedding techniques learn a "coordinate system" for each graph in a vacuum. Without a shared mathematical framework, the latent representation of an entity in one graph has no meaningful relationship to an entity in another. To solve this, we must find a way to align these separate latent spaces without requiring exhaustive manual mapping of every entity.

Methodology

Our framework builds upon traditional tensor factorization and introduces distribution alignment regularizers to bridge the domain gap.

Base Model: RESCAL

We utilize RESCAL, a standard tensor factorization method, as our base model. RESCAL learns embeddings for entities ($A$) and predicates ($R$) by decomposing the graph tensor. While effective for intra-domain tasks, RESCAL alone cannot generalize across different graphs with disjoint entity sets.

Soft Alignment Regularizers

The core innovation of this work is the addition of a penalty term to the loss function that minimizes the dissimilarity between the entity distributions of two different graphs. We explored two primary statistical divergences:

  1. Wasserstein Distance (WD): Derived from Optimal Transport theory, WD measures the minimum "cost" required to transform one distribution into another. We employ the Sinkhorn algorithm to ensure this remains computationally efficient for large-scale graphs.
  2. Maximum Mean Discrepancy (MMD): A kernel-based method that compares distributions by mapping them into a high-dimensional Reproducing Kernel Hilbert Space (RKHS) and measuring the distance between their mean embeddings.

Unlike "hard" entity alignment methods that require a-priori knowledge of identical nodes, this "soft" alignment approach assumes only that the underlying distributions of entities are similar, nudging the two embedding spaces to overlap naturally.

Experimental Evaluation

To evaluate the effectiveness of our approach, we created inter-domain benchmarks using four popular datasets: FB15k-237 (general knowledge), WN18RR (lexical relationships), DBbook2014 (e-commerce), and ML1M (movie ratings). We split these datasets into two sub-graphs with varying levels of entity overlap (0%, 1.5%, 3%, and 5%) to simulate different degrees of cross-domain connectivity.

Key Insights

  • The Superiority of Optimal Transport: The Wasserstein Distance (WD) regularizer consistently outperformed MMD across all benchmarks. While MMD occasionally introduced noise or struggled with local optima, WD effectively forced the embedding distributions to occupy the same region of the latent space while preserving their structural shapes.
  • The Role of Anchor Entities: Even a minimal overlap of 1.5% shared entities acted as a powerful "anchor." These shared points guided the Optimal Transport regularizer, allowing it to align the remaining unaligned entities with much higher precision.
  • Preservation of Intra-domain Performance: A critical finding was that the alignment process did not degrade the model's performance on internal graph tasks. In many cases, the WD alignment slightly improved intra-domain accuracy by providing a more robust structural regularization.

Results and Discussion

On the FB15k-237 dataset with 3% overlap, the WD-regularized model improved the Hit@10 score from 0.302 (baseline) to 0.328. Similar statistically significant improvements in ROC-AUC were observed across DBbook2014 and ML1M. Visualization of the embeddings via t-SNE confirmed that while standard RESCAL produced two distinct, isolated clusters, the WD-regularized version resulted in nearly identical, overlapping distributions, enabling seamless cross-domain reasoning.

Limitations and Future Work

The current approach assumes that both graphs share a similar underlying entity distribution. If the domains are radically different (e.g., a graph of biological proteins vs. a graph of financial transactions), the alignment may produce nonsensical results. Future research will explore Unbalanced Optimal Transport, which allows for "mass creation or destruction" during alignment, potentially enabling the integration of graphs with highly divergent sizes or non-identical distributions.

Conclusion

By framing inter-domain link prediction as a distribution alignment problem, we provide a scalable way to integrate disparate knowledge graphs. The use of Optimal Transport as a regularizer allows for the discovery of relationships across domains without the need for extensive manual labeling, paving the way for more unified and comprehensive knowledge representation systems.

Summary updated

Abstract

Multi-relational graph is a ubiquitous and important data structure, allowing flexible representation of multiple types of interactions and relations between entities. Similar to other graph-structured data, link prediction is one of the most important tasks on multi-relational graphs and is often used for knowledge completion. When related graphs coexist, it is of great benefit to build a larger graph via integrating the smaller ones. The integration requires predicting hidden relational connections between entities belonged to different graphs (inter-domain link prediction). However, this poses a real challenge to existing methods that are exclusively designed for link prediction between entities of the same graph only (intra-domain link prediction). In this study, we propose a new approach to tackle the inter-domain link prediction problem by softly aligning the entity distributions between different domains with optimal transport and maximum mean discrepancy regularizers. Experiments on real-world datasets show that optimal transport regularizer is beneficial and considerably improves the performance of baseline methods.
BibTeX
@inproceedings{phuc2021inter,
  author = {Luu Huu Phuc and Koh Takeuchi and Seiji Okajima and Arseny Tolmachev and Tomoyoshi Takebayashi and Koji Maruhashi and Hisashi Kashima},
  title = {{Inter-domain Multi-relational Link Prediction}},
  booktitle = {ECML/PKDD},
  year = {2021},
  doi = {10.1007/978-3-030-86520-7\_18},
}
Figure