Globally Optimizing Graph Partitioning Problems Using Message Passing

Elad Mezuman, Yair Weiss
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:770-778, 2012.

Abstract

Graph partitioning algorithms play a central role in data analysis and machine learning. Most useful graph partitioning criteria correspond to optimizing a ratio between the cut and the size of the partitions, this ratio leads to an NP-hard problem that is only solved approximately. This makes it difficult to know whether failures of the algorithm are due to failures of the optimization or to the criterion being optimized. In this paper we present a framework that seeks and finds the optimal solution of several NP-hard graph partitioning problems. We use a classical approach to ratio problems where we repeatedly ask whether the optimal solution is greater than or less than some constant - lambda. Our main insight is the equivalence between this “lambda question” and performing inference in a graphical model with many local potentials and one high-order potential. We show that this specific form of the high-order potential is amenable to message-passing algorithms and how to obtain a bound on the optimal solution from the messages. Our experiments show that in many cases our approach yields the global optimum and improves the popular spectral solution.

Cite this Paper

BibTeX
@InProceedings{pmlr-v22-mezuman12, title = {Globally Optimizing Graph Partitioning Problems Using Message Passing}, author = {Mezuman, Elad and Weiss, Yair}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {770--778}, year = {2012}, editor = {Lawrence, Neil D. and Girolami, Mark}, volume = {22}, series = {Proceedings of Machine Learning Research}, address = {La Palma, Canary Islands}, month = {21--23 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v22/mezuman12/mezuman12.pdf}, url = {https://proceedings.mlr.press/v22/mezuman12.html}, abstract = {Graph partitioning algorithms play a central role in data analysis and machine learning. Most useful graph partitioning criteria correspond to optimizing a ratio between the cut and the size of the partitions, this ratio leads to an NP-hard problem that is only solved approximately. This makes it difficult to know whether failures of the algorithm are due to failures of the optimization or to the criterion being optimized. In this paper we present a framework that seeks and finds the optimal solution of several NP-hard graph partitioning problems. We use a classical approach to ratio problems where we repeatedly ask whether the optimal solution is greater than or less than some constant - lambda. Our main insight is the equivalence between this “lambda question” and performing inference in a graphical model with many local potentials and one high-order potential. We show that this specific form of the high-order potential is amenable to message-passing algorithms and how to obtain a bound on the optimal solution from the messages. Our experiments show that in many cases our approach yields the global optimum and improves the popular spectral solution.} }
Endnote
%0 Conference Paper %T Globally Optimizing Graph Partitioning Problems Using Message Passing %A Elad Mezuman %A Yair Weiss %B Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2012 %E Neil D. Lawrence %E Mark Girolami %F pmlr-v22-mezuman12 %I PMLR %P 770--778 %U https://proceedings.mlr.press/v22/mezuman12.html %V 22 %X Graph partitioning algorithms play a central role in data analysis and machine learning. Most useful graph partitioning criteria correspond to optimizing a ratio between the cut and the size of the partitions, this ratio leads to an NP-hard problem that is only solved approximately. This makes it difficult to know whether failures of the algorithm are due to failures of the optimization or to the criterion being optimized. In this paper we present a framework that seeks and finds the optimal solution of several NP-hard graph partitioning problems. We use a classical approach to ratio problems where we repeatedly ask whether the optimal solution is greater than or less than some constant - lambda. Our main insight is the equivalence between this “lambda question” and performing inference in a graphical model with many local potentials and one high-order potential. We show that this specific form of the high-order potential is amenable to message-passing algorithms and how to obtain a bound on the optimal solution from the messages. Our experiments show that in many cases our approach yields the global optimum and improves the popular spectral solution.
RIS
TY - CPAPER TI - Globally Optimizing Graph Partitioning Problems Using Message Passing AU - Elad Mezuman AU - Yair Weiss BT - Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-mezuman12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 22 SP - 770 EP - 778 L1 - http://proceedings.mlr.press/v22/mezuman12/mezuman12.pdf UR - https://proceedings.mlr.press/v22/mezuman12.html AB - Graph partitioning algorithms play a central role in data analysis and machine learning. Most useful graph partitioning criteria correspond to optimizing a ratio between the cut and the size of the partitions, this ratio leads to an NP-hard problem that is only solved approximately. This makes it difficult to know whether failures of the algorithm are due to failures of the optimization or to the criterion being optimized. In this paper we present a framework that seeks and finds the optimal solution of several NP-hard graph partitioning problems. We use a classical approach to ratio problems where we repeatedly ask whether the optimal solution is greater than or less than some constant - lambda. Our main insight is the equivalence between this “lambda question” and performing inference in a graphical model with many local potentials and one high-order potential. We show that this specific form of the high-order potential is amenable to message-passing algorithms and how to obtain a bound on the optimal solution from the messages. Our experiments show that in many cases our approach yields the global optimum and improves the popular spectral solution. ER -
APA
Mezuman, E. & Weiss, Y.. (2012). Globally Optimizing Graph Partitioning Problems Using Message Passing. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 22:770-778 Available from https://proceedings.mlr.press/v22/mezuman12.html.

Related Material