summaries: In this paper, the authors studied the adversarial attack problem for graph classification problem with graph convolutional networks. After observing that traditional attack by adding or deleting edges can change graph eigenvalues, the author proposed to attack by adding rewiring operation which make less effects. Rewiring does not change the graph edge number and the average degree. Further, the authors propose an RL based learning method to learn the policy of doing rewiring operation. Experiments show that the proposed method can make more successful attack on social network data than baselines and previous methods.

summaries: This paper proposes a new type of adversarial attack setting for graphs, namely graph rewiring operation, which deletes an edge in the graph and adds a new edge between one node of the first edge and one of its 2-hop neighbors. This new attack is proposed to make the perturbations unnoticeable compared with adding or deleting arbitrary edges. To solve this problem, a reinforcement learning based approach is proposed to learn the attack strategy in the black-box manner. Experiments conducted on several datasets prove the effectiveness of the proposed with over an existing method and baseline methods.

summaries: This paper proposes the ReWatt method to attack graph classification models by making unnoticeable perturbations on graph. Reinforcement learning was leveraged to find a rewiring operation a = (v1; v2; v3) at each step, which is a set of 3 nodes. In the first step, an existing edge (v1, v2) in the original graph is selected and removed. Then another node v3 that is 2-hop away from v1 and not 1-hop away is selected.  Finally (v3, v1) is connected as a new edge. Some analysis shows that the rewiring operation tends to make smaller changes to the eigenvalues of the graph's Laplacian matrix compared with simply adding and deleting edges, making it difficult to detect the attacks.

abstractText: Graph Neural Networks (GNNs) have boosted the performance of many graph related tasks such as node classification and graph classification. Recent researches show that graph neural networks are vulnerable to adversarial attacks, which deliberately add carefully created unnoticeable perturbation to the graph structure. The perturbation is usually created by adding/deleting a few edges, which might be noticeable even when the number of edges modified is small. In this paper, we propose a graph rewiring operation which affects the graph in a less noticeable way compared to existing operators. We then use reinforcement learning to learn the attack strategy based on the proposed rewiring operation. Experiments on real world graphs demonstrate the effectiveness of the proposed framework. To understand the proposed framework, we further analyze how its generated perturbation to the graph structure affects the output of the target model and the advantages of the rewiring operation.

authors:
Joan Bruna
Wojciech Zaremba
Arthur Szlam
Yann LeCun

title: Spectral networks and locally connected networks on graphs

venue: arXiv preprint arXiv:1312.6203,

authors:
Nicholas Carlini
David Wagner

title: Towards evaluating the robustness of neural networks

venue: IEEE Symposium on Security and Privacy (SP),

authors:
Hau Chan
Leman Akoglu

title: Optimizing network robustness by edge rewiring: a general framework

venue: Data Mining and Knowledge Discovery,

authors:
Pin-Yu Chen
Huan Zhang
Yash Sharma
Jinfeng Yi
Cho-Jui Hsieh

title: Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models

venue: In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security,

authors:
Minhao Cheng
Thong Le
Pin-Yu Chen
Jinfeng Yi
Huan Zhang
Cho-Jui Hsieh

title: Queryefficient hard-label black-box attack: An optimization-based approach

venue: arXiv preprint arXiv:1807.04457,

authors:
Hanjun Dai
Hui Li
Tian Tian
Xin Huang
Lin Wang
Jun Zhu
Le Song

title: Adversarial attack on graph structured data

authors:
Michaël Defferrard
Xavier Bresson
Pierre Vandergheynst

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

venue: In Advances in neural information processing systems,

authors:
Wendy Ellens
FM Spieksma
P Van Mieghem
A Jamakovic
RE Kooij

title: Effective graph resistance

venue: Linear algebra and its applications,

title: Algebraic connectivity of graphs

venue: Czechoslovak mathematical journal,

authors:
Arpita Ghosh
Stephen Boyd

title: Growing well-connected graphs

venue: In Proceedings of the 45th IEEE Conference on Decision and Control,

authors:
Ian J Goodfellow
Jonathon Shlens
Christian Szegedy

title: Explaining and harnessing adversarial examples

venue: arXiv preprint arXiv:1412.6572,

authors:
Will Hamilton
Zhitao Ying
Jure Leskovec

title: Inductive representation learning on large graphs

venue: In Advances in Neural Information Processing Systems,

authors:
Andrew Ilyas
Logan Engstrom
Anish Athalye
Jessy Lin

title: Black-box adversarial attacks with limited queries and information

venue: arXiv preprint arXiv:1804.08598,

authors:
Kristian Kersting
Nils M. Kriege
Christopher Morris
Petra Mutzel
Marion Neumann

title: Benchmark data sets for graph kernels, 2016

authors:
Thomas N Kipf
Max Welling

title: Semi-supervised classification with graph convolutional networks

venue: arXiv preprint arXiv:1609.02907,

title: Information theory and statistics

venue: Courier Corporation,

authors:
Alexey Kurakin
Ian Goodfellow
Samy Bengio

title: Adversarial examples in the physical world

venue: arXiv preprint arXiv:1607.02533,

authors:
Benjamin A Miller
Mustafa Çamurcu
Alexander J Gomez
Kevin Chan
Tina Eliassi-Rad

title: Improving robustness to attacks against vertex classification

authors:
Bojan Mohar
Y Alavi
G Chartrand
OR Oellermann

title: The laplacian spectrum of graphs

venue: Graph theory, combinatorics, and applications,

authors:
Seyed-Mohsen Moosavi-Dezfooli
Alhussein Fawzi
Pascal Frossard

title: Deepfool: a simple and accurate method to fool deep neural networks

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

authors:
Aliaksei Sandryhaila
Jose MF Moura

title: Discrete signal processing on graphs: Frequency analysis

venue: IEEE Transactions on Signal Processing,

authors:
David I Shuman
Sunil K Narang
Pascal Frossard
Antonio Ortega
Pierre Vandergheynst

title: The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains

venue: arXiv preprint arXiv:1211.0053,

title: Matrix perturbation theory

title: Reinforcement learning: An introduction

venue: MIT press,

authors:
Ali Sydney
Caterina Scoglio
Don Gruenbacher

title: Optimizing algebraic connectivity by edge rewiring

venue: Applied Mathematics and computation,

authors:
Christian Szegedy
Wojciech Zaremba
Ilya Sutskever
Joan Bruna
Dumitru Erhan
Ian Goodfellow
Rob Fergus

title: Intriguing properties of neural networks

venue: arXiv preprint arXiv:1312.6199,

authors:
Xiaoyun Wang
Joe Eaton
Cho-Jui Hsieh
Felix Wu

title: Attack graph convolutional networks by adding fake nodes

venue: arXiv preprint arXiv:1810.10751,

authors:
Pinar Yanardag
SVN Vishwanathan

title: Deep graph kernels

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

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

title: Hierarchical graph representation learning withdifferentiable pooling

venue: arXiv preprint arXiv:1806.08804,

authors:
Muhan Zhang
Zhicheng Cui
Marion Neumann
Yixin Chen

title: An end-to-end deep learning architecture for graph classification

venue: In Thirty-Second AAAI Conference on Artificial Intelligence,

authors:
Marinka Zitnik
Rok Sosič
Marcus W. Feldman
Jure Leskovec

title: Evolution of resilience in protein interactomes across the tree of life

venue: Proceedings of the National Academy of Sciences,

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,

authors:
Daniel Zügner
Stephan Günnemann

title: Adversarial attacks on graph neural networks via meta learning

heading: 1 INTRODUCTION

