PaperlayerView exact revision on arXiv

Source-linked AI summary

Inductive Relation Prediction by Subgraph Reasoning

Komal K. Teru, Etienne Denis, William L. Hamilton

arXiv:1911.06962v2cs.LGcs.AIstat.ML

TL;DR

Embedding-based knowledge-graph methods do not explicitly capture compositional logical rules and are limited to transductive settings. GraIL uses local subgraph reasoning with a GNN to learn entity-independent relational semantics, outperforming inductive baselines and improving transductive embedding methods through ensembling.

  • Problem

    Embedding-based relation prediction does not explicitly capture compositional logical rules and assumes that the full entity set is known during training.

  • Method

    GraIL is a GNN framework that predicts relations from local subgraph structure without node attributes or entity-specific embeddings.

  • Results

    GraIL substantially outperforms state-of-the-art inductive baselines, with 5.25% higher AUC-PR and 6.75% higher Hits@10 on average, and improves transductive methods when ensembled.

  • Takeaways & Limitations

    GraIL provides an inductive approach to knowledge-graph reasoning and supplies a complementary bias that strengthens embedding-based completion through ensembling.

  • Takeaways & Limitations

    The theoretical analysis covers only a fixed class of logical rules, while larger latent dimensions may be needed for different rules and more complex compositions.

Abstract

from arXiv · show

The dominant paradigm for relation prediction in knowledge graphs involves learning and operating on latent representations (i.e., embeddings) of entities and relations. However, these embedding-based methods do not explicitly capture the compositional logical rules underlying the knowledge graph, and they are limited to the transductive setting, where the full set of entities must be known during training. Here, we propose a graph neural network based relation prediction framework, GraIL, that reasons over local subgraph structures and has a strong inductive bias to learn entity-independent relational semantics. Unlike embedding-based models, GraIL is naturally inductive and can generalize to unseen entities and graphs after training. We provide theoretical proof and strong empirical evidence that GraIL can represent a useful subset of first-order logic and show that GraIL outperforms existing rule-induction baselines in the inductive setting. We also demonstrate significant gains obtained by ensembling GraIL with various knowledge graph embedding methods in the transductive setting, highlighting the complementary inductive bias of our method.

1. Introduction

Relation prediction in knowledge graphs is framed as logical induction as well as embedding-based completion. GraIL addresses the transductive limits of entity-specific embeddings by reasoning over local subgraphs and learning entity-independent relational semantics.

  • Embedding-based methods exploit local connectivity and homophily but do not clearly capture the logical rules underlying knowledge-graph relations.
  • Logical rules encode entity-independent relational semantics and can generalize relation predictions to unseen entities and graphs.
  • Embedding-based approaches assume a fixed entity set, whereas rule induction supports inductive predictions but suffers from scalability and expressive-power limitations.
  • GraIL predicts relations from subgraph structure around candidate node pairs instead of learning entity-specific embeddings.
  • 5.25% and 6.75% average relative gains in AUC-PR and Hits@10, respectively, distinguish GraIL from the strongest inductive baseline on new benchmarks.
  • Ensembling GraIL with embedding-based methods yields significant performance improvements in the transductive setting.

2. Related Work

Related work spans embedding-based completion, GNN-based relation prediction, inductive node embeddings, rule induction, and graph link-prediction methods. GraIL differs by treating relation prediction as subgraph reasoning without node-specific embeddings.

  • Embedding-based completion methods train low-dimensional embeddings for training-set nodes to retrieve relational information.
  • R-GCN uses GNNs for relation prediction but remains transductive as originally proposed and requires node-specific embeddings.
  • Inductive embedding methods either rely on node features or require unseen nodes to be surrounded by known nodes.
  • Rule-induction methods are inherently inductive because their probabilistic rules are independent of node identities, but they face scalability and expressive-power limitations.
  • GraIL extends GNN-based link-prediction ideas to directed, multi-relational knowledge graphs.

3. Proposed Approach

