Venue: ICLR 2021 Conference

Reviews:

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

Summary:

This work proposes the Polynomial Graph Convolutional Networks (PGCNs), which is built upon the Polynomial Graph Convolution (PGC). The PGC is able to aggregate k-hop information in a single layer and comes with the hyper-parameter k. The PGCNs are composed of a PGC with k=1, followed by a PGC with a chosen k (usually > 1), and a complex readout layer using avg, max, and sum over all nodes. Theoretically, the proposed PGC has two major benefits as claimed: 1) Common graph convolution operators can be represented as special cases of the PGC; 2) A PGC with k = q (q > 1) is more expressive than linearly stacked q PGCs with k=1. The PGCNs are thus more general, expressive, and efficient than existing GNNs. Experimental studies are conducted on common graph classification benchmarks, showing the improved performances of the PGCNs.

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

Reasons for score:

Overall, I vote for rejection. My major concerns lie in three aspects, as detailed in Cons below: 1) Some statements to motivate this work are not well explained and supported. 2) The proposed idea seems quite similar to several previous studies; 3) The experimental studies are not convincing to me in order to show the effectiveness of the proposed PGC.

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

Pros:

1. The presentation is good and the proposed method is clearly described. I like the theoretical analysis in 3.2, which explains clearly how to build PGCNs with PGC.

2. This paper targets at two interesting problems in the literature: 1) designing more powerful graph convolution operator; 2) building GNNs with similar power as deeper GNNs. The deeper version of existing GNNs is usually not powerful as expected. As a result, building GNNs to achieve the expected power is an important topic.

3. The experimental details are provided in the appendix.

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

Cons:

1. Some statements to motivate this work are not well explained and supported. In particular, in the abstract and section 1, the authors indicate that interactions among non-linearly stacked graph convolution (GC) parameters at different levels pose a bias on the flow of topological information. This statement is not well explained and supported with analysis or experimental results.

2. The proposed idea seems quite similar to several previous studies. The proposed PGC is quite similar (or equivalent, with minor differences) to concatenating outputs of linearly stacked GCs and then going through a linear transformation. First, such concatenation is proposed in [1]. Second, linearly stacking GCs, or equivalently using a polynomial powers of the adjacency matrix A (possibly with some transformations), is studies in multiple studies like [2,3,4]. I didn't capture the key differences between this work and these previous studies. Only [2] is discussed in the appendix. [4] is mentioned in the experiments, but no discussion in terms of method differences is provided.

[1] Xu et al. "Representation Learning on Graphs with Jumping Knowledge Networks", ICML 2018

[2] Wu et al. "Simplifying Graph Convolutional Networks", ICML 2019

[3] Liu et al. "Towards Deeper Graph Neural Networks", KDD 2020

[4] Chen et al. "Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classification", ICLR 2019 RLGM workshop

3. The experimental studies are not convincing to me in order to show the effectiveness of the proposed PGC. As mentioned in Summary, the PGCNs use a quite complex readout layer, which is different from all the GNNs in comparison. Ablation studies on this readout layer should be provided in order to show that the improvement is indeed from the PGC.

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

Questions during rebuttal period: 

Please address and clarify the cons above 


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

Comments after the rebuttal period: 

I will keep my score. The authors' responses addresses my first concern. However, the differences from previous studies are still not significant to me. In addition, no matter the authors claim the proposal of a complete architecture or a new operator, ablation studies are necessary to backup the designing of each part.

review_title: Recommendation to Reject

final_score: rating: 5: Marginally below acceptance threshold
review_content: The article presents a novel framework for Graph Convolutional Neural Networks (GCNs). The method called  Polynomial Graph Convolution (PGC) is based on concatenating the powers of a transformed adjacent matrix in a given layer. The paper shows that various popular variants of GNNs can be expressed using the PGC framework.  Theoretical results presented show that PGC with higher degree is more expressive that deeper std. GNNs. Numerical results are presented on graph classification task that illustrate the performance of the method.

--------------
Strengths:
1. Paper presents a novel framework.
2. Numerical results look promising.
3. The method presents a more expressive method.

--------------
Weakness:
1. Novelty seems limited.
2. Node and edge task experiments are missing.
3. Certain claims need to be substantiated.

--------------
Details:
I have the following comments:
1. Novelty seems limited. It is unclear how the proposed method/framework is different from the Krylov subspace based work of (Luan et al. 2019) and also the Chebyshev polynomials approach of (Defferrard et al., 2016). Both these methods boil down to considering powers (polynomials) of the Laplacian, i.e., different topological distances in the model. Authors should clarify the key differences.

