TL;DR
This paper analyzes the success of a common convex relaxation for graph matching when dealing with symmetric graphs, particularly relevant for shape matching. The authors show that "convex exactness" (where the relaxation correctly identifies isomorphisms) is a property that either holds for almost all symmetric graphs of a given symmetry type or fails for all of them. They identify conditions for when this exactness holds, offering insights into how to reliably recover graph isomorphisms from symmetric structures.
What Problem Does This Paper Address?
The core problem is graph matching, which aims to find the best alignment between two graphs. This is a computationally hard problem (NP-hard). A popular approach is to relax the problem into a convex optimization problem over doubly stochastic (DS) matrices. While this relaxation is known to work well for asymmetric isomorphic graphs, its behavior for symmetric isomorphic graphs is less understood. Symmetric graphs, common in applications like shape matching, have multiple possible isomorphisms, which can lead to the convex relaxation producing solutions that are not actual isomorphisms. This paper investigates when the DS relaxation can still reliably recover the true isomorphisms in the presence of symmetry.
Methods
The paper introduces and analyzes the concept of "convex exactness" for the doubly stochastic (DS) relaxation of graph matching. This means that the set of solutions to the relaxed problem exactly corresponds to the set of true isomorphisms, without any extraneous convex combinations. The authors develop theoretical tools to analyze this property, focusing on the role of the graph's symmetry group. They prove that for certain types of symmetry groups (reflective groups with a "full orbit"), convex exactness holds generically (for almost all graphs with that symmetry). They also introduce and analyze the "centroid solution," which is the average of all possible isomorphisms, and show it can be efficiently recovered.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and uses synthetic examples to illustrate concepts.
Key Insights and Ideas
- Symmetry is Key: The success of the DS relaxation for graph matching is highly dependent on the type of symmetry present in the graphs.
- "All or Nothing" Property: For a given symmetry group, the DS relaxation is either "convex exact" for almost all symmetric isomorphic graphs, or it fails for all of them. There's no in-between for a specific symmetry type.
- Reflective Symmetries are Good: Graphs with reflective symmetries and a "full orbit" (where a vertex is not on an axis of symmetry) are likely to yield convex exactness. This is highly relevant for shape matching.
- Centroid as a Fuzzy Encoding: The average of all isomorphisms (the centroid solution) provides a meaningful "fuzzy encoding" of the shape's symmetries and can be efficiently computed.
- Interior-Point Solvers Miss Permutations: For symmetric problems where convex exactness holds, standard interior-point optimization methods will converge to the centroid solution, not necessarily a specific permutation isomorphism.
Key Results
- Theorem 1: For reflective symmetry groups with a full orbit, the DS relaxation is convex exact for almost all graphs in that symmetry class.
- Corollary 1: This implies convex exactness holds generically for $Z_2$ symmetry groups, common in bilateral symmetry.
- Theorem 2: For any symmetry group, either the DS relaxation is convex exact for almost all graphs, or it's never convex exact.
- Efficient Centroid Recovery: The centroid solution can be efficiently computed for almost all symmetric isomorphic graphs.
- Projection Methods: The paper theoretically analyzes and experimentally evaluates projection methods (like "convex to concave") for retrieving isomorphisms, showing their effectiveness, especially the "convex to concave" method, in the presence of noise.
Limitations and Future Work
- Non-Reflective Symmetries: The paper highlights that non-reflective symmetry groups can behave very differently, and convex exactness is not guaranteed. Figure 2 and Table 1 illustrate this with examples where convex exactness fails for certain non-reflective groups.
- Computational Cost: While the centroid solution is efficient, finding all extreme points (specific isomorphisms) can still be computationally intensive, especially for large graphs.
- Noise Sensitivity: While projection methods are explored for noisy data, the paper suggests further investigation into choosing optimal parameters for these methods.
- General Group Behavior: The "zero-one probability" result (Theorem 2) is powerful but requires a method to check which of the two outcomes (generic exactness or no exactness) applies to a given symmetry group. The paper outlines this checking process.
Summary updated