Year: 2019

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.

heading: 1 INTRODUCTION
text: Knowledge graphs (KGs) are prominent structured knowledge bases for many downstream semantic tasks (Hao et al., 2017). A KG contains an entity set E = {ei}, which correspond to vertices in the graph, and a relation set R = {rk}, which forms edges. The entity and relation sets form a collection of factual triplets, each of which has the form (ei, rk, ej) where rk is the relation between the head entity ei and the tail entity ej . 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 Or[·] from its head entity e1 to its tail entity e2: r : e1 7→ Or[e1] =: e2. (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 Or[·] is simply a vector summation: Or[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 Or[·] 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).

heading: 2 RELATED WORKS
text: 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 D4 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 r1 and r2 would change if the two are switched). Nevertheless, DihEdral applies a discrete group D8 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.

heading: 3 GROUP THEORY IN RELATIONAL EMBEDDINGS
text: 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.

heading: 3.1 HYPER-RELATION PATTERNS: RELATION-OF-RELATIONS
text: 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 : e1 7→ e2 −→ r̄ : e2 7→ e1, ∀e1, e2 ∈ E . (2)
The inversion captures any relation path with a length equal to 1 (in the unit of relations). • Composition: given two relations r1 and r2, there may exist a third relation r3, such that:{
r1 : e1 7→ e2 r2 : e2 7→ e3 −→ r3 : e1 7→ e3, ∀e1, e2, e3 ∈ E . (3)
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 r3 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: (e1, r, e2) −→ (e2, r, e1), anti-symmetric: (e1, r, e2) −→ ¬(e2, r, e1). (4)
In fact, if for any choice of e1,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:
r̄ = r. (5)
This is a special case of the inversion hyper-relation; and similarly, the anti-symmetric case simply implies r̄ 6= 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.

heading: 3.2 EMERGENT GROUP THEORY
text: 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 r1 and r2: r1 · r2, as subsequently ”finding the tail” twice according to the two relations, i.e.
Or1·r2 [ · ] := Or1 [ Or2 [·] ] . (6)
With the above definition, equation 3 can be rewritten as: r3 = r1 · r2. 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 r1 · r2 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:
i = r · r̄, ∀r ∈ R. (7) This element should map any entity to itself, and thus we call it identity element.
1Given a graph, not all inversions correspond to meaningful relations, but an embedding model should be able to capture this possibility in general.
2Given a graph, not all compositions correspond to meaningful relations, but an embedding model should be able to capture this possibility in general.
4. Associativity: In a relational path with the length longer than three (containing three or more relations {r1, r2, r3, ...}), as long as the sequential order does not change, the following two compositions should produce the same result:
(r1 · r2) · r3 = r1 · (r2 · r3). (8) See Appendix A for the proof.
5. Commutativity/Nonconmmutativity: In general, commuting two relations in a composition, i.e. r1 · r2 ↔ r2 · r1, 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.3
The 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.

heading: 3.3 EMBEDDING MODELS USING DIFFERENT GROUPS
text: 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 D4 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 Lp-norms (Lp) and the cos-similarity (cos). We would notice many choices reproduce some precedent works.
We summarize the results of several chosen examples in Table 1, and put a thorough discussion in Appendix D. Note in the Table 1, some groups have not been studied, but there are still some existing models which use a quite similar embedding space. The major gap, between the existing models and their group embedding counterparts, is the constraint from group structures on the parametrization. which is discussed in details in Appendix D.
3See Appendix B for a more detailed explanation and practical examples.

heading: 4 GROUP EMBEDDING FOR KNOWLEDGE GRAPHS
text: 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.

heading: 4.1 A GENERAL GROUP EMBEDDING RECIPE
text: 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 ~ve. 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 ~vr would be qn. A group element can now be expressed as a block-diagonal matrix Rr, with each block Mi being a p× p matrix whose entries are determined by the vector ~vr.
4. Choose a similarity measure d[·], the score value of a triplet (e1, r, e2) is then: d [ Rr · ~ve1 , ~ve2 ] (9)
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: [C2]⊗n, which consists n-copies of C2. Each C2 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).
4https://en.wikipedia.org/wiki/3D_rotation_group
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):
eiα[n̂· ~J] = cosα1̂ + i sinαn̂ · ~J, (10)
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): (Jx,Jy,Jz), which, in the standard rep have the following form:
Jx = [ 0 1 1 0 ] , Jy = [ 0 -i i 0 ] , Jz = [ 1 0 0 -1 ] . (11)
Put all together, our group embedding is then fixed as: e =⇒ ~ve = ( x1, y1, x2, y2, · · · , xn, yn ) , ∀e ∈ E ;
r =⇒ ~vr = ( α1, n̂1, α2, n̂2, · · · , αn, n̂n ) , ∀r ∈ R; (12)
where xi and yi are complex numbers, and αi and n̂i = (θi, φi) represent angles. In a triplet, the relation ~vr acts as a block diagonal matrix Rr, with each 2 × 2 block Mi 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 Mi in the subspace of (xi, yi). This completes the discussion of group embedding. We design the model loss function as follows:
L = − log σ (γ − dr(e1, e2))− n∑ i=1 p (e′1i, r, e ′ 2i) log σ (dr (e ′ 1i, e ′ 2i)− γ) (13)
p ( e′1j, r, e ′ 2j| {(e1i, ri, e2i)} ) =
expαfr ( e′1j, e ′ 2j )∑ i expαfr (e ′ 1i, e ′ 2i)
(14)
where σ is the Sigmoid function, γ is the margin used to prevent over-fitting, dr is the similarity measure, we use the conventional L2-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). fr is a L2-norm score function. We term the resulting model as SU2E. For other implementation details, we would mention in the next section.

