Learning SHACL shapes from knowledge graphs

2.1.Closed-path rules

KG rule learning systems employ various rule languages to express rules. RLvLR [27] and ScaleKB [9] use so-called closed path (CP) rules. Each consists of a head at the front of the implication arrow and a body at the tail. We say the rule is about the predicate of the head. The rule forms a closed path, or single unbroken loop of links between the variables. It has the following general form.

We interpret these kinds of rules with universal quantification of all variables at the outside, and so we can infer a fact that instantiates the head of the rule by finding an instantiation of the body of the rule in the KG. For example, from the rule citizenOf(x,y)←livesIn(x,z)∧locatedIn(z,y) and the facts in the KG: livesIn(Mary,Canberra) and locatedIn(Canberra,Australia), we can infer and assert the new fact: citizenOf(Mary,Australia).

Rules are considered of more use if they generalise well, that is, they explain many facts. To quantify this idea we recall measures support, head coverage and standard confidence that are used in some major approaches to rule learning including [9] and [15].

Standard confidence (SC) and head coverage (HC) offer standardised measures for comparing rule quality. SC describes how frequently the rule is true, i.e., of the number of entity pairs that satisfy the body in the KG, what proportion of the inferred head instances are satisfied? It is closely related to confidence widely used in association rule mining [1]. HC measures the explanatory power of the rule, i.e., what proportion of the facts satisfying the head of the rule could be inferred by satisfying the rule body? It is closely related to cover which is widely used for rule learning in inductive logic programming [34]. A non-recursive rule that has both 100% SC and HC is redundant with respect to the KG, and every KG fact that is an instance of the rule head is redundant with respect to the rule.

2.2.Open-path rules: Rules with open variables

Unlike earlier work in rule mining for KG completion, Oprl for active knowledge graph completion [18] defines open path (OP) rules of the form:

We call a variable closed if it occurs in at least two distinct predicate terms, such as z0 here, and otherwise it is open. If all variables of a rule are closed then the rule is closed. An OP rule has two open variables, y and x. [18] uses OP rules since they imply the existence of a fact, like spouse(x,y)→∃zchild(x,z) [15]. Unlike CP rules, OP rules do not necessarily form a loop, but a straightforward variable unification transforms an OP rule to a CP rule, and every entity-instantiation of a CP rule is also an entity-instantiation of the related OP rule (but not vice-versa).

To assess the quality of OP rules, we use open path standard confidence (OPSC) and open path head coverage (OPHC) which are derived in [18] from the closed path forms (Definition 2).

2.3.SHACL shapes

A KG is a schema-free database and does not need to be augmented with schema information natively. However, many KGs are augmented with type information that can be used to understand and validate data and can also be very helpful for inference processes on the KG. In 2017 the Shapes Constraint Language (SHACL) [21] was introduced as a W3C recommendation to define schema information for KGs stored as an RDF graph. SHACL defines constraints for graphs as shapes. KGs can then be validated against a set of shapes.

Shapes can serve two main purposes: validating the quality of a KG and characterising the frequent patterns in a KG. In Fig. 2, we illustrate an example of a shape from Wikidata,11 where x and zis are variables that are instantiated by entities. Although the shape is originally expressed in ShEx [32], we translate it to SHACL in the following.

humanShape
    a sh:NodeShape;
    sh:targetClass class:human ;
    sh:property [
        sh:path property:citizenOf ;
        sh:class class:country ;
        sh:nodeKind sh:IRI ;
    ];
    sh:property [
        sh:path property:father ;
        sh:class class:human ;
        sh:nodeKind sh:IRI ;
    ];
    sh:property [
        sh:path property:nativeLanguage ;
        sh:class class:language ;
        sh:nodeKind sh:IRI ;
    ];

SHACL, together with SHACL advanced features [20] is extensive. Here we focus on the core of SHACL in which node shapes constrain a target predicate (e.g., the unary predicate human in Fig. 2), with property shapes expressing constraints over facts related to the target predicate. We particularly focus on property shapes which act to constrain an argument of the target predicate. In Fig. 2 the shape expresses that each entity x which satisfies human(x) should satisfy the following paths: (1) citizenOf(x,z1)∧country(z1), (2) father(x,z2)∧human(z2), and (3) nativeLanguage(x,z3)∧language(z3).

