Exact Recovery with Symmetries for the Doubly Stochastic Relaxation

Nadav DymSIAM J. Appl. Algebra Geom 2018 · OpenReview

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

Abstract

Graph matching, or quadratic assignment, is the problem of labeling the vertices of two graphs so that they are as similar as possible. A common method for approximately solving the NP-hard graph matching problem is relaxing it to a convex optimization problem over the set of doubly stochastic (DS) matrices. Recent analysis has shown that for almost all pairs of isomorphic and asymmetric graphs, the DS relaxation succeeds in correctly retrieving the isomorphism between the graphs. Our goal in this paper is to analyze the case of symmetric isomorphic graphs. This goal is motivated by shape matching applications where the graphs of interest usually have reflective symmetry. For symmetric problems the graph matching problem has multiple isomorphisms, and so convex relaxations admit all convex combinations of these isomorphisms as viable solutions. If the convex relaxation does not admit any additional superfluous solution, we say that it is convex exact. We show that convex exactness depends strongly on the symmetry group of the graphs; for a fixed symmetry group $G$, the DS relaxation either will be convex exact for almost all pairs of isomorphic graphs with symmetry group $G$, or will fail for all such pairs. We show that for reflective groups with at least one full orbit, convex exactness holds almost everywhere. The importance of this result stems from the fact that such groups are the most common symmetry groups in shape matching applications. Finally, we provide some simple examples of nonreflective symmetry groups for which convex exactness always fails. These examples also show that the property of having generic convex exactness is not invariant under group isomorphisms. When convex exactness holds, the isomorphisms of the graphs are the extreme points of the convex solution set and the task of finding an isomorphism in polynomial time is tractable. We discuss several common algorithms capable of retrieving an isomorphism in this case. We also show that interior point algorithms will not return an isomorphism in this case but will return the centroid of the set of isomorphisms, which gives a “fuzzy encoding” of the symmetries of the shape. In fact, for any symmetry group $G$, the centroid solution can be recovered efficiently for almost all pairs of isomorphic graphs with symmetry group $G$.
BibTeX
@article{dym2018exact,
  author = {Nadav Dym},
  title = {{Exact Recovery with Symmetries for the Doubly Stochastic Relaxation}},
  journal = {SIAM J. Appl. Algebra Geom.},
  year = {2018},
  url = {https://openreview.net/forum?id=n4oiM_CFgB},
}
Figure