A Unified View on Graph Neural Networks as Graph Signal Denoising
Authors: Yao Ma
Xiaorui Liu
Tong Zhao
Yozen Liu
Jiliang Tang
Neil Shah
Venue:  (2021)
Keywords: Graph Neural Networks
Graph Signal Denoising
Smoothness

Abstract: Graph Neural Networks (GNNs) have risen to prominence in learning representations for graph structured data. A single GNN layer typically consists of a feature transformation and a feature aggregation operation. The former normally uses feed-forward networks to transform features, while the latter aggregates the transformed features over the graph. Numerous recent works have proposed GNN models with different designs in the aggregation operation. In this work, we establish mathematically that the aggregation processes in a group of representative GNN models including GCN, GAT, PPNP, and APPNP can be regarded as (approximately) solving a graph denoising problem with a smoothness assumption. Such a unified view across GNNs not only provides a new perspective to understand a variety of aggregation operations but also enables us to develop a unified graph neural network framework UGNN. To demonstrate its promising potential, we instantiate a novel GNN model, ADA-UGNN, derived from UGNN, to handle graphs with adaptive smoothness across nodes. Comprehensive experiments show the effectiveness of ADA-UGNN. 

Under review as a conference paper at ICLR 2021
A UNIFIED VIEW ON GRAPH NEURAL NETWORKS AS GRAPH SIGNAL DENOISING
Anonymous authors Paper under double-blind review
ABSTRACT
Graph Neural Networks (GNNs) have risen to prominence in learning representa- tions for graph structured data. A single GNN layer typically consists of feature transformation and a feature aggregation operation. The former normally uses feed-forward networks transform features, while the latter aggregates the trans- formed features over the graph. Numerous recent works have proposed GNN models with different designs in the aggregation operation. In this work, we es- tablish mathematically that the aggregation processes in group of representative GNN models including GCN, GAT, PPNP, and APPNP can be regarded as (ap- proximately) solving a graph denoising problem with smoothness assumption. Such a unified view across GNNs not only provides new perspective to under- stand a variety of aggregation operations but also enables us to develop a unified graph neural network framework UGNN. To demonstrate its promising potential, we instantiate novel GNN model, ADA-UGNN, derived from UGNN, to handle graphs with adaptive smoothness across nodes. Comprehensive experiments show the effectiveness of ADA-UGNN.
INTRODUCTION
Graph Neural Networks (GNNs) have shown great capacity in learning representations for graph-
structured data and thus have facilitated many down-stream tasks such as node classification (Kipf'
& Welling, 2016; Veličković et al., 2017; Ying et al., 201 8a; Klicpera et al., 2018) and graph clas- sification (Defferrard et al., 2016; Ying et al., 2018b). As traditional deep learning models, GNN
model is usually composed of several stacking GNN layers. Given a graph 9 with N nodes, a GNN layer typically contains a feature transformation and feature aggregation operation as:
Feature Transformation: X in Strans (Xin;; Feature Aggregation: X [e (X 9) (I)
where Xi. E R N xdin and X E Nxdout denote the input and output features of the GNN layer with dyn and dout as the corresponding dimensions, respectively. Note that the non-linear activation not included transforms the input of X X/n E R. xdout as its output; and the feature aggregation operation fago(::) updates the node features by aggregating the transformed node features via the graph G.
Eq. (1) ease the discussion. The feature transformation operation firane (-)
In general, different GNN models share similar feature transformations (often, a single foed-forward layer), while adopting different designs for aggregation operation. We raise natural question is there an intrinsic connection among these feature aggregation operations and their assumptions? The significance of positive answer to this question is two-fold. Firstly, it offers new perspective to create a uniform understanding on representative aggregation operations. Secondly, it enables us to develop a general GNN framework that not only provides a unified view on multiple existing representative GNN models, but also has the potential to inspire build the connection among feature aggregation operations of representative GNN models including GCN (Kipf & Welling, 2016), GAT (Veličković et al., 2017), PPNP and APPNP (Klicpera et al., 2018). In particular, can be unified as the process of exactly, and sometimes approximately, addressing a graph signal denoising problem with Laplacian regularization (Shuman et al., 2013). This connection suggests that these aggregation operations share a unified goal: to ensure feature smoothness of connected nodes. With this understanding, we propose a general GNN framework, UGNN, which not only provides a straightforward, unified view for many existing aggregation operations, but also suggests various promising directions to build new aggregation operations suitable for distinct applications. To demonstrate its potential, we build an instance of UGNN called ADA-UGNN, which is suited for handling varying smoothness properties across nodes, and conduct experiments to show its effec- tiveness.
ones. In this paper, aim to
mathematically establish that the aggregation operations in these models

---

Under review as a conference paper at ICLR 2021
2 REPRESENTATIVE GRAPH NEURAL NETWORKS
In this section, we introduce notations for graphs and briefty summarize several representative GNN models. graph can be denoted as 9 = (V. E, where V and & are its corresponding node and edge sets. The connections in G can be represented as an adjacency matrix A RR RNNN with N the number of nodes in the graph. The Laplacian matrix of the graph & is denoted as L. defined as L = D - A, where D is a diagonal degree matrix corresponding to A. There are also normalized versions of the Laplacian matrix such as L I D AD 3 L I D-1 A. In this work, we sometimes adopt different Laplacians to establish connections between different GNNs and the graph denoising problem, clarifying in the text. In this section, we generally Xin RNxdd and X out E TR Xdout to denote input and output features of GNN layers. Next, we describe a few representative GNN models.
2.1 GRAPH CONVOLUTIONAL NETWORKS (GCN)
Following Eq. (I), single layer in GCN (Kipf& & Welling, 2016) can be written as follows:
Feature Transformation: X', X... W; Feature Aggregation: X..t A'...
(2)
where W E Rdd. x dout is feature transformation matrix, and Á is normalized adjacency matrix which includes self-loop, defined as follows:
Á = D 3 AD- with A= and D diag( A....... AN.).
In practice, multiple GCN layers can be stacked, where each layer takes the output of its previous layer as input. Non-linear activation functions are included between consecutive layers.
2.2 GRAPH ATTENTION NETWORKS (GAT)
Graph Attention Networks (GAT) adopts the same feature transformation operation as GCN in Eq. (2). The feature aggregation operation (written node-wise). for a node is as:
exp (Ei))
Xou =
Σ JEM(
any ain.ii
with Cxy
(4)
Σ
exp exp(eak)
kEA(()
denotes the neighbors (self-inclusive) of node i, and X [i. is the i-th row of the matrix Xout, i.e. the output node features of node In this aggregation operation, Oss is learnable attention score to differentiate the importance of distinct nodes in the neighborhood. Specifically, oij is normalized form of Eij. which is modeled as:
where
Egj = LeakyRel.U ([x),. [6, =I.
(5)
where [II-] denotes the concatenation operation and E Idd is learnable vector. Similar to GCN, a GAT model usually consists of multiple stacked GAT layers.
2.3 PERSONALIZED PROPAGATION OF NEURAL PREDICTIONS (PPNP)
Personalized Propagation of Neural Predictions (PPNP) (Klicpera et al., 2018) introduces aggre- gation operation based on Personalized PageRank (PPR). Specifically, the PPR matrix is defined as a(I (1 a)A)- where E (0, 1) is a specifies the influence of node on node j. The feature transformation operation is modeled as Multi-layer Perception (MLP). The PPNP model can be written in the form of Eq. (1) follows:
The ij-th element of the PPR matrix
Feature Transformation: X ML.(X...):
Feature Aggregation: X a<( (1-
Unlike GCN and GAT, PPNP only consists of single feature aggregation layer, but with poten- tially deep feature transformation. Since the matrix inverse in Eq. (6) is costly, Klicpera et (2018) also introduces a practical, approximated version PPNP, called APPNP, where the aggregation operation performed in an iterative way as:
x out (1 a) Ax out aX',, k=
where X!!) (0) in Klicpera et al. (2018), (K) converges to the solution obtained by PPNP, i.e., X in Eq. (6).
X/,, and x(K) is the output of the feature aggregation operation. As proved
GNNS AS GRAPH SIGNAL DENOISING
In this section. we aim to establish the connections between the introduced GNN models and graph signal denoising problem with Laplacian regularization. We first introduce the problem.
2

---

Under review as a conference paper at ICLR 2021
Problem 1 (Graph Signal Denoising with Laplacian Regularization). Suppose that given a noisy signal X E RNdx on graph G. The goal of the problem is to recover clean signal E R Nxd, assumed to be smooth over G. by solving the following optimization problem:
1111
L = | XII² c (r(F' LF),
(8)
Note that the first term guides F to be close to X, while the second term 1r is the Laplacian regularization that guides the smoothness of F over the graph. >> 0 is a balancing constant. Assuming adopt the unnormalized version of in matrix with L D A (the adjacency matrix A is assumed to be binary), the second term Eq. (8) can be written in an edge-centric way node-centric way as:
edge-centric:
Σ
[1. F :
node-centric: 1
[F
(9)
(FF)EE
EEV JEN(O
Clearly, from the edge-centric view, the regularization term measures the global smoothness of F, which is small when connected nodes share similar features. On the other hand, we can view the term EjeN()) | [ F [J. =1l: as a local smoothness measure for node as it measures the difference between node i and all its neighbors. The regularization term can then be regarded as summation of local smoothness over all nodes. Note that the adjacency matrix A is assumed be binary when deriving Eq. (9). Similar formulations can also be derived to other types of Laplacian matrices. In the following subsections, we demonstrate the connections between aggregation operations in various GNN models and the graph signal denoising problem.
3.1 CONNECTION TO PPNP AND APPNP
In this subsection, establish the connection between the graph signal denoising problem (8) and the aggregation propagations in PPNP and APPNP in Theorem and Theorem 2, respectively.
Theorem 1. When we adopt the normalized Laplacian matrix L = I-À, with A defined in Eq. (3), the feature aggregation operation in PPNP (Eq. (6)) can be regarded as exactly solving the graph signal denoising problem (8) with X!,. as the input noisy signal and =
Proof. Note that the objective in Eq. (8) is convex. Hence, its closed- solution F to exactly solve the graph signal denosing problem can be obtained by setting its derivative to 0 as:
dc
2(F X) 2LL 0 F -L)
(10)
OF
Given L I- A, F can be reformulated as:
F' === (I+ (1 (I++c(I-A) x= Itc (1= Itc ( x
(11)
The feature aggregation operation in Eq. (6) is equivalent to the closed-form solution in Eq. (11) when we set a 1/(1 + c) and X X This completes the proof.
Theorem 2. When we adopt the normalized Laplacian matrix L = 1- A. the feature aggrega- tion operation in APPNP (Éq. (7)) approximately solves the graph signal denoising problem (8) by iterative gradient descent with Xt,, as the input noisy signal,
1 and stepsize b = 2+2c'
1
Proof. To solve the graph signal denoising problem (8), we take iterative gradient method with the stepsize Specifically, the k-th step gradient descent on problem (8) is as follows:
F(k) (k--1)_ b- dc (F- p(k-1)) (1 2b 2hc)
((t-)) + 26X + 2bcAF(t-1) (12)
OF
where F(0) = X. When we set the stepsize as 2426 we have the following iterative steps:
((t)
x Itc
() I....K,
(13)
which is equivalent to the iterative aggregation operation of the APPNP model in Eq. (7) with X X and a . This completes the proof.
1.
These two connections provide a new explanation on the hyper-parameter a in PPNP and APPNP from the graph signal denoising perspective. Specifically, smaller indicates a larger c, which means the obtained X is enforced to smoother over the graph.
3.2 CONNECTION TO GCN
We draw the connection between the GCN model (Kipf & Welling, 2016) and the graph signal denoising problem in Theorem 3.
3

---

Under review as a conference paper at ICLR 2021
When adopt the normalized Laplacian matrix - A. the feature aggregation operation in GCN Eq. (2) can be regarded as solving the graph signal denoising problem (8) using one-step gradient descent with X'n as the input noisy signal and stepsize b 20
Theorem 3.
-
Proof. The gradient with respect to F X is OF F-X 2cLX. Hence, one-step gradient descent
Oc
for the graph signal denoising problem (8) can be described as:
ac
F X b
X 2bcLX (1 -bc))x + 2bcAX.
(14)
OF P=X
When stepsize b = operation of GCN. 2c and X = X we have F c- Ax in which is the same as the aggregation
With this connection, garded as solving the graph signal denoising problem multiple times with different noisy signals. Specifically, each layer of a GCN model corresponds to graph signal denoising problem, where the imput noisy signal the output from the previous layer after the feature transformation of the cur- rent layer. Note that there are earlier works (NT & Maehara, 2019; Zhao & Akoglu, 2019) drawing connection between GCN and the optimization problem in Eq. (8), where the aggregation operation GCN shown to be the first-order approximation of the exact solution.
easy verify that GCN model with multiple GCN layers can be re-
3.3 CONNECTION TO GAT
To establish the connection between graph signal denoising and GAT (Veličković et al., 2017), in this subsection, adopt unnormalized version of the Laplacian. is defined based the adjacency matrix with self-loop Å, i.e. L D Á with D denoting the diagonal degree matrix of Å. Then, the denoising problem Eq. (8) can be rewritten from node-centric view as:
arg min L
Σ
[F[ X(i, 11122
E C. Σ SEV
F[. Fb.
(15)
JEN(()
where Where.N(i)= U denotes the neighbors (self-inclusive) of node i. In Eq. (15), the constant is shared by all nodes, which indicates that the same level of local smoothness enforced to all nodes. However, nodes in a real-world graph can have varied local smoothness. For nodes with low local smoothness, we should impose relatively smaller c, while for those nodes with higher local smoothness, we need a larger c. Hence, instcad of unified e as in Eq. (15), we could consider a node-dependent a for each node i. Then, the optimization problem in Eq. (15) can be adjusted as:
arg min F
L Σ
F [t.
X [t, 111
Σ
Σ (EN(()
|F [1.
F 11
(16)
2
REV
We next show that the aggregation operation in GAT is closely connected to an approximate solution of problem (16) with the help of the following theorem.
Theorem 4. With adaptive stepsize b; 1/ Σ (c++c)) for each node the process of taking
jEN(1)
one step of gradient descent from X to solve problem (16) can be described as follows:
Fli,:]+ + Σ
(17)
JEN(
Proof. The gradient of optimization problem Eq. (16) with respect F focusing on node can be formulated as:
ac (F [r. (1.)) + Σ (c. (e) [i.:] (j.::)
(18)
OF [
SEN()
where cj in the second term appears since i is also in the neighborhood of j. Then, the gradient at PC JF(.
X is
Σ (c++ (X [i. - x [i::)) Thus, taking a step of gradient descent
Je starting from X with stepsize b can be described as follows:
dL
- OF
Σ
(a (c++)))x(..))
[1:]+
Σ b(c +()
[.:
PM
JEN()
JEN()
(19) bilc, + + which
Given b 1/ Σ (c+te;,, Eq. (19) can be rewritten as Fli }EN(s) completes the proof.
Σ
JEN(()
4

---

Under review as a conference paper at ICLR 2021
Eq. (17) resembles the aggregation operation of GAT in Eq. (4) if we treat +((c++))) the attention score Ozj. Note that we have Σ (c: + (2) = 1/b,, for all i E V. So, (c + (ÿ) can be regarded
jE
as the pre-nommalized attention score and 1/b, can be regarded as the normalization constant. We further compare (c + cj) with aij by investigating the formulation of eig in Eq. (5). Eq. (5) can be rewritten as:
Giy = LeakyReLU (X,al..ja) + X [1 :laa)
(20)
where a E le and a2 Rd are learnable column vectors, which can be concatenated to form a in Eq. (5). Comparing Eij with (a- +g)) we find that they take a similar form. Specifically, X :Ja and X Li. can be regarded as the approximations of and Cj. respectively. The difference between (c + oz) and 0zz is that the normalization in Eq. (17) for de + 0z) is achieved via summation rather than a softmax as in Eq. (4) for Ozg. Note that since GAT makes the q and Cj learnable, they also include a non-linear activation in calculating Cij. By viewing the attention mechanism in GAT from the perspective of Eq. (17), namely that G, actually indicates a notion of local smoothness for node i, we can develop other ways to parameterize C. For example, instead of directly using the node features of as an indicator of local smoothness like GAT, we can consider the neighborhood information. In fact, we adopt this idea to design a new aggregation operation in Section 5.
4 UGNN: A UNIFIED GNN FRAMEWORK VIA GRAPH SIGNAL DENOISING
In the previous section, established that the aggregation operations in PPNP, APPNP, GCN and GAT are intimately connected to the graph signal denoising problem with (generalized) Laplacian regularization. In particular, from this perspective, all their aggregation operations aim to ensure feature smoothness: either global smoothness over the graph as in PPNP, APPNP and GCN, or local smoothness for each node as in GAT. This understanding allows us to develop unified feature aggregation operation by posing the following, more general graph signal denoising problem: Problem 2 (Generalized UGNN Graph Signal Denoising Problem).
argmin L |
I r(C,, F,9).
(21)
where r(C, F,9, 9) denotes a flexible regularization term to enforce some prior over F.
Note that we overload the notation C here: it can function a vector (like node-wise constants in GAT) or even a matrix (edge-wise constants) if we want to give flexibility to each node pair. Different choices of r--) imply different feature aggregation operations. Besides PPNP, APPNP, GCN and GAT, there are aggregation operations in more GNN models that can be associated with Problem with different regularization terms such as PairNorm (Zhao & Akoglu, 2019) and DropEdge (Rong et al., 2019) (more details can be found in Appendix B). The above mentioned regularization terms are all related to the Laplacian regularization. Other regular- ization terms can also be adopted, which may lead to novel designs of GNN layers. For example, we aim to enforce that the clean signal is piece-wise linear, we can adopt r(C, F, g) = C [LF|] designed for trend filtering (Tibshirani et al., 2014; Wang et al., 2016).
scalar (like a global constant in GCN),
With these discussions, we propose a unified framework (UGNN) to design GNN layers from the graph signal processing perspective as: (1) Design a graph regularization term r(C, F, G) in Prob- lem 2 according specific applications: (2) Feature Transformation: X = Strans (X,x); and (3)
Feature Aggregation: Solving Problem 2 with X = X and the designed r(C, G). To demon- strate the potential of UGNN, next we introduce new GNN model ADA-UGNN by instantiating UGNN with r(C, F. enforeing adaptive local smoothness across nodes. Note that we introduce ADA-UGNN with node classification as the downstream task.
ADA-UGNN: ADAPTIVE LOCAL SMOOTHING WITH UGNN
From the graph signal denoising perspective, PPNP, APPNP, and GCN enforces global smoothness by penalizing the difference with a constant C for all nodes. However, real-world graphs may con- sist of multiple groups of nodes which have different behaviors in connecting to similar neighbors. For example, Section 6.1 shows several graphs with varying distributions of local smoothness (as measured by label homophily): summarily, not all nodes are highly label-homophilic, and some nodes have considerably "noisier" neighborhoods than others. Moreover, as suggested by Wu et al. (2019); Jin et al. (2020), adversarial attacks graphs tend to promote such label noise in graphs by connecting nodes from different classes and disconnecting nodes from the same class, rendering
5

---

Under review as a conference paper at ICLR 2021
resultant graphs with varying local smoothness across nodes. Under these scenarios, constant C might not be optimal and adaptive (i.e. non-constant) smoothness to different nodes is desired. As shown in Section 3.3 by viewing GAT's aggregation as solution regularized graph signal denois- adaptive for different nodes, which facilitates adaptive
ing, GAT can be regarded adopting local smoothness. However, in GAT. the graph denoising problem solved by a single step of gra- dient descent, which might still be suboptimal, Furthermore, when modeling the local smoothness factor c; in Eq. (17), GAT only uses features of node i as imput, which may not be optimal since by understanding C; as local smoothness, it should intrinsically related to the neighborhood of node i. In this section, we adapt this notion directly into the UGNN framework by introducing a new reg- ularization term, and develop a resulting GNN model (ADA- (OANNGGN) which aims to enforce adaptive local smoothness to nodes in different manner to GAT. We then utilize an iterative gradient descent method to approximate the optimal solution for Problem 2 with the following regularization term:
F
F
(C,, F. FC 2G
(22)
Vd,
vd,
LVV
JEV()
2
where di, dj denotes the degree of node and j respectively, and C; indicates the smoothness factor of node i, which is assumed to be fixed scalar. Note that, the above regularization term can be regarded as a generalized version of the regularization term used in PPNP, APPNP, and GCN. Similar to PPNP and APPNP, ADA-UGNN only consists of a single GNN layer. However, ADA-UGNN assumes adaptive local smoothness. We next describe the feature transformation and aggregation operations of ADA DDANUGNN, and show how to derive the model via UGNN.
5.1 FEATURE T
Similar to PPNP and APPNP, we adopt MLP for the feature transformation. Specifically, for node classification task, the dimension of the output of the feature transformation X/n, is the number of classes in the graph.
5.2 FEATURE AGGREGATION
We use iterative gradient descent to solve Problem 2 with the regularization term in Eq. (22) The iterative gradient descent steps are stated in the following theorem and its proof can be found at Appendix A.I.
Theorem 5. With adaptive stepsize b; 1 22 E (C. Cc,+ for each node i, the iterative
SEN(0
gradient descent steps to solve Problem 2 with the regularization term in Eq. (22) is as follows:
p(l) [b:))
Σ (Ca+ + Cc)
b 1,....
(23)
Vd.d,
JEN(()
where F [i.] = x].
The iterative steps in Eq. (23) is guaranteed for convergence stated in the following theorem and its proof can be found in Appendix A.2.
Theorem 6. The iterative steps in Eq. (23) is guaranteed converge to the optimal solution of Problem 2 with Eq. (22) as regularization term.
Following the iterative solution in Eq. (23), we model the aggregation operation (for node i) for ADA-UGNN as follows:
Σ (C. CC) x(h-") G. k k=
( [i, 26, Xin [6:
(24)
Vd.dj
where K is the number gradient descent iterations, C, can be considered as a positive scalar to control the level of "local smoothness" for node and by can be calculated from {C,lā E (())) as
b. = 1/ 2
Σ (C, C,)/d. However, in practice, C, is usually unknown. One possible solu- JEN(S)
tion is treat C2 as hyper-parameters. Treating C, hyper- paree--prameterss for all nodes is impractical, since there are, in total N of them and do not have their prior knowledge. Thus, model C, as a function of the information of the neighborhood of node as follows:
C, = s (Ies (Ne ((x ((ximl Ali E N()) v()))))
(25)

---

Under review as a conference paper at ICLR 2021
where (-)-) is a function to transform the neighborhood information of node i to vector, while hi (-) further transforms it to a scalar, a(-) denotes the sigmoid function, which maps the output scalar from (-)()) to (0, I and a can be treated as a hyper-parameter controlling the upper bound of C.. h-)-) can be modeled as a single layer fully-connected neural network. There
different designs for lx2+)) such as channel-wise variance or mean (Corso et al., 2020). In this paper, we adopt channel-wise variance as the h2(-) function. In this case, the calculation of C2 in Eq. (25) only involves H parameters, with H denoting number of classes in the dataset. APPNP can be regarded a special case of ADA- UGNN, where hz(-) is modeled as a constant function producing 1 as the
output for all nodes. For the node classification task, the representation X which is obtained after K iterations as in Eq. (24), is directly softmax normalized row-wise and its i-th row indicates the discrete class distribution of node i.
EXPERIMENT
In this section, we evaluate how the proposed ADA-UGNN handles graphs with varying local smoothness. We conduct node classification experiments on natural graphs, and also evaluate the model's robustness under adversarial attacks. We note that our main goal in proposing/cvaluating ADA-UGNN is to demonstrate the promise of deriving new aggregations as solutions of denoising problems, rather than state-of-the the performance.
6.1 NODE CLASSIFICATION
In this section, we conduct the node classification task. We first introduce the datasets and the experimental settings in Section 6.1.1 and then present the results in Section 6.1.2.
6.1.1 DATASETS AND EXPERIMENTAL SETTINGS
We conduct the node classification task on 8 datasets from various domains including citation, so- cial, co-authorship and co-purehase networks. Specifically, we use three citation networks including CORA, CITESEER, and PUBMED (Sen et al., 2008); one social network, BLOGCATALOG (Huang et al., 2017); two co-authorship networks including COAUTHOR-CSS and COAUTHOR- PH (Shchur et al., 2018); and two co- co-purchase networks including AMAZON COMP and Amazon Photos (Shchur et al., 2018). Descriptions and detail statistics about these datasets can be found in Appendix C.I. To provide a sense of the local smoothness properties of these datasets, in addition the summary statistics, we also illustrate the local label smoothness distributions in Appendix 1.1: here, we define the local label smoothness of a node as the ratio of nodes in its neighborhood that share the same label (see formal definition in Eq. (34) in Appendix C.I. Notably, the variety in local label smoothness within several real-world datasets - also observed in (Shah, 2020) clearly motivates the importance of the adaptive smoothness assumption in ADA-UGNN. For the citation networks, we use the standard split as provided in Kipf & Welling (2016): Yang et al. (2016). For BL.OG- CATALOG, we adopt the split provided in Zhao et al. (2020). For both the citation networks and BLOGCATALOG, the experiments For co-authorship and co- co-purchase networks, we utilize 20 labels per class for training, 30 nodes per class for validation and the remaining nodes for test. This process is repeated 20 times, which results in 20 different training/validationnees with different initialization. The average results over 20 x 20 experiments are reported. We compare our methods with the methods introduced in Section 2 including GCN, GAT and APPNP. Note that we do not include PPNP as it difficult scale for most of the datasets due to the calculation of verse in Eq. 6. For all methods, we tune the hyperparameters from the following options: 1) learning rate: (0.005, 0.01, 0.05]: 2) weight decay (5e-04, 5e- 56-06, 5e-07, 5e-08): J; and 3) dropout rate: (0.2, 0.5, 0.8). For APPNP and our method we further tune the number of iterations K and the upper bound for o; in Eq. (25) from the following range: 1) K: {5, 103: and s: {1,9, 19}. Note that we treat APPNP special case of our proposed method with h-(-) 1.
with 30 random seeds and the average results are reported.
splits. For each split, the experiment is repeated for 20 times
6.2.2 PERFORMANCE COMPARISON
The performance comparison is shown in Table 1, where /-test is used to test the significance. First, GAT outperforms GCN in most datasets. It indicates that modeling adaptive local smoothness is helpful. Second, APPNP/ADA -GGNN outperform GCN/GAT in most settings, suggesting that it- erative gradient descent may offer advantages to single-step gradients, due to their better ability to achieve a solution closer to the optimal. Third, and most notably, the proposed ADA-UGNN achieves consistently better performance than GCN/GAT. and outperforms or matches the state- of-the-art APPNP across datasets. Notice that in some datasets such as CORA, CITESEER, and
7

---

Under review as a conference paper at ICLR 2021
Table 1: Node Classification Accuracy Various Datasets
Dataset
GCN
GAT
APPNP
ADA-UGNN
CORA
81.75:10.8
82.56.10.8
84.49.10.6
84.59:10.8*
CITESEER
7..13:1:.0
70.77+0.88
71.97+0.66
72.05-+0.5
PUBMED
78.56:10.5
78.88:0.5
79.92+0..5
79.70:10.4
BLOGCATALOG
71.38:1:277
72.90
92.43:0099
93.33:10.3*
AMAZON-CON COMP
82.7911.3
83.01
82.9911..6
83.40
AMAZON-PHOTE
89.60.1..5
90.33111.2
91.38.11.2
91.44.1.2
COAUTHOR-CG CS
91.55=00.6 93.23=00.7
90.95+0.7
92.33 91.69:0.4
COAUTHOR-PH PH
92.86=0.7
93.84=0.5
93.9210.6**
t6, sen indicale the improvement over APPNP is signilicant at p 0.1, 0.05 and 0.005
140
ADA/UOV
Text Asoussc 150
82-
42
60
60
40
20-
Teot
20
20-
LOW
1igh
LD7
High
Low
High
Low
High
(a) CORA
(b) BLOGCATALOG
(c) AMAZON-COMP
(d) COAUTHOR-CS
Figure 1: Accuracy for nodes with low and high local label smoothness.
COAUTHOR-PH. the improvements of the proposed model compared with APPNP are not very sig- nificant. Figure in Appendix C.1.1 shows that these datasets have extremely skewed local label smoothness distributions, with the majority of nodes having perfect, 1.0, label homophily (they are only connected other nodes of the same label). APPNP shines in such cases, since its assump- tion of h-(-) = ideal for these nodes (designating maximal local smoothness). Conversely, model has the challenging task of learning (.) in such skewed cases, learning h2(-) may be quite challenging and unfruitful. On the other hand, for datasets with higher diversity in local label smoothness across nodes such as BLOGCATALOG and AMAZON-COMP the proposed ADA-UGNN achieves more significant improvements.
To further validate, we partition the nodes in the test set of each dataset into two groups: (1) high smoothness: those with local label smoothness >0.5, and (2) low smoothness: those with <0.5, and evaluate accuracy for APPNP and the proposed ADA-UGNT for each group. The results for CORA, BLOGCATALOG, AMAZON-COMP and COAUTHOR-
are presented Figure while the results for the remaining datasets can be found in Figure 4 in Appendix C.2. Figure 1 clearly shows that ADA-UGNN consistently improves performance for low-smoothness nodes in most datasets, while keeping comparable (or marginally worse) performance for high-smoothness nodes. In cases where many nodes have low-level smoothness (like BLOGCATALOG or AMAZON-COMP), our method can notably improve overall performance.
6.2 ROBUSTNESS UNDER ADVERSARIAL ATTACKS
Adversarial attacks on graphs tend to connect nodes from different classes and remove edges be- tween nodes from the same class (Wu et al., 2019; Jin et al., 2020), producing graphs with varying local label smoothness after attack (we demonstrate this in Appendix C.3). To further demonstrate that ADA-UGNN can handle graphs with varying local label smoothness better than alternatives. we conduct experiments to show its robustness under adversarial attacks. Specifically. we adopt Met- tack (Zügner & Günnemann, 2019) perform the attacks. Mettack produces non-targeted attacks which aim to impair test set node classification performance by strategically adding or removing edges from the victim graph. We utilize the attacked graphs (5%-25% perturb rate) from Jin et al. (2020) and follow the same setting, i.c., each method run with 10 random seeds and the average performance is reported. These attacked graphs are generated from CORA, CITESEER and PUBMED, respectively and only the largest connected component is retained in each graph. Furthermore, the training. validation and test split ratio 10/ 10/80%. which different from the standard splits we use in Section 6.1. Thus, the performances reported in this section is not directly comparable with those in the previous section. We compare method both with standard GNNs discussed Section (GCN, GAT, APPNP), but also with recent state-of-the-art defense techniques against adversarial attacks including GCN-Jaccard (Wu et al., 2019), GCN-SVD (Entezari et al., 2020), Pro- GNN-fs and Pro-GNN (Jin al., 2020). The detailed description of these methods can be found
8

---

Under review as a conference paper at ICLR 2021
80
72.5
86
75
70.0
Test Accuracy(Si
84
APPN
SCN 65
ADA-UCNK
65.0
60
SAT
62.5
SCVSVO
50
Pro-OVN
57.5
0%
5%
10%
15%
20%
25%
0%
5%
10%
15%
20%
25%
0%
5%
10%
15%
20%
25%
Perturbation Rater%)
Perturbation Rate(%)
Porturbation Rater%)
(a) CORA
(b) CITESEER
(c) PUBMED
Figure 2: Robustness under adversarial attacks (node classification accuracy).
Appendix C.4. Results under varying perturbation rates (attack intensities) are shown in Figure 2. Again, we observe that GAT' outperforms GCN, suggesting the appeal of an adaptive local smooth- ness assumption. Here, our method (orange) substantially outperforms GCN, GAT' and APPNP by a large margin, especially in scenarios with high perturbation rate. Moreover, the proposed ADA- UGNN is also even more robust than several specially designed adversarial defense methods, like GCN-Jaccard and GCN-SVD, which are based on pre-processing the adversarial attack graphs to obtain cleaner ones, thanks to its adaptive smoothness assumption. Compared with Pro-GNN-fss, method performs comparably even better in few settings, especially when perturbation rate high. Furthermore, in these settings, performance of our method even closer Pro- GNN, which is the current state-of-the art adversarial defense technique. Note that, Pro-GNN-fs and Pro-GNN involves learning cleaner adjacency matrices of the attacked graphs, and thus has ((M) parameters (M denotes the number of edges graph), while our proposed model has far less parameters. Specifically, we have O'din dout) for feature transformation and H parameters for modelling h-)-) with H denoting the number labels.
RELATED WORKS
There are mainly two streams of work in developing GNN models. i.c, spectral-based and spatial- based. When designing spectral-based GNNs, graph convolution (Shuman et al., 2013), defined based on spectral theory, is utilized to design graph neural network layers together with the feature transformation and non-linearity (Bruna et al., 2013; Henaff et al., 2015; Defferrard et al., 2016). graph convolution are tightly related with graph signal process-
These designs of the spectral- ing, and they can be regarded as graph filters. Low-pass graph filters can usually be adopted to denoise graph signals (Chen et al., 2014). In fact. most algorithms discussed in our work can be regarded as low-pass graph filters. With the emergence of GCN (Kipf Welling, 2016), which can be regarded as simplified spectral based and also apatial-based graph convolution operator, numerous ppatial-based GNN models have since been developed (Hamilton et al., 2017; Veličković et al., 2017; Monti et al., 2017; Gao et al., 2018; Gilmer et al., 2017).
Graph signal denoising is to infer cleaner graph signal given noisy signal, and can be usually formulated graph regularized optimization problem (Chen al., 2014). Recently, several works connect GCN with graph signal denoising with Laplacian regularization (NT Machara, 2019; Zhao & Akoglu, 2019), where they found the aggregation process in GCN models can be regarded as the first-order approximation of the optimal solution the denoising problem. On the other hand, GNNs are also utilized to develop novel algorithms for graph denoising (Chen et al., 2020). Unlike these works, paper details how family of GNN models can be unified with graph signal denoising perspective, and demonstrates its promise for new architecture design.
CONCLUSION
In this paper, we show how various representative GNN models including GCN, PPNP, APPNP and GAT can be unified mathematically as natural instances of graph denoising problems. Specifically, the aggregation operations in these models can be regarded as exactly or approximately addressing such denoising problems subject to Laplacian regularization. With these observations, we propose a general framework, UGNN, which enables the design of new GNN models from the denoising perspective via regularizer design. As an example demonstrating the promise of this paradigm, instantiate the UGNN framework with regularizer addressing adaptive local smoothness across nodes, property prevalent in several real-world graphs, and proposed and evaluated a suitable new GNN model, ADA-UGNN.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:131 13/2.6203, 2013.
Siheng Chen, Aliaksei Sandryhaila, José MF Moura, and Jelena Kovacevic. Signal denoising on graphs via graph filtering. In 2014 IEEE Globul Conference on Signal and Information Processing (GlobalSIP), pp. 872-876. IEEE, 2014.
Siheng Chen, Yonina C Eldar, and Lingxiao Zhao. Graph unrolling networks: Interpretable neural networks for graph signal denoising. arXiv preprint arXiv:2006.03300 2020.
Gabriele Corso. Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. arXiv preprint arXiv:2004405718, 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 3844-3852, 3852, 2016.
Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalexakis. All you need is low (rank) defending against adversarial attacks on graphs. In Proceedings of the 13th International Conference on Web Search and Data Mining. pp. 169-177, 2020.
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convolutional networks. In Proceedings of the 24th ACM SIGKDD, pp. 1416-1424, 2018.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. arXiv preprint 171411774.01212,, 2017.
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In NeurlPS, pp. 1024-1033 1034, 2017.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. arXiv preprint arXiv: 150605 163, 2015.
Xiao Huang, Jundong Li, and Xia Hu. Label informed attributed network embedding. In Proceed- ings of the Tenth ACM International Conference on Web Search and Data Mining, pp. 731-739, 2017.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. arXiv preprint arXiv:2005. 10203, 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 1609.02907, 2016.
Johannes Klicpera, Aleksandar Bojehevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.0550 2018.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEEE Conference on CVPR, pp. 511--514,, 2017.
Yurii Nesterov. Introductory lectures on conver optimization: A basic course, volume 87, Springer Science & Business Media, 2013.
Hoang NT and Takanori Machara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv: /0X55v999500055000 2019.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks node classification. In International Conference Learning Repre- sentations, 2019.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-9)) 93, 2008
Neil Shah. Scale-free, attributed and aassssststttatvee graph generation to facilitate introspection of graph neural networks. KDD Mining and Learning with Graphs, 2020.
10

---

Under review as a conference paper at ICLR 2021
Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint 1.08888.. 2018.
David Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to net- works and other irregular domains. IEEE signal processing magazine, 30(3):83-98, 2013.
Ryan Tibshirani et al. Adaptive piecewise polynomial estimation via trend filtering. The Annals of Statistics, 42(1)):85-323 2014.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 1710,0000, 2017.
Yu-Xiang Wang, James Sharpnack, Alexander Smola, and Ryan J Tibshirani. Trend filtering on graphs. The Journal of Machine Learning Research, 17(1):3651-369) 2016.
Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adversarial examples on graph data: Deep insights into attack and defense. arXiv preprint arXiv: 0060000000, 2019.
Zhilin Yang. William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp. 40-48. PMLR, 2016.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD, pp. 974-983, 2018a.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- erarchical graph representation learning with differentiable pooling. In Advances in neural infor- mation processing systems, pp. 4800-4810, 2018b.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. arXiv preprint 1rXiv:1909.12223 2019.
Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data aug- mentation for graph neural networks. arXiv preprint vrXiv:2006.068.00 2020.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. arXiv preprint 19Xiv: 2019.

---

Under review as a conference paper at ICLR 2021
A PROOFS
A.1 PROOF OF THEOREM 5
Theorem 5. With adaptive stepsize b; - 1/(2 2+ E (c, (c,+c))/d,) for each node vn the meEi(m)
iterative gradient descent steps to solve Problem with the regularization term in Eq. (22) as follows:
[( ==
Fik + [
Σ (VE((
(C, (C+CC)
(26)
dddz
where [()) [ :i.
Proof. The gradient of the optimization problem 2 with the regularization term in Eq. (22) with respect F (focusing on node i) is as follows:
Oc
C.+C,
F d
FL.::]
OF i.:] 2(
[[ ((i,))
Σ
(27)
Vd
(.(()
where Cj in the second term appears since node is also in the neighborhood of node j. The iterative gradient descent steps with adaptive stepsize b, can be formulated as follows: OC
( [i. + ((, b;
k
(28)
i
P 1b.
With the gradient in Eq. (27), the iterative steps in Eq. (28) can be rewritten as:
C, + C2
[i. +11 2b; - bi
(K- 1) [t, + X(,
d
2, ((.)
F(M b.
+ b, Σ
(C,+C
1,
(29)
ddd
mEN((m)
Given b; = 1/ 11/(2+ 2+ Σ
(C, + C,)/d: the iterative steps in Eq. (29) can be re-written as
()E)(m)
follows:
F(K G.
[(
(i +
Σ
EC,+C CC,
k= ==1....
(30)
dldd
eyEN(r.)
with [t.) = :[i,:), which completes the proof.
A.2 PROOF OF THBOREM 6
Theorem 6. The iterative steps in Eq. (23) is guaranteed to converge to the optimal solution of Problem 2 with Eq. (22) regularization term.
Proof. By taking the second derivative with respect to Fli :], we obtain the Hessian matrix as:
O
Ca +C
21
Σ
(31)
OF
i. 1
(1s))
which implies the Lipschitz constant of the gradient in Eq. (27) is 2+
(CotC2) To guarantee veE((1))
E
convergence, the stepsize b; for node i should be smaller than 2/
2
Σ BEN((1)
(C: + C,)/dd (Nes-
terov, 2013). The stepsize we adopt Theorem 5 = 1/ 22 Σ JEN())
(C: + C2)/d,
hence the
convergence is guaranteed.
n
12

---

Under review as a conference paper at ICLR 2021
B CONNECTIONS TO PAIRNORM AND DROPEDGE
PairNorm and DropEdge, which are two recently proposed GNN enhancements for developing deeper GNN models, are corresponding to the following regularization terms:
PairNorm:
Σ Cp [.], Fli
Σ Cn [ Fli,;]l2,
(32)
(KJ)EE
(KJ)EE
DropEdge: Ci. [F.
F :11b where Ciy E [0,1).
(33)
(LJ))E
For PairNorm, consists of Cp. be similar while disconnected nodes to be dissimilar. For DropEdge, is sparse matrix having the same shape adjacency matrix. For each edge (i,j), its corresponding Cij is sampled from Bernoulli distribution with mean 1 g, where is pre-defined dropout rate.
and the regularization term ensures connected nodes to
C EXPERIMENTS
C.I DATASETS
#Nodes
#Edges
#aabels
#Features
CORA
2708
13264
1433
CITESEER
3327
12431
3703
PUBMED
19717
108365
500
BLOGCATALOG
5196
348682
8189
AMAZON-COO COMP
13381
504937
10
767
7487
245573
745
COAUTHOR- CS
18333
182121
15
6805
COAUTHOR-PHE 34493
530417
8415
Table 2: Dataset summary statistics.
In this section, we provide information of the datasets we used in the experiments follows:
Citation Networks: CORA, CITESEER and PUBMED are widely adopted benchmarks of GNN models. In these graphs, nodes represent documents and edges denote the citation links between them. Fach node is associated bag-of-words features of its corresponding document and also a label indicating the research field of the document.
BLOGCATALOG is online blogging community where bloggers can follow each other. The BLOGCATALOG graph consists of blogger as nodes while their social relations as edges. Each blogger is associated with some features generated from key words of his/her blogs. The bloggers labeled according to their interests.
Blogcatalog:
Co-purchase Graph: AMAZON-COMA and AMAZON- PHOTO are co-purchase graphs, where nodes represent items and edges indicate that two items are frequently bought to- gether. Each item is associated with bag-of-words features extract from corresponding reviews. The labels of items are given by the category of them.
Co-authorship Graphs: COAUTHOR- and COAUTHOR-PP where nodes are authors and edges indicating the co-authorship between authors. Each author is associated with some features representing the keywords of his/her papers. The label of an author indicates the his/her most active research field.
co-authorship graphs,
Some statistics of these graphs are shown in Table 2.
C.1.1 LOCAL LABEL SMOOTHNESS OF DATASETS
We further present the distribution of local label smoothness these datasets. For a node o; we formally define the local label smoothness as follows
Σ
1(((1) ((i))
Is(i) JEN(()
(34)
W(ii
13

---

Under review as a conference paper at ICLR 2021
2750
1303
15:00
1003
2250
12.00
0000
600
750
480
2ere
02
Liber Nnoveheees
03
02
Label Stoertee
Irral Wube Sanwthiee
06
Lond Srovttedds
(a) CORA
(b) CITESEER
(c) PUBMED
(d) BLOGCATALOG
100r0
23006
5030
4033
35000
3003
2000
4000
1000
34 AMAZON-COMP
0.7
0-
1.5
0.0
0.7
64
M
1.
0.
04
D.6 0.8.
1/
02
06 0-6
0.8
1.0
(f) AMAZON PHOTOO
(g) COAUTHOR-CS
(h) COAUTHOR PH
Figure 3: Distribution of local label smoothness (homophily) on different graph datasets: note the
non-hone non-homogeneity of smoothness values.
ARPMP
JC-N
80
Twet Arruncy (S6)
30
30
50
Test Arruray
60
Texl: Accuraty
80
40
13
(a) CITESEER
(b) PUBMED
(c) AMAZON- --TTO
(d) COAUTHOR -H
Figure 4: Accuracy with low label smoothness and high label smoothness nodes. Note the consistent improvement low smoothness cases, enabled by adaptive local smoothing.
where I(v;) denotes the label of node v; and {a) is an indicator function, which takes 1 as output only when a is true, otherwise 0. The distributions of local label smoothness for all datasets are presented in 3.
C.2 NODE CLASSIFICATION ACCURACY FOR NODES WITH LOW-LEVEL AND HIGII-LEVEL LOCAL LABEL SMOOTHNESS
The performance of nodes with low local label smoothness and high local label smoothness in CITE- SEER, PUBMED, AMAZON-PHOOO and COAUTHOR- -HH are presented in Figure 4.
C.3 LOCAL SMOOTHNESS DISTRIBUTION OF ATTACKED GRAPH
Graph adversarial attacks tend connect nodes from different classes while disconnect nodes from the same class, which typically leads more diverse distributions of local smoothness level. We present the distributions of the graphs generated by Mettack (Zügner & Günnemann, 2019) with different perturbation rate for CORA, CITESEER and PUBMED in Figure 5, Figure 6 and Figure 7, respectively.
C.4 BASELINES FOR ADVERSARIAL DEFENSE
In this section, we list the descriptions of the defense algorithms adopt in Section 6.2 as follows:
GCN-Jaccard (Wu et al., 2019): GCN-Jaccard aims to pre-process given attacked graph by removing those edges added by the attackers. Specifically, Jaccard smilarlity is utilized
14

---

Under review as a conference paper at ICLR 2021
0480
12:0
3000
1237
1030
500
400
633
440
03 02
02.
Labes Smoetwess
Latil Lab4 Stramins
(M0a) Swwrehas
(a) 0%
(b) 5%
(c) 15%
(d) 25%
Figure 5: Distribution of local label smoothness on CORA with various attack perturbation rates.
-200
1000
500
200
180
Local Lobel Smoothness
Loca Labe Smnetmne
Local Label Smoothreaa
Local Label Smeothaaa
(a) 0%
(b) 5%
(c) 15%
(d) 25%
Figure 6: Distribution local label smoothness on CITESEER with various attack perturbation rates.
5000
20330
0000
5000
4000
5000
1000
0031
2000
2330
2000
2000
Laca Li0 Sea-dhiss
Lncil Libel Smaddheess
Lecal Land Sreeewiss
Lacd Lond Serddaeos
(a) 0%
(b) 5%
(c) 15%
(d) 25%
Figure 7: Distribution of local label smoothness on PUBMED with various attack perturbation rates.
measure the feature similarity between connected pairs of nodes. The edges between node pairs with low-similarity are removed by the algorithm. This pre- pre-processed graph is then utilized for the node classification task.
GCN-SVD (Entezari et al., 2020): GCN-SVD is also a pre-pr pre-process method. It use SVD to decompose the adjacency matrix of given perturbed graph and then obtain its low-rank approximation. The low-rank approximation believed be cleaner as graph adversarial attacks are observed to be high-rank in (Entezari et al., 2020).
Pro-GNN (Jin et al., 2020): Pro-GNN tries to learn cleaner graph while training the node classification model at the same time. Specifically, it treats the adjacency as parameters, which is optimized during the training stage. Several different constraints are enforced to this learnable adjacency matrix, including: 1) the learned adjacency matrix should close to the original adjacency matrix; 2) the learned adjacency matrix should be low-rank; and 3) the learned adjacency matrix should ensure feature smoothness. Pro-GNN-fs is variant Pro-GNN where the third constraint, i.e. feature smoothness, is not enforced.
C.5 INVESTIGATION ON NUMBER OF GRADIENT DESCENT STEPS ADA-UGNN
In this section, we conducted experiments to check how the performance of ADA-UGNN is affected by K. For each K, with 30 random seeds (i.c., the same setting as in Section 6.) The average performance is reported. As shown in Figure 8, the performance increases quickly as K gets larger when K is relatively small. After K becomes large, the performance either slowly grows slightly fluctuates as K further increases.
the experiments standard splits of CoRa, CITESEER and PUBMED
15

---

Under review as a conference paper at ICLR 2021
0.720
0.84
Test Accuracyool
0.715
Test Accuraco(i
0.02
0.705
0.700
0.695
0.79
(a) CORA
(b) CITESEER
(c) PUBMED
Figure 8: ADA-UGNN performance (test accuracy) under different numbers of gradient steps (K).
16


Reviews:
[{"review_id": "hLoDZODGAlP", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nStrong 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.\n\nWeak 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.\n\nRecommendation: Based on the above points, I tend to marginally accept this paper but have concerns (these weak points). \n\nQuestions & other comments:\n“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.\nIn 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?\n\n[1] Hamilton, William L., Rex Ying, and Jure Leskovec. \"Representation learning on graphs: Methods and applications.\" arXiv preprint arXiv:1709.05584 (2017).\n[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.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "RmjogvLUbVb", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "SUMMARY:\nThis 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.\n\nSTRONG POINTS:\nShowing 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.\n\nWEAK POINTS:\nThe mathematical notation of the paper is sometimes ambiguous and unclear, so it should be carefully revised.\n\nThe 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.\n\nWhile 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”. \nThe paper would benefit if the proofs of Theorems 1-4 were included in the main body, rather than in the appendix. \nThe 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.\n\nThe 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.\n\nADDITIONAL COMMENTS:\n\nThe symbol L is ambiguously used to denote different types of Laplacian matrices.\nIn 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.\n\nEquation (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). \n\nThe 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. \n\nTwo 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.\n\nIn eq (15), please clarify what d_i and d_j represent.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "LPLsZcheSlg", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\n\n2). 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”?\n\n\n3). 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?\n\n4). 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.\n\n5). 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.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ELLhXmYN_cn", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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).\nIn 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.\n\nPros:\n* Consolidates a number of (a priori) unrelated GNN architectures and unifies them from the point of view of GSP.\n* The unified picture can be used for systematic comparison of architectures or for the design of new architectures, as the authors show.\n\nCons:\n* 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.\n* The paper concentrates only on the aggregation step, but in the architectures considered there are also different non-linearities -- this part is completely neglected.\n\nMore detailed comments.\n\nOverall I very much appreciate the work towards simplifying and unifying the somewhat disconnected literature -- this is an good contribution, I think.\nWhile 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.\nWhat 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.\n\nMy 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. \nUnifying the aggregation layer is useful, but at the end the improvements that these insights bring (in terms of UGNN) seem to somewhat small.\n\nOverall I see the strongest contribution here in terms of the theoretical unification provided.\n\nMinor comment:\nThe 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.\n(cf. top of page 4)\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "DHuogjL6dBH", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Post-discussion update:**\n\nI 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.\n\n---\n\n**Original review:** \n\nThis 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.\n\nThe 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.\n\nOn 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.\n\nTherefore, 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. \n\nMinor remarks:\n- In section 5, the authors say \"GAT unintentionally adopts an adaptive C\" - I would argue this is rather deliberate and not unintentional.\n- 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.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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