PaperlayerView exact revision on arXiv

Source-linked AI summary

Knowledge Graph Reasoning with Relational Digraph

Yongqi Zhang, Quanming Yao

arXiv:2108.06040v2cs.AIcs.CL

TL;DR

KG reasoning must infer missing facts while capturing local evidence beyond sequential paths. The paper introduces r-digraphs and RED-GNN, which uses shared-edge recursive encoding and query-dependent attention; it reports state-of-the-art inductive and transductive performance with efficient reasoning and interpretable structures.

  • Problem

    Relational paths provide interpretable and transferable reasoning but are limited in capturing complex local dependencies, while existing subgraph methods lack efficient, interpretable, and inductive structure learning.

  • Method

    RED-GNN represents local evidence with r-digraphs and uses dynamic programming to recursively encode shared edges with query-dependent attention.

  • Results

    RED-GNN achieves state-of-the-art performance on inductive and transductive KG reasoning benchmarks while maintaining efficient training and inference.

  • Takeaways & Limitations

    RED-GNN learns interpretable structures for KG reasoning and supports efficient reasoning over the evaluated inductive and transductive benchmarks.

  • Takeaways & Limitations

    Applying RED-GNN to extremely large-scale KGs remains future work, with pruning or distributed programming proposed as possible directions.

Abstract

from arXiv · show

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.

1 INTRODUCTION

KG reasoning infers missing facts, but existing triple- and path-based approaches have difficulty capturing complex local evidence or scaling to large graphs. The paper introduces r-digraphs and RED-GNN to combine richer structure with efficient, query-dependent reasoning.

  • Motivation: KG reasoning predicts missing facts from existing triples for queries of the form (subject entity, relation, ?).KG facts use the form (subject entity, relation, object entity), and reasoning supports applications including semantic search, recommendation, and question answering.
  • Motivation: Triple-based models learn entities and relations independently, so they cannot explicitly capture local structures around query triples.These local structures provide evidence for KG reasoning.
  • Existing methods: Relational paths capture sequential local evidence but can be difficult to train or expensive to enumerate on large or entity-query tasks.RL path methods face sparse rewards and large-scale training difficulty, while PathCon samples all connecting paths.
  • Existing methods: Subgraphs can preserve richer local evidence, yet enclosing-subgraph approaches suffer from effectiveness and efficiency problems.The limitation of the enclosing subgraph creates both concerns.
  • Proposed approach: RED-GNN introduces r-digraphs and recursively encodes shared edges with dynamic programming while selecting query-correlated edges through attention.The method is reported to achieve gains in inductive and transductive reasoning, with efficient training and inference and interpretable learned structures.

2 RELATED WORKS

Prior KG reasoning methods use relational paths, logical rules, or GNN-based subgraphs to model local evidence. Their trade-offs involve sequential expressiveness, computational cost, query dependence, interpretability, and inductive generalization.

  • Task formulation: KG reasoning predicts a missing answer entity for a query (e_q, r_q, ?), with all entities treated as candidate answers.The KG consists of entities, relations, and fact triples.
  • Path-based methods: Relational paths are sequentially connected triples used as local evidence, but path sampling can face sparse rewards or high computational cost.DeepPath, MINERVA, and M-walk use reinforcement learning, whereas PathCon samples all connecting paths.
  • Path-based methods: Rule-based methods generalize paths as logical relation compositions, providing interpretation and transfer to unseen entities but missing more complex subgraph patterns.The cited methods learn rules through mining, EM, or end-to-end training.
  • GNN-based methods: GNN-based methods aggregate entity and relation information over graph neighborhoods to model subgraph structures.R-GCN, CompGCN, and KE-GCN use message passing over KG edges.
  • GNN-based methods: Query-independent neighborhood aggregation cannot capture explicit local evidence for specific queries or provide interpretable reasoning.This limitation is stated for R-GCN and CompGCN.
  • GNN-based methods: GraIL uses query-dependent attention over enclosing-subgraph edges, but its attention weights are not interpretable and subgraph extraction adds cost.DPMPN provides interpretable attention flow but depends on embeddings and therefore cannot generalize to unseen entities.

3 RELATIONAL DIGRAPH (R-DIGRAPH)

