#  Arithmetic-Geometric Spectral Radius of Trees and Unicyclic Graphs

Ruiling Zheng, Xian${}^{{}^{\textbf{,}}}$an Jin
School of Mathematical Sciences, Xiamen University, Xiamen 361005, P. R. China
E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The arithmetic-geometric matrix $A_{ag}(G)$ of a graph $G$ is a square matrix,
where the $(i,j)$-entry is equal to
$\displaystyle\frac{d_{i}+d_{j}}{2\sqrt{d_{i}d_{j}}}$ if the vertices $v_{i}$
and $v_{j}$ are adjacent, and 0 otherwise. The arithmetic-geometric spectral
radius of $G$, denoted by $\rho_{ag}(G)$, is the largest eigenvalue of the
arithmetic-geometric matrix $A_{ag}(G)$. Let $S_{n}$ be the star of order
$n\geq 3$ and $S_{n}+e$ be the unicyclic graph obtained from $S_{n}$ by adding
an edge. In this paper, we prove that for any tree $T$ of order $n\geq 2$,

$\displaystyle
2\cos\frac{\pi}{n+1}\leq\rho_{ag}(P_{n})\leq\rho_{ag}(T)\leq\rho_{ag}(S_{n})=\frac{n}{2},$

with equality if and only if $T\cong P_{n}$ for the lower bound, and if and
only if $T\cong S_{n}$ for the upper bound. We also prove that for any
unicyclic graph $G$ of order $n\geq 3$,

$\displaystyle 2=\rho_{ag}(C_{n})\leq\rho_{ag}(G)\leq\rho_{ag}(S_{n}+e),$

the lower (upper, respectively) bound is attained if and only if $T\cong
C_{n}$ ($T\cong S_{n}+e$, respectively) and
$\displaystyle\rho_{ag}(S_{n}+e)<\frac{n}{2}$ for $n\geq 7$.

Keywords: Arithmetic-geometric matrix; Arithmetic-geometric spectral radius;
Tree; Unicyclic graph

##  1 Introduction

Throughout this paper we consider finite, undirected and simple graphs. Let
$G$ be a graph with vertex set $V(G)=\\{v_{1},v_{2},\ldots,v_{n}\\}$ and edge
set $E(G)$. An edge $e\in E(G)$ with end vertices $v_{i}$ and $v_{j}$ is
denoted by $v_{i}v_{j}$. For $i=1,2,\ldots,n$, we denote by $d_{i}$ the degree
of the vertex $v_{i}$ in $G$. As usual, let $P_{n}$, $S_{n}$ and $C_{n}$ be
the path, the star and the cycle of order $n\geq 3$. Let $S_{n}+e$ with $n\geq
3$ denote the unicyclic graph obtained from $S_{n}$ by adding an edge. The
spectral radius of a complex matrix $M$ is the largest value among the modules
of all eigenvalues of $M$. In the case that $M$ is real symmetric, its
spectral radius is exactly the largest eigenvalue and we denote it by
$\displaystyle\rho(M)$. The spectral radius of the adjacency matrix
$A(G)=(a_{i,j})$ of $G$ is referred as the spectral radius of $G$.

In 1975, a so-called Randić index was proposed[18], it is defined as

$\displaystyle R_{-1}(G)=\sum\limits_{v_{i}v_{j}\in
E(G)}\frac{1}{d_{i}d_{j}}.$

The Randić matrix $R(G)=(r_{i,j})$ of $G$, where $\displaystyle
r_{i,j}=\frac{1}{d_{i}d_{j}}$ if $v_{i}v_{j}\in E(G)$ and 0 otherwise, seems
to be first time used in 2005 by Rodríguez, who referred to it as the
“weighted adjacency matrix” [19] and the “degree adjacency matrix” [20].
Moreover, the role of Randić matrix in the Laplacian theory was clarified in
[3, 2]. The Randić spectral radius was studied in [14, 17, 3, 2] and the
references cited therein.

In 1994, Yang et al.[24] proposed the extended matrix of $G$, denoted by
$A_{ex}(G)=(c_{i,j})$, where $\displaystyle
c_{i,j}=\frac{1}{2}\Big{(}\frac{d_{i}}{d_{j}}+\frac{d_{j}}{d_{i}}\Big{)}$ if
$v_{i}v_{j}\in E(G)$ and $0$ otherwise. The corresponding topological index is
the symmetric division deg index, which is proposed by Vukičević[22] and
written as

$\displaystyle SDD(G)=\sum\limits_{v_{i}v_{j}\in
E(G)}\Big{(}\frac{d_{i}}{d_{j}}+\frac{d_{j}}{d_{i}}\Big{)}.$

The extended spectral radius were studied in [1, 9, 23] and the references
cited therein.

In 1998, Estrada, Torres, Rodríguez and Gutman[11] introduced the atom-bond
connectivity $(ABC)$ index, defined as

$\displaystyle ABC(G)=\sum\limits_{v_{i}v_{j}\in
E(G)}\sqrt{\frac{d_{i}+d_{j}-2}{d_{i}d_{j}}}.$

The ABC matrix of G, put forward by Estrada[10], is defined to be
$\Omega(G)=(\omega_{i,j})$, where
$\displaystyle\omega_{i,j}=\sqrt{\frac{d_{i}+d_{j}-2}{d_{i}d_{j}}}$ if
$v_{i}v_{j}\in E(G)$ and $0$ otherwise. Chen [7] showed that for any tree $T$
of order $n\geq 3$,

$\displaystyle\sqrt{2}\cos\frac{\pi}{n+1}\leq\rho(\Omega(T))\leq\sqrt{n-2},$

with left (right, respectively) equality if and only if $T\cong P_{n}$(
$T\cong S_{n}$, respectively), which was conjectured in[6]. Recently, Li and
Wang[16] proved that for an unicyclic graph $G$ of order $n\geq 4$,

$\displaystyle\sqrt{2}=\rho(\Omega(C_{n}))\leq\rho(\Omega(G))\leq\rho(\Omega(S_{n}+e)),$

with equality if and only if $T\cong C_{n}$ for the lower bound, and if and
only if $T\cong S_{n}+e$ for the upper bound, which was conjectured in[12].
Yuan and Du characterized the bicyclic graphs with the largest and second
largest $ABC$ spectral radius, which are just the unique two bicyclic graphs
of order $n$ with maximum degree $n-1$ for $n\geq 7$[25].

In 2015, Shegehall and Kanabur[21] proposed the arithmetic-geometric index of
$G$, which is defined as

$\displaystyle AG(G)=\sum\limits_{v_{i}v_{j}\in
E(G)}\frac{d_{i}+d_{j}}{2\sqrt{d_{i}d_{j}}}.$

Recently, Zheng et al.[26] considered the arithmetic-geometric matrix (AG
matrix) of $G$, denoted by $A_{ag}(G)=(h_{i,j})$, where $\displaystyle
h_{i,j}=\frac{d_{i}+d_{j}}{2\sqrt{d_{i}d_{j}}}$ if $v_{i}v_{j}\in E(G)$ and 0
otherwise. We denote $\rho(A_{ag}(G))$ by $\rho_{ag}(G)$, and call it the
arithmetic-geometric spectral radius ($AG$ spectral radius) of $G$. Moreover,
Zheng et al.[26] gave several bounds for the AG spectral radius in terms of
the maximum degree, the minimum degree of $G$, the Randić index $\displaystyle
R_{-1}(G)$ and the first Zagreb index $M_{1}(G)=\sum\limits_{v_{i}v_{j}\in
E}(d_{i}+d_{j})$. Guo and Gao [13] offered several other bounds for the $AG$
spectral radius as well.

In this paper, we consider the $AG$ spectral radius of trees and unicyclic
graphs. We prove that: (1) for any tree $T$ of order $n\geq 2$,

$\displaystyle
2\cos\frac{\pi}{n+1}\leq\rho_{ag}(P_{n})\leq\rho_{ag}(T)\leq\rho_{ag}(S_{n})=\frac{n}{2},$

with equality if and only if $T\cong P_{n}$ for the lower bound, and if and
only if $T\cong S_{n}$ for the upper bound.

(2) for any unicyclic graph $G$ of order $n\geq 3$,

$\displaystyle 2=\rho_{ag}(C_{n})\leq\rho_{ag}(G)\leq\rho_{ag}(S_{n}+e),$

the lower (upper, respectively) bound is attained if and only if $T\cong
C_{n}$ ($T\cong S_{n}+e$, respectively) and
$\displaystyle\rho_{ag}(S_{n}+e)<\frac{n}{2}$ for $n\geq 7$.

##  2 Lemmas

Lemma 2.1[15] Let $M$ ba a nonnegative matrix of order $n$. Let x be a
positive column vector of dimension $n$, i.e. every entry is positive. If
$k>0$ such that $M\textbf{x}\leq k\textbf{x}$, then $\rho(M)\leq k$.

Lemma 2.2[15] Let $B=(b_{ij})$ and $D=(d_{ij})$ be two nonnegative matrices of
order $n$. If $B\geq D$, i.e., $b_{ij}\geq d_{ij}\geq 0$ for all $i,j$, then
$\rho(B)\geq\rho(D)$.

Lemma 2.3[15] For any principle submatrix $M^{\prime}$ of a nonnegative matrix
$M$ of order $n$, $\rho(M^{\prime})\leq\rho(M)$.

Let $DT(p,q)$ denote the double star obtained by joining the center of
$K_{1,p}$ to that of $K_{1,q}$, which is depicted in Fig. 1. The following
Lemma was due to Chang and Huang[5].

Fig. 1. The double star $DT(p,q).$

Lemma 2.4 For two integers $p,q$ with $p\geq q\geq 1$,

$\displaystyle\rho(A(DT(p,q)))=\sqrt{\frac{p+q+1+\sqrt{(p+q+1)^{2}-4pq}}{2}}.$

Lemma 2.5[4] If $G$ is an unicyclic graph, then

$\displaystyle 2=\rho(A(C_{n}))\leq\rho(A(G))\leq\rho(A(S_{n}+e)),$

the lower bound is attained if and only if $G\cong C_{n}$, the upper bound is
obtained if and only if $G\cong S_{n}+e$.

Lemma 2.6[8] Let $\displaystyle\Phi(P_{n};\lambda)$ be the characteristic
polynomial of $P_{n}$. Then

$\displaystyle\Phi(P_{n};\lambda)=\frac{1}{\sqrt{\lambda^{2}-4}}\Big{(}x_{1}^{n+1}-x_{2}^{n+1}\Big{)}$,

where $\displaystyle
x_{1}=\frac{1}{2}\Big{(}\lambda+\sqrt{\lambda^{2}-4}\Big{)}$ and
$\displaystyle x_{2}=\frac{1}{2}\Big{(}\lambda-\sqrt{\lambda^{2}-4}\Big{)}$
are the roots of the equation $x^{2}-\lambda x+1=0.$

Zheng et al.[26] gave the following upper bound for the AG spectral radius of
graphs with order $n\geq 2$ and size $m$.

Lemma 2.7[26] Let $G$ be a graph of order $n\geq 2$ and size $m$. Then

$\displaystyle\rho_{ag}(G)\leq\frac{1}{2}\Big{(}\sqrt{n-1}+\frac{1}{\sqrt{n-1}}\Big{)}\sqrt{2m-n+1},$

where the equality holds if and only if $G\cong S_{n}$.

##  3 The $AG$ spectral radius of trees

Theorem 3.1. If $T$ is a tree of order $n\geq 2$, then

$\displaystyle
2\cos\frac{\pi}{n+1}<\rho_{ag}(P_{n})\leq\rho_{ag}(T)\leq\rho_{ag}(S_{n})=\frac{n}{2},$

with equality if and only if $T\cong P_{n}$ for the lower bound, and if and
only if $T\cong S_{n}$ for the upper bound.

Proof. If $n=2,3$, then it is obvious. Now we suppose that $n\geq 4$.
According to Lemma 2.7, it follows that

$\displaystyle\rho_{ag}(T)\leq\rho_{ag}(S_{n})=\frac{n}{2},$

we get the upper bound.

Then it suffices to show that for any tree $T\ncong P_{n}$,

$\displaystyle 2\cos\frac{\pi}{n+1}<\rho_{ag}(P_{n})<2\leq\rho_{ag}(T).$

We first prove that $\displaystyle 2\leq\rho_{ag}(T)$. If $T\ncong P_{n}$,
then it has at least one vertex of degree greater than 2. We consider the
following two cases.

Case 1. $T$ has two adjacent vertices of degree greater than 2.

Without loss of generality, we assume that $v_{p}v_{q}$ is an edge of $G$ such
that $d_{p}\geq d_{q}\geq 3$. Clearly, $DT:=DT(d_{p}-1,d_{q}-1)$ is an induced
subgraph of $T$. Let $\displaystyle h(x,y)=\frac{x+y}{2\sqrt{xy}}$, then
$\displaystyle h(x,y)\geq 1$ for $x,y>0$. By Lemma 2.2, We get
$\displaystyle\rho_{ag}(T)\geq\rho(A(T))$. And by Lemmas 2.3, 2.4, we have

$\displaystyle\rho_{ag}(T)\geq\rho(A(T))\geq\rho(A(DT))=\sqrt{\frac{d_{p}+d_{q}-1+\sqrt{(d_{p}+d_{q}-1)^{2}-4(d_{p}-1)(d_{q}-1)}}{2}}.$

