Inductive Relation Prediction by Subgraph Reasoning

In plain words

A knowledge graph stores facts as links between things: a person lives in a city, a word is a kind of another word. A common task is guessing a missing link, such as where someone lives when that fact is absent. The usual approach gives every entity a learned vector. That works for the entities seen during training, but a brand-new entity has no vector, so the model has to be retrained before it can answer questions about it.

GraIL takes a different route. To judge a candidate link between two entities, it looks at the small neighbourhood that connects them, labels every node in that neighbourhood by how far it sits from each of the two entities, and lets a small neural network read the pattern. Nothing in the model is tied to a particular entity's name or ID, only to the shape of the connections and the relation types. A new part of the graph with the same kinds of relations can therefore be scored without retraining.

The authors show that this kind of pattern reading can express the same chains of reasoning that classic rule-mining systems use, and that it can be combined with embedding models to improve results on the usual benchmarks.

TL;DR

• GraIL scores a candidate triple (u, r, v) from the enclosing subgraph between u and v. It uses no entity embeddings and no node features.
• The subgraph is labelled with the distance of each node to u and to v, then a relation-aware GNN with edge attention and a jumping-knowledge readout produces a score.
• Author-reported: best inductive AUC-PR on all 12 split–dataset combinations against RuleN, Neural-LP and DRUM; best Hits@10 on 10 of 12.
• Transductively it is not the strongest model alone, but ensembling it with KGE models gives small gains on two of three datasets.
• Official code is linked; it has no LICENSE file, so use it as a reference, not as a source of copied text.

Problem

Relation prediction in knowledge graphs is usually framed as ranking missing edges. Embedding methods learn one vector per entity; they capture local neighbourhood patterns but do not capture logical rules explicitly, and they assume a fixed entity set (the transductive setting) §1. Rule-induction methods are inductive because their rules do not depend on entity identity, but they scale poorly and have less expressive power §2.

Existing benchmarks ensure that every test entity appears in training, so they cannot test inductive ability. The authors therefore build new inductive splits in which the training graph and the test graph share no entities but share the relation set §4.1 app. F. The approach assumes the local neighbourhood of a candidate link contains the evidence needed to decide it §3.1.

Method

GraIL scores a triple in three steps §3.1:

1. Enclosing subgraph. Take the k-hop undirected neighbourhoods of u and of v and keep the nodes that lie in both. Edge direction is ignored here. Add the target triple so that u and v can exchange messages §3.1. Observation 1 §3.1 shows that nodes on a path of length k+1 between u and v are within k hops of one of them, so this keeps the relevant paths.
2. Double-radius labelling. Every node i gets the pair (distance to u, distance to v), with each distance measured without passing through the other target. u is labelled (0, 1) and v is labelled (1, 0). Nodes farther than k from either target are dropped. The initial feature is the concatenation of one-hot encodings of the two distances §3.1.
3. GNN scoring. Run L message-passing layers. Each layer sums messages from incoming edges, where each message is a relation-specific linear transform of the sender's state, weighted by an unnormalised sigmoid attention gate that depends on both endpoints and on the relation and the target relation §3.1 eq. 2 eq. 3. Relation matrices are built from a small set of shared bases as in R-GCN §3.1 layers.py. The score is a linear function of the mean-pooled subgraph state, the two target-node states and a learned embedding of the target relation §3.1 eq. 5 eq. 6. The best model concatenates these readouts from every layer (jumping-knowledge connections) §3.1 app. A.

Training uses a margin ranking loss. For each positive triple, one negative is created by replacing its head or its tail with a uniformly sampled entity §3.2. The loss pushes the positive score above the negative score by a margin eq. 7 §3.2.

The aggregation and combination functions follow the general message-passing scheme of Xu et al. §3.1 eq. 2 eq. 3:

\mathbf{a}_t^{k} = \mathrm{AGGREGATE}^{k}\left(\left\{\mathbf{h}_s^{k-1} : s \in \mathcal{N}(t)\right\}, \mathbf{h}_t^{k-1}\right) eq. 2

\mathbf{h}_t^{k} = \mathrm{COMBINE}^{k}\left(\mathbf{h}_t^{k-1}, \mathbf{a}_t^{k}\right) eq. 3

