tcb@breakable

# An $\tilde{\Omega}\big{(}\sqrt{\log|T|}\big{)}$ Lower Bound for Steiner
Point Removal

Yu Chen EPFL, Lausanne, Switzerland. Email<EMAIL_ADDRESS>Supported by ERC
Starting Grant 759471. Zihan Tan Rutgers University, NJ, USA. Email:
<EMAIL_ADDRESS>Supported by a grant to DIMACS from the Simons
Foundation (820931).

In the Steiner point removal (SPR) problem, we are given a (weighted) graph
$G$ and a subset $T$ of its vertices called terminals, and the goal is to
compute a (weighted) graph $H$ on $T$ that is a minor of $G$, such that the
distance between every pair of terminals is preserved to within some small
multiplicative factor, that is called the _stretch_ of $H$.

It has been shown that on general graphs we can achieve stretch $O(\log|T|)$
[Filtser, 2018]. On the other hand, the best-known stretch lower bound is $8$
[Chan-Xia-Konjevod-Richa, 2006], which holds even for trees. In this work, we
show an improved lower bound of $\tilde{\Omega}\big{(}\sqrt{\log|T|}\big{)}$.

##  1 Introduction

In the Steiner point removal (SPR) problem, we are given an undirected
weighted graph $G$ and a subset $T$ of its vertices called _terminals_ , and
the goal is to compute a minor $H$ of $G$ with $V(H)=T$ (and arbitrary edge
weights), such that for every pair $t,t^{\prime}\in T$,

$\textnormal{{dist}}_{G}(t,t^{\prime})\leq\textnormal{{dist}}_{H}(t,t^{\prime})\leq\alpha\cdot\textnormal{{dist}}_{G}(t,t^{\prime})$

for some small real number $\alpha\geq 1$, that is called the _stretch_ of the
SPR solution $H$.

The SPR problem was first proposed by Gupta [Gup01], who proved that trees
admit SPR solutions with stretch at most $8$, which was later shown to be
tight [CXKR06]. Later, Kamma, Nguyen, and Krauthgamer [KNZ14] showed that on
general graphs we can achieve stretch $O(\log^{5}|T|)$, and this was later
improved by Cheung [Che18] to $O(\log^{2}|T|)$ and further by Filtser [Fil18]
to $O(\log|T|)$.

There has also been an exciting line of work on achieving $O(1)$-stretch for
special types of graphs, especially minor-free graphs. Basu and Gupta [BG08]
showed that outerplanar graphs (graphs excluding $K_{2,3}$ and $K_{4}$ minor)
admit $O(1)$-stretch SPR solutions. Filtser [Fil20] reduced constructing SPR
solutions to computing scattering partitions. Building upon this, Hershkowitz
and Li [HL21] showed that series-parallel graphs (graphs excluding $K_{4}$
minor) admit SPR solutions with $O(1)$ stretch, and in a very recent sequence
of breakthrough papers, Chang et al [CCL+23a, CCL+23b, CCL+23c] finally showed
that minor-free graphs admit $O(1)$-stretch SPR solutions.

However, after all this amazing progress on the upper bound side, the best-
known stretch lower bound for general graphs remains $8$, which holds even for
trees [CXKR06]. In this work, we prove the first superconstant lower bound for
general graphs. Our main result can be summarized as the following theorem.

######  Theorem 1.

For any large enough integer $k>0$, there exists a graph $G$ and a subset
$T\subseteq V(G)$ of $k$ terminals, such that any SPR solution $H$ of $G$ with
respect to $T$ has stretch $\Omega(\sqrt{\log k/\log\log k})$.

Our lower bound is polynomially related to the best upper bound of $O(\log k)$
on general graphs. Closing this gap remains an interesting open problem.

##  2 Preliminaries

By default, all logarithms are to the base of $2$.

Let $G=(V,E)$ be an edge-weighted graph. For a pair $v,v^{\prime}$ of vertices
in $G$, we denote by $\textnormal{{dist}}_{G}(v,v^{\prime})$ the shortest-path
distance between $v,v^{\prime}$ in $G$. Let $P$ be a path in $G$. We denote by
$|P|$ its length (the total weight of all its edges). The _girth_ of $G$,
denoted by $\textnormal{{girth}}(G)$, is defined as the minimum length of any
cycle in $G$. We use the following observation.

######  Observation 2.

Let $P$ be a shortest path in $G$ connecting a pair $u,v$ of its vertices, and
let $Q$ be another $u$-$v$ path (possibly non-simple) in $G$. Then either
$P\subseteq Q$, or $|P|+|Q|\geq\textnormal{{girth}}(G)$.

###### Proof.

Assume that $P\not\subseteq Q$, and we will show that $P\cup Q$ contains a
cycle, which implies 2. Let $e$ be an edge in $P\setminus Q$. Note that the
(multi-)graph $P\cup Q$ can be viewed as a non-simple cycle (from $u$ to $v$
along $P$, and then back to $u$ along the reverse of $Q$). We iteratively
remove from it two copies of an edge that appear more than once in $P\cup Q$
until we cannot do so. It is easy to show that throughout the process the
graph is always the union of several disjoint cycles, and in the end the graph
consists of simple cycles and is non-empty (as edge $e$ will never get
removed). Therefore, $P\cup Q$ contains a cycle. ∎

### Minors and image paths.

Let $G$ be a graph. We say that a graph $H$ is a _minor_ of $G$, iff $H$ can
be obtained from $G$ by edge deletions, vertex deletions and edge
contractions. We have the following immediate observation.

######  Observation 3.

If $H$ is a minor of $G$, then $|E(H)|\leq|E(G)|$.

Recall that a SPR solution $H$ of $G$ is a minor of $G$ with $V(H)=T$, and $H$
can be edge-weighted. Let $P=(t_{0},\ldots,t_{r})$ be a shortest path in $H$
connecting $t_{0}$ to $t_{r}$. We define its _image path_ in $G$ as follows.
For each index $0\leq i\leq r-1$, we denote by $R_{i}$ the $t_{i}$-$t_{i+1}$
shortest path in $G$. We let $R$ be the sequential concatenation of paths
$R_{0},\ldots,R_{r-1}$, so $R$ is a path (possibly non-simple) in $G$
connecting $t_{0}$ to $t_{r}$. We use the following simple observations.

######  Observation 4.

The length of edge $(t_{i},t_{i+1})$ in $H$ is at least
$\textnormal{{dist}}_{G}(t_{i},t_{i+1})$.

###### Proof.

This is simply because
$\textnormal{{dist}}_{G}(t,t^{\prime})\leq\textnormal{{dist}}_{H}(t,t^{\prime})$
is required for all pairs $t,t^{\prime}\in T$. ∎

######  Corollary 5.

$\textnormal{{dist}}_{H}(t_{0},t_{r})\geq|R|\geq\textnormal{{dist}}_{G}(t_{0},t_{r})$.

###### Proof.

On the one hand, from 4,

$\textnormal{{dist}}_{H}(t_{0},t_{r})=\sum_{0\leq i\leq
r-1}\textnormal{{dist}}_{H}(t_{i},t_{i+1})\geq\sum_{0\leq i\leq
r-1}\textnormal{{dist}}_{G}(t_{i},t_{i+1})=\sum_{0\leq i\leq r-1}|R_{i}|=|R|.$

On the other hand, $R$ is a path in $G$ connecting $t_{0}$ to $t_{r}$, so
$|R|\geq\textnormal{{dist}}_{G}(t_{0},t_{r})$. ∎

##  3 Proof of Theorem 1

Recall that we are given a large enough integer $k$. Throughout, we set
$M=\left\lfloor\sqrt{\log k\cdot\log\log k}\right\rfloor$.

