# On Number of Particles in
Coalescing-Fragmentating Wasserstein Dynamics

Vitalii Konarovskyi  Faculty of Mathematics, Computer Science and Natural
Sciences, University of Hamburg, Bundesstraße 55, 20146 Hamburg, Germany;
Institute of Mathematics, University of Leipzig, Augustusplatz 10, 04109
Leipzig, Germany; Institute of Mathematics of NAS of Ukraine, Tereschenkivska
st. 3, 01024 Kiev, Ukraine Faculty of Mathematics, Computer Science and
Natural Sciences, University of Hamburg, Bundesstraße 55, 20146 Hamburg,
Germany<EMAIL_ADDRESS>
###### Abstract.

We consider the system of sticky-reflected Brownian particles on the real line
proposed in [4]. The model is a modification of the Howitt-Warren flow but now
the diffusion rate of particles is inversely proportional to the mass which
they transfer. It is known that the system consists of a finite number of
distinct particles for almost all times. In this paper, we show that the
system also admits an infinite number of distinct particles on a dense subset
of the time interval if and only if the function responsible for the splitting
of particles takes an infinite number of values.

###### Key words and phrases:

Sricky-reflected particle system, modified massive Arratia flow, infinite
dimensional singular SDE

###### 2020 Mathematics Subject Classification:

Primary 60K35, 60H05 ; Secondary 60H05, 60G44

The work is supported by the Grant “Leading and Young Scientists Research
Support” No. 2020.02/0303. The author thanks the referee for the careful
reading of the paper and many valuable comments.

##  1\. Introduction

In the paper we study the interacting particle system on the real line which
intuitively can be described as follows. Diffusion particles start at some
finite or infinite family of points and move independently until their
meeting. Every particle transfer a mass and its diffusion rate is inversely
proportional to its mass. When particles meet they sticky-reflect from each
other. The evolution of the particle system is similar to the motion of
particles in the Howitt-Warren flow [2]. The main difference is that the
motion of particles in our system inversely-proportionally depends on their
mass. In particular, particles with “infinitesimally small” mass have
“infinitely large” diffusion rate. We call this model the coalescing-
fragmentating Wasserstein dynamics (CFWD).

More precisely, let $X(u,t)$ be a position of particle labeled by $u\in(0,1)$
(we will shortly say “particle $u$”) at time $t\geq 0$, and $m(u,t)$ be its
mass that is the Lebesgue measure $\operatorname{Leb}$ of the corresponding
cluster $\pi(u,t)=\\{v\in(0,1):\ X(u,t)=X(v,t)\\}$. Assume that the diffusion
rate of the particle $u$ at time $t$ is inversely proportional to its mass
$m(u,t)$. The sticky-reflecting interaction between particles is defined by
the drift

$\xi(u)-\frac{1}{m(u,t)}\int_{\pi(u,t)}\xi(v)dv$

with a fixed bounded non-decreasing right-continuous function $\xi$ called the
interaction potential. Indeed, if $\xi$ is constant on $\pi(u,t)$ or
$\pi(u,t)$ is a one point set then the particle $u$ has no drift. Otherwise,
particles which stay together will have different drift for corresponding
different values of $\xi$ on $\pi(u,t)$ that makes particles to split. We
remark that the order between particles is preserved. Therefore, we may assume
that $X(u,t)\leq X(v,t)$ for all $u<v$ and $t\geq 0$.

In [4], we showed that $X$ appears as a martingale solution to the following
SDE

(1)
$\begin{split}dX_{t}&=\operatorname{pr}_{X_{t}}dW_{t}+(\xi-\operatorname{pr}_{X_{t}}\xi)dt,\quad
t\geq 0,\\\ X_{0}&=g,\end{split}$

in the space $L_{2}^{\uparrow}$ of all square-integrable functions (classes of
equivalences) $f:(0,1)\to\mathbb{R}$ which have a non-decreasing version,
$W_{t}$, $t\geq 0$, is a cylindrical Wiener process in
$L_{2}=L_{2}([0,1],du)$, $X_{t}:=X(\cdot,t)\in L_{2}^{\uparrow}$, and
$\operatorname{pr}_{f}$ denotes the orthogonal projection in $L_{2}$ onto its
subspace $L_{2}(f)$ of all $\sigma(f)$-measurable functions. The function
$g\in L_{2}^{\uparrow}$ describes the initial position of particles.

######  Remark 1.1.

For convenience of notation, considering $f\in L_{2}^{\uparrow}$ as a
function, we will always take its right continuous version on $(0,1)$, which
is unique according to, e.g., Proposition A.1 [5] and Remark A.6 ibid.

The existence result in [4] claims that for every $g\in L_{2}^{\uparrow}$
satisfying $\int_{0}^{1}g^{2+\varepsilon}(u)du<\infty$ for some
$\varepsilon>0$ there exist an $L_{2}$-valued cylindrical Wiener process
$W_{t}$, $t\geq 0$, and a continuous $L_{2}^{\uparrow}$-valued process
$X_{t}$, $t\geq 0$, both defined on the same filtered probability space
$(\Omega,\mathcal{F},(\mathcal{F})_{t\geq 0},\mathbb{P})$ such that
$\mathbb{E}\|X_{t}\|_{L_{2}}^{2}<\infty$, $t\geq 0$, and

$X_{t}=g+\int_{0}^{t}\operatorname{pr}_{X_{s}}dW_{s}+\int_{0}^{t}(\xi-\operatorname{pr}_{X_{s}}\xi)ds,\quad
t\geq 0.$

We call such $X_{t}$, $t\geq 0$, a weak solution to (1) and assume that the
process in a mathematical description of the CFWD.

Since $X_{t}(\omega)$ is a class of equivalences, the value $X_{t}(u,\omega)$
is not well defined for every $u\in(0,1)$. Note that $X_{t}(\omega)$ is an
element of $L_{2}^{\uparrow}$, therefore, one can easily see that there exists
its unique right-continuous modification, denoted also by $X_{t}(\omega)$. In
agreement with Remark 1.1, we will hereinafter consider this right-continuous
version of $X$. In general, the process $X_{t}(u)$, $t\geq 0$, is not
continuous. But it turns out that under some regularity conditions of the
initial condition $g$ and the interaction potential $\xi$ one can show that
$X(u,\cdot)=X_{t}(u)$ is a continuous semi-martingale which satisfies some
natural conditions for each $u$. We will not use those conditions for the
proof of our main result stated in Theorem 1.1, however, we will provide them
here to help the reader better understand the particle model.

Let $\mathcal{D}\big{(}[0,1],\mathcal{C}[0,\infty)\big{)}$ denote the Skorohod
space of all càdlàg functions from $[0,1]$ to the space
$\mathcal{C}[0,\infty)$ of real-valued continuous functions defined on
$[0,\infty)$. If the initial condition $g$ and the interaction potential $\xi$
are right-continuous and piecewise $(\frac{1}{2}+)$-Hölder continuous111There
exist $\varepsilon>0$ and a finite partition of the interval $[0,1]$ such that
the functions are $\left(\frac{1}{2}+\varepsilon\right)$-Hölder continuous on
each interval of the partition, then equation (1) admits a weak solution with
a modification $\\{X(u,t),\ t\geq 0,\ u\in[0,1]\\}$ from
$\mathcal{D}\big{(}[0,1],\mathcal{C}[0,\infty)\big{)}$ satisfying the
following properties

  1. (R1)

for all $u\in[0,1]$, $X(u,0)=g(u)$;

  2. (R2)

for each $u<v$ from $[0,1]$ and $t\geq 0$, $X(u,t)\leq X(u,t)$;

  3. (R3)

the process

$M(u,t):=X(u,t)-g(u)-\int_{0}^{t}\left(\xi(u)-\frac{1}{m(u,s)}\int_{\pi(u,s)}\xi(v)dv\right)ds,\quad
t\geq 0,$

is a continuous square integrable martingale with respect to the filtration
$\mathcal{F}_{t}=\sigma(X(v,s),\ v\in[0,1],\ s\leq t)$, $t\geq 0$;

  4. (R4)

the joint quadratic variation of $M(u,\cdot)$ and $M(v,\cdot)$ equals

$\langle
M(u,\cdot),M(v,\cdot)\rangle_{t}=\int_{0}^{t}\frac{\mathbb{I}_{\left\\{X(u,s)=X(v,s)\right\\}}}{m(u,s)}ds,\quad
t\geq 0.$

We remark that the uniqueness of a weak solution to equation (1) remains an
important open problem. For interested readers we would like to pointed out
that the CFWD admits an invariant measure and its reversible version was
stydied in [8]. Its connection with the Wasserstein diffusion [12] and the
geometry of the Wasserstein space of probability measures on the real line
also were studied there.

We will denote by $\sharp f$ a number of distinct values of $f\in
L_{2}^{\uparrow}$, which is well-defined according to Remark 1.1. By Lemma 6.1
[5], the square of the Hilbert-Schmidt norm of the orthogonal projection
$\operatorname{pr}_{f}$ coinsides with $\sharp f$, i.e.

(2)
$\|\operatorname{pr}_{f}\|_{HS}^{2}:=\sum_{n=1}^{\infty}\|\operatorname{pr}_{f}e_{n}\|_{L_{2}}^{2}=\sharp
f,$

where $\\{e_{n},\ n\geq 1\\}$ is an orthonormal basis in $L_{2}$. Therefore,
we can interpret the random variable
$\|\operatorname{pr}_{X_{t}}\|^{2}_{HS}=\sharp X_{t}$ as a number of distinct
particles in CFWD at time $t\geq 0$. In particular, if $X_{t}=X(\cdot,t)$,
$t\geq 0$, where the random element $\\{X(u,t),\ t\geq 0,\ u\in[0,1]\\}$ in
$\mathcal{D}\big{(}[0,1],\mathcal{C}[0,\infty)\big{)}$ satisfies conditions
((R1))-((R4)), then $\sharp X(\cdot,t)$ is exactly the number of distinct
particles at time $t\geq 0$ in the CFWD. Since $X_{t}$, $t\geq 0$, is square
integrable and $\xi$ is bounded, Theorem 2.4 [1] and equality (2) imply

$\int_{0}^{t}\mathbb{E}(\sharp X_{s})ds<\infty$

for all $t\geq 0$. This yields that

(3) $\mathbb{P}\left\\{\sharp X_{t}<\infty\ \mbox{for a.e.}\
t\in[0,\infty)\right\\}=1,$

i.e. the CFWD consists of a finite number of particles at almost all times
with probability 1. The goal of this paper is to show that almost surely there
exists a (random) dense subset of the time interval $[0,\infty)$ on which the
CFWD has an infinite number of particles if and only if $\sharp\xi=\infty$. We
remark that the property $\sharp\xi=\infty$ is equivalent to the fact that
$L_{2}(\xi)$ is infinite dimensional, by (2).

######  Theorem 1.1.

  1. (i)

If $\sharp\xi=+\infty$, then almost surely there exists a (random) dense
subset $S$ of $[0,\infty)$ such that $\sharp X_{t}=\infty$, $t\in S$, that is,

$\mathbb{P}\left\\{\exists S\ \mbox{dense in}\ [0,\infty)\ \mbox{such that}\
\sharp X_{t}=\infty,\ t\in S\right\\}=1.$

  2. (ii)

If $\sharp\xi<\infty$, then

(4) $\mathbb{P}\left\\{\sharp X_{t}<\infty,\ \ t\in[0,\infty)\right\\}=1.$

We note that the CFWD coincides with the modified massive Arratia flow [5, 6,
7, 9, 10] for $\xi=0$. In this case, equality (4) was stated in [5,
Proposition 6.2].

##  2\. Auxiliary statements

Let $\mathcal{C}\big{(}[a,b],L_{2}^{\uparrow}\big{)}$ denote the space of
continuous functions from $[a,b]$ to $L_{2}^{\uparrow}$ endowed with the usual
topology. We recall that the map $h\mapsto\|\operatorname{pr}_{h}f\|_{L_{2}}$
from $L_{2}^{\uparrow}$ to $\mathbb{R}$ is lower semi-continuous for each
$f\in L_{2}$, that is,

(5)
$\|\operatorname{pr}_{h}f\|_{L_{2}}\leq\varliminf_{n\to\infty}\|\operatorname{pr}_{h_{n}}f\|_{L_{2}},\quad\mbox{as}\
\ h_{n}\to h\ \ \mbox{in}\ \ L_{2}^{\uparrow}.$

The proof of this fact can be found in [4, Lemma A.4]. By Fatou’s lemma, the
map $h\mapsto\|\operatorname{pr}_{h}\|_{HS}$ is lower semi-continuous as well.

The following lemma is needed for the measurability of events which will
appear in the proof of Theorem 1.1.

######  Lemma 2.1.

For each $[a,b]$, the map $f\mapsto\sup_{t\in[a,b]}\|f_{t}\|_{HS}$ from
$\mathcal{C}\big{(}[a,b],L_{2}^{\uparrow}\big{)}$ to
$\mathbb{R}\cup\\{+\infty\\}$ is measurable.

###### Proof.

