Graph-based Neural Sentence Ordering

1 Introduction

Modeling the coherence in a paragraph or a long document is an important task, which contributes to both natural language generation and natural language understanding. Intuitively, it involves dealing with logic consistency and topic transitions. As a subtask, sentence ordering [Barzilay and Lapata, 2008] aims to reconstruct a coherent paragraph from an unordered set of sentences, namely paragraph. It has been shown to benefit several tasks, including retrieval-based question answering [Yu et al., 2018] and extractive summarization [Barzilay et al., 2002; Galanis et al., 2012], where erroneous sentence orderings may cause performance degradation. Therefore, it is of great importance to study sentence reordering.

Most conventional approaches [Lapata, 2003; Barzilay and Lapata, 2008; Guinaudeau and Strube, 2013] are rule-based or statistical ones, relying on handcrafted and sophisticated features. However, careful designs of these features require not only high labor costs but also rich linguistic knowledge. Thus, it is difficult to transfer these methods to new domains or languages. Inspired by the recent success of deep learning, neural networks have been introduced to this task, of which representative work includes window network [Li and Hovy, 2014], neural ranking model [Chen et al., 2016], hierarchical RNN-based models [Gong et al., 2016; Logeswaran et al., 2018], and deep attentive sentence ordering network (ATTOrderNet) [Cui et al., 2018]. Among these models, ATTOrderNet achieves the state-of-the-art performance with the aid of multi-head self-attention [Vaswani et al., 2017] to learn a relatively reliable paragraph representation for subsequent sentence ordering.

∗Equal contribution

†Corresponding author

Despite the best performance ATTOrderNet having exhibited so far, it still has two drawbacks. First, it is based on fully-connected graph representations. Although such representations enable the network to capture structural relationships across sentences, they also introduce lots of noise caused by any two semantically incoherent sentences. Second, the self-attention mechanism only exploits sentencelevel information and applies the same set of parameters to quantify the relationship between sentences. Obviously, it is not flexible enough to exploit extra information, such as entities, which have proved crucial in modeling text coherence [Barzilay and Lapata, 2008; Elsner and Charniak, 2011]. Thus, we believe that it is worthy of exploring a more suitable neural network for sentence ordering.

In this paper, we propose a novel graph-based neural sentence ordering model that adapts the recent graph recurrent network (GRN) [Zhang et al., 2018]. Inspired by Guinaudeau and Strube [2013], we first represent the input set of sentences (paragraph) as a Sentence-Entity graph, where each node represents either a sentence or an entity. Each entity node only connects to the sentence nodes that contain it, and two sentence nodes are linked if they contain the same entities. By doing so, our graph representations are able to model not only the semantic relevance between coherent sentences but also the co-occurrence between sentences and entities. Here we take the example in Figure 1 to illustrate the intuition behind our representations. We can see that the sentences sharing the same entities tend to be semantically close to each other: both the sentences S1 and S2 contain the entity "dad", and thus they are more coherent than S1 and S4. Compared with the fully-connected graph representations explored previously [Cui et al., 2018], our graph representations reduce the noise caused by the edges between irrelevant sentence nodes. Another advantage is that the useful entity information can be fully exploited when encoding the input paragraph. Based on sentence-entity graphs, we then adopt GRN [Zhang et al., 2018] to recurrently perform semantic transitions among connected nodes. In particular, we introduce an additional paragraph-level node to assemble semantic information of all nodes during this process, where the resulting paragraph-level representation is beneficial to information transitions among long-distance connected nodes. Moreover, since sentence nodes and entity nodes play different roles, we employ different parameters to distinguish their impacts. Finally, on the basis of the learned paragraph representation, a pointer network is used to produce the order of sentences.

The main contribution of our work lies in introducing GRN into sentence ordering, which can be classified into three sub aspects: 1) We propose a GRN-based encoder for sentence ordering. Our work is the first one to explore such an encoder for this task. Experimental results show that our model significantly outperforms the state-of-the-arts. 2) We refine vanilla GRN by modeling sentence nodes and entity nodes with different parameters. 3) Via plenty of experiments, we verify that entities are very useful in graph representations for sentence ordering.

2 Baseline: ATTOrderNet [Cui et al., 2018]

