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
Answering complex queries on knowledge graphs is important but particularly
challenging because of the data incompleteness. Query embedding methods address
this issue by learning-based models and simulating logical reasoning with set
operators. Previous works focus on specific forms of embeddings, but scoring
functions between embeddings are underexplored. In contrast to existing scoring
functions motivated by local comparison or global transport, this work
investigates the local and global trade-off with unbalanced optimal transport
theory. Specifically, we embed sets as bounded measures in $\real$ endowed with
a scoring function motivated by the Wasserstein-Fisher-Rao metric. Such a
design also facilitates closed-form set operators in the embedding space.
Moreover, we introduce a convolution-based algorithm for linear time
computation and a block-diagonal kernel to enforce the trade-off. Results show
that WFRE can outperform existing query embedding methods on standard datasets,
evaluation sets with combinatorially complex queries, and hierarchical
knowledge graphs. Ablation study shows that finding a better local and global
trade-off is essential for performance improvement.