Let $t\geq 0$ be fixed. Note that the map
$f\mapsto\|\operatorname{pr}_{f_{t}}\|_{HS}$ from
$\mathcal{C}\big{(}[a,b],L_{2}^{\uparrow}\big{)}$ to $\mathbb{R}$ is lower
semi-continuous because it is the composition of the continuous map
$\mathcal{C}\big{(}[a,b],L_{2}^{\uparrow}\big{)}\ni g\mapsto g_{t}\in
L_{2}^{\uparrow}$ and the lower semi-continuouous map $L_{2}^{\uparrow}\ni
h\mapsto\|\operatorname{pr}_{h}\|_{HS}\in\mathbb{R}$. This yields the claim of
the lemmas due to the measurability of
$f\mapsto\|\operatorname{pr}_{f_{t}}\|_{HS}$ and the equality

$\displaystyle\\{f:\ \sup_{t\in[a,b]}\|f_{t}\|_{HS}\leq c\\}$
$\displaystyle=\bigcap_{t\in[a,b]\cap\mathbb{Q}}\left\\{f:\
\|\operatorname{pr}_{f_{t}}\|_{HS}\leq c\right\\},$

for all $c\geq 0$. ∎

The following lemma directly follows from the lower semi-continuity of the map
$t\mapsto\|\operatorname{pr}_{f_{t}}\|_{HS}$ for every
$f\in\mathcal{C}\big{(}[0,\infty),L_{2}^{\uparrow}\big{)}$.

######  Lemma 2.2.

For every $f\in\mathcal{C}\big{(}[0,\infty),L_{2}^{\uparrow}\big{)}$, $c\geq
0$ and $0\leq a<b$ the set $A_{c}^{f,a,b}:=\big{\\{}t\in[a,b]:\
\|\operatorname{pr}_{f_{t}}\|^{2}_{HS}\leq c\big{\\}}$ is closed in
$[0,\infty)$.

We will also need a property of a function
$f\in\mathcal{C}\big{(}[0,\infty),L_{2}^{\uparrow}\big{)}$ if the Hilbert-
Schmidt norm $\|\operatorname{pr}_{f_{t}}\|_{HS}$, $t\in[0,\infty)$, is
constant on an interval.

######  Lemma 2.3.

Assume that $f$ belongs to
$\mathcal{C}\big{(}[0,\infty),L_{2}^{\uparrow}\big{)}$ and
$\|\operatorname{pr}_{f_{t}}\|_{HS}$, $t\in[a,b]$, is constant for some $0\leq
a<b$. Then

  1. (i)

for every $u_{0}\in(0,1)$ there exist $u_{1}<u_{0}<u_{2}$ and $\alpha<\beta$
from $[a,b]$ such that $f_{t}$ is constant on $[u_{1},u_{0})$ and
$[u_{0},u_{2})$ for each $t\in[\alpha,\beta]$;

  2. (ii)

for $u_{0}=0$ (resp. $u_{0}$=1) there exist $u_{2}>u_{0}$ (resp.
$u_{1}<u_{0}$) and $\alpha<\beta$ from $[a,b]$ such that $f_{t}$ is constant
on $[u_{0},u_{2})$ (resp. on $[u_{1},u_{0}]$) for each $t\in[\alpha,\beta]$.

###### Proof.

Since $\|\operatorname{pr}_{f_{\cdot}}\|_{HS}$ is constant on $[a,b]$, the
function $f_{t}$ takes a fixed number of distinct values, denoted by $n$, for
each $t\in[a,b]$, by equality (2). Let

$f_{t}=\sum_{k=1}^{n}x_{k}(t)\mathbb{I}_{[q_{k-1}(t),q_{k}(t))},\quad
t\in[a,b],$

where $x_{1}(t)<\ldots<x_{n}(t)$ and $0=q_{0}(t)<q_{1}(t)<\ldots<q_{n}(t)=1$.
From continuity of $f_{t}$, $t\geq 0$, it follows that the functions $x_{k}$
and $q_{k}$ are continuous on $[a,b]$ for each $k$ in $[n]:=\\{1,\dots,n\\}$.

If there exists $l\in[n]$ such that

(6) $u_{0}\in(q_{l-1}(t),q_{l}(t))\quad\mbox{for some}\ \ t\in(a,b),$

then one can take $u_{1}<u_{0}<u_{2}$ and $\alpha<\beta$ from $[a,b]$
satisfying $u_{1},u_{2}$ in $(q_{l-1}(t),q_{l}(t))$ for all
$t\in[\alpha,\beta]$, by the continuity of $q_{k}$, $k\in[n]$. This trivially
implies the statement of the lemma. If $l$ satisfying (6) does not exist, then
$u_{0}=q_{l}(t)$ for some $l\in[n]\cup\\{0\\}$ and all $t\in[a,b]$, which also
yields the statement. ∎

##  3\. Proof of Theorem 1.1

We first consider the case $\sharp\xi=\infty$. In order to show that with
probability 1 there exists a dense subset $S$ of $[0,\infty)$ such that
$\sharp X_{t}=\infty$ for all $t\in S$, it is enough to prove that for each
$0\leq a<b$ one has

(7) $\mathbb{P}\left\\{\sup_{t\in[a,b]}\sharp X_{t}=\infty\right\\}=1.$

Recall that the measurability of $\sup_{t\in[a,b]}\sharp X_{t}$ follows from
Lemma 2.1 and equality (2). We suppose that equality (7) is false, that is,

$\mathbb{P}\left\\{\sup_{t\in[a,b]}\sharp X_{t}<\infty\right\\}>0.$

Setting $A_{n}^{a,b}(\omega):=\left\\{t\in[a,b]:\
\|\operatorname{pr}_{X_{t}(\omega)}\|^{2}_{HS}\leq n\right\\}$,
$\omega\in\Omega$, and using equality (2), we can conclude that

$\mathbb{P}\left\\{\bigcup_{n=1}^{\infty}A^{a,b}_{n}=[a,b]\right\\}>0.$

By Lemma 2.2 and the Baire category theorem, we have

$\mathbb{P}\big{\\{}\exists a_{1}<b_{1}\ \ \mbox{from}\ \ [a,b]\ \ \mbox{and}\
\ n\in\mathbb{N}\ \ \mbox{such that}\ \
\|\operatorname{pr}_{X_{t}}\|_{HS}^{2}\leq n,\ \
t\in[a_{1},b_{1}]\big{\\}}>0.$

Consequently, we can find non-random $a_{1}<b_{1}$ from $[a,b]$ and
$k_{1}\in\mathbb{N}$ such that

$\mathbb{P}\Big{\\{}\|\operatorname{pr}_{X_{t}}\|_{HS}^{2}\leq k_{1},\ \
t\in[a_{1},b_{1}]\Big{\\}}>0.$

Let $k_{2}\in[k_{1}]$ be the minimal number such that

$\mathbb{P}\Big{\\{}\|\operatorname{pr}_{X_{t}}\|_{HS}^{2}\leq k_{2},\ \
t\in[a_{1},b_{1}]\Big{\\}}>0.$

By the minimality of $k_{2}$, we can conclude that

$\mathbb{P}\left\\{A^{a_{1},b_{1}}_{k_{2}}\setminus
A^{a_{1},b_{1}}_{k_{2}-1}\not=\emptyset\right\\}>0,$

where $A^{a_{1},b_{1}}_{0}=\emptyset$ if $k_{2}=1$. Next, since
$A^{a_{1},b_{1}}_{k_{2}}\setminus A^{a_{1},b_{1}}_{k_{2}-1}$ is open in
$A^{a_{1},b_{1}}_{k_{2}}=[a_{1},b_{1}]$ and non-empty with positive
probability, one can find non-random $a_{2}<b_{2}$ from $[a_{1},b_{1}]$
satisfying

$\mathbb{P}\Big{\\{}\|\operatorname{pr}_{X_{t}}\|_{HS}^{2}=k_{2},\ \
t\in[a_{2},b_{2}]\Big{\\}}>0.$

Next, due to the equality $\sharp\xi=\infty$, there exists $u_{0}\in[0,1]$
such that $\xi$ takes an infinite number of distinct values in $[u_{1},u_{0})$
for all $u_{1}<u_{0}$ or in $[u_{0},u_{2})$ for all $u_{2}>u_{0}$. Using Lemma
2.3 and the monotonicity of $X_{t}(\omega)$ for all $t$ and $\omega$, one can
find non-random $a_{3}<b_{3}$ from $[a_{2},b_{2}]$ and $u<v$ such that
$u=u_{0}$ or $v=u_{0}$, $\xi$ takes an infinite number of distinct values on
$[u,v]$ and

$\mathbb{P}\big{\\{}X_{t}(u)=X_{t}(\tilde{u}),\ \ \tilde{u}\in[u,v),\ \
t\in[a_{3},b_{3}]\big{\\}}>0.$

Let $h:=\mathbb{I}_{[(u+v)/2,v)}-\mathbb{I}_{[u,(u+v)/2)}$. Since $X_{t}$,
$t\geq 0$, solves equation (1) and belongs to $L_{2}^{\uparrow}$, one has that
$(X_{t},h)_{L_{2}}$, $t\geq 0$, is a continuous non-negative process such that

$M_{h}(t)=(X_{t},h)_{L_{2}}-\int_{0}^{t}\left(\xi-\operatorname{pr}_{X_{s}}\xi,h\right)_{L_{2}}ds,\quad
t\geq 0,$

is a continuous square integrable $(\mathcal{F}_{t})$-martingale with
quadratic variation

$\langle
M_{h}\rangle_{t}=\int_{0}^{t}\|\operatorname{pr}_{X_{s}}h\|_{2}^{2}ds,\quad
t\geq 0.$

We take $\omega$ from the event

$A:=\left\\{\forall t\in[a_{3},b_{3}]\ \ X_{t}\ \ \mbox{is constant on}\ \
[u,v)\right\\},$

and note that $(X_{t}(\omega),h)_{L_{2}}=0$,
$\operatorname{pr}_{X_{s}(\omega)}h=0$ and

$(\operatorname{pr}_{X_{s}}\xi,h)_{L_{2}}=(\xi,\operatorname{pr}_{X_{s}}h)_{L_{2}}=0$

for all $s\in[a_{3},b_{3}]$ due to the choice of $h$. Thus, we can conclude
that

(8)
$M_{h}(t,\omega)=-\int_{0}^{a_{3}}(\xi-\operatorname{pr}_{X_{s}(\omega)}\xi,h)_{L_{2}}ds-\int_{a_{3}}^{t}(\xi,h)_{L_{2}}ds$

and

$\langle
M_{h}\rangle_{t}(\omega)=\int_{0}^{a_{3}}\|\operatorname{pr}_{X_{s}(\omega)}h\|_{2}^{2}ds$

for all $t\in[a_{3},b_{3}]$. The equality for the quadratic variation of
$M_{h}$ and the representation of continuous martingales as a time changed
Brownian motion (see [3, Theorem II.7.2’]) imply that
$M_{h}(t,\omega)=M_{h}(a_{3},\omega)$, $t\in[a_{3},b_{3}]$ for a.e. $\omega\in
A$. Since the non-decreasing function $\xi$ is not a constant on $[u,v]$, the
inner product $(\xi,h)_{L_{2}}$ is strictly positive due to the choice of $h$.
According to equality (8), $M_{h}(t,\omega)$, $t\in[a_{3},b_{3}]$, is strictly
increasing (in $t$) for a.e. $\omega\in A$ because $(\xi,h)_{L_{2}}>0$. Since
$\mathbb{P}\\{A\\}>0$, we get a contradiction. This completes the proof of the
first part of the theorem.

We next prove claim (ii). Due to $\sharp\xi<\infty$, there exists a finite
partition $\pi_{k}$, $k\in[n]$, of the interval $[0,1)$ by intervals of the
form $[a,b)$ such that

$\xi(u)=\sum_{k=1}^{n}\xi_{k}\mathbb{I}_{\pi_{k}}(u),\quad u\in[0,1).$

In order to prove (ii), it is enough to show that almost surely $X_{t}$ takes
a finite number of distinct values on every interval $\pi_{k}$. We fix
$k\in[n]$ and consider the countable family of functions
$h_{u,v}:=\mathbb{I}_{[(u+v)/2,v)}-\mathbb{I}_{[u,(u+v)/2)}$ from $L_{2}$,
$u,v\in\pi_{k}\cap\mathbb{Q}$, denoted by $\mathcal{R}$.

We first remark that for every $h\in\mathcal{R}$ the process
$(X_{t},h)_{L_{2}}$, $t\geq 0$, is a non-negative continuous supermartingale.
Indeed, the non-negativity follows from the inequality $(f,h)_{L_{2}}\geq 0$
for every $f\in L_{2}^{\uparrow}$ and $h\in\mathcal{R}$. In order to show that
$(X_{t},h)_{L_{2}}$, $t\geq 0$, is a supermartingale, we use the fact that it
is a weak martingale solution to equation (1). Hence for each
$h\in\mathcal{R}$

$\displaystyle(X_{t},h)_{L_{2}}=M_{h}(t)+\int_{0}^{t}\left(\xi-\operatorname{pr}_{X_{s}}\xi,h\right)_{L_{2}}ds=M_{h}(t)-\int_{0}^{t}\left(\operatorname{pr}_{X_{s}}\xi,h\right)_{L_{2}}ds,\quad
t\geq 0,$

