Optimal Transport with Symmetry Groups

We propose a novel algorithm that accelerates optimal transport by exploiting intrinsic symmetries induced by finite group actions. The core of our approach is to recover the orbit decomposition and the associated algebraic structure directly from the cost matrix—without requiring prior knowledge of the group—and to reduce the original transport problem to a substantially smaller problem on the orbit space. This reduction preserves optimality while achieving a significant drop in computational complexity. We develop efficient solvers for two central classes of optimal transport: linear OT and entropy-regularized OT. Experiments on synthetic data, real-world image datasets, and molecular graph data confirm the efficiency and robustness of the method. To our knowledge, this work is the first to systematically incorporate symmetry groups into optimal transport, providing both a theoretical framework and a practical pathway to computational acceleration.

Problem: Optimal transport is a method used in AI to compare two sets of data by finding the most efficient way to move one set to match the other. It is useful for tasks like image matching and biology analysis. However, it becomes very slow — often too slow to be practical — when the data has many points. Solution: Many real-world datasets have a hidden property: symmetry. For example, a square picture looks almost the same after a 90-degree rotation. Our algorithm automatically discovers such symmetry and uses it to shrink the original large transport problem into a much smaller one, drastically reducing computation time. Impact: Experiments show our method runs several times faster (up to tens of times) than traditional approaches, while producing exactly the same optimal result. This makes optimal transport practical for more applications, such as molecular shape matching and large-scale image analysis.