PaperlayerView exact revision on arXiv

Source-linked AI summary

Generalizing Knowledge Graph Embedding with Universal Orthogonal Parameterization

Rui Li, Chaozhuo Li, Yanming Shen, Zeyu Zhang, Xu Chen

arXiv:2405.08540v1cs.LGcs.AI

TL;DR

Knowledge graph embedding uses orthogonal relation transformations to model logical patterns and topology, but existing approaches are restricted in dimension and geometry. GoldE provides a universal orthogonal parameterization based on generalized Householder reflection, and is reported to outperform state-of-the-art baselines across three standard benchmarks.

  • Problem

    Existing orthogonal relation transformations are restricted in dimension and homogeneous geometry, despite knowledge graphs containing heterogeneous topologies.

    Source: §1 · pp. 1–2

  • Method

    GoldE uses generalized Householder reflection to parameterize orthogonal transformations across Euclidean, elliptic, and hyperbolic geometries and unify them in a product manifold.

    Source: §1 · p. 2, §3.1 · pp. 3–4

  • Results

    GoldE consistently outperforms current state-of-the-art baselines across all three standard benchmarks.

    Source: §1 · p. 2

  • Takeaways & Limitations

    GoldE's parameterization is designed to capture logical patterns and heterogeneous topologies through dimensional extension and geometric unification.

    Source: §1 · p. 2

    GoldE models training triples independently, and accumulated optimization biases over relation hops can make perceived logical patterns unreliable and hinder generalization.

    Source: K. Limitations and Future Work · p. 20

Abstract

from arXiv · show

Recent advances in knowledge graph embedding (KGE) rely on Euclidean/hyperbolic orthogonal relation transformations to model intrinsic logical patterns and topological structures. However, existing approaches are confined to rigid relational orthogonalization with restricted dimension and homogeneous geometry, leading to deficient modeling capability. In this work, we move beyond these approaches in terms of both dimension and geometry by introducing a powerful framework named GoldE, which features a universal orthogonal parameterization based on a generalized form of Householder reflection. Such parameterization can naturally achieve dimensional extension and geometric unification with theoretical guarantees, enabling our framework to simultaneously capture crucial logical patterns and inherent topological heterogeneity of knowledge graphs. Empirically, GoldE achieves state-of-the-art performance on three standard benchmarks. Codes are available at https://github.com/xxrep/GoldE.

1. Introduction

Knowledge graph embedding predicts missing links in incomplete knowledge graphs, and orthogonal relation transformations have been used to model logical patterns and topology. GoldE addresses restrictions in dimension and geometry with a universal parameterization, and is reported to outperform state-of-the-art baselines across three benchmarks.

1. Introduction

  • Knowledge graphs organize factual triples, but real-world graphs can be incomplete; knowledge graph embedding learns entity and relation representations to predict missing links.The paper identifies logical patterns and topological structures, including cyclicity and hierarchy, as central modeling targets.Source: §1 · p. 1
  • Existing orthogonal approaches extend dimension only in Euclidean geometry, constrain hyperbolic orthogonalization to low dimensions, and assume homogeneous geometry despite topological heterogeneity in knowledge graphs.The paper frames the challenge as generalizing orthogonal transformations across both dimension and geometry.Source: §1 · pp. 1–2, Table 1 · p. 2
  • GoldE uses generalized Householder reflections to parameterize Euclidean, elliptic, and hyperbolic orthogonal transformations, then combines geometric types in a product manifold.The framework is presented as enabling dimensional extension and geometric unification to model logical patterns and heterogeneous topologies.Source: §1 · p. 2
  • GoldE consistently outperforms current state-of-the-art baselines across all three standard benchmarks.The reported experiments assess its universal orthogonal parameterization.Source: §1 · p. 2

2. Preliminaries

The preliminaries define knowledge graph embedding as representing entities and relations to score factual triples, with link prediction as an application. They also introduce elliptic and hyperbolic geometric settings and illustrate their relation-specific forms.

2.1. Problem Setup

  • A knowledge graph is a collection of factual triples, and knowledge graph embedding represents entities and relations to score triple plausibility and infer missing links.Each triple denotes a relation between a head entity and a tail entity.Source: §2.1 · p. 2

