Wasserstein-Fisher-Rao Embedding: Logical Query Embeddings with Local Comparison and Global Transport

Zihao Wang, Weizhi Fei, Hang Yin, Yangqiu Song, Ginny Y. Wong, Simon See

Introduction

Knowledge Graphs (KGs) serve as the backbone for many modern AI applications, storing vast amounts of structured facts. However, these graphs are often incomplete, necessitating methods that can perform complex logical reasoning over missing data. Query Embeddings have emerged as a powerful solution, mapping logical queries and entities into a continuous vector space to predict missing links. A critical component of these systems is the scoring function, which determines the likelihood of an entity being a valid answer to a query.

The Scoring Function Dilemma

Existing scoring functions typically fall into two categories, each with significant drawbacks:

  1. Local Comparison: Metrics like Euclidean distance or KL divergence compare embeddings point-by-point. While computationally efficient, they are "blind" to geometric similarities between non-overlapping regions.
  2. Global Transport: Metrics based on Optimal Transport (e.g., Wasserstein distance) measure the cost of moving "mass" between distributions. These capture geometric relationships effectively but are computationally expensive and can be unstable during training due to the dominance of large distances in the loss function.
A logical query graph illustrating how entities and relations are combined using set operators to find an answer set.

Wasserstein-Fisher-Rao Embedding (WFRE)

Wasserstein-Fisher-Rao Embedding (WFRE) bridges this gap by representing sets as bounded measures in $\mathbb{R}$, discretized as histograms on a uniform grid. The core innovation is the use of the Wasserstein-Fisher-Rao (WFR) metric, which allows for "unbalanced" transport.

In this framework, mass can be moved globally (transport) or created/destroyed locally (comparison). This balance is governed by a transport radius $\eta$: if two mass points are within $\eta$, the model prioritizes transport; otherwise, it relies on local comparison. This "Goldilocks" approach provides the stability of local comparison with the geometric awareness of global transport.

This figure illustrates how WFR (middle) combines the strengths of global transport (left) and local comparison (right) by balancing mass movement and local creation/destruction.

Computational Efficiency and Set Operators

To make WFRE viable for large-scale KGs, the authors introduced two key optimizations:

  • Convolution-based Sinkhorn: By treating kernel multiplication as a 1D discrete convolution, complexity is reduced to linear time, $O(d)$.
  • Block-Diagonal Kernel: Restricting transport to specific positions encourages parallelization and enforces the local/global trade-off.

Furthermore, because embeddings are histograms, the framework utilizes fuzzy logic t-norms (such as min/max) to define closed-form operators for logical intersection, union, and complement.

Experimental Results

WFRE was evaluated against several rigorous benchmarks, including FB15k, FB15k-237, NELL, and the hierarchical WN18RR dataset. Key findings include:

  • State-of-the-Art Performance: On FB15k, WFRE achieved a Mean Reciprocal Rank (MRR) of 52.8 for EPFO queries, outperforming previous leaders like GammaE.
  • Superior Generalization: The model demonstrated a higher performance "slope" as query complexity increased, indicating better handling of complex, unseen logical structures.
  • Hierarchical Reasoning: WFRE significantly improved performance on multi-hop queries in WN18RR, proving that its global transport mechanism effectively captures the "flow" of hierarchical data (e.g., "is-a" relations).

Conclusion

WFRE represents a significant step forward in logical query embedding. By balancing local and global views through the WFR metric, it achieves superior stability and performance while maintaining the linear-time efficiency required for industrial-scale knowledge graphs. Future work will explore its application to inductive reasoning and even larger datasets with billions of edges.

Summary updated

BibTeX
@inproceedings{wang2023wasserstein,
  author = {Zihao Wang and Weizhi Fei and Hang Yin and Yangqiu Song and Ginny Y. Wong and Simon See},
  title = {{Wasserstein-Fisher-Rao Embedding: Logical Query Embeddings with Local Comparison and Global Transport}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2023},
  doi = {10.18653/v1/2023.findings-acl.864},
}
Figure