We construct the hard instance as follows. Let $G^{\prime}$ be a $3$-regular
graph on $k$ vertices with girth at least $(\log k)/10$ (such graphs are known
to exist, see e.g., [AGS21]). We then add to $G^{\prime}$, for each vertex
$u\in V(G^{\prime})$, a new vertex $t_{u}$ that is connected to $u$ by a
single edge $(u,t_{u})$. The resulting graph is denoted by $G$. Each edge in
$E(G^{\prime})$ has weight $1$, and each new edge $(u,t_{u})$ has weight $M$.
The terminal set is defined to be $T=\left\\{t_{u}\mid u\in
V(G^{\prime})\right\\}$111We remark that our construction is similar to the
“expander with tails” graph used in [CKR05] for analyzing the integrality gap
of the semi-metric relaxation LP for the $0$-Extension problem. But our
analysis here is quite different from theirs..

Instead of directly proving Theorem 1, we will in fact prove the following
stronger lemma, which, together with 3 and 4, immediately imply that any SPR
solution of the instance $(G,T)$ has stretch $\Omega(\sqrt{\log k/\log\log
k})$, thereby proving Theorem 1.

######  Lemma 6.

Let $H$ be a graph on $T$ such that (i) $|E(H)|\leq|E(G)|$; and (ii) every
edge $(t,t^{\prime})$ in $H$ has length at least
$\textnormal{{dist}}_{G}(t,t^{\prime})$. Then there exists a pair
$t,t^{\prime}\in T$, such that

$\textnormal{{dist}}_{H}(t,t^{\prime})\geq\Omega(\sqrt{\log k/\log\log
k})\cdot\textnormal{{dist}}_{G}(t,t^{\prime}).$

From now on we focus on proving Lemma 6.

We define ${\mathcal{Q}}$ to be the set of paths $Q$ in $G$, such that

  * •

$Q$ is the image path of a single edge $(t_{u},t_{v})$ in $H$; and

  * •

$\textnormal{{dist}}_{G}(t_{u},t_{v})\leq\log k/100$.

We say a path $P$ in $G$ is _covered_ by a collection
${\mathcal{Q}}^{\prime}\subseteq{\mathcal{Q}}$ of paths, iff
$P\subseteq\bigcup_{Q\in{\mathcal{Q}}^{\prime}}Q$. For such a path $P$, we
denote by ${\mathsf{cov}}(P)$ be the minimum number of paths we need in
${\mathcal{Q}}$ to cover $P$. That is,
${\mathsf{cov}}(P)=\min\left\\{|{\mathcal{Q}}^{\prime}|\mid{\mathcal{Q}}^{\prime}\subseteq{\mathcal{Q}},P\text{
covered by }{\mathcal{Q}}\right\\}$. We prove the following lemma.

######  Lemma 7.

There is a path $P$ in $G^{\prime}$ of length $M$ such that
${\mathsf{cov}}(P)=\Omega(M/\log\log k)$.

###### Proof.

Recall that $G^{\prime}$ is the subgraph of $G$ without terminals. We will
construct a random path $P$, and then show that
$\mathbb{E}[{\mathsf{cov}}(P)]=\Omega(M/\log\log k)$, which implies the lemma.

We denote $P=(u_{1},\ldots,u_{M})$, so each vertex $u_{i}$ of $P$ is a random
variable. We start by pick a vertex in $G^{\prime}$ uniformly at random and
designate it as $u_{1}$, and we choose a random neighbor of this vertex in
$G^{\prime}$ as designate it as $u_{2}$. Then sequentially for each
$i=2,3,\ldots,M-1$, we choose a random non-$u_{i-1}$ neighbor of $u_{i}$ in
$G^{\prime}$, and designate it as $u_{i+1}$. This completes the construction
of $P$.

Denote $S=\left\lfloor 10\log\log k\right\rfloor$, we partition the path $P$
into $\left\lfloor M/S\right\rfloor$ subpaths $P_{1},\ldots,P_{\left\lfloor
M/S\right\rfloor}$, where for each $1\leq j<\left\lfloor M/S\right\rfloor$,
$P_{j}=(u_{(j-1)S+1},\ldots,u_{jS+1})$, and $P_{\left\lfloor
M/S\right\rfloor}=(u_{(\left\lfloor M/S\right\rfloor-1)S+1},\ldots,u_{M})$, so
each subpath $P_{j}$ has length at least $S$. We use the following two
observations.

######  Observation 8.

${\mathsf{cov}}(P)\geq\sum_{1\leq j\leq\left\lfloor
M/S\right\rfloor}\big{(}{\mathsf{cov}}(P_{j})-1\big{)}$.

###### Proof.

Consider a path $Q\in{\mathcal{Q}}$. Note that both $P$ and $Q$ are simple. As
$P$ contains $M$ edges and $Q$ contains at most $\log k/100$ edges, and
$M+\log k/100<\textnormal{{girth}}(G^{\prime})$, $P\cup Q$ may not contain any
cycle, so $Q\cap P$ must be a continuous subpath of $P$.

Consider the optimal covering of $P$ in a sequence: $(Q_{1},\ldots,Q_{r})$,
where paths are indexed according to the increasing order of the earliest
intersection with $P$. Now for each $P_{j}$, we take the minimal subsequence
$(Q_{p},\ldots,Q_{q})$ that covers $P_{j}$. It is easy to verify that the
subsequences for $P_{j}$ and $P_{j+1}$ share at most one path $Q_{q}$. The
observation now follows. ∎

######  Observation 9.

The number of length-$S$ paths in $G^{\prime}$ is $k\cdot 3\cdot 2^{S-1}$, and
for each $1\leq j<\left\lfloor M/S\right\rfloor$, path $P_{j}$ is uniformly at
random chosen from them.

###### Proof.

For choosing a length-$S$ path $P$ (as our algorithm above), the first vertex
has $k$ choices, the second has $3$ choices, and all the rest have $2$
choices. As $S<\textnormal{{girth}}(G)$, we cannot repeat any vertex and so
will always get a simple path, and therefore the number of length-$S$ paths in
$G^{\prime}$ is $k\cdot 3\cdot 2^{S-1}$.

We index vertices of $G^{\prime}$ by integers $1,\ldots,k$. Consider a vertex
$x$ in $G^{\prime}$ whose neighbors are indexed by $y_{1},y_{2},y_{3}$, where
$y_{1}\leq y_{2}\leq y_{3}$. For each $\ell\in\left\\{1,2,3\right\\}$, we say
that the _upper sibling_ of $y_{\ell}$ with respect to $x$ is $y_{\ell+1}$,
and _lower sibling_ of $y_{\ell}$ with respect to $x$ is $y_{\ell-1}$ (here we
use the convention that $3+1=1$). From the above discussion, the path $P$ is
determined by a sequence $(a,b,c_{3},\ldots,c_{M})$, where
$a,b\in\left\\{1,\ldots,k\right\\}$, representing the indices of the first and
the second vertices; and for each $r\geq 3$,
$c_{r}\in\left\\{\uparrow,\downarrow\right\\}$, reflecting that the $u_{r}$ is
either the upper sibling of $u_{r-2}$ with respect to $u_{r-1}$ ($\uparrow$)
or the lower sibling of $u_{r}$ with respect to $u_{r+1}$ ($\downarrow$).

