Coloured graphical models and their symmetries 62R01, 05C50

# Coloured graphical models
and their symmetries

Isobel Davies<EMAIL_ADDRESS>Max Planck Institute for Mathematics in the
Sciences
Inselstraße 22, 04103 Leipzig
Orlando Marigliano<EMAIL_ADDRESS>KTH Royal Institute of Technology
Lindstedtsvägen 25, 10044 Stockholm, Sweden

###### Abstract

Coloured graphical models are Gaussian statistical models determined by an
undirected coloured graph. These models can be described by linear spaces of
symmetric matrices. We outline a relationship between the symmetries of the
graph and the linear forms that vanish on the reciprocal variety of the model.
In particular, we give four families for which such linear forms are
completely described by symmetries.

###### keywords:

Coloured graphs, Gaussian graphical models, graph symmetries

##  1 Introduction

Coloured graphical models are a class of Gaussian statistical models first
introduced in [3] to model situations where some of the covariates have
approximately equal empirical concentrations. These equalities are represented
by a coloured graph. The set of concentration matrices associated to a
coloured graphical model is a linear subspace of the set of real symmetric
$n\times n$ matrices.

Following the approach of algebraic statistics we view maximum likelihood (ML)
estimation as a problem in algebraic geometry, see for instance [5, Ch. 7]. In
our case, we consider the complex linear space of symmetric matrices
$\mathcal{L}\subseteq\mathbb{S}^{n}$ defined by a given coloured graphical
model and its _reciprocal variety_ $\mathcal{L}^{-1}$, which is defined by the
matrix inverses of the points in $\mathcal{L}$. In particular, algebraic
statisticians are interested in a collection of algebraic properties of
$\mathcal{L}$, such as its ML degree $\operatorname{mld}(\mathcal{L})$, its
reciprocal ML degree $\operatorname{rmld}(\mathcal{L})$, the degree
$\deg(\mathcal{L}^{-1})$ and the ideal $I(\mathcal{L}^{-1})$ defining the
reciprocal variety. For the definitions of these properties, see [2].

In [4], Sturmfels and Uhler compute some of these algebraic properties for
coloured graphical models whose underlying graph is the four-cycle. Inspired
by their work, we are interested in understanding these properties for
coloured graphical models. In this article, we explore the notion of symmetry
of a coloured graph and study its connection with the linear part of the ideal
$I(\mathcal{L}^{-1})$. In particular, we focus on _uniform coloured graphs_ ,
whose symmetries coincide with the usual graph symmetries of the underlying
uncoloured graph. For a number of families of uniform coloured graphs we
completely describe the linear part of the ideal $I(\mathcal{L}^{-1})$ via
symmetries. For this, we use the results in [2] on pencils of quadrics.

### Notation.

Let $G=(V,E)$ be a simple undirected graph, let $n=|V|$ and $E^{c}$ denote the
set of edges of the graph complement $G^{c}$. The (uncoloured) _adjacency
matrix_ of $G$ is the $n\times n$ matrix whose $(i,j)$-th entry is $1$ if
$(i,j)\in E$ and $0$ otherwise. A _colouring_ of $G$ is a partition of $V$
together with a partition of $E$. A _colour_ is an equivalence class with
respect to one of these partitions.

Let $G$ be a coloured graph with $n$ vertices and $d$ colours
$\gamma_{1},\dotsc,\gamma_{d}$. For $k=1,\dotsc,d$ we define the matrix
$A_{k}$ associated to the colour $\gamma_{k}$ as follows. If $\gamma_{k}$ is a
vertex colour then $(A_{k})_{ii}=1$ if vertex $i$ has the colour $\gamma_{k}$,
while the other entries are all zero. If $\gamma_{k}$ is an edge colour then
$(A_{k})_{ij}=1$ if edge $(i,j)$ exists and has the colour $\gamma_{k}$, and
all the other entries are zero. The (coloured) _adjacency matrix_ $A$ of $G$
is the matrix

$\sum_{k=1}^{d}\lambda_{k}A_{k}\in\mathbb{Z}[\lambda_{1},\dotsc,\lambda_{d}]^{n\times
n}.$

Let $G$ be a coloured graph with $n$ vertices and $d$ colours. The associated
linear space of symmetric matrices $\mathcal{L}$ is the subspace

$\left\\{\sum_{k=1}^{d}\lambda_{k}A_{k}:\lambda_{1},\dotsc,\lambda_{d}\in\mathbb{C}\right\\}$

of the space of complex symmetric $n\times n$ matrices $\mathbb{S}^{n}$. The
_reciprocal variety_ $\mathcal{L}^{-1}$ is the Zariski-closure of the set

$\\{A^{-1}:A\in\mathcal{L}\text{ invertible}\\}\subseteq\mathbb{S}^{n}.$

Its ideal is denoted by $I(\mathcal{L}^{-1})$.

##  2 Linear forms from symmetries

We start by defining graph symmetries, following the approach in [3, Sec. 5].

Let $A$ be the uncoloured, resp. coloured adjacency matrix of an uncoloured,
resp. coloured graph $G$. A _symmetry_ of $G$ is an $n\times n$ permutation
matrix $B$ such that $BAB^{-1}=A$.

Such a symmetry gives a set of linear forms that vanish on the reciprocal
variety $\mathcal{L}^{-1}$:

######  Proposition 1.

Let $G$ be a coloured graph, $B$ a symmetry of $G$ and $X$ a generic element
of $\mathbb{S}^{n}$. The binomial linear forms defined by all distinct entries
of the matrix $BXB^{-1}-X$ belong to $I(\mathcal{L}^{-1})$.

######  Proof 2.1.

If $B$ is a symmetry of $G$, then $BA^{-1}B^{-1}=A^{-1}$ in
$\mathbb{Q}(\lambda_{1},\dotsc,\lambda_{d})^{n\times n}$ by taking inverses.
Thus, a generic element $X$ of $\mathcal{L}^{-1}$ must satisfy the equation
$BXB^{-1}-X=0,$ whose entries are binomial linear forms.

We call the linear forms that come from Proposition 1 _induced by symmetries_.
When the linear part of $I(\mathcal{L}^{-1})$ is generated by these linear
forms, we also say it is _induced by symmetries_.

Let $G$ be the following coloured $5$-cycle:

51432

The only nontrivial symmetry of $G$ is the reflection $B_{\tau}$ along the
depicted axis. The matrix $B_{\tau}XB_{\tau}^{-1}-X$ equals

$\begin{pmatrix}-x_{11}+x_{22}&0&-x_{13}+x_{25}&-x_{14}+x_{24}&-x_{15}+x_{23}\\\
0&x_{11}-x_{22}&x_{15}-x_{23}&x_{14}-x_{24}&x_{13}-x_{25}\\\
-x_{13}+x_{25}&x_{15}-x_{23}&-x_{33}+x_{55}&-x_{34}+x_{45}&0\\\
-x_{14}+x_{24}&x_{14}-x_{24}&-x_{34}+x_{45}&0&x_{34}-x_{45}\\\
-x_{15}+x_{23}&x_{13}-x_{25}&0&x_{34}-x_{45}&x_{33}-x_{55}\end{pmatrix}.$

Hence, the linear forms induced by symmetries in $I(\mathcal{L}^{-1})$ are:

$x_{11}-x_{22},\quad x_{33}-x_{55},\quad x_{13}-x_{25},\quad
x_{14}-x_{24},\quad x_{15}-x_{23},\quad x_{34}-x_{25}.$