text:
Graph structured data are ubiquitous in many real world applications. Various data from different domains, such as social networks, molecular graphs and transportation networks can all be modeled as graphs. Recently, increasing effort has been devoted towards developing deep neural networks on graph structured data. This stream of works, which is known as Graph Neural Networks (GNN) has shown to enhance the performance in many graph related tasks such as node classification (Kipf & Welling, 2016; Hamilton et al., 2017) and graph classification (Bruna et al., 2013; Defferrard et al., 2016; Ying et al., 2018; Zhang et al., 2018).
Recent researches have shown that deep neural networks are highly vulnerable to adversarial attacks (Szegedy et al., 2013; Goodfellow et al., 2014; Kurakin et al., 2016; Carlini & Wagner, 2017). In computer vision, performing an adversarial attack is to add deliberately created, but unnoticeable, perturbation to a given image such that the deep model misclassifies the perturbed image. Unlike image data, which can be represented in the continuous space, graph structured data is discrete. Few efforts have been made to investigate the robustness of graph neural networks against adversarial attacks. Only recently, such researches about adversarial attacks on graph structured data started to emerge. A greedy algorithm is proposed to attack the semi-supervised node classification task (Zügner et al., 2018). The method deliberately tries to modify the graph structure and node features such that the label of a targeted node can be changed. A reinforcement learning based algorithm is proposed to attack both node classification and graph classification task by only modifying the graph structure(Dai et al., 2018). A meta-learning based attack method is designed to impair the overall performance of the node classification task(Zügner & Günnemann, 2019). For the majority of existing works, the graph structure is modified by adding or deleting edges.
To ensure that the difference between the attacked graph and the original graph is “unnoticeable”, the number of actions (adding/deleting edges) that can be taken by the attacking algorithms is usually constrained by a budget. However, even when this budget is small, adding or deleting edges can still make “noticeable” changes to the graph structure (Miller et al., 2019). For example, it is evident that many important graph properties are based on eigenvalues and eigenvectors of the Laplacian matrix of the graph (Chan & Akoglu, 2016); while adding or deleting an edge can make remarkable changes on the eigenvalues/eigenvectors of the graph Laplacian (Ghosh & Boyd, 2006). Thus, in this work, we propose a new operation based on graph rewiring. A single rewiring operation involves
three nodes (vfir, vsec, vthi), where we remove the existing edge between vfir and vsec and add edge between vfir and vthi. Note that vthi is constraint to be the 2-hop neighbor of vfir in our setting. It is obvious that the proposed rewiring operation preserves some basic properties of the graph such as number of nodes and edges, total degrees of the graph and etc, while operations like adding and deleting edges cannot. Furthermore, the proposed rewiring operation affects some of the important measures based on graph Laplacian such as algebraic connectivity in a smaller way than adding/deleting edges, which is theoretically demonstrated in Section 4.1. In addition, the rewiring operation is a more natural way to modify the graph. For example, in biology, the evolution of DNA and amino acid sequences can lead to pervasive rewiring of protein–protein interactions (Zitnik et al., 2019).
In this paper, we aim to construct adversarial examples by performing rewiring operations for the task of graph classification. More specifically, we treat the process of applying a series of rewiring operations to a given graph as a discrete Markov decision process (MDP) and use reinforcement learning to learn how to make these decisions. We demonstrate the effectiveness of the proposed algorithm on real-world graphs. Then we further analyze how the adversarial changes in the graph structure affect both the graph embedding learned by the graph neural network model and the output label and illustrate the advantages of the rewiring operation.

heading: 2 BACKGROUND

text: In this section, we introduce notations and the target graph convolutional model we seek to attack. We denote a graph as G = {V, E}, where V = {v1, . . . , v|V|} and E = {e1, . . . , e|E|} are the sets of nodes and edges, respectively. The edges describe the relations between nodes, which can be described by an adjacency matrix A ∈ {0, 1}|V|×|V|. Aij = 1 means vi and vj are connected, 0 otherwise. Each node in the graph has some features that are associated with it. These features are represented as a matrix X ∈ R|V|×d, where the i-th row of X denotes the node features of node vi and d is the dimension of features. Thus, an attributed graph can be represented as G = {A,X}.

heading: 2.1 GRAPH CLASSIFICATION

text: In the setting of graph classification, we are given a set of graphs G = {Gi}. Each of these graphs Gi is associated with a label yi. The task is to build a good classifier using the given set of graphs such that it can make correct predictions when new unseen graphs are fed into it. A graph classifier parameterized by θ can be represented as f(G|θ) = yo, where yo denotes the label of a graph G ∈ G predicted by the classifier. The parameters θ in the classifier f(·|θ) can be learned by solving the following optimization problem minθ ∑ i L(f(Gi|θ), yi), where L(·, ·) is used to measure the difference between the predicted and ground truth labels. Cross entropy is a commonly adopted measurement for L(·, ·).

heading: 2.2 GRAPH CONVOLUTION NETWORKS

text:
Recently, Graph Neural Networks have been shown to be effective in graph representation learning. These models usually learn node representations by iteratively aggregating, transforming and propagating node information. In this work, we adopt the graph convolutional networks (GCN) (Kipf & Welling, 2016). A graph convolutional layer in the GCN framework can be represented as
Fj = ReLU(D− 1 2AD− 1 2Fj−1Wj) (1)
where Fj ∈ RN×dj is the output of the j-th layer and Wj represents the parameters of this layer. A GCN model usually consists of J graph convolutional layers, with F0 = X. The output of the GCN model is FJ , which is denote as F for convenience. To obtain a graph level embedding uG for graph G to perform graph classification, we apply a global pooling over the node embeddings.
uG = pool(F) (2)
Different global pooling functions can be used, and we adopt the max pooling in this work. A multilayer perceptron (MLP) and softmax layer are then sequentially applied on the graph embedding to predict the label of the graph
yo = argmax softmax(MLP (uG|WMLP )) (3)
where MLP (·|WMLP ) denotes the multilayer perceptron with parameters as WMLP . A GCNbased classifier for graph classification can be described using eq. equation 1, equation 2 and equation 3 as introduced above. For simplicity, we summarize it as yo = fGCN (G|θGCN ), where θGCN includes all the parameters in the model.

heading: 3 PROBLEM FORMULATION

text:
In this work, we aim to build an attacker T that takes a graph as input and modify the structure of the graph to fool a GCN classifier. Modifying a graph structure is equivalent to modify its adjacency matrix. The function of the attacker can be represented as G̃ = T (G) = {T (A),X} = {Ã,X}. Given a classifier f(·), the goal of the attacker is to modify the graph structure so that the classifier outputs a different label from what it originally predicted. Note here, we neglect the θ inside f(·), as the classifier is already trained and fixed. Mathematically, the goal of the attacker can be represented as: f(T (G)) 6= f(G). As described above, the attacker T is specifically designed for a given classifier f(·). To reflect this in the notation, we now denote the attacker for the classifier f(·) as Tf . In our work, the attacker Tf has limited knowledge of the classifier. The only information the attacker can get from the classifier is the label of (modified) graphs. In other words, the classifier f(·) is treated as a black-box model for the attacker Tf . An important constraint to the attacker Tf is that it is only allowed to make “unnoticeble” changes to the graph structure. To account for this, we propose the rewiring operation, which is supposed to make more subtle changes than adding or deleting edges. We will show that the rewiring operation can better preserve a lot of important properties of the graph compared to adding or deleting edges in Section 4.1. We also empirically compare the rewiring operation with the deleting/adding edges in Appendix C. The definition of the proposed rewiring is given below: Definition 1. A rewiring operation a involves three nodes and it can be denoted as a = {vfir, vsec, vthi}, where vsec ∈ N1(vfir) and vthi ∈ N2(vfir)/N1(vfir). Nk(vfir) denotes the k-th hop neighbors of vfir and the sign / stands for exclusion. The rewiring operation deletes the existing edge between nodes vfir and vsec, while adding an edge to connect nodes vfir and vthi.
The attacker Tf is given a budget of K proposed rewiring operations to modify the graph structure. A straightforward way to set K is choosing a small fix number. However, it is likely that graphs in a given data set have various graph sizes. The same number of rewiring operations can affect the graphs of different size in various magnitude. Hence, a more suitable way is to allow flexible number of rewiring operations according to the graph size. Thus, we propose to use K = p · |E| for a given graph G, where p ∈ (0, 1) is a ratio. The process of the attacker on a graph G can be now denoted as Tf (G) ↔ (a1, a2, . . . , aM )[G], where the right hand part means to sequentially apply the rewiring operations a1, . . . , aM to the graph G, and M is the number of rewiring operations taken with M ≤ K.

heading: 4 REWIRING-BASED ATTACK TO GRAPH CONVOLUTIONAL NETWORKS

text: Next, we first discuss the properties of the proposed rewiring operation to show its advantages. We then introduce the proposed attacking framework ReWatt based on reinforcement learning and rewiring.

heading: 4.1 PROPERTIES OF THE PROPOSED REWIRING OPERATION

