PaperlayerView exact revision on arXiv

Source-linked AI summary

Knowledge Graph Completion via Complex Tensor Factorization

Théo Trouillon, Christopher R. Dance, Johannes Welbl, Sebastian Riedel, Éric Gaussier, Guillaume Bouchard

arXiv:1702.06879v2cs.AIcs.LGmath.SPstat.ML

TL;DR

Knowledge graph completion requires predicting missing relationships while balancing expressive relation modeling against time and space complexity. The paper introduces ComplEx, a complex-valued factorization using a Hermitian dot product, and theoretically connects it to unitary diagonalization. The authors report that the decomposition covers all real square matrices, supports symmetric and asymmetric relations, remains scalable, and substantially improves over state-of-the-art methods on real knowledge graphs.

  • Problem

    Knowledge graph completion needs models that capture diverse relation patterns, including asymmetric ones, without sacrificing linear time and space scalability.

  • Method

    ComplEx factorizes relation data with complex-valued entity and relation embeddings using a Hermitian dot product and extends the formulation to multiple relations.

  • Results

    The decomposition exists for all real square matrices, extends to tensor sets of matrices, and substantially improves over the state-of-the-art on real knowledge graphs.

  • Takeaways & Limitations

    Complex-valued embeddings provide a scalable factorization that represents symmetric, antisymmetric, and asymmetric relation patterns with low-rank approximations.

  • Takeaways & Limitations

    The multi-relation existence question is presented as open, and the approach assumes observed data has sufficient regularity for low-rank generalization.

Abstract

from arXiv · show

In statistical relational learning, knowledge graph completion deals with automatically understanding the structure of large knowledge graphs---labeled directed graphs---and predicting missing relationships---labeled edges. State-of-the-art embedding models propose different trade-offs between modeling expressiveness, and time and space complexity. We reconcile both expressiveness and complexity through the use of complex-valued embeddings and explore the link between such complex-valued embeddings and unitary diagonalization. We corroborate our approach theoretically and show that all real square matrices---thus all possible relation/adjacency matrices---are the real part of some unitarily diagonalizable matrix. This results opens the door to a lot of other applications of square matrices factorization. Our approach based on complex embeddings is arguably simple, as it only involves a Hermitian dot product, the complex counterpart of the standard dot product between real vectors, whereas other methods resort to more and more complicated composition functions to increase their expressiveness. The proposed complex embeddings are scalable to large data sets as it remains linear in both space and time, while consistently outperforming alternative approaches on standard link prediction benchmarks.

1. Introduction

Knowledge graph completion predicts missing relationships in structured, labeled graphs, but useful models must balance relational expressiveness with scalable time and memory use. The paper proposes complex-valued embeddings with a Hermitian dot product to represent broader relation patterns while retaining efficient factorization.

  • Motivation: Knowledge graph completion predicts missing labeled edges by learning regularities in directed graphs of entities and relations.The task is motivated by incomplete knowledge graphs and supports applications such as recommender systems, question answering, and automated personal agents.
  • Existing approaches: Embedding-based factorization completes partially observed matrices or tensors using lower-dimensional representations of entities and relations.A fact score is recovered from a multilinear product involving the corresponding embeddings.
  • Modeling requirements: Relational models must learn combinations of symmetry, antisymmetry, reflexivity, irreflexivity, and transitivity while remaining linear in time and memory.Knowledge graphs contain patterns including hierarchies, compositions, and equivalence relations.
  • Modeling requirements: Existing approaches often handle asymmetric relations with superlinear time and space complexity, creating a trade-off among expressiveness, generalization, and scalability.The paper identifies this trade-off as a central challenge for embedding models.
  • Proposed approach: ComplEx uses complex-valued embeddings and a Hermitian dot product, whose conjugation makes the score asymmetric and supports richer relation modeling.The method retains the standard dot-product form while changing the representation from real to complex numbers.
  • Paper scope: The paper extends the matrix formulation to stacked relation matrices, provides existence and rank results, details stochastic-gradient training, and evaluates training time.The extended version adds proofs for single- and multi-relational settings and reports additional experiments.

2. Relations as the Real Parts of Low-Rank Normal Matrices

