Title: ADVERSARIAL ATTACKS ON NODE EMBEDDINGS

Abstract: 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.

1. INTRODUCTION:

Unsupervised node embedding (network representation learning) approaches are becoming increasingly popular and achieve state-of-the-art performance on many network learning tasks (Cai et al., 2017) . 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 (Goodfellow et al., 2014; Mei & Zhu, 2015; Carlini & Wagner, 2017; Liang et al., 2017; Cisse et al., 2017; Lin et al., 2017; Chen et al., 2017a) .

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 (Li et al.; Mei & Zhu, 2015) 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 (Stewart, 1990) 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.

2. RELATED WORK:

We focus on adversarial attacks on unsupervised node embedding approaches based on random walks (RWs), and further show how one can easily apply a similar analysis to attack other node embeddings based on factorization. For a recent extensive survey, also of other non-RW based approaches, we refer to Cai et al. (2017) . Moreover, while many (semi-)supervised learning methods (Kipf & Welling, 2016; Defferrard et al.) have been introduced, we focus on unsupervised methods since they are often used in practice due to their flexibility in solving various downstream tasks.

Adversarial attacks. Attacking machine learning models has a long history, with seminal works on SVMs and logistic regression (Biggio et al., 2012; Mei & Zhu, 2015) . Deep neural networks were also shown to be highly sensitive to small adversarial perturbations to the input (Szegedy et al., 2013; Goodfellow et al., 2014) . While most works focus on image classification, recent works have shown the existence of adversarial examples also in other domains (Liang et al., 2017; Grosse et al.) .

Different taxonomies exist characterizing the attacks/adversaries based on their goals, knowledge, and capabilities (Biggio et al.; Papernot et al.; Muñoz-González et al., 2017) . The two dominant attacks types are poisoning attacks that target the training data (the model is trained after the attack) and evasion attacks that target the test data/application phase (the learned model is assumed fixed). Compared to evasion attacks, poisoning attacks are far less studied (Koh & Liang, 2017; Muñoz-González et al., 2017; Li et al.; Mei & Zhu, 2015; Chen et al., 2017a) since they require solving a challenging bi-level optimization problem.

Attacks on semi-supervised graph models. The robustness of semi-supervised graph classification methods to adversarial attacks has recently been analyzed (Zügner et al., 2018; Dai et al., 2018a) . The first work, introduced by Zügner et al. ( 2018), linearizes a graph convolutional network (GCN) (Kipf & Welling, 2016) to derive a closed-form expression for the change in class probabilities for a given edge/feature perturbation. They calculate a score for each possible edge flip based on the classification margin and greedily pick the top edge flips with highest scores. Later, Dai et al. (2018a) proposed a reinforcement (Q-)learning formulation where they decompose the selection of relevant edge flips into selecting the two end-points. Both approaches focus on targeted attacks (misclassify a given node) for the semi-supervised graph classification task. In contrast, our work focuses on general attacks (decrease the overall quality) on unsupervised node embeddings.

Manipulating graphs. In the context of graph clustering, Chen et al. (2017b) measure the changes in the result when injecting noise to a bi-partite graph of DNS queries, but do not focus on automatically generating attacks. There is an extensive literature on works that optimize the graph structure to manipulate e.g. information spread in a network (Chen et al.; Khalil et al.) , user opinions (Amelkin & Singh, 2017; Chaoji et al.) , shortest paths (Phillips; Israeli & Wood) , page rank scores and other metrics (Avrachenkov & Litvak; Chan et al.) . Remotely related are poisoning attacks on multi-task relationship learning (Zhao et al., 2018) . While they exploit the relations between different tasks, they still deal with the classical scenario of i.i.d. instances within each task.

Robustness and adversarial training. The robustification of machine learning models has also been studied -known as adversarial machine learning or robust machine learning. Such approaches are out of scope for this paper and we do not discuss them. The goal of adversarial training (e.g. via GANs (Dai et al., 2018b) ) is to improve the embeddings, while our goal is to damage the embeddings produced by existing models by perturbing the graph structure.

3. ATTACKING NODE EMBEDDINGS:

Here we explore poisoning attacks on the graph structure -the attacker is capable of adding or removing (flipping) edges in the original graph within a given budget. We focus mainly on approaches based on random walks and extend the analysis to spectral approaches (Sec. 6.2 in the appendix).

