Abstract

Contextual Stochastic Block Models (cSBMs) are simple generative graph models commonly used to benchmark the performance of Graph Neural Networks (GNNs). In this thesis, I prove how inducing symmetries on general, nonlinear GNNs improves their cross entropy on cSBMs, and I derive the limiting accuracy of linear Graph Convolutional Networks (GCNs) on cSBMs. I use these results to derive the functional form of cross-entropy optimal GCNs on cSBMs and compare them to accuracy optimal GCNs.

Degree

College and Department

Computational, Mathematical, and Physical Sciences; Mathematics

Rights

https://lib.byu.edu/about/copyright/