Research map / Graph learning / Graph algorithms and clustering
Towards Optimizing Large-Scale Multi-Graph Matching in Bioimaging
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.
Proposes GREEDA, a greedy construction plus GM and swap local-search solver for incomplete, sparse multi-graph matching, and shows it scales to a 100-worm bioimaging instance where prior methods run out of memory.
Problem
Multi-graph matching for large-scale, incomplete, sparse bioimaging problems (100 C. elegans worms, ~45M keypoint correspondences), where existing MGM methods assume complete or dense settings and are too slow or infeasible.
Approach
Decomposes multi-graph matching into a chain or tree of pairwise graph-matching subproblems solved with a black-box GM solver (guaranteeing cycle consistency and allowed matches), plus parallel GM-based local search and a novel 2-clique swap local search formulated as a quadratic pseudo-boolean problem.
Key results
- On worms-29, GREEDA's construction finishes in about two minutes versus about half an hour for MP-T, with a lower objective.
- On worms-100, MP-T runs out of memory on a 250GB machine while GREEDA constructs a feasible solution in 10 minutes and converges in about an hour using 65GB RAM.
- On small dense or synthetic instances GREEDA is on par with leading methods (DS*, MP-T) while being roughly an order of magnitude faster.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use parallel GM local search instead of sequential GM local search (ablation) | GREEDA · worms-10 | convergence speed | Helped |
| use incremental construction instead of the other tested construction methods (ablation) | GREEDA · worms-10 | objective value | No clear effect |
| use incremental construction instead of the other tested construction methods (ablation) | GREEDA · worms-10 | runtime | Hurt |
| parallelize GM local search by accepting profitable proposals, rather than accepting only the best-improvement proposal (ablation) | GREEDA · worms-10 | convergence speed | Helped |
| change among sequential, parallel, and incremental construction methods (ablation) | GREEDA · worms-10 | final objective value | No clear effect |
| use GREEDA instead of MP-T | worms-29 · worms-29 | construction time: half an hour to just two minutes | Helped |
| use GREEDA instead of MP-T | worms-29 · worms-29 | objective value | Helped |
| use GREEDA instead of MP-T | worms-100 · worms-100 | feasible-solution runtime | Helped |
| use MP-T on worms-100 | MP-T · worms-100 | memory feasibility | Hurt |
Surprising findings
- Synchronization methods return solutions worse than the trivial all-unmatched solution on the hotel dataset due to blunders in forbidden matchings.
- Incremental construction takes notably more time without yielding a better solution than sequential construction.
Limitations
- SWAP-LS scales quadratically in the number of vertices and is the main bottleneck on large instances.
- Learned costs with neural networks are not addressed; the solver is only proposed for use inside such pipelines.
- Accuracy against ground truth is not evaluated; comparisons use objective values only.
Experimental setup
Datasets: worms-10 worms-29 worms-100 synthetic CMU hotel CMU house
Benchmarks: worms-29 worms-100 synthetic CMU hotel CMU house
Metrics: objective value (total cost) runtime
Baselines: MP-T DS* Projected power iteration Sparse Stiefel Synchronization Spectral synchronization with SBR
Builds on: QPBO-I MP-T DS* multi-dimensional assignment local search
Closest papers by meaning
- Multi-Shape Matching with Cycle Consistency Basis via Functional Maps (AAAI 2025 · similarity 0.85)
- HomoMatcher: Achieving Dense Feature Matching with Semi-Dense Efficiency by Homography Estimation (AAAI 2025 · similarity 0.84)
- Noisy One-point Homographies are Surprisingly Good (CVPR 2024 · similarity 0.84)
- FastJAM: a Fast Joint Alignment Model for Images (NeurIPS 2025 · similarity 0.84)
- BioCLIP: A Vision Foundation Model for the Tree of Life (CVPR 2024 · similarity 0.84)
- MATCHA: Towards Matching Anything (CVPR 2025 · 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.