PaperlayerView exact revision on arXiv

Source-linked AI summary

Pattern Over-Generalization of Knowledge Graph Embedding

Junsik Kim, Kangil Kim

arXiv:2609.03487v1cs.CLcs.AI

TL;DR

KGE models can over-generalize patterns from a single observed instance to all related graph instances, causing erroneous predictions. PogRE uses linear transformations and compound operations to address this issue, and it outperforms baselines on three benchmark datasets while reducing over-generalization. Its guarantees and benefits remain limited when pattern frequency diverges from semantic universality, and it currently supports only transductive settings.

  • Problem

    Existing KGE models may generalize a pattern observed in only one instance universally across the graph, producing erroneous predictions.

  • Method

    PogRE uses linear transformations and compound operations for relation representation to address pattern over-generalization.

  • Results

    PogRE consistently outperforms baseline KGE models in link prediction on three benchmark datasets and effectively addresses over-generalization.

  • Takeaways & Limitations

    PogRE allows patterns to become progressively universal as more linearly independent entities are observed, rather than making them universally valid from a single instance.

  • Takeaways & Limitations

    PogRE does not use pattern semantics and is limited to transductive settings, so it may misalign generalization with semantic universality and cannot directly represent unseen entities or relations.

Abstract

from arXiv · show

Knowledge graph embedding (KGE) demonstrates its effectiveness for predicting missing links in knowledge graphs (KGs) by projecting entities and relations into a low-dimensional vector space. It is crucial for KGE models to effectively capture inference patterns (patterns) inherent in KGs, such as symmetry/antisymmetry, inversion and composition. Although recent KGE models exhibit strong capabilities in modeling such diverse patterns, they suffer from inherent limitations stemming from pattern over-generalization, where embeddings learned from only a single pattern instance inevitably generalize that pattern to all related instances, i.e., generalize the pattern universally. To address this issue, we propose PogRE (Pattern Over-Generalization Robust Embedding), a simple but effective method that utilizes dense linear transformations and compound operations for relation representation. Our theoretical analysis demonstrates that a dense linear transformation allows a pattern to become progressively universal as more triples are observed in the pattern. Furthermore, after observing d+1 linearly independent entities (d+1 denotes the dimension of entity), the linear transformation guarantees universal generalization of the pattern across all related instances. Experimental results on three standard benchmark datasets show that PogRE outperforms existing state-of-the-art KGE models in link prediction. Moreover, our empirical results indicate that PogRE effectively addresses the negative impact of over-generalization.

1 Introduction

KGE predicts missing links by representing entities and relations in low-dimensional vectors, but existing models can over-generalize locally valid inference patterns across an entire graph. PogRE addresses this issue with dense linear transformations and compound operations, with benchmark results showing improved link prediction.

  • Knowledge graphs store knowledge as triples, and KGE represents entities and relations in low-dimensional vectors to predict missing links.
  • KGE models must capture inference patterns including symmetry/antisymmetry, inversion, and composition.
  • Existing models over-generalize patterns observed from few triples, treating locally valid patterns as universally valid and producing erroneous predictions.
  • PogRE uses dense linear transformations and compound operations to prevent locally valid patterns from being generalized universally.
  • PogRE theoretically supports progressive generalization as more triples are observed, with sufficient observations enabling universal generalization across related instances.
  • PogRE consistently outperforms baseline KGE models in link prediction on three benchmark datasets and addresses over-generalization's negative impact.

2 Background

KGE formalizes knowledge graphs as factual triples and scores their plausibility in a low-dimensional space. Background models differ in how they train and score triples, while inference patterns describe rules connecting observed bodies to implied heads.

  • A knowledge graph is a collection of triples (h, r, t), where h and t are entities and r is a relation.
  • KGE maps entities and relations to a low-dimensional vector space and uses a score function to measure triple plausibility.
  • Distance-based models minimize distances for factual triples while maximizing distances for negatives created by replacing heads or tails.
  • Tensor decomposition models maximize multilinear scores for factual triples and minimize scores for negative triples.
  • An inference pattern specifies that when a body of triples appears in a graph, its corresponding head should also appear; composition is one example.

