summaries: This paper extends the definition of the hidden subnetworks in randomly initiated neural networks. The new notion of subnetworks, namely the disguised subnetworks, apply a transformation on the hidden subnetwork weights to obtain final weights (a posteriori finding the hidden subnetwork).   Mathematically speaking, the main decision variable of the underlying optimisation problem of finding “hidden subnetworks” is the so-called masking variable that is a binary vector, the variable that decides which components of the randomly initiated weights will be zero, constrained to a desired level of sparsity. On the other hand, the underlying optimisation problem of “disguised subnetworks” has an additional variable U that applies a transformation on the set of weights after being ‘sparsified’. The selection of U = I, for I being the identity transformation, recovers the problem of hidden subnetworks, showing that the latter is a generalisation.  The author(s) present a heuristic algorithm that solves the forenamed optimisation problem. The idea is to first find a solution for the masking variable where (i) U = I is taken, (ii) the objective function is independent of a training set. Afterward, the algorithm proceeds by solving the problem for U given the solution of the previous step, where the space of U is restricted to the class of transformations where only sign-flips are allowed. If we think of the above solution process as a two-phase problem, the author(s) use the literature on sparse neural networks for the first phase and use the literature on binary neural networks for the sign flipping phase.

summaries: Optimizing sparse neural networks is an important topic due to their computational and space savings.  Building on the work of the lottery ticket hypothesis, others have shown there exist hidden subnetworks within randomly initialized NN that have good performance. The authors extend this definition to disguised subnetworks, which contain hidden subnetworks as a subclass. Moreover, the authors present a novel combination of existing methods  into a single algorithm they call Peek-a-Boo (PaB) which can efficiently find such networks.

summaries: This paper proposes the idea of a "disguised subnetwork", which are hidden random subnetworks that can be transformed into a well-performing subnetwork. The paper introduces PaB as a way to uncover these subnetworks, by first searching for a mask over the random weights using pruning-at-initialization techniques, and then learning a transformation on the subnetwork. The paper further shows that this PaB process can be efficiently implemented, offering significant advantage over prior work.

summaries: This paper presents an algorithm named peek-a-boo (PaB) to optimize network pruning (at initialization) and optimization (limited within flipping the sign of weights). This setting has not been studied by prior works. A two-step algorithm was designed -- pruning first, optimization second. Experiments show competitive performance compared to prior methods with similar optimization complexity.

abstractText: Sparse neural networks (NNs) are intensively investigated in literature due to their appeal in saving storage, memory, and computational costs. A recent work (Ramanujan et al., 2020) showed that, different from conventional pruningand-finetuning pipeline, there exist hidden subnetworks in randomly initialized NNs that have good performance without training the weights. However, such “hidden subnetworks” have mediocre performances and require an expensive edge-popup algorithm to search for them. In this work, we define an extended class of subnetworks in randomly initialized NNs called disguised subnetworks, which are not only “hidden” in the random networks but also “disguised” – hence can only be “unmasked” with certain transformations on weights. We argue that the unmasking process plays an important role in enlarging the capacity of the subnetworks and thus grants two major benefits: (i) the disguised subnetworks easily outperform the hidden counterparts; (ii) the unmasking process helps to relax the quality requirement on the sparse subnetwork mask so that the expensive edge-popup algorithm can be replaced with more efficient alternatives. On top of the concept of disguised subnetworks, we propose a novel two-stage algorithm that plays a Peek-a-Boo (PaB) game to identify the disguised subnetworks with a combination of two operations: (1) searching efficiently for a subnetwork at random initialization; (2) unmasking the disguise by learning to transform the resulting subnetwork’s remaining weights. Furthermore, we show that the unmasking process can be efficiently implemented (a) without referring to any latent weights or scores; and (b) by only leveraging approximated gradients, so that the whole training algorithm is computationally light. Extensive experiments with several large-scale models (ResNet-18, ResNet-50, and WideResNet-28), on CIFAR-10/100 datasets, demonstrate the competency of PaB over edge-popup and other counterparts. Codes will be released upon acceptance.

authors:
Yoshua Bengio
Nicholas Léonard
Aaron Courville

title: Estimating or propagating gradients through stochastic neurons for conditional computation

venue: arXiv preprint arXiv:1308.3432,

authors:
Jeremy Bernstein
Yu-Xiang Wang
Kamyar Azizzadenesheli
Animashree Anandkumar

title: signsgd: Compressed optimisation for non-convex problems

venue: In International Conference on Machine Learning,

authors:
Miguel Á. Carreira-Perpiñán
Yerlan Idelbayev

title: learning-compression” algorithms for neural net pruning

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Tianlong Chen
Jonathan Frankle
Shiyu Chang
Sijia Liu
Yang Zhang
Zhangyang Wang
Michael Carbin

title: The lottery ticket hypothesis for pre-trained bert networks, 2020

authors:
Matthieu Courbariaux
Itay Hubara
Daniel Soudry
Ran El-Yaniv
Yoshua Bengio

title: Binarized neural networks: Training deep neural networks with weights and activations constrained to+ 1 or-1

venue: arXiv preprint arXiv:1602.02830,

authors:
J. Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova. Bert

title: Pre-training of deep bidirectional transformers for language understanding

venue: In NAACL-HLT,

authors:
Erich Elsen
Marat Dukhan
Trevor Gale
Karen Simonyan

title: Fast sparse convnets

venue: In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition,

authors:
Utku Evci
Fabian Pedregosa
Aidan Gomez
Erich Elsen

title: The difficulty of training sparse neural networks

venue: arXiv preprint arXiv:1906.10732,

authors:
Jonathan Frankle
Michael Carbin

title: The lottery ticket hypothesis: Finding sparse, trainable neural networks

authors:
Jonathan Frankle
Gintare Karolina Dziugaite
Daniel M Roy
Michael Carbin

title: Stabilizing the lottery ticket hypothesis

venue: arXiv preprint arXiv:1903.01611,

authors:
Jonathan Frankle
Gintare Karolina Dziugaite
Daniel Roy
Michael Carbin

title: Linear mode connectivity and the lottery ticket hypothesis

title: Pruning neural networks at initialization: Why are we missing the mark

authors:
Xavier Glorot
Yoshua Bengio

title: Understanding the difficulty of training deep feedforward neural networks

venue: In Proceedings of the thirteenth international conference on artificial intelligence and statistics,

authors:
Yiwen Guo
Anbang Yao
Yurong Chen

title: Dynamic network surgery for efficient dnns

venue: In NIPS,

authors:
Babak Hassibi
David G Stork
Gregory J Wolff

title: Optimal brain surgeon and general network pruning

venue: In IEEE international conference on neural networks,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Koen Helwegen
James Widdicombe
Lukas Geiger
Zechun Liu
Kwang-Ting Cheng
Roeland Nusselder

title: Latent weights do not exist: Rethinking binarized neural network optimization

authors:
Cristian Ivan
Razvan Florian

title: Training highly effective connectivities within neural networks with randomly initialized, fixed weights

venue: arXiv preprint arXiv:2006.16627,

authors:
Qing Jin
Linjie Yang
Zhenyu Liao

title: Adabits: Neural network quantization with adaptive bitwidths

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Yann LeCun
John S Denker
Sara A Solla
Richard E Howard
Lawrence D Jackel

title: Optimal brain damage

venue: In NIPs,

authors:
Namhoon Lee
Thalaiyasingam Ajanthan
Philip Torr

title: SNIP: SINGLE-SHOT NETWORK PRUNING BASED ON CONNECTION SENSITIVITY

authors:
Ning Liu
Geng Yuan
Zhengping Che
Xuan Shen
Xiaolong Ma
Qing Jin
Jian Ren
Jian Tang
Sijia Liu
Yanzhi Wang

title: Lottery ticket implies accuracy degradation, is it a desirable phenomenon

venue: arXiv preprint arXiv:2102.11068,

authors:
Eran Malach
Gilad Yehudai
Shai Shalev-Schwartz
Ohad Shamir

title: Proving the lottery ticket hypothesis: Pruning is all you need

authors:
Ari Morcos
Haonan Yu
Michela Paganini
Yuandong Tian

title: One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers

venue: In NeurIPS,

authors:
Laurent Orseau
Marcus Hutter
Omar Rivasplata

title: Logarithmic pruning is all you need

authors:
Ankit Pensia
Shashank Rajput
Alliot Nagle
Harit Vishwakarma
Dimitris Papailiopoulos

title: Optimal lottery tickets via subsetsum: Logarithmic over-parameterization is sufficient

venue: arXiv preprint arXiv:2006.07990,

authors:
Vivek Ramanujan
Mitchell Wortsman
Aniruddha Kembhavi
Ali Farhadi
Mohammad Rastegari

title: What’s hidden in a randomly weighted neural network

authors:
Hidenori Tanaka
Daniel Kunin
Daniel LK Yamins
Surya Ganguli

title: Pruning neural networks without any data by iteratively conserving synaptic flow

venue: arXiv preprint arXiv:2006.05467,

authors:
Chaoqi Wang
Guodong Zhang
Roger Grosse

title: Picking winning tickets before training by preserving gradient flow

authors:
Yue Wang
Ziyu Jiang
Xiaohan Chen
Pengfei Xu
Yang Zhao
Yingyan Lin
Zhangyang Wang

title: E2-train: Training state-of-the-art cnns with over 80% energy savings

authors:
Mitchell Wortsman
Vivek Ramanujan
Rosanne Liu
Aniruddha Kembhavi
Mohammad Rastegari
Jason Yosinski
Ali Farhadi

