# Adversarial Robustness of
Graph-based Anomaly Detection

Yulin Zhu, Yuni Lai, Kaifa Zhao, Xiapu Luo, Mingquan Yuan, Jian Ren, Kai Zhou

###### Abstract

Graph-based anomaly detection is becoming prevalent due to the powerful
representation abilities of graphs as well as recent advances in graph mining
techniques. These GAD tools, however, expose a new attacking surface,
ironically due to their unique advantage of being able to exploit the
relations among data. That is, attackers now can manipulate those relations
(i.e., the structure of the graph) to allow target nodes to evade detection or
degenerate the classification performance of the detection. In this paper, we
exploit this vulnerability by designing the structural poisoning attacks to a
FeXtra-based GAD system termed $\mathsf{OddBall}$ as well as the black box
attacks against GCN-based GAD systems by attacking the imbalanced lienarized
GCN ($\mathsf{LGCN}$). Specifically, we formulate the attack against
$\mathsf{OddBall}$ and $\mathsf{LGCN}$ as a one-level optimization problem by
incorporating different regression techniques, where the key technical
challenge is to efficiently solve the problem in a discrete domain. We propose
a novel attack method termed $\mathsf{BinarizedAttack}$ based on gradient
descent. Comparing to prior arts, $\mathsf{BinarizedAttack}$ can better use
the gradient information, making it particularly suitable for solving discrete
optimization problems, thus opening the door to studying a new type of attack
against security analytic tools that rely on graph data.

###### Index Terms:

Graph-base anomaly detection, Graph learning and mining, Data poisoning
attack, Adversarial machine learning, Discrete optimization

##  1 Introduction

Anomaly detection is a long-standing task in the field of data science and
engineering with the goal to spot unusual patterns from the massive amount of
data. Recently, due to the powerful representation abilities of graphs as well
as the advances in graph mining and learning techniques, Graph-based Anomaly
Detection (GAD) is becoming prevalent across a wide spectrum of domains.
Various GAD systems are proposed and deployed as an indispensable security
component in detecting, for example, fake accounts in social networks [1],
fraudulent transactions in the financial industry [2], and Botnets in
communication networks [3].

Those GAD systems, however, expose a new attacking surface, ironically due to
their unique advantage of being able to exploit the connections among data
(i.e., edges in graphs). As a motivative example, consider the problem of
misinformation diffusion in social networks, where an attacker aims to
identify a set of nodes as the sources (called seeds) to diffuse
misinformation (e.g., fake news or hate speeches) through social media
platforms. To maximize the diffusion range, the attacker can employ some
influence maximization [4] algorithms to identify those most promising seeds,
which however are prone to be labeled as anomalous by GAD systems. Meanwhile,
the attacker can proactively alter the social ties (e.g., friend/unfriend with
other users) of those seeds so as to prevent them from being detected. That
is, attackers now can evade GAD systems via manipulating the structure of the
graph; we term such attacks as structural attacks. In Fig. 1, we demonstrate
how our proposed structural attacks can help those seeds to evade a popular
GAD system.

(a) Detection of seeds

(b) Evade detection

Figure 1: (a) The attacker uses four strategies (CELF, Greedy, Degree and
Betweenness centralities) to select seeds. However, these seeds can all be
detected using a GAD algorithm $\mathsf{OddBall}$ among the top-k (in terms of
anomaly score AScore) nodes. (b) The attacker can use our proposed algorithm
$\mathsf{BinarizedAttack}$ to significantly decrease the AScore and ranking of
those target seeds, thus evading the detection of $\mathsf{OddBall}$.

The previous example shows that there is an urgent need to investigate the
adversarial robustness of current GAD systems – how robust could those GAD
systems be under carefully designed attacks? To this end, we initiate the
study of structural attacks against GAD systems, answering to what extend an
attacker can evade the detection of prevalent GAD systems by solely
manipulating graph structures. Studying such structural attacks has
significant practical implications. Previous research on evading detection
tools (e.g., PDF/Android malware detection [5]) primarily operate in a feature
space, where attackers manipulate the extracted feature vectors. Consequently,
it is known that the manipulated feature vectors are hard to be mapped back to
real entities (e.g., PDF/Android software), affecting the effectiveness of the
actual attacks. In contrast, altering the structure of a graph always
corresponds to manipulating actual connections among entities, making
structural attacks highly realizable in practice. Besides, there are scenarios
where an attacker could have control of the whole graph structure, allowing
the global optimization of the attacks. A representative example is the
Command & Control center in Botnets [3], which can coordinate the
communication among Bots, i.e., globally optimizing the structure of the
communication graph, to evade Botnets detection tools. These practical threats
imposed by structural attacks motivate us to systematically study the
attacker’s ability to evade GAD.

In this paper, we instantiate our study by attacking two families of widely
used GAD systems. The first family is termed as FeXtra-Based GAD systems.
Specifically, these systems (e.g., $\mathsf{OddBall}$ [6]) extract structural
features of each node in the graph, then build regression models over those
features, and finally compute the node anomaly scores. We focus on FeXtra-
Based GAD systems, particularly $\mathsf{OddBall}$, mainly due to the
following reasons. First, $\mathsf{OddBall}$ stands for a class of simple
while effective approaches that require much less information from data, and
thus are widely adopted in practice. Second, the hand-crafted features in
$\mathsf{OddBall}$ are based on domain-specific knowledge, which well captures
the endogenous structural anomalous in the graph. In comparison, the second
family relies on the ability of Graph Convolutional Networks (GCNs [7]) as the
essential component to automatically learn the anomalous patterns, thus termed
as GCN-based GAD systems. Since GCNs are demonstrated to achieve state-of-the-
art performances across various graph-related tasks, we also choose them as
our attack targets.

However, attacking GAD systems faces several challenges. First, GAD systems
naturally feature an unsupervised/semi-supervised setting, where all nodes
reside in a single graph. Attacking GAD thus is poisoning the data from which
the detection model is built, which is in strong contrast to those attacks
that are manipulating the inputs to a fixed trained model. These poisoning
attacks are mathematically modeled as bi-level optimization problems, which
are notoriously hard to solve in the literature. Second, structural attacks
operate in a discrete domain, resulting in a strategy space exponential in the
graph size. Furthermore, the discrete nature makes it hard to adopt gradient-
descent-based attack methods [8, 9], as the attacker now needs to make binary
decisions on deleting or keeping the connections in the graph. Indeed as we
will show later, trivially utilizing the gradient information may result in
non-effective attacks.

To tackle these challenges, we propose $\mathsf{BinarizedAttack}$, which is
inspired by Binarized Neural Networks (BNN) [10] designed for model
compression. Specifically, BNN transforms the real-valued model weights to
discrete values $+1$/$-1$ to reduce the model size. To find the discrete
optimal weights, BNN uses a continuous version of the weights when computing
the gradients in the backward propagation. In light of this,
$\mathsf{BinarizedAttack}$ associates a discrete as well as a continuous
decision variable for each edge/non-edge in the graph and uses a novel
gradient-descent-based approach to solve the resulting discrete optimization
problem. Specifically, in the forward pass, the discrete decision variables
are used to evaluate the objective function. In the backward pass, the
continuous decision variables are firstly updated based on the fractional
gradients, and the discrete ones are then updated accordingly. In essence,
$\mathsf{BinarizedAttack}$ could better use the gradient information to guide
the search for the optimal graph structure. Comprehensive experiments
demonstrate that $\mathsf{BinarizedAttack}$ can effectively solve the discrete
optimization problem and outperforms other gradient-descent-based approaches.

In summary, we identify and initiate the study of a new vulnerability of
graph-based anomaly detection systems. Our results show that by slightly
modifying the graph structure, attackers can successfully evade two families
of widely used GAD systems. In particular, we propose a novel gradient-
descent-based approach $\mathsf{BinarizedAttack}$ that can effectively solve
discrete optimization problems, outperforming existing methods. The research
opens the door to studying this new type of attacks against graph-based
learning systems.

##  2 Related Works

###  2.1 Graph-based anomaly detection

The essential task of Graph-based Anomaly Detection (GAD) is to identify
anomalous patterns from graph data. It becomes prevalent due to the powerful
representation ability of graphs as well as the advances in graph mining and
learning techniques. Our focus is anomaly detection on static graphs [11],
where the graph structure and node features are fixed overtime. Representative
GAD can be roughly classified into four classes. Specifically, feature-based
methods [6] extract hand-crafted features from the graph and use typical
machine learning approaches to analyze those features. Proximity-based methods
[12] exploit the graph structure to measure the distances among nodes and
anomalous nodes are assumed to have larger distances to other nodes.
Community-based methods [13] employ community detection approaches to cluster
normal nodes. Relational-learning-based methods [14] design graphical models
to capture the relations among nodes and cast anomaly detection as a
classification problem. Importantly, all these methods rely on the graph
structure as an essential input. More recently, there are methods based on the
powerful graph neural network to capture anomalous features in the relational
data [15, 16, 17, 18], the propagation of the convolutional layer naturally
can distinguish the anomalous relation information of the anomaly nodes among
the benign nodes.

###  2.2 Adversarial graph analysis

Our work belongs to a long line of research that studies the adversarial
robustness of various graph analysis tasks, such as node classification [8, 9,
19], link prediction [20, 21], community detection [22], etc. All related
works on attacking graph analytic tools ([8], [9], [19], [20], [21], [22])
formulate the structural attacks as discrete optimization problems. Those
approaches for solving the optimization problems diverge into two categories:
task-specific and general. The task-specific approaches heavily rely on the
concrete scenarios of the optimization problem, which of course depends on the
target model. For example, [20] studies the sub-modularity of the objective
functions and accordingly proposes an approximation algorithm with nice
theoretical guarantees. In contrast, the general approach is to use the
gradient-descent method to optimize the objective iteratively. The key to this
approach lies in properly using the gradient information to guide the
optimization process in the discrete process. The most notable representative
is a greedy approach wherein each iteration the edge corresponding to the
largest gradient is selected (thus greedy) to alter. For example, [8]
generates the adversarial perturbations on both the node features and graph
structure by maximizing the classification margin of the target nodes and make
the decision by greedy search; [9] utilizes the meta-gradient on the bi-level
optimization problem of the structural poisoning attack on node
classification. Our proposed $\mathsf{BinarizedAttack}$ differs in the way of
utilizing the gradient information by using two sets of discrete and
continuous variables in optimization, which will lead to more precise updates
in the discrete space. This idea of using two sets of variables is loosely
connected to binary neural networks [10], which feature binary network
parameters with a rather different design goal of making the size of the
neural network compact. In fact, we adapted the greedy approach to our case,
resulting in a strong baseline attack method termed $\mathsf{GradMaxSearch}$.
We analyzed the advantages of $\mathsf{BinarizedAttack}$ compared to
$\mathsf{GradMaxSearch}$ in Section 5.2 and our comprehensive experiments also
demonstrated that $\mathsf{BinarizedAttack}$ outperforms
$\mathsf{GradMaxSearch}$ on all datasets.

