  An enormous amount of real-world data exists in the form of graphs.
Oftentimes, interesting patterns that describe the complex dynamics of these
graphs are captured in the form of frequently reoccurring substructures. Recent
work at the intersection of formal language theory and graph theory has
explored the use of graph grammars for graph modeling and pattern mining.
However, existing formulations do not extract meaningful and easily
interpretable patterns from the data. The present work addresses this
limitation by extracting a special type of vertex replacement grammar, which we
call a KT grammar, according to the Minimum Description Length (MDL) heuristic.
In experiments on synthetic and real-world datasets, we show that KT-grammars
can be efficiently extracted from a graph and that these grammars encode
meaningful patterns that represent the dynamics of the real-world system.
