Using knowledge anchors to facilitate user exploration of data graphs

2.1. Exploration through data graphs

Semantic data exploration approaches are divided into two broad categories: (i) visualisation approaches [32,39,48,62] and (ii) text-based semantic data browsers [7,47,72,91]. Visualisation provides an important tool for exploration that leverages the human perception and analytical abilities to offer exploration trajectories. These approaches, in addition to intuitiveness, focus on the need for managing the dimensions in semantic data represented as properties, similarity and relatedness of concepts. The text-based browser approaches operate on semantically augmented data (e.g. tagged content) with layout browsing trajectories using relationships in the underpinning ontologies. These approaches adopt techniques from learning, human-computer interaction and personalisation to enhance the data exploration experience of users.

2.2. Identifying key entities in data graphs

The most recent statistics2

Ontology summarisation has been seen as an important method to help ontology engineers to make sense of an ontology, in order to understand, reuse and build new ontologies [39,56]. Summarising an ontology involves identifying the key concepts in an ontology [93]. An ontology summary should be concise, yet it needs to convey enough information to enable ontology understanding and to provide sufficient coverage of the entire ontology [88]. Centrality measures have been used in [98] to identify key concepts and produce RDF summaries. The notion of relevance based on the relative cardinality and the in/out degree centrality of a node has been used in [87] to produce graph summaries. The approach presented in [88] exploits the structure and the semantic relationships of a data graph to identify the most important entities using the notion of relevance, which is based on relative cardinality (i.e. judging the importance of an entity from the instances it contains) and the in/out degree centrality (i.e. the number and type of the incoming and outgoing edges) of an entity.

The closest ontology summarisation approach to the context of our work deals with extracting key concepts in an ontology [25,69]. It highlights the value of cognitive natural categories for identifying key concepts to aid ontology engineers to better understand the ontology and quickly judge the suitability of an ontology in a knowledge engineering project. The authors applies a name simplicity approach, which is inspired by the cognitive science notion of Basic Level Objects (BLO) [76] as a way to filter entities with lengthy labels for the ontology summary. The work in [25] has utilised BLO to extract ontologies from collaborative tags. A metric based on the category utility is proposed to identify basic concepts from collaborative tags, where tags of a concept are inherited by its sub-concepts and a concept has all instances of its descendants. However, these approaches focus on the experimental side, and do not adopt the formal definitions of BLO and cue validity described in [75,76] in the context of a data graph. Our work operationalises these formal definitions by developing several metrics for identifying knowledge anchors in a data graph.

Formal Concept Analysis (FCA) is a method for analysis of object-attribute data tables [95], where data is represented as a table describing objects (i.e. taxonomical concepts), attributes and their relationships. FCA has been applied in different application areas [30,71] such as Web mining and ontology engineering. In Web mining, FCA based approaches have been used to improve the quality of search results presented to the end users. For example, the work in [29] has developed a personalised domain-specific search system that uses logs of keywords and Web pages previously entered and visited by other persons to build a concept lattice. More recently, FCA has been applied to construct a link pattern hierarchy to organise semantic links between entities in a data graph [99]. In ontology engineering, FCA has been used in two topics: ontology construction and ontology refinement. The work in [74] uses FCA to construct ad hoc ontologies to help the user to better understand the research domain. In [81] the authors present OntoComp, an approach for supporting ontology engineers to check whether an OWL ontology covers all relevant concepts in a domain, and supports the engineers to refine (extend) the ontology with missing concepts. The psychological approaches to basic level concepts have been formally defined for selecting important formal concepts in a concept lattice by considering the cohesion of a formal concept [15]. This measures the pair-wise similarity between the concept’s objects based on common attributes. More recently, the work in [16] has reviewed and formalised the main existing psychological approaches to basic level concepts. Five approaches to basic level objects have been formalised with FCA [16]. The approaches utilise the validity of formal concepts to produce informative concepts capable of reducing the user’s overload from a large number of concepts supplied to the user.

Existing studies in ontology summarisation and FCA utilise BLO to identify key concepts in an ontology in order to help experts to examine or reengineer the ontology. They have been evaluated with domain experts, and are applicable in tasks where the users have a good understanding of the domain. In contrast, we apply the notion of BLO in a data graph to identify concepts which are likely to be familiar to users who are not domain experts. Focusing on layman users, we provide unique contribution that adopts Rosch’s seminal cognitive science work [76] to devise algorithms that identify (i)  KA DG that represent familiar graph entities, and (ii)  BLO DG which correspond to human cognitive structures over a data graph. Crucially, these algorithms are validated with layman users who are not domain experts.

In data graphs, the notion of path queries uses regular expressions to indicate start and end entities of paths in data graphs [22]. For example, in a geographical graph database representing neighborhoods (i.e. places) as entities and transport facilities (e.g. Bus, Tram) as edges, the user writes a simple query such as “I need to go from Place a to Place b”, and the user is then provided with different transportations facilities going through different routes (paths) starting from Place a to reach the destination Place b [22]. Another used notion is property paths which specify the possible routes between two entities in a data graph. Property paths are used to capture associations between entities in data graphs where an association from entity a to entity b comprises entity labels and edges [6]. However, in data graphs there are usually high numbers of associations (i.e. possible property paths) between the entities and ways to refine and filter the possible paths, are required. To tackle this challenge, the work in [28] presented Explass3

While several approaches address the problem of supporting users’ exploration through data graphs, none of them aims at supporting layman users who are not domain experts. Many of the existing approaches may not be suitable for layman users, who may become confused or overloaded with too much unfamiliar entities. None of the existing approaches offers exploration paths to help users to expand their domain knowledge. Several approaches generate paths that link graph entities specified by the user, and are therefore suitable for tasks where the users are familiar with the domain. Instead, we provide paths for uni-focal exploration where the user starts from a single entry point and explores the data graph. The unique feature of our work is the explicit consideration of knowledge utility of exploration paths. We are finding entities that are likely to be familiar to the user and using them as knowledge anchors to gradually introduce unfamiliar entities and facilitate learning. This can enhance the usability of semantic data exploration systems, especially when the users are not domain experts. Therefore, our work can facilitate further adoption of linked data exploration in the learning domain. It can also be useful in other applications to facilitate the exploration by users who are not familiar with the domain presented in the graph.