text:
The proposed rewiring operation has several advantages compared to simply adding or deleting edges. More empirical discussions can be found in Appendix C. One obvious advantage of the proposed rewiring operation is that it does not change the number of nodes, the number of edges and the total degree of a graph. However, operations like “adding” or “deleting” edges may change those properties.
Many important graph properties are based on the eigenvalues of the Laplacian matrix of a graph (Chan & Akoglu, 2016) such as Algebraic Connectivity Fiedler (1973) and Effective Graph
Resistance Ellens et al. (2011). A detailed description of Algebraic Connectivity and Effective Graph Resistance are given in Appendix A. Next, we demonstrate that the proposed rewiring operation is likely to make smaller changes to eigenvalues, which result in unnoticeable changes under graph Laplacian based measures. For a graph G with A as its adjacency matrix, its Laplacian matrix L is defined as L = D−A, where D is the diagonal degree matrix (Mohar et al., 1991). Let λ1, . . . , λ|V| denote the eigenvalues of the Laplacian matrix arranged in the increasing order with x1, . . . ,x|V| being the corresponding eigenvectors. We show how a single proposed rewiring operation affects the eigenvalues. Our analysis is based on the following lemma: Lemma 1. (Stewart, 1990) Let (αi,hi) be the eigen-pairs of a symmetric matrix M ∈ RN×N . Given a perturbation ∆M to matrix M, its eigenvalues can be updated by ∆αi = hTi ∆Mhi.
The proof can be found in (Stewart, 1990). Using this lemma, we have the following corollary Corollary 1. For a given graph G with Laplacian matrix L, one proposed rewiring operation (vfir, vsec, vthi) affects the eigen-value λi by ∆λi, for i = 1, . . . , |V|, where
∆λi = (2xi[fir]− xi[thi]− xi[sec])(xi[sec]− xi[thi]) (4) where xi[index] denotes the index-th value of the eigenvector xi.
The proof can be found in Appendix B.
Furthermore, each eigenvalue λi of the Laplacian matrix measures the “smoothness” of its corresponding eigenvector xi (Shuman et al., 2012; Sandryhaila & Moura, 2014). The “smoothness” of an eigenvector measures how different its elements are from their neighboring nodes. Thus, the first few eigenvectors with relatively small eigenvalues are rather “smooth”. Note that in the proposed rewiring operation, vsec is the direct neighbor of vfir and vthi is the 2-hop neighbor of vfir. Thus, the difference xi[fir]−xi[thi] is expected to be smaller than the difference xi[fir]−xi[can], where xi[can] can be any other node that is further away. This means that the proposed rewiring operation (to 2-hop neighbors) is likely to make smaller changes to the first few eigenvalues than rewiring to any further away nodes or adding an edge between two nodes that are far away from each other.

heading: 4.2 GRAPH ADVERSARIAL ATTACK WITH REINFORCEMENT LEARNING

text:
Given a graph G, the process of the attacker T is a general decision making process M = (S,A, P,R), where A = {at} is the set of actions, which consists of all valid rewiring operations, S = {st} is the set of states that consists of all possible intermediate and final graphs after rewiring, P is the transition dynamics that describes how a rewiring action at changes the graph structure p(st+1|, st, . . . , s1, at). R is the reward function, which gives the reward for the action taken at a given state. Thus, the procedure of attacking a graph can be described by a trajectory (s1, a1, r1, . . . , sM , aM , rM ), where s1 = G. The key point for the attacker is to learn how to make the decision of picking a suitable rewiring action when at the state st. This can be done by learning a policy network to get the probability p(at|st, . . . , s1) and sample the rewiring operation correspondingly. Modelling in this way, the decision making at a state st is dependant on all its previous states, which could be difficult to model due to the long-term dependency. It is easy to notice that the intermediate states st are all predicted to have the same label as the original graph. Thus, we can treat each of the states as a brand new graph to be attacked regardless of what leads to it. That is to say, the decision making at the state st can be solely dependant on the current state, p(at|st, . . . , s1) = p(at|st). Thus, we model the process of attack as a Markov Decision Process (MDP) Sutton & Barto (2018). Hence, we adopt reinforcement learning to learn how to make effective decisions. We name the proposed framework as ReWatt. The key elements of the environment for the reinforcement learning are defined as follows:
State Space The state space of the environment consists of all the intermediate graphs generated after the possible rewiring operations. Action Space The action space consists of the valid rewiring operations as defined in Definition 1. State Transition Dynamics Given an action (rewiring operation) at = {vfir, vsec, vthi} at state st. The next state st+1 is achieved by deleting the edge between vfir and vsec in the current state st and adding an edge to connect vfir with vthi. Reward Design The main goal of the attacker is to make the classifier f(·) predict a different label than originally predicted. We also encourage the attacker to take as few actions as possible so that
the modification to the graph structure is minimal. Thus, we assign a positive reward when the attack is successful and assign a negative reward for each action step taken. The reward R(st, at) is given as
R(st, at) = { 1 if f(st) 6= f(s1); nr if f(st) = f(s1).
where nr is the negative reward to penalize each step taken. Similar to how we set a flexible rewiring budget K, here we propose to use nr = − 1K = − 1 p·|E| , which depends on the size of the graph.
Termination The attack process will stop either when the number of actions reaches the budget K or the attacker successfully “changed” the label of the slightly modified graph.

heading: 4.3 POLICY NETWORK

text:
In this subsection, we introduce the policy network to learn the policy p(at|st) on top of the graph representations learned by GCN. However, this GCN is different from the target classifier one, since it has 2 convectional layers. To choose a valid proposed rewiring action, we decompose the rewiring action to 3 steps: 1) choosing an edge et = (ve1 , ve2) from the set of edges of the intermediate graph st; 2) determining vet1 or vet2 to be vfirt and the other to be vsect ; and 3) choosing the third node vthit from N 2 st(vfirt)/N 1 st(vfirt). Correspondingly, we decompose p(at|st) as follows
p(at|st) = pedge(et|st) · pfir(vfirt |et, st) · pthi(vthit |vfirt , et, st) (5) We design three policy networks based on GCN to estimate the three distributions in the right hand of the equation equation 5, which will be introduced next. To select an edge from the edge set Est , we generate the edge representation from the node representations Fst ∈ R|Vst |×dF learned by GCN. For an edge e = (ve1 , ve2), the edge representation can be represented as e = concat(ust , h(Fst [e1, :],Fst [e2, :])), where ust is the graph representation of the state st, h(·, ·) is a function to combine the two node representations and concat(·, ·) denotes the concatenation operation. We include ust in the representation of the edge to incorporate the graph information when making the decision. The representation of all the edges in Est can be represented as a matrix Est ∈ R|Est |×2dF , where each row represents an edge. The probability distribution over all the edges can be represented as
pedge(·|st) = softmax(MLP (Est |θedge)), (6)
where we use MLP (·|θedge) to denote a Multilayer Perceptron that maps Est ∈ R|Est |×2dF to a vector in R|Est |, which, after going through the softmax layer, represents the probability of choosing each edge. Let et = (vet1 , vet2) denote the edge sampled according to eq. equation 6. To decide which node is going to be the first node, we estimate the probability distribution over these two nodes as
pfir(·|et, st) = softmax(MLP ([vet1 ,vet2 ] T |θfir)) (7)
where veti = concat(et,Fst [eti, :]) ∈ R3dF for i = 1, 2. The first node can be sampled from the two nodes vet1 , vet2 according to eq. equation 7. We then proceed to estimate the probability distribution p(·|vfirt , et, st). For any node vc ∈ N 2(vfirt)/N 1(vfirt), we use v̂c = concat(vet1 ,Fst [c, :]) to represent it. The representations for all the nodes in N 2(vfirt)/N 1(vfirt) can be represented by a matrix V̂st ∈ R|N 2(vfirt )/N
1(vfirt )|×4dF with each row representing a node. The probability distribution of choosing the third node over all the candidate nodes can be modeled as:
pthi(·|vfirt , et, st) = softmax(MLP (V̂st |θthi)) (8)
The third node vthit can be sampled from the set of candidate nodes N 2(vfirt)/N 1(vfirt) according to the probability distribution in eq equation 8. An action at can be generated by sequentially estimating and sampling from the probability distributions in eq. equation 6, equation 7 and equation 8.

