A Path Following Algorithm for the Graph Matching Problem

By Mikhail Zaslavskiy, Francis R. Bach, Jean-Philippe Vert. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008

439 citations recorded by the source corpus.

We propose a convex-concave programming approach for the labeled weighted graph matching problem. The convex-concave programming formulation is obtained by rewriting the weighted graph matching problem as a least-square problem on the set of permutation matrices and relaxing it to two different optimization problems: a quadratic convex and a quadratic concave optimization problem on the set of doubly stochastic matrices. The concave relaxation has the same global minimum as the initial graph matching problem, but the search for its global minimum is also a hard combinatorial problem. We, therefore, construct an approximation of the concave problem solution by following a solution path of a convex-concave problem obtained by linear interpolation of the convex and concave formulations, starting from the convex relaxation. This method allows to easily integrate the information on graph label similarities into the optimization problem, and therefore, perform labeled weighted graph matching. The algorithm is compared with some of the best performing graph matching methods on four data sets: simulated graphs, QAPLib, retina vessel images, and handwritten Chinese characters. In all cases, the results are competitive with the state of the art.

Subfields: Computational Theory and Mathematics, Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/127eb4d3a3b4d2a219cfd0058788144e29778f47

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

An Exact Penalty Method for Binary Optimization Based on MPEC Formulation (2017, neutral): “…problem (Jiang, Liu, and Wen, 2016; Fogel et al., 2015), graph matching (Cour, Srinivasan, and Shi, 2007; Toshev, Shi, and Daniilidis, 2007; Zaslavskiy, Bach, and Vert, 2009), image (co-)segmentation (Shi and Malik, 2000; Joulin, Bach, and Ponce, 2010), image Copyright c© 2017, Association…”
On Graduated Optimization for Stochastic Non-Convex Problems (2015, methodology): “, 2006), graph matching (Zaslavskiy et al., 2009), and ranking (Chapelle & Wu, 2010).”
A review of multimodal image matching: Methods and applications (2021, methodology): “Convex-to-concave relaxations [258,259] aim to gradually achieve convex-to-concave procedure of the original problem by using path-following approaches.”
Power Iterated Color Refinement (2014, methodology): “Computing automorphisms can be approached using continuous optimization formulations for graph isomorphisms, see e.g. (Zaslavskiy, Bach, and Vert 2009; Quadrianto et al. 2010) and references in there.”
Intelligent Reflecting Surface: A Programmable Wireless Environment for Physical Layer Security (2019, methodology): “• We solve the formulated problem efficiently in an iterative manner by developing alternating optimization based path-following algorithm [33], [34].”
Instance-Level Video Segmentation from Object Tracks (2016, methodology): “In order to push our solution away from these near-constant solution, and following the approach of graduated non-convexity [5, 49], we propose to add a concave quadratic term to our objective: Tr(y (1− y)), and weight it using a parameter δ.”
A tensor-based algorithm for high-order graph matching (2009, neutral): “, [3], [32]).”
Image Matching from Handcrafted to Deep Features: A Survey (2020, methodology): “Zaslavskiy et al. (2009) adopted this strategy for GM problem with Koopmans–Beckmann’s QAP formulation, which is extended by to directed graphs (Liu et al. 2012b) and partial matching (Liu and Qiao 2014).”
Factorized Graph Matching (2016, methodology): “In other applications [20], [21], [22], [25], [32], [33], the goal of GM was alternatively formulated as:”
Clique-graph matching by preserving global & local structure (2015, background): “Since this node-wise mapping can not well preserve both global and local structure in the feature subspaces, many researchers have been involved into designing the high order attributes for the formulation of the objective function [4, 20].”
On the Link between Gaussian Homotopy Continuation and Convex Envelopes (2015, background): “Other examples that utilize continuation for optimization are clustering [32], graph matching [31,79,42], multiple instance learning [37], language modeling [3], manifold sampling [58], and `0 norm minimization [65].”
Frank-Wolfe with Subsampling Oracle (2018, background): “…to their low memory requirements and projection-free iterations, which make them particularly appropriate to solve large scale convex problems, for instance convex relaxations of problems written over combinatorial polytopes (Zaslavskiy et al., 2009; Joulin et al., 2014; Vogelstein et al., 2015).”
Fast Exact Hyper-graph Matching with Dynamic Programming for Spatio-temporal Data (2014, neutral): “This work thus falls into the category of methods calculating the exact solution for an approximated model, unlike methods calculating an approximate solution, for instance [5,14,30,48,52,58,59] or methods which perform exact structure preserving matching like [29].”
Low-Rank Optimization on the Cone of Positive Semidefinite Matrices (2008, methodology): “It should be noted that the authors of [16] propose a similar approach to project doubly stochastic matrices onto permutation matrices.”