The aggregation used by GraIL, with the attention gate and the relation-specific weights, is given in §3.1 (unnumbered). Attention is a two-layer network over the concatenated endpoint states and relation embeddings, followed by a sigmoid §3.1 (unnumbered). The combination is a ReLU over a self-transform plus the aggregated message eq. 4.

\mathbf{h}_t^{k} = \mathrm{ReLU}\left(\mathbf{W}_{self}^k \mathbf{h}_t^{k-1} + \mathbf{a}_t^{k}\right) eq. 4

The score is computed from the pooled subgraph state and the two target states eq. 5 eq. 6; the loss is eq. 7.

# Enclosing subgraph of a candidate triple (u, r_t, v)  [§3.1]
# Input: KG triples, targets u and v, hop k; Output: node list
def enclosing_nodes(triples, u, v, k):
    # k-hop undirected neighbourhoods of each target  [§3.1]
    near_u = within_hops(triples, u, k)
    near_v = within_hops(triples, v, k)
    # Keep the nodes shared by both neighbourhoods  [§3.1]
    shared = near_u & near_v
    return [u, v] + [n for n in shared if n not in (u, v)]

# Double-radius labels for the nodes of the subgraph  [§3.1]
# Each distance avoids the other target node.
def double_radius_labels(subgraph, u, v, k):
    labels = {u: (0, 1), v: (1, 0)}  # targets fixed  [§3.1]
    for node in subgraph.nodes:
        if node in (u, v):
            continue
        # distance to u with v removed from the subgraph  [§3.1]
        dist_u = shortest_path_len(subgraph - v, node, u)
        # distance to v with u removed from the subgraph  [§3.1]
        dist_v = shortest_path_len(subgraph - u, node, v)
        labels[node] = (dist_u, dist_v)
    # Drop nodes farther than k from either target  [§3.1]
    return {n: l for n, l in labels.items() if max(l) <= k}

# One message-passing layer with edge attention  [§3.1] [eq. 2] [eq. 3]
# h[node] has shape (d,); W[r] is the relation-specific matrix
def gnn_layer(h, incoming, target_rel):
    new_h = {}
    for t in nodes:
        msg = zeros(d)
        # messages arrive along edges s -> t with relation r  [§3.1]
        for (s, r) in incoming[t]:
            # unnormalised gate; A1, b1, A2, b2 are learned  [§3.1]
            gate = sigmoid(A2 @ relu(A1 @ concat(h[s], h[t],
                                                 rel_att[r],
                                                 rel_att[target_rel])))
            msg = msg + gate * (W[r] @ h[s])
        # self transform plus aggregated message, then ReLU  [eq. 4]
        new_h[t] = relu(W_self @ h[t] + msg)
    return new_h

# Score a triple from every layer (jumping knowledge)  [§3.1] [app. A]
# layers_h: list of per-layer node states, one entry per GNN layer
def score(layers_h, u, v, target_rel):
    parts = []
    for h in layers_h:
        # mean over all subgraph nodes, plus both target nodes  [eq. 5]
        parts.append(mean_over_nodes(h))
        parts.append(h[u])
        parts.append(h[v])
    # learned embedding of the target relation  [eq. 6]
    parts.append(rel_emb[target_rel])
    return W_out @ concat(parts)

# Margin ranking loss on corrupted triples  [§3.2] [eq. 7]
def training_loss(positives, margin):
    total = 0
    for (u, r, v) in positives:
        # replace the head or the tail with a uniform random entity  [§3.2]
        u_neg, v_neg = corrupt(u, v)
        pos = score(run_gnn(u, v, r), u, v, r)
        neg = score(run_gnn(u_neg, v_neg, r), u_neg, v_neg, r)
        total = total + max(0, neg - pos + margin)  # margin  [app. C]
    return total

# Predict one candidate triple at test time  [§3.1] [§3.4]
def predict(triples, u, v, r, k):
    nodes = enclosing_nodes(triples, u, v, k)
    labeled = double_radius_labels(induced(triples, nodes), u, v, k)
    return score(run_gnn(labeled, r), u, v, r)

Hyperparameters

Values in the paper come from §4.1, §4.2 and app. C. Code defaults are listed where they differ or fill a gap. Settings the paper leaves out are written "not stated".

