Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper theoretically and empirically studies non-linearity and linearity in Graph Neural Networks (GNN) from the Bayesian-Inference Perspective and tries to explain the phenomenon that in practice for node classification tasks, the non-linearity of GNNs only has marginal improvement over their linear counterparts. The paper considers CSBM graph and one-hop neighbor settings with proper density and bounded attribution assumptions. The authors claim that the max-a-posterior estimation consists of two types of non-linearity, a non-linear transformation of node attributes and a ReLU-activated feature aggregation from neighbors. The paper also verifies their theorem on synthetic and real-world datasets.  
strengths_and_weaknesses: Strongness: 

1. Contribution: As far as I know, this is the first paper systematically study non-linear properties in GNN. The paper provides a clear take-home message that the non-linearity only makes a contribution when the Attributed Information is sufficient (Theorem 2). The theorem is strong enough to support the authors’ claim and seems consistent with our intuition. The observation about the ReLU non-linearity part is insightful. It is closely connected to the empirical GNN. Remark 1 is insightful. The paper also verifies their theorem on synthetic and real-world datasets. They are consistent with the theorem.
2. Writing: The paper has a clear motivation and good structure in Sections 3 and 4. The paper has all the necessary components, e.g., theorem and experiments. 

Weakness:

1. The gap in Figure 1 right is not large enough. It would be better to plot with a larger x. 
2. The discussion about the non-linearity of node-attribute transformation is limited. It would be better to give one more example for the NN case, e.g., a two-layer network. 

Claim: I only checked a limited part of the proof. 

questions: 1. Due to the CSBM setting, the paper can directly get the closed form solution equation (4) and give an analysis. I wonder is there any way to generalize the result, e.g., each node has its private connecting probability. 
2. Assumption 1 (Moderate Structural Information) means that the paper only considers a dense regime. Nowadays, community cluster detection works on sparse regime, e.g., S(p,q) = O(1/n) in [1]. Is the analysis still guaranteed in this regime? 
3. The non-linearity of a real dataset is hard to measure. Is there any way to metic the non-linearity in the dataset? Figure 4 seems related but still weak. 

[1] Li, Xiaodong, Yudong Chen, and Jiaming Xu. "Convex relaxation methods for community detection." Statistical Science 36.1 (2021): 2-15.

limitations: The paper only considers a 1-hop neighbor. It would be better to consider a 2-hop neighbor. I believe that for a 2-hop neighbor the gap between linearity and non-linearity will be much larger. For the experiments, the scale problem can be solved by sub-sampling.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper characterizes the effect of non-linearity in GNNs from a Bayesian inference perspective. It shows whether non-linearity is beneficial is related to whether node attributes are more informative than structural information. Experiments are conducted to verify the theoretical results.
strengths_and_weaknesses: The paper studies a very interesting research question concerning the role of non-linearity in GNNs. It poses valuable theoretical results answering when and why non-linear propagations have the potential to outperform linear counterparts, which is of benefit to the GNN community. The idea of using MAP to study the optimal propagation scheme may be of interest beyond the scope of this paper. The results also seem solid though I didn’t verity proofs in the supplementary material. Extensive experiments are conducted, and the results appear to align with the theoretical findings.

I also think the paper is clearly written and easy-to-follow. I appreciate that the authors tried to give high-level explanations of theories throughout the paper. Yet, there seems to be some typos, e.g., Eq.(3) in line 199 and 203 should be Eq.(4)? I suggest the authors double checking equation references. 

However, I have a lingering concern regarding the discrepancy between the models used for analysis (i.e., Eq.(3) and Eq.(7)) and the common ones used in practice (e.g.,  non-linear [1-3], linear [4,5]). Though the models considered in the paper are valid GNN instantiations, the corresponding functions $\phi$ and $\psi_{Gau}$ are different with their counterparts in mainstream GNN models (i.e., $\phi$ is ReLU and $\psi$ is linear map), and usually we also apply activation function to $\psi(X_{v})$ in Eq.(3). It is also strange that baseline linear model in Eq.(7) still uses $\psi$ since it corresponds to using feature transformation in conventional linear GNNs. Whether the theoretical results generalize to other GNN settings is questionable (both theoretically and empirically). Maybe the authors can shed more lights on this? 

[1] Semi-supervised classiﬁcation with graph convolutional networks. 
[2] Inductive representation learning on large graphs.
[3] Graph attention networks.
[4] Simplifying graph convolutional networks.
[5] LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation.
questions: See above.
limitations: I don’t think this paper has any negative societal impact.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This paper studies when non-linearity is useful for accuracy in graph neural nets. Authors show that under assumptions, the superiority of ReLU activations is only significant when the node attributes are far more informative than the graph structure. 
----
Authors say that I gave "accept score" initially. This is wrong.
Somehow this year "5" means borderline accept, but usually it meant "weak reject". So I intended to reject. I took another look of the paper and I feel the paper is not ready for publication so changed score to reject. 
strengths_and_weaknesses: Strength:
1. The problem of non-linearity is interesting and useful in practice.
2. The result shows some interesting implications, e.g., when structure vs feature is more important. Though the main message is too vague to be useful.

Weakness:
1. The main conclusion is vague and not so clear. The main point of the paper is trying to claim that "the superiority of ReLU activations is only significant when the node attributes are far more informative than the graph structure." However, it's not clear what you mean by node attributes are more informative than graph strucutre. A very clear definition and intuition, examples need to be give. 
2. It's not clear what practical implication we can gain? Why not just always add non-linearity, since they will outperform in some cases?

Authors need to clearly resolve my concerns to raise rating.
questions: 1. The main conclusion is vague and not so clear. The main point of the paper is trying to claim that "the superiority of ReLU activations is only significant when the node attributes are far more informative than the graph structure." However, it's not clear what you mean by node attributes are more informative than graph strucutre. A very clear definition and intuition, examples need to be give. 
2. It's not clear what practical implication we can gain? Why not just always add non-linearity, since they will outperform in some cases?

Authors need to clearly resolve my concerns to raise rating.
limitations: 1. The main conclusion is vague and not so clear. The main point of the paper is trying to claim that "the superiority of ReLU activations is only significant when the node attributes are far more informative than the graph structure." However, it's not clear what you mean by node attributes are more informative than graph strucutre. A very clear definition and intuition, examples need to be give. 
2. It's not clear what practical implication we can gain? Why not just always add non-linearity, since they will outperform in some cases?

Authors need to clearly resolve my concerns to raise rating.
review_title: null

Meta-review: metareview: The paper studies the functions of non-linearity in GNNs for node classification tasks, through Bayesian learning. It considers graphs from the statistical model CSBM and shows the max-a-posterior estimation for the label has two types of non-linearity. With Gaussian assumption on the node attributes it further proves that the second type of nonlinearity is only superior when the attributes are far more informative that the graph structure; similarly when there is a distribution shift between training and testing. It also provided verification experiments on synthetic and real data.

The paper considers an important topic and has provided a novel in-depth investigation. Some concerns of the reviewers are:

1. Interpretation of the theoretical results. The theorems are quite technical, and more elaboration on their implications can the readers appreciate better the results. The authors have provided some more clarification in the response.  

2. Connections between the theoretical models and the practical ones. The analysis makes some assumptions, e.g., dense CSBM graphs, Gaussian attributes. On the other hand, some simplifying assumptions are necessary for theoretical study. The empirical verification also matches the theory well. 
confidence: Less certain
Decision: Accept