Understanding Ontology Evolution Beyond Deltas

Abstract

The dynamic nature of the data on the Web gives rise to a multitude of problems related to the description and analysis of the evolution of such data. Traditional approaches for identifying and analyzing changes are descriptive, focusing on the provision of a \delta" that describes the changes and often overwhelming the user with loads of information. Here, we take an alternative approach which aims at giving a high-level overview of the change process and at identifying the most important changes in the ontology. For doing so, we consider di erent metrics of \change intensity", taking into account the changes that a ected each class and its neighborhood, as well as ontological information related to the importance and connectivity of each class in the different versions. We argue that this approach will allow a better understanding of the intent (rather than the actions) of the editor, and a better focusing of the curator analyzing the changes; traditional delta-based approaches can subsequently be used for a more ne-grained analysis.

1. INTRODUCTION

With the growing complexity of the Web, we face a completely di erent way of creating, disseminating and consuming big volumes of information. The recent explosion of the Data Web and the associated Linked Open Data (LOD) initiative has led several large-scale corporate, government, or even user-generated data from di erent domains to be published online and become available to a wide spectrum of users [ 1 ]. Dynamicity is an indispensable part of LOD; LOD datasets are constantly evolving for several reasons, such as the inclusion of new experimental evidence or observations, or the correction of erroneous conceptualizations [ 11 ].

Understanding this evolution using the di erences (deltas) between versions of datasets (schema and instances) has been proved to play a crucial role in various curation tasks, like the synchronization of autonomously developed dataset versions [ 2 ], the visualization of the evolution history of a dataset [ 5, 4 ], the need for accessing previous versions of a dataset to support historical or cross-snapshot queries [ 8 ], and the integration [ 3 ] and synchronization [ 6 ] of interconnected LOD datasets. Towards this, various approaches have been used for formally describing those deltas, ranging from low-level deltas (describing simple additions and deletions, see, e.g., [ 12 ]), to high-level ones (describing complex updates, such as, for instance, di erent change patterns in the subsumption hierarchy [ 6 ]).

However, both types of deltas aim at providing a descriptive analysis of the changes, but not at providing an overview of the changes, or the areas of the ontology that were mostly a ected by the change process. Identifying the most affected areas would require a signi cant amount of analysis on behalf of the curator, given that the number of changes recorded are often in the range of several hundreds (or even thousands) [ 6 ]. Moreover, deltas, even high-level ones, do not provide a supervisory overview of the changes, and cannot be easily used to observe trends in the changes. Further, not all changes have the same e ect on the ontology, as some may be minor (e.g., changing the label of a class), whereas others (or their combination) may signi cantly affect the structure or the focus of the ontology as a whole, or of particular areas in the ontology (e.g., the deletion of properties that would disconnect previously connected areas in the ontology, thereby changing its topology and focus).

Our objective in this paper is to identify the classes that were mostly a ected by the evolution process, thereby properly directing the focus of the curator. To do that, we rely on a set of assessment measures that allow quantifying the \intensity" of the changes that each class underwent, based on various assessment dimensions. These dimensions are related to the number of changes a ecting that class or its neighborhood, as well as the e ect of these changes on the centrality and relevance [ 10 ] of the class in the considered versions. These measures, and their combination, will allow appropriate ranking of the classes in the ontology, in terms of \change intensity", under various di erent (complementary) viewpoints. Our approach is demonstrated using experiments from the CIDOC-CRM ontology, con rming the feasibility of our approach and the considerable insights gained on the evolution process.

In Section 2 we describe the assessment dimensions, which are employed in Section 3 for de ning the assessment measures that quantify the importance of the changes related to each class, whereas Section 4 concludes.

ASSESSMENT DIMENSIONS

In this section, we present di erent dimensions that can be combined in order to study various aspects of ontology evolution. Each of these dimensions captures a characteristic that is arguably important in order to quantify the intensity of the changes that a class underwent.