3.1. BACKGROUND AND PRELIMINARIES:

Let G = (V, E) be an undirected unweighted graph where V is the set of nodes, E is the set of edges, and A ∈ {0, 1} |V |×|V | is the adjacency matrix. The goal of network representation learning is to find a low-dimensional embedding z v ∈ R K for each node with K |V |. This dense lowdimensional representation should preserve information about the network structure -nodes similar in the original network should be close in the embedding space. DeepWalk (Perozzi et al.) and node2vec (Grover & Leskovec) learn an embedding based on RWs by extending and adapting the skip-gram architecture (Mikolov et al., 2013) for learning word embeddings. They sample finite (biased) RWs and use the co-occurrence of node-context pairs in a given window in each RW as a measure of similarity. To learn z v they maximize the probability of observing v's neighborhood.

3.2. ATTACK MODEL:

We denote with Â the adjacency matrix of the graph obtained after the attacker has modified certain entries in A. We assume the attacker has a given, fixed budget and is only capable of modifying f entries, i.e. || Â -A|| 0 = 2f (we have 2f since G is undirected). The goal of the attacker is to damage the quality of the learned embeddings, which in turn harms subsequent learning tasks such as node classification or link prediction that use the embeddings as features. We consider both a general attack that aims to degrade the embeddings of the network as a whole, as well as a targeted attack that aims to damage the embedding regarding a specific target or specific task.

The quality of the embeddings is measured by the loss L(A, Z) of the model under attack, with lower loss corresponding to higher quality, where Z ∈ R N ×K is the matrix containing the embeddings of all nodes. Thus, the goal of the attacker is to maximize the loss. We can formalize this as the following bi-level optimization problem:

Â * = arg max Â∈{0,1} N ×N L( Â, Z * ) Z * = min Z L( Â, Z) subj. to || Â -A|| 0 = 2f , Â = ÂT (1)

Here, Z * is always the 'optimal' embedding resulting from the (to be optimized) graph Â, i.e. it minimizes the loss, while the attacker tries to maximize the loss. Solving such a problem is highly challenging given its discrete and combinatorial nature, thus we derive efficient approximations.

3.3. GENERAL ATTACK:

Since the first step in the embedding approaches is to generate a set of random walks that serve as a training corpus for the skip-gram model, the bi-level optimization problem is even more complicated. We have

Z * = min Z L({r 1 , r 2 , . . . }, Z) with r i ∼ RW l ( Â)

, where RW l is an intermediate stochastic procedure that generates RWs of length l given the graph Â which we are optimizing. By flipping (even a few) edges in the original graph, the attacker necessarily changes the set of possible RWs, thus changing the training corpus. Therefore, this RW generation process precludes any gradient-based methods. To tackle this challenge we leverage recent results that show that (given certain assumptions) RW based node embedding approaches are implicitly factorizing the Pointwise Mutual Information (PMI) matrix (Yang & Liu, 2015; Qiu et al., 2017) . We study DeepWalk as an RW-based representative approach since it's one of the most popular methods and has many extensions. Specifically, we use the results from Qiu et al. (2017) to sidestep the RW stochasticity.

Lemma 1 (Qiu et al. (2017) ). DeepWalk is equivalent to factorizing M = log(max(M, 1)) with

M = vol(A) T •b S, where S = T r=1 P r D -1 , where P = D -1 A (2)

where the embedding Z * is obtained by the Singular Value Decomposition of M = U ΣV T using the top-K largest singular values / vectors, i.e.

Z * = U K Σ 1/2 K .

Here, D is the diagonal degree matrix with D ii = j A ij , T is the window size, b is the number of negative samples and vol(A) = i,j A ij is the volume. Since M is sparse and has many zero entries the matrix log(M ) where the log is elementwise is ill-defined and dense. To cope with this, similar to the Shifted Positive PMI (PPMI) approach the elementwise maximum is introduced to form M . Using this insight, we see that DeepWalk is equivalent to optimizing min MK || M -MK || 2 F where MK is the best rank-K approximation to M . This in turn means that the loss for DeepWalk when using the optimal embedding Z * for a given graph

