# Computing Heat Kernel Pagerank and a Local Clustering Algorithm

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Mar 2015.

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

- [Local Clustering on Complex Graphs and Complex Hypergraphs](https://mlsanity.com/paper/2412.03008/) (2024)
- [A Poincar'e Inequality and Consistency Results for Signal Sampling on Large Graphs](https://mlsanity.com/paper/2311.10610/) (2023)
- [Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach](https://mlsanity.com/paper/2412.10789/) (2024)

## Abstract (arXiv)

Heat kernel pagerank is a variation of Personalized PageRank given in an exponential formulation. In this work, we present a sublinear time algorithm for approximating the heat kernel pagerank of a graph. The algorithm works by simulating random walks of bounded length and runs in time Obig(fraclog(ε-1)log nε3loglog(ε-1)big), assuming performing a random walk step and sampling from a distribution with bounded support take constant time. The quantitative ranking of vertices obtained with heat kernel pagerank can be used for local clustering algorithms. We present an efficient local clustering algorithm that finds cuts by performing a sweep over a heat kernel pagerank vector, using the heat kernel pagerank approximation algorithm as a subroutine. Specifically, we show that for a subset S of Cheeger ratio φ, many vertices in S may serve as seeds for a heat kernel pagerank vector which will find a cut of conductance O(√φ).