Multicuts and perturb \& MAP for probabilistic graph clustering

DOI10.1007/S10851-016-0659-3zbMATH Open1392.68431arXiv1601.02088OpenAlexW2294754899MaRDI QIDQ334274FDOQ334274

Authors: Jörg Hendrik Kappes, Paul Swoboda, Bogdan Savchynskyy, Tamir Hazan, Christoph Schnörr 

Publication date: 1 November 2016

Published in: Journal of Mathematical Imaging and Vision (Search for Journal in Brave)

Abstract: We present a probabilistic graphical model formulation for the graph clustering problem. This enables to locally represent uncertainty of image partitions by approximate marginal distributions in a mathematically substantiated way, and to rectify local data term cues so as to close contours and to obtain valid partitions. We exploit recent progress on globally optimal MAP inference by integer programming and on perturbation-based approximations of the log-partition function, in order to sample clusterings and to estimate marginal distributions of node-pairs both more accurately and more efficiently than state-of-the-art methods. Our approach works for any graphically represented problem instance. This is demonstrated for image segmentation and social network cluster analysis. Our mathematical ansatz should be relevant also for other combinatorial problems.

Full work available at URL: https://arxiv.org/abs/1601.02088

Recommendations

• Probabilistic correlation clustering and image partitioning using perturbed multicuts
• Exact solutions for discrete graphical models. Multicuts and reduction techniques
• Perturb-and-MAP random fields
• Graph cuts with interacting edge weights: examples, approximations, and algorithms
• Multilayer joint segmentation using MRF and graph cuts

zbMATH Keywords

graphical modelscorrelation clusteringmulticutperturb and MAP

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Social networks; opinion dynamics (91D30) Computing methodologies for image processing (68U10)

Cites Work

• LibDAI: a free and open source C++ library for discrete approximate inference in graphical models
• Graphical models, exponential families, and variational inference
• An Efficient Heuristic Procedure for Partitioning Graphs
• Title not available (Why is that?)
• Clustering stability: an overview
• Approximation of functional depending on jumps by elliptic functional via t-convergence
• Title not available (Why is that?)
• Correlation clustering
• The ellipsoid method and its consequences in combinatorial optimization
• Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
• Nonparametric Bayesian image segmentation
• On clusterings: good, bad and spectral
• Factor graphs and the sum-product algorithm
• On Finding Graph Clusterings with Maximum Modularity
• Tree-based reparameterization framework for analysis of sum-product and related algorithms
• The partition problem
• Combinatorial theory.
• Continuous multiclass labeling approaches and algorithms
• A Convex Approach to Minimal Partitions
• Correlation clustering in general weighted graphs
• Title not available (Why is that?)
• Ambrosio-Tortorelli segmentation of stochastic images: model extensions, theoretical investigations and numerical methods
• Title not available (Why is that?)

Cited In (1)

• Latent Clustering on Graphs with Multiple Edge Types

Uses Software

• LibDAI
• BSDS
• OpenGM

This page was built for publication: Multicuts and perturb \& MAP for probabilistic graph clustering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q334274)