Then we just need to prove that

$\displaystyle\sqrt{\frac{d_{p}+d_{q}-1+\sqrt{(d_{p}+d_{q}-1)^{2}-4(d_{p}-1)(d_{q}-1)}}{2}}\geq
2$ for $d_{p}\geq d_{q}\geq 3$.

Since $d_{p}\geq d_{q}\geq 3$, we obtain

$\displaystyle d_{p}+d_{q}-1+\sqrt{(d_{p}+d_{q}-1)^{2}-4(d_{p}-1)(d_{q}-1)}$

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\geq$5+$\sqrt{(d_{p}+d_{q}-1)^{2}-4(d_{p}-1)(d_{q}-1)}$

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
=5+\sqrt{(d_{p}-d_{q})^{2}+2d_{p}+2d_{q}-3}$

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \geq
5+\sqrt{2d_{p}+2d_{q}-3}$

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \geq 5+3=8$.

Hence

$\displaystyle\sqrt{\frac{d_{p}+d_{q}-1+\sqrt{(d_{p}+d_{q}-1)^{2}-4(d_{p}-1)(d_{q}-1)}}{2}}\geq
2$.

Case 2. $T$ has no two adjacent vertices of degree greater than 2.

In this case, because $T\ncong P_{n}$, then $T$ has at least one vertex of
degree greater than 2 and its adjacent vertices must be of degree 2 or 1.
Obviously, we obtain that $K_{1,3}$ is an induced subgraph of $T$.

If $n=4$, then $T\cong K_{1,3}$, and by Lemma 2.7, we have $\rho_{ag}(T)=2$.

We now assume that $n\geq 5$. Then $T$ contains $T_{1}$ or $T_{2}$ (as shown
in Fig. 2) as its induced subgraph.

Fig. 2. The trees $T_{1}$ and $T_{2}$.

Subcase 2.1 If $T_{1}$ is an induced subgraph of $T$, then
$\displaystyle\rho_{ag}(T)\geq\rho(A(T))\geq\rho(A(T_{1}))$. Since

$A(T_{1})=\left(\begin{array}[]{ccccc}0&1&1&1&1\\\ 1&0&0&0&0\\\ 1&0&0&0&0\\\
1&0&0&0&0\\\ 1&0&0&0&0\\\ \end{array}\right).$

A routine computation gives rise to $\rho(A(T_{1}))=2$. Then
$\displaystyle\rho_{ag}(T)\geq\rho(A(T_{1}))=2$.

Subcase 2.2 If $T$ contains $T_{2}$ as its induced subgraph.

If $n=5$, then $T\cong T_{2}$ and

$A_{ag}(T_{2})=\left(\begin{array}[]{ccccc}0&\frac{2\sqrt{3}}{3}&\frac{2\sqrt{3}}{3}&\frac{5\sqrt{6}}{12}&0\\\
\frac{2\sqrt{3}}{3}&0&0&0&0\\\ \frac{2\sqrt{3}}{3}&0&0&0&0\\\
\frac{5\sqrt{6}}{12}&0&0&0&\frac{3\sqrt{2}}{4}\\\
0&0&0&\frac{3\sqrt{2}}{4}&0\\\ \end{array}\right).$

By computation, we obtain $\displaystyle\rho_{ag}(T)=\rho_{ag}(T_{2})\approx
2.0253>2$.

If $n\geq 6$, then $T$ contains $T_{21}$ or $T_{22}$ (as shown in Fig. 3) as
its induced subgraph.

Fig. 3. The trees $T_{21}$ and $T_{22}$.

Subcase 2.2.1 $T_{21}$ is an induced subgraph of $T$. If $d_{2}=2$, then
$T_{3}$, which is depicted in Fig. 4, is an induced subgraph of $T$.

Fig. 4. The tree $T_{3}$.

By directly calculation, we obtain
$\displaystyle\rho_{ag}(T)\geq\rho(A(T))\geq\rho(A(T_{3}))=2$.

If $d_{2}=1$, by $\displaystyle h(x,y)\geq 1=h(2,2)$ and Lemmas 2.2,2.3, we
get $\rho_{ag}(T)\geq\rho(A_{ag}^{\prime}(T_{4}))$. The “graph” $T_{4}$ is
shown in Fig. 5, where $d_{5}=2$, $d_{6}=2$,
$V(T_{4})=\\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}\\}$ and
$E(T_{4})=\\{v_{1}v_{2},v_{1}v_{3},v_{1}v_{4},v_{4}v_{5},v_{3}v_{6}\\}$. The
matrix $A_{ag}^{\prime}(T_{4})=(h_{i,j})$, where $\displaystyle
h_{i,j}=\frac{d_{i}+d_{j}}{2\sqrt{d_{i}d_{j}}}$ if $v_{i}v_{j}\in E(T_{4})$
and 0 otherwise.

Fig. 5. The tree $T_{4}$.

We have

$A_{ag}^{\prime}(T_{4})=\left(\begin{array}[]{ccccccc}0&\frac{2\sqrt{3}}{3}&\frac{5\sqrt{6}}{12}&\frac{5\sqrt{6}}{12}&0&0\\\
\frac{2\sqrt{3}}{3}&0&0&0&0&0\\\ \frac{5\sqrt{6}}{12}&0&0&0&0&1\\\
\frac{5\sqrt{6}}{12}&0&0&0&1&0\\\ 0&0&0&1&0&0\\\ 0&0&1&0&0&0\\\
\end{array}\right),$

then $\displaystyle\rho_{ag}(T)\geq\rho(A_{ag}^{\prime}(T_{4}))\thickapprox
2.0226>2$.

Subcase 2.2.2 $T_{22}$ is an induced subgraph of $T$.

If $d_{5}\geq 3$, then $T_{5}$, which is depicted in Fig. 6, is an induced
subgraph of $T$.

Fig. 6. The tree $T_{5}$.

We acquire $\displaystyle\rho_{ag}(T)\geq\rho(A(T))\geq\rho(A(T_{5}))=2$.

If $d_{5}=2$, thanks to $d_{1}\geq 3$, then $d_{2},d_{3}=1$ or $2$,
respectively.

If $d_{2}=2$ and $d_{3}=2$, then $T_{6}$(as shown in Fig. 7) is an induced
subgraph of $T$.

Fig. 7. The tree $T_{6}$.

We obtain $\displaystyle\rho_{ag}(T)\geq\rho(A(T))\geq\rho(A(T_{6}))\approx
2.0285>2$.

If $d_{2}=1$ and $d_{3}=2$ or $d_{2}=2$ and $d_{3}=1$. Without loss of
generality, we let $d_{2}=1$ and $d_{3}=2$. Due to $\displaystyle h(x,y)\geq
1=h(2,2)$ for $x,y\geq 1$ and Lemmas 2.2,2.3, we get
$\rho_{ag}(T)\geq\rho(A_{ag}^{\prime}(T_{7}))$. The “graph” $T_{7}$ is shown
in Fig. 8, where $d_{6}=2$, $d_{7}=2$,
$V(T_{7})=\\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\\}$ and
$E(T_{7})=\\{v_{1}v_{2},v_{1}v_{3},v_{1}v_{4},v_{4}v_{5},v_{5}v_{6},v_{3}v_{7}\\}$.
The matrix $A_{ag}^{\prime}(T_{7})=(h_{i,j})$, where $\displaystyle
h_{i,j}=\frac{d_{i}+d_{j}}{2\sqrt{d_{i}d_{j}}}$ if $v_{i}v_{j}\in E(T_{7})$
and 0 otherwise.

Fig. 8. The tree $T_{7}$.

By simply calculation, we get
$\displaystyle\rho_{ag}(T)\geq\rho(A_{ag}^{\prime}(T_{7}))\thickapprox
2.0523>2$.

If $d_{2}=1$ and $d_{3}=1$, then
$\rho_{ag}(T)\geq\rho(A_{ag}^{\prime}(T_{8}))\thickapprox 2.0457>2$, where the
“graph” $T_{8}$ is shown in Fig. 9.

Fig. 9. The tree $T_{8}$.

It remains to show that $\displaystyle
2\cos\frac{\pi}{n+1}<\rho_{ag}(P_{n})<2$. The arithmetic-geometric matrix of
$P_{n}$ can be written as

$A_{ag}(P_{n})=\begin{pmatrix}0&\frac{3\sqrt{2}}{4}&0&0&\ldots&0&0&0&0\\\
\frac{3\sqrt{2}}{4}&0&1&0&\ldots&0&0&0&0\\\ 0&1&0&1&\ldots&0&0&0&0\\\
0&0&1&0&\ldots&0&0&0&0\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots\\\
0&0&0&0&\ldots&0&1&0&0\\\ 0&0&0&0&\ldots&1&0&1&0\\\
0&0&0&0&\ldots&0&1&0&\frac{3\sqrt{2}}{4}\\\
0&0&0&0&\ldots&0&0&\frac{3\sqrt{2}}{4}&0\\\ \end{pmatrix}.$

$f(\rho,n)=det(\rho
E_{n}-A_{ag}(P_{n}))=\begin{vmatrix}\rho&-\frac{3\sqrt{2}}{4}&0&0&\ldots&0&0&0&0\\\
-\frac{3\sqrt{2}}{4}&\rho&-1&0&\ldots&0&0&0&0\\\
0&-1&\rho&-1&\ldots&0&0&0&0\\\ 0&0&-1&\rho&\ldots&0&0&0&0\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots\\\
0&0&0&0&\ldots&\rho&-1&0&0\\\ 0&0&0&0&\ldots&-1&\rho&-1&0\\\
0&0&0&0&\ldots&0&-1&\rho&-\frac{3\sqrt{2}}{4}\\\
0&0&0&0&\ldots&0&0&-\frac{3\sqrt{2}}{4}&\rho\\\ \end{vmatrix}.$

If $\displaystyle\rho=2$, by directly calculation, we obtain $\displaystyle
f(2,n)=\frac{49n}{64}+\frac{77}{64}>0.$

If $\displaystyle\rho>2$, then by Lemma 2.6, we obtain

$\displaystyle f(\rho,n)$ $\displaystyle=$
$\displaystyle\rho^{2}\Phi(P_{n-2};\rho)-\frac{9}{4}\rho\Phi(P_{n-3};\rho)+\Big{(}\frac{9}{8}\Big{)}^{2}\Phi(P_{n-4};\rho)$
$\displaystyle=$
$\displaystyle\frac{1}{2^{n-3}\sqrt{\rho^{2}-4}}\Big{\\{}\Big{(}\frac{\rho}{2}\Big{)}^{2}\Big{[}\Big{(}\rho+\sqrt{\rho^{2}-4}\Big{)}^{n-1}-\Big{(}\rho-\sqrt{\rho^{2}-4}\Big{)}^{n-1}\Big{]}-\frac{9\rho}{8}\Big{[}\Big{(}\rho+\sqrt{\rho^{2}-4}\Big{)}^{n-2}$
$\displaystyle-$
$\displaystyle\Big{(}\rho-\sqrt{\rho^{2}-4}\Big{)}^{n-2}\Big{]}+\Big{(}\frac{9}{8}\Big{)}^{2}\Big{[}\Big{(}\rho+\sqrt{\rho^{2}-4}\Big{)}^{n-3}-\Big{(}\rho-\sqrt{\rho^{2}-4}\Big{)}^{n-3}\Big{]}\Big{\\}}.$

Now it suffices to prove that

$\displaystyle g(\rho,n)$ $\displaystyle=$
$\displaystyle\Big{(}\frac{\rho}{2}\Big{)}^{2}\Big{[}\Big{(}\rho+\sqrt{\rho^{2}-4}\Big{)}^{n-1}-\Big{(}\rho-\sqrt{\rho^{2}-4}\Big{)}^{n-1}\Big{]}-\frac{9\rho}{8}\Big{[}\Big{(}\rho+\sqrt{\rho^{2}-4}\Big{)}^{n-2}$
$\displaystyle-$
$\displaystyle\Big{(}\rho-\sqrt{\rho^{2}-4}\Big{)}^{n-2}\Big{]}+\Big{(}\frac{9}{8}\Big{)}^{2}\Big{[}\Big{(}\rho+\sqrt{\rho^{2}-4}\Big{)}^{n-3}-\Big{(}\rho-\sqrt{\rho^{2}-4}\Big{)}^{n-3}\Big{]}>0$

for $\rho>2$.

If $\displaystyle\frac{\rho(\rho-\sqrt{\rho^{2}-4})}{2}-\frac{9}{8}>0$, then

$\displaystyle\Big{[}\frac{\rho(\rho+\sqrt{\rho^{2}-4})}{2}-\frac{9}{8}\Big{]}^{2}>\Big{[}\frac{\rho(\rho-\sqrt{\rho^{2}-4})}{2}-\frac{9}{8}\Big{]}^{2}$.

If $\displaystyle\frac{\rho(\rho-\sqrt{\rho^{2}-4})}{2}-\frac{9}{8}\leq 0$,
then

$\displaystyle\frac{\rho(\rho+\sqrt{\rho^{2}-4})}{2}-\frac{9}{8}+\frac{\rho(\rho-\sqrt{\rho^{2}-4})}{2}-\frac{9}{8}=\rho^{2}-\frac{9}{4}>0$.