The paper represents real relation matrices as real parts of complex, unitarily diagonalizable factorizations. This construction supports symmetric and antisymmetric patterns while retaining low-rank complex embeddings, subject to rank and identifiability qualifications.

  • Motivation and representation: Complex-valued embeddings use Hermitian structure to represent asymmetric relations with unique entity representations.The conjugate of the object embedding makes the scoring function asymmetric while preserving a shared entity embedding scheme.
  • Complex-domain decomposition: Every real square matrix is the real part of a normal complex matrix and therefore admits a unitary-diagonalization representation.The result is formalized as X = Re(EWE∗), with E unitary and W diagonal.
  • Asymmetry and unique embeddings: Varying a complex relation parameter can assign any desired pair of scores to x_so and x_os, unlike the corresponding real diagonal formulation.The real-valued case forces x_so = x_os, whereas the complex-valued case separates the two directions.
  • Qualifications: The decomposition is non-unique, and its unitary-diagonalization rank bound can strictly exceed the original matrix rank or sign-rank.Some examples require rank greater than k, although adding an imaginary component may sometimes reduce rank through additional linear dependence.
  • Rank bounds: A rank-k real square matrix can be reconstructed with a 2k-dimensional unitary diagonalization, and a sign-rank-k matrix with rank at most 2k.For sign matrices, the construction is Y = sign(Re(EWE∗)).
  • Summary: The factorization encompasses all single-relation score matrices and is designed to approximate relation patterns efficiently with complex-valued low-rank embeddings.The paper summarizes the construction as supporting all score matrices, symmetric and antisymmetric relations, and efficient low-rank approximation.

3. Extension to Multi-Relational Data

ComplEx jointly factorizes multiple relation score matrices using shared complex entity embeddings and relation-specific diagonal embeddings. Its real-valued scores can represent both symmetric and antisymmetric relations, while existence results establish broad factorization coverage.

  • Multi-relational model: ComplEx jointly factorizes a score tensor with relation-specific diagonal matrices while sharing entity embeddings across relations.The score tensor has one square matrix per relation, with a distinct diagonal relation embedding and common entity matrix.
  • Multi-relational model: The Hermitian formulation handles asymmetry through conjugating the object-entity embedding, unlike real-valued DistMult.The same entity representations remain usable for subjects and objects.
  • Symmetry structure: The real and imaginary parts of each relation embedding weight symmetric and antisymmetric components of the score.Re(w_r) weights the symmetric component, while Im(w_r) weights the antisymmetric component.
  • Symmetry structure: Purely real relation embeddings produce symmetric score matrices, whereas purely imaginary relation embeddings produce antisymmetric score matrices.Learning can suppress the imaginary or real relation component according to the desired relation type.
  • Existence and rank: Whether a single unitary matrix with at most n columns can represent arbitrary multiple real square matrices remains open.The authors describe this as unresolved and suggest it may be unlikely.
  • Existence and rank: The multi-relational decomposition exists at rank K ≤ nm by concatenating per-relation decompositions, while practical rank may be lower through sign-rank and shared latent dimensions.When m ≤ n, nm matches the general CP rank upper bound, and real-world knowledge graphs typically satisfy m < n.

4. Algorithm

The ComplEx learning algorithm uses stochastic gradient descent with AdaGrad to optimize a regularized logistic objective. It implements complex embeddings as separate real and imaginary vectors, with negative sampling and validation-based early stopping.

  • Optimization: ComplEx is learned with stochastic gradient descent and AdaGrad, using separate real-valued vectors for complex embedding parts.The algorithm outputs real and imaginary entity and relation representations.
  • Sampling: When training data contain only positive triples, negatives are generated by randomly replacing the subject or object under a local closed-world assumption.The negative ratio η controls how many negatives are generated per positive triple.
  • Validation: AdaGrad accumulates squared gradients, while validation periodically evaluates average precision or mean reciprocal rank for early stopping.Average precision is used with observed negatives; mean reciprocal rank is used when only positives are available.
  • Representation: For each entity and relation, the scoring function uses two real embeddings corresponding to the real and imaginary parts of the complex representation.This real-valued reformulation preserves the complex model’s scoring structure.
  • Optimization: The objective is the negative log-likelihood of a logistic model with L2 regularization on the parameters.The gradient combines the logistic loss gradient with an L2 penalty term.

5. Experiments

The paper evaluates ComplEx on synthetic and real knowledge-graph data and compares it with several established factorization and embedding models. The comparisons use a shared implementation framework, with model-specific training choices where needed.

  • Evaluation design: Experiments cover synthetic data containing symmetric and antisymmetric relations and standard link-prediction benchmarks from real knowledge graphs.This evaluation spans controlled relational structure and real-world completion tasks.
  • Baselines: ComplEx is compared with TransE, DistMult, RESCAL, and CP to assess relational modeling and the value of shared entity embeddings.The baselines were reimplemented within the same Theano-based stochastic-gradient framework.
  • Training protocol: TransE uses its original max-margin loss, while the other models use the logistic negative log-likelihood objective.Positive triples are replicated when necessary to match negative counts for datasets with observed negatives.
  • Training protocol: Models are validated for early stopping every s = 50 iterations.The reported protocol evaluates models periodically during training.

