---
_id: '916'
abstract:
- lang: eng
text: We study the quadratic assignment problem, in computer vision also known as
graph matching. Two leading solvers for this problem optimize the Lagrange decomposition
duals with sub-gradient and dual ascent (also known as message passing) updates.
We explore this direction further and propose several additional Lagrangean relaxations
of the graph matching problem along with corresponding algorithms, which are all
based on a common dual ascent framework. Our extensive empirical evaluation gives
several theoretical insights and suggests a new state-of-the-art anytime solver
for the considered problem. Our improvement over state-of-the-art is particularly
visible on a new dataset with large-scale sparse problem instances containing
more than 500 graph nodes each.
article_processing_charge: No
author:
- first_name: Paul
full_name: Swoboda, Paul
id: 446560C6-F248-11E8-B48F-1D18A9856A87
last_name: Swoboda
- first_name: Carsten
full_name: Rother, Carsten
last_name: Rother
- first_name: Carsten
full_name: Abu Alhaija, Carsten
last_name: Abu Alhaija
- first_name: Dagmar
full_name: Kainmueller, Dagmar
last_name: Kainmueller
- first_name: Bogdan
full_name: Savchynskyy, Bogdan
last_name: Savchynskyy
citation:
ama: 'Swoboda P, Rother C, Abu Alhaija C, Kainmueller D, Savchynskyy B. A study
of lagrangean decompositions and dual ascent solvers for graph matching. In: Vol
2017. IEEE; 2017:7062-7071. doi:10.1109/CVPR.2017.747'
apa: 'Swoboda, P., Rother, C., Abu Alhaija, C., Kainmueller, D., & Savchynskyy,
B. (2017). A study of lagrangean decompositions and dual ascent solvers for graph
matching (Vol. 2017, pp. 7062–7071). Presented at the CVPR: Computer Vision and
Pattern Recognition, Honolulu, HA, United States: IEEE. https://doi.org/10.1109/CVPR.2017.747'
chicago: Swoboda, Paul, Carsten Rother, Carsten Abu Alhaija, Dagmar Kainmueller,
and Bogdan Savchynskyy. “A Study of Lagrangean Decompositions and Dual Ascent
Solvers for Graph Matching,” 2017:7062–71. IEEE, 2017. https://doi.org/10.1109/CVPR.2017.747.
ieee: 'P. Swoboda, C. Rother, C. Abu Alhaija, D. Kainmueller, and B. Savchynskyy,
“A study of lagrangean decompositions and dual ascent solvers for graph matching,”
presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA,
United States, 2017, vol. 2017, pp. 7062–7071.'
ista: 'Swoboda P, Rother C, Abu Alhaija C, Kainmueller D, Savchynskyy B. 2017. A
study of lagrangean decompositions and dual ascent solvers for graph matching.
CVPR: Computer Vision and Pattern Recognition vol. 2017, 7062–7071.'
mla: Swoboda, Paul, et al. A Study of Lagrangean Decompositions and Dual Ascent
Solvers for Graph Matching. Vol. 2017, IEEE, 2017, pp. 7062–71, doi:10.1109/CVPR.2017.747.
short: P. Swoboda, C. Rother, C. Abu Alhaija, D. Kainmueller, B. Savchynskyy, in:,
IEEE, 2017, pp. 7062–7071.
conference:
end_date: 2017-07-26
location: Honolulu, HA, United States
name: 'CVPR: Computer Vision and Pattern Recognition'
start_date: 2017-07-21
date_created: 2018-12-11T11:49:11Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2023-09-26T15:41:40Z
day: '01'
ddc:
- '000'
department:
- _id: VlKo
doi: 10.1109/CVPR.2017.747
ec_funded: 1
external_id:
isi:
- '000418371407018'
file:
- access_level: open_access
checksum: e38a2740daad1ea178465843b5072906
content_type: application/pdf
creator: dernst
date_created: 2019-01-18T12:49:38Z
date_updated: 2020-07-14T12:48:15Z
file_id: '5848'
file_name: 2017_CVPR_Swoboda2.pdf
file_size: 944332
relation: main_file
file_date_updated: 2020-07-14T12:48:15Z
has_accepted_license: '1'
intvolume: ' 2017'
isi: 1
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 7062-7071
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_identifier:
isbn:
- 978-153860457-1
publication_status: published
publisher: IEEE
publist_id: '6525'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A study of lagrangean decompositions and dual ascent solvers for graph matching
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 2017
year: '2017'
...
---
_id: '915'
abstract:
- lang: eng
text: We propose a dual decomposition and linear program relaxation of the NP-hard
minimum cost multicut problem. Unlike other polyhedral relaxations of the multicut
polytope, it is amenable to efficient optimization by message passing. Like other
polyhedral relaxations, it can be tightened efficiently by cutting planes. We
define an algorithm that alternates between message passing and efficient separation
of cycle- and odd-wheel inequalities. This algorithm is more efficient than state-of-the-art
algorithms based on linear programming, including algorithms written in the framework
of leading commercial software, as we show in experiments with large instances
of the problem from applications in computer vision, biomedical image analysis
and data mining.
article_processing_charge: No
author:
- first_name: Paul
full_name: Swoboda, Paul
id: 446560C6-F248-11E8-B48F-1D18A9856A87
last_name: Swoboda
- first_name: Bjoern
full_name: Andres, Bjoern
last_name: Andres
citation:
ama: 'Swoboda P, Andres B. A message passing algorithm for the minimum cost multicut
problem. In: Vol 2017. IEEE; 2017:4990-4999. doi:10.1109/CVPR.2017.530'
apa: 'Swoboda, P., & Andres, B. (2017). A message passing algorithm for the
minimum cost multicut problem (Vol. 2017, pp. 4990–4999). Presented at the CVPR:
Computer Vision and Pattern Recognition, Honolulu, HA, United States: IEEE. https://doi.org/10.1109/CVPR.2017.530'
chicago: Swoboda, Paul, and Bjoern Andres. “A Message Passing Algorithm for the
Minimum Cost Multicut Problem,” 2017:4990–99. IEEE, 2017. https://doi.org/10.1109/CVPR.2017.530.
ieee: 'P. Swoboda and B. Andres, “A message passing algorithm for the minimum cost
multicut problem,” presented at the CVPR: Computer Vision and Pattern Recognition,
Honolulu, HA, United States, 2017, vol. 2017, pp. 4990–4999.'
ista: 'Swoboda P, Andres B. 2017. A message passing algorithm for the minimum cost
multicut problem. CVPR: Computer Vision and Pattern Recognition vol. 2017, 4990–4999.'
mla: Swoboda, Paul, and Bjoern Andres. A Message Passing Algorithm for the Minimum
Cost Multicut Problem. Vol. 2017, IEEE, 2017, pp. 4990–99, doi:10.1109/CVPR.2017.530.
short: P. Swoboda, B. Andres, in:, IEEE, 2017, pp. 4990–4999.
conference:
end_date: 2017-07-26
location: Honolulu, HA, United States
name: 'CVPR: Computer Vision and Pattern Recognition'
start_date: 2017-07-21
date_created: 2018-12-11T11:49:11Z
date_published: 2017-07-01T00:00:00Z
date_updated: 2023-09-26T15:43:27Z
day: '01'
ddc:
- '000'
department:
- _id: VlKo
doi: 10.1109/CVPR.2017.530
ec_funded: 1
external_id:
isi:
- '000418371405009'
file:
- access_level: open_access
checksum: 7e51dacefa693574581a32da3eff63dc
content_type: application/pdf
creator: dernst
date_created: 2019-01-18T12:52:46Z
date_updated: 2020-07-14T12:48:15Z
file_id: '5849'
file_name: Swoboda_A_Message_Passing_CVPR_2017_paper.pdf
file_size: 883264
relation: main_file
file_date_updated: 2020-07-14T12:48:15Z
has_accepted_license: '1'
intvolume: ' 2017'
isi: 1
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
page: 4990-4999
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_identifier:
isbn:
- 978-153860457-1
publication_status: published
publisher: IEEE
publist_id: '6526'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A message passing algorithm for the minimum cost multicut problem
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 2017
year: '2017'
...
---
_id: '917'
abstract:
- lang: eng
text: We propose a general dual ascent framework for Lagrangean decomposition
of combinatorial problems. Although methods of this type have shown their efficiency
for a number of problems, so far there was no general algorithm applicable to
multiple problem types. In this work, we propose such a general algorithm. It
depends on several parameters, which can be used to optimize its performance in
each particular setting. We demonstrate efficacy of our method on graph matching
and multicut problems, where it outperforms state-of-the-art solvers including
those based on subgradient optimization and off-the-shelf linear programming solvers.
article_processing_charge: No
author:
- first_name: Paul
full_name: Swoboda, Paul
id: 446560C6-F248-11E8-B48F-1D18A9856A87
last_name: Swoboda
- first_name: Jan
full_name: Kuske, Jan
last_name: Kuske
- first_name: Bogdan
full_name: Savchynskyy, Bogdan
last_name: Savchynskyy
citation:
ama: 'Swoboda P, Kuske J, Savchynskyy B. A dual ascent framework for Lagrangean
decomposition of combinatorial problems. In: Vol 2017. IEEE; 2017:4950-4960. doi:10.1109/CVPR.2017.526'
apa: 'Swoboda, P., Kuske, J., & Savchynskyy, B. (2017). A dual ascent framework
for Lagrangean decomposition of combinatorial problems (Vol. 2017, pp. 4950–4960).
Presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA,
United States: IEEE. https://doi.org/10.1109/CVPR.2017.526'
chicago: Swoboda, Paul, Jan Kuske, and Bogdan Savchynskyy. “A Dual Ascent Framework
for Lagrangean Decomposition of Combinatorial Problems,” 2017:4950–60. IEEE, 2017.
https://doi.org/10.1109/CVPR.2017.526.
ieee: 'P. Swoboda, J. Kuske, and B. Savchynskyy, “A dual ascent framework for Lagrangean
decomposition of combinatorial problems,” presented at the CVPR: Computer Vision
and Pattern Recognition, Honolulu, HA, United States, 2017, vol. 2017, pp. 4950–4960.'
ista: 'Swoboda P, Kuske J, Savchynskyy B. 2017. A dual ascent framework for Lagrangean
decomposition of combinatorial problems. CVPR: Computer Vision and Pattern Recognition
vol. 2017, 4950–4960.'
mla: Swoboda, Paul, et al. A Dual Ascent Framework for Lagrangean Decomposition
of Combinatorial Problems. Vol. 2017, IEEE, 2017, pp. 4950–60, doi:10.1109/CVPR.2017.526.
short: P. Swoboda, J. Kuske, B. Savchynskyy, in:, IEEE, 2017, pp. 4950–4960.
conference:
end_date: 2017-07-26
location: Honolulu, HA, United States
name: 'CVPR: Computer Vision and Pattern Recognition'
start_date: 2017-07-21
date_created: 2018-12-11T11:49:11Z
date_published: 2017-07-01T00:00:00Z
date_updated: 2023-09-26T15:41:11Z
day: '01'
ddc:
- '000'
department:
- _id: VlKo
doi: 10.1109/CVPR.2017.526
ec_funded: 1
external_id:
isi:
- '000418371405005'
file:
- access_level: open_access
checksum: 72fd291046bd8e5717961bd68f6b6f03
content_type: application/pdf
creator: dernst
date_created: 2019-01-18T12:45:55Z
date_updated: 2020-07-14T12:48:15Z
file_id: '5847'
file_name: 2017_CVPR_Swoboda.pdf
file_size: 898652
relation: main_file
file_date_updated: 2020-07-14T12:48:15Z
has_accepted_license: '1'
intvolume: ' 2017'
isi: 1
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
page: 4950-4960
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_identifier:
isbn:
- 978-153860457-1
publication_status: published
publisher: IEEE
publist_id: '6524'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A dual ascent framework for Lagrangean decomposition of combinatorial problems
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 2017
year: '2017'
...
---
_id: '274'
abstract:
- lang: eng
text: We consider the problem of estimating the partition function Z(β)=∑xexp(−β(H(x))
of a Gibbs distribution with a Hamilton H(⋅), or more precisely the logarithm
of the ratio q=lnZ(0)/Z(β). It has been recently shown how to approximate q with
high probability assuming the existence of an oracle that produces samples from
the Gibbs distribution for a given parameter value in [0,β]. The current best
known approach due to Huber [9] uses O(qlnn⋅[lnq+lnlnn+ε−2]) oracle calls on average
where ε is the desired accuracy of approximation and H(⋅) is assumed to lie in
{0}∪[1,n]. We improve the complexity to O(qlnn⋅ε−2) oracle calls. We also show
that the same complexity can be achieved if exact oracles are replaced with approximate
sampling oracles that are within O(ε2qlnn) variation distance from exact oracles.
Finally, we prove a lower bound of Ω(q⋅ε−2) oracle calls under a natural model
of computation.
article_processing_charge: No
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: 'Kolmogorov V. A faster approximation algorithm for the Gibbs partition function.
In: Proceedings of the 31st Conference On Learning Theory. Vol 75. ML Research
Press; 2017:228-249.'
apa: Kolmogorov, V. (2017). A faster approximation algorithm for the Gibbs partition
function. In Proceedings of the 31st Conference On Learning Theory (Vol.
75, pp. 228–249). ML Research Press.
chicago: Kolmogorov, Vladimir. “A Faster Approximation Algorithm for the Gibbs Partition
Function.” In Proceedings of the 31st Conference On Learning Theory, 75:228–49.
ML Research Press, 2017.
ieee: V. Kolmogorov, “A faster approximation algorithm for the Gibbs partition function,”
in Proceedings of the 31st Conference On Learning Theory, 2017, vol. 75,
pp. 228–249.
ista: 'Kolmogorov V. 2017. A faster approximation algorithm for the Gibbs partition
function. Proceedings of the 31st Conference On Learning Theory. COLT: Annual
Conference on Learning Theory vol. 75, 228–249.'
mla: Kolmogorov, Vladimir. “A Faster Approximation Algorithm for the Gibbs Partition
Function.” Proceedings of the 31st Conference On Learning Theory, vol.
75, ML Research Press, 2017, pp. 228–49.
short: V. Kolmogorov, in:, Proceedings of the 31st Conference On Learning Theory,
ML Research Press, 2017, pp. 228–249.
conference:
end_date: 2018-07-09
name: 'COLT: Annual Conference on Learning Theory '
start_date: 2018-07-06
date_created: 2018-12-11T11:45:33Z
date_published: 2017-12-27T00:00:00Z
date_updated: 2023-10-17T12:32:13Z
day: '27'
ddc:
- '510'
department:
- _id: VlKo
ec_funded: 1
external_id:
arxiv:
- '1608.04223'
file:
- access_level: open_access
checksum: 89db06a0e8083524449cb59b56bf4e5b
content_type: application/pdf
creator: dernst
date_created: 2020-05-12T09:23:27Z
date_updated: 2020-07-14T12:45:45Z
file_id: '7820'
file_name: 2018_PMLR_Kolmogorov.pdf
file_size: 408974
relation: main_file
file_date_updated: 2020-07-14T12:45:45Z
has_accepted_license: '1'
intvolume: ' 75'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 228-249
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: Proceedings of the 31st Conference On Learning Theory
publication_status: published
publisher: ML Research Press
publist_id: '7628'
quality_controlled: '1'
status: public
title: A faster approximation algorithm for the Gibbs partition function
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 75
year: '2017'
...
---
_id: '5561'
abstract:
- lang: eng
text: 'Graph matching problems as described in "Active Graph Matching for Automatic
Joint Segmentation and Annotation of C. Elegans." by Kainmueller, Dagmar and Jug,
Florian and Rother, Carsten and Myers, Gene, MICCAI 2014. Problems are in OpenGM2
hdf5 format (see http://hciweb2.iwr.uni-heidelberg.de/opengm/) and a custom text
format used by the feature matching solver described in "Feature Correspondence
via Graph Matching: Models and Global Optimization." by Lorenzo Torresani, Vladimir
Kolmogorov and Carsten Rother, ECCV 2008, code at http://pub.ist.ac.at/~vnk/software/GraphMatching-v1.02.src.zip. '
acknowledgement: We thank Vladimir Kolmogorov and Stephan Saalfeld forinspiring discussions.
article_processing_charge: No
author:
- first_name: Dagmar
full_name: Kainmueller, Dagmar
last_name: Kainmueller
- first_name: Florian
full_name: Jug, Florian
last_name: Jug
- first_name: Carsten
full_name: Rother, Carsten
last_name: Rother
- first_name: Gene
full_name: Meyers, Gene
last_name: Meyers
citation:
ama: Kainmueller D, Jug F, Rother C, Meyers G. Graph matching problems for annotating
C. Elegans. 2017. doi:10.15479/AT:ISTA:57
apa: Kainmueller, D., Jug, F., Rother, C., & Meyers, G. (2017). Graph matching
problems for annotating C. Elegans. Institute of Science and Technology Austria.
https://doi.org/10.15479/AT:ISTA:57
chicago: Kainmueller, Dagmar, Florian Jug, Carsten Rother, and Gene Meyers. “Graph
Matching Problems for Annotating C. Elegans.” Institute of Science and Technology
Austria, 2017. https://doi.org/10.15479/AT:ISTA:57.
ieee: D. Kainmueller, F. Jug, C. Rother, and G. Meyers, “Graph matching problems
for annotating C. Elegans.” Institute of Science and Technology Austria, 2017.
ista: Kainmueller D, Jug F, Rother C, Meyers G. 2017. Graph matching problems for
annotating C. Elegans, Institute of Science and Technology Austria, 10.15479/AT:ISTA:57.
mla: Kainmueller, Dagmar, et al. Graph Matching Problems for Annotating C. Elegans.
Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:57.
short: D. Kainmueller, F. Jug, C. Rother, G. Meyers, (2017).
datarep_id: '57'
date_created: 2018-12-12T12:31:32Z
date_published: 2017-02-13T00:00:00Z
date_updated: 2024-02-21T13:46:31Z
day: '13'
ddc:
- '000'
department:
- _id: VlKo
doi: 10.15479/AT:ISTA:57
file:
- access_level: open_access
checksum: 3dc3e1306a66028a34181ebef2923139
content_type: application/zip
creator: system
date_created: 2018-12-12T13:02:54Z
date_updated: 2020-07-14T12:47:03Z
file_id: '5614'
file_name: IST-2017-57-v1+1_wormMatchingProblems.zip
file_size: 327042819
relation: main_file
file_date_updated: 2020-07-14T12:47:03Z
has_accepted_license: '1'
keyword:
- graph matching
- feature matching
- QAP
- MAP-inference
license: https://creativecommons.org/publicdomain/zero/1.0/
month: '02'
oa: 1
oa_version: Published Version
publisher: Institute of Science and Technology Austria
status: public
title: Graph matching problems for annotating C. Elegans
tmp:
image: /images/cc_0.png
legal_code_url: https://creativecommons.org/publicdomain/zero/1.0/legalcode
name: Creative Commons Public Domain Dedication (CC0 1.0)
short: CC0 (1.0)
type: research_data
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...