2. Experimental results section can be enhanced. Currently, the paper  considers only the graph classification task, where only global information suffices. GCN are more interesting in local, graph level tasks, in particular for prediction tasks on nodes and edges, e.g., link prediction, node and edge classification. It is unclear why these tasks were not considered. Moreover, methods of  (Kipf and Welling, 2016), (Luan et al. 2019) and (Defferrard et al., 2016), that are most relevant to this work are not considered for experimental comparisons.

3. The claim in Theorem 2, that PGC with k =2 is more expressive than two stacked PGC with k = 1, is du to that fact that the former has number of parameters higher than the latter. Is this correct? (Due to the structure of weight matrix W)

4.  There are few statements that need to be substantiated and explained. E.g.,
(a) It is claimed there is a bias in deeper GCNs, but no explanation is given.
(b) Similarly, PGC being more expressive (for the asme number of parameters) needs to be explained.
review_title: Interesting work, certain details missing

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary: The paper proposes Polynomial Graph Convolution (PGC), which enjoys a larger-than-one-hop receptive field within a single layer. This is done by first propagating information with a fixed (not learned) propagation matrix (e.g. adjacency matrix or graph Laplacian), and then projecting the information from different topological distances with a learned linear layer. PGC is shown to be theoretically more expressive than linearly stacking simple graph convolutions; experiments on several graph classification tasks show good performance.

Recommendation: Overall, I am slightly leaning to reject. The paper is interesting, but the theoretical contribution is rather straight-forward, and to warrant acceptance I would look for strong empirical performance together with an analysis of what is contributing to the gains. While some of the gains PGCN obtains look promising, others do not seem statistically significant; some results and baselines from related works are not compared against, and the effect of a strong node aggregation scheme is not discussed. Finally, it is unclear if the proposed method can be generalized to use edge types.

Main pros:
1. The paper is clear and easy to understand; even relatively small claims are backed up by proofs.
2. The relationship between linearly stacking k GraphConvs and using a single k-PGC layer is cleanly explained and motivates the work well. Decoupling receptive field size from network depth is a natural goal.
3. I appreciate the authors taking care to fairly evaluate their PGCN following [1]. This is crucial as many GNN works are iterating on metrics computed on the evaluation set despite it being available to the model selection procedure; as noted by authors, this includes the GIN results from [2].

Main cons:
1. I have several concerns about the results (Table 1):
- Best mean performance is bolded, but many of the gains (esp. PTC, PROTEINS, IMDB-B, IMDB-M) seem within noise levels due to high variance. Instead of saying "PGCN shows a slight improvement", it would be better to perform a statistical significance test, and clearly mark which improvements are significant (by bolding several joint-top values).
- Many results are taken from [1], but simple baselines of [1] that do not consider graph structure are omitted. These baselines outperform all GNNs in [1] for some benchmarks, e.g. getting 78.4 for D&D and 65.2 for ENZYMES (which is between the results of the best baseline and PGCN); to get a full picture these baselines should be included.
- [1] also shows that adding simple node features can make a big difference for IMDB-B and IMDB-M; for example, adding node degree features improves GIN on IMDB-B from 66.8 to 71.2. While PGCN is not using node degree features, for IMDB it's using the Graph Laplacian as T(A) (Appendix H), which implicitly encodes some degree information. As [1] already has results with node degree features included, it would be nice to see how PGCN compares.
- PGCN uses a powerful node aggregation scheme (Page 6). What aggregation methods are used in the baselines? What is the contribution of using this stronger aggregation scheme instead of a more standard weighted sum?
2. Section 3.3 and Appendix E mention that PGCN can be more efficient to train than standard GNNs because the propagation (i.e. multiplying node features by powers of T(A)) can be computed once. This only applies to the very first PGCN layer, and as authors state, before using a non-trivial (k > 1) PGC layer, one would typically use either 1-PGC (as done in the paper) or a learned linear projection, in order to avoid propagating highly sparse raw node features. It's therefore unclear if this training speedup can be really obtained in practice without sacrificing accuracy; one could use a random (not learned) linear projection as the initial "densification", but it's hard to say if that would work. Either way, if this speedup can really be obtained, it would be good to see supporting results (preferably on a large dataset where training time is indeed an issue).
3. Can PGC take edge types into account? I understand some of the benchmark datasets contain molecules, and thus have typed edges (single, double, triple); was that information utilized by PGCN? Considering edge types is straight-forward for GNNs that only perform a single learned propagation step, since the propagation matrix can be selected based on the edge type; it's unclear what to do for PGC which uses a fixed propagation matrix.

