Multicuts and perturb \& MAP for probabilistic graph clustering

DOI10.1007/S10851-016-0659-3MaRDI QIDQ334274zbMATHOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(2)

• Probabilistic correlation clustering and image partitioning using perturbed multicuts
• Latent Clustering on Graphs with Multiple Edge Types

Describes a project that uses

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)