heading: 5 EXPERIMENTS

heading: 5.1 EXPERIMENTAL SETUP
text: 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 nneg ∈ {128, 256}; adversarial negative sampling temperature α ∈ {0.5, 1.0}; loss function margin γ ∈ {6, 9, 12, 24, 36, 48}.

heading: 5.2 RESULTS AND MODEL ANALYSIS
text: 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), D4, 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) with V = C; and DihEdral with group D4 was proposed in Xu & Li (2019).
Results on datasets FB15K-237 and WN18RR are demonstrated in Table 4 and 5 respectively. We remove TorusE from the tables due to the absence of results in the original work, and use results in Nguyen 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 Table 2, 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.
5https://www.pytorch.org
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.

heading: 6 CONCLUSION AND FUTURE WORK
text: 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.

heading: A PROOF OF HYPER-ASSOCIATIVITY IN KNOWLEDGE GRAPH RELATIONS
text: The associativity is actually rooted in our definition of r1 · r2 in equation 6 through the subsequent operating sequence in the entity space:
Or1·r2 [ · ] := Or1 [ Or2 [·] ] , (15)
from which, we can derive directly that: O(r1·r2)·r3 [ · ] = Or1·r2 [ Or3 [·] ] = Or1 [ Or2 [Or3 [·]]
] = Or1 [ Or2·r3 [·] ] = Or1·(r2·r3) [ · ] , (16)
which then leads to the association equation below:
(r1 · r2) · r3 = r1 · (r2 · r3). (17)
This completes the proof of associativity in knowledge graphs.

heading: B AN EXPLICIT EXAMPLE OF HYPER-ASSOCIATIVITY
text: 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:
r1 = isBrotherOf, r2 = isMotherOf, r3 = isFatherOf. (18)
Meanwhile, the following composition relations are also meaningful:
r1 · r2 = isUncleOf, r2 · r3 = isGrandmotherOf. (19)
In this example, one could easily see that:
(r1 · r2) · r3 = r1 · (r2 · r3) = isGranduncleOf. (20)
This completes a simple demonstration of the hyper-associativity.

heading: C EXAMPLES OF NON-COMMUTATIVE RELATIONS
text: We provide a simple illustrative examples for non-commutative compositions. We consider the following real world kinship:
r1 = isMotherOf, r2 = isFatherOf. (21)
Clearly, the composition r1 · r2 and r2 · r1 correspond to isGrandmotherOf and isGrandfatherOf relations respectively, which are different. This is a simple example of non-commutative cases.

