Constructing Narrative Event Evolutionary Graph for Script Event Prediction

1 Introduction

Understanding events described in text is crucial to many artificial intelligence (AI) applications, such as discourse understanding, intention recognition and dialog generation. Script event prediction is the most challenging task in this line of work. This task was first proposed by Chambers and Jurafsky [2008], who defined it as giving an existing event context, one needs to choose the most reasonable subsequent event from a candidate list (as shown in Figure 1).

Previous studies built prediction models either based on event pairs [Chambers and Jurafsky, 2008; Granroth-Wilding and Clark, 2016] or event chains [Wang et al., 2017]. Although success in using event pairs and chains, rich connections among events are not fully explored. To better model event connections, we propose to solve the problem of script event prediction based on event graph structure and infer the correct subsequent event based on network embedding.

∗Corresponding author: tliu@ir.hit.edu.cn

Figure 2(a) gives an example to motive our idea of using more broader event connections (say graph structure). Given an event context A(enter), B(order), C(serve), we need to choose the most reasonable subsequent event from the candidate list D(eat) and E(talk), where D(eat) is the correct answer and E(talk) is a randomly selected candidate event that occurs frequently in various scenarios. Pair-based and chainbased models trained on event chains datasets (as shown in Figure 2(b)) are very likely to choose the wrong answer E, as training data show that C and E have a stronger relation than C and D. As shown in Figure 2(c), by constructing an event graph based on training event chains, context events B, C and the candidate event D compose a strongly connected component, which indicates that D is a more reasonable subsequent event, given context events A, B, C.

Abstract event evolutionary principles and patterns are valuable commonsense knowledge, which is crucial for understanding narrative text, human behavior and social development. We use the notion of event evolutionary graph (EEG) to denote the knowledge base that stores this kind of knowledge. Structurally, EEG is a directed cyclic graph, whose nodes are events and edges stand for the relations between events, e.g. temporal and causal relations. In this paper, we construct an event evolutionary graph based on narrative event chains, which is called narrative event evolutionary graph (NEEG). Having a NEEG in hand, another challenging problem is how to infer the subsequent event on the graph. A possible solution is to learn event representations based on network embedding.

Duvenaud et al. [2015] introduced a convolutional neural network that could operate directly on graphs, which could be used for end-to-end learning of prediction tasks whose inputs are graphs of arbitrary size and shape. Kipf and Welling [2016] presented a scalable approach for semi-supervised learning on graphs that was based on an efficient variant of convolutional neural networks. They chose a localized firstorder approximation of spectral graph convolutions as the convolutional architecture, to scale linearly in the number of graph edges and learn hidden layer representations that encode both local graph structure and features of nodes. However, their models require the adjacency matrix to be symmetric and can only operate on undirected graphs. Gori et al. [2005] proposed graph neural network (GNN), which extended recursive neural networks and could be applied on most of the practically useful kinds of graphs, including directed, undirected, labeled and cyclic graphs. However, the learning algorithm in their model required running the propagation to convergence, which could have trouble propagating information across a long range in a graph. To remedy this, Li et al. [2015] introduced modern optimization techniques of gated recurrent units to GNN. Nevertheless, their models can only operate on small graphs. In this paper, we further extend the work of Li et al. [2015] by proposing a scaled graph neural network (SGNN), which is feasible to large-scale graphs. We borrow the idea of divide and conquer in the training process that instead of computing the representations on the whole graph, SGNN processes only the concerned nodes each time. By comparing between context event representations and candidate event representations learned from SGNN, we can choose the correct subsequent event.

This paper makes the following two key contributions:

• We are among the first to propose constructing event graph instead of event pairs and event chains for the task of script event prediction.
• We present a scaled graph neural network, which can model event interactions on large-scale dense directed graphs and learn better event representations for prediction.

Empirical results on widely used New York Times corpus show that our model achieves the best performance compared to state-of-the-art baseline methods, by using standard multiple choice narrative cloze (MCNC) evaluation. The data and code are released at https://github.com/eecrazy/ ConstructingNEEG IJCAI 2018.

2 Model

As shown in Figure 3, our model consists of two steps. The first step is to construct an event evolutionary graph based on narrative event chains. Second, we present a scaled graph neural network to solve the inference problem on the constructed event graph.

