2 Background

下面按 2 BACKGROUND AND NOTATIONS 的逻辑，把 PageRank/HITS/IsoRank 的形式化、Kronecker 乘积、乘积图，以及“为什么后面 NSD 能展开”一次讲透。你可以把这一节理解成：作者先把已有方法写成统一的矩阵/向量迭代，再准备好后面分解所需的代数工具。

---

2.1 相关工作脉络：单图排名 → 跨图相似度

作者把相关工作分成两类。

第一类：单网络中的节点排名

代表是 PageRank 和 HITS。

• PageRank：把网页浏览建模为随机游走，节点排名是随机过程的稳态分布。
• HITS：区分“hub”和“authority”，二者互相强化；一个好的 authority 被很多好 hub 指向，一个好的 hub 指向很多好 authority。

这两个方法本质上是单图上的排名。作者说，HITS 可以看成在 hub-authority 二部图上做两个不同的随机游走；最终分数也是相应随机游走的平衡分布。

第二类：跨网络的节点相似度/网络对齐

代表工作包括：

• Blondel 等人：把 HITS 推广到一对有向图，定义任意一对顶点之间的相似度。但他们的迭代不一定收敛到唯一的奇/偶极限。
• Zager 和 Verghese：在 Blondel 迭代中加入对角项，放大高度连接节点的分数，并证明无论初始条件如何都收敛。
• IsoRank（Singh 等人）：本文最直接的前身。它把节点属性相似度（蛋白质序列相似度，即节点标签相似度）和拓扑相似度结合起来，用类似 PageRank 的迭代计算 PPI 网络中的顶点相似度，再用二部图匹配对齐两个网络。
• Rupp 等人的 graph kernel：利用分子结构图的有界度特性，把 PageRank 特化到目标结构；每轮迭代在每对顶点的邻域之间找最优映射。
• SimRank、Katz scores：也属于节点相似度，后面提到低秩近似曾被用于加速它们，但那些方法近似的是图结构，不是节点标签相似度矩阵 $H$。

作者对 NSD 的定位是：

NSD 是一个高效的、基于 PageRank 的拓扑相似度计算算法；它通过解耦和分解相似度计算，既大幅降低计算成本，又支持丰富查询、可解释执行轨迹，并且易于并行化。

---

2.2 术语与预备知识：邻接矩阵、归一化矩阵、score transport

图的表示

图 $G_A(V_A,E_A)$ 用邻接矩阵 $A$ 表示。$n_A$ 是节点数，$d(i)$ 是节点 $i$ 的度（有向图是入度+出度）。

归一化矩阵 $\tilde A$

作者定义：

$$(\tilde A)_{ij} = \frac{a_{ji}}{\sum_{k=1}^{n_A} a_{jk}}$$

对非零行成立，否则为零。

这个定义要仔细理解：

• $a_{ji}$ 表示原图中 $j \to i$ 的边；
• 分母 $\sum_k a_{jk}$ 是 $A$ 第 $j$ 行的和，也就是节点 $j$ 的出度；
• 所以 $\tilde A$ 的第 $i$ 行第 $j$ 列，等于“$j$ 指向 $i$ 的边”除以“$j$ 的出度”。

换句话说，$\tilde A$ 是 $A^T$ 的行归一化版本。它的每一行加起来为 1？不，更准确地说，它的每一列对应原图某个源节点 $j$ 的出边归一化，因此 $\tilde A$ 是列随机的：

$$\sum_i \tilde A_{ij} = \sum_i \frac{a_{ji}}{d(j)} = 1.$$

这正好对应 PageRank 中 Google 矩阵的列随机性。

score transport 解释

作者给出一个很有用的解释：

$$y = \tilde A x$$

可以看成“分数传输”：

$$y_i = \sum_j \tilde A_{ij} x_j = \sum_j \frac{a_{ji}}{d(j)} x_j.$$

节点 $i$ 从它的入邻居 $j$（即 $j \to i$）那里“拉取”分数，每个邻居 $j$ 贡献 $\frac{x_j}{d(j)}$。也就是说，$j$ 把自己的分数平均分给它的所有出邻居。

类似地：

$$y^T = x^T \tilde A^T$$

表示节点把自己的分数沿出边“推”给邻居。

