Theory Seminar
— 4:30pm
Location:
Traffic21 Classroom 6501
-
Gates Hillman Centers
Speaker:
DI WANG
,
Postdoctoral Researcher
https://dw236.github.io/
Graph Partitioning via Local Flow Methods
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 flow 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 first primarily flow-based local method for locating low conductance cuts, and it has exhibited improved theoretical and empirical behavior over classical diffusion 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.
Event Website:
http://theory.cs.cmu.edu/seminars/
For More Information:
eedavis@andrew.cmu.edu