UC Berkeley

Graphs are a rich and fundamental object of study, of interest from both theoretical and

applied points of view. This thesis is in two parts and gives a treatment of graphs from two

differing points of view, with the goal of doing inference on graphs. The first is a mathematical

approach. We create a formal framework to investigate the quality of inference on

graphs given partial observations. The proofs we give apply to all graphs without assumptions.

In the second part of this thesis, we take on the problem of clustering with the aid of

deep neural networks and apply it to the problem of community detection. The results are

competitive with the state of the art, even at the information theoretic threshold of recovery

of community labels in the stochastic blockmodel.