Reinforcement Learning-based Black-Box Evasion Attacks to Link Prediction in Dynamic Graphs

We use $\textbf{s}_{k}$ to denote the state of the intermediate perturbed graph $\widetilde{A}_{t-1}^{k}$ at the attack step $k$. Thus $\textbf{s}_{0}$ is the state of the clean graph $A_{t-1}$ and $\widetilde{A}_{t-1}^{0}=A_{t-1}$. Moreover, we also use ${\textbf{s}}_{k}$ to indicate a low-dimensional embedding of the high-dimensional perturbed graph $\widetilde{A}^{k}_{t-1}$. ${\textbf{s}}_{k}$ aims to capture the latent structural information in the perturbed graph $\widetilde{A}_{t-1}^{k}$. and it is learnt via the following three steps: First, we observe all clean graphs in the example other than ${A}^{k}_{t-1}$ (i.e., from $A_{t-n}$ to $A_{t-2}$ in this case), and select a fraction $\rho$ ($<0.5$) of nodes $V_{p}\subseteq V$ with the largest averaged degrees (called popular nodes) as well as the same fraction of nodes $V_{n}\subseteq V$ with the smallest averaged degrees (called neglected nodes) among those observed graphs (i.e., $|V_{p}|=|V_{n}|=\rho|V|$). Our intuition is that nodes with the largest/smallest averaged degrees can maintain the primary information in a graph. Second, we encode the two node sets $V_{p}$ and $V_{n}$ using two one-hot vectors $\textbf{o}_{p},\textbf{o}_{n}\in\mathbb{R}^{|V|}$. Specifically, $o_{p,u}=1$ if $u\in V_{p}$ and $o_{p,u}=0$ if $u\notin V_{p}$. Similarly, $o_{n,u}=1$ if $u\in V_{n}$ and $o_{n,u}=0$ if $u\notin V_{n}$. Third, we define the representation for ${\textbf{s}}_{k}$ as follows:

where $g(a)$ is a function $g:\mathbb{R}^{|V|}\rightarrow\mathbb{R}^{\rho|V|}$, which first selects $\rho|V|$ entries from the $|V|$-dimensional vector $a$ with indexes corresponding to $V_{p}$ (or $V_{n}$) to form a new $\rho|V|$-dimensional vector; and then applies a nonlinear activation function (e.g., ReLU in our paper) to the new vector to obtain the $\rho|V|$-dimensional embedding for the perturbed graph $\tilde{A}^{k}_{t-1}$. Note that we introduce a smooth regularization term $\gamma/|V|$ in order to stabilize the training and reduce overfitting. By default, we set $\gamma$ to be 0.2. With Equation 2, each entry value in ${\textbf{s}}_{k}$ indicates the importance of the corresponding node in $V_{p}$ or $V_{n}$. For the implementation purpose, we also store the mapping between the vector index $i\in[1:V_{p}]$ or $i\in[1:V_{n}]$ and the real node index $j\in V$ in the graph.

We consider that the attacker only changes the link status among $V_{p}$ and $V_{n}$. Our motivation is based on the assumption that: when deleting edges among popular nodes or/and adding edges among neglected nodes, the graph structure can be largely changed, and thus the DyGCN model would make as many wrong predicted links as possible when evaluated on the perturbed graph. Note that such a consideration can also reduce the computational complexity, as the attacker does not need to search the entire graph structure. Moreover, to ensure that certain graph property does not change significantly after the perturbation, we require the total number of edges in the graph keeps the same in each attack step. Particularly, we consider that an attacker executes an action by adding a new edge between a pair of nodes as well as deleting an existing edge between another pair of nodes. Then, the purpose of the action is to search two pairs of nodes, such that when executing the action, DyGCN’s performance decreases as much as possible based on the current state. Specifically, we denote $\textbf{a}_{k}$ as the action at the attack step $k$. Then, we design a policy to generate actions based on $\textbf{s}_{k}$. Formally, we define

where $\mathcal{P}_{\Phi}$ is a policy network parameterized by $\Phi$. Equation 3 attempts to enforce that, when nodes in $V_{p}$ (or $V_{n}$) are relative more important at state $\textbf{s}_{k}$, then they are more likely to be selected as the action $\textbf{a}_{k}$. In this paper, we define our policy network as a composition of a 3-layer MLP network and a truncated normal distribution (TruncNorm) within an interval $[1,\rho|V|]$. Specifically, the output of MLP is the mean and log-deviation of a TruncNorm; and we then perform the action $\textbf{a}_{k}$ by sampling two pairs of nodes from the TruncNorm (with rounding). Moreover, we note that the sampling process can be naturally divided into two separate steps: we first perform an action $\textbf{a}^{(1)}_{k}$ to sample a pair of nodes from $V_{p}$ and then perform another action $\textbf{a}^{(2)}_{k}$ to sample a pair of nodes from $V_{n}$. Formally,

With $\textbf{a}_{k}$, we can map each of its value back to the real node index via our stored mapping. For simplicity, we still use $\textbf{a}_{k}$ to indicate the real node indexes. Moreover, when the attacker’s action is to add an existing edge or delete a nonexistent edge, we will move to the next step. Details of training the policy network $\mathcal{P}_{\Phi}$ is illustrated in the next subsection.

