Efficient Hypergraph Clustering

Marius Leordeanu, Cristian Sminchisescu
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:676-684, 2012.

Abstract

Data clustering is an essential problem in data mining, machine learning and computer vision. In this paper we present a novel method for the hypergraph clustering problem, in which second or higher order affinities between sets of data points are considered. Our algorithm has important theoretical properties, such as convergence and satisfaction of first order necessary optimality conditions. It is based on an efficient iterative procedure, which by updating the cluster membership of all points in parallel, is able to achieve state of the art results in very few steps. We outperform current hypergraph clustering methods especially in terms of computational speed, but also in terms of accuracy. Moreover, we show that our method could be successfully applied both to higher-order assignment problems and to image segmentation.

Cite this Paper

BibTeX
@InProceedings{pmlr-v22-leordeanu12, title = {Efficient Hypergraph Clustering}, author = {Leordeanu, Marius and Sminchisescu, Cristian}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {676--684}, 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/leordeanu12/leordeanu12.pdf}, url = {https://proceedings.mlr.press/v22/leordeanu12.html}, abstract = {Data clustering is an essential problem in data mining, machine learning and computer vision. In this paper we present a novel method for the hypergraph clustering problem, in which second or higher order affinities between sets of data points are considered. Our algorithm has important theoretical properties, such as convergence and satisfaction of first order necessary optimality conditions. It is based on an efficient iterative procedure, which by updating the cluster membership of all points in parallel, is able to achieve state of the art results in very few steps. We outperform current hypergraph clustering methods especially in terms of computational speed, but also in terms of accuracy. Moreover, we show that our method could be successfully applied both to higher-order assignment problems and to image segmentation.} }
Endnote
%0 Conference Paper %T Efficient Hypergraph Clustering %A Marius Leordeanu %A Cristian Sminchisescu %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-leordeanu12 %I PMLR %P 676--684 %U https://proceedings.mlr.press/v22/leordeanu12.html %V 22 %X Data clustering is an essential problem in data mining, machine learning and computer vision. In this paper we present a novel method for the hypergraph clustering problem, in which second or higher order affinities between sets of data points are considered. Our algorithm has important theoretical properties, such as convergence and satisfaction of first order necessary optimality conditions. It is based on an efficient iterative procedure, which by updating the cluster membership of all points in parallel, is able to achieve state of the art results in very few steps. We outperform current hypergraph clustering methods especially in terms of computational speed, but also in terms of accuracy. Moreover, we show that our method could be successfully applied both to higher-order assignment problems and to image segmentation.
RIS
TY - CPAPER TI - Efficient Hypergraph Clustering AU - Marius Leordeanu AU - Cristian Sminchisescu 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-leordeanu12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 22 SP - 676 EP - 684 L1 - http://proceedings.mlr.press/v22/leordeanu12/leordeanu12.pdf UR - https://proceedings.mlr.press/v22/leordeanu12.html AB - Data clustering is an essential problem in data mining, machine learning and computer vision. In this paper we present a novel method for the hypergraph clustering problem, in which second or higher order affinities between sets of data points are considered. Our algorithm has important theoretical properties, such as convergence and satisfaction of first order necessary optimality conditions. It is based on an efficient iterative procedure, which by updating the cluster membership of all points in parallel, is able to achieve state of the art results in very few steps. We outperform current hypergraph clustering methods especially in terms of computational speed, but also in terms of accuracy. Moreover, we show that our method could be successfully applied both to higher-order assignment problems and to image segmentation. ER -
APA
Leordeanu, M. & Sminchisescu, C.. (2012). Efficient Hypergraph Clustering. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 22:676-684 Available from https://proceedings.mlr.press/v22/leordeanu12.html.

Related Material