Source-linked AI summary
Relational Message Passing for Knowledge Graph Completion
Hongwei Wang, Hongyu Ren, Jure Leskovec
TL;DR
Knowledge graph completion must predict missing relations in incomplete and noisy graphs, while conventional message passing is poorly matched to relation-centric information. PathCon uses relational message passing over relation types, combining relational context and paths; it achieves strong completion performance and supports inductive, storage-efficient, explainable prediction. The paper also identifies computational efficiency and several modeling directions as boundaries for future work.
Problem
Knowledge graphs are incomplete and noisy, and traditional node-based message passing is not suitable when edge relation types are more important.
Method
PathCon uses alternate relational message passing over relation types, combining relational context around entity pairs with relational paths between them.
Results
PathCon achieves state-of-the-art knowledge graph completion performance while maintaining inductive capability and providing explanations through important relational contexts and paths.
Takeaways & Limitations
The framework avoids entity embeddings, making it inductive, storage-efficient, and explainable for relation prediction.
Takeaways & Limitations
The approach has higher computational complexity than node-based message passing and leaves node features, pretrained word embeddings, path modeling, and context-path integration for future work.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Knowledge graph completion addresses missing and noisy links by predicting relations between entity pairs. PathCon uses relational message passing over relation types to combine relational context and paths, achieving strong benchmark performance while supporting inductive and explainable prediction.
- Knowledge graphs are often incomplete and noisy, motivating methods that predict missing links or relations.
- Relation types are spatially correlated, so neighboring relations around an entity pair provide information for predicting their connecting relation.
- PathCon passes messages directly between neighboring edges using relation types rather than entity identities.
- PathCon models both relational context around the entities and relational paths between them.The model combines these two topology types for relation prediction.
- PathCon significantly outperforms state-of-the-art knowledge graph completion methods, including absolute Hit@1 gains of 16.7% on WN18RR and 6.3% on NELL995.
- The framework is inductive and explainable, and the work introduces DDB14 as a new dataset for knowledge graph research.
2 PROBLEM FORMULATION
The paper formulates knowledge graph completion as predicting a relation distribution for an entity pair. Its probabilistic decomposition motivates representing entities through relational context and modeling how relational paths connect the pair.
- Given an entity pair, the task is to predict the distribution over relation types for the missing edge.
- Bayes’ theorem decomposes relation prediction using a prior over relation types and conditional terms involving the entities and relation.
- Because the model omits entity identities, it represents each entity with its local relational subgraph, called relational context.
- Relation prediction and missing-entity prediction are equivalent formulations, but this work focuses on relation prediction.
- The conditional reachability terms motivate modeling relational paths between the head and tail entities.
3 OUR APPROACH
The approach replaces node-based message passing with an edge-focused framework that models relational context and paths while addressing computational overhead. PathCon uses these relational signals for prediction, explanation, and logical-rule learning.
- Relational Message Passing Framework: Knowledge graphs provide relation types on edges but generally lack node features, making node-based message passing less natural and identity-based representations problematic.The proposed framework instead performs message passing over relational edge features.
- Alternate Relational Message Passing: N·Var[d] + 4M^2/N is the expected per-iteration cost of relational message passing, which becomes expensive for power-law graphs with high degree variance.This motivates an alternate scheme that reduces redundant computation.
- Alternate Relational Message Passing: 6M is the expected per-iteration cost of alternate relational message passing, matching the order of node-based message passing.The method aggregates edge messages at nodes, propagates them back to edges, and updates edge states.
- Relational Context and Paths: Relational context uses neighboring relation types to characterize an entity pair, while relational paths capture the pair’s connectivity pattern.PathCon combines these complementary topologies for relation prediction.
- Model Explainability: PathCon identifies important contextual relations and paths for predictions, and its path explanations can express logical rules over relations.Examples include contextual relations such as institution.location and paths such as (“schoolmate of”, “graduated from”).
4 EXPERIMENTS
Experiments evaluate PathCon across six datasets, baselines, inductive completion, ablations, and design choices. PathCon generally outperforms competing methods, with especially large gains on sparse graphs, while relational context and paths complement each other.
- Experimental Setup: PathCon is evaluated on five standard benchmarks and the newly proposed DDB14 dataset using MRR and Hit@1,3.The baselines include embedding-based methods and DRUM, which uses relational paths.
- Experimental Setup: PathCon is much more storage-efficient than embedding-based methods because it does not calculate or store entity embeddings.The parameter comparison is reported on DDB14.
- Main Results: PathCon improves absolute Hit@1 over the best baseline by 0.2%, 0.6%, 0.9%, 16.7%, 6.3%, and 1.8% across the six datasets.The largest gains occur on WN18RR and NELL995, identified as the two sparsest knowledge graphs.
- Model Variants: Combining relational context and relational paths usually performs better than using either Con or Path alone.The ablations show that each component can already outperform many baselines in several cases.
- Model Variants: Increasing context hops and maximum path length improves results when these values are small, showing benefits from additional neighboring edges and longer paths.The sensitivity study varies both quantities from 0 to 4 on WN18RR.
- Model Variants: BOW relation features slightly outperform identity features on NELL995, whereas BERT embeddings perform significantly worse.The authors leave matching BERT-based predicted-relation representations for future work.
5 RELATED WORK
Related work includes embedding-based knowledge graph completion and graph neural networks. PathCon differs by passing messages over relation-bearing edges and modeling relational paths for prediction.
- Knowledge Graph Embeddings: Knowledge graph completion commonly uses translation-based or multilinear and bilinear embedding models for entities and relations.These approaches represent entities and relations in continuous spaces and learn from observed facts.
- Graph Neural Networks: Existing graph neural networks generally use node-based propagation and aggregation, whereas PathCon passes messages based on edges.This distinction reflects the greater importance of relation types than node features in the targeted knowledge graphs.
- Knowledge Graph GNNs: Prior knowledge-graph GNNs either omit relational paths and inductive prediction or learn entity embeddings for recommendation rather than knowledge graph completion.PathCon is positioned as addressing these differences within KG completion.
6 CONCLUSION AND FUTURE WORK
PathCon combines relational context and relational paths for knowledge graph completion, with both structures reported as critical to relation prediction. The paper also identifies future work on node features, pretrained embeddings, relational paths, and combining representations.
- PathCon combines contextual relations around head/tail entities with relational paths between them for knowledge graph completion.
- Both relational context and relational paths are reported as critical to relation prediction.
- Future work includes evaluating PathCon on node-feature-aware knowledge graphs and better using pretrained word embeddings.
- Further directions include explaining RNN performance, improving relational-path modeling, and combining context and path representations more systematically.
A Proof of Theorem 1
The proof derives the expected per-iteration cost of node-based message passing by separately accounting for aggregation and update operations.
- 2M is the expected aggregation cost per iteration for node-based message passing.
- 2N is the update cost per iteration because each of N updates takes two input elements.
- 2M + 2N is the expected total cost of node-based message passing in each iteration.
B Proof of Theorem 2
The proof analyzes relational message passing through the line graph, showing that its size and density can greatly exceed those of the original graph.
- The line graph has M nodes, with each node representing an edge of the original graph.
- The expected degree of the line graph depends on node-degree variance in the original graph.
- The line graph’s expected degree is at least twice the original graph’s expected degree.
- In real-world knowledge graphs, high degree variance and M far exceeding N make the line graph generally much larger and denser.
- N·Var_G[d] + 4M^2 is the expected per-iteration cost of relational message passing.
C Proof of Theorem 3
The proof computes alternate relational message passing cost by summing edge-to-node aggregation, node-to-edge aggregation, and update operations.
- 2M is the expected edge-to-node aggregation cost per iteration.
- 2M is the node-to-edge aggregation cost because M aggregations each take two input elements.
- 2M is the update cost because M updates each take two input elements.
- 6M is the expected total cost of alternate relational message passing in each iteration.
D Implementation Details
The experiments use fixed training settings for PathCon while tuning context hops and maximum path length separately for each dataset.
- Training setup: PathCon is implemented in TensorFlow and trained on a single GPU with Adam, learning rate 0.005, batch size 128, and 20 epochs.The method uses L2 regularization with loss-term weight 10^-7.
- Features and selection: Initial relation features are identity features, while BOW and BERT features are evaluated separately in Section 4.3.The fixed settings were selected using validation classification accuracy on WN18RR and retained across datasets.
- Dataset-specific tuning: The number of context hops and maximum path length are tuned separately for each dataset because their performance depends on the dataset.Default settings are reported in Table 6.
- Search and evaluation: The hyperparameter search covers hidden dimensions 8–64, L2 weights 10^-8–10^-5, learning rates 0.001–0.1, context hops 1–4, and path lengths 1–4.Each PathCon experiment is repeated three times, with mean performance and standard deviation reported.
E More Results of Explainability on DDB14
On DDB14, PathCon’s learned context and path aggregators reveal interpretable correlations between observed relational patterns and predicted relations. The learned patterns include contextual type compatibility, equivalence-like rules, transitivity, and subtype relations.
- Correlation visualizations: The heat maps encode correlation strength between contextual relations or relational paths and predicted relations.Darker entries indicate stronger correlations; Figure 9 shows context correlations and Figure 8 shows path correlations.
- Relational context: Context correlations are mostly diagonal, indicating that an entity’s observed relation type is often associated with predicting the same relation type.For example, an entity observed as a risk factor is more likely to be predicted as a risk factor than as belonging to a drug family.
- Relational context: Some off-diagonal context correlations capture related relation types, including drug-family to drug-super-family and contraindication to interaction.These associations extend beyond exact relation-type matching.
- Relational paths: PathCon learns equivalence-like relational patterns in which a relation such as “see also” supports interchangeability between entities.The passage describes “see also” as indicating that the two entities are equivalent.
- Relational paths: PathCon also learns transitive rules, such as two successive “may be allelic with” relations implying the same relation between the endpoints.This provides an interpretable path-based explanation for the predicted relation.
- Relational paths: Another learned rule maps belonging to a category onto being a subtype of that category.This is presented as an additional interpretable rule learned by PathCon.
- Relational paths: Two additional DDB14 rules infer “may be allelic with” from shared “may cause” or shared risk-factor relations.Both rules connect relations involving a common third entity to the predicted relation between the first two entities.