The Bayesian Cut

Area of Science:

• Graph theory
• Network analysis
• Statistical modeling

Background:

• Community structure detection is crucial for understanding complex networks.
• Existing graph cutting methods face challenges in accurately accounting for community structures.

Purpose of the Study:

• To present a novel generic Bayesian probabilistic model for graph cutting.
• To derive an analytical solution for marginalizing nuisance parameters under community structure constraints.

Main Methods:

• Developed a Bayesian probabilistic model for graph cutting.
• Derived an analytical solution for nuisance parameter marginalization.
• Approximated integrals involving multiple incomplete gamma functions for a scalable solution.

Main Results:

• The model provides a generic tool for Bayesian inference on Poisson weighted graphs.
• Achieved on-par or superior performance compared to spectral graph cutting and community detection methods on social networks and image segmentation tasks.
• Successfully learned the underlying parameter space.

Conclusions:

• The developed procedure offers a principled statistical framework for graph cutting.
• The Bayesian Cut source code facilitates adoption as an alternative to existing methods.