Source-linked AI summary
Complex Embeddings for Simple Link Prediction
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, Guillaume Bouchard
TL;DR
Link prediction seeks to recover missing facts in large knowledge bases. This paper uses complex-valued embeddings with the Hermitian dot product, achieving systematic accuracy improvements over state-of-the-art alternatives on standard benchmarks.
Problem
Link prediction must recover unobserved facts from partially observed relational data while modeling diverse relation properties and scaling to large knowledge bases.
Method
The paper factorizes relations with complex-valued embeddings composed using the Hermitian dot product, which can represent antisymmetric relations efficiently.
Results
On standard benchmarks, the model systematically improves state-of-the-art accuracy, including filtered MRR 0.692 on FB15K versus 0.524 for HolE.
Takeaways & Limitations
Complex embeddings provide a simple factorization approach that improves link prediction performance on standard benchmarks without requiring further model modifications.
Takeaways & Limitations
The paper leaves open whether complex embeddings would similarly improve other dot-product models, such as deep neural networks.
Abstract
from arXiv · showhide
In statistical relational learning, the link prediction problem is key to automatically understand the structure of large knowledge bases. As in previous studies, we propose to solve this problem through latent factorization. However, here we make use of complex valued embeddings. The composition of complex embeddings can handle a large variety of binary relations, among them symmetric and antisymmetric relations. Compared to state-of-the-art models such as Neural Tensor Network and Holographic Embeddings, our approach based on complex embeddings is arguably simpler, as it only uses the Hermitian dot product, the complex counterpart of the standard dot product between real vectors. Our approach is scalable to large datasets as it remains linear in both space and time, while consistently outperforming alternative approaches on standard link prediction benchmarks.
1. Introduction
The introduction frames link prediction as a central Statistical Relational Learning problem for completing incomplete knowledge bases. It motivates complex embeddings as a simple, scalable representation for diverse relation patterns and previews large-scale benchmark experiments.
- Introduction: Link prediction aims to automatically discover regularities that fill missing entries in knowledge bases represented as directed graphs with labeled relations.Redundancies such as CityOfBirth can support inference of missing CountryOfBirth relations.
- Introduction: The task is commonly formulated as 3D binary tensor completion, using low-rank factorization or embeddings to produce fixed-dimensional entity representations.Each tensor slice corresponds to the adjacency matrix of one relation type.
- Introduction: Relational models must capture combinations of reflexivity, symmetry, antisymmetry, and transitivity while remaining linear in time and memory.These requirements support scaling to present-day knowledge bases and their growth.
- Introduction: Real-valued dot products handle symmetry and reflexivity naturally, but antisymmetric relations have generally required many more parameters, increasing overfitting risk.The introduction identifies balancing expressiveness against parameter-space size as a central modeling challenge.
- Introduction: The paper proposes complex embeddings with the Hermitian dot product as a simple composition function for representing diverse binary relations.The Hermitian dot product uses the conjugate-transpose of one complex vector.
- Introduction: The paper extends the complex-embedding formulation from one square relation matrix to third-order tensors with multiple relations and evaluates it on large-scale public benchmark knowledge bases.The introduction previews simpler and faster algorithms and an equivalent real-embedding reformulation for implementation without complex-number support.
2. Relations as Real Part of Low-Rank Normal Matrices
The paper represents relations through the real part of a complex low-rank factorization, using Hermitian products and unitary diagonalization to model both symmetric and antisymmetric structures. Under a low sign-rank assumption, this factorization can exactly reproduce any real square sign pattern with rank at most twice its sign-rank.
- Complex factorization: Complex eigenvalue decomposition handles antisymmetric relations that cannot be represented by real eigenvectors, using embeddings with real and imaginary components.The Hermitian product conjugates the first vector and provides a valid norm in the induced complex vector space.
- Normal matrices: Normal matrices are precisely the complex matrices that are unitarily diagonalizable, avoiding inversion of the eigenvector matrix.Their left and right embeddings share the same unitary basis.
- Real projection: Projecting the decomposition onto the real subspace exactly decomposes any real square matrix, while rows of the eigenvector matrix provide entity embeddings.For each entity, the subject embedding is the complex conjugate of its object embedding.
- Sign-rank and expressivity: If the observation matrix has low sign-rank, the model represents its sign pattern with a factorization whose rank is at most twice the sign-rank.This bound is useful because sign-rank can be much lower than ordinary matrix rank; for marriedTo, the model uses rank 6 for any n.
- Model properties: The factorization encompasses all binary relations and, by construction, accurately describes both symmetric and antisymmetric relations.Learnable relations are efficiently approximated through a simple low-rank factorization with complex latent factors.
3. Application to Binary Multi-Relational Data
The model extends complex-valued link prediction to multiple relation types by assigning each relation its own embedding while sharing entity embeddings across relations. Its scoring function represents relation matrices through symmetric and antisymmetric components, enabling both relation types with joint entity representations.
- Model extension: Each relation r receives a complex embedding w_r, while entity embeddings are shared across all relations.The model recovers score matrices X_r for all relations from partially observed true and false triples.
- Model extension: The scoring function predicts entries of the multi-relational score tensor X from observed triples and model parameters.Observed facts are represented as partially observed adjacency matrices across different relations, with the goal of predicting targeted entries.
- Scoring function: The model handles asymmetry by applying a complex conjugate to one entity embedding, generalizing DistMult with real embeddings.An equivalent formulation uses real vectors corresponding to the real and imaginary parts of entity and relation embeddings.
- Relation structure: The scoring function is antisymmetric when w_r is purely imaginary and symmetric when w_r is real.Separating Re(w_r) and Im(w_r) decomposes each relation matrix into symmetric and antisymmetric components.
- Relation structure: Relation embeddings weight latent dimensions for symmetric and antisymmetric relations while retaining joint entity representations for subject and object roles.Geometrically, each w_r anisotropically scales the entity-embedding basis before projection onto the real subspace.
4. Experiments
Experiments evaluate ComplEx on synthetic symmetry/antisymmetry data and the FB15K and WN18 knowledge-base benchmarks. ComplEx succeeds on the synthetic task and achieves strong ranking performance on both real datasets, especially for antisymmetric relations.
- Synthetic experiment: ComplEx is evaluated on a synthetic tensor containing one entirely symmetric and one completely antisymmetric relation.The tensor has two relations and 30 entities, with 1392 training triples and 174 validation and test triples each.
- Synthetic experiment: Only ComplEx succeeds on the combined synthetic symmetry and antisymmetry experiment, while DistMult, TransE, RESCAL, and CP fail on aspects of the task.DistMult cannot model antisymmetry, TransE performs poorly particularly on the antisymmetric relation, RESCAL overfits as rank grows, and CP struggles with both relations.
- Real-world benchmarks: ComplEx and HolE outperform DistMult and TransE on WN18, with filtered MRR scores of 0.941 and 0.938, respectively.WN18 contains many antisymmetric relations, including hypernymy, hyponymy, and being part of.
- Real-world benchmarks: On FB15K, ComplEx achieves a filtered MRR of 0.692 and 59.9% of Hits at 1, compared with 0.524 and 40.2% for HolE.ComplEx also exceeds DistMult’s filtered MRR of 0.654, while TransE and CP are largely left behind on the evaluated datasets.
- Training analysis: 0.737 filtered MRR and 64.8% of Hits@1 are obtained on FB15K with 100 generated negative triples per positive, before performance decreases with 200 negatives.More negatives also reduce the number of epochs needed for convergence up to 50 negatives, after which training time grows linearly with the number of negatives.
5. Related Work
Related work spans real-domain tensor factorization, pairwise interaction models, and neural or geometric approaches to relational prediction. Existing methods trade off symmetry handling, expressiveness, simplicity, and trainability in different ways.
- Factorization foundations: Traditional matrix and tensor factorization approaches primarily operated in the real domain, including the Canonical Polyadic decomposition.Complex-domain eigen-decomposition emerged later than early complex-free matrix factorization work.
- Pairwise interaction models: Universal Schema factorizes a 2D tensor unfolding of entity pairs versus relations, while later work extends pairwise interaction modeling to other pairs.These approaches were proposed to improve prediction performance.
- Neural tensor models: The Neural Tensor Network combines linear transformations and multiple bilinear forms with a nonlinear neural layer, increasing expressiveness over simpler scoring functions.Its large parameter count can make training harder and increase overfitting risk.
- Classical relational models: DistMult is symmetric in subject and object for every relation, whereas TransE embeds entities and relations together and imposes a translation-based geometric bias.DistMult achieves good performance, presumably due to its simplicity.
- Holographic embeddings: HolE addresses antisymmetry using circular correlation, whose dimension-shift covariance enables richer embedding interactions than classical tensor-product composition.The passage presents HolE as evidence that alternative composition functions can be useful.
6. Conclusion
The paper presents complex-valued matrix and tensor factorization for link prediction, using normal matrices and real-part scoring to model binary relations efficiently. It identifies extensions involving tensor-factorization methods, improved negative sampling, and complex embeddings in other dot-product models.
- Conclusion: Complex-valued vectors retain the standard dot-product definition for matrix and tensor factorization in link prediction.The approach is described as simple and applicable to link prediction data.
- Conclusion: Normal matrices naturally represent binary relations, while taking the real part efficiently approximates any learnable relation.The conclusion reports benchmark improvements over the state of the art without requiring additional modifications.
- Future directions: Combining complex embeddings with established tensor-factorization extensions, including pairwise embeddings, could improve predictive performance for non-compositional settings.This is proposed as a direction for further work rather than a demonstrated result.
- Future directions: A more intelligent negative-sampling procedure could generate more informative negatives.The passage introduces this as another possible extension.
- Future directions: Using complex embeddings wherever models include dot products, such as deep neural networks, is posed as an open question about systematic improvement.The passage asks whether similar gains would arise in these settings.
A. SGD algorithm
The ComplEx model is trained with SGD using only real-valued vectors, while preserving its complex formulation through separate real and imaginary embeddings. Training uses a sigmoid link function, L2-regularized negative log-likelihood, negative sampling, Adagrad, and validation-based early stopping.
- A. SGD algorithm: SGD trains ComplEx using only real-valued vectors, with two real embeddings for each entity and relation.The embeddings represent the real and imaginary parts separately, and the scoring function uses real vectors.
- A. SGD algorithm: The objective uses a sigmoid link function and minimizes the L2-regularized negative log-likelihood.The squared L2-norm of a complex vector equals the combined squared norms of its real and imaginary parts.
- A. SGD algorithm: Algorithm 1 updates parameters with Adagrad and stops early when filteredMRR or AP on the validation set decreases.The procedure takes learning rate α, embedding dimension k, regularization factor λ, negative ratio η, batch size b, maximum iterations m, and early-stopping interval s as inputs.
- A. SGD algorithm: When training data contains only positive triples, SGD generates η negatives per positive by corrupting its subject or object.Negative sampling follows the corruption procedure described in Bordes et al. (2013b).
B. WN18 embeddings visualization
PCA visualization of WN18 relation embeddings shows that DistMult clusters inverse relations together, whereas ComplEx spatially separates them and captures their direction.
- B. WN18 embeddings visualization: DistMult represents inverse relations with very close embeddings, reflecting shared semantics but not their direction.DistMult cannot model antisymmetry, so it captures the nature of opposite relations without distinguishing direction.
- B. WN18 embeddings visualization: PCA plots of WN18 relation embeddings show opposite relations clustered together by DistMult but correctly separated by ComplEx.The visualization uses the first four principal components and concatenates ComplEx’s real and imaginary parts.
- B. WN18 embeddings visualization: ComplEx spatially opposes inverse relations, especially in the third and fourth principal components.WN18’s hierarchical relations are generally antisymmetric and include inverse pairs such as hypernym/hyponym.