Fig. 2.

An example of a SHACL shape from Wikidata.

Various formalisms with corresponding shapes have been proposed to express diverse kinds of patterns exhibited in KGs, such as k-cliques, Closed rules (CR) [15] (that include closed path rules), Functional Graph Dependency (FGD) [13], and trees [3]. CRs are used for inferring new facts. FGDs define constraints like the type of entities in the domain and range of predicates, or the number of entities to which an entity can be related by a specific predicate. These constraints are deployed to make the KG consistent. Regardless of differences amongst these formalisms, they share a key feature in their syntax. The building block for expressing all of these shape constraints is a sequence of predicates.

We focus on such path shapes for our shape learning system. A path is a sequence of predicates connected by closed intermediate variables but terminating with open variables at both ends. Although shapes in the form of a path are less constrained than some more complex shapes, they are a more general template for more complex shapes like closed rules or trees, which are also paths (with further restrictions). We will define Inverse Open Path rules induced from paths that have a straightforward interpretation as shapes, and also propose a method to mine such rules from a KG. To demonstrate the potential for these kind of shapes to serve as building blocks for more complex shapes, we then propose a method that builds trees out of mined rules, and briefly discuss the application of such trees to KG completion.

3.1.Rules with open variables or uncertain shapes

We observe that the converse of OP rules, that we call inverse open path rules (IOP), correspond to SHACL shapes. For example, the shape of Fig. 2 can be derived from the following three IOP rules:

To assess the quality of IOP rules we follow the style of quality measures for OP rules [18].

Notably, because any instantiated open path in a KG induces both an OP and IOP rule: the support for an IOP rule is the same as the support for its corresponding OP form; IOPSC is the same as the corresponding OPHC; and IOPHC is the same as the corresponding OPSC. This close relationship between OP and IOP rules helps us to mine both OP and IOP rules in the one process.

We show the relationship between an OP rule and its converse IOP version in the following example. Consider the OP rule, P1(x,z0)←P2(z0,z1)∧P3(z1,z2). Assume we have three entities ({e3,e4,e5}) which can instantiate z0 and satisfy both P1(x,z0) and P2(z0,z1)∧P3(z1,z2). Assume the number of entities that can instantiate z0 to satisfy the head part is 5 ({e1,e2,e3,e4,e5}) and the number of entities that can instantiate z0 to satisfy the body part is 7 ({e3,e4,e5,e6,e7,e8,e9}). Hence, we have the following for this rule, OPsupp=3, OPSC=3/7 and OPHC=3/5. For the IOP version of the rule over the same KG, P1(x,z0)→P2(z0,z1)∧P3(z1,z2), we have the same entities to instantiate zo while the predicate terms corresponding to the bodies and heads are swapped. Hence, we have the following for the IOP version of the rule, IOPsupp=3, IOPSC=3/5 and IOPHC=3/7.

In many cases we need the rules to express not only the necessity of a chain of facts (the facts in the head of the IOP rule) but the number of different chains which should exist. For example, we may need a rule to express that each human has at least two parents. Hence, we introduce IOP rules annotated with a cardinality, Car. This gives us the following annotated form for each IOP rule.

The cardinality expresses a lower bound on the number of head paths which are satisfied in the KG for every instantiation of the variable that joins the body to the head. For example, if we have 0.8,0.1,2:Pt(x,y)→P1(y,z)∧P2(z,t) and have Pt(e1,e2) satisfied, we should have at least two paths starting from e2 that instantiate two distinct entities for variable t, of the form P1(e2,z)∧P2(z,e3) and P1(e2,z)∧P2(z,e4). There is no limitation on the instantiations for variable z which is scoped inside the head, so these two pairs of instantiations both satisfy cardinality of 2: (1) P1(e2,e5)∧P2(e5,e3) and P1(e2,e5)∧P2(e5,e4) and (2) P1(e2,e5)∧P2(e5,e3) and P1(e2,e6)∧P2(e6,e4).

Rules with the same head and the same body may have different cardinalities. In the given example we might have the following rule as well, 0.9,0.1,1:Pt(x,y)→P1(y,z)∧P2(z,t). While we have a rule with a cardinality, c1, we also have rules with lower cardinalities 1,…,(c1−1) but their IOPSCs should be as good or better than the rule with c1 cardinality. This statement is quite intuitive since cardinality expresses a lower bound on the number of instances of the head in the KB.

This Lemma is useful in the process of rule learning since it shows that if we discard a rule due to its low IOPSC, v, we do not need to check the rule extended with more head atoms, since those rules’ IOPSCs are at most v. Hence the process of pruning such rules does not harm the completeness of the rule learning.

3.2.IOP learning through representation learning

To mine IOP rules, we start with the open path rule learner Oprl [18], and adapt its embedding-based OP rule learning to learn annotated IOP rules. We call this new IOP rule learner, SHACLearner, shown in Algorithm 1.

SHACLearner uses a sampling method Sampling(), shown in Algorithm 2, to prune the entities and predicates that are less relevant to the target predicate to obtain a sampled KG. The sample is fed to an embedding learner, RESCAL [24,25], in Embeddings(). Then in PathFinding(), SHACLearner uses the computed embedding representations of predicates and entities in heuristic functions that inform the generation of IOP rules bounded by a maximum length. Then, potential IOP rules are evaluated, annotated, and filtered in Ev() to produce annotated IOP rules. Eventually, a tree is discovered for each argument of each target predicate by aggregating mined IOP rules in GreedySearch().

While the overall algorithm structure of SHACLearner is similar to Oprl [18], as is the embedding-based scoring function, the following elements are novel in SHACLearner:

Algorithm 1

SHACLearner

3.3.Sampling

In more detail, the Sampling() method in line 1 of Algorithm 1 computes a fragment of the KG, K′, consisting of a bounded number of entities that are related to the target predicate Pt. This sampling is essential since embedding learners (e.g., HOLE [24] and RESCAL) cannot handle massive KGs with millions of entities (e.g., YAGO2).

The sampling method, first introduced in [27], is shown in Algorithm 2. Since we search for IOP rules with up to l atoms (including the specific body target predicate, Pt), the entity set Esample and corresponding fact set K′ contains the information needed for learning such rules. Predicates less relevant to the target predicate are pruned in the sampling process and no facts about those predicates remain in K′.

This simple approach reduces the size of the problem significantly, as discussed in [28]. For a KG K with entities E and facts F, the set of sampled entities for a target predicate will be of size 2l.|F|.|E| in the worst case. Hence, the complexity of the sampling algorithm is O(|K|) where |K|=|E|.|F|. In the worst case, the sampled KG size is the same as the original KG, but real-world KGs are sparse with only a very small proportion of entities associated with any predicate within distance l. In practice, the sampled KG is far smaller than the original KG.

Algorithm 2

Sampling

3.4.Embeddings

After sampling, in line 2 Embeddings(), we compute predicate embeddings as well as subject and object argument embeddings for all predicates in the sampled K′, as is done in RLvLR [27]. The embedding is obtained from RESCAL [24,25] as it can provide an extensive representation of predicates and entities as is shown in previous heuristic rule learners like [28].

Briefly, we use RESCAL [24] to embed each entity ei to a vector Ei∈Rd and each predicate Pk to a matrix Pk∈Rd×d where R is the set of real numbers and d is an integer (a parameter of RESCAL). For each given fact P0(e1,e2), the following scoring function is computed:

In Embeddings() we additionally compute argument embeddings according to the method proposed in [27]. To compute the subject (respectively object) argument embeddings of a predicate Pk, we aggregate the embeddings of entities that occur as the subject (respectively object) of Pk in the KG. Hence for each predicate Pk we have two vectors, Pk1 and Pk2 that present the subject argument and object argument of Pk respectively.

