# Sparse Vicious Attacks on Graph Neural Networks

Giovanni Trappolini,1111Corresponding Author at
<EMAIL_ADDRESS>Valentino Maiorca,2$\dagger$ Silvio
Severino,2$\dagger$ Emanuele Rodolà,2 Fabrizio Silvestri,1 Gabriele Tolomei 2
1Department of Computer Engineering, Sapienza University of Rome
2Department of Computer Science, Sapienza University of Rome

###### Abstract

Graph Neural Networks (GNNs) have proven to be successful in several
predictive modeling tasks for graph-structured data. Amongst those tasks, link
prediction is one of the fundamental problems for many real-world
applications, such as recommender systems. However, GNNs are not immune to
adversarial attacks, i.e., carefully crafted malicious examples that are
designed to fool the predictive model. In this work, we focus on a specific,
white-box attack to GNN-based link prediction models, where a malicious node
aims to appear in the list of recommended nodes for a given target victim. To
achieve this goal, the attacker node may also count on the cooperation of
other existing peers that it directly controls, namely on the ability to
inject a number of “vicious” nodes in the network. Specifically, all these
malicious nodes can add new edges or remove existing ones, thereby perturbing
the original graph. Thus, we propose SAVAGE, a novel framework and a method to
mount this type of link prediction attacks. SAVAGE formulates the adversary’s
goal as an optimization task, striking the balance between the effectiveness
of the attack and the sparsity of malicious resources required. Extensive
experiments conducted on real-world and synthetic datasets demonstrate that
adversarial attacks implemented through SAVAGE indeed achieve high attack
success rate yet using a small amount of vicious nodes. Finally, despite those
attacks require full knowledge of the target model, we show that they are
successfully transferable to other black-box methods for link prediction.

##  1 Introduction

††$\dagger$ Equal Contribution

The purpose of link prediction methods is to estimate the probability that an
edge between two initially disconnected nodes in a graph should exist
(Martínez, Berzal, and Cubero 2016; Kumar et al. 2020). For example, these
methods are used to suggest the creation of new connections between social
network users (e.g., follower-followee relationships).

Several approaches to link prediction have been proposed in the literature (Lü
and Zhou 2011). Recently, methods based on graph neural networks (GNNs) have
achieved state-of-the-art performance (Kipf and Welling 2017).

The list of predicted links for a given user ranked by their estimated
probability represents a set of recommended new contacts, which eventually the
user may decide to follow or not. This step is crucial, especially for some
authoritative, highly followed social network users, i.e., so-called
“influencers”. Indeed, their reputation (and therefore social market value)
may be affected by who they choose to follow. Specifically, when the target of
recommendations is an influencer, it is paramount to be accurate at suggesting
the “right” set of candidate users to follow. As a matter of fact, being
followed by an authoritative user can be seen as a sign of endorsement and
ultimately could bring several advantages to the followee (e.g., higher
revenue from advertising campaigns run on the social media platform due to
increased popularity). Hence, malicious users have a strong interest in
manipulating link recommendation systems to inflate their reputation on social
media platforms artificially, thus perpetuating their own (harmful) goals
through adversarial attacks. For example, consider Sammy is a social network
user interested in increasing their reputation. Ideally, they would have other
influential users follow them to reach this goal.. However, Sammy has no
control over other users, making such tactic unfeasible. Still, Sammy could
try to adjust their existing connections (i.e., follow/unfollow users) with
the hope that their name will show up in the list of recommended connections
for Terry, i.e., the user profile of a target influencer. More generally,
Sammy would control a subset of nodes (in addition to themselves) and is
allowed to modify their neighborhood to achieve their goal. Sammy may also be
able to inject new nodes in the network and create connections between such
“artificial” users and other existing nodes. Obviously, all these operations
(e.g., adding/deleting an edge between two nodes) have a cost, which Sammy
wants to account for and minimize. Although the body of work on adversarial
attacks on link prediction is extensive (Sun et al. 2018), most of the
literature do not completely cover the scenario described in the example
above. Indeed, most work assumes the attacker can perturb the original network
topology by adding or deleting connections only between existing nodes to
favor the malicious goal (Chen et al. 2020). However, this setting is often
unfeasible because it requires the direct control of real users, with
prohibitive coordination costs. To overcome this limitation, vicious node
adversarial attacks have been proposed (Wang et al. 2018). Under this setting,
the attacker can create new users ex-novo and, by controlling these nodes,
engineer the network to mount the attack. This approach is much more feasible
than directly controlling real nodes; indeed, the Internet is full of services
selling fake accounts/comments/likes.

Still, existing methods for implementing vicious node attacks do not
incorporate the cost of adding such malicious nodes into the adversary’s
objective (Wang et al. 2018). Those methods typically assume the existence of
an upper bound on the attacker’s budget allocation, which is generally
exhausted to favor the highest attack success rate possible. In other words,
if an attacker has a maximum allowed budget of $N$ vicious nodes to inject
into the network, it will use all of them to increase the chance of attack
success. We argue that this solution is inefficient and impractical. For this
reason, in this paper we introduce SAVAGE (SpArse Vicious Attacks on Graph
nEtworks). This is a novel framework that provides an original perspective on
vicious node adversarial attacks on GNN-based link prediction methods for
directed graphs. SAVAGE operates in a white-box setting and promotes a spare
use of the malicious resources required by the attacker, i.e., the number of
vicious nodes and their aggressiveness. Moreover, SAVAGE is general enough as
it allows to frame existing vicious node attacks into it.

(a) The original directed graph.

(b) A generic attack to mispredict the existence of the link between $t$ and
$s$.

(c) The attack generated by SAVAGE is still successful but uses a sparser
number of malicious resources.

Figure 1: The picture on the left (a) shows a simple directed graph, where the
red node indicates the source ($s$) and the blue node the target ($t$) of the
link prediction attack. In the middle (b), a generic attack is depicted: the
injection of vicious nodes (in purple) and new connections induce the link
prediction system to suggest the connection between $t$ and $s$. Typically,
these attacks exhaust the allocated attacker’s budget. On the other hand,
SAVAGE (c) enforces sparsity on the amount of malicious resources used,
deactivating unnecessary vicious nodes (grayed-out), while keeping the attack
successful.

Overall, the main novel contributions of this paper are as follows: (a) We
introduce SAVAGE, a novel framework that enables a comprehensive attack model
based on vicious nodes to generate adversarial attacks on GNN-based link
prediction systems; (b) SAVAGE trades off the power of the attack with the
number of malicious resources required by explicitly enforcing the sparsity of
vicious controlled nodes without assuming any constraint on the attacker’s
budget; (c) We show the feasibility and effectiveness of SAVAGE in attacking
several GNN-based link prediction models learned from real-world and synthetic
datasets through extensive experiments; (d) We demonstrate that adversarial
attacks generated with SAVAGE can be successfully transferred to harm other
link prediction systems (not necessarily GNN-based) under the more challenging
black-box setting.

All code and data is released as supplementary material.

##  2 Related Work

#### Link Prediction.

Link prediction is one of the most investigated problems in modern graph
analysis. One class of simple yet effective approaches for link prediction is
called heuristic methods. These assume that the existence of a link between
two nodes depends on their “similarity”. In practice, they use some predefined
heuristics to compute node similarity scores as the link probability (Liben-
Nowell and Kleinberg 2003; Lü and Zhou 2011). Popular heuristics include:
Common Neighbors (Newman 2001), Jaccard (Liben-Nowell and Kleinberg 2003),
Preferential Attachment (Barabási and Albert 2010), Adamic-Adar (Adamic and
Adar 2003a), Resource Allocation (Zhou, Lü, and Zhang 2009), Katz (Katz 1953),
PageRank (Brin and Page 1998), and SimRank (Jeh and Widom 2002).

Although working well in practice, heuristic methods have strong “hand-coded”
assumptions on when links may exist. To overcome this limitation, the link
prediction problem has been formulated as a standard binary classification
task and solved using well-known supervised learning techniques (Al Hasan et
al. 2006).

With the advancements of deep learning and, specifically, graph neural
networks (GNNs), several approaches have recently proposed effective GNN-based
link prediction methods (Zhang and Chen 2018; Li et al. 2021). Roughly
speaking, GNNs allow to learn suitable representations (i.e., embeddings) of
graph nodes by aggregating information derived from the local neighborhood of
each individual node. These node embeddings are in turn used as input of a
downstream link prediction function, thus making the whole model’s
architecture end-to-end trainable. In this work, we focus on a specific attack
to GNN-based link prediction.

For a comprehensive survey on link prediction, we refer the reader to
(Martínez, Berzal, and Cubero 2016; Kumar et al. 2020; Wu et al. 2020).

#### Adversarial Attacks to Link Prediction.

Although very powerful, studies have shown that machine learning models may be
vulnerable to so-called adversarial attacks, i.e., carefully crafted malicious
examples designed to fool the predictive models. Typically, these adversarial
inputs are generated by introducing minor – yet thoughtfully selected –
perturbations to regular inputs. These attacks have been widely proven
successful in many critical domains, such as image recognition (Goodfellow,
Shlens, and Szegedy 2015) and malware detection (Grosse et al. 2017). However,
a few works have explored how effective such adversarial attacks may be for
link prediction algorithms, especially those based on GNNs, which require the
attacker to perturb the input graph. Amongst these studies, it is worth
mentioning (Zügner, Akbarnejad, and Günnemann 2018; Chen et al. 2020; Lin, Ji,
and Li 2020). We refer the reader to (Dai et al. 2022) for a comprehensive
survey.

The methods above assume that the attacker can control a subset of existing
nodes. As stated in Section 1, though, this is a pretty unrealistic premise,
as it would be prohibitively expensive. To address this issue, (Wang et al.
2018) introduce the capability for the attacker to generate new (i.e.,
fake/vicious) nodes to mount the attack more efficiently. Furthermore, (Wang
et al. 2020a) propose a linear approximation of the previous method to make it
more scalable. Dai, Zhu, and Luo (2022) formulate a universal perturbation
that can target multiple nodes and still remain effective.

In both classic and vicious settings, all the methods presented so far
introduce an unnoticeability constraint of the graph perturbation. This
constraint is usually of two kinds: either the attacker is given a fixed
budget to spend (Chen et al. 2020), or some rules are imposed to control the
difference between the original and the perturbed graph, like in (Lin, Ji, and
Li 2020). Either way, this is treated as an upper bound on the amount of
“malicious resources” used to implement the attack and does not promote
frugality. In fact, the adversary typically saturates the constraint to ensure
that the attack is successful. On the other hand, the method we propose in
this work enforces the sparsity of the malicious resources used by the
attacker (see Fig. 1).

##  3 Background and Notation

We consider a directed graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ with $n$
nodes $\mathcal{V}$, and $m$ edges $\mathcal{E}$. The structure of
$\mathcal{G}$ is encoded by its adjacency matrix $A\in\\{0,1\\}^{n\times n}$,
where ${A}_{i,j}$ = 1 iff $(i,j)\in\mathcal{E}$. Notice that, in general,
${A}_{i,j}\neq A_{j,i}$, i.e., the adjacency matrix is not symmetric. A
feature matrix $X\in\mathbb{R}^{n\times k}$ can also be used to associate
features to nodes of $\mathcal{G}$. We assume that a graph neural network
(GNN) $g$ learns a hidden representation of nodes in the graph (i.e., a node
embedding). Such representation is, in turn, used for our downstream task of
interest (i.e., link prediction).

The embedding of each node is learned through $g$ by iteratively updating the
node’s features based on the neighbors’ features. Formally, let
$\bm{h}^{l}_{u}$ denote the embedding of node $u\in\mathcal{V}$ at the $l$-th
layer of $g$.

Let
$\mathcal{N}^{1}(u)=\mathcal{N}(u)=\\{v\in\mathcal{V}~{}|~{}(u,v)\in\mathcal{E}\\}$
be the $1$-hop neighborhood of $u\in\mathcal{V}$, i.e., the set of all nodes
that are adjacent to $u$. More generally, we can define the $l$-hop
neighborhood of $u$ ($l\in\mathbb{Z}^{+},~{}l>1$) as the set of nodes that are
at most $l$ hops away from $u$, using the following recurrence relation:

$\mathcal{N}^{l}(u)=\mathcal{N}^{1}(u)\cup\bigcup_{v\in\mathcal{N}(u)}\mathcal{N}^{l-1}(v).$

Hence, let us consider the subgraph $\mathcal{G}^{l}_{u}$ of $\mathcal{G}$
induced by $u$ and its $l$-hop neighborhood $\mathcal{N}^{l}(u)$ as relevant
for the computation of $\bm{h}^{l}_{u}$. Specifically, we consider $A^{l}_{u}$
and $X^{l}_{u}$ as the adjacency matrix and the feature matrix of nodes in the
subgraph $\mathcal{G}^{l}_{u}$, respectively, and $\bm{h}^{l}_{u}$ is computed
by $g$ using the following equation:

$\bm{h}^{l}_{u}=g(A^{l}_{u},X^{l}_{u};\bm{\theta}_{g})=\phi(\bm{h}^{l-1}_{u},\psi(\\{\bm{h}^{l-1}_{v}~{}|~{}v\in\mathcal{N}(u)\\})),$
(1)

where $\phi$ and $\psi$ are arbitrary differentiable functions (i.e., neural
networks): $\psi$ is a permutation-invariant operator that aggregates the
information from the $l$-hop neighborhood of $u$; $\phi$ updates the node
embedding of $u$ by combining information from the previous layer;
$\bm{\theta}_{g}$ are the trainable parameters of $g$. The number of hidden
layers in $g$ determines the set of neighbors included while learning each
node’s embedding. From now on, unless otherwise needed, we will consider $l$
fixed and omit the corresponding superscript.

Given the graph
$\mathcal{G}^{\text{obs}}=(\mathcal{V},\mathcal{E}^{\text{obs}})$, where
$\mathcal{E}^{\text{obs}}\subset\mathcal{E}$ is a subset of the true links
observed, the link prediction problem generally resorts to estimating the
probability that an edge exists between two nodes $u$ and $v$, i.e.,
$\mathbb{P}[(u,v)\in\mathcal{E}\setminus\mathcal{E}^{\text{obs}}]$.

Let $\bm{h}_{w}=g(A_{w},X_{w};\bm{\theta}_{g})$ be the embedding of the
generic node $w\in\mathcal{V}$. Thus, we assume that the predicted link
probability between two nodes $u$ and $v$ is approximated with a function $f$,
defined as follows:

$f(\bm{h}_{u},\bm{h}_{v};\bm{\theta}_{f})=f(g(A_{u},X_{u};\bm{\theta}_{g}),g(A_{v},X_{v};\bm{\theta}_{g});\bm{\theta}_{f}).$
(2)

Notice that $f$ can itself be another neural network (e.g., an MLP) that takes
as input two node embeddings learned by the GNN $g$ and outputs their link
prediction.

A combined embedding $\bm{h}_{u,v}$ of the two input nodes can be obtained,
for example, via Hadamard (element-wise) product, i.e.,
$\bm{h}_{u,v}=\bm{h}_{u}\odot\bm{h}_{v}$. Eventually, the probability of a
link existing between $u$ and $v$ can be computed as
$f(\bm{h}_{u},\bm{h}_{v};\bm{\theta}_{f})=\sigma(\bm{\theta}_{f}^{T}\bm{h}_{u,v})$,
where $\sigma(x)=\frac{1}{1+e^{-x}}$ is the sigmoid activation function at the
last output layer of $f$.

In the following, we denote as $\bm{\theta}$ the overall set of end-to-end
trainable parameters of $f$ and $g$, i.e.,
$\bm{\theta}=\left[\bm{\theta}_{f},\bm{\theta}_{g}\right]$.

##  4 Problem Formulation

###  4.1 Attack Model