Inductive splits: each dataset has four versions, each a pair of graphs with disjoint entities and a shared relation set §4.1 app. E app. F. The released splits live in train.txt and similar folders.

Results

Author-reported. Setup: inductive splits derived from WN18RR, FB15k-237 and NELL-995 (four versions each), baselines RuleN, Neural-LP and DRUM, averaged over five runs §4.1. The authors state that the variance was very low and omit standard errors §4.1. The text also reports an average relative gain over the strongest inductive baseline of 5.25% in AUC-PR and 6.75% in Hits@10 §1.

Inductive AUC-PR tab. 1. GraIL is best in all 12 columns.

Inductive Hits@10 tab. 2. GraIL is best in 10 of 12 columns. RuleN is best on FB15k-237 v3, and Neural-LP and DRUM are best on NELL-995 v4 (Neural-LP 80.58, DRUM 80.58, GraIL 73.19).

Transductive AUC-PR, appendix app. D. Setup as in §4.2.

Transductive Hits@10, appendix app. D.

| Model | WN18RR v1 | v2 | v3 | v4 | FB15k-237 v1 | v2 | v3 | v4 | NELL-995 v1 | v2 | v3 | v4 | |---|---|---|---|---|---|---|---|---|---|---|---|---|---| | RuleN | 63.42 | 68.09 | 63.05 | 65.55 | 67.53 | 88.00 | 91.47 | 92.35 | 62.82 | 82.82 | 80.72 | 58.84 | | GraIL | 65.59 | 69.36 | 64.63 | 67.28 | 71.93 | 86.30 | 88.95 | 91.55 | 64.08 | 86.88 | 84.19 | 82.33 |

Late-fusion ensembles, AUC-PR tab. 3 tab. 4 tab. 5. Diagonal entries are single models; off-diagonal entries are pairwise ensembles. T, D, C, R and G are TransE, DistMult, ComplEx, RotatE and GraIL. The Hits@10 versions are in app. E and are not reproduced here.

WN18RR tab. 3:

NELL-995 tab. 4:

FB15k-237 tab. 5:

The text reports average gains from ensembling GraIL with each KGE model of 1.5% on WN18RR and 0.62% on NELL-995, and none significant on FB15k-237 §4.2. The paper does not give a significance test.

Early fusion, AUC-PR tab. 6. GraIL++ concatenates TransE embeddings to GraIL's labels. The text reports a boost of up to 18.2% §4.2.

Ablation on the v3 splits, AUC-PR tab. 7:

Inductive dataset statistics app. E. Counts are relations, nodes and links.

Figures 1 and 2 show the task settings and the model overview fig. 1 fig. 2. They are not reproduced on this page.

Paper vs code

Official code: the paper links github.com/kkteru/grail §4. The repository owner matches the first author, and it is pinned at code_commit. The repository has no LICENSE file, so code is cited here by path and line only, and nothing is quoted.