heading: 4.4 PROPOSED FRAMEWORK - REWATT

text:
With the rewiring and the policy network defined above, our overall framework can be summarized as follows. With State st, the Attacker uses GCN to learn node and edge embeddings, which are
used as input to Policy Networks to make decision about the next action. Once the new action is sampled from the policy network, rewiring is performed on st and we arrive in the new state st+1. We query the black-box classifier to get the prediction f(St+1), which is compared with f(s1) to get reward. Policy gradient (Sutton & Barto, 2018) is adopted to learn the policies by maximizing the rewards.

heading: 5 EXPERIMENT

text: In this section, we conduct experiments to evaluate the performance of the proposed framework ReWatt. We also carry out a study to analyze how the trained attacker works. Some empirical investigation on the advancements of the rewiring operation can be found in Appendix C.

heading: 5.1 ATTACK PERFORMANCE

text:
To demonstrate the effectiveness of ReWatt, we conduct experiments on three widely used social network data sets (Kersting et al., 2016) for graph classification, i.e., REDDIT-MULTI-12K, REDDITMULTI-5K and IMDB-MULTI (Yanardag & Vishwanathan, 2015). The statistics can be found in Appendix D. Note that the re-wiring operation (as well as the other operations) may lead to abnormal structure of some kinds of graphs, which can make the graphs invalid, especially for chemical molecules. So in this paper, We avoid chemical related datasets but only use social networks datasets. In the social domain, if the changes are subtle, it is most likely that we will not we will not introduce abnormal structures. Meanwhile, it is straightforward to extend our framework to datsets from the other domains if we have expertise in them. For example, if we know what structures are abnormal, we can use such knowledge to constraint the the state space of the RL framework. We leave it as one future work.
In this work, the classifier we target to attack is the GCN-based classifier as introduced in Section 2. We set the number of layers to 3. We need to train the classifier using a fraction of the data and then treat the classifier as a black box to be attacked. We then use part of the remaining data to train the attacker and use the rest of the data to test the performance of the attacker. Thus, for each data set, we split it into three parts with the ratio of a% : b% : c%, where a% of the data set is used to train the classifier, b% of the data set is used to train the attacker and the remaining c% of the data set is used to test the performance of the attacker. For the REDDIT-MULTI-12K and REDDIT-MULTI5K data sets, we set a = 90, b = 8 and c = 2. As the size of the IMDB-MULTI data set is quite small, to have enough data for testing, we set a = 50, b = 30 and c = 20.
We compare the attacking performance of the proposed framework with the RL-S2V proposed in (Dai et al., 2018), random selection method and some variants of our proposed framework. We briefly describe these baselines: 1) RL-S2V is a reinforcement learning based attack framework (Dai et al., 2018), which allows adding and deleting edges to the graph with a fixed budget for all the graphs; 2) Random denotes an attacker that performs the proposed rewiring operations randomly; 3) Random-s is also based on random rewiring. Note that ReWatt can terminate before using all the budget. We record the actual number of rewiring actions made in our method and only allow the Random-s to take exactly the same number of rewiring actions as ReWatt; 4) ReWatt-n denotes a variant of the ReWatt, where the negative reward is fixed to−0.5 for all the graphs in the testing set; and 5) ReWatt-a is a variant of ReWatt, where we allow any nodes in the graph to be the third node vthit instead of only 2-hop neighbors.
As RL-S2V only allows a fixed budget for the all the graphs, when comparing to it, for ReWatt, we also fix the number of proposed rewiring operations to a fixed number K for all the graphs. Note that a single proposed rewiring operation involves two edges, thus, for a fair comparison, we allow the RL-S2V to take 2K actions (adding/deleting edges). We set K = 1, 2, 3 in the experiments. To compare with the random selection method and the variants of ReWatt, we use flexible budget, more specially, we allow at most p · |Ei| proposed rewiring operations for graph Gi. Here, p is a fixed percentage and we set it to p = 1%, 2%, 3% in our experiments. We use the success rate as measure to evaluate the performance of the attacker. A graph is said to be successfully attacked if its label is changed when it is modified within the given budget.
The results are shown in Table 1. From the table, we can make the following observations: 1) Compared to RL-S2V, ReWatt can perform more effective attacks. Especially, in the IMDB-MULTI
data set, where ReWatt outperforms the RL-S2V with a large margin; 2) ReWatt outperforms the Random method as expected. Especially, ReWatt is much more effective than Random-s which performs exactly the same number of proposed rewiring operations ReWatt. This also indicates that the Random method uses more rewiring operations for successful attacking than ReWatt; 3) The variant ReWatt-a outperforms ReWatt, which means if we do not constraint the rewiring operation to 2-hop neighbors, the performance of ReWatt can be further improved. However, as we discussed in earlier sections, this may lead to more “noticeable” changes of the graph structure; and 4) ReWattn performs worse than our ReWatt, which shows the advancement of using a flexible reward design.

heading: 5.2 ATTACKER ANALYSIS

text:
In this subsection, we carry out experiments to analyze how ReWatt’s change in graph structure affects the graph representation u calculated by eq. equation 2 and the logits P (the output immediately after the softmax layer of the classifier). For convenience, we denote the original graph as Go and the attacked graph as Ga in this section. Correspondingly, the graph representation and logits for the original (attacked) graph are denoted as uo (ua) and Po (Pa), respectively. To measure the difference in graph representation, we used the relative difference in terms of 2-norm defined as RC(uo,ua) = ‖u
a−uo‖2 ‖uo‖2 . The logits denote the probability distribution that the given graph belongs
to each of the classes. Thus, we use the KL-divergence Kullback (1997) to measure the difference between the logits of the original and attacked graphs KL(Po,Pa) = C∑ i=1 Po[i] log ( Po[i] Pa[i] ) , where C is the number of classes in the data set and P[i] denotes the logit for the i-th class.
We perform the experiments on the REDDIT-MULTI-12K data set under the setting of allowing at most 3% · |E| proposed rewiring operations. The results for the graph representation and logits are shown in Figure 1 and Figure 2, respectively. The graphs in the testing set are separated in two groups, one group contains all the graphs successfully attacked by ReWatt (shown in Figure 1a and Figure 2a), and the other one contains those survived from ReWatt’s attack (shown in Figure 1b and Figure 2b). Note that, for comparison, we also include the results of Random-s on these two groups of graphs. In these figures, a single point represents a testing graph, the x-axis is the ratio M|E| , where M is the number of rewiring operations ReWatt used before the attacking process terminating. Note that M can be smaller than the budget as the process terminates once the attack successes.
As we can observe from the figures, compared with the Random-s, ReWatt can make more changes to both the graph representation and logits, using exactly the same number of proposed rewiring operations. Comparing Figure 1a with Figure 1b, we find that the perturbation generated by ReWatt affects the graph representation a lot even when it fails to attack the graph. This means our attack is perturbing the graph structure in a right way to fool the classifier, although it fails potentially due to the limited budget. Similar observation can be made when we compare Figure 2a with Figure 2b.

heading: 6 RELATED WORK

text:
In recent years, adversarial attacks on deep learning models have attracted increasing attention in the area of computer vision. Many deep models are found to be easily fooled by adversarial samples, which are generated by adding deliberately designed unnoticeable perturbation to normal im-
ages (Szegedy et al., 2013; Goodfellow et al., 2014). More algorithms with different level access to the target classifier have been proposed, including white-box attack models, which have access to the gradients (Moosavi-Dezfooli et al., 2016; Kurakin et al., 2016; Carlini & Wagner, 2017) and black-box attack model, which have limited access to the target classifier (Chen et al., 2017; Cheng et al., 2018; Ilyas et al., 2018).
Most of the aforementioned works are focusing in the computer vision domain, where the data sample can be represented in the continues space. Few attention has been payed into the discrete data structure such as graphs. Graph Neural Networks have been shown to bring impressive advancements to many different graph related tasks such as node classification and graph classification. Recent researches show that the graph neural networks are also venerable to adversarial attacks. (Zügner et al., 2018) proposed a greedy algorithm to perform adversarial attack to node classification task. Their algorithm tries to change the label of a target node by modifying both the graph structure and node features. (Dai et al., 2018) proposed a deep reinforcement learning based attacker to attack both the node classification and the graph classification task. (Zügner & Günnemann, 2019) designed an algorithm to impair the overall performance of node classification based on meta learning. All the three mentioned methods modify the graph structure by adding or deleting edges. A more recent work Wang et al. (2018) on attacking node classifications proposed to modify the graph structure by adding fake nodes. In this work, we propose to modify the graph structure using rewiring, which is shown to make less noticeable changes to the graph structure.

heading: 7 CONCLUSION

text: In this paper, we proposed a graph rewiring operation, which affect the graph structure in a less noticeable way than adding/deleting edges. The rewiring operation preserves some basic graph properties such as number of nodes and number of edges. We then designed an attacker ReWatt based on the rewiring operations using reinforcement learning. Experiments in 3 real world data sets show the effectiveness of the proposed framework. Analysis on how the graph representation and logits change while the graph being attacked provide us with some insights of the attacker.

heading: A GRAPH LAPLACIAN BASED MEASURES

text:
Many important graph properties are based on the eigenvalues of the Laplacian matrix of a graph (Chan & Akoglu, 2016). Here we list few:
• Algebraic Connectivity The algebraic connectivity of a graph G is the second-smallest eigenvalue of its Laplacian matrix (Fiedler, 1973). Note that we only consider connected graphs in this work, so it is always larger than 0. The larger the algebraic connectivity is, the more difficult it is to separate the graph into components (i.e., more edges need to be removed). The algebraic connectivity has previously been applied to measure network robustness Sydney et al. (2013).
• Effective Graph Resistance The effective graph resistance is a graph measure derived from the field of electric circuit analysis, where it is defined as the summation of effective resistance over all node pairs (Ellens et al., 2011). The effective graph resistance can be represented using the eigenvalues of Laplacian matrix as follows (Ellens et al., 2011)
Re = |V| · |V|∑ i=2 λi. (9)
By Corollary 2, we can represent the change of the algebraic connectivity λ2 as:
∆λ2 = (2x2[fir]− x2[thi]− x2[sec])(x2[sec]− x2[thi]) (10)
According to the above discussion, ∆λ2 is expected to be smaller for the operation of rewiring to 2-hop neighbor. Thus, the rewiring to 2-hop neighbor operation is expected to perturb the algebraic connectivity less compared with adding an edge between two nodes that are far away from each other. A similar argument can be built for effective graph resistance.

heading: B PROOF OF COLLARY 1

text:
Corollary 2. For a given graph G with Laplacian matrix L, one proposed rewiring operation (vfir, vsec, vthi) affects the eigen-value λi by ∆λi, for i = 1, . . . , |V|, where
∆λi = (2xi[fir]− xi[thi]− xi[sec])(xi[sec]− xi[thi]) (11)
where xi[index] denotes the index-th value of the eigenvector xi.
Proof. Let ∆L denotes the change in the Laplacian matrix after applying the rewiring operation (vfir, vsec, vthi) to graph G. Then we have ∆L[fir, sec] = ∆L[sec, fir] = 1, ∆L[fir, thi] = ∆L[thi, fir] = −1, ∆L[sec, sec] = −1, ∆L[thi, thi] = 1 and 0 elsewhere. Thus
∆λi = x T i ∆Lxi
= 2xi[fir]xi[sec]− xi[sec]2 + xi[thi]2 − 2xi[fir]xi[thi] = xi[thi]
2 − xi[sec]2 + 2xi[fir](xi[sec]− xi[thi]) = (2xi[fir]− xi[thi]− xi[sec])(xi[sec]− xi[thi])
which completes the proof.

heading: C EMPIRICAL INVESTIGATION OF THE REWIRING OPERATION

text:
In this section, we conduct experiments to empirically show the advancements of the proposed rewiring operator compared with the adding/deleting edge operator. We compare them from two perspectives: 1) connectivity after the attack and 2) change in eigenvalues after the attack. The experiments are carried out on the REDDIT-MULTI-12K dataset. On each of the graph successfully attacked by ReWatt, we perform exactly the same number of deleting/adding edge operator on it. For connectivity, the average number of components in the clean graphs is 2.6, this number becomes 3.02 after the rewiring attack while it becomes 5.2 after the deleting/adding edges attack. On the other hand, only 20% of the graphs get more disconnected (having more components) after ReWattattack than the original ones, while 87% of the graphs get more disconnected after the adding/deleting edges attack. Clearly, the rewiring operator is less likely to disconnect the graph. The comparison of the change in eigenvalues is shown in Figure 3, where we compare the change in different eigenvalues of the graphs after these two attacks. Specifically, we first compute the average relative change in the i-th eigenvalue after both attacks as follows:
rλi = |λorii − λattacki |
λorii , (12)
where λorii denotes the i-th eigenvalue of the clean graph while λ attack i denotes the i-th eigenvalue of the attacked graph. We then take the average of the above value over all the succeeded graphs, which we denoted as r̄λi . Specially, we use r̄ re λi to denote the average change ratio after ReWatt while using r̄d/aλi to denote the average change ratio after deleting/adding edge attack. To compare the these two attacks, we calculate r̄d/aλi /r̄ re λi
and the results are shown in Figure 3. The results show that in most of the cases, the deleting/adding edges attack makes much more changes to the eigenvalues as the value r̄d/aλi /r̄ re λi is way larger than 1.
By conducting these two experiments, we empirically conclude that the proposed re-wiring operator makes more subtle changes to graphs than existing methods.

heading: D STATISTICS OF THE DATASETS

text: The statistics of the datasets are given in Table 2. In this table, #nodes denotes the average number of nodes over all graphs and #edges denotes the average number of edges over all graphs. ACC denotes the mean of Average Clustering Coefficient (ACC) over all graphs. GCC denotes the mean of Global Clustering Coefficient (GCC) over all graphs.


summaries: The authors address the problem of efficiently employing the SURE estimator as a network training regularizer. They show that for CNN autoencoders this can be efficiently computed. Their other contribution is a bagging/boosting technique which is proved to avoid trivial solutions. The proposed architecture, motivated by the theoretical statements, is shown to outperform classic and 2019 state of the art image reconstruction algorithms in MRI and EDX.

summaries: The authors consider an encoder decoder setup for linear deblurring problem and propose efficient boosting estimators. Specifically, they use the Stein's unbiased risk estimator for the problem when the noise is gaussian. In the case when the encoder and decoder is represented by a convolutional neural network with RELU activations, they show how they can exploit the recent theoretical results that show the kernel type results to make their procedure efficient. They then propose using a set of models (boosting) and prove that the boosted loss function lower bounds the "nonboosted" loss function.

summaries: This paper proposed a piecewise linear close form expression for the Stein’s unbiased risk estimator and use this formulation to construct a new Encoder-decoder convolutional neural network. The author claimed that this closely related to bagging. Improved experimental results on two inverse problems are presented. Overall, the experiment results are encouraging but the paper need clarification on a few points.

abstractText: Encoder-decoder convolutional neural networks (CNN) have been extensively used for various inverse problems. However, their prediction error for unseen test data is difficult to estimate a priori, since the neural networks are trained using only selected data and their architectures are largely considered blackboxes. This poses a fundamental challenge in improving the performance of neural networks. Recently, it was shown that Stein’s unbiased risk estimator (SURE) can be used as an unbiased estimator of the prediction error for denoising problems. However, the computation of the divergence term in SURE is difficult to implement in a neural network framework, and the condition to avoid trivial identity mapping is not well defined. In this paper, inspired by the finding that an encoderdecoder CNN can be expressed as a piecewise linear representation, we provide a close form expression of the unbiased estimator for the prediction error. The close form representation leads to a novel bootstrap and aggregation scheme to prevent a neural network from converging to an identity mapping so that it can enhance the performance. Experimental results show that the proposed algorithm provides consistent improvement in various inverse problems.

authors:
Eirikur Agustsson
Radu Timofte

title: Ntire 2017 challenge on single image super-resolution: Dataset and study

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops,

title: A new look at the statistical model identification

venue: In Selected Papers of Hirotugu Akaike,

authors:
Martin Anthony
Peter L Bartlett

title: Neural network learning: Theoretical foundations

venue: cambridge university press,

authors:
Minhyung Cho
Jaehyung Lee

title: Riemannian approach to batch normalization

