# Complex Network Effects on the Robustness of Graph Convolutional
Networks††thanks: This material is based upon work supported by the United
States Air Force under Air Force Contract No. FA8702-15-D-0001 and the Combat
Capabilities Development Command Army Research Laboratory (under Cooperative
Agreement Number W911NF-13-2-0045). Any opinions, findings, conclusions or
recommendations expressed in this material are those of the authors and do not
necessarily reflect the views of the United States Air Force or Army Research
Laboratory.

Benjamin A. Miller Contact author<EMAIL_ADDRESS>Northeastern
University, Boston MA  Kevin Chan  Army Research Laboratory, Adelphi MD  Tina
Eliassi-Rad  Northeastern University, Boston MA

###### Abstract

Vertex classification—the problem of identifying the class labels of nodes in
a graph—has applicability in a wide variety of domains. Examples include
classifying subject areas of papers in citation networks or roles of machines
in a computer network. Vertex classification using graph convolutional
networks is susceptible to targeted poisoning attacks, in which both graph
structure and node attributes can be changed in an attempt to misclassify a
target node. This vulnerability decreases users’ confidence in the learning
method and can prevent adoption in high-stakes contexts. Defenses have also
been proposed, focused on filtering edges before creating the model or
aggregating information from neighbors more robustly. This paper considers an
alternative: we leverage network characteristics in the training data
selection process to improve robustness of vertex classifiers.

We propose two alternative methods of selecting training data: (1) to select
the highest-degree nodes and (2) to iteratively select the node with the most
neighbors minimally connected to the training set. In the datasets on which
the original attack was demonstrated, we show that changing the training set
can make the network much harder to attack. To maintain a given probability of
attack success, the adversary must use far more perturbations; often a factor
of 2–4 over the random training baseline. In addition, these training set
selection methods often work in conjunction with the best recently published
defenses to provide even greater robustness. While increasing the amount of
randomly selected training data sometimes results in a more robust classifier,
the proposed methods increase robustness substantially more. We also run a
simulation study in which we demonstrate conditions under which each of the
two methods outperforms the other, controlling for the graph topology,
homophily of the labels, and node attributes.

##  1 Introduction

Classification of vertices in graphs is an important problem in a variety of
applications, from e-commerce (classifying users for targeted advertising) to
security (classifying computer nodes as malicious or not) to bioinformatics
(classifying roles in a protein interaction network). In the past several
years, numerous methods have been developed for this task (see, e.g., [17,
28]). More recently, research has focused on attacks by adversaries [52, 11]
and robustness to such attacks [43]. If an adversary were able to insert
misleading data into the training set (e.g., generate benign traffic during a
data collection period that could conceal its behavior during
testing/inference time), the chance of successfully evading detection would
increase, leaving data analysts unable to respond to potential threats.

To classify vertices in the presence of adversarial activity, we must
implement learning systems that are robust to such potential manipulation. If
such malicious behavior has low cost to the attacker and imposes high cost on
the data analyst, machine learning systems will not be trusted and adopted for
use in practice, especially in high-stakes scenarios such as network security
and traffic safety. Understanding how to achieve robustness is key to
realizing the full potential of machine learning.

Adversaries, of course, will attempt to conceal their manipulation. The first
published poisoning attack against vertex classification was an adversarial
technique called Nettack [52], which can create perturbations that are subtle
while still being extremely effective in decreasing performance on the target
vertices. The authors use their poisoning attack against a graph convolutional
network (GCN).

From a defender’s perspective, we aim to make it more difficult for the
attacker to cause node misclassification. In addition to changing the
properties of the classifier itself, there may be portions of a complex
network that provide more information for learning than others. Complex
networks are highly heterogeneous and random sampling may not be the best way
to obtain labels. If there is flexibility in the means of obtaining training
data, the defender should leverage what is known about the graph topology.

This paper demonstrates that leveraging complex network properties can improve
robustness of GCNs in the presence of adversaries. We focus on two alternative
techniques for training data selection. Both methods aim to train with a
subset of nodes that are well connected to the held out set. Here we see a
benefit, often raising the number of perturbations required for a given level
of attack success by over a factor of 2. When it is possible to pick a
specific subset on which to train, this can provide a significant advantage.
Some combination of these methods will likely be useful to develop a more
robust vertex classification system.

###  1.1 Scope and Contributions

In this paper, we are specifically interested in _targeted poisoning_ attacks
against vertex classifiers, where the data are modified at training time to
cause a specific target node to be misclassified. We consider attacks against
the structure of the graph, rather than against node attributes. We focus on
classification methods where there is an implicit assumption of homophily.
Working within this context, the contributions of this work are as follows:

  * •

We propose two methods—StratDegree and GreedyCover—for selecting training data
that result in a greater burden on attackers.

  * •

We demonstrate that the robustness gained via these methods cannot be reliably
obtained by simply increasing the amount of randomly selected training data.

  * •

We show that the most robust defense methods are often improved by working in
conjunction with GreedyCover.

  * •

We show that there is no consistent tradeoff between the robustness gained
from these methods and classification performance.

  * •

In simulation, we study the effects of various generative models and report
the impact of class homophily, topological features, and node attribute
similarity across classes on classification performance and robustness to
attack.

These contributions all point toward interesting future research in this area,
such as determining the conditions under which such methods are effective.

###  1.2 Paper Organization

The remainder of this paper is organized as follows. In Section 2, we briefly
contextualize our work within the current literature. In Section 3 we describe
the vertex classification problem, GCNs, and the Nettack method. Section 4
outlines the methods we investigate to select training data, and Section 5
details the experimental setup, including datasets, attacks, and
classification methods. Section 6 documents experimental results on real data,
illustrating the effectiveness of the proposed methods. In Section 7, we
present the results of a simulation study in which we vary graph topology,
node attributes, and homophily, and evaluate robustness of the methods across
the landscape. In Section 8 we conclude with a summary and outline open
problems and future work.

##  2 Related Work

Adversarial examples in deep neural networks have received considerable
attention since they were documented several years ago [38]. Since that time,
numerous attack methods have been proposed, largely focused on the image
classification domain (though there has been interest in natural language
processing as well, e.g., [18]). In addition to documenting adversarial
examples, Szegedy et al. demonstrated that such examples can be generated
using the limited-memory BFGS (L-BFGS) algorithm, which identifies an
adversarial example in an incorrect class with minimal $L_{2}$ norm distance
to the true data. Later, Goodfellow et al. proposed the fast gradient sign
method (FGSM), where the attacker starts with a clean image and takes small,
equal-sized steps in each dimension (i.e., alters each pixel by the same
amount) in the direction maximizing the loss [16]. Another proposed attack—the
Jacobian-based Saliency Map Attack (JSMA)—iteratively modifies the pixel with
the largest impact on the loss [33]. DeepFool, like L-BFGS, minimizes the
$L_{2}$ distance from the true instance while crossing a boundary into an
incorrect class, but does so quickly by approximating the classifier as
linear, stepping to maximize the loss, then correcting for the true
classification surface [29]. Like Nettack, these methods all try to maintain
closeness to the original data ($L_{2}$ norm for L-BFGS and DeepFool, $L_{0}$
norm for JSMA, and $L_{\infty}$ norm for FGSM).

Some of these methods have been adapted for use with graph data. In [44], the
authors modify FGSM and JSMA to use integrated gradients and show it to be
effective against vertex classification. In addition, new attacks against
vertex classification have been introduced, including a method that uses
reinforcement learning to identify modifications to graph structure for an
evasion attack [11]. To increase the scale of attacks, the authors of [23]
propose an attack that only considers a $k$-hop neighborhood of the target.
This method attacks a simplified GCN, introduced in [42], which applies a
logistic regression classifier after $k$ rounds of feature propagation.

Defenses to attacks such as FGSM and JSMA have been proposed, although several
prove to be insufficient against stronger attacks. A simple improvement is to
include adversarial examples in the training data [16]. Defensive distillation
is one such defense, in which a classifier is trained with high “temperature”
in the softmax, which is reduced for classification [34]. While this was
effective against the methods from [38, 16, 33, 29], it was shown in [4] that
modifying the attack by changing the constraint function (which ensures the
adversarial example is in a given class) renders this defense ineffective.
More defenses have been proposed, such as pixel deflection [36] and
randomization techniques [45], but many such methods are still found to be
vulnerable to attacks [1, 2]. Other work has focused on provably robust
defenses [41], with empirical performance often close to certifiable claims
[9]. Stochastic networks have also shown improved robustness to various
attacks [12]. In the wake of growing interest in adversarial robustness,
several authors in the community have aggregated best practices for evaluation
of systems in [5].

More recent work has focused on robustness of GCNs, including work on
robustness to attacks on attributes [54] and more robust GCN variants [49].
Multiple authors have considered aggregation techniques that are less
sensitive to outliers [15, 7]. One approach to a more robust classifier
incorporates an attention mechanism that learns the importance of the
attributes of other nodes’ features to a node’s class [40]. Others have
considered using a GCN with modified graph structure to improve robustness,
such as using a low-rank approximation for the graph [14] and filtering edges
based on attribute values [44]. Another method also considers attribute
values, in this case creating a similarity graph from the attributes that
augments the given graph structure to preserve node similarity in feature
space [19]. The low-rank structure and node similarity concepts are combined
in [21] to create a neural network that aims to simultaneously learn the true
graph structure from poisoned data and learn a classifier of unlabeled nodes.
The authors of [10] explore a similar idea in the context of noisy data and
few labels, using link prediction to augment the observed graph. Relations
between attribute similarity and node class—including possible heterophily—are
also exploited in GNNGuard [48]. More recent work has shown that attacks that
are adaptive to defenses easily undermine the robustness increase observed
when using non-adaptive attacks [30]. Other recent GCN developments include
modifications to deal with heterophily, via classifier design choices [51] and
by learning the level of homophily or heterophily in the graph as part of the
training procedure [50]. Several attacks [11, 52, 6, 53, 44, 46] and defenses
[16, 44, 49, 14, 21] have been incorporated into a software package called
DeepRobust, enabling convenient experimentation across a variety of conditions
[24, 20]. As with neural networks more generally, there has been work on
certifiable robustness for GCNs [3, 55].

While this paper is focused on targeted attacks, several attacks, such as [53,
46], attack the whole graph in order to degrade overall performance. Some
attacks in this area have allowed adding new nodes [37], flipping labels [25],
and rewiring edges [26]. In addition, there are many machine learning tasks on
graphs other than vertex classification, and work has been done on, for
example, edge classification in an adversarial context [47].

##  3 Problem Model

