Local graph clustering methods aim to nd a cluster of nodes by exploring a small region of the graph. ese methods are a ractive because they enable targeted clustering around a given seed node and are faster than traditional global graph clustering methods because their runtime does not depend on the size of the input graph. However, current local graph partitioning methods are not designed to account for the higher-order structures crucial to the network, nor can they e ectively handle directed networks. Here we introduce a new class of local graph clustering methods that address these issues by incorporating higher-order network information captured by small subgraphs, also called network motifs. We develop the Motif-based Approximate Personalized PageRank (MAPPR) algorithm that nds clusters containing a seed node with minimal motif conductance, a generalization of the conductance metric for network motifs. We generalize existing theory to prove the fast running time (independent of the size of the graph) and obtain theoretical guarantees on the cluster quality (in terms of motif conductance). We also develop a theory of node neighborhoods for nding sets that have small motif conductance, and apply these results to the case of nding good seed nodes to use as input to the MAPPR algorithm. Experimental validation on community detection tasks in both synthetic and real-world networks, shows that our new framework MAPPR outperforms the current edge-based personalized PageRank methodology.
Some local graph clustering methods have been investigated by incorporating high-order network information captured by small subgraphs REF Lee, Gharan & Trevisan, 2014; Li et al., 2017b) .
Local Higher-Order Graph Clustering
KDD '17
Computer Science Medicine