Real graphs come with attributes — user profiles, page content, product features — and good clusters should be coherent in both structure and attributes. Most attributed-graph clustering methods either sacrifice quality for speed or cannot scale past a few million nodes.

The ACMin idea

ACMin (led by Renchi Yang) defines a clustering objective based on attributed multi-hop conductance: a random-walk model in which the walker moves through both topological edges and attribute similarities, so cluster quality reflects how well clusters trap these hybrid walks. The optimization runs via an efficient iterative scheme with per-iteration cost linear in graph size.

Results

ACMin produces higher-quality clusters than prior attributed clustering methods while scaling to graphs with tens of millions of nodes on a single machine — including datasets where competing methods run out of time or memory.