These do not generate the whole linear part of $I(\mathcal{L}^{-1})$. For
instance, the linear form $x_{14}+x_{44}-x_{35}-x_{55}$ is contained in the
ideal but is not a linear combination of the above. Let $G$ be the following
disconnected graph:

4132

The only nontrivial symmetry of $G$ is the permutation $B_{\rho}$ of vertices
$3$ and $4$. The matrix $B_{\rho}XB_{\rho}^{-1}-X$ gives all the binomial
linear forms in the following list of generators of the linear part of
$I(\mathcal{L}^{-1})$:

$x_{33}-x_{44},\quad x_{13}-x_{14},\quad x_{12},\quad x_{23},\quad x_{24}.$

The following proposition explains the three other generators.

######  Proposition 2.

Let $G$ be a coloured graph and let $i,j$ be a pair of vertices belonging to
different connected components of $G$. Then we have $x_{ij}\in
I(\mathcal{L}^{-1})$.

######  Proof 2.2.

The adjacency matrix $A$ of $G$ can be written as a block diagonal matrix
whose blocks are the adjacency matrices of the connected components of $G$.
Since its inverse $A^{-1}$ retains this block structure, a generic element $X$
of $\mathcal{L}^{-1}$ must have a zero entry at each pair of indices $(i,j)$
as in the statement.

Let $I^{\prime}$ be the ideal generated by all linear forms induced by
symmetries of $G$ and all linear forms found by applying Proposition 2. We
define a further linear subspace $\mathcal{L}^{\prime}$ as the vanishing set
$V(I^{\prime})$. Like $\mathcal{L}$, this linear subspace is associated to a
coloured graph $G^{\prime}$, whose colouring is induced by the linear forms in
$I^{\prime}$. In [3, Sec. 5], the linear subspace $\mathcal{L}^{\prime}$ is
called an _RCOP model_.

The linear forms found in Examples 2 and 2 give rise to the following graphs
$G_{1}^{\prime}$ and $G_{2}^{\prime}$.

514324132

By Proposition 1, every symmetry of a coloured graph $G$ is also a symmetry of
$G^{\prime}$. We also see that both $\mathcal{L}$ and $\mathcal{L}^{-1}$ are
contained in $\mathcal{L}^{\prime}$. The next proposition demonstrates how
$\mathcal{L}^{\prime}$ can be used as a lower-dimensional ambient space to
compute the ML degree of $\mathcal{L}$.

######  Proposition 3.

Let $S^{\prime}$ be a general matrix of $\mathcal{L}^{\prime}$ and let
$(\mathcal{L}^{\perp})^{\prime}=\mathcal{L}^{\perp}\cap\mathcal{L}^{\prime}$,
where $\mathcal{L}^{\perp}\subseteq\mathbb{S}^{n}$ is the orthogonal
complement to $\mathcal{L}$ with respect to the trace inner product. Let
$(\mathcal{L}^{\perp})^{\prime}+S^{\prime}$ denote the affine space
$\\{X^{\prime}+S^{\prime}\mid X^{\prime}\in(\mathcal{L}^{\perp})^{\prime}\\}$.
The ML degree of $\mathcal{L}$ is the cardinality of the set

$\mathcal{L}^{-1}\cap((\mathcal{L}^{\perp})^{\prime}+S^{\prime}).$

######  Proof 2.3.

By definition, the ML degree of $\mathcal{L}$ is the cardinality of
$\mathcal{L}^{-1}\cap(\mathcal{L}^{\perp}+S)$, where $S$ is a general matrix
of $\mathbb{S}^{n}$ and $\mathcal{L}^{\perp}\subseteq\mathbb{S}^{n}$ is the
orthogonal complement of $\mathcal{L}$ in $\mathbb{S}^{n}$. Since
$\mathcal{L}\subseteq\mathcal{L}^{\prime}$, we have
$\operatorname{span}(\mathcal{L}^{\prime},\mathcal{L}^{\perp})=\mathbb{S}^{n}$.
We write all matrices $M\in\mathbb{S}^{n}$ as $M=M_{1}+M_{2}+M_{3}$, where the
term $M_{1}$ is the part of $M$ contained in $(\mathcal{L}^{\perp})^{\prime}$,
the term $M_{2}$ is the remaining part contained in $\mathcal{L}^{\perp}$, and
$M_{3}$ is the remaining part contained in $\mathcal{L}^{\prime}$. Let
$S^{\prime}=S_{1}+S_{3}.$ Since $S$ is general in $\mathbb{S}^{n}$, the matrix
$S^{\prime}$ is general in $\mathcal{L}^{\prime}$, so it remains to show that

$(\mathcal{L}^{\perp}+S)\cap\mathcal{L}^{\prime}=(\mathcal{L}^{\perp})^{\prime}+S^{\prime}.$

The reverse inclusion is clear. For the forward inclusion, Let
$\Sigma\in(\mathcal{L}^{\perp}+S)\cap\mathcal{L}^{\prime}$ and write
$\Sigma=X+S$ with $X\in\mathcal{L}^{\perp}$. Write
$\Sigma=X_{1}+X_{2}+S^{\prime}+S_{2}$ using the above decomposition for $X$
and $S$. Since $\Sigma\in\mathcal{L}^{\prime},$ we have
$X_{2}+S_{2}\in\mathcal{L}^{\prime}$. By construction, $X_{2}+S_{2}=0$, so
$\Sigma=X_{1}+S^{\prime}\in(\mathcal{L}^{\perp})^{\prime}+S^{\prime}$, as
required.

##  3 Uniform coloured graphs

In this section, we apply Proposition 1 to coloured graphs whose colouring has
only one edge colour and one vertex colour. Such a graph is uniquely
determined by its underlying uncoloured graph, and we call it a _uniform
coloured graph_. Its group of symmetries coincides with the group of
symmetries of its uncoloured graph. We are interested in the question: when is
the linear part of $I(\mathcal{L}^{-1})$ induced by symmetries?

The adjacency matrix of a uniform coloured graph has the form

$\lambda_{1}A_{1}+\lambda_{2}A_{2}$

where $A_{1}$ is the $n\times n$ identity matrix and $A_{2}$ is the adjacency
matrix of the underlying uncoloured graph. Since the corresponding linear
space $\mathcal{L}$ is two-dimensional, we may apply the results in [2] on
pencils of quadrics.

[[2]] Let $\mathcal{L}$ be a linear space spanned by two symmetric matrices
$A_{1}$ and $A_{2}$, such that $A_{1}$ is an invertible matrix. The _Segre
symbol_ of $\mathcal{L}$ is the unordered list

$\sigma=\left[\sigma_{1}\ldots\sigma_{r}\right]$

specified by the Jordan canonical form of $A_{1}^{-1}A_{2}$ in the following
way. Let $\alpha_{1},\dotsc,\alpha_{r}$ be the distinct eigenvalues of
$A_{1}^{-1}A_{2}$. Each $\sigma_{i}$ is itself a tuple of natural numbers
associated to the eigenvalue $\alpha_{i}$. The entries of $\sigma_{i}$ are
precisely the sizes of the Jordan blocks associated to $\alpha_{i}$.

If $\mathcal{L}$ is the linear space associated to a uniform coloured graph,
then its Segre symbol is a description of the spectrum of the underlying
uncoloured graph. More precisely, its entries $\sigma_{i}$ correspond to the
distinct eigenvalues of $A_{2}$ and are of the form $(1,\dotsc,1)$, where the
number of ones equals the multiplicity of the eigenvalue.

