W asserstein-Fisher- R ao Embedding: Logical Query Embeddings with Local Comparison and Global Transport (2023)

Abstract: Answering complex queries on knowledge graphs is important but particularly challenging because of the data incompleteness. Query embedding methods address this issue by learningbased 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 scorning 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 R 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 is capable of outperforming 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.

## introduction knowledge graphs (kgs) store real-world factual knowledge as entity nodes and relational edges @xcite @xcite . and they facilitate many downstream tasks @xcite @xcite . notably, answering complex logical queries is an essential way to exploit the knowledge stored in knowledge graphs @xcite . formally speaking, complex logic queries can be expressed via first-order logic @xcite . specific groups of queries, whose predicates and logical connectives can be converted as set operatiors @xcite , are of particular interest due to their clear semantics. therefore, the logical reasoning process to answering complex queries is transformed to execute set projections and operations in an operator tree @xcite . figure 1 shows the operator tree for the query "who is the non-american director that has won golden globes or oscar". what makes this task difficult is the data incompleteness of knowledge graphs. modern large-scale kgs are naturally incomplete because they are constructed by crowdsource @xcite or automatic information extraction pipelines @xcite . this issue is acknowledged as the open world assumption @xcite . it leads to the fact that applying query answering algorithms for complete databases will not result in complete answers because of the data incompleteness. also, it is not able to prune the search space with the observed incomplete knowledge graph, which results in a large computational cost @xcite . it makes the problem even harder when answering logical queries on large knowledge graphs with billions of edges @xcite . we refer readers to recent surveys for more about logical queries on knowledge graphs @xcite . query embedding methods @xcite in fixed dimensional spaces are proposed to overcome the above difficulties. the data incompleteness is addressed by generalizing learnable set embeddings and operators to unseen data @xcite . and the computation cost does not grow with the developing efficient forms of set embeddings and operators is one of the recent focuses @xcite @xcite @xcite natural language: find non-american directors whose movie won golden globes or oscar? logical formula: 𝑞 = 𝑉 ? ∃ 𝑉 " . (won 𝑉 " , goldenglobes ∨ won(𝑉 " , oscar)) ∧ ¬bornin 𝑉 ? , america ∧ direct(v ? , v " ) set operators figure 1 : answering logical queries on knowledge graphs. natural language sentences can be interpreted as logical formulas and then converted to set operator trees @xcite . @xcite . however, the scoring function between sets, though it also characterizes set embeddings and plays a vital role in training models, is underexplored in the existing literature. existing scoring functions are chosen from two categories that emphasize either local comparisons @xcite or global transport between geometric regions @xcite @xcite . the following example motivated us to develop scoring functions for embeddings with both local and global trade-off. example 1.1. consider four "one-hot" vectors with dimension @xmath0: we observe that: in this paper, we develop a more effective scoring function motivated by the wasserstein-fisher-rao (wfr) metric @xcite , which introduces the local and global trade-off. we propose to embed sets as bounded measures in r, where each set embedding can be discretized as a bounded histogram on uniform grids of size d. this set embedding can be interpreted locally so that the set intersection, union, and negation can be easily defined by element-wise fuzzy logic t-norms @xcite . we propose an efficient convolutionbased algorithm to realize the computation of entropic wfr in o(d) time, and a block diagonal kernel to enforce the local and global trade-off. we conduct extensive experiments on large number of datasets: (1) standard complex query answering datasets over three kgs @xcite , (2) large-scale evaluation set emphasizing the combinatorial generalizability of models in terms of compositional complex queries @xcite , and (3) complex queries on a hierarchical knowledge graph @xcite . ablation studies show that the performance of complex query answering can be significantly improved by choosing a better trade-off between local comparison and global transport. ## related works we discuss other query embedding methods in fixed dimensions and optimal transport in this section. other methods for complex query answering are discussed in appendix a, figure 2 : illustration of different scoring functions. left: global transport, where the difference is measured by how to move mass from one place to another (purple arrows); right: local comparison, where the difference is measured by in-place comparison (yellow arrows); mid: local and global trade-off, where we first move mass in the transport radius η, then compare the unfilled mass. ## wasserstein-fisher-rao embedding the goal of this section is to present how to solve complex queries with set embeddings as the bounded measure in r. let the s be an arbitrary set, including the singleton set {e} with a single entity e, its embedding is m[s]. we denote the collection for all bounded measures as bm(r). our discussion begins with the discretization of measure m[s] ∈ bm(r) to histogram m @xmath1, where bm d is the collection of bounded histograms with d bars. then we discuss how to parameterize set operators with embeddings in the bm d and efficiently compute the scoring function in bm d . finally, we introduce how to learn set embeddings and operators. ## experiments in this section, we evaluate the performance of wfre on complex query answering in three aspects: (1) we compare wfre with other sota query embedding methods over commonly used datasets on three knowledge graphs @xcite ; (2) we evaluate wfre on 301 query types to justify its combinatorial generalizability @xcite ; (3) we train and evaluate wfre on a complex query answering datasets on wordnet @xcite , a lexical kg whose relations are typically hierarchical @xcite . aspects (2) and (3) emphasize on different query types and the underlying kg, respectively. these results provide empirical evidence for wfre's strong capability for applying to various query types and kgs. moreover, we also investi-gate the local and global tradeoff of wfre on ω and a in the ablation study. other results are listed in the appendix. ## conclusion in this paper, we propose wfre, a new query embedding method for complex queries on knowledge graphs. the key feature of wfre against to previous methods is its scoring function that balances local comparison and global transport. empirical results show that wfre is the state-of-the-art query embedding method for complex query answering, and has good generalizability to combinatorially complex queries and hierarchical knowledge graphs. the ablation study justifies the importance of the local and global trade-off.