Ranking-based clustering of heterogeneous information networks with star network schema

ABSTRACT

A heterogeneous information network is an information network

composed of multiple types of objects. Clustering on such a network may lead to better understanding of both hidden structures of the network and the individual role played by every object in each cluster. However, although clustering on homogeneous networks has been studied over decades, clustering on heterogeneous networks has not been addressed until recently.

A recent study proposed a new algorithm, RankClus, for clustering on bi-typed heterogeneous networks. However, a real-world network may consist of more than two types, and the interactions among multi-typed objects play a key role at disclosing the rich semantics that a network carries. In this paper, we study clustering of multi-typed heterogeneous networks with a star network schema and propose a novel algorithm, NetClus, that utilizes links across multityped objects to generate high-quality net-clusters. An iterative enhancement method is developed that leads to effective ranking-based clustering in such heterogeneous networks. Our experiments on DBLP data show that NetClus generates more accurate clustering results than the baseline topic model algorithm PLSA and the recently proposed algorithm, RankClus. Further, NetClus generates informative clusters, presenting good ranking and cluster membership information for each attribute object in each net-cluster.

REFERENCES

• 1: A. Banerjee, S. Basu, and S. Merugu. Multi-way clustering on relation graphs. In Proceedings of the 7th SIAM International Conference on Data Mining SIAM'07, 2007.
• 2: Ron Bekkerman , Ran El-Yaniv , Andrew McCallum, Multi-way distributional clustering via pairwise interactions, Proceedings of the 22nd international conference on Machine learning, p.41-48, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102357]
• 3: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 4: 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
• 5: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 6: T. Hofmann. Probabilistic latent semantic analysis. In In Proc. of Uncertainty in Artificial Intelligence (UAI'99)UAI'99, pages 289--296, 1999.
• 7: 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]
• 8: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 9: 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 [doi>10.1145/1143844.1143918]
• 10: Qiaozhu Mei , Duo Zhang , ChengXiang Zhai, A general optimization framework for smoothing language models on graph structures, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390438]
• 11: M. E. J. Newman. The structure of scientific collaboration networks. Working Papers 00-07-037, Santa Fe Institute, July 2000.
• 12: M. E. J. Newman. Assortative mixing in networks. Physical Review Letters, 89(20):208701, October 2002.
• 13: Zaiqing Nie , Yuanzhi Zhang , Ji-Rong Wen , Wei-Ying Ma, Object-level ranking: bringing order to Web objects, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060828]
• 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: Mark Steyvers , Padhraic Smyth , Michal Rosen-Zvi , Thomas Griffiths, Probabilistic author-topic models for information discovery, 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.1014087]
• 16: Yizhou Sun , Jiawei Han , Peixiang Zhao , Zhijun Yin , Hong Cheng , Tianyi Wu, RankClus: integrating clustering with ranking for heterogeneous information network analysis, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia [doi>10.1145/1516360.1516426]
• 17: Yuanyuan Tian , Richard A. Hankins , Jignesh M. Patel, Efficient aggregation for graph summarization, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376675]
• 18: U. von Luxburg. A tutorial on spectral clustering. Technical report, Max Planck Institute for Biological Cybernetics, 2006.
• 20: S. White and P. Smyth. A spectral clustering approach to finding communities in graph. In Proceedings of the Fifth SIAM International Conference on Data Mining (SDM'05)SDM'05, 2005.
• 21: Xiaowei Xu , Nurcan Yuruk , Zhidan Feng , Thomas A. J. Schweiger, SCAN: a structural clustering algorithm for networks, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281280]
• 22: Chengxiang Zhai , John Lafferty, A study of smoothing methods for language models applied to information retrieval, ACM Transactions on Information Systems (TOIS), v.22 n.2, p.179-214, April 2004 [doi>10.1145/984321.984322]
• 23: ChengXiang Zhai , Atulya Velivelli , Bei Yu, A cross-collection mixture model for comparative text mining, 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.1014150]
• 190: Nan Wang , Srinivasan Parthasarathy , Kian-Lee Tan , Anthony K. H. Tung, CSV: visualizing and mining cohesive subgraphs, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376663]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
clustering, heterogeneous information network