Quantifying the Effects of Edge Uncertainty on Node Embeddings

Uncertainty quantification is an essential step for developing reliable and trustworthy machine learning models. While a plethora of methods have been developed for quantifying predictive uncertainty of graph neural networks, theoretical insight into the impact of uncertain graph structure on node embeddings remains limited. Here, we leverage tools from the study of exponential random graphs to rigorously derive node-wise preactivation distributions for graph convolutional networks, highlighting sparsity as the key parameter governing the form of this distribution. On random graphs with diverging average degrees, message passing is asymptotically deterministic; however, on random graphs with constant average degrees, node preactivation distributions retain finite variance.