11institutetext:  Department of Mathematics, Jadavpur University,
Kolkata-700032, India.
e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>22institutetext:
Department of Pure Mathematics, University of Calcutta, Kolkata-700019, India.
e-mail<EMAIL_ADDRESS>
# An introduction to coding sequences of graphs

Shamik Ghosh Corresponding author11 Raibatak Sen Gupta 11 M. K. Sen 22

###### Abstract

In his pioneering paper on matroids in 1935, Whitney obtained a
characterization for binary matroids and left a comment at end of the paper
that the problem of characterizing graphic matroids is the same as that of
characterizing matroids which correspond to matrices (mod 2) with exactly two
ones in each column. Later on Tutte obtained a characterization of graphic
matroids in terms of forbidden minors in 1959. But it is clear that Whitney
indicated about incidence matrices of simple undirected graphs.

In this paper, we introduce the concept of a segment binary matroid which
corresponds to matrices over $\mathbb{Z}_{2}$ which has the consecutive $1$’s
property (i.e., $1$’s are consecutive) for columns and obtained a
characterization of graphic matroids in terms of this.

In fact, we introduce a new representation of simple undirected graphs in
terms of some vectors of finite dimensional vector spaces over
$\mathbb{Z}_{2}$ which satisfy consecutive $1$’s property. The set of such
vectors is called a coding sequence of a graph $G$. Among all such coding
sequences we identify the one which is unique for a class of isomorphic
graphs. We call it the code of the graph. We characterize several classes of
graphs in terms of coding sequences. It is shown that a graph $G$ with $n$
vertices is a tree if and only if any coding sequence of $G$ is a basis of the
vector space $\mathbb{Z}_{2}^{n-1}$ over $\mathbb{Z}_{2}$.

Moreover considering coding sequences as binary matroids, we obtain a
characterization for simple graphic matroids and found a necessary and
sufficient condition for graph isomorphism in terms of a special matroid
isomorphism between their corresponding coding sequences. For this, we
introduce the concept of strong isomorphisms of segment binary matroids and
show that two simple (undirected) graphs are isomorphic if and only if their
canonical sequences are strongly isomorphic segment binary matroids.

AMS Subject Classifications: 05C62, 05C50, 05B35.

Keywords: Simple undirected graph, graph representation, graph isomorphism,
incidence matrix, consecutive $1$’s property, binary matroid, graphic matroid.

##  1 Introduction

There are various representations of simple undirected graphs in terms of
adjacency matrices, adjacency lists, incidence matrix, unordered pairs etc. In
this paper, we introduce another representation of a simple undirected graph
with $n$ vertices in terms of certain vectors in the vector space
$\mathbb{Z}_{2}^{n-1}$ over $\mathbb{Z}_{2}$. We call the set of vectors
representing a graph $G$ as a coding sequence of $G$ and denote it by
$\beta(G,n)$. Among all such coding sequences we identify the one which is
unique for a class of isomorphic graphs. We call it the code of the graph. We
find characterizations of graphs which are connected, acyclic, bipartite,
Eulerian or Hamiltonian in terms of $\beta(G,n)$. We prove that a graph $G$
with $n$ vertices is a tree if and only if any coding sequence of $G$ is a
basis of the vector space $\mathbb{Z}_{2}^{n-1}$ over $\mathbb{Z}_{2}$.

In his pioneering paper [9] on matroids in 1935, Whitney left the problem of
characterizing graphic matroid open by making the following comment: “The
problem of characterizing linear graphs from this point of view is the same as
that of characterizing matroids which correspond to matrices (mod 2) with
exactly two ones in each column.” In 1959, Tutte obtained a characterization
of graphic matroids in terms of forbidden minors [7]. But it is clear that
Whitney indicated about incidence matrices of simple undirected graphs. In
this paper, use a variation of incidence matrix for the same characterization.

In section 3, we introduce the concept of a segment binary matroid which
corresponds to matrices over $\mathbb{Z}_{2}$ that has the consecutive $1$’s
property (i.e., $1$’s are consecutive) for columns and a characterization of
graphic matroids is obtained by considering $\beta(G,n)$ as a segment binary
matroid. We introduce the concept of a strong isomorphism for segment binary
matroids and show that two simple graphs $G$ and $H$ (with $n$ vertices each)
are isomorphic if and only if $\beta(G,n)$ and $\beta(H,n)$ are strongly
isomorphic segment binary matroids.

For graph theoretic concepts, see [8] and for matroid related terminologies,
one may consult [6].

##  2 Coding sequences

###### Definition 1

Let $G=(V,E)$ be a simple undirected graph with $n$ vertices and $m$ edges.
Let $V=\left\\{v_{0},v_{1},\ldots,v_{n-1}\right\\}$. Define a map
$f\,:\,V\longrightarrow\mathbb{N}$ by $f(v_{i})=10^{i}$ and another map
$f^{*}\,:\,E\longrightarrow\mathbb{N}$ by
$f^{*}(v_{i}v_{j})=|f(v_{i})-f(v_{j})|$, if $E\neq\emptyset$. Let
$\sigma(G,n)$ be the sequence $\left\\{f^{*}(e)\ |\ e\in E\right\\}$ sorted in
the increasing order. If $E=\emptyset$, then $\sigma(G,n)=\emptyset$. It is
worth noticing that for $e=v_{i}v_{j}\in E$, $f^{*}(e)=|10^{i}-10^{j}|$
uniquely determines the pair $(i,j)$ as it is a natural number with $i$
digits, starting with $i-j$ number of $9$’s and followed by $j$ number of
$0$’s, when $i>j$. Thus $m$ entries of $\sigma(G,n)$ are all distinct.