title: Supermasks in superposition

authors:
Haoran You
Chaojian Li
Pengfei Xu
Yonggan Fu
Yue Wang
Xiaohan Chen
Richard G Baraniuk
Zhangyang Wang
Yingyan Lin

title: Drawing early-bird tickets: Towards more efficient training of deep networks

venue: arXiv preprint arXiv:1909.11957,

authors:
Hattie Zhou
Janice Lan
Rosanne Liu
Jason Yosinski

title: Deconstructing lottery tickets: Zeros, signs, and the supermask

heading: 1 INTRODUCTION

text:
Recent years have seen substantial efforts devoted to scaling neural networks (NNs) to enormous sizes (He et al., 2016; Devlin et al., 2019). Parameter-counts are frequently measured in billions rather than millions, with the time and financial outlay necessary to train these models growing in concert. Sparse NNs, whose large portions of parameters are zero, have been studied to address those gaps, saving storage, memory and computational costs. Conventional approaches first train dense NNs, and then prune the trained NNs to high levels of sparsity (Han et al., 2015; Guo et al., 2016). Those methods significantly reduce the inference complexity yet cost even greater computational resources and memory footprints at training.
An emerging field has explored what roles sparsity can play in neural networks, spawning different directions of research. One of them follows the typical pruning-and-finetuning pipeline in conventional pruning methods, but explored the prospect of directly training smaller, sparse subnetworks in place of the full models without sacrificing performance. One key idea is to reuse the sparsity pattern found through pruning and training a sparse network from scratch. The seminal work of the Lottery ticket hypothesis (LTH) (Frankle & Carbin, 2019) demonstrated that standard dense NNs contain sparse matching subnetworks (called “winning tickets”) capable of training in isolation to
full accuracy. In other words, we could have trained smaller networks from the start if only we had known which subnetworks to choose. Additionally, other works also showed that sparsity might even emerge at initialization, before training ever starts and with minimal-to-no dependence on data, such as SNIP (Lee et al., 2019), GraSP (Wang et al., 2020), and SynFlow (Tanaka et al., 2020). Those methods suggest a tantalizing possibility of “pruning-at-initialization” for finding sparse subnetworks without overhead, even though it remains under debate whether their found subnetworks have inferior quality to lottery tickets found with IMP (Frankle et al., 2020). The consensus seems to be that, a “good” sparse topology can be very crucial and informative for successful training.
Another set of efforts (Zhou et al., 2019; Wortsman et al., 2020) suggest that “masking (pruning) is training”, e.g., by strategically zeroing out randomly initialized weights, the network can reach far-better-than-chance accuracy. (Ramanujan et al., 2020) found that from a “sufficiently overparameterized” dense NN with random initialization, there exists a hidden subnetwork that achieves competitive accuracy (w.r.t. to the fully trained dense NN), without any training on the remaining weights. Its theoretical proof was presented by (Malach et al., 2020) for the first time and followed by (Pensia et al., 2020; Orseau et al., 2020). (Ivan & Florian, 2020) tried an alternative training scheme, by only flipping the weight signs in a dense NN while preserving their initialized magnitudes. All aforementioned works suggest that it is possible to only update the connectivity patterns without changing the magnitudes of the weights to achieve decent performance.
However, many of them only tried on rather small NNs (Zhou et al., 2019; Ivan & Florian, 2020), with notable accuracy drops compared to full gradient-based training. This is intuitively understandable because NNs’ expressiveness will be strictly constrained if pruning is the only allowable operations during training. Under such rigid restrictions, to obtain hidden subnetworks with acceptable performance requires high-quality connectivity patterns with appropriate pruning ratios. Ramanujan et al. (2020) found that the hidden subnetworks with either too high or too low pruning ratios have poor performance. What is even worse is that the tedious optimization needed for identifying the hidden subnetworks. All of those works used some form of latent weights or score functions for all NN weights, which are cast into binary decisions to mask their corresponding weights or not during forward pass and are trained during backpropagation, e.g., the edge-popupalgorithm in (Ramanujan et al., 2020). Those latent weights or scores make their training even more costly than training standard NNs, and the non-differentiable binarization operation may also inject instability.

heading: 1.1 OUR CONTRIBUTIONS AND RATIONALES

text:
Inspired by the recent advances in sparse NNs and the philosophy of “masking is training”, this paper first proposes the concept of disguised subnetworks in randomly initialized NNs, as the extension to the “hidden subnetworks” found in (Ramanujan et al., 2020). At its name suggests, a disguised subnetwork is hidden as a sparse subnetwork in a dense NN at its random initialization. This subnetwork, without achieving good performance at the beginning, can have its “disguise” unmasked by learning some simple transformations on the remaining weights to lower the training loss. To preserve the randomness in the subnetwork at the best, we only consider transformations that do not alter the magnitudes of the remaining weights, such as shuffling and sign flipping. In this work, we will focus on sign flipping specifically.
We argue that the extra unmasking step in disguised subnetworks grants essential advantages over plain hidden subnetworks by significantly enlarging the expressiveness of the subnetworks. Such advantages immediately bring several benefits. Firstly, with much better capacity and expressiveness, disguised subnetworks can easily achieve superior performances compared with hidden subnetworks and thus have better scalability to larger NNs and datasets. Secondly, the searching of the sparse subnetwork and the following unmasking process can compliment each other for better performance, which relaxes the quality requirement on the sparse mask. This benefit enables us to replace the unstable and expensive searching algorithms in previous works with more efficient pruning algorithms. The rationale behind is that only learning transformations on randomly initialized weights cannot create sparsity that a trained NN often shows to possess (Zhou et al., 2019) while only pruning has too limited flexibility which can be drastically boosted by allowing for further weight processing.
Based on this reasoning, we propose a two-phase algorithm called Peek-a-Boo (PaB), which consists of the searching and unmasking phases involving two operations: (1) sparsifying a deep neural network with efficient pruning-at-initialization methods at its random initialization; (2) learning
to flip the signs of the resulting subnetwork’s remaining weights to lower the training loss. Note that we never modify weight magnitudes after being initialized aside from removing weights. PaB absorbs and improves the idea “masking is training” (Zhou et al., 2019), by unifying the two streams of ideas: pruning (i.e., applying {0,1} masks to weights) and flipping signs (i.e., applying {-1,1} masks). Moreover, for its second stage of unmasking, we optimize weight signs without extra latent weights or scores (Helwegen et al., 2019). Such optimization method frees us from using the heavy latent parameters nor the non-stable straight-through-estimators (STEs), which were assumed by all previous methods. We further demonstrate that an even more efficient implementation could be achieved by using low-cost gradient predictors for approximated gradients (Wang et al., 2019), as PaB might be tolerant to “coarser” gradient information since we only flip signs.
Despite remaining as an empirical exploration, the success of PaB also urges theoretical reflections on whether sparse NNs have to follow the same optimization strategies as the dense ones, or whether they can utilize new optimizers as simple as sign flipping. On one hand, pruning can often cause more difficult optimization landscapes for gradient descents, as training a sparse NN essentially becomes a constrained and non-smooth optimization problem (Evci et al., 2019). On the other hand, assuming a good sparse mask is known a priori, the possible solution space has also been significantly reduced, which may suggest the existence of “shortcuts” to reach the optima in this shrunken space, such as the “solution locality” of LTH recently observed by (Liu et al., 2021).

heading: 2 RELATED WORKS

heading: 2.1 SPARSE NEURAL NETWORKS

text:
Pruning methods (Hassibi et al., 1993; LeCun et al., 1989) have witnessed great advances to reduce the increasing inference complexities of NNs. Magnitude-based pruning methods (CarreiraPerpiñán & Idelbayev, 2018; Guo et al., 2016; Han et al., 2015) have become mainstream due to their relative low overheads and good scalability to large NNs. However, they still hinge on the expensive train-prune-retrain cycles to restore performance, and do not lead to efficient training. LTH (Frankle & Carbin, 2019) discovers sparse subnetworks at random initialization that can achieve similar or even better performance when trained in isolation. The winning tickets are found by the computationally intensive iterative magnitude-based pruning (IMP), which involves tens of rounds of train-prune-retrain cycles. Rewinding was later found to be essential for stably identifying winning tickets in large networks (Frankle et al., 2019; 2020). (Morcos et al., 2019; Chen et al., 2020) studied the transferability of winning tickets between datasets and downstream tasks.
Zhou et al. (2019) made further interesting observations on winning tickets, discovering that preserving the original weight signs is essential to successfully training the tickets, and that the pruned weights have to be set to zero instead of being frozen at initial values. They concluded that “masking is training”, i.e., the masking operation tends to move weights in the direction they would have moved during training. Hence, simply applying an appropriate mask to the random initialization leads to reasonably good performance. The authors found such “supermasks” with both heuristics and Bernoulli sampler-based optimization. Their finding was empirically concurred by (Ramanujan et al., 2020) and theoretically supported by (Malach et al., 2020).
However, the original experiments in (Zhou et al., 2019) were restricted to NNs with a very small number of layers (e.g., Conv 4). Later work (Ramanujan et al., 2020) identified untrained subnetworks from Wide ResNet-50 as “mother NNs” on ImageNet that can match the performance of ResNet-34 (worse than ResNet-50). Yet that is very different from our (more ambitious) goal - pruning a subnetwork from the “mother NN”, and having it match the original performance of the “mother NN” by only flipping-based training. Moreover, their sophisticated algorithm relies on a set of real-valued latent weights (called “scores” associated with each NN weight), making their training essentially as expensive as full SGD.
Another line of works has arisen to investigate pruning NNs directly at random initialization. Examples include SNIP (Lee et al., 2019), GraSP (Wang et al., 2020) and SynFlow (Tanaka et al., 2020), all of which exploit the weight magnitudes as well as first- or higher-order information of NNs at the initial point. (Frankle et al., 2021) revisited these methods and observed that the naive magnitude-based pruning at initialization already plays as a strong competitor, with a side observa-
tion that delaying the pruning generally improves performance. All these algorithms train the pruned networks using the same standard SGD-type optimizers.

