Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper unifies several variants of the graph convolutional networks (GCNs) into a regularized quadratic optimization framework. Basically, the function to be optimized considers both to preserve node information and to perform graph Laplacian regularization, whose optimal solution gives a convolutional layer.

The unification is given by equations (3) and (18) and elaborated in section 3, which includes several methods including GCN, graph attentions, residual connections, concatenation, etc. This is not surprising: as a GCN layer (without activation) is a linear transformation, surely it is the optimum of a quadratic function. Broadly, any linear layer can be trivially formulated as a quadratic optimization problem. Still, I appreciate the authors' delicate work on unifying these diverse methods from an optimization perspective, which is useful and could lead to new methods.

From a technical perspective, the main novelty is that the authors further extend this framework by adding another feature variance term, so that the learned features have a certain variance. This is similar to the idea of batch normalization. This is reasonable because GCN tends to correlate the learned features with the graph Laplacian embedding (the optimal solution of the 2nd term in the authors' framework).

This is interesting but empirical. I would like to see how this additional regularization can be equivalent to transforming the original graph with some formal arguments. Unfortunately, this technic is mainly introduced as a heuristic and more detailed analysis is missing.

As in any regularization framework, there is an additional parameter involved that is the regularization strength (\alpha_3 in 21). Therefore the performance improvement is not surprising as the model is "enlarged". In the experiments or supplementary material, there should be a sensitivity study of this parameter.

On three citation graphs (that are commonly used to evaluate graph neural networks) and semi-supervised node classification tasks, the authors showed that the regularizer can bring marginal performance improvement.

Regarding Clarity, there are some typos in several places and rarely used phrases.

Overall, I don't feel excited after reading the article (although the contents are useful), as a large part of this work is on summarizing existing literature.  The "new bit" is mainly on the additional regularization term that is introduced as a heuristic.

Based on the novelty, a more proper venue for publishing this work could be relevant journals. Overall this submission presents a borderline case and I recommend weak acceptance.

As a minor comment: Equation (21) why not set \alpha_1=1?

----
After rebuttal:

Novelty: my assessment remains the same. It is not non-trivial enough to combine several linear operators into a unified optimization framework. Although the unification is useful, it is not a major novelty.

Thank you for the additional experiments on testing the hyper-parameter. As you mentioned instability, it is worth to have some toy example to demonstrate the instability and study the cause of such instability and show how to avoid such instability using the proposed regularizer. Clearly (19) is bounded. When \alpha_3 is large enough, the solution will be trivial.

Regarding non-linearity: the authors' framework is for unifying a graph convolution operator (that is one layer in a graph neural network). Nonlinear activation is another operator. This is not a major problem from my perspective.

Overall, I think this work has some value (although the novelty is not strong) and still recommend weak acceptance.
review_title: Graph Convolution in a Unified Quandratic Optimization

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper presents a unified framework for graph convolutional neural networks based on regularized optimization, connecting different  variants of graph neural networks including vanilla, attention-based, and topology-based approaches. The authors also propose  a novel regularization technique to approach the oversmoothing problem in graph convolution. Experiments on the standard settings of node classification on Citeseer, Cora, and Pubmed prove the effectiveness of the proposed regularization techniques. 

Overall, this is a very interesting paper, proposing a unified framework for different variants of convolution-based graph neural networks. However, I also have a few concerns:

(1) The proposed framework is mainly designed for GNNs without considering the nonlinear transformation matrix. What if we have to consider the nonlinear transformation? Is the whole framework able to unify different GNNs?

(2) In the case of linear GNNs (without nonlinear transformation matrix), it is actually not surprising formulating GNNs as a regularized optimization problem. Such a regularization framework has already been discussed in the original GCN paper (Kipf et al. 2016). 

(3) In the case of linear GNNs, the overall framework is also very similar to the traditional label propagation framework (Zhou et al. Learning with Local and Global Consistency). Could you explain the difference?

(4) The new novel regularization technique seems to be similar to the one proposed in PairNorm (Zhao et al. 2020). Could you also explain the difference?

review_title: Interesting framework but it is not new

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary: The paper shows that several graph networks (GCN, attention GCN, PPNP, residual) can be unified under a common framework of Laplacian-regularised optimisation. Subsequently, different types of regularisation are combined to propose a new method for graph transduction, which is then empirically evaluated.

Significance: Laplacian regularisation is a classical approach for formulating/justifying graph transduction algorithms (multiple papers by Mikhail Belkin and Xiaojin Zhu around 2004-06). It is interesting to see that so many graph networks can also be unified in the same framework. A unified framework does aid in both theoretical analysis and implementation of GCNs.
However, the claims and derivation do not seem to account for the non-linear activation in the networks, and hence, significance of the work seems limited.

Quality: As noted above, non-linearity is not considered which makes the derivation significantly simpler. Moreover, the first-order approximation is quite misleading since even the proof do not seem to consider non-linear activation. 
Since the proposed method combines multiple types of regularisation, it is expected to perform better than other networks. However, it is not clear if the training time increases due to the complex regularisation.

Clarity and orginality: The paper is otherwise well written / organised, and the theoretical contributions (although technically straightforward) seem original and somewhat interesting.



review_title: GNN unified using old ideas of regularisation, but non-linearity not accounted

final_score: rating: 7: Good paper, accept
review_content: The paper introduces a unified framework for graph convolutional networks by interpreting filters as regularizers in the graph Fourier domain.
In particular, this framework allows to establish the relationships between standard, attention-based and topology-based GNNs.
Furthermore, the authors propose a regularization technique based upon the proposed framework which tackles the oversmoothing problem of GNNs, which achieves clear benefits on standard (small) benchmark datasets.

The paper is mostly well-written, although though to understand on first read.
I especially liked that it tries to establish a systematic view of different GNN models and their relations, which is a welcome work in the field of graph representation learning (especially with the sheer amount of GNN models available in literature).
In my opinion, the proposed framework has the potential to improve our understanding of GCNs and inspire better models in return.

On the other hand, it is not exactly clear to me how the proposed regularization technique differs from PairNorm (which is build upon similar insights by preventing node embeddings from becoming too similar). I would very much welcome a discussion between key differences and similarities between the two approaches. Furthermore, the authors should consider comparing the proposed regularization technique against related approaches, e.g., PairNorm and DropEdge.
Overall, the empirical evaluation feels a bit shallow by only evaluating on small benchmark datasets, but might be sufficient for a work that has mostly theoretical contributions.

Minor comments:

* It is not exactly clear to me how ECC can be viewed as an attention-based GNN since this operator learns a weight matrix conditioned on the edge features (instead of performing weighted normalization). Does this operator really fit into the proposed unified framework?

* A GCN baseline is missing on the PPI dataset.

============== Post Rebuttal Comments =================

I would like to thank the authors for their insightful rebuttal and clarifications. Sadly, I cannot find the newly added section regarding the non-linearity analysis in the revised manuscript and therefore cannot judge the findings of the authors.

Hence, my rating will stay the same.
review_title: Good work on establishing the relationship between different GNN models

Meta-review: Four reviewers have reviewed and discussed this submission. After rebuttal, two reviewers felt the paper is below acceptance threshold. Firstly, Rev. 1 and Rev. 2 were somewhat disappointed in the lack of analysis regarding non-linearities despite authors suggested this was resolved in the revised manuscript, e.g. Rev. 2 argued the paper without such an analysis is too similar to existing 'linear' models, e.g. APPNP, SGC, and so on. While Rev. 3 was mildly positive about the paper, they also noted that combining several linear operators is somewhat trivial. Overall, all reviewers felt there is some novelty in the proposed regularization term but also felt that contributions of the paper could have been stronger. While AC sympathizes with this submission and hopes that authors can improve this work, in its current form it appears marginally below the acceptance threshold.
Decision: Reject