3 Problem

Pattern over-generalization occurs when KGE models treat locally supported patterns as universally valid, producing erroneous predictions. The problem is tied to entity-independent relation conditions and can affect many body instances despite scarce pattern evidence.

  • Pattern Over-Generalization: Pattern over-generalization treats a pattern observed in one instance as valid for every corresponding body instance in the graph.A local pattern is therefore generalized universally, even without sufficient evidence.
  • Pattern Over-Generalization: Local patterns are formally distinguished from universal patterns by whether their supported pattern-instance set is a proper subset of, or equal to, the universal set.The definitions use Gp ⊂ Gu for local patterns and Gp = Gu for universal patterns.
  • Why Does The Problem Appear?: Universal generalization without sufficient evidence can inject incorrect information into embeddings and lead to erroneous predictions.The issue is especially consequential when a pattern is locally valid but not universally valid.
  • Why Does The Problem Appear?: Because the pattern condition depends only on relation embeddings, it is independent of entity identities and can generalize local patterns to unseen triples.The cited PairRE example shows a learned relation condition being reused for a new body instance.
  • Empirical Evidence: Figure 2 evidence shows PairRE concentrating embedding differences near zero for both local and universal patterns, regardless of instance frequency.Near-zero elements indicate that the model recognizes the relation set as a valid pattern and generalizes it universally.
  • Empirical Evidence: Local patterns may have scarce pattern instances but many body instances, causing a few observations to affect numerous predicted heads.Figure 3 compares these pattern-instance and body-instance counts; the OG ratio assesses whether models score true and false resulting triples similarly.
  • PogRE: PogRE explicitly models pattern locality and universality, generalizing patterns differentially according to their observation frequency.Its framework is proposed to address the tendency of existing KGE models to generalize all observed patterns equally.

4 Method

PogRE combines dense linear transformations with compound and affine operations to control how inference patterns generalize. Its theory makes generalization progressive with observed independent entities and universal after sufficient coverage.

  • Core architecture: PogRE uses dense relation transformations, decomposing each L_r into a relation-specific orthogonal matrix and a shared upper-triangular matrix.QR-inspired parameterization reduces the cost of dense transformations.
  • Core architecture: Spectral normalization bounds transformation Lipschitz constants to one, supporting generalization to semantically similar unobserved entities.The method retains controlled extension beyond entities observed in local patterns.
  • Core architecture: Relation-specific affine operators map entities before L_r, restoring expressive power lost by sharing the upper-triangular matrix.Scaling, rotation, and translation operators are unified through homogeneous coordinates.
  • Optimization: PogRE trains with self-adversarial negative sampling and a sigmoid-margin loss over weighted negative triples.The negative-triple weights use a sampling temperature.
  • Theoretical analysis: A pattern becomes progressively universal as PogRE observes linearly independent entities, reaching universal generalization after d entities in the linear case.With affine operators represented in augmented space, the corresponding threshold is d+1 independent entities.

5 Related Work

Related KGE models capture patterns through relational operations or tensor interactions. These approaches model diverse patterns but do not directly control generalization scope according to supporting evidence.

  • Distance-based models: Distance-based models represent relations with operations including translation, rotation, reflection, quaternion transformation, and compound mappings.Examples include TransE, RotatE, Rotate3D, DualE, ReflectE, RotatQ, HAKE, PairRE, and CompoundE.
  • Tensor decomposition models: Tensor decomposition models capture patterns through interactions among entity and relation embeddings using bilinear, circular-correlation, linear, CP, and Tucker operators.Representative models include DistMult, ComplEx, HolE, ANALOGY, SimplE, TuckER, and QuatE.
  • Generalization scope: Existing models can capture observed patterns but do not directly control the scope of pattern generalization based on supporting evidence.This motivates methods that distinguish locally supported patterns from universally supported ones.

6 Experiments