where $M_{h}$ is a martingale. According to Lemma A.2 [4], the orthogonal
projection $\operatorname{pr}_{f}$ maps the space $L_{2}^{\uparrow}$ into
$L_{2}^{\uparrow}$ for every $f\in L_{2}^{\uparrow}$. Hence,
$\operatorname{pr}_{X_{s}}\xi\in L_{2}^{\uparrow}$ and, therefore,
$\left(\operatorname{pr}_{X_{s}}\xi,h\right)\geq 0$. This implies that
$(X_{t},h)_{L_{2}}$, $t\geq 0$, is a continuous supermartingale.

It is well known that hitting at zero a positive continuous suparmartingales
stays there forewer (see e.g. Proposition II.3.4 [11]). We denote the
corresponding event for the supermartingale $(X_{t},h)_{L_{2}}$, $t\geq 0$, by
$\Omega_{h}$, i.e

$\Omega_{h}=\left\\{\begin{array}[]{l}\mbox{for every}\ t\in[0,\infty)\
\mbox{the equality}\ (X_{t},h)_{L_{2}}=0\\\ \mbox{implies}\
(X_{s},h)_{L_{2}}=0\ \mbox{for all}\ s\geq t\\\ \end{array}\right\\}.$

Then $\mathbb{P}\\{\Omega_{h}\\}=1$ for every $h\in\mathcal{R}$. Thus, the
event $\Omega^{\prime}:=\bigcap_{h\in\mathcal{R}}\Omega_{h}$ has the
probability 1. Take $\omega\in\Omega^{\prime}$, $u,v\in(0,1)$, and $t\geq 0$
such that $X_{t}(u,\omega)=X_{t}(v,\omega)$. Then for every $h\in\mathcal{R}$
one has $(X_{t}(\omega),h)_{L_{2}}=0$ and, consequently,
$(X_{s}(\omega),h)_{L_{2}}=0$ for all $s\geq t$, by the choice of $\omega$.
Using the right continuity of $X_{s}(\cdot,\omega)$ (see Remark 1.1), it is
easily seen that $X_{s}(u)=X_{s}(v)$, $s\geq t$. In other words, the process
$X_{t}$, $t\geq 0$, satisfies the following property: if $X_{t}$ is constant
on an interval $[u,v]\in\pi_{k}$ for some $k\in[n]$, then it remains constant
on this interval for every $s\geq t$. Combining this coalescing property of
$X_{t}$, $t\geq 0$, on every interval $\pi_{k}$, $k\in[n]$ with equality (3),
we get claim (ii) of the theorem.

## References

  * [1] Leszek Gawarecki and Vidyadhar Mandrekar, _Stochastic differential equations in infinite dimensions with applications to stochastic partial differential equations_ , Probability and its Applications (New York), Springer, Heidelberg, 2011. MR 2560625
  * [2] Chris Howitt and Jon Warren, _Consistent families of Brownian motions and stochastic flows of kernels_ , Ann. Probab. 37 (2009), no. 4, 1237–1272. MR 2546745
  * [3] Nobuyuki Ikeda and Shinzo Watanabe, _Stochastic differential equations and diffusion processes_ , second ed., North-Holland Mathematical Library, vol. 24, North-Holland Publishing Co., Amsterdam; Kodansha, Ltd., Tokyo, 1989\. MR 1011252
  * [4] Vitalii Konarovskyi, _Coalescing-Fragmentating Wasserstein Dynamics: particle approach_ , arXiv:1711.03011 (2017).
  * [5] by same author, _On asymptotic behavior of the modified Arratia flow_ , Electron. J. Probab. 22 (2017), Paper No. 19, 31. MR 3622889
  * [6] by same author, _A system of coalescing heavy diffusion particles on the real line_ , Ann. Probab. 45 (2017), no. 5, 3293–3335. MR 3706744
  * [7] Vitalii Konarovskyi and Victor Marx, _On conditioning brownian particles to coalesce_ , arXiv:2008.02568 (2020).
  * [8] Vitalii Konarovskyi and Max von Renesse, _Reversible Coalescing-Fragmentating Wasserstein Dynamics on the Real Line_ , arXiv:1709.02839 (2017).
  * [9] Vitalii Konarovskyi and Max-K. von Renesse, _Modified massive Arratia flow and Wasserstein diffusion_ , Comm. Pure Appl. Math. 72 (2019), no. 4, 764–800. MR 3914882
  * [10] Victor Marx, _A new approach for the construction of a Wasserstein diffusion_ , Electron. J. Probab. 23 (2018), Paper No. 124, 54. MR 3896861
  * [11] Daniel Revuz and Marc Yor, _Continuous martingales and Brownian motion_ , third ed., Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 293, Springer-Verlag, Berlin, 1999\. MR 1725357
  * [12] Max-K. von Renesse and Karl-Theodor Sturm, _Entropic measure and Wasserstein diffusion_ , Ann. Probab. 37 (2009), no. 3, 1114–1191. MR 2537551


# Enquire One’s Parent and Child Before Decision: Fully Exploit Hierarchical
Structure for Self-Supervised Taxonomy Expansion

Suyuchen Wang<EMAIL_ADDRESS>0000-0003-0404-2921 Mila & DIRO,
Université de MontréalMontréalQuébecCanada ,  Ruihui Zhao
<EMAIL_ADDRESS>Tencent Jarvis LabShenzhenGuangdongChina ,  Xi Chen
<EMAIL_ADDRESS>Tencent Jarvis LabShenzhenGuangdongChina ,  Yefeng
Zheng<EMAIL_ADDRESS>Tencent Jarvis LabShenzhenGuangdongChina and
Bang Liu<EMAIL_ADDRESS>Mila & DIRO, Université de
MontréalMontréalQuébecCanada

(2021)

###### Abstract.

Taxonomy is a hierarchically structured knowledge graph that plays a crucial
role in machine intelligence. The taxonomy expansion task aims to find a
position for a new term in an existing taxonomy to capture the emerging
knowledge in the world and keep the taxonomy dynamically updated. Previous
taxonomy expansion solutions neglect valuable information brought by the
hierarchical structure and evaluate the correctness of merely an added edge,
which downgrade the problem to node-pair scoring or mini-path classification.
In this paper, we propose the Hierarchy Expansion Framework (HEF), which fully
exploits the hierarchical structure’s properties to maximize the coherence of
expanded taxonomy. HEF makes use of taxonomy’s hierarchical structure in
multiple aspects: i) HEF utilizes subtrees containing most relevant nodes as
self-supervision data for a complete comparison of parental and sibling
relations; ii) HEF adopts a coherence modeling module to evaluate the
coherence of a taxonomy’s subtree by integrating hypernymy relation detection
and several tree-exclusive features; iii) HEF introduces the Fitting Score for
position selection, which explicitly evaluates both path and level selections
and takes full advantage of parental relations to interchange information for
disambiguation and self-correction. Extensive experiments show that by better
exploiting the hierarchical structure and optimizing taxonomy’s coherence, HEF
vastly surpasses the prior state-of-the-art on three benchmark datasets by an
average improvement of 46.7% in accuracy and 32.3% in mean reciprocal rank.

taxonomy expansion, self-supervised learning, hierarchical structure

††copyright: none††copyright: acmcopyright††journalyear: 2021††conference: WWW
’21: The Web Conference; April 19–23, 2021; Ljubljana, Slovenia††booktitle:
WWW ’21: The Web Conference, April 19–23, Ljubljana, Slovenia††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06

##  1\. Introduction

Figure 1. An illustration of the taxonomy expansion task and the contributions
of the proposed HEF model.

Taxonomy is a particular type of hierarchical knowledge graph that portrays
the hypernym-hyponym relations or “is-A” relations of various concepts and
entities. They have been adopted as the underlying infrastructure of a wide
range of online services in various domains, such as product catalogs for
e-commerce (Karamanolakis et al., 2020; Luo et al., 2020), scientific indices
like MeSH (Lipscomb, 2000), and lexical databases like WordNet (Miller, 1995).
A well-constructed taxonomy can assist various downstream tasks, including web
content tagging (Liu et al., 2019; Peng et al., 2019), web searching (Yin and
Shah, 2010), personalized recommendation (Huang et al., 2019) and helping
users achieve quick navigation on web applications (Hua et al., 2017).
Manually constructing and maintaining a taxonomy is laborious, expensive and
time-consuming. It is also highly inefficient and detrimental for downstream
tasks if we construct a taxonomy from scratch (Velardi et al., 2013; Gupta et
al., 2017) as long as the taxonomy has new terms to be added. A more realistic
strategy is to insert new terms (“query”) into an existing taxonomy, i.e., the
seed taxonomy, as a child of an existing node in the taxonomy (“anchor”)
without modifying its original structure to best preserve its design. This
problem is called taxonomy expansion (Jurgens and Pilehvar, 2016).

Early taxonomy expansion approaches use terms that do not exist in the seed
taxonomy and its best-suited position in the seed taxonomy as training data
(Jurgens and Pilehvar, 2015). However, it suffers from the insufficiency of
training data and the shortage of taxonomy structure supervision. More recent
solutions adopt self-supervision and try to exploit the information of nodes
in the seed taxonomy (seed nodes) to perform node pair matching (Shen et al.,
2020) or classification along mini paths in the taxonomy (Yu et al., 2020).
However, these approaches do not fully utilize the taxonomy’s hierarchical
structure’s characteristics, and neglect the coherence of the extended
taxonomy which oughts to be the core of the taxonomy expansion task. More
specifically, existing approaches do not model a hierarchical structure
identical to the taxonomy. Instead, they use ego-nets (Shen et al., 2020) or
mini-paths (Yu et al., 2020) and feature few or no tree-exclusive information,
making them unable to extract or learn the complete hierarchical design of a
taxonomy. Besides, they do not consider the coherence of a taxonomy. They
manage to find the most suitable node in a limited subgraph and only evaluate
the correctness of a single edge instead of the expanded taxonomy, which
downgrades the taxonomy expansion task to a hypernymy detection task. Lastly,
their scoring approach regards the anchor node as an individual node without
considering the hierarchical context information. However, the hierarchical
structure provides multi-aspect criteria to evaluate a node, such as its path
or level correctness. The structure also marks the nodes that are most likely
to be wrongly chosen to be a parent in a specific parental relation.

To solve all the stated flaws in previous works, we propose the Hierarchy
Expansion Framework (HEF), which aims to maximize the coherence of the
expanded taxonomy instead of the fitness of a single edge by fully exploiting
the hierarchical structure of a taxonomy for self-supervised training, as well
as modeling and evaluating the structure of taxonomy. HEF’s designs and goals
are illustrated in Fig. 1. Specifically, we make the following contributions.

Firstly, we design an innovative hierarchical data structure for self-
supervision to mimic how humans construct a taxonomy. Relations in a taxonomy
include hypernymy relations along a root-path and similarity among siblings.
To find the most suitable parent node for the query term, human experts need
to compare an anchor node with all its ancestors to distinguish the most
appropriate one and compare the query with its potential siblings to testify
their similarity. For example, to choose the parent for query “black tea” in
the food taxonomy, the most appropriate anchor “tea” can only be selected by
distinguishing from its ancestors “beverage” and “food”, which are all “black
tea” ’s hypernyms, as well as compare the query “black tea” with “tea”’s
children like “iced tea” and “oolong” to guarantee similarity among siblings.
Thus, we design a new structure called “ego-tree” for self-supervision, which
contains all ancestors and sample of children of a node for taxonomy structure
learning. Our ego-tree incorporates richer topological context information for
attaching a query term to a candidate parent with minimal computation cost
compared to previous approaches based on node pair matching or path
information.

Secondly, we design a new modeling strategy to perform explicit ego-tree
coherence modeling apart from the traditional node-pair hypernymy detection.
Instead of merely modeling the correctness of the added edge, we adopt a more
comprehensive approach to detect whether the anchor’s ego-tree after adding
the query maintains the original design of the seed taxonomy. The design of
taxonomy includes natural hypernymy relations, which needs the representation
of node-pair relations and expert-curated level configurations, such as
species must be placed in the eighth level of biological taxonomy, or adding
one more adjective to a term means exactly one level higher in the e-commerce
taxonomy. We adopt a coherence modeling module to detect the two aspects of
coherence: i) For natural hypernymy relations, we adopt a hypernymy detection
module to represent the relation between the query and each node in the
anchor’s ego-tree. ii) For expert-curated designs, we integrate hierarchy-
exclusive features such as embeddings of a node’s absolute level and relative
level to the anchor into the coherence modeling module.

Thirdly, we design a multi-dimensional evaluation to score the coherence of
the expanded taxonomy. The hierarchical structure of taxonomy allows the model
to evaluate the correctness of path selection and level selection separately
and the parental relationships in a hierarchy not only allow the model to
disambiguate the most similar terms but also enables the model to self-correct
its level selection by deciding the current anchor’s granularity is too high
or too low. We introduce the Fitting Score for the coherence evaluation of the
expanded ego-tree by using a Pathfinder and a Stopper to score path
correctness and level correctness, respectively. The Fitting Score calculation
also disambiguates the most appropriate anchor from its parent and children
and self-correct its level selection by bringing the level suggestion from the
anchor’s parent and one of its children into consideration. The Fitting
Score’s optimization adopts a self-supervised multi-task training paradigm for
the Pathfinder and Stopper, which automatically generates training data from
the seed taxonomy to utilize its information fully.