As $M<\textnormal{{girth}}(G)/2$ and $G^{\prime}$ is $3$-regular, the
$M$-neighborhood of each vertex in $G^{\prime}$ is isomorphic (to the graph
where a vertex is connected to the roots of three complete binary trees).
Thus, for each length-$S$ path $Q$ in $G^{\prime}$, and for each $i$, the
number of prefixes $(a,b,c_{3},\ldots,c_{i+S})$ determining that
$(u_{i},\ldots,u_{i+S})=Q$ is exactly $2^{i-1}$ (the choices of
$c_{i+2},\ldots,c_{i+S}$ are uniquely determined by the path $Q$, and
reversely for each $c_{i+1},c_{i},\ldots,c_{3}$, there are two choices, and in
the end indices $a,b$ are uniquely determined). As the sequence
$(a,b,c_{3},\ldots)$ is generated uniformly at random, for each $i$, the
random subpath $(u_{i},\ldots,u_{i+S})$ of $P$ is equally likely to be
realized as any length-$S$ path in $G^{\prime}$. The observation now follows.
∎

######  Observation 10.

A path in ${\mathcal{Q}}$ may cover at most $\log k/100$ length-$S$ paths in
$G^{\prime}$.

###### Proof.

Denote a path in ${\mathcal{Q}}$ as $(e_{1},e_{2},\ldots,e_{r})$ with
$r\leq\log k/100$. If this path covers a length-$S$ path $L$, as this path is
a simple path, then $L$ must be $(e_{i},\ldots,e_{i+S})$ for some $1\leq r\leq
L$, so there can be at most $r\leq\log k/100$ such paths $L$. ∎

Note that $|{\mathcal{Q}}|\leq|E(H)|\leq|E(G^{\prime})|=4k$, so the number of
length-$S$ paths in $G^{\prime}$ that can be covered by some path in
${\mathcal{Q}}$ is at most $4k\cdot(\log k/100)$. Therefore, for each $1\leq
j<\left\lfloor M/S\right\rfloor$,

$\Pr[{\mathsf{cov}}(P_{j})\geq 2]=1-\Pr[{\mathsf{cov}}(P_{j})=1]\geq
1-\frac{4k\cdot(\log k/100)}{k\cdot 3\cdot 2^{S-1}}>0.9,$

as $2^{S-1}>\log k$. Therefore, for each $1\leq j<\left\lfloor
M/S\right\rfloor$, $\mathbb{E}[{\mathsf{cov}}(P_{j})-1]\geq 0.9$, and so by 8,
$\mathbb{E}[{\mathsf{cov}}(P)]\geq 0.9\cdot(\left\lfloor
M/S\right\rfloor-1)=\Omega(M/\log\log k)$. This completes the proof of the
lemma. ∎

Let $u,v$ be the endpoints of the path $P$ given by Lemma 7. We augment $P$
with edge $(u,t_{u})$ at its beginning and edge $(v,t_{v})$ at its end, to
obtain a path, which we call $P^{\prime}$ that connects $t_{u}$ to $t_{v}$. As
$|P^{\prime}|=2M+M<\textnormal{{girth}}(G)/2$, $P^{\prime}$ is the shortest
path in $G$ connecting $t_{u}$ to $t_{v}$, so
$\textnormal{{dist}}_{G}(t_{u},t_{v})=3M$.

Consider now the shortest $t_{u}$-$t_{v}$ path $Q$ in graph $H$ and its image
path $R$ in $G$. If $P\not\subseteq R$, then from 2,
$|R|\geq\textnormal{{girth}}(G)-|P|\geq\log k/100$. If $P\subseteq R$, then
either $Q$ contains an edge whose length is at least $\log k/100$ which
immediately implies $|R|\geq\log k/100$, or $Q$ only contains edges with
length at most $\log k/100$, in which case from Lemma 7 we know that
$|E(Q)|=\Omega(M/\log\log k)$, which, combined with the fact that the distance
in $G$ between every pair of terminals is at least $2M$, implies that
$|R|\geq\Omega(M\cdot(M/\log\log k))$. Finally, from Corollary 5 and
$M=\left\lfloor\sqrt{\log k\cdot\log\log k}\right\rfloor$,

$\frac{\textnormal{{dist}}_{H}(t_{u},t_{v})}{\textnormal{{dist}}_{G}(t_{u},t_{v})}\geq\frac{\min\left\\{\log
k/100,\Omega(M^{2}/\log\log k)\right\\}}{3M}=\Omega(\sqrt{\log k/\log\log
k}).$

#### Acknowledgement.

We would like to thank D Ellis Hershkowitz for bringing this problem to our
attention. We would also like to thank the organizers of the DIMACS Workshop
on Modern Techniques in Graph Algorithms at Rutgers in Summer 2023.

## References

  * [AGS21] Noga Alon, Shirshendu Ganguly, and Nikhil Srivastava.  High-girth near-ramanujan graphs with localized eigenvectors.  Israel Journal of Mathematics, 246(1):1–20, 2021.
  * [BG08] Amitabh Basu and Anupam Gupta.  Steiner point removal in graph metrics.  Unpublished Manuscript, available from http://www. math. ucdavis. edu/~ abasu/papers/SPR. pdf, 1:25, 2008.
  * [CCL+23a] Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, and Shay Solomon.  Covering planar metrics (and beyond): $o(1)$ trees suffice.  arXiv:2306.06215, 2023.
  * [CCL+23b] Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, and Cuong Than.  Resolving the steiner point removal problem in planar graphs via shortcut partitions.  arXiv preprint arXiv:2306.06235, 2023.
  * [CCL+23c] Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, and Cuong Than.  Shortcut partitions in minor-free graphs: Steiner point removal, distance oracles, tree covers, and more.  arXiv preprint arXiv:2308.00555, 2023.
  * [Che18] Yun Kuen Cheung.  Steiner point removal—distant terminals don’t (really) bother.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1353–1360. SIAM, 2018.
  * [CKR05] Gruia Calinescu, Howard Karloff, and Yuval Rabani.  Approximation algorithms for the 0-extension problem.  SIAM Journal on Computing, 34(2):358–372, 2005.
  * [CXKR06] T-H Hubert Chan, Donglin Xia, Goran Konjevod, and Andrea Richa.  A tight lower bound for the steiner point removal problem on trees.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 70–81. Springer, 2006.
  * [Fil18] Arnold Filtser.  Steiner point removal with distortion o (log k).  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1361–1373. SIAM, 2018.
  * [Fil20] Arnold Filtser.  Scattering and sparse partitions, and their applications.  In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
  * [Gup01] Anupam Gupta.  Steiner points in tree metrics don’t (really) help.  In SODA, volume 1, pages 220–227, 2001.
  * [HL21] D Ellis Hershkowitz and Jason Li.  $o(1)$ steiner point removal in series-parallel graphs.  arXiv preprint arXiv:2104.00750, 2021.
  * [KNZ14] R. Krauthgamer, H. Nguyen, and T. Zondiner.  Preserving terminal distances using minors.  SIAM Journal on Discrete Mathematics, 28(1):127–141, 2014.


# Mapping Wordnets on the Fly with Permanent Sense Keys

Eric Kafe
MegaDoc
Charlottenlund, Denmark
<EMAIL_ADDRESS>
###### Abstract

Most of the major databases on the semantic web have links to Princeton
WordNet (PWN) synonym set (synset) identifiers, which differ for each PWN
release, and are thus incompatible between versions. On the other hand, both
PWN and the more recent Open English Wordnet (OEWN) provide permanent word
sense identifiers (the sense keys), which can solve this interoperability
problem.

We present an algorithm that runs in linear time, to automatically derive a
synset mapping between any pair of Wordnet versions that use PWN sense keys.
This allows to update old WordNet links, and seamlessly interoperate with
newer English Wordnet versions for which no prior mapping exists.

