Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: **Post-discussion update:**

I would like to thank the authors for addressing (albeit partially) my comments, as well as the comments from other reviewers. While I understand that some connections can be made between the proposed approach and other approaches or aspects that go beyond local smoothing or oversmoothing, this is somewhat anecdotal in my opinion. More generally, it is still not entirely clear to me how significant are the contributions here. Reading the other reviews, it seems these concerns are also shared by other reviewers, although I still think the analysis here is not without merit and this warrants it at least a borderline score. Further, there are some interesting insights provided here, which place this work slightly over the threshold. Since marginally above the threshold was already the score I gave the manuscript initially, it remains unchanged.

---

**Original review:** 

This work provides a formal interpretation of the aggregation step in common GNN architectures as aiming to solve (at least partially) a graph denoising problem formulated via graph Laplacian smoothing. In particular, it provides a unified formulation of GCN, GAT, PPNP and APPNP in these terms. Further, the authors use this understanding to formulate a unified GNN architecture, which can be instantiated to these particular ones, and then leverage this architecture to provide an improved adaptive one that is demonstrated to have some advantages over the mentioned classic GNNs.

The main insight showing that traditional GNN architectures essentially smooth or denoise node features is not surprising, and one might argue not quite novel, since this has been discussed and demonstrated in several previous work (some important ones already acknowledged and cited here). However, the unified view provided here does seem insightful and can contribute to more methodical view of their architecture design. Indeed, this is demonstrated by the introduction of ADA-UGNN here. Therefore, the paper does have merit that progresses the theory behind graph neural networks.

On the other hand, it is not clear how much insight can be drawn from the presented theory, or what impact this analysis might have. As said before, it is generally well accepted and understood that the four architectures discussed here rely on local smoothing, and are susceptible (to some degree) to oversmoothing in node classification. There is little discussion of numerous attempts in recent years to overcome this issue and provide architectures that aim to go beyond smoothing (e.g., MixHop, graph scattering, or various architectures with residual layers or skip connections come to mind). It seems the proposed approach here would still rely on local smoothing, and therefore it is not entirely clear if it will really contribute significantly compared to the current trends and state of the art in the field.

Therefore, I would consider this work as a borderline case, but I am leaning towards acceptance due to the contribution towards a more theoretically oriented (rather than algorithmic) unified formulation encompassing a plethora of architectures that fall under the local smoothing paradigm, while noting the paper would be more convincing if it also considered how to advance beyond this smoothing or denoising regime. 

Minor remarks:
- In section 5, the authors say "GAT unintentionally adopts an adaptive C" - I would argue this is rather deliberate and not unintentional.
- The use of *author (year)* and *(author, year)* citation styles (citet and citep natbib commands) seems somewhat inconsistent, and does not follow the recommended guidelines of when to utilize each style.

review_title: Nice insights, but unclear novelty and impact

final_score: rating: 3: Clear rejection
review_content: SUMMARY:
This paper establishes a relation between different popular graph neural networks by mathematically proving that the feature aggregation operation of such networks can be understood as a graph-signal-denoising step. Moreover, the authors try to establish a general framework based on graph signal denoising that subsumes the studied architectures, developing new graph neural network (GNN) architecture under this framework.

STRONG POINTS:
Showing that different architectures are indeed using a similar approach for the feature aggregation which is closely related to graph signal denoising is an interesting idea which helps to gain insight into how these architectures work. Furthermore, the numerical results illustrate that the proposed architecture has a competitive performance under certain settings.

WEAK POINTS:
The mathematical notation of the paper is sometimes ambiguous and unclear, so it should be carefully revised.

The relation between GAT and the graph signal denoising approach is not clear and should be detailed, since it is one of the main contributions of the paper.

While proposing a unified GNN framework based on graph signal denoising is stated as one of the main contributions of the paper, it amounts to presenting the graph denoising formulation with an arbitrary regularization function. The paper should focus more on the relation between the proposed architecture and the different “GNN with graph signal denoising schemes”. 
The paper would benefit if the proofs of Theorems 1-4 were included in the main body, rather than in the appendix. 
The reason is twofold. Those proofs are likely to constitute the main contribution of the paper. Furthermore, the statement of the theorems (without the proofs) is not sufficient to fully illustrate the relation with graph signal denoising.