因此矩阵 $\tilde A^n$ 的元素 $(\tilde A^n)_{ij}$ 有一个概率解释：初始在节点 $j$ 的单位分数，经过 $n$ 步后落到节点 $i$ 的比例。

单图排名算法的矩阵形式

作者指出，大多数单图节点排名算法用：

• HITS：$A$ 与 $A^T$ 的乘积，如 $AA^T$ 或 $A^TA$；
• PageRank：$\tilde A$ 的幂。

这样同时捕获入链和出链信息：

• $A$ 对应沿出链发送；
• $A^T$ 对应从入链接收；
• $\tilde A$ 对应从入链接收，但按源节点的出度归一化。

---

2.3 乘积图 $G_C = G_A \times G_B$：跨图相似度的基础

这是本节最核心的构造。

乘积图的定义

给定两个图 $G_A$ 和 $G_B$，它们的张量积/乘积图是：

$$G_C = G_A \times G_B.$$

• 节点：$G_A$ 和 $G_B$ 的节点对 $(a_i,b_i)$，其中 $a_i\in V_A$，$b_i\in V_B$；
• 边：$(c_i,c_j)\in E_C$ 当且仅当 $(a_i,a_j)\in E_A$ 且 $(b_i,b_j)\in E_B$。

也就是说，乘积图中的一个节点代表一个“候选匹配对”；乘积图中的一条边表示两个匹配对在原图中同时有边。

为什么乘积图能表达“拓扑相似度”？

单图排名的递归定义是：

一个节点排名高，如果它的邻居排名高。

跨图相似度的递归定义是：

一对节点相似度高，如果它们的邻居对也相似度高。

这个“邻居对”的关系正好定义在乘积图上。于是，在乘积图上运行普通节点排名算法，高排名节点对就对应两个原图中的高相似度节点对。

这就是 IsoRank/Blondel 方法的共同基础。

---

2.4 HITS 启发的 Blondel 迭代

Blondel 等人构造一个 $n_B\times n_A$ 的矩阵 $X$，初始化为全 1。迭代：

$$X \leftarrow BXA^T + B^TXA. \quad (1)$$

每一步后对 $X$ 归一化。偶数次迭代收敛到矩阵 $X'$，其中 $x'_{ij}$ 是节点 $i\in V_B$ 和 $j\in V_A$ 的相似度。

向量化形式

定义 $vec(\cdot)$ 把矩阵按列堆叠成向量，$unvec(\cdot)$ 是逆操作。令 $x=vec(X)$，则 (1) 变成：

$$x \leftarrow (A\otimes B + A^T\otimes B^T)x,$$

或者令 $C=A\otimes B$：

$$x \leftarrow (C+C^T)x. \quad (2)$$

这里 $\otimes$ 是 Kronecker 乘积。

这个迭代的问题

作者指出：除了归一化步骤，这些迭代本质上是把任意多个 $C$ 和 $C^T$ 因子作用在初始向量上。但 Blondel 方法不保证收敛到唯一的奇/偶极限，这是后面 Zager-Verghese 改进的动机。

---

2.5 PageRank 启发的 IsoRank 迭代

这是本文最关键的迭代，也是 NSD 的起点。

Singh 等人提出：

$$x \leftarrow \alpha \tilde A \otimes \tilde B\, x + (1-\alpha)h. \quad (3)$$

其中：

• $x=vec(X)$，$X$ 是相似度矩阵；
• $h=vec(H)$，$H$ 的元素的 $h_{ij}$ 是节点 $i\in V_B$ 和 $j\in V_A$ 的节点标签相似度；
• $h$ 归一化为单位范数；
• $\alpha\le 1$ 控制拓扑相似度的权重，$1-\alpha$ 控制节点标签相似度的权重。

在 Singh 等人的应用中，$h$ 编码蛋白质序列相似度，PPI 网络是无向图。

收敛性

迭代 (3) 本质是幂法，对任意 $x^{(0)}$ 在

$$O(\log(1/(1-\alpha)))$$

步内收敛。当 $\alpha=1$ 时，退化为一般马尔可夫链系统。

记 $\tilde C = \tilde A \otimes \tilde B$

于是 (3) 写成：

$$x \leftarrow \alpha \tilde C x + (1-\alpha)h. \quad (4)$$

这正是一个 PageRank 计算：

$$x \leftarrow \alpha Gx + (1-\alpha)v,$$