By applying the proposed algorithm on the fly, at load time, we combine the
Open Multilingual Wordnet (OMW 1.4, which uses old PWN 3.0 identifiers) with
OEWN Edition 2021, and obtain almost perfect precision and recall. We compare
the results of our approach using respectively synset offsets, versus the
Collaborative InterLingual Index (CILI version 1.0) as synset identifiers, and
find that the synset offsets perform better than CILI 1.0 in all cases, except
a few ties.

Mapping Wordnets on the Fly with Permanent Sense Keys

Eric Kafe MegaDoc Charlottenlund, Denmark<EMAIL_ADDRESS>

##  1 Introduction

All the available multilingual wordnets (Bond et al., 2014) and important
knowledge bases on the semantic web (Navigli and Ponzetto, 2010; Niles and
Pease, 2003; Suchanek et al., 2008; Nielsen, 2018) were originally linked to
different versions of Princeton WordNet (PWN) (Fellbaum, 1998), using version-
specific synset offsets (WordNet-team, 2010, Wndb), which differ between
releases, so mappings are necessary for interoperation, and for updating to a
later English Wordnet versions.

Many of these resources have been remapped to Wordnet 3.0 or Wordnet 3.1,
using offset to offset mappings obtained by relaxation labelling (Daudé et
al., 2000), offset to ILI (InterLingual Index) mappings (Vossen, 2002; Vossen
et al., 2016; Bond et al., 2016), sensekey to sensekey mappings (WordNet-team,
2010, Sensemap), and offset to offset mappings relying on sense key
persistence (Kafe, 2018). Contrary to synset offsets, the sensekeys persist
across database versions (WordNet-team, 2010, Senseidx), and can thus support
the derivation of mappings with high precision and recall.

PWN sensekeys (WordNet-team, 2010, Senseidx) are composite database keys
representing one particular word sense. They consist in the concatenation of
the identifiers for the corresponding lemma and its lexfile, lex_id, and
eventually head adjective (see examples in sections 2.1, 3.2 and 4.2). Each
PWN version includes an index.sense file, linking the sense keys to their
corresponding synset offsets.