3.5.Generating and pruning rules

After that, in line 3 to line 7 of Algorithm 1, PathFinding() produces candidate IOP rules based on the embedding representation of the predicates which are involved in each rule. The candidate rules are pruned by the scoring function heuristic proposed in [18] for OP rules. Due to the close relationship between OP and IOP rules, a high-scoring candidate OP rule suggests both a good OP rule and a good IOP rule.

An IOP rule Pt(x,y)→P1(y,z)∧P2(z,t). acts to connect entities satisfying the subject argument of the body predicate, Pt, to entities forming the object argument of the last predicate, P2, along a path of entities that satisfy a chain of predicates in the rule. There is a relationship between the logical statement of the rule and the following properties in the embedding space [18]:

Based on the above two properties, [18] defines two scoring functions that help us to heuristically mine the space of all possible IOP rules to produce a reduced set of candidate IOP rules.

The ultimate evaluation of an IOP rule will be done in the next step as described below.

3.6.Efficient computation of quality measures

Now we focus our attention on the efficient matrix-computation of the quality measures that are novel for SHACLearner. Ev() in Algorithm 1 first evaluates candidate rules on the small sampled KG, and selects only the rules with IOPsupp(r)⩾1. They may still include a large number of redundant and low quality rules and so are further downselected based on their IOPSC and IOPHC calculated over the full KG. We show in the following how to efficiently compute the measures over massive KGs using an adjacency matrix representation of the KG.

Let K=(E,F) with E={e1,…,en} be the set of all entities and P={P1,…,Pm} be the set of all predicates in F. Like RESCAL [24,25], we represent K as a set of square n×n adjacency matrices by defining the function A. Specifically, the [i,j]th element A(Pk)[i,j] is 1 if the fact Pk(ei,ej) is in F; and 0 otherwise. Thus, A(Pk) is a matrix of binary values and the set {A(Pk)∣k∈{1,…,m}} represents K.

We illustrate the computation of IOPSC and IOPHC through an example. Consider the IOP rule r:Pt(x,z0)→P1(z0,z1)∧P2(z1,y). Let E={e1,e2,e3} and

For (1) we can read the pairs (e″,e) directly from the matrix A(Pt). To find distinct es we sum each column (corresponding to each value for the second argument) and transpose to obtain the vector V2(Pt). Each non-zero element of this vector indicates a satisfying e and the number of distinct es is given by simply counting the number of non-zero elements. In the example, the only non-zero element in A(Pt) is A(Pt)[1,3] and after summing the columns and transposing we have

For (2) the pairs (e,e′) satisfying the head are connected by the path P1,P2,…Pm, and can be obtained, as for (1), directly from the matrix product A(P1)A(P2)…A(Pm), being the elements with a value ⩾Car (for rules with cardinality Car). To find distinct es we sum each row (corresponding to each value for the first argument) to obtain the vector V1(A(P1)A(P2)…A(Pm)). Each element with ⩾Car value of this vector indicates a satisfying e and the number of distinct es is given by counting the number of elements in V1(A(P1)A(P2)…A(Pm)).

In the example we have

Computing (3) is now straightforward. We have that the row index of non-zero elements of V2(Pt) indicates entities that satisfy the second argument of the body and that the row index of elements with a value ⩾Car of V1(A(P1)A(P2)…A(Pm)) indicates entities that satisfy the first argument of the head. Therefore we can find the entities that satisfy both of these conditions by pairwise multiplication. That is, the entities we need are {ei∣(V2(Pt)[i]>0∧V1(A(P1)A(P2)…A(Pm))[i])⩾Car and 1⩽i⩽n}, and the count of entities is the size of this set. For the example, for Car=1, we have {e2,e3} in the set with count 2 and for Car=2, we have {e2} in the set with count 1.

Hence, we could have three versions of r, i.e., r1,r2 and r3 with three different Car of 1, 2, and 3 respectively. For Car=1, IOPsupp(r1)=|{e2,e3}|=2. From Definition 4 we can obtain IOPHC(r1)=2/2 and IOPSC(r1)=2/2. For Car=2, IOPsupp(r2)=|{e2}|=1. We can obtain IOPHC(r2)=1/1 and IOPSC(r2)=1/2. In this case, we have the same qualities for Car=3 as we have for Car=2.

