* [163] P. deNiverville, C.-Y. Chen, M. Pospelov, and A. Ritz, “Light dark matter in neutrino beams: production modelling and scattering signatures at MiniBooNE, T2K and SHiP,” Phys. Rev. D 95 no. 3, (2017) 035006, arXiv:1609.01770 [hep-ph].


# Entity Linking and Discovery via
Arborescence-based Supervised Clustering

Dhruv Agarwal, Rico Angell, Nicholas Monath, Andrew McCallum
College of Information and Computer Sciences
University of Massachusetts Amherst
<EMAIL_ADDRESS>
###### Abstract

Previous work has shown promising results in performing entity linking by
measuring not only the affinities between mentions and entities but also those
amongst mentions. In this paper, we present novel training and inference
procedures that fully utilize mention-to-mention affinities by building
minimum arborescences (i.e., directed spanning trees) over mentions and
entities across documents in order to make linking decisions. We also show
that this method gracefully extends to entity discovery, enabling the
clustering of mentions that do not have an associated entity in the knowledge-
base. We evaluate our approach on the Zero-Shot Entity Linking dataset and
MedMentions, the largest publicly available biomedical dataset, and show
significant improvements in performance for both entity linking and discovery
compared to identically parameterized models. We further show significant
efficiency improvements with only a small loss in accuracy over previous work,
which use more computationally expensive models.

##  1 Introduction

Entities are often mentioned ambiguously in natural language corpora, such as
biomedical research papers Leaman and Lu (2016); Sung et al. (2020) , news
Milne and Witten (2008); Hoffart et al. (2011), and web page text Gabrilovich
et al. (2013); Lazic et al. (2015). Resolving the ambiguity of these entity
mentions requires either linking each mention to a knowledge-base (KB) or, if
there is no suitable KB entry, adding a new entity to the KB. The latter task,
_entity discovery_ , is often done by discovering coreference relationships
among mentions and providing each coreferent mention an identifier that
represents the newly added entity McNamee and Dang (2009); Radford et al.
(2011). Linking and discovery are important for question answering Das et al.
(2019) and building KBs Ling et al. (2015) or semantic indexes Leaman and Lu
(2016).

Entity linking is particularly challenging in zero-shot settings, where not
every entity has labeled training data Lin et al. (2017); Logeswaran et al.
(2019). In such settings, we rely on entity descriptions, types, and aliases
to form entity representations, which are used for linking predictions.

Figure 1: Linking & Discovery. We consider the task of both entity linking and
discovery (also known as NIL clustering), in which ambiguous mentions are
either ground to existing KB entities or form new ones.

Entity linking and coreference are closely related, with linking decisions
implying coreference relationships amongst mentions Dutta and Weikum (2015a).
Recent work Angell et al. (2021) has demonstrated how a clustering-based
approach for entity linking prediction can share linking decisions by
predicting coreference between mentions. This approach, however, uses cross-
encoder based transformer models Devlin et al. (2019), which are prohibitively
expensive when it comes to running in cross-document settings — the number of
input sequences passed through the transformer encoder scales quadratically
with the number of mentions. This limits the approach to only consider pairs
of mentions within the same document when computing mention-to-mention
affinities.

Inspired by this recent work on clustering-based inference, we present a new
model for clustering that uses a graph-based approach of modeling directed
nearest-neighbor relationships among mentions in an _arboresence_ (directed
minimum spanning tree). We demonstrate how this approach uses a bi-encoder
Devlin et al. (2019) in order to be significantly more efficient. To
complement this, we propose a supervised clustering training objective
motivated by our inference procedure. We further show how our model can be
used as a unified approach for both linking entities as well as discovering
them.

We evaluate our approach on two entity linking datasets, both of which are in
the zero-shot domain. We compare the performance of our training procedure
against two standard bi-encoder training procedures using both independent
inference (linking each mention individually) and clustering-based inference.
We find that our training improves performance by 13.1 percentage points on
MedMentions and 11.1 & 0.6 points on the two training variants compared on
ZeShEL. In addition, we run experiments for entity discovery by removing a
fraction of entities from the KB and demonstrate that our training and
inference procedures are better suited for this task. Compared to cross-
encoder based approaches, our bi-encoder approach is more that two times more
efficient with only a small loss in accuracy.

##  2 Problem Definition

Figure 2: Inference for Entity Linking and Discovery. Mentions are represented
by circles and entities by rectangles. The left sub-figure shows the
$k$-nearest neighbor graph over all mentions across all documents and all
entities in the knowledge-base. Dashed edges are edges that were dropped since
they have edge weights above the threshold $\lambda=0.4$ and solid edges
represent the resulting graph, which is input to the inference algorithms. The
center sub-figure shows the result of undirected inference and the right
figure shows the result of directed inference. In both sub-figures, the dark
edges are the edges kept and the light edges are those removed by the
inference procedure. Both inference procedures result in one cluster that does
not contain an entity, predicting this cluster of mentions as a new discovered
KB entity.

Each document $d$ of a corpus $\mathcal{D}$ contains a set of entity mention
spans $\mathcal{M}^{d}=\\{m^{d}_{1},m^{d}_{2},\dots,m^{d}_{N}\\}$. All
mentions in the corpus are given by
$\mathcal{M}=\bigcup_{d\in\mathcal{D}}\mathcal{M}^{d}$. Following Logeswaran
et al. (2019); Angell et al. (2021), we assume that these mentions are pre-
identified spans of text.

#### Entity Linking

We first consider the task of entity linking in which we are provided a
knowledge-base of entities $\mathcal{E}$ and our task is to predict an entity
$e^{d}_{i}\in\mathcal{E}$ for each mention $m^{d}_{i}$. We use
${e^{\star}}^{d}_{i}$ to refer to the ground truth entity label for
$m^{d}_{i}$.

#### Zero-Shot Linking

The zero-shot task refers to the setting where there are entities in the
knowledge base that do not have any labeled training data. Linking decisions
must, instead, rely on provided information for entities such as a
description, aliases, and/or the entity type.

#### Linking + Discovery

We also consider a setting in which the complete knowledge-base of entities
may not be known in advance and new entities must be _discovered_. For this
task, we assign every entity mention $m^{d}_{i}$ a cluster/coreference label
$c^{d}_{i}\in\mathcal{C}$ that is independent of the entity labels in the KB,
i.e. $\mathcal{C}\cap\mathcal{E}=\emptyset$. In this setting, a mention
$m^{d}_{i}$ may be assigned $e^{d}_{i}=\textsc{nil}$, indicating that
$m^{d}_{i}$ refers to an entity not present in the knowledge-base. Non-nil
assignment decisions imply coreference between mentions.

It is important to note the distinctions between zero-shot linking and
discovery. In the zero-shot setting, entities are known in the KB ahead of
time, but there is no training data. In the discovery setting, we do not know
all the entities a priori, and our performance, then, is evaluated in terms of
the correctness of clustering.

##  3 Linking & Discovering Entities with Graph-Based Clustering

In this section, we describe our proposed approach for making entity linking
and discovery decisions. We define a distance measure between mentions and
entities in terms of a directed graph, where nodes refer to both mentions as
well as entities, and the edges are inferred by the model. Clusters are then
constructed from this graph such that no cluster contains more than one
entity. Linking decisions are made by assigning each mention within a cluster
to the entity node present within the same cluster. In this way, clusters
represent new (discovered) entities if a set of mentions is clustered without
an entity node.

Our approach generalizes the clustering-based approach of Angell et al. (2021)
by (1) proposing a clustering approach on _directed_ graphs (2) using all
mentions in the corpus rather than operating in a within-document setting.

There are four main components to our approach: (1) graph-based dissimilarity
measure, (2) models to provide edge weights, (3) approach for inferring latent
graph, and (4) building constrained clusters.

#### Graph-based Dissimilarity

Let $G$ be a graph with nodes $V=\mathcal{M}\cup\mathcal{E}$ and directed
edges $E\subset V\times V$. Each edge $(x,y)$ of the graph has an associated
weight $w_{x,y}$. We define a dissimilarity function $f$ between two nodes
$u,v\in V$ to be the weight of the minimax path between the nodes, i.e.

$f(u,v)=\begin{cases}\min\limits_{p\in u\rightsquigarrow
v}\max\limits_{(x,y)\in p}w_{x,y},&\text{if }\mathop{\rm connected}(u,v)\\\
\;\;\infty,&\text{otherwise}\end{cases}$ (1)

where $\mathop{\rm connected(u,v)}$ is true if there exists a directed path
from node $u$ to $v$ in $G$, and $u\rightsquigarrow v$ is the set of all paths
between $u$ and $v$. In words, the dissimilarity between $u$ and $v$ is the
minimum of the highest weight edges in all paths between the two nodes, and
this is often referred to as the "bottleneck edge". This measure has the
property of emitting low dissimilarities between nodes even when the direct
edge weight $w_{u,v}$ is high by connecting them through a chain of low-weight
edges providing an inductive bias well-suited for coreference, i.e. not all
pairs of points in a cluster are nearby, see Figure 2 for an example. This
inductive bias is not achieved if we sum edge weights and simply find the
minimum path.

#### Edge Weights

With this definition of dissimilarity, we now define how edge weights are
calculated. We use two models: a mention-pair affinity model,
$\phi:\mathcal{M}\times\mathcal{M}\rightarrow\mathbb{R}$, and a mention-entity
affinity model, $\psi:\mathcal{E}\times\mathcal{M}\rightarrow\mathbb{R}$. An
edge between two mentions $m_{i}$ and $m_{j}$ has weight:

$\displaystyle w_{m_{i},m_{j}}$ $\displaystyle=-\,\phi(m_{i},m_{j}),$ (2)

and the weight of the edge from entity $e$ to $m_{i}$ is:

$\displaystyle w_{e,m_{i}}$ $\displaystyle=-\,\psi(e,m_{i})$ (3)

Each of $\phi(\cdot,\cdot)$ and $\psi(\cdot,\cdot)$ are parameterized by bi-
encoder transformer models Gillick et al. (2019); Humeau et al. (2019). We
train two independently parameterized transformer encoder models: one for
mentions, $\mathtt{Enc}_{\mathrm{M}}$, and one for entities,
$\mathtt{Enc}_{\mathrm{E}}$. The affinity models are simply the inner products
of the associated encoded representations:

$\displaystyle\phi(m_{i},m_{j})$
$\displaystyle=\mathtt{Enc}_{\mathrm{M}}(m_{i})^{T}\mathtt{Enc}_{\mathrm{M}}(m_{j})$
(4) $\displaystyle\psi(e,m_{i})$
$\displaystyle=\mathtt{Enc}_{\mathrm{E}}(e)^{T}\mathtt{Enc}_{\mathrm{M}}(m_{i})$