We conduct extensive evaluations based on three benchmark datasets to compare
our method with state-of-the-art baseline approaches. The results suggest that
the proposed HEF model significantly surpasses the previous solutions on all
three datasets by an average improvement of 46.7% in accuracy and 32.3% in
mean reciprocal rank. A series of ablation studies further demonstrate that
HEF can effectively perform the taxonomy expansion task.

##  2\. Related Work

Taxonomy Construction. Taxonomy construction aims to create a tree-structured
taxonomy with a set of terms (such as concepts and entities) from scratch,
integrating hypernymy discovery and tree structure alignment. It can be
further separated into two subdivisions. The first focuses on topic-based
taxonomy, where each node is a cluster of several terms sharing the same topic
(Zhang et al., 2018; Shang et al., 2020b). The other subdivision tackles the
problem of term-based taxonomy construction, in which each node represents the
term itself (Cocos et al., 2018; Shen et al., 2018; Mao et al., 2018). A
typical pipeline for this task is to extract “is-A” relations with a hypernymy
detection model first using either a pattern-based model (Hearst, 1992;
Agichtein and Gravano, 2000; Jiang et al., 2017; Roller et al., 2018) or a
distributional model (Lin, 1998; Yin and Roth, 2018; Wang et al., 2019; Dash
et al., 2020), then integrate and prune the mined hypernym-hyponym pairs into
a single directed acyclic graph (DAG) or tree (Gupta et al., 2017). More
recent solutions utilize hyperbolic embeddings (Le et al., 2019) or transfer
learning (Shang et al., 2020a) to boost performance.

Taxonomy Expansion. In the taxonomy expansion task, an expert-curated seed
taxonomy like MeSH (Lipscomb, 2000) is provided as both the guidance and the
base for adding new terms. The taxonomy expansion task is a ranking task to
maximize a score of a node and its ground-truth parent in the taxonomy. Wang
et al. (Wang et al., 2014) adopted Dirichlet distribution to model the
parental relations. ETF (Vedula et al., 2018) trained a learning-to-rank
framework with handcrafted structural and semantic features. Arborist (Manzoor
et al., 2020) calculated the ranking score in a bi-linear form and adopted
margin ranking loss. TaxoExpan (Shen et al., 2020) modeled the anchor node by
passing messages from its egonet instead of considering a single node, and
scored by feeding a concatenation of egonet representation and query embedding
to a feed-forward layer. STEAM (Yu et al., 2020) transformed the scoring task
into a classification task on mini-paths and performed model ensemble of three
sub-models processing distributional, contextual, and lexical-syntactic
features, respectively. However, existing approaches mostly neglect the
characteristics of taxonomy’s hierarchical structure and only evaluate the
correctness of a single edge from anchor to query. On the contrary, our method
utilizes the features and relations brought by the hierarchical structure and
aims to enhance the expanded taxonomy’s overall coherence.

Modeling of Tree-Structured Data. Taxonomy expansion involves modeling a tree
or graph structure. Plenty of works have been devoted to extending recurrent
models to tree structures, like Tree-LSTM (Tai et al., 2015). For explicit
tree-structure modeling, previous approaches include modeling the likelihood
of a Bayesian network (Fountain and Lapata, 2012; Wang et al., 2014) or using
graph neural net variants (Shen et al., 2020; Yu et al., 2020). Recently,
Transformers (Vaswani et al., 2017) achieved state-of-the-art performance in
the program translation task by designing a novel positional encoding related
to paths in the tree (Shiv and Quirk, 2019) or merely transforming a tree to
sequence by traversing its nodes (Kim et al., 2020). In our work, we model
tree-structure by a Transformer encoder, which, to the best of our knowledge,
is the first to use the Transformer for taxonomy modeling. We adopt a more
natural setting than (Shiv and Quirk, 2019) by using two different embeddings
for a node’s absolute and relative level to denote positions.

Figure 2. Illustration of the HEF model. Each circle denotes a seed node or a
query node. The “Anchor’s child*” in Fitting Score calculation denotes the
anchor’s child with maximum Pathfinder Score $S_{p}$.

##  3\. Problem Definition

In this section, we provide the formal definition of the taxonomy expansion
task and the explanation of key concepts that will occur in the following
sections.

Definition and Concepts about Taxonomy. A taxonomy
$\mathcal{T}=(\mathcal{N},\mathcal{E})$ is an arborescence that presents
hypernymy relations among a set of nodes. Each node $n\in\mathcal{N}$
represents a term, usually a concept mined from a large corpus online or an
artificially extracted phrase. Each edge
$\left<n_{p},n_{c}\right>\in\mathcal{E}$ points to a node from its most exact
hypernym node, where $n_{p}$ is $n_{c}$’s parent node, and $n_{c}$ is
$n_{p}$’s child node. Since hypernymy relation is transitive (Sang, 2007),
such relation exists not only in node pairs connected by a single edge, but
also in node pairs connected by a path in the taxonomy. Thus, for a node $n$
in the taxonomy, its hypernym set and hyponym set consists of its ancestors
$\mathcal{A}_{n}$, and its descendants $\mathcal{D}_{n}$ respectively.

Definition of the Taxonomy Expansion Task. Given a seed taxonomy
$\mathcal{T}^{0}=(\mathcal{N}^{0},\mathcal{E}^{0})$ and the set of terms
$\mathcal{C}$ to be added to the seed taxonomy, The model outputs the taxonomy
$\mathcal{T}=(\mathcal{N}^{0}\cup\mathcal{C},\mathcal{E}^{0}\cup\mathcal{R})$,
where $\mathcal{R}$ is the newly added relations from seed nodes in
$\mathcal{N}^{0}$ to new terms in $\mathcal{C}$. More specifically, during the
inference phase of a taxonomy expansion model, when given a query node
$q\in\mathcal{C}$, the model finds its best-suited parent node by iterating
each node in the seed taxonomy as an anchor node $a\in\mathcal{N}^{0}$,
calculating a score $f(a,q)$ representing the suitability for adding the edge
$\left<a,q\right>$, and deciding $q$’s parent $p_{q}$ in the taxonomy by
$p_{q}=\mathop{\arg\max}_{a\in\mathcal{N}^{0}}{f(a,q)}$.

Accessible External Resources. As a term’s surface name is usually
insufficient to convey the semantic information for hypernymy relationship
detection, previous research usually utilizes term definitions (Jurgens and
Pilehvar, 2016; Shen et al., 2020) or related web pages (Wang et al., 2014;
Kozareva and Hovy, 2010) to learn term representations. Besides, existing
hypernymy detection solutions usually use large external corpora to discover
lexical or syntactic patterns (Shwartz et al., 2016; Yu et al., 2020). As for
the SemEval-2016 Task 13 datasets (Bordea et al., 2016) used for our model’s
evaluation, utilizing the WordNet (Miller, 1995) definitions is allowed by the
original task, which guarantees a fair comparison with previous solutions.

##  4\. The Hierarchy Expansion Framework

In this section, we introduce the design of the Hierarchy Expansion Framework
(HEF). An illustration of HEF is shown in Fig. 2. We first introduce the way
HEF models the coherence of a tree structure, including two components for
node pair hypernymy detection and ego-tree coherence modeling, respectively.
Then, we discuss how HEF further exploits the hierarchical structure for
multi-dimensional evaluation by the modules of Pathfinder and Stopper, and the
self-supervised paradigm to train the model for the Fitting Score calculation.

###  4.1. Node Pair Hypernymy Detection

We first introduce the hypernymy detection module of HEF, which detects the
hypernymy relationships between two terms. Unlike previous approaches that
manually design a set of classical lexical-syntactic features, we accomplish
the task more directly and automatically by expanding the surface names of
terms to their descriptions and utilizing pre-trained language models to
represent the relationship between two terms.

Given a seed term $n\in\mathcal{N}^{0}$ and a query term $q\in\mathcal{N}^{0}$
during training or $q\in\mathcal{C}$ during inference, the hypernymy detection
module outputs a representation $r_{n,q}$ suggesting how well these two terms
form a hypernymy relation. Note that $n$ might not be identical to the anchor
$a$. Since the surface names of terms do not contain sufficient information
for relation detection, we expand the surface names to their descriptions,
enabling the model to better understand the semantic of new terms. We utilize
the WordNet (Miller, 1995) concept definitions for completing this task.
However, WordNet cannot explain all terms in a taxonomy due to its low
coverage. Besides, many terms used in taxonomies are complex phrases like
“adaptation to climate change” or “bacon lettuce tomato sandwich”. Therefore,
we further develop a description generation algorithm descr($\cdot$), which
generates meaningful and domain-related descriptions for a given term based on
WordNet. Specifically, descr($\cdot$) is a dynamic programming algorithm that
tends to integrate tokens into longer and explainable noun phrases. It
describes each noun phrase by the most relative description to the taxonomy’s
root’s surface name for domain relevance. The details are shown in Alg. 2 in
the appendix. The input for hypernymy detection is organized as the input
format of a Transformer:

$D_{n,q}=\left[\mbox{<CLS>}\oplus\texttt{descr(}n\texttt{)}\oplus\mbox{<SEP>}\oplus\texttt{descr(}q\texttt{)}\oplus\mbox{<SEP>}\right],$

where $\oplus$ represents concatenation, ¡CLS¿ and ¡SEP¿ are the special token
for classification and sentence separation in the Transformer architecture,
respectively.

As shown in Fig. 2, the hypernymy detection module utilizes a pre-trained
DistilBERT (Sanh et al., 2020), a lightweight variant of BERT (Devlin et al.,
2019), to learn the representations of cross-text relationships. Specifically,
we first encode $D_{n,q}$ by ${\rm DistilBERT}(\cdot)$ with positional
encoding. Then we take the final layer representation of ¡CLS¿ as the
representation of the node pair $\left<n,q\right>$:

$r_{n,q}={\rm DistilBERT}\left(D_{n,q}\right)\left[0\right],$

where index $0$ represents the position of ¡CLS¿’s embedding.

###  4.2. Ego-Tree Coherence Modeling

We further design a coherence modeling module to evaluate the coherence of the
tree structure after attaching the query term $q$ into taxonomy $\mathcal{T}$
as the anchor $a\in\mathcal{N}^{0}$’s child.

There are two different aspects for considering a taxonomy’s coherence: i) the
natural hypernymy relations. Since a node’s ancestors in the taxonomy all hold
hypernymy relations with it, an explicit comparison among a node’s ancestors
is needed to distinguish the most appropriate one; ii) the expert-curated
designs, which act as supplement information for maintaining the overall
structure. Some taxonomies contain latent rules about a node’s absolute or
relative levels in a taxonomy. For example, in the biological taxonomy,
kingdoms and species are all placed in the second and eighth levels,
respectively; in some e-commerce catalog taxonomies, terms that are one level
higher than another term contain exactly one more adjective. Hence, the
coherence modeling module needs to: i) model a subtree with the query as a
node in it, rather than a single node pair, enabling the model to learn the
design of a complete hierarchy; ii) add tree-exclusive features like absolute
level or relative level compared to the anchor to assist learning the expert-
curated designs of the taxonomy.

We design the Ego-tree $\mathcal{H}_{a}$, a novel contextual structure of an
anchor $a$, which consists of all the ancestors and children of $a$ (see Fig.
2). This structure contains all relevant nodes to both anchor and query,
enabling the model to both compare all hypernymy relations along the root path
and detect similarity among query and its potential siblings with minimal
computation cost:

(1) $\mathcal{H}_{a}=\mathcal{A}_{a}\cup\left\\{a\right\\}\cup{\rm
sample\\_child}\left(a\right),$

where $\mathcal{A}_{a}$ is all ancestors of $a$ in the seed taxonomy
$\mathcal{T}^{0}$, and sample_child$(\cdot)$ means sampling at most three
children of the anchor based on surface name similarity. The 3-children
sampling is a trade-off between accuracy and speed, for three potential
siblings are empirically enough for a comprehensive similarity comparison with
the query (especially when these potential siblings are quite different) while
decreasing the computation cost. Since this procedure is to leverage the
similarity brought by a hierarchy’s sibling relations, sampling by surface
name similarity is intuitive and cost-saving given that similar surface names
usually indicate similar terms. The input of the coherence modeling module
includes the anchor’s ego-tree $\mathcal{H}_{a}$ and the query $q$ as the
anchor’s child in $\mathcal{H}_{a}$. For each node $n\in\mathcal{H}_{a}$, we
represent the node pair $\left<n,q\right>$ by the following representations:

  * •

Ego-tree representations. The ego-tree representation $r_{n,q}$ is the output
of the hypernymy detection module described in Sec. 4.1. It suggests the node
pair’s relation.

  * •

Absolute level embedding. The absolute level embedding
$l_{n,q}=\mbox{AbsLvlEmb}\left(d_{n}\right)$, where $d_{n}$ is the depth of
$n$ in the expanded taxonomy. When $n=q$,
$l_{q,q}=\mbox{AbsLvlEmb}\left(d_{a}+1\right)$. It assists the modeling of the
expert-curated designs about granularity of a certain level.

  * •

Relative level embedding. The relative level embedding
$e_{n,q}=\mbox{RelLvlEmb}\left(d_{n}-d_{q}\right)$, where $d_{n}$ is the depth
of $n$ in the expanded taxonomy. It assists the modeling of expert-curated
designs about the cross-level comparison.

  * •

