ASGNN: Graph Neural Networks with Adaptive Structure
Authors: Zepeng Zhang
Songtao Lu
Zengfeng Huang
Ziping Zhao
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph neural network
graph adversarial attacks and defenses
adaptive structure

Abstract: The graph neural network (GNN) has presented impressive achievements in numerous machine learning tasks. However, many existing GNN models are shown to be extremely vulnerable to adversarial attacks, which makes it essential to build robust GNN architectures. In this work, we propose a novel interpretable message passing scheme with adaptive structure (ASMP) to defend against adversarial attacks on graph structure. Layers in ASMP are derived based on optimization steps that minimize an objective function that simultaneously learns the node feature and the graph structure. ASMP is adaptive in the sense that the message passing process in different layers is able to be carried out over different graphs. Such a property allows more fine-grained handling of the noisy graph structure and hence improves the robustness. Integrating ASMP with neural networks can lead to a new family of GNNs with adaptive structure (ASGNN). Extensive experiments on semi-supervised node classification tasks demonstrate that the proposed ASGNN outperforms the state-of-the-art GNN architectures with respect to classification performance under various graph adversarial attacks.

Under review as a conference paper at ICLR 2023
ASGNN: GRAPH NEURAL NETWORKS WITH ADAPTIVE STRUCTURE
Anonymous authors Paper under double-blind review
ABSTRACT
The graph neural network (GNN) models have presented impressive achievements in numerous machine learning tasks. However, many existing GNN models are shown to be vulnerable to adversarial attacks, which creates a stringent need build robust GNN architectures, In this work, we propose a novel interpretable message passing scheme with adaptive structure (ASMP) to defend against adversarial attacks on graph structure. Layers in ASMP are derived based on optimization steps that minimize an objective function that learns the node feature and the graph structure simultancously. ASMP is adaptive in the sense that the message passing process in different layers is able to be carried out over dynamically adjusted graphs Such property allows more fineggriined handling of the noisy (or perturbed) graph structure and hence improves the robustness. Convergence properties the ASMP scheme theoretically established. Integrating ASMP with neural networks can lead to a new family of GNN models with adaptive structure (ASGNN). Extensive experiments on semi-supervised node classification tasks demonstrate that the proposed ASGNN outperforms the state-of-the the-ttr- GNN architectures in terms of classification performance under various adversarial attacks.
INTRODUCTION
Graphs, networks, ubiquitous data structures in many fields of science and engineering (Newman) 2018), like molecular biology, computer vision, social science, financial technology, etc. In the past few years, due its appealing capability of learning representations through message passing over the graph structure, graph neural network (GNN) models have become popular choices for processing graph-structure data and have achieved astonishing success in various applications (Kipf and Welling, 2017 Bronstein et al., [017]] Wu et al.) [0200] Zhou et al.] [020]] Wu et al.) 2022). However, existing GNN backbones such as the graph convolutional network (GCN) (Kipf and
Welling 2017) and the graph attention network /Veličković et al. 2018) are shown to be extremely
vulnerable to carefully designed adversarial attacks on the graph structure (Sun et al. 2018 Jin et al.)
2021 Günnemann 2022). }. With unnoticeable malicious manipulations of the graph, the performance
of GNNs significantly drops and may even be worse than the performance of a simple baseline that
ignores all the relational information among data feature (Dai al. 2018 Zügnnr et al. 2018 Zügner and Günnemann] 2019 ZZhng and Zitnik] (2020). With the increasing deployments of GNN models applications, is of vital importance ensure their reliability and robustness, especially in scenarios, such as medical diagnosis and credit scoring, where a deflected model can lead to dramatic consequences (Günnemann, 2022).
various
To improve the robustness of GNNs with a potentially noisy graph structure input, a natural idea is to "purify" the given graph structure. Existing work in this line can be roughly classified into two categories. The first category of robustifying GNNs can be viewed as a two-stage approach (Wu et al. 2019b; Entezari et al. 2020; Gu et al., (021). A purified graph firstly obtained by "pre-processing the input graph structure leveraging on information from the node feature. Next, GNN model is trained based on this purified graph. For example, in the GNN-Jaccard method (Wu et al. 2019b), new graph is obtained by removing the edges with small "Jaccard similarity." In Entezari et al.) 2020)), observing that adversarial attacks can scale up the rank of the graph adjacency matrix, the authors propose to use low-rank approximation version of the given graph adjacency matrix as a substitute. In the second category, the graph adjacency matrix in a GNN model is treated as an unknown, purified graph structure with a parameterized form will be "learned" through optimizing

---

Under review as a conference paper at ICLR 2023
the supervised GNN training loss Zhuu et al. 2022). For example, in Franceschi et al. (211)). the graph adjacency matrix is directly learned with a GNN in a bilevel optimization way, where a full parametrization of the graph adjacency matrix is adopted. Moreover, under this full parametrization setting, structural regularizers are adopted in Jin et al. (2020); : Luo et al. (202T) as augmentations on the training loss function to promote certain properties of the purified graph. Besides the full parametrization approach, a multi-head weighted cosine similarity metric function (Chen et al. (2020)
and GNN model (Yu al. 2020) have also been used to parameterize the graph adjacency matrix for structure learning.
Going beyond purifying the graph structures to robustify the GNN models, there are also efforts on designing robust GNN architectures via directly designing the feature aggregation schemes. Under the observation that aggregation functions such as sum, weighted mean, or the max operations can be arbitrarily distorted by only single outlier node, [Geisler et al. (2020); Waan et (2020)
and Lu (2020) try to design robust GNN models via designing robust aggregation functions. Moreover, some works apply the attention mechanism (Veličković et al. 2018) mitigate the influence of adversarial perturbations. For example, Zhu et al. (2019) consider the node feature following a Gaussian distribution and use the variance information to determine the attention scores. (Tagg et al. (2020) use clean graph information and their adversarial counterparts to train an attention mechanism to learn to assign small attention scores to the perturbed edges. In Zhang and Zitnik (2020), the authors define an attention mechanism based on the similarity of neighboring nodes.
Different from existing approaches to robustify GNNs, in this work, we propose novel robust and interpretable message passing scheme with adaptive structure (ASMP). Based on ASMP, family of GNN models with adaptive structure (ASGNN) can be designed. Prior works have revealed that the message passing processes in a class of GNNs are actually (unrolled) gradient steps for solving graph signal denoising (GSD) problem (Zhu al.) 2021 Ma al.) [021: Zhang and Zhao 2022). ASMP is actually generated by an alternating (proximal) gradient descent algorithm for simultaneously denoising the graph signal and the graph structure. Designed in such principled way, ASMP is not only friendly to back-propagation training but also achieves the desired structure adaptivity with a theoretical convergence guarantee. Once trained, ASMP can be naturally interpreted as parameter-optimized iterative algorithm. This work falls into the category of GNN architecture designs. Conceptually different from the existing robustified GNNs with fixed graph structure, ASGNN interweaves the graph purification process and the message passing process, which makes it possible to conduct message passing over different graph structures at different layers, i.e., in an adaptive graph structure fashion. Thus, an edge might be excluded in some layers but included in other layers, depending on the dynamic structure learning process. Such property allows more fine- linegrained handling of perturbations than existing graph purification methods that use single graph in the entire GNN. To be more specific, the major contributions of this work are highlighted in the following.
We propose a novel message passing scheme over graphs called ASMP with convergence guarantee and specifications. To the best of our knowledge, ASMP is the first message passing scheme with adaptive structure that is designed based on an optimization problem.
Based on ASMP, a family of GNN models with adaptive structure, named ASGNN, are further introduced. The adaptive structure in ASGNN allows more fine-grained handling of noisy graph structures and strengthens the model robustness against adversarial attacks.
Extensive experiments under various adversarial attack scenarios showcase the superiority of the proposed ASGNN. The numerical results corroborate that the adaptive structure property inherited in ASGNN can help mitigate the impact of perturbed graph structure.
2 PRELIMINARIES AND BACKGROUND
An unweighted graph with self-loops is denoted as G = (V,E), where V and E denote the node set and the edge set, respectively. The graph adjacency matrix given by A E NxN, We denote by 1 and I the all-one column vector and the identity matrix, respectively. Given D = Diag (A1) E IR N
as the diagonal degree matrix, the Laplacian matrix is defined as L D A. We denote by Arw = D-1 A the random walk (or row-wise) normalized adjacency matrix and by Asym = D AD the symmetric normalized adjacency matrix. Subsequently, the random walk normalized and symmetric
2

---

Under review as a conference paper at ICLR 2023
normalized Laplacian matrices defined Lew = - A and Laym =I - D AD
respectively. X E RNXM (M is assumed to be the dimension of the node feature) is node feature matrix or graph signal, and its i-th row X1; represents the feature vector at the i-th node with i == . N. Xi (or (x)) denotes the ji, element of X with i,j ,,..., N. For vector X X represents its element-wise inverse.
2.1 GNNS AS GRAPH SIGNAL DENOISING
In the literature (Yang al. 2021 Pan al., 2021 Zhu et al. 2021). has been realized that the message passing layers for feature learning in many GNN models could be uniformly interpreted as gradient steps for minimizing certain energy functions, which carries a meaning of GSD (Mal et al. 202T). Recently, Zhang and Zhao (2022) further showed that some popular GNNs are neural networks induced from unrolling (proximal) gradient descent algorithms for solving specific GSD problems. Taking the approximate personalized propagation of neural predictions (APPNP) model (llicpera et al. 2019) as an example, the initial node feature matrix Z is first pre-propcessed by multilayer perceptron go(+) with model parameter 0 producing output X go (Z) and then X is fed into a K-layer message passing scheme given as follows:
(0) X,
H (++1) = (1 a) Aaym + ax, for t: = o,..., K
(1)
where (0) denotes the input feature of the message passing process, (k) represents the learned feature after the k-th layer, and a is the teleport probability. Therefore, the message passing of an APPNP model is fully specified by two parameters, namely, graph structure matrix Asym and parameter a, in which Asy assumes to be known beforehand and a is treated as hyperparameter.
executing K steps of gradient descent to solve GSD) problem with initialization H = X and step size 0.5 (Zhu et al. 2021 Ma et al. 2021 Zhang and Zhao 2022), which is given by
From optimization perspective, the message passing process in Eq. can be
minimize HMRN*M
| - X F/- + (1 a) Tr(H Laym H),
where X and given and share the same meaning in Eq. ① In Problem (2). the first term a fidelity term forcing the recovered graph signal H to be as close as possible to a noisy graph signal X, and the second term the symmetric normalized Laplacian smoothing term measuring the variation of the graph signal H, which can be explicitly expressed as
H.: VD
H VDj
Tr (H') Laym H
For more technical discussions on relationships between GNNs with iterative optimization algorithms for solving GSD problems, please refer to Ma et al. (202): : ZZang and Zhao (202)). Apart from using the lens optimization to interpret existing GNN models, there are also literature (Liu et al., 2021b Chen et al. 2021 Fu et al., 2022) working on building new GNN architectures based on
designing novel optimization problems and the corresponding iterative algorithms (more discussions provided in Appendix
2.2 GRAPH LEARNING WITH STRUCTURAL REGULARIZERS
Structural regularizers are commonly adopted to promote certain desirable properties when learning graph (Kalofolias) 2016 Pu et al. 2021). the following, we discuss several widely used graph structural regularizers which will be incorporated into the design of ASMP. We denote the learnable graph adjacency matrix as S satisfying S E S, where
S { TR NxN l0s S., 1, for = 1,..,, N}
defines the class of adjacency matrices. Under the assumption that node feature changes smoothly be- tween adjacent nodes (Ortega et al. 2018), the Laplacian smoothing regularization term is commonly considered in graph structure learning. Eq. (3) is the symmetric normalized Laplacian smoothing term, and a random walk normalized alternative can be similarly defined by replacing Leym in Eq. (3) by Lyw-
3

---

Under review as a conference paper at ICLR 2023
Real-world graphs are normally sparsely connected, which can be represented by sparse adjacency matrices. Moreover, is also observed that singular values of these adjacency matrices are commonly small (Zhou et al. 2013 Kumar et al. 2020). However, noisy adjacency matrix (e.g., one perturbed by adversarial attacks) tends to be dense and to gain singular values in larger magnitudes (Jin et al. (220)). In view of this, graph structural regularizers for promoting sparsity and/or suppressing the singular values are widely adopted in the literature of graph learning (Kalofolias) [016; Egilmez al., 2017; Dong et al., 2019). Specifically, the -n-ormm of the adjacency matrix often used to promote sparsity, defined as ||S|| Σúj=1 |S.y] For penalizing the singular values, the nnrrr and the f--nrrm on the singular value vector of the adjacency matrix can help. Equivalently, they can be translated to be the nuclear norm and the Frobenius norm on S, which are given by
2 ON (S) denote the ordered singular values of S. These two regularizers both restrict the scale of the singular values while the nuclear norm also promotes low-rankness. A recent study (Deng et al. (222)) points out that graph learning methods with low-rank promoting regularizers may lose a wide range of spectrum of the clean graph corresponding to important structure in the spatial domain. Thus, the nuclear norm regularizer may impair the quality of the reconstructed graph and therefore limit the performance of GNNs. Besides, the nuclear norm is not amicable for pack-propagttion and incurs high computational complexity (Luo et al.) 2021]. Arguably, the Frobenius norm of S is a more suitable regularizer for graph structure learning in comparison with the nuclear norm.
|S||. -i= of (S) and ||S|| y E of (S), respectively, where 0 (S)
THE PROPOSED GRAPH NEURAL NETWORKS
In this section, we first motivate the design principle based on jointly node feature learning and graph structure learning. Then, we develop an efficient optimization algorithm for solving this optimization problem, which eventually leads novel message passing scheme with adaptive structure (ASMP). After that, we provide interpretations, convergence guarantees, and specifications of ASMP. Finally, integrating ASMP with deep neural networks ends up with a new family of GNNs with adaptive structure, named ASGNNs.
3.1 A NOVEL DESIGN PRINCIPLE WITH ADAPTIVE GRAPH STRUCTURE
the message passing procedure in many popular GNNs can be viewed as performing graph signal denoising (or node feature learning) (Zhu et al., 2021 Ma et al. 2021 some edges in
As discussed in Section 2.1
Pan al.) 2021 /Zhan and Zhao 2022) over a prefixed graph. Unfortunately. the graph are task task-irrelevant or even maliciously manipulated, the node feature learned may not be appropriate for the downstream tasks. Motivated by this, propose new design principle for message passing. that is, to learn the node feature and the graph structure simultaneously. It enables learning an adaptive graph structure from the feature for the message passing procedure. Hence, such a message passing scheme can potentially improve robustness against noisy input graph structure.
Specifically, we construct an optimization objective by augmenting the GSD objective in Eq. (2) (we have used random walk normalized graph Laplacian smoothing term) with structure fidelity term || A 1|2 where A is the given initial graph adjacency matrix, and the structural regularizers ||S]|] and | || Then we obtain the following optimization problem:
learning
minimize HERNXM Ses
p (H, H X
XTr (H
L,w H) + +/11S A m [S]]
1 + 1/2 ||S|
structure learning
where H is the feature variable, S is the structure variable, and 7, X, μ1, and μ2 are parameters balancing different terms. To enable the interplay between feature learning and structure learning, the Laplacian smoothing term is concerned with S rather than A, i.e., Lew = I D D's with D Diag (S1). When adversarial attacks exist, perturbed adjacency matrix A will be generated. Since attacks are generally designed to be unnoticeable (Jin et al.] 202T), the perturbed graph adjacency matrix is largely similar the original graph matrix in value. In view of this, we also
4

---

Under review as a conference paper at ICLR 2023
000
ASMP: message passing with adaptive structure swemon
node feature
graph structure
output feature
updating feature
updating structure
updating feature
Figure I: Illustration of ASMP. (ASMP takes the node feature matrix X and graph structure matrix as input. Different colors of the feature indicate different embedding values. Different width the edges indicate different weight values. ASMP updates the node feature and the graph structure in an alternating way.)
include structural fidelity term S has been elaborated in Section 2.2
A The motivation for introducing the last two regularizers
3.2 ASMP: MESSAGE PASSING WITH ADAPTIVE STRUCTURE
Following the idea that the message passing a GNN model can be derived based on the optimization of a GSD objective function (Ma et al. 2021: Zhang and Zhao 2022), we can obtain message passing scheme from Problem (4). Different from the existing GSD problems for GNN model design with only the feature variable, Problem 4 is nonconvex and much more challenging. To obtain an efficient iterative algorithm that is friendly to back- back-propagen propagation training, we propose to use the alternating (proximal) gradient descent method (Parikh and Boyd 2014), i.e., alternatingly optimizing one variable by taking one (proximal) gradient step at a time with the other variable fixed. (Note that joint optimization approach is also eligible, while it would lead to slower convergence than the alternating optimization approach. More details can be found in Appendix D
We denote by H (k) and ((k) the variables at the k-th iteration (k O,..., K). the following, the update rules for H and S will be discussed, respectively.
Updating node feature matrix H: Given ( ). the subproblem with respect to feature matrix H given by
minimize HERNXM
|
XTr H ( (HH).
(5)
where (R) = I Diag( (S 1) ((k). One gradient step for H is computed as
(R+1)) (k) 171 (k 2X (A)
(k(k)_ k)) 171 (2 -2X + 22 Diag () -1 ss(i)) H(k)
(1 2m11 2m (k)) 2m ADiag (k) - ( (k) 272
where 7/2 denotes the step size.
Updating graph structure matrix S: Given (H(++1) s(()) and (r L L, H(+)))
(r(H(++1) H ())
SS
the subproblem for S becomes
S/I A - - XIr [ (k+IT Diagt (S1) (H(*+))) + μn ||S||| + #2 ||||
minimize SES
(6)
Due to the non-smoothness of the objective function, apply step of the proximal gradient descent (Parikh and Boyd| 2014) for this problem. Define
(Tk) = (2y + 2p2) (A) A >Diag S (())) 'H (1+1) (H(+))T
ADiag Diag (S 1) -1 (( H (H(+))) Diag ( (A()) 1)))))))))))) IT.
One step of proximal gradient descent is given follows (details are given in Appendix B): ((++1)_ prox na (p +Is()))+s))))))) (S(k) T()),
(7)
||-l,
5