Thus we also have
$\displaystyle\Big{[}\frac{\rho(\rho+\sqrt{\rho^{2}-4})}{2}-\frac{9}{8}\Big{]}^{2}>\Big{[}\frac{\rho(\rho-\sqrt{\rho^{2}-4})}{2}-\frac{9}{8}\Big{]}^{2}$.

Then for $\displaystyle\rho>2$, we obtain

$\displaystyle(\rho+\sqrt{\rho^{2}-4})^{n-3}\Big{[}\frac{\rho(\rho+\sqrt{\rho^{2}-4})}{2}-\frac{9}{8}\Big{]}^{2}$

$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
>(\rho-\sqrt{\rho^{2}-4})^{n-3}\Big{[}\frac{\rho(\rho+\sqrt{\rho^{2}-4})}{2}-\frac{9}{8}\Big{]}^{2}$

$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
>(\rho-\sqrt{\rho^{2}-4})^{n-3}\Big{[}\frac{\rho(\rho-\sqrt{\rho^{2}-4})}{2}-\frac{9}{8}\Big{]}^{2}$.

It follows that

$\displaystyle(\rho+\sqrt{\rho^{2}-4})^{n-3}\Big{[}\Big{(}\frac{\rho}{2}\Big{)}^{2}(\rho+\sqrt{\rho^{2}-4})^{2}-\frac{9\rho}{8}(\rho+\sqrt{\rho^{2}-4})+\Big{(}\frac{9}{8}\Big{)}^{2}\Big{]}$

$\displaystyle\ \ \ \ \ \ \
>(\rho-\sqrt{\rho^{2}-4})^{n-3}\Big{[}\Big{(}\frac{\rho}{2}\Big{)}^{2}(\rho-\sqrt{\rho^{2}-4})^{2}-\frac{9\rho}{8}(\rho-\sqrt{\rho^{2}-4})+\Big{(}\frac{9}{8}\Big{)}^{2}\Big{]}$.

That is $\displaystyle g(\rho,n)>0$.

Because for $P_{n}$, $\displaystyle A_{ag}(P_{n})>A(P_{n})$, then we have
$\displaystyle\rho_{ag}(P_{n})>\rho(A(P_{n}))=2\cos\frac{\pi}{n+1}$.

$\Box$

##  4 The $AG$ spectral radius of unicyclic graphs

Theorem 4.1. Let $G$ be an unicyclic of order $n\geq 3$, then

$\displaystyle 2=\rho_{ag}(C_{n})\leq\rho_{ag}(G)\leq\rho_{ag}(S_{n}+e)$

with equality if and only if $T\cong C_{n}$ for the lower bound, and if and
only if $T\cong S_{n}+e$ for the upper bound and
$\displaystyle\rho_{ag}(S_{n}+e)<\frac{n}{2}$ for $n\geq 7$.

Proof. If $n=3$, it is manifest. For any unicyclic graph $G$ of order $n\geq
4$, from Lemmas 2.2, 2.5 and $\displaystyle h(x,y)\geq h(2,2)=1$ for $x,y\geq
1$, we have
$\displaystyle\rho_{ag}(G)\geq\rho(A(G))\geq\rho(A(C_{n}))=\rho_{ag}(C_{n})=2.$
This leads to the lower bound.

Our task now is to consider the upper bound. The approximate values of
$\rho_{ag}$ of unicyclic graphs with order $4\leq n\leq 7$ are given in Tables
1-4 which are shown in the Appendix 1. It is obvious that $S_{n}+e$ has the
largest $AG$ spectral radius and
$\displaystyle\rho_{ag}(S_{7}+e)<\frac{n}{2}$.

For $n\geq 8$, according to Lemma 2.1, if we find a vector
$\textbf{x}>\textbf{0}$ such that $\displaystyle
A_{ag}(G)\textbf{x}\leq\frac{n-1}{2}\textbf{x}$, then
$\displaystyle\rho_{ag}(G)\leq\frac{n-1}{2}$. Let $x_{i}=\sqrt{d_{i}}$.

Suppose that any pair of adjacent vertices $v_{i},v_{j}\in G$, we have
$d_{i}+d_{j}\leq n-1$, then for any vertex $v_{i}$,

$\displaystyle(A_{ag}(G)\textbf{x})_{i}=\sum_{j=1,i\sim
j}^{n}\frac{d_{i}+d_{j}}{2\sqrt{d_{i}d_{j}}}\cdot\sqrt{d_{j}}=\sum_{j=1,i\sim
j}^{n}\frac{d_{i}+d_{j}}{2\sqrt{d_{i}}}\leq\frac{n-1}{2\sqrt{d_{i}}}\cdot
d_{i}=\frac{n-1}{2}\cdot\sqrt{d_{i}}$.

It follows that $\displaystyle\rho_{ag}(G)\leq\frac{n-1}{2}$.

Next we assume that there exist a pair of adjacent vertices $v_{i},v_{j}$ such
that $d_{i}+d_{j}\geq n$. By the proof of Conjecture 1 in [16], we know if $G$
exists two adjacent vertices $v_{i},v_{j}$ such that $d_{i}+d_{j}\geq n$, then
$G\in\\{\mathcal{G}_{1},\mathcal{G}_{2},\mathcal{G}_{3},\mathcal{G}_{4},\mathcal{G}_{5}\\}$(as
shown in Fig. 10).

Fig. 10. The graphs
$\mathcal{G}_{1},\mathcal{G}_{2},\mathcal{G}_{3},\mathcal{G}_{4},\mathcal{G}_{5}$.

The graphs ${G}_{1},{G}_{2},{G}_{3},{G}_{4}$ shown in Fig. 11 will be used in
the following.

Fig. 11. The graphs ${G}_{1},{G}_{2},{G}_{3},{G}_{4}$.

Let $G\in\mathcal{G}_{1}$ and $G\ncong G_{1},G_{2}$, then $d_{1}+d_{2}=n+1$
and $4\leq d_{1},d_{2}\leq n-3$.

For the pendent vertex $v$,

$\displaystyle(A_{ag}(G)\textbf{x})_{v}=\frac{1+d_{i}}{2\sqrt{d_{i}}}\cdot\sqrt{d_{i}}=\frac{1+d_{i}}{2}<\frac{n-1}{2}$
for $i=1,2$.

For the vertex $v_{1}$,

$\displaystyle(A_{ag}(G)\textbf{x})_{v_{1}}$ $\displaystyle=$
$\displaystyle(d_{1}-2)\cdot\frac{1+d_{1}}{2\sqrt{d_{1}}}+\frac{d_{1}+d_{2}}{2\sqrt{d_{1}d_{2}}}\cdot\sqrt{d_{2}}+\frac{d_{1}+2}{2\sqrt{2d_{1}}}\cdot\sqrt{2}$
$\displaystyle=$
$\displaystyle\frac{(d_{1}-2)(1+d_{1})}{2\sqrt{d_{1}}}+\frac{d_{1}+d_{2}}{2\sqrt{d_{1}}}+\frac{d_{1}+2}{2\sqrt{d_{1}}}$
$\displaystyle=$
$\displaystyle\frac{(d_{1}-2)(1+d_{1})+2d_{1}+d_{2}+2}{2\sqrt{d_{1}}}=\frac{d_{1}^{2}+n+1}{2\sqrt{d_{1}}}$
$\displaystyle\leq$
$\displaystyle\frac{(n-1)d_{1}}{2\sqrt{d_{1}}}=\frac{n-1}{2}\cdot\sqrt{d_{1}}.$

Similarly, for the vertex $v_{2}$, we have

$\displaystyle(A_{ag}(G)\textbf{x})_{v_{2}}\leq\frac{(n-1)}{2}\cdot\sqrt{d_{2}}$.

For the vertex $v_{3}$,

$\displaystyle(A_{ag}(G)\textbf{x})_{v_{3}}=\frac{2+d_{1}}{2\sqrt{2d_{1}}}\cdot\sqrt{d_{1}}+\frac{2+d_{2}}{2\sqrt{2d_{2}}}\cdot\sqrt{d_{2}}=\frac{4+d_{1}+d_{2}}{2\sqrt{2}}=\frac{n+5}{2\sqrt{2}}\leq\frac{n-1}{2}\cdot\sqrt{2}$.

Thus $\displaystyle(A_{ag}(G)\textbf{x})_{i}\leq\frac{n-1}{2}x_{i}$ holds for
all vertices in $G\in\mathcal{G}_{1}$ and $G\ncong G_{1},G_{2}$.

The proof of $G\in\mathcal{G}_{2}$ and $G\ncong G_{2}$, $G\in\mathcal{G}_{3}$
and $G\ncong G_{3}$, $G\in\mathcal{G}_{4}$ and $G\ncong G_{3}$ or
$G\in\mathcal{G}_{5}$ and $G\ncong G_{5}$ is quite similar to that given for
the case of $G\in\mathcal{G}_{1}$ and $G\ncong G_{1},G_{2}$ and given in the
Appendix 1.

Then it remains to prove that
$\displaystyle\rho_{ag}(G_{2}),\rho_{ag}(G_{3}),\rho_{ag}(G_{4})<\frac{n-1}{2}<\rho_{ag}(G_{1})<\frac{n}{2}$.

$A_{ag}(G_{1})=\begin{pmatrix}0&\frac{n+1}{2\sqrt{2(n-1)}}&\frac{n+1}{2\sqrt{2(n-1)}}&\frac{n}{2\sqrt{n-1}}&\ldots&\frac{n}{2\sqrt{n-1}}&\frac{n}{2\sqrt{n-1}}\\\
\frac{n+1}{2\sqrt{2(n-1)}}&0&1&0&\ldots&0&0\\\
\frac{n+1}{2\sqrt{2(n-1)}}&1&0&0&\ldots&0&0\\\
\frac{n}{2\sqrt{n-1}}&0&0&0&\ldots&0&0\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
\frac{n}{2\sqrt{n-1}}&0&0&0&\ldots&0&0\\\
\frac{n}{2\sqrt{n-1}}&0&0&0&\ldots&0&0\\\ \end{pmatrix}.$

Its arithmetic-geometric characteristic polynomial $g_{1}(\rho,n)=det(\rho
E_{n}-A_{ag}(G_{1}))$

$=\begin{vmatrix}\rho&-\frac{n+1}{2\sqrt{2(n-1)}}&-\frac{n+1}{2\sqrt{2(n-1)}}&-\frac{n}{2\sqrt{n-1}}&\ldots&-\frac{n}{2\sqrt{n-1}}&-\frac{n}{2\sqrt{n-1}}\\\
-\frac{n+1}{2\sqrt{2(n-1)}}&\rho&-1&0&\ldots&0&0\\\
-\frac{n+1}{2\sqrt{2(n-1)}}&-1&\rho&0&\ldots&0&0\\\
-\frac{n}{2\sqrt{n-1}}&0&0&\rho&\ldots&0&0\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
-\frac{n}{2\sqrt{n-1}}&0&0&0&\ldots&\rho&0\\\
-\frac{n}{2\sqrt{n-1}}&0&0&0&\ldots&0&\rho\\\ \end{vmatrix}$

$\displaystyle\ \ \ \ \ \ \ \
=\rho^{n-4}(\rho+1)\Big{[}\rho^{3}-\rho^{2}-\frac{n^{3}-2n^{2}+2n+1}{4(n-1)}\rho+\frac{(n-3)n^{2}}{4(n-1)}\Big{]}$.

Let $\displaystyle
t_{1}(\rho,n)=\rho^{3}-\rho^{2}-\frac{n^{3}-2n^{2}+2n+1}{4(n-1)}\rho+\frac{(n-3)n^{2}}{4(n-1)}$,
denoted by $\displaystyle\rho_{1}\geq\rho_{2}\geq\rho_{3}$ the three roots of
$\displaystyle t_{1}(\rho,n)=0$. Obviously, $\rho_{1}=\rho_{ag}$, i.e., the
desired result is equivalent to
$\displaystyle\frac{n-1}{2}<\rho_{1}<\frac{n}{2}$. From $\displaystyle
t_{1}(0,n)=\frac{(n-3)n^{2}}{4(n-1)}>0$,

$\displaystyle
t_{1}\Big{(}\frac{n-1}{2},n\Big{)}=\frac{(n-1)^{4}-2(n-1)^{3}-(n-1)(n^{3}-2n^{2}+2n+1)+2n^{2}(n-3)}{8(n-1)}$

$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
=\frac{-n^{3}+2n^{2}-9n+4}{8(n-1)}<0$ for $n\geq 8$.

and

$\displaystyle
t_{1}\Big{(}\frac{n}{2},n\Big{)}=\frac{(n-1)n^{3}-2n^{2}(n-1)-n(n^{3}-2n^{2}+2n+1)+2n^{2}(n-3)}{8(n-1)}$

$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ =\frac{n^{3}-6n^{2}-n}{8(n-1)}>0$
for $n\geq 8$.

It follows that $\displaystyle\frac{n-1}{2}<\rho_{1}<\frac{n}{2}$, i.e.,
$\displaystyle\frac{n-1}{2}<\rho_{ag}(G_{1})<\frac{n}{2}$.

