  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. Using a known connection between the optimal dual solution of the flow
diffusion problem and the local cut structure, our algorithm gives an
alternative approach for finding such cuts in nearly linear time.
  From a technical point of view, our algorithm contributes a novel way of
dealing with inequality constraints in graph optimization problems. It adapts
the high-level algorithmic framework of nearly linear time Laplacian system
solvers, but requires several new tools: vertex elimination under constraints,
a new family of graph ultra-sparsifiers, and accelerated proximal gradient
methods with inexact proximal mapping computation.

Data Structures and Algorithms;Machine Learning