Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper investigates the effects of different normalizations of the adjacency matrix as the convolution operator in graph neural networks. In particular, they present a theoretical investigation of GNNs in the Neural Tangent Kernel (NTK) limit (very wide limit where training the GNN is equivalent to kernel regression on the NTK – without the need to optimize hyperparameters). They study the effects of four different convolution operators with different normalizations on SBMs, and show that some normalizations (row norm) preserve the ‘block’ structure better than others even at (relatively) large depths of 5 or more. They show empirically that row normalization is the most likely to preserve this structure, while other operators diffuse information over the graph as the network gets deeper. The authors also investigate two types of skip connections and show theoretically that they retain the structural information of the SBM even at infinite width.
strength_and_weaknesses: Strength: Results are clear, novel, and interesting, the math seems correct, and the paper brings a new perspectives on GNNs in the NTK limit.

Comments:
The results, although compelling, are restricted to one example, i.e., preserving class structure in one model of graphs (DC SBMs). I would be interested in seeing if this holds true more generally for other models of random graphs. For instance if one considered a graph with a few core nodes and some peripheral structure, is row normalization the best choice to preserve such ‘importance’ structure here as well (where one could look at the difference between core-to-core and core-to-periphery as a metric) – this should generally hold I think, since diffusion operators capture notions of ‘importance’? Classes here could be defined as communities analogous to the authors’ suggestion, but the degree distribution within each class is bimodal.
 How about graphs with many triangles, versus graphs that are locally tree-like? Does the analysis extend just as easily to signed graphs (positive and negative weights)? Even if not, a discussion on assumptions of graph structure considered here would be very useful. 
A question of particular interest to me (which may be beyond the scope of this paper), is if there exists a normalization (perhaps one of the four proposed) that best preserves the ‘topological’ structure of the graph, i.e., holes in graph, in addition to the class structure. 

Could one define a metric for ‘distance’ between graphs. One might define two graphs to be ‘structurally’ similar if the have equivalent ‘mixing’ between classes after d layers. A GNN with improved expressive power should be better for defining better distance metrics, I think.

What is the conclusion from the section on skip connections? Is one type of skip connection supposed to work better with row norm, and another with sym? This was not clear to me. Panels on second row of Fig 4 (comparison between skip-PC and skip-alpha) look very similar to me. 

clarity,_quality,_novelty_and_reproducibility: It is well written, well structured, and is of broad interest to an audience in theoretical machine learning on graphs. Their results are assumptions are clearly stated. The results are novel. 
They cite other github repos such as GCN code they have adapted code from, but do not provide a link to their own code (as far as I can see). For reproducibility, I would suggest adding a github link to the authors' code in the NTK limit.
summary_of_the_review: The paper presents an interesting study on the expressive power of GNNs. It presents theoretical results (under certain orthonormality of features conditions), but shows that some of the results hold empirically in a more general case.
Graph NTKs have been introduced before…the novelty of this work is in the study of different normalizations of the convolution operator. Overall, while I have some questions on the generality of their results to other random graph models (if the results are general, this would strengthen their results), I believe the results are informative and interesting, and would recommend for publication, especially with additional discussion and testing for generality.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper defines a graph neural tangent kernel (NTK) in a semi-supervised node classification setting. Under the degree-corrected stochastic block model (SBM), it then uses the graph NTK to explain, theoretically and empirically, why (i) row normalization performs better than symmetric normalization; (ii) with row normalization, performance degrades more slowly with the network depth; and (iii) skip connections improve performance for both types of normalization.
strength_and_weaknesses: Strengths:

- The problem addressed by the paper---understanding the effect of design choices such row/symmetric normalization, depth, and residual connections---is timely and important.
- The empirical results in Figure 3 (left) are convincing in showing the effect of skip connections on class separability in node classification problems.

Weaknesses:

- The motivation of the paper is somewhat ill-defined. The motivation for analyzing the effect of depth comes from the observation, in Figure 1, that the performance of GCNs with symmetrically normalized adjacency matrices degrades faster with depth than that of GCNs with row normalized adjacency matrices. However, if the best accuracies in this figure are achieved for 2 layers, and the difference between symmetric and row normalization in the 2-layer case is small, why are we concerned with what happens for a larger (or even infinite) number of layers?
- The modeling assumptions restrict the applicability of the analysis, as it is likely that the SBM model used to conduct the NTK analysis and the specific task (community detection/separability of communities) are biased towards the row normalized adjacency matrix (also known as the random walk matrix). It is well known that community detection methods based on random walks (e.g., node embeddings such as DeepWalk; spectral methods based on the non-backtracking operator) fare better than methods based on symmetric aggregations. Moreover, not every node classification problem can be modeled as detecting communities, especially when considering heterophilous graphs. This is for instance suggested by [r1] below, where it is noted that the row-normalized adjacency is more limited in the amount of topological information that it carries. 
- Although the result in Theorem 2 agrees with the numerical results, i.e., it explains why the row normalized adjacency does better than the symmetrically normalized adjacency in practice, the result itself gives no intuition as to why that is the case, and an interpretation is not given by the authors.
- Although the NTK analysis is only accurate in the infinite width limit, the paper uses it to justify behaviors observed in the finite width limit. The justification for doing so is that the infinite width of the GCN does not affect the graph convolutions. However, infinite width certainly affects performance, as it corresponds to an overparameterized regime.
- The numerical experiments are limited. Specifically, they are restricted to class separability on SBMs and node classification on citation networks. Neither of these problems are adequate choices to analyze the effect of GCN depth, as both are relatively simple, consensus-like problems in which shallow and linear models have been shown to achieve very good performance. Additionally, the classification accuracy, which is the evaluation metric of interest for Cora, is not reported for this dataset.