2.2. Geometric Background

  • With an all-ones weighting vector, the elliptic inner product becomes Euclidean and the ellipsoid specializes to a hypersphere.The geometric background also defines elliptic settings using positive weighting vectors.Source: §2.2 · p. 2
  • The geometric background uses the hyperboloid model for hyperbolic space, with a Lorentz inner product whose first coordinate has weight −1 and remaining coordinates +1.The paper cites simplicity and numerical stability as its reasons for choosing this model.Source: §2.2 · p. 2
  • Figure 2 depicts generalized Householder reflection and elliptic and hyperbolic orthogonal parameterizations in two dimensions.Its reflection illustration contrasts Euclidean, elliptic, and hyperbolic weighting choices.Source: Figure 2 · p. 3

3. Methodology

This section presents GoldE’s universal orthogonal parameterization, which extends relation transformations across arbitrary dimensions and unifies Euclidean, elliptic, and hyperbolic geometries. It describes combining these geometries to represent heterogeneous knowledge-graph structures.

3.1. Generalized Orthogonal Matrix and Mapping

  • Generalized Householder reflections preserve a weighted quadratic inner product, and their mapping spans every generalized orthogonal matrix when the number of reflections equals the dimension.Choosing the weighting vector specializes the framework to Euclidean, elliptic, or hyperbolic spaces.Source: §3.1 · pp. 3–4

3.2.1. ELLIPTIC ORTHOGONAL PARAMETERIZATION

  • Elliptic parameterization gives each relation a learnable weighting vector, extending Euclidean orthogonal models to arbitrary dimensions with relation-specific element-wise scaling.The Euclidean models are special cases when the weighting vectors are set to 1.Source: §3.2.1 · p. 4

3.2.2. HYPERBOLIC ORTHOGONAL PARAMETERIZATION

3.2.3. MIXED ORTHOGONAL PARAMETERIZATION

  • GoldE combines elliptic and hyperbolic component spaces in a product manifold, enabling relation transformations across geometries and representations suited to heterogeneous KG structures.Component-wise invariance keeps transformed embeddings in the product space, where distances are computed by decomposition; the framework is claimed to capture symmetry, antisymmetry, inversion, composition, cyclicity, and hierarchy.Source: §3.2.3 · pp. 5–6

3.3. Optimization

  • GoldE is optimized with self-adversarial negative sampling and standard Euclidean optimization, enabled by differentiable, bijective relation transformations.The entity embeddings are initialized in Euclidean space for numerical stability.Source: §3.3 · p. 6

4.1. Experimental Setup

  • The experiments evaluate link prediction on WN18RR, FB15k-237, and YAGO3-10 against non-orthogonal, Euclidean orthogonal, and hyperbolic orthogonal KGE baselines.The stated experimental questions also examine geometry and dimension effects, relation-type modeling, and performance under restricted embedding size.Source: Datasets · p. 6, §4 · p. 6

4.2. Performance Comparison

  • GoldE outperforms baselines across all metrics on three datasets, gaining 2.5% average absolute MRR over HousE and 1.3% over HousE-pro.The paper also reports that GoldE outperforms the hyperbolic orthogonal models RefH, RotH, and AttH by a clear margin.Source: Table 2 · p. 7, §4.2 · p. 7

4.3. Effect of Universal Orthogonal Parameterization

  • Combining multiple elliptic and hyperbolic components lets GoldE model cycles and hierarchies together, achieving the best performance on all three datasets.Elliptic parameterization performs better on cycle-dominated FB15k-237, while hyperbolic parameterization performs better on hierarchy-dominated WN18RR and YAGO3-10; multiple homogeneous components also outperform single components.Source: Table 3 · p. 7, §4.3 · pp. 7–8
  • Higher-dimensional orthogonal transformations improve GoldE’s MRR over lower-dimensional counterparts in Euclidean, elliptic, and hyperbolic parameterizations.The reported comparisons cover WN18RR and FB15k-237.Source: Figure 3 · p. 7, §4.3 · p. 8

4.4. Fine-grained Performance Analysis

  • GoldE achieves the best performance against RotH and HousE on all 11 WN18RR relation types, including hierarchical and symmetric relations.The cited analysis highlights hypernym and instance hypernym as hierarchical examples, and derivationally related form and verb group as symmetric examples.Source: Table 4 · p. 8, §4.4 · p. 8