2.1 Narrative Event Evolutionary Graph Construction

NEEG construction consists of two steps: (1) we extract narrative event chains from newswire corpus; (2) construct NEEG based on the extracted event chains.

In order to compare with previous work, we adopt the same news corpus and event chains extraction methods as [Granroth-Wilding and Clark, 2016]. We extract a set of narrative event chains S = {s1, s2, s3, ..., sN}, where si = {T, e1, e2, e3, ..., em}. For example, si can be {T = customer, walk(T, restaurant, -), seat(T, -, -), read(T, menu, -), order(T, food, -), serve(waiter, food, T), eat(T, food, fork)}. T is the protagonist entity shared by all the events in this chain. ei is an event that consists of four components {p(a0, a1, a2)}, where p is the predicate verb, and a0, a1, a2 are the subject, object and indirect object to the verb, respectively.

NEEG can be formally denoted as G = {V,E}, where V = {v1, v2, v3, ..., vP} is the node set, and E = {l1, l2, l3, ..., lQ} is the edge set. In order to overcome the sparsity problem of events, we represent event ei by its abstract form (vi, ri), where vi is denoted by a non-lemmatized predicate verb, and ri is the grammatical dependency relation of vi to the chain entity T, for example ei=(eats, subj). This kind of event representation is called predicateGR [Granroth-Wilding and Clark, 2016]. We count all the predicate-GR bigrams in the training event chains, and regard each predicate-GR bigram as an edge li in E. Each li is a directed edge vi → vj along with a weight w, which can be computed by:

where count(vi, vj) means the frequency of the bigram (vi, vj) appears in the training event chains.

The constructed NEEG G has 104,940 predicate-GR nodes, and 6,187,046 directed and weighted edges. Figure

3(a) illustrates a local subgraph in G, which describes the possible events involved in the restaurant scenario. Unlikely event pairs or event chains, event graph has dense connections among events and contains more abundant event interactions information.

2.2 Scaled Graph Neural Network

GNNwas first proposed by Gori et al. [2005]. Li et al. [2015] further introduced modern optimization technique of backpropagation through time and gated recurrent units to GNN, which is called gated graph neural network (GGNN). Nevertheless, GGNN needs to take the whole graph as inputs, thus it cannot effectively handle large-scale graph with hundreds of thousands of nodes. For the purpose of scaling to largescale graphs, we borrow the idea of divide and conquer in the training process that we do not feed the whole graph into GGNN. Instead, only a subgraph (as shown in Figure 3(b)) with context and candidate event nodes is fed into it for each training instance. Finally, the learned node representations can be used to solve the inference problem on the graph.

As shown in Figure 3(c), the overall framework of SGNN has three main components. The first part is a representation layer, which is used to learn the initial event representation. The second part is a gated graph neural network, which is used to model the interactions among events and update the initial event representations. The third part is used to compute the relatedness scores between context and candidate events, according to which we can choose the correct subsequent event.

Learning Initial Event Representations

We learn the initial event representation by composing pretrained word embeddings of its verb and arguments. For arguments that consist of more than one word, we follow [Granroth-Wilding and Clark, 2016] and only use the head word identified by the parser. Out-of-vocabulary words and absent arguments are represented by zero vectors.

Given an event ei = {p(a0, a1, a2)} and the word embeddings of its verb and arguments vp, va0 , va1 , va2 ∈ Rd (d is the dimension of embeddings), there are several ways to get the representation of the whole event vei by a mapping function vei = f(vp, va0 , va1 , va2 ). Here, we introduce three widely used semantic composition methods:

• Average: Use the mean value of the verb and all arguments vectors as the representation of the whole event.

• Concatenation [Granroth-Wilding and Clark, 2016]: Concatenate the verb and all argument vectors as the representation of the whole event.

Updating Event Representations Based on GGNN

As introduced above, GGNN is used to model the interactions among all context and candidate events. The main challenge is how to train it on a large-scale graph. To train the GGNN model on NEEG with more than one hundred thousand event nodes, each time we feed into it a small subgraph, instead of the whole graph, to make it feasible to large-scale graphs.

