A0158
Title: Nonparametric priors for graph matching
Authors: Lizhen Lin - The University of Notre Dame (United States) [presenting]
Abstract: The graph matching problem seeks to establish correspondences between nodes in two graphs, when observing their connections. Achievable solutions to this statistical problem are often elusive due to computational complexity. Uncertainty quantification is even more challenging. We present a novel modeling idea for graph matching that takes inspiration from the extensive Bayesian nonparametric methodologies developed for random partition models. In particular, we combine a correlated Erdos-Renyi likelihood with a nonparametric prior on the space of random permutations obtained via an upgrade of the well-known Chinese restaurant process (CRP). We believe this to be the first model-based Bayesian nonparametric approach to the graph-matching problem. There are several possible generalizations of the proposed model: the CRP prior to random permutations can be replaced by more complex constructions, inducing structural information in the model. We propose model extensions introducing an interplay between a latent block connectivity structure and the cycle structure of the (random) permutation, realizing the matching. In such a framework, the matching is driven by the connectivity behaviour of the nodes: we can either allow matching just within the same connectivity block or, leveraging a conditional partially exchangeable scheme, induce higher prior probability on within-block matching without ruling out across-block matching. Posterior inference is carried out via MCMC algorithms.
