Principled Graph Structure Extraction

<p>This dissertation deals with two questions: <strong>(Q1)</strong> 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? <strong>(Q2)</strong> 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.</p><p><br>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.</p>