Given the state $\textbf{s}_{k}$ and action $\textbf{a}_{k}$, the attacker obtains a new state $\textbf{s}_{k+1}$. Naturally, if the link prediction performance of $\mathcal{F}_{\Theta^{*}}$ at state $\textbf{s}_{k+1}$ is worse than that at state $\textbf{s}_{k}$, then a positive reward will be given, otherwise a negative reward. Based on this motivation, we design the reward function as follows:

where $\textrm{err}^{k}=\mathcal{I}({A}_{t}^{k}\neq\mathcal{F}_{\Theta^{*}}(\widetilde{\mathcal{S}}^{k}_{[t-n:t-1]}))$ corresponds to our objective function in Equation 1 at the $k$-th attack step. $f^{k}$ is a function to measure the effectiveness of $\mathcal{F}_{\Theta^{*}}$ on the perturbed graphs for link prediction at state $\textbf{s}_{k}$. If $\textrm{err}^{k+1}>\textrm{err}^{k}$, which means our attack generates more wrong predicted links at the $k+1$-th attack step, then the gap between $f^{k}$ and $f^{k+1}$ is positive. Furthermore, if the positive gap is larger, then our attack is more effective. Thus, we can use this positive gap as a positive reward $\textbf{r}_{k}$. Otherwise, if our attack performs worse at the attack step $k+1$, then we set a large negative reward to penalize this step.

To obtain a optimal expected reward and guide the policy network $\mathcal{P}_{\Phi}$, we also need to solve a $Q$-function, which is parameterized by a soft $\mathcal{Q}$-network $\mathcal{Q}_{\Lambda}$. In our paper, soft $\mathcal{Q}$-network uses the same MLP as the policy network. Specifically, $\mathcal{Q}$-network takes a (state, action) pair as an input and outputs a score that indicates the effectiveness of the action. Its associated Bellman equation is defined as:

where

is the state value function that denotes the expected reward obtained by the attacker at state $\textbf{s}_{k}$. The discount factor $\lambda=0.99$ is to limit the sum of the expected rewards. Details of training the soft $Q$-network is shown in the next subsection.

As required for the attacker, the number of modified edges for each perturbed graph in the sequence is limited to $\delta$. During the training process, the steps for each training episode is finite and fixed. In each attack step, the attacker agent adds a new edge as well as deletes an existing edge, therefore there are at most $\delta/2$ steps per episode.

Its loss function is defined as

where $\mathcal{D}$ is a replay buffer which collects a set of previous states, actions, and rewards. $\alpha$ is a temperature parameter that controls the stochasticity of the optimal policy. In practice, $\alpha$ is an important parameter that is learnt as follows:

where $\mathcal{H}_{0}$ is a predefined entropy threshold (e.g., $\mathcal{H}_{0}=-2$ in our paper). Minimizing loss function in Equation 7 can make the policy $\mathcal{P}_{\Phi}$ select multiple attractive actions whose probabilities are similar, instead of focusing on a single determinate action.

Furthermore, to estimate the density of the $\mathcal{Q}$-function with a lower variance estimator, we usually apply a reparameterization trick to reparameterize the policy using a neural network transformation $f_{\Phi}(\epsilon_{k};\textbf{s}_{k})$, where $\epsilon_{k}$ is an input noise, sampled from, e.g., a normal Gaussian distribution. Then, we can rewrite the loss in Equation 7 as

Its loss function is defined as:

where $\textbf{s}_{k}$ and $\textbf{a}_{k}$ are sampled from the relay buffer $\mathcal{D}$, and $\textbf{a}_{k+1}$ is sampled from the policy during the training process.

After defining the loss function of the parameterized policy network, parameterized soft $\mathcal{Q}$-network and temperature parameter, we can now train our RL-based attack model. Suppose we are given a trained DyGCN model $\mathcal{F}_{\Theta^{*}}$, a validation set, and a testing set. We use the validation set and the Adam algorithm to train our attack against the DyGCN model. Specifically, we first update the parameters $\Phi$ in the policy network $\mathcal{P}_{\Phi}$, which guides the policy improvement; Then, we update the temperature parameter $\alpha$ based on updated parameters $\Phi$. Third, we update the parameter $\Lambda$ in the soft $\mathcal{Q}$-network, which evaluates the effectiveness of the policy. We iteratively and alternatively update these parameters until reaching the terminal condition. Finally, we can evaluate our trained attack model on a testing set. The training process and evaluation process of our attack are detailed in Algorithm 1 and Algorithm 2, respectively.

We evaluate our RL-based black-box evasion attack to DyGCN, a state-of-the-art LPDG method, on three graph datasets, i.e., Haggle, Hypertext, and Trapping, from three different domains. We split each dataset into 30 graphs in a chronological order.

• •

  Haggle. This is a social network available at KONECT¹¹1http://konect.uni-koblenz.de/networks/contact, representing the connection between users measured by wireless devices. A node represents a user and an link between two person indicates a contact between them. The dataset was collected within 5 days.