The spectrum of the Petersen graph is $(-2_{4},1_{5},3)$. Thus, the linear
space associated to its uniform coloured version has Segre symbol
$[1_{4},1_{5},1]$.

Using Segre symbols, it follows by [2, Thms. 3.2, 4.2] that the number $r$ of
distinct eigenvalues of $A_{2}$ determines certain algebraic properties of
$\mathcal{L}$. We summarize these in Table 1, along with the specific values
for the Petersen graph.

| Uniform Coloured Graph | Petersen Graph
---|---|---
$\deg(\mathcal{L}^{-1})$ | $r-1$ | 2
$\operatorname{mld}(\mathcal{L})$ | $r-1$ | 2
$\operatorname{rmld}(\mathcal{L})$ | $2r-3$ | 3
no. linear forms | $\binom{n+1}{2}-r$ | 52
no. quadratic forms | $\binom{r-1}{2}$ | 1
Table 1:  Algebraic properties of the linear space of symmetric matrices
$\mathcal{L}$ associated to a uniform coloured graph and the uniform coloured
Petersen graph. Here, $r$ denotes the number of distinct eigenvalues of the
uncoloured adjacency matrix of the graph. The first row is the degree of
$\mathcal{L}^{-1}$. The second and third rows are the ML and reciprocal ML
degrees of $\mathcal{L}$ as defined by [2]. Since $\mathcal{L}$ is a pencil,
the ideal $I(\mathcal{L}^{-1})$ is generated by linear and quadratic forms.
The last two rows give the number of these forms in a set of minimal
generators of $I(\mathcal{L}^{-1})$.

Comparing the number of linearly independent linear forms induced by
symmetries with the total number $\binom{n+1}{2}-r$, we can determine whether
the linear part of $I(\mathcal{L}^{-1})$ is induced by symmetries for any
given graph $G$. To this end, the following reformulation of Proposition 1 is
useful:

######  Corollary 4.

Let $G$ be a coloured graph, $i,j$ two vertices, and
$B\in\operatorname{Aut}(G)$ be a symmetry, considered as a permutation of the
vertex set $V$. Then $x_{i,j}-x_{B(i),B(j)}$ lies in $I(\mathcal{L}^{-1})$. In
particular, let $V*V$ be the set of unordered pairs of vertices of $G$ and $s$
the number of orbits of the entrywise action of $\operatorname{Aut}(G)$ on
$V*V$. Then the number of linear forms of $I(\mathcal{L}^{-1})$ induced by
symmetries is $\binom{n+1}{2}-s$.

######  Proof 3.1.

The statements follow from Proposition 1. The first statement follows by
computing the $(B(i),B(j))$-th entry of $BXB^{-1}$. The second follows from
the fact that every orbit $Y$ of the group action gives $|Y|-1$ linear forms,
while the number of elements in $V*V$ is $\binom{n+1}{2}$.

It follows that the linear part of $I(\mathcal{L}^{-1})$ is induced by
symmetries if and only if $s=r$. Our main result gives four families of
uniform coloured graphs where this is the case, illustrated in Figure 1. We
use the following conventions: the complete bipartite graph $K_{m,m}$ is split
by the parity of its vertices, and the hyperoctahedral graph $H_{m}$ is
obtained from the complete graph $K_{2m}$ by removing the edges
$\\{(2k-1,2k)\mid k=1,\dotsc,m\\}$.

514263

514263

514263

514263

Figure 1: Uniform coloured graphs on $6$ vertices where the linear part of
$I(\mathcal{L}^{-1})$ is induced by symmetries. From left to right: the cycle
$C_{6}$, the complete graph $K_{6}$, the complete bipartite graph $K_{3,3}$,
and the hyperoctahedral graph $H_{3}$.

######  Theorem 5.

Let $G$ be one of: the cycle $C_{n}$, the complete graph $K_{n}$, the complete
bipartite graph $K_{m,m}$, or the hyperoctahedral graph $H_{m}$. Then the
linear part $L$ of $I(\mathcal{L}^{-1})$ is induced by symmetries. More
precisely,

1\. If $G=C_{n}$, then $r=s=\lfloor n/2\rfloor+1$ and $L$ is generated by

$x_{1,1+d}-x_{i,i+d},\quad i=2,\dotsc,n,\quad d=0,\dotsc,\lfloor n/2\rfloor,$

where all indices are taken modulo $n$ and $x_{ji}$ for $j>i$ is taken to mean
$x_{ij}$.

2\. If $G=K_{n}$, then $r=s=2$ and $L$ is generated by

$\displaystyle x_{11}$ $\displaystyle-x_{ii},\quad i\in V$ $\displaystyle
x_{12}$ $\displaystyle-x_{ij},\quad i\in E.$

3\. If $G=K_{m,m}$, then $r=s=3$ and $L$ is generated by

$\displaystyle x_{11}$ $\displaystyle-x_{ii},\quad i\in V$ $\displaystyle
x_{12}$ $\displaystyle-x_{ij},\quad(i,j)\in E$ $\displaystyle x_{13}$
$\displaystyle-x_{ij},\quad(i,j)\in E^{c}.$

4\. If $G=H_{m}$, then $r=s=3$ and $L$ is generated by

$\displaystyle x_{11}$ $\displaystyle-x_{ii},\quad i\in V$ $\displaystyle
x_{13}$ $\displaystyle-x_{ij},\quad(i,j)\in E$ $\displaystyle x_{12}$
$\displaystyle-x_{ij},\quad(i,j)\in E^{c}.$

######  Proof 3.2.

First, all statements about the number of eigenvalues $r$ are proven in [1,
pp. 17, 50]. By Corollary 4, giving the linear forms induced by symmetries
amounts to giving a full set of representatives for the action of
$\operatorname{Aut}(G)$ on $V*V$. Since this action decomposes into an action
on the three disjoint subsets $V,E$, and $E^{c}$, it is useful to consider
these separately.

1\. If $G=C_{n}$, then $\operatorname{Aut}(G)$ acts transitively on $V$ and
$E$. The orbits of the action on $E^{c}$ are the sets
$E^{c}_{d}\coloneqq\\{(i,i+d)\mid i\in V\\}$ for $d=2,\dotsc,\lfloor
n/2\rfloor$.

2\. If $G=K_{n}$, then $\operatorname{Aut}(G)$ acts transitively on $V$ and
$E$, and $E^{c}=\emptyset$.

3\. If $G=K_{m,n}$ is any complete bipartite graph, then the complement
$G^{c}$ is the disjoint union of the two complete graphs
$K_{m}=(V_{1},E_{1}^{c})$ and $K_{n}=(V_{2},E_{2}^{c})$. The group
$\operatorname{Aut}(G)$ acts transitively on $V_{1},V_{2},E,E^{c}_{1}$, and
$E^{c}_{2}$. In the case $n=m$, there exists an additional symmetry that
interchanges $V_{1}$ and $V_{2}$. Hence in this case, we see that
$\operatorname{Aut}(G)$ acts transitively on $V,E$, and $E^{c}$.

4\. The hyperoctahedral graph $G=H_{m}$ is the complete multipartite graph on
$m$ two-element sets. A similar argument to the one for $K_{m,m}$ shows that
$\operatorname{Aut}(G)$ acts transitively on $V,E,$ and $E^{c}$.

Taking these statements about the action of $\operatorname{Aut}(G)$ on $V*V$
and applying Corollary 4 proves all statements in the theorem.

