# Towards Revealing Parallel Adversarial Attack on Politician Socialnet of Graph Structure

Authors: Yunzhe Tian; Jiqiang Liu; Endong Tong; Wenjia Niu; Liang Chang; Qi Alfred Chen; Gang Li; Wei Wang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Socialnet becomes an important component in real life, drawing a lot of study issues of security and safety. Recently, for the features of graph structure in socialnet, adversarial attacks on node classification are exposed, and automatic attack methods such as fast gradient attack (FGA) and NETTACK are developed for per-node attacks, which can be utilized for multinode attacks in a sequential way. However, due to the overlook of perturbation influence between different per-node attacks, the above sequential method does not guarantee a global attack success rate for all target nodes, under a fixed budget of perturbation. In this paper, we propose a parallel adversarial attack framework on node classification. We redesign new loss function and objective function for nonconstraint and constraint perturbations, respectively. Through constructing intersection and supplement mechanisms of perturbations, we then integrate node filtering-based P-FGA and P-NETTACK in a unified framework, finally realizing parallel adversarial attacks. Experiments on politician socialnet dataset Polblogs with detailed analysis are conducted to show the effectiveness of our approach.


---

## Body

## 1. Introduction

With the development of Internet and IT technology, an emerging cyber space [1], which refers to the global network of interdependent information technology infrastructures, telecommunications networks, and computer processing systems, is covering most aspects of our daily life nowadays. In such space, as a highly important and detailed representation, various emerging social networks (e.g., Facebook, Twitter, WeChat, and TikTok) are greatly pushing the new revolution of network interconnection and interdependence, as well as the social relations and information propagation [2, 3].Social network is called socialnet in short. Due to the popularity, billions of socialnet users share their personal data and connect with friends and family through various devices and applications. Since the socialnet can be abstracted to a simple kind of graph with features of nodes and edges, many researchers have contributed their efforts to study socialnet and corresponding services based on graph- and workflow-related approaches [4–8]. One of the most frequently applied tasks on graph data is node classification, the goal of which is to predict the labels of the remaining nodes when given a single large graph and the class labels of a few nodes [9]. For example, we can utilize node classification to predict the political labels of politician such as Liberals and Conservatives, according to their socialnet interactions.For node classification in recent years, the graph convolutional network (GCN) [10, 11], a kind of graph neural network (GNN) [12, 13] based on deep learning, has shown a great potential. Unfortunately, such GCN also opens a new door for cyber attacks. Adversarial attacks against GCN are discovered, through few edge perturbations of addition or deletion, and they are uneasy to notice [14]. Furthermore, automatic attack methods are developed to explore effective perturbations including constraint and nonconstraint perturbations. Constraint perturbation refers to the edge perturbation satisfying specific requirements such as node degree distribution of graph [15]. Nonconstraint perturbation means a free perturbation. Accordingly, fast gradient attack (FGA) [16] and NETTACK [17] are typical nonconstraint and constraint methods, respectively. The above methods enable per-node attacks, as well as multinode attacks in a sequential way. However, due to the overlook of perturbation influence between different per-node attacks, the above sequential method does not guarantee a global attack success rate for all target nodes, under a fixed budget of perturbation. Figure 1 shows the differences between sequential and parallel attacks in a motivating example. For the No. 1, 2, and 3 nodes, the attack goal is to change their class labels through changing graph structure with perturbations, including edge addition and edge deletion. We can see that, due to removing the edges from efforts of edge addition in attack of No. 1 node, No. 2 and No. 3 node attacks of sequential attack waste edges perturbations and cause No. 1 node attack to fail with a global attack success rate of 2/3, while the parallel attack considers perturbation influence and has a higher attack success rate with a lower budget.Figure 1
Differences between sequential and parallel attacks in a motivating example.In this work, we are the first to perform multinode attack in a parallel way by integrating two methods P-FGA and P-NETTACK in a unified attack framework. Based on nonconstraint FGA, we redesign a new loss function in P-FGA, which employs CW-loss [18] to replace CE-loss. For P-NETTACK, we utilize the maximum sum of surrogate loss as new objective function to support parallel attack. Moreover, we apply a node filtering mechanism to P-NETTACK and P-FGA, which filters out those nodes that are successfully attacked from target node set. After extracting common perturbations, we also provide a random supplement of perturbations to fill the budget.We experiment on politician socialnet dataset Polblogs [19] of 1222 nodes and 16714 edges, showing the effectiveness of our approach. We find that our approach can achieve a high attack success rate (ASR) of 71.5% at the lowest perturbation budget of 1/5 dsum (dsum is the sum of the degrees of all target nodes), that is over 15% higher than that of NETTACK or FGA, still keeping a satisfied test statistic of 0.005. The filtering mechanism can greatly improve ASR, with nearly 20% average increment. We summarize our contributions as follows: (1)
We give the very first attempt to propose a multinode parallel adversarial attack framework on node classification in socialnet of graph structure, based on considering perturbation influence between per-node attacks.(2)
Node filtering-based nonconstraint P-FGA and node filtering-based constraint P-NETTACK are proposed, and we integrate them into a unified multinode parallel attack framework, through constructing intersection and supplement mechanisms of perturbation.(3)
We evaluate our approach empirically on real dataset of politician socialnet Polblogs. Based on parallel attacking on the graph of 1222 nodes and 16714 edges, we reveal and verify the effectiveness of our approach compared to sequential attacks in terms of attack strength and attack stealthiness.The rest of the paper is structured as follows: Section2 introduces the preliminaries and problem definition. Section 3 proposes a multinode parallel attack framework. Section 4 reports our experiments and evaluations on the politician socialnet dataset Polblogs. In Section 5, we discuss the related works. Finally, Section 6 concludes the work of this paper.


## 2. Preliminaries and Problem Definition

### 2.1. Graph Structure of Socialnet

In real socialnet, one person can have an interaction with others by operations like the following: commenting, reposting, etc. Such interaction can be quantified and qualified, varying from different measurements. For simplicity, we assume that we just use an undirected unweighted edge to denote an interaction existence, constructing graph structure of socialnet (See Figure2). Moreover, we simply assume that one node only has one classification label, and we do not focus on multiple free-label user profile or granularity-based hierarchical user profile [20] in attack scenarios of this paper. Thus, for a socialnet graph, we have a triple G=V,C,A including node set V, label set C, and adjacent matrix A, in which V=v1,v2,…,vn, C=c1,c2,…,cn (V=C=n), and A is shown as follows:(1)A=a11⋯a1n⋮⋱⋮an1⋯ann,aij∈0,1.Figure 2
Illustration of socialnet graph.


### 2.2. Graph Convolutional Network

As a kind of GNN, GCN is an extremely powerful neural network architecture for deep learning on graphs to produce useful feature representations of nodes in networks. Given aG=V,C,A, we can partially delete some node’s label (ci = null) to obtain a new G′=V,C′,A. The goal of node classification is to learn a function Z, which maps each node v∈V to one class (ci=null=0).We use a two-layer GCN to approximate the functionZ: (2)Z=fθA,X=softmaxA^σA^XW1W2,where A^=D˜−1/2A˜D˜−1/2, A˜=A+IN is the adjacent matrix A of the input graph G′ with self-loops added via the identity matrix IN, D˜ii=∑ja˜ij is the degree matrix of A˜, and X is a matrix of node feature vectors. For the graph whose nodes do not have feature attributes, X can be set to an identity matrix IN. W1 and W2 are the trainable weight matrices of the first and second layers, respectively, and σ⋅ is a ReLU activation function. For the semisupervised node classification, the optimal parameters θ=W1,W2 are learnt by minimizing the cross-entropy loss over all labeled examples:(3)Lθ;A,X=−∑v∈VllnZv,cv,where Vl⊆V is the set of nodes with labels, namely, training set, cv is the given true label of node v, and Zv,cv is the probability of assigning class cv to node v.


