# Partitions of vertices and facets in trees and stacked simplicial complexes

Gunnar Fløystad  Matematisk Institutt
Postboks 7803
5020 Bergen<EMAIL_ADDRESS>https://folk.uib.no/nmagf/Home2013.html

###### Abstract.

For stacked simplicial complexes, (where trees are a special subclass), we
give an explicit bijection between partitions of facets (for trees: edges),
and partitions of vertices into independent sets. More generally we give
bijections between facet partitions whose parts have minimal distance $\geq s$
and vertex partitions whose parts have minimal distance $\geq s+1$.

A consequence is results on partitions of natural numbers, where the parts
have minimal bounds on spacing.

###### Key words and phrases:

tree, partition, independent, stacked simplicial complex, natural numbers,
Stirling numbers, bijection

###### 1991 Mathematics Subject Classification:

Primary: 05C05 05C69, 05E45; Secondary: 05C70

##  1\. Introduction

If $G=(V,E)$ is a graph with vertices $V$ and edges $E$, a set of vertices
$A\subseteq V$ is independent if no two vertices in $A$ are on the same edge.
When $G=T$ a tree, this notion may be refined a bit. For every pair $v,w$ of
vertices there is a unique path from $v$ to $w$ and so a well-defined
distance. Two vertices are independent if their distance if $\geq 2$. Also for
pairs of edges there is a unique path between them and so a well-defined
distance.

Consider partitions of vertices in a tree

$V=V_{0}\sqcup V_{1}\sqcup\cdots\sqcup V_{r}$

into $r+1$ non-empty parts. We can also partition edges

$E=E_{1}\sqcup E_{2}\sqcup\cdots\sqcup E_{s}$

into $s$ non-empty parts.

0. We give a bijection between:

  * i)

Partitions of vertices into $r+1$ non-empty parts, each part consisting of
independent vertices, and

  * ii)

partitions of edges into $r$ non-empty parts (and no further requirements).

######  Example 1.1.

Any tree has a unique partition of the vertices into two independent sets (two
colors modulo $S_{2}$). This corresponds to the partition of the edges into
one part (one color).

Moreover the above generalizes in two directions.

1. Define a set of vertices $A\subseteq V$ to be $s$-scattered if the distance between any two vertices is $\geq s$. Similarly we have the notion of a set of edges $B\subseteq E$ being $s$-scattered. We show, Theorem 3.6 for $r,s\geq 1$, there is a bijection between:

  * i)

Partitions of vertices into $r+1$ non-empty parts, each part being
$s+1$-scattered, and

  * ii)

Partitions of edges into $r$ non-empty parts, each part being $s$-scattered

2. Stacked simplicial complexes is a generalization of trees to higher dimensions. Their main feature for us is that between any two facets (maximal faces) there is a unique path, and so a well-defined distance. Similarly between any pair of vertices there is a unique path of facets, and so a well-defined distance. We show:

Theorem 3.6., Let $X$ be a stacked simplicial complex of dimension $d$ and
$r,s\geq 1$. There is a bijection between:

  * i)

Partitions of vertices of $X$ into $r+d$ non-empty parts, each part being
$s+1$-scattered,

  * ii)

Partitions of facets of $X$ into $r$ non-empty parts, each part being
$s$-scattered

The results on trees appear quite non-trivial even for the simplest of graphs,
the line graph. By considering larger and large line graphs, we get in the
limit results for partitions of natural numbers.

Theorem 4.1 There is a bijection between partitions of ${\mathbb{N}}$ into $r$
non-empty sets, each set being $s$-scattered, and partitions of ${\mathbb{N}}$
into $r+1$ non-empty sets, each set being $s+1$-scattered.

As a consequence we get for instance:

Corollary 4.4 There is a bijection between partitions of ${\mathbb{N}}$ into
two parts $A_{0}\sqcup A_{1}$ (each part automatically $1$-scattered) and
partitions of ${\mathbb{N}}$ into $d+1$ classes $B_{0}\sqcup\cdots\sqcup
B_{d}$, each part being $d$-scattered.

Let us explain in more detail the bijection, first for trees, and secondly in
an example of triangulations of polygons. Such triangulations are stacked
simplicial complexes of dimension two.

Given a tree and a partition of the vertices $V$, make a partition of the
edges $E$ as follows: If $v$ and $w$ are vertices consider the unique path in
$T$ linking $v$ and $w$. Let $f$, respectively $g$, be the edge incident to
$v$, respectively $w$, on this path. If (i) $v$ and $w$ are in the same part
$V_{i}$ of $V$ and (ii) no other vertex on this path is in the part $V_{i}$,
then put $f$ and $g$ into the same part of $E$, and write $f\sim_{E}g$. The
partition of edges is the equivalence relation generated by $\sim_{E}$.

Conversely given a partition of the edges $E$, make a partition of the
vertices $V$ as follows: Let $v$ and $w$ be distinct vertices, and consider
again the path from $v$ to $w$. If (i) the edges $f$ and $g$ are distinct,
(ii) $f$ and $g$ are in the same part $E_{j}$, and (iii) no other edge on this
path is in the part $E_{j}$, then put $v$ and $w$ in the same part of $V$, and
write $v\sim_{V}w$. The partition of vertices is the equivalence relation
generated by $\sim_{V}$.

######  Example 1.2.

In Figure 1 we partition the edges into red and black color classes. The
vertices are then partitioned into three sets, each consisting of independent
vertices. The partition of the vertex set of the first tree is

$\\{1,3,5\\}\cup\\{2,6\\}\cup\\{4\\},$

and that of the second tree is

$\\{1,3,5,8,10\\}\cup\\{2,4,7\\}\cup\\{6,9\\}.$

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

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$

Figure 1.

######  Example 1.3.

Consider now a triangulation of the heptagon, which is a stacked simplicial
complex. We partition the facets into two parts: three blue and two red,
Figure 2. This corresponds, in a similar way as for trees, to a partition of
the vertices, now into four parts of independent vertices: two yellow vertices
$3,7$, three red $1,4,6$, one blue $2$, and one green $5$. In fact the facet
classes are here $2$-scattered and so each of the vertex classes will even be
$3$-scattered.

Note that the colors have no real significance here, they are just added for
pedagogical and visualisation purposes. In particular there is no connection
between colors of facets and colors of vertices.

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

Our results here came out of work in [6] by M.Orlich and the author on
triangulations of polygons and more generally on stacked simplicial complexes.

Results related to the present article are to be found in enumerative
combinatorics. A first result in this direction is W.Yang [13] considering
trees on $n+1$ vertices, showing that partitions into independent sets of
vertices are counted by Bell numbers $B_{n}$. He also considers generalized
$d$-trees and show that partitions into independent sets of vertices of such a
tree with $n+d$ vertices is counted by the Bell number $B_{n}$. A generalized
$d$-tree is the same as the edges (or $1$-skeleton) of a stacked simplicial
complex of dimension $d$.

B.Duncan and R.Peele [4] consider enumerative aspects of partitions of
vertices of graphs into independent sets. For trees they show that partitions
of a tree with $n+1$ vertices into $k+1$ parts are in bijection with
partitions of an $n$-set into $k$ parts. They give, mostly illustrated by a
large example, a bijection which is essentially the same as we give. But we
gain here the conceptual advantage of expressing this in terms of edges of the
tree. Their statement involves choosing an arbitrary vertex $r$, a root, and
then relating independent vertex partitions of $V$ to partitions of
$V\backslash\\{r\\}$. [8] and [10] considers enumerative aspects of graphical
Bell numbers further, and the latter also generalized $d$-trees.

W.Chen, E.Deng, and R.Du [2] consider ordered sets and use the terminology
$m$-regular for $m$-scattered. They show that partitions of an ordered
$n+1$-set into $k+1$ parts which are $m+1$-regular are in bijection with
partitions of an $n$-set into $k$ parts which are $m$-regular. This
corresponds to the case of line graphs, and for this case the bijection they
give is essentially the same as ours. They also show that we have bijections
in this case when considering non-crossing partitions. Related enumerative
results are found in [12] and [3]. The book [11] is a comprehensive account of
partitions of ordered sets.

######  Remark 1.4.

The results of this paper dropped out of investigations in [6], concerning
Stanley-Reisner rings of stacked simplicial complexes. Among such simplicial
complexes there are certain separated models, and from these models we obtain
every stacked simplicial complex by partitioning the vertices into independent
classes and then collapsing each class into a single vertex. This is done such
that the essential algebraic and homological properties of the associated
rings are preserved.

The algebra involved here should generalize to much larger classes of
simplicial complexes. Polarizing artinian monomial ideals gives separated
models, and in [1] we describe all such for polarizations of any power of a
graded maximal ideal in a polynomial ring. The case of stacked simplicial
complex is the case of the second power. Polarizing artin monomial ideals in
general still goes much further than [1]. The results presented in this
article therefore likely have vast generalizations, see Subsection 8.2 of [7].
This should involve partitions of vertices, but it is a challenge what other
ingredients and statements should be involved.

Let us also mention that the main result of [7] is a fundamental theorem of
combinatorial geometry of monomial ideals. Namely that any polarization of an
artin monomial ideal, via the Stanley-Reisner correspondence, is a simplicial
complex whose topological realization is a ball.

Acknowledgements. I thank M.Orlich for making the Figure 1.

##  2\. Stacked simplicial complexes

We recall the notion of stacked simplicial complex. Its main feature from our
perspective, is that it generalizes the property of trees, that for every two
faces, there is a unique path between them.

###  2.1. Paths

Let $V$ be a finite set. A simplicial complex $X$ on $V$ is a family of
subsets of $V$ (called faces) closed under taking smaller subsets. So for a
face $F\in X$ and $G\subseteq F$, then also $G\in X$, a face. A facet of $X$
is an element in $X$, maximal for the inclusion relation. Given a subset
$R\subseteq V$, the restricted simplicial complex $X_{R}$ consists of those
$F\in X$ such that $F\subseteq R$. We denote by $X_{-R}$ the restriction of
$X$ to the complement $R^{c}=X\backslash R$.

A facet $F$ of a simplicial complex $X$ is a leaf if there is a vertex $v$ of
$F$ such that $F$ is the only facet containing $v$. Such a vertex is a free
vertex of $X$. If $v$ is the only free vertex of $F$ we say $F$ is stacked on
$X_{-\\{v\\}}$.

######  Definition 2.1.

A pure simplicial complex (i.e., where all the facets have the same dimension)
is stacked if there is an ordering of its facets $F_{0},F_{1},\ldots,F_{k}$
such that if $X_{p-1}$ is the simplicial complex generated by
$F_{0},\ldots,F_{p-1}$, then $F_{p}$ is stacked on $X_{p-1}$ for $p\geq 1$.

######  Remark 2.2.

This is a special case of shellable simplicial complexes, see [9, Subsection
8.2]. It is not the same as the notion of simplicial complex being a tree as
in [5], even if the tree is pure. Rather the notion of stacked simplicial
complex is more general. For instance the triangulation of the heptagon given
in Figure 2, is not a tree in the sense of [5], since removing the triangles
$234$ and $257$ one has no facet which is a leaf.

######  Definition 2.3.

A (gallery) walk in a pure simplicial complex, is a sequence of facets
$f_{1},\ldots,f_{p}$ such that each $g_{i}=f_{i}\cap f_{i+1}$ has codimension
one in $f_{i}$ (and hence also in $f_{i+1}$). The left end vertex is the
single element of $f_{1}\backslash f_{2}$ and the right end vertex is the
single element of $f_{p}\backslash f_{p-1}$.

If $f_{i}\cap f_{i+1}=f_{j}\cap f_{j+1}$ for some $1\leq i<j<p$, we can make a
shorter walk from $f_{1}$ to $f_{p}$. If $f_{i}\neq f_{j+1}$ then

$f_{1},\ldots,f_{i},f_{j+1},\ldots,f_{p}$

is a shorter walk. If $f_{i}=f_{j+1}$, then

$f_{1},\ldots,f_{i-1},f_{j+1},\ldots,f_{p}$

is a shorter walk.

######  Definition 2.4.

A path is a walk where all the $f_{i}\cap f_{i+1}$ are distinct.

We see that any walk may be reduced to a path, without changing the first and
last facet.

######  Lemma 2.5.

Let $f_{1},f_{2},\ldots,f_{p}$ be a path. In a stacking order for $X$, let
$f_{i}$ come last among the facets of the path, for the stacking order, and
let $v$ be its free vertex. Then either $f_{i}=f_{1}$ and
$\\{v\\}=f_{1}\backslash f_{2}$ or $f_{i}=f_{p}$ and $\\{v\\}=f_{p}\backslash
f_{p-1}$.

###### Proof.

If $1<i<p$, then $f_{i}=(f_{i}\cap f_{i-1})\cup(f_{i}\cap f_{i+1})$, and so
$v$ would be on two facets. But this is not so. So $f_{i}$ must be one of the
end vertices and $\\{v\\}$ must be as above. ∎

The following generalizes the well-known situation for trees.

######  Proposition 2.6.

Let $X$ be a pure simplicial complex of dimension $d$ with $n$ facets and $v$
vertices. Then $X$ is stacked iff $v=n+d$ and between every pair of facets
there is a unique path.

###### Proof.

When $X$ is stacked it is clear from construction that $v=n+d$. Let $f$ and
$f^{\prime}$ be facets, and let

(1) $f=f_{1},f_{2},\ldots,f_{p}=f^{\prime},\quad
f=f_{1}^{\prime},f_{2}^{\prime},\ldots,f_{q}^{\prime}=f^{\prime}$

be two paths between them. We show they are equal. We first show that $p,q\geq
2$.

