Bipartite graph partitioning and data clustering

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Bipartite graph partitioning and data clustering

Full text

Pdf (1.45 MB)

Source

Conference on Information and Knowledge Management archive
Proceedings of the tenth international conference on Information and knowledge management table of contents

Atlanta, Georgia, USA

Session: Clustering table of contents

Pages: 25 - 32

Year of Publication: 2001

ISBN:1-58113-436-3

Authors

Hongyuan Zha	Penn State Univ., State College, PA
Xiaofeng He	Penn State Univ., State College, PA
Chris Ding	Berkeley National Lab., Berkeley, CA
Horst Simon	Berkeley National Lab., Berkeley, CA
Ming Gu	U.C. Berkeley, Berkeley, CA

Sponsors

SIGMIS: ACM Special Interest Group on Management Information Systems
SIGIR: ACM Special Interest Group on Information Retrieval

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 44, Downloads (12 Months): 261, Citation Count: 34

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/502585.502591 What is a DOI?

ABSTRACT

Many data types arising from data mining applications can be modeled as bipartite graphs, examples include terms and documents in a text corpus, customers and purchasing items in market basket analysis and reviewers and movies in a movie recommender system. In this paper, we propose a new data clustering method based on partitioning the underlying bipartite graph. The partition is constructed by minimizing a normalized sum of edge weights between unmatched pairs of vertices of the bipartite graph. We show that an approximate solution to the minimization problem can be obtained by computing a partial singular value decomposition (SVD) of the associated edge weight matrix of the bipartite graph. We point out the connection of our clustering algorithm to correspondence analysis used in multivariate analysis. We also briefly discuss the issue of assigning data objects to multiple clusters. In the experimental results, we apply our clustering algorithm to the problem of document clustering to illustrate its effectiveness and efficiency.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Richard K. Belew , C. J. Van Rijsbergen, Finding out about: a cognitive perspective on search engine technology and the WWW, Cambridge University Press, New York, NY, 2000
	2	J.-P. Benzecri. Correspondence analysis handbook. Marcel Dekker, 1992.
	3	Daniel Boley, Principal Direction Divisive Partitioning, Data Mining and Knowledge Discovery, v.2 n.4, p.325-344, December 1998 [doi>10.1023/A:1009740529316]
	4	F.R.K. Chung. Spectral Graph Theory. American Mathematical Society, 1997.
	5	R. Van Driessche , D. Roose, An improved spectral bisection algorithm and its application to dynamic load balancing, Parallel Computing, v.21 n.1, p.29-48, Jan. 1995 [doi>10.1016/0167-8191(94)00059-J]
	6	B. Everitt. Cluster Analysis. Edward Arnold, 1993.
	7	M. Fiedler. Algebraic connectivity of graphs. Czechoslovak Math J., 23:298-305, 1973.
	8	Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
	9	A. D. Gordon. Classficataon. Second Edition, Chapman and Hall, 2000.
	10	M.J. Greenacre. Correspondence analysis an practice. Academic Press, 1993.
	11	Bruce Hendrickson , Tamara G. Kolda, Partitioning Rectangular and Structurally Unsymmetric Sparse Matrices for Parallel Processing, SIAM Journal on Scientific Computing, v.21 n.6, p.2048-2072, Dec 1999 [doi>10.1137/S1064827598341475]
	12	Thomas Hofmann, Probabilistic latent semantic indexing, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.50-57, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312649]
	13	A. McCallum. Bow: A toolkit for statistical language modeling, text retrieval, classification and clustering. http://wvu.cs.cmu.edu/ mccallum/bow, 1996.
	14	Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97), p.731, June 17-19, 1997
	15	Noam Slonim , Naftali Tishby, Document clustering using word clusters via the information bottleneck method, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.208-215, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345578]
	16	W.N. Venables and B.D. Ripley. Modern Applied Statistics with S-plus. Springer-verlag, 1999.

