# Detecting out-of-distribution text using topological features of
transformer-based language models

Andres Pollano  Department of Engineering and IT
University of Melbourne
Melbourne, Australia
<EMAIL_ADDRESS>Anupam Chaudhuri  Applied Artificial
Intelligence Institute
Deakin University
Geelong, Australia
<EMAIL_ADDRESS>Anj Simmons  Applied Artificial Intelligence
Institute
Deakin University
Geelong, Australia
<EMAIL_ADDRESS>
###### Abstract

We attempt to detect out-of-distribution (OOD) text samples though applying
Topological Data Analysis (TDA) to attention maps in transformer-based
language models. We evaluate our proposed TDA-based approach for out-of-
distribution detection on BERT, a transformer-based language model, and
compare the to a more traditional OOD approach based on BERT CLS embeddings.
We found that our TDA approach outperforms the CLS embedding approach at
distinguishing in-distribution data (politics and entertainment news articles
from HuffPost) from far out-of-domain samples (IMDB reviews), but its
effectiveness deteriorates with near out-of-domain (CNN/Dailymail) or same-
domain (business news articles from HuffPost) datasets.

##  I Introduction

Machine learning (ML) models perform well on the datasets they have been
trained on, but can behave unreliably when tested on data that is out-of-
distribution (OOD). For example, when a ML model has been trained to recognise
different breeds of cats is fed an image of a dog, the results are
unpredictable. OOD detection is the task of identifying that an input does not
seem to be drawn from the same distribution as the training data, and thus the
prediction given by the ML model should not be trusted. OOD detectors can be
used to defend ML models deployed in high stakes applications from OOD data by
providing a warning/error message for OOD inputs rather than processing the
input and producing untrustworthy results [1].

In this paper, we focus on OOD detection for textual inputs to safeguard ML
models that perform natural language processing (NLP) tasks. For example, a
sentiment classification model trained on formal restaurant reviews may not
produce valid results when applied to informal posts from social media.
Determining that an input is OOD requires a way to measure the distance
between an input and the in-distribution data. This in turn requires a method
to convert textual data into an embedding space in which we can measure
distance. One approach to this is to input the text to a transformer-based
language model, such as BERT [2], to extract an embedding vector for the input
text (e.g., the hidden representation of the special $[CLS]$ token). We can
then measure the distance of the embedding vector for an input text to the
nearest (or k-nearest) embedding vector of a text from an in-distribution
validation set. When this distance is beyond some threshold (which needs to be
calibrated for the application), the input text is flagged as out of
distribution.

The internal state of transformer-based language models contains important
information, which may be able to offer richer representations than only using
the embedding obtained from the last or penultimate layer. For example, Azaria
and Mitchell [3] demonstrated that it is possible to train a classifier on the
activation values of the hidden layers of large language models to predict
when they are generating false information rather than true information.
However, training a classifier for OOD detection in this manner is not a
suitable approach, as the distribution of the OOD data that will be
encountered is not knowable in advance. That is, due to the nature of OOD
detection, we need to extract an embedding vector and associated distance
metric (calibrated solely on the training/validation data) without training a
further classifier over this space.

Recently, Kushnareva et al. [4] proposed an approach to analyse the topology
of attention maps of transformer-based language models to determine when text
had been artificially generated, and Perez and Reinauer [5] propose using the
topology of attention maps of transformer-based language models to detect
adversarial textual attacks. Specifically, topological data analysis (TDA)
provides a way to extract high level features (related to the topology of the
attention maps for each attention head in each layer) that can serve as an
embedding vector of lower dimension than the full internal model state. In
this paper, we investigate the suitability of these topological embeddings for
the task of OOD detection, and contrast them to traditional approaches. We
have made the code111https://github.com/andrespollano/neural_nets-tda used to
generate our results public, with the intention of aiding the application of
TDA methods to transformer-based models.

##  II Background

###  II-A Topological Data Analysis

Topology deals with the properties of geometric objects that are invariant
under continuous deformation. For example, a donut and a coffee cup are
considered topologically the same object, and similarly, a point and a ball
are topologically similar. The branch of algebraic topology attaches algebraic
objects such as groups to these topological spaces, as mentioned in Hatcher’s
work [6]. This forms an identification or features of the topological space.

Now using the idea of persistence; we can extend the topology to the finite
data sets. The current from of persistence tools can be traced back to [7, 8].
Homology groups form the essential invariants for a Topological object. Hence
persistence homology groups form the invariant for finite discrete objects.

####  II-A1 Simplicial complex and Simplicial Chain

In mathematics, it is a common practice to study simple objects that can be
visualized or computed and then approximate complex objects in relation to the
known or studied objects. Therefore, we introduce the concept of a simplicial
complex, which facilitates the computational aspects of algebraic topology.

Given a set $X=\\{x_{0},\ldots,x_{k}\\}\subset\mathbb{R}^{d}$ of $k+1$
affinely independent points, the $k$-dimensional simplex
$\sigma=[x_{0},\ldots,x_{k}]$ spanned by $X$ is the convex hull of $X$. The
points of $X$ are called the vertices of $\sigma$, and the simplices spanned
by the subsets of $X$ are called the faces of $\sigma$. A geometric simplicial
complex $K$ in $\mathbb{R}^{d}$ is a collection of simplices such that:

  1. 1.

Any face of a simplex of $K$ is a simplex of $K$,

  2. 2.

The intersection of any two simplices of $K$ is either empty or a common face
of both.

Let’s begin with an example of a geometrical simplex

$\displaystyle\text{Let }K$
$\displaystyle=\\{\left[a\right],\left[b\right],\left[c\right],$
$\displaystyle\quad\left[a,b\right],\left[b,c\right],\left[a,c\right],\left[a,b,c\right]\\}.$

The above is a simplicial complex of dimension two as the highest simplex
$\left[a,b,c\right]$ is of dimension two.

For each dimension $k$, there is a chain group $C_{k}$ associated with the
$k$-dimensional simplices. The chain group is the free abelian group generated
by the $k$-dimensional simplices of the simplicial complex.

Valid 1-simplex for $K$ which is an element of the chain group $C_{1}$ is
given by

  * •

$\left[a,b\right]$

  * •

$\left[a,b\right]+\left[a,c\right]$

  * •

and any other similar combination of 1-dimensional simplex.

Boundary homomorphism Let $\sigma=\left\\{v_{0},\dots,v_{p}\right\\}$ be a
simplicial complex of dimension $p$. We define a boundary homomorphism
$\partial\sigma=\sum_{i}v_{0},\dots,\hat{v_{i}},\dots,v_{p}$ where
$\hat{v_{i}}$ denote it has been eliminated from the set. Hence we get a map
from $\partial_{p}:C_{p}\to C_{p-1}$. Let’s take a particular example

$\displaystyle\partial_{2}\\{a,b,c\\}$
$\displaystyle=\\{b,c\\}+\\{a,c\\}+\\{a,b\\}$ (1)
$\displaystyle\partial_{1}(\\{b,c\\}+\\{a,c\\}+\\{a,b\\})$
$\displaystyle=\\{c\\}+\\{b\\}+\\{c\\}+\\{a\\}+\\{b\\}+\\{a\\}$ (2)
$\displaystyle=0\quad\text{if we calculate in $\mathbb{Z}_{2}$}$ (3)

Chain Complex

A $k$ dimensional simplex forms a vector space, which we denote as $C_{k}$

$\displaystyle 0\rightarrow
C_{n}\xrightarrow{\partial_{n+1}}C_{n-1}\xrightarrow{\partial_{n}}\cdots\rightarrow
C_{1}\xrightarrow{\partial_{2}}C_{0}\xrightarrow{\partial_{1}}0$

Diagram

Kernel vs image

$\displaystyle f:$ $\displaystyle A\rightarrow B$ $\displaystyle\text{ker }f$
$\displaystyle=\\{a\in A\mid f(a)=0\\}$ $\displaystyle\text{im }f$
$\displaystyle=\\{f(a)\mid a\in A\\}\subseteq B$

Cycle and boundary groups

$\displaystyle\text{Cycle group }Z_{p}$ $\displaystyle=\text{ker
}\partial_{p}$ $\displaystyle\text{Boundary group }B_{p}$
$\displaystyle=\text{im }\partial_{p+1}$

$B_{p}\subset Z_{p}$

######  Definition 1.

Simplicial homology group and Betti numbers the $k^{\text{th}}$ (simplicial)
homology group of $K$ is the quotient vector space

$H_{k}(K)=\frac{Z_{k}(K)}{B_{k}(K)}.$

The $k^{\text{th}}$ Betti number of $K$ is the dimension $\beta_{k}(K)=\dim
H_{k}(K)$ of the vector space $H_{k}(K)$.

Hence given a simplicial complex we can compute the Homology group. Now given
a finite set of data points $X$:

$X=\\{p_{1},p_{2},\ldots,p_{m}\\}$

and a matrix that gives the distance of the points (or equivalently if the
points are embedded in a metric space and a metric dist such as the Euclidean
distance), pick a threshold $\varepsilon$:

$\mathcal{V}_{\varepsilon}(X):=\\{\sigma\subset X|\forall
u,v\in\sigma,\text{dist}(u,v)\leq\varepsilon\\}$

$\mathcal{V}_{\varepsilon}(X)$ is known as Vietoris Rips complex. Given
$\varepsilon_{1}$ and $\varepsilon_{2}$ such that
$\varepsilon_{1}\leq\varepsilon_{2}$ then

$\mathcal{V}_{\varepsilon_{1}(X)}\subseteq\mathcal{V}_{\varepsilon_{2}}(X)$

######  Definition 2.

Filtration
Given a set or space $X$, a _filtration_ $\mathcal{F}$ of $X$ is a sequence of
subspaces or subsets:

$X_{0}\subseteq X_{1}\subseteq X_{2}\subseteq\dots\subseteq X_{n}=X$

Each $X_{i}$ is referred to as the $i$-th filtration level or step of the
filtration.

So as we vary $\varepsilon$ we get a filtration of Vietoris Rips complex. So
in general for a topological space $X$ given a filtration of $X$

$K_{i}\subseteq K_{j}\subseteq X$

$f^{i,j}_{p}:H_{p}(K_{i})\xrightarrow{H}_{p}(K_{j})$

$0\to
H_{p}(K_{0})\xrightarrow{f^{0,1}_{p}}H_{p}(K_{1})\xrightarrow{f^{1,2}_{p}}\dots\xrightarrow{f^{n-2,n-1}_{p}}H_{p}(K_{n-1})\xrightarrow{f^{n-1,n}_{p}}H_{p}(K_{n})\to
H_{p}(X)$

The Persistence homology group is then computed by

$H_{p}^{i,j}=\frac{Z_{p}(K_{i})}{B_{p}(K_{j})\cap Z_{p}(K_{i})}$

So particular to our context for a monotonic sequence of $\varepsilon_{i}$.

$\varepsilon_{1}\leq\varepsilon_{2},\ldots,\leq\varepsilon_{i}\ldots\leq\varepsilon_{j}\ldots$

we get an filtration

$\mathcal{V}_{\varepsilon_{1}(X)}\subseteq\mathcal{V}_{\varepsilon_{2}}(X)\ldots\mathcal{V}_{\varepsilon_{i}(X)}\ldots\subseteq\mathcal{V}_{\varepsilon_{j}}(X)$

As it’s clear we are working in topological space $X$ we will denote
$\varepsilon_{i}(X)$, by $\varepsilon_{i}$.

$H_{k}(\iota_{i,j}):H_{k}(V_{\varepsilon_{i}})\to H_{k}(V_{\varepsilon_{j}})$

A homology class $\alpha\in H_{k}(V_{\varepsilon_{i}})$ is said to be born at
$V_{\varepsilon_{i}}$ if $\alpha\notin H^{i-1,i}_{k}$, i.e., if it is not in
the image of $H_{k}(\iota_{i-1,i})$.

If $\alpha$ is born at $V_{\varepsilon_{i}}$, it is said to die at
$V_{\varepsilon_{j}}$ if $H_{k}(\iota_{i,j-1})(\alpha)\notin H^{i-1,j-1}_{k}$
and $H^{k}(\iota_{i,j})(\alpha)\in H^{i-1,j}_{k}$.

The persistence of $\alpha$ is given by $\varepsilon_{j}-\varepsilon_{i}$ and
set to infinity if it never dies.

The persistent Betti-numbers, defined by
$\beta_{i,j}^{k}:=\text{dim}H^{i,j}_{k}$, carry information on how the
homology (and thus the topology) changes across the filtration.

###  II-B BERT Model

BERT [2] is a transformer-based language model that has been pre-trained on a
large corpus of text from BooksCorpus and English Wikipedia. Input text first
needs to be tokenized, in which each word is converted to one or more tokens.
The first token is the special $[CLS]$ token, followed by the tokenization of
each word, using the special $[SEP]$ token to separate “sentences” (e.g.,
question and answer, these don’t necessarily correspond to linguistic
sentences). BERT is trained to achieve two objectives: Masked Language
Modelling (MLM) in which tokens are masked at random (replaced with the
special $[MASK]$ token) and the language model needs to learn to fill these
in; and Next Sentence Prediction (NSP) in which the final hidden vector of the
special $[CLS]$ token is used to predict if two sentences follow each other in
the corpus.

As a transformer-based model, BERT consists of multiple layers, each with
multiple attention heads. While multiple variants of BERT are available, for
the purpose of this paper we use $BERT_{BASE}$, which consists of 12 layers,
each with 12 attention heads (i.e., 144 attention heads in total) that operate
on an input matrix, $X$, of $n$ tokens and 768 hidden dimensions, $d$.

####  II-B1 Sentence Embeddings

The final hidden vector of the special $[CLS]$ token can be used to embed the
input sequence (which varies in length) in $d$ hidden dimensions (178 in the
case of $BERT_{BASE}$). The authors of the BERT paper [2] note that the
$[CLS]$ embedding is not a meaningful sentence representation without fine-
tuning. Nevertheless, Uppaal et al. [9] claim that the practice of using this
to obtain sentence embeddings “is standard for most BERT-like models”, and
find that in the case of RoBERTa (a BERT-like model without the NSP training
objective) this embedding serves as a “near perfect” OOD detector even without
fine-tuning.

####  II-B2 Attention Maps

Each attention head computes an attention map, $W^{attn}$, of shape $n\times
n$ as an intermediate step of the calculation. We use the same definition of
attention maps as Kushnareva et al. [4] presented below:

$\displaystyle X^{out}$ $\displaystyle=W^{attn}(XW^{V})$ $\displaystyle
W^{attn}$
$\displaystyle=\text{softmax}\left(\frac{(XW^{Q})(XW^{K})^{T}}{\sqrt{d}}\right)$

Where $W^{Q}$, $W^{K}$, $W^{V}$ are learned projection matrices of shape
$d\times d$ and $X^{out}$ is the output of the attention head applied to the
$n\times d$ matrix $X$ from the previous layer. In this paper, we analyse the
attention maps for each of the 144 attention heads in $BERT_{BASE}$ using TDA.

##  III Experiment design

In this section, we outline the design of our methodology for our OOD
detection using Topological Data Analysis. For a supervised classification
task, given a test sample $x$, OOD detection aims to determine whether it
belongs to the in-distribution (ID) dataset $x\in\mathcal{D}_{in}$ or not.

We consider a $d$-dimensional representation of an input text $x$ as $h(x)$ in
$\mathbb{R}^{d}$. To analyse the benefits of TDA in OOD detection, we consider
two encoding functions $h_{1}(x)$ and $h_{2}(x)$:

  1. 1.

Topological feature vector $h_{1}(x)$: given $x$, we generate a vector of
$d_{1}$ topological features using the graph representations of the 144
attention maps generated by $BERT_{BASE}$. In subsection III-C and subsection
III-D, we explain in detail how the topological features are generated from an
input sentence.

  2. 2.

Sentence embedding $h_{2}(x)$: we take the $d_{2}$-dimensional text embedding
of the $[CLS]$ token output by $BERT_{BASE}$, which captures the contextual
and semantic information of the input text $x$.

Similar to Uppaal, et al. 2023 [9], we define the OOD detection function as
$G(x)$, which maps an instance $x$ to $\\{in,out\\}$ as follows:

$G_{\lambda}(x;h)=\begin{cases}in&\text{if }S(x;h)\geq\lambda\\\ out&\text{if
}S(x;h)<\lambda\end{cases}$

where $S(x;h)$ is an OOD scoring function using a distance-based method
(Mahalanobis distance to the ID class centroids or Euclidean distance to
k-nearest ID neighbour), described in subsection III-E, and $\lambda$ is the
threshold chosen so that a high proportion of ID samples’ scores are above
$\lambda$.

###  III-A Data

As the in-distribution dataset, we choose the headlines and abstract text of
‘Politics’ and ‘Entertainment’ news articles from HuffPost from the news-
category dataset (Misra, 2022) [10]. To test the robustness of the OOD method,
we conduct experiments on three kinds of dataset distribution shifts (Arora et
al. 2021) [11]:

  * •

Near Out-of-Domain shift. In this paradigm, ID and OOD samples come from
different distributions (datasets) exhibiting semantic similarities. In our
experiments, we evaluate the abstract of news articles from the cnn-dailymail
dataset (See, et al. 2017) [12].

  * •

Far Out-of-Domain shift. In this type of shift, the OOD samples come from a
different domain and exhibit significant semantic differences. In particular,
we evaluate the IMDB dataset (Maas et al. 2013) [13] as OOD samples.

  * •

Same-Domain shift. We also test a more challenging setting, where ID and OOD
samples are drawn from the same domain, but with different labels.
Specifically, we extract the ‘Business’ news articles from the news-category
dataset.

###  III-B Model

We focus on the attention heads of a pre-trained $BERT_{BASE}$ (L=12, H=12)
generated from an input text $x$ to produce topological features and compare
this encoding to the embeddings of the $[CLS]$ token as the sentence
representation. We replicate our experiments on a fine-tuned $BERT_{BASE}$ on
the ID news categorisation task
$\mathcal{X}\rightarrow{\\{\text{'Politics'},\text{'Entertainment'}\\}}$. We
fine-tune the model for 3 epochs, using Adam with batch size of 32 and
learning rate $10^{-5}$.

###  III-C Attention Maps and Attention Graphs

(a) Attention maps $\left(12\times 12\right)$ derived from pre-trained BERT
for the input text "President issues vows as tensions with China rise"

(b) BERT Attention Map
(Layer 7; Head 10)

(c) Undirected attention graph (Layer 7; Head 10) where edges are proportional
to the maximal attention between the two vertices. The edge width reprsetns
shorter distances(attention strength)

Figure 1: Process of transforming an attention map to an attention graph (one
per attention head)

Attention maps play a crucial role in our methodology as they form the basis
for extracting topological features used in our OOD detection. An attention
map $W^{attn}$ is a $n\times n$-dimensional matrix where each entry represents
the attention weight between two tokens. Each element $w_{ij}^{attn}$ can be
interpreted as the level of ‘attention’ token $i$ pays to token $j$ in the
input sequence during the encoding process. The higher the weight the stronger
the relation between two tokens. They are non-negative and the attention
weights of a token sum up to one (i.e. $\sum_{j=1}^{n}w_{ij}^{attn}=1$ for all
$i=1,...,n$.).