---

Under review as a conference paper at ICLR 2023
where 7/2 is the step size and Is (S) denotes the indicator function taking value 0 0f S S and too otherwise. Moreover, the proximal operator in Eq. (7) can be computed analytically as
s(k+1) = min ReI.U((( - 1/2 T(k) 12/11 11 }}
where ReLU(X)- = max X). In conclusion, the overall procedure of ASMP can be summarized as follows:
((k+1) = -1 - 20/1 - 2m H + 2m ADiag (5 s((h)) ((())(()))))))))) + 2m X, k: = K K-1. S ((++1) -min {1, ReLU (S T(k)
(k) 1211 111)
(ASMP)
The ASMP can be interpreted as the standard message passing (i.e., the update step of H) with extra operations that adaptively adjust the graph structure (i.e., the update step of S). Therefore, an edge of the graph included in some layers may be excluded or down-weighted in other layers. A pictorial illus- tration of the ASMP procedure is provided in Figure I K-llyer ASMP can be fully specified by pa- rameters X, M1, P2. 7/1, and 1/2, which we generally denote as ASMP X, A, 7, X, fl, P2, 71, 72).
Note that ASMP is general enough cover several existing propagation rules as special cases. Remark 1 (Special cases). If we use a fixed graph structure ( = s( = A in ASMP, i.c., In = P2 = 7 = 0, the ASMP reduces to classical message passing procedure that only performs feature learning. Specifically, with 7n
242x and the symmetric normalized adjacency matrix,
ASMP can be written as
(k+1)
X.
I+X sym
I+X
Case I: when À 1, the operation in Eq. (Kliepera al. 2019)
g becomes the message passing rule of APPNP
H (1 H + ox.
Case II: when oc. the operation in Eq. ( becomes the simple aggregation in many GNN models such as the GCN model (Kipf and Welling 2017) and the simple graph convolution (SGC) model (Wu et al. 2019a):
H (++1) Asym (())
also choose to update them for several steps. The convergence of ASMP is guaranteed with proper selections of the step sizes as demonstrated in Theorem 4 Before proceeding the convergence result, we first introduce some standard assumptions on the node feature vectors and the degree matrices, which are widely adopted in the literature (Garg
Instead of updating both S and H once,
al.
2020 Liao al. 2021 Cong et 2021).
Assumption 2. The energy of the node feature is uniformly upperbounded, i.e., H i = 1,..., N and k = =....., K.
S
B for
Assumption 3. The diagonal elements of the degree matrix is lowerbounded by a positive constant, ie. min; D; = <>>>> 0f =1 -,...., N.
Theorem 4. Let H X and S(0) A. Under Assumption and Assumption 3 the Tk= generated by (ASMP) with 0 < Th 1428 and 0 TT2 <
sequence (H ( 1
(1+2+((+ N=B converges to first-order stationary point of Problem denoted as H' with rate
inf EZK
H (k+1) - + |((++] -
1 -
pK
where p constant depending on the step sizes and Lipschitz constants, and p (H,S) represents the objective of Problem 44.
Proof. The proof for Theorem 4 is in Appendix C Note that if multiple updating steps are used for S
and H. in ASMP, this convergence result still holds (Bolte al. 2014 Nikolova and Tan 2017). Li

---

Under review as a conference paper at ICLR 2023
3.3 ASGNN: GRAPH NEURAL NETWORKS WITH ADAPTIVE STRUCTURE
In this section, we introduce a family of GNNs leveraging the ASMP scheme. Integrating (ASMP) with a machine learning model ( (c.g., a multilayer perceptron) with H = X = (Z) a K-layer ASGNN model is defined as follows:
H ASMP, ()) A, 7,, A, M1, M2, 22,71
In ASGNN, we have chosen a decoupled architecture similar to APPNP Klicpera et al. 2019) and deep adaptive GNN (DAGNN) (Liu et al., 2021a). Specially, in ASGNN, the model go will first transform the initial node feature as X = go (Z). and then ASMP performs K steps of message passing with input go (Z).
The parameters in ASMP, i.e., 7, X, M1, and μ2, are set to be weights to be learned from the downstream tasks. For example, chosen as the cross-entropy classification loss on the labeled nodes and the whole model is trained in an end-to-end way. Since ASMP is derived from the alternating (proximal) gradient descent algorithm, trained ASMP is naturally a parameter-optimizze and 7/2 in ASMP can be chosen according to the results in Theorem 4 However, such choices seem to be too conservative in practice and may lead to slow convergence. Thus, we may also consider the step sizes 1/1 and 7/2 as learnable parameters. Convergence property of ASMP with learned step sizes will be showcased in the experiments. In conclusion, there are in total six parameters in ASMP considered during the learning process.
sumi-supreiseed node classification tasks, the loss function is
iterative algorithm. The step sizes m
In this paper, we have focused problems in which there is an initial graph structure, while the use of ASGNN may also be extended to scenarios where the initial structure is not available. In such case. we can first create k-nearest neighbor graph or use some optimization methods (Dong et al.) 2016, Kalofolias 2016 Kumar et al. (2020) to learn a graph structure based on the node feature. Such extensions of ASGNN can be promising future research directions.
EXPERIMENTS
In this section, we conduct experiments to validate the effectiveness of the proposed ASGNN model. First, we introduce the experimental settings. Then, we assess the performance of ASGNN on semi- supervised node classifications tasks and investigate the benefits of introducing adaptive structure into GNNs against global attacks and targeted attacks. Finally, we analyze the structure denoising ability and the convergence property of ASMP with the learned step sizes.
4.1
EXPERIMENT SETTINGS
Datasets:
We perform numerical experiments on real-world citation graphs, i... Cora (Sen et al. Citeseer (Sen et al., 2008), Cora-ML (Bojchevski and Günnemann] (018). and ACM (Wang
2008
et al. 2019). and only consider the largest connected component in each dataset.
Baselines: To evaluate the effectiveness of ASGNN, compare it with GCN and several benchmarks that are designed from different perspectives to robustify the GNNs, including GCN-Jaccard (Wu al. 2019bb that pre-processes the graph by eliminating edges with low Jaccard similarity of node feature vectors, GCN-SVD (Entezari et al. (020) that applies the low-rank approximation of the given graph adjacency matrix, GNNGuard (Zhang and Zitnik (020) that defines an attention mechanism based on the similarity of neighboring nodes, Pro- ONo-GNN (Jin et al. 2020) that jointly learns graph structure and GNN model guided by some predefined structural priors, and Elastic GNN (Liu et al.) 2021b) that utilizes trend filtering instead of Laplacian smoothing to promote robustness. The code is implemented based on PyTooch Geometric (Fey and Lenssen 2019). For GCN-Jaccard, GCN-SVD, and Pro-GNN, we the implementation provided in DecpRobust (Li al. 2020). For GNNGuard and Elastic GNN, we follow the implementation provided in the original papers (Zhang and Zitnik 2020
Liu et al. 2021b)
Parameter settings: For all the experimental results, we give the average performance and standard variance with 10 independent trials. For each graph, randomly select 10%/10%/80%% of nodes for training, validation, and testing. The Adam optimizer is used all experiments. The models' hyper- parameters are tuned based the results of the validation set. The search space of hyperparameters
7

---

Under review as a conference paper at ICLR 2023
Table Node classification performance (aceuracy std) under global attack (Bold: the best model;
wavy: the runner-up model)
Dataset
Ptb. rate (%)
GCN
GCN-Jaccard
GCN-SVD
GNNGuard
Pro-GNN
Elastic GNN
ASGNN
85 3,0,99
81.75 + 0,49
75.15 = 0.64
80.14 + 0.15
82.94 : 0.28
84,80 0.58
85,38 : 0.24
79.71
0.48
77.81 1: 0.52
73.71 = 0.12
78.71
+ 0.33
82.20 1: 0.35
82.26 1.69
82.31 :: 0.53
Corn
10
74.28 0.79
74.38 4: 0.30
65.85
0.39
75.35
0:24
79.30
+: 0.64
4..57
80.31
1: 0.61
15
69.05 0.77
72.54 + 0.31
65.33
+ 0.47
73.54
+ 0.57
77.69 + 0.74
77.84
+
78.11
+ 0.76
20
57.76 +:
71.76
+: 0.48
60.85
=
70.99
14.16.
63.68
0.27
77.04
25
52.67 + 1.00
69.67
0.46
59.31
0.17
68.79
+: 0.82
71.19
62.90 1:337
75.18 :: 0.97
23.97 1.97
72.09 0.49
0.39
73.00
0.50
73.35
0.47
0:43 73.82
73.99
72.57 0.93
70.79 + 0.30
67.59
0.43
72.29
0.39
73.16
0:42
13.30
73.35 :: 0.44
Citescer
10
71.21 4: 1.44
70.27 1: 0.62
67.38
0.65
70.15 1: 0.36
72.78
A,079
12.78..4.00
72.83 1: 0.56
15
68.00 1.04
69.97 + 1.49
66.47
0.51 65,83
70.42
4 0.57
71.55 + 0.73
71.73
71.85 1.83
20
59.75 0.8
69.49 + 0.71
0.69
69.28
+ 0,41
70.07. 1,11
61.55 + 1.82
71.06 + 3.09
99.98 0.9
68,14
0.36
62.34
58.58
69.73,4.0955
63.98
70.03 3.45
0
86,59 1 0.07
84.68 1: 0.32
82.96
0.27
79.25 1: 0.30
79.48 +: 0.40
87.01
1 0.28
86.68
:: 0.43
0.50
0.37
81.78
0.46
79.07 4: 0.11
78.57
84.68 0.25
84.80
Con-ML
10
74.57 + 0.75
$0.35 + 0.24
81.75
0.33
78.99 + 0.10
78.74 + 0.84
62.01.+00.64 0.04
83.09
0.59
54.69 + 0.52
76,53
0.29
0.44 74.76
78.59 +: 0.09
73.62 :: 0.85
+: 2.69
73.71
: 1.82
20
40,24 1.97
76,46
53.94
0.15
77.58 1: 0.13
72.72 0.88
52.18
0.71
73.65
1.42
44.13 4 3.42
75,95
0.50 25005
0.17 71.98
77.03 1: 0.11
74.91
1: 0.56
53.05
0.36
75.36 :: 1.34
91,25 0.100
89.62
0.41
87.51
91.60
90.11 0.57
91,45
92.56
84,29 1 0.57
84.64 +: 0.27
85.29 + 1.13
82.64 +: 1.34
88.25 4: 1.19
90,10
90.60 :: 0.28
ACM
0.31
0.68
+ 1.29
89.45 0.441
90.10
15
79.65
+ 1.00
74.66 + 0.94
83.81
0.81
77.44 + 1,46
87.59
0.74
89.93 0.51
79.95
0.50
74.26
+: 0.75
82.35
1.64
77.38 + 1.55
87.83 1.03
88 05 0.35
90.61 : 0.28
25
79,55
1.16
74.12 1: 0.81
82.04
0.99
77.60
1: 1,60
88.06 0.85
88.15 0.58
90.15 0.33
are as follows: 1) learning rate: (0.005, 0.01, 0.05); 2) weight decay: {0, 5e-5, 5e-4); 3) dropout rate:
10.1, 0.5, 0.8): 4) model depth: [2, 4, 8, 16). For GCN-Jaccare the threshold of Jaccard similarity for removing dissimilar edges chosen from {0.01, 0.02, 0.03, 0.04, 0.05, 0.1). For GCN-SVD, the reduced rank of the graph is tuned from (5, 10, 15, 50, 100, 200 For Elastic GNN, the regularization coefficients are chosen from |3, 6, 9). For Pro-GNN, we adopt the hyperparameters provided in their paper (Jin et al.) 2020).
4.2 PERFORMANCE UNDER ADVERSARIAL ATTACK
The performance of the compared models is evaluated under the training taining-time adversarial attacks (Wang and Gong, 2019; Zügner and Günnemann (201)), i.e., the graph is first attacked, and then the GNN models are trained on the perturbed graph. In the following, we conduct experiments under both the glohal attack and the targeted attack. Specifically, the global attack aims to reduce the overall performance of GNNs (Zügner and Günnemann, 2019) while the targeted attack aims to fool GNNs on some specific nodes (Zügner et al. 2018).
Global Attack: We first test the node classification performance of ASGNN and other baselines under global attack using a representative global attack method called meta-attack (Zügner and Günnemann 2019). We vary the perturbation rate, i.e., the ratio of changed edges, from 0% to 25% with an increasing step of 5%. The results are reported in Table From the table, we observe that the proposed ASGNN model outperforms other methods in most cases. For instance, ASGNN improves GCN over 30% on the Cora-ML. dataset at a 20% perturbation rate and over 20% on the Cora dataset 25% perturbation rate. On Cora, Citeseer, and ACM datasets, ASGNN beats other baselines at various perturbation rates by a large margin. The GCN-Jaccard method and the GNNGuard slightly outperforms ASGNN on the Cora-ML dataset poorly on other datasets. Specifically, on the other three datasets under the 25% perturbation rate, ASGNN outperforms GCN-Jaccard by 22%, 10%, and 10%, respectively. Such inspiring results demonstrate that ASGNN can better resist global attack than other baseline methods.
15%-25% perturbation rate, while they performs
Targeted Attack: For the targeted attack, we use representative method called NETTACK Ziigner et al. 2018). Following existing works (Zhu et al.) 2019: Jin et al., 2020), we vary the perturbation number made on every node, i.c., the number of edge removals/additions, from 0 to with an increasing step of 1. The results are reported in Table We choose the nodes in the test set with degrees larger than 10 as targeted nodes and the reported classification performance is evaluated on target nodes. Thus, the results in Table is not directly comparable with the results in Table [I] From the table, we can see that the proposed ASGNN attains better performance than other baselines in most cases. For instance on the Citeseer dataset with perturbations per targeted node, ASGNN
8

---

Under review as a conference paper at ICLR 2023
Table 2: Node classification performance (aceuracy + std) under targeted attack (Bold: the best
model; wayy: the runner-up model)
Dataset
Ptb. number
GCN
GCN-Jaccar
GCN-SVD
GNNGuard
Pro-GNN
Elastic GNN
ASGNN
0
82.53 : 1.45
81.95 = 0.29
71.35 1: 1.40
77.59
1.34
82.92 : 0.29
84,93
2.28
85.01 5,557
19 1.66
75.30
1.51
75.18 1: 1.80
76.67 2.93
81.48 3. 0.91
81.44 1.81
81.57 1: 1.18
Cora
71.33 1.29
70.24 = 1.52
71.81
+: 1,63
75.48
3.02
79.03
1,80
76.74
1.97
78,80
66.63 1: 1.53
69.04
= 0.94
65.18
1: 1.65
75.09
1.06
72.75
:: 1.32
73.97
2.67
75.30 1: 1.35
61.45 2.16
61.68
1.06
58.79
2.14
70.45
1.34
70.11
+: 2.45
68.31
3.50 65.78
70,24
5
56.75 1.37
59.52
1.88
59.16
70.58
1.80
66.98 + 1.63
2.51
68..55 + 3.21
83.65
1.01
81442 0,76
81,90 1.95
80.63 + 0.63
80.00 = 1.45
78.57 + 2.67
80,95
4.2.5
80.52 + 0.85
80.79 + 1.17
81.21 + 1.11
Citeseer
1.02
1.77
73.02 6.77
80.63 0.95
0.550
81.11 1.32
66.51 +: 3.36
74.76
1.31
76.03 +: 3.71
78.09
2. 3.39
79.36 +: 4.76
80 31 1.1.10
80.32 :: 1.90
1.62
76.34
3.31
4.6.3 77.69
75.71 + 4.87
72.06
52.70 1,98
72.85
1.65
60. 6.67
75,37 +:
73.95 + 7,13
73.96 3,90
80.75
1.70
0.36
84,91
0:24
83.06 +
81.82
0:45
86.04 +: D.80
8K.44 0.67
88.88
0.31
83.85
83.82
80.51 0.28
82.22
0.66
83.77
85
86,20
Con--ML
2
79.18 1: 1.31
0.33 83.75
78.73 1: 0.34
82,35
4: 0.66
82.29 +: 0.13
84.34
1,02
84.41 1 1.51
78.23 0.20
82,39
80.58
1.62
70.61 1.56
81.90
0.45 $1.35
76.25 + 0.51
0.61 80.50
79.92 + 1.44
78.31
1.20
80,81 + 0.99
64.52 1.29
0.34
75.47
0.41
0.54 79.86
77.63 + 1.68
74.08
80, 1,85
90.33 0.09
89.76
0.39
86.21
1: 0.46
90,36
00.36.1.0.11
90.22 1: 0.60
90.31 1: 0.71
92.11 0.41
89.70 0.22
0.47 83.62
83,50
4: 0.71
0.35 89.09
87.09 +: 0.65
90.03 0.43
91.08 1.36
ACM
82.06 1.12
80.47
0.63
82.09 0.73
81.86
87.01
0.53
87.72
90.55 0.47
80. 26 +: 1.17
77.07
0.67
81.09
0.78
79.24
2 1.91
87.07
+ 1,14
84.75 +: 2.07
89.54 :: 0.49
86
77.45
80.76
74.88
$7,04.2
1.16
83.49
89.45
5
73.32 4: 1.77
74.38
0.59
79.74 4: 0.77
71.54 4 1.97
86.42 4 0.71
81.67 A: 1.53
88.44 :: 0.71
improves GCN by 25% and outperforms other baselines by over 5%. The reported results demonstrate that ASGNN can also effectively resist the targeted attack.
4.3 ROBUSTNESS OF ASGNN
The message passing scheme in ASGNN is designed based on jointly node feature learning and graph structure learning principle. To validate that ASGNN can help purify (i.e., denoise) the structure, we evaluate the quality of the graphs generated by ASGNN via evaluating the performance GCN model trained the generated graphs in the last layers of ASGNN (which named as GCN-AS). Under the assumption that the GCN trained on a purer graph will give better performance, the performance of GCN-AS can indicate the quality of the learned graph in ASGNN. We conduct experiments on different datasets under targeted attack with five perturbations per node and the results in Table 3 It can be seen that the performance of GCN-AS is much better than GCN. Moreover, GCN-AS even outperforms other defense models on some datasets, e.g., GCN-AS outperforms all other baselines on ACM dataset. These inspiring results indicate that ASGNN can mitigate the influence of adversarial attacks.
Table 3: Performance comparison of GCN and GCN-AS.
Model
Cora
Citeseer
Cora-MI.
ACM
GCN
56.75 1.37
52.70 1.98
64.52 + 1.29
73.32
1.77
GCN-AS
67,91 + 9.28
69.96
5.30
79.63 1: 7.98
87.56
4: 1.49
We provide some additional experiments in Appendix E including the runtime analysis in Appendix
E.1 the discussion of the leaned coeeficients in ASGNN in Appendix E.2 the sparsity level of the graphs generated in ASGNN in Appendix E.3 and the convergence analysis of ASMP with learned step sizes in Appendix E.4
CONCLUSION
In this work, we have developed an interpretable robust message passing scheme named ASMP following the jointly node feature learning and graph structure learning principle. ASMP provably convergent and it has clear interpretation a standard message passing scheme with adaptive structure. Integrating ASMP with neural network components, we have obtained a family of robust graph neural networks with adaptive structure. Extensive experiments real-world datasets with various adversarial attack settings corroborate the effectiveness and the robustness the proposed graph neural network architecture.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Hongjoon Ahn, Yongyi Yang, Quan Gan, David Wipf, and Taesup Moon. Descent steps of a relation- aware energy produce heterogeneous graph neural networks. arXiv preprint arXiv:2206. 10081, 2022.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. Proceedings of the International Conference on Learning Representations, 2018.
Jérôme Bolte,
Shoham Sabach, and Marc Teboulle. Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Mathematical Programming. 146(1):459-499) 2014.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: Going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18 42, 2017.
Siheng Chen, Yonina C Eldar, and Lingxiao Zhao. Graph unrolling networks: Interpretable neural networks for graph signal denoising. IEEE Transactions on Signal Processing, (9:3699-3747 2021.
Yu Chen, Lingfei Wu, and Mohammed Zaki. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. In Proceedings of Advances in Neural Information Processing Systems, volume 33, pages 19314-19326, 2020.
Fan RK Chung. Spectral gruph theory, volume 92, American Mathematical Society, 1997.
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On provable benefits of depth in training graph convolutional networks. In Proceedings of Advances in Neural Information Processing Systems, volume 34, pages 9936-9949, 2021.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. In Proceedings of the International Conference on Machine Learning. pages 124. PMLR, 2018
Chenhui Deng, Xiuyu Li, Zhuo Feng, and Zhiru Zhang. Garnet: Reduced-rank topology learning for robust and scalable graph neural networks. arXiv preprint arXiv:2201.12741, 2022.
Xiaowen Dong, Dorina Thanou, Pascal Frossard, and Pierre Vandergheynst. Learning laplacian matrix in smooth graph signal representations. IEEE Transactions on Signal Prucessing, 64(23); 6160-6173, 2016.
Xiaowen Dong, Dorina Thanou, Michael Rabbat, and Pascal Frossard. Learning graphs from data: A signal representation perspective. IEEE Signal Processing Magazine, 36(3):44-62 2019.
Hilmi Egilmez, Eduardo Pavez, and Antonio Ortega. Graph learning from data under laplacian and structural constraints. IEEE Journal of Selected Topics in Signal Processing, 1166):25 841, 2017.
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 Web Search and Data Mining, pages 169-177, 2020.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In Proceedings of the International Conference Machine Learning, pages 1972-1988 1982. PMLR, 2019.
Guoji Fu, Peilin Zhao, and Yatao Bian. p-Laplacian based graph neural networks. In Proceedings of the International Conference Machine Learning, pages 6878-6911 PMLR, 2022.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In Proceedings of the International Conference on Machine Learning. pages 3419-3430. PMLR, 2020.
10

---

Under review as a conference paper at ICLR 2023
Simon Geisler, Daniel Zügner, and Stephan Günnemann. Reliable graph neural networks via robust aggregation. In Proceedings of Advances in Neural Information Processing Systems, volume 33, pages 13272-13284, 2020.
Yujie Gu, Yangkun Cao, Qiang Huang, and Huiyan Sun. A general unified graph neural network framework against adversarial attacks. In URL https://ppemeiiee.ee/ffommmm http:///////mm/////////////CCCC
2021.
Stephan Günnemann. Graph neural networks: Adversarial robustness. In Lingfei Wu, Peng Cui, Jian Pei, and Liang Zhao, editors, Graph Neural Networks: Foundations, Frontiers, and Applications, pages 149-176. Springer Singapore, Singapore, 2022.
Zhimeng Jiang. Xiaotian Han, Chao Fan, Zirui Liu, Na Zou, Ali Mostafavi, and Xia Hu. Fmp: Toward fair graph message passing against topology bias. arXiv preprint 220::2202.041887, 2022.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pages 66-74, 2020.
Wei Jin, Yaxing Li, Han Xu, Yiqi Wang, Shuiwang Ji, Charu Aggarwal, and Jiliang Tang. Adversarial attacks and defenses graphs: A review, tool and empirical studies. ACM SIGKDD Explorations Newsletter, 22(2):19-34, 2021.
Vassilis Kalofolias. How to learn a graph from smooth signals. In Proceedings of Artificial Intelligence and Statistics, pages 920-929. PMLR, 2016.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Proceedings of the International Conference on Learning Representations, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In Proceedings of the International Conference on Learning Representations, 2019.
Sandeep Kumar, Jiaxi Ying, José Vinícius de Miranda Cardoso, and Daniel P Palomar. A unified framework for structured graph learning via spectral constraints. Journal of Machine Learning Research, 21(22):1-60, 2020.
Yaxin Li. Wei Jin, Han Xu, and Jiliang Tang. Deeprobust: A pytorch library for adversarial attacks and defenses. arXiv preprint arXiv:2005.06145 2020.
Renjie Liao, Raquel Urtasun, and Richard Zemel. A pac-bayesian approach to generalization bounds for graph neural networks. In Proceedings of the International Conference on Learning Representations, 2021.
Xiaorui Liu, Jiayuan Ding, Wei Jin, Han Xu, Yao Ma, Zitao Liu, and Jiliang Tang. Graph neural networks with adaptive residual. Proceedings of Advances Neural Information Processing Systems, volume 34, pages 9720-9733, 2021a.
Xiaorui Liu, Wei Jin, Yao Ma, Yaxin Li. Hua Liu, Yiqi Wang, Ming Yan, and Jiliang Tang. Elastic graph neural networks. In Proceedings of the International Conference on Machine Learning. pages 6837-6849. PMLR, 2021b.
Dongsheng Luo, Wei Cheng, Wenchao Yu, Bo Zong, Jingchao Ni, Haifeng Chen, and Xiang Zhang. Learning to drop: Robust graph neural network via topological denoising, In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pages 779-787, 2021.
Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah. A unified view on graph neural networks as graph signal denoising. In Proceedings of the 30th ACM International Conference on Information Knowledge Management, pages 1202-1211, 2021.
Mark Newman. Networks. Oxford University Press, 2018
Mila Nikolova and Pauline Tan. Alternating proximal gradient descent for nonconvex regularised problems with multiconvex coupling terms. HAI, 2017.
11

---

Under review as a conference paper at ICLR 2023
Antonio Ortega, Pascal Frossard, Jelena Kovačević, José MF Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106 (5):808 828,8888888 2018.
Xuran Pan, Shiji Song, and Gao Huang. A unified framework for convolution based graph neural networks. In URL http:/ppwrrwiiineeefooommdddddda Bb9BB, 2021.
Neal Parikh and Stephen Boyd. Proximal algorithms. Foundations and Trends in Optimization, 1(3): 127-239, 2014.
Xingyue Pu, Tianyue Cao, Xiaoyun Zhang, Xiaowen Dong, and Siheng Chen. Learning to learn graph topologies. In Proceedings of Advances in Neural Information Processing Systems, volume 34, pages 4249-4262, 2021.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification network data. Al Magazine, 29(3):33-93, 2008.
Lichao Sun, Yingtong Dou, Carl Yang, Ji Wang, Philip S Yu, Lifang He, and Bo Li. Adversarial attack and defense on graph data: A survey. arXiv preprint arXiv: /812. 10528, 2018.
Xianfeng Tang, Yandong Li, Yiwei Sun, Huaxiu Yao, Prasenjit Mitra, and Suhang Wang. Transfer- ring robustness for graph neural network against poisoning attacks. In Proceedings of the 13th International Conference on Web Search and Data Mining, pages 600-608, 2020.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In Proceedings of the International Conference on Learning Representations, 2018.
Binghui Wang and Neil Zhenqiang Gong. Attacking graph-based classification via manipulating the graph structure. In Proceedings of the ACM SIGSAC Conference on Computer and Commumications Security, pages 2023-2040) 2019.
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. Heterogeneous graph attention network. In Proceedings of the World Wide Web Conference, pages 2022-2032, 2019.
Yiwei Wang, Shenghua Liu, Minji Yoon, Hemank Lamba, Wei Wang, Christos Faloutsos, and Bryan Hooi. Provably robust node classification via low-pass message passing. In Proceedings of the IEEE International Conference on Data Mining, pages 621 1-3.0. IEEE, 2020.
Yu-Xiang Wang, James Sharpnack, Alex Smola, and Ryan Tibshirani. Trend filtering on graphs. In Proceedings of Artificial Intelligence and Statistics, pages 1042-1050. PMLR, 2015.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplify- ing graph convolutional networks. In Proceedings of the International Conference on Machine Learning, pages 6861-6871. PMLR, 2019a.
Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adversarial examples for graph data: deep insights into attack and defense. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 4816-4823, 2019b.
Lingfei Wu, Peng Cui, Jian Pei, and Liang Zhao. Graph Neural Networks: Foundations, Frontiers, and Applications. Springer Singapore, Singapore, 2022.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4-25 2020.
Yongyi Yang, Tang Liu. Yangkun Wang, Jinjing Zhou, Quan Gan, Zhewei Wei, Zheng Zhang, Zengfeng Huang, and David Wipf. Graph neural networks inspired by classical iterative algorithms. In Proceedings of the International Conference on Machine Learning, pages 11773-11781 PMLR, 2021.
12

---

Under review as a conference paper at ICLR 2023
Donghan Yu, Ruohong Zhang, Zhengbao Jiang, Yuexin Wu, and Yiming Yang. Graph-revised convolutional network. In Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 378-393, Springer, 2020.
Hongwei Zhang, Tijin Yan, Zenjun Xie, Yuanqing Xia, and Yuan Zhang. Revisiting graph convolu- tional network on semi-supervised node classification from an optimization perspective. arXiv preprint arXiv:2009. 11469, 2020.
Li Zhang and Haiping Lu. castureiimpottace-awaaaa and robust aggregator for gen. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 1813-1822, 2020.
Xiang Zhang and Marinka Zitnik. Gnnguard: Defending graph neural networks against adversarial attacks. In Proceedings of Advances in Neural Information Processing Systems, volume 33, pages 9263-9275, 2020.
Zepeng Zhang and Ziping Zhao. Towards understanding graph neural networks: An algorithm unrolling perspective. arXiv preprint arXiv:2206.04471, 2022.
Lingxiao Zhao and Leman Akoglu. PairNorm: Tackling oversmoothing in GNNs. In Proceedings of the International Conference Learning Representations, 2020.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: review of methods and applications. Al Open, 1:57-81, 2020.
Ke Zhou, Hongyuan Zha, and Song. Learning social infectivity in sparse low-rank networks using multi-dimensional hawkes processes. In Proceedings of Artificial Inteliiencee and Statistics, pages 641-649. PMLR, 2013.
Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu. Robust graph convolutional networks against adversarial attacks. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 1399-1407, 2019.
Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with an optimization framework. In Proceedings of the Web Conference 2021, pages 2021.
Yanqiao Zhu, Weizhi Xu, Jinghao Zhang, Qiang Liu, Shu Wu, and Liang Wang. A survey graph structure learning: Progress and opportunities. arXiv preprint arXiv:2103.03033 033006 2022.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In Proceedings of the International Conference Learning Representations, 2019.
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks neural networks for graph data. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2847-2856, 2018
13

---

Under review as a conference paper at ICLR 2023
A RELATED WORK ON OPTIMIZATIIO-INDDUCH, GRAPH NEURAL NETWORK DESIGN
Since ASGNN proposed in this paper induced from an optimization algorithm, in this section, we give more literatue review on ceiimization-induce GNN model design to supplement our discussion.
The idea of optimization -nnduneddddddddddd GNN model design partly stems from the observation that many primitive handcrafted GNN models could be nicely interpreted as (unrolled) iterative algorithms for
solving a GSD optimization problem (Ma et al., 2021 Zhu et al., 2021 Zhang and Zhao (022). Based on this observation, many papers aim at strengthening the capability of GNNs by carefully designing the underlying optimization problems and/or the iterative algorithms solving it.
For example, inspired by the idea of trend filtering (Wang et al. 2015). Liu et al. (2021b) replace the Laplacian smoothing term (which is in the form of (2-norm) in the GSD problem with an l2 -norm to promote robustness against abnormal edges. Also for robustness pursuit, Yang et al. (202T) replace the Laplacian smoothing term with nonlinear functions imposed over pairwise node distances. Since the classical Laplacian smoothing term in GSD only promotes smoothness nodes, the authors in /Zhang et al. 2020); Zhao and Akoglu (2020) further suggest promoting the non-smoothness over the disconnected nodes, which is achieved by deducting the of distances between disconnected pairs of nodes from the denoising objective. In Jiang et al. (2022). the authors augment the GSD objective with fairness term to fight against large topology bias. Most recently, Fu et al. (2022) propose a p-Laplacian message passing scheme and a PGNN model, which is capable of dealing with heterophilic graphs and is robust to adversarial perturbations, Apart from that, Ahn et al. (2022) designs a novel regularization term to build heterogeneous GNNs.
connected
Although there is rich literature on optimization induucdd GNN model design, all of them are focusing on learning the node feature matrix. The idea of this paper is similar to them in terms of the GNN design philosophy, however, we design an objective to jointly learn the node feature and the graph structure which was rarely covered in the literature.
B DERIVATION OF THE PROXIMAL GRADIENT STEP IN EQ.
For the S-block optimization, i.e., Eq. 6 we define the objective function except the term μl ||S]] as fS()), i.e.,
fs(S) = >/S
P XTr ( + l12 |||||
where D = Diag (S1). In this section, we first derive the expression of V (S)(S) and then compute the proximal operator in Eq.
B.1 ON COMPUTATION OF V fs)
We first focus on the gradient computation of the second term in Eq. (9. For the graph degree matrix, we have
D = Diag (S1) = S11 I
where c denotes the Hadamard product. Based on the rule of matrix calculus, the differential of the scalar function (r(H D I -SSH) with respect to matrix variable can be computed as follows:
d (Ir DH = Tr T D- ( SH)
For an invertible D (note that, in this paper, the graphs considered all have self loops, so D is always invertible), we have
d(D-") -D dD)
Thus, we can get
d (Tr (H DDTD-'H)) =Tr ( (((1 o ISH
=Tr DH - (D (D-'SHH D @ 1) d (S)
=Th (HH'D D-1 1Diag (D- "HHHHH D-1) )
14

---

Under review as a conference paper at ICLR 2023
Since (Tr(H'D D )-H = Tr
(T((dTr(H)
(dTT(HH)) SSH)
d(S)): we have
ds
d'Ir H D SH) D HH Diag (D SHH D D
dS
For other terms in fs(S), the gradients with respect S can be easily computed. Finally, obtain
- (S A) > (D-'HH -Diag (D-'SHH") D= 1)) + 2u2S.
B.2 ON COMPUTATION OF THE PROXIMAL STEP
Lemma 5. Given a matrix M E RNN, we have
prox x] H[(() (M) = min [n, - x11]))
(10)
where ReLU(X)= ma
Proof. The proximal step Eq.
10
can he rewritten as the following optimization problem:
minimize SES
S - M + |||||
(1I)
It is easy observe that Problem 11] is decoupled over different elements in matrix S. Therefore, each Sij with =, problem:
can be optimized individually by solving the following optimization
minimize 058.51
(s,()))) = S M,y + |Syll
(12)
According to Eq.
(10
we have
S min {1,
min
ReLU (M.j - -k)}
1 K S Mij
Mij - K Mij <1*k
My k.
Then, Lemma can be proved by showing that for i, = ....... N, S is the optimal solution for Problem (12). The optimality of Sjz can be validated by verifying the optimality condition, i.e., there exists a subgradient vé E 0hg (St,) such that
( S 20
for all 0 < Siy 1. Observe that the subdifferential of h.s (Sty) is computed as follows:
SSij Mij + k Sij > 0 SSi My + KE
Ohiy(S::)
S 0
where can be any constant satisfying -1 S < 1. Then, the subdifferential Oh (St,) is given by
1 Mij + K
1 M,j
(S:y)
0
K Mj <1
-Mij Re
Mi k.
In the following, will show that the optimality condition holds for each of the above cases.
For 1 - k. S MyS, we have St = and de Mij + k S 0. Since S.j 1, we can get
(S.j - -St))
2. For S My 1 + have v/ 0 and hence, (S SJ₂) 0 for all 0 S S 1.
3. For M2 K, have S 0 and z -My + with being any constant satisfying
-1 E < 1. Thus, we can choose 1, which leads to vp >> 0. Since S.j 2 O, we can get
(S St 0.
15

---

Under review as a conference paper at ICLR 2023
In conclusion, there exists subgradient v They (St,) such that (S,), S 2 0 for all 0 Sty 1, based on which the optimality Eq. (10) is validated and the proof is completed.
Based on the result in Lemma 5 by choosing
S 7/2 VS (S(K)) and K = 722/11 we get the
analytical expression for the proximal step in Eq. follows:
((++1) = min ReI.U S (k) V)s(((()) 72/11 11 }
which suffices to perform the soft-thresholding operation and then project the solution onto the constraint set S.
C PROOF OF THEOREM 4 (CONVERGENCE OF ASMP)
In this section, we will first prove that the objective function at the H-block optimization problem and the smooth part of the objective function the S-block optimization problem are L-smooth. Then we give the conditions to ensure convergence of ASMP.
Denote SH (H) the objective function the H- optimization problem, i.e.,
fH (H) | - + AIr (H' H)
The L-smoothness of fH (H) demonstrated in the following lemma.
Lemma 6. Function fu (H) is L-smooth with LH + 4X, i.e. for any HI, H2 E RNM the
following inequality holds:
[H,, - V H2) S LH H. -H2
Proof. First observe that
VV (H,) fx (H2)lFF
|2 X) 2 H
(2 XX H2)
=2 + AL,w) (H1 H2)l1r
<2 ||T AL ll2 HH - -H2lFF
Lemma 7 (Chung 1997). , The largest eigenvalue of random walk normalized Laplacian matrix Lyw is less than or equal to 2, i.e., [rw ll2 I
Based on Lemmal we can conclude that
|| ( ( S 4X) 4X) |H H2llr
Therefore, function (H) L-smooth with Lи = 2 + 4A and the proof is completed
With fs defined in Eq. 9 the T-smoothness of fs is deomnstrated in the following lemma.
Lemma 8. Function fs(S) is L-smooth with I.g 22 + 2/12 + N² + 22 /NBB for
any S1, S2 N*N, the following inequality holds:
(S,ss ffs((2))l= I Ls ||S| - S2llF.
Proof. Denote D₁ Diag (S,1) and D2 Diag (S,1) as two degree matrices corresponding to S and S2. We have
(Si) (S2))))
27 (S1 - A) + 2p AD TH ADiag (D, ' HH DJ') 1
- -(27 (27(S2 A) + 2p252 AD; A HH ADiag SD HH T D. 17)
52y 2μ22 |S] -S2lp + (D- -
|F
(13)
Diag I
DJ D SH D 1
< (2 + 2p²) |S| - -S2llp HH ||, |D. -D
+ Av
D HH D, -D,'S D
16

---

Under review as a conference paper at ICLR 2023
To derive the Lipschitz constant of (S), we first present several useful lemmas.
Lemma 9. Under Assumption that the norm of node feature vectors upperbounded, i.e.
H.
S
B, we have
HH
112
HH
ΣΣ 1=1=1
H
ΣΣ B NB².
Lemma 10. Given and = Diag (S1), under Assumption that the diagonal elements of D
is lowerbounded by positive constant, i.e, min; Da 0 == -,.... N, we have
N
N
S Di
2
N c
D |- - D DD-
Lemma 11. Given S₁, S S. D1 = Diag (S,1), and D, = Diag (S21), under Assumption
3 that the diagonal elements of the degree matrix is lowerbounded by positive constant, i.e.
min; Da = c for l..... N, we have
|D - D2
S 6
N - -
(14)
and
1
1 Nº) |S| - S2llF
D S1 - D.
S2
(15)
Proof. It can be observed that
D Dile: D2ls 2
|D
D 11
Dile D2la
2
S2 -1a2l;
max 1.....
|S
S21lF
which proves Eq.
14
Based on Eq.
14 we further have
D S D2 b
S2112
D P7'S2/11
< D ' + DT S2 D2-" S211
|D |S| Sallp |S2ll2 D D l|p
| 1|2 [S -S2lr + +N | - -D
+ N2 || S21le
c
through which the proof is completed.
Based on Lemma and Lemma the second term in Eq. 13) ie.. A HH |D, D 1| F' can be upperbounded as follows:
A HH
Dj
D2 11p
N²
S S2l1p
(16)
c
For the third term in Eq.
we have
N
D
HH
D D SS D ||
=\VN
D
SH
D D D + +D S D DD S,HH D lp
SXVN
S (D_ - -Dz') +AVN (D- 's D (s, HH D
<AVN
[D
| HH P [ -D," + A D
D S HH || D 1l,-
17

---

Under review as a conference paper at ICLR 2023
Based on Lemma
Lemma 10 and Lemma 11 get the following result:
[1+ 222 A
Av Dj HH Di"
-D S, D2 1|r
- NVNB
[S] - -S2llr (17)
Substituting the results in Eq. 116 and Eq. 17 into Eq. 113 gives
[V ffs(S))ll
27 + 242
2
No
B²
(1 + N2) x
Nv NVNB3)
||S -S2lFp
c²
2X
2y 2p (1 - N W N)
N B
|S| - -211F
Therefore, function fs(S) is L-smooth with Lg 27 + 2pu proof is completed.
22 N3 N VNB2 and the 2 N
Based on the results in Lemma 6 and Lemma L-smooth. To ensure the monotonically decreasing property (ASMP). the step sizes must satisfy (Parikh and Boyd 2014):
conclude that fH (H) and (s(S) are both
2
0 7 < Lu 1 and 0 <<> 12
<
L.s
7 12 (1 (
Under such condition, the convergence of (ASMP) a first-order stationary point of Problem can be readily obtained based on the results for alternating proximal gradient descent method in Bolte jet al. (2014); Nikolova and Tan (0077) with convergence rate
inf 12K
{ [[(
( ||
|(* pK (p(HO) (H''S)))
(18)
where p = min 1. Lx 1
2 1x) and p (H, S) represents the objective function in Eq.
D DISCUSSION ON THE JOINT OPTIMIZATION APPROACH
In this paper, have used the alternating optimization approach to induce the ASMP scheme, while another natural idea is to apply a joint optimization approach for Problem (4). In this section, we will show that the joint optimization approach actually is inferior compared the alternating one.
since joint optimization would lead to slower convergence, which motivates the use of alternating optimization in ASMP.
We define the smooth part of the objective in Problem as
H. S) H X S S A XIr (H H, + μ2 ||S||
The L-smoothness of f (H, S) is deommstrated in the following lemma.
Lemma 12. Function f (H, is L-smooth with L = max {v (V D3 + (1 N (N
L3 + (1 1 NB i.e., for any H1, H2 R and S1 E NNN the following
inequality holds:
(H) V (H2, 1 LV H H2ll : + || - Sz
Proof. Observe that
WHf S
-
WHf S2)
(H (Hf S.) ([VH((H,
=IVnn/HH,,S)) V Vs/
S2)
(19)
+ {(V - (H, Vz, - SH2.
<Lg [H, -H- + -
+ (HV VH/(H, S2) V (H,
18

---

Under review as a conference paper at ICLR 2023
where the Lipschitz constants Lи and Ls are given in Lemma 6 and Lemma 8
In the following, we will derive the upper bound for the third and the fourth term in Eq. 19 Based
on Lemma II the term VHf {1 V (H, S2)llp can be upperbounded follows:
|V [ ([ S1} V H S2)llF
2| (I - Di S1) H - 2A (I - D2 S22) H
(20)
<2> DJ - D5 H1|l
<(1 + 1 Nº) 11+=~9
VNB |s| -S21FF
(21)
Besides, for the forth term, we have
[V, S1) ( S
Si)llF
< <||AD] H H2H:) XDiag (D H - H, Dj
<> D |1 H. - H2HH || + AvN D S H - H.H || D 11
According to Lemma 10 have
Vs/(H, (s/(H2, s (1+ NVN) X H. H.H FF
Then, we can get
Vss/
2,
-(1 +1+ NVN
H H + H - H2H, lFF
<(1+ NVN)
( H H H H H2ll2)
(22)
<(1 NVN
( || + ||H2211))
[H] H2llF
2A
<(1 NVN
NBB
H H2llp
Substituting the results in Eq.
21 and Eq.
22 into Eq. 19 gives
VH [H,
V H (H2 S2)
H S1)
sf H,, S2)
L3 + (1+
4x
NB
H Hell + (L's + (1 N22= N2) NB²) ||S -S21
1
2412
C
Thus, function f(H, S) is L-smooth with
L2 + (1 NVVN 2 4X2
e² NB?, V L3 + (1+ - N2) N2) 2412
= max
c² NB²
(23)
through which the proof is completed.
This result in Lemma 12 indicates that the Lipsehitz constant L is larger than both Lu and Ls- Practical graphs are commonly large graphs; i.e., the number of nodes N would dominate the other constants T., i.e., e, X, and B. Therefore, if we use the joint optimization approach, the Lipschitz constant is larger than LH and Ls by a large margin.
After deriving the Lipschitz constant in joint optimization, we compare its convergence rate with the alternating optimization approach. Denote (H))), { above joint optimization approach. Following the results in Bolte et al. (2014); Nikolova and Tan (2017). the convergence property of the joint optimization approach also given Eq. (18) with 4.4 Theoretically, to guarantee the sufficient descent of the objective at each step, P can be chosen to be min that L >> max (LH, Ls) } according to Eq. (23), the alternating optimization approach is allowed to adopt a larger step size at each block than the joint optimization approach, resulting in faster convergence behavior of the sequence. Motivated by this fact, we develop ASMP based the alternating procedure rather than the joint one so that the resulting message passing structure contains fewer layers to achieve the similar even better numerical performance compared to the joint one.
} ((*)) as the sequence generated by the
Lu 1 Ls } in the alternating optimization approach. Due to the fact 2
1
19

---

Under review as a conference paper at ICLR 2023
E ADDITIONAL EXPERIMENTS
E. RUNTIME ANALYSIS
The computation complexity of ASMP in order (N²d), where N is the number of nodes and is the feature dimension. This is larger than the complexity of simple graph convolution, which is in order O (Ed) with E' being the number of edges. To better understand the complexity of ASGNN and other baselines, provide a runtime comparison of different models. Specifically, we train different models for 200 epochs on Cora dataset under nettack with one perturbation per target node and the averaged runtimes from ten trials are shown in the following table.
Table 4: Runtime (in seconds) for 200 epochs of training. GCN-Jaccard GCN-SVD Pro-GNN GNNGuard
Model
GCN
Elastic GNN
ASGNN 42.06
Time
1.44
2.00
1.56
193.34
36.68
28.89
From the table, we can see that although ASGNN requires more computation time than GCN, GCN-Jaccard, and GCN-SVD, it is much faster than Pro-GNN and the complexity of ASGNN is comparable GNNGuard and Elastic GNN.
E.2 THE LEARNED COEFFICIENTS IN ASGNN
To better understand how different terms in the joitn node feature learning and graph structure learning objective, we provide the learned ASGNN coefficients on Cora dataset under targeted attack below.
Table 5: Learned coefficients of ASGNN on Cora under targeted attack
Ptb. number
X
f41
U22
7/1
7/2
8.1085
0.1674
0.3808
0.4359
0.0441
0.0035
8.3985
0.3440
0.1673
0.3802
0.0365
0.0026
2
8.3891
0.3263
0.2060
0.3990
0.0382
0.0025
8.4248
0.1972
0.2003
0.3442
0.0369
0.0023
8.3735
0.0908
0.2199
0.4070
0.0368
0.0017
5
8,4753
0.1246
0.2005
0.3061
0.0381
0.0029
From the table, we can see that the value of À is much larger than other coefficients. Besides, the value of the coefficients do not vary much under different perturbation numbers, indicating the importance of different terms are not affected by the perturbation number.
E.3 SPARSITY LEVEL OF THE LEARNED GRAPHS IN ASGNN
The sparsity level of the graphs (percentage of zero elements in the learned adjacency matrix) generated in the last layer of ASGNN are provided below. Note that the sparsity level can be tuned by constraining the learning space of μ1. For example, we can fix μn to be large value, which will lead to sparser graphs.
Table 6: Sparsity level of the graphs leant in ASGNN.
Dataset
Cora
ACM 89,40 + 0.95 78.54 + 12.53 46,56 + 3,24
Citeseer
Cora-ML
Sparsity level (%) 77.27 + 18.39
E.4 CONVERGENCE PROPERTY OF ASMP IN PRACTICE
According to Theorem 4 the convergence of ASMP is guaranteed with proper choices of step sizes. Since the step sizes are set to be learnable parameters, we provide an additional experiment to evaluate the convergence of ASMP with learned step sizes empirically.
20

---

Under review as a conference paper at ICLR 2023
Cora
0.8
0.7
1.0
Citeseer
Objective
0.6
Cora-ML
0.8
Objective
0.4
0.2
10
12
14
16
Number
Figure The objective value in Problem during ASMP.
To evaluate the convergence property of ASMP with learned step sizes, we conduct experiments on Cora, Citeseer, and Cora-ML. datasets at 25% perturbation rate under meta-attack. Specially, train a 4-layer ASGNN model and observe that the learned step sizes do not satisfy the condition in Theorem 4 In the following, we investigate the empirical convergence property of ASMP. Since we use recurrent structure in ASGNN, i.e., the step sizes used in different layers are the same, we are able to extend the trained 4-layer ASGNN model to a deeper one. The values of the objective function in Problem (4) in different layers are showcased in Figure where the objective values are normalized by dividing the objective value in the first layer. From Figure [] we can find that ASMP with learned step sizes monotonically decrease the objective function value during the message passing process. Note that although the monotonic decreasing property does not hold in 16-18 layers the Cora-ML dataset, this may be mainly due the fact that the step sizes learned only based on a 4-layer model. The results indicate that although the learned step sizes do not satisfy the condition in Theorem 4 they still ensure the monotonic decrease of the objective function value in practice.
21


Reviews:
[{"review_id": "gDOMqHFCIaC", "reviewer": "Reviewer_tSZb", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "The paper deals with building robust graph learning methods not susceptible to adversarial attacks. Existing methods learn the structure of graph either by preprocessing the graph structure or by parametrically learning the graph adjacency. In this paper, the authors propose to simultaneously learn the graph structure as well as to use it for message passing iteratively. They call it message passing with adaptive structure (ASMP), which is shown as a way of doing proximal gradient descent for simultaneous denoising of graph signal and graph structure. Experimental results are provided to show the usefulness of the approach.", "summary_of_the_review": "The overall idea of adaptively learning graph structure with message passing seems nice and well-developed. However, I am not fully aware of the related works and hence, not clear on the degree of novelty and significance of the results. Hence, I'm less confident. Therefore, I'm going with weak acceptance.", "strength_and_weaknesses": "### Strengths:\n1. The paper is well-motivated to handle the noise in graph structure with simultaneous learning of graph structure with features.\n1. The idea of adaptively learning the graph structure iteratively is appealing.\n1. Experimental results show that the method is promising. However, improvements on most datasets is only marginal.\n\n### Weaknesses:\n1. I do not understand the usefulness of having ‘different structure’ in each layer. More plausible to me is that the with adaptive graph structure, it gets progressively better and not just different. \n1. Why do authors use $L_{rw}$ and not $L_{sym}$. Is there any reason which makes it better? Experimental analysis to study the difference would be helpful as well.\n1. The paper can also be strengthened with further ablations. What are the learnt values of ASGNN coefficients which give the best results? This would be helpful to see the terms affecting the performance.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IG2FcPTjSwg", "reviewer": "Reviewer_Qd9P", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The authors propose ASGNN, a robust GNN architecture. ASGNN learns a \"cleaned\" adjacency matrix as well as feature matrix per message passing layer with the goal of removing adversarial perturbations from the graph. The message passing procedure is framed as an optimization problem, and the individual message passing steps are proximal gradient steps. The authors present experimental results on well-known datasets from the literature.", "summary_of_the_review": "The paper is a solid piece of work developing a robust GNN architecture. The presentation is clear and easy to follow. There are some key limitations of the work that prevent me from recommending acceptance (see details above):\n* Missing the GNNGuard baseline\n* Lack of adaptive attacks.\n* Only reports results on small datasets, no runtime/ complexity information or ablation study results provided.\n", "strength_and_weaknesses": "Strengths:\n* Framing the structure learning as an optimization approximately solved via the message-passing procedure itself appears novel and is interesting\n* The presented results suggest that the method is effective at defending against existing attack methods.\n* The presentation of the work is clear and easy to follow.\n\n\nWeaknesses:\n* The authors do not evaluate their defense against adaptive attacks designed to circumvent their defense\n* The comparison is missing an important baseline with GNNGuard [Zhang and Zitnik, 2020].\n* The authors only evaluate their method on small datasets.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "BRYhZfBIN20", "reviewer": "Reviewer_sBNe", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The major contribution is the message passing scheme with the adaptive structure that enables learning different propagation structures for different GNN layers. The proposed method ASGNN is one of the graph structure learning methods and the improvement of this work in terms of motivation is marginal. \n", "summary_of_the_review": "The motivation of this work is not quite novel. And the adaptive structure assumption increases the complexity of the proposed model. In a word, the proposed ASGNN brings performance improvements, but the complexity of this model also makes it hard to apply to large-scale graph data.", "strength_and_weaknesses": "Strength:\n1. It’s a generalized framework, achieving conduct message passing over different graph structures at different layers.\n2. In most experiments, it achieves the best results. \n3. The proposed update scheme has good theoretical support.\n\nWeaknesses:\n1. The authors claim that the message passing scheme of ASGNN is ‘interpretable’. But relevant experimental results are not given. \n2. This paper lacks a complexity analysis of the proposed model, considering the proposed ASGNN is trained to learn different propagation structures on each GNN layer.\n3. The challenges and innovation of introducing the adaptive structure are not clear.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject