research-article

Approximation algorithms for co-clustering

Authors:

Aris Anagnostopoulos,

Anirban Dasgupta,

Ravi KumarAuthors Info & Claims

PODS '08: Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

Pages 201 - 210

https://doi.org/10.1145/1376916.1376945

Published: 09 June 2008 Publication History

Abstract

Co-clustering is the simultaneous partitioning of the rows and columns of a matrix such that the blocks induced by the row/column partitions are good clusters. Motivated by several applications in text mining, market-basket analysis, and bioinformatics, this problem has attracted severe attention in the past few years. Unfortunately, to date, most of the algorithmic work on this problem has been heuristic in nature.

In this work we obtain the first approximation algorithms for the co-clustering problem. Our algorithms are simple and obtain constant-factor approximation solutions to the optimum. We also show that co-clustering is NP-hard, thereby complementing our algorithmic result.

References

[1]

D. Agarwal and S. Merugu. Predictive discrete latent factor models for large scale dyadic data. In Proc. of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 26--35, 2007.

Digital Library

[2]

V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit. Local search heuristics for k-median and facility location problems. SIAM Journal on Computing, 33(3):544--562, June 2004.

Digital Library

[3]

M. Bǎdoiu, S. Har-Peled, and P. Indyk. Approximate clustering via core-sets. In Proc. of the 34th Annual ACM Symposium on Theory of Computing, pages 250--257, 2002.

Digital Library

[4]

A. Banerjee, I. Dhillon, J. Ghosh, S. Merugu, and D. S. Modha. A generalized maximum entropy approach to Bregman co-clustering and matrix approximation. Journal of Machine Learning Research, 8:1919--1986, 2007.

Digital Library

[5]

N. Bansal, A. Blum, and S. Chawla. Correlation clustering. Machine Learning, 56(1-3):89--113, 2004.

Digital Library

[6]

Y. Cheng and G. M. Church. Biclustering of expression data. In Proc. of the 8th International Conference on Intelligent Systems for Molecular Biology, pages 93--103, 2000.

Digital Library

[7]

H. Cho, I. S. Dhillon, Y. Guan, and S. Sra. Minimum sum-squared residue co-clustering of gene expression data. In Proc. of the 4th SIAM International Conference on Data Mining. SIAM, 2004.

[8]

I. S. Dhillon. Co-clustering documents and words using bipartite spectral graph partitioning. In Proc. of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 269--274, 2001.

Digital Library

[9]

P. Drineas, A. M. Frieze, R. Kannan, S. Vempala, and V. Vinay. Clustering large graphs via the singular value decomposition. Machine Learning, 56(1-3):9--33, 2004.

Digital Library

[10]

R. O. Duda, P. E. Hart, and D. G. Stork. Pattern Classification. Wiley Interscience, 2000.

Digital Library

[11]

U. Feige and S. Kogan. Hardness of approximation of the balanced complete bipartite subgraph problem, 2004.

[12]

B. Gao, T. Liu, X. Zheng, Q. Cheng, and W. Ma. Consistent bipartite graph co-partitioning for star-structured high-order heterogeneous data co-clustering. In Proc. of the 11th ACM Conference on Knowledge Discovery and Data Mining, pages 41--50, 2005.

Digital Library

[13]

S. Gollapudi, R. Kumar, and D. Sivakumar. Programmable clustering. In Proc. 25th ACM Symposium on Principles of Database Systems, pages 348--354, 2006.

Digital Library

[14]

J. A. Hartigan. Direct clustering of a data matrix. Journal of the American Statistical Association, 67(337):123--129, 1972.

[15]

S. Hassanpour. Computational complexity of bi-clustering. Master's thesis, University of Waterloo, 2007.

[16]

A. K. Jain, M. N. Murty, and P. J. Flynn. Data clustering: A review. ACM Computing Surveys, 31(3):264--323, 1999.

Digital Library

[17]

