Graph grammars for finding the optimal graph structure approximating the data

The graph grammars provide a well-developed formalism for the description of elementary transformations of a graph. Choosing an appropriate graph grammar operations, one can generate a class of graphs starting from the simplest one (e.g., containing two nodes and single edge).

In order to choose the most optimal structure of the principal graph, all possible applications of a grammar are evaluated and the best one in terms of decrease of the sum of the approximation error and the elastic energy is chosen for the next iteration (see Figure below).

If a graph grammar contains only one operation "Bisect an edge", this leads to the construction of principal curve approximations. Slightly more complicated set of two operations "Bisect an edge"+"Add a node to a node" results in construction of principal trees.