i) Suppose $q=1$, so $f=f^{\prime}$, and hence $f_{1}=f_{p}=f$. If the first
path has $p\geq 2$ it is easy to see that we must have $p\geq 4$. The last
facet in the stacking order for $X$ is $f=f^{\prime}$ by Lemma 2.5, and

$f_{1}\cap f_{2}=f_{1}\backslash\\{v\\},\quad f_{p-1}\cap
f_{p}=f_{p}\backslash\\{v\\}.$

So these two intersections are equal, which cannot be as we have a path.

Note that a consequence is that in a path we cannot have any facet appearing
twice.

ii) Then suppose $p,q\geq 2$. If $f_{2}=f_{2}^{\prime}$, we may delete
$f_{1}=f_{1}^{\prime}$. By induction the paths are equal. So we may assume
$f_{2}\neq f_{2}^{\prime}$ and similarly that $f_{p-1}\neq f_{q-1}^{\prime}$.
Of the facets in these two paths, consider the last one $g$ in the stacking
order of $X$ and let $v$ be its free vertex. It is one of the end facets, and
we may assume it is $g=f_{1}=f_{1}^{\prime}$. As above $v$ must be the left
end vertex of both paths, and so $f_{1}\cap f_{2}=f_{1}^{\prime}\cap
f_{2}^{\prime}$. Now let $h$ be the second last facet in the stacking order
and $w$ its free vertex. The only other possible facet containing $w$ would be
$g$. But if this is the case, since $v\neq w$ we get $w\in f_{1}\cap
f_{2}=f_{1}^{\prime}\cap f_{2}^{\prime}$. This is not possible as $w$ would
then be on three facets. Thus $w$ is on a single facet, and this must be the
right facet $f^{\prime}$ and also $w$ must be the right end vertex, implying
$f_{p}\cap f_{p-1}=f_{q}^{\prime}\cap f_{q-1}^{\prime}$.

If $p=q=2$ the paths are equal. If one of them is $2$, say $p=2$, we get

$f_{q}^{\prime}\cap f_{q-1}^{\prime}=f_{p}\cap f_{p-1}=f_{2}\cap
f_{1}=f_{2}^{\prime}\cap f_{1}^{\prime},$

a contradiction when $q\geq 3$.

Thus we may assume $p,q\geq 3$. Remove now the end facets $f$ and $f^{\prime}$
from the paths (1). We have

$f_{2}^{\prime}=(f_{2}^{\prime}\cap f_{1}^{\prime})\cup(f_{2}^{\prime}\cap
f_{3}^{\prime})\subseteq f_{2}\cup f_{3}^{\prime}.$

Then if $q\geq 4$, the last facet in the stacking order of the two paths (now
without $f$ and $f^{\prime}$) cannot be $f_{2}^{\prime}$ and similarly not
$f_{q-1}^{\prime}$. If also $p\geq 4$, the same argument applies and so none
of the end facets of the paths are last in the stacking order, a
contradiction. Thus we may assume, say $p=3$, and so $f_{2}$ is the last in
the stacking order. But

$f_{2}=(f_{1}\cap f_{2})\cup(f_{2}\cap f_{3})=(f_{1}^{\prime}\cap
f_{2}^{\prime})\cup(f_{q-1}^{\prime}\cap f_{q}^{\prime})\subseteq
f_{2}^{\prime}\cup f_{q-1}^{\prime},$

and this contradicts that $f_{2}$ has a free vertex together with
$f_{2},f_{2}^{\prime},f_{q-1}^{\prime}$ being distinct. (We cannot have
$f_{2}=f_{q-1}^{\prime}$ as $f_{q-1}^{\prime}$ cannot be last in the stacking
order.)

Conversely, assume $v=n+d$ and that between every pair of facets there is a
unique path. Choose a facet $f$, order the facets

(2) $f=f_{1},f_{2},\ldots,f_{n}$

such that the distance $\text{dist}(f,f_{i})\leq\text{dist}(f,f_{j})$ for
$i\leq j$. Let $Y_{p}$ be the simplicial complex generated by
$f_{1},\ldots,f_{p}$. Consider the path from $f$ to $f_{p+1}$:

$f=f^{1},f^{2},\ldots,f^{r}=f_{p+1}.$

Here all facets except the last $f^{r}$ are in $Y_{p}$ as they must be listed
before $f_{p+1}$ in (2) due to distance. Since $f^{r-1}\cap f^{r}$ has
codimension one in $f_{p+1}$, when passing from $Y_{p}$ to $Y_{p+1}$ we have
added at most one new vertex. Since $Y_{n}=X$ has $d+n$ vertices, we must have
added exactly one new vertex each time, and so $f_{n}$ has a single free
vertex, and $Y_{n-1}$ has $d+n-1$ vertices.

We show that between any two facets of $Y_{n-1}$ there is a unique path. This
will show that by induction that $Y_{n-1}$ is stacked and so $Y_{n}$ is also
stacked.

Let $f_{r},f_{s}$ be two facets in $Y_{n-1}$. Consider the path
$f_{r}=f^{1},\ldots,f^{p}=f_{s}$ in $X=Y_{n}$. If the last facet $f_{n}$ is on
this path, say $f_{n}=f^{t}$, then $1<t<p$ and

$f_{n}=f^{t}=(f^{t}\cap f^{t-1})\cup(f^{t}\cap f^{t+1})\subseteq Y_{n-1}.$

This is not so, and so the path from $f_{r}$ to $f_{s}$ is entirely in
$Y_{n-1}$. ∎

###  2.2. Paths between faces

######  Definition 2.7.

Let $h,k$ be faces in $X$ such that $h\cup k$ is not contained in any
codimension one face. A path between $h$ and $k$, written

$h|f_{1},\ldots,f_{p}|k$

is a path $f_{1},\ldots,f_{p}$ such that

$h\subseteq f_{1},h\not\subseteq f_{1}\cap f_{2},\quad k\subseteq
f_{p},k\not\subseteq f_{p}\cap f_{p-1}.$

We mainly use this when $h$ and $k$ consist of single points $\\{v\\}$ and
$\\{w\\}$, in which case we simply write $v$ instead of $\\{v\\}$, and
similarly for $w$.

######  Lemma 2.8.

In a path between $h$ and $k$ we have $h\not\subseteq f_{i}\cap f_{i+1}$ and
$k\not\subseteq f_{i}\cap f_{i+1}$ for each $1\leq i<p$.

###### Proof.

Suppose for $h$ there was an $r$ such that $h\subseteq f_{r}\cap f_{r+1}$. Let
$r$ be minimal such. Then we have a path

$h|f_{1},\ldots,f_{r}|h,\quad r\geq 2.$

Let $f$ be the last among these facets in the stacking order of $X$, and $v$
its free vertex. Then we may assume $f=f_{1}$ and we see that $v\in h$. But
then we must have $f_{r}=f_{1}$ since $v$ is on a single facet. In the proof
of Proposition 2.6 we showed that we cannot have a path of length $r\geq 2$
with the same start and end-facet ∎

######  Lemma 2.9.

Let $h,k$ be faces with union $h\cup k$ not contained in any codimension one
face. Then there is a unique path between them.

###### Proof.

Existence: If $h\cup k$ is a face $f$, then $h|f|k$ is path between them.
Assume then $h\cup k$ is not contained in a face.

Let $f$ be a facet containing $h$ and $f^{\prime}$ a facet containing $k$. Let

$f=f_{1},\ldots,f_{p}=f^{\prime}$

be the path between them. Let $i$ be maximal such that $h\subseteq f_{i}$. Let
$j\geq i$ be minimal such that $k\subseteq f_{j}$. Then we have a path from
$h$ to $k$:

$h|f_{i},\ldots,f_{j}|k.$

Uniqueness: Let

$h|f_{1},\ldots,f_{p}|k,\quad h|f_{1}^{\prime},\ldots,f_{q}^{\prime}|k$

be paths.

i) Suppose $p=1$ and $h\cup k=f_{1}$. For the two paths, let $f$ be the facet
last in the stacking order and $v$ the free vertex. If $f=f_{1}=h\cup k$, then
we must have $v\in f_{1}^{\prime}$ or $v\in f_{q}^{\prime}$, say the first
case and so $f_{1}^{\prime}=f_{1}$. Then $k\subseteq f_{1}=f_{1}^{\prime}$. By
Lemma 2.8, $k\not\subseteq f_{1}^{\prime}\cap f_{2}^{\prime}$. So we have a
path

$k|f_{1}^{\prime},\ldots,f_{q}^{\prime}|k.$

By the argument in Lemma 2.9, we must have $q=1$.

ii) Suppose the paths have $p,q\geq 2$. Of the facets in the paths, let $f$ be
the last in the stacking order, with free vertex $v$. Since
$f_{1}=h\cup(f_{1}\cap f_{2})$ and $v$ is on a single face, we have $v\in h$.
Hence $v\in f_{1}^{\prime}$, and so $f=f_{1}=f_{1}^{\prime}$. Then

$g:=f\backslash\\{v\\}=f_{1}\cap f_{2}=f_{1}^{\prime}\cap f_{2}^{\prime}.$

Since $k\not\subseteq f_{1}\cap f_{2}=g$, we have $g\cup k$ not included in a
codimension one face. So we get paths

$g|f_{2},\ldots,f_{p}|k,\quad g|f_{2}^{\prime},\ldots,f_{q}^{\prime}|k.$

By induction on length, these paths are equal. ∎

###  2.3. Distance neighborhoods

Choose a codimension one face $g$ in $X$. For $m\geq 1$, let $X_{m}$ consist
of those facets, whose distance to $g$ is $\leq m$. In particular
$X_{0}=\emptyset$ and $X_{1}$ is the set of facets containing $g$. Let $V_{0}$
be the vertices of $g$ and $V_{m}$ the vertices of $X_{m}$ for $m\geq 1$.

######  Lemma 2.10.

For $m\geq 1$, if $v\in V_{m}\backslash V_{m-1}$, there is a unique facet
$f_{v}$ in $X_{m}$ containing $v$, and $f_{v}\backslash\\{v\\}$ is a subset of
$V_{m-1}$.

###### Proof.

Let $f_{1}$ be a facet in $V_{m}$ containing $v$, and

$f_{1}|f_{1},\ldots,f_{r}|g$

the unique path from $f_{1}$ to $g$. We have $r\leq m$. Let $s$ be maximal
with $v\in f_{s}$. Then in $X_{m}$:

$v|f_{s},\ldots,f_{r}|g$

is the unique path from $v$ to $g$. Since $v\in V_{m}\backslash V_{m-1}$ we
must have $r-s+1=m$, and so $r=m$ and $s=1$. Then $f_{1}$ is the first facet
in the unique path from $v$ to $g$ and $f_{1}\backslash\\{v\\}\subseteq
f_{2}\subseteq V_{m-1}$. ∎

##  3\. Bijections between partitions of facets and of vertices

We show how partitions of facets and partitions of vertices into independent
sets correspond, and we show that this correspondence is really a bijection.
Our arguments are by induction on the distance neighbourhood $X_{m}$. We
develop some lemmata before the proof of the main theorem.

###  3.1. Bijections between partitions

######  Definition 3.1.

Let $X$ be a be a stacked simplicial complex with vertex set $V$, and $s$ an
integer $\geq 1$. A subset $A\subseteq V$ is $s$-scattered if the distance
between any two distinct vertices in $A$ is $\geq s$. The vertex set is
independent if it is $2$-scattered, i.e. no two vertices in $A$ are on the
same facet.

Similarly a subset $B$ of the facets is $s$-scattered if the distance between
any two facets in $B$ is $\geq s$.

We consider partitions of the vertices

(3) $V=V_{1}\sqcup V_{2}\sqcup\cdots\sqcup V_{r}$

into non-empty disjoint sets. Note that the order here is not relevant, so if
we switch $V_{i}$ and $V_{j}$ we have the same partition.

######  Remark 3.2.

If the $V_{i}$ are independent, this is almost the same as a graph coloring of
vertices, but not quite. A coloring of the vertices $V$ is a map
$f:V\rightarrow C$ where $C=\\{c_{1},\ldots,c_{r}\\}$ is a set of colors, such
that each inverse image $f^{-1}(c_{i})$ is a set of independent vertices. The
symmetric group $S_{r}$ acts on colorings by permuting the colors
$c_{1},\ldots,c_{r}$. So a partition as above (3) is an orbit for the action
of $S_{r}$. The class of such orbits, or equivalently of partitions (3) are
also called non-equivalent vertex colorings, see [8].

We also consider partitions of the facets

$F=F_{1}\sqcup F_{2}\sqcup\cdots\sqcup F_{s}.$

####  3.1.1. From vertex partitions to facet partitions.

Now we make a correspondence as follows. Given a partition of $V$ into non-
empty independent sets, given by an equivalence relation $\sim_{V}$. For ease
of following the arguments, we will think of each class as having a specific
color. Make a partition of $F$ as follows. Let $f$ and $f^{\prime}$ be facets.
Consider the unique path in $X$ between them:

$f=f_{1},\ldots,f_{p}=f^{\prime},$

and let $v$ and $w$ be respectively the left and right end vertices. If $v$
and $w$ have the same color, say blue, and none of the facets
$f_{2},\ldots,f_{p-1}$ has any blue vertex, then write
$f\sim^{\prime}_{F}f^{\prime}$. This means that $f$ and $f^{\prime}$ will be
in the same class of facets, these facets get the same color. The colors of
vertices and edges are however unrelated, so the facets $f$ and $f^{\prime}$
get some color unrelated to blue. The relation $\sim_{F}$ on $F$ is the
equivalence relation generated by $\sim_{F}^{\prime}$.

####  3.1.2. From facet partitions to vertex partitions

