# A tight bound for the number of edges of matchstick graphs

Jérémy Lavollée and Konrad Swanepoel

###### Abstract.

A matchstick graph is a plane graph with edges drawn as unit-distance line
segments. Harborth introduced these graphs in 1981 and conjectured that the
maximum number of edges for a matchstick graph on $n$ vertices is $\lfloor
3n-\sqrt{12n-3}\rfloor$. In this paper we prove this conjecture for all $n\geq
1$. The main geometric ingredient of the proof is an isoperimetric inequality
related to L’Huilier’s inequality.

###### Key words and phrases:

matchstick graph, penny graph, plane unit-distance graph

###### 2020 Mathematics Subject Classification:

Primary 52C10. Secondary 05C10

##  1\. Introduction

A _matchstick graph_ is a graph drawn in the Euclidean plane with each edge a
straight unit-length segment, such that two edges only intersect in a common
endpoint. These graphs were introduced by Harborth [11, 12] in 1981. Most of
the literature deals with matchstick graphs which are regular [3, 8, 9, 14,
16, 15, 21, 26] or almost regular [18, 22, 23, 24, 25]. There are also a few
papers dealing with more general aspects, such as enumeration [20] and
algorithmic recognition [1, 13]. Harborth considered the extremal problem of
finding the minimum number $n$ of vertices in a matchstick graph on $e$ edges,
or equivalently, the maximum number of edges for a given number of vertices.
He conjectured in [12] that $e\leq 3n-\sqrt{12n-3}$ (see also [4]*p. 225) and
proved this in the special case of penny graphs using a neat induction on the
number of vertices [10] (see also [19]*Theorem 13.12). A _penny graph_ is a
matchstick graph with the additional property that the circles of radius $1/2$
around the vertices are non-overlapping.

######  Theorem 1 (Harborth [10]).

Let $G$ be a matchstick graph on $n$ vertices such that the distance between
any two vertices is at least $1$. Then the number of edges of $G$ satisfies
$e\leq 3n-\sqrt{12n-3}$.

For each $n\geq 1$ there are examples on the triangular lattice with $n$
vertices and the optimal $\lfloor 3n-\sqrt{12n-3}\rfloor$ edges [10, 19].
Proving Harborth’s conjecture in general turns out to be trickier. Using the
isoperimetric inequality (Lemma 1) we showed in [17] that $e\leq
3n-c\sqrt{12n-3}$, where $c=\frac{1}{2}(1+\sqrt{\pi\sqrt{3}/6})=0.976\dots$,
which implies Harborth’s conjecture for some small values of $n$. In this
paper we settle the conjecture completely.

######  Theorem 2.

Let $G$ be a matchstick graph with $n$ vertices and $e$ edges. Then $e\leq
3n-\sqrt{12n-3}$.

As in our previous paper [17], as a first step we use the Euler formula and
the isoperimetric inequality.

######  Lemma 1 (Isoperimetric inequality).

For any simple polygon of perimeter $b$ and area $A$ we have $4\pi A<b^{2}$.

However, we will then exploit a different isoperimetric inequality that takes
into account that many edges on the outer boundary of $G$ lie on the same
triangular lattice. A variant of the isoperimetric inequality in the plane,
known as L’Huilier’s inequality, states that among all polygons of a given
perimeter for which the sides are constrained to be parallel to a given set of
directions, the one of maximum area is circumscribed to a circle [6]*pp. 9–10,
[7]*pp. 12–13. In particular, among all closed polygons of a given perimeter
with each side parallel to one of the sides of a fixed regular hexagon, the
regular hexagon is optimal. We prove the following variant of this special
case where we allow a certain bounded amount of the perimeter to be
unconstrained in direction.

######  Lemma 2.

Let $P$ be a simple polygon with perimeter $b$, area $A$, and with the total
length of the sides not parallel to any side of some fixed regular hexagon at
most $b_{*}$. Then

$8\sqrt{3}A\leq\bigl{(}b+\bigl{(}\tfrac{2}{\sqrt{3}}-1\bigr{)}b_{*}\bigr{)}^{2}.$

Our proof of Theorem 2 has an analytical flavour, with many inequalities
appearing in it that are rather weak, with constants that could easily be
improved. Surprisingly, this turns out to be unnecessary. The inequalities
also often need $n$ to be large, which creates the potential problem that this
approach will only work for sufficiently large $n$. However, the original
isoperimetric inequality allows us to dismiss all values of $n<147$ early on
in the proof. Then the rest of the proof goes through, although there are many
inequalities that have to be checked. This can be done by hand or by apps such
as Wolfram Alpha or Desmos. We have to balance the asymptotics with constant
terms in order to make the inequalities valid for small $n$. It is rather
strange that such an approach manages to make the induction succeed for all
values of $n$.

###  1.1. Proof outline

The proof of Theorem 2 is in Section 2. Here we give a high-level summary. The
proof is by induction with the induction step split up into $12$ claims. As
the cases $1\leq n\leq 4$ of Theorem 2 are easily checked, we assume that
$n>4$ and that the theorem holds for all smaller values of $n$, but not for
$n$, and aim for a contradiction.

Starting off, we show that the graph has minimum degree $3$ (Claim 1) and is
$2$-connected (Claim 2). We then apply the Euler formula and count incident
edge-face pairs to give an upper bound for the length of the boundary of $G$
in terms of $n$ and a certain weighted count $F$ of the number of non-
triangular inner faces (Claim 3), as well as a lower bound for the number of
triangles (Claim 4). If this weighted count $F$ equals $0$ or $1$, then either
all inner faces are triangles, a case where Theorem 1 applies, or there is a
quadrilateral as well, a case that can be easily dealt with by splitting up
the graph at the quadrilateral and applying induction. Thus we can assume that
$F\geq 2$ (Claim 5).

We apply the isoperimetric inequality (Lemma 1) to our upper bound of the
boundary length of $G$ and the lower bound on its area derived from the lower
bound on the number of triangles. This gives an upper bound for $F$ of the
form $c\sqrt{12n-3}$ (we use $c=1/11$, but $c$ can be made as small as $1/20$)
as well as showing that we may assume that $n\geq 147$ otherwise $F<2$ (Claim
6).

We next consider the so-called lattice components of the graph, which we
define to be maximal $2$-connected subgraphs that each lie on some triangular
lattice. We find lower bounds for their boundary lengths (Claim 7) and show
that they cover almost all of $G$ without too much overlap (Claim 8). This
enables us to show that the largest lattice component, $G_{1}$, has to be
quite large (we show that $n(G_{1})>3n/4$ in Claim 9, but it is possible to go
up to $0.97n$ if $n$ is sufficiently large).

We split $G$ up into $G_{1}$ and a slight enlargement of $G-G_{1}$, and apply
induction to obtain a lower bound for $F$ in terms of $n$ and $n_{1}$ (Claim
10) that will be crucial for the final part of the proof. We also bound the
number of edges on the boundary of $G$ that are not on the boundary of $G_{1}$
(Claim 11). Thus, except for a bounded quantity, the boundary edges of $G$ all
lie on the same triangular lattice. Our new isoperimetric inequality (Lemma 2)
then gives an improved upper bound on the area of $G$, which can be bounded
from below using the bound on the number of triangles from Claim 4. The upshot
of this is that we find a very good upper bound on $F$ (Claim 12), which,
together with the lower bound from Claim 10 gives us our final contradiction.

###  1.2. Definitions

We define a _triangular lattice_ to be any subset of the plane isometric to
$\\{m(1,0)+n(1/2,\sqrt{3}/2):m,n\in\mathbb{Z}\\}$, and we say that a finite
set of points _lies on a triangular lattice_ if it is a subset of some
triangular lattice. We will use the following simple observation.

######  Lemma 3.

If $a$ and $b$ are distinct points on a triangular lattice and $c$ is a point
at distance $1$ to both $a$ and $b$, then $c$ lies on the same triangular
lattice.

We use standard graph theory terminology as can be found in [5]*Sections
1.1–1.4, 4.1, 4.2. We call the cycle bounding the outer face of a plane graph
$G$ the _boundary_ of $G$, its length the _boundary length_ of $G$, and its
edges the _boundary edges_ of $G$.

We will occasionally use the function $\phi(x)=\sqrt{12x-3}-3$ which is non-
negative for all $x\geq 1$. Since $\phi$ is strictly concave,
$\phi(x+a)-\phi(x)$ is strictly decreasing in $x$ for all fixed $a>0$. This
implies the following inequality that we will use repeatedly.

######  Lemma 4.

$\phi(a)+\phi(b)<\phi(a-c)+\phi(b+c)$ whenever $a>b+c$, $b\geq 1$ and $c>0$.

##  2\. Proof

###  2.1. Setting up the induction

Let $G$ be a matchstick graph on $n=n(G)$ vertices in the plane. Denote the
number of edges by $e=e(G)$. We prove Theorem 2 by induction. The cases $1\leq
n\leq 3$ are trivial. The case $n=4$ follows since the complete graph on $4$
vertices is not a matchstick graph. So we fix $n>4$ and assume the theorem is
true for all matchstick graphs of less than $n$ vertices. Among all matchstick
graphs on $n$ vertices, fix one $G$ with the maximum number $e$ of edges. We
assume that

$e>3n-\sqrt{12n-3},$ (1)

and will aim for a contradiction. Claims 1–12 below will all have as unstated
assumptions the induction hypothesis, $n>4$, the inequality (1), and that $G$
has the maximum number of edges among all matchstick graphs with $n$ vertices.

###  2.2. Basic properties

######  Claim 1.

Each vertex of $G$ has at least $3$ neighbours.

###### Proof.

Suppose that there is a vertex $v$ with at most $2$ neighbours, and let
$G^{\prime}=G-v$. Then by induction and Lemma 4,

$\displaystyle e$ $\displaystyle\leq e(G^{\prime})+2\leq
3(n-1)-\sqrt{12(n-1)-3}+2$ $\displaystyle=3n-\phi(n-1)-4$ $\displaystyle\leq
3n-\phi(n)+\phi(5)-\phi(4)-4$
$\displaystyle=3n-\sqrt{12n-3}+\phi(5)-\phi(4)-1<3n-\sqrt{12n-3},$

