2010/04/28 by Mikhail Zaslavskiy, Zaslavskiy, Mikhail, Francis Bach +4
Computer Science · Decision Sciences · Mathematics · #Advanced Image and Video Retrieval Techniques #Computer Vision and Pattern Recognition (cs.CV) #Data Quality and Management #FOS: Computer and information sciences #Graph Theory and Algorithms #Machine Learning (stat.ML) #cs.CV #stat.ML
paper · pdf · doi:10.48550/arxiv.1004.4965
19
arxiv created 2010/04/28 · openalex publication_date 2010/04/28 · arxiv updated 2010/04/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Graphs provide an efficient tool for object representation in various computer vision applications. Once graph-based representations are constructed, an important question is how to compare graphs. This problem is often formulated as a graph matching problem where one seeks a mapping between vertices of two graphs which optimally aligns their structure. In the classical formulation of graph matching, only one-to-one correspondences between vertices are considered. However, in many applications, graphs cannot be matched perfectly and it is more interesting to consider many-to-many correspondences where clusters of vertices in one graph are matched to clusters of vertices in the other graph. In this paper, we formulate the many-to-many graph matching problem as a discrete optimization problem and propose an approximate algorithm based on a continuous relaxation of the combinatorial problem. We compare our method with other existing methods on several benchmark computer vision datasets.