### 2.3. Problem Definition

Given the attack target setVt⊆V in G′ and perturbation budget Δ, multinode attack on GCN can be regarded as the following optimization problem: (4)A∗=argmaxA∗∑v∈Vtsignmaxc≠cvZv,c−Zv,cv,(5)s.t.∑u<vauv−auv∗≤Δ,(6)u∈Vt∨v∈Vt,whereauv∗≠auv,where maxc≠cvZv,c−Zv,cv>0, sign⋅=1, else sign⋅=0.Formula (4) shows the objective function, aiming to find the optimal adjacent matrix. When the sum of misclassification for all target nodes is maximum, it means a most successful multinode attack. Formulas (5) and (6) show the constraints that should be satisfied. Formula (5) requires that the number of edge perturbations be no more than Δ (a predefined constant). Formula (6) has the constraint that any edge perturbation must be linked to a target attack node.Figure 3
The parallel adversarial attack framework against GCN-based node classification.


## 2.1. Graph Structure of Socialnet

In real socialnet, one person can have an interaction with others by operations like the following: commenting, reposting, etc. Such interaction can be quantified and qualified, varying from different measurements. For simplicity, we assume that we just use an undirected unweighted edge to denote an interaction existence, constructing graph structure of socialnet (See Figure2). Moreover, we simply assume that one node only has one classification label, and we do not focus on multiple free-label user profile or granularity-based hierarchical user profile [20] in attack scenarios of this paper. Thus, for a socialnet graph, we have a triple G=V,C,A including node set V, label set C, and adjacent matrix A, in which V=v1,v2,…,vn, C=c1,c2,…,cn (V=C=n), and A is shown as follows:(1)A=a11⋯a1n⋮⋱⋮an1⋯ann,aij∈0,1.Figure 2
Illustration of socialnet graph.


## 2.2. Graph Convolutional Network

As a kind of GNN, GCN is an extremely powerful neural network architecture for deep learning on graphs to produce useful feature representations of nodes in networks. Given aG=V,C,A, we can partially delete some node’s label (ci = null) to obtain a new G′=V,C′,A. The goal of node classification is to learn a function Z, which maps each node v∈V to one class (ci=null=0).We use a two-layer GCN to approximate the functionZ: (2)Z=fθA,X=softmaxA^σA^XW1W2,where A^=D˜−1/2A˜D˜−1/2, A˜=A+IN is the adjacent matrix A of the input graph G′ with self-loops added via the identity matrix IN, D˜ii=∑ja˜ij is the degree matrix of A˜, and X is a matrix of node feature vectors. For the graph whose nodes do not have feature attributes, X can be set to an identity matrix IN. W1 and W2 are the trainable weight matrices of the first and second layers, respectively, and σ⋅ is a ReLU activation function. For the semisupervised node classification, the optimal parameters θ=W1,W2 are learnt by minimizing the cross-entropy loss over all labeled examples:(3)Lθ;A,X=−∑v∈VllnZv,cv,where Vl⊆V is the set of nodes with labels, namely, training set, cv is the given true label of node v, and Zv,cv is the probability of assigning class cv to node v.


## 2.3. Problem Definition

Given the attack target setVt⊆V in G′ and perturbation budget Δ, multinode attack on GCN can be regarded as the following optimization problem: (4)A∗=argmaxA∗∑v∈Vtsignmaxc≠cvZv,c−Zv,cv,(5)s.t.∑u<vauv−auv∗≤Δ,(6)u∈Vt∨v∈Vt,whereauv∗≠auv,where maxc≠cvZv,c−Zv,cv>0, sign⋅=1, else sign⋅=0.Formula (4) shows the objective function, aiming to find the optimal adjacent matrix. When the sum of misclassification for all target nodes is maximum, it means a most successful multinode attack. Formulas (5) and (6) show the constraints that should be satisfied. Formula (5) requires that the number of edge perturbations be no more than Δ (a predefined constant). Formula (6) has the constraint that any edge perturbation must be linked to a target attack node.Figure 3
The parallel adversarial attack framework against GCN-based node classification.


## 3. Multinode Parallel Attack Framework

Our multinode parallel attack framework is shown in Figure3. Firstly, given an original graph G′=V,C′,A as defined in Section 2.1, we train a GCN for node classification task, and we obtain C, in which all nodes are labeled with prediction, and record G into testing result as ground truth. Then, given a target node set Vt⊆V, we utilize P-FGA and P-NETTACK to perturb the original graph, attacking target nodes in Vt. In each iteration of nonconstraint P-FGA method, based on GCN-gradient information of the adjacent matrix A, we select the pair of nodes vi,vj of maximum absolute value of gradient to perform perturbation (edge deletion or edge addition), generating a new adversarial graph GP−FGAadv by the generator. In each iteration of constraint P-NETTACK, to ensure keeping the perturbations unnoticeable and preserving the important structural characteristics, we firstly compute the candidate perturbation set Cpert to ensure the similar node degree distribution after perturbation execution. Then, according to our redesigned objective function, from candidate perturbation set, we greedily select the optimal perturbation vm,vn, which obtains the highest objective score, generating a new adversarial graph GP−NETTACKadv by the generator.In the filtering mechanism, after each perturbation of P-FGA or P-NETTACK, the new predicted labels should be compared with the testing result to determine the attack effect. For those nodes that are successfully attacked, such mechanism filters them out from target node setVt to form a new target node set Vt′, ignoring those nodes in the next gradient/objective function computation and perturbation selection. Such process is repeated until the perturbation budget Δ is reached. DP−FGA and DP−NETTACK are perturbation sets based on P-FGA and P-NETTACK, respectively. To integrate DP−FGA and DP−NETTACK and generate unified perturbations, we provide an intersection mechanism to extract common perturbations and a perturbation supplement mechanism to fill the perturbation budget Δ. Finally, the integrated perturbation set Dcomb is used to realize effective multinode parallel adversarial attacks.


### 3.1. P-FGA Method

