Conflict-Aware Pseudo Labeling via Optimal Transport for Entity Alignment

Qijie Ding, Daokun Zhang, Jie Yin

TL;DR

CPL-OT is a new framework that significantly improves entity alignment between knowledge graphs by framing the matching process as an Optimal Transport problem. By enforcing one-to-one mappings during iterative pseudo-labeling, the model eliminates alignment conflicts and achieves state-of-the-art results even when training labels are entirely unavailable.

What Problem Does This Paper Address?

Knowledge Graphs (KGs) like DBpedia or YAGO are powerful but often incomplete. Entity Alignment (EA) is the process of identifying when two different entries in separate KGs actually represent the same real-world object (e.g., "Apple Inc." in one graph and "苹果公司" in another).

Most modern approaches use Graph Convolutional Networks (GCNs) to embed entities into a vector space where similar entities are close together. However, these methods face two major hurdles:

  1. Alignment Conflicts: GCNs tend to "smooth" features, making neighboring entities look very similar. This often leads to "many-to-one" errors, where multiple entities from one graph are incorrectly matched to a single entity in another.
  2. Label Scarcity: Manually aligning entities is expensive. While "bootstrapping" (using high-confidence predictions as new training labels) helps, it often amplifies the conflict problem by feeding incorrect, conflicting matches back into the training loop.

Methods

The authors introduce CPL-OT (Conflict-aware Pseudo Labeling via Optimal Transport), which consists of two main pillars:

1. Global-Local Aggregation

To create better embeddings, the model looks at two levels of information:

  • Global-Level: It aggregates relation information by averaging the features of all head and tail entities associated with a specific relation.
  • Local-Level: It uses a two-layer GCN with a "highway gate" strategy. This gate acts as a filter, allowing the model to combine deep structural information without suffering from the over-smoothing that typically plagues GCNs.

2. Optimal Transport (OT) for Pseudo-Labeling

This is the paper's core innovation. Instead of simply picking the nearest neighbor for every entity (which causes conflicts), the authors treat alignment as a resource allocation problem.

  • They define a "transport cost" based on a rectified distance (combining embedding distance with neighborhood similarity).
  • They solve for a transport plan that minimizes the total cost across all entities while strictly enforcing a one-to-one mapping.
  • Because exact OT is computationally heavy, they implement a Greedy Algorithm (Algorithm 1 in the paper) that provides a fast, high-quality approximation in linear time.

Datasets

The model was evaluated on two major benchmark suites:

  • DBP15K: Three cross-lingual datasets (Chinese-English, Japanese-English, French-English) derived from DBpedia. These are known for having significant linguistic barriers.
  • SRPRS: Two sparse datasets (English-French, English-German) designed to mimic the challenging, low-density nature of real-world KGs.
TABLE I: Statistics of datasets

Key Insights and Ideas

  • OT as a Structural Constraint: The "aha moment" here is that entity alignment isn't just about individual similarity; it's a global matching problem. By using OT, the model uses the global structure of the graph to resolve local ambiguities.
  • Robustness to Zero Seeds: Perhaps the most surprising finding is how well the model performs with zero prior alignment seeds. By relying on the inherent structure and initial semantic features (like translated entity names), CPL-OT can self-start and reach performance levels that rival supervised models.
  • Rectification Matters: The authors found that simple embedding distance isn't enough. By "rectifying" the distance with relational neighborhood matching, they provide the OT solver with much more reliable cost data.

Key Results

CPL-OT outperformed 12 state-of-the-art baselines across all tested datasets.

  • Superior Accuracy: On the challenging DBP15K (Chinese-English) task, CPL-OT achieved a Hit@1 of 92.7%, outperforming the next best model (RNM) by nearly 9%.
  • Stability: When training labels were reduced from 30% to 0%, the performance drop was minimal (only 1.6% on DBP15K_ZH_EN), demonstrating incredible robustness.
  • Ablation Success: As shown in Table III, removing the OT component (w.o. Conflict-aware OT) consistently degraded performance, proving that managing alignment conflicts is vital for high-precision alignment.
TABLE II: Performance comparison on DBP15K and SRPRS
Table III: Ablation study of CPL-OT

Limitations and Future Work

  • One-to-One Assumption: The model assumes a strict one-to-one mapping between KGs. While common in research, real-world KGs might occasionally have one-to-many relationships depending on their schema granularity.
  • Greedy Approximation: While the greedy algorithm is efficient, it is still an approximation. Exploring more advanced, scalable OT solvers could potentially squeeze out even more performance.
  • Relation Complexity: The current global relation aggregation is relatively simple (averaging). Future work could incorporate more sophisticated relation-aware attention mechanisms.

Summary updated

Abstract

Entity alignment aims to discover unique equivalent entity pairs with the same meaning across different knowledge graphs (KGs). Existing models have focused on projecting KGs into a latent embedding space so that inherent semantics between entities can be captured for entity alignment. However, the adverse impacts of alignment conflicts have been largely overlooked during training, thereby limiting the entity alignment performance. To address this issue, we propose a novel Conflict-aware Pseudo Labeling via Optimal Transport model (CPL-OT) for entity alignment. The key idea is to iteratively pseudo-label alignment pairs empowered with conflict-aware optimal transport (OT) modeling to boost the precision of entity alignment. CPL-OT is composed of two key components -- entity embedding learning with global-local aggregation and iterative conflict-aware pseudo labeling -- that mutually reinforce each other. To mitigate alignment conflicts during pseudo labeling, we propose to use optimal transport as an effective means to warrant one-to-one entity alignment between two KGs with the minimal overall transport cost. Extensive experiments on benchmark datasets validate the superiority of CPL-OT over state-of-the-art baselines under both settings with and without prior alignment seeds.
BibTeX
@inproceedings{ding2022conflict,
  author = {Qijie Ding and Daokun Zhang and Jie Yin},
  title = {{Conflict-Aware Pseudo Labeling via Optimal Transport for Entity Alignment}},
  booktitle = {ICDM},
  year = {2022},
  url = {https://openreview.net/forum?id=yVVUxE96l8},
}
Figure