# Motif Clustering and Overlapping Clustering for Social Network Analysis

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Dec 2016.

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

- [You are AllSet: A Multiset Function Framework for Hypergraph Neural Networks](https://mlsanity.com/paper/2106.13264/) (2021)
- [Equivariant Hypergraph Diffusion Neural Operators](https://mlsanity.com/paper/2207.06680/) (2022)
- [Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernels](https://mlsanity.com/paper/2104.02995/) (2021)
- [A Rapid Review of Clustering Algorithms](https://mlsanity.com/paper/2401.07389/) (2024)
- [CHIEF: Clustering with Higher-order Motifs in Big Networks](https://mlsanity.com/paper/2204.02656/) (2022)
- [BoBa: Boosting Backdoor Detection through Data Distribution Inference in Federated Learning](https://mlsanity.com/paper/2407.09658/) (2024)
- [Multi-order Graph Clustering with Adaptive Node-level Weight Learning](https://mlsanity.com/paper/2405.12183/) (2024)
- [Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach](https://mlsanity.com/paper/2505.18043/) (2025)

## Abstract (arXiv)

Motivated by applications in social network community analysis, we introduce a new clustering paradigm termed motif clustering. Unlike classical clustering, motif clustering aims to minimize the number of clustering errors associated with both edges and certain higher order graph structures (motifs) that represent "atomic units" of social organizations. Our contributions are two-fold: We first introduce motif correlation clustering, in which the goal is to agnostically partition the vertices of a weighted complete graph so that certain predetermined "important" social subgraphs mostly lie within the same cluster, while "less relevant" social subgraphs are allowed to lie across clusters. We then proceed to introduce the notion of motif covers, in which the goal is to cover the vertices of motifs via the smallest number of (near) cliques in the graph. Motif cover algorithms provide a natural solution for overlapping clustering and they also play an important role in latent feature inference of networks. For both motif correlation clustering and its extension introduced via the covering problem, we provide hardness results, algorithmic solutions and community detection results for two well-studied social networks.