venue: In Advances in Neural Information Processing Systems,

authors:
David L Donoho
Iain M Johnstone

title: Adapting to unknown smoothness via wavelet shrinkage

venue: Journal of the american statistical association,

title: The estimation of prediction error: covariance penalties and cross-validation

venue: Journal of the American Statistical Association,

authors:
Mark A Griswold
Peter M Jakob
Robin M Heidemann
Mathias Nittka
Vladimir Jellus
Jianmin Wang
Berthold Kiefer
Axel Haase

title: Generalized autocalibrating partially parallel acquisitions (GRAPPA)

venue: Magn. Reson. Med.,

authors:
Kerstin Hammernik
Teresa Klatzer
Erich Kobler
Michael P Recht
Daniel K Sodickson
Thomas Pock
Florian Knoll

title: Learning a variational network for reconstruction of accelerated MRI data

venue: Magnetic resonance in medicine,

authors:
Yoseob Han
Jong Chul Ye

title: Framing U-Net via deep convolutional framelets: Application to sparse-view CT

venue: IEEE transactions on medical imaging,

title: k-Space Deep Learning for Accelerated MRI

venue: IEEE Transactions on Medical Imaging (in press),

authors:
Muhammad Haris
Gregory Shakhnarovich
Norimichi Ukita

title: Deep back-projection networks for super-resolution

authors:
Elad Hoffer
Ron Banner
Itay Golan
Daniel Soudry

title: Norm matters: efficient and accurate normalization schemes in deep networks

authors:
Sergey Ioffe
Christian Szegedy

title: Batch normalization: Accelerating deep network training by reducing internal covariate shift

venue: In International Conference on Machine Learning,

authors:
Jaakko Lehtinen
Jacob Munkberg
Jon Hasselgren
Samuli Laine
Tero Karras
Miika Aittala
Timo Aila

title: Noise2Noise: learning image restoration without clean data

authors:
Michael Lustig
David Donoho
John M Pauly

title: Sparse MRI: The application of compressed sensing for rapid MR imaging

authors:
Matthew T McDowell
Ill Ryu
Seok Woo Lee
Chongmin Wang
William D Nix
Yi Cui

title: Studying the kinetics of crystalline silicon nanoparticle lithiation with in situ transmission electron microscopy

venue: Advanced Materials,

authors:
Takeru Miyato
Toshiki Kataoka
Masanori Koyama
Yuichi Yoshida

title: Spectral normalization for generative adversarial networks

venue: arXiv preprint arXiv:1802.05957,

authors:
Sathish Ramani
Thierry Blu
Michael Unser

title: Monte-Carlo SURE: a black-box optimization of regularization parameters for general denoising algorithms

venue: IEEE Transactions on image processing,

authors:
Petre Stoica
Yngve Selen

title: Model-order selection: a review of information criterion rules

authors:
Ryan J Tibshirani
Saharon Rosset

title: Excess optimism: How biased is the apparent error

authors:
Chul Ye
Woon Kyoung Sung

title: gredient for fast stylization

venue: arXiv preprint arXiv:1607.08022,

authors:
Jong Chul Ye
Yoseob Han
Eunju Cha

title: Deep convolutional framelets: A general deep learning

heading: 1 INTRODUCTION

text:
Suppose that the measurement x is corrupted with additive noises:
x = µ+w, w ∼ N (0, σ2I), (1)
where µ ∈ Rn denotes the unknown mean vector, and σ2 is the variance. Consider a deep neural network model F (x) := FΘ(x) with the weight Θ, which is trained with the data x producing an estimate µ̂ = FΘ(x). Then, our goal is to estimate the prediction error:
Err(µ̂) = Ex,x∗‖x∗ − µ̂‖2 = Ex,x∗‖x∗ − F (x)‖2, (2)
which quantifies how well µ̂ can predict a test data x∗, independently drawn from the same distribution of x (Efron, 2004; Tibshirani & Rosset, 2018). The problem of estimating the prediction error is closely related to the generalizability of neural network (Anthony & Bartlett, 2009). Moreover, this problem is tightly linked to the classical approaches for model order selection in statistics literature (Stoica & Selen, 2004). One of the most investigated statistical theories to address this question is so-called covariance penalties approaches such as Mallow’s Cp (Mallows, 1973), Akaike’s information criterion (AIC) (Akaike, 1974), Stein’s unbiased risk estimate (SURE) (Donoho & Johnstone, 1995), etc.
This paper is particularly interested in estimating the prediction error of encoder-decoder convolutional neural networks (E-D CNNs) such as U-Net (Ronneberger et al., 2015; Han & Ye, 2018; Ye & Sung, 2019). E-D CNNs have been extensively used for various inverse problems (Ye et al., 2018). Recent theoretical results showed that, thanks to the ReLU nonlinearities, the input space is partitioned into non-overlapping regions so that input images in each region share the same linear representation, but not across different partitions (Ye & Sung, 2019).
One of the most important contributions of this paper is that this property can be exploited to derive a simplified form of prediction error estimator that can be used for neural network training. In particular, we provide a close form expression for the divergence term in the SURE estimator, which
suggests that the divergence term can be neglected if a proper batch normalization is used. Furthermore, the simplified form of the SURE estimate for the prediction error leads to a bootstrap and aggregation scheme to prevent the CNN from converging to a trivial solution so that it can improve the neural network performance. The applicability of the new method is demonstrated using various inverse problems such as accelerated MRI, energy-dispersive X-ray spectroscopic imaging, deconvolution, and etc, which clearly show that our method can significantly improve the image quality compared to the existing approaches.

heading: 2 RELATED WORKS

heading: 2.1 STEIN RISK UNBIASED ESTIMATION FOR PREDICTION ERROR

