# Chebotarëv’s nonvanishing minors for eigenvectors of random matrices and
graphs

Tarek Emmrich

###### Abstract

For a matrix $\mathbf{M}\in\mathbb{K}^{n\times n}$ we establish a condition on
the Galois group of the characteristic polynomial $\varphi_{\mathbf{M}}$ that
induces nonvanishing of the minors of the eigenvector matrix of $\mathbf{M}$.
For $\mathbb{K}=\mathbb{Z}$ recent results by Eberhard show that,
conditionally on the extended Riemann hypothesis, this condition is satisfied
with high probability111We say ”with high probability” for probability
$1-o(1)$ as $n\to\infty$.  and hence with high probability the minors of
eigenvector matrices of random integer matrices are nonzero. For random graphs
this yields a novel uncertainty principle, related to Chebotarëv’s theorem on
the roots of unity and results from Tao[18] and Meshulam[12]. We also show the
application in graph signal processing and the connection to the rank of the
walk matrix.

_Keywords_ : Nonvanishing minors, Spectral graph theory.

_2020 AMS Mathematics Subject Classification_ :  05C25, 65T50, 15B52, 05C50,

##  1 Introduction

For the Fourier matrix there is Chebotarëv’s famous theorem on the
nonvanishing of the minors, see [17] for a survey.

######  Theorem 1.

[17] Let $p$ be a prime and $\mathbf{F}$ be the Fourier matrix of order $p$,
i.e., $\mathbf{F}_{i,j}=\omega^{(i-1)(j-1)}$ for $\omega=e^{\frac{2\pi
i}{p}}$. Then all minors of $\mathbf{F}$ are nonzero.

From the viewpoint of spectral graph theory, the matrix $\mathbf{F}$ is a
possible eigenvector matrix of the circle graph and this yields the
uncertainty principle

$\|f\|_{0}+\|\hat{f}\|_{0}\geq p+1$

for any function $f$ on the circle graph and its Graph Fourier transform
$\hat{f}=\mathbf{F}^{*}f$, see Tao [18] and Meshulam [12] for uncertainty
principles. We will prove the following criterion on nonvanishing of the
minors of the eigenvector matrix of any matrix
$\mathbf{M}\in\mathbb{K}^{n\times n}$. Let $\varphi_{\mathbf{M}}$ be the
characteristic polynomial of $\mathbf{M}$ and $\mathbb{L}$ its splitting
field. We denote by $\operatorname{Gal}(\varphi_{\mathbf{M}})$ the Galois
group of the field extension $\mathbb{K}\subseteq\mathbb{L}$. Furthermore, if
$\mathbf{M}$ is diagonalizable, let $\mathbf{U}$ be the matrix with columns
$u_{i}$ that are eigenvectors corresponding to the eigenvalue $\lambda_{i}$ of
$\mathbf{M}$.

######  Theorem 2.

Let $\mathbf{U}$ be the eigenvector matrix of a diagonalizable matrix
$\mathbf{M}$. If $\operatorname{Gal}(\varphi_{\mathbf{M}})\geq A_{n}$, then
all minors of $\mathbf{U}$ are nonzero.

Note that for $\operatorname{Gal}(\varphi_{\mathbf{M}})\geq A_{n}$,
$\mathbf{M}$ is always diagonalizable. For various reasons we care about the
minors of the eigenvector matrices of operators an graphs. The two widely
studied operators on graphs are the adjacency matrix and the Laplacian matrix.
For directed graphs the directed adjacency matrix seems to be the most
interesting.

For a fixed finitely supported measure $\mu$ on $\mathbb{Z}$, let $\mathbf{M}$
be a random matrix with $m_{i,j}\sim\mu$. In this case Eberhard [5] proved
that, conditionally on the extended Riemann hypothesis, with high probability
$\varphi_{\mathbf{M}}$ is irreducible and
$\operatorname{Gal}(\varphi_{\mathbf{M}})\geq A_{n}$. This directly leads to
the following corollary, which induces an uncertainty principle for directed
graphs and their adjacency matrices.

######  Corollary 3.

Assume the extended Riemann hypothesis. For a random matrix $\mathbf{M}$, with
$m_{i,j}\sim\mu$, with high probability all minors of the eigenvector matrix
$\mathbf{U}$ of $\mathbf{M}$ are nonzero.

Following Eberhard’s results, Ferber, Jain, Sah and Sawhney [7] could show
that the Galois group of a random symmetric matrix is almost surely
transitive, which we will see is not sufficient for minors of arbitrary size
to be nonzero, but for minors of size one.

######  Corollary 4.

Let $\mathbf{M}$ be the adjacency matrix of a random Erdős–Rényi graph $G\sim
G(n,p)$ and assume the extended Riemann hypothesis. Then with high probability
no eigenvector of $\mathbf{M}$ contains a zero.

Working with the Laplacian matrix of a random graph on $n$ vertices has the
difficulty that the rank of the Laplacian matrix of a connected graph is $n-1$
by default. We can overcome this problem by using the factorization
$\varphi_{\mathbf{L}}(\lambda)=\lambda\cdot\xi(\lambda)$, but still known
results for random matrices do not apply. For applications, the most
interesting case is the following uncertainty principle that follows directly
from our results.

######  Theorem 5.

Let $G$ be a graph on $n$ vertices and
$\varphi_{\mathbf{L}}(\lambda)=\lambda\cdot\xi(\lambda)$. If
$\operatorname{Gal}(\xi)\geq A_{n-1}$, then all minors of $\mathbf{U}$ are
nonzero, i.e.

$\|f\|_{0}+\|\hat{f}\|_{0}\geq n+1$

for any signal $f\neq 0$ on the graph $G$. Here the Graph Fourier transform
$\hat{f}$ is given by $\hat{f}=\mathbf{U}^{*}f$.

The Fourier matrix can be seen as the eigenvector matrix of the shift matrix.
Its characteristic polynomial is

$\lambda^{p}-1=(\lambda-1)\cdot\sum_{k=0}^{p-1}\lambda^{k}:=\lambda\cdot\xi(\lambda)$

with splitting field $\mathbb{L}=\mathbb{Q}[\lambda]/\xi(\lambda)$ and Galois
group $(\mathbb{Z}/p\mathbb{Z})^{\times}$, which is surprisingly not
sufficient for our results to hold.

The eigenvectors of random matrices with continuous distribution have been
widely studied in the past, for a survey see [14], but as far as we know the
minors have not been studied in the discrete case. In the discrete setting the
most common application are graphs. Brooks and Lindenstrauss [2] proved a non-
localization for the eigenvectors of the normalized Laplacian matrix of large
regular graphs, i.e. small subsets of vertices only contain a small part of
the mass of an eigenvector. Alt, Ducatez and Knowles [1] determined regions
for the edge probability $p=\frac{d}{N}$ of an Erdős–Rényi graph, such that
the eigenvectors are delocalized. Both statements are relatively far away from
a statement about minors. A very well studied object is the walk matrix
$\mathbf{W}$ of a graph and we will establish a connection between this rank
and the minors of $\mathbf{U}$. The construction is well known in other areas
of mathematics as Krylov spaces [16].

Outline. After introducing notations and the necessary background in Section
2, we will establish our main results and a slight variation of it in Section
3. We discuss several applications in Section 4. We end by extending the
results to Laplacian matrices and by giving examples.

##  2 Background

In this section we will shortly introduce some notation and the background of
Galois theory, for a more detailed summary see [13]. For a polynomial
$\varphi\in\mathbb{Q}[\lambda]$ of degree $n$ the fundamental theorem of
algebra tells us that $\varphi$ has exactly $n$ roots $\lambda_{i}$,
$i=1,\ldots,n,$ over the complex numbers $\mathbb{C}$. Instead of working over
the complex numbers, we will work over the splitting field
$\mathbb{L}=\mathbb{Q}(\lambda_{i}\colon i\in[n])$ of $\varphi$, which is the
smallest field extension of $\mathbb{Q}$ that contains all roots of $\varphi$.
The dimension of the splitting field is bounded by

$\operatorname{dim}_{\mathbb{Q}}(\mathbb{L})\leq n!\ .$

The splitting field can also be constructed inductively by the step
$\mathbb{Q}\subseteq\mathbb{K}_{1}:=\mathbb{Q}[\lambda]/R(\lambda)$ that adds
at least one root of $\varphi$, where $R(\lambda)$ is an irreducible factor of
$\varphi$. After at most $n$ steps all roots of $\varphi$ are contained in the
resulting field $\mathbb{L}$. The structure of this adding process is encoded
in the Galois group

$\operatorname{Gal}(\varphi):=\operatorname{Aut}_{\mathbb{Q}}(\mathbb{L})\subseteq\operatorname{Sym}(\\{\lambda_{1},\ldots,\lambda_{n}\\})\cong
S_{n}.$

In most cases we will interpret the Galois group of any polynomial as a group
acting on the set $[n]$ by the given isomorphism. In the generic case over the
rational numbers, Hilbert’s irreducibility theorem tells us that

$\operatorname{Gal}(\varphi)\cong S_{n}.$

Two algebraic numbers $\mu_{1},\mu_{2}$ are called conjugate, if they have the
same minimal polynomial $\varphi$ over $\mathbb{Q}$. For two conjugate
algebraic numbers $\mu_{1},\mu_{2}$, there is a
$g\in\operatorname{Gal}(\varphi)$ with $g(\mu_{1})=\mu_{2}$. We call a group
$H\subseteq\operatorname{Sym}(\\{\lambda_{1},\ldots,\lambda_{n}\\})$
$m$-homogeneous, if for all $S,S^{\prime}\in\binom{[n]}{m}$ there exists a
$g\in H$ such that

$g(\\{\lambda_{i}|i\in S\\})=\\{\lambda_{i}|i\in S^{\prime}\\}.$

The prior fact tells us, that the Galois group of an irreducible polynomial is
$1$-homogeneous (which in this case equals transitivity). For a matrix
$\mathbf{U}$ and $W,S\subseteq[n]$ we write $\mathbf{U}_{W,S}$ for the
submatrix of $\mathbf{U}$ with rows induced by $W$ and columns induced by $S$.

For a tuple $B=(b_{1},\ldots,b_{k})\in\mathbb{C}^{k}$ we define the
Vandermonde matrix

$\mathbf{V}(B)=\left(b_{j}^{i}\right)_{{j=1,\ldots,k}\atop{i=0,\ldots,k-1}}.$

It is well known that this matrix is invertible if and only if all values in
$B$ are distinct.

For a finite set $V$ and $E\subseteq\binom{V}{2}$ we call $G=(V,E)$ a graph
and we often assume $V=[n]$. The elements of $V$ are called the vertices. We
say two vertices $v,w$ are connected, if $\\{v,w\\}\in E$ and sometimes write
$v\sim w$. For two vertices $v,w$ the distance $d(v,w)$ is the smallest
integer $r$ such that there exist vertices $v=v_{0},v_{1},\ldots,v_{r}=w$ with
$\\{v_{k},v_{k+1}\\}\in E$. The adjacency matrix
$\mathbf{A}\in\\{0,1\\}^{n\times n}$ of $G$ is defined by

$\mathbf{A}_{v,w}=\begin{cases}1,\text{ if }\\{v,w\\}\in E,\\\ 0,\text{
otherwise}.\end{cases}$

The combinatorial Laplacian matrix $\mathbf{L}\in\mathbb{Z}^{n\times n}$ is
the matrix $\mathbf{L}=\mathbf{D}-\mathbf{A}$, with
$\mathbf{D}_{v,v}=\operatorname{degr}(v)$. For a connected graph, the rank of
the Laplacian matrix is $n-1$ with the kernel vector $\mathds{1}$.

A matrix $\mathbf{U}\in\mathbb{K}^{n\times n}$ is orthonormal, if

$\mathbf{U}\mathbf{U}^{*}=\mathbf{U}^{*}\mathbf{U}=\mathbf{E}_{n}.$

For an orthonormal matrix $\mathbf{U}\in\mathbb{K}^{n\times n}$ and a vector
$f\in\mathbb{K}^{n}$ we denote

$\hat{f}:=\mathbf{U}^{*}f.$

If $\mathbf{U}$ is the eigenvector matrix of the Laplacian matrix, $\hat{f}$
is called the Graph Fourier transform, with the inverse transformation

$f=\mathbf{U}\hat{f}.$

We say a vector $f\in\mathbb{K}^{n}$ is $s$-sparse, if the size of its support
equals $s$. We denote the size of the support of a vector $f$ also by

$\|f\|_{0}:=\\#\\{i\in[n]:f(i)\neq 0\\}.$

##  3 Minors and Galois groups

Let $\mathbf{M}\in\mathbb{K}^{n\times n}$ be a diagonalizable matrix, let
$\varphi_{\mathbf{M}}$ be its characteristic polynomial with splitting field
$\mathbb{L}$. We denote the eigenvalues and eigenvectors by
$\lambda_{1},\ldots,\lambda_{n}\in\mathbb{L}$ and
$u_{1},\ldots,u_{n}\in\mathbb{L}^{n}$. The eigenvector matrix $\mathbf{U}$ is
the matrix with columns $u_{i}$. For any two conjugate elements
$\lambda_{i},\lambda_{j}$ there exists
$g\in\operatorname{Gal}(\varphi_{\mathbf{M}})$ such that
$g(\lambda_{i})=\lambda_{j}$. Applying this $g$ to the eigenvector equation
$\mathbf{M}u_{i}=\lambda_{i}u_{i}$ we get

$\displaystyle g(\mathbf{M})g(u_{i})=\lambda_{j}g(u_{i}).$ (1)

Since $\mathbf{M}\in\mathbb{K}^{n\times n}$ and $g_{|\mathbb{K}}$ is the
identity, we have $g(\mathbf{M})=\mathbf{M}$ and hence the equation (1) tells
us $g(u_{i})=u_{j}$. We denote by $u_{i}^{J}$ the restriction of the $i$-th
eigenvector to the rows with indices in $J$. We are now ready to prove Theorem
2.

###### Proof of Theorem 2.

Assume there are sets $S,W\in\binom{[n]}{m}$ for some $m\in[n]$ such that
$\det(\mathbf{U}_{W,S})=0$. Let $a_{1},\ldots,a_{m}\in\mathbb{L}$ be the
coefficients such that

$\sum_{i\in S}a_{i}u_{i}^{W}=0^{W}.$

Since $\operatorname{Gal}(\varphi_{\mathbf{M}})$ is $m$-homogeneous, there
exists $g\in\operatorname{Gal}(\varphi_{M})$ with $g(\\{\lambda_{i}|i\in
S\\})=\\{\lambda_{i}|i\in S^{\prime}\\}$ for all
$S^{\prime}\in\binom{[n]}{m}$. This yields

$\sum_{i\in S^{\prime}}g(a_{i})u_{i}^{W}=0^{W}$

for all $S^{\prime}\in\binom{[n]}{m}$ and hence
$\operatorname{rank}(\mathbf{U}_{W,[n]})=m-1$, a contradiction to the rows of
$\mathbf{U}$ being linearly independent. ∎

Eberhard[5, Theorem 1.3] proved that, conditionally on the extended Riemann
hypothesis, the Galois group of the characteristic polynomial of a random
matrix is almost surely $A_{n}$ or $S_{n}$ and hence Corollary 3 follows.
Under the same condition Ferber, Jain, Sah and Sawhney [7, Theorem 1.1] could
show that the characteristic polynomial of a random symmetrix matrix is almost
surely irreducible. Thus Corollary 4 follows.

Our condition $\operatorname{Gal}(\varphi_{\mathbf{M}})\geq A_{n}$ is slightly
stronger than just the $m$-homogeneity. Kantor[10][Theorem 1] was able to show
that only for $m=2,3,4$ there are groups that are $m$-homogeneous, but not
$m$-transitive. Additionally, by the classification of finite simple groups,
it was proven that for $m\geq 6$ there is no $m$-transitive group other than
$A_{n}$ or $S_{n}$[3]. The most precise way to state the connection is the
following.

######  Theorem 6.

Let $\mathbf{U}$ be the eigenvector matrix of a diagonalizable matrix
$\mathbf{M}$ with characteristic polynomial $\varphi_{\mathbf{M}}$. If the
Galois group $\operatorname{Gal}(\varphi_{\mathbf{M}})$ is m-homogeneous, then
all minors of size $m$ and $(n-m)$ do not vanish. In particular, if the group
$\operatorname{Gal}(\varphi_{\mathbf{M}})$ is transitive, i.e. the polynomial
$\varphi_{\mathbf{M}}$ is irreducible, the matrix $\mathbf{U}$ does not
contain a zero.

The proof relies on the proof of Theorem 2 in connection with the following
lemma. This lemma will also be useful for the eigenvector matrix of the
Laplacian matrix, that requires some special treatment.

######  Lemma 7.

Let $\mathbf{U}$ be the a matrix with orthogonal columns $u_{i}$. If there are
sets $W,S\in\binom{[n]}{m}$ such that the vectors $(u_{i}^{W})_{i\in S}$ are
linearly dependent, then the vectors $(u_{i}^{[n]\setminus
W})_{i\in[n]\setminus S}$ are also linearly dependent.

###### Proof.

Let $a_{i}\in\mathbb{R}$ be the coefficients such that

$\sum_{i\in S}a_{i}u_{i}^{W}=0^{W}.$

For $j\notin S$ we have $\langle u_{j},u_{i}\rangle=0$ for all $i\in S$ and it
follows that

$\displaystyle 0$ $\displaystyle=\langle u_{j},\sum_{i\in S}a_{i}u_{i}\rangle$
$\displaystyle=\langle u_{j}^{W},\sum_{i\in S}a_{i}u_{i}^{W}\rangle+\langle
u_{j}^{[n]\setminus W},\sum_{i\in S}a_{i}u_{i}^{[n]\setminus W}\rangle$
$\displaystyle=0+\langle u_{j}^{[n]\setminus W},\sum_{i\in
S}a_{i}u_{i}^{[n]\setminus W}\rangle.$

Since the vectors $u_{i}$ are linearly independent we know that $\sum_{i\in
S}a_{i}u_{i}\neq 0^{[n]}$ and hence

$\sum_{i\in S}a_{i}u_{i}^{[n]\setminus W}\neq 0^{[n]\setminus W}.$

Now the $(n-m)$ vectors $u_{j}^{[n]\setminus W}$ of length $(n-m)$ lie in the
hyperplane orthogonal to $\sum_{i\in S}a_{i}u_{i}^{[n]\setminus W}$ and
therefore are linearly dependent. ∎

35784621 Figure 1: A graph with 1-homogeneous Galois group
$\operatorname{Gal}(\varphi_{\mathbf{A}})<A_{8}$, but vanishing minors.

The characteristic polynomial of the adjacency matrix of the graph in figure 1
has the characteristic polynomial

$\varphi_{\mathbf{A}}=\lambda^{8}-10\lambda^{6}-4\lambda^{5}+23\lambda^{4}+12*\lambda^{3}-12\lambda^{2}-4\lambda+1,$

that is irreducible, but with the Galois group

$\operatorname{Gal}(\varphi_{\mathbf{A}})\cong\left\\{\sigma\in
S_{8}\colon\sigma(\\{1,2,3,4\\})\in\\{\\{1,2,3,4\\},\\{5,6,7,8\\}\\}\right\\}.$

The problem of vanishing minors originally appeared in the analysis of an
algorithm [6], that recovers sparse signals on graphs, whose success relies on
the regularity of the matrix

$\mathbf{G}_{v,j}=f_{v}(j)$

with $f_{v}(j)=\sum_{i\in S}\lambda_{i}^{j}u_{i}(v)$ for $0\leq j\leq s-1$ and
$v\in W\subseteq[n]$. The factorization
$\mathbf{G}=\mathbf{U}_{W,S}\cdot\mathbf{V}(\lambda_{i}:i\in S)$ yields the
connection to minors. A slighty improved version of this algorithm relies on
the regularity of the following matrix

$\tilde{\mathbf{G}}=\begin{pmatrix}f_{1}(0)&f_{1}(1)&\ldots&f_{1}(s-1)\\\
f_{1}(1)&f_{1}(2)&\ldots&f_{1}(s)\\\ \vdots&\vdots&&\vdots\\\
f_{1}(r_{1}-1)&f_{1}(r_{1})&\ldots&f_{1}(s-2+r_{1})\\\
f_{2}(0)&f_{2}(1)&\ldots&f_{2}(s-1)\\\ f_{2}(1)&f_{2}(2)&\ldots&f_{2}(s)\\\
\vdots&\vdots&&\vdots\\\
f_{k}(r_{k}-1)&f_{k}(r_{k})&\ldots&f_{k}(s-2+r_{k})\end{pmatrix}$

for some radii $\sum_{i=1}^{k}r_{i}=m$ and corresponding vertices
$W=\\{v_{1},\ldots,v_{k}\\}$. This matrix has the factorization

$\tilde{\mathbf{G}}=\underbrace{\begin{pmatrix}u_{j_{1}}(v_{1})&u_{j_{2}}(v_{1})&\ldots&u_{j_{s}}(v_{1})\\\
\lambda_{j_{1}}u_{j_{1}}(v_{1})&\lambda_{j_{2}}(v_{1})&\ldots&l_{j_{s}}u_{j_{s}}(v_{1})\\\
\vdots&\vdots&&\vdots\\\
\lambda_{j_{1}}^{r_{1}-1}u_{j_{1}}(v_{2})&\lambda_{j_{2}}^{r_{1}-1}u_{j_{2}}(v_{2})&\ldots&\lambda_{j_{s}}^{r_{1}-1}u_{j_{s}}(v_{2})\\\
u_{j_{1}}(v_{2})&u_{j_{2}}(v_{2})&\ldots&u_{j_{s}}(v_{2})\\\
\lambda_{j_{1}}u_{j_{1}}(v_{2})&\lambda_{j_{2}}(v_{2})&\ldots&l_{j_{s}}u_{j_{s}}(v_{2})\\\
\vdots&\vdots&&\vdots\\\
\lambda_{j_{1}}^{r_{k}-1}u_{j_{1}}(v_{k})&\lambda_{j_{2}}^{r_{k}-1}u_{j_{2}}(v_{k})&\ldots&\lambda_{j_{s}}^{r_{k}-1}u_{j_{s}}(v_{k})\end{pmatrix}}_{:=\mathbf{G}(S,W,r_{1},\ldots,r_{k})}\cdot\mathbf{V}(\lambda_{i}:i\in
S),$

for $W=\\{v_{i}:1\leq i\leq k\\}$ and $S=\\{j_{i}:1\leq i\leq s\\}$. Note that
the rows of each vertex-block are linearly independent as soon as
$u_{j}(v)\neq 0$ for $j\in S$. The next matrix is a small example of such a
matrix.

$\mathbf{G}\left(\\{1,2\\},\\{v,w\\},2,2\right)=\begin{pmatrix}u_{1}(v)&u_{2}(v)&u_{3}(v)&u_{4}(v)\\\
\lambda_{1}u_{1}(v)&\lambda_{2}u_{2}(v)&\lambda_{3}u_{3}(v)&\lambda_{4}u_{4}(v)\\\
u_{1}(w)&u_{2}(w)&u_{3}(w)&u_{4}(w)\\\
\lambda_{1}u_{1}(w)&\lambda_{2}u_{2}(w)&\lambda_{3}u_{3}(w)&\lambda_{4}u_{4}(w)\end{pmatrix}.$

######  Theorem 8.

Let $\mathbf{U}$ be the eigenvector matrix of $\mathbf{A}$. The matrix
$\mathbf{G}(S,W,r_{1},\ldots,r_{k})$ has full rank, if
$\operatorname{Gal}(\varphi_{\mathbf{A}})\geq A_{n}$ and
$d(v_{i},v_{j})>r_{i}+r_{j}$ for all $1\leq i,j\leq k$.

###### Proof.

Assume $\operatorname{rank}(\mathbf{G}(S,W,r_{1},\ldots,r_{k}))<s$. Then there
are coefficients $a_{i}$ such that

$\sum_{i\in S}a_{i}\lambda_{i}^{k_{i}}u_{i}(v)=0$

for $v\in W$ and $0\leq k_{i}\leq r_{k}-1$. Applying each
$\gamma\in\operatorname{Gal}(\varphi_{A})$ yields
$\operatorname{rank}(\mathbf{G}([n],W,r_{1},\ldots,r_{k}))<s$. Let $Z_{v,m}$
be the row of $\mathbf{G}([n],W,r_{1},\ldots,r_{k})$ belonging to vertex $v$
and power $m$. We have

$\displaystyle\langle Z_{v,m},Z_{w,l}\rangle$
$\displaystyle=\sum_{i=1}^{n}\lambda_{i}^{m+l}u_{i}(v)u_{i}(w)$
$\displaystyle=\mathbf{A}_{v,w}^{m+l}.$

And hence we know that $\langle Z_{v,m},Z_{w,l}\rangle=0$ for $d(v,w)>m+l$.
This yields that the intersection of the span of the blocks is $0$, if the
distance condition is fulfilled. Again, if
$\operatorname{Gal}(\varphi_{\mathbf{A}})\geq A_{n}$, then the blocks have
full rank and hence the matrix $\mathbf{G}([n],W,r_{1},\ldots,r_{k})$ can not
be singular, a contradiction. ∎