3.7.From IOP rules to tree shapes

Now in line 8 of Algorithm 1 we turn to deriving SHACL trees, as illustrated in Fig. 3, from annotated IOP rules. This procedure is novel in SHACLearner. We use a greedy search to aggregate the IOP rules for the subject argument and the object argument of each target predicate.

For example, the shape of Fig. 2 has the following tree:

To assess the quality of a tree we follow the quality measures for IOP rules.

To learn each tree we employ a greedy search, GreedySearch, in line 8 of Algorithm 1. To do so, we sort all rules that bind the subject argument (for the left hand tree in Fig. 3) in a non-increasing order with respect to IOPSC. Then we iteratively try to add the first rule in the list to the tree and compute the TreeSC. If the TreeSC drops below the defined threshold (i.e., TreeSCMIN) we dismiss the rule otherwise we add it to the tree. For the right hand tree we do the same with the rules that bind the object argument of the target predicate. Since a conjunction of IOP rules form a tree, TreeSC is bounded above by the minimum IOPSC of its constituent IOP rules.

These uncertain shapes can be presented as standard SHACL shapes by ignoring those that fail to satisfy minimum quality thresholds and deleting the quality annotations. Aside from the cardinality, the tree may be straightforwardly interpreted as a set of SHACL shapes by reading off every path from the target predicate terminating at a node in the tree. The body predicate is declared a sh:nodeShape and the path of head predicates as nested sh:path declarations within a sh:property declaration. Cardinality of a path is read from the annotation of the branch at the terminating node, and declared by sh:minCount within the property declaration. See Section 3.1 for an example.

SHACLearner supports all the SHACL Core22 [21] features (node and property shapes). The limitations of SHACLearner with respect to SHACL Core are: (1) it treats all properties, both object and datatype properties, as “plain predicates” so there is no distinction; (2) and so it does not perform any kind of data type validation; and (3) of cardinality expressions, only min cardinality is handled. SHACLearner does not mine SPARQL-like constraints, SHACL-SPARQL.33

Fig. 3.

Trees for a target predicate Pt. Each vi indicates a TreeSC.

5.1.Transforming KGs with type predicates for experiments

Since real-world KG models treat predicates and entities in a variety of ways, we require a common representation for this work that clearly distinguishes entities and predicates. We employ an abstract model that is used in Description Logic ontologies, where classes and types are named unary predicates, and roles (also called properties) are named binary predicates.

Presenting the class and type information as unary predicates also allows us to learn fully abstracted (entity-free) shapes (e.g. type_E(x)→P1(x,y),P2(y,z)) instead of partially instantiated shapes (e.g. type(x,E)→P1(x,y),P2(y,z)). This feature is important since learning partially instantiated shapes can cause an explosion in the space of possible shapes. Using self-loop links for unary predicates is convenient syntactic sugar to keep the presentation in the triple format, as for the original input KGs.

In real-world KGs, concept or class membership may be modeled as entity instances of a binary fact. For example, DBpedia contains “<dbo:type>(x,y)” and “<dbo:class>(x,y)” predicates where the second arguments of these predicates are types (e.g. “<db:Album>” or “<db:City>”) or classes (e.g. “<db:Reptile>” or “<db:Bird>”). Instead, we choose to model types and classes with unary predicates. To do so we make new predicates like <dbo:type>_ <db:Album>(x) from facts in the form <dbo:type> (x,<db:Album>), where x is the name of an album. Then we produce new unary facts based on the new predicate and related facts. For example, for <dbo:type>(Revolver,<db:Album>), we produce the new fact <dbo:type>_<db:Album>(Revolver).