We consider four such dimensions. The rst two are related to the amount (number) of changes that this speci c class (or its neighborhood) underwent during the evolution process and are de ned more precisely in Subsections 2.1, 2.2. The other two are based on the idea that the amount of interest exhibited by the curator related to a class is also related to how important this class is in his ontology, and how this importance changed during the evolution process. To capture the notion of importance, we use two metrics that have been proposed in [ 10 ], namely centrality (Subsection 2.3) and relevance (Subsection 2.4).

Note that our approach is class-centric, i.e., is concerned with identifying the classes that are of most interest to the curator. However, we can easily extend our approach to properties as well. 2.1

Number of Changes

Consider the evolution of a dataset from a version V1 to a version V2. In principle, as presented in [ 6 ], low-level deltas are used to describe the set of triples which were added ( V+1;V2 ) along with the set of triples triples which were deleted ( V1;V2 ) during the evolution from V1 to V2. The number of detected changes over this evolution is the size of their low-level delta V1;V2 , i.e., j V1;V2 j = j V+1;V2 j + j V1;V2 j.

In our case, we are interested in the changes related to a speci c class only, so we use the following de nition: +

Definition 1. Assume the low-level delta V1;V2 = h V1;V2 ; V1;V2 i between two dataset versions V1 and V2, and a class n. We de ne the low-level delta of n between V1 and V2 as V1;V2 (n) = h V+1;V2 (n); V1;V2 (n)i, where V+1;V2 (n) = V2n n V1n, V1;V2 (n) = V1n n V2n and Vin = ft 2 Vijt = (u1; u2; u3); n = uj , for some jg.

Then, the number of changes in which n appears is de ned + as j V1;V2 (n)j = j V1;V2 (n)j + j V1;V2 (n)j. 2.2

Number of Changes in Neighborhood

Apart from the number of changes over a speci c class n, another interesting dimension is the number of changes in the classes \around" n; this allows determining whether the topology of the ontology changed in a particular area. More speci cally, we de ne the neighborhood of a class n for two dataset versions V1; V2 (denoted by NV1;V2 (n)) as the set of classes that are either related to n via a subsumption relationship, or are connected with n via a property (through the property's domain/range), in either of V1; V2. Then:

Definition 2. Consider two ontology versions V1 and V2, and a class n with neighborhood NV1;V2 (n). We de ne the number of changes in NV1;V2 (n) as: j V1;V2 (n)j = Pc2NV1;V2 (n) j V1;V2 (c)j.

N 2.3

Centrality

The notion of centrality [ 10 ] is used to quantify how central is a speci c class in a speci c dataset version. To identify the centrality of a class n in a dataset version Vj , we initially consider the instances it contains by calculating its relative cardinality. The relative cardinality RCVj (e(n; ni)) of a property e(n; ni), which connects the classes n and ni, is de ned as the number of the speci c instance connections between these two classes divided by the total number of the connections of the instances that the two classes have. Then, we combine the data distribution with the number of the incoming/outgoing properties of this class. As such, the in/out-centrality (Cin=Cout) is de ned as the sum of the weighted relative cardinalities of the incoming/outgoing properties:

Definition 3. Assume the class n that appears in an ontology version Vj . The in-centrality CVinj (n) (respectively, the out-centrality CVoujt(n)) of n is de ned as the sum of the weighted relative cardinality of the properties e(ni; n) (respectively, e(n; ni)):

CVinj (n) = CVoujt(n) = m

X RCVj (ni; n) w(ni;n)

i=1 m

X RCVj (n; ni) w(n;ni)

i=1 where m represents the number of the incoming (respectively, outgoing) properties in the schema.

The weights w(ni; nj ) in the above formula have been experimentally de ned and vary depending on whether the property is user-de ned or RDF/S, giving higher importance to user-de ned ones. This is partly because the user-de ned properties correlate classes, each exposing the connectivity of the entire schema, in contrast to the hierarchical or other kinds (e.g., rdfs:comment) of RDF/S properties. More details on the notion of centrality can be found in [ 10 ]. 2.4

