PaperlayerView exact revision on arXiv

Source-linked AI summary

A path following algorithm for the graph matching problem

Mikhail Zaslavskiy, Francis Bach, Jean-Philippe Vert

arXiv:0801.3654v2cs.CVcs.DM

TL;DR

Large-scale graph matching is combinatorial, and labeled matching additionally requires balancing structural and label compatibility. The paper proposes PATH, which follows solutions from convex to concave relaxations, and reports competitive performance with competitive complexity across graph-matching and QAP benchmarks. The method remains approximate in general because tracked local minima may not be global minima.

  • Problem

    Graph matching is hard to solve exactly for large graphs because its permutation-based objective is combinatorial.

  • Method

    PATH rewrites labeled weighted matching as a QAP, relaxes it into convex and concave problems over doubly stochastic matrices, and follows an interpolated solution path.

  • Results

    PATH is competitive with state-of-the-art methods and has theoretical and empirical complexity competitive with the fastest available graph-matching algorithms.

  • Takeaways & Limitations

    PATH integrates graph structure with vertex-label similarity in a single approximate graph-matching formulation.

  • Takeaways & Limitations

    PATH only approximates the global minimum in general because tracked local minima may not be global minima.

Abstract

from arXiv · show

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 to perform labeled weighted graph matching. The algorithm is compared with some of the best performing graph matching methods on four datasets: simulated graphs, QAPLib, retina vessel images and handwritten chinese characters. In all cases, the results are competitive with the state-of-the-art.

1 Introduction

Graph matching seeks an optimal vertex correspondence but is difficult to solve exactly at large scale. The paper introduces PATH, an approximate convex-concave method for labeled weighted matching and evaluates it across several benchmarks.

  • Motivation: Exact graph matching is difficult for large graphs because of the problem’s combinatorial nature.Incomplete enumeration can find exact optima for some small or sparse graphs.
  • Existing approaches: Approximate methods improve scalability but generally return only an approximation of the optimal matching.Existing approaches include spectral methods and methods based directly on the matching objective.
  • Labeled matching: Labeled graph matching must align both graph structure and vertex labels using similarities between labels.Methods using only label similarities are fast and simple but do not account for graph structure.
  • Contribution: PATH formulates labeled weighted matching as a QAP, relaxes it to convex and concave problems on doubly stochastic matrices, and follows a solution path between them.The quadratic term represents structural compatibility, while the linear term represents local compatibility.
  • Evaluation: The paper compares PATH with established graph matching methods on simulated graphs, QAP benchmarks, retina vessel images, and handwritten Chinese characters.The introduction states that these comparisons produce competitive results.

2 Problem description

The paper represents graph correspondences with permutation matrices and measures structural or label mismatch through optimization objectives. It then situates approximate methods through relaxations, spectral representations, and the geometry of doubly stochastic matrices.

  • Problem formulation: For equal-sized graphs, a correspondence is represented by a permutation matrix with one 1 in every row and column.Permuting H gives adjacency matrix AP(H) = PAHP^T.
  • Problem formulation: Matching quality is measured by the discrepancy between the aligned graphs, counted by differing edges or total differing edge weight.This discrepancy is expressed through adjacency matrices and a norm-based objective.
  • Problem formulation: Graph matching minimizes the objective over permutation matrices, but the resulting optimization is combinatorial and has no known polynomial-time algorithm.This difficulty motivates the development of approximate methods for large graphs.
  • Labeled matching: Labeled matching combines structural fidelity with vertex-label fitness through a convex combination controlled by α.Small α emphasizes structure, whereas large α emphasizes labels.
  • Relaxations: Doubly stochastic matrices form a convex set whose extreme points are permutation matrices, making linear optimization over the permutation set polynomially solvable.The Hungarian algorithm solves the corresponding linear problem in O(N^3).
  • Existing approximate methods: Spectral methods match vertices using adjacency-matrix eigenvector coordinates, but sign flips and rotations within repeated-eigenvalue subspaces make the embeddings non-unique.Umeyama’s method uses absolute eigenvector values and solves its linear assignment problem with the Hungarian algorithm in O(N^3).
  • Existing approximate methods: Linear-programming approaches relax optimization from permutation matrices to doubly stochastic matrices and then project the solution back to a permutation matrix.The projection can use the Hungarian algorithm, but the O(N^2)-scale linear program becomes difficult for graphs larger than roughly one hundred nodes.

3 Convex-concave relaxation