heading: D DETAILED DISCUSSION OF EXAMPLING GROUP EMBEDDINGS
text: 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 Rn. The group embedding then produces the following embedding vectors:
e =⇒ ~ve = ( x1, x2, · · · , xn ) , ∀e ∈ E ;
r =⇒ ~vr = ( δ1, δ2, · · · , δn ) , ∀r ∈ R; (22)
both of which are n-dim. Here both xi and δi are real numbers. In a triplet, the relation ~vr acts as an addition vector added to the head entity e1. If one further chooses Lp-norm as the similarity measure:
‖(~r + ~e1)− ~e2‖p, (23)
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 Cn. The group embedding then produces the following embedding vectors:
e =⇒ ~ve = ( x1, x2, · · · , xn ) , ∀e ∈ E ;
r =⇒ ~vr = ( φ1, φ2, · · · , φn ) , ∀r ∈ R; (24)
where xi 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 ~vr acts as a phase shift on the head entity e1. In a matrix form, one could define Rr as the diagonal matrix with the i-th diagonal element being eiφi . If one further chooses Lp-norm as the similarity measure:
‖Rr · ~ve1 − ~ve1‖p = ‖ [ ei~r ] ◦ ~e1 − ~e2‖p, (25)
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 Tn as the rep-space:
e =⇒ ~ve = ( θ1, θ2, · · · , θn ) , ∀e ∈ E ;
r =⇒ ~vr = ( φ1, φ2, · · · , φn ) , ∀r ∈ R; (26)
where θi represents a coordinate on the torus. Still using the Lp-norm similarity measure:
‖Rr · ~ve1 − ~ve1‖p = ‖ei~r ◦ ei~e1 − ei~e2‖p, (27)
which leads to the TorusE model (Ebisu & Ichise, 2018) In the original implementation of TorusE, there is an additional projection π from Rn to Tn.
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 [C2]⊗n, which consists of n-copies of C2. Each C2 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 =⇒ ~ve = ( x1, y1, x2, y2, · · · , xn, yn ) , ∀e ∈ E ;
r =⇒ ~vr = ( α1, n̂1, α2, n̂2, · · · , αn, n̂n ) , ∀r ∈ R; (28)
where xi and yi are complex numbers, and αi and n̂i = (θi, φi) represent angles. In a triplet, the relation ~vr acts as a block diagonal matrix Rr, with each 2× 2 block Mi 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 Mi in the subspace of (xi, yi). The complete model form after a Lp-norm is implemented would be:
‖Rr · ~ve1 − ~ve2‖p (29)
D.4 GROUP: SO(3)
The 3D rotation group SO(3) is also one of the simplest continuous nonabelian group and has not been studied yet. A proper rep-space for entity embedding would be [R3]⊗n, which consists of ncopies of R3. Each R3 subspace transforms as the standard rep-space of SO(3). All relations thus act as 3n × 3n block diagonal matrix, with each block being a 3 × 3 matrix carrying the standard representation of SO(3).
Next, we choose a proper parametrization of SO(3). Instead of the more general angular momentum parametrization, due to our choice of using the standard representation, we could parameterize the SO(3) elements using Euler angles (φ, θ, ψ), which is easier for implementation.
Put all together, our group embedding is then fixed as: e =⇒ ~ve = ( x1, y1, z1, x2, y2, z2, · · · , xn, yn, zn ) , ∀e ∈ E ;
r =⇒ ~vr = ( φ1, θ1, ψ1, φ2, θ2, ψ2, · · · , φn, θn, ψn ) , ∀r ∈ R; (30)
both of which are 3n-dim. In a triplet, the relation vector ~vr acts as a block diagonal matrix Rr, with each 3× 3 block Mi parametrized as following6:[
cosψi cosφi − cos θi sinψi sinφi cosψi sinφi + cos θi cosψi cosφi sinψi sin θi − sinψi cosφi − cos θi sinψi cosφi − sinψi sinφi + cos θi cosψi cosφi cosψi sin θi
cosψi sin θi − cosψi cos θi cos θi ] An operation of relation r on e would act each block matrix Mi in the subspace of (xi, yi, zi). The complete model form after a Lp-norm is implemented would be:
‖Rr · ~ve1 − ~ve2‖p (31)
D.5 GROUP: GL(m,V)
This is a class of groups (m-dim general linear groups defined on field-V). We separate the discussion into two parts according the commutativity property of the group:
1. Group GL(1,V): Use n-copies of GL(1,V), the 1-dim general linear group defined on field-V, for the relational embedding. This is a noncompact abelian group. Suppose cossimilarity is used, and, most naturally, the entity rep-choice is chosen as Vn. One has at least two simple choices for the field-V: either real or complex. For the real field R, embeddings are:
e =⇒ ~ve = ( x1, x2, · · · , xn ) , ∀e ∈ E ;
r =⇒ ~vr = ( s1, s2, · · · , sn ) , ∀r ∈ R; (32)
with both xi and si being real numbers. In a triplet, the relation vector ~vr acts as a diagonal matrix Rr, with the i-th element being si. If one uses a cos-similarity which can be captured by the inner product, the eventual form would be:
~vTe2 · [ Rr · ~ve1 ] (33)
which leads to the DisMult model. And similarly a complex field C leads to a model structure similar to ComplEx (Trouillon et al., 2016). There is a minor difference in ComplEx: authors actually use the cos-similarity in a projected subspace (the real-subspace of Cn):
Re ( ~vTe2 · [ Rr · ~ve1 ]) (34)
2. GroupGL(n,V): UseGL(n,V), the n-dim general linear group defined on field-V, while keeping both the similarity measure (cos-similarity) and entity rep-space (Vn) choices unchanged. This is a noncompact nonabelian group. The choice of V = R would leads to a model similar to RESCAL (Nickel et al., 2011). However, different from the correspondences above, the original RESCAL model does not have a built-in group structure: it uses arbitrary n× n real matrices, some of which may not be invertible, and hence are not group elements in GL(n,R). It is, therefore, worth to add the extra invertible constraint in RESCAL, which requests matrices constructed through group parameterization rather than assigned arbitrary matrix elements.
6See Appendix.E for a detailed explanation.
D.6 GROUP: AFF(V)
Use Aff(V), the affine group defined on the field-V, for the relational embedding. This is a noncompact nonabelian group. One could choose V = Rn since the entity rep-space should always share the same one. If one further takes Lp-norm as the similarity measure, the embedding model would be quite similar to that in TransR (Lin et al., 2015) if relation and entity embeddings share the same dimension. However, similar to the RESCAL case, one important distinction is the original model does not explicit constraint the relational embedding on a group manifold. An extra invertible requirement would then produce exactly a group embedding model as proposed here.

