# Chaining 2-FWL GNNs for Combinatorial Graph Alignment

arXiv: https://arxiv.org/abs/2510.03086 · HTML: https://mlsanity.com/paper/2510.03086/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 55 references that are in the map.
- First posted on arXiv 3 Oct 2025.

## Builds on (most cited first, 26 of 26)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training](https://mlsanity.com/paper/2009.03294/) (2020)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [Expressive Power of Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/2006.15646/) (2020)
- [Deep Graph Matching Consensus](https://mlsanity.com/paper/2001.09621/) (2020)
- [Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching](https://mlsanity.com/paper/1911.11308/) (2019)
- [Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers](https://mlsanity.com/paper/2003.11657/) (2020)
- [Efficient random graph matching via degree profiles](https://mlsanity.com/paper/1811.07821/) (2018)
- [Improved Achievability and Converse Bounds for ErdHos-R'enyi Graph Matching](https://mlsanity.com/paper/1602.01042/) (2016)
- [Multi-level Graph Convolutional Networks for Cross-platform Anchor Link Prediction](https://mlsanity.com/paper/2006.01963/) (2020)
- [Graph Matching: Relax at Your Own Risk](https://mlsanity.com/paper/1405.3133/) (2014)
- [Spectral Graph Matching and Regularized Quadratic Relaxations II: ErdHos-R'enyi Graphs and Universality](https://mlsanity.com/paper/1907.08883/) (2019)
- [Random graph matching at Otter's threshold via counting chandeliers](https://mlsanity.com/paper/2209.12313/) (2022)
- [Impossibility of Partial Recovery in the Graph Alignment Problem](https://mlsanity.com/paper/2102.02685/) (2021)
- [Deep Graph Matching under Quadratic Constraint](https://mlsanity.com/paper/2103.06643/) (2021)
- [Matching recovery threshold for correlated random graphs](https://mlsanity.com/paper/2205.14650/) (2022)
- [Correlation detection in trees for planted graph alignment](https://mlsanity.com/paper/2107.07623/) (2021)
- [Statistical limits of correlation detection in trees](https://mlsanity.com/paper/2209.13723/) (2022)
- [A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation](https://mlsanity.com/paper/2306.00266/) (2023)
- [Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching](https://mlsanity.com/paper/1311.6425/) (2013)
- [(Probably) Concave Graph Matching](https://mlsanity.com/paper/1807.09722/) (2018)
- [SeedGNN: Graph Neural Networks for Supervised Seeded Graph Matching](https://mlsanity.com/paper/2205.13679/) (2022)
- [Faster algorithms for the alignment of sparse correlated Erd"os-R'enyi random graphs](https://mlsanity.com/paper/2405.08421/) (2024)
- [Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodings](https://mlsanity.com/paper/2505.13087/) (2025)

## Abstract (arXiv)

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.