Discourse-Level Event Temporal Ordering with Uncertainty-Guided Graph Completion

1 Introduction

Learning to order events at discourse-level is a crucial text understanding task, which is necessary for many applications including event timeline construction [Do et al., 2012; Reimers et al., 2016], time-aware summarization [Yan et al., 2011], temporal commonsense reasoning [Zhou et al., 2019], and others. Consider the example in Figure 1. Given a document marked with events, a system should assign a temporal link, i.e., TLINK [Allen, 1984], between every pair of events. For example, a TLINK of BEFORE should be assigned between [E2 assistance] and [E4 fallen], denoted by [E2] BEFORE -----→ [E4], indicating that [E2] occurs before [E4].

The challenge of discourse-level event temporal ordering derives from the appearance of long contexts. To succeed in the task, a system should be able to reason over global features and meanwhile maintain document-wide consistency.

For example, if a model has predicted [E2] BEFORE -----→ [E4] and [E4] SIMULTANEOUS ←--------→ [E5], it should also figure out that [E2] BEFORE -----→ [E5]. It is generally difficult to learn such patterns from texts solely, and the state-of-the-art methods usually resort to human-designed rules [Do et al., 2012; Ning et al., 2017; Ning et al., 2018; Han et al., 2019a; Han et al., 2019b]. Despite many progresses, these rules are usually costly to produce and often specific to tasks/domains/datasets, which limit the applicability of previous methods.

In this paper, we provide a new perspective for the event temporal ordering task - framing it as a graph completion problem. As noted in Figure 1 (Below), in our approach each document is considered as a temporal graph, in which each node has a one-to-one mapping relationship to an event. In this graph view, the event temporal ordering task corresponds to predicting/constructing the edges of the graph - which designate event-event temporal relations. By adopting this graph view, we can directly leverage the recent advances in graph representation learning [Chen et al., 2020] to enhance training, which endows our model the ability of global reasoning and meanwhile mining the underlying interdependencies of temporal relations effectively.

We devise an uncertainty-guided graph completion (UCGraph) framework. For training, our framework employs a graph mask pre-training strategy, in which we randomly mask a portion of edges out and then learn to reconstruct them following the remaining graph topology. This graph view enables our model to assimilate document-level features for reasoning and meanwhile learn the sense of global logical consistency. Nevertheless, a gap may exist in the inference stage as we would begin with an empty graph (instead of a masked graph), and the early predictions can have great impact on the late predictions. To mitigate this problem, we design a "certain-first" strategy in UCGraph based on model uncertainty [Gal and Ghahramani, 2016], which can find the optimal edge prediction orders and therefore minimize error propagation in the graph completion process (§ 6.2).

To verify the effectiveness of our approach, we have conducted extensive experiments on the standard benchmark datasets [Naik et al., 2019]. The experimental results demonstrate that our approach consistently outperforms previous methods and sets up a new state-of-the-art. In addition to its superior performance, our approach also show advantages over previous methods in maintaining global consistency, which is a crucial aspect of event temporal ordering. We have released our code at https://github.com/jianliu-ml/EventTemp to facilitate further exploration.

To summarize, our contributions are three-fold:

• This paper provides a new graph view on the task of discourse-level event temporal ordering, which can effectively assimilate document-level evidence for reasoning and learn inter-dependencies of temporal relations without complex feature engineering.
• We proposes a model consisting of graph mask pre-training and uncertainty-guided graph completion, which can learn inter-dependencies of temporal relations and find optimal prediction orders respectively. To our best knowledge, this is the first work introducing graph representation learning and uncertainty modeling to the task of discourse-level event temporal ordering.
• We set up a new state-of-the-art on the standard benchmark datasets, and we will release our code to facilitate following studies.

2 RelatedWork