We consider a snapshot of a network, modeled as a directed graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, and a trained GNN-based link
prediction model $f$. In our attack model, we assume the existence of an
attacker node ($s\in\mathcal{V}$) that can perturb the original graph
$\mathcal{G}$ into
$\widetilde{\mathcal{G}}=(\mathcal{V}^{\prime},\mathcal{E}^{\prime})$. The
perturbation represents the capability of the attacker to add a set of new
vicious nodes $\mathcal{V}^{\text{new}}$ to $\mathcal{G}$, such that
$\mathcal{V}^{\prime}=\mathcal{V}\cup\mathcal{V}^{\text{new}}$. Furthermore,
we suppose the attacker controls a subset of the original nodes
$\mathcal{V}^{s}\subseteq\mathcal{V}$ (trivially, $s\in\mathcal{V}^{s})$ and
is capable of adding/removing edges starting from the set of governed nodes
$\mathcal{V}^{s}\cup\mathcal{V}^{\text{new}}$. Let
$\mathcal{E}^{+}\subseteq(\mathcal{V}^{s}\cup\mathcal{V}^{\text{new}})\times\mathcal{V}^{\prime}$
and
$\mathcal{E}^{-}\subseteq(\mathcal{V}^{s}\cup\mathcal{V}^{\text{new}})\times\mathcal{V}^{\prime}$
be the set of edges added and removed by the attacker, respectively.
Eventually,
$\widetilde{\mathcal{G}}=(\mathcal{V}^{\prime},\mathcal{E}^{\prime})$ denotes
the final perturbed graph, where
$\mathcal{E}^{\prime}=\mathcal{E}\cup\mathcal{E}^{+}\setminus\mathcal{E}^{-}$.
Thus, the goal of the attacker $s$ is to transform $\mathcal{G}$ into
$\widetilde{\mathcal{G}}$, using the capabilities described above, to
ultimately induce the link prediction model $f$ in recommending $s$ to a
target victim node
$t\in\mathcal{V}\setminus(\mathcal{V}^{s}\cup\mathcal{V}^{\text{new}})$, i.e.,
to suggest the creation of the directed edge $(t,s)$ between the victim and
the attacker. We also assume the attacker has full knowledge of $f$, i.e., we
consider a white-box threat model, where the architecture and the entire set
of parameters of $f$
($\bm{\theta}=\left[\bm{\theta}_{f},\bm{\theta}_{g}\right]$) are known and
fixed (Pitropakis et al. 2019; Ren et al. 2020). Later in Section 6.4, we show
that this requirement does not limit the adversary’s power, as our proposed
attack can be successfully transferred to disrupt other link prediction models
in a black-box setting.

###  4.2 Attack Framework

The attacker $s$ aims to maximize the chance that the directed edge between
the target victim $t$ and itself, i.e., $(t,s)$, will be amongst those
predicted by $f$ while minimizing the “malicious effort” needed.

More formally, suppose $f$ is defined as in Eq. 2. To ease the notation, we
will omit the parameters $\bm{\theta}_{f}$ and $\bm{\theta}_{g}$ from the
equations below. Also, let $A$, $A^{\prime}$, and $\widetilde{A}$ be the
adjacency matrices associated with the original graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, the intermediate graph
$\mathcal{G}^{\prime}=(\mathcal{V}^{\prime},\mathcal{E})$, and the final
perturbed graph
$\widetilde{\mathcal{G}}=(\mathcal{V}^{\prime},\mathcal{E}^{\prime})$,
respectively. Thus, the problem for the attacker $s$ is to find the optimal
perturbation $\widetilde{\bm{h}}^{*}_{s}\neq\bm{h}_{s}$ such that
$f(\bm{h}_{t},\widetilde{\bm{h}}^{*}_{s})\neq f(\bm{h}_{t},\bm{h}_{s})$ by
solving the objective below:

$\displaystyle\widetilde{\bm{h}}^{*}_{s}~{}={}$
$\displaystyle\operatorname*{arg\,max}_{\widetilde{\bm{h}}_{s}}\Big{\\{}\big{[}f(\bm{h}_{t},\widetilde{\bm{h}}_{s})-f(\bm{h}_{t},\bm{h}_{s})\big{]}-d(\widetilde{\bm{h}}_{s},\bm{h}_{s})\Big{\\}},$
(3)

where $f(\bm{h}_{t},\widetilde{\bm{h}}_{s})-f(\bm{h}_{t},\bm{h}_{s})$ measures
the difference between the original and the adversarial link prediction, and
$d$ captures the magnitude of the malicious effort used by the attacker for
transforming $\bm{h}_{s}$ to $\widetilde{\bm{h}}_{s}$.

The generic perturbation $\widetilde{\bm{h}}_{s}=g(\widetilde{A}_{s},X_{s})$
indicates the attacker node embedding output by a trained GNN $g$, after the
$1$-hop neighborhood of the nodes controlled by the attacker
$\mathcal{V}^{s}\cup\mathcal{V}^{\text{new}}$ has been modified according to
its capabilities (i.e., by adding/removing edges as specified by
$\mathcal{E}^{+}$ and $\mathcal{E}^{-}$, respectively). Specifically, we
assume there exists a function $\pi$ that works as follows:

$\widetilde{\bm{h}}_{s}=g(\pi(A^{\prime}),X_{s})=g(\widetilde{A}_{s},X_{s}),$
(4)

where $A^{\prime}$ is the full adjacency matrix associated with the
intermediate graph $\mathcal{G}^{\prime}$, and
$\widetilde{A}_{s}=\pi(A^{\prime})$. Notice that the perturbation applied by
$\pi$ reflects the attacker’s capabilities described in our attack model,
i.e., it concerns only the topological structure of the neighborhood of the
nodes controlled by the attacker, whereas the node feature matrices are left
unaltered. We acknowledge that the ability to modify also the node feature
matrices is an interesting direction to explore, and we plan to investigate
this as future work since our framework is general enough to cover also that
scenario. Moreover, the perturbation induced by $\pi$ on $\bm{h}_{s}$ must not
affect the embedding of the target victim node $\bm{h}_{t}$. According to Eq.
1, the hidden representation of a node $u$ produced by a given $l$-layer GNN
($\bm{h}_{u}$) is influenced by all the other nodes $v$ that are in the
$l$-hop neighborhood of $u$, i.e., $\mathcal{N}^{l}(u)$. Thus, to avoid that
$\bm{h}_{t}$ is affected by $\pi$, we assume $t\notin\mathcal{N}^{l}(s)$ and,
even strongly, $s\notin\mathcal{N}^{l}(t)$.

To measure the malicious effort of the attacker, the function $d$ captures the
difference between the original and the perturbed attacker node embeddings.
Such a difference must consider: (i) the number of additional vicious nodes
$\mathcal{V}^{\text{new}}$ injected by the attacker to generate the
intermediate augmented graph $\mathcal{G}^{\prime}$; (ii) the distance between
the original adjacency matrix $A_{s}$ and the perturbed $\widetilde{A}_{s}$
obtained from structural modifications (i.e., edge additions/deletions) of
$\mathcal{G}^{\prime}$.

##  5 Method

In this section, we describe the method used by the attacker to solve the
optimization problem defined in Eq. 3, which we overall refer to as SAVAGE.

We consider the function $\pi$ parametrized by a perturbation matrix $P$,
i.e., $\pi(\cdot;P)$, and thus rewrite Eq. 4 as follows:

$\widetilde{\bm{h}}_{s;P}=g(\pi(A^{\prime};P),X_{s})=g((P\oplus
A^{\prime}),X_{s})=g(\widetilde{A}_{s},X_{s}),$ (5)

namely $\widetilde{A}_{s}=\pi(A^{\prime};P)=P\oplus A^{\prime}$, where
$\oplus$ is the element-wise matrix addition.

The perturbation matrix $P\in\\{-1,0,1\\}^{n\times n}$ is a discrete squared
matrix, where $n=|\mathcal{V}^{\prime}|$ is the total number of nodes of the
augmented graph $\mathcal{G}^{\prime}=(\mathcal{V}^{\prime},\mathcal{E})$.
This includes the set of additional vicious nodes $\mathcal{V}^{\text{new}}$
injected by the attacker into the original graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$ (i.e.,
$\mathcal{V}^{\prime}=\mathcal{V}\cup\mathcal{V}^{\text{new}}$), yet keeping
the same set of original edges $\mathcal{E}$, thus is represented by the
adjacency matrix $A^{\prime}$. For each
$i\in\mathcal{V}^{s}\cup\mathcal{V}^{\text{new}},j\in\mathcal{V}^{\prime}$:

$P_{i,j}=\begin{cases}+1&\text{if $(i,j)\in\mathcal{E}^{+}$: {\em add} the
edge between $i$ and $j$,}\\\ -1&\text{if $(i,j)\in\mathcal{E}^{-}$: {\em
remove} the edge between $i$ and $j$,}\\\ 0&\text{otherwise.}\end{cases}$

Hence, for a given perturbation matrix $P$, a graph $\mathcal{G}^{\prime}$
with $\mathcal{V}^{\text{new}}$ vicious nodes, a pair of source (attacker) and
target (victim) nodes $s,t\in\mathcal{V}$, and a fixed GNN-based link
prediction model $f$, such that $(t,s)\notin\mathcal{E}\wedge
f(\bm{h}_{t},\bm{h}_{s})=0$, we can compute the following (instance-level)
loss function:

$\mathcal{L}(P)=\ell_{\text{adv}}[f(\bm{h}_{t},\widetilde{\bm{h}}_{s;P})]+\beta\ell_{\text{dist}}(\bm{h}_{s},\widetilde{\bm{h}}_{s;P})+\gamma\ell_{\text{new}}(\bm{v}^{\text{new}})$
(6)

The first component ($\ell_{\text{adv}}$) penalizes when the adversarial
prediction goal is not satisfied and can be computed as:

$\ell_{\text{adv}}[f(\bm{h}_{t},\widetilde{\bm{h}}_{s;P})]=-\log[f(\bm{h}_{t},\widetilde{\bm{h}}_{s;P})],$
(7)

which corresponds to a standard binary cross-entropy, where the class label to
predict is always $1$, i.e., we want to enforce the prediction of an
adversarial edge between $t$ and $s$.

The second component ($\ell_{\text{dist}}$) is an arbitrary distance function
that discourages $\widetilde{\bm{h}}_{s;P}$ from being too far away from
$\bm{h}_{s}$, namely $\widetilde{A}_{s}$ must be close to the original
$A_{s}$. For example,
$\ell_{\text{dist}}(\bm{h}_{s},\widetilde{\bm{h}}_{s;P})=||A_{s}-\widetilde{A}_{s}||_{p}$,
where $||\cdot||_{p}$ is the $L^{p}$-norm.

The third component ($\ell_{\text{new}}$) controls the number of vicious nodes
injected into the original graph network. In practice, $\bm{v}^{\text{new}}$
is a $|\mathcal{V}^{\text{new}}|$-dimensional binary vector (i.e., a mask)
indicating the vicious nodes injected by the attacker, i.e.,
$\bm{v}^{\text{new}}[u]=1$ iff node $u\in\mathcal{V}^{\text{new}}$ has been
added to the graph network, $0$ otherwise. For example,
$\ell_{\text{new}}(\bm{v}^{\text{new}})=||\bm{v}^{\text{new}}||_{p}$. In this
work, we set $p=1$ both for $\ell_{\text{dist}}$ and $\ell_{\text{new}}$.

Eventually, solving the objective defined in Eq. 3 is framed into the
following optimization task:

$\widetilde{\bm{h}}_{s;P^{*}}=\operatorname*{arg\,min}_{P}\mathcal{L}(P).$ (8)

It is worth noticing that, in this original formulation, the optimization
objective defined in Eq. 8 is inherently discrete. To make it smooth, inspired
by prior work (Lucic et al. 2022; Srinivas, Subramanya, and Babu 2017), we
first consider an intermediate, real-valued perturbation matrix $\hat{P}$ with
entries in $(-1,1)$, obtained by applying a hyperbolic tangent transformation
($\tanh$). Intuitively, this matrix indicates the degree of confidence of the
attacker to add or remove an edge from the adjacency matrix $A^{\prime}$.
Thus, we can replace $P$ with $\hat{P}$ in Eq. 8, and solve the objective via
standard gradient-based optimization methods like stochastic gradient descent
or similar. Eventually, to obtain the discrete matrix $P$, we simply threshold
the entries of $\hat{P}$ as follows:

$P_{i,j}=\begin{cases}+1&\text{if $\hat{P}_{i,j}\geq t^{+}$,}\\\ -1&\text{if
$\hat{P}_{i,j}\leq t^{-}$,}\\\ 0&\text{otherwise.}\end{cases}$

A straightforward choice for the thresholds above is: $t^{+}=0.5$ and
$t^{-}=-0.5$. Notice, though, that $P\oplus A^{\prime}$ would lead to a
discrete matrix $\widetilde{A}_{s}$ whose entries are in the set
$\\{-1,0,1,2\\}$, instead of $\\{0,1\\}$ as required. Indeed, removing an edge
that does not exist from $\mathcal{E}$, will lead to an entry equals to $-1$;
on the other hand, adding an edge that already exists in $\mathcal{E}$ will
result in an entry equals to $2$.

We therefore obtain the correct final perturbed matrix $\widetilde{A}_{s}$ by
applying a $\operatorname*{clamp}_{[0,1]}$ function element-wise, i.e.,
$\widetilde{A}_{s}[i,j]=\operatorname*{clamp}_{[0,1]}(P_{i,j}+A^{\prime}_{i,j})~{}\forall(i,j)$,
where $\operatorname*{clamp}_{[0,1]}(x)=\max(0,\min(x,1))$.

##  6 Experiments

We evaluate the effectiveness of SAVAGE on several challenges. First, we
assess the power of our attack model by reporting some key performance
metrics. Second, we analyze the impact of the critical components of our model
through ablation studies. Finally, we demonstrate the ability of SAVAGE to
generate attacks that transfer toward other black-box link prediction systems.
We have released code on Github 222https://github.com/GiovanniTRA/SAVAGE.

###  6.1 Experimental Setting

#### Datasets.

We validate our method both on real-world and synthetic datasets. Moreover, as
dictated by our attack model, we focus only on data representing directed
graphs. Our real world datasets are mainly of two kinds: citation-based and
social networks. The former category includes _Cora_ (Kunegis 2013; Šubelj and
Bajec 2013), _Arxiv_ (Wang et al. 2020b), and _Citation2_ (Wang et al. 2020b),
whereas the latter contains _Twitter_ (McAuley and Leskovec 2012), _Wikipedia-
Vote_ (Leskovec, Huttenlocher, and Kleinberg 2010b, a), and _GPlus_ (McAuley
and Leskovec 2012). Furthermore, we test our method on a synthetic dataset,
partially taken from (Fey and Lenssen 2019), that we call _Synthetic_. It is
worth noticing that, to properly test our method, we choose datasets featuring
a varying degree of cardinality and density. For further details on the
preprocessing steps taken and additional statistics, we refer the reader to
the supplementary material.

#### GNN Models.

To evaluate the effectiveness of SAVAGE, we first train a GNN-based link
prediction system. The model is composed of two stacked convolutional layers
of 128 and 64 hidden units, respectively, and a two-layer MLP with a sigmoid
activation function at the last output layer. In our setup, we minimize the
prediction error with a binary cross-entropy loss using Adam optimizer with
$3\times 10^{-3}$ learning rate. Finally, we compute the accuracy (using $0.6$
as classification threshold) and the AUROC (Area Under the ROC) curve of the
learned GNN-based link predictor. On average, the best model achieves $85\%$
accuracy and $0.86$ AUROC score on every dataset considered. The full details
are available in the supplementary material.

#### Methods.

We test our method against different competitors and under several settings.
First, we consider a simple random baseline (RAND). This can add/remove
connections in the graph and activate/deactivate vicious nodes with a
probability $p$; the larger $p$, the stronger the corresponding attacker. We
denote by RAND-L and RAND-H the baseline with the lowest and the highest
probability of addition/activation, i.e., $p_{\text{L}}=0.25$ and
$p_{\text{H}}=0.75$. While we cannot perform a direct comparison with other
methods, as they are not naturally designed for our setting, we adapt the
greedy technique proposed in (Wang et al. 2018) and (Chen et al. 2020) to work
in our framework, and we call it AIGA (Adapted Iterative Gradient Attack).
Finally, we consider four instances of our method: (i) SAVAGE, (ii) SAVAGE-N,
(iii) SAVAGE-I, and (iv) SAVAGE-NI. SAVAGE refers to the plain full framework,
randomly initialized and defined in Eq. 6; SAVAGE-N is the same as SAVAGE yet
without the penalty losses (i.e., $\ell_{\text{dist}}$ and
$\ell_{\text{new}}$); SAVAGE-I is the same as SAVAGE yet initialized with the
output from AIGA; and SAVAGE-NI is the same as SAVAGE-N yet initialized with
the output from AIGA. Since SAVAGE tries to solve a highly non-convex problem,
the initialization of the parameters is indeed crucial. Distinguishing between
random and AIGA-based initialization serves two purposes. First, it shows that
SAVAGE can be used just as a sparsifying framework, compatible with other
techniques; second, it demonstrates the impact of initialization on the
optimization problem. For all the models considered, performance is reported
according to their best hyperparameter setting, which is detailed in the
supplementary material.

