Chaining 2-FWL GNNs for Combinatorial Graph Alignment¶

会议: NeurIPS 2026
arXiv: 2510.03086
代码: https://github.com/mlelarge/chaining-gnn-graph-alignment
领域: 图学习
关键词: 图对齐, 二次分配问题, 图神经网络, 2-FWL, 组合优化

一句话总结¶

针对纯结构无属性的无标签图组合对齐难题，本文提出串联 2-FWL 表达能力的 Folk-GNN 并引入离散匹配质量排名的链式迭代训练与推理机制，不仅打破了 MPNN 在正则图上的表达力屏障，更通过为经典凸松弛 FAQ 算法提供高质量初始相似度矩阵，在稀疏随机图与正则图上将对齐准确率大幅提升至 SOTA。

研究背景与动机¶

组合图对齐问题（Graph Alignment Problem, GAP）目标是在两个无节点属性的无标签图之间寻找节点置换，以最大化重合边数（Number of Common Edges, NCE）。该问题形式上等价于二次分配问题（Quadratic Assignment Problem, QAP），不仅将图同构判定作为特例包含在内，在一般图结构下更归约为最大公共子图匹配与哈密顿回路等 NP-hard 乃至 APX-hard 问题。十余年来，基于 Frank-Wolfe 优化的经典松弛算法 FAQ（Fast Approximate Quadratic）一直垄断着组合图对齐基准的领先地位；然而，FAQ 的最终表现极度敏感于初始化矩阵，传统从凸松弛极值点初始化的策略在强噪声或复杂拓扑结构下极易陷入低劣的局部极值。

近年来机器学习与图神经网络（GNN）在组合优化领域蓬勃发展，但在纯拓扑结构（无外源语义特征）的图对齐任务中却屡遭挫折。核心痛点主要源于两重严重瓶颈：其一，传统消息传递图神经网络（MPNN）受限于 1-WL（Weisfeiler-Lehman）同构测试能力上限，在缺乏区分性节点特征时，面对如 $d$-正则图（Regular Graphs）等高度局部对称结构，只能输出完全一致的节点嵌入，1-WL 无法产生任何颜色细化，导致计算出的相似度矩阵退化为完全无信息的均匀矩阵；其二，现有 GNN 匹配方法大多针对端到端单次推断或连续微分共识设计，缺乏针对离散图对齐目标的有效反馈机制，在高噪声稀疏随机图上匹配准确率几乎迅速坍塌至零，远远落后于古典 FAQ 算法。

面对这一矛盾，本文的切入点在于：既然图对齐从本质上是离散决策与二次目标优化的交织，就不能强求单次黑盒前向预测，而应将离散组合反馈作为逐步细化的引导信号，并赋予网络超越 1-WL 的结构分辨力。核心 idea：设计具备 2-FWL 表达能力的残差对表示 FGNN 骨干，通过非微分的线性分配与节点匹配边贡献排序引入链式级联机制（Chaining），在上一步离散对齐质量反馈的引导下逐级序列化训练 GNN，并在推断阶段利用循环自迭代（Looping）与 FAQ 后处理最大化重合边数。

方法详解¶

整体框架¶

组合图对齐旨在寻找置换矩阵 $P \in \mathcal{S}_n$（对应双射 $\pi: V_A \to V_B$），使得两图邻接矩阵 $A, B$ 的重合边数 $\text{nce}(\pi) = \frac{1}{2} \sum_{i,j} A_{ij} B_{\pi(i)\pi(j)}$ 最大化，等价于极小化 Frobenius 范数 $\|AP - PB\|_F^2$。

本文的方法流程是一个迭代式链式级联结构（Chaining Procedure）：首先由基础网络 $f$ 提取图对中节点对的结构表征并计算初始节点相似度矩阵 $S^{A \to B, (0)}$；随后提取离散置换 $\pi = \text{Proj}(S^{A \to B})$，计算每个节点在当前置换下匹配成功的关联边数并生成降序排列的节点质量排序向量 $r^A, r^B$；接着将该离散排名注入后续网络 $g^{(\ell)}$ 中生成融合拓扑与匹配质量的增强相似度矩阵；最后在推断阶段结合基于最佳 NCE 保留的循环自迭代机制与 Frank-Wolfe FAQ 局部精细化算法，输出最终的高质量置换。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入无标签图对<br/>邻接矩阵 A 与 B"] --> B["2-FWL 节点对残差表征网络<br/>双线性成对聚合与池化"]
    B --> C["初阶相似度计算<br/>S = f(A) f(B)^T"]
    C --> D["离散置换提取与节点对齐质量评分<br/>线性分配求解与关联匹配边计数"]
    D --> E["排名嵌入注入与级联细化 GNN<br/>融合相对排序与图结构"]
    E --> F["推断期自迭代循环<br/>贪心保留最优 NCE 候选解"]
    F --> G["FAQ 凸松弛后处理求解<br/>输出最终节点置换矩阵"]

