# Multi-class Graph Clustering via Approximated Effective p-Resistance

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 62 references that are in the map.
- First posted on arXiv 14 Jun 2023.

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

- [Poisson Learning: Graph Based Semi-Supervised Learning At Very Low Label Rates](https://mlsanity.com/paper/2006.11184/) (2020)
- [Analysis of p-Laplacian Regularization in Semi-Supervised Learning](https://mlsanity.com/paper/1707.06213/) (2017)
- [The Total Variation on Hypergraphs - Learning on Hypergraphs Revisited](https://mlsanity.com/paper/1312.5179/) (2013)
- [p-Norm Flow Diffusion for Local Graph Clustering](https://mlsanity.com/paper/2005.09810/) (2020)
- [Graph Clustering using Effective Resistance](https://mlsanity.com/paper/1711.06530/) (2017)
- [Hypergraph p-Laplacian: A Differential Geometry View](https://mlsanity.com/paper/1711.08171/) (2017)
- [Flow-Based Local Graph Clustering with Better Seed Set Inclusion](https://mlsanity.com/paper/1811.12280/) (2018)
- [Strongly local p-norm-cut algorithms for semi-supervised learning and local graph clustering](https://mlsanity.com/paper/2006.08569/) (2020)
- [Community detection in networks via nonlinear modularity eigenvectors](https://mlsanity.com/paper/1708.05569/) (2017)
- [Multiway p-spectral graph cuts on Grassmann manifolds](https://mlsanity.com/paper/2008.13210/) (2020)

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

- [Bandits with Abstention under Expert Advice](https://mlsanity.com/paper/2402.14585/) (2024)
- [Fast online node labeling with graph subsampling](https://mlsanity.com/paper/2503.16755/) (2025)

## Abstract (arXiv)

This paper develops an approximation to the (effective) p-resistance and applies it to multi-class clustering. Spectral methods based on the graph Laplacian and its generalization to the graph p-Laplacian have been a backbone of non-euclidean clustering techniques. The advantage of the p-Laplacian is that the parameter p induces a controllable bias on cluster structure. The drawback of p-Laplacian eigenvector based methods is that the third and higher eigenvectors are difficult to compute. Thus, instead, we are motivated to use the p-resistance induced by the p-Laplacian for clustering. For p-resistance, small p biases towards clusters with high internal connectivity while large p biases towards clusters of small "extent," that is a preference for smaller shortest-path distances between vertices in the cluster. However, the p-resistance is expensive to compute. We overcome this by developing an approximation to the p-resistance. We prove upper and lower bounds on this approximation and observe that it is exact when the graph is a tree. We also provide theoretical justification for the use of p-resistance for clustering. Finally, we provide experiments comparing our approximated p-resistance clustering to other p-Laplacian based methods.