Although empirical studies on GNNs are extensive till now and many practical observations as above have been made, there have been very few works attempting to characterize GNNs in theory, especially to understand the effect of non-linearity by comparing with the linear counterparts for node classification tasks. The only work on this topic to the best of our knowledge still focuses on comparing the expressive power of the two methods to distinguish nodes with different local structures [1]}. However, the achieved statement that non-linear propagation improves expressiveness may not necessarily reveal the above phenomenon that non-linear and linear methods have close empirical performance while with subtle difference. Moreover, more expressiveness is often at the cost of model generalization and thus may not necessarily yield more accurate prediction [2]}, [3]}.