只是：

• Google 矩阵 $G$ 换成了 $\tilde C$，即两个图邻接矩阵 Kronecker 乘积的列随机形式；
• 个性化向量 $v$ 换成了 $h$，即预计算的匹配偏好/节点标签相似度。

从向量形式回到矩阵形式

利用 $unvec$，把 (4) 写成矩阵形式：

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

这是本文后面反复使用的工作方程。

score transport 解释

拓扑相似度项

$$\alpha \tilde B X \tilde A^T$$

可以按 score transport 理解：

• 节点从邻居那里导入相似度分数；
• 同时它也作为邻居的相似度分数来源；
• 因此这种传输是双向的，更适合无向图。

Fig. 1 的例子说明：节点 2 从它的两个邻居拉取总分数，但有四种方式（因为另一张图有四个节点）；最终 $X_{21}$ 只被 $y(2)$ 和 $y(3)$ 加权更新，因为只有节点 2 和 3 是 $1\in V_A$ 的邻居；权重分别是 $\frac12$ 和 $\frac13$，因为节点 2 和 3 分别有 2 和 3 个邻居。

---

2.6 Kronecker 乘积与 unvec：NSD 展开的代数工具

要理解后面 NSD 为什么能从迭代展开，必须掌握两个恒等式。

恒等式 1：vec 与 Kronecker 乘积

对任意矩阵 $A,X,B$：

$$vec(AXB) = (B^T \otimes A)vec(X).$$

等价地：

$$unvec\big((B^T \otimes A)vec(X)\big) = AXB.$$

特别地，取 $A=\tilde B$，$B=\tilde A^T$，则 $B^T=\tilde A$，所以：

$$(\tilde A \otimes \tilde B)vec(X) = vec(\tilde B X \tilde A^T).$$

这正是 IsoRank 迭代中 $\tilde C x$ 对应的矩阵形式。

恒等式 2：Kronecker 乘积的乘法性质

$$(A\otimes B)(C\otimes D) = (AC)\otimes(BD).$$

因此：

$$(\tilde A\otimes \tilde B)^k = \tilde A^k \otimes \tilde B^k.$$

合起来：$\tilde C^k h$ 的矩阵形式

由上面两个性质：

$$\tilde C^k h = (\tilde A\otimes \tilde B)^k vec(H) = (\tilde A^k\otimes \tilde B^k)vec(H) = vec\big(\tilde B^k H (\tilde A^T)^k\big).$$

这就是第 3 节展开的核心代数依据。

---

2.7 为什么 NSD 公式能从迭代中展开出来？

现在把逻辑串起来。

从矩阵迭代 (5) 出发：

$$X^{(t)} = \alpha \tilde B X^{(t-1)} \tilde A^T + (1-\alpha)H.$$

第一步：展开一阶

$$X^{(1)} = \alpha \tilde B H \tilde A^T + (1-\alpha)H.$$

第二步：展开二阶

把 $X^{(1)}$ 代入：

$$X^{(2)} = \alpha \tilde B\big(\alpha \tilde B H \tilde A^T + (1-\alpha)H\big)\tilde A^T + (1-\alpha)H.$$

整理：

$$X^{(2)} = \alpha^2 \tilde B^2 H(\tilde A^T)^2 + \alpha(1-\alpha)\tilde B H\tilde A^T + (1-\alpha)H.$$

第三步：归纳到 $n$ 步

$$X^{(n)} = (1-\alpha)\sum_{k=0}^{n-1}\alpha^k \tilde B^k H(\tilde A^T)^k + \alpha^n \tilde B^n H(\tilde A^T)^n. \quad (8)$$

这就是第 3 节式 (8)。

第四步：极限形式

当 $n\to\infty$，$\alpha<1$ 时，最后一项 $\alpha^n\tilde B^n H(\tilde A^T)^n\to 0$，所以：

$$X^{(\infty)} = (1-\alpha)\sum_{k=0}^{\infty}\alpha^k \tilde B^k H(\tilde A^T)^k.$$

这个展开的直观含义是：

• $\tilde B^k H(\tilde A^T)^k$ 表示经过 $k$ 步链接模式传播后的相似度贡献；
• $\alpha^k$ 对长路径贡献进行阻尼；
• $(1-\alpha)$ 是整体归一化因子；
• $H$ 是初始偏好/节点标签相似度。