In our P-FGA, to adapt to the multinode attack, we redesign a new loss functionLmulti for attack target set Vt, which employs CW-loss [18] to replace CE-loss and takes all target nodes into consideration (see equation (7)).(7)Lmulti=∑v∈Vtmaxc≠cvlnZv,c−lnZv,cv.Following the gradient-based idea of original FGA, based on the new loss functionLmulti for multinode attack, we firstly calculate the partial derivatives with respect to the element aij of adjacency matrix A and further obtain gradient matrix GM, and its element gij can be calculated by(8)gij=∂Lmulti∂aij.Considering that the adjacency matrix is symmetric and its gradient matrix should also be symmetric, thus, we have(9)g^ij=g^ji=gij+gji2,i≠j,0,i=j,g˜ij=g^ij×−2⋅aij+1,where g˜ij forms GM˜. A bigger value of multinode loss function Lmulti corresponds to worse prediction results for the target nodes in Vt. And edge perturbations along the direction of the gradient can make the loss increase more faster locally. That is, for a positive gradient g^ij, adding the edge between the pair of nodes vi,vj can increase the loss. Similarly, for a negative gradient g^ij, deleting the edge also increases the loss.However, since the adjacent matrixA is binary discrete and aij∈0,1, not all edges can be perturbed along the direction of the gradient. For example, for a pair of nodes vi,vj who have positive/negative gradient (i.e., g^ij>0/g^ij<0) and meanwhile are connected/disconnected (i.e., aij=1/aij=0), we cannot further add/delete the edge along the direction of the gradient. Thus, we design equation (9); for a positive gradient g^ij, when aij=0, g˜ij is positive; when aij=1, g˜ij is negative. Similarly, for a negative gradient g^ij, when aij=1, g˜ij is positive; when aij=0, g˜ij is negative. Only the positive g˜ij enables the addition/deletion of the edge along the direction of the gradient. Then, for edge addition or deletion, we pick the optimal edge vm,vn, vm∈Vt∨vn∈Vt, with the maximum g˜mn, and the adjacent matrix A is updated to A′ by changing the corresponding value (amn and anm) to a different binary value (see equation (10)).(10)amn′=anm′=1−amn.The pseudocode for P-FGA is given in Algorithm1.Algorithm 1: Parallel fast gradient attack (P-FGA).
Input: G′=V,C′,A, attack target set Vt, perturbation budget ΔOutput: perturbation set DP−FGA(1)
Train the GCN modelZ on original graph G′(2)
InitializeA0=A(3)
Initialize perturbation setDP−FGA(4)
forh=1 to Δdo(5)
//GCN-based Gradient Computation(6)
Calculate multi-node target loss functionLmulti=∑v∈Vtmaxc≠cvlnZv,c−lnZv,cv(7)
ConstructGM˜h−1 based on the Ah−1:gijh−1=∂Lmulti/∂aijh−1, g^ijh−1=g^jih−1=gijh−1+gjih−1/2i≠j0i=j,g˜ijh−1=g^ijh−1×−2⋅aijh−1+1(8)
//Perturbation Selection(9)
Selecte∗=vm,vn where vm∈Vt∨vn∈Vt, having the maximum g˜mnh−1(10)
//Perturbation Execution(11)
Obtain the adjacency matrixAh by amnh=anmh=1−amnh−1(12)
Generate a new adversarial graphGh=V,C′,Ah(13)
Adde∗ to DP−FGA(14)
end(15)
returnDP−FGA


### 3.2. P-NETTACK Method

In constraint P-NETTACK, we use test statisticΛG′,Gadv to determine whether our generated adversarial graph Gadv=V,C′,A′ and original graphG′=V,C′,A have similar node degree distribution of pow-law distribution px∝x−α, in which px denotes the probability of certain degree x, and α refers to scaling parameter. The test statistic Λcan be calculated based on the following formulas.(11)αG=1+DG′⋅∑di∈DG′logdidmin−1/2−1,(12)lDG′=DG′⋅logαG′+DG⋅αG′⋅logdmin+αG′+1∑di∈DG′logdi,(13)ΛG′,Gadv=−2⋅lDG′∪​DGadv+2⋅lDG′+lDGadv.In equation (11), dmin is the minimum degree that a node has to be considered in the power-law test, and DG′=dvG′|v∈V,dvG′≥dmin is the multiset containing the list of node degrees, where dvG′ is the degree of node v in G′ [21]. Equation (12) is used to evaluate the log-likelihood lDG′ for the sample DG′ [22]. Then, we can get final test statistic by equation (13). Similar to NETTACK, we only accept adversarial graph Gadv whose degree distribution fulfils ΛG′,Gadv<0.004 and thus obtain the candidate perturbation set Cpert. In our P-NETTACK, the edge perturbations in Cpert must be linked to an attack target node.To efficiently select the optimal perturbation fromCpert, NETTACK utilizes a linear surrogate model Z′ to approximate the nonlinear GCN model Z by removing the activation function σ⋅. Z′ is calculated as follows:(14)Z′=softmaxA^A^XW1W2=softmaxA^2XW.In our P-NETTACK, given an attack target setVt, we utilize the sum of single surrogate losses for each v∈Vt as the new surrogate loss to support multinode attack:(15)LmultiA;X,W,Vt=∑v∈Vtmaxc≠cvA^2XWv,c−A^2XWv,cv,where A^2XWvt,c is the value of class c given to the node vt by the surrogate model. The multinode scoring function that evaluates the multinode surrogate loss obtained after adding/deleting an edge e=i,j∈Cpert is defined as(16)smultie;A,Vt≔LmultiA′;X,W,Vt,where A is updated to A′ by aij′=aji′=1−aij. Following the greedy approximate scheme in NETTACK, during each iteration, we select the optimal perturbation that has the highest value of multinode scoring function from the candidate perturbation set Cpert to execute. The above processes including candidate perturbation computation, determining optimal perturbation, and perturbation execution are repeated until the perturbation budget Δ is reached. The pseudocode for P-NETTACK is given in Algorithm 2.Algorithm 2: Parallel NETTACK (P-NETTACK).
Input: G′=V,C′,A, attack target set Vt, perturbation budget ΔOutput: perturbation setDP−NETTACK(1)
Train the surrogate modelZ' on original graph G′ to obtain W(2)
InitializeA0=A(3)
Initialize perturbation setDP−NETTACK(4)
forh=1 to Δdo(5)
Construct the valid candidate perturbations setCpertΛG′,Gh<0.004andvi∈Vt∨vj∈Vtwherevi,vj∈Cpert,Gh=V,C′,Ahandaijh=ajih=1−aijh−1(6)
Selecte∗=vm,vn of the maximum multi-node scoring function value in Cperte∗=vm,vn=argmaxe∈Cpertsmultie;Ah−1,Vt(7)
Obtain the adjacency matrixAh by amnh=anmh=1−amnh−1(8)
Generate a new adversarial graphGh=V,C′,Ah(9)
Adde∗ to DP−NETTACK(10)
end(11)
returnDP−NETTACK


### 3.3. Filtering Mechanism

In this part, we propose a filtering mechanism that filters out target nodes that are successfully attacked from the target node set. After each perturbation, by the filtering mechanism, we obtain a filtered attack target setVt′, which is used in the next iteration. If there are no nodes in Vt′, which means that all target nodes have been attacked successfully, and we reset the attack target set Vt′ to the original attack target set Vt. The pseudocode for filtering mechanism is given in Algorithm 3.Algorithm 3: Filtering mechanism.
Input: perturbed graph Gadv=V,C,A′, attack target set Vt, node classification model ZOutput: filtered attack target set Vt′(1)
InitializeVt′=Vt(2)
for each ν∈Vtdo(3)
Predict the label ofν in Gadv by Z(4)
ifcv of ground truth is not equal to prediction result then(5)
Removev from Vt′ //filtering(6)
end(7)
ifVt′==0then(8)
Vt′=Vt //reset(9)
returnVt′


### 3.4. Intersection and Supplement Mechanism

In this section, we construct intersection and supplement mechanism of perturbations. Given the perturbation setsDP−FGA and DP−NETTACK under a fixed perturbation budget Δ, we first utilize intersection mechanism to extract their common perturbations Dcomb. In general, the number of common perturbations is less than perturbation budget Δ. Thus, we should provide a perturbation supplement mechanism to fill the budget.We denoteDP−NETTACK′ as the set consisting of the perturbations in DP−NETTACK but not in Dcomb. Similarly, DP−FGA′ contains the perturbations in DP−FGA but not in Dcomb. Δ′ is the difference between Δ and the number of Dcomb. Besides, we use a supplementary factor k to control the proportion of supplementary perturbations from DP−NETTACK′. Specially, we randomly select k⋅Δ′ and Δ′−k⋅Δ′ perturbations from DP−NETTACK′ and DP−FGA′, respectively, and add them to the Dcomb, forming the final unified perturbation set. The pseudocode for intersection and supplement mechanism of perturbations is given in Algorithm 4.Algorithm 4: Intersection and supplement mechanism.
Input: DP−FGA, DP−NETTACK, supplementary factor k, perturbation budget ΔOutput: Dcomb(1)
Execute the intersection ofDP−FGA and DP−NETTACK to obtain DcombDcomb=DP−FGA∩DP−NETTACK(2)
ifDcomb<Δthen(3)
ObtainDP−NETTACK′=DP−NETTACK−Dcomb(4)
ObtainDP−FGA′=DP−FGA−Dcomb(5)
CalculateΔ′=Δ−Dcomb(6)
Randomly addk⋅Δ′ perturbations from DP−Nettack′ to Dcomb(7)
Randomly addΔ′−k⋅Δ′ perturbations from DD−FGA′ to Dcomb(8)
returnDcomb


## 3.1. P-FGA Method

In our P-FGA, to adapt to the multinode attack, we redesign a new loss functionLmulti for attack target set Vt, which employs CW-loss [18] to replace CE-loss and takes all target nodes into consideration (see equation (7)).(7)Lmulti=∑v∈Vtmaxc≠cvlnZv,c−lnZv,cv.Following the gradient-based idea of original FGA, based on the new loss functionLmulti for multinode attack, we firstly calculate the partial derivatives with respect to the element aij of adjacency matrix A and further obtain gradient matrix GM, and its element gij can be calculated by(8)gij=∂Lmulti∂aij.Considering that the adjacency matrix is symmetric and its gradient matrix should also be symmetric, thus, we have(9)g^ij=g^ji=gij+gji2,i≠j,0,i=j,g˜ij=g^ij×−2⋅aij+1,where g˜ij forms GM˜. A bigger value of multinode loss function Lmulti corresponds to worse prediction results for the target nodes in Vt. And edge perturbations along the direction of the gradient can make the loss increase more faster locally. That is, for a positive gradient g^ij, adding the edge between the pair of nodes vi,vj can increase the loss. Similarly, for a negative gradient g^ij, deleting the edge also increases the loss.However, since the adjacent matrixA is binary discrete and aij∈0,1, not all edges can be perturbed along the direction of the gradient. For example, for a pair of nodes vi,vj who have positive/negative gradient (i.e., g^ij>0/g^ij<0) and meanwhile are connected/disconnected (i.e., aij=1/aij=0), we cannot further add/delete the edge along the direction of the gradient. Thus, we design equation (9); for a positive gradient g^ij, when aij=0, g˜ij is positive; when aij=1, g˜ij is negative. Similarly, for a negative gradient g^ij, when aij=1, g˜ij is positive; when aij=0, g˜ij is negative. Only the positive g˜ij enables the addition/deletion of the edge along the direction of the gradient. Then, for edge addition or deletion, we pick the optimal edge vm,vn, vm∈Vt∨vn∈Vt, with the maximum g˜mn, and the adjacent matrix A is updated to A′ by changing the corresponding value (amn and anm) to a different binary value (see equation (10)).(10)amn′=anm′=1−amn.The pseudocode for P-FGA is given in Algorithm1.Algorithm 1: Parallel fast gradient attack (P-FGA).
Input: G′=V,C′,A, attack target set Vt, perturbation budget ΔOutput: perturbation set DP−FGA(1)
Train the GCN modelZ on original graph G′(2)
InitializeA0=A(3)
Initialize perturbation setDP−FGA(4)
forh=1 to Δdo(5)
//GCN-based Gradient Computation(6)
Calculate multi-node target loss functionLmulti=∑v∈Vtmaxc≠cvlnZv,c−lnZv,cv(7)
ConstructGM˜h−1 based on the Ah−1:gijh−1=∂Lmulti/∂aijh−1, g^ijh−1=g^jih−1=gijh−1+gjih−1/2i≠j0i=j,g˜ijh−1=g^ijh−1×−2⋅aijh−1+1(8)
//Perturbation Selection(9)
Selecte∗=vm,vn where vm∈Vt∨vn∈Vt, having the maximum g˜mnh−1(10)
//Perturbation Execution(11)
Obtain the adjacency matrixAh by amnh=anmh=1−amnh−1(12)
Generate a new adversarial graphGh=V,C′,Ah(13)
Adde∗ to DP−FGA(14)
end(15)
returnDP−FGA


## 3.2. P-NETTACK Method

In constraint P-NETTACK, we use test statisticΛG′,Gadv to determine whether our generated adversarial graph Gadv=V,C′,A′ and original graphG′=V,C′,A have similar node degree distribution of pow-law distribution px∝x−α, in which px denotes the probability of certain degree x, and α refers to scaling parameter. The test statistic Λcan be calculated based on the following formulas.(11)αG=1+DG′⋅∑di∈DG′logdidmin−1/2−1,(12)lDG′=DG′⋅logαG′+DG⋅αG′⋅logdmin+αG′+1∑di∈DG′logdi,(13)ΛG′,Gadv=−2⋅lDG′∪​DGadv+2⋅lDG′+lDGadv.In equation (11), dmin is the minimum degree that a node has to be considered in the power-law test, and DG′=dvG′|v∈V,dvG′≥dmin is the multiset containing the list of node degrees, where dvG′ is the degree of node v in G′ [21]. Equation (12) is used to evaluate the log-likelihood lDG′ for the sample DG′ [22]. Then, we can get final test statistic by equation (13). Similar to NETTACK, we only accept adversarial graph Gadv whose degree distribution fulfils ΛG′,Gadv<0.004 and thus obtain the candidate perturbation set Cpert. In our P-NETTACK, the edge perturbations in Cpert must be linked to an attack target node.To efficiently select the optimal perturbation fromCpert, NETTACK utilizes a linear surrogate model Z′ to approximate the nonlinear GCN model Z by removing the activation function σ⋅. Z′ is calculated as follows:(14)Z′=softmaxA^A^XW1W2=softmaxA^2XW.In our P-NETTACK, given an attack target setVt, we utilize the sum of single surrogate losses for each v∈Vt as the new surrogate loss to support multinode attack:(15)LmultiA;X,W,Vt=∑v∈Vtmaxc≠cvA^2XWv,c−A^2XWv,cv,where A^2XWvt,c is the value of class c given to the node vt by the surrogate model. The multinode scoring function that evaluates the multinode surrogate loss obtained after adding/deleting an edge e=i,j∈Cpert is defined as(16)smultie;A,Vt≔LmultiA′;X,W,Vt,where A is updated to A′ by aij′=aji′=1−aij. Following the greedy approximate scheme in NETTACK, during each iteration, we select the optimal perturbation that has the highest value of multinode scoring function from the candidate perturbation set Cpert to execute. The above processes including candidate perturbation computation, determining optimal perturbation, and perturbation execution are repeated until the perturbation budget Δ is reached. The pseudocode for P-NETTACK is given in Algorithm 2.Algorithm 2: Parallel NETTACK (P-NETTACK).
Input: G′=V,C′,A, attack target set Vt, perturbation budget ΔOutput: perturbation setDP−NETTACK(1)
Train the surrogate modelZ' on original graph G′ to obtain W(2)
InitializeA0=A(3)
Initialize perturbation setDP−NETTACK(4)
forh=1 to Δdo(5)
Construct the valid candidate perturbations setCpertΛG′,Gh<0.004andvi∈Vt∨vj∈Vtwherevi,vj∈Cpert,Gh=V,C′,Ahandaijh=ajih=1−aijh−1(6)
Selecte∗=vm,vn of the maximum multi-node scoring function value in Cperte∗=vm,vn=argmaxe∈Cpertsmultie;Ah−1,Vt(7)
Obtain the adjacency matrixAh by amnh=anmh=1−amnh−1(8)
Generate a new adversarial graphGh=V,C′,Ah(9)
Adde∗ to DP−NETTACK(10)
end(11)
returnDP−NETTACK