In the context of ontology summarisation, there are two main approaches for evaluating a user-driven ontology summary [56]: gold standard evaluation, where the quality of the summary is expressed by its similarity to a manually built ontology by domain experts, or corpus coverage evaluation, in which the quality of the ontology is represented by its appropriateness to cover the topic of a corpus. The evaluation approach used in [69] included identifying a gold standard by asking ontology engineers to select a number of concepts they considered the most representative for summarising an ontology. In this paper, we evaluate algorithms for identifying KA DG by comparing the algorithms’ outputs versus a benchmarking set of BLO identified by humans. To the best of our knowledge, there are no evaluation approaches that consider key concepts in data graphs which correspond to cognitive structures of users who are not domain experts. Our evaluation approach that identifies BLO DG through an experimental method adapting Cognitive Science methods is novel and can be applied to a range of domains.

Evaluation of data exploration applications usually considers the exploration utility from a user’s point of view or analyses the application’s usability and performance (e.g. precision, recall, speed etc.) [62]. The prime focus is assessing the usability of semantic Web applications, while assessing how well the applications help the users with their data exploration tasks is still a key challenge [40]. Task driven user studies have been utilised to assess whether a data exploration application provides useful recommendations for accomplishing users exploration tasks [66]. A task driven benchmark for evaluating semantic data exploration has been presented in [40]. The benchmark presents a set of information-seeking tasks and metrics for measuring the effectiveness of completing the tasks. The evaluation approach in [54] aims to identify whether the simulated exploration paths information networks are similar to those produced by human exploration. We will adopts the established task-based approach and will utilise an educational taxonomy for assessing conceptual knowledge to assess knowledge utility and usability of the generated exploration paths.

3.1. Application context

Our novel data graph exploration approach includes several algorithms which are formally defined and are independent from the domain and the data graph used. In order to validate the approach and evaluate the algorithms, we need a concrete application context. We will utilise MusicPinta – a semantic data browser in the music domain [86]. MusicPinta provides a uni-focal interface for users to navigate through musical instrument information extracted from various linked datasets. The MusicPinta dataset includes several sources, including DBpedia5

The MusicPinta dataset has 2.4M entities and 19M triple statements, taking 2 GB physical space, including 876 musical instruments entities, 71k (performances, albums, records, tracks), and 188k music artists. The dataset is made available on sourceforge.7

The MusicPinta dataset provides an adequate setup since it is fairly large and diverse, yet of manageable size for experimentation. The music ontology provides sufficient class hierarchy for experimentation. For instance, the class hierarchies for the String and Wind musical instruments have depths of 7, which is considered ideal for applying the cognitive science notion of basic level objects [76] on data graphs, as this notion states that objects within a hierarchy are classified at least three different levels of abstraction (superordinate, basic, subordinate). Figures 1–3 show examples of the user interface in the MusicPinta semantic data browser.

OPEN IN VIEWER

Fig. 1.

Semantic search interface in MusicPinta where a user inserts a name of a musical instrument (e.g. Xylophone).

OPEN IN VIEWER

Fig. 2.

Description page of the entity ‘Xylophone’ in MusicPinta, extracted from DBpedia using CONSTRUCT queries.

OPEN IN VIEWER

Fig. 3.

Semantic Links (i.e. predicates) related to entity Xylophone presented in Features and Relevant Information. Features include semantic relationships rdf:type (e.g. Xylophone is an instrument), rdfs:subclassOf (e.g. subClass Xylophone belongs to superClass Tuned Percussion) and dcterms:subject (e.g. Xylophone belongs to DBpedia category Greek loanwords). Relevant Information include rdfs:subclassOf (e.g. Celesta is subClassOf Xylophone).

To approximate the knowledge utility of an exploration path, we need a systematic approach. For this, we adapt the well-known taxonomy by Bloom [52] which is used for assessing conceptual knowledge. The taxonomy identifies a set of progressively complex learning objectives that can be used to assess learning experiences over information seeking and search tasks [38]. It suggests linking knowledge to six cognitive processes: remember, understand, apply, analyze, evaluate, and create. Among these, remember and understand are directly related to browsing and exploration activities. The remaining processes require deeper learning activities, which usually happen outside a browsing tool, in our case Semantic data browser, and hence will not be considered. The process remember is about retrieving relevant knowledge from the long-term memory, and includes recognition (locating knowledge) and recall (retrieving it from memory) [52]. The process understand is about constructing meaning; the most relevant to our context are categorise (determine entity membership) and compare (detect similarities) [52].

To approximate the knowledge utility of an exploration path, we employ schema activation – it was applied for assessing user knowledge expansion when reading text [26]. To assess the user’s knowledge of a target domain concept (X), the user is asked to name concepts that belongs to and are similar to the target concept X. A schema activation test is conducted before an exploration and after an exploration, using three questions related to the cognitive processes remember, categories, and compare:

The number of accurate concepts named (e.g. naming an entity with its exact name, or with a parent or with a member of the entity) by the user before and after exploration is counted, and the difference indicates the knowledge utility of the exploration. For example, if a user could name correctly two musical instruments similar to the musical instrument Biwa (Q3) before an exploration and then the user could name correctly six names of musical instruments similar to the instrument Biwa after the exploration, then the effect of the exploration on the cognitive process compare is indicated as 4 (i.e. as a result of the exploration the user learned 4 new similar musical instruments to the musical instrument Biwa). If the user named only one instrument after the exploration, the user knowledge did not increase, and the knowledge utility will be counted as zero.

3.3. Subsumption theory underpinning exploration

In a scoping user study, we examined user exploration of musical instruments in MusicPinta to identify what strategies would lead to paths with high knowledge utility (details of the study are given in [5]). We examined two dimensions – the user’s familiarity with the domain and the density of entities in the data graph. Paths which included familiar and dense entities and brought unfamiliar entities led to increasing the users’ knowledge. For example, when a participant was directed to explore the entity Guitar which he/she was familiar with, the participant could see unfamiliar entities linked to Guitar such as Resonator Guitar and Dobro. The entity Guitar served as an anchor from where the user made links to new concepts (Resonator Guitar and Dobro). We also noted that the dense entities, which had many subclasses and were well-connected in the graph, provided good potential anchors that could serve as bridges to learn new concepts.

While the scoping study provided us with useful insights, it did not give solid theoretical model for developing an approach that generalises across domains and data graphs. The study findings directed us to Ausubel’s subsumption theory for meaningful learning [9] as a possible theoretical underpinning model for generating exploration paths. This theory [8–10,12] has been based on the premise that a human cognitive structure (i.e. individual’s organisation, stability, and clarity of knowledge in a particular subject matter field) is the main factor that influences the learning and retention of new knowledge [10]. In relation to meaningful learning, the subsumption process postulates that a human cognitive structure is hierarchically organised with respect to levels of abstraction, generality, and inclusiveness of concepts. Highly inclusive concepts in the cognitive structure can be used as knowledge anchors to subsume and learn new, less inclusive, sub-concepts through meaningful relationships [8,9,11,13]. Once the knowledge anchors are identified, attention can be directed towards identifying the presentation and sequential arrangement of the new subsumed content [10]. Hence, to subsume new knowledge, anchoring concepts are first introduced to the user, and then used to introduce new concepts.