We use the two type-like predicates from DBpedia 3.8 “<dbo:type>” and “<dbo:class>” and the one from Wikidata “<occupation_P106>” to generate our unary predicates and facts. These predicates each have a class as their second argument. To prune the classes with few instances for which learning may be pointless, we consider only our unary predicates which have at least 100 facts. We retain the original predicates and facts in the KG as well as extending it with our new ones. In Table 1 we report the specifications of two benchmarks where we have added the unary predicates and facts (denoted as +UP).

5.2.Learning IOP rules

We follow the established approach for evaluating KG rule-learning methods, that is, measuring the quantity and quality of distinct rules learnt. Rule quality is measured by Inverse open path standard confidence (IOPSC) and Inverse open path head coverage (IOPHC). We randomly select 50 target predicates from Wikidata and DBPedia unary predicates (157 and 355 respectively). We use all binary predicates of YAGO2s (i.e., 37) as target predicates. Each binary target predicate serves as two target predicates, once in the straight form (where the object argument of the predicate is the common variable to connect the head) and secondly in its reverse form (where the subject argument serves to connect). In this manner, we ensure that the results of SHACLearner on YAGO2s with its binary predicates as targets is comparable with the results for Wikidata and DBpedia that have unary predicates as targets. Hence for YAGO2s we have 74 target predicates.

A 10 hour limit is set for learning each target predicate.

Table 2 shows #Rules, the average numbers of quality IOP rules found; %SucTarget, the proportion of target predicates for which at least one IOP rule was found; and the running times in hours, averaged over the targets. Only high quality rules meeting minimum quality thresholds are included in these figures, that is, with IOPSC⩾0.1 and IOPHC⩾0.01, thresholds established in comparative work [15]. These thresholds are quite low, so rules of low quality are also included. Generally, selecting a low threshold at the time of learning is a safe choice since the rules can be further pruned by applying stricter quality thresholds later on.

SHACLearner shows satisfactory performance in terms of both the runtime and the numbers of quality rules mined. Note that rules found have a variety of lengths and cardinalities. To better present the quality performance of rules we illustrate the distribution of rules with respect to the features, IOPSC, IOPHC, cardinality and length, and also IOPSC vs length. In the following, the proportion of mined rules having the various feature values is presented, to more evenly demonstrate the quality of performance over the three very different KGs.

Fig. 4.

Distribution of mined rules with respect to IOPSC and IOPHC.

The distribution of mined rules with respect to their IOPSC and IOPHC is shown in Fig. 4. In the left-hand chart we observe a consistent decrease in the proportion of quality rules as the IOPSC increases. In the right hand chart we see a similar pattern for increasing IOPHC, but the decrease is not as consistent, showing there must be many relevant rules with many covered head instances. Over all benchmarks, the majority of learned rules have lower IOPSC and IOPHC. This is expected because the statistical likelihood of poor quality rules is much higher. Indeed, we show experimentally in Section 5.3 that our pruning techniques, that are necessary for scalability, prune away predominantly lower quality rules.

With respect to IOPSC, proportionally more quality rules are learnt from DBpedia than from the other KGs, with Wikidata coming second, ahead of YAGO2s. This phenomenon might be a result of our deliberate selection of type-like unary predicates as targets for DBPedia and Wikidata, whereas for YAGO2s we use every one of the 37 binary predicates as a target.

Fig. 5.

Distribution of mined rules with respect to their cardinalities.

Fig. 6.

Distribution of mined rules with respect to their lengths.

The distribution of mined rules with respect to their cardinalities is shown in Fig. 5. We observe that the largest proportion of rules has a cardinality of 1, as expected, as they have the least stringent requirements to be met in the KG. We observe an expected decrease with greater cardinalities as they demand tighter restrictions to be satisfied. YAGO2 demonstrates a tendency towards higher cardinalities than the other KGs, possibly a result of its more curated development.

The distribution of mined rules with respect to their lengths is shown in Fig. 6. One might expect that as the length increases, the number of rules would increase since the space of possible rules grows, and this is what we see.

For a concrete example of SHACL learning, we show the following three IOP rules mined from DBpedia in the experiments. The IOPSC, IOPHC, and Cardinality annotations respectively prefix each rule.

