Diffusion is a fundamental graph process and has been a basic building block in the study of graph clustering and graph learning tasks such as node classification . In this paper, we initiate the study of computationally efficient diffusion primitives beyond random walk. We provide an O(m)-time randomized algorithm for the \ell_2-norm flow diffusion problem, obtaining the approximation factor of 1+1/\mathrm{poly local cut structure, we give an alternative approach for finding locally-biased low conductance cuts . It is done simply by sweeping over the dual solution vector. This algorithm demonstrates a novel way of dealing with inequality constraints in graph optimization problems. It adapts the high-level algorithmic framework of  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.
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 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.
R
process
procedure
R
the study of graph clustering and graph learning tasks such as node classification
a wide range of theoretical and empirical applications such as graph partitioning and semi-supervised learning on graphs
R
initiate the study of
study
R
provide
design
R
obtaining the approximation factor of 1+1/\mathrm{poly
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
R
we give
our algorithm gives
R
locally-biased low conductance cuts . It is done simply by sweeping over the dual solution vector. This algorithm demonstrates
such cuts in nearly linear time. From a technical point of view, our algorithm contributes
A
nearly linear time