Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: Paper Summary:

Paper summary:
This paper attempts to incorporate generalized page rank (GPR) in Graph Neural Networks (GNNs), aiming to address two problems plaguing GNNs: i) Existing message-passing based GNNs are best suited to handle graph-structured data with the homophily property and may not be able to handle those with the heterophily property. ii) Existing GNNs suffer over-smoothing which force them to be "shallow." The key idea of GPR is to introduce a weight factor $\gamma_k$ in the kth iteration of computing the page rank score. The authors conduct extensive evaluation using bencmark datasets, and show improvements over some existing GNN methods.

Pros:
  + Attempt in addressing the potential limitations of message-exchange based GNNs that may not be suited to deal with graph datasets with heterophily relations.
  + Evaluation using both synthetic data based on  contextual stochastic block models (cSBM) and real-world "heterophily" datasets.

Concerns:

  - The paper starts by talking about the "trade-offs" between node features and graph topology. However, the bulk of the paper is focused on using GPR as a more "general" graph filter as in the "standard" GNNs. The latter in recent years, unfortunately, since the work of Kipf & Welling, have primarily used variants of a simple graph of the form I+A.  Based on the GPR-GNN model shown in Fig.1, the node features {X_i} are only used to initialize H^{(0)}. In other words, the node features do not factor into the choice (or learning) of \gamma_k's in the latter stage.

 - One would assume that where a graph or network is "homophily" or "heterophily" would be in some matter encoded in the node features, apart from the network topology. In other words, the same network topology may appear in both homophily and heterophily datasets. [This might not be true in practice: one might imagine that heterophily datasets might likely contain bi-partite or multi-partite structures than homophily datasets.]

 - From a theoretical point of view, GPR as used in the paper does not really provide a trade-off between node features and graph topology. As a "polynomial graph filter", the parameters {\gamma_k} simply "modulate" the eigenvalues. In particular, if  {\gamma_k} (as an infinite sequence) is convergent,  the series \sum_k \gamma_k --> \gamma, then \sum_k \gamma_k A^k --> (\gamma)(I-A)^{-1}  (assuming A is normalized, the dominant eigenvalue is less 1), A^kH^{(k)} would converge to the eigenvector  (a normalized node degree vector) associated with the dominant eigenvalue, thus independent of the initial vector H^{(0)} that derives from the node features {X_i}.

 - Of course, the paper uses a fixed K power iteration (instead of letting K goes infinity). The issue of oversmoothing comes from when K is large, the "dominant" eigenvector takes over the "graph structure". I am not convinced that GPR helps either address the heterophily or the oversmoothing issues of GNNs. The use of GPR is motivated by the reference [Li et al 2019] "Optimizing Generalized PageRnak Methods for Seed-Expanision Community Detection". However,in [Li et al] GPR is used for community detection, where "homophily" is actually assumed. Note that stochastic block models (SBMs)  are fundamentally graphs with "homopily"  where nodes are likely to connected with nodes within the same community. 

 - All in all, GPR is yet another way to compute some "centrality" or ranking among the nodes. It does not fundamentally capture the structural (local or global) properties of graphs. There are other (perhaps "better" metrics, see, e.g., the paper "Hunt For The Unique, Stable, Sparse And Fast Feature Learning On Graphs" (NeurISP 2017), which is used to develop a Graph Capsule GNN. Unfortunately, some of these metrics are more computationally expensive to compute for large graphs.

Other comments:
 - As an aside, one can in fact absorb the parameter \gamma_k as part of the weight vector $W^{(k)}$ to be learned during the  kth-layer of the GNN. I believe that this might be the advantage gained by GPR-GNN, where in many existing GNNs the weight vector $W{(k)}$ is re-used (i.e., the same weight vector is often used in different layers). In GPR-GNN, the learned weight vector is rescaled by \gamma_k. 

- The theoretical results in Section 4 in terms of "graph filters"  are largely well known, see, the survey paper by Michael M. Bronstein et al, "Geometric deep learning: going beyond Euclidean data." IEEE Signal Processing Magazine, 2017.

- I am curious about the specific GNNs that you used to compare with your method, besides Geom-GNNs. There are many other GNNs, e.g., GIN, SAGE that are not chosen for comparison. 

review_title: An attempt to incorporate Generalized PageRank into GNNs to cope with heterophily and oversmoothing

final_score: rating: 7: Good paper, accept
review_content: The paper proposes a new GNN architecture based on Generalized PageRank to handle two weakness in some existing GNNs: the difficulty of neighborhood aggregation on heterophilic graphs, and the oversmoothing problem when stacking GNN layers. The proposed GPR-GNN can be viewed as an extension of the Personalized PageRank-based GNNs, such as APPNP and SGC, which also aimed to handle oversmoothing problem. Pros:  The paper highlights and clearly explains why optimizing the proposed layerwise GPR weights in GNN could tackle the two challenges. Although the final GPR-GNN architecture is simple, the ideas behind are significant. The paper is technically sound. The paper clearly analyzes the differences and relationships between related prior works and the proposed approach. In experiment, datasets are sufficient, including both homophilic and heterophilic graphs (both synthetic datasets and 10 real benchmarks are sufficient) which proves that GPR-GNN can achieve state-of-the-art performances especially on heterophilic graphs.
Cons:
* Baselines: The paper compares GPR-GNN with the state-of-the-art APPNP, a Personalized PageRank-based GNN. However, it also mentions SGC as another most related work based on PPR, but does not use it as a baseline. 
* Since the GPR-GNN only have one set of NN parameter \theta in the first layer, and other layers do not have such feature transformation parameters, maybe add more efficiency analysis would be better, since APPNP also has efficiency analysis.
* There are five heterophilic benchmarks. The performances of GPR-GNN on Chameleon and Squirrel are impressive, but GPR-GNN actually does not "significantly outperform" APPNP on Actor, Texas and Cornell datasets, which contradicts the claims. More discussions about this would be better. If it is due to other statistic differences between heterophilic benchmarks, it is necessary to mention them in Table 1.
review_title: The paper combines GNN with Generalized PageRank to handle two significant weakness of most GNNs, but lack of some important baselines and discussions

final_score: rating: 9: Top 15% of accepted papers, strong accept
review_content: 
The paper proposes a new neural net architecture based partially on the previously proposed Generalized
PageRank (GPR). The model adaptively learns the GPR weights so as to jointly optimize node feature and topological information extraction. The main advantage of  this approach is that -- unlike previously proposed GCNs -- this approach works well for both homophilic and heterophilic graphs (due to the use of GPR). This allows for e.g. node classification without a priori knowledge about the type of graph at hand. Additionally, this approach avoids feature over-smoothing, a known problem in GCNs. 

############

I recommend this paper for acceptance due to its novelty and its algorithmic contribution. I really enjoyed reading it. 

############

Pros
+ A very interesting approach with useful practical implications for a node classification of both both homophilic and heterophilic graphs. 
+ Very clearly written and well articulated. 
+ Great literature review of related topics in the area of GCNs. 

############

Cons/Suggestions 
- I found the explanation of GPR in the beginning of Sec 3 a bit confusing. Please rewrite to add a bit more detail (e.g. what is gamma?), I had to consult the original  paper to understand the notation here. 
 

review_title: Great paper, enjoyed reading it

final_score: rating: 6: Marginally above acceptance threshold
review_content: In this paper, the authors proposed a generalized pagerank version of a graph neural network (GNN). The authors learn a weighted combination of higher powers of the graph adjacency matrix, with the weights themselves being learnable. This allows their method to generalize existing GNN methods that work well when there's graph homophily, but not in the case of heterophily. The proposed method reduces to existing cases under certain weight settings, but in other cases, the learned weights allow for the GNN to act as a "high pass filter", which existing methods do not do. By learning these weights, the authors can also go deeper in the graph, and aggregate information from several hops away. Experiments on several standard datasets show that the proposed method outperforms multiple baselines. 

The paper is clearly written. My main concern is the overall novelty of the paper, with respect to ICLR. Unless I'm missing something, the main point the authors are making is to learn the weights of the decomposition, and show that by making those weights learnable, good things happen when compared to the methods in Klicpera et al, and Wu et al.  Just that to me is not grounds for strong acceptance. 

minor comments:
page 2: you keep using the term "large step propagation" several times, without actually defining what that means. 

Thm 4.1: is there a formal version of this theorem with a proof? if not it's probably not fair to call it a theorem. 

please make the text in figures 3 and 4 larger. It's hard to read. 

review_title: Official Blind Review #2

Meta-review: In this paper, the authors propose a new GNN architecture based on Generalized PageRank to handle two weaknesses in some existing GNNs. The novelty of this approach is that it works well for both homophilic and heterophilic graphs (due to the use of GPR).

Overall the paper is interesting and well written. Moreover,  the authors addressed the concerns of reviewers during the rebuttal period. Thus, I vote for acceptance.
Decision: Accept (Poster)