In this work, we expect to give a more precise characterization of the values of non-linearity in GNNs from a statistical perspective, based on Bayesian inference specifically. We resort to contextual stochastic block models (CSBM) [1]}, [2]}. We make a significant observation that given a graph generated by CSBM, the max-a-posterior (MAP) estimation of a node label given its own and neighbors' features surprisingly corresponds to a graph convolution layer with ReLU as the activation combined with an initial node-attribute transformation. Such a transformation of node attributes is generally nonlinear unless they are generated from the natural exponential family [3]}. Since the MAP estimator is known to be Bayesian optimal [4]}, the above observation means that ReLU-based propagation has the potential to outperform linear propagation. To precisely characterize such benefit, we further assume that the node attributes are generated from a label-conditioned Gaussian model, and analyze and compare the node mis-classification errors of linear and nonlinear models. We have achieved the following conclusions (note that we only provide informal statements here and the formal statements are left in the theorems).