We consider the vertex classification problem as described in [52], where we
are given an undirected graph $G=(V,E)$ of size $N=|V|$ and an $N\times d$
matrix of vertex attributes $X$. Each node has an arbitrary numeric index from
1 to $N$. For this work, as in [52], we consider only binary attributes. In
addition to its $d$ attributes, each node has a label denoting its class. We
enumerate classes as integers from $1$ to $C$. Given a subset of labeled
instances, the goal is to correctly classify the unlabeled nodes.

The focus of [52] is on GCNs, which make use of the adjacency matrix for the
graph $A=\\{a_{ij}\\}$, where $a_{ij}$ is 1 if there is an edge between node
$i$ and node $j$ and is 0 otherwise. The GCN applies a symmetrized one-hop
graph convolution [22] to the input layer. That is, if we let $D$ be the
diagonal matrix of vertex degrees—i.e., the $i$th diagonal entry is the number
of edges connected to vertex $i$, $d_{ii}=\sum_{j=1}^{N}{a_{ij}}$—then the
output of the first layer of the network is expressed as

$H=\sigma\left(D^{-1/2}AD^{-1/2}XW_{1}\right),$ (1)

where $W_{1}$ is a weight matrix, $X$ is a feature matrix whose $i$th row is
$x_{i}^{T}$ (the attribute vector for row vertex $i$), and $\sigma$ is the
rectifier function. From the hidden layer to the output layer, a similar graph
convolution is performed, followed by a softmax output:

$Y=\mathrm{softmax}\left(D^{-1/2}AD^{-1/2}HW_{2}\right).\ $

The focus in [52] is on GCNs with a single hidden layer. Each vertex is then
classified according to the largest entry in the corresponding row of $Y$.

The vertex attack proposed in [52] operates on a surrogate model where the
rectifier function is replaced by a linear function, thus approximating the
overall network as

$\displaystyle Y$
$\displaystyle\approx\mathrm{softmax}\left(\left(D^{-1/2}AD^{-1/2}\right)^{2}XW_{1}W_{2}\right)$
(2)
$\displaystyle=\mathrm{softmax}\left(\left(D^{-1/2}AD^{-1/2}\right)^{2}XW\right).$

Nettack uses a greedy algorithm to determine how to perturb both $A$ and $X$
to make the GCN misclassify a target node. The changes are intended to be
“unnoticeable,” i.e., the degree distribution of $G$ and the co-occurrence of
features are changed negligibly. Using the approximation in (2), Nettack
perturbs by either adding or removing edges or turning off binary features so
that the classification margin is reduced the most at each step. Note that
while it can change the topology and the features, Nettack does _not_ change
the labels of any vertices. In this paper, we only consider structural
perturbations. Nettack allows either _direct_ attacks, in which the target
node itself has its edges and features changed, or indirect _influence_
attacks, where neighbors of the target have their data altered.

The classifier is evaluated in a context where only some of the labels are
known, and the labeled data are split into training and validation sets. To
train the GCN, 10% of the data are selected at random (or by one of the
alternative methods outlined in Section 4), and another 10% is selected for
validation. The remaining 80% is the test data. After training, nodes are
selected for attack among those that are correctly classified. The goal of the
defender is to make the a successful attack as expensive as possible.

As we discuss in Section 5, we also consider attacks other than Nettack, and
classifiers other than standard GCNs. While the details differ (e.g., using
different criteria to identify perturbations), the overall problem model
remains the same.

##  4 Proposed Methods

As we investigated classification performance using Nettack, we noted that
nodes in the test set with many neighbors in the training set were more likely
to be correctly classified. This dependence on labeled neighbors is consistent
with previous observations [31]. We observed this effect using the standard
method of training data selection used in the original Nettack paper: randomly
select 10% for training, 10% for validation, and 80% for testing. This
observation suggested that a training set where the held-out nodes are well
represented among neighborhoods of the training data—providing a kind of
“scaffolding” for the unlabeled data—could make the classification more
robust.

We considered two methods to test this hypothesis. The first simply chooses
the highest-degree nodes (stratified by class) to be in the training set. We
refer to the stratified degree-based thresholding method as StratDegree. The
other method uses a greedy approach in an attempt to ensure every node has at
least a minimal number of neighbors in the training set. Starting with an
empty training set and a threshold $k=0$, we iteratively add a node of a
particular class with the largest number of neighbors that are connected to at
most $k$ nodes in the training set. The class is randomly selected based on
how many nodes of each class are currently in the training set and the number
required to achieve class stratification. When there are no such neighbors, we
increment $k$. This procedure continues until we have the desired proportion
of the overall dataset for training. Algorithm 1 provides the pseudo-code.

Input: Graph $G=(V,E)$, training proportion $t\in(0,1)$, classes $C$, class
map $\textrm{class}:V\rightarrow C$

Output: Training set $T\subset V$

$k\leftarrow 0$

for all $u\in V$ do

$m_{u}\leftarrow 0$ $\langle\langle$number of neighbors in the training set:
initialize all nodes to 0$\rangle\rangle$

end for

for all $c\in C$ do

$\langle\langle$initialize vertex and training subsets partitioned by
class$\rangle\rangle$

$V_{c}\leftarrow\\{v\in V|\textrm{class}(v)=c\\}$

$T_{c}\leftarrow\emptyset$

end for

while $|T_{c}|<t|V_{c}|~{}\forall c\in C$ do

$c\leftarrow$ class selected with probability proportional to
$1-\frac{|T_{c}|}{t|V_{c}|}$

$v\leftarrow\operatorname*{arg\,max}_{u\in V_{c}\setminus
T_{c}}\sum_{u^{\prime}\in\mathcal{N}(u)}\mathbb{I}\left[m_{u^{\prime}}=k\right]$

if
$\sum_{u^{\prime}\in\mathcal{N}(v)}\mathbb{I}\left[m_{u^{\prime}}=k\right]=0$
then

$k\leftarrow k+1$ $\langle\langle$incr. min. num. trained
neighbors$\rangle\rangle$

else

$T_{c}\leftarrow T_{c}\cup\\{v\\}$

$T\leftarrow\bigcup_{c\in C}{T_{c}}$

$m_{v}\leftarrow-1$

for all $u^{\prime}\in\mathcal{N}(v)\setminus T$ do

$m_{u^{\prime}}\leftarrow m_{u^{\prime}}+1$

end for

end if

end while

return $T$

Algorithm 1 GreedyCover

###  4.1 Computational Complexity

Using StratDegree and GreedyCover both have computational costs beyond random
sampling. StratDegree requires finding the highest-degree nodes, which, for a
constant fraction of the dataset size, will require $O(|E|+|V|\log{|V|})$ time
(for computing degrees and sorting), compared to $O(|V|)$ time for random
sampling. Each step in GreedyCover requires finding the vertex with the most
neighbors minimally connected to the training set. As written in Algorithm 1,
each iteration requires $O(|E|)$ time to count the number of such neighbors
each node has, which would result in an overall running time of $O(|V||E|)$.
This could be improved using a priority queue—such as a Fibonacci heap—to
achieve $O(|E|+|V|\log{|V|})$ time ($O(|V|)$ logarithmic-time extractions of
the minimum and $O(|E|)$ constant-time key updates. Thus, the two proposed
method require moderate overhead compared to the running time for the GCN.

##  5 Experimental Setup

Each experiment in our study involves (1) a graph dataset, (2) a method for
selecting training data, (3) a structure-based attack against vertex
classification, and (4) a classification algorithm. We consider several
options for each step in this process, as shown in Figure 1. This section
details the methods and datasets we use across the experiments in this paper.
We use the DeepRobust library [24] for datasets, attacks, and classifiers.

Figure 1: Processing chain for experiments. Each experiment takes a dataset,
applies some method to split training, validation, and test data, applies an
attack to a set of target nodes, then applies a classifier to the attacked
dataset. We evaluate the robustness of vertex classification—-in terms of
required attacker budget at a given attack success rate—across all possible
combinations of dataset, selection methods, attacks, and classifier.

###  5.1 Datasets

We use the three datasets used in the Nettack paper in our experiments, plus
one larger citation dataset:

  * •

CiteSeer The CiteSeer dataset has 3312 scientific publications put into 6
classes. The network has 4732 links representing citations between the
publications. The features of the nodes contain 1s and 0s indicating the
presence of the word in the paper. There are 3703 unique words considered for
the dictionary.

  * •

Cora The Cora dataset consists of 2708 machine learning papers classified into
one of seven categories. The citation network consists of 5429 citations. For
each paper (vertex) in the network there is a feature vector of 0s and 1s for
whether it contains one of 1433 unique words.

  * •

PolBlogs The political blogs dataset consists of 1490 blogs labeled as either
liberal or conservative. A total of 19,025 links between blogs form the
directed edges of the graph. No attributes are used.

  * •

PubMed The PubMed dataset consists of 19,717 papers pertaining to diabetes
classified into one of three classes. The citation network consists of 44,338
citations. For each paper in the network there is a binary feature vector
representing the presence of 500 words.

###  5.2 Training Data Selection

To select training data, we use StratDegree and GreedyCover as described in
Section 4, as well as random selection. For StratDegree and GreedyCover, we
split use the proposed algorithms to select 10% of the data, stratified by
class. The remaining 90% of the data is randomly split (stratified by class)
into validation (10%) and training data (80%). For random selection, we also
want to determine whether adding more random training data improves
classification robustness. Thus, in addition to using stratified random
sampling to select 10% of the data for training, we consider larger training
sets, increasing to 30% in 5% increments. In all cases, 10% of the data are
used for validation and the remainder comprise the test set. We measure the
average number of neighbors connected to a node outside of the training set,
i.e., for the training set $T\subset V$, we record

$\frac{1}{\left|V\setminus T\right|}\sum_{i\in T}\sum_{j\in V\setminus
T}{a_{ij}}.$ (3)

This allows us to evaluate what impact the overall number of connections to
the training data has on performance, and whether performance with the
proposed training data selection methods match any trend observed with random
training.

###  5.3 Attacks

  * •

Nettack The method from [52], briefly described in Section 3.

  * •

Fast Gradient Attack (FGA) Computes the gradient of the loss function at the
target node with respect to the adjacency matrix, then perturb the entry with
the largest gradient that points in the correct direction [6].

  * •

Integrated Gradient Attack (IG-Attack) A similar method that integrates the
gradient as an entry in the adjacency matrix varies from 1 to 0 (for edge
removal) or 0 to 1 (for edge addition) [44].

  * •

Simplified Gradient Attack (SGA) In this case, gradients are computed that
only consider a $k$-hop subgraph around the target [23].

For direct attacks, we use up to 20 edge additions and removals for a target.
For influence attacks, we allow up to 50 perturbations.

###  5.4 Classifiers

We consider the following eight classifier models, some of which were
developed with the explicit intent of improving robustness to adversarial
attack:

  * •

GCN The original GCN architecture as used in [52].

  * •

Jaccard Before training the GCN, removes edges between nodes that have
dissimilar feature vectors before [43].

  * •

SVD Uses a GCN in which the adjacency matrix is replaced with a low-rank
approximation via truncated singular value decomposition [14].

  * •

ChebNet Uses the spectral graph convolutions [13] of which the convolution
operator (1) is a first-order approximation.

  * •

Simple Graph Convolution (SGC) Applies a model similar to the surrogate (2),
where the matrix $W$ is learned via logistic regression on the features
defined by $(D^{-1/2}AD^{-1/2})^{k}X$ [42].

  * •

Graph Attention Network (GAT) Includes an attention mechanism based on the
importance of each node’s neighbors’ features [40].

  * •

Robust Graph Convolutional Network (RGCN) Uses Gaussian convolutions, in which
the output is drawn from a Gaussian distribution whose parameters the output
of a neural network [49].

  * •

MedianGCN Aggregates neighbors’ features based on their median values rather
than weighted averages [7].

###  5.5 Training

We tuned classifier hyperparameters for each (classifier, attack, training
selection method) triple, first performing a coarse grid search over all
hyperparameters, then performing some refinements: altering each single
parameter 10% and choosing the configuration with the best performance. The
performance metric is a linear combination of the $F_{1}$ score (macro
averaged) before an attack takes place with the was the average margin of 10
randomly selected targets after 5 perturbations with a direct attack. The
resulting hyperparameters were used in all cases with the corresponding
classifier, attack, and training selection method.

###  5.6 Evaluation

We evaluate performance based on 25 target nodes. The targets are randomly
selected from the set of nodes that are correctly classified when no attack
takes place. This procedure is repeated five times with the
train/validation/test splits recomputed each time. Our robustness metric is
the adversary’s required budget to achieve a given attack success rate. We
compute this based on the number of perturbations required to give a target a
negative classification margin in its correct class. If the target is never
successfully misclassified, we set the required budget to the maximum number
of perturbations. The result is averaged across the five trials.

##  6 Results on Real Data

###  6.1 Impact of Training Methods

We first consider influence attacks, where the target node’s neighbors are
modified rather than the target itself. We apply both Nettack and FGA,
replacing Nettack with SGA if the SGC-based classifier is used. We only
obtained results using IG-FGSM on the PolBlogs dataset, which can be seen in
the appendix. (IG-FGSM did not substantially outperform the other methods for
the best-performing classifiers.) In all other cases, IG-FGSM did not finish
in the allotted time. Results are illustrated in Figure 2. In addition to
standard the results for standard GCNs, we plot the upper envelope for each
method: at a given attack success probability, the largest required budget
across all classifiers. See Appendix A for details about the performance of
each individual classifier with each training scheme. CiteSeer has a
particularly large increase in the attacker’s required budget when using
GreedyCover: more than doubling it over several rates of attack success. In
fact, at low attack success probabilities, GreedyCover with a GCN provides
similar robustness to any of the classifiers listed in Section 5.4 with random
selection. In addition, GreedyCover provides greater robustness when used in
conjunction with the most robust defenses, as shown by the upper envelope.
There is a somewhat milder effect on the Cora dataset. In this case,
GreedyCover still performs best when using Nettack, but the best performance
when attacked with FGA comes from StratDegree (though GreedyCover is within
one standard error). With PolBlogs, we also see a benefit from both methods,
though we start from a much higher baseline in terms of required
perturbations. We see an exception with PubMed, where random training performs
best. Looking deeper into the data, we see that the target nodes for random
data tend to have higher margins on the best-performing classifiers. In all
other cases, GreedyCover performs as well or better than the other training
set selection methods.

Figure 2: Robustness to influence attacks using GCNs (solid line) or with the
best defense at a given attack success probability (dash line). Results are
shown for the CiteSeer, Cora, PolBlogs, and PubMed datasets, each plotted in a
subsequent row, and using both the Nettack/SGA (left column) and FGA (right
column) attacks. Insufficient results were returned in the allotted time for
IG-FGSM on all datasets, and FGA for PubMed. Each curve represents the average
required budget over 25 randomly selected targets, and error bars are standard
errors. Higher is better for the defender. With the exception of the PubMed
dataset, GreedyCover performs at least as well as random training selection,
and often performs much better.

######  Observation 6.1.

Training with GreedyCover frequently outperforms other training methods, both
with GCNs and in conjunction with published defenses.

When considering direct attacks, we use all four attacks, again with SGA
replacing Nettack in the appropriate case. Results of these experiments are
shown in Figure 3. It is much more difficult to defend against direct attacks;
note that the attacker often only needs one or two perturbations to be
successful. With the CiteSeer dataset, we once again see higher robustness
with GreedyCover and StratDegree, in particular at low attack probabilities.
With Nettack and FGA, GreedyCover improves performance when combined with
other defenses. With IG-FGSM, on the other hand, the alternative training
methods provide little benefit. Across datasets, this attack also has the
lowest robustness across defenses, which would suggest it is a preferred
attack for adversaries. (Note that for CiteSeer, we only obtained data for a
GCN classifier when attacked with IG-FGSM when using GreedyCover.) We once
again see a detriment in performance with PubMed, though in this case in the
area where a perturbing a single edge results in an successful attack.

Figure 3: Robustness to direct attacks using GCNs (solid line) or with the
best defense at a given attack success probability (dash line). Results are
shown for the CiteSeer, Cora, PolBlogs, and PubMed datasets, attacked with
Nettack/SGA (left column), FGA (center column), and IG-FGSM (right column).
Insufficient results were returned in the allotted time for IG-FGSM and FGA on
the PubMed dataset, or for IG-FGSM on the CiteSeer dataset when using a GCN
with random training or StratDegree. Each curve represents the average
required budget over 25 randomly selected targets, and error bars are standard
errors. Higher is better for the defender. While GreedyCover performs better
when paired with defenses on CiteSeer when attacked with Nettack or FGA, the
alternative methods generally increase robustness less than with indirect
attacks.

######  Observation 6.2.

Direct attacks typically benefit less than influence attacks from the
alternative training methods.

###  6.2 Impact of Labeled Neighbors

One possibility we considered is that robustness from the alternative training
methods comes entirely from the average number of trained neighbors for nodes
in the test set. To test this possibility, we performed the same experiments
with more randomly selected training data, as described in Section 5.2.
Results of these experiments are shown in Figure 4, using Nettack as an
influence attack against a GCN. While using more randomly selected training
data does sometimes increase robustness, it is not consistent, and in some
cases more randomly selected training data is slightly less robust. The one
case where additional training data consistently outperforms GreedyCover in
terms of robustness is Cora, where training using 30% of the dataset, randomly
selected, outperforms the alternatives. In this case, the average number of
neighbors per target for GreedyCover and StratDegree are 1.084 and 1.135, both
between the values for 25% random training (1.029) and 30% (1.237). Thus,
increasing the number of neighbors in the training set by adding more randomly
selected training data does not necessarily increase classifier robustness to
the same extent.

Figure 4: Robustness to influence attacks using GCNs when training data are
selected using GreedyCover, StratDegree, or varying amounts of random
selection. Results are shown for the CiteSeer (upper left), Cora (upper
right), PolBlogs (lower left), and PubMed (lower right) datasets. Each curve
represents the average required budget over 25 randomly selected targets, and
error bars are standard errors. Higher is better for the defender. Of the
datasets where robustness improves using GreedyCover (i.e., CiteSeer, Cora,
and PolBlogs), the only case that consistently performs better than
GreedyCover is 30% random selection on the Cora dataset.

######  Observation 6.3.

Using more training data with random selection does not consistently lead to
higher robustness.

###  6.3 Robustness vs. Classification Performance

Another important consideration is whether increased robustness comes at the
expense of classification performance. In Figure 5, we show the macro-averaged
$F_{1}$ score for each method using all classifiers. Performance does
occasionally vary. In particular, StratDegree results in somewhat lower
performance than random training among most classifiers for all datasets.
GreedyCover, on the other hand, typically yields similar performance to random
selection and occasionally outperforms it, e.g., using SGC on CiteSeer and
ChebNet on Cora. This yields another datapoint in favor of GreedyCover: it
tends to yield the greatest robustness across datasets, and does not seem to
greatly hinder overall classification performance.

Figure 5: Classifier performance across datasets when training data are
selected using GreedyCover, StratDegree, or varying amounts of random
selection. Results are shown for the CiteSeer (upper left), Cora (upper
right), PolBlogs (lower left), and PubMed (lower right) datasets. Each bar
height represents the average $F_{1}$ score (macro averaged) across 5 separate
train/validation/test sets, and error bars are standard errors. Performance is
shown for each classifier where experiments completed within the allotted
time. Higher is better for the defender. While StratDegree often underperforms
random selection, GreedyCover typically shows similar performance.

######  Observation 6.4.

Using GreedyCover yields no consistent reduction in classification performance
compared to random training set selection.

###  6.4 Adaptive Attacks

In the image classification literature, numerous published defenses were found
to primarily rely on model obfuscation and remain vulnerable to adaptive
attacks that take the new model into account [1]. Recent work has raised
similar concerns regarding the robustness of published defenses against GNN
attacks [30]. If training set selection makes a classifier more robust, one
advantage is that it makes no changes to the model class, and thus should not
be vulnerable to such oversights.

We applied our training set selection methods to a demonstration provided by
Mujkanovic and Geisler et al.111Available at
https://github.com/LoadingByte/are-gnn-defenses-robust., which includes an
adaptive attack based on projected gradient descent (PGD) [46]. The code
applies the attack with the objective of reducing the overall classifier
accuracy. We applied the demo to the same datasets used by the
authors—CiteSeer and Cora—and achieved the results shown in Figure 6. While
the SVD-based method and GNNGuard are both effectively attacked by the PGD-
based method, using GreedyCover to select the training data (again using 10%
for training, 10% for validation, and 80% for testing) results in higher post-
attack accuracy for with both classifiers. As defenses to new adaptive methods
are published, it will be interesting to consider their use in conjunction
with alternative training set selection.

Figure 6: Performance using an adaptive attack for global poisoning with all
three training schemes. Results are shown in terms of overall classifier
accuracy using a GCN, an SVD-based GCN, and GNNGuard on the CiteSeer and Cora
datasets. Bars showing accuracy before poisoning is desaturated, while
accuracy after poisoning is solid. Higher accuracy is better for the defender.
In all cases, selecting training data using GreedyCover results in better
post-attack accuracy.

##  7 Simulation Study

The results on real data show that GreedyCover often provides greater
robustness to attack, but they are by no means conclusive. In the next
section, we further explore the methods with simulated data to observe
performance differences while controlling network properties.

###  7.1 Synthetic Dataset Generation

Synthetic network generation to evaluate network effects on the performance of
GNNs has recently received attention in the research community [32]. In this
section, we outline a set of simulations that consider four key features of
the network: degree distribution, level of clustering, homophily with respect
to labels, and information gained via node attributes.

####  7.1.1 Random Graph Models

We use five random graph models that exhibit different properties in terms of
clustering, degree distribution, and dependence on attributes. In each case,
we use 1200 nodes and an average degree of approximately 10.

  * •

Erdős–Rényi (ER) Graphs: Each pair of nodes shares an edge with probability
$1/120$. This model yields homogeneous degree distributions and very little
clustering.

  * •

Barabási–Albert (BA) Graphs: Each node enters the graph and connects 5 edges
to existing nodes with probability proportional to their degrees. The process
is initialized with a 6-node star. This model yields graphs with heterogeneous
degree distributions and very little clustering.

  * •

Watts–Strogatz (WS) Graphs: A ring lattice—where each node is connected to 5
nodes on either side—has 10% of its edges randomly rewired. This model yields
graphs with substantial clustering and homogeneous degree distributions.

  * •

Lancichinetti–Fortunato–Radicchi (LFR) Graphs: Generates a degree sequence
with degree distribution $p(d)\propto d^{-3},$ with average and minimum degree
set to $d_{\textrm{avg}}=10$ and $d_{\textrm{max}}=135$. Nodes are randomly
assigned to communities, whose sizes are distributed according to
$p(|C|)\propto|C|^{-2}$, with the minimum community size being 10. Nodes
create 80% of their connections within the community and 20% outside the
community.

If the generated graph has multiple connected components, we use the largest
connected component for the experiment.

####  7.1.2 Label Assignment

We assign labels with varying levels of homophily. For the “high homophily”
scenario, we partition the nodes based on the normalized graph Laplacian

$L=I-D^{-1/2}AD^{-1/2},$

where $A$ and $D$ are the adjacency matrix and diagonal degree matrix as in
Section 3 [8]. We select the eigenvector $u_{2}$ associated with the second-
smallest eigenvalue of $L$. The nodes associated with the $N/2$ entries in
$u_{2}$ with the smallest values (i.e., values closest to $-\infty$) are
labeled 0, and the other nodes are labeled 1. Let $V_{0}$ and $V_{1}$ be the
respective subsets of vertices.

For lower homophily graphs, we first compute the difference between the number
of within-label edges and the number of cross-label edges, i.e., letting
$E_{ij}$ be the set of edges between nodes in $V_{i}$ and nodes in $V_{j}$,

$\Delta=|E_{00}|+|E_{11}|-|E_{01}|.$ (4)

Depending on how homophilous we want the graph to be, we swap labels on pairs
of nodes until $\Delta$ reaches a given value, based on its value from the
initial Laplacian-based partition (e.g., half as homophilous as the original).
The node swapping mechanism is detailed in Algorithm 2.

Input: Graph $G=(V,E)$, vertex subsets $V_{0},V_{1}$

Output: Updated vertex subsets $\hat{V}_{0},\hat{V}_{1}$

$x_{i}\leftarrow\begin{cases}-1&\textrm{if }v_{i}\in V_{0}\\\ 1&\textrm{if
}v_{i}\in V_{1}\end{cases}$

$d\leftarrow Ax$

$p_{i}\leftarrow d_{i}\cdot\mathbb{I}[d_{i}>=0]\cdot\mathbb{I}[x_{i}>0]$

$u\leftarrow$ node randomly selected with probability
$p_{i}/\sum_{j=1}^{N}{p_{j}}$

$p_{i}\leftarrow d_{i}\mathbb{I}[d_{i}<0]\mathbb{I}[x_{i}<0]$

$v\leftarrow$ node randomly selected with probability
$p_{i}/\sum_{j=1}^{N}{p_{j}}$

$\hat{V}_{0}\leftarrow(V_{0}\cup\\{u\\})\setminus{v}$

$\hat{V}_{1}\leftarrow(V_{1}\cup\\{v\\})\setminus{u}$

return $\hat{V}_{0},\hat{V}_{1}$

Algorithm 2 Swap2Reduce

####  7.1.3 Synthetic Attributes

As with the real graphs, we consider binary attribute vectors on the nodes of
the synthetic graphs. In each case, we consider nodes with 100 attributes, and
we give each attribute a probability of being true depending on its label.
Probabilities are determined by an exponentially decreasing function. We
consider three scenarios. In the most difficult case, the probabilities are
the same for both classes. As we make the problem easier, we shift the
function that determines the attribute probabilities so that high-probability
attributes in class 0 still have _relatively_ high probabilities class 0, but
there is not a perfect match. The shifts were chosen to create cases where a
generalized likelihood ratio test (with each attribute having an independent
probability parameter, estimated based on 60 cases for each class) achieves
accuracy of approximately $0.5$, $0.7$, and $0.9$. We refer to these cases as
having _uninformative_ , _moderately informative_ , and _highly informative_
attributes, respectively. In addition, each node has a one-hot encoded
attribute indicating its index in the node set.

###  7.2 Results

For all synthetic topologies, we ran experiments using Nettack perform an
influence attack against a GCN trained with data selected by all three
methods. Robustness results for ER, BA, WS, and LFR graphs are shown in Figure
7. When no attributes are used and homophily is high, we see a much larger
performance difference using GreedyCover than StratDegree in the WS graphs,
but the two methods yield more similar performance with the other models. For
all models, as homophily decreases, the performance improvement gets more
modest as homophily decreases.

When attributes with the same distribution are added to both classes (i.e.,
the case of “uninformative” attributes), robustness suffers in most cases. The
LFR graphs in particular see a large decrease in robustness using random
selection, with a much smaller decrease using the alternative methods. As
feature distributions become more distinct between the classes, the difference
between the methods becomes smaller, suggesting that the robustness
improvements we observe are likely due to structural considerations. With
highly informative attributes, we note that the models with homogeneous degree
distributions still gain a benefit from StratDegree and GreedyCover when
homophily is low, while the models with heterogeneous degree distributions are
somewhat hindered by these methods. Like in the real data, this is because the
targets have higher margins in the case of random training selection. This may
happen due to low-degree nodes, which tend to connect to high-degree nodes:
When homophily is low, nodes may become more difficult to predict based on
their proximity to hubs, and are _less_ likely to be selected to be labeled.
We summarize our observations here as follows:

Figure 7: Robustness to influence attacks against GCNs on simulated data.
Results are shown for ER (first column), BA (second column), WS (third
column), and LFR (fourth column) graphs, in cases with no attributes (first
row), uninformative attributes (second row), moderately informative attributes
(third row), and highly informative attributes (fourth row). Each curve
represents the average required budget over 25 randomly selected targets, and
error bars are standard errors. Higher is better for the defender. Results are
shown for high homophily (solid line) and low homophily (dash line) cases. As
attributes become more helpful in classification, the advantage gained by the
alternative training methods is substantially reduced.

######  Observation 7.1.

With no attributes and high homophily, all models gain robustness from the
alternative methods.

######  Observation 7.2.

With no attributes and low homophily, GreedyCover provides robustness for all
models, while for BA and LFR, StratDegree improves robustness only at higher
attack success rates.

######  Observation 7.3.

The increase in robustness for the alternative methods decreases as homophily
decreases and as attributes become better class predictors.

######  Observation 7.4.

With highly informative attributes and low homophily, GreedyCover and
StratDegree maintain some increased robustness for homogeneous degree
distributions, while they somewhat hinder performance for heterogeneous ones.

We consider the potential impact of the alternative training data on
classifier performance as well. Results are shown in Figure 8. Since we use
two balanced classes in all cases, we use accuracy as the classification
metric. For each case, we plot accuracy as a function of _heterophilicity_
[35], computed as

$H=\frac{\\#\\{\textrm{edges between $V_{0}$ and
$V_{1}$}\\}}{|V_{0}||V_{1}|M/\binom{N}{2}}.$ (5)

The denominator in (5) is the expected number of edges between $V_{0}$ and
$V_{1}$ after random rewiring. A high-homophily graph will have relatively low
heterophilicity. Note that both ER and BA graphs span the same range of
heterophilicity, while LFR graph can achieve lower heterophilicity and WS can
be almost perfectly homophilous. When no attributes are used, performance is
similar across methods in the high-homophily (low-heterophilicity) cases,
while the alternative methods perform worse in the low-homophily cases. This
yields a significant gap in the in the cases with skewed degree distributions.
In particular, LFR graphs maintain 75% accuracy with random training even in
the case where there is no homophily (heterophilicity is 1). As in the
analogous results in Figure 7, this may be due to low-degree nodes that are
unlikely to be chosen as training data, but are more difficult to classify in
a less homogeneous setting.

Figure 8: Classification accuracy as a function of heterophilicity using GCNs
on simulated data. Results are shown for ER (first column), BA (second
column), WS (third column), and LFR (fourth column) graphs, in cases with no
attributes (first row), uninformative attributes (second row), moderately
informative attributes (third row), and highly informative attributes (fourth
row). Each curve represents the average required budget over 5
train/validation/test splits, and error bars are standard errors. Higher is
better for the defender. The principal performance differences occur with
skewed degree distributions when homophily is low.

As attributes are added to the graphs, we see a decrease in performance when
the uninformative attributes are added, though the difference is very small
using GreedyCover for the clustered models. As we expect, accuracy increases
as the attributes become more informative. As we observed in the robustness
results, we see differences between methods diminish as attributes help
discriminate the classes.

######  Observation 7.5.

Graphs with skewed degree distributions and low homophily achieve lower
accuracy with GreedyCover and StratDegree than random selection, but
performance is similar in other cases.

######  Observation 7.6.

For higher homophily graphs, performance differences between methods decrease
as attributes become more informative.

When heterophilicity is approximately 1, accuracy is very low without
informative attributes. Considering cases where there is at least some
homophily and at least moderately informative attributes, the simulation
results where robustness does not improve with StratDegree or GreedyCover are
summarized in Table 1. As shown in the table, the cases where there is no
improvement all have heterogeneous degree distributions, while the homogeneous
degree distributions always have some improvement in robustness when
attributes are at least moderately informative. In addition, the low homophily
cases result in lower accuracy with the alternative methods. Note also that
more informative attributes and lower clustering coefficient hinder the
performance benefit.

Table 1: Summary of cases where StratDegree and GreedyCover do not improve
robustness when using informative attributes on synthetic graphs. The
alternative methods are considered less robust than random training selection
if the adversary’s budget decreases by at least 1 standard deviation for at
least 10 out of 20 points on the associated curve in Figure 7 (attack success
probability in multiples of 0.05). They are considered to be similarly robust
if the budget is within 1 standard deviation of for over 10 such points. For
accuracy, the alternative methods result in lower accuracy if the average
accuracy in Figure 8 decreases by at least 3% and similar accuracy if it is
within 3%. All cases in the table have heterogeneous degree distributions. All
cases with lower accuracy have low homophily. The improvement from the
alternatives is also degraded as attributes become more informative (from 70%
to 90% accuracy based on attributes alone) and clustering coefficient
decreases.

Relating the synthetic data to the real datasets, recall that StratDegree and
GreedyCover both failed to provide consistent improvement for PubMed, and
struggled with direct attacks against PolBlogs. Looking into the features of
these datasets, two points of interest are that PolBlogs has an especially
heavy-tailed degree distribution: there are many nodes with hundreds of edges,
which is rare in the other datasets. In addition, the PubMed dataset has node
attributes that are very useful in identifying the class of the nodes: a
support vector machine with a radial basis function kernel trained on the
attribute vectors alone (50% of the nodes used for training), the $F_{1}$
score (macro averaged) for the Cora dataset is approximately 0.71, for
CiteSeer is approximately 0.75, and for PubMed is about 0.87. As with the
synthetic data, the cases with the most informative node attributes are
hindered by the alternative training methods.

##  8 Conclusions

This paper explores the impact of complex network characteristics on the
robustness of vertex classification using GCNs. In particular, we consider
various scenarios regarding the structural relationship between the training
data and the remainder of the network. We consider selecting training data
using alternatives to random selection: using the highest degree nodes
(StratDegree) and using nodes that result in more connections to training
nodes from the test set (GreedyCover). We see the greatest improvement using
GreedyCover against influence attacks, though there are improvements in other
cases as well. With direct attacks via IG-Attack, on the other hand,
performance is similar across methods, and robustness in the best case (or
worst case for the defender) is lower than with the other attacks. We show
that the robustness achieved against Nettack with the alternative training
methods is not replicated through increasing the amount of randomly selected
training data, and that there is no significant tradeoff between classifier
performance and robustness using GreedyCover. In addition, we test StratDegree
and GreedyCover against an adaptive global poisoning attack and show that
GreedyCover yields better post-attack accuracy than random training.

In simulation, we see other interesting phenomena in the context of influence
attacks: GreedyCover increases robustness against Nettack for a diverse set of
topologies when label homophily is high and there are no node attributes. We
find that GreedyCover and StratDegree cease to be helpful when homophily is
very low and degree distributions are heterogeneous, perhaps because there are
fewer labels on low-degree nodes that attach to hubs. In all cases, variation
between training selection methods becomes less pronounced as node attributes
become more helpful in discriminating between classes.

The work documented here points to several open problems and avenues of
potential investigation. First, it is interesting that the integrated gradient
method is consistently the strongest attack against real data, regardless of
how training data are selected. Determining whether some network phenomenon
can be exploited to improve robustness against these attacks would be an
interesting topic for future work. Considering additional models for
topologies and attributes could yield additional insight into where the
various methods perform best, with Google’s GraphWorld being an important
enabling technology [32]. Another interesting question is whether there are
certain topology–attribute combinations where there is a true tradeoff between
robustness and classification performance. Identifying such cases—in the
spirit of [39], focused on graph data—would be important to understand what
could make classification inherently vulnerable to attack. Another potential
area to consider is detectability. Attackers try to hide their manipulation of
the data; what would be necessary to determine that an attack has been
performed on a graph? For example, we observed that direct attacks from
Nettack increase triangle count [27]. There may be other network statistics
that tend to change when an attack is carried out. These are all interesting
questions to consider as the research community continues to expand its
knowledge of vulnerability and robustness in graph machine learning.

## Acknowledgement

The authors wish to thank Mustafa Çamurcu and Alexander J. Gomez for their
assistance with the initial experiments on StratDegree and GreedyCover.

## References

  * [1] Anish Athalye and Nicholas Carlini.  On the robustness of the CVPR 2018 white-box adversarial example defenses.  CoRR, abs/1804.03286, 2018.
  * [2] Anish Athalye, Nicholas Carlini, and David Wagner.  Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples.  In ICML, pages 274–283, 2018.
  * [3] Aleksandar Bojchevski and Stephan Günnemann.  Certifiable robustness to graph perturbations.  In NeurIPS, pages 8317–8328, 2019.
  * [4] N. Carlini and D. Wagner.  Towards evaluating the robustness of neural networks.  In SP, pages 39–57, 2017.
  * [5] Nicholas Carlini et al.  On evaluating adversarial robustness.  arXiv preprint arXiv:1902.06705, 2019.
  * [6] Jinyin Chen, Yangyang Wu, Xuanheng Xu, Yixian Chen, Haibin Zheng, and Qi Xuan.  Fast gradient attack on network embedding.  arXiv preprint arXiv:1809.02797, 2018.
  * [7] Liang Chen, Jintang Li, Qibiao Peng, Yang Liu, Zibin Zheng, and Carl Yang.  Understanding structural vulnerability in graph convolutional networks.  In IJCAI, 2021.
  * [8] Fan RK Chung.  Spectral Graph Theory.  American Mathematical Soc., 1997.
  * [9] Francesco Croce, Maksym Andriushchenko, and Matthias Hein.  Provable robustness of relu networks via maximization of linear regions.  In AISTATS, pages 2057–2066, 2019.
  * [10] Enyan Dai, Wei Jin, Hui Liu, and Suhang Wang.  Towards robust graph neural networks for noisy graphs with sparse labels.  In WSDM, page 181–191, 2022.
  * [11] Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song.  Adversarial attack on graph structured data.  In ICML, pages 1115–1124, 2018.
  * [12] Joel Dapello, Jenelle Feather, Hang Le, Tiago Marques, David Cox, Josh McDermott, James J DiCarlo, and Sueyeon Chung.  Neural population geometry reveals the role of stochasticity in robust perception.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 15595–15607. Curran Associates, Inc., 2021.
  * [13] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst.  Convolutional neural networks on graphs with fast localized spectral filtering.  In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, NeurIPS, volume 29, 2016.
  * [14] Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalexakis.  All you need is low (rank): Defending against adversarial attacks on graphs.  In WSDM, pages 169–177, 2020.
  * [15] Simon Geisler, Daniel Zügner, and Stephan Günnemann.  Reliable graph neural networks via robust aggregation.  In NeurIPS, pages 13272–13284, 2020.
  * [16] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  In ICLR, 2015.
  * [17] William L. Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In NeurIPS, pages 1025–1035, 2017.
  * [18] Robin Jia and Percy Liang.  Adversarial examples for evaluating reading comprehension systems.  In EMNLP, pages 2021–2031, 2017.
  * [19] Wei Jin, Tyler Derr, Yiqi Wang, Yao Ma, Zitao Liu, and Jiliang Tang.  Node similarity preserving graph convolutional networks.  In WSDM, pages 148–156, 2021.
  * [20] Wei Jin, Yaxin Li, Han Xu, Yiqi Wang, Shuiwang Ji, Charu Aggarwal, and Jiliang Tang.  Adversarial attacks and defenses on graphs: A review, a tool and empirical studies.  arXiv preprint arXiv:2003.00653, 2020.
  * [21] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang.  Graph structure learning for robust graph neural networks.  In KDD, pages 66–74, 2020.
  * [22] Thomas N. Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In ICLR, 2017.
  * [23] Jintang Li, Tao Xie, Chen Liang, Fenfang Xie, Xiangnan He, and Zibin Zheng.  Adversarial attack on large scale graph.  IEEE Transactions on Knowledge and Data Engineering, 2021.
  * [24] Yaxin Li, Wei Jin, Han Xu, and Jiliang Tang.  DeepRobust: A PyTorch library for adversarial attacks and defenses.  arXiv preprint arXiv:2005.06149, 2020.
  * [25] Xuanqing Liu, Si Si, Jerry Zhu, Yang Li, and Cho-Jui Hsieh.  A unified framework for data poisoning attack to graph-based semi-supervised learning.  NeurIPS, 2019.
  * [26] Yao Ma, Suhang Wang, Tyler Derr, Lingfei Wu, and Jiliang Tang.  Attacking graph convolutional networks via rewiring.  arXiv preprint arXiv:1906.03750, 2019.
  * [27] Benjamin A. Miller, Mustafa Çamurcu, Alexander J. Gomez, Kevin Chan, and Tina Eliassi-Rad.  Improving robustness to attacks against vertex classification.  In MLG Workshop, 2019.
  * [28] John Moore and Jennifer Neville.  Deep collective inference.  In AAAI, pages 2364–2372, 2017.
  * [29] Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, and Pascal Frossard.  Deepfool: A simple and accurate method to fool deep neural networks.  In CVPR, pages 2574–2582, 2016.
  * [30] Felix Mujkanovic, Simon Geisler, Stephan Günnemann, and Aleksandar Bojchevski.  Are defenses for graph neural networks robust?  In NeurIPS, 2022.
  * [31] J. Neville, B. Gallagher, and T. Eliassi-Rad.  Evaluating statistical tests for within-network classifiers of relational data.  In ICDM, pages 397–406, 2009.
  * [32] John Palowitch, Anton Tsitsulin, Brandon Mayer, and Bryan Perozzi.  GraphWorld: Fake graphs bring real insights for GNNs.  In KDD, pages 3691–3701, 2022.
  * [33] N. Papernot, P. McDaniel, S. Jha, M. Fredrikson, Z. B. Celik, and A. Swami.  The limitations of deep learning in adversarial settings.  In EuroSP, pages 372–387, 2016.
  * [34] N. Papernot, P. McDaniel, X. Wu, S. Jha, and A. Swami.  Distillation as a defense to adversarial perturbations against deep neural networks.  In SP, pages 582–597, 2016.
  * [35] Juyong Park and Albert-László Barabási.  Distribution of node characteristics in complex networks.  Proceedings of the National Academy of Sciences, 104(46):17916–17920, 2007.
  * [36] Aaditya Prakash, Nick Moran, Solomon Garber, Antonella DiLillo, and James Storer.  Deflecting adversarial attacks with pixel deflection.  In CVPR, pages 8571–8580, 2018.
  * [37] Yiwei Sun, Suhang Wang, Xianfeng Tang, Tsung-Yu Hsieh, and Vasant Honavar.  Node injection attacks on graphs via reinforcement learning.  arXiv preprint arXiv:1909.06543, 2019.
  * [38] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  In ICLR, 2014.
  * [39] Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry.  Robustness may be at odds with accuracy.  In ICLR, 2019.
  * [40] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.  Graph attention networks.  In ICLR, 2018.
  * [41] Eric Wong and Zico Kolter.  Provable defenses against adversarial examples via the convex outer adversarial polytope.  In ICML, pages 5286–5295, 2018.
  * [42] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger.  Simplifying graph convolutional networks.  In ICML, pages 6861–6871, 2019.
  * [43] Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu.  Adversarial examples for graph data: Deep insights into attack and defense.  In IJCAI, pages 4816–4823, 2019.
  * [44] Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu.  Adversarial examples for graph data: Deep insights into attack and defense.  In IJCAI, pages 4816–4823, 2019.
  * [45] Cihang Xie, Jianyu Wang, Zhishuai Zhang, Zhou Ren, and Alan Yuille.  Mitigating adversarial effects through randomization.  In ICLR, 2018.
  * [46] Kaidi Xu, Hongge Chen, Sijia Liu, Pin-Yu Chen, Tsui-Wei Weng, Mingyi Hong, and Xue Lin.  Topology attack and defense for graph neural networks: an optimization perspective.  In IJCAI, pages 3961–3967, 2019.
  * [47] Sixie Yu, Yevgeniy Vorobeychik, and Scott Alfeld.  Adversarial classification on social networks.  In AAMAS, pages 211–219, 2018.
  * [48] Xiang Zhang and Marinka Zitnik.  GNNGuard: Defending graph neural networks against adversarial attacks.  In NeurIPS, pages 9263–9275, 2020.
  * [49] Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu.  Robust graph convolutional networks against adversarial attacks.  In KDD, pages 1399–1407, 2019.
  * [50] Jiong Zhu, Ryan A Rossi, Anup B Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra.  Graph neural networks with heterophily.  In AAAI, pages 11168–11176, 2021.
  * [51] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra.  Beyond homophily in graph neural networks: Current limitations and effective designs.  In NeurIPS, pages 7793–7804, 2020.
  * [52] Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann.  Adversarial attacks on neural networks for graph data.  In KDD, pages 2847–2856, 2018.
  * [53] Daniel Zügner and Stephan Günnemann.  Adversarial attacks on graph neural networks via meta learning.  In ICLR, 2019.
  * [54] Daniel Zügner and Stephan Günnemann.  Certifiable robustness and robust training for graph convolutional networks.  In KDD, pages 246–256, 2019.
  * [55] Daniel Zügner and Stephan Günnemann.  Certifiable robustness of graph convolutional networks under structure perturbations.  In KDD, pages 1656–1665, 2020.

##  Appendix A Extended Experimental Results

We present results for each classifier at various attacker budgets, and
highlight the best-performing pairing of a classifier with a training data
selection method. Results on influence attacks for CiteSeer, Cora, Polblogs,
and PubMed are in Tables 2, 3, 4, and 5, respectively. Results for direct
attacks are likewise in Tables 6, Tables 7, Tables 8, Tables 9. As we saw in
Section 6.1, GreedyCover and StratDegree perform best for CiteSeer and Cora,
and for PolBlogs in the case of influence attacks.

Table 2: Results of influence attacks against each classifier with the CiteSeer dataset, with attacker budgets of 10, 30, and 50 edge perturbations. Results are included for Nettack (Net), FGA, and IG-FGSM (IG). For each classifier, we train with random (Rand.), StratDegree (SD), and GreedyCover (GC). Each entry is a probability of attack success, thus higher is better for the attacker and lower is better for the defender. To yield the most robust classifier, the defender picks the classifier/training method combination that minimizes the worst-case attack probability. These entries are listed in bold. Entries representing the most robust case for random training are in italic. Entries listed as N/A did not finish in the allotted time. The Jaccard-based classifier performs best, both overall (with GreedyCover) and using random training. |  | Budget 10 | Budget 30 | Budget 50
---|---|---|---|---
defense | train. | Net | FGA | IG | Net | FGA | IG | Net | FGA | IG
Jaccard | Rand. | 0.248 | 0.224 | N/A | 0.432 | 0.336 | N/A | 0.504 | 0.408 | N/A
Jaccard | SD | 0.28 | 0.24 | N/A | 0.4 | 0.36 | N/A | 0.448 | 0.368 | N/A
Jaccard | GC | 0.152 | 0.168 | N/A | 0.176 | 0.288 | N/A | 0.192 | 0.36 | N/A
RGCN | Rand. | 0.752 | 0.696 | N/A | 0.944 | 0.84 | N/A | 0.976 | 0.904 | N/A
RGCN | SD | 0.504 | 0.328 | N/A | 0.768 | 0.592 | N/A | 0.816 | 0.744 | N/A
RGCN | GC | 0.448 | 0.384 | N/A | 0.864 | 0.76 | N/A | 0.952 | 0.824 | N/A
Cheb | Rand. | 0.304 | 0.384 | N/A | 0.496 | 0.464 | N/A | 0.552 | 0.544 | N/A
Cheb | SD | 0.32 | 0.352 | N/A | 0.464 | 0.432 | N/A | 0.52 | 0.496 | N/A
Cheb | GC | 0.352 | 0.272 | N/A | 0.52 | 0.424 | N/A | 0.552 | 0.512 | N/A
SVD | Rand. | 0.536 | 0.424 | N/A | 0.816 | 0.696 | N/A | 0.904 | 0.88 | N/A
SVD | SD | 0.624 | 0.6 | N/A | 0.912 | 0.776 | N/A | 0.968 | 0.928 | N/A
SVD | GC | 0.344 | 0.376 | N/A | 0.624 | 0.6 | N/A | 0.808 | 0.688 | N/A
median | Rand. | 0.584 | 0.44 | N/A | 0.816 | 0.84 | N/A | 0.864 | 0.88 | N/A
median | SD | 0.424 | 0.376 | N/A | 0.8 | 0.784 | N/A | 0.88 | 0.912 | N/A
median | GC | 0.392 | 0.304 | N/A | 0.768 | 0.768 | N/A | 0.88 | 0.864 | N/A
GAT | Rand. | 0.624 | 0.568 | N/A | 0.928 | 0.848 | N/A | 0.976 | 0.936 | N/A
GAT | SD | 0.552 | 0.392 | N/A | 0.816 | 0.728 | N/A | 0.912 | 0.896 | N/A
GAT | GC | 0.424 | 0.328 | N/A | 0.864 | 0.752 | N/A | 0.936 | 0.888 | N/A
GCN | Rand. | 0.68 | 0.568 | N/A | 0.848 | 0.856 | N/A | 0.872 | 0.904 | N/A
GCN | SD | 0.472 | 0.464 | N/A | 0.792 | 0.728 | N/A | 0.84 | 0.768 | N/A
GCN | GC | 0.408 | 0.368 | N/A | 0.728 | 0.768 | N/A | 0.832 | 0.872 | N/A
SGC | Rand. | 0.616 | N/A | N/A | 0.824 | N/A | N/A | 0.872 | N/A | N/A
SGC | SD | 0.696 | N/A | N/A | 0.8 | N/A | N/A | 0.816 | N/A | N/A
SGC | GC | 0.6 | N/A | N/A | 0.824 | N/A | N/A | 0.912 | N/A | N/A
Table 3: Results of influence attacks against each classifier with the Cora dataset, with attacker budgets of 10, 30, and 50 edge perturbations. Results are included for Nettack (Net), FGA, and IG-FGSM (IG). For each classifier, we train with random (Rand.), StratDegree (SD), and GreedyCover (GC). Each entry is a probability of attack success, thus higher is better for the attacker and lower is better for the defender. To yield the most robust classifier, the defender picks the classifier/training method combination that minimizes the worst-case attack probability. These entries are listed in bold. Entries representing the most robust case for random training are in italic. Entries listed as N/A did not finish in the allotted time. The Jaccard-based classifier performs best, both overall and using random training. If we focus on classifiers that achieve the best performance in Figure 5, (i.e., omitting Jaccard and SVD), the best performance is achieved by GCNs with the alternative training methods. |  | Budget 10 | Budget 30 | Budget 50
---|---|---|---|---
defense | training | Net | FGA | IG | Net | FGA | IG | Net | FGA | IG
Jaccard | Rand. | 0.296 | 0.24 | N/A | 0.472 | 0.432 | N/A | 0.592 | 0.504 | N/A
Jaccard | SD | 0.264 | 0.192 | N/A | 0.352 | 0.312 | N/A | 0.4 | 0.424 | N/A
Jaccard | GC | 0.224 | 0.256 | N/A | 0.36 | 0.392 | N/A | 0.448 | 0.456 | N/A
RGCN | Rand. | 0.68 | 0.6 | N/A | 0.912 | 0.944 | N/A | 0.952 | 0.976 | N/A
RGCN | SD | 0.448 | 0.408 | N/A | 0.848 | 0.784 | N/A | 0.904 | 0.888 | N/A
RGCN | GC | 0.44 | 0.296 | N/A | 0.832 | 0.808 | N/A | 0.92 | 0.888 | N/A
Cheb | Rand. | 0.448 | 0.448 | N/A | 0.784 | 0.808 | N/A | 0.872 | 0.896 | N/A
Cheb | SD | 0.656 | 0.48 | N/A | 0.976 | 0.816 | N/A | 0.976 | 0.912 | N/A
Cheb | GC | 0.488 | 0.448 | N/A | 0.864 | 0.88 | N/A | 0.928 | 0.912 | N/A
SVD | Rand. | 0.224 | 0.32 | N/A | 0.536 | 0.72 | N/A | 0.76 | 0.872 | N/A
SVD | SD | 0.296 | 0.216 | N/A | 0.568 | 0.536 | N/A | 0.76 | 0.728 | N/A
SVD | GC | 0.264 | 0.264 | N/A | 0.584 | 0.528 | N/A | 0.84 | 0.768 | N/A
median | Rand. | 0.544 | 0.424 | N/A | 0.872 | 0.808 | N/A | 0.944 | 0.912 | N/A
median | SD | 0.4 | 0.424 | N/A | 0.8 | 0.784 | N/A | 0.912 | 0.888 | N/A
median | GC | 0.24 | 0.312 | N/A | 0.784 | 0.84 | N/A | 0.896 | 0.912 | N/A
GAT | Rand. | 0.544 | 0.552 | N/A | 0.904 | 0.88 | N/A | 0.96 | 0.952 | N/A
GAT | SD | 0.608 | 0.48 | N/A | 0.88 | 0.816 | N/A | 0.968 | 0.872 | N/A
GAT | GC | 0.48 | 0.352 | N/A | 0.872 | 0.768 | N/A | 0.952 | 0.952 | N/A
GCN | Rand. | 0.568 | 0.448 | N/A | 0.896 | 0.896 | N/A | 0.936 | 0.952 | N/A
GCN | SD | 0.456 | 0.32 | N/A | 0.752 | 0.696 | N/A | 0.856 | 0.872 | N/A
GCN | GC | 0.384 | 0.32 | N/A | 0.816 | 0.776 | N/A | 0.896 | 0.896 | N/A
SGC | Rand. | 0.568 | N/A | N/A | 0.824 | N/A | N/A | 0.888 | N/A | N/A
SGC | SD | 0.632 | N/A | N/A | 0.84 | N/A | N/A | 0.856 | N/A | N/A
SGC | GC | 0.584 | N/A | N/A | 0.824 | N/A | N/A | 0.88 | N/A | N/A
Table 4: Results of influence attacks against each classifier with the PolBlogs dataset, with attacker budgets of 10, 30, and 50 edge perturbations. Results are included for Nettack (Net), FGA, and IG-FGSM (IG). For each classifier, we train with random (Rand.), StratDegree (SD), and GreedyCover (GC). Each entry is a probability of attack success, thus higher is better for the attacker and lower is better for the defender. To yield the most robust classifier, the defender picks the classifier/training method combination that minimizes the worst-case attack probability. These entries are listed in bold. Entries representing the most robust case for random training are in italic. Entries listed as N/A did not finish in the allotted time. Best results overall and with random training are achieved with SVD, while RGCN performs equally well when using StratDegree. |  | Budget 10 | Budget 30 | Budget 50
---|---|---|---|---
defense | training | Net | FGA | IG | Net | FGA | IG | Net | FGA | IG
Jaccard | Rand. | 0.92 | 0.872 | 0.928 | 0.992 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0
Jaccard | SD | 0.928 | 0.984 | 0.936 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0
Jaccard | GC | 0.936 | 0.952 | 0.944 | 0.992 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0
RGCN | Rand. | 0.08 | 0.128 | 0.032 | 0.224 | 0.248 | 0.056 | 0.32 | 0.304 | 0.064
RGCN | SD | 0.048 | 0.024 | 0.016 | 0.088 | 0.072 | 0.056 | 0.112 | 0.096 | 0.064
RGCN | GC | 0.088 | 0.096 | 0.04 | 0.192 | 0.176 | 0.048 | 0.232 | 0.272 | 0.056
Cheb | Rand. | 0.048 | 0.184 | 0.112 | 0.184 | 0.376 | 0.176 | 0.296 | 0.456 | 0.216
Cheb | SD | 0.128 | 0.128 | 0.168 | 0.256 | 0.232 | 0.288 | 0.368 | 0.32 | 0.336
Cheb | GC | 0.344 | 0.08 | 0.168 | 0.456 | 0.208 | 0.328 | 0.52 | 0.288 | 0.392
SVD | Rand. | 0.016 | 0.08 | 0.048 | 0.04 | 0.12 | 0.096 | 0.112 | 0.136 | 0.128
SVD | SD | 0.064 | 0.024 | 0.064 | 0.088 | 0.024 | 0.072 | 0.112 | 0.032 | 0.096
SVD | GC | 0.04 | 0.04 | 0.048 | 0.088 | 0.064 | 0.08 | 0.104 | 0.112 | 0.128
GAT | Rand. | 0.224 | 0.224 | 0.184 | 0.384 | 0.408 | 0.248 | 0.448 | 0.488 | 0.304
GAT | SD | 0.12 | 0.056 | 0.08 | 0.184 | 0.16 | 0.152 | 0.256 | 0.208 | 0.208
GAT | GC | 0.112 | 0.12 | 0.064 | 0.2 | 0.256 | 0.152 | 0.288 | 0.296 | 0.168
GCN | Rand. | 0.16 | 0.208 | 0.128 | 0.288 | 0.368 | 0.2 | 0.344 | 0.424 | 0.232
GCN | SD | 0.104 | 0.096 | 0.176 | 0.168 | 0.208 | 0.248 | 0.208 | 0.288 | 0.312
GCN | GC | 0.072 | 0.032 | 0.056 | 0.152 | 0.184 | 0.104 | 0.28 | 0.296 | 0.128
SGC | Rand. | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A
SGC | SD | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A
SGC | GC | 0.056 | N/A | N/A | 0.12 | N/A | N/A | 0.168 | N/A | N/A
Table 5: Results of influence attacks against each classifier with the PubMed dataset, with attacker budgets of 10, 30, and 50 edge perturbations. Results are included for Nettack (Net), FGA, and IG-FGSM (IG). For each classifier, we train with random (Rand.), StratDegree (SD), and GreedyCover (GC). Each entry is a probability of attack success, thus higher is better for the attacker and lower is better for the defender. To yield the most robust classifier, the defender picks the classifier/training method combination that minimizes the worst-case attack probability. These entries are listed in bold. Entries listed as N/A did not finish in the allotted time. Only results using Jaccard, GCN, and ChebNet were obtained in time. While StratDegree and GreedyCover improve performance with the Jaccard-based classifier, the best performance is achieved by a ChebNet classifier with random training. In our experiments, this classifier with the PubMed data typically has a much higher margin before the attack takes place. |  | Budget 10 | Budget 30 | Budget 50
---|---|---|---|---
defense | training | Net | FGA | IG | Net | FGA | IG | Net | FGA | IG
Jaccard | Rand. | 0.224 | N/A | N/A | 0.576 | N/A | N/A | 0.744 | N/A | N/A
Jaccard | SD | 0.12 | N/A | N/A | 0.136 | N/A | N/A | 0.16 | N/A | N/A
Jaccard | GC | 0.128 | N/A | N/A | 0.192 | N/A | N/A | 0.2 | N/A | N/A
GCN | Rand. | 0.456 | N/A | N/A | 0.76 | N/A | N/A | 0.888 | N/A | N/A
GCN | SD | 0.6 | N/A | N/A | 0.936 | N/A | N/A | 0.976 | N/A | N/A
GCN | GC | 0.544 | N/A | N/A | 0.88 | N/A | N/A | 0.952 | N/A | N/A
Cheb | Rand. | 0.056 | N/A | N/A | 0.072 | N/A | N/A | 0.072 | N/A | N/A
Cheb | SD | 0.072 | N/A | N/A | 0.128 | N/A | N/A | 0.136 | N/A | N/A
Cheb | GC | 0.136 | N/A | N/A | 0.16 | N/A | N/A | 0.192 | N/A | N/A
Table 6: Results of direct attacks against each classifier with the CiteSeer dataset, with attacker budgets of 5, 10, and 20 edge perturbations. Results are included for Nettack (Net), FGA, and IG-FGSM (IG). For each classifier, we train with random (Rand.), StratDegree (SD), and GreedyCover (GC). Each entry is a probability of attack success, thus higher is better for the attacker and lower is better for the defender. To yield the most robust classifier, the defender picks the classifier/training method combination that minimizes the worst-case attack probability. These entries are listed in bold. Entries representing the most robust case for random training are in italic. Entries listed as N/A did not finish in the allotted time. As with influence attacks, the Jaccard-based classifier performs best, though ChebNet also performs well for all training methods. |  | Budget 5 | Budget 10 | Budget 20
---|---|---|---|---
defense | training | Net | FGA | IG | Net | FGA | IG | Net | FGA | IG
Jaccard | Rand. | 0.384 | 0.256 | 0.296 | 0.592 | 0.392 | 0.368 | 0.752 | 0.464 | 0.472
Jaccard | SD | 0.432 | 0.32 | 0.256 | 0.672 | 0.416 | 0.32 | 0.808 | 0.52 | 0.432
Jaccard | GC | 0.2 | 0.184 | 0.224 | 0.264 | 0.336 | 0.336 | 0.408 | 0.52 | 0.456
RGCN | Rand. | 0.976 | 0.848 | 0.8 | 0.992 | 0.936 | 0.936 | 1.0 | 0.968 | 0.96
RGCN | SD | 0.88 | 0.568 | 0.912 | 0.992 | 0.856 | 0.976 | 1.0 | 0.944 | 0.976
RGCN | GC | 0.896 | 0.712 | 0.808 | 1.0 | 0.88 | 0.936 | 1.0 | 0.952 | 0.976
Cheb | Rand. | 0.224 | 0.28 | 0.264 | 0.344 | 0.352 | 0.384 | 0.424 | 0.44 | 0.464
Cheb | SD | 0.264 | 0.24 | 0.304 | 0.32 | 0.336 | 0.392 | 0.4 | 0.376 | 0.448
Cheb | GC | 0.288 | 0.24 | 0.256 | 0.376 | 0.312 | 0.328 | 0.472 | 0.4 | 0.4
SVD | Rand. | 0.552 | 0.392 | 0.768 | 0.76 | 0.576 | 0.936 | 0.944 | 0.856 | 0.952
SVD | SD | 0.84 | 0.544 | 0.936 | 0.984 | 0.696 | 0.976 | 1.0 | 0.856 | 0.976
SVD | GC | 0.408 | 0.312 | 0.864 | 0.688 | 0.488 | 0.952 | 0.968 | 0.792 | 0.992
median | Rand. | 0.808 | 0.792 | 0.792 | 0.96 | 0.936 | 0.96 | 0.984 | 0.952 | 0.984
median | SD | 0.904 | 0.84 | 0.872 | 0.992 | 0.952 | 0.952 | 1.0 | 0.96 | 0.952
median | GC | 0.856 | 0.832 | 0.848 | 0.96 | 0.952 | 0.96 | 0.992 | 0.968 | 0.976
GAT | Rand. | 0.92 | 0.864 | 0.84 | 0.984 | 0.952 | 0.936 | 1.0 | 0.96 | 0.952
GAT | SD | 0.944 | 0.808 | 0.952 | 1.0 | 0.952 | 0.992 | 1.0 | 0.984 | 1.0
GAT | GC | 0.936 | 0.808 | 0.832 | 1.0 | 0.952 | 0.92 | 1.0 | 0.984 | 0.96
GCN | Rand. | 0.944 | 0.872 | N/A | 0.992 | 0.952 | N/A | 1.0 | 0.976 | N/A
GCN | SD | 0.984 | 0.832 | N/A | 1.0 | 0.968 | N/A | 1.0 | 0.992 | N/A
GCN | GC | 0.912 | 0.904 | 0.936 | 1.0 | 0.976 | 0.992 | 1.0 | 0.976 | 0.992
SGC | Rand. | 0.832 | N/A | N/A | 0.944 | N/A | N/A | 1.0 | N/A | N/A
SGC | SD | 0.936 | N/A | N/A | 1.0 | N/A | N/A | 1.0 | N/A | N/A
SGC | GC | 0.88 | N/A | N/A | 0.96 | N/A | N/A | 1.0 | N/A | N/A
Table 7: Results of direct attacks against each classifier with the Cora dataset, with attacker budgets of 5, 10, and 20 edge perturbations. Results are included for Nettack (Net), FGA, and IG-FGSM (IG). For each classifier, we train with random (Rand.), StratDegree (SD), and GreedyCover (GC). Each entry is a probability of attack success, thus higher is better for the attacker and lower is better for the defender. To yield the most robust classifier, the defender picks the classifier/training method combination that minimizes the worst-case attack probability. These entries are listed in bold. Entries representing the most robust case for random training are in italic. Entries listed as N/A did not finish in the allotted time. While random training with the SVD classifier works best at a low attack budget, Jaccard with StratDegree performs better against better-resourced attackers. |  | Budget 5 | Budget 10 | Budget 20
---|---|---|---|---
defense | training | Net | FGA | IG | Net | FGA | IG | Net | FGA | IG
Jaccard | Rand. | 0.504 | 0.328 | N/A | 0.712 | 0.48 | N/A | 0.952 | 0.68 | N/A
Jaccard | SD | 0.448 | 0.216 | N/A | 0.656 | 0.36 | N/A | 0.776 | 0.552 | N/A
Jaccard | GC | 0.528 | 0.296 | N/A | 0.76 | 0.424 | N/A | 0.912 | 0.616 | N/A
RGCN | Rand. | 0.936 | 0.896 | N/A | 0.984 | 0.992 | N/A | 0.992 | 0.992 | N/A
RGCN | SD | 0.944 | 0.832 | N/A | 1.0 | 0.952 | N/A | 1.0 | 0.96 | N/A
RGCN | GC | 0.976 | 0.84 | 0.832 | 1.0 | 0.96 | 0.976 | 1.0 | 0.96 | 0.976
Cheb | Rand. | 0.88 | 0.728 | N/A | 0.976 | 0.928 | N/A | 0.984 | 0.96 | N/A
Cheb | SD | 0.96 | 0.752 | N/A | 1.0 | 0.928 | N/A | 1.0 | 0.936 | N/A
Cheb | GC | 0.944 | 0.816 | N/A | 0.992 | 0.952 | N/A | 1.0 | 0.96 | N/A
SVD | Rand. | 0.36 | 0.24 | N/A | 0.776 | 0.592 | N/A | 0.992 | 0.928 | N/A
SVD | SD | 0.696 | 0.288 | N/A | 0.936 | 0.632 | N/A | 1.0 | 0.92 | N/A
SVD | GC | 0.432 | 0.184 | N/A | 0.792 | 0.448 | N/A | 1.0 | 0.84 | N/A
median | Rand. | 0.936 | 0.768 | 0.824 | 0.992 | 0.96 | 0.968 | 1.0 | 0.976 | 0.992
median | SD | 0.968 | 0.864 | 0.864 | 1.0 | 0.952 | 0.984 | 1.0 | 0.952 | 0.984
median | GC | 0.912 | 0.824 | 0.824 | 1.0 | 0.968 | 0.976 | 1.0 | 0.968 | 0.976
GAT | Rand. | 0.944 | 0.856 | N/A | 1.0 | 0.96 | N/A | 1.0 | 0.968 | N/A
GAT | SD | 0.928 | 0.736 | N/A | 1.0 | 0.92 | N/A | 1.0 | 0.968 | N/A
GAT | GC | 0.92 | 0.824 | N/A | 1.0 | 0.952 | N/A | 1.0 | 0.984 | N/A
GCN | Rand. | 0.928 | 0.888 | N/A | 0.992 | 0.976 | N/A | 1.0 | 0.976 | N/A
GCN | SD | 0.928 | 0.624 | 0.904 | 0.992 | 0.944 | 0.992 | 1.0 | 0.968 | 0.992
GCN | GC | 0.904 | 0.832 | 0.808 | 0.992 | 0.976 | 0.984 | 1.0 | 0.984 | 0.992
SGC | Rand. | 0.896 | N/A | N/A | 1.0 | N/A | N/A | 1.0 | N/A | N/A
SGC | SD | 0.944 | N/A | N/A | 1.0 | N/A | N/A | 1.0 | N/A | N/A
SGC | GC | 0.904 | N/A | N/A | 1.0 | N/A | N/A | 1.0 | N/A | N/A
Table 8: Results of direct attacks against each classifier with the PolBlogs dataset, with attacker budgets of 5, 10, and 20 edge perturbations. Results are included for Nettack (Net), FGA, and IG-FGSM (IG). For each classifier, we train with random (Rand.), StratDegree (SD), and GreedyCover (GC). Each entry is a probability of attack success, thus higher is better for the attacker and lower is better for the defender. To yield the most robust classifier, the defender picks the classifier/training method combination that minimizes the worst-case attack probability. These entries are listed in bold. Entries representing the most robust case for random training are in italic. Entries listed as N/A did not finish in the allotted time. While random training with the SVD classifier works best at a low attack budget, Jaccard with StratDegree performs better against better-resourced attackers. |  | Budget 5 | Budget 10 | Budget 20
---|---|---|---|---
defense | training | Net | FGA | IG | Net | FGA | IG | Net | FGA | IG
Jaccard | Rand. | 0.672 | 0.616 | 0.688 | 0.896 | 0.848 | 0.856 | 0.992 | 0.968 | 0.976
Jaccard | SD | 0.752 | 0.8 | 0.808 | 0.936 | 0.928 | 0.952 | 1.0 | 0.984 | 1.0
Jaccard | GC | 0.768 | 0.76 | 0.872 | 0.904 | 0.92 | 0.976 | 0.992 | 1.0 | 1.0
RGCN | Rand. | 0.48 | 0.464 | 0.312 | 0.632 | 0.664 | 0.504 | 0.784 | 0.872 | 0.704
RGCN | SD | 0.304 | 0.28 | 0.344 | 0.4 | 0.44 | 0.52 | 0.648 | 0.568 | 0.736
RGCN | GC | 0.56 | 0.488 | 0.336 | 0.72 | 0.648 | 0.456 | 0.832 | 0.832 | 0.64
Cheb | Rand. | 0.376 | 0.352 | 0.448 | 0.536 | 0.552 | 0.544 | 0.72 | 0.68 | 0.744
Cheb | SD | 0.408 | 0.376 | 0.432 | 0.624 | 0.544 | 0.584 | 0.784 | 0.688 | 0.768
Cheb | GC | 0.576 | 0.424 | 0.472 | 0.68 | 0.568 | 0.592 | 0.8 | 0.728 | 0.768
SVD | Rand. | 0.184 | 0.056 | 0.336 | 0.368 | 0.104 | 0.552 | 0.496 | 0.192 | 0.704
SVD | SD | 0.288 | 0.016 | 0.368 | 0.416 | 0.024 | 0.536 | 0.496 | 0.064 | 0.808
SVD | GC | 0.12 | 0.04 | 0.32 | 0.36 | 0.04 | 0.512 | 0.464 | 0.048 | 0.768
GAT | Rand. | 0.456 | 0.52 | 0.376 | 0.624 | 0.792 | 0.52 | 0.824 | 0.912 | 0.672
GAT | SD | 0.32 | 0.24 | 0.36 | 0.464 | 0.384 | 0.504 | 0.664 | 0.648 | 0.752
GAT | GC | 0.552 | 0.528 | 0.336 | 0.744 | 0.84 | 0.576 | 0.856 | 0.936 | 0.84
GCN | Rand. | 0.472 | 0.624 | 0.408 | 0.68 | 0.784 | 0.52 | 0.816 | 0.92 | 0.76
GCN | SD | 0.424 | 0.344 | 0.408 | 0.568 | 0.528 | 0.544 | 0.76 | 0.76 | 0.672
GCN | GC | 0.496 | 0.552 | 0.312 | 0.72 | 0.768 | 0.512 | 0.88 | 0.912 | 0.728
SGC | Rand. | 0.36 | N/A | N/A | 0.464 | N/A | N/A | 0.6 | N/A | N/A
SGC | SD | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A
SGC | GC | 0.528 | N/A | N/A | 0.736 | N/A | N/A | 0.856 | N/A | N/A
Table 9: Results of direct attacks against each classifier with the PubMed dataset, with attacker budgets of 5, 10, and 20 edge perturbations. Results are included for Nettack (Net), FGA, and IG-FGSM (IG). For each classifier, we train with random (Rand.), StratDegree (SD), and GreedyCover (GC). Each entry is a probability of attack success, thus higher is better for the attacker and lower is better for the defender. To yield the most robust classifier, the defender picks the classifier/training method combination that minimizes the worst-case attack probability. These entries are listed in bold. Entries representing the most robust case for random training are in italic. Entries listed as N/A did not finish in the allotted time. While the aStratDegree GreedyCover work well in conjunction with the Jaccard classifier, a disparity in the classification margin hinders their performance in the best case, using a ChebNet classifier. |  | Budget 5 | Budget 10 | Budget 20
---|---|---|---|---
defense | training | Net | FGA | IG | Net | FGA | IG | Net | FGA | IG
Jaccard | random | 0.784 | N/A | N/A | 0.952 | N/A | N/A | 0.992 | N/A | N/A
Jaccard | degree | 0.208 | N/A | N/A | 0.248 | N/A | N/A | 0.328 | N/A | N/A
Jaccard | cover | 0.208 | N/A | N/A | 0.328 | N/A | N/A | 0.456 | N/A | N/A
GCN | random | 0.92 | N/A | N/A | 1.0 | N/A | N/A | 1.0 | N/A | N/A
GCN | degree | 0.952 | N/A | N/A | 1.0 | N/A | N/A | 1.0 | N/A | N/A
GCN | cover | 0.936 | N/A | N/A | 0.984 | N/A | N/A | 1.0 | N/A | N/A
Cheb | random | 0.056 | N/A | N/A | 0.088 | N/A | N/A | 0.088 | N/A | N/A
Cheb | degree | 0.072 | N/A | N/A | 0.088 | N/A | N/A | 0.104 | N/A | N/A
Cheb | cover | 0.088 | N/A | N/A | 0.112 | N/A | N/A | 0.152 | N/A | N/A
GAT | random | 0.792 | N/A | N/A | 0.896 | N/A | N/A | 0.992 | N/A | N/A
GAT | degree | 0.936 | N/A | N/A | 0.992 | N/A | N/A | 1.0 | N/A | N/A
GAT | cover | 0.92 | N/A | N/A | 0.984 | N/A | N/A | 0.992 | N/A | N/A