Consistent bipartite graph co-partitioning for star-structured high-order heterogeneous data co-clustering

ABSTRACT

Heterogeneous data co-clustering has attracted more and more attention in recent years due to its high impact on various applications. While the co-clustering algorithms for two types of heterogeneous data (denoted by pair-wise co-clustering), such as documents and terms, have been well studied in the literature, the work on more types of heterogeneous data (denoted by high-order co-clustering) is still very limited. As an attempt in this direction, in this paper, we worked on a specific case of high-order co-clustering in which there is a central type of objects that connects the other types so as to form a star structure of the inter-relationships. Actually, this case could be a very good abstract for many real-world applications, such as the co-clustering of categories, documents and terms in text mining. In our philosophy, we treated such kind of problems as the fusion of multiple pair-wise co-clustering sub-problems with the constraint of the star structure. Accordingly, we proposed the concept of consistent bipartite graph co-partitioning, and developed an algorithm based on semi-definite programming (SDP) for efficient computation of the clustering results. Experiments on toy problems and real data both verified the effectiveness of our proposed method.

REFERENCES

• 1: Bach, F.R., and Jordan, M.I. Learning spectral clustering. Neural Info. Processing Systems 16 (NIPS 2003), 2003.
• 2: H. P. Benson, Global optimization algorithm for the nonlinearsum of ratios problem, Journal of Optimization Theory and Applications, v.112 n.1, p.1-29, January 2002 [doi>10.1023/A:1013072027218]
• 3: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 4: Inderjit S. Dhillon, Co-clustering documents and words using bipartite spectral graph partitioning, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.269-274, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502550]
• 5: Inderjit S. Dhillon , Subramanyam Mallela , Dharmendra S. Modha, Information-theoretic co-clustering, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956764]
• 6: Chris H. Q. Ding , Xiaofeng He , Hongyuan Zha , Ming Gu , Horst D. Simon, A Min-max Cut Algorithm for Graph Partitioning and Data Clustering, Proceedings of the 2001 IEEE International Conference on Data Mining, p.107-114, November 29-December 02, 2001
• 7: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 8: Frenk, J.B.G., and Schaible, S. Fractional Programming. ERIM Report Series Reference No. ERS-2004-074-LIS. http://ssrn.com/abstract=595012.
• 9: Fujisawa, K., Fukuda, M., Kojima, M., and Nakata, K. Numerical evaluation of the SDPA (SemiDefinite Programming Algorithm). High Performance Optimization, Kluwer Academic Press, 267--301, 2000.
• 10: 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 [doi>10.1109/TKDE.2005.147]
• 11: Golub, G.H., and Loan, C.F.V. Matrix computations. Johns Hopkins University Press, 3rd edition, 1996.
• 12: Hagen, L., and Kahng, A.B. New spectral methods for ratio cut partitioning and clustering. IEEE. Trans. on Computed Aided Desgin, 11:1074--1085, 1992.
• 13: Klerk, E. Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications. Applied Optimization Series, Volume 65. Kluwer Academic Publishers, March 2002, 300 pp., ISBN 1-4020-0547-4.
• 14: Kluger, Y., Basri, R., Chang, J.T., and Gerstein, M. Spectral biclustering of microarray cancer data: co-clustering genes and conditions. Genome Res., Apr 2003; 13: 703--716.
• 15: Dharmendra S. Modha , W. Scott Spangler, Feature Weighting in k-Means Clustering, Machine Learning, v.52 n.3, p.217-237, September 2003 [doi>10.1023/A:1024016609528]
• 16: Monteiro, R.D.C. First- and Second-Order Methods for Semidefinite Programming. Georgia Tech, January 2003.
• 17: Pardalos, P.M. and Wolkowicz, H. Topics in Semidefinite and Interior Point Methods. Fields Institute Communications 18, AMS, Providence, Rhode Island, 1998.
• 18: Alex Pothen , Horst D. Simon , Kan-Pu Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal on Matrix Analysis and Applications, v.11 n.3, p.430-452, Jul. 1990 [doi>10.1137/0611030]
• 19: Guoping Qiu, Image and Feature Co-Clustering, Proceedings of the Pattern Recognition, 17th International Conference on (ICPR'04) Volume 4, p.991-994, August 23-26, 2004 [doi>10.1109/ICPR.2004.468]
• 20: SDPA Online for your future. http://grid.r.dendai.ac.jp/sdpa/.
• 21: Semidefinite Programming. http://www-user.tu-chemnitz.de/~helmberg/semidef.html.
• 22: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 23: Jidong Wang , Huajun Zeng , Zheng Chen , Hongjun Lu , Li Tao , Wei-Ying Ma, ReCoM: reinforcement clustering of multi-type interrelated data objects, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860486]
• 24: Yiming Yang , Jan O. Pedersen, A Comparative Study on Feature Selection in Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning, p.412-420, July 08-12, 1997
• 25: Hua-Jun Zeng , Zheng Chen , Wei-Ying Ma, A Unified Framework for Clustering Heterogeneous Web Objects, Proceedings of the 3rd International Conference on Web Information Systems Engineering, p.161-172, December 12-14, 2002
• 26: Hongyuan Zha , Xiaofeng He , Chris Ding , Horst Simon , Ming Gu, Bipartite graph partitioning and data clustering, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502591]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
co-clustering, consistency, high-order heterogeneous data, spectral graph