text:
The Stein Risk Unbiased Estimator (SURE) for the prediction error can be represented by (Donoho & Johnstone, 1995):
ŜURE(x) := ‖x− F (x)‖2 + 2σ2div{F (x)}, (3)
where div(·) denotes the divergence. Recently, the authors in (Soltanayev & Chun, 2018) employed the SURE for CNN-based image denoising without references by minimizing the following loss:
`SURE(Θ) := 1
P P∑ i=1 ‖x(i) − FΘ(x(i))‖2 + 2σ2div{FΘ(x(i))}. (4)
where {x(i)}Pi=1 denotes the training samples. Although the application of SURE for unsupervised denoising is an important advance in theory, there are several practical limitations. In particular, due to the difficulty of calculating the divergence term, the authors relied on MonteCarlo SURE (Ramani et al., 2008) which calculates the divergence term using MonteCarlo simulation. This introduces additional hyperparameters, on which the final results critically depend.

heading: 2.2 PIECEWISE LINEAR REPRESENTATION BY E-D CNN WITH RELUS

text:
Recently, the authors in (Ye & Sung, 2019) showed that the output of a CNN composed of κ layer of encoder and decoder without skipped connection can be represented by the following basis-like representation:
y := F (x) = ∑ i 〈bi(x),x〉b̃i(x) = B̃(x)B(x)>x, (5)
where bi(x) and b̃i(x) denote the i-th column of the following frame basis and its dual:
B(x) = E1Σ1(x)E2 · · ·Σκ−1(x)Eκ, (6) B̃(x) = D1Σ̃1(x)D2 · · · Σ̃κ−1(x)Dκ, (7)
where Σl(x) and Σ̃l(x) denote the diagonal matrix with 0 and 1 values that are determined by the ReLU output in the previous convolution steps. El andDl refer to the encoder and decoder matrices, respectively, which are determined by pooling (resp. unpooling) operation and convolution filters (Ye & Sung, 2019). For the case of encoder-decoder CNN with the skipped connection, similar basis expression can be obtained Ye & Sung (2019).
Note that the expression (5) is nonlinear due to the dependency on the input signal x. Moreover, as the ReLU nonlinearity is applied after the convolution operation, the on-and-off activation pattern of each ReLU determines a binary partition of the feature space across the hyperplane that is determined by the convolution. Accordingly, one of the most important observation in Ye & Sung (2019) is that the input space X is partitioned into multiple non-overlapping regions so that input images for each region share the same linear representation, but overall representation is still non-linear. This implies that two different input images may be automatically switched to two distinct linear representations that are different from each other.

heading: 3 MAIN CONTRIBUTION

text: In (3) and (4), the calculation of the divergence term is not trivial for general neural networks. This is why the authors in (Soltanayev & Chun, 2018) employed the MonteCarlo SURE. Thanks to the basis-like expression in (5), here we show that there exists a simple explicit form of the divergence term for the case of E-D CNNs. Then, the batch normalization is shown to make the divergence term trivial.

heading: 3.1 DIVERGENCE SIMPLIFICATION IN SURE

text:
In Proposition 6 of (Ye & Sung, 2019), the authors show that ∂F (x)/∂x = B̃(x)B(x)> for the case of E-D CNN with ReLUs. Accordingly, we have
div{F (x)} = Tr ( ∂F (x)
∂x
) = Tr ( B̃(x)B(x)> ) = Tr ( B(x)>B̃(x) ) =
∑ i 〈bi(x), b̃i(x)〉, (8)
where Tr(A) denotes the trace ofA.
This close form representation (8) leads to a further simplification of divergence term by exploiting the property of the batch normalization. Recall that batch normalization has been extensively used to make the training stable (Ioffe & Szegedy, 2015; Hoffer et al., 2018; Cho & Lee, 2017; Miyato et al., 2018; Ulyanov et al., 2016). It has been consistently shown that the batch normalization is closely related to the norm of the Jacobian matrix ∂F (x)/∂x, which is equal to B̃(x)B(x)>. For example, in their original paper (Ioffe & Szegedy, 2015), the authors conjectured that “Batch Normalization may lead the layer Jacobians to have singular values close to 1, which is known to be beneficial for training”. By extending the idea in (Ioffe & Szegedy, 2015) to multiple layers, the batch normalization can be understood as to make the covariance of the network output and input similar. For example, for the uncorrelated input with Cov[x(i)] = σ2I , the batch normalization may result in Cov[F (x(i))] ' σ2I . Furthermore, for sufficiently smaller σ, we have
σ2I ' Cov[F (x(i))] = Cov [ B̃(x(i))B(x(i))>x(i)x>(i)B(x(i))B̃(x(i))> ] = B̃(x(i))B(x(i))>Cov [ x(i)x>(i) ] B(x(i))B̃(x(i))>
= σ2B̃(x(i))B(x(i))>B(x(i))B̃(x(i))>,
because the corresponding piecewise linear representation does not change for the small perturbation of the input (Ye & Sung, 2019). Therefore, we have
B̃(x(i))B(x(i))> ' I, since B̃(x(i))B(x(i))> is a square matrix. This suggests that
divEL{F (x(i))} = ∑ i 〈bi(x(i)), b̃i(x(i))〉 = Tr ( B̃(x(i))B(x(i))> ) ' n, (9)
where n is the dimension of the input signal. As the resulting divergence term is just a constant, the contribution of the divergence term is considered trivial and can be neglected.

heading: 3.2 BAGGING ESTIMATOR

text:
Another important drawback of SURE-based denoising network (4) is that it is difficult to prevent the network from learning a trivial identity mapping. More specifically, if FΘ(x) = x, the cost function in (4) becomes zero. One way to avoid this trivial solution is to guarantee that the divergence term at the optimal network parameter should be negative. However, given that the divergence term comes from the degree of the freedom (Efron, 2004) and the amount of excess optimism in estimating the prediction error (Tibshirani & Rosset, 2018), enforcing negative value may be unnatural. Moreover, with the divergence simplification in (9), the cost function (4) can be simplified as
`SURE−ED(Θ) := 1
P P∑ i=1 ‖x(i) − FΘ(x(i))‖2 + 2σ2n (10)
so that it is much apparent that a trivial solution for (10) is FΘ(x) = x.
To prevent the neural network from converging to this trivial solution, here we propose a bootstrap aggregation (bagging) scheme (Breiman, 1996). Bagging is a classical machine learning technique which uses bootstrap sampling and aggregation of the results to reduce the variance and to improve the accuracy of the base learner. The rationale for bagging is that it may be easier to train several simple weak learners and combine them into a more complex learner than to learn a single strong learner. More specifically, we use the following bagging estimator:
µ̃(x) = K∑ k=1 wkFΘ(Lkx), (11)
and the corresponding prediction error estimate:
Err(µ̃) := Ex,x∗‖x∗ − µ̃‖2 = Ex,x∗‖x∗ − K∑ k=1 wkFΘ(Lkx)‖2,
where {Lk}Kk=1 denotes the diagonal matrix whose diagonal elements are either 0 or 1 depending on the bootstrap subsampling patterns, and {wk}Kk=1 is the corresponding weights. The corresponding empirical prediction error estimate is then given by
` (Θ, {wk}) := 1
P P∑ i=1 ‖x(i) − K∑ k=1 wkFΘ(Lkx (i))‖2, (12)
Note that x(i) 6= Lkx(i) due to the subsampling patterns so that the optimal neural network FΘ that minimizes (12) cannot be the trivial identity mapping. Furthermore, the following proposition shows that the prediction error for the bagging estimator (11) is not bigger than the average of the individual error estimate. Proposition 1. Let wk ≥ 0 and ∑ k wk = 1. Then, we have
1
P P∑ i=1 ∑ k wk‖x(i) − F (Lkx(i))‖2 ≥ 1 P P∑ i=1 ∥∥∥x(i) −∑wkF (Lkx(i))∥∥∥2 . Proof. For any x ∈ {x(i)}Pi=1, we have∑
k wk‖x− F (Lkx)‖2 = x>x− 2x> ∑ k wkF (Lkx) + ∑ k wk‖F (Lkx)‖2
≥ x>x− 2x> ∑ k wkF (Lkx) + ‖ ∑ wkF (Lkx)‖2
= ∥∥∥x−∑wkF (Lkx)∥∥∥2 ,
where we use the Jensen’s inequality for the inequality. By summing up for all training data {x(i)}Pi=1, we conclude the proof.
The gap increases more when the F (Lkx) provides diverse output for each realization of the index Lk (Breiman, 1996). In fact, the authors in (Ye & Sung, 2019) showed that the input space results in non-overlapping partitions with different linear representations so that by changing the subsampling pattern Lk, the distinct representation may be selected, which can make the corresponding bagging estimate more accurate.

heading: 4 IMPLEMENTATION DETAILS

text:
The final loss function for our bagging estimator is given by
` (Θ,Ξ) := 1
P P∑ i=1 ‖x(i) − K∑ k=1 wk(Ξ)FΘ(x, Lk)‖2, (13)
where we also parameterize the weighting using a neural network with parameter Ξ. Although the standard way of aggregation in bagging estimator is a simple average of the overall results of the regression network, this may not be the best method when the number of bootstrap subsampling is limited. Instead, we propose a weighted average scheme whose weight is calculated by data attention module so that it efficiently combines all data by adaptively incorporating output from various bootstrap sub-sampling patterns. A schematic diagram of the proposed method is illustrated in Fig. 1, which consists of three building blocks: bootstrap subsampling, a regression network, and an attention network to calculate the weight parameters.
In particular, U-net (Ronneberger et al., 2015) in Fig. 2 was used as our regression network. The network is composed of four stages with convolution, batch normalization, ReLU, and skip connection with concatenation. Each stage is composed of three 3×3 convolution layers followed by batch normalization and ReLU, except for the last layer, which is 1× 1 convolution layer. The number of convolutional filters increases from 64 in the first stage to 1024 in the final stage. To estimate the weight wk, our attention network consists of two fully connected layer. The input dimension of the attention network is R1×1×K followed by the average pooling of the concatenated output of regression network. The number of hidden node is 64, and the final dimension of the output is R1×1×K for aggregation.
The overall network was trained using Adam optimization with the momentum β1 = 0.9 and β2 = 0.999. The proposed network was implemented in Python using TensorFlow library and trained using an NVidia GeForce GTX 1080-Ti graphics processing unit.

heading: 5 EXPERIMENTAL RESULTS

text: Experiments were conducted for various inverse problems such as accelerated magnetic resonance imaging (MRI), energy-dispersive X-ray spectroscopy (EDX) (Solé et al., 2007), and image superresolution in Appendix.

heading: 5.1 ACCELERATED MRI

