Chaining 2-FWL GNNs for Combinatorial Graph Alignment

Technical Summary: Chaining 2-FWL GNNs for Combinatorial Graph Alignment

Problem Definition
The paper addresses the Combinatorial Graph Alignment Problem (GAP), which seeks to find the node correspondence between two unlabeled graphs ($G_A$ and $G_B$) that maximizes the number of common edges (nce). Formally, this is equivalent to minimizing the Frobenius norm $\|AP - PB\|_F^2$ over the set of permutation matrices $P$, or maximizing the quadratic form $\langle AP, PB \rangle$. This problem is a specific instance of the Quadratic Assignment Problem (QAP), known to be NP-hard.

The authors focus strictly on the purely structural setting, where graphs have no node features other than their topology. In this regime, existing Graph Neural Network (GNN) approaches have struggled to match the performance of strong classical baselines, specifically the Fast Approximate Quadratic (FAQ) algorithm [Vogelstein et al., 2015], which solves a continuous relaxation of the QAP using Frank-Wolfe optimization.

Methodology: Chaining with Discrete Feedback
The core contribution is a chaining procedure that sequentially trains a series of Folklore-type GNNs (2-FWL GNNs) to generate increasingly accurate similarity matrices, which serve as initializations for the FAQ algorithm.

1. Iterative Refinement Loop:

   • Step 1 (Feature Extraction): An initial GNN ($f$) extracts node features from the adjacency matrices and computes a similarity matrix $S^{(0)}$.
   • Step 2 (Decoding & Ranking): The similarity matrix is decoded into a permutation $\pi$ via a linear assignment solver (Projection). Crucially, the paper introduces a non-differentiable ranking step: nodes are ranked based on their "alignment quality" (the number of edges matched by the current permutation). This injects discrete combinatorial feedback into the pipeline.
   • Step 3 (Ranking-Enhanced Learning): A subsequent GNN ($g^{(k)}$) takes the graph structure and the node rankings as input to compute an enhanced similarity matrix $S^{(k)}$. This matrix is expected to be more informative than the previous one because it incorporates knowledge of which nodes are currently aligning well.

2. Sequential Training:
   Because the ranking step is non-differentiable, the GNNs cannot be trained end-to-end. Instead, they are trained sequentially:

   • Train $f$ to minimize cross-entropy loss against the ground-truth permutation.
   • Fix $f$, compute rankings on the training set, then train $g^{(1)}$ to minimize loss against the ground truth using the new rankings.
   • Repeat for $g^{(2)}, \dots, g^{(L)}$.
     Each network learns to improve upon the alignment quality achieved by the previous network in the chain.

3. Inference with Looping:
   At inference, the final trained network $g^{(L)}$ can be applied iteratively (looping). After each pass, a candidate permutation is generated, and the one with the highest observed nce is kept. This "looping" acts as a heuristic refinement without additional training.

4. Architecture (FGNN):
   The authors employ Folklore-type GNNs (FGNN), which operate on node pairs rather than individual nodes. This architecture achieves 2-FWL (2-Folklore Weisfeiler-Leman) expressivity. This is critical because standard Message Passing Neural Networks (MPNNs) are limited to 1-WL expressivity and fail to distinguish nodes in regular graphs (where all nodes have identical local neighborhoods), leading to degenerate similarity matrices.

Key Contributions

• Chaining Procedure: A novel training paradigm that bridges the gap between discrete combinatorial optimization and continuous GNN learning by using discrete rankings as feedback signals.
• Improved FAQ Initializations: The method learns to provide FAQ with similarity matrices that are significantly better initializations than the standard convex relaxation ($D_{cx}$), particularly on hard instances.
• Expressivity Analysis: The paper demonstrates that 2-FWL expressivity is necessary for the purely structural setting, as 1-WL-based MPNNs fail on regular graphs and sparse graphs with high noise.
• Re-evaluation of Baselines: The authors argue that prior comparisons in the literature often underestimate FAQ by initializing it with a uniform doubly stochastic matrix rather than the convex relaxation solution ($D_{cx}$). When properly initialized, FAQ is a much stronger baseline than previously reported.

Results
The method was evaluated on synthetic correlated random graphs (Sparse Erdős–Rényi, Dense Erdős–Rényi, and Regular graphs) and three real-world benchmarks (Yeast PPI, Coauthorship, Road networks).

• Sparse Erdős–Rényi Graphs: At a noise level of 0.25, the chained FGNN with FAQ post-processing (ChFGNN FAQ) achieved 85% accuracy, compared to 13% for FAQ initialized from the convex relaxation and essentially 0% for prior GNN methods.
• Regular Graphs: This is a regime where standard methods fail completely. The convex relaxation yields a degenerate solution (the barycenter), and MPNNs produce identical embeddings. The chained FGNN is the only method reported to recover a non-trivial alignment, achieving 56% accuracy at noise level 0.1, whereas all other methods failed.
• Real-World Benchmarks: On real-world datasets, the chained FGNNs improved upon the strengthened FAQ baseline (FAQ initialized from $D_{cx}$) by approximately 2% in terms of nce in high-noise settings.
• Efficiency: While the chaining procedure requires GPU-based training, the inference step significantly reduces the number of Frank-Wolfe iterations required by FAQ compared to using the convex relaxation directly, indicating a higher-quality initialization.

Significance and Claims
The paper claims that iterative refinement with discrete combinatorial feedback is a promising direction for combinatorial problems with a natural ranking interpretation. The authors do not claim their method transfers without modification to arbitrary combinatorial optimization problems.

The primary significance lies in demonstrating that learned representations can improve upon the state-of-the-art classical solver (FAQ) in the purely structural setting, a domain where GNNs have historically underperformed. The work highlights that the failure of prior GNNs was partly due to insufficient expressivity (1-WL limitations) and partly due to the lack of a mechanism to incorporate discrete structural feedback. By chaining 2-FWL GNNs, the authors successfully overcome these barriers, achieving state-of-the-art results on hard sparse and regular graph instances.