CSE Colloquium: Di Wang

Speaker: Di Wang

Date: Tuesday, May 14

Time: 11-12pm

Location: HBL 1947 room

Title: Graph Partitioning via Local Flow Methods

Abstract: Graph partitioning is a fundamental problem in combinatorial optimization, and also has great practical impacts. With the abundance of massive graphs emerging from real-world applications, we want to design simple and robust methods that are very efficient.

We study the problem of local graph clustering, where given a seed node $s$, we want to find a good cluster $C$ containing $s$ (if there exists one) in time proportional to the size of the output cluster $C$. In particular, our notion of a good cluster is a subset of vertices that are well connected to each other, while sparsely connected to the rest of the graph. Local clustering arises broadly in challenges from data mining and machine learning, and is closely related to the classical problem of finding sparse cut in graphs. While network ?ow and probability mass diffusion (or more generally, spectral methods) have a long history of competing to provide good graph decomposition, local methods are predominantly based on diffusion. We design the ?rst primarily ?ow-based local method for locating low conductance cuts, and it has exhibited improved theoretical and empirical behavior over classical di?usion methods, e.g. PageRank.

More generally, the approach of using flow as a primitive to explore local bottleneck structure has found applications in broader contexts such as expander decomposition and global minimum cut. This suggests that local flow methods have the potential to become a building block in the design of fast graph algorithms.