Query Structure Modeling for Inductive Logical Reasoning Over Knowledge Graphs (2023)

Abstract: Logical reasoning over incomplete knowledge graphs to answer complex logical queries is a challenging task. With the emergence of new entities and relations in constantly evolving KGs, inductive logical reasoning over KGs has become a crucial problem. However, previous PLMs-based methods struggle to model the logical structures of complex queries, which limits their ability to generalize within the same structure. In this paper, we propose a structure-modeled textual encoding framework for inductive logical reasoning over KGs. It encodes linearized query structures and entities using pre-trained language models to find answers. For structure modeling of complex queries, we design stepwise instructions that implicitly prompt PLMs on the execution order of geometric operations in each query. We further separately model different geometric operations (i.e., projection, intersection, and union) on the representation space using a pre-trained encoder with additional attention and maxout layers to enhance structured modeling. We conduct experiments on two inductive logical reasoning datasets and three transductive datasets. The results demonstrate the effectiveness of our method on logical reasoning over KGs in both inductive and transductive settings.

## introduction logical reasoning over knowledge graphs (kgs) aims to answer complex logical queries given largescale kgs @xcite . recent years have witnessed increasing attention on logical reasoning over widely used kgs such as freebase @xcite , yago (suchanek figure 1 : examples of inductive logical reasoning over kgs: testing queries contain unseen entities and relations (in red) during training. each query is associated with an intrinsic logical structure and its natural language interpretation. @xcite , nell @xcite and wikidata @xcite . with missing relations in the kg, it is challenging to deduce correct answers to complex queries by traversing the graph. previous work primarily focuses on transductive logical reasoning where the training and testing are done on the same kg with the same group of entities. they typically rely on geometric embedding-based methods to map both entities and queries into a joint low-dimensional vector space @xcite @xcite . the goal is to push the embeddings of answer entities and queries to be close to each other, allowing answers to be predicted through embedding similarity even when the involved relation is absent. in contrast, the inductive setting of logical reasoning has been rarely studied which requires generalizing to unseen entities and relations or even new kgs. as real-world kgs are usually dynamic with emerging unseen entities and relations, it's significant to explore the inductive setting for complex query answering. existing research on inductive logical reasoning mainly follows two directions. the first inherits embedding-based methods and incorporates type as additional information to improve inductive capability @xcite , which can not generalize to unseen types of entities and relations. the second direction leverages pre-trained language models (plms) to encode textual information of entities/relations for generalization to unseen elements @xcite @xcite . plms-based approaches provide more flexible solutions and generate better results. however, they only explore link prediction tasks of one-step reasoning, and simply linearize the triplet or subgraph into text sequence without modeling explicit reasoning structure @xcite . an example is shown in figure 1 . two findings stand out. (1) the query q 1 and q 2 appear to be similar in format (both as a conjunction of three terms) but actually have different logical structures. plms-based methods that encode flattened queries can not model this structure information for correct logical reasoning. (2) although queries q 1 and q 3 (also q 2 and q 4 ) contain different elements, they share the same logical structure. motivated by these, we argue that structure modeling of different complex queries can further boost the generalization ability of logical reasoners. in this paper, we propose to model query structure for inductive logical reasoning over kgs. specifically, we transform the query structure into a sequence using textual names of involved entities, relations, and logical operators. for complex query structures composed of multiple geometric operations over entities and relations, we introduce two measures to enable logical structure modeling during text encoding. first, we design stepwise instructions for different query types to indicate which operation in the query structure should be conducted at each step and feed them as the structural prompt to plms. besides, we extend the pre-trained encoder with an additional attention layer and a maxout layer to respectively model different geometric operations including projection, intersection, and union on the representation space, to implicitly inject structured modeling into plms. our proposed method is a generic inductive framework, which can be plugged into different plms for better performance. we conduct experiments on two datasets for inductive logical reasoning over kgs, fb15k-237-v2 and nell-v3 @xcite as well as three transductive datasets, fb15k @xcite , fb15k-237 @xcite , and nell995 @xcite . the results demonstrate that our method achieves strong inductive performance on unseen entities and relations, even across different kgs, without sacrificing logical reasoning capability and generalizability to new query structures. ## methodology in this work, we study the task of complex logical reasoning over kgs. the input is a first-order logic query q which can include any set of existential quantification (∃), conjunction (∧), and disjunction (∨) operators (such as the query in figure 1 ). our goal is to predict a set of entities @xmath0, a 2 , a 3 ...} that answer the query q based on an incomplete kg @xmath1, r) which consists of a set of triplets (h, r, t) but lacks several involved relations. here h, @xmath2. we mainly focus on the inductive setting of kg logical reasoning, where the evaluated queries contain entities/relations that are completely unseen during the training period. figure 2 shows the overall architecture of our model. we propose to encode the text sequences of query structures and predict the answer entities based on representation similarity for inductive logical reasoning over kgs. in this section, we first list different types of query structures studied in logical reasoning over kgs( § 2.1). then according to various query types, we introduce our structure linearization and structural prompts for textual encoding( § 2.2). the geometric operation modeling and query answer prediction modules are described in ( § 2.3) and ( § 2.4). finally, we provide the de- ## related work answering first-order logic queries over incomplete kgs is a challenging task @xcite . previous research @xcite mainly studies transductive logical reasoning, where the training and testing are performed on the same kg. embedding-based methods are widely used to embed both logical queries and entities into a joint low-dimensional vector space and push answer entities and queries to be close enough, enabling answer prediction through embedding similarity, even when the involved relation is absent. following this paradigm, some further propose extending the embedding of the query/entity from a single point to a region @xcite @xcite or probabilistic distribution (ren and leskovec, 2020; @xcite over vector space to map arbitrary first-order logic queries into sets of answer entities. however, these methods are unable to tackle the inductive problem, which requires generalizing to unseen entities and relations. although @xcite proposes enriching the entity and relation embedding with type information for inductive logical reasoning, it can only generalize to elements of observed types. another line of research focuses on inductive logical reasoning over kgs using textual encoding methods. with the advance of large-scale pre-trained language models @xcite , these methods propose transforming the graph structures into linearized text and utilize plms for encoding @xcite . with the strong generalizability of plms, they can easily generalize to unseen entities/relations, but struggle to model structure knowledge during text encoding. some works @xcite @xcite propose to follow transe @xcite to apply the translation function between entity and relation representations for geometric structure learning. nevertheless, these methods usually require descriptions of entities and relations for encoding and assume these descriptions are readily available. besides, they only focus on simple link prediction tasks without exploring complex structure modeling in logical reasoning, which is essential for generalizing within the same query structure/type. we thus propose to simultaneously encode the linearized query and preserve the logical structure knowledge by structural prompt and separate geometric operation modeling for inductive logical reasoning over kgs. ## conclusion in this paper, we present the first flexible inductive method for answering complex logical queries over incomplete kgs which can generalize to any unseen entities and relations. to accomplish this goal, we propose a structure-model textual encoding model that utilizes plms to encode linearized query structures to find the answer entities. for structure modeling of complex queries, we design structural prompts to implicitly indicate plms the order of geometric operations execution in each query, and separately model three geometric operations on representation space using a pre-trained encoder, an attention layer, and a maxout layer. experimental results demonstrate the effectiveness of our model on logical reasoning over kgs in both inductive and transductive settings.