Introduction

Ontology is commonly defined as a formal, explicit specification of a shared conceptualisation [14], and often has been used for modelling concepts of the world. Due to the experts' limitations of producing a complete image of the world with flexible boundaries for a domain, change is inevitable. Change in ontologies has some common causes [29]: change in the domain, change in the shared conceptualisation, or change in the specification. Ontology update has been a subject of debate for many years, and many methods have been proposed to address it. Ontology evolution and ontology learning are among these proposed methods. Ontology evolution is "the timely adaptation of an ontology to the arisen changes and the consistent propagation of these changes to dependent artefacts" [39], such as systems defined in [5,30,22,40,13,4,42,19,21]; ontology learning involves changing an ontology automatically or semi-automatically by consulting some structured data sources, such as databases; semi-structured data sources, such as WordNet, or Cyc; or some unstructured data sources, such as text documents and web pages [10]. A few examples of ontology learning systems can be found in [20,9,36,27,11,41,33].

Changing an ontology involves both changing the concepts and the relations. Ontology relations have been divided into two categories: taxonomic relations such as subClassOf and disjointWith in OWL [2], and non-taxonomic relations which covers most of the other OWL relations. On one hand, taxonomic relations provide a structure to ontologies and are crucial. On the other hand, non-taxonomic relations by presenting meaning add depth to the ontology. Regardless of using the term ontology evolution or ontology learning, commonly, ontology update involves changing both taxonomic and non-taxonomic relations.

A fundamental design operation for having a successful ontology evolution application includes concept addition [24,15]. To address concept addition, two approaches (Approach I (see Section 4.1) and Approach II (see Section 4.2)) have been introduced in which ontology graphs (see Section 2) and semantic similarity (see Section 3) have been employed.

Ontology Graph

The definition of an ontology in this paper is a set C of concepts and a set of relations R 1 , . . . , R n , R i ⊂ C × C. Since multiple relations with different labels are allowed to exist in ontologies, labelled graphs also known as multigraphs (G = (V, E 1 , . . . , E n )) with the set of vertices V ⇐⇒ C and a set of edges E i ⇐⇒ R i are a logical choice of representing them. A graph with the stated characteristics is called an ontology graph and is able to cover all important structural OWL ontology features including individuals, classes, relations, object properties, datatype properties, and restrictions [23]. The notion of ontology graph in this work is an extended version represented in [26,16,34,17,3,25]; vertices represent concepts, individuals, restrictions, and values, and edges, include taxonomic OWL relations, such as subClassOf and disjointWith, and non-taxonomic relations.

Semantic Similarity

A successful ontology change application must be able to detect what needs to be changed, gather sufficient information about the element that needs to be changed, and finally decide how to implement change. Extracting relevant and sufficient information is crucial. In this work, WordNet [38] and Wikipedia as general purpose semi-structured data sources are consulted; they both are capable of generating semantic similarity distances between concepts. Semantic similarity between two or more concepts refers to the level of closeness that their meanings possess, and it is very difficult to acquire. It is common practice to use ontologies for computing the distance between two concepts and normalising the final result. In RiTa WordNet [18], the minimum distance between any two senses for the two words in the WordNet tree is returned and the result is normalised; if there is a similarity a number is retuned, and 1 if no similarity is found.

This work has generated semantic similarities from Wikipedia as well. Although many have mentioned that Wikipedia is much richer and a far better source [35,7,32,37], the result acquired from Wikipedia were not as promising as WordNet. Often semantic Wikipedia APIs only consult the infoboxes for generating semantic similarity; lack of word sense when extracting concepts is identified as another shortcoming [37].

Methodology

Ontology development is highly dependent on ontology experts, and domain experts. The perception of an expert about a correct or an incorrect relation may differ from another expert. This issue has contributed to the complexity of ontology development and update. Nonetheless, this work proposes that when adding a non-taxonomic relation, provided that the consistency of the ontology holds and the ontological statement is semantically correct, the new statement is as welcomed as any existing statement. For example when given the three concepts Student, Library, and Group, and the relation memberOf, an expert might generate Student memberOf some Library, Student memberOf some Group, or both. Absence of either of these two statements will not make the ontology incorrect but in certain circumstances it can be claimed that the ontology is less accurate. The same justification holds when a system is automatically generating non-taxonomic statements.

Commonly when generating non-taxonomic statements, a common approach is to provide a set of possible properties for each concept, rank them according to their frequencies, and finally according to some criteria select the highly probably one. However, this work does not intend to generate new properties for concept, but to assign an existing property to an input concept. Non-taxonomic relations can be classified into two general groups: object properties (intrinsic and extrinsic), and data-type properties [28]. The aim of this work is to generate intrinsic properties for a new input concept based on the existing intrinsic properties. The hypothesis is that siblings of a vertex in an ontology graph often have the same intrinsic properties assigned to different concepts.

