Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: The authors argue that second-order graph convolutions (SoGC) should be the building blocks for future graph networks. The argument is that some of the second-order functions cannot be represented by stacking first-order graph convolutions. In contrast, second-order can represent any higher-order ones. In general, the theory is sound and the results on the synthetic data and ZINC are strong and I don't see many flaws, but I would like to see more results on realistic datasets.

##### Strengths
- The method is quite simple.
- The results on the synthetic dataset and ZINC are quite impressive.
- The visualization in Figure 5 convinces me that SoGC can deal with the oversmoothing problem of vanilla GCNs.
- The theoretical insights and proofs look correct to me, while I am not 100% confident. 

##### Weaknesses
- MNIST and CIFAR 10 do not seem to be real use cases for Graph models. According to the [homepage of MNIST](http://yann.lecun.com/exdb/mnist/), none of the MNIST results in Table 2 is better than an SVM with degree 4 polynomial kernels, a 2-layer MLP with 800d, or a LeNet-1 which has only 3k parameters instead of 100k. It would be better to see results on more realistic datasets where graph networks are close to state-of-the-art.
review_title: Simple method, interesting observations

final_score: rating: 5: Marginally below acceptance threshold
review_content: The submission identifies the importance of second-order filter by showing that two is the minimally necessary order to achieve full representation power. Based on this observation, this paper proposes Second-Order Graph Convolutional Networks. The proposed method is evaluated on graph classification benchmarks and demonstrates good empirical performance. As far as I know, the proposed method is novel and can inspire future analysis on the expressive power of graph convolution. 

Strength:
- The proposed method, SoGC, is theoretically motivated by the fact that second order graph convolution has universal representation power (Thm. 1)
- The proposed method demonstrates strong empirical performance on synthetic and real-world datasets

Weakness and Questions:
- The usage of GRU feels ad-hoc to me. Without using GRU, the proposed method in fact does not achieve state-of-the-art performance on CIFAR10 and MNIST, which is concerning. I understand that the authors attempt to analyze the effect of GRU in Section 5.1. However, the claim that "GRU retains information from previous layers effectively ..." needs more supporting evidence than Figure 2, which is conducted on a single graph from a single dataset. I encourage the authors to provide more in-depth analysis of GRU and connects it to the rest of the paper. 
For more low-level questions: 
     - How is the input node order to the GRU decided? Will changing the input order affect results?
     - In Figure 2, is the number of parameters controlled? 
     - Would GRU also improves the performance of vanilla GCN? As Figure 2 showed, GRU also changes the signal of a vanilla GCN significantly.
- I would like to see an ablation study between the non-linear and linear versions of SoGCN. Given that in section 3 the analysis is only done for the linear version, I am curious about how well the linear model can perform. Also, the theory predicts that the linear Second Order GCN should outperform linear Vanilla GCN (this is like SGC?). I would like to see this prediction gets tested.
- As the authors acknowledge in the introduction, Abu-El-Haija et al. (2019), MixHop, makes similar observations about higher-order GCN. I am curious about how these two models compare to each other performance-wise.
- Minor note: The submission only evaluates the proposed method on graph classification task. Will the proposed method works for node classification or link prediction? Even if it doesn't, the authors should document the limitations of this method if it doesn't work for those tasks. 

Typos:
- Page 1, the second to last paragraph: "in channel-wise filtering Furthermore" -> missing period
- Page 6, "we can whiteness the ineffectiveness" -> "witness"

review_title:  Second-Order Graph Convolutional Networks

final_score: rating: 5: Marginally below acceptance threshold
review_content: This is yet another paper on graph convolutional networks (GCNs). The investigated SoGCN is a second-order GCN, thus a special case of high-order GCNs (namely with multi-hop graph kernels), which have has been proposed earlier by many researchers, such as by Defferrard et al. (2016), by Kipf & Welling (2017) and by Abu-El-Haija et al. (2019). 

The main interest is that a second-order GC is a universal approximator, because any univariate polynomial can be factorized into sub-polynomials of degree two, which is not the case of first-order GCs. 

The paper has some theoretical derivations that seem interesting. However, the proposed second-order GC is a special case of well-studied frameworks, which have been widely studied in the literature, such as with the expressive power analysis. As a consequence, the derived theoretical results seem less relevant. 

In conducted experiments, the authors do not consider the same comparative analysis in all experiments. For example, two versions of the nonlinear activation are considered in experiments on CIFAR10 (with and without GRU); however, they were not considered in other experiments. Moreover, it is not clear where the combined RELU and GRU is considered.
review_title: This is yet another paper on graph convolutional networks, considering a special case of high-order kernels.

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes a so-called second-order graph convolution, where an additional second-order term is introduced into traditional first-order graph convolution. The authors explain the merits of second-order graph convolution from the perspective of representation ability. The resulted second-order graph convolutional networks are compared with several graph convolutional networks on three benchmarks. 

Strengths:
+: Incorporation of second-order information into graph convolution seems interesting, and such analogous idea has been verified in 2D convolutions.

+: The proposed method is simple and easy to implement.

Weaknesses:
-: The idea on incorporation of second-order or higher-order information into convolution is not novel. For example, Factorized Bilinear (FB) [r1] and Second-Order Response Transform (SORT) [r2] introduce second-order terms into traditional 2D convolutions, and they also claim second-order terms have better representation ability. Besides, second-order or higher-order information have also been used for global pooling for convolution networks [r3, r4, r5], which also show better representation ability. This paper lacks discussions on above these works, which will bring a side effect on contributions of this paper.
[r1] Factorized bilinear models for image recognition, ICCV 2017.
[r2] SORT: Second-order response transform for visual recognition, ICCV 2017.
[r3] Second-Order Pooling for Graph Neural Networks, arXiv, 2020.
[r4] Deep CNNs Meet Global Covariance Pooling: Better Representation and Generalization, TPAMI 2020.
[r5] Kernel pooling for convolutional neural networks, CVPR, 2020.

-: The experimental results are not very convincing.
(1) As shown in Table 2, pure soGCN achieves no improvement over compared methods, i.e., GatedGCN. GRU brings further gains for soGCN, but could GRU bring improvement for other compared methods?
(2) Number of parameters hardly represents model complexity totally. The model with the same number of parameters can have different computational complexity. Therefore, more metrics on model complexity (e.g., FLOPs) are suggested for comparison in Table 2.
(3) CIFAR10 and MNIST are too small and old to verify the effectiveness of different methods. The authors would better conduct experiments on more graph benchmarks. Besides, why higher-order  GCN are not compared on real-world benchmarks.
(4) Why parameters number of 3WLGNN is 100K on ZINC ?

-: The writing needs significant improvement.
(1) The authors would better give more detailed descriptions on differences between the proposed soGCN and related works ([Defferrard, 2016] and [Kipf&Welling, 2017]), further clarifying the contributions of the proposed method.
(2) I wonder the detailed computation methods and each curve in Fig.2, and why SoGCN is better than Vanilla GCN?
(3) The comparisons in terms of representation ability in section 4.3 is not very clear. The authors would better add a table to summarize representation ability of different graph convolution.
(4) Which method does MoNet indicate in Table 2 ?


review_title: Review for SoGCN: Second-Order Graph Convolutional Networks

Meta-review: Four reviewers have reviewed this paper. After rebuttal, the reviewers' recommendations were borderline. Rev. 4 remains concerned about relation of second-order approaches in CV and second-order filters. Indeed, there exists a connection although it is perhaps subtle in its nature and equally concerning is the connection with general Polynomial filters in many GCN papers. As other reviewers point out, MixHop and Jumping Knowledge also allow multi-hop designs. More importantly, APPNP and SGC networks allow multiple hops. From that point of view, the proposed approach is rather a recap of existing observations and contributions. Finally, even Rev. 2 has indicated that the paper is perhaps 'average' after checking with comments of other reviewers. Therefore, at this point, the paper is slightly below the acceptance threshold.

Decision: Reject