A is L DW1 (A, Z * ) = |V | p=K+1 σ 2 p where σ p are the singular values of M (A) ordered decreasingly σ 1 ≥ σ 2 • • • ≥ σ |V | .

This result shows that we do not need to construct random walks, nor do we have to (explicitly) learn the embedding Z * -it is implicitly considered via the singular values of M (A). Accordingly, we have transformed the bi-level problem into a single-level optimization problem. However, maximizing L DW1 is still challenging due to the singular value decomposition and the discrete nature of the problem.

Gradient based approach. Maximizing L DW1 with a gradient-based approach is not straightforward since we cannot easily backpropagate through the SVD. To tackle this challenge we exploit ideas from eigenvalue perturbation theory (Stewart, 1990) to approximate L DW1 (A) in closed-form without needing to recompute the SVD. This enables us to efficiently calculate the gradient. Theorem 1. Let A be the initial adjacency matrix and M (A) be the respective co-occurrence matrix. Let u p be the p-th eigenvector corresponding to the p-th largest eigenvalue of M . Given a perturbed matrix A , with A = A + ∆A, and the respective change ∆ M . We can approximately compute the loss:

L DW1 (A ) ≈ N p=K+1 u T p ( M + ∆ M )u p 2 =: L DW2 (A ) and the approxi- mation error is bounded by |L DW1 (A ) -L DW2 (A )| ≤ ||∆ M || F .

The proof is given in the appendix. For a small ∆A and thus small ∆ M we obtain a very good approximation, and if ∆A = ∆ M = 0 then the loss is exact. Intuitively, we can think of using eigenvalue perturbation as analogous to taking the gradient of the loss w.r.t. M (A). Now, gradient-based optimization is efficient since ∇ A L DW2 (A) avoids recomputing the eigenvalue decomposition. The gradient provides useful information for a small change, however, here we are considering discrete flips, i.e. = ±1 so its usefulness is limited. Furthermore, using gradient-based optimization requires a dense instantiation of the adjacency matrix, which has complexity O(N 2 ) in both runtime and memory (infeasible for large graphs). This motivates the need for our more advanced approach.

Sparse closed-form approach. Our goal is to efficiently compute the change in the loss L DW1 (A) given a set of flipped edges. To do so we will analyze the change in the spectrum of some of the intermediate matrices and then derivate a bound on the change in the spectrum of the co-occurrence matrix, which in turn will give an estimate of the loss. First, we need some results.

Lemma 2. The matrix S in Eq. 2 is equal to S = U ( T r=1 Λ r )U T where the matrices U and Λ contain the eigenvectors and eigenvalues solving the generalized eigen-problem Au = λDu.

The proof is given in the appendix. We see that the spectrum of S (and, thus, the one of M by taking scalars into account) is obtainable from the generalized spectrum of A. The difference to Qiu et al. (2017) 's derivation where a factorization of S using A norm := D -1/2 AD -1/2 is important. As we will show, our formulation using the generalized spectrum of A is key for an efficient approximation.

Let A = A + ∆A be the adjacency matrix after the attacker performed some edge flips. As above, by computing the generalized spectrum of A , we can estimate the spectrum of the resulting S and M . However, recomputing the eigenvalues λ of A for every possible set of edge flips is still not efficient for large graphs, preventing an effective application. Thus, we derive our first main result: an efficient approximation bounding the change in the singular values of M for any edge flip. Theorem 2. Let ∆A be a matrix with only 2 non-zero elements, namely ∆A ij = ∆A ji = 1 -2A ij corresponding to a single edge flip (i, j), and ∆D the respective change in the degree matrix, i.e. A = A + ∆A and D = D + ∆D. Let u y be the y-th generalized eigenvector of A with generalized eigenvalue λ y . Then the generalized eigenvalue λ y of A solving λ y A = λ y D u y is approximately:

λ y ≈ λ y = λ y + ∆λ y ∆λ y = ∆w ij (2u yi • u yj -λ y (u 2 yi + u 2 yj )) (3)

where u yi is the i-th entry of the vector u y , and

∆w ij = (1 -2A ij ) indicates the edge flip, i.e ±1.

