
GNNs have achieved great empirical success while theoretical understanding of GNNs, their non-linearity in particular, is still limited. There are many works studying the expressive power of GNNs [1]}, [2]}, [3]}, [4]}, [5]}, [6]}, [7]}, [8]}, [9]}, [10]}, [11]}, [12]}, while they often assume arbitrarily complex non-linearity with limited quantitative results. Only a few works provide characterizations on the needed width or depth of GNN layers [9]}, [11]}, [10]}, [12]}. More quantitative arguments on GNN analysis often depend on linear or Lipschitz continuous assumptions to enable graph spectral analysis, such as feature oversmoothing [17]}, [18]} and over-squashing [19]}, [20]}, the failure to process heterophilic graphs [21]}, [22]}, [23]} and the limited spectral representation [24]}, [25]}. Some works also study the generalization bounds [26]}, [27]}, [28]} and the stability of GNNs [29]}, [30]}, [31]}, [32]}. However, the obtained results may not reveal a direct comparison between non-linearity and linearity of the model, and their analytic techniques avoid tackling the specific forms of non-linear activations by using a Lipschitz continuous bound which is too loose in our case.