In this section, we give a brief introduction to ATTOrderNet, which achieves state-of-the-art performance and thus is chosen as the baseline of our work. As shown in Figure 2, ATTOrderNet consists of a Bi-LSTM sentence encoder, a paragraph encoder based on multi-head self-attention [Vaswani et al., 2017], and a pointer network based decoder [Vinyals et al., 2015b]. It takes a set of input sentences s = [so1 , . . . , soM ] with the order o = [o1, . . . , oM] as input and tries to recover the correct order o∗ = [o∗1 , . . . , o∗M ]. Here M denotes the number of the input sentences.

2.1 Sentence Encoding with Bi-LSTM

The Bi-LSTM sentence encoder takes a word embedding sequence (x1, . . . , xn) of each input sentence soi to produce its semantic representation. At the j-th step, the current states (-→hj and ←- hj) are generated from the previous hidden states (-→hj-1 and ←- hj+1) and the current word embedding xj as follows:

Finally, the sentence representation is obtained by concatenating the last states of the Bi-LSTM in both directions κ0oi =

2.2 Paragraph Encoding withMulti-Head Self-Attention Network

The paragraph encoder consists of several self-attention layers followed by an average pooling layer. Given the representations for the input sentences, the initial paragraph representation K0 is obtained by concatenating all sentence representations K0 = [κ0o1 , . . . , κ0oM ].

Next, the initial representation is fed into L self-attention layers for the update. In particular, the update for layer l is conducted by

where SelfAttenl represents the l-th network layer including multi-head self-attention and feed-forward networks. Finally, an average pooling layer is used to generate the final paragraph representation g from the output KL of the last selfattention layer g = 1M ∑Mi=1 κLi , where κLi is the vector representation of soi .

2.3 Decoding with Pointer Network

After obtaining the final paragraph representation g, an LSTM-based pointer network is used to predict the correct sentence order. Formally, the conditional probability of a predicted order o′ given input paragraph s can be formalized as

where v, W and U are model parameters. During training, the correct sentence order o∗ is known, so the sequence of decoder inputs is [κ0o∗1 , . . . , κ0o∗M ]. At test time, the decoder inputs correspond to the representations of sentences in the predicted order. For each step i, the decoder state is updated recurrently by taking the representation of the previous sentence κ0o′i-1 as the input:

where hdi is the decoder state, and hd0 is initialized as the final paragraph representation g. The first-step input and initial cell memory are zero vectors.

3 Our Model

In this section, we give a detailed description to our graphbased neural sentence ordering model, which consists of a sentence encoder, a graph neural network based paragraph encoder and a pointer network based decoder. For fair comparison, our sentence encoder and decoder are identical with those of ATTOrderNet. Due to the space limitation, we only describe our paragraph encoder here, which involves graph representations and graph encoding.

3.1 Sentence-Entity Graph

To take advantage of graph neural network for encoding paragraph, we need to represent input paragraphs as graphs. Different from the fully-connected graph representations explored previously [Cui et al., 2018], we follow Guinaudeau and Strube [2013] to incorporate entity information into our graphs, where it can serve as additional knowledge and be exploited to alleviate the noise caused by connecting incoherent sentences. To do this, we first consider all nouns of each input paragraph as entities. Since there can be numerous entities for very long paragraphs, we remove the entities that only appear once in the paragraph. As a result, we observe that a reasonable number of entities are generated for most paragraphs, and we will show more details in the experiments.

Then, with the identified entities, we transform the input paragraph into a sentence-entity graph. As shown in Figure 3 (b), our sentence-entity graphs are undirected and can be formalized as G = (V , ˆ V , E), where V , ˆ V and E represent the sentence-level nodes (such as vi), entity-level nodes (such as ˆ vj), and edges, respectively. Every sentence-entity graph has two types of edges, where an edge of the first type (SE) connects a sentence and an entity within it. Inspired by Guinaudeau and Strube [2013], we set the label for each SE-typed edge based on the syntactic role of the entity in the sentence, which can be either a subject(S), an object(O) or other(X). If an entity appears multiple times with different roles in the same sentence, we pick the highest-rank role according to S≻O≻X. On the other hand, every edge of the second type (SS) connects two sentences that have common entities, and these edges are unlabeled. As a result, sentence nodes are

