decompose $f$ (resp. $g$) to $f=f^{c}+f^{0}$ according to the spaces above,
write

$\langle Af,g\rangle=\langle Af^{c},g^{c}\rangle+\langle Af^{0},g^{0}\rangle.$

We show (A.1) separately for each term. Beginning with the left term, $\langle
Af^{c},g^{c}\rangle$, we can define
$\tilde{f}:V^{\prime}\to\mathbb{R},\tilde{g}:V^{\prime}\to\mathbb{R}$ by
$\tilde{f}(a)=f^{c}(a),\tilde{g}(a)=g^{c}(a)$ for some $u\in S_{a}$. We denote
$A_{H}$ the normalized adjacency-operator of $H$ and we have that

$\langle Af^{c},g^{c}\rangle=\langle A_{H}\tilde{f},\tilde{g}\rangle.$

The equality above is due to the definition of the weights $\nu_{f}$ of $G$,
where in particular $\nu_{f}(f^{-1}(a))=\nu_{h}(a)$. We note that
$f,g\bot{\mathbf{1}}$ and that $f^{0},g^{0}\bot{\mathbf{1}}$, hence
$f^{c},g^{c}\bot{\mathbf{1}}$, which implies that
$\tilde{f},\tilde{g}\bot{\mathbf{1}}$. Thus by $\lambda$-spectral expansion of
$H$

$\langle
A_{H}\tilde{f},\tilde{g}\rangle\leqslant\lambda\langle\tilde{f},\tilde{g}\rangle=\lambda\langle
f^{c},g^{c}\rangle.$

As for the right term, we note that

$\langle Af^{0},g^{0}\rangle=\operatorname*{\mathbb{E}}_{{ab\in
E^{\prime}}}\left[\operatorname*{\mathbb{E}}_{{xy\in
E_{ab}}}\left[f^{0}(x)g^{0}(y)\right]\right]=\operatorname*{\mathbb{E}}_{{ab\in
E^{\prime}}}\left[\langle
A_{ab}f^{0}|_{S_{a}},g^{0}|_{S_{b}}\rangle_{ab}\right].$

Here $A_{ab}$ is the normalized bipartite adjacency operator of the bipartite
graph between $S_{a},S_{b}$. For all $a,b\in V^{\prime}$ we have that
$f^{0}|_{S_{a}}\bot{\mathbf{1}}|_{S_{b}}$ (and resp. $g$). Thus from
$\eta$-bipartite expansion we have that

$\operatorname*{\mathbb{E}}_{{ab\in E^{\prime}}}\left[\langle
A_{ab}f^{0}|_{S_{a}},g^{0}|_{S_{b}}\rangle_{ab}\right]\leqslant\eta\operatorname*{\mathbb{E}}_{{ab\in
E^{\prime}}}\left[\langle
f^{0}|_{S_{a}},g^{0}|_{S_{b}}\rangle_{ab}\right]=\eta\langle
f^{0},g^{0}\rangle.$

The claim follows.

##### The one-sided case

The same proof applies with the following changes. Instead of showing (A.1),
we need to show

$\langle Af,f\rangle\leqslant\max\\{\lambda,\eta\\}.$ (A.2)

We can still orthogonally decompose

$\langle Af,f\rangle=\langle Af^{c},f^{c}\rangle+\langle Af^{0},f^{0}\rangle.$

Showing that $\langle Af^{0},f^{0}\rangle\leqslant\eta$ is the same as in the
two-sided case, since the bound uses the assumptions about the bipartite
graphs, not the expansion of $H$. Bounding $\langle
Af^{c},f^{c}\rangle\leqslant\lambda$ follows by the same argument of the two-
sided case, namely, that

$\langle Af^{c},f^{c}\rangle=\langle
A_{H}\tilde{f},\tilde{f}\rangle\leqslant\lambda\langle\tilde{f},\tilde{f}\rangle=\lambda\langle
f^{c},f^{c}\rangle.$

Here the inequality used that $1$-sided expansion of $A_{H}$.

∎

###  A.2 Proof of Proposition 3.15

######  Proposition (Restatement of Proposition 3.15).

Let $G=(V,E)$ be a $\lambda$-two-sided spectral expander over $n$ vertices for
$\lambda\leqslant 0.0001$. Let $r>1$ be so that every edge has weight between
$\frac{1}{r|E|}$ and $\frac{r}{|E|}$. Assume further that every vertex has
weight between $\frac{1}{r|V|}$ and $\frac{r}{|V|}$. Let
$p\in(0,\frac{1}{2})$. Consider the sampling of a random bipartite graph
$H=(A,B,E^{\prime})$ as follows:

  1. 1.

Sample a set $A\subseteq V$ by adding every $v\in V$ to $A$ independently with
probability $p$.

  2. 2.

Sample a set $B\subseteq V\setminus A$ by adding every $v\in V\setminus A$ to
$B$ independently with probability $\frac{p}{1-p}$.

  3. 3.

take the edges of $H$ to be $E^{\prime}=E(A,B)$.

Then $H$ is a $\frac{100}{p^{3}}\lambda$-bipartite spectral expander with
probability $\geqslant 3ne^{-0.2\lambda^{2}p^{2}r^{-2}D}$, where $D$ is the
minimal degree of a vertex in $G$.

Note that the sampling of the vertices in $H$ is sampling two _disjoint_ sets
$A,B\subseteq V$ where each vertex is sampled into one of the sets
independently with probability $p$ (and isn’t sampled into $H^{\prime}$ with
probability $1-2p$).

We also remark that this proposition is interesting when
$D=\operatorname{poly}(\log(n))$, otherwise the bound is trivial. This is
somewhat justified though. Observe that the probability that for some vertex
$v\in A$ the probability that none of its neighbours are sampled into $B$ is
$(1-p)^{D}$. So,for example, if $D$ was constant, this event would happen with
high probability when the number of vertices tends to infinity.

Recall that we denote by $\nu_{G}$ the probability measure on the graph of
$G$. Before we prove Proposition 3.15, we assert some properties that $H$ has
with high probability. These events are loosely that:

  1. 1.

$\nu_{G}(A)\approx p$.

  2. 2.

$\nu_{H|A}(v)\approx p^{-1}\nu_{G}(v)$, where $\nu_{H|A}(v)$ is the weight of
$v$ given that we sampled it in the $A$ side of $H$.

######  Claim A.1.

Let $\varepsilon>0$. Then

  1. 1.

$\operatorname*{\mathbb{P}}\left[{|\nu_{G}(A)-p|\geqslant\varepsilon
p}\right]\leqslant 2e^{p^{2}\varepsilon^{2}r^{-2}n}$ and similarly for $B$.

That is, the weight of $A$ and the weight of $B$ is approximately $p$ with
high probability.

  2. 2.

$\operatorname*{\mathbb{P}}\left[{\forall v\in A\,|\sum_{u\in
B}\nu_{G}(vu)-p\cdot\sum_{u\in V}\nu_{G}(vu)|<\varepsilon p\cdot\sum_{u\in
V}\nu_{G}(vu)}\right]\leqslant 2ne^{-\varepsilon^{2}p^{2}r^{-2}D}.$

That is, for every vertex $v$, approximately a $p$-fraction of the its edges
go to $B$ with high probability.

Here the $\operatorname*{\mathbb{P}}\left[{X}\right]$ notation is with respect
to the sampling of $H$.

We denote by $\mathcal{E}=\mathcal{E}(\varepsilon)$ the union of the two
events that appear in Claim A.1.

###### Proof of Proposition 3.15.

Let $\varepsilon=\min(\lambda^{2},0.0001)$. The event $\mathcal{E}$ occurs
with probability at most $(2n+2)e^{-\varepsilon^{2}p^{2}c^{-2}D}$. We show
that when $\mathcal{E}$ doesn’t occur, the resulting graph $H$ is a
$\frac{100}{p}\lambda$-bipartite expander. We hereby assume in all claims
below that indeed $\mathcal{E}$ doesn’t occur.

For a function $f:A\to\mathbb{R}$ or $g:B\to\mathbb{R}$ we define
$\tilde{f},\tilde{g}:V\to\mathbb{R}$ so that
$\tilde{f}|_{A}=f,\tilde{g}|_{B}=g$ and $\tilde{f}|_{V\setminus
A},\tilde{g}|_{V\setminus B}=0$.

Fix a function $f:A\to\mathbb{R}$ so that $\langle
f,{\mathbf{1}}_{A}\rangle_{H|A}=\operatorname*{\mathbb{E}}_{{v\sim\nu_{H|A}}}\left[f(v)\right]=0$.
We need to show that

$\langle A_{H}f,A_{H}f\rangle_{H|B}\leqslant\frac{100\lambda^{2}}{p^{3}}\lVert
f\rVert_{H|A}^{2}.$ (A.3)

We do the following steps:

##### Step 1

We relate $\langle A_{H}f,A_{H}f\rangle_{H|B}$ to
$\langle\widetilde{A_{H}f},\widetilde{A_{H}f}\rangle_{G}$. Namely, _we will
prove that:_

$\langle A_{H}f,A_{H}f\rangle_{H|B}\leqslant
p^{-1}(1+5\varepsilon)\langle\widetilde{A_{H}f},\widetilde{A_{H}f}\rangle_{G}.$
(A.4)

##### Step 2

We relate the inner product of $\widetilde{A_{H}f}$ (first using the bipartite
adjacency in $H$, then extending the resulting function from $B$ to all $G$),
with the inner product of $A_{G}\tilde{f}$ (first extending $f$ from $A$ to
all $G$ and then applying $G$’s adjacency operator). Namely, _we need to show
that:_

$p^{-1}(1+5\varepsilon)\langle\widetilde{A_{H}f},\widetilde{A_{H}f}\rangle_{G}\leqslant\frac{1+5\varepsilon}{p^{3}(1-\varepsilon)^{2}}\langle
A_{G}\tilde{f},A_{G}\tilde{f}\rangle_{G}.$ (A.5)

##### Step 3

We would like to use the expansion of $G$ to bound $\langle
A_{G}\tilde{f},A_{G}\tilde{f}\rangle_{G}\leqslant\lambda^{2}\langle\tilde{f},\tilde{f}\rangle_{G}$.
However, even if $f\bot{\mathbf{1}}_{A}$ it may be the case that
$\tilde{f}\not\bot{\mathbf{1}}_{G}$. However, _we will show that_ :

$\langle\tilde{f},{\mathbf{1}}_{G}\rangle^{2}\leqslant 17\varepsilon
p^{2}\langle f,f\rangle_{H|A}$ (A.6)

Plugging this in the right-hand side of (A.5) we have that

$\displaystyle\frac{1+5\varepsilon}{p^{3}(1-\varepsilon)^{2}}\langle
A_{G}\tilde{f},A_{G}\tilde{f}\rangle_{G}\leqslant$
$\displaystyle\frac{1+5\varepsilon}{p^{3}(1-\varepsilon)^{2}}\langle\tilde{f},{\mathbf{1}}_{G}\rangle_{G}^{2}+\frac{1+5\varepsilon}{p^{3}(1-\varepsilon)^{2}}\lambda^{2}\langle\tilde{f},\tilde{f}\rangle_{G}\leqslant$
(A.7)
$\displaystyle\frac{1+5\varepsilon}{p^{3}(1-\varepsilon)^{2}}17\varepsilon
p^{2}\langle
f,f\rangle_{H|A}+\frac{1+5\varepsilon}{p^{3}(1-\varepsilon)^{2}}\lambda^{2}\langle\tilde{f},\tilde{f}\rangle_{G}$

Finally _we will show that_ :

$\langle\tilde{f},\tilde{f}\rangle_{G}\leqslant\langle f,f\rangle_{H|A}$ (A.8)

Which implies that

