Research Project

GraphOracle

Efficient Fully-Inductive Knowledge Graph Reasoning via Relation-Dependency Graphs

AAAI 2026 Oral
Enjun Du1,2, Siyi Liu1, Yongqi Zhang1*
1HKUST(GZ)    2Beijing Institute of Technology
Affiliation logoAffiliation logo
Paper arXiv Code Dataset Video Slides Poster
GraphOracle overview
Figure 1: Overview of GraphOracle — construct a Relation-Dependency Graph (RDG) from the KG, propagate messages via multi-head attention, then score candidate entities for answer prediction.
60 benchmarks Four reasoning settings Transductive, entity-inductive, fully-inductive, and cross-domain evaluation.
+26.82% Cross-domain MRR improvement Directed relation dependencies transfer effectively to unseen domains.
Directed RDG Sparse relational structure Precedence edges encode compositional patterns that undirected graphs miss.

Abstract

Knowledge-graph reasoners often struggle when test-time entities and relations were never observed during training. GraphOracle addresses this fully-inductive setting by converting each knowledge graph into a directed Relation-Dependency Graph (RDG). The RDG captures how relations compose, and its query-aware embeddings guide answer prediction on the original entity graph.

Motivation

Relation order matters: “born in → located in” carries a compositional direction that an undirected relation graph erases.

Existing fully-inductive methods construct dense, undirected relation graphs. This makes computation expensive and loses directional dependencies that are essential for multi-hop reasoning. The same limitation makes it difficult to transfer a learned reasoner across domains with different entity and relation vocabularies.

Method

Framework

GraphOracle operates in three stages:

  • RDG Construction — Transform the KG into a directed Relation-Dependency Graph where edge (r_i, r_j) indicates that relation r_i precedes r_j in observed triple chains. This is significantly sparser than prior relation graphs while capturing compositional patterns.
  • Query-Dependent Multi-Head Attention — For each query relation, a multi-head attention GNN propagates messages over the RDG to produce context-aware relation embeddings. The same relation gets different representations depending on the query context.
  • Entity-Level Answer Prediction — The learned relation embeddings parameterize a second GNN on the original KG entity graph, performing inductive message passing from the query entity to score candidates.

Experimental Results

Evaluated across 60 benchmarks spanning transductive, entity-inductive, fully-inductive, and cross-domain settings.

MRR Comparison on 60 Datasets

MRR Comparison

GraphOracle (red) consistently matches or outperforms supervised SOTA (green) across all 60 datasets, with particularly strong gains on cross-domain and biomedical KGs.

Average Performance (4 Settings)

Main Results

GraphOracle achieves +7.19% MRR improvement in transductive, +10.86% in entity-inductive, +13.28% in fully-inductive, and +26.82% in cross-domain settings over supervised SOTA.

Ablation Study

Ablation

Removing the RDG structure or multi-head attention causes significant performance drops, confirming both components are essential. The directed precedence encoding is the single most important design choice.

Presentation

Citation

@inproceedings{du2026graphoracle,
  title     = {GraphOracle: Efficient Fully-Inductive Knowledge Graph
               Reasoning via Relation-Dependency Graphs},
  author    = {Du, Enjun and Liu, Siyi and Zhang, Yongqi},
  booktitle = {Proceedings of the AAAI Conference on Artificial
               Intelligence (AAAI)},
  year      = {2026},
  note      = {Oral Presentation}
}