# CHIEF: Clustering with Higher-order Motifs in Big Networks

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 50 references that are in the map.
- First posted on arXiv 6 Apr 2022.

## Builds on (most cited first, 8 of 8)

- [Higher-order organization of complex networks](https://mlsanity.com/paper/1612.08447/) (2016)
- [Scalable motif-aware graph clustering](https://mlsanity.com/paper/1606.06235/) (2016)
- [EdMot: An Edge Enhancement Approach for Motif-aware Community Detection](https://mlsanity.com/paper/1906.04560/) (2019)
- [The Four Dimensions of Social Network Analysis: An Overview of Research Methods, Applications, and Software Tools](https://mlsanity.com/paper/2002.09485/) (2020)
- [Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks](https://mlsanity.com/paper/1403.3795/) (2014)
- [Motif Clustering and Overlapping Clustering for Social Network Analysis](https://mlsanity.com/paper/1612.00895/) (2016)
- [Big Networks: A Survey](https://mlsanity.com/paper/2008.03638/) (2020)
- [Hierarchical Clustering for Smart Meter Electricity Loads based on Quantile Autocovariances](https://mlsanity.com/paper/1911.03336/) (2019)

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

- [Graph Transformers: A Survey](https://mlsanity.com/paper/2407.09777/) (2024)
- [Quantum Graph Learning: Frontiers and Outlook](https://mlsanity.com/paper/2302.00892/) (2023)
- [Collaborative Team Recognition: A Core Plus Extension Structure](https://mlsanity.com/paper/2406.06617/) (2024)

## Abstract (arXiv)

Clustering a group of vertices in networks facilitates applications across different domains, such as social computing and Internet of Things. However, challenges arises for clustering networks with increased scale. This paper proposes a solution which consists of two motif clustering techniques: standard acceleration CHIEF-ST and approximate acceleration CHIEF-AP. Both algorithms first find the maximal k-edge-connected subgraphs within the target networks to lower the network scale, then employ higher-order motifs in clustering. In the first procedure, we propose to lower the network scale by optimizing the network structure with maximal k-edge-connected subgraphs. For CHIEF-ST, we illustrate that all target motifs will be kept after this procedure when the minimum node degree of the target motif is equal or greater than k. For CHIEF-AP, we prove that the eigenvalues of the adjacency matrix and the Laplacian matrix are relatively stable after this step. That is, CHIEF-ST has no influence on motif clustering, whereas CHIEF-AP introduces limited yet acceptable impact. In the second procedure, we employ higher-order motifs, i.e., heterogeneous four-node motifs clustering in higher-order dense networks. The contributions of CHIEF are two-fold: (1) improved efficiency of motif clustering for big networks; (2) verification of higher-order motif significance. The proposed solutions are found to outperform baseline approaches according to experiments on real and synthetic networks, which demonstrates CHIEF's strength in large network analysis. Meanwhile, higher-order motifs are proved to perform better than traditional triangle motifs in clustering.