4 Numerical Experiment

下面进入 4 NUMERICAL EXPERIMENTS。这一节的目标不是再讲算法，而是用真实数据回答三个问题：

1. NSD 到底快多少？ 与 IsoRank、MAT3（矩阵三乘积）、PDM/GM 匹配相比。
2. NSD 在自相似和大图场景下是否可用？ 尤其是 Facebook 网络和 Web 图。
3. 多组件 $s>1$ 时，低秩分解对对齐质量有什么影响？ NMF 与 SVD、$s$ 的大小如何影响保守边和最大公共连通子图。

---

4.0 实验总览

实验分三块：

小节	数据	目的
4.1	7 个 PPI 网络，所有两两组合	计时：NSD vs IsoRank vs MAT3，以及匹配开销
4.2	Facebook 网络、两个 Web 图	自相似：MCCS 规模、rank-one 表示避免 TB 级存储
4.3	fly/yeast PPI，用 BLAST 序列相似度作 $H$	多组件 $s>1$：NMF/SVD 组件数对对齐质量的影响

---

4.1 PPI 网络计时：NSD 到底快多少？

4.1.1 数据与实验设置

表 1 给出 7 个物种的 PPI 网络（无向）：

• celeg（线虫）：2805 节点，4572 边
• dmela（果蝇）：7518 节点，25830 边
• ecoli（大肠杆菌）：1821 节点，6849 边
• hypio（幽门螺杆菌）：706 节点，1414 边
• hsapi（人）：9633 节点，36386 边
• mmusc（小鼠）：290 节点，254 边
• scere（酵母）：5499 节点，31898 边

作者对所有 21 个物种对计算相似度矩阵 $X$。

参数设置：

• 表 2：$\alpha=1.0$，20 次迭代，均匀初始条件（外积形式），NSD 用 Matlab 实现。
• 表 3：$\alpha=0.8$，20 次迭代，$s=1$，均匀初始条件，NSD 用 Java 实现。

为什么选 $\alpha=0.8$：

• [30] 发现 $\alpha=0.6$ 可减少噪声网络数据的影响；
• 作者选 0.8 是因为它最大化保守边数；
• PageRank 类计算通常选 $\alpha$ 在 0.85 左右（Google 用 0.85）。

为什么固定 20 次迭代：

• 20 次不保证收敛；
• 但对 PPI 网络，由于直径小（平均 2.29–6.23），20 次已经能给出不错的质量；
• 严格收敛反而可能不是最优质量。例如 $\alpha=0.8$ 收敛需 32 次迭代（norm-1 为 $5\times 10^{-6}$），得到 495 条保守边；但 19 次迭代得到 524 条保守边，质量更好。
• $\alpha=1.0$ 时，20 次迭代 norm-1 为 $10^{-2}$；精确收敛产生 410 条保守边，21 次迭代却产生 439 条。
• $\alpha=0.6$ 时，收敛需 15 次（429 条边），但 5 步就能得到 465 条边。

这说明：严格 norm-1 收敛不是必须的；低直径网络很快达到质量平台。

4.1.2 对比对象

• IsoRank 原生二进制 [28]：内部先算相似度矩阵，再做两阶段匹配；不提供单独算 $X$ 的选项，所以总时间包含匹配。
• MAT3 [29]：netalign 的 Matlab 实现，用三矩阵乘积 $\tilde B X\tilde A^T$，不显式构造 Kronecker 乘积。
• PDM：Primal-Dual Matching，Matlab 实现，用于从 $X$ 提取最佳匹配。
• GM：Greedy Matching，Java/C 实现，启发式匹配。
• NSD：本文方法，Matlab 和 Java 两版。

作者强调：NSD 只关注快速、可分解地计算 $X$。如果相似度矩阵一致，且用相同匹配过程，最终匹配对相同。实验也验证：NSD 计算的相似度矩阵与 netalign 在机器精度内一致。

4.1.3 表 2：Matlab 实现，$\alpha=1.0$

表 2 有三列：

• NSD 计算 $X$ 的时间；
• PDM 在 NSD 算出的 $X$ 上做匹配的时间；
• 原生 IsoRank 的总时间（含匹配）。

几个代表性数据：

物种对	NSD (s)	PDM (s)	IsoRank (s)
celeg-dmela	7.92	166.79	833.97
celeg-hsapi	12.68	232.15	1094.36
dmela-scere	15.01	191.18	5306.00
hsapi-scere	20.35	26.68	7691.00
mmusc-scere	0.81	3.22	43.23

解读：