which contradicts (1). ∎

######  Claim 2.

$G$ is 2-connected.

###### Proof.

$G$ has to be connected, otherwise we can move a connected component until one
of its vertices has distance $1$ to some other vertex, contradicting
maximality.

If $G$ is not $2$-connected, then $G$ has a cut vertex. Thus there exist two
subgraphs $G_{1}$ and $G_{2}$ that cover $G$ and have only a single vertex in
common. Then with $n_{1}=n(G_{1}),n_{2}=n(G_{2})\geq 2$, $e_{1}=e(G_{1})$, and
$e_{2}=e(G_{2})$, we have $n=n_{1}+n_{2}-1$, and

$\displaystyle e$ $\displaystyle=e_{1}+e_{2}$ $\displaystyle\leq
3n_{1}-\sqrt{12n_{1}-3}+3n_{2}-\sqrt{12n_{2}-3}$
$\displaystyle=3n-\phi(n_{1})-\phi(n_{2})-3$
$\displaystyle<3n-\phi(n_{1}+n_{2}-1)-\phi(1)-3=3n-\sqrt{12n-3}$

by induction and Lemma 4, which contradicts (1). ∎

###  2.3. The Euler formula and double counting.

Since $G$ is 2-connected by Claim 2, all of its faces are polygons. Let $b$
denote the length of the outer face, and for each $i\geq 3$, let $f_{i}$
denote the number of inner faces bounded by a cycle of length $i$. Since $G$
is connected, Euler’s formula gives

$n-e+\sum_{i\geq 3}f_{i}=1,$ (2)

and since $G$ is $2$-connected, by counting incident edge-face pairs in two
ways, we obtain

$2e=b+\sum_{i\geq 3}if_{i}.$ (3)

Let $F=\sum_{i\geq 4}(i-3)f_{i}$. Then (2) and (3) imply

$e=3n-3-b-F.$ (4)

From (1) we then obtain

######  Claim 3.

$b<\sqrt{12n-3}-3-F=\phi(n)-F$.

###  2.4. Using the isoperimetric inequality

We need the following lower bound on the number of triangular faces, so that
we can estimate the area of the region bounded by $G$, then use the
isoperimetric inequality to find a lower bound for $b$ and from that our first
upper bound on $F$. This upper bound will be needed later in our proof of an
improved upper bound for $F$ (Claim 12).

######  Claim 4.

$f_{3}>2n+1-\sqrt{12n-3}-F=\phi(n)^{2}/6-F$.

###### Proof.

Using the Euler formula (2) and our assumption (1), we obtain

$f_{3}=e-n+1-\sum_{i\geq 4}f_{i}>2n-\sqrt{12n-3}+1-F.\qed$

######  Claim 5.

$F\geq 2$.

###### Proof.

If $F=0$, then all inner faces are triangular, and since $G$ is $2$-connected,
it lies on a single triangular lattice. Then $G$ is a penny graph, and
Harborth’s Theorem 1 gives $e\leq 3n-\sqrt{12n-3}$, a contradiction.

If $F=1$, then there is a single quadrilateral inner face with all other inner
faces triangular. Each vertex $v$ of this quadrilateral must lie on the
boundary of $G$, otherwise, all other faces incident with $v$ would be
equilateral triangles, implying that the angle of the quadrilateral at $v$ is
a multiple of $60^{\circ}$. Then the quadrilateral would have angles
$60^{\circ}$ and $120^{\circ}$, and we could add an edge between the two
opposite vertices at the $120^{\circ}$ angles, violating the maximality of
$G$.

We next decompose $G$. Since $n>5$, at least one of the edges of the
quadrilateral is not a boundary edge of $G$. Let $p$ and $q$ be the endpoints
of such an edge. Then $G-\\{p,q\\}$ is not connected and has exactly two
connected components $C_{1}$ and $C_{2}$. Let $G_{i}$ be the subgraph of $G$
induced by the vertices of $C_{i}$ and $p$ and $q$ for $i=1,2$. Then $G_{1}$
and $G_{2}$ have only an edge of the quadrilateral in common, and cover $G$.
Denoting $n_{i}=n(G_{i})$ and $e_{i}=e(G_{i})$, $i=1,2$, we have
$n_{1}+n_{2}=n+2$ and $e_{1}+e_{2}=e+1$. Since $pq$ is not on the boundary of
$G$, it follows that $n_{i}\geq 3$ ($i=1,2$), and the length $b$ of the
boundary of $G$ is at least $5$. Then Claim 3 implies that $n>7$, and

$\displaystyle e$ $\displaystyle=e_{1}+e_{2}-1$ $\displaystyle\leq
3n-\phi(n_{1})-\phi(n_{2})-1\quad\text{by induction}$ $\displaystyle\leq
3n-\phi(n_{1}+n_{2}-3)-\phi(3)-1\quad\text{by Lemma~{}\ref{concave}}$
$\displaystyle<3n-\phi(n)+\phi(7)-\phi(6)-\phi(3)-1\quad\text{again by
Lemma~{}\ref{concave}}$ $\displaystyle<3n-\sqrt{12n-3},$

contradicting assumption 1.

$q$$p$$G_{1}$$G_{2}$ Figure 1. Subgraphs $G_{1}$ and $G_{2}$ covering $G$ and
sharing edge $pq$ of a quadrilateral

∎

######  Claim 6.

$n\geq 147$ and $F<\frac{1}{11}\sqrt{12n-3}-1$.

###### Proof.

Denote the area of the boundary polygon of $G$ by $A$. The area of an
equilateral triangle of side length $1$ is $\sqrt{3}/4$, hence
$A>\frac{\sqrt{3}}{4}f_{3}$. By Claim 4, $f_{3}>\phi(n)^{2}/6-F$, and by the
isoperimetric inequality (Lemma 1) and Claim 3, $4\pi
A<b^{2}<(\phi(n)-F)^{2}$. In the remainder of this proof we write
$\phi=\phi(n)$. We thus obtain the inequality
$\frac{\pi\sqrt{3}}{6}(\phi^{2}-6F)<(\phi-F)^{2}$, or when expanded,

$F^{2}-(2\phi-\pi\sqrt{3})F+(1-\pi\sqrt{3}/6)\phi^{2}>0.$ (5)

By Claim 3 and $b\geq 3$, we obtain $F<\phi-\pi\sqrt{3}/2$, so the left-hand
side of (5) is decreasing in $F$. Thus we can substitute $F=2$ into (5) to
obtain

$4-2(2\phi-\pi\sqrt{3})+(1-\pi\sqrt{3}/6)\phi^{2}>0,$

hence $\phi<4.114\dots$ or $\phi>38.849\dots$, or in terms of $n$,
$n<4.468\dots$ or $n>146.199\dots$. Since $n\geq 5$ by assumption, we conclude
that $n\geq 147$, as required. For the second part of the claim, we solve for
$F$ in (5) to obtain

$F<\phi-\pi\sqrt{3}/2-\frac{1}{2}\sqrt{\frac{2\pi}{\sqrt{3}}\phi^{2}-4\pi\sqrt{3}\phi+3\pi^{2}}.$

In order to show that $F<(\phi-8)/11$, it is sufficient to show that

$\phi-\pi\sqrt{3}/2-\frac{1}{2}\sqrt{\frac{2\pi}{\sqrt{3}}\phi^{2}-4\pi\sqrt{3}\phi+3\pi^{2}}\leq\frac{\phi-8}{11}.$

This inequality is equivalent to $\phi\leq 2.084\dots$ or $\phi\geq
20.506\dots$. However, we have already shown that $\phi>38.849\dots$. Thus we
conclude that $F<(\phi-8)/11$, which proves the second part of the claim. ∎

###  2.5. Lattice components

We define a _lattice component_ of $G$ to be any maximal $2$-connected
subgraph (on at least $3$ vertices) that lies on some triangular lattice.
Denote the lattice components of $G$ by $G_{1},\dots,G_{k}$. Denote the number
of vertices by $n_{i}=n(G_{i})$, the number of edges by $e_{i}=e(G_{i})$, and
the boundary length of $G_{i}$ by $b_{i}$. Assume that $n_{1}\geq
n_{2}\geq\dots\geq n_{k}$. Note that no two lattice components have an edge in
common, otherwise their union would be a larger $2$-connected graph on the
same lattice.

######  Claim 7.

For each $i=1,\dots,k$, $b_{i}\geq\sqrt{12n_{i}-3}-3$.

###### Proof.

$G_{i}$ is on a triangular lattice and is $2$-connected, so its boundary is a
cycle. Construct a new graph $G^{\prime}$ from $G_{i}$, by filling up all
missing lattice vertices and edges inside the boundary of $G_{i}$. By Theorem
1, $e(G^{\prime})\leq 3n(G^{\prime})-\sqrt{12n(G^{\prime})-3}$, since
$G^{\prime}$ is also on the triangular lattice. (We cannot use induction here,
because $G^{\prime}$ might have more than $n$ vertices.) By (4) applied to
$G^{\prime}$ (which is still $2$-connected and with $F=0$), we obtain
$b_{i}\geq\sqrt{12n(G^{\prime})-3}-3\geq\sqrt{12n_{i}-3}-3$, since
$G^{\prime}$ has the same outer boundary as $G_{i}$. ∎

We will later need that the largest lattice component is not too small. We
first show that the lattice components cover almost all of $G$ and do not
overlap too much.

######  Claim 8.

$n-2F\leq\sum_{i=1}^{k}n_{i}\leq n+4F$.

###### Proof.

For the lower bound, consider a vertex $v$ of $G$ that does not belong to any
lattice component. Let $s$ be the number of inner faces of $G$ incident to
$v$. Since $v$ has at least $3$ neighbours (Claim 1), $s\geq 2$. Assign a
charge of $1/s$ to each inner face incident to $v$. Since these faces are all
non-triangular, the total charge is $\leq\frac{1}{2}\sum_{i\geq 4}if_{i}\leq
2F$. The total charge on all such vertices counts the number of vertices not
covered by any lattice component. Thus, at least $n-2F$ vertices of $G$ are
covered by the lattice components, which gives $\sum_{i=1}^{k}n_{i}\geq n-2F$.

