Rules capture high-level patterns in knowledge graphs and sometimes can provide virtual schemata for the data. Recent research has witnessed an increasing interest in learning rules automatically and applying the learned rules in knowledge graph inferences. While quite a number of rule learning systems have been developed, the formats of learned rules are still restricted, mostly resemble paths in the knowledge graphs. Such methods focus on the graph structure of the knowledge graph, assuming all the vertices and all the edges in the graph have an equal role (while only named or labelled diferently). In this paper, we propose a method HARL (Hub Augmented Rule Learning) for learning rules containing attributes by treating certain binary predicates as unary predicates. A major component of HARL is an algorithm for identifying attributes for a given knowledge graph. HARL has been implemented through a scalable rule learner RLvLR. Our experimental results also show that HARL is scalable and outperforms RLvLR in most cases on major benchmark datasets.
Knowledge graphs (KGs) have proven to be useful for building interlinks between information
sources by connecting entities of diverse types like people, universities, movies, animals, etc.
This is particularly useful for information synthesis over multimodal media data, such as the
fusion of medical documents consisting of X-ray images and medical reports (texts and tables).
In artificial intelligence, a KG is usually a set of triples like (, bornInCity, ),
meaning that Barty was born in the city of Brisbane. Tools are available for retrieving such
triples from various sources [
On the other hand, in the KGs, specific entities in specific predicates acts as attributes. For example, in FB15k, the entity USA in the second argument of the predicate /film/film/country(, ) acts as a class that distinguish all films ( ) that are produced in the USA and from those who are not. Such binary attribute reflects a reality of dominance of the USA film industry globally. We refer to such entity-predicates as hubs and model them through attribute facts. We propose a method to identify a set of hubs automatically. Consider an example from YAGO2 KG, we have P : isCitizenOf_E : Netherland() as an attribute or hub. We can learn a number of patterns that cannot be expressed without such attributes, for instance, the rule P : isCitizenOf_E : Netherlands() ∧ isCitizenOf(, ) → livesIn(, ) would have only a much lower confidence degree if without the attribute P : isCitizenOf_E : Netherlands() (three times less confidence degree than the rule including attribute). Thus, we will consider the more specific rules such as, P : isCitizenOf_E : Netherlands() ∧ isCitizenOf(, ) → livesIn(, ), instead of the more general rule, isCitizenOf(, ) → livesIn(, ).
In this paper, we propose a method HARL (Hub Augmented Rule Learning), for learning rules
containing attributes. The idea is to regard such a rule as a closed path rule so that existing
scalable rule learners can be employed. This is achieved by treating a binary predicate as a
unary predicate, for example, an atom /film/film/country(, ) can be considered as an
attribute /film/film/country_USA(). Thus, a major component of HARL is an algorithm for
identifying attributes for a given KG. HARL can keep the search space in a manageable size
while essential entities for learning rules are not missed. HARL has been implemented through
a scalable rule learner RLvLR [
A knowledge graph consists of a set of entities ℰ as its vertices and its edges are directed and labelled with a set of predicates . An entity is an object such as a place, a person, etc., and a fact (or link) is a triple (, , ′), which means that the entity is related to another entity ′ via the binary predicate . Following the convention in knowledge representation, we denote such a fact as (, ′).
The format of rules we aim to learn extends closed-path rules (or CP rules), which is a language
bias that is widely adopted in the rule learning literature for knowledge graphs; for instance,
CP rules are the underlying formalism of Path Ranking Algorithms [
An attribute closed-path rule (or an ACP rule or simply a rule) is of the form 1(0, 1) ∧ 2(1, 2) ∧ · · · ∧ (− 1, ) ∧ 1(1 ) ∧ · · · ∧ ( ) → (0, ). (1) Here each (0 ≤ ≤ ) is a variable and 0 ≤ ≤ for each 1 ≤ ≤ , each (, ) is called an atom, and and are called respectively, the subject and object argument for , and each () is an atom with being a unary predicate. Intuitively, the rule reads that if 1(0, 1), 2(1, 2), . . . , (− 1, ), 1(1 ), . . . , ( ) hold, then (0, ) holds too. The atom (0, ) is the head of and the set of atoms {1(0, 1), 2(1, 2), . . . , (− 1, ), 1(1 ), . . . .( )} is the body of . The rule obtained from by removing unary predicates in the body, that is, 1(0, 1) ∧ 2(1, 2) ∧ · · · ∧ (− 1, ) → (0, ) is usually referred to as a closed-path rule or CP rule as the sequence of predicates in the rule body forms a path from the subject argument to the object argument of the head predicate.
To assess the quality of mined rules, we recall measures that are used in some major
approaches to rule learning [
The degrees of standard confidence (SC) and head coverage (HC) are defined as two forms of normalisation for (): () =
() #(, ′) : ()(, ′) () =
() #(, ′) : (, ′) So, () is the normalisation of () through the number of entity pairs that satisfy the body, while () is the normalisation of () through the number of entity pairs that satisfy the head.
In this section, we present our approach to learn rules with attributes through a simple and efective method. We first describe how to automatically identify facts in the KG that express entity attributes , which we refer to as attribute facts, and then explain how to transform such attribute facts to a form that can be easily processed by existing rule learning methods.
As argued in [
Existing rule learning approaches often do not distinguish entity attributes from entity relations as they can only learn the class of CP rules like
hasFriend(, ) ∧ gender(, ) → gender(, ).
However, in many cases it makes more sense to consider ‘gender’ as an attribute when rules of the following more general form are learned.
hasParent(, ) ∧ gender(, Male) → hasFather(, ).
To identify attribute facts (, ′), we need to identify ′ that can be used for attribute values, such as Male, and that is suitable for representing attributes, such as gender. That is, we need to identify the attribute values ′ and attribute predicates .
For attribute values, we observe that they are often linked to a huge number of entities and thus form kind of “hubs” in the network. Based on the above discussion, such hubs can be identified by their connection densities.
We define the density of a hub, (, ), as the (in and out) degrees of an entity w.r.t. a predicate as follows.
(, ) =
#′ : (′, ) #(′, ′′) : (′, ′′) (, ) =
#′ : (, ′) #(′, ′′) : (′, ′′) (2) In the definition of density, #′ : (, ′) or (′, ) is the total number of occurrences of (as a subject or object) in a fact of the KG, and it is normalized by the total number of facts about in the KG.
Yet a hub with high density is not necessarily suitable for an attribute value. Consider an extreme case where all the other entities ′ are connected with through a predicate , then is not an attribute value that can distinguish ′ from other entities. From information theory, such an attribute does not provide any information gain as it does not express any distinguishing feature of associated entities. Thus, we need to select the hubs that both have high density and provide distinguishing features. We compute the entropy of hubs as follows. (, ) = − ( * () + (1 − ) * (1 − )), where ∈ {, }, = (, ) (3) Next, we want to identify those predicates that are suitable for attributes. This is based on the observation that such a predicate often associates an entity with its attribute values, and the number of possible values (like Male) is often far smaller than the number of entities that can be associated with the attribute (like Joe Biden). So we define the imbalance degree (imb) of a predicate as follows.
() =
# : (, ′) (#′ : (, ′)) * |ℰ | () =
# : (′, ) (#′ : (′, )) * |ℰ | (4)
Intuitively, the degree () being large means that has more potential subjects than objects, which suggests the objects of could potentially be attribute values (whereas the subjects are more likely to be entities). In other words, the vertices with being an in-coming edge are more likely to be attribute values than those with being an out-going edge.
Finally, we combine the two measures to determine the likeliness of a fact with a hub and a predicate being an attribute fact.
(, ) = (, ) * (), where ∈ {, }. (5) The larger (, ) (or (, )) is the more likely a fact (, ′) (resp., (′, )) is an attribute fact, with ′ being an entity and representing its attribute value.
Unlike existing embedding methods that embed attributes separately from the other relations [
In general, attributes can be seen as unary predicates, whereas other relations are binary ones. For an attribute fact gender(Joe Biden, Male), it can be seen as a unary fact gender_Male(Joe Biden). Yet, such unary fact cannot be directly processed by existing rule learners as they only accept binary facts (i.e., triples) as inputs. Hence, we represent the unary fact gender_Male(Joe Biden) as a fact that is essentially a self-loop in the graph, i.e., gender_Male(Joe Biden, Joe Biden).
Formally, each attribute fact in the original KG of the form (, ′) (or (′, )) with ′ being the attribute value can be transformed into a fact : _ : ′(, ) (resp., : ′_ : (, )), where : _ : ′ (resp., : ′_ : ) is a new predicate. In Figure 2, we illustrate how attribute facts are transformed into self-loop in the KG.
The intuition of such a transformation is to represent attributes as self-loops in the KG, so that path-based rule learning method can be easily adapted to handle such a KG while the attribute atoms (as self-loops) can be conveniently identified in the learned rules. For example, a path hasParent(Joe Biden, Joseph R. Biden), gender(Joseph R. Biden, Male) is transformed into a path hasParent(Joe Biden, Joseph R. Biden), P : gender_E : Male(Joseph R. Biden, Joseph R. Biden), which together with many other similar paths may induce a rule
hasParent(, ) ∧ P : gender_E : Male(, ) → hasFather(, ).
The rule can be rewritten as
hasParent(, ) ∧ P : gender_E : Male() → hasFather(, ).
In Algorithm 1, we explain the complete process of identifying attribute facts, expanding the KG with transformed facts, and learning rules with attributes. Intuitively, we first select fact patterns (, · ) or (· , ) that can be considered attribute facts. We represent such a pattern as a triple (, , ) with ∈ {, }, which should not be confused with a triple in the KG. We select such triples where the total number of facts based on such patterns that can be added to the KG is bounded by a expansion degree . In what follows, we call such a triple a hub.
In line 1, we compute the frequency of all potential hubs. For each candidate hub (, , ), its frequency is the unnormalized density which is the numerator of Equation (2). To compute the frequencies, we just need to parse all facts in the KG once. We select top candidate hubs, where = , to form the .
In lines 2 to 3, we compute the measure for all potential hubs in as we explained in Equation (5). Then, we sort the list of candidate hubs by their values.
In lines 5 to 9, we consider the potential hubs one by one from the with the highest degree and create the corresponding new attribute predicate and facts. We stop this process when we hit the maximum expansion degree. The expansion degree is computed by the number of new facts divided by the number of facts in the original KG. The maximum expansion degree is given as input parameter, . In line 10 we feed the new set of facts to RLvLR and obtain a set of attribute rules. In line 11 we return a set of rules with attributes. Algorithm 1 Learn Rules with Attributes Input: a KG as a set of facts ℱ Parameter: a max expansion degree and an integer Output: a set of rules with attributes ℛ
There is a body of works for applying the learned rules to the known facts for inferring new
facts in KGs. Most of these works focus on how the rules can be used in a restricted iterative
way [12]. There is another stream of works that consider applying the uncertain rules once in
the knowledge graph community [
In the latter stream of works, each rule is augmented with a degree of confidence and the inference module takes to the account these degrees to infer a new fact (which is also augmented with a degree of confidence). To control the quality and number of new inferred facts, these systems put a maximum threshold on the number of new facts and/or put a minimum threshold on the confidence of new facts.
The problem with this method is they do not consider the demand of KG regarding each new fact; they merely focus on the process which results in the new facts. For example, consider the predicate isParentOf. For each human person, usually, we have at most two entities as parents. In the case that we want to infer new facts regarding this predicate for a specific person, Ann, we consider all rules that result in the following partially grounded fact (isParentOf(, )). On the other hand, we need to consider how many instantiations of this fact are needed. If we have already two entities as parents of Ann, we should reject any more facts even if those facts are inferred via quite confident rules. For another entity, Pit, that we have no facts that state the parent of him, we should accept the new inferred fact even if the confidences of the corresponding rules are not high. Thus, in the context-aware inference method, we try to consider the confidence of the new fact production process and the demand of the new fact in the KG.
In the context-aware inference method, we will infer the new facts by considering the already related existing facts in the KG. We could obtain an average number of facts regarding each predicate and entity in a specific predicate argument. Later, when we want to infer new facts, if there are enough facts already in the KG, inferring new facts are likely to be overpredicting. To avoid overpredicting, we consider just the predictions which securely fill the gap (between the current number of facts and the average number). We give higher priority to the facts with higher SC if there are alternatives. So we sort all predictions regarding their SCs, and for each one (1(1, 2)) we consider the gap between the average number of facts regarding specific entity and predicate and the concerning new fact. We obtain the Average Number of Facts (ANF) for each entity, predicate, and argument. Although this averaging method ignores the variations of the number of facts for a specific entity in the specific predicate, we propose it inferring a new fact in an extra cautious fashion. We do not claim the rejected new facts are not valid but based on this mechanism; we do not have strong support that the new fact is needed. 1 = 1 = #(, ′) : 1(, ′) # : ∃ 1(, ) #(, ′) : 1(, ′) #′ : ∃ 1(, ′) ((#′ : 1(1, ′)) < 1) ∧ ((# : 1(, 2)) < 1 )
We accept a new fact if the condition (8) is satisfied. This condition demands the new fact populate the KG whence both subject and object have less than average relations regarding the predicate.
By this extra cautious method, we can avoid overpopulating KG by predicting too many facts w. r. t. any specific pair of subject-predicate or object-predicate with the cost of excluding many facts that might be valid. For example, in the case of nationality, the number of entities with the same nationality varies from a hundred thousand to a billion based on real-world data. By considering the average, we might exclude many new valid facts for a more populated country. Hence, the excluded facts by this mechanism are not wrong, but if we have a high priority to infer fewer facts, we exclude them.
Based on the methods presented in previous sections, we have implemented Hub Augmented Rule Learning (HARL) and conducted three sets of experiments to evaluate the new system.
The first set of experiments aim to evaluate the efect of new hub predicates on rule learning. In the second set of experiments, we use the learned rules to infer new facts via the original inference module of RLvLR and the new context aware inference module. The results show the usefulness of hub-augmented rules to infer more quality facts. The third set of experiments aim to evaluate the improvements of RLvLR on link prediction task regarding using hubs as new predicates.
In Table 1, we show the statistics of three widely used Knowledge graphs. We randomly selected 50 target predicates for target predicates, and for YAGO2 core, we used all 32 predicates as target predicates. All results shown in the following experiments are average results for the corresponding target predicates. (6) (7) (8)
Rule learners can be evaluated by the number of distinct quality rules that they can learn.
AMIE+ [
We deployed a greedy search to find a set of rules with minimum redundancy w.r.t. fact inferences. Each rule is associated with a set of facts that can be inferred from the rule, denoted (). For a set of rules ℛ, (ℛ) = ⋃︀∈ℛ (). To obtain a concise set of rules, we start with an empty set ℛ and add rules into ℛ one by one from the set of all learned rules, following the descending order of the confidences of the rules (i.e., their SCs). Before adding a rule to ℛ, we first check if the facts inferred by can already be inferred by those in ℛ. We define the novelty degree for each rule as follows: noveltyDegree() = | ()| − | () ∩ (ℛ))| | (ℛ))| We add the rule to ℛ only if the novelty degree is higher than a threshold.
Table 2 shows the average numbers of rules (#) with the minimum quality SC≥ 0.1 and
HC≥ 0.01 as these values are used in RLvLR [
Compared to RLvLR, HARL showed significantly better performance in terms of both the rules with ordinary filtering and concise filtering. The superiority of HARL is more obvious in learning high quality rules, that is, among all the rules learned, HARL has a consistently higher number of high quality rules.
To estimate the predictive power of the corpus of learned rules, we calculated the number of
facts can be predicated by applying learned rules on the given facts via RLvLR inference module
and context-aware inference module. To aggregate the diferent rules with same target predicate
we use Noisy-OR similar to RLvLR [13] and AMIE+ [
The running of two systems have the following characteristics regarding time and other features 4. #Hub indicates the number of hubs that we consider before the number of new facts hits the max expansion degree ( in algorithm 1), which we assigned 0.1 for max expansion degree in these experiments. EXP is the actual expansion degree. Min is the value of the last hub that we consider.
We additionally evaluated the quality of rules through link prediction. We consider two queries,
(, ?) and (?, ′), for each fact, (, ′), in the testing data in each benchmark. For FB15k and
FB15KSE the separation of test and train data has been done, while for YAGO2core, there is
no previously prepared data, so we randomly separate 90% for train and 10% for the test. We
applied learnt rules on the training data to predict the missing entities, and the testing data
verified the correctness of such predictions. The predictions were measured using Mean Rank
(MR) in which the less value indicates better performance and Mean Reciprocal Rank (MRR) in
which the higher value indicates better performance. We also deployed Hits@1 and Hits@10.
These four quality measurements are commonly used in the Knowledge Graph Completion
literature [
HARL outperforms RLvLR in FB15K in all quality measures significantly while in other two benchmark it performs in par. Since the FB15kSE and YAGO2core are more dificult tasks regarding link prediction, it might be the case that proposing the hub could not help the link prediction.
To see how the hubs can efect the mined rules consider the following two rules from YAGO2core.
: 0.03, : 0.07, wasBornIn(, ) ∧ isLocatedIn(, ) → isCitizenOf(, ). : 0.61, : 0.01, P :< graduatedFrom > _E :< University_College_Dublin >() ∧wasBornIn(, ) ∧ isLocatedIn(, ) → isCitizenOf(, ).
The standard confidence of the second rule improved by about 20 times. Since we add a condition at the body of the rule, we make it more specified, so it fires less number of facts, but those shots are more accurate and improve the SC significantly. On the other hand, since the number of resulting facts in the second rule decreased, the head coverage also reduced, making the rule less general. While, the first rule is filtered due to its low SC, the specified version of it has higher SC and qualified to be in the output set of rules.
From FB15k KG, the following hubs are created as they have top . 1. P :< /people/person/gender > _E :< male >() 2. P :< /people/person/spouse_s./people/marriage/type_of_union > _E :< matrimony >()
From this example, we can observe the identified hubs in FB15k are intuitive and shows which binary attributes can separate the related entities into two sets. In the real case scenario, regarding the film industry, we have some dominant categories that can distinguish the entities, like the movies produced in the USA in contrast with those that were produced in any country other than the US. With our proposed modelling, we can reflect on this disparity between diferent values of one attribute.
Several rule learning systems, including AMIE+ [
The other related stream of works is attribute knowledge graph modelling. In general, our work is diferent from this line of works for at least two reasons: (1) they assume an input KG contain attributes while we create attributes out of the given KG; (2) the nature of attributes they consider is only numeric or categorical, while ours is a particular case of categorical ones.
The attribute KGs difer in terms of the nature of attributes. [ 11] and [
In [
In this paper, we proposed an approach to learn attributed rules over KGs. In contrast to existing attribute KG modelling approaches that assume attributes as input, we can mine the attributed rules from KG without an explicit set of attributes. We achieved this by proposing a binary attribute that can easily be embedded into the closed path rules and an identifying mechanism that automatically mines such attributes from KG. We enhance the original KG with new predicates (hubs) and corresponding facts. Then we feed the improved KG to a state-of-the-art rule learner, RLvLR, to learn attributed rules. We also proposed a novel inferring mechanism that considers the demands of a new inferred fact and the quality of the rules that infer it. Finally, we evaluated our system HARL on widely used benchmarks in rule learning and link prediction. Our experimental results demonstrate that HARL improved RLvLR in terms of both the number of mined quality rules, inferred facts, and accuracy in link prediction. [11] Z. Hu, Y. Dong, K. Wang, K. W. Chang, Y. Sun, GPT-GNN: Generative Pre-Training of
Graph Neural Networks, in: SIGKDD, ACM, 2020, pp. 1857–1867. [12] M. Svato, S. Schockaert, J. Davis, STRiKE : Rule-Driven Relational Learning Using Stratiefid k-Entailment, in: ECAI, 2020. [13] P. G. Omran, K. Wang, Z. Wang, An Embedding-based Approach to Rule Learning in
Knowledge Graphs, TKDE 33 (2021) 1348—-1359. [14] S. Ortona, V. V. Meduri, P. Papotti, Robust discovery of positive and negative rules in knowledge bases, in: International Conference on Data Engineering (ICDE), IEEE, 2018, pp. 1180–1191. [15] C. Meilicke, M. W. Chekol, D. Rufinelli, H. Stuckenschmidt, Anytime bottom-up rule learning for knowledge graph completion, in: IJCAI, 2019. [16] Y. Gu, Y. Guan, P. Missier, Towards Learning Instantiated Logical Rules from Knowledge Graphs, arXiv preprint (2020).