11institutetext: School of Electrical Engineering, Tel Aviv University, Israel
22institutetext: The Manuel and Raquel Klachky Chair of Image Processing,
School of Electrical Engineering, Tel-Aviv University, Israel 33institutetext:
Diagnostic Imaging, Sheba Medical Center, affiliated to the Sackler School of
Medicine, Tel-Aviv University, Israel

# Labeling of Multilingual Breast MRI Reports

Chen-Han Tsai 11 Nahum Kiryati 22 Eli Konen 33 Miri Sklair-Levy 33 Arnaldo
Mayer 33

###### Abstract

Medical reports are an essential medium in recording a patient’s condition
throughout a clinical trial. They contain valuable information that can be
extracted to generate a large labeled dataset needed for the development of
clinical tools. However, the majority of medical reports are stored in an
unregularized format, and a trained human annotator (typically a doctor) must
manually assess and label each case, resulting in an expensive and time
consuming procedure. In this work, we present a framework for developing a
multilingual breast MRI report classifier using a custom-built language
representation called LAMBR. Our proposed method overcomes practical
challenges faced in clinical settings, and we demonstrate improved performance
in extracting labels from medical reports when compared with conventional
approaches.

###### Keywords:

Labeling Medical Reports Transfer Learning Breast MRI LAMBR

##  1 Introduction

The introduction of the Electronic Medical Record (EMR) has improved
convenience in accessing and organizing medical reports. With the increasing
demand for biomedical tools based on deep learning, obtaining large volumes of
labeled data is essential for training an effective model. One major category
where such deep learning models excel is in the area of computer assisted
diagnosis (CADx), and several works (e.g. [1, 4, 12]) have demonstrated
effective utilization of weakly labeled data to achieve promising performance.
Since understanding medical data requires specialized training, datasets often
contain a small subset of all past exams, that are manually relabeled by
doctors for the target task. Not only is this a labour-intensive process, but
the resulting dataset is often too small to represent the true distribution,
resulting in underperforming models.

In this work, we present a framework for developing multilingual breast MRI
report classifiers by using a customized language representation called LAMBR.
LAMBR is first obtained by pre-training an existing language representation on
a large quantity of breast MRI reports. Fine-tuning is then applied to obtain
separate classifiers that can perform tasks such as: (1) determining whether
the corresponding patient in the report has been suggested to undergo biopsy
or (2) predicting BI-RADS 111Breast Imaging-Reporting and Data System: a score
between 0-6 indicating the level of severity of a breast lesion score for the
reported lesion (see Figure 1). With such classifiers, one may avoid the
manual labeling required from doctors, and instead, automatically extract a
large number of weak labels from existing medical reports for training weakly
supervised breast MRI CADx models.

Figure 1: An overview of training stages presented in our framework. Pre-
training is performed on the multilingual BERT with unlabeled breast MRI
reports to obtain a pre-trained LAMBR. The pre-trained LAMBR is then fine-
tuned using a small number of labeled reports to obtain classifiers for
specific downstream text classification tasks.

Prior to our work, text classification has been explored extensively by
several studies such as ULMFIT [5] and SiATL [2]. ELMo [9], BERT [3], and
XLNet [16] have also demonstrated adequate approaches towards text
classification using the notion of a generalized language representation.
However, the majority of these approaches require pre-training an encoder on a
massive text corpora, and this is a time consuming and resource intensive
procedure that is impractical for a clinical setting [10]. Moreover, the
majority of prior works perform encoder pre-training on widely available
natural language texts which differ greatly from the scarcely available
medical texts.

To overcome the difference in distrubtion between medical texts and natural
texts, BioBERT [7] introduced a pre-training objective that relied on a large
collection of PubMed abstracts and PMC articles. Although BioBERT demonstrated
improved performance compared with BERT, their method does not avoid the above
resource intensive pre-training. Within English medical reports, ALARM [14]
proposed a simple approach for labeling head MRI reports by utilizing a pre-
trained Bio-BERT and this avoids the expensive pre-training often required.
Yet for multilingual medical reports, such Bio-BERT does not exist, and in
this work, we present a solution based on the multilingual BERT. Our novel
approach introduces an inexpensive pre-training objective that yields
favorable text classification performance when fine-tuned, and in our
experiments, we demonstrate the robustness of the resulting classifiers even
in cases where parsing errors exist (see Figure 2). The remaining sections of
our paper are organized as follows: the proposed framework is presented in
Section 2, experimental results are reported in Section 3, and the conclusion
is given in Section 4.

Figure 2: Examples of breast MRI reports written in Hebrew and English (read
from right to left). Example 1 is complete report parsed from the EMR, and
Example 2 is missing the final assessments due to incorrect parsing. The
patient in Example 1 is recommended for biopsy, and patient in Example 2 is
not required to perform biopsy.

##  2 Methods

###  2.1 BERT Recap

BERT is a language representation based on the Transformer-Encoder [13]. The
input to the Transformer-Encoder is a sequence of tokens $\\{x_{i}\\}$
generated by WordPiece Embeddings [15] from a given series of sentences.
Special tokens are inserted and position encodings are added, and the output
is a sequence of bi-directional embeddings that represents each input token
[3]. In order to obtain the BERT language representation, Masked Language
Modeling (MLM) and Next Sentence Prediction (NSP) pre-training objectives were
introduced. MLM applies random masking on the 15% of the input tokens, and
BERT is trained to identify the original token of the masked token by
attending to other tokens of the same sequence. The NSP objective trains BERT
in understanding sentence coherence by randomly replacing the second sentence
of an existing sentence pair, and BERT has to determine whether the pair are
neighboring sentences.

Figure 3: An example of the tokens generated from breast MRI report using
WordPiece Embeddings. During DS-MLM, a portion of the tokens are augmented and
the pre-training objective is to correctly identify the original token prior
to augmentation (performed only on tokens selected for augmentation).

###  2.2 Domain-Specific Masked Language Modeling

The Domain-Specific Masked Language Modeling (DS-MLM) we propose is a
modification of the MLM pre-training objective introduced in BERT. The
multilingual BERT was trained using monolingual corpora from 104 languages,
and DS-MLM aims to retrain the multilingual BERT to better model the language
observed in breast MRI reports written in Hebrew and English. Unlike BioBert
[7], which relies on pre-training over massive biomedical corpora, we perform
DS-MLM solely from the available breast MRI reports stored in the hospital’s
EMR.

For each medical report, tokens are generated using WordPiece Embeddings (see
Figure 3). The [CLS] and [SEP] tokens are appended to the beginning and the
end of the generated tokens ([SEP] tokens are not added between sentences).
Since the multilingual BERT is already trained on a general domain corpora, we
select 20% of the generated tokens for MLM. Of the selected tokens, 60% are
masked using the [MASK] token, 30% are replaced with existing tokens and the
remaining 10% are left unchanged. In order to expose our model to more
frequent tokens observed in breast MRI reports, of the 30% of tokens selected
for replacement, two thirds are replaced with existing tokens encountered in
breast MRI reports, and one third is replaced with tokens from the complete
vocabulary (may include tokens corresponding to other languages). Dynamic
masking is applied to allow more exposure to a broad range of tokens.

Since most medical reports contain sentences not adhering to a strict flow of
ideas, we do not incorporate NSP into the pre-training objective of our
framework. In addition, RoBERTa [8] demonstrated that the removal of NSP may
even improve downstream task performance, and therefore, the pre-training
objective of the LAMBR language representation is simply DS-MLM.

###  2.3 Text Classification Fine-Tuning

Text Classification Fine-Tuning (TCFT) is a series of techniques to fine-tune
a pre-trained LAMBR for performing text classification. We propose a simple
classifier head to add on top of the Transformer-Encoder, and we present a
method to fine-tune the complete text classifier (Transformer-Encoder along
with classifier head) using a pre-trained LAMBR (see Figure 4).

Figure 4: An illustration of LAMBR encoding a breast MRI report. Tokens
$\\{x_{i}\\}$ are generated from the report using WordPiece Embeddings, and
the sum of the positional encoding and the token embedding are input to LAMBR.
During TCFT, the learning rates for each layer are progressively tuned so that
higher level features (layers near $0$) are updated more compared to lower-
level features. The classifier head takes the average of the token embeddings
$\hat{z}$, applies an affine transform, and passes it into a tempered Softmax
($\sigma_{T}$) to generate the class probabilities.

####  2.3.1 Classifier Head.

For a given token sequence $\\{x_{i}\\}$, we obtain the output embedding
sequence $\\{z_{i}\\}$ from the pre-trained LAMBR. The average of the output
token embeddings $\hat{z}$ is computed and is fed to an affine layer which
undergoes a Tempered Softmax operation ($\sigma_{T}$) to obtain the outputs
class probabilities $p$. Namely:

$p=\sigma_{T}(W\hat{z}+b)\;\;\leftarrow\;\;\hat{z}=\frac{1}{N}\sum_{i=1}^{N}z_{i}$
(1)

where $\hat{z},b\in R^{d}$, $W\in R^{c\times d}$, and $p\in R^{K}$.

####  2.3.2 Progressive Fine-Tuning.

Inspired by [17, 5], we propose a method for fine-tuning the complete text
classifier. The learning rates are adjusted such that high-level features will
be updated with a higher learning rate compared to lower level features.
Specifically, for a Transformer-Encoder with $L$ encoding layers
$\\{l_{i}\\}_{i=0}^{L-1}$ ($l_{0}$ indicates the top-most layer), the layer-
dependent learning rate $\eta(l)$ is formulated as:

$\eta(l)=\eta_{base}\cdot\gamma^{l}$ (2)

where $\eta_{base}$ is the base learning rate and $\gamma$ is the decay factor
valued between 0 and 1. Similarly, the classifier head is updated with
learning rate $\eta_{base}$.

Fine-tuning is performed by optimizing the weighted Label Smoothing Loss [11]:

$L(x,y(x))=-\sum_{c=1}^{K}w(c)\cdot\Bigg{[}(1-\epsilon)y_{c}(x)+\frac{\epsilon}{K}\Bigg{]}\cdot\log(p_{c}(x))$
(3)

where $w(c)$ are the weights for every class $c\in K$, $\epsilon\in[0,1)$ is
the smoothing term, $y_{c}(x)\in\\{0,1\\}$ is $1$ if $x$ belongs to class $c$,
and $p_{c}(x)$ is the probability of $x$ belonging to class $c$ as computed in
Equation 1.

##  3 Experiments

In this section, we evaluate the proposed framework on two text classification
tasks: (1) classifying whether the corresponding patient has been suggested to
undergo biopsy and (2) predicting the BI-RADS score for the lesion reported.

The data is a curated list of medical reports from breast MRI examinations
carried out at the Sheba Medical Center, Israel. Cases that were initially
diagnosed as containing potential malignant tumors have all been suggested to
undergo biopsy. Breast examinations from the years 2016-2019 were involved,
and a total of 10,529 medical reports were collected. Of the 10,529 breast MRI
reports, 541 reports were labeled with the relevant BI-RADS score for the
(single) lesion reported, and each case was labeled with whether the patient
had been suggested for biopsy.

###  3.1 Training Setup

####  3.1.1 Pre-Training.

Pre-training was performed using DS-MLM as mentioned in Section 2.2. Of the
9,988 reports used for pre-training, 85% of the reports were randomly
designated as the training set, and the remaining for validation. Cross
Entropy loss was used for DS-MLM pre-training, and the multilingual BERT was
trained for 70 epochs which took approximately 33 hours to complete using on
an NVIDIA GTX 1070 8GB GPU.

####  3.1.2 Biopsy-Suggested Classification