##  4 Consequences of nonvanishing minors and applications

There are several consequences of the minors of the eigenvector matrix being
nonzero. The first one is an uncertainty principle similar to the one from
Tao.

######  Theorem 9.

[18, Theorem 1.1] Let $\mathbf{U}\in\mathbb{K}^{n\times n}$ be a matrix. All
minors of any size of $\mathbf{U}$ are nonzero if and only if

$\|f\|_{0}+\|\hat{f}\|_{0}\geq n+1.$

###### Proof.

Assume some minor of $\mathbf{U}$ is zero. Then there are coefficients
$a_{i}\in\mathbb{K}$ such that $\sum_{i\in I}a_{i}u_{i}^{J}=0^{J}$ for
$\\#I=\\#J=m$. The vector

$f(i)=\begin{cases}a_{i}\ \text{ for }i\in I,\\\ 0\ \ \text{
else.}\end{cases}$

has support of size $m$. This choice yields $(\mathbf{U}f)^{J}=0^{J}$ and
hence

$\|f\|_{0}+\|\mathbf{U}f\|_{0}\leq m+(n-m)=n.$

Assume $\|f\|_{0}+\|\hat{f}\|_{0}=n$ and denote $\|f\|_{0}=r$. Let
$W=\operatorname{supp}(f)$ be the support of $f$ and
$S=\operatorname{supp}(\hat{f})$ be the support of $\hat{f}$ with $\\#S=n-r$.
Restricting $\mathbf{U}$ to the columns belonging to $S$ yields

$\mathbf{U}_{[n],S}\hat{f}_{S}=f,$

which means that the minor $\mathbf{U}_{[n]\setminus W,S}$ is zero, a
contradiction. ∎

Another well known consequence is the following application to sparse
recovery.

######  Theorem 10.

[8, Theorem 2.13] Let $G$ be a graph with vertex set $[n]$ and
$\mathbf{M}=\mathbf{U}\Lambda\mathbf{U}^{*}$ for
$\mathbf{M}\in\\{\mathbf{L},\mathbf{A}\\}$ with nonvanishing minors of
$\mathbf{U}$ of any size. For any $1\leq s\leq n$ pick any
$W,S\in\binom{[n]}{s}$, then each $s$-sparse signal

$f=\sum_{w\in W}a_{w}\delta_{w}$

is uniquely determined by at least $2s$ samples of the form

$\langle u_{i},f\rangle.$

Let $\mathbf{U}$ be the eigenvector matrix of
$\mathbf{M}\in\\{\mathbf{L},\mathbf{A}\\}$ and let $0\neq x\in\mathbb{R}^{n}$
be a vector. One interesting object to study is the so called walk matrix, see
e.g. [4][9][11][15],

$\mathbf{W}(x):=\begin{pmatrix}|&|&|&|&|\\\
x&\mathbf{M}x&\mathbf{M}^{2}x&\cdots&\mathbf{M}^{n-1}x\\\
|&|&|&|&|\end{pmatrix}$

and its rank, depending on $x$. Let $0\leq r\leq n-1$ be the minimal number
such that there are coefficients $a_{0},\ldots,a_{r}$ with

$\sum_{k=0}^{r}a_{k}\mathbf{M}^{k}x=0^{[n]}.$

Then $r$ is the degree of the polynomial
$Q(\lambda)=\sum_{k=0}^{r}a_{k}\lambda^{k}$ and also the rank of $\mathbf{W}$,
because each set of columns with indices in $\\{i,\ldots,i+r\\}$ will have the
kernel

$(a_{0},\ldots,a_{r})^{T}.$

The next theorem describes the connection between the choice of $x$, the rank
of the walk matrix and the nonvanishing of minors of $\mathbf{U}$.

######  Theorem 11.

Let $G$ be a graph on $n$ vertices, $0\neq x\in\mathbb{R}^{n}$ and let
$\mathbf{W}(x)$ be the walk matrix for $\mathbf{M}=\mathbf{A}$.

  1. 1.

If $\varphi_{\mathbf{A}}$ is irreducible and $x\in\mathbb{Q}^{n}$, then

$\operatorname{rank}(\mathbf{W}(x))=n.$

  2. 2.

For more general $0\neq x\in\mathbb{R}^{n}$ we have

$\operatorname{rank}(\mathbf{W}(x))=\|\mathbf{U}^{*}x\|_{0}=\|\hat{x}\|_{0}.$

  3. 3.

If all minors of $\mathbf{U}$ are nonvanishing, the following formula holds

$\operatorname{rank}(\mathbf{W}(x))\geq n+1-\|x\|_{0}.$

###### Proof.

In a first step we will show the following equation

$\operatorname{rank}(\mathbf{W}(x))=n-\|\mathbf{U}^{*}x\|_{0}.$

Let $Q=\sum_{k=0}^{r}a_{k}\lambda^{k}$ be the polynomial with coefficients
$a_{k}$, that are the kernel of $\mathbf{W}(x)$, i.e.,

$\displaystyle Q(\mathbf{A})\cdot
x=\sum_{k=0}^{r}a_{k}\mathbf{A}^{k}x=0^{[n]},$

which is equivalent to

$\displaystyle\sum_{k=0}^{r}a_{k}\sum_{w=1}^{n}\mathbf{A}_{v,w}^{k}x_{w}=0\text{
for all }v.$ (2)

The diagonalization of $\mathbf{A}$ yields

$\mathbf{A}_{v,w}^{k}=\sum_{l=1}^{n}u_{l}(v)u_{l}(w)\lambda_{l}^{k}$

and we want to use this equation to obtain a formula for
$\left(Q(\mathbf{A})\cdot x\right)$ that gives more insight

$\displaystyle\sum_{k=0}^{r}a_{k}\sum_{w=1}^{n}\mathbf{A}_{v,w}^{k}x_{w}$
$\displaystyle=\sum_{k=0}^{r}a_{k}\sum_{w=1}^{n}\left(\sum_{l=1}^{n}u_{l}(v)u_{l}(w)\lambda_{l}^{k}\right)x_{w}$
$\displaystyle=\sum_{l=1}^{n}u_{l}(v)\sum_{w=1}^{n}x_{w}u_{l}(w)\sum_{k=0}^{r}a_{k}\lambda_{l}^{k}$
$\displaystyle=\sum_{l=1}^{n}u_{l}(v)\sum_{w=1}^{n}x_{w}u_{l}(w)Q(\lambda_{l}).$

We can see now that equation (2) is equivalent to

$\sum_{l=1}^{n}u_{l}(v)Q(\lambda_{l})\sum_{w=1}^{n}x_{w}u_{l}(w)=0\text{ for
all }v.$

This condition reads as

$\left\langle\left(u_{l}(v)\right)_{l=1,\ldots,n},\left(Q(\lambda_{l})\sum_{w=1}^{n}x_{w}u_{l}(w)\right)_{l=1,\ldots,n}\right\rangle=0\text{
for all }v$

and since the vectors $(u_{l}(v))_{l=1,\ldots,n}$ form a basis this yields

$Q(\lambda_{l})\sum_{w=1}^{n}x_{w}u_{l}(w)=0$

for all $l$. The second vector can be written as

$\left(\sum_{w=1}^{n}w_{x}u_{l}(w)\right)_{l=1,\ldots,n}=\mathbf{U}^{*}x$

Thus we have

$\operatorname{rank}(\mathbf{W})(x)=n-\|\mathbf{U}^{*}x\|_{0}.$

Now for the first point, observe that $x\in\mathbb{Q}^{n}$ implies
$a_{k}\in\mathbb{Q}$ and hence $a_{k}\in\mathbb{Z}$ and thus $Q$ divides
$\varphi_{\mathbf{A}}$ in the polynomial ring $\mathbb{Q}[X]$. If
$\varphi_{\mathbf{A}}$ is irreducible, either $Q=\varphi_{\mathbf{A}}$ or
$Q=1$. The case $Q=1$ is not possible for $x\neq 0$ and hence
$\operatorname{rank}(\mathbf{W})=n$ for $\varphi_{\mathbf{A}}$ irreducible and
$x\in\mathbb{Q}^{n}$.

For not necessarily rational $x\in\mathbb{R}^{n}$ we see that

$\operatorname{rank}(\mathbf{W}(x))=\|\mathbf{U}^{*}x\|_{0}=\|\hat{x}\|_{0}.$

If we restrict the size of the support of $x$, i.e., $\|x\|_{0}=s$,
nonvanishing minors and Theorem 9 yield

$\operatorname{rank}(\mathbf{W}(x))\geq n+1-s.$

∎

##  5 Laplacian matrices

We now formulate the analog versions of the prior theorems for the Laplacian
matrices with necessary changes. Let $\xi(\lambda)$ be the unique polynomial
with $\varphi_{L}=\lambda\cdot\xi(\lambda)$.

######  Theorem 12.

Let $G$ be a graph on $n$ vertices and $\mathbf{U}$ be the eigenvector matrix
of the Laplacian matrix $\mathbf{L}$ with characteristic polynomial
$\varphi_{L}=\lambda\cdot\xi$. If $\operatorname{Gal}(\xi)\geq A_{n-1}$, then
we have

$\operatorname{det}\left(\mathbf{U}_{W,S}\right)\neq 0$

for all $W,S\in\binom{[n]}{m}$.

###### Proof.

By Lemma 7 we can assume $1\notin S$. If
$\operatorname{det}\left(\mathbf{U}_{W,S}\right)=0$ for some
$W,S\in\binom{[n]}{m}$, we know that
$\operatorname{det}\left(\mathbf{U}_{W,S^{\prime}}\right)$=0 for all
$S^{\prime}\in\binom{\\{2,\ldots,n\\}}{m}$ by applying the $m$-homogeneous
Galois group to the equation and hence

$\operatorname{rank}\left(\mathbf{U}_{W,\\{2,\ldots,n\\}}\right)=m-1.$

Thus there are coefficients $a_{w}\in\mathbb{K}$ for $w\in W$ such that

$\sum_{w\in W}a_{w}\tilde{u}(w)=0,$

where $\tilde{u}(w)=(u_{i}(w))_{i=2,\ldots,n}$. For $v\notin W$ we know that
$\langle u(v),u(w)\rangle=0$ and hence

$\displaystyle 0$ $\displaystyle=\langle u(v),\sum_{w\in W}a_{w}u(w)\rangle$
$\displaystyle=\langle u_{1}(v),\sum_{w\in
W}a_{w}u_{1}(w)\rangle+\langle\tilde{u}(v),\sum_{w\in
W}a_{w}\tilde{u}(v)\rangle$ $\displaystyle=u_{1}(v)\cdot\sum_{w\in
W}a_{w}u_{1}(w).$

Now since the vectors $u(w)$ are linearly independent for $w\in W$ we know
that $\sum_{w\in W}a_{w}u_{1}(w)\neq 0$ and together with
$u_{1}(v)=\frac{1}{\sqrt{n}}\neq 0$ this yields a contradiction. ∎

Theorem 5 follows now from the fact that $A_{n-1}$ and $S_{n-1}$ are
$m$-homogeneous and Lemma 7. Moreover, if $\xi$ is irreducible, it also
follows directly from Theorem 12 that all eigenvectors do not contain a zero.
Furthermore, if $\operatorname{Gal}(\xi)$ is $m$-homogeneous, then all minors
of $\mathbf{U}$ of size $m$ are nonzero.

######  Theorem 13.

Let $G$ be a graph on $n$ vertices, $0\neq x\in\mathbb{R}^{n}$ and let
$\mathbf{W}(x)$ be the walk matrix for $\mathbf{M}=\mathbf{L}$ with
characteristic polynomial $\varphi_{L}=\lambda\cdot\xi$.

  1. 1.

If $\xi(\lambda)$ is irreducible and $x\in\mathbb{Q}^{n}$, then

$\operatorname{rank}(\mathbf{W}(x))=n.$

  2. 2.

For more general $0\neq x\in\mathbb{R}^{n}$ we have

$\operatorname{rank}(\mathbf{W})=\|\mathbf{U}^{*}x\|_{0}=\|x\|_{0}.$

  3. 3.

If all minors of $\mathbf{U}$ are nonvanishing, the following formula holds

$\operatorname{rank}(\mathbf{W})\geq n+1-\|x\|_{0}.$

The only change in the proof in comparison to Theorem 11 is the use of
$\lambda_{1}=0$ and $u_{1}=\mathds{1}$.

######  Theorem 14.

Let $G$ be a graph on $n$ vertices and $\mathbf{U}$ be the eigenvector matrix
of the Laplacian matrix $\mathbf{L}$ with characteristic polynomial
$\varphi=\lambda\cdot\xi$. The matrix $\mathbf{G}(S,W,r_{1},\ldots,r_{k})$ has
full rank, if $\operatorname{Gal}(\xi)\geq A_{n-1}$ and
$d(v_{i},v_{j})>r_{i}+r_{j}$ for all $1\leq i,j\leq k$.