Inputs to GGNN are two matrices h(0) and A, where h(0)={ve1 , ve2 , ..., ven , vec1 , vec2 , ..., veck } (n is 8 and k is 5, the same as [Granroth-Wilding and Clark, 2016]), contains the initial context and subsequent candidate event vectors, and A∈ R(n+k)×(n+k) is the corresponding subgraph adjacency matrix, here:

The adjacency matrix A determines how nodes in the subgraph interact with each other. The basic recurrence of GGNN is:

GGNN behaves like the widely used gated recurrent unit (GRU) [Cho et al., 2014]. Eq. (4) is the step that passes information between different nodes of the graph via directed adjacency matrix A. a(t) contains activations from edges. The remainings are GRU-like updates that incorporate information from the other nodes and from the previous time step to update each node's hidden state. z(t) and r(t) are the update and reset gate, σ is the logistic sigmoid function, and ⊙ is element-wise multiplication. We unroll the above recurrent propagation for a fixed number of steps K. The output h(t) of GGNN can be used as the updated representations of context and candidate events.

Choosing the Correct Subsequent Event

After obtaining the hidden states for each event, we model event pair relations using these hidden state vectors. A straightforward approach to model the relation between two events is using a Siamese network [Granroth-Wilding and Clark, 2016]. The output of GGNN for context events are h(t) 1 , h(t) 2 , ..., h(t) n and for the candidate events are h(t) c1 , h(t) c2 , ..., h(t) ck . Given a pair of events h(t) i (i ∈ [1...n]) and h(t) cj (j ∈ [1...k]), the relatedness score is calculated by sij = g(h(t) i , h(t) cj ), where g is the score function.

There are multiple choices for the score function g in our model. Here, we introduce four common used similarity computing metrics that can serve as g in the followings.

• Manhattan Similarity is the Manhattan distance of two vectors: manhattan(h(t) i , h(t) cj ) = ∑ |h(t) i - h(t) cj |.
• Cosine Similarity is the cosine distance of two vectors: cosine(h(t) i , h(t) cj ) = h(t) i ·h(t) cj ||h(t) i ||||h(t) cj || .
• Dot Similarity is the inner product of two vectors: dot(h(t) i , h(t) cj ) = h(t) i · h(t) cj .
• Euclidean Similarity is the euclidean distance of two vectors: euclid(h(t) i , h(t) cj ) = ||h(t) i - h(t) cj ||.

Given the relatedness score sij between each context event h(t) i and each subsequent candidate event h(t) cj , the likelihood of ecj given e1, e2, ..., en can be calculated as sj = 1n ∑ni=1 sij, then we choose the correct subsequent event by c = maxj sj .

We also use the attention mechanism [Bahdanau et al., 2014] to the context events, as we believe that different context events may have different weight for choosing the correct subsequent event. We use an attentional neural network to calculate the relative importance of each context event according to the subsequent event candidates:

Then the relatedness score is calculated by:

Training Details

All the hyperparameters are tuned on the development set, and we use margin loss as the objective function:

where sIj is the relatedness score between the Ith event context and the corresponding jth subsequent candidate event, y is the index of the correct subsequent event. The margin is the margin loss function parameter, which is set to 0.015. Θ is the set of model parameters. λ is the parameter for L2 regularization, which is set to 0.00001. The learning rate is 0.0001, batch size is 1000, and recurrent times K is 2.

We use DeepWalk algorithm [Perozzi et al., 2014] to train embeddings for predicate-GR on the constructed NEEG (we find that embeddings trained from DeepWalk on the graph are better than that fromWord2vec trained on event chains), and use the Skipgram algorithm [Mikolov et al., 2013] to train embeddings for arguments a0, a1, a2 on event chains. The embedding dimension d is 128. The model parameters are optimized by the RMSprop algorithm. Early stopping is used to judge when to stop the training loop.

3 Evaluation

We evaluate the effectiveness of SGNN comparing with several state-of-the-art baseline methods. Accuracy (%) of choosing the correct subsequent event is used as the evaluation metric.

3.1 Baselines

We compare our model with the following baseline methods.

