图重排序收益的结构归因：以摊销成本口径检验社区结构强度能否预测 PageRank/BFS 的加速比

1 · 研究问题

对 20 个以上公开真实图，四种顶点重排序（graph reordering）方法——Gorder、Rabbit Order、按度排序（DegSort）、逆 Cuthill–McKee（RCM）——给 PageRank 与 BFS 带来的加速比，能否由一个可先验计算的图结构量（Louvain 模块度 Q、度分布幂律指数、平均度、有效直径）预测？在把重排序自身开销计入的摊销口径下，每种方法需要执行多少次图算法才能回本？

2 · 研究背景与空白

技术背景。 图算法（PageRank、BFS、连通分量）在压缩稀疏行（CSR）格式上的主要瓶颈不是算术，而是访问邻居顶点属性数组时的随机内存访问。顶点编号顺序直接决定这些访问的空间局部性：如果相邻顶点的编号也相近，它们的属性就落在同一缓存行或同一页上。顶点重排序就是在跑算法之前先把顶点重新编号一遍，用一次预处理成本换取后续每一轮迭代的缓存命中率。这类课题对本项目的资源约束是理想的：图数据是公开的、算法是纯 CPU 整数与访存密集型的、衡量指标（缓存缺失率、每边处理时间）在笔记本上就能稳定测出——算力墙在这里根本不构成约束，反而是"小内存 + 真实缓存层级"让局部性效应更容易观测。

已有工作到哪一步。 Wei 等的 Gorder（SIGMOD 2016）通过最大化滑动窗口内的共同邻居数来排序，报告了对多种图算法的加速；Arai 等的 Rabbit Order（IPDPS 2016）利用真实网络的层次社区结构做并行重排序；Balaji 与 Lucia 的《When is Graph Reordering an Optimization?》（IISWC 2018）已经明确提出了"重排序何时值得"的问题，并指出轻量方法（如 Hub Sorting、Hub Clustering）在摊销后往往优于重量方法。近期工作继续在这条线上推进：有研究报告 RCM 虽然摊销成本低于 Gorder，但仍需约 20 次算法执行才能抵消其重排序时间；另有面向稀疏矩阵向量乘（SpMV）与图神经网络训练的重排序实验研究，覆盖 bfs / degsort / dfs / gorder / hubcluster / hubsort / ldg / metis / minla / rabbit / rcm / slashburn 等十余种方法。

空白在于：现有实验研究几乎都停留在"哪个方法更快"的横向排名，而没有把加速比当作因变量、把可先验计算的图结构量当作自变量，去建立并检验一个预测模型。换句话说，从业者拿到一张新图时，仍然没有一条"先算个 Q 值就知道该不该重排序"的可操作判据。这个空白属于"问题方向的转换"（从"哪个更快"转为"什么能预测更快"），可靠性高：所有输入都是公开图与公开算法，实验规模可控，且正负结论都成立——若结构量能预测，得到一条实用判据；若不能预测，则说明重排序收益依赖更细的微架构因素，这本身是对现有直觉的一次证伪。

3 · 可检验假设

• H1：PageRank 的重排序加速比与 Louvain 模块度 Q 正相关，跨 ≥ 20 个图的 Spearman 秩相关 ρ ≥ 0.6（p < 0.05，自助法置信区间不跨 0）。若 ρ < 0.3，则 H1 被否证。
• H2：摊销回本次数（break-even executions，含排序时间的总成本等于不排序时的总成本所需的算法执行次数）在 Gorder 上中位数 ≥ 10，在 DegSort 上中位数 ≤ 3；即"轻量方法在单次或少次执行场景下严格占优"这一判断在本样本上成立。
• 备择机制假设：若 Q 的预测力不足，则改由"度分布幂律指数 γ"或"最大 k-core 的顶点占比"承担预测变量；模型选择用留一交叉验证的预测均方误差决定，而非事后挑选最好看的相关系数。

4 · 量化验收标准