Similarly we obtain the arithmetic-geometric characteristic polynomial
$g_{i}(\rho,n)$ of $G_{i}(i=2,3,4)$ as below $(1)$ $\displaystyle
g_{2}(\rho,n)=\frac{\rho^{n-4}}{4(n-2)}\Big{[}4(n-2)\rho^{4}-\frac{6n^{3}-31n^{2}+115n-136}{6}\rho^{2}-\frac{5n^{2}+5n}{6}\rho+\frac{2n^{2}}{3}$

$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
+\frac{19(n-4)(n-1)^{2}}{8}\Big{]}$;

$(2)$ $\displaystyle
g_{3}(\rho,n)=\frac{\rho^{n-6}}{8(n-2)}\Big{\\{}8(n-2)\rho^{6}-(2n^{3}-11n^{2}+39n-44)\rho^{4}-2n^{2}\rho^{3}+\Big{[}\frac{13n^{2}}{4}+9(n-2)+$

$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\frac{17}{4}(n-5)(n-1)^{2}\Big{]}\rho^{2}+\frac{9}{4}n^{2}\rho-\frac{9}{4}(n-5)(n-1)^{2}\Big{\\}}$;

$(3)$ $\displaystyle
g_{4}(\rho,n)=\frac{\rho^{n-4}}{8(n-2)}[8(n-2)\rho^{4}-(2n^{3}-10n^{2}+34n-40)\rho^{2}+4(n-4)(n-1)^{2}]$.

For $\displaystyle\rho\geq\frac{n-1}{2}$ and $n\geq 14$, we acquire

(1) $\displaystyle(4n-9)\rho^{4}>\frac{6n^{3}-31n^{2}+115n-136}{6}\rho^{2}$
and $\displaystyle\rho^{4}>\frac{5n^{2}+5n}{6}\rho$, then $\displaystyle
g_{2}(\rho,n)>0$;

(2) $\displaystyle(8n-18)\rho^{6}>(2n^{3}-11n^{2}+39n-44)\rho^{4}$,
$\displaystyle 9(n-2)\rho^{2}+\frac{9}{4}n^{2}\rho>\frac{9}{4}(n-5)(n-1)^{2}$
and

$\displaystyle\rho^{6}>n^{2}\rho^{3}$, then $\displaystyle g_{3}(\rho,n)>0$;

(3) $\displaystyle 8(n-2)\rho^{4}>(2n^{3}-10n^{2}+34n-40)\rho^{2}$, then
$\displaystyle g_{4}(\rho,n)>0$.

For $8\leq n\leq 13$, we can easily vertify that $\displaystyle
g_{2}(\rho,n),g_{3}(\rho,n)$ and $\displaystyle g_{4}(\rho,n)>0$ for
$\displaystyle\rho\geq\frac{n-1}{2}$.

$\Box$

## Acknowledgments

This work is supported by NSFC (No. 11671336) and the Fundamental Research
Funds for the Central Universities (No. 20720190062).

## References

  * [1] C. Adiga and B. R. Rakshith.  Upper bounds for the extended energy of graphs and some extended equienergetic graphs.  Opuscula Math., 38(1):5–13, 2018.
  * [2] S. B. Bozkur, A. D. Güngör, and I. Gutman.  Randić spectral radius and Randić energy.  MATCH Commun. Math. Comput. Chem., 64(2):321–334, 2010.
  * [3] S. B. Bozkurt and A. D. Güngör.  Randić matrix and Randić energy.  MATCH Commun. Math. Comput. Chem., 64(1):239–250, 2010.
  * [4] R. A. Brualdi and E. S. Solheid.  On the spectral radius of connected graphs.  Publ. Inst. Math. (Beograd), 39(53):45–54, 1986.
  * [5] A. Chang and Q. Huang.  Ordering trees by their largest eigenvalues.  Lin. Algebra. Appl, 370:175–184, 2003.
  * [6] X. Chen.  On $ABC$ eigenvalues and $ABC$ energy.  Lin. Algebra. Appl, 544:141–157, 2018.
  * [7] X. Chen.  On extremality of $ABC$ spectral radius of a tree.  Lin. Algebra. Appl, 564:159–169, 2019.
  * [8] D. Cvetković, M. Doob, and H. Sachs.  Spectra of graphs.  Academic Press, New York-London, 1980.
  * [9] K. C. Das, I. Gutman, and B. Furtula.  On spectral radius and energy of extended adjacency matrix of graphs.  Appl. Math. Comput., 296:116–123, 2017.
  * [10] E. Estrada.  The ABC matrix.  J. Math. Chem., 55(4):1021–1033, 2017.
  * [11] E. Estrada, L. Torres, L. Rodríguez, and I. Gutman.  An atom-bond connectivity index: Modelling the enthalpy of formation of alkanes.  Indian J. Chem, 37(10):849–855, 1998.
  * [12] M. Ghorbani, X. Li, M. Hakimi-Nezhaad, and J. Wang.  Bounds on the $ABC$ spectral radius and $ABC$ energy of graphs.  Lin. Algebra. Appl, 598:145–164, 2020.
  * [13] X. Guo and Y. Gao.  Arithmetic-geometric spectral radius and energy of graphs.  MATCH Commun. Math. Comput. Chem., 83:651–660, 2020.
  * [14] I. Gutman, B. Furtula, and S. B. Bozkurt.  On Randić energy.  Lin. Algebra. Appl, 442:50–57, 2014.
  * [15] R. A. Horn and C. R. Johnson.  Matrix analysis.  Cambridge University Press, Cambridge, 1990.
  * [16] X. Li and J. Wang.  On the ABC spectra radius of unicyclic graphs.  Lin. Algebra. Appl, 596:71–81, 2020.
  * [17] B. Liu, Y. Huang, and J. Feng.  A note on the Randić spectral radius.  MATCH Commun. Math. Comput. Chem., 68(3):913–916, 2012.
  * [18] M. Randić.  On characterization of molecular branching.  J. Am. Chem. Soc., 97(23):6609–6615, 1975.
  * [19] J. A. Rodríguez.  A spectral approach to the Randić index.  Lin. Algebra. Appl, 400:339–344, 2005.
  * [20] J. A. Rodríguez and J. M. Sigarreta.  On the Randić index and conditional parameters of a graph.  MATCH Commun. Math. Comput. Chem., 54(2):403–416, 2005.
  * [21] V. S. Shegehall and R. Kanabur.  Arithmetic-geometric indices of path graph.  J. Math. Comput. Sci, 6:19–24, 01 2015.
  * [22] D. Vukičević.  Bond additive modeling 2. mathematical properties of max-min rodeg index.  Croat. Chem. Acta, 83(3):261–273, 2010.
  * [23] B. Xu, S. Li, R. Yu, and Q. Zhao.  On the spectral radius and energy of the weighted adjacency matrix of a graph.  Appl. Math. Comput., 340:156–163, 2019.
  * [24] Y. Yang, L. Xu, and C. Y. Hu.  Extended adjacency matrix indices and their applications.  J Chem Inf Comput Sci, 34:1140–1145, 1994.
  * [25] Y. Yuan and Z. Du.  The first two maximum ABC spectral radii of bicyclic graphs.  Lin. Algebra. Appl, 615:28–41, 2021.
  * [26] L. Zheng, G. X. Tian, and S. Y. Cui.  On spectral radius and energy of arithmetic-geometric matrix of graphs.  MATCH Commun. Math. Comput. Chem., 83:635–650, 2020.

$\displaystyle\bf Appendix$ $\displaystyle 1$

The unicyclic graph G | $\displaystyle\rho_{ag}(G)$ | The unicyclic graph G | $\displaystyle\rho_{ag}(G)$
---|---|---|---
|  2 |  | 2.2536
Table 1: The approximate value of $\rho_{ag}$ of the unicyclic graph with order $n=4$ The unicyclic graph G | $\displaystyle\rho_{ag}(G)$ | The unicyclic graph G | $\displaystyle\rho_{ag}(G)$
---|---|---|---
|  2 |  | 2.2066
| 2.2543 |  | 2.4149
| 2.6035 |  |
Table 2: The approximate value of $\rho_{ag}$ of the unicyclic graph with order $n=5$ The unicyclic graph G | $\displaystyle\rho_{ag}(G)$ | The unicyclic graph G | $\displaystyle\rho_{ag}(G)$
---|---|---|---
|  2 |  | 2.1785
| 2.2096 |  | 2.2632
| 2.3439 |  | 2.3452
| 2.3551 |  | 2.4095
| 2.5275 |  | 2.5295
| 2.5695 |  | 2.6879
| 3.0113 |  |
Table 3: The approximate value of $\rho_{ag}$ of the unicyclic graph with
order $n=6$

The unicyclic graph G | $\displaystyle\rho_{ag}(G)$ | The unicyclic graph G | $\displaystyle\rho_{ag}(G)$
---|---|---|---
|  2 |  | 2.1602
| 2.1827 |  | 2.2188
| 2.2661 |  | 2.2942
| 2.3041 |  | 2.3094
| 2.316 |  | 2.3413
| 2.3428 |  | 2.3528
| 2.4044 |  | 2.4135
| 2.4473 |  | 2.4732
| 2.4908 |  | 2.499
| 2.5202 |  | 2.5376
| 2.5727 |  | 2.5962
| 2.5992 |  | 2.6023
| 2.6209 |  | 2.6564
| 2.6795 |  | 2.75
| 2.8717 |  | 2.9314
| 2.9516 |  | 3.0453
| 3.4526 |  |

Table 4: The approximate value of $\rho_{ag}$ of the unicyclic graph with
order $n=7$

Suppose that $n\geq 8$, the proof of $G\in\mathcal{G}_{2}$ and $G\ncong
G_{2}$, $G\in\mathcal{G}_{3}$ and $G\ncong G_{3}$, $G\in\mathcal{G}_{4}$ and
$G\ncong G_{3}$ or $G\in\mathcal{G}_{5}$ and $G\ncong G_{5}$ in Theorem 4.1 is
given in the following.

(1) If $G\in\mathcal{G}_{2}$ and $G\ncong G_{2}$, then $d_{1}+d_{2}=n$ and
$3\leq d_{1},d_{2}\leq n-3$.

For the vertex $v_{1}$,

$\displaystyle(A_{ag}(G)\textbf{x})_{v_{1}}$ $\displaystyle=$
$\displaystyle(d_{1}-2)\cdot\frac{1+d_{1}}{2\sqrt{d_{1}}}+\frac{d_{1}+d_{2}}{2\sqrt{d_{1}d_{2}}}\cdot\sqrt{d_{2}}+\frac{d_{1}+3}{2\sqrt{3d_{1}}}\cdot\sqrt{3}$
$\displaystyle=$
$\displaystyle\frac{d_{1}^{2}+n+1}{2\sqrt{d_{1}}}\leq\frac{(n-1)d_{1}}{2\sqrt{d_{1}}}=\frac{(n-1)}{2}\cdot\sqrt{d_{1}}.$

Similarly, for the vertex $v_{2}$, we get
$\displaystyle(A_{ag}(G)\textbf{x})_{v_{2}}\leq\frac{(n-1)\sqrt{d_{2}}}{2}$.

For the vertex $v_{3}$,

$\displaystyle(A_{ag}(G)\textbf{x})_{v_{3}}$ $\displaystyle=$
$\displaystyle\frac{3+d_{1}}{2\sqrt{3d_{1}}}\cdot\sqrt{d_{1}}+\frac{3+d_{2}}{2\sqrt{3d_{2}}}\cdot\sqrt{d_{2}}+\frac{1+3}{2\sqrt{3}}=\frac{10+d_{1}+d_{2}}{2\sqrt{3}}=\frac{n+10}{2\sqrt{3}}$
$\displaystyle=$
$\displaystyle\frac{n+10}{6}\cdot\sqrt{3}<\frac{n-1}{2}\cdot\sqrt{d_{3}}.$

Then $\displaystyle(A_{ag}(G)\textbf{x})_{i}<\frac{n-1}{2}x_{i}$ holds for all
vertices in $G\in\mathcal{G}_{2}$ and $G\ncong G_{2}$.

(2) If $G\in\mathcal{G}_{3}$ and $G\ncong G_{3}$, then $d_{1}+d_{2}=n$ and
$3\leq d_{1},d_{2}\leq n-3$.

For the vertex $v_{1}$,

$\displaystyle(A_{ag}(G)\textbf{x})_{v_{1}}$ $\displaystyle=$
$\displaystyle(d_{1}-2)\cdot\frac{1+d_{1}}{2\sqrt{d_{1}}}+\frac{d_{2}+d_{1}}{2\sqrt{d_{1}d_{2}}}\cdot\sqrt{d_{2}}+\frac{d_{1}+2}{2\sqrt{2d_{1}}}\cdot\sqrt{2}$
$\displaystyle=$
$\displaystyle\frac{d_{1}^{2}+n}{2\sqrt{d_{1}}}<\frac{(n-1)d_{1}}{2\sqrt{d_{1}}}=\frac{(n-1)\sqrt{d_{1}}}{2}.$

For the vertex $v_{2}$,