###### Proof.

By a similar argument as in the proof of Theorem 8, we get that singularity of
$\mathbf{G}(S,W,r_{1},\ldots,r_{k})$ yields singularity of
$\mathbf{G}(\\{2,\ldots,n\\},W,r_{1},\ldots,r_{k})$. Let $Z_{v,m}$ be the row
of $\mathbf{G}(\\{2,\ldots,n\\},W,r_{1},\ldots,r_{k})$ belonging to vertex $v$
and power $m$. For $m+l>0$ we have

$\displaystyle\langle Z_{v,m},Z_{w,l}\rangle$
$\displaystyle=\sum_{i=2}^{n}\lambda^{m+l}u_{i}(v)u_{i}(w)$
$\displaystyle=\mathbf{L}_{v,w}^{m+l}.$

The radius condition yields orthogonality for $m+l>0$. The rows belonging to
power $0$ can not be linearly dependent according to Theorem 12. ∎

We finally provide two examples.

######  Example 15.

The graph in Figure 2 has the characteristic polynomial

$\varphi=\lambda\cdot\left(\lambda^{8}-28\lambda^{7}+332\lambda^{6}-2170\lambda^{5}+8516\lambda^{4}-20440\lambda^{3}+29105\lambda^{2}-22288\lambda+6957\right).$

The Galois group of $\xi$ has order $384$ and is given by

$\operatorname{Gal}(\xi)\cong\left\\{\sigma\in
S_{8}\colon\sigma(i+4)=\begin{cases}\sigma(i)+4\text{ , for $\sigma(1)\leq
4$},\\\ \sigma(i)-4\text{ , for $\sigma(1)\geq 5$,}\end{cases}\text{ for
}1\leq i\leq 4\right\\}.$

This group is imprimitive but the minors of any size are nonzero. We see that
our criterion is not necessary.

123456789 Figure 2: A graph with imprimitive Galois group
$\operatorname{Gal}(\xi)<A_{8}$, but nonvanishing minors.

######  Example 16.

The graph in Figure 3 has the characteristic polynomial

$\varphi=\lambda\cdot\left(\lambda^{6}-12\lambda^{5}+54\lambda^{4}-114\lambda^{3}+115\lambda^{2}-50\lambda+7\right).$

The Galois group of $\xi$ has order 72 and is given by

$\operatorname{Gal}(\xi)\cong\left\\{\sigma\in
S_{6}\colon\sigma(\\{1,2,3\\})\in\\{\\{1,2,3\\},\\{4,5,6\\}\\}\right\\}.$

This group is imprimitive and the vanishing minors of size 3 are supported on
the columns $\\{1,2,3\\}$ or $\\{4,5,6\\}$.

1235674 Figure 3: A graph with $1$-homogeneous Galois group, but vanishing
minors.

## References

  * [1] J. Alt, R. Ducatez, and A. Knowles.  The completely delocalized region of the Erdős–Rényi graph.  Electron. Commun. Probab., 27:Paper No. 10, 9, 2022.
  * [2] S. Brooks and E. Lindenstrauss.  Non-localization of eigenfunctions on large regular graphs.  Israel J. Math., 193(1):1–14, 2013.
  * [3] P. J. Cameron.  Finite permutation groups and finite simple groups.  Bull. London Math. Soc., 13(1):1–22, 1981.
  * [4] D. M. Cvetković.  The main part of the spectrum, divisors and switching of graphs.  Publ. Inst. Math. (Beograd) (N.S.), 23(37):31–38, 1978.
  * [5] S. Eberhard.  The characteristic polynomial of a random matrix.  Combinatorica, 42(4):491–527, 2022.
  * [6] T. Emmrich, M. Juhnke-Kubitzke, and S. Kunis.  Two subspace methods for frequency sparse graph signals, 2023.
  * [7] A. Ferber, V. Jain, A. Sah, and M. Sawhney.  Random symmetric matrices: rank distribution and irreducibility of the characteristic polynomial.  Math. Proc. Cambridge Philos. Soc., 174(2):233–246, 2023.
  * [8] S. Foucart and H. Rauhut.  A mathematical introduction to compressive sensing.  Applied and Numerical Harmonic Analysis. Birkhäuser/Springer, New York, 2013.
  * [9] C. Godsil.  Controllable subsets in graphs.  Ann. Comb., 16(4):733–744, 2012.
  * [10] W. M. Kantor.  $k$-homogeneous groups.  Math. Z., 124:261–265, 1972.
  * [11] F. Liu and J. Siemons.  Unlocking the walk matrix of a graph.  J. Algebraic Combin., 55(3):663–690, 2022.
  * [12] R. Meshulam.  An uncertainty inequality for finite abelian groups.  European J. Combin., 27(1):63–67, 2006.
  * [13] P. Morandi.  Field and Galois theory, volume 167 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 1996.
  * [14] S. O’Rourke, V. Vu, and K. Wang.  Eigenvectors of random matrices: a survey.  J. Combin. Theory Ser. A, 144:361–442, 2016.
  * [15] P. Rowlinson.  The main eigenvalues of a graph: a survey.  Appl. Anal. Discrete Math., 1:445–471, 2007.
  * [16] Y. Saad.  Iterative methods for sparse linear systems.  Society for Industrial and Applied Mathematics, Philadelphia, PA, second edition, 2003.
  * [17] P. Stevenhagen and H. W. Lenstra, Jr.  Chebotarëv and his density theorem.  Math. Intelligencer, 18(2):26–37, 1996.
  * [18] T. Tao.  An uncertainty principle for cyclic groups of prime order.  Math. Res. Lett., 12(1):121–127, 2005.


# A Multi-Granularity-Aware Aspect Learning Model for Multi-Aspect Dense
Retrieval

Xiaojie Sun  CAS Key Lab of Network Data Science and Technology, ICT,
CASUniversity of Chinese Academy of SciencesBeijingChina
<EMAIL_ADDRESS>,  Keping Bi  CAS Key Lab of Network Data Science and
Technology, ICT, CASUniversity of Chinese Academy of SciencesBeijingChina
<EMAIL_ADDRESS>,  Jiafeng Guo  CAS Key Lab of Network Data Science and
Technology, ICT, CASUniversity of Chinese Academy of SciencesBeijingChina
<EMAIL_ADDRESS>,  Sihui Yang  CAS Key Lab of Network Data Science and
Technology, ICT, CASUniversity of Chinese Academy of SciencesBeijingChina
<EMAIL_ADDRESS>,  Qishen Zhang  ,  Zhongyi Liu  ,  Guannan Zhang  Ant
GroupBeijingChina qishen.zqs, zhongyi.lzy<EMAIL_ADDRESS>and
Xueqi Cheng  CAS Key Lab of Network Data Science and Technology, ICT,
CASUniversity of Chinese Academy of SciencesBeijingChina<EMAIL_ADDRESS>
(2024)

###### Abstract.

Dense retrieval methods have been mostly focused on unstructured text and less
attention has been drawn to structured data with various aspects, e.g.,
products with aspects such as category and brand. Recent work has proposed two
approaches to incorporate the aspect information into item representations for
effective retrieval by predicting the values associated with the item aspects.
Despite their efficacy, they treat the values as isolated classes (e.g.,
“Smart Homes”, “Home, Garden & Tools”, and “Beauty & Health”) and ignore their
fine-grained semantic relation. Furthermore, they either enforce the learning
of aspects into the CLS token, which could confuse it from its designated use
for representing the entire content semantics, or learn extra aspect
embeddings only with the value prediction objective, which could be
insufficient especially when there are no annotated values for an item aspect.

Aware of these limitations, we propose a MUlti-granulaRity-aware Aspect
Learning model (MURAL) for multi-aspect dense retrieval. It leverages aspect
information across various granularities to capture both coarse and fine-
grained semantic relations between values. Moreover, MURAL incorporates
separate aspect embeddings as input to transformer encoders so that the masked
language model objective can assist implicit aspect learning even without
aspect-value annotations. Extensive experiments on two real-world datasets of
products and mini-programs show that MURAL outperforms state-of-the-art
baselines significantly. Code will be available at the
URL111https://github.com/sunxiaojie99/MURAL.

Dense Retrieval, Multi-Aspect, Pre-training

††journalyear: 2024††copyright: rightsretained††conference: Proceedings of the
17th ACM International Conference on Web Search and Data Mining; March 4–8,
2024; Merida, Mexico††booktitle: Proceedings of the 17th ACM International
Conference on Web Search and Data Mining (WSDM ’24), March 4–8, 2024, Merida,
Mexico††doi: 10.1145/3616855.3635770††isbn: 979-8-4007-0371-3/24/03††ccs:
Information systems Information retrieval

##  1\. Introduction

Figure 1.  An example of a query and its candidate items.

In recent years, dense retrieval methods have been extensively studied in both
Information Retrieval (IR) and Natural Language Processing (NLP) communities
(Guo et al., 2022). On the shoulders of pre-trained language models (PLMs),
they have achieved compelling performance. However, they are mostly studied
for unstructured data and have not investigated how to effectively leverage
the aspect information of structured data, such as category for products and
affiliation for people. For example, in Figure 1, the query “sports gloves”
targets gloves for sports use so kitchen gloves should be avoided. It is
obvious that the category of the four items could help to differentiate
various types of gloves and improve retrieval performance. Unfortunately, it
remains largely unexplored to effectively leverage such aspect information in
dense retrieval.

Recently, Kong et al. (2022) has proposed two effective models for multi-
aspect dense retrieval, i.e., MTBERT and MADRAL. These methods follow a
typical paradigm of learning aspect embeddings with an auxiliary objective of
predicting their associated values (Ai et al., 2020, 2018). A concrete example
is that the embedding of aspect “category” for i4 in Figure 1 will be learned
by predicting its value, i.e., “Household Supplies”. Although effective, they
consider the values of an aspect as isolated classes and neglect the potential
correlation between various values, which could result in sub-optimal
performance. Taking the items in Figure 1 for instance, although they fall
into four separate categories, the first three are relevant to the user query
“sports gloves” while the last is not. The auxiliary objective of predicting
their categorical IDs treats each category equally and may not capture their
fine-grained relations.

Noticing this issue, we propose to leverage the aspect information at even
finer granularities, such as the word and token levels, in addition to the
previously considered phrase-level granularity. Then, for the items in Figure
1, when we break their category phrases into small pieces, the relation
between the first three will be clearer since they all have sports-related
descriptions such as exercise, sport, tennis, etc. Moreover, from a linguistic
perspective, coarser granularities such as sentences and phrases convey more
specific information while finer units usually carry more general information
(Mulkar-Mehta et al., 2011). Since different granularities could express
various levels of intent, we incorporate multiple granularities of aspect
annotation prediction to assist query/item representation learning.

Our model is named MURAL, short for a MUlti-granulaRity-aware Aspect Learning
model. It incorporates separate aspect embeddings before the content tokens
and after CLS as inputs to the transformer layers (shown in Figure 3). Then,
on the top layer, the aspect embeddings are supervised with value predictions
at various levels of granularities (e.g., phrase, word, and token). MURAL has
several advantages over state-of-the-art methods, i.e., MTBERT and MADRAL (See
Figure 2): First, in contrast to MTBERT which mixes the information from item
aspects and the overall content semantics in CLS, MURAL represents the two
types of information separately and allows for more interactions between them
with a gating mechanism. Second, in contrast to MADRAL which only learns the
aspect embeddings with the value prediction objective during pre-training,
MURAL also guides the aspect embeddings to learn from the masked language
model loss. This could assist implicit aspect learning even when there are no
annotated values for an item aspect. Last and most importantly, by
incorporating the aspect information across various granularities, MURAL could
capture the semantic relations between the aspect values at different levels,
contributing more to the retrieval performance.

We conduct extensive experiments on two real-world search datasets with rich
aspect information. Experimental results show that our method outperforms
competitive baselines significantly on both datasets. It is remarkable that
our model achieves compelling performance even without the supervision of
aspect annotations, which means that useful implicit representations can be
learned by MURAL even when the aspect information is not used. Ablation
studies on different granularities show that each granularity can contribute
to the multi-aspect retrieval performance and combining them all lead to much
better results.

##  2\. RELATED WORK

