Geometry of Graph Edit Distance Spaces
This work provides foundational tools for statistical pattern recognition in graph-based data, though it appears incremental as it builds on existing orbit space theory.
The paper tackles the problem of analyzing graph spaces with graph edit distances by proving the Graph Representation Theorem, which maps graphs to points in orbit spaces, making them easier to explore for statistical pattern recognition.
In this paper we study the geometry of graph spaces endowed with a special class of graph edit distances. The focus is on geometrical results useful for statistical pattern recognition. The main result is the Graph Representation Theorem. It states that a graph is a point in some geometrical space, called orbit space. Orbit spaces are well investigated and easier to explore than the original graph space. We derive a number of geometrical results from the orbit space representation, translate them to the graph space, and indicate their significance and usefulness in statistical pattern recognition.