PaperlayerView exact revision on arXiv

Source-linked AI summary

Convolutional 2D Knowledge Graph Embeddings

Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, Sebastian Riedel

arXiv:1707.01476v6cs.LG

TL;DR

Knowledge graphs contain missing links, while scalable shallow predictors may lack expressive power. This paper introduces ConvE, a parameter-efficient 2D convolutional link-prediction model, and evaluates it alongside robust datasets addressing inverse-relation leakage; ConvE achieves state-of-the-art results across most datasets.

  • Problem

    Knowledge graphs contain missing links, creating a need for link predictors that are both expressive and scalable to large graphs.

  • Method

    The paper introduces ConvE, a multi-layer model using 2D convolutions over entity and relation embeddings, and constructs robust dataset variants to address inverse-relation leakage.

  • Results

    ConvE achieves state-of-the-art results on several datasets, while a simple inverse-relation model achieves state-of-the-art results on WN18 and FB15k.

  • Takeaways & Limitations

    Evaluating link-prediction models on datasets without exploitable inverse relations is important, and ConvE remains competitive on robust benchmarks.

  • Takeaways & Limitations

    WN18 and FB15k are severely affected by inverse-relation test leakage, so strong results on them may not reflect knowledge-graph modeling ability.

Abstract

from arXiv · show

Link prediction for knowledge graphs is the task of predicting missing relationships between entities. Previous work on link prediction has focused on shallow, fast models which can scale to large knowledge graphs. However, these models learn less expressive features than deep, multi-layer models -- which potentially limits performance. In this work, we introduce ConvE, a multi-layer convolutional network model for link prediction, and report state-of-the-art results for several established datasets. We also show that the model is highly parameter efficient, yielding the same performance as DistMult and R-GCN with 8x and 17x fewer parameters. Analysis of our model suggests that it is particularly effective at modelling nodes with high indegree -- which are common in highly-connected, complex knowledge graphs such as Freebase and YAGO3. In addition, it has been noted that the WN18 and FB15k datasets suffer from test set leakage, due to inverse relations from the training set being present in the test set -- however, the extent of this issue has so far not been quantified. We find this problem to be severe: a simple rule-based model can achieve state-of-the-art results on both WN18 and FB15k. To ensure that models are evaluated on datasets where simply exploiting inverse relations cannot yield competitive results, we investigate and validate several commonly used datasets -- deriving robust variants where necessary. We then perform experiments on these robust datasets for our own and several previously proposed models and find that ConvE achieves state-of-the-art Mean Reciprocal Rank across most datasets.

Introduction · Related Work

Knowledge graphs are useful but incomplete, and scalable shallow link-prediction models trade expressiveness for efficiency. The paper introduces ConvE, a parameter-efficient 2D convolutional model, and motivates its design through related work and increased embedding interactions.

  • Introduction: More than 66% of person entries in Freebase and DBpedia are missing a birthplace, illustrating knowledge-graph incompleteness.
  • Introduction: Millions of facts make manageable parameter counts and computational costs necessary for real-world link prediction.
  • Introduction: Shallow models such as DistMult scale through simple operations and limited parameters, but learn less expressive features.
  • Introduction: A DistMult embedding size of 200 requires 33 GB of parameters on Freebase, making increased embedding size poorly scalable.
  • Introduction: ConvE uses a single convolution layer, projection layer, and inner-product layer to apply 2D convolutions over embeddings for missing-link prediction.
  • Introduction: 1-N scoring speeds training three-fold and evaluation by 300x, while ConvE achieves better FB15k-237 scores than DistMult and R-GCNs with 8x and 17x fewer parameters.
  • Related Work: Prior neural link-prediction models include TransE, DistMult, ComplEx, and HolE; ConvE is presented as the first neural link-prediction model using 2D convolutional layers.
  • Number of Interactions for 1D vs 2D Convolutions: Compared with 1D convolution, 2D convolution extracts more feature interactions between embeddings, with interaction counts proportional to m, n, and k in the alternating case.

Background

A knowledge graph represents facts as subject–relation–object triples over entities and relation types. Link prediction learns a scoring function for these triples, while neural models encode entities and score their embeddings with relation-specific functions.

  • Knowledge graphs: A knowledge graph is a set of triples (s, r, o), each representing a relation r between subject s and object o.The graph is formalized as G ⊆ E × R × E, with s, o ∈ E and r ∈ R.
  • Link prediction: Link prediction learns a scoring function ψ : E × R × E 7→ R whose scores indicate the likelihood that input triples are true.The task is formalized as pointwise learning to rank.
  • Neural link prediction: Neural link prediction models use an encoding component to map entities into embeddings and a scoring component to evaluate those embeddings.For an input triple (s, r, o), entity embeddings es and eo are scored by ψr, with ψ(s, r, o) = ψr(es, eo).
  • Neural link prediction: Existing neural link predictors differ in their scoring functions, relation-dependent parameters, embedding domains, and space complexity.The literature includes models using real or complex embeddings, tri-linear dot products, convolution, and nonlinear functions.

