3 Network Similarity Decomposition

下面进入 3 NETWORK SIMILARITY DECOMPOSITION。这一节是全文的方法核心。你可以把它理解成：

作者从 IsoRank 的矩阵迭代 (5) 出发，先把它按“路径长度”展开成级数；再对初始偏好矩阵 $H$ 做低秩外积分解；于是每个组件可以分别在两个图上独立传播，最后用外积合并。这样就把“同时处理两个图”的耦合计算，变成了“每图独立稀疏矩阵-向量乘法 + 最后外积”的解耦计算。

---

3.0 这一节的目标

作者开头说，出发点是 Singh 等人的 IsoRank 方法 [3]。NSD 要：

1. 大幅降低计算成本；
2. 提供执行轨迹，用来解释哪些链接模式对拓扑相似度贡献大；
3. 保持与 IsoRank 类迭代相同的数学结果，而不是换一种相似度定义。

所以这一节的所有推导，都是在重写同一个迭代，而不是引入新的相似度模型。

---

3.1 从迭代 (4) 展开成级数：式 (6) 和 (7)

回顾第 2 节的 IsoRank 向量迭代：

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

其中 $\tilde C=\tilde A\otimes \tilde B$，$x=\mathrm{vec}(X)$，$h=\mathrm{vec}(H)$。

作者取初始条件

$$x^{(0)}=h.$$

然后逐步展开。

第一步

$$x^{(1)}=\alpha \tilde C h+(1-\alpha)h.$$

第二步

$$x^{(2)} =\alpha \tilde C x^{(1)}+(1-\alpha)h =\alpha^2\tilde C^2h+(1-\alpha)\alpha\tilde C h+(1-\alpha)h.$$

第 $n$ 步

归纳得到：

$$x^{(n)} =(1-\alpha)\sum_{k=0}^{n-1}\alpha^k\tilde C^k h +\alpha^n\tilde C^n h. \quad (6)$$

这个式子的含义非常关键：

• 第 $k$ 项 $\tilde C^k h$ 表示初始偏好 $h$ 经过 $k$ 步乘积图传播后的贡献；
• $\alpha^k$ 对长路径贡献进行阻尼；
• $(1-\alpha)$ 是整体归一化；
• 最后一项 $\alpha^n\tilde C^n h$ 是截断到 $n$ 步后的“剩余项”。

当 $n\to\infty$ 且 $\alpha<1$ 时，因为 $\alpha^n\to 0$，最后一项消失：

$$x^{(\infty)} =(1-\alpha)\sum_{k=0}^{\infty}\alpha^k\tilde C^k h. \quad (7)$$

作者提到，这种展开在 PageRank 计算中已经被研究过 [23]。这里只是把 PageRank 的展开套到乘积图上。

关键点：式 (6) 不是近似，而是 $n$ 步迭代的精确展开；式 (7) 是 $n\to\infty$ 的极限。

---

3.2 把 $\tilde C^k h$ “unvec” 回矩阵形式：式 (8)

这一步是 NSD 解耦的代数基础。

利用第 2 节的两个性质：

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

以及

$$\mathrm{unvec}\big((B^T\otimes A)x\big)=AXB.$$

对 $\tilde C^k h$：

$$\tilde C^k h =(\tilde A\otimes\tilde B)^k\mathrm{vec}(H) =(\tilde A^k\otimes\tilde B^k)\mathrm{vec}(H).$$

再用 unvec 恒等式，取 $A=\tilde B^k$，$B=\tilde A^k$，注意 $B^T=(\tilde A^T)^k$：

$$(\tilde A^k\otimes\tilde B^k)\mathrm{vec}(H) =\mathrm{vec}\big(\tilde B^k H(\tilde A^T)^k\big).$$

所以式 (6) 的矩阵形式是：

$$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)$$

这一步的意义：原本 $\tilde C^k h$ 是在大小为 $n_A n_B$ 的乘积图上做向量乘法；现在它变成了两个独立的矩阵幂：

$$\tilde B^k H(\tilde A^T)^k.$$

注意 $\tilde B^k$ 只作用在 $B$ 图那一侧，$(\tilde A^T)^k$ 只作用在 $A$ 图那一侧。两个图已经开始解耦了，只是 $H$ 还把两边耦合在一起。

作者还指出，式 (8) 也可以直接通过迭代“unvec”版式 (4) 并令 $X^{(0)}=H$ 得到，两种推导等价。

---

3.3 分解 $H$：SVD 与外积分解

现在要把 $H$ 拆开，目的有两个：

1. 编码偏好；
2. 作为迭代初始条件。

作者用 SVD：

$$H=\sum_{i=1}^{r}\sigma_i u_i v_i^T, \quad (9)$$

