Title: A GROUP-THEORETIC FRAMEWORK FOR KNOWL-EDGE GRAPH EMBEDDING Anonymous

Abstract: We have rigorously proved the existence of a group algebraic structure hidden in relational knowledge embedding problems, which suggests that a group-based embedding framework is essential for designing embedding models. Our theoretical analysis explores merely the intrinsic property of the embedding problem itself hence is model independent. Using the proposed framework, one could construct embedding models that naturally accommodate all possible local graph patterns, which are necessary for reproducing a complete graph from knowledge triplets. We reconstruct many state-of-the-art models from the framework and re-interpret them as embeddings with different groups. Moreover, we also propose new instantiation models using simple continuous non-abelian groups.

1. INTRODUCTION:

Knowledge graphs (KGs) are prominent structured knowledge bases for many downstream semantic tasks (Hao et al., 2017) . A KG contains an entity set E = {e i }, which correspond to vertices in the graph, and a relation set R = {r k }, which forms edges. The entity and relation sets form a collection of factual triplets, each of which has the form (e i , r k , e j ) where r k is the relation between the head entity e i and the tail entity e j . Since large scale KGs are usually incomplete due to missing links (relations) amongst entities, an increasing amount of recent works (Bordes et al., 2013; Yang et al., 2014; Trouillon et al., 2016; Lin et al., 2015) have devoted to the graph completion (i.e., link prediction) problem by exploring a low-dimensional representation of entities and relations.

More formally, each relation r acts as a mapping O r [•] from its head entity e 1 to its tail entity e 2 :

r : e 1 → O r [e 1 ] =: e 2 .

(1)

The original KG dataset represents these mappings in a tabular form, and the task of KG embedding is to find a better representation for these abstract mappings. For example, in the TransE model (Bordes et al., 2013) , relations and entities are embedded in the same vector space, and the operation O r [•] is simply a vector summation: O r [e] = e + r. In general, the operation could be either linear or nonlinear, either pre-defined or learned.

Since the entity and relation sets in KGs play conceptually different roles, it is reasonable to represent them differently, which demands a more proper operation O r [•] for bridging the entity and relation sets. On the other hand, the graph completion task relies on the fact that relations are not independent. For example, the hypernym and hyponym are inverse to each other; while kinship relations usually support mutual inferences. Previous studies (Sun et al., 2019; Xu & Li, 2019) have concerned some specific cases of inter-relation dependencies, including (anti-)symmetry and compositional relations. However, one may ask a more general question: could we establish certain fundamental principles to guide the operation design, such that any inter-relation dependency could be naturally captured? In this work, we find the answer is positive, and we term these principles as hyper-relations. Group theory emerges as a natural description tool that satisfies the need for finding better operations and hyper-relations. In the following sections, we demonstrate the emergence of group definition, namely closure, identity, inverse, and associativity, from a study of knowledge graph itself, and explain in detail an implementation of group theory to tackle general relational embedding problems.

One main contribution of this work is it provides a framework for addressing the KG embedding problem from a novel and more rigorous perspective: the group-theoretic perspective. This frame-work arises from our investigation of the graph reconstruction problem. We prove that the intrinsic structure of this task automatically produces the complete definition of groups. To our best knowledge, this is the first proof that rigorously legitimates the application of group theory in KG embedding. With this framework, we reconstructed several existing models using group theory language (see Sec 3.3), including: TransE (Bordes et al., 2013) , TransR (Lin et al., 2015) , TorusE (Ebisu & Ichise, 2018) , RotatE (Sun et al., 2019) , ComplEx (Trouillon et al., 2016) , DisMult (Yang et al., 2014) .

2. RELATED WORKS:

From the group theory perspective, our work may be related to the TorusE (Ebisu & Ichise, 2018) , the RotatE (Sun et al., 2019) and DihEdral (Xu & Li, 2019) models. The TorusE model tries to frame the KG embedding in a Lie-group and deals with the compactness problem. Its authors proved that the additive nature of the operation in the TransE model contradicts the entity regularization. However, if a non-compact embedding space is used, entities must be regularized to prevent the divergence of negative scores. Therefore the TorusE model used n-torus, a compact manifold, as the embedding space. In other words, a group is regarded as a manifold, rather than as a set of operations where algebraic structures are more emphasized. Besides, the compactness issue was solved in many later works by bounding the training objective using Softplus function (Sun et al., 2019) . In the DihEdral model, the D 4 group the author used plays the same role as in our work: depicting the transformation of entities by assigning each relation a group element. The motivation of DihEdral is to resolve the non-abelian composition (i.e., the compositional relation formed by r 1 and r 2 would change if the two are switched). Nevertheless, DihEdral applies a discrete group D 8 for relation embedding while using a continuous entity embedding space, which may suffer two problems as discussed in the later Section 3.3. The RotatE model was designed to accommodate symmetric, inversion, and (abelian) composition of triplets at the same time.

