# Pruned Graph Neural Network for Short Story Ordering

Melika Golestani  Zeinab Borhanifard  Farnaz Tahmasebian  Heshaam Faili
School of Electrical and Computer Engineering, College of Engineering,
University of Tehran, Tehran, Iran
<EMAIL_ADDRESS>
Alumni of Emory University, Atlanta, GA, USA
<EMAIL_ADDRESS>
###### Abstract

Text coherence is a fundamental problem in natural language generation and
understanding. Organizing sentences into an order that maximizes coherence is
known as sentence ordering. This paper is proposing a new approach based on
the graph neural network approach to encode a set of sentences and learn
orderings of short stories. We propose a new method for constructing sentence-
entity graphs of short stories to create the edges between sentences and
reduce noise in our graph by replacing the pronouns with their referring
entities. We improve the sentence ordering by introducing an aggregation
method based on majority voting of state-of-the-art methods and our proposed
one. Our approach employs a BERT-based model to learn semantic representations
of the sentences. The results demonstrate that the proposed method
significantly outperforms existing baselines on a corpus of short stories with
a new state-of-the-art performance in terms of Perfect Match Ratio (PMR) and
Kendall’s Tau ($\tau$) metrics. More precisely, our method increases PMR and
$\tau$ criteria by more than 5% and 4.3%, respectively. These outcomes
highlight the benefit of forming the edges between sentences based on their
cosine similarity. We also observe that replacing pronouns with their
referring entities effectively encodes sentences in sentence-entity graphs.

##  1 Introduction

Text coherence is a fundamental problem in natural language generation and
understanding. A coherent text adheres to a logical order of events which
facilitates better understanding. One of the subtasks in coherence modeling,
called sentence ordering, refers to organizing shuffled sentences into an
order that maximizes coherence (Barzilay and Lapata, 2008). Several downstream
applications benefit from this task to assemble sound and easy-to-understand
texts, such as extraction-based multi-document summarization (Barzilay and
Elhadad, 2002; Galanis et al., 2012; Nallapati et al., 2017; Logeswaran et
al., 2018), natural language generation (Reiter and Dale, 1997), retrieval-
based question answering (Liu et al., 2018; Yu et al., 2018), concept-to-text
generation (Konstas and Lapata, 2012), storytelling (Fan et al., 2019; Hu et
al., 2020; Zhu et al., 2020), opinion generation (Yanase et al., 2015),
conversational analysis (Zeng et al., 2018), image captioning (Anderson et
al., 2018), recipe generation (Chandu et al., 2019), and discourse coherence
(Elsner et al., 2007; Barzilay and Lapata, 2008; Guinaudeau and Strube, 2013).

In early studies, researchers modeled sentence structure using hand-crafted
linguistic features (Lapata, 2003; Barzilay and Lee, 2004; Elsner et al.,
2007; Barzilay and Lapata, 2008), nonetheless, these features are domain-
specific. Therefore recent studies employed deep learning techniques to solve
sentence ordering tasks (Golestani et al., 2021; Logeswaran et al., 2018; Gong
et al., 2016; Li and Jurafsky, 2017; Chen et al., 2016).

(Cui et al., 2018) used graph neural networks, called ATTOrderNet, to
accomplish this task. They used a self-attention mechanism combined with LSTMs
to encode input sentences. Their method could get a reliable representation of
the set of sentences regardless of their input order. In this representation,
an ordered sequence is generated using a pointer network. Since ATTOrderNet is
based on fully connected graph representations, it causes to build an
association among some irrelevant sentences, which introduces massive noise
into the network. Furthermore, since a self-attention mechanism only uses the
information at the sentence level, other potentially helpful information such
as entity information is missed.

To overcome these drawbacks, Yin et al. (2019) developed the Sentence-Entity
Graph (SE-Graph), which adds entities to the graph. While in the ATTOrderNet,
every node is a sentence representation, SE-Graph consists of two types of
nodes: sentence and entity111the entity should be common to at least two
sentences. Moreover, the edges come in two forms called SS and SE:

  * •

SS: this edge is between sentence nodes that share a common entity,

  * •

SE: this edge connects a sentence and an entity within the sentence labeled
with the entity’s role.

However, the introduced methods perform poorly for short story reordering
tasks. The SE-graph solution seems effective for long texts but not for short
stories. In this paper, we suggest modifications to the introduced graph
methods to improve the performance for short story reordering tasks. Some
issues arise in short stories: First, entities are often not repeated in
multiple sentences in a short story or text; instead, pronouns refer to an
entity. To address this problem, we improve the semantic graph by replacing
the pronouns with their corresponding entities. Another issue is a high
correlation between the sentences in a short story along with a high
commonality of entities across sentences, which leads us to end up with a
complete graph in most cases. Our solution is moving towards a Pruned Graph
(PG).

As with the ATTOrderNet and SE-Graph networks, the PG architecture consists of
three components:  1. Sentence encoder based on SBERT-WK model (Wang and Kuo,
2020),  2. Graph-based neural story encoder, and  3. Pointer network based
decoder.

With PG, the network nodes and SE edges are created based on SE-Graph, in a
way that the first and third components are the same. However, in the story
encoding phase, after generating the nodes and SE edges based on SE-Graph
method, the pruning phase is started on SS edges. This pruning process is
defined as follow: each sentence edged out its neighbors with the first and
second most cosine similarities (Rahutomo et al., 2012). This method
alleviates some problems of the previous two methods in the case of organizing
short story sentences. It is noteworthy that pronouns are replaced with
entities during pre-processing.