The goal of this task to identify whether the patient in the report had been
suggested to undergo biopsy or not. We perform fine-tuning as proposed in
Section 2.3. Due to dataset imbalance (26.6% of the cases were suggested for
biopsy), class weights were set to the inverse of the counts per class.
Evaluation was performed using 5-fold cross validation, and stratified
sampling was applied to ensure equal class distribution between the training
and validation sets.

Training was performed using the Adam optimizer [6] with a base learning rate
of 1e-4 and a batch size of 8. Decay factor $\gamma$ was set to $1/4$, softmax
temperature $T$ was set to 1, and the smoothing term $\epsilon$ was set to 0.
The best performing model from training for 70 epochs (approx 25 mins) was
evaluated.

####  3.1.3 Masked BI-RADS Prediction

Masked BI-RADS Prediction is a classification task to assign the appropriate
BI-RADS score given the lesion description in the report. For reports that
were parsed correctly, the BI-RADS score is written in the assessments, and a
simple keyword-based tagging is often enough to label the reports with the
appropriate score. However, reports might also contain BI-RADS keywords that
refer to previous BI-RADS scores (for the same lesion or removed lesion),
which would lead to incorrect inference if the keyword based approach was
used. In addition, errors encountered during parsing would occasionally miss
out sections containing the BI-RADS score, rendering the keyword-based
approach useless. The text classifier we propose in our framework relies on
the report descriptions alone, and is thus robust against such potential
obstacles.

Keyword search was performed on all the reports and any revealing BI-RADS
scores (in the reports) were removed. This modified report was then fed into a
pre-trained LAMBR for fine-tuning, and a 5-fold cross validation was
performed. There were a total of 6 classes (no reports with BI-RADS score 5).
Class weights were computed as the inverse of the class counts, and stratified
sampling was performed to ensure equal class distribution between training and
validation sets. Optimization was performed using the Adam optimizer with a
base learning rate of 1e-4 and batch size of 8. The decay factor $\gamma$ was
set to 1/3, Softmax temperature $T$ was set to $\sqrt{2}$, and the smoothing
term $\epsilon$ was set to $1/3$. The best performing model over a training
period of 70 epochs was selected for evaluation.

Fine-Tuning Tasks (5-Fold Average) | Accuracy | ROC-AUC | Macro Avg F1 | MCC
---|---|---|---|---
Biopsy Suggested - LAMBR | 0.965 | 0.989 | 0.935 | 0.913
Biopsy Suggested - BERT | 0.949 | 0.987 | 0.904 | 0.8733
Biopsy Suggested - Baseline | 0.828 | - | 0.718 | 0.6035
BI-RADS Prediction - LAMBR | 0.8576 | - | 0.7158 | 0.7594
BI-RADS Prediction - BERT | 0.795 | - | 0.572 | 0.672
Table 1: Several metrics following the five-fold cross validation for Biopsy
Suggested Classification and Masked BI-RADS Prediction are presented. We
compare the performance between LAMBR and BERT for both classification tasks
(same classification head design, but different language representations). The
baseline for Biopsy Suggested Classification is a keyword matching algorithm.
Notice that in both tasks, LAMBR consistently outperforms their counterparts.

###  3.2 Experimental Results

The experimental results for our proposed framework are listed in Table 1, and
we include a comparison with BERT and a baseline algorithm.

In Biopsy Suggested Classification, the keyword matching algorithm aims to
label each report in accordance with keywords that hint of a potential biopsy
suggestion. Of the 541 labeled reports, 90 reports were misparsed, which
contributes to a 16% drop in accuracy. In contrast, the classifier trained and
fine-tuned using our proposed framework performs consistently across all five
folds (see Figure 5) despite misparsed reports. We also trained a classifier
with the same classification head from Section 2.3.1 using a multi-lingual
BERT, and we demonstrate a better classification performance with our
approach.

Figure 5: Detailed visualization of the evaluation metrics for Biopsy
Suggested Classification following the 5-fold cross validation. Notice the
consistent performance across a 5 folds.

In the task of Masked BI-RADS Prediction, the classifier trained using our
framework was able to correctly predict the BI-RADS score for most of the
reports. Unlike the previous task where the BI-RADS score was available, this
task requires the classifier to attend to relevant context clues in the
medical report for prediction (hence, the keyword-tagging algorithm does not
work). An additional comparison was made between LAMBR and the pre-trained
multilingual BERT, and the results in Table 1 demonstrate a clear difference
the two language representations partake in training a BI-RADS classifier.

##  4 Conclusion

In this work, we explore the task of labeling breast MRI reports written
primarily in Hebrew with occasional English texts through the use of
multilingual language representations. To avoid the expensive pre-training
required in obtaining a generalized language representation, the Domain-
Specific Masked Language Modeling objective pre-trains a multilingual BERT on
existing breast MRI reports alone to obtain the LAMBR language representation.
A simple classification head is integrated onto the Transformer-Encoder, and
Progressive Fine-Tuning is applied to train the classifier for its specific
text classification task.

In our experiments, we train two separate classifiers to perform two
classification tasks based on breast MRI reports. In the first task, we
trained a classifier to determine whether the patient described in the report
has been suggested to undergo biopsy. When compared with past methods, our
approach demonstrates better classification performance despite parsing errors
in a portion of the reports. In the second task, we trained a classifier to
predict the BI-RADS score based on the lesion description in the report.
Despite the absence of the BI-RADS score in the report, our classifier was
able to infer the correct BI-RADS score in the majority of the cases.

Future works may include labeling medical reports for additional pathologies
written in different languages. Additional tasks (apart from text
classification) such as named-entity recognition for medical reports and
summary generation for biomedical texts may also be investigated. In this
work, we focus on the task of medical text classification, and we believe our
proposed framework may assist in generating large numbers of labels for weakly
supervised training tasks required for breast MRI CADx development.

## References

  * [1] Bien, N., Rajpurkar, P., Ball, R.L., Irvin, J., Park, A., Jones, E., Bereket, M., Patel, B.N., Yeom, K.W., Shpanskaya, K., Halabi, S., Zucker, E., Fanton, G., Amanatullah, D.F., Beaulieu, C.F., Riley, G.M., Stewart, R.J., Blankenberg, F.G., Larson, D.B., Jones, R.H., Langlotz, C.P., Ng, A.Y., Lungren, M.P.: Deep-learning-assisted diagnosis for knee magnetic resonance imaging: Development and retrospective validation of MRNet. PLOS Medicine 15(11), e1002699 (Nov 2018). https://doi.org/10.1371/journal.pmed.1002699
  * [2] Chronopoulou, A., Baziotis, C., Potamianos, A.: An embarrassingly simple approach for transfer learning from pretrained language models. In: Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers). pp. 2089–2095. Association for Computational Linguistics, Minneapolis, Minnesota (Jun 2019), https://www.aclweb.org/anthology/N19-1213
  * [3] Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: Bert: Pre-training of deep bidirectional transformers for language understanding. In: NAACL-HLT (2019)
  * [4] Gozes, O., Frid-Adar, M., Greenspan, H., Browning, P.D., Zhang, H., Ji, W., Bernheim, A., Siegel, E.: Rapid ai development cycle for the coronavirus (covid-19) pandemic: Initial results for automated detection & patient monitoring using deep learning ct image analysis (2020)
  * [5] Howard, J., Ruder, S.: Universal language model fine-tuning for text classification. In: ACL. Association for Computational Linguistics (2018), http://arxiv.org/abs/1801.06146
  * [6] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization (2014), http://arxiv.org/abs/1412.6980
  * [7] Lee, J., Yoon, W., Kim, S., Kim, D., Kim, S., So, C.H., Kang, J.: BioBERT: a pre-trained biomedical language representation model for biomedical text mining. Bioinformatics (09 2019). https://doi.org/10.1093/bioinformatics/btz682
  * [8] Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyer, L., Stoyanov, V.: Roberta: A robustly optimized BERT pretraining approach. CoRR abs/1907.11692 (2019), http://arxiv.org/abs/1907.11692
  * [9] Peters, M.E., Neumann, M., Iyyer, M., Gardner, M., Clark, C., Lee, K., Zettlemoyer, L.: Deep contextualized word representations. CoRR abs/1802.05365 (2018)
  * [10] Sharir, O., Peleg, B., Shoham, Y.: The cost of training nlp models: A concise overview. ArXiv abs/2004.08900 (2020)
  * [11] Szegedy, C., Vanhoucke, V., Ioffe, S., Shlens, J., Wojna, Z.: Rethinking the inception architecture for computer vision (2015)
  * [12] Tsai, C.H., Kiryati, N., Konen, E., Eshed, I., Mayer, A.: Knee injury detection using mri with efficiently-layered network (elnet). Proceedings of Machine Learning Research, vol. 121, pp. 784–794. PMLR (2020)
  * [13] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, L., Polosukhin, I.: Attention is all you need (2017)
  * [14] Wood, D.A., Lynch, J., Kafiabadi, S., Guilhem, E., Al Busaidi, A., Montvila, A., Varsavsky, T., Siddiqui, J., Gadapa, N., Townend, M., Kiik, M., Patel, K., Barker, G., Ourselin, S., Cole, J.H., Booth, T.C.: Automated Labelling using an Attention model for Radiology reports of MRI scans (ALARM). Proceedings of Machine Learning Research, vol. 121, pp. 811–826. PMLR, Montreal, QC, Canada (2020), http://proceedings.mlr.press/v121/wood20a.html
  * [15] Wu, Y., Schuster, M., Chen, Z., Le, Q.V., Norouzi, M., Macherey, W., Krikun, M., Cao, Y., Gao, Q., Macherey, K., Klingner, J., Shah, A., Johnson, M., Liu, X., Łukasz Kaiser, Gouws, S., Kato, Y., Kudo, T., Kazawa, H., Stevens, K., Kurian, G., Patil, N., Wang, W., Young, C., Smith, J., Riesa, J., Rudnick, A., Vinyals, O., Corrado, G., Hughes, M., Dean, J.: Google’s neural machine translation system: Bridging the gap between human and machine translation (2016)
  * [16] Yang, Z., Dai, Z., Yang, Y., Carbonell, J., Salakhutdinov, R., Le, Q.V.: Xlnet: Generalized autoregressive pretraining for language understanding (2019)
  * [17] Yosinski, J., Clune, J., Bengio, Y., Lipson, H.: How transferable are features in deep neural networks? In: Advances in Neural Information Processing Systems. vol. 27, pp. 3320–3328. Curran Associates, Inc. (2014), https://proceedings.neurips.cc/paper/2014/file/375c71349b295fbe2dcdca9206f20a06-Paper.pdf


YITP-19-120

# Additive-error fine-grained quantum supremacy

Tomoyuki Morimae<EMAIL_ADDRESS>Yukawa Institute for
Theoretical Physics, Kyoto University, Kitashirakawa Oiwakecho, Sakyoku, Kyoto
606-8502, Japan  JST, PRESTO, 4-1-8 Honcho, Kawaguchi, Saitama, 332-0012,
Japan  Suguru Tamaki<EMAIL_ADDRESS>School of Social Information
Science, University of Hyogo, 8-2-1, Gakuennishi-machi, Nishi-ku, Kobe, Hyogo
651-2197, Japan

###### Abstract

It is known that several sub-universal quantum computing models, such as the
IQP model, the Boson sampling model, the one-clean qubit model, and the random
circuit model, cannot be classically simulated in polynomial time under
certain conjectures in classical complexity theory. Recently, these results
have been improved to “fine-grained" versions where even exponential-time
classical simulations are excluded assuming certain classical fine-grained
complexity conjectures. All these fine-grained results are, however, about the
hardness of strong simulations or multiplicative-error sampling. It was open
whether any fine-grained quantum supremacy result can be shown for a more
realistic setup, namely, additive-error sampling. In this paper, we show the
additive-error fine-grained quantum supremacy (under certain complexity
assumptions). As examples, we consider the IQP model, a mixture of the IQP
model and log-depth Boolean circuits, and Clifford+$T$ circuits. Similar
results should hold for other sub-universal models.

