1 Introduction

按第 1 INTRODUCTION AND MOTIVATION 的段落逻辑，理解作者的论证链：

图数据很多 → 网络对齐很重要 → 对齐的核心是节点对相似度 → 全局拓扑相似度定义很自然但计算很难 → 现有 IsoRank 类方法必须同时处理两个图，乘积图爆炸 → 我们提出 NSD：把两个图解耦、把相似度计算分解 → 因此大幅加速且结果可解释。

---

1.1 这一节到底在解决什么问题？

作者研究的是：

两个大而稀疏的图之间的全局对齐问题，核心是计算两个网络中节点之间的成对拓扑相似度。

给定两个图 $G_A$ 和 $G_B$，我们想知道：

• $G_A$ 中每个节点与 $G_B$ 中每个节点有多相似；
• 或者，$G_A$ 中每个节点的最佳匹配是谁；
• 也可以把 $G_A$ 与它自己比较，即自相似，用来发现同一网络中的重复结构。

这些相似节点对可以作为“种子”，进一步“生长”出两个网络中的保守子图或不变子图。在生物化学通路、蛋白质相互作用网络等场景中，这种保守子图能揭示功能与结构上的对应关系。

注意：作者特别说明，这不是一般意义上的子图同构或同胚问题。因为网络对齐需要先定义“相似度度量”和“映射约束”，而不是严格寻找完全同构的子图。

---

1.2 相似度矩阵 $S$ 是什么？

作者引入一个相似度矩阵 $S$，其中元素

$$s_{i,j}$$

表示第一个图中的节点 $i$ 与第二个图中的节点 $j$ 的相似度。

这个矩阵的构造方式取决于具体的节点相似度定义。相似度度量可以从多个维度区分，作者认为这里最关键的是：

相似度度量的拓扑范围：是局部的，还是全局的？

• 局部度量：只看节点的邻域，比如邻居重叠、局部结构。
• 全局度量：看整个网络的连接模式。

本文研究的是跨两个图的全局相似度计算，也包括一个图与自身的比较。

相似度分数代表节点之间“固有的但潜在的对应关系”。这些分数本身不是最终对齐结果，而是作为种子，用来生长保守子图。

---

1.3 拓扑相似度的递归定义：从 PageRank 类比而来

作者用一个非常关键的类比来定义节点拓扑相似度。

在单网络中，节点重要性/排名可以递归定义为：

一个节点重要，如果它被其他重要节点链接。

这是 PageRank 类思想的核心。

把这个定义扩展到节点相似度问题，就得到：

两个节点拓扑相似，如果它们被其他拓扑相似的节点对链接。

也就是说，节点对 $(i,j)$ 的相似度，不只取决于 $i,j$ 自身，还取决于与 $i$ 相邻的节点和与 $j$ 相邻的节点是否也形成相似节点对。这个定义是递归的，因此可以通过迭代矩阵乘法来传播远距离邻居的贡献。

作者还提到，这种思想可以用于自动图像标注、同义词抽取等任务，其中节点相似度被建模为节点排名，受 PageRank 和 HITS 两大模型启发。另一些方法则用 graphlet 入射模式的重叠来定义拓扑相似，例如考虑最多五个节点的所有子图模式，共 29 个 graphlet。

---

1.4 节点标签相似度与拓扑相似度的区别

这一节区分了两个概念：

节点标签相似度

节点标签相似度是两个带标签节点之间的相似度，与链接结构无关。

例如在蛋白质相互作用网络中，两个蛋白质的节点标签相似度可以就是它们蛋白质序列的匹配分数。

拓扑相似度

拓扑相似度则把节点标签相似度（如果可用）与链接结构结合起来，得到一个综合度量。

论文中说，本文中“拓扑相似度”和“一般节点相似度”可以互换使用。

标签相似度可以通过不同方式融入拓扑相似度：

• IsoRank 中，Singh 等人用蛋白质序列相似度来增强 PPI 网络中的蛋白质相似性。标签相似度不排除任何拓扑匹配，但标签相似度高的节点对在计算拓扑相似度时会被“偏爱”。
• 也可以用节点上的元数据标签，例如文章文本内容，来排除“无关”节点对。这可以显著减少内存和计算开销。
• 在另一些方法中不能强制排除，但可以在初始条件中指定节点对偏好。
• 大多数应用中，人们并不需要完整的拓扑相似度矩阵，而只关心最佳匹配节点对。这个优化通常表述为最大化某种累积成对拓扑相似度函数。

---

1.5 现有方法的根本痛点：同时处理两个图

作者指出，据他们所知，现有节点相似度计算方法会同时处理输入图。

常见做法是：

1. 计算输入图的稀疏或稀疏化乘积图；
2. 在这个乘积图中计算节点排名。