##  3 Background on GAD Systems

In this section, we provide the necessary background on the two families of
GAD systems – one based on feature extractions and the other based on GNNs.

###  3.1 FeXtra-Based GAD Systems

We introduce $\mathsf{OddBall}$ [6] as one of the representative Feature
eXtraction (FeXtra for short) based GAD systems that we aim to attack. At a
high level, $\mathsf{OddBall}$ extracts some carefully crafted structural
features for each node in the graph, and computes an anomaly score for each
node based on those features, where a larger score indicates that the node is
more likely to be anomalous.

To formalize, we denote a graph as $\mathcal{G}=(V,E)$, where $V$ denotes a
set of $n$ nodes and $E$ represents the edges. We consider a simple unweighted
graph with the adjacency matrix $\mathbf{A}\in\\{0,1\\}^{n\times n}$.
$\mathsf{OddBall}$ focuses on the local structural information of the nodes
for anomaly detection. Specifically, for a node $v_{i}\in V$,
$\mathsf{OddBall}$ examines an Egonet $\mathsf{ego}_{i}$ centered at $v_{i}$,
where $\mathsf{ego}_{i}$ is the reduced sub-graph contains $v_{i}$ and its
one-hop neighbors. An important finding of $\mathsf{OddBall}$ is that the
Egonets for anomalous nodes tend to appear in either a near-clique or near-
star structure (as shown in Fig. 2(a)). To detect such anomalous structures,
$\mathsf{OddBall}$ identifies two critical features $E_{i}$ and $N_{i}$ among
others from the Egonet $\mathsf{ego}_{i}$, where $E_{i}$ and $N_{i}$ denote
the number of edges and nodes in $\mathsf{ego}_{i}$, respectively. It was
observed that $E_{i}$ and $N_{i}$ follow an Egonet Density Power Law [6]:
$E_{i}\propto N_{i}^{\alpha},1\leq\alpha\leq 2$. The nodes that significantly
deviate from this law are thus flagged as anomalous.

(a) Anomalous patterns

(b) Feature distribution

Figure 2: (a) The near-clique (left) and near-star (right) structural
patterns. (b) The distribution of node features and the regression line.

$\mathsf{OddBall}$ uses a regression-based approach to quantify the deviation.
Specifically, let vectors $\mathbf{E}=(E_{1},E_{2},\cdots,E_{n})$ and
$\mathbf{N}=(N_{1},N_{2},\cdots,N_{n})$ be the collected features of all
nodes. Based on the power law observation, one can use the following linear
model to fit the pair of features $(E_{i},N_{i})$ for a node $i$:

$\ln E_{i}=\beta_{0}+\beta_{1}\ln N_{i}+\epsilon.$ (1)

In the above equation, the model parameters $\beta_{0}$ and $\beta_{1}$ are
given by the Ordinary Least Square (OLS) [23] estimation:

$[\beta_{0},\beta_{1}]=([\mathbf{1},\ln\mathbf{N}]^{T}[\mathbf{1},\ln\mathbf{N}])^{-1}[\textbf{1},\ln\mathbf{N}]^{T}\ln\mathbf{E},$
(2)

where $\mathbf{1}$ is an $n$-dimensional vector of all $1$’s.

The anomaly score $S_{i}(\mathbf{A})$ for the node $v_{i}$ is then computed as

$S_{i}(\mathbf{A})=\frac{\max(E_{i},e^{\beta_{0}}N_{i}^{\beta_{1}})}{\min(E_{i},e^{\beta_{0}}N_{i}^{\beta_{1}})}\ln(|E_{i}-e^{\beta_{0}}N_{i}^{\beta_{1}}|+1).$
(3)

Note that we made the dependency of $S_{i}(\mathbf{A})$ on $\mathbf{A}$
explicit as all of $\beta_{0},\beta_{1},E_{i},N_{i}$ rely on $\mathbf{A}$. As
illustrated in Fig. 2(b), the anomaly score $S_{i}(\mathbf{A})$ intuitively
measures the distance between the point $(N_{i},E_{i})$ and the regression
line along the vertical axis. Finally, nodes with high anomaly scores (e.g.,
by ranking) are determined as anomalous by $\mathsf{OddBall}$.

###  3.2 GCN-Based GAD Systems

With the advances of graph neural networks, an increasing number of GAD
systems are using GCN [7] as the backbone for automatically learning useful
anomalous patterns. In essence, anomaly detection is cast as a supervised
classification process where the labels of a portion of nodes are provided for
training. Specifically, GCN-based methods will take as input an attributed
graph where nodes are associative with feature vectors, and generate node
embeddings through several convolutional layers as follows:

$\displaystyle\mathbf{H}^{t+1}=\sigma(\tilde{\mathbf{A}}\mathbf{H}^{t}\mathbf{W}),\text{where
}$ (4a)
$\displaystyle\tilde{\mathbf{A}}=\text{diag}(\sum_{i=1}^{n}\mathbf{A}_{i})^{-\frac{1}{2}}(\mathbf{A+I})\text{diag}(\sum_{i=1}^{n}\mathbf{A}_{i})^{-\frac{1}{2}}\text{
and }$ (4b)
$\displaystyle\mathbf{H}^{0}=\sigma(\tilde{\mathbf{A}}\mathbf{X}\mathbf{W}).$
(4c)

In the above, $\mathbf{A}$ and $\mathbf{X}$ are the adjacency matrix and
feature matrix, respectively; $\mathbf{W}$ summarizes the learned model
parameters; $\mathbf{H}^{i}$ are the learned embeddings through the layers.
Finally, the embeddings are fed into a fully connected layer for
classification. The specific methods in this family integrate some minor
modifications into this framework to adapt to the various application
scenarios that they are designed for. In the following, we introduce six
typical GCN-based GAD systems and highlight their differences:

  * $\bullet$

GCN-reweight [7]. This is the $\mathsf{GCN}$ model with class-specific loss
weight to mitigate the imbalance problem. It assigns higher weight loss for
the minority class.

  * $\bullet$

GAT-reweight [24]. This is the $\mathsf{GCN}$ model augmented with the graph
attention mechanism to automatically distinguish the contributions from
different neighbors in the aggregation phase. Similar to the GCN-reweight, it
assigns higher weight loss for the minority class.

  * $\bullet$

FdGars [15]. It utilizes $\mathsf{GCN}$ for fraudulent detection in the online
APP review system to distinguish the malicious users out of benign users.

  * $\bullet$

GEM [16]. It is the first heterogeneous graph neural network model to detect
anomalous accounts at Alipay. It also augments the attention mechanism to
control the contributions from different nodes, and utilizes EM algorithm to
iteratively update the node embeddings and model parameters.

  * $\bullet$

Player2vec [17]. It is specially designed to detect the cybercriminals in the
e-commercial system by adopting $\mathsf{GCN}$ augmented with the attention
mechanism to automatically capture the anomalous behaviors in the environment.

  * $\bullet$

GraphSMOTE [18]. GraphSMOTE adopts synthetic minority oversampling techniques
(SMOTE) to generate an augmented graph to mitigate the class imbalance problem
in the bot detection field by using the synthetic node generator and edge
generator to interpolate new synthetic nodes and edges for the minority class.
Then the $\mathsf{GCN}$ classifier is implemented on the augmented graphs for
imbalanced node classification.

##  4 Formulation of Attacks

###  4.1 Threat Model

We consider a system consisting of three parties: a defender, an attacker, and
the outside environment, the interplay among which is illustrated in Fig. 3.
Specifically, a defender deploys a GAD system to detect anomalous nodes in an
existing network. In practice, the network is not readily available; instead,
the defender will need to construct the network via data collection. We model
data collections as a querying process where the defender sends queries
consisting of pairs of nodes $(u,v)$ to the environment, which responds with
the existence of the relation between $u$ and $v$ (i.e., whether there is an
edge between $u$ and $v$). Then, based on the query results the defender can
construct an observed network. This querying process models real-world
scenarios such as taking surveys on friendships, conducting field experiments
to measure the communication channels, etc.

Figure 3: Interplay among defender, attacker and environment.

An attacker, sitting between the defender and the outside environment, can
tamper with the above data collection procedure by modifying the query results
sent from the environment. For example, as shown in Fig. 3, the defender makes
a query “Is there a relation between $C$ and $D$?” to the environment; an
attacker can change the query result “$\\{C,D\\}=0$” (non-existence) to
“$\\{C,D\\}=1$” (existence), which is obtained by the defender. Consequently,
the attacker is inserting an edge in the network constructed by the defender.
That is, by modifying the query results, the attacker is equivalently
manipulating the network topology, resulting in structural attacks. We state
the attacker’s goal, knowledge, and capability as follows.

  * $\bullet$

Attacker’s Goal. For attacking unsupervised learning approach like
$\mathsf{OddBall}$, we assume that the attacker has a set of target nodes
within the network, which are risky nodes that have relatively high anomaly
scores initially. The attacker’s goal is thus to enable these target nodes to
evade the detection. For attacking supervised learning methods such as GCN,
the attacker’s goal is to minimize the overall classification accuracy of the
GAD systems.

  * $\bullet$

Attacker’s Knowledge We assume a worst-case scenario where the attacker has
full knowledge of the network structure. That is, the attacker knows all the
queries as well as the results to all those queries. Regarding the deployed
GAD systems, we consider different cases where the attacker may or may not
know the exact model in deployment.

  * $\bullet$

Attacker’s Capability. Again, we consider a worst-case scenario where the
attacker can modify the query results at her choice. That is the attacker has
control of the global structure of the graph and is able to add/delete edges
from the graph. To further constrain the attacker’s ability, we assume that
the attacker can add/delete up to $B$ edges.

###  4.2 Problem Formulation

In this section, we first universally formulate the structural poisoning
attacks against various GAD systems as bi-level discrete optimization
problems. Then, we instantiate the attack problems against $\mathsf{OddBall}$
and GCN-based methods, respectively, based on their unique characteristics.

