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

Apr 17, 2026cs.CL

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

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.

Ayoub Hammal, Pierre Zweigenbaum, Caio Corro

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

Rejection Test Time Ambiguity

Ask PDF

Jun 14, 2026stat.ML

Phase Transition in Convex Relaxations for Graph Alignment

We study the graph alignment problem for correlated Gaussian Orthogonal Ensemble (GOE) matrices, where the goal is to recover a hidden vertex permutation given two correlated symmetric Gaussian matrices

(A, B)

with correlation

1/\sqrt{1+σ^2}

. While the maximum likelihood estimator is information-theoretically optimal, its computation, which reduces to a quadratic assignment problem, is intractable. Motivated by this, we analyze convex relaxations based on minimizing

\|AX - XB\|_F

over the set of doubly stochastic matrices and the unit hypercube. We show that when the correlation parameter satisfies

σ= o(n^{-1/2}/\log^4 n)

, the solution of either relaxation

(X^\star)

concentrates around the ground-truth permutation matrix

(Π^\star)

, i.e.,

\|X^\star-Π^\star\|_F^2 = o(n)

, implying recovery of all but a vanishing fraction of vertices after simple post-processing. Combined with existing lower bounds, our results precisely characterize that

\|X^\star-Π^\star\|_F^2

transitions from

o(n)

for

σ= \tilde{o}(n^{-1/2})

Ω(n)

for

σ= \tildeΩ(n^{-1/2})

. In doing so, our analysis significantly tightens prior results and extends them beyond doubly stochastic relaxations.

Laurent Massoulié, Sushil Mahavir Varma, Louis Vassaux +1

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

Convex Relaxation Full-Rank Correlation Matrices Feature Alignment Gaussian Primitives Phase Transitions

Ask PDF

May 18, 2026stat.ML

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

Bayesian latent space models offer a principled approach to network representation, but rely on correct specification of both geometry and link function. Real-world networks often violate these assumptions, exhibiting geometric mismatch and structural anomalies that break standard metric properties. We show that such misspecification pushes the data-generating distribution outside the model class, causing Bayesian inference to become overconfident and poorly calibrated. To address this, we propose a generalized posterior framework for random geometric graphs. We introduce Link-Sequential R-SafeBayes, a method that exploits dyadic conditional independence to estimate prequential risk and adaptively tune posterior regularization. Experiments on synthetic and real-world networks demonstrate improved calibration, better link prediction performance, and a reliable criterion for selecting latent geometries across Euclidean, spherical, and hyperbolic spaces.

Aldric Labarthe

CB, UNIGE · Centre Borelli, Université Paris-Saclay Gif-Sur-Yvette, FR · Department of Computer Science, University of Geneva Carouge, CH-1227

Posterior Inhomogeneous Random Graphs Network Science Latent Space

Ask PDF