In this work, the complete set of possible answers (Ans list) is generated, and the existing statements in the ontology (Cur list) are extracted. Ans list is a combination of an input concept I, the set of vertices V = V 1 , V 2 , . . . , V n , the set of edges E = E 1 , E 2 , . . . , E n , and the set of restrictions. Note that in this work only the two restrictions some and only are considered. Sample statements for the following approaches are as follows:

Existing Statement: V 1 E 1 some V 2 Generated Statement: I E 1 some V 3 4.1 Approach I

The members of list Ans for an input concept I, m vertices, the two restrictions, and n edges will be 4 × m × n which comparative to list Cur are numerous. This approach consists of a number of filters to prune Ans list according to Cur list with the aid of various semantic similarities. To be able to apply semantic similarities, a random entropy or self-information approach has been selected. Probability of the event of randomly connecting a to b by an R i relation is defined by P (e) = P ((a, b) ∈ R i ). The prior probability therefore being P (e) = 1 k , where k is the number of possible links (a, b) ∈ R i . Given some semantic similarity distances (see Section 3) s(a, b) ∈ [0, 1], the posterior probability of a connection assuming a dependency between e and s(a, b) is:

P (e | s(a, b)) = P (e)

Since s(a, b) is a similarity distance (taking values in [0, 1] with 0 corresponding to the most similar), it can be assumed that the posterior probability of connection monotonically depends (∝) on 1 − s(a, b):

P (e | s(a, b)) ∝ 1 − s(a, b)

The monotonicity for two events e 1 = (a, b) and e 2 = (a, c) means the following:

s(a, b) ≥ s(a, c) ⇐⇒ 1 − s(a, b) ≤ 1 − s(a, c) =⇒ P (e 1 | s(a, b)) ≤ P (e 2 | s(a, c))

The probability can be used to compute self-information as follows [6]:

h(a, b) = − log(P (e | s(a, b))) ≈ − log(1 − s(a, b)))(1)

The first filter is called hierarchy filtering; it is based on the patterns of the siblings of the input concept. A sibling is referred to a concept with a disjoint-With relation. This work focuses on non-taxonomic patterns. For the input concept I, assuming that one of the statements in Ans is IE 1 onlyV 1 , the patterns would be IE 1 only and E 1 onlyV 1 . This approach only makes use of the forward patterns which in this example is E 1 onlyV 1 . Any member of the Ans list which does not contain the same pattern as one of the members of Cur list will be excluded from Ans. Also, if the input concept I and the first concept of a member of Cur list do not have the same parent, the statement will be excluded from Ans. Presuming both the pattern and the parent is matched, when the success rate of comparing the generated statement with all the members of Cur list is more than 50%, the statement will still remain in Ans, otherwise dropped. At this stage, only the statements with the patterns similar to the existing nontaxonomic statements remain.

From this point onwards, Equation 1 will aid the pruning process. For the second filter

Q 1 = h(I, E 1 ), Q 2 = h(V 3 , E 1 ), Q 3 = h(V 2 , E 1 ), and Q 4 = h(V 1 , E 1 ) are generated. The goal of this filter is to investigate Q 1 + Q 2 ≤ Q 3 + Q 4 ∈ [0.1];

if in more than half the occurrences this function holds, then the generated statement will be accepted; otherwise rejected. The aim is for the self-information of the generated statement to be less than or equal to the self-information of the current statements.

For the third filter Q 5 = h(I, V 1 ) and Q 6 = h(V 2 , V 3 ) are calculated. This filter will examine that in more than half the occurrences

Q 5 ≤ Q 6 ∈ [0, 1] holds.

The forth filter will generate

Q 7 = h(I, V 2 ) and Q 8 = h(V 1 , V 3 ); the relation Q 7 ≤ Q 8 ∈ [0, 1]

must hold in more than half the occurrences for the generated statement to be accepted.

The last filter will generate the self-information among all the members of the generated and the current statement:

Q i = h(Statement f rom Ans list, Statement f rom Cur list)

The result generated by Q i are sorted and the k most similar statements selected. Tables 1 and 2 display the results when k = 2.

Approach II

The members of the Ans list have to be pruned according to the members of Cur list. A comparison between all the members of both lists is made. Providing that a statement from one of lists has the same relation and restriction (for example E K Some or E K Only) as the other list, the occurring pattern and its frequency is recorded. The list containing the patterns P at will be sorted ascending with regard to the frequencies, and the top half selected. Those statements in Ans which do not contain these patterns will be omitted from the final answer pool.

