# Quantum search in structured database using local adiabatic evolution and
spectral methods

R. Sufiania,b , N. Baharia
aDepartment of Theoretical Physics and Astrophysics, University of Tabriz,
Tabriz 51664, Iran.
bInstitute for Studies in Theoretical Physics and Mathematics, Tehran
19395-1795, Iran.,
University of Tabriz, Tabriz 51664, Iran<EMAIL_ADDRESS>
###### Abstract

Since Grover’s seminal work which provides a way to speed up combinatorial
search, quantum search has been studied in great detail. We propose a new
method for designing quantum search algorithms for finding a marked element in
the state space of a graph. The algorithm is based on a local adiabatic
evolution of the Hamiltonian associated with the graph. The main new idea is
to apply some techniques such as Krylov subspace projection methods, Lanczos
algorithm and spectral distribution methods. Indeed, using these techniques
together with the second-order perturbation theory, we give a systematic
method for calculating the approximate search time at which the marked state
can be reached. That is, for any undirected regular connected graph which is
considered as the state space of the database, the introduced algorithm
provides a systematic and programmable way for evaluation of the search time,
in terms of the corresponding graph polynomials.

Keywords: Quantum search algorithm, Local adiabatic evolution, Graph, Krylov
subspace, Lanczos algorithm, Spectral distribution, Second-order perturbation
theory.

PACs Index: 03.65.Ud

##  1 Introduction

Grover’s quantum search algorithm [1] is one of the main applications of
quantum computation. This algorithm is sometimes described as a way for
searching a marked item in an unstructured database of $N$ items in time
$O(\sqrt{N})$. This gives a quadratic speedup over the exhaustive search for a
variety of search problems [2]. But the algorithm as originally proposed is
not designed to search a physical database. In [3], Aaronson and Ambainis
present a model of query complexity on graphs, where they showed that a
database of $N$ items laid out in $d$ spatial dimensions can be searched in
time of order $\sqrt{N}$. In [4], Childs and Goldstone have considered an
alternative quantum search algorithm based on a continuous time quantum walk
on a graph. Quantum walks provide a natural framework for the spatial search
problem because the graph can be used to model the locality of the database.
In fact, for the case of the complete graph (unsorted database), the resulting
algorithm is simply the continuous time search algorithm of Farhi and Gutmann
[5]. On the hypercube, their results showed that the algorithm also provides
quadratic speedup [6, 7, 8]. In [6], Farhi et al. have used the time-dependant
Hamiltonian approach for Grover’s problem, where they have considered the
constant-rate adiabatic approach (the requirement of adiabaticity is expressed
globally) and obtained a complexity of order $N$, the number of items in
database. Then, Roland and Cerf [9] have been considered the same problem with
the same approach with this deference that they considered the adiabatic
evolution locally, i.e., they adjusted the evolution rate of the Hamiltonian
so as to keep the evolution adiabatic on each infinitesimal time interval and
by this adjusting the total running time of order $\sqrt{N}$ has obtained.
Recently, another adiabatic version of the quantum search problem has
considered by Rezakhani et al. in [10], where they have employed continuous
time, global adiabatic evolution in order to calculate a quantity called
“adiabatic error”, which quantifies the distance between the instantaneous
ground state and the actual marked state.

In this paper, we follow the approach of the paper [9] and employ some
techniques such as Krylov subspace projection methods, Lanczos algorithm,
spectral distribution methods and the second-order perturbation theory in
order to give a systematic method for calculating the total search time
approximately. In fact, by reducing the Hilbert space of the corresponding
Hamiltonian to the smaller one called Krylov subspace and using the spectral
methods, we calculate the minimum energy gap between two lowest eigenvalues of
the Hamiltonian and consequently the total search time, in terms of the
polynomials associated with the graph. The organization of the paper is as
follows: In section 2, we recall some preliminary facts about Krylov subspace
projection methods and spectral distribution method needed for the approach of
the paper. In section 3, by using the local adiabatic evolution approach,
quantum search on a graph is investigated, where an analytical but approximate
formula for the quantum search time (the main result of the paper) is obtained
in terms of the graph polynomials. Section 4 is devoted to some examples of
graphs, in order to clarify the introduced method in details. The last section
contains a brief conclusion.

##  2 Krylov subspace and spectral methods

In this section we give a brief review of some of the main features of Krylov
subspace projection methods and spectral distribution method (the reader is
referred to Refs. [11]-[19] for more details).

###  2.1 Krylov subspace projection methods

Krylov subspace projection methods (KSPM) are probably the most important
class of projection methods for linear systems and for eigenvalue problems. In
KSPM, approximations to the desired eigenpairs of an $n\times n$ matrix $A$
are extracted from a $d$-dimensional Krylov subspace

$K_{d}(|\phi_{0}\rangle,A)=span\\{|\phi_{0}\rangle,A|\phi_{0}\rangle,\cdots,A^{d-1}|\phi_{0}\rangle\\},$
(2-1)

where $|\phi_{0}\rangle$ is often a randomly chosen starting vector called
reference state and $d\ll n$. In practice, the retrieval of desired spectral
information is accomplished by constructing an orthonormal basis $V_{d}\in
R^{n\times d}$ of $K_{d}(|\phi_{0}\rangle,A)$ and computing eigenvalues and
eigenvectors of the $d$ by $d$ projected matrix
$H_{d}={P_{V_{d}}}^{T}AP_{V_{d}}$, where $P_{V_{d}}$ is projection operator to
$d$-dimensional subspace spanned by the basis $V_{d}$.

The most popular algorithm for finding an orthonormal basis for the Krylov
subspace, is Lanczos algorithm. The Lanczos algorithm transforms a Hermitian
matrix $A$ into a tridiagonal form iteratively, i.e., the matrix $A$ will be
of tridiagonal form in the $d$-dimensional projected subspace $H_{d}$. In
fact, the Lanczos algorithm is deeply rooted in the theory of orthogonal
polynomials, which builds an orthonormal sequence of vectors
$\\{|\phi_{0}\rangle,|\phi_{1}\rangle,...,|\phi_{d-1}\rangle\\}$ and satisfy
the following three-term recursion relations

$A|\phi_{i}\rangle=\beta_{i+1}|\phi_{i+1}\rangle+\alpha_{i}|\phi_{i}\rangle+\beta_{i}|\phi_{i-1}\rangle.$
(2-2)

The vectors $|\phi_{i}\rangle,i=0,1,...,d-1$ form an orthonormal basis for the
Krylov subspace $K_{d}(|\phi_{0}\rangle,A)$. In these basis, the matrix $A$ is
projected to the following symmetric tridiagonal matrix:

$A\doteq\left(\begin{array}[]{cccccc}\alpha_{0}&\beta_{1}&0&...&...\\\
\beta_{1}&\alpha_{1}&\beta_{2}&0&...\\\
0&\beta_{2}&\alpha_{2}&\beta_{3}&...\\\ \vdots&\vdots&\ddots&\ddots&\ddots\\\
...&0&\;\;\ \beta_{{}_{d-2}}&\;\;\ \alpha_{{}_{d-2}}&\;\ \beta_{d-1}\\\
...&...&0&\beta_{d-1}&\alpha_{d-1}\\\ \end{array}\right),$ (2-3)

where the scalars $\beta_{i+1}$ and $\alpha_{i}$ are computed to satisfy two
requirements, namely that $|\phi_{i+1}\rangle$ be orthogonal to
$|\phi_{i}\rangle$ and that $\||\phi_{i+1}\rangle\|=1$.

In fact, the Lanczos algorithm is a modified version of the classical Gram-
Schmidt orthogonalization process. As it can be seen, at its heart is an
efficient three-term recursion relation which arises because the matrix $A$ is
real and symmetric.
If we define the Krylov matrix $K$ such that the columns of $K$ are Krylov
basis $\\{A^{i}\phi_{0};i=0,...,d-1\\}$ as:

$K:=(|\phi_{0}\rangle,A|\phi_{0}\rangle,...,A^{d-1}|\phi_{0}\rangle),$

the application of the orthonormalization process to the Krylov matrix is
equivalent to the construction of an upper triangular matrix $P$ such that the
resulting sequence $\Phi=KP$ satisfies $\Phi^{\dagger}\Phi=1$. We denote by
$|\phi_{j}\rangle$ and $P_{j}$ respectively the $j$-th column of $\Phi$ and
$P$. Then we have

$\langle\phi_{0}|P_{i}^{\dagger}(A)P_{j}(A)|\phi_{0}\rangle=\langle
KP_{i}|KP_{j}\rangle=\langle\phi_{i}|\phi_{j}\rangle,$ (2-4)

where $P_{i}=a_{0}+a_{1}A+...+a_{i}A^{i}$ is a polynomial of degree $i$ in
indeterminate $A$.

In the remaining part of this section we give an algorithmic outline of the
Lanczos algorithm, where it will be used in calculation of parameters
$\alpha_{i}$ and $\beta_{i}$ appeared in (2-2).
Lanczos algorithm
Input: Matrix $A\in R^{n\times n}$, starting vector $|\phi_{0}\rangle$,
$\||\phi_{0}\rangle\|=1$, scalar $d$
Output: Orthogonal basis $\\{|\phi_{0}\rangle,...,|\phi_{d-1}\rangle\\}$ of
Krylov subspace $K_{d}(|\phi_{0}\rangle,A)$

$\beta_{0}=0,|\phi_{0}\rangle=|\phi\rangle/\||\phi\rangle\|$ $for\;\;\
i=0,1,2,...$ $|\upsilon_{i}\rangle=A|\phi_{i}\rangle$
$\alpha_{i}=\langle\phi_{i}|\upsilon_{i}\rangle$
$|\upsilon_{i+1}\rangle=|\upsilon_{i}\rangle-\beta_{i}|\phi_{i-1}\rangle-\alpha_{i}|\phi_{i}\rangle$
$\beta_{i+1}=\||\upsilon_{i+1}\rangle\|$ $if$ $\beta_{i+1}\neq 0$
$|\phi_{i+1}\rangle=|\upsilon_{i+1}\rangle/\beta_{i+1}$ $else$
$|\phi_{i+1}\rangle=0.$

###  2.2 Spectral distribution method

For any pair $(A,|\phi_{0}\rangle)$ of a matrix $A$ and a vector
$|\phi_{0}\rangle$, one can assign a measure $\mu$ as follows

$\mu(x)=\langle\phi_{0}|E(x)|\phi_{0}\rangle,$ (2-5)

where $E(x)=\sum_{i}|u_{i}\rangle\langle u_{i}|$ is the operator of projection
onto the eigenspace of $A$ corresponding to eigenvalue $x$, i.e.,

$A=\int xE(x)dx$ (2-6)

so that, for any polynomial $P(A)$ we have

$P(A)=\int P(x)E(x)dx,$ (2-7)