• NSD 算 $X$ 的时间远小于 IsoRank 总时间。例如 hsapi-scere：20.35s vs 7691s，约 378 倍。
• PDM 匹配时间有时也不小（例如 celeg-dmela 的 166.79s），但作者指出 GM 启发式更快（Java/C 实现），且匹配不是本文重点。
• 原生 IsoRank 的总时间包含匹配，所以比较时要“扣除匹配开销”。作者认为即使扣除，NSD 仍显著优于 IsoRank。
• 对于 dmela-hsapi，IsoRank 显示 N/A，说明原生实现无法在合理时间内完成。

4.1.4 表 3：Java 实现，$\alpha=0.8$，$s=1$

表 3 更全面，列出：

• NSD（Java）
• MAT3
• PDM（Matlab）
• GM（Java）
• IsoRank（原生）

代表性数据：

物种对	NSD	MAT3	PDM	GM	IsoRank
celeg-dmela	3.15	64.20	152.12	7.29	783.48
dmela-hsapi	8.61	211.19	590.16	28.10	7840.00
hsapi-scere	6.09	152.02	181.17	15.56	6714.00
mmusc-scere	0.46	4.35	2.71	0.47	40.86

解读：

• NSD 比 MAT3 快约 25 倍。例如 dmela-hsapi：8.61s vs 211.19s。
• NSD 比原生 IsoRank 快最多 三个数量级。例如 dmela-hsapi：8.61s vs 7840s，约 910 倍。
• 图 3 展示 Matlab 版 NSD 对 MAT3 的加速比，约 5–9 倍；移植到 Java 后达到约 25 倍。
• 作者提醒：这些计时是 $s=1$ 的情况。$s$ 增大时，性能优势会线性下降。要等到 $s$ 达到几十或几百个组件时，NSD 才可能和 MAT3/IsoRank 性能相当。但即使那样，NSD 仍提供额外可解释信息。

4.1.5 计时实验的关键结论

1. NSD 算 $X$ 显著快于 IsoRank 和 MAT3；
2. 加速来自解耦：两个图分别做稀疏矩阵-向量乘法，而不是每步同时乘两个图；
3. $s=1$ 时优势最大；$s$ 增大时优势线性缩小；
4. NSD 与 IsoRank 的相似度矩阵在机器精度内一致，所以匹配结果不变；
5. 固定 20 次迭代不一定收敛，但对低直径 PPI 网络质量已足够；严格收敛未必最优。

---

4.2 网络自相似：Facebook 与 Web 图

4.2.1 为什么做自相似？

两两比较在这个场景下难以解释，所以先计算同一网络内节点之间的相似度，即 $G_A=G_B$。

实验设置：

• $\alpha=0.80$，20 次迭代，$s=1$；
• 一对随机初始条件（打破可能的平局），所有实验用同一随机种子；
• 算法会正确地把每个节点与自身匹配；
• 作者把这些自匹配分数置零，再用 GM 提取匹配。

为什么要排除自匹配：

如果保留自匹配，公共连通子图会直接复制原图结构，没有新信息。排除后，匹配对 $(i,j)$（$i\neq j$）可以揭示网络中的重复子结构或对称结构。

4.2.2 对齐图与公共连通子图

给定两个图 $G_A,G_B$，匹配 $m_1=(i_1,j_1)$ 和 $m_2=(i_2,j_2)$ 在 $V_B\times V_A$ 中。若：

• $i_1$ 与 $i_2$ 在原图中相连；
• $j_1$ 与 $j_2$ 在原图中相连；

则 $m_1$ 和 $m_2$ 在对齐图中连边。

公共连通子图就是对齐图中的连通分量，即“匹配节点对的簇”，同时保持链接模式。

自相似时 $G_A\equiv G_B$，还要考虑对称性：

$$(i_1,i_2)\equiv(i_2,i_1),$$

且 $m_1=(i_1,i_2)$、$m_2=(i_3,i_4)$ 连通当且仅当：

• $i_1,i_3$ 和 $i_2,i_4$ 连通；或
• $i_1,i_4$ 和 $i_2,i_3$ 连通。

作者用 networkx 找最大公共连通子图（MCCS）。

4.2.3 表 4：Facebook 网络

网络	节点数	边数
Caltech	36769	933312
Princeton	12659	6586640
Georgetown	15941	851276

Facebook 网络是无向的，因为好友关系需要双方同意。

4.2.4 表 5：MCCS 结果

表 5 列出每个网络与自身配对后的 MCCS 特征：

网络	节点数	边数	参与 MCCS 的节点比例	平均度
hypo	76	198	2.00%	2.00
dmela	849	22	2.33%	3.44
scere	239	288	8.69%	5.80
hsapi	189	245	3.92%	3.78
Caltech	36268	129769	69.79%	43.32
Princeton	12198	673346	60.22%	88.94
Georgetown	15265	476515	56.38%	90.43