For the upper bound, consider a vertex $v$ that belongs to $t\geq 2$ of the
$G_{i}$. Now let $s$ be the number of non-triangular inner faces of $G$
incident to $v$. Since two adjacent faces incident to $v$ cannot belong to
distinct $G_{i}$, there is at least one non-triangular face between any two
faces at $v$ belonging to distinct $G_{i}$, so $v$ is incident to at least $t$
non-triangular faces, of which one could be the outer face. Hence $s\geq t-1$.
Assign a charge of $(t-1)/s$ to each non-triangular inner face incident to
$v$. This gives a total charge of $t-1$ for each $v$, which is exactly its
contribution to $\sum_{i}n_{i}-n$. Since $(t-1)/s\leq 1$, we obtain that the
total charge is at most $\sum_{i\geq 4}if_{i}\leq 4F$. Thus,
$\sum_{i}n_{i}\leq n+4F$. ∎

From now on we concentrate on the largest lattice component $G_{1}$. We first
show that it covers a considerable proportion of $G$.

######  Claim 9.

$n_{1}>3n/4$.

###### Proof.

Suppose that all $n_{i}\leq 3n/4$. We will find a contradiction by bounding
$\sum_{i=1}^{k}b_{i}$ from above and below. Since no two $G_{i}$ have a common
boundary edge, this sum counts the number of edges on the boundaries of all
lattice components.

For the upper bound, note that if an edge is on the boundary of some lattice
component then it borders a non-triangular face on the outside of the lattice
component. This gives

$\sum_{i=1}^{k}b_{i}\leq b+\sum_{i\geq
4}if_{i}<\sqrt{12n-3}-3-F+4F<\frac{14}{11}\sqrt{12n-3}-6$ (6)

from Claims 3 and 6. For the lower bound we just use Claim 7:

$\sum_{i=1}^{k}b_{i}\geq\sum_{i=1}^{k}(\sqrt{12n_{i}-3}-3)=\sum_{i=1}^{k}\phi(n_{i}).$
(7)

We lower bound the right-hand side by relaxing it to a continuous optimisation
problem. We have $k\leq N/3$, where $N=\sum_{i=1}^{k}n_{i}$. For later
reference, note that $3n/4+3<N<6n/4-3$ since $n\geq 13$, by Claims 8 and 6. In
particular, $k\geq 2$. For each $\ell=2,\dots,\lfloor N/3\rfloor$, define
$\Phi_{\ell}(x_{1},\dots,x_{\ell})=\sum_{i=1}^{\ell}\phi(x_{i})$ on the domain

$D_{\ell}=\left\\{(x_{1},\dots,x_{\ell})\in\mathbb{R}^{\ell}:\tfrac{3}{4}n\geq
x_{1}\geq\dots\geq x_{\ell}\geq 3,\sum_{i=1}^{\ell}x_{i}=N\right\\}.$

For each $\ell$, the function $\Phi_{\ell}$ has a minimum value $y_{\ell}$ on
$D_{\ell}$. Among all of these $\ell$, fix one, say $m$, that minimises
$y_{\ell}$. Fix $(x_{1},\dots,x_{m})\in D_{m}$ such that
$\Phi_{m}(x_{1},\dots,x_{m})=y_{m}$. By strict concavity of $\phi$ (Lemma 4)
we cannot have two $x_{i}$ in the open interval $(3,\frac{3}{4}n)$. If $m\geq
3$, we cannot have some $x_{i}=3$ and another $x_{j}\leq 3n/4-3$, since we can
then replace both by a single variable equal to $x_{j}+3$, thereby finding

$\displaystyle y_{m-1}$ $\displaystyle\leq
y_{m}+\phi(3+x_{j})-\phi(x_{j})-\phi(3)$ $\displaystyle\leq
y_{m}+\phi(6)-\phi(3)-\phi(3)\quad\text{by Lemma~{}\ref{concave}}$
$\displaystyle<y_{m}.$

It follows that we cannot have any $x_{i}=3$, since this would imply that all
other $x_{j}\in(3n/4-3,3n/4]$, but $3+3n/4<N$ and $3+2(3n/4-3)>N$ as noted
before. We cannot have two $x_{i}$ equal to $\frac{3}{4}n$, since $6n/4>N$.
Thus necessarily $m=2,x_{1}=\frac{3}{4}n,x_{2}=N-\frac{3}{4}n$. It follows
that

$\displaystyle\sum_{i=1}^{k}\phi(n_{i})$
$\displaystyle=\Phi_{k}(n_{1},\dots,n_{k})\geq\Phi_{2}(x_{1},x_{2})$
$\displaystyle\geq\Phi_{2}(x_{1}+1/16,x_{2}-1/16)\quad\text{by
Lemma~{}\ref{concave}}$
$\displaystyle=\sqrt{(3/4)(12n-3)}-3+\sqrt{12(N-3n/4)-15/4}-3$
$\displaystyle\geq\frac{\sqrt{3}}{2}\sqrt{12n-3}+\sqrt{12(n/4-2F)-15/4}-6\quad\text{by
Claim~{}\ref{lattice-components}.}$ (8)

Putting (6), (7) and (8) together, we obtain

$\frac{1}{6}(12n-3)>\Bigl{(}\frac{14}{11}-\frac{\sqrt{3}}{2}\Bigr{)}^{2}(12n-3)>12(n/4-2F)-15/4=\frac{1}{4}(12n-3)-3-24F.$

Again using Claim 6 it follows that

$\frac{1}{12}(12n-3)-3<24F<\frac{24}{11}\sqrt{12n-3}-24,$

which has no solutions in $n$, a contradiction. ∎

The next inequality comes from applying the induction hypothesis to $G_{1}$
and a slight enlargement of the remainder $G-G_{1}$.

######  Claim 10.

$\sqrt{12(n-n_{1})}<6F+\sqrt{12n-3}-\sqrt{12n_{1}-3}$.

###### Proof.

Let $K$ be the set of vertices of $G_{1}$ that are joined to some vertex in
$G-G_{1}$, and let $G^{\prime}$ be the subgraph of $G$ induced by
$V(G-G_{1})\cup K$. Since $G_{1}$ is on the lattice, we already know by
Harborth’s Theorem 1 that $e_{1}\leq 3n_{1}-\sqrt{12n_{1}-3}$. If
$K=\emptyset$, then $G_{1}=G$ since $G$ and $G_{1}$ are connected, and then
the assumption (1) is contradicted. Thus $K\neq\emptyset$. Let
$n^{\prime}=n(G^{\prime})=n-n_{1}+|K|$ and $e^{\prime}=e(G^{\prime})$. Then
$G^{\prime}$ and $G_{1}$ cover all the edges of $G$, hence $e\leq
e_{1}+e^{\prime}$. To bound $e^{\prime}$ from above, we will apply induction,
but then we need to ensure that $K\neq V(G_{1})$. We do this by bounding $|K|$
from above.

$G_{1}$$G^{\prime}$$K$ Figure 2. Decomposition of $G$ into $G_{1}$ and
$G^{\prime}$ with common vertex set $K$

Each vertex $v$ in $K$ belongs to some inner face of $G$ not lying on the
lattice of $G_{1}$, otherwise all inner faces around $v$ lie on the same
lattice, so must be part of $G_{1}$ by maximality. Consider any inner face
$\Gamma$ not lying on the lattice of $G_{1}$, so with at least one vertex not
in $K$. Denote the length of the cycle bounding $\Gamma$ by $i$. Suppose that
all but one of the vertices on this cycle lie in $K$ and consider the
remaining vertex $v$ with neighbours $u$ and $w$ on $\Gamma$. Since $u$ and
$w$ are on the lattice of $G_{1}$, $v$ also lies on the same lattice by Lemma
3, but then $\Gamma$ lies on the lattice of $G_{1}$, a contradiction. Hence at
most $i-2$ vertices of $K$ belong to $\Gamma$. Since $\Gamma$ is a non-
triangular face of $G$, we find the upper bound

$|K|\leq\sum_{i\geq 4}(i-2)f_{i}\leq 2F.$

By Claims 6 and 9 it follows that $2F<n_{1}$, hence $K$ cannot be all of
$G_{1}$ so $G^{\prime}$ is a proper subset of $G$, and we can apply induction
to $G^{\prime}$ to obtain

$e\leq e_{1}+e^{\prime}\leq
3n_{1}-\sqrt{12n_{1}-3}+3n^{\prime}-\sqrt{12n^{\prime}-3}.$

Using assumption (1) and $n_{1}+n^{\prime}=n+|K|$, we obtain

$\sqrt{12(n-n_{1}+|K|)-3}<3|K|+\sqrt{12n-3}-\sqrt{12n_{1}-3}.$ (9)

The claim now follows from the bounds $1\leq|K|\leq 2F$. ∎

Let $b_{*}$ be the number of boundary edges of $G$ not on the boundary of
$G_{1}$.

######  Claim 11.

$b_{*}<\sqrt{12n-3}-\sqrt{12n_{1}-3}$.

###### Proof.

Each edge on the boundary of $G_{1}$ borders either the outer face of $G$ or
an inner non-triangular face $\Gamma$ of $G$. Let $i$ denote the length of the
cycle bounding $\Gamma$. Not all the edges of $\Gamma$ are on the boundary of
$G_{1}$. Thus $\Gamma$ contributes at most $i-1$ edges to the boundary of
$G_{1}$. If $\Gamma$ has $i-1$ or $i-2$ of its edges on the boundary of
$G_{1}$, then by Lemma 3, $\Gamma$ has to be a lattice polygon, so has to be
part of $G_{1}$ by maximality. Thus $\Gamma$ has at most $i-3$ of its edges on
the boundary of $G_{1}$. Therefore,

$b_{1}\leq b-b_{*}+\sum_{i\geq 4}(i-3)f_{i}=b-b_{*}+F.$

The claim now follows from the inequalities in Claims 3 and 7. ∎

###  2.6. An improved isoperimetric inequality

Our next aim is to find a better upper bound for $F$ in a form similar to the
upper bound of $b_{*}$ in Claim 11. This bound (Claim 12) will then be
combined with Claim 10 to obtain a contradiction. Claim 12 will follow from
our isoperimetric inequality in Lemma 2, which we now restate and prove.