#### Evaluation Metrics.

Given a graph and a GNN-based link prediction model trained on it, we
uniformly sample a source and a target node from the graph, providing that the
two nodes are disconnected and, even further, they are not part of each
other’s 2-hop neighborhood. Moreover, according to the link prediction model,
no edge should exist between the two sampled nodes. Then, we attack the graph
using all the methods described above (i.e., the four variants of our SAVAGE
along with its competitors) and run again the link prediction on the resulting
perturbed graph. We repeat this procedure for 20 different node pairs, for
each dataset used. We present our results according to the following metrics.
The average prediction under attack (AP) is the estimated probability output
by the link prediction model after the attack. The attack rate (AR) measures
the fraction of successful attacks, i.e., it counts the fraction of
predictions above the success threshold ($0.6$). AP and AR capture two
different aspects of the attack power. The former indicates the average
strength of each attack (i.e., the new link probability between the source and
target node, which initially was below the success threshold). The latter
measures only how frequently the new link probability is large enough for the
attack to succeed, regardless of its actual value. Finally, we report
statistics on the perturbation induced by SAVAGE on the original graph
topology: the number of vicious nodes injected (AN) and the shift in the
node’s degree distribution before and after the attack as measured with the
Kullback-Leibler divergence (KL).

###  6.2 Attack Power

We measure the power of the attacks generated by all the methods examined on
the real-world and synthetic datasets; the results are shown in Table 1. We
may observe that SAVAGE can mount very effective attacks across all datasets,
with the highest AP and AR between all the considered methods. In terms of AR,
we notice a positive correlation between the performance gap and the density
of the dataset. Furthermore, SAVAGE significantly reduces the number of
malicious resources used (AN) w.r.t. to AIGA, ranging from a minimum of 20% up
to 80% decrease and the KL score illustrates the limited impact on graph
connectivity, especially when compared with the baselines (see Section 6.5 for
additional discussion). We observe that the AIGA initialization can further
mitigate this impact at the cost of a slightly worse AR in sparser graphs.
This may be caused by the initialization that imposes the solution to get
stuck around the starting local minimum. In other words, this analysis shows
that SAVAGE (i) generates more successful attacks than competitors, (ii) with
stronger confidence, and (iii) does not rely on the introduction of random
noise since random baselines are not able to disrupt the prediction even when
using a comparable number of resources.

Table 1:  We report several metrics regarding the effectiveness and efficacy
of SAVAGE. First, we manage to mount very effective link prediction attacks.
Second, thanks to our penalized framework, we are able to greatly reduce the
amount of vicious nodes required. KL is in reported in base $10^{-3}.$

| Twitter | GPlus | Citation2
---|---|---|---
Method | AR $\uparrow$ | AN $\downarrow$ | AP $\uparrow$ | KL $\downarrow$ | AR $\uparrow$ | AN $\downarrow$ | AP $\uparrow$ | KL $\downarrow$ | AR $\uparrow$ | AN $\downarrow$ | AP $\uparrow$ | KL $\downarrow$
SAVAGE | $0.75$ | $\mathbf{57.95}$ | $0.73$ | $3.00$ | $0.80$ | $\mathbf{35.70}$ | $0.79$ | $0.03$ | $0.85$ | $13.10$ | $0.87$ | $1.00$
SAVAGE-I | $0.75$ | $61.05$ | $0.70$ | $3.00$ | $\mathbf{0.97}$ | $38.70$ | $\mathbf{0.95}$ | $0.03$ | $\mathbf{1.00}$ | $\mathbf{7.05}$ | $0.98$ | $0.30$
SAVAGE-N | $0.95$ | $95.30$ | $0.93$ | $4.00$ | $0.93$ | $46.70$ | $0.90$ | $1.00$ | $0.85$ | $37.70$ | $0.89$ | $4.00$
SAVAGE-NI | $\mathbf{1.00}$ | $95.55$ | $\mathbf{0.99}$ | $4.00$ | $\mathbf{0.97}$ | $50.00$ | $\mathbf{0.95}$ | $0.03$ | $\mathbf{1.00}$ | $47.10$ | $\mathbf{0.99}$ | $3.00$
AIGA | $0.60$ | $100.0$ | $0.61$ | $\mathbf{0.00}$ | $0.23$ | $50.00$ | $0.29$ | $\mathbf{0.00}$ | $0.90$ | $50.00$ | $0.93$ | $\mathbf{0.03}$
RAND-L | $0.00$ | $23.15$ | $0.04$ | $5.00$ | $0.00$ | $13.70$ | $0.04$ | $1.00$ | $0.05$ | $12.95$ | $0.03$ | $6.00$
RAND-H | $0.10$ | $74.70$ | $0.11$ | $10.00$ | $0.00$ | $37.35$ | $0.06$ | $10.00$ | $0.00$ | $38.85$ | $0.03$ | $10.00$

| Arxiv | Cora | Wiki | Synthetic
---|---|---|---|---
Method | AR $\uparrow$ | AN $\downarrow$ | AP $\uparrow$ | KL $\downarrow$ | AR $\uparrow$ | AN $\downarrow$ | AP $\uparrow$ | KL $\downarrow$ | AR $\uparrow$ | AN $\downarrow$ | AP $\uparrow$ | KL $\downarrow$ | AR $\uparrow$ | AN $\downarrow$ | AP $\uparrow$ | KL $\downarrow$
SAVAGE | $0.80$ | $35.70$ | $0.80$ | $5.00$ | $0.83$ | $47.60$ | $0.83$ | $1.00$ | $\mathbf{1.00}$ | $14.20$ | $0.88$ | $7.00$ | $\mathbf{1.00}$ | $14.00$ | $0.88$ | $7.00$
SAVAGE-I | $0.75$ | $\mathbf{34.90}$ | $0.75$ | $5.00$ | $\mathbf{0.96}$ | $\mathbf{33.60}$ | $\mathbf{0.97}$ | $\mathbf{0.04}$ | $0.60$ | $\mathbf{10.25}$ | $0.63$ | $3.00$ | $0.60$ | $\mathbf{9.00}$ | $0.63$ | $3.00$
SAVAGE-N | $\mathbf{0.95}$ | $44.55$ | $\mathbf{0.93}$ | $5.00$ | $0.83$ | $59.80$ | $0.83$ | $3.00$ | $\mathbf{1.00}$ | $29.70$ | $\mathbf{0.96}$ | $7.00$ | $\mathbf{1.00}$ | $29.00$ | $\mathbf{0.96}$ | $7.00$
SAVAGE-NI | $0.90$ | $43.05$ | $0.89$ | $5.00$ | $0.70$ | $49.40$ | $0.69$ | $3.00$ | $0.70$ | $11.10$ | $0.68$ | $3.00$ | $0.70$ | $11.00$ | $0.68$ | $3.00$
AIGA | $0.70$ | $50.00$ | $0.67$ | $\mathbf{0.00}$ | $0.80$ | $80.00$ | $0.79$ | $0.40$ | $0.40$ | $50.00$ | $0.47$ | $\mathbf{0.00}$ | $0.90$ | $50.00$ | $0.93$ | $\mathbf{0.03}$
RAND-L | $0.10$ | $11.40$ | $0.11$ | $6.00$ | $0.00$ | $17.50$ | $0.00$ | $4.00$ | $0.10$ | $13.10$ | $0.29$ | $3.00$ | $0.10$ | $13.10$ | $0.31$ | $6.00$
RAND-H | $0.15$ | $37.70$ | $0.14$ | $10.00$ | $0.00$ | $60.15$ | $0.00$ | $10.00$ | $0.05$ | $36.65$ | $0.29$ | $10.00$ | $0.10$ | $37.40$ | $0.22$ | $30.00$

###  6.3 Ablation Study

We perform an extensive ablation study to support the design choices made for
the main components of our framework. A key characteristic of SAVAGE is its
ability to enforce sparsity of malicious resources by adjusting the
optimization goal of the attacker. We analyze several components of the model,
like the initialization of the perturbation matrix and the effect of the
penalty losses, to study their behavior and how this impacts the
sparsification effort.

Figure 2: Visualizations of gradients for the model with $\ell_{\text{dist}}$
and $\ell_{\text{new}}$ (left), and without (right). Each cell describes the
activation strength of a vicious node. In blue are deactivated nodes. We
(visually) show that our losses successfully induce a sparse usage of
malicious resources.

