Scalable and Interpretable Graph Modeling with Graph Grammars

Unearthing the interaction patterns of the LEGO-like building blocks that make up a complex system provides a unique perspective into its inner workings. Being able to methodically encode, extract, and analyze those pieces represents a significant challenge. This dissertation demonstrates how a newfound link between formal languages, graph theory, and data mining helps to address this challenge. I achieve this by adopting the formalism of vertex replacement graph grammars, which provides the ability to formally encode graph substructures. Extracted grammar rules also provide for a better understanding of the network's underlying topology and simultaneously provides for the ability to generate, extrapolate, and infer new graphs in a precise and principled fashion.