##  1 Introduction

Classically sampling output probability distributions of sub-universal quantum
computing models is known to be impossible under certain classical complexity
conjectures. The depth-four model [1], the Boson Sampling model [2], the IQP
model [3, 4], the one-clean qubit model [5, 6, 7, 8, 9], the HC1Q model [10],
and the random circuit model [11, 12, 13] are known examples. These results
prohibit only polynomial-time classical sampling, but recently,
impossibilities of some exponential-time classical simulations have been shown
based on classical fine-grained complexity conjectures [14, 15, 16, 17, 18,
19].

These “fine-grained" quantum supremacy results are, however, only for exact
computations (i.e., strong simulations) or multiplicative-error sampling of
output probability distributions. Here, we say that a quantum probability
distribution $\\{p_{z}\\}_{z}$ is classically sampled in time $T$ within a
multiplicative error $\epsilon$ if there exists a classical $T$-time
probabilistic algorithm that outputs $z$ with probability $q_{z}$ such that
$|p_{z}-q_{z}|\leq\epsilon p_{z}$ for all $z$. It was open whether fine-
grained quantum supremacy can be shown for additive-error sampling. Here, we
say that a quantum probability distribution $\\{p_{z}\\}_{z}$ is classically
sampled in time $T$ within an additive error $\epsilon$ if there exists a
classical $T$-time probabilistic algorithm that outputs $z$ with probability
$q_{z}$ such that $\sum_{z}|p_{z}-q_{z}|\leq\epsilon$. Additive-error sampling
is more realistic for medium-size noisy quantum computers, and therefore
theoretically showing quantum supremacy for additive-error sampling is
important for the near-term experimental demonstrations of quantum supremacy.

In this paper, we show additive-error fine-grained quantum supremacy based on
certain classical fine-grained complexity conjectures. As examples, we
consider the IQP model (Sec. 2), a mixture of the IQP model and log-depth
Boolean circuits (Sec. 3), and Clifford+$T$ circuits (Sec. 4). Similar results
should hold for other sub-universal models.

The second result (IQP plus log-depth Boolean circuit) needs more complicated
quantum circuit than the first one, but the conjecture seems to be more
reliable. The first and second results are about the scaling for the number of
qubits, while the third result is about the scaling for the number of $T$
gates.

The standard proof technique of additive-error quantum supremacy [2, 4],
namely, the combination of Markov’s inequality, Stockmeyer’s theorem, and the
anti-concentration lemma, cannot be directly used for fine-grained quantum
supremacy, because Stockmeyer’s theorem is a result for polynomial-time
probabilistic computing. (Markov’s inequality and the anti-concentration lemma
can be used because they are independent of the time complexity.) In order to
show fine-grained additive-error quantum supremacy, we derive a “fine-grained
version" of Stockmeyer’s theorem. Our results, for the first time, demonstrate
that the standard proof technique of additive-error quantum supremacy can be
extended to exponential-time hardness.

Because there is a gap between the upper-bound and the lower-bound, the
results have a potential to be improved or sharpened. The upper-bound can be
improved by faster simulations, and the lower-bound can be improved by
improving the reduction or by introducing other conjectures. Furthermore,
possible ways are extensions of the MA algorithm to refute SETH [20], and the
fine-grained reductions from approximate counting to decision [21].

Note: After uploading this paper on arXiv, authors of Ref. [14] told us that
they also show independently additive-error fine-grained quantum supremacy
results. (Their additive-error results are added in their latest version.)
They consider an exponential-time version of the ${\rm SBP}\neq{\rm SBQP}$
conjecture. (If ${\rm SBQP}={\rm SBP}$, the polynomial-time hierarchy
collapses to the second level.) At this moment, we do not know how their
conjecture and ours are related.

##  2 IQP

In this section, we show additive-error fine-grained quantum supremacy of the
IQP model. The IQP model is defined as follows.

###### Definition 1

An $N$-qubit IQP model is the following quantum computing model:

  * 1.

The initial state is $|0^{N}\rangle$. (Here, $|0^{N}\rangle=|0\rangle^{\otimes
N}$.)

  * 2.

$H^{\otimes N}$ is applied, where $H$ is the Hadamard gate.

  * 3.

$Z$-diagonal gates (such as $e^{i\theta Z}$, $Z$, $CZ$, and $CCZ$) are
applied. (In this paper, we consider only $Z$, $CZ$, and $CCZ$.)

  * 4.

$H^{\otimes N}$ is applied.

  * 5.

All qubits are measured in the computational basis.

Let us consider an $n$-variable degree-3 polynomial,
$f:\\{0,1\\}^{n}\to\\{0,1\\}$, over ${\mathbb{F}}_{2}$ defined by

$\displaystyle
f(x_{1},...,x_{n})\equiv\sum_{i=1}^{n}\alpha_{i}x_{i}+\sum_{i>j}\beta_{i,j}x_{i}x_{j}+\sum_{i>j>k}\gamma_{i,j,k}x_{i}x_{j}x_{k}$

for any $x\equiv(x_{1},x_{2},...,x_{n})\in\\{0,1\\}^{n}$, where
$\alpha_{i},\beta_{i,j},\gamma_{i,j,k}\in\\{0,1\\}$. If we say that we
randomly choose $f$, it means that we randomly choose each
$\alpha_{i},\beta_{i,j},\gamma_{i,j,k}$ uniformly and independently.

The conjecture on which additive-error fine-grained quantum supremacy of the
IQP model is based is stated as follows.

###### Conjecture 1

Let $f$ be an $n$-variable degree-3 polynomial over ${\mathbb{F}}_{2}$. Let us
define

$\displaystyle gap(f)\equiv\sum_{x\in\\{0,1\\}^{n}}(-1)^{f(x)}.$

There exist positive constants $a$ and $n_{0}$ such that for every $n>n_{0}$
the following holds. Computing $[gap(f)]^{2}$ within a multiplicative error
$u$ for at least $v$ fraction of $f$ cannot be done with a classical
probabilistic $O^{*}(2^{an})$-time algorithm that makes queries of length
$O(2^{an})$ to an ${\rm NTIME}[n^{2}]$ oracle with a success probability at
least $w$. Here, $u,v,w$ are certain constants. ($O^{*}$ means that the
polynomial factor is ignored.)

Here, the oracle query is the standard one: there is a separate oracle tape
and answers can be returned from the oracle instantaneously. Note that the
parameters $u,v,w$ can be adjustable to some extent. (See the proof.) We do
not know whether this conjecture is true or false, but at least at this moment
we do not know how to refute it. (For more discussions, see Sec. 5.1).

Based on Conjecture 1, we show the following result.

###### Theorem 1

If Conjecture 1 is true, then there exists an $N$-qubit IQP circuit whose
output probability distribution cannot be classically sampled in
$O(2^{aN})$-time within a certain constant additive error $\epsilon$.

For simplicity, we consider degree-3 polynomials, but it is clear from the
following proof that a similar result holds for degree-$k$ polynomials for any
constant $k\geq 3$. (The anti-concentration lemma holds for any degree-$k$
polynomial with $k\geq 2$, but the degree-2 case is classically simulatable
because it is a Clifford circuit, so $k\geq 3$ is necessary.) If we consider
Conjecture 1 for degree-$k$ polynomials, it becomes more stable for larger $k$
[22].

Proof of Theorem 1. Given an $n$-variable degree-3 polynomial $f$, we can
construct an $n$-qubit IQP circuit such that the probability $p_{z}(f)$ of
outputting $z\in\\{0,1\\}^{n}$ satisfies

$\displaystyle p_{z}(f)=\frac{(gap(f_{z}))^{2}}{2^{2n}},$

where

$\displaystyle f_{z}(x_{1},...,x_{n})\equiv
f(x_{1},...,x_{n})+\sum_{i=1}^{n}z_{i}x_{i}.$

Assume that there exists a $T$-time classical probabilistic algorithm that
outputs $z\in\\{0,1\\}^{n}$ with probability $q_{z}(f)$ such that

$\displaystyle\sum_{z\in\\{0,1\\}^{n}}|p_{z}(f)-q_{z}(f)|\leq\epsilon$

for a certain $\epsilon$ and any $f$. From Markov’s inequality,

$\displaystyle{\rm
Pr}_{z}\Big{[}|p_{z}(f)-q_{z}(f)|\geq\frac{\epsilon}{2^{n}\delta}\Big{]}\leq\delta$

for any $f$ and $\delta>0$. According to the fine-grained Stockmeyer’s theorem
(see Appendix), a classical $O^{*}(T)$-time probabilistic algorithm that makes
queries of $O(T)$ length to the ${\rm NTIME}[n^{2}]$ oracle can compute
$\tilde{q}_{z}(f)$ such that

$\displaystyle|q_{z}(f)-\tilde{q}_{z}(f)|\leq\xi q_{z}(f),$

where

$\displaystyle\xi\equiv\frac{2^{\frac{1}{\alpha}}-2^{-\frac{1}{\alpha}}}{2},$

for any $f$, integer $\alpha\geq 1$, and $z\in\\{0,1\\}^{n}$, with a success
probability at least $w$. Due to the anti-concentration lemma [4],

$\displaystyle{\rm
Pr}_{z,f}\Big{[}p_{z}(f)\geq\frac{\tau}{2^{n}}\Big{]}\geq\frac{(1-\tau)^{2}}{3}$

for any $0<\tau<1$.

Therefore we have

$\displaystyle|p_{z}(f)-\tilde{q}_{z}(f)|$ $\displaystyle\leq$
$\displaystyle|p_{z}(f)-q_{z}(f)|+|q_{z}(f)-\tilde{q}_{z}(f)|$
$\displaystyle\leq$ $\displaystyle|p_{z}(f)-q_{z}(f)|+\xi
q_{z}(f)\leavevmode\nobreak\ \leavevmode\nobreak\ \mbox{(with a success
probability at least $w$ for each $f$ and $z$)}$ $\displaystyle\leq$
$\displaystyle|p_{z}(f)-q_{z}(f)|+\xi(p_{z}(f)+|p_{z}(f)-q_{z}(f)|)$
$\displaystyle=$ $\displaystyle\xi p_{z}(f)+|p_{z}(f)-q_{z}(f)|(1+\xi)$
$\displaystyle\leq$ $\displaystyle\xi
p_{z}(f)+\frac{\epsilon}{2^{n}\delta}(1+\xi)\leavevmode\nobreak\
\leavevmode\nobreak\ \mbox{(for at least $1-\delta$ fraction of $z$)}$
$\displaystyle\leq$ $\displaystyle\xi p_{z}(f)+\sigma
p_{z}(f)(1+\xi)\leavevmode\nobreak\ \leavevmode\nobreak\ \mbox{(for at least
$\frac{(1-\frac{\epsilon}{\sigma\delta})^{2}}{3}$ fraction of $(z,f)$)}$
$\displaystyle=$ $\displaystyle p_{z}(f)\Big{(}\sigma+(1+\sigma)\xi\Big{)}$
$\displaystyle=$ $\displaystyle p_{z}(f)u\leavevmode\nobreak\
\leavevmode\nobreak\ (\mbox{We take $u\equiv\sigma+(1+\sigma)\xi$}).$