The proof is provided in the appendix. By working with the generalized eigenvalue problem in Theorem 2 we were able to express A and D after flipping an edge as additive changes to A and D, this in turn enabled us to leverage results from eigenvalue perturbation theory to efficiently approximate the change in the spectrum. If we used A norm instead, the change to A norm would be multiplicative preventing efficient approximations. Using Eq. 3, instead of recomputing λ we only need to compute ∆λ, significantly reducing the complexity when evaluating different edge flips (i, j). Using this result, we can now efficiently bound the change in the singular values of S . Lemma 3. Let A be defined as before and S be the resulting matrix. The singular values of S are bounded: σ p (S ) ≤ σp (i, j) :=1 

d min • T r=1 ( λ π(p) ) r

where π is a permutation simply ensuring that the final σp (i, j) are sorted decreasingly, where d min is the smallest degree in A .

We provide the proof in the appendix. Using this result, we can efficiently compute the loss for a rank-K approximation/factorization of M , which we would obtain when performing the edge flip

(i, j), i.e. L DW3 (A ) = vol(A)+2∆wij T •b |V |

p=K+1 σp (i, j)2 1/2 . While the original loss L DW1 is based on the matrix M = log(max(M, 1)), there are unfortunately currently no tools available to analyze the spectrum of M given the spectrum of M . Therefore, we use L DW3 as a surrogate loss for L DW1 (Yang et al. similarly exclude the element-wise logarithm). As our experimental analysis shows, the surrogate loss is effective and we are able to successfully attack the node embeddings that factorize the actual co-occurrence matrix M , as well as the original skip-gram model. Similarly, methods based on spectral embedding, factorize the graph Laplacian and have a strong connection to the RW based approaches. We provide a similar detailed analysis in the appendix (Sec. 6.2).

The overall algorithm. Our goal is to maximize L DW3 by performing f edge flips. While Eq. 3 enables us to efficiently compute the loss for a single edge, there are still O(n 2 ) possible flips. To reduce the complexity when adding edges (see Sec. 4.2 for removing) we instead form a candidate set by randomly sampling C candidate flips. This introduces a further approximation that nonetheless works well in practice. For every candidate we compute its impact on the loss via L DW3 and greedily choose the top f flips. 1 The runtime complexity of our overall approach is:

O(N •|E|+C •N log N ).

First, we can compute the generalized eigenvectors of A in a sparse fashion in O(N • |E|). Then we sample C candidate edges, and for each we can compute the approximate eigenvalues in constant time (Theorem 2). To obtain the final loss, we sort the values leading to the overall complexity. The approach is easily parallelizable since every candidate edge flip can be evaluated in parallel.

3.4. TARGETED ATTACK:

If the goal of the attacker is to attack a specific node t ∈ V , called the target, or a specific downstream task, it is suboptimal to maximize the overall loss via L DW * . Rather, we should define some other target specific loss that depends on t's embedding -replacing the loss function of the outer optimization in Eq. 1 by another one operating on t's embedding. Thus, for any edge flip (i, j) we now need the change in t's embedding -meaning changes in the eigenvectors -which is inherently more difficult to compute compared to changes in eigen/singular-values. We study two cases: misclassifying a target node and manipulating the similarity of node pairs (i.e. link prediction task).

Surrogate embeddings. To efficiently compute the change in eigenvectors, we define surrogate embeddings Z * . Specifically, instead of performing an SVD decomposition on M (or equivalently S with upscaling) and using the results from Lemma 2 we define Z * = U ( T r=1 Λ r ). Experimentally, using Z * instead of Z * as the embedding showed no significant change in the performance on downstream tasks (even on the clean graph; suggesting its general use since it is more efficient to compute). Now, we can approximate the generalized eigenvectors, and thus Z * (A ), in closed-form: Theorem 3. Let ∆A, ∆D and ∆w ij be defined as before, and ∆λ y be the change in the y-th generalized eigenvalue λ y as derived in Theorem 2. Then, the y-th generalized eigenvector u y of A after performing the edge flip (i, j) can be approximated with:

EQUATION

) where E i (x) returns a vector of zeros except at position i where the value is x, d is a vector of the node degrees, • is the Hadamard product, and (•) + is the pseudo inverse.

