Due to the diverse ways of exploring the ontology matching problem, matching systems generally differ in the alignments generated between two ontologies. Some approaches may be better suited for some ontologies, or some tasks, than others. Ontology alignment agreement aims at overcoming the problem of allowing different parties to conciliate their conflicting points of view on alignments. There may be different ways to perform alignment agreement, such as voting or weighting. In this paper, we consider argumentation which offers a more reasoned way to decide which correspondences to preserve.
Argumentation theory has been exploited as a way to support the comparison and selection of correspondences within an alignment process. Correspondences are represented as arguments and argumentation frameworks support the reasoning on their acceptability. This approach has been used in different scenarios. [13] propose an approach for supporting the creation and exchange of different arguments, that support or reject correspondences in the context of agent communication. In [18], different matchers work on the basis of particular approaches achieving distinct results that are compared and agreed via an argumentation process.
An open issue in alignment agreement is related to the inconsistency in the agreed alignment. Indeed, some selected sets of correspondences may relate the ontology in an inconsistent way. Most matching systems do not consider logic-based semantics in their algorithms. As a result, almost all matching systems produce incoherent alignments [14]. Although argumentation aims at resolving conflicts on the alignments generated by these systems, this process does not guarantee that the agreed alignment is consistent even if the initial alignments were consistent.
In this paper, we propose a model that involves both argumentation and logical inconsistency detection. We focus on the scenario where matchers working on the basis of different matching approaches try to reach a consensus on their alignments. First, matchers generate their correspondences, representing them as arguments. Next, they exchange their arguments and interpret them under argumentation frameworks based on their individual preferences. The arguments in every individual set of acceptable arguments are considered as an agreed alignment. Then, the inconsistent correspondences in such sets are removed, in order to generate a maximal consistent agreed alignment. This allows for maintaining the consistency within an argumentation system. We evaluate our proposal on a standard set of alignments. Though theoretically grounded, the consistency step does not improve argumentation alone. For some test cases, the argumentation process is incidentally able to provide consistent agreed alignments. We describe the features of consistency checking and argumentation which cause this result.
The rest of the paper is organised as follows. First, we introduce alignments and inconsistency of alignments ( §2). We then present the argumentation approach for alignment agreement ( §3). Next, the consistency-driven argumentation protocol is presented ( §4) and its evaluation is discussed ( §5). Finally, we discuss related work ( §6) and conclude the paper ( §7).
An alignment (A) is a set of correspondences from a pair of ontologies (o and o ′ ). Each correspondence is a quadruple: e, e ′ , r, n , where e ∈ o, e ′ ∈ o ′ , r is the relation between e and e ′ , taken from set of alignment relations (e.g., ≡, ⊑, ⊒ or ⊥), and n ∈ [0 1] is a confidence level (e.g., measure of confidence in the fact that the correspondence holds). For instance, given the two ontologies of Figure 1, one can consider the following correspondences, meaning that (1) the two classes Person in both ontologies are the same, and that (2) DepartmentHead in the first ontology is subsumed by Department in the second ontology.
The semantics of alignments provides a definition of how alignments must be interpreted. It is related to the semantics of the aligned ontologies, which is given by their sets of models M(o) and M(o ′ ). The main effect of alignments is to select compatible pairs of models of the two related ontologies [8]. We rely here on a basic semantics in which models are directly compatible. It considers that a correspondence is satisfied by a pair of models if the interpretation of the entities by these models satisfy the relation of the correspondence. For instance, in the language used as example, if m and m ′ are respective models of o and o ′ :
The alignment acts as a model filter for the ontologies: it selects the interpretation (here the models) of ontologies which are coherent with the alignments. This allows for transferring information from one ontology to another since reducing the set of models will entail more consequences in each aligned ontology.
The notion of models of aligned ontologies is also useful for defining the usual notions of consistency or consequence.
A between these ontologies, A is consistent if there exists a model of A. Otherwise A is inconsistent.
For instance, under the classical ontology interpretation, the alignment A presented in Figure 1 is inconsistent as soon as there exists a DepartmentHead because any model would require to satisfy the following equations:
and the DepartmentHead would need to be in both the interpretation of Department o ′ and in that of Person o ′ .
In this paper we will only consider inconsistency, however, the same applies to incoherence: the fact that a class or relation may necessarily be empty, i.e., which would cause inconsistency if instantiated.
In alignment agreement, arguments can be seen as positions that support or reject correspondences. Such arguments interact following the notion of attack and are selected according to the notion of acceptability. These notions were introduced by [6]. In Dung's model, the acceptability of an argument is based on a reasonable view: an argument should be accepted only if every attack on it is attacked by an accepted argument. Dung defines an argumentation framework as follows. In Dung's model, all arguments have equal strength, and an attack always succeeds (or successfully attacks). [2] has introduced the notion of preference between arguments, where an argument can defend itself against weaker arguments. This model defines a global preference between arguments. In order to relate preferences to different audiences, [3] proposes to associate arguments to the values which supports them. Different audiences can have different preferences over these values. This leads to the notion of successful attacks, i.e., those which defeat the attacked argument, with respect to an ordering on the preferences that are associated with the arguments. This allows for accommodating different audiences with different interests and preferences.
Bench-Capon's framework acknowledges the importance of preferences when considering arguments. However, in the specific context of ontology matching, an objection can still be raised about the lack of complete mechanisms for handling persuasiveness [10]. Indeed, many matchers output correspondences with a strength that reflects the confidence they have in the fact that the correspondence between the two entities holds. These confidence levels are usually derived from similarity assessments made during the matching process. They are therefore often based on objective grounds.
For associating an argument to a strength, which represents the confidence that an agent has in some correspondence, [18] has proposed the strength-based argumentation framework, extending Bench-Capon's model: Definition 5 (Strength-based argumentation framework (SVAF) [18]). A SVAF is a sextuple A, ⋉, V, v, , s such that A, ⋉ is an AF, V is a nonempty set of values, v : A → V, is the preference relation over V (v 1 v 2 means that, in this framework, v 1 is preferred over v 2 ), and s : A → [0, 1] represents the strength of the argument.
Each audience α is associated with its own argumentation framework in which only the preference relation α differs. In order to accommodate the notion of strength, the notion of successful attack is extended: Definition 6 (Successful attack [18]). An argument a ∈ A successfully attacks (or defeats, noted a † α b) an argument b ∈ A for an audience α iff
Definition 7 (Acceptable argument [3]). An argument a ∈ A is acceptable to an audience α with respect to a set of arguments S, noted acceptable α (a, S), iff ∀x ∈ A, x † α a ⇒ ∃y ∈ S; y † α x.
In argumentation, a preferred extension represents a consistent position within a framework, which defends itself against all attacks and cannot be extended without raising conflicts:
free set of arguments S is admissible for an audience α iff ∀a ∈ S, acceptable α (a, S). A set of arguments S in the VAF is a preferred extension for an audience α iff it is a maximal admissible set (with respect to set inclusion) for α.
In order to determine preferred extensions with respect to a value ordering promoted by distinct audiences, objective and subjective acceptance are defined [3]. An argument is subjectively acceptable if and only if it appears in some preferred extension for some specific audience. An argument is objectively acceptable if and only if it appears in all preferred extension for every specific audience. We will call objective consolidation the intersection of objectively acceptable arguments for all audiences and subjective consolidation the union of subjectively acceptable arguments for all audiences.
A way of representing correspondences as arguments within an AF is as follows: Definition 9 (Argument [13,17]). An argument a ∈ A is a triple a = c, v, h , such that c is a correspondence,v ∈ V is the value of the argument and h is one of +,depending on whether the argument is that c does or does not hold.
The notion of attack is then defined as follow: Definition 10 (Attack [13,17]). An argument c, v, h ∈ A attacks an argument
For instance, if a = c, v 1 , + and b = c, v 2 , − , a ⋉ b and vice-versa (b is the counter-argument of a, and a is the counter-argument of b).
The way arguments are generated differs in each scenario. The strategy in [18], negative arguments as failure, relies on the assumption that matchers return complete results. Each possible pair of ontology entities which is not returned by the matcher is considered to be at risk, and a negative argument is generated (h=-).
In this paper, different matchers argue with each others in order to obtain an agreement on their alignments. To do this, each matcher is a different audience. The values in V correspond to the different matching approaches and each matcher m has a preference ordering m over V such that its preferred values are those it associates to its arguments. For instance, consider V = {l, s, w}, i.e., lexical, structural and wordnet-based approaches, respectively, and three matchers m l , m s and m w , using such approaches. The matcher m l has as preference order l m l s m l w.
To illustrate the agreement process, consider the alignment A Figure 1 and two matchers i and j. Both i and j generate the correspondence (1) and j correspondence (2). The following arguments are then created by i and j:
After generating their arguments, the matchers exchange their arguments with each other. The matcher i sends to j its arguments a i,1 and a i,2 , and vice-versa. i has a preference ordering w i l, while j has l j w. Having the complete set of arguments, the matchers generate their preferred extensions p i and p j . For both p i and p j , the arguments a i,1 , a j,1 and a j,2 are acceptable: a i,1 and a j,1 are not attacked, while a j,2 successfully attacks a i,2 because both arguments have opposite values of h but a j,2 has highest strength than a i,2 . So, the set of globally acceptable correspondences, A, contains both (1) and (2). It is the alignment associated with the objective consolidation.
However, this set is not consistent. Due to the fact that DepartmentHead is subsumed by Person in o, and Person and Department are disjoint concepts in o ′ , A is inconsistent as soon as there exists one Department.
Resolving the inconsistency problem in alignment agreement has two possible alternatives: (a) express the inconsistency within the argumentation framework, as in [1,4]; or (b) deal alternatively with the logical and argumentative parts of the problem. Integrating the logic within the argumentation framework seems a more elegant solution and it can be achieved straightforwardly when correspondences are arguments and incompatible correspondences can mutually attack each others. However, this works only when two correspondences are incompatible. When the set of incompatible correspondences is larger, the encoding is not so straightforward and may lead to the generation of an exponential amount of argument and attacks.
For that purpose, we define the consistency associated with an extension.
There are different ways to account for consistency in SVAF. The first one retains only consistent preferred extensions. However, the set of preferred consistent extensions may be empty. A fallback would be to consider maximal preferred consistent sub-extensions.
A consistent extension S is a maximal preferred consistent sub-extension iff there exists a preferred extension S ′ such that S ⊆ S ′ and ∀S ′′ ; S ⊂ S ′′ ⊆ S ′ , S ′′ is not consistent.
There may be several such sub-extensions. Another approach, considered here, is to work on consolidations, i.e., the set of objective or subjective arguments.
A consistent extension S is a maximal consistent sub-consolidation of an (objective or subjective) consolidation S ′ iff S ⊆ S ′ and ∀S ′′ ; S ⊂ S ′′ ⊆ S ′ , S ′′ is not consistent.
We propose a consistency-driven protocol that computes the maximal consistent objective sub-consolidations. The algorithm removes the correspondences that introduce inconsistencies into the resulting alignment, for maintaining the coherence within the argumentation system. First, as in Section 3.1, the matchers compute their preferred extension from which the objective consolidation, O, is obtained. Based on O, the maximal consistent sub-consolidations is then determined. It can be generalised to consider subjective consolidation or each preferred extension separately. If the objective consolidation is consistent, then the algorithm returns it. If not, the maximal consistent sub-consolidation S is computed.
For computing S we have used the algorithm proposed by [14] which identifies the minimal sets of incoherent correspondences and removes them from the original alignment. The algorithm is based on the theory of diagnosis, where a diagnosis is formed by the correspondences with lowest confidence degrees that introduce incoherence in the alignment. It partially exploits incomplete reasoning techniques to increase runtime performance, preserving the completeness and optimality of the solution.
The proposed approach is evaluated on a group of alignments from the conference track of the OAEI1 2009 campaign. The data set consists of 15 ontologies in the domain of conference organisation. They have been developed within the OntoFarm project2 . We use the subset of these test cases where a reference alignment is available (21 alignments, which corresponds to the alignment between 7 ontologies) 3 . We focus on equivalence correspondences, which are taken into account in the reference alignment, and filter out subsumption correspondences.
We have chosen the alignments generated by the four best matchers that have participated in the 2009 OAEI conference track [7]: AMaker, Aflood, AMext and Asmov.
Each matcher has a SVAF and a private preference order, which is based on the f-measure ordering for all matchers -AMaker (0.57), Aflood (0.52), AMext (0.51) and Asmov (0.47). The highest preferred value of each matcher is the value that it associates to its arguments. For instance, AMaker has as preference ordering: v amaker amaker v af lood amaker v amext amaker v asmov , while Asmov has the ordering: v asmov asmov v amaker asmov v af lood asmov v amext .
For negative arguments (h = −), we use two different strength values. First, we consider that the strength can vary according to the matcher quality (conformance with the reference alignment). We assume that this strength is inversely proportional to the probability that a false positive correspondence is retrieved by the matcher. Such probability can be measured by the fallout of the alignment A, given the reference alignment R. Then, we define str for the matcher m:
Second, we use str=1.0, assuming that matchers strongly reject correspondences that they do not found (it could be the case when the information about the matcher quality is not available).
We measure precision and recall of the maximal consistent sub-consolidation, S, with respect to the reference alignments. First, we present the results from our approach and next we compare them with the results from each matcher. Figure 2 presents the results from the objective consolidations, O, and from the maximal consistent subconsolidation, S, for SVAFs with str = 1 and fallout-based str.
For SVAF with str = 1, argumentation (O) is sufficiently selective for generating consistent objective consolidations. We obtain high precision but low recall. This behaviour is due to several reasons. First, we are using objective consolidations and only arguments present in every preferred extension are considered (what leads to an increase in precision). Correspondences being accepted by all matchers have high probability to be consistent. Second, we use str = 1 for negative arguments (h = 1) and thus a true positive (correct) correspondence with strength lower than 1.0 is successfully attacked by a false negative correspondence with strength 1.0 (what decreases the recall).
Using fallout-based str (Figure 2), we have an opposite behaviour. Argumentation is not able to filter out all inconsistent correspondences. We have low precision and high recall. This occurs because negative arguments are not strong enough for successfully attacking all positive arguments (including the incorrect ones). As a result, many correspondences are selected, what increases the probability for selecting inconsistent correspondences. When applying consistency checking, S, in average, precision slightly increases, while recall decreases. This effect is due the way the algorithm for removing the inconsistencies works. An incorrect (but consistent) correspondence might cause the removal of all conflicting correspondences with lower confidence, and thus some correct correspondences are filtered out. Second, we compare the results from O and S with the results from each matcher. Figure 2 shows the matcher results with and without consistency checking. In the majority of the test cases, the precision increases when filtering out the inconsistent correspondences, while recall decreases (in the case of Aflood, for some tests, the precision decreases while Amaker maintains its recall). As stated before, this is due to the fact that some correspondences are incorrect with respect to the reference alignment but consistent, as well as some correct correspondences are not included in the consistent set because together with some incorrect (but consistent) correspondences, they introduce inconsistencies into the set. Asmov is the only system able to check the consistency in its alignments. In terms of f-measure, apart Asmov, consistency checking improves the results from Amaker and Amext.
Comparing the results from SVAFs with the results from each matcher, for str=1 (Figure 2), argumentation outperforms all matchers in terms of precision, but recall is below all matchers. For fallout-based str, we find an opposite behaviour. All matchers outperform argumentation in terms of precision, but recall is better with argumentation. Looking for argumentation and consistency checking together, although consistency checking slightly improves the precision, both precision and recall are below every matcher. Consistency or argumentation improves results, while contrary to the intuition, we do not observe that the combination of both of these provide more improvements.
Following our (partial) experiments, we can observe that the behaviour of argumentation highly depends on the strength of the arguments. Argumentation is more or less selective when using strong or weak strengths for negative arguments, respectively. Thus, an important issue in the argumentation model is related with the choice of strengths of negative arguments.
Using logical consistency checking alone has positive effects in terms of f-measure for the majority of matchers. On the other hand, combining argumentation and consistency checking slightly improves the precision, when argumentation is not sufficiently selective for generating consistent alignments, but in terms of f-measure, this combination has some negative effects. It is due particularly to the decrease in recall.
Few ontology matching systems have been developed using semantic-based techniques. Examples of systems using some kind of logical verification are S-Match [9] and AS-MOV [11]. S-Match explores propositional satisfiability techniques (SAT) for generating correspondences between graph-like structures. ASMOV semantically verifies the alignments for filtering inconsistencies. However, ASMOV lacks a well defined alignment semantics and notions as correctness or completeness are thus not applicable [14].
In the field of alignment agreement based on argumentation, few approaches have been proposed. In [13], Bench-Capon's model is used to deal with arguments that support or oppose candidate correspondences between ontologies. Both Bench-Capon's and SVAFs frameworks fail at rendering the fact that sources of correspondences often agree on their results, and that this agreement may be meaningful. [10] have adapted the SVAF in order to consider the level of consensus between the sources of the correspondences, by introducing the notions of support and voting into the definition of successful attacks. The work from [5] aims at identifying subparts of ontologies which are sufficient for interpreting messages. This contributes to reduce the consumed time, at a minimal expense in accuracy.
In the field of alignment inconsistency, [15] and [12] considered correcting inconsistent alignments. Revision is obtained exclusively by suppressing correspondences from the alignment through minimising the impact of this suppression. In [15], the goal is to feed the consistent alignment back to a matcher so that it can find new correspondences. This process can be iterated until an eventual fix-point is reached. Similarly, [16] provides a revision operator by modifying one alignment between two ontologies such that the result be consistent. Consistency and consequences are given by merging both ontologies and alignments within the same standard theory. Operators are provided based on the notion of minimal conflict sets.
We have defined consistency-driven argumentation for alignment agreement. This fills a gap between argumentation-based matching and consistency-based alignment repairs. We have experimented our strategy on a set of alignments from expressive ontologies. The conclusion is that though theoretically grounded, the extra consistency step does not improve argumentation alone. At least in our experimental setting the argumentation process is incidentally able to provide near consistent extensions. We have analysed the features of consistency checking and argumentation which cause this result.
Hence from these (partial) experiments we can conclude that applying inconsistency recovery and argumentation independently improves results, while using them together does not improve significantly the results. If this does not discard the validity of the approach, it reveals that it should not be applied without care, especially given its complexity.
Further study is required to know better in which context matching and argumentation leads to inconsistency. One source of improvement would be to take into account several such alignments between several ontologies (a network of ontologies). Indeed, these could raise inconsistency within networks of ontologies which would have to be considered as well.
We are grateful to Christian Meilicke for letting us use his consistent sub-alignment software.