heading: 2.2 OPTIMIZATION BY SIGN FLIPPING

text:
The train-by-flipping scheme considered in this work is closely related to the optimization of binary neural networks (BNNs), whose weights are only +1/-1. Optimization methods over BNNs can be categorized into two types – training with and without real-valued latent weights. The former category (Bengio et al., 2013; Courbariaux et al., 2016) maintains and updates a set of full-precision weights for back-propagation while forward passes only utilize binary weights. The downside of this method is the extra memory and resource overhead in training. The second category eliminates latent weights and only learns the decision rules for flipping or not, based on certain training statistics. For example, Bop (Helwegen et al., 2019) keeps a running average of historical gradients, and flips a weight’s sign when its accumulated gradients surpasses a pre-defined threshold.
A more recent work (Ivan & Florian, 2020) studied the possibility of training NNs by only flipping the signs of the initialized weights, leaving the magnitudes unchanged. The authors proposed to update an extra set of latent parameters, whose signs determines the weight flipping decision throughout training. Their method struggled to scale up to large NNs, causing large performance drops. The potential reason behind this might be just as (Zhou et al., 2019) advocated, that zero would a particularly good value to set many weights to. In other words, weight sparsity may be a generally helpful inductive prior for well-trained NNs, which cannot be met by only flipping signs of weights. Besides, the training algorithm in (Ivan & Florian, 2020) also induces large overhead due to using full-precision latent weights and does not head towards efficient training. Moreover, neither (Ivan & Florian, 2020) nor any BNN optimization methods have considered the intersection of training-by-flipping and sparse NNs.

heading: 3 PEEK-A-BOO: SEARCH AND UNMASK DISGUISED SUBNETWORKS IN

text: RANDOMLY INITIALIZED NEURAL NETWORKS

heading: 3.1 DISGUISED SUBNETWORKS VERSUS HIDDEN SUBNETWORKS

text:
In this subsection, we formally define hidden subnetworks and disguised subnetworks in randomly initialized NNs, and show that the latter, as an extended class of subnetworks to the former, contain better subnetworks that can outperform those in the former.
Consider a neural network f(x;ω) parameterized by (vectorized) weights ω ∈ Rn for input x. We denote the randomly initialized weights as ω(0), and ω(t) as the weights after t steps of training. We denote a general transformation applied on the weights ω as U(ω) that takes any form. Definition 1. A hidden subnetwork in the dense neural network f(x;ω) is characterized by a binary mask m ∈ {0, 1}n and denoted as f(x;ω m), where represents the Hadamard product. A disguised subnetwork is defined as a transformed hidden subnetwork characterized by a binary mask m ∈ {0, 1}n and a weight transformation U(·), denoted as f(x;U(ω m))
Remark Here we omit the index for the number of training steps because we can take hidden subnetworks or disguised subnetworks at any time during training, while in this work our focus is on the subnetworks at random initializations, i.e., f(x;ω(0) m) and f(x;U(ω(0) m)). To identify the optimal disguised subnetworks at a certain sparsity level S, we need to solve the optimization problem below:
minimize U∈U, ‖m‖0=S
LD[f(x;U(ω(0) m))], (1)
where U is the collection of all possible weight transformations and LD is the loss function on dataset D. It is clear that the optimal disguised network achieves a minimum that is equal to or smaller than that achieved by the optimal hidden network, because the hidden networks are the special cases of disguised subnetworks if we constrain the weight transformation U to the identity mapping I . And the optimal hidden subnetwork is the minimizer of the following problem:.
minimize ‖m‖0=S
LD[f(x; I(ω(0) m))]. (2)
In this paper, we argue that constraining the weight transformation U to identity as in the hidden networks can significantly decrease the model capacity and thus degrade the performance, especially when n is large, i.e., the model is large or s is small, i.e., the model is highly sparse. In contrast, if we can directly solve (1), we can find disguised subnetworks with much better performance.
However, directly optimizing (1) is computationally intractable due to the high-dimensionality of the networks and the complexity of the collection of weight transformations. Therefore, we propose to approximately solve (1) by decoupling it into a two-phase process. In the first phase, we find a suitable mask m̂ to sparsify a deep neural network at its random initialization. We call it the searching phase. In the second phase, we learn the optimal weight transformation to further lower the training loss. We call it the unmasking phase. The whole process is formally formulated as:
m̂ ∈ argmin ‖m‖0=S R(f(x;ω(0) m)) (3)
Û ∈ argmin U∈U LD[f(x;U(ω(0) m̂))] (4)
Here R is a score function that measures the quality of the binary mask m for the network f with random initialization ω(0) in some metric. Different selections of this score function will lead to different pruning methods. To efficiently solve this two-phase optimization in (3) and (4), we propose Peek-a-Boo (PaB) framework.

heading: 3.2 PEEK-A-BOO: EFFICIENT SEARCHING AND UNMASKING

text:
We present the basic design options for the PaB framework. In the searching phase, we sparsify a neural network at its random initialization using a training-free pruning method. In the unmasking phase, we learn to flip signs of the remaining nonzero weights as the weight transformation U to lower the training loss.
Searching phase: training-free pruning. Our goal in the first step is to use pruning to find a sparse mask m̂, with two requirements. Firstly, the sparse mask provides a useful prior of “good structures” in the network for the flipping-based training that follows. Secondly, the pruning itself needs to be light enough to not incur overhead for training efficiency. Due to the second concern, we give up the expensive IMP (Frankle & Carbin, 2019; Zhou et al., 2019) and focus on the pruning-at-initialization methods (Lee et al., 2019; Wang et al., 2020; Tanaka et al., 2020; Frankle et al., 2021).
We choose SynFlow (Tanaka et al., 2020) over SNIP (Lee et al., 2019) and GraSP (Wang et al., 2020), because the latter two depend on the first-order and/or second-order information of the neural network to calculate the weight scores. To accurately estimate those, one needs to run through training samples. In comparison, SynFlow is data-free and only uses an all-one input.
Unmasking phase: flipping the non-zero weights. In the unmasking phase, we learn the optimal weight transformation in the form of sign flipping Us(ω) = ω s to lower the training loss. Here s is a {+1,−1} binary mask that we want to optimize. Allowing to flip the signs of the remaining nonzero weights, the unmasking phase significantly alleviates the limitation in model capacity. That is, one sparse NN of k non-zero elements can be augmented to 2k possible candidates, if sign flipping is enabled. However, it is computationally intractable to exhaustively search for the optimal vector. To approximately solve (4) with sign flipping transformation Us, we leverage a prior art called Bop from BNN optimization (Helwegen et al., 2019). As formulated in Appendix A, Bop selects what weights and when to flip their signs by taking into account the exponential moving average of historical gradients. Different from the edge-popup algorithm used by Ramanujan et al. (2020) and a similar method in (Ivan & Florian, 2020), Bop gets rid of additional latent weights, hence incurring more training overhead and deviating from our end goal of more efficient training. Bop also avoids the use of straight-through estimator (STE) during backpropagation, which is known to unstabilize the training.

heading: 3.3 FLIPPING USING CHEAP GRADIENTS: TOWARDS REAL COMPUTATIONAL EFFICIENCY

text:
The training-by-flipping scheme only seeks to optimize the sign configuration, not the the realvalued weights (they are fixed as initialized). Hence, an educated guess is that this scheme can tolerate “coarser” gradient information than standard training methods. This leaves decent room for
us to further reduce the training cost by replacing precise gradients with approximated ones. One way to implement this is to adopt a low-precision gradient approximation called Predictive Sign Gradient, which was shown to save computation on hardware (Wang et al., 2019).
PSG predicts the signs of the precise gradients. using the signs of approximated gradients calculated from the most significant bits (MSB). PSG only corrects its predictions when the approximated gradients are close to zero, e.g., implying a non-trivial chance of wrong predictions. Specifically, consider a one-layer neural network with input x, weight matrix ω and output y = ωx. During backpropagation, we receive gy = ∂L/∂y for the proceeding layer, and calculate the weight gradient gω = ∂L/∂ω = gyxT and the input gradient gx = ∂L/∂x = ωT gy . PSG replaces (x, ω, gy) in the above calculations with their bit-quantized versions (x̃, ω̃, g̃y), with bit-width (bx, bω, bg), and uses the resulting g̃ω = g̃yx̃T and g̃x = ω̃T g̃y as the approximated weight and input gradient. g̃x is further propagated to preceding layers to run the back-propagation.
In PaB, we use g̃ω itself instead of its sign, either in flipping with latent weights or flipping with Bop. This is because without changing the weight magnitudes, we only have two actions — to flip or not to flip. Too much training variance will be introduced if we directly use sign(g̃ω) to flip the weight signs, thus causing instability and difficulty in training. Moreover, we ignore elements in g̃ω that are close to zero, rather than correct them with precise gradient calculation. This can reduce the training cost and also help to smooth the training process. Gradients to be ignored are selected using an adaptive thresholding technique in (Wang et al., 2019). This behavior is discussed in Section 4.4. The full PaB framework is summarized in Algorithm 1.
Algorithm 1 PaB Efficient Training Framework
Require: Randomly initialized network f(x;ω(0)), dataset D = {xi, yi}Ni=1, loss function LD, sparsity S, threshold θ, total number of training steps T , PSG configuration [bx, bω, bg].
1: m← Prune(f(x;ω), S,D) with ‖m‖0 = S B Get the sparse mask by pruning 2: s(0) ← (1, . . . , 1); t = 0 B Initialize sign configuration and time step 3: while t < T do 4: g̃(t) ← PSG ( LD, f(x;ω(0) m s(t)), [bx, bω, bg] ) B Approximate gradient using PSG
5: s(t+1) ← Flip ( s(t), {g̃(i)}ti=1 ) B Flip signs using historical gradient information 6: t = t+ 1 7: end while 8: return f(x;ω(0) m s(T ))