If we take $\epsilon$ and $\delta$ such that
$-\delta+\frac{1}{3}(1-\frac{\epsilon}{\sigma\delta})^{2}=v$, the above
inequality is correct for at least $v$ fraction of $(z,f)$. Hence, we obtain

$\displaystyle|(gap(f_{z}))^{2}-2^{2n}\tilde{q}_{z}(f)|\leq u(gap(f_{z}))^{2}$

for at least $v$ fraction of $(z,f)$. It means $(gap(f))^{2}$ is computable
within the multiplicative error $u$ for at least $v$ fraction of $f$, which
contradict Conjecture 1.

Note that $w$ can be arbitrary close to 1, but $u$ is lower-bounded as
$u\geq\frac{\epsilon}{1+\sqrt{3}}$, and $v$ is upper-bounded as $v\leq
1-\frac{\epsilon}{u(1+\sqrt{3})}$.

##  3 IQP plus log-depth Boolean circuit

In this section, we show additive-error fine-grained quantum supremacy for the
IQP plus log-depth Boolean circuit model.

Let us consider the following conjecture.

###### Conjecture 2

Let $f:\\{0,1\\}^{n}\to\\{0,1\\}$ be an $n$-variable degree-2 polynomial over
${\mathbb{F}}_{2}$, and $g:\\{0,1\\}^{n}\to\\{0,1\\}$ be an $n$-variable log-
depth Boolean circuit. Define

$\displaystyle gap(f+g)\equiv\sum_{x\in\\{0,1\\}^{n}}(-1)^{f(x)+g(x)}.$

There exist $g$, and positive constants $a$ and $n_{0}$ such that for every
$n>n_{0}$ the following holds. Computing $[gap(f+g)]^{2}$ within a
multiplicative error $u$ for at least $v$ fraction of $f$ cannot be done with
a classical probabilistic $O^{*}(2^{an})$-time algorithm that makes queries of
length $O(2^{an})$ to an ${\rm NTIME}[n^{2}]$ oracle with a success
probability at least $w$.

Conjecture 2 is “more stable" than Conjecture 1, because log-depth Boolean
circuit is more general than constant-degree polynomials. For constant-degree
polynomials, there is a non-trivial exponential time algorithm to count the
number of solutions [23], but we do not know how to apply it to log-depth
Boolean circuits. Furthermore, note that in Conjecture 2, the average case is
considered only for $f$, and $g$ can be taken as the worst case one.

Based on Conjecture 2, we show the following result.

###### Theorem 2

If Conjecture 2 is true, then there exists an $N$-qubit $poly(N)$-size quantum
circuit (consisting of an IQP circuit and a log-depth Boolean circuit) whose
output probability distribution cannot be classically sampled in
$O(2^{aN})$-time within a certain constant additive error $\epsilon$.

Proof of Theorem 2. Given a log-depth Boolean circuit
$g:\\{0,1\\}^{n}\to\\{0,1\\}$, we can construct an $(n+1)$-qubit
$poly(n)$-size quantum circuit $U$ such that

$\displaystyle
U(|x\rangle\otimes|0\rangle)=e^{ih(x)}|x\rangle\otimes|g(x)\rangle$

for any $x\in\\{0,1\\}^{n}$, where $h$ is a certain function whose detail is
irrelevant here [24]. Let us consider the following circuit.

  * 1.

The initial state is $|0^{n}\rangle\otimes|0\rangle$.

  * 2.

Apply $H^{\otimes n}\otimes I$ to obtain

$\displaystyle\frac{1}{\sqrt{2^{n}}}\sum_{x\in\\{0,1\\}^{n}}|x\rangle\otimes|0\rangle.$

  * 3.

Apply $U$ to obtain

$\displaystyle\frac{1}{\sqrt{2^{n}}}\sum_{x\in\\{0,1\\}^{n}}e^{ih(x)}|x\rangle\otimes|g(x)\rangle.$

  * 4.

Apply $Z$ on the last qubit to obtain

$\displaystyle\frac{1}{\sqrt{2^{n}}}\sum_{x\in\\{0,1\\}^{n}}e^{ih(x)}(-1)^{g(x)}|x\rangle\otimes|g(x)\rangle.$

  * 5.

Apply $U^{\dagger}$ to obtain

$\displaystyle\frac{1}{\sqrt{2^{n}}}\sum_{x\in\\{0,1\\}^{n}}(-1)^{g(x)}|x\rangle\otimes|0\rangle.$

  * 6.

Apply $Z$ and $CZ$ that correspond to $f$ to obtain

$\displaystyle\frac{1}{\sqrt{2^{n}}}\sum_{x\in\\{0,1\\}^{n}}(-1)^{g(x)+f(x)}|x\rangle\otimes|0\rangle.$

  * 7.

Apply $H^{\otimes n}\otimes I$ and measure the first $n$ qubits in the
computational basis.

The probability of obtaining $z\in\\{0,1\\}^{n}$ is

$\displaystyle p_{z}(f+g)$ $\displaystyle=$
$\displaystyle\Big{|}\frac{1}{2^{n}}\sum_{x\in\\{0,1\\}^{n}}(-1)^{g(x)+f(x)+\sum_{j=1}^{n}x_{j}z_{j}}\Big{|}^{2}$
$\displaystyle=$ $\displaystyle\frac{(gap(g+f_{z}))^{2}}{2^{2n}}.$

Assume that there exists a $T$-time classical probabilistic algorithm that
outputs $z\in\\{0,1\\}^{n}$ with probability $q_{z}(f+g)$ such that

$\displaystyle\sum_{z\in\\{0,1\\}^{n}}|p_{z}(f+g)-q_{z}(f+g)|\leq\epsilon.$

From Markov’s inequality,

$\displaystyle{\rm
Pr}_{z}\Big{[}|p_{z}(f+g)-q_{z}(f+g)|\geq\frac{\epsilon}{2^{n}\delta}\Big{]}\leq\delta$

for any $f$, $g$, and $\delta>0$. According to the fine-grained Stockmeyer’s
theorem, a classical $O^{*}(T)$-time probabilistic algorithm that makes
queries of length $O(T)$ to the ${\rm NTIME}[n^{2}]$ oracle can compute
$\tilde{q}_{z}(f+g)$ such that

$\displaystyle|q_{z}(f+g)-\tilde{q}_{z}(f+g)|\leq\xi q_{z}(f+g),$

where

$\displaystyle\xi\equiv\frac{2^{\frac{1}{\alpha}}-2^{-\frac{1}{\alpha}}}{2},$

for any $f$, $g$, integer $\alpha\geq 1$, and $z\in\\{0,1\\}^{n}$, with a
success probability at least $w$. Due to the anti-concentration lemma [4]

$\displaystyle{\rm
Pr}_{z,f}\Big{[}p_{z}(f+g)\geq\frac{\tau}{2^{n}}\Big{]}\geq\frac{(1-\tau)^{2}}{3}$

for any $0<\tau<1$.

Then we have

$\displaystyle|p_{z}(f+g)-\tilde{q}_{z}(f+g)|$ $\displaystyle\leq$
$\displaystyle|p_{z}(f+g)-q_{z}(f+g)|+|q_{z}(f+g)-\tilde{q}_{z}(f+g)|$
$\displaystyle\leq$ $\displaystyle|p_{z}(f+g)-q_{z}(f+g)|+\xi q_{z}(f+g)$
$\displaystyle\leq$
$\displaystyle|p_{z}(f+g)-q_{z}(f+g)|+\xi(p_{z}(f+g)+|p_{z}(f+g)-q_{z}(f+g)|)$
$\displaystyle=$ $\displaystyle\xi p_{z}(f+g)+|p_{z}(f+g)-q_{z}(f+g)|(1+\xi)$
$\displaystyle\leq$ $\displaystyle\xi
p_{z}(f+g)+\frac{\epsilon}{2^{n}\delta}(1+\xi)\leavevmode\nobreak\
\leavevmode\nobreak\ \mbox{(for at least $1-\delta$ fraction of $z$)}$
$\displaystyle\leq$ $\displaystyle\xi p_{z}(f+g)+\sigma
p_{z}(f+g)(1+\xi)\leavevmode\nobreak\ \leavevmode\nobreak\ \mbox{(for at least
$\frac{(1-\frac{\epsilon}{\sigma\delta})^{2}}{3}$ fraction of $(z,f)$)}$
$\displaystyle=$ $\displaystyle p_{z}(f+g)\Big{(}\sigma+(1+\sigma)\xi\Big{)}$
$\displaystyle=$ $\displaystyle p_{z}(f+g)u\leavevmode\nobreak\
\leavevmode\nobreak\ \mbox{(We take $u\equiv\sigma+(1+\sigma)\xi$)}.$

If we take $\epsilon$ and $\delta$ such that
$-\delta+\frac{1}{3}(1-\frac{\epsilon}{\sigma\delta})^{2}=v$, the above
inequality is correct for at least $v$ fraction of $(z,f)$, which contradict
Conjecture 2.

##  4 Clifford plus $T$

In this section, we finally show additive-error fine-grained quantum supremacy
for Clifford+$T$ circuits. Let us consider the following conjecture.

###### Conjecture 3

Let $g:\\{0,1\\}^{n}\to\\{0,1\\}$ be a 3-CNF with $m$ clauses, and
$f:\\{0,1\\}^{n}\to\\{0,1\\}$ be an $n$-variable degree-2 polynomial over
${\mathbb{F}}_{2}$. Define

$\displaystyle gap(f+g)\equiv\sum_{x\in\\{0,1\\}^{n}}(-1)^{f(x)+g(x)}.$

There exist $g$, and positive constants $a$ and $n_{0}$ such that for every
$n>n_{0}$ the following holds. Computing $[gap(f+g)]^{2}$ within a
multiplicative error $u$ for at least $v$ fraction of $f$ cannot be done with
a classical probabilistic $O^{*}(2^{am})$-time algorithm that makes queries of
length $O(2^{am})$ to an ${\rm NTIME}[n^{2}]$ oracle with a success
probability at least $w$.

Based on Conjecture 3, we show the following result.

###### Theorem 3

If Conjecture 3 is true, then there exists a quantum circuit over Clifford
gates and $t$ $T$ gates whose output probability distribution cannot be
classically sampled in $O(2^{\frac{a(t+14)}{42}})$-time within a certain
constant additive error $\epsilon$.

Proof of Theorem 3. Given a 3-CNF $g:\\{0,1\\}^{n}\to\\{0,1\\}$, we can
construct a quantum circuit $U$ such that

$\displaystyle
U(|x\rangle\otimes|0^{\xi}\rangle)=|g(x)\rangle\otimes|junk(x)\rangle$

for any $x\in\\{0,1\\}^{n}$, where $\xi\equiv 3m-1$, and
$junk(x)\in\\{0,1\\}^{n+\xi-1}$ is a certain bit string whose detail is
irrelevant here. Note that $U$ consists of Clifford and $7(3m-1)$ number of
$T$ gates. (The 3-CNF $g$ contains $2m$ OR gates and $m-1$ AND gates. Each AND
and OR gate can be simulated with a single Toffoli gate by using a single
ancilla qubit. A single Toffoli gate can be simulated with Clifford and 7 $T$
gates.) Let us consider the following circuit.

  * 1.

The initial state is $|0^{n}\rangle\otimes|0^{\xi}\rangle$.

  * 2.

Apply $H^{\otimes n}\otimes I^{\otimes\xi}$ to obtain

$\displaystyle\frac{1}{\sqrt{2^{n}}}\sum_{x\in\\{0,1\\}^{n}}|x\rangle\otimes|0^{\xi}\rangle.$

  * 3.

Apply $U$ to obtain