Convolutional 2D Knowledge Graphs · Embeddings

ConvE models entity–relation interactions with convolutional and fully connected layers over reshaped 2D embeddings. For link prediction, 1-N scoring evaluates all candidate objects simultaneously, while full-entity scoring trades some per-pass speed for substantially faster convergence.

  • Embeddings: ConvE scores entity–relation interactions by applying convolutional and fully connected layers to concatenated, 2D-reshaped embeddings.The convolutional filters and projection matrix are independent of the subject and object entity parameters.
  • Embeddings: The model retrieves entity and relation vectors, reshapes them into matrices, concatenates them, and feeds the result into a 2D convolution.The resulting feature maps are vectorised, projected into k dimensions, and matched against candidate object embeddings.
  • Embeddings: Training applies the logistic sigmoid to scores and minimises binary cross-entropy using labels that mark existing relationships as one and others as zero.The label vector supports both 1-1 and 1-N scoring configurations.
  • Embeddings: The architecture uses ReLU activations, batch normalisation after each layer, and dropout on embeddings, convolutional feature maps, and fully connected hidden units.These choices are described as supporting faster training, stabilisation, regularisation, and convergence.
  • Fast Evaluation for Link Prediction Tasks: Convolution consumes about 75-90% of total computation time, while increasing batch size is constrained by GPU memory requirements.This motivates reducing convolution operations during link-prediction evaluation.
  • Fast Evaluation for Link Prediction Tasks: 1-N scoring evaluates one (s, r) pair against all entities o ∈E simultaneously instead of scoring each triple separately.This is contrasted with 1-1 scoring, which scores an individual entity–relation–entity triple.
  • Fast Evaluation for Link Prediction Tasks: 25% faster forward-backward passes from scoring 10% of entities come with roughly 230% slower training convergence, whereas 1-N scoring converges much faster and performs better.The authors interpret 1-N scoring as having an effect akin to batch normalisation, trading computational performance for convergence speed.

Experiments

The experiments evaluate ConvE across several link-prediction benchmarks while exposing severe inverse-relation leakage in WN18 and FB15k. The authors construct leakage-resistant evaluation variants and investigate convolutional design choices and training settings.

  • Datasets: The evaluation uses WN18, FB15k, YAGO3-10, and Countries, spanning hierarchical, factual, descriptive, and long-range dependency link-prediction settings.WN18 contains 18 relations and 40,943 entities; FB15k contains about 14,951 entities and 1,345 relations; YAGO3-10 contains 123,182 entities and 37 relations; Countries has sub-tasks with minimum pathlengths from 2 to 4.
  • Robust evaluation: FB15k-237 removes inverse relations from FB15k, while the authors create WN18RR after finding analogous flaws in WN18.These variants are intended to prevent competitive performance from coming simply from exploiting inverse relations.
  • Test leakage: A simple inverse-only rule-based model achieves state-of-the-art results on WN18 and FB15k, demonstrating that their leakage can dominate evaluation.The model automatically extracts inverse relation pairs from the training set and uses inverse matches at test time.
  • Model configuration: Replacing 2D convolution with fully connected layers or 1D convolution consistently reduced predictive accuracy, and good results required 3x3 filters in the first convolutional layer.The reported ConvE configuration used embedding dropout 0.2, feature map dropout 0.2, projection-layer dropout 0.3, embedding size 200, batch size 128, learning rate 0.001, and label smoothing 0.1 on most datasets.
  • Test leakage: 94% and 81% of WN18 and FB15k triples, respectively, have inverse relations linked to the test set, enabling predictions from training-set inverses.For example, a test triple (feline, hyponym, cat) can correspond to a training triple (cat, hypernym, feline).

Results

In filtered link-prediction evaluation, ConvE achieves strong or state-of-the-art results across several datasets, while an inverse-only model exposes severe benchmark leakage on FB15k and WN18. ConvE also delivers substantially greater parameter efficiency than DistMult and R-GCN.

  • Evaluation protocol: Filtered evaluation ranks each test triple against candidate triples formed by replacing its subject or object with every entity, excluding observed triples.Candidates exclude triples appearing in the training, validation, or test sets.
  • Benchmark leakage: The inverse model achieves state-of-the-art performance on many metrics for FB15k and WN18, but fails on YAGO3-10 and FB15k-237.Its good WN18RR score is explained by symmetric relationships remaining in the dataset.
  • ConvE results: ConvE achieves state-of-the-art performance for all metrics on YAGO3-10, some metrics on FB15k, and strong performance on WN18.On Countries, it solves S1 and S2 and outperforms DistMult and ComplEx on S3.
  • Parameter efficiency: 3 metrics out of 5: ConvE with 0.23M parameters performs better than DistMult with 1.89M parameters on FB15k-237.ConvE with 0.46M parameters achieves 0.425 Hits@10, compared with 0.417 Hits@10 for R-GCN using more than 8M parameters.
  • Parameter efficiency: 17x: ConvE is more parameter efficient than R-GCNs, and 8x more parameter efficient than DistMult.For the entirety of Freebase, model sizes are more than 82GB for R-GCNs, 21GB for DistMult, and 5.2GB for ConvE.

