SQUIRE : A Sequence-to-sequence Framework for Multi-hop Knowledge Graph Reasoning (2022)

Abstract: Multi-hop knowledge graph (KG) reasoning has been widely studied in recent years to provide interpretable predictions on missing links with evidential paths. Most previous works use reinforcement learning (RL) based methods that learn to navigate the path towards the target entity. However, these methods suffer from slow and poor convergence, and they may fail to infer a certain path when there is a missing edge along the path. Here we present SQUIRE, the first Sequence-to-sequence based multi-hop reasoning framework, which utilizes an encoder-decoder Transformer structure to translate the query to a path. Our framework brings about two benefits: (1) It can learn and predict in an end-to-end fashion, which gives better and faster convergence; (2) Our transformer model does not rely on existing edges to generate the path, and has the flexibility to complete missing edges along the path, especially in sparse KGs. Experiments on standard and sparse KGs show that our approach yields significant improvement over prior methods, while converging 4x-7x faster.

## introduction knowledge graph (kg) provides structural knowledge about entities and relations in real world in the form of triples. each edge in the graph, connecting two entities with a relation, represents a triple fact (h, r, t). knowledge graph supports a variety of downstream tasks, such as question answering @xcite , information retrieval @xcite and hierarchical reasoning @xcite . however, practical kgs often suffer from incompleteness, thus proposing the task of kg completion, such as predicting the tail entity t given (h, r). a popular approach for such a challenge is knowledge graph embedding (kge) @xcite , which infers a missing edge in a complete black-box manner. figure 1 : an example of multi-hop reasoning in an incomplete knowledge graph. the missing links (dashed arrows) can be inferred from existing links (solid arrows). however, such an evidential path may not be inferred when there is a missing edge (gray dashed arrow) along the path. to strengthen the interpretability of kg completion, @xcite proposes multi-hop knowledge graph reasoning. given a triple query (h, r), the task aims not only to predict the tail entity t, but to give the evidential path from h to t that indicates the inference process, e.g., we can infer (albert, native language, ?) from the relational path "born in" and "language", as shown in fig. 1 . most previous works use walk-based method @xcite @xcite to tackle such problem, where an agent is trained under the reinforcement learning (rl) framework to learn to "walk" from the head entity to the tail entity. one major drawback of these rl-based methods is that they suffer from slow and poor convergence, since the reward can be temporally delayed during the training process of rl @xcite . in fig. 2 , we show the training time of kge model (transe by @xcite , blue curve) and rl-based multi-hop reasoning model @xcite , brown curve) under different graph sizes. though multi-hop reasoning is a harder task than kg completion, 1×10 5 2×10 5 3×10 5 4×10 5 5×10 5 6×10 for rl-based model, the trade-off on time is still unbearable as the size of the graph grows. moreover, as @xcite points out, previous approaches suffer from the missing path problem, i.e., the model fails to infer an evidential path between pair of entities due to missing edges along the path, especially in sparse kgs. as shown in fig. 1 , there is no evidential path between albert and hans due to the missing of relation "spouse". amazingly, we show that both drawbacks can be alleviated by a new sequence to sequence framework for multi-hop reasoning (squire). by posing multi-hop reasoning as a sequence-to-sequence problem, we use a transformer encoder-decoder model @xcite to "translate" a query sequence to a path sequence. for model learning, each triple induces a supervised training sample consisting of a source sequence, i.e., query (h, r), and a target path sequence sampled from all paths between h and t. hence, squire framework learns and predicts in a complete end-to-end fashion, yielding faster and more stable convergence than rl-based methods (green curve in training time comparison fig. 2 ). furthermore, our approach naturally overcomes the missing path problem, since the transformer does not explicitly rely on existing edges in the graph to generate the path sequence. that is, our proposed method has the flexibility to "walk and complete": automatically infers missing edges along the path. meanwhile, multi-hop reasoning poses particular challenges to our framework. (a) noisy sample: unlike in language modeling where we have a groundtruth target sequence, in our case, there is no such supervision on the target path. a naive way to obtain the target path is randomly sampling from all paths between h and t, but this might introduce noise into model learning since the random path may be spurious. to address this, we propose rule-enhanced learning. we search groundtruth paths by logical rules mined from the kg, which are less noisy and more reliable compared to randomly sampled paths. (b) history gap: during training, we provide the groundtruth sequence as the path history for our model to predict the next token. yet, during inference the history is generated by the model from scratch, resulting in a deviation from its training distribution. in language modeling, this is also known as exposure bias @xcite , a common challenge faced in autoregressive models. to narrow such a gap, we propose iterative training that iteratively aggregates new paths to the training set based on the model's previous predictions, adapting the model to the distribution of history tokens it induces. we evaluate the performance of squire on link prediction over six benchmark kgs. squire achieves state-of-the-art results across all datasets. moreover, on two sparse kgs, our model outperforms dackgr @xcite , which is specifically designed to handle the sparse setting. squire takes 4x-7x less time to converge on larger kg datasets while obtaining better performance. to the best of our knowledge, squire is the first sequence-to-sequence framework for multihop reasoning, and may provide a new paradigm for future studies. ## conclusion this paper introduces squire, a sequence-tosequence framework for efficient and effective multi-hop knowledge graph reasoning. squire treats the triple query and the evidential path as sequences and utilizes transformer to learn and infer in an end-to-end fashion. we propose ruleenhanced learning and iterative training to further boost performance. experiments show that our approach significantly outperforms previous methods, on both standard kgs and sparse kgs. compared with rl-based methods, squire has faster convergence, and can be efficiently trained on larger kgs. moreover, we show that reasoning paths inferred by squire are more convincing than those generated by rl-based baselines.