Other comments:
- The abstract and introduction say "interactions among GC parameters at different levels pose a bias on the flow of topological information". I'm assuming this refers to entanglement of weights as in Equation 8, but when reading the intro this got me confused, since there was no reference, and the claim did not seem obvious.
- Propagation in PGCN does not use any non-linearity or normalization, so it seems values can grow exponentially with k, especially on dense graphs. Was this observed to be a problem?
- "GraphConv is more expressive than GCN and GIN" - this is not fully true, since GCN as defined in the paper uses the Laplacian instead of the adjacency matrix.
- The analysis shows the relation between PGC and linearly stacking GraphConv's, but in practice one wouldn't linearly stack them, and rather use non-linearities in between. Can anything be said in that case?
- "they (...) consider shortest paths, (...) that choice limits significantly the expressiveness" - I'm not fully convinced: PGC cannot be stronger than the WL test, while using shortest path information allows to exceed that (since it makes it possible to tell apart two disconnected cycles from a single larger cycle).
- The paper compares only against GraphConv-like layers; it would be interesting to compare (empirically) to a larger class of GNNs, such as GAT [3], GGNN [4] or GNN-FiLM [5].

Typos and small formatting issues (did not influence my rating recommendation):
- Page 1: "faces the problem" -> "addresses the problem"
- Page 1: "being able to" -> "by being able to"
- Page 3: "start showing" -> "start by showing"
- Page 6: In equation for y_j, I believe j should start with 1
- Pages 6 & 14: "PCG" -> "PGC"


References:
- [1] A Fair Comparison of Graph Neural Networks for Graph Classification
- [2] How Powerful are Graph Neural Networks?
- [3] Graph Attention Networks
- [4] Gated Graph Sequence Neural Networks
- [5] GNN-FiLM: Graph Neural Networks with Feature-wise Linear Modulation

----------------------------------------------------------------------------------------------------

Comments after rebuttal:

I have reviewed the response from the authors, and I decided to keep my score. Although the paper is certainly interesting, for ICLR it is borderline. While I agree that many works in the literature choose to treat their network as a monolithic architecture, and thus do not explore the effects of different components, I would still encourage the authors to add an ablation of the readout method, as that would help assess the interaction between that and the choice of the graph propagation scheme.
review_title: Official Blind Review #4

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper analyzes the current graph convolution and proposes a novel polynomial graph convolutional network (PGCN). Under the framework of PGCN, several other graph convolutions can be seen as a special case.

Quality:
The paper is technically sound and maintains a high presentation quality. 

Clarity:
The mathematical proof is clear and the whole paper is easy to follow.

Originality:
The paper is somewhat original but the proposed PGCN still lacks generalization, which will be pointed out in the following part.

Significance:
The significance is not very prominent.


Pros: 
1. The paper proposes a novel graph convolution named with PGCN. Under the framework of PGCN, several other graph convolutions can be regarded as a special case. 
2. The whole paper is described clearly and easy to follow.


Cons:
1. The core idea of PGCN mainly relies on the exponential power of different order applying on adjacent matrix A. It is easy to prove that by exponentiating the adjacency matrix to the K-th power, the node's receptive field can be extended to the K-th nearest neighboring nodes. However, this approach has been successfully adopted in different articles, as a result, the proposed PGCN is of limited originality without further analysis, either in theoretical aspect or technical aspect.
2. The mathematical proof in section 3.1 and section 3.2 shows that the stronger expressive ability comes from the less constraints of learnable parameters W. However, reducing the constraints may lead to the training process  more difficult than other graph convolution. To dispel this concern, the author needs to provide more detailed experimental results, especially the training convergence curves of different graph convolutions.
3. In terms of efficiency, the K-th order exponential method in equation (1) can improve the nodes' receptive field but brings heavy computational burden. In Table 3, All the evaluated dataset has a limited number of nodes in each graph. The maximum average number is 284.32 while the minimum average number is 13.00. The generalization of PGCN on large scale graph remains a serious concern. In Appendix E, the author has also noticed the computing efficiency and adopted a pre-computing strategy, which means the proposed PGCN is not an out-of-box model. In a word, although the proposed model shows stronger expression ability, the generalization and efficiency still remains a big concern.
review_title: Owning more expressive ability but still lacking generalization

Meta-review: All four reviewers expressed significant concerns on this submission during review. None of them is willing to change their evaluations and supports this work during discussions. Thus a reject is recommended.
Decision: Reject