Knowledge Graph Reasoning with Relational Digraph

In plain words

A knowledge graph stores facts as triples, such as (Sam, directed, Spider-2). To answer a question like "what does Sam direct?", one simple method follows chains of relations from the entity you start with. Such chains are easy to read, but they miss the wider local picture, because many chains overlap and the way they overlap carries information.

This paper groups the overlapping chains that start at the query entity into one small layered graph, which it calls an r-digraph. Building and scoring each candidate answer's graph on its own is slow. RED-GNN instead walks outward from the query entity once per layer, reuses the work that overlapping graphs share, and lets the query's relation decide which edges matter, through attention. It outputs one score per candidate entity, and the attention weights can be read as the edges the score relied on.

TL;DR

RED-GNN scores every candidate answer to a query (e_q, r_q, ?) by encoding r-digraphs, which are unions of overlapping relational paths. A dynamic-programming recursion shares the computation across all candidate answers, and a query-dependent sigmoid attention picks the edges that matter. The authors report the highest MRR on all 12 inductive splits and on all five transductive datasets. The official code differs from the paper in several places, including a GRU across layers, so read the Paper vs code section before reimplementing.

Problem

Knowledge-graph reasoning infers missing facts from existing ones §1. Relational paths capture sequential evidence and give interpretable, transferable rules, but they cannot represent richer local structure §1, §3. Subgraph and GNN methods capture more structure, yet the authors argue that they are costly or that their attention is hard to interpret. GraIL's enclosing subgraph is the example given: it loses the order of relations and is not interpretable §1, app. B. The paper targets queries of the form (subject entity, relation, ?) §1. The inductive setting assumes test-time entities are unseen during training but the relations are shared §5.1. Triples whose answer lies more than L hops from the query get no signal from an L-layer model §5.5.

Method

Setting, from §3: after augmenting every triple with a reverse and an identity relation, the r-digraph G_{e_q,e_a|L} is a layered st-graph (one source, one sink, edges only between consecutive layers) [def. 2]. It contains every relational path of length L from e_q to e_a and is empty if no such path exists [def. 3]. fig. 1 gives an example for (Sam, directed, Spider-2).

RED-GNN never builds one r-digraph per candidate. It runs one layer-wise recursion for the query and reads out a state for every entity:

1. Start with only the query entity visible, with a zero state alg. 2, line 1.
2. For layer l = 1..L, collect the facts whose subject is visible after layer l-1, and let the visible set be their objects alg. 2, line 2. These edges are shared by every candidate answer: the set of layer-l edges from e_q equals the union of the layer-l edges of all r-digraphs from e_q [prop. 1; eq. 2 is the recursion over G_{e_q,e_o|l}].
3. For each visible entity o, update its state with message passing over its incoming edges eq. 3. Each message is the previous state of the subject plus a layer-l relation embedding, scaled by an attention weight.
4. Return the layer-L state for every entity. Entities not visible at layer L get a zero representation alg. 2.

