Diffusion geometry for detecting topology-robust symmetries

Alexander Bronstein et al have an interesting preprint about exploring the intrinsic symmetries of non-rigid shapes.

For non-rigid shapes, you can’t just define symmetry in terms of rigid motions; you need some way to identify intrinsic symmetries that remain constant up to distortions. This has sometimes been handled with geodesic distances, considering the eigenfunctions of the Laplace-Beltrami operator on the surface to transform intrinsic symmetries to (approximate) Euclidean symmetries in a feature space created by the eigenfunctions. The problem is that this method is not robust to topological noise or noise that changes the connectivity of the surface. (Such noise is common, i.e. in protein modeling — I’ve often seen biologists bemoan the fact that a peninsula often gets confused for an island and vice versa.)

The authors suggest as a solution the diffusion distance, recently applied to data analysis by Lafon and Coifman, which gives the distance between two points in the basis of the coefficients of the heat kernel. That is, we look at

where are the eigenvalues and the eigenfunctions of the Laplacian.

Then we compare distances by

The strength of the diffusion distance is that, while the geodesic distance only looks at the shortest path, the diffusion distance looks at all paths between two points, and concludes that they’re close together if there are many short paths between them. It can be thought of as the limit of diffusions on discrete graphs.

Using this framework we can talk about approximate symmetries. These are distortion functions on the surface that leave the surface nearly invariant — as measured by the diffusion metric. We can also define the maximum asymmetry at a point, given one of these approximate symmetries:

Local minima of the distortion function are good candidates for approximate symmetry.

The authors use this framework to compare different surfaces using the Gromov-Hausdorff metric. They do some experimental comparisons and find that the diffusion distance is much better at identifying approximate symmetries than competing metrics.

Without being an expert, I have the sense that much more can be done in this field to deal with topology. The paper doesn’t actually address topology itself. But the issue seems to be that in noisy images, pieces break off — peninsulas become islands and so on. I’ve seen a sort of hierarchical method of dealing with this: define the coarseness at which the homology changes, and make a branch there, and then check further (finer) degrees of coarseness, and make a tree that way. Then you have some metric for the similarity of trees that you can use to compare images.

The thing is, what these trees essentially tell you is something about the intrinsic geometry of a surface — after all, it’s the protrusions that are most likely to become islands at coarser levels of visualization. I’d guess there’s actually a theorem to be found (or already exists) relating these topological tree structures to geometric notions like geodesic distance or diffusion distance — something along the lines of “the closer the trees, the smaller the Gromov-Hausdorff distance between the surfaces.”

Anybody know anything about this?