# Scalable motif-aware graph clustering

arXiv: https://arxiv.org/abs/1606.06235 · HTML: https://mlsanity.com/paper/1606.06235/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jun 2016.

## Built on by (most cited first, 15 of 15)

- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [Equivariant Hypergraph Diffusion Neural Operators](https://mlsanity.com/paper/2207.06680/) (2022)
- [Higher-order Clustering and Pooling for Graph Neural Networks](https://mlsanity.com/paper/2209.03473/) (2022)
- [Generative Graph Pattern Machine](https://mlsanity.com/paper/2505.16130/) (2025)
- [Scalable Community Detection via Parallel Correlation Clustering](https://mlsanity.com/paper/2108.01731/) (2021)
- [HC-GLAD: Dual Hyperbolic Contrastive Learning for Unsupervised Graph-Level Anomaly Detection](https://mlsanity.com/paper/2407.02057/) (2024)
- [DeSCo: Towards Generalizable and Scalable Deep Subgraph Counting](https://mlsanity.com/paper/2308.08198/) (2023)
- [CHIEF: Clustering with Higher-order Motifs in Big Networks](https://mlsanity.com/paper/2204.02656/) (2022)
- [On the Role of Edge Dependency in Graph Generative Models](https://mlsanity.com/paper/2312.03691/) (2023)
- [Community Recovery in the Geometric Block Model](https://mlsanity.com/paper/2206.11303/) (2022)
- [Clustering with Simplicial Complexes](https://mlsanity.com/paper/2303.07646/) (2023)
- [Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts](https://mlsanity.com/paper/2507.14835/) (2025)
- [DeHIN: A Decentralized Framework for Embedding Large-scale Heterogeneous Information Networks](https://mlsanity.com/paper/2201.02757/) (2022)
- [Multi-order Graph Clustering with Adaptive Node-level Weight Learning](https://mlsanity.com/paper/2405.12183/) (2024)
- [The ParClusterers Benchmark Suite (PCBS): A Fine-Grained Analysis of Scalable Graph Clustering](https://mlsanity.com/paper/2411.10290/) (2024)

## Abstract (arXiv)

We develop new methods based on graph motifs for graph clustering, allowing more efficient detection of communities within networks. We focus on triangles within graphs, but our techniques extend to other clique motifs as well. Our intuition, which has been suggested but not formalized similarly in previous works, is that triangles are a better signature of community than edges. We therefore generalize the notion of conductance for a graph to em triangle conductance, where the edges are weighted according to the number of triangles containing the edge. This methodology allows us to develop variations of several existing clustering techniques, including spectral clustering, that minimize triangles split by the cluster instead of edges cut by the cluster. We provide theoretical results in a planted partition model to demonstrate the potential for triangle conductance in clustering problems. We then show experimentally the effectiveness of our methods to multiple applications in machine learning and graph mining.