For the mention encoder, $\mathtt{Enc}_{\mathrm{M}}$, the input to the
transformer is the mention’s surrounding context with the mention span marked
by special tokens [START] and [END]:

$\displaystyle\texttt{[CLS]}c_{\text{left}}\texttt{[START]}m_{i}\texttt{[END]}c_{\text{right}}\texttt{[SEP]}$

where $c_{\text{left}}$ and $c_{\text{right}}$ are the left and right contexts
of the mention $m_{i}$ in the document. For the entity encoder,
$\mathtt{Enc}_{\mathrm{E}}$, the transformer takes as input the title and
description of the entity:

$\texttt{[CLS]}e_{\text{title}}\texttt{[TITLE]}e_{\text{desc}}\texttt{[SEP]}$

In this input, $e_{\text{desc}}$ is the token sequence corresponding to the
description of the entity, which could include natural language text related
to the entity, such as a "wiki" entry or a list of synonym representations of
the entity, or any other available features useful in forming an entity
representation.

#### Building the Graph

The structure of the graph $G$ impacts the dissimilarity function by changing
the paths between pairs of nodes in addition to changing which pairs of nodes
are connected. We advocate for a simple, deterministic approach to construct
this graph. For each mention $m$, construct $E_{m}$ by (1) adding edges from
$m$’s $k$-nearest neighbor mentions in $\mathcal{M}$ to $m$, and (2) adding an
edge from $m$’s nearest entity to $m$:

$\displaystyle E_{m}$ $\displaystyle=\left\\{(u,m)\ \Big{|}\ u\in\mathop{\rm
argmink}_{m^{\prime}\ \in\ \mathcal{M}}w_{m^{\prime},m}\right.$ (5)
$\displaystyle\qquad\qquad\quad\;\left.\lor\;u=\mathop{\mathrm{argmin}}_{e\
\in\ \mathcal{E}}w_{e,m}\right\\}$

The complete collection of edges $E$ in $G$ is given by
$E(G)=\bigcup_{m\in\mathcal{M}}E_{m}$. There are other ways that one could
conceivably pick the pairs of mentions to be connected in the graph. For
example, one could use the minimum spanning tree over the mentions. This
approach, however, has several drawbacks: (1) the directionality of nearest
neighbor relationships is ignored leading to added noise in the graph, and (2)
the resultant graph includes edges that clearly cross cluster boundaries due
to this approach forcing all pairs of mentions to be connected.

#### Forming Clusters & Making Predictions

The graph $G$ is input to a constrained clustering problem that partitions $G$
into disjoint clusters $\mathcal{C}=\\{C_{1},\dots,C_{M}\\}$ such that each
cluster contains at most one entity. There are three constraints that every
$C\in\mathcal{C}$ must satisfy:

$\displaystyle\textrm{ i. }\;|C\cap\mathcal{E}|\leq 1,\qquad\quad\;\,$
$\displaystyle\textrm{ ii. }\;\forall u,v\in C,\;\mathop{\rm
connected}(u,v)\implies f(u,v)\leq\lambda,$ $\displaystyle\textrm{iii.
}\;\forall u,v\in C,\;\mathop{\rm connected}(u,v)\vee\mathop{\rm
connected}(v,u)$

where $\lambda$ is a specified hyperparameter representing the dissimilarity
threshold. These constraints ensure that (i) there is at most one entity in
each cluster, (ii) if $u$ is reachable from $v$ then every edge in the path
from $v$ to $u$ has a weight $\leq\lambda$, and (iii) each node in the cluster
has a path connecting it with every other node in the cluster. We solve this
constrained clustering problem, i.e., partition graph $G$, using a process
similar to Angell et al. (2021).

Specifically, we first remove all edges in graph $G$ with weight greater than
$\lambda$. We then evaluate each edge $(u,v)\in E$ in descending order of
dissimilarity and check if its presence violates any of the three constraints
defined above, removing the edge from $E$ if it does. If not, we evaluate
whether there is an entity in the connected component of node $u$, i.e.
$|C_{u}\cap\mathcal{E}|=1$. We infer that $C_{u}$ refers to a new entity not
present in the KB if an entity is not found. If, however,
$|C_{u}\cap\mathcal{E}|=1$, we temporarily drop edge $(u,v)$ and check whether
$v$ can still be reached by an entity node. If reachable, we permanently drop
$(u,v)$, maintaining the validity of constraint (i) as well as our minimax
dissimilarity function $f(\cdot,\cdot)$. If an entity cannot reach $v$, we
retain edge $(u,v)$, preserving the connectivity of the cluster, and iterate
further. Our predicted clusters are the resultant connected components in the
partitioned graph $G$. We refer to this procedure as _directed inference_ when
we respect the direction of the edges and _undirected inference_ when we
disregard the direction (see Figure 2).

To make linking decisions for each mention $m^{d}_{i}$, we assign the ID of
the entity present in the mention’s cluster as the linking label (or nil if
there is no entity in the cluster). Let $\mathcal{C}(m^{d}_{i})$ be the
predicted cluster of mention $m^{d}_{i}$, then:

$e^{d}_{i}=\begin{cases}\mathcal{C}(m^{d}_{i})\cap\mathcal{E},&\text{if
}|\mathcal{C}(m^{d}_{i})\cap\mathcal{E}|=1\\\ \textsc{nil},&\text{
otherwise}\end{cases}.$ (6)

Furthermore, the clusters we predict for in the entity discovery setting are
exactly $\mathcal{C}$.

#### Cluster Spanning Arborescence

For every cluster with an entity node, the edge structure is a directed
analogue of the minimum spanning tree where there is a directed path from the
entity node to every other node in the cluster. This structure is often
referred to as the _minimum spanning arborescence_ , thus lending its name to
our method, i.e. Arborescence-based linking and discovery.

##  4 Training

In this section, we present our approach for training the affinity models,
$\phi(\cdot,\cdot)$ and $\psi(\cdot,\cdot)$, and their associated encoders,
$\mathtt{Enc}_{\mathrm{M}}$ and $\mathtt{Enc}_{\mathrm{E}}$. Our objective is
to optimize the dissimilarity function $f(\cdot,\cdot)$ such that the
clustering procedure infers a set of clusters that each contains exactly one
entity, and every mention is assigned to the cluster containing its ground
truth entity. We optimize $f(\cdot,\cdot)$ using mini-batch gradient descent
methods. To achieve this, we sequentially build mini-batches of mentions
$B\subset\mathcal{M}$ over the training data, where each $m_{i}\in B$ has
ground truth entity $e^{\star}_{i}$. We then build a graph $G_{B}$, where the
nodes are all $m_{i}\in B$, all mentions coreferent to $m_{i}\in B$, and the
set of ground truth entities for each $m_{i}\in B$.

For each $m_{i}$, we build a set of edges,

$\displaystyle E_{m_{i}}$ $\displaystyle=\left\\{(e^{\star}_{i},m_{\ell})\
\Big{|}\ m_{\ell}\in\mathcal{M}_{e^{\star}_{i}}\right\\}$ (7)
$\displaystyle\qquad\cup\left\\{(m_{\ell},m_{p})\ \Big{|}\
m_{\ell},m_{p}\in\mathcal{M}_{e^{\star}_{i}}\right\\}$

The complete set of edges in graph $G_{B}$ for a mini-batch $B$ is then given
by $E(G_{B})=\bigcup_{m_{i}\in B}E_{m_{i}}$. Observe that the resultant edges
ensure that each connected component contains exactly one entity (namely, the
ground truth entity for the mentions in that component). We then sparsify
$G_{B}$ by computing a partitioned target graph
$G^{\star}_{B}=\\{E^{\star}_{m_{i}}\ |\ m_{i}\in B\\}$ using the inference
procedure defined in the previous section, setting $\lambda=\infty$. After
this sparsification, $G^{\star}_{B}$ becomes a disjoint set of minimum
spanning arborescences rooted at the entity nodes. We use $E^{\star}_{m_{i}}$
to optimize the parametric encoder models. Note that each mention node in a
target edge set $E^{\star}_{m_{i}}$ has only one incoming edge originating
from either an entity or a mention, and the selection of $E^{\star}_{m_{i}}$
was done in a way to minimize $f(\cdot,\cdot)$ between mentions and entities
with the same label (maximize opposite labels) on the subgraph of the mini-
batch.

Akin to the graph embedding objectives used by Nickel and Kiela (2018) and
others, we construct our objective by sampling negative edges. For each
mention $m_{i}\in B$, the set of negative edges $\texttt{N}(m_{i})$ is the
$k/2$ lowest-weight incoming edges from
$\mathcal{E}\setminus\\{e^{\star}_{i}\\}$ and the $k/2$ lowest-weight incoming
edges from $\mathcal{M}\setminus\mathcal{M}_{e^{\star}_{i}}$, where $k$ is a
specified hyperparameter. Take $\Gamma(m_{i})=\\{u\ |\ (u,m_{i})\in
E^{*}_{m_{i}}\\}\cup\\{u\ |\ (u,m_{i})\in\texttt{N}(m_{i})\\}$ to be the set
of all neighbors with an outgoing edge to $m_{i}$ in the training graph. Let
$\mathbb{I}_{u,m_{i}}$ be the indicator variable such that
$\mathbb{I}_{u,m_{i}}=1$ if $(u,m_{i})\in E^{*}_{m_{i}}$ and
$\mathbb{I}_{u,m_{i}}=0$ otherwise. Our loss function with respect to each
mention $m_{i}\in B$ is as follows:

$\displaystyle\mathcal{L}(m_{i})$
$\displaystyle=\\!\\!\\!\sum_{u\in\Gamma(m_{i})}\\!\\!\\!\Big{(}\mathbb{I}_{u,m_{i}}\log(\sigma_{u}(w_{u,m_{i}}))$
(8)
$\displaystyle\quad+(1-\mathbb{I}_{u,m_{i}})\log(1-\sigma_{u}(w_{u,m_{i}}))\Big{)},$

where $\sigma(\cdot)$ is the softmax function over all edges in
$\Gamma(m_{i})\times\\{m_{i}\\}$. The loss for the entire batch $B$ is the
mean of losses over all mentions in $B$. Optimizing this loss function
requires simultaneously increasing the likelihood of the positive edges and
decreasing the likelihood of the negative edges. This objective and training
routine are inspired by the supervised single-linkage clustering proposed by
Yadav et al. (2019), but differs in the choice of loss function and selection
of negative examples. We also experimented with the standard cross-entropy
loss, but found its performance subpar.

