Many methods for network alignment, the task of finding which node in one graph corresponds to which node in another, work in two stages. A first method produces a rough matching. A refinement step then repeatedly improves it, often using the rule that matched nodes should have matched neighbors. Each refinement round reads the previous round's output. A refiner learned from data therefore faces the problem the sequence-modeling literature calls exposure bias: the model is trained on one kind of input and, at test time, fed its own imperfect earlier predictions. We argue that this mismatch is the hidden reason learned refiners break under structural noise (missing and spurious edges). The errors a real aligner makes on a noisy graph are not scattered at random. They form clusters that agree with their own neighborhoods: a block of nodes is mapped consistently, but to the wrong place. A refiner trained on randomly corrupted matchings has never seen such clusters and leaves them in place.
The proposal is to train the refiner on its own rollouts. We generate noisy copies of a graph, where the true correspondence is known because we made the copy. We run the base aligner and then the refiner for several rounds, and supervise every intermediate state the refiner actually visits. Because the copies come from the target graph itself, no labeled anchors are needed. The claim is specific and can be tested. Teacher-forced refiners show a measurable gap between how often they correct errors on synthetic corruptions and how often they correct errors on real aligner outputs. Rollout training closes that gap, and the gain concentrates on errors that agree with their neighborhoods, which current refinement cannot escape.
Core Claim and Positioning
Three findings motivate the claim. Refining Network Alignment to Improve Matched Neighborhood Consistency (RefiNA) shows that a simple iterative rule, which rewards matchings whose neighbors are also matched, lifts weak aligners dramatically: from 4% to 94% accuracy on some benchmarks, and effective up to 25% edge noise on Arenas. The same paper notes that the rule behaves like a low-pass filter and uses topology only. A filter of that kind strengthens whatever locally consistent pattern already exists, right or wrong. Fast Graph Generation via Autoregressive Noisy Filtration Modeling shows, for graph generation rather than alignment, that adding random edge noise during training is necessary but not sufficient to fix exposure bias. Their model also needed training on its own generated sequences, through adversarial reinforcement-learning fine-tuning. On Exposure Bias, Hallucination and Domain Shift in Neural Machine Translation shows that objectives computed on model rollouts reduce the tendency to compound early errors, with up to 21% fewer hallucinations than maximum likelihood under domain shift.
The closest alignment work treats matching as a sequence of decisions but solves a different problem. Revocable Deep Reinforcement Learning with Affinity Regularization for Outlier-Robust Graph Matching (RGM) commits node pairs one at a time with a reinforcement-learning agent and can undo conflicting pairs. That agent runs on a fixed affinity matrix, is slow at inference, and never measures the mismatch between training and test states. Sequential Graph Matching with Sequential Monte Carlo uses locally normalized step-by-step choices tracked by particle filtering, so early mistakes constrain later steps. Bootstrapping Entity Alignment with Knowledge Graph Embedding (BootEA) adds its own predictions to the training set and uses a heuristic editing pass to retract bad ones.
Our design differs from all three. We do not build matchings one pair at a time. We refine a whole soft matching in parallel rounds, with a sparse graph neural network: a model that updates each node's representation by combining its neighbors'. This keeps the cost near linear in edges times candidate-list size, not quadratic. The exposure-bias correction is applied to the refinement operator itself, which then plugs into any base aligner.
Research Program
The refiner $f_\theta$ takes the two graphs, node features if any, and a current sparse soft matching $M_k$ restricted to each node's top-$c$ candidates. It outputs $M_{k+1}$. Each layer passes messages along edges of both graphs and along candidate pairs, so a node pair can see whether its neighbors' candidates are mutually consistent at radius greater than one. That is information RefiNA's one-hop rule lacks. Training data comes from self-copies. We take the target graph $G$, apply a random permutation and an edge-noise process, and obtain $G'$ with known ground truth $M^*$. The noise process deletes and adds edges at rates drawn from a range, and is degree-biased as well as uniform. We run the base aligner $A$ on $(G, G')$ to get $M_0$.
The three training regimes differ only in which matchings the refiner learns from. Teacher forcing trains on $\tilde M \sim q(\cdot \mid M^*)$, a random corruption of the truth. Base-output training uses $M_0$ only. Rollout training unrolls $K$ rounds and minimizes
$$\mathcal{L}(\theta) = \sum_{k=1}^{K} \mathbb{E}\left[\ell\left(f_\theta(M_{k-1}), M^*\right)\right], \quad M_k = f_\theta(M_{k-1}),$$
where $\ell$ is a row-wise cross-entropy against the true match. The states $M_{k-1}$ are detached from the gradient, so this is a DAgger-style scheme that trains on visited states without backpropagating through the whole unroll. This keeps memory at one round.
To make "exposure gap" measurable, we define the correction rate $r(\mathcal{D})$. It is the fraction of nodes wrong in the input matching that are right after one refiner round, for inputs drawn from distribution $\mathcal{D}$. The gap is
$$\Delta = r(q) - r(\text{rollout states}),$$
the correction rate on training-style corruptions minus the rate on states the refiner actually visits. We also tag each error by whether it is neighborhood-consistent, meaning most of its neighbors are mapped consistently with it. This tests the claim that consistent errors account for most of $\Delta$.
Baselines
The naive reference is the base aligner alone, with no refinement. We use two bases on purpose. JOENA (Joint Optimal Transport and Embedding for Network Alignment) couples random-walk positional encodings with optimal transport, a method that computes a soft one-to-one assignment minimizing a transport cost. It reports up to a 16% Mean Reciprocal Rank gain over PARROT. The file gives no absolute JOENA scores. The second base is a weaker embedding method from the PLANETALIGN library, which benchmarks 14 methods on 18 datasets. PLANETALIGN finds optimal-transport methods most accurate and embedding methods noise-fragile. Its per-dataset scores appear only in figures, so there is no reported result on Lacuna for exact PLANETALIGN baseline accuracies. We rerun everything inside PLANETALIGN with identical splits and noise seeds.
The strongest existing refinement competitor is RefiNA applied to the same base outputs, with its iteration count and sparsity tuned on the same validation copies we use. Its reported numbers are 4% to 94% accuracy on corrupted benchmarks and effectiveness at 25% noise on Arenas. Beating it means higher final Hits@1 and Mean Reciprocal Rank at matched noise levels. It is not enough to beat it at 0–5% noise. The win must hold at 15–25% edge noise on Arenas, Douban, ACM-DBLP and Foursquare-Twitter, the range where RefiNA's gains are largest.
The key ablation holds the refiner architecture, data, training steps and tuning budget fixed and changes only the training inputs: teacher forcing, base-output training, or rollout training. Rollout training costs about $K$ times more forward passes, so we give the other two regimes the same total gradient steps. As a reference for one-shot robust transport on the subgraph benchmarks, we include SRGW (Achieving Structurally Robust Gromov Wasserstein Distance via Adaptive Dual-Mask). SRGW masks individual spurious edge interactions rather than discarding nodes, and reports gains of 10.7% on ENZYMES and 11.1% on DHFR over robust Gromov-Wasserstein.
Why not just…?
Why not just use a strong one-shot optimal-transport aligner and skip refinement? One-shot solvers have no rounds, so they have no exposure bias. They do pay in memory: PLANETALIGN reports out-of-memory failures as graphs approach 100,000 nodes. SRGW also shows that global quadratic couplings let a few spurious edges distort the whole solution, which it fixes only with user-set noise budgets. Our experiments test this directly. If rollout-refined JOENA does not beat JOENA alone at high noise, the proposal fails for the strongest base.
Why not just run RefiNA? It is cheap, needs no training, and works remarkably well. However, its own analysis frames it as neighborhood smoothing on topology alone. Smoothing cannot break a wrong matching that is consistent with its neighbors. Our consistent-error tagging tests this. If RefiNA corrects consistent errors at the same rate as inconsistent ones, this motivation is wrong.
Why not just train the refiner with random edge and matching noise? This is the teacher-forcing arm, and the graph-generation evidence from Krimmel et al. suggests it is insufficient. The real threat is a cheaper middle option: training once on the base aligner's outputs, with no rollouts. If base-output training matches rollout training, the honest conclusion is that the problem lies in the distribution of initial errors, not in compounding across rounds. We would report that and recommend the cheaper method.
Why not just use RGM's revocable reinforcement learning? RGM is built for keypoint matching with outlier nodes and a fixed affinity matrix. It decides one pair per step, which its authors note is slow. We compare on Willow, where RGM reports a 4% F1 gain with 6 outliers, but our main regime is large plain networks, where per-pair decisions do not scale.
Proposed Experiments
The first decisive check measures $\Delta$ for the teacher-forced refiner on Arenas, Douban and ACM-DBLP across 0–25% edge noise. The claim requires $\Delta$ to be large and to grow with noise. The second check requires rollout training to shrink $\Delta$ and to raise final Hits@1 over both RefiNA and the teacher-forced refiner, with the improvement concentrated on consistent errors. The third check runs the refiner trained only on self-copies on the real pairs (Douban, Foursquare-Twitter, ACM-DBLP, PPI). These pairs carry natural, non-synthetic structural differences, so the check shows whether learning from self-generated noise transfers. The fourth check tracks accuracy over $K$ up to 20 rounds. Teacher-forced refiners should plateau or degrade, while rollout-trained ones should keep improving or hold steady.
We also report wall-clock time and memory on the PLANETALIGN Erdős–Rényi scaling graphs, to confirm the sparse refiner stays usable where quadratic solvers run out of memory. A null result on the first check, meaning no measurable gap, would falsify the premise, and we would report that as the main finding.
References
- Refining Network Alignment to Improve Matched Neighborhood Consistency
- Fast Graph Generation via Autoregressive Noisy Filtration Modeling
- On Exposure Bias, Hallucination and Domain Shift in Neural Machine Translation
- Revocable Deep Reinforcement Learning with Affinity Regularization for Outlier-Robust Graph Matching
- Sequential Graph Matching with Sequential Monte Carlo
- Bootstrapping Entity Alignment with Knowledge Graph Embedding
- Joint Optimal Transport and Embedding for Network Alignment
- PLANETALIGN: A Comprehensive Python Library for Benchmarking Network Alignment
- Achieving Structurally Robust Gromov Wasserstein Distance via Adaptive Dual-Mask