## 3.3. Filtering Mechanism

In this part, we propose a filtering mechanism that filters out target nodes that are successfully attacked from the target node set. After each perturbation, by the filtering mechanism, we obtain a filtered attack target setVt′, which is used in the next iteration. If there are no nodes in Vt′, which means that all target nodes have been attacked successfully, and we reset the attack target set Vt′ to the original attack target set Vt. The pseudocode for filtering mechanism is given in Algorithm 3.Algorithm 3: Filtering mechanism.
Input: perturbed graph Gadv=V,C,A′, attack target set Vt, node classification model ZOutput: filtered attack target set Vt′(1)
InitializeVt′=Vt(2)
for each ν∈Vtdo(3)
Predict the label ofν in Gadv by Z(4)
ifcv of ground truth is not equal to prediction result then(5)
Removev from Vt′ //filtering(6)
end(7)
ifVt′==0then(8)
Vt′=Vt //reset(9)
returnVt′


## 3.4. Intersection and Supplement Mechanism

In this section, we construct intersection and supplement mechanism of perturbations. Given the perturbation setsDP−FGA and DP−NETTACK under a fixed perturbation budget Δ, we first utilize intersection mechanism to extract their common perturbations Dcomb. In general, the number of common perturbations is less than perturbation budget Δ. Thus, we should provide a perturbation supplement mechanism to fill the budget.We denoteDP−NETTACK′ as the set consisting of the perturbations in DP−NETTACK but not in Dcomb. Similarly, DP−FGA′ contains the perturbations in DP−FGA but not in Dcomb. Δ′ is the difference between Δ and the number of Dcomb. Besides, we use a supplementary factor k to control the proportion of supplementary perturbations from DP−NETTACK′. Specially, we randomly select k⋅Δ′ and Δ′−k⋅Δ′ perturbations from DP−NETTACK′ and DP−FGA′, respectively, and add them to the Dcomb, forming the final unified perturbation set. The pseudocode for intersection and supplement mechanism of perturbations is given in Algorithm 4.Algorithm 4: Intersection and supplement mechanism.
Input: DP−FGA, DP−NETTACK, supplementary factor k, perturbation budget ΔOutput: Dcomb(1)
Execute the intersection ofDP−FGA and DP−NETTACK to obtain DcombDcomb=DP−FGA∩DP−NETTACK(2)
ifDcomb<Δthen(3)
ObtainDP−NETTACK′=DP−NETTACK−Dcomb(4)
ObtainDP−FGA′=DP−FGA−Dcomb(5)
CalculateΔ′=Δ−Dcomb(6)
Randomly addk⋅Δ′ perturbations from DP−Nettack′ to Dcomb(7)
Randomly addΔ′−k⋅Δ′ perturbations from DD−FGA′ to Dcomb(8)
returnDcomb


## 4. Experiments

### 4.1. Dataset and Environment

We use the well-known politician socialnet Polblogs [19] as our experimental dataset to evaluate our methods. The basic statistics are summarized in Table 1, and only the largest connected component is considered. We randomly choose 20% nodes in the dataset as the labeled nodes for training. The testing set consists of the rest of the unlabeled nodes.Table 1
Dataset statistics of Polblogs.
NodesEdgesClassesMaximum degreeMinimum degreeAverage degree1222167142351127.4We also give our experimental environment configuration in Table2.Table 2
Experimental environment configuration.
Experimental environmentEnvironmental configurationOperating systemWindows 10CPU2.4 GHz intel core i5Memory16 GBHardware500GSoftwarePython 3.6


### 4.2. Target Parameters and Baselines