$\displaystyle(A_{ag}(G)\textbf{x})_{v_{2}}$ $\displaystyle=$
$\displaystyle(d_{2}-3)\cdot\frac{1+d_{2}}{2\sqrt{d_{2}}}+\frac{d_{2}+d_{1}}{2\sqrt{d_{2}d_{1}}}\cdot\sqrt{d_{1}}+2\cdot\frac{d_{2}+2}{2\sqrt{2d_{2}}}\cdot\sqrt{2}$
$\displaystyle=$
$\displaystyle\frac{d_{2}^{2}+n+1}{2\sqrt{d_{2}}}\leq\frac{(n-1)d_{2}}{2\sqrt{d_{2}}}=\frac{(n-1)\sqrt{d_{2}}}{2}.$

For the vertex $v_{3}$,

$\displaystyle(A_{ag}(G)\textbf{x})_{v_{3}}$ $\displaystyle=$
$\displaystyle\frac{2+d_{1}}{2\sqrt{2d_{1}}}\cdot\sqrt{d_{1}}+\frac{2+d_{2}}{2\sqrt{2d_{2}}}\cdot\sqrt{d_{2}}$
$\displaystyle=$
$\displaystyle\frac{4+d_{1}+d_{2}}{2\sqrt{2}}=\frac{4+n}{2\sqrt{2}}<\frac{n-1}{2}\cdot\sqrt{d_{3}}.$

For the vertex $v_{4}$,

$\displaystyle\ \ \
(A_{ag}(G)\textbf{x})_{v_{4}}=\frac{2+d_{2}}{2\sqrt{2d_{2}}}\cdot\sqrt{d_{2}}+\frac{1+2}{2\sqrt{2}}=\frac{5+d_{2}}{2\sqrt{2}}<\frac{n-1}{2}\cdot\sqrt{d_{4}}$.

Then $\displaystyle(A_{ag}(G)\textbf{x})_{i}<\frac{n-1}{2}x_{i}$ holds for all
vertices in $G\in\mathcal{G}_{3}$ and $G\ncong G_{3}$.

(3) If $G\in\mathcal{G}_{4}$ and $G\ncong G_{3}$, then $d_{1}+d_{2}=n$ and
$3\leq d_{1},d_{2}\leq n-3$.

For the vertex $v_{1}$,

$\displaystyle(A_{ag}(G)\textbf{x})_{v_{1}}$ $\displaystyle=$
$\displaystyle(d_{1}-1)\cdot\frac{1+d_{1}}{2\sqrt{d_{1}}}+\frac{d_{2}+d_{1}}{2\sqrt{d_{1}d_{2}}}\cdot\sqrt{d_{2}}$
$\displaystyle=$
$\displaystyle\frac{d_{1}^{2}+n-1}{2\sqrt{d_{1}}}<\frac{(n-1)d_{1}}{2\sqrt{d_{1}}}=\frac{(n-1)\sqrt{d_{1}}}{2}.$

For the vertex $v_{2}$,

$\displaystyle(A_{ag}(G)\textbf{x})_{v_{2}}$ $\displaystyle=$
$\displaystyle(d_{2}-3)\cdot\frac{1+d_{2}}{2\sqrt{d_{2}}}+\frac{d_{2}+d_{1}}{2\sqrt{d_{1}d_{2}}}\cdot\sqrt{d_{1}}+2\cdot\frac{d_{2}+2}{2\sqrt{2d_{2}}}\cdot\sqrt{2}$
$\displaystyle=$
$\displaystyle\frac{d_{2}^{2}+n+1}{2\sqrt{d_{2}}}\leq\frac{(n-1)d_{2}}{2\sqrt{d_{2}}}=\frac{(n-1)\sqrt{d_{2}}}{2}.$

For the vertex $v_{3}$,

$\displaystyle(A_{ag}(G)\textbf{x})_{v_{3}}=\frac{2+d_{2}}{2\sqrt{2d_{2}}}\cdot\sqrt{d_{2}}+\frac{2+2}{2\sqrt{4}}\cdot\sqrt{2}=\frac{d_{2}+6}{2\sqrt{2}}<\frac{n-1}{2}\cdot\sqrt{d_{3}}$.

Similarly, for the vertex $v_{4}$, we obtain

$\displaystyle(A_{ag}(G)\textbf{x})_{v_{4}}<\frac{(n-1)\sqrt{d_{4}}}{2}$.

Then $\displaystyle(A_{ag}(G)\textbf{x})_{i}<\frac{n-1}{2}x_{i}$ holds for all
vertices in $G\in\mathcal{G}_{4}$ and $G\ncong G_{3}$.

(4) If $G\in\mathcal{G}_{5}$ and $G\ncong G_{4}$, then $d_{1}+d_{2}=n$ and
$3\leq d_{1},d_{2}\leq n-3$.

For the vertex $v_{1}$,

$\displaystyle(A_{ag}(G)\textbf{x})_{v_{1}}$ $\displaystyle=$
$\displaystyle(d_{1}-2)\cdot\frac{1+d_{1}}{2\sqrt{d_{1}}}+\frac{d_{1}+d_{2}}{2\sqrt{d_{1}d_{2}}}\cdot\sqrt{d_{2}}+\frac{d_{1}+2}{2\sqrt{2d_{1}}}\cdot\sqrt{2}$
$\displaystyle=$
$\displaystyle\frac{d_{1}^{2}+n}{2\sqrt{d_{1}}}<\frac{(n-1)d_{1}}{2\sqrt{d_{1}}}=\frac{(n-1)\sqrt{d_{1}}}{2}.$

Similarly, for the vertex $v_{2}$, we obtain

$\displaystyle(A_{ag}(G)\textbf{x})_{v_{2}}<\frac{(n-1)\sqrt{d_{2}}}{2}$.

For the vertex $v_{3}$,

$\displaystyle\ \ \
(A_{ag}(G)\textbf{x})_{v_{3}}=\frac{2+d_{2}}{2\sqrt{2d_{2}}}\cdot\sqrt{d_{2}}+\frac{2+2}{2\sqrt{4}}\cdot\sqrt{2}=\frac{d_{2}+6}{2\sqrt{2}}<\frac{n-1}{2}\cdot\sqrt{d_{3}}$.

Similarly, for the vertex $v_{4}$, we get

$\displaystyle(A_{ag}(G)\textbf{x})_{v_{4}}<\frac{(n-1)\sqrt{d_{4}}}{2}$.

Then $\displaystyle(A_{ag}(G)\textbf{x})_{i}<\frac{n-1}{2}x_{i}$ holds for all
vertices in $G\in\mathcal{G}_{5}$ and $G\ncong G_{4}$.

That is $\displaystyle A_{ag}(G)\textbf{x}\leq\frac{n-1}{2}\textbf{x}$ holds
for $G$.


# Query Understanding for Natural Language Enterprise Search

Francisco Borges<EMAIL_ADDRESS>Salesforce Inc. ,  Georgios Balikas
<EMAIL_ADDRESS>Salesforce Inc. ,  Marc Brette<EMAIL_ADDRESS>Salesforce Inc. ,  Guillaume Kempf<EMAIL_ADDRESS>Salesforce
Inc. ,  Arvind Srikantan<EMAIL_ADDRESS>Salesforce Inc. ,
Matthieu Landos<EMAIL_ADDRESS>Salesforce Inc. ,  Darya
Brazouskaya<EMAIL_ADDRESS>Salesforce Inc. and  Qianqian
Shi<EMAIL_ADDRESS>Salesforce Inc.

(2018)

###### Abstract.

Natural Language Search (NLS) extends the capabilities of search engines that
perform keyword search allowing users to issue queries in a more “natural”
language. The engine tries to understand the meaning of the queries and to map
the query words to the symbols it supports like Persons, Organizations, Time
Expressions etc.. It, then, retrieves the information that satisfies the
user’s need in different forms like an answer, a record or a list of records.

We present an NLS system we implemented as part of the Search service of a
major CRM platform. The system is currently in production serving thousands of
customers. Our user studies showed that creating dynamic reports with NLS
saved more than 50% of our user’s time compared to achieving the same result
with navigational search. We describe the architecture of the system, the
particularities of the CRM domain as well as how they have influenced our
design decisions. Among several submodules of the system we detail the role of
a Deep Learning Named Entity Recognizer. The paper concludes with discussion
over the lessons learned while developing this product.

Conversational Search, Named Entity Recognition, Enterprise Search, Record
Retrieval

††copyright: acmcopyright††journalyear: 2018††doi:
10.1145/1122445.1122456††conference: DeepNLP ’20; July 30, 2020; Xi’an,
China††booktitle: DeepNLP’20, July 30, 2020, Xi’an, China††price: 15.00††isbn:
978-1-4503-XXXX-X/18/06

##  1\. Introduction

Recent advances in Machine Learning have resulted in considerable improvements
in Natural Language Search (NLS) systems. As a result, several popular web
search engines (Google, Bing, Yandex, DuckDuckGo to name a few) can now
resolve queries of various intents ranging from geography (“Which is the
capital of France?”) to restaurant suggestions (“show me sushi restaurants”)
and many others. Such systems are Natural in the sense that their style and
vocabulary is much richer and more human-like than what one would observe with
keyword search queries. From a user experience point-of-view, NLS is very
powerful: it allows the user to chain several filters together in natural
(colloquial) language, getting them applied in the results. Completing the
same task with keyword search would require issuing a relevant query,
navigating to the retrieved results and manually inspecting them. In other use
cases completing the same task would require manually creating a report or
formally querying a “database”. In the restaurant example above, a user can
type “show me open sushi restaurants near me” and expect the NLS results to be
filtered according to their opening hours and geolocalization.

In this paper we describe the main components of an NLS system we built as
part of the search service for a major Customer Relationship Management (CRM)
service. The goal of CRM is to manage a company’s interactions with current
and potential customers. It accompanies vendors in every step of the cycle
from finding a lead, converting it and later supporting existing contracts. As
such, it must be flexible and customizable to be tailored to a variety of
customers in very different domains and needs. In addition, data privacy is of
utmost importance to a CRM service both at the user level111The EU’s General
Data Protection Regulation (GDPR) is an example of law we, and many of our
customers, must comply with. and at the customer level. For instance, our
customers may not want their data to be used for improvements in machine
learning systems that will be used by their competitors. Designing an NLS
system that copes with these limitations poses several ML challenges in every
stage of the development pipeline including training data generation, model
selection and online evaluation.

Despite the challenges of the CRM field, providing NLS capabilities in a CRM
search service can dramatically improve the workflow of the users. For
example, a common workflow of a salesperson is to inspect their assigned
opportunities and perform different tasks to advance and convert them. This
workflow is accelerated when they can retrieve opportunities in a given state
like “open” or “closed”. Same for a salesperson on the road trying to visit
her customers: retrieving opportunities given a location can save her time.
Our user studies showed that creating dynamic reports using NLS saves more
than 50% of a user’s time compared to achieving the same goal with
navigational search. Enabling users to achieve their goals faster is the goal
of search. We believe that the adoption of our NLS system, that today serves
thousands of users, is mainly driven by this acceleration.

Our NLS system consists of several submodules that are responsible for
understanding parts of the query, applying business logic, enforcing sharing
rules etc. Among them, there is a deep learning Named Entity Recognition (NER)
system that is part of the query understanding submodules. While developing
the NLS system we faced different challenges concerning the integration of
Deep Learning to our system. Some examples are the lack of training data for
our use-case, our need to have a single model serving very different customers
and engineering constraints for the size of the model. In this paper we
discuss our choices and solutions to these problems.

The contributions of this paper can be summarized as follows:

  * •

We describe the core components of an NLS system that is in production and
serves thousands of customers daily.

  * •

We detail the system architecture and the design choices of a deep learning
NER that is among the core systems of our NLS implementation

  * •

We share our lessons learned and best practices from bringing this service to
production and the machine learning decisions we made. We also highlight how
these decisions evolved during the lifecycle of our project. We hope that
sharing these will benefit members of our community who are building such
systems to overcome problems similar to those we faced.

##  2\. Related Work

We aim to provide our users an interface to interact with their data stored in
a database (Androutsopoulos et al., 1995). NLS should use Natural Language
utterances instead of a formal language (like SQL) or a controlled language
(Schwitter, 2010) like Attempto Controlled English (Fuchs et al., 2008). These
require additional knowledge or training and we believe this is an adoption
barrier.

To develop the NLS functionality in our search service, we position ourselves
in the field on semantic parsing for Natural Language Search (Kamath and Das,
2018). Semantic parsers have found applications in various domains from robot
instructions following (Artzi and Zettlemoyer, 2013; Williams et al., 2018) to
conversational search and dialog management (Raghuvanshi et al., 2018;
Srivastava et al., 2017) Our implementation borrows ideas from (Liang and
Potts, 2015; Liang, 2016). Internally, NLS uses a grammar in order to generate
training examples for our Named Entity Recognizer and a more semantically and
syntactically narrow version of this grammar to support autocomplete and query
suggestions. The role of the grammar is different in our system compared to
these papers. We do not validate the logical forms with the grammar. We have a
system in place that validates it by applying our business logic which
controls for several aspects of the generated logical form including privacy.
More recent work has shown promising results using end-to-end neural networks
for semantic parsing (Dong and Lapata, 2018; Zhong et al., 2017). Instead of
relying exclusively on a neural network, we have designed our system with
several sub-components to allow for complete explainability of our results.