We use
$\mathcal{G}_{0}=\\{\mathbf{V}_{0},\mathbf{E}_{0},\mathbf{X}_{0},\mathbf{Y}_{0}\\}$
to represent the ground-truth graph in the environment, where $\mathbf{Y}_{0}$
are the binary (anomalous or not) labels of the nodes. In particular,
$\mathbf{X}_{0}\in\mathbb{R}^{n\times p}$ denotes the attribute matrix for the
nodes, where each node has an attribute vector of dimension $p$. When the node
attributes are not available, we set $\mathbf{X}_{0}=\emptyset$. In structural
attacks, the attacker will manipulate the graph structure in the data
collection phase, resulting in a manipulated graph
$\mathcal{G}=\\{\mathbf{V}_{0},\mathbf{E},\mathbf{X}_{0},\mathbf{Y}_{0}\\}$
observed by the defender. We note that only the graph structure
$\mathbf{E}_{0}$ will be modified to $\mathbf{E}$. We use $\mathbf{A}_{0}$ and
$\mathbf{A}$ to denote the adjacency matrices of $\mathcal{G}_{0}$ and
$\mathcal{G}$, respectively. Then the structural poisoning attacks against the
GAD systems can be formulated as:

$\displaystyle\mathbf{A}^{*}=$
$\displaystyle\operatorname*{arg\,min}_{\mathbf{A}}\mathcal{L}_{atk}(\mathbf{A},\mathbf{X},\theta^{*},\mathbf{Y}),$
(5a) s.t.
$\displaystyle\theta^{*}=\mathsf{Regression}(\mathbf{A},\mathbf{X},\theta,\mathbf{Y}),$
(5b) $\displaystyle\frac{1}{2}||\mathbf{A}_{0}-\mathbf{A}||_{1}\leq
B,\quad\mathbf{A}\in\\{0,1\\}^{n\times n}.$ (5c)

Here, in (5a) the loss function $\mathcal{L}_{atk}(\cdot)$ quantifies the
attacker’s malicious goal of evading detection. In (5b), we use
$\mathsf{Regression}(\cdot)$ to denote the training process of a GAD system,
where the output is the optimal model parameter $\theta^{*}$ by specially
designed regression methods. (5c) specifies the budget constraint on the
attacker’s power. We emphasize that we solve the complex bi-level optimization
problem where whenever one tries to optimize graph structure $\mathbf{A}$, the
optimal model parameter $\theta^{*}$ would change according to a complex
training process to the one-level case by finding an appropriate point
estimation $\theta^{*}$ for different scenarios.

####  4.2.1 Attacking FeXtra-Based GAD Systems

We now formulate the attacks against FeXtra-Based GAD systems with
$\mathsf{OddBall}$ as an instantiation. We assume that the attacker has a set
of target nodes $\mathcal{T}\subset V_{0}$, and her goal is to reduce the
probabilities that the nodes in $\mathcal{T}$ are detected as anomalous. To
this end, the attacker is allowed to add or delete at most $B$ edges in the
graph $\mathcal{G}_{0}$ with the goal of minimizing the anomaly scores of the
target nodes in $\mathcal{T}$. In our formulation, we consider the weighted
sum of scores, i.e.,
$S_{\mathcal{T}}(\mathbf{A})=\sum_{i:v_{i}\in\mathcal{T}}\kappa_{i}S_{i}(\mathbf{A})=\sum_{i:v_{i}\in\mathcal{T}}\kappa_{i}\frac{\max(E_{i},e^{\beta_{0}^{*}}N_{i}^{\beta_{1}^{*}})}{\min(E_{i},e^{\beta_{0}^{*}}N_{i}^{\beta_{1}^{*}})}\ln(|E_{i}-e^{\beta_{0}^{*}}N_{i}^{\beta_{1}^{*}}|+1)$,
where $S_{i}(\mathbf{A})$ denotes the anomaly score of node $v_{i}$ and
$(\beta_{0}^{*},\beta_{1}^{*})=\theta^{*}$ are the optimal parameters of the
regression model. For simplicity, in this paper, we consider the equal weight
case, i.e., $\forall i,\kappa_{i}=1$; however, our methods can be easily
extended to the case with unequal weights. Then the attack can be formulated
as the following optimization problem:

$\displaystyle\mathbf{A}^{*}=$
$\displaystyle\operatorname*{arg\,min}_{\mathbf{A}}S_{\mathcal{T}}(\mathbf{A}),$
(6a) s.t.
$\displaystyle\beta_{0}^{*},\beta_{1}^{*}=\mathsf{Train}(\mathbf{A}),$ (6b)
$\displaystyle\frac{1}{2}||\mathbf{A}_{0}-\mathbf{A}||_{1}\leq
B,\quad\mathbf{A}\in\\{0,1\\}^{n\times n}.$ (6c)

To solve the optimization problem (6), we re-formulate it from several
aspects. First, we note that the anomaly score $S_{i}(\mathbf{A})$ for node
$v_{i}$ is a normalized distance to the regression line. To reduce the non-
linearity and ease optimization, we omit the normalization term and use a
proxy
$\tilde{S}_{i}(\mathbf{A})=\ln(|E_{i}-e^{\beta_{0}^{*}}N_{i}^{\beta_{1}^{*}}|+1)$
to approximate $S_{i}(\mathbf{A})$. Consequently, we will use an objective
function
$\tilde{S}_{\mathcal{T}}(\mathbf{A})=\sum_{i:v_{i}\in\mathcal{T}}(E_{i}-e^{\beta_{0}^{*}}N_{i}^{\beta_{1}^{*}})^{2}$
acting as the surrogate of $S_{\mathcal{T}}(\mathbf{A})$ in the optimization
process. We emphasize that $\tilde{S}_{\mathcal{T}}(\mathbf{A})$ is only used
in the optimization process and we use the true anomaly scores
$S_{\mathcal{T}}(\mathbf{A})$ for evaluation. Second, $\mathsf{OddBall}$ uses
OLS point estimation to learn the model parameters $\beta_{0}^{*}$ and
$\beta_{1}^{*}$, which have closed-form solutions (Eqn. (2)). This allows us
to directly substitute $\beta_{0}^{*}$ and $\beta_{1}^{*}$ with functions of
$\mathbf{A}$. At last, we can explicitly write the features $N_{i}$ and
$E_{i}$ as $N_{i}=\sum_{j=1}^{n}\mathbf{A}_{ij}$,
$E_{i}=N_{i}+\frac{1}{2}\mathbf{A}_{ii}^{3}.$ Finally, we can re-formulate the
attack problem as:

$\displaystyle\mathbf{A}^{*}=\operatorname*{arg\,min}_{\mathbf{A}}\
\tilde{S}_{\mathcal{T}}(\mathbf{A})$ (7a)
$\displaystyle=\operatorname*{arg\,min}_{\mathbf{A}}\sum_{i:i\in\mathcal{T}}(E_{i}-e^{(1,\ln
N_{i})^{T}([\mathbf{1},\ln\mathbf{N}]^{T}[\mathbf{1},\ln\mathbf{N}])^{-1}[\textbf{1},\ln\mathbf{N}]^{T}\ln\mathbf{E}})^{2},$
$\displaystyle\text{s.t.}\quad N_{i}=\sum_{j=1}^{n}\mathbf{A}_{ij},\quad
E_{i}=N_{i}+\frac{1}{2}\mathbf{A}_{ii}^{3};$ (7b)
$\displaystyle\quad\quad\frac{1}{2}||\mathbf{A}_{0}-\mathbf{A}||_{1}\leq
B,\quad\mathbf{A}\in\\{0,1\\}^{n\times n}.$ (7c)

Solving the above one-level discrete optimization problem leads to the optimal
structural poisoning attacks.

####  4.2.2 Attacking GCN-based GAD Systems

We now formulate the structural poisoning attacks against GCN-based GAD
Systems. One challenge is that these GAD systems have their unique
characteristics, meaning that designing specific attacks for each system would
be troublesome. In addition, GCN-based systems involve sophisticated training
processes, imposing extra challenges to solving the attack optimization
problem. To address these challenges, we propose to construct a simplified GCN
model termed $\mathsf{LGCN}$ as a surrogate model, which represents the common
graph convolutional process shared by all those GCN-based GAD systems. Thus,
by attacking this surrogate $\mathsf{LGCN}$ model, we can generalize the
attacks to all GCN-based GAD systems. In addition, a nice feature of
$\mathsf{LGCN}$ is that we can use close-form (Ridge weighted least square
estimation [25, 26]) functions to approximate its training process, which will
significantly reduce the complexity of solving the attack optimization problem
by transforming the complex bi-level optimization problem to one-level
version.

Referring to [8], we construct the $\mathsf{LGCN}$ model by replacing the
activation function (Like $\mathsf{ReLU}$ [27]) of the convolutional layer (4)
with the linear activation function. In this paper, we consider a two-layered
$\mathsf{LGCN}$:

$\displaystyle\tilde{\mathbf{A}}=\text{diag}(\sum_{i=1}^{n}\mathbf{A}_{i})^{-\frac{1}{2}}(\mathbf{A+I})\text{diag}(\sum_{i=1}^{n}\mathbf{A}_{i})^{-\frac{1}{2}},$
(8a)
$\displaystyle\mathbf{Z}=\text{sigmoid}(\tilde{\mathbf{A}}\tilde{\mathbf{A}}\mathbf{X}\mathbf{W}^{1}\mathbf{W}^{2})=\text{sigmoid}(\tilde{\mathbf{A}}^{2}\mathbf{X}\mathbf{W}),$
(8b)

here $\mathbf{W}^{1}$ and $\mathbf{W}^{2}$ represent the weights for the first
and second $\mathsf{GCN}$ layer. We use sigmoid instead of softmax for sake of
transferring the nonconvex deep learning model to a convex logistic
regression. The corresponding reweighting binary cross-entropy loss is defined
as:

$\mathcal{L}_{\text{R-BCE}}=-\sum_{i=1}^{n}(\omega
y^{i}\log(\mathbf{Z}_{i})+(1-y^{i})\log(1-\mathbf{Z}_{i})),$ (9)

where $\omega$ is the ratio of positive samples number to negative samples
number. However, the optimal $\mathbf{W}^{*}$ can only be approximated by
vanilla gradient descent under this scenario. Crucially, we instead replace
the cross-entropy loss with mean square loss in order to reach
$\mathbf{W}^{*}$ without tedious training. As a result, we have new loss as:

$\begin{split}\mathcal{L}_{\text{R-MSE}}&=\sum_{i=1,y^{i}=1}^{n}(\omega(y^{i}-(\tilde{\mathbf{A}}^{2}\mathbf{X})_{i}))^{2}+\sum_{i=1,y^{i}=0}^{n}(y^{i}-(\tilde{\mathbf{A}}^{2}\mathbf{X})_{i})^{2}\\\
&=(\mathbf{Y}-\tilde{\mathbf{A}}^{2}\mathbf{X})^{T}\mathbf{D}(\mathbf{Y}-\tilde{\mathbf{A}}^{2}\mathbf{X}),\end{split}$
(10)

where

$\mathbf{D}=\begin{pmatrix}\omega^{y^{1}}&0&\dots&0\\\
0&\omega^{y^{2}}&\dots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\dots&\omega^{y^{n}}\end{pmatrix}$

is a diagonal matrix. Eqn. (10) is the loss function of weighted least square
(WLS [26]) problem. The point estimate of WLS is

$\mathbf{W}^{*}=((\tilde{\mathbf{A}}^{2}\mathbf{X})^{T}\mathbf{D}\tilde{\mathbf{A}}^{2}\mathbf{X})^{-1}(\tilde{\mathbf{A}}^{2}\mathbf{X})^{T}\mathbf{D}\mathbf{Y}.$
(11)

In consideration of the sigularity matrix
$(\tilde{\mathbf{A}}^{2}\mathbf{X})^{T}\mathbf{D}\tilde{\mathbf{A}}^{2}\mathbf{X}$
caused by $p>n$ (singular matrix does not have its inverse), we add Ridge
penalty [25] on $\mathcal{L}_{\text{R-MSE}}$ to ameliorate the high
dimensional problem and obtain:

$\mathcal{L}_{\text{RR-
MSE}}=(\mathbf{Y}-\tilde{\mathbf{A}}^{2}\mathbf{X})^{T}\mathbf{D}(\mathbf{Y}-\tilde{\mathbf{A}}^{2}\mathbf{X})+\xi\mathbf{W}^{T}\mathbf{W},$
(12)

the corresponding point estimate of $\mathbf{W}^{*}$ is:

$\mathbf{W}^{*}=((\tilde{\mathbf{A}}^{2}\mathbf{X})^{T}\mathbf{D}\tilde{\mathbf{A}}^{2}\mathbf{X}+\xi\mathbf{I}_{p\times
p})^{-1}(\tilde{\mathbf{A}}^{2}\mathbf{X})^{T}\mathbf{D}\mathbf{Y}.$ (13)

During the testing phase, we feed $\mathbf{W}^{*}$ to $\mathsf{LGCN}$ and get
the prediction score
$\mathbf{Z}^{*}=\text{sigmoid}(\tilde{\mathbf{A}}^{2}\mathbf{X}\mathbf{W}^{*})$
for prediction.

Since the $\mathsf{GCN}$-based GAD system is a supervised structural poisoning
attacks, the attacker’s goal is to decrease the classification accuracy of the
surrogate model in the previous context under the limited budgets. The
reformulation of the objective is:

$\begin{split}\mathbf{A}^{*}=&\operatorname*{arg\,min}_{\mathbf{A}}-\mathcal{L}_{\text{R-BCE}}(\mathbf{A},\mathbf{X},\mathbf{W}^{*},\mathbf{Y});\\\
\text{s.t.}\quad&\mathbf{W}^{*}=\operatorname*{arg\,min}_{\mathbf{W}}\mathcal{L}_{\text{RR-
MSE}}(\mathbf{A},\mathbf{X},\mathbf{W},\mathbf{Y}),\\\
&\frac{1}{2}||\mathbf{A}_{0}-\mathbf{A}||_{1}\leq
B,\quad\mathbf{A}\in\\{0,1\\}^{n\times n}.\end{split}$ (14)

Here we emphasize that the attack loss $\mathcal{L}_{\text{R-BCE}}$ can be
partitioned into two parts to incorporate the information of the training and
testing data:

$\mathcal{L}_{\text{R-BCE}}(\mathbf{Y})=h\mathcal{L}_{\text{R-BCE}}(\mathbf{Y}^{train})+(1-h)\mathcal{L}_{\text{R-BCE}}(\hat{\mathbf{Y}}^{test}),$
(15)

where $\mathbf{Y}^{train}$ is the training node labels,
$\hat{\mathbf{Y}}^{test}$ is the predictions for the testing node labels based
on the pre-trained $\mathsf{LGCN}$. Referring to [9], we choose $h=0.5$ during
training phase. With the help of the close form of $\mathbf{W}^{*}$, we can
transform the bi-level optimization problem to the one-level case:

$\begin{split}\mathbf{A}^{*}=&-\operatorname*{arg\,min}_{\mathbf{A}}\mathcal{L}_{\text{R-BCE}}(\mathbf{A},\mathbf{X},\mathbf{W}^{*},\mathbf{Y});\\\
\text{s.t.}\quad&\tilde{\mathbf{A}}=\text{diag}(\sum_{i=1}^{n}\mathbf{A}_{i})^{-\frac{1}{2}}(\mathbf{A+I})\text{diag}(\sum_{i=1}^{n}\mathbf{A}_{i})^{-\frac{1}{2}},\\\
&\mathbf{W}^{*}=((\tilde{\mathbf{A}}^{2}\mathbf{X})^{T}\mathbf{D}\tilde{\mathbf{A}}^{2}\mathbf{X}+\xi\mathbf{I}_{p\times
p})^{-1}(\tilde{\mathbf{A}}^{2}\mathbf{X})^{T}\mathbf{D}\mathbf{Y}^{train},\\\
&\frac{1}{2}||\mathbf{A}_{0}-\mathbf{A}||_{1}\leq
B,\quad\mathbf{A}\in\\{0,1\\}^{n\times n}.\end{split}$ (16)

Solving $\mathbf{A}^{*}$ lead to a optimal solution to the above discrete
optimization problem.

##  5 Attack Methods

Now, the task of designing structural poisoning attacks amounts to solving the
two optimization problems (7) and (16). In this section, we introduce three
methods, $\mathsf{GradMaxSearch}$, $\mathsf{ContinuousA}$, and
$\mathsf{BinarizedAttack}$. Specifically, the first two proposed methods
$\mathsf{GradMaxSearch}$ and $\mathsf{ContinuousA}$ are adapted from typical
approaches in the literature for solving similar problems. We further propose
$\mathsf{BinarizedAttack}$ to address their limitations.

###  5.1 Conventional Methods

Solving the optimization problem (7) to obtain the optimal graph structure is
hard in general, mainly due to the integer variables involved. Thus a common
approach is to relax the integral constraints, transforming the optimization
problem to its continuous counterpart, for which gradient-descent-based
optimization techniques could be employed. Ideally, a continuous optimal
solution $\tilde{\mathbf{A}}^{*}$ is obtained, which is then transformed to a
discrete solution $\mathbf{A}^{*}$. This approach faces two central
challenges: i) how to use the gradient information for the guidance of
searching for $\tilde{\mathbf{A}}^{*}$, and ii) how to discretize
$\tilde{\mathbf{A}}^{*}$ to obtain $\mathbf{A}^{*}$. Based on the previous
works in the literature, we propose two methods.

####  5.1.1 $\mathsf{GradMaxSearch}$

Most of the previous works on structural attacks utilize a greedy strategy to
solve the optimization problem in an iterative way. Specifically, the integer
constraints on $\mathbf{A}$ are relaxed and in each iteration, the gradients
of the objective with respect to each entry of $\tilde{\mathbf{A}}$ are
calculated. Then, the entry with the largest gradient is picked for
alternation (either deleting or adding an edge). Intuitively, a larger
gradient indicates a bigger impact on the objective value. The iteration
continues until budget constraint $B$ is reached. Attacking $\mathsf{LGCN}$
with $\mathsf{GradMaxSearch}$ is similar to attacking $\mathsf{OddBall}$.

Regarding the implementation of $\mathsf{GradMaxSearch}$, we note that when
picking the entry associated with the largest gradient, one should pay
attention to the signs of the gradients. For example, when $\mathbf{A}_{ij}=0$
we need to ensure that the corresponding gradient $\frac{\partial
AS(v_{a})}{\partial\mathbf{A}_{ij}}<0$ (and vice versa) to make the operation
(add or delete) valid. In addition, to avoid repeatedly adding and deleting
the same edge, we maintain a pool to record the edges that have not been
modified. Meanwhile, we also avoid the operations that would result in
singleton nodes.

####  5.1.2 $\mathsf{ContinuousA}$

Softening the discrete objective is another concerns. An apparent bottleneck
of $\mathsf{GradMaxSearch}$ is that the one-level discrete objective function
is only optimized through $B$ steps, where $B$ is the attacker’s budget. An
alternative way is thus to totally treat $\mathbf{A}$ as continuous variables
$\tilde{\mathbf{A}}\in[0,1]^{n\times n}$ and optimize the objective function
until it converges.

In detail, by solving the optimization problem in the continuous domain using
gradient-descent, we obtain the sub-optimal continuous solution
$\tilde{\mathbf{A}}^{*}$. We then calculate the differences in absolute values
between the original $\mathbf{A}$ and $\tilde{\mathbf{A}}^{*}$, and pick those
edges associated with the top-$B$ absolute differences to modify.

###  5.2 BinarizedAttack

Both $\mathsf{GradMaxSearch}$ and $\mathsf{ContinuousA}$ have their own
limitations. For $\mathsf{GradMaxSearch}$, one major limitation is that the
gradient only indicates a relatively small fractional update on the
corresponding entry in $\mathbf{A}$; while a discrete value ($\pm 1$) is
actually updated. This would not necessarily optimize the objective. Moreover,
due to budget constraint $B$, the objective is only optimized through $B$
steps. $\mathsf{ContinuousA}$ treating $\mathbf{A}$ as continuous in the whole
process of optimization, totally ignoring the effect of discrete updates on
the objective function. Furthermore, without careful design, converting from
the fractional optimal solution $\tilde{\mathbf{A}}^{*}$ to $\mathbf{A}^{*}$
may lead to arbitrary bad performances.