Dense Retrieval. Dense retrieval models typically use a bi-encoder structure
for independent query and item encoding, with relevance measured through a
simple similarity function (such as dot product). Karpukhin et al. (2020)
initializes the encoder with BERT and combines it with in-batch negatives,
achieving better performance than early models. After that, researchers began
to explore various fine-tuning techniques to train a better dense retriever,
including hard negative mining (Xiong et al., 2021; Qu et al., 2021),
knowledge distillation (Tahami et al., 2020), and multi-vector representation
(Luan et al., 2021; Khattab and Zaharia, 2020; Zhang et al., 2022). For
example, Xiong et al. (2021) proposed to dynamically mine hard negatives
during training by periodically refreshing the index. Luan et al. (2021)
captures information of items from different perspectives by using the first k
document token embeddings as the item representation. Based on this, Zhang et
al. (2022) added k special tokens before the item input to obtain the multi-
vector representation. These multi-vector methods aim to extract multiple
underlying semantic information from the item. In contrast, our method
explicitly considers explicit multi-aspect information modeling. Additionally,
our method outputs only a single representation vector for each item, saving
space and time for indexing items.

Recently, Kong et al. (2022) introduced two methods for incorporating explicit
aspect information into a single representation vector. The first method
employs CLS embeddings to simultaneously perform aspect classification tasks
for multiple aspects. The second method adds an attention network to the PLM,
enabling it to separately model multiple aspects, followed by aspect fusion.
Their differences with our method will be introduced in Section 4.

Multi-Field Retrieval. The effective utilization of multi-field information
(_e.g.,_ title, keyword, description) in documents has been studied for long.
Before PLM appears, many neural ranking models were proposed to effectively
leverage item structure (Balaneshinkordan et al., 2018; Liu et al., 2018;
Zamani et al., 2018). For example, Zamani et al. (2018) aggregated field-level
representations to obtain item representations and employed a matching network
for final relevance score prediction. In the PLM era, research has
continuously focused on the utilization of multi-field information (Shan et
al., 2023; Sun et al., 2023). For example, Shan et al. (2023) proposed the
field-level local matching loss, calculated based on the query and each
document field representation. Sun et al. (2023) treated aspect as text and
proposed an effective pre-training method to capture the bi-directional
interactions between aspect and content texts. The difference between multi-
aspect and multi-field is that fields contain an infinite textual value space,
usually composed of variable-length unstructured text. Conversely, an aspect
has a defined set of finite values, acting as ”labels” for structured items.
Given this, they face different core challenges, and effectively utilizing
multiple aspects’ information is a valuable research direction.

Pre-trained Bi-encoder. Researchers have explored pre-training models for
retrieval with the bi-encoder architecture(Lee et al., 2019; Lu et al., 2021;
Gao and Callan, 2021; Ma et al., 2022; Gao and Callan, 2022; Xiao et al.,
2022). For example, Gao and Callan (2021) added extra head layers atop the
Transformer, with shortcut connections between early outputs and the head,
enhancing the CLS embedding of the encoder. Lu et al. (2021) pre-trained an
auto-encoder with a weak decoder for document representation learning.
Differing from these pre-training methods targeted at unstructured data, we
investigate how to infuse explicit aspect information into the encoder
representation during pre-training. In the future, we will explore how to
integrate our approach with existing research.

##  3\. Preliminaries

Dual Encoding. The standard PLMs, _e.g.,_ BERT (Devlin et al., 2018), take a
token sequence $X=(x_{1},...,x_{n})$ as input, and generate contextualized
representations as:

(1)
$\small\textbf{h}(x_{0}),\textbf{h}(x_{1})...\textbf{h}(x_{n})=\Phi_{enc}(X),\
\textbf{h}(x_{i})\in\mathbb{R}^{H},$

where $H$ denotes the hidden size, and $x_{0}=[CLS]$ is a special token added
to the beginning. The representation $\textbf{h}(x_{0})$ is commonly used as
the final representation for the input $X$. In dense retrieval, the bi-encoder
architecture is widely adopted, where the query $Q$ and item $I$ are
separately encoded using the PLM to obtain their respective representation
vectors(Lin et al., 2021b). Then, a simple scoring function is used to
calculate the similarity between these two vectors.

Table 1. A summary of main notations used in this paper.  Notation |  Meaning
---|---
$X=(x_{1},x_{2},...,x_{n})$ |  The input token sequence of query/item.
$\textbf{h}_{X}$ |  The final representation for the input X.
$A=\\{a_{i}\\}$, $i=1,...,|A|$ |  A set of aspects, _e.g.,_ {brand, color, category}
$G=\\{g_{i}\\},i=1,...,|G|$ |  The set of language granularities, _e.g.,_ $\\{phrase,word,token\\}$
$V_{a_{i}}^{g_{j}}$ or $V_{a}^{g}$, $i=1,...,|A|$, $j=1,...,|G|$ |  The aspect value vocabulary of aspect $a_{i}$ at granularity level $g_{j}$, _e.g.,_ $V_{category}^{word}=\\{shoes,clothing,...\\}$
$\textbf{h}_{a_{i}}^{g_{j}}$ or $\textbf{h}_{a}^{g}$, $i=1,...,|A|$, $j=1,...,|G|$ |  The aspect embedding for query’s or item’s aspect $a$ at granularity $g$.
$E_{a_{i}}^{g_{j}}$ or $E_{a}^{g}$, $i=1,...,|A|,j=1,...,|G|$ |  The aspect value embedding table for aspect $a$ at granularity $g$.
$\mathcal{A}_{a_{i}}^{g_{j}}$ or $\mathcal{A}_{a}^{g}$, $i=1,...,|A|,j=1,...,|G|$ |  The set of aspect value annotations for query’s or item’s aspect $a$ at granularity $g$, $\mathcal{A}_{a}^{g}\subset V_{a}^{g}$

Aspect Learning. In dense retrieval, aspect learning involves using aspect
information to enhance retrieval performance when queries or items are
associated with varying aspects (e.g., brand, color, category in product
search). In addition to the content text $X=(x_{1},...,x_{n})$ (e.g., query,
item title), a query or item can be associated with multiple aspects, and we
denote the set of these aspects as $A=\\{a_{i}\\}_{i=1}^{|A|}$. For
simplicity, when the context is clear, we omit the subscript $i$ in $a_{i}$.
For each aspect $a$, there exists a finite vocabulary of aspect values,
represented as $V_{a}$, along with a corresponding embedding table
$E_{a}\in\mathbb{R}^{|V_{a}|\times H}$ that contains embeddings for each value
of aspect $a$. Figure 2 shows the aspect learning in two state-of-the-art
multi-aspect dense retrievers (Kong et al., 2022). Both approaches utilize
content text as the encoder input. Specifically, MTBERT reuses CLS to
represent aspects, whereas MADRAL constructs embeddings for the $|A|$ aspects
by attending to the final layer of content tokens. Both methods train the
aspect embeddings by predicting the corresponding value annotation ID in
$V_{a}$ for each of the $|A|$ aspects.

Multi-Granularity. Different granularities of text strings capture semantic
information at varied levels. Coarse grains such as sentences or phrases often
express more specific intent than finer grains like words or tokens.
Therefore, relying solely on phrase-level value prediction, as previous
methods do, might not yield effective aspect representations. For example, if
a product category value is ”handmade products”, its word-level granularity
values would be ”$[handmade,products]$”, and its token-level granularity
values would be ”$[hand,\\#\\#made,products]$”. Formally, we denote the set of
granularities as $G$, where each $g$ (with $g\in G$) represents a specific
granularity. In this paper, we use three granularities:
$G=\\{phrase,word,token\\}$. We use $V_{a}^{g}$ to represent the value
vocabulary obtained by decomposing aspect $a$’s values at granularity $g$. The
corresponding aspect value embedding table becomes
${E}_{a}^{g}\in\mathbb{R}^{|V_{a}^{g}|\times H}$. We list the frequently used
notations in Table 1.

##  4\. METHODOLOGY

In this section, we propose a MUlti-granulaRity-aware Aspect Learning model
(MURAL) for multi-aspect dense retrieval and introduce its core components. As
in (Kong et al., 2022), MURAL is also based on BERT (Devlin et al., 2018).
Since MURAL encodes both items and queries in the same way, we only use items
for illustration.

Figure 2.  SOTA multi-aspect dense retrieval models.  Figure 3.  Our MURAL
with single-objective-based grouping in a simplistic scenario of two aspects
and two granularities.

###  4.1. Aspect Representations

It is crucial to represent aspects reasonably in a pre-trained model so that
aspect learning can guide their training effectively. To fully exploit the
capabilities of the Transformer encoders, as shown in Figure 3, we introduce
several tokens after CLS and before the content tokens to represent aspects
from various perspectives. This aligns with the way CLS is obtained and these
tokens can interact with the content tokens sufficiently. During pre-training,
these inserted embeddings can act as different views of context when
predicting the masked tokens in the content. In this way, these embeddings can
also learn from the masked language model objective and capture the content
semantics from various implicit views, which could bring more benefits,
especially when there are no value annotations for an aspect.

Comparison with Previous Methods. As shown in Figure 2, MTBERT(Kong et al.,
2022) reuses the CLS token to predict the values of item aspects, which
enforces CLS to mix the information from item aspects with the overall content
semantics it is originally designated to capture. The balance between the two
cannot be automatically learned and CLS could be confused about what it should
learn. MADRAL (Kong et al., 2022) represents each item aspect separately by
attending to the final representations of content tokens and learns the aspect
embeddings by predicting their associated values. During pre-training, the
only guidance for the aspect embeddings is this value prediction objective,
which could be insufficient to learn them well. What is worse, they will not
be updated when there are no aspect-value annotations. In contrast, in MURAL,
the aspect information would not mix with the overall content semantics in
CLS. With the gating mechanism, they can interact more and the aspect
importance can be learned automatically. Moreover, the aspect embeddings can
be guided by the masked language model loss as well, which not only benefits
their representation learning but also facilitates implicit aspect learning
without aspect-value annotations.

###  4.2. Aspect Learning

For simplicity, we use an example of aspect $a$ at granularity $g$ to
illustrate. For aspect learning in MURAL, there are two important components:
value representation and the aspect learning objective.

Value Representation. To conduct effective aspect learning by predicting the
value annotations of an aspect in terms of both coarse and fine grains, value
representations play an important role. There are two options: 1) Sharing the
existing token embeddings in the backbone PLM and calculating the value
embeddings of word-level and phrase-level grains by a projection function. It
can reuse the semantic information carried in the PLM tokens. However, the
token embeddings are learned towards the goals of both PLM and aspect
learning, which may interfere with each other. 2) Declaring separate value
embedding tables, which is consistent with (Kong et al., 2022) and the
research before the PLMs era in (Ai et al., 2020). The extra value embeddings
could serve the model to conduct aspect learning better without other
interventions. However, if trained from scratch, these new parameters may be
difficult to optimize. We refer to these two options as “shared” and
“unshared” respectively in terms of whether to share the underlying token
embeddings with the existing encoder. We investigate both ways in our
experiments (see Section 6.2).

Specifically, for the “shared” option, we first tokenize each aspect value $v$
in $V_{a}^{g}$ using the BERT tokenizer. Then, we extract their embeddings
from BERT’s embedding tables and use a projector function on the token
embeddings to obtain the corresponding value embedding $e_{v}$ during
training. In this paper, we adopt average pooling as the projection function
since it is simple and produces similar results to other methods in our
preliminary experiments.

For the “unshared” option, each aspect $a$ has a separate embedding table
$E_{a}^{g}$ for each granularity $g$, storing the embeddings of its values
$V_{a}^{g}$. Instead of training these tables from scratch, we initialize the
tables using the average token embeddings in the PLM for each value $v$ at
granularity $g$ (the same as the initial embedding in the “shared” option).
This gives the new embeddings a decent starting point in the semantic space
and has the freedom to better conduct aspect learning, the benefit of which
will be shown in Section 6.2.

Aspect Learning Objective. Once we obtain the representation of aspect $a$ at
granularity $g$, denoted as $\textbf{h}_{a}^{g}(X)\in\mathbb{R}^{H}$, we adopt
the widely-used group-wise contrastive loss to pre-train the encoder. It aims
to bring the source representation closer to instances in its target group
while distancing it from representations of other groups (Khosla et al.,
2020).

(2)
$\small\mathcal{L}_{a}^{g}(X)=-\frac{1}{|\mathcal{A}_{a}^{g}|}\sum_{v^{+}\in\mathcal{A}_{a}^{g}}log\frac{exp(sim(\textbf{h}_{a}^{g}(X),\textbf{e}_{v^{+}}))}{\sum_{v\in
V_{a}^{g}}{exp(sim(\textbf{h}_{a}^{g}(X),\textbf{e}_{v}))}},\vspace*{-2mm}$

where $\textbf{e}_{v}$/$\textbf{e}_{v^{+}}\in\mathbb{R}^{H}$ is the aspect
value embedding from $E_{a}^{g}$, $sim(\cdot)$ is the dot-product function,
and $\mathcal{A}_{a}^{g}$ is the set of aspect value annotations for aspect
$a$ at granularity $g$.