关键设计¶

1. 2-FWL 表达能力的 Folklore 残差对表示架构：突破 1-WL 结构表征上限

传统 MPNN 对节点应用邻居聚合，在 $d$-正则图上若初始特征为常数，所有节点的聚合邻域多重集完全同构，特征无法细化。为此，本文直接在节点对隐状态空间 $(h^t_{i \to j})_{i,j} \in \mathbb{R}^{n \times n \times d}$ 上建立模型，构造能够模拟 2 阶 Folklore Weisfeiler-Lehman（2-FWL）测试能力的残差层： $$h^{t+1}_{i \to j} = h^t_{i \to j} + m_1 \left( h^t_{i \to j}, \sum_{\ell=1}^n h^t_{i \to \ell} \odot m_0(h^t_{\ell \to j}) \right)$$ 其中 $m_0: \mathbb{R}^d \to \mathbb{R}^d$ 与 $m_1: \mathbb{R}^{2d} \to \mathbb{R}^d$ 均为带有 GraphNorm 层的多层感知机（MLP），$\odot$ 表示按元素逐项相乘。与经典 PPGN 在乘法分支两端均配置 MLP 的设计相比，本文在双线性聚合中仅对第二项应用 $m_0$，大幅削减了显存开销与参数量。作者在理论上证明了（定理 A.4）：在采用恒等可实现激活函数（如 ReLU）的前提下，通道宽度为 $4d$ 的 $2K$ 层 FGNN 可以严格精确模拟通道宽度为 $d$ 的 $K$ 层 PPGN，因而 FGNN 在层数加倍后完全继承了 2-FWL 的区分能力。在经过多层残差计算后，网络通过对第二空间维度做最大池化 $\text{node}_i = \max_j h^k_{i \to j}$ 得到节点级嵌入，两图节点内积即可形成交叉相似度矩阵 $S^{A \to B} = f(A)f(B)^\top$。

2. 离散置换解码与节点质量评分排序：在不可导环节注入组合反馈

单步 GNN 往往由于缺乏全局图匹配的结构反馈而难以逼近全局最优。本文利用投影算子 $\pi = \text{Proj}(S^{A \to B}) = \arg\max_{\pi \in \mathcal{S}_n} \sum_i S^{A \to B}_{i, \pi(i)}$（通过匈牙利算法或 Jonker-Volgenant 线性分配在 $O(n^3)$ 时间内精确求解）提取出当前最优置换，并显式计算图 $G_A$ 中每个节点 $i$ 的对齐质量得分： $$\text{score}(i) = \sum_{j=1}^n A_{ij} B_{\pi(i)\pi(j)}$$ 该得分严格统计了在当前猜测置换 $\pi$ 下，节点 $i$ 的相连边中有多少条边与图 $G_B$ 的对应边完美匹配。接着，将图 $G_A$ 的节点按得分降序重排得到置换排列 $r^A \in \mathcal{S}_n$，满足 $\text{score}(r^A(1)) \ge \text{score}(r^A(2)) \ge \dots \ge \text{score}(r^A(n))$；再通过置换映射直接传递给图 $G_B$：$r^B(k) = \pi(r^A(k))$。这一操作将离散组合优化的全局重合状态映射为一维节点排名，为后续网络指明了哪些局部匹配已经极为可信、哪些子图区域存在严重冲突。

3. 相对排名分桶嵌入与级联序列训练：引导连续多阶段正向增益

由于排序操作非连续不可导，无法通过梯度反向传播端到端优化。本文采用序列化贪心训练策略：固定前序网络，利用前级模型对训练图对生成排名 $r^A, r^B$，作为后继网络 $g^{(\ell)}$ 的增强输入。为了让在固定节点规模（如 $n=500$）上训练的模型能泛化到任意尺寸的图，节点 $i$ 在当前图中的严格排位 $k$ 被归一化为相对排名 $\tilde{r} = (k-1)/(n-1) \in [0, 1]$，并通过固定数量的均匀分桶查表获得排名嵌入。在网络输入层，边指示符 $A_{ij}$ 与端点 $i, j$ 的相对排名嵌入联合输入；在池化层之后，节点结构特征与自身排名嵌入拼接并经由非线性投影层变换，最终生成增强的相似度矩阵 $S^{A \to B, (\ell)} = g^{(\ell)}(A, r^A) g^{(\ell)}(B, r^B)^\top$。序列中每个 GNN 都以前序网络产生的更高置信度对齐为脚手架，形成自我引导的自举（Bootstrap）效应。

