RankClus: integrating clustering with ranking for heterogeneous information network analysis

By Yizhou Sun, Jiawei Han, Peixiang Zhao, Zhijun Yin, Hong Cheng, Tianyi Wu. International Conference on Extending Database Technology, 2009

436 citations recorded by the source corpus.

As information networks become ubiquitous, extracting knowledge from information networks has become an important task. Both ranking and clustering can provide overall views on information network data, and each has been a hot topic by itself. However, ranking objects globally without considering which clusters they belong to often leads to dumb results, e.g., ranking database and computer architecture conferences together may not make much sense. Similarly, clustering a huge number of objects (e.g., thousands of authors) in one huge cluster without distinction is dull as well. In this paper, we address the problem of generating clusters for a specified type of objects, as well as ranking information for all types of objects based on these clusters in a multi-typed (i.e., heterogeneous) information network. A novel clustering framework called RankClus is proposed that directly generates clusters integrated with ranking. Based on initial K clusters, ranking is applied separately, which serves as a good measure for each cluster. Then, we use a mixture model to decompose each object into a K-dimensional vector, where each dimension is a component coefficient with respect to a cluster, which is measured by rank distribution. Objects then are reassigned to the nearest cluster under the new measure space to improve clustering. As a result, quality of clustering and ranking are mutually enhanced, which means that the clusters are getting more accurate and the ranking is getting more meaningful. Such a progressive refinement process iterates until little change can be made. Our experiment results show that RankClus can generate more accurate clusters and in a more efficient way than the state-of-the-art link-based clustering methods. Moreover, the clustering results with ranks can provide more informative views of data compared with traditional clustering.

Subfields: Artificial Intelligence, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/f77b5c0be3dafdb2000c84506e5b154bd37d3254

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Philip S. Yu
2. Jiawei Han
3. Charu C. Aggarwal
4. Yizhou Sun
5. Chuan Shi
6. Hong Cheng
7. Xifeng Yan
8. Jeffrey Xu Yu

In Computer Networks and Communications

1. Philip S. Yu
2. Jiawei Han
3. Hong Cheng
4. Xifeng Yan
5. Jeffrey Xu Yu
6. Yizhou Sun
7. Chuan Shi
8. Tianyi Wu

Citations in the corpus

• PathSim (2011, methodology): “As primary eigenvectors can be used as authority ranking of objects [16], the similarity between two objects under an infinite meta path can be viewed as a measure defined on their rankings (r(i) is the ranking score for object xi).”
• Mining heterogeneous information networks: a structural analysis approach (2013, background): “, RankClus [19] and NetClus [22]) that generates both clustering and ranking results efficiently.”
• Attention Models in Graphs (2018, methodology): “The study of heterogeneous graphs, also called heterogeneous information networks, has become quite popular in recent years with many papers published in the area [Dong et al. 2017; Lee and Adorna 2012; Sun et al. 2011, 2009a,b].”
• HeteSim: A General Framework for Relevance Measure in Heterogeneous Networks (2013, methodology): “The NMI criterion (NormalizedMutual Information) [30] is used to evaluate the clustering performances on conferences, authors, and papers.”
• Graph Clustering Based on Structural/Attribute Similarities (2009, methodology): “Sun et al. [ 21 ] proposed an algorithm, RankClus, which integrates clustering with ranking in large-scale information network analysis.”
• Ranking-based clustering of heterogeneous information networks with star network schema (2009, methodology): “Sci. NIPS Table 3: NMI between Attribute Types in Di.erent Scale of DBLP network able to catch the largest component structure of a network under the constraints that the relation between objects are recovered by 1-dimensional ranking.”