Exchangeable random permutations for Bayesian graph matching

We introduce a new theory of exchangeable random permutations by linking the cycle representation of permutations to the literature on exchangeable random partitions. A novel sequential metaphor, the position-aware Chinese restaurant process (PA-CRP), provides a constructive foundation for this theory and supports practical algorithmic design. As an application, we develop a Bayesian model for graph matching that combines the PA-CRP with a correlated stochastic block model likelihood by linking the cycle structure of the matching permutation to the latent node community memberships. Posterior inference is performed through a node-wise blocked Gibbs sampler directly inspired by the proposed sequential construction, allowing coherent updates in the complex permutation space. To summarize posterior uncertainty, we introduce perSALSO, an adaptation of the SALSO algorithm to the permutation domain that provides principled point estimation and interpretable posterior summaries. Together, these contributions establish a unified probabilistic framework for modeling, inference, and uncertainty quantification over permutations.