Prediction and Calibration: Complex Reasoning over Knowledge Graph with Bi-directional Directed Acyclic Graph Neural Network (2023)

Abstract: Answering complex logical queries is a challenging task for knowledge graph (KG) reasoning. Recently, query embedding (QE) has been proposed to encode queries and entities into the same vector space, and obtain answers based on numerical computation. However, such models obtain the node representations of a query only based on its predecessor nodes, which ignore the information contained in successor nodes. In this paper, we proposed a Bi-directional Directed Acyclic Graph neural network (BiDAG) that splits the reasoning process into prediction and calibration. The joint probability of all nodes is considered by applying a graph neural network (GNN) to the query graph in the calibration process. By the prediction in the first layer and the calibration in deep layers of GNN, BiDAG can outperform previous QE based methods on FB15k, FB15k-237, and NELL995.

## introduction knowledge graphs (kgs) organize world knowledge as interlinked triples which describe entities and their relationships @xcite . compared with link prediction @xcite , answering logical queries (i.e., complex query answering, cqa @xcite , as shown in figure 1 (a )) is a more challenging task because it needs to perform first-order logic (fol) operators such as conjunction (∧), disjunction (∨), and negation (¬). recently, query embedding (qe) models @xcite have been proposed to jointly encode logical queries and entities into the same vector space, and then retrieve answers (entities) based on the similarity scores. although qe models can obtain answers in linear time and implicitly reason over incomplete kgs by iteratively predicting the representation of intermediate and target nodes, such models obtain the representation of the current node only based on its predecessor nodes, which causes (1) the joint probability of all nodes in the query graph is ignored. take the example in figure 1 , the probability distribution of node v 1 will be more concentrated in japan and china after considering node a1. (2) the information contained in successor nodes is ignored. as shown in figure 1 , the type of node v 1 can only be country after considering the successor relation nationality.) to address the above drawbacks, in this paper, we propose a novel qe based method called bidirectional directed acyclic graph neural network (bidag), which splits the reasoning process into the following two processes: (1) prediction is used to obtain the initial representation of nodes by aggregating the information of predecessor nodes, which is similar to previous qe models. (2) calibration. in this process, the original unidirectional query graph is extended to a bidirectional graph, then we apply gnn to the bidirectional graph. in this way, bidag can take the joint probability into account, as each node is continuously calibrated by information of its predecessor and successor nodes. our contributions can be summarized as follows: ## related work modeling entity and query representations and logical operators are critical points of qe models. gqe @xcite answers the conjunctive queries by representing queries and entities as points in euclidean space. to represent queries with a large set of answer entities, query2box @xcite utilized hyper-rectangles to encode queries. by converting union queries into disjunctive normal form (dnf) (davey and priestley, 2002), query2box can handle arbitrary existential positive first-order (epfo) queries (i.e., queries that include any set of ∧, ∨, ∃). to further support the negation operator (¬), betae @xcite was proposed to support a full set of operations in fol by encoding entities and queries into beta distributions. mlpmix (amayuelas et al., 2022) utilized mlp-mixer @xcite to model logical operators. by encoding each query into multiple points in the vector space, query2particles @xcite can retrieve a set of diverse answers from the embedding space. in this paper, we not only predict the intermediate and target node representations but also constantly calibrate them by modeling the joint probability of all nodes in the query graph. ## preliminary in this section, we formally describe the task of complex query answering over kgs. we denote a kg as @xmath0, r), where @xmath1, and each @xmath2: v × @xmath3, 1} which indicates whether a directed relationship r exists between a pair of entities. first-order logic queries the complex queries in kgs are described in logic form with first-order logic (fol) operators such as existential quantification (∃), conjunction (∧), disjunction (∨), and negation (¬). a complex query q consists of a set of anchor entities v a ⊆ v, some existential quantified variables v 1 , ...v k , and a single target variable v ? . the disjunctive normal form (dnf) of a fol query q is defined as follows: computation graph each logical query can convert to a corresponding computation graph in the form of directed acyclic graph (dag, as shown in figure 1 (b )), where each node corresponds to an entity, and each edge corresponds to a logical operation. the logical operations are defined as follows. it should be noticed that, in qe models, all these operations are executed in the embedding space. so, we can obtain the target node representation by iteratively computing the node representation following the neural logic operators in the dag. ## bi-directional directed acyclic graph neural network the key idea of bidag is utilizing information of predecessor nodes to obtain the current node representation and then calibrating the representation with global information, as shown in figure 2 . specifically, bidag includes two modules: 1) representation prediction module; 2) representation calibration module. in the view of gnn, bidag can be regarded as the stack of one prediction module (the first layer) and multiple calibration modules (the deep layers). ## conclusion in this paper, we propose bidag, a query embedding method for answering complex queries over incomplete kgs. bidag splits the reasoning process into prediction and calibration. in the calibration process, the joint probability of all nodes is considered by applying gnn to the query graph that is extended to bidirectional message passing. the extensive experiments on multiple open datasets demonstrate that bidag outperforms previous qe based models and the effect of calibration in cqa.