Atomic Cycles and Finding Holes in Manifolds

It's been a while! Turns out being in a PhD program keeps you pretty busy. I'm gonna try to get back into research blogging, but we'll see how long that lasts. This post is going back to manifold learning, my research focus during my undergrad at the University of Michigan.

Machine learning theoreticians and practitioners frequently make use of the manifold hypothesis, which asserts that high-dimensional data generally lie along lower-dimensional latent manifolds. Manifold learning makes heavy use of that assumption: it tries to find a coordinate chart of that manifold, towards producing an explicit low-dimensional representation of the data. One potential shortcoming of this strategy is that not all manifolds can be represented using a single coordinate chart, due to holes in the manifold. One can get around this by making cuts to the manifold or embedding pieces of the manifold as an atlas of charts, but to do so, one must identify the holes. Since the manifold is unknown, one has to do this with only the input data.

Given the standard manifold learning approach of connecting data points together to form a nearest neighbors graph, it makes sense to look at that graph to try and identify holes. Certainly, if there's a hole in the manifold, there should also be some sort of "hole" in the graph (assuming sufficient data). But such a notion must be made explicit, and it needs to be efficiently computable. (For example, topological data analysis provides formal methods for these purposes, but they generally don't scale to the problems we care about.)

Formally, a hole in a graph is a chordless cycle within the graph of length four or more. One can certainly compute all of the holes in a graph, but this notion doesn't necessarily correspond to the notion of a hole in the manifold. For example, in the following image (reproduced from Robust Manifold Learning with CycleCut, Gashler and Martinez), the large outer cycle is indeed chordless, but the structure in the middle suggests it's not a hole in the manifold.

To avoid this problem, Gashler and Martinez introduced the notion of an atomic cycle. An atomic cycle is a cycle with no n-chords, where n is some constant integer. (An n-chord is a sequence of n edges that connect two vertices in the cycle, where n is less than the length of the path connecting the vertices along the cycle.) For example, the outer cycle in the above graph is not an atomic cycle, since it has a 2-chord.

Gashler and Martinez presented an algorithm for finding large atomic cycles as part of their CycleCut paper. It involves two steps: an outer breadth-first search (BFS) to find candidate cycles, and an inner BFS to search for n-chords. I implemented their algorithm as part of my atlas learning paper, and put together a simple visualization of the algorithm, which you can run for yourself here. Given data with an obvious topological hole, you can see the neighborhood graph, the outer BFS (which has found a candidate cycle), the inner BFS (which searches for an n-chord), and the identification that no n-chord exists (yielding the atomic cycle).






Large atomic cycles are an excellent indicator of 1-dimensional holes, but as far as I know, identifying higher-dimensional topological holes in a graph is an open problem. If you happen to know of efficient algorithms for this, please send them my way!

Comments

Post a Comment

Popular posts from this blog

Reimplementing GCS (Shortest Paths in Graphs of Convex Sets)

Image
In a previous blog post , I discussed my experiences reimplementing Iterative Regional Inflation by Semidefinite programming (IRIS) , which is an algorithm for finding large convex regions of collision free space (C-Free). In this blog post, I'll be discussing my experiences reimplementing shortest paths in Graphs of Convex Sets (GCS) , an algorithm for motion planning when the configuration space is described as the union of convex sets. Disclaimer: the intent is not to build a codebase for future use, since the Drake toolbox has mature implementations of both IRIS and GCS . Disclaimer: if you have not read the previous blog post , you should do so before reading this one. In this blogpost, I'll give a brief overview of the GCS paper, and then discuss my experiences reimplementing it. Before reading this blog post, you should read my previous blog post about reimplementing IRIS, as it provides some background and context which I will not repeat in this post. I have also ma...
Read more

Differing Formulations of GCS for Motion Planning

Image
In case you haven't heard of it before, GCS stands for "Graph of Convex Sets", and it is a framework for certain mixed integer convex optimization problems, primarily used for robot motion planning. I previously wrote a blog post on my experience implementing a basic version of it, which you can find here . I'd recommend reading that blog post before looking at this one. If you've read that previous blog post, you may recall that I described two different ways of transcribing the motion planning problem into a graph of convex sets. I implemented one version, which seems more faithful to the original GCS paper . However, the other transcription, presented in the planning-specific followup paper , has several benefits over the previous approach. In this blog post, I'll briefly present both methodologies, and explain their costs and benefits. Formulation 1: Conjugate Graph Fig. 1 of Shortest Paths in Graphs of Convex Sets The classic picture of GCS is the one sho...
Read more

IRIS on a Torus: Growing Convex Sets on Manifolds

Image
My current research focus at MIT is motion planning along manifolds, which we're primarily exploring through the lens of the graph of convex sets framework, abbreviated as GCS. (Refer to a previous blog post for more details, or check out the papers of Marcucci et. al. here and here .) Convexity is a property that is examined through the lens of Euclidean geometry, but it is possible to consider it in the broader context of smooth manifolds. This is reliant on the idea of a geodesic: a shortest path on a manifold. Replacing Euclidean spaces with manifolds and lines with geodesics allows us to consider a graph of geodesically convex sets (GGCS). We've begun laying the groundwork for planning over manifolds with such a tool, and you can read about it in our paper Non-Euclidean Motion Planning with Graphs of Geodesically-Convex Sets , to appear at RSS 2023. (You can read the preprint today on arXiv!) While GGCS assumes the geodesically convex sets are given, computing such set...
Read more