The Bayesian Cut

Research output: Contribution to journalJournal articleResearchpeer-review

2 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
VolumePP
Number of pages15
ISSN0162-8828
DOIs
Publication statusAccepted/In press - 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