# Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm and Application to 3D Multi-Shape Analysis

arXiv: https://arxiv.org/abs/2112.04165 · HTML: https://mlsanity.com/paper/2112.04165/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 63 references that are in the map.
- First posted on arXiv 8 Dec 2021.

## Builds on (most cited first, 12 of 12)

- [ShapeNet: An Information-Rich 3D Model Repository](https://mlsanity.com/paper/1512.03012/) (2015)
- [Pixel2Mesh: Generating 3D Mesh Models from Single RGB Images](https://mlsanity.com/paper/1804.01654/) (2018)
- [3D Menagerie: Modeling the 3D shape and pose of animals](https://mlsanity.com/paper/1611.07700/) (2016)
- [Learning multiview 3D point cloud registration](https://mlsanity.com/paper/2001.05119/) (2020)
- [MultiBodySync: Multi-Body Segmentation and Motion Estimation via 3D Scan Synchronization](https://mlsanity.com/paper/2101.06605/) (2021)
- [NeuRoRA: Neural Robust Rotation Averaging](https://mlsanity.com/paper/1912.04485/) (2019)
- [Learning Transformation Synchronization](https://mlsanity.com/paper/1901.09458/) (2019)
- [Higher-order Projected Power Iterations for Scalable Multi-Matching](https://mlsanity.com/paper/1811.10541/) (2018)
- [A Solution for Multi-Alignment by Transformation Synchronisation](https://mlsanity.com/paper/1410.8546/) (2014)
- [Synchronisation of Partial Multi-Matchings via Non-negative Factorisations](https://mlsanity.com/paper/1803.06320/) (2018)
- [Hamiltonian Dynamics for Real-World Shape Interpolation](https://mlsanity.com/paper/2004.05199/) (2020)
- [Distributed methods for synchronization of orthogonal matrices over graphs](https://mlsanity.com/paper/1701.07248/) (2017)

## Abstract (arXiv)

Finding shortest paths in a graph is relevant for numerous problems in computer vision and graphics, including image segmentation, shape matching, or the computation of geodesic distances on discrete surfaces. Traditionally, the concept of a shortest path is considered for graphs with scalar edge weights, which makes it possible to compute the length of a path by adding up the individual edge weights. Yet, graphs with scalar edge weights are severely limited in their expressivity, since oftentimes edges are used to encode significantly more complex interrelations. In this work we compensate for this modelling limitation and introduce the novel graph-theoretic concept of a shortest path in a graph with matrix-valued edges. To this end, we define a meaningful way for quantifying the path length for matrix-valued edges, and we propose a simple yet effective algorithm to compute the respective shortest path. While our formalism is universal and thus applicable to a wide range of settings in vision, graphics and beyond, we focus on demonstrating its merits in the context of 3D multi-shape analysis.