GraIL predicts relations from labeled enclosing subgraphs with a GNN, using structural information to learn entity-independent relational semantics. Its architecture can encode path-based logical rules and combine evidence from multiple rules for the same target relation.

  • Overall framework: GraIL predicts a target relation from the subgraph structure surrounding the two target nodes, without using node attributes.The task is organized into enclosing-subgraph extraction, node labeling, and GNN scoring.
  • Subgraph extraction: The enclosing subgraph intersects the k-hop neighborhoods of the target nodes and prunes isolated nodes or nodes too distant from either target.This construction retains nodes occurring on paths of length at most k + 1 between the targets.
  • Node labeling: Each node is labeled by its shortest distances to the two target nodes, while the targets receive unique labels to identify their structural roles.The distance paths exclude routes through the other target node, and the resulting features concatenate one-hot distance encodings.
  • GNN scoring: The GNN performs iterative message passing over the labeled subgraph and uses relation-aware aggregation with learned edge attention conditioned on the target relation.Attention weights are sigmoid-gated rather than normalized; basis sharing and edge dropout regularize the relational transformations.
  • Theoretical analysis: GraIL represents any path-based logical rule with k GNN layers and one-dimensional latent embeddings, producing a non-zero score exactly when the grounded rule body is satisfied.The theoretical result connects the model’s score to logical rule satisfaction for query entities.
  • Theoretical analysis: GraIL can count satisfied rules sharing the same target relation, thereby combining evidence from multiple logical rules to make a prediction.This extends the single-rule result to a set of rules with a common head relation.
  • Limitations: The theoretical analysis covers a fixed class of logical rules, while larger latent dimensions may help learn different or more complex rule compositions.Performance was reported as reasonably stable for dimensions d = 1, ..., 64.

4. Experiments

The experiments evaluate GraIL in inductive and transductive relation prediction, including benchmark construction, comparisons, ensembling, and ablations. GraIL outperforms inductive baselines and provides complementary gains when ensembled with embedding-based methods.

  • Experimental setup: The study evaluates inductive relation prediction against statistical and differentiable rule-induction methods, alongside transductive prediction, ensembling, and ablation questions.The experiments use WN18RR, FB15k-237, and NELL-995, with AUC-PR and Hits@10 as evaluation metrics.
  • Inductive relation prediction: GraIL is tested on fully inductive benchmarks built from disjoint train and test subgraphs whose relation schemas are shared.Four train-graph and ind-test-graph pairs with increasing numbers of nodes and edges are sampled for each benchmark knowledge graph.
  • Inductive relation prediction: GraIL significantly outperforms inductive baselines across all datasets in both AUC-PR and Hits@10.The results indicate that GraIL captures path-based logical rules and exploits more complex structural patterns than the compared baselines.
  • Transductive relation prediction: Ensembling GraIL with transductive embedding methods produces consistent gains across all methods on two of three datasets and exceeds other pairwise ensembles.Late fusion combines method scores through a linear classifier trained on validation data.
  • Transductive relation prediction: 1.5% and 0.62% are GraIL’s average ensemble gains on WN18RR and NELL-995, versus 0.007% and 0.08% for KGE ensembling.No ensembling produced significant gains on FB15k-237.
  • Ablation study: Removing path-only extraction, double-radius node labeling, or attention causes major degradation, with naive neighborhood extraction catastrophically overfitting.The naive configuration reaches training AUC above 99%, while the labeling and attention ablations show significant performance drops.

5. Conclusion

GraIL provides an inductive GNN framework for reasoning over knowledge graphs, combining empirical gains with theoretical analysis of logical-rule expressivity. The work also establishes benchmarks and identifies directions for further inductive-reasoning research.

  • GraIL predicts relations for nodes unseen during training and achieves state-of-the-art results in the inductive setting.
  • GraIL provides a complementary inductive bias that improves various knowledge graph embedding methods when ensembled.
  • The paper gives theoretical insights into how GNNs encode a useful subset of logical rules.
  • New benchmark datasets and a comprehensive study establish a basis for further work on inductive reasoning in knowledge graphs.Suggested directions include interpretable rule extraction, relation-distribution shifts, and meta-learning for few-shot settings.

A. JK Connections

JK-connections augment the model with representations from intermediate GNN layers, allowing flexible neighborhood ranges and improving robustness to the number of layers.

  • The best-performing model combines final-layer and intermediate-layer node representations through JK-connections.This mechanism allows the effective neighborhood range to vary for each node.
  • Adding JK-connections made model performance more robust to the number of GNN layers.

B. Other Model Variants

The authors tested alternative pooling and combination functions within the flexible GNN scoring formulation, but none produced significant performance improvements.

  • Alternative pooling aggregation and concatenation-like or GRU-based combination functions did not significantly improve performance.The scoring model supports different AGGREGATE and COMBINE functions, but these tested variants were not beneficial.

C. Hyperparameter Settings

The model was trained with fixed implementation and optimization settings, using checkpoint selection on validation performance before testing.

  • Experiments used PyTorch, 50 epochs, a GTX 1080 Ti, and the Adam optimizer with learning rate 0.01.The setup also used an L2 penalty of 5e-4, margin 10, and gradient clipping at norm 1000.
  • The checkpoint with the best validation performance was selected for testing and saved every three epochs.

D. Transductive Results

Transductive evaluation used the same methodology as the inductive evaluation, but trained and tested GraIL on the same graph. In this setting, GraIL generally outperformed RuleN and achieved substantially stronger ranking metrics than inductive evaluation.

  • GraIL was trained on the train-graph and tested on that same graph, with 10% of training links randomly selected as test links.This evaluation protocol corresponds to the transductive setting.
  • Transductive AUC-PR and Hits@10 were significantly better than the corresponding inductive results, indicating that the inductive task is more difficult.
  • GraIL performed significantly better than RuleN in most transductive cases and was competitive in the remaining cases.

E. Inductive Setting Hits@10

The paper reports late-fusion Hits@10 results in the transductive setting and states that the trends from earlier evaluations persist. Inductive graphs were constructed from disjoint entity sets using capped k-hop neighborhoods.

  • Transductive late fusion: Late-fusion models were evaluated with Hits@10 in the transductive setting, complementing results from Tables 3, 5, and 4.
  • Transductive late fusion: The late-fusion transductive results followed trends similar to those discussed in Section 4.2.
  • Inductive graph construction: Inductive train and test graphs contained no overlapping entities.
  • Inductive graph construction: Each inductive graph was formed by sampling root entities and taking the union of their k-hop neighborhoods.The number of new neighbors at each hop was capped to prevent exponential growth.

G. Proof of Theorem 1

Theorem 1 is established by constructing a GraIL parameterization that propagates rule-specific relation signals through a multi-layer message-passing network. Induction shows that the target representation is nonzero exactly when the rule body connects the source to the target.

  • Rule representation: The proof considers rules whose head relation connects variables through a sequence of body relations.The rule is represented as rt(X, Y) ← r1(X, Z1) ∧ r2(Z1, Z2) ∧... ∧rk(Zk−1, Y).
  • Lemma 2: For any such rule, a k-layer GraIL model with one-dimensional latent embeddings has a parameter setting satisfying the theorem's required condition.
  • Lemma 1: GraIL can assign attention so that the relation selected at layer l matches the rule relation at distance l from the head.This relation-specific attention is the key mechanism used in the proof.
  • Parameterization: The construction relies on nonlinear MLPs being universal function approximators and allows relation embeddings to be learned in one-dimensional space.
  • Lemma 2: Induction proves that the target node's representation is positive exactly when successive relation edges form the rule body from source u to target t.The base case handles one relation, while the induction step appends the next relation.
  • Theorem 1: Theorem 1 follows because the final target embedding is nonzero only when v is connected to u by the body of rule R.The proof identifies this condition with the rule head relation being satisfied for the queried pair.
Loading 1911.06962v2…