|  | MedMentions | ZeShEL
---|---|---|---
Training | Inference |  | Overall | Acc. on |  | Overall
|  | k | Acc. | Seen | Unseen | k | Acc.
| Independent† | - | 58.7 | 61.4 | 49.2 | - | 39.3
In-Batch Negatives | k-NN Graph (undirected) | 1 | 59.1 | 61.9 | 49.4 | 1 | 38.5
| k-NN Graph (directed) | 1 | 59.1 | 62.0 | 49.2 | 1 | 38.6
| Independent† | - | 56.9 | 64.0 | 31.9 | - | 49.8
k-NN Negatives | k-NN Graph (undirected) | 1 | 51.0 | 58.0 | 26.4 | 1 | 40.1
| k-NN Graph (directed) | 1 | 52.8 | 60.5 | 25.9 | 1 | 40.8
| Independent† | - | 72.3 | 77.5 | 54.2 | - | 50.3
Arborescence-based (Ours) | k-NN Graph (undirected) | 1 | 72.3 | 77.6 | 54.3 | 1 | 50.3
| k-NN Graph (directed) | 2 | 72.2 | 77.5 | 53.8 | 1 | 50.4

Table 1: Bi-Encoder Linking Results: Accuracy (†Predictions based on mention-to-entity similarity only) Training | Recall@64
---|---
| MedMentions | ZeShEL
In-Batch Negatives | 87.69 | 84.04
k-NN Negatives | 85.84 | 84.77
Arborescence-based (Ours) | 95.62 | 85.11
Table 2: Bi-Encoder Linking Results: Recall@64

##  5 Experiments

We perform entity linking and discovery experiments using two datasets that
require generalization to unseen entities at test time (Table 4).

We analyze the improvements using our proposed approach as compared to
similarly parameterized bi-encoder methods. We provide an analysis of the
performance of each component of our approach, comparing our proposed graph
clustering and training objective to sensible baselines, and show that our
model has much higher accuracy while being as efficient as these baselines. We
further compare our approach to a state-of-the-art cross-encoder method and
show that our approach produces comparable accuracy results while being much
more efficient.

###  5.1 Datasets

#### MedMentions Mohan and Li
(2019)111https://github.com/chanzuckerberg/MedMentions

is a collection of titles and abstractions of bio-medical research papers. The
KB that is used for this dataset is the 2017AA full-version of UMLS. The
validation and test sets contain both entities that are present in the
training set as well as entities that are zero-shot (never seen at training
time). We use the author-recommended ST21pv subset.

#### ZeShEL Logeswaran et al. (2019)

is a collection of Fandom Wikias. The Wikias are divided into train / dev /
test splits, with no set overlapping in entities. In this way, all entities
that appear at validation and test time are not seen during training.

#### Entity Discovery

For this setting, we modify each dataset by randomly sampling 10% of the
entities in the dev and test partitions, and remove them from the knowledge-
base. These removals are the new entities that we attempt to discover in this
task. To our knowledge, other ED systems include Andrews et al. (2014), Dutta
and Weikum (2015b), Pershina et al. (2015). However, incorporating BERT-based
encoder models in these approaches is not straightforward, therefore a
comparison was outside the scope of this work.

###  5.2 Methods Compared

We analyze our proposed approach through comparisons with various sensible
alternatives for graph clustering and training.

#### Training Objectives

We compare the proposed graph-based training objective, which directly trains
both the mention-mention similarity function $\phi(\cdot,\cdot)$ and the
mention-entity similarity function $\psi(\cdot,\cdot)$ to baselines, which
only explicitly train $\psi(\cdot,\cdot)$ (and rely on the structure of
$\phi(\cdot,\cdot)$ sharing representions with $\psi(\cdot,\cdot)$ to provide
meaningful mention-mention similarities). We compare to two baselines: (1)
training $\psi(\cdot,\cdot)$ with random negatives (In-batch) and (2) training
$\psi(\cdot,\cdot)$ with hard negatives (k-NN).

#### Linking Procedures

We compare our proposed clustering-based inference procedure to a state-of-
the-art independent procedure (Independent), which directly links each mention
to its nearest entity. This model was used by Wu et al. (2020) to generate
candidates for a cross-encoder model trained on ZeShEL. We further compare our
approach to using _undirected_ rather than _directed_ edges in the graph
clustering step.

#### Cross-Encoder Models / SOTA

To measure how much we pay in accuracy to use these more efficient bi-encoder
models vis-à-vis cross-encoder models, we compare our performance to the
state-of-the-art cross-encoder based model that uses clustering-based
inference as that is most directly comparable to our method. Angell et al.
(2021) train two cross-encoder models, one for mention-mention affinities and
one for mention-entity affinities, and use an inference procedure equivalent
to our undirected clustering-based inference. The cross-encoder procedure they
use necessitates limiting the potential mention-mention and mention-entity
edges in the graph used for clustering since it is intractable to consider all
pairs, while our method requires no such restriction.

|  | MedMentions | ZeShEL
---|---|---|---
Training | Inference | k | NMI | ARI | $\frac{\text{NMI+ARI}}{\text{2}}$ | k | NMI | ARI | $\frac{\text{NMI+ARI}}{\text{2}}$
| No Entities† | - | 0.93 | 0.37 | 0.65 | - | 0.98 | 0.31 | 0.65
In-Batch Negatives | k-NN Graph (undirected) | 4 | 0.95 | 0.58 | 0.76 | 1 | 0.96 | 0.25 | 0.61
| k-NN Graph (directed) | 8 | 0.95 | 0.58 | 0.76 | 8 | 0.96 | 0.17 | 0.57
| No Entities† | - | 0.93 | 0.49 | 0.71 | - | 0.98 | 0.29 | 0.64
k-NN Negatives | k-NN Graph (undirected) | 1 | 0.93 | 0.56 | 0.75 | 1 | 0.98 | 0.31 | 0.64
| k-NN Graph (directed) | 1 | 0.93 | 0.57 | 0.75 | 1 | 0.98 | 0.31 | 0.64
| No Entities† | - | 0.94 | 0.51 | 0.72 | - | 0.98 | 0.34 | 0.66
Arborescence-based (Ours) | k-NN Graph (undirected) | 8 | 0.95 | 0.64 | 0.79 | 1 | 0.97 | 0.27 | 0.62
| k-NN Graph (directed) | 8 | 0.95 | 0.64 | 0.79 | 1 | 0.98 | 0.36 | 0.67

Table 3: Bi-Encoder Discovery Results. (†Predictions based on mention-to-mention similarity only) |  | MedMentions | ZeShEL
---|---|---|---
$|\mathcal{M}|$ | Train | 120K | 49K
Dev | 40K | 10K
Test | 40K | 10K
$|\mathcal{E}|$ | Train | 19K | 26K
Dev | 9K | 7K
Test | 8K | 7K
$|\mathcal{E}\setminus\mathcal{E}_{{\text{Train}}}|$ | Dev | 4K | 7K
Test | 4K | 7K
Table 4: Dataset Statistics. $|\mathcal{M}|$ is the number of mentions.
$|\mathcal{E}|$ is the number of unique entities in the labeled partition, not
the total KB size. $|\mathcal{E}\setminus\mathcal{E}_{\text{Train}}|$ is the
number of _zero-shot_ entities. The total KB size of MedMentions and ZeShEL
are 2M and 500K respectively.

###  5.3 Linking Results

We report the linking accuracy on MedMentions and ZeShEL in Table 1. We refer
to our training procedure as Arborescence-based, and show comparisons in
performance of our model with In-Batch Negatives and k-NN Negatives, as
described in the previous section. We use three inference procedures,
including our clustering-based approach in both Directed and Undirected modes.
We report test set accuracy at $k$ that performed best on the validation set.

#### MedMentions

We follow previous work in not supplying gold entity type information during
inference. This makes the task significantly more challenging. In addition to
reporting the overall linking accuracy, we measure the accuracy on Seen and
Unseen subsets, which correspond to the ground truth entities that were seen
and unseen (i.e., zero-shot) at training, respectively.

In Table 1, we observe that regardless of the chosen inference, the
Arborescence-based model significantly outperforms the other models by at
least 13.1 points in terms of overall accuracy, 13.5 points on Seen, and 4.4
points on Unseen mentions. We further see that Undirected clustering
marginally outperforms the Directed variant in the three categories by 0.1,
0.1, and 0.5 points, respectively. In Table 2, we report Recall@64, defined as
the accuracy of predicting a gold entity from any of the top-64 predictions
for a mention. We see that Arborescence-based achieves 7.93 and 9.78 points of
improvement over In-Batch and k-NN models.

These improvements in accuracy indicate that our training procedure enables
the model to learn much better representations of mentions and entities than
previous approaches.

We also compare the efficiency / accuracy trade-offs between our models and
Angell et al. (2021). Table 5 shows the training time, inference time, and
accuracy for all training and inference procedures considered on MedMentions.
In less than half of the training and inference time, without any external
information or preprocessing, and a much weaker architecture, our method is
able to achieve accuracy within 2 points of the SOTA cross-encoder model. This
highlights the effectiveness of our approach in producing a highly accurate,
yet efficient, model.

ZeShEL On this dataset, we evaluate assuming gold entity type information is
provided at both training and inference time. Since entities in the validation
and test sets are from domains different than those in the test set, our
evaluation is fully zero-shot. In Table 2, we show that the Arborescence-based
model achieves better Recall@64 by 1.07 points and 0.34 points over In-batch
and k-NN, respectively. In Table 1, we present accuracy results, which prior
work using bi-encoder models, to the best of our knowledge, does not report.
We see that the Arborescence-based model is more accurate than the In-batch
and k-NN models by 11.1 and 0.6 points of accuracy, respectively.

Training | Time (hrs) | Inference | Time (hrs) | Accuracy
---|---|---|---|---
|  | Independent† | 1.5 | 58.7
In-Batch Negatives | 3.4 | k-NN Graph (undirected) | 1.7 | 59.1
|  | k-NN Graph (directed) | 1.7 | 59.1
|  | Independent† | 1.5 | 56.9
k-NN Negatives | 18.5 | k-NN Graph (undirected) | 1.7 | 51.0
|  | k-NN Graph (directed) | 1.7 | 52.8
|  | Independent† | 1.5 | 72.3
Arborescence-based (Ours) | 32.1 | k-NN Graph (undirected) | 1.6 | 72.3
|  | k-NN Graph (directed) | 1.6 | 72.2
Clustering-based Angell et al. (2021) | 72.0 | k-NN Graph (undirected) | 4.0 | 74.1