Finally, we present a method based on majority voting to combine our proposed
graph network-based method with the state-of-art methods to benefit from each.
Contributions of this study are as follows:

  1. 1.

Proposing a new method based on graph networks to order sentences of a short
stories corpus by:

    1. (a)

suggesting a new method for creating the edges between sentences,

    2. (b)

creating a better sentence-entity graph for short stories by replacing
pronouns in sentences with entities,

    3. (c)

Moreover, taking advantage of BERT-based sentence encoder.

  2. 2.

Using majority voting to combine sentence ordering methods.

##  2 Related Work

###  2.1 Sentence Ordering

In early studies on sentence ordering, the structure of the document is
modeled using hand-crafted linguistic features (Lapata, 2003; Barzilay and
Lee, 2004; Elsner et al., 2007; Barzilay and Lapata, 2008). Lapata (2003)
encoded sentences as vectors of linguistic features and used data to train a
probabilistic transition model. Barzilay and Lee (2004) developed the content
model in which topics in a specific domain are represented as states in an
HMM. Some other like Barzilay and Lapata (2008) utilize the entity-based
approach, which captures local coherence by modeling patterns of entity
distributions. Other approaches used a combination of the entity grid and the
content model Elsner et al. (2007) or employed syntactic features (Louis and
Nenkova, 2012) in order to improve the model.

However, linguistic features are incredibly domain-specific, so applying these
methods across different domains can decrease the performance. To overcome
this limitation, recent works have used deep learning-based approaches. Li and
Hovy (2014) proposes a neural model of distribution of sentence
representations based on recurrent neural networks. In (Li and Jurafsky,
2017), graph-based neural models are used to generate a domain-independent
neural model. Agrawal et al. (2016) introduced a method that involves
combining two points elicited from the unary and pairwise model of sentences.
Chen et al. (2016) used an LSTM encoder and beam search to construct a
pairwise model. Based on a pointer network that provides advantages in
capturing global coherence, Gong et al. (2016) developed an end-to-end
approach that predicts order of sentences. In another work, by applying an
encoder-decoder architecture based on LSTMs and attention mechanisms,
Logeswaran et al. (2018) suggested a pairwise model and established the gold
order by beam search. In (Pour et al., 2020), we presented a method that does
not require any training corpus due to not having a training phase. We also
developed a framework based on a sentence-level language model to solve the
sentence ordering problem in (Golestani et al., 2021). Moreover, in several
other studies, including (Cui et al., 2018) and (Yin et al., 2019), graph
neural networks are used to accomplish this task, as explained in the
following.

###  2.2 Graph Neural Networks in NLP

Graph neural networks (GNN) have shown to be effective in NLP applications,
including syntactic dependency trees (Marcheggiani and Titov, 2017), neural
machine translation (Beck et al., 2018), knowledge graphs (Wang et al., 2018),
semantic graphs Song et al. (2018), sequence-to-graph learning (Johnson,
2017), graph-to-sequence learning (Beck et al., 2018), sentence ordering (Yin
et al., 2019), and multi-document summarization (Christensen et al., 2013;
Yasunaga et al., 2017).

In particular, text classification is a common application of GNNs in natural
language processing. A GNN infers document labels based on the relationships
among documents or words (Hamilton et al., 2017). Christensen et al. (2013)
used a GNN in multi-document summarization. They create multi-document graphs
which determine pairwise ordering constraints of sentences based on the
discourse relationship between them. Kipf and Welling (2017) proposed Graph
Convolutional Networks (GCN), which is used in Yasunaga et al. (2017) to
generate sentence relation graphs. The final sentence embeddings indicate the
graph representation and are utilized as inputs to achieve satisfactory
results on multi-document summarization.

Another method is presented in Marcheggiani and Titov (2017) where a syntactic
GCN is developed with a CNN/RNN as sentence encoder. The GCN indicates
syntactic relations between words in a sentence. In a more recent work, Yin et
al. (2019) proposed a graph-based neural network for sentence ordering, in
which paragraphs are modeled as graphs where sentences and entities are the
nodes. The method showed improvement in evaluation metrics for sentence
ordering task. In this work, we explore the use of GRN for NLP tasks,
especially to perform sentence-ordering on a corpus of short stories.

##  3 Baselines

This section introduces ATTOrderNet (Cui et al., 2018) and SE-Graph (Yin et
al., 2019), which achieve state-of-the-art performances and serve as baseline
for our work.

###  3.1 ATTOrderNet

ATTOrderNet introduced in (Cui et al., 2018) is a model using graph neural
networks for sentence ordering. The model includes three components as
follows: a sentence encoder based on Bi-LSTM, a paragraph encoder based on
self-attention, and a pointer network-based decoder. In the sentence encoder,
sentences are translated into distributional representations with a word
embedding matrix. Then a sentence-level representation using the Bi-LSTM is
learned. An average pooling layer follows multiple self-attention layers in
the paragraph encoder. The paragraph encoder computes the attention scores for
all pairs of sentences at different positions in the paragraph. Therefore,
each sentence node is connected to all others where the encoder exploits
latent dependency relations among sentences independent of their input order.

