Geometric graph comparison from an alignment viewpoint

Abstract

In this paper we propose a new approach for the comparison and retrieval of geometric graphs formulated from an alignment perspective. The algorithm presented here is quite general in nature and applies to geometric graphs of any dimension. The method involves two major steps. Firstly graph alignment is effected making use of an optimisation approach whose target function arises from a diffusion process over the graphs under study. This provides, from the theoretical viewpoint, a link between stochastic processes on graphs and the heat kernel. The second step involves using a probabilistic approach to recover the transformation parameters that map the graph-vertices to one another so as to permit the computation of a similarity measure based on the goodness of fit between the two graphs under study. Here, we view the transformation parameters as random variables and aim at minimising the Kullback-Liebler divergence between the two graphical structures under study. We provide a sensitivity analysis on synthetic data and illustrate the utility of the method for purposes of comparison and retrieval of CAD objects and binary shape categorisation. We also compare our results to those yielded by alternatives elsewhere in the literature.