The proposed ADA-UGNN network should be further analyzed. An MLP is chosen as the feature aggregation function without providing a motivation. Furthermore, the impact of C being learned instead of being a hyperparameter (Theorems 5 and 6) should be discussed in more detailed, since it implies that convexity of (14) is lost.

ADDITIONAL COMMENTS:

The symbol L is ambiguously used to denote different types of Laplacian matrices.
In Section 2 says that each node is associated with a d-dimensional signal X of size N times d, but the signal associated with a node should be a vector, not a matrix.

Equation (4) is not mathematically correct. The variables used as indexes of the summation are not present in the terms inside the summation. In fact, notation for the indexes of the summations throughout the entire manuscript is quite confusing (and in cases like (4) definitely incorrect). 

The edge-centric interpretation of the Laplacian regularization is never used. Also, both the edge-centric and node-centric formulations are not correct since they are missing the related term of the adjacency matrix A_ij. If A is binary, this should be stated clearly. 

Two different notations for the gradient descent algorithms are used in the paper (see, e.g., equations (21) and (24) vs. (25) and (30)). This should be unified.

In eq (15), please clarify what d_i and d_j represent.

review_title: Worth pursing idea but needs more work

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary of the paper: In this paper, the authors make the following new argument: The aggregation processes of current popular GNN models such as GCN, GAT, PPNP, and APPNP can be treated as a graph denoising problem where the objective is to minimize a recovery error (a norm of noisy feature matrix, i.e. ||F-X||) plus a graph-based regularization (smoothness). This new view provides a way to build a GNN model, namely (Ada-)UGNN. Experimental results show the effectiveness of Ada-UGNN on the task of node classification and the task of preventing adversarial attacks on graphs.

Strong points: 1) Theoretical contributions of the proposed framework are solid and interesting. These findings show that two basic operations of a GNN layer, feature transformation and feature aggregation can be viewed as a gradient descent step of minimizing a graph denoising function. 2) Experimental results demonstrate the effectiveness of Ada-UGNN.

Weak points: 1) I think one weakness of this paper is that: Explanations are only focused on one layer (local). The theorems do not explain the relations between layers and how nonlinear activation functions affect these theoretical findings. For example, [1] and [2] treat the GNN as a procedure of encoding and decoding as a whole. However, it seems that the objective of GNN cannot be viewed as a simple combination of graph denoising problems. 2) The experiments do not explain well of theoretical findings: these connections are missing in experiments. I do see results of Ada-UGNN are promising on node classification and the task of preventing adversarial attacks. However, it would be better if there are some empirical evidence to explain these new theorems.

Recommendation: Based on the above points, I tend to marginally accept this paper but have concerns (these weak points). 

Questions & other comments:
“The improvements of the proposed model compared with APPNP are marginal”, as shown in Table 1. Are these really improvements? Based on my understanding, these means of Ada-UGNN are higher than APPNP, but the variance is also high. Significance test is needed.
In Ada-UGNN, it approximately solves problem 2 and uses a special regularization term. How does the approximation affect the final performance? Is there any clear guidance on how to choose the regularization term in different problems? Are these regularizations problem-dependent?

[1] Hamilton, William L., Rex Ying, and Jure Leskovec. "Representation learning on graphs: Methods and applications." arXiv preprint arXiv:1709.05584 (2017).
[2] Chami, I., Abu-El-Haija, S., Perozzi, B., Ré, C., & Murphy, K. (2020). Machine Learning on Graphs: A Model and Comprehensive Taxonomy. arXiv preprint arXiv:2005.03675.

review_title: A Unified View on Graph Neural Networks as Graph Signal Denoising

final_score: rating: 3: Clear rejection
review_content: 1). The novelty and contribution are very limited. In literature, many papers have discussed the connection between different GNNs, typically, including aggregators and Updaters, such as discussed in “Deep Learning on Graphs: A Survey”. The submission only provides a kind of connection between GCN, GAT, PPPN and APPNP in the perspective of denoising. Compared with that, the survey paper actually connects many different GNNs. 