######  Lemma 2.

Let $P$ be a simple polygon with perimeter $b$, area $A$, and with the total
length of the sides not parallel to any side of some fixed regular hexagon at
most $b_{*}$. Then

$8\sqrt{3}A\leq\bigl{(}b+\bigl{(}\tfrac{2}{\sqrt{3}}-1\bigr{)}b_{*}\bigr{)}^{2}.$

###### Proof.

Let $h$ be a fixed regular hexagon. For any simple polygonal path (open or
closed) $Q$, we denote its length by $b(Q)$ and the total length of its sides
not parallel to any side of $h$ by $b_{*}(Q)$. If $Q$ is closed (a polygon),
we denote its area by $A(Q)$.

We first modify $P$ into a convex polygon $P^{\prime}$ with
$b(P)=b(P^{\prime})$, $b_{*}(P)=b_{*}(P^{\prime})$, and $A(P)\leq
A(P^{\prime})$. We say that a simple polygon $Q$ is a _rearrangement_ of $P$
if there is a bijection between the edge set of $Q$ and the edge set of $P$
such that corresponding edges are parallel and have the same length. Note that
for any rearrangement $Q$ of $P$ we have $b(P)=b(Q)$ and $b_{*}(P)=b_{*}(Q)$.
Among all rearrangements of $P$ fix one, $P^{\prime}$, of maximum area. We
claim that $P^{\prime}$ is convex. If $P^{\prime}$ is not convex, then it has
two vertices $p$ and $q$ such that the boundary of $P^{\prime}$ between $p$
and $q$ lies in the interior of the convex hull of $P^{\prime}$. If we replace
this part of the boundary by its rotation by $180^{\circ}$ around the midpoint
of $p$ and $q$, then we obtain a new simple polygon that is still a
rearrangement of $P$, but with larger area.

$H$$r_{1}$$r_{2}$$r_{3}$$r_{4}$$r_{5}$$r_{6}$$p_{6}$$p_{2}$$q_{3}$$p_{4}$$q_{4}$$p_{5}$$q_{1}$$q_{6}$$p_{7}=p_{1}$$P^{\prime}$$q_{2}$$p_{3}$$q_{5}$$Q_{4}$$Q_{6}$$Q_{1}$$Q_{2}$$Q_{3}$$Q_{5}$
Figure 3. The polygon $P^{\prime}$ and its circumscribed hexagon $H$

Let $H$ denote the hexagon with sides parallel to the sides of $h$
circumscribed around $P^{\prime}$. Number the sides of $H$ in order from $1$
to $6$. For each $i=1,\dots,6$, let $p_{i}q_{i}$ be the segment of
$P^{\prime}$ on side $i$ of $H$, such that the points lie in the order
$p_{1},q_{1},p_{2},q_{2},\dots,p_{6},q_{6}$ around $P^{\prime}$. Denote the
path of $P^{\prime}$ between $q_{i}$ and $p_{i+1}$ by $Q_{i}$, $i=1,\dots,6$,
where $p_{7}=p_{1}$.

Note that in a triangle $pqr$ with $\angle r=120^{\circ}$, the cosine rule
gives

$\displaystyle|pq|^{2}$ $\displaystyle=|pr|^{2}+|qr|^{2}-2|pr|\cdot|qr|\cos
120^{\circ}$ $\displaystyle=|pr|^{2}+|qr|^{2}+|pr|\cdot|qr|$
$\displaystyle=\tfrac{3}{4}(|pr|+|qr|)^{2}+\tfrac{1}{4}(|pr|-|qr|)^{2}$
$\displaystyle\geq\tfrac{3}{4}(|pr|+|qr|)^{2},$

hence $|pr|+|qr|\leq\frac{2}{\sqrt{3}}|pq|$. We now apply this to each
triangle $p_{i+1}q_{i}r_{i}$ to obtain an upper bound on the perimeter of $H$
in terms of $b$ and $b_{*}$:

$\displaystyle b$
$\displaystyle=\sum_{i=1}^{6}|p_{i}q_{i}|+\sum_{i=1}^{6}b(Q_{i})$
$\displaystyle=b(H)-\sum_{i=1}^{6}|q_{i}r_{i}|-\sum_{i=1}^{6}|r_{i}p_{i+1}|+\sum_{i=1}^{6}b(Q_{i})$
$\displaystyle\geq
b(H)-\sum_{i=1}^{6}|q_{i}r_{i}|-\sum_{i=1}^{6}|r_{i}p_{i+1}|+\sum_{i=1}^{6}|q_{i}p_{i+1}|\quad\text{by
the triangle inequality}$ $\displaystyle\geq
b(H)-\tfrac{2}{\sqrt{3}}\sum_{i=1}^{6}|q_{i}p_{i+1}|+\sum_{i=1}^{6}|q_{i}p_{i+1}|\quad\text{since
$\angle r_{i}=120^{\circ}$}$
$\displaystyle=b(H)-(\tfrac{2}{\sqrt{3}}-1)\sum_{i=1}^{6}|q_{i}p_{i+1}|$
$\displaystyle\geq
b(H)-(\tfrac{2}{\sqrt{3}}-1)\sum_{i=1}^{6}b(Q_{i})\quad\text{again by the
triangle inequality}$ $\displaystyle=b(H)-(\tfrac{2}{\sqrt{3}}-1)b_{*}.$

By the isoperimetric inequality for hexagons (or L’Huilier’s inequality for
hexagons with sides parallel to those of a fixed hexagon) the hexagon with a
fixed perimeter maximising the area is regular. It follows that

$\displaystyle A$ $\displaystyle\leq A(P^{\prime})\leq A(H)$
$\displaystyle\leq\tfrac{\sqrt{3}}{24}b(H)^{2}\quad\text{by the isoperimetric
inequality for hexagons}$
$\displaystyle\leq\tfrac{\sqrt{3}}{24}(b+(\tfrac{2}{\sqrt{3}}-1)b_{*})^{2},$

and Lemma 2 follows. ∎

We now obtain an improved upper bound for $F$ from the above isoperimetric
estimate, again bounding the area from below by using the lower bound on
$f_{3}$ from Claim 4.

######  Claim 12.

$F<\frac{1}{6}(\sqrt{12n-3}-\sqrt{12n_{1}-3})+\frac{1}{2}$.

###### Proof.

As before, the area $A$ of the boundary polygon of $G$ is at least
$\frac{\sqrt{3}}{4}f_{3}$. If we substitute this, as well as the upper bounds
for $b$ and $b_{*}$ from Claims 3 and 11, respectively, and the lower bound
for $f_{3}$ from Claim 4, into Lemma 2, we obtain

$12n+6-6\sqrt{12n-3}-6F\leq(b+cD)^{2}<(\sqrt{12n-3}-3+cD-F)^{2},$

where $D=\sqrt{12n-3}-\sqrt{12n_{1}-3}$ and $c=2/\sqrt{3}-1$.

Suppose that $cD-F\leq-1/2$. Then

$12n+6-6\sqrt{12n-3}-6F<(\sqrt{12n-3}-7/2)^{2}.$

Multiplying out and simplifying, we obtain
$F>\frac{1}{6}\sqrt{12n-3}-\frac{13}{24}$, which contradicts the previous
upper bound on $F$ from Claim 6.

Therefore, $cD-F>-1/2$, which gives the claim. ∎

###  2.7. The conclusion

We now combine the new estimate for $F$ from Claim 12 with Claim 10 to obtain
a contradiction. Claim 12 together with $F\geq 2$ (Claim 5) imply that

$D:=\sqrt{12n-3}-\sqrt{12n_{1}-3}>9.$ (10)

Again by Claim 12,

$6F<D+3<D+\frac{1}{3}D=\frac{4}{3}D\quad\text{by \eqref{*}}.$

Then Claim 10 gives

$\sqrt{12(n-n_{1})}<\frac{4}{3}D+D=\frac{7}{3}D=\frac{7}{3}\cdot\frac{12(n-n_{1})}{\sqrt{12n-3}+\sqrt{12n_{1}-3}}.$

It follows that

$\frac{3}{7}(\sqrt{12n-3}+\sqrt{12n_{1}-3})<\sqrt{12(n-n_{1})}.$ (11)

By Claim 9, and using that $n_{1}$ and $n$ are integers, we have
$n_{1}>\frac{3}{4}n+\frac{1}{16}$, which implies
$\sqrt{12n_{1}-3}>\frac{\sqrt{3}}{2}\sqrt{12n-3}$ and
$\sqrt{12(n-n_{1})}<\frac{1}{2}\sqrt{12n-3}$. Together with (11) we obtain the
contradiction $\frac{3}{7}(1+\frac{\sqrt{3}}{2})<\frac{1}{2}$.

This finishes the induction step and thereby the proof of Theorem 2. ∎

