CSE Colloquium: 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 flow and probability massdiffusion (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.

Biography: Di Wang is a postdoc at Georgia Tech, hosted by Yang (Richard) Peng. He obtained his PhD in computer science from UC Berkeley under the advisement of Satish Rao. He spent Fall 2017 as the Simons- Berkeley Research Fellow at the Simons Institute program on optimization. He is broadly interested in theoretical computer science and optimization, particularly in graph algorithms and convex optimization.

 

Share this event:

facebook linked in twitter email

Media Contact: Antonio Blanca

 
 

About

The School of Electrical Engineering and Computer Science was created in the spring of 2015 to allow greater access to courses offered by both departments for undergraduate and graduate students in exciting collaborative research in fields.

We offer B.S. degrees in electrical engineering, computer science, computer engineering and data science and graduate degrees (master's degrees and Ph.D.'s) in electrical engineering and computer science and engineering. EECS focuses on the convergence of technologies and disciplines to meet today’s industrial demands.

School of Electrical Engineering and Computer Science

The Pennsylvania State University

207 Electrical Engineering West

University Park, PA 16802

814-863-6740

Department of Computer Science and Engineering

814-865-9505

Department of Electrical Engineering

814-865-7667