4.5. Results with Restricted Embedding Size

  • With embedding size fixed at 32, GoldE surpasses baselines across all three datasets.The paper presents this restricted-size setting as challenging for KGE models.Source: Table 5 · p. 8, §4.5 · p. 8

5. Related Work

  • GoldE’s orthogonal parameterization can be integrated with regularizers and graph encoders to improve performance.The paper presents the framework as generalizing existing KGE approaches in both dimension and geometry.Source: §5 · p. 8

6. Conclusion

  • The paper proposes future work on applying GoldE to hyper-relational and temporal knowledge graphs.It characterizes GoldE as capable of capturing logical patterns and heterogeneous KG structures.Source: §6 · p. 8

Impact Statement

  • GoldE may encode training-graph biases, leading to stereotyped predictions for missing links between some nodes.The paper gives users on social or e-commerce platforms as an example and calls for future mitigation.Source: Impact Statement · p. 9

B. Proof of Theorem 3.1

The proof establishes that every generalized orthogonal matrix can be represented by at most k reflections, then shows Orth spans the generalized orthogonal group when n=k.

B.1. Proof of Theorem B.1 (Cartan-Dieudonn´e Theorem)

  • Every element of O_w(k) is a product of at most k reflections, proved by handling fixed vectors, anisotropic differences, and the remaining rotation case.The remaining case establishes that k is even and the transformation is a rotation before completing the reflection bound.Source: §B.1 · pp. 13–14
  • When every anisotropic x has Gx−x isotropic and nonzero, the proof derives that k is even and G is a rotation.It uses W=(G−1)V and shows W=W⊥, so k=2dim(W).Source: §B.1 · pp. 13–14

B.2. Proof of Theorem 3.1

  • When n=k, Orth's image equals O_w(k), since its reflection products are orthogonal and every member can be expressed using at most k reflections.The mapping's output satisfies quadratic inner-product invariance.Source: §B.2 · p. 14

C. Proof of Claim 3.2

The elliptic distance can be reformulated as a Euclidean orthogonal transformation with relation-specific scaling of both embeddings.

C. Proof of Claim 3.2

  • The elliptic distance is equivalent to scaling the head embedding by √pr, applying a Euclidean orthogonal transformation, and comparing it with the tail embedding scaled by √pr.The reformulation identifies elliptic parameterization with Euclidean parameterization equipped with element-wise scaling.Source: C. Proof of Claim 3.2 · p. 15

D. Proof of Proposition 3.3

The proof characterizes hyperbolic orthogonal matrices through their block structure, inner-product invariance, and the sign behavior of their first coordinate.

D. Proof of Proposition 3.3

  • A hyperbolic orthogonal matrix preserves the quadratic inner product, and its first entry has absolute value at least 1.The matrix is written in block form with first entry a and remaining blocks b, c, and A.Source: D. Proof of Proposition 3.3 · p. 15
  • When G11≥1 the transformation preserves the sign of x1, whereas G11≤−1 reverses it.The proof derives this sign behavior from the hyperboloid constraint.Source: D. Proof of Proposition 3.3 · pp. 15–16
  • The subset O+_q(k) of hyperbolic orthogonal matrices with G11≥1 is a multiplicative subgroup.The proof cites closure under multiplication and inclusion of the identity.Source: D. Proof of Proposition 3.3 · p. 16

E. Proof of Proposition 3.4

The proof decomposes the block A of a positive hyperbolic orthogonal matrix into a Euclidean orthogonal factor and a positive symmetric factor, then parameterizes the orthogonal factor by reflections.

E. Proof of Proposition 3.4

  • The polar decomposition A=QS gives a Euclidean orthogonal Q and a positive symmetric S, with S derived from A⊤A=I+bb⊤.The eigenvalues of I+bb⊤ are 1 with multiplicity k−2 and a² with multiplicity 1.Source: E. Proof of Proposition 3.4 · p. 16
  • For a≥1, S has eigenvalue a along b and eigenvalue 1 on directions orthogonal to b.This follows from the eigenstructure of bb⊤ and the positive square root defining S.Source: E. Proof of Proposition 3.4 · p. 16
  • The Euclidean orthogonal factor Q is parameterized as a composition of k−1 Euclidean Householder reflections.Source: E. Proof of Proposition 3.4 · p. 17

F. Proof of Claim 3.5