Table 5: Efficiency-Accuracy Trade-Off (†Predictions based on entity-to-
mention affinity only)

###  5.4 Entity Discovery Results

In this setting, we evaluate the predicted clusters of our proposed approach
on a modified test set for MedMentions and ZeShEL by removing 10% of the
entities appearing in the test data from the knowledge-base and training new
models with the held-out entities removed during training. We report
performance in terms of two frequently-used clustering metrics — normalized
mutual information (NMI) and adjusted rand index (ARI) — in Table 3. We
compare the graph clustering-based inference procedures, which utilize entity
information, to one that only uses the mention-mention similarities. We select
the hyperparameters, ${k}$ and $\lambda$, on the dev set.

The results indicate that the Arborescence-based training procedure achieves
significantly better ARI score compared to the In-batch Negatives training on
both datasets (10 points on MedMentions and 5 points on ZeShEL). The
representations from our proposed training procedure seem to provide more
meaningful clusters of mentions than simply taking the layer before the
softmax of a trained linking model (i.e., the In-batch and k-NN settings). We
hypothesize that the improvements are achieved because the Arboresence-based
training is closely aligned with the clustering inference procedure. We
further observe that the directed approach offers significant improvement over
undirected on ZeShEL.

###  5.5 Experiment Details

Our experiments are run on top of BLINK Wu et al. (2020), a PyTorch Paszke et
al. (2019) implementation of the bi-encoder architecture for entity linking.
Each training procedure is run on a single machine using 2 NVIDIA Quadro RTX
8000 GPUs. Our models for Zeshel and MedMentions have 218M and 230M
parameters, respectively. Each variant of our bi-encoder models is optimized
using mini-batch gradient descent using the Adam optimizer for 5 epochs using
a mini-batch size of 128 to accumulate the gradients. Experiments with batch
sizes < 128 performed poorly possibly due to increased fluctuation of
gradients, and sizes > 128 were computationally infeasible to run given our
resources. For ZeShEL, each model is trained using 192 warm-up steps and
learning rates of 1e-5, 3e-5, and 3e-5 for In-batch, k-NN, and Arborescence-
based models, respectively. For MedMentions, each model is trained using 464
warm-up steps and a learning rate of 3e-5. We use
FAISS222https://github.com/facebookresearch/faiss Johnson et al. (2017) for
performing k-NN search during graph construction for training and inference.
For MedMentions, this took 70 mins to embed and index 2M entities and 120K
mentions, and 20 mins to perform search for 120K mentions.

##  6 Related Work

#### Entity Linking

Entity linking has been widely studied (Milne and Witten, 2008; Cucerzan,
2007; Lazic et al., 2015; Gupta et al., 2017; Raiman and Raiman, 2018;
Kolitsas et al., 2018; Cao et al., 2021, inter alia). Apart from Angell et al.
(2021), we note the similarities of our work and that of Dutta and Weikum
(2015a), which combines clustering-based cross-document coreference decisions
and linking. However, Dutta and Weikum (2015a) is based around using sparse
bag-of-word representations and is not well suited for the embedded-based
representations used in this work. Hoffart et al. (2011); Cheng and Roth
(2013); Ganea and Hofmann (2017); Le and Titov (2018) use global objectives
instead of independent predictions, measuring the compatibility of entity
links. Contemporaneous work by Jiang et al. (2022) also explores a joint
paradigm by building clusters of mentions and entities in order to solve a
maximum spanning tree problem.

#### Cross-document Coreference

Models have also been developed for the cross-document coreference setting
where no entity KB is assumed in advance (Bagga and Baldwin, 1998; Gooi and
Allan, 2004; Singh et al., 2011; Barhom et al., 2019; Cattan et al., 2020;
Caciularu et al., 2021; Ravenscroft et al., 2021; Cattan et al., 2021; Logan
IV et al., , inter alia). In future work, one might explore using our proposed
approach for entity discovery in these settings to understand room for
improvement of such systems using entity KB information.

#### Alternatives to Cross-Encoders

Our work demonstrates how clustering-based training and prediction improves
bi-encoder based models for linking and discovery. If prediction efficiency,
and not training efficiency, was the only concern, one could use model
distillation (Hinton et al., 2015; Izacard and Grave, 2021, inter alia). We
could also consider models such as poly-encoders as an alternative to bi-
encoders Humeau et al. (2020).

#### Ultrametric Fitting & Supervised Clustering

The proposed training objective is related to supervised clustering Yadav et
al. (2019). Algorithms for minimizing the minimax path distance is closely
related to fitting ultrametrics (Chierchia and Perret, 2019; Cohen-Addad et
al., 2020, inter alia).

#### Loss Augmented Inference

Our proposed training objective uses our graph-clustering procedure to
determine the loss. This is reminiscent structured prediction approaches such
as structured SVMs Tsochantaridis et al. (2004), in which inference is run
during training time and the loss is a function of predicted and target
structures.

##  7 Conclusion

In this work, we presented novel arboresence-based training and inference
procedures of bi-encoder models for entity linking and discovery. Our results
indicate that our training procedure yields bi-encoder models which far
outperform those models trained with standard procedures on challenging entity
linking and entity discovery tasks. Future work includes using cross-encoder
models, model distillation, and loss functions for directly optimizing
clustering metrics in entity discovery.

##  8 Ethical Considerations

The base models, which we fine-tuned, and evaluation datasets are all publicly
available. We will also make our code and models publicly available. The task
of entity resolution and discovery is relatively innocuous. However, there are
several ways in which models could be biased and there is the potential for
those biases to have harmful downstream consequences. There is a large body of
work studying the biases of language models (such as those used for fine-
tuning here) and coreference models. Most notably in understanding when error
rates in coreference differ across certain populations (e.g., genders, races,
or any entity-type more broadly). If entity linking and discovery systems are
used to build / populate knowledge-bases, those systems may propagate these
biased predictions. This could be particularly problematic if one used such a
biased knowledge-base with this realization. For instance, if entity mentions
are author names on citation data and the entities are scientific authors,
statistics like h-index or citation count could be biased if the algorithms
used to disambiguate the author names are biased. Lastly, we note entity
linking and discovery are related to surveillance and tracking in computer
vision, which bear a substantial weight of ethical considerations.

## Acknowledgements

We thank Nishant Yadav, Sunil Mohan, and members of UMass IESL and NLP groups
for helpful discussion and feedback. This work is funded in part by the Center
for Data Science and the Center for Intelligent Information Retrieval, and in
part by the National Science Foundation under Grants No. 1763618, and in part
by the Chan Zuckerberg Initiative under the project Scientific Knowledge Base
Construction. The work reported here was supported in part by the Center for
Data Science and the Center for Intelligent Information Retrieval, and in part
using high performance computing equipment obtained under a grant from the
Collaborative R&D Fund managed by the Massachusetts Technology Collaborative.
Rico Angell is supported by the National Science Foundation Graduate Research
Fellowship under Grant No. 1938059. Any opinions, findings and conclusions or
recommendations expressed in this material are those of the authors and do not
necessarily reflect those of the sponsor.