Analysis

The analysis identifies hidden dropout as ConvE’s most important ablation component and finds that model depth benefits prediction on graphs with high relation-specific indegree. PageRank analysis further links ConvE’s relative advantage over DistMult to graph connectivity and high recursive indegree.

  • Ablation study: Hidden dropout is by far the most important component; 1-N scoring and input dropout improve performance, feature-map dropout has a minor effect, and label smoothing is unimportant.The ablation study evaluates different parameter initialisations with n = 2 to calculate confidence intervals.
  • Indegree analysis: 0.952 Hits@10 for ConvE versus 0.938 Hits@10 for DistMult on high-WN18, while low-FB15k reverses the result at 0.586 versus 0.728 Hits@10.Both hypotheses hold: deeper ConvE performs better on the high-indegree dataset, whereas shallow DistMult performs better on the low-indegree dataset.
  • PageRank analysis: r = 0.56 is the strong correlation between mean test-set PageRank and ConvE’s relative error reduction compared to DistMult.The most central WN18 nodes have PageRank values more than an order of magnitude below YAGO3-10 and Countries, and about four times below FB15k.
  • PageRank analysis: ConvE’s increased performance over DistMult can be partially explained by greater precision in modelling nodes with high indegree, possibly related to its depth.PageRank is used as a measure of centrality and recursive indegree, supporting the connection between connectivity and model advantage.

Conclusion and Future Work

ConvE combines 2D convolution and multilayer nonlinear features to provide a parameter-efficient, scalable, and robust link-prediction model with state-of-the-art results. The paper also addresses inverse-relation test leakage and identifies deeper convolutions and embedding-structure constraints as future directions.

  • Contributions: ConvE uses 2D convolution over embeddings and multiple nonlinear layers while remaining fast through 1-N scoring and scalable to large knowledge graphs.Batch normalisation and dropout improve robustness to overfitting.
  • Dataset evaluation: A simple rule-based model achieves state-of-the-art results on WN18 and FB15k by exploiting test leakage through inverse relations.The authors derive WN18RR to provide a robust dataset variant.
  • Future work: Future work could develop deeper convolutional models, interpret 2D convolution, and enforce large-scale embedding structure to increase interactions between embeddings.The authors note that ConvE remains shallow compared with convolutional architectures in computer vision.

SUPPLEMENTAL MATERIAL · Versions · Further ConvE results

The supplemental version history records updated results, corrected evaluation issues, and dataset-reporting changes. It also documents that some datasets were unsuitable or difficult to reproduce reliably.

  • Versions: 2018-07-04: New YAGO3-10 results were added, with worse performance on most metrics but state-of-the-art results retained.The update also noted an inability to replicate the initially reported FB15k scores.
  • Versions: 2018-07-04: Nations scores were removed from the appendix because the dataset contains a high proportion of inverse relationships and was deemed unsuitable for research use.The authors stated they did not want to encourage its use.
  • Versions: 2018-04-06: Triple-mask evaluation issues were found and fixed, producing new UMLS and Nations appendix numbers.Results were unchanged on Kinship, WN18, WN18RR, and FB15k-237.
  • Versions: 2018-03-28: Inverse Model numbers were revised after a bugfix, alongside new UMLS, Nations, and Kinship appendix numbers.The appendix used the most commonly reported test-data splits.
  • Versions: 2018-01-07: The work was extended into an AAAI camera-ready version, while earlier entries record the original NIPS submission and an acknowledgements correction.The listed dates were 2018-01-07, 2017-07-08, and 2017-07-05.

Evaluation Metrics

The evaluation ranks each test triple against subject and object corruptions, using filtered rankings to exclude known true triples. Model quality is measured with Mean Reciprocal Rank and Hits@k, where higher values are better.

  • Evaluation procedure: For each test triple, subject and object corruptions replace the corresponding entity with every other knowledge-graph entity.The model is evaluated by whether it scores the test triple higher than its corruptions.
  • Evaluation procedure: The filtered setting removes all triples already present in the graph from the corruption sets, because some corruptions may also be true triples.Known true triples should not be penalized for receiving higher scores than the test triple.
  • Evaluation procedure: Evaluation uses left and right ranks, corresponding to corrupting the subject or object, respectively.Ranks are computed using the model scoring function ψ(·).
  • Metrics: Mean Reciprocal Rank is the average inverse rank, while Hits@k is the percentage of ranks at most k; higher values indicate better performance.Both metrics assess the quality of the resulting rankings.
Loading 1707.01476v6…