Many-to-Many Graph Matching: A Continuous Relaxation Approach
Abstract
Graphs provide an efficient tool for object representation in various machine learning 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 two approximate algorithms based on alternative continuous relaxations of the combinatorial problem. We compare new methods with other existing methods on several benchmark datasets.
Cite
Text
Zaslavskiy et al. "Many-to-Many Graph Matching: A Continuous Relaxation Approach." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2010. doi:10.1007/978-3-642-15939-8_33Markdown
[Zaslavskiy et al. "Many-to-Many Graph Matching: A Continuous Relaxation Approach." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2010.](https://mlanthology.org/ecmlpkdd/2010/zaslavskiy2010ecmlpkdd-manytomany/) doi:10.1007/978-3-642-15939-8_33BibTeX
@inproceedings{zaslavskiy2010ecmlpkdd-manytomany,
title = {{Many-to-Many Graph Matching: A Continuous Relaxation Approach}},
author = {Zaslavskiy, Mikhail and Bach, Francis R. and Vert, Jean-Philippe},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2010},
pages = {515-530},
doi = {10.1007/978-3-642-15939-8_33},
url = {https://mlanthology.org/ecmlpkdd/2010/zaslavskiy2010ecmlpkdd-manytomany/}
}