Event Temporal Ordering. Temporal ordering of events is a crucial text understanding task. Shaped by the proposed TimeML annotation [Pustejovsky et al., 2003a] and the related corpora such as TimeBank [Pustejovsky et al., 2003b] and TimeBank-Dense [Cassidy et al., 2014], most previous works focus on addressing local temporal relations, i.e., they focus on events in the same or adjacent sentences [Bethard et al., 2007; Verhagen et al., 2007; UzZaman and Allen, 2010; Chang and Manning, 2012; Chambers, 2013; Chambers et al., 2014; Reimers et al., 2016], Despite many progresses, the reliance on local features often restricts their ability to address global event relations. As a remedy, a few of works have explored introducing document-structure constraints [Ning et al., 2017; Han et al., 2019a], entity co-reference patterns [Do et al., 2012], and event causal clues [Do et al., 2012; Ning et al., 2018] to learn global dependencies. Nevertheless, designing such rules requires substantial domain expertise, which may limit the applicability of previous works. Recently, focusing on global event temporal relations specifically, [Naik et al., 2019] benchmark discourse-level event temporal ordering by proposing a new corpora TDDiscourse. As suggested by [Naik et al., 2019], global event temporal ordering is very challenging, and the previous state-of-the-art systems underperforms a simple majority-class baseline.

Graph Representation Learning. Recent years have witnessed a surge in exploring graph representation learning [Chen et al., 2020]. Graph neural networks, including Graph Convolution Network [Kipf and Welling, 2017] and its variants [Veliˇckovi´c et al., 2018; Schlichtkrull et al., 2018], have demonstrated state-of-the-art performance in addressing many tasks, including semantic role labeling [Marcheggiani and Titov, 2017], relation extraction [Zhang et al., 2018], event extraction [Liu et al., 2019], and others. Among all GCNs variants, Relational Graph Convolutional Networks (R-GCNs) [Schlichtkrull et al., 2018] is a particular structure that facilitate relational reasoning. To our best knowledge, this is the first work introducing R-GCNs to the task of discourse-level event temporal ordering.

3 Approach

Figure 2 schematically visualizes the proposed UCGraph framework. Specifically, at the training time, a graph mask pre-training mechanism is employed to learn the underlying inter-dependencies of edges, by reconstructing an edge conditioned on the remaining graph. At the test time, UCGraph employs an uncertainty-guided graph completion strategy to rank each predicted edge and select the most uncertain one as current prediction. Let a document be D, and the event set be ED. Let R be the TLINK set. We denote by ei ∈ ED the ith event, and ri,j ∈ R the TLINK between ei and ej . Our model UCGraph aims to structure D as a complete graph GD, where the ith node corresponds to ei, and ri,j is the edge connecting ei and ej . Considering the reflexivity of TLINKs (e.g., ei BEFORE -----→ej always implies ei AFTER ←---- ej), we assert i < j 1 . In this way, the total number of edges in GD is |ED|×(|ED|-1) 2 .

3.1 GraphMask Pre-Training

To learn the underlying inter-dependencies of temporal relations, UCGraph employs a graph mask pre-training strategy.

RandomEdgeMasking. Given a training document D and its temporal graph, we first adopt a random mask strategy to exclude some edges 2 in GD (inspired by the masked language modeling objective in BERT [Devlin et al., 2019]), and then employ a graph model to re-construct these edges conditioned on the remaining graph. Assume a masked edges is ri′ ,j ′ , which connects two end nodes e′i and e′j . Then in the edge reconstruction phase, our goal is to recover ri′ ,j ′ by exploring the remaining graph's structure. This graph formulation enables our model to learn the dependency of the masked edge on other edges, and assimilate global features for reasoning.

1 Note this setting is in line with previous evaluations [Ning et al., 2018; Naik et al., 2019].

2 The optimal portion is set to 5%, which is based on a grid search on the development set (c.f., § 6.1).

GraphRepresentationLearning viaR-GCNs. To recover a masked edge ri′ ,j ′ (with two end nodes e′i and e′j ), we adopt Relational Graph Convolutional Networks (R-GCNs) [Schlichtkrull et al., 2018], involving two major procedures:

1. Node Representations Learning, in which we first learn the node representation of each node in the graph. Particularly, we use the event's within-sentence representation as the initialized node representation, which is computed using Bi-directional LSTM (BiLSTM) [Hochreiter and Schmidhuber, 1997] and BERT [Devlin et al., 2019]. Accordingly, the initialized node representation of e′i is denoted by h(0) e′i .
2. Graph Representations Learning, in which we further learn the graph-aware representation of a node via R-GCNs. As shown in Figure 3, the graph-aware representation of e′i (and e′j ) is learned by assimilating representations of its direct neighborhoods, and many R-GCNs layers are stacked to model long-range inter-dependencies. Particularly, the graph representation of e′i at the l+1th layer is computed as:

