图归一化：可微分最大权重独立集的快速二值化动态系统

# 图归一化：用于可微最大权独立集的快速二值化动力学
来源：https://arxiv.org/html/2605.05330

###### 摘要

我们提出了图归一化（Graph Normalization, GN），这是一种在图上的原则性动力系统，作为NP难的最大权独立集（Maximum Weight Independent Set, MWIS）问题的可微近似引擎。MWIS涵盖了一类广泛的组合挑战，包括最优分配、调度、集合打包以及离散马尔可夫随机场中的最大后验（MAP）推理。与信念传播（Belief Propagation）不同，我们证明了GN总是收敛到最大独立集（Maximum Independent Set, MIS）的二值指示向量。GN通过精确的主要化-最小化（Majorization-Minimization）步骤实现了快速的拟牛顿下降，系统地改善了MWIS松弛对偶目标。我们建立了GN与非线性演化博弈的复制子动力学（Replicator Dynamics）之间的等价关系，其中节点竞争以被包含在独立集中。尽管这是一种非势博弈，GN博弈遵循费希尔自然选择基本定理，其中平均适应度等于MWIS对偶目标，并随时间严格增加。这种联系导致了Motzkin-Straus定理的加权推广，表明MIS与倾斜单纯形上二次型的局部最小值之间存在双射关系。对于分配问题，GN充当Sinkhorn算法的一种变体，自然地收敛到硬分配，同时泛化到二分匹配之外的任意约束图。我们展示了GN作为最先进Bregman-Sinkhorn松弛MWIS求解器的快速二值化引擎的性能。在多达100万条边的现实基准测试中，GN在笔记本电脑CPU上几秒钟内找到的解决方案与已知最佳结果仅相差11%以内。GN为需要可微、受约束的“硬”决策的深度神经网络架构开辟了新的途径，潜在应用包括结构化稀疏注意力、动态网络剪枝和混合专家（Mixture-of-Experts）模型。在核心AI之外，GN框架为计算机视觉、计算生物学和资源分配等领域中受约束优化任务的端到端学习提供了基础。

## 1 引言

最大权独立集（MWIS）问题——在图中选择总权重最大的不相邻节点集合——是组合优化的基石。它在补图中等价于最大权团（Maximum Weight Clique, MWC）问题，并直接包含了二分图匹配及其$n$维扩展、$k$-着色、最大权集合打包、多维背包问题和不完全图匹配Bunke (1997) (https://arxiv.org/html/2605.05330#bib.bib12)等经典问题。此外，它还是离散马尔可夫随机场中MAP推理Sanghavi et al. (2009) (https://arxiv.org/html/2605.05330#bib.bib106)、Max-SAT归约Karp (1972) (https://arxiv.org/html/2605.05330#bib.bib28)以及分布式约束优化（DCOP）Fioretto et al. (2018) (https://arxiv.org/html/2605.05330#bib.bib20)的关键框架。许多现实世界的问题都可以表述为MWIS实例，范围从物流和车辆路径规划Dumas et al. (1991) (https://arxiv.org/html/2605.05330#bib.bib5)、电信中的无线链路调度Tassiulas and Ephremides (1990) (https://arxiv.org/html/2605.05330#bib.bib7)到地图标签放置Verweij and Aardal (1999) (https://arxiv.org/html/2605.05330#bib.bib112)。在计算机视觉领域，这包括图像分割Brendel and Todorovic (2010) (https://arxiv.org/html/2605.05330#bib.bib107)、3D重建Zhuo et al. (2016) (https://arxiv.org/html/2605.05330#bib.bib156)、多目标跟踪Papageorgiou and Salpukas (2009) (https://arxiv.org/html/2605.05330#bib.bib115)以及动作识别Yu and Yuan (2015) (https://arxiv.org/html/2605.05330#bib.bib138)。在生物科学中，MWIS解决了分子序列比对Kececioglu (1993) (https://arxiv.org/html/2605.05330#bib.bib19)、药物发现Banchi et al. (2020) (https://arxiv.org/html/2605.05330#bib.bib8)和基因组序列组装Laso-Jadarte et al. (2020) (https://arxiv.org/html/2605.05330#bib.bib18)的问题，而在经济学中，它为求解组合拍卖De Vries and Vohra (2003) (https://arxiv.org/html/2605.05330#bib.bib153)提供了基础，并用于建模投资组合管理Bettinelli et al. (2017) (https://arxiv.org/html/2605.05330#bib.bib6)。

尽管其重要性 fundamental，但MWIS是NP难的且难以近似Garey and Johnson (1979) (https://arxiv.org/html/2605.05330#bib.bib148)，使得现代应用中遇到的大规模现实图难以求得精确解。传统方法通常依赖于相关二元线性规划（BLP）的LP松弛Haller et al. (2024) (https://arxiv.org/html/2605.05330#bib.bib83)；然而，弥合分数解与可行整数赋值（即MWIS问题的实际解）之间的差距仍然是一个重大挑战，并且通常是计算瓶颈。即使是使用图神经网络（GNNs）的现代基于学习的方法，如Karalias and Loukas (2020) (https://arxiv.org/html/2605.05330#bib.bib21)，通常也是求解问题的连续松弛，并遭受相同的二值化缺陷：它们不能保证有效的二值输出，需要事后贪心启发式方法。它们也无法提供经典优化框架中严格的优化间隙保证。

另一个根本性挑战是将MWIS求解器集成到深度学习管道中，以实现受约束任务的端到端学习。经典的组合算法是过程性的且不可微，阻碍了它们在基于梯度的学习中的直接使用。虽然黑盒微分Pogančić et al. (2019) (https://arxiv.org/html/2605.05330#bib.bib11)通过扰动输入来规避这一问题，但它带来了高昂的计算开销，并将求解器视为外部预言机而非原生动力学层。或者，强化学习（RL）已被用于将优化视为顺序决策任务Bello et al. (2016) (https://arxiv.org/html/2605.05330#bib.bib3); Khalil et al. (2017) (https://arxiv.org/html/2605.05330#bib.bib4)；然而，RL存在显著的样本效率低下和高方差问题，使其在计算上难以承受本工作中涉及的生产规模图。虽然信念传播（BP）是可微的，但在包含环的图上因其著名的不收敛性而备受诟病Sanghavi et al. (2009) (https://arxiv.org/html/2605.05330#bib.bib106)。据我们所知，唯一提供保证收敛到有效二值输出且无需外部退火调度的原生可微MWIS框架是Bomze及其同事的复制子动力学方法Bomze (1997) (https://arxiv.org/html/2605.05330#bib.bib57)。我们在第5节详细阐述了我们的方法与Bomze方法之间的关系，以及为什么GN提供更优越的可扩展性。

关键在于，可微组合优化最突出的成功案例——Sinkhorn-Knopp (SK) 算法——本质上是限制在二分图上的MWIS求解器。确实，二分图匹配（BGM），也称为分配问题——在两个集合之间寻找最大化匹配总权重的1:1匹配，等价于线图$L(K_{n,n})$中的MWIS，其中节点和边的角色相对于完全二分图$K_{n,n}$进行了交换。BGM是MWIS的一个简单子问题：它可以在多项式时间内求解，例如通过Kuhn的匈牙利算法Kuhn (1955) (https://arxiv.org/html/2605.05330#bib.bib149)。在他们开创性的工作中，Sinkhorn和Knopp证明了对具有完全支撑的非负矩阵进行交替的行和列归一化收敛于双随机矩阵Sinkhorn and Knopp (1967) (https://arxiv.org/html/2605.05330#bib.bib117)，即分配问题的“软”/松弛解。Sinkhorn-Knopp与“硬”分配问题之间的关系历史上是通过统计物理的视角来导航的，最著名的例子是SoftAssignGold et al. (1996) (https://arxiv.org/html/2605.05330#bib.bib125)和Graduated AssignmentGold and Rangarajan (1996) (https://arxiv.org/html/2605.05330#bib.bib124)框架。这些方法利用确定性退火通过最小化自由能函数来求解分配问题Yuille et al. (1990) (https://arxiv.org/html/2605.05330#bib.bib31); Kosowsky and Yuille (1994) (https://arxiv.org/html/2605.05330#bib.bib123)；随着“温度”参数向0温度极限降低，软解被迫收敛到“清晰”的置换矩阵Rangarajan et al. (1997) (https://arxiv.org/html/2605.05330#bib.bib98)。这一脉络为最优传输（OT）的现代突破奠定了理论基础，其中Sinkhorn算法为Kantorovich问题的严格凸松弛提供了高效解Cuturi (2013) (https://arxiv.org/html/2605.05330#bib.bib38)。从数学上讲，Sinkhorn迭代充当Bregman投影——最小化向约束集的Kullback-Leibler散度——其中熵惩罚有效地充当退火温度的倒数Cuturi (2013) (https://arxiv.org/html/2605.05330#bib.bib38); Genevay (2019) (https://arxiv.org/html/2605.05330#bib.bib100)。OT在机器学习社区中的普及反过来确立了“Sinkhorn层”作为各种神经架构中基础即插即用模块的地位——从可微排名Adams and Zemel (2011) (https://arxiv.org/html/2605.05330#bib.bib40); Mena et al. (2018) (https://arxiv.org/html/2605.05330#bib.bib41)、图对齐Zanfir and Sminchisescu (2018) (https://arxiv.org/html/2605.05330#bib.bib139)、图像匹配Sarlin et al. (2020) (https://arxiv.org/html/2605.05330#bib.bib22)到多人3D姿态跟踪Reddy et al. (2021) (https://arxiv.org/html/2605.05330#bib.bib23)。

Sinkhorn动力学的效用在大语言模型（LLMs）中显而易见；混合专家（MoE）和流形约束超连接Xie et al. (2025) (https://arxiv.org/html/2605.05330#bib.bib34)利用SK迭代来稳定训练并强制执行平衡的标记路由Clark et al. (2022) (https://arxiv.org/html/2605.05330#bib.bib37); DeepSeek-AI (2024) (https://arxiv.org/html/2605.05330#bib.bib33)。尽管取得了成功，SK从根本上受限于其底层二分拓扑，主要解决分配问题及其多维泛化Altschuler and Boix-Adsera (2023) (https://arxiv.org/html/2605.05330#bib.bib94)。虽然SK对于1:1匹配很有效，但它无法原生解决一般关系数据中存在的复杂多方冲突，除非进行人为的二分化处理，如图匹配中的SoftAssign算法Gold and Rangarajan (1996) (https://arxiv.org/html/2605.05330#bib.bib124)。此外，SK通常在Birkhoff单纯形内产生软分配，需要通过敏感的退火调度使熵正则化趋于零才能恢复离散解Rangarajan et al. (1999) (https://arxiv.org/html/2605.05330#bib.bib32)。

在本文中，我们引入了图归一化（GN），这是一种原则性的动力系统，通过将类似Sinkhorn的归一化动力学泛化到任意约束图，克服了这些拓扑限制。我们表明，GN通过精确的主要化-最小化步骤实现了快速的拟牛顿下降，该步骤在数学上被证明总是收敛到最大独立集的二值指示向量，从而消除了对事后启发式方法或敏感退火调度的需求。我们建立了GN与非线性演化博弈的复制子动力学之间的形式等价关系，其中平均种群适应度等同于MWIS对偶目标，并证明随时间严格增加。经验上，我们展示了GN作为最先进Bregman-Sinkhorn分数MWIS算法Haller et al. (2024) (https://arxiv.org/html/2605.05330#bib.bib83)提供的松弛解的高速二值化引擎的效率，在具有数百万条边的生产规模图上产生高质量解。作为*可微*MWIS引擎，GN解锁了复杂受约束任务的端到端学习，弥合了组合优化、理论博弈论和现代神经架构的结构需求之间的差距。

## 2 图归一化：定义和基本性质

我们将$\mathbb{R}_+^n$和$\mathbb{R}_{++}^n$分别记为非负正交限和正正交限。如果$x \in \mathbb{R}_+^n$，我们写$x \geq 0$；如果$x \in \mathbb{R}_{++}^n$，我们写$x > 0$。对于$x, y \in \mathbb{R}_{++}^n$，$x \odot y$和$x \oslash y$分别表示逐元素乘法和除法。设$G=(V,E)$是一个简单无向图，其中$|V|=n$，邻接矩阵$A \in \{0,1\}^{n \times n}$，满足$A_{ii}=0$因为$G$是简单的。我们将$V$与$\{1 \dots n\}$等同，并将$G$与其邻接矩阵等同。对于向量$x \in \mathbb{R}_+^n$，$\operatorname{supp}(x)=\{i: x_i > 0\} \subseteq V$是其*支撑*。相反，如果$S \subseteq V$，则$\mathbf{1}_S$表示其*指示向量*，它是二值的，并满足$(\mathbf{1}_S)_i=1 \Leftrightarrow i \in S$。假设$\operatorname{supp}(\mathbf{1}_S)=S$，我们将每个子集$S \subseteq V$与其指示向量$\mathbf{1}_S \in \{0,1\}^n$等同。向量$x \in [0,1]^n$可以解释为顶点集$V$上的*模糊集*成员资格向量。当$x \in \{0,1\}^n$是二值时，它是顶点*清晰*子集$S \subset V$的指示向量$\mathbf{1}_S$。$S \subset V$是*独立集（IS）*，$S \in \mathsf{IS}$，如果$S$中没有两个元素在$A$中是邻居，即，对于所有$(i,j) \in S^2$，$A_{ij}=0$，或者等价地，$\mathbf{1}_S^T A \mathbf{1}_S=0$。如果$S$不包含在另一个IS中，则IS $S$是*最大独立集（MIS）*，$S \in \mathsf{MIS}$。对于任何节点$i \in V$，$N(i):=\{j \in V: A_{ij}=1\}$是其*邻域*。我们用$A_I := A+I$表示*闭邻接矩阵*，其中单位矩阵$I$的加法对应于每个顶点自环的包含，使得$(A_I)_{ii}=1$。对于向量$x \in \mathbb{R}_+^n$，值$(A_I x)_i = x_i + \sum_{j \in N(i)} x_j$称为*闭邻域和*。

###### 定义 1。

如果且仅当$A_I x > \mathbf{0}$时，向量$x \in \mathbb{R}_+^n$在图$A$上是*可归一化*的。$\mathsf{N}_A := \{x \in \mathbb{R}_+^n : A_I x > \mathbf{0}\}$表示图$A$上可归一化向量的集合。不可归一化向量是在某些闭邻域上恒为零的向量，即，对于某些节点$i$，$x_i=0$以及其所有邻居。

###### 定义 2。

*图归一化（GN）*映射$\mathcal{N}_A: \mathsf{N}_A \to [0,1]^n$