We provide here a graphic visualization of our findings on SAVAGE inner
working. In Fig. 2, we inspect the gradients of our model with our introduced
sparsity losses $\ell_{\text{dist}}$ and $\ell_{\text{new}}$ (left) against
the model not featuring them (right). It is highly evident that most vicious
nodes on the left are deactivated (encoded with blue), and do not contribute
as additional resources to mount the attack. This is not true for gradients on
the right, which instead have a much higher diffusion, with credits being
awarded to the largest number of vicious nodes possible. Thus, we argue this
is further proof that our formulation is effective in injecting sparsity into
the model, making more efficient usage of malicious resources. Again, we
remind that we do not directly optimize for the feature matrix of the graph,
focusing instead on its topology, and leaving it for future work. Still, we
conduct a comprehensive analysis, showing that SAVAGE is robust under
different assumptions for the creation of the vicious nodes’ features. For the
entire set of results from our ablation study we refer the reader to the
supplementary material.

###  6.4 Attack Transferability

SAVAGE defines a white-box attack model, i.e., it assumes a full knowledge of
the target GNN-based link prediction model. This assumption may be unrealistic
in practice; indeed, the internals of a link prediction system (e.g., the
model’s architecture, parameters, or gradients) are rarely disclosed,
especially in a commercial scenario. Nevertheless, we claim that this
restriction does not limit the feasibility of our method. In fact, we show
that the adversarial perturbations generated by SAVAGE can be successfully
transferred to fool other link prediction systems (not necessarily GNN-based)
under the more challenging black-box setting. Specifically, to demonstrate
this capability, we focus on several link prediction heuristics, as reported
in Table 2. The higher the value of these heuristics, the higher the chance of
a link between two nodes. For a given graph, a source and a target node
initially disconnected, and a white-box GNN-based link predictor, we generate
the corresponding perturbation with SAVAGE so to increase the probability of a
connection between the victim and the source. The scores in Table 2 are
expressed in terms of the lift of the heuristic values as computed in the
original, unperturbed graph, i.e., before and after the attack, averaged
across 20 different pairs of sampled source and target nodes. We observe an
increase of all the heuristic values considered, which indicates that SAVAGE
would be able to mount attacks even on non-GNN-based link prediction systems.

Table 2:  Lift scores for popular link prediction heuristics before and after being attacked by SAVAGE. Given the large increase in heuristic values after the attack, we claim that our attacks successfully transfer to different black-box methods.  Heuristic |  | Lift Score
---
(attack/non-attack)
Common Neighbors (Newman 2001) | $70\times$
Jaccard (Liben-Nowell and Kleinberg 2003) | $93\times$
Preference Attachment (Barabási and Albert 2010) | $3.4\times$
Adam-Adar (Adamic and Adar 2003b) | $61\times$
Resource Allocation (Zhou, Lü, and Zhang 2009) | $2.9\times$
Katz Index (Katz 1953) | $3e5\times$
PageRank (Brin and Page 1998) | $1.2\times$
SimRank (Jeh and Widom 2002) | $20\times$

###  6.5 Limitations

Experiments have demonstrated that SAVAGE can achieve a high attack success
rate while using a sparse number of new, malicious nodes. However, SAVAGE
causes a shift in the node’s degree distribution between the original and the
attacked graph larger than other methods, thus indicating a more substantial
perturbation of the initial graph links. We argue that, in general, from the
attacker’s perspective, the cost of adding a vicious node to the network is
the most relevant and that should receive the highest priority. Moreover, on
average, the KL-divergence between the two node distributions is smaller than
$10^{-3}$ with SAVAGE. Still, we acknowledge this as a limitation of our
current method. We plan to incorporate a new factor (based on the KL-
divergence above) in the attacker’s objective, limiting the impact of SAVAGE
on the original graph connections.

##  7 Conclusion and Future Work

In this work, we presented SAVAGE, a novel framework for generating
adversarial attacks on GNN-based link prediction systems. SAVAGE defines a
white-box attack model where an adversary aims to appear in the list of
recommended users to follow for a target victim node. The attacker controls a
subset of original nodes and some additional vicious nodes that can inject
into the network. Each of these malicious nodes can, in turn, create or
destroy direct edges with others until eventually altering the link prediction
between the target victim node and the attacker node. SAVAGE formulated the
problem that the attacker must solve as an optimization task, which trades off
between the attack’s success and the sparsity of malicious resources required.
Experiments conducted on real-world and synthetic datasets showed the
effectiveness and efficiency of our approach in attacking several GNN-based
link prediction models. Moreover, we showed that SAVAGE attacks can be
successfully transferred to disrupt other link prediction systems (not
necessarily GNN-based) under black-box setting. In future work, we plan to
extend our attack model with the ability to perturb node features.
Furthermore, our method must operate on dense adjacency matrices, somewhat
limiting its scalability. Thus, we will develop a variant of SAVAGE that can
work with sparse adjacency matrices. The design of possible defense mechanisms
to combat the attacks generated by SAVAGE is another interesting direction to
explore; we will also consider different downstream tasks as the target of the
attacks (e.g., node classification).

