Extracting entity-specific substructures for RDF graph embeddings

Abstract

Knowledge Graphs (KGs) have become useful sources of structured data for information retrieval and data analytics tasks. Enabling complex analytics, however, requires entities in KGs to be represented in a way that is suitable for Machine Learning tasks. Several approaches have been recently proposed for obtaining vector representations of KGs based on identifying and extracting relevant graph substructures using both uniform and biased random walks. However, such approaches lead to representations comprising mostly popular, instead of relevant, entities in the KG. In KGs, in which different types of entities often exist (such as in Linked Open Data), a given target entity may have its own distinct set of most relevant nodes and edges. We propose specificity as an accurate measure of identifying most relevant, entity-specific, nodes and edges. We develop a scalable method based on bidirectional random walks to compute specificity. Our experimental evaluation results show that specificity-based biased random walks extract more meaningful (in terms of size and relevance) substructures compared to the state-of-the-art and the graph embedding learned from the extracted substructures perform well against existing methods in common data mining tasks.

1. Introduction

Knowledge Graphs (KGs), i.e., graph-structured knowledge bases, store information as entities and the relationships between them, often following some schema or ontology [3]. With the emergence of Linked Open Data [4], DBpedia [2], and Google Knowledge Graph,1

¹

https://www.blog.google/products/search/introducing-knowledge-graph-things-not/

large-scale KGs have drawn much attention and have become important data sources for many data mining and other knowledge discovery tasks [9,16,25,32,33,46,52] As such algorithms work with the propositional representation of data (i.e., feature vectors) [35], several adaptations of language modeling approaches such as word2vec [24] and GloVe [30] have been proposed for generating graph embedding for entities in a KG. As a first step for such approaches, a representative subgraph for each target entity in the KG must be acquired. Each entity (represented by a node) in a heterogeneous KG is surrounded by other entities (or nodes) connected by directed labeled edges. For a node representing a film, there can be a labeled edge director connecting it to a node representing the director of the film. Another labeled edge releaseYear may exist that connects the film to an integer literal, also represented by a node in the KG. If we want to extract a subgraph representing the film, ideally such relevant information (labeled edges and nodes) must be a part of the extracted subgraph. On the other hand, relationships linked to, say, the Director such as birthYear or deathYear, which are at two hops from a film, e.g. $\mathit{Batman}\text{\_}1989\stackrel{\mathit{director}}{\to }\mathit{Tim}\text{\_}\mathit{Burton}\stackrel{\mathit{birthYear}}{\to }1958$ , may not be useful or relevant for representing a film. Therefore, in order to extract a useful representation (as a subgraph) of a given entity, we first need to automatically determine the most relevant edges and nodes in its neighborhood. An extracted representation of any target entity2 ²

Since entities are represented as nodes in a KG; we use entity and node interchangeably throughout the text.

in a KG can only be considered representative if it includes only the most relevant nodes and edge w.r.t. the target entity. To accomplish this task approaches based on biased random walks [6,13] have been proposed. Such approaches use weighting schemes to make a particular set of edges and nodes more likely to be included in the extracted subgraphs than others. However, weighting schemes based on metrics such as frequency or PageRank [6,48] tend to favor popular (or densely connected) nodes in the representative subgraphs of target entities at the expense of semantically more relevant nodes and edges.

In this paper, we focus on RDF3 ³

https://www.w3.org/TR/rdf-concepts/

KGs which are encoded using the Resource Description Framework (RDF) syntax and constitute Linked Open Data [18,27]. We assert that the representative subgraphs of different types of entities (e.g., book, film, drug, athlete) in RDF KGs may comprise distinct sets of relationships. Our objective is to automatically identify such relationships and use them to extract entity-specific representations. This is in contrast to the scenario where extracted representations are KG-specific because of the inclusion of popular nodes and edges, irrespective of their semantic relevance to the target entities.

The main contributions of this paper are as follows:

• We propose Specificity as an accurate measure for assigning weights to those semantic relationships which constitute the most intuitively relevant representations for a given set or type of entities.

• We provide a scalable method of computing specificity for semantic relationships of any depth in large-scale KGs.

• We show that specificity-based biased random walks enable more compact extraction of relevant subgraphs for target entities in a KG as compared to the state-of-the-art.

To demonstrate the usefulness of our specificity-based approach for real-world applications, we train the neural language model (Skip-Gram [23]) for generating graph embedding from the extracted subgraphs and use the generated embeddings for the tasks of entity recommendation, regression, and classification for select entities in DBpedia. This paper considerably extends [43], in which we introduced the metric of specificity for the first time. We provide additional experiments to show that the vector embeddings can not only be used for entity recommendation but also regression and classification tasks. We also propose a variation of specificity called ${\mathit{Specificity}}^{\mathit{H}}$ which takes into account the hierarchy of classes in the schema ontology associated with a KG, discussed in Section 4.2.

The rest of this paper is structured as follows. In Section 2, we provide a brief overview of related work. In Section 3, we provide the necessary background. In Section 4 we motivate and introduce the concept of specificity. In Section 5, we present a scalable method for computing specificity. In Section 6, we present results highlighting beneficial characteristics of specificity on DBpedia. In Section 7 we conclude with a summary and an outlook on future work.

Fig. 1.

