Therefore, $Q''$ does not contain any vertex of another path $P'_{j'}$ with $j'\ne j$. We now show that the edge of $P'_j$ going out of $u'$ (that we denote by $e'$) is irrelevant.
First, since $u'\in P_{i'}\cap P'_j$, no other path of $\hat{\pset_0}\cup \hat{\pset_1}$ may contain $u'$, and therefore no other path of $\hat{\pset_0}\cup \hat{\pset_1}$ may contain the edge $e'$. We can then modify the path $P'_j$ in $\hat{\pset_2}$ by replacing its segment between $u'$ and $w'$ by $Q'$. Clearly, we obtain a new pair $\hat{\pset}_0, \hat{\pset}_1'$ of sets of node-disjoint paths in $\hat H\setminus e$, where $\hat{\pset}_0$ routes $B_0$ to $B_2$ and $\hat{\pset}_1'$ routes $B_1$ to $B_3$. This contradicts the fact that $\hat H$ contains no irrelevant edges.
Therefore, no bumps may exists.

Let $h'$ be the model that embeds the $(\gamma\times\gamma)$-grid into $G_{\lambda}$.

Since the property <ref> is satisfied, we can efficiently find a set $\hat\pset$ of at least $\lfloor\beta/2\rfloor$ edge-disjoint paths, each connecting a distinct vertex of $S$ to a distinct vertex of $V_{\lambda}$. Let $V'\subseteq V_{\lambda}$ be the set of endpoints  of these paths lying in $V_{\lambda}$.
Recall that vertex set $V_{\lambda}$ is partitioned into four contiguous subsets $B_0,B_1,B_2,B_3$.
Therefore, at least one of these four vertex sets (say $B_0$)

contains at least $\lfloor\beta/2\rfloor/4$ vertices of $V'$.

We view the paths connecting vertices of $B_0$ to vertices of $B_2$ as forming the columns of the grid, and we view the paths connecting vertices of $B_1$ to vertices of $B_3$ as forming the rows of the grid.
Therefore, each column of $R'$ corresponds to a vertex in $B_0$.
We let $V'_0=B_0\cap V'$, and let $\pset'\subseteq\hat{\pset}$ contain all paths with an endpoint in $V'_0$.
Lastly, we delete from $R'$ all columns that do not correspond to vertices of $V'_0$ and delete arbitrary $\gamma-|V'_0|$ columns. Let $R$ be the resulting $|V'_0|\times |V'_0|$ grid and let $h$ be the model induced by $h'$. From the discussion, $|V'_0|=\Theta(\beta)=\Theta(\alpha'r/\Delta)$. For each vertex $x\in V(R)$, we select an arbitrary vertex of $h(x)$ as $v_x$.
Denoting by $I$ the set of vertices in last row of $R$, it is easy to see that each path of $\pset'$ that connects a vertex of $S$ to a vertex of $B_0$ can be extended to a path that connects a vertex of $S$ to a vertex of $\set{v_x\mid x\in I}$, by concatenating it with a subpath of $\hat\pset_0$. We denote by $\pset$ the resulting paths obtained from $\pset'$ and $\hat\pset_0$. It is clear that the paths in $\pset$ are edge-disjoint.
This completes the construction of the grid minor $R$ and the set $\pset$ of edge-disjoint paths connecting $S$ to the vertices of $\set{v_x\mid x\in I}$, thus completing the proof of Lemma <ref>.

to be moved to intro:
To the best of our knowledge, the problem was only previously studied by Pelsmajer et al in [28]. They first showed that the problem is NP-complete, and then gave approximation algorithms to some special cases. In particular, when the number of vertices is $k$, they presented an algorithm that approximates the $\optcrors(G,\Sigma)$ to within a factor of $O(k^4)$ in time $O(m^k\log m)$, where $m$ is the number of edges in the graph.

In this section we provide the proof of  Corollary <ref>.

We fix the index $i$. For simplicity, we denote $C_i$ by $C$, $C_i^+$ by $C^+$, and $\chi_i$ by $\chi$.
The edge set $E^*$ is obtained by directly applying Lemma <ref>. To obtain a drawing $\psi'$ of $C^+$, we start with the drawing $\psi$ of $C^+$ given by Lemma <ref>. We will iteratively process each bridge $R\in \rset_{G}(C)$, and finally obtain a drawing $\phi'$ that satisfies all conditions of Corollary <ref>.

