Local Hypergraph Clustering using Capacity Releasing Diffusion
arXiv:2003.04213 · doi:10.1371/journal.pone.0243485
Abstract
Local graph clustering is an important machine learning task that aims to find a well-connected cluster near a set of seed nodes. Recent results have revealed that incorporating higher order information significantly enhances the results of graph clustering techniques. The majority of existing research in this area focuses on spectral graph theory-based techniques. However, an alternative perspective on local graph clustering arises from using max-flow and min-cut on the objectives, which offer distinctly different guarantees. For instance, a new method called capacity releasing diffusion (CRD) was recently proposed and shown to preserve local structure around the seeds better than spectral methods. The method was also the first local clustering technique that is not subject to the quadratic Cheeger inequality by assuming a good cluster near the seed nodes. In this paper, we propose a local hypergraph clustering technique called hypergraph CRD (HG-CRD) by extending the CRD process to cluster based on higher order patterns, encoded as hyperedges of a hypergraph. Moreover, we theoretically show that HG-CRD gives results about a quantity called motif conductance, rather than a biased version used in previous experiments. Experimental results on synthetic datasets and real world graphs show that HG-CRD enhances the clustering quality.
arXiv comment18 pages, 6 figures
References in corpus (11)
- Benchmark graphs for testing community detection algorithms
- Higher-order organization of complex networks
- Finding local community structure in networks
- Simplicial Closure and higher-order link prediction
- Inhomogeneous Hypergraph Clustering with Applications
- The Total Variation on Hypergraphs - Learning on Hypergraphs Revisited
- Flow-Based Algorithms for Local Graph Clustering
- Capacity Releasing Diffusion for Speed and Locality
- A Simple and Strongly-Local Flow-Based Method for Cut Improvement
- Hypergraph Cuts with General Splitting Functions
- Revisiting Decomposable Submodular Function Minimization with Incidence Relations