• •

  Hypertext. This is a face-to-face contact network of  100 attendees to the ACM Hypertext 2009 conference held in Turin, Italy over three days from June 29 to July 1, 2009. The network is provided by SocioPatterns²²2http://www.sociopatterns.org/datasets. In the network, a node represents a conference attendee, and an edge represents a face-to-face contact between two attendees that was active for at least 20 seconds.

• •

  Trapping. This is a real-world animal interaction network from Network Data Repository³³3http://networkrepository.com/mammalia-voles-rob-trapping.php. The animal interaction data were from published studies of wild, captive, and domesticated animals. Each node represents an animal, a mammal, or a voles. An edge was added into the network whenever two voles were caught in at least one common trap over the primary trapping sessions. Each network in the dataset has a 12-hour time span.

Each dataset is divided into a training set, a validation set, and a testing set, where each training/validation/testing example consists of a sequence of $n=10$ graphs. As each dataset has 30 graphs, we have $20$ examples in total. We use $M_{tr}=10$ training examples to train DyGCN; $M_{val}=5$ validation examples to train our attack model; and the remaining $M_{te}=5$ testing examples to evaluate our attack. All our experiments are performed on a Linux machine with 128GB memory and 10 cores.

In DyGCN, the number of GCN layers is $L=3$ with each layer having 64 units, and LSTM has 2 layers. As our graph datasets do not have node features, we thus use the identity matrix to represent node feature matrix, similar to [35]. In our attack, there are several key parameters that could affect the attack performance: the fraction $\mu$ of total graphs to be perturbed in an example; the fraction $\rho$ of total nodes to be selected as the popular/neglected nodes; and the fraction $\delta$ of total edges to be perturbed in each graph. By default, we set $\mu=1.0$, $\rho=0.30$, and $\delta=0.02$. We also explore the impact of these parameters. We fix the other parameters as the default value when we study one specific parameter. Specifically, we set $\mu=\{0.6,0.8,1.0\}$, $\rho=\{0.15,0.30,0.45\}$, and $\delta=\{0.01,0.02,0.05\}$.

There are no existing works on attacking dynamic link prediction in the black-box setting. Here, we propose two baseline attacks and compare them with our attack under the same setting (e.g., the same number of graphs to be attacked, the same attack budget).

• •

  Random-whole. In this attack, the attacker randomly deletes an edge from and adds an edge to the whole graph in each attack step.

• •

  Random-partial. In this attack, in each attack step, the attacker randomly selects a pair of nodes from $V_{p}$ and deletes the edge if an edge exists between them; and selects another pair of nodes from $V_{n}$ and adds the edge if there is no edge between them.

Similar to existing works [5, 23, 21], we use $F_{1}$ score to evaluate the performance of a link prediction algorithm. Thus, the function $f$ in Equation 4 is the $F_{1}$ score. The higher/lower the $F_{1}$ score, the better/worse the link prediction method is. All results are reported in an averaged $F_{1}$ score on the testing examples.

Table 3 shows DyGCN’s performance on the clean graphs, i.e., no attack, and the perturbed graphs, i.e., with our attack and two random attacks. We observe that our attack is effective. For instance, compared with no attack, our attack has an $12.4\%$, $16.7\%$, and $45.5\%$ $F_{1}$ score degradation on the three datasets, respectively. Moreover, our attack is much more effective than random attacks. For instance, on Trapping, our attack has a $30.3\%$ and $22.8\%$ performance gain over Random-whole attack and Random-partial attack, respectively.

Figure 3 shows DyGCN’s $F_{1}$ score under all compared attacks vs. fraction $\delta$ of total edges perturbed. We observe that as $\delta$ increases, all attacks have better attack performance. This is because, a larger $\delta$ indicates that an attacker is capable of perturbing a larger number of links/edges. Moreover, our attack is much more effective than random attacks at a given $\delta$. For instance, when only $1\%$ edges can be perturbed, our attack can reduce the $F_{1}$ score with $8.8\%$, $9.0\%$, $37.9\%$, while random attacks reduce around $1.3\%$, $1.4\%$, and $16.6\%$, on the three datasets, respectively.

Figure 4 shows DyGCN’s $F_{1}$ score under all compared attacks vs. fraction $\rho$ of total nodes selected as the popular/neglected node set. Similarly, we observe that as $\rho$ increases, all attacks’ performance increases. However, our attack requires a much smaller $\rho$ than random attacks, in order to achieve a promising attack performance.

Figure 5 shows DyGCN’s $F_{1}$ score under all compared attacks vs. fraction $\mu$ of total graphs perturbed in each example. Similarly, we observe that as $\mu$ increases, $F_{1}$ score of all attacks decreases. However, our attack obtains a good attack performance when perturbing a relatively smaller number of graphs (e.g., $\mu=0.6$).

We use running time as the metric to evaluate the efficiency of training our attack. Figure 6 shows the running time vs. $\rho$, $\mu$, and $\delta$ on Haggle. When we observe one fraction, the other two are set to default values. Note that we have similar observations on the other two datasets, and thus show results on Haggle for simplicity. We observe that the running time is linear to the three parameters. Thus, we can conclude that our attack is also efficient.