# Some Properties of Fibonacci-Sum Set-Graphs

Eunice Gogo Mphako-Banda  School of Mathematical Sciences
University of Witswatersrand
Johannesburg, South Africa.
<EMAIL_ADDRESS>Johan Kok Centre for Studies in Discrete
Mathematics
Vidya Academy of Science & Technology
Thalakkottukara, Thrissur, Kerala, India.
<EMAIL_ADDRESS> Sudev Naduvath111Corresponding Author Centre for
Studies in Discrete Mathematics
Vidya Academy of Science & Technology
Thalakkottukara, Thrissur, Kerala, India.
<EMAIL_ADDRESS>
###### Abstract

In this paper we study some properties of Fibonacci-sum set-graphs. The
aforesaid graphs are an extension of the notion of Fibonacci-sum graphs to the
notion of set-graphs. The colouring of Fibonacci-sum graphs (not set-graphs)
is also discussed. A number of challenging research problems are posed in the
conclusion.

Keywords: Set-graph, Fibonacci-sum set-graph.

Mathematics Subject Classification 2010: 05C15, 05C38, 05C75, 05C85.

##  1 Introduction

For general notation and concepts in graphs and digraphs see [2, 4, 7]. Unless
stated otherwise, all graphs will be finite connected graphs with multiple
edges and loops are permitted. The number of multiple (or single) edges
between vertices $u$ and $v$ is denoted by $\epsilon(u,v)$. Therefore,
$\epsilon(u,v)\geq 0$. Note that $\epsilon(u,v)=0$ implies that the vertices
$v,u$ are non-adjacent. For a vertex $v$ its number of loops is denoted,
$l(v)$. The open neighbourhood of a vertex $v$, denoted by $N(v)$, is the set
of vertices which are adjacent to $v$. The degree of a vertex $v\in V(G)$ is
denoted $d_{G}(v)$ or when the context is clear, simply as $d(v)$. The degree
of a vertex $v$ is given by $d(v)=2l(v)+\epsilon(v,u)$, where $u\in N(v)$.

Recall that the sequence of Fibonacci numbers $\mathcal{F}=\\{f_{n}\\}_{n\geq
0},\ n\in\mathbb{N}_{0}$ is defined recursively as $f_{0}=0$, $f_{1}=1$ and
$f_{n}=f_{n-1}+f_{n-2}$. As defined in [3], a Fibonacci-sum graph is defined
for a finite set of the first $n$ consecutive positive integers
$\\{1,2,3,\ldots,n\\}$ as $G^{F}_{n}$ with $V(G^{F}_{n})=\\{v_{i}:1\leq i\leq
n\\}$ and $E(G^{F}_{n})=\\{v_{i}v_{j}:i\neq j,i+j\in\mathcal{F}\\}$.

In this paper, we introduce the notion of a new class of graphs, namely the
Fibonacci-sum set-graphs and study some fundamental structural characteristics
of this graph class. Fibonacci-sum set-graphs are an extension of the notion
of Fibonacci-sum graphs to the notion of set-graphs.

##  2 Derivative Set-graphs

The notion of a set-graph was introduced in [5] as explained below.

######  Definition 2.1.

[5] Let $A^{(n)}=\\{a_{1},a_{2},a_{3},\dots,a_{n}\\}$, $n\in\mathbb{N}$ be a
non-empty set and the $i$-th $s$-element subset of $A^{(n)}$ be denoted by
$A^{(n)}_{s,i}$. Now, consider
$\mathcal{S}=\\{A^{(n)}_{s,i}:A^{(n)}_{s,i}\subseteq
A^{(n)},A^{(n)}_{s,i}\neq\emptyset\\}$. The set-graph corresponding to set
$A^{(n)}$, denoted $G_{A^{(n)}}$, is defined to be the graph with
$V(G_{A^{(n)}})=\\{v_{s,i}:A^{(n)}_{s,i}\in\mathcal{S}\\}$ and
$E(G_{A^{(n)}})=\\{v_{s,i}v_{t,j}:A^{(n)}_{s,i}\cap
A^{(n)}_{t,j}\neq\emptyset\\}$, where $s\neq t$ or $i\neq j$.

Note that the definition of vertices implies, $v_{s,i}\mapsto
A^{(n)}_{s,i}\in\mathcal{S}$.

$v_{1,1}$$v_{1,2}$$v_{1,3}$$v_{2,1}$$v_{2,2}$$v_{2,3}$$v_{3,1}$ Figure 1: The
set-graph $G_{A^{(3)}}$.

###  2.1 Fibonacci-sum set-graph

Derivative set-graphs are obtained by considering well-defined sets of
positive integers together with number theoretical operators or conditions
between the integers or the vertices corresponding to the subsets. For
colouring related results in respect of derivative set-graphs see [6].

The notion of a Fibonacci-sum set-graph can be introduced as follows.

######  Definition 2.2.

Let $A^{(n)}=\\{1,2,3,\ldots,n\\},\ n\in\mathbb{N}$ be a non-empty set and the
$i$-th $s$-element subset of $A^{(n)}$ be denoted by $A^{(n)}_{s,i}$. Now,
consider $\mathcal{S}=\\{A^{(n)}_{s,i}:A^{(n)}_{s,i}\subseteq
A^{(n)},A^{(n)}_{s,i}\neq\emptyset\\}$. The Fibonacci-sum set-graph
corresponding to set $A^{(n)}$, denoted $G^{F}_{A^{(n)}}$, is defined to be
the graph with $V(G^{F}_{A^{(n)}})=\\{v_{s,i}:A^{(n)}_{s,i}\in\mathcal{S}\\}$
and
$E(G^{F}_{A^{(n)}})=\\{v_{s,i}v_{t,j}:\forall(i^{\prime},j^{\prime}),i^{\prime}\in
A^{(n)}_{s,i},j^{\prime}\in A^{(n)}_{t,j},i^{\prime}\neq j^{\prime}\mbox{and
the sum}\ i^{\prime}+j^{\prime}\in\mathcal{F}\\}$.

Since $A^{(n)}_{s,i}$ and $A^{(n)}_{t,j}$ are not necessarily distinct, it
follows that loops are permitted. Figure 2 depicts the Fibonacci-sum set-graph
$G^{F}_{A^{(3)}}$. Significant differences exist between the Fibonacci-sum
graph $G^{F}_{3}\cong P_{3}$, the set-graph $G_{A^{(3)}}$ and the Fibonacci-
sum set-graph $G^{F}_{A^{(3)}}$. Evidently,
$\nu(G^{F}_{n})\leq\nu(G_{A^{(n)}})=\nu(G^{F}_{A^{(n)}})$ and
$\varepsilon(G^{F}_{n})\leq\varepsilon(G_{A^{(n)}})\leq\varepsilon(G^{F}_{A^{(n)}})$
with equality throughout only for $n=1$.

$v_{3,1}$$v_{1,1}$$v_{1,2}$$v_{1,3}$$v_{2,1}$$v_{2,2}$$v_{2,3}$ Figure 2:
Fibonacci-sum set-graph $G^{F}_{A^{(3)}}$.

######  Theorem 2.1.

For $n\in\mathbb{N}$, the Fibonacci-sum set-graph has no pendant vertices.

###### Proof.

The result can easily be verified for $n=1,2$. Note that an isolated vertex is
not a pendant vertex. Now assume that it holds for $n=k\geq 3$. The Fibonacci-
sum set-graph is, at least partially, constructed as follows:

Step 1: Take two copies of $G^{F}_{A^{(n)}}$ and label them $G_{1}$ and
$G_{2}$. Define a map $g:v_{s,i}\mapsto v^{\prime}_{s,i}$, where $v_{s,i}\in
V(G_{1})$, $v^{\prime}_{s,i}\in V(G_{2})$ and
$A^{{(n)}^{\prime}}_{s,i}=A^{(n)}_{s,i}\cup\\{k+1\\}$.

Step 2: Add all edges between $G_{1}$ and $G_{2}$ corresponding to Definition
2.2. Hence, all loops at vertex $v_{s,i}$, if any, correspond to multiple
edges between vertices $v_{s,i}$ and $v^{\prime}_{s,i}$. Furthermore, since
each $v_{s,i}\in V(G_{1})$ has at least two neighbours, say $v_{t,j}$,
$v_{m,q}$, in $G_{1}$, it follows that $v_{s,i}$ is adjacent to at least
$v^{\prime}_{t,j}$, $v^{\prime}_{m,q}$ in $G_{2}$. So, connectivity is ensured
with no pendant vertices resulting thus far.

Step 3(a): Consider the vertex $v_{1,k+1}$ corresponding to the subset
$\\{k+1\\}$. If $k+1$ is a Fibonacci number, say $f_{\ell}$, then $f_{\ell-1}$
exists in the finite set $A^{(n)}$ implying that at least two distinct subsets
exist which contains $f_{\ell-1}$. Hence, $d(v_{1,k+1})\geq 2$ in
$G^{F}_{A^{(n)}}$. Hence, the result holds for all $n\in\mathbb{N}$ and $n$
itself is a Fibonacci number.

Step 3(b): If $k+1$ is not a Fibonacci number, then a largest Fibonacci
number, say $f_{e}ll$ belongs to $A^{(n)}$. Also, $f_{\ell+1}\notin A^{(n)}$.
However, $\ell^{\prime}=f_{\ell+1}-(k+1)\in A^{(n)}$. Similarly, at least two
distinct subsets exist, each containing $\ell^{\prime}$. Since
$\ell^{\prime}+(k+1)=f_{\ell+1}$, vertex $v_{1,k+1}$ has $d(v_{1,k+1})\geq 2$
in $G^{F}_{A^{(n)}}$ as well. Hence, the result holds for all $n\in\mathbb{N}$
and $n$ itself is a non-Fibonacci integer.

Hence, by mathematical induction together with the well-ordering property of
the set of positive integers, the result follows for all $n\in\mathbb{N}$. ∎

The following two corollaries are the direct consequences of Theorem 2.1.

######  Corollary 2.2.

For $n\geq 1$, the Fibonacci-sum set-graph is connected.

######  Corollary 2.3.

For $n\geq 1$, the Fibonacci-sum set-graph is Hamiltonian.

######  Lemma 2.4.

For $n\geq 1$, the corresponding Fibonacci-sum set-graph has a unique vertex
$v$ for which $l(v)=\varepsilon(G^{F}_{n})$.

###### Proof.

For $n=1$, it follows that $G^{F}_{1}\cong K_{1}\cong G^{F}_{A^{(1)}}$.
Therefore, in $G^{F}_{A^{(1)}}$, $l(v_{1,1})=0=\varepsilon(G^{F}_{1})$.
Clearly, the vertex $v_{1,1}$ is unique. Similarly, for $n=2$, the Fibonacci-
sum graph is $G^{F}_{2}=P_{2}$. The Fibonacci-sum set-graph has vertices
$v_{1,1}=\\{1\\}$, $v_{1,2}=\\{2\\}$, $v_{2,1}=\\{1,2\\}$ and therefore has
edges $v_{1,1}v_{1,2}$, $v_{1,1}v_{2,1}$, $v_{1,2}v_{2,1}$ and loop
$v_{2,1}v_{2,1}$. Clearly, $l(v_{2,1})=1=\varepsilon(G^{F}_{2})$ and $v_{2,1}$
is unique, since $A^{(2)}_{1,1}\subset A^{(2)}_{2,1}=A^{(2)}$ and
$A^{(2)}_{1,2}\subset A^{(2)}_{2,1}=A^{(2)}$. Since $A^{(n)}_{s,i}\subset
A^{(n)}\in\mathcal{S}$ and $v_{2^{n}-1,1}\mapsto A^{(n)}$ is unique, by
mathematical induction, it follows that Definition 2.1 and Definition 2.2
imply $l(v_{2^{n}-1,1})=\varepsilon(G^{F}_{n})$. ∎

The next result is a direct derivative of Corollary 16 in [1] read together
with Lemma 2.4. Corollary 16 states that for $n\geq 1$ and $k\geq 2$
satisfying, $f_{k}\leq n\leq f_{k+1}$ then the number of edges of the
Fibonacci-sum graph, $G^{F}_{n}$ is

$\varepsilon(G^{F}_{n})=\begin{cases}n+\frac{f_{k}+1}{2}-\frac{\lfloor\frac{4(k+1)}{3}\rfloor}{2},&\text{if
$n\leq\frac{f_{k+2}}{2}$},\\\
2n+\frac{f_{k}+1}{2}-\frac{\lfloor\frac{4(k+1)}{3}\rfloor}{2}-\lceil\frac{f_{k+2}-1}{2}\rceil,&\text{if
$n>\frac{f_{k+2}}{2}$}.\end{cases}$

######  Theorem 2.5.

Let $n\geq 1$ and $k\geq 2$ be integers satisfying the inequality $f_{k}\leq
n\leq f_{k+1}$. For $A^{(n)}=\\{1,2,3,\dots,n\\}$ the vertex $v_{2^{n}-1,1}$
of the Fibonacci-sum set-graph, $G^{F}_{A^{(n)}}$ has maximum loop number,

$l(v_{2^{n}-1,1})=\begin{cases}n+\frac{f_{k}+1}{2}-\frac{\lfloor\frac{4(k+1)}{3}\rfloor}{2},&\mbox{if
$n\leq\frac{f_{k+2}}{2}$},\\\
2n+\frac{f_{k}+1}{2}-\frac{\lfloor\frac{4(k+1)}{3}\rfloor}{2}-\lceil\frac{f_{k+2}-1}{2}\rceil,&\mbox{if
$n>\frac{f_{k+2}}{2}$}.\end{cases}$

The result in Theorem 2.5 motivates us to introduce the notion of the loop
sequence of a graph as follows:

######  Definition 2.3.

The loop sequence is the sequence of the number of loops of the vertices,
$v_{i}\in V(G)$, $1\leq i\leq n$. For a simple graph $G$ of order $n$, the
loop sequence is $(l(v_{i})=0:1\leq i\leq n)$.

For $n\geq 1$, Theorem 2.5 results in an integer list given by
$\mathcal{L}_{n}=(0,1,2,3,4,5,7,8,\\\
9,10,12,14,15,16,17,18,19,21,23,25,26,\ldots,l(v_{2^{n}-1,1}))$. Note that
certain integers such as $6,11,13,20,22,\ldots$ are excluded from the list.

######  Theorem 2.6.

For $n\geq 1$, the loop sequence of the corresponding Fibonacci-sum set-graph
$G^{F}_{A^{(n)}}$ contains at least one of each entry in $\mathcal{L}_{n}$.

###### Proof.

We have to prove that for all $i\in\mathcal{L}_{n}$, there exists at least one
vertex $v_{s,i}\in V(G^{F}_{A^{(n)}})$ with $l(v_{s,i})=i$.

Consider any integer $n\in\mathbb{N}$ and its corresponding Fibonacci-sum set-
graph. All vertices $v_{1,i}$, $1\leq i\leq n$ are loop-free. Hence,
$l(v_{1,i})=0$, $1\leq i\leq n$. From Lemma 2.4, it follows that a unique
vertex exists with loop number equal to $l(v_{2^{n}-1,1})$.

For $n\geq 2$, all Fibonacci-sum set-graphs have the vertex
$v_{2,1}\mapsto\\{1,2\\}$ which has a single loop. Therefore, at least the
vertex $v_{2,1}$ exists with $l(v_{2,1})=1$. Similarly, for $n\geq 3$, all
Fibonacci-sum set-graphs have the vertex $v_{3,1}\mapsto\\{1,2,3\\}$ which has
a double loop. Therefore, at least the vertex $v_{3,1}$ exists with
$l(v_{3,1})=2$. Similarly, for $n\geq 4$, all Fibonacci-sum set-graphs have
the vertex $v_{4,1}\mapsto\\{1,2,3,4\\}$ which has a triple loop. Therefore,
at least the vertex $v_{4,1}$ exists with $l(v_{4,1})=3$.

Therefore, by induction read together with the well-ordering property of the
set of positive integers, the well-ordering of the power set
$\mathcal{P}(A^{(n)})-\emptyset$ and the well-defined set $\mathcal{L}_{n}$,
the result follows in general. ∎

######  Theorem 2.7.

For $n\geq 1$ all vertex degrees in the corresponding Fibonacci-sum set-graph
are even.

###### Proof.

As the loops account for an even count to a vertex degree, it is sufficient to
prove the result for the partial vertex degrees accounted for by incident
edges only.

The result can easily be verified for $n=1,2$. Assume the result holds for
$n=k\geq 3$. Following the partial construction as explained in the proof of
Theorem 2.1, it follows that the vertex degrees in the disjoint union,
$G_{1}\cup G_{2}$ are even. Edges between $G_{1}$ and $G_{2}$ are added as
follows. Each edge $v_{s,i}v_{t,j}$ in $G_{1}$ corresponds to the edges
$v_{s,i}v^{\prime}_{t,j}$ and $v_{t,j}v^{\prime}_{s,i}$ respectively. Hence,
this partial construction has even vertex degrees.

Finally, for $n\geq 2$, any element $j\in A^{(n)}$ is contained in $2^{n-1}$
distinct subsets of the power set $\mathscr{P}(A^{(n)})-\emptyset$. Hence, the
number of all possible pairs $(i,j)$ such that $i+j$ is a Fibonacci number, is
even. Thus, adding all additional edges to complete the construction of
$G^{F}_{A^{(n)}}$ results in all vertex degrees being even. ∎

######  Corollary 2.8.

For $n\geq 1$ the Fibonacci-sum set-graph is Eulerian.

###### Proof.

This result is a direct consequence of Theorem 2.7, since $G^{F}_{A^{(n)}}$
has no vertex with odd degree. ∎

######  Definition 2.4.

The popped graph of a graph $G$, denoted by $G^{{}^{\backepsilon}}$, is the
graph obtained by deleting all loops and all multiple edges except one (to
retain adjacency) from $G$.

Figure 3 depicts $G^{F^{{}^{\backepsilon}}}_{A^{(3)}}$.

$v_{3,1}$$v_{1,1}$$v_{1,2}$$v_{1,3}$$v_{2,1}$$v_{2,2}$$v_{2,3}$ Figure 3:
Popped Fibonacci-sum set-graph $G^{F^{{}^{\backepsilon}}}_{A^{(3)}}$.

######  Proposition 2.9.

For $n\geq 1$, the popped Fibonacci-sum set-graph has
$\varepsilon(G^{F^{{}^{\backepsilon}}}_{A^{(n)}})\leq(2^{n}-2)+\sum\limits_{u\in
N(v_{2^{n}-1,1})}\epsilon(v_{2^{n}-1,1},u)$.

###### Proof.

Clearly,
$\varepsilon(G^{F}_{A^{(n)}})=\varepsilon(G^{F^{{}^{\backepsilon}}}_{A^{(n)}})=2^{n}-1$.
For $n=1$, the equality holds and its verification is straight forward.

For $n\geq 2$, it can easily be verified that vertex $v_{2^{n}-1,1}$ is
adjacent to all vertices and hence in the popped graph
$G^{F^{{}^{\backepsilon}}}_{A^{(n)}}$, we have $d(v_{2^{n}-1,1})=2^{n}-2$.
With respect to the second term $\sum\limits_{u\in
N(v_{2^{n}-1,1})}\epsilon(v_{2^{n}-1,1},u)$ mathematical induction will be
used. For $n=2$ the popped graph $G^{F^{{}^{\backepsilon}}}_{A^{(2)}}\cong
K_{3}$. Hence, $\varepsilon(K_{3})=3<5=(2^{2}-2)+\sum\limits_{u\in
N(v_{2^{2}-1,1})}\epsilon(v_{2^{2}-1,1},u)$.

For $n=3$, Figure 2 shows that $\sum\limits_{u\in
N(v_{2^{3}-1,1})}\epsilon(v_{2^{3}-1,1},u)=15$, whilst Figure 3 shows that
$\varepsilon(G^{F^{{}^{\backepsilon}}}_{A^{(3)}}-v_{3,1})=13$. Therefore,
$\varepsilon(G^{F^{{}^{\backepsilon}}}_{A^{(3)}})<(2^{3}-2)+\sum\limits_{u\in
N(v_{2^{3}-1,1})}\epsilon(v_{2^{3}-1,1},u)$.

Now, consider the case $n=k$. Note that for any distinct pair of vertices
$v_{s,i}\neq v_{2^{k}-1,1}$, $v_{t,j}\neq v_{2^{k}-1,1}$ each edge
$v_{s,i}v_{t,j}$ which exists represents that, say $i^{\prime}\in
A^{(n)}_{s,i}$ and $j^{\prime}\in A^{(n)}_{t,j}$, such that
$i^{\prime}+j^{\prime}$ is a Fibonacci number. Since both
$i^{\prime},j^{\prime}\in A^{(n)}_{2^{k}-1,1}$, two edges
$v_{2^{k}-1,1}v_{s,i}$ and $v_{2^{k}-1,1}v_{t,j}$ must exist because of the
existence of edge $v_{s,i}v_{t,j}$. Therefore, the general result
$\varepsilon(G^{F^{{}^{\backepsilon}}}_{A^{(n)}})<(2^{n}-2)+\sum\limits_{u\in
N(v_{2^{n}-1,1})}\epsilon(v_{2^{n}-1,1},u)$, holds for $n\geq 2$ by induction.
∎

##  3 Conclusion

We know that a Fibonacci-sum graph $G^{F}_{n},\ n\geq 2$ is bipartite and
hence $\chi(G^{F}_{n})=2$, where $n\geq 2$ (see [1]). From Corollary 2.3 and
the fact that a Fibonacci-sum set-graph has an odd number of vertices imply
that for $n\geq 2$ an odd spanning cycle exists and therefore a Fibonacci-sum
set-graph is not $2$-colourable. We observe that the respective rainbow
neighbourhood numbers are
$r^{+}_{\chi}(G^{F}_{n})=r^{-}_{\chi}(G^{F}_{n})=2^{n}-1$ (see [6]). An
important invariant for further investigations and understanding of colouring
is the clique number $\omega(G)$. Determining this invariant for Fibonacci-sum
set-graphs is still open.

An eared clique is an induced complete subgraph of a graph $G$ with the loops
of each vertex and multiple edges which exist in $G$. The order of a largest
eared clique of a graph $G$ is called the eared clique number of $G$ and is
denoted by $\omega_{e}(G)$. Clearly
$\omega_{e}(G)=\omega(G^{{}^{\backepsilon}})$. When the context is clear the
invariant $\omega(G^{{}^{\backepsilon}})$ will be used.

######  Problem 1.

If possible, determine the eared clique number of the popped Fibonacci-sum
set-graph $\omega(G^{F^{{}^{\backepsilon}}}_{A^{(n)}})$.

######  Problem 2.

If possible, determine the chromatic number of the popped Fibonacci-sum set-
graph $G^{F^{{}^{\backepsilon}}}_{A^{(n)}}$.

######  Problem 3.

If possible, improve on the strict inequality of Proposition 2.9 for $n\geq
2$.

Beyond the limited study reported in this paper, the new notion of Fibonacci-
sum set-graphs offers a wide scope for further research. Similar integer
sequence-sum set-graphs such as the Lucas-sum set-graphs offer an interesting
new direction for research.

In particular, the idea of the set-graph of a graph $G$ of order $n$ comes to
the fore. Let $A^{(n)}=V(G)=\\{v_{i}:1\leq i\leq n\\}$ and define the set-
graph vertices as is understood from Definition 2.1. The set-graph of a graph
$G$, denoted by $G_{V(G)}$, has edges of the form $\\{v_{s,i}v_{t,j}\\}$ for
all $(v_{i^{\prime}},v_{j^{\prime}}),v_{i^{\prime}}\in A^{(n)}_{s,i}$ and
$v_{j^{\prime}}\in A^{(n)}_{t,j},v_{i^{\prime}}\neq v_{j^{\prime}}$ and edge
$v_{i^{\prime}}v_{j^{\prime}}\in E(G)\\}$. So, loops and multiple edges are
permitted. The study of the set-graph of a graph is open.

## References

  * [1] A. Arman, D.S. Gunderson and P.C. Li, Properties of the Fibonacci-sum graph, Preprint, arXiv:1710.10303v1, [math CO].
  * [2] J.A. Bondy and U.S.R. Murty, (2008). Graph theory, Springer, New York.
  * [3] K. Fox, W.B. Kinnersley, D. McDonald, N. Orlow and G.J. Puleo, (2014). Spanning paths in Fibonacci-sum graphs, Fibonacci Quart., 52,46–49.
  * [4] F. Harary, (2001). Graph theory, Narosa Publ. House, New Delhi.
  * [5] J. Kok, K.P. Chithra, N.K. Sudev and C. Susanth, (2015). A Study on Set-Graphs, Int. J. Computer Appl., Vol 118(7), 1–5.
  * [6] J. Kok and N.K. Sudev, On the rainbow neighbourhood numbers of set-graphs, Communicated.
  * [7] D.B. West, (2001). Introduction to graph theory, Prentice-Hall of India, New Delhi.


# Training Effective Neural Sentence Encoders from Automatically Mined
Paraphrases

Sławomir Dadas
National Information Processing Institute, Warsaw, Poland

###### Abstract

Sentence embeddings are commonly used in text clustering and semantic
retrieval tasks. State-of-the-art sentence representation methods are based on
artificial neural networks fine-tuned on large collections of manually labeled
sentence pairs. Sufficient amount of annotated data is available for high-
resource languages such as English or Chinese. In less popular languages,
multilingual models have to be used, which offer lower performance. In this
publication, we address this problem by proposing a method for training
effective language-specific sentence encoders without manually labeled data.
Our approach is to automatically construct a dataset of paraphrase pairs from
sentence-aligned bilingual text corpora. We then use the collected data to
fine-tune a Transformer language model with an additional recurrent pooling
layer. Our sentence encoder can be trained in less than a day on a single
graphics card, achieving high performance on a diverse set of sentence-level
tasks. We evaluate our method on eight linguistic tasks in Polish, comparing
it with the best available multilingual sentence encoders.

##  I Introduction

Using artificial neural networks for generating dense vector representations
of text has become a common practice in natural language processing (NLP).
While most research is focused on word and subword representations, some
applications require encoding larger chunks of text, such as sentences or
paragraphs. Neural sentence encoders are used in semantic search, question
answering, document clustering, dataset augmentation, plagiarism detection,
and other tasks which involve measuring semantic similarity between sentences.
Typically, these types of models are utilized for transforming text fragments
to their corresponding dense representations, which are then processed
independently by a vector search engine or other information retrieval system.
This allows billions of vectors to be compared and searched efficiently. The
quality of these representations, therefore, has a significant impact on the
performance of the whole system.

In recent years, a number of methods for encoding sentences have been
introduced. State-of-the-art models, producing high-quality vector
representations, are usually trained in a supervised way. Training
semantically meaningful representations, suitable for search and retrieval
problems, requires specific types of labeled datasets such as natural language
inference (NLI) or paraphrase pairs. Large datasets of manually labeled
sentence pairs exist only for high-resource languages. For English, SNLI [1]
and MultiNLI [2] datasets are available, among others, each with several
hundred thousand records. For other languages, there are either no NLI
datasets, or the size of existing datasets is insufficient for training high-
quality neural sentence encoders. Therefore, for low-resource languages,
multilingual or unsupervised sentence encoders need to be used, which offer
lower performance than the best methods trained for English.

This publication addresses this problem by proposing a method for training
effective language-specific sentence encoders without manually labeled data.
In the first step, we perform automatic extraction of paraphrase pairs in the
target language using a large corpus of parallel sentences from the OPUS
project [3]. Next, we fine-tune a siamese network composed of two Transformer-
based [4] language models on the collected data to discriminate paraphrases
from non-paraphrases. For fine-tuning, we employ an additional LSTM [5] (Long
Short-term Memory) layer as a pooling operation of which the last hidden state
is used as sentence representation. We show that it is possible to train a
neural sentence encoder for a lower resource language on a single GPU in under
24 hours, achieving better performance than state-of-the-art multilingual
models trained with significantly more data and compute power.

##  II Contributions

We make the following contributions in this work:

  1. 1.

We propose a framework for training neural sentence encoders which does not
require manually labeled data. Our method involves automatic extraction of
paraphrase pairs for a target language utilizing sentence-aligned cross-
lingual corpora. The resulting dataset is then used for fine-tuning
Transformer language model to produce high-quality dense representations of
sentences.

  2. 2.

Our architecture generates sentence vectors from an additional LSTM pooling
layer. Other popular Transformer-based sentence encoders use simple non-
parametric pooling operations such as mean or max pooling, which restrict the
dimension of the resulting vector. Using recurrent layer allows us to produce
arbitrarily sized sentence representations.

  3. 3.

We validate our approach on the Polish language. We conduct an evaluation on
eight tasks, including the following problems: paraphrase identification,
sentiment analysis, natural language inference, semantic relatedness, and
topic classification.

  4. 4.

For the purposes of the evaluation, we publish the Polish Paraphrase Corpus
(PPC). It is a new dataset consisting of 7000 manually labeled sentence pairs
from different sources, each assigned to one of three categories: exact
paraphrases, close paraphrases, non-paraphrases. Most of the examples have
high semantic overlap, which makes the task challenging for classification
models.

  5. 5.

We make the source code for paraphrase mining, model fine-tuning, and
evaluation publicly available111https://github.com/sdadas/polish-sentence-
evaluation. The code allows training sentence encoders and replicating our
results for any language.

##  III Related work

Since the popularization of word embedding models such as Word2Vec [6, 7],
GloVe [8], or FastText [9], there have been efforts to develop effective
vector representations for larger fragments of text. Early approaches employed
simple aggregation techniques of the individual word vectors, usually by
computing arithmetic or weighted mean. More advanced methods based on static
word representations have also been developed. Arora et al. [10] introduced
_Smooth Inverse Frequency (SIF)_ which included a weighted mean combined with
principal component analysis (PCE), Shen et al. [11] showed that concatenating
mean and max pooled vectors improves the quality of sentence embeddings.
Aggregation-based approaches offer intuitive and easy-to-use baselines, but
the quality of the resulting representations is inferior to more recent
models.

Most of the modern methods are based on artificial neural networks trained on
sentence-level optimization objective. Some of these models employ self-
supervised learning and can be trained using only raw text corpora, while
others are fully supervised and require labeled datasets for training. The
model proposed by Le and Mikolov [12] was one of the first self-supervised
approaches. It is a simple neural architecture for learning fixed-length
paragraph vectors from word embedding models. The network was trained to
predict the next word in the document from the representation of previously
encoded words. Skip-Thought vectors [13] is another notable example of self-
supervised methods. It is an encoder-decoder network in which the input
sentence is first encoded to a dense representation, and then the model is
expected to reconstruct the previous and the next sentence from the same
document. This method was followed by other similar architectures that
improved on the original model [14, 15]. Recent neural sentence encoders
typically do not involve optimizing the model from scratch, and they instead
rely on pre-trained language models, the most popular of which are
Transformer-based models. Latest self-supervised learning approaches propose
fine-tuning a language model using denoising or contrastive objectives. TSDAE
[16] tries to reconstruct the original sentence from a damaged input, SimCSE
[17] learns to identify two versions of the same sentence encoded with
different dropout masks, Contrastive Tension [18] trains two independent
models on a noise-contrastive task.