We provide the proof in the appendix. Computing Eq. 4 seems expensive at first due to the pseudo inverse term. However, note that this term does not depend on the particular edge flip we perform. Thus, we can pre-compute it once and furthermore, parallelize the computation for each y. Similarly, we can pre-compute u y d, while the rest of the terms are all computable in O(1). For any edge flip we can now efficiently compute the optimal embedding Z * (A ) using Eqs. 3 and 4. The t-th row of Z * (A ) is the desired embedding for a target node t after the attack.

Targeting node classification. The goal is to enforce misclassification of the target t for the downstream task of node classification (i.e. node labels are partially given). To fully specify the targeted attack we need to define the candidate flips and the target-specific loss responsible for scoring the candidates. As candidates we use {(v, t)|v = t}. For the loss, we first pre-train a classifier C on the clean embedding Z * . Then we predict the class probabilities p t of the target t using the compromised Z * t,• and we calculate the classification margin m(t) = p t,c(t) -max c =c(t) p t,c , where c(t) is the ground-truth class for t. That is, our loss is the difference between the probability of the ground truth and the next most probable class after the attack. Finally, we select the top f flips with smallest margin m (note when m(t) < 0 node t is misclassified). In practice, we average over 10 randomly trained classifiers. Another (future work) approach is to treat this as a tri-level optimization problem.

Targeting link prediction. The goal of the attack is: given a set of target node pairs T ⊂ V × V , decrease the similarity between the nodes that have an edge, and increase the similarity between nodes that do not have an edge, by modifying other parts of the graph -i.e. it is not allowed to directly flip pairs in T . For example, in an e-commerce graph representing users and items, the goal might be to increase the similarity between a certain item and user, by adding/removing connections between other users/items. To achieve this, we first train the initial clean embedding without the target edges. Then, for a candidate set of flips, we estimate Z * using Eqs. 3 and 4 and use them to calculate the average precision score (AP score) on the target set T , with Z * i ( Z * j ) T as a similarity measure. Finally, we pick the top f flips with lowest AP scores and use them to poison the network.

4. EXPERIMENTAL EVALUATION:

Since this is the first work considering adversarial attacks on node embeddings there are no known baselines. Similar to works that optimize the graph structure (Chen et al.) we compare with several strong baselines. B rnd randomly flips edges (we report averages over ten seeds), B eig removes edges based on their eigencentrality in the line graph L(A), and B deg removes edges based on their degree centrality in L(A) -or equivalently sum of degrees in the original graph. When adding edges we use the same baselines as above, now calculated on the complement graph, except for B eig since it is infeasible to compute even for medium size graphs. A DW2 denotes our gradient based attack, A DW3 our closed-form attack, A link our link prediction attack, A class our node classification attack. The size of the sampled candidate set for adding edges is 20K (for removing edges see Sec. 4.2).

We aim to answer the following questions: (Q1) how good are our approximations of the loss; (Q2) how much damage is caused to the embedding quality by our attacks/baselines; (Q3) can we still perform a successful attack when restricted; (Q4) what characterizes selected (top) adversarial edges; (Q5) how do the targeted attacks affect downstream tasks; and (Q6) are the attacks transferable. (2005) ). In all experiments, after choosing the top f flips we retrain the embeddings and report the final performance since this is a poisoning attack. Note, for the general attack, the downstream node classification task is only a proxy for estimating the quality of the embeddings after the attack, it is not our goal to damage this task, but rather to attack the unsupervised embeddings in general.

4.1. APPROXIMATION QUALITY:

To estimate the approximation quality we randomly select a subset of 20K candidate flips and compute the correlation between the actual loss and our approximation as measured by Pearson's R score. For example, for K = 32 we have R(L DW2 , L DW1 ) = 0.11 and R(L DW3 , L DW1 ) = 0.90, clearly showing that our closed-form strategy approximates the loss significantly better compared to the gradient-based one. Similarly, L DW 3 is a better approximation than L DW2 for K = 16, 64, 128. (d) Cora: restricted class.

Figure 1 : Vulnerability of the embeddings under the general attack for increasing number of flips.

The dotted line shows the performance before attacking.

To obtain a better understanding we investigate the effect of removing and adding edges separately. Since real graphs are usually sparse, for removing we set the candidate set to be the set of all edges, with one edge set aside for each node to ensure we do not have singleton nodes. To obtain candidate edges for adding we randomly sample a set of edges. We then simply select the top f edges from the candidate set according to our scoring function. For adding edges, we also implemented an alternative add-by-remove strategy denoted as A abr . Here, we first add cf -many edges randomly sampled from the candidate set to the graph and subsequently remove (c -1)f -many of them. This strategy performed better empirically. Since the graph is undirected, for each (i, j) we also flip (j, i).

