Kernelized multi-graph matching

François-Xavier Dupé, Rohit Yadav, Guillaume Auzias, Sylvain Takerkart
Proceedings of The 14th Asian Conference on Machine Learning, PMLR 189:311-326, 2023.

Abstract

Multigraph matching is a recent variant of the graph matching problem. In this framework, the optimization procedure considers several graphs and enforces the consistency of the matches along the graphs. This constraint can be formalized as a cycle consistency across the pairwise permutation matrices, which implies the definition of a universe of vertex (Pachauri et al., 2013). The label of each vertex is encoded by a sparse vector and the dimension of this space corresponds to the rank of the bulk permutation matrix, the matrix built from the aggregation of all the pairwise permutation matrices. The matching problem can then be formulated as a non-convex quadratic optimization problem (QAP) under constraints imposed on the rank and the permutations. In this paper, we introduce a novel kernelized multigraph matching technique that handles vectors of attributes on both the vertices and edges of the graphs, while maintaining a low memory usage. We solve the QAP problem using a projected power optimization approach and propose several projectors leading to improved stability of the results. We provide several experiments showingthat our method is competitive against other unsupervised methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v189-dupe23a, title = {Kernelized multi-graph matching}, author = {Dup{\'e}, Fran{\c c}ois-Xavier and Yadav, Rohit and Auzias, Guillaume and Takerkart, Sylvain}, booktitle = {Proceedings of The 14th Asian Conference on Machine Learning}, pages = {311--326}, year = {2023}, editor = {Khan, Emtiyaz and Gonen, Mehmet}, volume = {189}, series = {Proceedings of Machine Learning Research}, month = {12--14 Dec}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v189/dupe23a/dupe23a.pdf}, url = {https://proceedings.mlr.press/v189/dupe23a.html}, abstract = {Multigraph matching is a recent variant of the graph matching problem. In this framework, the optimization procedure considers several graphs and enforces the consistency of the matches along the graphs. This constraint can be formalized as a cycle consistency across the pairwise permutation matrices, which implies the definition of a universe of vertex (Pachauri et al., 2013). The label of each vertex is encoded by a sparse vector and the dimension of this space corresponds to the rank of the bulk permutation matrix, the matrix built from the aggregation of all the pairwise permutation matrices. The matching problem can then be formulated as a non-convex quadratic optimization problem (QAP) under constraints imposed on the rank and the permutations. In this paper, we introduce a novel kernelized multigraph matching technique that handles vectors of attributes on both the vertices and edges of the graphs, while maintaining a low memory usage. We solve the QAP problem using a projected power optimization approach and propose several projectors leading to improved stability of the results. We provide several experiments showingthat our method is competitive against other unsupervised methods.} }
Endnote
%0 Conference Paper %T Kernelized multi-graph matching %A François-Xavier Dupé %A Rohit Yadav %A Guillaume Auzias %A Sylvain Takerkart %B Proceedings of The 14th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Emtiyaz Khan %E Mehmet Gonen %F pmlr-v189-dupe23a %I PMLR %P 311--326 %U https://proceedings.mlr.press/v189/dupe23a.html %V 189 %X Multigraph matching is a recent variant of the graph matching problem. In this framework, the optimization procedure considers several graphs and enforces the consistency of the matches along the graphs. This constraint can be formalized as a cycle consistency across the pairwise permutation matrices, which implies the definition of a universe of vertex (Pachauri et al., 2013). The label of each vertex is encoded by a sparse vector and the dimension of this space corresponds to the rank of the bulk permutation matrix, the matrix built from the aggregation of all the pairwise permutation matrices. The matching problem can then be formulated as a non-convex quadratic optimization problem (QAP) under constraints imposed on the rank and the permutations. In this paper, we introduce a novel kernelized multigraph matching technique that handles vectors of attributes on both the vertices and edges of the graphs, while maintaining a low memory usage. We solve the QAP problem using a projected power optimization approach and propose several projectors leading to improved stability of the results. We provide several experiments showingthat our method is competitive against other unsupervised methods.
APA
Dupé, F., Yadav, R., Auzias, G. & Takerkart, S.. (2023). Kernelized multi-graph matching. Proceedings of The 14th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 189:311-326 Available from https://proceedings.mlr.press/v189/dupe23a.html.

Related Material