Local Higher-Order Graph Clustering

By Hao Yin, Austin R. Benson, Jure Leskovec, David F. Gleich. Knowledge Discovery and Data Mining, 2017

696 citations recorded by the source corpus.

Local graph clustering methods aim to find a cluster of nodes by exploring a small region of the graph. These methods are attractive 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 effectively 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 finds clusters containing a seed node with minimal \emph{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 finding sets that have small motif conductance, and apply these results to the case of finding 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.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/f2ab3c4e6fae8e666cc68ba1b5672dfddea71123

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications (2019, methodology): “For our experiments, we use the EU Email Core network, a directed graph generated using email data from a large European research institution [Yin et al., 2017, Leskovec et al., 2007].”
Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning (2020, background): “[55] H.”
Combining Label Propagation and Simple Models Out-performs Graph Neural Networks (2020, methodology): “Finally, we use an email dataset of a European research institute, where classes are department membership and there are no features (Leskovec et al., 2007; Yin et al., 2017).”
Networks beyond pairwise interactions: structure and dynamics (2020, background): “In this case too, the clustering coefficient is then defined as the fraction of k-paths of length k that are part of a k + 1-clique [115].”
A Comprehensive Survey on Community Detection With Deep Learning (2021, background): “With the advancement of high-order relationship representations [173], we believe deep learning models can facilitate the development of hierarchical community detection.”