Flow Ratio (chain objective)
Definition. Laenen & Sun (NeurIPS 2020) 引入的链式 cluster 间有向流目标函数, 对 k-way 划分 \{S_0, \ldots, S_{k-1}\}: \Phi_G(S_0, \ldots, S_{k-1}) = \sum_{j=0}^{k-1} \frac{w(S_j, S_{j-1})}{\text{vol}(S_j) + \text{vol}(S_{j-1})} 其中 w(S, T) = \sum_{u \in S, v \in T} w(u, v) 是 cut 值, \text{vol}(S) = \sum_{u \in S} d_u。最大化 \Phi_G 即寻找"沿有向链有最大 flow imbalance" 的 cluster 序列。
与 Bennett 2022 / Cucuringu 2020 的对比
| 目标 | Bennett 2022 (Herm-RW) | Laenen-Sun 2020 (Flow Ratio) |
|---|---|---|
| 求和形式 | 所有 \binom{k}{2} 个 pair 的 flow imbalance | 仅 k-1 个相邻 pair (沿一条链) |
| 几何含义 | "任意 cluster 对之间的流方向" | "沿一条有向链的 cluster 排序" |
| 适用场景 | lead-lag (谁 lead 谁, 无序) | 贸易链 / 信息流链 / 流行病传播 (有序) |
| k=2 复杂度 | MAX DICUT | MAX DICUT |
| Cluster 排序 | RowSum leadingness 启发式 | 自然序 (output 即链序) |
关键区别: Laenen-Sun 假设 cluster 间存在自然链式顺序 (如原油出口 → 加工 → 进口 → 消费), 而 Bennett 假设 cluster 间是任意 pair 的"lead/lag" 关系。
k=2 退化: MAX DICUT
当 k=2 时, \Phi_G(S_0, S_1) = \frac{w(S_1, S_0)}{\text{vol}(S_0) + \text{vol}(S_1)} + \frac{w(S_0, S_1)}{\text{vol}(S_1) + \text{vol}(S_0)}, 仍等价于 MAX DICUT (NP-hard)。Goemans & Williamson (1995) 的 0.878 SDP 近似是已知最佳。
Hermitian Laplacian 嵌入
Theorem 3.2 (Laenen-Sun 2020): 对最优划分 \{S_j^*\}, cluster indicator \chi_j(u) = \sqrt{\omega_{2\pi j/k} / \text{vol}(S_j^*)} \cdot \mathbf{1}\{u \in S_j^*\} 满足 \sum_{j=0}^{k-1} \chi_j 是 L_G 的最小特征向量 (特征值 0)。
直觉: cluster 在链中的"位置" 编码到 \chi_j 的相位 \omega_{2\pi j/k}, 不同 cluster 的点云在 \mathbb{C}^2 上沿 k 等分方向散开。
Cheeger 风格近似保证
设 \Phi^* = \max \Phi_G, \gamma_k = 1 / (1 - \Phi^*), SimpleHerm 输出 \{A_j\} 满足:
\text{vol}(A_j \triangle S_j^*) \le \frac{48 k^3 (1 + \text{APT})}{\gamma_k - 1} \cdot \text{vol}(S_j^*)
其中 APT 是 k-means 近似比。
与 Cheeger 不等式 (k=2) 同构: \gamma_k - 1 越大 (flow 结构越显著), 恢复越准; k^3 因子是链式 vs 二分目标的代价。
应用案例
| 数据 | k | cluster 含义 | 实证对齐 |
|---|---|---|---|
| UN Comtrade 国际油贸 | 4 | 出口国 → 中转 → 加工 → 进口 | 2008-09 crisis 期间 cluster 剧变 |
| UN Comtrade 国际木材 | 4 | 森林丰富国 → 中间 → 进口 | 2008-09 同上 |
| 韩国 COVID-19 感染图 | 4 | super-spreader + 3 个感染群体 | 找出单一 super-spreader |
邻近概念
- Hermitian Laplacian — 配套谱算法
- Hermitian Spectral Clustering — 父类
- Meta-Flow Graph — Bennett 2022 类似的可视化, 但更通用 (任意 pair)
- Directed Network Clustering — 算法全景
- MAX DICUT — k=2 退化的复杂度参考
起源 / 标准文献
- Laenen & Sun (NeurIPS 2020) — flow ratio 形式化 + 理论 + UN Comtrade (本 wiki 摘要)
- Cucuringu, Li, Sun, Zanetti (AISTATS 2020) — pairwise flow imbalance 版本
- Goemans & Williamson (1995) J. ACM — MAX DICUT 0.878 SDP 近似
- An, Zhong, Chen, Li, Gao (2014) Energy — 国际油贸复杂网络分析 (ref [1])
Open Questions
- 链长 k 未知: 能否用 Laplacian 特征值的"聚类间隙" 自动选 k? 类似 Dynamic Regime Number Selection。
- 美股 lead-lag 上, 是否存在"价值链" (上游材料 → 中游制造 → 下游消费) 对应的有序 cluster? Bennett 2022 没测试。
- 与 Bennett 2022 的 "any pair" 目标统一: 是否存在一个 "partially ordered" 目标, 介于 chain 与 full pairwise 之间?
- COVID-19 感染图的"链序" vs super-spreader cluster 的关系是否可定量分析?