## References

  * [1] Abel, Z., Demaine E. D., Demaine M. L., Eisenstat S., Lynch J., Schardl T. B.:  _Who needs crossings? Hardness of plane graph rigidity_.  32nd International Symposium on Computational Geometry, Art. No. 3, 15 pp., LIPIcs. Leibniz Int. Proc. Inform., 51, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern. (2016)
  * [2] Blåsjö, V.:  _The Isoperimetric Problem_.  Amer. Math. Monthly 112, 526–566. (2005)
  * [3] Blokhuis, A.:  _Regular finite planar maps with equal edges_.  arXiv preprint arXiv:1401.1799. (1982)
  * [4] Brass, P., Moser W. O. J., and Pach. J.:  _Research Problems in Discrete Geometry_.  Springer-Verlag, New York. (2005)
  * [5] Diestel, R.:  _Graph theory_. 3rd ed.  Springer, Berlin Heidelberg. (2006)
  * [6] Fejes Tóth, L.:  _Lagerungen in der Ebene auf der Kugel und im Raum_. 2nd ed.  Springer-Verlag, Berlin-New York. (1972)
  * [7] Fejes Tóth, L., Fejes Tóth G, and Kuperberg W.:  _Lagerungen: Arrangements in the Plane, on the Sphere, and in Space_. Springer-Verlag, Cham. (2023) (Translation of [6] with additional material.)
  * [8] Gerbracht, E. H.-A.:  _Minimal polynomials for the coordinates of the Harborth graph_.  arXiv:math/0609360. (2006)
  * [9] Gerbracht, E. H.-A.:  _Symbol-crunching the Harborth graph_.  Adv. in Appl. Math., 47 276–281. (2011)
  * [10] Harborth, H.:  _Solution to Problem 664A_.  Elemente der Mathematik 29, 14–15. (1974)
  * [11] Harborth, H.:  _Point sets with equal numbers of unit-distant neighbors_ (Abstract),  Discrete Geometry, 12–18 July 1981, Oberwolfach,  Tagungsbericht 31/1981, Mathematisches Forschungsinstitut Oberwolfach. pp. 11–12. (1981)
  * [12] Harborth, H.:  _Match sticks in the plane_.  In: The Lighter Side of Mathematics. Proceedings of the Eugène Strens Memorial Conference on Recreational Mathematics and its History held at the University of Calgary, Calgary, Alberta, August 1986. edited by R. K. Guy and R. E. Woodrow, 281–288. Mathematical Association of America, Washington, D.C. (1994)
  * [13] Kurz, S.:  _Fast recognition of planar non unit distance graphs_. Geombinatorics, 21, 25–33. (2011)
  * [14] Kurz, S.:  _A lower bound for $4$-regular planar unit distance graphs_.  Geombinatorics, 21, 63–72. (2011)
  * [15] Kurz, S. and Mazzuoccolo G.:  _$3$ -regular matchstick graphs with given girth_, Geombinatorics, 19, 156–173. (2010)
  * [16] Kurz, S. and Pinchasi R.:  _Regular matchstick graphs_.  Amer. Math. Monthly 118, 264–267. (2011)
  * [17] Lavollée, J. and Swanepoel K. J.:  _Bounding the Number of Edges of Matchstick Graphs_.  SIAM Journal on Discrete Mathematics, 36, 777–785. (2022)
  * [18] Lavollée, J. and Swanepoel K. J.:  _The number of small-degree vertices in matchstick graphs_.  Australas. J. Combin. 85, 92–99. (2023)
  * [19] Pach, J. and Agarwal P. J.:  _Combinatorial Geometry_.  Wiley, New York. (1995)
  * [20] Salvia, R.:  _A catalog of matchstick graphs_.  arXiv:1303.5965. (2013)
  * [21] Winkler M.:  _Ein neuer $4$-regulärer Streichholzgraph_.  Mitteilungen der Deutschen Mathematiker-Vereinigung, 24, 74–75. (2016)
  * [22] Winkler M.:  _A catalogue of $4$-regular matchstick graphs with $63$–$70$ vertices and $(2,4)$-regular matchstick graphs with less than $42$ vertices which contain only two vertices of degree $2$_.  arXiv preprint arXiv:1705.04715. (2017)
  * [23] Winkler, M., Dinkelacker P., and Vogel. S.:  _Minimal completely asymmetric $(4;n)$-regular matchstick graphs_.  arXiv preprint arXiv:1609.06972. (2016)
  * [24] Winkler, M., Dinkelacker P., and Vogel. S.:  _New minimal $(4,n)$-regular matchstick graphs_.  Geombinatorics, 27, 26–44. (2017)
  * [25] Winkler, M., P. Dinkelacker, and S. Vogel:  _On the existence of $4$-regular matchstick graphs_.  arXiv preprint arXiv:1705.00293. (2017)
  * [26] Winkler, M., P. Dinkelacker, and S. Vogel:  _A $3$-regular matchstick graph of girth $5$ consisting of $54$ vertices_.  Geombinatorics, 29, 116–121. (2020)


# Learning Action-Effect Dynamics for
Hypothetical Vision-Language Reasoning Task

Shailaja Keyur Sampat, Pratyay Banerjee, Yezhou Yang  Chitta Baral
Arizona State University, USA
<EMAIL_ADDRESS>
###### Abstract

‘Actions’ play a vital role in how humans interact with the world. Thus,
autonomous agents that would assist us in everyday tasks also require the
capability to perform ‘Reasoning about Actions & Change’ (RAC). This has been
an important research direction in Artificial Intelligence (AI) in general,
but the study of RAC with visual and linguistic inputs is relatively recent.
The CLEVR_HYP Sampat et al. (2021) is one such testbed for hypothetical
vision-language reasoning with actions as the key focus. In this work, we
propose a novel learning strategy that can improve reasoning about the effects
of actions. We implement an encoder-decoder architecture to learn the
representation of actions as vectors. We combine the aforementioned encoder-
decoder architecture with existing modality parsers and a scene graph question
answering model to evaluate our proposed system on the CLEVR_HYP dataset. We
conduct thorough experiments to demonstrate the effectiveness of our proposed
approach and discuss its advantages over previous baselines in terms of
performance, data efficiency, and generalization capability111Dataset setup
scripts and code for baselines are available at
https://github.com/shailaja183/ARL.

##  1 Introduction

Humans interact with their environment to accomplish desired goals. Object
manipulation (i.e., performing “actions” over the objects) is a fundamental
concept that makes this interaction possible. In other words, actions in their
simplest form have the power to change the state of a world and hence play a
vital role in enabling humans to perform day-to-day tasks. As we are
developing autonomous agents that can assist us in everyday tasks, they would
also require to interact with complex environments. Hence, the development of
autonomous agents that can perform actions to effectively manipulate objects
and understand corresponding effects is of great importance. As a result,
Reasoning about Action and Change (RAC) has been a long-standing research
problem, since the rise of AI.

Figure 1: Revisiting CLEVR_HYP task Sampat et al. (2021): Answer a reasoning
question (QH) about changes caused over the given image (I) by performing a
hypothetical action (TA).
Figure 2: Two possible ways (LS1 and LS2) to learn action-effect dynamics in a
supervised learning setting. In this paper, we implement LS2 which
demonstrates improvements over LS1. Blue box denotes vector representation.

The work of McCarthy et al. (1960) was the earliest to emphasize the
importance of reasoning about actions. They developed an advice taker system
that can do deductive reasoning about scenarios such as “going to the airport
from home” requires “walking to the car” and “driving the car to airport”.
Since then, many real-life use cases have been identified which require AI
models to understand interactions among the current states of the world,
actions being performed over various objects, and most likely following states
Banerjee et al. (2020). While RAC has been more popular among knowledge
representation and logic communities, it has recently piqued the interest of
researchers in NLP and vision domains. A recent survey by Sampat et al. (2022)
compiled a comprehensive list of works that explore neural network’s ability
to reason about actions and changes, provided a dataset of linguistic and/or
visual inputs.

In a recent tweet, Prof. Yann LeCunn also emphasized the importance of this
research direction. He mentions that “while we progress towards human-level
AI, I believe we need to find new concepts that would (i) allow machines to
learn to predict how one can influence the world through taking actions, (ii)
learn hierarchical representations that allow long-term predictions in
abstract spaces, (iii) enable agents to predict the effects of sequences of
actions so as to be able to reason & plan - all of this in ways that are
compatible with gradient-based learning” LeCun (2022).

In this work, we aim to better tackle the hypothetical action reasoning task
of CLEVR_HYP dataset Sampat et al. (2021). An example from this dataset is
shown in Figure 1). The key objective is to understand changes caused over a
visual scene by an action described in the natural language and answer a
reasoning question. In Figure 2, we describe two possible action-effect
learning strategies (LS1 and LS2) through a toy example to convey our
intuition behind this work. LS1 uses visual features (i.e. features from the
image of an apple) and a representation of actions (i.e. text “rotten”)
through sentence embeddings to imagine the effects (i.e. how a rotten apple
would look like). This can be an intuitive choice to model the CLEVR_HYP task
using pre-trained vision-language models.

In our hypothesis, LS1 does not improve the model’s understanding of what
effects the actions will produce. Thus, we propose an alternative strategy,
LS2222Figure 2 is meant to convey our intuition behind the proposed model in
this work at a very high level. Figure 5 is more complex in comparison and
accurately describes the working of our model, considering the format of
CLEVR_HYP dataset, decomposing the task into various neural components, and
measuring them using appropriate loss functions.. Specifically, we let the
model observe the difference between pairs of states before and after the
action is performed (i.e. decayed portion of the apple that distinguishes a
good apple from the rotten one), then associate those visual differences with
the corresponding linguistic action descriptions (i.e. text “rotten”). LS2 is
likely to better capture action-effect dynamics, as action representations are
learned explicitly.

To empirically test the above hypothesis, we develop a model (which is
described in Section 3) and evaluate it on the CLEVR_HYP dataset. We hope that
our exciting results would enable the development of AI agents that can better
collaborate with humans in the physical world and encourage further
investigations in this research area. In summary, our key contributions are as
follows;

  * •

We propose a novel learning strategy for predicting the “effects of actions”
in the vision-language domain (shown in Figure 2).

  * •

We develop a 3-stage model to implement the proposed learning strategy and
evaluate on the existing CLEVR_HYP Sampat et al. (2021) dataset.

  * •

Through ablations and analysis, we demonstrate the effectiveness of our model
in terms of performance (5.9% accuracy improvements), data efficiency (one-
third of training data required), and better generalization capability in
comparison with the best existing baselines.

Object Attributes in Visual Scenes | Action Text Types | Question Reasoning Types
---|---|---
1\. Shape: cylinder, sphere or cube | 1\. Add new objects to the scene | 1\. Counting objects fulfilling the condition
2\. Size: small or big | 2\. Remove objects from the scene | 2\. Verify existence of certain objects
3\. Material: metal or rubber | 3\. Change attribute of the objects | 3\. Query attribute of a particular object
4\. Spatial: left, right, front, behind or on | 4\. Move objects in or out of plane | 4\. Compare attributes of two objects
| 5\. Color: red, green, gray, blue,
---
$\frac{}{}\frac{}{}\frac{}{}$ brown, yellow, purple or cyan
|  | 5\. Integer comparison of two object sets
---
$\frac{}{}\frac{}{}\frac{}{}$ (same, larger or smaller)
Table 1: Summary of object attributes, actions, and reasoning types in
CLEVR_HYP dataset Sampat et al. (2021)