其中：

• $r\le \min(n_A,n_B)$ 是 $H$ 的秩；
• $\sigma_i>0$ 是奇异值，按降序排列；
• $u_i$ 是左奇异向量，构成正交基，$u_i u_j^T=\delta_{ij}$；
• $v_i$ 是右奇异向量，也正交，$v_i v_j^T=\delta_{ij}$。

把 (9) 代入 (8)：

$$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]. \quad (10)$$

令

$$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]. \quad (11)$$

或者写成组件和：

$$X_i^{(n)} =\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], \quad (12)$$ $$X^{(n)}=\sum_{i=1}^{r}X_i^{(n)}. \quad (13)$$

这里是 NSD 的核心结构：

• 每个 SVD 三元组 $(\sigma_i,u_i,v_i)$ 产生一个组件相似度矩阵 $X_i^{(n)}$；
• $u_i^{(k)}=\tilde B^k u_i$ 只在图 $B$ 上做稀疏矩阵-向量乘法；
• $v_i^{(k)}=\tilde A^k v_i$ 只在图 $A$ 上做稀疏矩阵-向量乘法；
• 两个图完全独立传播，最后用外积 $u_i^{(k)}v_i^{(k)T}$ 合并。

这就是“解耦 + 分解”的代数实现。

---

3.4 更一般的分解：不一定是 SVD

作者特别强调，SVD 只是把 $H$ 分解成外积和的一种选择。一般地，可以用任意 $s$ 对向量：

$$H=\sum_{i=1}^{s}w_i z_i^T. \quad (14)$$

于是式 (12)(13) 变成：

$$X_i^{(n)} =(1-\alpha)\sum_{k=0}^{n-1}\alpha^k w_i^{(k)}z_i^{(k)T} +\alpha^n w_i^{(n)}z_i^{(n)T}, \quad (15)$$ $$X^{(n)}=\sum_{i=1}^{s}X_i^{(n)}, \quad (16)$$

其中

$$w_i^{(k)}=\tilde B^k w_i,\qquad z_i^{(k)}=\tilde A^k z_i.$$

这里 $s$ 是使用的组件数，不一定等于 $H$ 的秩 $r$。精确分解要求 $s\ge r$；如果 $s<r$，就是低秩近似。

SVD 对应特例：

$$w_i\leftarrow \sigma_i u_i,\qquad z_i\leftarrow v_i,\qquad s=r,$$

并额外满足正交性。但正交性不是 NSD 必需的。

这个一般化很重要，因为：

• 可以用 NMF（非负矩阵分解）避免负元素；
• 可以按应用需求选择组件；
• 可以选择 $s$ 来平衡精度和速度。

---

3.5 Algorithm 1 逐步解读

Algorithm 1 是 NSD 的稠密版本。步骤如下：

输入：$A,B,\{w_i,z_i|i=1,\ldots,s\},\alpha,n$。

1. 计算归一化矩阵 $\tilde A,\tilde B$；
2. 初始化 $X^{(n)}=0$；
3. 对每个组件 $i=1,\ldots,s$： 4. $w_i^{(0)}\leftarrow w_i$； 5. $z_i^{(0)}\leftarrow z_i$； 6. 对 $k=1,\ldots,n$： 7. $w_i^{(k)}\leftarrow \tilde B w_i^{(k-1)}$； 8. $z_i^{(k)}\leftarrow \tilde A z_i^{(k-1)}$； 9. 结束 $k$ 循环； 10. 对 $k=0,\ldots,n-1$： 11. $X^{(n)}\leftarrow X^{(n)}+(1-\alpha)\alpha^k w_i^{(k)}z_i^{(k)T}$； 12. 结束 $k$ 循环； 13. $X^{(n)}\leftarrow X^{(n)}+\alpha^n w_i^{(n)}z_i^{(n)T}$；
4. 结束 $i$ 循环。

逐步理解：

• 第 4–8 步：对每个组件，分别在图 $B$ 和图 $A$ 上做 $n$ 步稀疏矩阵-向量乘法。注意这里没有乘积图，也没有 Kronecker 乘积，只是两个独立图的传播。
• 第 10–12 步：把不同路径长度 $k$ 的外积贡献按权重 $(1-\alpha)\alpha^k$ 累加。
• 第 13 步：加上截断剩余项 $\alpha^n w_i^{(n)}z_i^{(n)T}$。
• 外层对 $i$ 循环：把所有组件的贡献加起来。

与 IsoRank 的等价性：如果 $s=r$ 且使用 SVD，Algorithm 1 的结果与直接迭代 IsoRank 在数学上等价（在相同 $n$ 和 $\alpha$ 下）。区别只是计算顺序和表示方式。原文实验中也说，NSD 计算的相似度矩阵与 netalign 的结果在机器精度内一致。