解读：

• Facebook 网络的 MCCS 比同规模 PPI 网络大一个数量级；
• Facebook 中很大比例的匹配对参与 MCCS（56%–70%）；
• 作者归因于：Facebook 用户常与“朋友的朋友”连接，因此继承部分邻域结构，增强相似度分数；
• 与平均度强相关：平均度越大，两个匹配对相连的概率越高，因为它们包含的节点有更多连接“选项”。

4.2.5 表 6：Web 图

图	爬取年份	域名	节点数	边数
cnr-2000	2000	cnr	325,557	3,216,152
eu-2005	2005	eu	862,664	19,235,140

这些是有向图，用 WebGraph 压缩格式存储，作者把 NSD 适配到 WebGraph 框架。

关键设置：

• 计算纯拓扑自相似，$\alpha=1$，20 次迭代；
• 选择秩一初始条件，于是式 (12) 中的求和消失，只剩一个外积，两个向量相同，即一个排名向量；
• 这意味着 $X$ 可以表示为 $rr^T$ 形式，不需要存稠密矩阵。

为什么这很关键：

• 这些 Web 图有几十万到近百万节点；
• 如果像 IsoRank 那样存稠密 $X$，需要 TB 级内存，远超当前容量；
• NSD 的 rank-one 表示使计算可行。

匹配提取：

• 对排名向量排序；
• 从大项开始两两配对；
• 匹配对应节点；
• 这本质上是 GM 方法应用在“相同向量的外积”上，且不允许节点与自身匹配。

结果：

• cnr-2000：1,912 个含 4 个以上节点的公共连通子图；
• eu-2005：5,178 个；
• 覆盖节点比例：cnr-2000 为 28.29%，eu-2005 为 37.31%；
• 其余匹配节点参与孤立三角形、边或孤立节点；
• 图 4 展示最大 30 个公共连通子图的大小：
  • cnr-2000 最大 17,520 节点；
  • eu-2005 最大 38,818 节点。

解读：

• 匹配允许图中相距很远的节点配对；
• 一个公共连通子图本质上代表原图中两个子图，其节点匹配后边重叠令人满意；
• 因此可以发现重复的连接模式，即子图“副本”；
• 有些重复结构非常广泛；
• 注意 NSD 用于有向图时，分数只约束入链结构的相似性。

4.2.6 自相似实验的关键结论

1. NSD 能处理 Facebook 和 Web 图这类规模的数据；
2. Facebook 的 MCCS 远大于 PPI，且与平均度强相关；
3. Web 图上 rank-one 表示避免 TB 级存储，使自相似可行；
4. 排除自匹配后，公共连通子图揭示重复子结构，而不是复制原图；
5. 有向图场景下，NSD 的分数只反映入链结构相似性。

---

4.3 多组件 $s>1$：低秩分解对对齐质量的影响

4.3.1 实验设置

• 数据：fly/yeast PPI 网络；
• $H$：BLAST 序列相似度矩阵（节点标签相似度）；
• $\alpha=0.80$，20 次迭代；
• 计算所有含 $\ge 4$ 个节点的公共连通子图；
• 对比：
  1. 只用 $H$ 作为相似度分数（不计算拓扑相似度），再用 GM；
  2. MAT3 用精确 $H$ 计算相似度，再用 GM；
  3. NMF 分解 $H$ 为 $s=5$ 和 $s=10$ 个组件，跑 NSD + GM；
  4. SVD 分解 $H$ 为 $s=5$、$10$、$500$、$1,000$ 个组件，跑 NSD + GM。

4.3.2 评价指标

作者用两个纯拓扑指标评价匹配：

1. 对齐图中的边数（保守边）：每条保守边意味着原图中对应边被匹配；
2. 对齐图中连通分量的大小（公共连通子图）：这些子图本质上是输入网络中子结构的匹配。

两者关系：

• 保守边多，通常更容易形成大连通子图；
• 但也可能有很多中等大小的连通子图，而不是少数大子图。

4.3.3 图 5：只用 $H$ 与 MAT3

• 图 5a：只用节点标签相似度 $H$ 生成匹配，公共连通子图较小、较碎；
• 图 5b：MAT3 用精确 $H$ 计算拓扑相似度，公共连通子图更多、更大。

这说明拓扑传播确实能增强对齐结构。

4.3.4 图 6：NMF/SVD，$s=5$ 和 $s=10$

• 上排：NMF，$s=5$ 和 $s=10$；
• 下排：SVD，$s=5$ 和 $s=10$。

结果与 MAT3 定性相似，但规模不同。

4.3.5 图 7：SVD，$s=500$ 和 $s=1,000$

组件数增大后，结果更接近 MAT3。

4.3.6 具体数值

