# ℓ2-norm Flow Diffusion in Near-Linear Time

arXiv: https://arxiv.org/abs/2105.14629 · HTML: https://mlsanity.com/paper/2105.14629/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 76 references that are in the map.
- First posted on arXiv 30 May 2021.

## Builds on (most cited first, 26 of 26)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Combining Label Propagation and Simple Models Out-performs Graph Neural Networks](https://mlsanity.com/paper/2010.13993/) (2020)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple](https://mlsanity.com/paper/1605.02353/) (2016)
- [An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations](https://mlsanity.com/paper/1304.2338/) (2013)
- [p-Norm Flow Diffusion for Local Graph Clustering](https://mlsanity.com/paper/2005.09810/) (2020)
- [Capacity Releasing Diffusion for Speed and Locality](https://mlsanity.com/paper/1706.05826/) (2017)
- [Flow-Based Algorithms for Local Graph Clustering](https://mlsanity.com/paper/1307.2855/) (2013)
- [Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks](https://mlsanity.com/paper/1403.3795/) (2014)
- [Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers](https://mlsanity.com/paper/2011.08806/) (2020)
- [Strongly local p-norm-cut algorithms for semi-supervised learning and local graph clustering](https://mlsanity.com/paper/2006.08569/) (2020)
- [Nearly Maximum Flows in Nearly Linear Time](https://mlsanity.com/paper/1304.2077/) (2013)
- [Expander Decomposition and Pruning: Faster, Stronger, and Simpler](https://mlsanity.com/paper/1812.08958/) (2018)
- [Flows in Almost Linear Time via Adaptive Preconditioning](https://mlsanity.com/paper/1906.10340/) (2019)
- [Faster p-norm minimizing flows, via smoothed q-norm problems](https://mlsanity.com/paper/1910.10571/) (2019)
- [Bootstrapped Graph Diffusions: Exposing the Power of Nonlinearity](https://mlsanity.com/paper/1703.02618/) (2017)
- [A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond](https://mlsanity.com/paper/1910.08025/) (2019)
- [Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators](https://mlsanity.com/paper/1911.01956/) (2019)
- [Deterministic Edge Connectivity in Near-Linear Time](https://mlsanity.com/paper/1411.5123/) (2014)
- [Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time](https://mlsanity.com/paper/1708.03962/) (2017)
- [Faster Parallel Algorithm for Approximate Shortest Path](https://mlsanity.com/paper/1911.01626/) (2019)
- [Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs](https://mlsanity.com/paper/2003.04863/) (2020)
- [Almost-linear-time Weighted ℓp-norm Solvers in Slightly Dense Graphs via Sparsification](https://mlsanity.com/paper/2102.06977/) (2021)

## Abstract (arXiv)

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 widetildeO(m)-time randomized algorithm for the ℓ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.