Linked open data [source: http://lod-cloud.net/].

2. Related work

Linked Open Data (LOD) [51] is a massive KG shown in Fig. 1 where each node itself is a Knowledge Graph. Each of these individual KGs comes from semantically annotating and integrating unstructured data and publishing as structured data on the web using the principles of Linked Data or Semantic Web [15,29,39,42]. LOD cloud currently comprise 1205 KGs.4

⁴

Source: http://lod-cloud.net/.

Few of the KGs part of LOD are Wikidata,5 ⁵

https://www.wikidata.org/wiki/Wikidata:Main_Page

Freebase,6 ⁶

https://developers.google.com/freebase/

and DBpedia7 ⁷

https://wiki.dbpedia.org/

[10 ,17].

Due to its open availability, heterogeneity, and cross-domain nature, LOD is increasingly becoming a valuable source of information in many data mining tasks. However, most data mining algorithms work with a propositional feature vector representation of the data [35]. Recently, graph embedding techniques have become a popular area of interest in the research community. Embeddings map entire graph or individual nodes into low dimensional vector space, preserving as much information as possible related to its neighborhood [12,34,45].

Numerous techniques have been proposed for generating appropriate representations of KGs for knowledge discovery tasks. Graph kernel-based approaches simultaneously transverse the neighborhoods of a pair of entities in the graph to compute kernel functions based on metrics such as the number of common substructures (e.g., paths or trees) [8,22] or graphlets [44,50]. Neural language models such as word2vec [24] and GloVe [30], proposed initially for generating word embedding, have been adapted for KGs [7,13,35]. Deep Graph Kernel [50] identifies graph substructures (graphlets) and uses neural language models to compute a similarity matrix between identified substructures. For large scale KGs, embedding techniques based on random walks have been proposed in the literature. DeepWalk [31] learns graph embedding for nodes in the graph using neural language models while generating truncated uniform random walks. node2vec [13] is a more generic approach than DeepWalk and uses 2nd order biased random walks for generating graph embedding, preserving roles and community memberships of nodes. RDF2Vec [35], an extension of DeepWalk and Deep Graph Kernel, uses BFS-based random walks for extracting subgraphs from RDF graphs, which are converted into feature vectors using word2vec [24]. Random walk-based approaches such as RDF2Vec have been shown to outperform graph kernel-based approaches in terms of scalability and their suitability for ML tasks for large-scale KGs [12,35]. The main limitation of approaches using uniform (or unbiased) random walks is the lack of control over the explored neighborhood which can lead to the inclusion of less relevant nodes in identified subgraphs of target entities. To address this challenge biased random walks based approaches have been recently proposed [2,6,43]. Such approaches use different weighting schemes for nodes and edges. The weights create the bias by making specific nodes or edges more likely to be visited during random walks. The work closest to ours is biased RDF2Vec approach [6] which uses frequency-, degree-, and PageRank-based metrics for weighting schemes. Our proposed approach also uses biased random walks to extract entity representations. However, unlike [6], we use our proposed metric of specificity as an edge- and path-weighting scheme for biased random walks for identifying most relevant subgraphs for extracting entity representations in the KGs.

Semantic similarity and relatedness between two entities have been relatively well explored [1,11,19,29]. Searching for similar or related entities given a search query is a common task in the field of Information Retrieval [14,21,27]. To facilitate the search for similar entities the notion of similarity and the set of attributes used for its computation must first be defined. Semantic similarity and relatedness are often used interchangeably in literature [1,29,41,47], where the similarity between two entities is sometimes computed based on common paths between them. This definition allows computation of similarity between any two given entities, including entities of different types. For example, Kobe Bryant and Kareem Abdul-Jabbar (athletes) are each related to LA Lakers (team) based on path-based similarity. The other kind of similarity is between Kobe Bryant and Kareem Abdul-Jabbar who are entities of the same type, i.e., athletes. Both are athletes, basketball players, and have played for the same team. These attributes in KG, e.g. DBpedia, are represented through semantic relationships rdf:type and dct:subject. For this paper, our objective is to automatically identify such semantic relationships that constitute the representative neighborhoods of entities of the same given type. Therefore, we limit the computation of similarity to be between two entities of the same type.

3. Preliminaries

An RDF graph is represented by a knowledge base of triples [49]. A triple consists of three parts: ⟨subject (s), predicate (p), object (o)⟩.

Definition 1 (RDF Graphs).

Assuming that there is a set U of Uniform Resource Identifiers (URIs), a set B of blank nodes, a set L of literals, a set O of object properties, and a set D of datatype properties, an RDF graph G can be represented as a set of triples such that: $$\begin{array}{ll}\hfill \mathit{G}=& \{⟨\mathit{s}\mathrm{,}\mathit{p}\mathrm{,}\mathit{o}⟩|\mathit{s}\in \mathrm{(}\mathit{U}\cup \mathit{B}\mathrm{)}\mathrm{,}\mathit{p}\in \mathrm{(}\mathit{D}\cup \mathit{O}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{o}\in \\ \hfill & \mathrm{(}\mathit{U}\cup \mathit{B}\mathrm{)}\mathrm{,}\text{if }\mathit{p}\in \mathit{O}\mathrm{)}\wedge \mathrm{(}\mathit{o}\in \mathit{L}\mathrm{,}\text{if }\mathit{p}\in \mathit{D}\mathrm{)}\mathrm{,}\\ \text{(1)}& \hfill & \mathrm{(}\mathrm{(}\mathit{D}\cup \mathit{O}\mathrm{)}\subseteq \mathit{U}\mathrm{)}\}\end{array}$$

We can also represent an RDF graph G as $\mathit{G}=\{\mathit{V}\mathrm{,}\mathit{E}\}$ such that $\mathit{V}\in \mathrm{(}\mathit{U}\cup \mathit{B}\cup \mathit{L}\mathrm{)}$ and $\mathit{E}\in \mathrm{(}\mathit{O}\cup \mathit{D}\mathrm{)}$ , where E is a set of directed labeled edges. In an RDF graph, URIs are used as location-independent addresses of entities (both nodes and properties), whereas blank nodes are assigned internal IDs. Literals can have any values conforming to the XML schema definitions. Thus, (1) signifies that any entity with a URI can be subject, predicate, or object. In practice, only entities with URIs defined as Object or Datatype properties are used predicates. However, these properties can also be subjects or objects in other triples, which is an interesting feature of an RDF graph that an edge can be between two edges which makes it different from the traditional definition of a graph. Blanks nodes can either be subject or object, whereas literals can only be objects. An RDF graph is a set of all such RDF triples [26,49]. Ontologies are a key concept in the domain of Semantic Web. An ontology is a formal conceptualization of a particular domain containing a hierarchy of concepts (or classes), their relationships (object properties) and attributes (data properties). Such semantic relationships are the fundamental aspect of knowledge representation in Semantic Web as they provide information about how entities are linked together. Thus, the ontologies are used to enforce a schema over RDF instance data [38].

Definition 2 (Semantic relationship).

A semantic relationship in an RDF graph can be defined as $⟨\mathit{s}\mathrm{,}{\mathit{p}}^{\mathit{d}}\mathrm{,}\mathit{o}⟩$ where ${\mathit{p}}^{\mathit{d}}$ represents a path comprising d successive predicates and $\mathit{d}-1$ intermediate nodes between s and o. When $\mathit{d}=1$ , $⟨\mathit{s}\mathrm{,}{\mathit{p}}^1\mathrm{,}\mathit{o}⟩$ becomes equivalent to a single triple $⟨\mathit{s}\mathrm{,}\mathit{p}\mathrm{,}\mathit{o}⟩$ , where ${\mathit{p}}^1$ or p represents a single predicate or edge between two nodes s and o.

For this paper, we define semantic relationship ${\mathit{p}}^{\mathit{d}}$ of depth or length d, as a template for a path (or a walk) in G, that comprises of d successive predicates ${\mathit{p}}_1\mathrm{,}{\mathit{p}}_2\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{d}}$ . Thus, $⟨\mathit{s}\mathrm{,}{\mathit{p}}^{\mathit{d}}\mathrm{,}\mathit{o}⟩$ represents all paths (or walks) between any two entities s and o that traverse through $\mathit{d}-1$ intermediate nodes, using the same d successive predicates that constitute ${\mathit{p}}^{\mathit{d}}$ . To understand the difference between a triple, a path, and a template, assume that an RDF KG consists of only the following four triples: $⟨{\mathit{s}}_1\mathrm{,}\mathit{a}\mathrm{,}\mathit{x}⟩$ , $⟨\mathit{x}\mathrm{,}\mathit{b}\mathrm{,}{\mathit{o}}_1⟩$ , $⟨{\mathit{s}}_2\mathrm{,}\mathit{a}\mathrm{,}\mathit{y}⟩$ , and $⟨\mathit{y}\mathrm{,}\mathit{b}\mathrm{,}{\mathit{o}}_2⟩$ . $⟨{\mathit{s}}_1\mathrm{,}\mathit{a}\mathrm{,}\mathit{x}⟩$ and $⟨\mathit{x}\mathrm{,}\mathit{b}\mathrm{,}{\mathit{o}}_1⟩$ constitute a complex relationship between ${\mathit{s}}_1$ and ${\mathit{o}}_1$ . These two triples together are an example of a semantic relationship of form ${\mathit{p}}^2$ which consists of two successive predicates a and b and one intermediate node x. If we treat a, b as a template of a path, then in this KG there are two instances of this template: the semantic relationship between ${\mathit{s}}_1$ and ${\mathit{o}}_1$ (first and second triples) and the semantic relationship between ${\mathit{s}}_2$ and ${\mathit{o}}_2$ (third and fourth triples). This also means that for an arbitrary s and o, $|⟨\mathit{s}\mathrm{,}{\mathit{p}}^2\mathrm{,}\mathit{o}⟩|=2$ , where ${\mathit{p}}^2=\mathit{a}\mathrm{,}\mathit{b}$ . We will formulate the expression for specificity using this notation in Section 4.

Definition 3 (Graph walk).

Given a graph $\mathit{G}=\{\mathit{V}\mathrm{,}\mathit{E}\}$ , a single graph walk of depth d starting from a node ${\mathit{v}}_0\in \mathit{V}$ comprises a sequence of d edges (predicates) and $\mathit{d}+1$ nodes: ${\mathit{v}}_0\stackrel{{\mathit{e}}_1}{\to }{\mathit{v}}_1\stackrel{{\mathit{e}}_2}{\to }{\mathit{v}}_2\stackrel{{\mathit{e}}_3}{\to }\cdots \stackrel{{\mathit{e}}_{\mathit{d}}}{\to }{\mathit{v}}_{\mathit{d}}$ .

Random graph walks provide a scalable method of extracting entity representations from large scale KGs [13]. Starting from a node ${\mathit{v}}_0\in \mathit{V}$ , in the first iteration, a set of randomly selected outgoing edges ${\mathit{E}}_1$ is explored to get a set of nodes ${\mathit{V}}_1$ at depth 1. In the second iteration, from every $\mathit{v}\in {\mathit{V}}_1$ , outgoing edges are randomly selected for exploring the next set of nodes at depth 2. This is repeated until a set of nodes at depth d is explored. The generated random walks are the union of explored triples during each of the d iterations. This simple scheme of random walks resembles a randomized breadth-first search. In literature, both breadth-first and depth-first search strategies and interpolation between the two have been proposed for extracting entity representations from large-scale KGs [13,31,35].

Definition 4 (Representative subgraph).

The representative subgraph (neighborhood) of an entity or a node v is the set of other nodes S in the graph that represent the most relevant information related to v. The edges or paths that link v to every $\mathit{s}\in \mathit{S}$ are also part of the representative subgraph.

