Datasets for the Evaluation of Substitution-Tolerant Subgraph Isomorphism

Pierre Héroux, Pierre Le Bodic, Sébastien AdamGREC 2013 · DOI

TL;DR

This paper introduces three new datasets designed to rigorously evaluate algorithms for "substitution-tolerant subgraph isomorphism," a crucial task in recognizing patterns within complex structural data like technical drawings. By providing both synthetic and real-world benchmarks with ground truth, the authors aim to advance the field of structural pattern recognition, particularly in scenarios with noisy or imperfect data.

What Problem Does This Paper Address?

The recognition of symbols and patterns within technical documents often relies on representing these documents as graphs. Identifying a specific symbol then becomes a "subgraph isomorphism" problem: finding an instance of a smaller "pattern graph" within a larger "target graph" representing the document. However, real-world data is rarely perfect. Noise in feature extraction or segmentation can lead to variations in the labels of vertices and edges, or even topological differences. This paper focuses on "substitution-tolerant subgraph isomorphism," which specifically addresses variations in labels, assuming the underlying structure is mostly preserved. The core problem addressed is the lack of publicly available, well-annotated datasets that allow for the systematic evaluation of algorithms designed to handle these label variations, especially when dealing with continuous-valued labels.

Methods

The paper defines "substitution-tolerant subgraph isomorphism" formally, outlining the mathematical constraints for an isomorphism. It introduces a cost function that penalizes differences in vertex and edge labels, allowing for imperfect matches. The core contribution lies not in a new algorithm, but in the creation and description of datasets to evaluate existing and future algorithms. The paper also proposes performance measures like "detection rate," "top n detection rate," precision, and recall to quantify the effectiveness of these algorithms on the presented datasets.

Datasets

The authors introduce three datasets:

  • ILPIso_exact_synth: A synthetic dataset with 180 pattern-target graph couples. These graphs are generated using the Erdös-Rényi model with random numerical labels. This dataset is designed to test algorithms' ability to find exact subgraph isomorphisms without label noise.
  • ILPIso_noisy_synth: Also a synthetic dataset with 180 pattern-target graph couples, generated similarly to the exact version but with an added Gaussian noise to vertex and edge labels. This dataset is crucial for evaluating the robustness of algorithms to label perturbations.
  • ILPIso_real: A dataset derived from structural representations (Region Adjacency Graphs) of architectural plans. It contains 5609 symbol instances and 16 symbol models, allowing for the evaluation of finding multiple occurrences of patterns in real-world, albeit synthetically generated, document images. This dataset is particularly valuable for testing retrieval systems and multi-instance search.

Key Insights and Ideas

  • The critical need for realistic benchmarks: The paper highlights that existing datasets are insufficient for evaluating substitution-tolerant subgraph isomorphism, especially with continuous labels. The proposed datasets fill this gap.
  • Distinguishing label vs. topological errors: The authors clearly differentiate between "substitution-tolerant" (label errors) and "inexact" (topological errors) subgraph isomorphism, focusing their datasets on the former.
  • Bridging synthetic and real-world evaluation: The inclusion of both synthetic (controlled noise) and real-world (architectural plans) datasets provides a comprehensive evaluation framework, allowing for both algorithmic robustness testing and practical application assessment.
  • The impact of noise on isomorphism: The ILPIso_noisy_synth dataset directly addresses how algorithms perform when faced with imperfect, but structurally similar, patterns.

Key Results

The paper does not present quantitative results from running specific algorithms on these datasets. Instead, it focuses on the creation and description of the datasets themselves and the proposed evaluation metrics. The "key results" are the datasets themselves and the framework for their use:

  • Three distinct datasets (exact synthetic, noisy synthetic, real-world architectural plans) are made available.
  • Performance measures (detection rate, precision, recall) are defined for evaluating algorithms on these datasets.
  • The datasets are designed to test various aspects, from finding single exact matches to locating multiple noisy instances in complex structures.

Limitations and Future Work

  • Focus on label tolerance: The current datasets are primarily designed for "substitution-tolerant" subgraph isomorphism, meaning they focus on label variations. The authors acknowledge that extending this to "error-tolerant" subgraph isomorphism (which includes topological differences) would be a significant future direction, though it raises challenges in ground-truth definition.
  • Potential for more noise models: The authors suggest exploring various noise models and levels for more comprehensive robustness testing.
  • Alternative structural representations: Future work could involve using different graph representations, such as graphs of graphical primitives, to further diversify the evaluation landscape.
  • Ground truth for topological errors: Defining ground truth for topological differences in subgraph isomorphism is noted as a challenge for future research.

Summary updated

BibTeX
@inproceedings{heroux2013datasets,
  author = {Pierre Héroux and Pierre Le Bodic and Sébastien Adam},
  title = {{Datasets for the Evaluation of Substitution-Tolerant Subgraph Isomorphism}},
  booktitle = {GREC},
  year = {2013},
  doi = {10.1007/978-3-662-44854-0\_19},
}
Figure