保守边数：

方法	保守边
MAT3（精确 $H$）	1,455
SVD $s=5$	514
SVD $s=10$	537
SVD $s=500$	1,143
SVD $s=1,000$	1,236

解读：

• $s=5$ 时，SVD 低秩近似只捕获约 35% 的 MAT3 保守边；
• 原因：该 $H$ 的奇异值衰减不够快；
• 图 8 显示前 200 个奇异值：$i<20$ 快速下降后，存在一个持续的背景平台，大小相近的贡献一直存在；
• 所以少量组件无法很好近似 $H$。

最大公共连通子图：

方法	最大子图节点数
MAT3	22
SVD $s=5$	239
SVD $s=10$	204
SVD $s=500$	55
SVD $s=1,000$	25

这是一个有趣的反直觉现象：

• $s=5$ 时最大子图有 239 个节点，远大于 MAT3 的 22；
• 但随着 $s$ 增大，最大子图反而下降：239 → 204 → 55 → 25；
• 原因：更多组件更好地近似 $H$，结果更接近 MAT3；
• 所以低秩近似虽然保守边少，但可能把匹配集中到一个很大的连通子图中；
• 这说明保守边数和最大连通子图规模不是单调一致的。

4.3.7 NMF 的结果

• NMF 天然产生非负节点标签分数；
• $s=10$ 时：521 条保守边，最大公共连通子图 266 个节点；
• 与 SVD 定性相似；
• GM 对小的 $s$ 可能出现的负分数有鲁棒性，所以 SVD 结果也是“平滑”过渡的。

4.3.8 多组件实验的关键结论

1. 低秩分解的组件数 $s$ 是精度与成本的调节旋钮；
2. $s$ 小时，保守边少，但可能形成很大的连通子图；
3. $s$ 大时，结果更接近精确 $H$ 的 MAT3；
4. SVD 的奇异值衰减速度决定低秩近似的效果；该 fly/yeast 的 $H$ 衰减慢，所以 $s=5$ 只捕获 35% 保守边；
5. NMF 与 SVD 定性相似，但 NMF 非负，解释性更好；
6. 保守边多不等于最大连通子图大，两个指标要一起看。

---

4.4 第 4 节整体 takeaway

1. 速度：NSD 算相似度矩阵比 MAT3 快约 25 倍，比原生 IsoRank 快最多三个数量级（$s=1$，Java 实现）；Matlab 版对 MAT3 有 5–9 倍加速。
2. 等价性：NSD 与 IsoRank/netalign 的相似度矩阵在机器精度内一致，匹配结果不变。
3. 参数：固定 20 次迭代不保证收敛，但低直径 PPI 网络质量已足够；严格收敛未必最优；$\alpha=0.8$ 是常用选择。
4. 自相似：Facebook 的 MCCS 远大于 PPI，且与平均度强相关；Web 图上 rank-one 表示避免 TB 级存储，使几十万到近百万节点的自相似可行。
5. 多组件：$s$ 控制精度/成本；SVD 衰减慢时小 $s$ 只捕获部分保守边；但小 $s$ 可能产生更大的连通子图；NMF 与 SVD 定性相似。
6. 可解释性：NSD 的组件分解让每个 SVD/NMF 组件、每个路径长度 $k$ 的贡献都可追踪，这是 IsoRank/MAT3 不提供的。

---

4.5 容易混淆的点

• 表 2 的 IsoRank 时间是总时间（含匹配），NSD 列只是算 $X$ 的时间；比较时要考虑匹配开销。
• PDM/GM 是匹配算法，不是相似度算法；它们不是本文重点，但计时表里列出来是为了公平比较。
• 表 3 的 NSD 是 Java 实现，所以比表 2 的 Matlab 版快很多；图 3 的 5–9 倍是 Matlab 版对 MAT3 的加速，Java 版达到约 25 倍。
• $s$ 增大时 NSD 优势线性下降；$s$ 很小时优势最大。
• 自相似实验排除自匹配，否则公共连通子图只是复制原图。
• Web 图的 rank-one 表示只适用于 $\alpha=1$ 且秩一初始条件的自相似；不是所有 NSD 场景都能这样压缩。
• 保守边和最大连通子图不是一回事；$s=5$ 时保守边少但最大子图很大，$s$ 增大后最大子图反而下降。
• SVD 奇异值衰减慢意味着低秩近似效果差；图 8 的平台说明该 $H$ 不适合非常小的 $s$。
• NMF 和 SVD 都可以用；SVD 可能负元素，NMF 非负但计算可能更贵。

如果你愿意，下一步我们可以进入 5 CONCLUDING REMARKS AND FUTURE WORK，把全文贡献、局限和未来方向收束起来。