Experiments evaluate PogRE on three benchmark KGs under filtered link prediction and analyze performance, computational trade-offs, entity independence, pattern sparsity, and over-generalization.

  • Evaluation: The evaluation uses filtered link prediction with MRR, Hits@1, and Hits@10, removing known triples from corrupted candidate sets.Candidates corrupt either the subject or object while retaining the test triple of interest.
  • Main results: PogRE achieves MRR improvements of 0.009, 0.004, and 0.011 over second-best models on WN18RR, FB15k-237, and YAGO3-10, respectively.The cited comparisons are against DualE on WN18RR and HAKE on the other two datasets.
  • Ablation study: PogRE consistently outperforms ablated models, while omitting its dense transformation causes over-generalization and performance degradation.The w/o L_r variant is equivalent to CompoundE.
  • Pattern sparsity: 88.6%, 65.3%, and 52.8% of composition patterns have 10 or fewer instances in WN18RR, FB15k-237, and YAGO3-10, respectively.These sparse patterns are vulnerable to universal generalization when models over-generalize.
  • Over-generalization impact: PogRE consistently outperforms TransE, RotatE, PairRE, and CompoundE on G_over across pattern-instance counts in FB15k-237.G_over contains triples whose candidate alternatives are heads of training-supported pattern instances.

7 Conclusion

The paper introduces PogRE to address pattern over-generalization in KGE. Theory and experiments support progressive pattern generalization and effective link prediction across three benchmarks.

  • Conclusion: PogRE uses linear transformations and compound operations to address patterns generalized universally after only a single observed instance.The method targets erroneous universal treatment of locally supported patterns.
  • Conclusion: PogRE makes pattern generalization progressive as more linearly independent entities are observed and performs effectively on three benchmark datasets.The conclusion connects the theoretical property with the reported benchmark evidence.

Limitations

PogRE’s main limitations concern pattern semantics, transductive scope, and computational trade-offs. Its performance and efficiency also depend on the Householder-reflection setting and dataset.

  • Pattern-semantic limitation: PogRE does not use pattern semantics, so frequency–semantics mismatches can cause inappropriate generalization.Universal low-frequency patterns may not generalize universally, while local high-frequency patterns may generalize universally.
  • Setting limitation: PogRE is limited to the transductive setting and cannot directly represent entities or relations unseen during training.Extending it to inductive settings requires different assumptions and architectural designs.
  • Space complexity: PogRE uses O(nrkd + d2) parameters for dense transformations, whereas PogRE w/o QR uses O(nrd2) relation parameters.The w/o QR variant also requires a b×d×d relation tensor during batch scoring.
  • Time complexity: PogRE has higher theoretical scoring complexity than RotatE and PairRE, although training time with k = 2 remains comparable to the baselines.PogRE w/o QR is infeasible under the same experimental setting because of its substantially higher space complexity.
  • Hyperparameter trade-off: Increasing k raises computational cost; performance improves with k on WN18RR and FB15k-237 but peaks at k = 2 on YAGO3-10.On WN18RR and FB15k-237, performance shows no significant improvement after k = 20.

D Impact of Over-generalization

This section evaluates how over-generalization affects link prediction and introduces measures for detecting it. PogRE consistently performs better across the examined settings and is designed to reduce this failure mode.

  • Performance impact: PogRE outperforms baseline models across local-pattern criteria and datasets, demonstrating robustness against over-generalization.The comparison covers WN18RR and YAGO3-10 and uses varying pattern-instance sparsity conditions.
  • Pattern frequency: A substantial proportion of symmetry, antisymmetry, and inversion patterns have 10 or fewer pattern instances across the three benchmark datasets.For inversion, the corresponding proportions are 50.0%, 49.3%, and 58.8% in WN18RR, FB15k-237, and YAGO3-10.
  • Evaluation setting: PogRE is evaluated on WN18RR, FB15k-237, and YAGO3-10, with additional experiments on larger biomedical and Wikidata graphs.The benchmark datasets remove inverse relations or impose dataset-specific entity criteria as described in the supplied passages.
  • Large-scale evaluation: PogRE achieves the highest performance in valid and test MRR on the large-scale ogbl-biokg and ogbl-wikikg2 datasets.These datasets contain 4.7 million and 16.1 million triples, respectively.
  • OG ratio: The OG ratio compares average scores for true and false triples: values near 1 indicate over-generalization, while values near 0 indicate effective avoidance.True and false triples are separated after excluding head instances present in training data.

