Effective and scalable clustering on massive attributed graphs

Renchi Yang, Jieming Shi*, Yin Yang, Keke Huang, Shiqi Zhang, Xiaokui Xiao

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

3 Citations (Scopus)

Abstract

Given a graph G where each node is associated with a set of attributes, and a parameter k specifying the number of output clusters, k-attributed graph clustering (k-AGC) groups nodes in G into k disjoint clusters, such that nodes within the same cluster share similar topological and attribute characteristics, while those in different clusters are dissimilar. This problem is challenging on massive graphs, e.g., with millions of nodes and billions of attribute values. For such graphs, existing solutions either incur prohibitively high costs, or produce clustering results with compromised quality. In this paper, we propose , an efficient approach to k-AGC that yields high-quality clusters with costs linear to the size of the input graph G. The main contributions of are twofold: (i) a novel formulation of the k-AGC problem based on an attributed multi-hop conductance quality measure custom-made for this problem setting, which effectively captures cluster coherence in terms of both topological proximities and attribute similarities, and (ii) a linear-time optimization solver that obtains high quality clusters iteratively, based on efficient matrix operations such as orthogonal iterations, an alternative optimization approach, as well as an initialization technique that significantly speeds up the convergence of in practice. Extensive experiments, comparing 11 competitors on 6 real datasets, demonstrate that consistently outperforms all competitors in terms of result quality measured against ground truth labels, while being up to orders of magnitude faster. In particular, on the Microsoft Academic Knowledge Graph dataset with 265.2 million edges and 1.1 billion attribute values, outputs high-quality results for 5-AGC within 1.68 hours using a single CPU core, while none of the 11 competitors finish within 3 days.

Original languageEnglish
Title of host publicationWWW '21: Proceedings of the Web Conference 2021
PublisherAssociation for Computing Machinery (ACM)
Pages3675-3687
Number of pages13
ISBN (Electronic)9781450383127
DOIs
Publication statusPublished - 3 Jun 2021
Event2021 World Wide Web Conference, WWW 2021 - Ljubljana, Slovenia
Duration: 19 Apr 202123 Apr 2021
https://dl.acm.org/doi/proceedings/10.1145/3442381

Publication series

NameWWW: International World Wide Web Conference

Conference

Conference2021 World Wide Web Conference, WWW 2021
Country/TerritorySlovenia
CityLjubljana
Period19/04/2123/04/21
Internet address

Scopus Subject Areas

  • Computer Networks and Communications
  • Software

User-Defined Keywords

  • Attributed graph
  • Graph clustering
  • Random walk

Fingerprint

Dive into the research topics of 'Effective and scalable clustering on massive attributed graphs'. Together they form a unique fingerprint.

Cite this