  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.