t

Figure 4: GRN encoding for a sentence-entity graph. The original graph structure is only drawn on step t for being concise.

connected to other sentence nodes and entity nodes, while entity nodes are only connected to sentence nodes.

Figure 3 compares a fully-connected graph with a sentence-entity graph for the example in Figure 1. Within the fully-connected graph, there are several unnecessary edges that introduce noise, such as the one connecting S1 and S4. Intuitively, S1 and S4 do not form a coherent context. It is probably because they do not have common entities, especially given the situation that they both share entities with other sentences. In contrast, the sentence-entity graph does not take that edge, thus it does not suffer from the corresponding noise. Another problem with the fully-connected graph is that every node is directly linked to others, thus no information can be obtained based on the graph structure. Conversely, the structure of our sentence-entity graph can provide more discriminating information.

3.2 Encoding with GRN

To encode our graphs, we adopt GRN [Zhang et al., 2018] that has been shown effective in various kinds of graph encoding tasks. GRN is a kind of graph neural network [Scarselli et al., 2009] that parallelly and iteratively updates its node states with a message passing framework. For every message passing step t, the state update for each node vi mainly involves two steps: a message is first calculated from its directly connected neighbors, then the node state is updated by applying the gated operations of an LSTM step with the newly calculated message. Here we use GRU for updating node states instead of LSTM for better efficiency and fewer parameters.

Figure 4 shows the architecture of our GRN-based paragraph encoder, which adopts a paragraph-level state g in addition to the sentence states (such as κi, we follow Section 2.2 to use κ) and entity states (such as ϵj). We consider the sentence nodes and the entity nodes as different semantic units, since they contain different amount of information and have different types of neighbors. Therefore, we apply separate parameters and different gated operations to model their state transition processes, both following the two-step message-passing process. To update a sentence state κt-1 i at step t, messages from neighboring sentence states (such as κt-1 i′ ) and entity states (such as ϵt-1 j ) are calculated via weighted sum:

where Ni and ˜Ni denote the sets of neighboring sentences and entities of vi, respectively. We compute gates wi,j and ˜wi,j,l according to the edge label li,j (if any) and the two associated node states using a single-layer network with a sigmoid activation. Then, κt-1 i is updated by aggregating the messages (mti and ˜mti ) and the global state gt-1 via

Similarly, at step t, each entity state ϵt-1 j is updated based on its word embedding ej , its directly connected sentence nodes (such as κt-1 i ), and the global node gt-1:

Finally, the global state gt-1 is updated with the messages from both sentence and entity states via

parameters, and ˆM is the number of entities. In this way, each node absorbs richer contextual information through the iterative encoding process and captures the logical relationships with others. After recurrent state transitions of T iterations, we obtain the final paragraph state gT , which will be used to initialize the state hd0 of decoder (see Section 2.3).

4 Experiments

4.1 Setup

Datasets. We first compare our approach with previous methods on several benchmark datasets.

• NIPS Abstract. This dataset contains roughly 3K abstracts from NIPS papers from 2005 to 2015.
• ANN Abstract. It includes about 12K abstracts extracted from the papers in ACL Anthology Network (AAN) corpus [Radev et al., 2016].
• arXiv Abstract. We further consider another source of abstracts collected from arXiv. It consists of around 1.1M instances.
• SIND. It has 50K stories for the visual storytelling task 1 , which is in a different domain from the others. Here we use each story as a paragraph.

For data preprocessing, we first use NLTK to tokenize the sentences, and then adopt Stanford Parser 2 to extract nouns with syntactic roles for the edge labels (S, O or X). For each paragraph, we treat all nouns appearing more than once in it as entities. On average, each paragraph from NIPS Abstract, ANN Abstract, arXiv Abstract and SIND has 5.8, 4.5, 7.4 and 2.1 entities, respectively.

Settings. Our settings followCui et al., [2018] for fair comparison. We use 100-dimension Glove word embeddings 3 . The hidden size of LSTM is 300 for NIPS Abstract and 512 for the others. For our GRN encoders, The state sizes for sentence and entity nodes are set to 512 and 150, respectively. The size of edge embeddings is set to 50. Adadelta [Zeiler, 2012] is adopted as the optimizer with ϵ = 10-6 , ρ = 0.95 and initial learning rate 1.0. For regularization term, we employ L2 weight decay with coefficient 10-5 and dropout with probability 0.5. Batch size is 16 for training and beam search with size 64 is implemented for decoding.

