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:
- 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.
- 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