In the context of semantic parsing, previous works have used grammars in order
to extend the training set. In (Wang et al., 2015) Wang et al. describe their
approach where they begin by manually generating representative logical forms
paired with canonical utterances for a given domain. They, then, use
crowdsourcing to extend the produced data points by paraphrasing. In our
domain we do not massively label data, such as production logs, due to privacy
and legal issues. Another similar approach is recombination (Jia and Liang,
2016) where a synchronous Context Free Grammar is learned by identifying
conditional independece assumptions in the training data. This grammar allows
to sample more training data thus extending the initial training set.
Recombination is similar to our approach in that it allows sampling training
instances from a grammar by extending an existing, current dataset. In our
case, however, we did not have any initial training data: we used a
probabilistic Context Free Grammar to bootstrap the initial training set.

Developing NLS we came to understand that such a deployed system should come
with autocomplete and query suggestions support. We found that, instead of
user manuals, query suggestions are much more efficient to educate the users
for the capabilities of our search service. The value of query suggestions has
been found by previous studies e.g., (Jagadish et al., 2007). Query completion
and suggestion systems have also been proposed for formal languages such as
SQL (Khoussainova et al., 2010) or SPARQL (Bast and Buchhold, 2017). Query
suggestions as part of a semantic parser is also discussed in (Arkoudas and
Yahya, 2019). The most important difference is, perhaps, that our customer
data are kept apart and siloed for each customer; scaling approaches as those
described in (Arkoudas and Yahya, 2019) to treat each customer separately to
thousands of them is an important engineering challenge in itself. Instead,
until now we have opted for using a probabilistic grammar for suggestions,
which only needs probability weights that can be controlled for each
organization by the metadata.

##  3\. Problem Statement

Figure 1. Examples of processing NLS queries. The NLS system should understand
that the issued queries are not keyword searches and construct SQL-like
statements. These statements when executed against the CRM schema return lists
of records. In the examples NLS should return lists of opportunities that
satisfy the different filters that are described in the user query. For
simplicity, we do not show the annotations that NLS should return to the UI to
explain the query interpretation.

The core goal of our NLS system is to take short, colloquial and often
grammatically incorrect queries and convert them into formal structured
“database” queries. This allows users to filter and select information through
the CRM schema that organizes their data without using a dedicated formal
language.

We position ourselves in an Information Retrieval setting where the user
expresses their need as a query. We treat each query independently leaving the
concept of search sessions out of the scope of this work. The NLS system we
describe extends our deployed search engine by distinguishing between two
different user intents. The first user intent is keyword search. The second is
NLS. Figure 1 illustrates examples of NLS queries that our system is expected
to resolve.

The user of Fig. 1 issues the first query (“my open opportunities in New
York”) with a goal to fetch a filtered set of the records stored within their
CRM system. The query differs from a keyword search in that it expresses an
intent to select a subset of the “Opportunities” records,222In the rest of the
paper we refer to CRM entities, like Opportunities and Accounts, as CRM
objects or CRM entities interchangeably. after applying the prescribed
filters: open refers to the boolean “isOpen” and “New York” can refer to a
City or a State. The system must recognize that the query is to be resolved
using the “Opportunities” entity (our CRM schema has several entities) and
then construct an appropriate query that will return the expected results. The
second query (“acme opportunities”) needs to be resolved differently: the
system should recognize that “acme” is an organization, find its record id in
“Accounts” and return the opportunities whose account id matches the resolved
id for “acme”. For each user query an appropriate database query needs be
constructed to return to the user a list of records of the Opportunity entity.

We frame NLS as a semantic parsing problem (Kamath and Das, 2018; Liang and
Potts, 2015; Liang, 2016): given a natural language utterance (the query) we
try to generate a semantic representation. Theoretically the query can be of
arbitrary length combining several concepts like a record type or a time
expression. The final semantic representation is a logical form that (i)
allows querying the objects of our CRM schema via an SQL-like language333In
this paper we refer to both SQL-like and formal languages interchangeably and,
(ii) provides enough annotations for the UI to explain the retrieved results
to the users.

In the remainder of this section we describe the challenges and the
constraints of CRM in more detail as they have influenced several of our
design decisions and machine learning choices.

###  3.1. Challenges of enterprise CRM search

We provide enterprise search services to more than 150 thousand CRM customers.
Our customers444We refer to a customer also as an organization or a CRM
customer. range from small and medium sized businesses with few people,
nonprofits with 100s of volunteers to large companies with 100s of thousands
of employees. Each customer has a number of different users and most
importantly its own private data. In this section we will describe some of the
challenges that arise from the CRM domain and, more generally, from enterprise
search (Hawking, 2004; Dmitriev et al., 2010).

Privacy Our enterprise search service is characterized by the fact that
customers CRM data is completely siloed from one another. Data is not only
indexed separately but statistical aggregation is limited within each silo.
Privacy is manifested both in the user and content level and is extremely
strict. We do not customer queries to train models, nor do we inspect customer
CRM data to understand its characteristics better. Many customers are
unwilling to give us contractual permission to blindingly mix customer CRM
data, such as names of Accounts or just data mined from query logs to build
models.

Usability Our NLS offering augments our search services with the capacity to
interpret NLS queries. These queries are entered into the same search input
box as regular search. Reusing the input field has many practical
consequences. The first is that users may not be aware of the new NLS
capabilities. The system must offer NLS query suggestions and NLS query auto-
complete features to help them. When a query is interpreted as NLS, the User
Interface (UI) must provide clear explanations of how the query was
interpreted, as well as providing fall-back and remediation mechanisms. A
fall-back is when the user demands a query to be interpreted as a keyword
search. Remediation is when the user needs to change the interpretation of a
query. For example, when our system resolves a Person in a query to a given
record id the user may wish to correct that by selecting another Person
record. Recall the example of Fig. 1: NLS needs to resolve “acme” to an
Account record id but there can be multiple records with “acme” in their name.
The user should be able to signal that “this is not the acme I meant” and be
able to select another record from Accounts. The requirement to explain the
query’s interpretation and to be able to change specific clauses in it must be
taken into account when designing a solution. For example, an end-to-end deep
learning model with limited explainability is not a suitable solution.

Scale One of our key requirements is to deliver NLS at scale, to each of our
customers. This requires a generic architecture and generic models. We are not
building machine learning a la carte for each customer but a system that
delivers NLS to all of them at once. Yet this system must be able to deal with
each customer’s data, CRM workflows and even their customized CRM schemas. For
instance, many of our customers manage record ownership differently: “my
accounts” can have a different meaning depending on the customer and our
engine must be able to interpret the query according to the customer’s
specific record management workflow. An option is to require each customer’s
administrator to configure the system at length. We believe that this is a
huge barrier to adoption. Therefore, another key requirement is that our NLS
has to work and deliver customer value as is, without requiring admins to
invest time and energy pre-tuning their system.

##  4\. System Overview

Figure 2. A simplified representation of our NLS system showing the code
organization into submodules and where each comes in during the handling of a
query.

Our natural language search service implements and uses two different APIs:
(i) query processing and (ii) query suggestion. Query processing is
responsible for processing a user query and trying to transform it into a
formal structured query. It returns results and a data structure that explains
how the query was interpreted. Query suggestion generates valid NLS query
autocompletion and suggestions to the user. In this overview we describe our
query processing system in detail.

The query processing system is organized into several submodules roughly as
shown in Fig. 2. There are two groups of submodules in our system: the first
group is responsible for “understanding” the query and the second is
responsible for processing and validating the results of the first. Query
understanding steps involve pre-tagging, tagging (named-entity-recognition)
and parsing their results into a semantic tree. Processing and validating
steps involve sanity and security checks, rules enforcement, ID resolution and
other steps necessary to generate results and explain what was done to our
users.

When a query arrives, it is associated with the NLS metadata. These two
elements are shared over the entire handling of a query. The metadata carries
all configuration relative to the entire system and ensures that the whole
system behaves consistently. Consistent behavior means that when we change the
configuration of a certain aspect of our system the change is reflected
consistently across all different submodules.

The query first goes through Pre-Tagging where multiple expert systems are
applied. An expert system is a component that handles a specific sub-domain
such as identifying references to “picklist” CRM fields and its values. The
query is then passed on to a tagger which attempts to parse the query into one
or several semantic trees. The validity of these trees is evaluated by the
Execution Engine. This involves requirements and consistency checks, ID
resolution and finally applying security rules against each concept.

We built two taggers: one based on a simple grammar, called the Suggestions
Grammar, and another based on a Deep Learning NER. Both share most of the
steps described above. The system first attempts to interpret the query with
the Suggestions Grammar. If no semantic tree is valid, it runs the DL NER
tagger. The DL NER system can interpret a larger variety of queries than the
Suggestions Grammar but it can be unpredictable at times. It can also produce
multiple trees that the tagger orders by priority.

In the following subsections, we describe each of the subsystems in greater
detail.

###  4.1. NLS Metadata

The NLS Metadata is an object that unifies access to all configurations of our
system. It ensures consistency across the submodules and allows developers to
easily inspect the system configurations at once. Another practical aspect of
a dedicated metadata system is to coordinate and implement A/B experiments.
When a query is to be handled as part of an A/B experiment, we just pass the
corresponding experiment metadata.

###  4.2. Pre-tagging

The addition of pre-taggers to our system happened relatively late in its
development. The pre-taggers are expert systems that handle recognition tasks
that require customer-specific data. Pre-taggers are key components in making
NLS work well for thousands of customers with siloed data and different
vocabularies with just a single Deep Learning NER model.

One of our pre-taggers recognizes picklist values related to specific
entities. Picklists are dropdown fields that assume values from a list defined
in the CRM schema. While there are predefined values for them, each
organization can easily add, remove or edit/rename them to serve their
purposes. An example of a picklist that a Deep Learning solution can handle
well is a list of countries. Another example is the stage of an opportunity as
Figure 3 shows. In the second example, a DL system cannot easily generalize to
recognize such unseen values as they are specific to an organization and
normally extremely different across organizations.

Figure 3. An illustration of how recognizing picklist values can be difficult
in real life. Lots of values are very similar. The values shown are from our
own CRM organization and not from any of our customers.

Another pre-tagger in place is responsible for recognizing references to
entity names. Our CRM platform allows customers to rename our standard CRM
entities and many customers use that feature. In the example of Fig. 3 for
example, a customer could have renamed “Account” to “Customer”, “Factory” or,
say, their translation to another language. NLS should be able to correctly
resolve queries even with renamed entity names. While our deep learning NER
generalizes poorly in such cases, an expert system (in this case it can be a
dictionary look-up) with access to the CRM scheme during query resolution can
support the use-case.

###  4.3. Tagging

Our taggers are responsible for recognizing named-entities in a query that are
then parsed into semantic trees. As described above, we have two different
tagger implementations, the Suggestions Grammar, and the NER tagger. We
continue by describing the Suggestions Grammar and the need to have it in
place in addition to the NER tagger.

####  4.3.1. Suggestions Grammar tagger

As part of our overall user experience, the query suggestion engine helps
users craft queries and drive adoption of NLS. We do not address in detail the
Query Suggestion (QS) engine design in this paper, but we need to stress out
the interaction with the NLS system. QS must be consistent with the NLS
capabilities: its implementation should avoid logic duplication and a
suggested query must be interpretable and executable by the NLS execution
engine.

Our QS engine is based on a Probabilistic Context Free Grammar (PCFG), the
Suggestions Grammar. The system uses that PCFG to generate a Directed Acyclic
Graph (DAG) in memory, at query time. This DAG is used to both parse and
complete the input query. This approach allows us to deal with organization
and user specific vocabulary. We have a single global PCFG described in
metadata, and user specific DAGs generated using the query context (user,
organization, vocabulary etc). This not only enables us to respect customer
privacy, but also provides personalised vocabulary and ranking in query
suggestions, while only maintaining a single grammar.

To avoid duplicating logic, the QS engine re-uses part of the NLS pipeline and
is controlled by the same metadata driving the NLS engine. The PCFG re-uses
NLS pre-taggers logic when possible. Also, the suggested queries go through
the same security checks to eliminate candidates that would not be accessible
to the user.

When a user selects a suggestion, the query is interpreted by the NLS query
processing pipeline. Query suggestions are built to be interpretable, but
sometimes deep learning can be unpredictable and fails at tagging suggested
queries. Our solution was to turn the suggestion’s DAG parser into a second
tagger. This tagger has the capability to generate a semantic tree for each
generated suggestion. This ensures consistency between generation and
interpretation. While it may seem redundant to retag a suggested query, this
design choice was critical to consistently interpret both suggested and typed
NLS queries.

The Suggestion Grammar tagger is robust but limited in the variety of queries
it supports. It generates a single parse tree with no room for
misinterpretation. The NER tagger, described next, supports the whole range of
NLS queries.

####  4.3.2. Deep Learning NER tagger

Our main tagger is based on a DL NER model. This model recognizes and tags a
wide range of NLS query forms. The NER model encapsulates a lot of the
intelligence in the algorithm. It selects the most probable sequence of tags
for the query terms. The design of the NER model is addressed in details in
Section 5 below.

However, the tagger as a system, is more than the NER model. It generates
multiple candidates based on the tags from pre-taggers, and selects the best
candidates. Currently, the ordering criteria is very simple, assigning a
higher score for the longest matched sequences. Calling the NER model involves
several steps as follows:

  * •