K. Jain and V. V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. Journal of the ACM, 48(2):274--296, 2001.

Digital Library

[18]

M. Jambyu and M. O. Lebeaux. Cluster Analysis and Data Analysis. North-Holland, 1983.

[19]

J. Kleinberg. An impossibility theorem for clustering. In Advances in Neural Information Processing Systems 15, pages 446--453, 2002.

[20]

Y. Kluger, R. Basri, J. T. Chang, and M. Gerstein. Spectral biclustering of microarray data: Coclustering genes and conditions. Genome Research, 13:703--716, 2003.

[21]

A. Kumar, Y. Sabharwal, and S. Sen. A simple linear time (1 + ε)-approximation algorithm for k-means clustering in any dimensions. In Proc. of the 45th IEEE Symposium on Foundations of Computer Science, pages 454--462, 2004.

Digital Library

[22]

S. C. Madeira and A. L. Oliveira. Biclustering algorithms for biological data analysis: A survey. IEEE Transactions on Computational Biology and Bioinformatics, 1(1):24--45, 2004.

Digital Library

[23]

N. Megiddo and K. J. Supowit. On the complexity of some common geometric location problems. SIAM Journal on Computing, 13(1):182--196, 1984.

[24]

N. Mishra, D. Ron, and R. Swaminathan. On finding large conjunctive clusters. In Proc. of the 16th Annual Conference on Computational Learning Theory, pages 448--462, 2003.

[25]

N. Mishra, D. Ron, and R. Swaminathan. A new conceptual clustering framework. Machine Learning, 56(1-3):115--151, 2004.

Digital Library

[26]

R. Peeters. The maximum edge biclique problem is NP-complete. Discrete Applied Mathematics, 131(3):651--654, 2003.

Digital Library

[27]

K. Puolamäki, S. Hanhijärvi, and G. C. Garriga. An approximation ratio for biclustering. CoRR, abs/0712.2682, 2007.

[28]

R. Shamir, R. Sharan, and D. Tsur. Cluster graph modification problems. Discrete Applied Mathematics, 144(1-2):173--182, 2004.

Digital Library

[29]

H. Takamura and Y. Matsumoto. Co-clustering for text categorization. Information Processing Society of Japan Journal, 2003.

[30]

A. Tanay, R. Sharan, and R. Shamir. Biclustering algorithms: A survey. In E. by Srinivas Aluru, editor, In Handbook of Computational Molecular Biology. Chapman & Hall/CRC, Computer and Information Science Series, 2005.

[31]

V. V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001.

Digital Library

[32]

J. Yang, H. Wang, W. Wang, and P. Yu. Enhanced biclustering on expression data. In Proc. of the 3rd IEEE Conference on Bioinformatics and Bioengineering, pages 321--327, 2003.

Digital Library

[33]

J. Yang, W. Wang, H. Wang, and P. S. Yu. delta-clusters: Capturing subspace correlation in a large data set. In Proc. of the 18th International Conference on Data Engineering, pages 517--528, 2002.

Digital Library

[34]

H. Zhou and D. P. Woodruff. Clustering via matrix powering. In Proc. of the 23rd ACM Symposium on Principles of Database Systems, pages 136--142, 2004.

Digital Library

Cited By

Zheleva ETerzi EGetoor L(2022)Privacy in Social NetworksundefinedOnline publication date: 24-Mar-2022
Papalexakis EBeutel ASteenkiste P(2018)Network Anomaly Detection Using Co-clusteringEncyclopedia of Social Network Analysis and Mining10.1007/978-1-4939-7131-2_354(1501-1516)Online publication date: 12-Jun-2018
Allab KLabiod LNadif M(2017)Multi-manifold matrix decomposition for data co-clusteringPattern Recognition10.1016/j.patcog.2016.11.02764:C(386-398)Online publication date: 1-Apr-2017
Show More Cited By

Index Terms

