Local Graph Clustering

Targeted Pandemic Containment Through Identifying Local Contact Network Bottlenecks

Decision-making about pandemic mitigation often relies upon mathematical modelling. Models of contact networks are increasingly used for these purposes, and are often appropriate for infections that spread from person to person. Real-world human …

p-Norm Flow Diffusion for Local Graph Clustering

Local graph clustering and the closely related seed set expansion problem are primitives on graphs that are central to a wide range of analytic and learning tasks such as local clustering, community detection, nodes ranking and feature inference. …

Flow-based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance

Clustering points in a vector space or nodes in a graph is a ubiquitous primitive in statistical data analysis, and it is commonly used for exploratory data analysis. In practice, it is often of interest to refine or improve a given cluster that has …

Statistical Guarantees for Local Graph Clustering

Local graph clustering methods aim to find small clusters in very large graphs. These methods take as input a graph and a seed node, and they return as output a good cluster in a running time that depends on the size of the output cluster but that is …

Locality And Structure Aware Graph Node Embedding

In this work we propose Lasagne, a methodology to learn locality and structure aware graph node embeddings in an unsupervised way. In particular, we show that the performance of existing random-walk based approaches depends strongly on the structural …

Variational Perspective on Local Graph Clustering

Modern graph clustering applications require the analysis of large graphs and this can be computationally expensive. In this regard, local spectral graph clustering methods aim to identify well-connected clusters around a given 'seed set' of …

Capacity Releasing Diffusion for Speed and Locality

Diffusions and related random walk procedures are of central importance in many areas of machine learning, data analysis, and applied mathematics. Because they spread mass agnostically at each step in an iterative manner, they can sometimes spread …

An Optimization Approach to Locally-Biased Graph Algorithms

Locally-biased graph algorithms are algorithms that attempt to find local or small-scale structure in a large data graph. In some cases, this can be accomplished by adding some sort of locality constraint and calling a traditional graph algorithm; …

Parallel Local Graph Clustering

Graph clustering has many important applications in computing, but due to growing sizes of graph, even traditionally fast clustering methods such as spectral partitioning can be computationally expensive for real-world graphs of interest. Motivated …