For some years now ontologies have been used in Social Science, e.g. , in annotation of newspaper articles for disambiguating concepts within Media Analysis. These ontologies and annotations have now become objects of study in their own right, as they implicitly represent the shift of meaning of political concept over time. Manual mappings, which are intrinsically intensional, can hardly capture such subtle changes, but we claim that automatic instance-based mappings, with their extensional character, are more suitable for producing interesting mapping-chains. In this paper, we evaluate the use of instance-based ontology mappings for producing concept chains in a case-study in Communication Science on a corpus with ontologies describing the Dutch election campaigns since 1994. This initial research shows the potential of the associative character of extensional mapping-chains, but also indicates a number of unsolved open questions, most signi cantly the lack of a proper methodology for evaluating such chains due to the open, explorative character of the task.
Since 1994 Communications Scientists at the Vrije Universiteit Amsterdam have been annotating newspaper articles with controlled vocabularies (of increasing expressiveness) quantitatively studying the in uence of the Media on the political processes. The idea is to code the meaning of sentences and articles in a formalised graph representation (called NET) similar to RDF triples. In these triples actors and issues are taken from an ontology, and the predicate usually represents opinions and moods. During recent election campaigns all newspaper articles on Dutch politics were manually coded using the NET method, with a di erent ontology used in each of the elections. Each ontology is more or less an adaptation of a previous one, with di erent foci, as in each election new issues emerged and the (societies' and scientists') view on issues changed.
As now several of these campaign data sets can easily be queried, also through the use of Semantic Web technology, Communication Scientists' interests started to also include temporal shifts of political development. In an initial analysis political developments over time were studied by querying the NET representation of the articles from the di erent campaigns, which required manual mappings between the ontologies. In this paper, we propose a di erent approach, namely to study concept shift by using chains of extensional, i.e. , instance-based, mappings. Our hypothesis is that these mapping-chains represent subtle changes in meaning of the related concepts over time, and in this paper we will investigate this claim.
Methodology Following our previous work [
Data, experiments and evaluation For our experiments we used 5 di erent ontologies from the Dutch election campaigns in 1994, 1998, 2002, 2003 and 2006. Our experiment were conducted by mapping each of ontologies with each other. Each ontology was used to annotate (around 5000) newspaper articles of the respective campaign. Some initial formal evaluation was done by comparing mappings with an existing manually created (intensional) alignment. Evaluating the quality of the chains is more tricky, as we will discuss in Section 5.3. The answer to RQ2 therefore remains anecdotal, and nally rather unsatisfactory. Applications and generality Capturing meaning shift, particularly the extensional associations, of concepts over time, can help communication scientists to apply analysis on the dynamics of the political developments over time. This line of research is also generalisable in many other areas where similar problems occur, such as development of medical systems, e-Science, knowledge management, and other social networks, etc.
Instance-based ontology matching techniques have shown its capacity of dealing
with matching cases where lexical and structural techniques could not be applied
e ectively [
Let O1 and O2 be two ontologies which are used to annotate two instance sets I1 and I2. The instance-matching based method consists of two steps: { Instance enrichment. For each instance i1 in I1, nd the most similar instance j2 in I2. We consider i1 to be an instance of the concepts which j2 is described with. The same operation is applied in the other direction. In the end, an arti cial common instance set is built. { Concept matching. Each concept corresponds to a set of instances, including their real instances and those enriched in the previous step. A corrected Jaccard similarity measure is applied to calculate the similarity between concepts from di erent years. That is
Jacc = pjc1i [ c2ij (jc1i [ c2ij
0:8)
jc1i [ c2ij
(1)
where c1i, c2i are the instance sets of two concept c1(2 O1) and c2(2 O2). 3
Two concepts with su cient similarity are considered mapped. A set of mappings
between concepts of two ontologies form an alignment between the ontologies.
Instance matching There are di erent ways to match instances. A simple
method is to consider instances as documents, and apply information retrieval
techniques to retrieve similar instances (documents). We use a tf-idf weighting
scheme which is often exploited in the vector space model for information
retrieval and text mining [
Chains of mappings After alignments are generated between multiple ontologies, with some ontologies involved in multiple alignments, it is possible to generate chains of mappings between a series of ontologies, in, for example, a chronological order.
Let A12 and A23 be the alignments between O1 and O2 and between O2 and O3. If there is a mapping in A12, < c1i; c2j ; vi1j2 > and a mapping in A23, < c2j ; c3k; vj2k3 >, this results in a two-step chain of mapping from c1i to c3k via c2j , with a con dence value vik = vi1j2 vj2k3. When there are a series of alignments between O1 and O2, O2 and O3, until On 1 and On, this will result in n-1-step chains of mappings < c1i ! c2j ! ! cn 1;k ! cnl; vi1j2 : : : vknl 1;n > : In this paper, we investigate 4 di erent kinds of mapping-chains, and investigate their usefulness in a practical application: 1. Top-1 forward chain (such as in Fig.:2): in each step, only the mapping with highest con dence is considered. 2. Top-n forward-chains (such as in Fig.:4): in each step, the the best n mappings are considered, starting with the rst ontology. 3. Top-n backward-chains (such as in Fig.:5): in each step, the the best n are considered, starting with the last ontology. 4. Top-n kite (such as in Fig.:6): starting with the rst ontology in each step, the mappings with the n highest con dence values for which there exist a top n mapping chain to the correct mapping (according to the gold standard). 3
The series of ontologies to be mapped are the ontologies used to code newspapers
during ve recent Dutch elections taking place in 1994, 1998, 2002, 2003, and
2006. The articles were coded using the Network analysis of Evaluative Texts
(NET) method [
Example 1. Het Openbaar Ministerie (OM) wil de komende vier jaar
mensenhandel uitroeien. (The Justice Department (OM) wants to eliminate human
trafcking within the next four years.)
The sentence is coded as <om, -1,human trafficking>, where om and human
trafficking are two concepts in the ontology used in 2006, while -1 indicates
the Justice Department is negative about human tra cking. In this example, we
consider this sentence to be an instance of the two concepts involved. All ve
ontologies are represented in the standard SKOS format [
The synonymous concepts were found manually. As shown in Table 1, the number of manually mapped concepts is smaller than that of concepts found in the actual coding. The reason is that new variations of the concepts were manually input to the database. These variations are very likely to be synonyms of concepts in the ontologies or pure typos, which were not covered during the manual mapping process.
Alignments between ontologies of previous years to the latest 2006 version have also been made manually. However, some concepts used in previous years cannot nd the exact correspondences in the 2006 version. In that case, the domain experts added new concepts to the current version. The last column of Table 1 indicates how many new concepts were added during the manual aligning process. These new concepts are not used during the coding of 2006 articles, which means they do not have any instances in the 2006 corpus and were therefore not considered in our automated evaluation. 4
Before focussing on chains of mappings, we need to show that our methods for calculating individual mappings are trustworthy. We rst map all previous ontologies to the 2006 ontology. According to the extensional mapping technique, one concept can be related to multiple concepts, each with a certain amount of relatedness. As only one mapping for each concept was considered in the manual mapping results, for each concept, we take the mapping with the highest con dence value (i.e. , the corrected Jaccard similarity) as the nal mapping of this concept. Table 2 shows precision and recall of these 1:1 mappings.
For all the concepts which were manually mapped with existing concepts in the 2006 ontology, we also measure the mean reciprocal rank (MRR) mrr = jC1 j PiC=1 ran1ki ; where C is the set of concepts, the ranki is the rank of the concept which Ci should be mapped to. When Ci does not have a match, the reciprocal rank is set to 0. A higher mrr indicates the correct matches are ranked in the more front position. Table 3 shows that the correct mapping is ranked on average within the top 10 proposed ones. 5
The main topic of this paper is to investigate the use of chains of mappings of concepts from ontologies from 1994 to 2006. 5.1
Based on the manual alignments, we can measure the precision and recall of the chains. For each concept from 1994, top K mappings are taken into consideration, each of which will be expanded by its top K mappings too, and so on.4 A chain can start from any concept of any year. For all chains with n steps, n = 1; 2; 3; 4, we measure the precision and recall respectively. A chain is considered to be correct if the two end-point concepts form a correct mapping according to gold standard, i.e. , the correctness is 1; a chain is partially correct and the correctness is the number of correct mappings on the way over the number of steps. In the end we take the average of the correctness of all individual chains as the nal precision. The partial correctness is not considered when calculating the recall. The evaluation results are shown in Fig. 1.
Clearly, when considering more mapping candidates, more noisy data is included. Fig. 1 (c) gives the raw count of chains in terms of the choice of K. Note the numbers are in log scale. The red line indicates the number of chains with the two end-point concepts form a correct mapping judged by the gold standard. 4 By expanding via di erent intermediate mappings from one concept, the total amount of chains is growing, but not exponentially. The reason is that concepts related to the starting concept tend to have a similar extensional semantics.
If only taking top 1, 2 or 3 related concepts, when the steps goes up, the number of correct chains drop, but the total amount of chains drops even faster. The precision of multi-step chains is actually higher than that of shorter chains. This suggests, even the absolute correctness of direct mappings may not be perfect, a multi-step chains of less perfect mappings may still lead to correct mappings over all time. Unfortunately, when taking more less related concepts, the number of correct chains goes up, but the sheer amount of total chains climbs up more rapidly, which cause the precision to drop in the end; the precision of multi-step chains is lower than that of shorter chains, that is the quality of the mappings degraded when the intermediate steps became longer. 5.2
A qualitative analysis of chains of mappings provides interesting insights in the value of the matching of ontologies over time for social sciences. A typical example of mapping of concepts over time will be discussed. The domain-speci c political analysis will be supplemented by a methodological discussion (we call it Metaanalysis provided in italics) from the perspective of the usefulness of mapping-chains.
Let us start with an analysis of di erent chains for the two concepts asylum seekers (\asielzoekers") and senior citizens (\ouderen"). Figure 2 shows that the concept of asylum seekers (label: asielzoekers) is correctly mapped in each of the election years to the same concept at the highest rank. This result indicates that no or limited topic drift occurred. The con dence value slowly deteriorates, which might imply that the debate about asylum seekers has become more multifaceted. An alternative explanation is that the number of concepts relating to asylum policy in the ontologies has increased because of the increasing political interest in asylum policy. Metaanalysis 1: Even from a simple top 1 forward chain, some lessons can be drawn. However, note that analyses of this kind depend on the con dence values, which are rather dubious at best. Top 1 chains are more interesting objects of study when more drastic shifts occur.
Figure 3 shows that the elderly concept (ouderen) is only mapped to the expected concept between 1994 and 1998. The 1998 concept of the elderly is mapped to \obligation to apply for a job for the unemployed" (sollicitatieplicht). The abolition of the exemption of the obligation to apply for a job for the elderly was an election issues in 2002, which explains the link between these concepts. Both concepts should be considered as social security issues from a theoretical stance, since the elderly became an election issue during election campaigns with regard to special social security arrangement for the elderly. In 2003 the obligation to apply is correctly mapped to the 2002 concept. In 2006 the obligation to apply is mapped to the related concept of the unemployed.
Metaanalysis 2: Association versus similarity: One of the crucial methodological problems is the formal meaning of the mappings between two concepts such as the elderly and the obligation to apply. Clearly, our instance-based methods nd mappings with an extensional semantics, i.e. , the use of the concepts in annotating articles is related. A domain expert can identify elements of the intensional meaning that relate these two concepts in the speci c case. Concretely, the issue \senior citizen" in 1998 and the issue \obligation to apply" in 2002 also share an intensional meaning. However, to the best of our knowledge there is no theory to formalise the relation between the extensional meaning and the intensional meaning of the mappings. In the following we will see examples where using association misses the goal of nding similarity, in particular when chains of mappings are considered.
Although the asylum seeker concept is mapped correctly, the chains including top 2 concepts { represented in Figure 4 { give additional insights into the nature of the asylum debate over time. An analysis of the secondly ranked concepts shows with which issues asylum seekers have been associated during the election campaigns. In 1998 asylum seekers are mapped to the Cabinet of the time (kabinet kokmierlods), which follows from the fact that this Cabinet paid much attention to this issue. The second rank concepts in the following years indicate changes in the proposed policy measures. In 2002, when the anti-immigration party LPF came into power, asylum seekers are mapped to the constraint of the in ux of refugees (instroom beperking). In 2003, after the LPF had left the government, it was mapped to a non-restrictive measure, assistance to illegal immigrants (opvang illegalen). In 2006 { the year in which another anti-immigration party made an upsurge { was mapped to integration. It is worth noting that in 2006 the second rank mapping (integration) has a positive connotation, which suggests that the new anti-immigration party did not manage to in uence public opinion to the degree the LPF managed in 2002.
Metaanalysis 3: This nice example shows a number of useful ndings from the Communication Scientist perspective. The chains of intensional meaning of the concepts at the time of their use provides interesting, and very subtle, developments for further investigation. Given that the top 1 mappings are all correct, the interest lies particular in the second ranked mappings of each step, which tell a story of Dutch politics.
With the expansion of the chain, some concepts that were mapped to secondly ranked concepts do not always directly relate to asylum seekers anymore. While the secondly ranked concept assistance to illegal immigrants in 2003 was plausibly mapped to illegal immigrants (illegalen), it was also mapped to organ donation (orgaandonatie). This latter mapping is explained by a particular political actor who propagated both the assistance to illegal immigrants in 2003 and organ donation in 2006.
The lower half of the gure does not directly relate to asylum seekers either, since the Cabinet in 2003 was not mapped at a high rank to asylum seekers anymore, but to the military aircraft Joint Strike Fighter (jsf) and business (bedrijfsleven), which in turn were mapped to concepts in the military and economical area. We omitted parts of the lower half for space reasons.
Metaanalysis 4: These are examples, where association can lead to unrelated concepts in 2 steps only. This highlights one of the biggest methodological challenges: how to distinguish useful and non-useful chains. Early erroneous associations can turn large parts of the analysis practically useless.
Figure 5 containing the backward chain starting from 2006, complements the information about the nature of the asylum debate. Studying the secondly ranked concepts mapped to asylum seekers in the backward direction, partially di ering association with asylum seekers appear. Asylum seekers in 2006 are mapped to crime (criminaliteit) in 2003. In recent elections immigrants (including asylum seekers) have been regularly associated with crime by anti-immigration parties. Although these concepts are not directly related, they are related to each other in the political reality. As in the forward mapping asylum seekers in 2003 is mapped to the constraint of the in ux of refugees in 2002. In 1998 they are mapped to the police (rpolitie) and in 1994 to the Cabinet (luko lubbersko). The mapping to the police is in line with the mapping to crime in 2003.
Metaanalysis 5: The chains of the concept mappings in two di erent directions are complementary. While it seems, for example, anomalous that churches (okerken) in 1998 is mapped to the constraint of the in ux of asylum seekers in 2002, the mapping of the constraint of the in ux of asylum seekers in 2002 to assistance to asylum seekers in 1998 in the opposite direction helps to explain this mapping, since churches played an important role in the assistance to asylum seekers.
It is noticeable that the expansion chains do not expand exponentially, but still faster than we expected.5 An interesting phenomenon is that mappings do not converge again, i.e. , once an association happens in one year, it usually does not associate back the following year to the same topic. This is an interesting nding, for which we do not have an explanation.
Metaanalysis 6: The expansion factor is meaningful in two ways: it gives an indication on the debate itself, but it can also be an indication for the mapping quality. The smaller the tree is, the more closely related are the associated concepts, which might indicate that the mapping quality is better than that for larger trees.
The kite with two correct endpoint concepts integrates the information from the previous gures. In Figure 6, it becomes clear that the concept of asylum seekers is correctly mapped from one election year to another. Additionally it shows that the asylum debate is both associated with central concepts in the 5 In the top 2 chains we studied the average width was 12. asylum policy debate, the constraint of the in ux of refugees and the assistance to illegal immigrants, and to crime, a concept that is, however not directly related to asylum seekers, related to the concept in the political reality.
Metaanalysis 7: Kites from end to end seem the most useful way of illustrating concept drift, as incorrect associations are eliminated (because they are not mapped back to the start-concept). However, such a kite is less ne-grained than the forward chain: the subtle change between negative and positive connotation between 02 instroom beperking and 06 integration is lost. 5.3
The issues discussed in the previous section mostly center around two questions: the usefulness of our proposed mapping chains, and the meaning of the extensional mappings in the rst place. Studying a representative sample of chains through our domain expert indicates clearly that mapping chains can be interesting given the reasonable quality of the individual mappings we can produce.
However, apart from the concern about the accuracy of the mapping method used here, two problems are apparent to which we do not yet have a satisfactory solution: the lack of a notion of correctness of extensional mappings in the chains, and the evaluation of this correctness. Our manual analysis shows plenty of examples where an associative semantics of mappings based on the extensions of concepts corresponds to an intensional relation of the meaning between of two concepts. However, in other examples these associations often totally diverge from what domain experts nd acceptable intensional similarities. We have no intuition yet how to address this problem, i.e. , how to formalise and study it. The most promising solution for addressing this problem is to consider the kite structures, in which the disambiguation of mappings is achieved by requiring a mapping back to the original concept. In that way wild mismatches can be eliminated from the temporal chains. Many interesting parts of the temporal "story" get lost in this approach, though.
The second problem is the strongly related problem of evaluation: so far we found only two ways of evaluating our constructs: 1) comparing the chains with an intensional gold standard, and 2) having a domain expert evaluate each of the chains. Obviously, the rst option is methodologically not valid, as we evaluate against something we know not to be the solution. The second approach is more acceptable from the domain perspective, but manual checking is very expensive and di cult to quantify, if it is not yet impossible to identify all \intertesting chains." The only practical solutions we found so far is to use the spreading factor of the top K chains over time. In our view, the fewer leaves such a tree has, the semantically closer the mappings should be. However, this idea is build on intuition rather than empirical ndings. 6
In this paper we introduced di erent representations of mapping chains and evaluated them over sequences of political ontologies in a Media study driven by Communication Scientists. We used instance-based mappings between pairs of ontologies to calculate sequences of extensional mappings and show, for a usecase analysing Dutch election campaigns, some interesting qualitative ndings.
Apart from these stimulating examples we also provided an initial evaluation of our proposal, both qualitative and quantitative. However, this evaluation is tricky, as neither the notion of correctness of an extensional mapping is wellde ned, nor do we have a sound evaluation methodology yet.
For us the general lessons for the ontology mapping community is twofold: that the semantics of mappings is not yet fully understood, particularly, w.r.t., extensional semantics, and that mappings in a dynamic context are challenging, and worthwhile, objects of study in addition to their known static variants.