For a graph $G$ with $n$ vertices and $m$ edges, a $(\phi,\epsilon)$‑expander decomposition partitions the vertex set into $V_1,\dots,V_k$ such that each induced subgraph $G[V_i]$ satisfies $\Phi(G[V_i])\ge\phi$ and the number of inter‑cluster edges is at most $O(\epsilon m)$. This structure is pivotal in many graph algorithms.
[Agassy, Dorman, Kaplan, ICALP 2023] (referred to as ADK) presented a randomized $\tilde O(m)$‑time algorithm that computes a $(\phi,\phi\log^2 n)$‑expander decomposition. This paper extends the result to a more general notion of expansion. Let $\mu\in\mathbb R_{\ge0}^n$ be a vertex measure; the $\mu$‑expansion of a cut $(S,\overline S)$ is defined as $$ \PhiG^{\mu}(S,\overline S)=\frac{|E(S,\overline S)|}{\min{\mu(S),\mu(\overline S)}},\qquad \mu(S)=\sum{v\in S}\mu(v). $$ We devise a randomized $\tilde O(m)$‑time algorithm that yields a $(\phi,\phi\log^2 n\cdot\frac{\mu(V)}{m})$‑expander decomposition with respect to $\mu$‑expansion.
Most of the exposition follows the ADK framework, making this work a convenient reference for generalized expander decomposition.
Review: The paper lifts the classic uniform conductance notion to arbitrary vertex weights, providing an efficient tool for graph partitioning under non‑uniform measures.