Research map / Graph learning / Graph algorithms and clustering
MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models
Siddharth Tourani, Alexander Shekhovtsov, Carsten Rother, Bogdan Savchynskyy
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add the handshake push of pairwise cost into unaries to the MPLP update (MPLP++) (ablation) | MPLP · Dense datasets (pose, protein, worms) | speedup over MPLP: 5 to 150 times | Improved |
| replace MPLP by the MPLP++ update, sequential (ablation) | MPLP · Dense datasets | speed over MPLP: 5 to 150 times | Improved |
| replace TRW-S by MPLP++, sequential setting | TRW-S · Dense datasets | speed: 2 to 10 times | Improved |
| run MPLP++ in parallel against TRW-S | TRW-S · Dense datasets | speed: 7 to 40 times | Improved |
| replace TRWS by MPLP++ on sparse grid graphs | TRWS · Stereo (sparse grid graphs) | dual convergence | Hurt |
| remove edges from pose graph down to 10% of possible edges (ablation) | MPLP++ · pose dataset | dual vs time: down to 10% | No clear effect |
| remove edges from pose graph to 5% or fewer (ablation) | MPLP++ · pose dataset | dual vs time: 5% and less | Hurt |
| use own multi-threaded MPLP implementation instead of the original | MPLP · Dense datasets | speed: factor of 4 | Improved |
| replace MPLP update by the uniform update (ablation) | MPLP · Toy example (Fig. 2) | dual optimum reached | Hurt |
Later papers that compared with this method
3 later accepted papers report MPLP+ as a baseline in their results tables; 2 of them report a better number on most of the results they share with it.
- Plain Transformers are Surprisingly Powerful Link Predictors (ICML 2026 · better on 2 of 4 shared results)
- GraphGPT: Generative Pre-trained Graph Eulerian Transformer (ICML 2025 · better on 1 of 1 shared result)
- Factor Graph Neural Networks (NeurIPS 2020 · better on 3 of 4 shared results)
Matched by method name in results tables read by AI. Authors' own tables tend to favour the newer method, and a comparison can be missed when a method is renamed.
Closest papers by meaning
- Asynchronous Parallel Coordinate Minimization for MAP Inference (NeurIPS 2017 · similarity 0.85)
- FastDOG: Fast Discrete Optimization on GPU (CVPR 2022 · similarity 0.84)
- Efficient Low Rank Convex Bounds for Pairwise Discrete Graphical Models (ICML 2022 · similarity 0.84)
- GSPN-2: Efficient Parallel Sequence Modeling (NeurIPS 2025 · similarity 0.83)
- MDP: Multidimensional Vision Model Pruning with Latency Constraint (CVPR 2025 · similarity 0.82)
- B$^3$-PWL: GPU-Batched Branch-and-Bound for Piecewise-Linear Optimization with SOS2 Constraints (NeurIPS 2026 · similarity 0.82)
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.