Our GCN as an attack target is constructed based on the program on the Github (https://github.com/tkipf/gcn). We train all models for a maximum of 200 epochs using Adam [23] with a learning rate of 0.01. We initialize weights using the initialization described in Glorot and Bengio [24] and accordingly (row-) normalize input feature vectors.We compare our proposed attack method with comprehensive state-of-the-art adversarial attack methods including FGA and NETTACK. We use codes of the baselines provided by their authors.(i)
FGA [16] extracts the gradient of pairwise nodes based on the adversarial network and then selects the pair of nodes with maximum absolute link gradient to realize the attack and update the adversarial network.(ii)
NETTACK [17] designs adversarial attacks based on a static surrogate model and greedily selects the optimal perturbation through preserving the key structural features of a graph.(iii)
Random attack randomly perturbs the edges related to target nodes.


## 4.1. Dataset and Environment

We use the well-known politician socialnet Polblogs [19] as our experimental dataset to evaluate our methods. The basic statistics are summarized in Table 1, and only the largest connected component is considered. We randomly choose 20% nodes in the dataset as the labeled nodes for training. The testing set consists of the rest of the unlabeled nodes.Table 1
Dataset statistics of Polblogs.
NodesEdgesClassesMaximum degreeMinimum degreeAverage degree1222167142351127.4We also give our experimental environment configuration in Table2.Table 2
Experimental environment configuration.
Experimental environmentEnvironmental configurationOperating systemWindows 10CPU2.4 GHz intel core i5Memory16 GBHardware500GSoftwarePython 3.6


## 4.2. Target Parameters and Baselines

Our GCN as an attack target is constructed based on the program on the Github (https://github.com/tkipf/gcn). We train all models for a maximum of 200 epochs using Adam [23] with a learning rate of 0.01. We initialize weights using the initialization described in Glorot and Bengio [24] and accordingly (row-) normalize input feature vectors.We compare our proposed attack method with comprehensive state-of-the-art adversarial attack methods including FGA and NETTACK. We use codes of the baselines provided by their authors.(i)
FGA [16] extracts the gradient of pairwise nodes based on the adversarial network and then selects the pair of nodes with maximum absolute link gradient to realize the attack and update the adversarial network.(ii)
NETTACK [17] designs adversarial attacks based on a static surrogate model and greedily selects the optimal perturbation through preserving the key structural features of a graph.(iii)
Random attack randomly perturbs the edges related to target nodes.


## 5. Evaluations

### 5.1. Evaluation Metric

#### 5.1.1. Attack Success Rate (ASR)

ASR is the ratio of the number of successfully attacked nodes to the total number of target nodes, which can be calculated as follows:(17)ASR=nsuccVt,where nsucc denotes the number of successfully attacked nodes and Vt is the attack target set.


#### 5.1.2. Average Attack Speed (AAS)

AAS refers to average running time of each attack, and it can be calculated as follows:(18)AAS=ttotalΔ,where ttotal denotes the total attack time on target set Vt, and Δ is the perturbation budget.


#### 5.1.3. Test StatisticΛ

Test statisticΛ is used to evaluate attack stealthiness (see equation (13)), which measures the structural difference between original graph and adversarial graph. A smaller Λ means that the degree distribution of the adversarial graph is more similar to the original graph’s, and thus, the perturbations are more unnoticeable.


### 5.2. ASR Analysis

In our experiments, each attack target set consists of five target nodes, and all of them are from the test set that has been classified correctly in original graph. We divided the perturbation budgets into five levels according to the sum of degrees of all target nodes in the attack target setVt, i.e., Δ∈1/5dsum, 2/5dsum, 3/5dsum, 4/5dsum, 5/5dsum.As we can see from Table3, for each Δ, we compare ASR among P∗, P-NETTACK (k = 1), P-FGA (k = 0), NETTACK, FGA, and Random Attack, in which P∗ is the best value of our unified approach. From Algorithm 4, we know that if k = 1, our unified method can be simplified as P-NETTACK; and if k = 0, our unified method can be simplified as P-FGA. P∗ has the highest ASR values of 0.715, 0.880, 1, and 1 at Δ1, Δ2,Δ4,Δ5, respectively. When there is a quite low budget Δ1, the ASR of P∗ is over 15% higher than that of NETTACK or FGA. P-NETTACK (k = 1) and P-FGA (k = 0) have extremely close values for all budget Δ. Figure 4 shows the visual comparison in Table 3.Table 3
ASR comparison betweenP∗, P-NETTACK, P-FGA, NETTACK, FGA, and Random Attack.
Perturbation budgetP∗P-NETTACK (k = 1)P-FGA (k = 0)NETTACKFGARandom attackΔ1=1/5dsum0.715 (k = 0.5)0.7100.7150.4530.4800.0Δ2=2/5dsum0.880 (k = 0.7)0.8670.8740.8570.8770.024Δ3=3/5dsum0.987 (k = 0.8)0.9630.9530.9950.9850.025Δ4=4/5dsum10.99310.9920.9920.012Δ5=5/5dsum10.9921110.01Figure 4
ASR comparison under different perturbation budgetΔ.In Table4, we can see that, for Δ1, Δ2,Δ3, our approach achieves highest ASR values of 0.715 (k = 0.5), 0.880 (k = 0.7), and 0.987 (k = 0.8), respectively. At Δ4,Δ5, for many k settings, ASR values can reach 1. For example, at Δ4, ASR = 1 when k = 0.1, 0.2, 0.3, 0.4, 0.5, 0.7. Figure 5 shows the detailed ASR variation along with k increment.Table 4
ASR variation under different supplementary factork.
Perturbation budgetΔk = 0.1k = 0.2k = 0.3k = 0.4k = 0.5k = 0.6k = 0.7k = 0.8k = 0.9Δ1 = 1/5 dsum0.7050.7130.7060.7110.7150.7030.6950.6980.697Δ2 = 2/5 dsum0.8640.8740.8780.8650.860.8790.8800.8670.878Δ3 = 3/5 dsum0.9580.9670.9620.9780.9820.9830.9730.9870.978Δ4 = 4/5 dsum111110.99710.9970.997Δ5 = 5/5 dsum1111110.9970.9980.998Figure 5
k influence on ASR value among different perturbation budgets Δ.


### 5.3. Test StatisticsΛ Analysis

As we can see from Table5, P-NETTACK (k = 1) has the lowest Λ values of 0.003, 0.005, 0.005, and 0004 at Δ1, Δ2,Δ4,Δ5, respectively. Although P-NETTACK (k = 1) and NETTACK have the same constraint mechanism, theΛ values of P-NETTACK (k = 1) are always lower than those of NETTACK. For P-FGA (k = 0) and FGA, which have not enforced the constraint, the Λ values are extremely higher and continue increasing with the increment of Δ. Figure 6 shows the visual comparison in Table 5.Table 5
Test statisticsΛ comparison between P∗, P-NETTACK, P-FGA, NETTACK, and FGA.
Perturbation budgetΔP∗P-NETTACK (k = 1)P-FGA (k = 0)NETTACKFGAΔ1 = 1/5 dsum0.0050.0030.0350.0080.022Δ2 = 2/5 dsum0.0060.0050.1000.0130.091Δ3 = 3/5 dsum0.0050.0070.1470.0170.126Δ4 = 4/5 dsum0.0050.0050.1660.0160.134Δ5 = 5/5 dsum0.0060.0040.2040.0140.156Figure 6
Test statisticsΛ comparison under different perturbation budgets Δ.In Table6, we can see that, for all Δ∈Δ1,Δ2,Δ3,Δ4,Δ5, with the increment of k, the test statistics Λ keep decreasing, towards better results. Figure 7 clearly shows the Λ variation along with k increment.Table 6
Test statisticsΛ variation under different supplementary factors k.
Perturbation budgetΔk = 0.1k = 0.2k = 0.3k = 0.4k = 0.5k = 0.6k = 0.7k = 0.8k = 0.9Δ1 = 1/5 dsum0.0330.0260.0180.0170.0140.0110.0080.0060.005Δ2 = 2/5 dsum0.0920.0590.0500.0350.0260.0200.0100.0080.006Δ3 = 3/5 dsum0.1240.0980.0810.0450.0330.0210.0190.0060.005Δ4 = 4/5 dsum0.1380.1100.0770.0660.0350.0270.0170.0110.005Δ5 = 5/5 dsum0.1600.1200.1010.0800.0510.0280.0190.0130.006Figure 7
k influence on test statistics Λ value among different perturbation budgets Δ.


### 5.4. AAS Analysis

As we can see from Table7, P-NETTACK is the most time-consuming adversarial attack method, with an average of 11.17s of each attack. Since the candidate perturbation set of P-NETTACK is larger than that of NETTACK, the AAS of P-NETTACK is much higher than that of NETTACK. Instead, P-FGA and FGA have extremely close AAS values, 0.17s and 0.14s, respectively.Table 7
AAS comparison between P-NETTACK, P-FGA, NETTACK, and FGA.
MethodsAAS (second)P-NETTACK11.17P-FGA0.17NETTACK1.30FGA0.14


### 5.5. Filtering Mechanism Analysis

In Table8, we can see that, for all Δ∈Δ1,Δ2,Δ3,Δ4,Δ5, the filtering mechanism can greatly improve ASR, with nearly 20% average increment. And for P-FGA, the ASR values at Δ2 are higher than those of P-FGA (without filtering) at Δ5. Thus, we can see that the filtering mechanism plays a quite important role for P-NETTACK and P-FGA.Table 8
Filtering influence onASR of P-NETTACK and P-FGA.
Perturbation budgetΔP-NETTACKP-NETTACK (without filtering)P-FGAP-FGA (without filtering)Δ1 = 1/5 dsum0.7100.450.7150.551Δ2 = 2/5 dsum0.8670.6620.8740.653Δ3 = 3/5 dsum0.9630.7360.9530.721Δ4 = 4/5 dsum0.9930.81810.759Δ5 = 5/5 dsum0.9920.88710.813


## 5.1. Evaluation Metric

### 5.1.1. Attack Success Rate (ASR)

ASR is the ratio of the number of successfully attacked nodes to the total number of target nodes, which can be calculated as follows:(17)ASR=nsuccVt,where nsucc denotes the number of successfully attacked nodes and Vt is the attack target set.


### 5.1.2. Average Attack Speed (AAS)

AAS refers to average running time of each attack, and it can be calculated as follows:(18)AAS=ttotalΔ,where ttotal denotes the total attack time on target set Vt, and Δ is the perturbation budget.


### 5.1.3. Test StatisticΛ

Test statisticΛ is used to evaluate attack stealthiness (see equation (13)), which measures the structural difference between original graph and adversarial graph. A smaller Λ means that the degree distribution of the adversarial graph is more similar to the original graph’s, and thus, the perturbations are more unnoticeable.


## 5.1.1. Attack Success Rate (ASR)

ASR is the ratio of the number of successfully attacked nodes to the total number of target nodes, which can be calculated as follows:(17)ASR=nsuccVt,where nsucc denotes the number of successfully attacked nodes and Vt is the attack target set.


## 5.1.2. Average Attack Speed (AAS)

AAS refers to average running time of each attack, and it can be calculated as follows:(18)AAS=ttotalΔ,where ttotal denotes the total attack time on target set Vt, and Δ is the perturbation budget.


## 5.1.3. Test StatisticΛ

Test statisticΛ is used to evaluate attack stealthiness (see equation (13)), which measures the structural difference between original graph and adversarial graph. A smaller Λ means that the degree distribution of the adversarial graph is more similar to the original graph’s, and thus, the perturbations are more unnoticeable.


## 5.2. ASR Analysis

In our experiments, each attack target set consists of five target nodes, and all of them are from the test set that has been classified correctly in original graph. We divided the perturbation budgets into five levels according to the sum of degrees of all target nodes in the attack target setVt, i.e., Δ∈1/5dsum, 2/5dsum, 3/5dsum, 4/5dsum, 5/5dsum.As we can see from Table3, for each Δ, we compare ASR among P∗, P-NETTACK (k = 1), P-FGA (k = 0), NETTACK, FGA, and Random Attack, in which P∗ is the best value of our unified approach. From Algorithm 4, we know that if k = 1, our unified method can be simplified as P-NETTACK; and if k = 0, our unified method can be simplified as P-FGA. P∗ has the highest ASR values of 0.715, 0.880, 1, and 1 at Δ1, Δ2,Δ4,Δ5, respectively. When there is a quite low budget Δ1, the ASR of P∗ is over 15% higher than that of NETTACK or FGA. P-NETTACK (k = 1) and P-FGA (k = 0) have extremely close values for all budget Δ. Figure 4 shows the visual comparison in Table 3.Table 3
ASR comparison betweenP∗, P-NETTACK, P-FGA, NETTACK, FGA, and Random Attack.
Perturbation budgetP∗P-NETTACK (k = 1)P-FGA (k = 0)NETTACKFGARandom attackΔ1=1/5dsum0.715 (k = 0.5)0.7100.7150.4530.4800.0Δ2=2/5dsum0.880 (k = 0.7)0.8670.8740.8570.8770.024Δ3=3/5dsum0.987 (k = 0.8)0.9630.9530.9950.9850.025Δ4=4/5dsum10.99310.9920.9920.012Δ5=5/5dsum10.9921110.01Figure 4
ASR comparison under different perturbation budgetΔ.In Table4, we can see that, for Δ1, Δ2,Δ3, our approach achieves highest ASR values of 0.715 (k = 0.5), 0.880 (k = 0.7), and 0.987 (k = 0.8), respectively. At Δ4,Δ5, for many k settings, ASR values can reach 1. For example, at Δ4, ASR = 1 when k = 0.1, 0.2, 0.3, 0.4, 0.5, 0.7. Figure 5 shows the detailed ASR variation along with k increment.Table 4
ASR variation under different supplementary factork.
Perturbation budgetΔk = 0.1k = 0.2k = 0.3k = 0.4k = 0.5k = 0.6k = 0.7k = 0.8k = 0.9Δ1 = 1/5 dsum0.7050.7130.7060.7110.7150.7030.6950.6980.697Δ2 = 2/5 dsum0.8640.8740.8780.8650.860.8790.8800.8670.878Δ3 = 3/5 dsum0.9580.9670.9620.9780.9820.9830.9730.9870.978Δ4 = 4/5 dsum111110.99710.9970.997Δ5 = 5/5 dsum1111110.9970.9980.998Figure 5
k influence on ASR value among different perturbation budgets Δ.


## 5.3. Test StatisticsΛ Analysis

As we can see from Table5, P-NETTACK (k = 1) has the lowest Λ values of 0.003, 0.005, 0.005, and 0004 at Δ1, Δ2,Δ4,Δ5, respectively. Although P-NETTACK (k = 1) and NETTACK have the same constraint mechanism, theΛ values of P-NETTACK (k = 1) are always lower than those of NETTACK. For P-FGA (k = 0) and FGA, which have not enforced the constraint, the Λ values are extremely higher and continue increasing with the increment of Δ. Figure 6 shows the visual comparison in Table 5.Table 5
Test statisticsΛ comparison between P∗, P-NETTACK, P-FGA, NETTACK, and FGA.
Perturbation budgetΔP∗P-NETTACK (k = 1)P-FGA (k = 0)NETTACKFGAΔ1 = 1/5 dsum0.0050.0030.0350.0080.022Δ2 = 2/5 dsum0.0060.0050.1000.0130.091Δ3 = 3/5 dsum0.0050.0070.1470.0170.126Δ4 = 4/5 dsum0.0050.0050.1660.0160.134Δ5 = 5/5 dsum0.0060.0040.2040.0140.156Figure 6
Test statisticsΛ comparison under different perturbation budgets Δ.In Table6, we can see that, for all Δ∈Δ1,Δ2,Δ3,Δ4,Δ5, with the increment of k, the test statistics Λ keep decreasing, towards better results. Figure 7 clearly shows the Λ variation along with k increment.Table 6
Test statisticsΛ variation under different supplementary factors k.
Perturbation budgetΔk = 0.1k = 0.2k = 0.3k = 0.4k = 0.5k = 0.6k = 0.7k = 0.8k = 0.9Δ1 = 1/5 dsum0.0330.0260.0180.0170.0140.0110.0080.0060.005Δ2 = 2/5 dsum0.0920.0590.0500.0350.0260.0200.0100.0080.006Δ3 = 3/5 dsum0.1240.0980.0810.0450.0330.0210.0190.0060.005Δ4 = 4/5 dsum0.1380.1100.0770.0660.0350.0270.0170.0110.005Δ5 = 5/5 dsum0.1600.1200.1010.0800.0510.0280.0190.0130.006Figure 7
k influence on test statistics Λ value among different perturbation budgets Δ.


## 5.4. AAS Analysis

As we can see from Table7, P-NETTACK is the most time-consuming adversarial attack method, with an average of 11.17s of each attack. Since the candidate perturbation set of P-NETTACK is larger than that of NETTACK, the AAS of P-NETTACK is much higher than that of NETTACK. Instead, P-FGA and FGA have extremely close AAS values, 0.17s and 0.14s, respectively.Table 7
AAS comparison between P-NETTACK, P-FGA, NETTACK, and FGA.
MethodsAAS (second)P-NETTACK11.17P-FGA0.17NETTACK1.30FGA0.14


## 5.5. Filtering Mechanism Analysis

In Table8, we can see that, for all Δ∈Δ1,Δ2,Δ3,Δ4,Δ5, the filtering mechanism can greatly improve ASR, with nearly 20% average increment. And for P-FGA, the ASR values at Δ2 are higher than those of P-FGA (without filtering) at Δ5. Thus, we can see that the filtering mechanism plays a quite important role for P-NETTACK and P-FGA.Table 8
Filtering influence onASR of P-NETTACK and P-FGA.
Perturbation budgetΔP-NETTACKP-NETTACK (without filtering)P-FGAP-FGA (without filtering)Δ1 = 1/5 dsum0.7100.450.7150.551Δ2 = 2/5 dsum0.8670.6620.8740.653Δ3 = 3/5 dsum0.9630.7360.9530.721Δ4 = 4/5 dsum0.9930.81810.759Δ5 = 5/5 dsum0.9920.88710.813


## 6. Related Work

### 6.1. Politician Socialnet Analysis

In the last few years, social media has become an important political communication channel, attracting a lot of studies. Adamic and Glance [19] analyzed the political blogosphere over the period of two months preceding the US Presidential Election of 2004, measuring the degree of interaction between liberal and conservative blogs and revealing many interesting differences between the two communities such as linking patterns and discussion topics. Caton et al. [25] presented a Social Observatory, which focused on public Facebook profiles of 187 German politicians from five federal parties, observing how they interacted with constituents, measuring sentiment difference between the politicians and their followers, and analyzing online speech patterns of different parties. Stieglitz and Dang-Xuan [26] proposed a social media analytics framework in political context, aiming at continuously collecting, storing, monitoring, analyzing, and summarizing politically relevant user-generated content from different social media to gain a deeper insight into political discourse in social media.However, few studies focus on the security analysis of politician socialnet including politician label classification from the perspective of adversarial graph attack. In comparison, we focus on studying security issues of politician socialnet based on graph structure, targeting a GCN model for politician label classification. Interestingly, politician socialnet is highly vulnerable, and the attack cost is quite cheap only by deleting few existing interactions or adding few new interactions. As an important communication bridge between politicians and citizens, the security analysis of politician socialnet should be highly valued.


### 6.2. Adversarial Attack on Graphs

Recently, some studies have investigated the adversarial attack on neural networks for graph structure. Zügner et al. [17] first revealed the existence of adversarial attack against GCN in node classification task, by slightly modifying graph structure or node attributions to lead to misclassification of a target node. Dai et al. [27] studied test-time nontargeted adversarial attacks on both node classification task and graph classification [28] task based on reinforcement learning. In addition to white-box attack scenario, they also extended their attack method into practical black-box and restricted black-box attack scenarios. Zhang et al. [29] systematically investigated the vulnerability of knowledge graph embedding for the first time. By adding or deleting facts in the knowledge graph, they destroyed the relation prediction model based on representative knowledge graph embedding methods including TransE [30] and RESCAL [31], which is also the first investigation on adversarial attack for heterogeneous graph. Chen et al. [16] explored the adversarial attack on both node classification task and community detection task [32] based on GCN-based gradient information.However, most works about adversarial attack on node classification only focus on the per-node attack, aiming to achieve misclassification for a target node. Although, for those per-node attack methods, the multinode attack can be performed in a sequential way, the perturbation influence of different per-node attacks is overlooked. In comparison, our parallel attack method, which considers all target nodes and perturbation influence at the same time, is better for multinode attack. In addition, as the first to propose the parallel attack on graph structure, our work can provide an inspiration for adversarial attack on other tasks in a parallel way, such as parallel adversarial attack on prediction of multiple links.In addition to the benefits mentioned above, the main drawback of our method is that it is time-consuming, especially the P-NETTACK (see Table7), due to the reason that, at each iteration, more candidate perturbations are taken into computation compared with sequential per-node attack. One of the solutions is developing more computationally efficient test statistic function and scoring function. On the other hand, proposing a perturbation filtering mechanism to reduce the size of multinode candidate perturbations set is also an effective way. In addition, our method does not consider the constraints of attributed graphs [33], such as attribution-based node similarity constraint [34] and attribution cooccurrence constraint [17]. Parallel multinode adversarial attack on attributed graph and Heterogeneous Information Network (HIN) [35] still needs further exploration.


## 6.1. Politician Socialnet Analysis

In the last few years, social media has become an important political communication channel, attracting a lot of studies. Adamic and Glance [19] analyzed the political blogosphere over the period of two months preceding the US Presidential Election of 2004, measuring the degree of interaction between liberal and conservative blogs and revealing many interesting differences between the two communities such as linking patterns and discussion topics. Caton et al. [25] presented a Social Observatory, which focused on public Facebook profiles of 187 German politicians from five federal parties, observing how they interacted with constituents, measuring sentiment difference between the politicians and their followers, and analyzing online speech patterns of different parties. Stieglitz and Dang-Xuan [26] proposed a social media analytics framework in political context, aiming at continuously collecting, storing, monitoring, analyzing, and summarizing politically relevant user-generated content from different social media to gain a deeper insight into political discourse in social media.However, few studies focus on the security analysis of politician socialnet including politician label classification from the perspective of adversarial graph attack. In comparison, we focus on studying security issues of politician socialnet based on graph structure, targeting a GCN model for politician label classification. Interestingly, politician socialnet is highly vulnerable, and the attack cost is quite cheap only by deleting few existing interactions or adding few new interactions. As an important communication bridge between politicians and citizens, the security analysis of politician socialnet should be highly valued.


## 6.2. Adversarial Attack on Graphs

Recently, some studies have investigated the adversarial attack on neural networks for graph structure. Zügner et al. [17] first revealed the existence of adversarial attack against GCN in node classification task, by slightly modifying graph structure or node attributions to lead to misclassification of a target node. Dai et al. [27] studied test-time nontargeted adversarial attacks on both node classification task and graph classification [28] task based on reinforcement learning. In addition to white-box attack scenario, they also extended their attack method into practical black-box and restricted black-box attack scenarios. Zhang et al. [29] systematically investigated the vulnerability of knowledge graph embedding for the first time. By adding or deleting facts in the knowledge graph, they destroyed the relation prediction model based on representative knowledge graph embedding methods including TransE [30] and RESCAL [31], which is also the first investigation on adversarial attack for heterogeneous graph. Chen et al. [16] explored the adversarial attack on both node classification task and community detection task [32] based on GCN-based gradient information.However, most works about adversarial attack on node classification only focus on the per-node attack, aiming to achieve misclassification for a target node. Although, for those per-node attack methods, the multinode attack can be performed in a sequential way, the perturbation influence of different per-node attacks is overlooked. In comparison, our parallel attack method, which considers all target nodes and perturbation influence at the same time, is better for multinode attack. In addition, as the first to propose the parallel attack on graph structure, our work can provide an inspiration for adversarial attack on other tasks in a parallel way, such as parallel adversarial attack on prediction of multiple links.In addition to the benefits mentioned above, the main drawback of our method is that it is time-consuming, especially the P-NETTACK (see Table7), due to the reason that, at each iteration, more candidate perturbations are taken into computation compared with sequential per-node attack. One of the solutions is developing more computationally efficient test statistic function and scoring function. On the other hand, proposing a perturbation filtering mechanism to reduce the size of multinode candidate perturbations set is also an effective way. In addition, our method does not consider the constraints of attributed graphs [33], such as attribution-based node similarity constraint [34] and attribution cooccurrence constraint [17]. Parallel multinode adversarial attack on attributed graph and Heterogeneous Information Network (HIN) [35] still needs further exploration.


## 7. Conclusions

In this paper, we propose a multinode parallel adversarial attack framework on node classification in socialnet of graph structure, based on considering perturbation influence between per-node attacks. Through redesigning new loss function and objective function for nonconstraint and constraint perturbations, respectively, and constructing intersection and supplement mechanisms of perturbation, we integrate nonconstraint P-FGA and constraint P-NETTACK into a unified attack framework. Based on politician socialnet Polblogs of 1222 nodes and 16714 edges, we evaluate attack success rate, test statistics, and average attack speed for our approach. Our approach shows a high attack success rate of 71.5% at the lowest perturbation budget of 1/5dsum, keeping a satisfied test statistic of 0.005.This work severs as a first step to take security analysis on multinode parallel adversarial attack in politician socialnet. It is expected to inspire a series of follow-up studies, including but not limited to (1) adversarial attack on prediction of multiple links; (2) more concrete defense design and implementation.



---

*Source: 6631247-2021-03-09.xml*