$\displaystyle\frac{1+5\varepsilon}{p^{3}(1-\varepsilon)^{2}}17\varepsilon
p^{2}\langle
f,f\rangle_{H|A}+\frac{1+5\varepsilon}{p^{3}(1-\varepsilon)^{2}}\lambda^{2}\langle\tilde{f},\tilde{f}\rangle_{G}$
$\displaystyle\leqslant$ (A.9)
$\displaystyle\frac{(1+5\varepsilon)^{2}}{p^{3}(1-\varepsilon)^{2}}(17\lambda^{2}+16\varepsilon)\lVert
f\rVert_{H|A}^{2}.$

By our choice of $\varepsilon=\min(0.0001,\lambda^{2})$ we obtain that (A.3)
holds, i.e. $\langle
A_{H}f,A_{H}f\rangle_{H|B}\leqslant\frac{100\lambda^{2}}{p^{3}}\lVert
f\rVert_{H|A}^{2}.$

It remains to prove inequalities (A.4), (A.5), (A.6) and (A.8).

#### Proving the steps

##### Inequalities (A.4) and (A.8)

The following claim is proven after the proposition. Recall that the
expression
$\operatorname*{\mathbb{E}}_{{v\nu_{H|A}}}\left[g(v)\right]=\sum_{v\in
A}\nu_{H|A}(v)g(v)$, where $\nu_{H|A}(v)=\sum_{b\in B,v\sim b}\nu_{H}(vb)$, is
the weight of $v$ in the bipartite graph of $H$ conditioned on sampling $v\in
A$.

######  Claim A.2.

Let $g:A\to\mathbb{R}$ be a non-negative function. Then

$(1-5\varepsilon)p^{-1}\operatorname*{\mathbb{E}}_{{v\sim\nu_{G}}}\left[\tilde{f}(v)\right]\leqslant\operatorname*{\mathbb{E}}_{{v\sim\nu_{H|A}}}\left[f(v)\right]$
(A.10)

and

$\operatorname*{\mathbb{E}}_{{v\sim\nu_{H|A}}}\left[f(v)\right]\leqslant(1+5\varepsilon)p^{-1}\operatorname*{\mathbb{E}}_{{v\sim\nu_{G}}}\left[\tilde{f}(v)\right].$
(A.11)

Similar inequalities hold for non-negative $g:B\to\mathbb{R}$.

Recall that

$\langle
A_{H}f,A_{H}f\rangle_{H|B}:=\operatorname*{\mathbb{E}}_{{v\sim\nu_{H|B}}}\left[(A_{H}f(v))^{2}\right],$
$\langle\widetilde{A_{H}f},\widetilde{A_{H}f}\rangle:=\operatorname*{\mathbb{E}}_{{v\sim\nu_{G}}}\left[(\widetilde{A_{H}f(v))^{2}}\right].$

Applying (A.11) of Claim A.2 to the function
$g:B\to\mathbb{R};\;g(v)=(A_{H}f(v))^{2}$ gives

$\langle A_{H}f,A_{H}f\rangle_{H}\leqslant
p^{-1}(1+5\varepsilon)\langle\widetilde{A_{H}f},\widetilde{A_{H}f}\rangle_{G}.$

and (A.4) holds.

Similarly, applying (A.10) of Claim A.2 to $g:A\to\mathbb{R};\;g(v)=f(v)^{2}$
gives (A.8).

##### Inequality (A.5)

We bound the pointwise values of $\widetilde{A_{H}f}(v)^{2}$ by
$\frac{1}{4(1-\varepsilon)^{2}p^{2}}A_{G}\tilde{f}(v)^{2}$.

######  Claim A.3.

Let $f:A\to\mathbb{R}$. Then for every $v\in B$ it holds that

$\displaystyle\widetilde{A_{H}f}(v)^{2}\leqslant\frac{1}{(1-\varepsilon)^{2}p^{2}}(A_{G}\tilde{f}(v))^{2}.$
(A.12)

The claim is proven after the proposition. Note that (A.12) also holds for
$v\notin B$, since the values on the left-hand side of (A.12) is $0$ when
$v\notin B$, and the right-hand side is non-negative. Thus we can take
expectation on both sides of (A.12) with respect to $\nu_{G}$, and get (A.5),
that is:

$\displaystyle
p^{-1}(1+5\varepsilon)\operatorname*{\mathbb{E}}_{{v\sim\nu_{G}}}\left[\widetilde{A_{H}f(v)}\right]$
$\displaystyle=p^{-1}(1+5\varepsilon)\langle\widetilde{A_{H}f},\widetilde{A_{H}f}\rangle_{G}\leqslant$
$\displaystyle\frac{1+5\varepsilon}{p^{3}(1-\varepsilon)^{2}}\langle
A_{G}\tilde{f},A_{G}\tilde{f}\rangle_{G}=$
$\displaystyle\frac{1+5\varepsilon}{p^{3}(1-\varepsilon)^{2}}\operatorname*{\mathbb{E}}_{{v\in\nu_{G}}}\left[A_{g}\tilde{f}(v)^{2}\right].$

##### Inequality (A.6)

To show (A.6) we need the following claim on the weights $\nu_{H}(v)$.

######  Claim A.4.

For every $v\in A$

$(1-3\varepsilon)\frac{\nu_{G}(v)}{\nu_{G}(A)}\leqslant\nu_{H|A}({v})\leqslant(1+3\varepsilon)\frac{\nu_{G}(v)}{\nu_{G}(A)}.$
(A.13)

the same holds for every $u\in B$.

Let $f:A\to\mathbb{R}$ be so that $\langle f,{\mathbf{1}}_{A}\rangle_{H|A}=0$.

$\lvert\langle\tilde{f},{\mathbf{1}}_{G}\rangle_{G}\rvert=\lvert\operatorname*{\mathbb{E}}_{{v\in
V}}\left[\tilde{f}(v)\right]\rvert=\nu_{G}(A)\lvert\sum_{v\in
A}\frac{\nu_{G}(v)}{\nu_{G}(A)}f(v)\rvert\leqslant(1+\varepsilon)p\lvert\sum_{v\in
A}\frac{\nu_{G}(v)}{\nu_{G}(A)}f(v)\rvert$

By subtracting
$0=\frac{1}{2}\operatorname*{\mathbb{E}}_{{v\sim\nu_{H|A}}}\left[f(v)\right]=\sum_{v\in
A}\nu_{H}(v)f(v)$, we get:

$\leqslant(1+\varepsilon)p\lvert\sum_{v\in
A}\left(\frac{\nu_{G}(v)}{\nu_{G}(A)}-\nu_{H|A}(v)\right)f(v)\rvert$
$=(1+\varepsilon)p\lvert\sum_{v\in
A}\nu_{H|A}(v)\left(\frac{\nu_{G}(v)}{\nu_{H}(v)\nu_{G}(A)}-1\right)f(v)\rvert.$

By Claim A.4 it holds in particular that
$\left(\frac{\nu_{G}(v)}{\nu_{H|A}(v)\nu_{G}(A)}-1\right)^{2}\leqslant
16\varepsilon$ (for small enough $\varepsilon$). By Cauchy-Schwartz this is
less or equal to

$(1+\varepsilon)p\sqrt{\sum_{v\in A}\nu_{H|A}(v)16\varepsilon}\sqrt{\sum_{v\in
A}\nu_{H|A}(v)f(v)^{2}}\leqslant
4(1+\varepsilon)\varepsilon^{0.5}p\sqrt{\langle f,f\rangle_{H|A}}.$

In conclusion we have that

$\langle\tilde{f},{\mathbf{1}}_{G}\rangle_{G}^{2}\leqslant 17\varepsilon
p^{2}\langle f,f\rangle_{H|A},$

for small enough $\varepsilon$.

∎

It remains to prove the claims stated in the above proof.

###### Proof of Claim A.1.

For the first item, we note that $\nu_{G}(A)=\sum_{v\in V}{\mathbf{1}}_{v\in
A}\operatorname*{\mathbb{P}}\left[{v}\right]$. This is a sum of
$n$-independent random variables that are bounded between $0$ and
$\frac{r}{n}$. Its mean is $p$. By Hoeffding’s inequality, the event that
$|\operatorname*{\mathbb{P}}_{{v\in G}}\left[v\in
A\right]-p|\geqslant\varepsilon p$ is bounded by
$2e^{-2\varepsilon^{2}p^{2}c^{-2}n}$.

For the second item, fix $v\in A$. The sum of edge weights $\sum_{u\in
B}\nu_{G}(vu)=\sum_{u\in V}{\mathbf{1}}_{u\in B}\nu_{G}(vu)$. This is a sum of
$\geqslant D$ random variables, that are bounded between $0$ and
$\frac{r}{|E|}$. Its mean is $p\cdot\sum_{u\in V}\nu_{G}(vu)$. By Hoeffding’s
inequality

$\operatorname*{\mathbb{P}}\left[{|\sum_{u\in B}\nu_{G}(vu)-p\cdot\sum_{u\in
V}\nu_{G}(vu)|<\varepsilon p\cdot\sum_{u\in V}\nu_{G}(vu)}\right]\leqslant
2exp\left(-2\varepsilon^{2}p^{2}\left(\sum_{u\in
V}\nu_{G}(vu)\right)^{2}/\sum_{u\in V}\nu_{G}(vu)^{2}\right).$

By the assumption that $\nu_{G}(uv)\leqslant\frac{r}{|E|}$ hence the
denominator is bounded by $\frac{r}{|E|}\sum_{u\in V}\nu_{G}(vu)$ and

$(*)\leqslant exp\left(-2\varepsilon^{2}p^{2}r^{-1}|E|\left(\sum_{u\in
V}\nu_{G}(vu)\right)\right).$

As $\left(\sum_{u\in V}\nu_{G}(vu)\right)=2\nu_{G}(v)\geqslant\frac{2}{rn}$
this is

$\leqslant exp\left(-2\varepsilon^{2}p^{2}r^{-2}\frac{|E|}{n}\right).$

The degree of every vertex is at least $D$ and in particular
$\frac{|E|}{n}\geqslant D$, hence

$\operatorname*{\mathbb{P}}\left[{|\sum_{u\in B}\nu_{G}(vu)-p\cdot\sum_{u\in
V}\nu_{G}(vu)|\geqslant\varepsilon p\cdot\sum_{u\in
V}\nu_{G}(vu)}\right]\leqslant e^{-\varepsilon^{2}p^{2}r^{-2}D}.$

Finally, the second item follows from a union bound on $n$ vertices. ∎

The proof of Claim A.2 relies on Claim A.4 so we prove Claim A.4 first.

###### Proof of Claim A.4.

For the right-hand inequality in (A.13) observe that

$\nu_{H|A}(v)=\frac{\sum_{u\in B}\nu_{G}(vu)}{\sum_{v^{\prime}\in A}\sum_{u\in
B}\nu_{G}(v^{\prime}u)}.$

When $\mathcal{E}$ doesn’t occur, then $\sum_{u\in
B}\nu_{G}(vu)\leqslant(1+\varepsilon)p\sum_{u\in
V}\nu_{G}(vu)=2(1+\varepsilon)p\nu_{G}(v)$. When $\mathcal{E}$ doesn’t occur,
we can upper bound the denominator as well:

$\sum_{v^{\prime}\in A}\sum_{u\in
B}\nu_{G}(v^{\prime}u)\geqslant\sum_{v^{\prime}\in
A}p(1-\varepsilon)\sum_{u\in V}\nu_{G}(v^{\prime}u)=\sum_{v^{\prime}\in
A}2p(1-\varepsilon)\nu_{G}(v^{\prime})=2p(1-\varepsilon)\nu_{G}(A).$