The paper defines r-digraphs as layered structures that preserve relational paths and subgraph connectivity between query and answer entities. This representation targets the gap between path interpretability and subgraph expressiveness.

  • Motivation: Existing paths are interpretable and transferable but limited to sequential dependencies, while GNNs learn subgraphs without efficiently combining interpretability and inductive reasoning.This motivates a new structure for important local evidence.
  • Definition: A layered st-graph has one source and one sink, with edges directed between consecutive layers.All edges point from layer l to layer l+1.
  • Construction: After adding reverse and identity relations, all relational paths of length at most L between e_q and e_a form a layered st-graph preserving paths and subgraph structure.The source is e_q and the sink is e_a.
  • Definition: An r-digraph is a layered st-graph whose source and sink are the query and answer entities, with same-layer entities distinct.Every source-to-sink path is a length-L relational path, and the r-digraph is empty when no such path exists.
  • Motivation: R-digraphs generalize relational paths to subgraphs by preserving overlapping paths and relation structure, but their construction and learning are challenging.The paper illustrates an r-digraph for inferring (Sam, directed, Spider-2).

4 THE PROPOSED MODEL

RED-GNN efficiently encodes multiple r-digraphs by recursively reusing shared edges, while query-dependent attention selects relevant edges for reasoning and interpretable evidence.

  • R-digraph encoding: Subgraph encoding extracts neighborhoods around both query and answer entities, intersects them to construct an r-digraph, then applies layer-wise message passing.If the r-digraph is empty, its representation is set to 0; otherwise, the final sink representation encodes the structure.
  • Recursive r-digraph encoding: RED-GNN recursively constructs multiple r-digraph representations by reusing query-side edges shared across different answer entities.This dynamic-programming approach reduces repeated computation while preserving the structures encoded by single-r-digraph processing.
  • Recursive r-digraph encoding: Proposition 2 guarantees that recursive encoding and single-r-digraph encoding produce identical structures for the same query triple.The guarantee supports replacing the expensive single-r-digraph procedure with RED-GNN’s recursive computation.
  • Query-dependent attention: Query-dependent attention incorporates the query relation into edge weights, allowing multiple strongly relevant edges in one neighborhood through sigmoid attention.The resulting sink representation is used to score candidate triples, with parameters optimized using multi-class log-loss.
  • Interpretable reasoning: Theorem 1 states that relational paths strongly correlated with a query triple can be identified through RED-GNN attention weights, making the reasoning evidence interpretable.The theorem connects selected attention-weighted edges with interpretable relational-path evidence.
  • Inference complexity: RED-GNN has inference complexity comparable to CompGCN and lower than DPMPN, RED-Simp, and GraIL under the stated comparison.The comparison is RED-GNN ≈ CompGCN < DPMPN < RED-Simp < GraIL.

5 EXPERIMENTS

Experiments evaluate RED-GNN in inductive and transductive reasoning, comparing performance, efficiency, learned structures, variants, and distance-dependent behavior. Across these analyses, RED-GNN is reported as accurate, efficient, and capable of producing interpretable relational evidence.

  • Reasoning performance: RED-GNN outperforms all baselines by MRR in transductive reasoning and transfers to unseen entities without entity embeddings.The results also report that it captures important patterns in incomplete knowledge graphs.
  • Complexity analysis: RED-GNN is more efficient than Neural LP, DRUM, and GraIL in inductive reasoning, while using fewer parameters than Neural LP and DRUM.GraIL requires bidirectional subgraph sampling and is described as especially expensive.
  • Complexity analysis: In transductive inference complexity, RED-GNN is approximately comparable to CompGCN, cheaper than DPMPN and RED-Simp, and far cheaper than GraIL.GraIL is reported as hundreds of times more expensive than RED-GNN and intractable on larger knowledge graphs.
  • Case study: learned r-digraphs: Learned r-digraphs provide local structural evidence, including a family relationship needed to infer a son relation that DRUM fails to predict.Attention filtering removes edges with weights below 0.5, and different query relations can yield distinctive learned structures.
  • Ablation study: Removing the query relation from attention produces less informative structures and poor performance, while removing edge relations causes a dramatic performance drop.These variants indicate that query-dependent attention and relational dependencies are important components of RED-GNN.
  • Ablation study: RED-GNN has the best per-distance performance within distance 5, although all compared models perform worse on triples at larger distances.The analysis groups MRR by shortest-path distance and evaluates CompGCN with L=2, DPMPN with L=5, and RED-GNN with L=5.

6 CONCLUSION

