Graph Matching: Relax at Your Own Risk.

Area of Science:

• Graph theory
• Combinatorics
• Computer Vision
• Computational Neuroscience (Connectomics)

Background:

• Graph matching is a fundamental problem in aligning graph pairs, crucial for fields like computer vision and connectomics.
• Existing heuristic methods for graph matching often lack theoretical guarantees on performance.
• Continuous relaxation techniques enable gradient-descent algorithms but have limitations.

Purpose of the Study:

• To theoretically analyze the performance of different continuous relaxations for graph matching.
• To propose and validate a hybrid approach combining indefinite and convex relaxations for improved graph matching accuracy.

Main Methods:

• Theoretical analysis of indefinite and convex relaxations for graph matching.
• Proving that exact solutions to indefinite relaxations typically yield optimal permutations.
• Demonstrating that common convex relaxations often fail to find optimal permutations.

Main Results:

• The study proves that indefinite relaxations, when solved exactly, almost always find the optimal permutation for graph matching.
• Conversely, common convex relaxations are shown to frequently fail in discovering the optimal permutation.
• Experimental validation confirms that initializing indefinite algorithms with convex optima enhances practical performance.

Conclusions:

• Indefinite relaxations offer superior theoretical guarantees for solving the graph matching problem compared to convex relaxations.
• A hybrid approach, leveraging the strengths of both convex and indefinite relaxations, achieves excellent results on benchmark and real-world graph matching tasks.