Using our running example from Section 1, the representative subgraph of a film may contain depth-1 edges such as director, producer that link it to nodes representing its director(s) and producer(s). Some examples of depth-2 relationships are $\mathit{Film}\stackrel{\mathit{basedOn}}{\to }\mathit{Book}\stackrel{\mathit{writtenBy}}{\to }\mathit{Author}$ and $\mathit{Film}\stackrel{\mathit{director}}{\to }\mathit{Director}\stackrel{\mathit{knownFor}}{\to }\mathit{Style}$ . On the other hand, our intuition suggests that semantic relationships such as $\mathit{Film}\stackrel{\mathit{director}}{\to }\mathit{Director}\stackrel{\mathit{birthYear}}{\to }\mathit{Year}$ is not as relevant to represent a film and hence must not be part of the representative subgraph.

4. Specificity: An intuitive relevance metric

In this section, we introduce and motivate the use of specificity as a novel metric for quantifying relevance.

Fig. 2.

Random walks from node Batman (1989).

4.1. Specificity

Consider the example shown in Fig. 2. Starting from the entity Batman (1989) in DBpedia, a random walk explores the three shown semantic relationships (descriptive names used for brevity instead of actual DBpedia URIs). Our intuition suggests that the style of a director (represented by Gothic Films) is more relevant to a film than his year and place of birth. Frequency-, degree-, or PageRank-based metrics of assigning relevance may assign higher scores to nodes representing broader categories or locations. For example, PageRank scores (non-normalized) computed for DBpedia entities Gothic Films, 1958-births, and Burbank, CA are 0.586402, 161.258, and 57.1176 respectively (calculated based on [48]). PageRank-based biased random walks may include these popular nodes and exclude intuitively more relevant information related to the target entity. Our objective is to develop a metric that assigns a higher score to more relevant nodes and edges in such a way that the node Gothic Films becomes more likely to be captured for Batman (1989) than 1958 births and Burbank, CA. This way, the proposed metric captures our intuition behind identifying more relevant information in terms of its specificity to the target entity.

Fig. 3.

Illustration of specificity.

To quantify this relevance we determine if Gothic Films represents information that is specific to Batman (1989). We trace all paths of depth d reaching Gothic Films and compute the ratio of the number of those paths that originate from Batman (1989) to the number of all traced paths. This gives specificity of Gothic Films to Batman (1989) as a score between 0.0–1.0. A specificity score of 1.0 means that all paths of depth d reaching Gothic Films have originated from Batman (1989). For $\mathit{G}=\{\mathit{V}\mathrm{,}\mathit{E}\}$ , this node-to-node specificity of a node ${\mathit{n}}_1$ to ${\mathit{n}}_2$ , such that ${\mathit{n}}_1\in \mathit{V}$ , ${\mathit{n}}_2\in \mathit{V}$ and ${\mathit{p}}^{\mathit{d}}$ being any arbitrary path, can be defined as: $$\begin{array}{ll}\hfill & \mathit{Specificity}\mathrm{(}{\mathit{n}}_1\mathrm{,}{\mathit{n}}_2\mathrm{)}\\ \text{(2)}& \hfill & ={\displaystyle \frac{|⟨{\mathit{n}}_2\mathrm{,}{\mathit{p}}^{\mathit{d}}\mathrm{,}{\mathit{n}}_1⟩\in \mathit{G}|}{|⟨\mathit{v}\mathrm{,}{\mathit{p}}^{\mathit{d}}\mathrm{,}{\mathit{n}}_1⟩\in \mathit{G}:\mathit{v}\in \mathit{V}|}}\end{array}$$ Computing specificity between every pair of nodes in a large scale KG is impractical. Instead of defining specificity as a metric of relevance between each pair of entities (or nodes), we make two simplifying assumptions. First, we assert that each class or type of entities (e.g., films, books, athletes, politicians) has a distinct set of characteristic semantic relationships. This enables us to compute specificity as a metric of relevance of a node (Gothic Films) to a class or type of entities (Film), instead of every instance of that class (Batman (1989)). Second, we measure the specificity of a semantic relationship (director, knownFor), instead of an entity (Gothic Films), to the class of target entities. Here, we are assuming that if the majority of the entities (nodes) reachable via a given semantic relationship represents entity-specific information, we consider that semantic relationship to be highly specific to the given class of target entities. From our example, this means that instead of measuring specificity of Gothic Films to Batman (1989), we measure specificity of semantic relationship director, knownFor to the class or entity type Film. Based on these assumptions we redefine specificity as

Definition 5 (Specificity).

Given an RDF graph $\mathit{G}=\{\mathit{V}\mathrm{,}\mathit{E}\}$ , a semantic relationship ${\mathit{p}}^{\mathit{d}}$ of depth d, and a set $\mathit{S}\subseteq \mathit{V}$ of all entities s of type t, let ${\mathit{V}}_{\mathit{S}\mathrm{,}{\mathit{p}}^{\mathit{d}}}\subseteq \mathit{V}$ be the set of all nodes reachable from S via ${\mathit{p}}^{\mathit{d}}$ . We define the specificity of ${\mathit{p}}^{\mathit{d}}$ to S as $$\begin{array}{}\text{(3)}& \hfill \begin{array}{cc}\hfill & \mathit{Specificity}\mathrm{(}{\mathit{p}}^{\mathit{d}}\mathrm{,}\mathit{S}\mathrm{)}\hfill \\ \hfill & ={\displaystyle \frac{1}{|{\mathit{V}}_{\mathit{S}\mathrm{,}{\mathit{p}}^{\mathit{d}}}|}}{\displaystyle \sum }_{\mathit{k}\in {\mathit{V}}_{\mathit{S}\mathrm{,}{\mathit{p}}^{\mathit{d}}}}{\displaystyle \frac{|⟨\mathit{s}\mathrm{,}{\mathit{q}}^{\mathit{d}}\mathrm{,}\mathit{k}⟩\in \mathit{G}:\mathit{s}\in \mathit{S}|}{|⟨\mathit{v}\mathrm{,}{\mathit{q}}^{\mathit{d}}\mathrm{,}\mathit{k}⟩\in \mathit{G}:\mathit{v}\in \mathit{V}|}}\hfill \end{array}& \end{array}$$ where ${\mathit{q}}^{\mathit{d}}$ represents any arbitrary semantic relationship of length d. Figure 3 provides visual representation of Equation (3). S is a set of all nodes with a given type t and ${\mathit{S}}^{\prime }=\mathit{V}-\mathit{S}$ . S and ${\mathit{V}}_{\mathit{S}\mathrm{,}{\mathit{p}}^{\mathit{d}}}$ are shown as disjoint sets only for illustrative purposes. $\mathit{S}\cap {\mathit{V}}_{\mathit{S}\mathrm{,}{\mathit{p}}^{\mathit{d}}}\ne \varnothing$ when ${\mathit{p}}^{\mathit{d}}$ creates a loop or when for $\mathit{d}=1$ is a self-property.

4.2. ${\mathit{Specificity}}^{\mathit{H}}$ : Incorporating hierarchy of classes into specificity computations

We also present an extension of specificity which takes into account the class hierarchy of the schema ontology of the KG for its computation. In Equation (3), the numerator only counts those semantic relationships that originate from $\mathit{s}\in \mathit{S}$ . This definition is rigid because a given semantic relationship can be specific to multiple classes of entities.

In other words, certain semantic relationships can apply to a broader class and by extension to multiple of its subclasses. When computing specificity of a given semantic relationship to instances of one of these subclasses, e.g., Film, the specificity score may get penalized due to the relevance of the semantic relationships to the other subclasses such as TelevisionShow. To rectify this and make the specificity computations more flexible, we leverage the hierarchical relationships represented by the schema ontology. One of the most common relationships in an ontology is hyponymy, also called is-a relationship [5,37]. Hyponymy represents the relationship between hypernym (the broader category) and hyponyms (more specific categories). Figure 4 shows a subset of the hierarchical structure of DBpedia ontology. Film, MusicalWork, WrittenWork are hyponyms to the hypernym Work and co-hyponyms of each other. Assume that the class hierarchy in the schema ontology of the KG is structured as an n-ary tree, i.e., a class can have more than one subclasses but not more than one superclass. Moreover, there is only one class that has no superclass which is the root of the entire class hierarchy.

Fig. 4.

A subset of DBpedia class hierarchy.