##  2 CLEVR_HYP

In this section, we briefly summarize important aspects of the CLEVR_HYP
dataset Sampat et al. (2021) and related terminologies used in the subsequent
sections.

###  2.1 Problem Formulation

The task aims at understanding changes caused over an image by performing an
action described in natural language and then answering a reasoning question
over the resulting scene. Consult Figure 1 for better understanding of the
following;

  * •

Inputs:

    1. 1.

Image (I)- Visual scene with rendered objects

    2. 2.

Action Text (TA)- Textual modality describing action(s) to be performed over I

    3. 3.

Hypothetical Question (QH)- Textual question that will assess the system’s
capability to understand changes caused by TA on I

  * •

Output: Answer (A) for the given QH

  * •

Answer Vocabulary: [0-9, yes, no, cylinder, sphere, cube, small, big, metal,
rubber, red, green, gray, blue, brown, yellow, purple, cyan]

  * •

Evaluation: 27-class Answer Classification / Accuracy (%)

###  2.2 Dataset Details and Partitions

The CLEVR_HYP dataset assumes to have a closed set of object attributes,
action types, and question reasoning types which are summarized in Table 1.
The dataset is divided into the following partitions;

  * •

Train (67.5k) / Val (13.5k) sets have <I, TA, QH, A> tuples along with the
scene graphs as a visual oracle and functional programs333Originally
introduced in CLEVR Johnson et al. (2017). For example, a question ‘How many
red metal things are there?’ can be represented as a functional program
‘count(filter_color(filter_material(scene(),metal),red))’ as a textual oracle.

  * •

Test sets consist of only <I, TA, QH, A> tuples, and no oracle annotations are
available. There are three different test sets,

    1. 1.

Ordinary test (13.5k) consists of examples with the same difficulty as
train/val

    2. 2.

2HopTA test (1.5k) consists of examples where two actions are performed ex.
‘Move a purple object on a red cube then paint it cyan.’

    3. 3.

2HopQH test (1.5k) consists of examples where two reasoning types are combined
ex. ‘How many objects are either red or cylinder?’

###  2.3 Baseline Models

Following is a brief description of two top-performing baselines reported in
Sampat et al. (2021), to which we will compare the results of our proposed
approach in this paper.

  * •

(TIE) Text-conditioned Image Editing: Text-adaptive encoder-decoder with
residual gating Vo et al. (2019) is used to generate new image conditioned on
the action. Then, new image along with the question is fed into LXMERT Tan and
Bansal (2019) (which is a pre-trained vision-language transformer), to
generate an answer. The model can be visualized in Figure 3.

Figure 3: Architecture of TIE baseline

  * •

(SGU) Scene Graph Update: In this model, understanding changes caused by an
action text is considered as a graph-editing problem. First, an image is
converted into a scene graph and action text is converted into a functional
program (FP). Sampat et al. (2021) developed a module inspired by Chen et al.
(2020) that can generate an updated scene graph based on the original scene
graph and a functional program of an action text. It is followed by a neural-
symbolic VQA model Yi et al. (2018) that can generate an answer to the
question provided the updated scene graph. The model can be visualized in
Figure 4.

Figure 4: Architecture of SGU baseline

Figure 5: Detailed visualization of our proposed 3-stage Action Representation
Learner (ARL) model: (left) training phase (right) testing phase (bottom)
terms and notations used. Best viewed in color.

There are important distinctions between baselines developed by Sampat et al.
(2021) and our proposed method. Both the above baselines rely on pre-learned
word representation of actions- either by a word-vector algorithm or a learned
functional program and use that to conditionally update the visual scene (at
pixel level or through graph operations). Thus, TIE and SGU resembles more to
LS1 in Figure 2. Note that in SGU baseline, individual functions (in their
functional program representations) are human authored i.e. what kind of
inputs it accepts and what it will return when executed. For example, ‘remove
$<$attribute$>$’ function will take a set of objects as input and return a
subset of objects which do not have $<$attribute$>$.

In contrast, we learn action representations through two-step process. First,
we learn to predict changes in a pair of scene-graphs (before and after the
action is performed). And second, we minimize the loss between changes in the
scene with the representation of linguistic action descriptions. Thus, our
proposed model resembles more to LS2 in Figure 2. Our method is purely based
on data and does not require any human intervention. Also, note that oracle
scene graphs post-actions are not available at the test-time. By enforcing
two-way representation learning, we are able to predict changes in the scene
graph using and action vector from linguistic action description for a given
test instance.

##  3 Proposed Model: Action Representation Learner (ARL)

In this section, we describe the architecture of our proposed model Action
Representation Learner (ARL).

In our point of view, the most critical component of a model that attempts to
solve CLEVR_HYP is the one where mapping between visual changes and actions
are learned. In Figure 2, we graphically demonstrated our intuition behind how
we can do so. Our hypothesis is that a model can learn better action
representations by observing difference between a pair of states (before and
after the action is performed) and then associate those visual differences
with given linguistic description of actions. In this regard, we attempt to
create a 3-stage model shown in Figure 5, which we believe would better
capture the causal structure of this task. Detailed description of each
individual component is provided below and can be visualized in Figure 6.

###  3.1 Stage-1

Actions have the power to change the state of the world. In other words,
difference between a pair of states can be considered as a function of
performing actions. For example, consider two states ‘green cube’ and ‘red
cube’. The change between above states is ‘green$\rightarrow$red’, which is a
function of action ‘paint’ or ‘change color’. Conversely, if one is provided
with a state ‘green cube’ and knowing that the ‘paint red’ action is
performed, then one can visualize that the next state would be ‘red cube’. We
aim to capture such relationship between state changes and actions in this
stage.

Figure 6: Internal details of the components used in ARL model. Red denotes
entities predicted, Blue denotes entities utilized from the dataset.

Specifically, we setup an encoder-decoder model to achieve this objective.
Since our objective is to learn action and effects, we refer to them as
‘Action Encoder’ and ‘Effect Decoder’. As described in Section 2.2, the
training set of CLEVR_HYP provides oracle annotations for an initial scene
graph S (using which the image is rendered) and a scene graph after executing
the action text S′. We take a random subset of 20k444We experiment with
different data sizes and discuss results in Section 4.3, but obtain the
optimal results for 20k samples when action vector length is 125 scene graph
pairs from CLEVR_HYP training set that are balanced by action types (add,
remove, change, move) to train this encoder-decoder.

We capture the difference between states S and S′ i.e. A${}_{S,S^{\prime}}$
using the encoder. At the test time, we do not have the updated scene graph S′
available. To address this issue, the encoder is followed by a decoder, which
can reconstruct S′ provided S and the learned scene difference
A${}_{S,S^{\prime}}$ in the encoder network. Formally,

${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}A_{S,S^{\prime}}}=ActionEncoder({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}S},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}S^{\prime}})$
(1)

${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}S^{\prime}}=EffectDecoder({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}S},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}A_{S,S^{\prime}}})$
(2)

Where
$({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}S},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}S^{\prime}})\in$
CLEVR_HYP training set, red denotes entities predicted, blue denotes entities
utilized from the dataset. We jointly train action encoder-effect decoder
networks with the following objective;

$argmax_{\Theta_{ActionEncoder}\Theta_{EffectDecoder}}\\\
[logP({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}S^{\prime}}|\frac{}{}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}S},\frac{}{}ActionEncoder({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}S},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}S^{\prime}}))]$
(3)

Note that, in common applications involving encoder-decoder architecture, the
decoder part of the model is removed once the desired performance is achieved
and the encoder is used to encode input sequences to a fixed-length vector at
test-time. Contrary, here we discard the encoder part and keep the decoder
part to obtain updated scene representation from the initial scene and learned
action vector.

###  3.2 Stage-2

As explained in stage-1, we do not have the S′ at the test time and we cannot
compute A${}_{S,S^{\prime}}$. However, provided that changes in the scene are
a function of the action, we can approximate Arep Arep is a vector
representation corresponding to natural language action. A network is trained
which can convert ‘Natural language to Action Representation’ with the help of
encoder-decoder network trained in Stage-1 that maximizes the log probability
that outputs the correct state S′ as below.

$argmax_{\Theta_{NL2ActionRep}}\\\
[logP({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}S^{\prime}}|\frac{}{}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}S},\frac{}{}NL2ActionRep({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}T_{A}}))]$
(4)

At the core, lies LSTM encoder, which precedes by an embedding layer and
followed by dense layers. During model training, in addition to finding the
values for the weights of the LSTM and dense layers, the word embeddings for
each word in the training set are computed. This is achieved using
nn.Embedding(vocabulary_size, embedding_size) layer defined in pytorch. This
way, a fixed length one-hot vector of given length is generated for each word
in the vocabulary depending on the position of the word in context and updated
using back-propagation. Embedding layer is similar to a linear layer, which
returns the index where one is located instead of returning the whole one-hot
vector. It takes an action text TA as a sequence of learned word embeddings,
runs an LSTM over them, then projects from the final cell state to get the
output Arep. The LSTM has a hidden layer of size 200.

###  3.3 Stage-3

For each image, we use Mask R-CNN He et al. (2017) to generate segment
proposals of all objects. Along with the segmentation mask, the network also
classifies the objects based on their visual attributes- color, material,
size, and shape. The threshold for segment proposals is set to 0.9 i.e.
segments with bounding-box score less than 0.9 are dropped. The segment for
each single object, paired with the original image (resized to 224x224) is
sent to ResNet-34 He et al. (2016) to extract 3D coordinates of objects in the
scene. Inclusion of original full image is observed to enhance the performance
by incorporating contextual information. Note that scene-parsing is pre-
trained and not fine-tuned with rest of the network.

##  4 Results and Analysis

In this section, we discuss the performance of our model quantitatively and
qualitatively. Additionally, we discuss our findings from three ablations for
our model.

###  4.1 Quantitative Results

Once we complete the aforementioned 3-stage training process, we leverage a
couple of existing models along with the trained components to make
predictions on CLEVR_HYP Sampat et al. (2021) test data (as shown in the right
part of the Figure 5). The CLEVR_HYP has three test sets- Ordinary, 2HopTA and
2HopQH. Refer to Section 2.2 for the description of each test setting with
examples.