• PMI [Chambers and Jurafsky, 2008] is the co-occurrencebased model that calculates predicate-GR event pairs relations based on Pairwise Mutual Information.
• Bigram [Jans et al., 2012] is the counting-based skipgrams model that calculates event pair relations based on bigram probabilities.
• Word2vec [Mikolov et al., 2013] is the widely used model that learns word embeddings from large-scale text corpora. The learned embeddings for verbs and arguments are used to compute pairwise event relatedness scores.
• DeepWalk [Perozzi et al., 2014] is the unsupervised model that extends the word2vec algorithm to learn embeddings for networks.

• EventComp [Granroth-Wilding and Clark, 2016] is the neural network model that simultaneously learns embeddings for the event verb and arguments, a function to compose the embeddings into a representation of the event, and a coherence function to predict the strength of association between two events.
• PairLSTM [Wang et al., 2017] is the model that integrates event order information and pairwise event relations together by calculating pairwise event relatedness scores using the LSTM hidden states as event representations.

3.2 Dataset

Following Granroth-Wilding and Clark [2016], we extract event chains from the New York Times portion of the Gigaword corpus. The C&C tools [Curran et al., 2007] are used for POS tagging and dependency parsing, and OpenNLP is used for phrase structure parsing and coreference resolution. There are 5 candidate subsequent events for each event context and only one of them is correct. The detailed dataset statistics are shown in Table 1.

4 Results and Analysis

4.1 Overall Results

Experimental results are shown in Table 2, from which we can make the following observations.

1. Word2vec, DeepWalk and other neural network-based models (EventComp, PairLSTM, SGNN) achieve significantly better results than the counting-based PMI and Bigram models. The main reason is that learning low dimensional dense embeddings for events is more effective than sparse feature representations for script event prediction.
2. Comparison between "Word2vec" and "DeepWalk", and between "EventComp, PairLSTM" and "SGNN" show that graph-based models achieve better performance than pair-based and chain-based models. This confirms our assumption that the event graph structure is more effective than event pairs and chains, and can provide more abundant event interactions information for script event prediction.
3. Comparison between "SGNN-attention" and "SGNN" shows the attention mechanism can effectively improve the performance of SGNN. This indicates that different context events have different significance for choosing the correct subsequent event.
4. SGNN achieves the best script event prediction performance of 52.45%, which is 3.2% improvement over the best baseline model (PairLSTM).

We also experimented with combinations of different models, to observe whether different models have complementary effects to each other. We find that SGNN+EventComp boosts the SGNN performance from 52.45% to 54.15%. This shows that they can benefit from each other. Nevertheless, SGNN+PairLSTM can only boost the SGNN performance from 52.45% to 52.71%. This is because the difference between SGNN and PairLSTM is not significant, which shows that they may learn similar event representations but SGNN learns in a better way. The combination of SGNN, EventComp and PairLSTM achieves the best performance of 54.93%. This is mainly because pair structure, chain structure and graph structure each has its own advantages and they can complement each other.

The learning curve (accuracy with time) of SGNN and PairLSTM is shown in Figure 4. We find that SGNN quickly reaches a stable high accuracy, and outperforms PairLSTM from start to the end. This demonstrates the advantages of SGNN over PairLSTM model.

4.2 Comparative Experiments

We conduct several comparative experiments on the development set to study the influence of various settings on SGNN.

Experiment with Different Event Semantic Composition Methods

Given the word embeddings of the verb and arguments vp,va0 ,va1 ,va2 of the event ei, we compare three event semantic composition methods, introduced in Section 2.2.1. Experimental results are shown in Table 3.

We find that concatenating the embeddings of the verb and arguments vectors can achieve the best performance. And average input vectors is the worst way to get the representation ve. The main reason is that many events do not have an indirect object a2, which may harm the performance of the averaging operation.

Experiment with Different Score Functions

We compare several common used similarity score metrics g, as introduced in Section 2.2.3, to investigate their influence on the performance. As shown in Table 4, we find that different score metrics indeed have different effects on the performance, though the gaps among them are not so big. Euclidean score metric achieves the best result, which is consistent with the results of the previous study using word embeddings to compute document distances [Kusner et al., 2015].

5 RelatedWork

5.1 Statistical Script Learning

