Analogical Inference for Multi-Relational Embeddings

Hanxiao Liu; Yuexin Wu; Yiming Yang

Source-linked AI summary

Analogical Inference for Multi-Relational Embeddings

Hanxiao Liu, Yuexin Wu, Yiming Yang

arXiv:1705.02426v2May 6, 2017cs.LGcs.AIcs.CL

TL;DR

Large knowledge graphs are highly incomplete, while scalable analogical inference for completing their unobserved triples remains underdeveloped. The paper introduces a differentiable framework that explicitly models analogical structures and reports state-of-the-art benchmark results while supporting linear-time inference.

Problem
Large knowledge graphs are extremely large and inherently incomplete, making inference of unobserved triples from observed triplets a difficult research problem.
Method
The paper introduces a differentiable multi-relational embedding framework that explicitly models analogical structures using commuting families of normal relation matrices.
Results
The approach achieves state-of-the-art results on two popular benchmark datasets, outperforming many strong baselines in most cases.
Takeaways & Limitations
Analogical inference provides a framework for knowledge-base completion in which unobserved triples can be inferred by mirroring counterparts between analogous systems.
Takeaways & Limitations
The paper focuses on multi-relational inference for knowledge-base embedding and leaves applications to other machine-learning problems as future work.

Abstract

from arXiv · show

Large-scale multi-relational embedding refers to the task of learning the latent representations for entities and relations in large knowledge graphs. An effective and scalable solution for this problem is crucial for the true success of knowledge-based inference in a broad range of applications. This paper proposes a novel framework for optimizing the latent representations with respect to the \textit{analogical} properties of the embedded entities and relations. By formulating the learning objective in a differentiable fashion, our model enjoys both theoretical power and computational scalability, and significantly outperformed a large number of representative baseline methods on benchmark datasets. Furthermore, the model offers an elegant unification of several well-known methods in multi-relational embedding, which can be proven to be special instantiations of our framework.

1. Introduction

Knowledge graph embedding seeks latent entity and relation representations for inference over large, incomplete knowledge graphs. The paper identifies a gap in scalable, differentiable analogical inference and motivates completing missing triples by mirroring analogous systems.

Problem: Multi-relational embedding learns latent representations of entities and relations to support inference over knowledge graphs.Applications include question-answering, information retrieval, and natural language processing.
Problem: Real-world knowledge graphs are extremely large and incomplete, making inference of unobserved triples a difficult machine learning problem.
Research gap: Existing embedding research largely omitted rigorous analogical properties and algorithms for optimizing embeddings with respect to them.
Research gap: Analogical inference can complete unobserved triples in one system by mirroring known relational facts from an analogous system.The paper illustrates this intuition with the atom system as a miniature of the solar system.
Research gap: Earlier analogical reasoning models were mainly non-differentiable and difficult to scale to very large knowledge bases.The paper frames scalable statistical inference for large knowledge graphs as an unstudied challenge.
Research gap: The paper asks whether analogical structures can be formulated mathematically and incorporated into tractable objectives for very large knowledge graphs.

1. A new framework that, for the first time, explicitly

The paper introduces a framework that explicitly models analogical structures, supports differentiable and scalable inference, and unifies several representative embedding methods as restricted cases.

A new framework that, for the first time, explicitly: ANALOGY explicitly models analogical structures in multi-relational embedding and improves state-of-the-art performance on benchmark datasets.
A new framework that, for the first time, explicitly: Its differentiable algorithm performs analogical inference with scalability comparable to the fastest known relational embedding algorithms.
A new framework that, for the first time, explicitly: The framework unifies several representative embedding methods by showing that they are restricted versions that implicitly impose analogical properties.
A new framework that, for the first time, explicitly: The paper organizes its framework around linear-map formulations, commutative analogical structures, efficient inference, model unification, and benchmark experiments.

2. Related Background

The background formulates entities as vectors and relations as linear maps scored by a bilinear function. It motivates multiplicative relational modeling and introduces normal matrices as a well-behaved family with useful structural properties.

