# Knowledge Graph Reasoning with Relational Digraph

arXiv: https://arxiv.org/abs/2108.06040 · HTML: https://mlsanity.com/paper/2108.06040/

## Key facts

- Cited by 92 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 58 references that are in the map.
- First posted on arXiv 13 Aug 2021.

## Builds on (most cited first, 30 of 37)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space](https://mlsanity.com/paper/1902.10197/) (2019)
- [Convolutional 2D Knowledge Graph Embeddings](https://mlsanity.com/paper/1707.01476/) (2017)
- [A Survey on Knowledge Graphs: Representation, Acquisition and Applications](https://mlsanity.com/paper/2002.00388/) (2020)
- [Knowledge Graphs](https://mlsanity.com/paper/2003.02320/) (2020)
- [Composition-based Multi-Relational Graph Convolutional Networks](https://mlsanity.com/paper/1911.03082/) (2019)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning](https://mlsanity.com/paper/1707.06690/) (2017)
- [Inductive Relation Prediction by Subgraph Reasoning](https://mlsanity.com/paper/1911.06962/) (2019)
- [Quaternion Knowledge Graph Embeddings](https://mlsanity.com/paper/1904.10281/) (2019)
- [DRUM: End-To-End Differentiable Rule Mining On Knowledge Graphs](https://mlsanity.com/paper/1911.00055/) (2019)
- [Variational Reasoning for Question Answering with Knowledge Graph](https://mlsanity.com/paper/1709.04071/) (2017)
- [Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning](https://mlsanity.com/paper/1711.05851/) (2017)
- [Canonical Tensor Decomposition for Knowledge Base Completion](https://mlsanity.com/paper/1806.07297/) (2018)
- [RNNLogic: Learning Logic Rules for Reasoning on Knowledge Graphs](https://mlsanity.com/paper/2010.04029/) (2020)
- [Unifying Knowledge Graph Learning and Recommendation: Towards a Better Understanding of User Preferences](https://mlsanity.com/paper/1902.06236/) (2019)
- [Inductive Matrix Completion Based on Graph Neural Networks](https://mlsanity.com/paper/1904.12058/) (2019)
- [Knowledge Graph Embedding for Link Prediction: A Comparative Analysis](https://mlsanity.com/paper/2002.00819/) (2020)
- [Knowledge Graph Completion via Complex Tensor Factorization](https://mlsanity.com/paper/1702.06879/) (2017)
- [A Re-evaluation of Knowledge Graph Completion Methods](https://mlsanity.com/paper/1911.03903/) (2019)
- [Probabilistic Logic Neural Networks for Reasoning](https://mlsanity.com/paper/1906.08495/) (2019)
- [Relational Message Passing for Knowledge Graph Completion](https://mlsanity.com/paper/2002.06757/) (2020)

## Built on by (most cited first, 30 of 92)

- [A Survey of Knowledge Graph Reasoning on Graph Types: Static, Dynamic, and Multimodal](https://mlsanity.com/paper/2212.05767/) (2022)
- [Towards Foundation Models for Knowledge Graph Reasoning](https://mlsanity.com/paper/2310.04562/) (2023)
- [InGram: Inductive Knowledge Graph Embedding via Relation Graphs](https://mlsanity.com/paper/2305.19987/) (2023)
- [A*Net: A Scalable Path-based Reasoning Approach for Knowledge Graphs](https://mlsanity.com/paper/2206.04798/) (2022)
- [AdaProp: Learning Adaptive Propagation for Graph Neural Network based Knowledge Graph Reasoning](https://mlsanity.com/paper/2205.15319/) (2022)
- [Weisfeiler and Leman Go Relational](https://mlsanity.com/paper/2211.17113/) (2022)
- [A Prompt-Based Knowledge Graph Foundation Model for Universal In-Context Reasoning](https://mlsanity.com/paper/2410.12288/) (2024)
- [A Multi-Task Perspective for Link Prediction with New Relation Types and Nodes](https://mlsanity.com/paper/2307.06046/) (2023)
- [Over-Squashing in Graph Neural Networks: A Comprehensive survey](https://mlsanity.com/paper/2308.15568/) (2023)
- [How Expressive are Knowledge Graph Foundation Models?](https://mlsanity.com/paper/2502.13339/) (2025)
- [Designing the Topology of Graph Neural Networks: A Novel Feature Fusion Perspective](https://mlsanity.com/paper/2112.14531/) (2021)
- [Geodesic Graph Neural Network for Efficient Graph Representation Learning](https://mlsanity.com/paper/2210.02636/) (2022)
- [GraphMaster: Automated Graph Synthesis via LLM Agents in Data-Limited Environments](https://mlsanity.com/paper/2504.00711/) (2025)
- [MKGL: Mastery of a Three-Word Language](https://mlsanity.com/paper/2410.07526/) (2024)
- [Generalizing to Unseen Elements: A Survey on Knowledge Extrapolation for Knowledge Graphs](https://mlsanity.com/paper/2302.01859/) (2023)
- [A Foundation Model for Zero-shot Logical Query Reasoning](https://mlsanity.com/paper/2404.07198/) (2024)
- [KRACL: Contrastive Learning with Graph Context Modeling for Sparse Knowledge Graph Completion](https://mlsanity.com/paper/2208.07622/) (2022)
- [TripleRE: Knowledge Graph Embeddings via Tripled Relation Vectors](https://mlsanity.com/paper/2209.08271/) (2022)
- [SARF: Aliasing Relation Assisted Self-Supervised Learning for Few-shot Relation Reasoning](https://mlsanity.com/paper/2304.10297/) (2023)
- [Link Prediction with Relational Hypergraphs](https://mlsanity.com/paper/2402.04062/) (2024)
- [A Unified Temporal Knowledge Graph Reasoning Model Towards Interpolation and Extrapolation](https://mlsanity.com/paper/2405.18106/) (2024)
- [Flock: A Knowledge Graph Foundation Model via Learning on Random Walks](https://mlsanity.com/paper/2510.01510/) (2025)
- [KGTuner: Efficient Hyper-parameter Search for Knowledge Graph Learning](https://mlsanity.com/paper/2205.02460/) (2022)
- [Understanding Expressivity of GNN in Rule Learning](https://mlsanity.com/paper/2303.12306/) (2023)
- [GraphOracle: Efficient Fully-Inductive Knowledge Graph Reasoning via Relation-Dependency Graphs](https://mlsanity.com/paper/2505.11125/) (2025)
- [HYPER: A Foundation Model for Inductive Link Prediction with Knowledge Hypergraphs](https://mlsanity.com/paper/2506.12362/) (2025)
- [Are Message Passing Neural Networks Really Helpful for Knowledge Graph Completion?](https://mlsanity.com/paper/2205.10652/) (2022)
- [A Survey On Few-shot Knowledge Graph Completion with Structural and Commonsense Knowledge](https://mlsanity.com/paper/2301.01172/) (2023)
- [Towards Graph Foundation Models: Training on Knowledge Graphs Enables Transferability to General Graphs](https://mlsanity.com/paper/2410.12609/) (2024)
- [ASGEA: Exploiting Logic Rules from Align-Subgraphs for Entity Alignment](https://mlsanity.com/paper/2402.11000/) (2024)

## Abstract (arXiv)

Reasoning on the knowledge graph (KG) aims to infer new facts from existing ones. Methods based on the relational path have shown strong, interpretable, and transferable reasoning ability. However, paths are naturally limited in capturing local evidence in graphs. In this paper, we introduce a novel relational structure, i.e., relational directed graph (r-digraph), which is composed of overlapped relational paths, to capture the KG's local evidence. Since the r- digraphs are more complex than paths, how to efficiently construct and effectively learn from them are challenging. Directly encoding the r-digraphs cannot scale well and capturing query-dependent information is hard in r-digraphs. We propose a variant of graph neural network, i.e., RED-GNN, to address the above challenges. Specifically, RED-GNN makes use of dynamic programming to recursively encodes multiple r-digraphs with shared edges, and utilizes a query-dependent attention mechanism to select the strongly correlated edges. We demonstrate that RED-GNN is not only efficient but also can achieve significant performance gains in both inductive and transductive reasoning tasks over existing methods. Besides, the learned attention weights in RED-GNN can exhibit interpretable evidence for KG reasoning.