Relevance

The notion of relevance [ 10 ] has been proposed as adequate for quantifying the importance of a class within a dataset. Relevance is based on the idea that the importance of a class should describe how well the class could represent its neighborhood. Intuitively, classes with many connections with other classes in the ontology should have a higher importance than classes with fewer connections. Thus, the relevance of a class is a ected by the centrality of the class itself, as well as by the centrality of its neighboring classes. Moreover, since the dataset might contain huge amounts of data, the actual data instances of the class should also be considered when trying to estimate its importance (relevance). Formally, relevance is de ned as follows:

Definition 4. Assume a class n that appears in an ontology version V1. Assume also that the numbers of the incoming and outgoing properties that connect n with other classes are npin and npout, respectively. The relevance of n in V1, RelV1 (n), is the sum of the in- and out-centrality of n multiplied by the corresponding number of these classes, divided by the sum of out-centrality of the incoming classes ni and the in-centrality of the outgoing classes nj : RelV1 (n) =

CVin1 (n) npin + CVou1t(n) npout npin npout

X CVou1t(ni) + X CVin1 (nj )

i=1

ASSESSMENT MEASURES

In this section, based on the assessment dimensions dened above, we provide di erent ways for combining them, resulting in useful conclusions regarding the dataset/ontology evolution. As a running example, we consider two versions of the CIDOC-CRM1 ontology; clearly, our work could be generalized for any two versions of any given ontology. Speci cally, we use versions v3.2.1 and v3.3.2, that we will subsequently call V1 and V2, which were released in February and October of 2002, respectively.

Table 1 illustrates a sample of classes that appear in both versions with their values of the assessment dimensions. The values of the assessment measures introduced in this section appear in Table 2. 3.1

Deltas Change

The most obvious metric is related to the number of changes that a ected a particular class n. An important additional concern in this respect is that the changes on the neighborhood may be relevant as well; even if a class itself did not change much, many changes in the class' neighborhood may indicate that this class is interesting from the evolution analysis perspective. Thus, we de ne the delta change of a class as the weighted sum of the number of changes involving n and the number of changes involving neighbors of n: ChangeV1;V2 (n) = j V1;V2 (n)j + j VN1;V2 (n)j The parameters , can be used by the curator to ne-tune this metric, by assigning a di erent weight on the number of changes in the class or the number of changes in the neighborhood, depending on the application. For instance, if the curator is not interested in the changes of the neighborhood, he could consider setting = 0; for this case, the class E7.Activity would have a score of 28 (see column j V1;V2 (n)j in Table 1). If, on the other hand, the curator wants to consider both types (class and neighborhood) as equally important, then he could set, e.g., = = 1; this is the case for Table 2, where the score Change of E7.Activity is 119. 3.2

Change of Centrality and Relevance

