Stochastic block models (SBM) and its contextual counterparts have been widely used to study the node classification problems [1]}, [2]}, [3]}, [4]}, [5]}, [6]}, [7]}, while these studies focus on the fundamental limits. Recently, (C)SBM and its large-graph limitation also have been used to study the transferrability and expressive power of GNN models [8]}, [9]}, [10]} and GNNs on line graphs [11]}, while these works did not compare non-linear and linear propagation. CSBM has also been used to show the advantage of linear convolution over no convolution for node classification [12]}. A very recent result shows that attention-based propagation [13]} may be much worse than linear propagation given low-quality node attributes under CSBM [14]}. Our results imply that ReLU is the de facto optimal non-linearity instead of attention and may at most marginally outperform the linear model when with low-quality node attributes. Some previous works also use Bayesian inference to inspire GNN architectures [15]}, [16]}, [17]}, [18]}, [19]}, [20]}, [21]}, [22]}, while these works focus on empirical evaluation instead of theoretical analysis.