We propose $\mathsf{BinarizedAttack}$ to mitigate these limitations. At a high
level, $\mathsf{BinarizedAttack}$ is a gradient-descent-based approach that
optimizes the objective in iterations. Each iteration consists of a forward
pass, where the objective function is evaluated on some decision variables,
and a backward pass, where the decision variables are updated based on
calculated gradients. The core idea of $\mathsf{BinarizedAttack}$ lies in the
design of two sets of decision variables as well as the way of utilizing
gradient information. Specifically, we associate each entry $\mathbf{A}_{ij}$
with a discrete dummy (the use of dummy will be explained later) decision
variable $\mathbf{Z}_{ij}\in\\{-1,+1\\}$, where $\mathbf{Z}_{ij}=-1$ indicates
that the corresponding entry $\mathbf{A}_{ij}$ will be modified and vice
versa. For example, if $\mathbf{A}_{ij}=1$ and $\mathbf{Z}_{ij}=-1$, we will
change $\mathbf{A}_{ij}$ to $0$. Let $\mathbf{A}_{0}$ and $\mathbf{A}$ be the
original and modified adjacency matrix, respectively, which are connected
through the decision variables $\mathbf{Z}$ by

$\mathbf{A}=(\mathbf{A}_{0}-0.5\cdot\mathbf{1}^{n\times
n})\odot\mathbf{Z}+0.5,$ (17)

where $\odot$ denotes element-wise multiplication between two matrices.

We further associate each entry $\mathbf{A}_{ij}$ with a continuous soft
decision variable $\dot{\mathbf{Z}}\in[0,1]$ to facilitate gradient
computation. The two sets of decision variables $\dot{\mathbf{Z}}$ and
$\mathbf{Z}$ are related by

$\displaystyle\mathbf{Z}=-\mathsf{binarized}(2\cdot\dot{\mathbf{Z}}-1),$ (18)

where we define the function $\mathsf{binarized}(x)$ as
$\mathsf{binarized}(x)=+1$ if $x\geq 0$ and $\mathsf{binarized}(x)=-1$
otherwise. Since our objective function $\tilde{S}_{\mathcal{T}}(\mathbf{A})$
depends on $\mathbf{A}$, we can easily rewrite it as a function relying on the
decision variables $\dot{\mathbf{Z}}$ and $\mathbf{Z}$ as
$\tilde{S}_{\mathcal{T}}(\dot{\mathbf{Z}},\mathbf{Z})$.

We proceed to handle budget constraint (7c). Our goal is to transform this
constraint as part of the objective function so that we can thoroughly
optimize the objective beyond $B$ steps. To this end, we impose a LASSO
penalty [28] on the continuous soft decision variables $\dot{\mathbf{Z}}$. Our
choice of LASSO comes from the fact that LASSO can obtain sparser solutions
compared with the L2 penalty [29]. Based on Eqn. (18), we can observe that a
larger $\dot{\mathbf{Z}}_{ij}$ indicates that it is more likely to modify the
entry $\mathbf{A}_{ij}$ (i.e., $\mathbf{Z}_{ij}=-1$). As a result, in the
optimization process, while the LASSO penalty term pushes the entries in
$\dot{\mathbf{Z}}$ to zero, it is also restricting the modifications made to
$\mathbf{A}$, achieving a similar effect of the budget constraint.

####  5.2.1 Attacking $\mathsf{OddBall}$

Now, we can reformulate the attack problem as an optimization problem with
$\dot{\mathbf{Z}}$ and $\mathbf{Z}$ as decision variables:

$\displaystyle\mathbf{\dot{\mathbf{Z}}}^{*}=\operatorname*{arg\,min}_{\mathbf{\dot{Z}}}\sum_{a=1}^{\tau}(E_{a}-e^{\rho})^{2}+\lambda||\dot{\mathbf{Z}}||_{1}^{1},$
(19a) $\displaystyle\text{s.t.}\quad\rho=(1,\ln N_{a})^{T}([1,\ln N]^{T}[1,\ln
N])^{-1}[1,\ln N]^{T}\ln E;$ (19b) $\displaystyle\quad\quad
N_{i}=\sum_{j=1}^{n}\mathbf{A}_{ij},\quad
E_{i}=N_{i}+\frac{1}{2}\mathbf{A}_{ii}^{3};$ (19c)
$\displaystyle\quad\quad\mathbf{A}=(\mathbf{A}_{0}-0.5\cdot\mathbf{1}^{n\times
n})\odot\mathbf{Z}+0.5;$ (19d)
$\displaystyle\quad\quad\mathbf{Z}=-\mathsf{binarized}(2\cdot{\mathbf{\dot{Z}}}-1).$
(19e)

Note that we used a parameter $\lambda$ to tune the relative importance of the
adversarial objective and the penalty term.

Now, we can solve (19) through iteration. Specifically, in the forward pass,
we will evaluate the objective by the discrete dummy variables $\mathbf{Z}$.
Intuitively, this will more accurately measure the effect of discrete updates
of the graph structure on the objective. In the backward pass, we can compute
the gradients with respect to $\dot{\mathbf{Z}}$, and update $\mathbf{Z}$ from
(19e). In this way, by observing $\dot{\mathbf{Z}}$, we can obtain the entries
in $\mathbf{A}$ that the attacker needs to modify. We note that the discrete
variables $\mathbf{Z}$ are only used to evaluate the objective function for
optimization; the final decisions are made from the soft variables
$\dot{\mathbf{Z}}$, thus the reason why $\mathbf{Z}$ are called dummy
variables.

####  5.2.2 Attacking $\mathsf{LGCN}$

As for attacking $\mathsf{LGCN}$, similarly we deploy the interaction between
a discrete decision variable $\mathbf{Z}\in\\{-1,+1\\}^{n\times n}$ and
continuous random variable $\mathbf{\dot{Z}}\in[0,1]^{n\times n}$ by Eqn.
(18). Then the objective function of $\mathsf{BinarizedAttack}$ is:

$\displaystyle\mathbf{\dot{Z}}^{*}=$
$\displaystyle\operatorname*{arg\,min}_{\mathbf{\dot{Z}}}-\mathcal{L}_{\text{R-BCE}}(\mathbf{A},\mathbf{X},\mathbf{W}^{*},\mathbf{Y})+\lambda||\mathbf{\dot{Z}}||_{1}^{1};$
(20a) s.t.
$\displaystyle\tilde{\mathbf{A}}=\text{diag}(\sum_{i=1}^{n}\mathbf{A}_{i})^{-\frac{1}{2}}(\mathbf{A+I})\text{diag}(\sum_{i=1}^{n}\mathbf{A}_{i})^{-\frac{1}{2}},$
(20b)
$\displaystyle\mathbf{W}^{*}=((\tilde{\mathbf{A}}^{2}\mathbf{X})^{T}\mathbf{D}\tilde{\mathbf{A}}^{2}\mathbf{X}+\xi\mathbf{I}_{p\times
p})^{-1}(\tilde{\mathbf{A}}^{2}\mathbf{X})^{T}\mathbf{D}\mathbf{Y}^{train},$
(20c) $\displaystyle\mathbf{A}=(\mathbf{A}_{0}-0.5\cdot\mathbf{1}^{n\times
n})\odot\mathbf{Z}+0.5,$ (20d)
$\displaystyle\mathbf{Z}=-\mathsf{binarized}(2\cdot{\mathbf{\dot{Z}}}-1).$
(20e)

The training procedure of the $\mathsf{BinarizedAttack}$ against
$\mathsf{LGCN}$ is shown in Alg. 1. We leave the model comparison between the
three attack methods based on the surrogate model in the experiment part.

Input: clean graph $\mathbf{A}^{0}$, budget $B$, surrogate model
$\mathsf{LGCN}$, training nodal labels $\mathbf{Y}^{train}$,
$\Lambda=\\{\lambda_{k}\\}_{k=1}^{K}$, iteration number $T$, learning rate
$\eta$.

Parameter: Perturbation $\dot{\mathbf{Z}}$.

1: Pre-train $\mathsf{LGCN}$ and get prediction $\hat{\mathbf{Y}}^{test}$
based on the prediction score:
$\mathbf{Z}^{*}_{test}=\text{sigmoid}(\mathbf{A}_{0}^{2}\mathbf{X}\mathbf{W}^{*}).$

2: Let $t=0$ and initialize $\dot{\mathbf{Z}}$.

3: for $k\leftarrow 1,2,...,K$ do

4: while $t\leq T$ do

5: Forward Pass:

6: Calculate $\mathbf{Z}=-\mathsf{binarized}(2\cdot\dot{\mathbf{Z}}-1).$

7: Calculate $\mathbf{A}=(\mathbf{A}_{0}-0.5\cdot\mathbf{1}^{n\times
n})\odot\mathbf{Z}+0.5$.

8: Calculate the symmetric normalized Laplacian
$\tilde{\mathbf{A}}=\text{diag}(\sum_{i=1}^{n}\mathbf{A}_{i})^{-\frac{1}{2}}(\mathbf{A+I})\text{diag}(\sum_{i=1}^{n}\mathbf{A}_{i})^{-\frac{1}{2}}$.

9: Obtain RWLS point estimate
$\mathbf{W}^{*}=((\tilde{\mathbf{A}}^{2}\mathbf{X})^{T}\mathbf{D}\tilde{\mathbf{A}}^{2}\mathbf{X}+\xi\mathbf{I}_{p\times
p})^{-1}(\tilde{\mathbf{A}}^{2}\mathbf{X})^{T}\mathbf{D}\mathbf{Y}^{train}$.

10: Obtain goal function
$\mathcal{L}_{\text{R-BCE}}+\lambda_{k}||\dot{Z}||_{1}^{1}$.

11: Backward Pass:

12: $\forall i,j\in{1,2,...,n},$ calculate the gradient of the goal function
$\mathcal{L}_{\text{R-BCE}}$ w.r.t $\dot{\mathbf{Z}}_{ij}$, i.e.,
$\frac{\partial\mathcal{L}_{\text{R-BCE}}}{\partial\dot{\mathbf{Z}}_{ij}}.$

13: Projection Gradient Descent:

14:
$\dot{\mathbf{Z}}\rightarrow\prod_{[0,1]}(\dot{\mathbf{Z}}-\eta\frac{\partial\mathcal{L}_{\text{R-BCE}}}{\partial\dot{\mathbf{Z}}_{ij}})$

15: end while

16: return $\dot{\mathbf{Z}}$

17: end for

18: for $b\leftarrow 1,2,...,B$ do

19: Pick out $\dot{\mathbf{Z}}=min\ \mathcal{L}_{\text{R-BCE}}$ satisfies
$\sum\mathbf{Z}=-b$.