An indirect way of measuring the e ects of a change on a class is by determining how much the importance of a class changed by means of the change in its centrality or relevance. This is, in many cases, superior to the simple counting of changes, because it shows the cumulative e ect of these changes on the class; and not all changes have the same e ect. For example, we notice that, even thought the classes E7.Activity and E2.Temporal Enity have the same number of changes (28 { see column j V1;V2 j), the changes of the E2.Temporal Enity have had a greater impact on its centrality. A closer look at the changes a ecting these classes will reveal that the latter is involved in the addition of 27 new relationships, which increase its connectivity.

To capture this idea, we provide metrics that compute the absolute di erence of the (in/out) centrality before and after the change; we also provide a metric that combines in and out centrality. Formally:

CVin1;V2 (n) = jCVin2 (n) CVou1;tV2 (n) = jCVou2t(n)

CVin1 (n)j

CVou1t(n)j

1http://www.cidoc-crm.org/official_release_cidoc. html

A step further of the centrality, the relevance indicates the representative power of a class, as regards its area/neighbourhood. The absolute di erence of the values of this measurement in versions V1 and V2 re ects the change in the importance of a class during the evolution from V1 to V2: RelV1;V2 (n) = jRelV2 (n)

RelV1 (n)j In our running example (Tables 1, 2), the class E55.Type has greater CVov1;eVr2all than the class E3.Condition State, however relevance exhibits the opposite behavior, that is, E3.Condition State has higher RelV1;V2 than E55.Type. This observation indicates that even though the change of E3.Condition State's connectivity is imperceptible, the importance of the class is in uenced to a great extent by the changes of its neigbourhood. As such, the focus of the speci c area has probably been shifted.

Clearly, the information about the changes of each neighbourhood provides an overview of the evolution of each area (and its classes). Although the ChangeV1;V2 takes into consideration the changes on the neighbourhood, the RelV1;V2 o ers a more intuitive outcome. Taking as example the classes E3.Condition State and E7.Activity, the latter has the greatest value (119) of ChangeV1;V2 in the speci c sample, while the corresponding value for E3.Condition State is only 34. On the other hand, the di erence of relevance values from V1 to V2 for the class E3.Condition State (see column RelV1;V2 ) is one of the highest in Table 2, meaning that the e ect of said changes in the importance of E3.Condition State were signi cant. Overall, we conclude that ChangeV1;V2 considers the changes (on the class itself or its neigbourhood) equally important, whereas RelV1;V2 re ects the evolution of class importance according to the trend in the changes in its surround area. 3.3

Combined Change

Note that, in some cases, di erent changes on the same class may \cancel out" the net e ect on the importance of the class. In this case, the metrics of Subsection 3.2 may not be fully adequate. In this section, we provide a combining function that considers both the change of importance (in particular, of relevance) of a class, and the changes that this class (and its neighbourhood) underwent, essentially balancing between the two alternatives above:

CCV1;V2 (n) =

ChangeV1;V2 (n)

RelV1;V2 (n)

ChangeV1;V2 ).

