Research map / Graph learning / Graph algorithms and clustering
Higher-Order Ratio Cycles for Fast and Globally Optimal Shape Matching
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Replaces minimum-cost cycles with minimum cost-time ratio cycles on (conjugate) product graphs for 2D-3D, 3D-3D and contour-to-graph shape matching, with GPU implementations.
Problem
Graph-based shape matching via cyclic paths in product graphs is biased toward short cycles under minimum-cost formulations and is slow on large conjugate product graphs, limiting 2D-3D matching quality and scalability.
Approach
Uses minimum ratio (cost-time) cycles, solved with Lawler's algorithm and a GPU Moore-Bellman-Ford variant, combined with the conjugate product graph to allow higher-order costs (local rigidity) while avoiding bias toward fewer edges.
Key results
- On 2D-3D matching, the method matches or beats Roetzer et al. in accuracy (FAUST2D3D mean geodesic error 0.06 vs 0.06; TOSCA segment error 0.06 vs 0.07) while being orders of magnitude faster.
- On 3D matching, it performs on par with SpiderMatch (FAUST error 0.029 vs 0.029) and is faster than SpiderMatch.
- Runtime on the wolf 2D-3D example drops from 580s (Roetzer et al.) to 13s; speed-ups of 10x to 100x reported.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use minimum ratio cycles instead of minimum cost cycles | 2D-3D shape matching · TOSCA2D3D | mean geodesic error: 0.07 -> 0.06 | Helped |
| Use minimum ratio cycles instead of minimum cost cycles | 2D-3D shape matching · FAUST2D3D w/o Flips | mean geodesic error: 0.06 -> 0.06 | No clear effect |
| Use minimum ratio cycles instead of minimum cost cycles | 3D shape matching · FAUST | mean geodesic error: 0.029 -> 0.029 | No clear effect |
| Use minimum ratio cycles instead of minimum cost cycles | 3D shape matching · DT4D | mean geodesic error: 0.027 -> 0.28 | Mixed |
| Use minimum ratio cycles instead of minimum cost cycles | 2D-3D shape matching · Wolf | runtime: 10s -> 13s | Hurt |
| Use minimum ratio cycles instead of minimum cost cycles | 2D-3D shape matching · Wolf | runtime: 580s -> 13s | Helped |
| Use minimum ratio cycles instead of minimum cost cycles | 2D-3D shape matching · TOSCA2D3D | mean geodesic error: 0.11 -> 0.06 | Helped |
Surprising findings
- Ratio-cycle matching without geometric consistency constraints performs comparably to SpiderMatch on 3D shape matching.
Limitations
- Occasional failures, e.g., dog leg matched incorrectly in TOSCA2D3D.
- Matching costs may need more careful curation to avoid undesirable results.
- Framework restricted to matching problems expressed as product graphs of two input graphs.
Experimental setup
Datasets: FAUST2D3D TOSCA2D3D FAUST DT4D Nashville road network
Benchmarks: FAUST2D3D TOSCA2D3D FAUST DT4D
Metrics: mean geodesic error % correct correspondences runtime
Baselines: Lähner et al. 2D-3D matching Roetzer et al. conjugate product graph matching SpiderMatch ULRSSM DiscrOpt SmoothShells
Builds on: Lawler's algorithm Roetzer et al. higher-order 2D-3D matching SpiderMatch Schoenemann and Cremers ratio cycle segmentation
Closest papers by meaning
- Multi-Shape Matching with Cycle Consistency Basis via Functional Maps (AAAI 2025 · similarity 0.88)
- SpiderMatch: 3D Shape Matching with Global Optimality and Geometric Consistency (CVPR 2024 · similarity 0.87)
- Partial-to-Partial Shape Matching with Geometric Consistency (CVPR 2024 · similarity 0.86)
- HOPE: Shape Matching Via Aligning Different K-hop Neighbourhoods (NeurIPS 2024 · similarity 0.84)
- SegGraph: Leveraging Graphs of SAM Segments for Few-Shot 3D Part Segmentation (NeurIPS 2025 · similarity 0.83)
- 3D Geometric Shape Assembly via Efficient Point Cloud Matching (ICML 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.