Thus
$\nu_{H}({v})\leqslant\frac{2p(1+\varepsilon)}{2p(1-\varepsilon)}\frac{\nu_{G}(v)}{\nu_{G}(A)}\leqslant(1+3\varepsilon)\frac{\nu_{G}(v)}{\nu_{G}(A)}$
when $\varepsilon$ is small enough. The left-hand inequality follows
similarly. ∎

###### Proof of Claim A.2.

By Claim A.4 we get that

$\operatorname*{\mathbb{E}}_{{v\sim\nu_{H|A}}}\left[f(v)\right]=\sum_{v\in
A}\nu_{H|A}(v)f(v)\overset{\eqref{eq:probabilities-in-induced-
graph}}{\leqslant}$
$\frac{(1+3\varepsilon)}{\nu_{G}(A)}\sum_{v\in\nu_{G}}\nu_{G}(v)\tilde{f}(v)=\frac{(1+3\varepsilon)}{\nu_{G}(A)}\operatorname*{\mathbb{E}}_{{v\sim\nu_{G}}}\left[\tilde{f}(v)\right]\leqslant\frac{(1+3\varepsilon)}{p(1-\varepsilon)}\operatorname*{\mathbb{E}}_{{v\sim
G}}\left[\tilde{f}(v)\right]\leqslant\frac{(1+5\varepsilon)}{p}\operatorname*{\mathbb{E}}_{{v\in
V}}\left[\tilde{f}(v)\right]$

and (A.10) holds. The second inequality is because when $\mathcal{E}$ doesn’t
occur then $\nu_{G}(A)\geqslant p(1-\varepsilon)$. The opposite inequality
(A.11) follows similarly. ∎

###### Proof of Claim A.3.

Fix $v\in B$. We explicitly write down

$A_{G}\tilde{f}(v)=\sum_{u\in A}\frac{\nu_{G}(vu)}{2\nu_{G}(v)}f(u)$

and

$A_{H}f(v)=\sum_{u\in A}\frac{\nu_{H}(vu)}{\nu_{H|B}(v)}f(u)=\sum_{u\in
A}\frac{\nu_{G}(vu)}{\nu_{H|B}(v)\cdot K}f(u)$

where $K=\sum_{e\in E(A,B)}\nu_{G}(e^{\prime})$ is the $\nu_{G}$-weight of
edges in $H$. Thus we need to compare $\nu_{G}(v)$ and $\nu_{H|B}(v)K$. As

$K\nu_{H|B}(v)=K\sum_{u\in A}\nu_{H}(vu)=K\sum_{u\in
A}\frac{1}{K}\nu_{G}(vu)=\sum_{u\in A}\nu_{G}(vu).$

When $\mathcal{E}$ doesn’t occur it holds that

$K\nu_{H|B}(v)\geqslant(1-\varepsilon)p\sum_{u\in
V}\nu_{G}(vu)=2(1-\varepsilon)p\nu_{G}(v).$

Hence

$\left(\widetilde{A_{H}f}(v)\right)^{2}=(A_{H}f(v))^{2}=\left(\frac{1}{K\nu_{H|B}(v)}\sum_{u\in
A}\nu_{G}(uv)f(u)\right)^{2}\leqslant$
$\left(\frac{1}{(1-\varepsilon)p}\right)^{2}\left(\frac{1}{2\nu_{G}(v)}\sum_{u\in
A}\nu_{G}(uv)f(u)\right)^{2}=\frac{1}{(1-\varepsilon)^{2}p^{2}}A_{G}\tilde{f}(v).$

∎

###  A.3 sparsifying a dense expander

Let $H=(V,E)$ be any graph and let $p\in(0,1)$. We define a random
sparsification $H^{\prime}=(V,E^{\prime})$ by independently inserting every
edge to $E^{\prime}$ with probability $p$.

We show that if $H$ is an expander where every vertex has degree
$\Omega(logn)$ and the measure is “almost” uniform, then with high probability
the graph $H^{\prime}$ will also be an expander, albeit with worse parameters.

######  Lemma (Restatement of Lemma 3.16).

Let $p\in(0,1)$. Let $H=(A,B,E)$ be an $n$-vertex bipartite graph so that
every edge has weight between $\frac{1}{r|E|}$ and $\frac{r}{|E|}$ for some
$r>1$. Let $0<\varepsilon<0.05$ and
$0<\lambda<(1-0.25\varepsilon)\varepsilon^{3}p^{3}$. Denote by
$\mu=0.5r^{-2}\varepsilon^{3/2}p^{3/2}(1-0.25\varepsilon)((1-0.25\varepsilon)\varepsilon^{3}p^{3}-\lambda)$.
Let $D\in\mathbb{N}$ so that $\mu D>2\log n+5$.

Assume that $\min_{v\in A\cup B}deg(v)\geqslant D$ and that $H$ is a
$\lambda$-spectral expander. Let $H^{\prime}=(A,B,E^{\prime})$ be a random
subgraph where every edge is sampled in $H^{\prime}$ with probability $p$.

Then with probability at least $1-5n^{2}e^{-\mu D}$, $H^{\prime}$ is a
$260\varepsilon(1+\ln(3/\varepsilon))$-spectral expander.

###### Proof of Lemma 3.16.

Our Lemma shall follow from this claim:

######  Claim A.5.

With probability at least $1-5n^{2}e^{-\mu D}$ over the choice of
$H^{\prime}$, for every $S\subseteq A,T\subseteq B$ the following inequality
holds:

$\left|\operatorname*{\mathbb{P}}\left[{S}\right]\operatorname*{\mathbb{P}}\left[{T}\right]-\operatorname*{\mathbb{P}}\left[{E_{H^{\prime}}(S,T)}\right]\right|\leqslant\varepsilon\sqrt{\operatorname*{\mathbb{P}}\left[{S}\right]\operatorname*{\mathbb{P}}\left[{T}\right]},$
(A.14)

where all probabilities in (A.14) are with respect to the edge weights of
$H^{\prime}$.

Claim A.5 implies Lemma 3.16 via the inverse expander mixing lemma by [BL06].

######  Theorem (Restatement of Theorem 2.8).

Let $A$ be a normalized adjacency-operator of a bipartite graph
$H^{\prime}=(A,B,E^{\prime})$. Assume that for all $S\subseteq A,T\subseteq B$
it holds that

$\lvert\nu(E(S,T))-\nu(S)\nu(T)\rvert\leqslant\alpha\sqrt{\nu(S)\nu(T)}.$

Then $\lambda(A)\leqslant 260\alpha(1+\log_{2}(3/\alpha)).$

∎

We continue to prove Claim A.5. To do so, we introduce notation that differs
between the different probability spaces we refer to. For any graph
$G=(V(G),E(G))$ (be it either $H$ or one of the random $H^{\prime}$) and a set
$X\subseteq E(G)$ we denote its edge weights by $\nu_{G}(X)=\sum_{e\in
X}\nu_{G}(e)$. Likewise, for $X\subseteq V(G)$ we denote by
$\nu(X)_{G}=\frac{1}{2}\sum_{v\in X}\sum_{u\in G}\nu_{G}(vu)$, the weight of
$X$ induced by the edge weights.

The notation $\operatorname*{\mathbb{P}}\left[{A}\right]$ denotes the
probability that an event $A$ occurs with respect to the random choice of
$H^{\prime}$. With this notation, (A.14) translates to

$\left|\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)-\nu_{H^{\prime}}(E_{H^{\prime}}(S,T))\right|\leqslant\varepsilon\sqrt{\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)}.$
(A.15)

###### Proof of Claim A.5.

For $S\subseteq A,T\subseteq B$, denote by $B_{S,T}$ the event where (A.15)
doesn’t hold for the pair $S,T$, and denote by $B=\bigcup_{S\subseteq
A,T\subseteq B}B_{S,T}$. We need to show that
$\operatorname*{\mathbb{P}}\left[{B}\right]\leqslant 5n^{2}e^{-\mu D}$.

Denote by $R$ the “bad” event where

  1. 1.

Either $\nu_{H}(E)<(1-0.25\varepsilon)p$ or

  2. 2.

There exists some set $S\subseteq A\cup B$ so that one of the the following
inequalities hold:

$\displaystyle\nu_{H^{\prime}}(S)\leqslant(1+0.25\varepsilon)\nu_{H}(S)\text{
or }\nu_{H}(S)\leqslant(1+0.25\varepsilon)\nu_{H^{\prime}}(S).$ (A.16)

By a union bound it holds that

$\operatorname*{\mathbb{P}}\left[{B}\right]\leqslant\operatorname*{\mathbb{P}}\left[{R}\right]+\sum_{S,T}\operatorname*{\mathbb{P}}\left[{B_{S,T}\;\hbox{and}\;\neg
R}\right].$

This claim bounds $\operatorname*{\mathbb{P}}\left[{R}\right]$.

######  Claim A.6.

$R$ occurs with probability at-most $(2n+1)e^{-0.01\varepsilon p^{3}r^{-2}D}$.

These claims bounds the probability of
$\operatorname*{\mathbb{P}}\left[{B_{S,T}\;\hbox{and}\;\neg R}\right]$.

######  Claim A.7.

Let $S\subseteq A,T\subseteq B$ so that
$min(\nu_{H^{\prime}}(S),\nu_{H^{\prime}}(T))\leqslant\varepsilon^{3}p^{3}$.
Then $\operatorname*{\mathbb{P}}\left[{B_{S,T}\;\hbox{and}\;\neg R}\right]=0.$

######  Claim A.8.

Let $S\subseteq A,T\subseteq B$ so that
$\nu_{H^{\prime}}(S),\nu_{H^{\prime}}(T)\geqslant\varepsilon^{3}p^{3}$. Then
$\operatorname*{\mathbb{P}}\left[{B_{S,T}\;\hbox{and}\;\neg R}\right]\leqslant
e^{-\mu D(|S|+|T|)}$101010recall that
$\mu=0.5r^{-2}\varepsilon^{3/2}p^{3/2}(1-0.25\varepsilon)((1-0.25\varepsilon)\varepsilon^{3}p^{3}-\lambda)$..

We combine the above for our bound.

$\operatorname*{\mathbb{P}}\left[{B}\right]\leqslant\operatorname*{\mathbb{P}}\left[{R}\right]+\sum_{S,T}\operatorname*{\mathbb{P}}\left[{B_{S,T}\;\hbox{and}\;\neg
R}\right]\leqslant$ $(2n+1)e^{-0.01\varepsilon
p^{3}r^{-2}D}+\sum_{S,T:\;\nu_{H^{\prime}}(S),\nu_{H^{\prime}}(T)\geqslant\varepsilon^{2}p}e^{-\mu
D(|S|+|T|)}\leqslant$ $(2n+1)e^{-0.01\varepsilon
p^{3}r^{-2}D}+\left(\sum_{j=1}^{n}\binom{n}{j}e^{-\mu Dj}\right)^{2}\leqslant$

By using the crude estimate $\binom{n}{j}\leqslant n^{j}=e^{j\log n}$ we have

$(2n+1)e^{-0.01\varepsilon p^{3}r^{-2}D}+\left(\sum_{j=1}^{n}e^{j\log n-\mu
Dj}\right)^{2}\leqslant$ $(2n+1)e^{-0.01\varepsilon
p^{3}r^{-2}D}+\frac{e^{2(\log n-\mu D)}}{(1-e^{\log n-\mu D})^{2}}\leqslant
5n^{2}e^{-\mu D}$

as required. Note that in the last inequality we used the fact that when $\mu
D>2\log n+5$ to bound the denominator by a constant close to $1$ (say $0.99$).
∎

It remains to prove Claim A.6, Claim A.7 and Claim A.8. To do so, we show that
the probabilities of of sets in a typical $H^{\prime}$ are similar those of
$H$.

######  Claim A.9.

