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