###  4.3. Multi-Granularity-Aspect Grouping

Assume there are $|A|$ aspects and $|G|$ granularities, our goal is to
facilitate aspect learning for each aspect of each granularity, totally
—A—*—G— learning objectives. A straightforward approach is to use a single
representation to handle these multiple objectives. However, this method
enforces all the information to be compressed together, severely limiting the
learning capacity of each objective. Therefore, we introduce three grouping
schemes to integrate multi-granularities and multi-aspects: Single-objective-
based Grouping, Granularity-based Grouping, and Aspect-based Grouping.

Single-objective-based Grouping. As shown in Figure 3, when there are only a
few aspects and granularities, we can directly introduce $|A|*|G|$ tokens in
the input sequence $X$ to capture the item semantics from $|A|*|G|$ views.
Each of them accounts for a single objective among the multi-granularity-
aspect combinations. Specifically, we obtain a sequence of
$X=(x_{0},o_{1},...,o_{|A|*|G|},x_{1},..,x_{n})$. We utilize the hidden vector
$\textbf{h}(o_{k})$($k=1,...,i*j$) from the final layer as the item
representation from the perspective of aspect $a_{i}$ at the granularity
$g_{j}$. The aspect learning loss function becomes:

(3) $\displaystyle\mathcal{L_{A}}(X)$
$\displaystyle=\frac{1}{|A|*|G|}\sum_{i=1}^{|A|}\sum_{j=1}^{|G|}\mathcal{L}_{a_{i}}^{g_{j}}(X).$

When $|A|*|G|$ is large, adding a significant number of tokens can adversely
affect the semantic representation of the original input. Hence, it becomes
essential to further group the objectives across various granularities and
aspects.

Granularity-based Grouping. The same granularity indicates the same level of
semantic information, and grouping the objectives at the same grain is a
reasonable option. In this case, $|G|$ tokens will be inserted into the input
sequence, yielding $X=(x_{0},o_{1},...,o_{|G|},x_{1},x_{2},..,x_{n})$. Their
encoded representations become $\textbf{h}(o_{j})$ ($j=1,...,|G|$),
representing the item from the perspective of all the aspect information at
granularity $g_{j}$. A single aspect embedding accounts for the loss
$\mathcal{L}_{a_{i}}^{g_{j}}(X)$ of all the aspects $a_{i}$ ($i=1,...,|A|$) of
granularity $g_{j}$, i.e., $\textbf{h}_{a_{i}}^{g_{j}}$ ($i=1,...,|A|$) are
the same for granularity $g_{j}$. The aspect learning objective is:

(4)
$\small\mathcal{L_{A}}(X)=\frac{1}{|G|}\sum_{j=1}^{|G|}\mathcal{L}_{g_{j}}(X),\textrm{where
}\mathcal{L}_{g_{j}}(X)=\frac{1}{|A|}\sum_{i=1}^{|A|}\mathcal{L}_{a_{i}}^{g_{j}}(X).$

Aspect-based Grouping. An alternative option is to group the objectives across
multi-granularity-aspects by aspects so that different aspect information will
not mix together and various levels of granularities could benefit each other.
Here, we introduce $|A|$ guiding tokens before the content tokens:
$X=(x_{0},o_{1},...,o_{|A|},x_{1},x_{2},..,x_{n})$. The hidden vector
$\textbf{h}(o_{i})$ ($i=1,...,|A|$) captures the representations of all
granularities for the input item corresponding to aspect $a_{i}$. In
particular, when calculating the loss $\mathcal{L}_{a_{i}}^{g_{j}}(X)$ using
equation 2, the representation $\textbf{h}_{a_{i}}^{g_{j}}$ of aspect $a_{i}$
remains consistent across different granularities. Under this aggregation
method, loss $\mathcal{L_{A}}$ can be reformulated as follows:

(5)
$\small\mathcal{L_{A}}(X)=\frac{1}{|A|}\sum_{i=1}^{|A|}\mathcal{L}_{a_{i}}(X),\text{where
}\mathcal{L}_{a_{i}}(X)=\frac{1}{|G|}\sum_{j=1}^{|G|}\mathcal{L}_{a_{i}}^{g_{j}}(X).$

Grouping by granularities or aspects reduces the number of guiding tokens,
accommodating scenarios with numerous aspects and granularities. Their model
architectures stay the same as Figure 3, except that aspect learning
objectives for the same granularities or aspects are conducted on the shared
token.

###  4.4. Aspect Embedding Fusion

For efficiency concerns, it is necessary to consolidate multiple embeddings
into a single one to minimize storage and computation costs. Inspired by (Kong
et al., 2022), we adopt the ”CLS-Gating” fusion mechanism in MURAL. To
illustrate the fusion process, we present an example using the single-
objective-based grouping approach discussed in Section 4.3. Specifically, we
pass the CLS embedding through a linear layer and a softmax function to
compute the weighting scores for $\textbf{h}(o_{1}),...,\textbf{h}(o_{K})$,
where $K=|A|*|G|$:

(6) $\small\textbf{w}=Softmax(U\textbf{h}(x_{0})+b)\in\mathbb{R}^{K},$

where $U\in\mathbb{R}^{K\times H}$ and $b\in\mathbb{R}^{K}$ are trainable
parameters. Then, we utilize the learned weights to fuse multiple embeddings,
thereby obtaining the final encoded representation of the input $X$:

(7) $\displaystyle\textbf{h}_{X}$
$\displaystyle=\sum_{k=1}^{K}w_{k}\cdot\textbf{h}(o_{k}).$

###  4.5. Training Objectives

Pre-training. As discussed in previous work (Ma et al., 2021), the Masked
Language Model (MLM) (Taylor, 1953) task could help construct good text
representation for IR. Therefore, similar to (Kong et al., 2022), we also
adopt MLM as one of the pre-training objectives besides aspect learning.

(8) $\displaystyle\mathcal{L}_{MLM}(X)=-\sum_{w\in
masked(X)}logP(w|X_{\backslash masked(X)}),$

where $X$ means the input sentence, $masked(X)$ and $X_{\backslash masked(X)}$
denotes the masked tokens and the remaining tokens from $X$, respectively.

We then pre-train the Transformer encoder using the aspect learning loss
jointly with the MLM loss, as follows,

(9)
$\displaystyle\mathcal{L}_{total}(X)=\mathcal{L}_{MLM}(X)+\lambda\mathcal{L_{A}}(X),$

where $\lambda$ is the hyperparameter.

Fine-Tuning. We adopt the following in-batch softmax cross entropy loss
$\mathcal{L}_{SCE}$ as the learning objective during fine-tuning. Note that
although the aspect learning loss could also be added during fine-tuning, our
experimental results show no significant improvements for all the multi-aspect
retrievers. Hence, we omit this objective in this paper.

(10)
$\small\mathcal{L}_{SCE}=-log\frac{exp(sim(\textbf{h}_{Q},\textbf{h}_{I^{+}}))}{exp(sim(\textbf{h}_{Q},\textbf{h}_{I^{+}}))+{\textstyle\sum_{I^{-}}}{exp(sim(\textbf{h}_{Q},\textbf{h}_{I^{-}}))}}.$

Table 2.  Aspect-Related Dataset Statistics. It presents the percentage of queries/items with non-empty aspect values in the pre-training corpus and the aspect value vocabulary sizes at various granularities: phrase, word, and token.  | MA-Amazon | Alipay
---|---|---
aspect | item | item / query
brand |  $94\%$ (5k,6k,5k) |  $0.6\%/44\%$ (9k,11k,3k)
color |  $67\%$ (2k,1k,1k) | –
category |  $87\%$ (8k,5k,5k) |  $90\%/91\%$ (457,650,548)
Table 3. Comparisons between MURAL and the baselines. The best results (excluding MURAL-CONCAT) are in bold. ${\dagger}$, ${\ddagger}$, and $\ast$ indicate significant improvements over the best baselines in the first/second group and the backbone BIBERT, respectively.  Method | MA-Amazon | Alipay
---|---|---
R@100 | R@500 | NDCG@50 | R@100 | R@500 | NDCG@50
BIBERT | 0.6075 | 0.7795 | 0.3929 | 0.4464 | 0.6284 | 0.2033
Condenser | 0.6091 | 0.7801 | 0.3960 | 0.4520 | 0.6423 | 0.2072
BIBERT-CONCAT | 0.6137 | 0.7814 | 0.4005 | 0.4517 | 0.6291 | 0.2103
MTBERT | 0.6137 | 0.7852 | 0.3969 | 0.4498 | 0.6280 | 0.2064
MADRAL | 0.6088 | 0.7815 | 0.3950 | 0.4506 | 0.6383 | 0.2057
MUR | 0.6282†‡∗ | 0.7943†‡∗ | 0.4151†‡∗ | 0.4556∗ | 0.6458‡∗ | 0.2046
MURAL | 0.6371†‡∗ | 0.8023†‡∗ | 0.4228†‡∗ | 0.4630†‡∗ | 0.6519†‡∗ | 0.2177†‡∗
MURAL-CONCAT | 0.6389†‡∗ | 0.8005†‡∗ | 0.4281†‡∗ | 0.4669†‡∗ | 0.6474‡∗ | 0.2124†∗

##  5\. EXPERIMENTAL SETTINGS

###  5.1. Datasets

We use the following two large-scale search datasets from real-world platforms
with rich aspect information for our experiments. The aspect-related
statistics of the two datasets are in Table 2. (1) Multi-Aspect Amazon ESCI
Dataset (MA-Amazon). MA-Amazon (Sun et al., 2023) enriches the English portion
of the Amazon ESCI (Reddy et al., 2022) dataset with item category
information. In MA-Amazon, only items have annotations for brand, color and
category. The item corpus contains 482K distinct products, which are used for
pre-training. The retrieval dataset has 17k, 3.5k, and 8.9k queries for fine-
tuning, validation, and testing respectively, without any query overlaps. For
each query, the retrieval dataset provides 20.1 items on average, along with
their ESCI relevance judgments (Exact, Substitute, Complement, Irrelevant),
indicating each item’s relevance to the given query. Following (Reddy et al.,
2022), we treat Exact as positive and all others as negatives for fine-tuning
and metrics requiring binary labels. (2) Alipay Search Dataset. Alipay is a
Chinese mini-program (app-like service) search dataset. In Alipay, both
queries and items are annotated with two aspects: brand and category. We
conduct pre-training on both a query corpus, containing 1.3M unique queries,
and an item corpus with 1.8M distinct items. The retrieval dataset contains
60k, 3.3k, and 3.3k real user queries for fine-tuning, validation, and testing
respectively, without query overlaps. Note that the queries for validation and
testing do not appear in the pre-training query corpus. Each instance in the
relevance dataset is a ¡query, item, label¿ triplet, where the label indicates
the manually annotated binary relevance of this query-item pair.

###  5.2. Baselines

We adopt the following dense retrieval baselines for comparison, including
models using or without using aspect information: (1) BIBERT (Lin et al.,
2021a; Reimers and Gurevych, 2019): A standard bi-encoder baseline and the
backbone of MURAL, using CLS encoding of the BERT-based encoder for both query
and item representations. BIBERT is pre-trained with MLM loss and fine-tuned
with loss $\mathcal{L}_{SCE}$ (Equation 10). (2) Condenser(Gao and Callan,
2021): A pre-trained method tailored for unstructured textual dense retrieval.
It introduces a short circuit between middle-layer tokens (excluding CLS) and
their corresponding head-layer tokens during pre-training, optimizing the CLS
embedding to encapsulate more information. (3) BIBERT-CONCAT: It treats the
aspect values as texts and concatenates them with the query/item content
during pre-training with MLM. During fine-tuning, since the concatenation with
query could change query semantics , we only concatenate item aspects for
relevance matching. (4) MTBERT(Kong et al., 2022): A multi-task (MT) learning
model based on BIBERT. Besides MLM during pre-training, it conducts $|A|$
aspect prediction tasks using CLS. (5) MADRAL(Kong et al., 2022): It
incorporates an aspect extraction attention network to extract $|A|$ aspect
representations for both queries and items. These embeddings are learned from
aspect prediction tasks during pre-training and fused to yield the final
representation during fine-tuning. (6) MURAL, MUR and MURAL-CONCAT: MURAL is
our proposed multi-aspect dense retrieval model. In contrast, MUR disables
aspect learning. Specifically, when $\lambda$ in Equation 9 is set to 0, MURAL
regresses to MUR. MURAL-CONCAT employs the same aspect-content text
concatenation strategy as BIBERT-CONCAT for the model input. Note that unless
the model name includes ”-CONCAT”, the model input consists solely of content
text.

###  5.3. Implementation Details