## References

  * Andrews et al. (2014) Nicholas Andrews, Jason Eisner, and Mark Dredze. 2014.  Robust entity clustering via phylogenetic inference.  In _Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 775–785.
  * Angell et al. (2021) Rico Angell, Nicholas Monath, Sunil Mohan, Nishant Yadav, and Andrew McCallum. 2021\.  Clustering-based inference for biomedical entity linking.  In _Conference of the North American Chapter of the Association for Computational Linguistics (NAACL)_.
  * Bagga and Baldwin (1998) Amit Bagga and Breck Baldwin. 1998.  Entity-based cross-document coreferencing using the vector space model.  In _36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics, Volume 1_ , pages 79–85, Montreal, Quebec, Canada. Association for Computational Linguistics.
  * Barhom et al. (2019) Shany Barhom, Vered Shwartz, Alon Eirew, Michael Bugert, Nils Reimers, and Ido Dagan. 2019.  Revisiting joint modeling of cross-document entity and event coreference resolution.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4179–4189, Florence, Italy. Association for Computational Linguistics.
  * Caciularu et al. (2021) Avi Caciularu, Arman Cohan, Iz Beltagy, Matthew E Peters, Arie Cattan, and Ido Dagan. 2021.  Cross-document language modeling.  _arXiv preprint arXiv:2101.00406_.
  * Cao et al. (2021) Nicola De Cao, Gautier Izacard, Sebastian Riedel, and Fabio Petroni. 2021.  Autoregressive entity retrieval.  In _International Conference on Learning Representations_.
  * Cattan et al. (2020) Arie Cattan, Alon Eirew, Gabriel Stanovsky, Mandar Joshi, and Ido Dagan. 2020.  Streamlining cross-document coreference resolution: Evaluation and modeling.  _arXiv preprint arXiv:2009.11032_.
  * Cattan et al. (2021) Arie Cattan, Sophie Johnson, Daniel Weld, Ido Dagan, Iz Beltagy, Doug Downey, and Tom Hope. 2021.  Scico: Hierarchical cross-document coreference for scientific concepts.  _arXiv preprint arXiv:2104.08809_.
  * Cheng and Roth (2013) Xiao Cheng and Dan Roth. 2013.  Relational inference for wikification.  In _Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing_ , pages 1787–1796, Seattle, Washington, USA. Association for Computational Linguistics.
  * Chierchia and Perret (2019) Giovanni Chierchia and Benjamin Perret. 2019.  Ultrametric fitting by gradient descent.  In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , pages 3175–3186.
  * Cohen-Addad et al. (2020) Vincent Cohen-Addad, Karthik C. S., and Guillaume Lagarde. 2020.  On efficient low distortion ultrametric embedding.  In _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 2078–2088. PMLR.
  * Cucerzan (2007) Silviu Cucerzan. 2007.  Large-scale named entity disambiguation based on Wikipedia data.  In _Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL)_ , pages 708–716, Prague, Czech Republic. Association for Computational Linguistics.
  * Das et al. (2019) Rajarshi Das, Ameya Godbole, Dilip Kavarthapu, Zhiyu Gong, Abhishek Singhal, Mo Yu, Xiaoxiao Guo, Tian Gao, Hamed Zamani, Manzil Zaheer, et al. 2019.  Multi-step entity-centric information retrieval for multi-hop question answering.  In _Proceedings of the 2nd Workshop on Machine Reading for Question Answering_ , pages 113–118.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Dutta and Weikum (2015a) Sourav Dutta and Gerhard Weikum. 2015a.  C3EL: A joint model for cross-document co-reference resolution and entity linking.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pages 846–856, Lisbon, Portugal. Association for Computational Linguistics.
  * Dutta and Weikum (2015b) Sourav Dutta and Gerhard Weikum. 2015b.  C3el: A joint model for cross-document co-reference resolution and entity linking.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pages 846–856.
  * Gabrilovich et al. (2013) Evgeniy Gabrilovich, Michael Ringgaard, and Amarnag Subramanya. 2013.  Facc1: Freebase annotation of clueweb corpora, version 1 (release date 2013-06-26, format version 1, correction level 0).
  * Ganea and Hofmann (2017) Octavian-Eugen Ganea and Thomas Hofmann. 2017.  Deep joint entity disambiguation with local neural attention.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 2619–2629, Copenhagen, Denmark. Association for Computational Linguistics.
  * Gillick et al. (2019) Dan Gillick, Sayali Kulkarni, Larry Lansing, Alessandro Presta, Jason Baldridge, Eugene Ie, and Diego Garcia-Olano. 2019.  Learning dense representations for entity retrieval.  In _Proceedings of the 23rd Conference on Computational Natural Language Learning (CoNLL)_.
  * Gooi and Allan (2004) Chung Heong Gooi and James Allan. 2004.  Cross-document coreference on a large scale corpus.  In _Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics: HLT-NAACL 2004_ , pages 9–16, Boston, Massachusetts, USA. Association for Computational Linguistics.
  * Gupta et al. (2017) Nitish Gupta, Sameer Singh, and Dan Roth. 2017.  Entity linking via joint encoding of types, descriptions, and context.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 2681–2690, Copenhagen, Denmark. Association for Computational Linguistics.
  * Hinton et al. (2015) Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. 2015.  Distilling the knowledge in a neural network.  _arXiv preprint arXiv:1503.02531_.
  * Hoffart et al. (2011) Johannes Hoffart, Mohamed Amir Yosef, Ilaria Bordino, Hagen Fürstenau, Manfred Pinkal, Marc Spaniol, Bilyana Taneva, Stefan Thater, and Gerhard Weikum. 2011.  Robust disambiguation of named entities in text.  In _Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing_ , pages 782–792, Edinburgh, Scotland, UK. Association for Computational Linguistics.
  * Humeau et al. (2019) Samuel Humeau, Kurt Shuster, Marie-Anne Lachaux, and Jason Weston. 2019.  Poly-encoders: Architectures and pre-training strategies for fast and accurate multi-sentence scoring.  In _International Conference on Learning Representations_.
  * Humeau et al. (2020) Samuel Humeau, Kurt Shuster, Marie-Anne Lachaux, and Jason Weston. 2020.  Poly-encoders: Architectures and pre-training strategies for fast and accurate multi-sentence scoring.  In _International Conference on Learning Representations_.
  * Izacard and Grave (2021) Gautier Izacard and Edouard Grave. 2021.  Distilling knowledge from reader to retriever for question answering.  In _International Conference on Learning Representations_.
  * Jiang et al. (2022) Y Jiang, Klim Zaporojets, Johannes Deleu, Thomas Demeester, and Chris Develder. 2022\.  Towards consistent document-level entity linking: Joint models for entity linking and coreference resolution.
  * Johnson et al. (2017) Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2017.  Billion-scale similarity search with gpus.  _arXiv preprint arXiv:1702.08734_.
  * Kolitsas et al. (2018) Nikolaos Kolitsas, Octavian-Eugen Ganea, and Thomas Hofmann. 2018.  End-to-end neural entity linking.  In _Proceedings of the 22nd Conference on Computational Natural Language Learning_ , pages 519–529, Brussels, Belgium. Association for Computational Linguistics.
  * Lazic et al. (2015) Nevena Lazic, Amarnag Subramanya, Michael Ringgaard, and Fernando Pereira. 2015\.  Plato: A selective context model for entity resolution.  _Transactions of the Association for Computational Linguistics_ , 3:503–515.
  * Le and Titov (2018) Phong Le and Ivan Titov. 2018.  Improving entity linking by modeling latent relations between mentions.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1595–1604, Melbourne, Australia. Association for Computational Linguistics.
  * Leaman and Lu (2016) Robert Leaman and Zhiyong Lu. 2016.  Taggerone: joint named entity recognition and normalization with semi-markov models.  _Bioinformatics_ , 32(18):2839–2846.
  * Lin et al. (2017) Ying Lin, Chin-Yew Lin, and Heng Ji. 2017.  List-only entity linking.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 536–541, Vancouver, Canada. Association for Computational Linguistics.
  * Ling et al. (2015) Xiao Ling, Sameer Singh, and Daniel S. Weld. 2015.  Design challenges for entity linking.  _Transactions of the Association for Computational Linguistics_ , 3:315–328.
  * (35) Robert L Logan IV, Andrew McCallum, Sameer Singh, and Daniel Bikel.  Benchmarking scalable methods for streaming cross document entity coreference.
  * Logeswaran et al. (2019) Lajanugen Logeswaran, Ming-Wei Chang, Kenton Lee, Kristina Toutanova, Jacob Devlin, and Honglak Lee. 2019.  Zero-shot entity linking by reading entity descriptions.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 3449–3460, Florence, Italy. Association for Computational Linguistics.
  * McNamee and Dang (2009) Paul McNamee and Hoa Trang Dang. 2009.  Overview of the tac 2009 knowledge base population track.  In _Text Analysis Conference (TAC)_ , volume 17, pages 111–113.
  * Milne and Witten (2008) David Milne and Ian H Witten. 2008.  Learning to link with wikipedia.  In _Proceedings of the 17th ACM conference on Information and knowledge management_ , pages 509–518.
  * Mohan and Li (2019) Sunil Mohan and Donghui Li. 2019.  Medmentions: A large biomedical corpus annotated with umls concepts.  _arXiv preprint arXiv:1902.09476_.
  * Nickel and Kiela (2018) Maximillian Nickel and Douwe Kiela. 2018.  Learning continuous hierarchies in the lorentz model of hyperbolic geometry.  In _International Conference on Machine Learning_ , pages 3779–3788. PMLR.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019.  Pytorch: An imperative style, high-performance deep learning library.  In _Advances in Neural Information Processing Systems_.
  * Pershina et al. (2015) Maria Pershina, Yifan He, and Ralph Grishman. 2015.  Personalized page rank for named entity disambiguation.  In _Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 238–243.
  * Radford et al. (2011) Will Radford, Ben Hachey, Matthew Honnibal, Joel Nothman, and James R Curran. 2011\.  Naıve but effective nil clustering baselines–cmcrc at tac 2011.  In _Proceedings of Text Analysis Conference (TAC 2011)_. Citeseer.
  * Raiman and Raiman (2018) Jonathan Raiman and Olivier Raiman. 2018.  Deeptype: multilingual entity linking by neural type system evolution.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32.
  * Ravenscroft et al. (2021) James Ravenscroft, Arie Cattan, Amanda Clare, Ido Dagan, and Maria Liakata. 2021\.  Cd2cr: Co-reference resolution across documents and domains.  _arXiv preprint arXiv:2101.12637_.
  * Singh et al. (2011) Sameer Singh, Amarnag Subramanya, Fernando Pereira, and Andrew McCallum. 2011.  Large-scale cross-document coreference using distributed inference and hierarchical models.  In _Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies_ , pages 793–803, Portland, Oregon, USA. Association for Computational Linguistics.
  * Sung et al. (2020) Mujeen Sung, Hwisang Jeon, Jinhyuk Lee, and Jaewoo Kang. 2020.  Biomedical entity representations with synonym marginalization.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 3641–3650, Online. Association for Computational Linguistics.
  * Tsochantaridis et al. (2004) Ioannis Tsochantaridis, Thomas Hofmann, Thorsten Joachims, and Yasemin Altun. 2004\.  Support vector machine learning for interdependent and structured output spaces.  In _Proceedings of the twenty-first international conference on Machine learning_ , page 104.
  * Wu et al. (2020) Ledell Wu, Fabio Petroni, Martin Josifoski, Sebastian Riedel, and Luke Zettlemoyer. 2020.  Zero-shot entity linking with dense entity retrieval.  In _EMNLP_.
  * Yadav et al. (2019) Nishant Yadav, Ari Kobren, Nicholas Monath, and Andrew Mccallum. 2019.  Supervised hierarchical clustering with exponential linkage.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 6973–6983. PMLR.


Journal of Ramanujan Society of Mathematics and Mathematical Sciences
(JRSMAMS)
Vol. 9, No. 1, December 2021

On entire functions of several variables
with derivatives of even order taking integer values

Michel Waldschmidt

Sorbonne Université and Université de Paris, CNRS, IMJ-PRG, F-75005 Paris,
France.

<EMAIL_ADDRESS>
http://www.imj-prg.fr/~michel.waldschmidt

## Abstract

We extend to several variables an earlier result of ours, according to which
an entire function of one variable of sufficiently small exponential type,
having all derivatives of even order taking integer values at two points, is a
polynomial. The proof in the one dimensional case relies on Lidstone expansion
of the function. For $n$ variables, we need $n+1$ points, having the property
that the differences of $n$ of them with the remaining one give a basis of
${\mathbb{C}}^{n}$. The proof is by reduction to the one variable situation.

### Keywords

Integer valued entire functions, Lidstone polynomials, exponential type,
Pólya’s Theorem, analytic functions of several variables.

AMS Mathematics Subject Classification 2020: 30D15, 41A58.

##  1\. The main result

We denote by ${\mathbb{N}}$ the set $\\{0,1,2,\dots\\}$. For
${\underline{z}}=(z_{1},\dots,z_{n})\in{\mathbb{C}}^{n}$ and
${\underline{t}}=(t_{1},\dots,t_{n})\in{\mathbb{N}}^{n}$, write

${\underline{z}}^{\underline{t}}=z_{1}^{t_{1}}\cdots
z_{n}^{t_{n}},\quad|{\underline{z}}|=\max_{1\leq i\leq
n}|z_{i}|,\quad\|{\underline{t}}\|=t_{1}+\cdots+t_{n},\quad{\underline{t}}!=t_{1}!\cdots
t_{n}!$

and

$D^{\underline{t}}=\left(\frac{\partial}{\partial
z_{1}}\right)^{t_{1}}\cdots\left(\frac{\partial}{\partial
z_{n}}\right)^{t_{n}}.$

For ${\underline{z}}=(z_{1},\dots,z_{n})$ and
${\underline{w}}=(w_{1},\dots,w_{n})$ in ${\mathbb{C}}^{n}$, let
${\underline{w}}{\underline{z}}=w_{1}z_{1}+\cdots+w_{n}z_{n}$. For $r>0$ and
for $f$ an analytic function in a domain containing
$\\{{\underline{z}}\in{\mathbb{C}}^{n}\;\mid\;|{\underline{z}}|\leq r\\}$, set