Minor:

- The **Remark on Assumption 1**, particularly that "the linearized GCN performance is at par with the non-linear models with much reduced complexity", is misleading. This may be true in consensus-like problems like Cora and Citeseer, but it is not the case in problems where the relevant information lies in high graph frequencies. See, e.g., Fig. 3c in [r2].
- It is not "conventional" wisdom that GCNs "exhibit improvement in performance as depth increases" (third paragraph of the introduction). Overly increasing the depth may lead to overfitting.

[r1] Jeong, Sowon, and Claire Donnat. "Tuning the Geometry of Graph Neural Networks." arXiv preprint arXiv:2207.05887 (2022).
[r2] Ruiz, Luana, Luiz FO Chamon, and Alejandro Ribeiro. "Transferability Properties of Graph Neural Networks." arXiv preprint arXiv:2112.04629 (2021).
clarity,_quality,_novelty_and_reproducibility: The paper is mostly clear and well-written, but certain passages are difficult to understand. A non-exhaustive list:

- Assumption 2 and the corresponding remark are unclear; in particular, why does this assumption "enable(s) the computation of analytic expression for the population NTK instead of the expected NTK?"
- Theorem 2 is hard to parse, and the discussion following it is not obvious from the theorem. Either simplify the equations, or conduct a more detailed discussion.
summary_of_the_review: The problem addressed by the paper---understanding the effect of design choices such row/symmetric normalization, depth, and residual connections---is timely and important. However, the motivation for the proposed approach is ill-defined, the modeling assumptions restrict the applicability of the analysis, and the numerical experiments are limited.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper attempted to explain the superiority of row-normalized adjacency matrices as the graph convolution operator for node classification in GNNs from the viewpoint of graph neural tangent kernels (GNTK). This paper derived GNTKs for GNNs with finite and infinite layers (and with an infinite number of units) for various adjacency matrices when the underlying graph is a populated Degree-corrected SBM (DC-SBM), and the input matrix is orthogonal. By comparing the GNTKs, this paper showed that the row-normalized adjacency matrix is more capable of identifying nodes than the other design choices (symmetrized, raw, and column-normalized adjacency matrices). In addition, this paper considered GNTK for GNNs with initial residuals and showed that GNTK could identify nodes even with an infinite number of layers, provably avoiding over-smoothing.
strength_and_weaknesses: Strengths
- Few studies have investigated the impact of the design choice of adjacency matrices as a graph convolution operator. 

Weakness
- I have a question about the significance of the research question that this paper addressed (see Novelty section). 
- The theoretical analysis needs to discuss the validity of the assumptions more (see Quality section).
- The interpretation of the results of the theoretical analysis is questionable
- It is desirable to clarify the relationship between the theoretical analysis and the numerical experiments more.
clarity,_quality,_novelty_and_reproducibility: Clarity

This paper is well-written. I do not have any difficulty understanding the main points of the paper.


Quality

I have a question about the problem setting of the theoretical analysis because it looks somewhat artificial. This paper claimed the usefulness of row-normalized adjacency matrices by comparing the behavior of GNTKs (Theorem 2). This result strongly depends on the assumption that the underlying SBM is degree-correlated. I expected the authors to show why it is reasonable to assume the graph-generating process used in this paper.

I could not see why Theorem 2 shows the usefulness of row-normalized adjacency matrices. This paper claimed the superiority of row-normalized adjacency matrices on the ground that "only $\tilde{\Theta}_{\mathrm{row}}$ exhibits a block structure unaffected by the degree correction $\pi$, and the gap is determined by $r^2$ and $d$". However, I could not see why the independence from $\pi$ implies the superiority of row-normalized adjacency matrices.

The relationship between theoretical analysis and empirical evaluation was not very clear to me. 
According to the paper, we have an empirical fact that GNNs with row-normalized adjacency matrices perform well. Therefore, I expect the theoretical analysis's assumptions are empirically reasonable. However, this paper did not discuss the justification of the assumptions. Also, numerical evaluations considered the situation where the assumption of theoretical analysis does not hold (even approximately). Instead, this paper claimed the practical superiority of row-normalized adjacency matrices without assumptions. Therefore, it seems to me that it implies that the assumptions are superfluous and do not reflect real-world situations.
Therefore, I could not see what the numerical evaluations wanted to show and how they were related to theoretical analysis.


Novelty