Let $\eta>0$. For every set of edges $F\subseteq E$, denote the number of
remaining edges $H^{\prime}$ by $F^{\prime}=E^{\prime}\cap F$.

$\operatorname*{\mathbb{P}}_{{H^{\prime}}}\left[\lvert\nu_{H}(F^{\prime})-p\nu_{H}(F)\rvert\geqslant\eta
p\nu_{H}(F)\right]<2e^{-2p^{2}\eta^{2}r^{-2}|F|}.$ (A.17)

Furthermore, with probability at least $1-4e^{-0.07p\eta^{2}r^{-2}|F|}$ it
holds that

$(1-\eta)\nu_{H}(F)\leqslant\nu_{H^{\prime}}(F)\leqslant(1+\eta)\nu_{H}(F).$
(A.18)

###### Proof sketch of Claim A.9.

The proof of the first item is similar to the proof For the first item in
Claim A.1 and is omitted.

As for the second item, note that
$\nu_{H^{\prime}}(F^{\prime})=\frac{\nu_{H}(F^{\prime})}{\nu_{H}(E^{\prime})}$.
Thus when (A.17) is true for the entire edge set of $H^{\prime}$ and for $F$
with $\eta^{\prime}=\frac{\eta}{4}$, then (A.18) follows for $\eta$. The exact
calculations are omitted. ∎

###### Proof of Claim A.6.

By Claim A.9

$\operatorname*{\mathbb{P}}\left[{|E^{\prime}|<(1-\varepsilon)p|E|}\right]\leqslant
e^{-0.3p\varepsilon^{2}r^{-2}|E|}.$

Thus the first item in $R$’s description doesn’t occur except with probability
$e^{-0.3p\varepsilon^{2}r^{-2}|E|}.$ We bound the probability that the second
item occurs. The probability of a vertex $v\in V$ is half the probability of
$F=\left\\{e\in E\left|\;\vphantom{e\in Ev\in e}\right.v\in e\right\\}$. By
assumption, $|F|\geqslant D$. Thus for any $v\in V$, by Claim A.9, (A.16)
holds for $S=\\{v\\}$ with probability $\geqslant
1-2e^{-0.3p\varepsilon^{2}D}$. By a union bound (A.16) holds for all
$S=\\{v\\}\subseteq V$ simultaneously with probability
$1-2ne^{-0.01\varepsilon p^{-3}r^{-2}D}$. When this is true, then (A.16) holds
for all $S\subseteq V$ since $\nu_{H^{\prime}}(S)=\sum_{v\in
S}\nu(\\{v\\})_{H^{\prime}}$.

A union bound over the first item and the second item (for all singletons)
completes the proof. ∎

###### Proof of Claim A.7.

Fix $S\subseteq A,T\subseteq B$ so that
$\min(\nu_{H^{\prime}}(S),\nu_{H^{\prime}}(T))\leqslant\varepsilon^{3}p^{3}$.
If

$|\nu_{H^{\prime}}(E_{H^{\prime}}(S,T))-\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)|=\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)-\nu_{H^{\prime}}(E(S,T))$

then
$\sqrt{\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)}\leqslant\varepsilon^{1.5}p^{1.5}\leqslant\varepsilon$,
it holds that

$\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)-\nu_{H^{\prime}}(E(S,T))\leqslant\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)\leqslant\varepsilon\sqrt{\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)}.$

Thus assume that

$\displaystyle|\nu_{H^{\prime}}(E_{H^{\prime}}(S,T))-\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)|=\nu_{H^{\prime}}(E_{H^{\prime}}(S,T))-\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)\leqslant\nu_{H^{\prime}}(E_{H^{\prime}}(S,T)).$
(A.19)

The event $\neg R$ implies that
$\nu_{H}(E^{\prime})\geqslant(1-0.25\varepsilon)p$. Thus

$\nu_{H^{\prime}}(E_{H^{\prime}}(S,T))=\frac{\nu_{H}(E_{H^{\prime}}(S,T))}{\nu_{H}(E^{\prime})}\leqslant\frac{\nu_{H}(E_{H^{\prime}}(S,T))}{(1-0.25\varepsilon)p}\leqslant\frac{(1+\varepsilon)\nu_{H}(E_{H}(S,T))}{p}.$

This upper bound is tight when _all_ edges of $E_{H}(S,T)$ are sampled into
$H^{\prime}$. The original graph $H$ is a $\lambda$-spectral expander, so by
the expander mixing lemma $\nu_{H}(E_{H}(S,T))$ is also small:

$\displaystyle\nu_{H}(E_{H}(S,T))\leqslant\nu_{H}(S)\nu_{H}(T)+\lambda\sqrt{\nu_{H}(S)\nu_{H}(T)}.$
(A.20)

When $\neg R$ occurs, then
$\nu_{H}(S)\leqslant(1+\varepsilon)\nu_{H^{\prime}}(S)$ and
$\nu_{H}(T)\leqslant(1+\varepsilon)\nu_{H^{\prime}}(T)$. So we can upper bound
(A.20) by

$(1+\varepsilon)^{2}\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)+\lambda(1+\varepsilon)\sqrt{\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)}\leqslant(\varepsilon^{1.5}p^{1.5}+\lambda)(1+\varepsilon)^{2}\sqrt{\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)}.$

The inequality is by the fact that
$\nu_{H^{\prime}}(S)\cdot\nu_{H^{\prime}}(T)\leqslant\varepsilon^{2}p$.
Plugging this in (A.19) we get

$|\nu_{H^{\prime}}(E(S,T))-\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)|\leqslant\nu_{H^{\prime}}((E_{H^{\prime}}(S,T))\leqslant$
$(1+\varepsilon)^{3}(\lambda
p^{-1}+\varepsilon^{1.5}p^{0.5})\sqrt{\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)}\leqslant\varepsilon\sqrt{\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)},$

since by the assumptions on $\lambda$, $(1+\varepsilon)^{3}(\lambda
p^{-1}+\varepsilon^{1.5}p^{0.5})\leqslant\varepsilon$. ∎

###### Proof of Claim A.8.

Fix $S\subseteq A,T\subseteq B$ so that
$\nu_{H^{\prime}}(S),\nu_{H^{\prime}}(T)\geqslant\varepsilon^{3}p^{3}$. We
will prove below that

$\displaystyle|E_{H}(S,T)|\geqslant\mu D(|S|+|T|)$ (A.21)

for $\mu$ in the Theorem statement
$\mu:=0.5r^{-2}\varepsilon^{3/2}p^{3/2}(1-0.25\varepsilon)((1-0.25\varepsilon)\varepsilon^{3}p^{3}-\lambda)$.
For now let us assume (A.21). Claim A.9 implies that the event that

$|\nu_{H^{\prime}}(E_{H^{\prime}}(S,T))-\nu_{H}(E_{H}(S,T))|\leqslant
0.25\varepsilon\nu_{H}(E_{H}(S,T)),$ (A.22)

occurs with probability $\geqslant
1-2e^{-0.3p\varepsilon^{2}r^{-2}|E_{H}(S,T)|}$. By (A.21) this is $\geqslant
1-2e^{-0.3p\varepsilon^{2}r^{-2}\mu D(|S|+|T|)}$.

When (A.22) occurs, then

$\displaystyle|\nu_{H^{\prime}}(E_{H^{\prime}}(S,T))-\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)|\leqslant$
(A.23)
$\displaystyle|\nu_{H^{\prime}}(E_{H^{\prime}}(S,T))-\nu_{H}(E_{H}(S,T))|+$
(A.24) $\displaystyle|\nu_{H}(E_{H}(S,T))-\nu_{H}(S)\nu_{H}(T)|+$ (A.25)
$\displaystyle|\nu_{H}(S)\nu_{H}(T)-\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)|$
(A.26)

Before bounding the terms (A.24), (A.25), (A.26), we say informally that
(A.25) is bounded by the expander mixing lemma in $H$, and (A.24), (A.26) are
bounded by the fact that when $\neg R$ occurs, the probabilities of verticies
and edge sets between verticies are similar in $H,H^{\prime}$.

  1. 1.

By (A.22), (A.24) is bounded by $0.25\varepsilon\nu_{H}(E_{H}(S,T))$. As
$\nu_{H}(E_{H}(S,T))$ is bounded both by $\nu_{H}(S)$ and $\nu_{H}(T)$, it is
also bounded by their geometric mean. When $\neg R$ occurs, this implies that
(A.24) is bounded by

$0.25\varepsilon\sqrt{\nu_{H}(S)\nu_{H}(T)}\leqslant
0.25\varepsilon(1+0.25\varepsilon)\sqrt{\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)}\leqslant
0.4\varepsilon\sqrt{\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)}.$

  2. 2.

By the Expander Mixing Lemma in $H$, (A.25) is upper bounded by
$\lambda\sqrt{\nu_{H}(S)\nu_{H}(T)}$. When $\neg R$ occurs, this is further
bounded by
$\lambda(1+0.25\varepsilon)\sqrt{\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)}$. By
our assumption on $\lambda$, this is $\leqslant
0.09\varepsilon\sqrt{\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)}$.

  3. 3.

When $\neg R$ occurs, then (A.26) is bounded by
$((1+0.25\varepsilon)^{2}-1)\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)$. This is
further bounded by
$0.51\varepsilon\sqrt{\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)}$.

In conclusion, we showed that with probability
$1-2e^{-0.3p\varepsilon^{2}r^{-2}\mu D(|S|+|T|)}$,

$|\nu_{H^{\prime}}(E_{H^{\prime}}(S,T))-\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)|\leqslant\varepsilon\sqrt{\nu_{H^{\prime}}(S)\nu_{H^{\prime}}(T)}$

as required.

It remains to show (A.21). By the expander mixing lemma for $H$

$\nu_{H}(E_{H}(S,T))\geqslant\nu_{H}(S)\nu_{H}(T)-\lambda\sqrt{\nu_{H}(S)\nu_{H}(T)}\geqslant$
$\sqrt{\nu_{H}(S)\nu_{H}(T)}(\sqrt{\nu_{H}(S)\nu_{H}(T)}-\lambda)\geqslant$
$\sqrt{\nu_{H}(S)\nu_{H}(T)}((1-0.25\varepsilon)\varepsilon^{3}p^{3}-\lambda).$
(A.27)

The last inequality is due to the following: when $\neg R$ occurs and
$\nu_{H^{\prime}}(S),\nu_{H^{\prime}}(T)\geqslant\varepsilon^{3}p^{3}$ then
$\nu_{H}(S),\nu_{H}(T)\geqslant(1-0.25\varepsilon)\varepsilon^{3}p^{3}$. Thus
we replace their geometric mean by $(1-0.25\varepsilon)\varepsilon^{3}p^{3}$.

As

$\sqrt{\nu_{H}(S)\nu_{H}(T)}\geqslant\sqrt{(1-0.25\varepsilon)\varepsilon^{3}p^{3}\nu_{H}(T)}\geqslant(1-0.25\varepsilon)\varepsilon^{3/2}p^{3/2}\nu_{H}(T)$

and

$\sqrt{\nu_{H}(S)\nu_{H}(T)}\geqslant\sqrt{(1-0.25\varepsilon)\varepsilon^{3}p^{3}\nu_{H}(S)}\geqslant(1-0.25\varepsilon)\varepsilon^{3/2}p^{3/2}\nu_{H}(S)$

then by taking average, we have that

$\sqrt{\nu_{H}(S)\nu_{H}(T)}\geqslant
0.5(1-0.25\varepsilon)\varepsilon^{3/2}p^{3/2}(\nu_{H}(S)+\nu_{H}(T)).$

Plugging this in (A.27) we have that

