在一张含 $n$ 个顶点、$m$ 条边的图 $G$ 上，$(\phi,\epsilon)$‑扩展子图分解指将顶点集合划分为 $V_1,\dots,V_k$，使得每个子图 $G[V_i]$ 的导电率满足 $\Phi(G[V_i])\ge\phi$，且跨簇边的数量至多 $O(\epsilon m)$。该结构在众多图算法中扮演核心角色。
[Agassy, Dorman, Kaplan, ICALP 2023]（以下简称 ADK）给出了一种随机 $\tilde O(m)$ 时间算法，能够构造 $(\phi,\phi\log^2 n)$‑扩展子图分解。本文在此基础上推广到更一般的扩展度量。设 $\mu\in\mathbb R_{\ge0}^n$ 为顶点度量，切分 $(S,\overline S)$ 的 $\mu$‑扩展定义为 $$ \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). $$ 我们设计了一个随机 $\tilde O(m)$ 时间算法，能够得到相对于 $\mu$‑扩展的 $(\phi,\phi\log^2 n\cdot\frac{\mu(V)}{m})$‑扩展子图分解。
本文的大部分叙述沿袭 ADK 的框架，因而可视为对广义扩展子图分解的便捷参考。
点评：该工作把经典的均匀导电率概念扩展到任意顶点权重，为后续基于非均匀度量的图划分提供了高效工具。