Monochromatic Bi-Clustering

Sharon Wulff, Ruth Urner, Shai Ben-David
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(2):145-153, 2013.

Abstract

We propose a natural cost function for the bi-clustering task, the monochromatic cost. This cost function is suitable for detecting meaningful homogeneous bi-clusters based on categorical valued input matrices. Such tasks arise in many applications, such as the analysis of social networks and in systems-biology where researchers try to infer functional grouping of biological agents based on their pairwise interactions. We analyze the computational complexity of the resulting optimization problem. We present a polynomial time approximation algorithm for this bi-clustering task and complement this result by showing that finding (exact) optimal solutions is NP-hard. As far as we know, these are the first positive approximation guarantees and formal NP-hardness results for any bi-clustering optimization problem. In addition, we show that our optimization problem can be efficiently solved by deterministic annealing, yielding a promising heuristic for large problem instances.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-wulff13, title = {Monochromatic Bi-Clustering}, author = {Wulff, Sharon and Urner, Ruth and Ben-David, Shai}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {145--153}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/wulff13.pdf}, url = {https://proceedings.mlr.press/v28/wulff13.html}, abstract = {We propose a natural cost function for the bi-clustering task, the monochromatic cost. This cost function is suitable for detecting meaningful homogeneous bi-clusters based on categorical valued input matrices. Such tasks arise in many applications, such as the analysis of social networks and in systems-biology where researchers try to infer functional grouping of biological agents based on their pairwise interactions. We analyze the computational complexity of the resulting optimization problem. We present a polynomial time approximation algorithm for this bi-clustering task and complement this result by showing that finding (exact) optimal solutions is NP-hard. As far as we know, these are the first positive approximation guarantees and formal NP-hardness results for any bi-clustering optimization problem. In addition, we show that our optimization problem can be efficiently solved by deterministic annealing, yielding a promising heuristic for large problem instances.} }
Endnote
%0 Conference Paper %T Monochromatic Bi-Clustering %A Sharon Wulff %A Ruth Urner %A Shai Ben-David %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-wulff13 %I PMLR %P 145--153 %U https://proceedings.mlr.press/v28/wulff13.html %V 28 %N 2 %X We propose a natural cost function for the bi-clustering task, the monochromatic cost. This cost function is suitable for detecting meaningful homogeneous bi-clusters based on categorical valued input matrices. Such tasks arise in many applications, such as the analysis of social networks and in systems-biology where researchers try to infer functional grouping of biological agents based on their pairwise interactions. We analyze the computational complexity of the resulting optimization problem. We present a polynomial time approximation algorithm for this bi-clustering task and complement this result by showing that finding (exact) optimal solutions is NP-hard. As far as we know, these are the first positive approximation guarantees and formal NP-hardness results for any bi-clustering optimization problem. In addition, we show that our optimization problem can be efficiently solved by deterministic annealing, yielding a promising heuristic for large problem instances.
RIS
TY - CPAPER TI - Monochromatic Bi-Clustering AU - Sharon Wulff AU - Ruth Urner AU - Shai Ben-David BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/05/13 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-wulff13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 2 SP - 145 EP - 153 L1 - http://proceedings.mlr.press/v28/wulff13.pdf UR - https://proceedings.mlr.press/v28/wulff13.html AB - We propose a natural cost function for the bi-clustering task, the monochromatic cost. This cost function is suitable for detecting meaningful homogeneous bi-clusters based on categorical valued input matrices. Such tasks arise in many applications, such as the analysis of social networks and in systems-biology where researchers try to infer functional grouping of biological agents based on their pairwise interactions. We analyze the computational complexity of the resulting optimization problem. We present a polynomial time approximation algorithm for this bi-clustering task and complement this result by showing that finding (exact) optimal solutions is NP-hard. As far as we know, these are the first positive approximation guarantees and formal NP-hardness results for any bi-clustering optimization problem. In addition, we show that our optimization problem can be efficiently solved by deterministic annealing, yielding a promising heuristic for large problem instances. ER -
APA
Wulff, S., Urner, R. & Ben-David, S.. (2013). Monochromatic Bi-Clustering. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(2):145-153 Available from https://proceedings.mlr.press/v28/wulff13.html.

Related Material