# A Bayesian Approach To Graph Partitioning

arXiv: https://arxiv.org/abs/2204.12927 · HTML: https://mlsanity.com/paper/2204.12927/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 33 references that are in the map.
- First posted on arXiv 24 Apr 2022.

## Builds on (most cited first, 11 of 11)

- [MCMC for Variationally Sparse Gaussian Processes](https://mlsanity.com/paper/1506.04000/) (2015)
- [Optimality of Spectral Clustering in the Gaussian Mixture Model](https://mlsanity.com/paper/1911.00538/) (2019)
- [Approximate Inference for Fully Bayesian Gaussian Process Regression](https://mlsanity.com/paper/1912.13440/) (2019)
- [Recent Advances in Graph Partitioning](https://mlsanity.com/paper/1311.3144/) (2013)
- [Accelerating Asymptotically Exact MCMC for Computationally Intensive Models via Local Approximations](https://mlsanity.com/paper/1402.1694/) (2014)
- [Flow-Based Algorithms for Local Graph Clustering](https://mlsanity.com/paper/1307.2855/) (2013)
- [Marginalizing Gaussian Process Hyperparameters using Sequential Monte Carlo](https://mlsanity.com/paper/1502.01908/) (2015)
- [Warped Mixtures for Nonparametric Cluster Shapes](https://mlsanity.com/paper/1408.2061/) (2014)
- [Approximate Sampling using an Accelerated Metropolis-Hastings based on Bayesian Optimization and Gaussian Processes](https://mlsanity.com/paper/1910.09347/) (2019)
- [On MCMC for variationally sparse Gaussian processes: A pseudo-marginal approach](https://mlsanity.com/paper/2103.03321/) (2021)
- [Finding Many Sparse Cuts Using Entropy Maximization](https://mlsanity.com/paper/2203.07869/) (2022)

## Abstract (arXiv)

A new algorithm based on bayesian inference for learning local graph conductance based on Gaussian Process(GP) is given that uses advanced MCMC convergence ideas to create a scalable and fast algorithm for convergence to stationary distribution which is provided to learn the bahavior of conductance when traversing the indirected weighted graph. First metric embedding is used to represent the vertices of the graph. Then, uniform induced conductance is calculated for training points. Finally, in the learning step, a gaussian process is used to approximate the uniform induced conductance. MCMC is used to measure uncertainty of estimated hyper-parameters.