Different from those previous works, this work does not target at one or few specific cases but aims at answering the more general question: finding the generative principle of all possible cases, and thus to provide guidance for model designs that can accommodate all cases. More importantly, compared with most preceding works connecting to groups (Xu & Li, 2019; Cai, 2019) , the analysis in our current work does not focus on impose an implementation of groups. Rather, we start merely by studying the graph reconstruction problem and prove that the intrinsic structure of this task itself automatically produces the complete definition of groups. To our the best of our knowledge, this is the first proof that rigorously legitimates the application of group theory in KG embeddings.

3. GROUP THEORY IN RELATIONAL EMBEDDINGS:

In this section, we formulate the group-theoretic analysis for relational embedding problems. For simplicity, our discussion would start from 1-to-1 mappings and discuss the generalization to more complicated cases in the Appendix D.

Firstly, as most embedding models represent objects (including entities and relations) as vectors, the task of operation design thus can be stated as finding proper transformations of vectors. Secondly, as we mentioned in the introduction, our ultimate goal of reproducing the whole knowledge graph using atomic triplets further requires certain types of local patterns to be accommodated. We now discuss these structures, which in the end naturally leads to the definition of groups in mathematics.

3.1. HYPER-RELATION PATTERNS: RELATION-OF-RELATIONS:

One difficulty of generating the whole knowledge graph from atomic triplets lies in the fact that different relations are not independent of each other. The task of relation inference relies exactly on their mutual dependency. In other words, there exist certain relation of relations in the graph structure, which we term as hyper-relation patterns. A proper relation embedding method and the associated operations should be able to capture these hyper-relations. Now instead of studying exampling cases one by one, we ask the most general question: what are the most fundamental hyper-relations? The answer is quite simple and only contains two types, namely, inversion and composition:

• Inversion: given a relation r, there may exist an inversion r, such that:

r : e 1 → e 2 -→ r : e 2 → e 1 , ∀e 1 , e 2 ∈ E.

(2)

The inversion captures any relation path with a length equal to 1 (in the unit of relations). • Composition: given two relations r 1 and r 2 , there may exist a third relation r 3 , such that:

EQUATION

Any relation paths longer than 1 can be captured by a sequence of compositions.

One may notice the phrase may exist in the above definition, this simply emphasizes that the existence of these derived conceptual relations r and r 3 depends on the specific KG dataset; while, on the other hand, to accommodate general KG datasets, the embedding space should always contains the mathematical representations of these conceptual relations.

An important feature of KG is that with the above two hyper-relations, one could generate any local graph pattern and eventually the whole graph, as relational paths with arbitrary length have been captured. Note the term of inversion and composition might have different meanings from ones in other works: most existing works study triplets to analyze hyper relations, while the definition we provide above is based purely on relations. This is more general in the sense that any conclusion derived would not depend on entities at all, and some different hyper relations could, therefore, be summarized as a single one. For example, there are enormous discussions on symmetric triplets and anti-symmetric triplets (Sun et al., 2019) , which are defined as:

symmetric: (e 1 , r, e 2 ) -→ (e 2 , r, e 1 ), anti-symmetric: (e 1 , r, e 2 ) -→ ¬(e 2 , r, e 1 ).

(4)

In fact, if for any choice of e 1,2 , one could produce a symmetric pair of true triplets using r, this would imply a property of r itself, and in which case, one could then simply derive:

EQUATION

This is a special case of the inversion hyper-relation; and similarly, the anti-symmetric case simply implies r = r, which is quite common, and does not require extra design. The deep reason for discussing hyper-relations which relies merely on relations rather than triplets is that the logic of relation inference problem itself is not entity-dependent.

3.2. EMERGENT GROUP THEORY:

To accommodate both general inversions and general compositions, we now derive explicit requirements on the relation embedding model. We start by defining the product of two relations r 1 and r 2 : r 1 • r 2 , as subsequently "finding the tail" twice according to the two relations, i.e.

EQUATION

With the above definition, equation 3 can be rewritten as:

r 3 = r 1 • r 2 .

One would realize that the following properties should be supported by a proper embedding model:

1. Inverse element: to allow the possible existence of inversion, the elements r should also be an element living in the same relation-embedding space1 . 2. Closure: to allow the possible existence of composition, in general, the elements r 1 • r 2 should also be an element living in the same relation-embedding space2 . 3. Identity element: the possibly existing inverse and composition together define another special and unique relation:

EQUATION

This element should map any entity to itself, and thus we call it identity element.

4.. Associativity::

In a relational path with the length longer than three (containing three or more relations {r 1 , r 2 , r 3 , ...}), as long as the sequential order does not change, the following two compositions should produce the same result:

(r 1 • r 2 ) • r 3 = r 1 • (r 2 • r 3 ).

(8) See Appendix A for the proof. 5. Commutativity/Nonconmmutativity: In general, commuting two relations in a composition, i.e. r 1 • r 2 ↔ r 2 • r 1 , may compose either the same or different results. In real graphs, any cases may exist, and a proper embedding method should be able to accommodate both. 3The first four properties are exactly the definition of a group. In other words, the group theory automatically emerges from the relational embedding problem itself, rather than being applied manually. This is quite convincing evidence that group theory is indeed the most natural language for relational embeddings if one aims at ultimately reproducing all possible local patterns in graphs. Besides, the fifth property on commutativity/nonconmmutativity are actually termed as abelian/nonabelian in the group theory language. Since abelian is more special, to accommodate both possibilities, one should, in general, consider a nonabelian group for the relation embedding, and guarantee at the same time it contains at least one nontrivial abelian subgroup.

More explicitly, given a graph, to implement a group structure in embedding, one should embed all relations as group elements, which are parametrized by certain group parameters. For instance: the translation group T can be parametrized by a real number δ. And correspondingly, due to its vector nature, the embedding of entities could be regarded as a representation (rep) space of the same group. For the translation group, R (the real field) is a rep space of T .

This suggests the group representation theory is useful in knowledge graph embedding problems when talking about entity embeddings, and we leave this as a separate topic for subsequent works later. In the later section, we provide a general recipe for the graph embedding implementation.

3.3. EMBEDDING MODELS USING DIFFERENT GROUPS:

In this section, we discuss embedding methods using different groups, from simple ones as T (the translation group) and U (1), to complicated ones including SU (2), GL(n, V) (where V could be any type of fields), or even Aff (V). It is important to note that, in practice, continuous groups are more reasonable than discrete ones, due to the two following reasons:

• The entity embedding space is usually continuous, which matches reps of the continuous group better. If used to accommodate a discrete group, a continuous space always contains infinite copies of irreducible reps of that group, which makes the analysis much more difficult. • When training the embedding models, a gradient-based optimization search would be applied in the parameter space. However, different from continuous groups whose group parameter are also continuous, the parametrization of a discrete group uses discrete values, which brings in extra challenges for the training procedure.

With the two reasons above, we thus mainly consider continuous groups which are more reasonable choices. Although for completeness, we also compare the group D 4 as it is implemented in DihEdral (Xu & Li, 2019) . Two other important feature of a group are compactness and commutativity, which we would mention in each case below.

Besides the relational embedding group G, the entity embedding space and the similarity measure also need to be determined. As discussed above, the entity embedding should be a proper rep space of G. While for similarity measure d(•), we choose among the popular ones including L p -norms (L p ) and the cos-similarity (cos). We would notice many choices reproduce some precedent works.

We summarize the results of several chosen examples in 

4. GROUP EMBEDDING FOR KNOWLEDGE GRAPHS:

In this section, we would firstly provide a general recipe for the group embedding implementation, and then provide an explicit example, which applies a continuous nonabelian group that has not been studied in any precedent works before.

4.1. A GENERAL GROUP EMBEDDING RECIPE:

We summarize the group embedding procedure as following:

1. Given a graph, choose a proper group G for embedding. The choice may concern property of the task, such as commutativity and so on. And as stated above, in most general cases, a nonabelian continuous group should be proper.

2. Choose a rep-space for the entity embedding. For simplicity, one could use multiple (n) copies of the same rep ρ, which is the case of most existing works. Suppose ρ is a p-dim rep, then the total dimension of entity embedding would be pn, which is written as a vector v e . Roughly speaking, k captures the relational structure and n encodes other feature.

3. Choose a proper parametrization of G, that is, choose a set of parameters indexing all group elements in G. Suppose the number of parameters required to specify a group element is q, then the total dimension of relation embedding v r would be qn. A group element can now be expressed as a block-diagonal matrix R r , with each block M i being a p × p matrix whose entries are determined by the vector v r .

4. Choose a similarity measure d[•], the score value of a triplet (e 1 , r, e 2 ) is then:

EQUATION

4.2. AN EXAMPLE OF NONABELIAN GROUP EMBEDDING: SU2E:

The 2D special unitary group SU (2) is one of the simplest continuous nonabelian group. As an illustrative demonstration, we construct an embedding model with SU (2) structure and implement it in real experiments. As we mentioned in Table 1 , SO(3) is also a nice example group. The reason we study SU (2) rather than SO(3), is from a well-known mathematical fact4 : the universal cover of SO(3) is Spin(3) which is isomorphic to SU (2); or in the representation language, any rep of SO(3) corresponds to an integer rep of SU (2). This reveals that a study of SU (2) is more general and could easily cover the theory of SO(3).

Following the general recipe above, after determining the group G = SU (2), we choose a proper rep-space for entity embedding: [C 2 ] ⊗n , which consists n-copies of C 2 . Each C 2 subspace transforms as the standard rep-space of SU (2). All relations thus act as 2n × 2n block diagonal matrix, with each block being a 2 × 2 complex matrix carrying the standard representation of SU (2).

Next, we choose a proper parametrization of SU (2). An analysis with the corresponding Lie algebra su(2) shows that any group element could be written as (Hall & Hall, 2003) :

EQUATION

)

where α is a rotation angle taken from [0, 2π], and n is a unit vector on 2-sphere, represented by two other angles (θ, φ); moreover, the symbol 1 means an identity matrix, and J are three generators of the group SU (2): (J x , J y , J z ), which, in the standard rep have the following form:

EQUATION

)

Put all together, our group embedding is then fixed as:

EQUATION

where x i and y i are complex numbers, and α i and ni = (θ i , φ i ) represent angles. In a triplet, the relation v r acts as a block diagonal matrix R r , with each 2 × 2 block M i parametrized as (Hall & Hall, 2003) :

cos α i + i sin α i sin θ i ie -iφi • sin α i cos θ i ie -iφi • sin α i cos θ i cos α i -i sin α i sin θ i

An operation of relation r on e would act each block matrix M i in the subspace of (x i , y i ). This completes the discussion of group embedding. We design the model loss function as follows: where σ is the Sigmoid function, γ is the margin used to prevent over-fitting, d r is the similarity measure, we use the conventional L 2 -norm. e 1i and e 2i are negative samples while p (e 1i , r, e 2i ) is the adversarial sampling mechanism with temperature α we adopt self-adversarial negative sampling setting from (Sun et al., 2019) . f r is a L 2 -norm score function. We term the resulting model as SU2E. For other implementation details, we would mention in the next section.

EQUATION

5. EXPERIMENTS:



5.1. EXPERIMENTAL SETUP:



Datasets::

The most popular public knowledge graph datasets include FB15K (Bollacker et al., 2008) and WN18 (Miller, 1995) . FB15K-237 (Toutanova & Chen, 2015) and WN18RR (Dettmers et al., 2018) datasets were derived from these two, in which the inverse relations were removed. FB15K dataset is a huge knowledge base with general facts containing 1.2 billion instances of more than 80 million entities. For benchmarking, usually, a frequency filter was applied to obtain occurrence larger than 100 resulting in 592,213 instances with 14,951 entities and 1,345 relation types.

WN18 was extracted from WordNet (Miller, 1995) dictionary and thesaurus, the entities are word senses and the relations are lexical relations between them. It has 151,442 instances with 40,943 entities and 18 relation types.

Evaluation Protocols: We use three categories of protocols for evaluations, namely, cut-off Hit ratio (H@N), Mean Rank(MR) and Mean Reciprocal Rank (MRR). H@N measures the ratio of correct entities predictions at a top n prediction result cut-off. Following the baselines used in recent literatures, we chose n = 1, 3, 10. MR evaluates the average rank among all the correct entities. MRR is the average rank inverse rank of the correct entities.

Implementation Details::

We implemented our model using pytorch5 framework and experimented on a server with an Nvidia Titan-1080 GPU. The Adam (Kingma & Ba, 2014) optimizer was used with the default β 1 and β 2 settings. A learning rate scheduler observing validation loss decrease was used to reduce learning rate by half after patience of 3000. Batch-size was set at 1024. We did a grid search on the following hyper-parameters: embedding dimension d ∈ {100, 200, 250}; learning rate η ∈ {1e -4, 3e -4, 5e -5}; number of negative samples during training n neg ∈ {128, 256}; adversarial negative sampling temperature α ∈ {0.5, 1.0}; loss function margin γ ∈ {6, 9, 12, 24, 36, 48}.

