# Counting and localizing defective nodes by Boolean network tomography

Nicola Galesi
Sapienza Università Roma
Department of Computer Science
Rome, Italy  Fariba Ranjbar
Sapienza Università Roma
Department of Computer Science
Rome, Italy

###### Abstract

Identifying defective items in larger sets is a main problem with many
applications in real life situations. We consider the problem of localizing
defective nodes in networks through an approach based on boolean network
tomography ($\operatorname{\mathsf{BNT}}$), which is grounded on inferring
informations from the boolean outcomes of end-to-end measurements paths.
Identifiability conditions on the set of paths which guarantee discovering or
counting unambiguously the defective nodes are of course very relevant. We
investigate old and introduce new identifiability conditions contributing this
problem both from a theoretical and applied perspective. (1) What is the
precise tradeoff between number of nodes and number of paths such that at most
$k$ nodes can be identified unambiguously ? The answer is known only for $k=1$
and we answer the question for any $k$, setting a problem implicitly left open
in previous works. (2) We study upper and lower bounds on the number of
unambiguously identifiable nodes, introducing new identifiability conditions
which strictly imply and are strictly implied by unambiguous identifiability;
(3) We use these new conditions on one side to design algorithmic heuristics
to count defective nodes in a fine-grained way, on the other side to prove the
first complexity hardness results on the problem of identifying defective
nodes in networks via $\operatorname{\mathsf{BNT}}$. (4) We introduce a random
model where we study lower bounds on the number of unambiguously identifiable
defective nodes and we use this model to estimate that number on real networks
by a maximum likelihood estimate approach.

##  1 Introduction

Identifying a subset of defective items out of a much larger set of items is a
problem that found numerous application in a variety of situations such as
medical screening, network reliability, DNA screening, streaming algorithms.
Network Tomography is a general inference technique based on end-to-end
measurements aimed to extract internal network characteristics such as link
delays and link loss rates but also defective items. In this paper, we
consider Boolean Network Tomography ($\operatorname{\mathsf{BNT}}$) where the
outcome of the measurements is a boolean value. Duffield, who as first
introduced boolean network tomography [3] to identify network failure
components, proposed an inference algorithm based on
$\operatorname{\mathsf{BNT}}$ to identify sets of failure links. The
$\operatorname{\mathsf{BNT}}$ approach was later studied also to identify node
failures in networks [13, 11, 12, 6, 8, 2].

In the case of identifying failure nodes, the $\operatorname{\mathsf{BNT}}$
approach deals with extracting as much accurate as possible information on the
number and the positions of the corrupted nodes from the solutions $\vec{x}$
of a boolean system $\mathbb{P}\vec{x}=\vec{b}$, where $\mathbb{P}$ is the
incidence matrix of the $m$ measurement paths over the $n$ nodes and $\vec{b}$
is the $m$-vector of the boolean outcomes of the measurement paths (see Figure
1). The challenge of localizing failure nodes is that different sets of
failure nodes can produce the same measurement along the paths and so are
indistinguishable from each other using the measurements. This leads to pose
the following question: given the set of paths $\mathbb{P}$ what is the
maximal set of defective nodes we can hope to identify unambiguously ?
Identifiability conditions on the matrix $\mathbb{P}$ under which failure
nodes can be localized unambiguously (or also counted accurately) from the
solution of the system $\mathbb{P}\vec{x}=\vec{b}$ are of course of the utmost
interest. In this paper we study old and introduce new of these conditions,
contributing:

  1. 1.

to understand the combinatorics and the complexity of the theoretical problem
of unambiguously identify failure node sets under the
$\operatorname{\mathsf{BNT}}$ approach, and,

  2. 2.

to devise new algorithms and heuristics to count or localize as more precisely
as possible failure nodes in networks.

$1$$2$$3$$4$$5$$7$$6$