text:
In accelerated MRI, the goal is to recover high quality MR images from sparsely sampled k-space data to reduce the acquisition time. This problem has been extensively studied using compressed sensing (Lustig et al., 2007), but recently deep learning approaches have been the main research interest due to its excellent performance at significantly reduced run time complexity (Hammernik et al., 2018; Han & Ye, 2019). A standard method for neural network training for accelerated MRI is based on the supervised learning, where the MR images from fully sampled k-space data is used
as reference and subsampled and zero-filled k-space data is used as the input for the neural network. Specifically, we use the R = 13.45 subsampled k-space data as neural network input and the goal is to obtain high resolution images from the sub-sampled k-space data. As a baseline algorithm, the state-of-the-art deep learning algorithm called k-space deep learning (Han & Ye, 2019) is employed, which interpolates the missing k-data using a CNN.
In the proposed method, the accelerated k-space data is further subsampled using bootstrap sampling with the subsampling ratio of 91 %, and the number of bootstrap sample set K was set to 10. The same k-space deep learning network (Han & Ye, 2019) was used for our regression network using bootstrap samples. We trained the baseline algorithm and our method under the same conditions, except that the proposed network was trained by minimize the loss (13). The initial learning rate was set to 10−2, and it was divided by half at every 50 epochs until it reaches to around 10−4. The training data was generated from Human Connectome Project (HCP) MR dataset (https://db.humanconnectome.org). Among the 34 subject data sets, 28 subject data sets were used for training and validation. The other subject data sets were used for test. We also provide reconstruction results by GRAPPA (Griswold et al., 2002), which is a standard k-space interpolation method in MRI.
Thanks to the bagging, the proposed method provided nearly perfect reconstruction results compared to other algorithms as shown in Fig. 3. Moreover, its average peak signal-to-noise ratio (PSNR) and structural similarity (SSIM) index for entire test dataset significantly outperform existing methods as shown in Table 1.
To demonstrate the optimality of the proposed architecture, we performed extensive ablation study. For the ablation study, we used 13 subject data sets from HCP MR dataset, from which seven subject data sets were used for training and validation and the remaining dataset were used for test. The ablation study was performed by excluding some structures from the network and applying the same training processes. First, our theory says that the performance improvement of our method increases with the number of bootstrap subsamples K. To verify this, we performed comparative studies with different K values such as 1, 2, 4 and 10. As shown in Table 2, the proposed network provided better reconstruction results as the number of bootstrap sample set K increased. This clearly confirmed the importance of the bootstrap subsampling. Second, our derivation suggests that the batch normalization plays a key role to simplify the divergence term. As shown in Fig. 4 and Table 3, the lack of batch normalization produces a significantly degraded image with an average PSNR drop from 40.047 dB to 25.290 dB. This verified the important role of batch normalization.
We also evaluated the importance of the attention network to calculate the weights. With standard bagging, the final output is a simple average of the entire network output for each bootstrap subsamples without the attention network. As shown in Fig. 4 and Table 3, the simple average produced blurry results than by the attention network and the PSNR and SSIM values were worse. This confirmed that the important of attention network for the weight calculation.

heading: 5.2 ENERGY-DISPERSIVE X-RAY SPECTROSCOPY IMAGING

text:
As for another experiment, we use the energy-dispersive X-ray spectroscopy (EDX) (Solé et al., 2007) data set which were measured by scanning transmission electron microscopy. EDX (Solé et al., 2007) is an analytical technique used for spectroscopic characterization of a sample. It relies on the emission of characteristic X-rays from a specimen that is generated by a high-energy beam of electrons. Specifically, the incident beam may eject an electron from the inner shell of atoms. Then, an electron from an outer shell then fills the hole, and the energy difference may be released in the form of an X-ray. As the energies of the X-rays are characteristic of the energy differences that are determined by the atomic structure of the emitting element, EDX is widely used for nano-scale quantitative and qualitative elemental composition analysis by measuring X-ray radiation from the interaction with high energy electron and the material (McDowell et al., 2012).
However, in EDX, the specimens can be quickly damaged by the high energy electrons, so the acquisition time should be reduced to its minimum. This usually results in very noisy and even incomplete images as shown in Fig. 5(a). Therefore, the goal of this experiment was to remove the noise and reconstruct high resolution EDX images. The main technical difficulty is that there are no noiseless reference data. Due to the lots of missing photons, a widely used approach for EDX analysis is a kernel regression method using an average kernel as shown in Fig. 5(b). Unfortunately, this often results in severe blurring. Existing unsupervised learning methods such as SURE network (Soltanayev & Chun, 2018) and Noise2Noise (Lehtinen et al., 2018) cannot be used for this purpose, since there are no specific noise models for the EDX and the noiseless clean data is not available for Noise2Noise training. In fact, this difficulty of EDX denoising was our original motivation for this work. For our network training and inference, we use bootstrap subsampled images from the measurement image in Fig. 5(a). In addition, we used the measurement image in Fig. 5(a) as the label for training.
We used 28 cases from the EDX dataset. The specimen are composed of quantum-dots, where core and shell consist of Cadmium (Cd), Selenium (Se), Zinc (Zn), and Sulfur (S). The regression network was trained using image patches, whose sizes was 128 × 128. For stable training, the intensity of data was normalized between [0, 1]. The initial learning rate was set to 10−3, and it was divided in
half at every 50 epochs until it reaches around 10−5. For the bootstrap subsampling, the number of random subsampling mask wasK = 30. The regression network was optimized to minimize the loss (13) with respect to Θ first, after which the attention network was trained to properly aggregate the entire interpolated output. As shown in Fig. 5(d), our method successfully produced high resolution images which are significantly better than existing kernel regression methods. Thanks to the bagging procedure, the regression network is believed to learn the measurement statistics so that the network not only removes the noise but also filled in the unmeasured data. We also compared the performance between the standard bagging and the proposed method. As shown in Fig. 5(c) and (d), the weighted averaging from the attention module provides better performance over the the standard bagging that uses the simple average. This confirmed the efficacy of the proposed method.

heading: 6 CONCLUSION

text: In this paper, we proposed a novel bagging scheme of encoder-decoder CNNs for various inverse problems. The algorithm was derived by the observation that the existing SURE-based unsupervised denoising networks have several practical limitations due to the divergence term and potential to converge to a trivial solution. Inspired by the recent discovery of basis-like representation of the encoder-decoder CNN, we provide a simple approximation of the divergence term. This also led to a novel bagging scheme to prevent from converging to the trivial identity mapping. In the implementation, multiple input data were generated by bootstrap subsampling, after which final result are obtained by aggregating the entire output of network using an attention network. Experimental results with accelerated MRI and EDX experiments showed that the proposed method provides consistent improvement for various inverse problems.

heading: A APPENDIX: SUPER-RESOLUTION APPLICATION

text:
Single image super-resolution (SR) is a task to estimate a high-resolution (HR) image from its lowresolution (LR) image. To demonstrate the effectiveness of the proposed method, the proposed bagging scheme was also applied to these problems. Deep Back-Projection Network (DBPN) (Haris et al., 2018) is a recent state-of-the-art method for this applications, so we employed DBPN as our baseline model to improve its performance by the proposed method. The baseline network is trained using DIV2K (Agustsson & Timofte, 2017) with totally 800 training images on the ×2 and ×4 (in both horizontal and vertical directions) super-resolution tasks. The network consists of three modules: initial feature extraction, back-projection stages, and reconstruction. The initial LR feature maps were extracted using the convolution layer of the initial feature extraction module. By applying the sequence of projection units which alters between configuration of LR and HR feature maps, the extensive HR features maps can be obtained. The final HR image was reconstructed using the overall HR feature maps from the projection units.
Training conditions of the baseline algorithm and our method were followed as described in (Haris et al., 2018). Specifically, we used patch processing whose size is 32×32 for LR image. The initial learning rate was set to 10−4, and it was divided by 10 at every 5×105 iterations for total 106 iterations. For the training of our bagging network, the number of random subsampling maskK was set to 32 and 8 for ×2 and ×4 task, respectively. The subsampling ratio for bootstrap sampling was set to 80%. In addition, the entire networks were trained simultaneously to minimize the loss (13).
Thanks to the bootstrapping and aggregation using attention network, the data distribution can be fully exploited to restore the high resolution components, which results in the properly reconstructed details of the image as shown in Fig. 6. As described in Table 4, our method can also improve the quantitative performance of the super-resolution task.