Conversely given a partition of the edges $F$, given by an equivalence
relation $\sim_{F}$. Make a partition of $V$ as follows. Let $v$ and $w$ be
independent vertices, and consider the path from $v$ to $w$:

$v|f_{1},\ldots,f_{p}|w.$

If $f_{1}$ and $f_{p}$ have the same color, say green, and none of the facets
$f_{2},\ldots,f_{p-1}$ are green, then let $v\sim^{\prime}_{V}w$. The relation
$\sim_{V}$ is the equivalence relation generated by $\sim^{\prime}_{V}$. See
Example 1.2.

We want to show that these correspondences are inverse to each other. To do
this we show:

A. From an equivalence relation $\sim_{F}$ on $F$, we have constructed the
equivalence relation $\sim_{V}$ on $V$. We show that the equivalence relation
$\sim_{V}$ in turn induces the equivalence relation $\sim_{F}$ again by
showing:

  * 1.

If $v\sim_{V}w$ are distinct and, say blue, and

$v|f_{1},\ldots,f_{p}|w$

where none of $f_{2},\ldots,f_{p-1}$ have a blue vertex, then $p\geq 2$ and
$f_{1}\sim_{F}f_{p}$ (in the original equivalence relation for $F$)

  * 2.

If $f\sim_{F}g$, say they are green, there is a sequence
$f=f_{0},f_{1},\ldots,f_{p}=g$ such that

$f_{0}\sim_{F}^{\prime}f_{1}\sim_{F}^{\prime}\cdots\sim_{F}^{\prime}f_{p}$

where $\sim^{\prime}_{F}$ is the relation constructed from $\sim_{V}$.

  * 3.

We also show that if the original $\sim_{F}$ is $s$-scattered, then $\sim_{V}$
is $s+1$-scattered.

B. From an equivalence relation $\sim_{V}$ on $V$, we have constructed the
equivalence relation $\sim_{F}$ on $F$. We show that this in turn induces the
equivalence relation $\sim_{V}$, by showing:

  * 1.

If we have a path with $p\geq 2$

$v|f_{1},\ldots,f_{p}|w$

where $f_{1}$ and $f_{p}$ are, say green, and none of $f_{2},\ldots,f_{p-1}$
are green, then $v\sim_{V}w$ (in the original equivalence relation for $V$).

  * 2.

If $v\sim_{V}w$ in the original relation, there is a sequence
$v=v_{0},v_{1},\ldots,v_{p}=w$ such that

$v_{0}\sim_{V}^{\prime}v_{1}\sim_{V}^{\prime}\cdots\sim_{V}^{\prime}v_{p},$

where $\sim_{V}^{\prime}$ is the relation constructed from $\sim_{F}$.

  * 3.

We also show that if the original $\sim_{V}$ is $s+1$-scattered, then
$\sim_{F}$ is $s$-scattered.

###  3.2. Induction arguments on $X_{m}$

We show this successively for the $X_{m}$ by induction. For this we need some
lemmata.

######  Lemma 3.3.

Given a partition of the facets $F$, and consider the relation
$\sim_{V}^{\prime}$ on vertices, constructed above in Subsection 3.1.2 Let
$v\in V_{m}\backslash V_{m-1}$, and $u,w$ distinct in $V_{m}$. If
$v\sim_{V}^{\prime}u$ and $v\sim_{V}^{\prime}w$, then $u\sim_{V}^{\prime}w$.

###### Proof.

We show first that $u,w$ are independent.

i) Suppose $u,w$ were on the same face $f$. Let

$f_{v}=f_{1},\ldots,f_{p}=f$

be the path from $f_{v}$ to $f$, see Lemma 2.10. If $u,w$ are both on
$f_{p-1}$ we may make a shorter path. So we may assume $u,w\in f_{p}$ and not
both in $f_{p}\cap f_{p-1}$. Assume then that $u$ is the right end vertex of
$f_{p}$. Then the above must be the unique path from $v$ to $u$, and so
$f_{1}\sim_{F}f_{p}$ have the same color. We have $w\in f_{p-1}$ and $w\not\in
f_{1}$ (since $v,w$ are independent). Let $r\geq 2$ be minimal such that $w\in
f_{r}$. We then have a path

$v|f_{1},\ldots,f_{r}|w$

and this is the unique path from $v$ to $w$. By definition of
$\sim_{V}^{\prime}$, $f_{1}$ and $f_{r}$ have the same color, say green, and
$f_{1}$ and $f_{p}$ have the same color (also green). But by definition of
$v\sim_{V}^{\prime}u$ there should not have been any green color between the
faces $f_{1}$ and $f_{p}$. Hence $u,w$ must be independent.

ii) Let

$v|f_{1},\ldots,f_{p}|u,\quad v|f^{\prime}_{1},\ldots,f^{\prime}_{q}|w,$

be the unique paths where $f_{1}=f_{1}^{\prime}$ by Lemma 2.10. Here $f_{1}$
and $f_{p}$ have the same color, say green, and $f_{1}^{\prime}(=f_{1})$ and
$f_{q}^{\prime}$ have the same color, also green, and none of the facets in
between have color green. Let $r$ be minimal such that $f_{r}\neq
f_{r}^{\prime}$. Then we get

(4)
$u|f_{p},\ldots,f_{r},f_{r-1}=f_{r-1}^{\prime},f_{r}^{\prime},\ldots,f_{q}^{\prime}|w$

is a walk where $f_{p}$ and $f_{q}^{\prime}$ are the only green facets. By
reducing this like after Definition 2.4, we get a path giving
$u\sim_{V}^{\prime}w$. ∎

######  Lemma 3.4.

Given a partition of $V$ into independent sets, and the relation
$\sim_{F}^{\prime}$ constructed as in Subsection 3.1.1. Let $f$ be a facet in
$X_{m}$ which is not in $X_{m-1}$. If $f\sim^{\prime}_{F}g$ and
$f\sim^{\prime}_{F}h$, then $g\sim^{\prime}_{F}h$.

###### Proof.

Let

$v|f=f_{1},\ldots,f_{p}=g|u,\quad
v|f=f_{1}^{\prime},\ldots,f_{q}^{\prime}=h|w$

where $v,u$ have the same color blue and none of $f_{2},\ldots,f_{p-1}$ have
blue vertices. Similarly $v,w$ have the same color blue, and none of
$f^{\prime}_{2},\ldots,f^{\prime}_{q-1}$ have blue vertices. We may then cut-
splice as above (4) and get

$w|h=f_{q}^{\prime},\ldots,f_{r}^{\prime},f^{\prime}_{r-1}=f_{r-1},f^{\prime}_{r},\ldots,f_{p}=g|u,$

and so $h\sim^{\prime}_{F}g$. ∎

######  Lemma 3.5.

Suppose the relation $\sim_{F}$, corresponds to the relation $\sim_{V}$ on
$V$. Consider the subcomplex $X_{m}$. The restricted relation
$\sim_{F}|_{X_{m}}$ then corresponds to the restricted relation
$\sim_{V}|_{X_{m}}$.

###### Proof.

Suppose given $\sim_{F}$. Let $v,w\in V_{m}$ such that $v\sim_{V}w$, so we
have

$v=v_{0}\sim^{\prime}_{V}v_{1}\sim^{\prime}_{V}\cdots\sim^{\prime}_{V}v_{t}=w.$

Let $\ell$ minimal such that all $v_{i}\in V_{\ell}$. If $\ell>m$ then some
$v_{i}\in V_{\ell}\backslash V_{\ell-1}$ where $0<i<t$. By the above Lemma 3.3
we may replace $v_{i-1}\sim^{\prime}_{V}v_{i}\sim^{\prime}_{V}v_{i+1}$ by
$v_{i-1}\sim^{\prime}_{V}v_{i+1}$. In this way we may reduce the above so all
$v_{i}\in V_{m}$, and thus $\sim_{F}|_{X_{m}}$ induces $\sim_{V}|_{X_{m}}$.

Suppose given $\sim_{V}$. Let $f,g\in X_{p}$ and $f\sim_{F}g$, so we have

$f=f_{1}\sim^{\prime}_{F}f_{2}\sim^{\prime}_{F}\cdots\sim^{\prime}_{F}=g.$

Again using Lemma 3.4 above we may reduce to all $f_{i}\in X_{m}$. ∎

###  3.3. The main theorem

######  Theorem 3.6.

Let $X$ be a stacked simplicial complex of dimension $d$, with vertex set $V$
and facet set $F$, and $s$ an integer $\geq 1$. The correspondences in
Subsections 3.1.1 and 3.1.2 give a one-to-one correspondence between
partitions of the vertices $V$ into $r+d$ non-empty sets, each
$s+1$-scattered, and partitions of the facets $F$ into $r$ non-empty sets,
each $s$-scattered.

###### Proof.

A. Assume we have started from a partition $\sim_{F}$ of facets $F$, and have
constructed the equivalence relation $\sim_{V}$ corresponding to a partition
of the vertices $V$. We show properties A1, A2, A3 for $X_{m}$ by induction on
$m$, so that $\sim_{V}$ in turn induces the original partition $\sim_{F}$.

Property A1: Suppose $v\sim_{V}w$ are distinct and, say blue, and let $m$ be
minimal such that $v,w\in X_{m}$. We may assume $v\in V_{m}\backslash
V_{m-1}$. Suppose we have a path from $v$ to $w$:

$v|f_{1},\ldots,f_{p}|w$

where $f_{2},\ldots,f_{p-1}$ have no blue vertices. We want to show
$f_{1}\sim_{F}f_{p}$ (in the original equivalence relation for $F$), that is,
they have the same color, say green. Let $f_{1}$ have color green, and let

(5)
$v=v_{0}\sim^{\prime}_{V}v_{1}\sim^{\prime}_{V}\cdots\sim^{\prime}_{V}v_{t}=w.$

By Lemma 3.5 we may assume all $v_{i}\in X_{m}$. Also, if $v_{i}\in
V_{m}\backslash V_{m-1}$ for some $0<i<t$, we may by Lemma 3.3 reduce to a
shorter such sequence. We may therefore assume the $v_{i}$ for $0<i<t$ are in
$V_{m-1}$. Consider the path in $X_{m}$:

$v=v_{0}|f_{1}^{\prime},\cdots,f_{q}^{\prime}|v_{1}.$

Then $f_{1}^{\prime}=f_{1}$ and $f_{q}^{\prime}$ have the same color green by
definition of $\sim_{V}^{\prime}$ and none of
$f_{2}^{\prime},\ldots,f^{\prime}_{q-1}$ are green. Both $v=v_{0}$ and $v_{1}$
are blue. We claim that none of $f_{2}^{\prime},\ldots,f_{q-1}^{\prime}$ has
any blue vertex. Let $2\leq r\leq q-1$ be maximal such that $f^{\prime}_{r}$
has a blue vertex $v^{\prime}$. We get a sequence
$v^{\prime}|f^{\prime}_{r},\ldots,f^{\prime}_{q}|v_{1}$. If $r\geq 2$ then
$v^{\prime}\in V_{m-1}$ (since $f_{1}^{\prime}\backslash\\{v\\}\subseteq
V_{m-1}$ by Lemma 2.10, and the path must then be in $V_{m-1}$). Then by
induction (on $m$) the facets $f_{r}^{\prime}$ and $f_{q}^{\prime}$ have the
same color, a contradiction. Thus none of
$f_{2}^{\prime},\ldots,f_{q-1}^{\prime}$ has a blue vertex.

$\mathbf{p\geq 2}$. Recall by Lemma 2.10 that $f_{1}=f_{v}$ is the only facet
in $X_{m}$ containing $v$. So $p\geq 2$ iff $v$ and $w$ are independent. If
$w$ was in $f_{1}$ then $w\in
f_{1}\backslash\\{v\\}=f_{1}^{\prime}\backslash\\{v\\}$, which is $f_{1}\cap
f_{2}=f_{1}^{\prime}\cap f_{2}^{\prime}$. In particular $w\in V_{m-1}$. By
induction, since $w,v_{1}$ are in $X_{m-1}$ and are related by (5), they are
either equal or independent. If equal, $v$ and $w$ are independent since
$v\sim_{V}^{\prime}w$. If $w$ and $v_{1}$ are independent, $w$ is not in
$f_{q}^{\prime}$. Then $q\geq 3$, and $f_{2}^{\prime}$ has a blue vertex, a
contradiction. The upshot is that $w$ is not in $f_{1}$, and so $p\geq 2$.

As in Lemma 3.3 we may cut-splice

(6) $v|f_{1},\ldots,f_{p}|w,\quad v|f_{1}^{\prime},\ldots
f_{q}^{\prime}|v_{1},(\text{ where }f_{1}=f_{1}^{\prime}),$

and get a walk

(7) $v_{1}|f_{q}^{\prime},\ldots
f_{r}^{\prime},f_{r-1}^{\prime}=f_{r-1},f_{r},\ldots,f_{p}|w,\quad\text{where
}r>1.$

If $r=2$ both $f_{r}$ and $f_{r}^{\prime}$ contain $f_{v}\backslash\\{v\\}$
and so either they are equal of $f_{r}\cap
f_{r}^{\prime}=f_{v}\backslash\\{v\\}$. By the procedure before Definition 2.4
we may reduce this to a shorter path from $f_{q}^{\prime}$ to $f_{p}$, without
$f_{r-1}=f_{r-1}^{\prime}$. Since none of the intermediate facets in (6)
contains a blue vertex, the same holds for the path obtained from (7).

Case 1: $w\in V_{m-1}$. Then by induction, since $v_{1}$ and $w$ are in
$X_{m-1}$, $f_{q}^{\prime}$ and $f_{p}$ have the same color green. As
$f_{q}^{\prime}$ and $f_{1}^{\prime}=f_{1}$ has the same color, green, we get
that $f_{1}$ and $f_{p}$ have the same color.

