Distance-Based Propagation for Efficient Knowledge Graph Reasoning (2023)

Abstract: Knowledge graph completion (KGC) aims to predict unseen edges in knowledge graphs (KGs), resulting in the discovery of new facts. A new class of methods have been proposed to tackle this problem by aggregating path information. These methods have shown tremendous ability in the task of KGC. However they are plagued by efficiency issues. Though there are a few recent attempts to address this through learnable path pruning, they often sacrifice the performance to gain efficiency. In this work, we identify two intrinsic limitations of these methods that affect the efficiency and representation quality. To address the limitations, we introduce a new method, TAGNet, which is able to efficiently propagate information. This is achieved by only aggregating paths in a fixed window for each source-target pair. We demonstrate that the complexity of TAGNet is independent of the number of layers. Extensive experiments demonstrate that TAGNet can cut down on the number of propagated messages by as much as 90% while achieving competitive performance on multiple KG datasets.

## introduction knowledge graphs (kgs) encode facts via edges in a graph. because of this, one can view the task of predicting unknown edges (i.e. link prediction) as analogous to uncovering new facts. this task is referred to as knowledge graph completion (kgc) and has attracted a bevy of research over the past decade @xcite @xcite . most work has focused on learning quality representations for all nodes (i.e. entities) and edge types (i.e. relations) in the graph to facilitate kgc. recently, methods @xcite @xcite , have been introduced that move away from the embedding-based approach and focus instead on learning directly from path-based information. one recent gnnbased method, nbfnet @xcite , draws inspiration from the bellman-ford algorithm by computing path information through dynamic programming. by doing so, it learns pairwise embeddings between all node pairs in an inductive fashion. it achieves state-of-the-art performance in both the transductive and inductive kgc settings. in this work, we refer to such methods as pathbased gnns. however, a downside of path-based gnns is their inefficiency. this limits their ability in large real-world graphs. furthermore, it inhibits their ability to propagate deeply in the graph. two recent methods have been proposed to address the inefficiency problem, i.e., a * net @xcite and adaprop @xcite , by only propagating to a subset of nodes every iteration. however, they still tend to propagate unnecessary and redundant messages. for path-based gnns, only the source node is initialized with a non-zero message at the beginning of the propagation process. such models often run a total of t layers, where, in each layer, all nodes aggregate messages from their neighboring edges. we identify that this design is inefficient by making the following two observations. (1) empty messages: in the propagation process, a node only obtains non-empty messages when the number of propagation layers @xmath0. this means that a large number of nodes far from the source node only aggregate "empty" messages in the early propagation layers. nonetheless, path-based gnn models such as nbfnet propagate these unnecessary "empty messages" in these early propagation layers. (2) redundant messages: to ensure path information from the source reach distant nodes, the number of layers t needs to be sufficiently large. however, a large t induces the propagation of redundant messages for those nodes that are close to the source node. intuitively, short paths contain more significant information than long ones @xcite . the "close" nodes typically aggregate enough information from shorter paths in the early propagation layers. propagating messages for longer paths in later layers for "close" nodes does not provide significant information and needlessly adds to the complexity. more details on these two observations are provided in section 3.1. to address these limitations and make the propagation process more efficient, we aim to develop an algorithm that limits the propagation of "empty" and "redundant" messages. in particular, we propose a new method tagnet -truncated propagation network. tagnet only aggregates paths in a fixed window for each source-target pair, which can be considered a form of path pruning. our contributions can be summarized as follows: ## preliminary in this section, we first introduce the notation used throughout the paper. we then introduce the path formulation from @xcite , the generalized bellman-ford algorithm (baras and theodorakopoulos, 2010), and nbfnet @xcite . ## the proposed framework in this section, we propose a new approach to improve the efficiency of path-based gnn models. inspired by two observations in section 3.1, we proposed a simple but effective distance-based pruning strategy. we then introduce a truncated version of the generalized bellman-ford algorithm that achieves the goal of our proposed pruning strategy. finally, we describe a neural network model based on the truncated bellman-ford. ## conclusion in this paper we identify two intrinsic limitations of path-based gnns that affect the efficiency and representation quality. we tackle these issues by introducing a new method, tagnet, which is able to efficiently propagate path information. this is realized by only aggregating paths in a fixed window for each source-target pair. we demonstrate that the complexity of tagnet is independent of the number of layers. for future work, we plan on exploring methods to capture path information without having to perform a separate round of propagation for every individual source node.