Having an input set of sentences, the decoder aims to predict a coherent
order, identical to the original order. In this method, LSTM-based pointer
networks are used to predict the correct sentence ordering from the final
paragraph representation. Based on the sequence-to-sequence model, the pointer
network-based decoders predict the correct sentence sequence (Sutskever et
al., 2014). Specifically, input tokens are encoded using the pointer network
as summary vectors222The paragraph vector is nonetheless influenced by the
permutations of input sentences., and the next token vector is decoded
repeatedly. Finally, the output token sequence is derived from the output
token vector.

###  3.2 SE-Graph

SE-Graph, similarly to ATTOrderNet, consists of three components:  1. a
sentence encoder based on Bi-LSTM,  2. a paragraph encoder,  3. a pointer
network based decoder  Nevertheless, the difference between SE-Graph and
ATTOrderNet is only in the encoder paragraph component, described in the
following. In contrast to the fully connected graph representations explored
by ATTOrderNet, Yin et al. (2019) represented input paragraphs as sentence-
entity graphs. The SE-Graph includes two types of nodes: sentence and entity.
The entity should be common to at least two sentences to be considered as a
node of the graph. There are also two types of edges: SS edges that connect
sentence nodes with at least a common entity, and SE edges that link a
sentence with an entity within that and with a label of the entity’s role. SE
edges are labeled based on the syntactic role of the entity in the sentence,
such as a subject, an object, or other. When an entity appears multiple times
in a sentence with different roles, the role that has the highest rank is
considered. The highest rank of roles is the subject role; after that are the
object roles. SE-Graph framework utilizes a GRN-based paragraph encoder that
integrates the paragraph-level state along with the sentence-level state.

##  4 Methodology

In this section, first, the problem is formulated, second the dataset is
introduced and explains why this dataset is suitable for the sentence ordering
task. Then two methodologies are proposed. The first proposed method, called
Pruned Graph, is based on graph networks, and the second is based on the
majority voting to combine the outputs of three different models.

###  4.1 Problem Formulation

Consider $S(O)$ is a set of $n$ unordered sentences taken from a coherent
text:

$O={s_{1},s_{2},\dots,s_{n}}$,

$s(o_{1})>s(o_{2})>\dots>s(o_{n})$ (1)

The goal of sentence ordering is to find a permutation of sentences of O like
$S(o^{\prime})$,

$s({{o_{1}}^{\prime}})>s({{o_{2}}^{\prime}})>\ldots>s({{o_{n}}^{\prime}})$ (2)

that corresponds to the gold data arrangement. In other words, sentence
ordering aims to restore the original orders:

$s({o_{1}}^{*})>s({o_{2}}^{*})>\ldots>s({o_{n}}^{*})$ (3)

Where ${S({o^{*}})}$ represents the original or gold order. As a result a
correct output leads to ${S({o^{\prime}})=S({o^{*}})}$. Based on the above
definition and notions we propose our sentence ordering method.

###  4.2 Dataset

In this paper, we used a corpus of short stories, called ROCStories
(Mostafazadeh et al., 2016). It contains 98,162 commonsense stories, each with
exactly five sentences and an average word count of 50. Mostafazadeh et al.
(2017) created ROCStories corpus for a shared task called LSDSem, in which
models are supposed to predict the correct ending to short stories. 3,742 of
the stories have two options for the final sentence. It is worth noting that
humans generated all of the stories and options.

We can learn sequences of daily events from this dataset because it contains
some essential characteristics: The stories are rich with causal and temporal
relations among events, which makes this dataset a highly useful resource for
learning narrative structure across a wide range of events. The dataset
consists of a comprehensive collection of daily and non-fictional short
stories useful for modeling the coherence of a text (Mostafazadeh et al.,
2016).

Due to these features, ROCStories can be used to learn sequences of sentences.
Thus, the corpus is useful for organizing sentences in a text.

###  4.3 Pruned Graph Sentence Ordering (PG)

We propose a neural network based on the pruned graph for arranging the
sentences of short stories, a modified version of the ATTOrderNet (Cui et al.,
2018) and Sentence-Entity Graph (Yin et al., 2019). The PG method consists of
three components: sentence encoder, story encoder, and decoder. In order to be
a fair comparison, we used the same decoder as ATTOrderNet and SE-Graph. Due
to space limitations, here we explain our sentence encoder and our story
encoder. The Sentence encoder uses BERT encoding to encode sentences, while
Story encoder uses a graph neural network for encoding stories.

####  4.3.1 Sentence Encoder: SBERT-WK

We use fine-tuned pre-trained SBERT-WK model to encode sentences. BERT
contains several layers, each of which captures a different linguistic
characteristic. SBERT-WK found better sentence representations by fusing
information from different layers, Wang and Kuo (2020). The system
geometrically analyzes space using a deep contextual model that is trained on
both word-level and sentence-level, without further training. For each word in
a sentence, it determines a unified word representation then computes the
final sentence embedding vector based on the weighted average based on the
word importance of the word representations. Even with a small embedding size
of 768, SBERT-WK outperforms other methods by a significant margin on textual
similarity tasks (Wang and Kuo, 2020).

####  4.3.2 Story Encoder

To use graph neural networks for encoding stories, input stories should be
represented as graphs. We propose a pruned graph (PG) representation instead
of SE-Graph (Yin et al., 2019) for encoding short stories. Nodes in PG are
composed of sentences and entities. We replace pronouns with the entities they
refer to since entities are not often repeated from one sentence to another
during a short story333we use the Stanford’s tool (Lee et al., 2011), we will
go into more detail in the experiments. We consider all nouns of an input
story as entities at first. After that, we eliminate entities that do not
occur more than once in the story.