Now for $E\neq\emptyset$, we define a map
$f^{\\#}\,:\,E\longrightarrow\mathbb{Z}_{2}^{n-1}$ by
$f^{\\#}(e)=(x_{1},x_{2},\ldots,x_{n-1})$, where $x_{i}=1$, if
$(n-i)^{\text{th}}$ digit of $f^{*}(e)$ from the right is $9$, otherwise
$x_{i}=0$ for $i=1,2,\ldots,n-1$. For convenience we write the field
$\mathbb{Z}_{2}$ as $\left\\{0,1\right\\}$ instead of
$\left\\{\bar{0},\bar{1}\right\\}$. Let $\beta(G,n)$ be the sequence
$\left\\{f^{\\#}(e)\ |\ e\in E\right\\}$ sorted in the same order as in
$\sigma(G,n)$. If $E=\emptyset$, then $\beta(G,n)=\emptyset$. The sequence
$\beta(G,n)$ is called a coding sequence of the graph $G$.

Naturally, $\beta(G,n)$ is not unique for a graph $G$ as it depends on the
labeling $f$ of vertices. Now there are $n!$ such labellings and consequently
we have at most $n!$ different $\sigma(G,n)$ for a graph $G$. Among which we
choose the one, say, $\sigma_{c}(G,n)$ which is the minimum in the
lexicographic ordering of $\mathbb{N}^{m}$. The corresponding $\beta(G,n)$ is
called the code of the graph $G$ and is denoted by $\beta_{c}(G,n)$. Clearly
$\beta_{c}(G,n)$ is unique for a class of isomorphic graphs with given number
of vertices, though it is not always easy to determine generally.

###### Example 1

Consider the graph $G$ in Figure 1 (left). We have

$\sigma(G,4)=(9,90,900,990)\ \text{ and }\
\beta(G,4)=\left\\{(0,0,1),(0,1,0),(1,0,0),(1,1,0)\right\\}$

according to the labeling of vertices given in Figure 1 (left). One may verify
that

$\sigma_{c}(G,4)=(9,90,99,900)\text{ and
}\beta_{c}(G,4)=\left\\{(0,0,1),(0,1,0),(0,1,1),(1,0,0)\right\\}$

according to the labeling of vertices shown in Figure 1 (right).

Figure 1: The graph $G$ in Example 1 with different labellings.

###### Remark 1

An incidence matrix of a (simple undirected) graph $G=(V,E)$ is obtained by
placing its vertices in rows and edges in columns and an entry in a row
corresponding to a vertex $v$ and in a column corresponding to an edge $e$ of
the matrix is $1$ if and only if $v$ is an end point of $e$, otherwise it is
$0$. It is important to note that a coding sequence of a graph has a
similarity with the incidence matrix of the graph. In fact, given a coding
sequence of a graph $G$, one can easily obtain the incidence matrix of $G$ and
vice-versa. Also cut-set and circuit subspaces of a vector space of dimension
$|E|$ over $\mathbb{Z}_{2}$ constructed from edges of $G$ are well known [3,
4, 5]. Further, as we mentioned in the introduction, Whitney expected the
characterization of graphic matroids would be obtained from the incidence
matrix. Here we consider a variation of it with a consecutive $1$’s
representation as it helps us to build a very natural interplay between graph
theory, matroids and linear algebra which is evident from Theorems 2.1 and
3.3.

Throughout this section by a graph we mean a simple undirected graph.

###### Definition 2

A non-null vector $e=(x_{1},x_{2},\ldots,x_{n-1})\in\mathbb{Z}_{2}^{n-1}$ is
said to satisfy the consecutive $1$’s property if $1$’s appear consecutively
in the sequence of coordinates of $e$. Let

$C(n-1)=\left\\{v\in\mathbb{Z}_{2}^{n-1}\ |\ v\text{ satisfies the consecutive
}1\text{'s property}\right\\}.$

Clearly, $|C(n-1)|=\binom{n}{2}=\frac{n(n-1)}{2}$ and $G$ is a complete graph
with $n$ vertices if and only if $\beta(G,n)=C(n-1)$. In fact, for every
$S\subseteq C(n-1)$, there is a unique graph $G(S)$ of $n$ vertices such that
$\beta(G,n)=S$. If $S=\emptyset$, then $G$ is the null graph with $n$ vertices
and no edges. If $S\neq\emptyset$, each member $e$ of $S$ represents an edge
of $G(S)=(V,E)$ with end points $10^{n-i}$ and $10^{n-j-1}$, where the
consecutive stretch of $1$’s in $e$ starts from the $i^{\text{th}}$ entry and
ends at the $j^{\text{th}}$ entry from the left and
$V=\left\\{1,10,10^{2},\ldots,10^{n-1}\right\\}$. Also it is clear that
$C(n-1)\smallsetminus\beta(G,n)$ is a coding sequence of the complement
$\bar{G}$ of a graph $G$ with $n$ vertices.

Let $\emptyset\neq S\subseteq C(n-1)$. Let $\tilde{G}(S)$ be the subgraph of
$G(S)$ obtained by removing isolated vertices (if any) from $G(S)$. Then
$\tilde{G}(S)$ is the subgraph of the complete graph of $n$ vertices induced
by the edges represented by the vectors in $S$.

We denote the null vector in the vector space $\mathbb{Z}_{2}^{n-1}$ by
$\mathbf{0}$ for any $n\in\mathbb{N}$ and write $\mathbb{Z}_{2}^{0}$ for the
zero-dimensional space $\left\\{\mathbf{0}\right\\}$. Let
$S=\left\\{e_{1},e_{2},\ldots,e_{k}\right\\}\subseteq\mathbb{Z}_{2}^{n-1}\smallsetminus\left\\{\mathbf{0}\right\\}$,
($k\in\mathbb{N}$, $k\leqslant 2^{n-1}$). As $e_{i}$’s are distinct, we have
$e_{i}+e_{j}\neq\mathbf{0}$ for all $i\neq j$,
$i,j\in\left\\{1,2,\ldots,k\right\\}$. Thus $S$ is a set of linearly dependent
vectors in $\mathbb{Z}_{2}^{n-1}$ over $\mathbb{Z}_{2}$ if and only if there
exists $A\subseteq S$, $|A|\geqslant 3$ such that $\sum\limits_{e\in
A}e=\mathbf{0}$. In other words, $S\subseteq\mathbb{Z}_{2}^{n-1}$ is linearly
independent over $\mathbb{Z}_{2}$ if and only if $S=\emptyset$ or
$S=\left\\{e_{1},e_{2},\ldots,e_{k}\right\\}$ for some $k\in\mathbb{N}$,
$k\leqslant 2^{n-1}$ and $\sum\limits_{e\in A}e\neq\mathbf{0}$ for all
$\emptyset\neq A\subseteq S$. We denote the linear span (over
$\mathbb{Z}_{2}$) of a subset $S$ of $\mathbb{Z}_{2}^{n-1}$ by
$\text{Sp}\,(S)$, i.e., $\text{Sp}\,(S)$ is the smallest subspace of
$\mathbb{Z}_{2}^{n-1}$ containing $S$.

###### Proposition 1

Let $S=\left\\{e_{1},e_{2},e_{3}\right\\}\subseteq C(n-1)$ for some
$n\in\mathbb{N}$, $n\geqslant 3$. Then $\tilde{G}(S)$ is a $3$-cycle if and
only if $e_{1}+e_{2}+e_{3}=\mathbf{0}$.

###### Proof

First suppose that $\tilde{G}(S)$ is the $3$-cycle shown in Figure 2, where
$\alpha,\beta,\gamma\in\left\\{0,1,\ldots,n-1\right\\}$. Without loss of
generality we assume $\alpha>\beta>\gamma$. Then

$\begin{array}[]{rcl}e_{1}&=&(\underbrace{0,0,\ldots,0}_{n-\alpha-1},\underbrace{1,1,\ldots,1}_{\alpha-\beta},\underbrace{0,0,\ldots,0,0,0,\ldots,0}_{\beta})\\\
e_{2}&=&(\underbrace{0,0,\ldots,0}_{n-\alpha-1},\underbrace{1,1,\ldots,1,1,1,\ldots,1}_{\alpha-\gamma},\underbrace{0,0,\ldots,0}_{\gamma})\\\
e_{3}&=&(\underbrace{0,0,\ldots,0,0,0,\ldots,0}_{n-\beta-1},\underbrace{1,1,\ldots,1}_{\beta-\gamma},\underbrace{0,0,\ldots,0}_{\gamma})\end{array}$

Clearly $e_{1}+e_{2}+e_{3}=\mathbf{0}$.

Figure 2: A $3$-cycle

Conversely, let $e_{1}+e_{2}+e_{3}=\mathbf{0}$. Consider the matrix
$M=\left(\begin{array}[]{c}e_{1}\\\ e_{2}\\\ e_{3}\end{array}\right)$, where
we represent each $e_{i}$ as a row matrix consisting of $n-1$ columns for
$i=1,2,3$. Since $e_{1}+e_{2}+e_{3}=\mathbf{0}$, in each column where $1$’s
appear, they appear exactly in two rows. Let $i$ be the least column number of
$M$ that contains $1$. Without loss of generality we assume that $1$’s appear
in the first two rows in the $i^{\text{th}}$ column (otherwise we rearrange
rows of $M$). Also suppose that the number of zeros after the stretch of $1$’s
in the first row, say, $\beta$ is more than that of the second, say, $\gamma$
(otherwise again we rearrange rows of $M$). Let $\alpha=n-i$. Then the end
points of the edge of $\tilde{G}(S)$ corresponding to $e_{1}$ are
$10^{\alpha}$ and $10^{\beta}$ and those of the edge corresponding to $e_{2}$
are $10^{\alpha}$ and $10^{\gamma}$. Since $\beta>\gamma$ and
$e_{1}+e_{2}+e_{3}=\mathbf{0}$, we have

$e_{3}=e_{1}+e_{2}=(\underbrace{0,0,\ldots,0}_{n-\beta-1},\underbrace{1,1,\ldots,1}_{\beta-\gamma},\underbrace{0,0,\ldots,0}_{\gamma}).$

Thus the end points of the edge of $\tilde{G}(S)$ corresponding to $e_{3}$ are
$10^{\beta}$ and $10^{\gamma}$. So the vertices labeled by
$10^{\alpha},10^{\beta}$ and $10^{\gamma}$ form a $3$-cycle with edges
corresponding to $e_{1},e_{2},e_{3}$, as required.

###### Definition 3

A set $S\neq\emptyset$ of non-null vectors in $\mathbb{Z}_{2}^{n-1}$ is called
reduced if $\sum\limits_{e\in A}e\neq\mathbf{0}$ for all $\emptyset\neq
A\subsetneqq S$.

###### Lemma 1

Let $S=\left\\{e_{1},e_{2},\ldots,e_{k}\right\\}\subseteq C(n-1)$ for some
$k,n\in\mathbb{N}$, $3\leqslant k\leqslant n$. Then $\tilde{G}(S)$ is a
$k$-cycle if and only if $S$ is reduced and
$e_{1}+e_{2}+\cdots+e_{k}=\mathbf{0}$.

###### Proof

We prove by induction on $k$. By Proposition 1, the result is true for $k=3$.
Suppose the result is true for $k=r-1\geqslant 3$. Let
$S=\left\\{e_{1},e_{2},\ldots,e_{r}\right\\}\subseteq C(n-1)$ for some
$r,n\in\mathbb{N}$, $3<r\leqslant n$ form the $r$-cycle shown in Figure 3 (we
renumber $e_{i}$’s, if necessary). Consider the chord $e$ so that
$e_{1},e_{2}$ and $e$ form a triangle. Then $e_{1}+e_{2}+e=\mathbf{0}$ by
Proposition 1. So $e=e_{1}+e_{2}$. Also
$\left\\{e,e_{3},e_{4},\ldots,e_{r}\right\\}$ form an $(r-1)$-cycle. So by
induction hypothesis $e+e_{3}+e_{4}+\cdots+e_{r}=\mathbf{0}$ which implies
$e_{1}+e_{2}+e_{3}+e_{4}+\cdots+e_{r}=\mathbf{0}$. Moreover since $S$ is a
cycle, no proper subset of $S$ form a cycle. Thus $S$ is reduced by induction
hypothesis.

Figure 3: An $r$-cycle

Conversely, let $S=\left\\{e_{1},e_{2},\ldots,e_{r}\right\\}\subseteq C(n-1)$
for some $r,n\in\mathbb{N}$, $3<r\leqslant n$ be reduced and
$e_{1}+e_{2}+\cdots+e_{r}=\mathbf{0}$. Consider the matrix
$M=\left(\begin{array}[]{c}e_{1}\\\ e_{2}\\\ \cdots\\\
e_{r}\end{array}\right)$, where we represent each $e_{i}$ as a row matrix
consisting of $n-1$ columns for $i=1,2,\ldots,r$. Let $i$ be the least column
number of $M$ that contains $1$. Since the row sum of $M$ is zero (the null
vector), the $i^{\text{th}}$ column contains even number of $1$’s. So there
are at least two rows with $1$ in the $i^{\text{th}}$ column. Rearrange rows
of $M$ such that $e_{1}$ and $e_{2}$ be two such rows. Since both of these
rows begin with $1$ in the $i^{\text{th}}$ column, the edges corresponding to
them have a common end point with label $10^{n-i}$. Join the other end points
of $e_{1}$ and $e_{2}$ by an edge, say, $e$ to form a triangle with edges
$e_{1},e_{2},e$. Then $e_{1}+e_{2}+e=\mathbf{0}$ which implies
$e=e_{1}+e_{2}$. So $e+e_{3}+e_{4}+\cdots+e_{r}=\mathbf{0}$.

We claim that $S_{1}=\left\\{e,e_{3},e_{4},\ldots,e_{r}\right\\}$ is reduced.
Suppose $A\subsetneqq S_{1}$, $|A|\geqslant 3$ be such that
$a=\sum\limits_{x\in A}x=\mathbf{0}$. If $e\notin A$, then $a\neq 0$ as $S$ is
reduced. So $e\in A$. Then replacing $e$ by $e_{1}+e_{2}$ in $a$ would again
contradict the fact that $S$ is reduced. So $S_{1}$ is reduced. Hence by
induction hypothesis, $S_{1}$ form an $(r-1)$-cycle. Now replacing the edge
$e$ by the path consisting of edges $e_{1}$ and $e_{2}$ gives us an $r$-cycle
formed by $S$.

The following two corollaries follow immediately from the above lemma.

###### Corollary 1

A graph $G$ with $n\geqslant 3$ vertices $(n\in\mathbb{N})$ is Hamiltonian if
and only if for any coding sequence $\beta(G,n)$ of $G$, there exists
$S=\left\\{e_{1},e_{2},\ldots,e_{n}\right\\}\subseteq\beta(G,n)$ such that $S$
is reduced and $e_{1}+e_{2}+\cdots+e_{n}=\mathbf{0}$.

###### Corollary 2

A graph $G$ with $n$ vertices $(n\in\mathbb{N})$ is acyclic if and only if any
coding sequence $\beta(G,n)$ of $G$ is linearly independent over
$\mathbb{Z}_{2}$.

###### Corollary 3

A graph $G$ with at most one non-trivial component and with $n$ vertices
$(n\in\mathbb{N})$ is Eulerian if and only if
$\displaystyle{\sum\limits_{e\in\beta(G,n)}e=\mathbf{0}}$ for any coding
sequence $\beta(G,n)$ of $G$.

###### Proof

Follows from Lemma 1 and the fact that a circuit in a graph can be decomposed
into edge-disjoint cycles.

###### Corollary 4

A graph $G$ with $n\geqslant 2$ vertices $(n\in\mathbb{N})$ is bipartite if
and only if for any coding sequence $\beta(G,n)$ of $G$,
$\displaystyle{\sum\limits_{e\in S}e\neq\mathbf{0}}$ for every
$S\subseteq\beta(G,n)$ where $|S|$ is odd.

###### Proof

Follows from Lemma 1 and the fact that a graph is bipartite if and only if it
does not contain any odd cycle.

###### Theorem 2.1

A graph $G$ with $n$ vertices $(n\in\mathbb{N})$ is a tree if and only if any
coding sequence $\beta(G,n)$ of $G$ is a basis of the vector space
$\mathbb{Z}_{2}^{n-1}$ over the field $\mathbb{Z}_{2}$.

###### Proof

Suppose $G$ is a tree. Then $G$ is acyclic which implies $\beta(G,n)$ is
linearly independent over $\mathbb{Z}_{2}$ by Corollary 2. Again since $G$ is
a tree, the number of entries in $\beta(G,n)$ is $n-1$, we have $n-1$ linearly
independent vectors in $\mathbb{Z}_{2}^{n-1}$ over $\mathbb{Z}_{2}$. Thus
$\beta(G,n)$ is a basis of $\mathbb{Z}_{2}^{n-1}$ over $\mathbb{Z}_{2}$.

Conversely, suppose $\beta(G,n)$ is a basis of $\mathbb{Z}_{2}^{n-1}$ over
$\mathbb{Z}_{2}$. Then $\beta(G,n)$ is linearly independent over
$\mathbb{Z}_{2}$ and so $G$ is acyclic by Corollary 2. Also since $\beta(G,n)$
is a basis of $\mathbb{Z}_{2}^{n-1}$ over $\mathbb{Z}_{2}$, the number of
entries in $\beta(G,n)$ is $n-1$ which implies $G$ has $n-1$ edges. Thus $G$
is a tree.

###### Corollary 5

A graph $G$ with $n$ vertices $(n\in\mathbb{N})$ is connected if and only if
for any coding sequence $\beta(G,n)$ of $G$, $\text{{\em
Sp}}\,(\beta(G,n))=\mathbb{Z}_{2}^{n-1}$.

###### Proof

We first note that a graph $G$ is connected if and only if $G$ has a spanning
tree. Suppose $G=(V,E)$ has a spanning tree $H=(V,E_{1})$. Then
$\beta(H,n)\subseteq\beta(G,n)$ with the same vertex labeling. But
$\beta(H,n)$ is a basis of $\mathbb{Z}_{2}^{n-1}$ over $\mathbb{Z}_{2}$ by
Theorem 2.1. Thus
$\text{Sp}\,(\beta(G,n))\supseteq\text{Sp}\,(\beta(H,n))=\mathbb{Z}_{2}^{n-1}$.
So $\text{Sp}\,(\beta(G,n))=\mathbb{Z}_{2}^{n-1}$.

Conversely, if $\text{Sp}\,(\beta(G,n))=\mathbb{Z}_{2}^{n-1}$, then
$\beta(G,n)$ contains a basis, say $B$ of $\mathbb{Z}_{2}^{n-1}$ over
$\mathbb{Z}_{2}$. Then $G(B)$ is a spanning tree of $G$ by Theorem 2.1 as
$B=\beta(G(B),n)$. Thus $G$ is connected.

###### Corollary 6

Let $G$ be a connected graph with $n$ vertices and $S\subseteq\beta(G,n)$.
Then $G(S)$ is a spanning tree of $G$ if and only if $S$ is a basis of the
vector space $\mathbb{Z}_{2}^{n-1}$ over the field $\mathbb{Z}_{2}$.

##  3 Matroid representation

Whitney introduced the concept of a matroid in [9]. There are several ways of
defining matroids. We take the one that will serve our purpose. A matroid $M$
is an ordered pair $(E,\mathscr{B})$ consisting of a finite set $E$ of
elements and a nonempty collection $\mathscr{B}$ of subsets of $E$, called
bases which satisfies the properties: (i) no proper subset of a base is a base
and (ii) if $B_{1},B_{2}\in\mathscr{B}$ and $e\in B_{1}\smallsetminus B_{2}$,
then there exists $f\in B_{2}\smallsetminus B_{1}$ such that
$(B_{1}\smallsetminus\left\\{e\right\\})\cup\left\\{f\right\\}\in\mathscr{B}$.
Independent sets of $M$ are subsets of bases and minimal dependent sets are
circuits. The cycle matroid $M[G]$ of graph $G$ is the matroid whose elements
are edges of $G$ and circuits are cycles of $G$. Independent sets and bases of
$M[G]$ are forests and maximal forests of $G$ respectively. A matroid is
graphic (simple graphic) if it is a cycle matroid of a graph (respectively,
simple graph).

Let $E$ be the set of column labels of an $n\times m$ matrix $A$ over a field
$F$, and $\mathscr{B}$ be the set of maximal subsets $X$ of $E$ for which the
multiset of columns labeled by $X$ is linearly independent in the vector space
$F^{m}$ over $F$. Then the pair $(E,\mathscr{B})$ is the column (vector)
matroid of $A$ and is denoted by $M[A]$. In particular, if $F=\mathbb{Z}_{2}$,
then $M[A]$ is a binary matroid. A binary matroid $M[A]$ is simple if $A$ does
not contain zero columns and no two columns of $A$ are identical (i.e.,
columns of $A$ are non-zero and distinct).

###### Definition 4

A binary matroid $M[A]$ is called a segment binary matroid if $A$ satisfies
the consecutive $1$’s property for columns. Moreover, if it is simple, then we
call it a simple segment binary matroid. For any $\emptyset\neq
S\subseteq\mathbb{Z}_{2}^{n-1}$, $M[S]$ denotes the column (vector) matroid of
the matrix whose columns are precisely the elements of $S$. Clearly, $M[S]$ is
a binary matroid.

###### Remark 2

In particular, when $\emptyset\neq S\subseteq C(n-1)$, $M[S]$ becomes a simple
segment binary matroid. So for any simple graph $G$ with $n$ vertices,
$M[\beta(G,n)]$ is a simple segment binary matroid. Conversely, every simple
segment binary matroid $M[A]$ with $n-1$ rows is same as $M[S]$, where $S$ is
the set of column vectors of $A$ over $\mathbb{Z}_{2}$. Also in this case
$S\subseteq C(n-1)$.

Two matroids $M_{1}=(E_{1},\mathscr{B}_{1})$ and
$M_{2}=(E_{2},\mathscr{B}_{2})$ are isomorphic if there is a bijection $\psi$
from $E_{1}$ onto $E_{2}$ such that for all $X\subseteq E_{1}$, $X$ is
independent in $M_{1}$ if and only if $\psi(X)$ is independent in $M_{2}$ (or,
equivalently, $X$ is a circuit in $M_{1}$ if and only if $\psi(X)$ is a
circuit in $M_{2}$). In this case, we denote by $M_{1}\cong M_{2}$. Also
abusing notations we sometimes identify elements of $M[A]$ with its
corresponding column vector representation. Thus a simple binary matroid
$M[A]$ may be considered as the set of column vectors of $A$. The following
theorem characterizes isomorphisms of simple binary matroids in terms of
linear transformations.

###### Theorem 3.1

Let $M[A]$ and $M[A_{1}]$ be two simple binary matroids such that both $A$ and
$A_{1}$ are of same order $n\times m$, $(m,n\in\mathbb{N})$. Then $M[A]\cong
M[A_{1}]$ if and only if there exists a bijective linear operator $T$ on
$\mathbb{Z}_{2}^{n}$ such that $T$ restricted on $M[A]$ is a bijective map
from $M[A]$ onto $M[A_{1}]$.

###### Proof

Let $\psi$ be an isomorphism from $M[A]$ onto $M[A_{1}]$. Let $B$ be a base in
$M[A]$. Then $B$ is linearly independent over $\mathbb{Z}_{2}$. We extend $B$
to a basis $B_{1}$ (say) of $\mathbb{Z}_{2}^{n}$ over $\mathbb{Z}_{2}$. Now
since $\psi$ is an isomorphism, $\psi(B)$ is also a base in $M[A_{1}]$ and
$|\psi(B)|=|B|$. We also extend $\psi(B)$ to $B_{2}$, a basis of
$\mathbb{Z}_{2}^{n}$ over $\mathbb{Z}_{2}$. Then $|B_{1}\smallsetminus
B|=|B_{2}\smallsetminus\psi(B)|=n-|B|$. Let $f$ be a bijection from
$B_{1}\smallsetminus B$ onto $B_{2}\smallsetminus\psi(B)$. Now define a map
$T_{1}\,:\,B_{1}\longrightarrow B_{2}$ by

$T_{1}(e)=\left\\{\begin{array}[]{ll}\psi(e),&e\in B\\\ f(e),&e\in
B_{1}\smallsetminus B\end{array}\right.$

We next verify that $\psi$ is ‘linear’ on $M[A]$, i.e., if $e_{1},e_{2}$ are
columns of $A$ such that $e_{1}+e_{2}$ is also a column of $A$, then
$\psi(e_{1}+e_{2})=\psi(e_{1})+\psi(e_{2})$. Let $e=e_{1}+e_{2}$. Then
$e+e_{1}+e_{2}=\mathbf{0}$ which implies that $\left\\{e,e_{1},e_{2}\right\\}$
is a circuit of $M[A]$. Again since $\psi$ is an isomorphism,
$\left\\{\psi(e),\psi(e_{1}),\psi(e_{2})\right\\}$ is also a circuit in
$M[A_{1}]$. Hence $\psi(e)+\psi(e_{1})+\psi(e_{2})=\mathbf{0}$, i.e.,
$\psi(e_{1}+e_{2})=\psi(e)=\psi(e_{1})+\psi(e_{2})$. This completes the
verification. We extend $T_{1}$ linearly to obtain a linear operator $T$ on
$\mathbb{Z}_{2}^{n}$ over $\mathbb{Z}_{2}$. Then $T$ is bijective as $T_{1}$
maps a basis bijectively to another basis of $\mathbb{Z}_{2}^{n}$ over
$\mathbb{Z}_{2}$ and the restriction of $T$ on $M[A]$ is $\psi$ due to the
above verification.

Conversely, let $T$ be a bijective linear operator on $\mathbb{Z}_{2}^{n}$
such that the map $\psi$, the restriction of $T$ on $M[A]$ is a bijective map
from $M[A]$ onto $M[A_{1}]$. Let $X$ be a circuit in $M[A]$. Then
$\displaystyle{\sum\limits_{e\in X}e=\mathbf{0}}$ and
$\displaystyle{\sum\limits_{e\in A}e\neq\mathbf{0}}$ for all $\emptyset\neq
A\subsetneqq X$. Now since $T$ is bijective and linear, we have
$\displaystyle{\sum\limits_{e\in A}e=\mathbf{0}}$ if and only if
$\displaystyle{\sum\limits_{e\in A}T(e)=\mathbf{0}}$ for all $\emptyset\neq
A\subseteq X$. Thus $X$ is a circuit in $M[A]$ if and only if $\psi(X)$ is a
circuit in $M[A_{1}]$. Hence $\psi$ is an isomorphism from $M[A]$ onto
$M[A_{1}]$.

###### Corollary 7

Let $M[A]$ and $M[A_{1}]$ be two simple binary matroids such that both $A$ and
$A_{1}$ are of same order $n\times m$, $(m,n\in\mathbb{N})$. Then $M[A]\cong
M[A_{1}]$ if and only if there exist a non-singular matrix $P$ of order
$n\times n$ and a permutation matrix $Q$ of order $m\times m$ such that
$PAQ=A_{1}$.

###### Proof

If $M[A]\cong M[A_{1}]$, then following the proof of the direct part of the
above theorem, consider two bases $B_{1}$ and $B_{2}$ of $\mathbb{Z}_{2}^{n}$
over $\mathbb{Z}_{2}$ and the bijective linear operator $T$ that maps $B_{1}$
onto $B_{2}$. Let $P$ be the matrix representation of $T$ with respect to
these bases. Then $P$ is a non-singular matrix and $PA=A_{2}$ where $A_{2}$ is
obtained from $A_{1}$ by rearranging columns such that $i^{\text{th}}$ column
of $A_{2}$ is the image of the $i^{\text{th}}$ column of $A$ under $T$. Thus
$PAQ=A_{1}$ for some permutation matrix $Q$.

Conversely, let $A_{1}=PAQ$ for some non-singular matrix $P$ and some
permutation matrix $Q$. Let $A_{2}=A_{1}Q^{-1}$. Then $PA=A_{2}$. Since $P$ is
non-singular, it corresponds to a bijective linear operator $T$ on
$\mathbb{Z}_{2}^{n}$ (over $\mathbb{Z}_{2}$) defined by $T(e)=Pe$ (considering
elements of $\mathbb{Z}_{2}^{n}$ as column matrices) such that the restriction
of $T$ on $M[A]$ is a bijective map from $M[A]$ onto $M[A_{2}]$. Then
$M[A]\cong M[A_{2}]$ by the above theorem. Since $M[A_{1}]=M[A_{2}]$, we have
$M[A]\cong M[A_{1}]$.

Now we proceed to characterize simple graphic matroids.

###### Lemma 2

Let $G$ be a simple graph with $n$ vertices. Then $M[G]\cong M[\beta(G,n)]$
for any coding sequence $\beta(G,n)$ of $G$.

###### Proof

It follows from Lemma 1 that cycles of $G$ are precisely the circuits of the
matroid $M[\beta(G,n)]$. So $M[G]\cong M[\beta(G,n)]$ as matroids.

###### Theorem 3.2

A matroid is simple graphic if and only if it is isomorphic to a simple
segment binary matroid.

###### Proof

Let $M$ be a simple graphic matroid. Then $M\cong M[G]$ for a simple graph
$G$. By Lemma 2, we have $M[G]\cong M[\beta(G,n)]$ where $n$ is the number of
vertices of $G$. Thus $M$ is isomorphic to a simple segment binary matroid by
Remark 2.

Conversely, let $M[A]$ be a simple segment binary matroid. Then we may
consider $M[A]$ as $M[S]$ where $S$ is the set of columns of $A$. By Remark 2,
we have $S\subseteq C(n-1)$, where $A\in M_{n-1,m}(\mathbb{Z}_{2})$. Then by
Definition 2, there is a unique simple graph $G$ such that $S=\beta(G,n)$.
Therefore, by Lemma 2, $M[S]=M[\beta(G,n)]\cong M[G]$. Thus, $M[A]$ is a
simple graphic matroid.

###### Corollary 8

A simple binary matroid $M[A]$ $($where $A$ is of order $(n-1)\times m)$ is
simple graphic if and only if $m\leqslant\binom{n}{2}$ and there exists a non-
singular matrix $P$ such that $PA$ satisfies the consecutive $1$’s property
for columns.

###### Proof

Follows from Theorem 3.2 and Corollary 7.

###### Remark 3

Since any non-singular matrix is obtained from identity matrix by finite
number of elementary row operations, a simple binary matroid $M[A]$ is simple
graphic if and only if the consecutive $1$’s property for columns can be
obtained from $A$ by finite number of elementary row operations.

It is well known [6] that an ordinary matroid isomorphism does not guarantee
the corresponding graph isomorphoism for graphic matroids. We now introduce
the concept of a strong isomorphism of simple segment binary matroids.

###### Definition 5

Two simple segment binary matroids $M[A_{1}]$ and $M[A_{2}]$ are called
strongly isomorphic if

  1. (1)

$A_{1},A_{2}\in M_{n-1,m}(\mathbb{Z}_{2})$ for some $m,n\in\mathbb{N}$,
$n\geqslant 2$.

  2. (2)

There exists a bijective linear operator $T$ on $\mathbb{Z}_{2}^{n-1}$ such
that:

    1. (i)

$T$ restricted on $C(n-1)$ is a bijection onto itself.

    2. (ii)

$T$ restricted on $M[A_{1}]$ is a bijective map from $M[A_{1}]$ onto
$M[A_{2}]$.

We write $M[A_{1}]\cong_{s}M[A_{2}]$ to denote that $M[A_{1}]$ is strongly
isomorphic to $M[A_{2}]$.

Note that, if $M[A_{1}]\cong_{s}M[A_{2}]$, then the restriction of $T$ on
$M[A_{1}]$ is a matroid isomorphism onto $M[A_{2}]$ and the restriction of $T$
on $C(n-1)$ is a matroid automorphism. These follow from the fact that $T$ is
linear and injective, as then for any subset $X$ of the set of columns of
$A_{1}$, $\sum\limits_{e\in X}e=\mathbf{0}$ if and only if $\sum\limits_{e\in
X}T(e)=\mathbf{0}$. In the sequel, we show that strong isomorphism of simple
segment binary matroids would guarantee the corresponding graph isomorphism.

Let $G=(V,E)$ be a (simple undirected) graph with $|V|=n$. Then for any $e\in
E$, we use the symbol $p\sim_{n}|10^{x}-10^{y}|$ if $f^{*}(e)=|10^{x}-10^{y}|$
and $p=f^{\\#}(e)\in\beta(G,n)$.

###### Lemma 3

Let $p_{1},p_{2}$ be distinct elements in $\beta(G,n)$ for any coding sequence
$\beta(G,n)$ of a graph $G$ with $n$ vertices. If
$p_{1}\sim_{n}|10^{x}-10^{y}|$ and $p_{2}\sim_{n}|10^{x}-10^{z}|$, then
$p_{1}+p_{2}\sim_{n}|10^{y}-10^{z}|$.

###### Proof

Let $p_{3}=p_{1}+p_{2}$. So $p_{1}+p_{2}+p_{3}=\mathbf{0}$. From the converse
part of the proof of Proposition 1, we have that $p_{3}$ corresponds to the
end points $10^{y}$ and $10^{z}$. Thus, $p_{1}+p_{2}\sim_{n}|10^{y}-10^{z}|$.

###### Lemma 4

Let $S=\\{e_{1},e_{2},\ldots,e_{k}\\}\subseteq\beta(G,n)$ for any coding
sequence $\beta(G,n)$ of a graph $G$ with $n$ vertices. Then $\tilde{G}(S)$
induces a path in $G$ if and only if $\sum\limits_{j=1}^{k}{e_{j}}\in C(n-1)$
and $S$ is reduced.

###### Proof

If $e_{1},e_{2},\ldots,e_{k}$ induce a path (in that order) then it is easy to
see that we have $e_{i}\sim_{n}|10^{x_{i+1}}-10^{x_{i}}|$ for some distinct
$x_{1},x_{2},\ldots,x_{k+1}\in\mathbb{N}\cup\\{0\\}$. By applying Lemma 3
repetitively, we have
$\sum\limits_{j=1}^{k}{e_{j}}\sim_{n}|10^{x_{k+1}}-10^{x_{1}}|$. Thus
$\sum\limits_{j=1}^{k}{e_{j}}\in C(n-1)$. Let $e=\sum\limits_{j=1}^{k}e_{j}$.
Then elements of $S\cup\left\\{e\right\\}$ form a cycle. Then by Lemma 1,
$S\cup\left\\{e\right\\}$ is reduced and so $S$ is reduced.

Conversely, let $\sum\limits_{j=1}^{k}{e_{j}}\in C(n-1)$ and $S$ is reduced.
Let $\sum\limits_{j=1}^{k}e_{j}=e$. So
$e+\sum\limits_{j=1}^{k}e_{j}=\mathbf{0}$ and since $S$ is reduced,
$S\cup\left\\{e\right\\}$ is also reduced. Now consider the graph $G^{\prime}$
such that $\beta(G^{\prime},n)=\beta(G,n)\cup\\{e\\}$. Clearly, $S\cup\\{e\\}$
induces a cycle in $\beta(G^{\prime},n)$ by Lemma 1. One edge of that cycle
corresponds to $e$, all the other edges correspond precisely to the members of
$S$. Hence, $\tilde{G}(S)$ induces a path in $G$.

###### Corollary 9

Suppose $p\sim_{n}|10^{i}-10^{j}|,q\sim_{n}|10^{r}-10^{s}|$ where $p\neq q$
and $i,j,r,s\in\\{0,1,2,\ldots,n-1\\}$. Then we have $p+q\in C(n-1)$ if and
only if $|\\{i,j\\}\cap\\{r,s\\}|=1$. Moreover, $p+q\sim_{n}|10^{x}-10^{y}|$,
where $x\in\left\\{i,j\right\\}$, $y\in\left\\{r,s\right\\}$ and
$x,y\notin\left\\{i,j\right\\}\cap\left\\{r,s\right\\}$.

###### Proof

Consider a graph $G$ with $n$ vertices such that $p,q\in\beta(G,n)$ for some
coding sequence $\beta(G,n)$ of $G$. Clearly, $p$ corresponds to end-points
$10^{i}$ and $10^{j}$, and $q$ corresponds to end-points $10^{r}$ and
$10^{s}$. First, let $p+q\in C(n-1)$. So by Lemma 4, it follows that
$\tilde{G}(\\{p,q\\})$ induces a path in $G$. This implies that the two edges
corresponding to $p$ and $q$ have a common vertex. Since $p\not=q$, this gives
that $|\\{i,j\\}\cap\\{r,s\\}|=1$.

Conversely, let $|\\{i,j\\}\cap\\{r,s\\}|=1$. Suppose $j=r$, without loss of
generality. Then by Lemma 3, $p+q\sim_{n}|10^{i}-10^{s}|$ (which proves the
next part also). Thus, $p+q\in C(n-1)$.

###### Lemma 5

Suppose
$p_{1}\sim_{n}|10^{i}-10^{j}|,p_{2}\sim_{n}|10^{k}-10^{l}|,p_{3}\sim_{n}|10^{r}-10^{s}|$,
where $i,j,k,l,r,s\in\\{0,1,2,\ldots,n-1\\}$ and $p_{1},p_{2},p_{3}$ are
distinct. If $p_{1}+p_{2},p_{2}+p_{3},p_{1}+p_{3}\in C(n-1)$, then either
$p_{1}+p_{2}+p_{3}=\mathbf{0}$ or
$\\{i,j\\}\cap\\{k,l\\}=\\{i,j\\}\cap\\{r,s\\}=\left\\{k,l\right\\}\cap\left\\{r,s\right\\}$.

###### Proof

Consider a graph $G$ with $n$ vertices such that
$p_{1},p_{2},p_{3}\in\beta(G,n)$ for some coding sequence $\beta(G,n)$ of $G$.
Clearly, $p_{1}$ corrsponds to end-points $10^{i}$ and $10^{j}$, $p_{2}$
corresponds to end-points $10^{k}$ and $10^{l}$ and $p_{3}$ corresponds to
end-points $10^{r}$ and $10^{s}$. Now since $p_{1}+p_{2}\in C(n-1)$, by
Corollary 9 we have $|\\{i,j\\}\cap\\{k,l\\}|=1$. Without loss of generality,
let $j=k$. Then $10^{j}$ is the common end-point between edges corresponding
to $p_{1}$ and $p_{2}$. Since we also have that $p_{1}+p_{3}\in C(n-1)$ and
$p_{2}+p_{3}\in C(n-1)$, it follows that the edge corresponding to $p_{3}$ has
a common end-point with the edge corresponding to $p_{1}$ and a common end-
point with the edge correponding to $p_{2}$. If the common end-point in both
the cases is $10^{j}(=10^{k})$ then we have
$\\{i,j\\}\cap\\{k,l\\}=\\{i,j\\}\cap\\{r,s\\}=\left\\{k,l\right\\}\cap\left\\{r,s\right\\}$.
Otherwise, the common end-point between $p_{1}$ and $p_{3}$ must be $10^{i}$
and the common end-point between $p_{2}$ and $p_{3}$ must be $10^{l}$. Thus,
edges corresponding to $p_{1},p_{2},p_{3}$ form a cycle involving the vertices
$10^{i},10^{j},10^{l}$. So by Proposition 1, we have
$p_{1}+p_{2}+p_{3}=\mathbf{0}$.

###### Lemma 6

Let $G,H$ be two simple graphs with $n$ vertices each and suppose
$M[\beta(G,n)]\cong_{s}M[\beta(H,n)]$. Let $T$ be any bijective linear
operator on $\mathbb{Z}_{2}^{n-1}$ giving a strong isomorphism between
$M[\beta(G,n)]$ and $M[\beta(H,n)]$. Then for $e_{1},e_{2}\in C(n-1)$, we have
$e_{1}+e_{2}\in C(n-1)$ if and only if $T(e_{1})+T(e_{2})\in C(n-1)$.

###### Proof

Let $e_{1},e_{2}\in\beta(G,n)$. First, let $e_{1}+e_{2}\in C(n-1)$. Now
$T(e_{1})+T(e_{2})=T(e_{1}+e_{2})\in T(C(n-1))=C(n-1)$ as restriction of $T$
maps $C(n-1)$ onto itself. Conversely, let $T(e_{1})+T(e_{2})\in C(n-1)$. So
$T(e_{1}+e_{2})\in C(n-1)$. Again since restriction of $T$ maps $C(n-1)$ onto
itself, there exists some $e$ in $C(n-1)$ such that $T(e)=T(e_{1}+e_{2})$.
Finally, since $T$ is injective, we have $e=e_{1}+e_{2}$. So $e_{1}+e_{2}\in
C(n-1)$.

Now we prove the theorem which gives a necessary and sufficient condition for
two simple graphs to be isomorphic.

###### Theorem 3.3

Let $G$ and $H$ be two simple graphs of $n$ vertices each. Then $G\cong H$ if
and only if $M[\beta(G,n)]\cong_{s}M[\beta(H,n)]$ for any coding sequences
$\beta(G,n)$ and $\beta(H,n)$ of $G$ and $H$, respectively.

###### Proof

We consider vertices of both $G$ and $H$ are labeled by
$1,10,10^{2},\ldots,10^{n-1}$. First, let $G\cong H$. So there exists a
permutation $g$ on the set $\\{0,1,2,\ldots,n-1\\}$ such that for any
$r,s\in\\{0,1,2,\ldots,n-1\\}$, we have $10^{r}$ and $10^{s}$ are adjacent in
$G$ if and only if $10^{g(r)}$ and $10^{g(s)}$ are adjacent in $H$. We
consider the graphs $K^{(1)},K^{(2)}$, where $K^{(1)}=G\cup\bar{G}$ and
$K^{(2)}=H\cup\bar{H}$, where $\bar{G}$ and $\bar{H}$ are complements of
graphs $G$ and $H$ respectively. Now for each $e\in C(n-1)$, if
$e\sim_{n}|10^{i}-10^{j}|$, we define $T(e)\sim_{n}|10^{g(i)}-10^{g(j)}|$.
Clearly, $T$ is a well-defined mapping from $C(n-1)$ into itself, since
$|10^{p}-10^{q}|$ uniquely determines the pair $\\{p,q\\}$ for any $p,q$.

Now $g$, being a permutation, is a bijection. Suppose $e_{1},e_{2}$ are
distinct elements of $C(n-1)$. Let $e_{1}\sim_{n}|10^{a}-10^{b}|$ and
$e_{2}\sim_{n}|10^{c}-10^{d}|$. Clearly, $\\{a,b\\}\not=\\{c,d\\}$.
Bijectiveness of $g$ implies that $\\{g(a),g(b)\\}\not=\\{g(c),g(d)\\}$. This
shows that $T(e_{1})\not=T(e_{2})$. So we have that $T$ is one-to-one. Since
$T$ is a mapping from a finite set into itself, injectiveness of $T$ implies
that $T$ is a bijective mapping from $C(n-1)$ onto itself. Again, since
$10^{r}$ and $10^{s}$ are adjacent in $G$ if and only if $10^{g(r)}$ and
$10^{g(s)}$ are adjacent in $H$ for distinct $r,s\in\\{0,1,2,\ldots,n-1\\}$,
we have that $T$ restricted on $\beta(G,n)$ is a mapping from $\beta(G,n)$
into $\beta(H,n)$. Injectiveness of $T$ ensures the injectiveness of $T$
restricted to $\beta(G,n)$. Since $\beta(G,n)$ and $\beta(H,n)$ are finite
sets with equal cardinality, we have that $T$ restricted to $\beta(G,n)$ is a
bijection from $\beta(G,n)$ onto $\beta(H,n)$.

Next we observe that $T$ is ‘linear’ on $C(n-1)$, i.e., if $p,q\in C(n-1)$
such that $p+q\in C(n-1)$, then $T(p)+T(q)=T(p+q)$. Let
$p\sim_{n}|10^{i}-10^{j}|$, $q\sim_{n}|10^{r}-10^{s}|$ such that $p+q\in
C(n-1)$. Then by Corollary 9, we have
$|\left\\{i,j\right\\}\cap\left\\{r,s\right\\}|=1$. Without loss of
generality, we assume $j=r$. So $g(j)=g(r)$ and $p+q\sim_{n}|10^{i}-10^{s}|$.
Now $T(p)\sim_{n}|10^{g(i)}-10^{g(j)}|$ and
$T(q)\sim_{n}|10^{g(r)}-10^{g(s)}|$. Since $g(j)=g(r)$, we have $T(p)+T(q)\in
C(n-1)$ and $T(p)+T(q)\sim_{n}|10^{g(i)}-10^{g(s)}|$. Since
$T(p+q)\sim_{n}|10^{g(i)}-10^{g(s)}|$, we have $T(p+q)=T(p)+T(q)$.

Now let $e_{i}\sim_{n}|10^{i}-10^{i-1}|$ for all $i=1,2,\ldots,n$. We know
that $B=\\{e_{i}\mid i=1,2,\ldots,n\\}$ is a basis of $\mathbb{Z}_{2}^{n-1}$.
Since $T$ is defined on each $e_{i}$ as the latter is in $C(n-1)$ (in fact,
$T(e_{i})\sim_{n}|10^{g(i)}-10^{g(i-1)}|$), we can extend $T$ linearly to a
linear operator $T_{1}$ on $\mathbb{Z}_{2}^{n-1}$. Bijectiveness of $T_{1}$
follows from injectiveness of $T$ on $C(n-1)$ (which ensures distinct images
under $T$ for distinct elements of $B$, thus ensuring injectiveness of
$T_{1}$) and finiteness of $\mathbb{Z}_{2}^{n-1}$. As $M[\beta(G,n)]$ and
$M[\beta(H,n)]$ are also of the same order, we have
$M[\beta(G,n)]\cong_{s}M[\beta(H,n)]$.

Conversely, let $M[\beta(G,n)]\cong_{s}M[\beta(H,n)]$. So there exists a
bijective linear operator $T$ satisfying the properties mentioned in the
Definition 5. We find a permutation $g$ on the set $\\{0,1,2,\ldots,n-1\\}$
such that for any distinct $r,s\in\\{0,1,2,\ldots,n-1\\}$, $10^{r}$ and
$10^{s}$ are adjacent in $G$ if and only if $10^{g(r)}$ and $10^{g(s)}$ are
adjacent in $H$. Clearly, such a $g$ acts as an isomorphism between $G$ and
$H$. Now for $i=1,2,\ldots,n$, define $e_{i}$ as the element in $C(n-1)$ which
has 1 in its $i^{\text{th}}$ co-ordinate from the right ($(n-i)^{\text{th}}$
co-ordinate from the left) and 0 in remaining coordinates. Then
$e_{i}\sim_{n}|10^{i}-10^{i-1}|$. Now for $i=1,2,\ldots,n-1$, we have
$e_{i}+e_{i+1}\in C(n-1)$. So from Lemma 6, we have $T(e_{i})+T(e_{i+1})\in
C(n-1)$. From Corollary 9, the edges corresponding to $T(e_{i})$ and
$T(e_{i+1})$ have a (unique) common point, say $10^{x}$. We define $g(i-1)=x$.
This defines $g$ as a mapping from $\left\\{0,1,2,\ldots,n-2\right\\}$ into
$\\{0,1,2,\ldots,n-1\\}$. Now we show that $g$ is one-to-one.

If possible, let $g(i-1)=g(j-1)$ for some $i\not=j$,
$i,j\in\left\\{1,2,\ldots,n-1\right\\}$. By the above definition of $g$,
$g(i-1)$ and $g(j-1)$ are one of the common end points of
$T(e_{i}),T(e_{i+1})$ and $T(e_{j}),T(e_{j+1})$ respectively. So the edges
corresponding to $T(e_{i})$ and $T(e_{j})$ have a common end-point $g(i-1)$
($=g(j-1)$). So from Corollary 9, we have $T(e_{i})+T(e_{j})\in C(n-1)$.
Linearity of $T$ implies that $T(e_{i}+e_{j})\in C(n-1)$. Since $T$ restricted
to $C(n-1)$ is a bijection from $T$ onto itself, we have $e_{i}+e_{j}\in
C(n-1)$. Again, $e_{j}+e_{i+1}\in C(n-1)$ for the same reason as $g(i-1)$ is a
common end-point between edges corresponding to $T(e_{j})$ and $T(e_{i+1})$.
We also have $e_{i}+e_{i+1}\in C(n-1)$. So
$e_{i}+e_{j},e_{i+1}+e_{i},e_{j}+e_{i+1}\in C(n-1)$. If possible, let
$e_{i}+e_{j}+e_{i+1}=\mathbf{0}$. However, then $e_{j}=e_{i}+e_{i+1}$, which
is impossible by definition of $e_{i}$’s. Thus, from Lemma 5, $10^{i}$ is
either $10^{j}$ or $10^{j-1}$, i.e., $i=j$ or $j-1$. Similar argument on
$e_{i},e_{j},e_{j+1}$ gives us $j=i$ or $i-1$. But $i=j-1$ and $j=i-1$ both
cannot be true simultaneously. So we have $i=j$ which is a contradiction. Thus
$g$ is injective. So we define $g(n-1)=x$, where
$x\in\left\\{0,1,2,\ldots,n-1\right\\}\smallsetminus\left\\{g(0),g(1),\ldots,g(n-2)\right\\}$.
Then $g$ is defined on $\left\\{0,1,2,\ldots,n-1\right\\}$ into itself.
Moreover since $g$ is injective, it is a permutation on the set
$\\{0,1,2,\ldots,n-1\\}$.

## References

  * [1]
  * [2]
  * [3] W. K. Chen, _On vector spaces associated with a graph_ , SIAM J. Appl. Math. 20 (1971), 526–529.
  * [4] Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science, Prentice Hall of India Pvt. Ltd., 1997.
  * [5] R. Gould, _Graphs and vector spaces_ , J. Math. Phys. 37 (1958), 193–214.
  * [6] J. G. Oxley, Matroid Theory, Oxford University Press, 1992.
  * [7] W. T. Tutte, _Matroids and graphs_ , Trans. Amer. Math. Soc. 90 (1959), 527–552.
  * [8] D. B. West, Introduction to Graph Theory, Prentice-Hall of India Pvt.Ltd., 2003.
  * [9] H. Whitney, _On the Abstract Properties of Linear Dependence_ , American Journal of Mathematics 57 (1935), 509–533.
  * [10]


# Beyond Distributional Hypothesis: Let Language Models Learn
Meaning-Text Correspondence

Myeongjun Jang1 Frank Mtumbuka1 Thomas Lukasiewicz2,1
1 Department of Computer Science, University of Oxford, UK
2 Institute of Logic and Computation, TU Wien, Austria
<EMAIL_ADDRESS>

###### Abstract

The logical negation property (LNP), which implies generating different
predictions for semantically opposite inputs ($p$ is true iff $\lnot p$ is
false), is an important property that a trustworthy language model must
satisfy. However, much recent evidence shows that large-size pre-trained
language models do not satisfy this property. In this paper, we perform
experiments using probing tasks to assess PLMs’ LNP understanding. Unlike
previous studies that only examined negation expressions, we expand the
boundary of the investigation to lexical semantics. Through experiments, we
observe that PLMs violate the LNP frequently. To alleviate the issue, we
propose a novel intermediate training task, named meaning-matching, designed
to directly learn a meaning-text correspondence, instead of relying on the
distributional hypothesis. Through multiple experiments, we find that the task
enables PLMs to learn lexical semantic information. Also, through fine-tuning
experiments on 7 GLUE tasks, we confirm that it is a safe intermediate task
that guarantees a similar or better performance of downstream tasks. Finally,
we observe that our proposed approach111https://github.com/MJ-Jang/beyond-
distributional outperforms our previous counterparts despite its time and
resource efficiency.

Beyond Distributional Hypothesis: Let Language Models Learn
Meaning-Text Correspondence

Myeongjun Jang1 Frank Mtumbuka1 Thomas Lukasiewicz2,1 1 Department of Computer
Science, University of Oxford, UK 2 Institute of Logic and Computation, TU
Wien, Austria<EMAIL_ADDRESS>

##  1 Introduction

Contemporary large-size PLMs, such as BERT Devlin et al. (2019), ELECTRA Clark
et al. (2020), and GPT-2 and -3 Radford et al. (2019); Brown et al. (2020),
have shown excellent results in many downstream tasks, even performing better
than humans in the GLUE Wang et al. (2018) and SuperGLUE Wang et al. (2019b)
benchmark datasets.

However, their reliability is recently being challenged. Many studies have
conducted various probing tasks and observed that PLMs exhibit faulty
behaviours, such as insensitiveness to sentence ordering Pham et al. (2021);
Gupta et al. (2021); Sinha et al. (2021b), incomprehension on number-related
representations Wallace et al. (2019); Lin et al. (2020); Nogueira et al.
(2021), and lack of semantic content understanding Ravichander et al. (2020);
Elazar et al. (2021). These issues raise concerns about PLMs’ stability and
reliability, precluding them from applications in practice, especially in
risk-sensitive areas.

Another critical problem of PLMs is their inaccurate behaviour on negation,
which is a principal property in many language understanding tasks. For tasks
where the LNP holds ($p$ is true iff $\lnot p$ is false; see Aina et al.
2018), PLMs should make different answers for the original and negated inputs.
However, several studies observed that PLMs violate this property. In masked
knowledge retrieval tasks, PLMs frequently generate incorrect answers for
negated input queries Ettinger (2020); Kassner and Schütze (2020). In other
studies, PLMs show a poor generalisation ability on negated natural language
inference (NLI) datasets Naik et al. (2018); Hossain et al. (2020).

Although the aforementioned studies produced promising analysis results, they
limited the scope of the LNP only to adding negation expressions (e.g., “no”
and “not”). However, other perturbations that generate the opposite meaning
also can be applied to the property. Therefore, a consideration of such
perturbation methods is necessary to fully assess whether PLMs satisfy the
LNP.

Also, remedies to alleviate the problem have not been studied much yet.
Hosseini et al. (2021) recently employed data augmentation and unlikelihood
training Welleck et al. (2020) to prevent models from generating unwanted
words, given the augmented negated data during masked language modelling
(MLM). However, this approach has several downsides. First, like previous
works, Hosseini et al. (2021) only considered negation expressions. Second,
the data augmentation method is contingent on many additional linguistic
components, which causes the dependency of a model’s performance on certain
modules and precludes applying the method to other languages where such
resources are unavailable. Finally, the model should be pre-trained from
scratch with the unlikelihood objective, which consumes considerable time and
resources.

In this paper, we expand the boundary of the LNP to lexical semantics, i.e.,
synonyms and antonyms, and ascertain that PLMs are prone to violate the LNP.
Next, we propose a remedy, called intermediate-training on meaning-matching
($\textrm{I}\textrm{M}^{2}$), which hardly employs additional linguistic
components. We hypothesise that a leading cause lies in the MLM training
objective, which assumes the distributional hypothesis for learning the
meaning of the text Sinha et al. (2021a). Instead, we design a model that
directly learns the correspondence between words and their semantic contents.
Through experiments, we verify that our approach improves the model’s
comprehension of the LNP, while showing a stable performance on multiple
downstream tasks.

Our main contributions are as follows: (1) We extend the investigation of the
LNP from negation to lexical semantics (Section 2), (2) we reveal that PLMs
are prone to violate the LNP (Section 3), (3) we propose a novel remedy, named
$\textrm{I}\textrm{M}^{2}$, which is decoupled from the distributional
hypothesis but learns meaning-text correspondence instead (Section 4), (4)
through experiments, we ascertain that the proposed approach improves the
understanding of negation and lexical semantic information (Sections 5.1 and
5.2), and (5) we verify that meaning-matching is a stable and safe
intermediate task that produces a similar or better performance in multiple
downstream tasks (Sections 5.3 and 5.4).

(a) MKR-NQ

(b) MWR

(c) SAR

Figure 1: Illustration of the MKR-NQ, MWR, and SAR tasks.

##  2 Probing Tasks for Investigating the Logical Negation Property

We design three probing tasks to evaluate whether PLMs satisfy the LNP: masked
knowledge retrieval on negated queries (MKR-NQ), masked word retrieval (MWR),
and synonym/antonym recognition (SAR). Brief illustrations of each task are in
Figure 1.

###  2.1 Masked Knowledge Retrieval on Negated Queries

The MKR-NQ task examines whether PLMs generate incorrect answers for negated
queries. Following the work of Kassner and Schütze (2020), we constructed the
evaluation dataset by negating the LAMA dataset Petroni et al. (2019), which
contains masked free-text forms of ConceptNet Speer et al. (2017) triplets and
their corresponding answers (e.g., (bird, CapableOf, fly) $\rightarrow$ (“A
bird can [MASK]”, fly)). The task aims to generate a correct word through MLM.

According to the LNP, a model must not generate the original answer if the
query is negated. To measure how likely PLMs generate wrong predictions for
negated queries, we collected pairs of (negated_query, wrong_predictions). We
selected several relations in the LAMA dataset that ensure mutual
exclusiveness between the original and negated queries.222For example, the
HasProperty relation is not suitable to use, because sentences like “Some
adults are immature” and “Some adults are not immature” are not mutually
exclusive. For negating sentences, we selected LAMA data points that contain a
single verb using the Spacy parts of speech (POS) tagger Honnibal and Johnson
(2015). Next, we added negation expressions, such as “not” and “don’t”, or
removed such expressions if they existed. Finally, we collected the wrong
predictions from ConceptNet by using the head entity and relation. As a
result, we collected 3,360 data points for this task. The list of the
relations that we used and examples of the data are in Table 10 in Appendix A.

###  2.2 Masked Word Retrieval

To expand the boundary of the LNP to lexical semantics, we design the MWR
task, which generates an answer of a masked query, asking for the
synonym/antonym of a target word through MLM (e.g., “happy is the synonym of
[MASK]”).

Let $s_{w}$ and $a_{w}$ denote masked queries that ask the synonym and antonym
of the word $w$, respectively. Also, let $A_{s}$ and $A_{a}$ refer to the list
of correct answers for $s_{w}$ and $a_{w}$, respectively. Intuitively, $A_{a}$
becomes the wrong predictions of $s_{w}$, because $s_{w}$ and $a_{w}$ have the
opposite meaning. Therefore, we can evaluate the violation of the LNP by
investigating whether a PLM generates wrong predictions.

To extract commonly-used words for our experiment, we first extracted nouns,
adjectives, and adverbs that appear more than five times in the SNLI dataset
Bowman et al. (2015). Among the extracted candidates, we filtered words that
have synonyms or antonyms in ConceptNet. Finally, we generated masked queries
by employing templates used by Camburu et al. (2020). As a result, we
collected about 27K data points for MWR. The templates and examples of the
data are in Table 11 in Appendix A.

###  2.3 Synonym/Antonym Recognition

SAR is a classification that distinguishes whether two given words are
synonyms or antonyms. It aims to evaluate whether the contextualised
representations of PLMs reflect the lexical meaning of words. Therefore, we
use a parametric probing model Adi et al. (2017); Liu et al. (2019a); Belinkov
and Glass (2019); Sinha et al. (2021a) for the experiment. Specifically, the
experiment is performed on the final layer of each PLMs, i.e., we only train
the classifier while keeping the encoder frozen. We use ConceptNet to build
the dataset. ConceptNet has much more synonym triplets compared to antonyms.
As a result, we randomly sample the synonym triplets to maintain a balance. To
that end, we collect 33K, 1K, and 2K data points for the train, dev, and test
datasets, respectively.

###  2.4 Evaluation Metrics

We use the top-$k$ hit rate (HR@$k$) to evaluate the performance on the MKR-NQ
and MWR tasks. Assume that
$P=\\{(p_{1},c_{1}),(p_{2},c_{2}),\ldots,(p_{n},c_{n})\\}$ denotes the set of
predictions for a data point $x$, where $p_{t}$ and $c_{t}$ refer to the
predicted word and confidence score of the $t$-th prediction, respectively.
Then, the top-$k$ hit rate for a data point $x$ is defined as follows:

$\mathit{HR}@k(x)=\frac{\sum_{i=1}^{k}\mathbbm{1}(p_{i}\in\mathcal{W}_{x})}{k},$

where $\mathcal{W}_{x}$ is the wrong prediction set of $x$. Intuitively, the
metric measures the ratio of top-$k$ predicted words that belong to the wrong
prediction set.

To reflect the prediction confidence score to the evaluation metric, we
additionally define the weighted top-$k$ hit rate (WHR@$k$) that uses the
confidence score as weights. It is worth to mention that lower metrics mean a
better model performance in both cases as the metrics assess how likely the
models make inaccurate answers that they must avoid. The weighted metric can
be defined as follows:

$\mathit{WHR}@k(x)=\frac{\sum_{i=1}^{k}c_{i}\times\mathbbm{1}(p_{i}\in\mathcal{W}_{x})}{\sum_{i=1}^{k}c_{i}}.$

For the SAR task, we employ accuracy as an evaluation metric, because each
data point has its own label, and the label distribution is not skewed.

Model | MKR-NQ | MWR
---|---|---
HR@1 | HR@3 | WHR@3 | HR@5 | WHR@5 | HR@1 | HR@3 | WHR@3 | HR@5 | WHR@5
BERT-base | 9.57 | 6.38 | 8.42 | 5.00 | 7.81 | 35.03 | 18.83 | 28.71 | 13.26 | 26.03
BERT-large | 13.33 | 7.70 | 11.17 | 6.03 | 10.51 | 36.66 | 20.45 | 29.68 | 14.60 | 26.56
RoBERTa-base | 11.52 | 6.85 | 9.63 | 5.30 | 8.91 | 13.02 | 8.47 | 10.50 | 6.54 | 9.32
RoBERTa-large | 15.72 | 9.25 | 13.31 | 6.86 | 12.24 | 27.92 | 17.07 | 23.06 | 12.84 | 20.82
ALBERT-base | 4.24 | 3.75 | 4.24 | 3.26 | 4.09 | 26.37 | 14.95 | 22.10 | 10.75 | 20.32
ALBERT-large | 9.22 | 6.38 | 7.96 | 4.94 | 7.30 | 50.77 | 25.05 | 42.67 | 17.03 | 39.09
Table 1: Overall results for the MKR-NQ and MWR experiments. We multiply 100 to each value to improve readability. Note that the lower the values the better. | BERT | RoBERTa | ALBERT
---|---|---|---
base | large | base | large | base | large
$\mathcal{R}_{syn}$ | 37.79 | 36.58 | 17.13 | 46.01 | 11.37 | 76.10
$\mathcal{R}_{ant}$ | 41.44 | 41.79 | 13.57 | 30.21 | 33.26 | 62.65
Table 2: Ratios of instances that PLMs regenerate the word in the input
sentence. $\mathcal{R}_{syn}$ and $\mathcal{R}_{ant}$ are the ratios of
synonym and antonym-asking questions, respectively.

##  3 PLMs Lack Information of Negation and Lexical Semantics

We select the following PLMs for the experiments: bidirectional encoder
representations from transformers (BERT)-base/large Devlin et al. (2019),
RoBERTa-base/large Liu et al. (2019b), and ALBERT-base/large Lan et al.
(2019). These PLMs are pre-trained with the MLM training objective. We added
the ELECTRA-small/base/large models Clark et al. (2020) for the SAR task, but
it is not used for the MKR-NQ and MWR experiments, as the discriminator of the
ELECTRA models are trained with the replaced token prediction (RTP) training
objective and have no MLM classifier. No additional training is required for
the MKR-NQ and MWR tasks. For the SAR task, we fine-tune each PLM for 10
epochs and apply the early stopping technique. We use the AdamW optimiser
Loshchilov and Hutter (2019) for training with a learning rate of $5e^{-6}$
and a batch size of 32.

###  3.1 Results for MKR-NQ

The results for the MKR-NQ task are summarised in Table 1. In general, the
results are consistent with previous works Ettinger (2020); Kassner and
Schütze (2020). We observe three important characteristics from the
experimental results.

First, large models produce a higher hit rate than their corresponding base-
size models in all three PLMs, recording an average of about 1.5 times higher
values. This implies that large-size models are more likely to generate wrong
predictions for negated queries, even though they perform better than small-
size models in many benchmark tests. The results suggest that evaluating a
model’s performance solely based on the accuracy metric is unwise.

Second, the hit rate decreases as $k$ increases, which implies that the
majority of PLMs’ top predictions (e.g., $k$=1 or $k$=2) are incorrect.
Finally, the weighted hit rate is much higher than the vanilla hit rate,
suggesting that PLMs generate wrong predictions with high confidence.

Model | Encoder-fixed | Fine-tune
---|---|---
$\mathcal{A}_{val}$ | $\mathcal{A}_{test}$ | $\mathcal{A}_{val}$ | $\mathcal{A}_{test}$
BERT-base (108M) | 53.1 | 55.0 | 84.0 | 85.6
BERT-large (333M) | 54.4 | 53.5 | 92.1 | 92.5
RoBERTa-base (124M) | 71.1 | 70.1 | 87.2 | 87.8
RoBERTa-large (355M) | 69.7 | 69.1 | 93.7 | 94.2
ALBERT-base (11M) | 56.6 | 58.1 | 81.5 | 84.0
ALBERT-large (17M) | 54.7 | 56.6 | 86.9 | 88.0
ELECTRA-small (13M) | 64.1 | 63.9 | 80.2 | 80.9
ELECTRA-base (109M) | 67.9 | 70.6 | 93.3 | 92.9
ELECTRA-large (334M) | 69.4 | 72.7 | 95.9 | 95.4
Table 3: Results of the SAR experiment. $\mathcal{A}_{val}$ and
$\mathcal{A}_{test}$ are the accuracy of the validation and test dataset,
respectively. We record the average of five repetitions.

###  3.2 Results for MWR

The results of the MWR task are summarised in Table 1. The three
characteristics found in the MKR-NQ task are also observed in the MWR task.
Also, we found the following additional patterns.

####  PLMs lack knowledge of antonyms.

In general, the hit rates are extremely high compared to the MKR-NQ task in
all the PLMs. Analysing their predictions, we find that PLMs generate
incorrect predictions primarily in antonym-asking queries. Specifically, the
average HR@1 of the antonym-asking queries is 41.9%, while that of the
synonym-asking queries is only 1.4%. A leading cause is that PLMs simply
replicate the word presented in the input query. Table 2 shows the ratio of
instances where each PLM reproduces the same word in a question. While the
values are quite high for both synonym-asking and antonym-asking queries, the
problem is more severe in the latter case, because the generated predictions
are definitely incorrect. Based on our results, we conclude that PLMs’
contextualised representations lack lexical semantic information. Our
conclusion is in line with the findings of Liu et al. (2019a) showing that
encoder-fixed PLMs are not suitable to deal with tasks that require fine-
grained linguistic knowledge.

#### Issues are more severe with nouns.

We observe that the hit rates are higher when a word in a question is a noun.
Specifically, the average HR@1 values of nouns, adjectives, and adverbs are
35.1%, 27.4%, and 11.8%, respectively. Interestingly, PLMs have a high error
rate when dealing with nouns even though they are trained with a large written
English corpus, where nouns form the greatest portion (at least 37%) of all
POS tags Hudson (1994); Liang and Liu (2013).

###  3.3 Results for SAR

As part of the comparison, we fine-tune each PLM on the SAR task, i.e., train
the entire set of parameters. The results are summarised in Table 3. We
observe a huge gap between the performance of fine-tuned models and that of
encoder-fixed models. In contrast to the fine-tuned models that produce a high
accuracy, encoder-fixed models fall short of expectations, even recording
almost a random guess performance in BERT models. Also, just as a common
belief, large models’ performance is greatly improved when fine-tuned.
However, the difference between the large and small encoder-fixed models is
insignificant, except for the ELECTRA models that exhibit only a marginal
improvement. The two phenomenons suggest that PLMs’ outstanding performance is
predicated on updating many parameters to learn syntactic associations
presented in training data Niven and Kao (2019); McCoy et al. (2019), but
their contextualised representations do not carry abundant lexical meaning
information.

##  4 Intermediate Training on Meaning Matching Task:
$\textrm{I}\textrm{M}^{2}$

###  4.1 Issue of PLMs

Through the previous experiments, we observe that PLMs contain little
information about negation and especially lexical semantics. We hypothesise a
leading cause lies in the training objective of PLMs: the language modelling
(LM) objective, which is a backbone pre-training task of almost all PLMs.

In the LM objective, words are generated based on given contexts. The
distributional hypothesis Harris (1954), which assumes that semantically
related or similar words will appear in similar contexts Mrkšić et al. (2016),
is the underpinning assumption of the LM objective Sinha et al. (2021a). Under
this assumption, a model learns the meaning of texts based on their
correlation to others. This is a great benefit, because a model can learn the
meaning of texts using only the text form, allowing unsupervised training.
Based on this advantage, many unsupervised representations, such as Word2Vec
Mikolov et al. (2013), Glove Pennington et al. (2014), and current PLMs, have
been developed.

However, the problem is that the distributional hypothesis has limitations in
reflecting a word’s semantic meanings, because words having different or even
opposite semantic meanings can appear in similar or the same contexts. For
instance, consider the two words “boy” and “girl”. We can readily imagine
sentences in which the two words appear in the same context, e.g., “the little
boy/girl cuddled the teddy bear closely”. As a result, a model can learn their
common functional meanings, i.e., young human beings, and the vector
representations would be very similar if they were trained based on the
distributional hypothesis. However, the representation hardly captures their
semantic antonomy, e.g., gender. Similarly, negated sentences have almost
identical contexts to their original forms. As a result, models cannot
effectively learn the semantic meaning of words and negation expressions,
provided they leverage only the text forms.

Model | MKR-NQ | MWR
---|---|---
HR@1 | HR@3 | WHR@3 | HR@5 | WHR@5 | HR@1 | HR@3 | WHR@3 | HR@5 | WHR@5
BERT-large | 13.33 | 7.70 | 11.17 | 6.03 | 10.51 | 36.66 | 20.45 | 29.68 | 14.60 | 26.56
BERT-large ($\textrm{I}\textrm{M}^{2}$) | 11.41 | 7.01 | 9.86 | 5.57 | 9.14 | 18.92 | 13.07 | 15.78 | 10.30 | 14.14
RoBERTa-large | 15.72 | 9.25 | 13.31 | 6.86 | 12.24 | 27.92 | 17.07 | 23.06 | 12.84 | 20.82
RoBERTa-large ($\textrm{I}\textrm{M}^{2}$) | 6.56 | 4.97 | 6.05 | 3.99 | 5.67 | 22.08 | 12.68 | 18.94 | 9.20 | 17.63
Table 4: Results of BERT-large and RoBERTa-large after applying the $\textrm{I}\textrm{M}^{2}$ approach. We multiply 100 to each value for a better readability. Note that the lower the values the better. Model | Encoder-fixed | Fine-tune
---|---|---
$\Delta\mathcal{A}_{val}$ | $\Delta\mathcal{A}_{test}$ | $\Delta\mathcal{A}_{val}$ | $\Delta\mathcal{A}_{test}$
BERT-base (108M) |  +5.5* |  +5.1* |  +3.9* |  +3.0*
BERT-large (333M) |  +3.1* |  +6.3* | +1.0 | +0.2
RoBERTa-base (124M) |  +4.5* |  +5.9* |  +1.3* |  +1.6*
RoBERTa-large (355M) |  +15.0* |  +17.1* | +0.6 | +0.5
ALBERT-base (11M) | -2.6 | +2.5 |  +4.7* |  +3.3*
ALBERT-large (17M) | +1.3 | +1.4 | +1.2 | +1.6
ELECTRA-small (13M) |  -4.1* |  -2.7* | +1.1 | +1.1
ELECTRA-base (109M) |  +3.8* |  +3.2* | -0.2 | +0.7
ELECTRA-large (334M) |  +14.0* |  +10.2* | +0.4 | +0.5
Table 5: PLMs’ accuracy change in the SAR task when we apply
$\textrm{I}\textrm{M}^{2}$. We record the average across 5 runs. Our models
show a statistically significant difference with $p$-value $<$ 0.05 (*)
compared to the baseline results in Table 3.

###  4.2 Meaning-Matching Task

In the light of meaning-text theory, there is a correspondence between
linguistic expressions (text) and semantic contents (meaning) Mel’čuk and
Žolkovskij (1970); Milićević (2006). Instead of solely relying on the
distributional hypothesis, we propose the new meaning-matching task, which can
directly learn the correspondence. Specifically, meaning-matching is a
classification that takes a word and a sentence as input and determines
whether the sentence defines the word correctly. Through this task, a model
can learn both meaning-text correspondences and correlations between a word
and other words in a definition, which is rarely found in general corpora.

For training PLMs on our new task, we apply the intermediate-training
technique Phang et al. (2018); Wang et al. (2019a); Liu et al. (2019a);
Pruksachatkun et al. (2020); Vu et al. (2020), which first fine-tunes PLMs on
an intermediate task, and then fine-tunes the model again on target tasks. It
has been shown that training on intermediate tasks that require high-level
linguistic knowledge and inference ability could improve performance Liu et
al. (2019a); Pruksachatkun et al. (2020). Furthermore, it is more efficient in
time and resources than pre-training models on large corpora (e.g., BERTNOT
model Hosseini et al. (2021)).

#### Dataset.

We collect about 150K free-text definitions that depict the meaning of English
words from WordNet Miller (1995) and the English Word, Meaning, and Usage
Examples dataset.333https://data.world/idrismunir/english-word-meaning-and-
usage-examples/ In cases when a word appears in both datasets, we concatenate
the word’s definitions. Several examples of our data are presented in Table 12
in Appendix A. We use publicly available English datasets for convenience, but
our approach is easily adaptable to other languages, since most of them have
their own dictionaries.

Figure 2: The performance of the RoBERTa-base ($\textrm{I}\textrm{M}^{2}$)
model with different $k$ values. We repeat each experiments for five times and
record their average.

#### Training details.

It is necessary to generate false word-definition pairs to train PLMs on the
meaning-matching task. To achieve this, we use a negative sampling technique.
We investigate the proper $k$ in the range of 3, 5, 10, and 20. For a
hyperparameter search, the performance of the RoBERTa-base model on the SAR
task is used as a criterion. Figure 2 illustrates the SAR performance of the
RoBERTa-base model with different $k$ values. Intuitively, a large $k$ value
will lead the model to a better performance by investigating more word-meaning
combinations. However, we observe that the model performs the best when $k$ is
10, and the performance decreases if $k$ is too large. We conjecture that a
leading cause is that the dataset contains many words with similar meanings,
mostly derived from the same stem. As a result, large $k$ values can increase
the possibility of recognising the meaning of such similar words as different.

To avoid the class-imbalance issue in a batch, we duplicate the correct word-
definition pairs $k$ times when we construct the training data. For training,
the AdamW optimiser is used with a learning rate of $5e^{-6}$. We use 5% of
data points for validation and train the models for 15 epochs with a batch
size of 32. The early stopping technique is used to prevent overfitting.

##  5 Experiments and Results

We conduct the same probing tasks after the intermediate training on the
meaning-matching task.444Our models trained with the meaning-match task can be
downloaded from the following repositories: ELECTRA-large, BERT-large,
RoBERTa-large.

Query: demand is an antonym of [MASK]
---
RoBERTa-large |  RoBERTa-large ($\textrm{I}\textrm{M}^{2}$)
demand |  supply
Query: tomorrow is the opposite of [MASK]
BERT-large |  BERT-large ($\textrm{I}\textrm{M}^{2}$)
tomorrow |  today
Query: question is an antonym of [MASK]
BERT-large |  BERT-large ($\textrm{I}\textrm{M}^{2}$)
question |  answer
Table 6: Examples of top-1 predictions on MWR queries. Unlike the original
PLMs, our models do not reproduce a word in a query and make quite accurate
predictions.

###  5.1 SAR Results

We first focus on the SAR task. After the intermediate training, all models
are fine-tuned on the SAR task with the same hyperparameters described in
Section 3. The results are summarised in Table 5.

#### Improved lexical semantic information.

We generally observe marginal or no significant improvements when fine-tuning
the whole parameters, especially for large-size PLMs. However, with fixed
encoder, the performance is significantly improved for PLMs with more than
100M parameters, and the improvements are more significant for large PLMs. Our
results show that the proposed approach assists PLMs to learn enhanced
representations with more abundant lexical semantic information.

Figure 3: Frobenius norm box plots of PLMs’ layer after intermediate training on the meaning-matching task. Model | COLA | MNLI-m | MNLI-mm | QNLI | RTE | QQP | MRPC | SST2
---|---|---|---|---|---|---|---|---
BERT-large | 59.6$\pm$1.1 | 85.5$\pm$0.4 | 85.3$\pm 0.5$ |  91.7$\pm$0.1 | 65.5$\pm$2.6 | 89.9$\pm$0.2 | 80.9$\pm$2.0 | 92.3$\pm$0.3
BERT-large ($\textrm{I}\textrm{M}^{2}$) |  61.5$\pm$1.0 |  85.7$\pm$0.1 |  85.5$\pm$0.1 | 91.6$\pm$0.2 |  66.8$\pm$1.0 |  90.0$\pm$0.1 |  82.8$\pm$1.1 |  92.4$\pm$0.3
RoBERTa-large | 62.9$\pm$1.9 | 90.2$\pm$0.1 |  90.0$\pm$0.2 |  94.5$\pm$0.1 | 81.7$\pm$1.8 | 90.9$\pm$0.4 | 87.2$\pm$1.1 |  95.7$\pm$0.1
RoBERTa-large ($\textrm{I}\textrm{M}^{2}$) |  64.8$\pm$2.1 |  90.3$\pm$0.1 | 89.9$\pm$0.1 | 94.4$\pm$0.1 |  83.1$\pm$1.4 |  91.0$\pm$0.0 |  88.2$\pm$1.5 | 95.4$\pm$0.3
ELECTRA-large | 68.4$\pm$2.3 |  90.9$\pm$0.1 | 90.7$\pm$0.2 |  94.5$\pm$0.3 | 86.9$\pm$2.2 | 91.6$\pm$0.5 | 88.9$\pm$1.5 |  96.7$\pm$0.1
ELECTRA-large ($\textrm{I}\textrm{M}^{2}$) |  69.1$\pm$0.7 | 90.8$\pm$0.1 |  90.7$\pm$0.1 | 94.3$\pm$0.2 |  87.0$\pm$1.3 |  91.7$\pm$0.3 |  89.5$\pm$0.5 | 96.4$\pm$0.4
Table 7: GLUE benchmark validation performance of PLMs before and after
intermediate training on the meaning-matching task. Matthew’s correlation for
the COLA and accuracy for the other tasks are used as an evaluation metric. We
report the mean and standard deviation across 5 runs. The best values for each
PLM are in bold.

#### Catastrophic forgetting.

We find that small PLMs, such as ELECTRA-small and ALBERT models, show no
significant increase in performance or are negatively impacted. Because all
PLMs achieve a comparable performance on the meaning-matching task, we
hypothesise that a leading cause is catastrophic forgetting Pruksachatkun et
al. (2020); Wallat et al. (2020), where the model forgets previous knowledge
learned through pre-training to accept new information from the intermediate
task. To verify this, we measure the change of parameter values after
$\textrm{I}\textrm{M}^{2}$. Concretely, let $M_{i}$ and $M^{mm}_{i}$ denote
the parameter of $i$-th layer before and after $\textrm{I}\textrm{M}^{2}$. We
calculate the average Frobenius norm for each layer:

$\mathcal{F}_{i}=\frac{1}{|M_{i}|}|M_{i}-M^{mm}_{i}|_{F}.$

Figure 3 shows the boxplots of $\mathcal{F}_{i}$ for each PLMs. We observe
that the parameters of the ELECTRA-small model, which is negatively impacted,
are changed considerably compared to other PLMs having parameters more than
100M. The results suggest that the size of PLMs is an important property to
prevent the catastrophic forgetting issue.

###  5.2 MKR-NQ and MWR Results

Next, we perform the MKR-NQ and MWR tasks after applying the
$\textrm{I}\textrm{M}^{2}$ method. Since our models are not trained with the
MLM objective, we replace the encoder of original PLMs with that of the models
after fine-tuning on the meaning-matching task and reuse the MLM classifier.
For the experiments, we use BERT-large and RoBERTa-large, because they are
pre-trained based on the MLM objective, and parameters are hardly changed
after applying the $\textrm{I}\textrm{M}^{2}$ method. The results are
summarised in Table 4.

We observe substantial decreases in the hit rates of incorrect predictions in
both PLMs. For the MWR task, we find that the issue of regenerating a word in
a given query is greatly relieved after applying the
$\textrm{I}\textrm{M}^{2}$ method. Specifically, the percentage of such
instances drops from 40.3% to 19.6% and from 33.8% to 25.2% for BERT-large and
RoBERTa-large, respectively. Several examples of the predicted results are
presented in Table 6. The results lend support to our claim that the
$\textrm{I}\textrm{M}^{2}$ approach is of benefit to learning lexical semantic
information and the meaning of negated expressions.

###  5.3 Fine-Tuning on the GLUE Benchmark

A critical drawback of intermediate training is that the target task
performance could be negatively impacted if the intermediate task is not
related to the target task Liu et al. (2019a); Pruksachatkun et al. (2020). To
confirm whether the issue occurs, we compare the performance of BERT, RoBERTa,
and ELECTRA-large on 7 GLUE benchmark datasets Wang et al. (2018) with their
$\textrm{I}\textrm{M}^{2}$ counterparts. We train the models for 10 epochs for
each dataset and apply the early stopping technique where the patience number
is set to 3. It is observed that the training is generally finished within 8
epochs for all the models. The batch size per GPU and learning rates used for
each dataset are described in Table 8. Datasets with large training set (e.g.,
MNLI, QNLI, and QQP) were not sensitive to the hyperparameters.

| COLA | MNLI | QNLI | RTE | QQP | MRPC | SST2
---|---|---|---|---|---|---|---
b-size | 16 | 64 | 64 | 8 | 64 | 8 | 64
lr | $2e^{-5}$ | $1e^{-5}$ | $1e^{-5}$ | $2e^{-5}$ | $1e^{-5}$ | $1e^{-5}$ | $1e^{-5}$
Table 8: Batch size and learning rates used for the GLUE benchmark
experiments.

The results are presented in Table 7. We find no significant difference in
performance for tasks with large datasets, such as MNLI, QNLI, QQP, and SST2.
On the contrary, tasks with small datasets, like MRPC and RTE, are slightly
improved. The result is consistent with Pruksachatkun et al. (2020) and Vu et
al. (2020), which showed that smaller tasks benefit much more from the
intermediate training. Furthermore, unlike the previous studies that observed
a negative transfer with the COLA dataset Phang et al. (2018); Pruksachatkun
et al. (2020), the performance is improved in our approach. The result
suggests that meaning-matching is a safe intermediate task that ensures a
positive transfer with target downstream tasks.

Model | SNLI | MNLI
---|---|---
dev | w/neg | dev | w/neg
BERTNOT | 89.0$\pm$0.1 | 46.0$\pm$0.4 |  84.3$\pm$2.3 | 60.9$\pm$0.3
BERT-$\textrm{I}\textrm{M}^{2}$ |  90.3$\pm$0.2 |  48.00$\pm$0.5 | 83.1$\pm$0.3 |  61.8$\pm$0.6
Table 9: Accuracies on the original development dataset (dev) and the NegNLI
(w/neg) dataset for SNLI and MNLI tasks. The results of our approach are
averaged across 5 runs. The best values are in bold.

###  5.4 Experiments on the NegNLI Dataset

Finally, we conduct experiments on the NegNLI benchmark dataset Hossain et al.
(2020), where negation plays an important role for NLI tasks. As a baseline,
we compare the reported performance of BERTNOT Hosseini et al. (2021), which
is a recently proposed remedy to improve PLMs’ ability to understand negation.
Since Hosseini et al. (2021) used BERT-base as a backbone model, we also apply
the $\textrm{I}\textrm{M}^{2}$ method to BERT-base. The results are summarised
in Table 9.

For both SNLI and MNLI, we observe that our approach outperforms BERTNOT in
the NegNLI datasets, while yielding a comparable performance in the original
development datasets. It is interesting that our approach improves the
understanding of negation in both MKR-NQ and NegNLI tasks. We conjecture that
a leading cause is that the definitions of the meaning-matching dataset
contain many negation expressions, which enables a model to learn their
proposed meaning (see Table 12). The results suggest that our proposed
approach is more efficient than BERTNOT, because the
$\textrm{I}\textrm{M}^{2}$ method leverages less time and resources for
training.

##  6 Related Work

PLMs are at the core of many success stories in natural language processing
(NLP). However, it remains unclear to what extent PLMs understand the
syntactic and semantic properties of the human language. A series of probing
tasks have been conducted on PLMs and have found them lacking or falling short
on some language properties. Among the many findings of these probing tasks,
PLMs have been found to be insensitive to the order of sentences when
generating representations Pham et al. (2021); Gupta et al. (2021); Sinha et
al. (2021a), struggle to comprehend number-related representations Wallace et
al. (2019); Lin et al. (2020); Nogueira et al. (2021), and display a lack of
semantic content understanding Ravichander et al. (2020); Elazar et al.
(2021).

In addition to the above faulty behaviours, Ettinger (2020) and Kassner and
Schütze (2020) show that PLMs fail to comprehend negation, which is an
important property of language in many natural language understanding (NLU)
tasks. Ettinger (2020) check the ability of PLMs to understand the meaning of
negation in given contexts. In their work, they check whether models are
sensitive in their completions of sentences that either include negation or
not. Under normal circumstances, the completions are expected to vary in truth
depending on the presence or absence of negation in given sentences. Their
results show that PLMs are insensitive to the impacts of negations when
completing sentences. Kassner and Schütze (2020) construct the negated LAMA
dataset by inserting negation elements (e.g., “not”) in the LAMA cloze
questions Petroni et al. (2019). They use negated and original question pairs
to query PLMs and establish that models are equally prone to make the same
predictions for both the original and negated questions. In a well-informed
setting, it is expected that PLMs should make different predictions for the
original and negated questions. This shows that PLMs struggle to comprehend
negation.

In light of the highlighted faulty behaviours of PLMs, especially their
struggle to comprehend negation, Hosseini et al. (2021) propose a remedy to
alleviate the problem. In their remedy, they augment the language modelling
objective with an unlikelihood objective Welleck et al. (2020) based on
negated sentences from the training corpus. They use a syntactic augmentation
method to generate negated sentences. In this method, the dependency parse of
the sentences, POS tags, and morphological information of each word are taken
as input, and the negation of sentences is done using sets of dependency tree
regular expression patterns, such as Semgrex Chambers et al. (2007). During
training, they replace objects in negated sentences with [MASK] tokens and use
unlikelihood training to make the masked-out tokens unlikely under the PLM
distribution. To ensure that negated sentences are factually false, they use
the corresponding positive sentences as context for the unlikelihood
prediction task.

Previous studies (e.g., Kassner and Schütze (2020)) have mostly limited the
scope of the logical negation property only to the negation expressions (e.g.,
“no” and “not”). However, the core spirit of this property is the opposite
meaning, which is not only limited to the negation. Welleck et al. (2020)
consider negating sentences using dependency tree regular expression patterns.
This widens the scope of negation, as it is not only limited to the negation
expressions “no” and “not”. However, their approach relies on other
components, such as Semgrex, and dependency and POS parsers, which could
impact the quality of the data, hence impact the models’ performance. In this
work, we consider other perturbation methods to generate the opposite-meaning
sentences to investigate whether PLMs satisfy the logical negation property,
and we propose a remedy, called intermediate-training on meaning-matching
($\textrm{I}\textrm{M}^{2}$), which hardly employs additional linguistic
components.

##  7 Summary and Outlook

In this work, we investigated PLMs’ LNP. Compared to previous works that only
examine negation expressions, we expanded the boundary of LNP to lexical
semantics. We confirmed that PLMs are likely to violate LNP through extensive
experiments.

We hypothesise that the distributional hypothesis is an insufficient basis for
understanding the semantic meaning of texts. To alleviate the issue, we
proposed a novel intermediate task: meaning-matching. Via experiments, we
verified that meaning-matching is a stable intermediate task that
substantially improves PLMs’ understanding of negation and lexical semantic
information while guaranteeing a positive transfer with multiple downstream
tasks. Also, our approach produces a better performance on the negated NLI
datasets compared to the unlikelihood training-based method, which leverages
much more time and resources. Our work suggests that it is time to move beyond
the distributional hypothesis to develop logically consistent and stable
language models.

LNP

    logical negation property
BERT

    bidirectional encoder representations from transformers
BiLSTM

    bidirectional LSTM
DL

    deep learning
KG

    knowledge graph
MLM

    masked language modelling
NLI

    natural language inference
NLP

    natural language processing
NLU

    natural language understanding
NN

    neural network
PLM

    pre-trained language model
SOTA

    state-of-the-art
POS

    parts of speech
MKR-NQ

    masked knowledge retrieval on negated queries
MWR

    masked word retrieval
SAR

    synonym/antonym recognition
RTP

    replaced token prediction
LM

    language modelling
QA

    question answering
STS

    semantic textual similarity

## Acknowledgements

This work was partially supported by the Alan Turing Institute under the EPSRC
grant EP/N510129/1, by the AXA Research Fund, by the EPSRC grant EP/R013667/1,
and by the ESRC grant “Unlocking the Potential of AI for English Law”. We also
acknowledge the use of Oxford’s ARC facility, of the EPSRC-funded Tier 2
facilities JADE (EP/P020275/1) and JADE 2 (EP/T022205/1), and of GPU computing
support by Scan Computers International Ltd. Frank Mtumbuka was supported by
the Rhodes Trust under a Rhodes Scholarship.

## References

  * Adi et al. (2017) Yossi Adi, Einat Kermany, Yonatan Belinkov, Ofer Lavi, and Yoav Goldberg. 2017.  Fine-grained analysis of sentence embeddings using auxiliary prediction tasks.  _International Conference on Learning Representations_.
  * Aina et al. (2018) Laura Aina, Raffaella Bernardi, and Raquel Fernández. 2018.  A distributional study of negated adjectives and antonyms.  In _Proceedings of the 5th Italian Conference on Computational Linguistics (CLiC-it 2018)_ , volume 2253 of _CEUR Workshop Proceedings_.
  * Belinkov and Glass (2019) Yonatan Belinkov and James Glass. 2019.  Analysis methods in neural language processing: A survey.  _Transactions of the Association for Computational Linguistics_ , 7:49–72.
  * Bowman et al. (2015) Samuel R. Bowman, Gabor Angeli, Christopher Potts, and Christopher D. Manning. 2015\.  A large annotated corpus for learning natural language inference.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing (EMNLP 2015)_ , pages 632–642.
  * 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.
  * Camburu et al. (2020) Oana-Maria Camburu, Brendan Shillingford, Pasquale Minervini, Thomas Lukasiewicz, and Phil Blunsom. 2020.  Make up your mind! Adversarial generation of inconsistent natural language explanations.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 4157–4165.
  * Chambers et al. (2007) Nathanael Chambers, Daniel Cer, Trond Grenager, David Hall, Chloe Kiddon, Bill MacCartney, Marie-Catherine de Marneffe, Daniel Ramage, Eric Yeh, and Christopher D. Manning. 2007.  Learning alignments and leveraging natural logic.  In _Proceedings of the ACL-PASCAL Workshop on Textual Entailment and Paraphrasing_ , pages 165–170.
  * Clark et al. (2020) Kevin Clark, Minh-Thang Luong, Quoc V. Le, and Christopher D. Manning. 2020.  ELECTRA: Pre-training text encoders as discriminators rather than generators.  _International Conference on Learning Representations_.
  * 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.
  * Elazar et al. (2021) Yanai Elazar, Nora Kassner, Shauli Ravfogel, Abhilasha Ravichander, Eduard Hovy, Hinrich Schütze, and Yoav Goldberg. 2021.  Measuring and improving consistency in pretrained language models.  _Transactions of the Association for Computational Linguistics_ , 9:1012–1031.
  * Ettinger (2020) Allyson Ettinger. 2020.  What BERT is not: Lessons from a new suite of psycholinguistic diagnostics for language models.  _Transactions of the Association for Computational Linguistics_ , 8:34–48.
  * Gupta et al. (2021) Ashim Gupta, Giorgi Kvernadze, and Vivek Srikumar. 2021.  Bert & family eat word salad: Experiments with text understanding.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 12946–12954.
  * Harris (1954) Zellig S. Harris. 1954.  Distributional structure.  _Word_ , 10(2-3):146–162.
  * Honnibal and Johnson (2015) Matthew Honnibal and Mark Johnson. 2015.  An improved non-monotonic transition system for dependency parsing.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing (EMNLP 2015)_ , pages 1373–1378.
  * Hossain et al. (2020) Md Mosharaf Hossain, Venelin Kovatchev, Pranoy Dutta, Tiffany Kao, Elizabeth Wei, and Eduardo Blanco. 2020.  An analysis of natural language inference benchmarks through the lens of negation.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP 2020)_ , pages 9106–9118.
  * Hosseini et al. (2021) Arian Hosseini, Siva Reddy, Dzmitry Bahdanau, R. Devon Hjelm, Alessandro Sordoni, and Aaron Courville. 2021.  Understanding by understanding not: Modeling negation in language models.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 1301–1312.
  * Hudson (1994) Richard Hudson. 1994.  About 37% of word-tokens are nouns.  _Language_ , 70(2):331–339.
  * Kassner and Schütze (2020) Nora Kassner and Hinrich Schütze. 2020.  Negated and misprimed probes for pretrained language models: Birds can talk, but cannot fly.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7811–7818.
  * Lan et al. (2019) Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. 2019.  ALBERT: A lite BERT for self-supervised learning of language representations.  In _International Conference on Learning Representations_.
  * Liang and Liu (2013) Junying Liang and Haitao Liu. 2013.  Noun distribution in natural languages.  _Poznań Studies in Contemporary Linguistics_ , 49(4):509–529.
  * Lin et al. (2020) Bill Yuchen Lin, Seyeon Lee, Rahul Khanna, and Xiang Ren. 2020.  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 2020)_ , pages 6862–6868.
  * Liu et al. (2019a) Nelson F. Liu, Matt Gardner, Yonatan Belinkov, Matthew E. Peters, and Noah A. Smith. 2019a.  Linguistic knowledge and transferability of contextual representations.  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 1073–1094.
  * Liu et al. (2019b) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019b.  RoBERTa: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Loshchilov and Hutter (2019) Ilya Loshchilov and Frank Hutter. 2019.  Decoupled weight decay regularization.  In _International Conference on Learning Representations_.
  * McCoy et al. (2019) Tom McCoy, Ellie Pavlick, and Tal Linzen. 2019.  Right for the wrong reasons: Diagnosing syntactic heuristics in natural language inference.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 3428–3448.
  * Mel’čuk and Žolkovskij (1970) I. A. Mel’čuk and A. K. Žolkovskij. 1970.  Towards a functioning ’meaning-text’ model of language.  _Linguistics_ , 8(57):10–47.
  * Mikolov et al. (2013) Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S. Corrado, and Jeff Dean. 2013.  Distributed representations of words and phrases and their compositionality.  In _Advances in Neural Information Processing Systems_ , volume 26. Curran Associates, Inc.
  * Milićević (2006) Jasmina Milićević. 2006.  A short guide to the meaning-text linguistic theory.  _Journal of Koralex_ , 8:187–233.
  * Miller (1995) George A. Miller. 1995.  WordNet: A lexical database for English.  _Communications of the ACM_ , 38(11):39–41.
  * Mrkšić et al. (2016) Nikola Mrkšić, Diarmuid Ó Séaghdha, Blaise Thomson, Milica Gašić, Lina M. Rojas-Barahona, Pei-Hao Su, David Vandyke, Tsung-Hsien Wen, and Steve Young. 2016.  Counter-fitting word vectors to linguistic constraints.  In _Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 142–148.
  * Naik et al. (2018) Aakanksha Naik, Abhilasha Ravichander, Norman Sadeh, Carolyn Rose, and Graham Neubig. 2018.  Stress test evaluation for natural language inference.  In _Proceedings of the 27th International Conference on Computational Linguistics_ , pages 2340–2353.
  * Niven and Kao (2019) Timothy Niven and Hung-Yu Kao. 2019.  Probing neural network comprehension of natural language arguments.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4658–4664.
  * Nogueira et al. (2021) Rodrigo Nogueira, Zhiying Jiang, and Jimmy Lin. 2021.  Investigating the limitations of transformers with simple arithmetic tasks.  _arXiv preprint arXiv:2102.13019_.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014.  GloVe: Global vectors for word representation.  In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP 2014)_ , pages 1532–1543.
  * Petroni et al. (2019) Fabio Petroni, Tim Rocktäschel, Sebastian Riedel, Patrick Lewis, Anton Bakhtin, Yuxiang Wu, and Alexander Miller. 2019.  Language models as knowledge bases? 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 2019)_ , pages 2463–2473.
  * Pham et al. (2021) Thang Pham, Trung Bui, Long Mai, and Anh Nguyen. 2021.  Out of order: How important is the sequential order of words in a sentence in natural language understanding tasks? In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 1145–1160, Online. Association for Computational Linguistics.
  * Phang et al. (2018) Jason Phang, Thibault Févry, and Samuel R. Bowman. 2018.  Sentence encoders on stilts: Supplementary training on intermediate labeled-data tasks.  _CoRR_ , abs/1811.01088.
  * Pruksachatkun et al. (2020) Yada Pruksachatkun, Jason Phang, Haokun Liu, Phu Mon Htut, Xiaoyi Zhang, Richard Yuanzhe Pang, Clara Vania, Katharina Kann, and Samuel R. Bowman. 2020\.  Intermediate-task transfer learning with pretrained language models: When and why does it work? In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 5231–5247.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9.
  * Ravichander et al. (2020) Abhilasha Ravichander, Eduard Hovy, Kaheer Suleman, Adam Trischler, and Jackie Chi Kit Cheung. 2020.  On the systematicity of probing contextualized word representations: The case of hypernymy in BERT.  In _Proceedings of the 9th Joint Conference on Lexical and Computational Semantics_ , pages 88–102.
  * Sinha et al. (2021a) Koustuv Sinha, Robin Jia, Dieuwke Hupkes, Joelle Pineau, Adina Williams, and Douwe Kiela. 2021a.  Masked language modeling and the distributional hypothesis: Order word matters pre-training for little.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing (EMNLP 2021)_ , pages 2888–2913.
  * Sinha et al. (2021b) Koustuv Sinha, Prasanna Parthasarathi, Joelle Pineau, and Adina Williams. 2021b.  UnNatural Language Inference.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 7329–7346.
  * 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 31st AAAI Conference on Artificial Intelligence_.
  * Vu et al. (2020) Tu Vu, Tong Wang, Tsendsuren Munkhdalai, Alessandro Sordoni, Adam Trischler, Andrew Mattarella-Micke, Subhransu Maji, and Mohit Iyyer. 2020.  Exploring and predicting transferability across NLP tasks.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP 2020)_ , pages 7882–7926.
  * Wallace et al. (2019) Eric Wallace, Yizhong Wang, Sujian Li, Sameer Singh, and Matt Gardner. 2019.  Do NLP models know numbers? probing numeracy in embeddings.  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 2019)_ , pages 5307–5315.
  * Wallat et al. (2020) Jonas Wallat, Jaspreet Singh, and Avishek Anand. 2020.  BERTnesia: Investigating the capture and forgetting of knowledge in BERT.  In _Proceedings of the Third BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP_ , pages 174–183.
  * Wang et al. (2019a) Alex Wang, Jan Hula, Patrick Xia, Raghavendra Pappagari, R. Thomas McCoy, Roma Patel, Najoung Kim, Ian Tenney, Yinghui Huang, Katherin Yu, Shuning Jin, Berlin Chen, Benjamin Van Durme, Edouard Grave, Ellie Pavlick, and Samuel R. Bowman. 2019a.  Can you tell me how to get past Sesame Street? Sentence-level pretraining beyond language modeling.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4465–4476.
  * Wang et al. (2019b) Alex Wang, Yada Pruksachatkun, Nikita Nangia, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. 2019b.  SuperGLUE: A stickier benchmark for general-purpose language understanding systems.  In _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc.
  * Wang et al. (2018) Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. 2018.  GLUE: A multi-task benchmark and analysis platform for natural language understanding.  In _Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_ , pages 353–355.
  * Welleck et al. (2020) Sean Welleck, Ilia Kulikov, Stephen Roller, Emily Dinan, Kyunghyun Cho, and Jason Weston. 2020.  Neural text generation with unlikelihood training.  In _International Conference on Learning Representations_.

##  Appendix A Appendix: Examples

Relation | Negated Query | Wrong Predictions
---|---|---
IsA | Truth isn’t a [MASK]. | [“fact”, “statement”, “concept”, “actuality”]
CapableOf | A doctor cannot [MASK] you. | [“care”]
PartOf | England isn’t part of the [MASK]. | [“Europe”]
HasA | Apples don’t have [MASK] inside them. | [“stems”, “seeds”]
UsedFor | A map isn’t for [MASK]. | [“navigate”, “locating”, “navigating”, “orienteering”, “information”]
MadeOf | Air doesn’t have [MASK]. | [“molecules”]
NotDesires | Soldier does want to be [MASK]. | [“die”]
Table 10: ConceptNet relations for constructing the MKR-NQ dataset and their corresponding sample data points. Template | Query | Wrong Predictions
---|---|---
X is a synonym of Y | boy is a synonym of [MASK]. | [“sister”, “girl”]
X is an antonym of Y | boy is an antonym of [MASK]. | [“boys”, “brat”, “man”, “boy”, “lad”, …]
X is another form of Y | learning is another form of [MASK]. | [“forgetting”, “teaching”]
X is the opposite of Y | learning is the opposite of [MASK]. | [“knowledge”, “erudition”, “eruditeness”, “learning”]
X is a rephrasing of Y | speaker is a rephrasing of [MASK]. | [“microphone”, “listener”, “addressee”]
X is different from Y | speaker is different from [MASK]. | [“loudspeaker”, “transducer”, “talker”, “speaker”, …]
Table 11: Templates used to construct the MWR dataset and their sample data points. Word |  Definition
---|---
abnormal | not normal; not typical or usual or regular or conforming to a norm; out of ordinary; unusual
afebrile | having no fever
barefaced | with no effort to conceal
career |  the particular occupation for which you are trained; a job or occupation that a person does for an extended period
cargo | goods carried by a large vehicle
revise | the act of rewriting something; to review, alter and amend, especially of written material
salary |  something that remunerates; a determined yearly amount of money paid to an employee by an employer during a job
Table 12: Examples of word-definition pairs that we used for the meaning-
matching task.

  *[LNP]: logical negation property
  *[PLMs]: pre-trained language model
  *[NLI]: natural language inference
  *[MLM]: masked language modelling
  *[MKR-NQ]: masked knowledge retrieval on negated queries
  *[MWR]: masked word retrieval
  *[SAR]: synonym/antonym recognition
  *[POS]: parts of speech
  *[PLM]: pre-trained language model
  *[BERT]: bidirectional encoder representations from transformers
  *[RTP]: replaced token prediction
  *[LM]: language modelling
  *[NLP]: natural language processing
  *[NLU]: natural language understanding