3.4. Basic level objects

To identifying knowledge anchors in data graphs, we need to find entities that can be highly inclusive and familiar to the users. For this, we will adopt the Basic Level Objects (BLO) notion which was introduced by Cognitive science research. It states that domains of concrete objects include familiar categories that exist at an inclusive level of abstraction in human cognitive structures (called the basic level). Most people are likely to recognise and identify objects at the basic level. An example from the experimental studies from Rosch et al. [76] of a BLO in the music domain is Guitar. Guitar represents a familiar category that is neither too generic (e.g. musical instrument) nor too specific (e.g. Folk Guitar – subclass of the category Guitar).

Rosch, et al. [76], define BLO as: categories that “carry the most information, possess the highest category cue validity, and are, thus, the most differentiated from one another”. Crucial for identifying basic level categories is calculating cue validity: “the validity of a given cue x as a predictor of a given category y (the conditional probability of y / x ) increases as the frequency with which cue x is associated with category y increases and decreases as the frequency with which cue x is associated with categories other than y increases” [76]. A members of a BLO share many features (attributes) together, and hence they have high similarity values in terms of the feature the BLO members share. Consequently, two approaches can be applied to identify BLO in a domain taxonomy:

Distinctiveness (highest cue validity). This follows the formal definition of cue validity (given above). It identifies most differentiated category objects in a domain. A differentiated category object has most (or all) of its cues (i.e. attributes) linked to its members (i.e. subclasses of the category object) only, and not linked to other category objects in the taxonomy. Each entity linked to one (or more) members of the category object will have a single validity value used as a predictor for the distinctiveness of the category among other category objects in the taxonomy. For example, the category object v 2 in Fig. 4 has four entities ( u 3 , u 4 , u 5 , u 6 ) linked to its members ( v 21 , v 22 , v 23 , v 24 ). The validity of entity u 4 as predictor of category v 2 is higher than entity u 3 , since u 4 is only linked to members of the category v 2 whereas entity u 3 is linked to members of the categories v 1 and v 2 .

OPEN IN VIEWER

Fig. 4.

A data graph showing entities and relationship types between entities.

Homogeneity (highest commonality between category members). This identifies category objects whose members have high similarity values. The higher the similarity between category members, the more likely it is that the category object is at the basic level of abstraction. This is complementary with the distinctiveness feature described above. A category object with high cue validity will usually have high number of entities shared by its members. The homogeneity value for a category object considers the pair-wise similarity values between the category’s members. For example in Fig. 4, the category entity v 2 considers the pairwise similarities between its members (e.g. similarity between [ v 21 , v 22 ], [ v 21 , v 23 ], [ v 21 , v 24 ]). The higher the similarity between members of that category, the more likely that the category is at the basic level.

In the following sections, we will utilise Ausbel’s subsumption theory to generate exploration paths through data graphs based on knowledge anchors. We will split this into two stages: (i) identifying knowledge anchors in data graphs, and (ii) using the knowledge anchors to subsume new knowledge.

5.1. Distinctiveness metrics

This group of metrics aims to identify differentiated categories whose members are linked to distinctive entities that are shared amongst the categories’ members but not with other categories. Each category entity v ∈ V that is linked through an edge label e to members v ′ ⊆ v of the category entity v ∈ C will have a single validity value to distinguish v from the other category entities. We follow the definition of cue validity provided by Rosch et al. [76] in identifying basic level objects. According to Rosch et al., “the cue validity of an entire category may be defined as the summation of the cue validities for that category of each of the attributes of the category”. This definition is similar to the approach used to identify key concepts in formal concept analysis [16] where they summed up the validity of objects of a formal concept. Three distinctiveness metrics were developed and presented in [3].

Attribute Validity (AV). The attribute validity definition corresponds to the cue validity definition in [76] and adopts the formula from [16]. We use ‘attribute validity’ to indicate the association with data graphs – ‘cues’ in data graphs are attributes of the entities and are represented as relationships in terms of triples. The AV value of an entity v ∈ C with respect to a relationship type e, is calculated as the aggregation of the AV values for all entities v e ′ linked to subclasses v ′ : v ′ ⊆ v . The attribute validity value of v e ′ increases, as the number of relationships of type e between v e ′ and the subclasses v ′ : v ′ ⊆ v increases; whereas the attribute validity value of v e ′ decreases as the number of relationships of type e between v e ′ and all entities in the data graph increases. We define the set of entities W ( v , e ) that are related to the subclasses v ′ : v ′ ⊆ v as subjects via relationship of type e: (1) W ( v , e ) = { v e ′ : ∃ v ′ [ v ′ ⊆ v ∧ ⟨ v e ′ , e , v ′ ⟩ ∈ T ] }

Formula (2) defines the attribute validity metric for a given entity v with regards to a relationship type e. (2) AV ( v , e ) = ∑ v e ′ ∈ W ( v , e ) | { ⟨ v e ′ , e , v ′ ⟩ : v ′ ⊆ v } | | { ⟨ v e ′ , e , v a ⟩ : v a ∈ V } |

An example is provided in Fig. 4. The AV value for category entity v 2 with regard the domain-specific relationship D is the aggregation of the AV values of the subject entities u 3 , u 4 , u 5 , u 6 linked to members of the category entity v 2 (i.e. objects v 21 , v 22 , v 23 , v 24 ) via the edge label or predicate D.

The AV value for the entity u 3 equals the number of triples between the subject entity u 3 and members of the category v 2 (the object entities v 21 , v 22 ) via the relationship D (i.e. 2 triples), divided by the number of triples between the subject entity u 3 and all the object entities in the graph (i.e. v 12 , v 21 , v 22 ) via the relationship D (i.e. 3 triples). Hence the AV value for u 3 equals 2 / 3 = 0.66 . The aggregation of the individual AV values for entities u 3 , u 4 , u 5 , u 6 will identify the AV value for the category entity v 2 .

Category Attribute Collocation (CAC). This approach was used in [50] to improve the cue validity metric by adding a homogeneity weight called category-feature collocation measure which takes into account the frequency of the attribute within the members of the category. This gives preference to ‘good’ categories that have many attributes shared by their members (i.e. high similarity between members of the category). In our case, a good category will be an entity v ∈ C with a high number of relationships of type e between v e ′ and the subclasses v ′ : v ′ ⊆ v , relative to the number of its subclasses. Formula (3) defines the category-attribute collocation metric for a given entity v with regard to a relationship type e. (3) CAC ( v , e ) = ∑ v e ′ ∈ W ( v , e ) | { ⟨ v e ′ , e , v ′ ⟩ : v ′ ⊆ v } | | { ⟨ v e ′ , e , v a ⟩ : v a ∈ V } | · | { ⟨ v e ′ , e , v ′ ⟩ : v ′ ⊆ v } | | V ′ |

