Graph attribute embedding via Riemannian submersion learning

In this paper, we tackle the problem of embedding a set of relational structures into a metric space for purposes of matching and categorisation. To this end, we view the problem from a Riemannian perspective and make use of the concepts of charts on the manifold to define the embedding as a mixture of class-specific submersions. Formulated in this manner, the mixture weights are recovered using a probability density estimation on the embedded graph node coordinates. Further, we recover these class-specific submersions making use of an iterative trust-region method so as to minimise the L2 norm between the hard limit of the graph-vertex posterior probabilities and their estimated values. The method presented here is quite general in nature and allows tasks such as matching, categorisation and retrieval. We show results on graph matching, shape categorisation and digit classification on synthetic data, the MNIST dataset and the MPEG-7 database. (C) 2011 Elsevier Inc. All rights reserved.