<dbo:type>_<db:Song>(x) expresses x is a song. The first rule indicates x should belong to an album (z1) that has y as record label. The second rule requires a song (x) to have at least one producer while the third rule requires a song to have at least two producers, and these two rules are distinguished by the cardinality annotation. As we discussed in 3.1, the third rule is more constraining than the second, so the confidence of the third rule is lower than the confidence of the second, based on the KG data.

The rules can be trivially rewritten (through a script that we developed) into SHACL syntax as follows.

:s1 a sh:NodeShape ;
    sh:targetClass :<dbo:type>_<db:Song> ;
    sh:property [
        sh:minCount 1 ;
        sh:path :<dbo:album> ;
            [sh:path :<dbo:recordLabel> ; ]
    ] .
:s2 a sh:NodeShape ;
    sh:targetClass :<dbo:type>_<db:Song> ;
    sh:property [
        sh:minCount 1 ;
        sh:path :<dbo:producer> ;
    ] .
:s3 a sh:NodeShape ;
    sh:targetClass :<dbo:type>_<db:Song> ;
    sh:property [
        sh:minCount 2 ;
        sh:path :<dbo:producer> ;
    ] .

5.3.Completeness analysis of IOP rule learning

SHACLearner uses two tricks to significantly reduce the search space for IOP rules in PathFinding() of Algorithm 1, namely the prior Sampling() and the heuristic pruning used inside PathFinding() that uses the embedding-based scoring function. We conduct experiments to explore how these two pruning methods affect SHACLearner with regard to the quality and quantity of learnt rules. To do so we create three variants of SHACLearner as follows.

We observe that SHACLearner does not miss any rules of the highest quality, i.e., with IOPSC⩾0.9. SHACLearner’s pruning methods cause it to fail to discover more rules of lower quality, with the number of missing rules increasing as quality decreases. This is a reassuring property, since the goal of pruning is to improve the computational performance without missing high-quality rules. In real applications we will typically retain and action only the highest quality rules.

We observe that, unlike the other pruning variants, using heuristic pruning alone in (-S+H) does not uniformly increase in effectiveness with decreasing rule quality. This may be because using the complete KG for learning rules about all target predicates could harm the quality of the learnt embeddings used in the scoring function of SHACLearner. The better quality of embeddings extracted from the sampled KG arises from our sampling method that creates a KG that is customised for the target predicate. All entities in the sampled KG are either directly related to the target predicate or close neighbours of directly related entities as we described in 3.3.

5.4.Learning trees from IOP rules

Now we turn to presenting results for the trees that are built based on the IOP rules discovered in the experiments. We report the characteristics of discovered trees in Table 4. We use a value of 0.1 for the TreeSCMIN parameter and show average TreeSC for each KG, along with the average number of branches in the trees and the average tree-building runtime. The number of trees for each KG is defined by the number of target predicates for which we have at least one IOP rule (see %SucTarget in Table 2).

The results show the running time for aggregating IOP rules into trees is lower than the initial IOP mining time by a factor greater than 10. If, on the other hand, we wanted to discover such complex shapes from scratch it would be exhaustively time consuming due to the sensitivity of rule learners to the maximum length of rules. The number of potential rules in the search space grows exponentially with the maximum number of predicates of the rules. The average number of branches in the mined trees are 50%, 31%, and 56% of the corresponding number of mined rules respectively from Table 2. Hence, by imposing the additional tree-shaped constraint over the basic IOP-shaped constraint, at least 44% of IOP rules are pruned.

For an example of tree shape learning, in the following, we show a fragment of a 39-branched tree mined from DBpedia by aggregating IOP rules in the experiments.

Here, the first annotation value (0.13) presents the SC of the tree and the subsequent values at the beginning of each branch indicate the branch cardinality. This tree can be read as saying that a song has an album with a record label, an album with two producers, an album with a genre, and an artist who is a musical artist.

As can be seen here, there remains an opportunity for improving tree shapes for simplicity and easier interpretation by unifying some variables that occur in predicates that occur in multiple branches. We plan to investigate this potential post-processing step in future work.