Case 2: $w\in V_{m}\backslash V_{m-1}.$ We have $w\sim_{V}v_{1}$, and only one
of $w,v_{1}$ (i.e. $w$) is in $V_{m}\backslash V_{m-1}$. This is Case 1 above,
and we conclude again that $f_{q}^{\prime}$ and $f_{p}$ have the same color.
Again as $f_{q}^{\prime}$ and $f_{1}^{\prime}=f_{1}$ have the same color,
green, we get that $f_{1}$ and $f_{p}$ are green.

Property A2: Suppose $f,g$ are green. Let

$f=f^{1},f^{2},\ldots,f^{p}=g$

be the unique path from $f$ to $g$. Let $q>1$ be minimal such that $f^{q}$ is
green, and consider the path

$v|f^{1},\ldots,f^{q}|w.$

Then $v\sim_{V}w$ and so are, say blue. If one $f^{r}$ where $r\in[2,q-1]$ has
a blue vertex, let $r$ be minimal such, and let $v^{\prime}$ be this vertex,
so we have a path

$v|f^{1},\ldots,f^{r}|v^{\prime}.$

By part A1, $f^{1}$ and $f^{r}$ have the same color, which must be green. This
is a contradiction and so none of $f^{2},\ldots,f^{q-1}$ has a blue vertex.
Thus $f^{1}\sim_{F}^{\prime}f^{q}$. Let $f_{0}=f$ and $f_{1}=f^{q}$.
Considering now the shorter path $f^{q},f^{q+1},\ldots,f^{p}$. By induction on
length of path, there are

$f^{q}=f_{1}\sim_{F}^{\prime}\cdots\sim_{F}^{\prime}f_{r}=f^{p},$

and so we get part A2.

Property A3: Suppose $\sim_{F}$ is $s$-scattered. Let $v,w$ be blue vertices
whose distance $p$ is as small as possible. We have a path

$v|f^{1},f^{2},\ldots,f^{p}|w.$

None of $f^{2},\ldots,f^{p-1}$ can then have blue vertices. Thus
$f^{1}\sim_{F}f^{p}$ by what we showed in A1, and their distance is $p-1\geq
s$. Whence $p\geq s+1$ and the blue vertices are $s+1$-scattered.

B. We have started from a partition $\sim_{V}$ of the vertices $V$ into
independent sets. We have constructed from this an equivalence relation
$\sim_{F}$ and corresponding partition of the facets. We show that properties
B1, B2, B3 holds for $X_{m}$ by induction on $m$, so that $\sim_{F}$ induces
the original partition $\sim_{V}$.

Property B1: Suppose $f\sim_{F}g$, and the path from $f$ to $g$ is

(8) $v|f=f_{1},\ldots,f_{p}=g|w$

where $f_{1},f_{p}$ are green and none of $f_{2},\ldots,f_{p-1}$ are green. We
show that $v\sim_{V}w$, they have the same color, say blue.

There is a sequence

$f=f^{0}\sim^{\prime}_{F}f^{1}\sim^{\prime}_{F},\ldots,\sim^{\prime}_{F}f^{t}=g.$

Let $m$ be smallest possible such that $v,w\in V_{m}$. One of them, say $v\in
V_{m}\backslash V_{m-1}$. If for some $0<i<t$ we have $f^{i}\in
X_{m}\backslash X_{m-1}$ we may by Lemma 3.4 shorten the sequence. So we may
assume $f^{i}\in X_{m-1}$ for $0<i<t$.

Since $v\in V_{m}\backslash V_{m-1}$ we have $f^{0}=f_{v}$. Now look at at the
path from $f^{0}$ to $f^{1}$

$v=v^{0}|f^{0}=f_{1}^{\prime},\ldots,f_{q}^{\prime}=f^{1}|v^{1},$

where $v=v^{0}$ and $v^{1}$ are blue, and
$f_{2}^{\prime},\ldots,f_{q-1}^{\prime}$ do not have any blue vertex. The
facets $f_{1}^{\prime}=f^{0}=f$ and $f_{q}^{\prime}$ have the same color,
which is green. Are there any green facets in between? Suppose $2\leq r\leq
q-1$ is maximal such that $f_{r}^{\prime}$ is green. We have a path

$v^{2}|f_{r}^{\prime},\cdots,f_{q}^{\prime}|v^{1}$

where all $f_{r}^{\prime},\ldots,f_{q}^{\prime}$ are in $X_{m-1}$. By
induction on $m$, $v^{2}$ and $v^{1}$ have the same color, blue. This is a
contradiction, as $f_{r}^{\prime}$ has no blue vertex. So $f_{1}^{\prime}$ and
$f_{q}^{\prime}$ are green, while no facets in between are green.

As in Lemma 3.3 we may then cut-splice

$v|f=f_{1},\ldots,f_{p}=g|w,\quad
v=v^{0}|f_{1}=f_{1}^{\prime},\ldots,f_{q}^{\prime}|v^{1}$

where $v^{1}\in V_{m-1}$ and get a walk

$v^{1}|f_{q}^{\prime},\ldots,f_{r}^{\prime},f_{r-1}^{\prime}=f_{r-1},f_{r},\ldots,f_{p}|w,$

Case 1: $w\in V_{m-1}$. Then in the path from $v^{1}$ to $w$, the end facets
are green, and no intermediate facet is green. By induction on $m$ (since both
$v^{1}$ and $w$ are in $X_{m-1}$), we get that $v^{1}$ and $w$ have the same
color. Furthermore $v$ and $v^{1}$ have the same color, blue, so both $v$ and
$w$ are blue.

Case 2: $w\in V_{m}\backslash V_{m-1}$. We have exactly one of $w,v^{1}$ (i.e.
$w$) in $V_{m}\backslash V_{m-1}$. The path from $v^{1}$ to $w$ has end facets
green and no intermediate facet green. By Case 1, $w$ and $v^{1}$ have the
same color. Since $v$ and $v^{1}$ are both blue, we get that $v$ and $w$ are
both blue.

Property B2: Suppose $v,w$ are distinct and blue. Let

$v|f^{1},\ldots,f^{p}|w$

be the unique path from $v$ to $w$. Let $q\geq 2$ be minimal such that $f^{q}$
contains a blue vertex $v^{\prime}=v_{1}$. Then $f^{1}\sim_{F}f^{q}$ by
construction, say they are green. Consider the path

$v|f^{1},\ldots,f^{q}|v^{\prime}.$

If one $f^{r}$ for $r\in[2,q-1]$ is green, let $r$ minimal such. Then we have
a path

$v|f^{1},\ldots,f^{r}|v^{\prime\prime}$

and by B1 we have $v\sim_{V}v^{\prime\prime}$, both blue. This contradicts the
choice of $q$. Thus $v\sim_{V}^{\prime}v^{\prime}$. Now $v^{\prime}\in f^{q}$.
If $q=p$ we have $v^{\prime}=w$ and we are done. If $q<p$ then $v^{\prime}\neq
w$. Let $q\leq r<p$ be maximal such that $v^{\prime}\in f^{r}$. We then get

$v^{\prime}|f^{r},\ldots,f^{p}|w.$

By induction on path length there are

$v^{\prime}=v_{1}\sim_{V}^{\prime}v_{2}\sim_{V}^{\prime}\cdots\sim_{V}^{\prime}v_{s}=w,$

and so we get part B2.

Property B3: Suppose $\sim_{V}$ is $s+1$-scattered. Let $f\sim_{F}g$ be green
facets whose distance $p$ is as small as possible with path

$v|f=f_{0},f_{1},\ldots,f_{p}=g|w.$

None of the intermediate facets $f_{1},\ldots,f_{p-1}$ are green. Then we have
just shown in B1 that $v\sim_{V}w$ and so their distance $p+1\geq s+1$. Thus
the green facets are $s$-scattered. ∎

######  Corollary 3.7.

Let $X$ be a tree, and $s\geq 1$. There is a bijection between partitions of
the vertices into $r+1$ non-empty sets, each set $s+1$-scattered, and
partitions of the edges into $r$ non-empty sets, each $s$-scattered.

######  Corollary 3.8.

Let $X$ be a triangulation of a polygon and $s\geq 1$. There is a bijection
between partitions of the vertices into $r+2$ non-empty sets, each set
$s+1$-scattered, and partitions of the triangles into $r$ non-empty sets, each
$s$-scattered.

##  4\. Partitions of natural numbers

The main theorem here appears quite surprising and non-trivial even for the
simplest of trees, the line graph. Then it corresponds to studying ordered set
partitions, which has a comprehensive theory [11].

Taking the colimit of longer and longer line graphs, we get results for the
natural numbers, and we think it worth stating these although they are simple
consequences of known results for ordered set partitions [2, Thm.2.2] or in a
more enumerative form [3, Thm.1]. [12] also considers partitions of intervals
$[n]$, but with requirements on the parts which are different from ours here.

Consider the infinite line graph

The set of edges $E$ may be identified with the natural numbers
${\mathbb{N}}$, and also the set of vertices $V$ may be identified with
${\mathbb{N}}$. Let $L_{n}$ be the line graph with $n$ edges. The bijection
between partitions edges into $r$ parts, each $d$-scattered, and partitions of
vertices into $r+1$ parts, each $d$-scattered, is compatible with extending
the line graph $L_{n}=(V_{n},E_{n})$ with one edge and vertex to the line
graph $L_{n+1}$: If $(E^{i})$ is a partition of edges in $L_{n+1}$
corresponding to a partition $(V^{j})$ of vertices. Then the partition
$(E^{i}\cap E_{n})$ corresponds to $(V^{j}\cap V_{n})$.

Thus taking the colimit, we get for the infinite line graph (4) a bijection
between partitions of edges $(E^{i})$ into $r$ parts, each $d$-scattered, and
partitions of vertices $(V^{j})$ into $r+1$ parts, each $d+1$-scattered.

Recall that a subset $A\subseteq{\mathbb{N}}$ of natural numbers is
$d$-scattered if for every $p<q$ in $A$ we have $q-p\geq d$.

######  Theorem 4.1.

There is a bijection between partitions of ${\mathbb{N}}$ into $r$ sets, each
$d$-scattered, and partitions of ${\mathbb{N}}$ into $r+1$ sets, each
$d+1$-scattered.

By successively going from $r$ to $r+1$ to $r+2$ and so on we get:

######  Corollary 4.2.

There is a bijection between partitions of ${\mathbb{N}}$ into $r+1$ parts
$A_{0}\sqcup A_{1}\sqcup\cdots\sqcup A_{r}$ (each set by default being
$1$-scattered) and partitions of ${\mathbb{N}}$ into $r+d$ parts
$B_{0}\sqcup\cdots\sqcup B_{r+d-1}$, each $d$-scattered.

Specializing to $r=0$ we get the trivial:

######  Corollary 4.3.

There is a bijection between partitions of ${\mathbb{N}}$ into one part
$A_{0}={\mathbb{N}}$ and partitions of ${\mathbb{N}}$ into $d$ parts
$B_{0}\sqcup\cdots\sqcup B_{d-1}$, each $d$-scattered.

Clearly this partition is the congruence classes modulo $d$. However
specializing to $r=1$, we get the quite non-trivial:

######  Corollary 4.4.

For each $d\geq 1$ there is a bijection between partitions of ${\mathbb{N}}$
into two parts $A_{0}\sqcup A_{1}$ and partitions of ${\mathbb{N}}$ into $d+1$
parts $B_{0}\sqcup\cdots\sqcup B_{d}$, each being $d$-scattered.

######  Example 4.5.

For $r=1$ let the partition be $\\{p\\}\sqcup{\mathbb{N}}\backslash\\{p\\}$,
the one part consisting of a single element $p$. This corresponds to a
partition of ${\mathbb{N}}$ into three parts, each being $2$-scattered. We use
$\ldots$ to indicate arithmetic progression of step size $2$. These parts are:

$\displaystyle\ldots,p-4,p-2,$ $\displaystyle\,\,p$
$\displaystyle\,\,p+1,p+3,p+5,\ldots$ $\displaystyle\ldots,p-3,p-1,$
$\displaystyle\,\,p+2,p+4,\ldots$

It also corresponds to a partition of ${\mathbb{N}}$ into four parts, each
being $3$-scattered. (Here $\ldots$ denotes progression with step size $3$.)
These parts are:

$\displaystyle\ldots,p-6,p-3,$ $\displaystyle\,\,p$
$\displaystyle\ldots,p-5,p-2,$ $\displaystyle\,\,p+1,p+4,p+7,\ldots$
$\displaystyle\,\,p+2,p+5,\ldots$ $\displaystyle\ldots,p-4,p-1,$
$\displaystyle\,\,p+3,p+6,\ldots.$

######  Example 4.6.

Let again $r=1$. Consider the partition
$\\{p,q\\}\sqcup{\mathbb{N}}\backslash\\{p,q\\}$ where $p<q$. It corresponds
to the following three parts, each $2$-scattered. We get two cases, according
to whether $q-p$ is even or odd. When $q-p$ is even:

$\displaystyle\ldots,p-3,$ $\displaystyle\,\,p-1,p+2,\quad\ldots$
$\displaystyle q-2,$ $\displaystyle\,\,q$ $\displaystyle\ldots,p-4,p-2,$
$\displaystyle\,\,p,$ $\displaystyle\,\,q+1,q+3,\ldots$
$\displaystyle\,\,p+1,p+3,\quad\ldots$ $\displaystyle q-3,q-1,$
$\displaystyle\,\,q+2,q+4,\ldots.$

Note that in the middle part there is quite a long gap from $p$ to $q+1$. When
$q-p$ is odd:

$\displaystyle\,\,p+1,p+3,\quad\ldots$ $\displaystyle q-2,$
$\displaystyle\,\,q$ $\displaystyle\ldots,p-4,p-2,$ $\displaystyle\,\,p,$
$\displaystyle\,\,q+1,q+3,\ldots$ $\displaystyle\ldots,p-3,$
$\displaystyle\,\,p-1,p+2,\quad\ldots$ $\displaystyle q-1,$
$\displaystyle\,\,q+2,q+4,\ldots$

## References

  * [1] Ayah Almousa, Gunnar Fløystad, and Henning Lohne, _Polarizations of powers of graded maximal ideals_ , Journal of Pure and Applied Algebra 226 (2022), no. 5, 106924.
  * [2] William YC Chen, Eva YP Deng, and Rosena RX Du, _Reduction of m-regular noncrossing partitions_ , European Journal of Combinatorics 26 (2005), no. 2, 237–243.
  * [3] Wenchang Chu and Chuanan Wei, _Set partitions with restrictions_ , Discrete mathematics 308 (2008), no. 15, 3163–3168.
  * [4] Bryce Duncan and Rhodes Peele, _Bell and Stirling numbers for graphs_ , J. Integer Seq 12 (2009), no. 09.7.1, 1–13.
  * [5] Sara Faridi, _The facet ideal of a simplicial complex_ , Manuscripta Mathematica 109 (2002), no. 2, 159–174.
  * [6] Gunnar Fløystad and Milo Orlich, _Triangulations of polygons and stacked simplicial complexes: separating their Stanley–Reisner ideals_ , Journal of Algebraic Combinatorics (2022), 1–28.
  * [7] Gunnar Fløystad and Amir Mafi, _Polarizations of artin monomial ideals define triangulated balls_ , https://arxiv.org/abs/2212.09528 (2022).
  * [8] A Hertz and H Mélot, _Counting the Number of Non-Equivalent Vertex Colorings of a Graph_ , Les Cahiers du GERAD ISSN G-2013-82 (2013), 1–16.
  * [9] Jürgen Herzog and Takayuki Hibi, _Monomial ideals_ , Springer, 2011.
  * [10] Zsófia Kereskényi-Balogh and Gábor Nyul, _Stirling numbers of the second kind and Bell numbers for graphs_ , Australas. J Comb. 58 (2014), 264–274.
  * [11] Toufik Mansour, _Combinatorics of set partitions_ , CRC Press Boca Raton, 2013\.
  * [12] Augustine O Munagi, _Extended set partitions with successions_ , European Journal of Combinatorics 29 (2008), no. 5, 1298–1308.
  * [13] Winston Yang, _Bell numbers and k-trees_ , Discrete Mathematics 156 (1996), no. 1-3, 247–252.


# CofeNet: Context and Former-Label Enhanced Net for Complicated Quotation
Extraction

