The Bayesian Cut

Petr Taborsky, Laurent Vermue, Maciej Korzepa, Morten Morup

Research output: Contribution to journalJournal articleResearchpeer-review

227 Downloads (Pure)

Abstract

An important task in the analysis of graphs is separating nodes into densely connected groups with little interaction between each other. Prominent methods here include flow based graph cutting procedures as well as statistical network modeling approaches. However, adequately accounting for the holistic community structure in complex networks remains a major challenge. We present a novel generic Bayesian probabilistic model for graph cutting in which we derive an analytical solution to the marginalization of nuisance parameters under constraints enforcing community structure. As a part of the solution a large scale approximation for integrals involving multiple incomplete gamma functions is derived. Our multiple cluster solution presents a generic tool for Bayesian inference on Poisson weighted graphs across different domains. Applied on three real world social networks as well as three image segmentation problems our approach shows on par or better performance to existing spectral graph cutting and community detection methods, while learning the underlying parameter space. The developed procedure provides a principled statistical framework for graph cutting and the Bayesian Cut source code provided enables easy adoption of the procedure as an alternative to existing graph cutting methods.
Original languageEnglish
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Volume43
Issue number11
Pages (from-to)4111 - 4124
ISSN0162-8828
DOIs
Publication statusPublished - 2021

Keywords

  • Normalized Cut
  • Ratio cut
  • Graph cut
  • Modularity
  • Degree-corrected stochastic block modeling
  • Bayesian inference
  • Incomplete gamma function
  • Image segmentation

Fingerprint

Dive into the research topics of 'The Bayesian Cut'. Together they form a unique fingerprint.

Cite this