In this paper, we present a preliminary approach for automatically discovering the topics of a structured data source with respect to a reference ontology. Our technique relies on a signature, i.e., a weighted graph that summarizes the content of a source. Graph-based approaches have been already used in the literature for similar purposes. In these proposals, the weights are typically assigned using traditional information-theoretical quantities such as entropy and mutual information. Here, we propose a novel data-driven technique based on composite likelihood to estimate the weights and other main features of the graphs, making the resulting approach less sensitive to overfitting. By means of a comparison of signatures, we can easily discover the topic of a target data source with respect to a reference ontology. This task is provided by a matching algorithm that retrieves the elements common to both the graphs. To illustrate our approach, we discuss a preliminary evaluation in the form of running example.
Data-intensive applications (e.g., e-commerce applications, digital libraries, . . . ), which rely on the information stored in private databases, are now common over the Internet. The data behind the application is in general not accessible by external applications and represents the so-called deep web. The value derived from the re-use of this kind of data has been considered of paramount importance for both research and business activities.
For this reason, the research community has put a lot of effort in the last years for searching information in the deep web [13] and extracting knowledge from it [10]. Three key factors have recently affected this well-known architecture for web applications: 1. The Semantic Web vision is now reality. Research outcomes have provided standards, techniques and tools enabling the Web to move from a “Web of Documents”, where the data are typically optimized for the direct human-consumption, to a “Web ? The authors would like to acknowledge the networking support by the COST Action IC1302 (www.keystone-cost.eu) of Data”, where the data is structured thus making it more efficiently and effectively usable by software applications. Moreover, data from different sources can be linked with each other, thus fostering the interoperability of the information.
This is the Semantic Web vision, which is now becoming reality. 2. A large amount of structured data is available in the web. Public Sector and Enterprises have started to consider the web as the primary place for publishing their data with structured and open formats. The EU Commission, for example, is promoting the publication and the reuse of public sector information as open data, so that it can be publicly accessible by other Institutions and Enterprises1. 3. Applications for Data Analytics are now handy. Big data has become a hot trend topic. Data science is now a common term and denotes techniques and applications for extracting knowledge from data [6]. Several software packages, tools, and case studies are now available for managing, extracting, transforming and analyzing large amount of data.
These elements have radically changed the ways for accessing structured data: several data sources are “emerged” from the deep web and are available as open data. A direct user consumption of structured data (not mediated by any application) is now possible. Nevertheless, in this scenario, a new problem arises: how to find the data sources satisfying specific information needs. The usual paradigm for accessing information in the web is based on search engines as the entry points for users looking for information. Unfortunately, search engines cannot be an actual solution since they are not conceived for indexing structured data. Consequently, source retrieval can be a critical task. Some solutions have been proposed to deal with this problem: web portals (see for example the European Union Open Data Portal2) can support this task. In portals, the data sources are in general indexed on the basis of some metadata (e.g., title, author, content description, . . . ) manually provided by the data source owner. This is a tedious and error prone work that can generate biased results if the metadata have not been accurately selected. An automatic data-driven approach for extracting metadata from a target source can help managing this issue.
In this paper, we introduce a preliminary proposal for automatically discovering the topics of a target data source with respect to a reference ontology. Our approach relies on three key elements: a reference ontology, an algorithm for computing the “signature” of a data source, and a graph matching algorithm. We conceive the reference ontology as a vocabulary of concepts and related properties describing a real world domain. The signature is a concise weighted graph-based representation of the data source topics which is independent of the specific vocabulary adopted in the source (i.e. labels used to describe schema elements, and domains associated to the attributes). In particular, nodes represent concepts and attributes. Edges model three kinds of relationships: relationships between attributes belonging to the same concepts, relationships between concepts and the respective attributes and relationships between attributes and concepts. Entropy is used to weight nodes, thus giving an account of their importance in terms of information power. Mutual information is used to provide weights associated to edges, 1 Digital Agenda for Europe, http://ec.europa.eu/digital-agenda/, Pillar I, Action 3 2 https://open-data.europa.eu/ thus measuring the correlation between the involved nodes. We claim that such a signature can be used as a semantic identifier of a domain, i.e. two sources representing the same subject have a similar signature independently of the actual attribute domains adopted. The technique for extracting the signature is a critical task and represents the main contribution of the paper. Finally, a graph matching algorithm is used for comparing the signatures of the reference ontology and the target data source. The goal is the identification of possible matches which correspond to concepts in the ontologies described in the source.
Without loss of generality, in the following, we will focus on RDF data sources. RDF is becoming a standard way for publishing structured data on the web and several sources are available3. Moreover, working with RDF allows us to use DBpedia as reference ontology4. DBpedia is a large knowledge base derived from Wikipedia, which currently describes 4.0 million of “things” with 470 million of “facts”. Thus we can easily evaluate our approach in different domains with different data sets. We will experiment two ways for computing graph weights: one based on the classical computation of entropy and mutual information, the second based on composite likelihood to estimate those values.
The main advantage derived by the estimation of the weights is to reduce the sensitivity to a specific type of estimation error related to underestimation of the probability of rare labels combinations. The classic mutual information is known to be very sensitive to regions corresponding to small probabilities; thus, when label combinations are rare, assigning graph weights based on mutual information is expected to produce unstable results. This motivates the introduction of a composite divergence measure based on a linear combination of divergences. Estimation is based on a composite likelihood methodology, a well-known approach for complex models that has proved useful in statistics and machine learning; see [12] for an exhaustive overview. Our preliminary empirical results suggest increased reliability of the new approach based on out-ofsample performance on real data.
Finally, in this preliminary proposal, we do not investigate any advanced technique for graph matching. We adopt the distance-measure proposed in [9] for evaluating signature matches. Summarizing, the main contributions of this paper are: 1) a model for defining signatures representing topics of RDF sources based on schema information, entropy and mutual information; 2) a technique for computing the estimation of the signature weights; and 3) a preliminary evaluation of our proposal by means of a running example.
The rest of the paper is organized as follow: Section 2 introduces the problem, Section 3 describes our proposal for estimating the weights and in Section 4 a running example provides the reader an intuition of our approach. Section 5 describes some related work and finally in Section 6 we sketch out some conclusion and future work. 3 See for example http://linkeddata.org/data-sets for a list of possible data sets. 4 http://dbpedia.org/
Let us consider RDF sources with a RDFS schema as a Knowledge Base. We model the schema information as a total dependency graph where each node represents either a concept or a property of the knowledge base, and edges can represent: 1) EP P , relak tionships between properties related to the same concept k (i.e. there is an edge between two nodes representing properties if the properties have the same concept as domain), 2) ECP , relationships between concepts and properties (i.e., there is an edge between a k node representing a property and a node of representing concept indicated as domain), and 3) EP C relationships between properties and concepts (i.e., there is an edge bek tween a node representing a property and a node of representing concept indicated as range, if any). For completeness, in the rest of the section we provide a formal definition of the signatures5.
Definition (Knowledge base) Let L be the set of literals, U the set of URIs. A knowledge base is a set of triplets KB (U U (U [ L)). We use R = fr 2 U j 9(s; p; o) 2 KB : (r = s _ r = o)g to represent the set of resources, P = fp j 9s; o : (s; p; o) 2 KBg to represent the set of properties, and C = fc j 9s : (s rdf : type c) 2 KBg to represent the set of concepts.
Definition (Properties of a concept) Given a concept k 2 C, the set of properties of k, Pk is defined as Pk = fp j 9r1; r2 2 R; p 2 P : (r1; p; r2) 2 KB ^ (r1 rdf : type k) 2 KBg [ fp j 9r1 2 R; p 2 P; l 2 L : (r1; p; l) 2 KB ^ (r1 rdf : type k) 2 KBg.
The properties of a concept need to be better qualified for the definition of the total dependency graph. In particular, we define Definition (Set of Property-to-Property (P-P) relationships) Given a concept k 2 C, we define its set of Property-to-Property (P-P) relationships EP P as the set of relak tionships existing between properties having the concept k as domain. More formally, EkP P (Pk Pk).
Definition (Set of Concept-to-Property (C-P) relationships) Given a concept k 2 C, we define its set of Concept-to-Property (C-P) relationships EkCP as EkCP = f(k; pj ) j pj 2 Pkg. This is the set of relationships holding between a concept k and its properties Pk.
Definition (Set of Property-to-Concept (P-C) relationships) Given an object property, its range concept is defined as Cprange = fk j 9o 2 R; 9s : (s; p; o) 2 KB ^ (o rdf : type k) 2 KBg. We define the set of Property-to-Concept (P-C) relationships of a concept k 2 C, as EP C = f(pj ; c) j pj 2 Pk ^ c 2 Cprjangeg. This is k the set of relations between properties and their target concepts.
The Total Dependency Graph summarizes all these kinds of semantics in a unique graph as follow. 5 We extend the notation used in [16]. In a similar way, we do not model blank nodes to keep the presentation clear.
Organisation
< employer > Literal < eyeColor >
Person
< birthPlace > < birthName >
Place
Literal eyeColor Definition (Total Dependency Graph - TDG) A Total Dependency Graph - TDG is the quintuple T DG = (C; P; EP P ; ECP ; EP C ) where: C and P are set of nodes, representing concepts, and properties respectively, and EP P ; ECP ; EP C ) are sets of edges denoting: – EP P = S EkP P , the union of the sets of the P-P relationships built for each k2C concept in the knowledge base; – ECP = S EkCP , the union of the sets of C-P relationships built for each concept k2C in the knowledge base; – EP C = S EkP C , the union of the sets of P-C relationships built for each concept k2C in the knowledge base.
Fragments of a Total Dependency Graph concerning only one node associated to a concept are simply called Dependency Graphs.
Definition (Dependency Graph - DG) The Dependency Graph of a (reference) concept k 2 C is defined as DGk = (Pk; EkP P ).
Example 1. In Figure 1 a small RDF Schema and its corresponding TDG are shown. Classes and properties of the RDF schema are transformed into nodes in the TDG. Edges between nodes representing properties (EP P ), connecting the reference class with its attributes (ECP ), and connecting properties with external classes (EP C ) are shown.
The signature of a structured source is represented as a TDG with weigthed nodes and EP P and ECP edges. EP C are not weighted since they represent possible connections between classes in the data source.
A characterization of signatures is carried out by determining a weighted graph that summarizes the topics of a source. The weights in such graphs can be assigned using two basic information-theoretical quantities: entropy and mutual information [9]. After defining such quantities, we discuss their estimation based on data samples by composite likelihood techniques.
Definition (Entropy) Let X be a random variable representing an attribute with alphabets X and probability mass function p(xj ), with unknown parameters 2 Rp. The entropy H(X) is defined by H(X) = EX log p(Xj ), where E( ) denotes expectation with respect to p(xj ).
Note that the above definition does not involve realized values for data instances, thus making the signature independent of the class represented. In particular, entropy describes the uncertainty of values in an attribute. Thus, one problem is estimation of H(X) from available data instances by means of some appropriate approximation of p(xj ). If n samples of X are available, then an estimate ^ can be obtained by some statistical estimation method, such as maximum likelihood estimation, so that H(X) could be estimated by using = ^ in the definition above. To measure the information shared by two attributes at the time we introduce the concept of mutual information. Definition (Mutual Information) Let X and Y be two random variables representing attributes with alphabets X and Y with joint mass function p(x; yj XY ) and marginal mass functions p(xj X ) and p(yj Y ). The mutual information of X and Y is: p(X; Y j XY ) p(Xj X )p(Y j XY ) I(X; Y ) = EXY log = H(X) + H(Y )
H(X; Y )
(
Firstly, note that I( ; ) measures different levels of association (or shared information) between pairs of nodes. If the association is strong, then the estimated joint frequency p(x; yj XY ) is large compared to the estimated frequency of separate nodes, p(xj X ) and p(yj Y ). Secondly, note that similarly to entropy, also the mutual information needs to be estimated from data instances. To estimate I(X; Y ) we need to obtain parameter estimates ^X , ^Y , and ^XY . In our approach, entropy and mutual information are computed by means of the cardinality of the URI for nodes representing concepts and the cardinality of the range for nodes representing properties.
We remark that in the proposed TDG, a node can assume different roles (i.e., it can be the reference concept in a DG, the range value of several properties according to the source schema). This means that, depending on the role considered, a concept can assume different cardinalities: it may vary from its maximum value, when a concept node is considered as alone in a DG, to a number of other possible values, one for each property it is involved. As a consequence, its entropy and the mutual information of its edges may assume different values.
The method for estimating H(X), H(Y ) and H(X; Y ) from data samples is crucial to obtain representative signature. A suitable method should be able to prevent over-fitting. The estimated signature does not have to perfectly replicate a specific data source, but rather provide us with a synthetic representation of a reference ontology which, in turn, should describe a more complex real world. Over-fitting is important in the presence of very large alphabets for the attributes under exam, with only a few observed instances. The elements of the alphabets with very low frequency typically inflate the overall noise thus deteriorating the quality of the available information.
Another issue related to the high dimensionality of the problem is computing. The high number of instances usually collected in the RDF knowledge bases available online makes the calculation of the actual values expensive from the computational point of view. For example, the class Person (one of the 529 classes which form a subsumption hierarchy) of the DBpedia Ontology (version 3.9) contains 832.000 instances and has 101 properties. This means that the cardinality of the set EP P built considering only the class Person is 5,050. To address the above issues, we propose an approach for an approximate computation of entropy and mutual information. 3.1
Parameter estimation Let Y be an attribute of a binary alphabet y = (y1; : : : ; yq) 2 f0; 1gq. If the discrete alphabet is not binary we convert it into a binary alphabet. The full dependency of q labels can be represented by the joint distribution p(yj ), 2 . We consider a composite likelihood function constructed from marginal models, p(yijx; i) (i = 1; : : : ; q), and pairwise models, p(yi; yj j ij ) (1 i < j q). Here f ig and f ij g are two sets of parameters vectors for univariate and bivariate models. The marginal and pairwise densities are combined to form the composite model p(yj ; w) = q Y p(yij i)wi Y p(yi; yj j ij )wij ; i=1 i<j where w = (woTw; wpTw)T is a vector including nonnegative elements wow = fwi : i = 1; : : : ; qg and wpw = fwij : 1 i < j qg. These are importance parameters determining the contribution of the marginal and pairwise in the composite likelihood function. Estimation of the joint distribution of two attributes (X; Y ) will be analogous.
Given a set of N training samples D = fyngnN=1, we compute the maximum composite likelihood estimator (MCLE), ^, defined as the maximizer of the log-composite likelihood function `( ; w)
N X log p(ynj ; w) = n=1
N
Y L( ; wjyn):
n=1
Since parameters in different sub-likelihood components are independent, the MCLE
may be computed by maximizing separately marginal and pairwise log-likelihood
func(
i ^ij = argmax ij
N
X log p(yinj i); 1 i
n=1
N
X log p(yin; yjnj ij ); 1
n=1
q;
i < j
q:
(
Weights selection
The estimated one- and pair-wise models, f (yinj ^i) (1 i q) and f (yin; yjnj ^ij ) (1
i < j q), are combined by composite likelihood decomposition in (
N ) X log p(yinj ^i) ; 1 i n=1 N ) X log p(yin; yjnj ^ij ) ; 1 n=1 q; i < j q: ^ ^ where f ig and f ij g are maximum likelihood estimates computed in the previous section. The method is a type of regularization approach that favors simpler likelihoods by producing weights tending to zero as increases. For sufficiently large , incompatible sub-models are down-weighted to the maximum extent, thus resulting in sparse composite likelihood objects. 3.3
Estimation of mutual information
The mutual information defined in (
H^ (X) = `(^X ; w^X ) = H^ (Y ) = `(^Y ; w^Y ) =
N
X log pX (xnj^X ; w^X )
n=1
N
X log pY (ynj^Y ; w^Y )
n=1
where pX , pY are composite models for X and Y defined as in (
H^ (X; Y ) = `(^XY ; w^XY ) =
N X log pXY (xn; ynj^XY ; w^XY ) n=1 where pXY is the composite model for the variable pair (X; Y ) and f^(Y X); w^(Y X)g denote parameter estimates for the joint model. As a measure of mutual information, we propose to use the following empirical approximation of the mutual information I based on the fitted likelihood functions: Ib(X; Y ) =
N X log n=1 (
pXY (xn; ynj^XY ; w^XY ) pX (xnj^X ; w^X )pY (ynj^Y ; w^Y ) ) = H^ (X; Y )
H^ (X)
H^ (Y ):
Note that to avoid taking expectation over alphabets X and Y as in (
The DBpedia ontology (version 3.9) conceptualizes the real world through a hierarchy structure made of 610 classes (see the DBpedia website for more details6). Each class comprises a rich set of datatype and object properties (e.g., the class Person includes more than 3k properties), and a large number of instances is provided for most of the classes (e.g., there are more than 760k instances belonging to the class Person in the English version, more than 300k belonging to the class Work).
The goal of this preliminary evaluation is to show that signatures can effectively
represent topics. For reaching this purpose, we performed three experiments and we
tested if: 1) Casual partitions of the instances of the same concept provide similar
signatures; 2) The signatures of a concept and the one of some superset concept are close;
3) The signatures of two not related concepts are different. We started our evaluation
6 http://wiki.dbpedia.org/Datasets/DatasetStatistics
(
occupation
Automobile deathPlace by selecting three classes from DBpedia (Writer, Artist, Automobile) and building their TDGs as shown in Figure 2. The first signature represents a fragment of the DBpedia Writer class, including only five representative properties for simplicity. The second TDG describes the Artist class, i.e. a superclass of Writer. Note that both classes share the same properties. Finally, the third TDG represents five properties of the Automobile class. In Figure 2, we show also the weights for representing the actual and the estimated values (in the boxes) of Entropy (on the nodes) and Mutual Information (on the edges).
Since we are interested to evaluate the specific contribution provided by entropy and mutual information alone, we performed separate evaluations, by considering firstly only the nodes (thus measuring the contribution of the entropy) and secondly the edges (thus measuring the contribution of the mutual information). We adopted a Euclidean distance-based metric as, in [9], defined as follows. Let A and B be two equal size dependency graphs and ai, bj the entropy of the node i and j in graph A and B, respectively. Let m be an index that maps a node in graph A into the matching node in graph B (i.e., m(node in A) = matching node in B). The distance metric based on entropy for graph A and B is:
D = pPi (ai bm(i))2
An analogous distance measure can be easily defined by considering the mutual information instead of entropy. The result of our experiments is shown in Table 1, where Rows 1-3 compare signatures obtained by random equal-size partitions of the instances of the concepts Writer, Artist and Automobile (actually, the result shown is the mean of the distance measures obtained evaluating 10 random partition). Rows 4-5 show the distances between the signature of concept Writer and its superset Artist (with correct and random matches between the properties). Rows 6-7 show the distances between the previous concepts (Writer and Artist) and the concept Automobile. The columns of the Table represent the types of distances between the graphs computed: we considered nodes and edges with the standard and the estimated measures for entropy and mutual information.
A qualitative evaluation of the preliminary results shows that all the techniques can detect signatures representing similar or different concepts. Our estimated values produce more polarized values, thus making the understanding of diverse classes easier. Moreover, as in [9], our experiments show that the entropy alone provides a good account of the similarities between the classes. Nevertheless, since we considered only few properties, we found some results not strictly consistent with the data (e.g., the value of the distance between Artist and Writer based on mutual information is higher than the one we were expecting, since the classes represent similar world concepts). Finally, the evaluation would definitely provide better results by considering a distance relying on all the weights (nodes and edges). 4.1
Preliminary discussion
The evaluation shown in the previous section permits us to draw some preliminary
conclusions, which will constitute the basis of our future work.
1. The technique proposed and, in particular, the signature based on approximate
weights is promising: it can effectively support the process of identifying the topics
of a data source.
2. Signatures can also be experimented coupled with other techniques for
detecting similarities between graphs. In particular, we think to obtain better results
with matching approaches based on the source schema, like for instance names of
classes/properties comparisons. In this way, techniques, relying on different kinds
of information, can complement each other.
3. The definition of an effective and efficient algorithm for comparing signatures is
a critical task. The graph matching algorithm should be able to work with: (
To provide users with techniques and tools for automatically understanding the topics of a data source is a hot and challenging issue. The problem is well known in the IR Community, where it is applied to unstructured documents with important outcomes [3]. In the context of structured data sources, the proposed techniques face the issue following three main perspectives: providing summaries, exploiting reference ontologies and supporting users with visual tools.
Summary-based approaches aim to identify and extract a small subset of the information which is representative of the entire contents of the data source. In [14] and [15] two approaches dealing with relational databases and graphs, respectively, have been proposed. Both the approaches compute the closeness between data structures and the importance of the data taking into account entropy and mutual information. In [2], the goal is to summarize an attribute domain. A mix of techniques is applied for clustering the attribute values and identifying in each cluster a single representative value. Ontology-based approaches try to match content and data structures into some reference ontology. Summarized attributes can support the keyword search task as depicted in [1]. The research community in the Semantic Web is studying for fifteen years this process and several algorithms based on heuristic, syntactic and semantic rules have been proposed [7]. Finally, in the data science field, several code libraries and tools have been proposed for extracting visual summaries from the content of a data source (see for example Tableau7 or Gephi8).
Our approach mixes some features from both the summary and the ontology-based approaches. The idea of creating a datasource signature starts from [9] where a depen7 http://www.tableausoftware.com/ 8 http://www.gephi.org/ dency graph is built for supporting schema matching in a data integration approach. In this paper we adapted the approach for RDF sources and we extended the technique with the introduction of different kinds of edges connecting nodes.
Other approaches have applied entropy and mutual information to RDFS graphs (see for example [8]). Nevertheless, in this paper we adopted a novel technique for estimating the mutual information based on composite likelihood.
Finally, it is important to observe that Sindice.com [11], an RDF search engine, could be considered as a possible solution of the problem on hand. Nevertheless, Sindice focuses on finding triples containing particular keywords and not discovering data sources topics. 6
In this paper we presented our preliminary proposal for providing users with an insight of a target data source topic. The approach relies on a reference ontology, a technique for generating signatures and an algorithm for graph matching. The preliminary results show that our proposal can really support the user in this task.
Future work will be devoted to three main tasks. Firstly, we will develop and implement a graph matching algorithm able to effectively match signatures from different data sources. Secondly we will perform a deep evaluation of the proposed approach in different domains and with data sources having different features in terms of numbers of attributes and instances. Thirdly, we will improve the technique for estimating entropy and mutual information to weighting the graph. In particular, we will experiment other statistical measures for evaluating the correlation of the values in order to obtain more effective signatures.