4. 结合常数保证的自迭代循环（Looping）与 FAQ 凸松弛后处理精化

在推断阶段，模型不仅可以按顺序执行训练好的 $L+1$ 个网络（从 $f$ 到 $g^{(L)}$），还可以将最终训练的网络 $g^{(L)}$ 循环反复应用（Looping）。每一轮循环将当前输出的相似度矩阵再次解码置换、评分并重新送入 $g^{(L)}$，生成新的候选相似度矩阵。关键的是，算法维护一个运行时的最大公共边数记录：仅当新一轮置换产生的 $\text{nce}(\pi)$ 严格超越历史最高值时才予以采纳（上限设为 $N_{\text{loop}}=100$ 次）。这为推断提供了一个理论安全底线——其输出质量绝不劣于单次级联推断。最后，将链式 GNN 输出的高质量相似度矩阵作为 Frank-Wolfe FAQ 算法的初始点 $D_{\text{init}}$，在双随机矩阵多胞形上对二次目标 $\max_{D \in \mathcal{D}_n} \langle AD, DB \rangle$ 进行非凸梯度上升，彻底消除次优局部陷阱。

损失函数 / 训练策略¶

对于合成数据中带有已知真实对齐（Planted Permutation）$\pi^\star$ 的图对 $(G_A, G_B)$，每个网络在固定前序输入的前提下，采用行归一化的交叉熵损失函数进行独立序列训练： $$\mathcal{L}(S^{A \to B}, \pi^\star) = -\sum_{i=1}^n \log \left( \text{softmax}(S^{A \to B}_{i, \cdot}) \right)_{\pi^\star(i)}$$ 该目标驱动相似度矩阵的概率质量向真实对齐节点集中。训练时网络使用 Adam 优化器，初始学习率设为 $10^{-4}$，配合 ReduceLROnPlateau 学习率调度策略（patience=3）。默认采用 2 层残差块，MLP 隐藏层维度为 256。级联深度通常设定为 $L=15$（共 $1+15=16$ 个 FGNN 模型）。

实验关键数据¶

主实验¶

论文在稀疏 Erdős–Rényi 图（平均度 $d=4$）、稠密 Erdős–Rényi 图（平均度 $d=80$）以及 $d=10$ 的正则图（Regular Graphs）上展开全面对比（节点数均为 $n=500$），对比非神经凸松弛投影 $\text{Proj}(D_{\text{cx}})$、凸松弛初始化的古典最强基线 $\text{FAQ}(D_{\text{cx}})$、单步 FGNN 以及链式 FGNN（ChFGNN）。

下表汇报了在不同图类型与噪声级别下的对齐准确率（acc）与重合边数（nce，格式为 acc / nce）：

图结构类型与规模	噪声 $p_{\text{noise}}$	$\text{Proj}(D_{\text{cx}})$	$\text{FAQ}(D_{\text{cx}})$	单步 FGNN-FAQ	链式 ChFGNN-Proj	链式 ChFGNN-FAQ (本文)
稀疏 ER ($d=4$, $\text{nce}_{\max} \approx 1000$)	0.00	0.98 / 997	0.98 / 997	0.98 / 997	0.98 / 997	0.98 / 997
稀疏 ER ($d=4$)	0.10	0.90 / 853	0.96 / 898	0.96 / 898	0.96 / 898	0.96 / 899
稀疏 ER ($d=4$)	0.15	0.59 / 499	0.95 / 847	0.95 / 847	0.94 / 845	0.95 / 849
稀疏 ER ($d=4$)	0.20	0.23 / 195	0.73 / 723	0.81 / 755	0.91 / 790	0.93 / 800
稀疏 ER ($d=4$)	0.25	0.09 / 130	0.13 / 504	0.24 / 535	0.82 / 720	0.85 / 742
稀疏 ER ($d=4$)	0.30	0.04 / 115	0.04 / 487	0.07 / 494	0.49 / 549	0.52 / 638
稠密 ER ($d=80$, $\text{nce}_{\max} \approx 20000$)	0.20	0.14 / 3888	1.00 / 15972	0.95 / 15390	0.68 / 10291	0.99 / 15972
稠密 ER ($d=80$)	0.25	0.04 / 3646	0.21 / 7922	0.14 / 7031	0.37 / 6574	0.62 / 11577
10-正则图 ($d=10$, $\text{nce}_{\max} = 2500$)	0.00	0.002 / 51	0.002 / 385	1.00 / 2500	1.00 / 2500	1.00 / 2500
10-正则图 ($d=10$)	0.05	0.002 / 51	0.003 / 425	0.95 / 2059	0.95 / 2034	0.95 / 2059
10-正则图 ($d=10$)	0.10	0.003 / 50	0.003 / 456	0.10 / 912	0.54 / 1135	0.56 / 1383
10-正则图 ($d=10$)	0.15	0.001 / 49	0.002 / 369	0.005 / 837	0.009 / 281	0.008 / 871