The use of scripts in AI dates back to the 1970s [Schank and Abelson, 1979]. In this conception, scripts are composed of complex events without probabilistic semantics. In recent years, a growing body of research has investigated learning probabilistic co-occurrence-based models with script events. Chambers and Jurafsky [2008] proposed unsupervised induction of narrative event chains from raw newswire text, using narrative cloze as the evaluation metric, and pioneered the recent line of work on statistical script learning. Jans et al. [2012] used bigram model to explicitly model the temporal order of event pairs. However, they all utilized a very impoverished representation of events in the form of (verb, dependency). To overcome the drawback of this event representation, Pichotta and Mooney [2014] presented an approach that employed events with multiple arguments.

There have been a number of recent neural models for script learning. Pichotta and Mooney [2016] showed that LSTM-based event sequence model outperformed previous co-occurrence-based methods. Granroth-Wilding and Clark [2016] described a feedforward neural network which composed verbs and arguments into low-dimensional vectors, evaluating on a multiple-choice version of the narrative cloze task. Wang et al. [2017] integrated event order information and pairwise event relations together by calculating pairwise event relatedness scores using the LSTM hidden states.

Previous studies built prediction models either based on event pairs [Chambers and Jurafsky, 2008; Granroth-Wilding and Clark, 2016] or based on event chains [Wang et al., 2017]. In this paper, we propose to solve the problem of script event prediction based on event graph structure.

5.2 Neural Network on Graphs

Graph-structured data appears frequently in domains such as social networks and knowledge bases. Perozzi et al. [2014] proposed the unsupervised DeepWalk algorithm that extended the word2vec [Mikolov et al., 2013] algorithm to learn embeddings for graph nodes based on random walks. Later, other unsupervised network embedding algorithms including LINE [Tang et al., 2015] and node2vec [Aditya and Leskovec, 2016] were proposed following DeepWalk. Duvenaud et al. [2015] introduced a convolutional neural network that could operate directly on graphs. Kipf and Welling [2016] presented a scalable approach for semi-supervised learning on graphs that was based on an efficient variant of convolutional neural networks. However, their models require the adjacency matrix to be symmetric and can only operate on undirected graphs.

Most related to our SGNN model is the graph neural network introduced by Gori et al. [2005], which extended recursive neural networks and could be applied on most of the practically useful kinds of graphs, including directed, undirected, labeled and cyclic graphs. However, the learning algorithm they used required running the propagation to convergence, which could have trouble propagating information across a long range in a graph. To remedy this, Li et al. [2015] introduced modern optimization technique of backpropagation through time and gated recurrent units to GNN, resulting in the gated graph neural network model. Nevertheless, their models usually operate on small graphs.

In this paper, we further extend the GGNN model by proposing a scaled graph neural network, which is feasible to large-scale graphs. Instead of feeding the whole graph into the model, we borrow the idea of divide and conquer in the training process, and only a subgraph that contains the concerned nodes is fed into GGNN for each training instance.

5.3 Graph-based Organization of Events

Some previous studies also explored graph-based organization of events. Li et al. [2013] described an approach to construct graph-based narrative scripts using crowdsourcing for story generation. Orr et al. [2014] used hidden markov models for script event prediction. Glavas and Snajder [2015] proposed event graphs as a novel way of structuring event-based information from text. Other studies tried to organize temporal relations [Chambers and Jurafsky, 2008] or causal relations [Zhao et al., 2017] between events into graph structure. In this paper, we propose event evolutionary graph, which denotes the knowledge base that stores abstract event evolutionary principles and patterns.

6 Conclusion

In this paper, we propose constructing event graph to solve the script event prediction problem based on network embedding. In particular, to better utilize the dense connections information among events, we construct a narrative event evolutionary graph (NEEG) based on the extracted narrative event chains. To solve the inference problem on NEEG, we present a scaled graph neural network (SGNN) to model the events interactions and learn better event representations for choosing the correct subsequent event. Experimental results show that event graph structure is more effective than event pairs and event chains, which can help significantly boost the prediction performance and make the model more robust.

Acknowledgments

This work is supported by the National Key Basic Research Program of China via grant 2014CB340503 and the National Natural Science Foundation of China (NSFC) via grants 61472107 and 61702137. The authors would like to thank the anonymous reviewers for the insightful comments. They also thank Haochen Chen and Yijia Liu for the helpful discussion.