• Epochs. Paper: 50 app. C. Code default: 100 train.py.
• Validation schedule. Paper: evaluate every three epochs and keep the best checkpoint app. C. Code: evaluate every 455 iterations, save when the validation AUC is at least the best so far train.py trainer.py. The epoch-level evaluation is commented out trainer.py.
• Gradient clipping. Paper: norm 1000 app. C. Code: the --clip flag is parsed train.py, but the training step only calls zero_grad, backward and step trainer.py. Clipping is not applied.
• Batch size and "full batch". Paper: no batch size is given. Code: mini-batches of 16 positives train.py trainer.py. The log line says "full batch" train.py, which is misleading.
• Distance order in labels. Paper: the first component is d(i, u), the distance to the head, avoiding v §3.1. Code: the first component is computed on the subgraph with u removed, so it is the distance to v [code: subgraph_extraction/graph_sampler.py#L216-L219]. The target nodes keep the paper's fixed labels (0, 1) and (1, 0) graph_sampler.py. This reading is from the code and was not executed. It changes only which feature slot holds which distance, so a model trained one way will not load weights from the other.
• Direction wording. Paper: N_r(t) are the "immediate outgoing neighbors" of t §3.1. Code: messages travel along each stored edge from its source to its target, and the target aggregates them, so the aggregation is over edges that point into t layers.py. Reverse relations are added only when the flag is set, and it defaults to off train.py.
• Edge dropout. Paper: edges are randomly dropped at rate 0.5 §3.1 §4.1. Code: the dropout module is applied to a vector of ones used as edge weights layers.py. PyTorch's nn.Dropout scales surviving entries by 1/(1 − p) during training, so a kept edge has weight 2 in training and 1 at evaluation. The paper does not mention this scaling.
• Repeats. Paper: 5 runs averaged §4.1. Code: --runs defaults to 1 test_auc.py.
• Late fusion. Paper: a linear classifier trained on validation scores §4.2, with no optimizer or epoch count. Code: a two-input linear layer with Adam at learning rate 0.1, weight decay 5e-4, margin 10 and 500 epochs [code: ensembling/blend.py#L40-L42] blend.py.

No discrepancies found in the attention gate, the combination function, the JK readout, the pooling and the basis decomposition layers.py graph_classifier.py.

Pitfalls

• Negative sampling. The paper says a head or tail is replaced by a random entity §3.2. The code also redraws when the corrupted pair already exists for that relation or when head and tail coincide [code: subgraph_extraction/graph_sampler.py#L54-L60]. Test negatives also skip existing edges test_ranking.py. An implementation that omits this filter will produce different negatives.
• Hits@10 depends on the sampler. Each positive is ranked against 50 sampled negatives §4.1, so the number depends on those negatives [code: test_ranking.py#L75-L105].
• Enclosing subgraph matters a lot. Using the union of the neighbourhoods instead of the intersection drops FB (v3) from 91.68 to 84.25 tab. 7. The code keeps the intersection by default graph_sampler.py.
• Labels are clipped to the training maximum. At test time, labels above the largest training label are clipped to it graph_sampler.py graph_sampler.py. The training maximum is stored with the model datasets.py test_auc.py. The input size depends on it, because each distance gets one one-hot block of size max + 1 datasets.py.
• Distances are measured inside the extracted subgraph, not in the whole graph, so a node can look farther away than it is [code: subgraph_extraction/graph_sampler.py#L197]. Nodes beyond k are then dropped graph_sampler.py.
• Target-edge handling. The code adds the target edge (0, 1) with the target relation only if it is missing datasets.py. Edge dropout is applied to all edges, including this one [code: model/dgl/layers.py#L119], so during training the target edge is itself dropped about half the time.
• Unseen relations are dropped silently. At test time, triples whose relation is not in the training vocabulary are removed [code: utils/data_utils.py#L48-L50]. The paper requires the training graph to contain every test relation §4.1.
• Adjacency for testing comes from the train file only. The test graph is built from train.txt, so test links are not in the graph used for subgraphs data_utils.py test_auc.py.
• Attention is unnormalised. The sigmoid gate is not normalised over neighbours §3.1, so the aggregated sum grows with in-degree. The paper does not discuss this effect.
• Mean pooling depends on subgraph size eq. 5. Large enclosing subgraphs dilute the pooled state. The paper does not discuss this.
• Theory is narrower than the claims. The expressiveness result covers path-shaped rules with one-dimensional embeddings and an existence statement §3.3 app. G. Lemma 1 relies on an MLP approximation, and the experiments use 32 dimensions §4.1. The result does not show that training finds such parameters.
• Cost is in extraction, not in the network. Inference is dominated by shortest-path computations on the subgraph §3.4. The code precomputes subgraphs into an LMDB store per split graph_sampler.py.
• Significance is not tested. Ensemble and ablation gaps are reported without tests §4.2 §4.3.
• Printed formula. The gain formula in §4.2 has unbalanced parentheses in the denominator. Read it as the maximum of the two single-model scores.

Lineage

• Builds on: the SEAL method for link prediction with GNNs and its double-radius labelling §2 §3.1 (Zhang and Chen, NeurIPS 2018); R-GCN for relation-specific weights, basis sharing and the general message-passing scheme §3.1 (Schlichtkrull et al., ESWC 2017); the aggregation framework of Xu et al. §3.1 (ICLR 2019); jumping-knowledge connections (Xu et al., ICML 2018) app. A. No card for these papers exists in the wiki yet.
• Compared against: RuleN, Neural-LP and DRUM for inductive results §4.1; TransE, DistMult, ComplEx and RotatE for transductive and ensemble results §4.2.
• Superseded by: not stated in this wiki.