$\displaystyle\frac{1}{\sqrt{2^{n}}}\sum_{x\in\\{0,1\\}^{n}}|g(x)\rangle\otimes|junk(x)\rangle.$

  * 4.

Apply $Z\otimes I^{\otimes n+\xi-1}$ to obtain

$\displaystyle\frac{1}{\sqrt{2^{n}}}\sum_{x\in\\{0,1\\}^{n}}(-1)^{g(x)}|g(x)\rangle\otimes|junk(x)\rangle.$

  * 5.

Apply $U^{\dagger}$ to obtain

$\displaystyle\frac{1}{\sqrt{2^{n}}}\sum_{x\in\\{0,1\\}^{n}}(-1)^{g(x)}|x\rangle\otimes|0^{\xi}\rangle.$

  * 6.

Apply $Z$ and $CZ$ that correspond to $f$ to obtain

$\displaystyle\frac{1}{\sqrt{2^{n}}}\sum_{x\in\\{0,1\\}^{n}}(-1)^{g(x)+f(x)}|x\rangle\otimes|0^{\xi}\rangle.$

  * 7.

Apply $H^{\otimes n}\otimes I^{\otimes\xi}$ and measure all qubits in the
first register in the computational basis.

This quantum computing uses $t\equiv 14(3m-1)$ number of $T$ gates. The
probability of obtaining $z\in\\{0,1\\}^{n}$ is

$\displaystyle p_{z}(f+g)$ $\displaystyle=$
$\displaystyle\Big{|}\frac{1}{2^{n}}\sum_{x\in\\{0,1\\}^{n}}(-1)^{f(x)+\sum_{j=1}^{n}x_{j}z_{j}+g(x)}\Big{|}^{2}.$

Assume that there exists a $T$-time classical probabilistic algorithm that
outputs $z\in\\{0,1\\}^{n}$ with probability $q_{z}(f+g)$ such that

$\displaystyle\sum_{z\in\\{0,1\\}^{n}}|p_{z}(f+g)-q_{z}(f+g)|\leq\epsilon.$

From Markov’s inequality,

$\displaystyle{\rm
Pr}_{z}\Big{[}|p_{z}(f+g)-q_{z}(f+g)|\geq\frac{\epsilon}{2^{n}\delta}\Big{]}\leq\delta$

for any $f$, $g$, and $\delta>0$. According to the fine-grained Stockmeyer’s
theorem, a classical $O^{*}(T)$-time probabilistic algorithm that makes
queries of length $O(T)$ to the ${\rm NTIME}[n^{2}]$ oracle can compute
$\tilde{q}_{z}(f+g)$ such that

$\displaystyle|q_{z}(f+g)-\tilde{q}_{z}(f+g)|\leq\xi q_{z}(f+g),$

where

$\displaystyle\xi\equiv\frac{2^{\frac{1}{\alpha}}-2^{-\frac{1}{\alpha}}}{2},$

for any $f$, $g$, integer $\alpha\geq 1$, and $z\in\\{0,1\\}^{n}$, with a
success probability at least $w$. Due to the anti-concentration lemma [4]

$\displaystyle{\rm
Pr}_{z,f}\Big{[}p_{z}(f+g)\geq\frac{\tau}{2^{n}}\Big{]}\geq\frac{(1-\tau)^{2}}{3}$

for any $0<\tau<1$.

Then we have

$\displaystyle|p_{z}(f+g)-\tilde{q}_{z}(f+g)|$ $\displaystyle\leq$
$\displaystyle|p_{z}(f+g)-q_{z}(f+g)|+|q_{z}(f+g)-\tilde{q}_{z}(f+g)|$
$\displaystyle\leq$ $\displaystyle|p_{z}(f+g)-q_{z}(f+g)|+\xi q_{z}(f+g)$
$\displaystyle\leq$
$\displaystyle|p_{z}(f+g)-q_{z}(f+g)|+\xi(p_{z}(f+g)+|p_{z}(f+g)-q_{z}(f+g)|)$
$\displaystyle=$ $\displaystyle\xi p_{z}(f+g)+|p_{z}(f+g)-q_{z}(f+g)|(1+\xi)$
$\displaystyle\leq$ $\displaystyle\xi
p_{z}(f+g)+\frac{\epsilon}{2^{n}\delta}(1+\xi)\leavevmode\nobreak\
\leavevmode\nobreak\ \mbox{(for at least $1-\delta$ fraction of $z$)}$
$\displaystyle\leq$ $\displaystyle\xi p_{z}(f+g)+\sigma
p_{z}(f+g)(1+\xi)\leavevmode\nobreak\ \leavevmode\nobreak\ \mbox{(for at least
$\frac{(1-\frac{\epsilon}{\sigma\delta})^{2}}{3}$ fraction of $(z,f)$)}$
$\displaystyle=$ $\displaystyle p_{z}(f+g)\Big{(}\sigma+(1+\sigma)\xi\Big{)}$
$\displaystyle=$ $\displaystyle p_{z}(f+g)u\leavevmode\nobreak\
\leavevmode\nobreak\ \mbox{(We take $u\equiv\sigma+(1+\sigma)\xi$)}.$

If we take $\epsilon$ and $\delta$ such that
$-\delta+\frac{1}{3}(1-\frac{\epsilon}{\sigma\delta})^{2}=v$, the above
inequality is correct for at least $v$ fraction of $(z,f)$, which contradict
Conjecture 3.

##  5 Discussion

###  5.1 Conjectures

In this paper, we have shown additive-error fine-grained quantum supremacy
based on several conjectures. In this subsection, we provide some “evidence"
that support these conjectures.

Our conjectures are related to the exponential-time hypothesis (ETH) and the
strong exponential-time hypothesis (SETH) that are standard conjectures in
fine-grained complexity theory [25, 26]. ETH and SETH are stronger (or more
pessimistic) versions of the famous ${\rm NP}\neq{\rm P}$ conjecture that says
that an NP-complete problem cannot be solved in polynomial-time. More
precisely, ETH is stated as follows:

###### Conjecture 4

(ETH) Any (classical) deterministic algorithm that decides whether $\\#f>0$ or
$\\#f=0$ given (a description of) a 3-CNF with $n$ variables,
$f:\\{0,1\\}^{n}\to\\{0,1\\}$, needs $2^{\Omega(n)}$ time. Here,
$\\#f\equiv\sum_{x\in\\{0,1\\}^{n}}f(x)$.

SETH is the stronger version of ETH which says as follows:

###### Conjecture 5

(SETH) Let $A$ be any (classical) deterministic $T(n)$-time algorithm such
that the following holds: given (a description of) a CNF,
$f:\\{0,1\\}^{n}\to\\{0,1\\}$, with at most $cn$ clauses, $A$ accepts if
$\\#f>0$ and rejects if $\\#f=0$, where
$\\#f\equiv\sum_{x\in\\{0,1\\}^{n}}f(x)$. Then, for any constant $a>0$, there
exists a constant $c>0$ such that $T(n)>2^{(1-a)n}$ holds for infinitely many
$n$.

All conjectures used in this paper are the average-case hardness of computing
GapP functions within a multiplicative error in classical probabilistic time
with an NTIME oracle, and therefore different from ETH and SETH. There are,
however, three reasons that support these conjectures.

First, our conjectures consider GapP functions, while ETH and SETH consider
$\\#$P functions. A GapP function is a difference of two $\\#$P functions.
Furthermore, to our knowledge, only known way of computing a GapP function is
to compute the number of accepting and rejecting paths (i.e., $\\#$P
functions). Therefore, computing GapP functions should not be easier than
computing $\\#$P functions.

Second, our conjectures study average cases. One might think that solving an
average case could be easier than the worst case, but, at least, SETH has not
been refuted even in average cases. (The best upper-bound is Ref. [27].)

Third, our conjectures allow the algorithm to use an NTIME oracle. We point
out that at least $\\#$ETH, which is the counting version of ETH, has not been
refuted for MA (which is in ${\rm ZPP}^{\rm NP}$) and AM (which is ${\rm
coNP}^{\rm NP}$).

It is an important open problem for the research of (not only fine-grained but
also non-fine-grained) quantum supremacy to show additive-error quantum
supremacy based on standard conjectures.

###  5.2 Other models

For simplicity, we have considered the three models, but similar results
should hold for other sub-universal models such as the one-clean qubit model
and the random circuit model. For all sub-universal models, Markov’s
inequality and the anti-concentration lemma hold. (For the Boson sampling
model, the anti-concentration is a conjecture.) Therefore if we assume similar
average-case hardness conjectures as we have introduced in this paper, we
should be able to show additive-error fine-grained quantum supremacy for other
sub-universal models.

## Acknowledgements

TM thanks Yoshifumi Nakata for discussion. We thank authors of Ref. [14] for
comments on our manuscript, and sharing their draft. We also thank anonymous
reviewers, especially one reviewer who told us some errors and an improvement
of fine-grained Stockmeyer’s theorem. TM is supported by MEXT Q-LEAP, JST
PRESTO No.JPMJPR176A, and the Grant-in-Aid for Young Scientists (B)
No.JP17K12637 of JSPS. ST is supported by JSPS KAKENHI Grant Numbers 16H02782,
18H04090, and 18K11164.

##  Appendix A Appendix

In this Appendix, we provide a proof of the fine-grained Stockmeyer’s theorem.
The proof is a straightforward generalization of the one given in Ref. [28].

###  A.1 A pairwise independent hash family and the leftover hash lemma

To show the fine-grained Stockmeyer’s theorem, we need the following two
lemmas. Their proofs can be found in standard text books of complexity theory,
such as Ref. [29].

######  Lemma 1 (A pairwise independent hash family)

Let $A$ be a random $m\times n$ binary Toeplitz matrix, and $b$ be a random
$m$-dimensional binary vector. (Here, a Toeplitz matrix is a matrix whose
matrix elements satisfy $a_{i,j}=a_{i+1,j+1}$.) Then, the family
$H\equiv\\{h_{A,b}\\}_{A,b}$ of functions,
$h_{A,b}:\\{0,1\\}^{n}\to\\{0,1\\}^{m}$, with $h_{A,b}(x)\equiv Ax+b$
satisfies

$\displaystyle{\rm Pr}_{A,b}[h_{A,b}(x_{1})=y_{1}\wedge
h_{A,b}(x_{2})=y_{2}]=\frac{1}{2^{2m}}$

for any $x_{1}\neq x_{2}\in\\{0,1\\}^{n}$ and $y_{1},y_{2}\in\\{0,1\\}^{m}$.

######  Lemma 2 (The leftover hash lemma)

Let $S\subseteq\\{0,1\\}^{n}$ be a set of $n$-bit strings. Then

$\displaystyle{\rm Pr}_{A,b}\Big{[}\Big{|}|\\{x\in
S:h_{A,b}(x)=0^{m}\\}|-\frac{|S|}{2^{m}}\Big{|}\geq\epsilon\frac{|S|}{2^{m}}\Big{]}\leq\frac{2^{m}}{\epsilon^{2}|S|}.$

###  A.2 Algorithm $A_{k}$

In this subsection, we construct the algorithm $A_{k}$, which is used for
fine-grained Stockmeyer’s theorem. Let $G$ be an $n$-time deterministic
classical algorithm. Let $S\equiv\\{x\in\\{0,1\\}^{n}:G(x)=1\\}$. Let $k$ be
an integer such that $1\leq k\leq n$. We construct a classical probabilistic
$O(rn)$-time algorithm $A_{k}$ that gets a description of $G$ as the input,
and that makes queries of length $O(n)$ to the ${\rm NTIME}[n^{2}]$ oracle
such that

  * •