$\nu_{H}(E_{H}(S,T))\geqslant
0.5\varepsilon^{3/2}p^{3/2}(1-0.25\varepsilon)((1-0.25\varepsilon)\varepsilon^{3}p^{3}-\lambda)(\nu_{H}(S)+\nu_{H}(T)).$

Every edge in $H$ has weight at most $\frac{r}{|E|}$, we have that
$|E_{H}(S,T)|\cdot\frac{r}{|E|}\geqslant\nu_{H}(E_{H}(S,T))$. Furthermore,
since every edge in $H$ has weight at least $\frac{1}{r|E|}$, then
$\nu_{H}(S)\geqslant\frac{D}{r|E|}|S|$ (and the same for $T$). Thus concludes
that

$|E(S,T)|\geqslant\mu D(|S|+|T|).$

Where
$\mu=0.5r^{-2}\varepsilon^{3/2}p^{3/2}(1-0.25\varepsilon)((1-0.25\varepsilon)\varepsilon^{3}p^{3}-\lambda)$.

∎

##  Appendix B Bilu-Linial’s Converse Expander Mixing Lemma

In this appendix we give a variation of the converse expander mixing lemma
given in [BL06], that suits our purposes in Section A.

######  Theorem B.1 ([BL06], Lemma 3.3).

Let $X$ be a finite set and $\mu:X\to[0,1]$ be a probability distribution on
$X$. Let $V=L_{2}(X,\mu)$ be its inner product space. Let $A:V\to V$ be a self
adjoint operator that satisfies:

  1. 1.

Non-laziness: for every $x\in X$, $\langle
A{\mathbf{1}}_{x},{\mathbf{1}}_{x}\rangle=0$.

  2. 2.

For every $u\in\\{-1,0,1\\}^{X}$, and
$v_{1},v_{2},...,v_{m}\subseteq\\{-1,0,1\\}^{X}$ whose supports are pairwise
disjoint, it holds that

$\sum_{j=1}^{m}\lvert\langle u,Av_{j}\rangle\rvert\leqslant d\langle
u,u\rangle.$

  3. 3.

For every $S,T\subseteq X$ with disjoint support,

$\langle
A{\mathbf{1}}_{S},{\mathbf{1}}_{T}\rangle\leqslant\alpha\lVert{\mathbf{1}}_{S}\rVert\lVert{\mathbf{1}}_{T}\rVert.$

Then $\lVert A\rVert\leqslant 130(\alpha+\alpha\log_{2}(d/\alpha))$.

This version of Lemma 3.3 in [BL06], deals with self-adjoint operators rather
than real symmetric matrices which were in the original version.

######  Corollary (Restatement of Theorem 2.8).

Let $A$ be a normalized adjacency-operator of a bipartite graph
$H^{\prime}=(A,B,E^{\prime})$. Assume that for all $S\subseteq A,T\subseteq B$
it holds that

$\lvert\nu(E(S,T))-\nu(S)\nu(T)\rvert\leqslant\alpha\sqrt{\nu(S)\nu(T)}.$

Then $\lambda(A)\leqslant 260\alpha(1+\log_{2}(3/\alpha)).$

.

###### Proof of Theorem 2.8.

Let $J:L_{2}(H^{\prime})\to L_{2}(H^{\prime})$ be the operator of the complete
(weighted) bipartite graph

$J(f)(v)=\begin{cases}\operatorname*{\mathbb{E}}_{{u\in
X}}\left[f(u)\right]&v\in Y\\\ \operatorname*{\mathbb{E}}_{{u\in
Y}}\left[f(u)\right]&v\in X\end{cases}.$

Let $B=A-J$ and let $v_{0}={\mathbf{1}}_{X\cup Y}$,
$v_{n}={\mathbf{1}}_{X}-{\mathbf{1}}_{Y}$ the trivial eigenvectors of $A$. One
can verify that $Bv_{0}=Bv_{n}=0$. Furthermore, for every vector $v$
orthogonal to $v_{0},v_{n}$, $Bv=Av$. Thus, $\lambda(A)=\lambda(B)=||B||$.

We note that $B$ is self adjoint, and for every $u\in A\cup B$, $\langle
B{\mathbf{1}}_{u},{\mathbf{1}}_{u}\rangle=0$. Moreover, for every
$u\in\\{0,1\\}^{A\cup B}$ and pairwise disjoint $v_{j}\in\\{0,1\\}^{A\cup B}$
we have that

$\sum_{j}\lvert\langle Bu,v_{j}\rangle\rvert\leqslant\sum_{j}\lvert\langle
Au,v_{j}\rangle\rvert+\lvert\langle Ju,v_{j}\rangle\rvert\leqslant
2\sum_{j}\langle u,v_{j}\rangle=2\lVert u\rVert^{2}.$

In order to use Theorem B.1, we bound $\lvert\langle
B{\mathbf{1}}_{S},{\mathbf{1}}_{T}\rangle\rvert$ for every $S,T\subseteq A\cup
B$ that are disjoint. Indeed, let $S=S_{1}\cup S_{2},T=T_{1}\cup T_{2}$ so
that $S_{1},T_{1}\subseteq A,S_{2},T_{2}\subseteq B$. Then

$\lvert\langle B{\mathbf{1}}_{S},{\mathbf{1}}_{T}\rangle\rvert=\lvert\langle
B{\mathbf{1}}_{S_{1}},{\mathbf{1}}_{T_{2}}\rangle+\langle
B{\mathbf{1}}_{S_{2}},{\mathbf{1}}_{T_{1}}\rangle\rvert\leqslant$
$\lvert\langle
B{\mathbf{1}}_{S_{1}},{\mathbf{1}}_{T_{2}}\rangle\rvert+\lvert\langle
B{\mathbf{1}}_{S_{2}},{\mathbf{1}}_{T_{1}}\rangle\rvert.$

Note that $\langle
B{\mathbf{1}}_{S_{1}},{\mathbf{1}}_{T_{2}}\rangle=\operatorname*{\mathbb{P}}\left[{E(S_{i},T_{j})}\right]-\operatorname*{\mathbb{P}}\left[{S_{i}}\right]\operatorname*{\mathbb{P}}\left[{T_{j}}\right]$
hence we get the bound

$\lvert\langle
B{\mathbf{1}}_{S},{\mathbf{1}}_{T}\rangle\rvert\leqslant\alpha\sqrt{\operatorname*{\mathbb{P}}\left[{S_{1}}\right]\operatorname*{\mathbb{P}}\left[{T_{2}}\right]}+\sqrt{\operatorname*{\mathbb{P}}\left[{S_{2}}\right]\operatorname*{\mathbb{P}}\left[{T_{1}}\right]}\leqslant
2\alpha\sqrt{\operatorname*{\mathbb{P}}\left[{S}\right]\operatorname*{\mathbb{P}}\left[{T}\right]}=$
$2\alpha\lVert{\mathbf{1}}_{S}\rVert\lVert{\mathbf{1}}_{T}\rVert.$

Hence, by Theorem B.1, we have that

$\lambda(A)=||B||\leqslant 260\alpha(1+\log_{2}(2/\alpha)).$

∎

###  B.1 Proof of Theorem B.1

The proof of Theorem B.1 is the same as the proof of the original version in
[BL06]. The only change is that instead of taking matrix multiplication we
take inner product. We give it here in full just to stay self contained.

###### Proof of Theorem B.1.

The operator $A$ is self adjoint, our goal is to show that

$max_{0\neq v\in L_{2}(X,\mu)}\frac{\langle\pm Av,v\rangle}{\langle
v,v\rangle}\leqslant 130(\alpha+\alpha\log_{2}(d/\alpha)).$ (B.1)

As $A$ and $-A$ both uphold the assumptions of the Theorem, we focus on the
inequality with $A$. We begin by asserting that the third item’s inequality
also holds when the support is not disjoint, and when instead of vectors in
$\\{0,1\\}^{X}$ we take vectors in $\\{-1,0,1\\}^{X}$.

######  Claim B.2.

Let $v,u\in\\{-1,0,1\\}^{X}$. Then

$\langle Av,u\rangle\leqslant 64\alpha\lVert v\rVert\lVert u\rVert.$

Next we show that we can approximate the maximum in (B.1) by taking a maximum
only on $v$’s whose values are either $0$ or $\pm 2^{-i}$’s.

######  Claim B.3.

Let $v\in L_{2}(X,\mu)$. There exists some $w\in L_{2}(X,\mu)$ so that

  1. 1.

$\frac{\langle Av,v\rangle}{\langle v,v\rangle}\leqslant 2\frac{\langle
Aw,w\rangle}{\langle w,w\rangle}$.

  2. 2.

For all $x\in X$, $w(x)=sign(v(x))2^{-i}$ for some negative integer $i<0$.

By Claim B.3, we need to show that for every $w\in L_{2}(X,\mu)$ that takes
values that are negative powers on $2$,