The linear space associated to the uniform coloured $6$-cycle is

$\displaystyle\mathcal{L}=\left\\{\begin{pmatrix}\lambda_{2}&\lambda_{1}&0&0&0&\lambda_{1}\\\
\lambda_{1}&\lambda_{2}&\lambda_{1}&0&0&0\\\
0&\lambda_{1}&\lambda_{2}&\lambda_{1}&0&0\\\
0&0&\lambda_{1}&\lambda_{2}&\lambda_{1}&0\\\
0&0&0&\lambda_{1}&\lambda_{2}&\lambda_{1}\\\
\lambda_{1}&0&0&0&\lambda_{1}&\lambda_{2}\\\
\end{pmatrix}:\lambda_{1},\lambda_{2}\in\mathbb{C}\right\\}.$

The spectrum of the (uncoloured) $6$-cycle is $(1_{2},-1_{2},2,-2)$. There are
$4$ orbits of the action of $\operatorname{Aut}(G)$ on $V*V$, namely
$V,E,E_{2}^{c}$ and $E_{3}^{c}$. According to Theorem 5, the following $17$
linear forms generate the linear part of $I(\mathcal{L}^{-1})$:

$x_{11}-x_{22}$ | $x_{12}-x_{23}$ | $x_{13}-x_{24}$ | $x_{14}-x_{25}$
---|---|---|---
$x_{11}-x_{33}$ | $x_{12}-x_{34}$ | $x_{13}-x_{35}$ | $x_{14}-x_{36}$
$x_{11}-x_{44}$ | $x_{12}-x_{45}$ | $x_{13}-x_{46}$ |
$x_{11}-x_{55}$ | $x_{12}-x_{56}$ | $x_{13}-x_{15}$ |
$x_{11}-x_{66}$ | $x_{12}-x_{16}$ | $x_{13}-x_{26}$ |

The graph $G^{\prime}$ associated to the symmetries of $G$ can be found in
Table 4.

We conclude this section with two families of graphs where the linear part of
$I(\mathcal{L}^{-1})$ is not induced by symmetries, illustrated in Figure 2.
We use the convention that for $m<n$, the vertex set of the complete bipartite
graph $K_{m,n}$ is partitioned as $\\{1,\dotsc,m\\}$ and
$\\{m+1,\dotsc,m+n\\}$.

514263

564321

Figure 2:  The uniform coloured complete bipartite graph $K_{2,4}$ and the
star $K_{1,5}$. For these graphs, the linear part of $I(\mathcal{L}^{-1})$ is
not induced by symmetries.

######  Proposition 6.

Let $G=K_{m,n}$ be the complete bipartite graph with $1<m<n$. Then $r=3$,
$s=5$ and the linear part of $I(\mathcal{L}^{-1})$ is generated by

$\displaystyle x_{11}-x_{ii},$ $\displaystyle\quad i\in V_{1}$ $\displaystyle
x_{m+1,m+1}-x_{ii},$ $\displaystyle\quad i\in V_{2}$ $\displaystyle
x_{12}-x_{ij},$ $\displaystyle\quad(i,j)\in E^{c}_{1}$ $\displaystyle
x_{m+1,m+2}-x_{ij},$ $\displaystyle\quad(i,j)\in E^{c}_{2}$ $\displaystyle
x_{1,m+1}-x_{ij},$ $\displaystyle\quad(i,j)\in E$ $\displaystyle
mx_{12}-nx_{m+n-1,m+n},$ $\displaystyle
mx_{11}-(n-m)x_{m+n-1,m+n}-mx_{m+n,m+n},$

where $(V_{1},E_{1}^{c})$ and $(V_{2},E_{2}^{c})$ are the two components of
the complement $G^{c}$.

######  Proof 3.3.

The statement about $r$ is proven in [1, pg. 50]. The first five sets of
linear forms are the forms induced by symmetries, as explained in the proof of
Theorem 5. Furthermore, all the above linear forms are linearly independent.

To see that the last two linear forms vanish on $\mathcal{L}^{-1}$, let
$D_{m,n}$ be the determinant of the coloured adjacency matrix $A$ of
$K_{m,n}$. By manually calculating the entries of $A^{-1}$ (up to a factor of
$\det(A)^{-1}$) we have

$\displaystyle x_{11}$ $\displaystyle=D_{m-1,n},$ $\displaystyle x_{12}$
$\displaystyle=-(D_{m-1,n}-\lambda_{1}D_{m-2,n}),$ $\displaystyle
x_{m+n-1,m+n}$ $\displaystyle=-(D_{m,n-1}-\lambda_{1}D_{m,n-2}),$
$\displaystyle x_{n+m,n+m}$ $\displaystyle=D_{m,n-1}.$

Furthermore, one can verify that
$D_{m,n}=\lambda_{1}^{m+n}-mn\lambda_{1}^{m+n-2}\lambda_{2}^{2}.$ Substituting
this formula for $D_{m,n}$ in the above expressions for the entries of
$A^{-1}$ shows that the last two linear forms above indeed vanish. The
assumption that $m>1$ was used in the middle two equations for the entries of
$A^{-1}$.

######  Proposition 7.

Let $G$ be the _star graph_ on $n$ vertices, i.e. the complete bipartite graph
$K_{1,n-1}$. Then $r=3$, $s=4$, and the linear part of $I(\mathcal{L}^{-1})$
is generated by

$\displaystyle x_{22}-x_{ii},$ $\displaystyle\quad i=3,\dotsc,n$
$\displaystyle x_{12}-x_{ij},$ $\displaystyle\quad(i,j)\in E$ $\displaystyle
x_{23}-x_{ij},$ $\displaystyle\quad(i,j)\in E^{c}$ $\displaystyle
x_{11}-(n-2)x_{n-1,n}-x_{nn}.$

######  Proof 3.4.

The action of $\operatorname{Aut}(G)$ on $V$ has two orbits, one with only one
element, so that it does not give any linear form. The action on $E$ and
$E^{c}$ is transitive. This explains the first three sets of linear forms,
which are induced by symmetries.

The missing linear form can be derived by computing three entries of the
inverse $A^{-1}$. Up to a factor of $\det(A)^{-1}$, we have

$\displaystyle x_{11}$ $\displaystyle=\lambda_{1}^{n-1},$ $\displaystyle
x_{nn}$
$\displaystyle=\lambda_{1}^{n-1}-(n-2)\lambda_{1}^{n-3}\lambda_{2}^{2},$
$\displaystyle x_{n-1,n}$ $\displaystyle=\lambda_{1}^{n-3}\lambda_{2}^{2}.$

The middle equality holds since the determinant $D_{n}$ of the coloured
adjacency matrix of the star on $n$ vertices satisfies
$D_{n}=\lambda_{1}^{n}-(n-1)\lambda_{1}^{n-2}\lambda_{2}^{2}$.

##  4 Open Problems

By Proposition 1, the symmetries of a coloured graph explain some binomial
linear forms in the ideal $I(\mathcal{L}^{-1})$. The following example shows
that in general, not all binomial linear forms in $I(\mathcal{L}^{-1})$ are
induced by symmetries. The graph

4132

has no nontrivial symmetries, but all elements $X\in\mathcal{L}^{-1}$ satisfy
$x_{13}-x_{24}=0$. However, after computing the linear part of
$I(\mathcal{L}^{-1})$ for all colourings on the $3$,$4$, and $5$-cycle, we
arrived at the following conjecture.