Let the given entity type t be at height (or depth) h from the root such that t and root can be labeled as ${\mathit{C}}_0$ and ${\mathit{C}}_{\mathit{h}}$ respectively, which results in a hierarchy of classes ${\mathit{C}}_0\subseteq {\mathit{C}}_1\subseteq \cdots \subseteq {\mathit{C}}_{\mathit{h}}$ . Subclasses of ${\mathit{C}}_1$ are co-hyponyms of ${\mathit{C}}_0$ . Our objective is to include the instances of hypernyms of entity type t ( ${\mathit{C}}_0$ ) in the computation of specificity. In Equation (3), we only consider $\mathit{s}\in \mathit{S}$ , all of which are of type t (or instances of class t). We add a term to the numerator to include instances of hypernyms of t in the computation of specificity as follows: $$\begin{array}{ll}\hfill & \mathit{Specificity}\mathrm{(}{\mathit{p}}^{\mathit{d}}\mathrm{,}\mathit{S}\mathrm{)}\\ \hfill & ={\displaystyle \frac{1}{|{\mathit{V}}_{\mathit{S}\mathrm{,}{\mathit{p}}^{\mathit{d}}}|}}{\displaystyle \sum }_{\mathit{k}\in {\mathit{V}}_{\mathit{S}\mathrm{,}{\mathit{p}}^{\mathit{d}}}}{\displaystyle \frac{1}{|⟨\mathit{v}\mathrm{,}{\mathit{q}}^{\mathit{d}}\mathrm{,}\mathit{k}⟩\in \mathit{G}:\forall \mathit{v}\in \mathit{V}|}}\\ \hfill & \times \mathrm{\left(}{\displaystyle \sum }_{\mathit{j}=0}^{\mathit{h}}{\mathit{\beta }}^{\mathit{j}}\right|⟨{\mathit{v}}_{\mathit{j}}\mathrm{,}{\mathit{q}}^{\mathit{d}}\mathrm{,}\mathit{k}⟩\in \mathit{G}:\\ \text{(4)}& \hfill & \forall {\mathit{v}}_{\mathit{j}}\in \mathit{V}\wedge \mathit{type}\mathrm{(}{\mathit{v}}_{\mathit{j}}\mathrm{)}={\mathit{C}}_{\mathit{j}}\left|\mathrm{\right)}\end{array}$$ Additional constraints for Equation (4) are: ${\mathit{v}}_0\in \mathit{S}$ and ${\mathit{v}}_1\cap {\mathit{v}}_2\cap \cdots \cap {\mathit{v}}_{\mathit{h}}\cap \mathit{S}=\varnothing$ . This is to ensure that each instance of type t or any of its superclasses is only considered once in the computation. The factor β ensures diminishing influence of broader concepts on the computation of specificity for more specific concepts. For example, from Fig. 4, when computing specificity of a given semantic relationship for class Film other instances of class Work that are not films have a higher influence than the more broader class Thing.

5. Bidirectional random walks for computing specificity

Computing Equation (4) requires accessing large parts of the knowledge graph. In this section, we present an approach that uses bidirectional random walks to compute specificity. To understand, consider an entity type t and a semantic relationship ${\mathit{p}}^{\mathit{d}}$ , for which we want to compute $\mathit{Specificity}\mathrm{(}{\mathit{p}}^{\mathit{d}}\mathrm{,}\mathit{t}\mathrm{)}$ . We start with a set S containing a small number of randomly selected nodes of type t. From nodes in S, forward random walks via ${\mathit{p}}^{\mathit{d}}$ are performed to collect a set of nodes ${\mathit{V}}_{\mathit{S}\mathrm{,}{\mathit{p}}^{\mathit{d}}}$ (ignoring intermediate nodes, for $\mathit{d}\mathrm{>}1$ ). From nodes in set ${\mathit{V}}_{\mathit{S}\mathrm{,}{\mathit{p}}^{\mathit{d}}}$ , reverse random walks in G (or forward random walks in ${\mathit{G}}^{\mathit{r}}=\mathit{reverse}\mathrm{(}\mathit{G}\mathrm{)}$ ) are performed using arbitrary paths of length d to determine the probability of reaching any node of type t. Specificity is computed as the number of times a reverse walk lands on a node of type t divided by the total number of walks. This idea is the basis for the algorithm presented next which builds a list of most relevant semantic relationships up to depth d sorted by their specificity to a given entity type t.

Specifically, ${\mathit{Q}}_{\mathit{paths}}$ and ${\mathit{Q}}_{\mathit{spec}}[]$ hold the set of semantic relationships, unsorted and sorted by specificity respectively. ${\mathit{Q}}_{\mathit{spec}}[]$ is initialized as an array of size d to hold sorted semantic relationships for every depth up to d. ${\mathit{N}}_{\mathit{paths}}$ specify the size of ${\mathit{Q}}_{\mathit{paths}}$ . ${\mathit{N}}_{\mathit{walks}}$ is the number of bidirectional walks performed for computing specificity for each semantic relationship in ${\mathit{Q}}_{\mathit{paths}}$ . A set S of randomly selected nodes of type t is generated in line 3. For each ith iteration ( $\mathit{i}⩽\mathit{d}$ ), a set of semantic relationships ${\mathit{Q}}_{\mathit{paths}}$ is selected in line 5. The function computeSpecificity, in line 6, computes specificity for each semantic relationship in ${\mathit{Q}}_{\mathit{paths}}$ and returns results in ${\mathit{Q}}_{\mathit{spec}}[\mathit{i}]$ . Each element of ${\mathit{Q}}_{\mathit{spec}}$ is an array of dictionaries. Each dictionary contains $\mathit{key}$ – $\mathit{value}$ pairs sorted by $\mathit{value}$ , where $\mathit{key}$ is the semantic relationship and $\mathit{value}$ is its specificity. For each ith iteration of for in Algorithm 1, ${\mathit{Q}}_{\mathit{paths}}$ can be populated from scratch with semantic relationships of depth i by random sampling of outgoing paths from S. Alternatively, for iterations $\mathit{i}⩾2$ , ${\mathit{Q}}_{\mathit{paths}}$ can be populated by expanding from most specific semantic relationships in ${\mathit{Q}}_{\mathit{spec}}[\mathit{i}-1]$ .

Algorithm 1

$\mathit{rankBySpecificity}\mathrm{(}\mathit{G}\mathrm{,}\mathit{d}\mathrm{,}\mathit{t}\mathrm{)}$

Algorithm 2

$\mathit{computeSpecificity}\mathrm{(}\mathit{G}\mathrm{,}\mathit{Q}\mathrm{,}\mathit{S}\mathrm{,}\mathit{t}\mathrm{,}\mathit{d}\mathrm{,}\mathit{N}\mathrm{,}\mathit{\beta }\mathrm{)}$

Algorithm 2 shows the function computeSpecificity which computes specificity for a given set of semantic relationships in Q ( ${\mathit{Q}}_{\mathit{paths}}$ from Algorithm 1). In lines 7 and 8, for each semantic relationship $\mathit{q}\in \mathit{Q}$ , a node $\mathit{s}\in \mathit{S}$ is randomly selected to get a node v reachable from s via semantic relationship q in G (forward walk). In line 9, by using v and selecting an arbitrary path via any semantic relationship ${\mathit{q}}^{\prime }$ of depth d, a node ${\mathit{v}}^{\prime }$ is reached (reverse walk, reverse walk in G or forward walk in ${\mathit{G}}^{\mathit{r}}$ ). If implementing specificity based on Equation (3), the algorithm needs to check if t is one of the types associated with ${\mathit{v}}^{\prime }$ and simply increment an integer variable count [40,43]. To implement specificity based on Equation (4), we first need to acquire the class hierarchy of entity type t in H in line 2. The first index of H holds t and every subsequent entry $\mathit{H}[\mathit{i}]$ for $\mathit{i}\mathrm{>}1$ holds the hypernym or superclass of entry $\mathit{H}[\mathit{i}-1]$ . For example, for entity type Film (Fig. 4), H = [“Film”, “Work”, “Thing”]. Starting from the first element in H at index $\mathit{i}=1$ , the existence of triple $⟨{\mathit{v}}^{\prime }\mathrm{,}\mathit{rdf}:\mathit{type}\mathrm{,}\mathit{H}[\mathit{i}]⟩$ is checked in G. If such a triple exists, count is incremented by a factor of ${\mathit{\beta }}^{\mathit{i}-1}$ . This process of bidirectional walks is repeated N times for each q. At line 17, specificity is computed as $\frac{\mathit{count}}{\mathit{N}}$ . Lines 4–18 are repeated until specificity for each $\mathit{q}\in \mathit{Q}$ has been computed. The return variable L contains semantic relationships and their specificity scores as $\mathit{key}$ – $\mathit{value}$ pairs.

