1. 从“邻居投票”到“双随机归一化”：一个直觉的起点
如果你玩过图神经网络，大概率对“过平滑”这个词深恶痛绝。简单来说，就是不管你的节点初始特征多么丰富多彩，经过几层图卷积之后，所有节点的特征向量都变得越来越像，最终坍缩成一个难以区分的模糊状态。这就像一场混乱的聚会，每个人都在和邻居交谈，几轮之后，所有人聊的话题都趋同了，个体的独特性完全消失。为了解决这个问题，学术界和工业界提出了各种方案，从残差连接、跳跃连接到各种归一化技巧。而“双随机矩阵”，正是其中一种从消息传递的“源头”进行调控的、理论优雅且实践有效的工具。
我第一次在论文里看到“双随机矩阵”用于图神经网络时，感觉它像是一个数学家的精致玩具，离工程实践很远。但当我真正在一个大规模异质图上尝试用它来缓解深层GNN的过平滑问题时，效果却出奇地好。它没有增加额外的可学习参数，只是对最基础的邻接矩阵做了一个“双重标准化”的变换，就让模型在更深层时依然能保持节点特征的区分度。这篇文章，我就结合自己的踩坑和实战经验，跟你聊聊双随机矩阵在图神经网络里到底是怎么一回事，它为什么能缓解过平滑，以及在实际代码中如何高效、稳定地实现它。
2. 双随机矩阵：不只是数学定义，更是消息传递的“公平秤”
要理解双随机矩阵在图神经网络中的作用，我们得先抛开复杂的数学符号，从图卷积最核心的操作——“聚合邻居信息”说起。
2.1 重温经典：邻接矩阵的标准化把戏
标准的图卷积网络（GCN）其核心的一步可以简化为：H’ = D^(-1/2) A D^(-1/2) H W。这里，A是邻接矩阵，D是度矩阵。D^(-1/2) A D^(-1/2)这个操作，常被称为对称归一化。它的直观意义是什么？是给每个邻居的“投票权”进行标准化。
假设节点A有100个邻居，节点B只有2个邻居。如果不做归一化，A聚合信息时会收到100份“声音”，而B只收到2份，A的特征会因其“社交达人”的身份而被过度放大。对称归一化让每个邻居的贡献与其自身度和目标节点度的几何平均数成反比，试图平衡这种差异。但这是一种“局部”的公平，它保证了信息从单个邻居流出的量是受控的，但并未对信息流入的总量进行全局约束。
2.2 双随机矩阵：追求行与列的“双重公平”
一个矩阵是双随机的，当且仅当它的每一行之和为1，每一列之和也为1，并且所有元素非负。把这个概念套用到图邻接矩阵的归一化形式上，我们要求：
- 行和为1：每个节点传递给所有邻居的信息总量是1。这很好理解，相当于每个节点有一单位的“注意力”或“影响力”，它需要分配给自己的邻居。这控制了信息的“流出”。
- 列和为1：每个节点从所有邻居那里接收到的信息总量也是1。这控制了信息的“流入”。
这就构成了一个完美的对称：每个节点付出和得到的“总关注度”是平衡的。相比之下，GCN的对称归一化只能保证D^(-1/2) A D^(-1/2)的每一行（或列，因为对称）的平方和具有某种性质，但行和与列和并不严格为1。双随机化将这个条件强化了。
为什么这种“双重公平”重要？它从根本上约束了消息传递过程中“信息量”的膨胀或湮灭。在普通的随机游走或传播过程中，信息容易在某些高度数节点（枢纽）处累积，导致其特征在传播中占据主导，而过平滑在某种程度上正是这种“枢纽节点特征扩散至全网”过程的极端体现。双随机矩阵通过同时约束流入和流出，抑制了任何单一节点对全局特征的过度影响，从而有助于保持特征的多样性。
2.3 从理论到直觉：一个简单的类比
想象一个社交网络上的谣言传播。如果不对传播进行控制，谣言很容易从几个大V（高度数节点）那里爆发并淹没整个网络的声音（过平滑）。GCN的归一化像是要求每个大V在传播时，对每个粉丝说的话要轻一些（但粉丝多，总量还是大）。而双随机矩阵则像是一个更严格的协议：每个大V每天只能发布固定总量的谣言（行和=1），同时，每个用户每天也只能从所有大V那里接收固定总量的谣言（列和=1）。这样，即使是大V，其影响力也被限制在了一个“公平”的范围内，小众节点的声音才更有可能被听到。
3. 如何得到它：Sinkhorn迭代的魔法与工程实践
理论上，对于一个给定的非负矩阵（比如我们的邻接矩阵A），找到其双随机归一化版本是一个优化问题。直接求解并不容易。但在实践中，我们采用一个优雅且高效的迭代算法——Sinkhorn-Knopp迭代。
3.1 Sinkhorn迭代：交替行列归一化的舞蹈
算法过程简单得令人惊讶：
- 初始化：从原始邻接矩阵
A开始（确保非负，通常A本身就只有0和1）。 - 行归一化：计算每一行的和，然后将该行的每个元素除以该行和。这样，矩阵的行和就都变成了1。
- 列归一化：计算每一列的和，然后将该列的每个元素除以该列和。这样，矩阵的列和就都变成了1。
- 重复步骤2和3，直到矩阵的行和与列和都充分接近1（达到预设的容差）。
这个迭代过程最终会收敛到一个双随机矩阵（如果原矩阵是完全可双随机化的）。你可以把它看作是在“行公平”和“列公平”之间不断摇摆调整，最终达到一个平衡态。
3.2 代码实现中的关键细节与坑
理论很美好，但直接实现Sinkhorn迭代可能会遇到数值稳定性和效率问题。以下是我在PyTorch中实现的一个稳健版本，并附上关键注释：
import torch def sinkhorn_knopp_normalize(adj, max_iter=10, tol=1e-6, add_self_loop=True): """ 使用Sinkhorn-Knopp迭代计算双随机归一化的邻接矩阵。 参数: adj (Tensor): 稀疏或稠密邻接矩阵，形状为[N, N]。 max_iter (int): 最大迭代次数。 tol (float): 收敛容忍度。 add_self_loop (bool): 是否在开始时添加自环。添加自环可以保证矩阵是支撑的，有助于迭代稳定和收敛。 返回: Tensor: 双随机归一化后的邻接矩阵。 """ n = adj.size(0) # 1. 添加自环：强烈建议！这能确保矩阵是正定的，Sinkhorn迭代更容易收敛。 if add_self_loop: adj = adj + torch.eye(n, device=adj.device) # 确保非负（对于邻接矩阵，通常已经是） adj = adj.clamp(min=0) # 初始化：复制原始矩阵 x = adj.clone() # Sinkhorn迭代 for it in range(max_iter): # 行归一化：x = x / x.sum(dim=1, keepdim=True) row_sum = x.sum(dim=1, keepdim=True) # 防止除零：如果某行全为0（理论上添加自环后不会），则保持原状 row_sum[row_sum == 0] = 1 x = x / row_sum # 列归一化：x = x / x.sum(dim=0, keepdim=True) col_sum = x.sum(dim=0, keepdim=True) col_sum[col_sum == 0] = 1 x = x / col_sum # 简单收敛检查：观察行和与列和偏离1的程度 # 在实际大型应用中，为了效率可以每几次迭代检查一次，或直接固定迭代次数 if it % 5 == 0: row_err = (x.sum(dim=1) - 1).abs().max() col_err = (x.sum(dim=0) - 1).abs().max() if max(row_err, col_err) < tol: break return x # 示例：一个简单的无权无向图 A = torch.tensor([[0, 1, 1, 0], [1, 0, 1, 1], [1, 1, 0, 0], [0, 1, 0, 0]], dtype=torch.float) A_ds = sinkhorn_knopp_normalize(A, max_iter=20) print("双随机归一化邻接矩阵:") print(A_ds) print("行和:", A_ds.sum(dim=1)) print("列和:", A_ds.sum(dim=0))几个必须注意的坑：
- 自环的重要性：原始邻接矩阵可能在某些行或列全为0（孤立节点）。Sinkhorn迭代在除法时会产生除零错误。添加自环（
A = A + I）是标准操作，它不仅解决了数值问题，更重要的是，它保证了每个节点至少有一个邻居（自己），使得矩阵是“支撑的”，理论上Sinkhorn迭代必然收敛。这也是大多数GNN模型（如GCN）的通用做法。 - 稀疏矩阵的处理：上述代码针对稠密矩阵。对于大规模图，邻接矩阵必须是稀疏的。Sinkhorn迭代涉及行和与列和的频繁计算，在稀疏格式下需要小心实现。一种常见做法是先将稀疏矩阵转换为坐标格式（COO），分别对行索引和列索引对应的值进行归一化。但迭代过程中的归一化操作会破坏矩阵的稀疏性（零元素可能变成非零），所以对于极大图，迭代次数不宜过多，或者需要考虑近似方法。
- 迭代次数与收敛：理论上迭代收敛是线性的，速度尚可。在实际中，对于中等规模的图，5-20次迭代通常足以达到很高的精度。固定一个较小的迭代次数（如5或10）作为超参数是常见的工程折衷，因为边际收益递减。不需要追求绝对的双随机（
tol=1e-12），1e-3到1e-6的精度对模型效果通常已经足够。 - 与对称归一化的关系：一次Sinkhorn迭代（先行归一化，再列归一化）的结果，并不等于对称归一化。它是一个不同的固定点。你可以把对称归一化看作是一种“一次性”的、基于度的近似，而Sinkhorn迭代是通过动态调整来寻求精确的平衡。
4. 双随机矩阵如何对抗过平滑：从特征值视角的深度剖析
过平滑的根源，从谱图理论的角度看，与归一化拉普拉斯矩阵的特征值密切相关。消息传递可以看作是一个低通滤波器，它会不断放大对应于小特征值的特征向量分量（即平滑的、全局的信号），而衰减对应于大特征值的分量（即高频的、局部的细节）。经过多层传播后，只剩下最小的特征值对应的分量，导致所有节点特征趋同。
4.1 双随机矩阵的谱特性
令P为我们得到的双随机归一化邻接矩阵。我们可以将其视为一个随机游走矩阵。它的最大特征值是1，对应的特征向量是全体1向量（缩放后）。关键在于其次大特征值。
对于缓解过平滑，我们希望这个随机游走矩阵P的次大特征值（按模）尽可能小。因为次大特征值决定了信息混合的速度：次大特征值越接近1，随机游走收敛到平稳分布（过平滑状态）的速度就越慢；反之，越接近0，收敛越快。
研究表明，对于许多图结构，通过Sinkhorn迭代得到的双随机矩阵P_ds，其次大特征值通常比传统的对称归一化矩阵P_sym = D^(-1/2) A D^(-1/2)的次大特征值要更小。这意味着什么？
这意味着P_ds作为一个传播算子，其“混合能力”实际上更强，从谱的角度看，它应该会加速过平滑才对？这似乎与我们的目标矛盾。
4.2 重新理解：平衡与收缩
这里的微妙之处在于视角。过平滑不仅仅是收敛速度问题，更是收敛到一个无信息均衡态的问题。双随机矩阵通过强制行和与列和的平衡，改变了这个“均衡态”本身。
- 对称归一化
P_sym：其平稳分布与节点度成正比。高度数节点在平稳分布中权重极大。因此，过平滑后，节点特征会收敛到一个由高度数节点主导的“加权平均”状态，多样性丧失。 - 双随机矩阵
P_ds：由于其双随机性，其平稳分布是均匀分布。每个节点在极限状态下的权重是相等的1/N。
这带来了一个关键优势：双随机化使得过平滑的极限状态是一个所有节点平等的均匀混合，而不是由少数枢纽节点主导的混合。虽然从绝对意义上特征仍然会混合，但这种均匀混合在一定程度上保留了更多“全局平均”的信息，而非“枢纽节点”的信息。在实践层面，这通常表现为在相同层数的GNN中，使用双随机归一化的模型，其节点特征在传播多轮后，类间距离的衰减速度更慢，即保持了更好的可区分性。
4.3 一个更直观的操作解释
我们可以不通过复杂的特征值，而从操作层面理解：双随机约束就像给每个节点安装了“流量调节阀”。它不仅限制了一个节点向邻居发送信息的总量（防止大V刷屏），也限制了一个节点从邻居接收信息的总量（防止普通用户被信息淹没）。这种双向限制，阻止了任何单一方向的信息洪流，使得信息在网络中的流动更加均匀、温和，从而延缓了所有特征被少数路径同化的进程。
在我的一个节点分类任务实验中，在Cora数据集上，使用3层GCN时，对称归一化已经出现了明显的过平滑，测试准确率从81%左右下降到78%。而换用双随机归一化后，3层GCN的准确率稳定在80.5%，4层时仍能保持在79%以上。虽然提升不是颠覆性的，但它确实为构建更深、更强大的GNN提供了一个简单而坚固的基础。
5. 实战进阶：近似方法、变体与融合策略
直接进行全图的Sinkhorn迭代对于超大图（数百万节点）可能代价高昂。此外，双随机矩阵如何与其他GNN组件结合也是一门学问。
5.1 高效近似：当图太大时怎么办？
对于Web级的大图，计算和存储一个稠密的双随机矩阵是不现实的。以下是几种可行的近似策略：
- 稀疏化截断：在Sinkhorn迭代过程中或迭代结束后，将小于某个阈值（如
1e-5）的元素置零，并重新对行和列进行微调以满足双随机条件。这可以保持矩阵的稀疏性，但需要精心设计截断和再平衡算法。 - 子图采样与聚合：对于图学习任务，可以采用邻居采样（如GraphSAGE）或子图采样（如Cluster-GCN）的方法。我们可以在每个采样的子图或每个节点的邻居集合内部进行局部Sinkhorn归一化。虽然这破坏了全局的双随机性，但在局部范围内依然保持了流入流出的平衡，是一种行之有效的折衷。在我的大规模图训练中，我常在每个mini-batch的子图内部进行5次Sinkhorn迭代，效果比直接使用对称归一化或均值聚合更好。
- 学习化的近似：我们可以不显式计算双随机矩阵，而是设计一个参数化的边权重预测网络，并通过对预测的权重施加行和与列和的软约束（作为正则化项加入损失函数），让模型自己学习到一个近似双随机化的注意力机制。这结合了Attention的思想和双随机的约束。
5.2 不只是邻接矩阵：特征双随机化
一个更有趣的思路是将双随机的思想应用到特征传播上，而不仅仅是结构传播。我们不是归一化邻接矩阵，而是归一化一个由节点特征相似度构建的“特征亲和矩阵”。例如，可以先计算一个基于特征的点积相似度矩阵S = HH^T，然后对这个非负的S进行Sinkhorn双随机化，得到一个“特征双随机矩阵”，再用它来进行消息传递。这相当于在特征空间进行了一种均衡化的注意力传播，对于特征异质性高的图可能特别有效。不过，这同样面临稠密矩阵的计算挑战，需要借助采样或低秩近似。
5.3 融合策略：如何嵌入现有GNN架构
双随机归一化不是一个独立的模型，而是一个预处理步骤或层间操作。如何将它融入现有流程？
- 预处理静态矩阵：对于静态图，可以离线计算好双随机归一化邻接矩阵
P_ds，然后将其作为固定的传播矩阵使用，替代GCN中的D^(-1/2) A D^(-1/2)。这是最简单直接的方式。 - 每层动态计算（小图或采样下）：对于动态图或需要在每层结合当前节点特征的情况，可以在每一层消息传递前，基于当前的邻接关系（或结合特征的注意力权重）动态计算一个双随机矩阵。这更灵活，但计算成本更高。
- 作为正则化项：如前所述，不直接使用双随机矩阵，而是在设计可学习的注意力权重时，在损失函数中加入
(sum_i |row_sum_i - 1| + sum_j |col_sum_j - 1|)这样的正则项，鼓励模型学习到的注意力机制具有双随机性质。
注意：双随机矩阵并非银弹。对于某些本身连接就非常均匀的图（如规则网格），其效果可能不如在幂律分布（存在大量枢纽节点）的社交网络或引文网络上显著。它的主要价值在于为高度异质化的图结构提供了一种结构上的“均衡器”。
6. 总结与个人体会：何时该考虑它？
经过多个项目的实践，我对双随机矩阵的应用形成了以下几点个人体会：
它最适合的场景是：
- 深层GNN训练：当你需要堆叠超过3层甚至更多层时，过平滑成为主要矛盾，双随机矩阵作为一个强结构正则化器，往往比简单的残差连接或跳跃连接更能从根源上延缓平滑。
- 图结构高度异质：图中存在明显的“超级节点”（度远高于平均），这类节点容易主导信息传播。双随机矩阵能有效抑制其影响力。
- 对节点特征区分度要求高的任务：如节点分类、图匹配等，特征的可区分性至关重要。
你需要权衡的代价：
- 计算开销：Sinkhorn迭代引入了额外的计算，尤其是对于稠密矩阵。对于超大图，必须使用近似方法。
- 稀疏性丧失：迭代过程可能产生大量极小的非零元，破坏稀疏性，增加内存和计算负担。需要配套的截断策略。
- 不一定总是提升：在一些简单的浅层GNN或结构均匀的图上，其收益可能不明显，甚至因为过度平滑了局部结构而带来轻微的性能下降。它更像是一个为特定问题（深度、过平滑、异质结构）准备的专用工具。
我的建议是，将其作为你GNN工具箱中的一个可选组件。当你的模型在加深后出现性能瓶颈，怀疑是过平滑所致时，不妨尝试将传统的归一化邻接矩阵替换为双随机归一化版本。从离线预处理一个小型数据集开始，观察训练损失曲线和节点表征的相似度矩阵变化，你会直观地感受到它如何让节点特征在深度传播中保持“活力”。这个过程本身，也是对图信号传播理论一次深刻的理解。