######  Conjecture 8.

Let $G$ be a coloured $n$-cycle. All _binomial_ linear forms in
$I(\mathcal{L}^{-1})$ are induced by symmetries.

In Theorem 5 we give four families of graphs where the linear part of
$I(\mathcal{L}^{-1})$ is induced by symmetries. In particular, this gives a
complete description of the linear part for the uniform coloured $n$-cycle.
However, for every $n$ this only represents one possible colouring.

Can one give a a complete description of the linear part of
$I(\mathcal{L}^{-1})$ for _all_ colourings of the $n$-cycle?

Tables 2 and 3 give a complete list of all coloured $5$-cycles with only one
vertex colour. Just as in Example 2, some linear forms are not induced by
symmetries. We have highlighted these.

All graphs covered by Theorem 5 are _circulant graphs_. By definition, these
are graphs that have a symmetry which is a cyclic permutation of its vertices.
We conjecture that like the families in the theorem, the linear part of
$I(\mathcal{L}^{-1})$ is induced by symmetries for _all_ uniform coloured
circulant graphs. This is equivalent to $r=s$ in the notation of Section 3:

######  Conjecture 9.

If $G$ is an uncoloured circulant graph, then the number of orbits of the
action of $\operatorname{Aut}(G)$ on the set $V*V$ of unordered pairs of
vertices of $G$ coincides with the number of distinct eigenvalues of its
adjacency matrix.

In this article we have focused on linear forms. We do not know whether the
quadratic forms of a minimal generating set of $I(\mathcal{L}^{-1})$ can be
deduced graphically from $G$. In Table 4 we give these quadratic forms when
$G$ is the uniform coloured $n$-cycle for $n=3,\dotsc,8$, along with the graph
$G^{\prime}$ associated to the symmetries of $G$.

### Acknowledgements.

We thank Shiyue Li, Aida Maraj and Bernd Sturmfels for helpful conversations
in the early stages of this project. Thanks to the anonymous referee for
encouraging us to broaden the scope of our first version.

$G$ |  Linear Forms |  $G^{\prime}$
---|---|---
51432 |  | $x_{11}-x_{55}$ | $x_{12}-x_{45}$ | $x_{13}-x_{35}$
---|---|---
$x_{22}-x_{55}$ | $x_{23}-x_{45}$ | $x_{14}-x_{35}$
$x_{33}-x_{55}$ | $x_{34}-x_{45}$ | $x_{24}-x_{35}$
$x_{44}-x_{55}$ | $x_{15}-x_{45}$ | $x_{25}-x_{35}$
|  |
51432
51432 |  $x_{11}-x_{22}$ $x_{15}-x_{23}$ $x_{33}-x_{55}$ $x_{34}-x_{45}$ $x_{13}-x_{25}$ $x_{14}-x_{24}$ $\displaystyle x_{24}+x_{44}-x_{35}-x_{55}$ |  51432
51432 |  $x_{11}-x_{33}$ $x_{14}-x_{35}$ $x_{44}-x_{55}$ $x_{15}-x_{34}$ $x_{12}-x_{23}$ $x_{24}-x_{25}$ $\displaystyle x_{13}+x_{34}+x_{55}-x_{33}-x_{35}-x_{45}$ |  51432
51432 |  | $x_{11}-x_{44}$ | $x_{13}-x_{24}$
---|---
$x_{22}-x_{33}$ | $x_{15}-x_{45}$
$x_{12}-x_{34}$ | $x_{25}-x_{35}$
51432
51432 |  None. |  51432
51432 |  None. |  51432
Table 2: Linear minimal generators of $I(\mathcal{L}^{-1})$ for coloured five-cycles. The left column of the table shows the given coloured five-cycle $G$ with all vertices having the same colour. The linear generators of the corresponding reciprocal varieties are shown in the middle column. Highlighted are the generators not induced by symmetries, i.e. not found with Proposition 1. The right column shows the graph $G^{\prime}$ associated to the symmetries of $G$. If $I^{\prime}$ is the zero ideal, we give $G^{\prime}$ as the uncoloured complete graph on $5$ vertices.  $G$ |  Linear Forms |  $G^{\prime}$
---|---|---
51432 |  None. |  51432
51432 |  | $x_{11}-x_{33}$ | $x_{14}-x_{35}$
---|---
$x_{44}-x_{55}$ | $x_{15}-x_{34}$
$x_{12}-x_{23}$ | $x_{24}-x_{25}$
51432
51432 |  $\displaystyle x_{14}+x_{44}-x_{35}-x_{55}$ |  51432
51432 |  None. |  51432
51432 |  None. |  51432
51432 |  None. |  51432
Table 3: Continuation of Table 2. $n$ |  Quadratic Forms |  Graph $G^{\prime}$
---|---|---
$3$ |  None. |  213
$4$ |  $x_{13}^{2}-2x_{12}^{2}+x_{13}x_{11}$ |  4132
$5$ |  $x_{13}^{2}-x_{13}x_{12}-x_{12}^{2}+x_{13}x_{11}$ |  51432
6 |  | $2x_{13}^{2}-x_{12}x_{14}-x_{14}^{2}$
---
$2x_{12}x_{13}-x_{11}x_{14}-x_{13}x_{14}$
$2x_{12}^{2}-2x_{11}x_{13}+x_{12}x_{14}-x_{14}^{2}$
514263
7 |  | $x_{13}^{2}-x_{12}x_{14}+x_{13}x_{14}-x_{14}^{2}$
---
$x_{12}x_{13}-x_{11}x_{14}+x_{12}x_{14}-x_{13}x_{14}$
$x_{12}^{2}-x_{11}x_{13}+x_{13}x_{14}-x_{14}^{2}$
6153742
8 |  | $2x_{14}^{2}-x_{13}x_{15}-x_{15}^{2}$
---
$2x_{13}x_{14}-x_{12}x_{15}-x_{14}x_{15}$
$2x_{12}x_{14}-x_{11}x_{15}-x_{13}x_{15}$
$2x_{13}^{2}-x_{11}x_{15}-x_{15}^{2}$
$2x_{12}x_{13}-2x_{11}x_{14}+x_{12}x_{15}-x_{14}x_{15}$
$2x_{12}^{2}-2x_{11}x_{13}+x_{13}x_{15}-x_{15}^{2}$
61528374
Table 4: Quadratic forms in a minimal generating set of $I(\mathcal{L}^{-1})$
for the first eight uniform coloured $n$-cycles. The right column displays the
graph $G^{\prime}$ representing all linear forms in the minimal generating set
(by Theorem 5).

## References

  * [1] Norman Biggs, _Algebraic graph theory_ , Cambridge University Press, 1974.
  * [2] Claudia Fevola, Yelena Mandelshtam, and Bernd Sturmfels, _Pencils of quadrics: Old and new_ , ArXiv:2009.04334, 2020.
  * [3] Søren Højsgaard and Steffen L. Lauritzen, _Graphical gaussian models with edge and vertex symmetries_ , Journal of the Royal Statistical Society B 70 (2008), 1005–1027.
  * [4] Bernd Sturmfels and Caroline Uhler, _Multivariate gaussians, semidefinite matrix completion, and convex algebraic geometry_ , Annals of the Institute of Statistical Mathematics 62 (2010), 603–638.
  * [5] Seth Sullivant, _Algebraic statistics_ , American Mathematical Society, 2018\.


# Negated Complementary Commonsense using Large Language Models

