Local Higher-Order Graph Clustering

KDD : Proceedings
Hao YinDavid F Gleich

Abstract

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 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 ...Continue Reading

Citations

Aug 22, 2020·Big Data·Mandana SaebiNitesh V Chawla
Sep 12, 2018·BMC Bioinformatics·Danilo DessìDennis Shasha
Jun 12, 2019·Scientific Reports·Zhe LiTao Zhou
Sep 9, 2020·Scientific Reports·Irene MalvestioNaoki Masuda
May 14, 2020·Proceedings. Mathematical, Physical, and Engineering Sciences·Francesca ArrigoFrancesco Tudisco
Dec 29, 2020·PloS One·Rania Ibrahim, David F Gleich
Nov 6, 2020·Molecular & Cellular Proteomics : MCP·R Greg StaceyLeonard J Foster
Nov 17, 2020·Machine Learning·Blaž ŠkrljNada Lavrač
Jan 19, 2021·Social Network Analysis and Mining·Pawan Kumar, Adwitiya Sinha
Feb 17, 2021·Molecular & Cellular Proteomics : MCP·R Greg StaceyLeonard J Foster
Mar 11, 2019·PeerJ. Computer Science·Yufan FengZhaolong Ning
Jun 3, 2021··Konstantin ProkopchikFrancesco Tudisco
Jun 3, 2021··Jingrui He, Yikun Ban
Jul 19, 2018··Ruiyue PengLei Ying
Jul 19, 2018··Jon KleinbergDavid Parkes
Jul 19, 2018··Andrew TomkinsAustin R. Benson
Mar 11, 2019··Jure LeskovecAustin R. Benson
Aug 20, 2020··Yuchen BianYaowei Yan
Aug 20, 2020··Austin R. BensonJon Kleinberg
Jan 15, 2020··Dave BrainesDon Towsley
May 13, 2019··Austin BensonJon Kleinberg
May 13, 2019··Anthony WirthDavid Gleich
May 13, 2019··Benjamin RicaudNicolas Aspert
Nov 18, 2019··Kai YanWeiwei Cui
Aug 4, 2017··Jure LeskovecDavid F. Gleich

❮ Previous
Next ❯

Related Concepts

Related Feeds

Cardiac Conduction System

The cardiac conduction system is a specialized tract of myocardial cells responsible for maintaining normal cardiac rhythm. Discover the latest research on the cardiac conduction system here.