State-of-the-art sentence embedding models, achieving the highest performance
on semantic retrieval tasks, are optimized using supervised learning. Some of
the earlier popular models of this type include InferSent [19] and Universal
Sentence Encoder [20], both trained on the SNLI [1] corpus. Recently, several
new Transformer-based approaches to learning sentence encoders have been
developed as a part of the Sentence-Transformers
library222https://www.sbert.net/. Original method [21] is based on siamese
neural network architecture composed of two Transformer models with shared
parameters. Fine-tuning the network involves minimizing the distance between
representations for similar sentences and maximizing for different sentences.
The authors experimented with several loss functions, including cross-entropy
loss, mean squared error loss on cosine similarity between vectors, triplet
loss, multiple negatives ranking loss. The last one proved to produce the
highest quality sentence embeddings. Pre-trained models are provided along
with the library, the most recent of which were trained on a dataset of over
one billion English sentence pairs.

The availability of pre-trained models and labeled datasets of sentence pairs
is lower for languages other than English. Currently, the best option for
these languages is to use multilingual sentence encoders, which offer
reasonably good performance for semantic tasks. We can consider multilingual
models as a separate group of methods since they are usually learned in a
different way than the approaches described above. More specifically, these
models are trained using big cross-lingual text corpora, exploiting semantic
similarity between aligned sentence pairs in different languages. Since a
large volume of cross-lingual data is available on the Internet, training an
effective multilingual model is often computationally intensive and requires
at least several hundred gigabytes of text. In recent years, a few pre-trained
multilingual sentence encoders were published. Artetxe and Schwenk [22]
released LASER, neural sentence encoder which can handle 93 languages. A
multilingual version of Universal Sentence Encoder supporting 16 languages
[23] has also been made publicly available. LaBSE [24] is another popular
model, based on a multilingual BERT [25], fine-tuned for semantic retrieval
tasks in 112 languages. A different approach to training multilingual encoders
has been shown in Reimers and Gurevych [26]. The publication proposes a method
for transferring knowledge from a pre-trained English sentence encoder
(teacher) to a pre-trained multilingual language model (student) by minimizing
the distance between English sentence vector and sentence vectors
corresponding to translated sentences. This fine-tuning procedure requires
less data than training multilingual encoders from scratch. Several pre-
trained models created with this method have already been published in
Sentence-Transformers library.

Figure 1: A diagram showing our procedure for paraphrase extraction from a
bilingual corpus.

##  IV Methodology

In this section, we describe our approach to training Transformer-based
sentence encoders from automatically mined paraphrases. First, we characterize
our method of extracting paraphrase pairs from parallel corpora. Next, we
present the architecture of the neural model employed in this study and
describe the procedure of training the model on the collected data.

###  IV-A Paraphrase extraction

The main idea of our paraphrase extraction approach is to utilize sentence-
aligned cross-lingual text corpora. One of the largest available collections
of such corpora is the OPUS project [3], which contains several dozen datasets
covering almost all modern languages. In this study, two of them were used,
which proved to work best with our method - OpenSubtitles [27] and CCMatrix
[28]. They both include multiple alternative translations for the same
sentence, a characteristic that can be exploited for paraphrase mining.

A single run of our algorithm extracts paraphrased from a bilingual dataset.
First, we select the source and target language. The target language is the
one on which the model is trained, while the source language can be chosen
arbitrarily. Usually, it is preferred to use English as the source language
since most bilingual data is available for it. After downloading the sentence-
aligned corpus, we perform data filtering step using a pre-trained
multilingual sentence encoder. This step is necessary to improve the quality
of resulting paraphrases because the original corpus is often noisy,
containing translation errors and misaligned sentences. We compute the cosine
similarity between a pair of sentences and discard pairs that are below a
certain threshold. In our experiments, we used _paraphrase-xlm-r-
multilingual-v1_ model from the Sentence-Transformers library to filter the
data, and set a threshold of 0.7. In the next step, we group sentences in the
target language corresponding to the same source sentences. We can then
generate paraphrases from all groups containing at least two sentences. Within
each group, we randomly select sentence pairs such that the resulting pairs
contain at least one occurrence of each sentence. The dataset created in this
way can then be used to train a sentence encoder. The procedure described
above is shown in a graphical form in Figure 1.

###  IV-B Neural sentence encoder

Currently, a common approach to training sentence encoders is to use a pre-
trained language model such as BERT [25] or RoBERTa [29]. Such models already
contain sufficient semantic knowledge, and they only need to be fine-tuned to
efficiently encode representations of sentences for semantic retrieval tasks.
In this study, we employ an approach similar to the one proposed by Reimers et
al. [21]. We create a siamese network composed of two Transformer models with
tied weights, initialized with a pre-trained language model. This architecture
is then trained on a dataset of sentence pairs. Each Transformer network
independently produces a sentence vector, and the vectors are compared using a
similarity function. The sentence representation is generated by the model
from individual token embeddings using a pooling operation. Reimers et al.
[21] experimented with simple pooling strategies such as using the first
(_CLS_) token, computing the mean or max operation on all token vectors. These
pooling methods are fast to compute but have a significant drawback - they
restrict the size of the sentence embedding to be the same as the size of
token vectors.

We believe that higher-dimensional sentence representations would preserve
more semantic information, allowing higher performance on some tasks.
Therefore, we propose a pooling operation based on an additional LSTM layer.
The layer is placed after the last encoder block of the Transformer model. It
takes a sequence of token vectors as input and returns a single vector
representing the whole sentence. For the sentence embedding, we use the last
hidden state of the LSTM cell. The architecture of the proposed sentence
encoder is shown in Figure 2. This approach allows an arbitrary number of
dimensions to be set for the resulting sentence vector, since the size of the
LSTM cell does not depend on the size of the input.

Figure 2: The architecture of our neural sentence encoder. The model is based
on a standard Transformer architecture with an embedding layer and a number of
self-attention blocks. The input of the model is a sequence of tokens
$x_{1},...,x_{n}$, and the last of the encoder blocks outputs a vector
representation of each token $y_{1},...,y_{n}$. The sentence representation is
built from the individual token representations using an additional LSTM
layer. The last hidden state of the recurrent layer is used as sentence
embedding.

We fine-tune the model with mini-batch version of _AdamW_ [30] algorithm.
Every batch of size $K$ is composed of sentence pairs represented by their
embeddings encoded by the model:

$X=[(a_{1},b_{i}),(a_{2},b_{2}),...,(a_{K},b_{K})]$ (1)

Let us call the first sentence in each pair the _anchor_. The second sentence
in the same pair is its _positive_ sentence and the second sentences in all
other pairs are its _negative_ sentences. During training, every _anchor_
$a_{i}$ is compared to all representations $b_{1},b_{2},...,b_{K}$. We expect
the similarity of vectors to be high only for the positive pairs and low for
all other pairs. Specifically, we use multiple negatives ranking loss function
[31]:

$J(X,\theta)=-\frac{1}{K}\sum_{i=1}^{K}\Big{(}sim(a_{i},b_{i})-\log\sum_{j=1}^{K}e^{sim(a_{i},b_{j})}\Big{)}$
(2)

where X is the current mini-batch, $\theta$ denotes the model parameters, and
$sim(a_{i},b_{j})$ is a similarity function comparing sentence representations
$a_{i}$, $b_{j}$. In our case, the cosine similarity is used as the similarity
function, defined as follows:

$sim(x,y)=\frac{\sum_{i=1}^{n}x_{i}y_{i}}{\sqrt{\sum_{j=1}^{n}x_{j}^{2}}\sqrt{\sum_{j=1}^{n}y_{j}^{2}}}$
(3)

where both $x$ and $y$ are vectors, and $x_{i}$ denotes the $i$-th dimension
of $x$.

##  V Experiments

In this section, we demonstrate the results of our experiments. The method
presented in this paper was evaluated on eight linguistic tasks in Polish and
compared with other publicly available neural sentence encoders. In our
experiments, we follow the evaluation approach from SentEval [32] toolkit. The
evaluated sentence encoders are not fine-tuned for specific tasks, they are
only used to generate sentence embeddings. For each task, a simple neural
network with one hidden layer is trained, which takes these static sentence
representations as input and outputs a class label or regression score. For
classification tasks, we use accuracy as the evaluation metric. For semantic
relatedness, Spearman’s rank correlation coefficient is used.

For the purpose of our experiments, we created a new manually annotated
dataset for paraphrase identification: Polish Paraphrase Corpus. First, we
describe the corpus and the process of its development. Next, we present other
datasets used in the evaluation. Then we present a description of the neural
sentence encoders for Polish trained by us and other methods on which the
evaluation was performed. The section concludes with a discussion of the
results.

###  V-A Polish Paraphrase Corpus

Polish Paraphrase Corpus contains 7000 manually labeled sentence pairs. The
dataset was divided into training, validation and test splits. The training
part includes 5000 examples, while the other parts contain 1000 examples each.
The main purpose of creating such a dataset was to verify how machine learning
models perform in the challenging problem of paraphrase identification, where
most records contain semantically overlapping parts. Technically, this is a
three-class classification task, where each record can be assigned to one of
the following categories:

  * •

_Exact paraphrases_ \- Sentence pairs that convey exactly the same
information. We are interested only in the semantic meaning of the sentence,
therefore this category also includes sentences that are semantically
identical but, for example, have different emotional emphasis.

  * •

_Close paraphrases_ \- Sentence pairs with similar semantic meaning. In this
category we include all pairs which contain the same information, but in
addition to it there may be other semantically non-overlapping parts. This
category also contains context-dependent paraphrases - sentence pairs that may
have the same meaning in some contexts but are different in others.

  * •

_Non-paraphrases_ \- All other cases, including contradictory sentences and
semantically unrelated sentences.

The corpus contains 2911, 1297, and 2792 examples for the above three
categories, respectively. The process of annotating the dataset was preceded
by an automated generation of candidate pairs, which were then manually
labeled. We experimented with two popular techniques of generating possible
paraphrases: backtranslation with a set of neural machine translation models
and paraphrase mining using a pre-trained multilingual sentence encoder. The
extracted sentence pairs are drawn from different data sources: Taboeba333
https://tatoeba.org/, Polish news articles, Wikipedia and Polish version of
SICK dataset [33]. Since most of the sentence pairs obtained in this way fell
into the first two categories, in order to balance the dataset, some of the
examples were manually modified to convey different information. In this way,
even negative examples often have high semantic overlap, making this problem
difficult for machine learning models.

###  V-B Other datasets

Below we briefly describe the other datasets used in our experiments:

  * •

_Wroclaw Corpus of Consumer Reviews Sentiment (WCCRS)_ [34] \- A Polish
sentiment analysis dataset containing consumer reviews of products and
services, assigned to four classes: _positive_ , _negative_ , _neutral_ and
_ambiguous_. The corpus contains opinions relating to four domains: hotels,
medical services, products, and education. Two of those domains, hotels and
medical services, contain sentence-level annotations. We include them in our
evaluation as _Consumer Reviews - Hotels (CR-H)_ and _Consumer Reviews -
Medicine (CR-M)_ tasks.

  * •

_Sentences Involving Compositional Knowledge (SICK)_ [33] \- This corpus is a
manually translated version of English SICK dataset [35], containing 10,000
sentence pair with two types of annotations. Each pair contains a numerical
score of semantic relatedness between sentences, and additionally a natural
language inference (NLI) category label: _entailment_ , _neutral_ or
_contradiction_. We therefore include two evaluation tasks based on this
dataset: classification _(SICK-E)_ and regression _(SICK-R)_.

  * •

_Compositional Distributional Semantics (CDS)_ [36] \- A different corpus
using the same annotation format as SICK dataset. Like the original, this
corpus also contains 10,000 examples annotated with semantic relatedness score
and NLI label. As with the previously described dataset, we also include two
evaluation tasks in this case: _CDS-E_ and _CDS-R_.

  * •

_8TAGS_ [33] \- A collection of sentences relating to popular topics discussed
on the Internet. It contains about 50,000 sentences annotated with 8 topic
labels: _film_ , _history_ , _food_ , _medicine_ , _motorization_ , _work_ ,
_sport_ and _technology_. A multi-class classification task _(8TAGS)_ based on
this corpus was included in our experiments.

###  V-C Details of the experiments

Neural sentence encoders developed as part of this study were trained on an
automatically extracted collection of over 7 million sentence pairs. The
dataset was constructed by running our paraphrase mining algorithm on English-
Polish bilingual data from OpenSubtitles [27] and CCMatrix [28]. We trained
four neural architectures with different pooling layers. The first model was
based on standard mean pooling, while the other three employed pooling using
the LSTM layer with increasing cell memory size: 1024, 2048, and 4096. The
weights of all sentence encoders were initialized with a pre-trained Polish
RoBERTa base language model [37] and the same set of hyperparameters was used
for fine-tuning. We used a mini-batch size of 64. We employed a training
scheduler with a linearly decreasing learning rate and a warmup phase for the
first 10% update steps. The peak learning rate was set to $2\mathrm{e}{-6}$.
Each model was fine-tuned for three epochs, which took about 24-hours on a
single Nvidia V100 GPU.

All datasets used in the evaluation have separate training, validation, and
test parts. The results reported by us refer to the performance of the models
on the test split of each dataset. As in the case of SentEval [32], the
training part is used for training a single layer classifier on top of the
generated sentence embeddings, and the validation part is used for selecting
optimal regularization term for this classifier.

In addition to the models described in this paper, we test several other
neural sentence representations for Polish. We verify how the pre-trained
neural language models perform on sentence-level tasks without additional
fine-tuning on paraphrase data. For Polish, there are two high-quality models
that were included in our study, Polish RoBERTa [37] and HerBERT [38], each of
them available in base and large variants. We also test all available
multilingual models from Sentence-Transformers library, fine-tuned using
multilingual knowledge distillation method [26]. Finally, we include the other
commonly used neural sentence encoders: LASER [22], mUSE [23] and LaBSE [24].

###  V-D Results