## References

  * Adamic and Adar (2003a) Adamic, L. A.; and Adar, E. 2003a.  Friends and neighbors on the Web.  _Social Networks_ , 25(3): 211–230.
  * Adamic and Adar (2003b) Adamic, L. A.; and Adar, E. 2003b.  Friends and neighbors on the web.  _Social networks_ , 25(3): 211–230.
  * Al Hasan et al. (2006) Al Hasan, M.; Chaoji, V.; Salem, S.; and Zaki, M. 2006.  Link prediction using supervised learning.  In _SDM06: workshop on link analysis, counter-terrorism and security_ , volume 30, 798–805.
  * Barabási and Albert (2010) Barabási, A.-L.; and Albert, R. 2010.  Emergence of Scaling in Random Networks.  _ArXiv preprint_ , abs/10.1126.
  * Brin and Page (1998) Brin, S.; and Page, L. 1998.  The anatomy of a large-scale hypertextual Web search engine.  _Computer Networks and ISDN Systems_ , 30(1): 107–117.  Proceedings of the Seventh International World Wide Web Conference.
  * Chen et al. (2020) Chen, J.; Lin, X.; Shi, Z.; and Liu, Y. 2020.  Link prediction adversarial attack via iterative gradient attack.  _IEEE Transactions on Computational Social Systems_ , 7(4): 1081–1094.
  * Dai et al. (2022) Dai, E.; Zhao, T.; Zhu, H.; Xu, J.; Guo, Z.; Liu, H.; Tang, J.; and Wang, S. 2022\.  A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability.  _ArXiv preprint_ , abs/2204.08570.
  * Dai, Zhu, and Luo (2022) Dai, J.; Zhu, W.; and Luo, X. 2022.  A Targeted Universal Attack on Graph Convolutional Network by Using Fake Nodes.  _Neural Processing Letters_ , 1–17.
  * Fey and Lenssen (2019) Fey, M.; and Lenssen, J. E. 2019.  Fast Graph Representation Learning with PyTorch Geometric.  _ArXiv preprint_ , abs/1903.02428.
  * Goodfellow, Shlens, and Szegedy (2015) Goodfellow, I. J.; Shlens, J.; and Szegedy, C. 2015.  Explaining and Harnessing Adversarial Examples.  In Bengio, Y.; and LeCun, Y., eds., _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_.
  * Grosse et al. (2017) Grosse, K.; Papernot, N.; Manoharan, P.; Backes, M.; and McDaniel, P. 2017.  Adversarial Examples for Malware Detection.  In Foley, S. N.; Gollmann, D.; and Snekkenes, E., eds., _Computer Security – ESORICS 2017_ , 62–79. Springer International Publishing.  ISBN 978-3-319-66399-9.
  * Jeh and Widom (2002) Jeh, G.; and Widom, J. 2002.  SimRank: A Measure of Structural-Context Similarity.  In _Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’02, 538––543. New York, NY, USA: Association for Computing Machinery.  ISBN 158113567X.
  * Katz (1953) Katz, L. 1953.  A new status index derived from sociometric analysis.  _Psychometrika_ , 18(1): 39–43.
  * Kipf and Welling (2017) Kipf, T. N.; and Welling, M. 2017.  Semi-Supervised Classification with Graph Convolutional Networks.  In _5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings_. OpenReview.net.
  * Kumar et al. (2020) Kumar, A.; Singh, S. S.; Singh, K.; and Biswas, B. 2020.  Link prediction techniques, applications, and performance: A survey.  _Physica A: Statistical Mechanics and its Applications_ , 553: 124289\.
  * Kunegis (2013) Kunegis, J. 2013.  Konect: the koblenz network collection.  In _Proceedings of the 22nd international conference on world wide web_ , 1343–1350.
  * Leskovec, Huttenlocher, and Kleinberg (2010a) Leskovec, J.; Huttenlocher, D. P.; and Kleinberg, J. M. 2010a.  Predicting positive and negative links in online social networks.  In Rappa, M.; Jones, P.; Freire, J.; and Chakrabarti, S., eds., _Proceedings of the 19th International Conference on World Wide Web, WWW 2010, Raleigh, North Carolina, USA, April 26-30, 2010_ , 641–650. ACM.
  * Leskovec, Huttenlocher, and Kleinberg (2010b) Leskovec, J.; Huttenlocher, D. P.; and Kleinberg, J. M. 2010b.  Signed networks in social media.  In Mynatt, E. D.; Schoner, D.; Fitzpatrick, G.; Hudson, S. E.; Edwards, W. K.; and Rodden, T., eds., _Proceedings of the 28th International Conference on Human Factors in Computing Systems, CHI 2010, Atlanta, Georgia, USA, April 10-15, 2010_ , 1361–1370. ACM.
  * Li et al. (2021) Li, B.; Xia, Y.; Xie, S.; Wu, L.; and Qin, T. 2021.  Distance-enhanced graph neural network for link prediction.  In _ICML 2021 Workshop on Computational Biology_.
  * Liben-Nowell and Kleinberg (2003) Liben-Nowell, D.; and Kleinberg, J. 2003.  The Link Prediction Problem for Social Networks.  In _Proceedings of the Twelfth International Conference on Information and Knowledge Management_ , CIKM ’03, 556––559. New York, NY, USA: Association for Computing Machinery.  ISBN 1581137230.
  * Lin, Ji, and Li (2020) Lin, W.; Ji, S.; and Li, B. 2020.  Adversarial attacks on link prediction algorithms based on graph neural networks.  In _Proceedings of the 15th ACM Asia Conference on Computer and Communications Security_ , 370–380.
  * Lü and Zhou (2011) Lü, L.; and Zhou, T. 2011.  Link prediction in complex networks: A survey.  _Physica A: statistical mechanics and its applications_ , 390(6): 1150–1170.
  * Lucic et al. (2022) Lucic, A.; Ter Hoeve, M. A.; Tolomei, G.; De Rijke, M.; and Silvestri, F. 2022.  Cf-gnnexplainer: Counterfactual explanations for graph neural networks.  In _International Conference on Artificial Intelligence and Statistics_ , 4499–4511. PMLR.
  * Martínez, Berzal, and Cubero (2016) Martínez, V.; Berzal, F.; and Cubero, J.-C. 2016.  A Survey of Link Prediction in Complex Networks.  _ACM Comput. Surv._ , 49(4).
  * McAuley and Leskovec (2012) McAuley, J. J.; and Leskovec, J. 2012.  Learning to Discover Social Circles in Ego Networks.  In Bartlett, P. L.; Pereira, F. C. N.; Burges, C. J. C.; Bottou, L.; and Weinberger, K. Q., eds., _Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012\. Proceedings of a meeting held December 3-6, 2012, Lake Tahoe, Nevada, United States_ , 548–556.
  * Newman (2001) Newman, M. E. 2001.  Clustering and preferential attachment in growing networks.  _Physical review E_ , 64(2): 025102.
  * Pitropakis et al. (2019) Pitropakis, N.; Panaousis, E.; Giannetsos, T.; Anastasiadis, E.; and Loukas, G. 2019\.  A taxonomy and survey of attacks against machine learning.  _Computer Science Review_ , 34: 100199.
  * Ren et al. (2020) Ren, K.; Zheng, T.; Qin, Z.; and Liu, X. 2020.  Adversarial Attacks and Defenses in Deep Learning.  _Engineering_ , 6(3): 346–360.
  * Srinivas, Subramanya, and Babu (2017) Srinivas, S.; Subramanya, A.; and Babu, R. V. 2017.  Training Sparse Neural Networks.  In _2017 IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPRW)_ , 455–462.
  * Šubelj and Bajec (2013) Šubelj, L.; and Bajec, M. 2013.  Model of complex networks based on citation dynamics.  In _Proceedings of the 22nd international conference on World Wide Web_ , 527–530.
  * Sun et al. (2018) Sun, L.; Dou, Y.; Yang, C.; Wang, J.; Yu, P. S.; He, L.; and Li, B. 2018.  Adversarial attack and defense on graph data: A survey.  _ArXiv preprint_ , abs/1812.10528.
  * Wang et al. (2020a) Wang, J.; Luo, M.; Suya, F.; Li, J.; Yang, Z.; and Zheng, Q. 2020a.  Scalable attack on graph data by injecting vicious nodes.  _Data Mining and Knowledge Discovery_ , 34(5): 1363–1389.
  * Wang et al. (2020b) Wang, K.; Shen, Z.; Huang, C.; Wu, C.-H.; Dong, Y.; and Kanakia, A. 2020b.  Microsoft academic graph: When experts are not enough.  _Quantitative Science Studies_ , 1(1): 396–413.
  * Wang et al. (2018) Wang, X.; Cheng, M.; Eaton, J.; Hsieh, C.-J.; and Wu, F. 2018.  Attack graph convolutional networks by adding fake nodes.  _ArXiv preprint_ , abs/1810.10751.
  * Wu et al. (2020) Wu, Z.; Pan, S.; Chen, F.; Long, G.; Zhang, C.; and Philip, S. Y. 2020.  A comprehensive survey on graph neural networks.  _IEEE transactions on neural networks and learning systems_ , 32(1): 4–24.
  * Zeng et al. (2020) Zeng, H.; Zhou, H.; Srivastava, A.; Kannan, R.; and Prasanna, V. 2020.  GraphSAINT: Graph Sampling Based Inductive Learning Method.  In _International Conference on Learning Representations_.
  * Zhang and Chen (2018) Zhang, M.; and Chen, Y. 2018.  Link Prediction Based on Graph Neural Networks.  In Bengio, S.; Wallach, H. M.; Larochelle, H.; Grauman, K.; Cesa-Bianchi, N.; and Garnett, R., eds., _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada_ , 5171–5181.
  * Zhou, Lü, and Zhang (2009) Zhou, T.; Lü, L.; and Zhang, Y.-C. 2009.  Predicting missing links via local information.  _The European Physical Journal B_ , 71(4): 623–630.
  * Zügner, Akbarnejad, and Günnemann (2018) Zügner, D.; Akbarnejad, A.; and Günnemann, S. 2018.  Adversarial Attacks on Neural Networks for Graph Data.  In Guo, Y.; and Farooq, F., eds., _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018_, 2847–2856. ACM.

##  Appendix A Datasets

#### Pruning

Given both the high number of nodes in the social network-based datasets
(Twitter and GPlus) and the high dimensionality of their feature spaces, we
decided to prune them. We started by reducing the noise in the Twitter
features by normalizing the textual versions to lowercase and removing
characters not allowed in the hashtag and mention as per Twitter official
guidelines.333https://help.twitter.com/en/managing-your-account/twitter-
username-rules#error Then, for Twitter, we removed features with less than 20
occurrences, and for GPlus, the ones with less than 10. After that, we pruned
users with less than 20 remaining features on Twitter and 30 for GPlus. We
report in Table 3 the pruning results.

#### Preprocessing

Considering the high-dimensionality of the majority of the dataset used and
their sparsity, we adopted a preprocessing to make them smaller and,
simultaneously, as denser as possible. In particular, we extracted the largest
connected components from all of them. Subsequently, if the extracted subgraph
had more than 10K nodes, we first sampled employing GraphSAINTSampler (Zeng et
al. 2020), then we retrieved the largest connected component again to ensure
the density of the sampled subgraph. We report in Table 4 the statistics of
the preprocessed dataset.

