Bayesian graph alignment diagnostics reveal limits in certainty and accuracy
Auditing Bayesian Graph Alignment: Diagnostic Comparisons and Reference Failure
Machine Learning
Summary
Matching parts between two connected networks (graphs) is tricky, and just because an algorithm looks like it is doing well does not mean it actually is. The authors tested several ways to check the quality of these matches on many pairs of graphs and found that common checks often fail to catch big errors. They also showed that even making algorithms run much longer or more intensely does not always improve the match quality. Their work highlights the need for careful methods to verify these matches and the limits of current evaluating tools.
What this means in practice
- •For data scientists: Improve analysis reliability when aligning networked data by using assignment-sensitive diagnostics to detect alignment errors.
- •For software engineers: Use diagnostic comparisons from this study to better evaluate the accuracy of algorithms that match nodes in related graph structures during development.
Authors
Melika Gorgi, Kourosh Mirsohi
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.