A probabilistic framework for relational clustering

ABSTRACT

Relational clustering has attracted more and more attention due to its phenomenal impact in various important applications which involve multi-type interrelated data objects, such as Web mining, search marketing, bioinformatics, citation analysis, and epidemiology. In this paper, we propose a probabilistic model for relational clustering, which also provides a principal framework to unify various important clustering tasks including traditional attributes-based clustering, semi-supervised clustering, co-clustering and graph clustering. The proposed model seeks to identify cluster structures for each type of data objects and interaction patterns between different types of objects. Under this model, we propose parametric hard and soft relational clustering algorithms under a large number of exponential family distributions. The algorithms are applicable to relational data of various structures and at the same time unifies a number of stat-of-the-art clustering algorithms: co-clustering algorithms, the k-partite graph clustering, Bregman k-means, and semi-supervised clustering based on hidden Markov random fields.

REFERENCES

• 1: E. Airoldi, D. Blei, E. Xing, and S. Fienberg. Mixed membership stochastic block models for relational data with application to protein-protein interactions. In ENAR-2006.
• 2: Arindam Banerjee , Inderjit Dhillon , Joydeep Ghosh , Srujana Merugu , Dharmendra S. Modha, A generalized maximum entropy approach to bregman co-clustering and matrix approximation, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014111]
• 3: Arindam Banerjee , Srujana Merugu , Inderjit S. Dhillon , Joydeep Ghosh, Clustering with Bregman Divergences, The Journal of Machine Learning Research, 6, p.1705-1749, 12/1/2005
• 4: Sugato Basu , Mikhail Bilenko , Raymond J. Mooney, A probabilistic framework for semi-supervised clustering, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014062]
• 5: I. Bhattachrya and L. Getor. Entity resolution in graph data. Technical Report CS-TR-4758, University of Maryland, 2005.
• 6: T. N. Bui and C. Jones. A heuristic for reducing fill-in in sparse matrix factorization. In PPSC, pages 445--452, 1993.
• 7: Pak K. Chan , Martine D. F. Schlag , Jason Y. Zien, Spectral K-way ratio-cut partitioning and clustering, Proceedings of the 30th international conference on Design automation, p.749-754, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165117]
• 8: H. Cho, I. Dhillon, Y. Guan, and S. Sra. Minimum sum squared residue co-clustering of gene expression data. In SDM, 2004.
• 9: M. Collins, S. Dasgupta, and R. Reina. A generalizaion of principal component analysis to the exponential family. In NIPS'01, 2001.
• 10: I. Dhillon, Y. Guan, and B. Kulis. A unified view of kernel k-means, spectral clustering and graph cuts. Technical Report TR-04-25, University of Texas at Austin, 2004.
• 11: 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]
• 12: 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]
• 13: 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
• 14: Nada Lavrac , Saso Dzeroski, Relational Data Mining, Springer-Verlag New York, Inc., Secaucus, NJ, 2001
• 15: E. Erosheva, S. Fienberg, and J. Lafferty. Mixed membership models of scientific publications. In NAS.
• 16: E. Erosheva and S. E. Fienberg. Bayesian mixed membership models for soft clustering and classification. Classification-The Ubiquitous Challenge, pages 11--26, 2005.
• 17: S. E. Fienberg, M. M. Meyer, and S. Wasserman. Satistical analysis of multiple cociometric relations. Journal of American Satistical Association, 80:51--87, 1985.
• 18: 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, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081879]
• 19: L. Getoor. An introduction to probabilistic graphical models for relational data. Data Engineering Bulletin, 29, 2006.
• 20: Bruce Hendrickson , Robert Leland, A multilevel algorithm for partitioning graphs, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.28-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224228]
• 21: P. Hoff, A. Rafery, and M. Handcock. Latent space approaches to social network analysis. Journal of American Satistical Association, 97:1090--1098, 2002.
• 22: T. Hofmann. Probabilistic latent semantic analysis. In Proc. of Uncertainty in Artificial Intelligence, UAI'99, Stockholm, 1999.
• 23: Thomas Hofmann , Jan Puzicha, Latent Class Models for Collaborative Filtering, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.688-693, July 31-August 06, 1999
• 24: Lawrence B. Holder , Diane J. Cook, Graph-based relational learning: current and future directions, ACM SIGKDD Explorations Newsletter, v.5 n.1, July 2003 [doi>10.1145/959242.959254]
• 25: 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]
• 26: Glen Jeh , Jennifer Widom, SimRank: a measure of structural-context similarity, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775126]
• 27: G. Karypis. A clustering toolkit, 2002.
• 28: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 29: M. Kearns, Y. Mansour, and A. Ng. An information-theoretic analysis of hard and soft assignment methods for clustering. In UAI'97, pages 282--293, 2004.
• 30: B. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 49(2):291--307, 1970.
• 31: M. Kirsten and S. Wrobel. Relational distance-based clustering. In Proc. Fachgruppentreffen Maschinelles Lernen (FGML-98), pages 119--124, 1998.
• 32: K. Lang. News weeder: Learning to filter netnews. In ICML, 1995.
• 33: Tao Li, A general model for clustering binary data, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081894]
• 34: 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 [doi>10.1145/1150402.1150439]
• 35: Bo Long , Zhongfei (Mark) Zhang , Philip S. Yu, Co-clustering by block value decomposition, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081949]
• 36: A. Ng, M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In Advances in Neural Information Processing Systems 14, 2001.
• 37: Luc De Raedt , Hendrik Blockeel, Using Logical Decision Trees for Clustering, Proceedings of the 7th International Workshop on Inductive Logic Programming, p.133-140, September 17-20, 1997
• 38: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 39: N. Rosenberg, J. Pritchard, J. Weber, and H. Cann. Genetic structure of human population. Science, 298, 2002.
• 40: J. S. D. Pietra, V. D. Pietera. Duality and auxiliary functions for bregman distances. Technical Report CMU-CS-01-109, Carnegie Mellon University, 2001.
• 41: S. Geman and D. Geman. Stochastic relaxation, gibbs distribution, and the bayesian restoration of images. Pattern Analysis and Machine Intelligence, 6:721--742, 1984.
• 42: 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]
• 43: T. Snijders. Markov chain monte carlo estimation of exponential random graph models. Journal of Ssocial Structure, 2002.
• 44: Alexander Strehl , Joydeep Ghosh, Cluster ensembles: a knowledge reuse framework for combining partitionings, Eighteenth national conference on Artificial intelligence, p.93-98, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 45: B. Taskar, E. Segal, and D. Koller. Probabilistic classification and clustering in relational data. In Proceeding of IJCAI-01, 2001.
• 46: Kiri Wagstaff , Claire Cardie , Seth Rogers , Stefan Schrödl, Constrained K-means Clustering with Background Knowledge, Proceedings of the Eighteenth International Conference on Machine Learning, p.577-584, June 28-July 01, 2001
• 47: 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]
• 48: E. Xing, A. Ng, M. Jorda, and S. Russel. Distance metric learning with applications to clustering with side information. In NIPS'03, volume 16, 2003.
• 49: Xiaoxin Yin , Jiawei Han , Philip S. Yu, Cross-relational clustering with user's guidance, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081910]
• 50: Xiaoxin Yin , Jiawei Han , Philip S. Yu, LinkClus: efficient clustering via heterogeneous semantic links, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 51: 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

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

General Terms:
Algorithms

Keywords:
clustering, relational clustering, relational data