Local manifold distance based on neighborhood graph reordering

In this paper we consider the problem of estimating pair-wise signals׳ dissimilarities through the comparison of the underlying local manifold structures. Aiming to confront with issues such as high geometrical complexity and significant overlap that characterize local manifold structures, we propose a novel dissimilarity measure which is based on the reordering of a neighborhood graph using a permutation of its nodes. In order to quantify the diversity between two manifolds, the dissimilarity function utilizes a measure of reordering efficiency, computed on each of the corresponding neighborhood graphs, using a permutation derived from the solution of an optimization problem on the opposite graph. We study the properties of the proposed measure, demonstrating its efficiency in a variety of applications, using both 1D and 2D signals. Additionally, by exploiting the links to previous findings from the field of random graphs, we introduce a generalization of the above measure based on the notion of multi-dimensional ordering. Finally, we perform a thorough evaluation on the problem of face recognition under various challenging conditions, obtaining state-of-the-art recognition accuracy with a competitive computational load.