Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a p-Laplacian based GNN to handle heterophilic graphs and graphs with non-informative topologies. Both the above cases are assumed in most existing GNN architectures and hence this work breaks away from the norm. This work proposes a discrete p-Laplacian message passing scheme which is derived from a discrete regularization framework. The authors do a spectral analysis of their novel p-Laplacian message passing scheme and show that it works as both a low-pass and high-pass filter, which is then applicable to both homophilic and heterophilic graphs. More specifically, they show that p-GNN with p>2, works well for graphs which exhibit strong homophily, while for p \in [1,2) p-GNN works effectively on heterophilic graphs. The empirical results support the theoretical justifications and outperform the baselines quite significantly especially on heterophilic and non-informative topology bearing graphs.
main_review: -- Strengths:

1. The paper is very well-written and easy to follow. It was a pleasure to read the novel theoretical material presented in this paper. 

2. The paper proposes a novel architecture of p-GNN that introduces p-Laplacian message passing by leveraging and infusing existing architectures like SGC, APPNP and GPRGCN. 

3. The theoretical connection drawn between the “p-Laplacian message passing scheme” and “the polynomial graph filter defined on the spectral domain of the p-Laplacian” is particularly interesting. 

-- Weaknesses:

1. It would have been interesting to see a theoretical justification as to why p-GNN always outperforms say GCNs, GATs, etc. (models that stack their message passing layers) on heterophilic graphs. Can the authors please elaborate on this point in their rebuttal? I feel this would give more insights into the behavior of p-GNN and why it is outperforming standard GNN models. 

2. Much of the material in Sections 2 and 3 is obtained from Zhou and Scholkopf 2005. Less space could have been used for this explanation.

3. The function signature for the graph gradient operator in Definition 1 does not look right. The domain of this operator has to be a space of functions, it cannot be the set of vertices. Can you please relook into this?

4. In regards to the experiments conducted on noisy edges, it would be interesting to see how p-GNN performs on some stochastic block models based on edge dropping and some other random graph percolations. The random edge drop model seems a bit simplistic and it's not easy to see how this sort of noise is affecting the graph inputs and why p-GNN should do better than other robust GNNs?

5. In regards to the following statement in the paper on Pg 6. 				

“Therefore, for graphs whose topological information is not helpful for label prediction, we could impose more weights on the first term in Eq. (18) by using a large μ so that P-GNNs work more like MLPs which simply learn on node features. While for graphs whose topological information is helpful for label prediction, we could impose more weights on the second term by using a small μ so that P-GNNs can benefit from p-Laplacian smoothing on node features.” 

How does one determine when the graph’s topological information is helpful for
label prediction, as opposed to when it’s not?

summary_of_the_review: The paper is well written and presents a novel p-GNN architecture on top of other PageRank based GNN architectures. I found the theoretical justifications and connections drawn between the message passing scheme and the polynomial graph filter particularly interesting. Also, they had an interesting bound on the risk (Theorem 3). I am overall quite positive about this paper's acceptance, as it makes novel contributions to handle a difficult scenario like heterophilly in graphs and also the fact that they challenge the implicit assumption made by previous works that the "shape of node neighborhoods" helps distinguish nodes.. of course this can be extended to graph shapes too.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper derives the p-Laplacian message passing formula under the p-Laplacian based regularization framework and further proposes p-GNN architecture. Authors further justify the relations of p-Laplacian message passing with low and high-pass filters and the upper bound of
one layer risk of p-GNNs. Experiments show the superiority of p-GNNs on both heterophilic and homophilic settings. However, we still have some concerns for the paper before further evaluation.
main_review: The paper proposes general p-GNNs architecture under the p-Laplacian regularization framework
with comprehensive experimental results. The paper is well written and the theoretical part is well
organized, though not significant. However, we still have some concerns. 

Strength:
(1) The author proposes a new general GNN architecture based on p-Laplacian message passing,
which claims to work on both heterophily and homophily settings.
(2) Relations of p-Laplacian message passing with low-pass and high-pass filters have been
explained.
(3)Experiments are comprehensive and inclusive.

Weakness:
(1) More insights on how to choose parameter p should be given. From the upper bound risk theorem, we only know that for K=1, the risk can be controlled by \mu which further depends on whether the topological information of graphs is useful or not. However, for K >=2, we do not see the relations. More insights are welcomed.

(2) The stationary point for the objective function in equation 8 is problematic when $p < 2$ and $\nabla f =0$. In particular, when $p=1$  and $\nabla f =0$, the Laplacian diffusion should have a step function that is not continuous at $\nabla f =0$. The authors seem not to have given a good discussion on this aspect. 