The paper introduces r-digraphs and RED-GNN to efficiently learn query-relevant relational structures for KG reasoning. RED-GNN achieves state-of-the-art performance across inductive and transductive benchmarks while supporting interpretable reasoning structures.

  • 6 CONCLUSION: RED-GNN uses dynamic programming to efficiently construct and learn r-digraphs for the query (e_q,r_q,?).The method recursively shares computation across overlapping subproblems.
  • 6 CONCLUSION: RED-GNN achieves state-of-the-art performance on both inductive and transductive KG reasoning benchmarks.The conclusion reports this as the paper’s main empirical outcome.
  • 6 CONCLUSION: RED-GNN’s training and inference are more efficient than the other GNN-based baselines.The paper also reports interpretable structures learned for reasoning.
  • 6 CONCLUSION: Applying RED-GNN to extremely large KGs remains future work involving pruning or distributed programming.The discussion identifies these techniques as possible ways to address scale.

A VISUALIZATION

RED-GNN visualizes query-specific r-digraph structures by backtracking edges with attention above a threshold. Additional Family visualizations show consistent and semantically friendly patterns across query triples.

  • A VISUALIZATION: The visualization procedure backtracks neighborhood edges of the answer entity whose attention exceeds a predefined threshold θ.The remaining edges form the structure selected by the attention weights.
  • A VISUALIZATION: Algorithm 3 requires entities, triples, a query triple, depth L, model parameters, and threshold θ.It first obtains layer-wise attention weights before backtracking from the answer entity.
  • A VISUALIZATION: The paper provides additional visualized r-digraph results for the Family and UMLS datasets.The supplied figure caption identifies Family, while the accompanying text also mentions UMLS.
  • A VISUALIZATION: The visualized structures exhibit consistent and semantically friendly patterns across different query triples.This is the stated qualitative observation for the additional results.

B PROBLEM ANALYSIS ON GRAIL

The analysis contrasts GraIL’s enclosing subgraph with RED-GNN’s r-digraph, emphasizing relational-order preservation, interpretability, and computational cost. Ablations further indicate that GraIL is relatively insensitive to relation information, whereas RED-GNN relies strongly on it.

  • Enclosing subgraph v.s. r-digraph: Enclosing subgraphs preserve bidirectional paths between query and answer entities, whereas r-digraphs preserve layered relational structure.The enclosing-subgraph construction includes paths in both directions, while r-digraph layers implicitly encode distance and relation order.
  • Enclosing subgraph v.s. r-digraph: GraIL’s enclosing subgraph mixes relation order and therefore provides limited inductive bias for KG reasoning.The analysis gives brother∧mother→uncle versus mother∧brother→aunt as an example of the ordering issue.
  • Non-interpretable: GraIL’s computation graph does not provide an interpretable account of how attention weights cooperate across layers.The comparison is illustrated by the GraIL and RED-GNN computation graphs in Figure 7.
  • Empirical evidence: Removing relation information causes only marginal performance decay for GraIL, leading the authors to conclude that it mainly learns graph structure.Table 6 reports the comparison using MRR.
  • Empirical evidence: Removing relation information causes a dramatic performance drop for RED-GNN, indicating that relational dependencies in edges serve as its reasoning evidence.The variant is called RED-no rel.

C.1 Proposition 1

The proposition characterizes the layer-wise edge set around a query entity through the union of edges appearing in relational paths to candidate answers.

  • C.1 Proposition 1: Edges reachable in ℓ steps from the query entity are contained in the union of ℓ-th-layer edges across answer entities.The supplied proof argues that an edge visited at distance ℓ must occur in the ℓ-th triple of some relational path to an answer.

C.2 Proposition 2

Proposition 2 proves by induction that Algorithms 1 and 2 learn identical representations at every layer and for the answer entity.

  • C.2 Proposition 2: When G_{e_q,r_q|L}=∅, both algorithms assign h^L_{e_a}(e_q,r_q)=0.
  • C.2 Proposition 2: The induction starts at layer 1, assumes equality at layer ℓ−1, and establishes equality at layer ℓ.
  • C.2 Proposition 2: Algorithms 1 and 2 produce identical representations for every layer ℓ=1...L and entity e∈V_ℓ.The proof handles the empty and nonempty query-reachable subgraph cases.

C.3 Theorem 1

Theorem 1 shows that a relational-path set can be extracted as a subgraph of the query-specific r-digraph through recursively learned attention weights.

  • C.3 Theorem 1: Any set P of relational paths is contained in the r-digraph G_{e_q,e_a|L} constructed from those paths.The proof denotes the r-digraph constructed by P as G_P.
  • C.3 Theorem 1: The L-th layer of G_P can be extracted because learned parameters define a decision boundary separating its target triples from remaining triples.
  • C.3 Theorem 1: Independent parameters at adjacent layers allow the L−1-th layer to be extracted similarly.
  • C.3 Theorem 1: Recursive execution extracts G_P from the query-specific r-digraph using attention weights α^ℓ.
Loading 2108.06040v2…