heading: E EXPLANATION OF EULER ANGLES AND RELATION OPERATIONS
text: In this appendix section, we provide a pictorial explanation for Euler angles used in the exampling model of SO(3).
The idea is that all 3D rotations that preserve orientation could be decomposed into the following 3 subsequent rotations:
D = ( cosφ sinφ 0 − sinφ cosφ 0
0 0 1
) , (35)
C = ( 1 0 0 0 cos θ sin θ 0 − sin θ cos θ ) , (36)
B = ( cosψ sinψ 0 − sinψ cosψ 0
0 0 1
) . (37)
The composed operation M = BCD could then be written as:
[ cosψ cosφ− cos θ sinψ sinφ cosψ sinφ+ cos θ cosψ cosφ sinψ sin θ − sinψ cosφ− cos θ sinψ cosφ − sinψ sinφ+ cos θ cosψ cosφ cosψ sin θ
cosψ sin θ − cosψ cos θ cos θ
] ,
which is the matrix used in the main text. The meaning of the above three rotations can be easily visualized as following:
The action in the whole R3n space looks like: M1 0 . . . 0 0 M2 . . . 0 ... ... . . . ...
0 0 . . . Mn
  x1 y1 z1 x2 y2 z2 ...
xn yn zn

(38)

Review summaries:
This paper 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. it seems to be a novel result. Based on this result, one could construct embedding models that naturally accommodate all possible local graph patterns, and the paper also shows a few simulations.