5.2. RESULTS AND MODEL ANALYSIS:

Empirical results from FB15k and WN18 are reported in Table 2 and 3 . We compared the embedding results of different groups, including T , U (1), GL(1, R), GL(1, C), D 4 , and SU (2), which are categorized by two major properties: the commutativity and the continuity. As discussed in Sec. 3.3, these groups have been implicitly applied in existing state-of-the-art models.

For SU (2), we report the result of our own experiments. Results of the other models are taken from their original literature: TransE using group T was proposed in Bordes et al. (2013) ; RotatE using group U (1) was proposed in Sun et al. (2019) while TorusE with the same group was proposed in Ebisu & Ichise (2018) ; group GL(1, V) was implemented in DisMult (Yang et al., 2014) with V = R and in ComplEx (Trouillon et al., 2016) In the WN18 dataset, the SU2E outperformed all the baselines on all metrics shown in Table 3 . The recent model RotatE and DihEdral achieved comparable results. The WN18RR dataset removes the inversion relations from WN18, left only 11 relations and most of them are symmetry patterns. We can see from Table 5 , the DihEdral model and SU2E model performed well on this dataset due to their nonabelian nature. Besides, as DihEdral uses a discrete parametrization in relation embedding, it may benefit in special cases where the number of relations is extremely small (11 in this task).

Drawn from the experiments, two factors significantly impact the embedding model performance: the embedding dimension, and group attributes (including commutativity and continuity). Our current study provides the first systematic analysis of the second factor. As theoretically analyzed in Section 3.2, and empirically shown above, continuous nonabelian groups are more reasonable choices for general tasks. It is important to note that the SU2E proposed above plays as an exampling model for our group embedding framework, and it uses the simplest continuous non-abelian group. Much more efforts could be devoted in this direction in the future.

6. CONCLUSION AND FUTURE WORK:

We proved for the first time the emergence of a group definition in the KG representation learning. This proof suggests that relational embeddings should respect the group structure. A novel theoretic framework based on group theory was therefore proposed, termed as the group embedding of relational KGs. Embedding models designed based on our proposed framework would automatically accommodate all possible hyper-relations, which are building-blocks of the link prediction task.

From the group-theoretic perspective, we categorize different embedding groups regarding commutativity and the continuity and empirically compared their performance. We also realize that many recent models correspond to embeddings using different groups. Generally speaking, a continuous non-abelian group embedding should be powerful for a generic KG completion task. We demonstrate this idea by examining a simple exampling model: SU2E. With SU (2) as the embedding group, it showed promising performance in challenging tasks where hyper-relations become crucial.

In the proposed framework, beside embedding relations as group elements, entity embeddings live in different representation space of the corresponding group. And therefore an investigation of group representation theory in entity embedding is highly demanded. We leave this in future works. On the other hand, although empirical evaluations focus on linear models, it is important to note that the proof of the group structure only relies on the KG task itself. This means our conclusion also works for more general models, including neural-network-based ones. Beyond KG embeddings, the same analysis could be applied to other representation learning where intrinsic relational structures are prominent. An implementation of group structures in more general cases would be very interesting.

A PROOF OF HYPER-ASSOCIATIVITY IN KNOWLEDGE GRAPH RELATIONS:

The associativity is actually rooted in our definition of r 1 • r 2 in equation 6 through the subsequent operating sequence in the entity space:

EQUATION

from which, we can derive directly that:

EQUATION

which then leads to the association equation below:

EQUATION

This completes the proof of associativity in knowledge graphs.

B AN EXPLICIT EXAMPLE OF HYPER-ASSOCIATIVITY:

While the other four properties derived in the main part is easy to comprehend, the associativity may not be intuitive. To help readers understand the practical meaning of associativity in real life cases, here we provide a simple example of the relational hyper-associativity:

EQUATION

Meanwhile, the following composition relations are also meaningful:

EQUATION

In this example, one could easily see that:

EQUATION

This completes a simple demonstration of the hyper-associativity.

C EXAMPLES OF NON-COMMUTATIVE RELATIONS:

We provide a simple illustrative examples for non-commutative compositions. We consider the following real world kinship:

EQUATION

Clearly, the composition r 1 • r 2 and r 2 • r 1 correspond to isGrandmotherOf and isGrandfatherOf relations respectively, which are different. This is a simple example of non-commutative cases.

D DETAILED DISCUSSION OF EXAMPLING GROUP EMBEDDINGS:

In this appendix, we give a thorough discussion on examples listed in the Table 1 . We would explain in details some minor differences between models obtained directly from group embedding theory here, and existing models which may not concern/obey group structures in precedent works.