TABLE I: Evaluation of sentence representations on eight tasks for Polish. For classification tasks we use accuracy as the evaluation metric, for semantic relatedness tasks (_CDSC-R_ and _SICK-R_) the Spearman’s rank correlation coefficient is used. |  |  Paraphrase identification |  Sentiment analysis |  Natural language inference |  Semantic relatedness |  Topic classification
---|---|---|---|---|---|---
Model | Avg. | PPC | CR-H | CR-M | CDSC-E | SICK-E | CDSC-R | SICK-R | 8TAGS
Pre-trained language models + mean pooling
Polish RoBERTa (base) | 75.13 | 70.60 | 85.14 | 79.21 | 81.40 | 71.89 | 79.53 | 62.26 | 71.00
HerBERT (base) | 75.58 | 67.10 | 86.62 | 82.32 | 84.80 | 68.55 | 83.66 | 56.86 | 74.70
Polish RoBERTa (large) | 76.64 | 65.40 | 87.90 | 83.56 | 82.60 | 68.59 | 83.89 | 61.84 | 79.30
HerBERT (large) | 78.84 | 66.40 | 87.58 | 83.31 | 84.90 | 75.13 | 85.27 | 69.19 | 78.91
Sentence encoders (Sentence-Transformers library)
paraphrase-multilingual-MiniLM-L12-v2 | 78.62 | 76.80 | 80.24 | 78.81 | 85.70 | 78.45 | 88.13 | 71.60 | 69.19
distilbert-multilingual-nli-stsb-quora-rank | 78.80 | 80.00 | 80.44 | 74.02 | 86.70 | 79.66 | 87.23 | 73.61 | 68.73
distiluse-base-multilingual-cased-v2 | 78.85 | 73.80 | 79.92 | 75.95 | 87.90 | 78.68 | 90.54 | 73.12 | 70.86
xlm-r-bert-base-nli-stsb-mean-tokens | 79.91 | 80.10 | 81.15 | 80.69 | 86.00 | 81.02 | 85.69 | 75.25 | 69.37
paraphrase-xlm-r-multilingual-v1 | 81.44 | 82.80 | 82.50 | 80.74 | 86.70 | 82.08 | 90.14 | 76.08 | 70.49
paraphrase-multilingual-mpnet-base-v2 | 81.72 | 81.30 | 85.46 | 82.67 | 86.70 | 79.49 | 89.95 | 75.68 | 72.51
Sentence encoders (other methods)
mUSE | 78.79 | 72.70 | 79.02 | 74.22 | 86.30 | 81.96 | 90.23 | 76.61 | 69.26
LASER | 80.07 | 80.10 | 81.21 | 78.12 | 87.90 | 82.21 | 89.30 | 76.65 | 65.07
LaBSE | 81.20 | 77.10 | 86.10 | 80.64 | 86.70 | 81.63 | 90.02 | 76.04 | 71.36
Our sentence encoder with different pooling layers
Mean pooling | 81.53 | 79.40 | 85.78 | 80.94 | 87.90 | 80.35 | 88.57 | 76.56 | 72.78
LSTM pooling (1024) | 81.74 | 80.00 | 85.07 | 81.38 | 86.90 | 80.55 | 89.46 | 77.40 | 73.19
LSTM pooling (2048) | 82.48 | 83.40 | 85.26 | 81.58 | 87.30 | 81.49 | 89.70 | 78.48 | 72.60
LSTM pooling (4096) | 82.52 | 82.50 | 86.49 | 81.04 | 86.90 | 82.39 | 90.06 | 78.99 | 71.75

The results of our experiments are shown in Table I. The table is divided into
four sections, each corresponding to specific groups of sentence encoding
methods. The first group includes pre-trained neural language models based on
the Transformer architecture. In this part of the evaluation, we utilized the
original model weights without fine-tuning them for encoding sentences. In
this case, sentence representation is constructed by aggregating individual
token vectors generated by the last layer of the network using mean pooling
operation. As we can see, these representations perform well on conventional
classification tasks such as sentiment analysis or topic classification but
perform considerably worse on tasks that require measuring semantic
relationship between sentences. On the _SICK_ , _CDSC_ and _PPC_ datasets, the
results are up to 13% lower compared to the other evaluated solutions.

The second group consists of sentence encoders from the Sentence-Transformers
library trained using multilingual knowledge distillation method [26]. These
models offer varying performance on Polish language tasks. However, two of
them stand out: _paraphrase-xlm-r-multilingual-v1_ and _paraphrase-
multilingual-mpnet-base-v2_. Both achieved an average score on all tasks above
81%. The former was particularly good on the semantic retrieval tasks while
scoring lower on typical classification tasks. The latter, on the other hand,
obtained balanced scores on all types of tasks.

Three popular neural sentence embedding methods published by Google and
Facebook are included in the third group. Each of them performs well on
semantic relatedness and natural language inference problems, while results on
the other tasks often fall short of the performance offered by competing
approaches. Of the three architectures compared, LaBSE performed best by
achieving an average score above 81%. Reasonable performance is also offered
by the LASER model with an average score of around 80%. However, in both cases
their results were lower than those of the best models available in the
Sentence-Transformers library.

The last section presents the results of our sentence encoders applying
different pooling methods. The model using standard mean pooling achieved an
average score of 81.53%, which is the second-best result in comparison to the
previously discussed methods. Models incorporating an additional layer of
LSTM-based pooling further improved this result. We can see that increasing
the dimension of the sentence embedding has a positive effect on model
performance. The difference is especially noticeable between LSTM layers with
a hidden size of 1024 and 2048, while increasing the dimension further brings
smaller improvements. The two largest models achieved an average score over
all tasks of about 82.5%. It is also worth noting that all our models offer
balanced performance across different tasks. On conventional classification
problems, only pre-trained language models perform better. Whereas on
paraphrase identification, natural language inference, and semantic
relatedness, our encoders perform just as well or better than the best
multilingual sentence encoders.

##  VI Conclusion

In this paper, we have proposed a method for training neural sentence encoders
without manually labeled data. Our approach involves automatic extraction of
paraphrase pairs from sentence-aligned bilingual text corpora. Such datasets
are readily available for many languages, so our technique is particularly
suitable for training models in low-resource languages for which there is
little or no annotated data. Using the extracted sentence pairs, we fine-tune
a language model based on the Transformer architecture with an additional
recurrent pooling layer responsible for generating sentence embeddings. The
method allows us to train an effective language-specific sentence encoder in a
short time on a single GPU, outperforming state-of-the-art multilingual models
whose training required significantly more computational resources.

We validated our approach on eight tasks for the Polish language. For
evaluation purposes, we also developed a new dataset that includes 7000
manually annotated sentence pairs, the Polish Paraphrase Corpus (PPC). Our
sentence embeddings have shown high quality on a variety of linguistic
problems, performing well both on semantic retrieval tasks and on sentence-
level classification tasks.

