Network Embedding Attack: An Euclidean Distance Based Method

Abstract

Network embedding methods are widely used in graph data mining. This chapter proposes a Genetic Algorithm (GA) based Euclidean Distance Attack strategy (EDA) to attack the DeepWalk-based network embedding to prevent certain structural information from being discovered. EDA disrupts the Euclidean distance between pairs of nodes in the embedding space by making a minimal modification of the network structure, thereby rendering downstream network algorithms ineffective, because a large number of network embedding based downstream algorithms, such as community detection and node classification, evaluate the similarity based on the Euclidean distance between nodes. Different from traditional attack strategies, EDA is an unsupervised network embedding attack method, which does not need labeling information. Experiments with a set of real networks demonstrate that the proposed EDA method can significantly reduce the performance of DeepWalk-based networking algorithms, outperforming other attack strategies in most cases. The results also indicate the transferability of the EDA method since it works well on attacking the network algorithms based on other network embedding methods such as High-Order Proximity preserved Embedding (HOPE) and non-embedding-based network algorithms such as Label Propagation Algorithm (LPA) and Eigenvectors of Matrices (EM).