Amazing technological breakthrough possible @S-Logix pro@slogix.in

Office Address

  • #5, First Floor, 4th Street Dr. Subbarayan Nagar Kodambakkam, Chennai-600 024 Landmark : Samiyar Madam
  • pro@slogix.in
  • +91- 81240 01111

Social List

Effective and Scalable Clustering on Massive Attributed Graphs - 2021

Author(s) Name:  Renchi Yang , Jieming Shi, Yin Yang, Keke Huang, Shiqi Zhang, and Xiaokui Xiao
Journal name:  
Conferrence name:  WWW-21: Proceedings of the Web Conference April 2021
Publisher name:  ACM
DOI:  https://doi.org/10.1145/3442381.3449875
Research Area:  Machine Learning
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.

Volume Information:  Pages 3675–3687
Journal Link:

https://dl.acm.org/doi/abs/10.1145/3442381.3449875