D.1 GROUP: T:

Use multiple (n) copies of T , the translation group, for the relation embedding. This is a noncompact abelian group. The simplest rep-space would be the real field R, which should also appear n times as R n . The group embedding then produces the following embedding vectors:

EQUATION

both of which are n-dim. Here both x i and δ i are real numbers. In a triplet, the relation v r acts as an addition vector added to the head entity e 1 . If one further chooses L p -norm as the similarity measure:

EQUATION

this actually corresponds to the well-known TransE model (Bordes et al., 2013) . There was a regularization in the original TransE mode that changes the entity rep-space, which however has been removed in many later works by properly bounding the negative scores.

D.2 GROUP: U (1)

Use n-copies of U (1), the 1-dim unitary transformation group, for the relational embedding. This is a compact abelian group. The simplest rep-space would be the real field C, which should also appear n times as C n . The group embedding then produces the following embedding vectors:

EQUATION

where x i is a complex number containing a both real and imaginary part, while φ i is a phase variable take values from 0 to 2π. Therefore the entity-embedding dimension is 2n, while the relation dimension is n. In a triplet, the relation v r acts as a phase shift on the head entity e 1 . In a matrix form, one could define R r as the diagonal matrix with the i-th diagonal element being e iφi . If one further chooses L p -norm as the similarity measure:

EQUATION

where • means a Hadamard product. This precisely leads to the RotatE model (Sun et al., 2019) .

On the other hand, one could also use the n-torus T n as the rep-space:

EQUATION

where θ i represents a coordinate on the torus. Still using the L p -norm similarity measure:

R r • v e1 -v e1 p = e i r • e i e1 -e i e2 p ,

which leads to the TorusE model (Ebisu & Ichise, 2018) In the original implementation of TorusE, there is an additional projection π from R n to T n .

D.3 GROUP: SU (2):

The 2D complex special unitary group SU (2) is one of the simplest continuous nonabelian group, which is also the one we use in our instantiation. Use n-copies of SU (2), the 2-dim special unitary group, for the relational embedding. This is a compact nonabelian group. The natural choice of entity rep-space would be [C 2 ] ⊗n , which consists of n-copies of C 2 . Each C 2 subspace transforms as the standard rep-space of SU (2). All relations thus act as 2n × 2n block diagonal matrix, with each block being a 2×2 matrix carrying the standard representation of SU (2). our group embedding is then fixed as:

e =⇒ v e = x 1 , y 1 , x 2 , y 2 , • • • , x n , y n , ∀e ∈ E;

EQUATION

where x i and y i are complex numbers, and α i and ni = (θ i , φ i ) represent angles. In a triplet, the relation v r acts as a block diagonal matrix R r , with each 2 × 2 block M i parametrized as: cos α i + i sin α i sin θ i ie -iφi • sin α i cos θ i ie -iφi • sin α i cos θ i cos α i -i sin α i sin θ i

An operation of relation r on e would act each block matrix M i in the subspace of (x i , y i ). The complete model form after a L p -norm is implemented would be:

EQUATION

The action in the whole R 3n space looks like:

                   M 1 0 . . . 0 0 M 2 . . . 0 . . . . . . . . . . . . 0 0 . . . M n                                      

x 1 y 1 z 1 x 2 y 2 z 2 . . . 38) 

EQUATION

:

Given a graph, not all inversions correspond to meaningful relations, but an embedding model should be able to capture this possibility in general.

Given a graph, not all compositions correspond to meaningful relations, but an embedding model should be able to capture this possibility in general.

See Appendix B for a more detailed explanation and practical examples.

https://en.wikipedia.org/wiki/3D_rotation_group

https://www.pytorch.org

See Appendix.E for a detailed explanation.

Figures and Tables:

1i , r, e 2i ) log σ (d r (e 1i , e 2i ) -γ) (13) p e 1j , r, e 2j | {(e 1i , r i , e 2i )} = exp αf r e 1j , e 2j i exp αf r (e 1i , e 2i ) (14)

Examples of the group embedding.