Table 3:  User and feature pruning results for each social network dataset. We also consider the shrink percentage between the starting value and the one after the pruning. |  | GPlus | Twitter
---|---|---|---
Features | Original | 15,602 | 155,033
Pruned | 2,001 | 11,034
Shrink | 88% | 93%
Users | Original | 107,613 | 81,306
Pruned | 7,008 | 7,520
Shrink | 93% | 91%
Table 4: We report the statistics of the datasets used. In particular, $N$ represents the number of nodes, $E$ represents the number of edges, $\bar{X}$ represents the mean between the in and the out degree, $\tilde{X}$ represents the median between the in and the out degree and $AC$ represents the average clustering. Dataset | $N$ | $E$ | $\bar{X}$ | $\tilde{X}$ |  $AC$
---|---|---|---|---|---
Twitter |  $7.50$K |  $725.20$K | $96.84$ | $28.50$ | $0.43$
Gplus |  $6.90$K |  $2.80$M | $403.20$ | $35.00$ | $0.28$
Citation2 |  $10.10$K |  $15.40$K | $1.52$ | $1.00$ | $0.07$
Arxiv |  $10.70$K |  $46.60$K | $4.36$ | $2.00$ | $0.13$
Cora |  $2.50$K |  $5.20$K | $2.10$ | $1.50$ | $0.13$
Wiki |  $7.00$K |  $103.70$K | $14.67$ | $2.00$ | $0.08$
Synthetic |  $5.50$K |  $54.70$K | $9.99$ | $10.00$ | $0.01$

##  Appendix B GNN Models

We train our link prediction system in a transductive setting, using $90\%$ of
existing edges as training set and the remaining $10\%$ as test set. We train
our models for $2000$ epochs with a learning rate $lr=0.001$. The performance
of our GNN-based link prediction models measured on the test set for each
dataset considered is reported in Table 5.

Table 5: We report Accuracy and AUROC scores obtained by our link prediction systems on the datasets used in our experiments. Given the high scores obtained, we are confident to attack a strong-enough prediction system. Dataset | Accuracy | AUROC
---|---|---
Twitter | $0.94$ | $0.94$
GPlus | $0.81$ | $0.81$
Citation2 | $0.97$ | $0.97$
Arxiv | $0.90$ | $0.89$
Cora | $0.82$ | $0.82$
Wiki | $0.78$ | $0.78$
Synthetic | $0.77$ | $0.77$

##  Appendix C Methods

We have reported results for different configurations of our framework. In
particular, our SAVAGE and SAVAGE-I configurations rely on a set of
hyperparameters: the penalty losses $\beta$ and $\gamma$. In Table 6 we report
the best hyperparameter setting. These hyperparameters were found through a
grid search in the range $[10^{-3},10]$.

Table 6:  Best hyperparameter settings for selected configuration and dataset. | SAVAGE | SAVAGE-I
---|---|---
Dataset | $\beta$ | $\gamma$ | $\beta$ | $\gamma$
Twitter | $0.80$ | $0.80$ | $0.80$ | $0.80$
GPlus | $0.80$ | $0.80$ | $0.80$ | $0.80$
Citation2 | $0.80$ | $0.80$ | $0.80$ | $0.80$
Arxiv | $0.03$ | $0.03$ | $0.03$ | $0.03$
Cora | $0.80$ | $0.80$ | $0.80$ | $0.80$
Wiki | $0.10$ | $0.10$ | $0.01$ | $0.01$
Synthetic | $0.10$ | $0.10$ | $0.01$ | $0.01$

##  Appendix D Ablations

###  D.1 Initialization

As hinted several times in the paper, we are solving a highly non-convex
optimization problem. For this reason, the initialization of the perturbation
matrix $P$ can be considered crucial, as it reflects both the prior
information we inject into the model and the model’s results itself. For this
reason, we run an ablation experiment to show how different kinds of
initializations lead to different results.

We test four possible initializations for the perturbation matrix: Random, All
Zeros + $\epsilon$, all Ones - $\epsilon$, and All negative ones + $\epsilon$;
where $\epsilon$ is a small random positive number ($<0.3$). We test these
options by running experiments for $20$ different pairs randomly sampled from
the Synthetic dataset.

We report results in Table 7. We indicate the All negative ones option with a
minus as footer (Ones_).

We may observe that Random exhibits the best trade-off between the attack
power and the number of resources used.

Table 7:  Results for different initialization of the perturbation matrix $P$. The Random initialization offers the best trade off between resources used and power of the attack. Method | AR | AN | AP | KL
---|---|---|---|---
Random | $0.90$ | $14.00$ | $0.89$ | $0.01$
Zeros | $0.75$ | $11.50$ | $0.74$ | $0.01$
Ones | $0.45$ | $7.20$ | $0.50$ | $0.01$
Ones_ | $0.55$ | $22.05$ | $0.58$ | $0.00$

###  D.2 Penalty losses

SAVAGE relies on two penalty losses, $\beta$ and $\gamma$, to effectively
sparsify the resources used to carry out the attack. We hereby perform a
sensitivity analysis to quantify the impact of these losses on the model
results. In particular, we sample $20$ pairs at random from the Synthetic
dataset and run our method on them.

#### L-Dist

As explained in the relevant section of the main body, $\beta$ regulates the
effect of $\ell_{\text{dist}}$, that is, the penalty discouraging
$\tilde{h}_{s;P}$ from being too far off from $h_{s}$. In Figure 3 we report
our finding. On the horizontal axis, we indicate the penalty used, while on
the vertical axis, the amount of resources used. As we can see, increasing
$\beta$ corresponds to a reduction in the resources used. Furthermore, we
notice that the behavior of this penalty loss is optimal, as it features a
nice monotonic decrease in the amount of resources used. While not shown here
for visualization purposes, the relationships remain pretty much constant
outside the range considered.

$0$$2$$4$$6$$8$$10$$0$$5$$10$$15$$\beta$Nodes UsedAblation Study on $\beta$
Figure 3: Amount of resources used at the variying of the penalty loss
$\beta$. It can be noticed how the decrease in the resources used produces a
well behaved monotonic curve.

#### L-new

As explained in the relevant section of the main body, $\gamma$ regulates the
effect of $\ell_{\text{new}}$, that is, the penalty directly discouraging the
proliferation of vicious nodes injected into the original graph network. We
report results in Figure 4. We indicate the level of the penalty $\gamma$ used
on the horizontal axis, with the amount of resources used on the vertical axis
(on the log scale). Once again, even though the intrinsic discreteness of the
problem, we show how our formulation features a nice, well-behaved decrease in
resources used along with the increase in the penalty loss, with an almost-
monotonic curve. While not shown here for visualization purposes, the
relationships remain pretty much constant outside the range considered.

$0$$2$$4$$6$$8$$10$$-2$$0$$2$$4$$\gamma$log(Nodes Used)Ablation Study on
$\gamma$ Figure 4: Amount of resources used (log-scale) at the variying of the
penalty loss $\gamma$. Again, it can be noticed how the decrease in the
resources used produces a well behaved, almost monotonic, curve.

###  D.3 Feature Matrix

As stated in the main body of this paper, SAVAGE does not focus on the
creation of the features for the vicious nodes injected into the original
graphs, focusing instead on their topology.

Table 8: Results under different assumptions for creating the vicious nodes feature matrix. While not optimizing for this, SAVAGE is robust under different settings and maintains strong results. Method | AR | AN | AP | KL
---|---|---|---|---
Existent | $0.90$ | $13.90$ | $0.90$ | $0.01$
Random | $1.00$ | $16.70$ | $0.98$ | $0.01$
Ones | $0.75$ | $42.50$ | $0.75$ | $0.01$
Zeros | $0.95$ | $14.10$ | $0.91$ | $0.01$
Mean | $0.91$ | $14.10$ | $0.91$ | $0.01$
Median | $0.95$ | $14.00$ | $0.91$ | $0.01$

In particular, we do not optimize for it, leaving it as a feature work.
However, we hereby claim that SAVAGE is robust under different assumptions for
the creation of such a matrix. For this experiment, once again, we sampled
$20$ pairs randomly from the Synthetic dataset and ran our method on them.
This time, however, we consider six different settings for creating the
feature matrix. The first setting, used for the main experiment, is to
randomly sample features from existing nodes and add a slight noise. Three
settings consist in initializing the feature matrix $X$ with zeros, ones, and
at random, respectively; we apply some noise $\epsilon$ here as well. Finally,
we take the mean and the median of the feature matrix in two cases, still
adding noise to it. Results are reported in Table 8. These results show that
we maintain strong results across different initializations. In particular, we
can notice how the Random, Zeros, and Median methods produce the strongest
attack power, while Ones produces the lowest attack power while using the most
resources as well.