Segment embedding. The segment embedding of $\left<n,q\right>$
$g_{n,q}=\mbox{SegEmb}\left(\mbox{segment}\left(n\right)\right)$ distinguishes
anchor and query with other nodes in the ego-tree, where:

$\mbox{segment}\left(n,q\right)=\begin{cases}0,&\mbox{if }n\mbox{ is the
anchor},\\\ 1,&\mbox{if }n\mbox{ is the query},\\\
2,&\mbox{otherwise}.\end{cases}$

The input of the coherence modeling module
$R_{a,q}\in\mathbb{R}^{\left(\mathopen{|}\mathcal{H}_{a}\mathclose{|}+3\right)\times
d}$ is the sum of the above embeddings calculated with the anchor’s ego-tree
and the query, organized as the input of a Transformer:

(2) $R_{a,q}=\left[e_{<CLS>}\oplus
e_{<CLS>}\bigoplus_{n\in\mathcal{H}_{a}\cup{\left\\{q\right\\}}}{\left(r_{n,q}+l_{n,q}+e_{n,q}+g_{n,q}\right)}\right],$

where $d$ is the dimension of embedding, $e_{<CLS>}$ is a randomly initialized
placeholder vector for obtaining the ego-tree’s path and level coherence
representations, and $\oplus$ denotes concatenation.

We implement the coherence modeling module using a Transformer encoder.
Transformers are powerful to model sequences, but they lack positional
information to process the relations among nodes in graphs. However, in a
hierarchy like taxonomy, the level of nodes can be used as positional
information, which simultaneously eliminates the positional difference of
nodes on the same level. Transformers are also strong enough to integrate
multiple-source information by adding their embeddings, thus they are quite
suitable for modeling tree structures. In our HEF model, as shown in Fig. 2,
by using two ¡CLS¿s in the module’s input, we can obtain two different
representations: $p_{a,q}$ representing the coherence of hypernymy relations
(whether the path is correct), and $d_{a,q}$ representing the coherence of
inter-level granularity (whether the level is correct), evaluating how well
the query fits the current position in the taxonomy in both horizontal and
vertical perspective:

$\displaystyle p_{a,q}$
$\displaystyle=\mbox{TransformerEncoder}\left(R_{a,q}\right)\left[0\right]$
$\displaystyle d_{a,q}$
$\displaystyle=\mbox{TransformerEncoder}\left(R_{a,q}\right)\left[1\right],$

where $0$ and $1$ are the position indexes of the two ¡CLS¿s.

###  4.3. Fitting Score-based Training and Inference

Figure 3. An illustration of the self-supervision data labels for Pathfinder
and Stopper.

The two representations $p_{a,q}$ and $d_{a,q}$ need to be transformed into
scores indicating the fitness of placing the query $q$ on a particular path
and a particular level. Thus, we propose the Pathfinder for path selection and
the Stopper for level selection, as well as a new self-supervised learning
algorithm for training and the Fitting Score calculation for inference.

Pathfinder. The Pathfinder detects whether the query is positioned on the
right path. This module performs a binary classification using $p_{a,q}$. The
Pathfinder Score $S_{p}=1$ if and only if $a$ and $q$ are on the same root-
path:

(3)
$S_{p}\left(a,q\right)=\sigma\left(\mathbf{W}_{p2}\tanh\left(\mathbf{W}_{p1}p_{a,q}+b_{p1}\right)+b_{p2}\right),$

where $\sigma$ is the sigmoid function, and
$\mathbf{W}_{p1},\mathbf{W}_{p2},b_{p1},b_{p2}$ are trainable parameters for
multi-layer perceptrons.

Stopper. The Stopper detects whether the query $q$ is placed on the right
level, i.e., under the most appropriate anchor $a$ on a particular path.
Selecting the right level is nonidentical to selecting the right path since
levels are kept in order. The order of nodes on a path enables us to design a
more representative module for further classifying whether the current level
is too high (anchor $a$ is a coarse-grained ancestor of $q$) or too low ($a$
is a descendant of $q$). Thus, the Stopper module uses $d_{a,q}$ to perform a
$3$-class classification: searching for a better anchor node needs to go
Forward, remain Current, or go Backward, in the taxonomy:

$\displaystyle[S_{f}\left(a,q\right),S_{c}\left(a,q\right),S_{b}\left(a,q\right)]=$
(4)
$\displaystyle\mbox{softmax}\left(\mathbf{W}_{s2}\tanh\left(\mathbf{W}_{s1}d_{a,q}+b_{s1}\right)+b_{s2}\right),$

where $\mathbf{W}_{p1},\mathbf{W}_{p2},b_{p1},b_{p2}$ are trainable parameters
for multi-layer perceptrons. Forward Score $S_{f}$, Current Score $S_{c}$ and
Backward Score $S_{b}$ are called Stopper Scores.

Self-Supervised Training. Training the HEF model needs data labels for both
the Pathfinder and the Stopper. The tagging scheme is illustrated in Fig. 3.
There are totally four kinds of Pathfinder-Stopper label combinations since
Pathfinder Score is always $1$ when Stopper Tag is Forward or Current. The
training process of HEF is shown in Alg. 1. Specifically, we sample the ego-
tree of all four types of nodes for a query: $q$’s parent $a$, $a$’s
ancestors, $a$’s descendants and other nodes, as a mini-batch for training the
Pathfinder and Stopper simultaneously.

The optimization of Pathfinder and Stopper can be regarded as a multi-task
learning process. The loss $\mathcal{L}_{q}$ in Alg. 1 is a linear combination
of the loss from Pathfinder and Stopper:

$\displaystyle\mathcal{L}_{q}=$
$\displaystyle-\eta\frac{1}{\mathopen{|}\mathcal{X}_{q}\mathclose{|}}\sum_{a\in\mathcal{X}_{q}}{{\rm
BCELoss}\left(\hat{S_{p}}\left(a,q\right),S_{p}\left(a,q\right)\right)}$ (5)
$\displaystyle-\left(1-\eta\right)\frac{1}{\mathopen{|}\mathcal{X}_{q}\mathclose{|}}\sum_{a\in\mathcal{X}_{q}}{\sum_{k\in\left\\{f,c,b\right\\}}{\hat{s_{k}}\left(a,q\right)\log
s_{k}\left(a,q\right)}},$

where ${\rm BCELoss}\left(\cdot\right)$ denotes the binary cross entropy, and
$\eta$ is the weight of multi-task learning.

Algorithm 1 Self-Supervised Training Process of HEF.

1:procedure TrainEpoch($\mathcal{T}^{0},{\Theta^{0}}$)

2: $\Theta\leftarrow\Theta^{0}$

3: for $q\leftarrow\mathcal{N}^{0}-{\rm root}\left(\mathcal{T}^{0}\right)$ do
$\triangleright$ Root is not used as query

4: $\mathcal{X}_{q}=\\{\\}$ $\triangleright$ Initialize anchor set

5: $p\leftarrow{\rm parent}\left(q\right)$ $\triangleright$ Reference node of
labeling

6: $\mathcal{X}_{q}\leftarrow\mathcal{X}_{q}\cup\left\\{p\right\\}$
$\triangleright$ Ground Truth Parent: $S_{p}=1,S_{c}=1$

7: $\mathcal{X}_{q}\leftarrow\mathcal{X}_{q}\cup{\rm
sample}\left(\mathcal{A}_{p}\right)$ $\triangleright$ Ancestors:
$S_{p}=1,S_{f}=1$

8: $\mathcal{X}_{q}\leftarrow\mathcal{X}_{q}\cup{\rm
sample}\left(\mathcal{D}_{p}\right)$ $\triangleright$ Descendants:
$S_{p}=1,S_{b}=1$

9: $\mathcal{X}_{q}\leftarrow\mathcal{X}_{q}\cup{\rm
sample}\left(\mathcal{N}^{0}-\left\\{p\right\\}-\mathcal{A}_{p}-\mathcal{D}_{p}\right)$

10:$\triangleright$ Other nodes: $S_{p}=0,S_{b}=1$

11: for $a\leftarrow\mathcal{X}_{q}$ do

12: Compute $S_{p}\left(a,q\right)$ using Eqn. 3

13: Compute
$S_{f}\left(a,q\right),S_{c}\left(a,q\right),S_{b}\left(a,q\right)$ using Eqn.
4.3

14: end for

15: Compute $\mathcal{L}_{q}$ with $S_{p},S_{f},S_{c},S_{b}$ using Eqn. 5

16: $\Theta\leftarrow{\rm optimize}\left(\Theta,\mathcal{L}_{q}\right)$

17: end for

18: return $\Theta$

19:end procedure

Fitting Score-based Inference. During inference, evaluation of an anchor-query
pair $\left<a,q\right>$ should consider both Pathfinder’s path evaluation and
Stopper’s level evaluation. However, instead of merely using $S_{p}$ and
$S_{c}$, the multi-classifying Stopper also enables the HEF model to
disambiguate the most suited anchor from its neighbors (its direct parent and
children) and self-correct its level prediction by exchanging scores with its
neighbors to find the best position for maintaining the taxonomy’s coherence.
Thus, We introduce the Fitting Score function during inference. For a new
query term $q\in\mathcal{C}$, we first obtain the Pathfinder Scores and
Stopper Scores of all node pairs $\left<a,q\right>,a\in\mathcal{N}^{0}$. For
each anchor node $a$, we assign its Fitting Score by multiplying the following
four items:

  * •

$a$’s Pathfinder Score: $S_{p}\left(a,q\right)$, which suggests whether $a$ is
on the right path.

  * •

$a$’s parent’s Forward Score: $S_{f}\left({\rm
parent}\left(a\right),q\right)$, which distinguishes $a$ and $a$’s parent, and
rectifies $a$’s Current Score. When $a$ is the root node, we assign this item
as a small number like $1e-4$ since the first level of taxonomy is likely to
remain unchanged.

  * •

$a$’s Current Score: $S_{c}\left(a,q\right)$, which suggests whether $a$ is on
the right level.

  * •

$a$’s child with maximum Pathfinder Score’s Backward Score:
$S_{b}\left(c_{a}^{*},q\right),c_{a}^{*}=\mathop{\arg\max}_{c_{a}\in{\rm
child}\left(a\right)}{S_{p}\left(c_{a},q\right)}$, which distinguishes $a$ and
$a$’s children, and rectifies $a$’s Current Score. Since $a$ might have
multiple children, we pick the child with max Pathfinder Score, for larger
$S_{p}$ indicates a better hypernymy relation to $q$. When $a$ is a leaf node,
we assign this item as the proportion of leaf nodes in the seed taxonomy to
keep its overall design.

The Fitting Score of $\left<a,q\right>$ is given by:

(6) $F\left(a,q\right)=S_{p}\left(a,q\right)\cdot S_{f}\left({\rm
parent}\left(a\right),q\right)\cdot S_{c}\left(a,q\right)\cdot
S_{b}\left(c_{a}^{*},q\right)$ $c_{a}^{*}=\mathop{\arg\max}_{c_{a}\in{\rm
child}\left(a\right)}{S_{p}\left(c_{a},q\right)}.$

The Fitting Score can be computed using ordered $S_{p},S_{f},S_{c},S_{b}$
arrays and the seed taxonomy’s adjacency matrix. Since a tree’s adjacency
matrix is sparse, the time complexity of Fitting Score computation is low.
After calculating the Fitting Scores between all seed nodes and the query, we
select the seed node with the highest Fitting Score as the query’s parent in
the expanded taxonomy:

(7) ${\rm
parent}\left(q\right)\coloneqq\mathop{\arg\max}_{a\in\mathcal{N}^{0}}F\left(a,q\right).$

##  5\. Experiments

In this section, we first introduce our experimental setups, including
datasets, our implementation details, evaluation criteria, and a brief
description of the compared baseline methods. Then, we provide extensive
evaluation results for overall model performance, performance contribution
brought by each design, and sensitivity analysis of the multi-task learning
weight $\eta$ in Equation 5. In-depth visualizations of hypernymy detection
and coherence modeling modules are provided to analyze the model’s inner
behavior. We also provide a case study in the appendix.111The code will be
available at https://github.com/sheryc/HEF.

###  5.1. Experimental Setup

####  5.1.1. Datasets

We evaluate HEF on three public benchmark datasets retrieved from SemEval-2016
Task 13 (Bordea et al., 2016). This task contains three taxonomies in the
domain of Environment (SemEval16-Env), Science (SemEval16-Sci), and Food
(SemEval16-Food), respectively. The statistics of the benchmark datasets are
provided in Table 1. Note that the original dataset may not form a tree. In
this case, we use a spanning tree of the taxonomy instead of the original
graph to match the problem definition. The pruning process only removes less
than 6% of the total edges, keeping the taxonomy’s information and avoiding
multiple ground truth parents for a single node.

Since HEF and the compared baselines (Shen et al., 2020; Yu et al., 2020) are
all limited to adding new terms without modifying the seed taxonomy, nodes in
the test and validation set can only sample from leaf nodes to guarantee that
the parents of test or validation nodes exist in the seed taxonomy. This is
also the sampling strategy of TaxoExpan (Shen et al., 2020). Following the
previous state-of-the-art model STEAM (Yu et al., 2020), we exclude 20% of the
nodes in each dataset, of which ten nodes of each dataset are separated as the
validation set for early stopping, and the rest as the test set. The nodes not
included in the validation set and test set are seed nodes for self-
supervision in the training phase and potential anchor nodes in the inference
phase. Note that pruning the dataset does not affect the node count, thus the
scale of the dataset remains identical to our baselines’ settings.