heading: 4 EXPERIMENTS

heading: 4.1 MAIN RESULTS ON CIFAR-10/100

text:
Methods to compare. We compare our proposed PaB method with the standard SGD training for the dense network (Dense-SGD) and the edge-popup algorithm (Ramanujan et al., 2020). For the non-flipping training for pruned networks, we choose standard SGD and SignSGD (Bernstein et al., 2018) as the baselines. For the proposed PaB methods, we compare: (1) PaB-Latent, which first prunes the network and trains the unpruned weights using the flipping with latent weights method in (Ivan & Florian, 2020) 1; (2) PaB-Latent-PSG, the variant of PaB-Latent combined with PSG; (3) PaB-Bop, which trains the unpruned weights using Bop (Helwegen et al., 2019); and (4) PaB-BopPSG, the variant of PaB-Bop combined with PSG. We also introduce a variant of Dense-SGD as baseline called Dense-SGD-Short, where we cut down the training epochs of Dense-SGD to match the number of training BitOps of that in PaB-Bop-PSG.
We evaluate the performance of these PaB methods on the CIFAR-10 using large ResNet-18, ResNet-50 architectures, in contrast to previous papers on flipping based training (Ivan & Florian, 2020) and lottery tickets (Zhou et al., 2019) where their methods scale only up to 6-layer conv networks. In all experiments, we initialize networks using Kaiming Normal initialization (He et al.,
1The latest manuscript of (Ivan & Florian, 2020) just reported a new result on ResNet-18. However, their baseline accuracy number (90.45%) is much inferior to what is commonly used by the community (over 95% using this implementation). Their flipping algorithm ends up ∼3% accuracy drop on this baseline. Further, without access to their official codes for large models, we are not sure whether we could draw fair comparison with their results.
2016), prune to 90% pruning ratio using SynFlow for 100 iterations (Tanaka et al., 2020) at random initialization, and train over 200 epochs. For Bop, we start with adaptivity ratio γ = 10−3, which is decayed by 0.15 every 45 epochs, and use threshold τ = 10−6. For non-Bop methods and non-Bop weights, we use an initial learning rate of 0.1 and decay them by 0.1 at epoch 80 and 120. We use an initial learning rate of 0.01 for SignSGD as smaller learning rates are favored in (Bernstein et al., 2018). Results are presented in Table 1, including accuracies, model sizes and training BitOPs (in trillions) for each method and network. Huffman coding is used to encode the PaB models as described in Appendix D. We calculate training BitOPs following (Jin et al., 2020) instead of FLOPs because PSG involves low-precision computation. Several observations can be drawn from the results:
• As expected, the PaB framework results in impressive compression ratios (> 30x) on all models, thanks to the fact that flipping-based methods leave weight magnitudes unchanged, which can be restored easily using the same random seed.
• We see that PaB-Bop and its PSG variant are consistently better than PaB-Latent and the PSG variant. This shows the superiority of Bop-based methods over latent-weight methods (Ivan & Florian, 2020) in terms of the effectiveness when training sparse networks. We perceive this observation as an indication of the potential existence of even better sparse training methods than the Bop-based method that can exploit the sparse structure more effectively.
• The integration of PSG with PaB further reduces the training cost by significant margins, saving 82∼86% of the total BitOPs that is needed for training a dense counterpart.
• PaB-Bop-PSG performs comparatively well for ResNet-18/50, achieving 1.68% and 2.33% accuracy gaps respectively compared to SGD and even smaller gaps compared to SignSGD.
Results on wider networks Besides scaling ResNet-18 up to ResNet-50 in depth, we also show the scalability of PaB in width by training WideResNet-28 with a 10x width multiplier, on both CIFAR10 and CIFAR-100 datasets. As seen from the results shown in Table 2, PaB-Bop-PSG scales very well to WideResNet-28 on both CIFAR-10 and CIFAR-100. On CIFAR-10, PaB-Bop-PSG incurs a 1.24% gap compared to SGD and even outperforms SignSGD. Similarly on CIFAR-100, PaBBop-PSG incurs a 2.47% gap from SGD and performs similarly to SignSGD. The accuracy gaps of PaB on WideResNet-28 are even smaller than on ResNet-18/50, demonstrating that PaB scales well to wide networks, potentially due to better gradient flow in wider architectures. We omit PaBLatent results here because we fail to train PaB-Latent to reasonable accuracies for WideResNet-28, which, in addition to the observed gaps to PaB-Bop on ResNet-18 and -50, shows the superiority of Bop-based methods over flipping with latent weights.

heading: 4.2 COMPARISON WITH EDGE-POPUP ALGORITHM

text:
We compare PaB with the edge-popup algorithm proposed in (Ramanujan et al., 2020) to identify the hidden subnetworks in deep neural networks at their random initializations. We adopt two small networks, Conv4 and Conv62 used in (Ramanujan et al., 2020) and a larger network ResNet-18 for
2We follow the official implementation of the edge-popup algorithm but make slight modifications to the Conv4 and Conv6 networks by adding batch normalization layers to stabilize the training.
comparison. All models are trained on CIFAR-10. We apply PaB and edge-popup to the testing networks with pruning ratios 30%, 50%, 70% and 90%. Results presented in Figure 1 show that PaB consistently finds better disguised subnetworks than the hidden networks found by edge-popup algorithm, especially when the pruning ratios are hight.

heading: 4.3 COMPARISON WITH STATE-OF-THE-ART EFFICIENT TRAINING METHODS

text:
We compare PaB with two state-of-the-art efficient training methods, E2-Train (Wang et al., 2019) and EB-Train (You et al., 2019). E2-Train improves training efficiency by combining data dropping, model layer skipping, and gradient quantization, and EB-Train utilizes structured pruning and the early emergence of sparsity patterns. We train ResNet-18 on CIFAR-10 using all three methods with different efficiency-performance trade-offs.
As shown in Figure 2, PaB achieves better accuracyBitOps trade-off than E2-Train and EB-Train, especially when high training efficiency is demanded (small BitOps). The x-axis is the average BitOps for training one sample for one step. We present the detailed protocol for this comparison in Appendix.

heading: 4.4 ABLATION STUDIES ON PAB

text:
In this subsection, we conduct a complete set of ablation studies on the effects of important components in PaB. Due to space limit, we only present the ablation study on the most important two sets of hyperparameters in PaB, namely the hyperparameters for BOP and the hyperparameters that control the small gradient behavior in PSG. We leave the ablation studies on the pruning ratio, the
epoch during training at which pruning occurs, and the random distribution for initialization to the Appendix. We use ResNet-18 on CIFAR-10 as the testbed.
BOP Hyperparameters Different from PaB-Latent, which in nature still trains latent weights using SGD, PaB-Bop consists of two parts: the accumulation of historical gradients and a thresholding mechanism to select significant updates in the correct directions, controlled by adaptivity ratio γ and threshold τ , respectively, as formulated in (6). Therefore, we conduct an ablation study on γ and τ and present the results in Figure 3. We prune ResNet-18 networks with pruning ratio 90% using SynFlow and then train them on CIFAR-10 using PaB-Bop with different combinations of γ and τ . When γ is small, the latest gradient makes too small contributions in the accumulation to cause enough updates. In contrast, when γ = 0.01, Bop needs a larger threshold τ to reduce the training variance. The best combination is (γ, τ) = (10−3, 10−6).
Dealing with small gradients in PSG In the original PSG (Wang et al., 2019), when PSG obtains small gradient approximations (judged by a threshold θ), PSG corrects them with precise gradients using full-precision calculation. Here we study three different PSG behaviors in the framework of PaB: (1) PSG-All, where we take whatever gradient approximated; (2) PSG-Correct, the default behavior in (Wang et al., 2019), which corrects small approximated gradients with precise ones; and (3) PSG-Remove, which removes small approximated gradients. The accuracy results of applying PSG with these three different behaviors to ResNet-18 pruned by SynFlow are shown in Figure 4. Note that PSG-Correct/Remove reduces to PSG-All with zero threshold. The results show that PSGCorrect and PSG-Remove perform similarly at their best thresholds. Since PSG-Correct requires extra computation of precise small gradients, we prioritize efficiency and use the PSG-Remove behavior in all PSG experiments.

heading: 5 CONCLUSION, FUTURE WORKS, AND DISCUSSION OF SOCIETAL IMPACTS