消融实验：骨干网络架构与级联效能拆解¶

为了解耦 2-FWL 表达力与链式机制的各自增益，作者在稀疏 Erdős–Rényi 图（$n=500, d=4$）上将 FGNN 替换为三种主流 1-WL 消息传递骨干（GraphSAGE、GIN、GAT），并在统一隐藏维度和残差层数下对比单步与链式（Ch-）变体（均使用 FAQ 后处理解码）：

骨干网络配置	噪声 0.05 (acc / nce)	噪声 0.10 (acc / nce)	噪声 0.15 (acc / nce)	噪声 0.20 (acc / nce)	噪声 0.25 (acc / nce)
SAGE-FAQ	0.97 / 946	0.13 / 497	0.05 / 477	0.02 / 474	0.01 / 473
ChSAGE-FAQ (级联提升)	0.97 / 951	0.69 / 756	0.11 / 494	0.04 / 476	0.02 / 475
GIN-FAQ	0.98 / 951	0.93 / 879	0.25 / 538	0.04 / 478	0.02 / 477
ChGIN-FAQ (级联提升)	0.98 / 951	0.95 / 889	0.34 / 575	0.06 / 483	0.03 / 477
GAT-FAQ	0.97 / 951	0.79 / 805	0.14 / 503	0.04 / 479	0.02 / 478
ChGAT-FAQ (级联提升)	0.97 / 951	0.96 / 893	0.92 / 833	0.24 / 537	0.05 / 486
ChFGNN-FAQ (2-FWL+级联)	0.98 / 950	0.96 / 899	0.95 / 849	0.93 / 800	0.85 / 730

此外，在真实世界网络（酵母 PPI 交互网络 yeast25LC、引文网络 ca-netscience 以及欧洲道路网 inf-euroroad）上的迁移实验显示，由合成稀疏 ER 图训练的 ChFGNN-ER4 与针对特定网络噪声微调的 ChFGNN，均能超越经凸松弛初始化的最强基线 $\text{FAQ}(D_{\text{cx}})$（例如在 inf-euroroad 噪声 $10\%$ 时，$\text{FAQ}(D_{\text{cx}})$ 为 0.56 / 1170，而专用 ChFGNN 达到 0.64 / 1213）。

关键发现¶

离散链式机制是全骨干通用的性能加速器：消融实验清晰证明，无论是 SAGE、GIN 还是 GAT，加入级联反馈后均产生显著增益（如噪声 0.15 时 GAT 从 0.14 暴涨至 ChGAT 的 0.92）。
高噪声瓶颈严格依赖 2-FWL 表达力：当噪声上升至 $p_{\text{noise}} \ge 0.20$ 时，所有 MPNN 变体（包括带链式的 ChGAT）均发生崩溃（准确率跌至 0.24 以下），而仅有基于 2-FWL 的 ChFGNN 仍能稳健维持 0.93（噪声 0.20）与 0.85（噪声 0.25）的高准确率。
正则图上展现唯一的破局能力：在 $d$-正则图上，古典凸松弛的梯度完全退化，MPNN 因 1-WL 同构限制完全失效（准确率仅千分之二）；而 ChFGNN 在噪声 0.10 下实现了 0.56 的非平凡对齐准确率，成为首个在此极端对称挑战下取得实质性突破的学习算法。
大幅加速传统 FAQ 算法收敛：分析显示，以 ChFGNN 相似度矩阵作为初始化，FAQ 所需的 Frank-Wolfe 投影迭代步数在噪声 0.20 下从原本的 31.4 步大幅压减至 6.5 步，表明学习到的相似度矩阵已高度贴近局部乃至全局能量最优盆地。

亮点与洞察¶

