# Learning by non-interfering feedback chemical signaling
in physical networks

Vidyesh Rao Anisetti,1 B. Scellier,2 J. M. Schwarz1,3 1 Physics Department,
Syracuse University, Syracuse, NY 13244 USA
2 Department of Mathematics, ETH Zürich, Zürich, Switzerland
3 Indian Creek Farm, Ithaca, NY 14850 USA

###### Abstract

Both non-neural and neural biological systems can learn. So rather than
focusing on purely brain-like learning, efforts are underway to study learning
in physical systems. Such efforts include equilibrium propagation (EP) and
coupled learning (CL), which require storage of two different states—the free
state and the perturbed state—during the learning process to retain
information about gradients. Here, we propose a new learning algorithm rooted
in chemical signaling that does not require storage of two different states.
Rather, the output error information is encoded in a chemical signal that
diffuses into the network in a similar way as the activation/feedforward
signal. The steady state feedback chemical concentration, along with the
activation signal, stores the required gradient information locally. We apply
our algorithm using a physical, linear flow network and test it using the Iris
data set with 93% accuracy. We also prove that our algorithm performs gradient
descent. Finally, in addition to comparing our algorithm directly with EP and
CL, we address the biological plausibility of the algorithm.

##  I Introduction

What basic ingredients constitute a biological learning system, such as slime
mold or higher-order organisms? Biological learning systems adapt to the
external environment by tailoring specific responses for given external
conditions. As the system continues to experience external conditions of a
similar kind, it develops functionality to respond to the stimulus in such a
way to increase its chances of survival. Intriguingly, this functionality is
an emergent phenomenon as a result of interactions between the various
components Sumpter2006 . For example, when birds come together in a flock,
they increase their chances of survival Beauchamp2021 . This happens not
because of a ‘supervisor’ that commands each bird to fly in a particular way,
but because birds, such as starlings, interact with a fixed number of
neighbors independent of their density to give rise to emergent functionality
Ballerini2008 . Similarly, in the presence of rising waters, fire ants
cooperate to form floating rafts consisting of a structural base and freely-
moving ants on top of the base with treadmilling between the two roles
antraft1 ; antraft2 . Local, ant interaction rules, including an effective
repulsive force between the freely-moving ants and the water replicate the
types of observed shapes of rafts wagner2022 . These special interactions
between components, responsible for emergent functionality in nature, have
themselves emerged out of the long process of evolution.

Given the intricacies of biological learning systems, neural networks are in
silico brain-like learning systems, resembling the visual cortex, in
particular Issa2018 ; Kriegeskorte2015 ; D1988 ; Roelfsema2018 , that can
recognize patterns and solve problems nielsenneural ; Yang2020 . More
specifically, neural networks achieve functionality by modifying weights and
biases to minimise a particular cost function. Of the many ways to do so, the
algorithm of choice in neural networks with multiple layers (deep learning) is
the backpropagation algorithm Rumelhart1986 . Backpropagation updates the
network such that its weights (and biases) perform gradient descent in the
cost function landscape. The complex nature of the tasks that neural networks
are capable of hints at the possibility that biological learning systems also
achieve functionality by optimizing cost functions by gradient descent
Lillicrap2020 . In other words, the long process of evolution may have
optimised the “learning algorithm” in such biological systems to update its
components via gradient descent. The success of backpropagation has,
therefore, encouraged a search for biologically plausible learning rules
analogous to it sacramento2018dendritic ; Pozzi2018 ; Richards2019 ;
WHITTINGTON2019235 ; Lillicrap2020 ; payeur2021burst . For completeness, here
are properties one should ensure while constructing such a biologically
plausible learning system :

  1. 1.

local learning algorithms 111By local we not only mean in terms of metric
distance,

  2. 2.

the implementation of such algorithms is constrained by the laws of physics,
and

  3. 3.

the algorithms minimize a cost function via gradient descent or stochastic
gradient descent.

Indeed, there have been attempts to construct learning algorithms within
purely physical systems Hopfield1984 ; markovic2020physics ; endtoend2020 ;
scellier2020deep ; Stern2021 ; wright2022deep . Here, we will focus on
“equilibrium propagation” Scellier2017 ; scellier2020deep  and “coupled
learning”Stern2021 . In these approaches, the error information corresponding
to each component is encoded in terms of differences of local physical
quantities measured between two phases. At each step of training, the outputs
of the network are nudged towards the target output by applying additional
boundary conditions at the output nodes. Next, the system is allowed to settle
to a new steady state called the “nudged state” (or the “clamped state”),
which is closer to the desired target than the initial “free state”. In the
limit where the nudge amplitude goes to zero, the difference of local,
physical quantities between these two phases encodes the gradient of the cost
function Scellier2017 . Unlike backpropagation, these algorithms achieve
gradient descent without an explicit layer-by-layer transfer of error
information. Nevertheless, one caveat of these approaches is the requirement
to store the free state. In other words, the learning rule requires
information about the free state, which is no longer physically available at
the end of the second phase when the parameters are updated. One way around
this requirement is to build two copies of the same physical network
Dillavou2021 , though biology does not necessarily have such a luxury.

In this work, we present a new algorithm and a new learning rule that
overcomes the above requirement in equilibrium propagation and coupled
learning. Our learning rule computes the gradients using local information for
each weight without the need to store the free state. We demonstrate that the
functionality of the nudged state can be realised in physical and biophysical,
learning systems using chemical signalling. We show that steady state chemical
concentrations can be used in the second phase to encode the required gradient
information. Chemical signaling is ubiquitious in biology. For example,
consider the structurally simple, yet functionally complex organism, named
Physarum polycephalum, otherwise known as slime mold. Slime mold is a uni-
cellular, multi-nucleated organism that is neither a plant nor an animal nor a
fungus. This uni-cellular organism can span up to the meter scale and consists
of a network of tubes whose underlying structure is driven by cytoskeletal
reorganization slimemold . Despite its simplicity, in the sense that it is
non-neuronal, this organism is capable of myriad complex tasks – precisely
coordinating flows in its body Boussard2021 , navigating mazes slimemaze2000 ,
and connecting food sources with optimal paths tero2010 ; Tero2008 . Work by
K. Alim and others showed that much of this complex phenomenon can be
explained by a mechanism of signal propagation Alim2017 . Specifically, slime
mold uses a chemical signal to send information regarding the location of food
sources across its body, which triggers a change in its tubular structure due
to a softening agent to optimize the connection between food sources Alim2021
.

In light of an example, we construct a physical learning network of
tubes/pipes that uses chemical signals to send error information across the
system. Our system is a flow network, with activation pressures at nodes v and
pipe conductance described by weights w. The information from the external
environment is input into the system by fixing the boundary conditions I at
input nodes. Node activation pressures v are the non-trainable variables (or
“state variables”) of the system that are determined by Laplace’s equation and
input boundary conditions. Our physical system is, therefore, a linear one.
The functionality we seek is to obtain desired pressures (“target pressures”)
at output nodes for a given input I. To achieve this, a feedback chemical is
released into the flow network by fixing the chemical currents at output
nodes. The value $\bm{\epsilon}$ of these chemical currents is proportional to
the difference between target pressures and output pressures. The chemical
concentrations u at internal nodes are determined by the same Laplace
equation, but with feedback boundary conditions $\bm{\epsilon}$. We show that
this chemical concentration u along with the node pressures v locally encode
the weight gradients of the cost function that we want to optimize. We propose
a new learning rule that updates the trainable weights w such that it does
gradient descent with respect to the cost function.

##  II Theory

Figure 1: The flow network. Schematic of the flow network with blue points
representing the input node pair and red points representing the output node
pair. The weights of the flow network are denoted by $w_{xy}$ between
neighboring nodes $x$ and $y$. These weights are varied during the training-
testing process.

We consider a flow network of nodes interconnected by weighted edges. We
denote $w_{xy}$ the weight (i.e. conductance) of the edge between node $x$ and
node $y$. A subset of the nodes are boundary node pairs (or “input” node
pairs), denoted
$\\{(b_{1}^{+},b_{1}^{-}),(b_{2}^{+},b_{2}^{-}),\ldots,(b_{q}^{+},b_{q}^{-})\\}$.
For each pair $(b_{j}^{+},b_{j}^{-})$, an input current $I_{j}$ flows into the
network through the node $b_{j}^{+}$ and flows out of the network through the
node $b_{j}^{-}$. The state of the system is defined by the node pressures,
denoted $v(x)$ and governed by Laplace’s equation at steady state. Another
subset of the nodes are output node pairs
$\\{(o_{1}^{+},o_{1}^{-}),(o_{2}^{+},o_{2}^{-}),\ldots,(o_{p}^{+},o_{p}^{-})\\}$.
The output of the network is defined as the set of pressure drops across
output nodes
$\\{v(o_{1}^{+},o_{1}^{-}),v(o_{2}^{+},o_{2}^{-}),\ldots,v(o_{p}^{+},o_{p}^{-})\\}$
where $v(o_{i}^{+},o_{i}^{-})=v(o_{i}^{+})-v(o_{i}^{-})$. We note that
$v(o_{i}^{+},o_{i}^{-})$ is a function of input currents $\\{I_{j}\\}$ and all
the weights of the network $\\{w_{xy}\\}$. Training the network consists in
modifying the weights $\\{w_{xy}\\}$ such that, given the input currents
$\\{I_{j}\\}$, we get desired pressure drops
$\\{v_{d}(o_{i}^{+},o_{i}^{-})\\}$ across the output node pairs. We define the
cost function

$C=\frac{1}{2}\sum_{i=1}^{p}(v(o_{i}^{+},o_{i}^{-})-v_{d}(o_{i}^{+},o_{i}^{-}))^{2}.$
(1)

Now we present a physical procedure and a learning rule for the weights that
performs gradient descent with respect to the cost function. To achieve this,
we release a feedback chemical into the network through the pairs of output
nodes $\\{(o_{i}^{+},o_{i}^{-})\\}$, by fixing chemical currents across these
nodes. Specifically, for each pair of output nodes $(o_{i}^{+},o_{i}^{-})$, a
current

$\epsilon_{i}=\eta(v_{d}(o_{i}^{+},o_{i}^{-})-v(o_{i}^{+},o_{i}^{-}))$ (2)

flows into the network through node $o_{i}^{+}$ and flows out of the network
through node $o_{i}^{-}$, where $\eta$ is a constant (“nudging”). A steady
state chemical concentration develops at every node, governed again by
Laplace’s equation. We denote $u(x)$ the steady state concentration at node
$x$, and $u(x,y)$ the drop in chemical concentration between nodes $x$ and
$y$. Finally, we update each weight $w_{xy}$ according to

$\Delta w_{xy}=-\alpha u(x,y)v(x,y),$ (3)

where $\alpha$ is a constant. We show below that this learning rule performs
gradient descent on the cost function with step size (“learning rate”)
$\alpha\eta$, i.e.

$\Delta w_{xy}=-\alpha\eta\dfrac{\partial C}{\partial w_{xy}}$ (4)

for every weight $w_{xy}$. The above learning rule for the weights is local.
The final error term depends upon two quantities; the pressure drop due to
flow and the concentration drop of the feedback chemical. If they have the
same sign, then the weight gets a positive update and vice versa. Here, we
assume that the relaxation time scale of the system is much faster than the
time scale of weight updates so that the system is in steady state as the
weights are updated.

