面向网络对齐的可扩展最优传输算法

# 面向网络对齐的可扩展最优传输算法
Source: https://arxiv.org/html/2607.11952

,Durga Mandarapu∗Lawrence Berkeley National LaboratoryCAUSAdurga@lbl\.gov (https://arxiv.org/html/2607.11952v1/mailto:[email protected]),Qi YuUniversity of Illinois at Urbana\-ChampaignILUSAqiyu6@illinois\.edu (https://arxiv.org/html/2607.11952v1/mailto:[email protected]),Hanghang TongUniversity of Illinois at Urbana\-ChampaignILUSAhtong@illinois\.edu (https://arxiv.org/html/2607.11952v1/mailto:[email protected]) and Ariful AzadTexas A&M UniversityTXUSAariful@tamu\.edu (https://arxiv.org/html/2607.11952v1/mailto:[email protected])

###### 摘要。

网络对齐识别跨网络的节点对应关系，是许多数据科学应用中的基本原语，包括社交网络分析、欺诈检测和知识图谱集成。然而，最先进的网络对齐方法通常通过反复构建和更新稠密矩阵来实现高精度，但牺牲了可扩展性。为了解决这一可扩展性瓶颈而不影响对齐精度，我们提出了FastAlign，一个面向基于最优传输的网络对齐的可扩展、稀疏感知框架。FastAlign并非引入新的对齐模型，而是保留原始OT公式，并将其计算重新解释为一组反复出现的混合稀疏-稠密操作。FastAlign将稀疏感知图计算与领域特定内核融合相结合，包括一个自定义的SpMM内核。我们的结果表明，FastAlign实现了与最先进的基于OT的方法相当的对齐质量，同时大幅减少了端到端运行时间：在CPU上加速高达3.89×–9.45×，在GPU上加速2.24×–32.54×。

\*\*\*这些作者贡献相同。

## 1. 引言

网络对齐的目标是识别两个网络之间的节点对应关系。它是许多应用中跨源集成图结构数据的基本原语，包括社交网络分析 (Cao and Yu,2016 (https://arxiv.org/html/2607.11952#bib.bib11))、欺诈检测 (Duet al.,2021 (https://arxiv.org/html/2607.11952#bib.bib10)) 和知识图谱 (Wanget al.,2018 (https://arxiv.org/html/2607.11952#bib.bib12))。例如，跨社交平台对齐用户支持跨平台推荐；跨交易网络匹配实体有助于检测可疑活动；跨不完整知识图谱对齐实体能够构建统一的知识库。随着现代网络规模的扩大以及动态网络需要反复重新对齐，对齐算法必须既精确又快速。

现有的网络对齐方法在可扩展性和精度之间存在权衡 (图1 (https://arxiv.org/html/2607.11952#S1.F1))。基于一致性的方法使用两个网络之间的快速线性变换，但由于未能充分捕捉全局结构，其精度较差 (Zhang and Tong,2016 (https://arxiv.org/html/2607.11952#bib.bib4))。基于嵌入的方法通过学习节点表示提高了精度，但代价是深度表示学习导致运行时间更长 (Yanet al.,2021 (https://arxiv.org/html/2607.11952#bib.bib3); Zhanget al.,2020 (https://arxiv.org/html/2607.11952#bib.bib5),2021 (https://arxiv.org/html/2607.11952#bib.bib6))。基于最优传输 (OT) 的方法通过优化一个结合节点相似性、结构一致性、邻域一致性和锚点监督的传输目标，实现了最先进的 (SOTA) 经验精度 (Zenget al.,2023 (https://arxiv.org/html/2607.11952#bib.bib8); Yuet al.,2025b (https://arxiv.org/html/2607.11952#bib.bib7); Zenget al.,2024 (https://arxiv.org/html/2607.11952#bib.bib2); Tanget al.,2023 (https://arxiv.org/html/2607.11952#bib.bib9))。这种精度伴随着其自身的可扩展性限制，因为基于OT的方法在多次迭代中反复构建和更新稠密的跨网络成本和对齐矩阵，使得它们在运行时间和内存方面都非常昂贵。

10410^\{4\}10510^\{5\}10610^\{6\}0.40.40.60.60.80.8时间 (秒)MRRFastAlignFINALBRIGHTNetTransJOENAPARROTSLOTAlign

图1. 在ACM-DBLP网络上各网络对齐方法的MRR（精度）与运行时间对比。FINAL是基于一致性的，BRIGHT和NetTrans是基于嵌入的，其余是基于OT的方法。

为了解决这一可扩展性瓶颈而不牺牲对齐精度，我们提出了FastAlign，一个面向基于OT的网络对齐的可扩展稀疏感知框架。FastAlign并非引入新的对齐模型，而是保留原始OT公式，并将其计算重新解释为一组反复出现的混合稀疏-稠密操作。这种重新解释揭示了何处可以利用图稀疏性，以及何处必须针对内存效率优化稠密的跨网络操作。FastAlign通过使用稀疏感知图操作和内存高效的内核融合来实现这种分解，以减少内存流量并避免不必要的中间物化。因此，FastAlign加速并扩展了基于OT的网络对齐，使其在大图规模下变得实用。

基于这种重新解释，FastAlign结合了四种优化。首先，它使用稀疏感知计算来替换所有涉及图结构的稠密矩阵计算。第二，它引入了一个自定义的稀疏-稠密矩阵乘法 (SpMM) 算法，用于将稀疏矩阵与宽稠密矩阵相乘，这在基于OT的对齐中出现，与通用SpMM设置中稠密矩阵高且瘦的情况不同。第三，它使用领域特定的内核融合来合并一系列内存受限的操作，以减少中间物化和内存流量。第四，其GPU实现将数据保留在设备上，并在各阶段重用稠密矩阵，以避免不必要的数据移动，并分块内核以实现优化性能。

我们在CPU和GPU上实现FastAlign，并在一系列真实世界和合成网络对齐数据集上对其进行评估。我们的结果表明，FastAlign实现了与SOTA基于OT的方法相当的对齐质量，同时大幅减少了端到端运行时间。

总之，本文做出了以下贡献：

- •我们提出了FastAlign，一个面向基于OT的网络对齐的可扩展稀疏感知框架，保留了对齐精度，同时提高了运行时间和内存效率。
- •我们使用混合稀疏-稠密操作对基于OT的网络对齐进行了计算重新解释。
- •我们开发了稀疏感知图计算，包括自定义SpMM内核和相邻内存受限操作的融合，以加速基于OT的网络对齐。
- •通过大量实验，我们证明相对于SOTA网络对齐算法，FastAlign在CPU上实现了3.89×–9.45×的加速，在GPU上实现了2.24×–32.54×的加速。

## 2. 背景

设G1=(V1,E1,A1){\mathbf G}_{1}=({\mathbf V}_{1},{\mathbf E}_{1},{\mathbf A}_{1}) 和 G2=(V2,E2,A2){\mathbf G}_{2}=({\mathbf V}_{2},{\mathbf E}_{2},{\mathbf A}_{2}) 表示两个网络，其中 |V1|=n1|{\mathbf V}_{1}|=n_{1}, |V2|=n2|{\mathbf V}_{2}|=n_{2}，邻接矩阵分别为 A1∈Rn1×n1{\mathbf A}_{1}\in\mathbb R^{n_{1}\times n_{1}} 和 A2∈Rn2×n2{\mathbf A}_{2}\in\mathbb R^{n_{2}\times n_{2}}。节点可选地携带属性，编码为 X1∈Rn1×d{\mathbf X}_{1}{\in}\mathbb R^{n_{1}\times d} 和 X2∈Rn2×d{\mathbf X}_{2}\in\mathbb R^{n_{2}\times d}。我们还给定一组锚点对 L⊆V1×V2{\mathcal L}\subseteq{\mathbf V}_{1}\times{\mathbf V}_{2}，其中每对表示两个网络之间已知的对应关系。网络对齐计算一个软对齐矩阵 S∈Rn1×n2{\mathbf S}\in\mathbb R^{n_{1}\times n_{2}}，其中 Sij{\mathbf S}_{ij} 表示节点 i∈V1i\in{\mathbf V}_{1} 与节点 j∈V2j\in{\mathbf V}_{2} 对应的可能性分数。图2 (https://arxiv.org/html/2607.11952#S2.F2) 说明了网络对齐问题。现有方法可分为基于一致性、基于嵌入或基于OT的方法 (Zhang and Tong,2020 (https://arxiv.org/html/2607.11952#bib.bib21))。其中，基于OT的方法持续达到SOTA性能 (Yuet al.,2025a (https://arxiv.org/html/2607.11952#bib.bib1))，我们的算法建立在该范式之上。因此，我们在本节详细说明基于OT的方法，其余方法推迟到第5节 (https://arxiv.org/html/2607.11952#S5)。

### 2.1. 用于网络对齐的最优传输

最优传输 (OT) 通过最小化总传输成本（即Wasserstein距离）将一个离散分布映射到另一个分布 (Peyré and Cuturi,2019 (https://arxiv.org/html/2607.11952#bib.bib13))。基于OT的网络对齐将节点集 V1{\mathbf V}_{1} 和 V2{\mathbf V}_{2} 视为离散分布，具有均匀质量向量 μ=1n11n1{\bm \mu}=\tfrac{1}{n_{1}}{\mathbf 1}_{n_{1}} 和 ν=1n21n2{\bm \nu}=\tfrac{1}{n_{2}}{\mathbf 1}_{n_{2}}。软对齐矩阵 S{\mathbf S} 对应于OT传输计划，其条目 Sij{\mathbf S}_{ij} 表示从节点 i∈V1i\in{\mathbf V}_{1} 路由到节点 j∈V2j\in{\mathbf V}_{2} 的质量量，并解释为它们对应关系的强度。给定一个成本矩阵 C∈Rn1×n2{\mathbf C}\in\mathbb R^{n_{1}\times n_{2}}，编码每对节点对齐的惩罚，最优对齐通过求解下式获得：

(1) minS∈Π(μ,ν)⟨S,C⟩−εH(S),\min_{{\mathbf S}\in\Pi({\bm \mu},{\bm \nu})}\;\langle{\mathbf S},{\mathbf C}\rangle-\varepsilon\,H({\mathbf S}), 其中 ⟨⋅⟩\langle\cdot\rangle 表示Frobenius内积，Π(μ,ν)={S∈R≥0n1×n2:S1=μ,S⊤1=ν}\Pi({\bm \mu},{\bm \nu})=\{{\mathbf S}\in\mathbb R_{\geq 0}^{n_{1}\times n_{2}}:{\mathbf S}{\mathbf 1}={\bm \mu},\;{\mathbf S}^{\top}{\mathbf 1}={\bm \nu}\} 是可行软对齐的集合，ε>0\varepsilon>0 控制熵正则化项 H(S)H({\mathbf S}) 的强度，该正则化使问题严格凸，并且可以通过Sinkhorn算法高效求解 (Cuturi,2013 (https://arxiv.org/html/2607.11952#bib.bib15))。式 (1) (https://arxiv.org/html/2607.11952#S2.E1) 中的目标由两个设计选择决定：如何构造成本矩阵 C{\mathbf C} 以及如何求解得到的优化问题。我们依次讨论。

参照图注图2. 网络对齐问题。给定两个带属性网络 G1{\mathbf G}_{1} 和 G2{\mathbf G}_{2} 以及一组锚点链接，网络对齐寻找网络中节点的对应关系。

### 2.2. 成本矩阵的分解

成本矩阵 C{\mathbf C} 的设计最直接影响对齐质量。设计良好的成本共同捕捉三个一致性原则以及先验锚点知识 (Zenget al.,2023 (https://arxiv.org/html/2607.11952#bib.bib8))。*节点一致性* (Cnode{\mathbf C}_{\text{node}}) 要求匹配的节点在其各自网络内具有相似的属性和相似的结构位置。*边一致性* (Cedge{\mathbf C}_{\text{edge}}) 要求匹配的节点对保持其连接边。*邻域一致性* (Cnbr{\mathbf C}_{\text{nbr}}) 要求匹配的节点具有匹配的邻域，使得一个图中的邻居映射到另一个图中的邻居。最后，成本应反映先验锚点偏好 (Canc{\mathbf C}_{\text{anc}})，使对齐偏向已知对应关系 (Zenget al.,2023 (https://arxiv.org/html/2607.11952#bib.bib8))。整体成本矩阵按加性方式组合这些项，其中 λe,λn,λa≥0\lambda_{e},\lambda_{n},\lambda_{a}\geq 0 权衡各项的贡献：

(2) C=Cnode+λeCedge+λnCnbr+λaCanc{\mathbf C}={\mathbf C}_{\text{node}}\;+\;\lambda_{e}\,{\mathbf C}_{\text{edge}}\;+\;\lambda_{n}\,{\mathbf C}_{\text{nbr}}\;+\;\lambda_{a}\,{\mathbf C}_{\text{anc}}

### 2.3. OT求解器

给定当前成本矩阵 C{\mathbf C} 和预定义的边际向量 μ,ν{\bm \mu},{\bm \nu}，Sinkhorn算法通过迭代重新缩放其行和列来计算对齐矩阵 S{\mathbf S}，以满足边际约束，同时保持对齐成本低。该算法维护两个对偶向量 a{\mathbf a} 和 b{\mathbf b}，并在对数域中交替更新它们（为了数值稳定性）：

(3) aj=εlogνj−εLSEi(bi−Cijε),bi=εlogμi−εLSEj(aj−Cijε)a_{j}=\varepsilon\log\nu_{j}-\varepsilon\operatorname*{LSE}_{i}\!\left(\tfrac{b_{i}-{\mathbf C}_{ij}}{\varepsilon}\right),\quad b_{i}=\varepsilon\log\mu_{i}-\varepsilon\operatorname*{LSE}_{j}\!\left(\tfrac{a_{j}-{\mathbf C}_{ij}}{\varepsilon}\right) 其中 LSE 是 log-sum-exp 规约。收敛后，对齐矩阵恢复为：

(4) Sij=exp(aj+bi−Cijε).{\mathbf S}_{ij}=\exp\!\left(\frac{a_{j}+b_{i}-{\mathbf C}_{ij}}{\varepsilon}\right). 式 (4) (https://arxiv.org/html/2607.11952#S2.E4) 给出了当前 C{\mathbf C} 的最优对齐。由于 C{\mathbf C} 的某些组件本身依赖于 S{\mathbf S}，因此使用新计算的对齐更新成本，并重复Sinkhorn求解。这种交替实现了约束近端点方法 (Xieet al.,2020 (https://arxiv.org/html/2607.11952#bib.bib16))，该方法将问题求解为一系列固定成本OT子问题，并保证收敛。

## 3. 扩展基于OT的网络对齐

在本节中，我们介绍FastAlign，一个可扩展且快速的网络对齐框架。FastAlign通过一个有意的两阶段流水线实现加速。首先，它将基于OT的对齐重新表述为一系列在具有明确形状和稀疏性的矩阵上的线性代数操作。其次，它使用自定义稀疏算法、内核融合以及在CPU和GPU上的硬件映射并行实现来加速这些内核。这种两阶段框架是必要的，因为初始的线性代数分解揭示了通常被第2节 (https://arxiv.org/html/2607.11952#S2) 中描述的常规OT公式所隐藏的优化路径。

### 3.1. FastAlign的基础：网络对齐的线性代数分解

为了将基于OT的算法分解为线性代数形式，我们首先观察到第2节 (https://arxiv.org/html/2607.11952#S2) 中描述的计算可以分为三个阶段：(a) 第一阶段归一化邻接矩阵并计算对齐无关的成本分量 Cnode{\mathbf C}_{\text{node}} 和 Canc{\mathbf C}_{\text{anc}}；(b) 第二阶段计算对齐相关分量 Cedge{\mathbf C}_{\text{edge}} 和 Cnbr{\mathbf C}_{\text{nbr}}；(c) 第三阶段调用OT求解器从当前成本矩阵产生对齐。FastAlign的这三个阶段在算法1 (https://arxiv.org/html/2607.11952#alg1) 和图3 (https://arxiv.org/html/2607.11952#S3.F3) 中描述。

算法 1 FastAlign：基于OT网络对齐的线性代数视角
1: 图 G1,G2{\mathbf G}_{1},{\mathbf G}_{2}；属性 X1,X2{\mathbf X}_{1},{\mathbf X}_{2}；锚点 L{\mathcal L}
2: 对齐矩阵 S{\mathbf S}
3: Aˉ1←normalize(A1)\bar{\mathbf A}_{1}\gets \text{normalize}({\mathbf A}_{1}); Aˉ2←normalize(A2)\bar{\mathbf A}_{2}\gets \text{normalize}({\mathbf A}_{2})
4: Cnode←cost_node(X1,X2){\mathbf C}_{\text{node}}\gets \text{cost\_node}({\mathbf X}_{1},{\mathbf X}_{2})
5: Canc←cost_anchor(L){\mathbf C}_{\text{anc}}\gets \text{cost\_anchor}({\mathcal L})
6: for t=1…Tt=1\dots T do
7:    Cedge←sparse_fused_cost(S,Aˉ1,Aˉ2){\mathbf C}_{\text{edge}}\gets \text{sparse\_fused\_cost}({\mathbf S},\bar{\mathbf A}_{1},\bar{\mathbf A}_{2})
8:    Cnbr←sparse_batched_cost(S,Aˉ1,Aˉ2){\mathbf C}_{\text{nbr}}\gets \text{sparse\_batched\_cost}({\mathbf S},\bar{\mathbf A}_{1},\bar{\mathbf A}_{2})
9:    C←Cnode+λeCedge+λnCnbr+λaCanc{\mathbf C}\gets {\mathbf C}_{\text{node}}+\lambda_{e}{\mathbf C}_{\text{edge}}+\lambda_{n}{\mathbf C}_{\text{nbr}}+\lambda_{a}{\mathbf C}_{\text{anc}}
10:   S←sinkhorn(C,μ,ν){\mathbf S}\gets \text{sinkhorn}({\mathbf C},{\bm \mu},{\bm \nu})
11: end for
12: S{\mathbf S}