1. 方法学校验（硬门槛）：用自建管线在文献已报告过的至少 3 个公共图（例如 soc-LiveJournal1、com-Orkut、web-Google 或其在已发表实验中出现的等价图）上重现 Gorder 与 RCM 对 PageRank 的加速比，与已发表数值的相对偏差 ≤ 25%（跨硬件不可能更严，故同时要求方法间的相对排序完全一致，且缓存缺失率的变化方向一致）。这一步不过关，后续全部结论无效。
2. 基准测试方法学：每个（图 × 排序 × 算法）组合重复 ≥ 20 次；固定 CPU 频率与线程绑定，禁用 Turbo；每次运行前冲刷缓存与页缓存状态；报中位数与 IQR，不报均值；组间比较用 Mann–Whitney U 检验。PageRank 固定为 20 次幂迭代（不用收敛判据，避免迭代数随排序变化污染计时），BFS 固定从 64 个随机但种子写死的源点出发。
3. 双成本口径：与已发表实现对照时同时报等工作量（相同迭代数的墙钟时间）与等墙钟时间预算（固定 10 秒内完成的迭代数）；摊销口径单独作为第三张表，明确写出排序时间的测量方式（单线程还是并行、是否含 I/O）。
4. 样本量与统计：图样本 ≥ 20 个，覆盖至少 4 个类别（社交网络、网页图、道路网、合成幂律图），顶点数跨 3 个数量级；相关系数给自助法（bootstrap, ≥ 2000 次重采样）95% 置信区间；不报 R² 单一数字，必须同时给散点图与置信带。
5. 结构量计算的可复现性：模块度用固定分辨率参数与固定随机种子的 Louvain 实现，报告 10 次独立运行的 Q 值中位数与极差；幂律指数用 Clauset–Shalizi–Newman 的最大似然 + KS 距离方法，而非双对数最小二乘，并报告拟合的 KS 检验 p 值。
6. 可复现性：全部代码、图清单与下载脚本、原始计时 CSV、结构量表格与绘图脚本开源；一键重跑脚本；全部随机种子写死。

5 · 数据与工具

用途	来源 / 工具
真实图数据	SNAP 数据集（snap.stanford.edu/data，社交/网页/道路/协作网络，含 com-Orkut、soc-LiveJournal1、web-Google、roadNet-CA 等）；SuiteSparse Matrix Collection（sparse.tamu.edu，可按顶点数/非零数在线筛选后单图下载，有效控制下载量）
合成图	NetworkX 的 powerlaw_cluster_graph / LFR 基准生成器（LFR_benchmark_graph，内置于 NetworkX，可控社区强度 μ——这一条对 H1 至关重要，因为它允许主动扫描模块度而不是被动依赖真实图的分布）
图算法内核	GAP Benchmark Suite（GitHub sbeamer/gapbs，C++，含 PageRank、BFS、CC、BC 的高质量参考实现，支持 CSR 与 OpenMP）。仅用于校验与对比，不计入本项目的数据贡献。
重排序实现	Rabbit Order（作者开源，依赖 Boost 与 libnuma，需核实在无 NUMA 的笔记本上能否编译，这是已知风险点）；Gorder（作者开源 C++）；DegSort 与 RCM 可自行实现（RCM 亦有 SciPy scipy.sparse.csgraph.reverse_cuthill_mckee 内置版本，可作交叉校验）
社区检测与结构量	NetworkX（community.louvain_communities 自 3.x 起内置）或 igraph（community_multilevel，C 实现、快得多，大图上首选）；幂律拟合用 powerlaw 包（Alstott 等实现 CSN 方法）
计数器与计时	Linux perf stat（LLC 缺失、DTLB 缺失）；退路 cachegrind
算力	纯 CPU。com-Orkut（3M 顶点 / 117M 边）CSR 约 1 GB，Gorder 预处理是本课题最重的一步（文献报告在大图上可达分钟级），16 GB 笔记本可覆盖顶点数 ≤ 5M 的图；超出范围：顶点数 ≥ 50M 的图（如 web-ClueWeb）不在本课题范围内，需在正文明确声明样本上界

6 · 方法路径

1. 装环境，编译 GAP Benchmark Suite，用其自带算例与官方公布的参考结果确认安装正确；完成验收标准第 1 条的三图重现校验。
2. 核实工具能力边界：Rabbit Order 在无 NUMA 环境下能否编译运行（若不能，用其算法描述自行实现基于 Louvain 层次的重排序，并用制造样例验证——若需自行实现，须用小图上的暴力最优解或已知性质做验证，这本身可作为方法学贡献写入）；确认 Gorder 的窗口参数与文献一致。
3. 组建图样本：从 SNAP / SuiteSparse 选 ≥ 15 个真实图 + ≥ 5 个 LFR 合成图（合成图的 μ 参数扫描覆盖模块度 0.2–0.8），登记每图的顶点数、边数、方向性、是否去自环与重边；预处理判据写死并公开。
4. 计算结构量：对每图算 Louvain 模块度（10 次取中位数）、幂律指数（CSN 方法 + KS 检验）、平均度、有效直径（用采样估计并给误差）、最大 k-core 占比。
5. 执行主扫描：4 种排序 × 2 种算法 × 20+ 图 × 20 次重复，同步采集 perf 计数器与排序自身耗时；全部逐次结果落盘。
6. 分析：出中位数/IQR 表、加速比 vs 结构量的散点与 Spearman ρ（自助法置信区间）、摊销回本次数表、双成本口径对照表；用留一交叉验证选预测变量，报告预测均方误差而非仅相关系数。
7. 独立交叉校验：在 LFR 合成图上做一次受控实验——固定顶点数与度分布、只扫描社区强度 μ，看加速比是否随 μ 单调变化。这条是对 H1 的因果性最强的检验，与真实图上的相关性分析互为独立证据。