We implemented MURAL and all the baselines by ourselves to ensure consistent
implementation details and fair comparisons.

####  5.3.1. Pre-training

For all methods, the encoder is shared for both queries and items to
facilitate knowledge sharing. Specifically, we pre-train on a corpus
consisting of the item corpus or a mixture of the query and item corpus (when
query aspect annotations are available) to obtain the shared encoder for fine-
tuning.

Muti-granularity Value Collection. Given an aspect $a$ and its original aspect
vocabulary at the phrase level, we obtain its word and token granularity
vocabularies: For word granularity, we segment each aspect value $v$ by spaces
and punctuation (for English) or employ the Jieba tool (jie, 2023) (for
Chinese), and eliminate duplicates to aggregate the generated “words”. For
token granularity, we merge the token list obtained by processing each aspect
value $v$ with the BERT tokenizer to create the corresponding vocabulary set.

Model Pre-training. We initialize all the BERT components using Google’s
public checkpoint and employ the Adam optimizer with the linear warm-up
technique. The learning rate and epoch for the MA-Amazon/Alipay dataset are
set to 1e-4/5e-5 and 20/10, respectively. The maximum token length is 156, the
MLM mask ratios are 0.15 for items and 0.3 for queries. For all methods
requiring adjustment of training objective scaling coefficients, we uniformly
select coefficients based on their validation set performance after fine-
tuning. These coefficients vary from 0.1 to 1, in 0.1 intervals. For our
method, we set $\lambda$ in Eq.9 to 0.1. We use the following fine-tuning
procedures to evaluate pre-trained model checkpoints every two epochs and
select the best one on the validation set.

####  5.3.2. Fine-tuning

For both datasets, we fine-tune all the models for 20 epochs with Tevatron
toolkit(Gao et al., 2022). Following the previous work (Karpukhin et al.,
2020), we include a hard negative sample for each query besides in-batch
negatives. We use a learning rate of 5e-6 and a batch size of 64. The maximum
token lengths are set at 32 for queries and 156 for items. All the models are
trained with relevance loss $\mathcal{L}_{SCE}$ (Eq.10).

####  5.3.3. Evaluation Metrics

We report R@100, R@500, and NDCG@50. Following (Reddy et al., 2022), we assign
the gains of 1.0, 0.1, 0.01, and 0.0 to E, S, C, and I, respectively, for MA-
Amazon. We conduct two-tailed paired t-tests (p ¡ 0.05) to identify
significant differences.

##  6\. EXPERIMENT RESULTS

###  6.1. Overall Performance

We compare MURAL with baseline models both utilizing and without utilizing
aspect information. As shown in Table 3, we have the following observations:
(1) The models that leverage the aspect information (methods except for
BIBERT, Condenser, and MUR) outperform their backbone (BERT) without using it.
Among the multi-aspect dense retrievers, MURAL performs the best with a
significantly large margin. This confirms the necessity of incorporating
aspects in query/item representation learning. (2) On MA-Amazon, MADRAL
underperforms the simpler MTBERT. We believe this is due to the less pre-
training data of MA-Amazon and the absence of aspect annotations for queries,
which makes the aspect embeddings of MADRAL not sufficiently learned. In
contrast, MURAL achieves compelling performance consistently. (3) Condenser, a
more advanced pre-trained model for unstructured text retrieval, sometimes
outperforms the baseline multi-aspect dense retrievers. Notably, the gains
from advanced pre-training techniques are orthogonal to our method. Our
approach can be easily incorporated into stronger backbones like Condenser and
could achieve even better performance. We leave it in our future work. (4)
BIBERT-CONCAT performs better than MTBERT and MADRAL in terms of some metrics
on the two datasets, indicating that concatenating aspects as text strings can
be beneficial. However, query aspects should be taken special care of during
relevance matching in order to achieve good performance. Incorporating both
concatenation and aspect prediction in the same model (MURAL-CONCAT) does not
always result in better performance than without concatenation. We have
similar observations with MTBERT and MADRAL, but due to the space concern, we
do not report them. The reason may be that the model learns unwanted shortcuts
when using the aspect both as the model input and the learning objective. (5)
Our method shows competitive performance even without using aspect annotations
(MUR). MUR outperforms most baseline models in terms of all the metrics except
NDCG@50 on Alipay. This indicates that MUR can capture complementary
information from implicit perspectives for the final representation. It also
confirms the advantages of aspect representations and the MLM training for the
aspects in MURAL.

###  6.2. Studies on Model Variants

In this subsection, we study various options for the essential components in
MURAL. For reproducibility, all experiments are conducted on the public MA-
Amazon dataset.

Table 4. Variants of MURAL on MA-Amazon. ${\dagger}$ indicates significant differences from the best option. Method | R@100 | R@500 | NDCG@50
---|---|---|---
MURAL unshared_single | 0.6336† | 0.8005 | 0.4195†
MURALunshared_granu | 0.6371 | 0.8023 | 0.4228
MURAL unshared_aspect | 0.6340† | 0.8003† | 0.4195†
MURAL shared_single | 0.6300† | 0.7980† | 0.4171†
MURAL shared_granu | 0.6333† | 0.7996† | 0.4184†
MURAL shared_aspect | 0.6321† | 0.7995† | 0.4173†
MURAL unshared_randinit | 0.6337† | 0.8006 | 0.4196†
MURAL first_k | 0.6141† | 0.7873† | 0.4009†
MURAL no_cls_gating | 0.6212 † | 0.7890 † | 0.4064†

Studies on Value Representations. In Table 4, we observe that using an
independent value embedding space (the “unshared” option in Section 4.2) leads
to better performance. As we mentioned earlier, the “shared” option optimizes
token embeddings both towards the objectives in BERT and the aspect learning,
which could interfere with each other and limit the capacity of the model on
aspect prediction. However, under the “unshared” option, it may be difficult
to optimize the separate value embeddings from scratch while other parameters
only need fine-tuning. To see whether this affects model performance, instead
of using the same initial state as the “shared” option, we randomly initialize
the embeddings while keeping other best settings in MURAL. The harmed
performance of MURAL unshared_randinit in Table 4 confirms our presumption and
shows the benefit of decent initialization states.

Studies on Grouping Methods. In Table 4, we observe that MURAL unshared_granu,
which groups objectives by granularity, performs the best. Note that on the
Alipay dataset, which has fewer aspects, MURAL unshared_single, single-
objective-based grouping, has the best performance. This is consistent with
our claim in Section 4.3 that as the aspect count increases, further grouping
benefits model training. Based on these observations, we suggest: (1) For
small numbers of aspects and granularities, simply use independent learning
for each objective (MURAL unshared_single). (2) When there are more aspects
and granularities, grouping multiple objectives in one guiding token can be a
better choice.

Studies on Guiding Tokens and Fusion Methods. Instead of adding separate
guiding tokens for aspect learning, we study a variant that reuses the same
amount of tokens at the beginning of the input sequence to conduct aspect
learning, denoted as MURAL first_k. The results show that MURAL first_k has
similar or better performance to the best baseline in Table 3 but is
significantly worse than the best variant of MURAL. This indicates that the
multi-granularity-aware aspect learning is beneficial but using separate
guiding tokens to conduct the learning is needed.

To study whether CLS-Gating (introduced in Section 4.4) is helpful for aspect
embedding fusion, in MURAL no_cls_gating, we remove it and use the CLS
embedding as the final representation. CLS naturally fuses the aspect
embeddings in the second-to-last layer while the aspect learning is conducted
in the last layer. This variant performs better than the best baseline in
Table 3 but is worse than the best variant. It indicates that the fusion
should be carried on the final aspect embeddings with a proper weighting
mechanism.

Table 5. Ablation studies of MURAL in terms of category and granularity on the MA-Amazon dataset. ${\dagger}$, ${\ddagger}$ indicate significant differences over MURAL and BIBERT. Method | R@100 | R@500 | NDCG@50
---|---|---|---
BIBERT | 0.6075 | 0.7795 | 0.3929
MURAL | 0.6371 | 0.8023 | 0.4228
MURAL ${}^{\ only\ brand}$ | 0.6289†‡ | 0.7951†‡ | 0.4168†‡
MURAL ${}^{\ only\ color}$ | 0.6284†‡ | 0.7942†‡ | 0.4158†‡
MURAL ${}^{\ only\ category}$ | 0.6315†‡ | 0.7994†‡ | 0.4166†‡
MURAL ${}^{\ only\ phrase}$ | 0.6315†‡ | 0.7983†‡ | 0.4185†‡
MURAL ${}^{\ only\ word}$ | 0.6309†‡ | 0.7994†‡ | 0.4194†‡
MURAL ${}^{\ only\ token}$ | 0.6305†‡ | 0.7982†‡ | 0.4192†‡

###  6.3. Ablation Studies

We ablate various components of multi-aspect, multi-granularity, and
query/item aspect learning. In this section, our experiments are also based on
the enriched MA-Amazon dataset. Additionally, we validate the importance of
the query and item side effects on the Alipay dataset, since MA-Amazon lacks
query-side aspect information.

Table 6. Ablation of query and item aspects on Alipay. ${\dagger}$, ${\ddagger}$ indicate significant differences over MURAL and BIBERT.  Method | R@100 | R@500 | NDCG@50
---|---|---|---
BIBERT | 0.4464 | 0.6284 | 0.2033
MURAL | 0.4630 | 0.6519 | 0.2177
MURAL -query | 0.4569‡ | 0.6400†‡ | 0.2126†‡
MURAL -doc | 0.4573‡ | 0.6454†‡ | 0.2103†‡

Effect of Aspects and Granularities. In Table 5, we first study the impact of
multi-aspect and multi-granularity in MURAL. We find that: (1) Every aspect
contributes to the model performance, especially category, consistent with
(Kong et al., 2022). (2) Each granularity alone is conducive to model
performance and combining them all leads to even better results. Different
granularities capture semantics at distinct levels and they can complement
each other.

Effect of Query/Item Aspects. We disable the aspect learning on the query/item
side in Table 6. We observe that both query and item aspects are beneficial
and query aspects have a larger impact, which is also consistent with (Kong et
al., 2022). This is not surprising since query aspects are obtained from query
analysis such as intent classification and carry more additional information.

Table 7. The category aspect accuracy on Alipay dataset.  Method |  | query | doc
---|---|---|---
| pre-train | fine-tune | pre-train | fine-tune
MTBERT | phrase | 0.86 | 0.11 | 0.97 | 0.20
MADRAL | phrase | 0.88 | 0.81 | 0.98 | 0.87
MURAL | phrase | 0.89 | 0.85 | 0.98 | 0.93
word | 0.88 | 0.82 | 0.97 | 0.93
token | 0.89 | 0.73 | 0.97 | 0.80

###  6.4. Aspect Learning Accuracy

In Table 7, we compare the accuracy of MURAL with baseline methods after pre-
training and fine-tuning to understand the aspect learning process better. We
only analyze the most important aspect - category on Alipay. MA-Amazon and
other aspects have similar conclusions. Considering that each item may have
multiple category annotations, we use Accuracy@3 to calculate accuracy.
Evaluation of the query and item aspect prediction is based on the test query
set and item corpus of the Alipay dataset, respectively.

First, all methods have high accuracy after aspect learning in pre-training
while lower accuracy after fine-tuning. Since we only use relevance loss
during fine-tuning, it is expected that the accuracy will drop. In our
experiments, we find that adding aspect learning loss during fine-tuning
enhances aspect prediction accuracy but will harm retrieval performance. We
speculate that this objective guides the model parameters to somewhere not
aligned with the relevance-matching objective. Hence, higher aspect prediction
accuracy does not always co-occur with better retrieval performance.

Secondly, the prediction accuracy of MTBERT drops dramatically after fine-
tuning. Since MTBERT uses the same CLS token to conduct relevance matching and
aspect prediction, optimization only toward relevance matching during fine-
tuning undermines its ability to predict aspect values. In contrast, MADRAL
and MURAL retain most of such ability after fine-tuning since they use extra
aspect embeddings to perform aspect learning.

Lastly, for phrase-level evaluation, MURAL has the best aspect prediction
accuracy. As we know, MURAL also has the best retrieval performance, which
means MURAL can learn the two objectives well and let better aspect embeddings
assist relevance matching more. Notably, the accuracy at the word and token
level is not comparable with the phrase level since the ground truth is
different. The finer-level prediction accuracy is also good. When the
granularity becomes finer, the accuracy becomes lower after fine-tuning, which
is probably because finer grains have more ground-truth values, making the
multi-label classification more challenging.

Figure 4. The t-SNE plot of item representations for MADRAL and MURAL on MA-
Amazon.

###  6.5. Case Visualization

