The goal of network representation learning is to learn low-dimensional node embeddings that capture the graph structure and are useful for solving downstream tasks. However, despite the proliferation of such methods there is currently no study of their robustness to adversarial attacks. We provide the first adversarial vulnerability analysis on the widely used family of methods based on random walks. We derive efficient adversarial perturbations that poison the network structure and have a negative effect on both the quality of the embeddings and the downstream tasks. We further show that our attacks are transferable since they generalize to many models, and are successful even when the attacker is restricted. Unsupervised node embedding (network representation learning) approaches are becoming increasingly popular and achieve state-of-the-art performance on many network learning tasks BID5 . The goal is to embed each node in a low-dimensional feature space such that the graph's structure is captured. The learned embeddings are subsequently used for downstream tasks such as link prediction, node classification, community detection, and visualization. Among the variety of proposed approaches, techniques based on random walks (RWs) (Perozzi et al.; Grover & Leskovec) are highly successful since they incorporate higher-order relational information. Given the increasing popularity of these method, there is a strong need for an analysis of their robustness. In particular, we aim to study the existence and effects of adversarial perturbations. A large body of research shows that traditional (deep) learning methods can easily be fooled/attacked: even slight deliberate data perturbations can lead to wrong results BID17 BID28 BID6 BID12 BID26 BID10 .So far, however, the question of adversarial perturbations for node embeddings has not been addressed. This is highly critical, since especially in domains where graph embeddings are used (e.g. the web) adversaries are common and false data is easy to inject: e.g. spammers might create fake followers on social media or fraudsters might manipulate friendship relations in social networks. Can node embedding approaches be easily fooled? The answer to this question is not immediately obvious. On one hand, the relational (non-i.i.d.) nature of the data might improve robustness since the embeddings are computed for all nodes jointly rather than for individual nodes in isolation. On the other hand, the propagation of information might also lead to cascading effects, where perturbations in one part of the graph might affect many other nodes in another part of the graph.Compared to the existing works on adversarial attacks our work significantly differs in various aspects. First , by operating on plain graph data, we do not perturb the features of individual instances but rather their interaction/dependency structure. Manipulating the structure (the graph) is a highly realistic scenario. For example, one can easily add or remove fake friendship relations on a social network, or write fake reviews to influence graph-based recommendation engines. Second, the node embedding works are typically trained in an unsupervised and transductive fashion. This means that we cannot rely on a single end-task that our attack might exploit to find appropriate perturbations, and we have to handle a challenging poisoning attack where the model is learned after the attack. That is, the model cannot be assumed to be static as in most other adversarial attack works. Lastly, since graphs are discrete classical gradient-based approaches BID28 for finding adversarial perturbations that were designed for continuous data are not well suited. Particularly for RW-based methods, the gradient computation is not directly possible since they are based on a non-differentiable sampling procedure. How to design efficient algorithms that are able to find adversarial perturbations in such a challenging -discrete and combinatorial -graph domain?We propose a principled strategy for adversarial attacks on unsupervised node embeddings. Exploiting results from eigenvalue perturbation theory BID35 we are able to efficiently solve a challenging bi-level optimization problem associated with the poisoning attack. We assume an attacker with full knowledge about the data and the model, thus, ensuring reliable vulnerability analysis in the worst case. Nonetheless, our experiments on transferability demonstrate that our strategy generalizes -attacks learned based on one model successfully fool other models as well.Overall, we shed light on an important problem that has not been studied so far. We show that node embeddings are sensitive to adversarial attacks. Relatively few changes are needed to significantly damage the quality of the embeddings even in the scenario where the attacker is restricted. Furthermore, our work highlights that more work is needed to make node embeddings robust to adversarial perturbations and thus readily applicable in production systems. We demonstrate that node embeddings are vulnerable to adversarial attacks which can be efficiently computed and have a significant negative effect on node classification and link prediction. Furthermore, successfully poisoning the system is possible with relatively small perturbations and under restriction. More importantly, our attacks generalize -the adversarial edges are transferable across different models. Future work includes modeling the knowledge of the attacker, attacking other network representation learning methods, and developing effective defenses against such attacks.
Adversarial attacks on unsupervised node embeddings based on eigenvalue perturbation theory.
{"src": "scitldr-AIC_train", "paper_id": "Sye7qoC5FQ"}