where σ denotes the ReLU activate function; r denotes a particular TLINK label 3 in the pre-defined label set R; N r (e′i ) denotes the set of neighbor nodes of e′i under relation r; ce′i ,r is a normalization constant, and W (l) r is the parameter regarding r at the lth layer. The graph representation of e′i is set as R-GCNs' output, denoted as He′i , and the representation of e′j is computed in a similar way, denoted by He′j .

3 Including a NA label to denote "no-relation".

Edge Prediction and Optimization. Based on He′i and He′j , we conduct a multi-class classification to predict the masked edge:

where oe′i ,e′j is an output vector containing the predictive probabilities of different TLINK labels, and the predicted result is the label having the largest value in oe′i ,e′j ; [; ] indicates concatenation computation; Wout and bout are model parameters. We train our model with cross-entropy loss:

where (e′i , e′j ) ranges over each masked edge; re′i ,e′j denotes the ground-truth TLINK label; p(re′i ,e′j |(e′i , e′j )) is the predictive probability of re′i ,e′j in oe′i ,e′j . We adopt Adam rules [Kingma and Ba, 2015] for model optimization.

3.2 Uncertainty-Guided Graph Completion

A gap max exist between training and testing, as in the testing stage we should build a temporal graph from the ground up (i.e., all the edges are masked), and previous predictions affect the following predictions. To minimize error propagation, we propose a "certain-first" strategy to explore the edge prediction orders, as visualized in Figure 2.

Uncertainty Modeling. Assume our model's prediction is r for a masked edge. We next estimate our model's uncertainty of r via MC-Dropout [Gal and Ghahramani, 2016]. Specifically, we conduct K forward passes with dropout layers being activated and get K output values ˜ r = [˜ r1, ˜ r2, ..., ˜ rK] 4 . According to [Gal and Ghahramani, 2016], the uncertainty of r empirically equals to the variance of ˜ r. Considering r is a categorical value, we adopt Shannon's entropy to

4 The values may be different due to the activated dropout layers.

Algorithm 1 Certain-First Graph Completion

Input: A test document D annotated with a set of events ED Output: A complete graph G

• 1: Transfer D as an empty graph G with nodes being ED
• 2: while G is not completed do
• 3: Predict TLINKs for all the missing edges in G
• 4: Estimate uncertainties of TLINKs via Eq. (4)
• 5: Select TLINK with minimal uncertainty value as current prediction, and insert the edge into G
• 6: end while

model the variance of ˜ r:

where p(˜ri) = N(˜ ri) K and N(˜ ri) is the frequency of ˜ ri in ˜ r. Note lower Unc(r) indicates smaller uncertainty of r, which also implies a more reliable prediction.

Certain-First Graph Completion Strategy. We design a certain-first graph completion strategy to decide prediction orders, as shown in Algorithm 1. Specifically, our algorithm starts with an empty graph G, which corresponds to a test document, and then conducts the following steps:

• Step 1: Pseudo-predict TLINK labels for all the missing edges in G.
• Step 2: Estimate the uncertainty value for each edge prediction using E.q. (4).
• Step 3: Select an prediction with the minimal uncertainty value, and add the corresponding edge into G.
• Step 4: Repeat the above steps until G is completed.

Note in Step 3, when a new edge is added into the G, the graph structure will change, and thus the next predictions may be different from the current ones. The above algorithm will repeat |ED|×(|ED|-1) 2 times exactly, which equals to the total number of edges in the graph 5 . We compare our method with different graph completion methods in § 6.2.

4 Experimental Setups

