# Graph Clustering using Effective Resistance

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Nov 2017.

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

- [Understanding Oversquashing in GNNs through the Lens of Effective Resistance](https://mlsanity.com/paper/2302.06835/) (2023)
- [DiffWire: Inductive Graph Rewiring via the Lov'asz Bound](https://mlsanity.com/paper/2206.07369/) (2022)
- [Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence](https://mlsanity.com/paper/2204.02570/) (2022)
- [Local Algorithms for Estimating Effective Resistance](https://mlsanity.com/paper/2106.03476/) (2021)
- [HyperEF: Spectral Hypergraph Coarsening by Effective-Resistance Clustering](https://mlsanity.com/paper/2210.14813/) (2022)
- [The Structural Complexity of Matrix-Vector Multiplication](https://mlsanity.com/paper/2502.21240/) (2025)
- [Multi-class Graph Clustering via Approximated Effective p-Resistance](https://mlsanity.com/paper/2306.08617/) (2023)
- [Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach](https://mlsanity.com/paper/2509.05129/) (2025)
- [Biharmonic Distance of Graphs and its Higher-Order Variants: Theoretical Properties with Applications to Centrality and Clustering](https://mlsanity.com/paper/2406.07574/) (2024)
- [SGM-PINN: Sampling Graphical Models for Faster Training of Physics-Informed Neural Networks](https://mlsanity.com/paper/2407.07358/) (2024)
- [SHyPar: A Spectral Coarsening Approach to Hypergraph Partitioning](https://mlsanity.com/paper/2410.10875/) (2024)
- [Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs](https://mlsanity.com/paper/2601.11159/) (2026)

## Abstract (arXiv)

 defvecc#1boldsymbol#1 We design a polynomial time algorithm that for any weighted undirected graph G = (V, E,vecc w) and sufficiently large δ > 1, partitions V into subsets V1, ldots, Vh for some h≥ 1, such that bullet at most δ-1 fraction of the weights are between clusters, i.e. [ w(E - cupi = 1h E(Vi)) lesssim fracw(E)δ;] bullet the effective resistance diameter of each of the induced subgraphs G[Vi] is at most δ3 times the average weighted degree, i.e. [ maxu, v ∈ Vi mathsfReffG[Vi](u, v) lesssim δ3 · frac|V|w(E) quad  for all  i=1, ldots, h.] In particular, it is possible to remove one percent of weight of edges of any given graph such that each of the resulting connected components has effective resistance diameter at most the inverse of the average weighted degree. Our proof is based on a new connection between effective resistance and low conductance sets. We show that if the effective resistance between two vertices u and v is large, then there must be a low conductance cut separating u from v. This implies that very mildly expanding graphs have constant effective resistance diameter. We believe that this connection could be of independent interest in algorithm design.