The tagger prepares the input query for the NER model,

  * •

Pre-tagged terms are masked with a fixed token that the NER is aware of,

  * •

Some tokens are normalized: numbers and IDs are replaced with corresponding
fixed tokens.

The NER model output is a sequence of tags for each term. The tagger filters
out the invalid sequences and transforms each sequence of tags into a semantic
tree. Invalid sequences include sequences breaking structural rules we
manually defined. Each remaining tree corresponds to a different
interpretation of the query. The tagger ranks them in priority order and the
topmost interpretations are returned to the Execution engine. Here again, the
order is based on manual structural rules.

####  4.3.3. Semantic trees

The output format of our taggers started as a bag of named-entities and
evolved into a semantic tree at the time that we added support to entities
that modified the meaning of other entities than the root of the tree.

Figure 4. A very simple illustration of a semantic tree build for the query
“my won opportunities closed in the last 3 quarters”.

Figure 4 shows an example of a semantic tree for the query “my won
opportunities closed in the last 3 quarters”. One of the challenges of the
example is in handling “closed”. It can either refer to an “opportunity” or it
can be attached in the time expression. Creating a tree and attaching it to
the time expression disambiguates the semantics: the user is asking for
opportunities whose close date is within the last 3 quarters.

###  4.4. Execution Engine

Once we have a semantic tree of representation of a query, it gets passed to
our Execution Engine. This engine determines whether the semantic tree is a
valid natural language query. It then creates a logical form with enough
information to (i) create a structured query based on the customer’s CRM
schema and (ii) explain to the user how the query was interpreted.

Determining whether the semantic tree is valid involves validating the
internal consistency of the semantic tree, not just generally but according to
the customer’s CRM schema and to the security access rights of the user
running the query. If there are any Person or Organization named entities in
the semantic tree, they have to be resolved to a record id. Any unresolved
references invalidate the tree.

This final secondary structure must also contain enough information for our UI
to modify the interpretation of the query should the user decide to do so.
Suppose the user issues a query for “acme’s opportunities” with “acme” being
tagged as an Organization. If our ID resolution module resolves it to the
wrong Account ID (consider that there may be hundreds of valid Account records
with “acme” in their title), our users can use the remediation mechanisms NLS
provides to select a different Account record.

###  4.5. Security

In our CRM product customers can restrict user access not just to specific
records but also to entities and to specific fields of a given entity. That
means that some users may not be allowed to view or know about the Account
entity and that other users may know about Accounts but not about certain
fields of it, like Account.Price.

So both when creating query suggestions as well as interpreting queries we
need to enforce these access rules. Which means that besides usual record
access checks, we also perform security checks at the concept level.

If a user is not allowed to see the Account entity, our system will not show
any suggestions based on this entity nor interpret any queries based on
suggestions. For a user that can see the Account entity but can not see a
particular field of it, say Account.Stage, then only the queries that involve
this concept will be filtered out from their suggestions and the
interpretation of their queries.

###  4.6. ID Resolution

When a query makes a reference to a Person or Organization, e.g. ”jane’s
accounts” or ”acme closing opportunities”, we must resolve the Person or
Organization reference to a record id.

Id resolution is a navigational search problem (Broder, 2002) where there may
be hundreds of matches to the reference but only 1 of these is valid. In the
example of “jane’s accounts”, we may have hundreds of contacts or users named
Jane but only one of these records satisfy the user’s need. This is different
from the classical exploratory search situation where there is normally a
continuous range of relevant results.

To complicate things further, the expected record for “acme” or “jane” will
differ depending on who is issuing the query. For example, imagine a sales
agent working with an account named “Acme Canada Ltd” and another sales agent
working with an account named “Acme Netherlands BV”. The correct record to
return for a reference like “acme” depends on who is issuing the query.

Resolution takes place via cascade of different machine learning models, some
deep-learning based but not all. Due to its complexity and the theme of this
paper, we do not elaborate further on it.

Figure 5. An illustration of the typical ambiguity found when resolving
references to IDs within large organizations. The user is likely only
interested in a single record, there is no gradual continuous relevance in
this context. The correct result also depends on which is the user issuing the
query.

##  5\. NER with Deep Learning

Named Entity Recognition is central to any Language Understanding system. For
our case, we train a deep learning NER system to distinguish between standard
entities like Persons, Organizations, Time and Location (we split location in
City, State and Country) some entities that are boolean filters specific in
our CRM data model, and the standard CRM schemas that our CRM system uses and
we support. This entails that currently we only support NLS queries that can
be resolved using the subset of the CRM entities we support and our system
does not generalize to arbitrary entities (Zhong et al., 2017; Lyu et al.,
2020; Guo and Gao, 2019).

###  5.1. Data Generation

Figure 6. Pipeline to create synthetic data.

Before describing the architecture of our NER model, we describe the main
problem we faced: how to train a NER model without training data. In the early
development stages of the NLS system, we faced the challenge of collecting
data to train the model. Publicly available pre-trained models or datasets are
not sufficient for our use-case because:

  * •

The entities we are interested are a superset of those that are often used in
the literature

  * •

Most available datasets are very different in terms of style. We want to
recognize entities in short queries without long-range dependencies and formal
syntax.

To overcome this problem we decided to use a grammar. Similarly to the
Suggestions Grammar, we developed a probabilistic context free grammar which
models the order and the concepts of an NLS query. This is done offline, using
the Natural Language Toolkit (Bird et al., 2009). Figure 6 shows a simple
example of a toy PCFG grammar and a few of the related productions. Notice in
the figure that the grammar produces tag sequences that are populated with
appropriate vocabulary.

Having access to synthetic yet realistic tag sequences, we use in-house
available collections of organization names, locations etc to populate the tag
sequences. Such a slot-filling approach enables us to massively produce
training data for our NER model. The data are tailored to our product needs
and resemble sufficiently the queries we expect our users will issue.

###  5.2. Model Architecture

Figure 7. The architecture we are using for our deep learning tagger that is
implemented using Keras. We use word embeddings initialized with GloVe and
also character embeddings randomly initialized.

Our NER is a sequence to sequence Bidirectional-LSTM network that uses word
and character embeddings (Lample et al., 2016). The goal is to predict the tag
of each word. Our data use the IOB format (In-Outside-Begin) to denote multi-
word entities. Figure 7 shows the architecture as implemented in Keras
(Chollet et al., 2015). We have relied on the open-source implementation of
Anago (Nakayama, 2020) that we extended for our usage.

We expect our NER model to fully understand the words in a query. Given their
tags, the execution engine generates the logical form that can be used to
retrieve the results for the user as described in Section 4.4. Depending on
the tags, terms are treated differently. For example, Persons or Organizations
are resolved to an id. Due to this strong dependency between the NER tags and
the system’s response, we require every term of the query to be correctly
tagged. For this reason, we decided to measure and optimize our recognition
performance against the Strict Correct Ratio (SCR) on the query level and not
the $F_{1}$ score that is often used and is calculated at the tag level. Given
an input query with tags $y=(y_{1},\ldots,y_{n})$ and predicted tags
$\hat{y}=(\hat{y_{1}},\ldots,\hat{y_{n}})$ the SCR is 1 if every tag is
predicted correctly: $\forall i:(y_{i}==\hat{y_{i}})$. We implemented
monitoring callbacks and early stopping using SCR in order to optimize for it.

As seen in the model’s output layer in Fig. 7 there are 48 output classes (24
named entities). Compared to well studied datasets like the CoNLL NER dataset
(Sang and De Meulder, 2003) or the WNUT datasets (Derczynski et al., 2017) we
have many more tags. This is due to our decision to maintain the complexity to
the deep learning system instead of using several subsystems. As a
consequence, the deep learning system needs to distinguish between standard
entities (Organization, Person, etc.) and domain-specific ones like boolean
filters that can be applied when fetching records belonging to specific CRM
entities. Recall the example of Fig. 1 : “open” is a boolean filter that must
be recognized in the context of “opportunities”. The same term can have a
different or no meaning in the context of another object, like “account” for
instance. Modeling such contextual information is a key challenge of our use-
case.

###  5.3. NER Model Evaluation

Data preprocessing is central to any machine learning application. Our
preprocessing decisions are evaluated on different dimensions. Two of the most
notable ones are NER performance improvement and memory when the model is
serialized. The role of the first is clear: better recognition rates ensure
better user experience. The second is enforced by our engineering platform
constraints. The NER model is trained with Tensorflow (Abadi et al., 2016). To
serve the model we need it to be less than 200MB serialized. Respecting such a
hard limit introduces different trade-offs between model expressiveness and
memory footprint. To this end, we have evaluated different aspects of the
model complexity: (i) the dimensions of our word and character embeddings,
(ii) the size of our vocabulary, and (iii) the depth of the Neural Network
too. In the remainder of this section we demonstrate the impact of different
hyper-parameters for the architecture presented in the previous paragraph.

Figure 8. The effect of increasing the size of the training data in the
performance of the model. Lowercasing ignores casing information by
lowercasing the queries. “With casing” uses separate character embeddings
depending on the casing in the query.

Training Data For machine learning systems and in particular for deep-learning
the size of the training data is an important factor. Using the method of
Subsection 5.1 we can practically generate large amounts of training data.
Figure 8 shows the performance of NER in terms of SCR with respect to the size
of the training data. Increasing the training data improves the performance of
NER. As a result, having a high quality PCFG to generate realistic and complex
data, can benefit the performance online.

Embeddings We initialize our embeddings using GloVe (Pennington et al., 2014).
However, our vocabulary is different from Wikipedia as it contains a lot of
person and organization names. As a result, we observed a lot of out-of-
vocabulary (OOV) words. During training we initialize OOV with embeddings
randomly from a uniform distribution in [-0.5, 0.5]. Further, we train the
embeddings to fine-tune them for our application. Figure 9 shows the effect of
the dimension of embeddings. For our application, we find that the best
performance is obtained with dimension 50. We hypothesize that this is due to
the nature of the task: queries as short text spans, they do not follow
grammar rules and there are few long dependencies. Small embeddings can encode
the information needed for the task. This finding is convenient for our use-
case as it reduces the memory requirements of the deep learning model.

Figure 9. Impact of the dimension of the word embeddings in the performance of
the NER. For NLS queries, we achieve the optimal performance with embeddings
of size 50.

Text style The seminal work of (Sutton et al., 2012) shows that style
information is important for NER and the importance of capturing text style in
the form of capitalization. In the early stages of our development, we
evaluated this finding for our data. We implemented casing features as
separate character embeddings for the same character. In this experiment, we
kept the word embedding lookups lower-cased to respect the memory
requirements. As Figure 8 shows, we found that lowercasing text did not
degrade the NER performance.

An interesting observation concerns the impact on the user experience of
capitalization features. As expected from a modeling perspective, we found
cases where changing capitalization resulted in different NER tags due to
capitalization signals in the training data. Such behaviors, however, in an
online system can be frustrating for the users as they would receive different
results depending on how they type the query. Given this observation and the
performance benefits of dropping text style information, we are lower-casing
the queries.

##  6\. System Evaluation

Releasing a new version of our NER impacts the user experience as it is used
to recognize the main parts of the query. Before releasing a model, we follow
a thorough performance validation process on several test datasets. The goal
is to avoid introducing regressions that may impact negatively the user’s
trust on NLS and track the quality improvement.

Evaluating the performance of a model in the setting of a product that
constantly evolves is a challenge in itself. We cannot use a static validation
or test set. Also, as the system becomes more mature, measures need to be
taken to ensure smooth and consistent user experience. As a result, at the
very early stages of development, one could allow faster model
experimentation. However, as the user base increases and starts to rely on our
functionality the validation around every change must become stricter. Apart
from the usual validation and test sets that are automatically generated as
described in the previous section, we have developed three additional
mechanisms to ensure quality control. We present them ordered, from those we
implemented early to those we implemented as the product became more popular.

###  6.1. Non Regression Dataset

Our Non-Regression Dataset (NRD) is a dataset that consists of queries whose
tags must be predicted correctly always. The concept of NRD extends the
concepts of unit tests and test datasets for training a model to serve
customers. It is a collection of test cases gathered in a dataset (like a test
dataset) but if any of them is tagged incorrectly the training process fails.
Having NRD in place ensures that NER tags a set of queries we deem very
important as expected. For example, we include generic queries listed in the
documentation that lots of users are bound to try.

###  6.2. Golden Standard Dataset

While the NRD ensures that a set of queries consistently succeed, it does not
evaluate the quality of the predictions. To achieve this, we are maintaining a
manually curated test dataset, which we refer to as our Golden Standard
Dataset (GSD). This is a versioned collection of queries of two categories:
queries that should trigger an NLS and those which should trigger a keyword
search.

NLS queries are annotated with (i) their NER tags, (ii) their SQL-like
statement we expect that NLS will generate and whose results will be rendered
to the user and, (iii) one, or several query annotations - which indicate
various semantic information like the origin of the query, or the set of
concepts in the query.

The NER tags allow us to evaluate the quality of the NER predictions. NER,
however, is a sub-component of the system. The SQL-like statements let us
evaluate the whole NLS system as it controls the content that is to be
rendered in the user.