5.1 Synthetic Task

The synthetic experiment tests whether models can jointly represent one symmetric and one antisymmetric relation. ComplEx is designed for this setting, whereas the reported baselines exhibit specific failures or overfitting.

  • Task construction: The synthetic graph contains 2 relations and 30 entities: one entirely symmetric relation and one completely antisymmetric relation.The data form a 2 × 30 × 30 tensor, with test values arranged to be predictable from training information.
  • Results: DistMult models the symmetric relation but cannot model antisymmetry.Its limitation follows from the symmetry of its real-valued scoring formulation.
  • Results: TransE performs poorly in practice, particularly on the antisymmetric relation, despite not being intrinsically symmetric.Its lack of symmetry alone does not yield strong performance on this task.
  • Results: RESCAL quickly overfits as rank increases because it uses a large number of parameters, while CP fails on both relations.The reported failures distinguish parameter overfitting from inability to handle the mixed relational structure.
  • Task construction: Figure 2 encodes positive triples in red, negatives in blue, and missing entries in green for symmetric and antisymmetric slices.The top plots show the symmetric slice and the bottom plots show the antisymmetric slice for the first 10 entities.

5.2 Real Fully-Observed Data Sets: Kinships and UMLS

The evaluation compares ComplEx with state-of-the-art models on fully observed Kinships and UMLS data sets across factorization ranks up to 50. ComplEx is competitive with CP and RESCAL, while DistMult performs poorly on these antisymmetry-rich relations.

  • Data sets: Kinships contains 26 kinship relations among 104 individuals, while UMLS contains 49 relations linking 135 medical concepts and diseases.
  • Evaluation: The experiments use 10-fold cross-validation with eight folds for training, one for validation, and one for testing.
  • Results: ComplEx, RESCAL, and CP perform very similarly, with ComplEx slightly ahead on Kinships and RESCAL slightly ahead on UMLS.
  • Results: DistMult performs poorly because many UMLS and Kinships relations are antisymmetric, including causal links, anatomical hierarchies, father, uncle, and grandfather relations.
  • Evaluation: Average precision is reported across factorization ranks from 5 to 50 for different state-of-the-art models on Kinships and UMLS.
  • Interpretation: Under the closed-world assumption, CP performs well, whereas unique entity embeddings become important for generalization when only a fraction of positive examples is observed.

5.3 Real Sparse Data Sets: FB15K and WN18

ComplEx is evaluated on FB15K and WN18 using filtered ranking metrics, where it performs strongly on datasets containing antisymmetric relations. Its performance gains persist without requiring substantially higher ranks, while training choices such as negative sampling and regularization materially affect results.

  • Results: ComplEx outperforms DistMult and TransE on WN18, while matching HolE with filtered MRR scores of 0.941 and 0.938, respectively.WN18 contains many antisymmetric relations, including hypernymy and hyponymy.
  • Results: ComplEx’s advantage on WN18 is confirmed for antisymmetric relations while performance is retained on other relations.PCA projections of the relation embeddings visually corroborate the comparison with DistMult.
  • Results: 0.692 filtered MRR and 59.9% Hits at 1 for ComplEx exceed HolE’s 0.524 filtered MRR and 40.2% Hits at 1 on FB15K.The reported gap is attributed to the loss function and negative-sampling settings used in the compared experiments.
  • Rank and optimization: Filtered MRR converges quickly as rank increases, with little performance gain between ranks 50 and 200.This supports the practical adequacy of the low-rank hypothesis and indicates that the gains are linked to expressiveness rather than simply doubled real and imaginary parameters.
  • Rank and optimization: Increasing negative samples from 1 to 10 improves FB15K filtered MRR by up to 0.08, while regularization improves filtered MRR by up to 0.05 on both datasets.Negative-sample count had little effect on WN18, and the best ranks were generally 150 or 200.

5.4 Training time

The training-time analysis contrasts models with linear complexity against RESCAL’s quadratic rank dependence. RESCAL remains manageable on WN18 but becomes substantially slower and more memory-intensive on FB15K as the number of relations grows.

  • Complexity: All evaluated models except RESCAL have linear complexity, whereas RESCAL has quadratic complexity in decomposition rank.RESCAL learns one matrix per relation, increasing its computational and memory demands.
  • Convergence: On WN18, all models converge within 15 minutes to 1 hour and 20 minutes.RESCAL’s gap is limited because its optimal rank is lower and WN18 contains only 18 relations.
  • FB15K scaling: RESCAL takes more than four days to train on FB15K, compared with 40 minutes to 3 hours for the other models.The result is presented as experimental support for linear complexity as datasets scale beyond FB15K.
  • Negative sampling: Figure 7 shows that increasing negative triples improves FB15K performance up to 100 negatives, reaching 0.737 filtered MRR and 64.8% Hits@1 before declining at 200.The model converges in fewer epochs, partially offsetting the additional per-epoch training time up to 50 negatives.
  • Embedding structure: ComplEx relation embeddings separate opposite WN18 relations, whereas DistMult clusters them together in PCA projections.WN18’s hierarchical relations are often antisymmetric and include inverse pairs.

6. Related Work

Related work spans matrix and tensor factorization, probabilistic relational models, neural architectures, and embedding methods for handling relational structure. The paper positions complex-valued representations as a simple way to increase expressiveness while retaining efficient scoring.

  • Paper positioning: Unlike prior uses that encode complex-valued inputs, this work applies complex representations directly to real-valued data and projects the result onto the real-valued subspace.The paper presents this as a simple route to increased model expressiveness.
  • Knowledge graph models: Earlier factorization and embedding models address missing links through low-dimensional entity and relation representations, but differ in their treatment of asymmetry and complexity.Approaches include CP, RESCAL, DistMult, TransE, and HolE.
  • Complexity trade-offs: RESCAL and NTN provide expressive relation modeling but incur quadratic complexity in the factorization rank, while HolE offers quasi-linear time and linear space complexity.DistMult handles only symmetric relations, and TransE imposes strong geometric constraints on embeddings.
  • Asymmetry: DistMult is symmetric in subject and object for every relation, limiting its ability to represent antisymmetric relations.Its strong benchmark performance is discussed in connection with datasets lacking true negative facts.
  • Related embeddings: HolE uses circular correlation and has been shown to be equivalent to ComplEx.This provides a direct connection between the two models despite their different formulations.

7. Discussion and Future Work

The discussion identifies broader applications for the proposed decomposition while emphasizing unresolved questions about uniqueness and optimization. Future work includes combining complex embeddings with richer factorization extensions and improving negative sampling.

  • Open theory: All unitary diagonalizations preserving the real part are not yet characterized, especially for constrained-rank approximations minimizing reconstruction error.The paper identifies this characterization as an open question because the decomposition is not unique.
  • Applications: The decomposition may apply to asymmetric square-matrix problems such as directed-graph spectral analysis and asymmetric distance or similarity matrices.These applications extend beyond knowledge graph completion.
  • Optimization: The non-convex objective means stochastic gradient descent may fail to reach a globally optimal decomposition.The observed stability across random initializations suggests, but does not establish, a related theoretical property.
  • Future work: Future extensions include combining complex numbers with pairwise or bigram embeddings and developing more informative negative-sampling procedures.The stated goal of improved negative sampling is to reduce the number of negatives needed for good performance and accelerate training.
  • Future work: Extending ComplEx to relations among more than two entities is not straightforward because conjugating the object embedding breaks subject–object symmetry.The paper links this difficulty to the lack of a standard multilinear extension of the Hermitian product.

8. Conclusion

ComplEx uses complex-valued latent factors to decompose matrices and tensors, covering all real square matrices through the real parts of normal matrices. The approach supports antisymmetric and asymmetric relations, remains scalable, and substantially improves over state-of-the-art methods on real knowledge graphs.

  • 8. Conclusion: ComplEx is a matrix and tensor decomposition with complex-valued latent factors.The decomposition extends from matrices to sets of real square matrices, namely tensors.
  • 8. Conclusion: Every real square matrix can be expressed as the real part of a normal matrix.This theoretical result also applies to sets of real square matrices.
  • 8. Conclusion: ComplEx handles antisymmetric and asymmetric relations while remaining scalable for knowledge graph completion.The method is described as efficiently approximating real-world relations with low-rank normal matrices.
  • 8. Conclusion: Experiments show substantial improvement over state-of-the-art methods on real knowledge graphs.
Loading 1702.06879v2…