I Empirical Analysis of Local and Universal Patterns

The analysis separates semantically local and universal patterns by their observed frequency and examines when PogRE succeeds or fails. PogRE generally helps on low-frequency local patterns but is vulnerable when frequency conflicts with semantic scope.

  • Frequency and semantics: Low-frequency patterns with n ≤10 generally tend to be semantically local, which can cause erroneous predictions under existing models’ over-generalization.The authors note that this tendency does not always hold because real-world KG semantics are complex.
  • Universal low-frequency cases: PogRE may fail on universal but low-frequency patterns because it does not use semantic information to infer universal validity.This failure can arise when dataset sparsity leaves a universal pattern supported by only a few instances.
  • Local high-frequency cases: PogRE may generalize local but high-frequency patterns universally, producing inappropriate generalization.This case occurs when many observed instances do not match the pattern’s local semantics.
  • Failure-case evaluation: PogRE underperforms CompoundE on the universal-but-low-frequency case set in FB15k-237 and YAGO3-10.The comparison measures MRR on test triples containing relations from the identified failure cases.
  • Failure-case evaluation: PogRE also does not outperform CompoundE on the local-but-high-frequency set evaluated on YAGO3-10.This result establishes an additional boundary for PogRE’s applicability.
  • Applicability boundary: PogRE is most suitable when low-frequency patterns are likely local and high-frequency patterns are likely universal.Most local patterns are reported to have low frequency, so the method can generally improve overall dataset performance.

J Additional Empirical Evidence for Over-Generalization

Additional experiments show that over-generalization extends beyond composition to symmetry patterns. Pattern-instance counts and embedding-difference distributions indicate that models can treat both local and universal patterns as valid.

  • Composition-pattern evidence: Universal patterns also have higher PI/BI ratios of 0.432 and 0.761 than local patterns’ 0.176 and 0.012.These ratios support the universal characteristics of the patterns in Figure 2(b).
  • Symmetry mechanism: PairRE’s symmetry condition depends only on relation embeddings, allowing a pattern learned from few instances to generalize to other entities.This relation-level condition creates a mechanism for local symmetry over-generalization.
  • Symmetry evidence: Embedding-difference values concentrate near zero for both local and universal symmetry patterns, regardless of instance frequency.The result indicates that the model recognizes both types as valid symmetry patterns.
  • Overall implication: The symmetry analysis empirically shows that pattern over-generalization is not limited to composition patterns.Figures 8 and 9 compare embedding-difference distributions with pattern and body-instance counts.

K Bounding Constraint Errors Under Practical Training Dynamics

Theoretical analysis extends PogRE’s pattern-constraint guarantees to practical approximate training, while positioning its dense transformations against alternative models and evaluating broader benchmarks.

  • Practical Training Dynamics: Approximate satisfaction of observed pattern constraints bounds constraint error for unseen entities, so exact zero error is unnecessary in practice.The guarantee applies when observed constraint errors remain within a small margin ϵ.
  • Assumptions: The analysis assumes approximate constraint satisfaction and d + 1 linearly independent observed entities, with the latter serving as a sufficient condition for universal generalization.Universal generalization is guaranteed when the observed entities span the relevant space.
  • Assumptions: Less restrictive independence requirements may ease pattern generalization but increase the risk that weakly supported patterns generalize too broadly.This trade-off is the over-generalization problem PogRE is designed to avoid.
  • Model Comparisons: Dense transformation baselines such as RESCAL and TransR assign a dense R^n×n matrix to each relation, increasing computational costs as entity and relation dimensions grow.These models are described as not being designed for pattern modeling.
  • Model Comparisons: PogRE outperforms transductive GNN baselines in MRR across the available benchmarks, including WN18RR and FB15k-237.The comparison evaluates PogRE against graph-contextual baselines that improve entity representations through message passing.
Loading 2609.03487v1…