Table 1. Statistics of datasets. $\left|N\right|$ and $\left|E_{O}\right|$ are the numbers of nodes and edges in the original datasets, respectively. $D$ is the depth of the taxonomy. We adopt the spanning tree of each dataset, and $\left|E\right|$ is the number of remaining edges. Dataset | $\left|N\right|$ | $\left|E_{O}\right|$ | $\left|E\right|$ | $D$
---|---|---|---|---
SemEval16-Env | 261 | 261 | 260 | 6
SemEval16-Sci | 429 | 452 | 428 | 8
SemEval16-Food | 1486 | 1576 | 1485 | 8
Table 2. Comparison of the proposed method against state-of-the-art methods. All metrics are presented in percentages (%). Best results for each metric of each dataset are marked in bold. Reported performance is the average of three runs using different random seeds. The MRR of TAXI (Panchenko et al., 2016) is inaccessible since it outputs the whole taxonomy instead of node rankings. The performance of baseline methods are retrieved from (Yu et al., 2020). Dataset | SemEval16-Env | SemEval16-Sci | SemEval16-Food
---|---|---|---
Metric | Acc | MRR | Wu&P | Acc | MRR | Wu&P | Acc | MRR | Wu&P
BERT+MLP | 11.1 | 21.5 | 47.9 | 11.5 | 15.7 | 43.6 | 10.5 | 14.9 | 47.0
TAXI (Panchenko et al., 2016) | 16.7 | - | 44.7 | 13.0 | - | 32.9 | 18.2 | - | 39.2
HypeNet (Shwartz et al., 2016) | 16.7 | 23.7 | 55.8 | 15.4 | 22.6 | 50.7 | 20.5 | 27.3 | 63.2
TaxoExpan (Shen et al., 2020) | 11.1 | 32.3 | 54.8 | 27.8 | 44.8 | 57.6 | 27.6 | 40.5 | 54.2
STEAM (Yu et al., 2020) | 36.1 | 46.9 | 69.6 | 36.5 | 48.3 | 68.2 | 34.2 | 43.4 | 67.0
HEF | 55.3 | 65.3 | 71.4 | 53.6 | 62.7 | 75.6 | 47.9 | 55.5 | 73.5

####  5.1.2. Baselines for Comparison

We compare our proposed HEF model with the following baseline approaches:

  * •

BERT+MLP: This method utilizes BERT (Devlin et al., 2019) to perform hypernym
detection. This model’s input is the term’s surface name, and the
representation of BERT’s classification token $\langle$CLS$\rangle$ is fed
into a feed-forward layer to score whether the first sequence is the ground-
truth parent.

  * •

HypeNet (Shwartz et al., 2016): HypeNet is an LSTM-based hypernym extraction
model that scores a term pair by representing node paths in the dependency
tree.

  * •

TAXI (Panchenko et al., 2016): TAXI was the top solution of SemEval-2016 Task
13. It explicitly splits the task into a pipeline of hypernym detection using
substring matching and pattern extraction, and hypernym pruning to avoid
multiple parents.

  * •

TaxoExpan (Shen et al., 2020): TaxoExpan is a self-supervised taxonomy
expansion model. The anchor’s representation is modeled by a graph network of
its Egonet with consideration of relative levels, and the parental
relationship is scored by a feed-forward layer. BERT embedding is used as its
input instead of the model’s original configuration.

  * •

STEAM (Yu et al., 2020): STEAM is the state-of-the-art self-supervised
taxonomy expansion model, which scores parental relations by ensembling three
classifiers considering graph, contextual, and hand-crafted lexical-syntactic
features, respectively.

####  5.1.3. Implementation Details

In our setting, the coherence modeling module is a 3-layer, 6-head,
768-dimensional Transformer encoder initialized from Gaussian distribution
$\mathcal{N}\left(0,0.02\right)$. The first hidden layers of Pathfinder and
Stopper are both 300-dimensional. The input to the hypernymy detection module
is either truncated or padded to a length of 64. Each training step contains a
set of 32 query-ego-tree pairs of 32 query nodes using gradient accumulation,
with each query-ego-tree pair set containing one ground-truth parent
($S_{p}=1$, $S_{c}=1$), at most 6 ground-truth parent’s ancestors ($S_{p}=1$,
$S_{f}=1$), at most 8 ground-truth parent’s descendants ($S_{p}=1$,
$S_{b}=1$), and at least 16 other nodes ($S_{p}=0$, $S_{b}=1$). The
hyperparameters above are empirically set, since our algorithm is not
sensitive to the setting of splits. Each dataset is trained for 150 epochs. In
a single epoch, each seed node is trained as the query exactly once. AdamW
(Loshchilov and Hutter, 2019) is used for optimization with $\epsilon$ set to
$1\times 10^{-6}$. A linear warm-up is adopted with the learning rate linearly
rise from 0 to 5e-5 in the first 10% of total training steps and linearly drop
to 0 at the end of 150 epochs. The multi-task learning weight $\eta$ is set to
0.9. After each epoch, we validate the model and save the model with the best
performance on the validation set. These hyperparameters are tuned on on
SemEval16-Env’s validation set, and are used across all datasets and
experiments unless specified in the ablation studies or sensitivity analysis.

####  5.1.4. Evaluation Metrics

Assume $k\coloneqq\mathopen{|}\mathcal{C}\mathclose{|}$ to be the term count
of the test set, $\left\\{p_{1},p_{2},\cdots,p_{k}\right\\}$ to be the
predicted parents for test set queries, and
$\left\\{\hat{p_{1}},\hat{p_{2}},\cdots,\hat{p_{k}}\right\\}$ to be the ground
truth parents accordingly. Following the previous solutions (Manzoor et al.,
2020; Vedula et al., 2018; Yu et al., 2020), we adopt the following three
metrics as evaluation criteria.

  * •

Accuracy (Acc): It measures the proportion that the predicted parent for each
node in the test set exactly matches the ground truth parent:

$\mbox{Acc}=\mbox{Hit@1}=\frac{1}{k}\sum_{i=1}^{k}{\mathbb{I}\left(p_{i}=\hat{p_{i}}\right)},$

where $\mathbb{I}(\cdot)$ denotes the indicator function,

  * •

Mean Reciprocal Rank (MRR): It calculates the average reciprocal rank of each
test node’s ground truth parent:

$\mbox{MRR}=\frac{1}{k}\sum_{i=1}^{k}{\frac{1}{\mbox{rank}\left(\hat{p_{i}}\right)}},$

  * •

Wu & Palmer Similarity (Wu&P) (Wu and Palmer, 1994): It is a tree-based
measurement that judges how close the predicted and ground truth parents are
in the seed taxonomy:

$\mbox{Wu\&P}=\frac{1}{k}\sum_{i=1}^{k}{\frac{2\times\mbox{depth}\left(\mbox{LCA}\left(p_{i},\hat{p_{i}}\right)\right)}{\mbox{depth}\left(p_{i}\right)+\mbox{depth}\left(\hat{p_{i}}\right)}},$

where $\mbox{depth}(\cdot)$ is the node’s depth in the seed taxonomy and
$\mbox{LCA}(\cdot,\cdot)$ is the least common ancestor of two nodes.

###  5.2. Main Results

The performance of HEF is shown in Table 2. HEF achieves the best performance
on all datasets and surpasses previous state-of-the-art models with a
significant improvement on all metrics.

From the table, we get an overview of how taxonomy expansion models evolve
chronologically. The solution of BERT+MLP does not utilize any structural and
lexical-syntactic features of terms, and the insufficiency of information
attributes to its poor results. Models of the first generation like TAXI and
HypeNet utilize lexical, syntactic, or contextual information to achieve
better results, mainly for the task’s hypernymy detection part. However, these
two models do not utilize any of the structural information of taxonomy; hence
they are unable to maintain the taxonomy’s structural design. Models of the
second generation, like TaxoExpan and STEAM, inherit handcrafted lexical-
syntactic features for detecting hypernymy relations. They also utilize the
structural information by self-supervision from seed taxonomy and graph neural
networks on small subgraphs of the taxonomy. However, they neglect the
hierarchical structure of taxonomies, and they do not consider the coherence
of the whole expanded taxonomy. Thus, their usage of structural information is
only an improvement for performing hypernymy detection rather than taxonomy
expansion.

HEF further improves both the previous two generations’ strength by proposing
a new approach that better fits the taxonomy expansion task. Moreover, it
introduces a new goal for the task: to best preserve the taxonomy’s coherence
after expansion. We propose the description generation algorithm to generate
accurate and domain-specific descriptions for complex and rare terms, to
incorporate lexical-syntactic features for hypernymy detection. Aided by
DistilBERT’s power of sentence-pair representation, HEF can mine hypernymy
features more automatically and accurately. HEF also aims to fully exploit the
information brought by the taxonomy’s hierarchical structure to boost
performance. HEF uses ego-trees to perform thorough comparison along root path
and among siblings, injects tree-exclusive features to assist modeling the
expert-curated taxonomy designs and explicitly evaluates both path and level
for the anchor node as well as its parent and child. Experiment results
suggest that these designs are capable of modeling and maximizing the
coherence of taxonomy in different aspects, which results in a vast
performance increase in the taxonomy expansion task.

|  |
---|---|---
(a) Accuracy on all 3 datasets. |  (b) MRR on all 3 datasets. |  (c) Wu&P on all 3 datasets.
Figure 4. Sensitivity analysis of model performance under different multi-task
learning weight $\eta$.

###  5.3. Ablation Studies

Table 3. Ablation experiment results on the SemEval16-Env dataset. All metrics are presented in percentages (%). For each ablation experiment setting, only the best result is reported. Abl. Type | Setting | Acc | MRR | Wu&P
---|---|---|---|---
Original |  HEF | 55.3 | 65.3 | 71.4
Dataflows |  \- WordNet Descriptions | 41.5 | 55.3 | 62.6
\- Ego-tree + Egonet | 45.3 | 60.6 | 69.9
\- Relative Level Emb. | 49.1 | 59.2 | 60.9
\- Absolute Level Emb. | 49.1 | 60.6 | 68.4
Scoring Function |  Stopper Only | 52.8 | 62.5 | 68.7
Pathfinder + Current Only | 50.9 | 62.1 | 66.8
Current Only | 41.5 | 54.7 | 58.6

We discuss how exploiting different characteristics of taxonomy’s hierarchical
structure brings performance increase by a series of ablation studies. We
substitute some designs of HEF in dataflow and score function to a vanilla
setting and rerun the experiments. The results of the ablation studies are
shown in Table 3.

  * •

\- WordNet Descriptions: WordNet descriptions are substituted with the term’s
surface name as the hypernymy detection module’s input.

  * •

\- Ego-tree + Egonet: the Egonet from TaxoExpan (Shen et al., 2020) is used
instead of the ego-tree for modeling the tree structure.

  * •

\- Relative Level Emb.: The relative level embedding for the coherence
modeling module is removed.

  * •

\- Absolute Level Emb.: The absolute level embedding for the coherence
modeling module is removed.

  * •

Stopper Only: Only the Stopper Scores are used for Fitting Score calculation.
More specifically, $\eta=0$, and the Fitting Score in Equation 6 becomes:

$F\left(a,q\right)=S_{f}\left({\rm parent}\left(a\right),q\right)\cdot
S_{c}\left(a,q\right)\cdot S_{b}\left(c_{a}^{*},q\right),$
$c_{a}^{*}=\mathop{\arg\max}_{c_{a}\in{\rm
child}\left(a\right)}{S_{p}\left(c_{a},q\right)}.$

  * •

Pathfinder + Current Only: Only the Pathfinder Score and the Current Score are
used for Fitting Score calculation. More specifically, the Fitting Score in
Equation 6 and the loss in Equation 5 become:

$F\left(a,q\right)=S_{p}\left(a,q\right)\cdot S_{c}\left(a,q\right),$
$\displaystyle\mathcal{L}_{q}=$
$\displaystyle-\eta\frac{1}{\mathopen{|}\mathcal{X}_{q}\mathclose{|}}\sum_{a\in\mathcal{X}_{q}}{{\rm
BCELoss}\left(\hat{S_{p}}\left(a,q\right),S_{p}\left(a,q\right)\right)}$
$\displaystyle-\left(1-\eta\right)\frac{1}{\mathopen{|}\mathcal{X}_{q}\mathclose{|}}\sum_{a\in\mathcal{X}_{q}}{{\rm
BCELoss}\left(\hat{S_{c}}\left(a,q\right),S_{c}\left(a,q\right)\right)}.$

  * •

Current Only: Only the Current Score is used for Fitting Score calculation.
This is the scoring strategy identical to prior arts (Shen et al., 2020; Yu et
al., 2020). More specifically, the Fitting Score in Equation 6 and the loss in
Equation 5 become:

$F\left(a,q\right)=S_{c}\left(a,q\right),$
$\mathcal{L}_{q}=-\frac{1}{\mathopen{|}\mathcal{X}_{q}\mathclose{|}}\sum_{a\in\mathcal{X}_{q}}{{\rm
BCELoss}\left(\hat{S_{c}}\left(a,q\right),S_{c}\left(a,q\right)\right)}.$

