Year: 2018

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.

heading: 1 INTRODUCTION
text: 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.

heading: 2 RELATED WORK
text: 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.; Muñoz-Gonzá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; MuñozGonzá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 (Zügner et al., 2018; Dai et al., 2018a). The first work, introduced by Zü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.

heading: 3 ATTACKING NODE EMBEDDINGS
text: 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).

heading: 3.1 BACKGROUND AND PRELIMINARIES
text: 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 zv ∈ RK 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 zv they maximize the probability of observing v’s neighborhood.

heading: 3.2 ATTACK MODEL
text: We denote with Â 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̂ − 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 lossL(A,Z) of the model under attack, with lower loss corresponding to higher quality, where Z ∈ RN×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:
Â∗ = arg max Â∈{0,1}N×N L(Â, Z∗) Z∗ = min Z L(Â, Z) subj. to ||Â−A||0 = 2f , Â = ÂT (1)
Here, Z∗ is always the ’optimal’ embedding resulting from the (to be optimized) graph Â, 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.

heading: 3.3 GENERAL ATTACK
text: 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∗ = minZ L({r1, r2, . . . }, Z) with ri ∼ RWl(Â), where RWl is an intermediate stochastic procedure that generates RWs of length l given the graph Â 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−1A (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∗ = UKΣ 1/2 K .
Here, D is the diagonal degree matrix with Dii = ∑ j Aij , T is the window size, b is the number of
negative samples and vol(A) = ∑ i,j Aij is the volume. SinceM 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 minM̃K ||M̃ − M̃K || 2 F where M̃K 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 LDW1(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 LDW1 is still challenging due to the singular value decomposition and the discrete nature of the problem.
Gradient based approach. Maximizing LDW1 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 LDW1(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 up 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: LDW1(A′) ≈ √∑N p=K+1 ( uTp (M̃ + ∆M̃)up )2 =: LDW2(A′) and the approximation error is bounded by |LDW1(A′)− LDW2(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∇ALDW2(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(N2) 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 LDW1(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)UT 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 ofM 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 Anorm := D−1/2AD−1/2 is important. As we will show, our formulation using the generalized spectrum ofA 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 ∆Aij = ∆Aji = 1− 2Aij corresponding to a single edge flip (i, j), and ∆D the respective change in the degree matrix, i.e. A′ = A+∆A andD′ = D+∆D. Let uy be the y-th generalized eigenvector ofA with generalized eigenvalue λy . Then the generalized eigenvalue λ′y of A ′ solving λ′yA ′ = λ′yD ′u′y is approximately:
λ′y ≈ λ̃′y = λy + ∆λy ∆λy = ∆wij(2uyi · uyj − λy(u2yi + u2yj)) (3) where uyi is the i-th entry of the vector uy , and ∆wij = (1− 2Aij) 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 Anorm 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) := 1d′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. LDW3(A′) = vol(A)+2∆wij T ·b [∑|V | p=K+1 σ̃p(i, j) 2 ]1/2
. While the original loss LDW1 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 LDW3 as a surrogate loss for LDW1 (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 LDW3 by performing f edge flips. While Eq. 3 enables us to efficiently compute the loss for a single edge, there are stillO(n2) 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 viaLDW3 and greedily choose the top f flips.1 The runtime complexity of our overall approach is: O(N ·|E|+C ·N logN). First, we can compute the generalized eigenvectors of A in a sparse fashion inO(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.

heading: 3.4 TARGETED ATTACK
text: 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 LDW∗ . 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 onM (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 ∆wij 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: u′y ≈ uy −∆wij(A− λD)+(−∆λyuy ◦ d+ Ei(uyj − λyuyi) + Ej(uyi − λyuyj)) (4)
where Ei(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.
1A 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.
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 uyd, 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 6= t}. For the loss, we first pre-train a classifier C on the clean embedding Z̄∗. Then we predict the class probabilities pt of the target t using the compromised Z̄∗t,· and we calculate the classification margin m(t) = pt,c(t) −maxc6=c(t) pt,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.

heading: 4 EXPERIMENTAL EVALUATION
text: 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. Brnd randomly flips edges (we report averages over ten seeds), Beig removes edges based on their eigencentrality in the line graph L(A), and Bdeg 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 Beig since it is infeasible to compute even for medium size graphs. ADW2 denotes our gradient based attack, ADW3 our closed-form attack,Alink our link prediction attack,Aclass 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.
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 (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.

heading: 4.1 APPROXIMATION QUALITY
text: 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(LDW2 ,LDW1) = 0.11 and R(LDW3 ,LDW1) = 0.90, clearly showing that our closed-form strategy approximates the loss significantly better compared to the gradient-based one. Similarly, LDW3 is a better approximation than LDW2 for K = 16, 64, 128.

heading: 4.2 GENERAL ATTACK
text: 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 Aabr. 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, Bdeg 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, ADW3 and Aabr perform better than ADW2 . 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 pr 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 pr = 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 (pr = 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.
1 2 4 8 16 32 64 128 256
source node degree
1 2
4 8
16 32
64 12
8 25 6 de st in at io n no de d eg re e
0.0
0.2
0.4
0.6
0.8
1.0
(a) Degree centrality
0.00 0.01 0.02 0.03 edge centrality
0
0.1
0.2
0.3
K D
E d
en si
ty
adversarial remaining
(b) Edge centrality
Figure 2: Analysis of the adversarial edges.
-1000 12.5 -800 10.0 -600 7.5 -400 5.0 -200 2.5 200 2.5 400 5.0 600 7.5 800 10.0 1000 12.5
number of flips / % edges
0.72
0.74
0.76
0.78
0.80
0.82
A P
s co
re
DW2 DW3 link rnd deg eig
(a) Cora
-1000 27.3 -800 21.8 -600 16.4 -400 10.9 -200 5.5 200 5.5 400 10.9 600 16.4 800 21.8 1000 27.3
number of flips / % edges
0.60
0.65
0.70
0.75
0.80
0.85
A P
s co
re
DW2 DW3 link rnd deg eig
(b) Citeseer
Figure 3: Targeted attack on the link prediction

heading: 4.3 TARGETED ATTACK
text: 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 (dt + 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% forBrnd . For the link prediction task (Fig. 3) we are similarly able to cause significant damage – e.g. Alink 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.

heading: 4.4 TRANSFERABILITY
text: 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 ADW3 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.

heading: 5 CONCLUSION
text: 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.

heading: 6 APPENDIX

heading: 6.1 PROOFS AND DERIVATIONS
text: Proof. Theorem 1. Applying eigenvalue perturbation theory we obtain that λ′p = λp+uTp (∆M̃)up where λ′p is the eigenvalue of M̃
′ obtained after perturbing a single edge based on A′. Using the fact that λp = uTp M̃up, and the fact that singular values are equal to the absolute value of the corresponding eigenvalues we obtain the desired result.
Proof. Theorem 2. Denote with ei the vector of all zeros and a single one at position i. Then, we have ∆A = ∆wij(eieTj + eje T i ) and ∆D = ∆wij(eie T i + eje T j ). From eigenvalue perturbation theory Stewart (1990), we get: λ′y ≈ λy + uTy (∆A − λy∆D)uy . Substituting ∆A/∆D concludes the proof.
We include an intermediate result which is required for proving Lemma 2 and Lemma 3.
Lemma 4. λ is an eigenvalue ofD−1/2AD−1/2 := Anorm with eigenvector û = D1/2u if and only if λ and u solve the generalized eigen-problem Au = λDu.
Proof. Lemma 4. We have Az = λDz =⇒ (Q−1AQ−T )(QT z) = λ(QT z) for any real symmetric A and any positive definite D, where D = QQT using the Cholesky factorization. Substituting the adjacency/degree matrix and noticing that Q = QT = D1/2 we obtain the result.
Proof. Lemma 2. S is equal to a product of three matrices S = D−1/2 ( Û (∑T r=1 Λ̂ r ) ÛT ) D−1/2 where Û Λ̂ÛT = D−1/2AD−1/2 =: Anorm is the eigenvalue decomposition of Anorm (Qiu et al. (2017)). From Lemma 4 we have the fact that λ is an eigenvalue ofD−1/2AD−1/2 with eigenvector û = D1/2u if and only if λ and u solve the generalized eigen-problem Au = λDu. Substituting Λ̂ = Λ and Û = D1/2U in S, and since D is diagonal, we obtain the result.
Proof. Lemma 3. Following Qiu et al. (2017), the singular values of S can be bounded by σp(S) ≤ 1 dmin ∣∣∑T r=1(µ̂π(p)) r ∣∣ where µ are the (standard) eigenvalues of Anorm. Using Lemma 4, the same bound applies using the generalized eigenvalues λp of A. Now using Theorem 2, we obtain λ̃′p an approximation of the p-th generalized eigenvalue of A′. Plugging it into the singular value bound we obtain: σp(S) ≤ 1dmin ∣∣∑T r=1(λ̃ ′ π(p)) r ∣∣ which concludes the proof.
Please note that the permutation π does not need be computed/determined explicitly. In practice, for every λ̃′p, we compute the term ∣∣∑T r=1(λ̃ ′ p) r ∣∣. Afterwards, these terms are simply sorted.

heading: 6.2 ANALYSIS OF SPECTRAL EMBEDDING METHODS
text: Attacking spectral embedding. Finding the spectral embedding is equivalent to the following trace minimization problem:
min Z∈R|V |×K
Tr(ZTLxyZ) = K∑ i=1 λi(Lxy) = LSC (5)
subject to orthogonality constraints, where Lxy is the graph Laplacian. The solution is obtained via the eigen-decomposition ofL, withZ∗ = UK whereUK are theK-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 Lrw = D−1L = I − D−1A and the normalized symmetric Laplacian Lsym = D−1/2LD−1/2 = I −D−1/2AD−1/2 = I −Anorm, where A,D,Anorm are defined as before. Lemma 5 (Von Luxburg). λ is an eigenvalue of Lrw with eigenvector u if and only if λ is an eigenvalue of Lsym with eigenvector w = D1/2u. Furthermore, λ is an eigenvalue of Lrw 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 Lrw (or equivalently Lsym) be the initial graph Laplacian before performing a flip and λy and uy be any eigenvalue and eigenvector of Lrw. The eigenvalue λ′y of L ′ rw obtained after flipping a single edge (i, j) is
λ′y ≈ λy + ∆wij((uyi − uyj)2 − λy(u2yi + u2yj)) (6)
where uyi is the i-th entry of the vector uy .
Proof. From Lemma 5 we can estimate the change in Lrw (or equivalently Lsym) 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 ei be defined as before. Then ∆L = (1 − 2Aij)(ei − ej)(ei − ej)T and ∆D = (1− 2Aij)(eieTi + ejeTj ). Based on the theory of eigenvalue perturbation we have λ′y ≈ λy + uTy (∆L − λy∆D)uy . 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 LSC(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 uy 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− 2Aij)(uyi − uyj)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 ei be defined as before. Then ∆L = L′ − L = (D + ∆D)− (A+ ∆A)− (D−A) = ∆D−∆A = (1− 2Aij)(eieTi + ejeTj − (eie T j + eje T i )). Based on the theory of eigenvalue perturbation we have λ ′ y ≈ λy + uTy (∆L)uy . Substituting ∆L and re-arranging we get the above results.

heading: 6.3 FURTHER EXPERIMENTAL EVIDENCE
text: Upper bound on singular values. From Lemma 3 we have that LDW3 is an upper bound on LDW1 (excluding the elementwise logarithm) so maximizing LDW3 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 Beig 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.

Review summaries:
The authors present a novel adversarial attack on node embedding method based on random walks. They focus on perturbing the structure of the network. Because the bi-level optimization problem can be highly challenging, they refer to factorize a random walk matrix which is proved equivalent to DeepWalk. The experimental results show that their approach can effectively mislead the node embedding from multi-classification.