Source-linked AI summary
Graph Matching: Relax at Your Own Risk
Vince Lyzinski, Donniell Fishkind, Marcelo Fiori, Joshua T. Vogelstein, Carey E. Priebe, Guillermo Sapiro
TL;DR
Graph matching seeks a low-disagreement alignment but is computationally difficult, motivating continuous relaxations. This paper compares convex and indefinite relaxations theoretically and empirically, finding that the indefinite approach is accurate while convex initialization can improve its practical solution.
Problem
Graph matching asks for a permutation aligning two graphs while minimizing adjacency disagreements, a difficult problem with applications across scientific and engineering domains.
Method
The paper analyzes convex and indefinite relaxations over doubly stochastic matrices and studies how their solutions relate to the original permutation problem.
Results
The indefinite relaxation almost always recovers the optimal permutation, whereas the convex relaxation almost always fails under the correlated Bernoulli model.
Takeaways & Limitations
Experiments on real data and benchmark problems find best performance by using the convex solution to initialize an approximate indefinite solver.
Takeaways & Limitations
The theory is established for correlated random Bernoulli graphs, and highly regular or symmetric random graph models were not experimentally included.
Abstract
from arXiv · showhide
Graph matching---aligning a pair of graphs to minimize their edge disagreements---has received wide-spread attention from both theoretical and applied communities over the past several decades, including combinatorics, computer vision, and connectomics. Its attention can be partially attributed to its computational difficulty. Although many heuristics have previously been proposed in the literature to approximately solve graph matching, very few have any theoretical support for their performance. A common technique is to relax the discrete problem to a continuous problem, therefore enabling practitioners to bring gradient-descent-type algorithms to bear. We prove that an indefinite relaxation (when solved exactly) almost always discovers the optimal permutation, while a common convex relaxation almost always fails to discover the optimal permutation. These theoretical results suggest that initializing the indefinite algorithm with the convex optimum might yield improved practical performance. Indeed, experimental results illuminate and corroborate these theoretical findings, demonstrating that excellent results are achieved in both benchmark and real data problems by amalgamating the two approaches.
1 INTRODUCTION
The paper formulates graph matching as minimizing adjacency disagreements over permutation matrices, then compares convex and indefinite continuous relaxations. Its main result shows a sharp trade-off: the convex relaxation almost always fails under the stated random-graph model, whereas the indefinite relaxation almost always recovers the correct permutation.
- Problem formulation: Graph matching minimizes the Frobenius discrepancy between A and a permuted B over permutation matrices.The Frobenius norm counts adjacency disagreements induced by the corresponding vertex bijection.
- Problem formulation: The equivalent objective −⟨AP, PB⟩ replaces discrepancy minimization with maximizing agreement between aligned adjacency structures.
- Relaxations: The convex relaxation minimizes ∥AD −DB∥2_F over doubly stochastic matrices, while the indefinite relaxation minimizes −⟨AD, DB⟩ over the same domain.The convex problem is polynomial-time solvable exactly; the indefinite objective is nonconvex and generally intractable.
- Main result: For correlated random Bernoulli graphs, Theorem 1 states that the true permutation is almost always the unique discrete optimum under its stated condition.
- Main result: When the between-graph correlation ρ is below one, the correct permutation is almost always not a solution of the convex relaxation.The convex optimum can lie closest to an incorrect permutation, so projection need not recover the truth.
- Implication: The proofs and experiments motivate using the convex solution to initialize an approximate solver for the indefinite relaxation.The proof of the indefinite result uses disagreement counting and the Birkhoff–von Neumann representation of doubly stochastic matrices.
3 PROOF OF THEOREM 1, PART B
The proof of the convex-relaxation failure shows that the identity permutation is almost surely not a KKT point. It combines necessary KKT conditions with concentration bounds whose failure probability decays exponentially in graph size.
- Probabilistic bounds: Concentration arguments control diagonal and off-diagonal terms using independent bounded random variables and Hoeffding-type bounds.The proof separately analyzes a sum that dominates a binomial variable and a centered sum of variables taking values in {−1, 0, 1}.
- KKT reduction: The proof reduces convex-relaxation optimality to whether the identity matrix is a KKT point of the constrained problem.Because the objective is convex and the feasible region is defined by affine constraints, any local or global optimizer must satisfy KKT conditions.
- KKT conditions: The KKT system incorporates unrestricted row- and column-sum multipliers and nonnegative multipliers for entrywise nonnegativity.Complementary slackness forces the diagonal nonnegativity multipliers to vanish at the identity.
- Gradient condition: At the identity, the gradient simplifies to ∇ = 2A^2 + 2B^2 − 4AB, yielding a necessary relation involving (A − B)^T(A − B).
- Conclusion: The probability that the necessary KKT relation holds decays exponentially in n, so the identity is almost always not a convex-relaxation minimizer.
4 EXPERIMENTAL RESULTS
Experiments corroborate the tractability–correctness trade-off and show that initializing the indefinite relaxation with the convex solution yields strong practical performance. The approach performs well across simulations, real data, and benchmark problems, while projection and graph structure impose important boundaries.
- On the convex relaxed graph matching problem: The convex relaxation can produce a doubly stochastic solution whose projection fails to recover the true permutation, even when the unrelaxed optimum is correct.Projection is especially unreliable when the convex solution lies near the barycenter.
- On the convex relaxed graph matching problem: For ρ > 0.9, the convex solution moves toward the true permutation, which is typically recovered by projection.At lower correlations, the solution is often far from the permutation boundary.
- On indefinite relaxed graph matching problem: Initializing the indefinite relaxation with D∗ improves graph matching performance over alternative initializations and is computationally less intensive than PATH and GLAG.The combined procedure uses the tractable convex solution to initialize a nonconvex local search.
- On indefinite relaxed graph matching problem: For 0.35 < ρ < 0.75, FAQ:D∗ can reach a substantially suboptimal local minimum before transitioning near ρ ≈ 0.75 to recovering P∗ without projection.The objective gap helps distinguish failure from successful recovery.
- Real data and benchmark experiments: Across real-data examples and 16 QAPLIB benchmarks, intelligently initialized indefinite relaxation achieved the best reported performance.In real data, FAQ:D∗ was computationally inexpensive relative to GLAG and PATH.
- Other random graph models: Power-law graphs and regular or nearly regular graphs expose structural boundaries: recovery can remain strong for p ≤ 0.3, but regularity can make even isomorphic instances ill-conditioned.The experiments excluded highly regular and symmetric random graph models.
5 CONCLUSIONS
The paper finds that exact indefinite relaxation is usually correct while convex relaxation usually fails, and experiments support combining them by initializing the indefinite method with the convex solution.
- The indefinite relaxation obtains the optimal graph-matching solution with high probability under mild conditions, whereas the convex relaxation almost always fails to find the correct permutation.
- Experiments in simulations and real data corroborate that approximately solving the intractable indefinite problem produces the best results.
- Initializing the indefinite algorithm with the convex solution combines the two approaches and provides a computationally tractable algorithm with state-of-the-art performance.