{'fraction_non_alphanumeric': 0.03903459296860312, 'fraction_numerical': 0.009494265839443504, 'mean_word_length': 4.689664393635513, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 5, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Relational Message Passing for Knowledge Graph Completion

Knowledge graph completion aims to predict missing relations between entities in a knowledge graph. In this work, we propose a relational message passing method for knowledge graph completion. Different from existing embedding-based methods, relational message passing only considers edge features (i.e., relation types) without entity IDs in the knowledge graph, and passes relational messages among edges iteratively to aggregate neighborhood information. Specifically, two kinds of neighborhood topology are modeled for a given entity pair under the relational message passing framework: (1) Relational context, which captures the relation types of edges adjacent to the given entity pair; (2) Relational paths, which characterize the relative position between the given two entities in the knowledge graph. The two message passing modules are combined together for relation prediction. Experimental results on knowledge graph benchmarks as well as our newly proposed dataset show that, our method PathCon outperforms state-of-the-art knowledge graph completion methods by a large margin. PathCon is also shown applicable to inductive settings where entities are not seen in training stage, and it is able to provide interpretable explanations for the predicted results. The code and all datasets are available at https://github.com/hwwang55/PathCon.


INTRODUCTION
Knowledge graphs (KGs) store structured information of real-world entities and facts. A KG usually consists of a collection of triplets. Each triplet (ℎ, , ) indicates that head entity ℎ is related to tail entity through relationship type . Nonetheless, KGs are often  incomplete and noisy. To address this issue, researchers have proposed a number of KG completion methods to predict missing links/relations in KGs [3,9,12,13,19,22,24,35,36,39,40]. In general, relation types are not uniformly distributed over a KG but spatially correlated with each other. For example, the neighboring relations of "graduated from" in the KG are more likely to be "person.birthplace" and "university.location" rather than "movie.language". Therefore, for a given entity pair (ℎ, ), characterizing the relation types of neighboring links of ℎ and will provide valuable information when inferring the relation type between ℎ and . Inspired by recent success of graph neural networks [11,15,34], we propose using message passing to capture the neighborhood structure for a given entity pair. However, traditional message passing methods usually assume that messages are associated with nodes and messages are passed from nodes to nodes iteratively, which are not suitable for KGs where edge features (relation types) are more important.
Relational message passing. To address the above limitation, we propose relational message passing for KG completion. Unlike traditional node-based message passing, relational message passing only considers edge features (relation types), and passes messages of an edge directly to its neighboring edges. Note that since relational message passing only models relations rather than entities, it brings three additional benefits compared with existing knowledge graph embedding methods [3,13,22,24,35,39]: (1) it is inductive, since it can handle entities that do not appear in the training data during inference stage; (2) it is storage-efficient, since it does not calculate embeddings of entities; and (3) it is explainable, since it is able to provide explainability for predicted results by modeling the correlation strength among relation types. However, a potential issue of relational message passing is that its computational complexity is significantly higher than node-based message passing (Theorem 2). To solve this issue, we propose alternate relational message passing that passes relational messages between nodes and edges alternately over the KG. We prove that alternate message passing scheme greatly improves time efficiency and achieves the same order of computational complexity as traditional node-based message passing (Theorem 1 and 3).
Relational context and relational paths. Under the alternate relational message passing framework, we explore two kinds of local subgraph topology for a given entity pair (ℎ, ) (see Figure 1 for an illustrating example): (1) Relational context. It is important to capture the neighboring relations of a given entity in the KG, because neighboring relations provide us with valuable information about what is the nature or the "type" of the given entity ( Figure  1a). Many entities in KGs are not typed or are very loosely typed, so being able to learn about the entity and its context in the KG is valuable. We design a multi-layer relational message passing scheme to aggregate information from multi-hop neighboring edges of (ℎ, ). (2) Relational paths. Note that modeling only relational context is not able to identify the relative position of (ℎ, ). It is also important to capture the set of relational paths between (ℎ, ) ( Figure 1b). Here different paths of connections between the entities reveal the nature of their relationship and help with the prediction. Therefore, we calculate all relational paths connecting ℎ and in the KG and pass relational messages along these paths. Finally, we use an attention mechanism to selectively aggregate representations of different relational paths, then combine the above two modules together for relation prediction.
Experiments. We conduct extensive experiments on five wellknown KGs as well as a new KG proposed by us, DDB14 dataset. Experimental results demonstrate that our proposed model PathCon (short for relational PATHs and CONtext) significantly outperforms state-of-the-art KG completion methods, for example, the absolute Hit@1 gain over the best baseline is 16.7% and 6.3% on WN18RR and NELL995, respectively. Our ablation studies show the effectiveness of our approach and demonstrate the importance of relational context as well as relational paths. Our method is also shown to maintain strong performance in inductive KG completion, and it ? head ℎ tail Relational Context Relational Path Figure 2: An example of PathCon considering both the relational context within 2 hops of the head and the tail entities (denoted by red edges) and relational paths of length up to 3 relations that connect head to tail (denoted by green arrows). Context and paths are captured based on relation types (not entities) they contain. By combining the context and paths PathCon predicts the probability of relation .
provides high explainability by identifying important relational context and relation paths for a given predicted relation.

Contributions.
Our key contributions are listed as follows: • We propose alternate relational message passing framework for KG completion, which is inductive, storage-efficient, explainable, and computationally efficient compared with existing embedding-based methods; • Under the proposed framework, we explore two kinds of subgraph topology: relational context and relational paths, and show that they are critical to relation prediction; • We propose a new KG dataset DDB14 (Disease Database with 14 relation types) that is suitable for KG-related research.

PROBLEM FORMULATION
Let G = (V, E) be an instance of a knowledge graph, where V is the set of nodes and E is the set of edges. Each edge has a relation type ∈ R. Our goal is to predict missing relations in G, i.e., given an entity pair (ℎ, ), we aim to predict the relation of the edge between them. 1 Specifically, we aim to model the distribution over relation types given a pair of entities (ℎ, ): ( |ℎ, ). This is equivalent to modeling the following term according to Bayes' theorem. In Eq. (1), ( ) is the prior distribution over relation types and serves as the regularization of the model. Then the first term can be further decomposed to Eq. (2) sets up the guideline for designing our model. The term (ℎ| ) or ( | ) measures the likelihood of an entity given a particular relation. Since our model does not consider the identity of entities, we use an entity's local relational subgraph instead to represent the entity itself, i.e., Context representation of the entity pair (ℎ, ) ℎ→ Path representation of all paths from ℎ to Attention weight of path P ℎ→ Set of paths from ℎ to Table 1: Notation used in this paper.
denotes the local relational subgraph of an entity. This is also known as relational context for ℎ and . The term ( |ℎ, ) or (ℎ| , ) in Eq.
(2) measures the likelihood of how can be reached from ℎ or the other way around given that there is a relation between them. This inspires us to model the relational paths between ℎ and in the KG. In the following we show how to model the two factors in our method and how they contribute to relation prediction.

OUR APPROACH
In this section, we first introduce the relational message passing framework, then present two modules of the proposed PathCon: relational context message passing and relational path message passing. Notations used in this paper are listed in Table 1.

Relational Message Passing Framework
Traditional node-based message passing. We first briefly review traditional node-based message passing method for general graphs. Assume that each node is with feature . Then the message passing runs for multiple timesteps over the graph, during which the hidden state of each node in iteration is updated by where is the message received by node in iteration , N ( ) denotes the set of neighbor nodes of in the graph, (·) is message aggregation function, and (·) is node update function. The initial hidden state 0 = .
The above framework, though popular for general graphs and has derived many variants such as GCN [15], GraphSAGE [11], and GIN [34], faces the following challenges when applied to knowledge graphs: (1) Unlike general graphs, in most KGs, edges have features (relation types) but nodes don't, which makes node-based message passing less natural for KGs. Though node features can be set as their identities (i.e., one-hot vectors), this will lead to another two issues: (2) Modeling identity of nodes cannot manage previously unseen nodes during inference and fails in inductive settings. (3) In real-world KGs, the number of entities are typically much larger than the number of relation types, which requires large memory for storing entity embeddings.
Relational message passing. To address the above problems, a natural thought is to perform message passing over edges instead of nodes: where N ( ) denotes the set of neighbor edges of (i.e., edges that share at lease one common end-point with ) in the graph, and 0 = is the initial edge feature of , i.e., the relation type. Therefore, Eqs. (5) and (6) are called relational message passing.
Relational message passing avoids the drawbacks of node-based message passing, however, it brings a new issue of computational efficiency when passing messages. To see this, we analyze the computational complexity of the two message passing schemes (proofs are given in Appendix A and B): Theorem 1 (Complexity of node-based message passing). Consider a graph with nodes and edges. The expected cost of node-based message passing (Eqs. (3) and (4)) in each iteration is 2 + 2 .
Theorem 2 (Complexity of relational message passing). Consider a graph with nodes and edges. The expected cost of relational message passing (Eqs. (5) and (6)) in each iteration is · Var[ ] + 4 2 , where Var[ ] is the variance of node degrees in the graph.
Alternate relational message passing. According to the above theorems, the complexity of relational message passing is much higher than node-based message passing, especially in real-world graphs where node distribution follows the power law distribution whose variance (Var[ ]) is extremely large due to the long tail. To reduce the redundant computation in relational message passing and improve its computational efficiency, we propose the following message passing scheme for KGs: We decompose edge aggregation in Eq. (5) into two steps as Eqs. (7) and (8). In Eq. (7), for each node , we aggregate all the edges that connects to by an aggregation function 1 (·) and get message , where N ( ) denotes the set of neighbor edges for node . Then in Eq. (8), we obtain message of edge by aggregating messages from its two end-points and using function 2 (·), where N ( ) denotes the set of neighbor nodes for edge . The hidden state of edge is finally updated using the message as in Eq. (9). An intuitive understanding of alternate relational message passing is that nodes here serve as "distribution centers" that collect and temporarily store the messages from their neighbor edges, then propagate the aggregated messages back to each of their neighbor edges. Therefore, we call Eqs. (7)-(9) alternate relational message passing, as messages are passed alternately between nodes and edges.
The complexity of alternate relational message passing is given as follows (proof is given in Appendix C): Theorem 3 (Complexity of alternate relational message passing). Consider a graph with nodes and edges. The expected cost of alternate relational message passing (Eqs. (7)-(9)) in each iteration is 6 .
From Theorem 3 it is clear to see that alternate relational message passing greatly reduces the time overhead and achieves the same order of complexity as node-based message passing.
Remarks. We present the following two remarks to provide more insight on the proposed framework: Remark 1 (Relationship with belief propagation). Alternate relational message passing is conceptually related to belief propagation (BP) [37], which is also a message-passing algorithm that passes messages between nodes and edges. But note that they are significantly different in: (1) application fields. BP is used to calculate the marginal distribution of unobserved variables in a graphical model, while our method aims to predict the edge type in KGs; (2) the purpose of using edge-node alternate message passing. BP uses this because of the special structure of factor graphs, while we use this to reduce the computational overhead.
Remark 2 (Utilizing node features). Though our proposed framework is claimed to only use edge features, it can be easily extended to the case where node features are present and assumed to be important, by additionally including the feature vector of node in Eq. (7), i.e., , where is the feature of node . As long as node features do not contain node identities, our proposed framework is still inductive. We do not empirically study the performance of our method on node-feature-aware cases, because node features are unavailable for all datasets used in this paper. We leave the exploration of this extension to future work.

Relational Context
For a KG triplet (ℎ, , ), relational context of ℎ and is usually highly correlated with . For example, if is "graduated from", it's reasonable to guess that the surrounding relations of ℎ are "person.birthplace", "person.gender", etc., and the surrounding relations of are "institution.location", "university.founder", "university.president", etc. Therefore, the context of ℎ and will provide valuable clues when identifying the relation type of the edge between them, and here we use the proposed message passing method to learn from relational context.
Denote as the hidden state of edge in iteration , and as the message stored at node in iteration . We instantiate the alternate relational message passing in Eqs. (7)-(9) to learn the representation of each edge: where [·] is the concatenation function, , , and (·) are the learnable transformation matrix, bias, and nonlinear activation function, respectively. 2 0 = is initial feature of edge , which can be taken as the one-hot identity vector of the relation type that belongs to. 3 Relational context message passing in Eqs. (10) and (11) are repeated for times. The final message −1 ℎ and −1 are taken as the representation for head ℎ and tail , respectively. We also give an illustrative example of relational context message passing in Figure 2, where the red/pink edges denote the first-order/secondorder contextual relations.

Relational Paths
We follow the discussion in Section 2 and discuss how to model the term ( |ℎ, ) or (ℎ| , ). Note that we do not consider node/edge identity in relational context message passing, which leads to a potential issue that our model is not able to identify the relative position between ℎ and in the KG. For example, suppose for a given entity pair (ℎ, ), ℎ is surrounded by "person.birthplace", "person.gender", etc., and is surrounded by "institution.location", "university.founder", "university.president", etc. Then it can be inferred that ℎ is probably a person and is probably a university, and there should be a relation "graduated_from" between them because such a pattern appears frequently in the training data. However, the person may have no relationship with the university and they are far from each other in the KG. The reason why such false positive case happens is that relational context message passing can only detect the "type" of ℎ and , but is not aware of their relative position in the KG.
To solve this problem, we propose to explore the connectivity pattern between ℎ and , which are represented by the paths connecting them in the KG. Specifically, a raw path from ℎ to in a KG is a sequence of entities and edges: in which two entities and +1 are connected by edge , and each entity in the path is unique. 4 The corresponding relational path is the sequence of relation types of all edges in the given raw path, i.e., = 0 , 1 , ..., −1 , where is the relation type of edge . Note that we do not use the identity of nodes when modeling relational paths, which is the same as for relational context.
Denote P ℎ→ as the set of all relational paths from ℎ to in the KG. Our next step is to define and calculate the representation of relational paths. In PathCon, we assign an independent embedding vector for each relational path ∈ P ℎ→ . 5 A potential concern here is that the number of different paths increases exponentially with the path length (there are | | -hop paths), however, in practice we observe that in real-world KGs most paths actually do not occur (e.g., only 3.2% of all possible paths of length 2 occur in FB15K dataset), and the number of different paths is actually quite manageable for relatively small values of ( ≤ 4).
An illustrative example of relational paths is shown in Figure 2, where the two green arrows denote the relational paths from head entity ℎ to tail entity . 3 In cases where relation types have names, initial features can also be bag-of-words (BOW) or sentence embeddings learned by language models like BERT [7]. We shall investigate the performance of different initial feature types in experiments. 4 Entities in a path are required to be unique because a loop within a path does not provide additional semantics thus should be cut off from the path. 5 Other methods for calculating path representations are also possible. We shall discuss them in Section 3.6.

Combining Relational Context and Paths
For relational context, we use massage passing scheme to calculate the final message −1 ℎ and −1 for ℎ and , which summarizes their context information, respectively. −1 ℎ and −1 are further combined together for calculating the context of (ℎ, ) pair: where (ℎ, ) denotes the context representation of the entity pair (ℎ, ). Note here that Eq. (12) should only take messages of ℎ and as input without their connecting edge , since the ground truth relation should be treated unobserved in the training stage. For relational paths, note that there may be a number of relational paths for a given (ℎ, ) pair, but not all paths are logically related to the predicted relation , and the importance of each path also varies. In PathCon, since we have already known the context (ℎ, ) for (ℎ, ) pair and it can be seen as prior information for paths between ℎ and , we can calculate the importance scores of paths based on (ℎ, ) . Therefore, we first calculate the attention weight of each path with respect to the context (ℎ, ) : where P ℎ→ is the set of all paths from to . Then the attention weights are used to average representations of all paths: where ℎ→ is the aggregated representation of relational paths for (ℎ, ). In this way, the context information (ℎ, ) is used to assist in identifying the most important relational paths. Given the relational context representation (ℎ, ) and the relational path representation ℎ→ , we can predict relations by first adding the two representation together and then taking softmax as follows: ( |ℎ, ) = SoftMax (ℎ, ) + ℎ→ .
Our model can be trained by minimizing the loss between predictions and ground truths over the training triplets: where D is the training set and (·) is the cross-entropy loss. It is worth noticing that the context representation (ℎ, ) plays two roles in the model: It directly contributes to the predicted relation distribution, and it also helps determine the importance of relational paths with respect to the predicted relation.

Discussion on Model Explainability
Since PathCon only models relations without entities, it is able to capture pure relationship among different relation types thus can naturally be used to explain for predictions. The explainability of PathCon is two-fold: On the one hand, modeling relational context captures the correlation between contextual relations and the predicted relation, which can be used to indicate important neighbor edges for the given relation. For example, "institution.location", "university.founder", and "university.president" can be identified as important contextual relations for "graduated from".
On the other hand, modeling relational paths captures the correlation between paths and the predicted relation, which can indicate important relational paths for the given relation. For example, ("schoolmate of", "graduated from") can be identified as an important relational path for "graduated from".
It is interesting to see that the explainability provided by relational paths is also connected to first-logic logical rules with the following form: where is the conjunction of relations in a path and (ℎ, ) is the predicted relation. The above example of relational path can therefore be written as the following rule: (ℎ, schoolmate of, ) ∧ ( , graduated from, ) ⇒(ℎ, graduated from, ).

Design Alternatives
Next we discuss several design alternatives for PathCon. In our ablation experiments we will compare PathCon with the following alternative implementations.
When modeling relational context, we propose two alternatives for context aggregator, instead of the Concatenation context aggregator in Eqs. (11) and (12): Mean context aggregator. It takes the element-wise mean of the input vectors, followed by a nonlinear transformation function: The output of Mean context aggregator is invariant to the permutation of its two input nodes, indicating that it treats the head and the tail equally in a triplet.
Cross context aggregator. It is inspired by combinatorial features in recommender systems [31], which measure the interaction of unit features (e.g., AND(gender=female, language=English)). Note that Mean and Concatenation context aggregator simply transform messages from two input nodes separately and add them up together, without modeling the interaction between them that might be useful for link prediction. In Cross context aggregator, we first calculate all element-level pairwise interactions between messages from the head and the tail: where we use superscript with parentheses to indicate the element index and is the dimension of and . Then we summarize all interactions together via flattening the interaction matrix to a vector then multiplied by a transformation matrix: It is worth noting that Cross context aggregator preserves the order of input nodes.
Learning path representation with RNN. When modeling relational paths, recurrent neural network (RNN) can be used to learn the representation of relational path = ( 1 , 2 , ...): instead of directly assigning an embedding vector to . The advantage of RNN against path embedding is that its number of parameters is fixed and does not depend on the number of relational paths. Another potential benefit is that RNN can hopefully capture the similarity among different relational paths.
Mean path aggregator. When calculating the final representation of relational paths for (ℎ, ) pair, we can also simply average all the representations of paths from ℎ to instead of the Attention path aggregator in Eqs. (13) and (14): Mean path aggregator can be used in the case where representation of relational context is unavailable, since it does not require attention weights as input.

EXPERIMENTS
In this section, we evaluate the proposed PathCon model, and present its performance on six KG datasets.  [18]. WN18RR [6] is a subset of WN18 where inverse relations are removed. NELL995 [33] is extracted from the 995th iteration of the NELL system [5] containing general knowledge.

Experimental Setup
In addition, we present a new dataset DDB14 that is suitable for KG-related tasks. DDB14 is collected from Disease Database 6 , which is a medical database containing terminologies and concepts such as diseases, symptoms, drugs, as well as their relationships. We randomly sample two subsets of 4,000 triplets from the original one as validation set and test set, respectively.
The statistics of the six datasets are summarized in Table 2. We also calculate and present the mean and variance of node degree distribution (i.e.,  models are embedding-based methods, while DRUM only uses relational paths to make prediction. The implementation details of baselines (as well as our method) is provided in Appendix D.
We also conduct extensive ablation study and propose two reduced versions of our model, Con and Path, which only use relational context and relational paths, respectively, to test the performance of the two components separately.
The number of parameters of each model on DDB14 are shown in Table 3. The result demonstrates that PathCon is much more storage-efficient than embedding-based methods, since it does not need to calculate and store entity embeddings.  Evaluation Protocol. We evaluate all methods on relation prediction, i.e., for a given entity pair (ℎ, ) in the test set, we rank the ground-truth relation type against all other candidate relation types. It is worth noticing that most baselines are originally designed for head/tail prediction, therefore, their negative sampling strategy is to corrupt the head or the tail for a true triple (ℎ, , ), i.e., replacing ℎ or with a randomly sampled entity ℎ ′ or ′ from KGs, and using (ℎ ′ , , ) or (ℎ, , ′ ) as the negative sample. In relation prediction, since the task is to predict the missing relation for a given pair (ℎ, ), we modify the negative sampling strategy accordingly by corrupting the relation of each true triplet (ℎ, , ), and use (ℎ, ′ , ) as the negative sample where ′ is randomly sampled from the set of relation types. This new negative sampling strategy can indeed improve the performance of baselines in relation prediction. We use MRR (mean reciprocal rank) and Hit@1, 3 (hit ratio with cut-off values of 1 and 3) as evaluation metrics.

Main Results
Comparison with baselines. The results of relation prediction on all datasets are reported in Table 4. In general, our method outperforms all baselines on all datasets. Specifically, the absolute Hit@1 gain of PathCon against the best baseline in relation prediction task are 0.2%, 0.6%, 0.9%, 16.7%, 6.3%, and 1.8% in the six datasets, respectively. The improvement is rather significant for WN18RR and NELL995, which are exactly the two most sparse KGs according to the average node degree shown in Table 2. This empirically demonstrates that PathCon maintains great performance for sparse KGs, and this is probably because PathCon has much fewer parameters   than baselines and is less prone to overfitting. In contrast, performance gain of PathCon on FB15K is less significant, which may be because the density of FB15K is very high so that it is much easier for baselines to handle. In addition, the results also demonstrate the stability of PathCon as we observe that most of the standard deviations are quite small.
Results in Tables 4 also show that, in many cases Con or Path can already beat most baselines. Combining relational context and relational paths together usually leads to even better performance.
Inductive KG completion. We also examine the performance of our method in inductive KG completion. We randomly sample a subset of nodes that appears in the test set, then remove these nodes along with their associated edges from the training set. The remaining training set is used to train the models, and we add back the removed edges during evaluation. The evaluation transforms from fully conductive to fully inductive when the ratio of removed nodes increases from 0 to 1. The results of PathCon, DistMult, and RotatE on relation prediction task are plotted in Figure 3. We observe that the performance of our method decreases slightly in fully inductive setting (from 0.954 to 0.922), while DistMult and RotatE fall to a "randomly guessing" level. This is because the two baselines are embedding-based models that rely on modeling node identity, while our method does not consider node identity thus being naturally generalizable to inductive KG completion.

Model Variants
The number of context hops and maximum path length. We investigate the sensitivity of our model to the number of context hops and maximum path length. We vary the two numbers from 0 to 4 (0 means the corresponding module is not used), and report the results of all combinations (without (0, 0)) on WN18RR in Figure 4. It is clear to see that increasing the number of context hops and maximum path length can significantly improve the result when they are small, which demonstrates that including more neighbor edges or counting longer paths does benefit the performance. But the marginal benefit is diminishing with the increase of layer numbers. Similar trend is observed on other datasets too.
Context aggregators. We study how different implementations of context aggregator affect the model performance. The results of Mean, Concat, and Cross context aggregator on four datasets are shown in Figure 5 (results on FB15K and WN18 are omitted as they are similar to FB15K-237 and WN18RR, respectively). The results show that Mean performs worst on all datasets, which indicates the importance of node orders when aggregating features from nodes to edges. It is also interesting to notice that the performance comparison between Concat and Cross varies on different datasets: Concat is better than Cross on NELL995 and is worse than Cross on WN18RR, while their performance is on par on FB15K-237 and DDB14. However, note that a significant defect of Cross is that it has much more parameters than Concat, which requires more running time and memory resource.
Path representation types and path aggregators. We implement four combinations of path representation types and path aggregators: Embedding+Mean, Embedding+Attention, RNN+Mean, and RNN+Attention, of which the results are presented in Figure  6. Different from context aggregators, results on the six datasets are similar for path representation types and path aggregators, so we only report the results on WN18RR. We find that Embedding is consistently better than RNN, which is probably because the length of relational paths are generally short (no more than 4 in our experiments), so RNN can hardly demonstrate its strength in modeling sequences. The results also show that Attention aggregator performs slightly better than Mean aggregator. This demonstrates that the contextual information of head and tail entities indeed helps identify the importance of relational paths.
Initial edge features. Here we examine three types of initial edge features: identity, BOW, and BERT embedding of relation types. We choose to test on NELL995 because its relation names consist of relatively more English words thus are semantically meaningful (e.g., "organization.headquartered.in.state.or.province"). The results are reported in Figure 7, which shows that BOW features are slightly better than identity, but BERT embeddings perform significantly worse than the other two. We attribute this finding to that BERT embeddings are better at identifying semantic relationship among relation types, but our model aims to learn the mapping from BERT embeddings of context/paths to the identity of predicted relation types. In other words, BERT may perform better if the predicted relation types are also represented by BERT embeddings, so that this mapping is learned within the embedding space. We leave the exploration as future work.

Case Study on Model Explainabilty
We choose FB15K-237 and DDB14 as the datasets to show the explainability of PathCon. The number of context hops is set to 1 and the maximum path length is set to 2. When training is completed, we choose three relations from each dataset and list the most important relational context/paths to them based on the transformation matrix of the context/path aggregator. The results are presented in Table 5, from which we find that most of the identified context/paths are logically meaningful. For example, "education campus of" can be inferred by "education institution in", and "is associated with" is found to be a transitive relation. In addition, more visualized results and discussion on DDB14 dataset are included in Appendix E.

RELATED WORK 5.1 Knowledge Graph Completion
KGs provide external information for a variety of downstream tasks such as recommender systems [27][28][29] and semantic analysis [26]. Most existing methods of KG completion are based on embeddings, which normally assign an embedding vector to each entity and relation in the continuous embedding space and train the embeddings based on the observed facts. One line of KG embedding methods is translation-based, which treat entities as points in a continuous space and each relation translates the entity point. The objective is that the translated head entity should be close to the tail entity in real space [3], complex space [22], or quaternion space [39], which have shown capability to handle multiple relation patterns and achieve state-of-the-art result. Another line of work is multi-linear or bilinear models, where they calculate the semantic similarity by matrix or vector dot product in real [35] or complex space [24]. Besides, several embedding-based methods explore the architecture design that goes beyond point vectors [6,21]. However, these embedding-based models fail to predict links in inductive setting, neither can they discover any rules that explain the prediction.

Graph Neural Networks
Existing GNNs generally follow the idea of neural message passing [10] that consists of two procedures: propagation and aggregation. Under this framework, several GNNs are proposed that take inspiration from convolutional neural networks [8,11,15,25], recurrent neural networks [17], and recursive neural networks [1]. However, these methods use node-based message passing, while we propose passing messages based on edges in this work. There are two GNN models conceptually connected to our idea of identifying relative position of nodes in a graph. DEGNN [16] captures the distance between the node set whose representation is to be learned and each node in the graph, which is used as extra node attributes or as controllers of message aggregation in GNNs. SEAL [38] labels nodes with their distance to two nodes and when predicting link existence between ( , ). In contrast, we use relational paths to indicate the relative position of two nodes.
Researchers also tried to apply GNNs to knowledge graphs. For example, Schlichtkrull et al. [20] use GNNs to model the entities and relations in KGs, however, they are limited in that they did not consider the relational paths and cannot predict in inductive settings. Wang et al. [30,32] use GNNs to learn entity embeddings in KGs, but their purpose is to use the learned embeddings to enhance the performance of recommender systems rather than KG completion.

CONCLUSION AND FUTURE WORK
We propose PathCon for KG completion. PathCon considers two types of subgraph structure in KGs, i.e., contextual relations of the head/tail entity and relational paths between head and tail entity. We show that both relational context and relational paths are critical to relation prediction, and they can be combined further to achieve may cause may cause, belongs to the drug family of (is a risk factor for), (see also, may cause) is associated with is associated with, is a risk factor for (is associated with, is associated with) may be allelic with may be allelic with, belong(s) to the category of (may cause, may cause), (may be allelic with, may be allelic with) state-of-the-art performance. Moreover, PathCon is also shown to be inductive, storage-efficient, and explainable.
We point out four directions for future work. First, as we discussed in Remark 2, it is worth studying the empirical performance of PathCon on node-feature-aware KGs. Second, as we discussed in Section 4.3, designing a model that can better take advantage of pre-trained word embeddings is a promising direction; Third, it is worth investigating why RNN does not perform well, and whether we can model relational paths better; Last, it is interesting to study if the context representation and path representation can be assembled in a more principled way.

APPENDIX A Proof of Theorem 1
Proof. In each iteration of node-based message passing: The aggregation (Eq. (3)) is performed for times, and each aggregation takes E[ ] = 2 elements as input in expectation, where E[ ] is the expected node degree. Therefore, the expected cost of aggregation in each iteration is · E[ ] = 2 ; The update (Eq. (4)) is performed for times, and each update takes 2 elements as input. Therefore, the cost of update in each iteration is 2 .
In conclusion, the expected cost of node-based message passing in each iteration is 2 + 2 . □

B Proof of Theorem 2
For relational message passing, it actually passes messages on the line graph of the original graph. The line graph of a given graph G, denoted by (G), is a graph such that each node of (G) represents an edge of G, and two nodes of (G) are adjacent if and only if their corresponding edges share a common endpoint in G. We show by the following lemma that the line graph is much larger and denser than the original graph: Lemma 1. The number of nodes in line graph (G) is , and the expected node degree of (G) is where Var G [ ] is the variance of node degrees in G.
Proof. It is clear that the number of nodes in line graph (G) is because each node in (G) corresponds to an edge in G. We now prove that the expected node degree of (G) is E ( G) [ ] = ·Var G [ ] + 4 − 2.
Let's first count the number of edges in (G). According to the definition of line graph, each edge in (G) corresponds to an unordered pair of edges in G connecting to a same node; On the other hand, each unordered pair of edges in G that connect to a same node also determines an edge in (G). Therefore, the number of edges in (G) equals the number of all unordered pairs of edges connecting to a same node: where is the degree of node in G and = 2 is the number of edges. Then the the expected node degree of (G) is □ From Lemma 1 it is clear to see that E ( G) [ ] is at least twice of E G [ ] = 2 , i.e. the expected node degree of the original graph G, since Var G [ ] ≥ 0 (−2 is omitted). Unfortunately, in real-world graphs (including KGs), node degrees vary significantly, and they typically follow the power law distribution whose variance is extremely large due to the long tail (this is empirically justified in Table 2, as we can see that Var G [ ] is quite large for all KGs). This means that E ( G) [ ] ≫ E G [ ] in practice. On the other hand, the number of nodes in (G) (which is ) is also far larger than the number of nodes in G (which is ). Therefore, (G) is generally much larger and denser than its original graph G. Based on Lemma 1, Theorem 2 is proven as follows: Proof. In each iteration of relational message passing: The aggregation (Eq. (5) The update ((Eq. (6))) is performed for times, and each update takes 2 elements as input. Therefore, the cost of update in each iteration is 2 .
In conclusion, the expected cost of relational message passing in each iteration is · Var G [ ] + 4 2 . □

C Proof of Theorem 3
Proof. In each iteration of alternate relational message passing: The edge-to-node aggregation operation (Eq. (7)) is performed for times, and each aggregation takes E[ ] = 2 elements as input in expectation. Therefore, the expected cost of edge-to-node aggregation in each iteration is · E[ ] = 2 ; The node-to-edge aggregation (Eq. (8)) is performed for times, and each aggregation takes 2 elements as input. So the cost of node-to-edge aggregation in each iteration is 2 ; The update (Eq. (9)) is performed for times, and each update takes 2 elements as input. Therefore, the cost of update in each iteration is 2 .
In conclusion, the expected cost of alternate relational message passing in each iteration is 6 . □

D Implementation Details
Baselines. The implementation code of TransE, DistMult, Com-plEx, and RotatE comes from https://github.com/DeepGraphLearning/ KnowledgeGraphEmbedding; the implementation code of SimplE is at https://github.com/baharefatemi/SimplE; the implementation code of QuatE is at https://github.com/cheungdaven/QuatE, and we use QuatE 2 (QuatE without type constraints) here; the implementation code of DRUM is at https://github.com/alisadeghian/DRUM. For fair comparison, the embedding dimension for all the baselines are set to 400. We train each baseline for 1,000 epochs, and report the test result when the result on validation set is optimal.
Our method. Our proposed method is implemented in TensorFlow and trained on single GPU. We use Adam [14] as the optimizer with learning rate of 0.005. L2 regularization is used to prevent overfitting and the weight of L2 loss term is 10 −7 . Batch size is 128, the number of epochs is 20, and the dimension of all hidden