where for discrete spectrum the above integrals are replaced by summation. For
example, in continuous time quantum walk on a graph [21], the expectation
value of powers of the corresponding adjacency matrix $A$ over starting site
$|\phi_{0}\rangle$ can be written as

$\langle\phi_{0}|A^{m}|\phi_{0}\rangle=\int_{R}x^{m}\mu(dx),\;\;\;\;\
m=0,1,2,....$ (2-8)

The existence of a spectral distribution satisfying (2-8) is a consequence of
Hamburger s theorem, see e.g., Shohat and Tamarkin [[16], Theorem 1.2].

From the orthogonality of vectors $|\phi_{j}\rangle$ (Krylov bases) produced
from Lanczos algorithm process we have,

$\delta_{ij}=\langle\phi_{i}|\phi_{j}\rangle=\langle\phi_{0}|P_{i}^{\dagger}(A)P_{j}(A)|\phi_{0}\rangle$
$=\int P_{i}^{*}(x)P_{j}(x)\mu(x)dx=(P_{i},P_{j})_{\mu}.$ (2-9)

Conversely if $P_{0},...,P_{d-1}$ is the system of orthonormal polynomials for
the measure $\mu$ then the vectors

$|\phi_{j}\rangle=P_{j}(A)|\phi_{0}\rangle,$ (2-10)

will coincide with the sequence of orthonormal vectors produced by the Lanczos
algorithm applied to $(A,|\phi_{0}\rangle)$.

Now, substituting (2-10) in (2-2), we get three term recursion relations
between polynomials $P_{j}(A)$, which leads to the following three term
recursion between polynomials $P_{j}(x)$

$\beta_{k+1}P_{k+1}(x)=(x-\alpha_{k})P_{k}(x)-\beta_{k}P_{k-1}(x)$ (2-11)

for $k=0,...,d-1$. Multiplying by $\beta_{1}...\beta_{k}$ we obtain

$\beta_{1}...\beta_{k+1}P_{k+1}(x)=(x-\alpha_{k})\beta_{1}...\beta_{k}P_{k}(x)-\beta_{k}^{2}.\beta_{1}...\beta_{k-1}P_{k-1}(x).$
(2-12)

By rescaling $P_{k}$ as $Q_{k}=\beta_{1}...\beta_{k}P_{k}$, the three term
recursion relations (2-11) are replaced by

$Q_{0}(x)=1,\;\;\;\;\;\ Q_{1}(x)=x,$
$Q_{k+1}(x)=(x-\alpha_{k})Q_{k}(x)-\beta_{k}^{2}Q_{k-1}(x),$ (2-13)

for $k=1,2,...,d$.

In the next section, we will need the distinct eigenvalues of adjacency matrix
of a given undirected graph which can be written in the form (2-3), and the
corresponding eigenvectors in order to obtain the minimum time at which the
marked state can be reached. As it is known from spectral theory, we have the
eigenvalues $x_{i}$ of the adjacency matrix $A$ as roots of the last
polynomial $Q_{d+1}(x)$ in (2-13), and the normalized eigenvectors as [18, 19]

$|\psi_{i}\rangle=\frac{1}{\sqrt{\sum_{l=0}^{d}P^{2}_{l}(x_{i})}}\left(\begin{array}[]{c}P_{0}(x_{i})\\\
P_{1}(x_{i})\\\ \vdots\\\ P_{d}(x_{i})\\\ \end{array}\right).$ (2-14)

##  3 Quantum search via local adiabatic evolution

In this section, we investigate quantum search in an structured database by
using the time-dependent Hamiltonian approach and spectral distribution
method. To do so, first, we recall briefly the time-dependent Hamiltonian
approach and local adiabatic evolution employed in Ref.[9] to Grover’s
problem.

Consider the evolution of a quantum system state $|\psi(t)\rangle$ subject to
a time-dependent Hamiltonian $H(t)$ is described by the Schrödinger equation
($\hbar=1$)

$i\frac{d}{dt}|\psi(t)\rangle=H(t)|\psi(t)\rangle.$ (3-15)

According to the adiabatic theorem [20], the state of the system will stay
close to the instantaneous ground state of the Hamiltonian at each time $t$,
if the Hamiltonian varies slowly enough. In other words, for the instantaneous
energy eigenbasis defined by $H(t)|E_{n}(t)\rangle=E_{n}(t)|E_{n}(t)\rangle$,
if we define the minimum gap between the lowest two eigenvalues as

$g_{min}=\min_{0\leq t\leq T}[E_{1}(t)-E_{0}(t)]$ (3-16)

and the maximum value of the matrix element of $\frac{dH}{dt}$ between the two
corresponding eigenstates as

$D_{max}=\max_{0\leq t\leq T}|\langle\frac{dH}{dt}\rangle_{1,0}|$ (3-17)

with $\langle\frac{dH}{dt}\rangle_{1,0}=\langle
E_{1}(t)|\frac{dH}{dt}|E_{0}(t)\rangle$, then the adiabatic evolution theorem
guaranties that for the system which is prepared in its ground state
$|E_{0}(0)\rangle$ at time $t=0$, and evolved under the Hamiltonian $H(t)$, we
will have

$|\langle E_{0}(T)|\psi(T)\rangle|^{2}\geq 1-\epsilon^{2}$ (3-18)

provided that

$\frac{D_{max}}{g^{2}_{min}}\leq\epsilon,$ (3-19)

where $\epsilon\ll 1$.

###  3.1 Quantum search in an unsorted database with local adiabatic evolution

Assuming a set of $N$ items in an unsorted database (uniform distribution)
where one of them is marked, the main goal is finding the marked item in a
minimum run time. To this end, a quantum state $|i\rangle$ is assigned to each
item $i$, so that the state space of the database is spanned by the states
$|i\rangle$ with $i=0,1,\ldots,N-1$, where the marked state is denoted by
$|m\rangle$. Since $|m\rangle$ is unknown a priori, the initial state is
chosen as an equal superposition of all basis states, i.e.,

$|\psi_{0}\rangle=\frac{1}{\sqrt{N}}\sum_{i=0}^{N-1}|i\rangle.$ (3-20)

Then, the Hamiltonian of the system is initially chosen as

$H_{0}=I_{N}-|\psi_{0}\rangle\langle\psi_{0}|$ (3-21)

whose ground state is $|\psi_{0}\rangle$ with energy zero. Since the database
is unsorted, we can associate the items of the database with the nodes of the
complete graph with $N$ vertices (denoted by $K_{N}$), for which the adjacency
matrix is given by $A=J_{N}-I_{N}$. Therefore the initial Hamiltonian can be
written as

$H_{0}=I_{N}-\frac{1}{N}\sum_{i,j=0}^{N-1}|i\rangle\langle
j|=I_{N}-\frac{1}{N}J_{N}=\frac{1}{N}[(N-1)I_{N}-A]=\frac{1}{N}L,$ (3-22)

where, $J_{N}$ is an $N\times N$ all one matrix and $L=(N-1)I_{N}-A$ is the
Laplacian of the complete graph $K_{N}$. Now, suppose that we are able to
apply to our system the Hamiltonian

$H_{m}=I_{N}-|m\rangle\langle m|,$ (3-23)

whose ground state is the unknown marked state $|m\rangle$. Then, the
corresponding time dependent Hamiltonian is considered as the following linear
interpolation between $H_{0}$ and $H_{m}$

$H(s)=(1-s)H_{0}+sH_{m}=\frac{1}{N}[(N-1+s)I_{N}-(1-s)A-Ns|m\rangle\langle
m|],$ (3-24)

where $s$ is an evolution function of time $t$ and must be found optimally
with the boundary conditions $s(0)=0$ and $s(T)=1$. In the global adiabatic
evolution $s(t)$ is chosen as a linear function of $t$ as $s(t)=t/T$, but in
the local adiabatic evolution the time interval $T$ is divided into
infinitesimal time intervals $dt$ and the adiabaticity condition is locally
applied to each of these intervals. Applying Eq.(3-19) to each infinitesimal
time intervals, the local adiabatic condition is given by

$|\frac{ds}{dt}|\leq\epsilon\frac{g^{2}(s)}{|\langle\frac{dH}{dt}\rangle_{1,0}|}$
(3-25)

for all times $t$. Now, by using the fact that
$|\langle\frac{dH}{dt}\rangle_{1,0}|\leq 1$, the condition (3-25) is verified
provided that

$|\frac{ds}{dt}|=\epsilon g^{2}(s).$ (3-26)

The algorithm consists in preparing the system in the state $|\psi_{0}\rangle$
and then applying the Hamiltonian $H(s)$ during a time $T$ so that $s(T)=1$.
In order to obtain the eigenvalues of $H(s)$ and evaluate (3-16), we use the
Lanczos algorithm to obtain the orthonormal basis in which the hamiltonian
$H(s)$ can be reduced to as a tridiagonal matrix. To do so, we choose
$|m\rangle\equiv|\phi_{0}\rangle$ as the reference state (starting vector in
the Lanczos iteration algorithm) and apply $H(s)$ on it to obtain the vector
orthogonal to $|\phi_{0}\rangle$ as

$|\phi_{1}\rangle=\frac{1}{\sqrt{N-1}}(\sqrt{N}|\psi_{0}\rangle-|\phi_{0}\rangle).$

Now, the Hamiltonian $H(s)$ can be represented in the new orthonormal basis
states $|\phi_{0}\rangle$ and $|\phi_{1}\rangle$ as follows

$H(s)=\frac{1}{N}\left(\begin{array}[]{cc}(1-s)(N-1)&-\sqrt{N-1}(1-s)\\\
-\sqrt{N-1}(1-s)&1+s(N-1)\\\ \end{array}\right)$ (3-27)

The eigenvalues of $H(s)$ are given by
$E_{\pm}=\frac{1}{2N}\\{N\pm\sqrt{N^{2}(1-2s)^{2}+4Ns(1-s)}\\}$, so that the
difference between these two eigenvalues gives the gap $g(s)$ as

$g(s)=\sqrt{\frac{N-4s(1-s)(N-1)}{N}}.$ (3-28)

We see that the minimum gap $g_{min}=\frac{1}{\sqrt{N}}$ is attained for
$s=1/2$. Now, by using the local adiabatic condition (3-26) we obtain

$|\frac{ds}{dt}|=\frac{\epsilon}{N}[N-4s(1-s)(N-1)].$ (3-29)

After integration, one can find

$t=\frac{1}{2\epsilon}\frac{N}{\sqrt{N-1}}\\{\arctan[\sqrt{N-1}(2s-1)]+\arctan{\sqrt{N-1}}\\}.$
(3-30)

One may now evaluate the computation time of the algorithm by taking $s=1$.
For $N\gg 1$, we obtain

$T\simeq\frac{\pi}{2\epsilon}\sqrt{N},$ (3-31)