Adding query annotations to each query solves the problem of comparability of
systems that are trained on evolving training and dev datasets. The training
sets evolve to encompass new features. As the number of tags to the training
data changes to cover more use-cases, predictions may change. Having query
level annotations allows for historical comparisons of model quality: we can
always report the performance on queries annotated as “core-concept” and
compare whether newer models improve on these queries. For example, we are
interested to know that the model versioned 0.1.5 achieved 90% SCR in the
queries annotated as “time-modifiers” and that this is an improvement by 6
absolute points compared to the 0.1.4 model that scored 84%. This insight
enables us to ship the model 0.1.5 in production. At the same time, with each
new feature we support, we add queries in the GSD to monitor the system’s
performance on them. Finally, such a system allows us to track improvement on
regressions or bugs: for every acknowledged case, we can create feature tags
pertaining to a bug and ensure that future models improve on it.

###  6.3. Model Deployment

The NER tags can be used to test a new version of a NER model without any
deployment. However, to run the GSD evaluation, we need an environment with
realistic data. The GSD contains queries that are based on internal production
data. To calculate measures on the SQL-like level, we set up an internal
sandbox instance of our internal CRM –our use of our own product– that is
populated with real production data. In this sandbox we issue the GSD queries,
collect the logs from the different steps of the NLS system and report on
metrics on the entire NLS system.

Evaluating new and existing models in this end-to-end way let us define a
release cycle. Before shipping a new model in production, it goes through the
different quality gates and it has to perform better or the same in the end-
to-end evaluation. In this way, we can also deploy multiple models to be
evaluated with A/B experiments.

##  7\. Lessons Learned

Our current System is the result of effort across many iterations. During this
journey, we learned a lot and our system evolved in some unexpected ways.

Query Suggestions In this paper, we only briefly talked about query
suggestions. However, they are essential for feature discovery. We observed
that concepts that were not exposed in query suggestions were barely used by
the users as they were not familiar with them. Even today, with increased
adoption, the majority of NLS queries come from suggestions. A core conclusion
is that any feature supported by our NLS query processing engine must be
supported by query suggestions. Another aspect is that suggestions ranking
needs to maintain a critical but delicate balance between user education/new
feature advertisement and click-through-rate (essentially a diversity/quality
problem on its own).

Deep Learning Model Deep-learning is not the ideal tool for every problem, but
it is strong enough to handle all tasks well. In our early development process
we started with a single tagger that used the deep-learning NER model. This
allowed us to bootstrap a working NLS system end to end in a short amount of
time and also allowed us to pilot the system early.

As we monitored the system usage and the system failures in particular, we
identified concepts that are better served by expert systems, which in the
majority of cases are rule-based annotators. While maintaining the core NER
component, we added these expert systems to increase robustness and coverage.

Another important reason in favour of the expert systems was the variety of
data across customers due to their ability to extensively customize our CRM
platform. The demand to support more use-cases, in diverse settings, with
restricted access to customer data for training makes it challenging for the
NER to generalize well. On the other hand, expert systems that have access
online to the configuration of an organization are more robust for simple
recognition tasks (like boolean filters or picklist values).

Additionally, in our setting, the DL-based algorithm had to be complemented by
a simpler and more robust grammar based algorithm - the Query Suggestions
Grammar. This originated from the need to consistently support suggested
queries execution but it finally provides a good balance between the two
systems. The Query Suggestions Grammar alleviates pressure on DL because it
handles easy queries predictably and without surprises. DL alleviates pressure
from Query Suggestion Grammar-based algorithm because it handles hard complex
queries and idiosyncrasies which cannot be encoded in a context free setting
of the suggestion grammar.

Training data generation Our initial model was trained with a very constrained
training set. We forced the training set to be limited to the minimal set of
query patterns we wanted to support. In particular, queries followed a strict
ordering of concepts. Instead of making the model more robust, it made it more
brittle. We, since, switched to a training generation approach with more noise
- randomly reordering terms and concepts while ensuring the data remains
semantically meaningful in most cases.

Pre-trained embeddings were not sufficient in our context. The specificity of
queries required embeddings trained for our domain.

The named entities that are normally used in NER systems were at times too
specific for us: the difference between Person and Organization is less
important because the ID Resolution module performs well even if these
categories are merged.

Project life cycle In an agile project setting, each component evolves and
matures as the project progresses. Some critical data science and engineering
practices at our current stage would have been detrimental in the early pilot
phases. We now have a mature quality gating workflow with versioned GSD and AB
experiment support, but it would have been unwise to spend effort on these
early.

As adoption grows and users start to depend on the system, it is key to have
those features and others like model versioning, metadata-driven algorithms,
multi-stage quality pipeline, or extremely precise production instrumentation.

##  8\. Conclusions

In this paper, we described an industrial NLS system integrated as part of
Search of a major CRM platform. Our system was initially built with a deep
learning NER model at its core. The architecture later evolved to better
support the complexity and the real world constraints of enterprise customers.

Our NLS in its current state is a hybrid system that uses two tagging
pipelines: one that combines Deep Learning with rule-based (expert) systems to
generalize to various customers and, another that uses a grammar and mainly
resolves our query suggestions. To use deep learning we overcame several
challenges, the most important being, perhaps, the lack of training data. We
found using synthetically generated, yet realistic, data generated by a PCFG
to be very effective for our use-case.

To ensure high quality and user satisfaction, before shipping a model we apply
multiple validation checks. To track improvement in this constantly evolving
setting we improved our model lifecycle management, our metadata and the
evaluation datasets in ways we described in this paper. We now firmly believe
that in the context of real applications investments in such tools are
essential and should complement work on model improvements.

As adoption continues, we will add support for more concepts and new user
intents, more customization (like custom objects that our customers can
create) and more languages. We will support more advanced remediations, and
improve our system by learning specialized models for query suggestions,
interpretations ranking and ID resolution.

##  9\. Acknowledgements

We would like to thank Ahmet Bugdayci, Anmol Bhasin, Christian Posse, Dylan
Hingey, Ghislain Brun, Mario Rodriguez, Paulo Gomes, Rohit Kapoor and Sam
Edwards for their support, help and feedback throughout the development of
this work.

## References

  * (1)
  * Abadi et al. (2016) Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. 2016\.  Tensorflow: A system for large-scale machine learning. In _12th $\\{$USENIX$\\}$ Symposium on Operating Systems Design and Implementation ($\\{$OSDI$\\}$ 16)_. 265–283.
  * Androutsopoulos et al. (1995) Ion Androutsopoulos, Graeme D Ritchie, and Peter Thanisch. 1995\.  Natural language interfaces to databases–an introduction.  _Natural language engineering_ 1, 1 (1995), 29–81.
  * Arkoudas and Yahya (2019) Konstantine Arkoudas and Mohamed Yahya. 2019.  Semantically Driven Auto-completion.  _CoRR_ abs/1906.09450 (2019).  arXiv:1906.09450 http://arxiv.org/abs/1906.09450
  * Artzi and Zettlemoyer (2013) Yoav Artzi and Luke Zettlemoyer. 2013.  Weakly supervised learning of semantic parsers for mapping instructions to actions.  _Transactions of the Association for Computational Linguistics_ 1 (2013), 49–62.
  * Bast and Buchhold (2017) Hannah Bast and Björn Buchhold. 2017.  Qlever: A query engine for efficient sparql+ text search. In _Proceedings of the 2017 ACM on Conference on Information and Knowledge Management_. 647–656.
  * Bird et al. (2009) Steven Bird, Ewan Klein, and Edward Loper (Eds.). 2009\.  _Natural language processing with Python : [analyzing text with the natural language toolkit]_ (1. ed. ed.).  O’Reilly.
  * Broder (2002) Andrei Broder. 2002\.  A taxonomy of web search. In _ACM Sigir forum_ , Vol. 36. ACM New York, NY, USA, 3–10.
  * Chollet et al. (2015) François Chollet et al. 2015\.  Keras.  https://keras.io.
  * Derczynski et al. (2017) Leon Derczynski, Eric Nichols, Marieke van Erp, and Nut Limsopatham. 2017.  Results of the WNUT2017 shared task on novel and emerging entity recognition. In _Proceedings of the 3rd Workshop on Noisy User-generated Text_. 140–147.
  * Dmitriev et al. (2010) Pavel Dmitriev, Pavel Serdyukov, and Sergey Chernov. 2010\.  Enterprise and desktop search. In _Proceedings of the 19th international conference on World wide web_. 1345–1346.
  * Dong and Lapata (2018) Li Dong and Mirella Lapata. 2018.  Coarse-to-fine decoding for neural semantic parsing.  _arXiv preprint arXiv:1805.04793_ (2018).
  * Fuchs et al. (2008) Norbert E Fuchs, Kaarel Kaljurand, and Tobias Kuhn. 2008\.  Attempto controlled english for knowledge representation.  In _Reasoning Web_. Springer, 104–124.
  * Guo and Gao (2019) Tong Guo and Huilin Gao. 2019.  Content Enhanced BERT-based Text-to-SQL Generation.  _arXiv preprint arXiv:1910.07179_ (2019).
  * Hawking (2004) David Hawking. 2004\.  Challenges in Enterprise Search.. In _ADC_ , Vol. 4. Citeseer, 15–24.
  * Jagadish et al. (2007) HV Jagadish, Adriane Chapman, Aaron Elkiss, Magesh Jayapandian, Yunyao Li, Arnab Nandi, and Cong Yu. 2007.  Making database systems usable. In _Proceedings of the 2007 ACM SIGMOD international conference on Management of data_. 13–24.
  * Jia and Liang (2016) Robin Jia and Percy Liang. 2016.  Data recombination for neural semantic parsing.  _arXiv preprint arXiv:1606.03622_ (2016).
  * Kamath and Das (2018) Aishwarya Kamath and Rajarshi Das. 2018.  A survey on semantic parsing.  _arXiv preprint arXiv:1812.00978_ (2018).
  * Khoussainova et al. (2010) Nodira Khoussainova, YongChul Kwon, Magdalena Balazinska, and Dan Suciu. 2010.  SnipSuggest: Context-aware autocompletion for SQL.  _Proceedings of the VLDB Endowment_ 4, 1 (2010), 22–33.
  * Lample et al. (2016) Guillaume Lample, Miguel Ballesteros, Sandeep Subramanian, Kazuya Kawakami, and Chris Dyer. 2016\.  Neural architectures for named entity recognition.  _arXiv preprint arXiv:1603.01360_ (2016).
  * Liang (2016) Percy Liang. 2016\.  Learning executable semantic parsers for natural language understanding.  _Commun. ACM_ 59, 9 (2016), 68–76.
  * Liang and Potts (2015) Percy Liang and Christopher Potts. 2015.  Bringing machine learning and compositional semantics together.  _Annu. Rev. Linguist._ 1, 1 (2015), 355–376.  http://www.annualreviews.org/doi/abs/10.1146/annurev-linguist-030514-125312
  * Lyu et al. (2020) Qin Lyu, Kaushik Chakrabarti, Shobhit Hathi, Souvik Kundu, Jianwen Zhang, and Zheng Chen. 2020\.  _Hybrid Ranking Network for Text-to-SQL_.  Technical Report MSR-TR-2020-7. Microsoft Dynamics 365 AI.  https://www.microsoft.com/en-us/research/publication/hybrid-ranking-network-for-text-to-sql/
  * Nakayama (2020) Hiroki Nakayama. 2020\.  Bidirectional LSTM-CRF and ELMo for Named-Entity Recognition, Part-of-Speech Tagging and so on.  https://github.com/Hironsan/anago.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D Manning. 2014.  Glove: Global vectors for word representation. In _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_. 1532–1543.
  * Raghuvanshi et al. (2018) Arushi Raghuvanshi, Lucien Carroll, and Karthik Raghunathan. 2018\.  Developing Production-Level Conversational Interfaces with Shallow Semantic Parsing. In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_. 157–162.
  * Sang and De Meulder (2003) Erik F Sang and Fien De Meulder. 2003.  Introduction to the CoNLL-2003 shared task: Language-independent named entity recognition.  _arXiv preprint cs/0306050_ (2003).
  * Schwitter (2010) Rolf Schwitter. 2010\.  Controlled natural languages for knowledge representation. In _Proceedings of the 23rd International Conference on Computational Linguistics: Posters_. Association for Computational Linguistics, 1113–1121.
  * Srivastava et al. (2017) Shashank Srivastava, Amos Azaria, and Tom M Mitchell. 2017\.  Parsing Natural Language Conversations using Contextual Cues.. In _IJCAI_. 4089–4095.
  * Sutton et al. (2012) Charles Sutton, Andrew McCallum, et al. 2012\.  An introduction to conditional random fields.  _Foundations and Trends® in Machine Learning_ 4, 4 (2012), 267–373.
  * Wang et al. (2015) Yushi Wang, Jonathan Berant, and Percy Liang. 2015\.  Building a semantic parser overnight. In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_. 1332–1342.
  * Williams et al. (2018) Edward C Williams, Nakul Gopalan, Mine Rhee, and Stefanie Tellex. 2018.  Learning to parse natural language to grounded reward functions with weak supervision. In _2018 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 1–7.
  * Zhong et al. (2017) Victor Zhong, Caiming Xiong, and Richard Socher. 2017\.  Seq2SQL: Generating Structured Queries from Natural Language using Reinforcement Learning.  _CoRR_ abs/1709.00103 (2017).