Note that the two quantities in the weight update are independent of each
other, therefore, we assume that diffusion is fast enough that it is
independent of the flow. In an experimental setting, one can realize this by
using very small flow rate, leading to very small pressure drops across
weights and using a signalling chemical with very high diffusion rate via,
perhaps, some catalytic process. We understand that such a construction is not
necessarily realized in nature, therefore, we also propose a purely flow
version of the model where the chemical signals are carried by the fluid flow
and not by diffusion (Appendix A). While this chemical flow algorithm is
presumably more physically plausible, it is not yet clear that the algorithm
performs gradient descent. In any event, what we present here is an
idealization. Obviously, nature may be using a complex combination of flow and
diffusion for signalling.

Considering $v$ as a pressure and $u$ as a chemical concentration is just a
certain packaging of the theory. The central idea of this work is to use two
independent physical quantities which leads to non-interference of the input
signal and the feedback signal, in other words one can use any two non-
interfering modalities to conduct learning 222 We acknowledge Nachi Stern for
suggesting the use of the word modality . For example, one can use two
chemicals $v$ and $u$ diffusing in a static fluid, with distinct chemical
signatures to encode input and error signal. In this case, there is no need
for an additional assumption on the relationship between flow rate and
diffusion rate.

Our result holds for any cost function $C$, not just the squared error (Eq.
1). In general, in the second phase, the chemical current flowing in through
$o_{i}^{+}$ and flowing out through $o_{i}^{-}$ must be
$\epsilon_{i}=-\eta\frac{\partial C}{\partial v(o_{i}^{+},o_{i}^{-})}$. Our
result also holds if we reverse the sign of $\eta$ (2) and the sign of
$\alpha$ in the learning rule (3). In other words, the algorithm performs
gradient descent so long as $\alpha\eta>0$.

Now we prove our claim that the learning rule (3) performs gradient descent
(4). Let us number the nodes of the network $1,2,\ldots,n$. Let $I_{x}$ be the
input current at node $x$ (with $I_{x}=0$ by convention if node $x$ is not an
input node) and $v_{x}$ the pressure at node $x$. For each node $x$, the
steady state condition at node $x$ in the first phase yields:

$\sum_{y}w_{xy}(v_{x}-v_{y})=I_{x}.$ (5)

We get a system of $n$ linear equations. This system rewrites with matrix-
vector notations as

$L\cdot v=I,$ (6)

where $v$ is the vector of node pressures, $I$ is the vector of input currents
and $L$ is the matrix

$L=\left(\begin{array}[]{ccccc}\sum_{x}w_{1x}&-w_{12}&-w_{13}&\cdots&-w_{1n}\\\
-w_{21}&\sum_{x}w_{2x}&-w_{23}&\cdots&-w_{2n}\\\
-w_{31}&-w_{32}&\sum_{x}w_{3x}&\cdots&-w_{3n}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
-w_{n1}&-w_{n2}&-w_{n3}&\cdots&\sum_{x}w_{nx}\\\ \end{array}\right).$ (7)

Note that the matrix $L$ is symmetric because $w_{xy}=w_{yx}$ for every pair
of nodes $(x,y)$. Next, we denote $E_{x}=-\eta\frac{\partial C}{\partial
v_{x}}$ the chemical current at node $x$ in the second phase (with $e_{x}=0$
by convention if node $x$ is not an output node), and $u_{x}$ the
concentration of the chemical at node $x$. Assuming that the diffusion
constant of the chemical is equal to the flow conductivity (up to a constant
of proportionality), the chemical concentration at steady state satisfies the
same system of linear equations, with different boundary conditions, i.e.

$L\cdot u=E,$ (8)

where $u$ is the vector of node concentrations, and $E$ is the vector of
chemical currents. Now we compute the gradient of the cost function: for every
weight $w_{xy}$ we have

$\frac{\partial C}{\partial w_{xy}}=\left(\frac{\partial C}{\partial
v}\right)^{\top}\cdot\frac{\partial v}{\partial w_{xy}}.$ (9)

Multiplying by $-\eta$ on both sides, we get, by definition of $E$,

$-\eta\frac{\partial C}{\partial w_{xy}}=E^{\top}\cdot\frac{\partial
v}{\partial w_{xy}}.$ (10)

Using the steady state condition of the second phase (8) and the fact that $L$
is symmetric, we get

$-\eta\frac{\partial C}{\partial w_{xy}}=u^{\top}\cdot L\cdot\frac{\partial
v}{\partial w_{xy}}.$ (11)

Next, we differentiate the steady state condition of the first phase (6) with
respect to $w_{xy}$. We get

$\frac{\partial L}{\partial w_{xy}}\cdot v+L\cdot\frac{\partial v}{\partial
w_{xy}}=0.$ (12)

Rearranging the terms and injecting this in (11), we get

$\eta\frac{\partial C}{\partial w_{xy}}=u^{\top}\cdot\frac{\partial
L}{\partial w_{xy}}\cdot v.$ (13)

Looking at the form of the matrix $L$ (7), the matrix $\frac{\partial
L}{\partial w_{xy}}$ has exactly four non-zero coefficients: those at
positions $(x,x)$, $(x,y)$, $(y,x)$ and $(y,y)$, equal to $+1$, $-1$, $-1$ and
$+1$, respectively. Therefore

$\displaystyle u^{\top}\cdot\frac{\partial L}{\partial w_{xy}}\cdot v$
$\displaystyle=\;\;$ $\displaystyle u(x)v(x)-u(x)v(y)-u(y)v(x)+u(y)v(y)$ (14)
$\displaystyle=\;\;$ $\displaystyle(u(x)-u(y))\cdot(v(x)-v(y))$ (15)
$\displaystyle=\;\;$ $\displaystyle u(x,y)\cdot v(x,y).$ (16)

Combining this with (13), we conclude that

$\Delta w_{xy}=-\alpha u(x,y)\cdot v(x,y)=-\alpha\eta\frac{\partial
C}{\partial w_{xy}}.$ (17)

Hence, the learning rule corresponds to one step of gradient descent with step
size $\alpha\eta$. This concludes the proof.

Summing up the training mechanism:

  1. 1.

A flow network is generated where chemicals can spread via a diffusion
process.

  2. 2.

Input to the network is given by fixing currents $\\{I_{j}\\}$ across input
node pairs $\\{(b_{j}^{+},b_{j}^{-})\\}$, leading to steady state pressures
$v$. Outputs are measured as pressure drops $\\{v(o_{i}^{+},o_{i}^{-})\\}$
across output node pairs $\\{(o_{i}^{+},o_{i}^{-})\\}$.

  3. 3.

Outputs are compared to the desired outputs
$\\{v_{d}(o_{i}^{+},o_{i}^{-})\\}$, and a feedback chemical is released in the
network by fixing the chemical currents
$\epsilon_{i}=\eta(v_{d}(o_{i}^{+},o_{i}^{-})-v(o_{i}^{+},o_{i}^{-}))$ across
the output node pairs $\\{(o_{i}^{+},o_{i}^{-})\\}$. The chemical
concentration reaches steady state $u$.

  4. 4.

The concentration drop $u(x,y)$ and pressure drop $v(x,y)$ are measured across
each weight $w_{xy}$, and the weights are updated according to $\Delta
w_{xy}=-\alpha u(x,y)v(x,y)$.

  5. 5.

This procedure, which corresponds to one step of gradient descent, is repeated
iteratively until convergence of the weights is achieved.

##  III The Iris data set