Approximation algorithms for co-clustering
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Co-clustering by block value decomposition
KDD '05: Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining

Dyadic data matrices, such as co-occurrence matrix, rating matrix, and proximity matrix, arise frequently in various important applications. A fundamental problem in dyadic data analysis is to find the hidden block structure of the data matrix. In this ...
Non-Exhaustive, Overlapping Co-Clustering
CIKM '17: Proceedings of the 2017 ACM on Conference on Information and Knowledge Management

The goal of co-clustering is to simultaneously identify a clustering of the rows as well as the columns of a two dimensional data matrix. Most existing co-clustering algorithms are designed to find pairwise disjoint and exhaustive co-clusters. However, ...
An improved approximation algorithm for hierarchical clustering

A hierarchical clustering algorithm has been proposed.The proposed algorithm improves upon the current approximation ratio.Performance guarantee of the algorithm for the k-median objective has been derived. Dasgupta and Long [7] have shown that it is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS '08: Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

June 2008

330 pages

ISBN:9781605581521

DOI:10.1145/1376916

General Chair:
Phokion Kolaitis
IBM Almaden Research Center, USA
,
Program Chair:
Maurizio Lenzerini
SAPIENZA University of Rome, Italy

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 June 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMOD/PODS '08

Sponsor:

SIGMOD/PODS '08: SIGMOD/PODS '08 - International Conference on Management of Data

June 9 - 12, 2008

Vancouver, Canada

Acceptance Rates

PODS '08 Paper Acceptance Rate 28 of 159 submissions, 18%;

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
756
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)3

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zheleva ETerzi EGetoor L(2022)Privacy in Social NetworksundefinedOnline publication date: 24-Mar-2022
Papalexakis EBeutel ASteenkiste P(2018)Network Anomaly Detection Using Co-clusteringEncyclopedia of Social Network Analysis and Mining10.1007/978-1-4939-7131-2_354(1501-1516)Online publication date: 12-Jun-2018
Allab KLabiod LNadif M(2017)Multi-manifold matrix decomposition for data co-clusteringPattern Recognition10.1016/j.patcog.2016.11.02764:C(386-398)Online publication date: 1-Apr-2017
Papalexakis EBeutel ASteenkiste P(2017)Network Anomaly Detection Using Co-clusteringEncyclopedia of Social Network Analysis and Mining10.1007/978-1-4614-7163-9_354-1(1-17)Online publication date: 22-Apr-2017
Cheng WZhang XPan FWang W(2016)HICCKnowledge and Information Systems10.1007/s10115-015-0823-x46:2(343-367)Online publication date: 1-Feb-2016
Wang YLiu WCaccetta LZhou G(2015)Parameter selection for nonnegative l 1 matrix/tensor sparse decompositionOperations Research Letters10.1016/j.orl.2015.06.00543:4(423-426)Online publication date: 1-Jul-2015
Pensa RPenta ASapino M(2015)Multimedia Recommendation and Delivery StrategiesData Management in Pervasive Systems10.1007/978-3-319-20062-0_16(327-342)Online publication date: 2015
Vlachos MFusco FMavroforakis CKyrillidis AVassiliadis VLi JWang XGarofalakis MSoboroff ISuel TWang M(2014)Improving Co-Cluster Quality with Application to Product RecommendationsProceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management10.1145/2661829.2661980(679-688)Online publication date: 3-Nov-2014
Beutel AMurray KFaloutsos CSmola AChung CBroder AShim KSuel T(2014)CoBaFiProceedings of the 23rd international conference on World wide web10.1145/2566486.2568040(97-108)Online publication date: 7-Apr-2014
Epasto AFeldman JLattanzi SLeonardi SMirrokni VChung CBroder AShim KSuel T(2014)Reduce and aggregateProceedings of the 23rd international conference on World wide web10.1145/2566486.2568025(349-360)Online publication date: 7-Apr-2014
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents