Constrained fractional set programs and their application in local clustering and community detection

Thomas Bühler, Shyam Sundar Rangapuram, Simon Setzer, Matthias Hein
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(1):624-632, 2013.

Abstract

The (constrained) minimization of a ratio of set functions is a problem frequently occurring in clustering and community detection. As these optimization problems are typically NP-hard, one uses convex or spectral relaxations in practice. While these relaxations can be solved globally optimally, they are often too loose and thus lead to results far away from the optimum. In this paper we show that every constrained minimization problem of a ratio of non-negative set functions allows a tight relaxation into an unconstrained continuous optimization problem. This result leads to a flexible framework for solving constrained problems in network analysis. While a globally optimal solution for the resulting non-convex problem cannot be guaranteed, we outperform the loose convex or spectral relaxations by a large margin on constrained local clustering problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-buhler13, title = {Constrained fractional set programs and their application in local clustering and community detection}, author = {Bühler, Thomas and Rangapuram, Shyam Sundar and Setzer, Simon and Hein, Matthias}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {624--632}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {1}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/buhler13.pdf}, url = {https://proceedings.mlr.press/v28/buhler13.html}, abstract = {The (constrained) minimization of a ratio of set functions is a problem frequently occurring in clustering and community detection. As these optimization problems are typically NP-hard, one uses convex or spectral relaxations in practice. While these relaxations can be solved globally optimally, they are often too loose and thus lead to results far away from the optimum. In this paper we show that every constrained minimization problem of a ratio of non-negative set functions allows a tight relaxation into an unconstrained continuous optimization problem. This result leads to a flexible framework for solving constrained problems in network analysis. While a globally optimal solution for the resulting non-convex problem cannot be guaranteed, we outperform the loose convex or spectral relaxations by a large margin on constrained local clustering problems.} }
Endnote
%0 Conference Paper %T Constrained fractional set programs and their application in local clustering and community detection %A Thomas Bühler %A Shyam Sundar Rangapuram %A Simon Setzer %A Matthias Hein %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-buhler13 %I PMLR %P 624--632 %U https://proceedings.mlr.press/v28/buhler13.html %V 28 %N 1 %X The (constrained) minimization of a ratio of set functions is a problem frequently occurring in clustering and community detection. As these optimization problems are typically NP-hard, one uses convex or spectral relaxations in practice. While these relaxations can be solved globally optimally, they are often too loose and thus lead to results far away from the optimum. In this paper we show that every constrained minimization problem of a ratio of non-negative set functions allows a tight relaxation into an unconstrained continuous optimization problem. This result leads to a flexible framework for solving constrained problems in network analysis. While a globally optimal solution for the resulting non-convex problem cannot be guaranteed, we outperform the loose convex or spectral relaxations by a large margin on constrained local clustering problems.
RIS
TY - CPAPER TI - Constrained fractional set programs and their application in local clustering and community detection AU - Thomas Bühler AU - Shyam Sundar Rangapuram AU - Simon Setzer AU - Matthias Hein BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/02/13 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-buhler13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 1 SP - 624 EP - 632 L1 - http://proceedings.mlr.press/v28/buhler13.pdf UR - https://proceedings.mlr.press/v28/buhler13.html AB - The (constrained) minimization of a ratio of set functions is a problem frequently occurring in clustering and community detection. As these optimization problems are typically NP-hard, one uses convex or spectral relaxations in practice. While these relaxations can be solved globally optimally, they are often too loose and thus lead to results far away from the optimum. In this paper we show that every constrained minimization problem of a ratio of non-negative set functions allows a tight relaxation into an unconstrained continuous optimization problem. This result leads to a flexible framework for solving constrained problems in network analysis. While a globally optimal solution for the resulting non-convex problem cannot be guaranteed, we outperform the loose convex or spectral relaxations by a large margin on constrained local clustering problems. ER -
APA
Bühler, T., Rangapuram, S.S., Setzer, S. & Hein, M.. (2013). Constrained fractional set programs and their application in local clustering and community detection. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(1):624-632 Available from https://proceedings.mlr.press/v28/buhler13.html.

Related Material