text:
We study Peek-a-Boo (PaB) as a new minimalist approach to training dense networks at their random initializations without altering weight magnitudes. Inspired by the recent exploration of sparse NNs, PaB achieves high training efficiency and provides a natural lossless compression after training. While this work remains as a pilot study, we show it can already scale up to larger networks with competitive trade-off between accuracy and training efficiency. We hope that PaB will evoke more theoretical reflections on training.
One of our immediate future work will explore alternatives to the sign flipping operation as the weight transformation in the unmasking phase. For example, we can extend sign flipping with learnable scaling, or replace it with quantization. In another direction, while this paper mainly uses unstructured sparsity following the convention of pruning at initialization, we can explore how structured pruning (You et al., 2019) may fit in PaB for practical hardware acceleration. As another avenue, despite the traditional lack of hardware and software support for (unstructured) sparsity, new types of hardware accelerators continue to improve the performance of IMP-pruned sparse networks on current hardware. For example, in the range of 70%-90% unstructured sparsity, XNNPACK has already shown speedups over dense baselines on smartphone processors (Elsen et al., 2020).

heading: A BOP FORMULATION

text:
Bop (Helwegen et al., 2019) selects what weights and when to flip their signs by taking into account past gradient information. In particular, Bop accumulates the exponential moving average of historical gradients:
e(t+1) = (1− γ)e(t) + γ∇ωLD[f(ω(t))], (5)
where γ is called the adaptivity ratio. Bop flips weight signs when the moving average surpasses a certain threshold τ and aligns with the weights in direction:
w(t+1) = { −w(t) if |e(t)| ≥ τ and e(t)w(t) > 0, w(t) otherwise.
(6)
B PROTOCOL OF COMPARING PAB WITH E2-TRAIN AND EB-TRAIN
EB-train (You et al., 2019) is easier to control the computational costs and calculate its BitOps. EBTrain consists of three stages: (i) the searching stage where a dense model is trained with sparsity regularization applied on the scaling factors of the batch normalization layers; (ii) prune the filters when the convergence of the pruning mask is detected; (iii) continue training the pruned models. In the first stage, EB-Train has the same computational cost as a dense model, but only for a short period of training. After the pruning is performed in the second stage, we can easily calculate the reduced BitOps based on the layerwise pruning ratios induced by pruning. Such reduced computational cost will be sustained throughout the third stage. In the experiment shown in Figure 2, we change the pruning ratio in EB-Train to control the BitOps.
E2-Train Wang et al. (2019) is a more tricky baseline because it consists of three components - stochastic mini-batch dropping (SMD), selective layer update (SLU) and predictive sign gradient (PSG). We follow the setting of SMD ratio, i.e., the ratio of randomly dropped mini-batches during training and fix it at 50%. The BitOps reduction brought by PSG is decided by the bit-width of the most significant bits. We use the same 8-8-16 bit widths for inputs/activations, weights and gradients respectively as in (Wang et al., 2019) and use full-precision computations for the forward passes. We then change the computation budget in SLU to control the BitOps in Figure 2.
Although the computation reduction of PaB is fixed given the sparsity ratio and the bit-width configuration in PSG, PaB is orthogonal to stochastic mini-batch dropping and can be combined with it. Hence, we change the ratio of dropping mini-batches to control the BitOps of PaB-Bop-PSG in Figure 2.

heading: C ADDITIONAL ABLATION STUDIES

text:
Pruning time point. Although pruning at initialization has shown success at training sparse networks, (Frankle et al., 2021) identify that pruning at different time points after initialization could further improve the performance of these networks. Using a fixed pruning ratio of 90%, we train ResNet-18 on CIFAR-10 and observe the effects on the test accuracy of delaying pruning to different training points from epoch 0/200 to epoch 60/200. Figure 5a shows the performance of our nonflipping baselines and PaB methods as the pruning epoch varies. Different from the observations in (Frankle et al., 2021), while slight increases in accuracy can be observed with delayed pruning, the effect is quite small at the scale of this experiment. The reason might be that we fix the total number of epochs whenever we perform pruning, while (Frankle et al., 2021) goes through the whole training process after pruning. With efficient training in mind, we maintain pruning at initialization in subsequent experiments since delaying pruning after initialization would require expensive training of dense networks before pruning.
Pruning ratios. We also evaluate the performance of our PaB methods against our baselines at different levels of sparsity. Figure 5b shows the test accuracies from training ResNet-18 on CIFAR10 at varying pruning ratios from 0% to 90%. Not surprisingly we see a decreasing tendency in test accuracy when we gradually increase the pruning ratios for all methods, especially going from 80% to 90%. However, PaB-Bop and its PSG variant are more robust to high pruning ratios, while
PaB-Latent and PaB-Latent-PSG have obvious degradation at 90% pruning ratio. Beyond 90%, the test accuracy starts to drop noticeably, and the resulting sparse networks becoming untrainable for all training methods due to layer collapse. By default hereinafter, we fix the pruning ratio to 90%.
Ablation on initialization. In previous experiments, we use Kaiming Normal distribution for random initialization. We also try Kaiming Uniform and Xavier Normal (Glorot & Bengio, 2010) distributions as alternatives. As shown in Table 3, there is generally little variation in performance across initialization methods, but we are able to achieve the best results across all PaB methods from PaB-Bop-PSG initialized using the Kaiming Normal distribution. We can also see that all PaB methods consistently perform better under Kaiming Normal initialization than under Xavier Normal initialization.
Iterative pruning and sign-flipping training. Inspired by the iterative scheme of IMP, which is observed to be essential for finding winning tickets, we extend SynFlow from one-shot pruning to multiple-shot over a period of the training process. Note that one shot of SynFlow can contain many iterations of pruning as described in Tanaka et al. (2020). Here by “multi-shot” we mean to apply SynFlow several times throughout the training process to gradually increase the sparsity level. Specifically, instead of applying SynFlow to the networks once at initialization, we run SynFlow for 2∼5 times, evenly spread over the first 50 epochs, so that the sparsity ratio linearly increases to a certain level (90%). Between two runs of pruning or after the last run of pruning, we perform the flipping-based training using Bop.
This iterative multi-shot version of PaB can be seen as alternating between the optimization processes of the searching and unmasking phase to discover the disguised networks. Compared to the one-shot variant, multi-shot PaB is closer to a joint optimization scheme on the objective in (1). The results are shown in Table 4. We observe that such an alternative scheme provides little accuracy improvement, while apparently losing more of training efficiency. We do not intend to say that the joint optimization is not good: to properly solve the joint optimization problem in (1) with iterative algorithms is interesting and potentially desirable. Our argument is that, with our goal to do “efficient” finding of disguised subnetworks, our current two-step relaxation is not only the most efficient; but also highly competitive in accuracy with no sacrifice.
Changing the bit-widths in PSG. In PSG, the bit-width configuration (bx, bω, bg) for layer inputs, layer weights and output gradients controls the trade-off between training efficiency and the precision of approximated gradient, and thus the model performance. We apply PaB-Bop-PSG with varying bit-configurations and show the results in Table 5. We observe that the bit-width of output gradient bg has a strong influence on the final performance, which is consistent with previous lowprecision efficient training works (Wang et al., 2019). We choose (bx, bω, bg) = (8, 8, 16) as it is a combination of good performance and training efficiency.

heading: D HUFFMAN CODING FOR ENCODING MASK AND SIGN ENCODING

text: PaB methods, without changing the magnitudes of the random initialization, only induces two outputs that need to be stored - (i) the sparse mask generated by the pruning methods (SynFlow in this work); and (ii) the sign flipping actions for all weights. These two outputs can be merged into one format, where the pruned weights are represented by 0, sustaining the sign by +1 and flipping the sign by−1. Considering that the pruned weights account for the majority of all weights (90% in our CIFAR-10 experiments and 70% in our CIFAR-100 experiments), we can adopt Huffman coding to encode 0 using 1-bit representation, and the sign flipping actions with 2-bit representation, as illustrated in Figure 6.


summaries: This paper focuses on developing a robust GNN model to defend against adversarial attacks on both graph structures and node features. More specifically, a general unified graph neural network is proposed to learn a graph structure and node features to correct the adversarial attacks. This a two-step approach. First, one operation is applied to reconstruct the graph with the node features. Then, the node features are updated by another operation with the learned graph structure. Experiments are conducted on four small datasets for evaluation.

summaries: The authors propose a General Unified Graph Neural Network (GUGNN) framework to address graph and feature denoising. They use this framework to design a graph neural network (R-GUGNN) which is Robust against poison adversarial attacks in a semi-supervised node classification setting. The authors demonstrate on four common datasets (Cora, Citeseer, Cora-ML & Polblogs) that their method is generally more robust against perturbation compared to commonly used graph neural networks (GCN, GAT) and models which are designed to be robust in the same setting (RGCN, GCN-SVD, Pro-GNN).

summaries: Considering the problem of adversarial manipulations of graphs, the authors propose a framework for "cleaning" the graph structure and its features to obtain more robust predictions. The core contribution, compared to existing works, is the additional considering of the feature cleaning. Technically, the authors first perform the graph cleaning (phrased as some kind of sparse, trace minimization problem) followed by some feature cleaning (phrased as some kind of feature diffusion/propagation). Experiments on standard (small) benchmark datasets shows some improvements.

summaries: The paper proposes a robust model for graph neural networks (GNNs) to defend against adversarial attacks. While most of the defense mechanisms in previous work focus on identifying and fixing the perturbed structure of the underlying graph, this paper proposes to jointly fix the perturbed structure as well as the node features. The proposed objective function captures these components along with weighting by some hyper-parameters. The experiments include several baselines and show results on different attack models: targeted attack, untargeted or global attack, and random attack. The experiments also have results on ablation study as well as hyper-parameters.

abstractText: Graph Neural Networks (GNNs) are powerful tools in representation learning for graphs. However, they are reported to be vulnerable to adversarial attacks, raising numerous concerns for applying it in some risk-sensitive domains. Therefore, it is essential to develop a robust GNN model to defend against adversarial attacks. Existing studies address this issue only considering cleaning perturbed graph structure, and almost none of them simultaneously consider denoising features. As the graph and features are interrelated and influence each other, we propose a General Unified Graph Neural Network (GUGNN) framework to jointly clean the graph and denoise features of data. On this basis, we further extend it by introducing two operations and develop a robust GNN model(R-GUGNN) to defend against adversarial attacks. One operation is reconstructing the graph with its intrinsic properties, including similarity of two adjacent nodes’ features, sparsity of real-world graphs and many slight noises having small eigenvalues in perturbed graphs. The other is the convolution operation for features to find the optimal solution adopting the Laplacian smoothness and the prior knowledge that nodes with many neighbors are difficult to attack. Experiments on four real-world datasets demonstrate that R-GUGNN has greatly improved the overall robustness over the state-of-the-art baselines.

authors:
Aleksandar Bojchevski
Stephan Günnemann

title: Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking

venue: arXiv preprint arXiv:1707.03815,

authors:
Aleksandar Bojchevski
Oleksandr Shchur
Daniel Zügner
Stephan Günnemann

title: Netgan: Generating graphs via random walks

venue: In ICML,

authors:
M. Defferrard
X. Bresson
P. Vandergheynst

title: Convolutional neural networks on graphs with fast localized spectral filtering

authors:
D. Duvenaud
D. Maclaurin
J. Aguilera-Iparraguirre
R. Gómez-Bombarelli
Timothy D. Hirzel
Alán Aspuru-Guzik
Ryan P. Adams

title: Convolutional networks on graphs for learning molecular

venue: fingerprints. ArXiv,

authors:
Negin Entezari
Saba A Al-Sayouri
Amirali Darvishzadeh
Evangelos E Papalexakis

title: All you need is low (rank) defending against adversarial attacks on graphs

venue: In Proceedings of the 13th International Conference on Web Search and Data Mining,

authors:
C Lee Giles
Kurt D Bollacker
Steve Lawrence

title: Citeseer: An automatic citation indexing system

venue: In Proceedings of the third ACM conference on Digital libraries,

authors:
Aditya Grover
J. Leskovec

title: node2vec: Scalable feature learning for networks

venue: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,

authors:
Wei Jin
Yaxin Li
Han Xu
Yiqi Wang
Shuiwang Ji
Charu Aggarwal
Jiliang Tang

title: Adversarial attacks and defenses on graphs: A review, a tool and empirical studies

venue: arXiv preprint arXiv:2003.00653,

authors:
Wei Jin
Yao Ma
Xiaorui Liu
Xianfeng Tang
Suhang Wang
Jiliang Tang

title: Graph structure learning for robust graph neural networks

venue: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,

authors:
Thomas Kipf
M. Welling

title: Semi-supervised classification with graph convolutional networks. ArXiv

authors:
Johannes Klicpera
Aleksandar Bojchevski
Stephan Günnemann

title: Predict then propagate: Graph neural networks meet personalized pagerank

venue: In ICLR,

authors:
Yaxin Li
Wei Jin
Han Xu
Jiliang Tang

title: Deeprobust: A pytorch library for adversarial attacks and defenses

venue: arXiv preprint arXiv:2005.06149,

authors:
Yao Ma
Xiaorui Liu
Tong Zhao
Yozen Liu
Jiliang Tang
Neil Shah

title: A unified view on graph neural networks as graph signal denoising

authors:
Andrew Kachites McCallum
Kamal Nigam
Jason Rennie
Kristie Seymore

title: Automating the construction of internet portals with machine learning

venue: Information Retrieval,

authors:
M. McPherson
L. Smith-Lovin
J. Cook

title: Birds of a feather: Homophily in social networks

venue: Review of Sociology,

authors:
J. Qiu
Jian Tang
Hao Ma
Yuxiao Dong
Kuansan Wang
Jie Tang

title: Deepinf: Social influence prediction with deep learning

authors:
Zonghan Wu
Shirui Pan
Fengwen Chen
Guodong Long
Chengqi Zhang
S Yu Philip

title: A comprehensive survey on graph neural networks

venue: IEEE transactions on neural networks and learning systems,

authors:
Han Xu
Yao Ma
Haochen Liu
Debayan Deb
H. Liu
Jiliang Tang
Anil K. Jain

title: Adversarial attacks and defenses in images, graphs and text: A review

venue: International Journal of Automation and Computing,

authors:
Rex Ying
Ruining He
Kaifeng Chen
Pong Eksombatchai
William L. Hamilton
J. Leskovec

title: Graph convolutional neural networks for web-scale recommender systems

authors:
Rex Ying
Jiaxuan You
Christopher Morris
Xiang Ren
William L. Hamilton
J. Leskovec

title: Hierarchical graph representation learning with differentiable pooling

authors:
Ziwei Zhang
Peng Cui
Wenwu Zhu

title: Deep learning on graphs: A survey

venue: IEEE Transactions on Knowledge and Data Engineering,

authors:
Ke Zhou
H. Zha
Le Song

title: Learning social infectivity in sparse low-rank networks using multidimensional hawkes processes

venue: In AISTATS,

authors:
Dingyuan Zhu
Ziwei Zhang
Peng Cui
Wenwu Zhu

title: Robust graph convolutional networks against adversarial attacks

venue: In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,

authors:
Daniel Zügner
Stephan Günnemann

title: Adversarial attacks on graph neural networks via meta learning

venue: arXiv preprint arXiv:1902.08412,

authors:
Daniel Zügner
Amir Akbarnejad
Stephan Günnemann

title: Adversarial attacks on neural networks for graph data

venue: In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,

heading: 1 INTRODUCTION

text:
Graph Neural Networks(GNNs) have drawn great attention as graphs can represent complex relationships among nodes. Graphs are ubiquitous in different domains, which are usually applied in recommender systems(Ying et al., 2018a), chemistry(Duvenaud et al., 2015), social media(Qiu et al., 2018) and so on. Utilizing the strong representation capacity of graphs, we can enhance performance of down-stream tasks such as node classification(Kipf & Welling, 2017; Velickovic et al., 2018; Klicpera et al., 2019), link prediction(Grover & Leskovec, 2016; Bojchevski et al., 2018) and graph classification(Defferrard et al., 2016; Ying et al., 2018b). A GNN model often consists of several graph convolution layers. A common practice of convolution layers is utilizing a feed-forward network to transform features and then aggregating transformed features. A series of convolution layers have been proposed and achieved great success such as GCN(Kipf & Welling, 2017), GAT(Velickovic et al., 2018) and PPNP(Klicpera et al., 2019).
However, GNN models composed of these convolution layers are vulnerable to adversarial attacks. Attacks can be conducted on either node features or the graph structure, while most existing adversarial attacks on graph data focus on modifying the graph structure(Xu et al., 2020). They always try to add, delete, or rewire edges to change the graph structure. Although these perturbations are unnoticeable, they can easily degrade the performance of GNN models, which may cause bad consequences. For example, spammers may create virtual followers to increase the chance of false messages being recommended and spread. The lack of GNNs’ robustness raises increasing concerns for applying it in some risk-sensitive domains. Therefore, it is necessary to develop graph defense techniques. Many existing defense methods focus on cleaning perturbed graphs by detecting properties of clean graphs and effects of specific attacks on graphs(Entezari et al., 2020; Jin et al., 2020b). Prior knowledge according to these researches can help GNN models defend against adversarial attacks to a certain extent. The study(Jin et al., 2020b) has proved that adversarial attacks could lead perturbed graphs to violate some properties of real graphs. For example, the rank of attacked graph increases and adversarial attacks often connect nodes with large feature differences.
However, existing studies only focus on cleaning the perturbed graph structure, and almost none of them simultaneously consider denoising features.
As the graph and features are closely tied and contain perturbations and noises, in this paper, we propose a General Unified Graph Neural Network(GUGNN) framework to jointly clean the graph and denoise features. Based on the GUGNN framework, we further introduce two kinds of operations. One operation is reconstructing the graph with its properties that real-world graphs are sparse(Zhou et al., 2013), the features of two adjacent nodes tend to be similar(McPherson et al., 2001) and perturbed graphs have many slight noises with small eigenvalues. Nodes with more neighbors are hard to attack(Zügner et al., 2018). Though we cannot change the number of nodes’ first-order neighbors, we can adjust the size of nodes’ neighborhood to add some high-order neighbors to nodes. According to this principle, from the denoising perspective, we design the convolution operation for features to find the optimal solution. Utilizing the two kinds of operations above, we develop a robust model(R-GUGNN), which can be applied for defending against different adversarial attacks.
The contributions of this paper are summarized as follows:
• We propose GUGNN framework to jointly clean the graph and denoise features for perturbations and noises existing in the graph and features.
• We introduce two kinds of operations to clean attacked graphs and denoise features respectively based on the GUGNN framework.
• For defending against adversarial attacks, we develop a concrete model R-GUGNN to realize the goal of the GUGNN framework utilizing the two kinds of operations.
• Experiments show that R-GUGNN has a strong capacity for defending against different adversarial attacks and stably outperforms the state-of-the-art defense models.

heading: 2 RELATED WORK

text: This section has two parts, including graph neural networks, and adversarial attacks and defenses for GNNs.

heading: 2.1 GRAPH NEURAL NETWORKS

text:
In this subsection, we review some famous graph neural network models, including GCN, GAT, PPNP, and a unified GNN framework UGNN. For more knowledge about GNNs, you can refer to some reviews(Wu et al., 2020; Zhang et al., 2020).
The convolution of GCN(Kipf & Welling, 2017) is defined in the graph spectral domain. Avoiding computing the full eigenvectors of the graph Laplacian matrix, based on Chebyshev polynomials, GCN only uses the first-order polynomial to simplify the graph convolution, which has been an accepted good graph convolution layer for its performance. The convolution of GAT(Velickovic et al., 2018) is defined in the spatial domain. The difference between GAT and GCN is that GAT learns different attention scores for neighbors when aggregating features. PPNP(Klicpera et al.,
2019) derives a propagation scheme based on personalized PageRank. It propagates information from a large and adjustable neighborhood instead of the first-order neighborhood directly. The neighborhood can be adjusted via a hyper-parameter.
UGNN(Ma et al., 2020) is a unified GNN framework available for different feature propagation processes from a denoising perspective. It proposes a denoising optimization problem with the Laplacian regularization term and tries to solve it in different ways utilizing the first derivative or the optimal solution. Original Laplacian matrix can be also replaced with different normalized forms. Different solutions to the optimization problem are corresponding to various convolution layers with different feature aggregation processes such as GCN, GAT, PPNP and so on.

heading: 2.2 ADVERSARIAL ATTACKS AND DEFENSES FOR GNNS

text:
We recommend a repository DeepRobust(Li et al., 2020) for readers. It contains many adversarial attacks and defenses on the graph, which is quite useful for researchers. For more knowledge about adversarial attacks and defenses for GNNs, you can refer to the review(Jin et al., 2020a).
Some adversarial attack methods have been proposed to show the vulnerability of GNNs with some unnoticeable perturbations added to the graph structure or node attributes. In the field of node classification, the aim of adversarial attacks is fooling GNNs into classifying nodes incorrectly. Poisoning attacks change the graph structure before we train GNN models, which is one of the most common settings of adversarial attacks on graph data. Poisoning attacks have various types, including global attack, targeted attack and random attack. Based on the whole graph, the goal of global attack is to degrade the overall performance of GNNs. One of the state-of-the-art global attacks is metattack(Zügner & Günnemann, 2019), which generates the poisoning attacks based on metalearning. Targeted attack generates attacks on some specific nodes and aims to fool GNNs on these target nodes. The nettack(Zügner et al., 2018) is one of the state-of-the-art targeted attacks, which aims to change the graph structure and features of target nodes or nearby nodes with perturbations remaining unnoticeable. Random attack adds random noises to the clean graph whose concrete practice is adding, removing or flipping edges randomly.
Methods about preventing GNNs from adversarial attacks are also developed to improve the robustness of GNNs recently. To mitigate the effects of adversarial attacks on the graph, RGCN(Zhu et al., 2019) uses Gaussian distributions as hidden representations of nodes instead of plain vectors in other GNNs. Considering that nettack is a high-rank attack, GCN-SVD(Entezari et al., 2020) is proposed to reconstruct the perturbed graph with only the top-k largest singular components. Using such a low-rank approximation, GCN-SVD can reduce the effects of nettack. In fact, the practice of ensuring low-rank is removing noises with small singular values of the graph. Pro-GNN(Jin et al., 2020b) jointly optimizes a structural graph and a robust GNN model from the perturbed graph with some properties of clean graphs. Pro-GNN has big improvement over other defense models with these properties. However, like other defense models, Pro-GNN doesn’t take denoising features into account jointly.

heading: 3 THE PROPOSED FRAMEWORK

text: In this section, we first present GUGNN framework, and then we introduce a novel graph reconstruction operation. At last, we show the convolution operation for features and our concrete design of R-GUGNN model, which is used to realize the goal of GUGNN framework.

heading: 3.1 NOTIONS

text:
We denote some notations here. Denote X ∈ RN×d as the feature matrix, where N, d represent the number of samples and the dimension of features respectively. Denote G = {V, E} as the graph, where V represents node sets and E represents edge sets. We also use the adjacency matrix A ∈ RN×N to represent G.
Algorithm 1: R-GUGNN Input: Adjacency matrix A, Feature matrix X, Labels y, Hyper-parameters m, c,β, λ, Learning rate η. Output: GNN parameters θ
1 Ã = A + I; Initialize S = Ã; 2 for i= 1 to m do 3 Calculating Z in formula(5); 4 S = S− c2Z; 5 S = prox∗β(S); 6 S = proxs(S); 7 Initialize F = X;Randomly initialize θ; 8 while Stopping condition is not met do 9 Forward propagation using two convolution layers:
10 Using feature transformation formula: F = FW, 11 and feature aggregation formula: F = (I + λL̂)−1F; 12 Getting output y′; 13 Calculating gradient g according to y and y′; 14 Backward propagation: θ = θ − ηg; 15 return θ;

heading: 3.2 THE GENERAL UNIFIED GNN FRAMEWORK

text:
To discard perturbations and noises in the graph and features, considering the tight connection between them, we propose our general united graph neural network(GUGNN) framework to solve such problem, which is shown as follows:
argmin S,F
L = ‖S− A‖2F + γ‖F− X‖2F + c · tr(FTLF) + β · f(S) (1)
where S and F are the learned adjacency and feature matrix. L is the Laplacian matrix of S. L = D − S, where D is a diagonal matrix and Dii = ∑N j=1 Sij . L can be also replaced with different normalized forms. tr(FTLF) is Laplacian regularization term for both denoising features and cleaning the graph. f(S) is a flexible regularization term to enforce some prior over S. γ, c and β are hyper-parameters to balance different components.
From a united perspective, we view that both features and the graph contain noises and our goal is jointly optimizing F and S. tr(FTLF) can be rewritten as 12 ∑N i,j=1 Sij(fi − fj)2, where fi is the i-th row of F. This term represents that features of two adjacent nodes should be similar, which is the guidance for both learning F and S. Although X and A have some noises, they can represent the real features and the graph to a large extent. So, the learned F and S should be similar to X and A respectively, which are the meanings of ‖F − X‖2F and ‖S − A‖2F . In addition, we add some prior to the graph in f(S) to make it more accurate.

heading: 3.3 THE NOVEL GRAPH RECONSTRUCTION OPERATION

text:
We focus on cleaning the perturbed graph supposing F=X. Formula(1) of GUGNN can be rewritten as follows:
argmin S
L = ‖S− A‖2F + c · tr(XTLX) + β · f(S) (2)
Considering that the graph contains noises, we rewrite formula(2) as follows:
argmin S
L = ‖S− Ã‖2F + c · tr(XT L̂X) + β‖S‖∗
= L1 + L2 + L3 (3)
The adjacency matrix with self-loop Ã and the normalized Laplacian matrix L̂ are adopted. L̂ = D− 1 2 LD−
1 2 . tr(XT L̂X) is equal to 12 ∑N i,j=1 Sij( xi√ Dii − xj√ Djj )2. Since degrees of the perturbed
graph are approximately equal to those of the real graph, for the convenience of calculation, we let Dii = ∑N j=1 Ãij . ‖S‖∗ = ∑rank(S) i σi, where σi is the i-th singular value of S.
To solve formula(3), we let ∂L1+L2∂S = 0 to get the closed form solution.
∂L1 + L2 ∂S = 2(S− Ã) + c
 ( x1√ D11 − x1√D11 ) 2 · · · ( x1√D11 − xN√ DNN )2 ... . . .
... ( xN√DNN − x1√D11 ) 2 · · · ( xN√DNN − xN√ DNN )2
 = 0 (4)
S = Ã− c 2
 ( x1√ D11 − x1√D11 ) 2 · · · ( x1√D11 − xN√ DNN )2 ... . . .
... ( xN√DNN − x1√D11 ) 2 · · · ( xN√DNN − xN√ DNN )2  (5) We denote formula(5) as S = Ã − c2Z for convenience. A proximal operator of nuclear norm is adopted to remove noises and reserve main properties(Entezari et al., 2020).
prox∗β(S) = Udiag(max{σi − β, 0})iVT (6)
where S = Udiag(σ1 . . . σN )VT is the singular value decomposition of S. Let S = prox∗β(S) to represent this step. For the constraint Sij ∈ [0, 1], we let S = S + I to enhance self-loop, and set Sij<0 to 0 and Sij>1 to 1. We denote this step as S = proxs(S), which can make the graph sparse at the same time.

heading: 3.4 THE CONVOLUTION OPERATION FOR FEATURES

text:
After getting the cleaned graph through several graph reconstruction operations above, we fix it and focus on denoising features, formula(1) of GUGNN can be rewritten as follows:
argmin F
L = ‖F− X‖2F + λ · tr(FTLF) (7)
where λ = cγ . In this case, formula(7) is equal to that of UGNN(Ma et al., 2020). We use the normalized Laplacian matrix L̂ and let ∂L∂F = 0 to find the optimal solution. ∂L ∂F = 2(F− X) + 2λL̂F = 0 (8)
F = (I + λL̂)−1X (9) Formula(9) is the process of feature aggregation. Before it, we let X = XW to transform features, where W is the parameter of a single GNN convolution layer. This is our convolution operation for features, which is proved(Ma et al., 2020) equal to PPNP(Klicpera et al., 2019). So, our convolution operation for features can also adjust nodes’ neighborhood to enhance the model’s robustness.

heading: 3.5 THE DESIGN OF R-GUGNN MODEL

text: Utilizing the two kinds of operations, we design R-GUGNN model and show it in Figure 1, where m is the number of graph reconstruction operations we can set. In step À, we fix features and clean the graph with m graph reconstruction operations. In step Á, we fix the cleaned graph and denoise features with two graph convolution layers. We train GNN parameters θ using the two graph convolution layers and classify nodes finally. Concrete steps of R-GUGNN are shown in Algorithm 1.

heading: 4 EXPERIMENTS

text: In this section, we evaluate the effectiveness of R-GUGNN model compared with the state-of-theart GNN models against different attacks. We first introduce the experimental settings and then present results of a series of experiments. At last, we conduct the ablation study and analyze hyperparameters of R-GUGNN.

heading: 4.1 EXPERIMENTAL SETTINGS

heading: 4.1.1 DATASETS

text: We compare different models on four benchmark datasets, including three citation graphs, i.e., Cora(McCallum et al., 2000), Citeseer(Giles et al., 1998) and Cora-ML(Bojchevski & Günnemann, 2017), and one blog graph, i.e., Polblogs(Jin et al., 2020b). Cora-ML is the subset of machine learning papers from Cora dataset, which is also a well-known dataset in GNN field. Since Polblogs dataset has no node features, a N × N identity matrix is used to act as the feature matrix. We only consider the largest connected component(LCC) in each dataset(Jin et al., 2020b; Zügner et al., 2018). Table 1 contains detailed information about the dataset.

heading: 4.1.2 BASELINES

text: R-GUGNN model are compared with the state-of-the-art GNN and defense models in repository DeepRobust(Li et al., 2020), i.e., GCN(Kipf & Welling, 2017), GAT(Velickovic et al., 2018), RGCN(Zhu et al., 2019), GCN-SVD(Entezari et al., 2020) and Pro-GNN(Jin et al., 2020b). We adopt the default parameter settings in GCN and GAT. The number of hidden units of RGCN are tuned from {16, 32, 64, 128}. The reduced rank of the perturbed graph in GCN-SVD is tuned from {5, 10, 15, 50, 100, 200}. For Pro-GNN, we use the tuned hyper-parameters the author gives online.

heading: 4.1.3 PARAMETER SETTINGS

text: Just as(Jin et al., 2020b), for each dataset, we choose 10% of nodes for training, 10% of nodes for validation and the remaining 80% of nodes for testing. The average performance of 10 runs is reported for all experiments below. The hyper-parameters of all the models are tuned based on the loss and accuracy on the validation set. Note that the same hyper-parameters are used under the same attack for the same dataset no matter what perturbation rate is. If there are no special instructions, all models adopt two graph convolution layers with 16 hidden units. Learning rate of Adam optimizer η is fixed as 0.01 and negative log likelihood loss is adopted for a fair comparison(RGCN has its own loss function).

heading: 4.2 PERFORMANCE AGAINST DIFFERENT ATTACKS

text: The node classification performance of R-GUGNN is evaluated against three types of poisoning attacks, i.e., global attack, targeted attack and random attack. Since Ploblogs dataset has no real node features, hyper-parameter c of R-GUGNN is set to 0 on Ploblogs dataset.

heading: 4.2.1 AGAINST GLOBAL ATTACK

text:
The famous metattack(Zügner & Günnemann, 2019) is used as the global attack to conduct experiments and all the default parameter settings in the authors’ original implementation are adopted. Concretely, the strongest variant Meta-Self is applied for all datasets. The perturbation rate of metattack on the graph is from 0% to 25% with a step of 5%, since too heavy attacks are noticeable and make no sense. We report the average accuracy of node classification with standard deviation on test set and highlight the optimal results in bold. Concrete results are shown in Table 2 and we draw some conclusions:
• R-GUGNN has great improvement compared to others on four datasets. The average improvement of accuracy under different perturbation rates over GCN on four datasets is about 16%, 10%, 19% and 21% respectively. When the graph is heavily perturbed, the improvement is larger. For example, when the perturbation rate is 20%, the improvement over GCN is about 23%, 16%, 25% and 25% on four datasets respectively. When compared with different second best models, improvement can reach 10%, 6%, 19% and 7% on four datasets. These results prove that R-GUGNN can defend against metattack very well.
• Accuracy of R-GUGNN is stably high under different perturbation rates on all datasets. The gap between accuracy of R-GUGNN on clean and perturbed graphs is small. For example, gaps of the accuracy of R-GUGNN under 25% and 0% metattack on Cora and Citeseer datasets are only about 7% and 2%. Besides, the overall standard deviations of R-GUGNN are small. However, the lack of real node features on Polblogs dataset causes big standard deviations when the graph is heavily attacked.

heading: 4.2.2 AGAINST TARGETED ATTACK

text: The typical netttack(Zügner et al., 2018) is employed as the targeted attack to conduct experiments and all the default parameter settings in the authors’ original implementation are adopted. We select nodes with degree >10 as targeted nodes from the test set. The number of perturbations of the graph on each targeted node is from 0 to 5 with a step of 1. We report accuracy of these targeted nodes as results, which are shown in Figure 2. R-GUGNN suffers less effects of nettack and also performs greatly and stably. For example, compared to the second best method Pro-GNN, R-GUGNN achieves 10% and 5% improvement on Citeseer and Cora-ML datasets. These results prove that R-GUGNN can defend against netttack very well.

heading: 4.2.3 AGAINST RANDOM ATTACK

text:
Performance of R-GUGNN under random attack is evaluated here. We add random perturbations on the graph from 0% to 100% with a step of 20%. Concrete results are shown in Figure 3. R-GUGNN outperforms other models again and the improvement is distinct. For example, compared to different second best models, R-GUGNN achieves a 2.5% and 3.5% improvement on Citeseer and Cora-ML datasets. These results prove that R-GUGNN can defend against random attack very well.
From the overall performance, we observe that the advantage of R-GUGNN is obvious compared with others and its performance is stably great. In conclusion, R-GUGNN is robust enough to defend against different attacks.

heading: 4.3 ABLATION STUDY

text:
R-GUGNN contains m graph reconstruction operations. If we discard these operations and only use two convolution layers for features, R-GUGNN is equal to PPNP(Klicpera et al., 2019). So, in this
subsection, we compare PPNP with GCN and R-GUGNN on Cora dataset under random attack as an example to illustrate. In addition, we set β and c to 0 to understand the impact of each component in the graph reconstruction operation. Furthermore, we observe standard deviations of R-GUGNN when c=0.
In Figure(4)(a), we can see that performance of R-GUGNN is better than PPNP and performance of GCN is the worst. It shows graph reconstruction operations are significant(R-GUGNN vs PPNP), and adjusting neighborhood is beneficial to defending against attacks(PPNP vs GCN). PPNP curve and the no-β curve overlap very well, which indicates that removing noises with small singular values plays a quite important role in cleaning the graph. What’s more, if c=0, not only model’s performance is poor, but also the standard deviation rises a lot especially when the graph is heavily attacked in Figure(4)(b). It shows the Laplacian regularization term is significant in improving stability of R-GUGNN, which explains why the standard deviation is big on Polblogs dataset under heavy attack.

heading: 4.4 PARAMETER ANALYSIS

text:
In this subsection, we show performance of R-GUGNN with different values of hyper-parameters i.e., m, c, β, and λ. We use Cora-ML dataset under 15% metattack as an example to illustrate. The value range of m is from 1 to 5 with the step of 1. The value of c is selected in {10−5, 10−4, 10−3, 10−2, 10−1}. We select β from 1 to 3.5 and λ from 0.5 to 3 with the step of 0.5. In the process of tuning one hyper-parameter, other hyper-parameters are fixed as the optimal. Figure 5 shows effects of different values of hyper-parameters.
m is the number of graph reconstruction operations. Our novel operations of R-GUGNN are important for defending against attacks, and even one such operation improves model’s robustness(76.87% accuracy). However, proper m can boost the accuracy and too many such operations cannot benefit R-GUGNN. β is also a key affecting the performance of R-GUGNN, which controls how many noises with small singular values to remove. When β is too small, noises cannot be removed entirely. While when β is too big, the main properties of the graph can be hurt. λ is used to adjust the size of nodes’ neighborhood when propagating features and choosing proper λ is also important. c is used to control the Laplacian smoothness of the graph. We find the big value of c hurts the performance of R-GUGNN, but when c is small, accuracy doesn’t decrease a lot. From a whole performance, all hyper-parameters have an interval of values where the performance of R-GUGNN is stably great.

heading: 5 CONCLUSION

text: In this paper, we propose GUGNN, a novel general unified framework to effectively enhance the robustness of GNNs against adversarial attacks by jointly cleaning the perturbed graph and denoising the features of data. Furthermore, we extend this framework by reconstructing the graph and making convolution operations of features with intrinsic properties, and propose a robust GNN model RGUGNN. Experiment results show that R-GUGNN stably outperforms the state-of-the-art baselines under different adversarial attacks. In the future, we aim to extend this framework to other models on graphs, even more complicated graph structures for mining the rich value underlying graph data of various domains.