2.1. Notations: Entities use vector embeddings v, while each relation uses a matrix embedding W_r; both are learned from knowledge-base triplets.
2.2. Relations as Linear Maps: Each relation matrix transforms a subject representation toward the representation of its object.
2.2. Relations as Linear Maps: The model measures how well a triple fits using the inner product between the transformed subject and the object vector.
2.2. Relations as Linear Maps: Learning seeks high bilinear scores for valid triples and low scores for invalid triples.
2.2. Relations as Linear Maps: Multiplicative relation operators are richer than additive translations and align naturally with treating relations as predicate operators.
2.3. Normal Transformations: Normal matrices satisfy A^⊤A = AA^⊤ and provide a theoretically well-behaved family for relational modeling.They are unitarily diagonalizable and include diagonal and positive semi-definite matrices.
2.3. Normal Transformations: Different matrix subclasses support different relation patterns: symmetric matrices model symmetric relations, skew-symmetric matrices asymmetric relations, and rotation matrices bijections.
2.3. Normal Transformations: Circulant matrices are normal and commute, and have been used implicitly in holographic representations with Fourier-domain interpretations.

3. Proposed Analogical Inference Framework

The framework formalizes analogical structures in a latent semantic space by requiring equivalent relation paths to compose identically. It incorporates these constraints into a differentiable embedding objective for scalable inference.

Analogical Structures: Analogical reasoning is formulated as structure-preserving inference over entity and relation embeddings in a latent semantic space.The paper uses analogies such as “man is to king as woman is to queen” to motivate this formulation.
Analogical Structures: A parallelogram represents an analogy whose edges are linear maps, with two paths connecting the same starting and ending entities.The diagram differs from a geometric parallelogram because its edges are relation maps rather than vector differences.
Commutative Constraint for Linear Maps: Although enumerating all entity analogies is intractable, constraining relation maps provides a tractable way to model desirable analogical structures.The paper also notes that commuting normal relations remain closed under multiplication, unlike the full family of normal matrices.
Commutative Constraint for Linear Maps: The framework restricts relation maps so that paths with identical endpoints have equivalent compositions, called the commutativity property.Relation composition is implemented through matrix multiplication, so commutativity becomes a matrix constraint.
The Optimization Objective: ANALOGY learns embeddings with a standard positive-versus-negative triple objective plus constraints requiring relation maps to form a commuting family of normal matrices.The constrained objective is later recast so each stochastic-gradient update can be performed in O(m) time.

4. Efficient Inference Algorithm

The efficient algorithm exploits the shared block structure of commuting normal relation matrices. This removes the costly constraints from direct optimization while preserving the same triple scores.

Efficient Inference Algorithm: Direct optimization is challenging because it combines a large tensor of parameters with matrix-normality and quadratic pairwise commutativity constraints.These constraints make the original formulation computationally demanding for large embedding models.
Efficient Inference Algorithm: Commuting real normal matrices can be simultaneously block-diagonalized by a shared real orthogonal basis.Each resulting diagonal block is either a real scalar or a 2-dimensional real block.
Efficient Inference Algorithm: The dense relational matrices therefore have equivalent sparse almost-diagonal representations in the common basis.This canonical form reduces the number of free relation parameters while preserving the commuting structure.
Efficient Inference Algorithm: For any solution of the original optimization, an alternative embedding set in the transformed basis produces identical scores for every triple.The alternative formulation is supplied by Corollary 4.2.1.
Efficient Inference Algorithm: Binding coefficients within each 2 × 2 block leaves only m free relation parameters and enables O(m) gradient evaluation per triple.The reduced parameterization also handles the alternative formulation’s constraints directly.

5. Unified View of Representative Methods

ANALOGY provides a unified framework in which several representative embedding models appear as restricted versions that implicitly impose analogical properties. The framework recovers DistMult and ComplEx exactly under specific dimensional settings and relates HolE to ComplEx through the Fourier domain.

ANALOGY unifies DistMult, ComplEx, and HolE as restricted versions that implicitly impose analogical properties.This unification is presented as an explanation for their strong empirical performance.
5.1. DistMult: DistMult embeddings can be fully recovered by ANALOGY when n = m.
5.1. DistMult: DistMult encourages entity analogies through normal, mutually commutative diagonal relation matrices but models only symmetric relations.Its score function is invariant under exchanging subject and object.
5.2. ComplEx: ComplEx embeddings of size m can be fully recovered by ANALOGY of size 2m when n = 0.The construction recasts complex embeddings as real embeddings with doubled dimensionality.
5.3. HolE: HolE uses circular correlation, which yields circulant relation matrices that are normal and mutually commutative, thereby encouraging entity analogies.The resulting optimization becomes unconstrained when all relation matrices are circulant.
5.3. HolE: HolE is equivalent to ComplEx with minor relaxation: restricting complex embeddings to F(R^m) gives HolE, while relaxing that restriction gives ComplEx.

6. Experiments

