Local Motif Clustering via (Hyper)Graph Partitioning
This work addresses the problem of efficiently extracting well-characterized communities based on motifs for graph analysis, representing an incremental improvement over existing methods.
The paper tackles local motif clustering by building hypergraph and graph models to represent motif distributions around seed nodes, and solves them using combinatorial (hyper)graph partitioning algorithms. In experiments with triangle motifs, their algorithm achieves communities with motif conductance one-third lower on average than the state-of-the-art MAPPR tool while being 6.3 times faster on average.
A widely-used operation on graphs is local clustering, i.e., extracting a well-characterized community around a seed node without the need to process the whole graph. Recently local motif clustering has been proposed: it looks for a local cluster based on the distribution of motifs. Since this local clustering perspective is relatively new, most approaches proposed for it are extensions of statistical and numerical methods previously used for edge-based local clustering, while the available combinatorial approaches are still few and relatively simple. In this work, we build a hypergraph and a graph model which both represent the motif-distribution around the seed node. We solve these models using sophisticated combinatorial algorithms designed for (hyper)graph partitioning. In extensive experiments with the triangle motif, we observe that our algorithm computes communities with a motif conductance value being one third on average in comparison against the communities computed by the state-of-the-art tool MAPPR while being 6.3 times faster on average.