6. Evaluation

We evaluate our approach in multiple ways. We analyze the behavior of specificity computed for most relevant semantic relationships up to depth 3. We evaluate the compactness of the extracted subgraphs by specificity-based biased random walk scheme against other metrics used as baselines. We generate embeddings from the extracted subgraphs to perform tasks of entity recommendation, regression, and classification. We analyze the ability of generated embeddings in preserving the semantics associated with the entities extracted from the KG. We study the sensitivity of specificity to the parameter ${\mathit{N}}_{\mathit{walks}}$ (number of bidirectional walks) and $|\mathit{S}|$ (seed set size). We provide an empirical analysis of the running time of Algorithm 2.

Fig. 5.

Extracted subgraphs are represented as a sequence of edge and node labels resulting in a document-like representation. The specificity scores shown are with respect to the entity type Film. The relationship starring has a specificity score of 79.1%, whereas starring → spouse has a score of 34.16%. Only those nodes connected to semantic relationships of specificity higher than 50% are considered for the extracted representation.

6.1. Datasets

We use DBpedia for evaluation which is one of the largest RDF repositories publicly available [20]. We use the English version of DBpedia dataset from 2016-04 (http://wiki.dbpedia.org/dbpedia-version-2016-04). We create graph embeddings for 5000 entities each of types: Film, Book, and Album. We also generate embeddings for 500 and 3000 entities of types Country and City respectively.

We use three different datasets for the tasks of classification and regression which provide classification and regression targets for DBpedia cities, films, and music albums:

The Mercer Cities8

⁸

https://mobilityexchange.mercer.com/Insights/quality-of-living-rankings

dataset contains a list of cities and their quality of living as numeric scores and discrete labels (“high”, “medium”, “low”).

The Metacritic Movies9 ⁹

http://www.metacritic.com/browse/movies/score/metascore/all

and Metacritic Music Albums10 ¹⁰

http://www.metacritic.com/browse/albums/score/metascore/all

datasets contain the Metacritic score (0–100) which are used as regression targets. The classification targets are provided as either “good” (score $⩾50$ ) and bad (score $\mathrm{<}50$ ) [35]. These datasets are accessible at http://data.dws.informatik.uni-mannheim.de/rmlod/LOD_ML_Datasets/data/datasets/.

6.2. Experimental setup and methodology

For our experiments, we hosted the DBpedia dataset using OpenLink Virtuoso11

¹¹

https://virtuoso.openlinksw.com/

on a server. All data transactions between the implemented modules and the repository occurr as SPARQL queries.

6.2.1. Implementation of baselines and proposed approach

In the first step, we compute $\mathit{Specificity}$ and Specificity ^H to find the set of most relevant semantic relationships for entities of selected types. Unless otherwise specified, we use following values for the parameters of the Algorithms 1 and 2: ${\mathit{N}}_{\mathit{walks}}=5000$ , $|\mathit{S}|=500$ , $\mathit{\beta }=0.25$ . Starting from a random seed set S for each type of entities, we randomly sample semantic relationships originating from entities in S and select top-25d semantic relationships based on the frequency of occurrence for each depth d. This becomes the frequency-based baseline, where the relevance of semantic relationships is based on how frequently they occur in the KG. After computing specificity for each of the most frequent semantic relationship, we only consider those as relevant that have specificity scores $⩾50\mathrm{\%}$ . For creating the PageRank-based baseline, we use the PageRank DBpedia dataset provided by Thalhammer et al. [48] (available at http://people.aifb.kit.edu/ath/#DBpedia_PageRank).

Fig. 6.

Comparison of frequency- and specificity-based metrics for top-15 semantic relationships.

6.2.2. Biased random walks for subgraph extraction

Using the lists of most relevant semantic relationships based on frequency-, PageRank-, and specificity-based metrics, we perform subgraph extraction using biased random walks. We use weighted randomized DFS for subgraph extraction for each target entity. The DFS algorithm traverses the paths starting from each target node using the list of most relevant semantic relationships. The nodes linked by more relevant semantic relationships have a greater likelihood to become part of the extracted subgraphs. The subgraphs are extracted as a set of unique graph walks (Definition 3) and can be represented as a sequence of edge and node labels, in the order in which they are visited [6,35]. An example of document-based representation of extracted subgraph is shown in Fig. 5. The semantic relationships such as starring and director have higher specificity than the threshold of $50\mathrm{\%}$ and thus are included in the extracted representation. The two depth-2 relationships starring → spouse and director → birthplace which have low specificity scores are excluded. For our experiments, we include up to a maximum of 1000 distinct paths in the extracted subgraphs for each entity for proposed and baseline approaches.

6.2.3. Embedding generation using word2vec

With the document-based representation, we use the Python library gensim12

¹²

https://radimrehurek.com/gensim/index.html

which provides the implementation of word2vec [24] to estimate representation of each label in the generated document into vector space creating embedding for the RDF entities [35].

6.3. Specificity as a metric for measuring relevance

Figure 6 shows the top 15 semantic relationships for entities of three types sorted by their $\mathit{Specificity}$ up to depth 3. The frequency represents the percentage of number of times a path representing a particular semantic relationship is traversed when the neighborhoods of randomly selected nodes are explored. For depth 1, the topmost plot of each subplot in Fig. 6 shows that there are only a few relatively high-frequency semantic relationships (represented by the peaks) whereas the rest show a uniform trend of frequency. As depth d increases, frequency exhibits a flattened trend due to a rapid increase in the number of possible semantic relationships at each depth. This trend makes it difficult to define a frequency-based cut-off value for choosing a certain set of semantic relationships as most relevant. This may require manual examination of the set of semantic relationships for choosing an appropriate frequency threshold. Alternatively, we can choose a value k such that top-k high-frequency semantic relationships are selected as the most relevant. For example, in Table 1, assuming that we wish to include the intuitively relevant semantic relationship dbo:director in the selected semantic relationships, we can either choose a frequency threshold of $\mathrm{<}1.08$ or choose $\mathit{k}⩾7$ . However, this ad-hoc method of selecting thresholds is impractical since it has to be done for every different class of entities, every depth, and every different RDF KG.

Table 1

Top semantic relationships based on frequency with corresponding specificity scores for dbo:Film

Semantic relationship	Freq. (%)	Spec. (%)	Spec. H (%)
rdf:type	38.46	74.69	79.15
dct:subject	16.94	87.9	89.09
owl:sameAs	11.88	98.4	98.4
dbo:starring	5.82	79.06	84.43
dbo:writer	1.68	76.48	81.86
dbo:producer	1.34	83.9	88.22
dbo:director	1.08	81.76	87.42
dbo:musicComposer	0.92	70.77	80.28
dbo:distributor	0.84	74.08	83.22
dbo:language	0.72	38.65	53.42
dbo:editing	0.66	91.65	92.82
dbo:cinematography	0.64	92.99	94.49

The threshold of Specificity is drawn at 50% in all plots in Fig. 6. The specificity of a semantic relationship is the probability of reaching any node of a given type from a set of nodes ( ${\mathit{V}}_{\mathit{S}\mathrm{,}{\mathit{p}}^{\mathit{d}}}$ in Definition 5) by reverse walks in G (or forward walks in ${\mathit{G}}^{\mathit{r}}$ ) using any arbitrary path of length d. We can define a universal cut-off for specificity at 50%. Specificity score above this threshold means that the selected semantic relationship links the instances of given class (or entity type) t to the set ${\mathit{V}}_{\mathit{S}\mathrm{,}{\mathit{p}}^{\mathit{d}}}$ such that more than half the incoming edges to this set originate from instances of class t. This means that the information represented by nodes in ${\mathit{V}}_{\mathit{S}\mathrm{,}{\mathit{p}}^{\mathit{d}}}$ on average is more specific to t.

In literature, other approaches such as [29] have employed a decaying factor ${\mathit{\alpha }}^{\mathit{d}}$ (where $\mathit{\alpha }\in [0.0\text{–}1.0]$ ) as a function of depth d that is used to equally penalize the relevance score of all nodes at depth d from target nodes. This is done to implement the idea that the relevance of nodes decreases as we move farther away from the target nodes. Specificity, on the other hand, has a more fine-grained mechanism of assigning relevance score across different depths. Figure 6 shows that there are multiple instances of semantic relationships at depth d that have higher specificity than semantic relationships at depth $\mathrm{<}\mathit{d}$ . This way specificity exhibits a more fine-grained behavior of relevance across depths, meaning that all semantic relationships at depth d do not simultaneously become less relevant as compared to those on depth $\mathit{d}-1$ , as d increases. There are variations in the specificity-based relevance scores of semantic relationships at the same depth as well as across depths. This allows both shallow (breadth-first) and deep (depth-first) exploration of the relevant neighborhoods around target entities by specificity-based biased random walks.

Table 2

Comparison of relevance metrics for example in Fig. 2

Semantic relationships	Spec.	PR	Freq.
director, knownFor	59.14	6.2	345
director, subject	1.05	823.53	73,752
director, birthPlace	0.03	200.33	7087

Fig. 7.

Average number of walks per entity for subgraph extraction.

Table 2 shows computed relevance of the three semantic relationships from example in Fig. 2 (Section 4.1) based on their specificity, PageRank, and frequency. The given PageRank values in column 3 are the average of non-normalized PageRank scores [48] of top-25 nodes linked to DBpedia entities of type Film by corresponding semantic relationship. The values of frequency in the last column represent the number of occurrences of the corresponding semantic relationship in DBpedia dataset. We argue that the semantic relationship director,knownFor is more relevant to a film as compared to the other two. Table 2 shows that the proposed specificity based relevance metric is closer to our intuition as compared to other metrics.

Table 3

Comparison of Specificity and ${\mathit{Specificity}}^{\mathit{H}}$ scores ( $\mathit{\beta }=0.25$ )

Semantic relationships	Entity type	Spec. (%)	Spec H (%)
dbo:language	dbo:Film	38.65	53.42
dbo:genre	dbo:Album	43.29	50.8
dbo:recordLabel	dbo:Album	43.41	56.34
dbp:genre	dbo:Book	46.85	52.29
dbo:previousWork	dbo:Book	40.0	55.0
dbo:litrerayGenre	dbo:Book	46.22	51.52

6.3.1. ${\mathit{Specificity}}^{\mathit{H}}$

As discussed in Section 4.1 that $\mathit{Specificity}$ only includes those nodes in its computation that are dominantly exclusive or specific to nodes of a given type. However, many types of entities require both specific as well as generic nodes and relationships for complete characterization. For example, assume that a node representing $\mathit{language}$ is associated with all instances of the class $\mathit{Work}$ and its subclasses (Fig. 4). Since nodes representing languages can be linked to multiple different entity types, therefore the specificity of the semantic relationship that links language-related nodes will be low. In other words, if the algorithm performs reverse walks from dbo:English, it can potentially land on multiple different types of nodes (e.g., films, books, songs, plays, games).

Table 3 shows a few examples of intuitively relevant semantic relationships with specificity scores below the threshold of 50%, resulting in the exclusion from the representative subgraphs of instances of corresponding entity types. ${\mathit{Specificity}}^{\mathit{H}}$ computed using Algorithm 2 takes into account the applicability of such relationships to co-hyponyms and hypernyms of the given entity types, resulting in an increase in the specificity score. This is evident in all plots in Fig. 6 where the curve of ${\mathit{Specificity}}^{\mathit{H}}$ lie on or above the corresponding curve of $\mathit{Specificity}$ .

6.4. Comparison of sizes of representative subgraphs

Figure 7 shows that specificity-based random walk schemes enable the extraction of relevant subgraphs with fewer number of walks. Specificity-based schemes use extraction template based on semantic relationships with ⩾50% specificity which enables collection of comparatively fewer but more relevant nodes and edges than the baselines for all three of the chosen entity-types. ${\mathit{Specificity}}^{\mathit{H}}$ , as seen in Fig. 6 assigns higher specificity scores, resulting in a few more semantic relationships meeting the 50% threshold. This results in an increase in the collected number of walks which, nevertheless, is still below the baseline approaches.

Figure 7(a) shows that the average size of the subgraph of each entity of type dbo:Book for ${\mathit{Specificity}}^{\mathit{H}}$ is smaller by a factor of 48, 16, and 5 w.r.t uniform, PageRank, and Frequency-based approaches respectively. Similarly, Fig. 7(b) shows that the average size of the subgraph of each entity of type dbo:Book for ${\mathit{Specificity}}^{\mathit{H}}$ is smaller by a factor of 62, 30, and 2 w.r.t uniform, PageRank, and Frequency-based approaches respectively. We will revisit this discussion in the context of its impact on the recommendation task in Section 6.5.1.

Figure 7(a) shows that the average subgraph size is larger for depth-3 than depth-2. One of the reasons is that the most specific depth-2 property for dbo:Book entities adds on average one walk to each of the extracted subgraphs, whereas the most specific depth-3 property adds 15 walks on average. On the other hand, Fig. 7(c) shows the opposite effect where depth-2 subgraph size is larger than depth-3 for Specificity ( $\mathit{\beta }=0.0$ ). The top specific semantic relationships at depth-2 and depth-3 add 100.8 and 9.4 walks on the average to each extracted subgraph respectively. The main underlying reason is that having a higher number of specific semantic relationships does not necessarily indicate a larger extracted subgraph or vice versa. The size of the subgraph depends on the number of nodes a particular semantic relationship connects to the target entities to include in the extracted subgraph. For example, for film nodes, on average dbo:director and dbo:cinematographer add 1.06 and 1.07 walks to the extracted subgraphs whereas rdf:type and dct:subject add 28 and 8 walks respectively.

6.5. Embeddings as an application of specificity-based extracted subgraphs

We have shown that the specificity-based biased random walks extract more compact subgraphs representing entities as compared to other schemes. However, to show that the compactness of the extracted subgraphs is not a disadvantage, we use the graph embeddings as an application to evaluate their effectiveness. Using the extracted subgraphs extracted as documents (Section 6.2), we train Skip-gram models using the following parameters: dimensions of generated vectors = 500, window size = 10, negative samples = 25, iterations = 5 for each scheme and depth. All models for depth $\mathit{d}\mathrm{>}1$ are trained using sequences generated for both depths 1 and d. The parameters for this experiment are based on RDF2Vec [35].

Fig. 8.

Comparison of precision and recall for entity recommendation tasks ( $\mathit{\beta }=0.25$ for ${\mathit{Specificity}}^{\mathit{H}}$ ).

6.5.1. Suitability for entity recommendation task

To show that the compactness of the extracted subgraphs is not a disadvantage, we use the generated graph embeddings for the task of entity recommendation. Given a vectorized entity as the search key, we list its top-k most similar results. We use the metrics of precision@k to quantify the performance of the recommendation tasks. Evaluating retrieved results requires ground truth. For music albums and books, the ground truth straightforwardly consists of other works by the same artists and authors respectively. For films, we select franchises or series as ground truth. Films in a franchise or a series usually share common attributes (e.g., director, actors, genre, characters) and are more likely to be similar to each other. For example, for any of the three The Lord of the Rings (LOTR) films the other two films in the trilogy are its more likely top-2 similar results because of the same director, cast members, genre, and characters. In our experiments, King Kong (2005) also frequently appeared among the results similar to LOTR since it also has the same director. Other films may also occur among top-k results based on any number of other factors, e.g., cinematography, editing, distributor, all of which have high specificity to dbo:Film (from Table 1). Creating exhaustive lists of films for the ground truth to encompass all such scenarios is laborious. That is why we include only those films in the ground truth that are either in a franchise (e.g., all Batman films) or are part of a series (e.g., prequels or sequels). Similarity among such films is relatively stronger and easier to interpret. Assuming that there are n entities in the ground truth for a given franchise, series, author, or artist (e.g., $\mathit{n}=3$ for LOTR or $\mathit{n}=71$ for Agatha Christie in our DBpedia dataset), we chose one entity at a time to retrieve top-k similar entities (for $\mathit{k}=1$ to $\mathit{n}-1$ ), resulting in a total of $\mathit{n}\mathrm{(}\mathit{n}-1\mathrm{)}$ recommendation tasks per franchise, author, or music artist. We perform 59,616, 221,280, and 124,032 recommendation tasks for films, books, and music albums for each random walk scheme respectively.

Results Figure 8 shows the results of recommendation tasks for each scheme. Here, we have chosen $\mathit{\beta }=0.25$ for computing ${\mathit{Specificity}}^{\mathit{H}}$ . The baselines are shown as colored bars whereas ${\mathit{Specificity}}^{\mathit{H}}$ is drawn as a line to make the comparison clearer. ${\mathit{Specificity}}^{\mathit{H}}$ is generally slightly better than other baseline schemes except in Fig. 8(c) where PageRank-based extracted subgraphs have a better performance.

Fig. 9.

Effect of β on recommendation task.

Here, it is important to note that the compactness of the extracted subgraphs is the main contribution of our approach. We use recommendation as an application to show that despite extracting less information from the KG, there is not a significant deterioration in performance when using the specificity-based approach with such applications. The results of the recommendation task must be interpreted in conjunction with our primary metric of the size of the extracted subgraph. Figure 9 shows the average precision of recommendation tasks performed along with the average size of the subgraph extracted per entity from which the embeddings were generated. For dbo:Book, Fig. 9(a) shows that the average size of the subgraph for each entity is 48, 16, and 5 times smaller for ${\mathit{Specificity}}^{\mathit{H}}$ w.r.t uniform, PageRank, and Frequency-based approaches respectively, whereas the precision values for ${\mathit{Specificity}}^{\mathit{H}}\mathrm{(}\mathit{\beta }=0.25\mathrm{)}$ and the three baselines lie in $75.1\pm 0.78\mathrm{\%}$ . Similarly, for music albums (Fig. 9(b)), the subgraph size for ${\mathit{Specificity}}^{\mathit{H}}\mathrm{(}\mathit{\beta }=0.25\mathrm{)}$ is reduced by factors of 62, 30, and 2 respectively with precision lying $68.7\pm 1.6\mathrm{\%}$ . Figure 9(c) shows that the average size of the subgraph for PageRank-based approach for each entity is 4.2 times larger than ${\mathit{Specificity}}^{\mathit{H}}$ with $\mathit{\beta }=0.25$ with an advantage of $5\mathrm{\%}$ in precision. The size of the subgraph for each entity for unbiased (uniform) approach is ten times larger than ${\mathit{Specificity}}^{\mathit{H}}$ -based approach for films. The range of precision values for ${\mathit{Specificity}}^{\mathit{H}}\mathrm{(}\mathit{\beta }=0.25\mathrm{)}$ and the baselines lie in the range $71.1\pm 3\mathrm{\%}$ . This shows that a substantial reduction in extracted information still allows us to have comparable performance in entity recommendation task with the specificity-based approach.

For the recommendation task, we have used a purely content-based recommendation system. In future work, we intend to use collaborative information in conjunction with the extracted semantic information and compare against hybrid approaches such as SPRank [28] and $\mathcal{H}$ -DB2Vec (a hybrid RDF2Vec-based approach). Such approaches have shown favorable outcome for ranking-related tasks on multiple datasets [36].

Table 4

Results of regression and classification tasks – ${\mathit{Specificity}}^{\mathit{H}}\mathrm{(}\mathit{\beta }=0.25\mathrm{)}$

Model	Depth	Classification			Regression
		Cities	Films	Albums	Cities	Films	Albums
Uniform	1	0.935	1.0585	0.983	0.9011	1.0079	1.0002
Uniform	2	0.9359	1.0273	1.0374	0.9131	0.9976	1.0056
PageRank	1	1.0985	1.029	0.9663	0.9546	0.9955	1.0033
PageRank	2	1.0135	0.9849	1.0484	0.9347	0.9935	1.0019
Frequency	1	1.0709	1.0118	0.9421	0.9506	0.998	0.9926
Frequency	2	0.9558	1.0294	0.9886	1.0328	1.0002	0.9996
SpecificityS	1	1.1098	1.0341	0.9894	1.0601	0.9967	1.0017
SpecificityS	2	0.9161	1.023	1.0401	0.8882	0.9985	1.0027

Effects of β on specificity Increasing the value of β means that the ${\mathit{Specificity}}^{\mathit{H}}$ score (for $\mathit{\beta }\mathrm{>}0.0$ ) for any semantic relationship will be equal or higher than its $\mathit{Specificity}$ score. This is also evident from Fig. 6 where ${\mathit{Specificity}}^{\mathit{H}}$ ( $\mathit{\beta }=0.25$ ) ⩾ $\mathit{Specificity}$ ( $\mathit{\beta }=0.0$ ). This will result in more semantic relationships having higher specificity than the cut-off set at $50\mathrm{\%}$ . With a higher number of relevant semantic relationships used for subgraph extraction, the size of extracted subgraphs can increase. Therefore, the function of β is to select between better performance versus smaller size of the extracted subgraphs.

Figure 9 also shows the effect of changing β on the size of the extracted subgraphs and the recommendation task. Here first we refer back to discussion of Algorithm 1 in Section 5. In Line 5 ${\mathit{Q}}_{\mathit{paths}}$ holds the set of selected semantic relationships which are then re-ordered and filtered in Line 6 using the metric of specificity. In our implementation, the semantic relationships for populating ${\mathit{Q}}_{\mathit{paths}}$ are selected based on their frequency of occurrence. For $\mathit{\beta }=1.0$ , every semantic relationship in ${\mathit{Q}}_{\mathit{paths}}$ gets a high specificity score in Line 6, i.e., the $\mathit{count}$ variable in Line 12 gets incremented by 1 irrespective of the type of ${\mathit{v}}^{\prime }$ in Line 9. This means that all frequent semantic relationships are also deemed specific for $\mathit{\beta }=1.0$ . Figure 9 shows the average sizes of extracted subgraphs for Frequency and ${\mathit{Specificity}}^{\mathit{H}}\mathrm{(}\mathit{\beta }=1.0\mathrm{)}$ are the same in each subplot.

6.5.2. Suitability for regression and classification tasks

We perform the tasks of classification and regression on the Mercer Cities, Metacritic Movies, and Metacritic Music Albums datasets using the embeddings generated for DBpedia entities. We use SVM for classification and Logistic Regression for regression tasks. We measure accuracy for classification tasks and root mean squared error (RMSE) for regression tasks. The numeric values shown in Table 4 can be interpreted as factor of improvement ( $\mathit{lift}$ ) when ${\mathit{Specificity}}^{\mathit{H}}\mathrm{(}\mathit{\beta }=0.25\mathrm{)}$ -based embeddings are compared to the baselines and $\mathit{Specificity}$ . The results show that all schemes are comparable with no scheme consistently outperforming the others. However, these results are achieved using embeddings generated from smaller extracted subgraphs, proving that specificity-based embeddings can be suitable for data mining tasks.

6.5.3. Semantics of specificity-based vector representations

To analyze the semantics of the vector representations, we employ Principal Component Analysis (PCA) to project the generated embeddings into a two-dimensional feature space. We selected seven countries (similar to evaluation done for RDF2Vec [35]) and their capital cities and visualized the vectors as shown in Fig. 10. Figures 10(d) and 10(e) show that specificity-based embeddings are capable of organizing entities of different types and preserving some semantic context among them. For instance, there is a separation between two different types of entities: dbo:Country and dbo:City, preserving the rdf:type relationship. Compared to $\mathit{Specificity}$ , ${\mathit{Specificity}}^{\mathit{H}}$ has comparatively better, although not perfect, organization of capitals in correspondence to their respective countries. Third, in Fig. 10(e), cities are grouped together based on the continents. The information regarding continents is represented via the semantic relationship dct:subject which links each city to different DBpedia categories including one that represents information about continents, e.g. dbc:Capitals_in_Asia.

Figures 10(b) and 10(c) show that rdf:type relationship is not preserved by frequency and PageRank-based projections respectively. There exists some, but inconsistent, organization of countries and capitals with respect to each other and a grouping based on continents. There is also no clear segregation based on entity types. Figure 10(a) shows that semantic associations are also preserved using uniform random walks. However, it can be seen in Fig. 11 that the average size of extracted subgraphs is order of magnitude more than the Specificity-based approach.

6.6. Parameter sensitivity

The algorithms for computing specificity use bidirectional random walks, governed by two parameters: number of bidirectional walks ( ${\mathit{N}}_{\mathit{walks}}$ ) and size of seed set S. In this section, we evaluate the sensitivity of specificity to these parameters.

6.6.1. Sensitivity of specificity to ${\mathit{N}}_{\mathit{walks}}$

The algorithm for computing specificity uses the parameter ${\mathit{N}}_{\mathit{walks}}$ for the number of bidirectional walks. To understand the effect of this parameter on specificity, we first compute specificity for ${\mathit{N}}_{\mathit{walks}}\in [2500\mathrm{,}20\text{,}000]$ . Figures 12(a), 12(c), and 12(e) show the comparison between specificity scores computed for different values of ${\mathit{N}}_{\mathit{walks}}$ for top-10 semantic relationships for entity type dbo:Film, dbo:Book, and dbo:Album. The semantic relationships are sorted on the x-axis (from left to right) in order of decreasing specificity computed based on ${\mathit{N}}_{\mathit{walks}}=2500$ for comparison. Figure 12(g) shows the total time taken to compute specificity for the top-10 semantic relationships for each value of ${\mathit{N}}_{\mathit{walks}}$ . The computation time increases with increasing number of bidirectional walks. Figures 12(b), 12(d), and 12(f) show the average specificity and corresponding computation time for each semantic relationship for all values of ${\mathit{N}}_{\mathit{walks}}$ for the three chosen entity types. We use standard deviation to show the variations in the specificity scores and computation times observed for different values of ${\mathit{N}}_{\mathit{walks}}$ . It can be observed that generally large variations in computation time do not lead to significant changes in the specificity scores. Choosing a larger value of ${\mathit{N}}_{\mathit{walks}}$ will simply increase the total computation time without having significant effect on the computed specificity scores. If we select ${\mathit{N}}_{\mathit{walks}}=5000$ as a suitable value for computing specificity, it can be seen from Fig. 12(g) that the time for computing specificity scores w.r.t. either entity-type is ⩽150 s. Moreover, this computation is only needed to be performed once for each type of target entities in a KG.

6.6.2. Sensitivity of specificity to $|\mathit{S}|$

Similar to previous discussion for ${\mathit{N}}_{\mathit{walks}}$ , Figs 13(b), 13(d), and 13(f) also shows that the large variations in computation time do not lead to major change in the specificity. Choosing a larger value of $|\mathit{S}|$ increases the total computation time without having a significant effect on the computed specificity scores. If we choose $|\mathit{S}|\in [500\text{–}1000]$ as a suitable value for computing specificity, it will result in computation time of ≈150 s for computing specificity of top-10 most specific semantic relationships.

Fig. 10.

Projection of countries and capitals in 2D space using embeddings generated from RDF subgraphs of depth 2.

Fig. 11.

Average number of walks per entity of types dbo:City and dbo:Country for subgraph extraction for different values of β.

6.7. Analysis of running time of specificity computations

The specificity computations are performed by Algorithm 2. Algorithm 1 is used for setting up parameters and inputs for Algorithm 2. Since, the algorithm for computing specificity is based on random sampling governed by specific parameters, so instead of purely theoretical formulation here we provide a limited complexity analysis supplemented by empirical analysis of the running time of the algorithm.

Algorithm 2 computes specificity for a list of semantic relationships provided as input parameter Q. The complexity of Algorithm 2 as presented is the complexity of computing specificity of a single semantic relationship multiplied by the size of Q. Therefore, we analyze the complexity of computing specificity of a single semantic relationship which is accomplished in Lines 5–17. Lines 6–16 repeat N (or ${\mathit{N}}_{\mathit{walks}}$ ) times, which is the number of bidirectional walks. In each iteration, the Algorithm 2 performs a forward walk in G and ${\mathit{G}}^{\mathit{r}}\mathrm{(}\mathit{reverse}\mathrm{(}\mathit{G}\mathrm{)}\mathrm{)}$ or a forward and then a reverse walk in G (Lines 8 and 9). After completing the bidirectional walk, a node ${\mathit{v}}^{\prime }$ is identified in Line 9. Lines 10–15 determine if ${\mathit{v}}^{\prime }$ has the type t or some other type in the class hierarchy, and the count is updated accordingly.

Fig. 12.

Effect of ${\mathit{N}}_{\mathit{walks}}$ on computation of specificity.

Fig. 13.

Effect of $|\mathit{S}|$ on computation of specificity.

Fig. 14.

Empirical analysis of computation time of specificity.

There are two distinct tasks being performed in each iteration of the loop (Lines 6–16): (i) a bidirectional walk starts from a random node s of type t and lands at a node ${\mathit{v}}^{\prime }$ and (ii) determining the position of the type of ${\mathit{v}}^{\prime }$ in the class hierarchy. Assuming a tree-like class hierarchy where the height of the tree is H, the running time of the Lines 6–16 can be represented as $\mathit{O}\mathrm{(}\mathit{N}{\mathit{n}}_1+\mathit{N}\mathit{H}{\mathit{n}}_2\mathrm{)}$ where ${\mathit{n}}_1$ and ${\mathit{n}}_2$ correspond to the two tasks described above. Tasks ${\mathit{n}}_1$ and ${\mathit{n}}_2$ require information that is gathered by issuing SPARQL queries in our implementation. Therefore, the complexity of these tasks depends on how the query engine of Virtuoso optimizes the query execution. Instead of further expanding the relation for complexity mathematically, we treat the query engine as a black box and measure the query execution times of the issued SPARQL queries. In our implementation, we compute specificity using three sets of SPARQL queries, each of which performs one of the tasks below:

1. Starting from the seed set S, get a set V of N number of nodes using the semantic relationship of depth d, i.e., N iterations of Lines 7–8 of Algorithm 2.

2. Starting from the acquired set V, perform N number of reverse walks to get a set ${\mathit{V}}^{\prime }$ using any arbitrary path of depth d, i.e., N iterations of Line 9 of Algorithm 2.

3. Determine type of each ${\mathit{v}}^{\prime }\in {\mathit{V}}^{\prime }$ and update count in Line 12 accordingly.

Table 5 shows the distribution of classes at different heights in the class hierarchy of DBpedia. Level 0 corresponds to dbo:Thing, the root of the class hierarchy. The maximum height of the tree H is 8. We replace H with a constant term and rewrite the running time relation for our DBpedia-based experiments as $\mathit{O}\mathrm{(}\mathit{N}[{\mathit{n}}_1+\mathit{k}{\mathit{n}}_2]\mathrm{)}$ . Since the time complexity of tasks ${\mathit{n}}_1$ and ${\mathit{n}}_2$ depends on the query optimizations performed by the SPARQL query engine, therefore, we empirically measure the behavior of the term in the parentheses.

In the Fig. 14(a), each marker represents a single computation of specificity. We compute specificity for five classes (dbo:Film, dbo:Book, dbo:Album, dbo:City, and dbo:Country, depths $\mathit{d}⩽3$ , different seed set S sizes (100–1000), and ${\mathit{N}}_{\mathit{walks}}=[5000\mathrm{,}50\text{,}000]$ , resulting in 23,908 data points. The red curve shows the average of computation time averaged against each value of ${\mathit{N}}_{\mathit{walks}}$ . Figure 14(b) shows the distribution of computation times which shows 75% of all the data points shown in Fig. 14(a) represent a computation time of less than 20 s for DBpedia KG. Moreover, this computation is only needed to be performed once for each type of target entities in a KG.

Table 5

Distribution of classes at different heights in DBpedia hierarchy

Height in the class hierarchy	Number of classes
0	1
1	49
2	126
3	209
4	271
5	72
6	23
7	4

7. Conclusion and future work

Graph embedding is an effective method of preparing KGs for AI and ML techniques. However, to generate appropriate representations, it is imperative to identify the most relevant nodes and edges in the neighborhood of each target entities. In this paper, we presented specificity as a useful metric for finding the most relevant semantic relationships for target entities of a given type. Our bi-directional random walks-based approach for computing specificity is suitable for large-scale KGs of any structure and size. We have shown through experimental evaluation that the metric of specificity incorporates a fine-grained decaying behavior for semantic relationships. It has the inherent ability to interpolate between extreme exploration strategies: BFS and DFS. We used specificity-based biased random walks to extract compact representations of target entities for generating graph embedding. These generated representations have similar performance as compared to baseline approaches when used for our selected tasks of entity recommendation, regression, and classification.

We presented the variable β for ${\mathit{Specificity}}^{\mathit{H}}$ as a hyperparameter that controls the trade-off between better precision and smaller extracted subgraph sizes. We experimented with fixed values of β. In future extensions, we will explore estimating β based on the structure of the given KG. We also intend to use collaborative information in conjunction with the specificity-based extracted semantic information to improve the performance of the recommendation tasks. Finally, we intend to study other tasks for which specificity-based graph embedding can be useful such as KG completion and ontology alignment.