Evaluating the similarity of RDF resources is nowadays a thoroughly investigated research problem, with reference to a variety of contexts. In fact, several tools are available for the comparison of pairs and/or groups of resources in a knowledge graph, mostly based on machine learning techniques. Unfortunately such tools, though extensively tested and fully scalable, return non-explainable (often numerical) similarity results also when comparing RDF resources, treating them according to their vector embeddings. and making no use of the semantic information carried by RDF triples. In this work, we propose a tool able to compute the commonalities of compared resource and explain them through a text in English, produced by a Natural Language Generation approach. The proposed approach is logic-based and is grounded on the computation of the Least Common Subsumer (re)defined in RDF. The feasibility of the tool is demonstrated with reference to the similarity of Twitter accounts.
Learning techniques based on Neural Networks or other forms of numerical vectors comparison
have recently shown their efectiveness in producing tools for assessing similarity between
complex objects and for clustering them according to (possibly unsupervised) criteria. These
tools are nowadays also applied to data coming from RDF repositories [
Yet RDF, as part of the Semantic Web efort, was equipped from its birth with a logical
semantics [
We present a Natural Language Generation (NLG) tool, based on LCS for RDF data, that
describes in English sentences the commonalities of RDF resources previously clustered,
or declared similar, by any other non-transparent tool. The connectivity of RDF-graphs—
objects/predicates of a triple being subjects of other triples—leads to non-trivial relative
sentences in English, rendered with relative pronouns. Blank nodes are fundamental in our common
subsumers to represent partial commonalities in RDF paths from clustered resources. We use
relative pronouns in relative sentences to represent them. To our knowledge, there are no
other tools that also accept blank nodes in the verbalization of RDF graphs. This tool has been
already implemented for the comparison of drugs and of contracting processes [
The paper is organized as follows: in the next section, we discuss related works and how diferent our approach is from them. In Section 3 we briefly summarize the necessary notions regarding LCS in RDF. Then in Section 4 we explain in detail how we construct (possibly relative) sentences from Common Subsumers. In Section 5 we show examples of the results of our tool when applied to similar Twitter accounts. The final section concludes the paper.
The explanation of clustering results has been addressed since 1980 in the conceptual clustering
research field [
So far, this problem has attracted several researchers, whose most influential proposals have
been recently reviewed, for the interested reader, by Pérez-Suárez et al. [
In this paper, similarly to conceptual clustering, we aim at explaining clustering results, but we do not cope with the problem of grouping resources. In fact, we propose a logic-based methodology to explain the commonalities of RDF resources grouped by any aggregation criterion. In other words, our methodology is agnostic w.r.t. the aggregation criterion.
A similar attitude is shared by Dedalo [
Diferently from Dedalo, we take a deductive approach to the identification of cluster commonalities. In particular, given a group of resources returned in the same cluster, the approach computes their LCS,i.e., a set ot triples that abstracts their commonalities. The RDF triples in the LCS are then parsed to produce a human-readable explanation of their content.
Thus, our approach falls in the widely populated field of Natural Language Generation
(NLG) from the Semantic Web. Since 2014, Bouayad-Agha et al. [
None of the reviewed approaches is able to manage anonymous resources or to generate text from derived triples (not explicitly stated in RDF).
In recent years, NLG has mainly focused on the improvement of the readability of generated
language, measured through the setting of common baselines. The WebNLG challenge [
The traditional trend of NLG approaches has been the usage of rules and templates, which represent solutions highly domain-dependent and demanding manual intervention.
A recent shift to this trend has been made possible by deep learning, thanks to neural networkbased NLG models. As an example, Neural Wikipedian [13] employs the Sequence to Sequence (SEQ2SEQ) framework [14] (a neural network-based NLG model) to generate summaries of RDF triples. Similarly, Li et al.[15] propose the Neural Entity Summarization approach.
Both summarization approaches collect only triples that are already present in the RDF descriptions, without handling blank nodes.
Our template-based method for explaining RDF similarity has several distinguishing features
w.r.t. the approaches above. To the best of our knowledge, it is the only one able to manage
blank nodes, that are crucial for the purpose of abstracting several triples with common
predicate/object. Even more importantly, our method uses blank nodes to chain triples reaching
the same known object (see the example about Twitter accounts in Sect.5). Lastly, our method
does not explain just trivial sets of triples, but RDF graphs logically computed to summarize
the commonalities shared by groups of resources. This makes really significant the
informative potential of the returned explanation, which is double-tied to the logic-based nature of
computation.
3. LCS in RDF
We assume that the reader is familiar with RDF triples and graphs, but to make this paper
self-contained, we briefly recall here the definition of [Least] Common Subsumers (LCS) in the
context of RDF [
First, given an RDF-graph containing Resource as a node, we denote a rooted RDF-graph (in brief r-graph) by the pair ⟨, ⟩. This allows us to compare Resources , by referring to their respective r-graphs ⟨, ⟩, ⟨, ⟩.
Second, let [ → ] be the graph obtained by substituting each occurrence of with in ;
now the definition of Simple Entailment |= [
Conditions is a blank node is not a blank node
is a blank node [ ↦→ ] |= [ ↦→ ] for a new URI occurring neither in nor in |= [ ↦→ ] is not a blank node
No entailment = , and |= Intuitively, Rooted Entailment restricts Simple Entailment by requiring that the root of one graph be mapped to the root of the other. When both resources , are URI, this is possible only when = (2nd row, 2nd column), while when either or is a blank node (all other entries), a suitable substitution is necessary to obtain the mapping before checking Simple Entailment.
Rooted Entailment is needed to define the notion of Common Subsumer (CS) of two r-graphs ⟨, ⟩, ⟨, ⟩: Definition 2 (Common Subsumer, [3, Def.7]). Let ⟨, ⟩, ⟨, ⟩ be two r-graphs. An rgraph ⟨, ⟩ is a Common Subsumer (CS) of ⟨, ⟩, ⟨, ⟩ if both ⟨, ⟩ |= ⟨, ⟩ and ⟨, ⟩ |= ⟨, ⟩.
Finally, a Least Common Subsumer (LCS) of two RDF resources can be defined as follows: Definition 3 (Least Common Subsumer [3, Def.8]). Let ⟨, ⟩, ⟨, ⟩ be two r-graphs. An r-graph ⟨, ⟩ is a Least Common Subsumer (LCS) of ⟨, ⟩, ⟨, ⟩ if both conditions below hold: 1. ⟨, ⟩ is a CS of ⟨, ⟩, ⟨, ⟩; 2. for every other CS ⟨, ⟩ of ⟨, ⟩, ⟨, ⟩: if ⟨, ⟩|=⟨, ⟩ then ⟨, ⟩ |= ⟨, ⟩, ( i.e., ⟨, ⟩ and ⟨, ⟩ are equivalent under Rooted Entailment).
Colucci et al.[
Associativity relies on a fundamental property of LCSs as proposed by Colucci et al., namely, the LCS of two r-graphs is itself an r-graph, so it can be used as an argument of another LCS operation with a third r-graph, etc. Associativity ensures that the order in which resources are taken—when computing the LCS of all of them—does not matter.
We also recall some definitions adapting the basic notions of Graph Theory to RDF-graphs
[
We propose to use the LCS of a cluster of RDF resources—obtained in any way—to explain their commonalities. The LCS could be useful both in a tuning phase of a clustering tool, and in an explanation of the result to an unacquainted final user. To this end, we attached to the construction of an LCS its explanation in English common language, as described in the next section.
The main contribution of this paper is the proposal of an approach grounded on LCS computation to the explanation of similarities among grouped RDF resources. The approach has been also implemented in a tool demonstrating its feasibility. The whole explanation process is performed in three steps: i) Problem settings; ii) (L)CS computation; iii) Natural Language Generation from the (L)CS computed at Step 2. We detail each step in the next subsections.
The first step aims at specifying some preliminary settings, both for ensuring feasibility in the management of RDF resources and for tailoring the approach to the specific application scenario.
In particular, RDF-based applications need to select which triples qualify a resource , among the ones available in the Web of Data. This filtering is necessary because the management of all triples linked to a resource would make unfeasible any application, given the huge and ever increasing dimensions of this information source.
Our approach adopts the explicit criteria proposed by Colucci et al. [
The fourth additional setting (1d) is required to increase the significance of returned commonalities, by recursively eliminating from the LCS triples that provide little information, called uninformative triples. Thus, a—no more Least—Common Subsumer is obtained, containing only the most informative triples deducible from all r-graphs.
The set of stop-patterns and uninformative triples include both general patterns/triples (to be discarded in every application domain), and some domain-dependent patterns/triples, defined through the analysis of our results.
The last required settings (1e) are aimed at tailoring the explanation to the specific application domain to cope with. In particular, it is required a dictionary for the English language translation of URIs included in the reference dataset, to improve the readability of returned explanation. The full automation of this mapping (URI to common language term) is not always feasible, depending on the quality of used datasets. Notably, when a dataset allows for the retrieval of significant URI labels, the above mentioned dictionary may be automatically built. We summarize below all problem settings of Step 1:
a) data sources: which datasets (one or more) to explore for the comparison; b) RDF-distance: the maximum RDF-distance from of triples to involve1; c) stop-patterns: triples patterns to be excluded in the selection; d) LCS uninformative triples: triples which, although logically implied by the r-graphs of all analyzed resources, are recursively eliminated from the results; e) dictionary of resources involved in triples: English language form to be employed in the verbalization of URIs.
Such settings allow for flexibly tailoring the approach to diferent application scenarios, as
demonstrated by its implementation for the comparison of drugs and contracting processes [
The second step is implemented by Algorithm 1, that computes a CS of a of RDF
resources, given as first input. Since previous publications [
Algorithm 1: find a CS of a set of resources incrementally, by Associativity 1 __(, , , , uninf _triples);
Input : • : an array containing the URIs of all resources to analyze; • : the RDF-distance for graphs exploration; • : the union of datasets to be explored; • : a boolean predicate to be satisfied by selected triples; • uninf _triples: triples to be recursively eliminated from the results.
Output : r-graph ⟨, ⟩ such that ⟨, ⟩ |= ⟨, ⟩ for every ∈
Subroutine : (, , , , , ) [
Before entering the main loop (Rows 4–13), Algorithm 1 extracts the first resource from the list (Row 2). Then, the resource representing the root of the running CS, , is initialized to the first resource (Row 3). The CS ⟨, ⟩ is incrementally built by looping over the remaining 1We recall that r-graph definition ensures connectedness: there must be an RDF-path from to the subject of each chosen triple resources (Rows 4–13). At each iteration stage, another resource is extracted from the cluster (Row 5). In Row 6, we compute the LCS between this and the running CS, , resulting from the previous iteration. At Row 7, uninformative triples are recursively removed from the CS computed so far. The loop continues until either is empty or until the dimension of the last computed seed, , equals to zero (Row 11). In this second case, Algorithm 1 returns the last significant CS, whose is not empty and that is stored in ⟨, ⟩ at each iteration (Row 9).
We notice that, in place of the exit criterion in Row 8, thresholds greater than 0 could be adopted to improve the significance of the returned set of commonalities, by giving up to the largest sharing of such commonalities among resources in the cluster and retrieving more significant CSs of specific cluster subsets. At implementation level, such more stringent requirements (that will be part of our future work) are possible because the running CSs, together with the subsets of resources it represents, is saved and available for further usage. In particular, at each iteration stage, the running CS is serialized2 and saved in both Turtle and N-triples formats.
The output of Algorithm 1 is passed to the third step, which implements the NLG approach for the explanation of (L)CS that we propose as our main contribution.
We recall that r-graphs modeling (L)CSs include blank nodes by construction (see Definition 1) and that blank nodes may occur in positions other than the root. For instance, while describing a cluster of Twitter accounts (see Sect. 5), we may find in the CS the following path (simplified here with prefix ex: for readability): _:x _:y ex:mention _:y .
ex:involved-in ex:videogames . which says that the accounts in the cluster (all represented by one blank node _:x) mention some resource (_:y) which is involved in the topic of videogames. We stress that the blank node _:y representing a generic resource does not occur by itself in the input r-graphs; it represents the fact that diferent accounts mention diferent IRIs, yet all such diferent IRIs are involved in videogames.
To the best of our knowledge, no available NLG tool3 is able to verbalize RDF triples involving blank nodes in any position, and this makes our proposal (and tool) original.
In what follows, we describe our NLG approach, w.r.t. the six main building tasks synthesized by Gatt and Krahmer [18]: 1. Content Determination We determine the content to explain through the (L)CS construction detailed in Section 4.2, that discards from the (L)CS all information we consider uninformative; nevertheless the (L)CS r-graph may include paths which difer only in the involved blank nodes (see Figure 1) and would generate identical sentences in the explanation. Thus, we include only once such a content in the text under construction. 2Serialization uses the method (https://rdflib.readthedocs.io/en/stable/plugin_serializers.html). 3https://aclweb.org/aclwiki/Downloadable_NLG_systems 2. Text Structuring Our (L)CS is an r-graph whose root is a blank node and that includes triple paths always RDF-connected to the root, involving triples with variable RDF-distance from the root (see the example at the beginning of this section). Such paths are considered equally informative and then presented in the order they appear in the (L)CS. 3. Sentence Aggregation We present each RDF path to the root in a single sentence. 4. Lexicalisation The lexicalization of triples depends on the RDF-distance form the root. We always generate a pronoun (depending on the RDF-distance) for the subject, a verb in past tense for the predicate and a noun for the object. When the object (respectively the predicate) is a blank node, we generate a phrase ("some generic resource"), that can be further explained through a relative sentence when the object (respectively the predicate) has successors in the r-graph (i.e., when the path to verbalize has length greater than 1). 5. Referring Expression Generation The entities to describe in our text correspond to the RDF resources which stand as triple subject at any level of the RDF path to consider. We collect all such information around the root, generating sentences whose main subject is the phrase corresponding to the root ("They all"). 6. Linguistic Realisation The final text is generated by following a human-crafted grammarbased approach. The main rules of the grammar are given below, with the conventions that terminal symbols are quoted, and that vertical bar represents a choice between two forms of a rule.
CS RC → "They all" Predicate (Noun | Noun RC ) → "which" Predicate (Noun | Noun RC ) where is a nonterminal representing a relative clause. The nonterminals Predicate and Noun describe the (finitely many) predicates and nouns that linguistically realize terms in predicate- and subject/object-positions of a triple, respectively. Blank nodes are linguistically realized as "some generic resource" (see next section). As an aside, note that since Predicate and Noun produce a finite number of terminals, substituting all such terminals in the above rules yields a (very lengthy) right-recursive Type-3 Grammar. Jumping over some details about linguistic realisation, the reader can verify that one of the phrases such grammar can generate is indeed "They all mention some resource which is involved in videogames", that explains the example of the RDF path shown above. We use such a grammar as a guidance in the implementation of the linguistic realisation, with a breadth-first strategy: that is, taking all (say, ) RDF-paths contained in the CS, we follow the first triple of each one of them, generating phrases that are complete if the path has length 0 (just one triple), or they contain a nonterminal RC when the path has length ≥ 1. Then we follow each path one triple further, and add their verbalization substituting all non terminals RC once. We proceed, until no path extends further. This breadth-first generation of phrases make it easier to perform subsequent verbal improvements, e.g., subject sharing, sentence coordination, etc.
In the rest of this section, we delve into some implementation details. The uninterested reader can jump to the next section to see the results we obtained.
In brief, Algorithm 2 takes an r-graph in input and describes its root by generating a verbose human-readable explanation of its triples set.
If the input r-graph is the CS of a group of diferent resources (like the one returned by Algorithm 1), the root is a blank node and the generated text summarizes common features among analyzed resources.
Algorithm 2: The algorithm returns a dictionary storing for each explored RDF-distance (dictionary key), the text generated for explanation (dictionary value) 1 _ (⟨, ⟩, , _);
Input : • ⟨, ⟩: the r-graph to explain; • : the RDF-distance for r-graph exploration; • _: a dictionary with keys indexing all URIs defined in the name-space and values storing the English terms corresponding to them;
Algorithm 2 starts the exploration of ⟨, ⟩ from its root node and returns a dictionary, , storing, for each explored RDF-distance, the text generated for its explanation; is initialized to an empty dictionary at Row 2.
The main loop of Algorithm 2 (Rows 5–17) is responsible for iteration over diferent RDFdistance values (up to the input ): for each RDF-distance, it computes an _ which is initialized as empty at every iteration (Row 6) and added to the final in Row 16.
The loop in Rows 7–15 analyzes all resources present in _ (but not in ) and, for each of them, finds all the triples, , in rooted in (Row 8). Then, is put in the array of already explored resources (Row 9). For each such that is not empty, the subroutine __ (see Algorithm 3) is called in Row 11 to perform the linguistic realization of triples rooted in . In particular, Algorithm 3 returns, for each node: Algorithm 3: The algorithm returns, for a single node, the output text to generate, the list of nodes yet to be explored and a data structure supporting the writing of relative sentences at every RDF-distance. 1 __(⟨, ⟩, _);
Input : • ⟨, ⟩: the r-graph of the node to explain; • _: the dictionary of URIs defined in the dataset; • _: a dictionary storing, for each node identifier, the linguistic realization of the triples rooted in the node; • _ℎ: a list of nodes to be explored in next stages of iteration by Algorithm 2 ; • _: a dictionary storing indexes and descriptive triples of nodes to be explained through relative sentences.
_ ← "not identified dataset resource"
_ ← "not identified dataset resource"; end add to _ℎ; = _(_, _); if is indexed in _ then
add to _ the generated text (_), the list of nodes yet to be explored (_ℎ) and a data structure supporting the writing of relative sentences at every RDF-distance (_).
Algorithm 2 uses the variable _ to update the running _ (Row 13) and _ℎ to set the array _ (Row 14).
After the execution of the main loop (Rows 5–17), stores, for each analyzed RDFdistance , the related text generated from ⟨, ⟩. The text to generate, at any distance , may refer to nodes that are indexed in _ with key , and whose linguistic realization is stored in _[]. In this case, one sentence relative to is added for each text item in _[] (Rows 18–20).
Algorithm 3 starts by initializing _ℎ to an empty set and _ to an empty dictionary (Rows 2–3). For each triple in , both the predicate and the object are explored to determine a verbal form for them (_ and _). In particular, Algorithm 3 discriminates among 3 diferent kinds of resources: 1. The resource is in the input _, that includes its linguistic realization (see Row 5 and 17); 2. The resource is a blank node, and is explained by the phrase "some generic resource" (see
Row 9 and 20); 3. The resource is neither in the dictionary of defined URIs (Case 1) nor a blank node (Case 2): it is a generic (but not anonymous) resource, which has been given a URI, but which is not further defined in the reference namespace. Thus, a generic phrase—"not identified dataset resource"—is used for its explanation (see Row 11 and 22).
In Cases 2 and 3, Algorithm 3 updates the _ dictionary (Rows 13 and 24) supporting the building of relative sentences in the final output of Algorithm 2. In all cases, the triple predicate and object are added to _ℎ (Row 15 and 26), to be explored in next iterations by Algorithm 2. Also (Row 27), the grammar above (see Linguistic Realization description) is used to generate a text on the basis of predicate and object realizations, through the subroutine _. Such a generated text is assigned to the variable .
Algorithm 3 proceeds (conditional block in Rows 28–32) by adding the triple either to the dictionary _ for nodes indexed in it (and thus to be explained through relative sentences) or directly to _ for other nodes.
The exponential growth in popularity of online social networking systems led to an increasing importance of social media analytic tools for a variety of applications, such as customer segmentation, market analysis and recommendation systems based on collaborative filtering.
By exploiting the information available in Linked Data, our method is able to highlight the semantic properties shared by two or more users on a given platform, producing an easy-to-read, understandable description. In particular, we use two combined datasets as information source: Influence Tracker 4 and DBPedia5.
The Influence Tracker (IT) ontology [ 19] collects activities and interactions over the so-called "Twittersphere" of several users modelled as RDF-graphs and grouped together according to the content they publish. In our examples, we refer to the prefixes in Turtle notation shown below: 4https://old.datahub.io/dataset/influence-tracker-dataset 5https://www.dbpedia.org/ The class it:User models owners of Twitter accounts, either a physical person or a company, in terms of mentions, replies, hashtags, photos, URLs, and so on. The activity of Twitter user accounts is traced through several predicates, useful for catching semantic similarity among diferent users. In our examples, we refer to the predicate it0:hasMentioned, that connects a resource (belonging to class it:User) to users mentioned in its tweets. Notably, the IT service provides an RDF graph, called twitterSimilarity, which traces the connection (through the property it0:hasSimilarity) of Twitter accounts considered similar based on their published content. We use the knowledge modeled in twitterSimilarity to extract the groups of similar accounts to be analyzed in our use case.
In order to enrich the informative content of our explanation, we combined the information in IT with selected knowledge from DBPedia. Such an integration is possible thanks to the high quality of IT dataset, which includes links to URIs in DBPedia, and is then classifiable as 5-stars Linked Open Data [20]. The IT service provides, in fact, the dbpediaGraph, that maps—through the property it0:dbpediaUri—the correspondence between Twitter users in the IT namespace and the related resource in DBpedia, if any.
Following such correspondences, we extract from DBpedia further information about account owners. In our example, we only extract triples including the predicates dct:subject and dbp:industry6.
In the following, we analyze the commonalities of three accounts grouped by similarity in IT: it:instagram, it:dannysullivan and it:jimmykimmel. We first compute a significant CS of the three resources, by flexibly providing an RDF-distance, a set of stop-patterns and a set of uninformative triples. Then, we generate a text linguistically realizing such a CS.
In Figure 1, we focus only on the portion of CS computed at RDF-distance 1 from the root and show the related graph representation. The reader may notice that two diferent paths exist from the LCS root to the two resources "social media" and "videogames streaming services", passing through diferent blank nodes. In the generation of the verbal explanation to return, we notify only one of these paths7, that would be indistinguishable for users unacquainted in RDF.
Figure 2 reports the verbal explanation generated from the LCS at RDF-distance 1 of the three Twitter accounts cited above8.
Again, the explanation coming from the analysis at RDF-distance 1 (Row 96 in Fig. 2) benefits from the verbalization of paths passing through blank nodes, and collecting important commonalities.
Based on a theory on (Least) Common Subsumers in RDF, we built a tool that verbalizes in
the English common language the commonalities between two or more resources in RDF. We
piped our tool to a standard clustering tool applied to the domain of Twitter accounts, in order
6The portion of the DBPedia graph to include in the analysis may be easily adapted to the explanation need.
7It corresponds to a “lean” version [
According to the classification of Samek et al. [21], our tool fulfills at least three objectives of Explanations in AI: 1) verification of the system: it allows users to check for meaningful/clueless clusterizations; 2) improvement of the system: looking at the verbalization, a user can tune the clusterization tool in order to weigh some features more than others; 3) learning from the system: the verbalization makes explicit commonalities that might not be immediately visible by looking at the resources in the cluster.
Future work may include extension both to the LCS construction and to the natural language generation approach. In particular, LCS computation may be extended to consider also paths traversing triples backwards (from the object to the subject). The extension of RDF-LCS to backward RDF-paths is straightforward; yet their verbalization may need a chain of passive relative English sentences, which are less readable than the forward ones. Another future direction is verbalizing a subset of the cluster [22], since when the explanation for the commonalities of a set of resources is too shallow, focusing on the commonalities of a subset of the resources may yield more interesting explanations.
Regarding NLG, the analysis of results suggests some improvements to our approach, at least in the sentence aggregation and in the text structuring tasks. In particular, by looking at Figure 2, the first 95 sentences in the text generated from the CS appear like a list of mentioned accounts and included hashtags, that may be not interesting for all readers. In most cases, a text like "They all mentioned the same 59 Twitter users. They all included the same 36 hashtags." would The resources in analysis present the following properties in common: be enough informative. Thus, as first improvement, we are investigating a diferent sentence aggregation strategy, aimed at returning a more compact explanation when the generated text is too verbose and highly repetitive. This strategy needs to be information-conservative and able to return on demand the full text generated from the CS.
Also, we are designing a diferent approach to text structuring; in this work we structured the text by presenting the sentences generated from the paths in the (L)CS in the order they appear in the r-graph. This causes a random alternation of predicates involved in sentences, as shown in the example in Figure 2 (w.r.t. to predicates "mentioned" and "included the hashtag"). Such a result suggests to present close to each other all sentences related to the same predicate. The new design would significantly benefit also from the introduction of a weighting mechanism for the importance of predicates, to be used for setting the order of presentation of generated sentences.
Projects Regione Lazio-DTC/“SanLo” (CUP F85F21001090003) and “TEBAKA-SISTEMA PER ACQUISIRE CONOSCENZE DI BASE DEL TERRITORIO" (Code ARS01_00815, CUP B82C20000160005) partially supported this work.