GoldE’s product manifold uses elliptic and hyperbolic transformations to represent cyclical and hierarchical structures, while orthogonality and geometric unification support logical patterns. Efficient vector-vector computations reduce transformation costs, and training time remains comparable to RotatE and HousE.

F. Proof of Claim 3.5

  • Orthogonality and geometric unification let GoldE capture logical patterns and topological structures together.The proof section frames this as a consequence of the relation matrix’s orthogonality and the embedding space’s geometric unification.Source: F. Proof of Claim 3.5 · p. 17
  • Elliptic transformations suit cyclical structures, while hyperbolic boosts encode hierarchical moves across levels and Euclidean orthogonal matrices model moves within a level.GoldE’s product manifold combines multiple model spaces to match heterogeneous KG structures.Source: F. Proof of Claim 3.5 · p. 17

G. Efficient Computation

  • Vector-vector operations reduce the elliptic and hyperbolic transformation costs from O(k3) to O(k2).The elliptic reflections are computed iteratively; the hyperbolic transformation uses an equivalent boost form and block multiplication before its Euclidean orthogonal step.Source: G. Efficient Computation · p. 18
  • GoldE achieves comparable training time to RotatE and HousE while delivering superior link-prediction effectiveness without sacrificing efficiency.The comparison uses three standard benchmarks.Source: G. Efficient Computation · p. 18, Table 7 · p. 18

H. Datasets

The experiments use WN18RR, FB15k-237, and YAGO3-10, with the first two formed by removing inverse relations from their source datasets.

H. Datasets

  • Table 8 reports detailed statistics for benchmark datasets, but the cited descriptions conflict on the count: one says three datasets, while its caption says five standard benchmarks.Source: H. Datasets · p. 18, Table 8 · p. 18
  • WN18RR and FB15k-237 are subsets of WN18 and FB15k, respectively, with inverse relations removed to avoid test leakage.WN18 comes from WordNet, while FB15k comes from Freebase.Source: H. Datasets · p. 18
  • YAGO3-10 contains 123,182 entities and 37 relations, mostly describing people’s attributes.Examples include citizenship, gender, profession, and marital status.Source: H. Datasets · p. 18

I. Implementation Details

Implementation uses filtered ranking metrics, parameter-matched baselines, and a simplified product-manifold configuration with tuned hyperparameters.

I. Implementation Details

  • Filtered ranking evaluates each test triple against absent head- or tail-corrupted triples using MR, MRR, and H@N.The protocol excludes negative triples that appear in the knowledge graph.Source: §I · p. 19
  • GoldE’s entity embedding size is fixed at 800 on WN18RR, 600 on FB15k-237, and 1000 on YAGO3-10 to keep parameter counts similar to baselines.Baseline parameter counts are reported in Table 9.Source: §I · p. 19, Table 9 · p. 19
  • With embedding size fixed for fair comparison, the product manifold is configured through k*=mP kP, mP, and mQ.Component spaces of the same geometric type are assigned identical dimensions; the selected manifold may not be optimal because of this simplified configuration.Source: §I · p. 19
  • Adam is used, and validation-set hyperparameters are selected by random search over batch size, sampling temperature, margin, learning rate, and manifold dimensions.The search includes b, α, γ, lr, k*, mP, and mQ.Source: §I · p. 19, Table 10 · p. 19

J. More Results of GoldE with Varying Embedding Size

GoldE outperforms baselines across metrics and datasets in the k=32 results, and its WN18RR MRR advantage persists across a broad range of embedding sizes.

J. More Results of GoldE with Varying Embedding Size

K. Limitations and Future Work

GoldE retains the traditional KGE paradigm, modeling training triples independently; the authors identify resulting multi-hop reliability and graph-only inference as limitations and outline future directions.

K. Limitations and Future Work

  • Single-triple training can accumulate optimization biases across relation hops, making perceived logical patterns unreliable and hindering generalization.The authors suggest combining GoldE with a path or graph encoder to process structurally dependent triples together.Source: K. Limitations and Future Work · p. 20
  • GoldE uses graph structure alone for symbolic inference; incorporating textual attributes of entities and relations is proposed as future work.Source: K. Limitations and Future Work · p. 20
  • The authors also plan to investigate other theories and methodologies for knowledge mining.Source: K. Limitations and Future Work · p. 20
Loading 2405.08540v1…