Efficient and Incremental Clustering Algorithms on Star-Schema Heterogeneous Graphs

Lu Chen, Yunjun Gao, Yuanliang Zhang, Christian S. Jensen, Bolong Zheng

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

4 Citations (Scopus)


Many datasets including social media data and bibliographic data can be modeled as graphs. Clustering such graphs is able to provide useful insights into the structure of the data. To improve the quality of clustering, node attributes can be taken into account, resulting in attributed graphs. Existing attributed graph clustering methods generally consider attribute similarity and structural similarity separately. In this paper, we represent attributed graphs as star-schema heterogeneous graphs, where attributes are modeled as different types of graph nodes. This enables the use of personalized pagerank (PPR) as a unified distance measure that captures both structural and attribute similarity. We employ DBSCAN for clustering, and we update edge weights iteratively to balance the importance of different attributes. To improve the efficiency of the clustering, we develop two incremental approaches that aim to enable efficient PPR score computation when edge weights are updated. To boost the effectiveness of the clustering, we propose a simple yet effective edge weight update strategy based on entropy. In addition, we present a game theory based method that enables trading efficiency for result quality. Extensive experiments on real-life datasets offer insight into the effectiveness and efficiency of our proposals, compared with existing methods.
Original languageEnglish
Title of host publicationProceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019
Number of pages12
Publication date2019
Article number8731611
ISBN (Print)978-1-5386-7475-8
ISBN (Electronic)978-1-5386-7474-1
Publication statusPublished - 2019
EventThe 35th IEEE International Conference on Data Engineering (ICDE) - Macau, Macau, China
Duration: 8 Apr 201912 Apr 2019


ConferenceThe 35th IEEE International Conference on Data Engineering (ICDE)
SeriesProceedings of the International Conference on Data Engineering


  • Algorithm
  • Graph clustering
  • Graph mining
  • Heterogeneous graph

Fingerprint Dive into the research topics of 'Efficient and Incremental Clustering Algorithms on Star-Schema Heterogeneous Graphs'. Together they form a unique fingerprint.

Cite this