20: Get poisoned graph
$\mathbf{A}^{b}=(\mathbf{A}_{0}-0.5\cdot\mathbf{1}^{n\times
n})\odot\mathbf{Z}+0.5$.

21: return $\mathbf{A}^{b}$.

22: end for

Algorithm 1 $\mathsf{BinarizedAttack}$ for $\mathsf{LGCN}$

After the training phase of the structural attacks against the surrogate
model, we ideally feed the poisoned graphs under different attack power into
six popular GAD systems with the $\mathsf{GCN}$ as their backbone in a black-
box manner: GCN-reweight [7], GAT-reweight [24], FdGars [15], GEM [16],
Player2vec [17], GraphSMOTE [18]. We leave the model description and the
black-box attack results in the experiment part.

##  6 Experiments

###  6.1 Datasets and Experiment Settings

####  6.1.1 Datasets

BA (Barabasi-Albert) [30] is a graph generative model which incorporate the
idea of preferential attachment on the links probability. we set the number of
edges attaching from a new node to existing nodes is $5$. Blogcatalog [31] is
a social network indicating follower/followee relationships among bloggers in
a blog sharing website. The network has 88,800 nodes and 2.1M edges. Wikivote
[32] contains all the Wikipedia voting data from the inception of Wikipedia
till January 2008. Nodes in the network represent Wikipedia users and the edge
represents that user $i$ voted on user $j$. The dataset contains around 7000
nodes and 0.1M edges. Bitcoin-Alpha [33] is a who-trusts-whom social network
of traders who trade Bitcoin on the Bitcoin-Alpha platform. It is a weighted
signed network with weights ranging from $+10$ to $-10$. It has more than 3000
nodes and 24186 edges. We pre-process the data by removing all the negative
edges and erasing the weights of all the remaining edges, resulting in an
unsigned unweighted version of Bitcoin-Alpha. For Wikivote and Bitcoin-Alpha
we randomly sample the connected sub-graph with around 1000 nodes from the
whole graph. Citeseer [34], Cora [35] Cora-ML [36] are the citation networks
which well capture the citation relations and co-authors relations. ca-GrQc
[37] is a collaboration network from the e-print arXiv and covers scientific
collaborations between authors papers submitted to General Relativity and
Quantum Cosmology category. For all the real-world graph data we pick out the
largest connnected component to prevent the present of the isolated nodes. The
statistics of the real datasets are summarized in Tab. I. Here Citeseer-Wo
means we only consider the structural information of Citeseer dataset.

TABLE I: Statistics of datasets.

Dataset | # Nodes | # Edges | # Attributes | # Anomalies
---|---|---|---|---
BA | $1000$ | $4975$ | NA | NA
Wikivote | $1012$ | $4860$ | NA | NA
Bitcoin-Alpha | $1025$ | $2311$ | NA | NA
Cora-ML | $2810$ | $7981$ | NA | NA
Citeseer-Wo | $3327$ | $4732$ | NA | NA
ca-GrQc | $5242$ | $14496$ | NA | NA
Cora | $2708$ | $5803$ | $1433$ | $150$
Citeseer | $3327$ | $4732$ | $3703$ | $150$
Blogcatalog | $5196$ | $172652$ | $8189$ | $300$

####  6.1.2 Setting

For datasets in Tab. I, we analyze the structural poisoning attacks against
$\mathsf{OddBall}$ with the first six datasets. We determine our target set by
sampling 10 target nodes from the top-$50$ nodes based on $\mathsf{AScore}$
(From now on we denote anomaly score as $\mathsf{AScore}$ for simplicity)
rankings. For each experiment, we sample target nodes 5 times individually and
report the mean values to measure the efficacy of the structural attack on
$\mathsf{OddBall}$. For structural attack (add/delete edges) on node anomaly
detection, we aim to minimize the $\mathsf{AScore}$ sums for target set $V$
under different budget constraints. We determine the max budget $B$ for each
case by the convergence of $\mathsf{AScore}$ for the three structural attacks.
We stop attacking until the changes of $\mathsf{AScore}$ saturated.

We explore the structural poisoning attacks against the $\mathsf{LGCN}$ with
the last three datasets in Tab. I. We synthetically inject structural
anomalies into these datasets and flag the perturbed nodes as anomalous.
Referring to [38], we randomly choose some nodes in the clean graph and inject
cliques to make them fully connected. We split the dataset into training and
testing part, the ratio of training to testing is $9:1$. We split the dataset
$5$ times and report the mean AUC scores for model comparison.

###  6.2 Attack Performance

(a) BA

(b) Bitcoin-Alpha

(c) Wikivote

(d) Citeseer-Wo

(e) Cora-ML

(f) ca-GrQc

Figure 4: Mean changes in $\mathsf{AScores}$ for BA, Bitcoin-Alpha, Wikivote
and Citeseer-Wo, Cora-ML and ca-GrQc.

(a) Case 1: Add edges

(b) Case 2: Delete edges

(c) Case 3: Add/Delete edges

Figure 5: $\mathsf{BinarizedAttack}$ can add, delete, and both add and delete
edges in the graph.

####  6.2.1 Effectiveness of attack $\mathsf{OddBall}$

Our main focus is to investigate whether the proposed attack methods can
effectively decrease $\mathsf{AScores}$ of the target nodes. We use the
Decreasing Percentage of $\mathsf{AScore}$ denoted as $\tau_{as}$ as the
evaluation metric. Specifically, let $S_{\mathcal{T}}^{0}$ and
$S_{\mathcal{T}}^{B}$ be the sum of $\mathsf{AScores}$ of the target nodes
before attack and after an attack with a budget $B$, respectively. Then,
$\tau_{as}$ is defined as
$\tau_{as}=(S_{\mathcal{T}}^{0}-S_{\mathcal{T}}^{B})/S_{\mathcal{T}}^{0}$.

Fig. 4 presents the $\tau_{as}$ of the three attack methods,
$\mathsf{BinarizedAttack}$, $\mathsf{GradMaxSearch}$, and
$\mathsf{ContinuousA}$, with varying attack power. In particular, the attack
power is measured as a percentage $\frac{B}{|E|}$, where $|E|$ is the number
of edges in the clean graph. We note that in all the cases, the attacker has
modified very limited edges in the graph: less than $2\%$ when $|V|=10$.

We can observe from Fig. 4 that both $\mathsf{BinarizedAttack}$ and
$\mathsf{GradMaxSearch}$ can significantly (up to $90\%$) decrease
$\mathsf{AScores}$ with very limited power while $\mathsf{ContinuousA}$ is not
effective in several cases. This demonstrated the unpredictable feature of
$\mathsf{ContinuousA}$ when converting continuous solutions to discrete ones.
Our main method $\mathsf{BinarizedAttack}$ consistently achieves the best
performance in all cases. We note that the margin between
$\mathsf{BinarizedAttack}$ and $\mathsf{GradMaxSearch}$ is significant (with a
$>10\%$ performance improvement) when the attack power is high (although the
two lines look close in the figures). For example, in Fig. 4(e), when the
attack power is $0.5\%$, $\mathsf{BinarizedAttack}$ outperforms
$\mathsf{GradMaxSearch}$ by $41.01\%$. One intriguing observation is that the
gap between $\mathsf{BinarizedAttack}$ and $\mathsf{GradMaxSearch}$ becomes
larger when we increase the attacker’s budget. The reason is that
$\mathsf{GradMaxSearch}$ is a greedy strategy in nature and should performs
well when modifying a few edges; meanwhile, it is also myopic when the budget
is large.

The computational bottleneck of $\mathsf{BinarizedAttack}$ lies in computing
the egonet edge features $E_{i}$ for all nodes, which involves calculating
$\mathbf{A}^{3}$. We use two techniques to allow $\mathsf{BinarizedAttack}$ to
scale to large graphs. First, we use the sparse matrix representation of the
adjacent matrix $\mathbf{A}$ and implement all the the computations based on
sparse matrix techniques. Empirically, we observe that, on the largest dataset
ca-GrQc, using sparse matrix can introduce an around $\times 10$ speed
increase. Second, we observe through our experiments that
$\mathsf{BinarizedAttack}$ will almost only modify the edges directly
connected to the targeted nodes. For example, the percentage of direct edges
are 94.7% for Bitcoin-Alpha. As a result, we can design a variant of
$\mathsf{BinarizedAttack}$, termed
$\mathsf{BinarizedAttack}$-$\mathsf{Direct}$, where the attacker is retreated
to altering the direct connections to the target nodes. This will decrease the
number of parameters involved in optimization; however, the cost is that the
performance of attack might be sacrificed. We implemented
$\mathsf{BinarizedAttack}$-$\mathsf{Direct}$ on the largest dataset ca-GrQc.
The results shows that $\mathsf{BinarizedAttack}$-$\mathsf{Direct}$ will
increase the speed by around $2$ times with a reasonable performance sacrifice
(Fig. 4(f)).

We further show in Fig. 5 how $\mathsf{BinarizedAttack}$ will actually modify
the structure of a real-world graph (Wikivote as the example). We demonstrated
three cases, where the attacker deletes edges only, adds edges only, and
deletes and adds edges simultaneously. It shows that
$\mathsf{BinarizedAttack}$ will indeed break the anomalous structural patterns
(i.e., near-star and near-clique) in the graph.

(a) Cora

(b) Citeseer

(c) Blogcatalog

Figure 6: Mean testing AUC scores for Cora, Citeseer and Blogcatalog attribute
graphs.

####  6.2.2 Effectiveness of attack $\mathsf{LGCN}$

For attacking supervised graph anomaly detection, we focus on analyzing the
attack efficacy of three attack methods by measuring the changes in the
overall AUC scores after attack. Fig. 6 presents the mean testing AUC scores
of the proposed three attack methods with different attacking powers. Since it
is a global attack, we may increase the degree attack power to up to around
$30\%$ to highlight the attacking performance on the supervised graph anomaly
detection.

We observe that similar to attacking $\mathsf{OddBall}$, our main method
$\mathsf{BinarizedAttack}$ consistently outperforms the other two baseline
methods in all the three real-world datasets. Especially, when the attacking
power increase to up to $30\%$ for Citeseer, $\mathsf{BinarizedAttack}$ can
effectively misguide the $\mathsf{LGCN}$ for anomaly node detection
($\text{AUC}=0.5$ means the classification is totally a random guess). At the
same time, the AUC margin between $\mathsf{BinarizedAttack}$ and
$\mathsf{GradMaxSearch}$ increase to up to around $0.15$ for Citeseer and
around $0.08$ for Cora.