$|f|_{r}=\sup_{|{\underline{z}}|=r}|f({\underline{z}})|.$

The order of an entire function $f$ is

$\varrho(f)=\limsup_{r\to\infty}\frac{\log\log|f|_{r}}{\log r}$

and its exponential type

$\tau(f)=\limsup_{r\to\infty}\frac{\log|f|_{r}}{r}\cdotp$

Given $\tau>0$, ${\underline{w}}\in{\mathbb{C}}^{n}\setminus\\{0\\}$ and an
entire function $f$ in ${\mathbb{C}}^{n}$, we say that $f$ has _exponential
type $\leq\tau$ in the direction ${\underline{w}}$_ if the function of a
single variable ${\underline{z}}\mapsto f({\underline{w}}{\underline{z}})$ has
order $\leq 1$ and exponential type $\leq\tau$, namely

$\limsup_{r\to\infty}\frac{1}{r}\log\sup_{|{\underline{z}}|\leq
r}|f({\underline{w}}{\underline{z}})|\leq\tau.$

It depends not only on ${\underline{w}}/|{\underline{w}}|$ but also on
$|{\underline{w}}|$.

Let ${\underline{s}}_{0},{\underline{s}}_{1},\dots,{\underline{s}}_{n}$ be
$n+1$ elements in ${\mathbb{C}}^{n}$, such that
$\\{{\underline{s}}_{1}-{\underline{s}}_{0},\dots,{\underline{s}}_{n}-{\underline{s}}_{0}\\}$
is a basis of ${\mathbb{C}}^{n}$ over ${\mathbb{C}}$.

Finally, let ${\mathcal{T}}$ be the set of
$({\underline{t}},i)\in{\mathbb{N}}^{n}\times\\{0,\dots,,n\\}$ satisfying

$\|{\underline{t}}\|\text{ even for all $i=0,1,\dots,n$ and
}~t_{1},\ldots,t_{i}\text{ even for }i=1,\dots,n.$

The main result of this paper is the following.

######  Theorem 1.

Let $f$ be an entire function of $n$ variables having exponential type
$\leq\tau$ in each of the directions ${\underline{s}}_{i}-{\underline{s}}_{0}$
($i=1,\dots,n$) satisfying

$\limsup_{r\to\infty}{\mathrm{e}}^{-r}\sqrt{r}|f|_{r}<\frac{1}{\sqrt{2\pi}}{\mathrm{e}}^{-\max\\{|s_{0}|,\dots,|s_{n}|\\}}.$
(1)

Assume

$(D^{\underline{t}}f)({\underline{s}}_{i})\in{\mathbb{Z}}\text{ for all
$({\underline{t}},i)\in{\mathcal{T}}$.}$ (2)

Then the set of $({\underline{t}},i)\in{\mathcal{T}}$ with
$(D^{\underline{t}}f)({\underline{s}}_{i})\not=0$ is finite. Further, if

$\tau<\pi,$ (3)

then $f$ is a polynomial in ${\mathbb{C}}[{\underline{z}}]$.

The case $n=1$ of Theorem 1 is Corollary 1.2 of [4].

We will see (Corollary 2) that when $K$ is a subfield of ${\mathbb{C}}$ such
that ${\underline{s}}_{i}\in K^{n}$ for all $i=0,1,\dots,n$, then the
conclusion of Theorem 1 is $f\in K[{\underline{z}}]$.

Assumption (1) implies that $f$ has exponential type $\leq 1$. Hence, when

$\max_{1\leq i\leq n}|{\underline{s}}_{i}-{\underline{s}}_{0}|<\pi,$

the hypothesis (3) is a consequence of (1). An example is when
${\underline{s}}_{0}=(0,\dots,0)$ and
$({\underline{s}}_{1},\dots,{\underline{s}}_{n})$ is the canonical basis of
${\mathbb{C}}^{n}$.

Theorem 1 cannot be improved in general. Here are some examples. Assume

${\underline{s}}_{0}=(a_{1},a_{2},\dots,a_{n}),\;{\underline{s}}_{i}={\underline{s}}_{0}+(b_{i}-a_{i}){\underline{e}}_{i}\quad(i=1,\dots,n),$

where $a_{i}$ and $b_{i}$ are complex numbers with $a_{i}\not=b_{i}$ for
$1\leq i\leq n$, while ${\underline{e}}_{1},\dots,{\underline{e}}_{n}$ is the
canonical basis of ${\mathbb{C}}^{n}$. Our first example is the function

$\sin\left(\pi\frac{z_{1}-a_{1}}{b_{1}-a_{1}}+\cdots+\pi\frac{z_{n}-a_{n}}{b_{n}-a_{n}}\right),$

which has exponential type $\leq\pi$ in each of the directions
${\underline{s}}_{i}-{\underline{s}}_{0}$ ($i=1,\dots,n$) and satisfies
$(D^{\underline{t}}f)({\underline{s}}_{i})=0$ for $i=0,1,\dots,n$ and for any
${\underline{t}}\in{\mathbb{N}}^{n}$ with $\|{\underline{t}}\|$ even.

For our second example, we define
${\underline{\theta}}:{\mathbb{C}}^{n}\to{\mathbb{C}}^{n}$ as follows

${\underline{\theta}}({\underline{z}})=\left(\frac{z_{1}-a_{1}}{b_{1}-a_{1}},\dots,\frac{z_{n}-a_{n}}{b_{n}-a_{n}}\right).$

For $1\leq i\leq n-1$, let $g_{i}$ be a polynomial in $n-i$ variables with
complex coefficients, and let $g_{n}$ be a polynomial in a single variable
with complex coefficients. Consider the entire function of $n$ variables
${\underline{w}}=(w_{1},\dots,w_{n})$:

$\varphi({\underline{w}})=\sum_{i=1}^{n-1}\sin(\pi
w_{i})g_{i}(w_{i+1}^{2},\dots,w_{n}^{2})+\sin(\pi w_{n})g_{n}(w_{n-1}^{2}).$

Then the function

$f({\underline{z}})=\varphi\circ{\underline{\theta}}({\underline{z}})$

has exponential type $\leq\pi$ in each of the directions
${\underline{s}}_{i}-{\underline{s}}_{0}$ ($i=1,\dots,n$) and satisfies
$(D^{\underline{t}}f)({\underline{s}}_{i})=0$ for all
$({\underline{t}},i)\in{\mathcal{T}}$.

For our third example, we keep the same notation for ${\underline{s}}_{i}$ and
${\underline{\theta}}$, we assume that
$a_{i}-b_{i}\not\in\pi{\mathrm{i}}{\mathbb{Z}}$ for $1\leq i\leq n$, we also
assume that the polynomials $g_{i}$ have integer coefficients and we set

$\psi({\underline{w}})=\sum_{i=1}^{n-1}\frac{\sinh(w_{i}-b_{i})}{\sinh(a_{i}-b_{i})}g_{i}(w_{i+1}^{2},\dots,w_{n}^{2})+\frac{\sinh(w_{n}-b_{n})}{\sinh(a_{n}-b_{n})}g_{n}(w_{n-1}^{2}).$

Then the function

$f({\underline{z}})=\psi\circ{\underline{\theta}}({\underline{z}})$

has exponential type $\leq 1$ in each of the directions
${\underline{s}}_{i}-{\underline{s}}_{0}$ ($i=1,\dots,n$) and satisfies
$(D^{\underline{t}}f)({\underline{s}}_{i})\in{\mathbb{Z}}$ for all
$({\underline{t}},i)\in{\mathcal{T}}$.

Another reason for which Theorem 1 is optimal is the following. If we relax
the assumption (2) by requiring that it holds outside a finite subset of
${\mathcal{T}}$, the conclusion that $f$ is a polynomial is still valid - this
follows easily from Theorem 1. But if we impose the conditions (2) only
outside an infinite subset of ${\mathcal{T}}$, then the conclusion is no more
valid. We come back to this issue in the remark at the end of § 3.

##  2\. An extension of a result due to Pólya

The proof of the first part of Theorem 1 rests on Proposition 1, which is an
extension to several variables of Proposition 2.2 of [4].

We will use Cauchy’s inequalities for an analytic function of several
variables ([2, Theorem 2.2.7 p. 27]). Let $r>0$, let
${\underline{t}}\in{\mathbb{N}}^{n}$ with $\|{\underline{t}}\|=T$ and let $f$
be analytic in a domain containing
$\\{{\underline{z}}\in{\mathbb{C}}^{n}\;\mid\;|{\underline{z}}|\leq r\\}$.
Then

$\frac{|(D^{\underline{t}}f)(0)|}{{\underline{t}}!}r^{T}\leq|f|_{r}.$

We deduce that for ${\underline{z}}_{0}\in{\mathbb{C}}^{n}$ and for $f$
analytic in a domain containing

$\\{{\underline{z}}\in{\mathbb{C}}^{n}\;\mid\;|{\underline{z}}|\leq
r+|{\underline{z}}_{0}|\\},$

we have

$\frac{|(D^{\underline{t}}f)({\underline{z}}_{0})|}{{\underline{t}}!}r^{T}\leq|f|_{r+|{\underline{z}}_{0}|}.$
(4)

We will also use Stirling’s Formula:

$N^{N}{\mathrm{e}}^{-N}\sqrt{2\pi N}<N!<N^{N}{\mathrm{e}}^{-N}\sqrt{2\pi
N}{\mathrm{e}}^{1/(12N)},$ (5)

which is valid for all $N\geq 1$.

######  Proposition 1.

Let $f$ be an entire function in ${\mathbb{C}}^{n}$ and let $A\geq 0$. Assume

$\limsup_{r\to\infty}{\mathrm{e}}^{-r}\sqrt{r}|f|_{r}<\frac{{\mathrm{e}}^{-A}}{\sqrt{2\pi}}\cdotp$
(6)

Then there exists $T_{0}>0$ such that, for
${\underline{t}}\in{\mathbb{N}}^{n}$ with $\|{\underline{t}}\|\geq T_{0}$, we
have

$|D^{\underline{t}}f|_{A}<1.$

###### Proof.

From assumption (6), it follows that there exists $\eta>0$ such that, for $T$
sufficiently large, we have

$|f|_{T}<(1-\eta)\frac{{\mathrm{e}}^{T-A}}{\sqrt{2\pi T}}\cdotp$

Let ${\underline{t}}\in{\mathbb{N}}^{n}$ with $\|{\underline{t}}\|=T$. We use
Cauchy’s inequalities (4) with $r=T-A$: since ${\underline{t}}!\leq T!$, for
$|{\underline{z}}|\leq A$ we have