Table content: <table><tr><td>Group</td><td colspan="4">Space Commutativity d(•) Studied</td><td>Related work</td></tr><tr><td>T</td><td>R n</td><td>abelian</td><td>L p</td><td/><td>TransE (Bordes et al., 2013)</td></tr><tr><td>U (1)</td><td>C n</td><td>abelian</td><td>L p</td><td/><td>RotatE (Sun et al., 2019)</td></tr><tr><td>U (1)</td><td>T n</td><td>abelian</td><td>L p</td><td/><td>TorusE (Ebisu &amp; Ichise, 2018)</td></tr><tr><td>SO(3)</td><td>R 3n</td><td>nonabelian</td><td>L p</td><td>-</td><td>-</td></tr><tr><td>SU (2)</td><td>C 2n</td><td>nonabelian</td><td>L p</td><td>-</td><td>-</td></tr><tr><td>GL(1, R)</td><td>R n</td><td>abelian</td><td>cos</td><td/><td>DisMult (Yang et al., 2014)</td></tr><tr><td>GL(1, C)</td><td>C n</td><td>abelian</td><td>cos</td><td/><td>ComplEx (Trouillon et al., 2016)</td></tr><tr><td>GL(n, R)</td><td>R n</td><td>nonabelian</td><td>cos</td><td>-</td><td>RESCAL (Nickel et al., 2011)</td></tr><tr><td>Aff (R n )</td><td>R n</td><td>nonabelian</td><td>L p</td><td>-</td><td>TransR (Lin et al., 2015)</td></tr><tr><td>D 4</td><td>R n</td><td>nonabelian</td><td>L p</td><td/><td>DihEdral (Xu &amp; Li, 2019)</td></tr></table>

with V = C; and DihEdral with group D 4 was proposed inXu & Li (2019). Link prediction results on WN18 dataset Results on datasets FB15K-237 and WN18RR are demonstrated in Table4and 5 respectively. We remove TorusE from the tables due to the absence of results in the original work, and use results inNguyen et al. (2017) for TransE.In the FB15k dataset, the main hyper-relation is anti-/symmetry and inversion. The dataset has a vast amount of unique entities. Shown in Table2, the RotatE model achieved good performance in this dataset. We should also point out that RotatE model result is achieved on large embedding dimension setting namely 1000 (effective 2000) while we use a setting of only 250 (effective 1000) across all the tasks. SU2E achieved comparable result across the metrics. On the other hand, in FB15k-237 dataset since inversion relations are removed, the dominant portion of hyper-relations becomes the composition. We can see RotatE fail short on non-abelian hyper-relations in this task. Shown in 4, the continuous non-abelian group method SU2E outperformed most of the metrics. The DihEdral model suffers from the problems we mentioned in Section 3.3.

Table content: <table><tr><td>Group</td><td colspan="2">Commutativity Continuity</td><td colspan="3">MR MRR H@1 H@3 H@10 Example</td></tr><tr><td>T</td><td>abelian</td><td>continuous</td><td>-</td><td>0.463 0.297 0.578 0.749</td><td>TransE</td></tr><tr><td>U(1)</td><td>abelian</td><td>continuous</td><td>40</td><td>0.797 0.746 0.830 0.884</td><td>RotatE</td></tr><tr><td>U(1)</td><td>abelian</td><td>continuous</td><td>-</td><td>0.733 0.674 0.771 0.832</td><td>TorusE</td></tr><tr><td>GL(1, R)</td><td>abelian</td><td>continuous</td><td>-</td><td>0.654 0.546 0.733 0.824</td><td>DistMult</td></tr><tr><td>GL(1, C)</td><td>abelian</td><td>continuous</td><td>-</td><td colspan="2">0.692 0.599 0.759 0.840 ComplEx</td></tr><tr><td>D 4</td><td>non-abelian</td><td>discrete</td><td>-</td><td colspan="2">0.728 0.648 0.782 0.864 DihEdral</td></tr><tr><td>SU(2)</td><td>non-abelian</td><td>continuous</td><td>42</td><td>0.776 0.710 0.823 0.881</td><td>SU2E</td></tr><tr><td/><td colspan="4">Table 2: Link prediction results on FB15K dataset</td><td/></tr><tr><td>Group</td><td colspan="2">Commutativity Continuity</td><td colspan="3">MR MRR H@1 H@3 H@10 Example</td></tr><tr><td>T</td><td>abelian</td><td>continuous</td><td>-</td><td>0.495 0.113 0.888 0.943</td><td>TransE</td></tr><tr><td>U(1)</td><td>abelian</td><td colspan="3">continuous 309 0.949 0.944 0.952 0.959</td><td>RotatE</td></tr><tr><td>U(1)</td><td>abelian</td><td>continuous</td><td>-</td><td>0.947 0.943 0.950 0.954</td><td>TorusE</td></tr><tr><td>GL(1, R)</td><td>abelian</td><td>continuous</td><td>-</td><td>0.822 0.728 0.914 0.936</td><td>DistMult</td></tr><tr><td>GL(1, C)</td><td>abelian</td><td>continuous</td><td>-</td><td colspan="2">0.941 0.936 0.945 0.949 ComplEx</td></tr><tr><td>D 4</td><td>non-abelian</td><td>discrete</td><td>-</td><td colspan="2">0.946 0.942 0.949 0.954 DihEdral</td></tr><tr><td>SU(2)</td><td>non-abelian</td><td colspan="3">continuous 207 0.950 0.944 0.954 0.960</td><td>SU2E</td></tr></table>

