Principled Graph Structure Extraction

This dissertation deals with two questions: (Q1) How do you tell a computer to extract new and interesting patterns from graphs without already knowing what those patterns look like? What even is a pattern in a graph? How do you formalize that notion of pattern in a way that is simultaneously generalized enough to encapsulate new phenomena yet specific enough to be meaningful and computationally tractable? (Q2) How do symmetries in graphs relate to each other, and how do they affect tasks such as link prediction? Question 2 is closely related to question 1 because when we explore the notion of pattern in graphs, we find that it coincides with symmetry.

I initially explore Q1 via small, local patterns I call "subgraph-to-subgraph transitions." Then at the end of the dissertation I re-address the question in a much more global and principled manner that ties graph pattern to symmetry (automorphisms); this allows me to uncover a wide variety of graph patterns across different datasets. I explore Q2 by proving that graph automorphisms impose performance constraints on tasks like link prediction, and I also prove a theorem relating the symmetries of any two n-node graphs.