Navid Rezaei
ECE, University of Alberta
Edmonton, Canada T6G 1H9
<EMAIL_ADDRESS>
Marek Z. Reformat
ECE, University of Alberta
Edmonton, Canada T6G 1H9
University of Social Sciences
90-113 Łódź, Poland
<EMAIL_ADDRESS>

###### Abstract

Larger language models, such as GPT-3, have shown to be excellent in many
tasks. However, we demonstrate that out-of-ordinary questions can throw the
model off guard. This work focuses on finding answers to negated complementary
questions in commonsense scenarios. We illustrate how such questions adversely
affect the model responses. We propose a model-agnostic methodology to improve
the performance in negated complementary scenarios. Our method outperforms
few-shot generation from GPT-3 (by more than 11 points) and, more importantly,
highlights the significance of studying the response of large language models
in negated complementary questions. The code, data, and experiments are
available under: https://github.com/navidre/negated_complementary_commonsense.

##  1 Introduction

The larger the language models (LLMs) become, the better they demonstrate new,
outstanding capabilities. For example, one is conducting a conversation about
commonsense scenarios. However, our interaction with LLMs has led us to
observe that the models tend to emphasize the normal flow of events and seem
to struggle with questions involving a negated form of verbs, such as not or
cannot. An example of that is in Figure 1. Therefore, in this paper, we focus
on demonstrating the issue and then suggest an approach to remedy the problem.

Figure 1: An example of a large language model (GPT-3) generating negated
commonsense. Five responses per query are demonstrated. The applied pre-
processing and post-processing can improve the performance of the models in
negated commonsense cases. Non-specific answers, such as not Santa, are
considered incorrect.

To better clarify the problem statement, we start with an example and then
formalize it using elements of the set theory. Let us look at the scenario in
Figure 1; the standard question is “Who PersonX can be?”. The answer to this
question is Santa Claus. The answer to the negated complementary question –
“Who PersonX cannot be?” – should be all valid answers which are not the
answer to the standard (can be) question. A valid answer fits the scenario
described. In this case, we ask about a person, so a non-person cannot be a
valid answer. To better illustrate the concept of a negated complementary
question, we refer to the basic notion of the complement of a set, Figure 2.
Furthermore, we define a set of correct answers to a negated complementary,
Equation 1.

$\mathit{NC}=V\cap A^{\prime}=\\{x\>|\>x\in V\land x\notin A\\}$ (1)

where $\mathit{NC}$ represents answers to the negated complementary question,
$V$ is the set of all valid answers, $A$ is the set of correct answers to the
standard question, and $A^{\prime}$ is the complement of $A$ under the
universal set of all answers ($U$).

Figure 2: Venn diagram of answer sets: $U$ is the universal set of answers;
$V$ is the set of all valid answers that includes two sets – correct answers
to a standard question $A$, and correct answers to its negated complementary
version $\mathit{NC}$.

We focus our efforts on commonsensical questions as the uncertainty of results
depends on the context and experiences of people answering the questions. As
defined in (LeCun, 2022), commonsense is a collection of world models
representing what is likely, plausible, or impossible. In light of that, our
goal is to assess the ability of LLMs to answer plausible questions that could
be refuted or accepted in a given context.

Given their pre-training nature, we hypothesize that LLMs have an inherent
bias towards likely scenarios, which are the most repeated in the common text.
Most of the text available on the web contains information supporting answers
to ‘positive’ questions, like, how to do things or where to go, not to
questions such as how things could not be done or where not to go. It results
in an imbalance of the training datasets due to the sparsity of plausible or
impossible scenarios. In this paper, we demonstrate that LLMs have difficulty
answering negated complementary questions, which results in responses
representing plausible, but not impossible, answers. Although LLMs are shown
to have this shortcoming, we claim that enough instructions and examples,
especially showing reasoning processes, can guide the LLMs into the right path
to answer negated complementary questions with commonsense context.

Our contributions are as follows. (1) We present an analysis exposing the
shortcomings of LLMs when it comes to negated complementary questions in
commonsensical scenarios. (2) We propose a novel methodology to improve the
performance of the GPT-3 model when negated complementary questions are asked;
compare the results with the results obtained using conventional methods. Our
code, human-evaluation process, and data will be publicly available.

##  2 Related Work

Language models with transformer architectures have revolutionized the natural
language processing landscape in recent years (Vaswani et al., 2017; Devlin et
al., 2019). It is shown that improved performance and new capabilities emerge
when scaling up the size of language models (Brown et al., 2020; Chowdhery et
al., 2022), although more is needed in challenging tasks, such as commonsense
(Rae et al., 2021).

A body of research focuses on analyzing and extracting commonsense from
language models (West et al., 2022; Rezaei and Reformat, 2022; Hwang et al.,
2021; Da et al., 2021). Authors of (Jiang et al., 2021) focus on implications
of negated statements and contradictions, where in a commonsense triple
relationship (head-relation-tail), the head is either contradicted or
logically negated. Comparably this paper focuses on negating relations instead
of the head, as explained in Section 4.

##  3 Commonsense Data

The commonsense dataset used in this paper is the ATOMIC-2020 dataset (Hwang
et al., 2021). It includes general purpose commonsense knowledge, divided into
three main categories – physical, event-centered, and social commonsense. The
ATOMIC 2020 dataset is licensed under CC-BY and we use it according to the
license.

In our experiments, ten relation types are selected from the twenty-three
relations from the ATOMIC-2020 dataset. These ten relation types performed
worse in our initial evaluation of negated complementary questions. The
relations are: xWant, xReact, oWant, CapableOf, Desires, HinderedBy, isBefore,
isAfter, AtLocation, HasSubEvent. The worse-performer triples are intuitively
more common in the normal format in written language than their negated
complementary versions, which can result in unbalanced training data.

The dataset is formatted in a triple style. Each atomic piece of data contains
$\langle head-relation-tail\rangle$. For example, $\langle a\ curved\ yellow\
fruit\ (head)-CanBe\ (relation)-banana\ (tail)\rangle$.

##  4 Methodology

We propose a pipeline system to improve the performance on negated
complementary commonsense questions. The pipeline consists of an input
prompting technique and a post-processing module. The input prompt adds
relevant context and logic in the form of chain-of-thought prompting (Wei et
al., 2022) to improve the LLM performance. The post-processing module selects
the outputs with a higher chance of correctness and filters out the rest.

###  4.1 Generating Negated Complementary Questions

As described in Section 3, the used dataset is in the format of triples. To
form a standard question, we use the head and the relation nodes and leave out
the tail to be answered. By standard, we mean utilizing the head, relation,
and tail, without any modifications. Assuming a triple, a curved yellow fruit
(head), CanBe (relation), banana (tail), the standard question is What can be
a curved yellow fruit?. The negated complementary question is formed by
negating the relation and verbalizing the resulting triple in question format:
What cannot be a curved yellow fruit? A valid answer to the standard question
is banana, and a reasonable response to the negated complementary question is
apple. The process is visualized in Figure 3. For the complete list of triple
verbalizations, please see Appendix A.

Figure 3: The process to automatically generate negated complementary
questions from dataset triples. The head and relation nodes are used to form a
question.

###  4.2 Prompting Technique

The proposed methodology to improve the performance of LLMs relies on building
an adequate prompt. It starts with a general introduction of what negations
are and emphasizes a need to pay special attention to the word Not. The chain-
of-thought prompt in each answer has five sections in sequence: 1) phrasing
standard question; 2) standard question reasoning, 3) standard question
answer; 4) negation logic, and 5) negated complementary question answer. The
steps are visualized in Figure 4. For a fair comparison, we used the same
number of five question/answer examples in the prompts. We also used the same
questions for all prompts.

