S-Match: an Algorithm and an Implementation of Semantic Matching

Fausto Giunchiglia, Pavel Shvaiko, Mikalai Yatskevich

TL;DR

This paper introduces S-Match, a novel algorithm and system for semantic matching of graph-like structures (like ontologies or classification hierarchies). It goes beyond simple label matching by considering the implicit and explicit semantic information within node and arc labels, achieving promising results in precision and recall compared to existing systems.

What Problem Does This Paper Address?

The paper tackles the challenge of semantic matching, which is the process of finding correspondences between elements (nodes and arcs) of two different graph-like structures that represent similar concepts. This is crucial for tasks like data integration, ontology alignment, and information retrieval, where different systems or datasets might use different vocabularies or structures to describe the same real-world entities. Traditional matching approaches often rely on syntactic similarity of labels or simple structural comparisons, which can miss deeper semantic connections. The authors aim to bridge this gap by developing a method that truly understands the meaning behind the labels.

Methods

The core of the S-Match approach is its semantic matching algorithm, which operates in four main steps:

  1. Compute concepts at labels: For each label in both input trees, the algorithm extracts atomic concepts (e.g., breaking "Wine and Cheese" into "wine" and "cheese"). It then uses an "Oracle" (like WordNet) to find senses of these atomic concepts and builds a complex concept representation for the label.
  2. Compute concepts at nodes: This step considers the structural context of a node within its tree, often by combining the concepts of its label with those of its ancestors.
  3. Compute semantic relations among concepts denoted by labels: Element-level matchers are used to determine semantic relationships (equivalence, more general, less general, mismatch, overlapping) between the concepts derived from labels.
  4. Compute semantic relations among concepts at nodes: This is the final matching step where the problem is reformulated into a set of node matching tasks, ultimately reduced to propositional validity problems.

The S-Match system is designed as a highly modular platform, allowing components like different oracles or matchers to be plugged in and out. It includes a preprocessing module to convert input schemas into an internal format, a database to store enriched trees, and a Matching Manager that orchestrates the execution of the matching steps.

Datasets

The paper describes using three examples for evaluation:

  • A simple catalog matching problem.
  • Two small examples from business domains: one comparing a "standard" company profile with a Yahoo Finance profile.
  • Two small examples from academic domains: comparing courses taught at Cornell University with those at the University of Washington.

The authors mention that the full description of the schemas tested can be found at a provided URL, implying these are specific, potentially custom-built, test cases rather than publicly released standard benchmarks.

Key Insights and Ideas

  • Meaning over syntax: The fundamental insight is that true semantic matching requires going beyond surface-level label similarity to understand the underlying meaning of concepts.
  • Leveraging external knowledge: The use of an "Oracle" (like WordNet) is critical for enriching label concepts with real-world semantic information, enabling more accurate comparisons.
  • Compositional concepts: Representing concepts as combinations of atomic concepts and their senses allows for nuanced comparisons.
  • Modular architecture: Designing S-Match as a flexible platform is key to its adaptability and extensibility, allowing for the integration of various knowledge sources and matching techniques.

Key Results

The paper presents preliminary comparative evaluation results against three state-of-the-art matching systems: Cupid, COMA, and SF (within the Rondo system). Across the tested examples, S-Match reportedly outperforms the other systems in terms of precision, recall, and overall quality. While specific numbers are presented in graphs, the text emphasizes that S-Match "clearly outperforms the other systems." The evaluation also considered time, but the primary focus is on the quality of the matching results.

Limitations and Future Work

  • Preliminary results: The authors themselves state that the results are "preliminary," suggesting that further validation and testing on larger, more diverse datasets are needed.
  • Oracle dependency: The performance of S-Match is significantly dependent on the quality and coverage of the Oracle used. The current implementation primarily relies on WordNet.
  • Scalability: While not explicitly detailed as a limitation, the complexity of computing semantic relations across all pairs of nodes and labels could raise scalability concerns for very large graphs.

Future work could involve exploring other oracles, developing more sophisticated element-level and structure-level matchers, and conducting more extensive evaluations on a wider range of real-world scenarios.

Summary updated

Abstract

We think of Match as an operator which takes two graph-like structures and produces a mapping between those nodes of the two graphs that correspond semantically to each other. Semantic matching is a novel approach where semantic correspondences are discovered by computing and returning as a result, the semantic information implicitly or explicitly codified in the labels of nodes and arcs. In this paper we present an algorithm implementing semantic matching, and we discuss its implementation within the S-Match system. We also test S-Match against three state of the art matching systems. The results, though preliminary, look promising, in particular for what concerns precision and recall.
BibTeX
@inproceedings{giunchiglia2004s,
  author = {Fausto Giunchiglia and Pavel Shvaiko and Mikalai Yatskevich},
  title = {{S-Match: an Algorithm and an Implementation of Semantic Matching}},
  booktitle = {ESWS},
  year = {2004},
  doi = {10.1007/978-3-540-25956-5\_5},
}

Loading related content...

Figure