Improving Multi-hop Logical Reasoning in Knowledge Graphs with Context-Aware Query Representation Learning (2024)

Abstract: Multi-hop logical reasoning on knowledge graphs is a pivotal task in natural language processing, with numerous approaches aiming to answer First-Order Logic (FOL) queries. Recent geometry (e.g., box, cone) and probability (e.g., beta distribution)-based methodologies have effectively addressed complex FOL queries. However, a common challenge across these methods lies in determining accurate geometric bounds or probability parameters for these queries. The challenge arises because existing methods rely on linear sequential operations within their computation graphs, overlooking the logical structure of the query and the relation-induced information that can be gleaned from the relations of the query, which we call the context of the query. To address the problem, we propose a model-agnostic methodology that enhances the effectiveness of existing multi-hop logical reasoning approaches by fully integrating the context of the FOL query graph. Our approach distinctively discerns (1) the structural context inherent to the query structure and (2) the relation-induced context unique to each node in the query graph as delineated in the corresponding knowledge graph. This dual-context paradigm helps nodes within a query graph attain refined internal representations throughout the multi-hop reasoning steps. Through experiments on two datasets, our method consistently enhances the three multi-hop reasoning foundation models, achieving performance improvements of up to 19.5%. Our codes are available at https://github.com/kjh9503/caqr.

## introduction multi-hop logical reasoning on knowledge graphs (kgs) is a crucial task in natural language processing. kgs, which map real-world knowledge as interconnected entities and relationships @xcite , help * corresponding author answer complex questions expressed as first-order logic (fol) queries. a fol query can be converted into a computation graph, using variables, conjunctions, and existential quantification operators to represent a natural language question. for example, the computation graph of the query representing "what are the names of the teams playing the team sports featured in the 1980 olympics?" can be constructed with two conjunction relations: 1) finding the sports featured in the 1980 olympics, and 2) finding the sports teams that play that sports (see figure 1 for illustration). recent advancements in multi-hop reasoning leverage the power of embedding-based models such as q2b @xcite , betae @xcite , and cone @xcite . these models embed both a given query and entities (answer candidates) in a kg into a latent space. in this space, entities relevant to the query are positioned closer to the query's embedding. this allows the model to predict the answer to the query by identifying these nearby entities. despite their success, these embedding-based models still face a major hurdle: learning more accurate geometric bounds or probability parameters for complex queries. prior models handle all queries in the same way, building the embedding for each relationship (e.g., f eaturedat -1 or t eamsp lay -1 in figure 1 ) one after another. this approach overlooks the structural context and relation-induced context within each question. therefore, entities like sprint, marathon, triathlon, and figure are treated as answers by the existing models @xcite @xcite based on the given query in figure 1 . to address this limitation, we propose a novel query embedding technique, named caqr (context-aware query representation learning), that incorporates both structural context and relation-induced context. the structural context encodes the positional or role-like information of a node within the query computation graph. for example, in figure 1 , the structural context of node v could include the number of incoming and outgoing edges, the canonical position of v within the query graph, and the length of the query graph containing node v. based on this, figure can be excluded as a v candidate because it is unlikely to be derived through the one-hop reasoning from the 1980 olympics in kg. the relation-induced context, on the other hand, leverages kg entities linked to each node's relations. for instance, in the query graph shown in figure 1 , the relationinduced context-acquired by identifying nodes in the kg associated with t eamsp lay -1 -suggests that sprint, marathon, and triathlon are not suitable candidates for v by accentuating the entities which linked to the t eamsp lay -1 relations (soccer, volleyball, and basketball). by incorporating structural and relation-induced contexts into the existing query embedding methods, our approach mitigates the cascading errors that can arise from the step-by-step computation characteristic of these methods. our contributions are threefold: (1) we propose a novel query representation learning method that leverages two types of context within a query computation graph: structural context and relationinduced context, which are often overlooked in previous methods. (2) our proposed technique is applicable to any existing query embeddingbased method, as it utilizes structural and relationinduced context acquired from the input query graph, irrespective of the models. (3) our experiments show that our method leads to performance improvements for various models (q2b @xcite , betae @xcite , and cone @xcite ), which have received considerable attention in various fol tasks as foundation models. specifically, our experiments on two benchmark datasets demonstrate that our method consistently improves these models, achieving up to a 19.5% enhancement in query reasoning tasks compared to their baselines. probability-based. in contrast to geometrybased approaches, probability-based methods represent queries as probability distributions. for example, betae @xcite uses multiple beta distributions to represent a query, entities, and relations. similar approaches include gammae @xcite with gamma distributions and perm @xcite with multivariate gaussian distributions. these methods measure the distance between the query embedding and candidate entities using kl-divergence. fuzzqe @xcite takes a different approach, mapping queries and entities to a fuzzy space. it represents the answer set as a fuzzy vector and calculates the probability of an entity being an answer using a score function. similarly, gnn-qe @xcite adopts fuzzy logic to represent queries and entities but uses graph neural networks for projection in an incomplete kg. on the other hand, wfre @xcite ) models queries and entities as discretized mass vectors that satisfy fuzzy logic. it models logical operators through t-norm or t-conorm functions and measures the distance between mass vectors using the optimal transport theory @xcite . while each method has its advantages and disadvantages and is selectively utilized in various fol-based applications @xcite @xcite , the potential of query-based context encoding to enhance multiple multi-hop reasoning approaches and yield robust performance improvements has not received sufficient attention. query encoder-based. there are auxiliary transformation encoders for representing the fol queries for multi-hop reasoning. these include q2t @xcite and lmpnn @xcite , which take distinct approaches to tackling complex queries. q2t transforms the complex query into a single virtual triple of head, relation, and tail components. it computes the score of this virtual triple with a pre-trained kg embedding model to predict the answer to the query. lmpnn @xcite , on the other hand, decomposes the complex multi-hop query into multiple simpler triples. it generates a message using the entity embedding to maximize the score for each triple, utilizing a pre-trained kg embedding model. however, these approaches require initial kg embeddings from extensive pre-training and are not applicable to various multi-hop reasoning approaches. ## preliminaries given an entity set v and a relation set r, the kg @xmath0, r, t) ⊂ v × r × v represents a collection of triples that encapsulate factual information in the real world. here, h, @xmath1, and @xmath2. when considering each relation as a binary function, such as r(h, t), following the structure of predicate logic, the triples observed from the kg hold a value of true. ## methodology in this section, we explain caqr, our method that leverages context information from the query graph to create more accurate and nuanced entity embeddings. by incorporating context, caqr can make fine-grained adjustments within the embedding space, capturing the complexities of real-world queries. caqr concentrates on two key types of context: structural context and relation-induced context. the structural context combines positional cues (where nodes appear in the query) and functional roles (the specific role a node plays) to comprehend the overall structure and relationships within the query. furthermore, the relation-induced context focuses on the specific relationships and interactions between entities within the query. caqr combines these structural and relation-induced contexts to create a more comprehensive query embedding. ## conclusion in this paper, we introduced caqr, a modelagnostic approach that leverages structural and relation-induced context within the query graph. by seamlessly fusing position, role, type, and relation-induced embeddings into the query representation, caqr substantially improves the performance of query embedding-based multi-hop reasoning models across diverse query types.