The statement V 1 E 1 some V 2 contains two patterns; (1) E 1 some V 2 and (2) V 1 E 1 some.

The aim of this step is to prune Ans list according to the patterns in Cur list; there is a trade off to this filter, some semantically correct statements will not be validated due to the low or lack of frequencies.

Hierarchy filtering as discussed in approach (I) will filter the remaining members of the Ans list. When the siblings of the input concept contain a nontaxonomic relation which have occurred in more than 50% of the cases and this taxonomic relation is among the remaining members of the Ans list, this statement will be accepted, otherwise rejected from Ans list.

Transitive Reduction

Both of the introduced approaches have the potential of producing transitive relations, which from the consistency point of view have to be eliminated. Inheritance through the hierarchy has to be modelled in an ontology graph. Transitive reduction on directed graphs is the answer to this problem. Presuming there is the possibility of representing information in the directed graph G with fewer arcs than the current amount, then that is the solution [1]. Graph G will be the transitive reduction of G if it satisfies the following conditions:

1. A direct path between v and u in G exists, if a direct path between v and u in G exists. 2. There is no graph with fewer arcs than G satisfying the above condition.

For approach (II), since all the remaining members of the Ans list are selected, transitive reduction is applied after the last step. However, approach (I) is more complicated due to selecting the top k generated relations. Transitive reduction can be applied before or after the top k selection, which this work has adopted the latter. Regardless of the approach, in situations in which a child inherits a property and the algorithm identifies this transitive property, the property is dropped.

Evaluation

This work has adopted an evaluation mechanism based on precision and recall measurements [8,12]. The strategy is to select a well-structured ontology and after converting it into an ontology graph, detach the vertices one by one; the system will attempt to reattach the vertex to the graph optimally with the original relations and at the original location [31]. A comparison between the number of removed edges in the original ontology graph (O) and the modified graph (O ) is made. Assuming concepts c 1 and c 2 and relation R k are present in O , the hypothesis is to examine O and determine whether c 1 and c 2 are related by R k or not. Accepting the hypothesis indicates that O contains an edge corresponding to c 1 R k c 2 ; rejecting is when there is no such edge in O. The overall count of correct edges in O relative to the numbers of all edges in O or O respectively will produce precision and recall. F-measure is a more just measurement since precision and recall are distributed evenly.

P (E , E) = |E ∩ E | |E | R(E , E) = |E ∩ E | |E| F (E , E) = 2 × P (E , E)R(E , E) P (E , E) + R(E , E)

Other than studying the effect of a single concept addition, the effect of adding a sequence of concepts also has to be studied. The order in which concepts a and b are added to the system has an effect on the non-taxonomic relations generated; generally, the semantic richness of the ontology is affected by the existing concepts and relations. This work has studied the effect of adding two (p = 2) and ten (p = 10) concepts to the ontology graph. Due to all the input concepts being known, the average of all the possible orders have been displayed.

Approaches (I) clearly has better results than approaches (II) excluding one exception. The more frequent a pattern, the higher the probability of it being selected; also, the closer the pattern in the hierarchy, the greater the likelihood of it being the final answer. The major difference between the two approaches other than the F-measure is in the number of statements being selected as the final answer. In the approach (I), the number of statements selected has a limit; as a result, fewer unmatched statements are selected. However, approach (II) has no limit on the number of generated statement, but at the same time more unmatched statements are in the final answer pool. The reason this paper is using the expression unmatched instead of incorrect is that studying the final

Conclusion and Future Work

One ontology evolution operation is concept addition, which implies adding a concept by taxonomic and non-taxonomic relations. Commonly for changing an ontology some external information is required. In this work WordNet as an external source for generating similarities between concepts and relations has been selected. The semantic similarities generated by WordNet, self-information produced from patterns within ontologies, and the hierarchical structure of ontologies are the basis of approaches introduced in this paper. The focus is on intrinsic properties; presuming that intrinsic properties already exist, the assumption is that an input concept is more likely to have the same intrinsic properties as its siblings. Evaluation is based on calculating the precision and recall of detaching a node from an ontology and attempting to reattach it. The results displayed in this paper are based on this evaluation technique. Due to the poor F-measures generated by the introduced approaches, an investigation into the cause of this poor performance revealed that more than 50% of the statements that were considered incorrect are actually semantically accurate. These results if generated by an ontology expert, could easily be regarded as correct. The next step for this research is to generate more complex non-taxonomic relations, such as statements including conjunction and disjunction. Throughout the development of this work, the need for a ternary and a quaternary comparison has been visible. Such a comparison is essential for generating more meaningful ontology statements. Another future direction is to develop a source capable of ternary and quaternary comparison.