We can formalize our undirected pruned graphs as G = ($V_{s}$, $V_{e}$, E),
where $V_{s}$ indicates the sentence-level nodes, $V_{e}$ denotes the entity-
level nodes, and E represents edges. Edges in PG graphs are divided into two
types: SS and SE. The SS type links two sentences in a story that have the
highest or second-highest value of cosine similarity with each other; and the
SE type links a sentence with an entity within that with a label of the
entity’s role. Equation 4 shows the formula for calculating the cosine
similarity, where CosSim is cosine similarity and $Emb_{s_{i}}$ represents
vector of sentence i.

$CosSim(Emb_{s_{i}},Emb_{s_{j}})=\frac{Emb_{s_{i}}*Emb_{s_{j}}}{||Emb_{s_{i}}||||Emb_{s_{j}}||}$
(4)

SE edges are labeled according to the syntactic role of the entity in the
sentence, such as a subject, an object, or other. The role that has the
highest rank in an instance of an entity appearing multiple times is
considered. The ranking is as follows: subject role, object roles, and other.
The use of referring entities rather than pronouns is crucial.

Thus, sentence nodes are linked to both sentence and entity nodes, whereas an
entity node is not connected to any other entity nodes. For graph encoding, we
use GRN (Zhang et al., 2018), which has been found effective for various kinds
of graph encoding tasks. GRN used in our PG is the same as GRN in (Yin et al.,
2019), so we do not explain it.

###  4.4 Majority Voting

We combine the output of three methods to achieve better results in majority
voting. Since the stories in Rocstories all have five sentences, there are 20
possible pair sentence orderings as follow:

1. $s_{1}s_{2}$or  2. $s_{2}s_{1}$,  3. $s_{1}s_{3}$or  4. $s_{3}s_{1}$,  5. $s_{1}s_{4}$or  6. $s_{4}s_{1}$,  7. $s_{1}s_{5}$or  8. $s_{5}s_{1}$,  9. $s_{2}s_{3}$or  10. $s_{3}s_{2}$,  11. $s_{2}s_{4}$or  12. $s_{4}s_{2}$,  13. $s_{2}s_{5}$or  14. $s_{5}s_{2}$,  15. $s_{3}s_{4}$or  16. $s_{4}s_{3}$,  17. $s_{3}s_{5}$or  18. $s_{5}s_{3}$,  19. $s_{4}s_{5}$or  20. $s_{5}s_{4}$

Each suggested order for a story includes 10 of the above pair orderings,
either of the two pair orderings that have an "or" between them. Through
majority voting444For example, either $s_{1}s_{2}$ or $s_{2}s_{1}$ occurs, and
without a doubt, the co-occurrence of these is a vast and impossible
contradiction., we can combine the outputs of three separate methods to
generate a final order.

According to the number of occurrences in each of the three output
arrangements, we assign scores to each of the 20 possible pairings. As a
result, each of these possible pairings is scored between 0 and 3. 0 indicates
that this pairing does not appear in any of the three methods’ outputs, while
3 indicates that it appears in all of them. In the end, all pairs with a
greater score of 1 occur in the final orderings555Suppose the outputs of the
three methods for arranging $sentence_{1}$ ($s_{1}$) and $sentence_{2}$
($s_{2}$) are: Method 1: $s_{1}$$s_{2}$, Method 2: $s_{1}$$s_{2}$, and Method
3: $s_{2}$$s_{1}$. Therefore, the order $s_{1}$$s_{2}$ gets two points and the
order $s_{2}$$s_{1}$ gets one, so $s_{1}$$s_{2}$ applies to the final output..
Indeed, these are ten pairs666either of the two pair orderings that have an
”or” between them., and with the chosen pairs, the sentences of the story are
arranged uniquely.

In the following subsection, we are proving that majority voting is a valid
way to combine the outputs generated from three different methods for
arranging sentences. By using contradiction, we demonstrate the validity of
the majority voting method for combining three distinct methods of sentence
ordering to arrange two sentences.

Assuming the majority voting of three methods fails to create an unique order,
then two orders are possible, $s_{1}s_{2}$, and $s_{2}s_{1}$. In the first
case, $s_{1}$ appears before $s_{2}$ in two or more outputs of the methods,
and in the second case, $s_{2}$ appears before $s_{1}$ in two or more outputs.
Due to the three methods, this assumption causes a contradiction. To ordering
more than two sentences, it can be proved by induction.

##  5 Experiment

###  5.1 Evaluation Metrics

We use two standard metrics to evaluate the proposed model outputs that are
commonly used in previous work: Kendall’s tau and perfect match ratio, as
described below.

  * •

Kendall’s Tau ($\tau$)

Kendal’s Tau (Lapata, 2006) measures the quality of the output’s ordering,
computed as follows:

$\tau=1-\frac{(2*\\#\>of\>Inversions)}{N*(N-1)/2}$ (5)

Where $N$ represents the sequence length (i.e. the number of sentences of a
story, which is always equal to 5 for ROCStories), and the inversions return
the number of exchanges of the predicted order with the gold order for
reconstructing the correct order. $\tau$ is always between -1 and 1, where the
upper bound indicates that the predicted order is exactly the same as the gold
order. This metric correlates reliably with human judgments, according to
Lapata (2006).

  * •

Perfect Match Ratio (PMR)

According to this ratio, each story is considered as a single unit, and a
ratio of the number of correct orders is calculated. Therefore no penalties
are given for incorrect permutations (Gong et al., 2016). PMR is formulated
mathematically as follows:

$PMR={{1/N}{\sum_{1}^{N}{o_{i}^{\prime}}={o_{i}^{*}}}}$ (6)

where $o_{i}^{\prime}$ represents the output order and $o_{i}^{*}$ indicates
the gold order. $N$ specifies the sequence length. Since the length of all the
stories of ROCStories is equal to 5, $N$ in this study is always equal to 5.
PMR values range from 0 to 1, with a higher value indicating better
performance.

###  5.2 Contrast Models

We compare our PG to the state of the arts, namely the following:  1. LSTM +
PtrNet (Gong et al., 2016),  2. LSTM + Set2Seq (Logeswaran et al., 2018),  3.
ATTOrderNet (Cui et al., 2018),  4. SE-Graph (Yin et al., 2019),  5. HAN (Wang
and Wan, 2019),  6. SLM (Golestani et al., 2021),  7. RankTxNet ListMLE (Kumar
et al., 2020),  8. Enhancing PtrNet + Pairwise (Yin et al., 2020),  9. B-TSort
(Prabhumoye et al., 2020).  We teach LSTM + PtrNet, ATTOrderNet, SE-Graph, and
B-TSort on the ROCStories. The following is a brief description of the
mentioned methods, but We refer to Section 3 to explain ATTOrderNet and SE-
Graph.

Gong et al. (2016) proposes LSTM + PtrNet as a method for ordering sentences.
In this end-to-end method, pointer networks sort encrypted sentences after
decoding them by LSTM. Logeswaran et al. (2018) recommended LSTM + Set2Seq.
Their method encodes sentences, learns context representation by LSTM and
attention mechanisms, and utilizes a pointer network-based decoder to predict
sentences’ order. A transformer followed by an LSTM was added to the sentence
encoder in (Wang and Wan, 2019) to capture word clues and dependencies between
sentences; and so on, HAN is developed.

In (Golestani et al., 2021), we developed the Sentence-level Language Model
(SLM) for Sentence Ordering, consisting of a Sentence Encoder, a Story
Encoder, and a Sentence Organizer. The sentence encoder encodes sentences into
a vector using a fine-tuned pre-trained BERT. Hence, the embedding pays more
attention to the sentence’s crucial parts. Afterward, the story encoder uses a
decoder-encoder architecture to learn the sentence-level language model. The
learned vector from the hidden state is decoded, and this decoded vector is
utilized to indicate the following sentence’s candidate. Finally, the sentence
organizer uses the cosine similarity as the scoring function in order to sort
the sentences.

An attention-based ranking framework is presented in (Kumar et al., 2020) to
address the task. The model uses a bidirectional sentence encoder and a self-
attention-based transformer network to endcode paragraphs. In (Yin et al.,
2020), an enhancing pointer network based on two pairwise ordering prediction
modules, The FUTURE and HISTORY module, is employed to decode paragraphs.
Based on the candidate sentence, the FUTURE module predicts the relative
positions of other unordered sentences. Although, the HISTORY module
determines the coherency between the candidate and previously ordered
sentences. And lastly, Prabhumoye et al. (2020) designed B-TSort, a pairwise
ordering method, which is the current state-of-the-art method for sentence
ordering. This method benefits from BERT and graph-based networks. Based on
the relative pairwise ordering, graphs are constructed. Finally, the global
order is derived by a topological sort algorithm on the graph.

###  5.3 Setting

For a fair comparison, we follow Yin et al. (2019)’s settings. Nevertheless,
we use SBERT-WK’s 768- dimension vectors for sentence embedding. Furthermore,
the state sizes for sentence nodes are set to 768 in the GRN; The Batch size
is 32. In preprocessing, we use Stanford’s tool (Lee et al., 2011) to replace
pronouns with the referring entities.

###  5.4 Results

In this paper, we propose a new method based on graph networks for sentences
ordering short stories called Pruned Graph (PG). In order to achieve this, we
propose a new method for creating edges between sentences (by calculating the
cosine similarity between sentences), and we create a better sentence-entity
graph for short stories by replacing pronouns with the relevant entities.
Besides, to make a better comparison, we also teach the following cases:

  1. 1.

All nodes in the graph are of the sentence type, and the graph is fully
connected. In other words, we train ATTOrderNet on ROCStories777Cui et al.
(2018) did not train ATTOrderNet on the ROCStories dataset..

  2. 2.

The nodes include sentence and entity nodes, and each sentence’s node has the
edge over all other sentences’ nodes (semi fully connected SE-Graph888Entity
nodes are not connected to all nodes.).

  3. 3.

The network comprises sentence and entity nodes, and every two sentences with
at least one entity in common are connected (SE-Graph999We train SE-Graph on
ROCStories since Yin et al. (2019) did not.).

  4. 4.

Replacing pronouns with the relevant entities in SE-Graph (SE-Graph + Co-
referencing).

  5. 5.

Similar to PG, but each sentence is connected to a sentence with the highest
cosine similarity (semi $PG_{1}$).

  6. 6.

Similar to PG; however, each sentence is connected to three other sentences
based on their cosine similarity (semi $PG_{3}$).

  7. 7.

Pruned Graph with a Bi-LSTM based sentence encoder101010To demonstrate the
advantages of the PG’s BERT-based sentence encoder, this component is
considered exactly like the sentence encoder of SE-Graph and
ATTOrderNet.($PG^{\prime}$).

Note that in the above methods, where the graph also contains the nodes of the
entity, there is an edge between a sentence and an entity within
it111111Entity nodes can only have a link to sentence nodes.. Table 1 reports
the results of Pruned Graph (PG) and the above seven methods.

To get the training, validation, and testing datasets, we randomly split
ROCStories into 8:1:1. Therefore, the training set includes 78,529 stories,
the validation set contains 9,816 stories, and the testing set consists of
9,817 stories.

As shown in table 1, our PG beats all seven other methods. The results show
that all three of our innovations to the graph-based method have improved the
performance. Based on our analysis, the SBERT-WK sentence encoder is more
beneficial than the Bi-LSTM. Our experiences also find that using referring
entities instead of pronouns is helpful to create a more effective sentence-
entity graph. Additionally, it indicates connecting each sentence to two
others using cosine similarity is efficient to encode a story.

Method | $\tau$ | PMR
---|---|---
ATTOrderNet | 0.7364 | 0.4030
Fully connected SE-Graph | 0.7300 | 0.3927
SE-Graph | 0.7133 | 0.3687
SE-Graph + Co-ref | 0.7301 | 0.3981
PG+ 1 SS | 0.7534 | 0.4349
PG + 3 SS | 0.7379 | 0.4100
PG + Bi-LSTM-based sentence encoder | 0.7852 | 0.4769
Pruned Graph | 0.8220 | 0.5373
Table 1: Reporting the results of the proposed network called Pruned Graph in
comparison with the seven methods mentioned above

Table 2 reports the results of the proposed method of this paper in comparison
with competitors. When compared with ATTOrdeNet, PG improved the Tau by over
8.5% as well as PMR by 13.5%. Furthermore, the Tau is increased by 10.8% and
the PMR by more than 16.8% compared to SE-Graph. PG outperforms the state-of-
the-art on ROCStories with a more tthan 1.8% increase in pmr and a more than
3.9% improvement in $\tau$.

Model | $\tau$ | PMR
---|---|---
LSTM+PtrNet | 0.7230 | 0.3647
LSTM+Set2Seq | 0.7112 | 0.3581
ATTOrderNet | 0.7364 | 0.4030
SE-Graph | 0.7133 | 0.3687
HAN | 0.7322 | 0.3962
SLM | 0.7547 | 0.4064
RankTxNet ListMLE | 0.7602 | 0.3602
Enhancing PtrNet + Pairwise | 0.7681 | 0.4600
B-TSort | 0.8039 | 0.4980
Our Pruned Graph | 0.8220 | 0.5373
Table 2: Results of our PG compared to baselines and competitors

Finally, we merged the outputs of the three methods using the majority voting
method, including Enhancing PtrNet, B-TSort, and Our Pruned Graph. Table 3
shows the results of the combination, which improves the PMR and $\tau$
criteria by more than 5% and 4.3% on ROCStories, respectively.

Method | $\tau$ | PMR
---|---|---
combination | 0.8470 | 0.5488
Table 3: Results of combining of Enhancing PtrNet, B-TSort, and Pruned Graph
using majority voting

##  6 conclusion

This paper introduced a graph-based neural framework to solve the sentence
ordering task. This framework takes a set of randomly ordered sentences and
outputs a coherent order of the sentences. The results demonstrate that SBERT-
WK is a reliable model to encode sentences. Our analysis examined how the
method is affected by using a Bi-LSTM model in the sentence encoder component.
In addition, we found that replacing pronouns with their referring entities
supplies a more informative sentence-entity graph to encode a story. The
experimental results indicate that our proposed graph-based neural model
significantly outperforms on ROCStories dataset. Furthermore, we recommend a
method for combining different methods of sentence ordering based on majority
voting that achieves state-of-the-art performance in PMR and $\tau$ scores. In
future, we plan to apply the trained model on sentence ordering task to tackle
other tasks including text generation, dialogue generation, text completion,
retrieval-based QA, and extractive text summarization.

## References

  * Agrawal et al. (2016) Harsh Agrawal, Arjun Chandrasekaran, Dhruv Batra, Devi Parikh, and Mohit Bansal. 2016.  Sort story: Sorting jumbled images and captions into stories.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 925–931, Austin, Texas. Association for Computational Linguistics.
  * Anderson et al. (2018) Peter Anderson, Xiaodong He, Chris Buehler, Damien Teney, Mark Johnson, Stephen Gould, and Lei Zhang. 2018.  Bottom-up and top-down attention for image captioning and visual question answering.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 6077–6086.
  * Barzilay and Elhadad (2002) Regina Barzilay and Noemie Elhadad. 2002.  Inferring strategies for sentence ordering in multidocument news summarization.  _Journal of Artificial Intelligence Research_ , 17:35–55.
  * Barzilay and Lapata (2008) Regina Barzilay and Mirella Lapata. 2008.  Modeling local coherence: An entity-based approach.  _Computational Linguistics_ , 34(1):1–34.
  * Barzilay and Lee (2004) Regina Barzilay and Lillian Lee. 2004.  Catching the drift: Probabilistic content models, with applications to generation and summarization.  In _Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics: HLT-NAACL 2004_ , pages 113–120.
  * Beck et al. (2018) Daniel Beck, Gholamreza Haffari, and Trevor Cohn. 2018.  Graph-to-sequence learning using gated graph neural networks.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 273–283, Melbourne, Australia. Association for Computational Linguistics.
  * Chandu et al. (2019) Khyathi Chandu, Eric Nyberg, and Alan W Black. 2019.  Storyboarding of recipes: grounded contextual generation.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 6040–6046.
  * Chen et al. (2016) Xinchi Chen, Xipeng Qiu, and Xuanjing Huang. 2016.  Neural sentence ordering.  _arXiv preprint arXiv:1607.06952_.
  * Christensen et al. (2013) Janara Christensen, Mausam, Stephen Soderland, and Oren Etzioni. 2013.  Towards coherent multi-document summarization.  In _Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 1163–1173, Atlanta, Georgia. Association for Computational Linguistics.
  * Cui et al. (2018) Baiyun Cui, Yingming Li, Ming Chen, and Zhongfei Zhang. 2018.  Deep attentive sentence ordering network.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processinga_ , pages 4340–4349.
  * Elsner et al. (2007) Micha Elsner, Joseph Austerweil, and Eugene Charniak. 2007.  A unified local and global model for discourse coherence.  In _Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference_ , pages 436–443.
  * Fan et al. (2019) Angela Fan, Mike Lewis, and Yann Dauphin. 2019.  Strategies for structuring story generation.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 2650–2660, Florence, Italy. Association for Computational Linguistics.
  * Galanis et al. (2012) Dimitrios Galanis, Gerasimos Lampouras, and Ion Androutsopoulos. 2012.  Extractive multi-document summarization with integer linear programming and support vector regression.  In _Proceedings of COLING 2012_ , pages 911–926.
  * Golestani et al. (2021) Melika Golestani, Seyedeh Zahra Razavi, Zeinab Borhanifard, Farnaz Tahmasebian, and Hesham Faili. 2021.  Using bert encoding and sentence-level language model for sentence ordering.  In _Text, Speech, and Dialogue_ , pages 318–330, Cham. Springer International Publishing.
  * Gong et al. (2016) Jingjing Gong, Xinchi Chen, Xipeng Qiu, and Xuanjing Huang. 2016.  End-to-end neural sentence ordering using pointer network.  _arXiv preprint arXiv:1611.04953_.
  * Guinaudeau and Strube (2013) Camille Guinaudeau and Michael Strube. 2013.  Graph-based local coherence modeling.  In _Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 93–103.
  * Hamilton et al. (2017) William L. Hamilton, Rex Ying, and Jure Leskovec. 2017.  Inductive representation learning on large graphs.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , NIPS’17, page 1025–1035, Red Hook, NY, USA. Curran Associates Inc.
  * Hu et al. (2020) Junjie Hu, Yu Cheng, Zhe Gan, Jingjing Liu, Jianfeng Gao, and Graham Neubig. 2020\.  What makes a good story? designing composite rewards for visual storytelling.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 7969–7976.
  * Johnson (2017) D. Johnson. 2017.  Learning graphical state transitions.  In _ICLR_.
  * Kipf and Welling (2017) Thomas N Kipf and Max Welling. 2017.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_.
  * Konstas and Lapata (2012) Ioannis Konstas and Mirella Lapata. 2012.  Concept-to-text generation via discriminative reranking.  In _Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 369–378.
  * Kumar et al. (2020) Pawan Kumar, Dhanajit Brahma, Harish Karnick, and Piyush Rai. 2020.  Deep attentive ranking networks for learning to order sentences.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 8115–8122.
  * Lapata (2003) Mirella Lapata. 2003.  Probabilistic text structuring: Experiments with sentence ordering.  In _Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics_ , pages 545–552.
  * Lapata (2006) Mirella Lapata. 2006.  Automatic evaluation of information ordering: Kendall’s tau.  _Computational Linguistics_ , 32(4):471–484.
  * Lee et al. (2011) Heeyoung Lee, Yves Peirsman, Angel Chang, Nathanael Chambers, Mihai Surdeanu, and Dan Jurafsky. 2011.  Stanford’s multi-pass sieve coreference resolution system at the conll-2011 shared task.  In _Proceedings of the 15th conference on computational natural language learning: Shared task_ , pages 28–34. Association for Computational Linguistics.
  * Li and Hovy (2014) Jiwei Li and Eduard Hovy. 2014.  A model of coherence based on distributed sentence representation.  In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 2039–2048.
  * Li and Jurafsky (2017) Jiwei Li and Dan Jurafsky. 2017.  Neural net models of open-domain discourse coherence.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 198–209, Copenhagen, Denmark. Association for Computational Linguistics.
  * Liu et al. (2018) Xiaodong Liu, Yelong Shen, Kevin Duh, and Jianfeng Gao. 2018.  Stochastic answer networks for machine reading comprehension.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1694–1704, Melbourne, Australia. Association for Computational Linguistics.
  * Logeswaran et al. (2018) Lajanugen Logeswaran, Honglak Lee, and Dragomir Radev. 2018.  Sentence ordering and coherence modeling using recurrent neural networks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32.
  * Louis and Nenkova (2012) Annie Louis and Ani Nenkova. 2012.  A coherence model based on syntactic patterns.  In _Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning_ , pages 1157–1168.
  * Marcheggiani and Titov (2017) Diego Marcheggiani and Ivan Titov. 2017.  Encoding sentences with graph convolutional networks for semantic role labeling.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 1506–1515, Copenhagen, Denmark. Association for Computational Linguistics.
  * Mostafazadeh et al. (2016) Nasrin Mostafazadeh, Nathanael Chambers, Xiaodong He, Devi Parikh, Dhruv Batra, Lucy Vanderwende, Pushmeet Kohli, and James Allen. 2016.  A corpus and cloze evaluation for deeper understanding of commonsense stories.  In _Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 839–849, San Diego, California. Association for Computational Linguistics.
  * Mostafazadeh et al. (2017) Nasrin Mostafazadeh, Michael Roth, Annie Louis, Nathanael Chambers, and James Allen. 2017.  LSDSem 2017 shared task: The story cloze test.  In _Proceedings of the 2nd Workshop on Linking Models of Lexical, Sentential and Discourse-level Semantics_ , pages 46–51, Valencia, Spain. Association for Computational Linguistics.
  * Nallapati et al. (2017) Ramesh Nallapati, Feifei Zhai, and Bowen Zhou. 2017.  Summarunner: A recurrent neural network based sequence model for extractive summarization of documents.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 31.
  * Pour et al. (2020) Melika Golestani Pour, Seyedeh Zahra Razavi, and Heshaam Faili. 2020.  A new sentence ordering method using bert pretrained model.  In _2020 11th International Conference on Information and Knowledge Technology (IKT)_ , pages 132–138. IEEE.
  * Prabhumoye et al. (2020) Shrimai Prabhumoye, Ruslan Salakhutdinov, and Alan W Black. 2020.  Topological sort for sentence ordering.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 2783–2792, Online. Association for Computational Linguistics.
  * Rahutomo et al. (2012) Faisal Rahutomo, Teruaki Kitasuka, and Masayoshi Aritsugi. 2012.  Semantic cosine similarity.  In _The 7th International Student Conference on Advanced Science and Technology ICAST_ , volume 4, page 1.
  * Reiter and Dale (1997) Ehud Reiter and Robert Dale. 1997.  Building applied natural language generation systems.  _Natural Language Engineering_ , 3(1):57–87.
  * Song et al. (2018) Linfeng Song, Yue Zhang, Zhiguo Wang, and Daniel Gildea. 2018.  N-ary relation extraction using graph-state LSTM.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 2226–2235, Brussels, Belgium. Association for Computational Linguistics.
  * Sutskever et al. (2014) Ilya Sutskever, Oriol Vinyals, and Quoc V. Le. 2014.  Sequence to sequence learning with neural networks.  In _Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2_ , NIPS’14, page 3104–3112, Cambridge, MA, USA. MIT Press.
  * Wang and Kuo (2020) Bin Wang and C-C Jay Kuo. 2020.  Sbert-wk: A sentence embedding method by dissecting bert-based word models.  _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , 28:2146–2157.
  * Wang and Wan (2019) Tianming Wang and Xiaojun Wan. 2019.  Hierarchical attention networks for sentence ordering.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 7184–7191.
  * Wang et al. (2018) Zhichun Wang, Qingsong Lv, Xiaohan Lan, and Yu Zhang. 2018.  Cross-lingual knowledge graph alignment via graph convolutional networks.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 349–357, Brussels, Belgium. Association for Computational Linguistics.
  * Yanase et al. (2015) Toshihiko Yanase, Toshinori Miyoshi, Kohsuke Yanai, Misa Sato, Makoto Iwayama, Yoshiki Niwa, Paul Reisert, and Kentaro Inui. 2015.  Learning sentence ordering for opinion generation of debate.  In _Proceedings of the 2nd Workshop on Argumentation Mining_ , pages 94–103.
  * Yasunaga et al. (2017) Michihiro Yasunaga, Rui Zhang, Kshitijh Meelu, Ayush Pareek, Krishnan Srinivasan, and Dragomir Radev. 2017.  Graph-based neural multi-document summarization.  In _Proceedings of the 21st Conference on Computational Natural Language Learning (CoNLL 2017)_ , pages 452–462, Vancouver, Canada. Association for Computational Linguistics.
  * Yin et al. (2020) Yongjing Yin, Fandong Meng, Jinsong Su, Yubin Ge, Lingeng Song, Jie Zhou, and Jiebo Luo. 2020.  Enhancing pointer network for sentence ordering with pairwise ordering predictions.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 9482–9489.
  * Yin et al. (2019) Yongjing Yin, Linfeng Song, Jinsong Su, Jiali Zeng, Chulun Zhou, and Jiebo Luo. 2019\.  Graph-based neural sentence ordering.  In _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19_ , pages 5387–5393. International Joint Conferences on Artificial Intelligence Organization.
  * Yu et al. (2018) Adams Wei Yu, David Dohan, Minh-Thang Luong, Rui Zhao, Kai Chen, Mohammad Norouzi, and Quoc V Le. 2018.  Qanet: Combining local convolution with global self-attention for reading comprehension.  _arXiv preprint arXiv:1804.09541_.
  * Zeng et al. (2018) Xingshan Zeng, Jing Li, Lu Wang, Nicholas Beauchamp, Sarah Shugars, and Kam-Fai Wong. 2018.  Microblog conversation recommendation via joint modeling of topics and discourse.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 375–385.
  * Zhang et al. (2018) Yue Zhang, Qi Liu, and Linfeng Song. 2018.  Sentence-state LSTM for text representation.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 317–327, Melbourne, Australia. Association for Computational Linguistics.
  * Zhu et al. (2020) Yutao Zhu, Ruihua Song, Zhicheng Dou, Jian-Yun Nie, and Jin Zhou. 2020.  ScriptWriter: Narrative-guided script generation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 8647–8657, Online. Association for Computational Linguistics.