We train the flow network on a standard machine learning task: classifying
Iris flowers. The Iris data setmisc_iris_53  contains 150 examples of Iris
flowers belonging to three species (setosa, virginica and versicolor), and,
therefore, 50 examples for each category. Each example is of the form
$X=(X_{1},X_{2},X_{3},X_{4})$, composed of four features of the flower (petal
width, petal length, sepal width and sepal length, all measured in cm), and
comes with its assigned iris category, denoted $Y$. So an example would look
something like $X=(5.1,3.5,1.4,0.2)$ and $Y=\text{`setosa'}$. Given the four
features of the flower as input, the trained network should be able to tell
which species it belongs to.

Figure 2: Training and testing using the Iris data set. The Iris data set is
trained on a network with $12^{2}$ nodes and learning rate $\eta=10^{-4}$. The
weights are sampled from a truncated normal distribution with mean of 0.1,
standard deviation of 0.01 with a lower cutoff of 0.01 and upper cutoff of
0.19. We use the standard mean squared error (L2 norm) as the cost function.
[Top Left] At each training step, the network is shown an example and the mean
squared error is calculated between the network’s output and desired output,
shown as a blue dot. [Top Right] Accuracy is defined as the fraction of
correct predictions out of total testing examples. [Bottom Left] The initial
state of the network, with thickness of blue edges representing the
conductance. Red crosses denote input nodes; green crosses denote output
nodes. [Bottom Right] The change in weights between the initial state and the
final trained state of the network. Red denotes negative change, while blue
denotes positive change with thickness showing the magnitude of change.

We now detail how we do this. A flow network is constructed as follows:

  1. 1.

Generate a square lattice,

  2. 2.

Perturb the positions of the lattice with a step of length $\delta$ in any
random direction,

  3. 3.

every node is connected to its $d$ nearest neighbours 333Note that $d$ may not
be equal to degree of the node: given two neighbouring nodes $A$ and $B$, it
is possible that $B$ is in the $d$ nearest neighbours of $A$, while $A$ is not
in the $d$ nearest neighbors of $B$.. We choose $d=4$ for all our simulations
unless specified.

  4. 4.

Every edge of the network is assigned a conductance from a truncated normal
distribution.

  5. 5.

Four pairs of input nodes are chosen from this flow network, where the input
data (the normalised features of the iris) is given as external currents
across these four pairs of boundary nodes. Three pairs of nodes are chosen as
the output nodes such that every pair is composed of two neighbouring nodes.
For pairs of output nodes that are not neighboring nodes, the training error
decreased less smoothly. Once the network is trained, for a given input, the
set of potential drops across these node pairs should tell the category of
iris the input data corresponds to.

The network architecture remains fixed throughout the training-testing
process. Only the conductances of these weights are modified.

As for how the flow network interfaces with the Iris data set,

  1. 1.

The data set is divided into two subsets: one training set (used for training)
and one test set (used for testing). Each of these sets have 75 examples of
irises, 25 from each category.

  2. 2.

The data set is normalised. That is, for each example $X$ in the data set, and
for each feature $X_{i}$ of $X$; we set $X_{i}^{\rm
norm}=\lambda\cdot\dfrac{X_{i}-X_{i}^{\rm min}}{X_{i}^{\rm max}-X_{i}^{\rm
min}}$, where $X_{i}^{\rm max}$ and $X_{i}^{\rm min}$ are the minimum and
maximum values for that feature $X_{i}$ in the training set. We choose
$\lambda=5$ for all simulations.

While choosing the desired outputs we must keep in mind the fact that this
linear system may not be able to find a set of weights that give out the
desired output. In other words, we must choose desired outputs that are
physically attainable. We, therefore, implement the same technique as
described in Ref. Dillavou2021  to choose the desired output voltages for each
of the three Iris categories. For each category, the desired voltage is the
average, normalized input data. That is, each iris category has 25 examples of
four input features, each input feature is averaged out over 25 examples.
Finally, we obtain a four tuple of averaged input features for each iris
category. When this is given as input to the initial network, we aim to arrive
at an output voltage that corresponds to the average behavior of the input,
which is the desired voltage.

To conduct the training process, first the input data is given to the network
and the output is observed. If the output is not equal to the desired output
for that iris category, the feedback chemical is released at the output node
pairs by fixing the currents. The weights of the network are modified using
the learning rule mentioned above. This process is repeated consecutively for
all examples. Next, once the entire data set is exhausted, we say ’one epoch’
has passed. We train the network for multiple epochs. At the beginning of each
epoch, because the network has changed significantly, new desired voltages are
calculated. Therefore, each epoch has its own set of desired voltages.

To conduct the testing process, after the network is trained for multiple
epochs, we record how well it classifies unseen data from the test set. To be
specific, the test set has 25 examples per iris category. The iris features
from these test examples are given as input and the output voltage is compared
with the desired voltage. The desired voltage is calculated using the testing
data set. An example is then classified into that iris category, for which the
output voltage is closest to the desired output.

This training-testing procedure is implemented on a biophysical network.
Results are shown in Fig 2.

##  IV Link with Equilibrium Propagation and Coupled Learning

To readily see the link with our algorithm and EP, suppose that, in the second
phase, instead of injecting the chemical, we inject more of the main substance
at output nodes (through the currents
$\epsilon_{i}=\eta(v_{d}(o_{i}^{+},o_{i}^{-})-v(o_{i}^{+},o_{i}^{-}))$). We
can adapt the analysis of Sec. II to show that, instead of the chemical
concentration, $u$ now represents the pressure difference between the second
phase and the first phase (after and before injecting the currents
$\epsilon_{i}$ at output nodes). Indeed, denoting $v^{\rm free}$ and $v^{\rm
nudged}$ the node pressures at equilibrium in the first phase and second
phase, respectively, we have

$\displaystyle L\cdot v^{\rm free}$ $\displaystyle=I,$ (18) $\displaystyle
L\cdot v^{\rm nudged}$ $\displaystyle=I-E,$ (19)

where we recall that $E$ is the vector of currents at output nodes. Eq. (18)
is the same Laplace equation as (6), therefore $v^{\rm free}=v$. Moreover,
subtracting (19) from (18), we see that $v^{\rm nudged}-v^{\rm free}$
satisfies the same equation (8) as the chemical concentration $u$, that is
$L\cdot\left(v^{\rm nudged}-v^{\rm free}\right)=-E$. We conclude that
$u=v^{\rm nudged}-v^{\rm free}$. We thus recover the setting of equilibrium
propagation endtoend2020  with “free state” $v^{\rm free}=v$ and “nudged
state” $v^{\rm nudged}=v+u$. Coupled learning Stern2021  is also very closely
related, with the difference that nudged states are realized by imposing
boundary conditions on the pressures of output nodes, rather than on the
currents.

Without loss of generality, let us assume for convenience that $\alpha=-1$.
Our learning rule rewritten in terms of the free and nudged states is

$\displaystyle\Delta w_{xy}=$ $\displaystyle-v(x,y)u(x,y)$ (20)
$\displaystyle=$
$\displaystyle\frac{1}{2}v(x,y)^{2}+\frac{1}{2}u(x,y)^{2}-\frac{1}{2}\left(v(x,y)+u(x,y)\right)^{2}$
(21) $\displaystyle=$ $\displaystyle\frac{1}{2}\left(v^{\rm
free}(x,y)^{2}-v^{\rm nudged}(x,y)^{2}\right)+O(\eta^{2}),$ (22)

where $\eta$ is the nudge amplitude, i.e. the factor that scales the amplitude
of the currents injected in the second phase. Here we have used that $u$ is
proportional to the nudge amplitude, i.e. $u(x,y)=O(\eta)$. We have thus
recovered the learning rule of equilibrium propagation endtoend2020  and
coupled learning Stern2021  which, at order $1$ in $\eta$, is

$\Delta w_{xy}^{\rm EP/CL}=k\left(\left(v^{\rm
free}(x,y)\right)^{2}-\left(v^{\rm nudged}(x,y)\right)^{2}\right).$ (23)

In equilibrium propagation and coupled learning, the multiplicative factor in
front of the learning rule is $k=\frac{\text{learning
rate}}{2\times\text{nudge amplitude}}$ ; in our setting here, since
$\alpha=-1$, the nudge amplitude is the same as the learning rate, therefore
$k=\frac{1}{2}$.

To understand the discrepancy of $O(\eta^{2})$ between our learning rule and
the learning rule of EP and CL, let us rewrite $v^{\rm nudged}$ as $v^{\eta}$
to explicitly show the dependence of the nudged state on the nudge amplitude
$\eta$. In particular, $v^{0}=v^{\rm free}=v$. In our linear flow network, $u$
is a linear response of $\eta$ (specifically $u=-\eta L^{-1}\frac{\partial
C}{\partial v}$, see Eq. (8)). Combined with the relationship
$u=v^{\eta}-v^{0}$ shown above, this implies that $u=\eta\left.\frac{\partial
v^{\eta}}{\partial\eta}\right|_{\eta=0}$. Therefore:

$\displaystyle\Delta w_{xy}$ $\displaystyle=-v(x,y)u(x,y)$ (24)
$\displaystyle=-\eta\;v(x,y)\left.\frac{\partial
v^{\eta}(x,y)}{\partial\eta}\right|_{\eta=0}$ (25)
$\displaystyle=-\frac{\eta}{2}\frac{d}{d\eta}\bigg{|}_{\eta=0}\left[v^{\eta}(x,y)\right]^{2}.$
(26)

We recover the learning rule $\Delta w_{xy}^{\rm EP/CL}$ of Eq. (23) as a
finite difference approximation of Eq. (26) – hence the term $O(\eta^{2})$.

The advantage of our method over EP and CL is that, by using chemical
signaling, the system components can now differentiate between “activation”
and “feedback” signals based on their distinct chemical signatures. This
happens because the chemical $u$ encodes the same information as
$\frac{\partial v^{\eta}}{\partial\eta}$. Not only this eliminates the need to
store information about two separate phases, but also gives a way for exact
gradient computation.

On the other hand, one of the strengths of equilibrium propagation and coupled
learning is that they can be used for arbitrary physical systems driven by
physical equilibration: their learning rule can be written in terms of
derivatives of energy with respect to the trainable parametersScellier2017 ;
Stern2021 ; scellier2020deep , as follows:

$\Delta\mathbf{w}^{\rm EP/CL}=2k\bigg{(}\dfrac{\partial\mathcal{E}^{\rm
free}}{\partial\mathbf{w}}-\dfrac{\partial\mathcal{E}^{\rm
nudged}}{\partial\mathbf{w}}\bigg{)},$ (27)

where $\mathcal{E}^{\rm free}$ is the energy of the system in the free phase
and $\mathcal{E}^{\rm nudged}$ is the energy in the nudged phase. For example,
Eq 23 can be obtained from Eq 27 by taking $\mathcal{E}$ as power dissipation
function endtoend2020 ; Stern2021 . While the present work focuses on linear
physical systems, we will leave the study of our algorithm in nonlinear
systems for future work.

##  V Discussion

We present a simple model of a physical learning system that learns via
chemical signaling. In our system, the error between the desired behavior and
observed behavior at the output nodes is encoded in the form of a feedback
chemical signal. These signals travel across the network via diffusion with
the weights of the network updating in response to the concentration of the
feedback chemical and there is no need for two states, as there is in
equilibrium propagation and coupled learning. We also show that this learning
rule minimises a cost function via gradient descent even beyond the
infinitesimal nudge amplitude or learning rate limit.

Given the prevalence of backpropagation, we also compare our algorithm to
backpropagation. While there are many explicit differences between
backpropagation and our algorithm – mostly because artificial neural networks
are very different from physical flow networks – we can compare the basic
ideas between these algorithms. In our model the weight update rule is
proportional to two quantities: the “error term” $u(x,y)$ which tells how much
the pressure drop across the weight $w_{xy}$ must change, and the “activation
term” $v(x,y)$ which tells the existing pressure drop due to input. This is
similar to backpropagation where the weight update is proportional to the
presynaptic input and error in the postsynaptic output nielsenneural .
However, the difference between these algorithms is seen in the way error
information is communicated. In backpropagation, the error at the output layer
and the weights projecting onto this output layer determines the error at the
penultimate layer and so on nielsenneural . Therefore, the relationship
between the error values of two layers only depends on the local weight values
connecting them. In our model, once the error at output is known, the error at
the neighbouring nodes is determined by the steady state of the system, which
means that the relationship between their error depends on all the weights of
the network.

While our work here is mostly concerned with linear flow networks in the
absence of advection (see Appendix A for an exception to this), one can
explore how our algorithm can be extended to include it. Moreover, our
physical procedure (Sec. II) may also be applied to nonlinear systems, i.e.,
systems whose components have nonlinear characteristics. We will leave the
mathematical analysis and experimentation of these settings for future work.
We also must explore going beyond the quasistatic limit as time scales also
constrain biological learning systems. Efforts towards this goal have recently
been made in silico and in experiments using coupled learning Stern2021b .
Similar extensions can be implemented using our algorithm.

Nature may indeed be using similar signaling mechanisms that we have
elaborated on here. Cells use biochemical signals to structure themselves in
response to external conditions to optimize their functionality and, thus,
identity cellcognition . Slime mold, a tubular network-like single cell
organism uses chemical signals to modify its tube radii in response to food as
the external stimuli Alim2017 . While the particular chemical still remains
unknown, a recently proposed candidate is ATP Alim2021 . ATP is crucial for
the activity of myosin and, hence, the contractility of the actin
cytoskeleton. An increase in ATP would presumably enhance contractility. One
might conclude that enhanced contractility leads to stiffer cells as is found
in cells adherent to a substrate. However, for cells in suspension, inhibition
of myosin leads to stiffer cells due to accelerated depolymerization of actin
filaments Chan2015 . Perhaps suspended cell behavior is more relevant for the
tubular structures in slime model than adherent cells behavior. On other hand,
given such understanding, we expect similar artificial versions of this
signaling mechanism could be used for experimental realizations of our model
with its aforementioned extensions. For instance, an experimental system that
makes use of different mechanisms, such as different catalytic reactions on a
flexible sheet to drive shape changes in the presence of flows (see Appendix
A), is a distinct possibility Laskar2022 . Alternatively, perhaps one may
implement similar catalytic reactions in stiff sheets that fold. Incidentally,
supervised learning in stiff sheets, i.e. origami, has been explored
Stern2020supervised .

As for multi-cellular organisms, the brain presumably fine tunes the synaptic
strengths of billions of neurons to generate an optimal behavior. For this to
happen, feedback signals should not only carry precise credit information to
individual neurons but while doing so, they must not interfere with the
activation/feedforward signals Lillicrap2020 . How the brain does this is
still unknown and many models have been developed to explain this phenomenon.
For instance, some models invoke the use of error neurons
schwartz1993computational , while others assume a temporal segregation of
activation and feedback phases Stern2021 . Others propose a
compartmentalization of individual neurons to spatially separate information
as opposed to temporal segregation Ording2001 . Our learning mechanism is
similar to this last one. It avoids multiple phases by modifying a node to
store two kinds of information - an activation signal and a feedback signal.
The reason they do not interfere is because the system components can identify
them by their chemical signatures - a ubiquitous phenomenon in nature. We have
shown how the same network structure used to send an activation signal, can be
used to send precise gradient information to individual weights. Therefore,
our model optimises a cost function via gradient descent, something that deep
neural networks already do to achieve human like functionality imagerecog ;
alphago ; languagetrans ; speechrecog . In light of the reasons stated above,
we think our model may ultimately help neuroscientists understand credit
assignment mechanisms in the brain.

###### Acknowledgements.

The authors thank Sid Mishra, Sam Dillavou, Doug Durian, Andrea Liu, and Nachi
Stern for discussion. JMS acknowledges funding support from NSF-DMR-1832002
and an Isaac Newton Award from the DoD.

## References

  * (1) D. J. Sumpter, “The principles of collective animal behaviour,” Philosophical Transactions of the Royal Society B: Biological Sciences, vol. 361, no. 1465, pp. 5–22, 2006.
  * (2) G. Beauchamp, “Flocking in birds increases annual adult survival in a global analysis,” Oecologia, vol. 197, no. 2, pp. 387–394, 2021.
  * (3) M. Ballerini and et al., “Interaction ruling animal collective behavior depends on topological rather than metric distance: Evidence from a field study,” PNAS, vol. 105, 5 2008.
  * (4) N. J. Mlot, C. A. Tovey, and D. L. Hu, “Fire ants self-assemble into waterproof rafts to survive floods,” PNAS, vol. 108, pp. 7669–7673, 2011\.
  * (5) B. J. Adams, L. M. Hooper-Bui, R. M. Strecker, and D. M. O’Brien, “Raft formation by the red imported fire ant solenopsis invicta,” J. Insect. Sci., vol. 11, 2011.
  * (6) R. J. Wagner and F. J. Vernerey, “Computational exploration of treadmilling and protrusion growth observed in fire ant rafts,” PLoS Comp. Biol., vol. 18, p. e1009869, 2022.
  * (7) E. B. Issa, C. F. Cadieu, and J. J. Dicarlo, “Neural dynamics at successive stages of the ventral visual stream are consistent with hierarchical error signals,” eLife, vol. 7, no. 1, pp. 1–24, 2018.
  * (8) N. Kriegeskorte, “Deep Neural Networks: A New Framework for Modeling Biological Vision and Brain Information Processing,” Annual Review of Vision Science, vol. 1, no. 1, pp. 417–446, 2015.
  * (9) D. Zipser and R. Andersen, “A back-propagation programmed network that simulates response properties of a subset of posterior parietal neurons,” Nature, vol. 336, pp. 403–405, 1988.
  * (10) P. R. Roelfsema and A. Holtmaat, “Control of synaptic plasticity in deep cortical networks,” Nature Reviews Neuroscience, vol. 19, no. 3, pp. 166–180, 2018.
  * (11) M. A. Nielsen, “Neural networks and deep learning,” 2018.
  * (12) G. R. Yang and X. J. Wang, “Artificial Neural Networks for Neuroscientists: A Primer,” Neuron, vol. 107, no. 6, pp. 1048–1070, 2020.
  * (13) D. E. Rumelhart, G. E. Hinton, and R. J. Williams, “Learning Representations by Back-propagating Errors,” Nature, vol. 323, no. 6088, pp. 533–536, 1986.
  * (14) T. P. Lillicrap, A. Santoro, L. Marris, C. J. Akerman, and G. Hinton, “Backpropagation and the brain,” Nature Reviews Neuroscience, vol. 21, no. 6, pp. 335–346, 2020.
  * (15) J. Sacramento, R. Ponte Costa, Y. Bengio, and W. Senn, “Dendritic cortical microcircuits approximate the backpropagation algorithm,” Advances in neural information processing systems, vol. 31, 2018.
  * (16) I. Pozzi, S. Bohté, and P. Roelfsema, “A Biologically Plausible Learning Rule for Deep Learning in the Brain,” 2018.
  * (17) B. A. Richards and T. P. Lillicrap, “Dendritic solutions to the credit assignment problem,” Current Opinion in Neurobiology, vol. 54, pp. 28–36, 2019.
  * (18) J. C. Whittington and R. Bogacz, “Theories of error back-propagation in the brain,” Trends in Cognitive Sciences, vol. 23, no. 3, pp. 235–250, 2019\.
  * (19) A. Payeur, J. Guerguiev, F. Zenke, B. A. Richards, and R. Naud, “Burst-dependent synaptic plasticity can coordinate learning in hierarchical circuits,” Nature neuroscience, vol. 24, no. 7, pp. 1010–1019, 2021.
  * (20) By local we not only mean in terms of metric distance.
  * (21) J. J. Hopfield, “Neurons with graded response have collective computational properties like those of two-state neurons,” Proceedings of the National Academy of Sciences of the United States of America, vol. 81, no. 10 I, pp. 3088–3092, 1984.
  * (22) D. Marković, A. Mizrahi, D. Querlioz, and J. Grollier, “Physics for neuromorphic computing,” Nature Reviews Physics, vol. 2, no. 9, pp. 499–510, 2020.
  * (23) J. D. Kendall, R. D. Pantone, K. Manickavasagam, Y. Bengio, and B. Scellier, “Training end-to-end analog neural networks with equilibrium propagation,” CoRR, vol. abs/2006.01981, 2020.
  * (24) B. Scellier, “A deep learning theory for neural networks grounded in physics,” PhD thesis, Université de Montréal, 2021.
  * (25) M. Stern, D. Hexner, J. W. Rocks, and A. J. Liu, “Supervised Learning in Physical Networks: From Machine Learning to Learning Machines,” Physical Review X, vol. 11, no. 2, p. 21045, 2021.
  * (26) L. G. Wright, T. Onodera, M. M. Stein, T. Wang, D. T. Schachter, Z. Hu, and P. L. McMahon, “Deep physical neural networks trained with backpropagation,” Nature, vol. 601, no. 7894, pp. 549–555, 2022.
  * (27) B. Scellier and Y. Bengio, “Equilibrium propagation: Bridging the gap between energy-based models and backpropagation,” Frontiers in Computational Neuroscience, vol. 11, no. May, 2017.
  * (28) S. Dillavou, M. Stern, A. J. Liu, and D. J. Durian, “Demonstration of Decentralized, Physics-Driven Learning,” 2021.
  * (29) F. Patino-Ramirez, A. Boussard, C. Arson, and A. Dussutour, “Substrate composition directs slime molds behaviour,” Scientific Reports, vol. 9, p. 15444, 2019.
  * (30) A. Boussard, A. Fessel, C. Oettmeier, L. Briard, H. G. Döbereiner, and A. Dussutour, “Adaptive behaviour and learning in slime moulds: The role of oscillations,” Philosophical Transactions of the Royal Society B: Biological Sciences, vol. 376, no. 1820, 2021.
  * (31) H. Yamada, A. Toth, and T. Nakagaki, “Intelligence: Maze-solving by an amoeboid organism,” Nature, vol. 407, pp. 470–470, 09 2000.
  * (32) A. Tero, S. Takagi, T. Saigusa, K. Ito, D. P. Bebber, M. D. Fricker, K. Yumiki, R. Kobayashi, and T. Nakagaki, “Rules for biologically inspired adaptive network design,” Science, vol. 327, no. 5964, pp. 439–442, 2010.
  * (33) A. Tero, K. Yumiki, R. Kobayashi, T. Saigusa, and T. Nakagaki, “Flow-network adaptation in Physarum amoebae,” Theory in Biosciences, vol. 127, no. 2, pp. 89–94, 2008.
  * (34) K. Alim, N. Andrew, A. Pringle, and M. P. Brenner, “Mechanism of signal propagation in Physarum polycephalum,” Proceedings of the National Academy of Sciences of the United States of America, vol. 114, no. 20, pp. 5136–5141, 2017.
  * (35) M. Kramar and K. Alim, “Encoding memory in tube diameter hierarchy of living flow network,” PNAS, vol. 118, no. 10, p. e2007815118, 2021.
  * (36) We acknowledge Nachi Stern for suggesting the use of the word modality.
  * (37) R. Fisher, “Iris.” UCI Machine Learning Repository, 1988.
  * (38) Note that $d$ may not be equal to degree of the node: given two neighbouring nodes $A$ and $B$, it is possible that $B$ is in the $d$ nearest neighbours of $A$, while $A$ is not in the $d$ nearest neighbors of $B$.
  * (39) M. Stern, S. Dillavou, M. Z. Misken, D. J. Durian, and A. J. Liu, “Physical learning beyond the quasistatic limit,” arXiv:2112.11399, 2021.
  * (40) A. Koseska and P. I. Bastiaens, “Cell signaling as a cognitive process,” The EMBO Journal, vol. 36, no. 5, pp. 568–582, 2017.
  * (41) C. J. Chan and et al., “Myosin ii activity softens cells in suspension,” Biophysical Journal, vol. 108, no. 8, pp. 1856–1869, 2015.
  * (42) A. Laskar, R. K. Manna, O. E. Shklyaev, and A. C. Balazs, “Computer modeling reveals modalities to actuate mutable, active matter,” Nature Communications, vol. 13, no. 1, pp. 1–4, 2022.
  * (43) M. Stern, C. Arinze, L. Perez, S. E. Palmer, and A. Murugan, “Supervised learning through physical changes in a mechanical system,” Proceedings of the National Academy of Sciences, vol. 117, no. 26, pp. 14843–14850, 2020\.
  * (44) E. L. Schwartz, Computational neuroscience.  Mit Press, 1993.
  * (45) K. P. Ording and A. Peter, “Supervised and Unsupervised Learning with Two Sites of Synaptic Integration,” Journal of Computational Neuroscience, vol. 11, pp. 207–215, 2001.
  * (46) K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770–778, 2016.
  * (47) D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, Y. Chen, T. Lillicrap, F. Hui, L. Sifre, G. Driessche, T. Graepel, and D. Hassabis, “Mastering the game of go without human knowledge,” Nature, vol. 550, pp. 354–359, 10 2017.
  * (48) A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. u. Kaiser, and I. Polosukhin, “Attention is all you need,” in Advances in Neural Information Processing Systems (I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, eds.), vol. 30, Curran Associates, Inc., 2017.
  * (49) A. Y. Hannun, C. Case, J. Casper, B. Catanzaro, G. Diamos, E. Elsen, R. Prenger, S. Satheesh, S. Sengupta, A. Coates, and A. Y. Ng, “Deep speech: Scaling up end-to-end speech recognition,” CoRR, vol. abs/1412.5567, 2014\.
  * (50) For simplicity we assume that the chemical has negligible diffusion and the only way it can spread is via the network currents.
  * (51) The current flows into and out of the network through boundary nodes.
  * (52) This helps the potentials at the output node to converge nicely at the desired potentials. If this delay is not introduced, the output potential oscillates about the desired potential. Moreover, the delay helps in avoiding the buildup of excess chemical in the network.

##  Appendix A Flow version of the chemical signaling algorithm

Here we present a model where the chemical signal spreads not via diffusion
but via advection. To begin, the pressure at a node depends on the resistance
to flow downstream. Therefore, to alter the pressure at a node, we must change
the conductance of pipes downstream. Let us say that there is an output node
pressure we wish to decrease. We will simply release a chemical at that node
which gets carried by the current downstream. This chemical is such that, when
it is flowing through a pipe, it increases the conductance of the pipe (e.g.
making it thicker). This increase in conductance decreases the resistance to
flow which in turn decreases the pressure at the output node. Similarly, when
we wish to increase the output node pressure, we must release a different kind
of chemical which decreases the conductance of the pipes (e.g. making it
thinner). Using this we can tune the network to output desired voltages. In
fact, we observe numerically system optimises a cost function-but not
necessarily via gradient descent.

To implement the above idea as a tuning process, consider

  1. 1.

The input pressures $\\{p_{i}\\}$ is applied at output nodes. A supervisor
checks the output pressures $\\{v\\}$ at output nodes and compares them to
desired output pressures $\\{{v}_{d}\\}$ .

  2. 2.

There are two kinds of chemicals, $s_{+}$ and $s_{-}$. $s_{+}$ increases the
conductance of the pipe when it passes through it, and vice versa for $s_{-}$.
We assume that the output nodes release a chemical whose amount is
proportional to the difference between the present output pressures and
desired output pressures. At $t=0$ for some output node
$a,~{}v(a)\neq{v}_{d}(a)$, then

$\displaystyle~{}~{}if~{}v(a)>{v}_{d}(a)\implies
s_{+}(a)=\lambda(v(a)-{v}_{d}(a))\,\,\,{\rm at}\,\,\,t=0,$ (28) $\displaystyle
elif~{}v(a)<{v}_{d}(a)\implies s_{-}(a)=\lambda({v}_{d}(a)-v(a))\,\,\,{\rm
at}\,\,\,t=0,$ (29)

Where $\lambda$ is the factor that controls the chemical response given by the
node to the difference in pressures. Moreover, $s_{+}(a)$ denotes amount of
chemical (e.g. no of molecules) at node“a” .

  3. 3.

This chemical is carried by the current in the network. Therefore, in the next
time step the chemical flows to the neighbouring nodes of $a$ that are
downstream to $a$444For simplicity we assume that the chemical has negligible
diffusion and the only way it can spread is via the network currents. We call
all such downstream neighbours of $a$ as $\mathcal{D}(a)$. Then for all
$b\in\mathcal{D}(a):$

$s_{+}(b,t+1)=s_{+}(a,t)\times\dfrac{i(b,a)}{\sum_{x\in\mathcal{D}(a)}i(x,a)}$
(30) $+{\rm(incoming~{}chemical~{}from~{}other~{}nodes)}$

where $i(x,a)$ represents the current from $a$ to $x$. Note that all the
chemical initially present at $a$ flows downstream after one time step.

  4. 4.

Using the above equation, an N $\times$ N array $\hat{S}_{+}$ is generated,
where each entry $i,j$ denotes the amount of chemical passing through the pipe
$\\{i,j\\}$ at step $t$ $\xrightarrow{}$ $t+1$. Let $\hat{W}$ denote the
conductance matrix of the graph, where each entry $\\{i,j\\}$ denotes the
conductance of that pipe. Then

$\displaystyle\hat{W}(t+1)=\hat{W}(t)+\xi(\hat{S}_{+}-\hat{S}_{-}),$ (31)

$\xi$ controls the response of the pipe to the passing chemical.

  5. 5.

The new potentials are calculated on the interior vertices using
$\hat{W}(t+1)$. Again, the supervisor checks if $v(a)=v_{d}(a)$. The chemical
takes some time to reach the boundary nodes, where it drains out of the
network 555The current flows into and out of the network through boundary
nodes. Therefore, the total change in potential due to the chemical released
at the output nodes is observed after some amount of time. Therefore, we
introduce a time delay $\tau$ before releasing the chemical once again 666This
helps the potentials at the output node to converge nicely at the desired
potentials. If this delay is not introduced, the output potential oscillates
about the desired potential. Moreover, the delay helps in avoiding the buildup
of excess chemical in the network.

  6. 6.

This process is repeated iteratively.


# GANTEE: Generative Adversatial Network for Taxonomy Entering Evaluation

Zhouhong Gu1,4, Sihang Jiang1, Jingping Liu2, Yanghua Xiao1,3*, Hongwei Feng1,
Zhixu Li1,
Jiaqing Liang4, Jian Zhong5 Corresponding Authors

###### Abstract

Taxonomy is formulated as directed acyclic concepts graphs or trees that
support many downstream tasks. Many new coming concepts need to be added to an
existing taxonomy. The traditional taxonomy expansion task aims only at
finding the best position for new coming concepts in the existing taxonomy.
However, they have two drawbacks when being applied to the real-scenarios. The
previous methods suffer from low-efficiency since they waste much time when
most of the new coming concepts are indeed noisy concepts. They also suffer
from low-effectiveness since they collect training samples only from the
existing taxonomy, which limits the ability of the model to mine more
hypernym-hyponym relationships among real concepts. This paper proposes a
pluggable framework called Generative Adversarial Network for Taxonomy
Entering Evaluation (GANTEE) to alleviate these drawbacks. A generative
adversarial network is designed in this framework by discriminative models to
alleviate the first drawback and the generative model to alleviate the second
drawback. Two discriminators are used in GANTEE to provide long-term and
short-term rewards, respectively. Moreover, to further improve the efficiency,
pre-trained language models are used to retrieve the representation of the
concepts quickly. The experiments on three real-world large-scale datasets
with two different languages show that GANTEE improves the performance of the
existing taxonomy expansion methods in both effectiveness and efficiency.

## Introduction

Taxonomy is formulated as directed acyclic graphs or trees, which consist of
hyponym-hypernym relations between concepts. One concept is a hypernym of
another concept if the meaning of the former covers the latter (Sang 2007). A
well-constructed taxonomy assist various downstream tasks, including web
content tagging (Liu et al. 2020, 2019; Peng et al. 2019), personalized
recommendation (Karamanolakis, Ma, and Dong 2020; Huang et al. 2019), query
understanding (Yang, Zhang, and Han 2020) and so on.

Manually maintaining a taxonomy is labor-intensive and time-consuming. For
example, millions of new concepts are expected to be added to the taxonomy of
one of the largest shopping platforms in the world each month (Jiang et al.
2019). So the task of automated taxonomy expansion is proposed (Jurgens and
Pilehvar 2016), which aims to automatically assign an existing concept (anchor
concept) as a hypernym concept to the newly input concept (query concept).
These models successfully save much time from labor annotation in taxonomy
maintenance. These methods predict the hypernym-hyponym relationships mainly
based on the representation similarity, so they sample the training data based
on the existing taxonomy to learn good representations for each concept.

However, we argue that these methods (Yu et al. 2020; Wang et al. 2022; Cheng
et al. 2022; Shen et al. 2020; Mao et al. 2020; Wang et al. 2021; Zhang et al.
2021) have two drawbacks when being applied to real applications. First, these
methods suffer from low effectiveness in real applications due to limited
ability to represent the semantics of concepts. Only sampling from existing
taxonomy provides limited data to train representations for zero-shot
concepts, where thousands times queries of the number of concepts in existing
taxonomy are all unseen to the models (Cheng et al. 2022). Second, these
methods suffer from low efficiency in real applications because most of the
query concepts are noisy. For instance, in a leading ordering take-outs online
platform, only thousands of concepts out of billions of queries are finally
added to their taxonomy (Cheng et al. 2022). Previous methods ignore the noisy
concepts and waste much time finding the anchor concept for noisy query
concepts.

Figure 1: An example of the GANTEE framework. This framework is implemented as
a plugin before taxonomy expansion. The demand for generating high-quality
data and taxonomy entering evaluation is formulated as a generative
adversarial network in GANTEE.

In this paper, we propose a pluggable framework called Generative Adversarial
Network for Taxonomy Enterance Evaluation (GANTEE) to boost both the
effectiveness and efficiency of the taxonomy expansion methods in real-
scenarios as is shown in Figure 1. To improve the effectiveness, GANTEE
proposes a generative model to generate more high-quality training data, which
are required to train the high-quality representation for taxonomy expansion.
To improve efficiency, GANTEE introduces a new task called taxonomy entering
evaluation, which removes many noisy query concepts before finding the
suitable anchor concept for them. Intuitively, the generative model and the
taxonomy entering evaluation model are two adversarial models which can
improve each other. The generative model produces fake samples similar to real
ones to confuse the discriminative model. The taxonomy entering evaluation
model learns to generate high-quality samples. Therefore, these two tasks can
be formulated as a generative adversarial task (Goodfellow et al. 2014) to
improve their performance further.

Specifically, to improve efficiency, the taxonomy entering evaluation model is
expected to be more lightweight than the taxonomy expansion model. We
introduce two mechanisms to ensure the efficiency of the taxonomy entering
evaluation model. First, instead of determining where to extend the query
concept, GANTEE introduces two more manageable tasks _“isA Concept Access”_
and _“isA Query Access”_ to determine whether the query concept is a concept
and whether the query concept should be added to the taxonomy. Second, instead
of training a new representation for emerging query concepts, we use pre-
trained language models (PLMs) to directly obtain a representation of each
concept based on the textual features of the concept. Although PLMs have
limited ability in representing the fine-grained semantics based on conceptual
text (Lauscher et al. 2019), the experimental results verify that PLMs are
suitable to generate representation in _“isA Concept Access”_ and _“isA Query
Access”_ task.

In the experiments, we benchmark the taxonomy entering evaluation task on
three real-world taxonomies in two languages, English and Chinese. We reached
the new SOTA in the experiments by improving all the metrics in only a third
of the time of other methods in the prediction stage. Finally, extensive
experiments have been conducted to study how the parameters affect the result
of GANTEE, and provide an effective tuning scheme for the following
researchers who will use our method in the future.

#### Contribution.

To summarize, our major contributions include: (1) We propose a more
manageable task called taxonomy entering evaluation which judges whether a
query concept should be added to an existing taxonomy efficiently; (2) We
propose a novel, effective method called GANTEE to generate confusing negative
and fidelity positive data boosts the performance and efficiency for both
traditional taxonomy expansion tasks and taxonomy entering evaluation tasks.
(3) Extensive experiments have been conducted to verify the superiority of
GANTEE on three datasets in two languages. We also propose an effective tuning
method based on the experiment results.

## Problem Formalization

In this section, we first define the preliminaries used in this paper, then
formally define the taxonomy entering evaluation task and traditional taxonomy
expansion problems.

### Preliminary and Problem Definition

######  Preliminary 1.

(Taxonomy and Anchor Concept.) A taxonomy
$\mathcal{T}=(\mathcal{A},\mathcal{E})$ is a directed acyclic graph. Each node
$a\in\mathcal{A}$ denotes an anchor concept and each directed edge $\langle
a_{p},a_{c}\rangle\in\mathcal{E}$ represents the hyponymy relation between the
parent (hypernym) concept $a_{p}$ and the child (hyponym) concept $a_{c}$.

######  Preliminary 2.

(Query Concept.) Query concept is the concept prepared to be added to the
existing taxonomy. The set of query concepts is represented as
$\mathcal{Q}=\\{q_{1},q_{2},\cdots,q_{m}\\}$.

######  Problem 1.

Taxonomy entering Evaluation: In taxonomy entering evaluation task, the input
is (1) an existing taxonomy
$\mathcal{T}^{0}=(\mathcal{A}^{0},\mathcal{E}^{0})$, (2) a set of query
concepts $\mathcal{Q}$. The output of entering evaluation is a set of clean
query concepts $\mathcal{Q}^{*}$, which is formalized into the following
formula:

$\mathcal{Q}^{*}=\mathcal{Q},\ \forall q\in\mathcal{Q}^{*}\ s.t.\
P(q|\mathcal{T}^{0};\Theta_{2})>\gamma.$ (1)

$\Theta_{2}$ denotes the parameters, and $\gamma$ is a given threshold.

######  Problem 2.

Taxonomy Expansion: In taxonomy expansion task, the input is (1) an existing
taxonomy $\mathcal{T}^{0}=(\mathcal{A}^{0},\mathcal{E}^{0})$, (2) a set of
clean query concepts $\mathcal{Q}^{*}$. The output of the taxonomy expansion
is a best-expanded taxonomy $\mathcal{T}^{*}$ with all the clean query
concepts added in:

$\displaystyle\mathcal{T}^{*}$
$\displaystyle=\underset{\mathcal{T}}{\arg\max}\mathbf{P}(\mathcal{T}\mid\mathcal{T}^{0};\Theta)$
(2)
$\displaystyle=\underset{\mathcal{T}}{\arg\max}\sum_{i=1}^{\left|\mathcal{A}\cup\mathcal{Q}^{*}\right|}\log\mathbf{P}\left(q_{i}\mid
p\left(q_{i}\right);\Theta\right),$

where $\Theta$ denotes model parameters, and $p(q_{i})$ denotes the parent of
$q_{i}$ in the taxonomy $\mathcal{T}$.

## Framework of GANTEE

GANTEE consists of a generator $G$ and two discriminators, which are hyper
discriminator $D_{H}$ and rollout discriminator $D_{R}$. $G$ takes an anchor
concept and a label that generates positive or negative samples as inputs and
generates the corresponding query concept. $D_{H}$ determines whether the
given anchor concept is suitable for the generated query concept based on the
given label, and $D_{R}$ determines whether the generated text is a concept.

Specifically, when a new query concept is given in the predicting stage,
GANTEE first determines if it is a concept by $D_{R}$. Then GANTEE determines
whether the given concept has a hypernym-hyponym relation to the root concept
by $D_{H}$. Finally, GANTEE output the confidence score of if the given query
concept is suitable for this taxonomy.

Figure 2: The framework of GANTEE. The generator of the GANTEE is on the left,
and duel discriminator is on the right.

### The Generative Model for Query Concept Generating

We use Transformer (Vaswani et al. 2017) as the generative model. Transformer
maps the input sequence $x_{1},\dots,x_{n}$ into a sequence of hidden states
$h_{1},\dots,h_{n}$. Specifically, a Transformer block consists of stacked
self-attention layers with residual connections. Each self-attention layer
receives $n$ embeddings $\\{h^{(l)}_{i}\\}^{n}_{i=1}$ corresponding to unique
input tokens, and outputs $n$ hidden states $\\{h^{(l+1)}_{i}\\}^{n}_{i=1}$.
The $i$-th token is mapped via linear transformations to a key $k_{i}$, query
$q_{i}$, and value $v_{i}$. The $i$-th output of the self-attention layer is
given by weighting the values $v_{j}$ by the normalized dot product between
the query $q_{i}$ and other keys $k_{j}$:

$h_{i}=\sum^{n}_{j=1}softmax(\langle
q_{i},k_{j^{\prime}}\rangle^{n}_{j^{\prime}=1})_{j}\cdot v_{j}.$ (3)

This allows the layer to assign “credit” by implicitly forming state-return
associations via similarity of the query and key vectors (maximizing the dot
product). It is worth noticing that most of the Transformer variants, such as
BART (Lewis et al. 2019) or XLNet (Yang et al. 2019), and the RNN variants,
such as the Gated Recurrent Unit(GRU) (Cho et al. 2014) or Long-Short Term
Memory network(LSTM) (Hochreiter and Schmidhuber 1997), can be used as a
generator in GANTEE.

We use GPT-2 (Radford et al. 2019) in this paper to give the best experimental
results. GPT-2 modifies the transformer architecture with a causal self-
attention mask to enable auto-regressive generation. It is one of the most
famous auto-regressive models, which best suits the fake query generation
task.

As an auto-regressive generative model, GPT-2 could generate sequences based
on all input sequences. So we formulate the input and the output of the GPT-2
in the following format:

$GPT2(l_{i}\oplus a_{i})=l_{i}\oplus a_{i}\oplus q_{i}.$ (4)

$GPT2$ denotes the GPT-2 model, $l_{i}$ denotes the given label, $a_{i}$
denotes the text of the given anchor concept, $q_{i}$ denotes the text of the
given query concept, and $\oplus$ denotes the concatenation of the tokens.

### The Rollout Discriminative Model for Short Term Reward in Generating

The rollout discriminative model is used to judge whether the generated text
is a concept before the generating process finish. Deep discriminative models
such as deep neural network(DNN), convolutional neural network(CNN), and
recurrent convolutional neural network(RCNN) have shown their effectiveness in
complicated sequence classification tasks (Guo et al. 2018; Yu et al. 2017;
Nie, Narodytska, and Patel 2018). In this paper, we choose LSTM (Hochreiter
and Schmidhuber 1997) as our rollout discriminator. Since previous study (Guo
et al. 2018) find that severe gradient vanishing occurs when the discriminator
is too strict, LSTM is a lightweight model which is easy to do the training
and will not provide too strict discriminative ability. LSTM will take in the
input embedding $x_{1},\dots,x_{t}$ and use purpose-built memory cells to
calculate the hidden state for each step $h_{1},\cdots,h_{t}$.

$\displaystyle\\{h_{1},\cdots,h_{t}\\}=lstm(x_{1},\cdots,x_{t}),$ (5)

where $lstm$ denotes the model of LSTM. We take the final hidden state $h_{t}$
and inject it into a linear layer to calculate the reward of the generated
text:

$r_{r}=W_{r}\cdot h_{t}+b_{r},$ (6)

where $W_{r}$ and $b_{r}$ are the parameters in a linear layer, the $r_{r}$ is
the confidence of whether the generated text is a concept.

### The Hyper Discriminative Model for Long Term Reward in Generating

The hyper discriminative model is used to judge whether the generated concept
has a hypernym relation to the given anchor concept after the generating
process finish based on the given label. Such discriminative models offer a
long-term reward for the generating process to guide the direction of the
generation better. The existing models for taxonomy expansion can be used as
the hyper discriminative model, which can detect whether there is a hypernym
relation between two concepts.

However, these models rely heavily on the vector representation of the
concepts, many studies such as STEAM (Yu et al. 2020) or HiExpan (Shen et al.
2018) use external information to get better representations for the concepts,
and that would be time-consuming for the generating process since each time
the generative model produce a new concept, it will take time to get its
detailed external information and get its vector representation.

Instead, we use Bert (Devlin et al. 2018) to retrieve the representation of
concepts since it shows its ability in Dependency Judgement task (Shi and
Demberg 2019), which is also good at understanding the hypernym (hyponym)
relation between two concepts. We concatenate the label representation and the
position embedding proposed by the TaxoExpan (Shen et al. 2020) to the Bert
representation and put them into a linear layer to get the final predicted
result.

Specifically, we get the representation of the concept by Bert in the
following format:

$\displaystyle x_{a}=Bert(x^{c_{0}}_{1},\dots,x^{c_{0}}_{t})[1],$ (7)
$\displaystyle x_{q}=Bert(x_{1},\dots,x_{t})[1],$ $\displaystyle
l=EMB(positive)\text{ or }EMB(negative).$

$Bert$ denotes the BERT model, $EMB$ denotes the embedding model, and
$positive$ or $negative$ denotes the input to the embedding model.

Then, we concatenate the label representation and position embedding to the
representation of the anchor concept and the query concept and put them into a
linear layer:

$r_{h}=W_{h}\cdot(l+x_{a}+p_{a}+x_{q}+p_{q})+b_{h}$ (8)

Where $W_{h}$ and $b_{h}$ are the parameters in a linear layer, $p_{a}$ and
$p_{q}$ are the position embedding. The $r_{h}$ is the probability of the
hypernym relation between the generated query concept and the anchor concept.

### Training for GANTEE

GANTEE uses a Generative Adversarial Network (GAN) model to combine taxonomy
entering evaluation and high-quality training samples generating. It needs a
generative model to produce conceptual text and use discriminative models to
offer supervised signals to the generative model. However, naive GAN is used
for continuous data, not discrete tokens. The previous researchers (Bachman
and Precup 2015; Bahdanau et al. 2016; Yu et al. 2017) propose considering the
text generation procedure as a sequential decision-making process. The
objective function of such generative models is formulated to generate a
sequence from the start state $s_{0}$ to maximize its expected end reward via
policy gradient algorithms (Sutton et al. 1999):

$\displaystyle J(\theta)$ $\displaystyle=\mathbb{E}[R_{T}|s_{0}=l\oplus
a;\theta]$ (9) $\displaystyle=\sum_{y_{1}\in Y}G(y_{1}|s_{0}=l\oplus a)\cdot
Q^{G}_{D}(s_{0}=l\oplus a,y_{1}),$

where $J(\theta)$ is the object function, $R_{T}$ is the reward for a complete
concept that has hypernym relation to the given anchor concept $a$ and label
$l$. Note that the reward is from both the hyper discriminator $D_{H}$ and
rollout discriminator $D_{R}$. $G$ is the generative model, and
$Q^{G}_{D}(s,a)$ is the action-value function of a sequence, which is
calculated in the following format:

$Q^{G}_{D}(a=y_{t},s=Y_{1:t-1},s_{0})=D(s_{0},Y_{1:t-1})$ (10)

Since the reward getting from an unfinished sequence often have a large bias
over the finished one, the Monte Carlo search is used to sample the unknown
last $T-t$ tokens (Yu et al. 2017):

$\\{Y^{1}_{1:T},\dots,Y^{N}_{1:T}\\}=MC^{G}\left(Y_{1:t};N\right)$ (11)

We use rollout discriminator $D_{R}$ to calculate the expected reward based on
Monte Carlo search during the generative process for short-term reward and use
hyper discriminator $D_{H}$ to calculate the reward when the generating is
done for long-term reward. The action-value function is transformed into the
following format:

$\displaystyle Q^{G}_{D}(a=y_{t},s=Y_{1:t-1},s_{0})=$ (12)
$\displaystyle\begin{cases}\frac{1}{N}\sum^{N}_{n=1}D_{R}(s_{0},Y_{1:t-1}),Y^{n}_{1:T}\in
MC^{G}\left(Y_{1:t};N\right)&\text{for }t<T\\\ D_{H}(Y_{1:t},s_{0})&\text{for
}t=T\end{cases}$

Once we have a set of more realistic generated sequences, we will re-train the
discriminator model as follows:

$\min_{D}-\mathbb{E}_{Y\sim p_{data}}[\log D(Y)]-\mathbb{E}_{Y\sim
G}[log(1-D(Y))]$ (13)

Specifically, we pre-train the generator and the discriminator before the
adversarial process begins. After the pre-training stage, the generator and
discriminator have trained alternatively. As the generator is updated via some
training epochs, the discriminators need to be re-trained periodically to keep
a good pace with the generator.

When training the discriminator, positive samples are sampled from the
existing taxonomy $\mathcal{T}^{0}$ based on the hypernym relation
$\mathcal{R}$. In contrast, negative samples are the fake samples generated
from our generator. To ensure the learning process is doing well, we use both
generated samples and pure noisy samples as the negative query concepts to
inject into the training process. The number of negative query concepts we use
is the same as the size of positive query concepts.

## Experiments

Method | MAG-CS (10k-level) | MAG-FoS (100k-level) | CN-Probase (1000k-level)
---|---|---|---
MR | MRR@10 | hit@5 | time | MR | MRR@100 | time | MR | MRR@1k | time
Close-Position | 2.3k | 0.137 | 0.023 | - | 23.2k | 0.128 | - | 157.5k | 0.159 | -
Close-Neighbor | 1.8k | 0.153 | 0.043 | - | 15.6k | 0.146 | - | 95.5k | 0.188 | -
BERT+MLP | 2.5k | 0.001 | 0.002 | 116.0 s | 25.6k | 0.023 | 5.4k s | 159.1k | 0.143 | 42.5k s
TaxoExpan | 1.3k | 0.319 | 0.157 | 471.4 s | 3.7k | 0.305 | 25.2k s | - | - | (200k+) s
TaxoExpan | 1.2k | 0.360 | 0.193 | 152.8 s | 2.5k | 0.382 | 6.1k s | 6.6k | 0.319 | 67.4k s
\+ GANTEE

Table 1: Overall Performance on Taxonomy Expansion.

There is an open question that whether the generated positive samples should
be treated as positive training samples or negative training samples. Since
the purpose of GAN is to train a generator that output a distribution similar
to the real data, if all the data generated by the generator are regarded as
negative samples, it will beyond the discriminative ability of the classifier
in downstream applications. In this paper, we treat them as negative training
samples in the first epoch of adversarial training and as positive training
samples in the subsequent epochs of adversarial training.

### Experimental Setup

#### Dataset

We study the performance of GANTEE on three large-scale real-world taxonomies:

  * •

Microsoft Academic Graph on Field-of-Study (MAG-FoS): This taxonomy (Sinha et
al. 2015) consists of public Field-of-Study Taxonomy(FoS). It contains over
0.6 million scientific concepts and more than 0.7 million taxonomic relations
in English.

  * •

Microsoft Academic Graph on Computer-Science (MAG-CS): Following the work of
TaxoExpan (Shen et al. 2020), we construct MAG-CS based on the sub-graph of
MAG-FoS related to the “Computer Science” domain.

  * •

CN-Probase: This is an open chinese general concept taxonomy CN-Probase (Chen
et al. 2019). It contains over 300 thousand concepts and more than 30 million
“isA” relations between concepts and entities in Chinese.

Notice that there are many outlier concepts in the taxonomy, so we remove all
concepts that do not relate to the original taxonomy. To ensure the validity
and test data won’t be trained, we randomly mask 20% of leaf concepts (along
with their relations) for validation and testing. Furthermore, we add noisy
query concepts as 60% size of leaf concepts into the validation and test set
to conduct the experiments as in the real-scenarios.

#### Evaluation Metric

  * •

Mean Rank (MR): measures the average rank position of a query concept’s true
parent among all candidates.

  * •

Mean Reciprocal Rank@k (MRR@k): calculates the reciprocal rank of a query
concept’s true parent. We use a scaled version of MRR in the below equation:

$MRR=\frac{1}{|C|}\sum_{c\in C}\frac{1}{|parent(c)|}\sum_{i\in
parent(c)}\frac{1}{R_{i,c}/k}$

where $parent(c)$ represents the parent node set of the query concept $c$, and
$R_{i,c}$ is the rank position of query concept c’s true parent $i$.

  * •

hit@k: is the number of query concepts whose parent is ranked in the top k
positions, divided by the total number of queries.

  * •

time: denotes the seconds used in the predicting stage of each model on each
dataset.

#### Baseline Methods

We compared our proposed GANTEE model with the following baseline approaches:

  * •

Closest-Position: A rule-based method that chooses the anchor concept which
have the most similar embedding with query concept as the query concept’s
parent.

  * •

Closest-Neighbor: Another rule-based method that scores each position based on
its distance to the query concept plus the average distance between its
children nodes and the query.

  * •

BERT+MLP: This method utilizes BERT (Devlin et al. 2018) 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.

  * •

Random: This method is used only in the taxonomy entering evaluation task,
which is random to determine if the query concept should be added to the
existing taxonomy or not.

  * •

TaxoExpan (Shen et al. 2020): One state-of-the-art taxonomy expansion
framework which leverages position enhanced graph neural network to capture
local information and InfoNCE (Oord, Li, and Vinyals 2018) loss for robust
training.

Notably, except for the rule-based method Closest-Position and Closest-
Neighbor, other baselines are learning-based methods and designed for one-to-
one matching. There are other recently proposed taxonomy expansion methods,
e.g., HiExpan (Shen et al. 2018) and STEAM (Yu et al. 2020). We do not include
them as baselines because they leverage external sources, e.g., text corpus,
to extract complicated features. In contrast, TaxoExpan and other baselines
only take initial feature vectors as input.

#### Parameter Setting

For learning-based methods, we use SGD optimizer with initial learning rate
0.0001 and
ReduceLROnPlateau111https://pytorch.org/docs/stable/optim.html/#torch.optim.lr
_scheduler.ReduceLROnPlateau scheduler with ten patience epochs. During model
training, the batch size and negative sample size are set to 16 and 256 in the
overall performance experiments, respectively. We set the epochs to be ten and
use two layers of Graph Attention Layer with 8 and 1 attention head and 100
dimensions of the position dim.

Figure 3: The changing of the results on different metrics with different
negative size sampling during the taxonomy expansion model training stage and
different number of generated high-quality samples by GANTEE.

Method | MAG-CS | CN-Probase-Sampled
---|---|---
Acc | F1 | Acc | F1
Closest-Position | 21.5 | 13.9 | 15.4 | 11.5
Closest-Neighbor | 28.8 | 17.8 | 19.6 | 13.7
BERT+MLP | 57.6 | 46.1 | 52.3 | 43.8
Random | 74.8 | - | 75.9 | -
TaxoExpan | 76.4 | 52.7 | 66.8 | 32.1
GANTEE | 89.2 | 79.3 | 77.5 | 65.4

Table 2: Performance on Taxonomy Entering Evaluation.

Figure 4: The changing of the losses and results on different metrics with the
adversarial training goes on. In these figures, red lines denote “loss”, and
blue line denotes the metrics, label “No” means taxonomy expansion without
GANTEE, label “P” means the stage of pretraining generative model, and label
“A” means the adversarial training stage.

Taxonomy | MAG-CS TE | MAG-CS TEE
---|---|---
\+ GANTEE | MR | MRR | hit@5 | Acc | F1
w/o hd | 1235 | 0.357 | 0.186 | 78.5 | 62.9
w/o rd | 1217 | 0.351 | 0.182 | 81.5 | 71.3
w/o $D_{\phi}$ | 1250.1 | 0.348 | 0.180 | 71.4 | 51.9
- | 1188.1 | 0.360 | 0.193 | 89.2 | 79.3

Table 3: Ablation study on GANTEE.

### Experimental Results

#### Overall Performance on Taxonomy Expansion

As our proposal is a plugin framework for improving both the effectiveness and
efficiency of the taxonomy expansion, we are curious how GANTEE will affect
the performance of the previous methods on the taxonomy expansion task. Thus,
we use GANTEE on the most prevailing State-Of-The-Art (SOTA) method TaxoExpan
(Shen et al. 2020) on the taxonomy expansion task. The results are presented
in Table 1.

Notably, since the time expense of the rule-based method only depends on the
computational complexity of the algorithms or matrix operations, it is not
recorded, for it can be neglected most of the time in our experiments. And the
time expense of TaxoExpan on CN-Probase is too large, and we do not finish
this experiment in days, so the expected time expense is recorded in the
table.

Effectiveness Performance: From the results, we can see that all of the rule-
based methods did a poor job in most metrics, which demonstrates that the
semantics of concepts in real-scenarios are complicated, so simple rule-based
methods have difficulty performing well in the taxonomy expansion task.
However, BERT+MLP has also done a poor job on most metrics, demonstrating that
simply using the representation of PLM is not suitable for taxonomy expansion
tasks. With our GANTEE, TaxoExpan can reach a new SOTA in all three datasets.
Additionally, the larger scale of the taxonomy, the more improvement is made
through GANTEE.

Efficiency Performance: BERT+MLP method is proven itself to be an efficient
method, and we think it is because this method also uses PLMs to fetch the
representation of each concept, which is a trade to the final effectiveness of
the taxonomy expansion task. Moreover, when TaxoExpan is implemented after our
proposed method, a new SOTA is reached within one-third of the predicting time
on three datasets on average.

#### Performance on Taxonomy Entering Evaluation

Table 2 presents the results of all compared methods on the three datasets.
The rule-based methods and BERT+MLP did a poor job on taxonomy entering
evaluation task, which is much worse than the Random. The TaxoExpan has
limited ability to distinguish the noisy query concept, for it outperforms
four of the other baseline methods. GANTEE outperforms all the other methods
by a large margin on all datasets in taxonomy entering evaluation task.
Furthermore, since the PLM representation of the English word is better than
the Chinese word, it is easier for the discriminator to distinguish the noisy
query concepts in English than in Chinese, which makes all the metrics in
English higher than in Chinese.

#### Ablation Study

The detail of ablation studies is presented in this subsection. We remove
three of the essential designs in the GANTEE. In “w/o hd”, we remove the hyper
discriminator during the adversarial generating process. In “w/o rd”, we
remove the rollout discriminator during the adversarial generating process. In
“w/o $D_{\phi}$”, we remove all the adversarial processes and only use the
generator to generate samples. The results are shown in Table 3

We compare the removal of the hyper discriminative model $D_{H}$ and rollout
discriminative model $D_{R}$ together. We can see that without the rollout
discriminative model, all metrics have a more significant decline than without
the hyper discriminative model in the taxonomy expansion task. However, when
the hyper discriminative model is removed, there will be a more significant
decline in the metrics in the taxonomy entering evaluation task than removing
the rollout discriminative. We conclude that the rollout discriminative model
generates better conceptual texts, and the hyper discriminative is used to
strictly denoise all the noisy query concepts.

And without all of the discriminative models, which means only using the
generative model to learn from the query conceptual text, a significant
decline is witnessed in all metrics. We conclude there are two main reasons.
The first reason for this significant decline is because there has no model
trained for taxonomy entering evaluation specifically, so the metrics of
taxonomy entering evaluation task is decreasing. The second reason for this
significant decline is because there have no supervised signals provided
during the generating process, and the GPT-2 is hard to capture the semantic
of the hypernym-hyponym relationship in the existing taxonomy, so the result
of the taxonomy expansion task is decreasing.

#### Analysis of GANTEE

The Table 3 denotes how different the negative size during training and a
different number of the high-quality generated training sampled by GANTEE
affect the final result of the taxonomy expansion task. The upper right corner
of the figure is significantly darker than the other areas. So we conclude
that when generating more high-quality training samples by GANTEE, the
taxonomy expansion task will improve performance by using a bigger negative
size of the taxonomy expansion in its training stage.

The Table 4 denotes how the final result of the taxonomy expansion task will
be affected when the GANTEE stop training in a different training stage. In
these figures, we can intuitively conclude that with the stage of the training
going deeper, the performance of the final result will not be better because
the line in MRR, hit@1, and hit@3 are not consistently decreasing, and the
line in MR is not continuously increasing. We conclude that when the loss no
longer drops dramatically, it is better to stop the training of the GANTEE to
receive a better performance in the taxonomy expansion task. We find out that
the goal of the generative model in GANTEE is to confuse the discriminator,
and when the distribution of the generated text is close to the distribution
of the real conceptual text, the discriminator will not be able to identify
the samples effectively. And the gradients are not effectively obtained,
causing the discriminator to become less and less effective, affecting the
quality of the generator and generated training data.

---
Samples Generated by GANTEE
Given Label
Positive
Given Anchor Concept
Deep Learning Algorithm
Generated Text
Deep Q-Learning ✓
Given Label
Positive
Given Anchor Concept
Computer Vision
Generated Text
Computer Vision Algorithm ✓
Given Label
Negative
Given Anchor Concept
Deep Learning Algorithm
Generated Text
Deep Graphics Processing Unit ✓
Given Label
Positive
Given Anchor Concept
Deep Q-Learning
Generated Text
Deep Algorithm ✗
Given Label
Positive
Given Anchor Concept
Deep Learning
Generated Text
Deep Graphics Processing Unit ✗
Table 4: Case study of the samples generated by GANTEE. Text in purple and
brown represents given label and given anchor concept. Text in blue and red
denotes good cases and bad cases.

#### Case Analysis

We present three good cases and two typical bad cases of GANTEE in Tabel 4

The result shows that GANTEE has the ability in generating a new concept in a
domain-specific field. For example, “Deep Q-Learning”, “Computer Vision
Algorithm” and “Deep Graphics Processing Unit” are all correct concepts and
have true hypernym-hyponym relationships to the given anchor concepts based on
the given label.

However, we find GANTEE has limited ability in generating positive query
concepts for too fine-grained or too coarse-grained anchor concepts. We
conclude that GANTEE has difficulty in capturing the semantics of too fine-
grained anchor concepts which are seldom seen in the training process of
GANTEE “Deep Q-Learning Algorithm” to “Deep Algorithm”. And GANTEE tends to
assign any concept to the too coarse-grained anchor concepts like “Deep
Graphics Processing Unit” to “Deep Learning”.

## Related Work

### Taxonomy Construction and Expansion

The previous methods for taxonomy expansion task can be divided into two
categories. The studies in the first category tend to construct a better model
to predict the hypernym-hyponym relationships of the concepts. Position
embedding (Shen et al. 2020), concept sorting mechanism (Song et al. 2021) and
multilevel position matching (Wang et al. 2022) are proposed to better
understand the semantics of the query concepts and anchor concepts. The second
category focus on learning good representations for all concepts. Open source
(Yu et al. 2020), user-clicked-logs (Cheng et al. 2022) and parent-child
information (Wang et al. 2021, 2022) are all used by the previous methods to
learn a better representation for concepts. Besides, there exist many studies
that use PLMs during the representation learning stage (Cheng et al. 2022;
Wang et al. 2022; Takeoka, Akimoto, and Oyamada 2021), however, these methods
only use the PLMs as a external information provider to learn a better
representation.

## Conclusion

This paper studies the drawbacks of the existing taxonomy expansion methods
when applied to the real-scenarios. We propose a pluggable framework called
GANTEE to alleviate these drawbacks. Extensive experiments have been conducted
to demonstrate that GANTEE can boost the efficiency and effectiveness of the
taxonomy expansion task. Interesting future work includes lower the
representation learning expense or learning representation for multi-model
queries in the task of taxonomy expansion.

##  Acknowledgments

This work was supported by Shanghai Municipal Special Fund for Promoting High-
quality Development of Industries (No. 2021-GZL-RGZN-01018), Shanghai Sailing
Program (No. 23YF1409400), National Key Research and Development Project
(No.2020AAA0109302), Scientific and technological innovation 2030 - major
project of new generation artificial intelligence (No.2020AAA0109300),
National Natural Science Foundation of China (No.62072323), Shanghai Science
and Technology Innovation Action Plan (No. 22511104700). National Natural
Science Foundation of China (No. 62102095).

## References

  * Bachman and Precup (2015) Bachman, P.; and Precup, D. 2015.  Data generation as sequential decision making.  _Advances in Neural Information Processing Systems_ , 28.
  * Bahdanau et al. (2016) Bahdanau, D.; Brakel, P.; Xu, K.; Goyal, A.; Lowe, R.; Pineau, J.; Courville, A.; and Bengio, Y. 2016.  An actor-critic algorithm for sequence prediction.  _arXiv preprint arXiv:1607.07086_.
  * Chen et al. (2019) Chen, J.; Wang, A.; Chen, J.; Xiao, Y.; Chu, Z.; Liu, J.; Liang, J.; and Wang, W. 2019.  CN-Probase: a data-driven approach for large-scale Chinese taxonomy construction.  In _2019 IEEE 35th International Conference on Data Engineering (ICDE)_ , 1706–1709. IEEE.
  * Cheng et al. (2022) Cheng, S.; Gu, Z.; Liu, B.; Xie, R.; Wu, W.; and Xiao, Y. 2022.  Learning What You Need from What You Did: Product Taxonomy Expansion with User Behaviors Supervision.  _arXiv preprint arXiv:2203.14921_.
  * Cho et al. (2014) Cho, K.; Van Merriënboer, B.; Gulcehre, C.; Bahdanau, D.; Bougares, F.; Schwenk, H.; and Bengio, Y. 2014.  Learning phrase representations using RNN encoder-decoder for statistical machine translation.  _arXiv preprint arXiv:1406.1078_.
  * Devlin et al. (2018) Devlin, J.; Chang, M.-W.; Lee, K.; and Toutanova, K. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Goodfellow et al. (2014) Goodfellow, I.; Pouget-Abadie, J.; Mirza, M.; Xu, B.; Warde-Farley, D.; Ozair, S.; Courville, A.; and Bengio, Y. 2014.  Generative adversarial nets.  _Advances in neural information processing systems_ , 27.
  * Guo et al. (2018) Guo, J.; Lu, S.; Cai, H.; Zhang, W.; Yu, Y.; and Wang, J. 2018.  Long text generation via adversarial training with leaked information.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 32.
  * Hochreiter and Schmidhuber (1997) Hochreiter, S.; and Schmidhuber, J. 1997.  Long short-term memory.  _Neural computation_ , 9(8): 1735–1780.
  * Huang et al. (2019) Huang, J.; Ren, Z.; Zhao, W. X.; He, G.; Wen, J.-R.; and Dong, D. 2019.  Taxonomy-aware multi-hop reasoning networks for sequential recommendation.  In _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining_ , 573–581.
  * Jiang et al. (2019) Jiang, S.; Liang, J.; Xiao, Y.; Tang, H.; Huang, H.; and Tan, J. 2019.  Towards the completion of a domain-specific knowledge base with emerging query terms.  In _2019 IEEE 35th International Conference on Data Engineering (ICDE)_ , 1430–1441. IEEE.
  * Jurgens and Pilehvar (2016) Jurgens, D.; and Pilehvar, M. T. 2016.  Semeval-2016 task 14: Semantic taxonomy enrichment.  In _Proceedings of the 10th international workshop on semantic evaluation (SemEval-2016)_ , 1092–1102.
  * Karamanolakis, Ma, and Dong (2020) Karamanolakis, G.; Ma, J.; and Dong, X. L. 2020.  Txtract: Taxonomy-aware knowledge extraction for thousands of product categories.  _arXiv preprint arXiv:2004.13852_.
  * Lauscher et al. (2019) Lauscher, A.; Vulić, I.; Ponti, E. M.; Korhonen, A.; and Glavaš, G. 2019\.  Specializing unsupervised pretraining models for word-level semantic similarity.  _arXiv preprint arXiv:1909.02339_.
  * Lewis et al. (2019) Lewis, M.; Liu, Y.; Goyal, N.; Ghazvininejad, M.; Mohamed, A.; Levy, O.; Stoyanov, V.; and Zettlemoyer, L. 2019.  Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  _arXiv preprint arXiv:1910.13461_.
  * Liu et al. (2020) Liu, B.; Guo, W.; Niu, D.; Luo, J.; Wang, C.; Wen, Z.; and Xu, Y. 2020.  GIANT: scalable creation of a web-scale ontology.  In _Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data_ , 393–409.
  * Liu et al. (2019) Liu, B.; Guo, W.; Niu, D.; Wang, C.; Xu, S.; Lin, J.; Lai, K.; and Xu, Y. 2019.  A user-centered concept mining system for query and document understanding at tencent.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 1831–1841.
  * Mao et al. (2020) Mao, Y.; Zhao, T.; Kan, A.; Zhang, C.; Dong, X. L.; Faloutsos, C.; and Han, J. 2020\.  Octet: Online Catalog Taxonomy Enrichment with Self-Supervision.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2247–2257.
  * Nie, Narodytska, and Patel (2018) Nie, W.; Narodytska, N.; and Patel, A. 2018.  Relgan: Relational generative adversarial networks for text generation.  In _International conference on learning representations_.
  * Oord, Li, and Vinyals (2018) Oord, A. v. d.; Li, Y.; and Vinyals, O. 2018.  Representation learning with contrastive predictive coding.  _arXiv preprint arXiv:1807.03748_.
  * Peng et al. (2019) Peng, H.; Li, J.; Wang, S.; Wang, L.; Gong, Q.; Yang, R.; Li, B.; Philip, S. Y.; and He, L. 2019.  Hierarchical taxonomy-aware and attentional graph capsule RCNNs for large-scale multi-label text classification.  _IEEE Transactions on Knowledge and Data Engineering_ , 33(6): 2505–2519.
  * Radford et al. (2019) Radford, A.; Wu, J.; Child, R.; Luan, D.; Amodei, D.; Sutskever, I.; et al. 2019\.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8): 9.
  * Sang (2007) Sang, E. T. K. 2007.  Extracting hypernym pairs from the web.  In _Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics Companion Volume Proceedings of the Demo and Poster Sessions_ , 165–168.
  * Shen et al. (2020) Shen, J.; Shen, Z.; Xiong, C.; Wang, C.; Wang, K.; and Han, J. 2020.  TaxoExpan: self-supervised taxonomy expansion with position-enhanced graph neural network.  In _Proceedings of The Web Conference 2020_ , 486–497.
  * Shen et al. (2018) Shen, J.; Wu, Z.; Lei, D.; Zhang, C.; Ren, X.; Vanni, M. T.; Sadler, B. M.; and Han, J. 2018.  Hiexpan: Task-guided taxonomy construction by hierarchical tree expansion.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2180–2189.
  * Shi and Demberg (2019) Shi, W.; and Demberg, V. 2019.  Next sentence prediction helps implicit discourse relation classification within and across domains.  In _Proceedings of the 2019 conference on empirical methods in natural language processing and the 9th international joint conference on natural language processing (EMNLP-IJCNLP)_ , 5790–5796.
  * Sinha et al. (2015) Sinha, A.; Shen, Z.; Song, Y.; Ma, H.; Eide, D.; Hsu, B.-J.; and Wang, K. 2015.  An overview of microsoft academic service (mas) and applications.  In _Proceedings of the 24th international conference on world wide web_ , 243–246.
  * Song et al. (2021) Song, X.; Shen, J.; Zhang, J.; and Han, J. 2021.  Who Should Go First? A Self-Supervised Concept Sorting Model for Improving Taxonomy Expansion.  _arXiv preprint arXiv:2104.03682_.
  * Sutton et al. (1999) Sutton, R. S.; McAllester, D.; Singh, S.; and Mansour, Y. 1999.  Policy gradient methods for reinforcement learning with function approximation.  _Advances in neural information processing systems_ , 12.
  * Takeoka, Akimoto, and Oyamada (2021) Takeoka, K.; Akimoto, K.; and Oyamada, M. 2021.  Low-resource taxonomy enrichment with pretrained language models.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , 2747–2758.
  * Vaswani et al. (2017) Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, Ł.; and Polosukhin, I. 2017.  Attention is all you need.  _Advances in neural information processing systems_ , 30.
  * Wang et al. (2021) Wang, S.; Zhao, R.; Chen, X.; Zheng, Y.; and Liu, B. 2021.  Enquire One’s Parent and Child Before Decision: Fully Exploit Hierarchical Structure for Self-Supervised Taxonomy Expansion.  _arXiv preprint arXiv:2101.11268_.
  * Wang et al. (2022) Wang, S.; Zhao, R.; Zheng, Y.; and Liu, B. 2022.  QEN: Applicable Taxonomy Completion via Evaluating Full Taxonomic Relations.  In _Proceedings of the ACM Web Conference 2022_ , 1008–1017.
  * Yang, Zhang, and Han (2020) Yang, C.; Zhang, J.; and Han, J. 2020.  Co-embedding network nodes and hierarchical labels with taxonomy based generative adversarial networks.  ICDM.
  * Yang et al. (2019) Yang, Z.; Dai, Z.; Yang, Y.; Carbonell, J.; Salakhutdinov, R. R.; and Le, Q. V. 2019\.  Xlnet: Generalized autoregressive pretraining for language understanding.  _Advances in neural information processing systems_ , 32.
  * Yu et al. (2017) Yu, L.; Zhang, W.; Wang, J.; and Yu, Y. 2017.  Seqgan: Sequence generative adversarial nets with policy gradient.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 31.
  * Yu et al. (2020) Yu, Y.; Li, Y.; Shen, J.; Feng, H.; Sun, J.; and Zhang, C. 2020.  STEAM: Self-Supervised Taxonomy Expansion with Mini-Paths.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 1026–1035.
  * Zhang et al. (2021) Zhang, J.; Song, X.; Zeng, Y.; Chen, J.; Shen, J.; Mao, Y.; and Li, L. 2021.  Taxonomy Completion via Triplet Matching Network.  _arXiv preprint arXiv:2101.01896_.