← 研踪 PaperTrailarXiv:2510.03086 · v3
Chaining 2-FWL GNNs for Combinatorial Graph Alignment
首次提交 2025-10-03 23:17
版本更新 2026-11-07 02:29
雷达观测 2026-11-09 13:22
摘要
For the combinatorial graph alignment problem (GAP), finding the node correspondence that maximizes the number of common edges (nce) between two unlabeled graphs, the classical Frank-Wolfe heuristic FAQ remains a strong baseline once it is properly initialized, 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 stage; 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 used to initialize FAQ 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 among those we evaluate, including Gromov-Wasserstein solvers, that recovers a non-trivial alignment. On three real-world benchmarks (yeast PPI, coauthorship, and road networks), recent comparisons underestimate FAQ by initializing it from a uniform doubly stochastic matrix; initialized from the convex relaxation it already surpasses prior reported numbers, and dataset-specific chained FGNNs further improve on this strengthened baseline. Code and pretrained chains available at: https://github.com/mlelarge/chaining-gnn-graph-alignment.
作者备注：Accepted at NeurIPS 2026
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-07 02:29 · 最新观测版本
Chaining 2-FWL GNNs for Combinatorial Graph Alignment
For the combinatorial graph alignment problem (GAP), finding the node correspondence that maximizes the number of common edges (nce) between two unlabeled graphs, the classical Frank-Wolfe heuristic FAQ remains a strong baseline once it is properly initialized, 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 stage; 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 used to initialize FAQ 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 among those we evaluate, including Gromov-Wasserstein solvers, that recovers a non-trivial alignment. On three real-world benchmarks (yeast PPI, coauthorship, and road networks), recent comparisons underestimate FAQ by initializing it from a uniform doubly stochastic matrix; initialized from the convex relaxation it already surpasses prior reported numbers, and dataset-specific chained FGNNs further improve on this strengthened baseline. Code and pretrained chains available at: https://github.com/mlelarge/chaining-gnn-graph-alignment.
查看此版本解读 →查看此版本原文 ↗