Datasets and Evaluation Metrics. We use TDDiscourse, the largest discourse-level event temporal ordering benchmark, as the test bed [Naik et al., 2019]. It includes two subsets: 1) TDD-Man, which augments TimeBank-Dense (TBDense) [Cassidy et al., 2014] by manually annotating TLINKs between event pairs that are more than one sentence apart. 2) TDD-Auto, which derives new TLINKs in the document with automatic inference rules. Table 1 and Table 2 compare the sizes and label distributions of TBDense, TDDMan and TDD-Auto. We adopt Precision (P), Recall (R), and F1 score (F1) as estimation metrics, same as previous works to ensure comparability [Ning et al., 2017; Naik et al., 2019; Han et al., 2019b].

5 The computation complexity of our method (for inference) is O(K × N2 ), where K is the number of forward passes in uncertainty computing, and N is the number of events in a document.

Implementation Details. The hyper-parameters of our model are tuned on the development set of TDDiscourse. Finally, for graph mask pre-training, the mask portion is set as 5% (chosen from 1% to 50%, c.f., § 6.1). The number of RGCN layers is set at 3 (chosen from [1, 2, 3, 4, 5]), and we use DEEP GRAPH LIBRARY 6 (DGL) to implement graph convolution algorithm. To learn the node representations, for BERT encoder, we use BERT-Base architecture; for BiLSTM encoder, we use Glove embeddings [Pennington et al., 2014] and set the hidden dimension to 256 (chosen from [64, 128, 256, 512]). In uncertainty modeling, we set K to 20 to balance speed and efficiency. For testing, we consider event pairs which are 15 or fewer sentences apart following [Naik et al., 2019] (The evaluation is not changed).

Baselines. We compare our method with the following baselines: Majority, which assigns the majority-class label to each event pair. Despite its simplicity, Majority outperforms most existing state-of-the-art methods on TDD-Man [Naik et al., 2019]. CAEVO [Chambers et al., 2014], a previous state-of-the-art method for identifying sentence-level TLINK which heuristic rules. BiLSTM [Cheng and Miyao, 2017], which introduces BiLSTM to learn representation of events to predict TLINKs. SP+ILP [Ning et al., 2017], which adds global constraints via integer linear programming (ILP), aiming to mitigate the problem that CAEVO and BiLSTM make separate local decisions that may result in global inconsistency. Deep SSVM [Han et al., 2019a], which leverages structured support vector machine to make global predictions. Mult-Task [Han et al., 2019b], which jointly predict events and relations. BERT, which adopts BERT [Devlin et al., 2019] to learn event representations (same as our method in learning node representations), but it conducts a pair-wise classification and ignores inter-dependencies. Our approach is denoted by UCGraph. We use UCGraph+BiLSTM and UCGraph+BERT to designate learning node representations via BiLSTM and BERT respectively.

6 https://www.dgl.ai/

5 Experimental Results

5.1 Overall Performance

Table 3 compares the performance of different models on TDD-Auto and TDD-Man. We also study the performance of different models on the local event temporal relation dataset TBDense 7 . From the results, our approach (UCGraph+BERT) achieves the best performance on TDD-Auto and TDD-man, outperforming the other methods by consideration margins (+2.4% in F1 on the average). This has justified the effectiveness of our approach. While, our approach underperforms Deep SSVM and Multi-Task on TBDense, where the reason might be TBDense focuses on local event temporal ordering, which may not fit with our method as the constructed temporal graph is too small for feature learning. We also note that both BiLSTM representations and BERT representations are effective (e.g., +8.5% and +3.5% in F1 on TDD-Man). This suggests that the effectiveness of our approach is independent of the initialized node representations.

5.2 Maintaining Global Consistency

Maintaining global consistency is an important aspect for discourse-level event temporal ordering. For example, if e1 BEFORE -----→ e2 and e2 BEFORE -----→ e3, an ideal system should make a globally consistent prediction e1 BEFORE -----→ e3. Following [Naik et al., 2019], we evaluate global consistency of different models by enumerating every possible triples and check whether the TLINKs are consistent. From the results in Table 4, adding ILP constraints 8 improves both the F1 score and global consistency for feature-based model (e.g, adding ILP constraints leads to a 3-point gain in F1 and a 1.2 point in consistency over SP). However, for neural network based methods (e.g., BiLSTM and BERT), though ILP constraints improves consistency, they generally harm the F1 score. This may show the difficulty in injecting prior knowledge into neural network based models. Our model achieves the highest F1 score and meanwhile can maintain good global consistency, which justifies the effectiveness of assimilating documentlevel features via graph representation learning.