Figure 4: Chain-of-thought steps for each answer. The process is to answer the
standard question first and then lead the model to answer the negated
complementary version.

###  4.3 Post Processing

Inspired by (Kadavath et al., 2022), we feed the question and answer pair back
to the GPT-3 model and ask if it considers a question/answer pair correct. The
prompt has instructions for assessing an answer and includes five sample
questions/answer pairs. Interestingly, this extra step can improve the results
by almost one percent. To better understand the effect of this step, please
refer to Table 2.

##  5 Experiments

Experiments are conducted on each type of relation mentioned in Section 3. A
hundred data points (triples) are sampled randomly from the dataset. The head
and relation from each triple are verbalized and fed into the GPT-3 model
(text-davinci-002). The goal is to predict the tail for two forms of
questions: (1) standard question; (2) negated complementary question. For each
question, three responses are requested from the model. They are then parsed,
and the answers (tails) are automatically extracted. Therefore, three possible
tails are obtained for each head and relation, which results in $600$ total
answers per method.

In social commonsense scenarios, PersonX and PersonY are used in place of
gender-specific pronouns to make the questions and answers gender-neutral.

The experiments are done using the GPT-3 model (Brown et al., 2020) with
version text-davinci-002, which has 175 billion parameters. The temperature is
set to $0.7$, and in case of no answer, it is increased to $1.0$. The maximum
length of the output is set between $100$ and $150$ tokens, depending on the
method. The presence and frequency penalties are set to $0$. GPT-3 is
commercially available, and we have used it within its intended usage and
terms of service.

###  5.1 Human Evaluations

We use Amazon mTurk evaluations via AWS SageMaker to evaluate the results.
Each answer is written in a sentence format and given to nine different
annotators for assessment. Instructions and examples are provided with each
question to assist the annotators better. The options to choose from are: (1)
Makes sense; (2) Sometimes makes sense; (3) Does not make sense or incorrect;
(4) The first part and the second part are not related; or not enough
information to judge; (5) Unfamiliar to me to judge. The first two options are
considered correct, the second two are considered incorrect, and the last is
considered unfamiliar. To measure inter-rater reliability, we use
Krippendorff’s alpha and make sure the value is above acceptable amounts
(minimum 0.667) (Hayes and Krippendorff, 2007). The evaluators were paid based
on AWS guidelines.

Method | Standard | Negated Complementary
---|---|---
Few-shot | 88.7% | 78.7%
Ours | 88.1% | 89.8%
Table 1: Our method compared with the few-shot method when applied to
ATOMIC-2020 dataset.

###  5.2 Results

As seen in Table 1, our method outperforms the few-shot method by more than
eleven percentage points when answering negated complementary questions. The
few-shot method includes five different questions in the prompt with their
answers without chain-of-thought prompting. The performance of our method can
mainly be attributed to the specific chain-of-thought prompting with negation
logic description, Figure 4. More information about the main contributing
factors is in Section 5.3. Although chain-of-thought prompting seems to help
the negated complementary questions, it adversely affects answers to the
standard questions. Please note that the chain-of-thought prompt for the
standard questions does not include negation logic, and a post-processing
technique similar to negated complementary questions is performed.

###  5.3 Ablation Studies

To gain insight into the importance of elements of our method, we perform an
ablation study, Table 2. As we can see, adding standard question reasoning
(step 2 of Figure 4) results in more than 7% improvement in the results.
Adding the thought process explaining the negation logic (steps 1, 3, and 4 of
Figure 4) adds another 3% performance improvement. Finally, the post-
processing (Section 4.3) is responsible for about 1% improvement in the
results.

Method | Neg. Comp.
---|---
Ours | 89.8%
Ours-wo-pp | 89.0%
Ours-wo-nl-pp | 86.0%
Few-shot | 78.7%
Table 2: Ablation study of the method: Ours-wo-pp is ours without post-
processing; Ours-wo-nl-pp is ours without negation logic and post-processing.

##  6 Conclusions

In this paper, we demonstrate how simple changes in question formats, which
can be trivial for humans, can be challenging for large language models
(LLMs). We specifically focus on negated complementary questions in a
commonsense context, which is constructed by negating a relation in a
commonsense triple. Given the vast amount of knowledge embedded in LLMs, we
show that by appropriate guidance, the models could perform well on negated
complementary tasks. Our method results in more than eleven percent
improvement compared to the vanilla few-shot method. Given the widespread
usage of LLMs and their growth rate, we believe focusing on and solving the
model’s weaknesses is imperative. As future work, negated complementary task
can be further analyzed in different formats, such as sentence instead of a
question, and also different contexts, e.g., new datasets.

## Limitations

The experiments in this paper have focused on the negated complementary task
in the context of commonsense and the format of questions. However, it is
interesting to experiment with other contexts, such as mathematical datasets
and other formats, such as sentences instead of questions.

This paper only uses the English language in the negated complementary task
experiments, so further investigation is needed in other languages to
understand better the limitations of large language models across other
languages.

GPT-3 is commercially available, and the cost can be a limitation. For
example, the current price for text-davinci-002 model is $0.02 per 1,000
tokens.

## Ethics Statement

Given the widespread use of large language models and their growth, more
software systems will depend on them. This could improve productivity and
accessibility, but any vulnerability in large language models can propagate
through the system and affect the end users. This work focused on distorted
commonsense scenarios that are almost trivial for humans but can be
challenging for large language models. Not only we highlighted the negated
complementary questions issue, but we also suggested practical solutions that
do not require extensive computation. We believe this line of research can
ultimately benefit end users in terms of productivity, reliability, and
accessibility.

## References

  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 1877–1901. Curran Associates, Inc.
  * Chowdhery et al. (2022) Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Levskaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowycz, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier-Hellstern, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. 2022\.  Palm: Scaling language modeling with pathways.  _CoRR_ , abs/2204.02311.
  * Da et al. (2021) Jeff Da, Ronan Le Bras, Ximing Lu, Yejin Choi, and Antoine Bosselut. 2021.  Analyzing commonsense emergence in few-shot knowledge models.  In _3rd Conference on Automated Knowledge Base Construction_.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  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.
  * Hayes and Krippendorff (2007) Andrew F. Hayes and Klaus Krippendorff. 2007.  Answering the call for a standard reliability measure for coding data.  _Communication Methods and Measures_ , 1:77 – 89.
  * Hwang et al. (2021) Jena D. Hwang, Chandra Bhagavatula, Ronan Le Bras, Jeff Da, Keisuke Sakaguchi, Antoine Bosselut, and Yejin Choi. 2021.  (COMET-)ATOMIC 2020: On symbolic and neural commonsense knowledge graphs.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 35(7):6384–6392.
  * Jiang et al. (2021) Liwei Jiang, Antoine Bosselut, Chandra Bhagavatula, and Yejin Choi. 2021.  “I’m not mad”: Commonsense implications of negation and contradiction.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 4380–4397, Online. Association for Computational Linguistics.
  * Kadavath et al. (2022) Saurav Kadavath, Tom Conerly, Amanda Askell, T. J. Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, Zachary Dodds, Nova DasSarma, Eli Tran-Johnson, Scott Johnston, Sheer El-Showk, Andy Jones, Nelson Elhage, Tristan Hume, Anna Chen, Yuntao Bai, Sam Bowman, Stanislav Fort, Deep Ganguli, Danny Hernandez, Josh Jacobson, John Kernion, Shauna Kravec, Liane Lovitt, Kamal Ndousse, Catherine Olsson, Sam Ringer, Dario Amodei, Tom B. Brown, Jack Clark, Nicholas Joseph, Benjamin Mann, Sam McCandlish, Christopher Olah, and Jared Kaplan. 2022.  Language models (mostly) know what they know.  _ArXiv_ , abs/2207.05221.
  * LeCun (2022) Yann LeCun. 2022.  A path towards autonomous machine intelligence version 0.9.2.
  * Rae et al. (2021) Jack W. Rae, Sebastian Borgeaud, Trevor Cai, Katie Millican, Jordan Hoffmann, H. Francis Song, John Aslanides, Sarah Henderson, Roman Ring, Susannah Young, Eliza Rutherford, Tom Hennigan, Jacob Menick, Albin Cassirer, Richard Powell, George van den Driessche, Lisa Anne Hendricks, Maribeth Rauh, Po-Sen Huang, Amelia Glaese, Johannes Welbl, Sumanth Dathathri, Saffron Huang, Jonathan Uesato, John Mellor, Irina Higgins, Antonia Creswell, Nat McAleese, Amy Wu, Erich Elsen, Siddhant M. Jayakumar, Elena Buchatskaya, David Budden, Esme Sutherland, Karen Simonyan, Michela Paganini, Laurent Sifre, Lena Martens, Xiang Lorraine Li, Adhiguna Kuncoro, Aida Nematzadeh, Elena Gribovskaya, Domenic Donato, Angeliki Lazaridou, Arthur Mensch, Jean-Baptiste Lespiau, Maria Tsimpoukelli, Nikolai Grigorev, Doug Fritz, Thibault Sottiaux, Mantas Pajarskas, Toby Pohlen, Zhitao Gong, Daniel Toyama, Cyprien de Masson d’Autume, Yujia Li, Tayfun Terzi, Vladimir Mikulik, Igor Babuschkin, Aidan Clark, Diego de Las Casas, Aurelia Guy, Chris Jones, James Bradbury, Matthew Johnson, Blake A. Hechtman, Laura Weidinger, Iason Gabriel, William S. Isaac, Edward Lockhart, Simon Osindero, Laura Rimell, Chris Dyer, Oriol Vinyals, Kareem Ayoub, Jeff Stanway, Lorrayne Bennett, Demis Hassabis, Koray Kavukcuoglu, and Geoffrey Irving. 2021.  Scaling language models: Methods, analysis and insights from training gopher.  _CoRR_ , abs/2112.11446.
  * Rezaei and Reformat (2022) Navid Rezaei and Marek Z. Reformat. 2022.  Utilizing language models to expand vision-based commonsense knowledge graphs.  _Symmetry_ , 14(8).
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoc Le, and Denny Zhou. 2022.  Chain of thought prompting elicits reasoning in large language models.  _arXiv preprint arXiv:2201.11903_.
  * West et al. (2022) Peter West, Chandra Bhagavatula, Jack Hessel, Jena Hwang, Liwei Jiang, Ronan Le Bras, Ximing Lu, Sean Welleck, and Yejin Choi. 2022.  Symbolic knowledge distillation: from general language models to commonsense models.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 4602–4625, Seattle, United States. Association for Computational Linguistics.

##  Appendix A Verbalizations

The questions are verbalized from triples using pre-defined formats. Table 3
summarizes the verbalizations organized by relation types. The question
template formats are inspired by the sentence format used in (Hwang et al.,
2021).

Relation | Question
---|---
xWant | [head]. What does PersonX want to do?
| [head]. What does PersonX not want to do?
xReact | [head]. What does PersonX feel about it?
| [head]. What does PersonX not feel about it?
oWant | [head]. What does PersonY want to do?
| [head]. What does PersonY not want to do?
CapableOf | What is [head] capable of?
| What is [head] not capable of?
Desires | What does [head] desire to do?
| What does [head] not desire to do?
HinderedBy | [head]. What can hinder/obstruct it?
| [head]. What cannot hinder/obstruct it?
isBefore | [head]. What happens before it?
| [head]. What does not happen before it?
isAfter | [head]. What happens after it?
| [head]. What does not happen after it?
AtLocation | Where is the [head] located?
| Where is the [head] not located?
HasSubEvent | [head]. What will you do while: [head]?
| [head]. What you will not do while: [head]
Table 3: Question templates for each relation type. The first row for each
relation shows the standard question format, and the second row shows the
negated complementary format. [head] refers to the head in a triple.

##  Appendix B Human Evaluation Instructions

The following instructions are given to each human evaluator to better
understand and respond to the task:

Based on your own commonsense, choose one of the five options. Examples are
provided in the description. IMPORTANT: Please note the CANNOT, DO Not, and
other negated cases.

Instruction notes: Based on your own commonsense, choose one of the five
options. Examples are provided in the description.

IMPORTANT: Please note the CANNOT, DO Not, and other negated cases.

  1. 1.

Instead of names, PersonX and PersonY are used to be gender-neutral.

  2. 2.

Please ignore grammatical errors and focus on commonsense.

  3. 3.

If a response is vague, such as not fireman, or if a random word does not fit
the scenario, please choose 4 (not enough information).

Added to the instructions, we also provided some examples to clarify the task
better:

Unfamiliar to me to judge: PersonX discovers a new planet. The planet is in
the Alpha Centauri system.

First part and second part are not related! Or not enough information to
judge: PersonX rides a bike. Elephants are not birds. (Although the second
part is correct, it is not related to the first part)

Makes sense: It is NOT likely to see an elephant on the table.

Does not make sense: It is likely to see an elephant on the table.

The answers are written in a text format to make it easier for human
evaluators. Here is an example:. Here is an example:

PersonX sends PersonY to the showers. PersonX will not be amused.

##  Appendix C ChatGPT

The experiments of this paper were done using text-davinci-002 version of
GPT-3. The new version of GPT-3 with reinforcement learning from human
feedback (RLHF) is introduced and is called ChatGPT. Out of curiosity, we did
limited experiments with ChatGPT to see if the problem of negated
complementary questions persists. Here are a few answers from ChatGPT to the
question shown in Figure 1:

Q: PersonX is wearing red and white clothes and is going down a stranger’s
home’s chimney. Who PersonX cannot be?

A: It is likely that PersonX is not Santa Claus, as he is commonly depicted
wearing red and white clothes and going down chimneys.

As we can see, the model answers with not Santa Claus and then describes Santa
Clause. Asking the same question again, we get the following answer:

A: PersonX cannot be a real person as it is impossible for someone to
physically fit into a chimney. The scenario you described is likely
referencing a fictional character, such as Santa Claus, who is often depicted
as wearing red and white clothes and entering homes through chimneys on
Christmas Eve to deliver presents to children.

In this answer, there is a good start of context; however, somewhere within
the text, the model forgets about the cannot word and again describes Santa
Claus. For the third time, we ask the same question and we get the following
answer:

A: It is likely that PersonX is Santa Claus, a fictional figure who is often
depicted wearing red and white clothes and delivering presents to children
through the chimneys of houses.

The sentence is technically correct, but it is not what we asked for, which is
who cannot be. Therefore, we can consider the last answer incorrect as well.

Given the limited interaction with ChatGPT, it seems that the negated
complementary task issue persists.