Fig. 1 answers question (Q2). Removed/added edges are denoted on the x-axis with negative/positive values respectively. On Fig. 1a we see that our strategies achieve a significantly higher loss compared to the baselines when removing edges. To analyze the change in the embedding quality we consider the node classification task (i.e. using it as a proxy to evaluate quality; this is not our targeted attack). Interestingly, B deg is the strongest baseline w.r.t. to the loss, but this is not true for the downstream task. As shown in Fig. 1b and 1c, our strategies significantly outperform the baselines. As expected, A DW3 and A abr perform better than A DW2 . On Cora our attack can cause up to around 5% more damage compared to the strongest baseline. On PolBlogs, by adding only 6% edges we can decrease the classification performance by more than 23%, while being more robust to removing edges.

Restricted attacks. In the real world, attackers cannot attack any node, but rather only specific nodes under their control, which translates to restricting the candidate set. To evaluate the restricted scenario, we first initialize the candidate sets as before, then we randomly choose a given percentage p r of nodes as restricted and discard every candidate that includes them. As expected, the results in Fig. 1d show that for increasingly restrictive sets with p r = 10%, 25%, 50%, our attack is able to do less damage. However, we always outperform the baselines (not plotted), and even in the case when half of the nodes are restricted (p r = 50%) we are still able to damage the embeddings. With this we are can answer question (Q3) affirmatively -the attacks are successful even when restricted.

Analysis of selected adversarial edges. In Fig. 2a we analyze the top 1K edges on Cora-ML. For each edge we consider its source node degree (destination node, resp.) and plot it on the x-axis (yaxis). The heatmap shows adversarial edge counts divided by total edge counts for each bin. We see that low, medium and high degree nodes are all represented. In Fig. 2b we plot the edge centrality distribution for the top 1K adversarial edges and compare it with the distribution of the remaining edges. There is no clear distinction. The findings highlight the need for a principled method such as ours since using intuitive heuristics such as degree/edge centrality cannot identify adversarial edges. 

To obtain a better understanding of the performance we study the margin m(t) before and after the attack considering every node t as a potential target. We allow only (d t + 3) flips for attacking each node ensuring the degrees stay similar. Each dot in Fig. 4 represents one node grouped by its degree in the clean graph (logarithmic bins). We see that low-degree nodes are easier to misclassify (m(t) < 0), and that high degree nodes are more robust in general -the baselines have 0% success.

Our method, however, can successfully attack even high degree nodes. In general, our attack is significantly more effective across all bins -as shown by the numbers on top of each box -with 77.89% nodes successfully misclassified on average compared to e.g. only 33.64% for B rnd . For the link prediction task (Fig. 3 ) we are similarly able to cause significant damage -e.g. A link achieves almost 10% decrease in performance by flipping around 12.5% of edges on Cora, significantly better than all other baselines. Here again, compared to adding edges, removing has a stronger effect. Overall, answering (Q5), both experiments confirm that our attacks hinder the downstream tasks.

4.4. TRANSFERABILITY:

The question of transferability -do attacks learned for one model generalize to other models -is important since in practice the attacker might not know the model used by the system under attack. However, if transferability holds, such knowledge is not required. To obtain the perturbed graph, we remove the top f adversarial edges with the A DW3 attack. The same perturbed graph is then used to learn node embeddings using several other state-of-the-art approaches. Table 1 shows the change in node classification performance compared to the embeddings learned on the clean graph for each method respectively. We tune the key hyperparameters for each method (e.g. p and q for node2vec). Answering (Q6), the results show that our attack generalizes: the adversarial edges have a noticeable impact on other models as well. We can damage DeepWalk trained with the skip-gram objective with negative sampling (SGNS) showing that the factorization analysis is successful. We can even damage the performance of semi-supervised approaches such as GCN and Label Propagation. Compared to the transferability of the baselines (Sec. 6.3) our attack causes significantly more damage.

5. CONCLUSION:

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.

6.2. ANALYSIS OF SPECTRAL EMBEDDING METHODS:

Attacking spectral embedding. Finding the spectral embedding is equivalent to the following trace minimization problem:

EQUATION

subject to orthogonality constraints, where L xy is the graph Laplacian. The solution is obtained via the eigen-decomposition of L, with Z * = U K where U K are the K-first eigen-vectors corresponding to the K-smallest eigenvalues λ i . The Laplacian is typically defined in three different ways: the unnormalized Laplacian L = D -A, the normalized random walk Laplacian

L rw = D -1 L = I - D -1 A and the normalized symmetric Laplacian L sym = D -1/2 LD -1/2 = I -D -1/2 AD -1/2 = I -A norm ,

where A, D, A norm are defined as before.

Lemma 5 (Von Luxburg) . λ is an eigenvalue of L rw with eigenvector u if and only if λ is an eigenvalue of L sym with eigenvector w = D 1/2 u. Furthermore, λ is an eigenvalue of L rw with eigenvector u if and only if λ and u solve the generalized eigen-problem Lu = λDu.

From Lemma 5 we see that we can attack both normalized versions of the graph Laplacian with a single attack strategy since they have the same eigenvalues. It also helps us to do that efficiently similar to our previous analysis (Theorem. 3).

Theorem 4. Let L rw (or equivalently L sym ) be the initial graph Laplacian before performing a flip and λ y and u y be any eigenvalue and eigenvector of L rw . The eigenvalue λ y of L rw obtained after flipping a single edge (i, j) is

EQUATION

where u yi is the i-th entry of the vector u y .

Proof. From Lemma 5 we can estimate the change in L rw (or equivalently L sym ) by estimating the eigenvalues solving the generalized eigen-problem Lu = λDu. Let ∆L = L -L be the change in the unnormalized graph Laplacian after performing a single edge flip (i, j) and ∆D be the corresponding change in the degree matrix. Let e i be defined as before. Then ∆L = (1 -2A ij )(e i -e j )(e i -e j ) T and ∆D = (1 -2A ij )(e i e T i + e j e T j ). Based on the theory of eigenvalue perturbation we have λ y ≈ λ y + u T y (∆L -λ y ∆D)u y . Substituting ∆L and ∆D are re-arranging we get the above results.

Using now Theorem 4 and Eq. 5 we finally estimate the loss of the spectral embedding after flipping an edge L SC (L rw , Z) ≈ K p=1 λ p . Note that here we are summing over the K-first smallest eigenvalues. We see that spectral embedding and the random walk based approaches are indeed very similar.

We provide similar analysis for the the unnormalized Laplacian: Theorem 5. Let L be the initial unnormalized graph Laplacian before performing a flip and λ y and u y be any eigenvalue and eigenvector of L. The eigenvalue λ y of L obtained after flipping a single edge (i, j) can be approximated by:

λ y ≈ λ y -(1 -2A ij )(u yi -u yj ) 2 (7)

Proof. Let ∆A = A -A be the change in the adjacency matrix after performing a single edge flip (i, j) and ∆D be the corresponding change in the degree matrix. Let e i be defined as before. Then ∆L = L -L = (D + ∆D) -(A + ∆A) -(D -A) = ∆D -∆A = (1 -2A ij )(e i e T i + e j e T j -(e i e T j + e j e T i )). Based on the theory of eigenvalue perturbation we have λ y ≈ λ y + u T y (∆L)u y . Substituting ∆L and re-arranging we get the above results. 

6.3. FURTHER EXPERIMENTAL EVIDENCE:

Upper bound on singular values. From Lemma 3 we have that L DW 3 is an upper bound on L DW 1 (excluding the elementwise logarithm) so maximizing L DW 3 is principled. To gain a better understanding of the tightness of the bound we visualize the singular values of S and their respective upper-bound for all datasets. As we can see in Fig. 5 , the gap is different for different datasets and relatively small. Furthermore we can notice that the gap tends to increase for larger singular values.

Transferability of the baselines. To further support the transferability of our proposed attack we also examine the transferability of the baseline attacks. Specifically, we examine the transferability of B eig since it is the strongest baseline when removing edges as shown in Fig. 1b . We use the same experimental setup as in Sec. 4.4 and show the results in Table 2 . We can see that compared to our proposed attack the baseline can do a significantly smaller amount of damage (compare to results in Table 1 ). Interestingly, it can do significant damage to GCN when removing 250 edges on Cora, but not when removing 500 edges. We plan on exploring this counterintuitive finding in future work. 