which gives a quadratic speed-up with respect to a classical search, so that
the algorithm can be viewed as the adiabatic evolution version of Grover’s
algorithm.

###  3.2 Quantum search in a structured (non-uniform) database

In the case that our states distributed non-uniformly, the state space of the
database can be considered as an arbitrary connected graph other than the
complete graph. Therefore, a straightforward generalization of the relations
(3-22)-(3-24) leads us to consider

$H_{0}=\gamma L,\;\;\ H_{m}=I-|m\rangle\langle m|$ (3-32)

so that

$\tilde{H}(s)=\gamma(1-s)L+s(I-|m\rangle\langle
m|)=aI_{N}-\gamma(1-s)A-s|m\rangle\langle m|,$ (3-33)

where $L$ is the Laplacian of the graph and $\gamma$ is a constant parameter
which is determined in such a way that the search time be minimum (the search
algorithm be optimal). We will consider regular undirected graphs so that the
corresponding adjacency matrices are symmetric, and moreover the Laplacian $L$
and the adjacency matrix $A$ of the graphs differ from each other in only
multiple of identity matrix, i.e., we have $L=DI-A$ with $D$ as the degree of
each vertex. So, the parameter $a$ in (3-33) is given by $a=\gamma D(1-s)+s$.
Since we need the minimum gap between two lowest eigenvalues of the
hamiltonian $\tilde{H}(s)$, so the first term in (3-33) (multiple of identity)
can be dropped.

By choosing $|m\rangle\equiv|\phi_{0}\rangle$ as the starting state for the
Lanczos iteration algorithm, the corresponding Krylov bases are obtained via
the three term recursion relation (2-2). That is we have,

$\tilde{H}(s)|\phi_{0}\rangle=(\gamma(s-1)\alpha_{0}-s)|\phi_{0}\rangle+\gamma(s-1)\beta_{1}|\phi_{1}\rangle,$
$\tilde{H}(s)|\phi_{i}\rangle=\gamma(s-1)\\{\beta_{i}|\phi_{i-1}\rangle+\alpha_{i}|\phi_{i}\rangle+\beta_{i+1}|\phi_{i+1}\rangle\\}\;\
;\;\ i=1,2,\ldots,d.$ (3-34)

In other words, in the krylov bases $|\phi_{i}\rangle$, the Hamiltonian
$\tilde{H}(s)$ is rewritten as

$\tilde{H}(s)=\gamma(s-1)H_{0}-sH_{1}$ (3-35)

where,

$H_{0}\equiv
A=\left(\begin{array}[]{cccccc}\alpha_{0}&\beta_{1}&0&0&\ldots&0\\\
\beta_{1}&\alpha_{1}&\beta_{2}&0&\ldots&0\\\
0&\beta_{2}&\ddots&\ddots&\ddots&\vdots\\\ 0&0&\ddots&\ddots&\ddots&0\\\
\vdots&\vdots&\ddots&\ddots&\ddots&\beta_{d-1}\\\
0&0&\ldots&0&\beta_{d-1}&\alpha_{d-1}\\\ \end{array}\right),\;\
H_{1}=\left(\begin{array}[]{ccccc}1&0&\ldots&\ldots&0\\\ 0&0&0&\ldots&0\\\
\vdots&0&0&\ddots&0\\\ 0&\vdots&\ddots&\ddots&0\\\ 0&0&\ldots&0&0\\\
\end{array}\right).$ (3-36)

Now, using (2-14) and the form of $H_{1}$, one can easily evaluate

$\langle\psi_{j}|H_{1}|\psi_{i}\rangle=\frac{1}{\sqrt{\sum_{l,l^{\prime}=0}^{d}P^{2}_{l}(x_{j})P^{2}_{l^{\prime}}(x_{i})}},$

so that we obtain

$E_{i}^{(1)}=\langle\psi_{i}|H_{1}|\psi_{i}\rangle=\frac{1}{\sum_{l=0}^{d}P^{2}_{l}(x_{i})},$
$E_{i}^{(2)}=\sum_{j;j\neq
i}\frac{|\langle\psi_{j}|H_{1}|\psi_{i}\rangle|^{2}}{E_{i}^{(0)}-E_{j}^{(0)}}=\frac{1}{\gamma(s-1)}\sum_{j;j\neq
i}\frac{1}{(x_{i}-x_{j})\sum_{l,l^{\prime}=0}^{d}P^{2}_{l}(x_{i})P^{2}_{l^{\prime}}(x_{j})}.$

Then, the approximate eigenvalues of $\tilde{H}(s)$ up to second order are
given by

$E_{i}\cong\gamma(s-1)x_{i}-sE_{i}^{(1)}+s^{2}E_{i}^{(2)},$

such that, the energy gap $g(s)$ is given by

$g(s)=E_{1}-E_{0}\cong\gamma(s-1)(x_{1}-x_{0})-s(\frac{1}{\sum_{l=0}^{d}P_{l}^{2}(x_{1})}-\frac{1}{\sum_{l=0}^{d}P_{l}^{2}(x_{0})})+$
$\frac{s^{2}}{\gamma(s-1)}\\{\sum_{j\neq
1}\frac{1}{(x_{1}-x_{j})\sum_{l,l^{\prime}=0}^{d}P_{l}^{2}(x_{1})P_{l}^{\prime
2}(x_{j})}-\sum_{j\neq
0}\frac{1}{(x_{0}-x_{j})\sum_{l,l^{\prime}=0}^{d}P_{l}^{2}(x_{0})P_{l}^{\prime
2}(x_{j})}\\}.$ (3-37)

Denoting the terms in the parentheses of the second term in (3-37) by $A$ and
the terms in the bracket of the last term by $B$, the energy gap is written
as:

$g(s)\cong\gamma(s-1)(x_{1}-x_{0})-sA+\frac{s^{2}}{\gamma(s-1)}B.$ (3-38)

Now, in order to obtain the critical value of $\gamma$ in which the gap $g(s)$
is minimum, we take the derivative of $g(s)$ with respect to $\gamma$ so that
$\frac{\partial g(s)}{\partial\gamma}=0$. Then, one can obtain

$\gamma_{{}_{crit.}}=\frac{s}{1-s}\sqrt{\frac{B}{(x_{1}-x_{0})}},\;\;\ s\neq
0,1.$ (3-39)

By substituting $\gamma_{{}_{crit.}}$ in (3-38), we obtain

$g_{{}_{min}}(s)\cong-s[A+2\sqrt{B(x_{1}-x_{0})}].$ (3-40)

Now, by using (3-26), the search time is evaluated as

$t\cong\int\frac{ds}{\epsilon
s^{2}(A+2\sqrt{B(x_{1}-x_{0})})^{2}}=\frac{1}{\epsilon
s(A+2\sqrt{B(x_{1}-x_{0})})^{2}}.$

By substituting $s=1$, the total search time at which the marked state
$|m\rangle$ is found, is given by

$T\cong\frac{1}{\epsilon(A+2\sqrt{B(x_{1}-x_{0})})^{2}}.$ (3-41)

As the above result indicates, in order to obtain the search time, one needs
to evaluate the terms $A$ and $B$ defined below of (3-37) in terms of the
corresponding graph polynomials $P_{i}(x)$. On the other hand, $A$ and $B$ can
be calculated easily via a systematic computer program for calculating the
corresponding polynomials from the three term recursion relations (2-11).

##  4 Examples

1\. Dihedral group graph
The dihedral group $G=D_{2n}$ is generated by two generators $a$ and $b$ as
follows:

$D_{2n}=<a,b:a^{n}=1,b^{2}=1,b^{-1}ab=a^{-1}>.$

We consider the even $n=2m$, where the odd $n$ can be considered similarly. In
this case, the conjugacy classes of the group, are given by

$C_{0}=\\{e\\},C_{i}=\\{a^{i},a^{-i}\\};i=1,...,m-1,C_{m}=\\{a^{m}\\},C_{m+1}=\\{a^{2j}b;0\leq
j\leq m-1\\}$ $C_{m+2}=\\{a^{2j+1}b;0\leq j\leq m-1\\},$

so we have $m+3$ conjugacy classes. It is well known that the adjacency
matrices defined as $A_{i}=\sum_{g\in C_{i}}R(g)$, are correspond to the
underlying graph of the so-called group association scheme [22, 23] associated
with the group $D_{2n}$, where $R(g)$ is the regular representation of the
element $g$ of the group [24]. Therefore, we have

$A_{0}=I_{2}\otimes I_{n},\;\ A_{i}=I_{2}\otimes(S^{i}+S^{-i}),i=1,2,...,m-1,$
$A_{m}=I_{2}\otimes S^{m},\;\
A_{m+1}=\sigma_{x}\otimes(I_{n}+S^{2}+...+S^{(m-1)}),$
$A_{m+2}=\sigma_{x}\otimes(S+S^{3}+...+S^{2(m-1)})$

where, $S$ is the shift or circulant matrix defined as

$S=\left(\begin{array}[]{ccccc}0&1&0&\ldots&0\\\ 0&0&1&\ddots&0\\\
0&0&0&\ddots&\vdots\\\ \vdots&\ddots&\ddots&\ddots&1\\\
1&0&0&\cdots&0\end{array}\right),$

and $\sigma_{x}$ is the Pauli matrix. In order that we obtain a connected
undirected graph, the adjacency matrices must be symmetrized, i.e.,
$A_{i}=A_{i}^{t}$. To this end, we introduce the new adjacency matrix
$A^{\prime}$ as
$A^{\prime}=A_{m+1}+A_{m+2}=\sigma_{x}\otimes(I+S+...+S^{n-1})$ so that the
Krylov bases are given by

$|\phi_{0}\rangle=\\{|e\rangle\\},$
$|\phi_{1}\rangle=\frac{1}{\sqrt{n}}\\{|b\rangle+|ba\rangle+|ba^{n-1}\rangle\\},$
$|\phi_{2}\rangle=\frac{1}{\sqrt{n-1}}\\{|a\rangle+|a^{2}\rangle+|a^{n-1}\rangle\\}$

and the adjacency matrix is represented as

$A^{\prime}=\left(\begin{array}[]{ccc}0&\sqrt{n}&0\\\
\sqrt{n}&0&\sqrt{n(n-1)}\\\ 0&\sqrt{n(n-1)}&0\\\ \end{array}\right).$

By replacing
$\alpha_{0}=\alpha_{1}=\alpha_{2}=0;\beta_{1}=\sqrt{n},\beta_{2}=\sqrt{n(n-1)}$
in the three term recursion relation (2-13), the corresponding polynomials are
obtained as

$Q_{0}(x)=1,\;\;\ Q_{1}(x)=x,\;\ Q_{2}(x)=x^{2}-n,$ $Q_{3}(x)=x(x^{2}-n^{2}).$

So, the corresponding eigenvalues are given by $x_{0}=-n$, $x_{1}=0$ and
$x_{2}=n$ (the roots of $Q_{3}(x)$). Then by replacing in (3-37), (3-40) and
(3-41) respectively, and considering $n\gg 1$, we obtain

$A=\frac{2n-3}{2n}\cong 1,\;\;\ B=\frac{4n-3}{4n^{3}}\cong\frac{1}{2n^{2}},$
$\gamma_{crit.}\cong\frac{s}{1-s}\frac{\sqrt{4n-3}}{2n^{2}},\;\;\
g_{min}(s)\cong s(\frac{2n+2\sqrt{4n-3}-3}{2n}),$
$T\cong\frac{4n^{2}}{\varepsilon(2n+4\sqrt{n})^{2}}.$

2\. m-partite Graph
An $m$-partite graph (i.e., a set of graph vertices decomposed into $m$
disjoint sets such that no two graph vertices within the same set are
adjacent) such that every pair of graph vertices in the $m$ sets are adjacent.
Considering an $m$-partite graph which has $n$ vertices in each of its
disjoint sets, the corresponding adjacency matrix is given by

$A=K_{m}\otimes J_{n},$

where, $K_{m}$ is the adjacency matrix of the complete graph with $m$ vertices
and $J_{n}$ is $n\times n$ all one matrix. Now by using the Lanczos iteration
algorithm, the Krylov bases are obtained as

$|\phi_{0}\rangle=|1\rangle,$
$|\phi_{1}\rangle=\frac{1}{\sqrt{n(m-1)}}(|n+1\rangle+|n+2\rangle+\cdots+|n(m-1)\rangle),$
$|\phi_{2}\rangle=\frac{1}{\sqrt{(n-1)}}(|2\rangle+|3\rangle+\cdots+|n\rangle)$

where, the adjacency matrix is reduced to the following $3\times 3$
tridiagonal form

$A=\left(\begin{array}[]{ccc}0&\sqrt{n(m-1)}&0\\\
\sqrt{n(m-1)}&n(m-2)&\sqrt{n(n-1)(m-1)}\\\ 0&\sqrt{n(n-1)(m-1)}&0\\\
\end{array}\right).$

Now, as illustrated in the previous example in detail, by replacing
$\alpha_{0}=\alpha_{2}=0,\alpha_{1}=n(m-2)$ and
$\beta_{1}=\sqrt{n(m-1)},\beta_{2}=\sqrt{n(m-1)(n-1)}$ in three term recursion
relations (2-13), and evaluating the polynomials $P_{i}(x)$ for $i=0,1,2$ and
$Q_{3}(x)$, one can obtain

$x_{0}=-n,\;\ x_{1}=0,\;\ x_{2}=n(m-1)$

and

$A=\frac{m(n-1)-1}{mn},\;\;\;B=\frac{1-n}{n}[\frac{1-(m-1)^{2}}{n^{2}m(m-1)}]+\frac{1}{nm}[\frac{m^{2}n-2m+1}{n^{2}m^{2}(m-1)}],$

where for $n\gg 1,m\gg 1$, $A$ and $B$ are approximately as

$A\cong 1,\;\;\ B\cong\frac{1}{n^{2}}.$

Then, by using (3-39), (3-40) and (3-41), one can obtain

$\gamma_{crit.}\cong\frac{s}{1-s}\sqrt{\frac{1}{n^{3}(m-1)}},$
$g_{min}(s)\cong s(1+2\sqrt{\frac{m-1}{n}}),$

and

$T\cong\frac{1}{\varepsilon(1+2\sqrt{\frac{m-1}{n}})^{2}},$

respectively.

3\. Crown Graph
A crown graph on $2n$ vertices is an undirected graph with two sets of
vertices $u_{i}$ and $v_{i}$ and with an edge from $u_{i}$ to $v_{j}$ whenever
$i\neq j$. The adjacency matrix of this graph is given by:

$A=K_{n}\otimes\sigma_{x}$

where, $K_{n}$ is the adjacency matrix of the complete graph with $n$ vertices
and $\sigma_{x}$ is the Pauli matrix. Then, the Krylov bases are given by

$|\phi_{0}\rangle=|1\rangle,$
$|\phi_{1}\rangle=\frac{1}{\sqrt{n-1}}(|n+1\rangle+|n+2\rangle+\cdots+|2n-1\rangle),$
$|\phi_{2}\rangle=\frac{1}{\sqrt{n-1}}(|2\rangle+|3\rangle+\cdots+|n\rangle),$
$|\phi_{3}\rangle=|2n\rangle.$

In the above bases, the adjacency matrix is represented as

$A=\left(\begin{array}[]{cccc}0&\sqrt{n-1}&0&0\\\ \sqrt{n-1}&0&n-2&0\\\
0&n-2&0&\sqrt{n-1}\\\ 0&0&\sqrt{n-1}&0\\\ \end{array}\right).$

Again, by using (2-13) and (3-37) one can easily calculate the roots $x_{i}$
and the quantities $A$ and $B$ as follows:

$x_{0}=-(n-1),\;\ x_{1}=-1,\;\ x_{2}=1,\;\ x_{3}=(n-1),$
$A\cong\frac{n-2}{2n},\;\;\;B\cong\frac{(n-1)^{2}}{n^{2}}.$

Now, by using (3-39), (3-40) and (3-41), one can obtain

$\gamma_{crit.}\cong\frac{s}{1-s}\sqrt{\frac{n-1}{n^{2}}},$ $g_{min}(s)\cong
s(1+2\sqrt{\frac{(n-2)(n-1)^{2}}{n^{2}}}),$
$T\cong\frac{1}{\varepsilon(1+2\sqrt{\frac{(n-2)(n-1)^{2}}{n^{2}}})^{2}}\cong\frac{1}{\varepsilon
n}.$

##  5 Conclusion

Based on the local adiabatic evolution of the Hamiltonian and some techniques
such as Krylov subspace projection methods, Lanczos iteration algorithm and
spectral distribution methods, a new procedure for investigating quantum
search in the state space of a graph was introduced, where an approximate
analytical formula for calculating the corresponding minimum energy gap and
the total search time was given.

## References

  * [1] L. K. Grover, Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett. 79, 325, 1997.
  * [2] A. Ambainis, Quantum search algorithms, SIGACT News, 35 22-35, 2004. Also quant-ph/0504012.
  * [3] S. Aaronson and A. Ambainis, Quantum search of spatial regions, quant-ph/0303041, Proc. 44th IEEE Symposium on Foundations of Computer Science, 200, 2003.
  * [4] Andrew M. Childs and J. Goldstone, Phys. Rev. A 70, 022314, 2004.
  * [5] E. Farhi and S. Gutmann, Analog analogue of a digital quantum computation, Phys. Rev. A 57, 2403, 1998.
  * [6] E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Quantum computation by adiabatic evolution, quant- ph/0001106.
  * [7] A. M. Childs, E. Deotto, E. Farhi, J. Goldstone, S. Gutmann, and A. J. Landahl, Quantum search by measurement, Phys. Rev. A 66, 032314, 2002.
  * [8] A. Childs, E. Deotto, R. Cleve, E. Farhi, S. Gutmann, D. Spielman , in Proc. $35$th Ann. Symp. Theory of Computing (ACM Press), 59, 2003\.
  * [9] J. Roland and N. J. Cerf, Phys. Rev. A 65, 042308, 2002.
  * [10] A. T. Rezakhani, A. K. Pimachev and D. A. Lidar, Phys. Rev. A 82, 052305, 2010.
  * [11] B. Parlett, The Symmetric Eigenvalue Problem, Prentice-Hall Inc., Englewood Cliffs, N.J., 1980.
  * [12] J. Wilkkinson, The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, 1965.
  * [13] L. Trefethen and D. Bau, Numerical Linear Algebra, Society for Industrial and Applied Mathematics (SIMA), Philadelphia, PA. 1997.
  * [14] J. Cullum and R. Willoughby, L$\acute{a}$nczos Algorithems for Large Symmetric Eigenvalue Computations, Vol. I, Birkh$\ddot{a}$user Boston Inc, Boston, MA, 1985, Theory.
  * [15] M.A. Jafarizadeh, R. Sufiani, S. Salimi and S. Jafarizadeh, Eur. Phys. J. B 59, 199 216, 2007.
  * [16] J. A. Shohat, and J. D. Tamarkin, The Problem of Moments, American Mathematical Society, Providence, RI, 1943.
  * [17] P.D.Hislop and I.M.Sigal, Introduction to spectral theory: With applications to schrodinger operators, 1995.
  * [18] T. S. Chihara, An Introduction to Orthogonal Polynomials, Gordon and Breach, Science Publishers Inc, 1978.
  * [19] Z. Alipour, M.A. Jafarizadeh, N. Fooladi and R. Sufiani, International Journal of Modern Physics E, 1465-1476, 2011.
  * [20] L.I. Schiff, Quantum Mechanics, McGraw-Hill, Singapore, 1955.
  * [21] M. A. Jafarizadeh, S. Salimi, Annals of physics, 322, 1005-1033, 2007\.
  * [22] R. A. Bailey, Association Schemes: Designed Experiments, Algebra and Combinatorics, Cambridge University Press, Cambridge, 2004\.
  * [23] M. A. Jafarizadeh, R. Sufiani, S. F. Taghavi and E. Barati, Journal of Statistical Mechanics, 04004, 2009.
  * [24] Gordon James and Martin Liebeck, Representations and characters of groups, Cambridge University Press, Cambridge, 1993.


#  ACL-IJCNLP 2021 Findings
RiddleSense: Reasoning about Riddle Questions
Featuring Linguistic Creativity and Commonsense Knowledge

Bill Yuchen Lin Ziyi Wu Yichi Yang Dong-Ho Lee Xiang Ren
<EMAIL_ADDRESS>
Department of Computer Science and Information Sciences Institute,
University of Southern California

###### Abstract

Question: I have five fingers but I am not alive. What am I? Answer: a glove.

Answering such a riddle-style question is a challenging cognitive process, in
that it requires complex commonsense reasoning abilities, an understanding of
figurative language, and counterfactual reasoning skills, which are all
important abilities for advanced natural language understanding (NLU).
However, there is currently no dataset aiming to test these abilities. In this
paper, we present RiddleSense111https://inklab.usc.edu/RiddleSense/, a new
multiple-choice question answering task, which comes with the first large
dataset (5.7k examples) for answering riddle-style commonsense questions. We
systematically evaluate a wide range of models over the RiddleSense challenge,
and point out that there is a large gap between the best-supervised model and
human performance — suggesting intriguing future research in the direction of
higher-order commonsense reasoning and linguistic creativity towards building
advanced NLU systems.

##  1 Introduction

> “ The essence of a riddle is to express true facts under impossible
> combinations.”
>
> — Aristotle, Poetics (350 BCE)

A riddle is a puzzling question about concepts in our everyday life. For
example, a riddle might ask “My life can be measured in hours. I serve by
being devoured. Thin, I am quick. Fat, I am slow. Wind is my foe. What am I?”
The correct answer “candle,” is reached by considering a collection of
commonsense knowledge: a candle can be lit and burns for a few hours; a
candle’s life depends upon its diameter; wind can extinguish candles, etc.

Figure 1:  The top example is a trivial commonsense question from the
CommonsenseQA Talmor et al. (2019) dataset. The two bottom examples are from
our proposed RiddleSense challenge. The right-bottom question is a descriptive
riddle that implies multiple commonsense facts about candle, and it needs
understanding of figurative language such as metaphor; The left-bottom one
additionally needs counterfactual reasoning ability to address the ‘but-no’
cues. These riddle-style commonsense questions require NLU systems to have
higher-order reasoning skills with the understanding of creative language use.

It is believed that the riddle is one of the earliest forms of oral
literature, which can be seen as a formulation of thoughts about common sense,
a mode of association between everyday concepts, and a metaphor as higher-
order use of natural language Hirsch (2014). Aristotle stated in his Rhetoric
(335-330 BCE) that good riddles generally provide satisfactory metaphors for
rethinking common concepts in our daily life. He also pointed out in the
Poetics (350 BCE): “the essence of a riddle is to express true facts under
impossible combinations,” which suggests that solving riddles is a nontrivial
reasoning task.

Answering riddles is indeed a challenging cognitive process as it requires
complex commonsense reasoning skills. A riddle can describe multiple pieces of
commonsense knowledge with figurative devices such as metaphor and
personification (e.g., “wind is my foe $\xrightarrow[]{}$ extinguish”).
Moreover, counterfactual thinking is also necessary for answering many riddles
such as “what can you hold in your left hand but not in your right hand?
$\xrightarrow[]{}$ your right elbow.” These riddles with ‘but-no’ cues require
that models use counterfactual reasoning ability to consider possible
solutions for situations or objects that are seemingly impossible at face
value. This reporting bias Gordon and Van Durme (2013) makes riddles a more
difficult type of commonsense question for pretrained language models to learn
and reason. In contrast, superficial commonsense questions such as “What home
entertainment equipment requires cable?” in CommonsenseQA Talmor et al. (2019)
are more straightforward and explicitly stated. We illustrate this comparison
in Figure 1.

In this paper, we introduce the RiddleSense challenge to study the task of
answering riddle-style commonsense questions222We use “riddle” and “riddle-
style commonsense question” interchangeably in this paper. requiring
creativity, counterfactual thinking and complex commonsense reasoning.
RiddleSense is presented as a multiple-choice question answering task where a
model selects one of five answer choices to a given riddle question as its
predicted answer, as shown in Fig. 1. We construct the dataset by first
crawling from several free websites featuring large collections of human-
written riddles and then aggregating, verifying, and correcting these examples
using a combination of human rating and NLP tools to create a dataset
consisting of 5.7k high-quality examples. Finally, we use Amazon Mechanical
Turk to crowdsource quality distractors to create a challenging benchmark. We
show that our riddle questions are more challenging than CommonsenseQA by
analyzing graph-based statistics over ConceptNet Speer et al. (2017), a large
knowledge graph for common sense reasoning.

Recent studies have demonstrated that fine-tuning large pretrained language
models, such as BERT Devlin et al. (2019a), RoBERTa, and ALBERT Lan et al.
(2020), can achieve strong results on current commonsense reasoning
benchmarks. Developed on top of these language models, graph-based language
reasoning models such as KagNet Lin et al. (2019) and MHGRN Feng et al. (2020)
show superior performance. Most recently, UnifiedQA Khashabi et al. (2020)
proposes to unify different QA tasks and train a text-to-text model for
learning from all of them, which achieves state-of-the-art performance on many
commonsense benchmarks.

To provide a comprehensive benchmarking analysis, we systematically compare
the above methods. Our experiments reveal that while humans achieve 91.33%
accuracy on riddlesense, the best language models can only achieve 68.80%
accuracy, suggesting that there is still much room for improvement in the
field of solutions to complex commonsense reasoning questions with language
models. We believe the proposed RiddleSense challenge suggests productive
future directions for machine commonsense reasoning as well as the
understanding of higher-order and creative use of natural language.

##  2 Construction of RiddleSense

In this section, we first present our pipeline for collecting the RiddleSense
dataset, including the details of data cleaning. We introduce how we design a
crowd-sourcing protocol for annotating quality distractors to turn riddle-
solving into a multiple-choice question answering task.

###  2.1 Riddle Crawling and Cleaning

We write web crawlers for collecting a large number (approximately 10,000) of
riddles and their answers from public riddle websites, such as brainzilla.com,
riddlewot.com, etc. As the crawled data contain much noise such as
inconsistent answer format and misspelled words, we process riddles through
careful data cleaning as well as human verification. First, we use an open-
source tool for detecting typos333github.com/phatpiglet/autocorrect and then
refine the sentences. Then we continuously sample (riddle, answer) pairs and
recognize errors, for which we iteratively improve our program with a set of
conditions to filter out noisy examples that are not readable or have
ambiguous answers. Also, we merge the riddles from different sources while
removing duplicate riddle questions with similar answers. For detecting
duplicate riddles with minor word changes, we use SentenceBERT Reimers and
Gurevych (2019) to find clusters with high cosine similarities.

###  2.2 Distractor Collection from AMT

We consider a multi-choice question answering format rather than the open-
ended format, as it is easier to meaningfully compare the performance of
different models in a more controlled manner — there is a limited range of of
options. For such a dataset, given a riddle-style question and 5 answer
options, the model should select the best one as the predicted answer. This
format offers a straightforward and fair evaluation metric – accuracy, which
is the metric adopted by many popular commonsense reasoning benchmarks such as
CommonsenseQA, ARC Clark et al. (2018), and OpenbookQA Mihaylov et al. (2018).

High-quality distractors are essential for multiple-choice question answering
tasks as they can ensure that the dataset is both clean and challenging — the
distractors are neither too similar nor too distant from the correct answer.
We thus design a protocol to collect quality distractors from human annotators
via Amazon Mechanical Turk444https://www.mturk.com/ based on a pool of
candidate distractors.

#### Candidate Distractor Pool

We use $Q$ to denote the concepts that are mentioned in the question, and $a$
to denote the concept in the answer555If there are multiple concepts, we pick
the one with the least network degrees as they tend to be more important.. We
then first get all two-hop neighbors in the ConceptNet of $a$ and one-hop
neighbors of each $c\in Q$ respectively:

$\displaystyle A$ $\displaystyle=\\{x|(x,r_{i},y),(y,r_{j},a)\\}$
$\displaystyle B$ $\displaystyle=\\{x|(x,r_{k},c),\forall c\in Q\\}$
$\displaystyle~{}~{}~{}~{}D=A\cap B,$

where $r_{i/j/k}$ is a binary relation in the ConceptNet such as HasProperty.
The final intersection, $D$, is thus the pool of distractor candidates. We
further use WordNet Miller (1992) to filter out concepts that have either too
low or too high Wu-Palmer similarity666We use 0.5 as a threshold which is
effective as expected.. We argue that such sampled distractors are
semantically relevant to both questions and answers, and are also closer to
answers in the WordNet taxonomy. Thus, they are more likely to serve as ideal
distractors in a multiple-choice question answering task.

#### AMT Crowd-sourcing

We design a three-stage annotation protocol:

  * •

S1) Sanity Check. We show a question and 3 choices where only 1 choice is
correct and the other 2 are randomly sampled concepts from the full vocabulary
of ConceptNet. Only when the workers pass this sanity check, their following
annotations will be considered, so we can avoid noise from random workers.

  * •

S2) Candidate Selection. As it is difficult to control and verify the quality
of distractors from crowd workers, we first sample concepts from ConceptNet,
which are relevant to both question concepts and answer concepts, forming a
set of candidate distractors $D$ for annotators to choose from. Workers are
required to select at least 5 concepts that they think are good distractors to
the question. There are at least 3 different workers for each question and we
take the candidates which are selected by at least two different workers to
make sure the selected distractors are indeed meaningful.

  * •

S3) Open Distractor Collection. We also ask master workers on AMT to write at
least one more distractor based on the question context. This stage is
important because sometimes the candidate pool contains fewer candidates of
good quality and the human-written distractors are usually better than the
ones in the candidate pool. We thus give extra bonus credits to encourage
annotators to write more quality distractors.

| CSQA | RS
---|---|---
# All Examples | 12,102 | 5,715
# Train Examples | 9,741 | 3,510
# Validation Examples | 1,221 | 1,021
# Test Examples | 1,140 | 1,184
Average Question Length | 15.06 | 24.04
% Long Qs ($>$20 tokens) | 16.5% | 47.3%
Distinct Question Words | 6,822 | 7,110
Distinct Choice Words | 7,044 | 9,912
Avg PLL of Qs | -34.41 | -53.98
QA-NLI Conflict | 12.7% | 39.6%
QA-NLI Neutral | 71.6% | 44.9%
QA-NLI Entailment | 15.7% | 15.5%

Table 1: Key statistics of the RiddleSense dataset (v1.1) vs the CommonsenseQA
(CSQA) dataset.

(a) Length of Q-A Paths (b) Mean Length (c) Min Length (d) Max Length

Figure 2: The Q-A paths serve as estimation of underlying reasoning chains.
Fig. (a) illustrates how to compute mean/min/max of the Q-A paths:
$\\{q_{1},q_{2},q_{3}\\}$ are three concepts mentioned in the question, and
$a$ is the answer concept. $L_{k}$ is the length of the shortest path between
$q_{k}$ and $a$ over ConceptNet; min/max/mean are computed over
$\\{L_{1},L_{2},L_{3}\\}$ as three aspects to measure the overall difficulty.
Fig. (b), (c), and (d) show that generally  RiddleSense has a longer question-
answer path than  CommonsenseQA , thus being harder to reason.

##  3 Data Analysis of RiddleSense

In this section, we first report the key statistics of the proposed
RiddleSense dataset, then we compare it to CommonsenseQA Talmor et al. (2019)
from two major angles: the distribution of the lengths of Q-A paths and the
types of reasoning chains, which serve as an effective proxy to analyze the
differences between the two datasets.

Input: Knowledge graph $KG=(V,E)$, riddle question $Q$, riddle answer $A$

Output: $minPathLength$, $maxPathLength$, $meanPathLength$

1

2$QC\leftarrow$ extractConcept(_$Q$_)

3 $AC\leftarrow$ extractConcept(_$A$_)

4 $ac\leftarrow v\in AC$ with smallest deg(_$G,v$_)

5 $l\leftarrow$ []

6 foreach  _$qc\in QC$_ do

7 $path\leftarrow$ shortestPathLen(_KG, qc, ac_)

8 if  _$path\neq None$_ then

9 $l$.append(_$path$_)

10$minPathLength\leftarrow$ min ($l$)

11 $maxPathLength\leftarrow$ max ($l$)

$meanPathLength\leftarrow$ mean ($l$)

Algorithm 1 Get statistics of QA paths.

CommonsenseQA (CSQA)
---
1-hop (14.0%) | 2-hop (34.4%) | 3-hop (41.5%) | 4-hop (9.5%)
AtLoc (4.8%) |  Related-Related (8.3%) |  Related-Related-Related (4.1%) |  Related $\times$ 4 (0.4%)
Related (3.4%) | Related-AtLoc (4.5%) | Related-Related-AtLoc (2.7%) | Related $\times$ 3 -AtLoc (0.3%)
Causes (1.1%) | Related-Antonym (1.8%) | Related-AtLoc-1-AtLoc (1.4%) | Related-Related-AtLoc-1-AtLoc (0.3%)
Antonym (0.9%) | Related-IsA-1 (1.3%) | Related-Related-Antonym (1.3%) | Related $\times$ 3 -Antonym (0.2%)
Capableof (0.8%) | Related-AtLoc-1 (0.9%) | Related-Related-CapableOf (1.3%) | Related$\times$2-SubEvent-1-Cause (0.1%)
… | … | … | …
$\rho=\frac{3.4}{4.8}=0.7$ | $\rho=\frac{8.3}{4.5}=1.8$ | $\rho=\frac{4.1}{2.7}=1.5$ | $\rho=\frac{0.4}{0.3}=1.3$
RiddleSense (RS)
1-hop (4.6%) | 2-hop (31.6%) | 3-hop (47.8%) | 4-hop (14.0%)
Related (3.1%) |  Related-Related (13.1%) |  Related-Related-Related (10.6%) |  Related $\times$ 4 (1.8%)
Antonym (0.4%) | Related-Antonym (2.1%) | Related-Related-IsA-1 (2.6%) | Antonym-Related$\times$3 (0.4%)
IsA-1 (0.3%) | Related-IsA-1 (2.0%) | Related-Related-Antonym (1.6%) | Related$\times$3 -IsA-1 (0.3%)
PartOf (0.1%) | Related-AtLoc-1 (1.3%) | Related-Antonym-Related (1.5%) | Related$\times$2-IsA-1-Related (0.3%)
AtLoc-1 (0.1%) | Antonym-Related (0.8%) | Antonym-Related-Related (1.5%) | Related$\times$2-Antonym-Related (0.3%)
… | … | … | …
$\rho=\frac{3.1}{0.4}=7.8$ | $\rho=\frac{13.1}{2.1}=6.2$ | $\rho=\frac{10.6}{2.6}=4.1$ | $\rho=\frac{1.8}{0.4}=4.5$

Table 2: The top-5 most frequent types of reasoning chains in CSQA and RS
datasets, grouped by their length $k=\\{1,2,3,4\\}$. The  implicit-ratio
$\rho$ is defined as the ratio of the implicit reasoning types (i.e.,
Related$\times k$ ) over the most frequent types with at least one explicit
relation (e.g., AtLoc) of the same length $k$.

###  3.1 Key Statistics

Table 1 presents the key statistics of RiddleSense (RS) and the comparisons
with CommonsenseQA (CSQA) which is the most similar benchmark to ours.
Although the size of RS is smaller than CSQA, we argue that RS is
complementary to the CSQA dataset and introduces novel challenges for the
commonsense reasoning community. As they share the same format, we can test
different methods by training on either CSQA-only, RS-only, or the
concatenation of CSQA and RS, as we show later in Section 4.

Moreover, there is a greater number of long questions (i.e., containing more
than 20 words) in RS than in CSQA. Additionally, we find that RS questions
have a lower normalized pseudo-likelihood (PLL) Salazar et al. (2020), a proxy
of estimating sentence probability, suggesting that RS questions are more
puzzling (i.e., the words are less frequently co-occurring). We also use a
RoBERTa model fine-tuned on MNLI Williams et al. (2018) to perform natural
language inference between CSQA/RS questions and their answers. There is a
much greater proportion of questions in RS that have conflicting relations
with their correct answers than compared to CSQA. This is indicative of RS’s
complexity due to the self-contradictory and perplexing nature of riddles.

Interestingly, we also find that although there are about twice as many
examples in CSQA as RS, there are more distinct words in the questions and
answer choices of RS than CSQA, suggesting that RS covers more diverse topics
than CSQA.

###  3.2 Distribution of the Lengths of Q-A Paths

Our main intuition is that the shortest paths between question concepts and
the answer concepts can approximate the underlying reasoning chains, which are
hidden and difficult to label. To understand the difference between CSQA and
RS in terms of their reasoning chains, we use Q-A paths over ConceptNet as a
proxy. For a riddle question, a set of Q-A path lengths are the lengths of the
shortest paths between every question concept and the answer concept, i.e.,
shortestPathLen(KG, qc, ac) in Alg. 1. For a question-answer pair, we first
extract the concepts mentioned in the question and the answer respectively
(extractConcept() in Algorithm 1), following the steps of Lin et al. (2019)
and Feng et al. (2020). If there are three question concepts
$\\{q_{1},q_{2},q_{3}\\}$ and an answer concept $a$, we denote their shortest
path lengths as $\\{L_{1},L_{2},L_{3}\\}$. Finally, we compute the
min/max/mean over them for a comprehensive understanding of the approximated
difficulty of this riddle — a greater value indicates a more challenging
example.

As shown in Figure 2 (b), we can see that RS has longer Q-A paths as
underlying reasoning chains. In addition, we can see that RS generally has
longer chains, particularly the min of CSQA is $1$-hop for more than 80% of
examples. On the other hand, only about 30% of RS examples have 1-hop minimum
Q-A paths, while about 50% of the examples have 2-hop min Q-A paths. The
distribution over the maximum in Figure 2 (d) also shows that RS tends to have
longer maximum paths than CSQA. We also show the percentage of all Q-A paths
of different length as part of Table 2, and we can see that RS has longer
paths in general (e.g., CSQA = 14.0% vs. RS = 4.6% in 1-hop).

###  3.3 Relational Types of Reasoning Paths

In addition to the analysis on path length, we also show that the relation
types of Q-A paths for RS and CSQA have clear differences, as shown in Table
2. The types of reasoning chains in RS rely more on a special relation in
ConceptNet — Related, which is relatively more implicit and can not be
grounded to a specific, explicit relation such as AtLoc (e.g., <wind, Related,
air> vs. <lamp, AtLoc, table>). The most frequent relation between question
concepts and answer concepts in CSQA is the AtLoc relation (4.8%), however, it
is Related (3.1%) in RS. We define implicit-ratio for $k$-hop paths,
$\rho_{k}=\frac{\%(\texttt{Related}\times k)}{\%(E_{k})}$, where $E_{k}$ is
the most frequent type of chains with at least one explicit relation of length
$k$. In RS, $\rho_{k}$ is around $4.1\sim 7.8$, while it is about $0.7\sim
1.8$ for CSQA. Thus, we conclude that the dominant reasoning chains in RS are
much more implicit, and consequently RS is more challenging to reason with
using commonsense knowledge resources like ConceptNet.

Figure 3: Three types of baseline methods: 1) fine-tuning pre-trained LMs, 2)
incorporating graph-based reasoner, 3) fine-tuning a unified text-to-text LM.

##  4 Experiments

We first introduce three types of popular baseline methods for commonsense
reasoning (Section 4.1), then we present our main experimental results with
analysis (Section 4.2), and finally show case studies for error analysis
(Section 4.3).

###  4.1 Baseline Methods

Given a riddle question $q$, there are 5 different choices
$\\{c_{1},\dots,c_{5}\\}$, where only one of them is the correct choice and
the others are distractors. The model needs to rank all choices and select the
best one as the final answer. There are three major types of models for
commonsense reasoning tasks in this format: 1) fine-tuning pretrained language
models, 2) incorporating relevant knowledge graphs for reasoning, 3) fine-
tuning a unified text-to-text QA model, as shown in Figure 3.

#### Fine-tuning Pre-trained LMs

As we seek to investigate how well current NLU models can perform in higher-
order commonsense reasoning, we first experiment with a typical set of large
pretrained language models such as BERT Devlin et al. (2019b), RoBERTa Liu et
al. (2019), and ALBERT Lan et al. (2020). We concatenate the question with
each choice, using [SEP] as the separator, thus forming a statement. Then, we
fine-tune any pretrained LMs like BERT to use their [CLS] token embeddings to
predict a score for each statement. Then, a set of five scores about an
example will be fed to SoftMax to optimize for maximizing the score of the
correct choice.

#### LMs + Graph Reasoning Modules

KagNet Lin et al. (2019) and MHGRN Feng et al. (2020) are two typical graph-
based language reasoning models. They both extract a schema graph from
ConceptNet, i.e., a subgraph of ConceptNet consisting of Q-A paths in Figure
2, by incorporating them with a graph encoding module. They finally fuse the
external commonsense knowledge with a text encoder (e.g., a pretrained LM).
KagNet uses heuristics to prune irrelevant paths and then encode them with
path-based LSTM and hierarchical attention to select the most important paths
for improving commonsense reasoning. In contrast, the recent MHGRN explicitly
encodes multi-hop paths at scale using graph networks with relational
attention, improving efficiency and performance over KagNet and other models.
A unique merit of such graph-based models is their interpretibility due to the
neural attention over the symbolic structures of KGs.

#### Fine-Tuning a Text-to-Text QA Model

UnifiedQA Khashabi et al. (2020), the state-of-the-art multiple-choice QA
model, simply concatenates the question with all answer candidates as a single
input sequence to a T5 Raffel et al. (2020) model for learning to generate the
correct choice as extracting a span from the input. Apart from the multiple-
choice QA format, it is also trained with other QA task formats so that it can
benefit from many other QA datasets (including CSQA) via sharing the model
parameters.

#### Human Evaluation

We invite three native English speakers who study computer science to solve
100 riddle examples sampled from the test set. They achieved an average
accuracy of 91.3%.

Models $\downarrow$ Training Data $\rightarrow$ | Train = CSQA | Train = RiddleSense | Train = RS+CSQA
---|---|---|---
RiddleSense-Split $\rightarrow$ | Dev | Test | Dev | Test | Dev | Test
Random Guess | 20.0 | 20.0 | 20.0 | 20.0 | 20.0 | 20.0
BERT-Base Devlin et al. (2019a) | 33.59 | 34.61 | 54.16 | 42.43 | 56.22 | 47.67
BERT-Large Devlin et al. (2019a) | 36.14 | 39.10 | 55.24 | 45.09 | 57.69 | 54.91
RoBERTa-Large Liu et al. (2019) | 43.68 | 47.42 | 60.72 | 52.58 | 66.11 | 59.82
ALBERT-XXL Lan et al. (2020) | 51.03 | 51.00 | 66.99 | 60.65 | 71.50 | 67.30
KagNet (RoBERTa-L) Lin et al. (2019) | 42.66 | 48.24 | 61.77 | 53.72 | 66.55 | 59.72
MHGRN (RoBERTa-L) Feng et al. (2020) | 46.83 | 49.65 | 63.27 | 54.49 | 66.90 | 63.73
MHGRN (ALBERT-XXL) Feng et al. (2020) | 50.89 | 50.21 | 66.27 | 59.93 | 70.81 | 66.81
UnifiedQA (T5-Large) Khashabi et al. (2020) | 28.50 | 37.27 | 56.21 | 56.40 | 58.17 | 56.57
UnifiedQA (T5-3B) Khashabi et al. (2020) | 37.32 | 50.25 | 67.38 | 66.06 | 68.26 | 68.80
Human Performance | - | 91.33 | - | 91.33 | - | 91.33

Table 3: Benchmark performance over the dev and test set of RiddleSense .
Figure 4: The curve of dev accuracy using different percentage of the RS-
training data, respectively for RoBERTa-Large and ALBERT-XXL.

###  4.2 Results and Analysis

We show the main results of the experiments in Table 3. There are 3 settings
according to the different training data options: 1) the training data of
CSQA, 2) the training data of RS, and 3) the concatenation of both RS and
CSQA, while all experiments are validated over the dev set of RS. However, as
the public UnifiedQA checkpoints were already trained on CSQA (together with
many other QA datasets), we directly use them for inference over RS in the
first setting (i.e., “Train=CSQA”). This also suggests that the performance of
UnifiedQA models in 2nd setting should be better than others although they all
are fine-tuned on RS’s training data only.

We can see that larger pretrained language understanding models always gain
better performance, ranging from BERT-base to Albert-XXL, which gets the best
performance in this group of baselines (67.30%). This matches their
performance comparisions on CSQA and other benchmark datasets as well,
suggesting that a better pre-trained language model can be also identified by
RiddleSense as well. Interestingly, we find that ALBERT-XXL is so powerful
that it can generalize from training on CSQA only but achieve comparable
results with RoBERTa-Large that is trained over RS (i.e., 51.0% vs. 52.6%).
However, if we look at the curve of dev accuracy when using different
percentage of the RS-train data (setting 2) in Figure 4, we can see that
RoBERTa-Large can generally outperform ALBERTA-XXL when using less than 60%
data for fine-tuning.

Moreover, we find that the KG-enhanced models, KagNet and MHGRN, using
RoBERTa-Large (RB-L) as the encoder, perform better than vanilla RB-L.
Although the Q-A paths over ConceptNet have more implicit paths (e.g.,
Related$\times k$), some paths can still be beneficial. For example,

$\textit{wind}\xleftrightarrow{~{}\texttt{Related}~{}}\textit{blow}\xleftrightarrow{~{}\texttt{Related}~{}}\textit{candle},$

can still help reason about the riddle “… Wind is my foe. What am I?” to the
answer “candle.”

The fusion of ConceptNet also improves in the situation when only training
with CSQA data using RoBERTa-Large. However, the improvement of KagNet is
negative, which is unexpected. We conjecture that this is because the
extracted subgraphs from the ConceptNet does not guarantee the reasoning path
from question concepts to answer concepts, while the training phase forces
models to learn to reason over those graphs, yielding a possibly harmful
impact. Additionally, we find that MHGRN with ALBERT-XXL also results in a
worse performance, unlike using RoBERTa-Large. We believe this may be related
to the specific design of ALBERT, which reuses model parameters for multiple
layers, and thus it could be a problem when fused with another learnable
module (e.g., a graph network in MHGRN).

Fine-tuning UnifiedQA with T5-3B achieves the best performance, which is also
the case for CSQA in their leaderboard. This is expected for two reasons: 1)
UnifiedQA has been trained over multiple other QA datasets, which increases
its generalization ability, 2) UnifiedQA considers all choices together at a
time and thus can better compare different choices with self-attention
mechanism of Transformer Vaswani et al. (2017).

Figure 5: Case studies of the error by UnifiedQA-3B model on the test set of
RiddleSense.

###  4.3 Error Analysis and Future Directions

We show a few examples that are mistakenly predicted by the UnifiedQA-3B model
in Figure 5. From these concrete cases, we can see that even the best model
cannot solve riddles that can be trivial to humans, especially when there are
metaphors and/or counterfactual situations. We argue that future research
should aim to address the creative use of language in commonsense reasoning
and general understanding of language, as creativity is a critical feature of
natural language. We list several promising directions as follows.

First of all, we should mine (semi-)structured knowledge of metaphors, so that
concepts can connect via metaphorical links (e.g., “tail” $\rightarrow$
“thread”). Second, to prevent false inferences, we need more complete, precise
commonsense knowledge of concepts. For example, in Figure 5, a model should
know a chair only has exactly four legs instead of hundreds Lin et al.
(2020a); ink can be black or red, but it won’t change over time. However,
current KGs only have (leg, PartOf, chair) and (ink, HasProperty, black/red).
In addition, the reasoning methods should incorporate more symbolic logic
rules, so that the multi-hop conditions and counterfactual “but-no” negations
will be handled better. Finally, we think the graph-augmented methods should
be improved to compare multiple options in a schema graph, e.g., QA-GNN
Yasunaga et al. (2021). Both KagNet and MHGRN consider only a single option at
a time which prevents them from effectively reasoning about the subtle
differences between options.

##  5 Related Work

### Benchmarking Machine Common Sense

The prior works on building commonsense reasoning benchmarks touch different
aspects of commonsense reasoning: SWAG Zellers et al. (2018), HellaSWAG
Zellers et al. (2019), CODAH Chen et al. (2019), aNLI Bhagavatula et al.
(2020) for situation-based reasoning; Physical IQA Bisk et al. (2020) on
physical knowledge; Social IQA Sap et al. (2019) on social psychology
knowledge; LocatedNearRE Xu et al. (2018) on mining spatial commonsense
knowledge; DoQ Elazar et al. (2019) and NumerSense Lin et al. (2020a) on
numerical common sense; CommonGen Lin et al. (2020b) for generative
commonsense reasoning, and many others; OpenCSR Lin et al. (2021) and ProtoQA
Boratko et al. (2020) aim to test commonsense reasoning ability in an open-
ended setting.

CommonsenseQA Talmor et al. (2019) has the same format as our proposed
RiddleSense, and both target general commonsense knowledge via multiple-choice
question answering. However, CSQA focuses more on straightforward questions
where the description of the answer concept is easy to understand and
retrieval over ConceptNet, while RS makes use of riddle questions to test
higher-order commonsense reasoning ability. More detailed comparisions between
them are in Section 3, which shows that the unique challenges of the
RiddleSense on multiple dimensions.

### Commonsense Reasoning Methods

Our experiments cover three major types of commonsense reasoning methods that
are popular in many benchmarks: fine-tuning pretrained LMs Devlin et al.
(2019a); Liu et al. (2019); Lan et al. (2020), graph-based reasoning with
external KGs Lin et al. (2019); Feng et al. (2020), and fine-tuning unified
text-to-text QA models Khashabi et al. (2020). Apart from ConceptNet, There
are also some methods Lv et al. (2020); Xu et al. (2020) using additional
knowledge resources such as Wikipedia and Wiktionary. A few recent methods
also aim to generate relevant triples via language generation models so that
the context graph is more beneficial for reasoning Wang et al. (2020); Yan et
al. (2020). Our experiments in this paper aim to compare the most typical and
popular methods which have open-source implementations, which we believe are
beneficial for understanding the limitation of these methods in higher-order
commonsense reasoning — RiddleSense.

### Computational Creativity and NLP

Creativity has been seen as a central property of the human use of natural
language McDonald and Busa (1994). Text should not be always taken at face
value, however, higher-order use of language and figurative devices such as
metaphor can communicate richer meanings and needs deeper reading and more
complicated reasoning skills Veale (2011). Recent works on processing language
with creative use focus on metaphor detection Gao et al. (2018), pun
generation He et al. (2019); Luo et al. (2019), creative story generation, and
humor detection Weller and Seppi (2019, 2020), sarcasm generation Chakrabarty
et al. (2020), etc.

Riddling, as a way to use creative descriptions to query a common concept, are
relatively underexplored. Previous works Tan et al. (2016); Gonçalo Oliveira
and Rodrigues (2018) focus on the generation of riddles in specific languages
and usually rely on language-specific features (e.g., decomposing a Chinese
character into multiple smaller pieces). There is few datasets or public
resources for studying riddles as a reasoning task, to the best of our
knowledge. The proposed RiddleSense is among the very first works connecting
commonsense reasoning and computational creative, and provides a large dataset
to train and evaluate models for answering riddle questions.

##  6 Conclusion

We propose a novel commonsense reasoning challenge, RiddleSense, which
requires complex commonsense skills for reasoning about creative and
counterfactual questions, coming with a large multiple-choice QA dataset. We
systematically evaluate recent commonsense reasoning methods over the proposed
RiddleSense dataset, and find that the best model is still far behind human
performance, suggesting that there is still much space for commonsense
reasoning methods to improve. We hope RiddleSense can serve as a benchmark
dataset for future research targeting complex commonsense reasoning and
computational creativity.

## Acknowledgements

This research is supported in part by the Office of the Director of National
Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA),
via Contract No. 2019-19051600007, the DARPA MCS program under Contract No.
N660011924033 with the United States Office Of Naval Research, the Defense
Advanced Research Projects Agency with award W911NF-19-20271, and NSF SMA
18-29268. The views and conclusions contained herein are those of the authors
and should not be interpreted as necessarily representing the official
policies, either expressed or implied, of ODNI, IARPA, or the U.S. Government.
We would like to thank all the collaborators in USC INK research lab and the
reviewers for their constructive feedback on the work.

## Ethical Considerations

#### Copyright of Riddles.

The RiddleSense dataset is consistent with the terms of use of the fan
websites and the intellectual property and privacy rights of the original
sources. All of our riddles and answers are from fan websites that can be
accessed freely. The website owners state that we may print and download
material from the sites solely for non-commercial use provided that we agree
not to change or delete any copyright or proprietary notices from the
materials. Therefore, in addition to the dataset itself, we also provide the
according copyright statements of every website and an URL link to the
original page for each riddle. The dataset users must sign an informed consent
form that they will only use our dataset for research purposes before they can
access the both the riddles and our annotations.

## References

  * Bhagavatula et al. (2020) Chandra Bhagavatula, Ronan Le Bras, Chaitanya Malaviya, Keisuke Sakaguchi, Ari Holtzman, Hannah Rashkin, Doug Downey, Wen-tau Yih, and Yejin Choi. 2020.  Abductive commonsense reasoning.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net.
  * Bisk et al. (2020) Yonatan Bisk, Rowan Zellers, Ronan LeBras, Jianfeng Gao, and Yejin Choi. 2020.  PIQA: reasoning about physical commonsense in natural language.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020_ , pages 7432–7439. AAAI Press.
  * Boratko et al. (2020) Michael Boratko, Xiang Li, Tim O’Gorman, Rajarshi Das, Dan Le, and Andrew McCallum. 2020.  ProtoQA: A question answering dataset for prototypical common-sense reasoning.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1122–1136, Online. Association for Computational Linguistics.
  * Chakrabarty et al. (2020) Tuhin Chakrabarty, Debanjan Ghosh, Smaranda Muresan, and Nanyun Peng. 2020.  R^3: Reverse, retrieve, and rank for sarcasm generation with commonsense knowledge.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7976–7986, Online. Association for Computational Linguistics.
  * Chen et al. (2019) Michael Chen, Mike D’Arcy, Alisa Liu, Jared Fernandez, and Doug Downey. 2019.  Codah: An adversarially authored question-answer dataset for common sense.  _ArXiv_ , abs/1904.04365.
  * Clark et al. (2018) Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, A. Sabharwal, Carissa Schoenick, and Oyvind Tafjord. 2018.  Think you have solved question answering? try arc, the ai2 reasoning challenge.  _ArXiv_ , abs/1803.05457.
  * Devlin et al. (2019a) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019a.  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)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Devlin et al. (2019b) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019b.  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)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Elazar et al. (2019) Yanai Elazar, Abhijit Mahabal, Deepak Ramachandran, Tania Bedrax-Weiss, and Dan Roth. 2019.  How large are lions? inducing distributions over quantitative attributes.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 3973–3983, Florence, Italy. Association for Computational Linguistics.
  * Feng et al. (2020) Yanlin Feng, Xinyue Chen, Bill Yuchen Lin, Peifeng Wang, Jun Yan, and Xiang Ren. 2020.  Scalable multi-hop relational reasoning for knowledge-aware question answering.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1295–1309, Online. Association for Computational Linguistics.
  * Gao et al. (2018) Ge Gao, Eunsol Choi, Yejin Choi, and Luke Zettlemoyer. 2018.  Neural metaphor detection in context.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 607–613, Brussels, Belgium. Association for Computational Linguistics.
  * Gonçalo Oliveira and Rodrigues (2018) Hugo Gonçalo Oliveira and Ricardo Rodrigues. 2018.  Exploring lexical-semantic knowledge in the generation of novel riddles in Portuguese.  In _Proceedings of the 3rd Workshop on Computational Creativity in Natural Language Generation (CC-NLG 2018)_ , pages 17–25, Tilburg, the Netherlands. Association for Computational Linguistics.
  * Gordon and Van Durme (2013) Jonathan Gordon and Benjamin Van Durme. 2013.  Reporting bias and knowledge acquisition.  In _Proceedings of the 2013 workshop on Automated knowledge base construction_ , pages 25–30.
  * He et al. (2019) He He, Nanyun Peng, and Percy Liang. 2019.  Pun generation with surprise.  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)_ , pages 1734–1744, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Hirsch (2014) Edward Hirsch. 2014.  _A poet’s glossary_.  HMH.
  * Khashabi et al. (2020) Daniel Khashabi, Sewon Min, Tushar Khot, Ashish Sabharwal, Oyvind Tafjord, Peter Clark, and Hannaneh Hajishirzi. 2020.  UNIFIEDQA: Crossing format boundaries with a single QA system.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 1896–1907, Online. Association for Computational Linguistics.
  * Lan et al. (2020) Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. 2020.  ALBERT: A lite BERT for self-supervised learning of language representations.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net.
  * Lin et al. (2019) Bill Yuchen Lin, Xinyue Chen, Jamin Chen, and Xiang Ren. 2019.  KagNet: Knowledge-aware graph networks for commonsense reasoning.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 2829–2839, Hong Kong, China. Association for Computational Linguistics.
  * Lin et al. (2020a) Bill Yuchen Lin, Seyeon Lee, Rahul Khanna, and Xiang Ren. 2020a.  Birds have four legs?! NumerSense: Probing Numerical Commonsense Knowledge of Pre-Trained Language Models.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6862–6868, Online. Association for Computational Linguistics.
  * Lin et al. (2021) Bill Yuchen Lin, Haitian Sun, Bhuwan Dhingra, Manzil Zaheer, Xiang Ren, and William Cohen. 2021.  Differentiable open-ended commonsense reasoning.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 4611–4625, Online. Association for Computational Linguistics.
  * Lin et al. (2020b) Bill Yuchen Lin, Wangchunshu Zhou, Ming Shen, Pei Zhou, Chandra Bhagavatula, Yejin Choi, and Xiang Ren. 2020b.  CommonGen: A constrained text generation challenge for generative commonsense reasoning.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 1823–1840, Online. Association for Computational Linguistics.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _ArXiv_ , abs/1907.11692.
  * Luo et al. (2019) Fuli Luo, Shunyao Li, Pengcheng Yang, Lei Li, Baobao Chang, Zhifang Sui, and Xu Sun. 2019.  Pun-GAN: Generative adversarial network for pun generation.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 3388–3393, Hong Kong, China. Association for Computational Linguistics.
  * Lv et al. (2020) Shangwen Lv, Daya Guo, Jingjing Xu, Duyu Tang, Nan Duan, Ming Gong, Linjun Shou, Daxin Jiang, Guihong Cao, and Songlin Hu. 2020.  Graph-based reasoning over heterogeneous external knowledge for commonsense question answering.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020_ , pages 8449–8456. AAAI Press.
  * McDonald and Busa (1994) David D. McDonald and Federica Busa. 1994.  On the creative use of language: The form of lexical resources.  In _Proceedings of the Seventh International Workshop on Natural Language Generation_.
  * Mihaylov et al. (2018) Todor Mihaylov, Peter Clark, Tushar Khot, and Ashish Sabharwal. 2018.  Can a suit of armor conduct electricity? a new dataset for open book question answering.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 2381–2391, Brussels, Belgium. Association for Computational Linguistics.
  * Miller (1992) George A. Miller. 1992.  WordNet: A lexical database for English.  In _Speech and Natural Language: Proceedings of a Workshop Held at Harriman, New York, February 23-26, 1992_.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _Journal of Machine Learning Research_ , 21(140):1–67.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-BERT: Sentence embeddings using Siamese BERT-networks.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 3982–3992, Hong Kong, China. Association for Computational Linguistics.
  * Salazar et al. (2020) Julian Salazar, Davis Liang, Toan Q. Nguyen, and Katrin Kirchhoff. 2020.  Masked language model scoring.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 2699–2712, Online. Association for Computational Linguistics.
  * Sap et al. (2019) Maarten Sap, Hannah Rashkin, Derek Chen, Ronan Le Bras, and Yejin Choi. 2019.  Social IQa: Commonsense reasoning about social interactions.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 4463–4473, Hong Kong, China. Association for Computational Linguistics.
  * Speer et al. (2017) Robyn Speer, Joshua Chin, and Catherine Havasi. 2017.  Conceptnet 5.5: An open multilingual graph of general knowledge.  In _Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA_ , pages 4444–4451. AAAI Press.
  * Talmor et al. (2019) Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. 2019.  CommonsenseQA: A question answering challenge targeting commonsense knowledge.  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)_ , pages 4149–4158, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Tan et al. (2016) Chuanqi Tan, Furu Wei, Li Dong, Weifeng Lv, and Ming Zhou. 2016.  Solving and generating Chinese character riddles.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 846–855, Austin, Texas. Association for Computational Linguistics.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA_ , pages 5998–6008.
  * Veale (2011) Tony Veale. 2011.  Creative language retrieval: A robust hybrid of information retrieval and linguistic creativity.  In _Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies_ , pages 278–287, Portland, Oregon, USA. Association for Computational Linguistics.
  * Wang et al. (2020) Peifeng Wang, Nanyun Peng, Filip Ilievski, Pedro Szekely, and Xiang Ren. 2020.  Connecting the dots: A knowledgeable path generator for commonsense question answering.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 4129–4140, Online. Association for Computational Linguistics.
  * Weller and Seppi (2019) Orion Weller and Kevin Seppi. 2019.  Humor detection: A transformer gets the last laugh.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 3621–3625, Hong Kong, China. Association for Computational Linguistics.
  * Weller and Seppi (2020) Orion Weller and Kevin Seppi. 2020.  The rJokes dataset: a large scale humor collection.  In _Proceedings of the 12th Language Resources and Evaluation Conference_ , pages 6136–6141, Marseille, France. European Language Resources Association.
  * Williams et al. (2018) Adina Williams, Nikita Nangia, and Samuel Bowman. 2018.  A broad-coverage challenge corpus for sentence understanding through inference.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 1112–1122, New Orleans, Louisiana. Association for Computational Linguistics.
  * Xu et al. (2018) Frank F. Xu, Bill Yuchen Lin, and Kenny Zhu. 2018.  Automatic extraction of commonsense LocatedNear knowledge.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 96–101, Melbourne, Australia. Association for Computational Linguistics.
  * Xu et al. (2020) Yichong Xu, Chenguang Zhu, Ruochen Xu, Yang Liu, Michael Zeng, and Xuedong Huang. 2020.  Fusing context into knowledge graph for commonsense reasoning.  _arXiv preprint arXiv:2012.04808_.
  * Yan et al. (2020) Jun Yan, Mrigank Raman, Tianyu Zhang, Ryan Rossi, Handong Zhao, Sungchul Kim, Nedim Lipka, and Xiang Ren. 2020.  Learning contextualized knowledge structures for commonsense reasoning.  _arXiv preprint arXiv:2010.12873_.
  * Yasunaga et al. (2021) Michihiro Yasunaga, Hongyu Ren, Antoine Bosselut, Percy Liang, and Jure Leskovec. 2021.  QA-GNN: Reasoning with language models and knowledge graphs for question answering.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 535–546, Online. Association for Computational Linguistics.
  * Zellers et al. (2018) Rowan Zellers, Yonatan Bisk, Roy Schwartz, and Yejin Choi. 2018.  SWAG: A large-scale adversarial dataset for grounded commonsense inference.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 93–104, Brussels, Belgium. Association for Computational Linguistics.
  * Zellers et al. (2019) Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. 2019.  HellaSwag: Can a machine really finish your sentence? In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4791–4800, Florence, Italy. Association for Computational Linguistics.