On the geometry of graph spaces

Optimal alignment kernels are graph similarity functions defined as pointwise maximizers of a set of positive-definite kernels. Due to the max-operation, optimal alignment kernels are indefinite graph kernels. This contribution studies how the max-operation transforms the geometry of the associated feature space and how standard pattern recognition methods such as linear classifiers can be extended to those transformed spaces. The main result is the Graph Representation Theorem stating that a graph is a point in some geometric space, called orbit space. This result shows that the max-operation transforms the feature space to a quotient by a group action. Orbit spaces are well investigated and easier to explore than the original graph space. We derive a number of geometric results, translate them to graph spaces, and show how the proposed results can be applied to statistical pattern recognition.