Knowledge graphs (KGs) has raised enormous attention among the general artificial intelligence community, which represent human knowledge as a triplet data structure (head entity, relation, tail entity) and can be applied in various downstream scenarios, such as recommendation system [1], question answering [2][3][4], information extraction [5,6], and etc. [7][8][9]. It is therefore important to design appropriate knowledge graph embeddings (KGEs) to capture knowledge in the whole dataset with uniform consistency. It is therefore important to design appropriate knowledge graph embeddings (KGEs) to capture knowledge in the whole dataset with uniform consistency. A knowledge graph represents a network of real-world entities-i.e., objects, events, situations, or concepts-and illustrates the relationship between them. It is usually represented as one collection of triplets, where each triplet represents the relation between two entities. Figure 1 provides an illustration of a triplet (A, B, C) where A and C represent two entities while B is the relation between them. Triplet instances could be (Louver, is_located_in, Paris) and (Da Vinci, painted, Mona Lisa). Concretely, KGs are collections of factual triplets, where each triplet represents the relation between two entities [10,11]. Mathematically, a KG consists of two sets: an entity Our work is partially motivated by NagE [27], but differs from it significantly in the following aspects. Firstly, we deliver a categorical language for KGE problems, which is much more general than NagE with fewer assumptions; secondly, we prove that a group structure would be inappropriate for a large class of problems, where the invertibility could not be enforced; thirdly, beyond a conventional KGE perspective, we adopt a machine reasoning perspective by considering the impact of chain-like logic rules, which is traditionally studied in symbolic AI, and therefore shed light on a potential pathway for neural-symbolic integration.
The rest part of the paper is organized in the following ways: Section 2 introduces the emergent algebra in KG, i.e., Knowledgebra, and proves that a semigroup structure is suited for a general KGE task; Section 3 proposes a model, SemE, for general KGE problems, as an instantiation of Knowledgebra, and demonstrates its performance advantage on benchmark datasets; in Section 4, we propose a regularization based method to integrate chain-like logic rules into embedding model training, and deliver a case study using a toy dataset where logic rules are easy to be specified; in the end, we provide a further investigation on the implementation of SemE and discuss potential directions in the future in Section 5, which could exploit more power of the developed algebraic language, Knowledgebra, in knowledge graph applications.
In this section, we would analyze a general KG, and demonstrate the emergence of an algebraic structure, which we term as Knowledgebra. The study of algebraic properties in Knowledgebra would produce constraints on KGE modeling.
As introduced at the beginning, KGs are composed of two sets: E and R, with entities in E linked by arrows representing relations in R. Although knowledge triplets {(e i , r, e j )} are the elementary atomic components of a KG, the complexity of the KG structure is not present on the triplet level. It is the set of logic rules that dictate the global consistency of a KG. Logic rules are the central topic of machine reasoning. In the machine reasoning field, relations are a special type of predicates, labeled as α, with arity 2. A logic rule can be expressed as the following:
where each α i is a predicate with entity variables as arguments. The above expression means that the head predicate α 0 would be iff all body predicates {α i } m i=1 hold. There is a special type of logic rules, chain-like rules, which has the following form:
where all predicates are of arity 2, and the head argument of the next predicate is always the tail argument of the previous one. The "cancellation" of intermediate terms {e i } m i=2 implies a compositional definition of the corresponding type of logic rules, where a composition of two predicates r a and r b is denoted as r a • r b . Furthermore, it has been proved in [27] that the composition defined above is associative.
The chain rule reflects more complex logic rules, i.e., hyper-relations in KG. This is the central topic of machine reasoning since the model should learn to make inference via integrating information from multiple triplets. For example, the reasoning of "James visited Paris" could be completed from two triplets (James, visited, Tour Eiffel) and (Tour Eiffel, is located in, Paris). Here the chain rule becomes: visited[James, Paris] ← (visited[James, Tour Eiffel], isLocatedIn[Tour Eiffel, Paris]). ( 4) Thus the chain-like reasoning from different levels of locations can not be ignored.
All elements discussed above have indicated the existence of an abstract mathematical structure: category. In mathematics, a category C consists of [28]
Identity: for every object x, there exists a morphism 1 x : x → x, called the identity morphism for x, such that every morphism f : a → x satisfies 1 x • f = f , and every morphism g :
It is straightforward to examine that all above definitions and axioms hold for a general knowledge graph, which therefore suggests that knowledge graphs naturally host a categorical language description. In this work, all our later discussions would then utilize concepts and properties of categories, which provide a formal basis.
With regards to logic rules, there are two pathways in the research of knowledge graphs: namely, logic construction and logic extraction.
Logic construction is widely used in machine reasoning via symbolic programming, where predicates are built as modules and logic rules are constructed explicitly. This is similar to the case of a theorem prover, where the propagation from sub-queries to a query is governed by pre-defined rules composed of logical operators, e.g., conjunctions and disjunctions. Logic construction is a completely deductive process. With explicit logic construction, one could derive both conclusions and reasoning paths at the same time. There are several advantages of applying logic construction: firstly, one could integrate common sense knowledge and domain expertise into the modeling of the reasoning process, which requires less or nearly zero data dependence; secondly, as rules are constructed explicitly, rigorousness could be guaranteed; thirdly, with the potential to construct a complete reasoning path, the interpretability of a conclusion derivation could be easily achieved. On the other side, the disadvantages of logic construction-based approaches are also significant:
1. The hand-crafting effort of integrating logic rules becomes impractical when the number of rules gets large; 2. The explicit construction could not accommodate any possible faults; 3. The construction could only take into account rules known a priori, and could not observe new ones (with logic operators, higher-order rules could be composed; However, here we refer to an inductive process to obtain new elementary rules).
These problems have been addressed in an alternative method: logic extraction. Different from logic construction, logic extraction-based approaches belong to the category of statistical learning. Opposite to the spirit of logic construction, logic extraction is an inductive process, which infers that logic rules are implied by a collection of data samples. One of the most important advantages of logic extraction is that the human effort remains low when the number of logic rules increases, while logic construction needs to construct each rule one by one manually. Thus, logic extraction could take advantage of huge datasets and is fault-tolerant based on its statistical nature. Besides, the induction process is insensitive to the number of logic rules and hence scales well with an increasing number of rules. It is obvious, though, that logic extraction could not integrate with human knowledge easily, and also suffers from the interpretability issue.
It is also noteworthy to emphasize an extra challenge for logic extraction on the implementation level: the set of logic rules hidden in a dataset requires a global consistency of knowledge representation. In the context of KGE, relation embeddings are not independent of each other and should accommodate all chain-like logic rules under compositions.
With the discussion above, we now consider the problem of KGE. KGE belongs to the class of logic extraction which explores a given dataset to infer logic rules. There are two embeddings of KGE, i.e., entity embeddings and relation embeddings. The chain-like logic rules, however, are entity-independent and only related to relation embeddings. As introduced above, relations correspond to morphisms in a category and are not independent of each other due to the existence of hidden logic rules under compositions.
The class hom(C), i.e., the set of relations, forms an algebraic structure, which, in general, is termed as knowledgebra. To specify an algebraic structure, the following five properties are usually discussed:
Variant algebraic structures could be differed by these five properties, and we list 10 well-studied structures in Table 1. To fully specify the structure of Knowledgebra, we now examine the five properties in the context of KGE. An analysis in [27] claimed that all the first four properties: totality, associativity, identity, and invertibility, should hold for KGE modeling, and the authors thus developed a group-based framework for relation embeddings. While we agree with most of the analysis in [27], we now provide an argument specifically on the invertibility property. Consider the following logic rule example consisting of two kinship relations:
Now if a group structure is used for relation embedding, then there always exist an inverse relation ra for r a , then, based on associativity, we would obtain:
requiring the relation isBrotherOf to be an identity map that always returns the head entity itself-which is incorrect. Therefore the existence of r a should be prohibited. Another less trivial example consists of the following four kinship relations:
which could be related by the following two rules abstractly:
Again, if a group embedding is implemented, based on invertibility, i.e., ra , and associativity, we would obtain:
which then demands directly:
an obviously incorrect conclusion. To simultaneously accommodate the two equations in Equation ( 8), the element r a should not be invertible. This suggests that invertibility is not a desired property for relation embedding in KG. As in [27], the existence of an identity element is proved based on invertibility, which we could also ignore for now (the existence of identity is not necessary but indeed compatible without any conflict). Therefore, in the end, only totality and associativity are natural properties of KGE tasks, which, according to Table 1, indicates that a semigroup-based relation embedding is desired.
In the above section, we delivered a formal analysis of KGE problems and proved that relations in a KG could generally be embedded in a semigroup structure. In this section, we implement this proposal by constructing an instantiation model, termed as SemE, and demonstrate the power of algebraic-based embedding on several benchmark tasks.
We firstly introduce the proposed model, including embedding space and distance function design.
We choose the simplest semigroup, which has a straightforward parametrization: real k × k matrices, as the embedding space for relations. It reduces to GL(k, R) with an extra condition: det = 0, which guarantees the invertibility. Here GL(k, R) represents the general linear group, which is the set of k-by-k invertible matrices over real numbers R, together with the operation of matrix multiplication. Entities are embedded as real vectors. Similar to the implementation in [27], to prevent the curse of dimensionality while allowing an embedding space large enough to accommodate knowledge graphs, we apply block-diagonal matrices as relation embeddings:
where each M i is a real k × k matrix and each v i is a vector in R k , i.e., entities are embedded in (R k ) ⊗n . We label the (nk) × (nk) embedding matrix for relation r as M r , and the (nk)-dim embedding vector for entity e as v e .
To apply an end-to-end gradient-based training, a scoring function to compare the similarity between two arbitrary entities is required. In this work, we exploited a distancebased scoring function that measures the plausibility of a factual triplet as the distance between the two entities, where a translation of the head entity is usually carried out by the relation. The two most common choices are Euclidean distance and cosine distance. The latter one, i.e., cosine similarity, focuses only on the relative angle between two high dimensional vectors while ignoring the radial component. Ref. [30] overviews more scoring function options. In the current work, a general k × k matrix transform a k-dim vector in 6 ways, including 5 affine-type transformations: translations, rotations, reflections, scaling maps, and shear maps, and projections achieved by non-invertible matrices, most of which, except rotations and reflections, cannot be differed by the cosine similarity, and we, therefore, choose Euclidean distance to measure entity similarity. For a fact triplet (e i , r, e j ), the performance of a SemE model would therefore be measured by the following similarity measure:
where • 2 calculates the L 2 -norm of a vector. The complete loss function is designed as follows: ∑ l e
where σ is the Sigmoid function, and γ is a hyper-parameter controlling the margin to prevent over-fitting, p loss is a hyper-parameter controlling the ratio of negative and positive losses. Equation ( 15) is the standard form that was first proposed in [12], and applied in nearly all KGE models, including [10][11][12]26,27,31,32], etc. Following an energy-based framework, the energy of a triplet is equal to the similarity measure of this triplet, which corresponds to Equation (14). To learn embeddings, a margin-based ranking criterion over the training set is proposed, which prefers ranking real triplets over corrupted triplets. Specifically, the set of corrupted triplets is constructed from negative sampling and is composed of training triplets with either the head or tail (but not both), replaced by a random entity. The complete loss favors lower values of the energy for training triplets than for corrupted triplets and thus leads to the two components in Equation (15). We apply a popularly implemented [10,27] negative sampling setup, termed as self-adversarial negative sampling [10], with e ik and e jk being the negative samples for head and tail entity, respectively, while p(e ik , r, e jk ) is the adversarial sampling weight with the inverse temperature α controlling the focus on poorly learned samples.
In the standard SemE, relations are embedded as n blocks of k × k matrices while the entities are mapped to (nk)-dim vectors. In practice, there are tasks where only simple relations are involved. For example, the WordNet-18 dataset includes only 18 distinct relations, connected by very simple logic rules. However, the large number of entities requires a relatively high dimensional vector space for embedding, which easily results in large redundancy in relation embedding in such tasks. To improve the efficiency of parametrization for tasks with simple relations, and accelerate learning convergence at the same time, we propose two simplified alternatives for relation embedding:
• shared blocks: instead of using n distinct k × k matrices, we use identical copies of one k × k matrix, i.e.,
The number of parameters of embedding for one relation then reduces from n × k × k to k × k, which is a super low dimensional embedding, termed as SemE-s.
shared blocks with shift: in the case where a single k × k matrix is insufficient while low-dimensional efficiency is still demanded, we could break the symmetry among n subspaces by introducing a block-dependent shift δ i . Precisely, the transformation in each subspace could be written as:
The number of parameters is then k × k + n × k. And we term the resulting model as SemE-δs (importantly, this shift corresponds to a translation in each subspace, which, together with the matrix multiplication, still hold a semigroup structure. The resulting operation is quite similar to a Euclidean group but with non-invertible elements).
We would implement these low-dim embedding methods later on tasks with simple relations.
Datasets: we evaluate the proposed approach on two popular public knowledge graph benchmarks: WN18RR [33] and FB15k-237 [34]. These two datasets were derived from WN18 [35] and FB15K [36] respectively. The FB15k dataset extracted all FreeBase entities that have over 100 mentions and are featured in the Wikilinks database while the WN18 dataset extracted from a linguistic knowledge graph ontology named the WordNet. After finding that the FB15k and the WN18 dataset suffered from test leakage issues due to the presence of equivalent inverse relations, the WN18RR and FB15k-237 were created as more challenging datasets, removing all equivalent and inverse relations. These two datasets are currently benchmarked across the KGE domain to fairly compare model performances specifically in recent relevant works [11,27,34]. In these two datasets, none of the triplets in the training set are directly linked to the validation and test sets.
Evaluation Metrics: similar to previous work, we use two ranking-based metrics for evaluation: (1) Cut-off Hit ratio (H@N, N ∈ {1, 3, 10}), which measures the proportion of correct entity predictions among the top N prediction result cut-off, and (2) Mean Reciprocal Rank (MRR), which represents the average of inverse ranks assigned to correct entities.
Implementation Details: we implement our models via the Pytorch framework and experimented on a server with an NVIDIA Tesla V100 GPU (32 GB). The Adam optimizer [37] is used with default settings of β 1 and β 2 . We use a learning rate annealing schedule that discounted the learning rate by a factor of 0.1 with a patience setting of 10. The batch size is fixed at 1000 (the code is available at https://github.com/yifeiwang15/Knowledgebra (accessed on 2 May 2022)).
For FB15k-237, we implement the standard SemE as stated in Section 3.1.1, with parameterization of k = 5 and n = 240. Other hyper-parameters are tuned as following: learning rate η ∈ {3e -4, 1e -3}; number of negative samples during training n neg ∈ {64, 128}; adversarial negative sampling temperature α ∈ {0.75, 0.85, 0.95, 1}; loss function margin γ ∈ {9, 12}; ratio between negative and positive losses p loss ∈ {5, 10}. The best model is under configuration of η = 1e -3, n neg = 64, α = 0.85, γ = 9, p loss = 5. As another benchmark dataset, WN18RR only includes simple relations that can be sufficiently captured by low-dimensional embeddings. Therefore we apply a low-dim alternative model, SemE-δs, as discussed in Section 3.1.3, where we take k = 10 and n = 100 in this case. Other hyper-parameters of grid search include: η ∈ {3e -4, 1e -3}; n neg ∈ {64, 128}; α ∈ {0.5, 0.7, 0.85, 1}; γ ∈ {6, 7, 7.5}; p loss ∈ {10, 20, 30}. The best performance appears in the configuration with η = 1e -3, n neg = 128, α = 0.7, γ = 6, p loss = 30. The experimental results of the best models are exhibited in Table 2. As shown above, in the WN18RR dataset, our SemE model outperformed the previous state-of-the-art knowledge graph model on the metrics of the average of inverse ranks assigned to correct entities, also known as the mean reciprocal rank, the cut-off hit ratio of top one and top three; on the FB15k-237 dataset our SemE model outperformed all the benchmark evaluation metrics compared to previous state-of-the-art model, our cut-off hit ratio at top three outperformed by a margin of 4%. Remarkably, in the task of WN18RR, our model SemE has already provided promising results only with a dimensionality setting of k = 10 and n = 100. In comparison, the baseline RotatE model has 81% more model parameters. A significantly small number of model parameters further demonstrates the advantage of the proposed approach.
We have discussed the advantages and shortages of the logic constructions versus logic extraction in Section 2.2. In this section, we will propose a way to integrate human knowledge into KGE. This is valuable since logic rules, e.g., chain-like rules, could provide rich information and hence efficient constraints on the embedding model, which has been ignored in nearly all preceding works. With a regularization-based method to integrate chain-like logic rules derived from human knowledge into embedding training, we provided a solution to bridge the gap between logic construction and extraction. The resulting method is therefore more data-efficient and interpretable.
One of the major challenges in KGE is to integrate human knowledge, either commonsense or domain knowledge, into the embedding model. As introduced in knowledge is expressed as logic rules, which in turn is represented by relation compositions. The task of integrating human knowledge is equivalent to enforcing the compositional dependence among embeddings of different relations. For example, the two relations r a = isWifeOf and r b = isHusbandOf are mutually dependent on each other as:
where E is an identity mapping. When a matrix embedding is implemented, the following equation should hold:
which results into an identity matrix. The above example inspires a way to integrate human knowledge, i.e., logic rules, into embeddings: to design an additional loss term that minimizes the matrix distance suggested by rules. For the instance above, we may add the following term into loss function:
where L 0 is the usual training loss defined in Equation (15), while the second term regularizes the embeddings of r a and r b to be mutually dependent. In general, for chain-like rules, which could be captured as compositions, we could apply the following regularized loss function:
where without loss of generality as argued in the inverse and compositional hyper-relation, logic rules are expressed as a compositional dependency of three relations, with one of which could be an identity to capture the case of the inverse. This provides an efficient approach to integrating human knowledge, i.e., logic rules, into KG embedding tasks.
We now demonstrate the above proposed regularized loss method on a toy dataset: Hinton's Kinship dataset. There are 12 relations in this toy KG: wife, husband, father, mother, son, daughter, sister, brother, uncle, aunt, niece, and nephew.
From common sense knowledge, we consider the following set of constraints for relation embedding shown in Table 3. We implemented the logic regularized loss method using a small shared block model, SemE-s, with 2 copies of 2 dimensional subspaces. We used the batch size of 5 for training and 12 for testing. For other hyper-parameters we took = 0.1, n neg = 4, p loss = 2. We set all regularization parameters λ i = 0.1, ∀i, and compared the baseline model with λ i = 0, ∀i. Experimental results on testing dataset are shown in Table 4. The performance advantage of the logic regularized model is significant, which demonstrates the power of the regularization brought by logic rules. This showcases an efficient way to integrate external knowledge.
SemE applies matrices to embed relations. A non-invertible matrix M has a determinant det(M) = 0, which, from a dimensional-perspective, suggests a projection associated with a dimension reduction. For the example in Equation ( 7), the relation r a = IsMotherOf should not be invertible for a family with multiple children, since all vectors corresponding to a child should be simultaneously mapped by the matrix M r a to the same vector, which represents their mother. In other words, the non-invertible elements in a semigroup are used to capture N-to-1 relations, which commonly exist in real-life datasets.
A derived question from the above discussion would be the representation of 1-to-N relations. Within the context of KGE using statistical learning-based representation, it is challenging to directly design a mathematically rigorous 1-to-N mapping operation O(•, •), as it always produces a deterministic result. However, this could be relieved by noting that the final performance of an embedding model is determined not directly by the mapping output but by the ranking of closeness between the output with each candidate entity. Therefore, instead of producing multiple results, the distributed learning framework requires the output to be as equidistant to all correct candidates as possible. This also explains the necessity of high-dimensional entity embedding: within a low-dimensional vector space, it is more challenging to find a point equidistant w.r.t multiple points.
With the proposal logic-regularized-loss method in Section 4, the proposed algebraic learning framework sheds new light on the area of neural-symbolic integration. More specifically, we proposed a method to integrate chain-like logic rules of relations into distributed representations. However, this only covers a small set of general logic, and it is, therefore, interesting to develop further methods to integrate other types of logic rules, including ones concerning entity attributes (also called arity-1 relations). Furthermore, the current work focuses merely on relation embeddings, which have an algebraic nature. The entity embedding, on the other hand, plays the role of "action space" of the relational algebra and therefore has a geometric nature. Given an algebraic structure, the choice of its "action space" is far from being fully determined. There is hence a rich set of candidates for entity embedding design, which is worth to investigate in the future.
The mutual dependence of relations in a knowledge graph suggests the existence of an algebraic structure, which is introduced in this work as Knowledgebra. By analyzing a general KG based on five distinct properties, we determined that the semigroup is the most reasonable algebraic structure for general relation embeddings, where only totality and associativity are required. Our theoretical analysis based on the work of NagE [27], and differed from it majorly by demonstrating that invertibility should be allowed to break. In Section 2.3, we provided proof based on contradictions with several examples among kinship relations. With the instantiation model, SemE proposed, we could discuss the invertibility issue from an alternative perspective.