Equations from the paper (in the paper's notation):

Recursive r-digraph construction eq. 2:

\mathcal G_{e_q, e_o|\ell} = \cup_{(e_s, r, e_o) \in \hat{\mathcal E}_{e_q}^\ell} \mathcal G_{e_q, e_s|\ell-1} \otimes \left\lbrace (e_s, r, e_o) \right\rbrace

Message passing with query-dependent attention eq. 3:

\bm{h}_{e_o}^{\ell}(e_q, r_q) = \delta\Big(\bm W^\ell \cdot \sum\nolimits_{(e_s, r, e_o)\in\hat{\mathcal E}_{e_q}^{\ell}} \alpha^{\ell}_{e_s,r,e_o|r_q} \big(\bm{h}_{e_s}^{\ell-1}(e_q, r_q) + \bm{h}_r^{\ell} \big) \Big)

Attention, with a sigmoid rather than a softmax so that several edges can be selected in one neighbourhood eq. 4 and the sentence after it. The paper gives w in R^{d_alpha}, W_alpha in R^{d_alpha x 3d}, and writes the concatenation as a set of three inputs:

\alpha^{\ell}_{e_s,r,e_o|r_q} = \sigma\Big( (\bm w^{\ell}_\alpha)^\top \mathrm{ReLU}\big( \bm W^{\ell}_\alpha \cdot ( \bm h^{\ell-1}_{e_s}(e_q, r_q) \oplus \bm h^{\ell}_r \oplus \bm h^{\ell}_{r_q} ) \big) \Big)

Scoring and training eq. 5 and eq. 6:

f(e_q, r_q, e_a) = \bm w^\top \bm h^{L}_{e_a}(e_q, r_q), \qquad \bm w \in \mathbb R^{d}

\sum_{(e_q, r_q, e_a) \in \mathcal T_{\text{tra}}} \Big( - f(e_q, r_q, e_a) + \log \sum_{e \in \mathcal V} e^{f(e_q, r_q, e)} \Big)

Parameters Theta are the W^l, w_alpha^l, W_alpha^l, relation embeddings h_r^l and w, all randomly initialised. The initialisation scheme is not stated §4.2.

The model below follows the paper's equations. It is not the official code (see Paper vs code):

# RED-GNN: recursive r-digraph encoding  [alg. 2]
# Input:  query (e_q, r_q, ?), depth L, facts F, entities V
# Output: one score per entity in V  [eq. 5]

def red_gnn_scores(e_q, r_q, facts, entities, L):
    # Only e_q is visible at layer 0, with a zero state  [alg. 2, line 1]
    visible = {e_q}
    previous = {e_q: zeros(d)}                       # (d,) per entity
    for layer in range(1, L + 1):
        # Facts whose subject was visible at layer - 1  [alg. 2, line 2]
        # Shared by all candidate answers  [prop. 1]
        edges = [(s, r, o) for (s, r, o) in facts if s in visible]
        visible = {o for (s, r, o) in edges}
        # Fresh buffer, so layer - 1 states are not overwritten  [alg. 2]
        current = {}
        for o in visible:
            # Incoming edges of o at this layer  [alg. 2, line 3]
            incoming = [(s, r) for (s, r, obj) in edges if obj == o]
            total = zeros(d)
            for (s, r) in incoming:
                # Attention weight for this edge  [eq. 4]
                a = attention(previous[s], rel_emb[layer][r],
                              rel_emb[layer][r_q], layer)
                total = total + a * (previous[s] + rel_emb[layer][r])
            # Linear map and activation  [eq. 3]
            current[o] = act(W[layer] @ total)
        previous = current
    # Entities not visible at layer L keep a zero representation  [alg. 2]
    return [w @ previous[e] if e in visible else 0 for e in entities]


# Query-dependent attention on one edge  [eq. 4]
def attention(state_s, rel_r, rel_query, layer):
    # Concatenate the three inputs, then project with ReLU
    hidden = relu(W_alpha[layer] @ concat(state_s, rel_r, rel_query))
    # One scalar per edge, squashed by a sigmoid  [eq. 4]
    return sigmoid(w_alpha[layer] @ hidden)

Training uses the multi-class log loss of eq. 6, summed over the training queries, with each query scored against every entity §4.2. The paper says it minimises this with stochastic gradient descent §4.2 and uses Adam §5.1.

Cost §4.3: per query, RED-GNN costs O(d * min(D^L, |F| L)), where D is the average degree, versus O(|V| (min(D^L, |F| L) + d E L)) for the direct construction (RED-Simp, alg. 1). The paper states that RED-Simp and RED-GNN produce identical representations for the same triple [prop. 2; proof in app. C].

Interpretability §4.2, app. A: Theorem 1 §4.2, proof in app. C says that for any rule set that generates a set of relational paths, parameters and a threshold theta exist such that the edges with attention above theta form that path set's r-digraph. The proof relies on a universal-approximation argument app. C, so it is an existence result, not a learnability guarantee. For visualisation, alg. 3 (app. A) backtracks from e_a through edges with attention at least theta, and the case study uses theta = 0.5 with L = 3 on Family and UMLS §5.4.

Hyperparameters

The paper gives tuning ranges, not the selected values §5.1, §5.2. The selected per-dataset values are in the code (second table).

Tuning ranges stated in the paper:

Per-dataset settings in the official code. Inductive settings come from Static/inductive/train.py, and transductive settings from Static/transductive/train.py. The transductive table shows the training batch and the evaluation batch separately.

Sources: train.py and train.py. Both scripts run 50 epochs train.py.

Results

Author-reported. Metrics are filtered MRR, Hit@1 and Hit@10, with ties averaged §5.1. Hit@k is in percent, as printed. The inductive baseline numbers are not marked as copied; the transductive table marks copied values with "*" tab. 2. The text says RuleN was run with its default implementation §5.1.

Inductive reasoning tab. 1. Columns are the GraIL inductive benchmark versions V1 to V4 for WN18RR, FB15k-237 and NELL-995. The table is a headline in the paper, and the setup is in §5.1.

MRR:

Hit@1 (%):

Hit@10 (%):

Transductive reasoning tab. 2. "*" marks values copied from the original papers, "-" marks unavailable results, and "OOM" means out of memory tab. 2 caption. Dataset statistics are in tab. 3.

Dataset statistics, transductive tab. 3. NELL-995* follows the version in [das2017go], not the one in [teru2019inductive] (the table caption says so).

Ablation tab. 4. Each variant is evaluated on V1 of the three inductive datasets. Attn-w.o.-r_q removes the query relation from the attention. RED-Simp uses the direct construction of alg. 1 with a margin ranking loss on one negative sample, as in GraIL §5.5.

Per-distance MRR on WN18RR tab. 5. Distances are shortest-path lengths from e_q to e_a. The ratio row gives the share of test triples at each distance.

GraIL without relation information tab. 6, app. B. Each variant is evaluated by MRR on V1 of the three inductive datasets. RED-no rel removes the relation term from the RED-GNN aggregation.

Other claims: RED-GNN has far fewer parameters than the other four transductive methods, because it learns no entity embeddings §5.3. The run-time comparison is in fig. 2 and is described only in words: GraIL is "hundreds of times" slower than RED-GNN on transductive data §5.3. The depth study fig. 4 shows MRR and coverage for L from 1 to 5 §5.5. For L of at least 3, RED-GNN is the best of the compared methods, and L is tuned over {3, 4, 5} §5.5.

Paper vs code

Code: AutoML-Research/RED-GNN, commit c9badffdfe6b46dd94849ea843734a5b3d830c57. The paper's footnote links this repository, which is the basis for treating it as official. The repository has no LICENSE file, so it is cited here, not quoted; code_license is recorded as none. The README cites a 2026 journal version of the paper (Artificial Intelligence, doi 10.1016/j.artint.2026.104520) README.md. The paper text read here is the arXiv v2 LaTeX, which is in WWW '22 format, so some differences may come from the journal revision.

Matches (checked, no discrepancy): messages are the subject state plus the layer relation embedding, scaled by attention, summed, then linear and activated models.py. The attention is a sigmoid over a ReLU hidden layer on the three concatenated inputs models.py. Identity relations are added to the facts load_data.py. Reverse relations are added to each triple load_data.py. Edge expansion goes only forward from the query entity load_data.py. Scores are zero for entities not visible at layer L models.py. The score has no bias, as in eq. 5 models.py. The loss is the sum over the batch of eq. 6 base_model.py.

Differences:

1. GRU across layers (not in the paper). After every layer the code applies dropout and then a single GRU cell, shared by all layers. The GRU carries each node's hidden state across layers, with the state of a node carried over to its new index in the next layer models.py. The paper's h^L is the output of the last GNN layer eq. 3, eq. 5. The GRU parameters are not in the paper's parameter list Theta §4.2.
2. Dropout between layers (not in the equations). The paper tunes a dropout rate §5.1 but states no placement. The code applies it after each layer, before the GRU models.py.
3. Attention bias (not in the paper). The three attention projections are summed, not concatenated, and the query-relation projection and the scalar output carry biases models.py. Equation 4 has no bias terms.
4. Weight decay and learning-rate decay. The code uses Adam with weight decay lambda applied to all parameters and an exponential learning-rate decay of gamma per epoch base_model.py. The paper states only Adam and the tuning range for weight decay §5.1.
5. NaN guard (not in the paper). After every optimiser step, any NaN parameter is replaced by a uniform random number base_model.py.
6. Model selection. The code prints the epoch with the best validation MRR, and it has no early stopping train.py. The paper says the hyperparameters are selected by validation MRR with at most 50 epochs §5.1.
7. Inductive data mapping differs from the paper. As written, the loader trains on the queries in valid.txt of the transductive directory load_data.py. Its validation queries are the transductive test.txt queries load_data.py. Its test set is the union of the inductive valid.txt and test.txt queries load_data.py. The paper trains on T_tra and reports on T_tst §5.1. The data files are not in the repository, so the mapping could not be checked against the files.
8. Transductive split is re-drawn every epoch. The code merges the facts and training triples, shuffles them, and takes 3/4 as the fact graph and 1/4 as training queries load_data.py, then calls this after each epoch's evaluation base_model.py. The paper describes a 3:1 split §5.2 and does not mention re-drawing. The README describes a 3:1 random split of train.txt README.md. Validation and test use the full known graph of facts and training triples load_data.py.
9. Ties. The code averages the full rank of tied scores but uses the minimum rank for the filtered rank utils.py. The paper says that ties are averaged §5.1.
10. Hyperparameter values. The code fixes one configuration per dataset (second and third tables). The paper gives only ranges §5.1. The paper's d set {32, 48, 64, 96} does not contain the code's d = 16 for NELL-995 V3 and V4 train.py.
11. Extra code. Temporal/ holds temporal-KG code, which the paper does not cover. Its results are not included in this card.

Requirements README.md: PyTorch 1.9.1 with CUDA 10.2 and torch_scatter 2.0.9. The code calls .cuda() throughout, and data directories are referenced but not included.

Pitfalls

• Table 1 bolding does not match the numbers, and the text overstates the margin. The text says RED-GNN "outperforms the baselines across all benchmarks" §5.1. In the printed tables, RuleN is higher on FB15k-237 V1 Hit@1 (30.9 vs 30.2, although RED-GNN is bolded), on NELL-995 V1 Hit@1 (54.5 vs 52.5), and DRUM (87.3) and Neural LP (87.1) are higher than RED-GNN (86.6) on NELL-995 V1 Hit@10 tab. 1. The paper acknowledges the Hit@10 gap in the rule-based methods §5.1.
• Table 2 has cells where RED-GNN is not best. DPMPN is higher on FB15k-237 Hit@1 (28.6 vs 28.3, bolded) and CompGCN on UMLS Hit@10 (99.4 vs 99.0) tab. 2. RED-GNN is best on MRR in all five datasets.
• Possible copy error in Table 2. The RNNLogic* and pLogicNet* rows show the same UMLS values (.842, 77.2, 96.5). The asterisk says these were copied from the original papers, so check them against those papers before reuse tab. 2. The ConvE* UMLS Hit values are printed as "92." and "96.".
• Commented-out hyperparameter table in the source. The LaTeX source contains a table of "optimal hyper-parameters" inside a comment block [tex source, appendix]. It is not in the published text, and some values differ from the code. For example, NELL-995 V2 weight decay is 0.00066 there and 0.000066 in the code, and WN18RR V1 uses ReLU there and identity in the code. This card does not use the commented table.
• Unreached candidates have a fixed logit of 0. Entities not visible at layer L get the score 0 alg. 2. The learned scores can be negative, so an unreached entity can outrank reached ones in the softmax and in the ranking. The paper's per-distance results show the drop beyond L hops tab. 5.
• Layer updates must read the previous layer. Algorithm 2 updates the states of layer l from those of layer l-1 alg. 2, line 3. Writing into the same buffer during the loop mixes layers. The pseudocode above uses a fresh buffer.
• Loss scale depends on batch size. Eq. 6 is a sum over the training queries, not a mean §4.2. The code also sums over the batch base_model.py. Averaging instead would change the effective learning rate, and the paper does not discuss this.
• Full softmax over all entities. The training loss needs a score for every entity per query eq. 6. The paper says this is why RED-Simp switched to a margin ranking loss §5.5. Memory and time grow with |V|.
• Dense baselines run out of memory on large graphs. The paper attributes the failure of three baselines on the largest transductive dataset to their use of a full adjacency matrix. They are marked OOM in the NELL-995 column §5.2, tab. 2.
• Complexity hides the cost of a deep recursion. The cost bound for RED-GNN depends on the neighbourhood growth min(D^L, |F| L) §4.3, which is large for high-degree graphs. The paper gives no measured peak memory for RED-GNN in the text.
• Single runs, no variance. The paper reports one number per cell and does not state seeds or the number of runs §5. Some margins are small, for example RED-GNN .374 vs DPMPN .369 MRR on FB15k-237 tab. 2. Without variance figures, such gaps cannot be judged as significant.
• Interpretability is a construction, not a learned guarantee. Theorem 1 shows that a parameter setting exists app. C. The case study shows attention maps for two datasets with L = 3 §5.4. The paper does not measure how often learned attention recovers the rules.
• Requires CUDA. .cuda() is hard-coded in the model and loader models.py. CPU runs need code changes.

Lineage

• Builds on: relational paths and rule learners (RuleN, Neural LP, DRUM and the path samplers MINERVA and M-walk), named as cited in §2.1. No cards exist for these. Subgraph encoding follows GraIL §2.2, §4: GraIL, which the paper also uses as the main inductive baseline §5.1. The message-passing form follows the general GNN framework §2.2, eq. 1. The query-dependent attention follows GAT §4.2, with sigmoid in place of softmax §4.2.
• Compared against: RuleN, Neural LP, DRUM, GraIL in the inductive setting §5.1; ConvE, RotatE, QuatE, MINERVA, Neural LP, DRUM, RNNLogic, pLogicNet, CompGCN, DPMPN in the transductive setting §5.2.
• Concurrent work: NBFNet, cited as a concurrent method that recursively encodes all paths from the query entity with a full adjacency matrix §6. No card exists for it, and no arXiv id is given in the source.
• Superseded by: not stated in this card's sources. The repository README cites a 2026 journal version of this paper README.md.