PaperlayerView exact revision on arXiv

Source-linked AI summary

Holographic Embeddings of Knowledge Graphs

Maximilian Nickel, Lorenzo Rosasco, Tomaso Poggio

arXiv:1510.04935v2cs.AIcs.LGstat.ML

TL;DR

Knowledge-graph embedding models must represent rich relational interactions without sacrificing scalability and efficient training. The paper introduces HOLE, which uses circular correlation to construct fixed-width compositional representations and learns embeddings for relational data. Across benchmark knowledge-graph and relational-learning tasks, HOLE achieves state-of-the-art performance while remaining economical in parameters; the training setup can require heuristic negative-example generation under the open-world assumption.

Abstract

from arXiv · show

Learning embeddings of entities and relations is an efficient and versatile method to perform machine learning on relational data such as knowledge graphs. In this work, we propose holographic embeddings (HolE) to learn compositional vector space representations of entire knowledge graphs. The proposed method is related to holographic models of associative memory in that it employs circular correlation to create compositional representations. By using correlation as the compositional operator HolE can capture rich interactions but simultaneously remains efficient to compute, easy to train, and scalable to very large datasets. In extensive experiments we show that holographic embeddings are able to outperform state-of-the-art methods for link prediction in knowledge graphs and relational learning benchmark datasets.

Introduction

Knowledge graphs represent entities and their binary relationships, supporting tasks such as link prediction, entity resolution, taxonomy extraction, and probabilistic question answering. Existing embedding models face a trade-off between expressive relational interactions and scalability, motivating HOLE.

  • Knowledge graphs model facts as instances of binary relations between entities and concepts.Source: Introduction · p. 1
  • Embeddings of knowledge graphs support link prediction, entity resolution, taxonomy extraction, probabilistic question answering, machine reading, and website-trust assessment.Source: Introduction · p. 1
  • Existing models often trade expressive relational interactions for computational scalability.Source: Introduction · p. 1
  • HOLE uses circular correlation of entity embeddings to form compositional representations of binary relational data.Source: Introduction · p. 1
  • HOLE is designed to capture rich interactions while remaining efficient to compute, easy to train, and scalable to very large datasets.Source: Introduction · p. 1

Compositional Representations

Compositional vector space models learn relation functions from entity and relation embeddings by constructing representations for entity pairs. They balance expressive interactions against representation size, computational cost, and modeling simplicity.

Tensor Product

  • Tensor products capture all pairwise feature interactions but require composite representations of size d^2, increasing parameter and computational demands.Source: Compositional Representations · p. 2

Concatenation, Projection, and Non-Linearity

  • Concatenation followed by projection and nonlinearity learns an adaptive mapping, but its representations do not directly model feature interactions.Source: Compositional Representations · p. 2

Non-compositional Methods

  • TRANSE scores triples through distances between relation-specific translations, requiring few parameters and being easy to train but offering less modeling power.Source: Compositional Representations · pp. 2–3
  • RESCAL and HOLE differ in pair-representation width: RESCAL uses d^2 middle-layer components, whereas HOLE uses d.Source: Figure 1 · p. 3

Holographic Embeddings

HOLE uses circular correlation to represent entity pairs, combining tensor-product expressiveness with lower-dimensional, efficient computation. The resulting model is connected to holographic associative-memory methods and supports probabilistic relational learning.

  • HOLE represents entity pairs with circular correlation, combining the expressive power of tensor products with TRANSE-like efficiency and simplicity.Source: Holographic Embeddings · p. 3
  • HOLE estimates triple probabilities from correlated subject and object embeddings and relation embeddings, optimized with stochastic gradient descent.Source: Holographic Embeddings · pp. 3–4
  • Circular correlation compresses tensor-product interactions by summing fixed partitions, allowing relation embeddings to share weights across semantically similar interactions.Source: Holographic Embeddings · p. 3
  • Compared with the tensor product, circular correlation keeps composite representations at dimension d rather than increasing dimensionality, with linear memory complexity and quasilinear runtime.The runtime benefit follows from computation through the fast Fourier transform.Source: Holographic Embeddings · pp. 3–4
  • Circular correlation is non-commutative, enabling compositional representations for asymmetric relations, and includes a similarity component corresponding to the dot product.Source: Holographic Embeddings · p. 4

