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 edges. For such graphs, existing solutions either incur prohibitively high costs, or produce clustering results with compromised quality. In this paper, we propose ACMin, an effective approach to k-AGC that yields high-quality clusters with cost linear to the size of the input graph G. The main contributions of ACMin 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 ACMin in practice. Extensive experiments, comparing 11 competitors on 6 real datasets, demonstrate that ACMin 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, ACMin 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.
翻译:鉴于每个节点都与一组属性相关联的图形 G, 以及一个参数 k 指定输出群集数目的数值, k属性图形群集( k- AGC) 将 G 中的 K属性图形群集( k- AGC) 节点组成 k 互换组群, 使同一组群中的节点具有相似的表层和属性特性, 而不同组群中的节点则不同。 这个问题在巨大的图表上具有挑战性, 例如, 数百万个节点和数十亿边缘。 对于这些图表, 现有的解决方案要么带来惊人的高成本, 或产生质量下降的质量。 在本文件中, 我们提议对 k属性群集采取有效的方法, 使 K- AGC 生成高质量的组合群集, 成本线性组合组群与输入G 的大小相直线线。