2). The writing quality is low. There are many errors, for example, in section 3, “the unnormalized version of Laplacian matrix with L−D−A”==> “the unnormalized version of Laplacian matrix with L=D−A”?


3). In Eq. (1) to ease the discussion, the non-linear activation is not included. However, the nonlinearity is the key part for deep GNNs. In Formula (8), the GNNS AS GRAPH SIGNAL DENOISING actually oversimplified the topological smoothing over attributes, since the nonlinear transformation, especially with dropout will already conduct the signal denoting. So why use such additional effects to do that?

4). The submission provides both Node classification task and ADVERSARIAL defense task to validate the performance. As for Node classification, the results however are not very promising compared with current SOTA. For example, in ICLR’20 paper “ADAPTIVE STRUCTURAL FINGERPRINTS FOR GRAPH ATTENTION NETWORKS”, the cora dataset reports “85.4±0.3%” compared with that reported by this submission only “84.59±0.8”; in cite seer “74.0±0.4%” compared with this submission’s report “72.05±0.5”. In Pubmed, this paper reports “79.70±0.4”, however, in the ICLR paper, they report “81.2±0.3%”. From that perspective, I did not see any advantage in the submission.

5). As another task for validation, that is robustness to ADVERSARIAL attack. It is suggest to compare the recent SOTA “Graph Information Bottleneck” by Jure stanford in NeurIPS’20.

review_title: The submission claimed to provide an connection between GCN,GAT,PPPN and APPNP using a denoising perspective. However, the contribution is limited and the results are not sufficiently strong.

final_score: rating: 7: Good paper, accept
review_content: The paper attempts to provide a unified picture of a number of different GNN architectures from the point of view of graph signal processing (GSP).
In particular, it is argued that the aggregation operation in a number of important architectures can effectively be seen as a form of (graph) signal denoising.

Pros:
* Consolidates a number of (a priori) unrelated GNN architectures and unifies them from the point of view of GSP.
* The unified picture can be used for systematic comparison of architectures or for the design of new architectures, as the authors show.

Cons:
* It appears that despite the theoretical insights are nice for unifying the representation, but do not quite lead to a more improved GNN architecture in terms of numerical performance.
* The paper concentrates only on the aggregation step, but in the architectures considered there are also different non-linearities -- this part is completely neglected.

More detailed comments.

Overall I very much appreciate the work towards simplifying and unifying the somewhat disconnected literature -- this is an good contribution, I think.
While some of the transformations the authors propose to make the architectures align with the GSP picture feel a bit contrived, I think that is ok, given the simplification gained.
What I am missing somewhat was a discussion in how far knowing this representation can actually theoretically lead to improvements. For instance it is known that GNNs cannot be more expressive that the weisfeiler-leman test (see Morris et al) --- does the GSP lens provide any alternative perspective on this? This would be very interesting theoretically I think.

My second suggestion for possible improvements would be to provide a somewhat more detailed discussion on the effects of the non-linearity in such networks for the classification results. 
Unifying the aggregation layer is useful, but at the end the improvements that these insights bring (in terms of UGNN) seem to somewhat small.

Overall I see the strongest contribution here in terms of the theoretical unification provided.

Minor comment:
The Laplacian is invariant to the addition of self loops, i.e., \hat{D} - \hat{A} = D-A, as the addition of a self loop on the diagonal of A will be cancelled by the corresponding change in D.
(cf. top of page 4)

review_title: A Unified View on Graph Neural Networks as Graph Signal Denoising 

Meta-review: The paper argues that GNNs can be understood as a graph signal denoising. While this interpretation is not surprising and not novel, the unified view does seem insightful according to some reviewers. Yet, it is not clear how much insight can be drawn from the presented theory, as no significantly better architecture or experimental results are presented. 

Additional criticism was raised wrt unclear relation between GAT and the graph signal denoising, the fact that analysis focused on one layer and does not explain the relations between layers and how nonlinear activation functions affect these theoretical findings, and that the objective of GNN cannot be viewed as a simple combination of graph denoising problems. Several reviewers complained that the paper is hard to follow. 

In light of the above, despite the significant efforts of the authors to address these issues in the rebuttal, we believe the paper is below the bar and recommend Rejection. 
Decision: Reject