We notice that by changing the design of dataflows, the performance of the HEF
model suffers from various deteriorations. Substituting WordNet descriptions
with a term’s surface name surprisingly remains a relatively high performance,
which might attribute to the representation power of the DistilBERT model.
Using Egonets rather than ego-trees for coherence modeling also affects the
performance. Although egonets can capture the local structure of taxonomy,
ego-trees are more capable of modeling the complete construction of a
hierarchy. For the introduction of level embeddings, the results show that
removing one of the two level embeddings for the coherence modeling module
hurts the learning of taxonomy’s design. This is in accordance with the
previous research about the importance of using the information of both
absolute and relative positions in Transformers (Shaw et al., 2018) and
confirms our assumption that taxonomies have intrinsic designs about both
absolute and relative levels.

Changes to the score function bring a smaller negative impact on the model
compared to the dataflow changes, except for the setting of using merely
Current Score. When using only the Current Score, the model loses the ability
to disambiguate with its neighbors and the capacity of directly choosing the
right path, downgrading the problem to be a series of independent scoring
problems like the previous solutions. Adding Backward Score and Forward Score
into Fitting Score calculation allows the model to distinguish the ground
truth from its neighbors, bringing a boost to accuracy. However, without the
Pathfinder, the “Stopper Only” setting only explicitly focuses on choosing the
right level without considering the path and is inferior to the original HEF
model.

However, we observe that although changing several designs of dataflow or
scoring function deteriorates the performance, our method can still surpass
the previous state-of-the-art in Acc and MRR, suggesting that the HEF model
introduces improvements in multiple aspects, which also testifies that
maximizing the taxonomy’s coherence is a better goal for the taxonomy
expansion task.

Figure 5. Illustration of one self-attention head in the last layer of the
hypernymy detection module, showing how the hypernymy detection module detects
hypernymy relations. In this example, the seed node is “tea”, and the query is
“oolong”.

###  5.4. Impact of Multi-Task Learning Weight $\eta$

In this section, we discuss the impact of $\eta$ in Equation 5 through a
sensitivity analysis. Since $\eta$ controls the proportion of loss from the
path-oriented Pathfinder and the level-oriented Stopper, this hyperparameter
affects HEF’s tendency to prioritize path or level selection. The results on
all three datasets are shown in Fig. 4.

From the result, we notice that $\eta$ cannot be set too low, which means that
explicit path selection contributes a lot to the model’s performance. This is
in accordance with the fact that taxonomies are based on hypernymy relations
and selecting the right path is the essential guidance for anchor selection. A
better setting of $\eta$ is $\left[0.4,0.6\right]$. In this setting, the model
tends to balance path and level selections, which results in better
performance. Surprisingly, setting $\eta$ to a high value like 0.9 also brings
a performance boost, and sometimes even achieves the best result. This
phenomenon consistently exists when changing random seeds. However, setting
$\eta$ to 1 means using merely Pathfinder, which cannot distinguish the ground
truth from other nodes and breaks the model. This discovery further testifies
the importance of explicitly evaluating path selection in the taxonomy
expansion task.

###  5.5. Visualization of Self-Attentions

####  5.5.1. Node Pair Hypernymy Detection Module

To illustrate how the hypernymy detection module works, we show the weights of
one of the attention heads of the hypernymy detection module’s last
Transformer encoder layer in Fig. 5.

By expanding a term to its description, the model is capable of understanding
the term “oolong” by its description, which cannot be achieved by constructing
rule-based lexical-syntactic features since “oolong” and “tea” have no
similarity in their surface names. Furthermore, by adopting the pretrained
DistilBERT, the hypernymy detection module can also discover more latent
patterns such as the relation between “leaves” and “tree”, allowing the model
to discover more in-depth hypernymy relations.

####  5.5.2. Ego-Tree Coherence Modeling Module

Figure 6. Illustration of one self-attention head in the first layer of the
coherence modeling module, showing how the coherence modeling module finds the
most fitted node in an ego-tree. In this example, the anchor is “herb”, the
query is “oolong”, and the query’s ground truth parent is “tea”.

To illustrate how the coherence modeling module compares the nodes in the ego-
tree to maintain the taxonomy’s coherence, we present the weights of an
attention head of the module’s first Transformer encoder layer in Fig. 6.
Since the last layer’s attention mostly focuses on the anchor node (“herb”),
the first layer can better illustrate the model’s comparison among ego-tree
nodes.

Based on our observation, the two ¡CLS¿s are capable of finding the best-
suited parent node in the ego-tree even if it is not the anchor. Since the
coherence modeling module utilizes ego-trees for hierarchy modeling, the
coherence modeling module can compare a node with all its ancestors and its
children to find the most suited anchor, which makes the model more robust.
Besides, the coherence modeling module is also able to assign a lower
attention weight to the best-suited parent’s parent node when it is on the
right path, suggesting that the coherence modeling module can achieve both
path-wise and level-wise comparison.

##  6\. Conclusion

We proposed HEF, a self-supervised taxonomy expansion model that fully
exploits the hierarchical structure of a taxonomy for better hierarchical
structure modeling and taxonomy coherence maintenance. Compared to previous
methods that evaluate the anchor by merely a new edge in a normal graph
neglecting the tree structure of taxonomy, we used extensive experiments to
prove that, evaluating a tree structure for coherence maintenance, and mining
multiple tree-exclusive features in the taxonomy, including hypernymy
relations from parent-child relations, term similarity from sibling relations,
absolute and relative levels, path+level based multi-dimensional evaluation,
and disambiguation based on parent-current-child chains all brought
performance boost. This indicates the importance of using the information of
tree structure for the taxonomy expansion task. We also proposed a framework
for injecting these features, introduced our implementation of the framework,
and surpassed the previous state-of-the-art. We believe that these novel
designs and their motivations will not only benefit the taxonomy expansion
task, but also be influential for all tasks involving hierarchical or tree
structure modeling and evaluation. Future works include how to model and
utilize these or new tree-exclusive features to boost other taxonomy-related
tasks, and better implementation of each module in HEF.

###### Acknowledgements.

Thanks to everyone who helped me with this paper in the Tencent Jarvis Lab, my
family, and my loved one.

## References

  * (1)
  * Agichtein and Gravano (2000) Eugene Agichtein and Luis Gravano. 2000.  Snowball: Extracting Relations From Large Plain-Text Collections. In _Proceedings of JCDL_. 85–94.
  * Bordea et al. (2016) Georgeta Bordea, Els Lefever, and Paul Buitelaar. 2016\.  SemEval-2016 Task 13: Taxonomy Extraction Evaluation (TExEval-2). In _Proceedings of the SemEval-2016_. 1081–1091.
  * Cocos et al. (2018) Anne Cocos, Marianna Apidianaki, and Chris Callison-Burch. 2018\.  Comparing Constraints for Taxonomic Organization. In _Proceedings of NAACL_. 323–333.
  * Dash et al. (2020) Sarthak Dash, Md Faisal Mahbub Chowdhury, Alfio Gliozzo, Nandana Mihindukulasooriya, and Nicolas Rodolfo Fauceglia. 2020\.  Hypernym Detection Using Strict Partial Order Networks. In _Proceedings of AAAI_. 7626–7633.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-Training of Deep Bidirectional Transformers for Language Understanding. In _Proceedings of NAACL_. 4171–4186.
  * Fountain and Lapata (2012) Trevor Fountain and Mirella Lapata. 2012.  Taxonomy Induction Using Hierarchical Random Graphs. In _Proceedings of NAACL_. 466–476.
  * Gupta et al. (2017) Amit Gupta, Rémi Lebret, Hamza Harkous, and Karl Aberer. 2017\.  Taxonomy Induction Using Hypernym Subsequences. In _Proceedings of CIKM_. 1329–1338.
  * Hearst (1992) Marti A. Hearst. 1992\.  Automatic Acquisition of Hyponyms From Large Text Corpora. In _Proceedings of ACL_. 539–545.
  * Hua et al. (2017) Wen Hua, Zhongyuan Wang, Haixun Wang, Kai Zheng, and Xiaofang Zhou. 2017.  Understand Short Texts by Harvesting and Analyzing Semantic Knowledge.  _IEEE Transactions on Knowledge and Data Engineering_ (2017), 499–512.
  * Huang et al. (2019) Jin Huang, Zhaochun Ren, Wayne Xin Zhao, Gaole He, Ji-Rong Wen, and Daxiang Dong. 2019\.  Taxonomy-Aware Multi-Hop Reasoning Networks for Sequential Recommendation. In _Proceedings of WSDM_. 573–581.
  * Jiang et al. (2017) Meng Jiang, Jingbo Shang, Taylor Cassidy, Xiang Ren, Lance M. Kaplan, Timothy P. Hanratty, and Jiawei Han. 2017.  MetaPAD: Meta Pattern Discovery From Massive Text Corpora. In _Proceedings of KDD_. 877–886.
  * Jurgens and Pilehvar (2015) David Jurgens and Mohammad Taher Pilehvar. 2015.  Reserating the Awesometastic: An Automatic Extension of the WordNet Taxonomy for Novel Terms. In _Proceedings of NAACL_. 1459–1465.
  * Jurgens and Pilehvar (2016) David Jurgens and Mohammad Taher Pilehvar. 2016.  SemEval-2016 Task 14: Semantic Taxonomy Enrichment. In _Proceedings of the SemEval-2016_. 1092–1102.
  * Karamanolakis et al. (2020) Giannis Karamanolakis, Jun Ma, and Xin Luna Dong. 2020.  TXtract: Taxonomy-Aware Knowledge Extraction for Thousands of Product Categories.  (2020).
  * Kim et al. (2020) Seohyun Kim, Jinman Zhao, Yuchi Tian, and Satish Chandra. 2020\.  Code Prediction by Feeding Trees to Transformers.  (2020).
  * Kozareva and Hovy (2010) Zornitsa Kozareva and Eduard Hovy. 2010.  A Semi-Supervised Method to Learn and Construct Taxonomies Using the Web. In _Proceedings of EMNLP_. 1110–1118.
  * Le et al. (2019) Matthew Le, Stephen Roller, Laetitia Papaxanthos, Douwe Kiela, and Maximilian Nickel. 2019\.  Inferring Concept Hierarchies From Text Corpora via Hyperbolic Embeddings. In _Proceedings of ACL_. 3231–3241.
  * Lin (1998) Dekang Lin. 1998\.  An Information-Theoretic Definition of Similarity. In _Proceedings of ICML_. 296–304.
  * Lipscomb (2000) Carolyn E. Lipscomb. 2000\.  Medical Subject Headings (MeSH).  _Bulletin of the Medical Library Association_ (2000), 265–266.
  * Liu et al. (2019) Bang Liu, Weidong Guo, Di Niu, Chaoyue Wang, Shunnan Xu, Jinghong Lin, Kunfeng Lai, and Yu Xu. 2019\.  A User-Centered Concept Mining System for Query and Document Understanding at Tencent. In _Proceedings of KDD_. 1831–1841.
  * Loshchilov and Hutter (2019) Ilya Loshchilov and Frank Hutter. 2019.  Decoupled Weight Decay Regularization.  (2019).
  * Luo et al. (2020) Xusheng Luo, Luxin Liu, Yonghua Yang, Le Bo, Yuanpeng Cao, Jinghang Wu, Qiang Li, Keping Yang, and Kenny Q. Zhu. 2020.  AliCoCo: Alibaba E-Commerce Cognitive Concept Net. In _Proceedings of SIGMOD_. 313–327.
  * Manzoor et al. (2020) Emaad Manzoor, Rui Li, Dhananjay Shrouty, and Jure Leskovec. 2020\.  Expanding Taxonomies With Implicit Edge Semantics. In _Proceedings of TheWebConf_. 2044–2054.
  * Mao et al. (2018) Yuning Mao, Xiang Ren, Jiaming Shen, Xiaotao Gu, and Jiawei Han. 2018.  End-To-End Reinforcement Learning for Automatic Taxonomy Induction. In _Proceedings of ACL_. 2462–2472.
  * Miller (1995) George A. Miller. 1995\.  WordNet: A Lexical Database for English.  _Commun. ACM_ (1995), 39–41.
  * Panchenko et al. (2016) Alexander Panchenko, Stefano Faralli, Eugen Ruppert, Steffen Remus, Hubert Naets, Cédrick Fairon, Simone Paolo Ponzetto, and Chris Biemann. 2016.  TAXI at SemEval-2016 Task 13: A Taxonomy Induction Method Based on Lexico-Syntactic Patterns, Substrings and Focused Crawling. In _Proceedings of SemEval-2016_. 1320–1327.
  * Peng et al. (2019) Hao Peng, Jianxin Li, Senzhang Wang, Lihong Wang, Qiran Gong, Renyu Yang, Bo Li, Philip Yu, and Lifang He. 2019.  Hierarchical Taxonomy-Aware and Attentional Graph Capsule RCNNs for Large-Scale Multi-Label Text Classification.  _IEEE Transactions on Knowledge and Data Engineering_ (2019).
  * Roller et al. (2018) Stephen Roller, Douwe Kiela, and Maximilian Nickel. 2018\.  Hearst Patterns Revisited: Automatic Hypernym Detection From Large Text Corpora. In _Proceedings of ACL_. 358–363.
  * Sang (2007) Erik Tjong Kim Sang. 2007\.  Extracting Hypernym Pairs From the Web. In _Proceedings of ACL_. Association for Computational Linguistics, 165–168.
  * Sanh et al. (2020) Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. 2020.  DistilBERT, a Distilled Version of BERT: Smaller, Faster, Cheaper and Lighter.  (2020).
  * Shang et al. (2020a) Chao Shang, Sarthak Dash, Md. Faisal Mahbub Chowdhury, Nandana Mihindukulasooriya, and Alfio Gliozzo. 2020a.  Taxonomy Construction of Unseen Domains via Graph-Based Cross-Domain Knowledge Transfer. In _Proceedings of ACL_. 2198–2208.
  * Shang et al. (2020b) Jingbo Shang, Xinyang Zhang, Liyuan Liu, Sha Li, and Jiawei Han. 2020b.  NetTaxo: Automated Topic Taxonomy Construction From Text-Rich Network. In _Proceedings of TheWebConf_. 1908–1919.
  * Shaw et al. (2018) Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. 2018\.  Self-Attention With Relative Position Representations. In _Proceedings of NAACL_. 464–468.
  * Shen et al. (2020) Jiaming Shen, Zhihong Shen, Chenyan Xiong, Chi Wang, Kuansan Wang, and Jiawei Han. 2020\.  TaxoExpan: Self-Supervised Taxonomy Expansion With Position-Enhanced Graph Neural Network. In _Proceedings of TheWebConf_. 486–497.
  * Shen et al. (2018) Jiaming Shen, Zeqiu Wu, Dongming Lei, Chao Zhang, Xiang Ren, Michelle T. Vanni, Brian M. Sadler, and Jiawei Han. 2018\.  HiExpan: Task-Guided Taxonomy Construction by Hierarchical Tree Expansion. In _Proceedings of KDD_. 2180–2189.
  * Shiv and Quirk (2019) Vighnesh Shiv and Chris Quirk. 2019.  Novel Positional Encodings to Enable Tree-Based Transformers.  In _Advances in Neural Information Processing Systems 32_. 12081–12091.
  * Shwartz et al. (2016) Vered Shwartz, Yoav Goldberg, and Ido Dagan. 2016\.  Improving Hypernymy Detection With an Integrated Path-Based and Distributional Method. In _Proceedings of ACL_. Association for Computational Linguistics, 2389–2398.
  * Tai et al. (2015) Kai Sheng Tai, Richard Socher, and Christopher D. Manning. 2015\.  Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks. In _Proceedings of ACL/IJCNLP_. 1556–1566.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017\.  Attention Is All You Need.  In _Advances in Neural Information Processing Systems 30_. 5998–6008.
  * Vedula et al. (2018) Nikhita Vedula, Patrick K. Nicholson, Deepak Ajwani, Sourav Dutta, Alessandra Sala, and Srinivasan Parthasarathy. 2018.  Enriching Taxonomies With Functional Domain Knowledge. In _Proceedings of SIGIR_. 745–754.
  * Velardi et al. (2013) Paola Velardi, Stefano Faralli, and Roberto Navigli. 2013\.  OntoLearn Reloaded: A Graph-Based Algorithm for Taxonomy Induction.  _Computational Linguistics_ (2013), 665–707.
  * Wang et al. (2019) Chengyu Wang, Yan Fan, Xiaofeng He, and Aoying Zhou. 2019\.  A Family of Fuzzy Orthogonal Projection Models for Monolingual and Cross-Lingual Hypernymy Prediction. In _Proceedings of WWW_. 1965–1976.
  * Wang et al. (2014) Jingjing Wang, Changsung Kang, Yi Chang, and Jiawei Han. 2014\.  A Hierarchical Dirichlet Model for Taxonomy Expansion for Search Engines. In _Proceedings of WWW_. 961–970.
  * Wu and Palmer (1994) Zhibiao Wu and Martha Palmer. 1994.  Verbs Semantics and Lexical Selection. In _Proceedings of ACL_. 133–138.
  * Yin and Roth (2018) Wenpeng Yin and Dan Roth. 2018.  Term Definitions Help Hypernymy Detection. In _Proceedings of *SEM_. 203–213.
  * Yin and Shah (2010) Xiaoxin Yin and Sarthak Shah. 2010.  Building Taxonomy of Web Search Intents for Name Entity Queries. In _Proceedings of WWW_. 1001–1010.
  * Yu et al. (2020) Yue Yu, Yinghao Li, Jiaming Shen, Hao Feng, Jimeng Sun, and Chao Zhang. 2020\.  STEAM: Self-Supervised Taxonomy Expansion With Mini-Paths. In _Proceedings of KDD_. 1026–1035.
  * Zhang et al. (2018) Chao Zhang, Fangbo Tao, Xiusi Chen, Jiaming Shen, Meng Jiang, Brian Sadler, Michelle Vanni, and Jiawei Han. 2018\.  TaxoGen: Unsupervised Topic Taxonomy Construction by Adaptive Term Embedding and Clustering. In _Proceedings of KDD_. 2701–2709.