---

3.6 复杂度分析：为什么 NSD 更快？

3.6.1 朴素方法：显式乘积图

设 $nnz_A$ 是 $A$ 的非零元数（边数），$nnz_B$ 类似。乘积图 $C$ 的邻接矩阵有

$$nnz_C=nnz_A\times nnz_B$$

个非零元。每次迭代需要约

$$nnz_A\times nnz_B$$

次浮点运算。

这就是 IsoRank 直接在乘积图上做随机游走的成本，对大图不可行。

3.6.2 矩阵三乘积方法（MAT3）

如果使用式 (5) 的核：

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

每步计算 $\tilde B X\tilde A^T$ 的复杂度约为

$$n_B\times nnz_A+n_A\times nnz_B.$$

空间复杂度由 $O(n_A\times n_B)$ 的相似度矩阵 $X$ 主导。这比显式乘积图好，因为避免了 $nnz_A\times nnz_B$ 的存储和计算，但仍然每步要同时处理两个图。

3.6.3 NSD 的成本

Algorithm 1 中，对 $s$ 个组件，每个迭代步的成本约为

$$s\times(nnz_A+nnz_B+n_A\times n_B).$$

其中：

• $nnz_A+nnz_B$ 来自两个图上的稀疏矩阵-向量乘法；
• $n_A\times n_B$ 来自外积 $w_i^{(k)}z_i^{(k)T}$ 的累加；
• 每个组件独立，所以乘 $s$。

作者说，主导项是每个组件每步的 $O(n_A\times n_B)$。因此，当

$$s<\frac{nnz_{A,B}}{n_{A,B}}$$

时，NSD 有显著改进。这里 $\frac{nnz_{A,B}}{n_{A,B}}$ 大致是图的平均度。也就是说，当组件数小于图的平均度时，NSD 比 MAT3 更省。在实际应用中，$s$ 通常很小（例如 1、5、10），而平均度往往大于这个数，所以改进明显。

空间复杂度仍然是 $O(n_A\times n_B)$，因为要存相似度矩阵 $X$。

3.6.4 专门查询：不必构造完整 $X$

NSD 的另一个优势是支持节点对级别的查询，而不需要构造完整相似度矩阵。作者给出：

• 查询节点 $i\in V_B$ 和 $j\in V_A$ 的相似度分数：$O(s\times n)$ 次浮点运算；
• 查询最终 $X$ 条目的上界或下界：$O(s\times n\times\max\{n_A,n_B\})$ 次浮点运算。

这些查询假设幂迭代向量（Algorithm 1 第 7、8 步）已经算好。计算这些向量的成本是

$$O(s\times n\times\max\{nnz_A,nnz_B\}),$$

但可以摊销，因为可以复用。

直观理解：因为最终相似度是

$$X^{(n)}=\sum_i X_i^{(n)},$$

而每个 $X_i^{(n)}$ 是若干外积之和。要算单个元素 $(p,q)$，只需要算每个组件在每个 $k$ 上的

$$w_i^{(k)}(p)\cdot z_i^{(k)}(q),$$

再按权重求和即可。不需要存储整个 $n_A\times n_B$ 矩阵。

---

3.7 稀疏版本：Algorithm 2

3.7.1 为什么需要稀疏版本？

NSD 输出的是稠密相似度矩阵 $X$，即对每一对节点 $(i\in V_B,j\in V_A)$ 都给分数。这对应 $V_A$ 和 $V_B$ 之间的稠密二部图。

当两个图各有几万个节点时，$n_A\times n_B$ 的稠密矩阵会变得不可行。很多应用允许假设：大量潜在匹配的相似度可以忽略。例如 [9] 中，主题网络比较时，相似度矩阵被稀疏化到密度 $10^{-4}$，通过元数据标签排除低亲和力的节点匹配。

3.7.2 候选边集 $E_L$

给定一个稀疏二部图 $L$，节点在 $V_B\cup V_A$，边集

$$E_L=\{(p,q)|p\in V_B,q\in V_A\}$$

表示候选节点对，且

$$|V_B|\times|V_A|\gg |E_L|.$$

Algorithm 2 只在这些候选对上计算外积。

Algorithm 2 的步骤：

1. 强制 $X_i^{(n)}$ 矩阵只在 $E_L$ 索引的位置有非零元；
2. 把 Algorithm 1 第 11、13 步中的外积

$$P_i^{(k)}=w_i^{(k)}z_i^{(k)T},\quad k=0,\ldots,n$$

替换为稀疏版本： 3. 对每个 $(p,q)\in E_L$： 4.