Contrast Models. We compare our model (SE-Graph) with the existing state of the arts, including (1) LSTM+PtrNet [Gong et al., 2016], (2) Varient-LSTM+PtrNet [Logeswaran et al., 2018], and (3) ATTOrderNet [Cui et al., 2018]. Their major difference is how to encode paragraphs: LSTM+PtrNet uses a conventional LSTM to learn paragraph representation, Varient-LSTM+PtrNet is based on a set-to-sequence framework [Vinyals et al., 2015a], and ATTOrderNet adopts selfattention mechanism. Besides, in order to better study the different effects of entities, we also list the performances of two variants of our model: (1) F-Graph. Similar to ATTOrderNet, it uses a fully-connected graph to represent the input unordered paragraph, but adopts GRN rather than self-attention layers to encode the graphs. (2) S-Graph. It is a simplified version of our model by removing all entity nodes and their related edges from the original sentence-entity graphs. Correspondingly, all entity states (ϵs in Equations 5, 6, 7 and 8) are also removed.

1 http://visionandlanguage.net/VIST/

2 https://nlp.stanford.edu/software/lex-parser.shtml

3 https://nlp.stanford.edu/projects/glove/

Evaluation Metrics. Following previous work, we use the following three major metrics:

• Kendall's tau (): It ranges from -1 (the worst) to 1 (the best). Specifically, it is calculated as = 1- 2×(number of inversions)/(M2 ), where M denote the sequence length and number of inversions is the number of pairs in the predicted sequence with incorrect relative order.
• Accuracy (Acc): It measures the percentage of sentences whose absolute positions are correctly predicted. Compared with τ, it penalizes results that correctly preserve most relative orders but with a slight shift.
• Perfect Match Ratio (PMR): It considers each paragraph as a single unit and calculates the ratio of exactly matching orders, so no partial credit is given for any incorrect permutations.

Obviously, these three metrics evaluate the quality of sentence ordering from different aspects, and thus their combination can give us a comprehensive evaluation on this task.

4.2 Effect of Recurrent Step t

The recurrent step t is an important hyperparameter to our model, thus we choose the validation set of our largest dataset

(arXiv Abstract) to study its effectiveness. Figure 5 shows the results. We observe large improvements when increasing t from 0 to 3, showing the effectiveness of our framework. Nevertheless, the increase of t from 3 to 5 does not lead to further improvements while requiring more running time. Therefore, we set t=3 for all experiments thereafter.

4.3 Main Results

Table 1 reports the overall experimental results. Our model exhibits the best performance across datasets in different domains, demonstrating the effectiveness and robustness of our model. Moreover, we draw the following interesting conclusions. First, based on the same fully-connncted graph representations, F-Graph slightly outperforms ATTOrderNet on all datasets, even with fewer number of parameters and relatively fewer recurrent steps. This result proves the validity of applying GRN to encode paragraphs. Second, S-Graph shows better performance compared with F-Graph. This confirms the hypothesis that leveraging entity information can reduce the noise caused by connecting incoherent sentences. Third, SE-Graph outperforms S-Graph on all datasets across all metrics. It is because incorporating entities as extra information and modeling the co-occurrence between sentences and entities can further contribute to our neural graph model. Considering that SE-Graph has slightly more parameters than S-Graph, we make further analysis in Section 4.4 to show that the improvement given by SE-Graph is irrelevant to introducing new parameters.

Previous work has indicated that both the first and last sentences play special roles in a paragraph due to their crucial absolute positions, so we also report accuracies of our models on predicting them. Table 2 summarizes the experimental results on arXiv Abstract and SIND, where SE-Graph and its two variants also outperform ATTOrderNet, and particularly, SE-Graph reaches the best performance. Again, both results witness the advantages of our model.

4.4 Ablation Study

To investigate the impacts of entities and edges on our model, we adopt SE-Graph and S-Graph for further ablation studies, because both of them exploit entity information. Particularly, we continue to choose arXiv Abstract, the largest among our datasets, to conduct reliable analyses. The results are shown in Table 3, and we have the following observations.

