Source-linked AI summary
On the Equivalence of Holographic and Complex Embeddings for Link Prediction
Katsuhiko Hayashi, Masashi Shimbo
TL;DR
Knowledge graph completion seeks to add missing facts to incomplete knowledge graphs. This paper trains HolE in the frequency domain and analyzes its relationship to ComplEx. It establishes both a constrained ComplEx interpretation of spectral HolE and a conversion from complex embeddings to equivalent HolE embeddings.
Problem
Knowledge graph completion seeks to score unobserved triples in incomplete knowledge graphs according to how likely their relations are to hold.
Source: §1 · p. 1, §3.1 · p. 3Method
The paper trains HolE in the frequency domain and analyzes its relationship to ComplEx through conjugate symmetry and embedding conversion.
Source: §1 · p. 2Results
HolE’s scoring-function computation falls from O(n log n) to O(n), and spectral HolE is a conjugate-symmetric special case of ComplEx with a converse conversion to equivalent HolE embeddings.
Source: §6 · p. 8Takeaways & Limitations
Every set of complex embeddings can be converted to equivalent holographic embeddings, while spectral HolE corresponds to ComplEx under conjugate symmetry.
Source: §6 · p. 8
Abstract
from arXiv · showhide
We show the equivalence of two state-of-the-art link prediction/knowledge graph completion methods: Nickel et al's holographic embedding and Trouillon et al.'s complex embedding. We first consider a spectral version of the holographic embedding, exploiting the frequency domain in the Fourier transform for efficient computation. The analysis of the resulting method reveals that it can be viewed as an instance of the complex embedding with certain constraints cast on the initial vectors upon training. Conversely, any complex embedding can be converted to an equivalent holographic embedding.
1 Introduction
Knowledge graph completion addresses missing facts in incomplete knowledge graphs, and vector embeddings have become a scalable approach. The paper examines the connection between HolE and ComplEx, two methods reported to achieve state-of-the-art KGC performance.
1 Introduction
- The paper establishes a connection between holographic embeddings (HolE) and complex embeddings (ComplEx), two methods used for knowledge graph completion.The introduction describes both as simple methods achieving state-of-the-art KGC performance.Source: §1 · p. 1
- Training HolE entirely in the frequency domain reduces scoring-function computation from O(n log n) to O(n), where n is the embedding dimension.Source: §1 · p. 2
- Frequency-domain HolE is an instance of ComplEx when its initial vectors satisfy conjugate symmetry.Source: §1 · p. 2
- Conversely, every set of complex embeddings can be converted to equivalent real-vector holographic embeddings, with scoring functions equal up to scaling.Source: §1 · p. 2
2 Preliminaries
The preliminaries define the paper’s vector notation and circular operations, then describe how Fourier transforms support their computation. The original real vector space is termed the time domain, while the DFT space is the frequency domain.
2 Preliminaries
- The paper uses superscript T for transpose, overbars for complex conjugation, and Re(·) for real parts of complex values, vectors, and matrices.Source: §2 · p. 2
- Circular convolution is commutative, whereas circular correlation is generally noncommutative and can be written as convolution after reversing one vector.Source: §2 · p. 2
- Fourier transforms compute circular convolution through DFTs, elementwise multiplication, and an inverse DFT, with FFT-based computation taking O(n log n) time.Source: §2 · p. 2
- The paper calls the original real space the time domain and the complex space containing DFT vectors the frequency domain.Source: §2 · p. 3
3 Holographic embeddings for knowledge graph completion
Knowledge graph completion scores unobserved entity-relation triples to rank how likely they are to hold. HolE represents entities and relations with real vectors and scores triples using circular correlation.
3.1 Knowledge graph completion
- For unobserved triples, the scoring function should assign higher values when a relation is more likely to hold and lower values when it is less likely.The paper defines observed positive and negative triples with labels +1 and −1, respectively.Source: §3.1 · p. 3
- Knowledge graph completion can be viewed as link prediction on a directed graph whose nodes are entities and whose relation-labeled edges represent facts.Source: §3.1 · p. 3
3.2 Holographic embeddings (HolE)
- HolE learns real-valued n-dimensional vectors for entities and relations, then scores each triple using the entity vectors’ circular correlation and the relation vector.Source: §3.2 · p. 3
- HolE’s scoring function can be evaluated in O(n log n) time when circular correlation is computed using the Fourier-based method.Source: §3.2 · p. 3
4 Spectral training of HolE
The section develops direct frequency-domain training for HolE and explains how conjugate symmetry preserves valid real embeddings while retaining the original storage footprint.
4 Spectral training of HolE
- Training HolE directly from frequency vectors avoids FFT and inverse FFT, and computes the scoring function and required operations in O(n).Table 1 summarizes the time- and frequency-domain operation correspondences.Source: §4 · pp. 3–4, Table 1 · p. 4
4.1 Conjugate symmetry of spectral components
- A DFT is conjugate symmetric if and only if its corresponding time-domain vector is real.This condition also ensures the relevant dot products are real-valued.Source: §4.1 · p. 4
4.2 Vector initialization and update in frequency domain
- Conjugate-symmetric initial frequency vectors remain so under SGD updates, including the regularization contribution, keeping inverse-DFT embeddings real.The update operations preserve conjugate symmetry.Source: §4.2 · p. 5
4.3 Real-valued dot product
- When frequency vectors retain conjugate symmetry, their complex dot product is real, as follows from Parseval’s theorem.Source: §4.3 · p. 6
4.4 Space requirement
- A spectral HolE vector requires exactly n floating-point numbers, matching the original HolE storage and using half the storage of a general complex vector.The vector’s conjugate symmetry means only the first ⌊n/2⌋ components suffice, with specified components real.Source: §4.4 · p. 6
5 Relation to Trouillon et al.’s complex embeddings
The section relates ComplEx’s complex-valued scoring to spectral HolE, then establishes that each can be converted to an equivalent scoring model of the other. Spectral HolE corresponds to ComplEx with conjugate symmetry, while the reverse conversion yields real holographic embeddings.
5.1 Complex embeddings (ComplEx)
- ComplEx represents entities and relations with complex-valued vectors and scores triples using the real part of a complex dot product.Its relation matrix is constructed from entity embeddings and a diagonal matrix of relation embeddings; the real part ensures real-valued scores.Source: §5.1 · p. 6
5.2 Equivalence of holographic and complex embeddings
- Spectral HolE’s scoring function matches ComplEx’s because conjugate symmetry makes its complex dot product real.ComplEx extracts the real part; spectral HolE’s dot product is already real, so the real-part operator is redundant.Source: §5.2 · p. 7
- Every set of ComplEx embeddings can be converted into real holographic embeddings whose scores equal ComplEx scores up to a positive constant.The conversion constructs a conjugate-symmetric frequency representation and applies the inverse Fourier transform to obtain real vectors.Source: §5.2 · pp. 7–8
6 Conclusion
The conclusion presents frequency-domain training for HolE as a way to reduce scoring computation and establishes its equivalence with ComplEx. It also identifies natural-language applications as a direction for future investigation.
6 Conclusion
- Frequency-domain HolE training removes the need for FFT and inverse FFT, reducing scoring time from O(n log n) to O(n).With stochastic gradient descent, conjugate symmetry is preserved, ensuring that learned frequency vectors correspond to real-space holographic embeddings.Source: §6 · p. 8
- Spectral HolE is a conjugate-symmetry-constrained special case of ComplEx, and every set of complex embeddings can be converted to equivalent holographic embeddings.The conclusion summarizes the two directions of the equivalence.Source: §6 · p. 8
- The authors plan to investigate spectral HolE and ComplEx in applications such as semantic parsing and question answering.These systems can benefit from access to knowledge-graph information.Source: §6 · p. 8