7 · 新颖性边界

本课题不声称：不提出新的重排序算法，不声称任何重排序方法优于另一种（这已由前人给出），不声称对图算法性能的新的理论界。GAP 内核、Gorder 与 Rabbit Order 的实现均为他人工作，标注为对照基准，不计入本项目贡献。

已有工作完成了什么：Wei 等（Gorder, SIGMOD 2016）与 Arai 等（Rabbit Order, IPDPS 2016）给出了方法本身及其加速比；Balaji 与 Lucia（IISWC 2018）已提出"重排序何时是优化"并给出轻量方法在摊销下常优于重量方法的结论；近期 SpMV 与 GNN 训练场景的实验研究把方法清单扩展到十余种，并报告了 RCM 约需 20 次执行回本这一量级的数字。这些结论本项目直接引用，不重复声称为发现。历届丘奖对照：计算机赛道 2021 年金奖《Efficient Algorithm for Parallel Bi-core Decomposition》（Phillips Academy）与 2022 年银奖《Efficient Parallel Density-Peak Clustering》（Phillips Academy / MIT PRIMES）是最相邻的两项——它们的共同形态是"为某个图/聚类问题设计一个更快的并行算法"。本课题的形态与之相反：不设计任何算法，而是把已有方法的收益当作被解释的因变量，判断依据是结构量的预测力而非加速比本身。这一差异必须在引言写明。

本项目的贡献：把问题方向从"哪种排序更快"转为"能否用可先验计算的结构量预测收益"，并用 LFR 合成图上的受控 μ 扫描把相关性证据升级为准因果证据。产出物是一条可操作的判据（例如"Q < 0.4 时任何重排序的摊销收益都为负"）及其置信区间。这是主结论。

为什么有价值：从业者面对新图时需要的是决策规则而不是排行榜。若判据成立，它可以直接写进图处理框架的启发式；若不成立（结构量无预测力），则证明收益由更细的微架构因素主导，这对后续研究是明确的方向排除。

风险提示：ρ 落在 0.3–0.6 之间的"弱相关"是最可能的结果。此时必须给出自助法置信区间证明本样本量（≥ 20 图）确有分辨 ρ=0.6 与 ρ=0 的统计功效；功效不足则须扩大图样本至 30 个而非改口径。

8 · 决策门槛（go / no-go）

• 第 5 周：数据与编译门槛。若 GAP 无法编译或 SNAP 大图下载受阻，降级路径 A：改用 igraph（Python 绑定，pip 可装）+ 自行实现的 CSR PageRank/BFS 作为内核，图样本改以 SuiteSparse 的中等规模图（顶点 10⁵–10⁶）为主。加速比的绝对值会下降，但结构量—加速比的关系框架完全保留。
• 第 9 周：Rabbit Order 可用性必须核实完毕——这是需要提前确认而非边做边发现的事项。若无法编译且自行实现超时，降级路径 B：把方法集缩为 Gorder + DegSort + RCM + HubSort 四种（后三种均可在 200 行内自行实现或由 SciPy 提供），主结论框架不变，仅在正文声明 Rabbit Order 未纳入及原因。
• 第 12 周：方法学校验硬门槛。若三图重现的偏差 > 25% 或方法排序与文献不一致，排查频率控制、迭代数定义（是否用了收敛判据）、图预处理（是否去了重边）三个最常见原因；第 15 周仍不过关则降级路径 C：放弃跨文献绝对对照，改为纯内部对照设计（同一管线内比较"排序前 vs 排序后"），并把校验硬门槛替换为"在 LFR 合成图上验证 CSR 局部性指标（平均邻居编号距离）随排序单调下降"这一可解析验证的替代门槛。
• 第 30 周：H1 必须有明确结论。若 ρ 的置信区间过宽无法判定，降级路径 D：把课题重心正式移到 H2（摊销回本次数的系统测定），这部分不依赖相关性显著性，且本身就是文献中缺少系统数字的方向；H1 降为次要分析并如实报告统计功效不足。主结论框架（摊销口径下的重排序决策）保留。
• 预算裁剪顺序：结构量种类 → 图样本中的合成图数量 → 排序方法数量 → （绝不裁剪）重复次数与真实图样本量。
• 选择前提：适合对图论有兴趣、能接受"结果可能是负相关或无相关"的学生。若学生期待"做出一个更快的算法"，这条路线不合适。

---