# Variational Perspective on Local Graph Clustering

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Feb 2016.

## Built on by (most cited first, 14 of 14)

- [Residual2Vec: Debiasing graph embedding with random graphs](https://mlsanity.com/paper/2110.07654/) (2021)
- [DPAR: Decoupled Graph Neural Networks with Node-Level Differential Privacy](https://mlsanity.com/paper/2210.04442/) (2022)
- [Local Hyper-Flow Diffusion](https://mlsanity.com/paper/2102.07945/) (2021)
- [Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval Guarantees](https://mlsanity.com/paper/2605.18775/) (2026)
- [Local Clustering on Complex Graphs and Complex Hypergraphs](https://mlsanity.com/paper/2412.03008/) (2024)
- [Graph-based Semi-supervised Local Clustering with Few Labeled Nodes](https://mlsanity.com/paper/2211.11114/) (2022)
- [Fast Online Node Labeling for Very Large Graphs](https://mlsanity.com/paper/2305.16257/) (2023)
- [Local Graph Clustering with Noisy Labels](https://mlsanity.com/paper/2310.08031/) (2023)
- [Fast and Robust Contextual Node Representation Learning over Dynamic Graphs](https://mlsanity.com/paper/2411.07123/) (2024)
- [FairRARI: A Plug and Play Framework for Fairness-Aware PageRank](https://mlsanity.com/paper/2602.08589/) (2026)
- [Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints](https://mlsanity.com/paper/2212.11143/) (2022)
- [Fast online node labeling with graph subsampling](https://mlsanity.com/paper/2503.16755/) (2025)
- [Accelerated Evolving Set Processes for Local PageRank Computation](https://mlsanity.com/paper/2510.08010/) (2025)
- [Complexity of Classical Acceleration for ℓ1-Regularized PageRank](https://mlsanity.com/paper/2602.21138/) (2026)

## Abstract (arXiv)

Modern graph clustering applications require the analysis of large graphs and this can be computationally expensive. In this regard, local spectral graph clustering methods aim to identify well-connected clusters around a given "seed set" of reference nodes without accessing the entire graph. The celebrated Approximate Personalized PageRank (APPR) algorithm in the seminal paper by Andersen et al. is one such method. APPR was introduced and motivated purely from an algorithmic perspective. In other words, there is no a priori notion of objective function/optimality conditions that characterizes the steps taken by APPR. Here, we derive a novel variational formulation which makes explicit the actual optimization problem solved by APPR. In doing so, we draw connections between the local spectral algorithm of and an iterative shrinkage-thresholding algorithm (ISTA). In particular, we show that, appropriately initialized ISTA applied to our variational formulation can recover the sought-after local cluster in a time that only depends on the number of non-zeros of the optimal solution instead of the entire graph. In the process, we show that an optimization algorithm which apparently requires accessing the entire graph, can be made to behave in a completely local manner by accessing only a small number of nodes. This viewpoint builds a bridge across two seemingly disjoint fields of graph processing and numerical optimization, and it allows one to leverage well-studied, numerically robust, and efficient optimization algorithms for processing today's large graphs.