$|(D^{\underline{t}}f)({\underline{z}})|\leq\frac{T!}{(T-A)^{T}}|f|_{T}.$

Hence the upper bound for $T!$ given by the right hand side of (5) yields

$\sup_{|{\underline{z}}|\leq
A}|(D^{\underline{t}}f)({\underline{z}})|\leq(1-\eta){\mathrm{e}}^{-A+1/(12T)}\left(1-\frac{A}{T}\right)^{-T}.$

For $T$ sufficiently large, the right hand side is $<1$. ∎

We deduce the following extension to several variables of Corollary 2.4 of
[4].

######  Corollary 1.

Let $f$ be a transcendental entire function in ${\mathbb{C}}^{n}$. Let $A\geq
0$. Assume (6). Then the set

$\bigl{\\{}({\underline{t}},{\underline{z}}_{0})\in{\mathbb{N}}^{n}\times{\mathbb{C}}^{n}\;\mid\;|{\underline{z}}_{0}|\leq
A,\;(D^{\underline{t}}f)({\underline{z}}_{0})\in{\mathbb{Z}}\setminus\\{0\\}\bigr{\\}}$

is finite.

##  3\. A special case:
$({\underline{s}}_{0},{\underline{s}}_{1},\dots,{\underline{s}}_{n})=({\underline{e}}_{0},{\underline{e}}_{1},\dots,{\underline{e}}_{n})$

Set ${\underline{e}}_{0}=(0,\dots,0)\in{\mathbb{C}}^{n}$ and denote, as
before, by $\\{{\underline{e}}_{1},\dots,{\underline{e}}_{n}\\}$ the canonical
basis of ${\mathbb{C}}^{n}$:

${\underline{e}}_{ij}=\delta_{ij}\quad(1\leq i,j\leq n).$

We will say that an entire function $f$ in ${\mathbb{C}}^{n}$ has _exponential
type $\leq\tau$ in each of the variables_ if it has exponential type
$\leq\tau$ in each of the directions
${\underline{e}}_{1},\dots,{\underline{e}}_{n}$: in other words, for any
$i=1,\dots,n$ and any
$(z_{1},\dots,z_{i-1},z_{i+1},\dots,z_{n})\in{\mathbb{C}}^{n-1}$,

$\limsup_{r\to\infty}\frac{1}{r}\log\sup_{|z_{i}|\leq
r}|f(z_{1},\dots,z_{n})|\leq\tau.$

The main result of this section is the following.

######  Proposition 2.

Let $f$ be an entire function in ${\mathbb{C}}^{n}$ of exponential type $<\pi$
in each of the variables. Assume

$(D^{\underline{t}}f)({\underline{e}}_{i})=0\text{ for all
}({\underline{t}},i)\in{\mathcal{T}}.$ (7)

Then $f=0$.

The case $n=1$ of Proposition 2 is a result due to Poritsky (cf. [3] and [4, §
3.1]). We will prove Proposition 2 by induction on $n$, starting with and
including the case $n=1$. The proof in the one dimensional case will use the
following two well known lemmas dealing with univariate functions.

######  Lemma 1.

Let $f$ be an entire function in ${\mathbb{C}}$. The two following conditions
are equivalent:
(i) The function $f$ is periodic of period $\omega\not=0$ ;
(ii) There exists a function $g$ analytic in ${\mathbb{C}}^{\times}$ such that
$f(z)=g({\mathrm{e}}^{2\pi{\mathrm{i}}z/\omega})$.

###### Proof.

Clearly (ii) implies (i). Assume (i). The map
$z\mapsto{\mathrm{e}}^{\pi{\mathrm{i}}z}$ is analytic and surjective. The
condition
${\mathrm{e}}^{\pi{\mathrm{i}}z_{1}}={\mathrm{e}}^{\pi{\mathrm{i}}z_{2}}$
implies $f(z_{1})=f(z_{2})$. Hence there exists a unique map
$g:{\mathbb{C}}^{\times}\to{\mathbb{C}}$ such that
$g({\mathrm{e}}^{2\pi{\mathrm{i}}z})=f(z)$.

<EMAIL_ADDRESS>
Let $w\in{\mathbb{C}}^{\times}$ and let $z\in{\mathbb{C}}$ be such that
$w={\mathrm{e}}^{2\pi{\mathrm{i}}z}$. From $g(w)=f(z)$ it follows that $g$ is
holomorphic, hence analytic, in ${\mathbb{C}}^{\times}$.

This proves lemma 1. ∎

######  Lemma 2.

If $g$ is an analytic function in ${\mathbb{C}}^{\times}$, if $\omega$ is a
nonzero complex number and if the entire function
$g({\mathrm{e}}^{2\pi{\mathrm{i}}z/\omega})$ has an exponential type
$<2(N+1)\pi/|\omega|$ for some nonnegative integer $N$, then $w^{N}g(w)$ is a
polynomial of degree $\leq 2N$.

As a consequence, if $g({\mathrm{e}}^{2\pi{\mathrm{i}}z/\omega})$ has a type
$<2\pi/|\omega|$, then $g$ is constant.

###### Proof.

Assume that the function $f(z)=g({\mathrm{e}}^{2\pi{\mathrm{i}}z/\omega})$ has
an exponential type $\tau$ with $\tau<2(N+1)\pi/|\omega|$. Let
$w\in{\mathbb{C}}^{\times}$. Write $w=|w|{\mathrm{e}}^{i\theta}$ with
$|\theta|\leq\pi$. Set

$z=\frac{\omega}{2\pi{\mathrm{i}}}(\log|w|+i\theta),$

so that $w={\mathrm{e}}^{2\pi{\mathrm{i}}z/\omega}$. For any $\epsilon_{1}>0$,
we have

$|z|\leq\left(\frac{\omega}{2\pi}+\epsilon_{1}\right)|\log|w||$

for sufficiently large $|w|$ and also for sufficiently small $|w|$. We deduce

$\log|g(w)|=\log|f(z)|\leq(\tau+\epsilon_{2})|z|\leq\left(\frac{\omega\tau}{2\pi}+\epsilon_{3}\right)|\log|w||.$

Hence if $\alpha$ satisfy $\frac{\tau|\omega|}{2\pi}<\alpha<N+1$, then
$|g|_{r}\leq r^{\alpha}$ for sufficiently large $r$ and $|g|_{r}\leq
r^{-\alpha}$ for sufficiently small $r>0$ . Consider the Laurent expansion of
$g$ at the origin:

$g(w)=\sum_{n\in{\mathbb{Z}}}b_{n}w^{n}.$

From

$b_{n}=\frac{1}{2\pi}\int_{|w|=r}g(w)\frac{{\mathrm{d}}w}{w^{n+1}}$

we deduce Cauchy’s inequalities

$|b_{n}|r^{n}\leq\frac{1}{2\pi}|g|_{r}.$

For $n>N$, we use these inequalities with $r\to\infty$ while for $n<-N$, we
use these inequalities with $r\to 0$. We deduce $b_{n}=0$ for $|n|\geq N+1$.
Hence

$g(w)=\frac{1}{w^{N}}A(w)+B(w)$

where $A$ and $B$ are polynomials of degree $\leq N$. ∎

###### Proof of Proposition 2.

We start by proving the case $n=1$ of Proposition 2, due to Poritsky. So let
$f$ be an entire function of a single variable of exponential type $<\pi$
satisfying $f^{(t)}(0)=f^{(t)}(1)=0$ for all even $t\geq 0$. We claim that
this implies $f=0$.

Indeed, from the assumptions it follows that the functions $f(z)$ and $f(1-z)$
are odd, hence $f(z)$ is periodic of period $2$. Lemma 1 gives the existence
of an entire function $g$ such that $f(z)=g({\mathrm{e}}^{\pi{\mathrm{i}}z})$.
Since $f(z)$ has exponential type $<\pi$, Lemma 2 implies that $g$ is a
constant, hence $f$ also. From $f(0)=0$ we conclude $f=0$.

We now prove Proposition 2 by induction on the number $n$ of variables. Let
$n\geq 2$ and let

$f({\underline{z}})=\sum_{{\underline{k}}\in{\mathbb{N}}^{n}}a_{\underline{k}}{\underline{z}}^{\underline{k}}$

be an entire function of $n$ variables of exponential type $<\pi$ in each of
the variables satisfying

$(D^{\underline{t}}f)({\underline{e}}_{i})=0\text{ for all
$({\underline{t}},i)\in{\mathcal{T}}$.}$

For $k_{n}\geq 0$, define an entire function $f_{k_{n}}$ of $n-1$ variables,
having exponential type $<\pi$ in each of the $n-1$ variables, by setting

$f_{k_{n}}(z_{1},\dots,z_{n-1})=\sum_{(k_{1},\dots,k_{n-1})\in{\mathbb{N}}^{n-1}}a_{\underline{k}}z_{1}^{k_{1}}\cdots
z_{n-1}^{k_{n-1}}=k_{n}!\left(\frac{\partial}{\partial
z_{n}}\right)^{k_{n}}f(z_{1},\dots,z_{n-1},0),$

so that

$f({\underline{z}})=\sum_{k_{n}\geq
0}f_{k_{n}}(z_{1},\dots,z_{n-1})z_{n}^{k_{n}}.$

Let $k_{n}\geq 0$ be even. For each
$(t_{1},\dots,t_{n-1})\in{\mathbb{N}}^{n-1}$, we have

$\left(\frac{\partial}{\partial
z_{1}}\right)^{t_{1}}\cdots\left(\frac{\partial}{\partial
z_{n-1}}\right)^{t_{n-1}}f_{k_{n}}(z_{1},\dots,z_{n-1})=k_{n}!(D^{t_{1},\dots,t_{n-1},k_{n}}f)(z_{1},\dots,z_{n-1},0).$

If $((t_{1},\dots,t_{n-1}),i)\in{\mathbb{N}}^{n-1}\times\\{0,1,\dots,n-1\\}$
is such that $t_{1}+\cdots+t_{n-1}$ is even and $t_{1},\dots,t_{i}$ are even,
then $((t_{1},\dots,t_{n-1},k_{n}),i)\in{\mathcal{T}}$. From the assumption we
deduce

$(D^{t_{1},\dots,t_{n-1},k_{n}}f)({\underline{e}}_{i})=0.$

Using the induction hypothesis for $n-1$ variables, we deduce $f_{k_{n}}=0$
for all ${\underline{k}}\in{\mathbb{N}}^{n}$ with $k_{n}$ even, hence
$a_{\underline{k}}=0$ for all ${\underline{k}}\in{\mathbb{N}}^{n}$ with
$k_{n}$ even.

