Dynamic Selection of Ontological Alignments: A Space Reduction Mechanism

Paul Doran, Valentina Tamma, Terry R. Payne, Ignazio PalmisanoIJCAI 2009

Abstract

This paper proposes the use of ontology modularization as a critical pre-processing step to mitigate the computational burden of agent-based negotiation in the Semantic Web. By extracting relevant subsets of ontologies based on specific query signatures, the authors demonstrate a significant reduction in the search space for correspondences. Experimental results show an average 53% reduction in the number of alignments requiring negotiation, while also enabling a "fail-fast" mechanism that identifies incompatible ontologies before expensive computation occurs.

Introduction: The Search Space Problem

In decentralized environments like the Semantic Web, software agents must frequently interact using heterogeneous vocabularies or ontologies. To achieve interoperability, these agents must find alignments—mappings between their respective concepts. While argumentation-based negotiation allows agents to reach a consensus on these mappings at runtime, the process is computationally intensive. Determining the existence of an argument for a specific mapping can reach a complexity of $\Pi_2^{(p)}$-complete, making it a significant bottleneck as ontologies scale.

The core challenge addressed here is the "search space problem": how to prune the vast list of potential correspondences so that agents only engage in negotiation over the elements strictly necessary for their current task.

Methodology: Modularized Negotiation

The authors introduce a framework that integrates ontology modularization directly into the negotiation pipeline. Instead of processing entire ontologies, the system extracts a "module"—a logically consistent subset—based on the specific query or "signature" of the initiating agent.

The 9-Step Workflow

The integrated process begins when an agent initiates a query and ends with a consensus answer. This workflow ensures that negotiation is focused only on relevant concepts.

The 9-step integrated workflow for agent negotiation using ontology modularization.

Modularization Techniques

The paper evaluates three distinct modularization approaches:

  1. Graph-Traversal (D): Based on the work of Doran et al., this method uses graph-based traversal to include all subclasses of a signature while ignoring superclasses to maintain focus.
  2. Logic-Based (CG): Utilizing the techniques of Cuenca Grau et al., these methods use "locality" constraints ($\perp$-locality and $\top$-locality) to extract the minimal set of axioms required to preserve the logical meaning of the signature.

Experimental Evaluation

The framework was tested using the OAEI 2007 Conference Track, involving 11 real-world ontologies (such as Cmt, ConfTool, and Sigkdd) with varying Description Logic (DL) expressivity. The researchers compared their approach against two alignment sources: the Alignment-API (textual/structural matching) and Falcon-AO (a high-quality "gold standard" set).

Key Insights and Results

The study revealed that modularization profoundly impacts the efficiency of the negotiation process. The authors identified three primary behavioral patterns when applying these filters:

  1. Significant Reduction: In the majority of cases, the number of negotiated alignments was reduced by an average of 53.1%, with some cases reaching up to 97% reduction.
  2. The "Fail-Fast" Benefit: In approximately 40.4% of cases, modularization resulted in an empty alignment set. This is a critical efficiency gain, as it allows agents to immediately identify that a transaction will fail due to a lack of common ground without wasting resources on negotiation.
  3. No Reduction: In a small minority of cases (6.5%), the query signature was so central to the ontology that the entire structure remained relevant.
Summary of argument reduction across different alignment sources and modularization techniques.

Conclusion and Future Work

By treating a query as a specific "signature," agents can ignore the vast majority of an ontology that is irrelevant to the current transaction. While logic-based modules (CG) were generally smaller and more precise, the authors noted a potential risk of information loss regarding "child concepts" not present in the original signature. Future research will explore hybrid approaches to balance the minimality of logic-based methods with the broader contextual reach of traversal-based techniques, particularly when dealing with instance-level data (ABox).

Summary updated

BibTeX
@inproceedings{doran2009dynamic,
  author = {Paul Doran and Valentina Tamma and Terry R. Payne and Ignazio Palmisano},
  title = {{Dynamic Selection of Ontological Alignments: A Space Reduction Mechanism}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2009},
}
Figure