First, shuffling edges significantly hurts the performances of both S-Graph and SE-Graph. The resulting PMR of SGraph (42.41) is still comparable with the PMR of F-Graph (42.50 as shown in Table 1). Intuitively, shuffling edges can introduce a lot of noise. These facts above indicate that fullyconnected graphs are also very noisy, especially because FGraph takes the same number of parameters as S-Graph. Therefore we can confirm our previous statement again: the entities can help reduce noise. Second, removing edge labels leads to less performance drops than removing or shuffling edges. It is likely because some labels can be automatically learned by our graph encoder. Nevertheless, the labels still provide useful information. Third, there are slight decreases for S-Graph and SE-Graph, if we only remove 10% entities. Removing entities is a way to simulate syntactic parsing noise, as our entities are obtained by the parsing results. This indicates the robustness of our model against potential parsing accuracy drops on certain domains, such as medical and chemistry. On the other hand, randomly removing 50% entities causes significant performance drops. As the model size still remains unchanged, this shows the importance of introducing entities. Particularly, the result of removing 50% entities for SE-Graph is slightly worse than original model of S-Graph, demonstrating that SE-Graph's improvement over S-Graph is not derived from simply introducing more parameters. Finally, share parameters illustrates the effect of making both GRNs (Equations 6 and 7) to share parameters. The result shows a drastic decrease on final performance, which is quite reasonable because entity nodes play fundamentally different roles from sentence nodes. Consequently, it is intuitive to model them separately.

5 Related work

Sentence Ordering. Previous work on sentence ordering mainly focused on the utilization of linguistic features via statistical models [Lapata, 2003; Barzilay and Lee, 2004; Barzilay and Lapata, 2005; Barzilay and Lapata, 2008; Elsner and Charniak, 2011; Guinaudeau and Strube, 2013]. Especially, the entity based models [Barzilay and Lapata, 2005; Barzilay and Lapata, 2008; Guinaudeau and Strube, 2013] have shown the effectiveness of exploiting entities for this task. Recently, the studies have evolved into neural network based models, such as window network [Li and Hovy, 2014], neural ranking model [Chen et al., 2016], hierarchical RNN-based models [Gong et al., 2016; Logeswaran et al., 2018], and ATTOrderNet [Cui et al., 2018]. Compared with these models, we combine the advantages of modeling entities and GRN, obtaining state-of-the-art performance. Even without entity information, our model variant based on fullyconnected graphs still shows better performance than the previous state-of-the-art model, indicating that GRN is a stronger alternative for this task.

Graph Neural Networks in NLP. Recently, graph neural networks have been shown successful in the NLP community, such as modeling semantic graphs [Beck et al., 2018; Song et al., 2018a; Song et al., 2019], dependency trees [Marcheggiani and Titov, 2017; Bastings et al., 2017; Song et al., 2018b], knowledge graphs [Wang et al., 2018] and even sentences [Zhang et al., 2018; Xu et al., 2018]. Particularly, Zhang et al., [2018] proposed GRN to represent raw sentences by building a graph structure of neighboring words and a sentence-level node. Their model exhibit satisfying performance on several classification and sequence labeling tasks. Our work is in line with theirs for the exploration of adopting GRN on NLP tasks. To our knowledge, our work is the first attempt to investigate GRN on solving a paragraph coherence problem.

6 Conclusion

We have presented a neural graph-based model for sentence ordering. Specifically, we first introduce sentence-entity graphs to model both the semantic relevance between coherent sentences and the co-occurrence between sentences and entities. Then, GRN is adopted on the built graphs to encode input sentences by performing semantic transitions among connected nodes. Compared with the previous state-of-theart model, ours is capable of reducing the noise brought by relationship modeling between incoherent sentences, but also fully leveraging entity information for paragraph encoding. Extensive experiments on several benchmark datasets prove the superiority of our model over the state-of-the-art and other baselines.

Acknowledgments

The authors were supported by Beijing Advanced Innovation Center for Language Resources, National Natural Science Foundation of China (No. 61672440), the Fundamental Research Funds for the Central Universities (Grant No. ZK1024), and Scientific Research Project of National Language Committee of China (Grant No. YB135-49).