The Research On Graph Topology Attack For Node Classification

Graph data is commonly used in many real world applications such as social networks,citation networks,traffic networks,etc.Node classification is one of the most important tasks on graph.In recent years,with the rapid development of neural network and deep learning,graph neural network models have been widely concerned and have been achieved state-of-the-art performance in classification task.However,many researchers have noticed that deep learning is vulnerable to be fooled.Even only slight,deliberate perturbations could lead to wrong predictions.The current adversarial attack mainly focuses on continuous data such as image,voice and text,etc.And only a few adversarial attacks are based on the discrete graph.Due to the graph neural networks been widely applied in security analytics,such as malware detection and fraud user detection,there is still a large space for the study of graph adversarial attack.In this paper,we focus on Deepwalk and Graph Convolution Network（GCN）to carry out research on adversarial attack,which have excellent performance in node classification:Firstly,a topology attack method is proposed for Deepwalk model that is based on the simple neural network.Deepwalk is an embedding approach to learn the low-dimensional vector representation combining the random walk and the skip-gram model in Word2 vec.Gradient based approaches for finding perturbations are not suited because of the randomness of the random walk process and the discreteness of graph.To tackle this challenge,the research found that network embedding approaches based on random walk could unified into the matrix factorization framework.Therefore,in this paper we use the equivalent matrix decomposition form of Deepwalk as the surrogate model and combine the eigen-value perturbation theory to find the optimal adversarial samples.The perturbed graph is applied to the Deepwalk model for retraining.The performance of node classification is evaluated by retraining the Deepwalk with perturbed graph.Our experimental study shows that accuracy of node classification significantly drops even when performing only few perturbations.Then,we proposed a topological attack method for GCN（the graph convolutional network model）.The complicated parameters of GCN and long training time pose challenges for the generation of adversarial perturbations.Here,we utilize the SGC（simplified graph convolution network）as surrogate model to perform adversarial attack.SGC uses linear equations to replace the nonlinear activation equations in GCN,so that the perturbations could be calculated in parallel.We select the rewiring network to attack the targeted nodes,which delete an edges and insert an edge at the same time.Therefore,the degree of target nodes and the total edges in the network will not be changed.The optimal perturbations will be searched on SGC.And the performance for classification is evaluated by retraining GCN with the perturbed graph.The experimental results show that only few perturbations could make GCN produce wrong predictions.In this paper,we study the topology attack for Deepwalk and GCN respectively and the experiments are carried out on node classification task.The experimental results show that only few perturbations samples could reduce the performance of classification task,and it is also effective that the perturbations transfer to other models.