Link prediction results on WN18RR dataset

Table content: <table/>

Peer review (iclr2020):
I would like to thank the authors for the detailed rebuttal. My concern is generalizing something that is not correctly describing the object we should model (KGs). For instance, *all properties mentioned in the paper, including closure, identity, inversion, and associativity, are desired properties of relation embedding spaces, rather than existing properties of specific knowledge graphs. * => should we not care about the actual relations of knowledge graphs? Should we not build a theory that closely matches the properties of the actual objects we are modeling? The argument seems to be: forget the actual knowledge graph, here is a generalization of existing KGE methods. Even the proof provided was unrelated to my question: I gave an example: can you list all relations in FB15K and prove that they fit the group axioms? If they don*t fit, what is the advantage of modeling the relations as a group? What is the representation error this causes? The authors misunderstood my comment about (Bloem-Reddy and Teh 2019). *Therefore the previous works mentioned by the reviewer above are irrelevant.* => this is a weird statement. Permutation invariance is relevant to all objects that are graphs. I recommend reading the long history relating graph models and exchangeability (Persi Diaconis has a good overview). I was just mentioning that I don*t see why KGs should have another associated permutation group besides permutation invariance. I would also recommend following the emerging literature in graph representation learning using group theory, of which KGs are but a special case. *The (entity) manifold, however, means that the relations no longer form a group. I see no easy fix.* => I clarified it, since I was talking about the entity embedding. I did not see a revised version of the manuscript. I will raise my score because the paper could be published as a niche paper. We generalize KGE but we acknowledge its shortcomings: And here is a way to measure the embedding error of modeling the relations as a group, when they are not actually a group. -------------- The paper is well written and an interesting read. I think it complements well the existing literature. Unfortunately, I think the paper overstate its claims. It is clear that permutation groups are the natural language of all graphs (Kondor and Trivedi, 2018) and (Bloem-Reddy and Teh, 2019). It is less clear that knowledge graphs also comply with another set of group axioms. Why would the set of relations be closed? Say, Owns cdot Spouse_of = ? . I cannot see why and how this is necessary. Must all the relations be closed? I understand why this is true for KGE but this is not true for KGs, which only shows that KGEs may not be the right method to represent KGs moving forward. I see no easy fix. The rest of the paper is straightforward, just applying the definitions of groups. I found the classification of different methods interesting, and should be made more clear in the experiments. The experimental results are interesting but their significance is unclear. Please add standard deviations to all experiments. We cannot have a sense of the significance of the results without knowing how many runs were executed, how they were executed (e.g., k-fold cross-validation, bootstrapping), and their standard deviation. I dispute that the paper proves that the definition of groups emerges purely from the nature of the knowledge graph embedding (KGE) task. I would actually say the opposite, it is clear to me that for most KGs, their relations do not fit the definition of a group. I am open to be (formally) proven wrong. E.g., can you list all relations in FB15K and show that they fit the group axioms? Fixing the paper: Maybe the paper could be rewritten, constrained to Euclidean spaces? Then prove (formally) that the group axioms are a sufficient(?) and necessary(?) condition for such embeddings? Minor issues: honestly could not make sense of the abstract: The sentence choices - *which suggests that a group-based embedding framework is essential for model design* - *Our theoretical analysis explores merely the intrinsic property of the embedding problem itself without introducing extra design* in the abstract are very strange. It means nothing to a reader at that point. What a model design? What is an extra design? A modeling assumption? A model prior? *Using the proposed framework, one could construct embedding models that naturally accommodate all possible local graph patterns, which are necessary for reproducing a complete graph from atomic knowledge triplets* => what is an *atomic knowledge triplet*? Why are they necessary to reproduce a complete graph? This is all very confusing. * contradicts to the entity regularization* => contradicts the entity regularization References: Kondor, R. and Trivedi, S., 2018. On the generalization of equivariance and convolution in neural networks to the action of compact groups. ICML Bloem-Reddy, B. and Teh, Y.W., 2019. Probabilistic symmetry and invariant neural networks. arXiv:1901.06082.