$\frac{\langle Aw,w\rangle}{\langle w,w\rangle}\leqslant
64(\alpha+\alpha(\log_{2}(d/\alpha)).$

Indeed, we partition the support of $w=\sum_{i>0}2^{-i}w_{i}$ where $w_{i}=\pm
1$ and the support of the $w_{i}$’s are pairwise disjoint.

By Claim B.2 we have that

$\langle w_{i},Aw_{j}\rangle\leqslant 64\alpha\lVert w_{i}\rVert\lVert
w_{j}\rVert$ (B.2)

and by the second assumption in the theorem we have that

$\sum_{j}\lvert\langle w_{i},Aw_{j}\rangle\rvert\leqslant d\langle
w_{i},w_{i}\rangle$ (B.3)

Furthermore, we have that

$\frac{\langle Aw,w\rangle}{\langle
w,w\rangle}\leqslant\frac{\sum_{i,j}2^{-i-j}\lvert\langle
w_{i},w_{j}\rangle\rvert}{\sum_{i}2^{-2i}\langle w_{i},w_{i}\rangle}.$ (B.4)

Denote by $\gamma=\log(d/\alpha)$, $q_{i}=2^{-2i}\langle w_{i},w_{i}\rangle$
and $Q=\sum_{i}q_{i}$. Add up inequalities (B.2) and (B.3) as follows. For
$i=j$ we multiply (B.2) by $2^{-2i}$. when $i<j\leqslant i+\gamma$ multiply it
by $2^{-(i+j)+1}$. Multiply (B.3) by $2^{-(2i+\gamma)}$. We get that:

$\sum_{i}2^{-2i}\lvert\langle
w_{i},Aw_{i}\rangle\rvert+\sum_{i}\sum_{i<j\leqslant
i+\gamma}2^{-(i+j)+1}\lvert\langle
w_{i},Aw_{j}\rangle\rvert+\sum_{i}2^{-2i+\gamma}\sum_{j}\lvert\langle
w_{i},Aw_{j}\rangle\rvert\leqslant$ (B.5)
$64\alpha\sum_{i}q_{i}+64\alpha\sum_{i}\sum_{i<j\leqslant
i+\gamma}2\sqrt{q_{i}q_{j}}+\alpha\sum_{i}q_{i}\leqslant$ $67\alpha
Q+64\alpha\sum_{i}\sum_{i<j\leqslant i+\gamma}q_{i}+q_{j}.$

Every member $q_{j}$ appears in $\sum_{i}\sum_{i<j\leqslant
i+\gamma}q_{i}+q_{j}$ at most $\lceil\gamma\rceil+1\leqslant\gamma+2$ times,
this is at most

$130\alpha+\alpha\log_{2}(d/\alpha)Q.$

As $Q$ is the denominator in (B.4), it is enough to show that the numerator in
(B.4) is at most (B.5). Indeed, we compare the coefficients of $\lvert\langle
w_{i},Aw_{j}\rangle\rvert$ in both expressions (as $A$ is self adjoint, it is
enough to consider $i\leqslant j$.

  * –

For $i=j$ the coefficient in (B.5) is $2^{-2i}$ and $2^{-2i}+2^{-(2i+\gamma)}$
in (B.4).

  * –

For $i<j\leqslant i+\gamma$ the coefficient in (B.5) is $2^{-(i+j)+1}$ and
$2^{-(i+j)+1}+2^{-(2i+\gamma)}+2^{-(2j+\gamma)}$ in (B.4).

  * –

For $i+\gamma<j$ the coefficient in (B.5) is $2^{-(i+j)+1}$. In (B.4) it is
$2^{-(2i+\gamma)}+2^{-(2j+\gamma)}\geqslant 2^{-(2i+\gamma)}\geqslant
2^{-(i+j)+1}$.

The claim follows.

∎

###  B.2 Proof of various claims

###### Proof of Claim B.2.

We first show that for every $u\in\\{0,1\\}^{X}$, $\langle
Au,u\rangle\leqslant 2\alpha\langle u,u\rangle$. Indeed, Let $S=supp(u)$ be of
size $n$. We have that

$\lvert\sum_{T\subseteq S}\langle A{\mathbf{1}}_{T},{\mathbf{1}}_{S\setminus
T}\rangle\rvert=2^{n-2}\lvert\sum_{x,y\in S,x\neq y}\langle
A{\mathbf{1}}_{x},{\mathbf{1}}_{y}\rangle\rvert=$ $2^{n-2}\lvert\langle
Au,u\rangle\rvert.$ (B.6)

The last inequality uses the assumption that $\langle
A{\mathbf{1}}_{x},{\mathbf{1}}_{x}\rangle=0$. On the other hand,

$\lvert\sum_{T\subseteq S}\langle A{\mathbf{1}}_{T},{\mathbf{1}}_{S\setminus
T}\rangle\rvert\leqslant\sum_{T\subseteq S}\lvert\langle
A{\mathbf{1}}_{T},{\mathbf{1}}_{S\setminus T}\rangle\rvert$

and by the third assumption in the theorem, this is at most

$\alpha\sum_{T\subseteq
S}\lVert{\mathbf{1}}_{T}\rVert\lVert{\mathbf{1}}_{S\setminus T}\rVert.$

By AM-GM this is at most

$\alpha\sum_{T\subseteq S}\frac{1}{2}\lVert u\rVert^{2}=2^{n-1}\alpha\lVert
u\rVert^{2}.$ (B.7)

By combining (B.6) and (B.7) we get that $\langle Au,u\rangle\leqslant
2\alpha\langle u,u\rangle$.

Next, for arbitrary $u,v\in\\{0,1\\}^{X}$, we write
$u=w+u^{\prime},v=w+v^{\prime}$ where the support of $u^{\prime},v^{\prime},w$
is disjoint. We have that

$\langle Au,v\rangle=\langle Aw,w\rangle+\langle Au^{\prime},w\rangle+\langle
Aw,v^{\prime}\rangle+\langle Aw,v^{\prime}\rangle\leqslant$ $2\alpha(\lVert
w\rVert\lVert w\rVert+\lVert u^{\prime}\rVert\lVert w\rVert+\lVert
w\rVert\lVert v^{\prime}\rVert+\lVert w\rVert\lVert v^{\prime}\rVert)=$
$2\alpha(\lVert w\rVert+\lVert u^{\prime}\rVert)(\lVert w\rVert+\lVert
v^{\prime}\rVert)\leqslant 8\alpha\lVert v\rVert\lVert u\rVert.$

Finally, let $v,u\in\\{-1,0,1\\}^{X}$. We write $u=u^{+}-u^{-}$ and
$v=v^{+}-v^{-}$ where $u^{+},u^{-},v^{+},v^{-}\in\\{0,1\\}^{X}$. We again have
that

$\lvert\langle Au,v\rangle\rvert\leqslant\lvert\langle
Au^{+},v^{+}\rangle\rvert+\lvert\langle
Au^{+},v^{-}\rangle\rvert+\lvert\langle
Au^{-},v^{+}\rangle\rvert+\lvert\langle Au^{-},v^{-}\rangle\rvert\leqslant$
$\leqslant 8\alpha(\lVert u^{+}\rVert+\lVert u^{-}\rVert)(\lVert
v^{+}\rVert+\lVert v^{-}\rVert)\leqslant$ $32\alpha\lVert u\rVert\lVert
v\rVert.$

∎

###### Proof of Claim B.3.

(B.1) is homogenuous, so we assume without loss of generality that $max_{x\in
X}\lvert v(x)\rvert\leqslant 2^{-2}$. We denote
$v(x)=sign(v(x))(1+\delta_{x})2^{i_{x}}$ for $i_{x}$ a negative integer and
$\delta_{x}\in[0,1)$. We sample $w$ as follows. For every $x\in X$
independently we sample $w(x)=sign(v(x))2^{i_{x}+1}$ with probability
$\delta_{x}$ and $w(x)=sign(v(x))2^{i_{x}}$ with probability $1-\delta_{x}$.
Obviously, the second item in the claim holds, namely, $w(x)$ is equal to
$sign(v(x))$ times some negative power of $2$. Furthermore, it is clear that
$\langle w,w\rangle\leqslant 2\langle x,x\rangle$. Finally, note that by
linearity of expectation, $\operatorname*{\mathbb{E}}_{{w}}\left[\langle
w,Aw\rangle\right]=\sum_{x,y}\operatorname*{\mathbb{E}}_{{w}}\left[w(x)w(y)\right]\langle
A{\mathbf{1}}_{x},{\mathbf{1}}_{y}\rangle$. As $A$ is non-lazy, and
$w(x),w(y)$ are pairwise independent, this is equal to $\sum_{x\neq
y}\operatorname*{\mathbb{E}}_{{w}}\left[w(x)\right]\operatorname*{\mathbb{E}}_{{w}}\left[w(y)\right]\langle
A{\mathbf{1}}_{x},{\mathbf{1}}_{y}\rangle=\langle Av,v\rangle$. Thus there
exists some $w$ so that its inner product is greater or equal the expectation,
$\langle Aw,w\rangle\geqslant\langle Av,v\rangle$. For that $w$ the first item
holds, namely, $\frac{\langle Av,v\rangle}{\langle v,v\rangle}\leqslant
2\frac{\langle Aw,w\rangle}{\langle w,w\rangle}$. ∎


# Bilingual Dictionary-based Language Model Pretraining for Neural Machine
Translation

Yusen Lin*
Univ. of Maryland
<EMAIL_ADDRESS>
Jiayong Lin
Univ. of Maryland
<EMAIL_ADDRESS>
Shuaicheng Zhang
Univ. of Maryland
<EMAIL_ADDRESS>
Haoying Dai
Univ. of Maryland
<EMAIL_ADDRESS>

###### Abstract

Recent studies have demonstrated a perceivable improvement on the performance
of neural machine translation by applying cross-lingual language model
pretraining Lample and Conneau (2019), especially the Translation Language
Modeling (TLM). To alleviate the need for expensive parallel corpora by TLM,
in this work, we incorporate the translation information from dictionaries
into the pretraining process and propose a novel Bilingual Dictionary-based
Language Model (BDLM). We evaluate our BDLM in Chinese, English, and Romanian.
For Chinese-English, we obtained a 55.0 BLEU on WMT-News’19 Tiedemann (2012)
and a 24.3 BLEU on WMT’20 news-commentary, outperforming the Vanilla
Transformer Vaswani et al. (2017) by more than 8.4 BLEU and 2.3 BLEU,
respectively. According to our results, the BDLM also has advantages on
convergence speed and predicting rare words. The increase in BLEU for WMT’16
Romanian-English also shows its effectiveness in low-resources language
translation.

##  1 Introduction

Many previous works in language representation models like BERT Devlin et al.
(2018) have shown that prior knowledge is of great importance to many
downstream tasks such as natural language understanding (NLU) and neural
machine translation (NMT). As one of the most successful Language Models
(LMs), cross-lingual language models (XLMs) Lample and Conneau (2019), which
construct LM upon corpora from multiple languages, have demonstrated their
ability to reach state-of-the-art performance in NLU as well as NMT. However,
XLMs like Translation Language Model (TLM) require expensive corpus with
parallel sentences for training and such a dataset might not be available in
certain languages.

Meanwhile, a dictionary contains information like Part-of-Speech (POS) and
synonyms that human frequently refers to. Inspired by this, there have been a
few previous works, such as Zhang and Zong (2016) and Adams et al. (2017),
that incorporate bilingual dictionaries into NMT to improve translation
quality and to obtain translations of rare words. Zhang and Zong (2016)
integrates the dictionary information into the training process by mixing
words or characters to the corresponding tokens or synthesizing parallel
sentences. This method inevitably introduces ambiguity into the model due to
the ignorance of context and still has room for improvement. As for Adams et
al. (2017), it incorporates the dictionary information into the pretraining
process and then fine-tunes the model with the pretrained embeddings. Although
it also evaluates fine-tuning with the entire Long Short-Term Memory Model
Gers et al. (1999), recent studies show Vanilla Transformer Vaswani et al.
(2017) performs better on many NMT tasks.

In this article, we propose a novel LM named Bilingual Dictionary-based
Language Model (BDLM) that learns dictionary information during pretraining.
By replacing words in a sentence with information from the dictionary, BDLM
could be trained on monolingual corpora. Besides, the ambiguity problem is
greatly alleviated because BDLM is only pretrained for initialization, which
is fined-tuned later to better fit the NMT for word choice. As we shall see
later, the BDLM benefits the translation tasks in many aspects.

Our main contributions are as follows:

  * •

BDLM incorporates rich information from the dictionary into the pretraining
process. When being applied to NMT task, a steady increase of the BLEU score
is observed.

  * •

BDLM could be trained only by monolingual corpus with dictionary information,
which is especially helpful for improving translation quality for low-resource
languages.

  * •

BDLM significantly improves the translation precision of rare words.

  * •

BDLM speeds up the convergence of Vanilla Transformer for the NMT tasks.

##  2 Related Work

#### Language Model Pretraining and BERT

Devlin et al. (2018)’s work has shown great success in pretraining a language
representation model for many natural language downstream tasks. In this
paper, two unsupervised pretraining tasks, the Masked LM (MLM) and Next
Sentence Prediction (NSP), are first proposed to train the BERT. The MLM is
for getting better token representations bidirectionally while the NSP is for
capturing the sentence-level relationships. The MLM randomly masks a small
ratio of tokens and set those masked tokens to be the ground truth of the
corresponding sentences; the NSP classifies the actual next sentence from a
randomly selected sentence. However, those LMs do not consider multi-lingual
information for NMT.

#### Cross-lingual Language Model (XLM) Pretraining

Taking advantage of BERT’s success by LM pretraining, Lample and Conneau
(2019) proposes the idea of XLM pretraining. They propose a Translation
Language Model (TLM) to take account of multi-lingual information by simply
concatenating two parallel sentences processed by MLM. By masking words
randomly in sentences of both the source side and target side, the model can
attend the surrounding source context as well as the target context. The TLM
is typically used in combination with MLM. Although it achieves several state-
of-the-art results on NLU, unsupervised NMT tasks, supervised NMT tasks, and
etc, it requires a large number of expensive parallel corpora, which are not
available for low-resource languages.

Compared to TLM, our model is able to train on considerable monolingual
corpora by introducing the dictionary information to the pretraining process.
Opposed to Ren et al. (2019), we do not explicitly build up a look-up table,
which is likely to bring additional bias by the errors of the look-up table.
Ren et al. (2019) proposes another XLM named cross-lingual masked language
model (CMLM), which introduces a complicated N-gram embedding procedure and an
N-gram translation table. Another similar task of ours is known as cross-
lingual word embedding Klementiev et al. (2012), which aims to learn cross-
lingual word embeddings by pretraining with a monolingual corpus with the
translation information from the dictionary.

##  3 Bilingual Dictionary-based Language Model

Figure 1: Three LM objectives of BDLM with translation information.

In this section, we will give a detailed introduction to the proposed BDLM.
BDLM is a multi-LM model that three LM objectives are pretrained on one
unified architecture. After pretraining, it is fine-tuned for NMT tasks with
initialization with all the pretrained parameters including the embedding
layers, encoder, and decoder. No dependency on parallel corpora and
representation with rich prior knowledge are its advantages. Although BDLM can
be applied to any auto-regressive encoder-decoder architecture models, we opt
for implementation with Vanilla Transformer.

###  3.1 Input Representations

Following Lample et al. (2017), we share the same vocabulary for all languages
and leverage part of their input settings. Figure 1 demonstrates an example of
the input representations during training.

#### Input of Encoder

There are three types of embeddings at the input of the encoder: token
embeddings, type embeddings, and position embeddings. For position embeddings,
we use the sinusoidal position encoding in Vaswani et al. (2017) while the
other two embeddings are learned. The type embeddings are used to denote the
information type of the corresponding token. It is extended from language
embeddings so that BDLM can adapt to more information besides translation.

#### Input of Decoder

Except for token embeddings and type embeddings, there are two types of
position embeddings at the input of the decoder: hard position embeddings and
soft position embeddings.

The hard position embeddings denote the absolute position of each token at the
decoder input sequence and are used to record the order information.
Meanwhile, the soft position embeddings denote the first position of the
masked or replaced words/phrases at the input of the encoder and are used to
record their corresponding positions in the original sentence. For example, in
the IPLM inside figure 1 (discussed in Section 3.2), the ”活泼开朗” can be
translated to ”lively and cheerful”. The soft positions for ”lively and
cheerful” are the first position of the ”活泼开朗” in the encoder input, which
help the model attend the ”活泼开朗”; while the hard positions help specify the
relative positions in the phrase ”lively and cheerful”. It’s worth noting that
the soft position embeddings are only exploited during pre-training and will
be dropped when being fine-tuned for NMT tasks.

###  3.2 Multi-language-model Objectives

BDLM contains three various LM objectives: Masked Language Model(MLM),
Replaced Language Model (RLM), and Information Prediction Language Model
(IPLM). Figure 1 shows these objectives for incorporating translation
information into the pretraining process.

#### MLM:

As proved by Lample and Conneau (2019), combining MLM with other LM objectives
could achieve a better representation than only using one LM objective. We
leverage the strength of multi-LM but only apply the MLM for the words that
can be mapped by the dictionary. A portion of those words is randomly masked
out with special tokens [mask] and then serve as the ground truth of the
corresponding input sequence. Then, the neural model is trained to predict the
masked words from their contexts.

#### RLM:

The difference between the MLM and the RLM is that the replaced tokens are no
longer the special mask tokens. Instead, tokens representing the information
from the dictionary are placed into the masked positions. For the case of
incorporating translation information into the BDLM, we replace the masked
tokens of the input sentence with the corresponding translation tokens. In
this case, the LM is forced to recover the original words from the replaced
translations and the context so that the translation knowledge could be
integrated into the BDLM to some extent.

#### IPLM:

Compared to the MLM, One distinct feature of the IPLM is that the LM learns to
predict the linguist information of the original tokens instead of merely the
original masked tokens from the context. In case the masked token has multiple
information, which is likely to happen in many scenarios like a word has
multiple translations or POS. we introduce a special separation token [sep],
which aims to concatenate various information. For the translation case of
BDLM in Figure 1, the ”活泼开朗” in the sentence of the encoder input is masked
and the ground truth becomes a sequence of ”lively and cheerful” and
”outgoing”, divided by [sep] tokens. IPLM is trained to build up the
connections between the contextual information of one word to its
corresponding translation.

However, IPLM brings up ambiguity because dictionary translation does not take
account of contextual information. The ambiguity can be alleviated because
IPLM is only pretrained for initialization. Besides, getting the knowledge of
a similar representation is beneficial. Intuitively, IPLM is a simulation of
human learning a new language. When a human learns a new language by starting
with the vocabulary, he/she is probably learning non-native and imprecise
knowledge. It is easier to acquire the correct knowledge when a human gets a
new language environment. This process maps the fine-tuning stage. he/she can
realize the vocabulary learned before is helpful in the new environment.

###  3.3 Training schedule

The multiple LM objectives are trained on one unified architecture with the
same cross-entropy loss function with label smoothing Szegedy et al. (2016).
Before training, samples for each LM are randomly drawn with a fixed ratio to
form a combined training set. For the model to distinguish the various LMs,
distinct special start tokens and end tokens are added to the start and the
end position of the input sentences for each LM. The dataset is then shuffled
and fed into the model. Finally, the model is able to automatically switch the
pretraining process among multiple LMs according to the data being fed.

###  3.4 Integrating Dictionary Information

Figure 1 illustrates an example of integrating translation information into
BDLM. Besides translation, BDLM can be extended to various information such as
POS, synonyms, definition, and named entity (NE). To incorporate the POS or NE
information, for the RLM, we could replace the masked tokens of a word or
phrase with the corresponding POS tags or NE tags. B, M, E, O are the prefix
of tags for the beginning, middle, ending, and no-chunk tokens respectively.
As for the IPLM, the ground truth becomes the sequence of those POS or NE
tags. The same methods also apply to synonyms and definitions.

##  4 Experiment Settings

###  4.1 Datasets

Dataset | Train | Val | Test
---|---|---|---
WMT-News’19 Zh-En | 16k | 2k | 2k
WMT’20 Zh-En(NC) | 300k | 6k | 6k
WMT’16 Ro-En(6k) | 5.4k | 0.6k | 0.6k
WMT’16 Ro-En(60k) | 54k | 6k | 6k
Table 1: Statistics of the division of the dataset. The WMT’20 Zh-En(NC)
represents the WMT’20 Zh-En news-commentary dataset. Follow Gu et al. (2018),
the WMT’16 Ro-En(6k) and WMT’16 Ro-En(60k) are the subsets of the WMT’16 Ro-
En, containing 6k and 60k sentence pairs, respectively. The ”Train”, ”Val”,
and ”Test” columns indicate the count of sentence pairs of the training set,
validation set, and test set respectively.

The experiments were performed on WMT-News’19 Zh-En Tiedemann (2012), WMT’20
Zh-En news-commentary, and WMT’16 Ro-En. The datasets contain 20K, 310K, and
610K bilingual pairs and there are 510K, 6.9M, and 14M English tokens,
respectively. Following Gu et al. (2018), we only used 6k and 60k WMT’16 Ro-En
sentence pairs for the training set for the purpose of low-resource testing.
Table 1 shows the ratio of the training, validation, and test sets of each
dataset. For the pretraining, only the training sets are used, and both the
source and target sides of them are used as monolingual data. Besides, for
each set of experiments, we built a joint vocabulary with vocabulary size 50k,
80k, 90k, and 90k, respectively. For the Chinese side, Jieba
toolkit111https://github.com/fxsjy/jieba is used for tokenization. After
tokenization, we apply the SubwordTextEncoder toolkit in
Tensorflow222https://www.tensorflow.org/datasets/api_docs/python/
tfds/features/text/SubwordTextEncoder for byte-pair encoding Sennrich et al.
(2015). Sentences longer than 60 subwords would be removed from the dataset.

###  4.2 Dictionaries

We integrated data from multiple sources, including Facebook research Conneau
et al. (2017), Facebook Muse333https://ai.facebook.com/tools/muse/, Wiki-
titles444http://data.statmt.org/wikititles/, NLTK
wordnet555https://www.nltk.org/howto/wordnet.html, and
ECDICT666https://github.com/skywind3000/ECDICT. The integrated dictionary
consists of translation, Part-of-Speech (POS), synonyms, definitions, and
named entity (NE) information. We cleaned the dictionary by only preserving
tokens whose translations occur in the combined corpus. The dictionary remains
760K Chinese tokens, 1.4M English tokens, and 120K Romanian tokens after the
cleaning process. The dictionary coverage of Chinese, English and Romanian
tokens are 70%, 59% and 27% respectively, with approximately the same coverage
for training, validation and test sets.

###  4.3 Sample Rate

The sample rate represents the number of repeated sampling for the same
sentence during pretraining. For each sentence in pretraining, we perform word
masking randomly. A higher sample rate can increase the probability that the
words in each sentence are learned.

###  4.4 Evaluations

$Prec_{rare/dict}=\frac{1}{N}\sum_{i=1}^{N}\frac{\sum_{j=1}^{count(y_{i})}[y_{i,j}=\hat{y}_{i,j}]}{count(y_{i})}$
(1)

For the evaluation of supervised machine translation performance, we use case-
insensitive BLEU score, precision for rare words (Prec(rare)), and precision
for words that appear in the dictionary (Prec(dict)), while for the
pretraining tasks, we use perplexity and accuracy. We used case insensitive
BLEU from nltk’s corpus bleu
toolkit777https://www.nltk.org/_modules/nltk/translate/bleu_score.html. Koehn
and Knowles (2017) serves as a good foundation for our research for metrics on
rare words. Equation 1 is used for Prec(rare) and Prec(dict). The N stands for
the count of words that occurs less than 10 times when calculating Prec(rare)
and stands for the count of words appear in dictionary when calculating
Prec(dict).  yi and ŷi,j respectively represent the ground truth and
corresponding predicted words. The bracket returns 1 if  yi equals to ŷi,j,
and returns 0 otherwise.

###  4.5 Training Details

In all experiments, following Vaswani et al. (2017); Lample and Conneau (2019)
we use a vanilla Transformer architecture with 8 heads, 6 layers for the
encoder, 6 layers for the decoder, ReLU activations, a dropout rate of 0.1,
and sinusoidal positional embeddings. For the reasons of training time and the
NMT performance of Vanilla Transformer on WMT-News’19 Zh-En, we choose 128 of
hidden units and of embedding size. The training set for NMT is used for
pretraining. We train our models with the Adam optimizer Kingma and Ba (2014),
set the initial learning rate to 1e-4 and the mini-batch size is 16. To build
a competitive baseline model, we use a shared token embedding layer and type
embedding layer described in section 3 for both encoder and decoder. Besides,
Label smoothing with $\epsilon=0.1$ is added for the cross-entropy loss.
Greedy decoding is used and the average accuracy of the translated tokens in
the validation set is used as a stopping criterion for training.

##  5 Results

In this section, we empirically present BDLM’s fine-tuning results and
demonstrate the effectiveness of NMT, which shows our approach significantly
outperforms Vanilla Transformer and TLM.

###  5.1 Golden information in Dictionary

models | BLEU | Prec(rare) | Prec(dict)
---|---|---|---
Vanilla | 46.6 | 46.5 | 54.2
MLM | 46.7 | 46.8 | 54.3
TLM | 48.8 | 47.5 | 55.8
translate | 55.0 | 53.7 | 61.4
POS | 44.5 | 45.5 | 52.3
synonyms | 47.7 | 48.0 | 56.0
definitions | 37.4 | 34.4 | 42.2
NE | 51.0 | 52.2 | 59.2
Table 2: Supervised NMT Results on WMT-News’19 Zh-En. BLEU, precision of rare words, and precision of words in the dictionary are used for evaluation. Models pretrained with different schemes are evaluated. Vanilla Transformers without pretraining, with MLM pretraining, and with TLM pretraining are used as baselines. For BDLM, we investigate translation, POS, synonym, definition, and NE information to examine which information is beneficial to NMT. tasks | size | epochs | acc | ppl
---|---|---|---|---
MLM | 80k | 5 | 5.2 | 3.08
TLM | 91k | 11 | 14.9 | 5.14
translate | 132k | 80 | 13.3 | 2.06
POS | 71k | 8 | 12.1 | 2.28
synonyms | 12k | 66 | 7.4 | 2.15
definitions | 23k | 165 | 48.8 | 2.25
NE | 142k | 48 | 17.2 | 2.03
Table 3: Statistics and Performance of Different pretrain Tasks. For each
model, we included the training data size, number of epochs the pretraining
runs, pretraining’s token-level accuracy, and perplexity.

A typical bilingual dictionary contains rich information includes but not
limited to: translation, POS, synonyms, definition, and named entity (NE). The
translation information naturally fits the NMT task because the pretraining
process could build a connection between the translation representation and
the corresponding context; synonyms could also lead to a better-generalized
model with diversified translations; NE information helps the model to locate
and recognize the entity.

In Table 2, we evaluate five BDLMs, each one leverages one distinct
information from the dictionary, which is the translation, POS, synonym,
definition, and NE information, respectively. To prove the benefit of
incorporating information from dictionary into pretraining, we include three
baselines: Vanilla Transformers without pretrain, with MLM pretrained, and
with TLM pretrained. We evaluate on WMT-News’19 Zh-En and use BLEU, precision
of rare words, and precision of words in the dictionary as metrics. Our
results show that BDLM with translation information (BDLMtranslate) gets a
superior performance of 55.0 BLEU over other BDLMs, which proves that the
translation information is the most valuable for NMT. Besides BDLMtranslate,
BDLMNE also significantly outperforms the three baselines. To better interpret
the results, Table 3 shows the statistics and performance of the models. The
data sizes vary among different tasks due to the various size of information;
the epochs vary because the models early stop at different epochs
automatically. One of the factors that contribute to the better performance of
BDLMtranslate and BDLMNE is their large data size. However, although
BDLMsynonym has the smallest data size, it still improves the Vanilla and MLM
by 1.0+ BLEU; BDLMtranslate has the second-largest data size but performs the
best on NMT. It proves that the data size is related to the effect of
pretraining, but the relevance to the translation task itself is more
important. The BDLMPOS performs poorly because of the under-fitting problem.
Due to the noisiness and small size of data, only 8 epochs were trained for
BDLMPOS. Meanwhile, the BDLMdefinition suffers from the over-fitting problem.
BDLMdefinition trained too many epochs and the discrepancy between the
definition and translation information is huge, leading to worse performance
than Vanilla. Additionally, our empirical experience shows the token-level
accuracy and perplexity of pretraining have no direct relationship with the
NMT performance but only demonstrate how well the task has been trained.

###  5.2 Effect of Sample Rate

| $samplerate$
---|---
$models$ | 3.0 | 10.0
BDLMtranslation | 38.4 | 55.0
BDLMNE | 41.2 | 51.0
Table 4: BLEU for BDLMs with Different Sample Rate. We tested BDLMtranslate
and BDLMNE with a sample rate of 3.0 and 10.0.

In Table 4, we highlight experiments on translation and NE models with a
sample rate of 3.0 and 10.0. Based on experimental results, a higher sample
rate yields better performance.

###  5.3 Evaluation for Convergence Speed

To measure the effectiveness of pretraining, we compared the Convergence Speed
of BDLMtranslate with Vanilla. The train and test data are from WMT’20 Zh-En
news-commentary. Figure 4 shows the obvious advantages of BDLMtranslate in
convergence speed. BDLMtranslate-10.0 achieves 23.0 BLEU at the 20th epoch,
which is higher than BDLMtranslate-0.5 and Vanilla at the 100th epoch. It
implies that the model has learned abundant effective representation during
pretraining.

###  5.4 Effect on Translating Rare words

Figure 2: Examples of Translation Results. We extracted 3 examples from test
data to show how the BDLMtranslate-10.0 helps the translation quality.  Figure
3: Precision of the translated words. The left portion of the graph
corresponds to rarer words. The blue indicates Vanilla Transformer model
performed better, the red indicates the BDLMtranslate performed better, and
the magenta is their overlapping regions. Figure 4: The Convergence Speed
Comparison on WMT’20 Zh-En news-commentary. We Calculate the BLEU at multiple
epochs during training.

We further evaluate the precision of translated words with different
occurrence frequencies with the BDLMtranslate in section 5.1. As shown in
Figure 3, it compares the precision performance of the Vanilla Transformer
with the BDLMtranslate. The x-axis of the figure represents the training
dataset occurrence groups and is set at a logarithmic scale. The left portion
of the graph corresponds to rarer words. The y-axis corresponds to the ratio
of words found in the predicted sentences compared to the ground truth. The
red region is always on the top of the magenta region and there is a bigger
red area on the left portion of the figure, which confirms that BDLMtranslate
is effective for improving the translation of rare words. In addition, the
precision of rare words and precision of words in the dictionary shown in
Table 2 also proves that BDLMtranslate and BDLMNE have large gains on the
translation of rare words.

Through the model trained in section 5.3, we use some test cases to observe
the advantages of BDLM in Rare words translation. Figure 2 shows translation
sentence samples from BDLMtranslation-10.0 and Vanilla.

Figure 5: Attention map for the 3rd example in Figure 2

In the third example, the Chinese phrase ”实施了量化宽松方案” can be successfully
translated to ”implemented a quantitative easing program” in
BDLMtranslate-10.0 while Vanilla cannot. Four words in the phrase ”实施”, ”量化”,
”宽松” and ”方案” all appear in the dictionary used in pretraining. This indicates
that pretraining improves the accuracy of rare words translation.

Figures 5 show the attention maps for a Zh-En translation example. The lighter
the region is, the larger the attention value is. Figure 5.a uses Vanilla for
translation while Figure 5.b uses BDLMtranslate-10.0 in section 5.3. When
comparing the two figures, we can find that the diagonal brightness of Figure
5.b is higher than that of Figure 5.a. Especially the upper left corner area,
where the ”量化宽松方案” locates, BDLMtranslate-10.0’s attention is more observable.

###  5.5 Effect for Low-resource Language

models | ro-en6k | ro-en60k | en-ro6k | en-ro60k
---|---|---|---|---
Vanilla | 3.6 | 33.3 | 3.5 | 30.7
BDLM | 5.4 | 35.6 | 5.2 | 32.9
VanillaGu et al. (2018) | 1.2 | 12.1 | – | –
Multi-NMT+UnivTokGu et al. (2018) | 20.1 | 24.3 | – | –
Table 5: BLEU for NMT on WMT’16 Ro-En

In previous experiments, we only verified the effectiveness of BDLM on zh and
en. Both Chinese and English are high-resource languages, meaning that we can
obtain a large number of parallel corpus and dictionary resources. Gu et al.
(2018) uses Multi-lingual NMT with a transfer-learning method to share lexical
and sentence level representations across multiple source languages into one
target language. The main goal is to help low-resource languages by sharing
the learned model. We adapted their experimental settings to measure the
performance of BDLM in a low-resource language. We use WMT’16 Ro-En data as a
monolingual resource to pretrain the model, and train NMT models on 6k and 60k
sentence pairs respectively. In addition, we tested our Vanilla and BDLM on
the En-Ro task to verify the generalization of the model. As shown in Table 5,
due to our baseline boost settings described in Section 4.4, our Vanilla
exceeds Gu et al. (2018)’s Vanilla significantly. The BDLM outperforms Vanilla
in every experiment. In the 6k training setting, Multi-NMT+UnivTok’s
performance is phenomenal because they used a large number of parallel corpora
of other high-resource languages. However, the BDLM’s advantages are shown in
the 60k training setting. It outperforms Multi-NMT+UnivTok by 11.3 BLEU. BDLM
and Multi-NMT+UnivTok both significantly improve the performance of low-
resource language.

##  6 Conclusion

We proposed a novel BDLM that incorporates dictionary information into the
pretraining process. We investigated multiple information, including
translation, POS, synonyms, definitions, and NE information, and prove that
the translation information is the most valuable for NMT tasks. Compared with
TLM, our proposed BDLM does not need any parallel corpus. Our experiments show
that BDLM pretraining is effective for improving the BLEU scores for NMT
tasks. Due to random masking during pretraining, a higher sample rate can
increase the probability that each word of the sentence is learned, thereby
improving the BLEU value of the model. In addition, BDLM’s convergence speed
is significant faster than Vanilla Transformer. When predicting rare words,
BDLM also has obvious improvement for words that appear in the dictionary.
Through experiments of WMT’16 Ro-En, we also verified the considerable
improvement of BDLM in a low-resource language NMT task.

##  7 Future Work

We are interested in conducting ablation experiments for the three pretrain
LMs of BDLM to understand how these LMs benefit NMT independently. Besides, we
plan to use a large amount of data for pretraining with the support of more
GPUs. We also plan to apply a multi-task for incorporating the translation,
NE, and synonym information into the pretraining process. Finally, extending
the bilingual to multi-lingual model, especially for those low-resource
languages, is in the schedule.

## References

  * Adams et al. (2017) Oliver Adams, Adam Makarucha, Graham Neubig, Steven Bird, and Trevor Cohn. 2017\.  Cross-lingual word embeddings for low-resource language modeling.  In _Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers_ , pages 937–947.
  * Conneau et al. (2017) Alexis Conneau, Guillaume Lample, Marc’Aurelio Ranzato, Ludovic Denoyer, and Hervé Jégou. 2017.  Word translation without parallel data.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Gers et al. (1999) Felix A Gers, Jürgen Schmidhuber, and Fred Cummins. 1999.  Learning to forget: Continual prediction with lstm.
  * Gu et al. (2018) Jiatao Gu, Hany Hassan, Jacob Devlin, and Victor O.K. Li. 2018.  Universal neural machine translation for extremely low resource languages.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 344–354, New Orleans, Louisiana. Association for Computational Linguistics.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_.
  * Klementiev et al. (2012) Alexandre Klementiev, Ivan Titov, and Binod Bhattarai. 2012.  Inducing crosslingual distributed representations of words.  In _Proceedings of COLING 2012_ , pages 1459–1474.
  * Koehn and Knowles (2017) Philipp Koehn and Rebecca Knowles. 2017.  Six challenges for neural machine translation.  In _Proceedings of the First Workshop on Neural Machine Translation_ , pages 28–39, Vancouver. Association for Computational Linguistics.
  * Lample and Conneau (2019) Guillaume Lample and Alexis Conneau. 2019.  Cross-lingual language model pretraining.  In _NeurIPS_.
  * Lample et al. (2017) Guillaume Lample, Alexis Conneau, Ludovic Denoyer, and Marc’Aurelio Ranzato. 2017\.  Unsupervised machine translation using monolingual corpora only.  _arXiv preprint arXiv:1711.00043_.
  * Ren et al. (2019) Shuo Ren, Yu Wu, Shujie Liu, Ming Zhou, and Shuai Ma. 2019.  Explicit cross-lingual pre-training for unsupervised machine translation.  In _EMNLP/IJCNLP_.
  * Sennrich et al. (2015) Rico Sennrich, Barry Haddow, and Alexandra Birch. 2015.  Neural machine translation of rare words with subword units.  _arXiv preprint arXiv:1508.07909_.
  * Szegedy et al. (2016) Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. 2016.  Rethinking the inception architecture for computer vision.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 2818–2826.
  * Tiedemann (2012) Jörg Tiedemann. 2012.  Parallel data, tools and interfaces in opus.  In _Lrec_ , volume 2012, pages 2214–2218.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in neural information processing systems_ , pages 5998–6008.
  * Zhang and Zong (2016) Jiajun Zhang and Chengqing Zong. 2016.  Bridging neural machine translation and bilingual dictionaries.  _ArXiv_ , abs/1610.07272.