$\ell_2$-norm Flow Diffusion in Near-Linear Time

Understand

Diffusion is a fundamental graph procedure and has been a basic building block in a wide range of theoretical and empirical applications such as graph partitioning and semi-supervised learning on graphs.

• In this paper, we study computationally efficient diffusion primitives beyond random walk.
• We design an $\widetilde{O}(m)$-time randomized algorithm for the $\ell_2$-norm flow diffusion problem, a recently proposed diffusion model based on network flow with demonstrated graph clustering related applications both in theory and in practice.
• Examples include finding locally-biased low conductance cuts.