If $|S|\geq 2^{k+1}$ then ${\rm Pr}[A_{k}\leavevmode\nobreak\ {\rm
accepts}]\geq 1-e^{-r}$.

  * •

If $|S|<2^{k}$ then ${\rm Pr}[A_{k}\leavevmode\nobreak\ {\rm accepts}]\leq
e^{-r}$.

To construct $A_{k}$, let us consider the following algorithm.

  * 1.

If $k\leq 5$, query the ${\rm NTIME}[n]$ oracle whether $|S|\geq 2^{k+1}$ or
not. (The query to the oracle is the description of $G$. Given the description
of $G$, deciding $|S|\geq 2^{k+1}$ or not is in ${\rm NTIME}[n]$.) Accept if
the oracle answer is yes. If the oracle answer is no, reject.

  * 2.

If $k\geq 6$, set $m\equiv k-5$. Randomly choose an $m\times n$ binary
Toeplitz matrix $A$, and an $m$-dimensional binary vector $b$. It takes
$n+2m-1=O(n)$ time. Define the function
$h_{A,b}:\\{0,1\\}^{n}\to\\{0,1\\}^{m}$ by $h_{A,b}(x)\equiv Ax+b$. Query the
${\rm NTIME}[n^{2}]$ oracle whether $|\\{x\in S:h_{A,b}(x)=0^{m}\\}|\geq 48$
or not. (The query to the oracle is the description of $G$, $A$, and $b$.
Given the description of $G$, $A$, and $b$, deciding $|\\{x\in
S:h_{A,b}(x)=0^{m}\\}|\geq 48$ or not is in ${\rm NTIME}[n^{2}]$.) If the
oracle answer is yes, accept. If the oracle answer is no, reject.

Assume that $k\leq 5$. Then, if $|S|\geq 2^{k+1}$, the probability that the
algorithm accepts is 1. If $|S|<2^{k}$, the probability that the algorithm
accepts is 0.

Assume that $k\geq 6$. If $|S|\geq 2^{k+1}$, then $|S|\geq 2^{m+6}$ and
therefore

$\displaystyle{\rm Pr}[{\rm reject}]$ $\displaystyle=$ $\displaystyle{\rm
Pr}_{A,b}\Big{[}|\\{x\in S:h_{A,b}(x)=0^{m}\\}|<48\Big{]}$ $\displaystyle\leq$
$\displaystyle{\rm Pr}_{A,b}\Big{[}|\\{x\in
S:h_{A,b}(x)=0^{m}\\}|\leq\frac{3}{4}\frac{|S|}{2^{m}}\Big{]}$
$\displaystyle=$ $\displaystyle{\rm Pr}_{A,b}\Big{[}-|\\{x\in
S:h_{A,b}(x)=0^{m}\\}|+\frac{|S|}{2^{m}}\geq\frac{1}{4}\frac{|S|}{2^{m}}\Big{]}$
$\displaystyle\leq$ $\displaystyle{\rm Pr}_{A,b}\Big{[}\Big{|}|\\{x\in
S:h_{A,b}(x)=0^{m}\\}|-\frac{|S|}{2^{m}}\Big{|}\geq\frac{1}{4}\frac{|S|}{2^{m}}\Big{]}$
$\displaystyle\leq$ $\displaystyle\frac{2^{m+4}}{|S|}\leq\frac{1}{4}.$

If $|S|<2^{k}$, define a superset $S^{\prime}\supseteq S$ with
$|S^{\prime}|=2^{k}$. Then,

$\displaystyle{\rm Pr}[{\rm accept}]$ $\displaystyle=$ $\displaystyle{\rm
Pr}_{A,b}\Big{[}|\\{x\in S:h_{A,b}(x)=0^{m}\\}|\geq 48\Big{]}$
$\displaystyle\leq$ $\displaystyle{\rm Pr}_{A,b}\Big{[}|\\{x\in
S^{\prime}:h_{A,b}(x)=0^{m}\\}|\geq 48\Big{]}$ $\displaystyle=$
$\displaystyle{\rm Pr}_{A,b}\Big{[}|\\{x\in
S^{\prime}:h_{A,b}(x)=0^{m}\\}|\geq\frac{3}{2}\frac{|S^{\prime}|}{2^{m}}\Big{]}$
$\displaystyle=$ $\displaystyle{\rm Pr}_{A,b}\Big{[}|\\{x\in
S^{\prime}:h_{A,b}(x)=0^{m}\\}|\geq\frac{|S^{\prime}|}{2^{m}}+\frac{1}{2}\frac{|S^{\prime}|}{2^{m}}\Big{]}$
$\displaystyle=$ $\displaystyle{\rm Pr}_{A,b}\Big{[}|\\{x\in
S^{\prime}:h_{A,b}(x)=0^{m}\\}|-\frac{|S^{\prime}|}{2^{m}}\geq\frac{1}{2}\frac{|S^{\prime}|}{2^{m}}\Big{]}$
$\displaystyle\leq$ $\displaystyle{\rm Pr}_{A,b}\Big{[}\Big{|}|\\{x\in
S^{\prime}:h_{A,b}(x)=0^{m}\\}|-\frac{|S^{\prime}|}{2^{m}}\Big{|}\geq\frac{1}{2}\frac{|S^{\prime}|}{2^{m}}\Big{]}$
$\displaystyle\leq$ $\displaystyle\frac{2^{m+2}}{|S^{\prime}|}=\frac{1}{8}.$

Therefore we have constructed the algorithm such that

  * •

If $|S|\geq 2^{k+1}$ then ${\rm Pr}[{\rm accept}]\geq\frac{3}{4}$.

  * •

If $|S|<2^{k}$ then ${\rm Pr}[{\rm accept}]\leq\frac{1}{8}$.

By repeating this algorithm $O(r)$ times, we get the final result.

###  A.3 Fine-grained Stockmeyer’s theorem

###### Theorem 4

For any classical probabilistic $T$-time algorithm that outputs
$z\in\\{0,1\\}^{N}$ with probability $q_{z}$, and any constant integer
$\alpha\geq 1$, there exists a $O(T\log(T)\log\log(T))$-time classical
probabilistic algorithm that makes queries of length $O(T)$ to the
NTIME[$n^{2}$] oracle that outputs $\tilde{q}_{z}$ such that

$\displaystyle|q_{z}-\tilde{q}_{z}|\leq\frac{2^{\frac{1}{\alpha}}-2^{-\frac{1}{\alpha}}}{2}q_{z}$

with a success probability at least $w$ for any $z\in\\{0,1\\}^{N}$. Here, $w$
is a certain constant.

Proof of Theorem 4. Let $C$ be a $T$-time deterministic classical algorithm
such that

$\displaystyle\frac{|\\{r\in\\{0,1\\}^{T}:C(r)=z\\}|}{2^{T}}=q_{z}$

for all $z\in\\{0,1\\}^{N}$. For each $z\in\\{0,1\\}^{N}$, let us define the
set $S_{z}\subseteq\\{0,1\\}^{T}$ by

$\displaystyle S_{z}\equiv\\{r\in\\{0,1\\}^{T}:C(r)=z\\}.$

For any integer $\alpha\geq 1$, define

$\displaystyle
S_{z}^{\times\alpha}\equiv\\{(r_{1},...,r_{\alpha})\in(\\{0,1\\}^{T})^{\times\alpha}:C(r_{1})=...=C(r_{\alpha})=z\\}.$

For $S_{z}^{\times\alpha}$, find an integer $\eta\in\\{1,2,...,\alpha T\\}$
such that $A_{\eta-1}$ accepts and $A_{\eta}$ rejects by the binary search. It
takes classical probabilistic $O(T\log(T)\log\log(T))$-time that makes queries
of length $O(T)$ to the ${\rm NTIME}[n^{2}]$ oracle. (For the binary search,
$O(\log T)$ steps are necessary, and each implementation of the algorithm $A$
takes $O(T\log\log(T))$ steps.) Then,
$2^{\eta-1}<|S_{z}^{\times\alpha}|<2^{\eta+1}$ with a sufficiently small
failure probability.

If we define $\sigma\equiv 2^{\frac{\eta}{\alpha}}$,
$\frac{1}{2}\sigma^{\alpha}<|S_{z}|^{\alpha}<2\sigma^{\alpha}$. Hence
$\Big{(}\frac{1}{2}\Big{)}^{\frac{1}{\alpha}}\sigma<|S_{z}|<2^{\frac{1}{\alpha}}\sigma$.
If we define $\tilde{q}_{z}\equiv\sigma/2^{T}$, we obtain the result.

## References

  * [1] B. M. Terhal and D. P. DiVincenzo, Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games. Quant. Inf. Comput. 4, 134 (2004). DOI:10.26421/QIC4.2
  * [2] S. Aaronson and A. Arkhipov, The computational complexity of linear optics. Theory of Computing 9, 143 (2013). DOI:10.1145/1993636.1993682
  * [3] M. J. Bremner, R. Jozsa, and D. J. Shepherd, Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. R. Soc. A 467, 459 (2011). DOI:10.1098/rspa.2010.0301
  * [4] M. J. Bremner, A. Montanaro, and D. J. Shepherd, Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett. 117, 080501 (2016). DOI:10.1103/PhysRevLett.117.080501
  * [5] E. Knill and R. Laflamme, Power of one bit of quantum information. Phys. Rev. Lett. 81, 5672 (1998). DOI:10.1103/PhysRevLett.81.5672
  * [6] T. Morimae, K. Fujii, and J. F. Fitzsimons, Hardness of classically simulating the one clean qubit model. Phys. Rev. Lett. 112, 130502 (2014). DOI:10.1103/PhysRevLett.112.130502
  * [7] T. Morimae, Hardness of classically sampling one clean qubit model with constant total variation distance error. Phys. Rev. A 96, 040302(R) (2017). DOI:10.1103/PhysRevA.96.040302
  * [8] K. Fujii, H. Kobayashi, T. Morimae, H. Nishimura, S. Tamate, and S. Tani, Impossibility of classically simulating one-clean-qubit model with multiplicative error. Phys. Rev. Lett. 120, 200502 (2018). DOI:10.1103/PhysRevLett.120.200502
  * [9] K. Fujii, H. Kobayashi, T. Morimae, H. Nishimura, S. Tamate, and S. Tani, Power of quantum computation with few clean qubits. Proceedings of 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), pp.13:1-13:14 (2016). DOI:10.4230/LIPIcs.ICALP.2016.13
  * [10] T. Morimae, Y. Takeuchi, and H. Nishimura, Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy. Quantum 2, 106 (2018). 10.22331/q-2018-11-15-106
  * [11] A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, On the complexity and verification of quantum random circuit sampling. Nature Phys. 15, 159 (2019). DOI:10.1038/s41567-018-0318-2
  * [12] R. Movassagh, Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling. arXiv:1810.04681
  * [13] R. Movassagh, Cayley path and quantum computational supremacy: A proof of average-case $\\#P$-hardness of Random Circuit Sampling with quantified robustness. arXiv:1909.06210
  * [14] A. M. Dalzell, A. W. Harrow, D. E. Koh, and R. L. La Placa, How many qubits are needed for quantum computational supremacy? Quantum 4, 264 (2020). DOI:10.22331/q-2020-05-11-264
  * [15] A. M. Dalzell, Bachelor thesis, MIT (2017). https://dspace.mit.edu/handle/1721.1/111859
  * [16] C. Huang, M. Newman, and M. Szegedy, Explicit lower bounds on strong quantum simulation. arXiv:1804.10368
  * [17] C. Huang, M. Newman, and M. Szegedy, Explicit lower bounds on strong simulation of quantum circuits in terms of $T$-gate count. arXiv:1902.04764
  * [18] T. Morimae and S. Tamaki, Fine-grained quantum computational supremacy. Quant. Inf. Comput. 19, 1089 (2019). DOI:10.26421/QIC19.13-14
  * [19] R. Hayakawa, T. Morimae, and S. Tamaki, Fine-grained quantum supremacy based on Orthogonal Vectors, 3-SUM and All-Pairs Shortest Paths. arXiv:1902.08382
  * [20] R. R. Williams, Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation. Proceedings of the 31st Conference on Computational Complexity (CCC’16), pages 1-17 (2016). DOI:10.4230/LIPIcs.CCC.2016.2
  * [21] Dell and Lapinskas, Fine-grained reductions from approximate counting to decision. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), pages 281-288 (2018). 10.1145/3188745.3188920
  * [22] R. Williams, Counting solutions to polynomial systems via reductions. Proceedings of the 1st Symposium on Simplicity in Algorithms (SOSA 2018). DOI:10.4230/OASIcs.SOSA.2018.6
  * [23] D. Lokshtanov, R. Paturi, S. Tamaki, R. Williams, and H. Yu, Beating brute force for systems of polynomial equations over finite fields. Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.2190-2202 (2017). DOI:10.1137/1.9781611974782.143
  * [24] A. Cosentino, R. Kothari, and A. Paetznick, Dequantizing read-once quantum formulas. arXiv:1304.5164; 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013), Leibniz International Proceedings in Informatics (LIPIcs) 22, pp. 80-92 (2013). 10.4230/LIPIcs.TQC.2013.80
  * [25] R. Impagliazzo, R. Paturi, and F. Zane, Which problems have stronly exponential complexity? J. Comput. Syst. Sci. 63(4), 512-530 (2001). DOI:10.1006/jcss.2001.1774
  * [26] R. Impagliazzo and R. Paturi, On the complexity of $k$-SAT. J. Comput. Syst. Sci. 62(2), 367-375 (2001). DOI:10.1006/jcss.2000.1727
  * [27] A. Lincoln and A. Yedidia, Faster random $k$-CNF satisfiability. 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). DOI:10.4230/LIPIcs.ICALP.2020.78
  * [28] L. Trevisan, Lecture notes on computational complexity.
  * [29] O. Goldreich, Computational Complexity: a conceptual perspective. Cambridge University Press (2008).


# PyGOD: A Python Library for Graph Outlier Detection

Kay Liu1<EMAIL_ADDRESS>
Yingtong Dou1,6††footnotemark<EMAIL_ADDRESS>
Yue Zhao2††footnotemark<EMAIL_ADDRESS>
Xueying Ding2<EMAIL_ADDRESS>
Xiyang Hu2<EMAIL_ADDRESS>
Ruitong Zhang3<EMAIL_ADDRESS>
Kaize Ding4<EMAIL_ADDRESS>
Canyu Chen5<EMAIL_ADDRESS>
Hao Peng3<EMAIL_ADDRESS>
Kai Shu5<EMAIL_ADDRESS>
George H. Chen2<EMAIL_ADDRESS>
Zhihao Jia2<EMAIL_ADDRESS>
Philip S. Yu1<EMAIL_ADDRESS>
1University of Illinois Chicago, 2Carnegie Mellon University, 3Beihang
University, 4Arizona State University, 5Illinois Institute of Technology,
6VISA Research Equal contribution

###### Abstract

PyGOD is an open-source Python library for detecting outliers on graph data.
As the first comprehensive library of its kind, PyGOD supports a wide array of
leading graph-based methods for node-, edge-, subgraph-, and graph-level
outlier detection, under a unified, well-documented API designed for use by
both researchers and practitioners. To overcome the scalability issue in large
graphs, we provide advanced functionalities for selected models, including
mini-batch and sampling. PyGOD is equipped with best practices to foster code
reliability and maintainability, including unit testing, continuous
integration, and code coverage. To foster accessibility, PyGOD is released
under a permissive BSD-license at https://github.com/pygod-team/pygod/ and the
Python Package Index (PyPI).

Keywords: outlier detection, anomaly detection, graph learning, graph neural
networks

##  1 Introduction

Outlier detection (OD), also known as anomaly detection, is a key machine
learning task to identify the deviant samples from the general data
distribution (Aggarwal, 2017; Li et al., 2022). With the increasing importance
of graph data in both research and real-world applications (Ding et al.,
2021b; Huang et al., 2021; Fu et al., 2021; Zhou et al., 2021; Xu et al.,
2022), detecting outliers with graph-based methods such as graph neural
networks (GNNs) recently have drawn much attention (Ma et al., 2021; Ding et
al., 2019b, 2021a) with many applications such as detecting suspicious
activities in social networks (Sun et al., 2018; Dou et al., 2020) and
security systems (Cai et al., 2021).

Although there is a long list of established libraries for detecting outliers
in tabular and time-series data in multiple programming languages, e.g., PyOD
(Zhao et al., 2019), SUOD (Zhao et al., 2021b), PyODDs (Li et al., 2020), ELKI
(Achtert et al., 2010), OutlierDetection.jl (Muhr et al., 2022), PyTOD (Zhao
et al., 2021a), TODS (Lai et al., 2021), Telemanom (Hundman et al., 2018), a
specialized library for graph outlier detection is absent.

Algorithm | Supervision | Level | Backbone | Mini-batch
---|---|---|---|---
MLPAE (Sakurada and Yairi, 2014) | Unsupervised | Node | MLP | Yes
GCNAE (Kipf and Welling, 2016) | Unsupervised | Node | GNN | Yes
ONE (Bandyopadhyay et al., 2019) | Unsupervised | Node | MF | No
DOMINANT (Ding et al., 2019a) | Unsupervised | Node | GNN | Yes
DONE (Bandyopadhyay et al., 2020) | Unsupervised | Node | GNN | Yes
AdONE (Bandyopadhyay et al., 2020) | Unsupervised | Node | GNN | Yes
AnomalyDAE (Fan et al., 2020) | Unsupervised | Node | GNN | In progress
GAAN (Chen et al., 2020) | Unsupervised | Node | GAN | Yes
OCGNN (Wang et al., 2021) | Unsupervised | Node | GNN | Yes
GUIDE (Yuan et al., 2021) | Unsupervised | Node | GNN | Yes
CONAD (Xu et al., 2022) | Unsupervised/SSL | Node | GNN | In progress
CoLA (Xu et al., 2022) | Unsupervised/SSL | Node | GNN | In progress

Table 1: Select outlier detection models in PyGOD V0.2.0

To tap this gap, we design the first comprehensive Python Graph Outlier
Detection library called PyGOD, with a couple of key technical advancement and
contributions. First, it covers a wide array of algorithms from node to graph
level detection, with varying availability of labels/supervision. Table 1
shows that PyGOD already supports more than ten leading algorithms. Second,
PyGOD streamlines the accessibility of detection models with a unified API
design. From the user perspective, one only needs to prepare the data into a
predefined graph format—all outlier detectors in PyGOD are then capable of
processing and handling it. Third, PyGOD supports large-scale detection via
mini-batch and sampling, which can facilitate detection on large graphs. With
code clarity and quality in mind, we offer detailed API documentation and
examples, and enable unit testing with cross-platform continuous integration
along with code coverage and maintainability checks.

Figure 1: Demonstration of PyGOD’s unified API design

##  2 Library Design and Implementation

Dependency. PyGOD builds for Python 3.6+, and depends on popular Pytorch
(Paszke et al., 2019) and Pytorch Geometric (PyG) (Fey and Lenssen, 2019) for
effective graph learning on both CPUs and GPUs. Additionally, it uses numpy
(Harris et al., 2020), scipy (Virtanen et al., 2020), and scikit-learn
(Pedregosa et al., 2011) for data manipulation.

API Design. Inspired by the API design of scikit-learn (Buitinck et al., 2013)
and PyOD (Zhao et al., 2019), all detection algorithms in PyGOD inherit from a
base class with the same API interface: (i) fit trains the detection model,
gets the outlier scores (the higher, the more outlying) and labels on the
input data, and generates necessary statistics for prediction (in the
inductive setting); (ii) decision_function leverages the trained model to
predict the raw outlier scores of the incoming data (in the inductive
setting); (iii) predict returns the binary prediction using the trained model
(0 for normal samples and 1 for outliers); and (iv) predict_proba returns the
probability of samples being outlier using the leading method (Kriegel et al.,
2011). Meanwhile, we also include the recent advance in providing the
confidence score in outlier detection (Perini et al., 2020) for the above
prediction methods. The usage of the above APIs is demonstrated in Code demo
1.

⬇

1 from torch_geometric.datasets import Planetoid # import data from PyG

2 from pygod.utils import gen_attribute_outliers # import injection func

3

4 data = Planetoid("Cora")[0] # load data in PyG format

5 data, y = gen_attribute_outliers(data, n=100) # inject outliers

6

7 from pygod.models import DOMINANT # import the model

8 model = DOMINANT(num_layers=2) # init. detection model

9 model.fit(data) # fit with data

10

11 pred_label = model.predict(data) # predict binary labels

12 pred_scores = model.decision_function(data) # predict outlier scores

13 pred_proba = model.predict_proba(data) # predict probability

14

15 from pygod.utils.metric import eval_recall_at_k, eval_precision_at_k

16 eval_recall_at_k(y.numpy(), pred_scores) # eval. by recall

17 eval_precision_at_k(y.numpy(), pred_scores) # eval. by precision

Code demo 1: Using Dominant (Ding et al., 2019a) on Cora data (Morris et al.,
2020)

Streamlined Graph Learning with PyG. We choose to develop PyGOD on top of the
popular PyG Llibrary for multiple reasons. First, this reduces the complexity
in processing graph data for users. That is, PyGOD only requires the input
data to be in the standard graph data format in PyG111PyG data object:
https://pytorch-geometric.readthedocs.io/en/latest/modules/data.html. Notably,
different detection models need distinct information from a PyG graph. Within
the implementation of each detection model, we design an abstract
process_graph method to extract necessary information, e.g., the adjacency
matrix, node, and edge attributes, etc., for the underlying detection
algorithm. Second, most of the detection algorithms share common backbones
(see Table 1) like graph convolutional neural networks (GCN) (Kipf and
Welling, 2017) and graph autoencoders (Kipf and Welling, 2016), where PyG
already provides optimized implementation. Third, PyG is the most popular GNN
libraries with advanced functions like graph sampling and distributed
training. Under the PyG framework, we enable and implement mini-batch and/or
sampling for selected models to accommodate the learning with large graphs as
shown in Table 1.

In addition to the detection models, a set of helpful utility functions is
designed to facilitate graph outlier detection. Evaluation-wise, PyGOD
provides common metrics for graph OD in the utils.metric module. Data-wise,
PyGOD offers outlier injection methods for both structure and attribute
settings (Ding et al., 2019a) in utils.outlier_generator, as a solution to
model evaluation and benchmarking.

##  3 Library Robustness and Accessibility

Robustness and Quality. While building PyGOD, we follow the best practices of
system design and software development. First, we leverage the continuous
integration by GitHub Actions222Continuous integration by GitHub Actions:
https://github.com/pygod-team/pygod/actions to automate the testing process
under various Python versions and operating systems. In addition to the
scheduled daily test, both commits and pull requests trigger the unit testing.
Notably, we enforce all code to have at least 90% coverage333Code coverage by
Coveralls: https://coveralls.io/github/pygod-team/pygod. By following the PEP8
standard, we enforce a consistent coding style and naming convention, which
facilitates the community collaboration and code readability.

Accessibility. PyGOD comes with detailed API documentation rendered by Read
the Docs444Documentation: https://docs.pygod.org/. Within the documentation,
installation guide and interactive examples in Jupyter notebooks are provided.
To facilitate community contribution, the project is hosted on GitHub with
friendly contribution guide and issue reporting mechanism.

##  4 Conclusion and Future Plans

In this paper, we present the first comprehensive library for graph outlier
detection, called PyGOD. Uniquely, it supports a wide range of detection
algorithms with unified APIs, rich documentation, and robust code design,
which are readily useful for both academic research and industry applications.
The development plan of PyGOD will focus on multiple aspects: (i) including
more algorithms for different sub-tasks, e.g., outlier detection in edges and
sub-graphs; (ii) collaborating with industries to make PyGOD more practical
and tailor the needs of practitioners; (iii) optimizing its accessibility and
scalability with the latest advancement in graph (Jia et al., 2020); and (iv)
incorporate automated machine learning to enable intelligent model selection
and hyperparameter tuning (Zhao et al., 2021c).

Acknowledgments

The authors of this paper were supported by NSF under grants III-1763325,
III-1909323, III-2106758, and SaTC-1930941.

## References

  * Achtert et al. (2010) E. Achtert, H.-P. Kriegel, L. Reichert, E. Schubert, R. Wojdanowski, and A. Zimek.  Visual evaluation of outlier detection models.  In _Proceedings of the DASFAA_ , pages 396–399. Springer, 2010.
  * Aggarwal (2017) C. C. Aggarwal.  An introduction to outlier analysis.  In _Outlier analysis_ , pages 1–34. Springer, 2017.
  * Bandyopadhyay et al. (2019) S. Bandyopadhyay, N. Lokesh, and M. N. Murty.  Outlier aware network embedding for attributed networks.  In _Proceedings of the AAAI conference_ , volume 33, pages 12–19, 2019.
  * Bandyopadhyay et al. (2020) S. Bandyopadhyay, S. V. Vivek, and M. Murty.  Outlier resistant unsupervised deep architectures for attributed network embedding.  In _Proceedings of the WSDM_ , pages 25–33, 2020.
  * Buitinck et al. (2013) L. Buitinck, G. Louppe, M. Blondel, F. Pedregosa, A. Mueller, O. Grisel, V. Niculae, P. Prettenhofer, A. Gramfort, J. Grobler, R. Layton, J. VanderPlas, A. Joly, B. Holt, and G. Varoquaux.  API design for machine learning software: experiences from the scikit-learn project.  In _Proceedings of ECML PKDD Workshop: Languages for Data Mining and Machine Learning_ , pages 108–122, 2013.
  * Cai et al. (2021) L. Cai, Z. Chen, C. Luo, J. Gui, J. Ni, D. Li, and H. Chen.  Structural temporal graph neural networks for anomaly detection in dynamic graphs.  In _Proceedings of the ACM CIKM_ , pages 3747–3756, 2021.
  * Chen et al. (2020) Z. Chen, B. Liu, M. Wang, P. Dai, J. Lv, and L. Bo.  Generative adversarial attributed network anomaly detection.  In _Proceedings of the ACM CIKM_ , pages 1989–1992, 2020.
  * Ding et al. (2019a) K. Ding, J. Li, R. Bhanushali, and H. Liu.  Deep anomaly detection on attributed networks.  In _Proceedings of the SDM_ , pages 594–602. SIAM, 2019a.
  * Ding et al. (2019b) K. Ding, J. Li, and H. Liu.  Interactive anomaly detection on attributed networks.  In _Proceedings of the ACM WSDM_ , pages 357–365, 2019b.
  * Ding et al. (2021a) K. Ding, J. Li, N. Agarwal, and H. Liu.  Inductive anomaly detection on attributed networks.  In _Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence_ , pages 1288–1294, 2021a.
  * Ding et al. (2021b) K. Ding, Q. Zhou, H. Tong, and H. Liu.  Few-shot network anomaly detection via cross-network meta-learning.  In _Proceedings of the Web Conference 2021_ , pages 2448–2456, 2021b.
  * Dou et al. (2020) Y. Dou, Z. Liu, L. Sun, Y. Deng, H. Peng, and P. S. Yu.  Enhancing graph neural network-based fraud detectors against camouflaged fraudsters.  In _Proceedings of the ACM CIKM_ , pages 315–324, 2020.
  * Fan et al. (2020) H. Fan, F. Zhang, and Z. Li.  Anomalydae: Dual autoencoder for anomaly detection on attributed networks.  In _Proceedings of the IEEE ICASSP_ , pages 5685–5689, 2020.
  * Fey and Lenssen (2019) M. Fey and J. E. Lenssen.  Fast graph representation learning with PyTorch Geometric.  In _Proceedings of the ICLR Workshop on Representation Learning on Graphs and Manifolds_ , 2019.
  * Fu et al. (2021) T. Fu, C. Xiao, X. Li, L. M. Glass, and J. Sun.  Mimosa: Multi-constraint molecule sampling for molecule optimization.  In _Proceedings of the AAAI Conference_ , volume 35, pages 125–133, 2021.
  * Harris et al. (2020) C. R. Harris, K. J. Millman, S. J. Van Der Walt, R. Gommers, P. Virtanen, D. Cournapeau, E. Wieser, J. Taylor, S. Berg, N. J. Smith, et al.  Array programming with numpy.  _Nature_ , 585(7825):357–362, 2020.
  * Huang et al. (2021) K. Huang, T. Fu, W. Gao, Y. Zhao, Y. H. Roohani, J. Leskovec, C. W. Coley, C. Xiao, J. Sun, and M. Zitnik.  Therapeutics data commons: Machine learning datasets and tasks for drug discovery and development.  In _Proceedings of the Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1)_ , 2021\.
  * Hundman et al. (2018) K. Hundman, V. Constantinou, C. Laporte, I. Colwell, and T. Soderstrom.  Detecting spacecraft anomalies using lstms and nonparametric dynamic thresholding.  In _Proceedings of the ACM SIGKDD_ , pages 387–395, 2018.
  * Jia et al. (2020) Z. Jia, S. Lin, M. Gao, M. Zaharia, and A. Aiken.  Improving the accuracy, scalability, and performance of graph neural networks with roc.  _Proceedings of the MLSys_ , 2:187–198, 2020.
  * Kipf and Welling (2016) T. N. Kipf and M. Welling.  Variational graph auto-encoders.  _arXiv preprint arXiv:1611.07308_ , 2016.
  * Kipf and Welling (2017) T. N. Kipf and M. Welling.  Semi-supervised classification with graph convolutional networks.  In _Proceedings of the ICLR_ , 2017.
  * Kriegel et al. (2011) H.-P. Kriegel, P. Kroger, E. Schubert, and A. Zimek.  Interpreting and unifying outlier scores.  In _Proceedings of the SDM_ , pages 13–24. SIAM, 2011.
  * Lai et al. (2021) K.-H. Lai, D. Zha, G. Wang, J. Xu, Y. Zhao, D. Kumar, Y. Chen, P. Zumkhawaka, M. Wan, D. Martinez, and X. Hu.  TODS: An automated time series outlier detection system.  In _Proceedings of the AAAI Conference_ , pages 16060–16062, 2021\.
  * Li et al. (2020) Y. Li, D. Zha, P. Venugopal, N. Zou, and X. Hu.  Pyodds: An end-to-end outlier detection system with automated machine learning.  In _Companion Proceedings of the Web Conference_ , pages 153–157, 2020.
  * Li et al. (2022) Z. Li, Y. Zhao, X. Hu, N. Botta, C. Ionescu, and G. Chen.  Ecod: Unsupervised outlier detection using empirical cumulative distribution functions.  _IEEE Transactions on Knowledge and Data Engineering_ , pages 1–1, 2022.  doi: 10.1109/TKDE.2022.3159580.
  * Ma et al. (2021) X. Ma, J. Wu, S. Xue, J. Yang, C. Zhou, Q. Z. Sheng, H. Xiong, and L. Akoglu.  A comprehensive survey on graph anomaly detection with deep learning.  _IEEE Transactions on Knowledge and Data Engineering_ , 2021.
  * Morris et al. (2020) C. Morris, N. M. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. Neumann.  Tudataset: A collection of benchmark datasets for learning with graphs.  In _Proceedings of the ICML Workshop on Graph Representation Learning and Beyond_ , pages 1–11, 2020.
  * Muhr et al. (2022) D. Muhr, M. Affenzeller, and B. Anthony D.  Outlierdetection.jl: A modular outlier detection ecosystem for the julia programming language.  2022\.
  * Paszke et al. (2019) A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  _Proceedings of the NeurIPS_ , 32, 2019.
  * Pedregosa et al. (2011) F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, et al.  Scikit-learn: Machine learning in python.  _Journal of Machine Learning Research_ , 12:2825–2830, 2011\.
  * Perini et al. (2020) L. Perini, V. Vercruyssen, and J. Davis.  Quantifying the confidence of anomaly detectors in their example-wise predictions.  In _Proceedings of ECML-PKDD_ , pages 227–243. Springer, 2020.
  * Sakurada and Yairi (2014) M. Sakurada and T. Yairi.  Anomaly detection using autoencoders with nonlinear dimensionality reduction.  In _Proceedings of the MLSDA workshop on machine learning for sensory data analysis_ , pages 4–11, 2014.
  * Sun et al. (2018) L. Sun, Y. Dou, C. Yang, J. Wang, P. S. Yu, L. He, and B. Li.  Adversarial attack and defense on graph data: A survey.  _arXiv preprint arXiv:1812.10528_ , 2018.
  * Virtanen et al. (2020) P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, et al.  Scipy 1.0: fundamental algorithms for scientific computing in python.  _Nature methods_ , 17(3):261–272, 2020.
  * Wang et al. (2021) X. Wang, B. Jin, Y. Du, P. Cui, Y. Tan, and Y. Yang.  One-class graph neural networks for anomaly detection in attributed networks.  _Neural computing and applications_ , 33(18):12073–12085, 2021.
  * Xu et al. (2022) Z. Xu, X. Huang, Y. Zhao, Y. Dong, and J. Li.  Contrastive attributed network anomaly detection with data augmentation.  In _Proceedings of the PAKDD_ , 2022.
  * Yuan et al. (2021) X. Yuan, N. Zhou, S. Yu, H. Huang, Z. Chen, and F. Xia.  Higher-order structure based anomaly detection on attributed networks.  In _Proceedings of the IEEE Big Data Conference_ , pages 2691–2700, 2021.
  * Zhao et al. (2019) Y. Zhao, Z. Nasrullah, and Z. Li.  PyOD: A python toolbox for scalable outlier detection.  _Journal of Machine Learning Research_ , 20(96):1–7, 2019.
  * Zhao et al. (2021a) Y. Zhao, G. H. Chen, and Z. Jia.  TOD: Tensor-based outlier detection.  _arXiv preprint arXiv:2110.14007_ , 2021a.
  * Zhao et al. (2021b) Y. Zhao, X. Hu, C. Cheng, C. Wang, C. Wan, W. Wang, J. Yang, H. Bai, Z. Li, C. Xiao, et al.  Suod: Accelerating large-scale unsupervised heterogeneous outlier detection.  pages 463–478, 2021b.
  * Zhao et al. (2021c) Y. Zhao, R. Rossi, and L. Akoglu.  Automatic unsupervised outlier model selection.  _Proceedings of the NeurIPS_ , 34:4489–4502, 2021c.
  * Zhou et al. (2021) S. Zhou, Q. Tan, Z. Xu, X. Huang, and F.-l. Chung.  Subtractive aggregation for attributed network anomaly detection.  In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_, pages 3672–3676, 2021.