Timezone: »
Max-product Belief Propagation (BP) is a popular message-passing algorithm for computing a Maximum-A-Posteriori (MAP) assignment over a distribution represented by a Graphical Model (GM). It has been shown that BP can solve a number of combinatorial optimization problems including minimum weight matching, shortest path, network flow and vertex cover under the following common assumption: the respective Linear Programming (LP) relaxation is tight, i.e., no integrality gap is present. However, when LP shows an integrality gap, no model has been known which can be solved systematically via sequential applications of BP. In this paper, we develop the first such algorithm, coined Blossom-BP, for solving the minimum weight matching problem over arbitrary graphs. Each step of the sequential algorithm requires applying BP over a modified graph constructed by contractions and expansions of blossoms, i.e., odd sets of vertices. Our scheme guarantees termination in O(n^2) of BP runs, where n is the number of vertices in the original graph. In essence, the Blossom-BP offers a distributed version of the celebrated Edmonds' Blossom algorithm by jumping at once over many sub-steps with a single BP. Moreover, our result provides an interpretation of the Edmonds' algorithm as a sequence of LPs.
Author Information
Sungsoo Ahn (KAIST)
Sejun Park (KAIST)
Michael Chertkov (Los Alamos National Laboratory)
Jinwoo Shin (KAIST)
More from the Same Authors
-
2021 : SURF: Semi-supervised Reward Learning with Data Augmentation for Feedback-efficient Preference-based Reinforcement Learning »
Jongjin Park · Younggyo Seo · Jinwoo Shin · Honglak Lee · Pieter Abbeel · Kimin Lee -
2022 : STUNT: Few-shot Tabular Learning with Self-generated Tasks from Unlabeled Tables »
Jaehyun Nam · Jihoon Tack · Kyungmin Lee · Hankook Lee · Jinwoo Shin -
2022 : Dynamics-Augmented Decision Transformer for Offline Dynamics Generalization »
Changyeon Kim · Junsu Kim · Younggyo Seo · Kimin Lee · Honglak Lee · Jinwoo Shin -
2022 : Unsupervised Meta-learning via Few-shot Pseudo-supervised Contrastive Learning »
Huiwon Jang · Hankook Lee · Jinwoo Shin -
2022 Poster: NOTE: Robust Continual Test-time Adaptation Against Temporal Correlation »
Taesik Gong · Jongheon Jeong · Taewon Kim · Yewon Kim · Jinwoo Shin · Sung-Ju Lee -
2022 Poster: RényiCL: Contrastive Representation Learning with Skew Rényi Divergence »
Kyungmin Lee · Jinwoo Shin -
2022 Poster: Meta-Learning with Self-Improving Momentum Target »
Jihoon Tack · Jongjin Park · Hankook Lee · Jaeho Lee · Jinwoo Shin -
2022 Poster: Scalable Neural Video Representations with Learnable Positional Features »
Subin Kim · Sihyun Yu · Jaeho Lee · Jinwoo Shin -
2021 Poster: Improving Transferability of Representations via Augmentation-Aware Self-Supervision »
Hankook Lee · Kibok Lee · Kimin Lee · Honglak Lee · Jinwoo Shin -
2021 Poster: Landmark-Guided Subgoal Generation in Hierarchical Reinforcement Learning »
Junsu Kim · Younggyo Seo · Jinwoo Shin -
2021 Poster: RoMA: Robust Model Adaptation for Offline Model-based Optimization »
Sihyun Yu · Sungsoo Ahn · Le Song · Jinwoo Shin -
2021 Poster: Scaling Neural Tangent Kernels via Sketching and Random Features »
Amir Zandieh · Insu Han · Haim Avron · Neta Shoham · Chaewon Kim · Jinwoo Shin -
2021 Poster: Meta-Learning Sparse Implicit Neural Representations »
Jaeho Lee · Jihoon Tack · Namhoon Lee · Jinwoo Shin -
2021 Poster: Object-Aware Regularization for Addressing Causal Confusion in Imitation Learning »
Jongjin Park · Younggyo Seo · Chang Liu · Li Zhao · Tao Qin · Jinwoo Shin · Tie-Yan Liu -
2021 Poster: Object-aware Contrastive Learning for Debiased Scene Representation »
Sangwoo Mo · Hyunwoo Kang · Kihyuk Sohn · Chun-Liang Li · Jinwoo Shin -
2021 Poster: SmoothMix: Training Confidence-calibrated Smoothed Classifiers for Certified Robustness »
Jongheon Jeong · Sejun Park · Minkyu Kim · Heung-Chang Lee · Do-Guk Kim · Jinwoo Shin -
2020 Poster: Distribution Aligning Refinery of Pseudo-label for Imbalanced Semi-supervised Learning »
Jaehyung Kim · Youngbum Hur · Sejun Park · Eunho Yang · Sung Ju Hwang · Jinwoo Shin -
2020 Poster: Time-Reversal Symmetric ODE Network »
In Huh · Eunho Yang · Sung Ju Hwang · Jinwoo Shin -
2020 Poster: Learning from Failure: De-biasing Classifier from Biased Classifier »
Junhyun Nam · Hyuntak Cha · Sungsoo Ahn · Jaeho Lee · Jinwoo Shin -
2020 Poster: CSI: Novelty Detection via Contrastive Learning on Distributionally Shifted Instances »
Jihoon Tack · Sangwoo Mo · Jongheon Jeong · Jinwoo Shin -
2020 Poster: Guiding Deep Molecular Optimization with Genetic Exploration »
Sungsoo Ahn · Junsu Kim · Hankook Lee · Jinwoo Shin -
2020 Poster: Consistency Regularization for Certified Robustness of Smoothed Classifiers »
Jongheon Jeong · Jinwoo Shin -
2020 Poster: Trajectory-wise Multiple Choice Learning for Dynamics Generalization in Reinforcement Learning »
Younggyo Seo · Kimin Lee · Ignasi Clavera Gilaberte · Thanard Kurutach · Jinwoo Shin · Pieter Abbeel -
2020 Poster: Learning Bounds for Risk-sensitive Learning »
Jaeho Lee · Sejun Park · Jinwoo Shin -
2020 Poster: Few-shot Visual Reasoning with Meta-Analogical Contrastive Learning »
Youngsung Kim · Jinwoo Shin · Eunho Yang · Sung Ju Hwang -
2019 Poster: Mining GOLD Samples for Conditional GANs »
Sangwoo Mo · Chiheon Kim · Sungwoong Kim · Minsu Cho · Jinwoo Shin -
2018 Poster: A Simple Unified Framework for Detecting Out-of-Distribution Samples and Adversarial Attacks »
Kimin Lee · Kibok Lee · Honglak Lee · Jinwoo Shin -
2018 Poster: Stochastic Chebyshev Gradient Descent for Spectral Optimization »
Insu Han · Haim Avron · Jinwoo Shin -
2018 Spotlight: A Simple Unified Framework for Detecting Out-of-Distribution Samples and Adversarial Attacks »
Kimin Lee · Kibok Lee · Honglak Lee · Jinwoo Shin -
2018 Spotlight: Stochastic Chebyshev Gradient Descent for Spectral Optimization »
Insu Han · Haim Avron · Jinwoo Shin -
2018 Poster: Learning to Specialize with Knowledge Distillation for Visual Question Answering »
Jonghwan Mun · Kimin Lee · Jinwoo Shin · Bohyung Han -
2017 Poster: Gauging Variational Inference »
Sungsoo Ahn · Michael Chertkov · Jinwoo Shin -
2016 Poster: Synthesis of MCMC and Belief Propagation »
Sungsoo Ahn · Michael Chertkov · Jinwoo Shin -
2016 Oral: Synthesis of MCMC and Belief Propagation »
Sungsoo Ahn · Michael Chertkov · Jinwoo Shin -
2016 Poster: Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models »
Marc Vuffray · Sidhant Misra · Andrey Lokhov · Michael Chertkov -
2015 Poster: Minimum Weight Perfect Matching via Blossom Belief Propagation »
Sungsoo Ahn · Sejun Park · Michael Chertkov · Jinwoo Shin -
2013 Poster: A Graphical Transformation for Belief Propagation: Maximum Weight Matchings and Odd-Sized Cycles »
Jinwoo Shin · Andrew E Gelfand · Misha Chertkov