(3) Moreover, when $p<2$, the graph diffusion operator is not Lip-continuous, which violates the assumption made by the upper-bounding risks theorem. So I do not see how that theorem can be applied here. 

(4) For p=1, the diffusion becomes a step function (piecewise constant), how can the model be trained? Can the authors also provide the training curve for the p=1 case?

(5) P-GNN can only get comparable performances on homophilic benchmark datasets (both
accuracy and entropy experiments).

(6) The authors claim that p-lap can handle the heterophilic case. And the explanation is that the p-lap allows big change on the class boundary which can be viewed as a high-pass filter. I do not think this argument is very convincing. Can the authors have TSNE of the node embeddings for the heterophilic case so that we can get some visualization of the results?


Some typos:
(1)Page 2, last paragraph: Heterphily -> Heterophily
(2)Section 3.1, R^N should be changed into N
summary_of_the_review: See the main review.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors propose a new message-passing design based on p-Laplacian. They demonstrate that their method works better in heterophilic graphs.
main_review: ## Pros:

(+) The idea of designing new message-passing based on p-Laplacian is interesting.

(+) The empirical evaluation of cSBM is great.

(+) The high-level idea on the effect of different choices of p is inspiring.

## Cons:

(-) Most theorems derived in this paper are either well-known (Theorem 1) or not meaningful (Theorem 3).

(-) The overall clarity of the paper can be improved, especially in section 4.

(-) Some concerns regarding the choice of hyperparameters (see detail below).

## Detail comments:

-	Theorem 1 is well-known in the graph learning community, (see [4], equation (3) for example). I think there should be a proper reference for it.
-	Theorem 3 is not very meaningful, as the derived risk bound is greater than discarding the graph part ($\beta = 1,\; \alpha = 0$). This is because the analysis does not take the correlation of graphs into account. See [3] on how the authors show the graph convolution is helpful under cSBM assumption. I feel like the analysis and result here can be further improved for meaningful bound.
-	The clarity of section 4 and explanation of Theorem 2 should be improved. Regarding the explanation of Theorem 2, I cannot understand why the “weight effect” of p-Laplacian based message passing can help for heterophilic graphs. What does the “boundary of the lined nodes” refer to in the explanation? On the other hand, while I like the explanation of Proposition 1, I feel like the authors treat the matrix M as fixed in this section. However, according to their definition, it should depend on the input feature matrix. Please elaborate more on this point and improve the clarity of the text.
-	I find it weird for the choice of hyperparameter for all baseline methods. More precisely, the authors choose the hidden unit = 16 while the default and common choice is 64. I wonder why the authors detour from the standard choice.

### Typo:

1.	Page 2, the reference of the cSBM is incorrect. Should be [1].

2.	Page 5, in Remark 2: “In contrast, it is is similar with SGC…”, redundant “is” here.

### Additional questions:

1.	The matrix M in Theorem 2 depends on the node embedding F right? I assume it follows the specific aggregation rule of equation (12).

2.	Does the iteration (11)-(13) guarantee to converge?

## Reference:

[1] Contextual stochastic block models. Deshpande et al. NeurIPS 2018. 

[2] Optimizing generalized pagerank methods for seed-expansion community detection, Li et al. NeurIPS 2019.

[3] Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization, Baranwal et al. ICML 2021.

[4] PREDICT THEN PROPAGATE: GRAPH NEURAL NETWORKS MEET PERSONALIZED PAGERANK, Klicpera et al. ICLR 2019. 

summary_of_the_review: I have mixed feelings about this paper. On one hand, I like the newly designed message passing scheme and their implicit bias demonstrated in Proposition 1. Also, conducting experiments on cSBM is great for studying problems of heterophilic graphs. On the other hand, the drawbacks of the paper prevent me from supporting acceptance of it. I think the paper has great potential but requires a major revision.
review_title: null

Meta-review: This work studies a variant of a message-passing scheme,  aiming to improve the efficiency of GNNs to heterophilic graphs, as well as improving its stability to noise. The authors provide a new architecture, called $p$-Laplacian message passing, as well as some theoretical analysis and empirical evaluation. 
Reviewers highlighted several positive aspects on this work, such as the general idea of considering p-Laplacians, as well as the extensive empirical evaluation. However, during the review discussions, several important issues arose, namely important concerns regarding the theoretical contributions, as well as concerns in calibrating the baselines in some empirical evaluations. Overall, the AC is of the opinion that this paper requires a further iteration before it can be considered for publication, and encourages the authors to take the time to address the comments raised by the reviewers.
Decision: Reject