Paper deep dive
Pattern Over-Generalization of Knowledge Graph Embedding
Junsik Kim, Kangil Kim
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 9/4/2026, 3:19:18 AM
Summary
The paper introduces PogRE (Pattern Over-Generalization Robust Embedding), a Knowledge Graph Embedding (KGE) method designed to address the issue of pattern over-generalization. Existing KGE models tend to generalize patterns observed in a few instances universally across the entire graph, leading to erroneous predictions for local patterns. PogRE utilizes dense linear transformations and compound operations to ensure that patterns become progressively universal only as more linearly independent entities are observed, thereby distinguishing between local and universal patterns. Experimental results on benchmark datasets show that PogRE outperforms state-of-the-art KGE models in link prediction and effectively mitigates over-generalization.
Entities (10)
Relation Signals (10)
PogRE → addressesproblem → Pattern Over-Generalization
confidence 98% · To address this issue, we propose PogRE... effectively addresses the negative impact of over-generalization.
PogRE → usestechnique → Linear Transformation
confidence 95% · PogRE uses dense linear transformations and compound operations for relation representation
TransE → suffersfrom → Pattern Over-Generalization
confidence 90% · While well-known KGE models such as TransE... suffer from inherent limitations stemming from pattern over-generalization.
RotatE → suffersfrom → Pattern Over-Generalization
confidence 90% · While well-known KGE models such as... RotatE... suffer from inherent limitations stemming from pattern over-generalization.
PairRE → suffersfrom → Pattern Over-Generalization
confidence 90% · While well-known KGE models such as... PairRE... suffer from inherent limitations stemming from pattern over-generalization.
CompoundE → suffersfrom → Pattern Over-Generalization
confidence 90% · While well-known KGE models such as... CompoundE... suffer from inherent limitations stemming from pattern over-generalization.
PogRE → outperforms → TransE
confidence 85% · Experimental results on three standard benchmark datasets show that PogRE outperforms existing state-of-the-art KGE models in link prediction.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2609.03487v1
- Canonical: https://arxiv.org/abs/2609.03487v1
Trouble viewing inline? Open PDF directly →
Full Text
88,686 characters extracted from source content.
Expand or collapse full text
Pattern Over-Generalization of Knowledge Graph Embedding Junsik Kim and Kangil Kim * AI Graduate School Gwangju Institute of Science and Technology junsikkim@gm.gist.ac.kr, kangil.kim.01@gmail.com Abstract Knowledge graph embedding (KGE) demon- strates 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 mod- els to effectively capture inference patterns (patterns) inherent in KGs, such as symme- try/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 em- beddings 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 com- pound 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 observingd + 1linearly independent entities (d + 1denotes the dimension of entity), the linear transformation guarantees universal gen- eralization of the pattern across all related in- stances. Experimental results on three standard benchmark datasets show that PogRE outper- forms 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 Knowledge graphs (KGs) store vast amounts of human knowledge in the form of triples(h,r,t), wherehandtrepresent the head and tail entities andrdenotes the relationship between entities. KGs have demonstrated their effectiveness in vari- ous downstream tasks (Sui et al., 2025; Ma et al., * Corresponding author. 2025). However, real-world KGs such as Free- base (Bollacker et al., 2008) and WordNet (Miller, 1995), even on a large scale, still suffer from in- completeness (Bordes et al., 2013). To address this issue, Knowledge graph embedding (KGE), which represents entities and relations in a low- dimensional vector space, has been widely studied as an effective method for predicting missing links. A fundamental challenge in KGE lies in effec- tively capturing the inference patterns (patterns) inherent in KGs, such as symmetry/antisymmetry, inversion, and composition. To address this, ex- isting works focus on designing specific score functions to capture these patterns. For instance, TransE (Bordes et al., 2013) represents relations as translations to model inversion and composition, while RotatE (Sun et al., 2019) employs rotations to capture symmetry/antisymmetry, inversion and composition. PairRE (Chao et al., 2021) and Com- poundE (Ge et al., 2023) leverage scaling and com- pound operators to effectively model more patterns, including subrelation as well as complex relations. Despite their strong ability to capture various pat- terns, existing KGE models tend to over-generalize the patterns they observe. In particular, once a model observes a pattern, it generalizes the pattern universally across the entire graph, even when the pattern is supported by only a small number of ob- served triples. Consequently, patterns that are valid locally in the graph are treated as universally valid. We refer to this phenomenon as over-generalization, which leads to erroneous predictions. To address this issue, we propose a simple but effective method, PogRE, that prevents locally valid patterns from being generalized universally. PogRE uses dense linear transformations and com- pound operations for relation representation, where the linear transformation is decomposed into a relation-specific orthogonal matrix and a shared upper-triangular matrix. This framework theoreti- cally guarantees that patterns supported by only a arXiv:2609.03487v1 [cs.CL] 3 Sep 2026 small number of observed triples are generalized locally, while ensuring that any pattern supported by sufficient observed triples is generalized uni- versally across the entire graph, when patterns are represented as connected relational paths. Our contributions are as follows: • We introduce pattern over-generalization, the phenomenon in which patterns supported by only a small number of observed triples are generalized universally across the entire graph in existing KGE models. •We propose a novel KGE method, Pat- tern Over-Generalization Robust Embedding (PogRE), and theoretically guarantee that it effectively addresses over-generalization. In particular, PogRE allows any pattern repre- sented as a connected relational path to be- come progressively universal as more triples are observed in the pattern. Moreover, suffi- cient triples are observed, PogRE guarantees universal generalization of the pattern across all related instances. • Experimental results on three benchmark datasets demonstrate that PogRE consistently outperforms baseline KGE models in link pre- diction and effectively addresses the negative impact of over-generalization. 2 Background Knowledge Graph EmbeddingGiven sets of en- tities and relationsEandR, a KG can be defined as a collection of factual triplesG =(h,r,t)|h,t∈ E,r ∈ R, wherehandtare the head and tail entities, andris the relation. KGE mapsEand Rto low-dimensional vector space and defines a score function to measure triple plausibility. Distance-based models (DBMs) are trained to minimize the distance of the factual triple(h,r,t), while maximizing the distance of corrupted nega- tive triples(h ′ ,r,t)or(h,r,t ′ ), which are gener- ated by randomly replacing the headhor tailtwith other entities inE. PairRE (Chao et al., 2021), a representative model of DBMs, defines the score function as follows: f r (h,t) =∥h◦ r H − t◦ r T ∥, (1) whereh,t,r H ,r T ∈R d ,◦denotes a Hadamard product and∥·∥ is a vector norm. Tensor decomposition models (TDMs) are trained to maximize the score (or semantic sim- ilarity) of the factual triple calculated via the multi- linear product of the head entityh, the relationr and the tail entityt, while minimizing the score of negative triples. DistMult (Yang et al., 2015), a representative model of TDMs, defines the score function as follows: f r (h,t) =⟨h,r,t⟩ = P d i=1 h i r i t i , (2) whereh,r,t∈R d , and⟨·,·,·⟩denotes the sum of element-wise products. Inference Pattern Inference patterns (patterns) are widely used to analyze the generalization ca- pabilities of KGEs. A pattern, notated asψ ⇒ φ, has the bodyψand the headφ, which are sets of triples composed of observed entities and re- lations in the data. For example, a composition pattern for relationsr 1 ,r 2 ,r 3 ∈ Ris defined as r 1 (X,Y )∧ r 2 (Y,Z) ⇒ r 3 (X,Z). A pattern im- plies that if the body is in the graph, the head is also in the graph (Pavlovi ́ c and Sallinger, 2023). 3 Problem 3.1 Problem Formulation Pattern Instance We further define a pattern in- stance as an instantiation of patternψ ⇒ φ. For the composition pattern of relationsr 1 ,r 2 ,r 3 ∈ R , a pattern instanceψ 1 ⇒ φ 1 is expressed asr 1 (e x ,e y ) ∧ r 2 (e y ,e z ) ⇒ r 3 (e x ,e z ), where r 1 (e x ,e y )∧ r 2 (e y ,e z )corresponds to a body in- stanceψ 1 ,r 3 (e x ,e z )corresponds to the head in- stance φ 1 , and e x ,e y ,e z ∈ E. Pattern Over-Generalization Although well- known KGE models such as TransE (Bordes et al., 2013), RotatE (Sun et al., 2019), PairRE (Chao et al., 2021), and CompoundE (Ge et al., 2023) demonstrate strong generalization capabilities by modeling various patterns, they suffer from in- herent limitations stemming from pattern over- generalization. Pattern over-generalization is the phenomenon where a model, after observing a single instance of a pattern (ψ 1 ⇒ φ 1 ) in the graphG, generalizes the pattern to every body in- stance that appears in the graph; for example, if the bodyψ 2 appears in graphG, the model in- fers that the corresponding headφ 2 must also exist (i.e.,ψ 2 ⇒ φ 2 ). This issue arises because existing models are trained to generalize a pattern univer- sally. We formally define the phenomenon of pat- tern over-generalization as well as local pattern, and universal pattern as follows: Pattern Over-Generalization The model generalizes a local pattern to all unseen triples without sufficient evidence, i.e., the model treats a local pattern as a universal pattern. • Local Pattern:ψ i ∈ G o ⇒ φ i ∈ G p (s.t. G p ⊂ G u and G p ̸= G u ) • Universal Pattern:ψ i ∈ G o ⇒ φ i ∈ G p (s.t. G p = G u ) for a given set of instantiated relationsr i n i=1 . where G o :f|f is a set of triples observed in the given KG G p :f|f is ψ i ∈ G o or φ i that corresponds to ψ i , s.t. φ i is semantically correct. G u :f|f is ψ i ∈ G o or φ i that corresponds to ψ i ) (3) While this phenomenon can serve as a crucial inductive bias in KGE, universally generalizing a local pattern without sufficient evidence can lead to erroneous predictions by injecting incorrect in- formation into the embeddings. 3.2 Cause and Evidence Why Does The Problem Appear? The cause is that the pattern condition depends only on re- lation embeddings in KGE methods. This entity- independent pattern condition allows the model to generalize local patterns to unseen triples. For example, in PairRE that is fully trained to satisfy Equation 1 for all triples inG, if body in- stance(e x 1 ,r 1 ,e y 1 ), (e y 1 ,r 2 ,e z 1 ) ∈ Gand head instance (e x 1 ,r 3 ,e z 1 )∈ G, we have e x 1 ◦ r H 1 = e y 1 ◦ r T 1 ∧ e y 1 ◦ r H 2 = e z 1 ◦ r T 2 ∧ e x 1 ◦ r H 3 = e z 1 ◦ r T 3 ⇒ r T 1 ◦ r T 2 ◦ r H 3 = r H 1 ◦ r H 2 ◦ r T 3 (4) Under this pattern condition, if a new body in- stance (e x 2 ,r 1 ,e y 2 ), (e y 2 ,r 2 ,e z 2 ) is observed as e x 2 ◦ r H 1 = e y 2 ◦ r T 1 ∧ e y 2 ◦ r H 2 = e z 2 ◦ r T 2 (5) then the model guarantees that e x 2 ◦ r H 3 = e z 2 ◦ r T 3 , (6) Local Pattern : Body (휓) : Head (휙) 휓 1 휙 1 Generalize Pattern Universally Observing Single Instance (Jon Favreau, 푟 1 , Iron Man 2) (Iron Man 2, 푟 2 , Iron Man) (Jon Favreau, 푟 3 , Iron Man) (Ridley Scott, 푟 1 , Hannibal) (Hannibal, 푟 2 , Hannibal Rising) (Ridley Scott, 푟 3 , Hannibal Rising) (Sam Raimi, 푟 1 , Spider-Man 3) (Spider-Man 3, 푟 2 , Spider-Man 2) (Sam Raimi, 푟 3 , Spider-Man 2) 푟 1 : film/director 푟 2 : film/prequel 푟 3 : film/actor # of Pattern Instance: 22 Composition (푋,푟 1 ,푌) (푋푟 3 ,푍) (푌,푟 2 ,푍) Relations Example of Over-Generalization Pattern Over-Generalization Universal Pattern 퐺 표 휓 1 휓 2 휓 3 휓 4 휓 푖 휓 5 휙 1 휙 2 휙 3 휙 4 휙 푖 휙 5 퐺 표 퐺 푝 퐺 표 휓 1 휓 2 휓 3 휓 4 휓 푖 휓 5 휙 1 휙 2 휙 3 휙 4 휙 푖 휙 5 퐺 푝 =퐺 푢 퐺 표 휓 푖 휙 푖 휓 5 휙 5 휓 1 휙 1 휓 2 휙 2 휓 3 휙 3 휓 4 휙 4 Over-Generalized Local Pattern 퐺 푢 Over-Generalization Semantically Incorrect Head Semantically Incorrect Head Figure 1: Illustration of local and universal patterns, and the process and examples of over-generalization. Exist- ing models suffer from over-generalization by treating local patterns as universal patterns. The example shows that a local pattern is generalized universally, which leads to erroneous predictions. thereby leading the model to treat the correspond- ing head as valid for every new body instance of the same pattern. This phenomenon is further illus- trated in Figure 1, where the model generalizes the pattern universally to every body instance. How- ever, not all patterns in KGs are universally valid, especially those with a few pattern instances. 1 Empirical EvidenceNevertheless, existing KGE models overlook the difference between local and universal patterns, treating all observed patterns as universally valid regardless of their frequency. Figure 2 shows the histograms of the embedding difference∆ = r T 1 ◦ r T 2 ◦ r H 3 − r H 1 ◦ r H 2 ◦ r T 3 , that is presented in Equation 4. Elements of∆close to zero indicate that the model recognizes the given relation set(r 1 ,r 2 ,r 3 )as a valid pattern, therefore, the model generalizes the pattern universally to ev- ery body instance. Figures 2(a) and 2(b) show that the elements of∆are concentrated near zero for both local and universal patterns, indicating that the model recognizes both as valid composi- tion patterns regardless of instance frequency. This empirically demonstrates that PairRE is trained to generalize local patterns as if they were universal, even when the supporting instances are scarce. While local patterns are supported by only a 1 In Appendix I, we present examples of semantically local patterns that have low frequency, along with failure cases where pattern frequency does not match the pattern semantics. 0.20.10.00.10.2 Element Values of 0 650 1300 Frequency # of PI: 22 0.20.10.00.10.2 Element Values of 0 650 1300 Frequency # of PI: 13 (a) Histograms of local patterns that are supported by scarce pattern instances. The relation sets for the left and right figures are (film/written_by, actor/film, film/prequel) and (film/director, film/prequel, actor/film), respectively 0.20.10.00.10.2 Element Values of 0 600 1200 Frequency # of PI: 5033 0.20.10.00.10.2 Element Values of 0 650 1300 Frequency # of PI: 1082 (b) Histograms of universal patterns that are supported by many pattern instances. The relation sets for the left and right fig- ures are (actor/film, film/country, people/nationality) and (peo- ple/place_of_birth, location/country, people/nationality), respec- tively Figure 2: Histograms of embedding difference∆ = r T 1 ◦ r T 2 ◦ r H 3 − r H 1 ◦ r H 2 ◦ r T 3 for different relation set(r 1 ,r 2 ,r 3 ). # of PI denotes the number of pattern instances. (r 1 ,r 2 ,r 3 ) are retrieved from FB15k-237. Pattern InstanceBody Instance 0 20 40 60 # of Instances r 1 : film/written_by r 2 : actor/film r 3 : film/prequel Pattern InstanceBody Instance 0 500 1000 1500 # of Instances r 1 : film/director r 2 : film/prequel r 3 : actor/film Figure 3: The number of pattern instances and body instances for the local patterns introduced in Figure 2(a). scarce number of pattern instances, they often have a vast number of body instances. Figure 3 presents the number of pattern instances and body instances of the local patterns in Figure 2(a). This indicates that a large number of body instances are affected by only a few pattern instances, leading the model to predict the corresponding head instances as valid for all body instances. The distribution of pattern instances and body instances of the universal pat- terns in Figure 2(b) and empirical evidence for another pattern type are presented in Appendix J. To address this issue, we propose a novel KGE framework PogRE that explicitly models the dis- tinction between pattern universality and locality. Our core idea is to generalize patterns differentially based on their observation frequency inG, rather than generalizing all patterns equally. Which Methods Are Affected? Table 1 presents representative examples of KGE meth- ods that suffer from over-generalization.To verify whether these models actually suffer from over-generalization, we propose the Over- ModelScore Function Over-generalization OG ratio (↓) Sym/Asym/Inves/Comp TransE∥h + r− t∥-/✓/✓/✓.927 RotatE∥h◦ r− t∥✓/✓/✓/✓.921 PairRE ∥h◦ r H − t◦ r T ∥✓/✓/✓/✓.917 CompoundE ∥M r · h− ˆ M r · t∥✓/✓/✓/✓.910 PogRE (Ours) ∥L r h r − t r ∥✗/✗/✗/✗.869 Table 1: Comparison between PogRE and KGE models. handtdenote head and tail embeddings andh r and t r indicate head and tail embeddings in the relation- specific space, as presented in Equation 10. Generalization (OG) ratio. Specifically, for the local patterns presented in Figure 3, we extract the head instances corresponding to the body instances and categorize them into True triples (if triples are inG) and False triples (others). The OG ratio is defined as the average score produced by a model for the True triples divided by the average score for the False triples. An OG ratio close to 1 indicates that a model suffers from over-generalization, as it assigns similar scores to both True and False triples. Conversely, an OG ratio closer to 0 implies that the model effectively avoids this issue by assigning higher scores to False triples than to True triples. PogRE exhibits a lower OG ratio than other models. This indicates that PogRE effectively addresses over-generalization. For more details of the OG ratio, please refer to Appendix H. 4 Method In this section, we present the formulation of PogRE and provide a theoretical analysis demon- strating how PogRE addresses over-generalization. 4.1 Pattern Over-Generalization Robust Embedding (PogRE) Final Form We define the score function as the distance between the head entityh r and tail en- tityt r in relation-specific space, after the linear transformation L r ∈R d×d : f r (h,t) =∥L r h r − t r ∥(7) whereh r ,t r ∈R d denote the head and tail embed- dings in relation-specific space, respectively. Comparison Between Existing Linear Transfor- mation Models Although existing models such as RESCAL (Nickel et al., 2011) and TransR (Lin et al., 2015) employ dense linear transformations, they suffer from overfitting and representing re- lations asR n×n dense linear matrix incurs sig- nificant computational costs. As a result, recent KGE models rarely adopt such dense linear trans- formations. CompoundE (Ge et al., 2023) utilizes sparse affine operators; consequently, it suffers from over-generalization, as presented in Table 1. In contrast, PogRE addresses over-generalization by employing dense linear transformations through a QR decomposition-inspired method, which re- duces computational costs. Detailed differences are presented in Appendix L. QR Decomposition and Partial Sharing for Ef- ficient ParameterizationLinear transformation L r of PogRE is decomposed into a relation-specific orthogonal matrixQ r and an upper-triangular ma- trix R that is shared across all relations: L r = Q r R Q r = H 1 H 2 ...H k (8) In addition,Q r is approximated using a product ofkHouseholder reflections (wherek ≪ d). This approximation significantly reduces the number of parameters fromn r d 2 tod(d + 1)/2 + n r kd, wheren r denotes the number of relations, thereby effectively reducing the model complexity. Details about computational complexity with respect tok are presented in Appendix C. Additionally, let ̄ Rbe the learnable upper- triangular parameter matrix. The final shared ma- trix R is formulated as: R = ̄ R ∥ ̄ R∥ 2 (9) where∥·∥ 2 denotes the spectral norm. We argue that even for local patterns, the pattern should be generalized to entities that are not observed in the patterns but are semantically similar to entities that are observed in the patterns. Spectral Normaliza- tion (SN) enables this generalization by bounding the Lipschitz constant of the transformations to one (Miyato et al., 2018). Detailed derivations are provided in the Appendix A. Relation-Specific Affine Mapping for Expres- sive PowerSharing an upper-triangular matrixR reduces the expressive power of relation-specific transformations. To address this limitation and enhance the model capacity, following (Ge et al., 2023), each entity is mapped into an relation- specific space via three affine operators before ap- plyingL r . By employing homogeneous coordi- nates, these operators can be unified into a single matrix multiplication: h r = M r h,t r = ˆ M r · t M r = S r · R r · T r , ˆ M r = ˆ S r · ˆ R r · ˆ T r (10) whereh,tare head and tail embeddings,S r ,R r , andT r denote the scaling, rotation, and translation operators, and ˆ S r , ˆ R r , and ˆ T r denote the scaling, rotation, and translation operators for tail entity embedding, respectively. This mapping strategy ensures that each relation has sufficient expressive power despite the shared components in L r . Optimization Following Sun et al. (2019), we adopt self-adversarial negative sampling for train- ing. The loss function can be written as: L =− logσ(γ− f r (h,t)) − P n i=1 p(h ′ i ,r,t ′ i ) logσ(f r (h ′ i ,t ′ i )− γ) (11) whereσis the sigmoid function,γis a fixed margin, (h ′ i ,r,t ′ i )is thei-th negative triple andp(h ′ i ,r,t ′ i ) is the weight of the negative triple, defined as: p(h ′ j ,r,t ′ j |(h i ,r i ,t i )) = expαf r (h ′ j ,t ′ j ) P i expαf r (h ′ i ,t ′ i ) (12) where α is the temperature of sampling. 4.2 How Is Pattern Over-Generalization Addressed? To analyze how PogRE addresses over generaliza- tion, we first consider using only the linear trans- formationL r , and then extend this analysis to our framework, which incorporates the affine opera- tors. Theoretical Analysis: Linear Transformation To the best of our knowledge, all patterns studied in existing research are based on connected paths formed by relations. This implies that a body (ψ) and head (φ) can be represented as a relational path between the start entitye u and the end entitye v , where each path is formulated as a product of linear matrix multiplications. Consequently, the body (ψ) and head (φ) of a pattern can be expressed as: Body (ψ) : L ψ e u = L r n ...L r 2 L r 1 e u = e v , Head (φ) : L φ e u = L r ′ m ...L r ′ 2 L r ′ 1 e u = e v . (13) whereL ∈R d×d ande ∈R d denote the transfor- mation matrix and entity vector, respectively. From Equation 13, since both paths mape u to the same entitye v , we explicitly haveL ψ e u = L φ e u , which is equivalent to: (L ψ − L φ )e u = 0 ⇐⇒ Ee u = 0(14) whereE = L ψ − L φ denotes the constraint ma- trix. Next, consider a set ofdlinearly independent entitiese u 1 ,e u 2 ,...,e u d that satisfy the pattern, such that 2 : Ee u i = 0,for all i = 1, 2,...,d(15) For any arbitrary entitya∈R d , sincee u i forms a basis inR d ,acan be expressed as a linear com- binationa = c 1 e u 1 + c 2 e u 2 +· + c d e u d . By the linearity of the transformation E, it follows that: Ea = c 1 Ee u 1 +c 2 Ee u 2 +·+c d Ee u d = 0 (16) These results indicate that as PogRE observes more linearly independent entitiese u , the dimen- sion of the space spanned by these entities in- creases. Consequently, when the number of ob- served entities reachesd, PogRE guarantees the universal generalization of the pattern across all re- lated instances. In other words, it can be expected that a pattern becomes progressively universal as the number of observed entities increases. Extension to Relation-Specific Affine Mapping This analysis can be extended to our proposed framework by employing homogeneous coordi- nates. By representing entities in an augmented (d + 1)-dimensional space, the integration of affine operators and linear transformations for a rela- tionrcan be unified into a single linear matrix A r ∈R (d+1)×(d+1) when ˆ M r is non-singular: A r = ˆ M −1 r L r M r (17) Therefore, the relational path can be expressed as a product of linear transformationA r . Consequently, the same proof used in the linear case can be ap- plied, demonstrating that the pattern becomes uni- versal only whend+1linearly independent entities are observed in the augmented space. The linear independence of entity embeddings is discussed in Section 6.3. Our theoretical guarantees rely on the ideal assumption that∥Ee i ∥ = 0. Since satisfying this exact constraint is challenging in practice, we provide further analysis in Appendix K, proving that an approximate constraint (∥Ee i ∥ < ε) still bounds the pattern constraint of unseen entities, along with a discussion on the practical strength of the approximate constraint assumption. 2 Appendix A details constraint matrix for various patterns. 5 Related Work 5.1 Distance-based Models Distance-based models capture patterns through various relational operations. TransE (Bordes et al., 2013), RotatE (Sun et al., 2019), Rotate3D (Gao et al., 2020), DualE (Cao et al., 2021), Re- flectE (Zhang et al., 2022) and, RotatQ (Xie et al., 2025) model relations through translation, rotation, 3D rotation, a combination of translation and ro- tation, reflection transformation, and quaternion- based transformation, respectively. Other mod- els enrich these operations: HAKE (Zhang et al., 2020b) uses polar coordinates for semantic hi- erarchies, PairRE (Chao et al., 2021) and Com- poundE (Ge et al., 2023) apply scaling and com- pound operators, and DensE (Lu et al., 2022) de- composes relations into rotation and scaling in 3D Euclidean space. Recent models further di- versify relation modeling: ExpressivE (Pavlovi ́ c and Sallinger, 2023) and OctagonE (Charpenay and Schockaert, 2024) represent relations as hyper- parallelograms and axis-aligned octagons, respec- tively. SpeedE (Pavlovi ́ c and Sallinger, 2024) im- proves efficiency in low-dimensional Euclidean set- tings, OrthogonalE (Zhu and Shimodaira, 2024) adopts block-diagonal orthogonal matrices with Riemannian optimization, and Charpenay and Schockaert (2025) theoretically analyze the ability of MuRE to capture inference patterns. Although these models effectively capture patterns, their pat- tern conditions are determined by relation embed- dings, which can generalize patterns even when the pattern is supported by only a few instances. 5.2 Tensor Decomposition Models Tensor decomposition models capture patterns through interactions among entity and relation em- beddings. DistMult (Yang et al., 2015) and Com- plEx (Trouillon et al., 2016) use bilinear scoring functions, whereas HolE (Nickel et al., 2016) em- ploys circular correlation. ANALOGY (Liu et al., 2017), SimplE (Kazemi and Poole, 2018), and TuckER (Balaževi ́ c et al., 2019) use normal linear operators, enhanced CP decomposition, and Tucker decomposition, respectively. QuatE (Zhang et al., 2019) extends interactions with quaternion repre- sentations, while CustomizE (Guan et al., 2025) introduces customized embeddings to address the long-tail problem. Although these models provide strong representation capacity, they are not explic- itly designed to distinguish between local patterns Knowledge Graph Embedding WN18RRFB15k-237YAGO3-10 MRRH@1H@10MRRH@1H@10MRRH@1H@10 TransE (Bordes et al., 2013).226-.501.294-.465--- DistMult (Yang et al., 2015).430.390.490.241.155.419--- ComplEx (Trouillon et al., 2016).440.410.510.247.158.428--- RotatE (Sun et al., 2019).476.428.571.338.241.533.495.402.670 TuckER (Balaževi ́ c et al., 2019).470.443.526.358.266.544--- QuatE (Zhang et al., 2019).488.438.582.348.248.550--- Rotate3D (Gao et al., 2020).489.442.579.347.250.543--- HAKE (Zhang et al., 2020b).497 .452.582.346.250.542.545.462.694 DualE (Cao et al., 2021).492.444.584.365.268.559--- PairRE (Chao et al., 2021)---.351.256.544--- HopfE (Bastos et al., 2021).472.413.586.343.247.534.529.438.695 DensE (Lu et al., 2022).492-.586.351-.544.541-.678 ReflectE (Zhang et al., 2022).488.450.559.358.263.546--- ExpressivE (Pavlovi ́ c and Sallinger, 2023).482.407.619.350.256.535--- CompoundE (Ge et al., 2023).491.450.576.357.264.545--- SpeedE (Pavlovi ́ c and Sallinger, 2024).493.446-.320.227-.413.332- OctagonE (Charpenay and Schockaert, 2024).479.436.561.332.241.517--- OrthogonalE (Zhu and Shimodaira, 2024).494.446.573.334.242.518--- CustomizE (Guan et al., 2025).486.446-.351.261.504--- RotatQ (Xie et al., 2025).489.450.552.356.254.619--- MuRE variant (Charpenay and Schockaert, 2025).469.427.553.307.212.503--- PogRE (Ours) .506.461.595.369.273.562.556.474.699 ±.001 ±.001 ±.000 ±.001 ±.001 ±.001 ±.000 ±.001 ±.000 Table 2: Link prediction results on WN18R, FB15k-237 and YAGO3-10. Bold indicates the best result and underline indicates the second best result. ± indicates standard deviation. and universal patterns. As a result, they may cap- ture observed patterns, but they do not directly con- trol the scope of pattern generalization based on supporting evidence. 6 Experiments 6.1 Experimental Setting Dataset We evaluate PogRE on three widely used KG datasets: WN18R (Dettmers et al., 2018), FB15k-237 (Toutanova and Chen, 2015) and YAGO3-10 (Mahdisoltani et al., 2013). The statis- tics of these datasets are presented in Appendix E Evaluation ProtocolWe evaluate link prediction performance in the filtered setting (Bordes et al., 2013). In this setting, test triples are ranked against all other candidate triples that are generated by cor- rupting subjects or objects:(h ′ ,r,t)or(h,r,t ′ ), and all the triples that appear either in the training, validation or test set are removed from the candi- date triples, except the test triple of interest. We adopt MRR, Hits@1 (H@1), and Hits@10 (H@10) to compare the performance of different KGE mod- els. MRR denotes the mean reciprocal rank of the correct entities, and H@N represents the propor- tion of correct entities ranked within the topN. For performance comparison, we evaluate PogRE against all KGE models discussed in Section 5. 6.2 Main Results Link Prediction Performance As shown in Ta- ble 2, PogRE exhibits superior or competitive per- formance compared with the baselines. For in- Model MRR WN18RRFB15k-237YAGO3-10 PogRE.506.369.556 + w/o R.505.365.517 + w/o Q r .501.364.540 + w/o SN.505.360.523 + w/o L r (CompoundE).491.357.477 + w/o QR DecompositionOOMOOMOOM Table 3: Ablation study of PogRE on WN18R, FB15k- 237 and YAGO3-10. MRR is used for performance comparison.R,Q r ,SN,L r , and OOM denote the shared upper triangular parameter matrix, relation spe- cific Householder reflection, Spectral Normalization, linear transformation of PogRE, and Out of Memory, respectively. In w/o QR Decomposition,n× ndense linear transformations are used for L r . stance, PogRE achieves MRR improvements of 0.009, 0.004, and 0.011 over the second-best mod- els, DualE and HAKE, on WN18R, FB15k-237 and YAGO3-10, respectively. These results indi- cate the effectiveness and robustness of PogRE across diverse datasets. In addition to the standard benchmarks presented above, Appendix F provides link prediction results on large-scale KG datasets. Ablation Study Table 3 summarizes the results of an ablation study conducted to verify the effec- tiveness of each proposed component. As shown in the results, PogRE consistently outperforms the ablated models across all datasets. Specifically, w/oL r (equivalent to CompoundE) exhibits sig- nificant performance degradation. w/oL r does not employ a dense matrix and thus suffers from over-generalization, which suggests that overlook- ing this problem results in significant performance Number of Sample Vector Rank WN18RRFB15k-237YAGO3-10 100100.0100.0100.0 200200.0200.0200.0 500500.0500.0500.0 1,000994.4± 1.51000.0999.5± 0.5 1,5001000.01497.4± 0.61000.0 2,0001000.01500.01000.0 Table 4: Mean rank of the subspace spanned by ran- domly sampled entities over 100 random trials across three benchmarks. The entity dimensions of PogRE are 1,000 on WN18R and YAGO3-10, and 1,500 on FB15k-237. loss. Furthermore, employing dense linear transfor- mations without QR decomposition was infeasible across all datasets; this demonstrates that models such as TransR (Lin et al., 2015), which rely on dense linear transformations, lack scalability due to their high computational costs. 6.3 Analysis Entity Independence As discussed in Sec- tion 4.2, PogRE ensures that any pattern be- comes progressively universal as more linearly independent entities are observed in the pattern. This implies that if the entity embeddings trained by PogRE are linearly independent, PogRE can achieve such progressive universality in practice. To investigate entity independence, we randomly sample entity embeddings trained by PogRE and compute the rank of the space spanned by the sam- pled entities. Table 4 shows the mean rank of the subspace spanned by sampled entities over 100 ran- dom trials. We empirically observe that the rank of the space spanned by the randomly sampled entities is approximately equal to the number of sampled entities, demonstrating that the sampled entities are linearly independent. These results indicate that, since entities in practice are shown to be linearly independent, the dimension of the space spanned by the entities increases as the number of observed entities increases, and that universal generalization is achieved when aroundd+1entities are observed. We also present empirical results on the indepen- dence of entities observed in specific patterns in Appendix G. Distribution of Patterns by Number of Pattern Instances Table 5 presents the distribution of composition patterns according to the number of their pattern instancesnacross three KG bench- marks. We compute the number of composition pat- terns as the number of relation sets(r x ,r y ,r z )∈ R that have at least one observed composition pat- # of Pattern Instances (n) WN18RRFB15k-237YAGO3-10 # of PatternsProp. (%)# of PatternsProp. (%)# of PatternsProp. (%) n = 11748.61,54626.35617.6 1 < n≤ 101440.02,28839.011235.2 10 < n≤ 10 2 411.41,43924.59128.6 10 2 < n≤ 10 3 --4898.35316.7 n > 10 3 --1111.961.9 Total35100%5,873100%318100% Table 5: Distribution of composition patterns accord- ing to the number of pattern instances (n) across three benchmark datasets. # of Pattern Instances and # of Pat- terns indicate the number of pattern instances and the number of patterns, respectively. Prop. (%) is calculated as the number of patterns within each range ofndivided by the total number of patterns, within each dataset. n = 1 n10 n10 2 n10 3 (a) Head Prediction 0.1 0.2 0.3 0.4 MRR n = 1 n10 n10 2 n10 3 (b) Tail Prediction 0.1 0.2 0.3 0.4 MRR 5000 10000 15000 Frequency 5000 10000 15000 Frequency TransERotatEPairRECompoundEOursFrequency Figure 4: MRR comparison between PogRE and base- line models for various sparsity conditions of pattern instances on FB15k-237. The black line indicates the number of test triples of G over . tern instance(ψ 1 ⇒ φ 1 )in the KG. In WN18R, FB15k-237 and YAGO3-10, 88.6%, 65.3% and 52.8% of composition patterns have 10 or fewer pattern instances, respectively. This result indicates that a substantial proportion of patterns in KGs are observed in only a few instances. These patterns can be generalized universally when a model suf- fers from over-generalization. The distributions of other patterns are presented in Appendix D. Quantified Impact of Over-generalization To investigate the impact of over-generalization, we extractG over , a set of triples(h,r,t), where candi- dates(h,r,t ′ )or(h ′ ,r,t)(witht ′ ̸= tandh ′ ̸= h) are heads of pattern instances whose bodies are in the training set, i.e., candidates(h,r,t ′ )or(h ′ ,r,t) areφ i ∈ G u o for which there is a corresponding ψ i ∈ G o . Intuitively, if the model suffers from over- generalization, the rank of(h,r,t)is lower than the rank of the candidate triples. To extractG over , we consider symmetry, inversion, composition, hi- erarchy, intersection, transitive, g.intersection, b. transitive and b. composition where the number of pattern instances isn = 1,n ≤ 10,n ≤ 10 2 , and n ≤ 10 3 . We compare the MRR of PogRE with other baselines: TransE, RotatE, PairRE, and Com- poundE onG over . Figure 4 presents the results on FB15k-237. We observe that PogRE consistently outperforms the baselines, regardless of the num- ber of pattern instances. These results show that PogRE effectively addresses the negative impact of over-generalization. The detailed definitions of G over and the comparison results for WN18R and YAGO3-10 are presented in Appendix D. 7 Conclusion In this paper, we propose PogRE, a novel KGE method that utilizes linear transformations and compound operations. PogRE addresses over- generalization, a phenomenon in which a model generalizes a pattern to every body instance in the graph after observing only a single instance. Our theoretical analysis shows that PogRE allows a pattern to become progressively universal as more linearly independent entities are observed. Experi- mental results on three benchmark datasets demon- strate the effectiveness of PogRE. Limitations To universally generalize patterns, PogRE does not utilize the semantics of patterns, which can be a useful inductive bias for pattern generaliza- tion. Therefore, for universal but low-frequency patterns, PogRE may fail to generalize them uni- versally, and for local but high-frequency patterns, PogRE may generalize them universally, result- ing in inappropriate generalization. This limitation arises when pattern frequency does not align with semantic universality. Accordingly, PogRE should be understood as alleviating, rather than fully re- solving, pattern over-generalization. To address this limitation, in future work, we will leverage the semantics of patterns for pattern generalization. Furthermore, PogRE is limited to the transduc- tive setting, where the goal is to learn and improve embedding structures for a fixed set of known en- tities and relations. Since PogRE explicitly learns entity and relation embeddings for entities and re- lations observed during training, it cannot directly represent entities or relations not observed during training. While extending PogRE to the inductive setting is an important problem for handling un- known entities and relations, addressing it requires substantially different assumptions and architec- tural designs. For this reason, we leave extending PogRE to the inductive setting as future work. Acknowledgements This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Ko- rea government(MSIT) (RS-2026-25520248) (Con- tribution Rate: 50%); the National Research Foun- dation of Korea (NRF) grant funded by the Korea government (MSIT) (No.2022R1A2C2012054, De- velopment of AI for Canonicalized Expression of Trained Hypotheses by Resolving Ambiguity in Various Relation Levels of Representation Learn- ing) (Contribution Rate: 40%); and Institute of Information & communications Technology Plan- ning & Evaluation (IITP) grant funded by the Ko- rea government (MSIT) (No.2019-0-01842, Artifi- cial Intelligence Graduate School Program (GIST)) (Contribution Rate: 10%). References Ivana Balaževi ́ c, Carl Allen, and Timothy Hospedales. 2019. Tucker: Tensor factorization for knowledge graph completion. In Proceedings of the 2019 Con- ference on Empirical Methods in Natural Language Processing and the 9th International Joint Confer- ence on Natural Language Processing (EMNLP- IJCNLP), pages 5185–5194. Anson Bastos, Kuldeep Singh, Abhishek Nadgeri, Saeedeh Shekarpour, Isaiah Onando Mulang, and Johannes Hoffart. 2021. Hopfe: Knowledge graph representation learning using inverse hopf fibrations. In Proceedings of the 30th ACM international con- ference on information & knowledge management, pages 89–99. Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008. Freebase: a collabo- ratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIG- MOD international conference on Management of data, pages 1247–1250. Antoine Bordes, Nicolas Usunier, Alberto Garcia- Duran, Jason Weston, and Oksana Yakhnenko. 2013. Translating embeddings for modeling multi- relational data. Advances in neural information pro- cessing systems, 26. Zongsheng Cao, Qianqian Xu, Zhiyong Yang, Xiaochun Cao, and Qingming Huang. 2021. Dual quaternion knowledge graph embeddings. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 6894–6902. Linlin Chao, Jianshan He, Taifeng Wang, and Wei Chu. 2021. Pairre: Knowledge graph embeddings via paired relation vectors. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Confer- ence on Natural Language Processing (Volume 1: Long Papers), pages 4360–4369. Victor Charpenay and Steven Schockaert. 2024. Cap- turing knowledge graphs and rules with octagon em- beddings. In Proceedings of the Thirty-Third Inter- national Joint Conference on Artificial Intelligence, pages 3289–3297. Victor Charpenay and Steven Schockaert. 2025. Less is mure: Revisiting shallow knowledge graph embed- dings. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pages 15428–15454. Guoquan Dai, Xizhao Wang, Xiaoying Zou, Chao Liu, and Si Cen. 2022. Mrgat: multi-relational graph attention network for knowledge graph completion. Neural Networks, 154:234–245. Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. 2018. Convolutional 2d knowl- edge graph embeddings. In Proceedings of the AAAI conference on artificial intelligence, volume 32. Chang Gao, Chengjie Sun, Lili Shan, Lei Lin, and Mingjiang Wang. 2020. Rotate3d: Representing re- lations as rotations in three-dimensional space for knowledge graph embedding. In Proceedings of the 29th ACM international conference on information & knowledge management, pages 385–394. Xiou Ge, Yun Cheng Wang, Bin Wang, and C-C Jay Kuo. 2023. Compounding geometric operations for knowledge graph completion. In Proceedings of the 61st Annual Meeting of the Association for Compu- tational Linguistics (Volume 1: Long Papers), pages 6947–6965. Zhanpeng Guan, Zhao Zhang, Yiqing Wu, Fuwei Zhang, and Yongjun Xu. 2025. Should we use a fixed embed- ding size? customized dimension sizes for knowledge graph embedding. In Proceedings of the 31st Inter- national Conference on Computational Linguistics, pages 9006–9012. Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118–22133. Seyed Mehran Kazemi and David Poole. 2018. Simple embedding for link prediction in knowledge graphs. Advances in neural information processing systems, 31. Narayanan Asuri Krishnan and Carlos R Rivero. 2024. A method for assessing inference patterns captured by embedding models in knowledge graphs. In Pro- ceedings of the ACM Web Conference 2024, pages 2030–2041. Juanhui Li, Harry Shomer, Jiayuan Ding, Yiqi Wang, Yao Ma, Neil Shah, Jiliang Tang, and Dawei Yin. 2023. Are message passing neural networks really helpful for knowledge graph completion? In Pro- ceedings of the 61st Annual Meeting of the Associa- tion for Computational Linguistics (Volume 1: Long Papers), pages 10696–10711. Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. 2015. Learning entity and relation embed- dings for knowledge graph completion. In Proceed- ings of the AAAI conference on artificial intelligence, volume 29. Hanxiao Liu, Yuexin Wu, and Yiming Yang. 2017. Ana- logical inference for multi-relational embeddings. In International conference on machine learning, pages 2168–2178. PMLR. Haonan Lu, Hailin Hu, and Xiaodong Lin. 2022. Dense: An enhanced non-commutative representation for knowledge graph embedding with adaptive semantic hierarchy. Neurocomputing, 476:115–125. Chuangtao Ma, Yongrui Chen, Tianxing Wu, Arijit Khan, and Haofen Wang. 2025. Large language mod- els meet knowledge graphs for question answering: Synthesis and opportunities. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pages 24589–24608, Suzhou, China. Association for Computational Linguistics. Farzaneh Mahdisoltani, Joanna Biega, and Fabian M Suchanek. 2013. Yago3: A knowledge base from multilingual wikipedias. In CIDR. George A Miller. 1995. Wordnet: a lexical database for english. Communications of the ACM, 38(11):39–41. Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. 2018. Spectral normalization for generative adversarial networks. In International Conference on Learning Representations. Maximilian Nickel, Lorenzo Rosasco, and Tomaso Pog- gio. 2016. Holographic embeddings of knowledge graphs. In Proceedings of the AAAI conference on artificial intelligence, volume 30. Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. 2011. A three-way model for collective learning on multi-relational data. In Proceedings of the 28th International Conference on International Conference on Machine Learning, pages 809–816. Aleksandar Pavlovi ́ c and Emanuel Sallinger. 2023. Ex- pressive: A spatio-functional embedding for knowl- edge graph completion. In The Eleventh Interna- tional Conference on Learning Representations. Aleksandar Pavlovi ́ c and Emanuel Sallinger. 2024. Speede: Euclidean geometric knowledge graph em- bedding strikes back. In Findings of the Association for Computational Linguistics: NAACL 2024, pages 69–92. Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. 2018. Modeling relational data with graph convolu- tional networks. In European semantic web confer- ence, pages 593–607. Springer. Chao Shang, Yun Tang, Jing Huang, Jinbo Bi, Xiaodong He, and Bowen Zhou. 2019. End-to-end structure- aware convolutional networks for knowledge base completion. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 3060– 3067. Yuan Sui, Yufei He, Nian Liu, Xiaoxin He, Kun Wang, and Bryan Hooi. 2025. Fidelis: Faithful reasoning in large language models for knowledge graph question answering. In Findings of the Association for Com- putational Linguistics: ACL 2025, pages 8315–8330. Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. 2019. Rotate: Knowledge graph embedding by relational rotation in complex space. In International Conference on Learning Representations. Kristina Toutanova and Danqi Chen. 2015. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd workshop on continuous vector space models and their composi- tionality, pages 57–66. Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. 2016. Complex embeddings for simple link prediction. In Interna- tional conference on machine learning, pages 2071– 2080. PMLR. Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. 2020. Composition-based multi- relational graph convolutional networks. In Interna- tional Conference on Learning Representations. Yanjie Wang, Daniel Ruffinelli, Rainer Gemulla, Samuel Broscheit, and Christian Meilicke. 2019. On evaluating embedding models for knowledge base completion. In Proceedings of the 4th Workshop on Representation Learning for NLP (RepL4NLP-2019), pages 104–112. Shiwen Xie, Yongfang Xie, Cheng Hu, and Tingwen Huang. 2025. Rotatq: Knowledge graph embedding based on quaternion unit. Neurocomputing, page 132413. Bishan Yang, Scott Wen-tau Yih, Xiaodong He, Jian- feng Gao, and Li Deng. 2015. Embedding entities and relations for learning and inference in knowledge bases. In Proceedings of the International Confer- ence on Learning Representations (ICLR) 2015. Qianjin Zhang, Ronggui Wang, Juan Yang, and Lixia Xue. 2022. Knowledge graph embedding by re- flection transformation. Knowledge-Based Systems, 238:107861. Shuai Zhang, Yi Tay, Lina Yao, and Qi Liu. 2019. Quaternion knowledge graph embeddings. Advances in neural information processing systems, 32. Siheng Zhang, Zhengya Sun, and Wensheng Zhang. 2020a. Improve the translational distance models for knowledge graph embedding. Journal of Intelligent Information Systems, 55(3):445–467. Zhanqiu Zhang, Jianyu Cai, Yongdong Zhang, and Jie Wang. 2020b. Learning hierarchy-aware knowledge graph embeddings for link prediction. In Proceed- ings of the AAAI conference on artificial intelligence, volume 34, pages 3065–3072. Yihua Zhu and Hidetoshi Shimodaira. 2024. Block- diagonal orthogonal relation and matrix entity for knowledge graph embedding. In Findings of the Association for Computational Linguistics: EMNLP 2024, pages 16956–16972. PatternConstraint Matrices (E = A ψ − A φ ) Hierarchy r 1 (X,Y )⇒ r 2 (X,Y ) (A r 1 − A r 2 )X = 0 Symmetry r(X,Y )⇒ r(Y,X) (A 2 r − I)X = 0 Antisymmetry r(X,Y )⇒¬r(X,Y ) (A 2 r − I)X ̸= 0 Inversion r 1 (X,Y )⇒ r 2 (Y,X) (A r 2 A r 1 − I)X = 0 Intersection r 1 (X,Y )∧ r 2 (X,Y )⇒ r 3 (X,Y ) (A r 1 − A r 3 )X = (A r 2 − A r 3 )X = 0 Transitivity r(X,Y )∧ r(Y,Z)⇒ r(X,Z) (A 2 r − A r )X = 0 Composition r 1 (X,Y )∧ r 2 (Y,Z)⇒ r 3 (X,Z) (A r 2 A r 1 − A r 3 )X = 0 Gen. Intersection r 1 (X,Y )∧ r 1 (Y,X)⇒ r 2 (X,Y ) (A r 1 A r 2 − I)X = (A r 1 − A r 2 )X = 0 B. Transitive r(Y,Z)∧ r(Z,X)⇒ r(X,Y ) (A 3 r − I)X = 0 Equality r(X,Z)∧ r(Y,Z)⇒ r(X,Y ) (I − A r )X = 0 B. Composition r 1 (Y,Z)∧ r 2 (Z,X)⇒ r 3 (X,Y ) (A r 2 A r 1 A r 3 − I)X = 0 Commonality r 1 (X,Z)∧ r 2 (Y,Z)⇒ r 3 (X,Y ) (A −1 r 2 A r 1 − A r 3 )X = 0 Table 6: Constraint matrices corresponding to various inference patterns. The patterns are presented in (Krish- nan and Rivero, 2024) A Constraint Matrices for Patterns and Local Pattern Generalization Constraint Matrices for Various Patterns Ta- ble 6 summarizes the derived constraint matrices for various patterns widely used in KG. Note that for patterns having multiple paths (e.g., Intersec- tion),Erepresents a set of matricesE 1 ,E 2 ,... to be satisfied simultaneously. Bounding Lipschitz Constants for Local Pattern Generalization to Unobserved Entities By ap- plying Spectral Normalization to the shared ma- trixR, we ensure that the spectral norm of each relation-specific linear transformation is bounded: ∥L r ∥ 2 ≤ 1. Since the constraint matrixEis de- fined asL ψ − L φ , the spectral norm ofEis also bounded by the triangle inequality: ∥E∥ 2 =∥L ψ − L φ ∥ 2 ≤∥L ψ ∥ 2 +∥L φ ∥ 2 ≤ 2 This bound ensures that the transformation defined by the constraint matrix is Lipschitz continuous. DatasetB N D γ αlrk WN18R512102410006.00.50.0000520 FB15k-237102425615006.01.00.0000520 YAGO3-101024400100024.01.00.00022 ogbl-biokg512128200012.01.00.00112 ogbl-wikikg240962501007.01.00.00520 Table 7: The best hyperparameter settings of PogRE for link prediction.B,N,D,γ,α,lr, andkdenote batch size, negative sampling size, dimension, gamma (presented in Equation 11), alpha (presented in Equation 12), learning rate, and number of Householder reflections, respectively. ModelRelation ParametersRequired Relation Tensors Peak GPU Memory During Training WN18RRFB15k-237 RotatEn r db× d11,384 MB11,391 MB PairRE2n r d2(b× d)14,370 MB10,855 MB PogREn r (k + 4)d + d(d+1) 2 4(b× d) + b× k× d + d(d+1) 2 14,624 MB12,627 MB PogRE w/o QRn r (d 2 + 4d)4(b× d) + b× d× dOOMOOM Table 8: Space complexity comparison of PogRE and baseline models.n r ,d,k, andbdenote the number of relations, embedding dimension, number of Householder reflections, and batch size, respectively. Peak GPU memory consumption is measured during training on WN18R and FB15k-237 using a single NVIDIA GeForce RTX 3090 under the same experimental settings. For an entitye obs that is known to satisfy the pat- tern (i.e.,∥Ee obs ∥ ≈ 0) and a semantically simi- lar but unobserved entitye unobs , the pattern error ∥Ee unobs ∥ for e unobs is bounded as follows: ∥Ee unobs ∥≤∥E∥ 2 ∥e unobs − e obs ∥ +∥Ee obs ∥ As shown in the inequality, if the distance∥e unobs − e obs ∥is small, the error∥Ee unobs ∥remains small. This mathematically guarantees that the model gen- eralizes the learned pattern from observed entities to semantically similar entities with similar embed- dings. B Implementation Details For the experiments, we adopt the hyperparam- eter settings from RotatE (Sun et al., 2019) for WN18R and YAGO3-10, and from PairRE (Chao et al., 2021) for FB15k-237. Additionally, for PogRE, the number of Householder reflectionsk is selected from2, 4, 8, 12, 20. More specifi- cally, we utilized the official implementations of RotatE (Sun et al., 2019) and PairRE (Chao et al., 2021) as our codebase. For the datasets, we used WN18R, FB15k-237, and YAGO3-10 as provided in the official RotatE repository, and the biokg and wikikg2 datasets as provided in the PairRE reposi- tory. Table 7 presents the exact batch size, negative sampling size, embedding dimension,γ, learning rate, andkused for each dataset. Our presented re- sults represent the mean of three independent runs for each dataset. Furthermore, ScalingS r and Ro- tationR r are used for FB15k-237 and YAGO3-10, whereas TranslationT r and RotationR r are used for WN18R. Finally, following Rotate3D (Gao et al., 2020), anL 2 regularizer is applied to en- tity embeddings for WN18R. Experiments for the PogRE were conducted on an NVIDIA 3090 with 24GB of memory. C Computational Complexity Space ComplexityTable 8 compares the number of relation parameters, the relation tensors required during batch scoring, and the peak GPU memory consumption during training.n r ,d,k, andbde- note the number of relations, embedding dimen- sion, number of Householder reflections, and batch size, respectively. In PogRE, the relation-specific orthogonal trans- formation is represented usingkHouseholder vec- tors, while the upper-triangular matrix is shared across all relations. Therefore, PogRE requires O(n r kd +d 2 )parameters for its dense linear trans- formations. In contrast, PogRE w/o QR assigns an independentd×ddense matrix to each relation, re- sulting inO(n r d 2 )relation parameters. The differ- ence becomes more pronounced during batch scor- ing. PogRE w/o QR requires ab×d×dtensor con- taining relation-specific dense matrices, whereas PogRE requiresb× k× drelation-specific House- holder vectors and a single sharedd× (d + 1)/2 matrix. This quadratic memory requirement at the batch level makes PogRE w/o QR infeasible under the same experimental setting and results in OOM. ModelTime Complexity Training TimeMRR WN18RRFB15k-237WN18RRFB15k-237 RotatEO(bd)1h 40m2h 20m.476.338 PairREO(bd)2h 20m3h.413.351 PogRE (k = 2)O(bd 2 )2h 50m3h.503.362 PogRE (k = 20)O(bd 2 )3h 40m4h 30m.506.369 PogRE (w/o QR)O(bd 2 )– Table 9: Time complexity, training time, and link prediction performance of PogRE and baseline models.bandd denote the batch size and embedding dimension, respectively. Training times are measured using a single NVIDIA GeForce RTX 3090 under the same experimental settings. 248122030 Number of Householder Reflection (k) 0.502 0.503 0.504 0.505 0.506 0.507 MRR MRR Training Time (Hours) # of Parameters (Million) Inference Time (Minute) 2.0 2.6 3.2 3.8 4.4 5.0 Training Time (Hours) 41.80 41.95 42.10 42.25 42.40 42.55 # of Parameters (Million) 0.4 0.7 1.0 1.3 1.6 1.9 Inference Time (Minute) (a) WN18R 248122030 Number of Householder Reflection (k) 0.360 0.362 0.364 0.366 0.368 0.370 MRR MRR Training Time (Hours) # of Parameters (Million) Inference Time (Minute) 2 3 4 5 6 7 Training Time (Hours) 24 27 30 33 36 39 # of Parameters (Million) 1.7 2.0 2.3 2.6 2.9 3.2 Inference Time (Minute) (b) FB15k-237 248122030 Number of Householder Reflection (k) 0.49 0.51 0.53 0.55 0.57 0.59 MRR MRR Training Time (Hours) # of Parameters (Million) Inference Time (Minute) 6.0 7.5 9.0 10.5 12.0 13.5 Training Time (Hours) 124.2 124.5 124.8 125.1 125.4 125.7 # of Parameters (Million) 3.0 3.6 4.2 4.8 5.4 6.0 Inference Time (Minute) (c) YAGO3-10 Figure 5: MRR, training time, inference time, and number of parameters of PogRE on three benchmark datasets. Time ComplexityTable 9 compares the theoreti- cal scoring complexity and the actual training time. PogRE w/o QR has the same theoretical time com- plexity as PogRE but is infeasible under the same experimental setting due to its substantially higher space complexity. PogRE has a higher theoretical time complexity than RotatE and PairRE because of the shared matrix multiplication. Nevertheless, its practical training time withk = 2remains com- parable to that of the baselines, while achieving higher performance in link prediction. Increasing kto 20 requires additional training time but further improves the MRR on both datasets. These results demonstrate that PogRE provides a practical trade- off between computational cost and performance. Figure 5 presents computational complexity and performance with respect to the Householder reflec- tionk. In WN18R and FB15k-237, performance improves askincreases but shows no significant improvement afterk = 20. This performance gain is accompanied by an increase in computational cost askgrows. In YAGO3-10, the MRR is high- est atk = 2and decreases askincreases. These results suggest that while a largerkcan improve performance by increasing the expressive power, excessive complexity may lead to a decrease in per- formance due to overfitting. Furthermore, there is almost no variation in inference time across differ- entkvalues, implying thatkcan be selected during training without concerns regarding inference time. D Impact of Over-generalization Detailed Definition of GroupG over Group G over consists of test triples(h,r,t)where at least one candidate triple(h,r,t ′ )(wheret ′ ̸= t) is φ i ∈ G u \ G o for which there is a correspond- ingψ i ∈ G o . In this case, the body instances corresponding to the candidate appear in the train- ing set. For instance, consider a local composition patternψ ⇒ φconsisting of the relation triplet (r 1 ,r 2 ,r). If the training set contains the body instances(h,r 1 ,x)and(x,r 2 ,t ′ )for at least one candidatet ′ and some entityx ∈ E, then the test triple(h,r,t)is assigned toG over . If KGE models suffer from over-generalization, they are likely to assign a high score to such a candidate(h,r,t ′ ), treating it as a valid triple. For simplicity, we only describe the case of tail prediction, but the same procedure applies to head prediction. For pattern, we consider symmetry, inversion, composition, hi- erarchy, intersection, transitive, g.intersection, b. transitive and b. composition patterns, as they are the most representative inference patterns exten- sively investigated across a wide range of KGE models. Antisymmetry is not considered because it ensures the absence of a head, rather than ensuring the presence of head. Quantified Impact of Over-generalizationFig- ure 6 presents the performance comparison on the G over across WN18R and YAGO3-10. Also in WN18R and YAGO3-10, PogRE consistently out- Model ogbl-biokgogbl-wikikg2 DimValid MRRTest MRRDimValid MRRTest MRR TransE20000.7456±0.00030.7452±0.00045000.4272±0.00300.4256±0.0030 DistMult20000.8055±0.00030.8043±0.00035000.3506±0.00420.3729±0.0045 ComplEx10000.8105±0.00010.8095±0.00072500.3759±0.00160.4027±0.0027 RotatE10000.7997±0.00020.7989±0.00042500.4353±0.00280.4332±0.0025 PairRE20000.8172 ±0.00050.8164±0.00052000.5423±0.00200.5208±0.0027 ComopoundE---1000.6716±0.00090.6473±0.0022 PogRE20000.8198±0.00010.8190±0.00031000.6841±0.00100.6606±0.0006 Table 10: Link prediction results on large-scale KGs, including ogbl-biokg and ogbl-wikikg2. Bold indicates the best result, and underline indicates the second best result. ± indicates the standard deviation. n = 1 n10 n10 2 n10 3 (a) Head Prediction 0.2 0.4 0.6 0.8 MRR n = 1 n10 n10 2 n10 3 (b) Tail Prediction 0.2 0.4 0.6 0.8 MRR 1000 2000 3000 Frequency 1000 2000 3000 Frequency TransERotatEPairRECompoundEOursFrequency (a) WN18R n = 1 n10 n10 2 n10 3 (a) Head Prediction 0.0 0.2 0.4 0.6 MRR n = 1 n10 n10 2 n10 3 (b) Tail Prediction 0.0 0.2 0.4 0.6 MRR 500 1000 1500 Frequency 500 1000 1500 Frequency TransERotatEPairRECompoundEOursFrequency (b) YAGO3-10 Figure 6: MRR comparison between PogRE and base- line models for various sparsity conditions of pattern in- stances on two benchmarks: WN18R (a), and YAGO3- 10 (b). The black line indicates the number of test triples for each group. performs the baselines regardless of the local pat- tern criteria and the dataset. These results demon- strate that PogRE effectively addresses the negative impact of over-generalization, and shows robust- ness across datasets. Distribution of Patterns by Number of Pattern Instances Table 20 presents the distribution of each pattern according to the number of its pat- tern instances (n) across three KG benchmark datasets.In WN18R, FB15k-237, and YAGO3-10, respectively, 20.0%, 22.7%, and 41.7% of sym- metry patterns, 27.3%, 24.6%, and 20.0% of anti- symmetry patterns, and 50.0%, 49.3%, and 58.8% of inversion patterns have 10 or fewer pattern in- stances. This result indicates that for symmetry, antisymmetry, and inversion, a substantial propor- tion of patterns in real-world KGs are observed in only a few instances. DatasetEntitiesRelations Triples TrainValidTest WN18R40,9431186,8353,0343,134 FB15k-23714,541237272,11517,53520,466 YAGO3-10123,182371,079,0405,0005,000 ogbl-biokg93,773514,763,814162,870162,886 ogbl-wikikg22,500,60453516,109,182429,456598,543 Table 11: Statistics of three benchmark datasets E Datasets WN18R, FB15k-237 and YAGO3-10 are used to evaluate PogRE. WN18R and FB15k-237 are sub- sets of WN18 (Bordes et al., 2013) and FB15k (Bor- des et al., 2013) with inverse relations removed, and YAGO3-10 is a subset of YAGO3 (Mahdisoltani et al., 2013) containing only entities with a mini- mum of 10 relations each. ogbl-biokg (Hu et al., 2020) is a large-scale biomedical KG, and ogbl- wikikg2 (Hu et al., 2020) is a Wikidata knowledge graph that contains a large number of triples. The statistics are summarized in Table 11. F Link Prediction Performance on Large-scale Knowledge Graph To verify the effectiveness of PogRE in large-scale KGs, we conduct additional experiments on biokg and wikikg2. As shown in the table 11, biokg and wikikg2 contain 4.7 million and 16.1 million triples, respectively, making them significantly larger than the standard benchmarks. The comparative results on biokg and wikikg2 are presented in Table 10. PogRE achieves the highest performance in both valid and test MRR compared to the baselines. For instance, PogRE achieves MRR improvements of 0.0027 and 0.0133 over the second-best models, PairRE and CompoundE, on biokg and wikikg2 in Test MRR, respectively. Furthermore, PogRE exhibits a low standard deviation (±0.001) across all datasets and settings, indicating that it consis- tently maintains stable performance regardless of initialization. This comparison demonstrates the robustness of our method across different datasets, Number of Sample Vector Rank WN18RRFB15k-237YAGO3-10 100100.0100.0100.0 200200.0200.0200.0 500500.0500.0500.0 1,000996.1±2.01000.0999.4±0.5 1,5001000.01492.8±1.21000.0 2,0001000.01500.01000.0 Table 12: Mean rank of the subspace spanned by ran- domly sampled entities in the specific pattern, over 100 random trials across three benchmarks. The entity di- mensions of PogRE are 1,000 on WN18R and YAGO3- 10, and 1,500 on FB15k-237. Model Over-Generalization Ratio n≤ 10 n≤ 10 2 n≤ 10 3 TransE.851.850.795 RotatE.866.852.793 PairRE.749.719.651 CompoundE.744.711.638 PogRE.707.681.618 Table 13: OG ratio comparison between KGE baselines and PogRE on FB15k-237.nindicates the number of pattern instances. especially in large-scale KGs. G Linear Independence of Entities Observed Within a Pattern In Section 6.3, we empirically observed that the di- mension of the space spanned by entities randomly sampled from the entire KG is approximately equal to the number of sampled entities. In this section, we further investigate whether entities observed within specific patterns—rather than across the en- tire KG—are also linearly independent of each other. Our experimental procedure is as follows: First, we randomly select a pattern containing at least 2,000 instances. We then randomly sampleN entities from this pattern (varyingNfrom 100 to 2,000) and measure the rank of the space spanned by these sampled entities. Finally, we repeat this process for 100 independent trials and report the average rank in Table 12. Our results demonstrate that the rank of the space spanned by these entities is approximately equal to the number of sampled entities, indicating that linear independence is in- deed preserved even within specific patterns. H Detailed Definition of the OG Ratio and Its Comparison on Various Patterns In this section, we provide a detailed definition of the OG Ratio and additional experiments on the OG Ratio. Detailed Definition of OG Ratio Since KGE is a relative distance-based method, if the score of a triple(h,r,t)is closer to 0 than that of another triple(h,r,t ′ ), it implies that the model considers (h,r,t)to be more plausible than(h,r,t ′ ). Based on this relative property, we define the OG ratio as follows. First, we extract head instances corre- sponding to the body instances of patterns in the KG. We then divide them into two groups—True triples and False triples—and measure the average score of each group (we exclude head instances that are in the training data, as they are used to train the models). Next, we define the OG ratio as the aver- age score of True triples divided by that of False triples. An OG ratio≈1 indicates that the model suffers from over-generalization, as it assigns sim- ilar scores to both True and False triples. An OG ratio≈0 implies that the model effectively avoids over-generalization by assigning higher scores to False triples compared to True triples. OG Ratio Comparison on Various PatternsWe use the OG ratio to verify whether our model effec- tively addresses over-generalization in the entire KG. Specifically, we extract True and False triples for patterns whose number of pattern instancesn satisfiesn≤ 10,n≤ 10 2 , andn≤ 10 3 in FB15k- 237, and compare the OG ratio of PogRE against KGE baselines, including TransE, RotatE, PairRE, and CompoundE. Table 13 presents a comparison of the OG ratios between PogRE and the KGE base- lines. Our model exhibits a lower OG ratio than all other models across all settings. This demonstrates that our model effectively addresses pattern over- generalization in the entire KG. This analysis was not conducted for WN18R and YAGO3-10; due to their small validation/test sets and data sparsity, these datasets contain very few True triples (fewer than 10). I Empirical Analysis of Local and Universal Patterns In Table 21, we present examples of local and universal patterns in real-world KGs based on hu- man verification. Because symmetry and inversion patterns can be easily classified as either univer- sal or local, we extract these patterns from three benchmark datasets: WN18R, FB15k-237, and YAGO3-10. For FB15k-237, due to the large num- ber of patterns, we randomly extract only 40 pat- terns. We then manually classify each pattern into two groups: semantically universal and semanti- Universal but Low FrequencyLocal but High Frequency _similar_to (74, WN)isLocatedIn (5742, YAGO) _also_see (828, WN)isLocatedIn, hasCapital (1743, YAGO) dealsWith (160, YAGO) hasNeighbor (550, YAGO) .../legislative_sessions (668, FB) .../military_combatant_group (620, FB) .../canoodled/participant (368, FB) .../marriage/spouse (342, FB) .../friendship/friend (204, FB) .../friendship/participant (1216, FB) .../dated/participant (1134, FB) Table 14: Representative examples of patterns catego- rized into the two failure case sets: universal but low frequency, and local but high frequency. The numbers in parentheses indicate the frequency of pattern instances, while WN, FB, and YAGO denote the WN18R, FB15k- 237, and YAGO3-10, respectively. cally local. We further categorize these patterns based on the number of pattern instances (n). Em- pirically, we observe that, in general, patterns that have low frequencies (n≤ 10) tend to be semanti- cally local, which can cause over-generalization in existing KGE models, leading to erroneous predic- tions. However, we also note that, due to the semantic complexity of real-world KGs, this general ten- dency may not always hold. We identify two repre- sentative failure cases for our proposed method. •First, universal but low-frequency patterns may appear when semantically universal pat- terns are observed in only a few instances due to dataset sparsity. In this case, PogRE may fail to generalize them universally. •Second, local but high-frequency patterns may appear when semantically local patterns have many observed instances. In this case, PogRE may generalize them universally, re- sulting in inappropriate generalization. Table 14, a subset of Table 21, shows examples of patterns in these two case sets. Each pattern is reported with its frequency and dataset. The universal but low-frequency set indicates semanti- cally universal patterns whose frequency is lower than the entity embedding dimension. The local but high-frequency set indicates semantically local patterns whose frequency is higher than the entity embedding dimension. We compare PogRE with KGE baselines on these cases. Specifically, for each dataset, we ex- tract test triples that contain relations included in each failure case set and measure MRR. Table 15 reports the MRR results for the universal but low frequency set. PogRE underperforms compared to ModelsWN18RRFB15k-237YAGO3-10 TransE0.2420.1030.213 RotatE0.6610.1210.377 PairRE0.6570.1250.303 CompoundE0.6600.1660.301 PogRE0.6860.1500.283 Table 15: MRR comparison between PogRE and base- line KGE models for the universal but low frequency case set across WN18R, FB15k-237, and YAGO3-10. Bold indicates the best performance. ModelsMRR TransE0.088 RotatE0.131 PairRE0.155 CompoundE0.185 PogRE0.172 Table 16: MRR comparison between PogRE and base- line KGE models for the local but high frequency case set. Note that the evaluated patterns for this case are observed exclusively within YAGO3-10. Bold indicates the best performance. CompoundE on FB15k-237 and YAGO3-10. This demonstrates the negative impact of the universal but low frequency failure case on performance of PogRE. Interestingly, PogRE still outperforms Com- poundE on WN18R. We analyze the reasons for this as follows. For WN18R, we measured the MRR for two patterns: _similar_to and _also_see. First, despite the _similar_to pattern having only 74 instances, all models except TransE achieved an MRR of 1.0. This pattern is a potential failure case, but not empirically harmful because of dataset- specific or relatively easy test structure. Further- more, the _also_see pattern has 828 instances. Al- though these instances may not span the entire em- bedding space, they still provide observed instances that can support generalization. As theoretically shown in Appendix A, our spectral normalization can help keep the pattern error bounded for un- observed entities if they are semantically similar to the observed entities. Therefore, PogRE can achieve generalization to semantically similar en- tities for _also_see, which can explain its superior performance on WN18R. Table 16 reports the MRR results for the local but high-frequency set (only evaluated on YAGO3- 10). In this case, PogRE also does not outperform CompoundE. This result indicates that PogRE may underperform existing models when semantically local patterns have high frequencies. Through this analysis, we clarify the applicabil- Pattern Type# of PI# of BIRatio (PI/BI) Local Pattern (film/written_by, actor/film, film/prequel)13740.176 Local Pattern (film/director, film/prequel, actor/film)221,8950.012 Universal Pattern (actor/film, film/country, people/nationality)5,03311,6590.432 Universal Pattern (people/place_of_birth, location/country, people/nationality)1,0821,4220.761 Table 17: Comparison of Pattern Instances (PI) and Body Instances (BI) between the local and universal patterns introduced in Figure 2. ’# of PI’ and ’# of BI’ represent the number of pattern instances and body instances, respectively. Pattern InstanceBody Instance 0 2500 5000 7500 10000 # of Instances r 1 : actor/film r 2 : film/country r 3 : people/nationality Pattern InstanceBody Instance 0 250 500 750 1000 1250 # of Instances r 1 : people/place_of_birth r 2 : location/contry r 3 : people/nationality Figure 7: The number of pattern instances and body instances for the universal patterns introduced in Fig- ure 2(b). ity boundary of PogRE. • Our method is designed to prevent the over- generalization of local patterns. •As shown in Table 21, most local patterns have low frequency, and therefore PogRE can generally improve performance on the overall datasets. •However, PogRE may underperform exist- ing models in failure cases where pattern frequency does not match pattern semantics, such as universal but low-frequency patterns or local but high-frequency patterns. •Therefore, PogRE is most suitable for KGs where low-frequency patterns are likely to be local and high-frequency patterns are likely to be universal. J Additional Empirical Evidence for Over-Generalization Comparison of the Number of Pattern and Body Instances Between Local and Universal Patterns In Figure 7, we present the number of pattern and body instances for the universal patterns introduced in Figure 2(b). Additionally, Table 17 compares the PI and BI of the local and universal patterns from Figure 2. As shown in Figure 7, the universal patterns are supported by 5,033 and 1,082 pattern instances, respectively. This significantly exceeds the number of pattern instances of local patterns (13 and 22), demonstrating that universal patterns are supported by a much larger number of observations. -0.2-0.10.00.10.2 Element Values of 0 500 1000 Frequency # of PI: 38 -0.2-0.10.00.10.2 Element Values of 0 500 1000 Frequency # of PI: 20 (a) Histograms of local patterns that are supported by scarce pattern instances.The relations for the left and right figures are (.../gardening_hint/split_to) and (.../us_county/county_seat), respectively. -0.2-0.10.00.10.2 Element Values of 0 500 1000 Frequency # of PI: 1660 -0.2-0.10.00.10.2 Element Values of 0 500 1000 Frequency # of PI: 12950 (b) Histograms of universal patterns that are supported by many pattern instances. The relations for the left and right figures are (.../location/adjoining_relationship...) and (.../award/award_nomination...), respectively. Figure 8: Histograms of embedding difference∆ = (r H 1 ) 2 − (r T 1 ) 2 for different symmetric relationsr 1 . # of PI denotes the number of pattern instances.r 1 are retrieved from FB15k-237. Furthermore, as shown in Table 17, universal pat- terns exhibit higher PI/BI ratios (0.432 and 0.761) compared to local patterns (0.176 and 0.012). This demonstrates that the patterns in Figure 2(b) exhibit universal characteristics. Empirical Evidence for the Symmetry Pattern To demonstrate that the over-generalization effect is not limited to the composition pattern discussed in Section 3, we conduct an additional analysis on the symmetry pattern using the same framework in Section 3, as follows. Similar to the composition pattern, PairRE also induces a relation-level pattern condition for sym- metry patterns. If a relationr 1 is symmetric, PairRE satisfies the following condition: (r H 1 ) 2 = (r T 1 ) 2 (18) This condition is determined only by relation embeddings. Therefore, once this condition is learned from observed triples, the model can gen- eralize the symmetry pattern to other entities, even Pattern InstanceBody Instance 0 20 40 60 80 100 # of Instances r 1 : _hint/split Pattern InstanceBody Instance 0 50 100 150 # of Instances r 1 : /county_seat (a) The number of pattern instances and body instances for the local patterns introduced in Figure 8(a). Pattern InstanceBody Instance 0 500 1000 1500 2000 # of Instances r 1 : /location/adjoin Pattern InstanceBody Instance 0 5000 10000 15000 # of Instances r 1 : /nomination (b) The number of pattern instances and body instances for the universal patterns introduced in Figure 8(b). Figure 9: The number of pattern instances and body instances for the local and universal symmetry patterns introduced in Figure 8 when the pattern is supported by only a small num- ber of instances. This can lead to pattern over- generalization for local symmetry patterns. We empirically verify this by measuring the distribu- tion of∆ = (r H 1 ) 2 − (r T 1 ) 2 . Figure 8 shows the histograms of the embedding difference (∆) of lo- cal and universal symmetry patterns. Figures 8(a) and 8(b) show that the elements of∆are concen- trated near zero for both local and universal pat- terns, indicating that the model recognizes both as valid symmetry patterns regardless of instance fre- quency. The numbers of pattern instances and body instances for these symmetry patterns are shown in Figure 9. This analysis empirically shows that pattern over-generalization also occurs in another pattern type. K Bounding Constraint Errors Under Practical Training Dynamics In Section 4.2, we provide a theoretical analysis showing that a dense linear transformation can ad- dress over-generalization. However, in practice, KGE embeddings are optimized with negative sam- pling and a margin-based loss; therefore, the con- straintEe i = 0is approximate. That is, satisfying the exact linear constraintEe i = 0is challenging due to the approximate nature of margin-based op- timization with negative sampling. However, we can mathematically guarantee that the constraint er- ror for unseen entities is bounded by the constraint error of observed entities. Specifically, let us as- sume the model is sufficiently trained such that the constraint error is minimized within a small mar- ginεfor the observed linearly independent entities e 1 ,...,e d (i.e., we consider the practical scenario in which∥Ee i ∥ < ε, rather than the exact condi- tion∥Ee i ∥ = 0.) Since we empirically verified that the learned entity embeddings form a basis (Section 6.3), any unseen entitye new can be rep- resented as a linear combination of the observed entities:e new = P d i=1 c i e i . By the linearity of the transformationEand the triangle inequality, the error for the unseen entity is bounded as follows: ∥Ee new ∥ = d X i=1 c i (Ee i ) ≤ d X i=1 |c i |·∥Ee i ∥ < d X i=1 |c i | ! ε (19) This inequality demonstrates that minimizing the constraint error of observed entities (ε → 0) di- rectly suppresses the constraint error for unseen entities. Therefore, even under the approximate optimization of margin-based loss, the constraint error of unseen entities remains bounded. Through this analysis, we clarify the practical scope of the theoretical guarantees of our method. In practice, exact constraint satisfaction, corresponding to the ideal zero-error case, i.e.,∥Ee i ∥ = 0, is not guar- anteed after training. Rather, when the constraint errors of observed entities are small, corresponding to the approximate case, i.e.,∥Ee i ∥ < ε, the errors of unseen entities can also be bounded, thereby en- suring the practical effectiveness of our proposed method. Practical Strength of the AssumptionsOur the- oretical analysis involves two assumptions: (1) the approximate satisfaction of pattern constraints for observed entities and (2) the availability ofd + 1 linearly independent observed entities. We discuss the practical strength of these assumptions below. First, the practical strength of the approximate pattern-constraint assumption depends on how small the residuals become in practice. The approx- imate satisfaction of pattern constraints is encour- aged by the KGE training objective. The training objective reduces the errors of observed pattern in- stances, thereby encouraging small residuals in the corresponding pattern constraints. However, be- cause training relies on mini-batch gradient-based optimization, it is difficult to know how small the residuals will be after training, making the practical ModelScore FunctionPattern ModelingOver-GeneralizationScalability MRR WN18RRFB15k-237 RERSCAL< h T W r t >✗-✗.420.270 TransR −∥P r h + r− P r t∥✗-✗.220.299 CompoundE −∥M r · h− ˆ M r · t∥✓.491.357 PogRE −∥L r h r − t r ∥✓✗✓.506.369 Table 18: Summary of differences between PogRE and the existing linear transformation models. RESCAL is reproduced in Wang et al. (2019), and TransR is reproduced in Zhang et al. (2020a).W r andP r areR d×d dense linear transformations, where d is the dimension of entities and relations. strength difficult to assess a priori. Consequently, our approximate analysis above is conditional on the residuals actually achieved after training. Second, the requirement of observingd + 1lin- early independent entities should be understood as a sufficient condition for universal generalization, rather than as a condition that must always hold. As more linearly independent entities supporting a pat- tern are observed, the pattern constraint applies to a larger subspace; universal generalization is guar- anteed when these entities span the relevant space. We regard this requirement as part of an inherent trade-off. If this condition is made less strict, the model may generalize patterns more easily. How- ever, this may also increase the risk of generalizing weakly supported patterns too broadly, which may lead to the over-generalization problem that PogRE is designed to avoid. L Differences between the existing linear transformation model and PogRE We present a comparison between existing linear transformation models and PogRE in Table 18. Existing models that use dense linear transforma- tion such as RESCAL (Nickel et al., 2011) and TransR (Lin et al., 2015) are not designed for pat- tern modeling; moreover, when the entity and re- lation dimensions aren, they assign anR n×n ma- trix to each relation, leading to high computational costs as the dimension of entities and relations increases. While CompoundE is capable of pat- tern modeling and avoids these computational is- sues by using sparse affine transformation, it suf- fers from over-generalization. In contrast, PogRE is designed for pattern modeling, addresses the over-generalization problem, and avoids the com- putational cost issue using a QR-decomposition- inspired method. In addition, PogRE outperforms existing models on WN18R and FB15k-237, demonstrating its effectiveness. ModelWN18RRFB15k-237 R-GCN (Schlichtkrull et al., 2018)–.248 SACN (Shang et al., 2019).470.350 CompGCN (Vashishth et al., 2020).479.355 MRGAT (Dai et al., 2022).481.358 CompGCN-MLP (Li et al., 2023).473.355 PogRE.506.369 Table 19: MRR comparison between PogRE and trans- ductive GNN-based models on WN18R and FB15k- 237. M Comparison with Transductive GNNs TransductiveGNNmodelssuchasR- GCN (Schlichtkrull et al., 2018), SACN (Shang et al., 2019), and CompGCN (Vashishth et al., 2020) improve entity representations through message passing,which incorporates local structural context into entity embeddings. By leveraging structural context, these models may also alleviate pattern over-generalization. However, pattern over-generalization has not been explicitly discussed or analyzed in transductive GNN models. In particular, prior work has not characterized how transductive GNN models capture patterns or how the patterns captured by transductive GNN models are generalized from observed evidence. In contrast, PogRE explicitly models patterns and is designed to improve entity representations while alleviating pattern over-generalization. We further compare PogRE with these transduc- tive GNN models in terms of MRR. As shown in Ta- ble 19, PogRE outperforms the baselines across the available benchmarks, demonstrating that PogRE remains effective compared with graph-contextual baselines. Pattern # of Pattern Instances (n) WN18RRFB15k-237YAGO3-10 # of Patterns Prop. (%) # of Patterns Prop. (%) # of Patterns Prop. (%) Symmetry n = 1--613.6-- 1 < n≤ 10120.049.1541.7 10 < n≤ 10 2 120.01022.7-- 10 2 < n≤ 10 3 120.01738.6433.3 n > 10 3 240.0715.9325.0 Total5100%44100%12100% Antisymmetry n = 119.111.8-- 1 < n≤ 10218.21322.8320.0 10 < n≤ 10 2 218.22645.6533.3 10 2 < n≤ 10 3 218.21322.8213.3 n > 10 3 436.447.0533.3 Total11100%57100%15100% Inversion n = 1330.05218.6635.3 1 < n≤ 10220.08630.7423.5 10 < n≤ 10 2 550.08329.6423.5 10 2 < n≤ 10 3 --5118.215.9 n > 10 3 --82.9211.8 Total10100%280100%17100% Composition n = 11748.61,54626.35617.6 1 < n≤ 101440.02,28839.011235.2 10 < n≤ 10 2 411.41,43924.59128.6 10 2 < n≤ 10 3 --4898.35316.7 n > 10 3 --1111.961.9 Total35100%5,873100%318100% Hierarchy n = 1112.57221.41119.6 1 < n≤ 10225.09428.01628.6 10 < n≤ 10 2 562.511433.91425.0 10 2 < n≤ 10 3 --5014.91221.4 n > 10 3 --61.835.4 Total8100%336100%56100% Intersection n = 1--43829.61815.0 1 < n≤ 10--64243.35445.0 10 < n≤ 10 2 --37825.54235.0 10 2 < n≤ 10 3 --241.665.0 n > 10 3 ------ Total--1,482100%120100% Transitive n = 1--24.1-- 1 < n≤ 10116.7816.3533.3 10 < n≤ 10 2 233.31632.7426.7 10 2 < n≤ 10 3 350.01122.4213.3 n > 10 3 --1224.5426.7 Total6100%49100%15100% G.Intersection n = 1233.32113.0218.2 1 < n≤ 10--5433.5545.5 10 < n≤ 10 2 466.77043.5218.2 10 2 < n≤ 10 3 --148.7218.2 n > 10 3 --21.2-- Total6100%161100%11100% B. Transitive n = 1--615.8-- 1 < n≤ 10--25.3112.5 10 < n≤ 10 2 133.31128.9225.0 10 2 < n≤ 10 3 266.6923.7337.5 n > 10 3 --1026.3225.0 Total3100%38100%8100% B. Composition n = 11240.01,27828.437.1 1 < n≤ 101860.01,71038.11535.7 10 < n≤ 10 2 --1,05323.41228.6 10 2 < n≤ 10 3 --3457.71228.6 n > 10 3 --1082.4-- Total30100%4,494100%42100% Table 20: Distribution of inference patterns: Symmetry/Antisymmetry, Inversion, Composition, Hierarchy, Intersec- tion, Transitive, G.Intersection, B. Transitive and B. Composition according to the number of pattern instances (n) across three benchmark datasets. # of Pattern InstancesSemantically Universal (n)Semantically Local (n) n≤ 10-owns (4) (S) isAffiliatedTo (10) (S) isKnownFor (4) (S) created (2) (S) hasAcademicAdvisor (4) (S) influences, created (3) (I) influences, isInterestedIn (8) (I) participatedIn, isCitizenOf (1) (I) created, hasAcademicAdvisor (1) (I) isAffiliatedTo, isMarriedTo (1) (I) isLocatedIn, isConnectedTo (1) (I) influences, isKnownFor (5) (I) isLocatedIn, dealsWith (1) (I) influences, hasChild (1) (I) isMarriedTo, influences (8) (I) _synset_domain_topic_of (2) (S) _synset_domain_topic_of, _has_part (9) (I) _hypernym, _derivationally_related_form (17) (I) _derivationally_related_form, _member_meronym (23) (I) _hypernym, _also_see (38) (I) _hypernym, _synset_domain_topic_of (4) (I) _also_see, _verb_group (1) (I) _hypernym, _verb_group (17) (I) _has_part, _member_of_domain_region (1) (I) _instance_hypernym, _member_of_domain_region (1) (I) _derivationally_related_form, _synset_domain_topic_of (23) (I) /location/ ...division/country (4) (S) /location/country/capital (3) (S) /film/film/prequel (2) (S) /people/person/profession (1) (S) /film/film/genre (1) (S) /film/film_subject/films (1) (S) /base/aareas/schema /administrative_area/capital (1) (S) /medicine/symptom/symptom_of (1) (S) /music/instrument/family (1) (S) .../sibling_relationship .../influenced_by (2) (I) ../romantic_relationship/celebrity (1) (I) 10 < n≤ 100_similar_to (74) (S)isLocatedIn, participatedIn (50) (I) isMarriedTo, hasChild (59) (I) influences, hasAcademicAdvisor (63) (I) isLocatedIn, owns (60) (I) 100 < n≤ 1000dealsWith (160) (S)influences (180) (S) hasNeighbor (550) (S)hasChild (414) (S) _also_see (828) (S)dealsWith, hasNeighbor (165) (I) .../legislative_sessions (668) (S).../award_nomination/nominated_for (592) (S) .../military_combatant_group/combatants (620) (S).../recording .../performance_role (402) (S) .../canoodled/participant (368) (S).../award_honor/honored_for (392) (S) .../marriage/spouse (342) (S).../education/major_field_of_study (282) (S) .../friendship/friend (204) (S).../sports_team_roster/position (106) (S) .../location/contains, .../first_level_division_of (124) (I) .../genre/titles, ...film/country (157) (I) .../performance/film, ...award_winner (963) (I) .../sports_team_roster/team, .../american_football/ .../position (470) (I) ...location/contains, .../mailing_address/state_province_region (359) (I) .../regular_tv_appearance/actor, .../award_nomination/nominated_for (445) (I) ...location/contains, .../mailing_address/country (103) (I) .../award_nomination/nominated_for, .../produced_by (497) (I) .../dated/participant, ../romantic_relationship/celebrity (136) (I) .../award_nomination/nominated_for, /film/film/music (314) (I) .../music/group_membership/role, .../performance_role (246) (I) .../dated/participant, .../spouse (108) (I) n > 1000isMarriedTo (3674) (S)isLocatedIn (5742) (S) happenedIn, participatedIn (1468) (I)isLocatedIn, hasCapital (1743) (I) _derivationally_related_form (27701) (S) _verb_group (1060) (S) .../award_nomination/award_nominee (12950) (S) .../award_honor/award_winner (6860) (S) .../track_contribution/role (3068) (S) .../group_membership/role (2170) (S) .../adjoining_relationship/adjoins (1660) (S) .../friendship/participant (1216) (S) .../dated/participant (1134) (S) Table 21: Human verification results of semantically universal and semantically local patterns, categorized by the number of pattern instances. The number next to each pattern indicates the number of pattern instances, and (S) and (I) indicate symmetry and inversion, respectively.