Algorithms & Randomness Center (ARC)
Di Wang (UC Berkeley/Georgia Tech)
Monday, February 5, 2018
Klaus 1116 East - 11:00 am
Title: Capacity Releasing Diffusion for Speed and Locality
Abstract: Diffusion and related random walk procedures on graphs are of central importance in many areas of machine learning, data analysis, and algorithm design. Because they spread mass agnostically at each step in an iterative manner, they can sometimes spread mass “too aggressively,” thereby failing to find the “right” clusters. We introduce a novel Capacity Releasing Diffusion (CRD) Process, which is both faster and stays more local than the classical probability mass diffusion.
The CRD Process follows a carefully-constructed push-relabel rule, using techniques that are well-known from flow-based graph algorithms. While 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. Our CRD Process is 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.
--------------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