Since ${\underline{e}}_{n-1}$ and ${\underline{e}}_{n}$ play the same role, we
also have $a_{\underline{k}}=0$ for all ${\underline{k}}\in{\mathbb{N}}^{n}$
with $k_{n-1}$ even. Therefore the condition $a_{\underline{k}}\not=0$ implies
that $k_{n-1}$ and $k_{n}$ are both odd, and this implies that $k_{n-1}+k_{n}$
is even.

We now complete the proof of Proposition 2 in the case $n=2$: the hypothesis

$(D^{k_{1},k_{2}}f)(0,0)=0\text{ for all ($k_{1},k_{2})\in{\mathbb{N}}^{2}$
with $k_{1}+k_{2}$ even }$

implies $a_{k_{1},k_{2}}=0$ for all ($k_{1},k_{2})\in{\mathbb{N}}^{2}$ with
$k_{1}$ and $k_{2}$ both odd, hence, using what we already proved,
$a_{k_{1},k_{2}}=0$ for all ($k_{1},k_{2})\in{\mathbb{N}}^{2}$, and therefore
$f=0$.

Finally, assume $n\geq 3$. Let us fix $k_{n-1}$ and $k_{n}$, both odd, and
consider the entire function of $n-2$ variables

$\displaystyle f_{k_{n-1},k_{n}}(z_{1},\dots,z_{n-2})$
$\displaystyle=\sum_{(k_{1},\dots,k_{n-2})\in{\mathbb{N}}^{n-2}}a_{\underline{k}}z_{1}^{k_{1}}\cdots
z_{n-2}^{k_{n-2}}$
$\displaystyle=k_{n-1}!k_{n}!\left(\left(\frac{\partial}{\partial
z_{n-1}}\right)^{k_{n-1}}\left(\frac{\partial}{\partial
z_{n}}\right)^{k_{n}}f\right)(z_{1},\dots,z_{n-2},0,0).$

If $t_{1}+\cdots+t_{n-2}$ is even, if $i$ satisfies $0\leq i\leq n-2$ and if
$t_{1},\dots,t_{i}$ are even, then
$((t_{1},\dots,t_{n-2},k_{n-1},k_{n}),i)\in{\mathcal{T}}$. From the induction
hypothesis with $n-2$ variables, we deduce that this function
$f_{k_{n-1},k_{n}}$ is $0$. Hence $a_{\underline{k}}=0$ for all
${\underline{k}}\in{\mathbb{N}}^{n}$, and finally $f=0$. ∎

######  Remark.

Using Proposition 2, one can prove that there exists a unique family of
polynomials $\Lambda_{{\underline{t}},i}\in{\mathbb{C}}[{\underline{z}}]$
($({\underline{t}},i)\in{\mathcal{T}}$) which satisfy, for all
$({\underline{\tau}},j)\in{\mathcal{T}}$ and
$({\underline{t}},i)\in{\mathcal{T}}$,

$(D^{\underline{\tau}}\Lambda_{{\underline{t}},i})({\underline{e}}_{j})=\delta_{{\underline{t}},{\underline{\tau}}}\delta_{ij}.$

These polynomials generalize Lidstone polynomials to several variables. In a
forthcoming paper [5], we study these polynomials and we prove that any entire
function $f$ in ${\mathbb{C}}^{n}$ of exponential type $<\pi$ in each variable
is the sum of a series

$f({\underline{z}})=\sum_{({\underline{t}},i)\in{\mathcal{T}}}(D^{\underline{t}}f)({\underline{e}}_{i})\Lambda_{{\underline{t}},i}({\underline{z}}).$

This generalizes a result of Poritsky (cf. [3] and [4, § 3.1]) for univariate
entire functions.

In [5], we also show that if ${\mathcal{T}}^{\prime}$ is a subset of
${\mathcal{T}}$ such that ${\mathcal{T}}\setminus{\mathcal{T}}^{\prime}$ is
infinite, then there exists an uncountable set of transcendental entire
functions $f$ of exponential type $0$ such that
$(D^{\underline{t}}f)({\underline{e}}_{i})=0$ for all
$({\underline{t}},i)\in{\mathcal{T}}^{\prime}$.

##  4\. Change of coordinates

We deduce from Proposition 2 the following result

######  Proposition 3.

An entire function $f$ in ${\mathbb{C}}^{n}$ of exponential type $<\pi$ in
each of the directions ${\underline{s}}_{i}-{\underline{s}}_{0}$
($i=1,\dots,n$) which satisfies

$(D^{\underline{t}}f)({\underline{s}}_{i})=0$ (8)

for all $({\underline{t}},i)\in{\mathcal{T}}$ is the zero function.

###### Proof.

Set

$\tilde{f}(z_{1},\dots,z_{n})=f\bigl{(}{\underline{s}}_{0}+({\underline{s}}_{1}-{\underline{s}}_{0})z_{1}+\cdots+({\underline{s}}_{n}-{\underline{s}}_{0})z_{n}\bigr{)}.$

Since
$\\{{\underline{s}}_{1}-{\underline{s}}_{0},\dots,{\underline{s}}_{n}-{\underline{s}}_{0}\\}$
is a basis of ${\mathbb{C}}^{n}$, the condition $f=0$ is equivalent to
$\tilde{f}=0$ and the conditions (8) for $f$ are equivalent to the conditions
(7) for $\tilde{f}$. From the assumption on the exponential type of $f$ we
deduce that the function $\tilde{f}$ has exponential type $<\pi$ in each of
the variables. Hence Proposition 3 follows from Proposition 2. ∎

######  Corollary 2.

Let $K$ be a field containing all coordinates of
${\underline{s}}_{0},{\underline{s}}_{1},\dots,{\underline{s}}_{n}$. A
polynomial $f\in{\mathbb{C}}[{\underline{z}}]$ which satisfies (2) for
$({\underline{t}},i)\in{\mathcal{T}}$ belongs to $K[{\underline{z}}]$.

###### Proof.

For $({\underline{t}},i)\in{\mathcal{T}}$, set
$a_{{\underline{t}},i}=(D^{\underline{t}}f)({\underline{s}}_{i})$. Since $f$
is a polynomial, the set of $({\underline{t}},i)\in{\mathcal{T}}$ such that
$a_{{\underline{t}},i}\not=0$ is finite. By assumption,
$a_{{\underline{t}},i}\in{\mathbb{Z}}$. Proposition 2 shows that $f$ is the
unique polynomial satisfying
$(D^{\underline{t}}f)({\underline{s}}_{i})=a_{t,i}$ for all
$({\underline{t}},i)\in{\mathcal{T}}$. Hence the coefficients of the
polynomial $f$ are the unique solution to a system of linear equations with
coefficients in $K$. Therefore these coefficients are in $K$. ∎

##  5\. Proof of Theorem 1

The proof of Theorem 1 will use the following easy Lemma:

######  Lemma 3.

Let $f$ be an analytic function at $0$ in ${\mathbb{C}}^{n}$ and let $D$ be a
positive integer. Assume that for all ${\underline{t}}\in(2{\mathbb{N}})^{n}$
with $\|{\underline{t}}\|=D$, we have

$D^{\underline{t}}f=0.$

Then $f$ is a polynomial of total degree $<D+n$;

###### Proof.

Assume $f$ satisfies the assumptions of Lemma 3. For
${\underline{\nu}}=(\nu_{1},\dots,\nu_{n})\in\\{0,1\\}^{n}$, we have
$D^{{\underline{t}}+{\underline{\nu}}}f=0$. Hence $D^{\underline{\tau}}f=0$
for all ${\underline{\tau}}\in{\mathbb{N}}^{n}$ satisfying
$\|{\underline{\tau}}\|=D+n$. This implies $(D^{\underline{k}}f)(0)=0$ for all
${\underline{k}}\in{\mathbb{N}}^{n}$ with $\|{\underline{k}}\|\geq D+n$. The
conclusion follows. ∎

###### Proof of Theorem 1.

Assume that $f$ satisfies the assumptions of Theorem 1. Given the growth
assumption (1), Proposition 1 shows that the set of $({\underline{t}},i)$ with
${\underline{t}}\in{\mathbb{N}}^{n}$, $i=0,1,\dots,n$ and

$\left|(D^{\underline{t}}f)({\underline{s}}_{i})\right|<1$

is finite. Therefore there exists an even integer $T_{0}$ such that, for
$\|{\underline{t}}\|\geq T_{0}$ and $0\leq i\leq n$ with
$({\underline{t}},i)\in{\mathcal{T}}$, we have
$(D^{\underline{t}}f)({\underline{s}}_{i})=0$.

Let $\tau_{1},\dots,\tau_{n}$ be even integers with
$\|{\underline{\tau}}\|\geq T_{0}$. Denote by $\hat{f}$ the function
$D^{\underline{\tau}}f$. For $({\underline{t}},i)\in{\mathcal{T}}$, we have
$({\underline{t}}+{\underline{\tau}},i)\in{\mathcal{T}}$ and
$\|{\underline{t}}+{\underline{\tau}}\|\geq T_{0}$, hence
$(D^{\underline{t}}\hat{f})({\underline{s}}_{i})=(D^{{\underline{t}}+{\underline{\tau}}}f)({\underline{s}}_{i})=0$.
Assuming that the exponential type of $f$ is $<\pi$ in each direction
${\underline{s}}_{i}-{\underline{s}}_{0}$, we deduce the same for $\hat{f}$,
and then Proposition 3 implies $\hat{f}=0$. Hence $D^{\underline{\tau}}f=0$
for all $\tau_{1},\dots,\tau_{n}$ even integers with
$\|{\underline{\tau}}\|\geq T_{0}$. It follows from Lemma 3 that $f$ is a
polynomial of total degree $<T_{0}+n$. ∎

## References

  * [1]
  * [2] Hörmander, L.  An introduction to complex analysis in several variables.  D. Van Nostrand Co., Inc., Princeton, N.J.-Toronto, Ont.-London, 1966\. MR Zbl
  * [3] Poritsky, H.  On certain polynomial and other approximations to analytic functions.  Trans. Amer. Math. Soc. 34:2 (1932), 274–331. MR Zbl
  * [4] Waldschmidt, M.  On transcendental entire functions with infinitely many derivatives taking integer values at two points. Southeast Asian Bulletin of Mathematics, Vol.45(3) (2021), 379–408.
arXiv: 1912.00173 [math.NT].

  * [5] Waldschmidt, M.  Multivariate Lidstone interpolation.  In preparation.