####  6.2.3 Attacks against GCN-Based GAD Systems

TABLE II: Black-box attacks to GCN-based GAD systems.

BR (%) | GCN-reweight | GAT-reweight | FdGars | GEM | Player2vec | GraphSMOTE
---|---|---|---|---|---|---
Cora | Citeseer | Cora | Citeseer | Cora | Citeseer | Cora | Citeseer | Cora | Citeseer | Cora | Citeseer
$0$ | $0.72$ | $0.79$ | $0.71$ | $0.79$ | $0.65$ | $0.64$ | $0.72$ | $0.76$ | $0.67$ | $0.64$ | $0.73$ | $0.78$
$(0,1]$ | $0.71$ | $0.76$ | $0.70$ | $0.74$ | $0.60$ | $0.58$ | $0.68$ | $0.75$ | $0.60$ | $0.60$ | $0.73$ | $0.77$
$(1,2]$ | $0.70$ | $0.77$ | $0.72$ | $0.74$ | $0.60$ | $0.60$ | $0.70$ | $0.74$ | $0.61$ | $0.59$ | $0.73$ | $0.78$
$(2,5]$ | $0.68$ | $0.76$ | $0.70$ | $0.72$ | $0.60$ | $0.56$ | $0.70$ | $0.72$ | $0.59$ | $0.55$ | $0.73$ | $0.76$
$(5,7]$ | $0.65$ | $0.75$ | $0.66$ | $0.74$ | $0.59$ | $0.60$ | $0.70$ | $0.72$ | $0.60$ | $0.58$ | $0.72$ | $0.78$
$(7,10]$ | $0.68$ | $0.75$ | $0.68$ | $0.71$ | $0.56$ | $0.56$ | $0.70$ | $0.70$ | $0.58$ | $0.57$ | $0.71$ | $0.77$
$(10,15]$ | $0.60$ | $0.71$ | $0.60$ | $0.69$ | $0.54$ | $0.53$ | $0.57$ | $0.68$ | $0.53$ | $0.52$ | $0.67$ | $0.73$
$(15,20]$ | $0.60$ | $0.64$ | $0.60$ | $0.66$ | $0.52$ | $0.53$ | $0.56$ | $0.66$ | $0.51$ | $0.52$ | $0.66$ | $0.70$
$(20,25]$ | $0.54$ | $0.59$ | $0.56$ | $0.63$ | $0.48$ | $0.52$ | $0.49$ | $0.67$ | $0.51$ | $0.54$ | $0.63$ | $0.66$

In this section, we explore the black box attacks of the
$\mathsf{BinarizedAttack}$ against $\mathsf{LGCN}$ on other GCN-based GAD
models: GCN-reweight, GAT-reweight, FdGars, GEM, Player2vec and GraphSMOTE on
Cora and Citeseer dataset as exemplars. We measure the attack efficacy of
black-box attacks with the mean AUC scores on the testing data. The results
are shown in Tab. II. $BR$ is the modified edges percentage range. We can
observe that $\mathsf{BinarizedAttack}$ against $\mathsf{LGCN}$ has a
significant effect on the global accuracy of those six GCN-based GAD systems
especially for FdGars. That is, when the attacking power increases to more
than $20\%$, the mean AUC scores for Cora and Citeseer decrease to $0.48$ and
$0.52$, resulting in an approximately useless anomaly detector. On the other
hand, the biggest gap for mean AUC scores before and after an attack is the
black box attack against GEM on Cora dataset, which is up to around $32\%$
(decreased from $0.72$ to $0.49$). In general, the results in Tab. II shows
that $\mathsf{BinarizedAttack}$ against $\mathsf{LGCN}$ as a surrogate model
can effectively influence the $\mathsf{GCN}$ backbones of the other GAD
systems, resulting in respectable attack efficacy in black-box attack manner.

###  6.3 Side Effects of Attack OddBall

$\mathsf{BinarizedAttack}$ is a structural targeted attack that aims to
mislead the predictions of a small set of target nodes in poisoning manner. A
desirable character is that the attack would not significantly change the data
distribution to the extent that the poisoned data would look abnormal for a
smart defender. In other words, an attacker wants to make the attack
unnoticeable. In this paper we assume the detector is specially caring about
the ego-features distribution.

In our context, $\mathsf{BinarizedAttack}$ modifies the features
$(\mathbf{N}_{i},\mathbf{E}_{i})$ of the ego-net centered at node $i$. By
design, $\mathsf{BinarizedAttack}$ will significantly modify the features of
targeted nodes; however, an inevitable side effect for the structural attack
against $\mathsf{OddBall}$ is that $\mathsf{BinarizedAttack}$ would also
change the features of the rest of the nodes. In the worst case, the shift of
the feature distributions caused by an attack is so large that the attacked
graph would appear abnormal and be easily detected by the defender. Thus,
ideally, we would expect the side effect of $\mathsf{BinarizedAttack}$ is
reasonably small to achieve an unnoticeable attack.

We thus experiment to investigate the shift of distribution of the ego-
features $(\mathbf{N},\mathbf{E})$ before and after
$\mathsf{BinarizedAttack}$. Specifically, we deploy the permutation test [39],
which is a general non-parametric test to check whether two different
independent data groups follow the same distribution. However, it will be NP-
hard for the permutation test if we consider all kinds of perturbations in the
concatenation of two groups data. We thus refer to the Monte Carlo way to
approximate the p-value with sufficient experiment times, which is computed
as:

$\displaystyle p(t\geq t_{0})=\frac{1}{M}\sum_{j=1}^{M}I(t_{j}\geq t_{0}),$
(21)

where $t_{0}$ is the observed value of test statistic and $t$ is the statistic
calculated from the re-samples, i.e.,
$t(x_{1}^{\prime},x_{2}^{\prime},...,x_{n}^{\prime},y_{1}^{\prime},y_{2}^{\prime},...,y_{n}^{\prime})=|\bar{x^{\prime}}-\bar{y^{\prime}}|,$
$M$ is the Monte Carlo sampling times (in the experiment we set $M=100000$).
$x$ and $y$ can be either $\mathbf{N}^{clean}$ and $\mathbf{N}^{poisoned}$ or
$\mathbf{E}^{clean}$ and $\mathbf{E}^{poisoned}$. $x^{\prime}$ and
$y^{\prime}$ are re-samples of
$\mathsf{Concat}[\mathbf{N}^{clean}||\mathbf{N}^{poisoned}]$ or
$\mathsf{Concat}[\mathbf{E}^{clean}||\mathbf{E}^{poisoned}]$.

We report the $p$-value of ego-features $\mathbf{N}$ and $\mathbf{E}$ on two
real datasets: Bitcoin-Alpha and Wikivote. The results are shown in Tab. III,
where we consider ego-features of the poisoned graph with maximum
perturbations and $|V|=30$.

TABLE III: $p$-values for ego-features.

$t$ features $p$ | Bitcoin-Alpha | Wikivote
---|---|---
$\mathbf{N}$ | $\mathbf{E}$ | $\mathbf{N}$ | $\mathbf{E}$
$1$ | $0.72$ | $0.04$ | $0.56$ | $0.02$
$2$ | $0.66$ | $0.03$ | $0.58$ | $0.02$
$3$ | $0.75$ | $0.04$ | $0.56$ | $0.01$
$4$ | $0.72$ | $0.04$ | $0.57$ | $0.02$
$5$ | $0.71$ | $0.03$ | $0.56$ | $0.005$

From Tab. III we notice that under 99% significant level we cannot reject the
null hypothesis that $\mathbf{N}^{clean}$ and $\mathbf{N}^{poisoned}$ follows
the same distribution, that is, we can draw the conclusion that
$\mathsf{BinarizedAttack}$ does not manipulate the distribution of
$\mathbf{N}$. For ego-feature $\mathbf{E}$, in most cases, we cannot reject
the null hypothesis. However, in experiment 5 for Wikivote the $p$-value is
less than 1%, so we reject the null hypothesis, that is, in Wikivote
experiment 5 $\mathsf{BinarizedAttack}$ manipulate the distribution of E under
the significant level 99%. As an example, the probability density function of
$\textbf{N}^{clean}$ and $\textbf{N}^{poisoned}$ and $\textbf{E}^{clean}$ and
$\textbf{E}^{poisoned}$ on Wikivote are presented in Fig. 7 (similar results
are observed on other datasets).

(a) Wikivote N

(b) Wikivote E

Figure 7: The probability density function of ego-features N and E for clean
and poisoned graphs on Wikivote.

###  6.4 Ablation Study on WLS

In this section, we start to discuss the contribution of the weighted least
square estimation (WLS) in the attack model. If we set the diagonal matrix
$\mathbf{D}=\text{Diag}([1,...,1]_{n\times 1})$, the point estimate of RWLS in
Eqn. (13) changes to Ridge regression [25]:

$\displaystyle\tilde{\mathbf{A}}=\text{diag}(\sum_{i=1}^{n}\mathbf{A}_{i})^{-\frac{1}{2}}(\mathbf{A+I})\text{diag}(\sum_{i=1}^{n}\mathbf{A}_{i})^{-\frac{1}{2}},$
(22a)
$\displaystyle\mathbf{W}^{*}=((\tilde{\mathbf{A}}^{2}\mathbf{X})^{T}\tilde{\mathbf{A}}^{2}\mathbf{X}+\xi\mathbf{I}_{p\times
p})^{-1}(\tilde{\mathbf{A}}^{2}\mathbf{X})^{T}\mathbf{Y}.$ (22b)

We compare the decreasing percentage of mean AUC scores for RWLS and Ridge
regression on Cora dataset as exemplar. Fig. 8(a) illustrates that by using
RWLS as the point estimate for $\mathsf{LGCN}$’s weights, the attacking
performance is significantly higher than Ridge regression (the decreasing
percentage of mean AUC scores for RWLS is much larger than Ridge). This
phenomenon is attributed to the fact that WLS incorporate the imbalanced
sample numbers and pay more attention to the minority class during the
training phase, leading to more suitable close form solutions of $W^{*}$.
Hence the introduction of RWLS makes a great contribution to the attack model.

(a) Ridge-vs-RWLS

(b) Tuning $\xi$

Figure 8: (a) RWLS vs Ridge; (b) is the sensitivity analysis on $\xi$.