7 Note, on TBDense, we only build local graph and we also discard the VAGUE TLINKs following [Naik et al., 2019].

8 We use PuLP (https://github.com/coin-or/pulp) to implement ILP algorithm and adopt global constraints.

6 Ablation and Discussion

We next conduct a series of studies to further explore the effectiveness of our model. The experiments are based on the development set of TDD-Auto, considering that it is much larger than TDD-Man and its annotation quality is also good.

6.1 Impact of the GraphMasking Pre-Training

We compare different edge masking strategies to explore which is the most effective way to learn edge interdependencies: 1) One-edge mask. At each step, only one edge is masked, and the goal is to recover the masked edge based on the remaining graph. 2) Random mask. At each step, a portion (ranging from 1% to 50%) of edges are randomly masked. Figure 4 shows the results. Particularly, the random strategy is better than one-edge strategy when a relative small portion (e.g., 5% to 15%) is adopted. A plausible explanation is that the temporal graph is dense, so only masking one edge may prevent the model to learn the underlying patterns. While, when a lot of edges are masked (i.e., when the portion is over 15%), it is also difficult for a model to capture edge inter-dependencies.

6.2 Impact of the Certain-First Strategy

We take a closer look at our certainty-first graph completion strategy, by comparing it with other strategies: 1) BERT+Ind., which makes independent pair-wise predictions based on BERT representations; 2) Graph+Seq., which adopts graph view but predicts edges sequentially (e.g., following the ordering (e1, e2), (e1, e3), ...); 3) Graph+Rand., which also adopts graph view but randomly predicts an edge at each step; 4) Graph+Logits, which is similar to our model but ranks all of the edge predictions based on their softmax probabilities, and at each step considers the edge having the highest softmax probability as prediction. Table 5 shows the results.

From the results, approaches adopting graph view generally yield better performance than pair-wise methods, which justifies the necessity of graph representation learning. While, the prediction orders affect the results seriously. For example, Graph + Logits even yield negative results than Graph + Rand. adopting random prediction strategy. This implies that softmax probability does not reflect the reliability of prediction. Among all the above strategies, our certainty-first approach achieves the best performance. To find out the reason, we manually examine predictions and their uncertainty values. From the results, for predictions whose uncertainty value are lower than 0.15, 81.2% of them are correct; for predictions whose uncertainties values are higher than 0.5, only 30.1% of them are correct. This implies that our certain-first strategy tend to yield correct predictions at early stage and thus reduce error cascading in graph completion.

6.3 Learning Visualization and Case Study

A salient cluster pattern can be observed in our certaintyfirst graph completion process. Particularly, Figure 5 studies the number of cases where the events evolved in the current edge prediction overlap with that of previous-N predictions, by comparing our method and a random prediction strategy. From the results, in our method, there are 358 cases (28%)

and 780 cases (61%) overlap with the previous-1 and -3 predictions, but in the random strategy there are only 48 cases (3%) and 122 cases (9%). This indicate that our method tends to tackle events which have been addressed in previous predictions. Figure 6 visualizes the case of a randomly selected document APW19980227.0494 with down-sampled events, where the cluster pattern can be clearly observed. A plausible explanation of the above phenomenon is that: when an edge is predicted and added into graph, our model gets more information about the nodes (i.e., events). Thus our model becomes more confident to predict edges involving those nodes.

7 Conclusion

In conclusion, this paper takes a new graph perspective on the task of discourse-level event temporal ordering, framing it as a graph completion problem. A new model based on graph representation learning and uncertainty modeling is proposed, which can effectively capture the inter-dependencies of temporal relations and assimilate document-level features for reasoning. The experimental results have suggested that our approach not only improves performance but also maintains global consistency. In the future, we seek to apply our method to other discourse-level tasks such as document-level relation extraction and event causality identification.

Acknowledgments

The research work descried in this paper has been supported by the Fundamental Research Funds for the Central Universities 2021RC234. It has also been supported by the National Key R&D Program of China (2019YFB1405200) and the National Nature Science Foundation of China (No. 61976015, 61976016, 61876198 and 61370130).