However, the necessary mappings between synsets linked to different PWN
versions are not always available, either because a resource is too new, or
has too few users to justify the production of a mapping. This causes
potentially long delays for interoperability, which may remain impossible as
long as no relevant mapping exists. For example, Edition 2022 of the Open
English Wordnet (OEWN111https://github.com/globalwordnet/english-wordnet)
(McCrae et al., 2020) was released recently, and the
wndb222https://github.com/x-englishwordnet/wndb project has also published the
same data in a PWN-compatible format (including the relevant index.sense).
These two variants of the OEWN 2022 Edition use different, mutually
incompatible synset offsets; no mapping exists for neither yet, and no known
project currently aims to produce such mappings.

On the other hand, OEWN has adopted PWN sensekeys as its main sense
identifier, so it is easy to extract a sense index from the database, and
almost instantly produce a sensekey-based mapping, since this only requires
joining the index.sense of the relevant wordnet versions. Therefore, we
propose to carry out the mapping process on the fly, whenever loading wordnets
that are linked to different English Wordnet (PWN or OEWN) versions.

##  2 Methods

###  2.1 Mapping Strategy

Between two Wordnet versions, word senses can be either added or removed, and
the same applies to synonym sets, in the case where all their elements are
respectively completely new or entirely deleted. In addition to that, synonym
sets can also be split and/or merged, when one or more of their elements are
moved to another (existing or new) synset.

For example, between versions 3.0 and 3.1 of PWN, Pluto was moved from the god
of the underworld in Greek mythology, to the synset with the names of the
corresponding Roman "god of the underworld":

Sense Key | PWN3.0 | CILI3.0 | CILI3.1 | PWN3.1
---|---|---|---|---
aides%1:18:00:: | 09570298-n | i86957 | i86957 | 09593427-n
aidoneus%1:18:00:: | 09570298-n | i86957 | i86957 | 09593427-n
hades%1:18:00:: | 09570298-n | i86957 | i86957 | 09593427-n
pluto%1:18:00:: | 09570298-n | i86957 | i86958 | 09593643-n
dis%1:18:00:: | 09570522-n | i86958 | i86958 | 09593643-n
orcus%1:18:00:: | 09570522-n | i86958 | i86958 | 09593643-n
dis_pater%1:18:00:: | $\displaystyle\nexists$ | $\displaystyle\nexists$ | i86958 | 09593643-n

The problem is that foreign language translations of the involved synsets
cannot deal with this change by simply applying a concept to offset mapping
like the Collaborative Interlingual index
(CILI333https://github.com/globalwordnet/cili). In the French Wordnet, for
example, Pluton is a synonym of Hadès and Aides, and thus a member of the
Greek gods, and remains so, even after applying the CILI mapping. Unlike the
English Pluto, the French Pluton keeps the CILI i86957 identifier, and still
translates to Hades in later English Wordnet versions. Conversely, the French
translation of the PWN 3.1 synset with CILI i86958 does not include Pluton. To
adequately deal with this situation, the French Pluton would need a link to
the corresponding English sense key, instead of being linked at the synset
level.

Here, where both gods are the same and the name Plouton actually exists in the
Greek mythology, it would make sense to apply the map-to-all strategy, and
insert Pluto in both target synsets, as in the mappings from the Sense Key
Index (SKI)444https://github.com/ekaf/ski. But mapping to all possible targets
is not guaranteed to be adequate in all cases, so it is always preferable to
review all the synset splits manually.

We aim to support wordnet interoperability in the general-purpose natural
language toolkit NLTK555https://www.nltk.org (Bird et al., 2009), which is
increasingly used in very diverse Machine Learning projects, without
specialized lexicographic knowledge. So a one-to-many synset mapping strategy
would not be an adequate default, because users would not know how to choose
the most adequate target synset from a list of mapping candidates. In such
cases, it is more convenient that the system only picks one target synset for
each source synset.

Mapping the wordnets on the fly, at load time, requires an algorithm that
performs as close to instantly as possible, so we prefer a simple frequency-
based approach, rather than a more complex analysis of relation links.
Therefore, we map each source synset to the target that retains most of the
source lemmas and, in the case of equality, to the synset with the highest
offset. In most cases, though, the choice is limited to one single target
synset, since choosing between synsets is only relevant in the cases where a
source synset is split into two (or eventually three) synsets. These cases are
rare Kafe (2018), so candidates with an equal number of lemmas are even rarer.

So we apply a many-to-one mapping strategy, where potentially many (though
most often only one) source synsets are merged into a single target synset.
This is the only difference between this work and the many-to-many mappings
from the Sense Key Index (SKI), resulting in slightly different numbers of
False Positives (fp) and False Negatives (fn), and only tiny differences in
overall performance.

###  2.2 Linear Time Algorithm

Algorithm 1 Map synsets from source to target Wordnet version using sense keys

$\displaystyle\text{\sc
sense\\_index}_{source}\leftarrow\left\\{\,\forall\;\text{sense}\in\text{\it
source}:\text{sense}_{key}\rightarrow\text{synset\\_id}_{source}\,\right\\}$

$\displaystyle\text{\sc
sense\\_index}_{target}\leftarrow\left\\{\;\forall\;\text{sense}\in\text{\it
target}:\text{sense}_{key}\rightarrow\text{synset\\_id}_{target}\;\right\\}$

$\displaystyle\text{\sc
map\\_to\\_many}\leftarrow\left\\{\,\forall\;\text{synset\\_id}_{source}\in\text{values}(\text{\sc
sense\\_index}_{source}):\text{synset\\_id}_{source}\rightarrow\emptyset\,\right\\}$

for $\displaystyle\text{sense}_{key}\in\text{\sc
sense\\_index}_{source}\cap\text{\sc sense\\_index}_{target}$ do

$\displaystyle\text{\sc
map\\_to\\_many}[\text{synset\\_id}_{source}].\text{append}(\text{synset\\_id}_{target})$

end for

$\displaystyle\text{\sc
map\\_to\\_one}\leftarrow\left\\{\,\forall\;\text{synset\\_id}_{source}\in\text{\sc
map\\_to\\_many}:\text{synset\\_id}_{source}\rightarrow\text{argmax}(\text{count}(\text{synset\\_id}_{target}))\,\right\\}$

return map_to_one

Algorithm 1 constructs a mapping between two English Wordnet (PWN or OEWN)
versions (respectively $\displaystyle source$ and $\displaystyle target$),
using intermediate mappings, implemented here as Python dictionaries (see the
NLTK listing in Appendix A).

First, we construct a mapping from the sensekeys to the corresponding synset
identifier (synset_id) for each of the $\displaystyle source$ and
$\displaystyle target$ Wordnet versions. For this, we use either the
index.sense file included in each PWN release, or the sense id attribute of
the OEWN senses, since OEWN now uses sensekeys directly as its main sense
identifier. NLTK does not yet support ILI identifiers, so the current NLTK
implementation can only use offset-part_of_speech synset identifiers, but it
is straightforward to replace these by ILI concept identifiers. Each sensekey
is linked to at most one synset in each version, but may be absent from either
the source or target version (in the cases where a sense was added or
removed). This step does one pass over the index.sense, which consists in one
record per sensekey, so its complexity is obviously linear.

Then the map_to_many step joins the two index_sense maps in order to produce a
synset_to_many mapping from the source synset identifiers to lists of
corresponding synset identifiers in target. Python sets are implemented as
hash tables, with $\displaystyle O(1)$ lookup, so the intersection of both
versions’ sense keys is computed in $\displaystyle O(n)$ time. Then we do one
pass over the sources’ offsets, to initialize empty candidate bags, and one
pass over the common sense keys, to populate the map_to_many mapping, which is
identical to the corresponding SKI mapping (Kafe, 2018).

Finally, a map_to_one step chooses the most adequate target synset for each
source synset, among a bag of candidates provided by the map_to_many mapping.
This step is optional for use cases where we want to retain all the candidate
targets. Here, we use the $\displaystyle max$666Thanks to Steven Bird, who
reviewed the initial implementation, and pointed out that $\displaystyle max$
is quicker than $\displaystyle sort$. function to pick the target synset that
retains most lemmas from the source synset, but we also discuss using
$\displaystyle sort$ as an alternative in section 4.3. We do one pass over
each of the candidate bags, where we use the $\displaystyle O(n)$
$\displaystyle max$ function to pick the target synset, so this step also runs
in linear time.

###  2.3 Complexity

Since each of its steps runs in linear time, the total complexity of this
mapping algorithm is also $\displaystyle O(n)$, where $\displaystyle n$
corresponds to the numbers of sense keys and synset offsets in the involved
wordnets. To our knowledge, this is the simplest mapping algorithm yet
proposed for wordnets, and considerably less complex than the deep relation
analysis in Daudé et al. (2000) and Daudé et al. (2001), although both
approaches have similar performance, but also complementary strengths and
weaknesses (Kafe, 2018).

###  2.4 Implementation

We first integrated this mapping process in the wordnet library of NLTK
version 3.6.6, and used it to map the multilingual wordnets from OMW 1.4 Bond
et al. (2020) at load time, converting their PWN 3.0 synset identifiers to
those used in any of the more recent English Wordnets, in order to support the
seamless interoperation of the involved databases.

NLTK is developed on an open software development
platform777https://github.com/nltk/nltk, which provides free access for all,
to not only the software code, but also its various incarnations, and the
corresponding discussions before and after its release. Everyone is free to
modify the source code, and welcome to contribute improvements back to the
community.

When using synset offsets, the implementation differs from algorithm 1 by
adding a supplementary mapping link from adjectives, when the source synset is
an adjective satellite. This is necessary for handling OMW data, where most
languages ignore the $\displaystyle satellite$ category. But this step does
not apply to ILI identifiers, since these don’t include any part-of-speech
reference.

We rewrote the implementation for NLTK version 3.8, in order to closely follow
algorithm 1. In the initial implementation, the source wordnet was hard-coded
to PWN version 3.0, for handling the OMW data. An optional version parameter
has been added in the forthcoming NLTK 3.8.2, which allows to produce mappings
for any pair of English Wordnet versions. Appendix A includes the listing of
this slightly more elaborated implementation, which additionally collects the
split or lost synsets in structures called respectively $\displaystyle splits$
and $\displaystyle nomap$, which should be useful for further improving the
mappings. We also adapted the functions in the appendix for the
Wn888https://github.com/goodmami/wn library Goodman and Bond (2021), in order
to compare the performance of algorithm 1 using respectively synset offsets
versus ILIs as synset identifiers. We thus used Wn to produce the
$\displaystyle Map_{CILI}$ results in table 3.1, while we computed the
$\displaystyle Map_{Offset}$ results in table 3.1 using both NLTK and Wn, and
verified that both libraries yield identical outputs.

##  3 Results

###  3.1 Multilingual Coverage

Table 1: Multilingual synsets in OMW 1.4 mapped to OEWN 2021 using synset
offsets vs. CILI 1.0

| Synsets | MapOffset | MapCILI
---|---|---|---
Language | PWN 3.0 | OEWN 2021 | Lost | % | OEWN 2021 | Lost | %
English | 117659 | 117454 | 205 | 0.17 | 117427 | 232 | 0.20
Finnish | 116763 | 116562 | 201 | 0.17 | 116535 | 228 | 0.20
Thai | 73350 | 73240 | 110 | 0.15 | 73223 | 127 | 0.17
French | 59091 | 59015 | 76 | 0.13 | 59005 | 86 | 0.15
Japanese | 57184 | 57086 | 98 | 0.17 | 57080 | 104 | 0.18
Romanian | 56026 | 55941 | 85 | 0.15 | 55931 | 95 | 0.17
Catalan | 45826 | 45773 | 53 | 0.12 | 45769 | 57 | 0.12
Portuguese | 43895 | 43844 | 51 | 0.12 | 43840 | 55 | 0.13
Slovenian | 42583 | 42520 | 63 | 0.15 | 42513 | 70 | 0.16
Mandarin Chinese | 42300 | 42249 | 51 | 0.12 | 42240 | 60 | 0.14
Spanish | 38512 | 38431 | 81 | 0.21 | 38418 | 94 | 0.24
Indonesian | 38085 | 38018 | 67 | 0.18 | 38011 | 74 | 0.19
Standard Malay | 36911 | 36843 | 68 | 0.18 | 36836 | 75 | 0.20
Italian | 35001 | 34964 | 37 | 0.11 | 34960 | 41 | 0.12
Polish | 33826 | 33798 | 28 | 0.08 | 33794 | 32 | 0.09
Dutch | 30177 | 30154 | 23 | 0.08 | 30151 | 26 | 0.09
Basque | 29413 | 29387 | 26 | 0.09 | 29386 | 27 | 0.09
Croatian | 23115 | 23081 | 34 | 0.15 | 23077 | 38 | 0.16
Galician | 19311 | 19290 | 21 | 0.11 | 19283 | 28 | 0.14
Slovak | 18507 | 18478 | 29 | 0.16 | 18472 | 35 | 0.19
Modern Greek (1453-) | 18049 | 18025 | 24 | 0.13 | 18023 | 26 | 0.14
Italian (iwn) | 15563 | 15553 | 10 | 0.06 | 15553 | 10 | 0.06
Standard Arabic | 9916 | 9897 | 19 | 0.19 | 9896 | 20 | 0.20
Lithuanian | 9462 | 9446 | 16 | 0.17 | 9442 | 20 | 0.21
Swedish | 6796 | 6784 | 12 | 0.18 | 6784 | 12 | 0.18
Hebrew | 5448 | 5441 | 7 | 0.13 | 5439 | 9 | 0.17
Bulgarian | 4959 | 4950 | 9 | 0.18 | 4950 | 9 | 0.18
Icelandic | 4951 | 4942 | 9 | 0.18 | 4942 | 9 | 0.18
Albanian | 4675 | 4668 | 7 | 0.15 | 4668 | 7 | 0.15
Danish | 4476 | 4468 | 8 | 0.18 | 4468 | 8 | 0.18
Norwegian Bokmål | 4455 | 4447 | 8 | 0.18 | 4447 | 8 | 0.18
Norwegian Nynorsk | 3671 | 3666 | 5 | 0.14 | 3666 | 5 | 0.14
Average | 32811.12 | 32762.97 | 48.16 | 0.15 | 32757.16 | 53.97 | 0.16

We computed the MapOffset results using both the NLTK and Wn software
libraries, and the MapCILI results with only Wn, since NLTK does not yet
support ILI identifiers.

Table 3.1 displays the number of synsets and lemmas in NLTK’s data package for
OMW 1.4, when loaded with respectively the default PWN 3.0, and OEWN Edition
2021. The languages are listed by their number of synsets in decreasing order,
and we report the number of synsets lost, as well as percentages, when mapping
between the two English Wordnet versions, using either synset offsets or the
CILI 1.0 synset identifiers currently included in the Wn library.

All the multilingual wordnets suffer a loss in the mapping, but this loss is
almost negligible with either type of synset identifier: at most
$\displaystyle 0.19\%$ (corresponding to $\displaystyle 99.81\%$ recall) for
Standard Arabic with synset offsets, and $\displaystyle 0.21\%$ using CILI
with Lithuanian. Except a small number of ties with the smallest wordnets, the
synset offset mappings perform better than the CILI 1.0 mappings in all cases.
This is surprising since the CILI mappings were partially curated manually, so
we expected them to provide an advantage over the completely automatic offset
mappings. However, the difference is small, and might be attributed to known
issues 999CILI issue #16, https://github.com/globalwordnet/cili/issues/16 with
the CILI 1.0 mappings, which could be remedied in a future version.

With PWN 3.0, some numbers are identical to those reported by Bond et al.
(2014). These concern wordnets that have not been updated since OMW 1.0. On
the other hand, some wordnets in OMW 1.4 are not current, as for ex. the
Basque, Catalan, Galician and Spanish wordnets date back to the 2012 edition
of the Multilingual Core Repository (MCR) described by Gonzalez-Agirre et al.
(2012), although the coverage of these wordnets was greatly expanded in the
2016 edition of MCR.

NLTK also has a PWN 3.1 data package, where the mapping loss is usually less
than half, compared to OEWN 2021, and for ex. only $\displaystyle 0.09\%$ for
Standard Arabic, corresponding to $\displaystyle 99.91\%$ recall. We also
mapped two variants of OEWN Edition 2022: the official release
101010https://en-word.net/static/english-wordnet-2022.zip, and an alternative
version provided by the XEWN111111https://github.com/x-englishwordnet project.
Their databases have different sizes, and hence different synset offsets, but
both yielded identical mapping losses, which were slightly better than OEWN
2021 in all cases, for ex. $\displaystyle 0.17\%$ synset lost with Standard
Arabic. Standard mappings are not likely to become available for different
variants of the same Wordnet version, so an advantage of our method is that it
nevertheless allows a downstream comparison of these variants, which would not
be possible otherwise.

###  3.2 Splits and Merges

As a consequence of our mapping strategy, where we only pick one target for
each source synset, the synsets are never split. On the contrary, all lemmas
belonging to a source synset, that would be split according to a many-to-many
strategy, are mapped to the same target synset, and synonymy persists.

With the example from section 2.1, since Pluto is not split out of its source
synset, it is not merged into its target synset, but remains a synonym of the
other Greek gods:

Sense Key | PWN3.0 | CILI3.0 | CILI3.1 | PWN3.1
---|---|---|---|---
aides%1:18:00:: | 09570298-n | i86957 | i86957 | 09593427-n
aidoneus%1:18:00:: | 09570298-n | i86957 | i86957 | 09593427-n
hades%1:18:00:: | 09570298-n | i86957 | i86957 | 09593427-n
pluto%1:18:00:: | 09570298-n | i86957 | i86957 | 09593427-n
dis%1:18:00:: | 09570522-n | i86958 | i86958 | 09593643-n
orcus%1:18:00:: | 09570522-n | i86958 | i86958 | 09593643-n
dis_pater%1:18:00:: | $\displaystyle\nexists$ | $\displaystyle\nexists$ | i86958 | 09593643-n

The result is mostly a one-to-one mapping, with only 44 many-to-one cases
occurring, when different source synsets are merged into the same target
synset. Our method maps all the merged foreign language synsets to their
correct target, as for ex. with the baseball example below. This contrasts
with the current implementation of the Wn library’s standard translate
function, which finds no translation for the first PWN3.0 synset (i37881) in
PWN3.1. Conversely, translating i37882 back from PWN3.1 to PWN3.0, Wn does not
find the i37881 lemmas.

Sense Key | PWN3.0 | CILI3.0 | CILI3.1 | PWN3.1
---|---|---|---|---
baseball%1:04:00:: | 00471613-n: | i37881 | i37882 | 00472688-n
baseball_game%1:04:00:: | 00471613-n: | i37881 | i37882 | 00472688-n
ball%1:04:01:: | 00474568-n | i37882 | i37882 | 00472688-n

The problem is that Wn only knows the correspondence between ILIs and offsets
within each involved Wordnet version, but has no mapping between these
versions. Merged synsets disappear in
translation121212https://github.com/goodmami/wn/issues/179, because only one
of the merged CILI identifiers is available in the target, so the synsets with
the other ILIs are no longer reachable. This problem with merged ILIs in Wn
only concerns a small number of synsets, since each foreign language wordnet
covers only a fraction of the 44 merged English synsets. It does not affect
the MapCILI results in Table 3.1, since we computed these using our mapping
algorithm, instead of Wn’s standard translate function.

###  3.3 Performance

We found that our method could not map 205 English synset offsets from PWN 3.0
to an OEWN 2021 target. The small mapping losses in table 3.1 correspond to
the subset of these 205 synsets included in each multilingual wordnet. These
losses represent all the negatives in a confusion matrix, amounting to the
addition of the True Negatives (tn), which were truly removed in the target
Wordnet, and the False Negatives (fn), which we ideally should be able to map.
So among the mapping losses, only the fn are fallacies.

The minority lemmas in the split English synsets, which are induly mapped to
the same synset as in the source, constitute the False Positives (fp). These
only amount to the 44 splits between PWN 3.0 and OEWN 2021, so their number is
small, compared to the True Positives (117454 minus eventual sense key
violations).

Synsets | Mapped | Not Mapped
---|---|---
True | $\displaystyle PWN_{3.0}\cap OEWN_{2021}$ | $\displaystyle\emptyset$
| $\displaystyle tp=117454$ | $\displaystyle tn=0$
False | $\displaystyle Splits$ | $\displaystyle\complement_{OEWN_{2021}}^{PWN_{3.0}}$
| $\displaystyle fp=44$ | $\displaystyle fn=205$

We evaluate the performance of our algorithm using the values above, and
obtain almost perfect performance results:

$precision=\frac{tp}{tp+fp}=0.9996$ (1) $recall=\frac{tp}{tp+fn}=0.9983$ (2)
$f1=\frac{2*precision*recall}{precision+recall}=0.9989$ (3)

Thus, the overall performance of the English mapping is $\displaystyle
99.89\%$, which compares favorably with more complex mapping strategies like
Daudé et al. (2000).

Comparing the lost English synsets between the two types of synset identifiers
(offsets vs. ILIs), we found that 143 were lost using both types, while 62
were only lost with offsets (always due to satellite adjectives becoming
standard adjectives), and 89 were only lost with CILI 1.0. The respective
additions of these losses yield the total loss reported for English in table
3.1 (205 with offsets vs. 232 with the ILI).

##  4 Discussion

We have shown that mapping between different English Wordnet versions is
feasible in linear time, by relying on the stability of PWN sense keys. Our
method allows to transparently update the database links on-the-fly, to
another English Wordnet version, even though no prior mapping exists yet. This
can benefit any database linked with an English Wordnet, and enhance any
downstream task that uses such a database.

###  4.1 Coverage and Integrity

Our results show that almost all the vocabulary of the multilingual wordnets
in OMW 1.4 persisted after the mapping.

Some doubts remain necessarily, though, concerning the referential integrity
of the sensekeys, on which the mappings rely. Sensekeys are meant to always
refer to the same wordsense across wordnet versions, but Kafe (2018) reported
a few violations of sensekeys’ referential integrity. The number of these
violations seems negligible in PWN, but their impact has not yet been studied
in OEWN. However, the fact that OEWN now uses the PWN sensekeys as principal
wordsense identifier, is a reason for considering that the sensekeys are
indeed persistent in OEWN, and that we can rely on their referential integrity
in theory. Still, it would be helpful to investigate in practice, whether the
addition of a new wordsense in OEWN could entail a modification of the
sensekeys for other existing senses of the same word.

###  4.2 Challenges and Opportunities

In the mapping between PWN 3.0 and OEWN 2021, which we investigated here, our
method displayed two shortcomings: 205 English synsets were completely lost in
the mapping, and 44 split synsets were somewhat arbitrarily mapped to one
single target. It is questionable, to which extent any automatic mapping can
provide linguistically satisfying targets for each of these cases.
Fortunately, their number is sufficiently small to allow a manual review, of
which we can already attempt to sketch some outlines.

It is possible, for ex., to identify genuinely lost synsets, which do not have
any plausible target. This happens when all the words included in the source
synset are completely absent from the target Wordnet version. Here, it
occurred in particular with a number of racially tainted expressions, like the
synset $\displaystyle\\{darky,darkie,darkey\\}$, defined as "(ethnic slur)
offensive term for Black people". In these cases, relaxing the equivalence
criteria, and mapping the synset to for ex. a superordinate, would entail
losing an essential nuance, and might often not be adequate. So these losses
may be unavoidable, unless choosing to retain the synset with its original
meaning.

On the other hand, many losses are relatively easy to avoid. For example, out
of the 205 English synsets that our algorithm doesn’t map, 62 concern
adjective satellites which were changed to plain adjectives. These have an
obvious mapping through the ILI, where both Wordnet versions share the same
concept identifier.

In other cases, we can identify changes in a part of the sense key, for words
that keep identical definitions. This reveals that unfortunate changes can
occur in any sense key part between two wordnet versions. For example, Table 2
shows how the lex_id of a sense of "sequoia" changed from 00 to 01 between PWN
3.0 and OEWN 2021, while the lexfile of a sense of "stub out" changed from 30
to 35, the adjective category of "obtrusive" changed from 3 to 5, and the
satellites’ head adjective of "newfangled" changed from original to new.

Table 2: Changed Sense Key Parts (Examples)

Sense Key |  PWN 3.0 |  OEWN 2021
---|---|---
sequoia%1:20:00:: |  either of two huge coniferous California trees that reach a height of 300 feet; sometimes placed in the Taxodiaceae |  $\displaystyle\nexists$
sequoia%1:20:01:: |  $\displaystyle\nexists$ |  either of two huge coniferous California trees that reach a height of 300 feet; sometimes placed in the Taxodiaceae
stub_out%2:30:00:: |  extinguish by crushing |  $\displaystyle\nexists$
stub_out%2:35:01:: |  $\displaystyle\nexists$ |  extinguish by crushing
obtrusive%3:00:00:: |  undesirably noticeable |  $\displaystyle\nexists$
obtrusive%5:00:00:noticeable:00 |  $\displaystyle\nexists$ |  undesirably noticeable
newfangled%5:00:00:original:00 |  (of a new kind or fashion) gratuitously new |  $\displaystyle\nexists$
newfangled%5:00:00:new:00 |  $\displaystyle\nexists$ |  (of a new kind or fashion) gratuitously new

In all these cases, we see different sense keys pointing to the same word
sense, and this is different from key violations (one sense key pointing to
different word senses). In some cases, the English lexicographers could
prevent this problem, but it can also be remedied downstream, by an additional
mapping link between the few changed sense keys, which would allow even higher
quality mappings. Our implementation (see Appendix A) supports eventual
further improvements of the mappings through the map_to_many function, and by
providing the splits and nomap lists of problematic cases to study in greater
depth.

###  4.3 Variants of the mapping algorithm

Applying our mapping algorithm to other synset identifiers than the offsets
only requires a simple modification of the initial $\displaystyle IndexSense$
function, while our two other functions remain unchanged. So we extended our
approach, to also map ILI concept identifiers instead of synset offsets. This
is not always practical yet though, because of inherent delays in the current
attribution process for new ILI identifiers131313CILI issue #9,
https://github.com/globalwordnet/cili/issues/9.

We applied $\displaystyle max$ to a list of candidate
$\displaystyle(count,offset)$ pairs, in order to pick the target synset that
retains most lemmas from the source synset. As a consequence, in the case of
equal counts, the $\displaystyle max$ function picks the target synset with
the highest offset. But instead of the highest offset, it would be possible to
use the $\displaystyle min$ function, and pick the lowest offset instead when
the counts are equal. Alternatively, this strategy can be implemented by
taking the first pair in a sorted list, eventually sorting the counts in
decreasing order and the offsets in increasing order. Generally, the lowest
offset corresponds to a synset that was included in the PWN databases before
those with higher offsets, so the choice between using $\displaystyle min$ or
$\displaystyle max$ often induces a preference for older versus newer synsets.
More research could be useful, in order to assess which difference this choice
makes in practice.

Concerning the complexity of max, which is $\displaystyle O(n)$ versus sort,
which is $\displaystyle O(n.logn)$, their difference is not substantial here,
where $\displaystyle n$ represents the number of target
$\displaystyle(count,offset)$ pairs, which is normally one, and only two or
three in the rare cases where the source synset is split.

##  5 Conclusion

We presented an algorithm for mapping wordnets, that runs in linear time, thus
moving the frontier of wordnet interoperability by allowing to almost
instantly combine different database versions, for which no prior mapping
exists. We illustrated this capability by combining the OMW with OEWN. Other
potential uses include seamlessly updating existing PWN links in any Wordnet-
linked semantic web database, to newer OEWN versions.

We saw how our mappings only lose tiny amounts of data when mapping
multilingual wordnets, which indicates that the performance of this approach
is comparable to the best results obtained with alternative strategies.

Now that OEWN has adopted the original PWN sensekeys as main wordense
identifier, we may expect that the proposed algorithm remains relevant with
future OEWN versions. However, if more wordnet resources start to use a common
set of persistent identifiers like the PWN sensekeys, mappings could become
unnecesary between these resources, as they would be natively interoperable.

## Acknowledgments

Thanks to Tom Aarsen and Steven Bird for their useful review of the NLTK
implementation, and to the anonymous GWC 2023 reviewers for their many
detailed and accurate suggestions. The final version of this article also
benefited from helpful comments by participants at the GWC 2023 presentation,
in particular Francis Bond and Piek Vossen.

## References

  * Bird et al. (2009) Steven Bird, Ewan Klein, and Edward Loper. 2009.  _Natural language processing with Python: analyzing text with the natural language toolkit_.  O’Reilly Media, Inc.
  * Bond et al. (2014) Francis Bond, Christiane Fellbaum, Shu-Kai Hsieh, Chu-Ren Huang, Adam Pease, and Piek Vossen. 2014.  A multilingual lexico-semantic database and ontology.  In _Towards the Multilingual Semantic Web_ , pages 243–258. Springer.
  * Bond et al. (2020) Francis Bond, Luis Morgado da Costa, Michael Wayne Goodman, John Philip McCrae, and Ahti Lohk. 2020.  Some issues with building a multilingual Wordnet.  In _Proceedings of the 12th Language Resources and Evaluation Conference_ , pages 3189–3197, Marseille, France. European Language Resources Association.
  * Bond et al. (2016) Francis Bond, Piek Vossen, John McCrae, and Christiane Fellbaum. 2016.  CILI: the collaborative interlingual index.  In _Proceedings of the 8th Global WordNet Conference (GWC)_ , pages 50–57, Bucharest, Romania. Global Wordnet Association.
  * Daudé et al. (2000) J. Daudé, L. Padró, and G. Rigau. 2000.  Mapping WordNets using structural information.  In _Proceedings of the 38th Annual Meeting of the Association for Computational Linguistics_ , pages 504–511, Hong Kong. Association for Computational Linguistics.
  * Daudé et al. (2001) J. Daudé, L. Padró, and G. Rigau. 2001.  A complete wn1.5 to wn1.6 mapping.  In _Proceedings of the NAACL Workshop ’WordNet and Other Lexical Resources: Applications, Extensions and Customizations’ (NAACL’2001)., Pittsburg, PA, USA_.
  * Fellbaum (1998) Christiane Fellbaum. 1998.  _WordNet, An Electronic Lexical Database_.  MIT Press, Cambridge.
  * Gonzalez-Agirre et al. (2012) A. Gonzalez-Agirre, E. Laparra, and G. Rigau. 2012.  Multilingual central repository version 3.0: upgrading a very large lexical knowledge base.  In _Proceedings of the Sixth International Global WordNet Conference (GWC2012). Matsue, Japan_.
  * Goodman and Bond (2021) Michael Wayne Goodman and Francis Bond. 2021.  Intrinsically interlingual: The wn python library for wordnets.  In _Proceedings of the 11th Global Wordnet Conference_ , pages 100–107, University of South Africa (UNISA). Global Wordnet Association.
  * Kafe (2018) Eric Kafe. 2018.  Persistent semantic identity in wordnet.  _Cognitive Studies | Études cognitives_ , 18.
  * McCrae et al. (2020) John Philip McCrae, Alexandre Rademaker, Ewa Rudnicka, and Francis Bond. 2020.  English WordNet 2020: Improving and extending a WordNet for English using an open-source methodology.  In _Proceedings of the LREC 2020 Workshop on Multimodal Wordnets (MMW2020)_ , pages 14–19, Marseille, France. The European Language Resources Association (ELRA).
  * Navigli and Ponzetto (2010) Roberto Navigli and Simone Paolo Ponzetto. 2010.  Babelnet: Building a very large multilingual semantic network.  In _Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, Uppsala, Sweden, 11-16 July 2010_ , pages 216–225.
  * Nielsen (2018) Finn Årup Nielsen. 2018.  Linking imagenet wordnet synsets with wikidata.  In _Proceedings of The 2018 Web Conference Companion (WWW’18 Companion)_. ACM, New York, USA.
  * Niles and Pease (2003) Ian Niles and Adam Pease. 2003.  Linking lexicons and ontologies: Mapping wordnet to the suggested upper merged ontology.  In _Ike_ , pages 412–416.
  * Suchanek et al. (2008) Fabian M Suchanek, Gjergji Kasneci, and Gerhard Weikum. 2008.  Yago: A large ontology from wikipedia and wordnet.  _Web Semantics: Science, Services and Agents on the World Wide Web_ , 6(3):203–217.
  * Vossen (2002) Piek Vossen. 2002.  _EuroWordnet General Document_.  EWN.
  * Vossen et al. (2016) Piek Vossen, Francis Bond, and John McCrae. 2016.  Toward a truly multilingual GlobalWordnet grid.  In _Proceedings of the 8th Global WordNet Conference (GWC)_ , pages 424–431, Bucharest, Romania. Global Wordnet Association.
  * WordNet-team (2010) WordNet-team. 2010.  Wordnet 3.0 reference manual.  In _WordNet Documentation_. Princeton University, https://wordnet.princeton.edu/documentation.

##  Appendix A Appendix: Implementation in NLTK (Python)

⬇

1221 def index_sense(self, version=None):

1222
"""Read␣sense␣key␣to␣synset␣id␣mapping␣from␣index.sense␣file␣in␣corpus␣directory"""

1223 fn = "index.sense"

1224 if version:

1225 from nltk.corpus import CorpusReader, LazyCorpusLoader

1226

1227 ixreader = LazyCorpusLoader(version, CorpusReader, r".*/" + fn)

1228 else:

1229 ixreader = self

1230 with ixreader.open(fn) as fp:

1231 sensekey_map = {}

1232 for line in fp:

1233 fields = line.strip().split()

1234 sensekey = fields[0]

1235 pos = self._pos_names[int(sensekey.split("%")[1].split(":")[0])]

1236 sensekey_map[sensekey] = f"{fields[1]}-{pos}"

1237 return sensekey_map

1238

1239 def map_to_many(self, version="wordnet"):

1240 sensekey_map1 = self.index_sense(version)

1241 sensekey_map2 = self.index_sense()

1242 synset_to_many = {}

1243 for synsetid in set(sensekey_map1.values()):

1244 synset_to_many[synsetid] = []

1245 for sensekey in set(sensekey_map1.keys()).intersection(

1246 set(sensekey_map2.keys())

1247 ):

1248 source = sensekey_map1[sensekey]

1249 target = sensekey_map2[sensekey]

1250 synset_to_many[source].append(target)

1251 return synset_to_many

1252

1253 def map_to_one(self, version="wordnet"):

1254 self.nomap[version] = set()

1255 self.splits[version] = {}

1256 synset_to_many = self.map_to_many(version)

1257 synset_to_one = {}

1258 for source in synset_to_many:

1259 candidates_bag = synset_to_many[source]

1260 if candidates_bag:

1261 candidates_set = set(candidates_bag)

1262 if len(candidates_set) == 1:

1263 target = candidates_bag[0]

1264 else:

1265 counts = []

1266 for candidate in candidates_set:

1267 counts.append((candidates_bag.count(candidate), candidate))

1268 self.splits[version][source] = counts

1269 target = max(counts)[1]

1270 synset_to_one[source] = target

1271 if source[-1] == "s":

1272 # Add a mapping from "a" to target for applications like omw,

1273 # where only Lithuanian and Slovak use the "s" ss_type.

1274 synset_to_one[f"{source[:-1]}a"] = target

1275 else:

1276 self.nomap[version].add(source)

1277 return synset_to_one

1278

1279 def map_wn(self, version="wordnet"):

1280 """Mapping␣from␣Wordnet␣’version’␣to␣currently␣loaded␣Wordnet␣version"""

1281 if self.get_version() == version:

1282 return None

1283 else:

1284 return self.map_to_one(version)