# Auditing Bayesian Graph Alignment: Diagnostic Comparisons and Reference Failure

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 33 references that are in the map.
- First posted on arXiv 19 Sep 2026.

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

- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [Validating Bayesian Inference Algorithms with Simulation-Based Calibration](https://mlsanity.com/paper/1804.06788/) (2018)
- [Oops I Took A Gradient: Scalable Sampling for Discrete Distributions](https://mlsanity.com/paper/2102.04509/) (2021)
- [Settling the Sharp Reconstruction Thresholds of Random Graph Matching](https://mlsanity.com/paper/2102.00082/) (2021)
- [Exact alignment recovery for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1711.06783/) (2017)
- [Graph Matching: Relax at Your Own Risk](https://mlsanity.com/paper/1405.3133/) (2014)
- [Matching recovery threshold for correlated random graphs](https://mlsanity.com/paper/2205.14650/) (2022)
- [The feasibility of multi-graph alignment: a Bayesian approach](https://mlsanity.com/paper/2502.17142/) (2025)
- [Convergence diagnostics for MCMC draws of a categorical variable](https://mlsanity.com/paper/1706.04919/) (2017)
- [Exchangeable random permutations with an application to Bayesian graph matching](https://mlsanity.com/paper/2602.01993/) (2026)

## Abstract (arXiv)

Bayesian graph alignment estimates correspondence probabilities, but convergence of an alignment-score trace need not imply accurate correspondence marginals. We audit this gap on 240 new exact graph pairs from four source families, 240 larger pairs with 20-100 vertices, and a separate 60-case exact implementation check. Under an explicit edge-flip likelihood, we compare three samplers and score, marginal, indicator, categorical, and classifier-based diagnostics. Marginal disagreement improves error discrimination over score R-hat for the exact informed sampler, but its improvement for vanilla local sampling is uncertain. Assignment-based R* and short indicator panels are competitive; no diagnostic dominates across samplers and endpoints. At larger sizes, diagnostics predict subsequent marginal changes, not posterior error, and classification performance depends on the drift threshold. Disjoint-window and held-out-chain checks attenuate but preserve positive associations. Only 22 of 240 original reference sets pass an agreement screen. On forty failure-selected cases, eightfold SMC particle escalation does not resolve disagreement, whereas additional rejuvenation helps. Longer informed runs remain unstable. An elementary feasible-alignment bound demonstrates severely unrepresentative SMC and informed-chain scores in concentrated 100-vertex cases, independently of approximate reference consensus. We also exhibit common-start chains with near-zero disagreement despite exact marginal error near .967. These results support assignment-sensitive auditing while identifying limits of finite budgets, diagnostic rankings, and reference agreement as evidence of accuracy.