$\begin{array}[]{c||ccccccc||c}\mathbb{P}&1&2&3&4&5&6&7&\vec{b}\\\
\hline\cr{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{1}}&1&1&1&0&1&0&0&1\\\
{\color[rgb]{0.03,0.27,0.49}\definecolor[named]{pgfstrokecolor}{rgb}{0.03,0.27,0.49}{2}}&1&0&1&1&0&0&1&0\\\
{\color[rgb]{0.,0.6,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{0.,0.6,0.2}{3}}&0&0&1&1&1&1&0&1\\\
{\color[rgb]{1.0,0.87,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.87,0.0}{4}}&0&1&0&1&1&0&1&1\\\
\end{array}$

$\left\\{\begin{array}[]{lll}x_{1}\vee x_{2}\vee x_{3}\vee x_{5}&=&1\\\
x_{1}\vee x_{3}\vee x_{4}\vee x_{7}&=&0\\\ x_{3}\vee x_{4}\vee x_{5}\vee
x_{6}&=&1\\\ x_{2}\vee x_{4}\vee x_{5}\vee x_{7}&=&1\end{array}\right.$

Figure 1: (1) A set $\mathbb{P}$ of 4 paths over $7$ nodes. (2) The incidence
matrix of $\mathbb{P}$ and a measurements vector $\vec{b}$. (3) The associated
boolean system. Notice that the outcome $1$ in the measurement of a path
indicates the presence of at least a node failure.

###  1.1 Previous work

The condition introduced as $k$-identifiability (for $\mathbb{P}$) states that
any two distinct node sets of size at most $k$ can be separated by at least a
path in $\mathbb{P}$. $k$-identifiability initially introduced for link
failure detection [10, 14], was later studied with success also for node
failure detection [13, 11, 12, 6, 8, 2]. If this condition is true for a set
of measurements paths $\mathbb{P}$ it ensures that if there are at most $k$
failure nodes in $\mathbb{P}$ then these nodes can be identified
unambiguously. Hence the optimization problem of computing the maximal $k\leq
n$ such that a set $\mathbb{P}$ is $k$-identifiable
($k$-$\operatorname{\mathsf{ID}}$), i.e. admits the $k$-identifiability
property is very relevant to the problem of node failure localization. We
refer to this maximal value as $\mu(\mathbb{P})$ (it was called
$\Omega(\mathbb{P})$ in [11]).

As observed in [11, 12] $k$-identifiability can be scaled to each single node
yet preserving the property for the whole set of paths. A node $u$ is
$k$-$\operatorname{\mathsf{ID}}$ if any two sets of size at most $k$ differing
on $u$ are separated by at least a path in $\mathbb{P}$ (see Definition 2.2).
Hence understanding the combinatorics of the set
$\operatorname{\mathsf{ID}}_{k}(\mathbb{P})$ of the $k$-identifiable nodes in
$\mathbb{P}$ and study upper and lower bounds for
$|\operatorname{\mathsf{ID}}_{k}(\mathbb{P})|$ is of great importance to
develop algorithms to maximize the identification of failure nodes in real
networks.

Both definitions of $k$-identifiability were largely investigated. In [12]
they started this study quantifying the capability of failure localization
through (1) the maximum number of failures such that failures within a given
node set can be localized unambiguously, and (2) the largest node set failures
can be uniquely localized under a given bound on the total number of failures.
These measures where used to evaluate the impact of maximum identifiability on
various parameters of the network (underlying the set of paths) like the
topology, the number of monitor and the probing mechanisms.

In the work [6, 7] we studied $k$-identifiability from the topological point
of view of the graph underlying $\mathbb{P}$. We were proving tight bounds on
the maximum identifiability that can be reached in the case of topologies like
trees, grids and hypergrids and under embeddings on directed graphs. Our
results culminated with a heuristic to design networks with a high degree of
identifiability or to modify a network to boost identifiability. In the work
[8] we were employing Menger’s theorem establishing a precise relation of
$\mu(\mathbb{P})$ with the vertex connectivity of the graph underlying
$\mathbb{P}$. We generalize results in [6] to Line-of-Sight Networks and
started the study of identifiability conditions on random graphs and random
regular graphs.

Monitor placement can be in fact relevant to improve identifiability of
failure nodes. The works [11, 2] considered the problem of optimizing the
capability of identifying network failures through different monitoring
schemes giving upper bounds on the maximum number of identifiable nodes, given
the number of monitoring paths, the routing scheme and the maximum path
length. In [2] in particular studied upper bounds on the set of
$|\operatorname{\mathsf{ID}}_{1}(\mathbb{P})|$ and as in the case of [6] they
provide hueristics on how to design topologies and related monitoring schemes
to achieve the maximum identifiability under various network settings.

###  1.2 Contributions

In this work we introduce new identifiability measures and deepen the study of
$k$-identifiability obtaining several new results and new heuristics to test
networks against the number and position of failing nodes. From a theoretical
perspective our contributions are the following

  1. 1.

We set a question implicitly left open in some previous works [10, 2] about
the limits of upper bounds on identifiability of node failures via Boolean
network tomography. What are the precise tradeoffs between number of nodes $n$
and number of paths $m$ of $\mathbb{P}$ such that $\mathbb{P}$ is no longer
$k$-identifiable, that is $\mu(\mathbb{P})<k$? The answer is known only for
$k=1$ where the tradeoff $n\geq 2^{m}-1$ implies $\mu(\mathbb{P})<1$, is
obtained by a straightforward counting argument ( see Lemma 3.1 and [2]).

Using the notion of regular union-free families, we answer to the problem for
any $2\leq k\leq n$, showing that $n\geq
2^{\frac{k}{k-1}(m+k-1)^{(1+\epsilon)}}$ implies $\mu(\mathbb{P})<k$, for any
$\epsilon>0$.

  2. 2.

We introduce two new identifiability notions, namely, $k$-separability
($k$-$\operatorname{\mathsf{SEP}}$) and $k$-distinguishability
($k$-$\operatorname{\mathsf{DIS}}$). Analogously to identifiability we define
these notions on nodes and we consider the corresponding node sets
$\operatorname{\mathsf{SEP}}_{k}(\mathbb{P})$ and
$\operatorname{\mathsf{DIS}}_{k}(\mathbb{P})$. These conditions provide
significant upper and lower bounds to identifiability: namely we prove that
for all $k\leq n$, $k$-$\operatorname{\mathsf{SEP}}$ implies
$k$-$\operatorname{\mathsf{ID}}$ and $k$-$\operatorname{\mathsf{ID}}$ implies
$k$-$\operatorname{\mathsf{DIS}}$, both strictly. Hence
$\operatorname{\mathsf{SEP}}_{k}(\mathbb{P})\subseteq\operatorname{\mathsf{ID}}_{k}(\mathbb{P})\subseteq\operatorname{\mathsf{DIS}}_{k}(\mathbb{P})$.
We use these measures to get upper and lower bounds for
$|\operatorname{\mathsf{ID}}_{k}(\mathbb{P})|$ and $\mu(\mathbb{P})$, to study
the computational complexity of identifiability conditions and to estimates
the number of $k$-identifiable nodes through a random model. Namely:

  3. 3.

We prove that the problem of deciding the non $k$-separability (hence the non
$k$-identifiability) of a given node in $\mathbb{P}$ is polynomial time
reducible to the minimum hitting set problem ($\operatorname{\mathsf{MHS}}$).
Furthermore we prove that the optimization problem of finding the minimal $k$
such that a given node is not $k$-separable in $\mathbb{P}$ is
$\operatorname{\mathsf{NP}}$\- complete. To our knowledge these are the first
known hardness results of identifiability problems arising from boolean
network tomography.

  4. 4.

We introduce and study a random model for $\mathbb{P}$ based on the binomial
distribution and we estimate lower bounds on the number of $k$-identifiable
nodes $|\operatorname{\mathsf{ID}}_{k}(\mathbb{P})|$ in this model by
analyzing the number of $k$-separable nodes in $\mathbb{P}$.

  5. 5.

We use node distinguishability to study upper bounds on the number of
$k$-identifiable nodes parameterizing the search of such nodes in terms of
specific subset of nodes and specific subset of paths in $\mathbb{P}$. We
introduce the relation (Definition 7.1) $u$ $k$-equal $W$ modulo ${\cal P}$,
where $u$ is node, $W$ a set of nodes and ${\cal P}$ a family of paths in
$\mathbb{P}$ that characterizes non-distinguishability of $u$ restricted to
the set $W$ with respect to ${\cal P}$. A recursive construction (Definition
7.3 of $\tau_{k}$) built on the previous relation allows to upper bound
efficiently the number of $k$-identifiable nodes in a fine-grained way.

From a more applied perspective our results have the following consequences
and applications.

  1. 1.

The result in item 1 can be used as an estimate of upper bounds on the number
of $k$-identifiable nodes in $\mathbb{P}$. As [2] use the result for $k=1$ to
prove that $|\operatorname{\mathsf{ID}}_{1}(\mathbb{P})|\leq\min(n,2^{m}-1)$
(see Theorem 3.2), our bound proves the general statement that for all $2\leq
k\leq n$,
$|\operatorname{\mathsf{ID}}_{k}(\mathbb{P})|\leq\min\\{n,2^{\frac{k}{k-1}(m+k-1)^{(1+\epsilon)}}\\}$
(Theorem 3.9). Our bound can also be used as a black-box in algorithms and
heuristics aimed at approximating the number of identifiable ([13, 11, 12])
nodes which use the bound for $k=1$. For instance the ICE heuristic of [2],
that creates a set of paths $\mathbb{P}$ reaching a certain value of
$\mu(\mathbb{P})$, is generating paths according to the result for $k=1$.

  2. 2.

The fact that the $\operatorname{\mathsf{MHS}}$ problem is reducible to the
non-separability problem (item 3) suggests the idea of using the minimal
hypergraph transversal (instead of a minimum hitting set) to lower bound the
number of separable nodes (hence identifiable nodes) in $\mathbb{P}$. Given an
order of the variables a minimum hypergraph transversal in a set-system can be
efficiently computed. We propose two algorithms based on the hypergraph
transversal (Simple-$\operatorname{\mathsf{SEP}}$ and
Decr-$\operatorname{\mathsf{SEP}}$). In particular in the second algorithm we
use a new idea which partition the set of nodes of $\mathbb{P}$ in family of
subsets of nodes called $0$-decreasing which allow to apply in a more
efficient way the hypergraph transversal heuristic
(Decr-$\operatorname{\mathsf{SEP}}$).

  3. 3.

We employ the random model in item 4 to approximately counting the number of
$k$-identifiable nodes on concrete networks using an approach based on the
maximum likelihood estimate for binomial distributions. Our experimental
results indicate that a lower bound for the number of $k$-identifiable nodes
of a real network can be computed very accurately using a relatively simple
random model based on the binomial distributions and computing the probability
that a node is $k$-separable in this model. We then consider a real set of
measurement paths $\hat{}\mathbb{P}$ as it was a random experiment, we plug in
the MLE estimates on $\hat{}\mathbb{P}$ in the probability formula of the
random model to estimate the cardinality of the sets
$\operatorname{\mathsf{SEP}}_{k}(\hat{}\mathbb{P})$.

  4. 4.

We use the definition of $\tau_{k}$ to upper bound the number of
$k$-identifiable nodes in $\mathbb{P}$ according to specific families of
subset of nodes and subset of paths. As we show in Section 7, this can be used
to compute approximations of the value of $\mu(\mathbb{P})$ and
$|\operatorname{\mathsf{ID}}_{k}(\mathbb{P})|$ which are efficiently
computable (Algorithm lb-$\operatorname{\mathsf{DIS}}_{k}$).

The paper is organized as follows: first we give the preliminary definitions
on boolean network tomography and identifiability, showing the connection with
unambiguous identification of failure nodes. In Section 3 we study the
tradeoffs between number of nodes and number of paths. In Section 4 we give
the definitions of $k$-separability and $k$-distinguishability and prove the
relation with identifiability. In Section 5 we introduce the random model and
we show how to count $k$-separable nodes (hence lower bounds on
$k$-identifiable nodes) on real networks through a maximum likelihood estimate
method. In Section 6 we present the results on the computational complexity of
$k$-identifiability and we introduce two algorithms based on hypergraph
transversal to count identifiable nodes. In Section 7 we introduce the
definition of $\tau_{k}$ and a corresponding method (based on
distinguishability) to compute upper bounds on identifiable nodes in a fine-
grained way, when the set of paths is obtained by taking all the paths in a
graph from a set of sources to a set of target nodes.

##  2 Preliminary definitions

Let $n,k\in\mathbb{N}$ and $k\leq n$. ${[n]\choose k}$ is the set of subsets
of $[n]$ of size $k$. ${[n]\choose\leq k}$ be the set of subsets of $[n]$ of
size at most $k$. $2^{A}$ is the set of subsets of the set $A$. $A\oplus B$ is
the symmetric difference between $A$ and $B$. $\overline{A}$ denotes the
complement of $A$.

Let $n$ and $m$ be positive integers. We encode a set of $m$ paths over nodes
in $[n]$ as a collection $\mathbb{P}$ of $n$ distinct $m$-bit vectors such
that $\mathbb{0}\not\in\mathbb{P}$, i.e. the $m$-bit zero vector is not in
$\mathbb{P}$ (this condition means that each node in $[n]$ is used in at least
a path).

We can view $\mathbb{P}$ in three different ways: as a boolean $m\times
n$-matrix, as a collection of $n$ $m$-bit vectors and as a collection of $m$
$n$-bit vectors. For a node $u\in[n]$, $\mathbb{c}_{u}$ is then the $m$-bit
vector whose $p$-th coordinate indicates whether the node $u$ is in the $p$-th
path or not.

We use also $\mathbb{P}$ in a graph notation as follows: if $u\in[n]$ is a
node, then $\mathbb{P}(u)$ identifies the set of all paths touching $u$, in
other words the set $\\{p\in[m]:\mathbb{P}[p,u]=1\\}$. If $U\subseteq[n]$ is a
set of nodes, $\mathbb{P}(U)$ denotes the set of paths in $[m]$ touching at
least a node in $U$, i.e. $\mathbb{P}(U)=\bigcup_{u\in U}\mathbb{P}(u)$.

###  2.1 Identifiability

Let $\mathbb{P}$ be a set of $m$ paths over $n$ nodes. We consider the
following definition [13]

######  Definition 2.1.

$\mathbb{P}$ is $k$-identifiable if for all $U,W\subseteq[n]$ such that
$|U|,|W|\leq k$ and $U\not=W$, it holds that
$\mathbb{P}(U)\not=\mathbb{P}(W)$.

Notice that in terms of the column-vector notation, the previous definition
says that for all distinct sets $U,W\subseteq[n]$ of size at most $k$,
$\displaystyle\bigvee_{u\in U}\mathbb{c}_{u}\oplus\bigvee_{w\in
W}\mathbb{c}_{w}\not=\mathbb{0}.$

The definition of $k$-identifiability can be equivalently given for nodes
$u\in[n]$ as follows (see also [11]).

######  Definition 2.2.

($k$-identifiable nodes) A node $u\in[n]$ is $k$-identifiable with respect to
$\mathbb{P}$, if for all $U,W\subseteq[n]$ of size at most $k$ and such that
$U\cap\\{u\\}\not=W\cap\\{u\\}$, it holds that
$\mathbb{P}(U)\not=\mathbb{P}(W)$.

$\operatorname{\mathsf{ID}}_{k}(\mathbb{P})$ denotes the set of
$k$-identifiable nodes in $\mathbb{P}$. From the definitions a second of
thought allows to see that $k$-identifiability implies
$k^{\prime}$-identifiability for $k^{\prime}<k$. Hence

######  Lemma 2.3.

Let $\mathbb{P}$ be a set of $m$ paths over $n$ nodes. Then
$\operatorname{\mathsf{ID}}_{k}(\mathbb{P})\subseteq\operatorname{\mathsf{ID}}_{k^{\prime}}(\mathbb{P})$
for $k^{\prime}\leq k\leq n$.

Furthermore scaling to identifiability of nodes does not affect the main
property of $k$-identifiability (which we see below). Next theorem is proved
in [11] (Theorem 4).

######  Theorem 2.4.

([11]) Let $\mathbb{P}$ be a set of $m$ paths over $n$ nodes. $\mathbb{P}$ is
$k$-identifiable if and only if every node in $[n]$ is $k$-identifiable with
respect to $\mathbb{P}$.

We denote by $\mu(\mathbb{P})$ the maximal $k\leq n$ s.t. $\mathbb{P}$ is
$k$-identifiable.

Let us motivate our definitions in the context of the approach of boolean
network tomography to detect failure nodes in networks. Assume to have a set
$\mathbb{P}$ of $m$ end-to-end paths over $n$ nodes $\mathbb{P}$. A binary
measurement $\mathbb{M}$ along a path $p\in[m]$ is obtained by sending a
message through $p$ and recording the outcome $\mathbb{M}(p)$, a bit, which
identifies (in the case $\mathbb{M}(p)=1$) that some node in $p$ is failing,
or (in the case $\mathbb{M}(p)=0$) that no node is failing along the path $p$.

We claim that if $\mathbb{P}$ is $k$-identifiable, then under any binary
measurement $\mathbb{M}$, we can uniquely localize in $\mathbb{P}$ up to $k$
failing nodes. Given a binary measurement $\mathbb{M}$ over $\mathbb{P}$, let
$\operatorname{\mathsf{fail}}_{\mathbb{M}}(\mathbb{P})=\\{p\in[m]|\mathbb{M}(p)=1\\}$.

######  Definition 2.5.

(Unique failure) Let $\mathbb{P}$ be a set of $m$ paths over $n$ nodes and
$\mathbb{M}$ a binary measurement on $\mathbb{P}$. A set of nodes
$W\subseteq[n]$ is failing in $\mathbb{P}$ if
$\mathbb{P}(W)\subseteq\operatorname{\mathsf{fail}}_{\mathbb{M}}(\mathbb{P})$.
$W$ is uniquely failing if it is failing and furthermore
$\overline{\mathbb{P}(W)}\subseteq\overline{\operatorname{\mathsf{fail}}_{\mathbb{M}}(\mathbb{P})}$,
i.e. on any path not touching $W$ the measurement is not failing.

######  Theorem 2.6.

Let $\mathbb{P}$ be a set of $m$ paths over $n$ nodes. If $\mu(\mathbb{P})\geq
k$, then there is exactly one set of nodes of size at most $k$ that is
uniquely failing in $\mathbb{P}$.

###### Proof.

Let $\mathbb{M}$ be a measurements over $\mathbb{P}$. Assume by contradiction
that there are two distinct sets $U$ and $W$ of size at most $k$ which are
both uniquely failing in $\mathbb{P}$ under $\mathbb{M}$. Since $U\not=W$, and
$\mathbb{P}$ is $k$-identifiabale, then there is either a
$p\in\mathbb{P}(U)\setminus\mathbb{P}(W)$ or a
$p\in\mathbb{P}(W)\setminus\mathbb{P}(U)$. Assume wlog the former. Since $U$
is failing, then $\mathbb{M}(p)=0$. But since $W$ is uniquely failing and
$p\in\overline{\mathbb{P}(W)}$, then
$p\in\overline{\operatorname{\mathsf{fail}}_{\mathbb{M}}(\mathbb{P})}$ and
hence $\mathbb{M}(p)=1$. Contradiction. ∎

##  3 Upper bounds on $\mu(\mathbb{P})$ by counting

In this subsection we show that under what bounds on the number of paths $m$
in $\mathbb{P}$, we have that $\mu(\mathbb{P})<k$. We start by showing under
what conditions on $m$, $\mu(\mathbb{P})<1$.

Notice that to prove that $\mu(\mathbb{P})<1$, by Definition 2.1 it is
sufficient to find two distinct nodes $u,w\in[n]$ such that
$\mathbb{c}_{u}\oplus\mathbb{c}_{w}=\mathbb{0}$, that is for all
$p\in[m]:\mathbb{c}_{u}[p]=\mathbb{c}_{w}[p]$. $\mu(\mathbb{P})<1$ will follow
from a easy information theoretic bound on sets of $m$-vectors.

######  Lemma 3.1.

Let $\mathbb{P}$ be a set of $m$ paths built on $n$ nodes. If
$m<\log_{2}(n+1)$, then $\mu(\mathbb{P})<1$.

###### Proof.

$\mathbb{P}$ is a collection of $n$ $m$-bit strings. There are at most
$2^{m}-1$ different such strings ($\mathbb{0}\not\in\mathbb{P}$). Hence
whenever $n>2^{m}-1$ there are two elements $u\not=w\in[n]$ such that
$\mathbb{c}_{u}=\mathbb{c}_{w}$, which means
$\mathbb{c}_{u}\oplus\mathbb{c}_{w}=\mathbb{0}$. ∎

Corollary IV.1 in [2] can be obtained by previous observation immediately.

######  Theorem 3.2.

([2]) Let $\mathbb{P}$ be a set of $m$ paths over $n$ nodes. Then
$|\operatorname{\mathsf{ID}}_{1}(\mathbb{P})|\leq\min\\{n,2^{m}-1\\}$.

###### Proof.

$|\operatorname{\mathsf{ID}}_{1}(\mathbb{P})|\leq n$ since it is a set of
nodes. Assume that $n>2^{m}-1$, hence by previous Lemma 3.1
$\mu(\mathbb{P})=0$, hence there are at least two nodes $u_{1}\not=u_{2}$ not
$1$-identifiable. Hence $|\operatorname{\mathsf{ID}}_{1}(\mathbb{P})|\leq
2^{m}-1$ ∎

We will prove a similar results for $\mu(\mathbb{P})<k$ for a generic $k\leq
n$.

###  3.1 Union-free families and upper bounds for $k$-identifiability

A hypergraph $\mathcal{F}$ on the set $[m]$ is a family of distinct subsets of
$[m]$, called edges of $\mathcal{F}$. If each edge is of fixed size $r\leq m$,
then $\mathcal{F}$ is said to be $r$-regular, i.e.,
$\mathcal{F}\subset{[m]\choose r}$.

######  Definition 3.3.

For a positive integer $k$, $\mathcal{F}$ is called $k$-union-free if for any
two distinct subsets of edges $\mathcal{A},\mathcal{B}\subseteq\mathcal{F}$,
with $1\leq|\mathcal{A}|,|\mathcal{B}|\leq k$, it holds that
$\displaystyle\cup_{A\in\mathcal{A}}A\not=\cup_{B\in\mathcal{B}}B$.

Union-free regular hypergraphs are investigated in extremal combinatorics [5].
It is immediate to see that a set $\mathbb{P}$ of $m$ paths over $n$ nodes
defines a hypergraph ${\cal F}_{\mathbb{P}}$ on the set $[m]$ in the following
way: for $i\in[n]$ let $A_{i}=\\{j\in[m]|\mathbb{c}_{i}[j]=1\\}$ and define
${\cal F}_{\mathbb{P}}=\\{A_{1},\ldots,A_{n}\\}$. Given a $U\subseteq[n]$,
consider the subset of ${\cal F}_{\mathbb{P}}$, ${\cal U}=\\{A_{i}\in{\cal
F}_{\mathbb{P}}|i\in U\\}$. Observe that then
$\mathbb{P}(U)=\bigcup_{A\in{\cal U}}A$. Hence immediately by definition of
$k$-identifiability and that of $k$-union-freeness it follows that:

######  Lemma 3.4.

If $\mathbb{P}$ is a set of $m$ paths over $n$ nodes and $\mu(\mathbb{P})\geq
k$, then ${\cal F}_{\mathbb{P}}$ is k-union free.

${\cal F}_{\mathbb{P}}$ is not necessary a regular hypergraph. For $r\in[m]$
let ${\cal F}_{\mathbb{P}}(r)=\\{A\in{\cal F}_{\mathbb{P}}||A|=r\\}$. Notice
that each ${\cal F}_{\mathbb{P}}(r)$ is now a $r$-regular hypergraph on $[m]$.
Moreover the family of the ${\cal F}_{\mathbb{P}}(r)$’s partitions ${\cal
F}_{\mathbb{P}}$ and hence $|{\cal F}_{\mathbb{P}}|=\sum_{r\in[m]}|{\cal
F}_{\mathbb{P}}(r)|$. Since $|{\cal F}_{\mathbb{P}}|=n$, it follows that:

######  Lemma 3.5.

$\sum_{r\in[m]}|{\cal F}_{\mathbb{P}}(r)|=n$.

Furthermore notice that if ${\cal F}_{\mathbb{P}}$ is $k$-union free then such
it will be ${\cal F}_{\mathbb{P}}(r)$ for each $r\in[m]$.

Let $m>r$, $k\in[m]$ with $k\geq 2$, and let $f(k,r,m)$ denote the maximum
cardinality of a $k$-union-free $r$-regular hypergraph over $[m]$.

######  Theorem 3.6 ([5, 15]).

$\Omega(m^{\frac{r}{k-1}})\leq f(k,r,m)\leq O(m^{\lceil\frac{r}{k-1}\rceil}).$

Let $m_{0}\in\mathbb{N}$ and $C$ be the constant such that for all $m\geq
m_{0}$, $f(k,r,m)\leq Cm^{\lceil\frac{r}{k-1}\rceil}$.

######  Theorem 3.7.

Let $m$ be an integer such that $m\geq m_{0}$. Let $\mathbb{P}$ be a set of
$m$ paths over $n$ nodes. If $n>\sum_{r\in[m]}Cm^{\lceil\frac{r}{k-1}\rceil}$,
then $\mu(\mathbb{P})<k$.

###### Proof.

Assume by contradiction that $n>\sum_{r\in[m]}Cm^{\lceil\frac{r}{k-1}\rceil}$
and $\mu(\mathbb{P})\geq k$. By Lemma 3.4 ${\cal F}_{\mathbb{P}}$ is $k$-union
free. Hence (see observation after Lemma 3.5) for each $r\in[m]$, ${\cal
F}_{\mathbb{P}}(r)$ is a $r$-regular $k$-union free hypergraph and hence by
previous theorem $|{\cal F}_{\mathbb{P}}(r)|\leq
Cm^{\lceil\frac{r}{k-1}\rceil}$. The ${\cal F}_{\mathbb{P}}(r)$ partition
${\cal F}_{\mathbb{P}}$ and by Lemma 3.5 we have $n=\sum_{r\in[m]}|{\cal
F}_{\mathbb{P}}(r)|\leq\sum_{r\in[m]}Cm^{\lceil\frac{r}{k-1}\rceil}$. ∎

######  Corollary 3.8.

Let $\mathbb{P}$ be a set of $m$ paths over $n$ nodes and $2\leq k\leq m$. If
$m<\sqrt[1+\epsilon]{\frac{(k-1)}{k}(\log_{2}n-D)}-(k-1)$, for some
$\epsilon>0$ and where $D=\log C$, then $\mu(\mathbb{P})<k$.

###### Proof.

Assume for the moment that $m$ divides $k-1$. We prove that if
$m<\sqrt[1+\epsilon]{\frac{(k-1)}{k}(\log_{2}n-D)}$, then

$\displaystyle n>Cmm^{\frac{m}{k-1}}.$ (1)

This immediately implies $n>\sum_{r\in[m]}Cm^{\lceil\frac{r}{k-1}\rceil}$,
since $\sum_{r\in[m]}Cm^{\lceil\frac{r}{k-1}\rceil}\leq Cmm^{\frac{m}{k-1}}$.
Equation 1 follows by the following implications:

$\displaystyle m<\sqrt[1+\epsilon]{\frac{k-1}{k}(\log_{2}n-D)}$ (2)
$\displaystyle m^{1+\epsilon}<\frac{k-1}{k}(\log_{2}n-D)$ (3)
$\displaystyle\frac{k}{k-1}m^{1+\epsilon}<\log_{2}n-D$ (4) $\displaystyle\log
C+\frac{k}{k-1}m\log m<\log n$ (5) $\displaystyle\log C+\log
m+\frac{m}{k-1}\log m<\log n$ (6) $\displaystyle Cmm^{\frac{m}{k-1}}<n$ (7)

Equation 6 follows from Equation 5 since $K=\frac{k}{k-1}>1$ and $Km\log
m>\log m+\frac{m\log m}{k-1}$ for all $m$.

If $m$ does not divide $(k-1)$, let $a<(k-1)$ be the smallest non-negative
integer such that $m+a$ divides $k-1$. Hence $m+a<m+(k-1)$. Let $\hat{m}=m+a$.
Since $m<\sqrt[1+\epsilon]{\frac{(k-1)}{k}(\log_{2}n-D)}-(k-1)$, then
$\hat{m}<\sqrt[1+\epsilon]{\frac{(k-1)}{k}(\log_{2}n-D)}$. Hence the previous
argument proves that $n>C\hat{m}\hat{m}^{\frac{\hat{m}}{k-1}}$. Since
$m<\hat{m}$, then $n>Cmm^{\frac{m}{k-1}}$. Now by Theorem 3.7, this implies
that $\mu(\mathbb{P})<k$. ∎

######  Theorem 3.9.

Let $\mathbb{P}$ be a set of $m$ paths over $n$ nodes. Then for all $k\leq n$,
$|\operatorname{\mathsf{ID}}_{k}(\mathbb{P})|\leq\min\\{n,2^{\frac{k(m+2k-2))^{2}}{k-1}}\\}$.

###### Proof.

Notice that if $n\geq 2^{\frac{k(m+k-1)^{2}}{k-1}}$, then
$m<\sqrt[1+\epsilon]{\frac{(k-1)}{k}(\log_{2}n-D)}-(k-1)$. Hence Corollary 3.8
and the same proof of Theorem 3.2 imply the claim. ∎

##  4 Refining identifiability: separability and distinguishability

We introduce two new definitions approximating identifiability from above and
from below that we are going to use to prove upper and lower bounds on the
number of $k$-identifiable nodes.

######  Definition 4.1.

($k$-separable nodes) A node $u\in[n]$ is $k$-separable in $\mathbb{P}$, if
for all $U\subseteq[n]$ of size at most $k$ and such that $u\not\in U$, it
holds that there is a path $p\in\mathbb{P}(u)\setminus\mathbb{P}(U)$, i.e.
there is at least a path passing though $u$ but not touching any node of $U$.

We say that $\mathbb{P}$ is $k$-separable if each node $u\in[n]$ is
$k$-separable. $k$-separability is a stronger notion than $k$-identifiability
as captured by the following lemma.

######  Lemma 4.2.

If $u$ is $k$-separable in $\mathbb{P}$, then $u$ is is $k$-identifiable in
$\mathbb{P}$.

###### Proof.

Let $U$ and $W$ be distinct subset of $[n]$ of size at most $k$. Then there
exists a $u$ such that $U\cap\\{u\\}\not=W\cap\\{u\\}$ and then either $u\in
U\setminus W$ or $u\in W\setminus U$. Assume wlog the former. Then $u\not\in\
W$. $u$ is $k$-separable in $\mathbb{P}$, there is a path
$p\in\mathbb{P}(u)\setminus\mathbb{P}(W)$. Since $u\in U$, then
$p\in\mathbb{P}(U)\setminus\mathbb{P}(W)$ and then
$\mathbb{P}(U)\not=\mathbb{P}(W)$. ∎

Notice that opposite direction is not true as we argue: assume that
$\mathbb{P}$ is $k$-identifiable and that $u\not\in W$ for $W$ a set of at
most $k$ nodes. The $k$-identifiability of $\mathbb{P}$ implies that
$\mathbb{P}(u)\not=\mathbb{P}(W)$, yet this condition alone does not guarantee
that the path separating $\\{u\\}$ from $W$, pass through $u$ and not touching
$W$.

######  Definition 4.3.

($k$-distinguishable nodes) A node $u\in[n]$ is $k$-distinguishable in
$\mathbb{P}$, if for all $U\subseteq[n]$ of size at most $k$ and such that
$u\not\in U$, it holds $\mathbb{P}(u)\not=\mathbb{P}(U)$.

We say that $\mathbb{P}$ is $k$-distinguishable if each node $u\in[n]$ is
$k$-distinguishable.

######  Lemma 4.4.

If $u$ is is $k$-identifiable in $\mathbb{P}$, then $u$ is $k$-distinguishable
in $\mathbb{P}$.

###### Proof.

Assume that $u\in[n]$ is $k$-$\operatorname{\mathsf{ID}}$ in. $\mathbb{P}$.
Let $W\subseteq[n]$ of size at most $k$ such that $u\not\in W$. We want to
prove that $\mathbb{P}(u)\not=\mathbb{P}(W)$. By
$k$-$\operatorname{\mathsf{ID}}$ of $u$ we know that for all $U^{\prime}$ and
$W^{\prime}$ in $[n]$ of size at most $k$ such that
$U^{\prime}\cap\\{u\\}\not=W^{\prime}\cap\\{u\\}$, it holds that
$\mathbb{P}(U^{\prime})\not=\mathbb{P}(W^{\prime})$. Fix $U^{\prime}=\\{u\\}$
and $W^{\prime}=W$. Since $u\not\in W$, then
$U^{\prime}\cap\\{u\\}\not=W^{\prime}\cap\\{u\\}$, hence
$\mathbb{P}(u)\not=\mathbb{P}(W)$, as required. ∎

Notice that the opposite direction is not necessary true: indeed if $u\in
U\setminus W$, knowing that $\mathbb{P}(u)\not=\mathbb{P}(W)$ it is not
sufficient to conclude $\mathbb{P}(U)\not=\mathbb{P}(W)$, exactly in those
case when $\mathbb{P}(u)\not=\mathbb{P}(W)$ is witnessed by a path in
$\mathbb{P}(W)\setminus\mathbb{P}(u)$, which can touch other nodes in $U$ but
not $u$.

We denote by
$\operatorname{\mathsf{ID}}_{k}(\mathbb{P}),\operatorname{\mathsf{SEP}}_{k}(\mathbb{P}),\operatorname{\mathsf{DIS}}_{k}(\mathbb{P})$
the set of nodes which are respectively $k$-identifiable, $k$-separable and
$k$-distinguishable in $\mathbb{P}$. And we use to say respectively that $u$
is $k$-$\operatorname{\mathsf{ID}}$, $k$-$\operatorname{\mathsf{SEP}}$ and
$k$-$\operatorname{\mathsf{DIS}}$ in $\mathbb{P}$.

By previous Lemmas and discussion it holds that

######  Lemma 4.5.

For all $k\in[n]$,
$|\operatorname{\mathsf{SEP}}_{k}(\mathbb{P})|\leq|\operatorname{\mathsf{ID}}_{k}(\mathbb{P})|\leq|\operatorname{\mathsf{DIS}}_{k}(\mathbb{P})|$.

Furthermore since the three properties are clearly antimonotone, it holds
that;

######  Lemma 4.6.

For all $k\in[n]$,
$\operatorname{\mathsf{ID}}_{k}(\mathbb{P})\subseteq\operatorname{\mathsf{ID}}_{k-1}(\mathbb{P})$,
$\operatorname{\mathsf{SEP}}_{k}(\mathbb{P})\subseteq\operatorname{\mathsf{SEP}}_{k-1}(\mathbb{P})$,
$\operatorname{\mathsf{DIS}}_{k}(\mathbb{P})\subseteq\operatorname{\mathsf{DIS}}_{k-1}(\mathbb{P})$

We denote by $\sigma(\mathbb{P})$ (respectively $\delta(\mathbb{P})$) the
maximal $k\leq n$ s.t. $\mathbb{P}$ is $k$-separable (respectively
$k$-distinguishable). Hence we have
$\delta(\mathbb{P})\leq\mu(\mathbb{P})\leq\sigma(\mathbb{P})$.

##  5 Lower bounds on $\mu(\mathbb{P})$ by a random model

To study lower bounds on $\operatorname{\mathsf{ID}}_{k}(\mathbb{P})$ (or on
$\mu(\mathbb{P})$) for real set of paths we introduce a simple random model.
We are given $m$ and $n$ natural numbers and $n$ real numbers
$\lambda_{i}\in[0,1]$. The random set $\mathbb{P}$ of $m$ paths over $n$ nodes
is obtained by taking independently $n$ binary strings of length $m$ such that
the $i$-th string is distributed according to the binomial distributions
$\operatorname{\mathsf{Bin}}(m,\lambda_{i})$. That means that node $i\in[n]$
will be present on each path with probability $\lambda_{i}$ and absent with
probability $(1-\lambda_{i})$.

Our approach to estimate $|\operatorname{\mathsf{ID}}_{k}(\mathbb{P})|$ is the
following:

  1. 1.

by Lemma 4.5,
$|\operatorname{\mathsf{SEP}}_{k}(\mathbb{P})|\leq|\operatorname{\mathsf{ID}}_{k}(\mathbb{P})|$.

  2. 2.

For $u\in[n]$ we obtain
$\nu_{n,m,\lambda}(u)=\Pr[u\in\operatorname{\mathsf{SEP}}_{k}(\mathbb{P})]$.

  3. 3.

Given a real set $\hat{}\mathbb{P}$ of $M$ paths on $N$ nodes, we consider
$\hat{}\mathbb{P}$ to be a random experiment and from $\hat{}\mathbb{P}$ we
compute a maximum likelihood estimate $\hat{\lambda}_{i}$ for each of the
$\lambda_{i}$.

  4. 4.

We estimate
$|\operatorname{\mathsf{SEP}}_{k}(\hat{}\mathbb{P})|=\displaystyle\sum_{u\in[N]}\nu_{N,M,\hat{\lambda}}(u)$

Let $u\in[n]$ and $W\in{[n]-\\{u\\}\choose\leq k}$. Let us say that $(u,W)$ is
$\operatorname{\mathsf{GOOD}}$ if there is a path $p\in[m]$ such that
$p\in\mathbb{P}(u)\setminus\mathbb{P}(W)$. $(u,W)$ is
$\operatorname{\mathsf{BAD}}$ if it is not $\operatorname{\mathsf{GOOD}}$.

######  Lemma 5.1.

Let $u\in[n]$ and $W\subseteq[n]\setminus\\{u\\}$.
$\Pr[(u,W)\operatorname{\mathsf{BAD}}]=\left(1-\lambda_{u}\prod_{w\in
W}(1-\lambda_{w})\right)^{m}.$

###### Proof.

$(u,W)$ is $\operatorname{\mathsf{BAD}}$ if and only if for all
$p\in[m]:(p(u)\rightarrow p(W))$. Then
$\Pr[(u,W)\operatorname{\mathsf{BAD}}]=\left(\Pr[(p(u)\rightarrow
p(W))]\right)^{m}$. The condition $p(u)\rightarrow p(W)$ is the same as $\neg
p(u)\vee\bigvee_{w\in W}p(w)$ which is the same as
$\neg\left(p(u)\wedge\bigwedge_{w\in W}\neg p(w)\right)$.
$\Pr[p(u)]=\lambda_{u}$ and $\Pr[\neg p(w)]=(1-\lambda_{w})$. Hence the claim.
∎

Let $k\leq n$. and let $S(k)={[n-1]\choose\leq k}$.

######  Theorem 5.2.

Let $n,m,k\in\mathbb{N}$, $u\in[n]$, and $k\leq n$.
$\Pr[u\in\operatorname{\mathsf{SEP}}_{k}(\mathbb{P})]=\displaystyle\prod_{W\in
S(k)}\left(1-(1-\lambda_{u}\prod_{w\in W}(1-\lambda_{w}))^{m}\right).$

###### Proof.

Observe that $\Pr[u\in\operatorname{\mathsf{SEP}}_{k}(\mathbb{P})]=\Pr[\mbox{
$u$ is $k$-$\operatorname{\mathsf{SEP}}$ in $\mathbb{P}$}]=\Pr[\forall
W\mbox{with $u\not\in\\!W$ and $|W|\leq
k$}:(u,W)\operatorname{\mathsf{GOOD}}]$. By previous Lemma
$\Pr[(u,W)\operatorname{\mathsf{GOOD}}]=1-(1-\lambda_{u}\prod_{w\in
W}(1-\lambda_{w}))^{m}$. Hence the theorem follows. ∎

Assume we have a set $\hat{}\mathbb{P}$ of $m$ paths over $n$ nodes. We
consider $\hat{}\mathbb{P}$ as a random experiment. The standard approach to
compute an MLE estimate $\hat{\lambda}_{i}$ of the $\lambda_{i}$ in the case
of binomial distribution is to compute $\hat{\lambda}_{i}$ as the zero of the
polynomial obtained by the prime derivative of the function expressing the
probability that the node $i$ touches $N_{i}$ paths in $\hat{}\mathbb{P}$.

Let $p_{i}=\Pr[\mbox{ node }i\mbox{ touches }N_{i}\mbox{ paths in
}\mathbb{P}]$. Since in $\mathbb{P}$ the column $i$ is distributed accordingly
to the $\operatorname{\mathsf{Bin}}(m,\lambda_{i})$, then $p_{i}={m\choose
N_{i}}\lambda_{i}^{N_{i}}(1-\lambda_{i})^{m-N_{i}}$ . We study
$\frac{d}{d\lambda_{i}}p_{i}$ and compute $\hat{\lambda}_{i}$ by setting
$\frac{d}{d\lambda_{i}}p_{i}=0$. It is easy to see that this happen for
$\hat{\lambda}_{i}=\frac{N_{i}}{M}$.

Figure 2: Data on the network BTEurope

Figure 3: The network ClaraNet and a Bridge Network

###  5.1 Experiments

Let
$\nu_{n,m,\vec{\lambda}}(u)=\Pr[u\in\operatorname{\mathsf{SEP}}_{k}(\mathbb{P})]$.
Assume to have a real set of $M$ paths $\hat{}\mathbb{P}$ over $N$ nodes. From
$\hat{}\mathbb{P}$ we extract the $\hat{\lambda}_{i}$ for all $i\in[N]$ and we
then estimate $|\operatorname{\mathsf{SEP}}_{k}(\hat{}\mathbb{P})|$ as
$\chi(\hat{}\mathbb{P},k,\hat{\lambda})=\displaystyle\sum_{u\in[N]}\nu_{N,M,\hat{\lambda}}(u)$,
using the closed formula in Theorem 5.2.

In Figure 2 and 3 we consider two graphs from the Internet topology Zoo
(ClaraNet and BTEurope) and we consider set of measurement paths $\mathbb{P}$
obtained from these networks by taking all the different paths starting in
source and ending in a target node (green nodes are source and red nodes are
target). In the second table in each Figure ee compare the real values of
$|SEP_{k}(\mathbb{P})|$ with the values of
$\chi(\hat{}\mathbb{P},k,\hat{\lambda})$ for all these paths obtaining results
very tight to the real values. Notice that to compute
$\nu_{N,M,\hat{\lambda}}(u)$ we need to compute
$\Pr[(u,W)\operatorname{\mathsf{GOOD}}]$ for all $W\in S(k)$111This is because
we need to use the $\lambda_{w}$ for all $w\in W$.. We consider another
estimates of $|\operatorname{\mathsf{SEP}}_{k}(\hat{}\mathbb{P})|$ obtained
from $\chi(\hat{}\mathbb{P},k,\vec{\hat{\lambda}})$ by having only one value
for all the $\lambda_{i}$’s. We consider the significant case
$\chi_{2}(\hat{}\mathbb{P},k,{\hat{\lambda}_{\max}})$, where
$\hat{\lambda}_{\max}=\max_{i}\lambda_{i}$222It is easy to see that
$\chi(\hat{}\mathbb{P},k,\vec{\hat{\lambda}})\geq\chi_{2}(\hat{}\mathbb{P},k,{\hat{\lambda}_{\max}})$..
Notice that in these cases we do not have to have available all the
$\lambda_{w}$ for all $W\subseteq[n]$ of size at most $k$ and the computation
can be made much less expensive since
$\chi_{2}(\hat{}\mathbb{P},k,{\hat{\lambda}_{\max}})=\prod_{j\in[k]}(1-(1-\lambda_{u}(1-\lambda_{\max})^{j})^{m})^{{n-1\choose
j}}$ and we can use methods to approximate ${n-1\choose j}$. The estimates
$\chi_{2}$ is already very good in all these examples.

In each table we also scatter the estimates $\hat{\lambda}_{i}$ coming from
the MLE method.

##  6 Complexity of $k$-identifiability and the minimum hitting set

Consider the optimization problem Minimum Hitting Set,
$\operatorname{\mathsf{MHS}}$, that given an hypergraph (a set-system) ${\cal
H}=(V,E)$, where $E\subseteq 2^{V}$, asks to find the smallest
$V^{\prime}\subseteq V$ such that for all $e\in E$, $V^{\prime}\cap
e\not=\emptyset$. $\operatorname{\mathsf{MHS}}$ is a notorious
$\operatorname{\mathsf{NP}}$-complete problem [1, 9] extending vertex cover.

We show how to use $\operatorname{\mathsf{MHS}}$ to find the minimal $k$ such
that $u$ is not $k$-$\operatorname{\mathsf{ID}}$ in $\mathbb{P}$, i.e. there
exits a set of nodes $W$ of size $|W|\leq k$ , such that
$\mathbb{P}(u)\subseteq\mathbb{P}(W)$.

######  Theorem 6.1.

Assume $\operatorname{\mathsf{MHS}}$ is solvable in polynomial time, then,
deciding whether $u$ is not $k$-$\operatorname{\mathsf{SEP}}$ in $\mathbb{P}$
is solvable in polynomial time.

###### Proof.

Consider the subset $T(u)$ of $[n]$ of those nodes touching at least a path in
$\mathbb{P}(u)$. Let $Y$ be the vector of dimension $|\mathbb{P}(u)|$ defined
in the $j$-th coordinate as follows:

$Y[j]=\bigvee_{v\in T(u)}\mathbb{P}[j,v]\quad\quad\quad j\in\mathbb{P}(u)$

$Y$ has no $0$-coordinate. For otherwise there is a path in $\mathbb{P}$ only
touching $u$. Hence $Y$ has all $1$-coordinates. We consider the set-system
${\cal H}$ obtained from $\mathbb{P}$ by restricting the columns to $T(u)$ and
the rows to $\mathbb{P}(u)$. Let $W$ be the smallest subset of $T(u)$ provided
by $\operatorname{\mathsf{MHS}}$ and covering all $\mathbb{P}(u)$. Hence $u$
is not $|W|$-$\operatorname{\mathsf{SEP}}$, since
$\mathbb{P}(u)\subseteq\mathbb{P}(W)$.

The optimality of the bound is an immediate consequence of the optimality of
$\operatorname{\mathsf{MHS}}$. There is no subset $Z$ of $[n]$ smaller than
$U$ such that $\mathbb{P}(u)\subseteq\mathbb{P}(Z)$, since of course
$Z\subseteq T(u)$ and, by optimality of $\operatorname{\mathsf{MHS}}$, $Z$ it
cannot be smaller than $U$. ∎

The problem of finding a minimal transversal in an hypergraph is a
simplification of $\operatorname{\mathsf{MHS}}$ (see below) which can be
decided efficiently. Our reduction hence suggests to implement an algorithm on
concrete example of paths where we find the smallest transversal instead of
the minimal hitting set.

Let us recall the following definitions from hypergraph transversal problem
[4].

######  Definition 6.2.

Let ${\cal H}=(V,E)$ be an hypergraph. A set $T\subseteq V$ is called a
transversal of $H$ if it meets all the edges of $H$, i.e. if $\forall e\in
E:T\cap e\not=\emptyset$. A transversal $T$ is called minimal if no proper
subset $T^{\prime}$ of $T$ is a transversal.

It is possible to find in time $O(|V||E|)$ a minimal transversal of ${\cal H}$
by the following algorithm (see also [4]). If $E=\emptyset$, then every subset
of $V$ is a transversal of ${\cal H}$, hence the minimal one is $\emptyset$.
If $E\not=\emptyset$, let $V=\\{v_{1},\ldots v_{n}\\}$. Then define:

$\begin{array}[]{l}V_{0}=V\\\
V_{i+1}=\left\\{\begin{array}[]{ll}V_{i}&V_{i}\setminus\\{v_{i}\\}\mbox{ is
not a transversal of ${\cal H}$}\\\
V_{i}\setminus\\{v_{i}\\}&V_{i}\setminus\\{v_{i}\\}\mbox{ is a transversal of
${\cal H}$}\end{array}\right.\end{array}$

Hence $V_{n}$ is a minimal transversal of ${\cal H}$. Notice however that
$V_{n}$ it is not necessarily the smallest (by cardinality) transversal of
${\cal H}$. In fact this last problem is the $\operatorname{\mathsf{MHS}}$
problem which is $\operatorname{\mathsf{NP}}$-hard.

Let us call ${\tt HT}$ be a procedure that implements the previous algorithm
on a given ${\cal H}(V,E)$, and given an order on $V$, and outputs a minimal
transversal of ${\cal H}$.

The proof of Theorem 6.1 suggests an algorithm to compute an upper bound on
the $k$-separablity of a node $u$ in $\mathbb{P}$, where instead of computing
the minimum hitting set we compute a minimal transversal using ${\tt HT}$ on
any order of the variables.

Data: $\mathbb{P},u$

Result: $(W,s)$ s.t. $\mathbb{P}(u)\subseteq\mathbb{P}(W)$ and $|W|=s$

1

2$W={\tt HT}([n],\mathbb{P}(u))$;

return $(W,|W|)$;

Algorithm 1 Algorithm Simple-$\operatorname{\mathsf{SEP}}$

However we can think of a slightly different algorithm which is computing HT
not only once on $([n],\mathbb{P}(u))$ but several times on a sequence of
hypergraphs of decreasing complexity.

Consider the following sets: for all $i\in\mathbb{P}(u)$, let
$Z(v)=\\{i\in[n]\;|\;\mathbb{P}[i,v]=0\\}$, for all $v\in[n]$ and
$V^{i}=\\{v\in[n]\;|\;|\mathbb{P}(u)\cap Z(v)|=i\\}$. Let $I=\\{i_{1},\ldots
i_{N}\\}\subseteq\mathbb{P}(u)$ be the set of indices of the
$V_{i_{j}}\not=\emptyset$. We say that $V_{i_{N}},\ldots,V_{i_{1}}$ is a
$0$-decreasing sequence since, by definition, $Z(v)>Z(w)$ whenever $v\in
V_{i}$, $w\in V_{j}$ and $i<j$.

Data: $\mathbb{P},u$

Result: $(W,s)$ s.t. $\mathbb{P}(u)\subseteq\mathbb{P}(W)$ and $|W|=s$

1

2Compute all $V_{i}$’s ;

3 Compute $I$ ;

4 $\mathbb{P}_{0}[u]=\mathbb{P}[u]$;

5 for  _$l=0\ldots N$_ do

6 $k=N-l$;

7 for  _$j\in\mathbb{P}(u)$_ do

8 if  _$j\in\mathbb{P}_{l}[u]$_ then

9 $\vec{Y}_{i_{k}}[j]=\bigvee_{v\in V_{i_{k}}}\\!\\!\\!\mathbb{P}_{l}[j,u]$

10 else

11 $\vec{Y}_{i_{k}}[j]=0$ ;

12 end if

13

14 end for

15 $\hat{V}_{i_{k}}={\tt HT}(V_{i_{k}},\mathbb{P}_{l}[u])$;

16 $Z_{i_{k}}$ = $0$-coordinates of $Y_{i_{k}}$;

17 $\mathbb{P}_{l+1}(u)=\mathbb{P}_{l}(u)\cap Z_{i_{k}}$;

18

19 end for

20${\cal Y}={\tt HT}(I,\bigcup_{i\in I}\vec{Y}_{i})$;

21 $W=\bigcup_{i\in{\cal Y}}\hat{V}_{i}$;

22 return $(W,|W|)$;

Algorithm 2 Decr-$\operatorname{\mathsf{SEP}}$

The algorithm starts by computing the set $V_{i}$ and the set of indices $I$
of such sets which are not empty. The main observations on the algorithm are
the following:

  * •

that $V_{i_{N}},\ldots,V_{i_{1}}$ is a $0$-decreasing sequence. At each step
we try to cover only the paths in $\mathbb{P}(u)$ not already covered before.
This is the reason why in line 2 we restrict only to $0$-coordinates in
$Z_{i_{k}}$. The vectors $Y_{i}$ are also defined accordingly. Only the
coordinates in $\mathbb{P}_{l}(u)$ are important since the rest are already
covered by some previous $V_{i}$. That is the reason why in line 2 we define
to be $0$ the $Y$ vector in all the coordinates not in $\mathbb{P}_{l}(u)$.

  * •

Another observation is that at each step $l$ we want to save the minimal set
of nodes $\hat{V}_{i_{N-l}}$ sufficient to cover all the $1$’s in
$\mathbb{P}_{l}[u]$. This is the meaning of the call to HT in line 2.

  * •

finally, when we have done with analizying all the family of the sets
$V_{i}$’s, $\mathbb{P}(u)$ is covered by the union of the $Y$ vectors (this is
by an argument similar to that fof Theorem 6.1). But it is sufficient to have
the minimal subset of this family for covering all $\mathbb{P}(u)$. To this
end we perform a final call to HT on input the set-system, $(I,\bigcup_{i\in
I}\vec{Y}_{i})$ in 2.

###  6.1 $\operatorname{\mathsf{NP}}$-Completeness

Consider the following optimization problem MIN-
NOT-$\operatorname{\mathsf{SEP}}$ ($\operatorname{\mathsf{MNS}}$).

Input: A Boolean $m\times n$ matrix $\mathbb{P}$, an element $u\in[n]$;

Output: $k$ such that $u$ is not $k$-$\operatorname{\mathsf{SEP}}$ and $u$ is
$k^{\prime}$-$\operatorname{\mathsf{SEP}}$ for all $k^{\prime}<k$.

######  Theorem 6.3.

$\operatorname{\mathsf{MNS}}$ is $\operatorname{\mathsf{NP}}$-complete

###### Proof.

To see that $\operatorname{\mathsf{MNS}}$ is in $\operatorname{\mathsf{NP}}$
we can use the reduction in Theorem 6.1 which is in fact proving that
$\operatorname{\mathsf{MNS}}\leq_{p}\operatorname{\mathsf{MHS}}$. Since
$\operatorname{\mathsf{MHS}}\in\operatorname{\mathsf{NP}}$ [1], then
$\operatorname{\mathsf{MNS}}\in\operatorname{\mathsf{NP}}$.

To prove the $\operatorname{\mathsf{NP}}$-hardness of
$\operatorname{\mathsf{MNS}}$ we show the opposite reduction, i.e. that
$\operatorname{\mathsf{MHS}}\leq_{p}\operatorname{\mathsf{MNS}}$. Hence the
result follows by the $\operatorname{\mathsf{NP}}$-hardenss of
$\operatorname{\mathsf{MHS}}$ [1]. Let ${\cal H}=(V,E)$ be an instance of
$\operatorname{\mathsf{MHS}}$. We define an instance of
$\operatorname{\mathsf{MNS}}$ as follows:

  * •

The set of nodes of $\mathbb{P}$ is $V\cup\\{u\\}$.

  * •

The set of paths of $\mathbb{P}$ is $E$;

  * •

$\mathbb{P}(u)=E$;

Since a minimal hitting set $W$ is touching all edges in $E$, that means that
$\mathbb{P}(W)=E=\mathbb{P}(u)$. Hence $u$ is not
$|W|$-$\operatorname{\mathsf{SEP}}$. Moreover since it is minimal, then for
any subset $W^{\prime}$of $[n]$ of size smaller that $|W|$ there is an edge
$e\in E$ not in $W^{\prime}$. That means that
$e\in\mathbb{P}(v)\setminus\mathbb{P}(W)$, that is $u$ is
$k^{\prime}$-$\operatorname{\mathsf{SEP}}$ in $\mathbb{P}$ for any
$k^{\prime}<|W|$.

On the opposite direction, assume that $W\subseteq[n]-\\{u\\}$ is witnessing
that $u$ is not $|W|$-$\operatorname{\mathsf{SEP}}$ but is
$k^{\prime}$-$\operatorname{\mathsf{SEP}}$ for any $k^{\prime}<|W|$, then $W$
is clearly a minimal hitting set in ${\cal H}$.

##  7 Localizing failure nodes in real networks

In this section we study some heuristics to compute as more precisely as
possible the number of $k$-identifiable nodes in set of measurements paths
defined on concrete networks, that is the the set of all paths from between
monitor nodes. According to Section 4 we study upper bounds on the number of
$k$-distinguishable nodes.

To upper bound $|\operatorname{\mathsf{DIS}}_{k}|$ we lower bound the number
of node which are not distinguishable in $\mathbb{P}$. In fact we will
localize specific sets of nodes which we can guarantee to be not
$k$-distinguishable.

Let $\mathbb{P}$ be given and let $u\in V$. We let $\mathbb{W}_{k}(u)$ be a
subset of ${V\setminus\\{u\\}\choose\leq k}$. This should be meant as (a
method to generate) a collection of subset of at most $k$ nodes in $V-\\{u\\}$
as function of the node $u$. An example can be: the subsets of $[n]$ made by
at most $k$ nodes which are at distance at most $d$ from $u$. For any
$v\in\mathbb{W}(u)$, let ${\cal
P}(u,v)\subseteq\mathbb{P}(u)\cap\mathbb{P}(v)$. This should be meant as (a
method to generate) a subset of all paths touching both nodes $u$ and $v$.

######  Definition 7.1.

Let $\mathbb{W}$ and ${\cal P}$ be given for $\mathbb{P}$. We say that
$u\in[n]$ and $W\in\mathbb{W}_{k}(u)$ are $k$-equal modulo ${\cal P}$ in
$\mathbb{P}$ if

  1. 1.

$\exists w,w^{\prime}\in W$ such that $\mathbb{P}(u)\setminus{\cal
P}(u,w)\subseteq\mathbb{P}(w^{\prime})$, and

  2. 2.

$\forall w\in W$, $\mathbb{P}(w)\setminus{\cal P}(u,w)\subseteq\mathbb{P}(u)$.

Let

$\begin{array}[]{l}E_{V,k}[\mathbb{W},{\cal P}]:=\\{u\in V:\mbox{there is a
$W\in\mathbb{W}(u)$}\\\ \quad\quad\quad\quad\mbox{s.t. $u$ and $W$ are
$k$-equal modulo ${\cal P}$\\}}\end{array}$

######  Lemma 7.2.

For all $V\subseteq[n]$, $E_{V,k}[\mathbb{W},{\cal
P}]\subseteq\overline{\operatorname{\mathsf{DIS}}_{k}(\mathbb{P})}$.

###### Proof.

Let $u\in E_{V,k}[\mathbb{W},{\cal P}]$ we have to find a $W\in{V\choose\leq
k}$ with $u\not\in W$ such that $\mathbb{P}(u)=\mathbb{P}(W)$. Fix as $W$ the
one in $\mathbb{W}(u)$ given by the the definition of
$E_{V,k}[\mathbb{W},{\cal P}]$. We first argue that
$\mathbb{P}(u)\subseteq\mathbb{P}(W)$. By Definition 7.1 case (1) we know that
there are $w,w^{\prime}\in W$ such that $\mathbb{P}(u)-{\cal
P}(u,w)\subseteq\mathbb{P}(w^{\prime})$. Consider a $p\in\mathbb{P}(u)$. If
$p\in{\cal P}(u,w)$, then $p\in\mathbb{P}(w)$ and hence $p\in\mathbb{P}(W)$.
If $p\not\in{\cal P}(u,w)$, then $p\in\mathbb{P}(u)\setminus{\cal P}(u,w)$ and
then by Definition 7.1 case (1) $p\in\mathbb{P}(w^{\prime})$ and hence in
$\mathbb{P}(W)$.

Let $q\in\mathbb{P}(W)$, then $q\in\mathbb{P}(w)$ for some $w\in W$. If
$q\in{\cal P}(u,w)$, then $q\in\mathbb{P}(u)$. If $q\not\in{\cal P}(u,w)$,
then $q\in\mathbb{P}(w)\setminus{\cal P}(u,w)$ and then, by Definition 7.1
case (1), $q\in\mathbb{P}(u)$. ∎

By Lemma 7.2 nodes in $E_{[n],k}[\mathbb{W},{\cal P}]$ are not
$k$-distinguishable and, for the anti-monotonicity, are not
$(k+1)$-,$(k+2)$-,$\ldots$, $n$-distinguishable.

We now study how to upper bound the number of $k$-distinguishable nodes in
$\mathbb{P}$ given a specific definition of $\mathbb{W}$ and ${\cal P}$.
Consider the following family of vertices in $[n]$ :

$\left\\{\begin{array}[]{ll}V_{1}=[n]&\\\
V_{k}=[n]-\bigcup_{j<k}E_{V_{j},j}[\mathbb{W},{\cal P}]&\quad
k>1\end{array}\right.$

######  Definition 7.3.

Let $k\leq n$. $\tau_{k}:=|E_{V_{k},k}[\mathbb{W},{\cal P}]|$.

######  Theorem 7.4.

$|\operatorname{\mathsf{DIS}}_{k}(\mathbb{P})|\leq n-\sum_{j=1}^{k}\tau_{j}$.

###### Proof.

We abbreviate $E_{V_{j},j}[\mathbb{W},{\cal P}]$ with $E_{V_{j},j}$. First we
claim that $\left|\bigcup_{j\leq
k}E_{V_{j},j}\right|\leq\sum_{j=1}^{k}\tau_{j}$. This is because for all
$k\leq n$, if $u\in E_{V_{k},k}$, then $u\not\in\bigcup_{j\leq
k-1}E_{V_{j},j}$, by definition of $E_{V_{k},k}$.

Further we claim that

$E_{V_{k},k}\subseteq\overline{\operatorname{\mathsf{DIS}}_{k}(\mathbb{P})}\setminus\bigcup_{j\leq
k-1}E_{V_{j},j}.$

Indeed by Lemma 7.2
$E_{V_{k},k}\subseteq\overline{\operatorname{\mathsf{DIS}}_{k}(\mathbb{P})}$
and again by definition of $E_{V_{k},k}$, if $u\in E_{V_{k},k}$, then
$u\not\in\bigcup_{j\leq k-1}E_{V_{j},j}$ . Therefore:

$\overline{\operatorname{\mathsf{DIS}}_{k}(\mathbb{P})}\geq|E_{V_{k},k}|+\left|\bigcup_{j\leq
k-1}E_{V_{j},j}\right|.$

By definition of $\tau_{k}$ it follows that
$|\overline{\operatorname{\mathsf{DIS}}_{k}(\mathbb{P})}|\geq\tau_{k}+\sum_{j=1}^{k-1}\tau_{j}$,
and hence that $|\operatorname{\mathsf{DIS}}_{k}(\mathbb{P})|\leq
n-\sum_{j=1}^{k}\tau_{j}$.

∎

Notice that the proof of the theorem is constructive and is counting well-
defined nodes in the network, so that nodes can also precisely be localized.

###  7.1 Examples of applications

We show how to use previous results to localize and upper bound the number of
$k$-identifiable nodes on real set of measurements paths. The estimate will
depend on what set $\mathbb{W}(u)$ we consider for any node $u$ and on what
set of paths ${\cal P}$ we are going to test path not distinguishability.
However once we have fixed $\mathbb{W}$ and ${\cal P}$ the algorithm we run is
always the same and reflects the discussion in the previous subsection (See
Algorithm lb-$\operatorname{\mathsf{DIS}}_{k}$).

Data: $\mathbb{P}$

Result: number of $k$-$\operatorname{\mathsf{SEP}}$ nodes

1

2for  _$u\in[n]$_ do

3 Compute $\mathbb{W}(u)$;

4 for  _$w\in\mathbb{W}(u)$_ do

5 Compute ${\cal P}(u,w)$

6 end for

7

8 end for

9$V=[n],i=1,\tau=0$;

10 while  _$i\leq k$_ do

11 Compute $E_{V,i}[\mathbb{W},{\cal P}]$;

12 $\tau=\tau+|E_{V,i}[\mathbb{W},{\cal P}]|$;

13 $V=V-E_{V,i}[\mathbb{W},{\cal P}]$;

14 $i=i+1$;

15 end while

16return $n-\tau$;

Algorithm 3 lb-$\operatorname{\mathsf{DIS}}_{k}$: Counting
$k$-$\operatorname{\mathsf{SEP}}$ nodes

Our method can be applied on a network given as a graph once we have decided
the set of measurements paths. Every possible way of choosing $\mathbb{W},$
and ${\cal P}$ is giving a way to count nodes which are no distinguishable. We
caton therefore thinking of applying the method restricting for each node $u$
the nodes we are checking be not distiguinshable and the effective paths we
are going to to consider. We consider here three potential examples. We will
add details on experiments and we wilkla dd other cases in the final version
of the paper.

####  7.1.1 Neighbours

For any given $u\in[n]$, let $\mathbb{W}_{k}(u)={N(u)\choose\leq k}$, where
$N(u)$ are the neighbours of $u$ and consider for all $v\in N(u)$, the ${\cal
P}^{N}(u)$ of the paths touching both $u$ and its neighbours $v$

####  7.1.2 Nodes at a fixed distance $d$

For any given $u\in[n]$, let $N_{d}(u)=\\{v\in V:d(u,v)=d,d\geq 1\\}$ and
$\mathbb{W}_{k}(u)={N_{d}(u)\choose\leq k}$. For $v\in N_{d}(u)$, the ${\cal
P}^{d}$ of the paths touching both $u$ and $v$.

####  7.1.3 Shortest paths

In this case we consider as set $\mathbb{W}_{k}(u)={V-\\{u\\}\choose\leq k}$,
and for all $v\in V\setminus\\{u\\}$, ${\cal P}$ is the set of shortest paths
from $u$ to $v$.

## Acknowledgements

The authors would like to thank Navid Talebanfard to point them to the paper
[15]. ∎

## References

  * [1] Ausiello, G., D’Atri, A., and Protasi, M. Structure preserving reductions among convex optimization problems.  J. Comput. Syst. Sci. 21, 1 (1980), 136–153.
  * [2] Bartolini, N., He, T., Arrigoni, V., Massini, A., Trombetti, F., and Khamfroush, H. On fundamental bounds on failure identifiability by boolean network tomography.  IEEE/ACM Trans. Netw. 28, 2 (2020), 588–601.
  * [3] Duffield, N. G. Network tomography of binary network performance characteristics.  IEEE Trans. Information Theory 52, 12 (2006), 5373–5388.
  * [4] Eiter, T., and Gottlob, G. Identifying the minimal transversals of a hypergraph and related problems.  SIAM J. Comput. 24, 6 (1995), 1278–1304.
  * [5] Frankl, P., and Füredi, Z. Union-free families of sets and equations over field.  Journal of Number Theory 23 (1986), 210–218.
  * [6] Galesi, N., and Ranjbar, F. Tight bounds for maximal identifiability of failure nodes in boolean network tomography.  In 38th IEEE International Conference on Distributed Computing Systems, ICDCS 2018, Vienna, Austria, July 2-6, 2018 (2018), IEEE Computer Society, pp. 212–222.
  * [7] Galesi, N., and Ranjbar, F. Tight bounds to localize failure nodes on trees, grids and through embeddings under boolean network tomography.  Submitted (2020).
  * [8] Galesi, N., Ranjbar, F., and Zito, M. Vertex-connectivity for node failure identification in boolean network tomography.  In Algorithms for Sensor Systems - 15th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2019, Munich, Germany, September 12-13, 2019, Revised Selected Papers (2019), F. Dressler and C. Scheideler, Eds., vol. 11931 of Lecture Notes in Computer Science, Springer, pp. 79–95.
  * [9] Garey, M. R., and Johnson, D. S. Computers and Intractability, A Guide to the Theory of NP-Completeness, 22 ed.  W. H. Freeman and Company, New York, 2000.
  * [10] Ma, L., He, T., Leung, K. K., Swami, A., and Towsley, D. Inferring link metrics from end-to-end path measurements: Identifiability and monitor placement.  IEEE/ACM Trans. Netw. 22, 4 (2014), 1351–1368.
  * [11] Ma, L., He, T., Swami, A., Towsley, D., and Leung, K. K. On optimal monitor placement for localizing node failures via network tomography.  Perform. Eval. 91 (2015), 16–37.
  * [12] Ma, L., He, T., Swami, A., Towsley, D., and Leung, K. K. Network capability in localizing node failures via end-to-end path measurements.  IEEE/ACM Trans. Netw. 25, 1 (2017), 434–450.
  * [13] Ma, L., He, T., Swami, A., Towsley, D., Leung, K. K., and Lowe, J. Node failure localization via network tomography.  In Proceedings of the 2014 Internet Measurement Conference, IMC 2014, Vancouver, BC, Canada, November 5-7, 2014 (2014), C. Williamson, A. Akella, and N. Taft, Eds., ACM, pp. 195–208.
  * [14] Ren, W., and Dong, W. Robust network tomography: K-identifiability and monitor assignment.  In 35th Annual IEEE International Conference on Computer Communications, INFOCOM 2016, San Francisco, CA, USA, April 10-14, 2016 (2016), IEEE, pp. 1–9.
  * [15] Shangguan, C., and Tamo, I. New turán exponents for two extremal hypergraph problems.  SIAM Journal on Discrete Mathematics (2020).


# An Ensemble Approach to Acronym Extraction using Transformers

Prashant Sharma1, Hadeel Saadany2, Leonardo Zilio2,
Diptesh Kanojia2, Constantin Orăsan2

###### Abstract

Acronyms are abbreviated units of a phrase constructed by using initial
components of the phrase in a text. Automatic extraction of acronyms from a
text can help various Natural Language Processing tasks like machine
translation, information retrieval, and text summarisation. This paper
discusses an ensemble approach for the task of Acronym Extraction, which
utilises two different methods to extract acronyms and their corresponding
long forms. The first method utilises a multilingual contextual language model
and fine-tunes the model to perform the task. The second method relies on a
convolutional neural network architecture to extract acronyms and append them
to the output of the previous method. We also augment the official training
dataset with additional training samples extracted from several open-access
journals to help improve the task performance. Our dataset analysis also
highlights the noise within the current task dataset. Our approach achieves
the following macro-F1 scores on test data released with the task: Danish
(0.74), English [Legal] (0.72), English [Scientific] (0.73), French (0.63),
Persian (0.57), Spanish (0.65), Vietnamese (0.65). We release our code and
models publicly111https://github.com/dipteshkanojia/PR-AAAI22-SDU-ST1-AE.

##  1 Introduction

Acronyms are commonly used to shorten known units of text in various domains
such as scientific (Pustejovsky et al. 2001), medical (Dannélls 2006),
business (Ménard and Ratté 2011) and legal (Tsimpouris, Sgarbas, and
Panagiotopoulou 2015). Humans can usually identify acronyms in a text without
too much difficulty by relying on various surface clues. Without knowing the
meaning of acronyms, it is not possible to understand a text properly.
Moreover, in absence of the long forms of an acronym translators and
interpreters may have difficulties translate a text reliably.

Automatic identification of acronyms and their corresponding long forms is a
relevant issue in the domain of Natural Language Processing (NLP) as it can
help tasks such as information extraction and retrieval (Sánchez and Isern
2011; Ballesteros and Croft 1996), machine translation (Kirchhoff and Turner
2016) and also machine interpreting (Braun 2019). Acronyms represent relevant
parts of the text and can confuse translation models. Thus, the task of
automatically identifying and extracting acronyms from a text can be
challenging for a machine.

Figure 1: Examples of Long Forms and their Acronyms

The shared task-1 for acronym extraction (AE) under the Scientific Document
Understanding (SDU) workshop222https://sites.google.com/view/sdu-aaai22/home
allows researchers to tackle this challenge and propose novel ways to solve
it. The task requires participants to submit systems that can automatically
identify acronyms and their long forms from a given piece of text. Figure 1
shows two examples of acronyms and their long forms from the English dataset
(Scientific domain) and English dataset (Legal domain). These examples are
from the task dataset provided as-is to the participants. The acronyms in
parentheses are highlighted in yellow, and their respective long forms are
underlined. Automatic acronym extraction can be particularly challenging and
based on our analysis of the training data for this task (Veyseh et al.
2022b), we observe:

  * •

Acronyms are known to be present in uppercase letters in the text, but there
can be instances where they can contain lowercase letters (e.g., CATiB, SEqui,
OEqul, SRals ing)

  * •

There can be instances where the long forms of the acronyms are not present in
the text (e.g., We originally developed BBLT for ourselves..)

  * •

There can be different long forms for the same acronym (e.g., CT has been used
as an acronym for both “contract” and “certain”)

  * •

Acronyms can have special characters present in them (e.g., Communist Party of
the Philippines-New Peoples Army-National Democratic Front (CPPNPA-NDF) )

  * •

Multiple acronymised letters are part of the same word (e.g., subsequence
kernel (SSK), maximum entropy (MaxEnt) )

Apart from the challenges discussed here, we also noted noise in the dataset,
which we discuss in the dataset analysis subsection later (Section 3).
However, for the challenges discussed here, rule-based approaches fail, in
particular, as they try to generalise over a pattern or a regular expression
to detect acronyms from the text. There are multiple outliers that cannot be
detected with the help of such approaches, as can be seen in the results of
the rule-based approach implemented by the organisers of this task as a
baseline. We discuss this approach in brief in Section 4. For this reason, we
focused our efforts to develop a data-driven approach (more precisely a deep
learning-based approach) to extract acronyms from the multilingual dataset
prepared by the organisers of the shared task.

In this paper, we describe our efforts to create a system that can extract
acronyms and their long forms from a multilingual dataset. We model the task
of acronym extraction as a sequence labelling problem and perform token
classification considering each dataset sample as a sequence. After
experimenting with several architectures, we decided to use an Ensemble
approach which relies on two methods. The first method utilises the
Transformer-architecture-based multilingual language model, XLM-R (Conneau et
al. 2019), to perform fine-tuning and extract acronyms. We also perform the
acronym extraction task with the help of a Convolutional Neural Network (CNN),
which employs word embeddings from a different source, as described later in
our work. The resultant outputs from both these methods are then combined to
create an ensemble output which we submit to obtain our scores for the task.

##  2 Related Work

The task of extracting acronyms from text has been performed in different
domains for English, with most of the approaches being rule-based approaches
(Taghva and Gilbreth 1999; Yeates 1999; Park and Byrd 2001; Larkey et al.
2000). Schwartz and Hearst (2002) implemented an algorithm for identifying
acronyms by using parenthetical expressions as a marker of a short form. Their
work is based on a previous work by Pustejovsky et al. (2001) which also
extracts acronyms using a similar method. Dannélls (2006) performs the
extraction of acronym-definition pairs from Swedish medical texts by primarily
using a rule-based approach to extract acronyms and then a memory-based
supervised machine learning approach to compare and evaluate the results. A
rule-based approach was also implemented by Okazaki and Ananiadou (2006) for
term recognition, and it discusses the extraction of acronyms and their long
forms. This system mines acronyms based on parenthetical expressions as a
marker of a short form as previous methods had described. However, for mining
long forms, they created a candidate list based on frequent co-occurrences of
word sequences. Movshovitz-Attias and Cohen (2012) investigate the use of
Hidden Markov Model (HMM) for the extraction of acronyms from text. Ehrmann et
al. (2013) show how acronym recognition patterns, initially developed for
medical terms, can be adapted to the more general news domain. Their efforts
led to automatically merging the numerous long-form variants referring to the
same short form while maintaining non-related long forms separately. Their
work is based on the algorithm developed by Schwartz and Hearst (2002), but
they perform the task of acronym extraction for 22 languages.

Machine learning-based approaches for the extraction of acronyms have been
utilised in many previous studies (Nadeau and Turney 2005; Kuo et al. 2009).
With the advancement of research in NLP, various methods to extract word
embeddings for text have been proposed, the most recent of them being
contextual language models. To detect acronyms without local definitions,
Rogers, Rae, and Demner-Fushman (2021) applied two deep learning approaches:
bi-directional LSTM with CRF and Transformer models. Li et al. (2021) utilise
transformer-based architecture for modelling the task of acronym
identification as a sentence-level sequence labelling problem. Zhu et al.
(2021) incorporate the FGM adversarial training strategy for fine-tuning BERT
for robust and generalised acronym identification. This was the winning system
for the Acronym Extraction Shared Task held at SDU workshop in 2021.

In this paper, we employ the previously proposed approach of fine-tuning a
language model for the task of acronym extraction (Kubal and Nagvenkar 2021).
However, we extract additional data from PLOS journals and perform additional
data analysis. We describe data augmentation and pre-processing techniques in
the upcoming sections.

##  3 Dataset

The dataset provided by the task organisers consists of independent sentences
in Danish, English, French, Persian, Spanish, and Vietnamese languages in the
JSON format (Veyseh et al. 2022a). The English dataset is further divided into
two different domains: legal and scientific. The dataset statistics can be
seen in Table 1. However, each text sample can contain multiple lines of the
text, thus containing up to 1050 words in each sample as observed from the
training dataset.

| Training | Development | Test
---|---|---|---
Danish | 3082 | 385 | 386
English (Legal) | 3564 | 445 | 446
English (Scientific) | 3980 | 497 | 498
French | 7783 | 973 | 973
Persian | 1336 | 167 | 168
Spanish | 5928 | 741 | 741
Vietnamese | 1274 | 159 | 160

Table 1: Dataset Statistics, in terms of number of dataset samples, for the
Acronym Extraction task as provided by the task organizers. Figure 2: System
Architecture for Our Ensemble Approach

### Dataset Preprocessing

The fact that we model the task as a sequence labelling problem required us to
convert the text provided into a BIO (short for Beginning, Inside, Outside)
format. BIO is a common format for tagging a token in a chunking or a named
entity recognition task in computational linguistics (Ramshaw and Marcus
1999). We convert each JSON task dataset into the BIO format with the help of
a custom script written in Python. The custom tags we use to convert each
token in the sequence resemble Named Entity tags and result in the following
list of tags: [O (Outside), B-AN (Begin Acronym), I-AN (Inside Acronym), B-LF
(Begin Long Form), I-LF (Inside Long Form)].

### Dataset Analysis

We analysed the dataset provided for the task and observed the following
issues:

  * •

There are instances with missing or incomplete annotation (e.g. the acronym
SDI has associated with the long-form “selective dissemination” instead of
“selective dissemination of information”, which is present in the instance).

  * •

Segments with wrong annotation (e.g. “US$ 3” was annotated as an acronym of
“USh 3,000”, when these are actually conversions between two currencies).

  * •

Segments with over-annotation (e.g. the acronym “(GHS)” had the brackets
included in the annotation).

In an analysis performed on the first 100 instances of the English scientific
training dataset, we found 28 instances with such issues. These issues were
also found in 21 instances among the first 100 instances of the English legal
training dataset. The presence of such a high number of errors in the dataset
poses some serious challenges to any data-driven method.

### Data Augmentation

To increase the amount of training data, a separate training dataset was
created by using information extracted from the PLOS333https://plos.org/.
open-access journal publications. The XML versions of these publications are
freely distributed along with the PMC Open Access Subset
444https://www.ncbi.nlm.nih.gov/pmc/tools/openftlist/. and amount to 305,445
texts.

The XML files in the PLOS corpus have a section for abbreviations, where all
abbreviations used in a paper are made explicit along with their long forms.
This information was used to extract sentences from research articles within
the PLOS corpus. For the augmented dataset, only sentences containing at least
one abbreviation with a related long-form were included (other abbreviations
with or without long forms could be present as well). This augmented training
dataset contained a total of approx. 93k samples for English (Scientific
domain).

##  4 Our Approach

The baseline approach provided the task organisers uses a single rule, i.e.,
if the word inside a parenthesis contains more than 60% uppercase letters, it
is to be identified as an acronym. Moreover, the number of uppercase letters
in this acronym form a sliding window for words before/after the acronym. If
each uppercase letter matches the first characters of words in the sliding
window, the words constitute the long-form phrase. This approach clearly fails
to address the challenges discussed in Section 1 of the paper. The resulting
macro-F1 scores for the baseline approach on the development data are: English
(Legal) - 0.1258, English (Scientific) - 0.1084, Danish - 0.0950, French -
0.0806, Spanish - 0.0831, Persian - 0.4437, Vietnamese - 0.3538. Hence, we
needed to look for alternative methods for identifying acronyms and their long
forms. After considering a number of options, we decided to experiment with a
deep-learning-based ensemble approach.

Our Ensemble Approach: We concatenate all the multilingual task data into a
single training dataset. This was then concatenated with the PLOS data
described above to increase the train data size to approx. 113k dataset
samples. This data is used to fine-tune the multilingual language model
described below to perform the acronym extraction (AE) task. We obtain the
test output from two different methods described below and concatenate them.
The fine-tuning method described below is able to label both acronyms and long
forms. The spaCy blank model-based method described below is only able to
obtain acronyms for the task but helps achieve improved F1 scores for the
task. The architecture for our approach is shown in Figure 2.

### Fine-tuning with XLM-RoBERTa

XLM-RoBERTa (XLM-R) (Conneau et al. 2019) is a multilingual contextualised
Language Model (LM) pre-trained on filtered CommonCrawl data from 100+
languages. Each language dataset from this task is included in this
model555https://github.com/facebookresearch/XLM.

Our approach utilises this transformer architecture-based pre-trained LM and
fine-tunes it for the downstream sequence labelling task. The LM used for our
approach is XLM-Rbase, and has approximately 270M parameters with 12-layers,
768 hidden states, 3072 feed-forward hidden states, 8 heads; and is pre-
trained on CommonCrawl data in over 100 languages. The fine-tuning process
adds a hidden linear layer on top of the pre-trained LM and projects the
output to a softmax layer for token classification. We perform further
hyperparameter tuning as described below.

We observed that during the inference phase, the output token length was
truncated to 128 tokens as it was the default ‘maximum sequence length’
parameter. To preserve the entire token length, the two parameters, namely,
‘sliding window’ and ‘maximum sequence length’ were being used with the
original model. The sliding window prevents the truncation of sentences by
splitting the input sequence into multiple windows if it exceeds the default
maximum sequence value. The sliding window problem represents the broken
contextual information while predicting token class, and hence it was not
used. We carried out multiple experiments with the ‘maximum sequence length’
parameter and observed that the model performed the best when it was limited
to 512. The other values for maximum sequence length we experimented with were
128, 256, 350, 450, and 512. The language model was fine-tuned by using the
fairSeq (Ott et al. 2019) library. We used an NVIDIA Quadro RTX 5000 GPU with
16 GB of memory for carrying out these experiments. This approach utilizes the
training data to learn how to classify each token as B-AN, I-AN, B-LF and
I-LF, in the text. With the help of further post-processing using a custom
script in Python, we were able to convert the predictions in the JSON format
as required for the evaluation phase of the task.

### spaCy Blank Model

The other model that we used for AE was a spaCy v3.2666https://spacy.io/models
blank NER model. The spaCy v3.2 model is based on predicting context-sensitive
vectors for each word in the input by a token-to-vector model. The embeddings
in this model are obtained from the Bloom embeddings where each sub-word is
transferred into a string of fixed symbols (e.g. 0-9 integer transferred to
letter d, capital letter to W and lower case letter to w) (Serrà and
Karatzoglou 2017). This strategy has proven to be effective in handling out-
of-vocabulary (OOV) tokens; instead of dumping all OOVs in one bucket, each
OOV is given a unique representation. The method offers a variety of neural
architectures for building a blank NER model to predict task-tailored
entities. We opted for the trigram-CNN architecture learning via a transition-
based approach which takes a window of the embeddings on either side of each
word in the sentence and concatenates them in a multi-layered perceptron
followed by an attention layer (Lample et al. 2016). A Maxout Unit (Goodfellow
et al. 2013) is used as an activation function that calculates the ‘maximum’
of the inputs. These architecture parameters have performed well for NER
tasks777https://v2.spacy.io/usage/facts-figures.

For training, we use the English (Scientific) and English (Legal) training
sets consisting of 7523 instances and evaluate our method on the English
(Scientific) and English (Legal) development sets. We use a limited training
dataset as these experiments are performed with CPU cores. Before training, we
pre-processed the data to conform with the ‘.spacy’ format, where each
positive instance was assigned the NER label acronym along with its specific
indices. For the spaCy pipeline parameters, we chose the spaCy en_core_web_sm
model, which is the small model trained on written English language web text
(blogs, news, comments) including vocabulary, vectors, syntax and entities. We
trained this model on a CPU with 100 iterations and with a batch size of 1000.

We used this model as a zero-shot model for the AE task with the test sets of
the other four languages during the final stage of the shared task. A note on
the reason for choosing this blank spaCy model for AE in this task is that it
has a CPU-optimised pipeline, and it is much cheaper to run than pre-trained
models. Due to its competitive results to the more expensive pre-trained
models, we plan to explore training a spaCy model with more data for future AE
task.

##  5 Results and Discussion

| F1 | P | R
---|---|---|---
Danish | 0.74 | 0.78 | 0.70
English (Legal) | 0.72 | 0.75 | 0.69
English (Scientific) | 0.73 | 0.77 | 0.69
French | 0.63 | 0.68 | 0.59
Persian | 0.57 | 0.64 | 0.51
Spanish | 0.65 | 0.65 | 0.65
Vietnamese | 0.65 | 0.64 | 0.66

Table 2: Results obtained using our ensemble approach over the test data as
provided for the task where P is Precision, R is Recall, and F1 is the
Macro-F1 score as used for the task.

Using the fine-tuned XLM-R model, we obtained acronyms and long forms for the
test data provided for this task. We then concatenated this output with the
output from the spaCy blank model. The results obtained for the final test set
output are present in Table 2. Our approach was outranked by several other
systems submitted for the task, but we show a significantly improved set of
results over the baseline method proposed for the task. Our results also show
how the AE task can be modelled as a sequence labelling problem, thus
utilising pre-existing architecture for the NER problem in NLP. The
performance of our approach in comparison to other systems submitted at the
task was comparatively lower, which can be attributed to the fact that we use
a single multilingual training model for all the languages. We also use a
rather simple fine-tuning based approach and do not add a more sophisticated
neural networks-based architecture.

The output obtained using the fine-tuning method described above outperforms
the rule-based baseline approach by a significant margin. This method helps
our approach gain significant percentage points for both acronyms and long
forms as compared to the baseline approach. However, we observed that this
method did not recognise many acronyms, resulting in low recall values. We
also observed that due to the noise present in the data, this method tagged
special characters like ‘)’ as a part of the acronym. We also observed that
the fine-tuning process tagged a lot of stopwords as long forms even when they
were not a part of any long-form sequence (e.g., for, the, of). We post-
process the output of this model to rectify such errors.

The performance of the spaCy method, however, is significantly better at
extracting acronyms as it uses a CNN architecture and performs well for the
English language. However, it needs to be pointed out that, despite the fact
that the dataset was multilingual in nature, most instances of long forms and
acronyms were present in the English language. The results of the spaCy model
for the extraction of only acronyms against the development set were: English
Scientific - Precision: 0.8847, Recall: 0.7990, F1: 0.8397; and English Legal
- Precision: 0.9168, Recall: 0.7354 and F1: 0.8161. As noted, this method only
extracts acronyms and does not work well with long forms.

In most of the cases, we observed that our approach obtains higher precision
than recall. This observation is expected as the fine-tuning process expects a
lot more ‘O’ tokens compared to the AN or the LF classes. Our approach, which
classifies each token, confuses a lot of ‘AN’s as ‘O’s. In fact, when the
output of the spaCy model was deconcatenated, we observed that the XLM-R based
method for the Persian language had only achieved an F1 of 0.27 compared to
the overall F1 of 0.57. The task performance of our approach on the Spanish
test data, however, is an exception as it shows a steady Precision, Recall,
and F1 scores of 0.65.

##  6 Conclusions and Future Work

In this paper, we propose a deep-learning-based approach to extract acronyms
and long forms from the data provided for the task. We discuss the problem of
acronym extraction and show how challenging it is to accomplish this task
automatically. The dataset provided for the task is multilingual in nature,
and our approach attempts to build a single model which can handle all the
languages. However, our dataset analysis shows that the data provided for the
task should indeed be manually validated first to remove the noise. We also
augmented this dataset with more samples from the PLOS open-access journal to
improve the dataset size, but it is unclear how much this helped improve the
performance. We modelled this AE task as a sequence labelling problem and used
an ensemble approach which utilises two different methods: (1) based on fine-
tuning the XLM-R model to extract ANs and LFs, and (2) based on using a CNN
architecture provided by spaCy blank modelling method. Our results
significantly outperform the baseline results and show that this approach does
work for the AE task. We release the code and the models used for this
task888https://github.com/dipteshkanojia/PR-AAAI22-SDU-ST1-AE.

For the future, we aim to perform this multilingual AE task by separating the
models individually for each language. We plan to use the data from PLOS to
augment each training dataset and perform further experiments. We also plan to
collect more data for each language for the task and augment it with the
training data for each of the models. With this augmented resource, we plan to
perform an extensive analysis of the acronym extraction task and present our
findings in the near future. Our eventual goal is to perform exhaustive
experimentation with various datasets/methods and empirically find the best
performing approach for this task.

## References

  * Ballesteros and Croft (1996) Ballesteros, L.; and Croft, B. 1996.  Dictionary methods for cross-lingual information retrieval.  In _International Conference on Database and Expert Systems Applications_ , 791–801. Springer.
  * Braun (2019) Braun, S. 2019.  Technology and interpreting.  In _The Routledge Handbook of translation and technology_ , 271–288. Routledge.
  * Conneau et al. (2019) Conneau, A.; Khandelwal, K.; Goyal, N.; Chaudhary, V.; Wenzek, G.; Guzmán, F.; Grave, E.; Ott, M.; Zettlemoyer, L.; and Stoyanov, V. 2019.  Unsupervised cross-lingual representation learning at scale.  _arXiv preprint arXiv:1911.02116_.
  * Dannélls (2006) Dannélls, D. 2006.  Automatic Acronym Recognition.  In _Demonstrations_ , 167–170.
  * Ehrmann et al. (2013) Ehrmann, M.; Della Rocca, L.; Steinberger, R.; and Tanev, H. 2013.  Acronym recognition and processing in 22 languages.  _arXiv preprint arXiv:1309.6185_.
  * Goodfellow et al. (2013) Goodfellow, I.; Warde-Farley, D.; Mirza, M.; Courville, A.; and Bengio, Y. 2013\.  Maxout networks.  In _International conference on machine learning_ , 1319–1327. PMLR.
  * Kirchhoff and Turner (2016) Kirchhoff, K.; and Turner, A. M. 2016.  Unsupervised resolution of acronyms and abbreviations in nursing notes using document-level context models.  In _Proceedings of the Seventh International Workshop on Health Text Mining and Information Analysis_ , 52–60.
  * Kubal and Nagvenkar (2021) Kubal, D. R.; and Nagvenkar, A. 2021.  Effective Ensembling of Transformer based Language Models for Acronyms Identification.  In _SDU@ AAAI_.
  * Kuo et al. (2009) Kuo, C.-J.; Ling, M. H.; Lin, K.-T.; and Hsu, C.-N. 2009.  BIOADI: a machine learning approach to identifying abbreviations and definitions in biological literature.  In _BMC bioinformatics_ , volume 10, 1–10. BioMed Central.
  * Lample et al. (2016) Lample, G.; Ballesteros, M.; Subramanian, S.; Kawakami, K.; and Dyer, C. 2016.  Neural architectures for named entity recognition.  _arXiv preprint arXiv:1603.01360_.
  * Larkey et al. (2000) Larkey, L. S.; Ogilvie, P.; Price, M. A.; and Tamilio, B. 2000.  Acrophile: an automated acronym extractor and server.  In _Proceedings of the fifth ACM conference on Digital libraries_ , 205–214.
  * Li et al. (2021) Li, F.; Mai, Z.; Zou, W.; Ou, W.; Qin, X.; Lin, Y.; and Zhang, W. 2021.  Systems at SDU-2021 Task 1: Transformers for Sentence Level Sequence Label.  In _SDU@ AAAI_.
  * Ménard and Ratté (2011) Ménard, P. A.; and Ratté, S. 2011.  Classifier-based acronym extraction for business documents.  _Knowledge and information systems_ , 29(2): 305–334.
  * Movshovitz-Attias and Cohen (2012) Movshovitz-Attias, D.; and Cohen, W. 2012.  Alignment-HMM-based extraction of abbreviations from biomedical text.  In _BioNLP: Proceedings of the 2012 Workshop on Biomedical Natural Language Processing_ , 47–55.
  * Nadeau and Turney (2005) Nadeau, D.; and Turney, P. D. 2005.  A supervised learning approach to acronym identification.  In _Conference of the Canadian Society for Computational Studies of Intelligence_ , 319–329. Springer.
  * Okazaki and Ananiadou (2006) Okazaki, N.; and Ananiadou, S. 2006.  A Term Recognition Approach to Acronym Recognition.  In _Proceedings of the COLING/ACL 2006 Main Conference Poster Sessions_ , 643–650. Sydney, Australia: Association for Computational Linguistics.
  * Ott et al. (2019) Ott, M.; Edunov, S.; Baevski, A.; Fan, A.; Gross, S.; Ng, N.; Grangier, D.; and Auli, M. 2019.  fairseq: A Fast, Extensible Toolkit for Sequence Modeling.  In _Proceedings of NAACL-HLT 2019: Demonstrations_.
  * Park and Byrd (2001) Park, Y.; and Byrd, R. J. 2001.  Hybrid text mining for finding abbreviations and their definitions.  In _Proceedings of the 2001 conference on empirical methods in natural language processing_.
  * Pustejovsky et al. (2001) Pustejovsky, J.; Castano, J.; Cochran, B.; Kotecki, M.; and Morrell, M. 2001.  Automatic extraction of acronym-meaning pairs from MEDLINE databases.  In _MEDINFO 2001_ , 371–375. IOS Press.
  * Ramshaw and Marcus (1999) Ramshaw, L. A.; and Marcus, M. P. 1999.  _Text Chunking Using Transformation-Based Learning_ , 157–176.  Dordrecht: Springer Netherlands.  ISBN 978-94-017-2390-9.
  * Rogers, Rae, and Demner-Fushman (2021) Rogers, W.; Rae, A. R.; and Demner-Fushman, D. 2021.  AI-NLM exploration of the Acronym Identification Shared Task at SDU@ AAAI-21.  In _SDU@ AAAI_.
  * Sánchez and Isern (2011) Sánchez, D.; and Isern, D. 2011.  Automatic extraction of acronym definitions from the Web.  _Applied Intelligence_ , 34(2): 311–327.
  * Schwartz and Hearst (2002) Schwartz, A. S.; and Hearst, M. A. 2002.  A simple algorithm for identifying abbreviation definitions in biomedical text.  In _Biocomputing 2003_ , 451–462. World Scientific.
  * Serrà and Karatzoglou (2017) Serrà, J.; and Karatzoglou, A. 2017.  Getting deep recommenders fit: Bloom embeddings for sparse binary input/output networks.  In _Proceedings of the Eleventh ACM Conference on Recommender Systems_ , 279–287.
  * Taghva and Gilbreth (1999) Taghva, K.; and Gilbreth, J. 1999.  Recognizing acronyms and their definitions.  _International Journal on Document Analysis and Recognition_ , 1(4): 191–198.
  * Tsimpouris, Sgarbas, and Panagiotopoulou (2015) Tsimpouris, C.; Sgarbas, K.; and Panagiotopoulou, S. 2015.  Acronym identification in Greek legal texts.  _Digital Scholarship in the Humanities_ , 30(3): 440–451.
  * Veyseh et al. (2022a) Veyseh, A. P. B.; Meister, N.; Yoon, S.; Jain, R.; Dernoncourt, F.; and Nguyen, T. H. 2022a.  MACRONYM: A Large-Scale Dataset for Multilingual and Multi-Domain Acronym Extraction.  In _arXiv_.
  * Veyseh et al. (2022b) Veyseh, A. P. B.; Meister, N.; Yoon, S.; Jain, R.; Dernoncourt, F.; and Nguyen, T. H. 2022b.  Multilingual Acronym Extraction and Disambiguation Shared Tasks at SDU 2022.  In _Proceedings of SDU@AAAI-22_.
  * Yeates (1999) Yeates, S. A. 1999.  Automatic Extraction of Acronyms from Text.  In _New Zealand Computer Science Research Students’ Conference_ , 117–124. Citeseer.
  * Zhu et al. (2021) Zhu, D.; Lin, W.; Zhang, Y.; Zhong, Q.; Zeng, G.; Wu, W.; and Tang, J. 2021.  AT-BERT: Adversarial Training BERT for Acronym Identification Winning Solution for SDU@ AAAI-21.  _arXiv preprint arXiv:2101.03700_.