Associative Memory

HOLE is related to holographic associative memory, which stores and retrieves vector associations through circular convolution, correlation, and superposition. Unlike direct associative-memory storage, HOLE learns embeddings from observed graph data so the model can generalize.

  • Holographic reduced representations store an association between vectors through circular convolution and retrieve associated items using correlation.Source: Associative Memory · p. 4
  • Associative memory can store multiple vector associations through superposition and retrieve noisy versions that may be cleaned up by selecting the most similar stored item.Source: Associative Memory · p. 4
  • For relational data, object embeddings store subject-predicate associations, while correlated entity representations retrieve predicates associated with a subject-object pair.Source: Associative Memory · p. 4
  • HOLE differs from associative memory because it learns embeddings that explain observed data rather than directly storing given associations, yielding a defined form of generalization.Source: Associative Memory · p. 5
  • The model can estimate a probability distribution over possible knowledge-graph states and predict the probability of any possible triple.Source: Associative Memory · pp. 4–5

Experiments

HOLE was evaluated against established baselines on WN18, FB15k, and Countries tasks using filtered link-prediction and relational-learning protocols. It consistently performed strongly, including 93.0% Hits at 1 on WN18 and good performance on the hardest Countries task.

Link Prediction

  • HOLE was compared with RESCAL, TRANSE, TRANSR, and ER-MLP on WN18 and FB15k using fixed benchmark splits.The datasets contain 40,943 entities and 151,442 triples for WN18, and 14,951 entities and 592,213 triples for FB15k.Source: Knowledge Graphs · p. 5
  • 93.0% Hits at 1 was achieved by HOLE on WN18, compared with 11.5% for TRANSE and 33.5% for TRANSR.The evaluation used filtered ranking and reported mean reciprocal rank and Hits at n.Source: Knowledge Graphs · p. 5
  • HOLE consistently outperformed the considered baseline methods on both WN18 and FB15k.The authors selected hyperparameters using filtered MRR on validation data.Source: Knowledge Graphs · p. 5

Relational Learning

  • The Countries experiment tested prediction of locatedIn(c, r) using progressively harder settings with missing country, subregion, and neighbor-region edges.S1 used the easiest setting, S2 removed country-to-subregion triples, and S3 additionally removed neighbor-to-region triples.Source: Relational Learning · pp. 5–6
  • HOLE predicted S1 missing triples nearly perfectly and achieved very good results even on S3, the hardest task involving a neighborOf relation and a path of length 3.Performance was measured with area under the precision-recall curve.Source: Relational Learning · p. 6

Conclusion and Future Work

The paper concludes that HOLE combines expressive relational modeling with efficient, fixed-width representations. It reports strong benchmark performance and identifies extensions to higher-arity relations and facts about facts.

Conclusion

  • HOLE is a compositional vector space model for knowledge graphs based on circular correlation of entity and relation vectors.Circular correlation produces a compositional representation with the same dimensionality as its constituents.Source: Conclusion and Future Work · p. 6
  • Fixed-width representations allow HOLE to capture rich relational interactions while remaining efficient to compute, easy to train, and scalable.The conclusion also characterizes the model as economical in its number of parameters.Source: Conclusion and Future Work · p. 6
  • HOLE achieved state-of-the-art performance across benchmark datasets and modeled complex relational patterns economically in parameters.The conclusion summarizes results from knowledge-graph and relational-learning evaluations.Source: Conclusion and Future Work · p. 6

Future Work

  • The paper connects HOLE to holographic associative memory and discusses principled querying, including applications such as question answering.This connection links relational learning with associative-memory models.Source: Conclusion and Future Work · p. 6
  • Future work targets complex scenarios involving higher-arity relations and facts about facts.Examples include taughtAt(John, AI, MIT) and believes(John, ...).Source: Conclusion and Future Work · p. 6

Related papers

Loading 1510.04935v2…