第五步：分解 $H$

第 3 节进一步把 $H$ 做 SVD：

$$H = \sum_{i=1}^r \sigma_i u_i v_i^T.$$

代入展开式，得到：

$$X^{(n)} = \sum_{i=1}^r \sigma_i \left[ (1-\alpha)\sum_{k=0}^{n-1}\alpha^k \tilde B^k u_i v_i^T(\tilde A^T)^k + \alpha^n \tilde B^n u_i v_i^T(\tilde A^T)^n \right].$$

令

$$u_i^{(k)}=\tilde B^k u_i,\qquad v_i^{(k)}=\tilde A^k v_i,$$

就得到：

$$X^{(n)} = \sum_{i=1}^r \sigma_i \left[ (1-\alpha)\sum_{k=0}^{n-1}\alpha^k u_i^{(k)}v_i^{(k)T} + \alpha^n u_i^{(n)}v_i^{(n)T} \right].$$

这就是 NSD 的组件分解形式：每个 SVD 三元组 $(\sigma_i,u_i,v_i)$ 产生一个组件相似度矩阵 $X_i^{(n)}$，最终相似度是这些组件之和。

---

2.8 这一节的关键 takeaway

可以浓缩成下面几条：

1. PageRank/HITS 是单图排名；IsoRank 把 PageRank 推广到乘积图，用 $\tilde C=\tilde A\otimes\tilde B$ 做类似 PageRank 的迭代。
2. 乘积图 $G_A\times G_B$ 的节点是节点对，边表示两个原图中的边同时存在；在乘积图上排名高，就对应原图中拓扑相似的节点对。
3. IsoRank 的向量形式是 $$x\leftarrow \alpha \tilde C x+(1-\alpha)h,$$ 矩阵形式是 $$X\leftarrow \alpha \tilde B X\tilde A^T+(1-\alpha)H.$$
4. Kronecker 乘积 + unvec 给出关键恒等式： $$(\tilde A\otimes\tilde B)vec(X)=vec(\tilde B X\tilde A^T),$$ 以及 $$\tilde C^k h=vec\big(\tilde B^k H(\tilde A^T)^k\big).$$
5. 因此 IsoRank 迭代可以显式展开成 $$X^{(n)} =(1-\alpha)\sum_{k=0}^{n-1}\alpha^k \tilde B^k H(\tilde A^T)^k +\alpha^n \tilde B^n H(\tilde A^T)^n.$$ 这正是第 3 节 NSD 分解的起点：先把 $H$ 低秩分解，再把每个组件的路径贡献分开计算，从而避免同时处理两个图的大规模乘积。
6. 注意：NSD 并不是换了相似度定义，而是对 IsoRank 类迭代做代数展开和分解；第 2 节的所有记号、Kronecker 性质、unvec 操作，都是为第 3 节的展开服务的。

---

2.9 容易混淆的点

• $\tilde A$ 是 $A^T$ 的行归一化，因此 $\tilde A$ 是列随机的；这对应 PageRank 中 Google 矩阵的列随机性。
• $x=\mathrm{vec}(X)$ 是按列堆叠；$unvec$ 是逆操作。Kronecker 乘积恒等式中的转置位置容易写错，记住： $$vec(AXB)=(B^T\otimes A)vec(X).$$
• 乘积图 $G_C$ 的节点数是 $n_A n_B$，边数量级是 $nnz_A\cdot nnz_B$；这正是 IsoRank 类方法在大图上的瓶颈。
• Blondel 的 HITS 型迭代和 IsoRank 的 PageRank 型迭代是两种不同形式；本文主要沿 IsoRank 的 PageRank 型迭代展开，因为它的阻尼和初始偏好更适合后续分解。
• 第 3 节的“分解”有两个层次：
  1. 对路径长度 $k$ 展开；
  2. 对初始条件 $H$ 做低秩外积分解。 这两层都建立在第 2 节的 Kronecker/unvec 恒等式上。

下一步进入 3 NETWORK SIMILARITY DECOMPOSITION，重点讲 Algorithm 1 的每一步、复杂度为什么从 $nnz_A\times nnz_B$ 降到 $s\times(nnz_A+nnz_B+n_A n_B)$，以及稀疏版本 Algorithm 2 如何只在外积的候选边上计算。