Kernel on Bag of Paths For Measuring Similarity of Shapes

Frédéric Suard, Alain Rakotomamonjy, Abdelaziz BensrhairESANN 2007 · OpenReview

Abstract

This paper introduces a novel framework for measuring shape similarity by representing objects as "bags of paths" derived from their skeletal graphs. By applying advanced kernel functions—specifically the "path level-set kernel"—the authors achieve state-of-the-art performance in shape retrieval, outperforming traditional graph-matching techniques on the Rutgers Tools Database.

Introduction

Object recognition often relies on analyzing an object's shape. A common way to represent shape is through "shock graphs" or skeletons, which capture the topological structure of an object. However, comparing two graphs to determine similarity is a notoriously difficult problem in computer science. Traditional methods, such as graph edit-distance, are computationally expensive and difficult to integrate with modern machine learning algorithms like Support Vector Machines (SVMs). This paper seeks to bridge the gap between structural graph representation and kernel-based statistical learning.

Methodology: Bag of Paths

The authors propose representing a graph not as a single entity, but as a Bag of Paths.

Path Generation

Instead of using "random walks"—a common technique that can suffer from "tottering" (repeatedly moving back and forth between nodes)—the authors use shortest paths between all pairs of vertices in the graph, calculated via Dijkstra’s algorithm. This ensures a finite, representative set of structural features.

Skeletal graph representations of various shapes, illustrating the structural features used for path extraction.

Merging Strategies

The core innovation lies in how individual path similarities are combined into a single score for the whole graph. Three approaches are compared:

  • Mean Average Kernel: A simple average of all path-pair similarities.
  • Matching Kernel: A focused approach that finds the "best match" for each path, using a positive-definite approximation.
  • Path Level-Set Kernel: The most advanced method, which uses a one-class SVM to estimate the "support" of the path distribution for each graph and then compares those supports.

Experimental Setup

The researchers evaluated their approach using the Rutgers Tools Database, which contains 25 objects categorized into 8 classes (five tool categories and three biological shape categories). The primary task was shape retrieval, where each object is used as a query to find and rank the most similar objects from the rest of the database.

Results and Discussion

The proposed framework demonstrated significant improvements over existing benchmarks.

Performance and Robustness

Both the "Path Level-Set Kernel" and the "Matching Kernel" were reported to achieve a 100% recognition rate for the best match on the Rutgers dataset, surpassing previous state-of-the-art algorithms which reached 96%. The path level-set kernel proved remarkably stable, maintaining perfect recognition rates across various path lengths.

Recognition rate for best match as a function of maximal path length across different kernel strategies.

The Role of Path Length

The authors found that path length acts as a "zoom" level. Very short paths (length 0) only look at local nodes, while longer paths capture more global structure. As shown in the performance analysis, there is a "sweet spot" (usually length 2 or 3) where the most discriminative information is captured. By focusing on shortest paths, the authors avoid convergence issues and ensure the set of paths is of finite cardinality.

Conclusion

While the "bag of paths" approach is highly effective, there is room for improvement. The current system uses relatively simple labels for graph nodes; incorporating more complex local descriptors, such as texture features, could enhance discriminative power. Additionally, while the "best match" was always correct, the system occasionally struggled with fine-grained classification between very similar classes. Future work will also need to address the computational scalability of generating all-pairs shortest paths for larger, denser graphs.

Summary updated

BibTeX
@inproceedings{suard2007kernel,
  author = {Frédéric Suard and Alain Rakotomamonjy and Abdelaziz Bensrhair},
  title = {{Kernel on Bag of Paths For Measuring Similarity of Shapes}},
  booktitle = {ESANN},
  year = {2007},
  url = {https://openreview.net/forum?id=5aP54Od-xR},
}
Figure