We now describe the execution of an iteration in detail.
For a bridge $R\in \rset_{G}(C)$, we let $T\in X_{G}(C)$ be the corresponding tree in the extension of $C$. Recall that $T'$ is obtained from $T$ by suppressing all degree-$2$ nodes, we denote its root by $r_{T'}$, and let $D_{r_{T'}}$ be a small disc around the image of $r_{T'}$ in $\psi$. We then place a planar drawing of whole tree $T'$ into this disc in a planar drawing, so that the vertices of $L(R)$ lie on the boundary of this disc.
Finally, we connect the image of the vertices of $L(R)$ in $\psi$ to the to the new copy of the vertices of $L(R)$ on the boundary of $D_{r_{T'}}$. This is done by following the images of the paths in $T'$ connecting it leaves to its root in the original drawing. Note that this may increase the number of crossings by at most a $O(\mu)$ factor, so the number of crossings in $\psi'$ is still bounded by $O\!\left(\chi_i\cdot \poly(\mu\Delta\log n)\right)$.

§ PROOFS OMITTED FROM SECTION <REF>

§.§ Proof of Lemma <ref>

We use the following theorem from [32].

There is an efficient algorithm, that, given a simple graph $G$, finds a drawing of $G$ with $O\left((\optcro(G)+\sum_{v\in V(G')}\deg^2_G(v))\cdot\poly(\log n)\right)$ crossings.

Note that our input graph $G$ is not necessarily simple. We remedy this by subdividing every edge of $G$ with a new vertex, obtaining a simple graph $G'$. Applying the algorithm from Lemma <ref> to graph $G'$, we obtain a drawing $\phi'$ of $G'$ with the number of crossings bounded by:

\[\begin{split}
&O\Bigg(\Big(\optcro(G')+\sum_{v\in V(G')}\deg^2_{G'}(v)\Big)\cdot  \poly(\log n)\Bigg)\\
&\quad\quad\quad\quad\quad\quad\quad\quad\leq O\Bigg(\Big(\optcro(G)+\Delta \cdot \sum_{v\in V(G')}\deg_{G'}(v)\Big)\cdot\poly(\log n) \Bigg)\\
&\quad\quad\quad\quad\quad\quad\quad\quad\leq O\left (\left (\optcro(G)+\Delta \cdot |E(G')|\right )\cdot\poly(\log n) \right )\\
&\quad\quad\quad\quad\quad\quad\quad\quad\leq O\left (\left (\optcrors(G)+\Delta \cdot |E(G)|\right )\cdot\poly(\log n) \right ).
\end{split}
\]

Here we use the fact that any solution to an instance $(G,\Sigma)$ of defines a solution to instance $G$ of of the same value, so $\optcro(G)\leq \optcrors(G)$.

Notice that drawing $\phi'$ of $G'$ naturally induces a drawing $\phi$ of $G$, with the number of crossings bounded by $O\left (\left (\optcrors(G)+\Delta \cdot |E(G)|\right )\cdot\poly(\log n) \right )$. However, this drawing may not respect the rotation system $\Sigma$. We slightly modify the drawing $\phi$ in order to rectify that.

We process every vertex $v\in V(G)$ one-by-one. When vertex $v$ is processed, we let $\eta(v)$ be a small disc around $v$ in the current drawing $\phi$. For every edge $e\in \delta_{G}(v)$ that is incident to $v$, we let $\sigma_e$ be the segment of the image of $v$ in $\phi$ that is contained in $\eta(v)$, and we let $p_e$ be the unique point on the intersection of $\sigma_e$ and the boundary of the disc $\eta(v)$. We define new curves $\set{\sigma'_e\mid e\in \delta_G(v)}$, that are contained in $\eta(v)$, such that each curve $\sigma'_e$ originates at $p_e$ and terminates at the image of $v$ in $\phi$. We ensure that every pair of the resulting curves crosses at most once, and moreover, the images of the curves in $\set{\sigma'_e\mid e\in \delta_G(v)}$ enter the vertex $v$ in  a circular order consistent with the order $\oset_v\in \Sigma$.

Once every vertex of $V(G)$ is processed, we obtain a drawing of $G$ that respects $\Sigma$. The total number of new crossings that we introduced is bounded by $\sum_{v\in V(G)}(\deg_G(v))^2\leq \Delta\cdot |E(G)|$. Therefore, we obtain a final drawing of graph $G$ that respects $\Sigma$, and has at most $O\left (\left (\optcrors(G)+\Delta \cdot |E(G)|\right )\cdot\poly(\log n) \right )$ crossings.

§.§ Proof of Lemma <ref>

The following claim is central to the proof of the lemma.

There is an efficient algorithm, that, given an instance $(H,\Sigma)$ of the problem, an edge $e\in E(H)$, and a drawing $\phi$ of graph $H\setminus \set{e}$ that respects $\Sigma$, computes one of the following:

* either a drawing $\hat \phi$ of $H\setminus \set{e}$ that respects $\Sigma$, with $\cro(\hat \phi)<\cro(\phi)$; or

* a drawing $\phi'$ of $H$ that respects $\Sigma$, with $\cro(\phi')\le \cro(\phi)+|E(H)|$.

It is now easy to complete the proof of Lemma <ref> using Claim <ref>.
We denote $E'=\set{e_1,\ldots,e_r}$. The algorithm consists of $r$ phases, where in the $i$th phase we compute a drawing $\phi_i$ of graph $(H\setminus E')\cup \set{e_1,\ldots,e_i}$ that respects the rotation system $\Sigma$. We set $\phi_0=\phi$. We now describe the $i$th phase.

Recall that, at the beginning of the $i$th phase, we are given a drawing $\phi_{i-1}$ of graph $(H\setminus E')\cup \set{e_1,\ldots,e_{i-1}}$.  We iteratively apply the algorithm from Claim <ref> to the current drawing $\phi_{i-1}$. If the outcome of the algorithm is another drawing  $\hat \phi_{i-1}$ of of graph $(H\setminus E')\cup \set{e_1,\ldots,e_{i-1}}$ that respects $\Sigma$ with $\cro(\hat \phi_{i-1})<\cro(\phi_{i-1})$, then we replace $\phi_{i-1}$ with $\hat \phi_{i-1}$ and continue to the next iteration. Otherwise, we obtain the desired drawing $\phi_i$ of graph $(H\setminus E')\cup \set{e_1,\ldots,e_{i}}$ that respects $\Sigma$, with $\cro(\phi_i)\le \cro(\phi_{i-1})+|E(H)|$ (recall that $E'\subseteq E(H)$). We then return this drawing as the outcome of the $i$th phase, and continue to the next phase.

Let $\phi'=\phi_r$ be the drawing of $H$ that is obtained after the $r$th phase. Then we are guaranteed that $\phi'$ respects the rotation system $\Sigma$, and moreover, from the above discussion, $\cro(\phi')\le \cro(\phi)+|E'|\cdot|E(H)|$.
Therefore, in order to complete  the proof of Lemma <ref>, it is now enough to prove Claim <ref>.

Claim <ref>
Let $e=(u,v)$. We compute a curve $\gamma$ in the current drawing $\phi$ of $H\setminus\set{e}$ connecting $\phi(u)$ to $\phi(v)$, such that (i) $\gamma$ intersects the drawing of $H\setminus\set{e}$ at images of edges only; (ii) $\gamma$ does not contain any crossings of the drawing $\phi$; and (iii) if we add the edge $e$ to the drawing $\phi$ such that the image of $e$ is $\gamma$, then the resulting drawing of $H$ respects the rotation system $\Sigma$. Among all curves $\gamma$ with the above properties, we choose the one that has fewest crossings with the edges of $H\setminus \set{e}$, and does not cross itself. Such a curve $\gamma$ can be computed as follows.
Let $\fset$ be the set of all faces in the drawing $\phi$ of $H\setminus\set{e}$. Let $F$ be the face that is incident to $v$, such that, if edge $e$ is added to the drawing in a manner that respects the ordering $\oset_v$ of all edges incident to $v$, then there must be a segment of the image of $e$ that contains $v$, does not contain any crossings, and is contained in $F$. We define the face $F'$ incident to $u$ similarly. We then compute a graph that is dual to the drawing $\phi$ of $H\setminus\set{e}$, and in that graph we compute a shortest path between the two vertices that represent faces $F$ and $F'$. The resulting path then naturally defines the desired curve $\gamma$.

Assume first that curve $\gamma$ participates in at most $|E(H)|$ crossings. In this case we simply add the edge $e$ to the drawing $\phi$ so that the image of $e$ is $\gamma$, and return the resulting drawing of $H$. Clearly, this drawing has at most $\cro(\phi)+|E(H)|$ crossings, and it respects $\Sigma$.

Assume now that $\gamma$ has more than $|E(H)|$ crossings. Then there is some edge $e'\in E(H)\setminus\set{e}$ whose image intersects $\gamma$ at least twice. Let $x,y$ be two intersections of $\gamma$ and the image of $e'$. We denote by $\sigma$ the segment of $\gamma$ between $x$ and $y$, and we denote by $\sigma'$ the segment of the image of $e'$ between $x$ and $y$. Let $N$ be the number of crossings in which $\sigma$ participates (excluding $x$ and $y$), and let $N'$ be defined similarly for $\sigma'$. Observe that $N< N'$ must hold. Indeed, if $N\geq N'$, then we can modify the curve $\gamma$ as follows. Assume that $\gamma$ is directed so that $x$ appears before $y$ on $\gamma$. Let $t$ be a point on $\gamma$ that appears just before point $x$ on it, and let $t'$ be a point on $\gamma$ that appears just after point $y$ on it. Let $\sigma^*$ be a curve that connects $t$ to $t'$, and follows the segment $\sigma'$. By replacing the segment of curve $\gamma$ between $t$ and $t'$ with $\sigma^*$, we obtain a new curve $\gamma'$ that has all the required properties, but has fewer crossings than $\gamma$, a contradiction. We conclude that $N<N'$ must hold.
We then modify the drawing of  the edge $e'$ in $\phi$, by replacing the segment $\sigma'$ with $\sigma$. This produces a new drawing $\hat \phi$ of $H\setminus\set{e}$ with $\cro(\hat \phi)<\cro(\phi)$, that respects the rotation system $\Sigma$.

§.§ Proof of Lemma <ref>

Given the input drawing $\phi$ of $G$,
we perform sequentially, for each vertex $v\in V$, a local adjustment step to the drawing, such that, after this step, the image of the edges of $\delta(v)$ in the current drawing enter $v$ in the same order as the rotation $\oset_v$ in $\Sigma$.
Therefore, after we perform the local adjustment steps for all vertices in $V$, the resulting drawing $\phi'$ respects the rotation system $\Sigma$.

It remains to describe a local adjustment step at $v$. If the image of the edges of $\delta(v)$ in the current drawing enter $v$ in the same order as the rotation $\oset_v$, then we do nothing. Otherwise, we draw a small disc $D_v$ around $v$, and reorganize the ordering of images of the edges of $\delta(v)$ entring $v$ so that it coincides with $\oset_v$, by letting each pair of edges in $\delta(v)$ cross at most once. Please see Figure <ref> for an illustration. It is clear that such a local adjustment step at $v$ introduces at most $\deg_G^2(v)$ new crossings. Therefore, the final drawing $\phi'$ contains at most $\cro(\phi)+\sum_{v\in V}\deg^2_G(v)$ crossings.

[The local drawing at $v$ before the local adjustment.]0.21

[The rotation $\oset_v$ of $v$ in $\Sigma$.]0.21

[The local drawing at $v$ after the local adjustment.]0.21
An illustration of a local adjustment step.

§.§ Proof of Lemma <ref>

We show that, given a graph $G$, an edge $(u,v)\in E(G)$, a rotation system $\Sigma$ on $G$ and a drawing $\phi'$ of $G\setminus \set{e}$ respecting $\Sigma$, we can efficiently compute a drawing $\phi$ of $G$ that respects $\Sigma$, such that $\cro(\phi)\le \cro(\phi')+|E(G)|$.
Note that this directly implies Lemma <ref>, since we can add the edges in $E'$ one-by-one to the drawing $\phi'$, introducing at most $|E(G)|$ new crossings each time.

For the edge $e=(u,v)\in E'$, we arbitrarily draw a curve $\gamma_e$ connecting $\phi'(u)$ to $\phi'(v)$ as the image of $(u,v)$, such that the curve does not cross itself, and the curve enters $\phi'(u)$ and $\phi'(v)$ with respect to $\Sigma$. Then, if the image of any pair of edges in $E$ cross twice, we perform a standard uncrossing. Let $\phi$ be the resulting drawing. It is clear that we create at most $|E(G)|$ new crossings in $\phi$ in this way.

I want to suggest the following fix.

Let $G$ be a graph with a drawing $\phi$. We want to prove that, when we add one edge $e$ into the graph, we can compute a drawing $\phi'$ of $G\cup e$ such that $\cro(\phi')\le \cro(\phi)+O(|E(G)|)$.

We first insert the edge $e$ into $\phi$ in a way that creates minimum number of new crossings. This can be done via computing the shortest path in “dual graph” w.r.t. $\phi$.
Denote this drawing as $\hat{\phi}_0$.

We would like to gradually modify the drawing $\hat{\phi}_0$ of $G\cup e$ so that (i) for each $e'\in G$, $\cro_{\hat\phi}(e',G)$ does not increase; and (ii) eventually every edge $e'\in G$ intersect at most once with $e$. If this can be achieved then we are done.

We initialize $\hat\phi=\hat{\phi_0}$. Take any edge $e'$ that intersect at least twice with $e$ in $\hat{\phi}$. Let $x$ be the first intersection and let $y$ be the last intersection. We “reroute” the segment between $x$ and $y$ of the image of edge $e'$ along the segment between $x$ and $y$ of the image of edge $e$. Due to the optimality of inserting $e$, this guarantees that $e'$ participate in no more crossings with other edges of $G$ than before, and $e$ intersect with $e'$ at most once now. Note that after this operation the optimality of inserting $e$ may not hold anymore. We then re-insert $e$ optimally in the new drawing.
We repeat this process until we cannot further modify the drawing.
It can be shown that the number of crossings in the drawing only decrease after each iteration, and at the end the two desired properties are satisfied.

§.§ Proof of Lemma <ref>

Let $P$ be a path and let $v\in V(P)$ be a vertex of $P$. We denote by $P[v]$ the subpath of $P$ consisting of the edges in $P$ incident to $v$. Namely, if $P=(v_1,v_2,\ldots,v_k)$, then $P[v_1]=(v_1,v_2)$,
and for each $2\le i\le k-1$, $P[v_i]=(v_{i-1},v_i,v_{i+1})$.
For a set $\pset$ of paths in $G$ and a vertex $v$,

we define $G[\pset,v]$ as the subgraph of $G$ that contains all paths in $\set{P[v]\mid P\in \pset, v\in P}$. Therefore, $G[\pset,v]$ is a star graph with $v$ being the center of the star.
Given a rotation $\oset_v$ on the edges of $\delta(v)$, we say that the set $\pset$ of paths is locally non-interfering at $v$ with respect to $\oset_v$, iff the paths of $\pset[v]$ are non-interfering with respect to the unique planar drawing of $G[\pset,v]$ that respects $\oset_v$.

We use the following lemma.

There exists an efficient algorithm that, given a graph $G$, a rotation system $\Sigma$ on $G$ and a set $\tilde\pset$ of edge-disjoint paths connecting a pair $v,v'$ of distinct vertices of $G$, computes another set $\pset$ of $|\pset|=|\tilde{\pset}|$ edge-disjoint paths in $G$ connecting $v$ to $v'$, such that $E(\pset)\subseteq E(\tilde\pset)$, and $\pset$ is locally non-interfering at all vertices of $V(G)\setminus\set{v,v'}$ with respect to their rotations in $\Sigma$.

We note that the algorithm in Section <ref> essentially gives the proof of Lemma <ref>.
From now on we focus on the proof of Lemma <ref> using it.
Recall that we are given a graph $G$, a rotation system $\Sigma$ on $G$, and a set $\tilde\pset$ of edge-disjoint paths in $G$ connecting $v$ to $v'$.
We apply Lemma <ref> to the set $\tilde{\pset}$ of paths, and let $\pset$ be the set we obtain.
From Lemma <ref>, $|\pset|=|\tilde \pset|$ and $E(\pset)\subseteq E(\tilde\pset)$.

Note that the rotation $\oset_v$ naturally defines a cyclic order on the first edges of the paths in $\pset$. Therefore, it also defines a cyclic order on paths in $\pset$, that we denote by $\sigma$. This completes the construction of the set $\pset$ of paths and the cyclic order $\sigma$.

It remains to show that $\pset$ and $\sigma$ satisfies the properties (a) and (b) in Lemma <ref>. We first show (a).
Take a drawing $\phi\in \Phi(G,\Sigma)$ where two paths $P_1$ and $P_2$ cross. We denote $\gamma_1=\phi(P_1)$ and $\gamma_2=\phi(P_2)$. So the curves $\gamma_1$ and $\gamma_2$ intersect. Let $x$ be the intersection of $\gamma_1$ and $\gamma_2$ that is closest to $\phi(v)$ on $\gamma_1$.

In other words, if we denote by $\gamma'_1$ ($\gamma'_2$, resp.) the sub-curve of $\gamma_1$ ($\gamma_2$, resp.) between $\phi(v)$ and $x$, then $\gamma'_1$ and $\gamma'_2$ are internally disjoint. It is not hard to see that, $\phi(v')$ lies in the interior of either the region $R_{\phi}(\gamma'_2, \gamma'_1)$, or the region $R_{\phi}(\gamma'_1, \gamma'_2)$.
Assume first that the former case happens, and claim that every path in $\sigma[P_1,P_2]$ has to cross $P_1\cup P_2$. Specifically, let $P$ be a path in $\sigma[P_1,P_2]$, then $\phi(P)$ has to intersect $\gamma'_1$ or $\gamma'_2$. This is because the starting segment of $\phi(P)$ is contained in $R(\gamma'_1, \gamma'_2)$, the ending segment of $\phi(P)$ is outside the region $R(\gamma'_1, \gamma'_2)$.
Since the paths in $\pset$ are locally non-interfering with respect to $\Sigma$, and the drawing $\phi$ respects $\Sigma$, any intersection of $\phi(P)$ and $\gamma'_1\cup \gamma'_2$ cannot be the image of some vertex. Therefore, it must be a crossing between $P$ and $P_1$ or $P_2$.
Assume now that $\phi(v')$ lies in the interior of $R_{\phi}(\gamma'_1, \gamma'_2)$, then similarly, we can deduce that every path in $\sigma[P_2,P_1]$ has to cross $P_1\cup P_2$. We then show (b). From the definition of a blocking curve, $\phi(P)$ and $\phi(P')$ must intersect at some point other than $\phi(v)$ and $\phi(v')$. Note that any intersection (except $\phi(v)$ and $\phi(v)$) of $\phi(P)$ and $\phi(P')$ cannot be the image of some vertex. Therefore, it must be a crossing between an edge of $P$ and an edge of $P'$. This completes the proof of Lemma <ref>.

We now provide the proof of Lemma <ref>.
We view the paths in $\tilde\pset$ as originating from $v$ and ending at $v'$.
First, we perform the standard re-routing to the paths of $\tilde\pset$ and obtain another set $\tilde\pset'$ of paths, such that $E(\tilde\pset')\subseteq E(\tilde\pset)$, and the graph consisting of directed paths in $\tilde\pset'$ is a DAG.
This defines a topological order on vertices of $G$.
We will sequentially perform, for each vertex $u\in V(G)\setminus\set{v,v'}$  according to this topological order, a route-swap operation to all the paths that contain $u$, that is defined as follows.

Consider the graph $G[\tilde\pset',u]$ and think of the edges in $G[\tilde\pset',u]$ as directed edges, so each edge is an in-edge if it is directed towards $u$, and is an out-edge otherwise. We first recompute a matching between the in-edges and the out-edges, such that the paths formed by the new pairs of edges are locally non-interfering at $u$. Let $(e_{in}, e_{out})$ be a pair in the matching, where $e_{in}$ originally belongs to the path $P$ of $\tilde{\pset'}$ and $e_{out}$ originally belongs to the path $P'$ of $\tilde{\pset'}$. We define a new path from this pair $(e_{in}, e_{out})$ as the concatenation of the subpath of $P$ between $v$ and $u$, and the subpath of $P'$ between $u$ and $v'$. We replace the paths in $\tilde\pset'$ that contains $u$ with all the new paths that we defined according the the matching. This completes the description of a route-swap operation.
See Figure <ref> for an illustration.

[Before: the paths are not locally non-interfering at $u$.]

[After: the paths are locally non-interfering at $u$.]
An illustration of a route-swap operation.

It is not hard to see that, after the route-swap operation at $u$, the paths in $\tilde\pset'$ are locally non-interfering at $u$. Therefore, if we denote by $\pset$ the resulting set of paths that we obtain, then the paths in $\pset$ are locally non-interfering at all vertices of $V(G)\setminus\set{v,v'}$. This completes the proof of Lemma <ref>.

§.§ Proof of Lemma <ref>

Recall that the minimum-cardinality set of edges in $G''$ whose removal separates $v'$ from $v''$ has size at least $\eac^{1-2\eps}$.
From Menger's theorem, $G''$ contains a collection of at least $\ceil{\eac^{1-2\eps}}$ edge-disjoint paths connecting $v'$ to $v''$.
Our first step is to compute such a set $\tilde \pset$ of $\ceil{\eac^{1-2\eps}}$ edge-disjoint paths connecting $v'$ to $v''$, using standard max-flow techniques.
We view the paths in $\tilde\pset$ as being directed from $v'$ to $v''$. Let $H$ be the directed graph obtained by taking the union of the  directed paths in $\tilde \pset$. We can assume, from the properties of maximum flow, that $H$ is a directed acyclic graph, so there is an ordering $\oset$ of its vertices, such that, for every pair $x,y$ of vertices in $H$, if there is a path of $\tilde \pset$ in which $x$ appears before $y$, then $x$ also appears before $y$ in the ordering $\oset$.
Note that the rotation system $\Sigma''$ for graph $G''$ naturally induces a rotation system for graph $H$, that we denote by $\tilde \Sigma$. For each vertex $u\in V(H)$, we denote by $\delta^+(u)$ the set of edges leaving $u$ in $H$, and by $\delta^-(u)$ the set of edges entering $u$ in $H$. Clearly, if $u\not\in\set{ v',v''}$, then $|\delta^+(u)|=|\delta^-(u)|$.
We use the following simple observation.

There is an efficient algorithm to compute, for each vertex $u\in V(H)\setminus \set{v',v''}$, a perfect matching $M(u)\subseteq \delta^-(u)\times \delta^+(u)$ between the edges of $\delta^-(u)$ and the edges of $\delta^+(u)$, such that, for each pair of matched pairs $(e^-_1,e^+_1)$ and $(e^-_2,e^+_2)$ in $M(u)$, the intersection of the path that consists of the edges $e^-_1,e^+_1$ and the path that consists of edges $e^-_2,e^+_2$ at vertex $u$ is non-transversal with respect to $\tilde\Sigma$.

We start with $M(u)=\emptyset$ and perform $|\delta^-(u)|$ iterations. In each iteration, we select a pair $e^-\in \delta^-(u), e^+\in \delta^+(u)$ of edges that appear consecutively in the rotation $\oset_v$ of $\tilde\Sigma$. We add $(e^-,e^+)$ to $M(u)$, delete them from $\delta^-(u)$ and $\delta^+(u)$ respectively, and then continue to the next iteration. It is immediate to verify that the resulting matching $M(u)$ satisfies the desired properties.

We now gradually modify the set $\tilde \pset$ of paths in order to obtain a set $\pset$ of edge-disjoint paths connecting $v'$ to $v''$, that is non-transversal with respect to $\Sigma''$.
We process all vertices of $V(H)\setminus \set{v',v''}$ one-by-one, according to the ordering $\oset$. We now describe an iteration in which the vertex $u$ is processed. Let $\tilde\pset_u\subseteq\tilde \pset$ be the set of paths containing $u$. For each path $P\in \tilde\pset_u$, we delete the unique edge of $\delta^+(u)$ that lies on this path, thereby decomposing $P$ into two-subpaths: path $P^-$ connecting $v'$ to $u$; and path $P^+$ connecting some vertex that is the endpoint of an edge of $\delta^+(u)$ to $v''$. Define $\tilde\pset^-_u=\set{P^-\mid P\in \pset_u}$ and
$\tilde\pset^+_u=\set{P^+\mid P\in \pset_u}$.
We will glue these paths together using the edges in $\delta^+(u)$ and the matching $M(u)$ produced in Observation <ref>. Specifically, we construct a new path set $\tilde{\pset}'$ that contains, for each path $P\in \tilde \pset$, a new path $P'$, defined as follows. Consider a path $P\in \tilde\pset$. If $P\notin\tilde{\pset}_u$, then we let $P'=P$. Otherwise, consider the unique path $P^-\in \tilde{\pset}^-_u$ that is a subpath of $P$, and let $e^-_P$ be the last edge on this path. Let $e^+$ be the edge in $\delta^+(u)$ that is matched with $e^-_P$ in $M(u)$, and let $\hat P^+$ be the unique path in $\tilde\pset^+_u$ that contains $e^+$.
We then define the new path $P'$ to be the concatenation of the path $P^-$, the edge $e^+$, and the path $\hat P^+$. This finishes the description of an iteration.

Let $\pset$ be the final set of path that we obtain from the above process. It is easy to verify that the set $\pset$ of paths is non-transversal with respect to $\tilde \Sigma$, and is therefore non-transversal with respect to $\Sigma''$.

§.§ Proof of Claim <ref>

Recall that we view paths $Q_1$ and $Q_2$ as originating from $v'$ and terminating at $v''$.
Assume for contradiction that $u'$ appears before $u''$ on $Q_1$, while $u''$ appears before $u'$ on $Q_2$.

Let $\gamma_1=\tphi(Q_1)$. We denote by $\gamma_1'$ the subcurve of $\gamma_1$ between $v'$ and $u'$, and denote by $\gamma_1''$ the subcurve of $\gamma_1$ between $v'$ and $u''$, so $\gamma'_1$ is a subcurve of $\gamma''_1$.
Let $\gamma_2=\tphi(Q_2)$. We define $\gamma_2'$ and $\gamma_2''$ similarly, but note that now $\gamma''_2$ is a subcurve of $\gamma'_2$.

Consider the region $R_{\tphi}(\gamma''_1,\gamma'_2)$. Assume first that the image of $v''$ lies in the interior of this region. Since $Q_1$ and $Q_2$ do not cross in $\tphi$, and recall from Lemma <ref> that $Q_1$ and $Q_2$ are locally non-interfering, we can deduce that the curve $\gamma_2\setminus \gamma''_2$ lies outside the region $R_{\tphi}(\gamma''_1,\gamma'_2)$. But this is impossible since the curve $\gamma_2\setminus \gamma''_2$ ends at the image of $v''$ that lies in the interior of $\gamma_2\setminus \gamma''_2$, a contradiction.
Assume now that the image of $v''$ does not lie in the interior of this region. We can deduce similarly that the curve $\gamma_2\setminus \gamma''_2$ lies outside the region $R_{\tphi}(\gamma''_1,\gamma'_2)$. But this again leads to a contradiction since the curve $\gamma_2\setminus \gamma''_2$ ends at the image of $v''$ that lies in the interior of $\gamma_2\setminus \gamma''_2$.

§.§ Proof of Claim <ref>

We first prove property <ref>. Note that, the number of paths in $\qset$ that is crossed at least $\cro^{4\eps}/3$ times in $\tphi$ is at most $\tilde O(\cro^{1-4\eps})$. Therefore, the probability that one of $Q_L,Q,Q_R$ is crossed $\cro^{4\eps}/3$ times is at most $O(\cro^{-2\eps})$, and the probability that <ref> does not hold is $O(\cro^{-2\eps})$.
Note that, if a pair of paths from $K$ crosses in $\tphi$, from Lemma <ref>, at least $100\cro^{4\eps}$ paths from $\qset$ have to cross at least one of the paths in this pair. Therefore, at least one of the pair of paths is crossed $100\cro^{4\eps}/2$ times in $\tphi$, this contradicts <ref>.
On the other hand, if the image of a path in $K$ is a blocking curve, then it has to cross all paths in $\qset$ in $\tphi$, which makes it participate in at least $\Omega(\cro^{1-2\eps})$ crossings, again causing a contradiction to <ref>. Therefore, the image of paths in $K$ are non-blocking curves.

Now we prove property <ref>.
Denote $\qset=\set{Q_1,\ldots,Q_k}$. Let $r=200\cro^{4\eps}$.
We fix a vertex $u$ in the graph $G'$ that is not $v,v'$, and we will analyze the number of paths $Q_i$ in $\qset$ such that $u\in V(Q_i)\setminus V(Q_{i+r})$.

First we construct a sequence of indices as follows.
We say that an index $i$ is $u$-good if $u\in V(Q_i)\setminus V(Q_{i+r})$.
We find the smallest index $i_1\ge 1$ that is $u$-good. Then, for each $j>1$, assuming $i_1,\ldots,i_{j-1}$ are already defined, we let $i_j$ be the smallest $u$-good index that satisfies (i) $i_j\ge i_{j-1}+r$; and (ii) there exists $i_{j-1}< i^*< i_j$, such that $u\notin V(Q_{i^*})$. We continue this process to augment the sequence it cannot be augmented anymore. Let $I_u=(i_1,\ldots,i_{s})$ be the final sequence we get. We claim that $s\le  O(\cro^{1/2})$. To see why this is true, we assume the contrast that $s>30\cro^{1/2}$. For each $10\cro^{1/2}\le t\le 20\cro^{1/2}$, let $i^*_t$ be an index such that $i_t<i^*_t<i_{t+1}$ and $u\notin V(Q_{i^*_t})$. Note that the existence of such indices are guaranteed by our process of constructing the sequence $I_u$. Therefore, since each path in $\qset$ connects $v$ to $v'$, it is not hard to see that, each path in $\set{Q_{i^*_{t}}\mid 10\cro^{1/2}\le t\le 20\cro^{1/2}}$ will have to cross each path in $\set{Q_{i_{r}}\mid 1\le r\le 10\cro^{1/2}}$. This creates at least $100\cro$ crossings in $G'$, leading to a contradiction.

On the other hand, it is not hard to see that, the number of $u$-good indices in $\set{1,\ldots,k}$ is at most $O(s\cdot\cro^{4\eps})=O(\cro^{1/2+4\eps})$. Therefore, the probability that a random index $i$ is $u$-good is at most $O(\cro^{6\eps-1/2})$.

Now, for an edge $e=(u_1,u_2)$ where none of $u_1,u_2$ is $v$, for the edge to be incident to a vertex in $V(Q_i)\setminus V(Q_{i+r})$, $i$ has to be either $u_1$-good or $u_2$-good. Therefore, under the random choice of $i$, the probability that a specific edge is incident to a vertex in $V(Q_i)\setminus V(Q_{i+r})$ is at most $O(\cro^{6\eps-1/2})$. Therefore, the expected number of edges in $G'$ that are incident to a vertex in $V(Q_i)\setminus V(Q_{i+r})$, under a random choice of $i$, is at most $O(\cro^{1/2+6\eps})$. By Markov's bound, with probability $1-O(\cro^{-2\eps})$, this number is below $O(\cro^{1/2+8\eps})$.

[1]
M. Ajtai, V. Chvátal, M. Newborn, and E. Szemerédi.
Crossing-free subgraphs.
Theory and Practice of Combinatorics, pages 9–12, 1982.

[2]
C. Ambuhl, M. Mastrolilli, and O. Svensson.
Inapproximability results for sparsest cut, optimal linear
arrangement, and precedence constrained scheduling.
In Proceedings of the 48th Annual IEEE Symposium on Foundations
of Computer Science, pages 329–337, 2007.

[3]
Sanjeev Arora, Satish Rao, and Umesh V. Vazirani.
Expander flows, geometric embeddings and graph partitioning.
J. ACM, 56(2), 2009.

[4]
Christoph Buchheim, Markus Chimani, Carsten Gutwenger, Michael Jünger,
and Petra Mutzel.
Crossings and planarization.
In Handbook on Graph Drawing and Visualization, pages 43–85.

[5]
Michael J Bannister and David Eppstein.
Crossing minimization for 1-page and 2-page drawings of graphs with
bounded treewidth.
In International Symposium on Graph Drawing, pages 210–221.
Springer, 2014.

[6]
Sandeep N Bhatt and Frank Thomson Leighton.
A framework for solving vlsi graph layout problems.
Journal of Computer and System Sciences, 28(2):300–343, 1984.

[7]
Sergio Cabello.
Hardness of approximation for crossing number.
Discrete & Computational Geometry, 49(2):348–358, 2013.

[8]
Markus Chimani and Petr Hliněnỳ.
A tighter insertion-based approximation of the crossing number.
In International Colloquium on Automata, Languages, and
Programming, pages 122–134. Springer, 2011.

[9]
Julia Chuzhoy.
An algorithm for the graph crossing number problem.
In Proceedings of the forty-third annual ACM symposium on Theory
of computing, pages 303–312. ACM, 2011.

[10]
Chandra Chekuri, Sanjeev Khanna, and F Bruce Shepherd.
Edge-disjoint paths in planar graphs.
In 45th Annual IEEE Symposium on Foundations of Computer
Science, pages 71–80. IEEE, 2004.

[11]
Julia Chuzhoy, Vivek Madan, and Sepideh Mahabadi.
In Private Communication, 2016.

[12]
Julia Chuzhoy, Yury Makarychev, and Anastasios Sidiropoulos.
On graph crossing number and edge planarization.
In Proceedings of the twenty-second annual ACM-SIAM symposium on
Discrete algorithms, pages 1050–1069. SIAM, 2011.

[13]
Chandra Chekuri and Anastasios Sidiropoulos.
Approximation algorithms for euler genus and related problems.
In 2013 IEEE 54th Annual Symposium on Foundations of Computer
Science, pages 167–176. IEEE, 2013.

[14]
Walter Didimo, Giuseppe Liotta, and Fabrizio Montecchiani.
A survey on graph drawing beyond planarity.
ACM Computing Surveys (CSUR), 52(1):1–37, 2019.

[15]
Guy Even, Sudipto Guha, and Baruch Schieber.
Improved approximations of crossings in graph drawings and vlsi
layout areas.
SIAM Journal on Computing, 32(1):231–252, 2002.

[16]
M. R. Garey and D. S. Johnson.
Crossing number is NP-complete.
SIAM J. Algebraic Discrete Methods, 4(3):312–316, 1983.

[17]
M. Grohe.
Computing crossing numbers in quadratic time.
J. Comput. Syst. Sci., 68(2):285–302, 2004.

[18]
Petr Hliněnỳ and Marek Derňár.
Crossing number is hard for kernelization.
arXiv preprint arXiv:1512.02379, 2015.

[19]
P. Hlinený.
Crossing number is hard for cubic graphs.
J. Comb. Theory, Ser. B, 96(4):455–471, 2006.

[20]
K. Kawarabayashi and B. A. Reed.
Computing crossing number in linear time.
In STOC, pages 382–390, 2007.

[21]
Ken-ichi Kawarabayashi and Anastasios Sidiropoulos.
Polylogarithmic approximation for minimum planarization (almost).
In 58th IEEE Annual Symposium on Foundations of Computer
Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages
779–788, 2017.

[22]
Ken-ichi Kawarabayashi and Anastasios Sidiropoulos.
Polylogarithmic approximation for euler genus on bounded degree
In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory
of Computing, pages 164–175. ACM, 2019.

[23]
F. T. Leighton.
Complexity issues in VLSI: optimal layouts for the
shuffle-exchange graph and other networks.
MIT Press, 1983.

[24]
Tom Leighton and Satish Rao.
Multicommodity max-flow min-cut theorems and their use in designing
approximation algorithms.
Journal of the ACM (JACM), 46(6):787–832, 1999.

[25]
Richard J. Lipton and Robert Endre Tarjan.
A separator theorem for planar graphs.
SIAM Journal on Applied Mathematics, 36(2):177–189, 1979.

[26]
J. Matoušek.
Lectures on discrete geometry.
Springer-Verlag, 2002.

[27]
Michael J Pelsmajer, Marcus Schaefer, and Daniel Štefankovič.
Crossing numbers and parameterized complexity.
In International Symposium on Graph Drawing, pages 31–36.
Springer, 2007.

[28]
Michael J Pelsmajer, Marcus Schaefer, and Daniel Štefankovič.
Crossing numbers of graphs with rotation systems.
Algorithmica, 60(3):679–702, 2011.

[29]
J. Pach and G. Tóth.
Thirteen problems on crossing numbers.
Geombinatorics, 9(4):194–207, 2000.

[30]
Neil Robertson and Paul D Seymour.
Graph minors. vi. disjoint paths across a disc.
Journal of Combinatorial Theory, Series B, 41(1):115–138,

[31]
R. B. Richter and G. Salazar.
Crossing numbers.
In L. W. Beineke and R. J. Wilson, editors, Topics in
Topological Graph Theory, chapter 7, pages 133–150. Cambridge University
Press, 2009.

[32]
Farhad Shahrokhi, Ondrej Sỳkora, László A Székely, and Imrich
Book embeddings and crossing numbers.
In International Workshop on Graph-Theoretic Concepts in
Computer Science, pages 256–268. Springer, 1994.

[33]
P. Turán.
A note of welcome.
J. Graph Theory, 1:1–5, 1977.

[34]
Imrich Vrto.
Crossing numbers of graphs: A bibliography.
<http://www.ifi.savba.sk/ imrich>.

[35]
Hassler Whitney.
Congruent graphs and the connectivity of graphs.
In Hassler Whitney Collected Papers, pages 61–79. Springer,


# ZeroShotDataAug: Generating and Augmenting Training Data with ChatGPT

Solomon Ubani  Suleyman Olcay Polat  Rodney D Nielsen  {solomon.ubani,
suleymanolcay.polat<EMAIL_ADDRESS>
###### Abstract

In this paper, we investigate the use of data obtained from prompting a large
generative language model, ChatGPT, to generate synthetic training data with
the aim of augmenting data in low resource scenarios. We show that with
appropriate task-specific ChatGPT prompts, we outperform the most popular
existing approaches for such data augmentation. Furthermore, we investigate
methodologies for evaluating the similarity of the augmented data generated
from ChatGPT with the aim of validating and assessing the quality of the data
generated.

##  1 Introduction

Data augmentation is a technique to increase the size of the training data
available to machine learning models without requiring additional human
annotation of data. Increasing the size of training data, provided the
additional data is somewhat diverse, is pertinent to enable model
generalization especially in low resource tasks. The aim of this paper is to
evaluate zero-shot prompting of ChatGPT for data augmentation in the low
resource scenario.

Wei and Zou [14] proposed Easy Data Augmentation (EDA) which is a technique
based on word replacement that includes four types of operations: synonym
replacement, random insertion, random deletion, and random swap. In synonym
replacement, words with similar meanings are substituted for some of the
original words in the text. This helps to introduce variations in the text and
expand the range of vocabulary. Random insertion involves adding new words to
the text, which are not present in the original data. This helps to increase
the diversity of the text and can also help models learn to deal with out-of-
vocabulary words. In random deletion, words are randomly removed from the
text. This can help to simulate situations where some words may be missing in
the input and can help the model become more robust to noise. In random swap,
two words in the text are randomly swapped. This can help to introduce
variations in the text and improve the diversity of the training data.

Back translation [11] is a common data augmentation technique in Natural
Language Processing (NLP). It involves translating a sentence or text from one
language to another and then translating it back to the original language
using a machine translation model. Back translation can introduce variations
in the text which can help to create more diverse and representative data for
training NLP models. Researchers have also used pretrained autoencoder
transformer models like BERT [3], CBERT [15], and BART [5] to augment text
data in NLP [4] [15]. These techniques generally mask some words in the
training set and utilize the pretrained models to predict the masked word(s).
This could create more diverse data since the predicted words could vary from
the original word. The authors include the class labels during finetuning and
language modelling to aid the models in predicting the masked words in the
context of their labels. Kumar et al. [4] also utilzed an autoregressive
pretrained language model, GPT-2 [9], to augment data by prompting GPT-2 to
complete the sentence given only the first few words of the sentence and the
training data label.

Dai et al. [2] utilized few-shot prompting of ChatGPT [8] for data
augmentation to produce several variations of each sentence in the training
sample. The generated sentences are similar in meaning but have different
syntax. ChatGPT is a conversational agent that utilizes OpenAI’s GPT-3.5 [7]—a
large-scale language model trained on a vast corpus of diverse and
information-rich web data and Reinforcement Learning from Human Feedback
(RLHF). Few-shot prompting is a technique that enables a language model to
perform a new task with only a few examples of training data. Zero-shot
prompting is a technique in which a language model is provided with a task
description, rather than direct supervision or training data, to perform a
specific task. The task description is in the form of a prompt or a question
that guides the model on how to generate the desired output. In this paper, we
investigate zero-shot prompting of ChatGPT for data augmentation.

The main contributions of this paper are:

  * •

Evaluation of zero-shot prompting of ChatGPT for data augmentation on three
datasets.

  * •

Three methodologies to evaluate the similarity of the data generated from
zero-shot prompting of ChatGPT with the training and test sets with the aim of
validating and assessing the quality of the data generated.

  * •

Investigation of the marginal returns of data generated from different data
augmentation techniques.

##  2 Datasets

The datasets we use to evaluate our data augmentation methodology are popular
benchmark natural language understanding datasets that researchers have
utilized to evaluate other data augmentation techniques. We evaluate on three
text classification datasets:

  * •

SST-2 [12]: Stanford Sentiment Treebank consists of movie reviews from the
Rotten Tomatoes website, where each example in the reviews is labeled with its
sentiment polarity (positive or negative).

  * •

SNIPS [1]: The Spoken Natural Language Interaction for Personal Services
dataset consists of annotated spoken queries related to seven intents in the
domains of music, weather, and home automation.

  * •

TREC [6]: A question classification dataset sourced from the Text Retrieval
Conference. It contains six question types (whether the question is about an
abbreviation, description, entity, human, location, or numeric value).

###  2.1 Low-Resource Data Scenario

In this research work, we evaluate the impact of data augmentation in the low-
data scenario. We follow a similar approach to previous work [4] on data
augmentation by randomly subsampling only 10 examples per class on each task
for both the training and the development sets.

To improve the model’s performance on the low training data scenario, for each
task, we incorporate the synthetic data generated by either ChatGPT or the
comparison approaches. Subsequently, we assess the models’ performance on the
entire test set. To address any stochastic variation, we repeat all
experiments 15 times.

##  3 Methods

###  3.1 Baseline Methods

In this research, we compare zero-shot prompting of ChatGPT with other popular
data augmentation methods listed below (see original sources cited following
the method names for further details):

  * •

EDA [14]: We used the random word replacement techniques that include four
types of operations: synonym replacement, random insertion, random deletion,
and random swap. We set $\alpha$ (proportion of words replaced) to 0.10 since
the examples are short sentences.

  * •

BackTrans [11]: We translated the training example from one language to
another and then translated it back to the original language using a machine
translation model.111Google Translate (https://pypi.org/project/googletrans/).

  * •

CBERT [15]: First, we utilize BERT’s segment embeddings to condition the BERT
model on the class labels during finetuning.222In all baseline experiments
that require finetuning, we trained for 20 epochs using AdamW optimizer with a
learning rate of $5\times 10^{-4}$ and the cross entropy loss. We then
finetuned the model with the masked language model (MLM) objective which
randomly masks some words in the sequences and aims to predict the original
word using the context. Finally, we use the resulting model to predict and
replace masked words in the training set.

  * •

BERTexpand [4]: First, we prepended the label to each sequence in the training
data and added the labels to the model vocabulary before finetuning. We then
finetuned the model with the MLM objective. Finally, we use the resulting
model to predict and replace masked words in the training set.

  * •

BERTprepend [4]: First, we prepended the label to each sequence in the
training data without adding the labels to the model vocabulary before
finetuning. We then finetuned the model with the MLM objective. Finally, we
used the resulting model to predict and replace masked words in the training
set.

  * •

GPT2context [4]: First, we prepended the label to each sequence in the
training data before finetuning GPT-2. Next, We then finetuned the GPT-2 model
on the MLM objective. Finally, we prompted the resulting model to complete the
sentences given only the first three words of the sentence prepended by the
label in the training set.

  * •

BARTword [4]: First, we prepended the label to each sequence in the training
data without adding the labels to the model vocabulary. Next, we finetuned the
BART model on the denoising reconstruction task where 40% of words are masked
and the goal of the model is to reconstruct the original sequence. Finally, we
used the resulting model to predict and replace the masked word in each
sequence of the training set.

  * •

BARTspan [4]: First, we prepended the label to each sequence in the training
data without adding the labels to the model vocabulary. Next, we finetuned the
BART model on the denoising reconstruction task where 40% of words are masked
and the goal of the model is to reconstruct the original sequence. Finally, we
used the resulting model to predict and replace the masked spans of words in
the training set.

  * •

ChatGPTfew-shot [2]: We used few-shot prompting of ChatGPT for data
augmentation to produce several paraphrases of each sentence in the training
set.

###  3.2 Prompts for Zero-shot Data Augmentation

In this section, we list the prompts used to generate augmented examples for
each class. The prompts were generated by observing the task, class
description and five instances per class of the training data.

Dataset: SST-2

  * Class: Positive
Prompt: Generate 20 sentences that are positive reviews to a movie Class:
Negative
Prompt: Generate 20 sentences that are negative reviews to a movie

Dataset: SNIPS

  * Class: RateBook
Prompt: Generate 20 sentences in an imperative mood where a human tells a
digital assistant to rate a random book and the human provides the numerical
rating. Use random book names. Do not mention the name of the digital
assistant.
Class: AddToPlaylist
Prompt: Generate 20 sentences in an imperative mood where a human tells a
digital assistant to add music to a playlist and the human provides the music
name. Use random music and playlist names. Do not mention the name of the
digital assistant.
Class: PlayMusic
Prompt: Generate 20 sentences in an imperative mood where a human tells a
digital assistant to play a music and the human provides the music name. Use
random music and names. Do not mention the name of the digital assistant.
Class: BookRestaurant
Prompt: Generate 20 sentences in an imperative mood where a human tells a
digital assistant to book a restaurant and the human provides the restaurant
or food name. Use random restaurant and food names. Do not mention the name of
the digital assistant.
Class: GetWeather
Prompt: Generate 20 sentences in an imperative mood where a human asks a
digital assistant about the weather. Sometimes the human may provide the time
and city. Use random city names. Do not mention the name of the digital
assistant.
Class: SearchCreativeWork
Prompt: Generate 20 sentences in an imperative mood where a human asks a
digital assistant to find a specific creative work. The creative work could be
a movie, tv show, book or game. Use random movie names, tv shows names, books,
games. Sometimes the human asks for a specific creative work. Do not mention
the name of the digital assistant.
Class: SearchScreeningEvent
Prompt: Generate 20 sentences in an imperative mood where a human asks a
digital assistant to find information about a movie or screening in the
theater. Sometimes the human asks for a specific movie. Do not mention the
name of the digital assistant.

Dataset: TREC

  * Class: Abbreviation
Prompt: Generate 20 questions asking about the meaning of an abbreviation
Class: Entity
Prompt: Generate 20 questions asking about a random example of a noun or
entity. Actually use different nouns or entities in each sentence.
Class: Description
Prompt: Generate 20 sentences that are only ”what is” questions that query for
a definition.
Class: Human
Prompt: Generate 20 questions about random facts about a person or people in
history.
Class: Location
Prompt: Generate 20 sentences that are questions that ask the location of a
place in history. Use a different place for each sentence
Class: Numeric Value
Prompt: Generate 20 sentences that are questions about a numeric fact in
history

###  3.3 Evaluating the Similarity of the Generated Data from ChatGPT Versus
the Training and Test Data

Since there is a chance that ChatGPT might have been trained on the datasets
for some of our tasks, we investigate data contamination in all our datasets.
We investigate data contamination by measuring the similarity between the data
generated from ChatGPT and the datasets for each of our tasks using three
similarity metrics: Cosine(Sentence Embedding), Cosine(TF-IDF), and Percent
Word Overlap (each detail later in this section).

First, for each task, we compared each example generated by ChatGPT with all
the examples from the training set and, separately, with the testing set. For
each generated example, we selected the maximum similarity score and then
averaged the scores over the generated dataset.

The three metrics used to evaluate similarity were:

  * •

Sentence Embedding: We used the MiniLM model [13] in the sentence transformer
library [10] to obtain the embedding of each example. We calculated the cosine
similarity between the embeddings of the pair of examples.

  * •

TF-IDF: We used TF-IDF vectors to calculate the similarity between examples.
First, we removed the stop words from each example and created a corpus by
combining the training data, testing data and zero-shot ChatGPT generated
data. We used the resulting corpus as the corpus for the TF-IDF vector
similarity approach. Finally, we converted each example into a TF-IDF vector
and calculated the cosine similarity between each example.

  * •

Word Overlap: We calculated the word overlap scores between examples to obtain
their similarity. First, we removed the stop words and punctuation from all
the examples. Next, for a example pair, we counted the number of unique words
that appear in both examples and divided it by the number of unique words that
appear on the longer example of the pair. This metric gives us the percentage
of overlapping words between the two examples.

|  Sentence Embedding |  TF-IDF |  Word Overlap
---|---|---|---
ChatGPTzero-shot to SNIPStest | 0.553 | 0.239 | 0.265
SNIPStrain to SNIPStest | 0.593 | 0.362 | 0.426
ChatGPTzero-shot to TRECtest | 0.528 | 0.330 | 0.271
TRECtrain to TRECtest | 0.448 | 0.240 | 0.202
ChatGPTzero-shot to SST-2test | 0.600 | 0.293 | 0.271
SST-2train to SST-2test | 0.535 | 0.229 | 0.211
Table 1: Data augmentation similarity results of ChatGPTzero-shot versus the original training sets relative to the testing sets. |  Sentence Embedding |  TF-IDF |  Word Overlap
---|---|---|---
ChatGPTzero-shot to SNIPStrain | 0.629 | 0.341 | 0.360
ChatGPTzero-shot to TRECtrain | 0.634 | 0.435 | 0.404
ChatGPTzero-shot to SST-2train | 0.635 | 0.351 | 0.317
Table 2: Data augmentation similarity results between ChatGPTzero-shot and training sets. | Word Overlap Similarity
---|---
|  $>$ 66% | Max % | # Exs at Max
ChatGPTzero-shot to SNIPStest |  0.7 |  67 | 2
SNIPStrain to SNIPStest | 11.0 | 100 | 142
ChatGPTzero-shot to TRECtest |  5.0 | 100 | 3
TRECtrain to TRECtest |  1.3 | 100 | 14
ChatGPTzero-shot to SST-2test |  0.0 |  43 | 1
SST-2train to SST-2test |  0.2 | 100 | 4
Table 3: Three statistics for the word overlap similarity: the percentage of
examples where word overlap similarity is greater than 66%, the maximum word
overlap similarity, and the number of examples with the maximum overlap

As seen in Tables 1, 2 and 3 the results from the data similarity
investigation revealed that there is little to no data contamination from the
data generated by ChatGPT for any of our tasks. The investigation also reveals
that the data generated by ChatGPT is on average 7% more similar to the
training datasets than the testing datasets. We believe this difference stems
from the higher number of examples in the training datasets relative to
testing. Hence, since we are calculating the maximum similarity between each
example and the entire dataset, a larger dataset increases the probability
that there will be an example with a high similarity.

As seen in Table 3, for SNIPS percent word overlap, the original training data
is 16% more similar to the testing data than is the generated data. The most
similar generated examples to the testing set matched two out of three content
words (two examples); whereas, the most similar original training examples had
a 100% content word overlap with a testing example (142 examples). Together,
these statistics imply the generation did not rely on memorization by the
underlying pretrained LLM (ChatGPT) for this task.

For the TREC and SST-2 testing data, the generated training data appeared more
similar than the original training data by 7% and 6%, respectively. For TREC,
there were 3 generated examples and 14 original training examples having
complete content word overlap with testing examples. For the generated
examples, this complete overlap is associated with common very short,
questions (“Who invented the telephone?”, “What year did the Titanic sink?”,
“What is a tsunami?”). Given the small number of such questions, we don’t see
this as a worrisome problem. For SST-2, the maximum overlap with a testing
example for the generated data was only 43% (in one example); whereas, there
were four original training examples with 100% content word overlap with a
testing example.

Again, these statistics imply ChatGPT did not rely on memorization of the
testing data during its pretraining. Hence, results reported in the following
sections should be predictive of what others will achieve on new tasks that
are relatively similar in nature.

###  3.4 Model Implementation

We finetuned the pretrained BERT-base uncased model for all three text
classification tasks. The hyperparameters we used to finetune BERT were
similar to the hyperparameters used by Kumar et al. [4] for a fair comparison.
The hyperparameters were a training time of twelve epochs, batch size of 32,
the AdamW optimizer function with a learning rate of $5\times 10^{-5}$, and
the categorical cross entropy loss function. During the training the models
are saved after each epoch and the best performing model on the development
set is chosen to be run on the testing set for each model.

##  4 Results

As seen in Table 4, with zero-shot prompting of ChatGPT for data augmentation,
our model achieves an accuracy of 78.1%, 91.2%, and 75.2% for SST-2, SNIPS,
and TREC respectively. Zero-shot prompting of ChatGPT outperformed all
existing data augmentation methods on SST-2 and TREC while showing similar
performance to few-shot prompting of ChatGPT on SNIPS. Specifically, our model
surpassed the best non-ChatGPT-based model by 20%, 4%, and 8% on SST-2, SNIPS,
and TREC, respectively. It is also noteworthy that ChatGPTzero-shot had the
lowest variance for both SNIPS and TREC, and the second lowest for SST-2.

Model | SST-2 | SNIPS | TREC
---|---|---|---
No Aug | 52.9 (5.0) | 79.4 (3.2) | 48.6 (11.5)
EDA | 53.8 (4.4) | 85.8 (3.0) | 52.6 (10.5)
BackTrans. | 57.5 (5.6) | 86.5 (2.4) | 66.2 ( 8.5)
CBERT | 57.4 (6.7) | 85.8 (3.5) | 64.3 (10.9)
BERTexpand | 56.3 (6.5) | 86.1 (2.7) | 65.3 ( 6.1)
BERTprepend | 56.1 (6.3) | 86.8 (1.6) | 64.7 ( 9.6)
GPT2context | 55.4 (6.7) | 86.6 (2.7) | 54.3 (10.1)
BARTword | 58.0 (6.8) | 86.8 (2.6) | 63.7 ( 9.8)
BARTspan | 57.7 (7.1) | 87.2 (1.4) | 67.3 ( 6.1)
ChatGPTfew-shot | 69.6 (5.8) |  91.3 (1.4) | 66.7 ( 8.0)
ChatGPTzero-shot |  78.1 (5.1) | 91.2 (1.3) |  75.3 ( 4.0)
Table 4: Accuracy (and standard deviation) for each data augmentation method.
All results except for ChatGPTfew-shot and ChatGPTzero-shot were the same
results reported by Kumar et al. [4].

##  5 Evaluating the Performance Improvement with more Augmentation Examples

In this section, we investigate how performance is impacted by the number of
examples created through augmentation for all data augmentation methods. In
Figure 1, we show the performance of different data augmentation techniques on
the SST-2 dataset for $K$ augmentation examples per original training
example.333For Back Translation, we used $K$ different languages.

Figure 1: Accuracy as the number of generated examples per original training
example increases

As seen in Figure 1, ChatGPTzero-shot outperforms all other data augmentation
methods for $K\in\\{1,2,4,8,16,32\\}$. This provides further evidence on the
effectiveness of using ChatGPT for data augmentation in low resource
scenarios.

##  6 No Training Data Scenario

In this section, we investigate the performance of our model on SST-2, SNIPS
and TREC’s test dataset when we use augmented data from zero-shot prompting of
ChatGPT without any data from the original training datasets. We use the same
prompts described in section 3.2 to generate 20 instances per class. We train
the models using the same hyperparameters as in section 3.4. We repeat both
steps 15 times to account for stochasticity. Our model obtained a mean
accuracy of 0.80, 0.78, and 0.62 on SST-2, SNIPS and TREC’s designated test
sets respectively. Interestingly, with no data from the original training set,
our model outperforms all existing augmentation methods on SST-2 and within a
standard deviation of the best result on TREC. These results further highlight
the significance of zero-shot prompting of ChatGPT. Unlike other data
augmentation techniques, our method of data augmentation can be used even in
the absence of any training data.

##  7 Discussion

This research provides an easy-to-use and intuitive methodology for generating
augmented data. In our experiments, our method of augmenting training data for
these NLP tasks by zero-shot prompting ChatGPT shows great promise in the low
resource scenario, substantially outperforming all but one of the baseline
methods – few-shot ChatGPT, which only exceeded it by 0.1% on one task. It
should however be noted that, as with other data augmentation methods, zero-
shot prompting of ChatGPT for data augmentation does not necessarily improve
results where there is a large training dataset.

One of the limitations of previous data augmentation methods is that the
quality of augmented data strongly depends on the original training dataset.
The quality of data generated from zero-shot prompting of ChatGPT is not
limited by the human-annotated training data. This research also provides
evidence that data generated from zero-shot prompting of ChatGPT has slower
diminishing returns compared to many existing data augmentation techniques.
Furthermore, on SST-2, our model achieved better results using only data from
zero-shot prompting of ChatGPT than did other data augmentation approaches
that supplemented an initial human-annotated training dataset. This further
highlights the effectiveness of zero-shot prompting of ChatGPT as a data
augmentation approach.

It is important to note that the quality of augmented data generated by zero-
shot prompting of ChatGPT depends on the quality of the prompts. The prompts
in this research were human generated based on the task description and
observing a few training data instances. While there is a lot of current
research in the area of prompt engineering, there are still no task-
independent well-established best practices for how to generate effective
prompts. This research presents a methodology for evaluating the augmented
data generated from large language models. To evaluate the augmented data, we
calculated the sentence embedding similarity, TF-IDF vector similarity, and
word overlap scores of the synthetic examples compared to all the examples in
the training and test data. This revealed that there was very little data
generated with high similarity scores, making it unlikely this stemmed from
memorization of the datasets by ChatGPT during its training.

##  8 Conclusion and Future Work

This paper proposes a novel technique for generating augmented data for
machine learning tasks using zero-shot prompting of ChatGPT. The experimental
results demonstrate that the proposed method substantially outperforms all the
baseline approaches for the three tasks investigated in this research, with
the single exception of few-shot ChatGPT performing as well on one task. This
indicates our method’s potential as a promising data augmentation method in
the low resource setting.

The data augmentation approach investigated in this research relies on
manually engineering effective prompts for each task which requires some
expertise. Future researchers can explore more systematic approaches to prompt
engineering especially for tasks that cannot be adequately described within a
concise prompt of one to three sentences.

## References

  * [1] Alice Coucke, Alaa Saade, Adrien Ball, Théodore Bluche, Alexandre Caulier, David Leroy, Clément Doumouro, Thibault Gisselbrecht, Francesco Caltagirone and Thibaut Lavril  “Snips voice platform: an embedded spoken language understanding system for private-by-design voice interfaces”  In _arXiv preprint arXiv:1805.10190_ , 2018
  * [2] Haixing Dai, Zhengliang Liu, Wenxiong Liao, Xiaoke Huang, Zihao Wu, Lin Zhao, Wei Liu, Ninghao Liu, Sheng Li and Dajiang Zhu  “Chataug: Leveraging chatgpt for text data augmentation”  In _arXiv preprint arXiv:2302.13007_ , 2023
  * [3] Jacob Devlin, Ming-Wei Chang, Kenton Lee and Kristina Toutanova  “Bert: Pre-training of deep bidirectional transformers for language understanding”  In _arXiv preprint arXiv:1810.04805_ , 2018
  * [4] Varun Kumar, Ashutosh Choudhary and Eunah Cho  “Data augmentation using pre-trained transformer models”  In _arXiv preprint arXiv:2003.02245_ , 2020
  * [5] Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Ves Stoyanov and Luke Zettlemoyer  “Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension”  In _arXiv preprint arXiv:1910.13461_ , 2019
  * [6] Xin Li and Dan Roth  “Learning question classifiers”  In _COLING 2002: The 19th International Conference on Computational Linguistics_ , 2002
  * [7] OpenAI  “GPT-3.5” [Accessed: 07.04.2023]  URL: https://platform.openai.com/docs/models/gpt-3-5
  * [8] OpenAI  “Introducing ChatGPT.” [Accessed: 07.04.2023]  URL: https://openai.com/blog/chatgpt
  * [9] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei and Ilya Sutskever  “Language models are unsupervised multitask learners”  In _OpenAI blog_ 1.8, 2019, pp. 9
  * [10] SBERT.net  “SentenceTransformers Documentation” [Accessed: 07.04.2023]  URL: https://www.sbert.net/index.html
  * [11] Rico Sennrich, Barry Haddow and Alexandra Birch  “Improving neural machine translation models with monolingual data”  In _arXiv preprint arXiv:1511.06709_ , 2015
  * [12] Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng and Christopher Potts  “Recursive deep models for semantic compositionality over a sentiment treebank”  In _Proceedings of the 2013 conference on empirical methods in natural language processing_ , 2013, pp. 1631–1642
  * [13] Wenhui Wang, Furu Wei, Li Dong, Hangbo Bao, Nan Yang and Ming Zhou  “Minilm: Deep self-attention distillation for task-agnostic compression of pre-trained transformers”  In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 5776–5788
  * [14] Jason Wei and Kai Zou  “Eda: Easy data augmentation techniques for boosting performance on text classification tasks”  In _arXiv preprint arXiv:1901.11196_ , 2019
  * [15] Xing Wu, Shangwen Lv, Liangjun Zang, Jizhong Han and Songlin Hu  “Conditional bert contextual augmentation”  In _Computational Science–ICCS 2019: 19th International Conference, Faro, Portugal, June 12–14, 2019, Proceedings, Part IV 19_ , 2019, pp. 84–95  Springer