Test performance on CLEVR_HYP
---
|  | TIE | SGU | ARL
Ordinary |  | 64.7 | 70.5 | 76.4
2HopAT |  | 55.6 | 64.4 | 69.2
2HopQH |  | 58.7 | 66.5 | 70.7
Table 2: Performance of two baselines (TIE, SGU) reported in Sampat et al.
(2021) and our proposed model (ARL) on three test sets of CLEVR_HYP
Accuracy(%) by Action Types
---
Validation |  | TIE | SGU |  $\frac{}{}$ ARL
Add |  | 58.2 | 65.9 | 70.3
Remove |  | 89.4 | 88.6 | 94.1
Change |  | 88.7 | 91.2 | 95.8
Move |  | 61.5 | 69.4 | 72.6
2HopTA |  | TIE | SGU |  $\frac{}{}$ ARL
Add + Remove |  | 53.6 | 63.2 | 66.7
Add + Change |  | 55.4 | 64.7 | 70.6
Add + Move |  | 49.7 | 57.5 | 63.2
Remove + Change |  | 82.1 | 85.5 | 91.6
Remove + Move |  | 52.6 | 66.4 | 68.3
Change + Move |  | 53.8 | 63.3 | 67.1
Table 3: Performance breakdown of models by different action types in
validation and 2HopTA test set Accuracy(%) by Reasoning Types
---
Validation |  | TIE | SGU | ARL
Count |  | 60.2 | 74.3 | 78.6
Exist |  | 69.6 | 72.6 | 77.3
CompareInteger |  | 56.7 | 67.3 | 70.7
CompareAttribute |  | 68.7 | 70.5 | 73.4
QueryAttribute |  | 65.4 | 68.1 | 74.9
2HopQH |  | TIE | SGU | ARL
And |  | 59.2 | 67.1 | 70.3
Or |  | 58.8 | 67.4 | 71.5
Not |  | 58.1 | 65.0 | 68.4
Table 4: Performance breakdown of models by different question types in
validation and 2HopQH test set

The CLEVR_HYP dataset is formulated as a classification task with exactly one
correct answer. Therefore, the exact match accuracy (%) metric is used for
evaluation. Table 2 demonstrates the performance of our proposed model in
comparison with the two best performing existing models TIE and SGU, described
in Section 2.3. Our proposed approach outperforms those baselines by 5.9%,
4.8% and 4.2% on Ordinary, 2HopTA Test and 2HopQH Test respectively. This
demonstrates that our model not only achieves better overall accuracy but also
has improved generalization capability when multiple actions have to be
performed on the image or understand logical combinations of attributes while
performing reasoning.

In Table 3, we analyze the ability of models to perform a particular action.
For validation set, the model is expected to perform one of the four actions-
add objects, remove objects, change in attributes or move objects. Overall, we
can observe that our proposed method ARL achieves better fine-grained accuracy
for all action types compared to existing models. All three models do quite
well on ‘remove’ and ‘change’ actions whereas struggle when new objects are
added or existing objects are moved around. Yet, our model shows 4.4% and 3.2%
improvements on ‘add’ and ‘move’ respectively compared to the best previous
baseline.

For 2HopTA test set, the model is expected to perform two different actions
(among add, remove, change and move) one after the other. Our observation from
the Validation results remains consistent when multiple actions are combined.
In other words, models were able to achieve relatively high accuracy for
actions ‘remove’ and ‘change’, hence their combination ‘remove+change’ also
has high model performance. Whereas other combinations of actions accomplish
relatively lower performance. It leads to the conclusion that understanding
the effect of different actions is of varying complexity. It also indicates
that the learned action representations in our proposed model are helpful as
it shows better generalization by action types.

Figure 7: Correct scene graph predictions for the given (input image, action
text) by our ARL model

Though understanding changes caused by actions is the core challenge in
CLEVR_HYP Sampat et al. (2021) task, it has a question answering downstream
task. To answer questions in the CLEVR_HYP dataset, models should be able to
perform counting, check the existence of objects given the criteria, compare
sets of objects, or retrieve attributes of the desired objects. We carry out a
similar analysis of models based on their capability to perform above-
mentioned reasoning tasks. The results are summarized in Table 4.

For validation set, our proposed method ARL has better fine-grained accuracy
across all reasoning types, but improvements on ‘query attribute’ and ‘exist’
types are maximum (6.8% and 4.7% respectively). For the 2HopQH test set, the
model is expected to perform logical operations within a particular reasoning
type. For example, ‘How many objects are either red or cylinder?’ and ‘Are
there any rubber cubes that are not green?’. Though we see some gains here as
well, our overall pipeline is limited by the capabilities of the question
answering model of Yi et al. (2018) we use in stage-3.

###  4.2 Qualitative results

In Figure 7, we visually demonstrate scene graphs predicted by our ARL model
over a variety of action texts. From examples 1-6, we can observe that the
model can correctly identify objects that match the object attributes (color,
size, shape, material) provided in the action text. Examples 4 and 6
demonstrate that our system is consistent in predictions when we use synonyms
of various words (e.g. sphere$\sim$ball, shiny$\sim$metallic) in the dataset.
Finally, examples 7-9 show that our model does reasonably well on other
actions (add, change, move).

We further generate a t-SNE plot of action vectors learned by our best
proposed model, which is shown in Figure 9. At a first glance, we can say that
the learned action representations formulate well-defined and separable
clusters corresponding to each action type. Clusters for add, remove and
change actions are closer and somewhat overlapping. We observed that many
samples of type ‘change’ is interpreted by the reasoner as ‘remove+add’
action. For example, if a color of ’small blue metal sphere’ is changed to
’red’, the action reasoner interprets it as removal of the ’small blue metal
sphere’ followed by an addition of a ’small red metal sphere’ on the same
location.

###  4.3 Ablations

#### Importance of stage-1 training

Cause-effect learning with respect to actions is a key focus in CLEVR_HYP. In
existing models, it is formulated as a updated scene graph prediction task
(i.e. given an initial scene and an action, determine what the resulting scene
would look like after executing the action). In our opinion, stage-1 plays a
critical role in learning causal structure of the world. To demonstrate this,
we set up two experiments; first, where training takes place in a sequential
manner (stage-1 followed by stage-2), where trained encoder-decoders from
stage-1 are frozen and utilized in stage-2. Second experiment, where there is
no separate stage-1 training and encoder-decoder in stage-2 are randomly
initialized.

Figure 8: The t-SNE plot of learned action vectors

Figure 9: Performance of our model with varying (top) data size and (bottom)
action vector lengths

The results are summarized in Table 5. We can observe that inclusion of
stage-1 training improves the accuracy of scene graph prediction by $\sim$30%
compared to the stage(2 only) model. To evaluate question answering task of
CLEVR_HYP, both setups are followed by stage-3 where the image parser and
scene-graph question answering modules are combined to predict the answer. It
is known that Yi et al. (2018) has near-perfect performance on the scene graph
question answering task over CLEVR Johnson et al. (2017). As a result, the
gains achieved in the scene graph task directly benefit the question answering
performance without much of a loss. In other words, there are only 0.2%
instances where the scene prediction is correct but the final answer is
incorrect.

#### Performance with different lengths of learned action vector in stage-1

In this ablation, the goal is to find out optimal length of action vectors
that can reasonably simulate the effects of the actions. We experiment with
different lengths of learned action vector- from 25 to 200 in increment of 25.
Figure 9 (bottom) shows the effect of training with diverse action vector
lengths on scene graph update and downstream question answering task. The
model learns better initially when the vector length is increased, however
performance reaches at peak for the action vector length of 125.

Task | Experiment | Accuracy (%)
---|---|---
Scene Graph Update | Stage(2 only) | 56.3
Stage(1+2) | 87.2
Question Answering | Stage(2+3 only) | 45.7
Stage(1+2+3) | 76.4
Table 5: Performance of our model in the absence and presence of stage-1 over
ordinary test set

##  5 Related Works

In this section, we discuss existing research efforts that align with our work
in this paper. Specifically, we elaborate on tasks involving learning action
representations, counterfactual reasoning, and what-if question answering
datasets.

#### Tasks involving learning representation of actions:

Better representation learning is key to success in all kinds of artificial
intelligence problems Banerjee et al. (2021); Gan et al. (2020); Chen et al.
(2021); Lee et al. (2018b, a). Learning a mapping from the goal (provided in
natural language) to a sequence of actions to be performed in a visual
environment is a common task in robotics Kanu et al. (2020); Shridhar et al.
(2020). Specifically, human-in-the-loop methods for training robots to perform
various actions involve learning a mapping between verbal commands and low-
level motor controls of a robot Stepputtis et al. (2020). Another relevant
task is vision-and-language navigation Anderson et al. (2018); Chen et al.
(2019); Nguyen et al. (2019), where an agent navigates in a visual environment
to find the goal location by following natural language instructions.
Navigation tasks focus on selecting the right actions to achieve desired goals
provided a visual environment and natural language instructions. Our focus in
this paper is to develop models that can implicitly reason about the effect of
actions rather than determining which action to perform.

#### Counterfactual vision-language reasoning:

Counterfactual reasoning is termed as an ability to develop mental
representations to generate alternate consequences about an event that
happened in the past based on given criteria. Inspired by this human ability,
there have been efforts to utilize this concept to improve many aspects of
language and vision-language research; Kusner et al. (2017) and Garg et al.
(2019) proposed methods to measure counterfactual fairness of models. A few
recent works incorporated counterfactual augmentation of training sets Zmigrod
et al. (2019); Fu et al. (2020b) to improve the robustness of models and
discourage biases. Contrary to that, the work of Fu et al. (2020a) was the
first to utilize counterfactual instructions in training (ex. multiple
questions asked to the same image set) to deal with the data scarcity issue
and improve the generalization.

#### What-if question answering datasets:

WIQA Tandon et al. (2019) is a testbed for what-if reasoning over natural
language contexts. Provided a procedural paragraph, the task is to answer the
question “Does change in X result in change in Y?” (where X and Y are two
events from the paragraph) as a 3-way choice- correct, opposite, or no effect.
In the vision-language domain, TIWIQ Wagner et al. (2018) was among the
earliest works. Given a synthetically rendered table-top scene, the task is to
generate a textual response to the what-if question when an action (push,
rotate, remove or drop) is performed on an object. However, the evaluation of
open-ended text generation is challenging. To fill in this gap, Sampat et al.
(2021) created CLEVR_HYP dataset. It shares similarities with TIWIQ for having
rendered images, limited action types, and QA as a task. However, the key
difference is that in CLEVR_HYP, an action can cause changes to multiple
objects in the scene, which is not the case with TIWIQ.

##  6 Conclusion

In the vision and language domain, several tasks are proposed that require an
understanding of the causal structure of the world. In this work, we propose
an effective way of learning action representations and implement a 3-stage
model for the what-if vision-language reasoning task CLEVR_HYP. We provide
insights on the learned action representations and validate the effectiveness
of our proposed method through ablations. Finally, we demonstrate that our
proposed method outperforms existing baselines while being data-efficient and
showing some degree of generalization capability. By extending our approach to
a larger set of actions, we aim to develop AI agents which are equipped with
action-effect reasoning capability and can better collaborate with humans in
the physical world.

## Limitations

In the CLEVR_HYP dataset, all actions are considered to be independent of each
other and execution of actions is always guaranteed. However, we found few
instances in the CLEVR_HYP dataset where two different actions taken over an
initial scene leads to the same resulting effects. Our proposed 3-stage model
has higher error rates and low confidence for such samples. Further, in real
world situations, actions can have inter-dependencies on world conditions or
have other properties such as order-sensitivity, symmetry with respect to
other actions, reversibility etc. Exploring hypothetical reasoning problems
from aforementioned aspects is still an open research direction.

## Computing Infrastructure

All experiments are done over Tesla V100-PCIE-16GB GPU. Total time for all
experiments (including parameter search for best model) utilized approximately
70 GPU hours.

## Ethical Considerations

In this paper, our experiments are limited to publicly available CLEVR_HYP
dataset that is synthetically generated through controlled environment. Thus,
there are no ethical violations or known bias issues, to our best knowledge.

## Acknowledgements

We are thankful to the anonymous reviewers for the constructive feedback. This
work is partially supported by the grants NSF 1816039 and NSF 2132724.

## References

  * Anderson et al. (2018) Peter Anderson, Qi Wu, Damien Teney, Jake Bruce, Mark Johnson, Niko Sünderhauf, Ian D. Reid, Stephen Gould, and Anton van den Hengel. 2018.  Vision-and-language navigation: Interpreting visually-grounded navigation instructions in real environments.  In _2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City, UT, USA, June 18-22, 2018_ , pages 3674–3683. IEEE Computer Society.
  * Banerjee et al. (2020) Pratyay Banerjee, Chitta Baral, Man Luo, Arindam Mitra, Kuntal Pal, Tran C Son, and Neeraj Varshney. 2020.  Can transformers reason about effects of actions? _arXiv preprint arXiv:2012.09938_.
  * Banerjee et al. (2021) Pratyay Banerjee, Tejas Gokhale, Yezhou Yang, and Chitta Baral. 2021.  Weakly supervised relative spatial reasoning for visual question answering.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 1908–1918.
  * Chen et al. (2019) Howard Chen, Alane Suhr, Dipendra Misra, Noah Snavely, and Yoav Artzi. 2019.  Touchdown: Natural language navigation and spatial reasoning in visual street environments.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 12538–12547.
  * Chen et al. (2020) Lichang Chen, Guosheng Lin, Shijie Wang, and Qingyao Wu. 2020.  Graph edit distance reward: Learning to edit scene graph.  In _European Conference on Computer Vision_ , pages 539–554. Springer.
  * Chen et al. (2021) Nuo Chen, Chenyu You, and Yuexian Zou. 2021.  Self-Supervised Dialogue Learning for Spoken Conversational Question Answering.  In _Proc. Interspeech 2021_ , pages 231–235.
  * Fu et al. (2020a) Tsu-Jui Fu, Xin Wang, Scott Grafton, Miguel Eckstein, and William Yang Wang. 2020a.  Iterative language-based image editing via self-supervised counterfactual reasoning.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 4413–4422.
  * Fu et al. (2020b) Tsu-Jui Fu, Xin Eric Wang, Matthew F Peterson, Scott T Grafton, Miguel P Eckstein, and William Yang Wang. 2020b.  Counterfactual vision-and-language navigation via adversarial path sampler.  In _European Conference on Computer Vision_ , pages 71–86. Springer.
  * Gan et al. (2020) Zhe Gan, Yen-Chun Chen, Linjie Li, Chen Zhu, Yu Cheng, and Jingjing Liu. 2020.  Large-scale adversarial training for vision-and-language representation learning.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 6616–6628. Curran Associates, Inc.
  * Garg et al. (2019) Sahaj Garg, Vincent Perot, Nicole Limtiaco, Ankur Taly, Ed H Chi, and Alex Beutel. 2019.  Counterfactual fairness in text classification through robustness.  In _Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society_ , pages 219–226.
  * He et al. (2017) Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross B. Girshick. 2017.  Mask R-CNN.  In _IEEE International Conference on Computer Vision, ICCV 2017, Venice, Italy, October 22-29, 2017_ , pages 2980–2988. IEEE Computer Society.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016.  Deep residual learning for image recognition.  In _2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016_ , pages 770–778. IEEE Computer Society.
  * Johnson et al. (2017) Justin Johnson, Bharath Hariharan, Laurens van der Maaten, Li Fei-Fei, C. Lawrence Zitnick, and Ross B. Girshick. 2017.  CLEVR: A diagnostic dataset for compositional language and elementary visual reasoning.  In _2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017_ , pages 1988–1997. IEEE Computer Society.
  * Kanu et al. (2020) John Kanu, Eadom Dessalene, Xiaomin Lin, Cornelia Fermuller, and Yiannis Aloimonos. 2020.  Following instructions by imagining and reaching visual goals.  _arXiv preprint arXiv:2001.09373_.
  * Kusner et al. (2017) Matt J Kusner, Joshua R Loftus, Chris Russell, and Ricardo Silva. 2017.  Counterfactual fairness.  _arXiv preprint arXiv:1703.06856_.
  * LeCun (2022) Yann LeCun. 2022.  Some obvious facts related to human level ai.
  * Lee et al. (2018a) Chia-Hsuan Lee, Shang-Ming Wang, Huan-Cheng Chang, and Hung-Yi Lee. 2018a.  Odsqa: Open-domain spoken question answering dataset.  In _2018 IEEE Spoken Language Technology Workshop (SLT)_ , pages 949–956. IEEE.
  * Lee et al. (2018b) Chia-Hsuan Lee, Szu-Lin Wu, Chi-Liang Liu, and Hung-yi Lee. 2018b.  Spoken squad: A study of mitigating the impact of speech recognition errors on listening comprehension.  _Proc. Interspeech 2018_ , pages 3459–3463.
  * McCarthy et al. (1960) John McCarthy et al. 1960.  _Programs with common sense_.  RLE and MIT computation center.
  * Nguyen et al. (2019) Khanh Nguyen, Debadeepta Dey, Chris Brockett, and Bill Dolan. 2019.  Vision-based navigation with language-based assistance via imitation learning with indirect intervention.  In _IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019_ , pages 12527–12537. Computer Vision Foundation / IEEE.
  * Sampat et al. (2021) Shailaja Keyur Sampat, Akshay Kumar, Yezhou Yang, and Chitta Baral. 2021.  Clevr_hyp: A challenge dataset and baselines for visual question answering with hypothetical actions over images.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 3692–3709.
  * Sampat et al. (2022) Shailaja Keyur Sampat, Maitreya Patel, Subhasish Das, Yezhou Yang, and Chitta Baral. 2022.  Reasoning about actions over visual and linguistic modalities: A survey.  _arXiv preprint arXiv:2207.07568_.
  * Shridhar et al. (2020) Mohit Shridhar, Jesse Thomason, Daniel Gordon, Yonatan Bisk, Winson Han, Roozbeh Mottaghi, Luke Zettlemoyer, and Dieter Fox. 2020.  ALFRED: A benchmark for interpreting grounded instructions for everyday tasks.  In _2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020_ , pages 10737–10746. IEEE.
  * Stepputtis et al. (2020) Simon Stepputtis, Joseph Campbell, Mariano Phielipp, Stefan Lee, Chitta Baral, and Heni Ben Amor. 2020.  Language-conditioned imitation learning for robot manipulation tasks.  _Advances in Neural Information Processing Systems_ , 33.
  * Tan and Bansal (2019) Hao Tan and Mohit Bansal. 2019.  LXMERT: Learning cross-modality encoder representations from transformers.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 5100–5111. Association for Computational Linguistics.
  * Tandon et al. (2019) Niket Tandon, Bhavana Dalvi, Keisuke Sakaguchi, Peter Clark, and Antoine Bosselut. 2019.  WIQA: A dataset for “what if…” reasoning over procedural text.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 6076–6085. Association for Computational Linguistics.
  * Vo et al. (2019) Nam Vo, Lu Jiang, Chen Sun, Kevin Murphy, Li-Jia Li, Li Fei-Fei, and James Hays. 2019.  Composing text and image for image retrieval - an empirical odyssey.  In _IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019_ , pages 6439–6448. Computer Vision Foundation / IEEE.
  * Wagner et al. (2018) Misha Wagner, Hector Basevi, Rakshith Shetty, Wenbin Li, Mateusz Malinowski, Mario Fritz, and Ales Leonardis. 2018.  Answering visual what-if questions: From actions to predicted scene descriptions.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pages 0–0.
  * Yi et al. (2018) Kexin Yi, Jiajun Wu, Chuang Gan, Antonio Torralba, Pushmeet Kohli, and Josh Tenenbaum. 2018.  Neural-symbolic VQA: disentangling reasoning from vision and language understanding.  In _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada_ , pages 1039–1050.
  * Zmigrod et al. (2019) Ran Zmigrod, Sabrina J Mielke, Hanna Wallach, and Ryan Cotterell. 2019.  Counterfactual data augmentation for mitigating gender stereotypes in languages with rich morphology.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 1651–1661.