## References

  * Bowman et al. [2015] S. Bowman, G. Angeli, C. Potts, and C. D. Manning, “A large annotated corpus for learning natural language inference,” in _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , 2015, pp. 632–642.
  * Williams et al. [2018] A. Williams, N. Nangia, and S. Bowman, “A broad-coverage challenge corpus for sentence understanding through inference,” in _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , 2018, pp. 1112–1122.
  * Tiedemann [2012] J. Tiedemann, “Parallel data, tools and interfaces in opus,” in _Proceedings of the Eighth International Conference on Language Resources and Evaluation (LREC’12)_ , 2012, pp. 2214–2218.
  * Vaswani et al. [2017] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” in _Advances in neural information processing systems_ , 2017, pp. 5998–6008.
  * Hochreiter and Schmidhuber [1997] S. Hochreiter and J. Schmidhuber, “Long short-term memory,” _Neural computation_ , vol. 9, no. 8, pp. 1735–1780, 1997.
  * Mikolov et al. [2013a] T. Mikolov, K. Chen, G. S. Corrado, and J. Dean, “Efficient estimation of word representations in vector space,” _International Conference on Learning Representations_ , 2013.
  * Mikolov et al. [2013b] T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean, “Distributed representations of words and phrases and their compositionality,” _Neural Information Processing Systems_ , pp. 3111–3119, 2013.
  * Pennington et al. [2014] J. Pennington, R. Socher, and C. D. Manning, “Glove: Global vectors for word representation,” in _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_. Empirical Methods in Natural Language Processing, 2014, pp. 1532–1543.
  * Bojanowski et al. [2017] P. Bojanowski, E. Grave, A. Joulin, and T. Mikolov, “Enriching word vectors with subword information,” _Transactions of the Association for Computational Linguistics_ , pp. 135–146, 2017.
  * Arora et al. [2017] S. Arora, Y. Liang, and T. Ma, “A simple but tough-to-beat baseline for sentence embeddings,” in _ICLR 2017 : International Conference on Learning Representations 2017_. International Conference on Learning Representations, 2017.
  * Shen et al. [2018] D. Shen, G. Wang, W. Wang, M. R. Min, Q. Su, Y. Zhang, C. Li, R. Henao, and L. Carin, “Baseline needs more love: On simple word-embedding-based models and associated pooling mechanisms,” _Meeting of the Association for Computational Linguistics_ , pp. 440–450, 2018.
  * Le and Mikolov [2014] Q. Le and T. Mikolov, “Distributed representations of sentences and documents,” in _International conference on machine learning_. PMLR, 2014, pp. 1188–1196.
  * Kiros et al. [2015] R. Kiros, Y. Zhu, R. R. Salakhutdinov, R. S. Zemel, A. Torralba, R. Urtasun, and S. Fidler, “Skip-thought vectors,” _Neural Information Processing Systems_ , pp. 3294–3302, 2015.
  * Gan et al. [2017] Z. Gan, Y. Pu, R. Henao, C. Li, X. He, and L. Carin, “Learning generic sentence representations using convolutional neural networks,” in _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_. Empirical Methods in Natural Language Processing, 2017, pp. 2390–2400.
  * Logeswaran and Lee [2018] L. Logeswaran and H. Lee, “An efficient framework for learning sentence representations,” _International Conference on Learning Representations_ , 2018.
  * Wang et al. [2021] K. Wang, N. Reimers, and I. Gurevych, “TSDAE: Using transformer-based sequential denoising auto-encoderfor unsupervised sentence embedding learning,” in _Findings of the Association for Computational Linguistics: EMNLP 2021_. Punta Cana, Dominican Republic: Association for Computational Linguistics, Nov. 2021, pp. 671–688.
  * Gao et al. [2021] T. Gao, X. Yao, and D. Chen, “SimCSE: Simple contrastive learning of sentence embeddings,” in _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_. Online and Punta Cana, Dominican Republic: Association for Computational Linguistics, Nov. 2021, pp. 6894–6910.
  * Carlsson et al. [2021] F. Carlsson, A. C. Gyllensten, E. Gogoulou, E. Y. Hellqvist, and M. Sahlgren, “Semantic re-tuning with contrastive tension,” in _International Conference on Learning Representations_ , 2021.
  * Conneau et al. [2017] A. Conneau, D. Kiela, H. Schwenk, L. Barrault, and A. Bordes, “Supervised learning of universal sentence representations from natural language inference data,” in _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_. Empirical Methods in Natural Language Processing, 2017, pp. 670–680.
  * Cer et al. [2018] D. Cer, Y. Yang, S.-y. Kong, N. Hua, N. L. U. Limtiaco, R. S. John, N. Constant, M. Guajardo-Céspedes, S. Yuan, C. Tar, Y.-h. Sung, B. Strope, and R. Kurzweil, “Universal sentence encoder,” _arXiv preprint arXiv:1803.11175_ , 2018.
  * Reimers et al. [2019] N. Reimers, I. Gurevych, N. Reimers, I. Gurevych, N. Thakur, N. Reimers, J. Daxenberger, I. Gurevych, N. Reimers, I. Gurevych _et al._ , “Sentence-bert: Sentence embeddings using siamese bert-networks,” in _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics, 2019.
  * Artetxe and Schwenk [2019] M. Artetxe and H. Schwenk, “Massively Multilingual Sentence Embeddings for Zero-Shot Cross-Lingual Transfer and Beyond,” _Transactions of the Association for Computational Linguistics_ , vol. 7, pp. 597–610, 09 2019.
  * Yang et al. [2020] Y. Yang, D. Cer, A. Ahmad, M. Guo, J. Law, N. Constant, G. Hernandez Abrego, S. Yuan, C. Tar, Y.-h. Sung, B. Strope, and R. Kurzweil, “Multilingual universal sentence encoder for semantic retrieval,” in _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations_. Online: Association for Computational Linguistics, Jul. 2020, pp. 87–94.
  * Feng et al. [2020] F. Feng, Y. Yang, D. Cer, N. Arivazhagan, and W. Wang, “Language-agnostic bert sentence embedding,” _arXiv preprint arXiv:2007.01852_ , 2020.
  * Devlin et al. [2019] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “BERT: Pre-training of deep bidirectional transformers for language understanding,” in _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_. Minneapolis, Minnesota: Association for Computational Linguistics, Jun. 2019, pp. 4171–4186.
  * Reimers and Gurevych [2020] N. Reimers and I. Gurevych, “Making monolingual sentence embeddings multilingual using knowledge distillation,” in _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_. Online: Association for Computational Linguistics, Nov. 2020, pp. 4512–4525.
  * Lison and Tiedemann [2016] P. Lison and J. Tiedemann, “OpenSubtitles2016: Extracting large parallel corpora from movie and TV subtitles,” in _Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC’16)_. Portorož, Slovenia: European Language Resources Association (ELRA), May 2016, pp. 923–929.
  * Schwenk et al. [2021] H. Schwenk, G. Wenzek, S. Edunov, E. Grave, A. Joulin, and A. Fan, “CCMatrix: Mining billions of high-quality parallel sentences on the web,” in _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_. Online: Association for Computational Linguistics, Aug. 2021, pp. 6490–6500.
  * Liu et al. [2019] Y. Liu, M. Ott, N. Goyal, J. Du, M. Joshi, D. Chen, O. Levy, M. Lewis, L. Zettlemoyer, and V. Stoyanov, “Roberta: A robustly optimized bert pretraining approach,” _arXiv preprint arXiv:1907.11692_ , 2019.
  * Loshchilov and Hutter [2019] I. Loshchilov and F. Hutter, “Decoupled weight decay regularization,” in _International Conference on Learning Representations_ , 2019.
  * Henderson et al. [2017] M. Henderson, R. Al-Rfou, B. Strope, Y.-H. Sung, L. Lukács, R. Guo, S. Kumar, B. Miklos, and R. Kurzweil, “Efficient natural language response suggestion for smart reply,” _ArXiv_ , vol. abs/1705.00652, 2017.
  * Conneau and Kiela [2018] A. Conneau and D. Kiela, “SentEval: An evaluation toolkit for universal sentence representations,” in _Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC 2018)_. Miyazaki, Japan: European Language Resources Association (ELRA), May 2018.
  * Dadas et al. [2020a] S. Dadas, M. Perełkiewicz, and R. Poświata, “Evaluation of sentence representations in Polish,” in _Proceedings of the 12th Language Resources and Evaluation Conference_. Marseille, France: European Language Resources Association, May 2020, pp. 1674–1680.
  * Kocoń et al. [2019] J. Kocoń, M. Zaśko-Zielińska, and P. Miłkowski, “Multi-level analysis and recognition of the text sentiment on the example of consumer opinions,” in _Proceedings of the International Conference Recent Advances in Natural Language Processing, RANLP 2019_ , 2019.
  * Marelli et al. [2014] M. Marelli, S. Menini, M. Baroni, L. Bentivogli, R. bernardi, and R. Zamparelli, “A sick cure for the evaluation of compositional distributional semantic models,” in _Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC’14)_. Language Resources and Evaluation, 2014, pp. 216–223.
  * Wróblewska and Krasnowska-Kieraś [2017] A. Wróblewska and K. Krasnowska-Kieraś, “Polish evaluation dataset for compositional distributional semantics models,” in _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_. Vancouver, Canada: Association for Computational Linguistics, Jul. 2017, pp. 784–792.
  * Dadas et al. [2020b] S. Dadas, M. Perełkiewicz, and R. Poświata, “Pre-training polish transformer-based language models at scale,” in _International Conference on Artificial Intelligence and Soft Computing_. Springer, 2020, pp. 301–314.
  * Mroczkowski et al. [2021] R. Mroczkowski, P. Rybak, A. Wróblewska, and I. Gawlik, “HerBERT: Efficiently pretrained transformer-based language model for Polish,” in _Proceedings of the 8th Workshop on Balto-Slavic Natural Language Processing_. Kiyv, Ukraine: Association for Computational Linguistics, Apr. 2021, pp. 1–10.