CITED BY 34

	Hongyuan Zha , Xiang Ji, Correlating multilingual documents via bipartite graph modeling, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland
	Hui Han , Lee Giles , Hongyuan Zha , Cheng Li , Kostas Tsioutsiouliklis, Two supervised learning approaches for name disambiguation in author citations, Proceedings of the 4th ACM/IEEE-CS joint conference on Digital libraries, June 07-11, 2004, Tuscon, AZ, USA
	Ying Zhao , George Karypis, Empirical and Theoretical Comparisons of Selected Criterion Functions for Document Clustering, Machine Learning, v.55 n.3, p.311-331, June 2004
	Zheng-Yu Niu , Dong-Hong Ji , Chew-Lim Tan, Document clustering based on cluster validation, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
	Wei Xu , Yihong Gong, Document clustering by concept factorization, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom
	S. H. Srinivasan, Features for unsupervised document classification, proceeding of the 6th conference on Natural language learning, p.1-7, August 31, 2002
	Bin Gao , Tie-Yan Liu , Xin Zheng , Qian-Sheng Cheng , Wei-Ying Ma, Consistent bipartite graph co-partitioning for star-structured high-order heterogeneous data co-clustering, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
	Hui Han , Hongyuan Zha , C. Lee Giles, Name disambiguation in author citations using a K-way spectral clustering method, Proceedings of the 5th ACM/IEEE-CS joint conference on Digital libraries, June 07-11, 2005, Denver, CO, USA
	Bhushan Mandhani , Sachindra Joshi , Krishna Kummamuru, A matrix density based algorithm to hierarchically co-cluster documents and words, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary
	Bin Gao , Tie-Yan Liu , Tao Qin , Xin Zheng , Qian-Sheng Cheng , Wei-Ying Ma, Web image clustering by consistent utilization of visual features and surrounding texts, Proceedings of the 13th annual ACM international conference on Multimedia, November 06-11, 2005, Hilton, Singapore
	Bin Gao , Tie-Yan Liu , Guang Feng , Tao Qin , Qian-Sheng Cheng , Wei-Ying Ma, Hierarchical Taxonomy Preparation for Text Categorization Using Consistent Bipartite Spectral Graph Copartitioning, IEEE Transactions on Knowledge and Data Engineering, v.17 n.9, p.1263-1273, September 2005
	Chris Ding , Tao Li , Wei Peng , Haesun Park, Orthogonal nonnegative matrix t-factorizations for clustering, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
	Bo Long , Zhongfei (Mark) Zhang , Xiaoyun Wú , Philip S. Yu, Spectral clustering for multi-type relational data, Proceedings of the 23rd international conference on Machine learning, p.585-592, June 25-29, 2006, Pittsburgh, Pennsylvania
	Bo Long , Xiaoyun Wu , Zhongfei (Mark) Zhang , Philip S. Yu, Unsupervised learning on k-partite graphs, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
	Hua Yan , Keke Chen , Ling Liu, Efficiently clustering transactional data with weighted coverage density, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
	Güneş Erkan, Language model-based document clustering using random walks, Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, p.479-486, June 04-09, 2006, New York, New York
	Zheng-Yu Niu , Dong-Hong Ji , Chew Lim Tan, Using cluster validation criterion to identify optimal feature subset and cluster number for document clustering, Information Processing and Management: an International Journal, v.43 n.3, p.730-739, May, 2007
	Chris Ding , Tao Li, Adaptive dimension reduction using discriminant analysis and K-means clustering, Proceedings of the 24th international conference on Machine learning, p.521-528, June 20-24, 2007, Corvalis, Oregon
	Bo Long , Zhongfei (Mark) Zhang , Xiaoyun Wu , Philip S. Yu, Relational clustering by symmetric convex coding, Proceedings of the 24th international conference on Machine learning, p.569-576, June 20-24, 2007, Corvalis, Oregon
	Ying Zhao , George Karypis , Usama Fayyad, Hierarchical Clustering Algorithms for Document Datasets, Data Mining and Knowledge Discovery, v.10 n.2, p.141-168, March 2005
	Navaratnasothie Selvakkumaran , George Karypis, Multi.Objective Hypergraph Partitioning Algorithms for Cut and Maximum Subdomain Degree Minimization, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.726, November 09-13, 2003
	Tao Li , Chris Ding , Yi Zhang , Bo Shao, Knowledge transformation from word space to document space, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore
	Yang Song , Ziming Zhuang , Huajing Li , Qiankun Zhao , Jia Li , Wang-Chien Lee , C. Lee Giles, Real-time automatic tag recommendation, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore
	Guobiao Hu , Shuigeng Zhou , Jihong Guan , Xiaohua Hu, Towards effective document clustering: A constrained K-means based approach, Information Processing and Management: an International Journal, v.44 n.4, p.1397-1409, July, 2008
	Bo Long , Zhongfei Mark Zhang , Philip S. Yu, A probabilistic framework for relational clustering, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA
	Manjeet Rege , Ming Dong , Jing Hua, Graph theoretical framework for simultaneously integrating visual and textual features for efficient web image clustering, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China
	Lei Tang , Huan Liu , Jianping Zhang , Zohreh Nazeri, Community evolution in dynamic multi-mode networks, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA
	Manjeet Rege , Ming Dong , Farshad Fotouhi, Bipartite isoperimetric graph partitioning for data co-clustering, Data Mining and Knowledge Discovery, v.16 n.3, p.276-312, June 2008
	Bo Shao , Tao Li , Mitsunori Ogihara, Quantify music artist similarity based on style and mood, Proceeding of the 10th ACM workshop on Web information and data management, October 30-30, 2008, Napa Valley, California, USA
	Yang Song , Lu Zhang , C. Lee Giles, A sparse gaussian processes classification framework for fast tag suggestions, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA
	Bo Long , Mark Zhang , Philip S. Yu, Graph partitioning based on link distributions, Proceedings of the 22nd national conference on Artificial intelligence, p.578-583, July 22-26, 2007, Vancouver, British Columbia, Canada
	Gang Chen , Fei Wang , Changshui Zhang, Collaborative filtering using orthogonal nonnegative matrix tri-factorization, Information Processing and Management: an International Journal, v.45 n.3, p.368-379, May, 2009
	Lin Li , Zhenglu Yang , Ling Liu , Masaru Kitsuregawa, Query-URL bipartite based approach to personalized query recommendation, Proceedings of the 23rd national conference on Artificial intelligence, p.1189-1194, July 13-17, 2008, Chicago, Illinois
	Chris H. Q. Ding, Data clustering: principal components, Hopfield and self-aggregation networks, Proceedings of the 18th international joint conference on Artificial intelligence, p.479-484, August 09-15, 2003, Acapulco, Mexico