The paper relaxes graph matching from permutation matrices to doubly stochastic matrices through convex and concave quadratic formulations. PATH interpolates between these formulations and tracks local minima to approximate the hard concave problem.

  • Convex and concave relaxations: Graph matching minimizes the structural discrepancy F0(P) over permutation matrices P.The formulation uses the squared Frobenius norm between adjacency matrices.
  • Convex and concave relaxations: The convex relaxation QCV minimizes F0 over doubly stochastic matrices and is efficiently solvable, but its solution generally requires projection onto permutation matrices.Projection can be poor when the relaxed solution lies far from the permutation set.
  • Convex and concave relaxations: The concave relaxation QCC minimizes F1 over doubly stochastic matrices and has the same solution as the original graph matching problem.Because a concave function reaches its minimum on the boundary, the minimum over doubly stochastic matrices lies in the permutation set.
  • PATH algorithm: PATH approximately solves QCC by tracking local minima of Fλ(P)=(1−λ)F0(P)+λF1(P) as λ increases from 0 to 1.It starts from the unique convex minimum at λ=0 and successively locally optimizes the interpolated functions.
  • PATH algorithm: The two relaxations coincide up to a constant on permutation matrices, so a PATH minimum reaching that set is globally optimal for the initial problem.The paper illustrates this case when the interpolated function has a boundary minimum.
  • PATH algorithm: PATH remains approximate because increasing λ can create new local minima, and the tracked sequence need not contain global minima.The paper gives simple examples where PATH succeeds and fails to find the global minimum.

3.4 Numerical continuation method interpretation

The authors interpret PATH as numerical continuation over KKT solution branches, moving through local-minimum segments as λ varies. Implementation combines adaptive continuation steps with Frank-Wolfe optimization and specialized linear-algebra operations.

  • Numerical continuation interpretation: PATH is a numerical continuation method that tracks stationary solutions of interpolated problems parameterized by λ.Its KKT systems define curves of stationary points associated with active constraint sets.
  • Numerical continuation interpretation: Each active constraint set defines a smooth one-dimensional solution curve, and PATH can jump between curves when continuation events occur.The tracked solutions may move along segments and switch constraint sets before λ reaches 1.
  • Optimization procedure: Frank-Wolfe optimizes each new interpolated objective by solving a linear program and performing a line search over the resulting segment.The linear program can be solved by the Hungarian algorithm in O(N^3).
  • Implementation details: The Newton step can be computationally demanding because it may require inversion of matrices of size O(N^2) × O(N^2).When no nonnegativity constraints are active, Kronecker-product structure reduces the calculation to O(N^3) instead of O(N^6).
  • Implementation details: The Newton step is generally usable only once because subsequent active nonnegativity constraints prevent the same efficient calculations.Even then, it usually substantially decreases the objective value.
  • Adaptive continuation: PATH adapts dλ by doubling it when objective changes stay below ελ and halving it when they exceed ελ, subject to dλmin=10^-5.The scheme uses larger steps for smoother changes and smaller steps when the objective is sensitive to λ.
  • Adaptive continuation: The parameter M controls the allowed relaxation of stopping criteria and therefore the width of the tube around the path of optimal solutions.Larger M permits moving farther from a local minimum and using larger dλ.

3.6 Algorithm complexity

The paper analyzes the complexity of the algorithms, emphasizing that PATH’s graph-size cost is dominated by each Frank-Wolfe iteration rather than iteration count.

  • Umeyama’s algorithm has complexity O(N^3), while the LP approach has worst-case complexity O(N^7).
  • PATH complexity depends on ε_FW, M, and N, with ε_FW controlling Frank-Wolfe precision and M influencing path-following behavior.The ratio parameter M affects the number of optimization runs, while ε_FW affects algorithm precision and speed.
  • The graph size N is not crucial for the number of Frank-Wolfe iterations but strongly increases the cost of each iteration.Gradient estimation and linear minimization over doubly stochastic matrices can each be performed in O(N^3).

3.7 Vertex pairwise similarities

The method incorporates pairwise vertex-label similarities into graph matching and addresses unequal graph sizes through alternative matching-error definitions and dummy vertices.

  • Pairwise similarities between graph vertices can improve labeled graph matching by adding local compatibility information to the objective.The approach uses F_λ(P), which includes the vertex-similarity information while retaining the same minimization algorithm.
  • For unequal graph sizes, three matching-error definitions differ in whether unmatched-subgraph and omitted-edge terms are counted.These alternatives correspond to different matrix dimensions and treatments of edges within and outside the selected subgraph.
  • Adding dummy isolated vertices to the smaller graph is presented as the preferred strategy for unequal-size matching.The transformation pads the smaller adjacency matrix with zero rows and columns, allowing equal-size matching.
  • The dummy-vertex strategy avoids favoring very sparse candidate subgraphs solely because the objective minimizes mismatched rather than well-matched edges.Edges connecting selected and unselected vertices contribute to the error, reducing the quality of overly sparse selections.

4 Simulations

