  Higher-order graph clustering aims to partition the graph using frequently
occurring subgraphs. Motif conductance is one of the most promising
higher-order graph clustering models due to its strong interpretability.
However, existing motif conductance based graph clustering algorithms are
mainly limited by a seminal two-stage reweighting computing framework, needing
to enumerate all motif instances to obtain an edge-weighted graph for
partitioning. However, such a framework has two-fold vital defects: (1) It can
only provide a quadratic bound for the motif with three vertices, and whether
there is provable clustering quality for other motifs is still an open
question. (2) The enumeration procedure of motif instances incurs prohibitively
high costs against large motifs or large dense graphs due to combinatorial
explosions. Besides, expensive spectral clustering or local graph diffusion on
the edge-weighted graph also makes existing methods unable to handle massive
graphs with millions of nodes. To overcome these dilemmas, we propose a
Provable and Scalable Motif Conductance algorithm PSMC, which has a fixed and
motif-independent approximation ratio for any motif. Specifically, PSMC first
defines a new vertex metric Motif Resident based on the given motif, which can
be computed locally. Then, it iteratively deletes the vertex with the smallest
motif resident value very efficiently using novel dynamic update technologies.
Finally, it outputs the locally optimal result during the above iterative
process. To further boost efficiency, we propose several effective bounds to
estimate the motif resident value of each vertex, which can greatly reduce
computational costs. Empirical results show that our proposed algorithms
achieve 3.2-32 times speedup and improve the quality by at least 12 times than
the baselines.