直观上，两个图 $G_A$ 和 $G_B$ 的乘积图 $G_C=G_A\times G_B$ 的节点是节点对 $(a_i,b_i)$。如果 $G_A$ 有 $n_A$ 个节点，$G_B$ 有 $n_B$ 个节点，那么乘积图有 $n_A n_B$ 个节点对。边数则大致是 $nnz_A\times nnz_B$ 量级。

即使原图很稀疏，乘积图也可能爆炸。对于 $10^6$ 节点的图，这种乘积图往往计算上不可行。

这就是 IsoRank 类方法的核心瓶颈：它们直接在乘积图上做类似 PageRank 的迭代，每一步都要让两个图同时参与。

后文的典型迭代形式是

$$X \leftarrow \alpha \tilde B X \tilde A^T + (1-\alpha)H,$$

其中 $X$ 是相似度矩阵，$\tilde A,\tilde B$ 是两个图的归一化邻接矩阵，$H$ 是节点标签相似度/初始偏好。这个形式看起来是矩阵三乘积，已经比显式构造 Kronecker 乘积 $\tilde A\otimes \tilde B$ 好，但仍然需要同时处理两个图，并且要存储或操作 $n_A\times n_B$ 的相似度矩阵。

---

1.6 NSD 的核心思想：解耦 + 分解

作者提出 NSD 来绕开上述瓶颈。第 1 节给出了两个核心概念：

1. 解耦（uncoupling）

解耦指的是对每个输入图进行独立的预处理。

也就是说，不再让两个图在每次迭代中同时参与大规模乘积，而是把计算拆成分别作用于 $G_A$ 和 $G_B$ 的部分，最后再合并。后文会看到，这对应于分别计算 $\tilde A^k v_i$ 和 $\tilde B^k u_i$ 这样的稀疏矩阵-向量乘积。

2. 分解（decomposition）

分解意味着成对相似度分数可以显式地拆解为不同链接模式的贡献，这些贡献可以追溯到计算初始条件的低秩近似。

直观上，初始偏好矩阵 $H$ 可以分解成若干个外积项，例如

$$H=\sum_i w_i z_i^T.$$

每一对向量 $w_i,z_i$ 产生一个“组件相似度矩阵” $X_i$，最终相似度是这些组件贡献之和。每个组件还可以按路径长度 $k$ 展开，因此可以看到不同长度的链接模式如何贡献相似度。

这两个概念带来三方面改进：

1. 计算成本显著降低；
2. 相似度分数更可解释；
3. 支持更丰富的查询，例如只查询某一对节点的相似度，而不必构造完整相似度矩阵。

---

1.7 作者报告的贡献与性能提升

作者在第 1 节末尾给出量化结论：

• 相比 IsoRank / Random Walk 形式，NSD 在真实数据集上实现超过两个数量级的性能提升；
• 相比约束矩阵三乘积形式，实现超过一个数量级的提升；
• 这些结果是在中等规模真实数据上展示的；
• 对于更大的图，作者用简单性能模型说明收益可能更高。

这里的“约束矩阵三乘积形式”对应后文的 $\tilde B X\tilde A^T$ 迭代，也就是 MAT3 类实现。它避免了显式 Kronecker 乘积，但仍然每步做两个图耦合的矩阵乘法。

---

1.8 第 1 节的关键 takeaway

你可以把这一节浓缩成下面几句话：

1. 网络对齐的核心是节点对相似度矩阵 $S$，高相似节点对可以作为种子生长保守子图。
2. 本文关注全局拓扑相似度，其递归定义是“两个节点相似，如果它们被其他相似节点对链接”。
3. 节点标签相似度可以独立于结构定义，并作为偏好或初始条件融入拓扑相似度。
4. 现有 IsoRank/随机游走类方法必须同时处理两个图，在乘积图上计算，面对大图时计算和存储都不可行。
5. NSD 的关键是：
   • 解耦：每个图独立预处理；
   • 分解：把相似度拆成低秩初始条件的组件贡献和不同链接模式的贡献；
   • 最后合并，得到快速、可解释、支持专门查询的相似度计算。
6. 结果是相对 IsoRank/Random Walk 超过两个数量级加速，相对矩阵三乘积方法超过一个数量级加速。

---

1.9 容易混淆的点

• NSD 不是重新定义一种完全不同的相似度度量，而是为 IsoRank 类拓扑相似度计算提供快速近似/分解算法。
• 不是子图同构算法，相似度分数只是对齐种子。
• 节点标签相似度不等于拓扑相似度；前者独立于结构，后者结合结构和标签偏好。
• “分解”不是简单矩阵分块，而是把初始偏好矩阵分解成若干外积组件，并把每个组件的路径贡献显式展开。
• “解耦”不是忽略两个图之间的关系，而是把每图的传播计算独立做，最后通过外积合并。

下一步 2 BACKGROUND AND NOTATIONS，重点是 PageRank/HITS/IsoRank 的形式化、Kronecker 乘积、乘积图，以及为什么后文的 NSD 公式能从迭代中展开出来。