通过链式结构提升图对齐性能,显著优于传统方法。
Chaining 2-FWL GNNs for Combinatorial Graph Alignment
- 用多阶段2-FWL GNN链式迭代,每步基于前序结果重排节点顺序。
- 在噪声图上准确率达85%,远超此前方法的0%~13%。
- 适用于结构同质图,且能超越经典初始化的FAQ基准。
针对组合图对齐问题(GAP),即寻找最大化两无标签图间公共边数(nce)的节点对应关系,现有方法中恰当初始化的FAQ仍是强基线,而传统GNN在纯结构场景表现不佳。本文提出链式过程:一系列2-FWL型GNN串联,每轮网络以交叉熵训练,并利用前一轮输出的相似度矩阵解码后按对齐质量排序节点。该非可微排序步骤在每条连接处注入离散组合反馈;推理时迭代最终网络并保留nce最高的候选。在噪声水平0.25的稀疏Erdos-Renyi图上,经FAQ后处理的链式FGNN达到85%准确率,而从凸松弛初始化的FAQ仅13%,先前GNN方法近乎0%。在相关正则图上,当常量特征的MPNN导致节点嵌入相同(1-WL无法区分),且FAQ初始值退化时,链式方法是唯一能恢复非平凡对齐的方法。在酵母PPI、合作者网络和道路网络三个真实数据集上,我们发现以往对比低估了FAQ,因其初始化为均匀双随机矩阵;一旦改用凸松弛初始化,FAQ已超越已有报告结果,而特定数据集的链式FGNN进一步提升此强化基线。
原文摘要 · Abstract (English)
For the combinatorial graph alignment problem (GAP) -- finding the node correspondence that maximizes the number of common edges (nce) between two unlabeled graphs -- properly initialized FAQ remains a strong classical baseline, while existing GNN approaches struggle in the purely structural setting. We introduce a chaining procedure: a sequence of Folklore-type (2-FWL) GNNs in which each network is trained with cross-entropy after decoding the previous network's similarity matrix and ranking nodes by their current alignment quality. This non-differentiable ranking step injects discrete combinatorial feedback at every link; at inference, we iterate the final network and keep the candidate with highest observed nce. On sparse Erdos-Renyi graphs at noise level 0.25, chained FGNNs with FAQ post-processing reach 85% accuracy versus 13% for FAQ initialized from the convex relaxation, and essentially 0% for prior GNN methods. On correlated regular graphs, where MPNNs with constant features produce identical node embeddings (1-WL fails to refine) and FAQ's convex initialization is degenerate, chaining is the only method we know that recovers a non-trivial alignment. On three real-world benchmarks (yeast PPI, coauthorship, and road networks), we show that recent comparisons underestimate FAQ by initializing it from a uniform doubly stochastic matrix; once FAQ is initialized from the convex relaxation it already surpasses prior reported numbers, and dataset-specific chained FGNNs further improve on this strengthened baseline.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。