Evaluation of Graph Matching Measures for Documents Retrieval

Salim Jouili, Salvatore Tabbone, Ernest Valveny2009

TL;DR

This paper evaluates four distinct graph matching algorithms for document retrieval tasks, demonstrating that their effectiveness is highly dependent on the type of document and the chosen graph representation. The findings highlight the trade-offs between different approaches, offering insights into selecting the most suitable method for specific retrieval scenarios.

What Problem Does This Paper Address?

In document retrieval, representing documents in a way that facilitates efficient and accurate searching is crucial. While statistical methods (like feature vectors) are common, they often discard valuable structural information. Structural methods, which represent documents as graphs, offer richer descriptions but face challenges in graph matching due to high computational complexity and sensitivity to noise and variations. This paper addresses the need to evaluate and compare different graph matching techniques for document retrieval, aiming to understand their performance across diverse document types and representations.

Methods

The authors evaluate four graph matching measures:

  • Graph Edit Distance from Spectral Seriation (GEDSS): This method transforms graphs into strings and then uses string edit distance to measure similarity.
  • Graph Matching based on Node Signatures (GMNS): This approach uses a vector-based signature for each node, capturing local graph structure, and then solves an assignment problem to find the optimal matching.
  • Graph Probing (GP): This technique uses "probes" (queries about graph properties like node degrees) to create feature vectors for graphs, and then computes similarity using an L1 norm distance.
  • Graph Histogram (GH): This method relies on the degree sequence of a graph, represented as a histogram, and uses the L1-distance between these histograms for similarity.

The evaluation is performed using precision-recall curves, a standard metric for retrieval system performance.

Datasets

The paper evaluates the proposed methods on four distinct datasets:

  • GREC database: Graphs representing symbols from architectural and electronic drawings (528 graphs, 24 classes).
  • Ornamental letters database: Graphs representing graphical objects (lettrines) from ancient documents (280 graphs, 4 classes).
  • Shape database: Graphs derived from shapes by skeletonization and Delaunay triangulation (216 graphs, 18 classes).
  • Logo database: Graphs extracted from trademark-logos using interest point detection and Delaunay triangulation (80 graphs, 10 classes).

Key Insights and Ideas

  • Representation is King: The performance of graph matching algorithms is heavily influenced by how the document is represented as a graph. A representation that works well for one type of document might not be optimal for another.
  • No One-Size-Fits-All: Different graph matching algorithms excel in different scenarios. There isn't a single "best" algorithm across all document types and representations.
  • Simplicity Can Be Effective: For graphs with low edge and node densities (like the GREC dataset), simpler structural modifications (GP, GH, GMNS) can outperform more complex methods like GEDSS.
  • Robustness Varies: Some methods, like Graph Probing (GP) and GEDSS, appear to be more sensitive to the chosen graph representation, suggesting they might be better suited for specific types of structural information.

Key Results

The paper presents precision-recall curves for each dataset and algorithm. While specific quantitative values are not explicitly stated as "best" or "worst" in a summary table, the analysis of the curves reveals:

  • For the GREC database, GP, GH, and GMNS performed similarly and better than GEDSS. GMNS showed a performance peak at low recall.
  • For the Ornamental letters database, most measures performed similarly, with GP showing slightly less performance. The region adjacency graph representation was found to be relatively robust.
  • For the Shape database, Graph Probing (GP) performed poorly compared to other measures. GEDSS yielded the best retrieval results.
  • For the Logo database, all measures showed similar behaviors, with GP leading. Performance was generally better across all methods for this dataset, possibly due to a more suitable graph representation.

Limitations and Future Work

  • Representation Dependency: The authors acknowledge that the performance is highly dependent on the graph representation. They suggest that future work should investigate the behavior of these methods against different representations and document types.
  • Algorithm Sensitivity: The paper notes that GP and GEDSS are more sensitive to the graph representation. Further research could explore how to mitigate this sensitivity or leverage it for specific applications.
  • Beyond ROC: While ROC curves are used, exploring other evaluation metrics or qualitative analyses of retrieval results could provide deeper insights.

Summary updated

Abstract

International audience
BibTeX
@misc{jouili2009evaluation,
  author = {Salim Jouili and Salvatore Tabbone and Ernest Valveny},
  title = {{Evaluation of Graph Matching Measures for Documents Retrieval}},
  year = {2009},
}
Figure