Simulations compare PATH with classical and convex alternatives on noisy random graphs across small, medium, and large sizes. PATH performs best among approximate methods, while runtime comparisons reflect the algorithms’ complexity differences.

  • The simulations generate random graphs from binomial, exponential, and power degree distributions, then add σNE noisy edges to test non-isomorphic matching.Here NE is the original edge count and σ is the noise level.
  • For N=8, experiments compare PATH, QCV, Umeyama, LP, and exhaustive search using matching error over samples of 100 graphs.Figures 4–6 extend the comparison to N=20 and N=100.
  • Across N=8, N=20, and N=100 experiments, PATH works much better than the other approximate algorithms and approaches the optimal solution when evaluable.The results also indicate that QCV and LP perform similarly, while path following improves over convex relaxation followed by projection.
  • Matching error can decrease as noise increases because denser graphs reduce the upper bound determined by zeros in the adjacency matrices.At very high graph density, matching error decreases generally across algorithms.
  • Increasing M makes PATH faster but reduces how precisely it follows the path of local minima.When M approaches 1/ε_FW, the algorithm jumps directly from the convex to the concave function.
  • Umeyama is fastest, QCV and PATH have the same graph-size complexity, and LP is competitive on small graphs but scales worse with N.Figure 8 reports slopes of approximately 3.4 for U, QCV, and PATH and approximately 6.7 for LP.

5 QAP benchmark library

The QAP benchmark evaluation compares PATH with established approximate methods and finds PATH best on most tested instances.

  • Graph matching is treated as a particular case of the quadratic assignment problem, motivating comparison with QAP-specific approximate algorithms.
  • On 14 out of 16 QAPLIB benchmarks, PATH is the best optimization method among the methods tested.The comparison uses results for QPB, graduated assignment, and Umeyama’s algorithm from the benchmark study.

6 Image processing

The paper evaluates PATH on vessel-image alignment and handwritten-character classification, showing that incorporating graph structure with label information improves results over shape-context or weaker graph-matching alternatives.

  • 6.1 Alignment of vessel images: PATH aligns vessel contours more coherently than shape context by accounting for relational positions between matched points.Shape context creates unwanted matches, whereas PATH produces a visually correct structural alignment.
  • 6.1 Alignment of vessel images: PATH achieves the smallest matching error on vessel alignment, followed by QCV, while Umeyama fails to find a correct alignment visually.The reported visual failures of Umeyama resemble those of shape context.
  • 6.2 Recognition of handwritten chinese characters: The character experiment uses KNN matching scores for classification and evaluates parameter effects with five-fold cross-validation.The dataset contains 50 images per class, represented as 63 × 64 binary matrices.
  • Figures: Figure 10 compares bidirectional spline-based alignments from shape context and PATH, while Figure 12 plots classification error against α and k.Figure 9 shows eye photographs and extracted vessel contours; Figure 11 shows ETL9B Chinese characters.
  • 6.2 Recognition of handwritten chinese characters: Combining shape-context labels with graph structure reduces handwritten-character classification error from about 39% to 25%.Pure unlabeled graph matching yields about 60% error, while PATH outperforms QCV and Umeyama.

7 Conclusion

The conclusion presents PATH as a convex-concave graph-matching method that combines structural and label alignment, reports competitive performance and complexity, and identifies relaxation design and directed-graph extensions as open directions.

  • Conclusion: PATH integrates graph-structure alignment with matching vertices that have similar labels through convex-concave relaxations.The method is based on relaxing the initial integer programming problem.
  • Conclusion: PATH achieves results competitive with state-of-the-art methods across several graph-matching and QAP benchmark experiments.
  • Conclusion: PATH has theoretical and empirical complexity competitive with the fastest available graph-matching algorithms.
  • Future research: Better performance may result from choosing more appropriate convex and concave relaxation functions.
  • Future research: Constructing a concave relaxation for directed graph matching remains an open direction, with possible relevance to approximate solutions for general QAP.

A A toy example

The toy examples examine when PATH’s tracked local-minimum path reaches the global optimum, showing that discontinuous global-minimum paths can defeat the method while modified costs can produce success.

  • Toy example: PATH does not generally find the global optimum of the NP-complete optimization problem.The appendix uses two simple graphs to illustrate successful and unsuccessful path tracking.
  • Toy example: The examples vary the cost matrix, tradeoff parameter α, and objective F_λ to study global-minimum path behavior.
  • Toy example: For small graphs, the exact global minimum of F_λ can be computed across λ and visualized through the nine coordinates of a doubly stochastic matrix.At λ = 1, the coordinates are expected to be zero or one.
  • Toy example: When λ is near 0.2, the global minimum jumps from one face to another, so the tracked path is not smooth.
  • Toy example: Changing the linear term C makes the trace smooth, allowing PATH to find the globally optimal point.The paper states that characterizing when the path is smooth remains ongoing research.

B Kronecker product

This appendix introduces the Kronecker product and identifies two of its properties as important for the paper’s derivations.

  • Kronecker product: The Kronecker product A ⊗ B is introduced before its properties are used in the paper.
  • Kronecker product: The paper presents the block-matrix form of the Kronecker product for matrices A and B.
  • Kronecker product: Two properties of the Kronecker product are identified as important for the paper.The supplied passage does not state the properties themselves.
Loading 0801.3654v2…