Our objective here is to compute an aggregated score for the class based on its behaviour on a pure quantitative measure that cares only for numbers of changes and a more sophisticated measure that additionally regards the evolution of the connectivity of the class in the ontology. For example, in Table 2, we can see that although the classes E7.Activity and E28.Conceptual Object have similar values for RelV1;V2 , their CCV1;V2 di ers signi cantly, due to the di erent number of changes a ecting those classes (see column

CONCLUSIONS

In this paper, we proposed measures that can be used to assess the evolution intensity of each class in a given dataset version. This is intended as an aid for the curator, allowing him to quickly get an overview of the most important CIDOC-CRM Class E7.Activity E2.Temporal Entity E28.Conceptual Object E55.Type

E3.Condition State CIDOC-CRM Class E7.Activity E2.Temporal Entity E28.Conceptual Object E55.Type E3.Condition State 1,25 2,29 0,22 1,47 0,38 0,33 0,35 0,054 0,31 0,09 0,56 0,63 0,32 0,59 0,39 changes, and properly focusing on the truly important ones. Our work is motivated by the fact that deltas are not suitable for providing an overview of the evolution process, as they are too descriptive (at a very detailed level), and often large and overwhelming for the curator. Towards this aim, we considered several dimensions that capture information on the number of changes, the centrality and the relevance of the ontology classes between di erent dataset versions and studied how to combine them to provide measures and useful insights on the ontology evolution.

As a future work, we plan to consider alternative assessment measures, e.g., measures that rank higher the classes that are important for the ontology, even if the changes that they underwent are minor; we may also consider alternative combinations of assessment dimensions and measures. To evaluate our approach, we plan to perform a user study; our usability experiments will consider the overhead imposed to the users for understanding the degree of change between two ontologies versus how well the proposed measures conceive the changes.

Moreover, given our set of assessment dimensions or measures, possibly augmented by additional ones, we envision to o er a number of di erent, user-de ned, ways for combining them in order to determine complex assessment measures that provide helpful deductions regarding an ontology evolution and take explicitly into account the information needs of particular users. For example, a user may choose to combine the assessment dimensions based on the notion of attitude. We consider two types of attitude: the overriding and the combinatory one. Assume, for instance, the simple case in which we have only two assessment dimensions, namely A and B. Then, in the overriding attitude, one of the dimensions, say A, is given priority over the other, meaning that B is somehow applicable only when A is not (e.g., consider a user that cares for changes in the neighborhood of a class only when there are no changes on the class itself). In the combinatory attitude, both A and B contribute to the nal assessment measure. For example, assume a user that considers equally important the number of changes of a class with the change of the relevance of the class between these two versions. These are similar to the standard preference methods for prioritized and pareto composition [ 9 ].

Interestingly, we believe that the issue of allowing users to de ne their own assessment measures arises not only when aggregating di erent choices of a single person, but also when aggregating choices of di erent people (modeling the needs of groups of users). In the former case, there is a need to combine di erent criteria that are posed by a single user, whereas in the latter case, we seek to reach a consensus among the members of the group. As a short-term goal, we plan to integrate such a capability to our system for visualizing the evolution of an ontology [ 7 ]. 5.

ACKNOWLEDGMENTS

This work was partially supported by the EU projects, DIACHRON (FP7-601043), MyHealthAvatar (FP7-600929) and iManageCancer (H2020-643529).

References

[1] V. Christophides , V. Efthymiou , and K. Stefanidis . Entity Resolution in the Web of Data. Synthesis Lectures on the Semantic Web: Theory and Technology . Morgan & Claypool Publishers, 2015 .

[2] R. Cloran and B. Irvin . Transmitting RDF graph deltas for a cheaper semantic Web . In SATNAC , 2005 .

[3] H. Kondylakis and D. Plexousakis . Ontology evolution without tears . J. Web Sem ., 19 : 42 { 58 , 2013 .

[4] H. Kondylakis and D. Plexousakis . Exploring RDF/S evolution using provenance queries . In Workshops of EDBT/ICDT , 2014 .

[5] N. F. Noy , A. Chugh , W. Liu, and M. A. Musen . A framework for ontology evolution in collaborative environments . In ISWC , 2006 .

[6] V. Papavasileiou , G. Flouris, I. Fundulaki , D. Kotzinos , and V. Christophides . High-level change detection in RDF(S) kbs . ACM Trans. Dat . Syst., 38 ( 1 ): 1 , 2013 .

[7] Y. Roussakis , I. Chrysakis, K. Stefanidis , and G. Flouris. D2V: A tool for de ning, detecting and visualizing changes on the data web . In ISWC , 2015 .

[8] K. Stefanidis , I. Chrysakis , and G. Flouris . On designing archiving policies for evolving RDF datasets on the web . In ER , 2014 .

[9] K. Stefanidis , G. Koutrika, and E. Pitoura . A survey on representation, composition and application of preferences in database systems . ACM Trans. Dat . Syst., 36 ( 3 ): 19 , 2011 .

[10] G. Troullinou , H. Kondylakis , E. Daskalaki, and D. Plexousakis . RDF digest: E cient summarization of RDF/S kbs . In ESWC , 2015 .

[11] F. Zablith , G. Antoniou, M. d'Aquin, G. Flouris , H. Kondylakis , E. Motta , D. Plexousakis , and M. Sabou . Ontology evolution: a process-centric survey . Knowledge Eng. Review , 30 ( 1 ): 45 { 75 , 2015 .

[12] D. Zeginis , Y. Tzitzikas , and V. Christophides . On computing deltas of RDF/S knowledge bases . ACM Transactions on the Web , 5 ( 3 ): 14 :1{ 14 : 36 , July 2011 .