Inference on Graphs: From Probability Methods to Deep Neural Networks
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.