:

A greedy approach where we sequentially flip the single best candidate, followed by a periodic recomputation of the eigenvalues did not show benefits, nor did an evolutionary strategy using

Theorem 2 as a heuristic.

Figures and Tables:

We set DeepWalk's hyperparameters to: T = 5, b = 5, K = 64 and use a logistic regression for classification. We analyze three datasets: Cora (N = 2810, |E| = 15962, McCallum et al.), Citeseer (N = 2110, |E| = 7336, Giles et al.), and PolBlogs (N = 1222, |E| = 33428, Adamic & Glance

Figure 2: Analysis of the adversarial edges.

Figure 3: Targeted attack on the link prediction

Figure 5: The singular value of S and our derived upper bound.

Transferability: The change in F 1 score (in percent) compared to the clean/original graph.

Table content: <table><tr><td colspan="7">Cora / Citeseer DeepWalk (SVD) DeepWalk (SGNS) node2vec Spect. Embd. Label Prop. GCN</td></tr><tr><td>f = 250(03.1%)</td><td>-3.59</td><td>-3.97</td><td>-2.04</td><td>-2.11</td><td>-5.78</td><td>-3.34</td></tr><tr><td>f = 500(06.3%)</td><td>-5.22</td><td>-4.71</td><td>-3.48</td><td>-4.57</td><td>-8.95</td><td>-2.33</td></tr><tr><td>f = 250(06.8%)</td><td>-7.59</td><td>-5.73</td><td>-6.45</td><td>-3.58</td><td>-4.99</td><td>-2.21</td></tr><tr><td>f = 500(13.6%)</td><td>-9.68</td><td>-11.47</td><td>-10.24</td><td>-4.57</td><td>-6.27</td><td>-8.61</td></tr></table>

Transferability: The change in F 1 score (in percent) compared to the clean/original graph.

Table content: <table><tr><td colspan="7">Cora / Citeseer DeepWalk (SVD) DeepWalk (SGNS) node2vec Spect. Embd. Label Prop. GCN</td></tr><tr><td>f = 250(03.1%)</td><td>-0.61</td><td>-0.65</td><td>-0.57</td><td>-0.86</td><td>-1.23</td><td>-6.33</td></tr><tr><td>f = 500(06.3%)</td><td>-0.71</td><td>-1.22</td><td>-0.64</td><td>-0.51</td><td>-2.69</td><td>-0.64</td></tr><tr><td>f = 250(06.8%)</td><td>-0.40</td><td>-1.16</td><td>-0.26</td><td>+0.11</td><td>-1.08</td><td>-0.70</td></tr><tr><td>f = 500(13.6%)</td><td>-2.15</td><td>-2.33</td><td>-1.01</td><td>+0.38</td><td>-3.15</td><td>-1.40</td></tr></table>

Peer review (iclr2019):
 This paper is a timely work on poisoning random walk based graph embedding methods. In particular, it shows how to derive a surrogate loss function for DeepWalk. Even though the analysis method and the algorithm proposed is somewhat loose, I think this paper do a good contribution towards the adversarial attack problem for important models. There are still some room to improve in this paper. One problem is that since the paper proposes a surrogate loss L_{DW3}, it would be natural to analysis its gap from L_{DW1}. In this paper I can only see some empirical results on this issue. Another issue is that the algorithm the paper used is another approximation towards L_{DW3} by an additional sampling method. And the overall strategy can be far away from the true optimal solution for maximizing L_{DW3}. Still there*s no analysis on that issue. A potential drawback for the method proposed is that its complexity is O(NE), which can be quite expensive when the graph is big, and # edges is .Omega(NlogN). The experiments in this paper is convincing. It seems that the method proposed is way better than its competitors when removing edges. Is there any further intuition on that? Why the method is not so good when we add edges? Moreover, the black-box attack scenario requires more justification. What is the relative performance gain for A_{DW3} against other attacks in the black-box setting? Overall, this paper targets on an important issue in machine learning. My main concern is that it leaves too many questions behind their algorithms. Still some effort is required to improve the paper.