Research map / Graph learning / Graph algorithms and clustering

Chaining 2-FWL GNNs for Combinatorial Graph Alignment

NeurIPS 2026 · Graph learning › Graph algorithms and clustering · approach: Deep learning for graph matching · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Chains of 2-FWL (Folklore-type) GNNs trained sequentially with a non-differentiable ranking feedback step to learn better similarity matrices for FAQ-based graph alignment, with looping at inference.

Problem

Combinatorial graph alignment (GAP): finding the node correspondence maximizing common edges between two unlabeled graphs; GNN methods fail in the purely structural setting, and FAQ initialization is often poorly chosen.

Approach

A sequence of Folklore-type (2-FWL) GNNs, each trained with cross-entropy on a similarity matrix whose node features are conditioned on the discrete node ranking induced by the previous network's projected alignment; at inference the final network is looped and the candidate with highest number of common edges is kept.

Key results

• On sparse ER at noise 0.25, ChFGNN with FAQ reaches 0.85 accuracy vs 0.13 for FAQ(D_cx) and near 0 for prior GNN methods.
• On regular graphs at noise 0.1, ChFGNN with FAQ reaches 0.56 accuracy (NCE 1383) where other methods essentially fail.
• On real graphs, dataset-specific ChFGNN improves NCE over FAQ(D_cx) by about 2% in high-noise settings; FAQ initialized from convex relaxation surpasses previously reported FUGAL numbers.

Surprising findings

• Properly initialized FAQ (from convex relaxation) substantially outperforms prior reported results and FUGAL, suggesting prior comparisons underestimate FAQ due to uniform doubly stochastic initialization.
• Single-step MPNN backbones (SAGE, GIN, GAT) collapse at noise 0.2 even with chaining, while ChFGNN retains 0.93 accuracy.

Limitations

• Memory O(n^2 d) per layer caps training around n≈1000 on an 80GB GPU.
• FGNN inherits the 2-FWL expressivity ceiling and cannot separate strongly regular graphs of identical parameters.
• Looping at inference is out-of-distribution heuristic without theoretical guarantee; dense ER and real-world gains are modest.

Experimental setup

Datasets: synthetic correlated Erdos-Renyi graphs synthetic correlated regular graphs synthetic Bernoulli graphs yeast PPI ca-netscience inf-euroroad

Benchmarks: synthetic sparse ER (n=500, d=4) synthetic dense ER (d=80) synthetic regular graphs (degree 10) yeast PPI ca-netscience inf-euroroad

Metrics: accuracy number of common edges (NCE)

Baselines: FAQ(D_cx) FUGAL SGWL SeedGNN PGM SGM MGCN SAGE GIN GAT

Builds on: FAQ PPGN Folklore-type GNN SeedGNN

Closest papers by meaning

• Iteratively Refined Early Interaction Alignment for Subgraph Matching based Graph Retrieval (NeurIPS 2024 · similarity 0.88)
• A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening (NeurIPS 2024 · similarity 0.87)
• GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring (ICLR 2025 · similarity 0.87)
• TopoTune: A Framework for Generalized Combinatorial Complex Neural Networks (ICML 2025 · similarity 0.87)
• A Unified Graph Language Model for Multi-Domain Multi-Task Graph Alignment Instruction Tuning (NeurIPS 2026 · similarity 0.87)
• Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality (ICML 2025 · similarity 0.87)