As far as I know, no paper has given a theoretical explanation for the usefulness of row-normalized adjacency matrices in GNNs. So in that sense, this paper is novel.
On the other hand, I question whether the problem of this paper is sufficiently significant because, to the best of my knowledge, the superiority of row-normalized adjacency matrices is not well-known. This paper referred Wang et al., 2018, Wang & Leskovec, 2020, and Ragesh et al., 2021 as existing studies of GNNs using row-normalized NNs. However, it is difficult to say that they support the significance of the research question of this paper:
- Wang et al., 2018 certainly claimed the usefulness of row-normalized adjacency matrices. However, they discussed it in the context of adversarial attacks. The relevance of the node prediction considered in this issue is not apparent.
- In Wang & Leskovec, 2020, row-normalized adjacency is introduced because of the analogy with label propagation. However, they did not compare it with a symmetrized adjacency matrix was not made.
- Ragesh et al., 2021 used three types of NNs: raw, row-normalized, and symmetrized matrices. However, it did not state which one was the best.
Therefore, I have question about the significance of the research question this paper addressed.


Reproducibility

The code and datasets for the numerical experiments are provided. It allows readers to see the details of the implementation. In addition, instructions for reproduction are provided. Although I have not run the code, I expect that it is possible to reproduce the same experiments as the authors.
summary_of_the_review: Although the choice of the adjacency matrix is one of the design choices, the significance of the research question is questionable, considering the line of previous studies. Also, unless I missed it, the reason for making that assumption about the theoretical analysis is not discussed qualitatively or experimentally, and its validity is questionable.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: I am not in good position to review
strength_and_weaknesses: I am not in good position to review
clarity,_quality,_novelty_and_reproducibility: I am not in good position to review
summary_of_the_review: I am not in good position to review
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper utilizes the graph neural tangent kernel to theoretically prove the superiority of row normalization in a semi-supervised node classification setting. It is proven that row normalization can preserve the class structure better, and work better at reducing over-smoothing, especially when combined with skip connections,
strength_and_weaknesses: Strength:
This paper provides a theoretical analysis of why row normalization is better than symmetric normalization, which is absent from current research. Thus, it provides insight and potential research direction.

Weakness:
1. Graph neural tangent kernel is presented by others before.
2. The observations are discovered previously by others empirically.
3. The underlying reasons for the observations have been discussed or at least inferred somewhere else.
4. No further proposal is made based on the proof.
clarity,_quality,_novelty_and_reproducibility: Novelty:
The author(s) claims that the paper is the first theoretical proof of this topic. However, after the proof, they fail to provide new knowledge about the GCNs field.

Quality:
The proof looks legit and correct.

Clarity:
A few pronouns are not well defined, thus bringing confusion. For example, in the second sentence in the abstract, it is not clear what the authors refer to by "its". 

Reproducibility:
Datasets and implementation are provided in the supplementary. The empirical part of this paper is not critical though.
summary_of_the_review: By theoretically proving that row normalization and skip connection work better in semi-supervised node classification tasks, this paper serves as a good suggestion for how to implement GCNs. However, it lacks a further discussion on what we can do differently from the current existing approaches.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: __Summary.__ This work proposes an analysis of the impact of the convolution operator on the performance of GNN through the lens of Neural Tangent Kernels for semi-supervised node classification tasks. Under the degree-corrected stochastic block model (SBM), it uses the graph NTK to explain, theoretically and empirically, why  and when row normalization performs better than symmetric normalization; They further show that, with row normalization, performance degrades more slowly with the network depth; and finally, they highlight why skip connections improve performance for both types of normalization. The use of the NTK foregoes the problem of parameter tuning, and allows them to draw insights on the benefits of the different types of convolutions.


__Overview of criticisms raised during the review process.__
Overall,  at the exception of one reviewer who deems the paper to be good, all the other three vote for a strong rejection (note that we are excluding the opinion of a fifth reviewer, who declared themselves unable to assess the paper). The main criticisms expressed by the reviewers were (a) a lack of justification for the study of the normalized and symmetric convolutions through the degree corrected SBM, (b) a lack of appropriate numerical experiments, and (c) the inability to generalize to other graphs beyond the degree corrected SBM that the authors consider. While during the review process the authors have attempted to address these issues by running experiments on other types of graphs, the edits do not seem to have satisfied fully the reviewers. The consensus amongst the reviewers seems to be that the results are hard to interpret as well. The approach was however interesting and the problem, “timely” as expressed by the reviewers. __While we advise a rejection of this paper, we therefore encourage the authors to continue improving their paper based on the feedback that they have received and re-submit in the near future.__

justification_for_why_not_higher_score: As stated above, the main criticisms expressed by the reviewers were (a) a lack of justification for the study of the normalized and symmetric convolutions through the degree corrected SBM, (b) a lack of appropriate numerical experiments, and (c) the inability to generalize to other graphs beyond the degree corrected SBM that the authors consider. While during the review process the authors have attempted to address these issues by running experiments on other types of graphs, the edits do not seem to have satisfied fully the reviewers.
Decision: Reject