The experiments evaluate ANALOGY and diverse multi-relational embedding baselines on FB15K and WN18. The comparison spans translation, latent-factor, neural, pathwise, analogical-framework, and externally enhanced models.

6.1. Datasets: ANALOGY and baselines are evaluated on FB15K for generic facts and WN18 for lexical relationships between words.Both are benchmark datasets released in previous work.
6.2. Baselines: The benchmark comparison includes translation-based models such as TransE and its variants.
6.2. Baselines: Latent-factor, neural-network, and pathwise models form additional baseline categories.Examples include LFM, RESCAL, neural tensor networks, PTransE-RNN, and PTransE variants.
6.2. Baselines: DistMult, ComplEx, and HolE are included as models subsumed under the proposed framework and viewed as implicitly leveraging analogical structures.
6.2. Baselines: Node+LinkFeat represents models enhanced with external side information derived from textual mentions in ClueWeb.

6.3. Evaluation Metrics

The evaluation uses ranked-list metrics averaged over test instances, with filtered and raw variants distinguished by whether known training and validation triples are removed. Hits@10 is supplemented by MRR, Hits@1, and Hits@3.

Hits@k and Mean Reciprocal Rank evaluate each system-produced ranked list and average scores across test instances.
Filtering removes training- and validation-set triples from test ranked lists to avoid flawed negative-instance evaluation.“Filt.” denotes filtered metrics, whereas “raw” denotes metrics without filtering.
The first experiments use Hits@10, while additional comparisons report MRR, Hits@1, and Hits@3.The additional metrics support comparison with methods whose published results use those measures.

6.4. Implementation Details

ANALOGY is trained with logistic loss, asynchronous CPU-based SGD, and artificially generated corrupted triples. Hyperparameters are selected by validation MRR, and training runs for 500 epochs.

6.4.1. Training Objective: ANALOGY uses logistic loss throughout the experiments.The authors report that this simple loss performs reasonably well relative to more sophisticated ranking losses.
6.4.2. Optimization: The CPU implementation uses lightweight linear algebra routines and asynchronous stochastic gradient descent across multiple threads.Gradients are evaluated on different mini-batches simultaneously without synchronizing shared-parameter updates.
6.4.3. CREATION OF NEGATIVE SAMPLES: For each positive triple, three negative instances are generated by corrupting its subject, relation, or object.The positive and negative instances together define the SGD data distribution.
6.4.4. HYPERPARAMETER SETTINGS: Hyperparameters are selected by grid search to maximize filtered validation MRR, with embedding size m ∈ {100, 150, 200}, λ ∈ {10^-1, 10^-2, 10^-3}, and α ∈ {3, 6}.The selected embedding size is m = 200 for both WN18 and FB15K.
6.4.4. HYPERPARAMETER SETTINGS: Both datasets use an initial learning rate of 0.1, AdaGrad adjustment, and 500 training epochs.

6.5. Results

ANALOGY achieves strong benchmark performance while remaining empirically scalable with a linear relationship to embedding problem size. Its asynchronous implementation also provides substantial multithreaded speedups.

Benchmark performance: ANALOGY performs best or statistically equivalent to the best in both benchmark tables.On FB15K, it outperforms all baseline methods in Table 2.
Benchmark performance: ANALOGY outperforms DistMult, ComplEx, and HolE across all reported metrics in Table 3.These methods are described as more constrained versions of ANALOGY.
Scalability: ANALOGY completes an epoch in a few seconds on both datasets and scales linearly with embedding problem size.Figure 3 varies embedding size with 16 CPU threads and varies thread count at embedding size 200.
Scalability: 11.4x and 8.3x speedups are achieved over single-threaded AdaGrad on FB15K and WN18, respectively, using 16 CPU threads.The measurements were obtained on a single commercial desktop.
Evaluation protocol: Statistical significance testing was applied only to proportional metrics such as Hits@k, not to nonproportional metrics such as MRR.The reported tests used a one-sample proportion test at the 5% p-value level.

7. Conclusion

The paper presents ANALOGY as a scalable framework for analogical structure modeling in knowledge-graph embeddings. It reports state-of-the-art benchmark results while identifying broader applications of analogical inference as future work.

Conclusion: The framework explicitly models analogical structures with a differentiable objective and a linear-time inference algorithm.The design targets large-scale knowledge-graph embedding.
Conclusion: ANALOGY achieves state-of-the-art results on two popular benchmark datasets and outperforms many strong baselines in most cases.
Scope and future work: The study focuses on multi-relational inference for knowledge-base embedding, leaving applications such as machine translation and image captioning for future work.