We develop a geometric framework, based on the classical theory of fibre bundles, to characterize the cohomological nature of a large class of \emph{synchronization-type problems} in the context of graph inference and combinatorial optimization. We identify each synchronization problem in topological group $G$ on connected graph $\Gamma$ with a flat principal $G$-bundle over $\Gamma$, thus establishing a classification result for synchronization problems using the representation variety of the fundamental group of $\Gamma$ into $G$. We then develop a twisted Hodge theory on flat vector bundles associated with these flat principal $G$-bundles, and provide a geometric realization of the \emph{graph connection Laplacian} as the lowest-degree Hodge Laplacian in the twisted de Rham-Hodge cochain complex. Motivated by these geometric intuitions, we propose to study the problem of \emph{learning group actions} --- partitioning a collection of objects based on the local synchronizability of pairwise correspondence relations --- and provide a heuristic synchronization-based algorithm for solving this type of problems. We demonstrate the efficacy of this algorithm on simulated and real datasets.

This presentation is part of Minisymposium “MS29 - Geometry and Learning in 3D Shape Analysis”
organized by: Ronald Lui (Chinese University of Hong Kong) , Rongjie Lai (Rensselaer Polytechnic Institute) .

Authors:

Tingran Gao (The University of Chicago)

Keywords: