# Out of Distribution Detection and Adversarial Attacks
on Deep Neural Networks for Robust Medical Image Analysis

Anisie Uwimana  Ransalu Senanayake

###### Abstract

Deep learning models have become a popular choice for medical image analysis.
However, the poor generalization performance of deep learning models limits
them from being deployed in the real world as robustness is critical for
medical applications. For instance, the state-of-the-art Convolutional Neural
Networks (CNNs) fail to detect adversarial samples or samples drawn
statistically far away from the training distribution. In this work, we
experimentally evaluate the robustness of a Mahalanobis distance-based
confidence score, a simple yet effective method for detecting abnormal input
samples, in classifying malaria parasitized cells and uninfected cells.
Results indicated that the Mahalanobis confidence score detector exhibits
improved performance and robustness of deep learning models, and achieves
state-of-the-art performance on both _out-of-distribution (OOD)_ and
_adversarial_ samples.

Machine Learning, ICML

##  1 Introduction

Deep learning is increasingly making its way into groundbreaking technologies
that have high-value applications in the real-world clinical environment.
Innovative medical imaging applications and diagnostics are among the most
exciting use cases. One such application is developing microscopy-based
malaria diagnosis procedures (Ravendran et al., 2015; Silva et al., 2013; Yang
et al., 2019). Malaria is a deadly mosquito-borne disease infecting around
$300$ million people annually (World Health Organization, ). Since it is
mostly prevalent in low-income countries, developing semi-automated microscopy
techniques, as alternatives to polymerase chain reaction (PCR) tests and rapid
diagnostic tests (RDT), is a low-cost and reliable solution (Wongsrichanalai
et al., 2007).

###  1.1 Applications of deep learning in medical diagnosis

Esteva et al. (2017) developed a convolutional neural network (CNN) model that
was trained on $130,000$ clinical images of skin pathologies to detect cancer.
The proposed model achieves performance on par with all tested experts,
demonstrating an artificial intelligence model capable of classifying skin
cancer with a level of competence comparable to dermatologists. In $2018$,
another research study showed that a convolutional neural network trained to
analyze dermatology images identified melanoma with ten percent more
specificity than human clinicians (Haenssle et al., 2018). Another algorithm
trained on $42,000$ chest CT scans outperformed expert radiologists in
detecting lung cancers (Ardila et al., 2019). It was able to find malignant
lung modes $5$-$9.5\%$ more often than human specialists. Recently, a CNN
model designed to predict malignancy and identify 134 skin disorders (Cho et
al., 2020). The proposed algorithm is capable of distinguishing, at the human
expert level, melanoma from birthmarks. There have also been various studies
on assessing the uncertainty and robustness in medical data (Senanayake et
al., 2016; Laves et al., 2020; Asgharnezhad et al., 2020).

###  1.2 Applications of deep learning for malaria diagnosis

Various computer vision algorithms have been used for malaria diagnosis
(Ravendran et al., 2015). Deep learning algorithms are recently being used
increasingly by researchers especially for malaria detection because of its
applicability in building automated diagnostic system. Liang et al. (2016)
presented a 16-layer CNN towards classifying uninfected and parasitized cells.
The study reported that the custom model was more accurate, sensitive, and
specific than the pre-trained model. Dong et al. (2017) evaluated three well-
known CNNs (LeNet, AlexNet and GoogLeNet) on classifying parasite/not parasite
slide images of thin blood stains. Simulation results showed that all three
CNNs achieved classification accuracy scores of over $95\%$. Rajaraman et al.
(2018b) introduced a pretrained CNN as a feature extractor towards improved
malaria parasite detection in thin blood smear images, and the results present
the use of pretrained CNNs as a promising tool in malaria detection.

Rajaraman et al. (2018a) has demonstrated that deep neural networks can be
used to detect malaria from microscopic images. However, in order to deploy
such systems in medical facilities, it is vital to ensure that the automated
detection systems are indeed robust. Nonetheless, deep learning algorithms
work on the premise that both training and test data are drawn from the same
application-specific distribution. However, in real-world applications, they
need to be able to robustly handle anomalous inputs including, 1) adversarial
samples arising from image distortion and 2) samples drawn from a different
distribution but belong to the same input space.

In this work, we propose using a Mahalanobis distance-based confidence score
method (Lee et al., 2018; Kamoi & Kobayashi, 2020; Nitsch et al., 2021) for
detecting abnormal (both OOD and adversarial) samples to improve the
performance and robustness of pre-trained convolutional neural network models
to improve the robustness of malaria detection (Figure 1). The suggested
method gives better results compared to the current state-of-the-art method
ODIN (Liang et al., 2018) in detecting OOD malaria samples. We also
demonstrate that Mahalanobis distance-based confidence score outperforms the
state-of-the-art detection, LID, in all test cases, in detecting adversarial
samples generated by four adversarial attacking methods: FGSM (Goodfellow et
al., 2015), BIM (Kurakin et al., 2016), DeepFool (Moosavi-Dezfooli et al.,
2016), and CW (Carlini & Wagner, 2017).

Figure 1: FGSM adversarial attack on parasitized and healthy cells for varying
levels of noise. Noise can be visually inspected on the black areas and cell
boundary, especially for $\epsilon=0.3$). On the top row, parasites can be
seen in dark color inside the cell. The prediction probabilities are indicated
above each image.

##  2 Robustness of deep learning models

The robustness of deep learning algorithms needs to be evaluated before
deploying them in real-wold. Therefore, it is crucial to ensure the neural
networks can detect abnormal inputs in safety- and security-sensitive
applications such as medical diagnosis, biometric authentication, intrusion
detection, and autonomous driving (Emmott et al., 2016; Nitsch et al., 2021).

###  2.1 Robust out-of-distribution detection for neural networks

Out-of-Distribution (OOD) samples, the test samples that are not well covered
by training data, is a major cause of poor performance in deep learning
models. OOD samples are able to both evade the deep learning algorithms as
well as achieve targeted misclassification with high confidence. There are
currently many approaches that can detect OOD examples. They work well when
tested on natural samples from a distribution that is sufficiently different
from the distribution of the training data (Chen et al., 2020).

Hendrycks & Gimpel (2016) recently proposed a baseline for detecting
misclassified and OOD examples in deep neural networks (DNNs), and Liang et
al. (2017) improved it by processing the input and output of the DNNs. The
Softmax Baseline Mode computes softmax probabilities with the fast-growing
exponential function. Thus minor changes to the softmax inputs, can lead to
major changes in the output distribution. A softmax baseline method uses
probabilities from softmax distributions to predict whether a test example is
from a different distribution from the training data or from within the same
distribution. Liang et al. (2018) proposed ODIN (Out-of-DIstribution detector
for Neural networks) which is a simple and effective method for detecting OOD
images in neural networks. ODIN does not require re-training the neural
network and is compatible with diverse network architectures and datasets.

###  2.2 Robust adversarial detection for neural networks

Recent studies have concentrated on identifying adversarial examples despite
the inefficiency of adversarial defense (Fawzi et al., 2016). Goodfellow et
al. (2014) suggested a framework for estimating abnormal samples via
adversarial networks. Local Intrinsic Dimensionality (LID) is one of the
successful adversarial detection techniques proposed by Ma et al. (2018). With
the assumption that adversarial subspaces are low probability regions that are
densely scattered in the high dimensional representation space of DNNs. The
properties of adversarial regions is considered as a key requirement for
adversarial defense (Ma et al., 2018).

##  3 Mahalanobis confidence score

One of the limitations of both ODIN and LID is that they are designed for
either OOD or adversarial corruption but not for both. More recently, Lee et
al. (2018) proposed a simple yet effective method for detecting both OOD
samples and adversarial samples.

Mahalanobis distance-based confidence score is a class-conditional anomaly
detection method, motivated by classification prediction confidence (Kamoi &
Kobayashi, 2020).

Let us consider a dataset $\mathcal{D}=\\{(\mathbf{x}_{n},y_{n})\\}_{n=1}^{N}$
with input-label pairs. The labels belong to one of the classes
$\\{1,\ldots,C\\}$. For malara parasite detection, labels are either
parasitized or healthy. For a deep neural network, $f_{\phi}$, with parameters
$\phi$, we consider a pre-trained softmax classifier,

$p_{\theta}(y=c|\mathbf{x})=\frac{\exp(\mathbf{w}_{c}^{\top}f_{\phi}(\mathbf{x}))}{\sum_{c^{\prime}}\exp(\mathbf{w}_{c^{\prime}}^{\top}f_{\phi}(\mathbf{x}))}.$
(1)

For each class, we define a multivariate Gaussian distribution,
$p(f_{\phi}(\mathbf{x})|y=c)=\mathcal{N}(f_{\phi}(\mathbf{x})|\bm{\mu}_{c},\Sigma)$
with class mean $\bm{\mu}_{c}$ and pooled-covariance $\Sigma$. This way, we
compute the empirical statistics
$(\hat{\bm{\mu}}_{1},\hat{\bm{\mu}}_{2},\ldots,\hat{\bm{\mu}}_{C},\hat{\Sigma})$
from the training dataset $\mathcal{D}$. With these statistics, the closest
class $\tilde{c}$ to a query input $\mathbf{x}_{*}$ can be computed using the
Mahalanobis distance,

$\tilde{c}=\min_{c\in\\{1,2,\ldots,C\\}}\sqrt{(f(\mathbf{x}_{*})-\hat{\bm{\mu}}_{c})^{\top}\hat{\Sigma}^{-1}(f(\mathbf{x}_{*})-\hat{\bm{\mu}}_{c})}.$
(2)

Following Liang et al. (2017), a controlled noise $\epsilon$ is added to the
input,

${\tilde{\mathbf{x}}}_{*}=\mathbf{x}_{*}-\epsilon\cdot\mathrm{sign}\big{(}\nabla_{\mathbf{x}}(f(\mathbf{x}_{*})-\bm{\mu}_{\tilde{c}})^{\top}\hat{\Sigma}^{-1}(f(\mathbf{x}_{*})-\bm{\hat{\mu}}_{\tilde{c}})\big{)},$
(3)

for better calibration. Then, we can compute the confidence score,

$M(\tilde{\mathbf{x}}_{*})=\max_{c\in\\{1,2,\ldots,C\\}}-(f(\tilde{\mathbf{x}}_{*})-\hat{\bm{\mu}}_{c})^{\top}\hat{\Sigma}^{-1}(f(\tilde{\mathbf{x}}_{*})-\hat{\bm{\mu}}_{c}).$
(4)

By doing this for all $l=\\{1,\ldots,L\\}$ layers of the neural network with
weights $\alpha_{l}$ of the logistic regression classifier (separately trained
for each layer on a validation dataset (Ma et al., 2018)), we can compute the
overall score
$M^{*}(\mathbf{x_{*}})=\sum_{l=1}^{L}\alpha_{l}M_{l}(\mathbf{x_{*}})$. For a
given threshold $\rho$, the query samples, $\mathbf{x_{*}}$, is _in-
distribution_ , if $M^{*}(\mathbf{x_{*}})\geq\rho$.

##  4 Experiments

In our experiments, we used a publicly accessible and annotated malaria
dataset of healthy and infected blood smear images 111
https://lhncbc.nlm.nih.gov/publication/pub9932. It contains $13,779$
parasitized and $13,779$ uninfected cell images. We split the dataset into
$60:10:30$ for train, validation, and test datasets, respectively. We resized
the images to $125\times 125$ pixels and normalized them to assist in faster
convergence. To prevent over-fitting and to account for possible variations in
photomicroscopy, we have applied data augmentation techniques such as
rotation, shearing, translation, and zooming. For OOD, another malaria dataset
consisting of $22,046$ was used222https://github.com/shriyakabra97/malaria-
parasite-detection.

Figure 2: Robustness against _out-of-distribution_ samples: ResNet-18

Figure 3: Robustness against _out-of-distribution_ samples: VGG-19 Table 1:
Robustness against _adversarial samples_ : a comparison of the performance of
LID and Mahalanobis (proposed) towards detecting adversarial test samples
generated from malaria image datasets.

Model | Metric | LID | Mahalanobis
---|---|---|---
|  | FGSM | BIM | DeepFool | CW | FGSM | BIM | DeepFool | CW
VGG-19 | TNR at TPR 95% | 99.96 | 96.87 | 74.48 | 75.93 | 100.00 | 100.00 | 75.96 | 98.11
| AUROC | 97.30 | 96.68 | 78.01 | 89.64 | 99.98 | 99.68 | 83.56 | 99.35
| Detection accuracy | 99.41 | 90.46 | 46.05 | 72.96 | 99.98 | 99.99 | 61.95 | 97.51
ResNet-18 | TNR at TPR 95% | 96.84 | 95.61 | 63.59 | 73.09 | 99.99 | 97.98 | 76.22 | 98.90
| AUROC | 97.30 | 96.68 | 78.01 | 89.64 | 99.98 | 99.68 | 83.56 | 99.35
| Detection accuracy | 97.02 | 97.65 | 49.56 | 84.66 | 99.75 | 99.95 | 64.95 | 98.05

Figure 4: A comparison of performance between LID and Mahalanobis distance-
based confidence score for ResNet-18 pre-trained model.

Figure 5: A comparison of detection performance between LID and Mahalanobis
distance-based confidence score for VGG-19 pre-trained model

For OOD and adversarial samples detection, the suggested method to improve the
robustness of DL models was evaluated on both VGG-19 and ResNet-18 using a
threshold-based detector. We evaluate the models with the following metrics:
the true negative rate (TNR) at 95% true positive rate (TPR), the area under
the receiver operating characteristic (AUROC) curve, the area under the
precision-recall (AUPR) curve, and the detection accuracy. The Mahalanobis
confidence score was compared with the baseline method and state-of-the-art
ODIN for OOD samples. It was also compared with the state-of-the-art LID
toward adversarial samples detection. Comparing with the baseline method, ODIN
and LID, as shown in Table 1 and Figures 2, 3,4,and 5, the proposed approach
outperforms on detecting abnormal samples.

As the Mahalanobis distance-based score method outperforms for the tasks of
detecting OOD samples and adversarial samples, it can serve as a diagnostic
framework for evaluating deep neural networks, as it is able to reveal their
potentially non-obvious vulnerabilities and reliability. Such frameworks help
to ensure that deep neural networks are effective, secure, and easy to deploy
in a broad range of medical imaging applications beyond malaria detection. Our
future work will extend this framework to test medical images under various
lighting and other possible sources of corruption. We envision this, in the
long-term, will enable low-cost, yet reliable, imaging procedures.

## Broader impact statement

Broadly, our research is a step towards developing robust semi-automated
medical image analysis techniques. Specifically, we focus on ensuring that
malaria detection procedures are reliable enough before deployment. It, in the
long-term, will help low-income countries to eradicate malaria. These systems,
however, need to be rigorously validated before deploying in medical
facilities.

## References

  * Ardila et al. (2019) Ardila, D., Kiraly, A. P., Bharadwaj, S., Choi, B., Reicher, J. J., Peng, L., Tse, D., Etemadi, M., Ye, W., Corrado, G., et al.  End-to-end lung cancer screening with three-dimensional deep learning on low-dose chest computed tomography.  _Nature medicine_ , 25(6):954–961, 2019.
  * Asgharnezhad et al. (2020) Asgharnezhad, H., Shamsi, A., Alizadehsani, R., Khosravi, A., Nahavandi, S., Sani, Z. A., and Srinivasan, D.  Objective evaluation of deep uncertainty predictions for covid-19 detection.  _arXiv preprint arXiv:2012.11840_ , 2020.
  * Carlini & Wagner (2017) Carlini, N. and Wagner, D.  Adversarial examples are not easily detected: Bypassing ten detection methods.  In _Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security_ , pp. 3–14, 2017.
  * Chen et al. (2020) Chen, J., Wu, X., Liang, Y., Jha, S., et al.  Robust out-of-distribution detection in neural networks.  _arXiv preprint arXiv:2003.09711_ , 2020.
  * Cho et al. (2020) Cho, S. I., Sun, S., Mun, J.-H., Kim, C., Kim, S., Cho, S., Youn, S., Kim, H. C., and Chung, J.  Dermatologist-level classification of malignant lip diseases using a deep convolutional neural network.  _British Journal of Dermatology_ , 182(6):1388–1394, 2020.
  * Dong et al. (2017) Dong, Y., Jiang, Z., Shen, H., David Pan, W., Williams, L. A., Reddy, V. V. B., Benjamin, W. H., and Bryan, A. W.  Evaluations of deep convolutional neural networks for automatic identification of malaria infected cells.  In _2017 IEEE EMBS International Conference on Biomedical Health Informatics (BHI)_ , pp. 101–104, 2017.
  * Emmott et al. (2016) Emmott, A., Das, S., Dietterich, T., Fern, A., and Wong, W.-K.  A meta-analysis of the anomaly detection problem, 2016.
  * Esteva et al. (2017) Esteva, A., Kuprel, B., Novoa, R. A., Ko, J., Swetter, S. M., Blau, H. M., and Thrun, S.  Dermatologist-level classification of skin cancer with deep neural networks.  _nature_ , 542(7639):115–118, 2017.
  * Fawzi et al. (2016) Fawzi, A., Moosavi-Dezfooli, S.-M., and Frossard, P.  Robustness of classifiers: from adversarial to random noise.  In Lee, D. D., Sugiyama, M., Luxburg, U. V., Guyon, I., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems 29_ , pp. 1632–1640. Curran Associates, Inc., 2016.
  * Goodfellow et al. (2014) Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y.  Generative adversarial nets.  In _Advances in neural information processing systems_ , pp. 2672–2680, 2014.
  * Goodfellow et al. (2015) Goodfellow, I. J., Shlens, J., and Szegedy, C.  Explaining and harnessing adversarial examples.  In _The International Conference on Learning Representations_ , 2015\.
  * Haenssle et al. (2018) Haenssle, H. A., Fink, C., Schneiderbauer, R., Toberer, F., Buhl, T., Blum, A., Kalloo, A., Hassen, A. B. H., Thomas, L., Enk, A., et al.  Man against machine: diagnostic performance of a deep learning convolutional neural network for dermoscopic melanoma recognition in comparison to 58 dermatologists.  _Annals of Oncology_ , 29(8):1836–1842, 2018\.
  * Hendrycks & Gimpel (2016) Hendrycks, D. and Gimpel, K.  A baseline for detecting misclassified and out-of-distribution examples in neural networks.  _arXiv preprint arXiv:1610.02136_ , 2016.
  * Kamoi & Kobayashi (2020) Kamoi, R. and Kobayashi, K.  Why is the mahalanobis distance effective for anomaly detection?  _arXiv preprint arXiv:2003.00402_ , 2020.
  * Kurakin et al. (2016) Kurakin, A., Goodfellow, I., and Bengio, S.  Adversarial examples in the physical world.  _arXiv preprint arXiv:1607.02533_ , 2016.
  * Laves et al. (2020) Laves, M.-H., Ihler, S., Fast, J. F., Kahrs, L. A., and Ortmaier, T.  Well-calibrated regression uncertainty in medical imaging with deep learning.  In _Medical Imaging with Deep Learning_ , pp. 393–412. PMLR, 2020\.
  * Lee et al. (2018) Lee, K., Lee, K., Lee, H., and Shin, J.  A simple unified framework for detecting out-of-distribution samples and adversarial attacks.  In _Advances in Neural Information Processing Systems_ , pp. 7167–7177, 2018.
  * Liang et al. (2017) Liang, S., Li, Y., and Srikant, R.  Principled detection of out-of-distribution examples in neural networks.  _arXiv preprint arXiv:1706.02690_ , 2017.
  * Liang et al. (2018) Liang, S., Li, Y., and Srikant, R.  Enhancing the reliability of out-of-distribution image detection in neural networks.  In _The International Conference on Learning Representations_ , 2018\.
  * Liang et al. (2016) Liang, Z., Powell, A., Ersoy, I., Poostchi, M., Silamut, K., Palaniappan, K., Guo, P., Hossain, M. A., Antani, S. K., Maude, R. J., Huang, X., Jaeger, S., and Thoma, G. R.  Cnn-based image analysis for malaria diagnosis.  _2016 IEEE International Conference on Bioinformatics and Biomedicine (BIBM)_ , pp. 493–496, 2016.
  * Ma et al. (2018) Ma, X., Li, B., Wang, Y., Erfani, S. M., Wijewickrema, S., Schoenebeck, G., Song, D., Houle, M. E., and Bailey, J.  Characterizing adversarial subspaces using local intrinsic dimensionality.  In _The International Conference on Learning Representations_ , 2018\.
  * Moosavi-Dezfooli et al. (2016) Moosavi-Dezfooli, S.-M., Fawzi, A., and Frossard, P.  Deepfool: a simple and accurate method to fool deep neural networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 2574–2582, 2016.
  * Nitsch et al. (2021) Nitsch, J., Itkina, M., Senanayake, R., Nieto, J., Schmidt, M., Siegwart, R., Kochenderfer, M. J., and Cadena, C.  Out-of-distribution detection for automotive perception.  In _24th IEEE International Conference on Intelligent Transportation Systems (ITSC)_ , 2021.  doi: arXiv:2011.01413.
  * Rajaraman et al. (2018a) Rajaraman, S., Antani, S. K., Poostchi, M., Silamut, K., Hossain, M. A., Maude, R. J., Jaeger, S., and Thoma, G. R.  Pre-trained convolutional neural networks as feature extractors toward improved malaria parasite detection in thin blood smear images.  _PeerJ_ , 6:e4568, 2018a.
  * Rajaraman et al. (2018b) Rajaraman, S., Antani, S. K., Poostchi, M., Silamut, K., Hossain, M. A., Maude, R. J., Jaeger, S., and Thoma, G. R.  Pre-trained convolutional neural networks as feature extractors toward improved malaria parasite detection in thin blood smear images.  _PeerJ_ , 6:e4568, 2018b.
  * Ravendran et al. (2015) Ravendran, A., de Silva, K. R. T., and Senanayake, R.  Moment invariant features for automatic identification of critical malaria parasites.  In _2015 IEEE 10th International Conference on Industrial and Information Systems (ICIIS)_ , pp. 474–479. IEEE, 2015.
  * Senanayake et al. (2016) Senanayake, R., O’Callaghan, S., and Ramos, F.  Predicting spatio-temporal propagation of seasonal influenza using variational gaussian process regression.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 30, 2016.
  * Silva et al. (2013) Silva, A. D. N., Wijesundara, M. N., and Senanayake, R.  Computer controlled digital microscope with photomicrograph enhancement.  In _2013 International Conference of Information and Communication Technology (ICoICT)_ , pp. 44–47. IEEE, 2013.
  * Wongsrichanalai et al. (2007) Wongsrichanalai, C., Barcus, M. J., Muth, S., Sutamihardja, A., and Wernsdorfer, W. H.  A review of malaria diagnostic tools: microscopy and rapid diagnostic test (rdt).  _The American journal of tropical medicine and hygiene_ , 77(6_Suppl):119–127, 2007.
  * (30) World Health Organization.  World malaria report 2019.  https://www.who.int/news-room/fact-sheets/detail/malaria.  Accessed: 2020-05-25.
  * Yang et al. (2019) Yang, F., Poostchi, M., Yu, H., Zhou, Z., Silamut, K., Yu, J., Maude, R. J., Jaeger, S., and Antani, S.  Deep learning for smartphone-based malaria parasite detection in thick blood smears.  _IEEE journal of biomedical and health informatics_ , 24(5):1427–1438, 2019.


#  XGBD: Explanation-Guided Graph Backdoor Detection

Zihan Guan  Mengnan Du  Ninghao Liu Corresponding Author. Email:
<EMAIL_ADDRESS>School of Computing, University of Georgia, USA
Department of Data Science, New Jersey Institute of Technology, USA

###### Abstract

Backdoor attacks pose a significant security risk to graph learning models.
Backdoors can be embedded into the target model by inserting backdoor triggers
into the training dataset, causing the model to make incorrect predictions
when the trigger is present. To counter backdoor attacks, backdoor detection
has been proposed. An emerging detection strategy in the vision and NLP
domains is based on an intriguing phenomenon: when training models on a
mixture of backdoor and clean samples, the loss on backdoor samples drops
significantly faster than on clean samples, allowing backdoor samples to be
easily detected by selecting samples with the lowest loss values. However, the
ignorance of topological feature information on graph data limits its
detection effectiveness when applied directly to the graph domain. To this
end, we propose an explanation-guided backdoor detection method to take
advantage of the topological information. Specifically, we train a helper
model on the graph dataset, feed graph samples into the model, and then adopt
explanation methods to attribute model prediction to an important subgraph. We
observe that backdoor samples have distinct attribution distribution than
clean samples, so the explanatory subgraph could serve as more discriminative
features for detecting backdoor samples. Comprehensive experiments on multiple
popular datasets and attack methods demonstrate the effectiveness and
explainability of our method. Our code is available:
https://github.com/GuanZihan/GNN_backdoor_detection.

##  1 Introduction

Graph machine learning has recently gained popularity due to its high
expressibility in a wide range of graph-based applications such as social
networks [34], physical systems [27], and biomedical analysis [7]. Graph
neural networks (GNNs) achieve state-of-the-art performance in various graph
learning tasks [35, 46, 45, 30]. In practice, due to the complexity of graph
data and the difficulty of data collection, it is common for users to directly
use graph datasets published by a third party [25] or from untrusted Internet
sources, which could lead to potential security problems. For example, a
malicious entity could launch backdoor attacks by injecting predefined
triggers (e.g., small subgraphs) into victim samples and changing their labels
to target values. If users train their models on the poisoned dataset, a
mapping from the trigger patterns to the target labels will be learned. Then,
if the model is deployed to real-world applications, the malicious entity
could manipulate model behaviors by feeding poisoned inference samples into
the model.

There has been a plethora of prior work on backdoor detection in the vision
and NLP domains [1, 10, 17, 6, 13, 37, 15, 2, 41, 3]. However, backdoor
detection on graph data has not been well explored. Although some work [1, 20]
originally proposed in the vision domain can be applied directly to the graph
domain, their effectiveness is limited as they ignore the topological
information of the graph data. To the best of our knowledge, only a few
preliminary works focus on backdoor detection on graphs [18]. However, it
requires an additional validation set to determine the detection boundary,
which is not always realistic in practice.

A recently observed phenomenon provides opportunities for detecting backdoor
samples: When training models on a mixture of backdoor samples and clean
samples, the loss on backdoor samples tends to decrease significantly fast in
the early epochs, while the loss on clean samples tends to decrease steadily.
Therefore, the backdoor samples could be easily identified by selecting
samples with the top-k lowest loss values. The method has been shown to be
effective in the vision domain [20]. However, the method does not perform
effectively in the graph domain due to the following challenges: 1) How to
take advantage of the topological information in the graph data? 2) How to
enlarge the loss gap between backdoor samples and clean samples in the graph
domain?

To this end, we develop an eXplanation-Guided Backdoor Detection (XGBD)
method. It is motivated by the following empirical findings: Given backdoor
samples, neural networks are prone to solely rely on simple trigger patterns
to make predictions, whereas given clean samples, they tend to rely on more
complex feature patterns. It is easier for an explanation method to capture
the trigger patterns of backdoor samples than to find all the key features of
clean samples, thus creating a gap between the two types of samples.
Therefore, given a training dataset which could contain backdoor samples, we
train a graph neural network on the dataset, and apply explanation methods on
each of the training samples to extract an explanatory subgraph. As a result,
the backdoor samples could be detected based on the model’s loss value with
the explanatory subgraph as input. If the loss value is less than some
threshold $\tau$, i.e., the explanatory subgraph well preserves the core
information of the overall graph, the input sample is regarded as containing
backdoors.

Figure 1: The average training loss curve for clean samples and backdoor
samples on different datasets. The blue and red bands denote the range of loss
values for clean samples and backdoor samples, respectively. The $x$-axis
denotes the training epochs, and the $y$-axis denotes the training loss value.
The gap between the loss curves of clean and backdoor samples is not
significant enough to effectively distinguish them for backdoor samples
detection.

In summary, our contributions lie in the following aspects:

  * •

We propose a backdoor detection method for graph data. Compared to previous
work [18], our method does not require an additional validation dataset.

  * •

We show that explanation methods are effective feature filters in
distinguishing between clean samples and backdoor samples when integrated with
our carefully crafted constraints and detectors (Section 3.2).

  * •

We conduct comprehensive experiments with rich ablation studies, where our
proposed method achieves satisfactory performance across various datasets
(Section 4).

##  2 Preliminaries

###  2.1 Graph Neural Networks

Notations. Let $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{X})$ denote a
graph with a finite node set $\mathcal{V}$ of size $n$, an edge set
$\mathcal{E}$, and a node feature matrix $\mathcal{X}\in\mathbb{R}^{n\times
m}$. $A\in\mathbb{R}^{n\times n}$ is the corresponding adjacent matrix, where
$A_{i,j}\in\\{0,1\\},\forall i,j\in\mathcal{V}$, indicates whether there is an
edge between node $i$ and node $j$. The neighbors of a node $v\in\mathcal{V}$
are denoted as $\mathcal{N}(v)=\\{u\in\mathcal{V}|(u,v)\in\mathcal{E}\\}$; the
neighbors of a subset $S\subset\mathcal{V}$ are defined as
$\mathcal{N}(S)=\bigcup_{v\in S}N(v)$. For simplicity, we also denote
$\mathcal{X}(S)\in\mathbb{R}^{|S|\times m}$ as the feature matrix of the
subset $S$.

Graph Neural Networks (GNNs). GNNs have become the state-of-the-art approach
for modeling graph data. Typically, GNNs take a graph $\mathcal{G}$ as input
and use the message-passing mechanism to learn its embedding and prediction.
Without loss of generality, the message passing towards node $v$ at layer $l$
is defined as below:

$h_{v}^{l+1}=\sigma(\bm{a}_{v}^{l}W^{l}),\,\,\bm{a}_{v}^{l}=g^{l}(h_{v}^{l},\\{h_{u}^{l}:u\in\mathcal{N}(v)\\}),$
(1)

where $h_{v}^{l}$ is the intermediate embedding of node $v$ at layer $l$,
$W^{l}$ denotes the trainable parameter at layer $l$, $\sigma$ denotes the
activation function, and $g^{l}$ is the aggregation function at layer $l$ that
collects information from neighbors $\mathcal{N}(v)$.

The node embedding in the final layer could be used for downstream tasks such
as node classification. For graph-level tasks such as graph classification, a
read-out function is further added to aggregate all node-level embeddings to
obtain a graph-level embedding $H_{\mathcal{G}}$ for the graph $\mathcal{G}$:

$H_{\mathcal{G}}=\text{READOUT}(\\{h_{v}^{L}:v\in\mathcal{V}\\}),$ (2)

where the $\text{READOUT}(\cdot)$ function can be a simple average function or
a carefully crafted pooling function [8].

Backdoor Attacks. The goal is to embed backdoors into the target model, where
the model is expected to perform normally on clean input, but behave
incorrectly if a trigger is present in the input graph during the inference
stage. The backdoor triggers could either be injected into the target label by
poisoning the dataset and luring the users to train on the dataset, or by
directly modifying the model weights. In this paper, we consider the former
situation.

Graph Classifier Training in Backdoor Attacks. A GNN-based classifier
$f_{\theta}:\mathcal{G}\rightarrow\mathbb{R}^{C}$ maps the input graph
$\mathcal{G}$ into its prediction distribution, where $C$ is the number of
classes. Let
$\mathcal{D}=\\{(\mathcal{G}_{1},y_{1}),(\mathcal{G}_{2},y_{2}),...,(\mathcal{G}_{n},y_{n})\\}$
denote the dataset, where $\mathcal{G}_{i}$ and $y_{i}$ denote the $i$-th
graph and its ground-truth label. In a standard machine learning paradigm,
$\mathcal{D}$ is usually divided into two parts: $\mathcal{D}_{train}$ and
$\mathcal{D}_{test}$, for training and testing, respectively. In the context
of backdoor attacks, $\mathcal{D}_{train}$ are injected with backdoor samples,
where
$\mathcal{D}_{train}=\mathcal{D}_{train}^{poi}\cup\mathcal{D}_{train}^{clean}$,
with $\mathcal{D}_{train}^{poi}$ denoting the backdoor subset and
$\mathcal{D}_{train}^{clean}$ denoting the clean subset. In this paper,
$\mathcal{D}_{train}$ specifically denotes a poisoned dataset with an
injection ratio of $\eta=|\mathcal{D}_{train}^{poi}|/|\mathcal{D}_{train}|$.
Then a target GNN classifier $f_{\theta}$ is trained over
$\mathcal{D}_{train}$ as follows,

$\theta=\operatorname*{arg\,min}_{\theta^{\prime}}\mathbb{E}_{(\mathcal{G},y)\sim\mathcal{D}_{train}}\ell(f_{\theta^{\prime}},\mathcal{G},y),$
(3)

where $\ell(\cdot)$ is the loss function on a single graph sample.

###  2.2 Threat Model

We define the threat model in two aspects: attacker and defender, following
previous work on backdoor detection [1, 14].

Figure 2: The pipeline of our proposed XGBD framework. After training
$f_{\theta}$ with $L_{trap}$, each graph in the dataset goes through the
explanation method, generating a set of explanatory subgraphs. After neighbor
expansion, the subgraphs are fed back into $f_{\theta}$, where samples with
loss value below threshold $\tau$ are detected as backdoor samples.

Attacker. We assume that the attackers have white-box access to the training
dataset $\mathcal{D}_{train}$, i.e., they can inject backdoor samples into the
training dataset. The attackers can construct backdoor samples with four
parameters: trigger size, trigger density, trigger synthesis method, and
injection ratio, where trigger size characterizes the ratio of nodes to be
poisoned, the trigger density describes the probability of choosing each
possible edge for the subgraph trigger, trigger synthesis method describes how
the trigger is generated, and the injection ratio is the parameter $\eta$
described above. To poison the training dataset, a random subgraph
$\mathcal{S}\subset\mathcal{G}$ is chosen for each victim sample
($\mathcal{G},y$) and replaced by the subgraph trigger $t$, along with its
label $y$ altered to the target label $\hat{y}$. We assume that the attackers
only poison the dataset but do not train the models on their own.

Defender. We assume that the defender has full access to the training dataset
$\mathcal{D}_{train}$. Given the $\mathcal{D}_{train}$, the defender’s goal is
to detect the backdoor samples. The defenders are assumed to have the
flexibility to pursue different methodologies in achieving this goal. For
example, they could train their own models or detectors over
$\mathcal{D}_{train}$.

##  3 Methodology

###  3.1 A Naïve Detection Method

When training the neural network on a mixture of backdoor samples and clean
samples, it was recently discovered that the losses on backdoor samples tend
to drop significantly faster than clean samples in the early epochs [20].
Based on the phenomenon, a naïve method of backdoor detection is to select the
top-k samples from $D_{train}$ with the lowest training loss during the early
training epochs. This intuitive method has been shown to be effective in image
classification [20]. However, its effectiveness is diminished when applied
directly to graph learning tasks. Figure 1 presents a preliminary example
showing the average training loss curve for the backdoor and clean samples for
different epochs. In the experiment, a GIN model [39] is trained on a poisoned
AIDS/ENZYMES training dataset $D_{train}$ with injection ratio $\eta=0.1$. We
track the average training loss for the backdoor samples and clean samples
shown in Figure 1, where the blue line represents the clean sample curve and
the red line represents the backdoor sample curve. However, the gap between
the two curves is not significant, so the backdoor samples cannot be easily
isolated. If we try to isolate 10% samples with the lowest values after
training with one epoch (since the average loss gap is the largest after the
first epoch), the precision of the isolated backdoor samples is only
$28.57\%/38.23\%$ for the two datasets, respectively. The possible reason
could be that subgraph triggers contain topological information, making them
harder to be learned by the model, compared to triggers in the image domain
(e.g., mosaic patches). To solve the problem, the question is _how to enlarge
the loss difference between backdoor samples and clean samples._

###  3.2 Topological Feature Filtering with Explanation

To this end, we propose to utilize explainability to guide the detection of
backdoor samples. Specifically, we adopt post-hoc local explanation methods as
feature filters to distinguish backdoor samples from clean samples. Given a
prediction $f_{\theta}(\mathcal{G})$, where $f_{\theta}$ is a trained GNN
model and $\mathcal{G}$ is an input graph, the goal of the explanation is to
extract a subgraph $\mathcal{G}^{*}\subset\mathcal{G}$ that preserves the most
important information of $\mathcal{G}$ to the prediction. In general, we try
to solve the following optimization problem via graph model explanation:

$\mathcal{G}^{*}=\operatorname*{arg\,max}_{|\mathcal{G}^{\prime}|\leq\Omega}\,\text{Score}(\mathcal{G},\mathcal{G}^{\prime},f_{\theta}),$
(4)

where $\Omega$ is the upper bound on the size of the explanatory subgraph
$\mathcal{G}^{*}$, and $\text{Score}(\cdot)$ is a scoring function that
measures the importance of the subgraph $\mathcal{G}^{\prime}$ to the original
graph $\mathcal{G}$ in the context of $f_{\theta}$. _The scoring function
prefers $\mathcal{G}^{*}$ that leads to the similar prediction as the original
graph $\mathcal{G}$._ For example, in SubgraphX [42], the scoring function is
designed as the Shapley values. The constraint
$|\mathcal{G}^{\prime}|\leq\Omega$ controls the size of the explanation
results, to promote the sparsity of $\mathcal{G}^{*}$ and avoid trivial
solutions such as $\mathcal{G}^{*}=\mathcal{G}$. Another relevant design of
explanation algorithms such as GNNExplainer [40] and PGExplainer [24] solves
the problem:

$\mathcal{G}^{*}=\operatorname*{arg\,max}_{\mathcal{G}^{\prime}}\,\text{Score}(\mathcal{G},\mathcal{G}^{\prime},f_{\theta})-\lambda\cdot
R(\mathcal{G}^{\prime}),\\\ $ (5)

where the previous explicit constraint is replaced by a regularization term
$\lambda\cdot R(\mathcal{G}^{\prime})$ controlling the complexity (e.g., size)
of $\mathcal{G}^{\prime}$, and $\lambda$ is the hyperparameter. In both
GNNExplainer and PGExplainer, the scoring function measures the mutual
information between predicting $\mathcal{G}$ and $\mathcal{G}^{\prime}$.

The proposed detection framework is shown in Figure 2. A graph model
$f_{\theta}$ is trained over $\mathcal{D}_{train}$, which serves as the
detector. We find that $f_{\theta}$ is prone to depend solely on trigger
patterns given backdoor samples, since backdoor triggers are created manually
and tend to be strong features learned by neural networks [22]. On the
contrary, clean samples usually depend on more natural and complex features.
Therefore, we leverage explanation methods to be used as “smart" filters,
where: 1) the explanation result $\mathcal{G}^{*}$ for a backdoor sample is
very likely to find the full trigger patterns, making $-\bm{y}\cdot
log(f_{\theta}(\mathcal{G}))\approx-\bm{y}\cdot
log(f_{\theta}(\mathcal{G}^{*}))$ for
$\mathcal{G}\in\mathcal{D}^{poi}_{train}$; 2) the key features for clean
samples are not well covered in $\mathcal{G}^{*}$, so that $-\bm{y}\cdot
log(f_{\theta}(\mathcal{G}))<-\bm{y}\cdot log(f_{\theta}(\mathcal{G}^{*}))$
for $\mathcal{G}\in\mathcal{D}^{clean}_{train}$. Such a difference could be
leveraged to distinguish between backdoor and clean instances.

How to Find a Desirable $\mathcal{G}^{*}$? The motivation of choosing
explanation comes from the commonly adopted guidelines of backdoor design [21,
9]. That is, attackers want the trigger patterns to be stealthy, which means
that the size of the trigger pattern should be small. Thus, we could set
$\Omega$ as a small value or make $\lambda$ large, so that: 1) backdoor
triggers are successfully extracted, and 2) explainable evidence in clean
samples is not fully extracted. Then, if we mask the training samples with
explanation results, the loss between backdoor samples and clean samples would
be distinguished. The above motivation is also supported by the following
empirical findings: Backdoor samples have a sparse attribution distribution,
where the trigger subgraph found by $\mathcal{G}^{*}$ almost has the same
prediction score as the entire graph; in contrast, clean samples have a
dispersed attribution distribution, where features not contained in the
subgraph $\mathcal{G}^{*}$ also have non-trivial contributions to the model
prediction.

How to Find a Desirable $f_{\theta}$? Our backdoor detector is based on
$f_{\theta}$, which is trained over the dataset $\mathcal{D}_{train}$. A
desirable $f_{\theta}$ is expected to well fit the backdoor samples, but
mediocrely fit the clean samples. This is because such a model $f_{\theta}$
will amplify the loss gap between backdoor samples and clean samples, making
the backdoor samples more isolated in the latent space. To achieve this, we
propose the following loss function:

$L_{trap}=\mathbb{E}_{(\mathcal{G},y)\sim\mathcal{D}_{train}}(\ell(f_{\theta},\mathcal{G},y)-\gamma)^{2},$
(6)

where $\gamma$ is the loss threshold and $\ell(\cdot)$ is the loss function on
a single example. The $L_{trap}$ loss function is a quadratic version of the
original loss with the axis of symmetry at $\gamma$. When a neural network
$f_{\theta}$ is trained with $L_{trap}$, the loss on most samples will be
trapped around $\gamma$. However, because the learning task on backdoor
samples is relatively easier, the loss on backdoor samples will not be trapped
and can still achieve a low value. In this way, the backdoor samples show
distinguished loss values over the clean samples.

###  3.3 One-hop Neighbor Expansion

We further present a simple but effective step, i.e., slightly expanding the
extracted subgraph, to increase the likelihood that the trigger is covered by
the explanatory subgraph. The neighbor nodes, which are topologically close to
the extracted subgraph $\mathcal{G}^{*}$, are the best candidates to be
selected. Formally, for an extracted subgraph
$\mathcal{G}^{*}=(\mathcal{V}^{*},\mathcal{E}^{*},\mathcal{X}^{*})$, it is
expanded to a graph
$\tilde{\mathcal{G}}=(\tilde{\mathcal{V}},\tilde{\mathcal{E}},\tilde{\mathcal{X}})$
with

$\begin{split}&\tilde{\mathcal{V}}=\\{v|v\in\mathcal{N}({\mathcal{G}^{*}})\cup\mathcal{V}^{*}\\},\\\
&\tilde{\mathcal{E}}=\\{(i,j)|i\in\mathcal{V}^{*}\vee
j\in\mathcal{V}^{*},\forall(i,j)\in\mathcal{E}\\},\\\
&\tilde{\mathcal{X}}=\\{x|x\in\mathcal{X}(\mathcal{N}({\mathcal{G}^{*}}))\cup\mathcal{X}(\mathcal{G}^{*})\\},\end{split}$
(7)

where $\mathcal{E}$ denotes the edge set of the entire graph.

###  3.4 Loss Computation

Following the above steps, we have obtained a dataset of subgraphs
$\hat{\mathcal{D}}=\\{(\tilde{\mathcal{G}}_{1},y_{1}),(\tilde{\mathcal{G}}_{2},y_{2}),...,(\tilde{\mathcal{G}}_{n},y_{n})\\}$.
Then, we compute the loss value on each sample
$(\tilde{\mathcal{G}}_{i},y_{i})$.

$\ell(f_{\theta},\tilde{\mathcal{G}}_{i},y_{i})=-\bm{y}_{i}\cdot
log(f_{\theta}(\tilde{\mathcal{G}}_{i})),$ (8)

where $\bm{y}_{i}\in\\{0,1\\}^{C}$ denotes the one-hot vector with the
$y_{i}$-th component as one and the remaining components as zero. To identify
the backdoor samples, we simply compare the loss on the samples to a
predefined threshold $\tau$. The choices for $\tau$ will be shown in the
experiment part. The backdoor samples are detected as:

$\mathcal{D}_{backdoor}=\\{\tilde{\mathcal{G}}_{i}|\ell(f_{\theta},\tilde{\mathcal{G}}_{i},y_{i})\leq\tau,\forall
i\in[1,n]\\}.$ (9)

We formalize the whole process in Algorithm 1.

Algorithm 1 The XGBD backdoor detection framework.

Input: Dataset
$\mathcal{D}_{train}=\\{(\mathcal{G}_{1},y_{1}),...,(\mathcal{G}_{n},y_{n})\\}$;
detection threshold $\tau$.

Train a model $f_{\theta}$ over $\mathcal{D}_{train}$ with loss in Equation 6.

for $i=1$ to $n$ do

Obtain subgraph $\mathcal{G}^{*}_{i}$ for each
$(\mathcal{G}_{i},y_{i})\in\mathcal{D}_{train}$.

Expand subgraph $\mathcal{G}_{i}^{*}$ to $\tilde{\mathcal{G}}_{i}$ following
Equation 7.

Compute the loss Value on $\tilde{\mathcal{G}}_{i}$ following Equation 8.

end for

Detect backdoor samples following Equation 9.

##  4 Experiments

In this section, we conduct multiple experiments to answer the following
research questions. RQ1: How effective is the proposed detection method
compared to baseline methods? RQ2: What is the impact of hyperparameters on
the effectiveness of the proposed detection method? RQ3: Why is the proposed
method effective in detecting backdoor samples? RQ4: What is the computational
efficiency of the proposed method?

###  4.1 Experimental Settings

Graph Datasets. We evaluate our approach on three real-world graph datasets,
where the basic statistics are given in Table 1.

  * •

MUTAG [4] is a collection of nitroaromatic compounds and the goal is to
predict whether they would have a mutagenic effect on Salmonella typhimurium.

  * •

AIDS [26] contains 2000 chemical compounds. The goal is to predict whether the
molecules have activity against HIV or not.

  * •

ENZYMES [25] is a dataset containing six different protein tertiary
structures. The task is to predict the class of each protein structure.

Table 1: Basic statistics of the three datasets. Dataset | Graphs | Classes | Avg. Nodes | Avg. Edges
---|---|---|---|---
MUTAG | 188 | 2 | 17.93 | 19.79
AIDS | 2000 | 2 | 15.69 | 16.20
ENZYMES | 600 | 6 | 32.63 | 62.14
Table 2: The detection accuracy (Accuracy) and area under curve (AUC) of
backdoor detection methods against different attacks.

Dataset | Attack Method | AC | ABL | ExD | Ours
---|---|---|---|---|---
Accuracy | AUC | Accuracy | AUC | Accuracy | AUC | Accuracy | AUC
MUTAG | BadGraph | $0.91_{\pm 0.02}$ | - | $0.89_{\pm 0.02}$ | $0.84_{\pm 0.10}$ | $0.44_{\pm 0.18}$ | $0.61_{\pm 0.06}$ | $\textbf{0.98}_{\pm\textbf{0.02}}$ | $\textbf{0.94}_{\pm\textbf{0.08}}$
ExA | $0.91_{\pm 0.01}$ | - | $0.91_{\pm 0.02}$ | $0.87_{\pm 0.02}$ | $0.60_{\pm 0.24}$ | $0.65_{\pm 0.09}$ | $\textbf{0.92}_{\pm\textbf{0.04}}$ | $\textbf{0.90}_{\pm\textbf{0.07}}$
GTA | $0.90_{\pm 0.02}$ | - | $0.88_{\pm 0.01}$ | $0.76_{\pm 0.02}$ | $0.64_{\pm 0.19}$ | $0.66_{\pm 0.09}$ | $\textbf{0.97}_{\pm\textbf{0.02}}$ | $\textbf{0.88}_{\pm\textbf{0.04}}$
AIDS | BadGraph | $0.91_{\pm 0.03}$ | - | $0.89_{\pm 0.02}$ | $\textbf{0.83}_{\pm\textbf{0.13}}$ | $0.88_{\pm 0.04}$ | $0.62_{\pm 0.06}$ | $\textbf{0.93}_{\pm\textbf{0.04}}$ | $0.78_{\pm 0.13}$
ExA | $0.92_{\pm 0.03}$ | - | $0.89_{\pm 0.02}$ | $0.84_{\pm 0.11}$ | $0.91_{\pm 0.03}$ | $0.63_{\pm 0.05}$ | $\textbf{0.93}_{\pm\textbf{0.01}}$ | $\textbf{0.84}_{\pm\textbf{0.03}}$
GTA | $0.88_{\pm 0.03}$ | - | $0.89_{\pm 0.01}$ | $\textbf{0.84}_{\pm\textbf{0.11}}$ | $0.87_{\pm 0.03}$ | $0.60_{\pm 0.06}$ | $\textbf{0.96}_{\pm\textbf{0.01}}$ | $0.74_{\pm 0.03}$
ENZYMES | BadGraph | $0.93_{\pm 0.04}$ | - | $0.89_{\pm 0.05}$ | $0.83_{\pm 0.10}$ | $0.92_{\pm 0.03}$ | $0.63_{\pm 0.04}$ | $\textbf{0.96}_{\pm\textbf{0.02}}$ | $\textbf{0.96}_{\pm\textbf{0.01}}$
ExA | $0.91_{\pm 0.01}$ | - | $0.89_{\pm 0.01}$ | $0.84_{\pm 0.03}$ | $0.91_{\pm 0.02}$ | $0.58_{\pm 0.02}$ | $\textbf{0.94}_{\pm\textbf{0.03}}$ | $\textbf{0.87}_{\pm\textbf{0.09}}$
GTA | $0.90_{\pm 0.01}$ | - | $0.88_{\pm 0.02}$ | $0.67_{\pm 0.09}$ | $0.76_{\pm 0.13}$ | $0.54_{\pm 0.04}$ | $\textbf{0.93}_{\pm\textbf{0.04}}$ | $\textbf{0.88}_{\pm\textbf{0.05}}$

  * •

\- AC uses binary clustering to detect backdoor samples, which does not
incorporate any threshold value for computing AUC.

Attack Methods. We consider three state-of-the-art backdoor attack methods:
BadGraph [44], GTA [36], and Explainability-based Attack [38]. The
configurations for these attack methods are introduced as follows:

  * •

BadGraph [44]. This attack involves injecting a subgraph trigger into a graph.
For all experiments, the subgraph trigger is generated by the Erdős-Rényi (ER)
model [11], and the poisoned nodes are randomly selected from the node set of
the graph.

  * •

GTA [36]. We train a topology generator and a feature generator for five
epochs respectively, which can be utilized to generate a series of candidate
backdoor triggers. Then a bi-level optimization problem is solved iteratively
to poison the victim graphs with the backdoor triggers. For all the
experiments, we set the number of epochs as 20 for the bi-level optimization.

  * •

Explainability-based Attack (ExA) [38]. We first adopt GraphExplainer [40] to
generate a node importance matrix for each victim graph with a pre-trained
model. Then the nodes with top-$k$ highest importance values are replaced by
the subgraph trigger, where $k$ denotes the number of poisoned nodes.

Baseline Defense Methods. We select three backdoor defense methods as our
defense baselines. First, we consider Explainability-based Defense (ExD) [18],
an existing defense method designed especially for GNN backdoor attacks.
Furthermore, we adopt two detection methods developed for image data to the
graph domain, including Activation Clustering (AC) [1] and Anti-backdoor
Learning (ABL) [20]. The details of the defense baselines are given as
follows:

  * •

ExD: Our implementation follows the algorithms described in [18].
Specifically, they adopt explanation methods to generate a subgraph mask and
thereby calculate an Explainability Score (ES) to distinguish the backdoor
samples and clean samples. We follow the settings in the original paper,
adopting GNNExplainer as the explanation method and using an additional
validation set $\mathcal{D}_{val}\subset\mathcal{D}_{test}$ to calculate the
decision boundary by default.

  * •

Activation Clustering: Our implementation follows the detection algorithms
described in [1]. Specifically, we select a fully-connected layer to compute
the activation values and use an ICA algorithm to perform dimensionality
reduction on the activation values. Then we adopt a K-NN algorithm with k = 2
to cluster the activation values. The cluster whose size is relatively smaller
will be considered as the backdoor cluster, within which all the samples are
detected as backdoor samples. Please note that, according to the original
paper, if the size of the smaller cluster is greater than p%, then all samples
will be considered as clean. In all experiments, p is set as 15 by default.

  * •

ABL: Our implementation follows the open-source
code111https://github.com/bboylyg/ABL. Specifically, we train the GNNs with
the proposed LGA loss for 20 epochs, which is observed to be able to achieve
the optimal isolation precision rate in the Cifar10 dataset. Then we classify
the samples with the top 10% lowest values as the backdoor samples, and the
others as the clean samples. Please note that the LGA loss function is
formulated as follows:

$LGA=(loss-\gamma)\cdot loss,$ (10)

where $\gamma$ is set as 0.5 by default and $loss$ is the cross-entropy loss.

Evaluation Metrics. To evaluate backdoor detection performance, we adopt two
commonly used metrics [19, 13, 6]: 1) Detection Accuracy (Accuracy), which
measures the proportion of correctly identified samples; 2) The Area under
Receiver Operating Curve (AUC), which measures the trade-off between the
detection error rate for clean samples and the detection success rate for
backdoor samples.

###  4.2 RQ1: Backdoor Detection Performance

Implementation Details. For all attack experiments, we use GIN [39] as the GNN
network architecture with a learning rate of 0.01 and training epochs of 100.
We use the cross-entropy function as the loss function $\ell$. The default
settings for the attack methods follow [44]: trigger density $d=0.8$ and
trigger size $t=0.2$, where trigger density is used to determine the
probability of choosing each edge for the subgraph trigger and trigger size is
used to determine the number of nodes in the subgraph trigger. Given a dataset
$\mathcal{D}_{train}$ with an average node number $\mathcal{N}_{avg}$, the
number of nodes in the subgraph trigger is equal to
$\mathcal{N}_{avg}\times\text{trigger size}$. Furthermore, we select the
poisoning ratio as $\eta=10\%$ following [20]. For the three evaluated
datasets, the loss values on subgraph samples are nearly close to zero, while
those on the clean samples are significantly larger, so we choose a small
threshold $\tau=1e{-5}$ for the three datasets. The size constraint on the
explanatory subgraph is $\Omega=4$ for MUTAG and AIDS dataset, and $\Omega=6$
for the ENZYMES dataset. The loss threshold $\gamma$ in Equation 6 is chosen
as 0.5. Besides, we adopt subgraphX [42] as the explanation method by default.
The ablation studies on these hyperparameters will be conducted in later
subsections.

Comparing with Baselines. To evaluate the effectiveness of XGBD, we compare it
with the three baseline methods. Table 2 presents our main results. As shown,
XGBD achieves a satisfactory performance for all experimental instances. In
contrast, despite that other baseline methods sometimes achieve a
comparatively higher AUC value than XGBD, the overall performance still
implies that they are less effective than XGBD. Compared to AC and ABL, the
advantage of XGBD comes from the use of topological information in graph data.
Specifically, our explanation-based topological feature filter effectively
distinguishes between backdoor samples and clean samples. Compared to ExD, the
advantage comes from our exploration for the detector function $f_{\theta}$,
which effectively enlarges the loss gap with the proposed trap training loss
function.

###  4.3 RQ2: Ablation Studies

Impact of Explanation Methods.

Table 3: The detection accuracy (Accuracy) and area under curve (AUC) of XGBD
with different explanation methods.

Dataset | Attack Method | SubgraphX | GNNExplainer | PGExplainer
---|---|---|---|---
Accuracy | AUC | Accuracy | AUC | Accuracy | AUC
MUTAG | BadGraph | $0.98_{\pm 0.02}$ | $0.94_{\pm 0.08}$ | $0.97_{\pm 0.03}$ | $0.93_{\pm 0.06}$ | $0.97_{\pm 0.02}$ | $0.93_{\pm 0.03}$
ExA | $0.92_{\pm 0.04}$ | $0.90_{\pm 0.07}$ | $0.96_{\pm 0.01}$ | $0.80_{\pm 0.12}$ | $0.96_{\pm 0.02}$ | $0.81_{\pm 0.10}$
GTA | $0.97_{\pm 0.02}$ | $0.88_{\pm 0.04}$ | $0.94_{\pm 0.03}$ | $0.85_{\pm 0.06}$ | $0.92_{\pm 0.03}$ | $0.92_{\pm 0.01}$
AIDS | BadGraph | $0.93_{\pm 0.04}$ | $0.78_{\pm 0.13}$ | $0.91_{\pm 0.07}$ | $0.76_{\pm 0.17}$ | $0.93_{\pm 0.01}$ | $0.86_{\pm 0.10}$
ExA | $0.93_{\pm 0.01}$ | $0.87_{\pm 0.02}$ | $0.92_{\pm 0.02}$ | $0.74_{\pm 0.02}$ | $0.93_{\pm 0.02}$ | $0.84_{\pm 0.04}$
GTA | $0.96_{\pm 0.01}$ | $0.74_{\pm 0.03}$ | $0.93_{\pm 0.01}$ | $0.73_{\pm 0.05}$ | $0.94_{\pm 0.01}$ | $0.77_{\pm 0.05}$
ENZYMES | BadGraph | $0.96_{\pm 0.02}$ | $0.96_{\pm 0.01}$ | $0.95_{\pm 0.04}$ | $0.92_{\pm 0.07}$ | $0.95_{\pm 0.05}$ | $0.81_{\pm 0.18}$
ExA | ${0.94}_{\pm{0.03}}$ | ${0.87}_{\pm{0.09}}$ | $0.94_{\pm 0.01}$ | $0.80_{\pm 0.12}$ | $0.96_{\pm 0.01}$ | $0.81_{\pm 0.10}$
GTA | ${0.93}_{\pm{0.04}}$ | ${0.88}_{\pm{0.05}}$ | $0.93_{\pm 0.03}$ | $0.85_{\pm 0.06}$ | $0.92_{\pm 0.02}$ | $0.92_{\pm 0.01}$
| Avg Ranking $\downarrow$ | 1.67 | 1.44 | 2.22 | 2.89 | 2.11 | 1.67

We select GNNExplainer [40], PGExplainer [24], and SubgraphX [42] as the
explanation methods. Table 3 presents the performance of XGBD with different
explanation methods. To compare the three explanation methods, we calculate
their rankings of Accuracy and AUC for each experimental instance and finally
report the average ranking value. As shown, XGBD achieves the highest average
ranking for Accuracy and AUC with SubgraphX [42], indicating that SubgraphX
could provide a relatively more stable and effective performance.

Impact of Trigger Size.

Figure 3: The impact of trigger size.

Figure 3 presents the impact of trigger size under different attack methods in
the MUTAG dataset. The X-axis denotes the trigger size, ranging from 15% to
40% of the original graph size, and the Y-axis denotes the Accuracy/AUC value.
The blue line denotes the accuracy curve and the red line denotes the AUC
curve. The standard deviation band is also plotted. We could observe that, for
all three attack methods, XGBD achieves a satisfactory performance when the
trigger size is at different levels. Furthermore, the performance of XGBD
tends to be more stable and significant with increasing trigger size. This
happens because as the trigger size increases, the subgraph trigger becomes
stronger, making the attribution distribution more concentrated on the
subgraph trigger.

Impact of Trigger Density. Figure 4 presents the impact of trigger density
under different attack methods in the MUTAG dataset. The X-axis denotes the
trigger density, ranging from 0.5 to 1.0. As GTA [36] adopts dynamic trigger
patterns, we only compare the performance under BadGraph and ExA. As
demonstrated, as the trigger density increases, the performance of XGBD under
the two attack methods becomes stronger and more stable. The reasons for this
are consistent with the findings of the trigger size impact analysis: the
trigger pattern feature becomes stronger.

Figure 4: The impact of trigger density.

Impact of Injection Ratio $\eta$.

Figure 5: The impact of injection ratio.

Since the number of backdoor samples in the training data is unpredictable, we
evaluate the effectiveness of XGBD under different injection ratios in Figure
5. The X-axis denotes the poisoning ratio, and the Y-axis denotes the
Accuracy/AUC value. It is shown that our proposed method effectively detects
backdoor samples under different poisoning ratios.

Impact of Detection Threshold $\tau$. We evaluate the effectiveness of XGBD
under three different attack methods with different thresholds $\tau$ on the
three datasets. Figure 6 presents the experiment results. The X-axis denotes
the threshold value, and the Y-axis denotes the accuracy value. XGBD works
well and stably under a wide range of $\tau$ values below 0.01.

Figure 6: Accuracy with different threshold values $\tau$ over MUTAG dataset
(first row), AIDS dataset (second row), and ENZYMES dataset (third row).
Figure 7: The impact of $\gamma$ value.

Impact of Loss Threshold $\gamma$. Figure 7 presents the performance of XGBD
when training with different $\gamma$ values. As shown in the figure, the
Accuracy value and AUC value generally become more unstable with the increase
of the $\gamma$ value, and a $\gamma$ value between 0.1 and 0.5 generates a
satisfactory result.

###  4.4 RQ3: Why is XGBD Effective?

Explanation Visualizations. To better understand how XGBD helps to detect the
backdoor samples, we visualize the results of the explanation method in Figure
8. It presents the identified subgraphs of backdoor samples in the MUTAG
dataset. The backdoor samples in the first row are poisoned with a trigger of
size three, and those in the second row are poisoned with a trigger of size
four. We use red circles to denote poisoned nodes and bold edges to highlight
identified subgraphs. As shown, the identified subgraphs align very well with
the real poisoned nodes. This is because backdoor models rely almost entirely
on the trigger pattern to make predictions when the trigger appears in the
input graph.

Loss Distribution. Figure 9 presents the distribution of loss values computed
from the backdoor subgraphs (blue) and the clean subgraphs (red),
respectively. As shown, the loss values of all the backdoor subgraphs are less
than 0.005, while the loss values of over 99% clean subgraphs are higher than
0.005. Therefore, as discussed above, if we set the threshold $\tau$ as a
small value such as $1e{-5}$, then the method would effectively separate
backdoor and clean samples.

Component Contributions. Table 4 presents the contributions of the XGBD
components. The first row represents the scenario in which no explanation
methods or subgraph expansion are used, and instead, the training loss is used
to identify backdoor samples. The second row corresponds to the scenario in
which the explanation method is used, but the subgraph expansion and trap loss
are not used. The third row corresponds to the scenario where the explanation
method and subgraph expansion are used, but the trap loss is not used.
Finally, the fourth row corresponds to the fully-implemented XGBD. As can be
seen, the proposed XGBD performs better as more components are included,
indicating the importance of all three key components.

Figure 8: Visualization of identified subgraphs (highlighted by bold lines) by
SubgraphX. The true poisoned nodes are in the red circle. Figure 9:
Distribution of loss values on explanatory subgraphs from backdoor samples and
clean samples. Table 4: The effects of XGBD components on ablation results.

Explainability Method | Subgraph Expansion | Trap Loss $L_{trap}$ | Accuracy | AUC
---|---|---|---|---
- | - | - | $0.91_{\pm 0.04}$ | $0.81_{\pm 0.03}$
✓ | - | - | $0.93_{\pm 0.02}$ | $0.92_{\pm 0.03}$
✓ | ✓ | - | $0.95_{\pm{0.05}}$ | $0.93_{\pm 0.05}$
✓ | ✓ | ✓ | $\textbf{0.98}_{\pm\textbf{0.02}}$ | $\textbf{0.94}_{\pm\textbf{0.08}}$

###  4.5 RQ4: Running Time Efficiency

In this section, we empirically analyze the running time efficiency of XGBD.
Table 5 compares the average running time of XGBD with different explanation
methods. As shown, when integrating XGBD with an efficient explanation method,
such as PGExplainer, the efficiency of XGBD can be guaranteed. For
acceleration, the computation on different graph queries could be run in
parallel in practice.

Table 5: Average time (second/sample) consumption.

Method | MUTAG | AIDS | ENZYMES
---|---|---|---
XGBD-PGExplainer | 0.95 | 0.63 | 1.12
XGBD-GNNExplainer | 6.11 | 5.98 | 6.35
XGBD-SubgraphX | 25.62 | 23.21 | 87.81

##  5 Related Work

###  5.1 Backdoor Attacks

Backdoor attacks aim to poison the training dataset with trigger patterns or
manipulate the weights and structures of the model directly [31]. BadNet first
proposed backdoor attacks [12] in the image domain, where they use grid-like
patterns as triggers. After training on the poisoned dataset, the backdoor
model will continuously predict the target label when the trigger is present
in the input image but behaves normally when the input is clean. Following
this, many methods are proposed to strengthen attacks by making trigger
patterns more stealthy. For example, [28] proposes a clean-label attack, which
perturbs the clean images without changing their labels. Recently, it has been
found that backdoor attacks can also be launched in the graph classification
task [44, 36]. Simply put, the trigger is a subgraph. When the input graph
contains such a subgraph, the prediction would be the target label. When the
input graph is clean, the GNN will behave normally. [44] uses a fixed subgraph
to poison the training dataset, where the subgraph is generated randomly and
the poisoned nodes of each graph are also generated randomly. [38] applies a
pre-trained GNN to search for the most vulnerable nodes to be poisoned. [36]
solves a bi-optimization problem to make the injected subgraph more stealthy.

###  5.2 Backdoor Defense

Various methods have been proposed to defend against backdoor attacks in the
image domain. As in [21], we categorize existing defense methods into five
categories. First, detection-based methods [10, 37] detect whether the
backdoor exists in the model by scanning the model prediction or neuron
activation values. Second, preprocessing-based methods [5] introduce a data
preprocessing module to inactivate backdoors. Third, model reconstruction
based defenses [23, 43, 33] directly eliminate the effects of backdoors by
adjusting weights or structures. Fourth, trigger-synthesis-based defenses [32,
29] synthesize the trigger patterns from the victim DNN model and unlearn the
patterns learned by the model. Lastly, training sample filtering based
defenses [20, 16] work by first filtering backdoor samples from the poisoned
dataset, then training the network exclusively in the rest of the dataset.

Some of the above methods can be directly adapted to the graph domain [1, 20].
However, limited research has been conducted on the backdoor defenses
specially designed for the graph domain. To the best of our knowledge, [18] is
the only paper that focuses on removing backdoors in GNNs. In their work, they
propose to use an explanation score as the decision criterion for
discriminating backdoor samples and clean samples.

##  6 Conclusions and Future Work

This paper tackles the backdoor detection problem in the graph domain, by
leveraging explanation methods to identify discriminative topological
features. Extensive experiments across three popular graph datasets
demonstrate the efficacy of our method across a set of popular tasks and
state-of-the-art graph backdoor attacks. Despite the satisfactory performance
in detecting backdoor samples, there are still some future works to be done in
the research direction. The first one is how to speed up the detection
process. Our current detection algorithm sequentially iterates all the
training samples, which may take a considerable amount of time when the size
of the training dataset becomes significantly large. Therefore, we will
consider implementing a parallel version in the future. The second one is how
to determine the hyper-parameter: threshold value $\tau$. It would be
promising if we determine the value $\tau$ by utilizing some properties of the
dataset in an automated way.

This work is in part supported by NSF (#IIS-2223768). The views and
conclusions contained in this paper are those of the authors and should not be
interpreted as representing any funding agencies.

## References

  * [1] Bryant Chen, Wilka Carvalho, Nathalie Baracaldo, Heiko Ludwig, Benjamin Edwards, Taesung Lee, Ian Molloy, and Biplav Srivastava.  Detecting backdoor attacks on deep neural networks by activation clustering, 2018.
  * [2] Kangjie Chen, Xiaoxuan Lou, Guowen Xu, Jiwei Li, and Tianwei Zhang, ‘Clean-image backdoor: Attacking multi-label models with poisoned labels only’, in The Eleventh International Conference on Learning Representations, (2023).
  * [3] Sheng-Yen Chou, Pin-Yu Chen, and Tsung-Yi Ho, ‘How to backdoor diffusion models?’, in ICLR 2023 Workshop on Backdoor Attacks and Defenses in Machine Learning, (2022).
  * [4] Asim Kumar Debnath, Rosa L. Lopez de Compadre, Gargi Debnath, Alan J. Shusterman, and Corwin Hansch, ‘Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity’, Journal of Medicinal Chemistry, 34(2), 786–797, (1991).
  * [5] Bao Gia Doan, Ehsan Abbasnejad, and Damith C. Ranasinghe, ‘Februus: Input purification defense against trojan attacks on deep neural network systems’, in Annual Computer Security Applications Conference, ACSAC ’20, p. 897–912, New York, NY, USA, (2020). Association for Computing Machinery.
  * [6] Yinpeng Dong, Xiao Yang, Zhijie Deng, Tianyu Pang, Zihao Xiao, Hang Su, and Jun Zhu.  Black-box detection of backdoor attacks with limited information and data, 2021.
  * [7] Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur, ‘Protein interface prediction using graph convolutional networks’, in Advances in Neural Information Processing Systems, eds., I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, volume 30. Curran Associates, Inc., (2017).
  * [8] Hongyang Gao and Shuiwang Ji.  Graph u-nets, 2019.
  * [9] Yansong Gao, Bao Gia Doan, Zhi Zhang, Siqi Ma, Jiliang Zhang, Anmin Fu, Surya Nepal, and Hyoungshick Kim, ‘Backdoor attacks and countermeasures on deep learning: A comprehensive review’, arXiv preprint arXiv:2007.10760, (2020).
  * [10] Yansong Gao, Chang Xu, Derui Wang, Shiping Chen, Damith C. Ranasinghe, and Surya Nepal, ‘Strip: A defence against trojan attacks on deep neural networks’, (2019).
  * [11] Edgar N Gilbert, ‘Random graphs’, The Annals of Mathematical Statistics, 30(4), 1141–1144, (1959).
  * [12] Tianyu Gu, Brendan Dolan-Gavitt, and Siddharth Garg, ‘Badnets: Identifying vulnerabilities in the machine learning model supply chain’, arXiv preprint arXiv:1708.06733, (2017).
  * [13] Junfeng Guo, Ang Li, and Cong Liu.  Aeva: Black-box backdoor detection using adversarial extreme value analysis, 2021.
  * [14] Jonathan Hayase, Weihao Kong, Raghav Somani, and Sewoong Oh.  Spectre: Defending against backdoor attacks using robust statistics, 2021\.
  * [15] Jonathan Hayase and Sewoong Oh, ‘Few-shot backdoor attacks via neural tangent kernels’, arXiv preprint arXiv:2210.05929, (2022).
  * [16] Kunzhe Huang, Yiming Li, Baoyuan Wu, Zhan Qin, and Kui Ren, ‘Backdoor defense via decoupling the training process’, arXiv preprint arXiv:2202.03423, (2022).
  * [17] Xijie Huang, Moustafa Alzantot, and Mani Srivastava.  Neuroninspect: Detecting backdoors in neural networks via output explanations, 2019.
  * [18] Bingchen Jiang and Zhao Li.  Defending against backdoor attack on graph nerual network by explainability, 2022.
  * [19] Soheil Kolouri, Aniruddha Saha, Hamed Pirsiavash, and Heiko Hoffmann.  Universal litmus patterns: Revealing backdoor attacks in cnns, 2019.
  * [20] Yige Li, Xixiang Lyu, Nodens Koren, Lingjuan Lyu, Bo Li, and Xingjun Ma.  Anti-backdoor learning: Training clean models on poisoned data, 2021.
  * [21] Yiming Li, Yong Jiang, Zhifeng Li, and Shu-Tao Xia.  Backdoor learning: A survey, 2020.
  * [22] Junyu Lin, Lei Xu, Yingqi Liu, and Xiangyu Zhang, ‘Composite backdoor attack for deep neural network by mixing existing benign features’, in Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, CCS ’20, p. 113–131, New York, NY, USA, (2020). Association for Computing Machinery.
  * [23] Kang Liu, Brendan Dolan-Gavitt, and Siddharth Garg.  Fine-pruning: Defending against backdooring attacks on deep neural networks, 2018.
  * [24] Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang, ‘Parameterized explainer for graph neural network’, Advances in Neural Information Processing Systems, 33, (2020).
  * [25] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann.  Tudataset: A collection of benchmark datasets for learning with graphs, 2020.
  * [26] Ryan A. Rossi and Nesreen K. Ahmed, ‘The network data repository with interactive graph analytics and visualization’, in AAAI, (2015).
  * [27] Alvaro Sanchez-Gonzalez, Nicolas Heess, Jost Tobias Springenberg, Josh Merel, Martin Riedmiller, Raia Hadsell, and Peter Battaglia.  Graph networks as learnable physics engines for inference and control, 2018.
  * [28] Ali Shafahi, W. Ronny Huang, Mahyar Najibi, Octavian Suciu, Christoph Studer, Tudor Dumitras, and Tom Goldstein.  Poison frogs! targeted clean-label poisoning attacks on neural networks, 2018.
  * [29] Guangyu Shen, Yingqi Liu, Guanhong Tao, Shengwei An, Qiuling Xu, Siyuan Cheng, Shiqing Ma, and Xiangyu Zhang.  Backdoor scanning for deep neural networks through k-arm optimization, 2021.
  * [30] Yucheng Shi, Kaixiong Zhou, and Ninghao Liu, ‘Engage: Explanation guided data augmentation for graph representation learning’, in ECML-PKDD, (2023).
  * [31] Ruixiang Tang, Mengnan Du, Ninghao Liu, Fan Yang, and Xia Hu, ‘An embarrassingly simple approach for trojan attack in deep neural networks’, in Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 218–228, (2020).
  * [32] Bolun Wang, Yuanshun Yao, Shawn Shan, Huiying Li, Bimal Viswanath, Haitao Zheng, and Ben Y. Zhao, ‘Neural cleanse: Identifying and mitigating backdoor attacks in neural networks’, in 2019 IEEE Symposium on Security and Privacy (SP), pp. 707–723, (2019).
  * [33] Dongxian Wu and Yisen Wang, ‘Adversarial neuron pruning purifies backdoored deep models’, in Advances in Neural Information Processing Systems, eds., M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, volume 34, pp. 16913–16925. Curran Associates, Inc., (2021).
  * [34] Yongji Wu, Defu Lian, Yiheng Xu, Le Wu, and Enhong Chen, ‘Graph convolutional networks with markov random field reasoning for social spammer detection’, Proceedings of the AAAI Conference on Artificial Intelligence, 34(01), 1054–1061, (Apr. 2020).
  * [35] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip, ‘A comprehensive survey on graph neural networks’, IEEE transactions on neural networks and learning systems, 32(1), 4–24, (2020).
  * [36] Zhaohan Xi, Ren Pang, Shouling Ji, and Ting Wang.  Graph backdoor, 2020.
  * [37] Zhen Xiang, David J. Miller, and George Kesidis.  Post-training detection of backdoor attacks for two-class and multi-attack scenarios, 2022.
  * [38] Jing Xu, Xue Minhui, and Stjepan Picek.  Explainability-based backdoor attacks against graph neural networks, 2021\.
  * [39] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?, 2018.
  * [40] Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec.  Gnnexplainer: Generating explanations for graph neural networks, 2019\.
  * [41] Yi Yu, Yufei Wang, Wenhan Yang, Shijian Lu, Yap-peng Tan, and Alex C Kot, ‘Backdoor attacks against deep image compression via adaptive frequency trigger’, arXiv preprint arXiv:2302.14677, (2023).
  * [42] Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji.  On explainability of graph neural networks via subgraph explorations, 2021\.
  * [43] Yi Zeng, Si Chen, Won Park, Zhuoqing Mao, Ming Jin, and Ruoxi Jia, ‘Adversarial unlearning of backdoors via implicit hypergradient’, in International Conference on Learning Representations, (2021).
  * [44] Zaixi Zhang, Jinyuan Jia, Binghui Wang, and Neil Zhenqiang Gong, ‘Backdoor attacks to graph neural networks’, in Proceedings of the 26th ACM Symposium on Access Control Models and Technologies, SACMAT ’21, p. 15–26, New York, NY, USA, (2021). Association for Computing Machinery.
  * [45] Ziwei Zhang, Peng Cui, and Wenwu Zhu, ‘Deep learning on graphs: A survey’, IEEE Transactions on Knowledge and Data Engineering, (2020).
  * [46] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun, ‘Graph neural networks: A review of methods and applications’, AI Open, 1, 57–81, (2020).


So-called $N$-body problems arise in many areas (e.g. astrophysics, molecular
dynamics, vortex methods, electrostatics). In these problems, the system is
described by a set of $N$ particles, and the dynamics of the system is the
result of the interactions that occur for every pair of particles. To
calculate all such interactions, the total number of operations required
normally scales as $N^{2}$. One useful way to mathematically express an
$N$-body problem is by means of a matrix-vector multiplication, where the
matrix is dense and represents the particle interactions, and the vector
corresponds to the weights of the particles. Thus, the mat-vec product
corresponds to the evaluation of all pairwise interactions. In a naive
implementation, we would directly create the matrix in computer memory and
then perform the multiplication with the vector. This naive approach would
prove feasible only for small $N$, as the computational requirements in
processing power and memory both grow as $N^{2}$. For this reason, many
efforts have been directed at producing efficient implementations, capable of
performing the mat-vec operation at reduced memory requirements and operation
counts.

The various methods for more efficient calculation of the particle interaction
problem can be broadly classified in two types: mesh-based interpolation
methods, and hierarchical or multiresolution methods. The basic mesh-based
method is the particle-mesh (pm) approach, in which particle information is
interpolated onto a lattice, the field of interest is solved on the mesh by
means of some grid-based method such as finite difference, and the field
information is finally interpolated back to the particle locations
HockneyEastman81. (This method is also called particle-in-cell, pic.) In some
applications, such as molecular dynamics, the smoothing at the short-range
introduced by the interpolations in the pm method is unacceptable. An
alternative mesh-based method can then be used in which all near-field
potentials are calculated directly, while far-field effects are calculated
with the pm method; this is called the particle-particle/particle-mesh method
(p3m).

The second class of methods provides efficient computation of the interactions
by means of a hierarchical or multilevel approach. The main subset of this
class performs a hierarchical subdivision of the computational domain, which
is used to group particles at different length scales, and then approximates
the interactions of clusters of particles using series expansions. The
approximation is applied to far-field interactions, while near-field
interactions are summed directly. This type of methods can be considered
meshfree, and includes: tree codes BarnesHut1986,Appel1985, the fast multipole
method () greengard+rokhlin1987 and its variations
CarrierGreengardRokhlin88,Anderson92,YingBirosZorin2004,GimbutasRokhlin2003.
An alternative multilevel method has been presented by Skeel
SkeelTezcanHardy02, which instead of using series expansions for the far field
approximations utilizes a multigrid approach. The approximation of the field
is in this case performed after a splitting of the particle potentials into a
smooth part (matching the far field) and a nonsmooth part (acting only in the
near field). While the nonsmooth (purely local) part can be calculated
directly at low cost, a multigrid method is used to approximate the smooth
component. For this approximation, the method relies on gridded basis
functions of compact support, like in p3m, but unlike p3m it provides
acceleration via multiple grid levels, achieving complexity. Thus, this method
applies the multilevel approach via field decomposition, rather than spatial
decomposition; it can perhaps be viewed as a hybrid of the mesh-based and
hierarchical methods.

In this paper, we present the theory and development of a parallel fast
multipole library, ††stands for ‘portable extensible toolkit for ’, as in ,
which is ‘portable extensible toolkit for scientific computing’. , belonging
to the meshfree type of methods described above. The overarching goal is to
unify the efforts in the development of -like methods into an open-source
library, that provides a framework with the capacity to accommodate memory
efficiency, parallelism and the data structures used for spatial
decomposition. The software is implemented utilizing
http://www.mcs.anl.gov/petsc/petsc-as/, the parallel library for scientific
computing developed over more than 17 years at Argonne National Laboratory
petsc-manual. At this point, we have a complete implementation of the in
parallel, with dynamic load balancing provided by means of an optimization
approach—minimizing inter-node communications and per-node computational work.
But a prominent feature of this implementation is that it is designed to be
extensible, so that it can effectively unify efforts involving many algorithms
which are based on the same principles of the . The perspectives for
extensibility are described in this paper as well.

The development of this extensible parallel library for $N$-body interactions
is important due to the programming difficulty associated with the algorithm,
which has been a barrier for adoption and arguably diminished its potential
impact. A critical stage in the maturation of a computational field begins
with the widespread availability of community software for the central
algorithms. A good example is molecular dynamics, which blossomed after
introduction of freely available packages, such as charmm CHARMM1983 and namd
NAMD2005. Such game-changing community software does not exist for particle
methods or for $N$-body computations in general.

The present paper does not merely describe a new parallel strategy and
implementation, it also details an exhaustive model for the computation of
tree-based $N$-body algorithms in parallel. Our model is a significant
extension of the time model developed in GreengardGropp1990, which assumed a
uniform distribution of the particles among processors and does not address
load balancing or communication overheads. With our model, which includes both
work estimates and communication estimates, we are able to implement a method
to provide a priori, automatic load balancing.

The first parallel implementations of the was that of Greengard and Gropp
GreengardGropp1990, on a shared memory computer. They also presented a timing
model for a perfectly balanced implementation, of which we say more in §work.
More recent versions of the parallel have been presented in
Ying03anew,Have2003,Ogata2003,kurzakPettit2005. Many of these codes produce a
partition of the data among processors based upon a space-filling curve, as
previously introduced for the case of parallel treecodes in warren+salmon93.
Only one of these parallel codes represents a supported, open source code
available for community use. The kifmm3d code can be downloaded and modified
under the gpl license. It is not an implementation of the classic algorithm,
however, but rather a kernel-independent version developed by the authors.
This algorithm does not utilize series expansions, but instead uses values on
a bounding surface of each subdomain obtained through an iterative solution
method; these ideas are based on Anderson92. The code does not appear to allow
easy extension to traditional , or to the other related algorithms alluded to
above. Moreover, it does not appear to be designed as an embedded library
component, part of a larger multiphysics simulation.

This paper is organized as follows. We present first a brief overview of the
algorithm; this presentation is necessarily cursory, as a large body of
literature has been written about this method. A basic description, however,
is necessary to agree on a common terminology for the rest of the paper. Our
approach is to illustrate the method using graphical representations. The
following section (§particle) describes our client application code, the
vortex particle method for simulation of incompressible flow at high Reynolds
numbers. In this method, the is one of two approaches commonly used to obtain
the velocity of particles from the vorticity field information; the second
approach (as in other $N$-body problems) is to interpolate information back
and forth from a mesh, while solving for the field of interest on the mesh.
Although equally efficient—both can be —the extensive use of interpolations
may introduce numerical diffusion, which is undesirable in certain
applications. Next, §parallel discusses our parallelization strategy. The goal
is achieving optimal distribution of the computational work among processors
and minimal communication requirement. Our approach to parallelization is
original in the use of an optimization method to obtain the parallel
partitioning. To be able to apply such an optimization, there is need for good
estimates of the computational work required for algorithmic components, as
well as communication requirements. The development of these estimates, in
addition to memory estimates, is presented in §work. The subsequent section
(§software) presents details of our software design, implementation and
verification carried out. Results of computational experiments with the
parallel software are presented in §results, and we end with some conclusions
and remarks about future work.

Note that a very simple and flexible, yet efficient and scalable code has been
produced. The entire implementation of is only 2600 lines of C++, including
comments and blank lines. It is already freely downloadable from
http://petsc.cs.iit.edu/petsc/ and we welcome correspondence with potential
users or those who wish to extend it for specific purposes.