To generate topological features from an attention map, we first convert it
into an attention graph following the approach of Perez and Reinauer (2022)
[5]. Given an attention matrix $W^{attn}$, we create an undirected weighted
graph where the vertices represent the tokens of the input text $x$, and the
weights are determined by the attention weights in the corresponding attention
map. To emphasise the important relationships and reduce noise, we calculate
the distance between vertices as $1-\max(w^{ij},w^{ji})$. The distance
calculation reflects the inverse of the maximum attention weight between two
tokens, ensuring the relationship is symmetric and the strong relationships
result in smaller distances. To prevent the formation of self-loops, all
diagonals in the adjacency matrix are set to 0. Figure 1 shows an example of
constructing the attention graph for an attention map.

###  III-D Persistent Homology

Figure 2: Filtration process for the attention graph (Layer 7; Head 10) where
edges with shorter distances below a threshold are added first, gradually
connection the nodes until a complete graph is formed

The constructed attention graphs from the attention heads contain the
structure and relationships we need to extract topological features. To encode
the topological information provided by the attention graph, we use a
filtration process to generate a persistence diagram. Filtration in TDA is a
systematic process where a topological space is progressively constructed
across varying scales to analyse the emergence, persistence and disappearance
of simplicial complexes, such as connected components, holes, or voids.

We apply one of the most widely used types of filtration process to the
attention graphs, the Vietoris-Rips filtration. This process starts with only
the vertices of the graph, considering them as zero-dimensional simplices.
Then it adds edges one by one, depending on their weights (i.e. distances).
Edges with shorter distances below a threshold are added first, gradually
connecting the vertices by increasing the threshold until a complete graph is
formed. As edges are added, the filtration process captures the graph’s
properties and the relationships between its vertices [14]. This process is
visualised in fig. 2.

To construct a persistence diagram, we keep track of the lifetime of
persistence features as the threshold is increased. One can think of
0-dimensional persistent features as connected components, 1-dimensional
features as holes and 2-dimensional features as voids (2-dimensional holes)
and so on. The birth and death time of a persistence feature is the threshold
value at which the feature appeared and disappeared. For example, when the
threshold is 0 all 0-dimensional features are born (vertices), and when two
vertices $i$ and $j$ are connected at threshold $w^{ij}$, one 0-dimensional
feature will disappear. Similarly, a 1-dimensional feature (hole) will appear
at the threshold where 3 vertices connect to each other, and disappear when a
fourth vertex forms a 2-dimensional simplex (void). The birth and death of all
$k$-dimensional simplices are recorded in a persistence diagram. An example
persistence diagram is shown in fig. 3(a).

(a) Persistence diagram generated from the filtration process for attention
map in Layer 7, Head 10. The set of $H_{0}$ (red points) represents the birth
and death of ‘connected components’ and the set of $H_{1}$ (teal points)
represents the birth and death of ‘holes’.

(b) Topological features extracted from the persistence diagram, calculating
persistence entropy, and amplitude with ‘Bottleneck’ and ‘Wassertstein’
distances for homology dimensions 0, 1, 2 and 3. (In the case of NaN values,
e.g. due to no higher dimensional simplices, we set the persistence entropy
feature to -1, as per the default behaviour of Giotto-tda)

Figure 3: Example persistence diagram and extracted topological features

From the persistence diagrams, we extract various topological features to
represent the underlying graph’s structure. In our experiments, we focus on
the following topological features:

  1. 1.

Persistence Entropy: This feature quantifies the complexity of the persistence
diagram as calculated by the Shannon entropy of the persistence values (birth
and death), with higher entropy indicating a more complex topology.

  2. 2.

Amplitude: We compute amplitude using two different distance measures:
‘bottleneck’ and ‘Wasserstein’. The amplitude measures the maximum persistence
value within the diagram, providing insights into the significance of the
topological features.

We focus on different homology dimensions to capture topological features of
varying complexities. In our experiments, we consider homology dimensions [0,
1, 2, 3] to account for different aspects of the attention graph’s topology.
We use the Giotto-tda library to generate the persistence diagrams and extract
the topological features, as per fig. 3(b).

###  III-E OOD Scoring Function

Similar to Perez and Reinauer (2022) [5], given $h(x)$, a $d$-dimensional
representation of an input text $x$, we employ two distance-based methods as
the OOD scoring functions:

  1. 1.

Mahalanobis distance to the ID class centroids: the Mahalanobis distance is
used to measure the distance between the feature vector $h(x)$ and the class
centroids. This distance is based on the covariance matrix of the class
features, which is based on the assumption that the data in that class follows
a multivariate Gaussian distribution. The OOD score is calculated as follows:

$S_{\text{Maha}}(x;h;\Sigma;\mu)=min_{c\in
y}(z_{x}-\mu_{c})^{T}\Sigma^{-1}(z_{x}-\mu_{c})$

where $z_{x}$ is the standardised feature vector for the input $h(x)$,
$\Sigma$ is the covariance matrix of the standardised ID feature vectors and
$\mu$ is the set of class mean standardised embeddings. Both $\Sigma$ and
$\mu_{c}$ are extracted from the ID validation set embeddings to account for
the inherent distribution of the ID data. The covariance matrix $\Sigma$
captures how the features vary with respect to one another, and $\mu_{c}$
represents the centroid or average representation of data belonging to class
$c$.

  2. 2.

Euclidean distance to k-nearest ID neighbour: We measure the distance between
$h(x)$ and the k-nearest ID neighbour’s feature vector from the validation
set. Given $h(x)$ and a set of $m$ ID feature vectors
$\\{h(x_{1}),h(x_{2}),...,h(x_{m})\\}$, the Euclidean distance to the
k-nearest ID neighbour is calculated as follows:

$S_{\text{KNN}}(x;h)=||z_{x}-z_{x_{k}}||_{2}$

where $z_{x}$ and $z_{x_{k}}$ are the standardised feature vector for the
input $h(x)$ and its k-nearest ID sample $h(x_{k})$. In our experiments, we
set $k=5$.

To classify an instance as OOD, we set a threshold $\lambda$ at which 95% of
the test ID samples are correctly classified as ID. For both scoring
functions, the feature vectors of a sample $h(x)$ are standardised (i.e. zero-
mean and unit variance) based on the mean and standard deviation of the ID
validation set feature vectors.

###  III-F Evaluation Metrics

To evaluate the OOD detector, we report:

  * •

FPR95, which measures the false positive rate (% of OOD samples classified as
ID), while ensuring that the true negative rate (% of ID samples classified as
ID) remains at 95%. Lower FPR95 values indicate better performance of the OOD
detector.

  * •

AUROC plots the true positive rate against the false positive rate at various
threshold values. Higher AUROC values indicate better discrimination between
ID and OOD samples.

##  IV Results

We conduct our experiments using Topological Data Analysis to generate
topological feature vectors $h_{1}(x)$ from attention maps, which are then
compared to standard sentence embeddings $h_{2}(x)$ generated from the $[CLS]$
token of BERT. Table I shows the OOD detection performance of both approaches
for three out-of-distribution datasets, using both pre-trained and fine-tuned
BERT models.

|  | Pre-trained model | Fine-tuned model
---|---|---|---
|  | KNN | MAHA | KNN | MAHA
|  | AUROC $\uparrow$ | FPR95 $\downarrow$ | AUROC $\uparrow$ | FPR95 $\downarrow$ | AUROC $\uparrow$ | FPR95 $\downarrow$ | AUROC $\uparrow$ | FPR95 $\downarrow$
IMDB | TDA | 0.940 | 0.090 | 0.940 | 0.112 | 0.958 | 0.084 | 0.950 | 0.124
CLS | 0.680 | 0.875 | 0.799 | 0.704 | 0.771 | 0.916 | 0.814 | 0.852
CNN/Dailymail | TDA | 0.572 | 0.890 | 0.563 | 0.908 | 0.551 | 0.909 | 0.521 | 0.927
CLS | 0.875 | 0.591 | 0.897 | 0.445 | 0.947 | 0.215 | 0.949 | 0.208
news-category (Business) | TDA | 0.527 | 0.929 | 0.543 | 0.921 | 0.570 | 0.923 | 0.568 | 0.925
CLS | 0.580 | 0.921 | 0.638 | 0.878 | 0.884 | 0.431 | 0.885 | 0.424
Table I: Comparison of the performance of our scoring functions on all three
out-of-distribution datasets using both pre-trained and fine-tuned models.

For visualisation purposes, we use UMAP projections of the in-distribution
(validation and test sets) and out-of-distribution data points in the
corresponding feature space. Figures 4, 5 and 6 show the data representations
from the TDA and CLS approaches for the far out-of-domain dataset (IMDB), near
out-of-domain dataset (CNN/Dailymail) and the same-domain dataset (business
news-category), respectively.

| Pre-trained | Fine-tuned
---|---|---
TDA |  |
CLS |  |
Figure 4: IMDB | Pre-trained | Fine-tuned
---|---|---
TDA |  |
CLS |  |
Figure 5: CNN/Dailymail | Pre-trained | Fine-tuned
---|---|---
TDA |  |
CLS |  |
Figure 6: News-Categories (Business)

The results demonstrate that the TDA-based approach consistently outperforms
the CLS embeddings in detecting OOD samples in the IMDB dataset from both the
pre-trained and fine-tuned models. OOD detection using TDA can detect IMDB
review samples with 8-9% FPR95, in stark contrast to the 87-91% FPR95
exhibited by CLS embeddings. As seen in fig. 4, the TDA feature vectors
project the data into well-separated and compact clusters, which explains its
superior performance.

The TDA approach was less effective than the CLS approach at detecting OOD
samples from the near out-of-domain CNN/Dailymail dataset. Even though the
data visualisation in fig. 5 shows that TDA was able to cluster OOD samples
together, the cluster was not distant enough from ID samples, rendering both
distance-based OOD detection methods less effective.

For same-domain datasets (news-category), both approaches struggled to detect
OOD samples. As seen in fig. 6, when both ID and OOD data are from the same
domain, their feature vectors are highly overlapping, although fine-tuning
seems to provide stronger separability between ID and OOD data for the CLS
approach.

##  V Discussion

From our experiments, we showed that the TDA approach outperforms the CLS
approach at detecting far out-of-domain OOD samples like those in the IMDB
dataset. Yet, its effectiveness deteriorates with near out-of-domain
(CNN/Dailymail) or same-domain (business news-category) datasets. To
understand why, we looked at the samples that each approach thrived and
struggled with, and we highlight three observations:

(1) The TDA approach accentuates features associated with textual flow or
grammatical structures rather than lexical semantics, consistent the findings
of Deng, F and Duzhin, F (2022) [15] and Kushnareva, L et al. (2021) [4]. For
example, TDA was adept at identifying OOD samples that are structurally unique
in the IMDB dataset, as the most confident OOD samples detected were:

  * •

‘OK…i have seen just about everything….and some are considered classics that
shouldn’t be ( like all those Halloween movies that suck crap or even Steven
king junk)…….and some are considered just OK that are really great…..( like
carnival of souls )……..and then some are just plain ignored…………like ( evil ed
) […]’

  * •

‘Time line of the film: * Laugh * Laugh * Laugh * Smirk * Smirk * Yawn * Look
at watch * walk out * remember funny parts at the beginning * smirk < br / >
<br /> […]’

In contrast, TDA struggled with detecting CNN/Dailymail OOD samples as they
have similar sentence structures and length to the ID samples, even if they
are semantically unrelated. Table II shows the samples with the least
confident OOD score from the CNN/Dailymail dataset, and their nearest ID
neighbour.

CNN/Dailymail sample |  Nearest ID neighbour
---|---
Footage showed an unusual ’apocalyptic’ dust storm hitting Belarus. China has suffered four massive sandstorms since the start of the year. Half of dust in atmosphere today is due to human activity, said Nasa. |  Trump’s Proposed Cuts To Foreign Food Aid Are Proving Unpopular. The president might see zeroed-out funding for foreign food aid as "putting America first," but members of Congress clearly disagree.
Video posted by YouTube user Richard Stewart showing a Porsche Cayman flying out of control. Police cited unidentified driver for the crash. Car reportedly wrecked and needed to be towed from the scene. |  Trump Signs Larry Nassar-Inspired Sexual Assault Bill Behind Closed Doors. The president quietly signed the bill the week after two White House staffers resigned amid allegations of domestic violence.
Table II: Least confident OOD samples from the CNN/Dailymail dataset and their
nearest ID neighbours, from the TDA approach using the pre-trained BERT model

(2) CLS embeddings are sensitive to the semantic and contextual meaning of the
samples, regardless of sentence structure. This explains why this approach
struggled with OOD detection from IMDB reviews, as it often classified IMDB
movie reviews as in-distribution due to their semantic similarities with the
entertainment news articles from the ID dataset, especially those related to
movies. A closer look at the IMDB samples with smallest OOD score from the CLS
embeddings in table III exemplifies this insight, identifying ID samples of
similar topic as nearest neighbours even though they are clearly from
different domains.

IMDB review sample |  Nearest ID neighbour
---|---
’[…] I would spend good, hard-earned cash money to see it again on DVD. And as long as we’re requesting Smart Series That Never Got a Chance…How about DVD releases of Maximum Bob (another well written, odd duck show with a delightful cast of characters.) […]’ |  DVDs: Great Blimp, Badlands, Buster Keaton & More. Let’s catch up with some reissues of classic – and not so classic – movies, with a few documentaries tossed in at the end for good measure.
’[…] I am generally not a fan of Zeta-Jones but even I must admit that Kate is STUNNING in this movie. […]’ |  How ‘Erin Brockovich’ Became One Of The Most Rewatchable Movies Ever Made. Julia Roberts gives the best performance of her career, aided by a sassy Susannah Grant script full of one-liners.
Table III: Least confident OOD samples from the IMDB dataset and their nearest
ID neighbours, from the CLS approach using the pre-trained BERT model

(3) Fine-tuning has improved performance of CLS embeddings for near or same-
domain shifts, but shows no significant benefit for TDA. Fine-tuning induces a
model to divide a single domain cluster into class clusters, as highlighted by
Uppaal et al. (2023) [9]. For CNN/Dailymail and Business news OOD datasets,
this is beneficial for the CLS approach as it learns to better distinguish
topics. However, fine-tuning made the CLS embeddings of IMDB movie reviews
appear even more similar to entertainment news, deteriorating OOD performance.

For the TDA approach, fine-tuning did not present any considerable benefits.
This can be partly attributed to observation (1) that TDA primarily captures
structural differences, and fine-tuning, which is driven by semantics, does
not significantly alter the topological representation.

##  VI Conclusion

In this paper, we explore the capabilities of Topological Data Analysis for
identifying Out-of-Distribution samples by leveraging the attention maps
derived from BERT, a transformer-based Large Language Model. Our results
demonstrate the potential of TDA as an effective tool to capture the
structural information of textual data.

Nevertheless, our experiments also highlighted the intrinsic limitations of
TDA-based methods. Predominantly, our TDA method captured the inter-word
relations derived from the attention maps, but failed to account for the
actual lexical meaning of the text. This distinction suggests that while TDA
offers valuable insights into textual structure, a lexical and more holistic
understanding of textual data is needed for OOD detection, especially with
near or same-domain shifts.

For future work, it might be worth combining the topological features that
capture the structural information of textual data, with those that encode the
semantics of text in an ensemble model that might boost our ability to detect
OOD samples. In addition, there is an opportunity to investigate the
effectiveness of TDA in other NLP tasks where the textual structure might be
important, such as authorship attribution, document classification or
sentiment analysis.

## Acknowledgement

The research was supported by a National Intelligence Postdoctoral Grant
(NIPG-2021-006).

## References

  * Wong et al. [2023] S. Wong, S. Barnett, J. Rivera-Villicana, A. Simmons, H. Abdelkader, J.-G. Schneider, and R. Vasa, “Mlguard: Defend your machine learning model!” 2023. [Online]. Available: https://arxiv.org/abs/2309.01379
  * Devlin et al. [2019] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “BERT: Pre-training of deep bidirectional transformers for language understanding,” 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)_ , Jun. 2019, pp. 4171–4186. [Online]. Available: https://aclanthology.org/N19-1423
  * Azaria and Mitchell [2023] A. Azaria and T. Mitchell, “The internal state of an llm knows when its lying,” 2023. [Online]. Available: https://arxiv.org/abs/2304.13734
  * Kushnareva et al. [2021] L. Kushnareva, D. Cherniavskii, V. Mikhailov, E. Artemova, S. Barannikov, A. Bernstein, I. Piontkovskaya, D. Piontkovski, and E. Burnaev, “Artificial text detection via examining the topology of attention maps,” in _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_. Online and Punta Cana, Dominican Republic: Association for Computational Linguistics, Nov. 2021, pp. 635–649. [Online]. Available: https://aclanthology.org/2021.emnlp-main.50
  * Perez and Reinauer [2022] I. Perez and R. Reinauer, “The topological bert: Transforming attention into topology for natural language processing,” 2022. [Online]. Available: https://arxiv.org/abs/2206.15195
  * Hatcher [2002] A. Hatcher, _Algebraic Topology_. Cambridge University Press, 2002. [Online]. Available: https://pi.math.cornell.edu/~hatcher/AT/ATpage.html
  * Frosini [1992] P. Frosini, “Measuring shapes by size functions,” in _Intelligent Robots and Computer Vision X: Algorithms and Techniques_ , vol. 1607. SPIE, 1992, pp. 122–133. [Online]. Available: https://doi.org/10.1117/12.57059
  * Robins [1999] V. Robins, “Towards computing homology from finite approximations,” in _Topology proceedings_ , vol. 24, no. 1, 1999, pp. 503–532.
  * Uppaal et al. [2023] R. Uppaal, J. Hu, and Y. Li, “Is fine-tuning needed? pre-trained language models are near perfect for out-of-domain detection,” in _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , Jul. 2023, pp. 12 813–12 832. [Online]. Available: https://aclanthology.org/2023.acl-long.717
  * Misra [2022] R. Misra, “News category dataset,” 2022. [Online]. Available: https://arxiv.org/abs/2209.11429
  * Arora et al. [2021] U. Arora, W. Huang, and H. He, “Types of out-of-distribution texts and how to detect them,” in _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , Nov. 2021, pp. 10 687–10 701. [Online]. Available: https://aclanthology.org/2021.emnlp-main.835
  * See et al. [2017] A. See, P. J. Liu, and C. D. Manning, “Get to the point: Summarization with pointer-generator networks,” in _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , Jul. 2017, pp. 1073–1083. [Online]. Available: https://www.aclweb.org/anthology/P17-1099
  * Maas et al. [2011] A. L. Maas, R. E. Daly, P. T. Pham, D. Huang, A. Y. Ng, and C. Potts, “Learning word vectors for sentiment analysis,” in _Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies_ , June 2011, pp. 142–150. [Online]. Available: http://www.aclweb.org/anthology/P11-1015
  * Bauer [2021] U. Bauer, “Ripser: efficient computation of vietoris–rips persistence barcodes,” _Journal of Applied and Computational Topology_ , vol. 5, pp. 391–423, 2021. [Online]. Available: https://doi.org/10.1007/s41468-021-00071-5
  * Deng and Duzhin [2022] R. Deng and F. Duzhin, “Topological data analysis helps to improve accuracy of deep learning models for fake news detection trained on very small training sets,” _Big Data Cogn. Comput._ , vol. 6, no. 3, p. 74, 2022. [Online]. Available: https://doi.org/10.3390/bdcc6030074


Department of Mathematics, University of California Los<EMAIL_ADDRESS>Department of Computer Science, Portland State<EMAIL_ADDRESS>
Theory of computation Design and analysis of algorithms Theory of computation
Quantum computation theory

# Simple vertex coloring algorithms

Jackson Morris  Fang Song

###### Abstract

Given a graph $G$ with $n$ vertices and maximum degree $\Delta$, it is known
that $G$ admits a vertex coloring with $\Delta+1$ colors such that no edge of
$G$ is monochromatic. This can be seen constructively by a simple greedy
algorithm, which runs in time $O(n\Delta)$. Very recently, a sequence of
results (e.g., [Assadi et. al. SODA’19, Bera et. al. ICALP’20, AlonAssadi
Approx/Random’20]) show randomized algorithms for
$(\epsilon+1)\Delta$-coloring in the query model making $\tilde{O}(n\sqrt{n})$
queries, improving over the greedy strategy on dense graphs. In addition, a
lower bound of $\Omega(n\sqrt{n})$ for any $O(\Delta)$-coloring is established
on general graphs.

In this work, we give a simple algorithm for $(1+\epsilon)\Delta$-coloring.
This algorithm makes $O(\epsilon^{-1/2}n\sqrt{n})$ queries, which matches the
best existing algorithms as well as the classical lower bound for sufficiently
large $\epsilon$. Additionally, it can be readily adapted to a quantum query
algorithm making $\tilde{O}(\epsilon^{-1}n^{4/3})$ queries, bypassing the
classical lower bound.

Complementary to these algorithmic results, we show a quantum lower bound of
$\Omega(n)$ for $O(\Delta)$-coloring.

###### keywords:

graph coloring, quantum algorithms, query model

##  1 Introduction

Graph coloring is a fundamental problems in discrete algorithms and graph
theory. It has wide applications in scheduling, resource allocation, compiler
optimization, and logistics settings. In this problem, one aims to assign
every vertex a color such that no edge is _monochromatic_ , i.e., both
endpoints having the same color. Finding such a valid coloring with $k\geq 1$
colors is usually called the $k$-coloring problem. A critical graph parameter
$\chi(G)$ is the minimum number of colors necessary to guarantee a valid
coloring. In Karp’s renowned result, 3-coloring as well as deciding $\chi(G)$
in general are proven NP-complete [12]. On the other hand, it is known that
for any graph $G$, $\chi(G)\leq\Delta+1$ where $\Delta$ is the maximum degree
of $G$. This follows from a simple greedy algorithm for $\Delta+1$-coloring.
The basic observation is that any valid partial $\Delta+1$-coloring of $G$ can
be extended to a complete $\Delta+1$-coloring. This is because every vertex
has at most $\Delta$ neighbors, there must be at least one choice of color for
that vertex that does not conflict with any of its neighbors.

For quite some time, the $O(n\Delta)$ greedy algorithm is the best known
algorithm for $\Delta+1$ vertex coloring on general graphs. Very recently,
authors of [2] give a new $\tilde{O}(n\sqrt{n})$ algorithm in the _query_
model, where the graph’s adjacency matrix is given as a black-box. This
algorithm relies on a tool called palette sparsification, in which a small
number of colors are sampled at every vertex and a valid coloring is found
from there. These tools are ingenious but at the same time rather complicated,
when compared to the vanilla greedy algorithm and looking ahead the algorithms
presented in this paper. Additionally, the authors of [1] have extended this
theory of palette sparsification, achieving improved results for when $G$ is
triangle free and for $(1+\epsilon)\Delta$-coloring in general. Another
important line of research concerns solving these problems in a space-
efficient manner: [2, 5] develop algorithms for $\Delta+1$-coloring and
related problems using a (near) linear amount of space. Meanwhile An almost
matching lower bound of $\Omega(n\sqrt{n})$ is also known, implying that their
algorithm is optimal up to $\text{polylog}(n)$ factors.

#### Our Contribution.

In this work, we revisit the graph coloring problem, in both classical and
quantum query models. We give a new randomized algorithm for
$(1+\epsilon)\Delta$ coloring which is optimal for sufficiently large
$\epsilon$, and a quantum variant of this algorithm follows readily that
bypasses the classical lower bound in [2]. The most appealing feature of our
algorithms is their simplicity. Basically, we are inspired by the $\Delta+1$
greedy algorithm, where the algorithms progresses by extending a partial
solution _locally_ , and it is suitable to speed up “local” search subroutine
by quantum unstructured search. In particular, we do not need the heavy
machinery such as palette sparsification and list-coloring in existing
classical algorithms. We overview our results below, and see also Table 1 for
a summary.

Result 1: A randomized algorithm for $(1+\epsilon)\Delta$-coloring which makes
$O(\epsilon^{-1/2}n\sqrt{n})$ queries in expectation and always returns a
valid coloring.

This basic idea inherits the same general “local search” strategy. For each
vertex, we sample a random color and check if it conflicts with any of its
neighbors that has been assigned already. This simple approach is surprisingly
efficient We show that this algorithm has expected query complexity
$O(\frac{n^{2}}{\epsilon\Delta})$, and as in existing works we then just need
to choose between our algorithm and the vanilla greedy algorithm, which gives
the desired
$O(\min\\{n\Delta,\frac{n^{2}}{\epsilon\Delta}\\})=O(\epsilon^{-1/2}n\sqrt{n})$
expected query complexity. This is optimal for $\epsilon^{-1/2}=O(1)$ as we
show in Corollary 3.1, and its Monte Carlo variant improves upon existing
algorithms [1] by a factor of $\epsilon^{-1}$. This algorithm also serves a
template for designing our efficient quantum algorithm. Our new algorithm only
needs oracle access to the adjacency matrix (i.e., pair queries), and the
vanilla greedy algorithm needs access to the adjacency list (i.e., neighbor
queries). Therefore the final algorithm assumes both kinds of oracles are
available.

A central subroutine in our algorithm, which is again extremely simple, is
what we call Find-Conflict. It takes a vertex $v$, a set of vertices $S$ such
that $v\not\in S$ and uses the graph oracle to determine if there are any
edges of the form $(u,v)$ actually present in $E(G)$ for any of the $u\in S$.
Classically, this amounts to an exhaustive search on all such vertices $s\in
S$.

Result 2: A quantum algorithm which makes $\tilde{O}(\epsilon^{-1}n^{4/3})$
queries and returns a valid $(1+\epsilon)\Delta$-coloring with high
probability.

Achieving this result essentially has the same strategy as that of result 1,
while noting that Find-Conflict can be instantiated by (variants of) Grover’s
quantum search algorithm [11, 15, 7], under the standard quantum query model
where the adjacency matrix can be queried in quantum superposition. The
analysis nonetheless requires more care to carefully contain the errors.

We remark that although we rely on well-known quantum algorithmic techniques,
it is crucial that they get employed in the right place. For instance, one may
be tempted to perform a search over just the color palette, thus requiring
$O(\sqrt{\Delta}\log\Delta)$ queries, but such an approach would need a rather
powerful “color validity” oracle for every vertex, which needs to be
dynamically updated as various colors become forbidden for some vertices.
Maintaining these oracles from standard oracles (adjacency matrix or adjacency
list) would incur a significant overhead that would wipe out possible quantum
speedup.

Result 3: Quantum query lower bound of $\Omega(n)$ for $O(\Delta)$ coloring,
when (quantum) pair queries are allowed.

This is shown by concocting specific graph instances and reducing the
unstructured search problem to them, when only adjacency matrix queries are
available. Therefore the $\Omega(\sqrt{n})$ quantum query lower bound for
unstructured search [4] will transfer.

Problem | Quantum Algorithm | Classical Algorithm |  Classical Lower Bound
---|---|---|---
$2\Delta$-coloring | $\tilde{O}(n^{4/3})$ |  $\tilde{O}(n\sqrt{n})$, $\tilde{O}(n\sqrt{n})$ [2] |  $\Omega(n\sqrt{n})$ [2]
$(1+\epsilon)\Delta$-coloring | $\tilde{O}(\epsilon^{-1}n^{4/3})$ |  ${O}(\epsilon^{-1/2}n\sqrt{n}\log{n})$,
${O}(\epsilon^{-3/2}n\sqrt{n\log{n}})$ [1] |  $\Omega(n\sqrt{n})$ [2]
Table 1: Summary of results - no reference indicates a result from this work.
The $2\Delta$-coloring problem occurs when $\epsilon=1$ and we include this
case to demonstrate the quantum advantage. Since any $\Delta+1$-coloring is
also a $2\Delta$-coloring by definition, we use [2] for classical
$2\Delta$-coloring, but this comparison is not of great importance. While our
randomized algorithm is given as a Las Vegas algorithm, it can easily be
converted to Monte-Carlo with success probability at least $1-1/n^{k}$ for any
$k$ using only $O(\epsilon^{-1/2}n\sqrt{n}\log{n})$ queries. Note that prior
to this work the best know algorithm for $(1+\epsilon)\Delta$-coloring from
[1] has query complexity ${O}(\epsilon^{-3/2}n\sqrt{n\log{n}})$ compared to
our algorithm’s ${O}(\epsilon^{-1/2}n\sqrt{n}\log{n})$. Note that the former
performs better for $\epsilon^{-1}\leq\sqrt{\log{n}}$, while the latter
performs better for $\epsilon^{-1}\geq\sqrt{\log{n}}$.

#### Further discussion.

One immediate problem left open by our results in to close the gap between the
algorithmic bounds and the lower bound. Some other well studied graph problems
that are likely to admit similar quantum speedups are variants of coloring
(defective coloring, edge coloring, etc) and potentially some dynamic graph
problems.

A problem that has received considerable study in the quantum query model is
triangle finding. Here one aims to either output a triangle if one exists or
determine that the graph is triangle free with bounded error (or other
variants such as listing all triangles). For a general graph this may require
$\Omega(n^{2})$ queries to the adjacency matrix oracle. However, a modified
Grover search can be used, searching over triples of vertices, to achieve an
$\tilde{O}(n\sqrt{n})$ quantum algorithm for triangle finding as in [9]. More
sophisticated arguments in [10] improve upon this resulting, bring the query
complexity down to $\tilde{O}(n^{5/4})$. Conversely, the best know lower bound
for triangle finding in the quantum query model is the immediate $\Omega(n)$
bound established in [3]. Just as in triangle finding, a gap persists between
the best known quantum lower bound and the best known quantum algorithm for
$O(\Delta)$ coloring as shown in our work.

In addition, the problem of _maximum matching_ in which one wishes to find the
largest maximal matching, has been studied in the quantum query model. The
very recent results of [13] gives an improved quantum algorithm for maximum
matching in the adjacency matrix model which makes $O(n^{7/4})$ queries.
However, a lower bound of $\Omega(n^{3/2})$ queries in the adjacency matrix
model established in [6] show that a gap persists between the best known
algorithm and lower bound for this problem as well. Other structural graph
problems such as those relating to connected components and spanning forests
have also been studied. A recent work [14], surprisingly, shows exponential
quantum speedup for these problem, assuming a more sophisticated oracle model
that can answer “cut queries”.

##  2 Preliminaries

In this paper the notation $[n]$ will refer to the set $\\{1,2,\ldots n\\}$
for any positive integer $n$. For a positive integer $L$, the $L$-coloring
problem is as follows: given a graph $G=(V,E)$ and $n=|V|$ we wish to find an
assignment $c:[L]=\\{1,\dots L\\}\to V$ such that for any edge $(x,y)\in E$ we
have $c(x)\not=c(y)$. $L$ will be referred to as the palette throughout. Such
an assignment is called a _valid $L$-coloring of $G$_. Let $\Delta$ be the
maximum degree of any vertex in $G$. As previously stated a simple greedy
algorithm can be shown to always produce a valid coloring and runs in time
$O(n\Delta)$. Rather than time complexity, the results in this paper will
mostly be stated in terms of query complexity. The main models of computation
in this paper are the graph query model and the quantum graph query model. In
the standard graph query model, we assume that $n$ and the degrees of the
vertices is the only knowledge available about $G$ before any queries have
been made. The standard query model for graphs supports the following types of
queries:

  * •

Pair Queries: we can query the oracle if the edge $(v_{i},v_{j})$ is present
in the graph for any $i,j\in\\{1,\dots n\\}$. This will be denoted as

$M[v_{i},v_{j}]=\begin{cases}1&(v_{i},v_{j})\in E\\\
0&\text{otherwise}\end{cases}$

This is equivalent to granting oracle access to the adjacency matrix
$(M_{i,j})$.

  * •

Neighbor Queries: we can query the oracle for the $j$th neighbor of vertex
$v_{i}$ for any $i\in\\{1,\dots n\\}$ and $j\in\\{1,\dots\deg{v_{i}}\\}$. When
$j>\deg{v_{i}}$ the query returns $Null$.

Similarly this is equivalent to granting oracle access to the adjacency list
of the graph.

The classic greedy $\Delta+1$-coloring algorithm can easily be implemented in
the graph query model via neighbor queries. Explicitly, we can determine which
colors are valid at any vertex $v\in V$ with $\deg{v}$ neighbor queries.

In the quantum setting, we assume standard quantum query access to the
adjacency matrix. Namely we allow “pair queries” in superposition. More
precisely, we encode each vertex $i$ in a $O(\log n)$-qubit register
$|i\rangle$, and assume a black-box unitary operation

$O_{M}:|i,j\rangle\mapsto(-1)^{M(i,j)}|i,j\rangle,\quad\forall i,j\in V(G)\,.$

Each application of this unitary transformation will be referred to as a
quantum query.

Quantum “neighbor query” oracle can be defined similarly (i.e., black-box
unitary computing the adjacency list). However, all our algorithms will only
require _classical_ neighbor queries, and hence we do not specify the quantum
oracle explicitly.

Throughout this paper we use the phrase with high probability to mean with
probability at least $1-\frac{1}{n^{k}}$ for a sufficiently large constant
$k$.

##  3 Algorithmic Results

In this section we give a simple optimal randomized algorithm for
$(1+\epsilon)\Delta$-Coloring. This algorithm serves as a "warm-up" and as the
inspiration for the quantum algorithms presented later. We start by
transforming a bound on Monte Carlo algorithms for $O(\Delta)$-Coloring to one
on Las Vegas algorithms for the same class of problems. From the lower bounds
established in [2]:

######  Corollary 3.1.

Any randomized algorithm which always returns a valid $2\Delta$ coloring
requires ${\Omega}(n\sqrt{n})$ queries in expectation.

######  Proof 3.2 (Proof of corollary 1).

Lemma 5.6 of [2] implies that any Monte Carlo algorithm for $2\Delta$ coloring
which makes fewer than $\frac{n\sqrt{n}}{400000}$ queries returns an invalid
coloring with probability at least $\frac{1}{4}$. So, suppose that some Las
Vegas algorithm which makes $O(\frac{n^{3/2}}{T(n)})$ queries in expectation
for some $T:\mathbb{N}\rightarrow\mathbb{N}$ with
$\lim_{n\to\infty}T(n)=\infty$. Now, consider a Monte Carlo variant of this
algorithm which runs until a valid $2\Delta$-coloring is found or until
$\frac{n\sqrt{n}}{500000}$ queries have been made. The probability that this
Monte Carlo variant fails to return a valid coloring is equal to the
probability that the Las Vegas algorithm makes $\frac{n\sqrt{n}}{500000}$
queries or more on the same input. Let $Q$ denote the number of queries made
by the Las Vegas algorithm. From Markov’s inequality, we have

$\displaystyle\mathbb{P}(Q\geq\frac{n\sqrt{n}}{500000})\leq\frac{\mathbb{E}[Q]}{a}\leq\frac{n\sqrt{n}/T(n)}{n\sqrt{n}/500000}=\frac{500000}{T(n)}$

Since $T(n)\to\infty$ as $n\to\infty$, there must exist some $N$ such that for
all $n>N$, $T(n)\geq 5000000$ and therefore for $n>N$

$\displaystyle\mathbb{P}(Q\geq\frac{n\sqrt{n}}{500000})$
$\displaystyle\leq\frac{500000}{T(n)}\leq\frac{1}{10}$

Thus, this Monte-Carlo variant produces a valid $2\Delta$-coloring with
probability at least $\frac{9}{10}$ and makes at most
$\frac{n\sqrt{n}}{5000000}$ queries for sufficiently large $n$. This
contradicts lemma 5.6 of [2], proving the stated lower bound.

This result will guide us in our search for randomized algorithms.

###  3.1 Randomized $(1+\epsilon)\Delta$-Coloring

We begin this section by providing a Las Vegas algorithm for
$(1+\epsilon)\Delta$-coloring in the standard query model.

######  Theorem 3.3.

There exists a randomized algorithm which returns a valid $(1+\epsilon)\Delta$
vertex coloring and makes $O(\epsilon^{-1/2}n\sqrt{n})$ queries in
expectation.

######  Proof 3.4 (Proof of theorem 2).

Recall that the greedy algorithm for $\Delta+1$-coloring algorithm makes
$O(n\Delta)$ queries, so when $\Delta\ll n$ this algorithm performs very well.
This helps us on our search for sublinear algorithms since we can use this
just greedy algorithm when $\Delta$ is sufficiently small, allowing us to
restrict our attention to larger $\Delta$ i.e. $\Delta\geq\sqrt{n}$ \- this is
the case in previous work [1, 2]. Since $\Delta$ is not given, we must solve
for it. This can be done with neighbor queries by binary searching at each
vertex, i.e. we binary search at $v$ to find the maximum $i$ such that the
neighbor query $(v,i)$ does not return $Null$. Doing this at every vertex and
then taking the maximum uses $O(n\log{n})$ queries.

Both the classical and quantum coloring algorithms in this paper will have the
same general strategy: when coloring a vertex choose a random color, test
whether that color is a valid choice, if it is we move on, otherwise repeat.
While this is a simple approach with some obvious limitations, it yields some
surprisingly efficient algorithms. The only data structure we maintain in all
of our algorithms is defined as follows:

  * •

For every $c\in[(1+\epsilon)\Delta]$ we maintain a set called $\chi(c)$ of all
vertices which we have been colored with color $c$. Let $\chi_{t}(c)$ denote
the collection of vertices with color $c$ after having colored $t-1$ vertices.

Our randomized algorithm is as follows:

for $v\in V$ while $v$ is not colored Choose a color $c$ uniformly at random
from $[(1+\epsilon)\Delta]$ for $u\in\chi(c)$ Query $M[u,v]$ if $M[u,v]=1$
break choose a new color Assign color $c$ to $v$ and update $\chi(c)$ with $v$
return The coloring assignment $\\{\chi(1),\dots\chi((1+\epsilon)\Delta)\\}$
Algorithm 1 $(1+\epsilon)\Delta$-Color($G(V,E),\epsilon$)

Note that this algorithm always returns a valid $(1+\epsilon)\Delta$-coloring
since a color $c\in[(1+\epsilon)\Delta]$ is only ever assigned to $v$ if no
edge of the form $(u,v)$ for $u\in\chi(c)$ is present in the graph. Every
vertex has at least one valid color since a vertex $v$ has at most $\Delta$
neighbors and therefore at least $(1+\epsilon)\Delta-\Delta=\epsilon\Delta\geq
1$ valid colors.

Now, we will show that $(1+\epsilon)\Delta$-Color makes
$O(\epsilon^{-1/2}n\sqrt{n})$ queries in expectation, for sufficiently large
$\Delta$. Let $Q(G)$ denote the number of queries made by this algorithm for a
graph $G$ and let $Q_{t}$ denote the number of queries made when coloring
vertex $v_{t}$. Observe that

$\displaystyle\mathbb{E}[Q(G)]$
$\displaystyle=\mathbb{E}\bigg{(}\sum_{t=1}^{n}Q_{t}\bigg{)}=\sum_{t=1}^{n}\mathbb{E}[Q_{t}]$

So, bounding $\mathbb{E}[Q_{t}]$ will allow us to bound the total expected
number of queries.

######  Lemma 3.5.

For $\Delta\geq\sqrt{n/\epsilon}$ and any $t\leq n$

$\mathbb{E}[Q_{t}]=O(\sqrt{n/\epsilon})$

######  Proof 3.6 (Proof of lemma 3).

Let $c$ be the first color that is chosen for the vertex we are currently
looking at. There are two possibilities: 1) $c$ is valid at $v_{t}$ or 2) it
is not. Let $p=\mathbb{P}[c\text{ is valid at }v_{t}]$, we have:

$\displaystyle\mathbb{E}[Q_{t}]$ $\displaystyle=p\mathbb{E}[|\chi(c)|\ :\
c\text{ is valid at }v_{t}]+(1-p)(\mathbb{E}[|\chi(c)|\ :\ c\text{ is invalid
at }v_{t}]+\mathbb{E}[Q_{t}])$ $\displaystyle=p\mathbb{E}[|\chi(c)|\ :\
c\text{ is valid at }v_{t}]+(1-p)\mathbb{E}[|\chi(c)|\ :\ c\text{ is invalid
at }v_{t}]+(1-p)\mathbb{E}[Q_{t}]$
$\displaystyle=\mathbb{E}[|\chi(c)|]+(1-p)\mathbb{E}[Q_{t}]$

When $c$ is chosen uniformly at random from $[(1+\epsilon)\Delta]$,
$\mathbb{E}[|\chi(c)|]\leq\frac{n}{(1+\epsilon)\Delta}$. Also, recall that
there are at least $\epsilon\Delta$ colors valid colors for $v_{t}$, so
$p\geq\frac{\epsilon\Delta}{(1+\epsilon)\Delta}=\frac{\epsilon}{1+\epsilon}$.
From these facts it follows that

$\displaystyle\mathbb{E}[Q_{t}]$
$\displaystyle=\frac{1}{p}\mathbb{E}[|\chi(c)|]\leq\frac{1+\epsilon}{\epsilon}\frac{n}{(1+\epsilon)\Delta}=\frac{n}{\epsilon\Delta}$

Hence, when $\Delta\geq\sqrt{n/\epsilon}$

$\mathbb{E}[Q_{t}]\leq\sqrt{n/\epsilon}\,.$

From Lemma 3.5 we have that

$\displaystyle\sum_{t=1}^{n}\mathbb{E}[Q_{t}]=O(\epsilon^{-1/2}n\sqrt{n})$

when $\Delta\geq\sqrt{n/\epsilon}$. So, $(1+\epsilon)$-Color makes
$O(\epsilon^{-1/2}n\sqrt{n})$ queries in expectation for
$\Delta\geq\sqrt{n/\epsilon}$ and the greedy algorithm suffices for
$\Delta\leq\sqrt{n/\epsilon}$. This concludes the proof of Theorem 3.3.

Whenever $\epsilon^{-1/2}=O(1)$ we have that $\mathbb{E}[Q(G)]=O(n\sqrt{n})$.
Hence this algorithm achieves the query lower bound for Las Vegas algorithms
established in corollary 1 for sufficiently large values of $\epsilon$ \- this
is somewhat surprising given the exceedingly simple nature of this randomized
algorithm. However, this procedure is not useful when $\epsilon^{-1}=\Delta$
($\Delta+1$-coloring), so finding an $O(n\sqrt{n})$ algorithm (Las Vegas or
Monte Carlo) for $\Delta+1$ coloring remains as an open problem. Also, note
that this algorithm can readily be converted to have a fixed query complexity
with error bounded by $O(1/n^{k})$ for any constant $k$ via Markov’s
inequality. Doing so incurs a multiplicative cost of an additional $O(\log{n}$
It would be interesting to see if the randomness used here could be combined
with the palette sparsification technique of [2] to achieve an improved
algorithm for $\Delta+1$-coloring.

$v$ Figure 1: Here, we query all edges whose existence would prevent us from
coloring $v$ red

##  4 Quantum Algorithms

The simple randomized algorithm explored in the previous section involved
repeatedly solving the following sub-problem: Given a vertex $v\in V$ and a
collection of vertices $S\subset V\setminus v$ determine if $\\{(u,v):u\in
S\\}\cap E(G)=\emptyset$. In other words, does $v$ have any neighbors in $S$?
In effect, this is just an instance of unstructured search. However, we do not
know how many (if any) such edges are actually present, so a standard Grover
search algorithm will not work here. Luckily, a slight modification of Grover
search resolves this problem.

######  Claim 1.

There is a quantum algorithm which given a set of vertices $S\subset V$ and
$v\in V\setminus S$ determines whether or not $v$ is adjacent to any vertex in
$S$ and returns such a vertex in $S$ if it exists using $O(\sqrt{|S|})$
queries to the oracle with success probability at least $\frac{2}{3}$, without
prior knowledge of $|\\{(v,s)\in E\ |\ s\in S\\}|$.

This is a restatement of Theorem 3 of [8], whose algorithm is sketched in the
appendix. This result was originally proven in [7]. This $2/3$ success
probability can be amplified to at least $1-\frac{1}{n^{3}}$ via $O(\log{n})$
additional runs. So, we will let $\textbf{Find-Conflict}(v,S)$ be the
algorithm which determines if $v$ is adjacent to $s\in S$ with failure
probability at most $\frac{1}{n^{2}}$ and uses $O(\sqrt{|S|}\log{n})$ queries.
We can additionally guarantee that Find-Conflict does not return false
positives (concluding there is a conflict when no such conflict exists) by
having it return a proposed neighbor of $v$, $s\in S$, and then make the
classical query $(v,s)$ to ensure this edge is actually present in the graph.
Thus, the only chance of error is when we incorrectly conclude there is no
conflict, which happens with probability at most $\frac{1}{n^{3}}$. A detailed
version of this algorithm is included in Appendix A.

In $(1+\epsilon)\Delta$-Color we needed to spend $|\chi(c)|$ queries in the
worst case in order to determine if $c$ is valid at $v$, but by using Find-
Conflict we are able to achieve a quantum speed up. Another change in the case
of the quantum algorithm is that we wish only have one type of randomness
(accuracy or query complexity). To simplify the analysis we only allow the
algorithm to test "small" color classes; explicitly, we only look at color
classes of size at most $\frac{2n}{\epsilon\Delta}$. We did not do this in the
case of the randomized algorithm since the expected size of a uniformly random
color class gives the desired asymptotic. Since we now wish to bound the error
of the algorithm, we fix the total number of queries at
$T=9\epsilon^{-3/2}\log^{2}{n}\sqrt{\frac{n^{3}}{\Delta}}$.

######  Theorem 4.1.

There exists a quantum algorithm which returns a valid
$(1+\epsilon)\Delta-$vertex coloring with high probability and makes
$\tilde{O}(\epsilon^{-1}n^{4/3})$ queries.

######  Proof 4.2 (Proof of theorem 5).

Consider the algorithm below:  $t\leftarrow 0$ while $t\leq T$ for $v\in V$:
while $v$ is not colored  Choose a color $k$ uniformly at random from
$[(1+\epsilon)\Delta]$ if $|\chi(k)|>\frac{2n}{\epsilon\Delta}$ break choose a
new color  else if Find-Conflict($v,\chi(k)$)  $t\leftarrow
t+2\sqrt{\frac{n}{\epsilon\Delta}}\log{n}$ break choose a new color  else
Assign $k$ to $v$ and update $\chi(k)$ return The coloring assignment
$\\{\chi(1),\dots\chi((1+\epsilon)\Delta)\\}$ Algorithm 2 Quantum-
Color($G(V,E)$, $\epsilon$)

######  Lemma 4.3.

Quantum-Color returns valid $(1+\epsilon)\Delta$-coloring of $G$ with high
probability.

######  Proof 4.4 (Proof of lemma 6).

First, note that that in this algorithm Find-Conflict is only ever called when
$|\chi(c)|\leq\frac{2n}{\epsilon\Delta}$, so every call makes at most
$2\sqrt{\frac{n}{\epsilon\Delta}}\log{n}$ queries and has failure probability
at most $1/n^{2}$. This algorithm fails to produce a valid coloring in two
cases:

  1. 1.

Some vertex is assigned an invalid color

  2. 2.

Not all of the vertices are colored by the time
$9\epsilon^{-3/2}\log^{2}n\sqrt{\frac{n^{3}}{\Delta}}$ queries have been made

For the first case, note that any $v\in V$ is assigned an invalid color only
when Find-Conflict returns false when it should return true. This occurs with
probability at most $\frac{1}{n^{2}}$ when a color which is invalid at $v$ is
chosen. So a union bound shows that when all vertices are assigned a color,
the coloring is valid with probability at least $1-\frac{1}{n^{2}}$.

Now, we will show that with high probability every vertex is assigned some
color before using too many queries. Let $Q_{t}$ be the number of queries made
when attempting to color vertex $v_{t}$. Additionally, let $K_{t}$ be the
number of times that a small random color
($|\chi(k)|\leq\frac{2n}{\epsilon\Delta}$) is tested when attempting to color
$v_{t}$. Note that $K_{t}$ is the number of times that Find-Conflict is called
on $v_{t}$. Let $\ell=9\epsilon^{-3/2}\log^{2}n\sqrt{\frac{n}{\Delta}}$. Then,

$\displaystyle\mathbb{P}[Q_{t}\geq\ell]$
$\displaystyle\leq\mathbb{P}[K_{t}\geq 9\epsilon^{-1}\log n]$

Since Find-Conflict cannot have false positives, $K_{t}$ only depends on the
number of invalid colors that we test with Find-Conflict. In other words, we
are guaranteed to stop once a valid small color is chosen and we will use this
to upper bound $K_{t}$.

Now, note that there are at most $\frac{\epsilon\Delta}{2}$ colors $k$ such
that $|\chi(k)|\geq\frac{2n}{\epsilon\Delta}$ and since there are at least
$\epsilon\Delta$ valid colors for $v$, there must be at least
$\frac{\epsilon\Delta}{2}$ colors which are both small and valid. For a color
$k$ which is randomly chosen among all small colors, it is valid with
probability at least
$\frac{\epsilon\Delta/2}{(1+\epsilon\Delta)}=\frac{\epsilon}{2(1+\epsilon)}\geq\frac{\epsilon}{4}$.
Thus,

$\displaystyle\mathbb{P}[Q_{t}\geq\ell]$
$\displaystyle\leq\mathbb{P}[K_{t}\geq 9\epsilon^{-1}\log
n]\leq\bigg{(}1-\frac{\epsilon}{4}\bigg{)}^{9\epsilon^{-1}\log{n}}$

Now, note that for $\epsilon>0$,
$\bigg{(}1-\frac{\epsilon}{4}\bigg{)}^{\epsilon^{-1}}<\frac{1}{\sqrt[4]{e}}$,
so

$\displaystyle\mathbb{P}[Q_{t}\geq\ell]$
$\displaystyle\leq\bigg{(}\frac{1}{\sqrt[4]{e}}\bigg{)}^{9\log{n}}\leq\bigg{(}\frac{1}{2}\bigg{)}^{3\log{n}}=\frac{1}{n^{3}}$

By union bound, we get

$\displaystyle\mathbb{P}\bigg{[}\sum_{t=1}^{n}Q_{t}\geq
9\epsilon^{-3/2}\log^{2}{n}\sqrt{\frac{n^{3}}{\Delta}}\bigg{]}$
$\displaystyle\leq\sum_{t=1}^{n}\mathbb{P}[K_{t}\geq 9\epsilon^{-1}\log{n}]$
$\displaystyle\leq\frac{n}{n^{3}}=\frac{1}{n^{2}}$

Taking both failure cases into account, we can see
$O(\epsilon^{-3/2}\log^{2}{n}\sqrt{\frac{n^{3}}{\Delta}})$ queries are made
and that a valid $(1+\epsilon)\Delta$-coloring is obtained with probability at
least $1-\Theta(n^{-2})$ for sufficiently large $n$ and this can be boosted to
$1-\Theta(n^{-k})$ by altering the constants used for any $k>0$.

Now, note that whenever $\Delta\geq n^{1/3}\epsilon^{-1}$ this algorithm makes
$\tilde{O}(\epsilon^{-1}n^{4/3})$ queries and the greedy algorithm suffices
whenever $\Delta\leq n^{1/3}$.

##  5 Lower Bounds

In this section, we establish some lower bounds for coloring and maximal
matching with a very simple argument relying on the optimality of Grover’s
algorithm [8]:

######  Theorem 5.1.

$\Omega(n$) queries are necessary to obtain an $O(\Delta)$\- coloring on
graphs with exactly one edge using only (quantum) adjacency matrix queries.

######  Proof 5.2 (Proof of theorem 12).

Finding a $2$-coloring for these graphs, given the promise that there is
exactly one edge is the same as determining for which $i,j\in[n]$ with
$i\not=j$ we have $M[i,j]=1$. Clearly, we can see this as an instance of
unstructured search with exactly one marked element among the
$\binom{n}{2}=O(n^{2})$ possible edges. Since unstructured search requires
$\Omega(\sqrt{N})$ quantum queries, $\Delta+1$ coloring requires $\Omega(n)$
quantum queries in general. This also implies that $\Omega(n)$ queries are
necessary for $2\Delta$ coloring on general graphs since finding a
$2-$coloring for graphs with exactly one edge is also equivalent to finding a
$2\Delta$ coloring ($\Delta=1$).

It would be very interesting to see if more advanced techniques could yield a
tighter lower bound, especially one which includes classical neighbor queries.
We suspect that when all types of queries are available the same bound holds.

##  Appendix A Details of Find-Conflict

Here, we will give an explicit description of the quantum subroutine Find-
Conflict for completeness. Recall that for a given set $S\subset V$ and some
$v\in V$ we wish to determine if there exists $u\in S$ such that $(u,v)\in E$
with probability at least $\frac{2}{3}$. This algorithm is described in [8].

Let $U_{O}$ be the unitary oracle transformation

for $t=1,2:$

$|\phi\rangle\leftarrow\frac{1}{\sqrt{|S|}}\sum_{u\in S}|uv\rangle$

$U_{\phi}=2|\phi\rangle\langle\phi|-I$

Apply $U_{O}$ and then $U_{\phi}$ to $|\phi\rangle$ each
$\frac{\pi}{4}\sqrt{\frac{N}{t}}$ times

Observe $|\phi\rangle$ resulting in candidate edge $(u,v)$

Make the classical edge query $(u,v)$

if $M[u,v]=1$:

return True

return False

Algorithm 3 Find-Conflict$(v,S)$

######  Proof A.1.

If there are exactly $1$ or $2$ conflicting neighbors for $v$ in $S$ then $u$
will be one of them with high probability when $t=1$ or $t=2$ respectively.
When there are no conflicts the algorithm will always return False. The only
worrisome case is when there are $3$ or more conflicts for $v$ in $S$.
However, when there are $t_{0}>2$ conflicts each of the searches with $t=1,2$
will still succeed with probability at least $1/2$, resulting in an error
probability of at most $\frac{1}{4}$. $O(\sqrt{|S|})$ queries are used every
iteration, so $O(\sqrt{|S|})$ queries are used in total. See Theorem 3 of [8]
for more details and [7] for general reference.

## References

  * [1] Noga Alon and Sepehr Assadi.  Palette Sparsification Beyond ($\Delta$+1) Vertex Coloring.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020), volume 176 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:22. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.APPROX/RANDOM.2020.6.
  * [2] Sepehr Assadi, Yu Chen, and Sanjeev Khanna.  Sublinear algorithms for ($\Delta$\+ 1) vertex coloring.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 767–786. SIAM, 2019.  doi:10.1137/1.9781611975482.48.
  * [3] Aleksandrs Belovs and Ansis Rosmanis.  On the power of non-adaptive learning graphs.  2013 IEEE Conference on Computational Complexity, Jun 2013.  URL: http://dx.doi.org/10.1109/CCC.2013.14, doi:10.1109/ccc.2013.14.
  * [4] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani.  Strengths and weaknesses of quantum computing.  SIAM Journal on Computing, 26(5):1510–1523, Oct 1997.  URL: http://dx.doi.org/10.1137/S0097539796300933, doi:10.1137/s0097539796300933.
  * [5] Suman K. Bera, Amit Chakrabarti, and Prantar Ghosh.  Graph coloring via degeneracy in streaming and other space-conscious models.  CoRR, abs/1905.00566, 2019.  URL: http://arxiv.org/abs/1905.00566, arXiv:1905.00566.
  * [6] Aija Berzina, Andrej Dubrovsky, Rusins Freivalds, Lelde Lace, and Oksana Scegulnaja.  Quantum query complexity for some graph problems.  In Peter Van Emde Boas, Jaroslav Pokorný, Mária Bieliková, and Július Štuller, editors, SOFSEM 2004: Theory and Practice of Computer Science, pages 140–150, Berlin, Heidelberg, 2004\. Springer Berlin Heidelberg.
  * [7] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp.  Tight bounds on quantum searching.  Fortschritte der Physik, 46(4-5):493–505, Jun 1998.  URL: http://dx.doi.org/10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P, doi:10.1002/(sici)1521-3978(199806)46:4/5<493::aid-prop493>3.0.co;2-p.
  * [8] H. Buhrman, R. Cleve, R. De Wolf, and C. Zalka.  Bounds for small-error and zero-error quantum algorithms.  In 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039), pages 358–368, 1999.  doi:10.1109/SFFCS.1999.814607.
  * [9] Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, and Ronald de Wolf.  Quantum algorithms for element distinctness.  SIAM Journal on Computing, 34(6):1324–1330, Jan 2005.  URL: http://dx.doi.org/10.1137/S0097539702402780, doi:10.1137/s0097539702402780.
  * [10] Francois Le Gall.  Improved quantum algorithm for triangle finding via combinatorial arguments.  2014 IEEE 55th Annual Symposium on Foundations of Computer Science, Oct 2014.  URL: http://dx.doi.org/10.1109/FOCS.2014.31, doi:10.1109/focs.2014.31.
  * [11] Lov K. Grover.  A fast quantum mechanical algorithm for database search, 1996.  arXiv:arXiv:quant-ph/9605043.
  * [12] Richard M Karp.  Reducibility among combinatorial problems.  In Complexity of computer computations, pages 85–103. Springer, 1972.  doi:10.1007/978-1-4684-2001-2_9.
  * [13] Shelby Kimmel and R. Teal Witter.  A query-efficient quantum algorithm for maximum matching on general graphs.  2020\.  arXiv:2010.02324.
  * [14] Troy Lee, Miklos Santha, and Shengyu Zhang.  Quantum algorithms for graph problems with cut queries.  arXiv:2007.08285, 2020.  https://arxiv.org/abs/2007.08285.
  * [15] Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha.  Search via quantum walk.  SIAM journal on computing, 40(1):142–164, 2011.  doi:10.1137/090745854.