$$(P_i^{(k)})_{pq}=(w_i^{(k)})_p(z_i^{(k)T})_q;$$

5. 结束。

注意：幂迭代

$$w_i^{(k)}\leftarrow \tilde B w_i^{(k-1)},\qquad z_i^{(k)}\leftarrow \tilde A z_i^{(k-1)}$$

仍然包含所有节点，只是分别在每个图上独立进行。稀疏化只发生在外积累加阶段。

3.7.3 没有候选对时怎么办？

如果没有候选对，作者提出一种启发式稀疏化：按行生成 $X$，每行只保留最大的若干项，具体比例取决于可用内存。这是退而求其次的方案。

---

3.8 SVD 的注意事项：负元素问题

3.3 节讨论 SVD 的一个重要细节。

$H$ 是非负矩阵（节点标签相似度通常非负）。但 SVD 的奇异向量 $u_i,v_i$ 在一般情况下可能含负元素，因为正交性要求。Perron-Frobenius 定理只保证第一对奇异向量 $u_1,v_1$ 非负。

这意味着：

• 某些组件矩阵 $X_i^{(n)}$ 可能有负元素；
• 在位置 $(p,q)$ 上的负元素表示：第 $i$ 个 SVD 三元组惩罚节点 $p\in V_B$ 和 $q\in V_A$ 的匹配；
• 但所有组件加起来，总和仍然为正。

负元素带来的麻烦：

1. 解释性：负贡献不如非负贡献直观；
2. 误差界：如果用少于 $r$ 项做近似，负元素使误差界难以建立。

作者给出两种解决方向：

• 使用非负分解（NMF）[25],[26]；
• 把因子中的正负元素分开处理 [27]。

但这些方法会带来额外的性能和成本考虑。原文实验中也同时用了 NMF 和 SVD 做对比。

---

3.9 这一节的关键 takeaway

可以浓缩成下面几条：

1. NSD 不改变 IsoRank 的相似度定义，而是把同一个迭代重写成可分解形式。
2. 迭代 (4) 可以精确展开为 $$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. 对 $H$ 做外积分解 $H=\sum_i w_i z_i^T$ 后，每个组件 $i$ 的传播完全解耦： $$w_i^{(k)}=\tilde B^k w_i,\qquad z_i^{(k)}=\tilde A^k z_i.$$ 两个图分别做稀疏矩阵-向量乘法，最后用外积合并。
4. Algorithm 1 对每个组件独立做 $n$ 步幂迭代，再按路径长度加权累加外积。
5. 复杂度：NSD 每步每组件约 $O(n_A n_B)$，总成本 $s\times(nnz_A+nnz_B+n_A n_B)$；当组件数 $s$ 小于平均度时，比 MAT3 的 $n_B nnz_A+n_A nnz_B$ 更省。
6. 专门查询：不必构造完整 $X$，单个节点对相似度只需 $O(s\times n)$。
7. Algorithm 2 对候选边集 $E_L$ 稀疏化外积，适合大图；幂迭代仍包含所有节点。
8. SVD 负元素：$H$ 非负，但奇异向量可能负，导致组件有负贡献；可用 NMF 或正负分离处理。

---

3.10 容易混淆的点

• 展开式 (6) 是精确的，不是近似；$n$ 步迭代对应有限项加一个剩余项。只有 $n\to\infty$ 时才取极限。
• 分解 $H$ 不一定是 SVD；SVD 只是特例。一般外积分解 $H=\sum w_i z_i^T$ 更灵活。
• $s$ 是组件数，不一定是 $H$ 的秩 $r$。$s<r$ 时是低秩近似；$s\ge r$ 时可以精确。
• NSD 的解耦发生在传播阶段：$w_i^{(k)}$ 只在 $B$ 上传播，$z_i^{(k)}$ 只在 $A$ 上传播；耦合只发生在最后的外积和 $H$ 的分解中。
• 稀疏版本 Algorithm 2 不是忽略节点；幂迭代仍然覆盖所有节点，只是外积累加限制在候选边 $E_L$ 上。
• 复杂度比较中的 $s<\frac{nnz_{A,B}}{n_{A,B}}$：右边近似是平均度；实际中 $s$ 往往很小，所以 NSD 优势明显。
• 负元素不是错误：它是 SVD 正交性的结果，总和仍为正；但会影响解释和误差界。

下一步进入 4 NUMERICAL EXPERIMENTS，重点看：Table 2/3 的计时如何体现 NSD 相对 IsoRank 和 MAT3 的加速；Facebook 自相似实验如何展示 MCCS；Web 图实验如何利用 rank-one 表示避免存储 TB 级矩阵；以及 $s>1$ 时 NMF/SVD 组件数对保守边和最大连通子图的影响。