Yequan Wang1∗, Xiang Li2∗, Aixin Sun3, Xuying Meng4, Huaming Liao4, Jiafeng
Guo4
1Beijing Academy of Artificial Intelligence, Beijing, China
2Alibaba Group, China
3School of Computer Science and Engineering, Nanyang Technological University,
Singapore
4Institute of Computing Technology, Chinese Academy of Sciences, Beijing,
China
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
{mengxuying, lhm<EMAIL_ADDRESS>

###### Abstract

Quotation extraction aims to extract quotations from written text. There are
three components in a quotation: source refers to the holder of the quotation,
cue is the trigger word(s), and content is the main body. Existing solutions
for quotation extraction mainly utilize rule-based approaches and sequence
labeling models. While rule-based approaches often lead to low recalls,
sequence labeling models cannot well handle quotations with complicated
structures. In this paper, we propose the Context and Former-Label Enhanced
Net (CofeNet) for quotation extraction. CofeNet is able to extract complicated
quotations with components of variable lengths and complicated structures. On
two public datasets (i.e., PolNeAR and Riqua) and one proprietary dataset
(i.e., PoliticsZH), we show that our CofeNet achieves state-of-the-art
performance on complicated quotation extraction.

CofeNet: Context and Former-Label Enhanced Net for Complicated Quotation
Extraction

Yequan Wang1∗, Xiang Li2∗, Aixin Sun3, Xuying Meng4, Huaming Liao4, Jiafeng
Guo4 1Beijing Academy of Artificial Intelligence, Beijing, China 2Alibaba
Group, China 3School of Computer Science and Engineering, Nanyang
Technological University, Singapore 4Institute of Computing Technology,
Chinese Academy of Sciences, Beijing, China<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>{mengxuying, lhm,
<EMAIL_ADDRESS>

11footnotetext: Indicates equal contribution

##  1 Introduction

Quotation extraction aims to extract quotations from written text Pouliquen et
al. (2007). For example, given one instance shown in Figure 1, we extract the
quotation with source: some democrats, cue: privately express, and content:
reservations about …. As a point of view, quotations provide opinions of the
speaker, which is important for analyzing the speaker’s stand. In general,
quotation extraction is the first step before any further analysis, e.g.,
speaker stand detection. In this paper, we focus on the extraction of the
three quotation components.

As illustrated in the above example, the extraction of content component in a
quotation is complicated and difficult due to three reasons: variable length,
unclear boundary, and indistinguishable components. Specifically, the length
of content can be over $10$, or even more than $50$ tokens. Moreover, content
does not come with a regular pattern, which not only leads to a more unclear
boundary of itself, but also affects the estimation of source and cue. For
example, content in a quotation can be a complete instance with subject,
predicate, and object. It is therefore hard to distinguish a noun (subject or
object) representing the source or a part of content. Difficulty also exists
in recognition of cue when tackling with a predicate, e.g., verb. Thus, as
content may contain another quotation, such a nesting structure further
increases the difficulty of extracting quotations.

Figure 1: An example of quotations. Text spans with orange, green and gray
denote source, cue and content respectively.

Many existing solutions for quotation extraction are rule-based methods
Pouliquen et al. (2007); Krestel et al. (2008); Elson and McKeown (2010); Vu
et al. (2018). Generally, quotations include direct quotations and indirect
quotations. Quotation marks and their variants are clear; thus content can be
extracted by using regular expressions. However, not all quoted texts are
quotations. Meanwhile, not all quotations are quoted. Another popular rule-
based approach is to recognize cue words, e.g., speak(s). Similarly, not all
cue words are related to quotations and vice versa. For both approaches, after
recognizing content or cue, they usually search for the nearby noun as source.
In short, rule-based methods only cover limited cases, leading to serious low
recall problems.

Quotation extraction has also been formulated as a sequence labeling task.
Pareti et al. (2013); Lee et al. (2020) directly adopt sequence labeling for
quotation extraction. However, these solutions ignore the traits of quotations
where lengths of quotation components are variable and structures of content
are complicated. In general, source and cue components are short, e.g., $\leq
3$ tokens. However, content usually is over $10$ tokens, or even more.
Further, the complicated structure of content greatly reduces the performance
of content extraction for sequence-labeling-based solutions.

In this paper, we propose Context and Former-Label Enhanced Net (CofeNet) for
quotation extraction. CofeNet is a novel architecture to extract quotations
with variable-length and complicated-structured components. Our model is also
capable of extracting both direct and indirect quotations.

CofeNet extracts quotations by utilizing dependent relations between sequenced
texts. The model contains three components, i.e., Text Encoder, Enhanced Cell,
and Label Assigner. Given a piece of text, the encoder encodes the instance
and outputs the encoded hidden vectors. We design the Enhanced Cell module to
study semantic representations of variable-length components with the
utilization of contextual information. Specifically, the enhanced cell (i)
uses a composer layer to enhance the input with the former labels (which are
predicted by the former cells), the former words, the current word, and the
latter words encoded by the encoder; and (ii) uses a gate layer and an
attention layer to control and attend the corresponding input when predicting
the label of the current word, at the level of element and vector
respectively. Experimental results on two public datasets (i.e., PolNeAR and
Riqua) and one proprietary dataset (i.e., PoliticsZH) show that our CofeNet
achieves state-of-the-art performance on complicated quotation extraction.

##  2 Related Work

At first glance, quotation detection is a kind of “triplet” extraction, making
the task similar to another two tasks, open information extraction Angeli et
al. (2015); Gashteovski et al. (2017) and semantic role labeling Exner and
Nugues (2011). However, these three tasks have different focuses. Arguments
extracted by semantic role labeling are event-related factors. OpenIE aims to
output a structured representation of an instance in the form of binary or
n-ary tuples, each of which consists of a predicate and several arguments. The
extracted text spans in both tasks are typically short and less complicated,
compared to the content in quotations. Because content extraction is the key
challenge in quotation extraction, we will not further elaborate on semantic
role labeling and OpenIE. Prior work on quotation extraction can be grouped
into rule-based and sequence labeling methods.

###  2.1 Rule-based Methods

Extracting indirect quotations without clear boundaries is a challenging task,
so early studies focus on rule-based methods to extract direct quotations
Pouliquen et al. (2007); Krestel et al. (2008); Elson and McKeown (2010). In
fact, rule-based methods perform well for marked texts, especially for direct
quotations.

Pattern matching is a popular method in early studies. Pouliquen et al.
(2007); Elson and McKeown (2010) identify content, cue and source by known
quote-marks, pre-defined vocabulary, and rules of pattern recognition. The
difference is that Elson and McKeown (2010) add machine learning methods to
the quote attribution judgment so that they can process complex text. O’Keefe
et al. (2012) use regular expressions to recognize quote-marks to extract
components, then use sequence labeling to recognize quotation triplets.

Hand-built grammar is another popular rule-based method. Krestel et al. (2008)
design a system by combining common verbs corresponding to cue and hand-built
grammar to detect constructions that match six general lexical patterns.
PICTOR Schneider et al. (2010) utilizes context-free grammar to extract
components of quotations.

###  2.2 Sequence Labeling Methods

Due to the development of deep learning, sequence-labeling-based approaches
have attracted attention Pareti et al. (2013); Lee et al. (2020). To identify
the beginning of a quotation, Fernandes et al. (2011) use sequence labeling
with features including part-of-speech and entity features generated by a
guided transformation learning algorithm. Then they use regular expressions to
recognize the content within quotations. Pareti et al. (2013) follow a similar
idea but use CRF to decode the label. Lee et al. (2020) further use BERT to
encode the text and CRF to decode the label on a non-public Chinese news
dataset. However, these models cannot well handle quotations with complicated
structures.

Figure 2:  The architecture of CofeNet. Enhanced Cell is detailed on the
right-hand side. (best viewed in color)

##  3 CofeNet Model

Figure 2 depicts the architecture of CofeNet. It consists of three modules:
Text Encoder, Enhanced Cell, and Label Assigner. Text encoder is used to
encode the input text to get hidden representations. Then, the enhanced cell
is capable of building a representation considering the trait of quotations
including variable-length and complicated-structured components. Last, the
label assigner is to assign labels “B-source”, “B-cue”, “B-content”,
“I-source”, “I-cue”, “I-content” and “O”, with BIO scheme.

###  3.1 Text Encoder

CofeNet is generic and can be realized by popular encoders such as LSTM
Hochreiter and Schmidhuber (1997), CNN Kim (2014), Recursive Neural Network
Socher et al. (2011), and BERT Devlin et al. (2019a). Unless otherwise
specified, CofeNet denotes the model using BERT Devlin et al. (2019b) as the
encoder.

Given input text, hidden states of words are formulated by:

$\\{h_{1},h_{2},\dots,h_{N}\\}=\text{Encoder}(\\{x_{1},x_{2},\dots,x_{N}\\}),$

where, $x_{i}$ is the $i$-th word of input, and Encoder denotes the Text
Encoder. The hidden state $h_{i}$ denotes the representation of $i$-th word
$x_{i}$ while encoding the preceding contexts of the position.

###  3.2 Enhanced Cell

As aforementioned, the challenge of quotation extraction is to extract the
complicated-structured components with variable lengths. To this end, we
design the enhanced cell with composer layer, gate layer, and attention layer,
to study the semantic representations of variable-length components. At the
same time, we also try to utilize contextual information and predicted labels.

Shown in Figure 2, the composer is used to reformat the input information to
include the former labels $y_{i-k},\dots,y_{i-1}$, the former hidden states
$h_{i-m},\dots,h_{i-1}$, the current state $h_{i}$, and the latter states
$h_{i+1},\dots,h_{i+n}$. In this way, our model is able to consider a long
span with different structures in a more coherent manner on top of encoded
word representations. In general, the influence of different inflow
information is different. To this end, we use a gate mechanism to control each
element of input representations, and an attention mechanism to weigh the
input representations at the vector level. Through the two mechanisms, we get
a refined representation so that we could hold the complicated-structured and
variable-length components of quotations. Next, we detail the workflow of the
enhanced cell.

Composer Layer. The composer contains a label embedding unit and a linear unit
to reformat the inflow information: the former labels
{$y_{i-k},\dots,y_{i-1}\\}$, the former hidden states
$\\{h_{i-m},\dots,h_{i-1}\\}$ of previous $m$ words, the current state $h_{i}$
of the current word $x_{i}$, and the latter states
$\\{h_{i+1},\dots,h_{i+n}\\}$ of latter $n$ words.

First, the enhanced cell contains a label embedding unit, which is able to
select the embedding of the given label, formulated by:

$e_{i}=\text{Emb}(y_{i}),$ (1)

where Emb denotes the mentioned label embedding unit. The predicted label of
word $i$ is $y_{i}$ and the embedding of $y_{i}$ is $e_{i}$. Taking the former
$k$ predicted labels into consideration, we get the former labels’
representations $[e_{i-k},\dots,e_{i-1}]$ by concatenation, which is shown as
a rectangle in green background, in the Enhanced Cell in Figure 2.

Intuitively, contextual information is important for us to predict the label
of the current input word. We take the following context through simple but
effective linear layers: the former predicted $k$ labels, the former $m$
words, the current word $i$, and the latter $n$ words.

$\displaystyle h_{i}^{y}$
$\displaystyle=\operatorname{GELU}([e_{i-k},\dots,e_{i-1}]W_{y}+b_{y})$ (2)
$\displaystyle h_{i}^{f}$
$\displaystyle=\operatorname{GELU}([h_{i-m},\dots,h_{i-1}]W_{f}+b_{f})$ (3)
$\displaystyle h_{i}^{c}$
$\displaystyle=\operatorname{GELU}(h_{i}W_{c}+b_{c})$ (4) $\displaystyle
h_{i}^{l}$
$\displaystyle=\operatorname{GELU}([h_{i+1},\dots,h_{i+n}]W_{l}+b_{l})$ (5)

In the above formulation, the hidden states
$\\{h_{i-m},\dots,{h_{i}},\dots,h_{i+n}\\}$ and label embeddings
$\\{e_{i-k},\dots,e_{i-1}\\}$ are the input. $W_{y},W_{f},W_{c},W_{l}$ and
$b_{y},b_{f},b_{c},b_{l}$ are the parameters of the linear layers. Here, we
adopt $\operatorname{GELU}$ as the active function.
$h_{i}^{y},h_{i}^{f},h_{i}^{c},h_{i}^{l}$ denote the farther hidden states of
the former labels, the former words, the current word and the latter words,
respectively.

Gate Layer. The influence of different contexts is different. Hence, we use a
gate mechanism to control the inflow hidden states at the element level.
Inspired by Hochreiter and Schmidhuber (1997), we design a gate layer in the
enhanced cell:

$\displaystyle r_{i}^{y}$
$\displaystyle=h_{i}^{y}\odot\operatorname{sigmoid}([h_{i}^{y},h_{i}^{c}]W_{y}^{z}+b_{y}^{z})$
(6) $\displaystyle r_{i}^{f}$
$\displaystyle=h_{i}^{f}\odot\operatorname{sigmoid}([h_{i}^{y},h_{i}^{c}]W_{f}^{z}+b_{f}^{z})$
(7) $\displaystyle r_{i}^{c}$
$\displaystyle=h_{i}^{c}\odot\operatorname{sigmoid}([h_{i}^{y},h_{i}^{c}]W_{c}^{z}+b_{c}^{z})$
(8) $\displaystyle r_{i}^{l}$
$\displaystyle=h_{i}^{l}\odot\operatorname{sigmoid}([h_{i}^{y},h_{i}^{c}]W_{l}^{z}+b_{l}^{z})$
(9)

In the above formulation, $r_{i}^{y}$, $r_{i}^{f}$, $r_{i}^{c}$, and
$r_{i}^{l}$ denote the adjusted states of the former labels, the former words,
the current word, and the latter word representation, respectively. The
operation $\odot$ denotes element-wise product. $W_{y}^{z}$, $W_{f}^{z}$,
$W_{c}^{z}$, $W_{l}^{z}$, and $b_{y}^{z}$, $b_{f}^{z}$, $b_{c}^{z}$,
$b_{l}^{z}$ are the parameters. We use $\operatorname{sigmoid}$ to adjust each
element of the inflow representations.

Attention Layer. Inspired by Wang et al. (2016); Yang et al. (2016); Wang et
al. (2018); Lin et al. (2019); Meng et al. (2022), we use an attention
mechanism to attend the important part of $r_{i}^{y}$, $r_{i}^{f}$,
$r_{i}^{c}$, and $r_{i}^{l}$. Since our target is to predict the label of the
current word, we use the concatenation of $h_{i}^{y}$ and $h_{i}^{c}$ to
attend the four vectors by

$\alpha_{y},\alpha_{f},\alpha_{c},\alpha_{l}=\operatorname{softmax}([h_{i}^{y},h_{i}^{c}]W_{w}+b_{w}),$
(10)

where $\alpha_{y},\alpha_{f},\alpha_{c}$, and $\alpha_{l}$ are the weights for
$r_{i}^{y}$, $r_{i}^{f}$, $r_{i}^{c}$, and $r_{i}^{l}$ respectively. $W_{w}$
and $b_{w}$ are the parameters. In the attention layer,
$\operatorname{softmax}$ function is used to calculate weights. Then, the
current word representation $r_{i}$ is obtained via:

$r_{i}=\alpha_{y}r_{i}^{y}+\alpha_{f}r_{i}^{f}+\alpha_{c}r_{i}^{c}+\alpha_{l}r_{i}^{l}$
(11)

To summarize, the Enhanced Cell uses the gate and attention layers with
contextual information (i.e., former labels, former words, current word, and
latter words) to handle complicated-structured components with variable
lengths. Specifically, to sense continuous span, we use attention layer by
attending contextual information at the vector (macro) level, by using former
labels, and the former, current, and latter word(s). Thus, the model avoids
undesirable interruption within an instance. We also use the gate layer to
control contextual information at the element (micro) level, especially former
labels. Further, thanks to the ability of fine control, the gate layer is
capable of avoiding illegal patterns, e.g., “O” followed by “I-*”.

###  3.3 Label Assigner

After getting the hidden representation of the current word, we use label
assigner module to compute a probability distribution of the current label.

Briefly speaking, in label assigner, we use $\operatorname{softmax}$
classifier to calculate the distribution $\mathcal{P}_{i}$ of the current word
$i$. Then $\operatorname{argmax}$ is used to assign a label of the current
word. The two operations can be formulated as

$\displaystyle\mathcal{P}_{i}$
$\displaystyle=\operatorname{softmax}(r_{i}W_{p}+b_{p}),$ (12) $\displaystyle
y_{i}$ $\displaystyle=\operatorname{argmax}(\mathcal{P}_{i}),$ (13)

where $W_{p}$ and $b_{p}$ are the parameters.

###  3.4 Training Objective

The proposed CofeNet model could be trained in an end-to-end way by
backpropagation. We adopt the cross-entropy objective function that has been
used in many studies Tang et al. (2015); Wang et al. (2016, 2019).

Sequence Labeling Objective. Similar to sequence labeling tasks, we evaluate
the label of all words for each given training instance. Recall that our
objective is to predict the label of each word in the given instance. The
unregularized objective $L$ can be formulated as cross-entropy loss:

$L(\theta)=-\sum_{i}\sum_{j}l_{i}^{j}\log(\mathcal{P}_{i}^{j})$ (14)

For a given training instance, $l_{i}^{j}$ is the ground truth of label $j$
for word $i$. Correspondingly, $\mathcal{P}_{i}^{j}$ is the probability of
label $j$ for word $i$. $\theta$ is the parameter set.

##  4 Experiment

We now evaluate the proposed CofeNet on two public datasets (i.e., PolNeAR and
Riqua), and one proprietary dataset (i.e., PoliticsZH) against baselines. The
implementation details and parameter settings are presented in Appendix A. On
all datasets, we train the model with the training set, tune hyperparameters
on the validation set, and report performance on the test set.

###  4.1 Datasets

PolNeAR. Political News Attribution Relations Corpus (PolNeAR) Newell et al.
(2018) is a corpus of news articles in English, on political candidates during
US Presidential Election in November 2016. PolNeAR annotations are univocal,
meaning that each word has only one label (source, cue, content, or none). The
average number of tokens is $46$.

Riqua. RIch QUotation Annotations (Riqua) Papay and Padó (2020) provides
quotations, including interpersonal structure (speakers and addressees) for
English literary. This corpus comprises 11 works of 19th-century literature
that are manually annotated for direct and indirect quotations. Each instance,
typically a sentence, is annotated with its source, cue, and content. The
average number of tokens in this corpus is $129$, longer than PolNeAR.

PoliticsZH. Chinese Political Discourse (PoliticsZH) contains politics and
economics news collected from mainstream online media of China including
Xinhua Net111http://news.cn/. The news are in Chinese and the average length
of input is $69$ tokens, longer than PolNeAR but shorter than Riqua.

Table 1 presents the statistics of the three datasets. We observe that the
numbers of instances of PolNeAR and PoliticsZH are at the order of $10k$, and
the Riqua is at $1k$. The length of source and cue is less than $5$ tokens.
The length of content is greater than $10$, even $40$ tokens. Note that for
all three datasets, the length of content is much longer than source and cue.

###  4.2 Compared Methods

Table 1: The statistics of three datasets. “Ave. len.” refers to “Average length”. Dataset | Number of sentences | Ave. len. in tokens
---|---|---
Train |  Valid |  Test |  Source | Cue |  Content
PolNeAR | 17,397 | 1,925 | 1,814 | 3.27 | 1.88 | 14.49
Riqua | 1,604 | 208 | 105 | 1.38 | 1.08 | 20.65
PoliticsZH | 10,754 | 1,344 | 1,345 | 3.08 | 1.80 | 43.47
Table 2: The $F1$ and $J$(accard) of methods on PolNeAR, Riqua and PoliticsZH datasets. The results marked with ∗ are obtained by calling the CoreNLP toolkit package directly.  Dataset | Model | Source | Cue | Content
---|---|---|---|---
$F1$-E. |  $F1$-B. |  $J$ |  $F1$-E. |  $F1$-B. |  $J$ |  $F1$-E. |  $F1$-B. |  $J$
PolNeAR | Rule | 10.7 | 13.0 | 8.8 | 22.8 | 25.3 | 14.4 | 5.6 | 10.5 | 6.1
CoreNLP∗ | 13.9 | 21.3 | 11.1 | - | - | - | 17.5 | 18.7 | 12.8
CRF | 50.6 | 56.2 | 42.1 | 53.4 | 63.3 | 44.1 | 28.6 | 50.9 | 42.3
CNN | 52.7 | 65.9 | 45.1 | 58.4 | 67.8 | 49.4 | 16.2 | 60.6 | 30.2
GRU | 46.5 | 58.2 | 36.7 | 59.1 | 68.1 | 48.8 | 51.3 | 65.0 | 51.3
BiLSTM | 64.1 | 74.4 | 56.8 | 63.3 | 72.6 | 55.1 | 53.4 | 67.3 | 53.7
BERT | 81.1 | 86.2 | 74.8 | 74.0 | 81.1 | 67.4 | 68.9 | 78.7 | 70.0
CofeNet | 83.2 | 87.1 | 76.4 | 75.3 | 82.3 | 69.4 | 72.9 | 79.6 | 73.2
Riqua | Rule | 16.8 | 16.8 | 11.2 | 36.5 | 36.5 | 22.3 | 0.0 | 2.4 | 2.4
CoreNLP∗ | 22.8 | 22.8 | 17.9 | - | - | - | 63.8 | 63.8 | 46.9
CRF | 46.9 | 51.0 | 32.9 | 59.6 | 65.7 | 46.6 | 42.7 | 85.9 | 62.2
CNN | 52.7 | 59.1 | 39.6 | 85.2 | 85.2 | 74.2 | 45.2 | 95.4 | 58.5
GRU | 55.8 | 62.9 | 43.4 | 77.1 | 77.1 | 62.8 | 92.5 | 95.2 | 89.6
BiLSTM | 56.4 | 64.1 | 44.5 | 85.4 | 85.4 | 74.4 | 92.2 | 95.9 | 90.3
BERT | 74.5 | 77.9 | 62.4 | 88.9 | 88.9 | 80.0 | 94.3 | 96.6 | 92.9
CofeNet | 81.8 | 84.3 | 72.6 | 89.2 | 89.2 | 80.4 | 94.4 | 97.1 | 94.1
PoliticsZH | Rule | 78.8 | 79.3 | 66.8 | 80.3 | 81.2 | 69.7 | 0.4 | 7.0 | 3.7
CoreNLP∗ | 38.1 | 39.5 | 24.3 | - | - | - | 0.2 | 2.2 | 4.3
CRF | 81.6 | 84.0 | 72.2 | 80.0 | 80.4 | 68.5 | 45.7 | 49.1 | 66.3
CNN | 82.5 | 87.8 | 76.5 | 81.4 | 83.6 | 72.1 | 35.0 | 74.5 | 46.7
GRU | 85.5 | 88.3 | 78.1 | 82.1 | 84.6 | 73.6 | 65.7 | 79.8 | 71.5
BiLSTM | 87.5 | 91.3 | 83.3 | 86.2 | 88.6 | 79.9 | 70.3 | 81.8 | 74.9
BERT | 92.6 | 93.7 | 88.2 | 89.5 | 90.8 | 84.0 | 73.7 | 83.6 | 84.4
CofeNet | 93.7 | 94.4 | 89.8 | 90.3 | 91.1 | 85.4 | 78.0 | 86.9 | 88.7

To provide a comprehensive evaluation, we experiment on both deep learning
(i.e., CNN, GRU, (Bi)LSTM, BERT, and BERT-CRF), and traditional methods (i.e.,
Rule and CRF).

Rule. O’Keefe et al. (2012) uses rules including entity dictionary, reported
speech verbs, and special flag characters to extract components of quotations.

CoreNLP. CoreNLP Vu et al. (2018) contains quote extraction pipeline which
deterministically picks out source and content from a text while ignoring cue.

CRF. Lafferty et al. (2001) present CRF to label sequence by building
probabilistic models.

CNN. CNN LeCun et al. (1995), a simple and parallelized model, can be
independently adopted for sequence labeling tasks Xu et al. (2018).

(Bi)LSTM. LSTM Hochreiter and Schmidhuber (1997) is able to exhibit dynamic
temporal behavior due to its well-designed structure. We use it and its
variants, i.e., Bidirectional LSTM (BiLSTM).

GRU. GRU is a slightly more dramatic variation of LSTM Cho et al. (2014).

BERT(-CRF). BERT is designed to pre-train deep bidirectional representations
from unlabeled text by jointly conditioning on both left and right contexts
Devlin et al. (2019a).

###  4.3 Evaluation Metrics

The components of quotations are variable-length and complicated. As a result,
it requires more specific metrics. To this end, we evaluate the performance of
models using our proposed “Jaccard”, in addition to “Exact Match” and “Begin
Match”.

Exact Match. To measure the overall prediction at the instance level, we
propose Exact Match index to quantify whether the multi-label prediction
exactly matches the annotation. In the experiments, we use accuracy,
precision, recall, and $F1$ to evaluate the exact match performance.

Begin Match. Exact match is harsh, especially long text span. Generally, the
length of source and cue is short while the content is much longer. As a
result, exact match is hard for content. To this end, we use begin match to
evaluate only the beginning location for text span matching Lee and Sun
(2019).

Jaccard. For text span matching, an important index is a ratio of the
overlapping span over the total span. Thus we use “Jaccard” index to evaluate
the performance of model in this aspect. Given the groundtruth text span
$\mathcal{T}_{g}$ and its predicted text span $\mathcal{T}_{p}$, we can
calculate the Jaccard index $J$ through

$J=\frac{|\mathcal{T}_{p}\cap\mathcal{T}_{g}|}{|\mathcal{T}_{p}\cup\mathcal{T}_{g}|}.$
(15)

###  4.4 Main Results

Table 2 lists the $F1$ and $J$(accard) performance on the three datasets. In
this table, the best results are in boldface and the second-best are
underlined. We report results by exact match, begin match, and Jaccard, of all
models for the three components of quotations. Here, $F1$-E. and $F1$-B. refer
to the $F1$ based on exact match and begin match, respectively. The precision,
recall and accuracy are shown in the
page222https://thuwyq.github.io/docs/cofenet-detail-exp.pdf due to space
limitation. Our CofeNet model is listed in the last row of each dataset.

Table 3: The $F1$ and $J$ of methods on PolNeAR. B.L. and B.L.C. denote BiLSTM and BiLSTM+CRF respectively. Model | Source | Cue | Content
---|---|---|---
$F1$-E. |  $F1$-B. | $J$ |  $F1$-E. |  $F1$-B. | $J$ |  $F1$-E. |  $F1$-B. | $J$
CNN | 52.7 | 65.9 | 45.1 | 58.4 | 67.8 | 49.4 | 16.2 | 60.6 | 30.2
w. CRF | +8.3 | +4.1 | +8.0 | +4.3 | +2.2 | +3.6 | +25.8 | +1.9 | +19.3
w. Cofe | +9.4 | +3.9 | +8.1 | +3.7 | +2.1 | +3.2 | +31.8 | +3.1 | +21.9
GRU | 46.5 | 58.2 | 36.7 | 59.1 | 68.1 | 48.8 | 51.3 | 65.0 | 51.3
w. CRF | +19.3 | +13.7 | +19.3 | +6.2 | +3.9 | +6.8 | +3.8 | +0.8 | +6.2
w. Cofe | +20.5 | +14.6 | +19.7 | +7.2 | +4.6 | +7.5 | +6.9 | +1.9 | +6.2
LSTM | 46.1 | 56.4 | 35.7 | 58.6 | 67.5 | 47.9 | 50.4 | 65.5 | 50.8
w. CRF | +19.4 | +14.7 | +19.4 | +6.4 | +4.2 | +6.7 | +4.6 | +0.3 | +5.4
w. Cofe | +21.8 | +16.3 | +20.9 | +6.5 | +4.3 | +7.1 | +7.6 | +0.7 | +6.0
BiLSTM | 64.1 | 74.4 | 56.8 | 63.3 | 72.6 | 55.1 | 53.4 | 67.3 | 53.7
w. CRF | +5.5 | +1.3 | +4.5 | +3.4 | +1.2 | +2.6 | +5.6 | +2.1 | +6.6
w. Cofe | +7.1 | +3.7 | +7.0 | +3.7 | +1.3 | +3.4 | +8.8 | +3.4 | +9.1
BERT | 81.1 | 86.2 | 74.8 | 74.0 | 81.1 | 67.4 | 68.9 | 78.7 | 70.0
w. CRF | +1.1 | +0.3 | +0.8 | +0.9 | +0.9 | +1.5 | +2.1 | +0.2 | +2.8
w. CNN | -0.3 | +0.6 | +0.5 | +0.0 | +1.0 | +1.2 | +0.7 | +0.3 | +0.8
w. LSTM | +0.5 | +0.4 | +0.4 | -0.3 | 0.0 | +0.1 | +2.0 | +0.3 | +1.0
w. B.L. | -0.6 | -0.1 | -0.5 | -0.5 | +0.7 | +0.5 | +0.7 | -0.2 | -0.6
w. B.L.C. | +1.4 | +0.3 | +1.2 | +1.4 | +0.9 | +1.8 | +2.9 | +0.2 | +2.4
w. Cofe | +2.2 | +0.9 | +1.7 | +1.3 | +1.2 | +2.0 | +4.0 | +1.0 | +3.2

Table 2 shows that our CofeNet performs the best against all baselines. BERT
achieves the second-best, followed by other deep-learning-based models. Note
that due to the settled human-written rules, the performance of Rule and
CoreNLP is not stable. For source and cue, on PoliticsZH, the performance is
good due to more comprehensive rules. However, the rules on the other two
datasets do not fit the domain well. As a comparison, content is on the
opposite side. For content, the precision and recall of CoreNLP are $97.2$ and
$47.5$ on Riqua dataset, which is better than PolNeAR. PoliticsZH dataset
shows the worst performance. This is because CoreNLP uses quote marks to
extract quotations. The number of direct quotations (i.e., quoted content) on
PolNeAR and Riqua is large, while the PoliticsZH is small. This shows that the
rule-based methods cannot effectively identify indirect quotations.

The level of difficulty in extracting source, cue, and content is different.
As a result, the performances of source and cue are better than the difficult
content. This is expected because content is longer and complex in semantics.
For example, the content may contain another source, cue and content. We
design gate and attention mechanisms to fit those so that our model performs
well.

###  4.5 Comparison with CRF and BERT

Comparison with CRF. CRF is a popular approach to handle sequence labeling
problems, e.g., NER Ritter et al. (2011); Dong et al. (2016). We compare
CofeNet with CRF by changing the encoder, i.e., LSTM w. Cofe denotes the Cofe
using LSTM as text encoder. Recall that CofeNet specifically refers to the
model using BERT as encoder, marked as BERT w. Cofe in Table 3. To make the
comparison comprehensively and deeply, our comparisons between CRF and Cofe
are based on various mainstream models including CNN, GRU, LSTM, BiLSTM, and
BERT.

Table 3 details the comparison results on PolNeAR, and the results of the
other two datasets are reported in the
page333https://thuwyq.github.io/docs/cofenet-detail-exp.pdf. (i) Results show
that both Cofe and CRF perform better than basic models, and Cofe-based models
perform better than CRF-based models. The comparison results suggest that our
model architecture fits well with dependent sequence labeling tasks. As
designed, the enhanced cell is capable of building the dependency relations of
labels. (ii) Another interesting observation from the results is that if the
basic model (e.g., GRU) is simple, a larger improvement is achieved. On the
contrary, the improvement over BERT is relatively small. It makes sense
because the improvement is harder when the performance is already at a very
high level. (iii) We also note that CofeNet performs better than CRF on all
components of quotations.

Comparison with BERT. BERT based models are strong baselines for many tasks,
particularly when there are clear patterns. The performance of models could be
improved if we adopt a dependent encoding method based on BERT. To this end,
based on BERT, we use decoders including CNN, LSTM, BiLSTM, BiLSTM+CRF in
addition to CRF. The bottom area of Table 3 shows the results. Results show
that the improvements of decoders including CNN, LSTM and BiLSTM are not
significant than BiLSTM+CRF. Despite this, our CofeNet performs best. When
meeting simple text span (e.g., Cue), the improvement of our proposed CofeNet
is relatively small (1.3 point improvement, F1-Exact Match, on the Cue of
PolNeAR dataset). When it comes to complex text span (e.g., Content), our
model shows large improvement over BERT model (4.0 points improvement,
F1-Exact Match, on the Content of PolNeAR dataset).

From the comparisons, we demonstrate that our proposed CofeNet achieves the
state-of-the-art performance on quotation extraction. To reveal the essence of
CofeNet, we show the transition matrix of labels, the analysis on attention
mechanism, and the ablation study in the next sections.

###  4.6 Label Transition Matrix

(a) The transition matrix of groundtruth

(b) The margin between groundtruth and CofeNet

Figure 3: The transition matrix and the margin of groundtruth and our model on
PolNeAR.

The probability transition matrix of labels reflects the particular features
of source, cue and content. Thus we can use them to reveal the transition
mechanism of labels. To this end, we calculate the label transition matrix of
groundtruth, and the margin between groundtruth and CofeNet. Figure 3 depicts
the detail on PolNeAR. In all subfigures, the column denotes the previous
label and the row represents the current label. The value of Figure 3(a)
denotes the transition probability of true labels, and the value of Figure
3(b) is the margin between the true and the predicted. As the word saying,
“⟨Start⟩” denotes the location before the first word, “B-” and “I-” denote the
beginning and the inside of the source, cue and content, respectively. “O”
refers to the other words.

The transition matrix of groundtruth shown in Figure 3(a) reveals the
statistics of the PolNeAR dataset. Recall that the key for quotation
extraction is the recognition of the “Begin”. Hence, the margin of “Begin” is
the compass for evaluating the performance. We find that the maximum absolute
margin of “Begin” is $-0.03$, when the precious label is “B-source” and the
current label is “B-cue”. This is because the length of source is short, and
cue word often follows source word closely. This proves that our model
performs well even in difficult situations.

For BIO labeling scheme, the “I-source/cue/con-tent” exists except the
corresponding “B-*” exists. As a result, the transition value of “I-” could
show the recognition ability of the model for those patterns. Also, Figure
3(b) shows almost all margins of those values are zeros. This reveals that our
model could study those key patterns well.

###  4.7 Analysis on Attention Mechanism

Figure 4: The attention weights of one test data from PolNeAR.

In our design, the utilization of inflow information (e.g., former labels,
previous words, current word, and latter words) is the key for quotation
extraction. Figure 4 shows the weights from the attention layer of one test
instance in PolNeAR. To avoid the bias of a single case, we do a global
prediction for all texts in the test dataset of PolNeAR attached in Appendix
B. (i) The current word information has the largest weight, as expected. For
the prediction of “I-source/cue/content”, the former labels and former words
information are the most important roles after the current word. It indicates
that our model is capable of utilizing the former labels and sequence
information as we designed. (ii) Another interesting observation is that the
weights of the latter words’ information for predicting “B/I-content” are
about $0.1$, which are greater than the other weights in $\alpha_{l}$. As we
mentioned before, the length of content is longer than source and cue, so the
utilization of latter information improves the performance of long-span
extraction more efficiently.

Table 4: Ablation study on PolNeAR dataset. Model | Source | Cue | Content
---|---|---|---
$F1$-E. |  $F1$-B. | $J$ |  $F1$-E. |  $F1$-B. | $J$ |  $F1$-E. |  $F1$-B. | $J$
CofeNet | 83.2 | 87.1 | 76.4 | 75.3 | 82.3 | 69.4 | 72.9 | 79.6 | 73.2
w.o. g.m. | -1.0 | -0.6 | -0.9 | -0.2 | -0.2 | -1.0 | -0.8 | -0.3 | -1.2
w.o. a.m. | -0.9 | -1.4 | -1.5 | -0.2 | -1.0 | -1.3 | -1.2 | -0.8 | -1.3
w.o. f.l. | -2.4 | -0.8 | -1.5 | -1.9 | -0.5 | -1.5 | -2.5 | -0.3 | -2.7
w.o. f.w. | -0.9 | -0.6 | -1.1 | -0.1 | -0.3 | -0.9 | -1.3 | -0.8 | -1.1
w.o. c.w. | -2.0 | -1.4 | -2.0 | -1.1 | -1.0 | -1.6 | -1.4 | -1.2 | -1.2
w.o. l.w. | -1.0 | -0.9 | -1.2 | -0.4 | -0.4 | -0.6 | -1.7 | -1.4 | -1.0

###  4.8 Ablation Study

The CofeNet model uses gate mechanism $g.m.$ and attention mechanism $a.m.$
(see Section 3) to utilize information including former labels $f.l.$, former
words $f.w.$, current word $c.w.$, and latter words $l.w.$. To study the
effect of the two mechanisms and on the four information sources, we conduct
ablation experiments on PolNeAR dataset.

Table 4 reports the results of this ablation study. (i) As expected, all
mechanisms and information are useful for quotation extraction. For content,
the Jaccard performance degrades at least $1.0$ points after removing
mechanisms or input information, which is similar to source and cue. As a
comparison, the performance drop on $F1$-E. and $F1$-B. is significantly less
than $J$. It is because the structure of source and cue is simpler than
content. This phenomenon shows our CofeNet is particularly suitable for
extracting quotations with long and complicated structures. (ii) When removing
attention, larger drops on exact match are observed than removing gate. It
reveals that attention is effective for begin match while gate prefers exact
match. (iii) Further, we explore the performance of inflow information. The
“w.o. f.w.” on Table 4 shows that the former words’ information is not so
important for the prediction of cue because the cue is the shortest of all
three components. The former label and the current word, the latter words are
important for all of the components. It proves that the latter words’
information is key for the recognition of content. This fits with our
observations in Section 4.7.

##  5 Conclusion and Future Work

In this study, we design the CofeNet model for quotation extraction with
variable-length span and complicated structure. The key idea of CofeNet model
is to use gate and attention mechanisms to control the important information
including former labels, former words, current word and latter words at the
element and vector levels. Experiments show that the proposed model achieves
the state-of-the-art performance on two public datasets PolNeAR and Riqua and
one proprietary dataset PoliticsZH.

For quotation analysis, the extraction of quotation components is the first
step. In our study, we split a long text into short texts to ensure that one
instance contains one source, one cue and one content. Thus the recognition of
quotation triplets from long text (e.g., across instance) is one important
future work. Another important direction is to go deep into the nesting
phenomenon, which makes the recognition harder.

## Acknowledgments

This work was supported by the National Key R&D Program of China
(2020AAA0105200) and the National Science Foundation of China (NSFC No.
62106249, 61902382, 61972381).

## References

  * Angeli et al. (2015) Gabor Angeli, Melvin Jose Johnson Premkumar, and Christopher D. Manning. 2015.  Leveraging linguistic structure for open domain information extraction.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 344–354, Beijing, China. Association for Computational Linguistics.
  * Cho et al. (2014) Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014.  Learning phrase representations using RNN encoder–decoder for statistical machine translation.  In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1724–1734, Doha, Qatar. Association for Computational Linguistics.
  * Devlin et al. (2019a) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019a.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Devlin et al. (2019b) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019b.  BERT: pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers)_ , pages 4171–4186. Association for Computational Linguistics.
  * Dong et al. (2016) Chuanhai Dong, Jiajun Zhang, Chengqing Zong, Masanori Hattori, and Hui Di. 2016\.  Character-based LSTM-CRF with radical-level features for chinese named entity recognition.  In _Natural Language Understanding and Intelligent Applications \- 5th CCF Conference on Natural Language Processing and Chinese Computing, NLPCC 2016, and 24th International Conference on Computer Processing of Oriental Languages, ICCPOL 2016, Kunming, China, December 2-6, 2016, Proceedings_ , volume 10102 of _Lecture Notes in Computer Science_ , pages 239–250. Springer.
  * Elson and McKeown (2010) David K. Elson and Kathleen R. McKeown. 2010.  Automatic attribution of quoted speech in literary narrative.  In _Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010_. AAAI Press.
  * Exner and Nugues (2011) Peter Exner and Pierre Nugues. 2011.  Using semantic role labeling to extract events from wikipedia.  In _Proceedings of the Workhop on Detection, Representation, and Exploitation of Events in the Semantic Web (DeRiVE 2011), Bonn, Germany, October 23, 2011_ , volume 779 of _CEUR Workshop Proceedings_ , pages 38–47. CEUR-WS.org.
  * Fernandes et al. (2011) William Paulo Ducca Fernandes, Eduardo Motta, and Ruy Luiz Milidiú. 2011.  Quotation extraction for Portuguese.  In _Proceedings of the 8th Brazilian Symposium in Information and Human Language Technology_.
  * Gashteovski et al. (2017) Kiril Gashteovski, Rainer Gemulla, and Luciano Del Corro. 2017.  Minie: Minimizing facts in open information extraction.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, EMNLP 2017, Copenhagen, Denmark, September 9-11, 2017_ , pages 2630–2640. Association for Computational Linguistics.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long short-term memory.  _Neural Comput._ , 9(8):1735–1780.
  * Kim (2014) Yoon Kim. 2014.  Convolutional neural networks for sentence classification.  In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1746–1751, Doha, Qatar. Association for Computational Linguistics.
  * Kingma and Ba (2015) Diederik P. Kingma and Jimmy Ba. 2015.  Adam: A method for stochastic optimization.  In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_.
  * Krestel et al. (2008) Ralf Krestel, Sabine Bergler, and René Witte. 2008.  Minding the source: Automatic tagging of reported speech in newspaper articles.  In _Proceedings of the Sixth International Conference on Language Resources and Evaluation (LREC’08)_ , Marrakech, Morocco. European Language Resources Association (ELRA).
  * Lafferty et al. (2001) John D. Lafferty, Andrew McCallum, and Fernando C. N. Pereira. 2001.  Conditional random fields: Probabilistic models for segmenting and labeling sequence data.  In _Proceedings of the Eighteenth International Conference on Machine Learning (ICML 2001), Williams College, Williamstown, MA, USA, June 28 - July 1, 2001_ , pages 282–289. Morgan Kaufmann.
  * LeCun et al. (1995) Yann LeCun, Yoshua Bengio, et al. 1995.  Convolutional networks for images, speech, and time series.  _The handbook of brain theory and neural networks_ , 3361(10):1995.
  * Lee and Sun (2019) Grace E. Lee and Aixin Sun. 2019.  A study on agreement in PICO span annotations.  In _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2019, Paris, France, July 21-25, 2019_ , pages 1149–1152. ACM.
  * Lee et al. (2020) Kuan-Lin Lee, Yu-Chung Cheng, Pai-Lin Chen, and Hen-Hsen Huang. 2020.  Keeping their words: Direct and indirect chinese quote attribution from newspapers.  In _Companion of The 2020 Web Conference 2020, Taipei, Taiwan, April 20-24, 2020_ , pages 98–99. ACM / IW3C2.
  * Lin et al. (2019) Xi Lin, Yequan Wang, Xiaokui Xiao, Zengxiang Li, and Sourav S. Bhowmick. 2019.  Path travel time estimation using attribute-related hybrid trajectories network.  In _Proceedings of the 28th ACM International Conference on Information and Knowledge Management, CIKM 2019, Beijing, China, November 3-7, 2019_ , pages 1973–1982. ACM.
  * Meng et al. (2022) Xuying Meng, Yequan Wang, Runxin Ma, Haitong Luo, Xiang Li, and Yujun Zhang. 2022\.  Packet representation learning for traffic classification.  In _KDD ’22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 14 - 18, 2022_ , pages 3546–3554. ACM.
  * Newell et al. (2018) Edward Newell, Drew Margolin, and Derek Ruths. 2018.  An attribution relations corpus for political news.  In _Proceedings of the Eleventh International Conference on Language Resources and Evaluation, LREC 2018, Miyazaki, Japan, May 7-12, 2018_. European Language Resources Association (ELRA).
  * O’Keefe et al. (2012) Timothy O’Keefe, Silvia Pareti, James R. Curran, Irena Koprinska, and Matthew Honnibal. 2012.  A sequence labelling approach to quote attribution.  In _Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, EMNLP-CoNLL 2012, July 12-14, 2012, Jeju Island, Korea_ , pages 790–799. ACL.
  * O’Keefe et al. (2012) Timothy O’Keefe, Silvia Pareti, James R. Curran, Irena Koprinska, and Matthew Honnibal. 2012.  A sequence labelling approach to quote attribution.  In _Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning_ , pages 790–799, Jeju Island, Korea. Association for Computational Linguistics.
  * Papay and Padó (2020) Sean Papay and Sebastian Padó. 2020.  Riqua: A corpus of rich quotation annotation for english literary text.  In _Proceedings of The 12th Language Resources and Evaluation Conference, LREC 2020, Marseille, France, May 11-16, 2020_ , pages 835–841. European Language Resources Association.
  * Pareti et al. (2013) Silvia Pareti, Tim O’Keefe, Ioannis Konstas, James R. Curran, and Irena Koprinska. 2013.  Automatically detecting and attributing indirect quotations.  In _Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing_ , pages 989–999, Seattle, Washington, USA. Association for Computational Linguistics.
  * Pouliquen et al. (2007) Bruno Pouliquen, Ralf Steinberger, and Clive Best. 2007.  Automatic detection of quotations in multilingual news.  In _Proceedings of Recent Advances in Natural Language Processing_ , pages 487–492.
  * Ritter et al. (2011) Alan Ritter, Sam Clark, Mausam, and Oren Etzioni. 2011.  Named entity recognition in tweets: An experimental study.  In _Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing_ , pages 1524–1534, Edinburgh, Scotland, UK. Association for Computational Linguistics.
  * Schneider et al. (2010) Nathan Schneider, Rebecca Hwa, Philip Gianfortoni, Dipanjan Das, Michael Heilman, Alan W. Black, Frederick L. Crabbe, and Noah A. Smith. 2010.  Visualizing topical quotations over time to understand news discourse.
  * Socher et al. (2011) Richard Socher, Cliff Chiung-Yu Lin, Andrew Y. Ng, and Christopher D. Manning. 2011.  Parsing natural scenes and natural language with recursive neural networks.  In _Proceedings of the 28th International Conference on Machine Learning, ICML 2011, Bellevue, Washington, USA, June 28 - July 2, 2011_ , pages 129–136. Omnipress.
  * Tang et al. (2015) Duyu Tang, Bing Qin, and Ting Liu. 2015.  Document modeling with gated recurrent neural network for sentiment classification.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pages 1422–1432, Lisbon, Portugal. Association for Computational Linguistics.
  * Vu et al. (2018) Thanh Vu, Dat Quoc Nguyen, Dai Quoc Nguyen, Mark Dras, and Mark Johnson. 2018.  VnCoreNLP: A Vietnamese natural language processing toolkit.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Demonstrations_ , pages 56–60, New Orleans, Louisiana. Association for Computational Linguistics.
  * Wang et al. (2016) Yequan Wang, Minlie Huang, Xiaoyan Zhu, and Li Zhao. 2016.  Attention-based LSTM for aspect-level sentiment classification.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 606–615, Austin, Texas. Association for Computational Linguistics.
  * Wang et al. (2018) Yequan Wang, Aixin Sun, Jialong Han, Ying Liu, and Xiaoyan Zhu. 2018.  Sentiment analysis by capsules.  In _Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018, Lyon, France, April 23-27, 2018_ , pages 1165–1174. ACM.
  * Wang et al. (2019) Yequan Wang, Aixin Sun, Minlie Huang, and Xiaoyan Zhu. 2019.  Aspect-level sentiment analysis using as-capsules.  In _The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019_ , pages 2033–2044. ACM.
  * Xu et al. (2018) Hu Xu, Bing Liu, Lei Shu, and Philip S. Yu. 2018.  Double embeddings and CNN-based sequence labeling for aspect extraction.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 592–598, Melbourne, Australia. Association for Computational Linguistics.
  * Yang et al. (2016) Zichao Yang, Diyi Yang, Chris Dyer, Xiaodong He, Alex Smola, and Eduard Hovy. 2016\.  Hierarchical attention networks for document classification.  In _Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 1480–1489, San Diego, California. Association for Computational Linguistics.

## Appendix

##  Appendix A Implementation Details

We list the implementation details of CofeNet.

Table 5:  CofeNet-BERT experimental configuration on PolNeAR, Riqua and PoliticsZH datasets. The sampling ratio is the value selection ratio of the former label during training. The three values represent the proportions of truth label, predict label and random label.  Training hyperparameters |
---|---
Optimizer | Adam |
Learning rate except BERT | 1e-3 |
Learning rate of BERT | 5e-5 |
The hyperparameters of BERT |
Encoder layer | 12 |
Attention head | 12 |
Hidden size | 768 |
Intermediate size | 3,072 |
The hyperparameters of CofeNet |
Hidden size | 100 |
Label embedding | 100 |
Number of Former labels $k$ | 1 |
Number of Former words $n$ | 3 |
Number of Latter words $m$ | 3 |

Table 5 lists the same settings for the two public datasets (i.e., PolNeAR and
Riqua) and our proprietary dataset (i.e., PoliticsZH). The learning rate for
model parameters except BERT are $1e-3$, and $5e-5$ for BERT. We use typical
$12$-layers BERT (known as bert-base-uncased
444https://s3.amazonaws.com/models.huggingface.co/bert/bert-base-uncased-
pytorch_model.bin) as a basic encoder for the two English datasets. For the
Chinese dataset PoliticsZH, we use bert-base-chinese
555https://s3.amazonaws.com/models.huggingface.co/bert/bert-base-chinese-
pytorch_model.bin. The middle part of Table 5 shows the important
hyperparameters of BERT. There are other hyperparamters for CofeNet except
BERT related. The hidden sizes of word representation and label embedding are
100. The number of former labels, former words, and latter words is $1$, $3$,
and $3$, respectively. The different hyperparameter for CofeNet is the batch
size due to the GPU memory limitation. During training, we set the batch sizes
for PolNeAR, Riqua and PoliticsZH to $15$, $15$ and $16$, respectively.

(a) The weight $\alpha_{y}$ for former labels $r_{i}^{y}$

(b) The weight $\alpha_{f}$ for former words $r_{i}^{f}$

(c) The weight $\alpha_{c}$ for current word $r_{i}^{c}$

(d) The weight $\alpha_{l}$ for latter words $r_{i}^{l}$

Figure 5: The weights for hidden states on PolNeAR.

We use Adam Kingma and Ba (2015) as our optimization method. CofeNet is
implemented on Pytorch (version 1.2.0). NLTK is used to segment text. For BERT
model, we invoke the pytorch-transformers package (version 1.2.0). To ensure
the reliability of experimental results, we use the same transformer package
with the same initialization parameters in BERT, BERT-CRF and CofeNet.

##  Appendix B Global Analysis on Attention Mechanism

In our design, the utilization of inflow information is the key for quotation
extraction. Recall that the information includes the former labels, the
previous words, the current word and the latter words. Hence, we use the
attention to reveal the operating principle of the model. Figure 4 has shown
the weights from the attention layer of one individual case from test set of
PolNeAR dataset. To avoid the bias of a single case, we do a global prediction
for all texts in test set of PolNeAR shown in Figure 5. The observations from
Figure 5 are similar to that reported in Section 4.7, so we will not repeat
them.