A Bayesian Approach To Graph Partitioning
This work addresses graph partitioning for researchers in machine learning and network analysis, but it appears incremental as it builds on existing Bayesian and MCMC techniques.
The paper tackles the problem of graph partitioning by introducing a Bayesian inference algorithm that uses Gaussian Processes and MCMC to learn local graph conductance, resulting in a scalable and fast method for convergence to stationary distributions.
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.