We visualize the item representations of three categories, as shown in Figure
1, to see their distributions in semantic space. Specifically, c1 (Sport
Specific Clothing) and c2 (Exercise & Fitness) are semantically similar, while
c3 (Household Supplies) is unrelated to the first two. We first use MADRAL and
MURAL to obtain all the item representations on MA-Amazon and put items into
their categories. Then we randomly pick 20 items of c1, c2 and c3 and plot
them using the t-SNE toolkit in Figure 4. We can observe that MADRAL separates
c1, c2, and c3 to a similar extent. By contrast, MURAL places the related
categories c1 and c2 closer and puts them farther from the unrelated c3. This
demonstrates MADRAL’s inability to discern the semantic similarity between c1
and c2, as it treats different phrase-level product categories as isolated
IDs, overlooking their word-level semantic connections. MURAL can capture
fine-grained semantic relations among similar aspect values while maintaining
precise phrase-level aspect discrimination by incorporating both coarse and
fine granularity information.

##  7\. CONCLUSIONS

In this paper, we propose a multi-granularity-aware aspect learning model that
enhances the utilization of additional aspect information in structured data.
Unlike previous methods that disregard the semantic relationship among
different aspect values, our approach incorporates multiple granularities of
aspect values to facilitate query/item representation learning. By effectively
capturing the semantics of queries/items from implicit views, our model
achieves compelling performance even without the supervision of aspect
annotations. Empirical results on two real-world datasets demonstrate the
superiority of MURAL.

###### Acknowledgements.

This work was funded by the National Natural Science Foundation of China
(NSFC) under Grants No. 62302486, the Lenovo-CAS Joint Lab Youth Scientist
Project, and the project under Grants No. JCKY2022130C039. This work was also
supported by Ant Group through Ant Innovative Research Program.

## References

  * (1)
  * jie (2023) 2023\.  https://github.com/fxsjy/jieba.
  * Ai et al. (2018) Qingyao Ai, Vahid Azizi, Xu Chen, and Yongfeng Zhang. 2018.  Learning Heterogeneous Knowledge Base Embeddings for Explainable Recommendation.  _Algorithms_ 11, 9 (2018), 137.
  * Ai et al. (2020) Qingyao Ai, Yongfeng Zhang, Keping Bi, and W. Bruce Croft. 2020.  Explainable Product Search with a Dynamic Relation Embedding Model.  _ACM Trans. Inf. Syst._ 38, 1 (2020), 4:1–4:29.
  * Balaneshinkordan et al. (2018) Saeid Balaneshinkordan, Alexander Kotov, and Fedor Nikolaev. 2018.  Attentive Neural Architecture for Ad-hoc Structured Document Retrieval. In _Proceedings of the 27th ACM International Conference on Information and Knowledge Management, CIKM 2018, Torino, Italy, October 22-26, 2018_ , Alfredo Cuzzocrea, James Allan, Norman W. Paton, Divesh Srivastava, Rakesh Agrawal, Andrei Z. Broder, Mohammed J. Zaki, K. Selçuk Candan, Alexandros Labrinidis, Assaf Schuster, and Haixun Wang (Eds.). ACM, 1173–1182.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  _CoRR_ abs/1810.04805 (2018).  arXiv:1810.04805
  * Gao and Callan (2021) Luyu Gao and Jamie Callan. 2021.  Condenser: a Pre-training Architecture for Dense Retrieval. In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP 2021, Virtual Event / Punta Cana, Dominican Republic, 7-11 November, 2021_ , Marie-Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih (Eds.). Association for Computational Linguistics, 981–993.
  * Gao and Callan (2022) Luyu Gao and Jamie Callan. 2022.  Unsupervised Corpus Aware Language Model Pre-training for Dense Passage Retrieval. In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2022, Dublin, Ireland, May 22-27, 2022_ , Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (Eds.). Association for Computational Linguistics, 2843–2853.
  * Gao et al. (2022) Luyu Gao, Xueguang Ma, Jimmy Lin, and Jamie Callan. 2022.  Tevatron: An Efficient and Flexible Toolkit for Dense Retrieval.  _CoRR_ abs/2203.05765 (2022).  arXiv:2203.05765
  * Guo et al. (2022) Jiafeng Guo, Yinqiong Cai, Yixing Fan, Fei Sun, Ruqing Zhang, and Xueqi Cheng. 2022.  Semantic Models for the First-Stage Retrieval: A Comprehensive Review.  _ACM Trans. Inf. Syst._ 40, 4 (2022), 66:1–66:42.
  * Karpukhin et al. (2020) Vladimir Karpukhin, Barlas Oguz, Sewon Min, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020.  Dense Passage Retrieval for Open-Domain Question Answering.  _CoRR_ abs/2004.04906 (2020).  arXiv:2004.04906
  * Khattab and Zaharia (2020) Omar Khattab and Matei Zaharia. 2020.  ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT. In _Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, SIGIR 2020, Virtual Event, China, July 25-30, 2020_ , Jimmy X. Huang, Yi Chang, Xueqi Cheng, Jaap Kamps, Vanessa Murdock, Ji-Rong Wen, and Yiqun Liu (Eds.). ACM, 39–48.
  * Khosla et al. (2020) Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan. 2020.  Supervised Contrastive Learning. In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.).
  * Kong et al. (2022) Weize Kong, Swaraj Khadanga, Cheng Li, Shaleen Kumar Gupta, Mingyang Zhang, Wensong Xu, and Michael Bendersky. 2022.  Multi-Aspect Dense Retrieval. In _KDD ’22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 14 - 18, 2022_ , Aidong Zhang and Huzefa Rangwala (Eds.). ACM, 3178–3186.
  * Lee et al. (2019) Kenton Lee, Ming-Wei Chang, and Kristina Toutanova. 2019.  Latent Retrieval for Weakly Supervised Open Domain Question Answering. In _Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28- August 2, 2019, Volume 1: Long Papers_ , Anna Korhonen, David R. Traum, and Lluís Màrquez (Eds.). Association for Computational Linguistics, 6086–6096.
  * Lin et al. (2021a) Jimmy Lin, Rodrigo Nogueira, and Andrew Yates. 2021a.  _Pretrained Transformers for Text Ranking: BERT and Beyond_.  Morgan & Claypool Publishers.
  * Lin et al. (2021b) Jimmy Lin, Rodrigo Frassetto Nogueira, and Andrew Yates. 2021b.  _Pretrained Transformers for Text Ranking: BERT and Beyond_.  Morgan & Claypool Publishers.
  * Liu et al. (2018) Binsheng Liu, Xiaolu Lu, Oren Kurland, and J. Shane Culpepper. 2018.  Improving Search Effectiveness with Field-based Relevance Modeling. In _Proceedings of the 23rd Australasian Document Computing Symposium, ADCS 2018, Dunedin, New Zealand, December 11-12, 2018_. ACM, 11:1–11:4.
  * Lu et al. (2021) Shuqi Lu, Chenyan Xiong, Di He, Guolin Ke, Waleed Malik, Zhicheng Dou, Paul Bennett, Tie-Yan Liu, and Arnold Overwijk. 2021.  Less is More: Pre-training a Strong Siamese Encoder Using a Weak Decoder.  _CoRR_ abs/2102.09206 (2021).  arXiv:2102.09206
  * Luan et al. (2021) Yi Luan, Jacob Eisenstein, Kristina Toutanova, and Michael Collins. 2021.  Sparse, Dense, and Attentional Representations for Text Retrieval.  _Trans. Assoc. Comput. Linguistics_ 9 (2021), 329–345.
  * Ma et al. (2022) Xinyu Ma, Jiafeng Guo, Ruqing Zhang, Yixing Fan, and Xueqi Cheng. 2022.  Pre-train a Discriminative Text Encoder for Dense Retrieval via Contrastive Span Prediction. In _SIGIR ’22: The 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, Madrid, Spain, July 11 - 15, 2022_ , Enrique Amigó, Pablo Castells, Julio Gonzalo, Ben Carterette, J. Shane Culpepper, and Gabriella Kazai (Eds.). ACM, 848–858.
  * Ma et al. (2021) Xinyu Ma, Jiafeng Guo, Ruqing Zhang, Yixing Fan, Xiang Ji, and Xueqi Cheng. 2021.  PROP: Pre-training with Representative Words Prediction for Ad-hoc Retrieval.  _Proceedings of the 14th ACM International Conference on Web Search and Data Mining_ (2021).
  * Mulkar-Mehta et al. (2011) Rutu Mulkar-Mehta, Jerry R. Hobbs, and Eduard H. Hovy. 2011.  Granularity in Natural Language Discourse. In _Proceedings of the Ninth International Conference on Computational Semantics, IWCS 2011, January 12-14, 2011, Oxford, UK_ , Johan Bos and Stephen Pulman (Eds.). The Association for Computer Linguistics.
  * Qu et al. (2021) Yingqi Qu, Yuchen Ding, Jing Liu, Kai Liu, Ruiyang Ren, Wayne Xin Zhao, Daxiang Dong, Hua Wu, and Haifeng Wang. 2021.  RocketQA: An Optimized Training Approach to Dense Passage Retrieval for Open-Domain Question Answering. In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2021, Online, June 6-11, 2021_ , Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer, Dilek Hakkani-Tür, Iz Beltagy, Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou (Eds.). Association for Computational Linguistics, 5835–5847.
  * Reddy et al. (2022) Chandan K. Reddy, Lluís Màrquez, Fran Valero, Nikhil Rao, Hugo Zaragoza, Sambaran Bandyopadhyay, Arnab Biswas, Anlu Xing, and Karthik Subbian. 2022.  Shopping Queries Dataset: A Large-Scale ESCI Benchmark for Improving Product Search.  _CoRR_ abs/2206.06588 (2022).  arXiv:2206.06588
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks. In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019, Hong Kong, China, November 3-7, 2019_ , Kentaro Inui, Jing Jiang, Vincent Ng, and Xiaojun Wan (Eds.). Association for Computational Linguistics, 3980–3990.
  * Shan et al. (2023) Hongyu Shan, Qishen Zhang, Zhongyi Liu, Guannan Zhang, and Chenliang Li. 2023.  Beyond Two-Tower: Attribute Guided Representation Learning for Candidate Retrieval. In _Proceedings of the ACM Web Conference 2023_. 3173–3181.
  * Sun et al. (2023) Xiaojie Sun, Keping Bi, Jiafeng Guo, Xinyu Ma, Yixing Fan, Hongyu Shan, Qishen Zhang, and Zhongyi Liu. 2023.  Pre-Training with Aspect-Content Text Mutual Prediction for Multi-Aspect Dense Retrieval. In _Proceedings of the 32nd ACM International Conference on Information and Knowledge Management_ (Birmingham, United Kingdom) _(CIKM ’23)_. Association for Computing Machinery, New York, NY, USA, 4300–4304.  https://doi.org/10.1145/3583780.3615157
  * Tahami et al. (2020) Amir Vakili Tahami, Kamyar Ghajar, and Azadeh Shakery. 2020.  Distilling Knowledge for Fast Retrieval-based Chat-bots. In _Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, SIGIR 2020, Virtual Event, China, July 25-30, 2020_ , Jimmy X. Huang, Yi Chang, Xueqi Cheng, Jaap Kamps, Vanessa Murdock, Ji-Rong Wen, and Yiqun Liu (Eds.). ACM, 2081–2084.
  * Taylor (1953) Wilson L. Taylor. 1953.  “Cloze Procedure”: A New Tool for Measuring Readability.  _Journalism & Mass Communication Quarterly_ 30 (1953), 415 – 433.
  * Xiao et al. (2022) Shitao Xiao, Zheng Liu, Yingxia Shao, and Zhao Cao. 2022.  RetroMAE: Pre-Training Retrieval-oriented Language Models Via Masked Auto-Encoder. In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, EMNLP 2022, Abu Dhabi, United Arab Emirates, December 7-11, 2022_ , Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang (Eds.). Association for Computational Linguistics, 538–548.
  * Xiong et al. (2021) Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul N. Bennett, Junaid Ahmed, and Arnold Overwijk. 2021.  Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval. In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net.
  * Zamani et al. (2018) Hamed Zamani, Bhaskar Mitra, Xia Song, Nick Craswell, and Saurabh Tiwary. 2018.  Neural Ranking Models with Multiple Document Fields. In _Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, WSDM 2018, Marina Del Rey, CA, USA, February 5-9, 2018_ , Yi Chang, Chengxiang Zhai, Yan Liu, and Yoelle Maarek (Eds.). ACM, 700–708.
  * Zhang et al. (2022) Shunyu Zhang, Yaobo Liang, Ming Gong, Daxin Jiang, and Nan Duan. 2022.  Multi-View Document Representation Learning for Open-Domain Dense Retrieval. In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2022, Dublin, Ireland, May 22-27, 2022_ , Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (Eds.). Association for Computational Linguistics, 5990–6000.