MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models

  • We developed a new state-of-the-art Block Coordinate Ascent (BCA) algorithm for dense graphical models based on the Handshake [3] operation.
  • The method is state-of-the-art on all dataset instances with graph density >10% of all possible edges. We tested on the following datasets:
    • Worms [5]
    • Pose-6D [6]
    • Stereo [4]
    • Protein Folding [4]
  • We developed parallel implementation for both CPU and GPU based on processing edges belonging to maximal matchings of the graph.


Non-incident edges of a graph can be processed in parallel. So, maximum matchings are used to compute an edge cover. In the figure, edges (b,d), (a,c) and (e,f) can be processed in parallel.

Extended Version

Conference Poster


[1] Kolmogorov, V., “Convergent tree-reweighted message passing for energy minimization”, PAMI, 2006.

[2] Globerson et al., “Fixing Max-Product: Convergent Message Passing Algorithms for MAP LP-Relaxations”, NIPS, 2008.

[3] Shekhovtsov, A., et al., “Solving Dense Image Matching in Real-Time Using Discrete-Continuous Optimization”, CVWW 2016.

[4] Kappes, J. et al. , “A comparative study of modern inference techniques for discrete energy minimization problems”, IJCV, 2015.

[5] Kainmueller, D., et al., “Graph matching problems for annotating C. Elegans”, IST Austria, Data Repository, 2017.

[6] Michel, F. et al., “Global hypothesis generation for {6D} object pose estimation”, CVPR, 2017.