精读笔记
Problem Setting
论文处理的是 graph k-CUT 家族的统一启发式求解问题。这里的关键不是定义 k 个非空子集，而是九类 cut objective 在优化方向和平衡项上互相接近但又不完全兼容：Max-k-Cut 追求尽量多切边，Min-k-Cut 追求尽量少切边，Normalized/Cheeger/Ratio/Sparsest 又把 cut 与 volume/cardinality 绑定在一起。真正困难在于局部移动一个 vertex 后，不同目标的 objective delta 维护成本和搜索方向不同，导致已有强算法通常只适用于一个或少数 formulation。以前方法卡在两个地方：一是 Max-k-Cut、Cheeger cut、Ratio cut 等各自有专门 heuristic，但结构不能自然迁移；二是如果直接对复杂目标做 best-of-all move evaluation，代价会接近 O(k|V|) 级别，稀疏图上的局部性没有被充分利用。本文的关键矛盾是：如何同时保持跨目标的一般性和单目标强启发式的速度。
Motivation
作者的动机不是提出一个全新的 evolutionary algorithm，而是把 graph cut 变体重新组织成可以共享搜索信号的同一类问题。核心观察是：这些目标虽然形式不同，但都含 cut boundary，而且对 boundary 的偏好存在单调方向。MaxGCP 中优化目标本质上鼓励更大的 cut/boundary；MinGCP 中则鼓励更小的 cut/boundary。这个观察使得局部搜索不必完全依赖目标原式，而可以先沿 cut/boundary 的稳定增益方向找候选 move，再用真实目标筛选。关键缺口是：已有算法通常把每个 objective 当成独立问题，缺少一个“同类目标之间共享 landscape”的机制；而 Judicious、AntiCheeger 等问题尤其缺少高质量数值解，导致理论性质也难通过实验观察。
Core Idea
论文真正的核心是一个重编码：把九类 k-CUT 目标都视为 F(cut(boundary), volume, cardinality)，再按 boundary 单调性分成 MaxGCP 与 MinGCP。这个分类不是为了命名，而是给局部搜索提供统一 inductive bias：对 MaxGCP，优先搜索能扩大 cut/boundary 的 move；对 MinGCP，优先搜索能缩小 cut/boundary 的 move。这样，算法不需要为每个目标重新设计完整邻域结构，只需要维护少数稳定的 move-gain signal，再用目标函数做最终比较。
另一个核心思想是把相邻 cut objective 当作辅助 landscape。ACMH 在目标函数和同类辅助问题之间切换，实际上是在做 objective-level perturbation：当主目标陷入局部最优时，换一个相关但不同的目标继续搜索，再把对主目标有改善的解截获回来。它引入的 inductive bias 是：同一 MaxGCP 或 MinGCP 内的优质 partitions 往往共享部分结构，只是 balance preference 不同。相比 prior 的单问题 heuristic，这里改变的是信息流：搜索不再只沿一个 objective 的局部梯度走，而是在一族相邻 objective 的局部结构之间迁移。
Method
方法中真正必要的机制有三层。
第一，稳定增益矩阵。cut-stable matrix 维护单点移动对总 cut 的影响，boundary-stable matrix 维护单点移动对各 segment boundary 的影响。它解决的是复杂目标局部增益难以频繁重算的问题。核心变化是把搜索候选压缩到由 cut/boundary 增益极值诱导的 promising subset，而不是枚举全部 vertex-label move。
第二，MMH 的层次化 mutation。它不是普通 mutation，而是主搜索引擎：先做基于 best-of-part 的单点/双点局部搜索，再用 tabu 逃离局部最优，最后用强随机扰动重启远距离区域。这里的必要性在于，cross-over 只能继承结构，不能保证改善；真正提升 objective 的是 mutation 阶段的高强度 test-time compute。
第三，ACMH 的辅助目标切换。它解决的是单一 objective landscape 容易局部冻结的问题。辅助 cut 不是为了多任务学习，而是提供 alternative basin：用 Max-k-Cut 辅助 Judicious/AntiCheeger，用 Ratio/Cheeger2 等辅助 MinGCP 目标。核心变化是把 objective family 当作搜索空间的一部分。
第四，PEAF 的 population 机制。crossover 与 diversity selection 主要用于保留多个结构假设，避免所有搜索线程收敛到同一个 basin。这里的贡献更多是工程上把 strong local search 并行化并维持多样性，而不是单独形成新的组合优化理论。
Key Insight / Why It Works
最可能真正有效的部分是“稳定局部信号 + 强 test-time compute”。这篇论文的成功并不神秘：G-set 是稀疏图，单点移动影响局部邻域；如果能用 bucket-like 结构快速维护 cut/boundary gain，就可以在有限时间内做大量高质量局部搜索。这个机制比直接求解 MIP 更适合大规模稀疏图，也比目标特化的启发式更容易迁移。
ACMH 是第二个关键点。它本质上利用了 latent structure：同一类 graph cut objective 的高质量 partitions 往往重叠，只是对 balance 的惩罚不同。辅助目标搜索相当于在相邻 energy landscape 上做 escape，再把主目标改善截获。这比普通随机扰动更有方向性。尤其对 Judicious、AntiCheeger、Normalized、Cheeger、Sparsest 这类带 ratio/max/balance 项的目标，辅助目标提供了更平滑或更强的 cut signal。
PEAF 的 crossover/selection 是有用的，但我不认为它是最核心贡献。它更像 memory reuse 和 parallel multi-start：保留多个高质量分区结构，用 crossover 重组共享片段，用 diversity 避免过早收敛。真正的改进很可能来自 mutation budget 和局部搜索效率，而不是 evolutionary abstraction 本身。文中虽然做了 PEAF-MMH、ACMH、MMH、PEAF-ACMH 的对比，但没有足够细粒度地隔离并行度、search operations 数量、crossover 算子类型和 auxiliary objective 的贡献，增益来源不清。
这不是 retrieval 或 data coverage 型方法，而是典型的 engineered combinatorial search：better inductive bias 加 test-time compute。所谓 unified framework 的有效性来自问题族共享 boundary 单调性，而不是框架对任意 graph partitioning objective 都泛化。
Relation To Prior Work
这篇最接近的技术谱系是 Max-k-Cut 的 memetic/evolutionary/local-search heuristic，尤其是 MOH、scatter search、path relinking、tabu/VNS，以及 graph coloring/partitioning 中的 greedy partition crossover。很多模块并不新：结构继承 crossover、path relinking、tabu、强扰动、diversity selection 都是成熟启发式组件。
真正不同的地方有两个。第一，作者把这些组件从 Max-k-Cut 扩展到一组 cut objective，并给出 MaxGCP/MinGCP 分类，使得局部搜索候选可以由 cut/boundary 单调方向统一生成。第二，ACMH 把辅助 cut objective 系统化，用同类任务的 landscape 帮助主任务逃离局部最优。这比简单调参或多算子堆叠更有实质性。
看似新的 PEAF 不是本质突破；它是已有 evolutionary search 组件的强组合。实质创新更接近“跨 cut objective 的统一搜索语言”和“稳定增益矩阵驱动的目标无关候选生成”。如果要给它定位，它属于组合优化中 domain-specific metaheuristic 的一次统一化工程，而不是近似理论或全新算法范式。
Dataset / Evaluation
评估覆盖九类 k-CUT、k=2到5、G-set 35 个图，任务覆盖面在同一 benchmark 家族内很宽，足以支持“同一框架可跑多个 cut formulation”的 claim。和 Gurobi 的比较说明在给定时间预算下，PEAF-ACMH 对这些大规模稀疏实例更实用；这点是可信的。
但 evaluation 的外推性有限。所有主要结论都建立在 G-set 上，图分布相对固定，不能证明在社交网络、图像网格、动态图、有符号图、非整数权图或强约束 partition 上仍然成立。Gurobi 也不是这些 NP-hard 大规模 cut 变体的最强启发式 baseline；用 NoRel heuristic 和 MIP search 对比，更像证明通用 MIP 不适合这类大规模启发式 benchmark，而不是证明 PEAF 超越所有专门算法。
文中关于结构发现的实验，例如 Judicious 比 AntiCheeger 更平衡、Cheeger 比 Normalized 更平衡、Sparsest 比 Ratio 更平衡、Min-k-Cut 与 MinMax-k-Cut 解相似，比较有价值。但这些是 empirical structural evidence，不是严格理论结论。它们依赖高质量解的可信度，而不是直接证明。
Limitation
最大限制是归因不清。PEAF-ACMH 同时改变了 population、crossover、mutation、辅助目标、并行预算和搜索时间；虽然有四个变体比较，但不足以判断主要收益到底来自 auxiliary objective、更多 search operations，还是 population diversity。对 Max-k-Cut，ACMH 反而不如 MMH 的现象也说明辅助目标不是普适增益。
方法成立依赖一个强前提：目标必须能由 cut boundary、volume、cardinality 组合表达，并且相对于 boundary 有清晰单调方向。这个前提对文中九个目标成立，但不代表对更复杂的 graph partition objective 成立。若目标包含全局约束、非局部正则、节点属性、社区先验或动态约束，稳定增益矩阵可能无法低成本维护。
scalability 的上限也不是完全解决。bucket sorting 依赖整数正权和 bounded gain range；论文结尾提到非整数权、signed graph、constrained cuts 的扩展，但主要是 sketch，文中未充分说明这些扩展在精度、稳定性和复杂度上是否仍保留优势。
泛化也需要谨慎。这里的 unified 不是 learned generalization，而是 hand-crafted objective family generalization。它可以迁移到同构目标族，但不应被理解为对任意图优化任务的泛化能力。可能主要来自 scaling / engineering：更快的局部增益维护、更多并行搜索、更强扰动和更长 test-time compute。
Takeaway
- 1. 最值得记住的是 MaxGCP/MinGCP 这个重组方式：如果一族组合优化目标共享某个单调结构变量，可以先按该变量构造统一搜索方向，再让原 objective 只负责筛选。
- 2. ACMH 的迁移价值很高：相邻 objective 可以作为 escape landscape，而不仅是 evaluation metric。
- 这种 objective-level perturbation 可以迁移到其他多目标/带平衡项的组合优化问题。
- 3. 对 graph cut 这类稀疏局部结构问题，强启发式的关键不是设计更复杂的全局模型，而是把 move-gain 更新压到局部并让 test-time compute 足够密集。
一句话总结
这篇论文是 graph k-CUT 启发式求解的一次强工程化统一：它把多个 cut 变体按 boundary 单调性组织起来，用稳定局部增益和辅助目标搜索把已有 evolutionary/local-search 思想扩展成一个可迁移的多目标 cut solver。