Auditing Bayesian Graph Alignment: Diagnostic Comparisons and Reference Failure

Melika Gorgi; Kourosh Mirsohi

stat.APSep 19, 2026

Auditing Bayesian Graph Alignment: Diagnostic Comparisons and Reference Failure

Authors: Melika Gorgi, Kourosh Mirsohi

Organizations: Center for Complex Biological Systems University of California, Irvine Irvine, CA 92697, USA · Department of Computer Science University of California, Irvine Irvine, CA 92697, USA

Abstract

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.

Figures & tables

Method	Diagnostic	Spearman	AUC	High error
Local MH	$D_{\rm marg}$	0.527	0.976	4/240
Local MH	Score $\widehat{R}$	0.137	0.944	4/240
Local MH	Indicator $\widehat{R}$	0.409	0.972	4/240
PT	$D_{\rm marg}$	0.271	not estimable	0/240
PT	Score $\widehat{R}$	0.013	not estimable	0/240
PT	Indicator $\widehat{R}$	0.031	not estimable	0/240

Table 1: New exact tier; high error means pooled row-TV above 0.1. AUC is undefined without both label classes.

Method	$\rho(D_{\rm marg})$	$\rho(\widehat{R})$	AUC $(D_{\rm marg})$	AUC $(\widehat{R})$	Drift $>0.1$
Local MH	0.433	0.184	0.998	0.995	200/240
PT	0.809	0.437	1.000	0.814	235/240
Informed MH	0.665	0.210	not estimable	not estimable	240/240

Table 2: Large-tier endpoint is drift after sixteen times the early work, not exact posterior error.

Particles	Moves	Cross PT	Within SMC	Ancestors
512	32	0.788	0.903	4.556
512	256	0.721	0.735	11.025
1024	32	0.790	0.891	6.575
2048	32	0.792	0.886	10.244
4096	4	0.850	0.936	6.456
4096	32	0.784	0.874	19.306

Table 3: SMC on forty failure-selected graphs. Distances are mean row-TV; passes require all original screen conditions. Ancestors are surviving initial particle lineages, averaged over graphs and four replicates. The 4096/4 and 512/256 settings are work controls.

Replicas	Cross original PT	Within PT	Trips	Min. swap	Cold swap
8	0.508	0.761	5.013	0.004	0.200
16	0.710	0.761	8.569	0.082	0.386
32	0.704	0.740	9.150	0.322	0.618

Table 4: Longer PT references on the same forty graphs. Trips are mean cold–hot–cold traversals per replicate; minimum swap is the graphwise minimum over edges and replicates, averaged over graphs. Replica count trades ladder resolution against sweeps at fixed local-proposal work.

Transitions	Adjacent drift	$D_{\mathrm{marg}}$	Window drift	Acceptance
10,000	0.701	0.936	0.309	0.125
40,000	0.355	0.881	0.277	0.103
160,000	0.308	0.821	0.222	0.093

Table 5: Unmatched informed runs on forty selected graphs. The first adjacent comparison uses the original early budget; subsequent rows compare successive new budgets. Drift and disagreement are different quantities and neither alone certifies accuracy.

Diagnostic	Exact informed AUC	Large local MH $\rho$	Large PT $\rho$	Large informed MH $\rho$
$D_{\mathrm{marg}}$	0.975	0.433	0.809	0.665
Score $\widehat{R}$	0.846	0.184	0.437	0.210
Indicator $\widehat{R}$	0.971	0.302	0.328	0.190
Weiß/DAR(1)	0.907	-0.355	0.254	-0.745
Score $R^{*}$	0.810	0.251	0.692	0.342
Panel $R^{*}$	0.973	0.747	0.566	-0.043

Table 6: Added diagnostic comparison. Exact AUC uses error above 0.1; large Spearman correlations use continuous later drift. These columns describe different endpoints and sampler groups. Undefined values are excluded and their counts are retained in the companion repository. Paired bootstrap contrasts use shared valid graphs.

Figure 1: Prespecified large-tier drift-threshold sweep for the original diagnostic panels. Missing points have undefined AUC. All positive/negative counts and stratified bootstrap intervals, including size-specific results, are available in the companion repository. Spearman correlation with continuous drift does not change with threshold.

Sampler	Original	Shared A	A to B	Chain holdout
Informed MH	0.665	0.750	0.633	0.486
Local MH	0.433	0.482	0.420	0.295
PT	0.809	0.805	0.747	0.640

Table 7: Spearman associations with later drift on all 240 large graphs. Original uses the full early sample in both quantities. Shared A uses half as many early draws in both quantities. A to B diagnoses A but measures drift from disjoint B draws. Chain holdout uses two chains for the diagnostic and two different chains for the outcome. These columns differ in retained information; shared controls and reverse orientations are retained in the companion repository.

Diagnostic	Local MH	PT	Informed MH
$D_{\mathrm{marg}}$	0.420	0.747	0.633
Score $\widehat{R}$	0.160	0.328	0.157
Indicator $\widehat{R}$	0.263	0.262	0.169
Weiß/DAR(1)	-0.337	0.073	-0.667
Score $R^{*}$	0.236	0.604	0.182
Panel $R^{*}$	0.722	0.583	-0.025

Table 8: All diagnostics recomputed from A and evaluated against B-to-later drift. Each column is a pooled Spearman correlation, with undefined diagnostic values excluded and their counts retained in the companion repository. RF hyperparameters are unchanged; less data can change classifier performance.

Variant	Transitions	Work (millions)	$D_{\mathrm{marg}}$	Window drift
Broader	160,000	7.680	0.983	0.258
Broader	663,333	31.840	0.979	0.306
Single pivot	160,000	31.840	0.976	0.259

Table 9: Matched eight-graph broader-proposal probe at 100 vertices, with four chains per graph. Work counts transposition-delta evaluations per chain. The 160,000-step broader run matches transitions; 663,333 steps match the original 160,000-step single-pivot work within 16 delta evaluations. Comparisons are exploratory, not evidence about every locally balanced proposal.

Explore similar work

On the Rejection Criterion for Proxy-based Test-time Alignment
Apr 17, 2026Ayoub Hammal, Pierre Zweigenbaum, Caio CorroRejection Test Time
Université Paris-Saclay, CNRS, LISN · INSA Rennes, IRISA, CNRS, Université de Rennes
Phase Transition in Convex Relaxations for Graph Alignment
Jun 14, 2026Laurent Massoulié, Sushil Mahavir Varma, Louis Vassaux +1Convex Relaxation Full-Rank Correlation Matrices
INRIA, DI/ENS, PSL Research University, Paris, France · Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan, USA. · CNRS, INRIA, Universit´e Paris Dauphine, Paris, France
Bayesian Latent Space Models for Graphs Are Misspecified: Toward Robust Inference via Generalized Posteriors
May 18, 2026Aldric LabarthePosterior Inhomogeneous Random Graphs
CB, UNIGE · Centre Borelli, Université Paris-Saclay Gif-Sur-Yvette, FR · Department of Computer Science, University of Geneva Carouge, CH-1227

Apr 17, 2026, cs.CLJ/K move · Enter open · S save

On the Rejection Criterion for Proxy-based Test-time Alignment

Ayoub Hammal, Pierre Zweigenbaum, Caio Corro

Université Paris-Saclay, CNRS, LISN · INSA Rennes, IRISA, CNRS, Université de Rennes

Rejection Test Time Ambiguity

Open paper AskPDF arXiv

Recent works proposed test-time alignment methods that rely on a small aligned model as a proxy that guides the generation of a larger base (unaligned) model. The implicit reward approach skews the large model distribution, whereas the nudging approach defers the generation of the next token to the small aligned model when the large base one is unconfident about its outcome. In this work, we first show that both approaches can be reduced to sampling from similar graphical models, where they differ only in the definition of a rejection criterion (or distribution). Moreover, we argue that the confidence criterion is ill-motivated due to linguistic phenomena like ambiguous phrasing. We propose a novel rejection criterion based on a conservative confidence bet. Experimentally, our novel approach outperforms previous work on several datasets.

Abstract

Explore similar work

On the Rejection Criterion for Proxy-based Test-time Alignment

Phase Transition in Convex Relaxations for Graph Alignment

Bayesian Latent Space Models for Graphs Are Misspecified: Toward Robust Inference via Generalized Posteriors