##  Appendix A Case Study

To understand how different Fitting Score components contribute to HEF’s
performance, we conduct a case study on the SemEval16-Food dataset and show
the detailed results in Table 4.

The first two rows of Table 4 shows two cases where HEF successfully predicts
the query’s parent. We can see that the Pathfinder Score and the three Stopper
Scores all contribute to the correct selection, which testifies the
effectiveness of the Fitting Score design.

The last two rows of Table 4 provide situations when HEF fails to select the
correct parent. In the third row, “bourguignon” is described as “reduced red
wine”, thus the model attaches it to the node “wine”. However, “bourguignon”
is also a sauce for cooking beef. Such ambiguation consequently affects the
meaning of a term by assigning an incorrect description, which hurts the
model’s performance. In the last row, although “hot fudge sauce”’s description
contains ”chocolate sauce”, the node “chocolate sauce” still gets a low
Current Score. In HEF, the design of Stopper Scores enables the model to self-
correct the occasionally wrong Current Scores by assigning larger Forward
Score from a node’s parent and larger Backward Score from one of the node’s
children. However, since “chocolate sauce” is a leaf node, its child’s
Backward Score is assigned to be the proportion of leaf nodes in the seed
taxonomy, which is 0.07 in the SemEval16-Food dataset. This indicates that
future work includes designing a more reasonable Backward Score function for
leaf nodes to improve the model’s robustness.

##  Appendix B Description Generation Algorithm

Algorithm 2 shows the description generation algorithm descr($\cdot$) used in
HEF’s hypernymy detection module. descr($\cdot$) utilizes WordNet descriptions
to generate domain-related term descriptions by dynamic programming. In this
algorithm, WordNetNounDescr($\cdot$) means the set of a concept’s noun
descriptions from WordNet (Miller, 1995), and
CosSimilarity($t,n_{\mbox{root}}$) means calculating the average token cosine
similarity of word vectors between a candidate description $t$ and the surface
name of a taxonomy’s root term $n_{\mbox{root}}$.

Algorithm 2 Description Generation Algorithm for the Hypernymy Detection
Module

1:procedure Descr($n$) $\triangleright$ Input: term $n$

2: $N\leftarrow$split($n$)

3: for $i\leftarrow 0,\cdots,\texttt{length($N$)}$ do

4: $S[i]=0$ $\triangleright$ Initialize score array

5: $C[i]=0$ $\triangleright$ Initialize splitting positions

6: end for

7: for $i\leftarrow 0,\cdots,\texttt{length($N$)$-1$}$ do

8: for $j\leftarrow 0,\cdots,i$ do

9: if WordNetNounDescr($N[j:i+1]$)$>0$ then

10: $s_{ij}=\left(i-j+1\right)^{2}+1$ $\triangleright$ Prefer longer concepts

11: else

12: $s_{ij}=1$

13: end if

14: if $S[j]+s_{ij}>S[i+1]$ then

15: $S[i+1]\leftarrow S[j]+s_{ij}$ $\triangleright$ Save max score

16: $C[i]=j$ $\triangleright$ Save splitting position

17: end if

18: end for

19: end for

20: $D\leftarrow$“” $\triangleright$ Initialize description

21: $p\leftarrow\texttt{length(}N\texttt{)}$ $\triangleright$ Generate split
pointer

22: while $p\neq-1$ do

23: $D_{WN}=$WordNetNounDescr($N\left[C[p]:p+1\right]$)

24: if len($D_{WN}$)$>0$ then $\triangleright$ Noun or noun phrase

25: $d\leftarrow\mathop{\arg\max}_{t\in
D_{WN}}{{\texttt{CosSimilarity(}}t,n_{\mbox{root}}{\texttt{)}}}$

26: else$\triangleright$ Prep. or adj.

27: $d\leftarrow{\texttt{j}oin(}N[C[p]:p+1]\texttt{)}$

28: end if

29: $D\leftarrow d+D$ $\triangleright$ Put new description in the front

30: $p\leftarrow C[p]-1$ $\triangleright$ Go to next split

31: end while

32:end procedure

Table 4. Examples of HEF’s prediction, with detailed Fitting Score composition and comparison between the ground truth and the predicted parent. Scores in this table correspond to the node in the same tabular cell with the score. Query ($q$) |  Ground Truth ($\hat{p}$) |  Scores |  Prediction ($p$) |  Scores
---|---|---|---|---
$q$: paddy is rice in the husk either gathered or still in the field |  $\hat{p}$: rice is grains used as food either unpolished or more often polished |  $S_{p}=0.9997$ |  $p$: rice is grains used as food either unpolished or more often polished |  $S_{p}=0.9997$
|  |  $S_{c}=0.4599$ |  |  $S_{c}=0.4599$
|  ${\rm parent}(\hat{p})$: starches is a commercial preparation of starch that is used to stiffen textile fabrics in laundering |  $S_{f}=0.9755$ |  ${\rm parent}(p)$: starches is a commercial preparation of starch that is used to stiffen textile fabrics in laundering |  $S_{f}=0.9755$
$F(\hat{p},q)=0.4483$ |  $c_{\hat{p}}^{*}$: white rice is having husk or outer brown layers removed |  $S_{b}=0.9995$ |  $c_{p}^{*}$: white rice is having husk or outer brown layers removed |  $S_{b}=0.9995$
$\hat{p}$’s Ranking: 1 |  |  |  |
$q$: fish meal is ground dried fish used as fertilizer and as feed for domestic livestock |  $\hat{p}$: feed is food for domestic livestock |  $S_{p}=0.9993$ |  $p$: feed is food for domestic livestock |  $S_{p}=0.9993$
|  |  $S_{c}=0.3169$ |  |  $S_{c}=0.3169$
|  ${\rm parent}(\hat{p})$: food is any substance that can be metabolized by an animal to give energy and build tissue |  $S_{f}=0.9984$ |  ${\rm parent}(p)$: food is any substance that can be metabolized by an animal to give energy and build tissue |  $S_{f}=0.9984$
$F(\hat{p},q)=0.3158$ |  $c_{\hat{p}}^{*}$: mash is mixture of ground animal feeds |  $S_{b}=0.9988$ |  $c_{p}^{*}$: mash is mixture of ground animal feeds |  $S_{b}=0.9988$
$\hat{p}$’s Ranking: 1 |  |  |  |
$q$: bourguignon is reduced red wine with onions and parsley and thyme and butter |  $\hat{p}$: sauce is flavorful relish or dressing or topping served as an accompaniment$\cdots$ |  $S_{p}=0.0002$ |  $p$: wine is a red as dark as red wine |  $S_{p}=0.9997$
|  |  $S_{c}=0.0001$ |  |  $S_{c}=0.1399$
|  ${\rm parent}(\hat{p})$: condiment is a preparation (a sauce or relish or spice) to enhance flavor or enjoyment |  $S_{f}=0.0004$ |  ${\rm parent}(p)$: alcohol is any of a series of volatile hydroxyl compounds that are made from hydrocarbons by distillation |  $S_{f}=0.9812$
$F(\hat{p},q)=1e-11$ |  $c_{\hat{p}}^{*}$: bercy is butter creamed with white wine and shallots and parsley |  $S_{b}=0.9997$ |  $c_{p}^{*}$: red wine is wine having a red color derived from skins of dark-colored grapes |  $S_{b}=0.8784$
$\hat{p}$’s Ranking: 328 |  |  |  |
$q$: hot fudge sauce is hot thick chocolate sauce served hot |  $\hat{p}$: chocolate sauce is sauce made with unsweetened chocolate or cocoa$\cdots$ |  $S_{p}=0.9471$ |  $p$: sauce is flavorful relish or dressing or topping served as an accompaniment$\cdots$ |  $S_{p}=0.9995$
|  |  $S_{c}=9e-5$ |  |  $S_{c}=0.0172$
|  ${\rm parent}(\hat{p})$: sauce is flavorful relish or dressing or topping served as an accompaniment$\cdots$ |  $S_{f}=0.9617$ |  ${\rm parent}(p)$: condiment is a preparation (a sauce or relish or spice) to enhance flavor or enjoyment |  $S_{f}=0.9888$
$F(\hat{p},q)=6e-6$ |  $c_{\hat{p}}^{*}$: None |  $S_{b}=0.0700$ |  $c_{p}^{*}$: lyonnaise sauce is brown sauce with sauteed chopped onions and parsley$\cdots$ |  $S_{b}=0.9995$
$\hat{p}$’s Ranking: 20 |  |  |  |