离散组合反馈融入连续神经网络训练：巧妙通过不可导的线性分配与节点匹配边评分，将图的离散组合一致性压缩为一维排序信号反馈给后续 GNN，绕过了纯连续端到端松弛难以捕捉离散拓扑硬约束的固有缺陷。
精简双线性 2-FWL 架构与理论等价保证：去除了传统 PPGN 的冗余分支 MLP，既控制了 $O(n^2 d)$ 张量存储开销，又严格证明了深度加倍下的 2-FWL 表达力保持定理，兼具工程实用性与理论深度。
澄清历史基准缺陷，确立扎实评测基准：揭示了以往众多 GNN 论文因使用默认均匀双随机矩阵初始化而严重低估 FAQ 算法的学术盲点，展示了在学术研究中严格对齐强古典 baseline 的规范标杆。

局限与展望¶

计算复杂度与显存规模受限：2-FWL 逐对交互层具有 $O(n^3 d)$ 的计算复杂度与 $O(n^2 d)$ 的中间激活张量显存占用，在当前单卡 80GB GPU 上支持的节点规模上限约为 $n \approx 1000$，难以直接扩展至超大尺度工业图谱。
2-FWL 的理论盲区：FGNN 理论上仍无法区分参数完全相同的强正则图（Strongly-Regular Graphs），虽然在现实与随机图基准中极少遭遇该极端反例，但该理论上界仍旧存在。
未来方向：探索稀疏张量近似或分块层次化表征以突破 $O(n^2)$ 空间瓶颈，并将链式离散反馈机制推广至带种子锚点的半监督图对齐以及其他带排列约束的二次组合优化问题中。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 巧妙结合 2-FWL 表达能力与非微分离散链式排序反馈，立意新颖且理论完备。
实验充分度: ⭐⭐⭐⭐⭐ 涵盖不同稀疏度随机图、极端正则图、多领域真实网络，不仅剖析了骨干消融，还澄清了经典基准的初始化缺陷。
写作质量: ⭐⭐⭐⭐⭐ 叙述严谨深入，从组合优化到松弛理论及表达力证明脉络极为清晰。
价值: ⭐⭐⭐⭐⭐ 成功将图神经网络在纯结构图对齐上的能力推向超越传统顶级优化算法的高度，兼具极高的学术与方法学价值。

图结构类型与规模	噪声 \(p_{\text{noise}}\)	\(\text{Proj}(D_{\text{cx}})\)	\(\text{FAQ}(D_{\text{cx}})\)	单步 FGNN-FAQ	链式 ChFGNN-Proj	链式 ChFGNN-FAQ (本文)
稀疏 ER (\(d=4\), \(\text{nce}_{\max} \approx 1000\))	0.00	0.98 / 997	0.98 / 997	0.98 / 997	0.98 / 997	0.98 / 997
稀疏 ER (\(d=4\))	0.10	0.90 / 853	0.96 / 898	0.96 / 898	0.96 / 898	0.96 / 899
稀疏 ER (\(d=4\))	0.15	0.59 / 499	0.95 / 847	0.95 / 847	0.94 / 845	0.95 / 849
稀疏 ER (\(d=4\))	0.20	0.23 / 195	0.73 / 723	0.81 / 755	0.91 / 790	0.93 / 800
稀疏 ER (\(d=4\))	0.25	0.09 / 130	0.13 / 504	0.24 / 535	0.82 / 720	0.85 / 742
稀疏 ER (\(d=4\))	0.30	0.04 / 115	0.04 / 487	0.07 / 494	0.49 / 549	0.52 / 638
稠密 ER (\(d=80\), \(\text{nce}_{\max} \approx 20000\))	0.20	0.14 / 3888	1.00 / 15972	0.95 / 15390	0.68 / 10291	0.99 / 15972
稠密 ER (\(d=80\))	0.25	0.04 / 3646	0.21 / 7922	0.14 / 7031	0.37 / 6574	0.62 / 11577
10-正则图 (\(d=10\), \(\text{nce}_{\max} = 2500\))	0.00	0.002 / 51	0.002 / 385	1.00 / 2500	1.00 / 2500	1.00 / 2500
10-正则图 (\(d=10\))	0.05	0.002 / 51	0.003 / 425	0.95 / 2059	0.95 / 2034	0.95 / 2059
10-正则图 (\(d=10\))	0.10	0.003 / 50	0.003 / 456	0.10 / 912	0.54 / 1135	0.56 / 1383
10-正则图 (\(d=10\))	0.15	0.001 / 49	0.002 / 369	0.005 / 837	0.009 / 281	0.008 / 871