###  6.5 Sensitivity Analysis on $\xi$

Another important issue is the choice of the penalty parameter $\xi$ for Ridge
regression. According to Tab. I, the dimension of the attributes for real-
world graphs are usually more than one thousand, thus leading to a high-
dimensional problem in the regression. The introduction of $L2$ penalty here
can not only prevent the inexistence of the inverse of singularity matrix in
the point estimate, but also highlight the important part of the nodal
attributes to prevent over-fitting.

Fig. 8(b) depicts the effect of choosing $\xi$ with varying order of
magnitudes for attack efficacy. The results show that too high and too low
value of $\xi$ will damage the attacking performance of the attack model.
Specially, if $\xi$ is ranged between $[0.001,0.01]$, the attacking
performance will be unstable. In this context, we regard that $\xi=0.1$ is a
suitable choice for attacking $\mathsf{LGCN}$. Without loss of generality, we
choose $\xi=0.1$ for attacking $\mathsf{LGCN}$ in Fig. 6 for sake of fair
comparison.

##  7 Conclusion

In this paper, we initiate the study to investigate the vulnerability of
graph-based anomaly detection under structural poisoning attacks. Specially,
we target on $\mathsf{OddBall}$ as feature extraction based anomaly detector
and $\mathsf{LGCN}$ as the surrogate model of the GCN-based anomaly detector,
we further mathematically formulate it as a discrete one-level optimization
problem by incorporating specially designed regression techniques (OLS
estimation for $\mathsf{OddBall}$ and RWLS estimation for $\mathsf{LGCN}$). We
then propose a novel training procedure $\mathsf{BinarizedAttack}$ which
effectively damages the target GAD systems, significantly outperforming
existing methods. Moreover, we explore the black-box attacks of the typical
six GCN-based GAD systems (GCN-reweight, GAT-reweight, FdGars, GEM, Player2vec
and GraphSMOTE) and prove that by universally attacking $\mathsf{LGCN}$ can
effectively transfer attack other GCN-based GAD systems in black-box manner.
In the future work, it is interesting to explore the possible countermeasure
against such poisoning attacks on graph data to enhance the robustness of the
existed graph anomaly detectors.

## References

  * [1] S. Khaled, N. El-Tazi, and H. M. O. Mokhtar, “Detecting fake accounts on social media,” in 2018 IEEE International Conference on Big Data (Big Data), pp. 3672–3681, 2018.
  * [2] A. Diadiushkin, K. Sandkuhl, and A. Maiatin, “Fraud detection in payments transactions: Overview of existing approaches and usage for instant payments,” Complex Systems Informatics and Modeling Quarterly, pp. 72–88, 10 2019.
  * [3] Q. Cao, M. Sirivianos, X. Yang, and T. Pregueiro, “Aiding the detection of fake accounts in large scale social online services,” in 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12), (San Jose, CA), pp. 197–210, USENIX Association, Apr. 2012.
  * [4] D. Kempe, J. Kleinberg, and É. Tardos, “Maximizing the spread of influence through a social network,” in Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 137–146, 2003.
  * [5] M. Iwamoto, S. Oshima, and T. Nakashima, “A study of malicious pdf detection technique,” in 2016 10th International Conference on Complex, Intelligent, and Software Intensive Systems (CISIS), pp. 197–203, 2016.
  * [6] L. Akoglu, M. McGlohon, and C. Faloutsos, “oddball: Spotting anomalies in weighted graphs,” in Advances in Knowledge Discovery and Data Mining (M. J. Zaki, J. X. Yu, B. Ravindran, and V. Pudi, eds.), (Berlin, Heidelberg), pp. 410–421, Springer Berlin Heidelberg, 2010.
  * [7] T. N. Kipf and M. Welling, “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, 2017.
  * [8] D. Zügner, A. Akbarnejad, and S. Günnemann, “Adversarial attacks on neural networks for graph data,” SIGKDD, Jul 2018.
  * [9] D. Zügner and S. Günnemann, “Adversarial attacks on graph neural networks via meta learning,” in International Conference on Learning Representations, 2019.
  * [10] I. Hubara, M. Courbariaux, D. Soudry, R. El-Yaniv, and Y. Bengio, “Binarized neural networks,” in Proceedings of the 30th International Conference on Neural Information Processing Systems, pp. 4114–4122, 2016.
  * [11] L. Akoglu, H. Tong, and D. Koutra, “Graph based anomaly detection and description: a survey,” Data mining and knowledge discovery, vol. 29, no. 3, pp. 626–688, 2015.
  * [12] H.-H. Chen and C. L. Giles, “Ascos: an asymmetric network structure context similarity measure,” in 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2013), pp. 442–449, IEEE, 2013.
  * [13] D. Kuang, C. Ding, and H. Park, “Symmetric nonnegative matrix factorization for graph clustering,” in Proceedings of the 2012 SIAM international conference on data mining, pp. 106–117, SIAM, 2012.
  * [14] U. Kang, D. H. Chau, and C. Faloutsos, “Mining large graphs: Algorithms, inference, and discoveries,” in 2011 IEEE 27th International Conference on Data Engineering, pp. 243–254, IEEE, 2011.
  * [15] J. Wang, R. Wen, C. Wu, Y. Huang, and J. Xion, “Fdgars: Fraudster detection via graph convolutional networks in online app review system,” in Companion Proceedings of The 2019 World Wide Web Conference, WWW ’19, (New York, NY, USA), p. 310–316, Association for Computing Machinery, 2019.
  * [16] Z. Liu, C. Chen, X. Yang, J. Zhou, X. Li, and L. Song, “Heterogeneous graph neural networks for malicious account detection,” in Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pp. 2077–2085, 2018.
  * [17] Y. Zhang, Y. Fan, Y. Ye, L. Zhao, and C. Shi, “Key player identification in underground forums over attributed heterogeneous information network embedding framework,” in Proceedings of the 28th ACM International Conference on Information and Knowledge Management, CIKM ’19, (New York, NY, USA), p. 549–558, Association for Computing Machinery, 2019.
  * [18] T. Zhao, X. Zhang, and S. Wang, “Graphsmote: Imbalanced node classification on graphs with graph neural networks,” in Proceedings of the 14th ACM International Conference on Web Search and Data Mining, WSDM ’21, (New York, NY, USA), p. 833–841, Association for Computing Machinery, 2021.
  * [19] K. Zhou and Y. Vorobeychik, “Robust collective classification against structural attacks,” in Conference on Uncertainty in Artificial Intelligence, pp. 250–259, PMLR, 2020.
  * [20] K. Zhou, T. P. Michalak, M. Waniek, T. Rahwan, and Y. Vorobeychik, “Attacking similarity-based link prediction in social networks,” in Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pp. 305–313, 2019.
  * [21] M. Waniek, K. Zhou, Y. Vorobeychik, E. Moro, T. P. Michalak, and T. Rahwan, “How to hide one’s relationships from link prediction algorithms,” Scientific reports, vol. 9, no. 1, pp. 1–10, 2019.
  * [22] M. Waniek, T. P. Michalak, M. J. Wooldridge, and T. Rahwan, “Hiding individuals and communities in a social network,” Nature Human Behaviour, vol. 2, no. 2, pp. 139–147, 2018.
  * [23] B. Zdaniuk, Ordinary Least-Squares (OLS) Model, pp. 4515–4517.  Dordrecht: Springer Netherlands, 2014.
  * [24] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, “Graph attention networks,” in International Conference on Learning Representations, 2018.
  * [25] D. E. Hilt, D. W. Seegrist, U. S. F. Service., and P. Northeastern Forest Experiment Station (Radnor, Ridge, a computer program for calculating ridge regression estimates, vol. no.236.  Upper Darby, Pa, Dept. of Agriculture, Forest Service, Northeastern Forest Experiment Station, 1977.  https://www.biodiversitylibrary.org/bibliography/68934.
  * [26] Weighted Least-Squares Method, pp. 566–569.  New York, NY: Springer New York, 2008.
  * [27] A. F. Agarap, “Deep learning using rectified linear units (relu),” arXiv preprint arXiv:1803.08375, 2018.
  * [28] R. Tibshirani, “Regression shrinkage and selection via the lasso,” JOURNAL OF THE ROYAL STATISTICAL SOCIETY, SERIES B, vol. 58, pp. 267–288, 1994\.
  * [29] A. E. Hoerl and R. W. Kennard, “Ridge regression: Biased estimation for nonorthogonal problems,” Technometrics, vol. 12, pp. 55–67, 1970.
  * [30] R. Albert and A.-L. Barabási, “Statistical mechanics of complex networks,” Rev. Mod. Phys., vol. 74, pp. 47–97, Jan 2002.
  * [31] R. Zafarani and H. Liu, “Users joining multiple sites: Distributions and patterns,” 2014.
  * [32] J. Leskovec, D. Huttenlocher, and J. Kleinberg, “Predicting positive and negative links in online social networks,” in Proceedings of the 19th international conference on World wide web, pp. 641–650, 2010.
  * [33] S. Kumar, B. Hooi, D. Makhija, M. Kumar, C. Faloutsos, and V. Subrahmanian, “Rev2: Fraudulent user prediction in rating platforms,” in Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pp. 333–341, ACM, 2018.
  * [34] C. Giles, K. Bollacker, and S. Lawrence, “Citeseer: an automatic citation indexing system,” in Proceedings of the ACM International Conference on Digital Libraries, pp. 89–98, ACM, 1998.  Proceedings of the 1998 3rd ACM Conference on Digital Libraries ; Conference date: 23-06-1998 Through 26-06-1998.
  * [35] Y. Liu, Z. Li, S. Pan, C. Gong, C. Zhou, and G. Karypis, “Anomaly detection on attributed networks via contrastive self-supervised learning,” IEEE Transactions on Neural Networks and Learning Systems, pp. 1–15, 2021.
  * [36] A. Bojchevski and S. Günnemann, “Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking,” in International Conference on Learning Representations, 2018.
  * [37] J. Leskovec, J. Kleinberg, and C. Faloutsos, “Graph evolution: Densification and shrinking diameters,” ACM transactions on Knowledge Discovery from Data (TKDD), vol. 1, no. 1, pp. 2–es, 2007.
  * [38] D. B. Skillicorn, “Detecting anomalies in graphs,” in 2007 IEEE Intelligence and Security Informatics, pp. 209–216, IEEE, 2007.
  * [39] L. Stanberry, Permutation Test, pp. 1678–1678.  New York, NY: Springer New York, 2013.