On convex relaxation of graph isomorphism

Area of Science:

• Graph theory
• Combinatorial optimization
• Spectral graph theory

Background:

• Graph matching seeks optimal vertex correspondence to minimize weight disagreement.
• Commonly relaxed to convex quadratic programming using doubly stochastic matrices.
• The effectiveness of this relaxation for graph isomorphism is not well understood.

Purpose of the Study:

• Define and analyze a class of "friendly graphs" for which graph matching relaxations are guaranteed to succeed.
• Extend results to approximate graph isomorphism.
• Develop more efficient relaxations for graph matching.

Main Methods:

• Spectral analysis to identify "friendly graphs" based on verifiable properties.
• Convex quadratic programming relaxation of the graph matching problem.
• Theoretical analysis of relaxation guarantees for exact and approximate isomorphism.

Main Results:

• Introduced "friendly graphs" with a specific spectral property.
• Proved that for friendly graphs, the convex relaxation correctly identifies graph isomorphism or its absence.
• Developed bounds for globally optimal approximate graph isomorphism.
• Showed a more efficient relaxation using n separable linear equality constraints.
• Extended validity to "unfriendly graphs" with additional seed or attribute information.

Conclusions:

• The proposed spectral property effectively identifies graphs where convex relaxation guarantees accurate isomorphism detection.
• Significant computational efficiency gains are achieved through a simplified relaxation.
• The framework extends to approximate matching and can incorporate auxiliary data for challenging cases.