Considering the example in Fig. 4 for identifying the AV value for the entity u 3 , and considering the relationship D, the CAC adds a weight of (the number of the triples between the subject u 3 and the members of v 2 via the relationship D divided by the number of members of the category entity v 2 . Hence the CAC of u 3 will be the AV value of u 3 (i.e., 2 / 3 ) multiplied by (2/4), equal to 0.33. The aggregation of individual CAC values for entities u 3 , u 4 , u 5 , u 6 will identify the CAC value for v 2 .

Category Utility (CU). This approach was presented in [31] as an alternative metric for obtaining categories at the basic level object. The metric takes into account that a category is useful if it can improve the ability to predict the attributes for members of the category, i.e. a good category will have many attributes shared by its members (as mentioned in the category-attribute collocation metric), and at the same time, it possess ‘unique’ attributes that are not related to many other categories in the graph. In other words, CU gives preference to a category that have unique attributes associated only with the category’s members. We adapt the formula in [16] for a data graph: (4) CU ( v , e ) = | V ′ | | V | ∑ v e ′ ∈ W ( v , e ) ( | { ⟨ v e ′ , e , v ′ ⟩ : v ′ ⊆ v } | | V ′ | ) 2 − ( | { ⟨ v e ′ , e , v a ⟩ : v a ∈ V } | | V | ) 2

Continuing the previous example from Fig. 4 for calculating the AV and the CAC values for entity u 3 ; in addition to the category-feature collocation measure used by the CAC value, the CU will also include the proportion of all triples between the subject entity u 3 and all the object entities in the graph (i.e. entities v 12 , v 21 , v 22 ) linked via relationship D (i.e. 3 triples) over the number of entities linked via subsumption relationships (e.g. rdfs:subClassOf and rdf:type) in the graph (i.e. total 11 entities). Hence the CU value for u 3 will be: ( 2 / 4 ) 2 − ( 3 / 11 ) 2 = 0.177 . The aggregation of CU values for entities u 3 , u 4 , u 5 , u 6 , multiplied by the total number of members of category v 2 , divided by the total number of entities in the graph linked via the susbsumption relationships will result in the CU value for v 2 .

5.2. Homogeneity metrics

These metrics aim to identify categories whose members share many entities among each other. In this work, we have utilised three set-based similarity metrics9

6.1. Obtaining human BLO_DG

As described in the preliminaries, the set of entities in a data graph can be divided into two types: (i) category entities, representing the inner entities in a class taxonomy that have at least one member, and (ii) leaf entities, representing the set of entities that have no subclasses, and may have one or more individuals. Therefore, we divide the free-naming task into two strategies that correspond to the two types of entities:

Strategy 1: the participants were shown an image of a leaf entity, and were asked to type its name.

Strategy 2: the participants were shown a group of images presenting the entities of a category, and were asked to type the name of the category.

To obtain a set of human BLO DG used to benchmark the KA DG metrics, we conducted a user study with the MusicPinta data graph.

Participants. The study involved 40 participants recruited on a voluntary basis, varied in gender (28 male and 12 female), their cultural background (1 Belgian, 10 British, 5 Bulgarian, 1 French, 1 German, 5 Greek, 1 Indian, 2 Italian, 6 Jordanian, 1 Libyan, 2 Malaysian, 1 Nigerian, 1 Polish, and 3 Saudi Arabian), and age (18–55, mean = 25 ). None of these participants had any expertise in music.

Method. The participants were asked to freely name objects that were shown in an image stimuli, under limited response time (10 seconds) for each image. Overall, 364 taxonomical musical instruments were extracted from the MusicPinta dataset by running SPARQL queries over the triple-store hosting the dataset to get all musical instrument entities linked via rdfs:subclassOf relationship. There were 256 leaf entities and 108 category entities. For each leaf entity, we collected a representative image from the Musical Instrument Museums Online (MIMO)10

OPEN IN VIEWER

Fig. 5.

Example of accurate naming of a category following Strategy 1. The user names the category entity Flute when shown an image of the leaf entity Bansuri that belongs to the category Flute.

OPEN IN VIEWER

Fig. 6.

Example of accurate naming of a category following Strategy 2. The user names the category entity Flute when shown images of leaf entities belonging to the category Indian Bambo Flutes which is a subclass of Flute.

OPEN IN VIEWER

Fig. 7.

Example of accurate naming of a category following Strategy 2. The user names the category entity Flute when shown images of leaf entities that belong to Flute.

Each image was shown for 10 seconds on the participant’s screen, and the participant was asked to type the name of the given object (for leaf entities) or the category of objects (for category entities). The image allocation in the surveys was done randomly. Every survey had four respondents (i.e. each image was named by four different participants – overall there were 1456 total answers). Each participant was allocated to one survey (either leaf entities or category entities). Figures 5–8 show example images and participants’ answers (Fig. 5 from Strategy 1; Figs 6–8 from Strategy 2). Processing the answers, we identify two sets of human BLO DG (see [4] for detailed algorithm how the two sets were obtained).

Set1 [resulting from Strategy1]. We mark as accurate naming of a category entity (parent) when leaf entity that belongs to this category is identified. This is illustrated in the example in Fig. 5 which shows an accurate naming of Flute. The overall count for Flute will include all cases when participants named Flute while seeing any of its leaf members.

Set2 [resulting from Strategy 2]. We mark as accurate naming of a category entity when its exact name or a name of its parent or subclass member is identified. These cases are illustrated in Figs 6, 7 and 8.

OPEN IN VIEWER

Fig. 8.

Example of accurate naming of a category following Strategy 2. The user names the category entity Flute when shown images of leaf entities that belong to Woodwind which is a parent of Flute.

In each of the two sets, entities with frequency equal or above two (i.e. named by at least two different participants) were identified as human BLO DG . The union of Set1 and Set2 gives human BLO DG . In total, we identified 24 human BLO DG . The full list of human BLO DG obtained from MusicPinta is available in [1].

We used the human BLO DG to examine the performance of the KA DG metrics. For each metric, we aggregated (using union) the KA DG entities identified using the hierarchical relationships (H). We noticed that the three homogeneity metrics have the same values. Therefore, we chose one metric when reporting the results, namely Jaccard similarity.13

A cut-off threshold point for the result lists with potential KA DG entities was identified by normalizing the output values to a range between 0 and 1 from each metric and taking the mean value for the 60th percentile of the normalised lists.14

As in ontology summarisation approaches [69], a name simplicity strategy based on data graphs was applied to reduce noise when calculating key concepts (usually, basic level objects have relatively simple labels, such as chair or dog). The name simplicity approach we use is solely based on the data graph. We identify the weighted median for the length of the labels of all data graph entities v ⊆ V and filter out all entities whose label length is higher than the median. For the MusicPinta data graph, the weighted median is 1.2, and hence we only included entities which consist of one word. Table 2 illustrates precision and recall values comparing human BLO DG and KA DG derived using hierarchical and domain specific relationships. We used Precision, Recall and F scores since we are dealing with a binary classification problem where all knowledge anchors identified by our KA_DG metrics are considered of same rank. All class entities above the 60th percentile are identified as knowledge anchors of same rank (i.e. knowledge anchors above the 60th percentile are given the value of 1).

Hybridisation of Metrics. Further analysis of the False Positive (FP) and False Negative (FN) entities indicated that the metrics had different performance on different taxonomical levels in the graph. This led to the following hybridisation heuristics.

Heuristic 1: Use Jaccard metric with hierarchical relationships for the most specific categories in the graph (i.e. the categories at the bottom quartile of the taxonomical level). There were FP entities (e.g. Shawm and Oboe) returned by distinctiveness metrics using the domain-specific relationship MusicOntology:Performance because these entities are highly associated with musical performances (e.g. Shawm is linked to 99 performances and Oboe is linked to 27 performance). Such entities may not be good knowledge anchors for exploration, as their hierarchical structure is flat. The best performing metric at the specific level was Jaccard for hierarchical attributes – it excluded entities which had no (or a very small number of) hierarchical attributes.

Heuristic 2: Take the majority voting for all the other taxonomical levels. Most of the entities at the middle and top taxonomical level will be well represented in the graph hierarchy and may include domain-specific relationships. Hence, combining the values of all algorithms is sensible. Each algorithm represents a voter and provides two lists of votes, each list corresponding to hierarchical or domain-specific associated attributes ( H , D ) . At least half of the voters should vote for an entity for it to be identified in KA DG . Examples from the list of KA DG identified by applying the above hybridisation heuristics included Accordion, Guitar and Xylophone. The full KA DG list is available here [1]. Applying the hybridisation heuristics presented above improved Precision value to 0.65 ( average Precision in Table 2 = 0.59 ), Recall value to 0.68 ( average Recall in Table 2 = 0.56 ), and F score to 0.66 ( average F score in Table 2 = 0.57 ).

Examining the FP and FN entities for the hybridization algorithm, led to the following observations about the possible use of KA DG as exploration anchors.

Missing basic level entities due to unpopulated areas in the data graph. We noticed that none of the metrics picked FN entities (such as Harmonica, Banjo or Cello) that belonged to the bottom quartile of the class hierarchy and had a small number of subclasses (e.g. Harmonica, Banjo and Cello each have only one subclass and there are no domain-specific relationships with their members). Similarly, none of the metrics picked Trombone (which is false negative) – although Trombone has three subclasses, it is linked only to one performance and is not linked to any DBpedia categories. While these entities belong to the cognitive structures of humans and were therefore added in the benchmarking sets, one could doubt whether such entities would be useful exploration anchors because they are not sufficiently presented in the data graph. These entities would take the user to ’dead-ends’ with unpopulated areas which may be confusing for exploration. We therefore argue that such FN cases could be seen as ‘good misses’ of algorithms.

Selecting entities that are superordinate of basic level entities. The FP included entities, such as Tambura, Reeds, Bass, Brass, Castanets, and Woodwind, which are well presented in the graph hierarchy (e.g. Reeds has 36 subclasses linked to 60 DBpedia categories, Brass has 26 subclasses linked to 22 DBpedia categories, Woodwind has 72 subclasses linked to 82 DBpedia categories). Also, their members participate in many domain-specific relationships (e.g. Reeds members are linked to 606 performances, Brass – 33, and Woodwind – 853). Although, these entities are not close to the human cognitive structures, they provide direct links KA DG entities from the benchmarking sets (e.g. Reeds links to Accordion, Brass links to Trumpet and Woodwind links to Flute). We therefore argue that such FP cases could be seen as ‘good picks’ of the algorithms because they can provide exploration bridges to reach BLO.

The generated KA DG after applying hybridisation is used for generating data graph exploration paths, as presented in the next section.

7.1. Finding the closest KA_DG

Let v s be the first entity of an exploration path. It can be any class entity in the class hierarchy. If v s is a knowledge anchor ( v s ∈ KA DG ), then there is no need to identify the closest knowledge anchor, and the subsumption process can start immediately from v s . However, if v s is not a knowledge anchor ( v s ∉ KA DG ), then v s can be superordinate, subordinate, or sibling of one or more knowledge anchors. Hence, an automatic approach for identifying the closest knowledge anchor v KA to v s is required. For this, we calculate the semantic similarity between v s and every knowledge anchor v i ∈ KA DG . The semantic similarity between two entities in the class hierarchy is based on their distances (i.e. length of the data graph trajectory between both entities). Due to the fact that class hierarchies exist in most data graphs, we adopt the semantic similarity metric from [97] and used in [101] and apply it in the context of a data graph, where semantic similarity is based on the lengths between the entities in the class hierarchy. The semantic similarity between v s and a knowledge anchor v i is calculated as: (5) sim ( v s , v i ) : = 2 . depth ( lca ( v s , v i ) ) depth ( v s ) + depth ( v i ) where, lca ( v s , v i ) is the least common ancestor of v s and v i , and depth(v) is a function for identifying the depth of the entity v in the class hierarchy.

Algorithm 1 describes how the semantic similarity metric is applied to identify v KA . The algorithm takes a data graph, the first entity v s of an exploration path and a set of knowledge anchors KA DG as an input, and identifies the closest knowledge anchor v KA ∈ KA DG with highest semantic similarity value to v s .

OPEN IN VIEWER

Algorithm 1

Identifying closest KA DG

If the first entity v s belongs to the set of knowledge anchors v s ∈ KA DG (line 1), then the first entity v s is identified as the closest knowledge anchor v KA (line 2). However, if the first entity v s does not belong to the set of knowledge anchors (line 3), then the following steps are conducted:

The semantic similarity value is then inserted into the list S (line 13), and the knowledge anchor with the highest similarity value to the first entity v s will be identified as closest knowledge anchor v KA (line 15).

The closest knowledge anchor v KA is used to subsume new class entities and to generate transition narratives in the exploration path. Table 3, describes the different narrative types used between entities while generating an exploration path.

Algorithm 2 describes our approach for generating exploration paths using the subsumption theory for meaningful learning.

OPEN IN VIEWER

Algorithm 2

Subsumption using closest KA DG

The algorithm takes a data graph DG , the first entity v s , the closest knowledge anchor v KA , the length of an exploration path (m), and the edge label e = rdfs:subClassOf as an input, and generates an exploration path P of length m. The algorithm starts by initialising an empty exploration path P (line 1) used to store m transition narratives. Then the algorithm starts identifying the relationship type between v s and v KA . If v s is a subclass of v KA (line 2), then the following steps are conducted:

If v s is superclass of v KA (lines 12), then the transition narrative ⟨ v s , script ( N 2 ) , v KA ⟩ from v s to v KA is inserted into P (line 13) where the function script( N 2 ) retrieves the script output for narrative type N 2 from Table 3. Length m of P is decreased by one (line 14). If v s and v KA are siblings (line 15), then the transition narrative ⟨ v s , script ( N 3 ) , v KA ⟩ from v s to v KA is inserted into P (line 16) where the function script( N 3 ) retrieves the script output for narrative type N 3 from Table 3. Length m pf P is decreased by one (line 17).

After identifying the relationship between v s and v KA , the following steps are conducted:

8.1. Data graph exploration task

Designing exploration tasks for users is considered an important requirement for evaluating data exploration approaches [53]. A typical exploration task has to be generic (i.e. the scope of the task is broad and the user don’t have specific information needs), realistic (i.e. real-life task that set in a familiar situation), discovery-oriented (i.e. users travel beyond what they know), open-ended (i.e. requires a significant amount of exploration, where open-endedness relates to uncertainty over the information available, or incomplete information on the nature of the search task), and set in an unfamiliar domain for the user [53,65,94]. In this work, we follow a two-step approach (similar to [53]) to design a data exploration task for the study participants. The approach involves: (i) Designing a task template that places the participant in a familiar situation which involves exploring multiple entities in an unfamiliar domain or topic (e.g. a researcher at a university that wants to write a research paper about a new topic), and (ii) Identifying unfamiliar candidate entities (e.g. find new research topic) in the domain that could be plugged into the task template.

Our aim was to design a generic task template that encourages layman users to seek knowledge in a domain unfamiliar to them. Therefore, we designed the task template in the context of a general knowledge quiz show where layman users need to acquire as much knowledge as they can. Inspired by the task templates in [53], our task template in Table 4 was designed to suit the musical instrument domain.

The second step in designing data exploration task was to identify unfamiliar entities in the domain of this user study. For this we ran a questionnaire with users to identify the unfamiliar entities in the String Instrument and Wind Instrument class hierarchies in the MusicPinta data graph. These two class hierarchies have the richest class representation in terms of the number of classes and the hierarchy depth as discussed in Section 3.1, and have the highest number of knowledge anchors (9 anchors in the String Instrument class hierarchy and 10 anchors in the Wind Instrument class hierarchy – out of 24 anchors in MusicPinta data graph). We have extracted class entities at the bottom quartile of the two class hierarchies (note that the depth of the two class hierarchies is 7 – see Table 1, and entities of depth 6 or 7 are considered to be at the bottom quartile of the data graph). This is based on earlier Cognitive science studies acknowledging that layman users are not familiar with specific objects in a domain [85]. Overall 61 class entities from the String Instrument and Wind Instrument class hierarchies were used in the survey. The selected classes were randomised and distributed among twelve participants who are not experts in the musical instruments (the participants have limited knowledge about musical instruments and may have seen the instrument, and none of the participants had played any musical instruments.

The most unfamiliar instrument from each class hierarchy was Biwa (class hierarchy: String Instrument, origin: Japanese) and Bansuri (class hierarchy: Wind Instrument, origin: Indian).

Participants. 32 participants, including university students and professionals (24 students and 8 professionals15

Method. We ran four online surveys,16

OPEN IN VIEWER

Fig. 9.

Structure of user study to examine EC against CC in terms of knowledge utility, usability and cognitive load.

In both the strategies, the participants explored the same information including categories from a semantic data browser (i.e. participants’ explored ‘Description’, ‘Features’ and ‘Relevant information’ of musical instruments – see Figs 2, and 3). The order of EC and CC was randomised to counter balance the impact on the results. Every participant session was conducted separately and observed by the authors. All participants were asked to provide feedback before, during, and after the interaction with MusicPinta.

The different stages of the study are explained below.

Task presentation [1 min] – utilise the task template (described in Section 8.1) to present the data exploration task for the users at the beginning of their exploration session. We used the task template in Table 4.

Pre-study questionnaire [2 min] – collected information about the participants’ profiles, and their familiarity with the music domain, focusing on the two musical instrument class hierarchies which would be explored – String Instrument and Wind Instrument. The participants’ familiarity with the two class hierarchies varied from low to medium (the figures were 63% and 78% for low familiarity with String Instrument and Wind Instrument, respectively).

Graph exploration [20 min] – each user explored the two strategies where each strategy corresponds to one of the two unfamiliar instruments (Biwa or Bansuri). Figure 10 shows an example for generating an exploration path under EC for the instrument Biwa (the first entity of the exploration path) using the closest knowledge anchor Lute.

The first transition narrative in the exploration path is between the Biwa and the closest knowledge anchor Lute (using N 1 in Table 3). After that, the closest knowledge anchor Lute is used to subsume new class entities and generate transition narratives in the exploration path using the narrative types N 4 (subsume intermediate class entities between Lute and Biwa – line 9 in Algorithm 2) and N 5 (subsume subclasses of Lute other than class entities that have been subsumed using N 4  – line 23 in Algorithm 2).

OPEN IN VIEWER

Fig. 10.

Extract from the String Instrument class hierarchy in MusicPinta showing exploration path of Biwa. This path was followed in the experimental condition EC .

Table 5 lists the transition narratives that were followed in generating the exploration path for Biwa.

Table 6 shows examples of the entities that were freely visited in the control condition for Biwa.

Figure 11 shows an example for generating the exploration path under EC for the instruments Bansuri (the first entity v s in the exploration path) using the closest knowledge anchor Flute.

OPEN IN VIEWER

Fig. 11.

Extract from the Wind Instrument class hierarchy in MusicPinta showing exploration path of Bansuri. This path was followed in experimental condition EC .

The exploration path for Bansuri was generated using the closest knowledge anchor Flute and narrative types N 1 , N 4 given in Table 3. The first transition narrative is between the first entity Bansuri and the closest knowledge anchor Flute (using N 1 in Table 3). After that, the closest knowledge anchor Flute is used to subsume new class entities and to generate transition narratives in the exploration path using narrative type N 4 (subsume intermediate class entities between Flute and Bansuri). Transition narratives that were followed in generating the exploration path for Bansuri are listed in Table 7.

Table 8 shows examples of the entities that were freely visited in control condition CC for Bansuri

Both, EC and the CC had the same length ( EC had four transition narratives, and CC had four edges).17

Approximating Knowledge Utility. The participants’ knowledge was measured before and after each exploration using the three questions of the schema activation test related to the entities Biwa and Bansuri (see Section 3.2). Before exploration, none of the users were able to articulate any item linked to the two musical instruments (Biwa and Bansuri) using the three cognitive processes. The knowledge utility for the three cognitive process before and after exploration of EC and CC is shown in Fig. 12.

OPEN IN VIEWER

Fig. 12.

Knowledge utility of the two strategies ( EC and CC ) of the user cognitive processes (median of the knowledge utility of exploration for all users).

The knowledge utility of the exploration under EC in the three cognitive processes was higher than the CC ; and this difference is significant (see Table 9). The results showed that all participants were able to remember and categorise entities with EC (only 5 participants couldn’t compare new entities). Whereas not all participant could remember, categorise or compare new entities after they have finished their exploration with CC (there were 2 participants that could not remember or categorise new entities; 13 participants that could not compare between entities).

Notably, for the cognitive process categorise the bigger effect on exploration of the subsumption exploration strategy over the free exploration strategy is highly significant ( p < 0.0001 ). The difference between the median values for categorise under EC and CC was higher than remember and compare. Furthermore, we examined the knowledge utility for the three cognitive processes for each instrument in its corresponding class hierarchies, as shown in Fig. 13.

OPEN IN VIEWER

Fig. 13.

Knowledge utility of the two strategies ( EC and CC ) of the user cognitive processes (median of the knowledge utility of exploration for all users).

The knowledge utility of the exploration under EC in the three cognitive processes was higher than the effect of free exploration under CC for Biwa and was higher in the cognitive processes compare and categorise for Bansuri (see Fig. 13). This difference in EC and CC is significant except for the cognitive process compare for instrument Bansuri (see Table 10).

To further inspect what caused the low knowledge utility for the cognitive process compare for instrument Bansuri, we looked into the participants’ familiarity with the Wind Instrument class hierarchy (the class hierarchy that Bansuri belongs to) and noticed that 78% of the participants had low familiarity (i.e. participants have limited knowledge and they may have seen some instruments) with Wind Instrument, whereas 65% of the participants had low familiarity with the String Instrument class hierarchy. Being more familiar with the String Instrument class hierarchy than the Wind Instrument class hierarchy, participants may have found it easier to name entities for comparison. Also, entities in the String Instrument class hierarchy are associated with more DBpedia categories compared to entities in the Wind Instrument class hierarchy (String Instrument has 255 and Wind Instrument has 161 DBpedia categories).

User Exploration Experience. After each exploration strategy, the participants’ feedback on the exploration experience was collected including exploration usability and exploration complexity, adapted from NASA-TLX [42] (Table 11). Furthermore, the participants were asked to think aloud and notes of all comments were kept.

Figures 14 and 15 summarise the users’ feedback. As shown in Fig. 14, the exploration experience with EC was the most informative (all 32 participants identified their exploration experience with the exploration paths under EC as informative, whereas 20 participants indicated their exploration with CC as informative). The participants also found their exploration under EC to be slightly more interesting and enjoyable than CC . Furthermore, the participants found the exploration paths under EC to be the least boring and least confusing – only 3% (one participant) and 16% (four participants) of the participants founded their exploration with EC to be boring or confusing, respectively. For instance, one participant indicated “Narratives in paths allows me to explore entities in a hierarchical fashion, and I would like to freely explore other types of relationships”. Another participant indicated his exploration experience with EC as confusing: “I saw the same instruments several times during my exploration”.

OPEN IN VIEWER

Fig. 14.

Users’ exploration experience of the two exploration strategies ( EC and CC ). Values show number of user paths rated with the corresponding characteristics.

OPEN IN VIEWER

Fig. 15.

Users’ subjective perception of the two exploration strategies ( EC and CC ), based on an adapted NASA-TLX questionnaire [42] (median values for all users in the range 1–10).

The effect of the exploration path under EC on the subjective processes knowledge expansion and performance was higher than the effect of the free exploration strategy; and this difference was significant (see Table 12 and Fig. 15).

Notably, for the subjective process knowledge expansion the bigger effect on exploration of EC over CC is highly significant ( p < 0.0001 ).

9.1. Benefit of the exploration approach

Overall, the evaluation results have supported our hypotheses, which were set out in Section 8.

H1:When following the subsumption exploration paths, the users expanded their domain knowledge. When users followed the experimental condition, i.e. the paths generated by the subsumption algorithm using knowledge anchors, all of them expanded their domain knowledge. All participants indicated that their exploration in the experimental condition was informative (in other words, they felt that while following the path they were able to find useful information); in contrast, only 62% of the participants founded their free exploration trajectories to be informative.

H2:The expansion in the users’ knowledge when following the subsumption exploration paths was higher than knowledge expansion when following free exploration. The participants were able to remember, categorise and compare significantly more entities. The results also showed that the cognitive process categorise had most effect on expanding the participants’ knowledge. This was caused because: (i) the subsumption hierarchical relationship (rdfs:subclassOf) was used to create the narrative scripts between entities of the generated exploration paths, which helped the users to categorise new entities at different levels of abstraction at their cognitive structures; and (ii) the subsumption process uses knowledge anchors to subsume and learn new sub-categories similarly to the way humans learn new concepts.

H3:The usability when the subsumption exploration paths were followed was higher than the free exploration cases. The results showed that participants found the generated exploration paths to be more enjoyable and less confusing than free exploration, and their assessment of performance was higher. One participant thought that the experience with hierarchical narrative scrips was boring; and suggested that the system should diversify the types of narratives used between entities in the exploration path.

9.2. Identifying knowledge anchors in data graphs

To identify knowledge anchors in a data graph, we have utilised Rosch’s definitions of basic level objects. This required operationalising cue validity, using two groups of metrics: distinctiveness (to identify the most differentiated categories whose attributes are shared amongst the category members but not with members of other categories), and homogeneity (to identify categories whose members share many attributes).

We have adapted existing methods in FCA to define metrics for KA DG , following Rosch’s definitions of BLO. The algorithms have been applied over two data graphs – in music (presented here) and in careers (presented in [4]); both data graphs had different size and hierarchy structure. Although this paper focuses only on the music domain (so that we can show a holistic approach illustrated with a concrete application), in the discussion below we identify key features of the algorithms which have been confirmed in broader evaluation (see [4] for further detail).

Hybridisation. The analysis indicated that hybridisation of the metrics notably improved performance. The same was observed in the careers domain ([4]). Appropriate hybridisation heuristics for the upper level of the data graph is to combine the KA DG metrics using majority voting. The hybridisation heuristics for the bottom level of the hierarchy are dependent on the domain-specific relationships in the data graph. Hence, to derive appropriate hybridisation heuristics that give good performance for categories at the bottom level, further experimentation will be required. This will include comparing the KA DG derived using the various domain-specific relationships against human BLO DG .

Cut-off point in the evaluation. An important step in the evaluation is to identify a suitable cut-off point for the KA DG metrics. In the current implementation, this was done through experimentation – the best performance was achieved when using the 60th percentile. The same percentile was identified as best for the career domain (see [4]). We expect that when applied to a range of data graphs, the 60th percentile will give reasonable performance. However, the best cut-off point for a specific data graph would require experimentation comparing different percentiles.

Sensitivity to data graph structure. The output of the KA DG algorithms is sensitive to the data graph structure in terms of the richness of the class entities and the hierarchy depth. Specifically, the algorithms tend to pick more anchoring entities when a data graph has many classes and high depth. For instance, the algorithms identified 9 anchors in the String Instrument class hierarchy and 10 anchors in the Wind Instrument class hierarchy – out of 24 anchors (String Instrument and Wind Instrument are the richest class hierarchies in MusicPinta – see Table 1). The algorithms did not produce any anchor in the Electronic Instrument class hierarchy (only 15 classes with a depth of one). The same was observed in the career domain [4]. It should be noted that KA DG metrics may not produce KA DG in shallow class hierarchies (depth 1 or 2).

Possible high number of KA DG . Applying the KA DG algorithms over large data graphs may produce high number of KA DG . Further filtering would be required to reduce the number of KA DG . One possible way to address this is to use crowdsourcing – showing all derived knowledge anchors and asking a large number of users (crowd) to identify the most familiar entities, which will then form the refined KA DG list.

9.3. Generating exploration paths

We have developed a novel computational approach to generate exploration paths, which is the first attempt to address users’ domain knowledge expansion during exploration. We have provided an original way to link learning and exploration by operationalising Ausubel’s subsumption theory for meaningful learning. Two algorithms have been formally defined: (i) identifying the closest knowledge anchor; and (ii) generating exploration paths and transition narratives.

Several possible knowledge anchors. It is possible that several knowledge anchors in a data graph have the same semantic similarity value with the first entity (the entity selected as a starting point for the path). For example, there were two knowledge anchors (Flute and Reeds) with the same semantic similarity value with the first entity Bansuri. One way to address this is to consider the density of each knowledge anchor entities (e.g. using degree centrality in the graph). Then, select knowledge anchor with the highest density, as it will include many subclass members to subsume while generating the exploration path.

Transition to the closest knowledge anchor. In some cases, the semantic similarity metric can identify closest knowledge anchors which are not superclass (i.e. N 1 in Table 3), subclass (i.e. N 2 in Table 3) nor sibling (i.e. N 3 in Table 3) to the first entity, which means that the closest knowledge anchor cannot be reached directly from the first entity using one of the suggested narrative transitions. For instance, although the anchors Flute and Reeds have the same semantic similarity value with the first entity Bansuri, Flute is a superclass of Bansuri that can be reached directly using the narrative type ( N 1 in Table 3), whereas Reeds can’t be reached directly from Bansuri. Our solution to address this issue was to apply the semantic similarity measure proposed in [97] to find knowledge anchors which could be reached directly from the first entity. Future work can consider other semantic similarity algorithms, such as the measure proposed in [55] where calculating semantic similarity between two entities is based on the shortest path and maximum depth of the class hierarchy, or the semantic similarity model presented in [57] where each class entity is given a probability value used to calculate the semantic similarity between two entities. Another solution for reaching the closes knowledge anchor is to add a narrative type in Table 3 that indicates that the first entity and the closest knowledge anchor simply belong to the same domain but there is no direct trajectory between them.

Exploration path length. The path generation algorithm uses a knowledge anchor to subsume subordinate entities (i.e. subclasses of the closest knowledge anchor) while generating transition narratives of a pre-defined length m (given as input to the algorithm). The algorithm is dependent on the subclasses of the selected knowledge anchor, and it may not always be possible to generate m transition narratives in the exploration path. Our implementation uses only the knowledge anchor, and can result in paths whose length of less than m. Another way to address this would be to continue the path by selecting other knowledge anchors. It is also possible to use superordinate categories to the knowledge anchor to extend an exploration path. This will be suitable for cases when the user has gained knowledge at the subordinate level and is ready to generalise to a more abstract level. In such cases, a user model will be required.

9.4. Generality and further applications

The proposed exploration approach includes formal definitions for the algorithms used in both parts – identifying KA DG and generating a path and transition narratives. Both parts are generic and can be applied over different data graphs and adopted in any domain represented with a data graph. The algorithms will perform well when the taxonomy of the data graph has depth higher than 2.

Applications of knowledge anchors. The formal description of the KA DG provides a generic solution for identifying familiar entities over data graphs, which make such entities useful in different ways. We have shown here how KA DG enable operationalising the subsumption theory for meaningful learning to generate exploration paths for knowledge expansion. There are other possible applications beyond data graph exploration. For example, our approach for identifying KA DG can be applied to ontology summarisation where KA DG allow capturing layman users’ view of the domain. Furthermore, KA DG can be applied to solve the key problem of ‘cold start’ in personalisation and adaptation. One of the popular choices for addressing the cold start problem is a dialogue system with the user. The data graphs can provide a large knowledge pool to implement such probing dialogue, however, one needs to select entities from the vast amount of possibilities for probing to avoid too long interactions with the user. KA DG can be such entities, e.g. we have proposed an approach to detect user domain familiarity by exploiting KA DG for probing interactions over data graph concepts [2].

Applications of exploration paths. The subsumption algorithms for generating an exploration path are generic and can be applied in different domains that are represented as data graphs. This opens a broad spectrum of applications where users not familiar with the domain explore semantic data, such as: (i) researching a new domain (e.g. digital libraries); (ii) exploring information content in a domain where the user is not an expert (e.g. cultural heritage or news); (iii) browsing through large graphs with many options which the user may not be familiar with (e.g. job opportunities, health information, travel information); (iv) exploring content for learning (e.g. videos or presentations).