# A Survey on Event-based News Narrative Extraction

Brian Felipe Keith Norambuena<EMAIL_ADDRESS>Virginia
TechBlacksburgVirginiaUSA Universidad Católica del NorteAntofagastaChile ,
Tanushree Mitra<EMAIL_ADDRESS>University of WashingtonSeattleWashingtonUSA
and  Chris North<EMAIL_ADDRESS>Virginia TechBlacksburgVirginiaUSA

###### Abstract.

Narratives are fundamental to our understanding of the world, providing us
with a natural structure for knowledge representation over time. Computational
narrative extraction is a subfield of artificial intelligence that makes heavy
use of information retrieval and natural language processing techniques.
Despite the importance of computational narrative extraction, relatively
little scholarly work exists on synthesizing previous research and
strategizing future research in the area. In particular, this article focuses
on extracting news narratives from an event-centric perspective. Extracting
narratives from news data has multiple applications in understanding the
evolving information landscape. This survey presents an extensive study of
research in the area of event-based news narrative extraction. In particular,
we screened over 900 articles that yielded 54 relevant articles. These
articles are synthesized and organized by representation model, extraction
criteria, and evaluation approaches. Based on the reviewed studies, we
identify recent trends, open challenges, and potential research lines.

computational narratives, narrative representation, narrative extraction,
narrative analysis

††copyright: rightsretained††journal: CSUR††journalyear: 2023††journalvolume:
1††journalnumber: 1††article: 1††publicationmonth: 1††doi:
10.1145/3584741††ccs: Computing methodologies Information extraction††ccs:
Computing methodologies Knowledge representation and reasoning††ccs: General
and reference Surveys and overviews

##  1\. Introduction

Narratives are fundamental to our understanding of the world (Abbott, 2008)
and they provide a framework that enables humans to associate and represent
events over time (Burke, 1969). Moreover, narratives are a core element of
collaborative sensemaking in society (Baber et al., 2011; Wilson et al.,
2018). In this context, narratives are defined as a _coherent system of
interrelated stories_ (Halverson et al., 2011), where stories themselves are
defined as sequences of events (Wake, 2013). These systems of stories help
humans produce a shared understanding of the world (Szostek, 2017). In
particular, extracting narratives from data is a fundamental task in our
efforts to achieve this goal of common understanding (Keith Norambuena and
Mitra, 2021).

In this survey, we focus on a specific type of narrative: news narratives. In
particular, we analyze works that extract computational narrative
representations from news articles. Work on general computational narratives
started as early as the 1960s (Ryan, 2017). However, these early works focused
mostly on narrative generation—usually through rule-based methods and grammars
(Alhussain and Azmi, 2021)—rather than extracting narratives from data. In
contrast, the narrative extraction works reviewed in this survey start around
the 2000s (e.g., (Uramoto and Takeda, 1998; Chieu and Lee, 2004; Nallapati et
al., 2004)).

From an information retrieval standpoint, extracting narratives from data
relies on several techniques from this field, including event (Nallapati et
al., 2004) and entity extraction methods (Bögel and Gertz, 2015), as well as
elements from search and ranking (Liao et al., 2021) and summarization
techniques (La Quatra et al., 2021). Furthermore, narrative extraction is
supported by several artificial intelligence techniques, such as machine
learning (Tannier and Moriceau, 2013) and search and optimization (Shahaf and
Guestrin, 2010).

Despite the importance of news narrative extraction, relatively little work
has focused on clarifying the past trajectory and future agenda of news
narrative extraction. Our goal with this survey is to fill this gap. This
article presents a literature review of narrative extraction screening over
900 papers from a variety of journals, conferences, and workshops. In
particular, by thematically analyzing 54 articles we identify a taxonomy of
representations, extractions methods, and evaluation methods, that helps
organize prior work and chart the path forward for future research. Taken
together, all these elements provide a detailed account of the core elements
of event-based news narrative extraction.

###  1.1. Scope of this Survey and Definitions

####  1.1.1. Narrative Definition

There are many potential definitions of narrative in the literature. General
narrative theory focuses explicitly on understanding the general rules of
narrative and its different arrangements that make it meaningful (Abbott,
2008; Puckett, 2016). The key intuition in formal narrative theory is that
there is a distinction between the story itself and its representation.
Narrative theory tries to understand the relationships between stories and
their many possible representations (Puckett, 2016). Other definitions
consider narratives as communication tools to construct a shared meaning of
events with the purpose of influencing the behaviors (Miskimmon et al., 2014).

Halverson et al. (Halverson et al., 2011) define narratives not just as one
story, but rather as a system of stories. That is, narratives are a systematic
collection of interrelated stories with coherent themes. Stories are defined
as sequences of events tied together in a coherent fashion. In this
definition, events are the fundamental units of narrative action, they are
either an act involving characters and entities or a happening where no
entities are causally involved (Abbott, 2008). We leverage this definition to
model news narratives. Thus, we have a series of hierarchical definitions
starting from the narrative, then going into stories, and finally into the
fundamental units of the narrative: the event and its related entities.
Furthermore, these definitions require an underlying order for the events, as
they have to be linked sequentially in the stories.

There are two fundamental units in our previous discussion: events and
entities. These units provide different perspectives of the narrative, one is
focused on the actions and happenings of the narrative, while the other is
focused on the characters and other entities that participate in the events.
However, to provide a more focused review we will focus exclusively on event-
based narrative representations. Thus, we define computational narrative
representations as an event structure that represents different stories. We
note that these event structures are discrete in nature (e.g., a graph or a
timeline of events). Nevertheless, we note that some of the extraction methods
that we review will leverage entity-based information, but they are not the
focus of their representation.

Finally, we note that the simplest way to computationally represent a
narrative is through a linear structure representing sequences of events
(i.e., a timeline). In fact, this is the most common approach in our survey.
However, we also find that there are more complex representations, based on
event graph structures.

####  1.1.2. News Narrative Extraction

The main focus of this survey is on narrative extraction from news data (“How
do we extract a news narrative from data?”). In particular, we focus
exclusively on textual narratives extracted from a set of news articles
published in traditional news sources—we exclude works that focus on mixed
types of data (e.g., images and text, or videos and text). Thus, all of the
surveyed works fall under the umbrella of Natural Language Processing.

Moreover, we note that extraction can be performed at a document level (i.e.,
extracting a narrative from a single document) or at a corpus level (i.e.,
extracting a narrative from multiple news articles). As part of our scope
definition, we focus on corpus-level extraction methods, where the goal is to
obtain a narrative representation from a set of articles, rather than on
document-level extraction (e.g., extracting the narrative of a single
document).

Throughout this work, we work under the assumption that most news articles
focus on a single main event. This is a common assumption in story and
narrative extraction methods (Keith Norambuena and Mitra, 2021) and a natural
assumption when dealing with breaking news articles, as they are likely to
present a single event (Keith Norambuena et al., 2020). We note that news
articles may sometimes refer to previous or secondary events in their body,
which can be used to link articles together. However, for the purposes of our
definition, these references are not considered the main event of that news
article. Following this assumption, we deal with three levels of resolution in
our works: events as sentences, events as documents, and events as clusters.
Events may be represented by relevant sentences extracted from a news article,
usually, a single sentence is used for these purposes. Events may also be
represented by an entire document (i.e., a news article). We note that there
is some overlap between these two representations when documents are
associated with headlines. Finally, events may also be represented as sets of
documents that refer to the same main event.

We note that there are more granular views of events in the literature—for
example, the notion of event from TimeML (Pustejovsky et al., 2003; Minard et
al., 2015), where events are a much more specific action (e.g., a perception
or state) compared to a news event that may comprise multiple of these events
(Hu et al., 2014). Contrasting with the granular specifications of TimeML,
there are also works that view events as sets of terms (e.g., keywords or
entities) (Swan and Allan, 2000), akin to how topics are sometimes
characterized in traditional topic modeling works (Blei and Lafferty, 2006),
and construct timelines representing them as such. However, this view of
events is too broad and lacks the specificity expected from news events. Thus,
we do not consider narrative representations that use such approaches.
Following these exclusion criteria, we removed approximately 10 articles from
the final data set.

Leveraging our previous discussion of narratives as a structured system of
interrelated stories, we define the (event-based) narrative extraction task as
follows:

News Narrative Extraction: Given a set of news articles, the news narrative
extraction task generates a discrete structure comprised of events to
represent the narrative.

We note that the structure is left deliberately ambiguous to allow for
different types of representations, such as event timelines or event graphs.
However, we note that all these overarching narrative representations are
discrete in nature (e.g., event graphs), even if the underlying event
representations could be continuous (e.g., text embeddings). Furthermore, the
representation of the event itself can be defined in different ways depending
on the resolution level (sentences, documents, or clusters) of the narrative
representation. Furthermore, this definition excludes entity-based
representations (e.g., character networks).

####  1.1.3. Exclusions: Related Tasks

We exclude works that focus on narrative generation, narrative forecasting,
and narrative analysis. We also exclude works that only focus on
representational issues without an associated method.

Narrative generation is a fundamentally different task from extraction that
seeks to create new fictional narratives, rather than extract a narrative that
already exists (either fictional or non-fictional) (Gervás et al., 2019; Gatt
and Krahmer, 2018). Furthermore, the focus of narrative generation is usually
fictional narratives, not news narratives. Narrative forecasting (i.e.,
predicting the next events in the narrative) is a task that lies between
extraction and generation, but its focus is on generating new events rather
than on extracting the complete narrative (Zhao, 2021). Narrative analysis
methods use existing extraction approaches to obtain a computational
representation of the narrative and then use it to analyze the narrative (Ofek
et al., 2013; Schlachter et al., 2015). However, they do not provide new
insight into the extraction task itself, unless they include a novel
extraction method as well.

Moreover, we exclude interactive narratives, as these are a fundamentally
different type of narratives where the story can be changed through user
feedback and actions (Cavazza and Pizzi, 2006), which would not make sense in
the context of news narratives. However, while the underlying story cannot be
changed, it might still be possible to interact with the narrative model. In
fact, several works rely on interactivity at a presentation level.

Finally, we exclude works that focus on news narratives extracted from social
media (Lin et al., 2012; Bandeli et al., 2020), as social media narratives
follow a different approach that requires not only analyzing content but also
the users spreading it, leading to unique challenges that are left beyond the
scope of this survey.

####  1.1.4. Inclusion and Exclusion Criteria

Having defined our scope, we provide details of our collection methodology and
inclusion/exclusion criteria. We describe the query and steps used to generate
the final article set in Figure 1.

Figure 1. Overview of the article collection process and the
inclusion/exclusion criteria used to construct the final article set.

We performed two article searches on SCOPUS and Web of Science. The first
search was based on three queries that covered broad areas related to the news
narrative extraction task: narrative extraction and computational narratives
in general, topic detection and tracking (TDT) (Allan, 2012), and timeline
summarization (TLS) (Ghalandari and Ifrim, 2020). These latter two fields are
highly related to our task and provide a series of relevant works that we have
examined in our survey. In particular, we note that most TDT works view news
as flat collections (Nallapati et al., 2004) of events without an underlying
narrative structure. Instead, we view news data as an interconnected structure
of events. Nevertheless, some TDT works fit with our view of narratives and
thus we include them in the review. In contrast, we consider most of the TLS
line of works as a subset of the narrative extraction task and include many
works from that field as part of the “event as sentences” resolution level.
However, we exclude works that do not generate a full timeline and only focus
on identifying relevant dates, as that is a different sub-task. Next, we
performed a second query based on a series of keywords obtained from the
initial results. We applied the same inclusion and exclusion criteria for this
second set of articles. After this, some additional articles that were not
caught by our two main searches were added based on references from some
reviewed articles. Finally, we performed a final pass on all the articles
based on an in-depth reading of each article.

The rest of this article is structured as follows. The rest of Section 1
discusses related surveys and reviews. Section 2 presents an overview and
summary of each one of the reviewed articles. Section 3 discusses the
different extraction criteria. Section 4 presents a discussion of the
evaluation approaches and metrics. Section 5 presents a discussion of our
findings and future research directions. This survey concludes with a brief
summary and key takeaways in Section 6.

###  1.2. Related Surveys

Most surveys regarding computational narratology focus on the task of
narrative generation rather than extraction. In fact, there is an extensive
series of survey papers and literature reviews on generation in conferences
(Valls-Vargas et al., 2017) and journals (Kybartas and Bidarra, 2016; Gervás
et al., 2019) that cover narrative generation and its different approaches in-
depth. Moreover, there is even a book (Mani, 2012) on computational narrative
representations for narrative generation and an extensive and in-depth book
chapter on different cognitive approaches to narrative generation (Ogata,
2016). Narrative generation is also covered as a specific subtask of the more
general field of natural language generation (Gatt and Krahmer, 2018). In
contrast, general narrative extraction is not covered by any published survey.
More specifically, our domain of interest—news narrative extraction—is also
not covered in the literature. However, there are some surveys that touch on
related topics. In the rest of this subsection, we provide a general
description of these works and how they relate to our own survey.

First, we note a survey on the evaluation of summarization methods by Ermakova
et al. (Ermakova et al., 2019) as a related approach to narrative extraction.
In particular, this survey provides a comprehensive overview of existing
metrics for the evaluation of narrative summarization methods. Narrative
summarization is related to both narrative extraction and generation, as it
requires extracting an internal narrative representation from data and then
generating the summary. In comparison, our survey presents evaluation metrics
for narrative extraction methods, some of which overlap with the evaluation
metrics discussed in the aforementioned survey.

Second, we note the work of Richards et al. (Richards et al., 2009) which
discusses representation models for narratives. Most of the discussion is
specific to narrative generation, but there are general models that could be
applied in both generation and extraction contexts. Nevertheless, the
discussion is focused on what constitutes a narrative in general rather than
being directly useful for the news narrative extraction task as defined here.

Third, we note the survey on extracting character networks from fictional
narratives by Labatut and Bost (Labatut and Bost, 2019). Their work is related
to ours as it focuses on the narrative extraction task, but with a much more
specific scope focused on character-based models (i.e., entity-based narrative
extraction). In contrast, our work has a different scope that considers event-
based models. Moreover, their scope focuses on extracting networks from
fictional narratives, while we consider extraction methods for non-fictional
narratives in news data.

Finally, we note the recent survey on timeline summarization approaches by
Ghalandari and Ifrim (Ghalandari and Ifrim, 2020). While there is plenty of
overlap between this survey and our own, the news narrative extraction task
that we cover is more general than just timeline summarization, as we include
methods that treat events as documents and clusters, rather than at a sentence
level. However, we highlight the empirical component of that survey, which
includes an experimental section comparing the state-of-the-art methods in
timeline summarization.

##  2\. News Narrative Extraction

###  2.1. Overview

We found a total of 54 articles focusing on event-based news narrative
extraction in our review. We present the articles based on the resolution
level that they use: events as sentences, events as documents, and events as
clusters. Figure 2 summarizes the identified approaches categorized by event
resolution and some relevant subsets of these categories. In the sentence-
level resolution, query-based approaches include an information retrieval step
in addition to the narrative extraction itself. For example, these approaches
require the user of the method to define a search query (e.g., “COVID” or
“Terrorism”) to find related documents in the data set through similarity-
based techniques or other methods before extracting the narrative from the
queried subset. In contrast, pre-filtered approaches assume that the data set
has been already filtered and do not require an explicit query. In the
document-level resolution, Connect the Dots approaches refer to the line of
works derived from Shahaf and Guestrin’s seminal method of the same name on
storyline extraction (Shahaf and Guestrin, 2010). In the cluster-level
resolution, event threading and evolution methods refer to a series of works
based on Nallapati et al.’s event threading concept (Nallapati et al., 2004)
or Yang et al.’s event evolution concept (Yang et al., 2006). Works that fall
under the “Others” do not fit in any of the defined subsets.

Figure 2. Overview of the different methods used in news narrative extraction
categorized by event resolution.

Table 1 summarizes the reviewed articles. In particular, we include the
following columns in this table: event resolution, number of stories,
structure, type of approach, and event representation. We now provide a brief
description of these elements and their possible values.

Event resolution refers to the abstraction level at which the events are
extracted. As mentioned in the scope definition, we consider three levels:
sentences, documents, and clusters. Sentence-level works represent events as
either a single sentence (e.g., the most important sentence or a headline) or
a set of sentences (e.g., a sample of representative sentences). Document-
level works represent events directly as a single document (e.g., a full news
article). Cluster-level works represent events as sets of documents (e.g.,
multiple news articles that talk about the same basic event). Structure
represents whether the extraction method generates a linear structure of
events (e.g., a timeline (Shahaf and Guestrin, 2010; Yan et al., 2011a)) or a
graph-like structure (e.g., a directed acyclic graph (Keith Norambuena and
Mitra, 2021) or tree (Liu et al., 2017)). Figure 3 exemplifies these concepts.

Figure 3. Resolution level and narrative structure. Examples adapted from
several works in this survey.

Number of stories refers to whether the method is designed to handle a single
storyline or multiple storylines. Recall that our definition of a story as a
sequence of events. Most timeline extraction methods extract a single story,
but some of them extract parallel timelines, where each timeline represents a
different story from the data (Yu et al., 2021; Laban and Hearst, 2017). In
contrast, most graph-based works are designed to represent multiple
storylines, due to their inherent more complex nature compared to timelines.
However, there are some works that represent a single story, but provide extra
information by exploiting graph structures. For example, appending additional
nodes with related events to the central story (Lin and Liang, 2008).

Type of approach represents whether the method is supervised—which requires
training data—or unsupervised—which does not require training data. In
general, we considered any method where the authors had to train the model
with labeled data before using it as supervised. However, some approaches only
did this to find the optimal value of a small set of hyperparameters
(Nallapati et al., 2004; Yan et al., 2011b; Li et al., 2015) and it could be
possible to use them in an unsupervised manner, provided that those
hyperparameters were fixed in some other way (e.g., heuristics or previous
work information).

Finally, event representation provides information about the computational
representation of the events. Note that this is separate from the resolution
level of the event. In general, we found four types of representations: word
frequency models (e.g., TF-IDF and Bag of Words vectors), topic distribution
models (e.g., Latent Dirichlet Allocation (LDA) vectors), neural embeddings
(e.g., BERT), and entity-based models (e.g., entity frequency vectors). Some
works combine these approaches and have a mixed event representation that
leverages all these elements in some way to extract the final narrative model.
There are some works that did not fit in any of these approaches and were
marked as “Other”.

|  | Event Resolution | # of Stories | Structure | Approach | Event Representation
---|---|---|---|---|---|---
Year | Reference | Sentences | Documents | Clusters | Single | Multiple | Linear | Graph | Unsupervised | Supervised | Word Vectors | Topic Distribution | Neural Embeddings | Entities | Other
1998 | Uramoto and Takeda (1998) |  | $\times$ |  |  | $\times$ |  | $\times$ | $\times$ |  | $\times$ |  |  |  |
2004 | Nallapati et al. (2004) |  |  | $\times$ |  | $\times$ |  | $\times$ |  | $\times$ | $\times$ |  |  | $\times$ |
2004 | Chieu and Lee (2004) |  | $\times$ |  | $\times$ |  | $\times$ |  | $\times$ |  | $\times$ |  |  |  |
2005 | Guha et al. (2005) |  | $\times$ |  |  | $\times$ | $\times$ |  | $\times$ |  | $\times$ |  |  |  |
2006 | Yang et al. (2006) |  |  | $\times$ |  | $\times$ |  | $\times$ | $\times$ |  | $\times$ |  |  |  |
2006 | Lin and Liang (2006) |  |  | $\times$ | $\times$ |  |  | $\times$ | $\times$ |  | $\times$ |  |  |  |
2007 | Lin et al. (2007) |  |  | $\times$ | $\times$ |  |  | $\times$ | $\times$ |  | $\times$ |  |  |  |
2008 | Chen and Chen (2008) |  |  | $\times$ |  | $\times$ |  | $\times$ | $\times$ |  | $\times$ | $\times$ |  |  |
2008 | Qiu et al. (2008) |  |  | $\times$ |  | $\times$ |  | $\times$ |  | $\times$ | $\times$ |  |  |  |
2008 | Lin and Liang (2008) |  |  | $\times$ | $\times$ |  |  | $\times$ | $\times$ |  | $\times$ |  |  |  |
2009 | Yang et al. (2009) |  |  | $\times$ |  | $\times$ |  | $\times$ | $\times$ |  | $\times$ |  |  |  |
2010 | Shahaf and Guestrin (2010) |  | $\times$ |  | $\times$ |  | $\times$ |  | $\times$ |  | $\times$ |  |  |  |
2011 | Yan et al. (2011b) | $\times$ |  |  | $\times$ |  | $\times$ |  |  | $\times$ | $\times$ |  |  |  |
2011 | Yan et al. (2011a) | $\times$ |  |  | $\times$ |  | $\times$ |  |  | $\times$ | $\times$ |  |  |  |
2011 | Hu et al. (2011) | $\times$ |  |  | $\times$ |  | $\times$ |  | $\times$ |  | $\times$ | $\times$ |  |  |
2011 | Khurdiya et al. (2011) |  |  | $\times$ |  | $\times$ |  | $\times$ | $\times$ |  |  | $\times$ |  |  |
2012 | Zhu and Oates (2012) |  | $\times$ |  | $\times$ |  | $\times$ |  | $\times$ |  | $\times$ |  |  |  |
2012 | Chen and Chen (2012) |  |  | $\times$ |  | $\times$ |  | $\times$ | $\times$ |  | $\times$ | $\times$ |  |  |
2012 | Shahaf and Guestrin (2012) |  | $\times$ |  | $\times$ |  | $\times$ |  | $\times$ |  | $\times$ |  |  |  |
2012 | Shahaf et al. (2012) |  | $\times$ |  |  | $\times$ |  | $\times$ | $\times$ |  | $\times$ |  |  |  |
2013 | Binh Tran et al. (2013) | $\times$ |  |  | $\times$ |  | $\times$ |  |  | $\times$ | $\times$ |  |  |  |
2013 | Li and Li (2013a) | $\times$ |  |  | $\times$ |  | $\times$ |  |  | $\times$ |  | $\times$ |  |  |
2013 | Tran et al. (2013) | $\times$ |  |  | $\times$ |  | $\times$ |  |  | $\times$ | $\times$ |  |  |  |
2013 | Huang et al. (2013) | $\times$ |  |  | $\times$ |  | $\times$ |  | $\times$ |  |  | $\times$ |  |  |
2013 | Tannier and Moriceau (2013) |  | $\times$ |  |  | $\times$ |  | $\times$ |  | $\times$ | $\times$ |  |  |  |
2013 | Shahaf et al. (2013a) |  | $\times$ |  |  | $\times$ |  | $\times$ | $\times$ |  | $\times$ |  |  |  |
2013 | Shahaf et al. (2013b) |  |  | $\times$ |  | $\times$ |  | $\times$ | $\times$ |  | $\times$ |  |  |  |
2014 | Nguyen et al. (2014) | $\times$ |  |  | $\times$ |  | $\times$ |  | $\times$ |  | $\times$ |  |  |  |
2014 | Zhu and Oates (2014) |  | $\times$ |  | $\times$ |  | $\times$ |  | $\times$ |  | $\times$ |  |  |  |
2014 | Huang et al. (2014) |  |  | $\times$ |  | $\times$ |  | $\times$ | $\times$ |  | $\times$ | $\times$ |  | $\times$ |
2014 | Wei et al. (2014) |  |  | $\times$ |  | $\times$ |  | $\times$ | $\times$ |  | $\times$ |  |  |  |
2014 | Hu et al. (2014) |  | $\times$ |  |  | $\times$ |  | $\times$ | $\times$ |  |  | $\times$ |  |  |
2014 | Zhou et al. (2014) | $\times$ |  |  |  | $\times$ |  | $\times$ | $\times$ |  | $\times$ |  |  |  |
2015 | Tran et al. (2015a) | $\times$ |  |  | $\times$ |  | $\times$ |  |  | $\times$ | $\times$ |  |  |  |
2015 | Li et al. (2015) | $\times$ |  |  | $\times$ |  | $\times$ |  |  | $\times$ |  | $\times$ |  |  |
2015 | Bögel and Gertz (2015) |  | $\times$ |  | $\times$ |  |  | $\times$ | $\times$ |  | $\times$ |  |  | $\times$ |
2015 | Chen et al. (2015) | $\times$ |  |  | $\times$ |  | $\times$ |  | $\times$ |  | $\times$ | $\times$ |  |  | $\times$
2015 | Shahaf et al. (2015) |  |  | $\times$ |  | $\times$ |  | $\times$ | $\times$ |  | $\times$ |  |  |  |
2017 | Wu et al. (2017) | $\times$ |  |  | $\times$ |  | $\times$ |  | $\times$ |  | $\times$ |  |  |  |
2017 | Liu et al. (2017) |  |  | $\times$ |  | $\times$ |  | $\times$ |  | $\times$ | $\times$ |  |  |  |
2017 | Laban and Hearst (2017) |  | $\times$ |  |  | $\times$ | $\times$ |  | $\times$ |  | $\times$ |  |  |  |
2018 | Wang et al. (2018) | $\times$ |  |  | $\times$ |  | $\times$ |  |  | $\times$ |  | $\times$ |  | $\times$ |
2018 | Tikhomirov and Dobrov (2018) | $\times$ |  |  | $\times$ |  | $\times$ |  |  | $\times$ | $\times$ |  | $\times$ |  |
2018 | Xu and Tang (2018) |  |  | $\times$ |  | $\times$ |  | $\times$ | $\times$ |  |  |  | $\times$ |  |
2018 | Zhou et al. (2018) | $\times$ |  |  |  | $\times$ |  | $\times$ | $\times$ |  | $\times$ |  |  |  |
2019 | Camacho Barranco et al. (2019) |  | $\times$ |  |  | $\times$ |  | $\times$ | $\times$ |  | $\times$ | $\times$ |  | $\times$ |
2019 | Cai et al. (2019) |  |  | $\times$ |  | $\times$ |  | $\times$ | $\times$ |  | $\times$ |  |  |  |
2019 | Yuan et al. (2019) | $\times$ |  |  |  | $\times$ |  | $\times$ | $\times$ |  |  |  | $\times$ |  |
2020 | Duan et al. (2020) | $\times$ |  |  | $\times$ |  | $\times$ |  | $\times$ |  | $\times$ |  | $\times$ |  |
2020 | Liu et al. (2020) |  |  | $\times$ |  | $\times$ |  | $\times$ |  | $\times$ | $\times$ |  |  |  |
2021 | La Quatra et al. (2021) | $\times$ |  |  | $\times$ |  | $\times$ |  | $\times$ |  |  |  |  |  | $\times$
2021 | Yu et al. (2021) | $\times$ |  |  |  | $\times$ | $\times$ |  |  | $\times$ |  |  | $\times$ |  |
2021 | Liao et al. (2021) | $\times$ |  |  | $\times$ |  | $\times$ |  | $\times$ |  |  |  | $\times$ |  |
2021 | Keith Norambuena and Mitra (2021) |  | $\times$ |  |  | $\times$ |  | $\times$ | $\times$ |  |  |  | $\times$ |  |

Table 1. Summary of the surveyed articles.

###  2.2. Events as Sentences

We start with works that use a sentence-level resolution. Most of these
methods fall under the umbrella of timeline summarization (Ghalandari and
Ifrim, 2020). However, not all of them fit with traditional TLS work. We split
the discussion into three parts: query-based approaches, pre-filtered
approaches, and others.

####  2.2.1. Query-based Approaches

These approaches perform an information retrieval step before or during the
narrative extraction process based on a user-defined query. In some cases, the
query just acts as a simple filter, in others, they explicitly include the
query into the narrative extraction model.

Chieu and Lee (Chieu and Lee, 2004) present a query-based timeline extraction
approach where each event is represented as a sentence. This is the earliest
form of the “events as sentences” that we could find in the literature.
Sentences are first filtered based on the query and then ranked according to
two criteria: interest—based on the frequency of the reported event in the
query—and burstiness—based on the idea that important events form clusters
around their date of occurrence. To determine whether two sentences are
reporting the same event, the authors use cosine similarity. Furthermore,
interest is determined based on a time window to avoid combining events that
should be separated due to their temporal distance. To reduce redundancy,
duplicated sentences are removed based on a time window around an important
event that depends on the interest value.

Yan et al. (Yan et al., 2011b) proposed a timeline summarization method based
on balanced optimization and iterative substitution of sentences. Their
optimization problem is defined in terms of relevance, coverage, coherence,
and diversity. All these terms are based on the Kullback-Leibler divergence
(KLD) (Kullback and Leibler, 1951) of the summary items with a target
distribution. Relevance is related to a user-defined query and is defined as
the KLD between the summary items and the internal representation of the
query. Coverage is based on a global term—KLD between the summary items and
the whole corpus—and a local term—KLD between the summary items and the set of
sentences from the same date. Coherence is defined locally, based on the KLD
between each summary item and its neighboring summaries by using an
exponential temporal decay term (i.e., consecutive dates should have
relatively similar summaries). Diversity is measured across dates and measures
the average KLD of each sentence with respect to all other sentences in a
leave-one-out manner. The final utility function is a weighted average of
these terms with user-defined weights and can be defined at a local level (to
evaluate individual time periods) and a global level (to evaluate the full
timeline). To find the sentences, this utility function is optimized in an
iterative manner by replacing sentences in the date summaries and improving
the utility value in each step using a dynamic programming algorithm that
considers both local and global constraints.

Li et al. (Li and Li, 2013a) propose a topic modeling approach for timeline
extraction from news called Evolutionary Hierarchical Dirichlet Process (EHDP)
to capture the evolution pattern of news topics. This model extends
Hierarchical Dirichlet Process models (Teh et al., 2006) by incorporating time
dependencies and background information. In particular, it adds a new dynamic
Dirichlet mixture model. Using this proposed topic model, a series of
sentences are selected to represent each time period in the timeline based on
the weighted average of three criteria: relevance (the summary should be
related to the overall query), coverage (the summary should generalize the
important topics in each time period), and coherence (each summary should be
coherent with neighboring time periods). To score these criteria, the authors
propose a topic scoring algorithm based on KLD that leverages their new topic
model. The selected sentences are used to represent the relevant events in
each time period.

RaRE (Rank and RErank) (Nguyen et al., 2014) is a system for building
timelines of events from news articles based on a user query. In particular,
it extracts timelines in three steps: temporal clustering based on salient
dates, event relevance, salience scoring, and sentence re-ranking using an
iterative algorithm that seeks to reduce redundancy. The method has an
underlying assumption that each document represents a single event that can be
described by a single sentence. The temporal clustering step identifies
salient dates based on the number of occurrences of the date in the documents.
The sets of events linked to a specific salient date are called temporal
clusters. Furthermore, as a preprocessing step, events are clustered into
thematic clusters inside each date using hierarchical clustering based on
normalized Manhattan distance and a user-specified threshold. The event
relevance and salience scoring steps use these criteria to rank events (i.e.,
documents) inside each temporal cluster. In particular, it uses four metrics:
event relevance, thematic cluster relevance, event salience, and date
salience. Event relevance is based on cosine similarity with the initial
query. Thematic cluster relevance is based on the similarity of its thematic
cluster with the initial query based on the average relevance of each event in
the cluster. Event salience is based on the frequency of terms on a specific
date. Date salience is based on the (normalized) total relevance of all events
happening on that date. Finally, the sentence re-ranking step measures the
frequency of unused terms on each date for a specific event to reduce
redundancy.

Another topic modeling approach uses a time-dependent Hierarchical Dirichlet
Tree Model (Li et al., 2015) to capture the evolution of news topics using the
Dirichlet Tree distribution—a generalization of the Dirichlet distribution
(Dennis III, 1991). In particular, the model represents topic distributions in
sentences using a tree of fixed depth. Each sentence is associated with a path
and with a topic vector and each node has its own topic distribution over
words. Using the proposed topic model, sentences are selected by first
locating candidate words on the nodes of the tree based on the Jensen-Shannon
(JS) divergence of sentences and KLD between word collections. Next, the
candidate sentences are scored based on the weighted average of the following
criteria: focus (the timeline should be relevant to a given query), coherence
(the sentences should be correlated), and coverage (the sentences and
documents should be representative).

Wu et al. (Wu et al., 2017) propose a sentence-based approach to generate
timelines. In particular, all the sentences that contain a user-defined query
word are split by date and used to generate a date vector representing that
specific date. Sentences that do not include parseable dates are grouped based
on similarity with the date vector. All sentences are then ranked based on
similarity with their corresponding date vector and unrelated sentences are
filtered out based on a user-defined threshold. The highest-ranking sentence
is used to summarize each date.

Tikhomirov and Dobrov (Tikhomirov and Dobrov, 2018) propose a news timeline
generation approach from a query based on three steps: query extension, inter-
document graph extraction, and intra-document sentence ranking. Query
extension is based on pseudo-relevance feedback and consists of three query
levels, which are constructed using the most significant terms based on TF-IDF
weights. Next, as a preprocessing step, dates that have a frequency below a
statistically determined threshold are discarded. The next two steps use an
inverted pyramid (Keith Norambuena et al., 2020) heuristic, which assumes that
the upper part of the article contains the most important information and the
lower part of the article may contain references to important events from the
past. In particular, the inter-document graph extraction step constructs a
similarity matrix between the upper and lower parts of the documents. If the
similarity is above a specified threshold, then the articles are considered to
be linked, creating a similarity graph. Next, a ranking algorithm—LexRank
(Erkan and Radev, 2004b)—is used to determine the importance of each document.
Documents that are above a specified importance threshold are used to further
expand the original query one more time. Finally, to rank the final selected
sentences for the summary, a ranking metric is defined by taking into account
content similarity (using cosine similarity) with the extended query (i.e.,
maximizing relevance) and subtracting similarity with already extracted
sentences (i.e., minimizing redundancy).

WILSON (neWs tImeLine SummarizatiON) (Liao et al., 2021) is a query-based
timeline summarization method for news based on a divide-and-conquer approach
consisting of two major components: date selection and text summarization for
each selected date. For date selection, the method first tags temporal
expressions in sentences and constructs a date reference graph based on these
annotations. Next, the method assigns weights to the edges of the date
reference graph by taking the product of the number of references and temporal
distances with the references. Then, it uses the PageRank algorithm (Page et
al., 1999) on the extracted graph to find the most salient dates. However,
this approach leads to a bias towards older dates, as they have had more time
to get references. Thus, the model is augmented with an exponential recency
adjustment weight, which is used to initialize the Personalized PageRank
algorithm (Bahmani et al., 2010), which allows for non-uniform initial
distributions. Next, the daily summarization can be done using any multi-
document summarization approach. Specifically, the authors use TextRank
(Mihalcea and Tarau, 2004) based on BERT (Devlin et al., 2018) representations
to generate the summaries.

####  2.2.2. Pre-filtered Approaches

These approaches assume that the data set has already been filtered as part of
a pre-processing step. Thus, they do not explicitly model the query in their
extraction model.

Yan et al. (Yan et al., 2011a) propose a system to generate news timelines
using a trans-temporal summarization approach, where the summary for each time
period depends on its context—that is, nearby time periods. Before generating
the timeline, the system chooses the important time periods (e.g., specific
days) to be summarized based on burstiness. The timeline extraction approach
is based on two components: a global component—which defines the structure of
the overall summary and the inter-temporal relationships between each period
of the timeline—and a local component—which defines the summary in each time
period. The global component is based on a global graph that uses inter-date
dependency, which is computed using temporal proximity and a global affinity
model for each sentence based on PageRank. Furthermore, to ensure a diverse
set of sentences in the global component, the system incorporates DivRank into
the affinity model (Mei et al., 2010) to penalize the lack of diversity in the
sentence selection. Next, the local component is based on a local sentence
graph for each time period following a similar approach to the global graph.
To generate the final sentence selection in each time period, the system
optimizes a weighted ranking generated by both components.

Hu et al. (Hu et al., 2011) propose a timeline overview method for news based
on the concept of breakpoints—points in time where a significant development
or change occurs (i.e., important events). Their extraction approach consists
of three steps. First, they analyze topic activity using a Topic-Activeness
Hidden Markov Model (HMM) and discard inactive periods. In practice, this is
done by measuring whether there is new information using KLD and document
frequency. Next, the breakpoints are identified by detecting topic variations
in each time period using a topic mixture model—in particular, a generative
probabilistic mixture model (Mei and Zhai, 2005)—and a Theme-Transition HMM
model to model topic evolution. Specifically, breakpoints are identified by
using JS divergence to measure topic variation between two consecutive time
points. Then, a summary for each breakpoint is generated by selected
representative sentences—based on Jaccard similarity with topic keywords and
relevant entities.

Tran et al. (Binh Tran et al., 2013) present a supervised learning method to
extract timelines from news articles based on Linear Regression. Their model
first identifies salient dates based on burstiness (i.e., high-frequency
periods), and then selects the most representative sentences from the news
articles on each of these dates. In particular, the model uses surface-level
features (e.g., length and position of the sentences), coherence features
(e.g., causal and temporal signals), topic features (e.g., TF-IDF information
and cross-entropy), and time-related features (e.g., popularity over time and
use of temporal expressions) to determine the key sentences of each date.
Subsequent work by Tran et al. (Tran et al., 2013) used SVM-Rank instead of
linear regression and expanded upon this supervised framework. In particular,
they leverage three metrics to evaluate the event sentences: relevance,
novelty, and continuity. Relevance is learned using the SVM-Rank mentioned
earlier. Novelty is evaluated by measuring the non-overlapping n-grams over
the total n-grams between a candidate sentence and previously selected
sentences. Continuity is a measure of local coherence—there should be smooth
transitions in the timeline—that is computed as the average n-gram overlap of
all sentences in the current day with the previous summary. The final score is
based on a weighted average of these metrics. To learn the relevance function,
the authors leverage the same set of features from their previous work (Binh
Tran et al., 2013), but they also added an extra set of features about the
event itself. For example, they evaluated whether the sentences properly
represent the main event of the article, using the fact that the first
sentences should contain the most relevant information (following the inverted
pyramid structure). Thus, they evaluate the similarity between the sentence
summary and the first four sentences. Once the SVM-Rank method was trained,
the ranking is fed to a dynamic programming approach to optimize the final
score.

Huang and Huang (Huang et al., 2013) present an event storyline generation
method based on a mixture-event-aspect probabilistic model that can detect and
distinguish the different types of sub-events in the article data set. Their
model is an extension of Probabilistic Latent Semantic Analysis (Hofmann,
1999) and LDA (Blei et al., 2003). In particular, their model detects global
aspects (i.e., terms that are important throughout the whole story) and local
aspects (i.e., terms that are important in a specific event inside the story).
Based on the extracted aspect model, the bursty periods for each aspect are
extracted to measure their popularity on a certain date and detect relevant
events. Based on these results, it is possible to extract a timeline and
select the most representative sentences associated with both global and local
aspects to compose the final storyline with adjustable weights for the
aspects. Sentences are selected by minimizing the overall information loss
over each aspect. In particular, the LexPageRank algorithm (Erkan and Radev,
2004a) is used to rank sentences and KLD is used for sentence similarity.

Tran et al. (Tran et al., 2015a) propose a timeline summarization approach
based on article headlines. Their approach is based on a random walk model
using a topic-sensitive version of PageRank (Haveliwala, 2003) that selects
relevant headlines from the data set for each time period. There are three key
metrics to evaluate the relevance of a headline: informing value, spread, and
influence. The informing value depends on whether the headline provides
factual information or an opinion, review, or another non-informing category.
It is a binary value computed using a supervised learning approach based on an
SVM classifier to separate facts from opinion (Yu and Hatzivassiloglou, 2003).
Influence tries to measure the impact of an event on future events (e.g., “the
president resigns” would lead to a “new election” event) based on references
from future events using similarity between future news articles and the
headline of the event. Spread is based on the intuitive idea that a relevant
event will be reported in multiple news outlets—that is, its reporting will be
spread over multiple headlines. Thus, it is a measure of positive redundancy
and it is formally defined as the probability of a headline being duplicated.
To estimate whether two headlines are duplicates, the system uses a supervised
logistic regression model trained on semantic similarity measures based on
paraphrase detection literature (Mihalcea et al., 2006). Having defined these
elements, the goal is to maximize all three aspects to select the best
headlines. This is done by using PageRank on a graph of headlines, taking into
account both spread (graph edges) and influence (random walk probability), to
generate the final rankings. Next, to generate the final timeline for each
day, the resulting rankings are selected greedily, subject to redundancy
constraints, informativeness constraints, and a maximum number of headlines
per day.

Chen et al. (Chen et al., 2015) present a supervised timeline summarization
algorithm based on aging theory for news data sets. Aging theory (Chen et al.,
2003) is a model that tracks the life cycle of events using an energy
function, which increases when an event becomes popular and diminishes with
time. The method works by extracting sentences (i.e., specific events) and the
publication time from news articles and using a classification model built
with SVM to determine whether they belong in the output timeline. This
approach is based on surface-level features (e.g., noun frequencies and stop
word frequencies), importance features (e.g., latent semantic analysis
scores), topic features (e.g., topic word frequencies), an aging score feature
(i.e., changing coverage of an event over time), and a novelty feature. The
aging score is used to measure the life cycle of each term over time using a
recurrence relation with TF-IDF representations. The novelty score is based on
the Jaccard similarity of the current summary and the candidate sentence.

####  2.2.3. Others

Here we present works that use a sentence-level resolution but differ from the
majority of the other works that follow the traditional timeline summarization
approach. In particular, we consider works on extracting disaster storylines
from news and works that present variations on the traditional TLS task.

Disaster Storylines Zhou et al.’s works (Zhou et al., 2014, 2018) present a
framework to construct spatio-temporal storylines for disaster management from
news data based on how the disaster location moves over time (e.g., a typhoon
moving through different areas). This approach generates timelines for two
levels of representation: a global level that follows the progress of the
disaster through each location and a local level that focuses on a specific
location. To extract the storyline, a series of snippets (i.e., event
sentences) are extracted from the news articles using named entity recognition
methods and grouped together based on a similarity graph. Then, a set of
representative sentences is selected by finding the minimum dominating set
(Shen and Li, 2010) using a greedy algorithm. Next, an integer linear
programming approach is used to select the optimal sequence for the main route
of the disaster by maximizing the coherence of the story chain, subject to a
series of structural, chronological, and length constraints. In this method,
coherence is defined based on consecutive content similarity rather than word
influence. However, the key difference is that this formulation includes a
smoothness constraint, which is specifically designed to track the moving
location of disasters through time. Smoothness is based on simulating the
natural trajectory of a disaster. In particular, the constraints set a maximum
distance for consecutive events (i.e., avoiding jumps to locations too far
away) and seek to avoid acute angles that could be formed by two consecutive
connections (i.e., avoiding sharp turns in the trajectory of the disaster).
Once the main storyline has been constructed, the next step is to analyze the
local level storylines. For each main storyline event, a set of similar
articles are selected and used to construct a multi-view graph that represents
the event relationships based on content similarity. Then, a Steiner tree
algorithm is used on the multi-view graph to generate a local storyline for
that location.

Yuan et al. (Yuan et al., 2019) propose dTexSL, a disaster storyline
extraction approach that extends Zhou et al.’s works (Zhou et al., 2014,
2018). Unlike the previous approach, the news articles are first divided into
different subsets based on location and are represented using neural
embeddings. Locations are found by measuring the distance of the locations
described in each article—using named entity recognition to find location
references—and merging locations that are close enough based on a user-defined
threshold. Then, an integer linear programming approach is used to select the
key locations (i.e., document clusters). Instead of choosing events to
maximize coherence like before, the goal is to maximize the number of
documents covered on the map. The model has similar constraints as the
original approach: chronological order, length, and smoothness. Once the main
storyline has been constructed, a word embedding method is used to construct a
multi-view graph that represents the event relationships based on content
similarity. Using this graph, a set of representative articles are selected
based on two criteria: uniqueness—computed using information gain—and
relevance—computed using a measure of node importance. Then, a dynamic Steiner
tree algorithm is used on the multi-view graph to generate a local storyline
for that specific location. Finally, a traditional multi-document
summarization method (Goldstein et al., 2000) is applied to generate a high-
level event description for that specific location.

Task Variations Duan et al. (Duan et al., 2020) introduce another variation on
the timeline summarization task called comparative timeline summarization. In
this task, the goal is to provide timelines consisting of major contrasting
events from two data sets. Their approach is based on three core
characteristics: coverage, distinctness, and diversity. Coverage is based on
the idea that the timelines should cover most of the important information or
topics from each data set. Distinctness is based on the idea that the events
in a timeline should be distinct from the events on the other timeline at each
time point, to allow for a proper contrast between them. Diversity is based on
the idea that each timeline should cover a diverse set of events from its data
set. To model these attributes, the authors propose a dynamic Markov model
that is built around sentence similarity at a document level for each time
step. In particular, sentences are selected from news articles to describe
events based on local and global importance measures through the use of an
affinity-preserving mutually reinforced Markov random walk model based on the
PageRank algorithm. The output is a timeline that contains contrasting events
from both data sets.

Yu et al. (Yu et al., 2021) propose a variation on the basic timeline
summarization task, called Multi-TimeLine Summarization (MTLS). In this task,
events are represented as sets of sentences and computationally represented by
the neural embedding model sentence-BERT (Reimers and Gurevych, 2019). Given a
set of time-stamped news articles, MLTS seeks to automatically extract
timelines for important and different stories found in the data set. The
authors propose a framework to solve this task called 2SAPS (Two-Stage
Affinity Propagation Summarization). There are two key components in their
framework: an event generation module and a timeline generation module. The
event generation module seeks to extract important events from the document
collection. To do so, it uses an affinity propagation approach to cluster
similar sentences (Frey and Dueck, 2007) and to identify the event of the
article and any other previously referenced event. Furthermore, there is a
temporal similarity term that uses an exponential decay function to penalize
similarities of events that are temporally far away. Once the events are
identified, a subset of these events is selected based on a weighted average
of a salience metric—based on event frequency—and a consistency metric—based
on the intra-event similarity. Next, the timeline generation module has three
internal steps: event link, time selection, and timeline summarization itself.
Event linking is based on the weighted average between a co-reference score
(based on entities or terms shared between events) and semantic similarity
(e.g., cosine similarity). Based on these average scores, the system builds an
event graph and uses affinity propagation on it to determine the initial
clusters (i.e., timeline sets). Next, there is a timeline selection based on
the weighted average of timeline salience—the average event salience of the
timeline—and timeline coherence—the average semantic similarity scores between
chronologically adjacent events. The timeline summarizing step selects an
exemplar sentence for each event in the timelines, as the most typical and
representative member of each event. Finally, there is an add-on timeline
tagging step which assigns a label to each timeline, based on the most
frequent words of the events.

Summarize Dates First (SDF) (La Quatra et al., 2021) is a timeline
summarization pipeline that follows a different paradigm for timeline
summarization based on generating a summary for each individual date first,
and then selecting the most relevant dates using these summaries. This is
different from the traditional approach where the relevant dates are selected
first. Furthermore, this approach aggregates dates by leveraging higher-level
temporal references (i.e., references to previous events in the article). SDF
consists of three steps: temporal tagging, per-date summary extraction, and
summary-drive date selection. In the temporal tagging stage, the raw text is
annotated to identify date-level references (e.g., 31 December 2021) and high-
level references (e.g., last December). The per-date summary extraction step
uses any traditional sentence-based summarization algorithm from the multi-
document summarization literature (e.g., TextRank (Mihalcea and Tarau, 2004)).
Summary-driven date selection is the last step and uses a selection strategy,
called Graph-Based Date Selection, which uses graph ranking algorithms (e.g.,
PageRank, HITS). In particular, a directed date graph model is built using the
temporal references of the data set, where the edge weight connecting two
dates is influenced by the count of date-level references and the similarity
between the date summary and the high-level references to the earlier date.

###  2.3. Events as Documents

Here we present works that use a document-level resolution. We split the
discussion into two parts: methods that build upon the Connect the Dots
approach by Shahaf and Guestrin (Shahaf and Guestrin, 2010)—a seminal work in
the field of news narrative extraction—and others. We further divide the
presentation based on whether the methods are linear or graph-based. We note
that the works cataloged as others did not have a discernible pattern beyond
using a document-level resolution.

####  2.3.1. Connect the Dots Approaches

Linear Representations Shahaf and Guestrin (Shahaf and Guestrin, 2010)
proposed the Connect the Dots algorithm to extract temporal chains of
documents (i.e., timelines). In particular, they use an optimization approach
that seeks to maximize the overall coherence of the timeline. Coherence
measures the smoothness of a storyline, a coherent story should not have
drastic changes in content or topic. To implement this metric, they propose an
approach based on word influence—a measure of word relevance computed through
random walks on a word-document graph—and word activations—which measure
whether a specific word is active at a given point in the storyline. To
extract the story chains, they used linear programming to maximize coherence
subject to structural and temporal constraints. However, since linear
programming provides non-integer solutions, it required additional heuristics
to find the best chain by defining a rounding method. The linear programming
approach used in the original Connect the Dots implementation was
computationally expensive. Thus, Shahaf and Guestrin (Shahaf and Guestrin,
2012) proposed a new method to reduce computational costs and avoid the
approximate solutions from the linear program. In particular, they used a
best-first search algorithm based on an extension heuristic—given a chain of
documents, adding a new document to the chain will at most keep the same level
of coherence—and the original linear program to individually evaluate each
chain.

Expanding upon the Connect the Dots method, Zhu and Oates (Zhu and Oates,
2012) propose an algorithm to extract story chains from newswire articles that
connect two user-defined endpoints based on the following characteristics:
relevance (the articles on the chain should be relevant to the endpoints),
coherence (the transition between events should be smooth), low redundancy
(there should only be one representative article for every event of the
chain), and coverage (the chain should cover every important event). To
compute measures of these characteristics, the article proposes using random
walks on bipartite graphs formed by articles and words, where the weights are
given by TF-IDF representations. Thus, based on these criteria, their proposed
algorithm consists of two iterative stages. The first phase consists of a
divide-and-conquer bisecting search problem that adds articles to the story
chain. In particular, in this phase the algorithm finds the best article to
insert in the middle of each current link of the story chain (i.e., it bisects
the current links) based on coherence and relevance criteria. The second phase
consists of pruning redundant articles—by removing a certain percentage based
on how much coherence they would add to the current story chain—and irrelevant
articles—by removing events that are similar to each other and temporally
close with an exponential decay function. These phases are repeated until
there are no more articles to add or prune. A subsequent article by the same
authors (Zhu and Oates, 2014) revisits the story chain algorithm and extends
this approach by adding an intermediate clustering step that groups documents
into document clusters and words into word clusters. These clusters are used
to generate a new bipartite correlation graph that combines the weight of
individual documents and words through a weighted average to assign the edge
weights. Furthermore, the model adds a named entity bias that assigns a higher
weight to named entities compared to other terms. This is modeled through a
co-occurrence frequency matrix for entity pairs, which is then used to compute
a relevance score for each document in the data set based on the named
entities. In turn, these elements are used to modify the cluster and document
weights in the correlation graph.

Camacho Barranco et al. (Camacho Barranco et al., 2019) propose a storyline
extraction algorithm that takes a set of user-defined articles as a seed and
generates a timeline of articles based on a series of evaluation metrics.
First, the authors propose a temporal criterion to filter candidate documents
based on a range between the latest publication date of the seed articles and
a maximum threshold away from the earliest publication date of the seed
articles (i.e., in the interval $[t_{\min}-t_{threshold},t_{\max}]$). Next,
there is a topical criterion that measures how much a candidate article can
deviate from the seed articles based on KLD and LDA topics. Having defined
their basic framework, the authors then formalize an optimization problem to
extract the storylines by selecting article connections based on different
criteria: incoherence, similarity, overlap, and uniformity. Incoherence is
based on the average pairwise Soergel distance between documents—measured
using TF-IDF information for the entities of the document—with a temporal
factor to penalize temporally distant articles. Similarity is used as a
penalty factor to enforce diversity in non-adjacent articles of the storyline,
implemented as a negative exponential factor based on the Soergel distance.
Both of these metrics are weighted by a relevance factor of the documents and
are smoothed using modified Gaussian distributions to measure event overlap.
Next, an overall overlap factor for the storyline is computed, assigning a
penalty based on the difference between publication dates and a user-defined
threshold. The overlap factor ensures that the breakpoints occur at
sufficiently distinct dates. The uniformity penalty seeks to avoid the case
where the optimal solution selects purely irrelevant events as optimal by
penalizing uniform weights. The objective function to minimize consists of the
sum of the product between incoherence and similarity, multiplied by the
overlap and uniformity penalties.

Graph-based Representations Metro Maps (Shahaf et al., 2012, 2013a) are an
extension of the Connect the Dots approach that represents more than a single
storyline using a directed acyclic graph of events. In particular, the metro
maps method is a structured summarization approach that captures the evolution
of multiple stories and their interactions. The stories are represented using
a metro map metaphor, where each metro line represents a story and stations
represent key events. Metro lines intersect in specific stations, representing
how storylines connect with each other. This representation is extracted by
solving an optimization problem. In particular, the goal is to maximize
connectivity, subject to coverage and coherence constraints. Coverage is
computed based on how well specific terms or keywords are represented in the
selected events and is defined using a submodular function that encourages
diversity (e.g., if a term is already covered, adding a document that covers
it provides little extra coverage). These keywords depend on the specific
corpus or domain of application. Coherence is defined following Shahaf et
al.’s previous work (Shahaf and Guestrin, 2010, 2012). Finally, connectivity
is defined as the number of stories that intersect which is used to ensure
that the final metro map is connected. The optimization problem is solved in
phases. First, a series of coherent candidate metro lines are selected based
on a divide-and-conquer approach, which constructs long lines from shorter
ones and encodes them in a graph. Then, the method extracts a set of coherent
lines that maximize coverage using an approximation algorithm based on the
submodularity of the coverage function (otherwise finding these lines is an
NP-hard problem). Finally, connectivity is increased using a local search
approach that substitutes lines without sacrificing coverage.

Similar to the metro maps metaphor, the Narrative Maps model (Keith Norambuena
and Mitra, 2021) provides a framework to extract and represent narratives
based on a route map metaphor. The narrative and its stories are shown as a
series of routes through landmarks, which represent the events. In
computational terms, the narrative is modeled through a directed acyclic graph
of events. The events are represented through neural embeddings of article
headlines. The graph is extracted by solving an optimization problem defined
following a linear programming formulation similar to the Connect the Dots
approach. The optimization problem is based on maximizing coherence subject to
coverage constraints. Coherence measures how much sense it makes to connect
two events together and is defined as the geometric mean of the content
similarity of events—using cosine or angular similarity—and their topical
similarity—based on JS similarity of their topic distributions based on
clustering. Coverage is measured by the average percentage of topical clusters
covered by the selected events based on their topic distributions. Once the
optimal map has been found, the main storyline is extracted by normalizing the
coherence values of the edges into probabilities and finding the maximum
likelihood path. Then, a set of representative landmarks (i.e., important
events) of each story by finding the maximum antichain, which corresponds to
the point of the maximum width of the graph.

####  2.3.2. Others

Linear Representations Guha et al. (Guha et al., 2005) propose an event
threading approach based on a graph decomposition method that generates
document timelines. In particular, they propose decomposing a directed acyclic
graph into disjointed node paths that ensure that as many nodes as possible
participate in at least one path (i.e., they seek to maximize a notion of
coverage). The first step is to construct the graph, they propose doing this
based on important terms (or even entities) in the document collection and
their co-occurrence. Furthermore, documents are modeled following a bag of
words approach, although the method is also designed to handle TF-IDF
representations. Once the graph is constructed, the next step is to solve the
event thread extraction problem. To do this, they propose three formulations:
an exact algorithm, a maximum approach, and a dynamic programming approach.
The first method is an exact algorithm based on minimum cost flow, which has a
high computational cost and is impractical. The second is an approximation
algorithm based on maximum matching in bipartite graphs that solves the thread
extraction problem for a fixed maximum size. The third method is based on an
approximation algorithm that uses dynamic programming to solve the thread
extraction problem for a range of thread sizes.

Laban and Hearst (Laban and Hearst, 2017) present newsLens, a system to build
and visualize long-ranging news stories. In particular, their system groups
news articles based on their topics—based on a graph clustering approach—and
then selects a sample of headlines from salient dates—based on the frequency
of publications. In more detail, the first step in their extraction approach
is to construct a keyword graph for a starting time period using TF-IDF
representations of the articles. Next, a local topic graph is created based on
a user-defined threshold for the number of shared keywords between articles.
After the initial time period, a sliding window approach with a user-defined
length is used to handle the rest of the data. For each time period, a local
topic graph is created and compared with the graph from the previous period to
check for three types of relationships: linking (connecting a topic from the
current graph to a pre-existing topic), splitting (dividing a pre-existing
topic into new topics in the current period), or merging (combining separate
topics from the previous step into a single one of the current period).
However, this approach is not able to handle stories that have long-time gaps
between publications. To handle these cases, the content similarity of non-
overlapping stories is analyzed and merged if above a specific threshold.
Afterward, their method assigns a name to the storyline by extracting noun
phrases from the news articles and scoring them based on multiple criteria
(e.g., length, type of noun, abstractness, and frequency). Finally, salient
dates are selected based on local frequency changes, and representative
headlines are sampled randomly from these dates to generate the final timeline
visualization.

Graph Representations Uramoto and Takeda (Uramoto and Takeda, 1998) proposed a
graph-based approach to model the relationships between news articles. In
particular, they use a directed graph based on temporal ordering and event
similarity. This is the earliest article that fits with our definitions of
event-based narrative representations for news narratives that we found. In
particular, the authors use the concepts of genus and differentia words. For
adjacent articles, genus words are computed using the intersection of their
word sets and represent already known information in the story. In contrast,
differentia words are built from the set difference between the articles (in
temporal order) and represent new knowledge in the story. Thus, differentia
words are more important when trying to find coherent sequences of articles.
The events are represented with a variation of TF-IDF that assigns more weight
to differentia words.

Tannier and Moriceau (Tannier and Moriceau, 2013) propose an approach for
building multi-document event threads from news articles. In particular, they
use a supervised learning approach with a series of classifiers to define the
type of relationship between news articles: same-event, continuation, or
reaction. The output of this method is a temporal event graph, where the nodes
correspond to events (represented as news articles) and the edges are labeled
with the corresponding relationships. In particular, the first step is to
determine whether there is a connection at all between the articles. To do so,
an initial classifier is implemented using a series of content similarity
features (e.g., word overlap, cosine similarity, and similarity of the first
sentences) to construct the initial temporal graph. However, this is not
enough to find all potential relationships and a second-level classifier is
included that takes into account the results from the previous classifier by
using degree-based features from the temporal graph. Next, after a connection
has been established, another classifier determines whether this connection is
based on the articles referring to the same news event—same-event
connection—or based on a continuation—when an event is a direct continuation
or consequence of a previous one. This classifier relies on date-based
features (e.g., differences in publication time, date references, and
references between events themselves) and keyword-based features (e.g., usage
of temporal words, reaction words, or opinion words). The output is fed into
another classifier that leverages degree-based features again to find more
relationships. Due to the transitive nature of the same-event and continuation
relationships, a post-processing step takes the graph and constructs the
transitive closure for these specific relations. Afterward, a final classifier
uses the same features to determine whether a continuation is a reaction—a
subset of continuations that relate the reactions of people (or organizations)
to an event.

Hu et al. (Hu et al., 2014) propose a system to model storyline interactions
from news events. Their approach generates a series of event timelines
focusing on specific entities or topics and their interactions with each
other. In particular, this results in a directed graph connecting multiple
events. In contrast to other approaches, the underlying representation of
events is based on the main event descriptors (i.e., the answers to Who, What,
When, Where, Why, and How) (Keith Norambuena et al., 2020) which are extracted
directly from each article and represent the key elements of the event. Based
on this information, a coherence graph is constructed and used to identify the
storylines through a random walk. Coherence is defined by three factors:
subtopic consistency, entity relatedness, and time continuity. To measure
subtopic consistency, the first step is to use a generative probabilistic
mixture model to discover latent subtopics. Then, JS divergence is used to
measure the distance of topic distributions between articles. Next, entity
relatedness is measured by the average affinity of the entities from each pair
of articles using normalized point-wise mutual information. The time
continuity factor is simply defined as an exponential penalty term dependent
on the temporal distance between events. The coherence graph is built by
creating edges between documents that have a coherence score above a given
threshold. Based on the coherence graph, a series of informative events that
connect multiple storylines are identified. Specifically, a topic-sensitive
PageRank algorithm (Haveliwala, 2003) is used to discover these events. In
turn, these events feed the storyline generation algorithm, an iterative
algorithm that selects a single informative event for each story for each day.

Bögel and Gertz (Bögel and Gertz, 2015) present a temporal linking framework
based on the concept of article references. In particular, they exploit the
structure of news articles to construct an information network. Instead of
comparing articles based on overall content similarity, they exploit the use
of lead paragraphs, explanatory paragraphs, and additional information
paragraphs in typical news articles. Specifically, they construct the network
based on temporal expressions, keywords, and entity names. To select valid
event connections, the first step is to filter based on temporal information
contained in the text based on a temporal tagger. Next, connections are
evaluated based on the similarity of the lead paragraph of a news article with
all the other paragraphs of another news article (i.e., capturing references
to the event). Similarity is computed based on the entities and keywords
mentioned in each paragraph based on a weighted average of Jaccard and cosine
similarity. Finally, irrelevant edges are pruned based on a user-defined
threshold. However, some non-relevant edges are kept if they fulfill the role
of a support path—paths that have non-relevant edges but share endpoints with
fully relevant paths—that provide more evidence of two events being connected.
The output is a directed graph based on references, not necessarily acyclic,
as there are future temporal references in some articles.

###  2.4. Events as Clusters: Event Evolution and Threading

Now, we present works that use a cluster-level resolution. We divide the
discussion into two parts: works related to event threading (Nallapati et al.,
2004) and evolution (Yang et al., 2006), and others.

####  2.4.1. Event Threading and Evolution

Nallapati et al. (Nallapati et al., 2004) use a directed graph model to
represent to capture the structure and dependencies of events in a news topic.
They call this extraction process event threading. They represent each event
as a cluster of news articles. Event threading is a supervised method that
consists of two phases: clustering documents and modeling dependencies. The
clustering process starts with a cluster for each document in the data set and
merges them iteratively based on similarity until the similarities fall below
a predefined threshold. The authors evaluate three types of cluster similarity
on the average link, complete link, or single link of the clusters based on
document similarities. Document similarities are based on content similarity
(e.g., cosine similarity), common locations, and common entities. Furthermore,
there is an exponential decay term based on the temporal distance to penalize
larger temporal distances between documents. Next, dependency modeling uses
surface-level features of the document clusters, such as word distributions
and time-ordering of the news articles. Based on this information, the authors
propose several link extraction criteria (complete-link, simple threshold,
nearest parent, best similarity, and maximum spanning tree). These approaches
rely on temporal order, similarity information, or structural information.

SToRe (Storyline-based Topic Retrospection) is a topic retrospective system
(Lin and Liang, 2006; Lin et al., 2007; Lin and Liang, 2008) that extracts the
main storyline from a given news topic and provides a summary of the topic
based on this storyline. In particular, the extraction process consists of
four phases: event identification, topic structure identification, main
storyline construction, and storyline-based summarization. In the event
identification phase, similar news articles will be clustered together to
represent a single event using self-organizing maps. In the topic structure
identification step, the events are linked together based on whether their
similarity exceeds a specific threshold. To compute similarity, the events are
represented with a vector of term weights using the concepts of genus and
differentia words (Uramoto and Takeda, 1998). Then, cosine similarity is used
to compare the event vectors. Next, in the main storyline construction step,
an MST is extracted from the constructed topic structure. The MST is based on
the relevance of each event with respect to the topic. The MST is used to
generate a timeline of events, and it is further extended with small side
branches of other relevant events based on a specific threshold. Finally, in
the storyline-based summarization, a summary is generated for each event based
on the news articles contained in its cluster using accumulated weight summary
(Goldstein et al., 2000).

Yang et al. (Yang et al., 2006, 2009) use directed acyclic graphs to represent
the evolution of events in online news. They call their approach event
evolution graphs, which represent temporal and causal relationships between
events. Events are defined as sets of news articles and are represented as the
average of the TF-IDF vectors of each article they contain. We note that the
proposed method assumes that events and their corresponding articles are
already computed. In practice, this would require a clustering step before
constructing the graph. These events are linked together based on their
similarity and a user-specified threshold, which is computed based on content
similarity (e.g., cosine similarity), temporal proximity, and document
distributional proximity (which penalizes bursty periods with many articles
about the same event). The latter two terms are represented through
exponential decay factors. Furthermore, users are able to reduce the temporal
granularity of the event evolution graph, which merges specific events that
occur in short time frames.

Qiu et al. (Qiu et al., 2008) propose another event evolution graph extraction
method. Their construction method follows an iterative approach based on
content similarity and temporal order. In particular, documents are first
grouped into clusters using the OHC method (Qiu and Tang, 2007) in the first
time period, which gives rise to the initial events. Next, the PRAC method
(Qiu et al., 2007) is used to build classifiers and determine whether the
documents of the next time period are continuations of a cluster identified in
the previous period. If so, a new event node is created using the identified
cluster as its parent. This process is repeated until the last time period.
Next, twigs—paths that die before the end of the timeline—are removed based on
a user-set tolerance, and equivalent event nodes are merged to reduce graph
complexity.

TSCAN (Topic Summarization and Content ANatomy) (Chen and Chen, 2008, 2012) is
a method to analyze news data that produces a global summary and constructs an
event evolution graph. We focus on the event graph component of this method.
First, news articles are grouped into themes obtained through a matrix
factorization approach with TF-IDF document representations. Next, the news
articles of each theme are temporally segmented using an energy value
threshold based on eigenvalues from the matrix representation. In practice,
this generates clusters of documents based on frequency, which are associated
with the nodes of the event evolution graph. The evolution graph is a directed
acyclic graph, where the edges are constructed using temporal
similarity—computed using the temporal distance between events, with special
cases to consider event overlap—and content similarity—based on cosine
similarity.

Khurdiya et al. (Khurdiya et al., 2011) propose a system that extracts
directed graphs to represent stories from news data using multi-perspective
links. Each node of this graph is associated with multiple news articles. The
system uses LDA to extract topics in each time unit (e.g., a day). The
extracted topics are associated with sets of articles based on the strength of
the topic in each article and form the basis of the story identification
model. We note that these topics and their article sets correspond to the
notion of event that we use in this survey. Next, article sets are linked
chronologically based on topic correlation (e.g., Pearson’s correlation
coefficient) and a user-defined threshold, generating a directed graph of
events.

Wei et al. (Wei et al., 2014) identify event episodes in news data sets and
construct a temporal episode graph (i.e., an event graph under our definitions
in the survey). In particular, this article shows a discovery mechanism that
organizes news documents into events using novel TF-IDF representations that
incorporate a temporal component. Then, the system builds a link structure
based on intercluster similarity measures. The first proposed event
representation, called TF-IDFTempo, gives more weight to features with
consecutive occurrences in a sequence of documents (i.e., it incorporates the
surrounding context of the document) by modifying the IDF component of TF-IDF
to consider the order of the documents. However, this approach is too strict
and is unable to model overlapping events. Moreover, it also has a high bias
towards low-frequency articles that are temporally close. Thus, the authors
propose a second representation, called TF-Enhanced-IDFTempo which modifies
the IDF component by adopting the significance factor proposed by Luhn (Luhn,
1958) and a temporal gap threshold to allow for short discontinuities in
feature appearances. These representations are used with Hierarchical
Agglomerative Clustering (HAC) (Voorhees, 1986) to construct the article
clusters that represent the events. For the purposes of clustering, document
similarity is defined by content similarity (e.g., cosine similarity) and a
negative exponential penalty for temporally distant documents.

Huang et al. (Huang et al., 2014) propose a different event evolution approach
to build and analyze event relationships based on three types of event
connections. In particular, they define a co-occurrence dependence
relationship, an event reference relationship, and a temporal proximity
relationship. The authors define events as a set of news articles and identify
them through clustering and topic modeling using a combined similarity measure
that leverages LDA and a TF-IDF document model with cosine similarity. Once
the events are identified, the method extracts a series of core features
(i.e., key entities and terms of the article) by analyzing the lead of the
articles and evaluating whether their frequency is above a specified
threshold. These core features are used to construct a vectorial
representation of the events. For the co-occurrence relationship, the method
computes the aggregation of all mutual information between all features of the
event, generating a symmetric matrix that represents all event-event
relationships. For the event reference analysis, the method identifies shared
core features and defines the degree of event reference based on the frequency
of references in an event to the core features of a previous event, adjusted
by the weight of these terms in the referencing event. Temporal dependency is
evaluated using an exponential decay formula.

Event Phase Oriented News Summarization (EPONS) (Wang et al., 2018) is a
timeline summarization approach that assumes that a story summary contains
multiple timelines, each one corresponding to a specific event. To model the
semantic relations of news articles, EPONS uses a graph model, called Temporal
Content Coherence Graph (TCCG), which is an event graph based on two metrics:
content coherence and temporal influence. Content coherence is based on the
weighted average of topic level similarity—modeled by JS divergence over an
LDA topic distribution—and entity-level similarity—modeled over a ranking of
named entities using the Tanimoto coefficient. Temporal influence is modeled
through a Hamming (cosine) kernel to properly separate temporally distinct
events. The TCCG is built by selecting edges that are above user-specified
thresholds in each metric. Based on this graph, EPONS uses a modified
structural clustering approach to group the news articles into different
events. Furthermore, small clusters of similar articles are filtered out to
ensure that the events are modeled properly. This post-processing is done by
using four quality metrics on a pre-trained logistic regression classifier:
percentage of new articles, time interval length, pairwise topic similarity,
and pairwise entity similarity. Having identified the events, it is now
necessary to construct the individual summaries and finalize the timeline. To
do so, a vertex-reinforced random walk (Mei et al., 2010; Pemantle, 1992) is
used to rank the relevance of news articles inside each event, in a similar
manner to PageRank. Next, a supervised model is used to determine whether the
headlines are factual (i.e., they are reporting a specific event) or an
opinion, as opinion-based headlines are not considered useful for timelines
and must be filtered out. Finally, an optimization method is used to maximize
the total relevance, subject to non-redundancy constraints (i.e., disallowing
events that are too similar) to select the news articles.

Cai et al. (Cai et al., 2019) propose a method to extract Temporal Event Maps
(TEM) based on the content dependence degree and component event reference
degree for each pair of events. TEMs are directed graphs that have events as
nodes, relations as edges, edge weights representing the strength of event
relationships, and node weights representing the importance of each event.
Events are defined as groups of related documents and identified using a LDA
model. After obtaining the events, the next step is to compute the two core
metrics that define the temporal event maps. The content dependence degree is
defined as the aggregation of all mutual information among the features of
each event. The content reference degree is defined by the presence of core
features of an event—salient terms based on frequency—in other events. Unlike
content dependence, this is not a symmetric relationship between events. To
construct the temporal event maps, the first step is to order events based on
starting time. Then, connections are added for events that surpass a user-
specified threshold for the product of content dependence and event reference
degrees, which provides the edge weights for the graph. Finally, a ranking
procedure based on PageRank is used to generate the event importance values.

####  2.4.2. Others

Information Cartography Continuing with their work on metro maps, Shahaf et
al. (Shahaf et al., 2013b, 2015) propose a new framework called Information
Cartography that features zoomable metro maps, allowing users of the map to
visualize the news at different levels of resolution, allowing the user to
zoom in to specific metro stops and generate a new map. Metro stops and events
are no longer represented as single documents but as clusters of events. The
articles are segmented into time windows and clusters are computed using a
community-detection algorithm on word co-occurrence graphs. To extract the
maps, an optimization problem is defined based on finding the best structure
for the map, relying on the idea of minimizing the total number of storylines
(to reduce unneeded complexity) and maximizing the number of covered clusters
(to ensure that the stories are well covered). This approach leads to simple
stories being modeled as a single metro line and more complex stories
requiring the use of multiple shorter lines. Furthermore, a series of
additional constraints for story coherence, cluster quality, and map size is
imposed.

Building upon the concept of metro maps and information cartography, Xu and
Tang (Xu and Tang, 2018) propose a narrative representation in the context of
societal risk events (e.g., earthquakes) called Risk Maps. These maps follow
the same basic representation of information cartography with events being
represented as clusters of documents. However, one key difference is that this
approach leverages advances in text representation by using neural word
embeddings for news articles before clustering. To obtain the risk map, the
authors choose to maximize coverage as their primary objective, followed by
connectivity, subject to a minimal coherence constraint. Coverage is defined
based on how well each cluster is covered by the different storylines.
Connectivity is simply the number of storylines that intersect. Coherence is
defined based on the Jaccard similarity of consecutive clusters in the
storylines. The optimization problem is solved using a greedy algorithm that
finds the best path among clusters at each step.

Story Forests Liu et al. (Liu et al., 2017, 2020) propose the Story Forest
approach, where different stories are constructed and represented as a forest
of event trees. First, events are clustered using a community detection
approach on word co-occurrence graphs using betweenness centrality. Next,
documents are associated with each topic through a similarity based on TF-IDF
representations. Afterward, a second step groups documents together based on a
supervised classifier (SVM) to determine whether pairs of documents refer to
the same event based on TF-IDF features and similarities between the contents
and titles of articles. The story forest is built iteratively by adding events
into its trees by using three operations: merge, extend and insert. Before
adding the events it is necessary to determine the correct story tree. This is
done based on a measure of compatibility, computed as the Jaccard similarity
of the keywords of the event and the tree. If no trees are related to the
event, a new tree is created with the event as its root. To add the event to
an existing tree, the method first tries to merge it with any of the existing
events into the same node using the previously trained SVM classifier.
Otherwise, the method scans all the nodes to identify which tree to extend
based on a measure of connection strength determined by three elements:
compatibility, coherence, and time penalty. Compatibility is measured by the
similarity of their centroids based on cosine similarity. Coherence is a
story-level measure that takes into account the path of events from the root
of the tree to the newly appended event by measuring the average consecutive
compatibility value. Finally, the time penalty is an exponential decay factor
that depends on temporal distance. If none of the events are appropriate, the
event is inserted as a new node connected to the root.

##  3\. Narrative Extraction Criteria

In this section, we present a summary of the different construction criteria
found in the reviewed articles. These criteria refer to either an evaluation
metric or additional information used in the extraction algorithms themselves
as part of an objective function (e.g., coherence optimization), selection
criteria (e.g., filtering based on content similarity or topic distribution
similarity), and other types of extraction heuristics (e.g., leveraging
article structure to compute content similarity or evaluating the use of
opinionated language). The first part of Table 2 provides an overview of the
different construction criteria. We note that these criteria are not mutually
exclusive and can be combined as needed.

|  | Extraction Criteria | Evaluation Metrics
---|---|---|---
Year | Reference |  Relevance |  Surface Similarity |  Topic Distribution |  Entities |  Coherence |  Coverage |  Dispersion |  Diversity and Redundancy |  Output Structure |  Article Structure |  Content References |  Temporal References |  Burstiness and Frequency |  Temporal Distance |  Traditional IR Metrics |  Summarization Metrics |  Ranking Metrics |  Clustering Metrics |  Coherence |  Coverage |  Dispersion |  Diversity and Redundancy |  User Performance |  User Perception |  Other or N/A
1998 | Uramoto and Takeda (1998) |  | $\times$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | $\times$
2004 | Nallapati et al. (2004) |  | $\times$ |  | $\times$ |  |  |  |  |  |  |  |  |  | $\times$ | $\times$ |  |  |  |  |  |  |  |  |  |
2004 | Chieu and Lee (2004) |  | $\times$ |  |  |  |  |  |  |  |  |  |  | $\times$ | $\times$ |  |  |  |  |  |  |  |  |  | $\times$ |
2005 | Guha et al. (2005) |  | $\times$ |  |  |  | $\times$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | $\times$
2006 | Yang et al. (2006) |  | $\times$ |  |  |  |  |  |  |  |  |  |  | $\times$ | $\times$ | $\times$ |  |  |  |  |  |  |  |  |  |
2006 | Lin and Liang (2006) |  | $\times$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | $\times$ | $\times$ |
2007 | Lin et al. (2007) |  | $\times$ |  |  |  |  |  |  |  |  |  |  |  |  | $\times$ |  |  |  |  |  |  |  |  |  |
2008 | Chen and Chen (2008) |  | $\times$ |  |  |  |  |  |  |  |  |  |  | $\times$ | $\times$ |  | $\times$ |  |  |  |  |  |  |  |  |
2008 | Qiu et al. (2008) |  | $\times$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | $\times$
2008 | Lin and Liang (2008) |  | $\times$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | $\times$ | $\times$ |
2009 | Yang et al. (2009) |  | $\times$ |  |  |  |  |  |  |  |  |  |  | $\times$ | $\times$ | $\times$ |  |  |  |  |  |  |  |  |  |
2010 | Shahaf and Guestrin (2010) |  |  |  |  | $\times$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | $\times$ |
2011 | Yan et al. (2011b) | $\times$ |  |  |  | $\times$ | $\times$ |  | $\times$ |  |  |  |  |  |  |  | $\times$ |  |  |  |  |  |  |  |  |
2011 | Yan et al. (2011a) | $\times$ |  |  |  |  |  |  |  |  |  |  |  | $\times$ | $\times$ |  | $\times$ |  |  |  |  |  |  |  |  |
2011 | Hu et al. (2011) |  | $\times$ | $\times$ | $\times$ |  |  |  |  |  |  |  |  |  |  | $\times$ |  |  |  |  |  |  |  |  |  |
2011 | Khurdiya et al. (2011) |  |  | $\times$ |  |  |  |  |  |  |  |  |  |  |  | $\times$ |  |  |  |  |  |  |  |  |  |
2012 | Zhu and Oates (2012) | $\times$ | $\times$ |  |  | $\times$ |  |  | $\times$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | $\times$ |
2012 | Chen and Chen (2012) |  | $\times$ |  |  |  |  |  |  |  |  |  |  | $\times$ | $\times$ |  | $\times$ |  |  |  |  |  |  |  |  |
2012 | Shahaf and Guestrin (2012) |  |  |  |  | $\times$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | $\times$ |
2012 | Shahaf et al. (2012) |  |  |  |  | $\times$ | $\times$ |  |  | $\times$ |  |  |  |  |  |  |  |  |  |  |  |  |  | $\times$ |  |
2013 | Binh Tran et al. (2013) | $\times$ | $\times$ | $\times$ |  | $\times$ |  |  |  |  | $\times$ |  | $\times$ | $\times$ |  | $\times$ | $\times$ |  |  |  |  |  |  |  |  |
2013 | Li and Li (2013a) | $\times$ |  | $\times$ |  | $\times$ | $\times$ |  |  |  |  |  |  |  |  |  | $\times$ |  |  |  |  |  |  |  |  |
2013 | Tran et al. (2013) | $\times$ | $\times$ | $\times$ |  | $\times$ |  |  |  |  | $\times$ |  | $\times$ | $\times$ |  |  | $\times$ |  |  |  |  |  |  |  |  |
2013 | Huang et al. (2013) |  |  | $\times$ |  |  |  |  |  |  |  |  |  | $\times$ |  |  | $\times$ |  |  |  |  |  |  |  |  |
2013 | Tannier and Moriceau (2013) |  | $\times$ |  |  |  |  |  |  | $\times$ |  |  | $\times$ |  |  | $\times$ |  |  |  |  |  |  |  |  |  |
2013 | Shahaf et al. (2013a) |  |  |  |  | $\times$ | $\times$ |  |  | $\times$ |  |  |  |  |  |  |  |  |  |  |  |  |  | $\times$ |  |
2013 | Shahaf et al. (2013b) |  |  |  |  | $\times$ | $\times$ |  |  | $\times$ |  |  |  |  |  |  |  |  |  |  |  |  |  | $\times$ |  |
2014 | Nguyen et al. (2014) | $\times$ | $\times$ | $\times$ |  |  |  |  | $\times$ |  |  |  |  | $\times$ |  | $\times$ | $\times$ |  |  |  |  |  |  |  |  |
2014 | Zhu and Oates (2014) | $\times$ | $\times$ |  | $\times$ | $\times$ |  |  | $\times$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | $\times$ |
2014 | Huang et al. (2014) |  | $\times$ | $\times$ |  |  |  |  |  |  |  | $\times$ |  |  | $\times$ | $\times$ |  |  |  |  |  |  |  |  |  |
2014 | Wei et al. (2014) |  | $\times$ |  |  |  |  |  |  |  |  |  |  | $\times$ | $\times$ | $\times$ |  |  |  |  |  |  |  |  |  |
2014 | Hu et al. (2014) |  |  | $\times$ | $\times$ |  |  |  |  |  |  |  |  |  | $\times$ | $\times$ | $\times$ |  |  |  |  |  |  |  | $\times$ |
2014 | Zhou et al. (2014) |  | $\times$ |  |  | $\times$ |  |  |  | $\times$ |  |  |  |  |  |  | $\times$ |  |  |  |  |  |  |  |  |
2015 | Tran et al. (2015a) | $\times$ |  |  |  |  |  |  | $\times$ |  |  |  | $\times$ | $\times$ |  | $\times$ |  |  |  |  |  |  |  |  | $\times$ |
2015 | Li et al. (2015) | $\times$ | $\times$ | $\times$ |  | $\times$ | $\times$ |  |  |  |  |  |  |  |  |  | $\times$ |  |  |  |  |  |  |  |  |
2015 | Bögel and Gertz (2015) |  | $\times$ |  | $\times$ |  |  |  |  |  | $\times$ |  | $\times$ |  |  | $\times$ |  |  |  |  | $\times$ |  |  |  |  |
2015 | Chen et al. (2015) |  | $\times$ | $\times$ |  |  |  |  |  |  |  |  |  |  | $\times$ | $\times$ | $\times$ |  |  |  |  |  |  |  |  |
2015 | Shahaf et al. (2015) |  |  |  |  | $\times$ | $\times$ |  |  | $\times$ |  |  |  |  |  |  |  |  |  |  |  |  |  | $\times$ |  |
2017 | Wu et al. (2017) |  | $\times$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | $\times$
2017 | Liu et al. (2017) |  | $\times$ |  |  | $\times$ |  |  |  |  |  |  |  |  | $\times$ |  |  |  | $\times$ |  |  |  |  |  | $\times$ |
2017 | Laban and Hearst (2017) |  |  | $\times$ |  |  |  |  |  |  |  |  |  | $\times$ | $\times$ |  |  |  |  |  |  |  |  |  |  | $\times$
2018 | Wang et al. (2018) | $\times$ |  | $\times$ | $\times$ |  |  |  | $\times$ |  |  |  |  |  | $\times$ | $\times$ |  | $\times$ |  |  |  |  |  |  |  |
2018 | Tikhomirov and Dobrov (2018) | $\times$ | $\times$ |  |  |  |  |  |  |  | $\times$ | $\times$ |  | $\times$ |  |  | $\times$ |  |  |  |  |  |  |  |  |
2018 | Xu and Tang (2018) |  |  |  |  | $\times$ | $\times$ |  |  | $\times$ |  |  |  |  |  |  |  |  |  | $\times$ | $\times$ |  |  |  |  |
2018 | Zhou et al. (2018) |  | $\times$ |  |  | $\times$ |  |  |  | $\times$ |  |  |  |  |  |  | $\times$ |  |  |  |  |  |  |  |  |
2019 | Camacho Barranco et al. (2019) |  | $\times$ | $\times$ | $\times$ | $\times$ |  |  | $\times$ |  |  |  |  |  |  |  |  |  |  |  |  | $\times$ |  |  | $\times$ |
2019 | Cai et al. (2019) |  | $\times$ |  |  |  |  |  |  |  |  | $\times$ |  |  |  | $\times$ |  | $\times$ |  |  |  |  |  |  |  |
2019 | Yuan et al. (2019) |  |  |  |  |  | $\times$ |  |  | $\times$ |  |  |  |  |  |  | $\times$ |  |  |  |  |  |  |  |  |
2020 | Duan et al. (2020) |  |  |  |  |  | $\times$ |  | $\times$ |  |  |  |  |  |  | $\times$ | $\times$ |  |  |  |  |  | $\times$ |  |  |
2020 | Liu et al. (2020) |  | $\times$ |  |  | $\times$ |  |  |  |  |  |  |  |  | $\times$ |  |  |  | $\times$ |  |  |  |  |  | $\times$ |
2021 | La Quatra et al. (2021) |  | $\times$ |  |  |  |  |  |  |  |  |  | $\times$ |  |  |  | $\times$ |  |  |  |  |  |  |  |  |
2021 | Yu et al. (2021) |  | $\times$ |  |  | $\times$ |  |  |  |  |  | $\times$ |  | $\times$ | $\times$ |  | $\times$ |  |  |  |  |  |  |  |  |
2021 | Liao et al. (2021) |  |  |  |  |  |  |  |  |  |  |  | $\times$ |  |  |  | $\times$ | $\times$ |  |  |  |  |  |  | $\times$ |
2021 | Keith Norambuena and Mitra (2021) |  | $\times$ | $\times$ |  | $\times$ | $\times$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | $\times$ |

Table 2. Summary of the extraction criteria and evaluation metrics used in the
reviewed articles.

Relevance Relevance metrics evaluate whether the events in the narrative are
relevant or significant to a given query or topic (Yan et al., 2011b; Yan et
al., 2011a; Li and Li, 2013a; Nguyen et al., 2014; Li et al., 2015; Tikhomirov
and Dobrov, 2018). In general, relevance is measured by borrowing techniques
from traditional search methods in Information Retrieval, such as PageRank and
its variations (Zhu and Oates, 2012, 2014; Tran et al., 2015a; Wang et al.,
2018). However, some approaches use supervised methods to learn a ranking
function (Binh Tran et al., 2013; Tran et al., 2013). The results from such
techniques are used to feed other parts of the algorithm or could be directly
used to select relevant events, turning this issue into more of a traditional
information retrieval problem rather than a narratological one.

Content Similarity Another approach to extracting narratives is based on
modeling content similarity between events. Over two-thirds of the methods use
some sort of content similarity measure. There are many ways to do this, in
particular, we found the following approaches: surface-level similarity
comparisons (e.g., Jaccard similarity or cosine similarity) (Hu et al., 2011;
Nguyen et al., 2014; Uramoto and Takeda, 1998), topic similarity based on
topic distribution information (e.g., comparing topic vectors extracted from
LDA models) (Li et al., 2015; Chen et al., 2015), and entity-based comparisons
(e.g., entity co-occurrence in events) (Nallapati et al., 2004; Zhu and Oates,
2014).

The exact choice of approach is highly dependent on the event representation.
In recent years, researchers have started leveraging advances in text
representation with neural embeddings (e.g., BERT) (Yu et al., 2021; Keith
Norambuena and Mitra, 2021; Liao et al., 2021; Duan et al., 2020; Tikhomirov
and Dobrov, 2018), which have several advantages over traditional frequency-
based models and are better able to capture semantic similarities.

The use of entity-based information in event-based narrative extraction
methods to measure event content similarity remains limited in scope, with
sparse usage over the years compared to other content similarity measures
(Camacho Barranco et al., 2019; Wang et al., 2018; Bögel and Gertz, 2015; Zhu
and Oates, 2014; Hu et al., 2014; Hu et al., 2011; Nallapati et al., 2004).
Combining entity information with other types of similarities would provide a
much more holistic view of content similarity. Furthermore, expanding upon
this approach, content similarity metrics could exploit the main event
descriptors (Keith Norambuena et al., 2020) to compute a more precise
similarity measure.

Coherence Coherence metrics evaluate whether the narrative makes sense. Due to
their importance as an extraction metric, we show some mathematical
formulations of coherence and coherence-like metrics in Table 3.

While coherence has a formal definition in narratological terms (Abbott,
2008), it is just as complex and ill-defined as relevance in computational
terms. One particular motivation for the definition of coherence that stands
out is the idea of smoothness from the Connect the Dots (Shahaf and Guestrin,
2010, 2012; Shahaf et al., 2013b, 2015) series of works. In particular, they
use the concept of word influence and word activations (i.e., the sustained
importance of the word in a storyline) to construct stories that have smooth
transitions.

Other approaches compute coherence based on content similarity. These works
also seek to generate smooth stories by avoiding drastic local changes based
on content similarity (Yan et al., 2011b; Zhu and Oates, 2012; Tran et al.,
2013; Zhou et al., 2014; Zhu and Oates, 2014; Li et al., 2015; Zhou et al.,
2018; Liu et al., 2017; Xu and Tang, 2018; Camacho Barranco et al., 2019; Liu
et al., 2020; Keith Norambuena and Mitra, 2021), without explicitly defining
active words or topics like the original Connect the Dots approach. Finally,
one approach also considers coherence around the idea of causality (Binh Tran
et al., 2013; Tran et al., 2013) in a supervised setting (e.g., causal signals
in text).

Formula | Resolution Level |  Description | Source
---|---|---|---
$\displaystyle\frac{1}{|S|-1}\sum_{(c_{i},c_{j})\in S}{\mathsf{JaccardSim}(c_{i},c_{j})}$ | Events as Clusters |  This is a measure of coherence based on average Jaccard Similarity along a story $S$ based on cluster words. | (Xu and Tang, 2018)
$\displaystyle\frac{1}{|S|-1}{\mathsf{CosineSim}(c_{i},c_{j})}$ | Events as Clusters |  This is a measure of coherence based on average Cosine Similarity along a story $S$ based on cluster centroids. | (Liu et al., 2017)
$\displaystyle\max_{\mathsf{activations}}\left\\{\min_{(d_{i},d_{j})\in S}{\sum_{w\in\mathsf{Words}}{\mathsf{Influence}(d_{i},d_{j}|w)\cdot\mathbbm{1}(w\text{ active in }d_{i},d_{j})}}\right\\}$ | Events as Documents |  This is the full form of the coherence for a storyline $S$ from the original Connect the Dots algorithm. It is based on maximizing the sum of word influences over active words in the storyline. Influence can be changed for any other type of scoring mechanism. | (Shahaf and Guestrin, 2010)
$\displaystyle\min_{(d_{i},d_{j})\in S}{\mathsf{CosineSim}(d_{i},d_{j})}$ | Events as Documents |  This is a measure of coherence based on the minimum Cosine Similarity along a story $S$ based on document vectors. | (Zhou et al., 2014)
$\displaystyle\min_{(d_{i},d_{j})\in N}{\sqrt{\mathsf{SurfaceSim}(d_{i},d_{j})\cdot\mathsf{TopicSim}(d_{i},d_{j})}}$ | Events as Documents |  This is a measure of coherence for a narrative $N$ based on the minimum geometric mean of Surface-level similarity (e.g., cosine similarity) and Topic-level similarity (e.g., Jensen-Shannon divergence). It is based on document vectors and topic distribution vectors.. | (Keith Norambuena and Mitra, 2021)
$\displaystyle\frac{\sum\limits_{i,j\in|D|\times|D|}{w_{i}\cdot w_{j}\cdot\Phi\cdot\mathsf{Soergel}(d_{i},d_{j})\cdot|t_{i}-t_{j}|}}{\sum\limits_{i,j\in|D|\times|D|}{w_{i}\cdot w_{j}\cdot\Phi}}$ | Events as Documents |  This is a measure of incoherence rather than coherence. It is based on the average Soergel distance and includes a temporal distance term as well. The events are weighted by their relevance ($w_{i}$ and $w_{j}$) and their temporal distance using a custom kernel $\Phi$. |
$\displaystyle\sum_{s\in E}{\frac{\mathsf{Count}_{\mathsf{match}(s,E)}(\mathsf{gram}_{n})}{\mathsf{Count}_{\mathsf{Previous}(E)}(\mathsf{gram}_{n})}}$ | Events as Sentences |  This is a measure of coherence based on the n-gram overlap between the current event sentences and the sentences of the previous summary of the timeline. | (Tran et al., 2013)
$\displaystyle\frac{1}{1+\exp{(JS(E,\mathsf{Previous}(E))))}}$ | Events as Sentences |  This is a measure of coherence based on the Jensen-Shannon divergence between the current event sentence and the previous event sentence of the timeline. | (Li et al., 2015)
$\displaystyle\frac{\sum\limits_{\delta=-\Delta/2}^{\delta=\Delta/2}{\exp{(-\delta/v)}\cdot KLD(E_{t},E_{t-\delta}})}{\sum\limits_{\delta=-\Delta/2}^{\delta=\Delta/2}{\exp{(-\delta/v)}}}$ | Events as Sentences |  This is a measure of coherence based on Kullback-Leibler divergence between the current event at time $t$ and all the other local events in a $\Delta$ time window surrounding the event. The events are weighted by their temporal distance based on parameter $v$. | (Li and Li, 2013a)

Table 3. A sample of different formulations of coherence from the reviewed
articles.

Coverage-like Metrics Coverage-like metrics evaluate whether the extracted
narrative properly covers the relevant events, stories, or topics. These
metrics include coverage itself and related metrics, such as redundancy and
diversity. The most basic form of coverage is simply the percentage of topics
or relevant events covered by the extracted representation (or some variation
of this metric) (Guha et al., 2005; Yuan et al., 2019; Duan et al., 2020;
Keith Norambuena and Mitra, 2021), or a probability estimation (Shahaf et al.,
2012, 2013a; Shahaf et al., 2013b, 2015; Xu and Tang, 2018). Equation 1 shows
an example formulation of coverage for a cluster $c$, where $\Pi$ represents
an extracted narrative with storylines $l$.

(1)
$\mathsf{Cover}_{\Pi}(c)=1-\prod_{l\in\Pi}{\left(1-\mathsf{Cover}_{l}(c)\right)}$

Another approach to compute coverage is to do a content similarity comparison
between the output and the full data set (or a relevant subset) (Yan et al.,
2011b; Li and Li, 2013a; Li et al., 2015). In contrast, redundancy and
diversity (Zhu and Oates, 2014, 2012; Yan et al., 2011b; Duan et al., 2020;
Wang et al., 2018) metrics are based on the idea that events should not be
covered more than necessary, thus high redundancy can lead to coverage
problems.

Structural Information Some works evaluate the structure of the output
narrative representation. In particular, these metrics consider aspects such
as size (in general) or connectivity (in graph-based narratives).

Size can be used as a proxy for complexity (e.g., length of the timeline) (Xu
and Tang, 2018). In most cases, rather than as an evaluation metric, size is
used as a constraint (e.g., setting a maximum story length) (Yuan et al.,
2019; Zhou et al., 2018, 2014; Shahaf et al., 2015, 2013b; Shahaf et al.,
2013a, 2012).

Connectivity metrics (Shahaf et al., 2015, 2013b; Shahaf et al., 2013a, 2012)
are used to ensure that narrative graphs avoid isolated stories, as they
should be interwoven throughout the narrative. Structure metrics are mostly
analyzed at a global level (e.g., the total number of connected stories).
However, it is possible to consider local structural features, such as node
degrees (Tannier and Moriceau, 2013).

Exploiting the internal article structure (Tran et al., 2013; Bögel and Gertz,
2015; Tikhomirov and Dobrov, 2018) is another piece of structural information
used by some methods. Most breaking news articles are written following the
inverted pyramid structure (Keith Norambuena et al., 2020), where the most
important information—the main event descriptors—is shown first in the lead.
Thus, the first few lines of an article describe its main event (Tran et al.,
2013) and subsequent paragraphs may contain more details and reference
previous events.

Content References Another criterion to consider in news narrative extraction
is the use of content references. As mentioned before, some news articles make
explicit references to previous works in their body. Note that this differs
from explicit date-based references discussed before, which rely on explicit
temporal information. This approach also differs from general content
similarity because of its goal of identifying specific references rather than
global similarity.

One way to identify these references is to compare the lead of a news article
with the additional information paragraphs of another article (Tikhomirov and
Dobrov, 2018). Other approaches identify references based on sentence co-
occurrence without considering article structure (Yu et al., 2021).
Alternatively, a set of core features (Huang et al., 2014; Cai et al., 2019)
(e.g., relevant keywords or main event descriptors) could be identified and
used to detect references in other articles. Once identified, these references
can be used to identify relevant events based on reference-based metrics
(e.g., bibliographic coupling).

Temporal Features Temporal information, such as the temporal distance between
events or specific date references, has been used. In particular, temporal
distance is commonly used to penalize events that would otherwise be similar
in content. For example, consider two articles describing separate protests in
a city, one during the year 2000 and another in the year 2010. These two
articles would likely be very similar in terms of content, including both
surface-level features and topic distributions. However, given the temporal
separation between them, they would likely refer to different events. Thus, a
common strategy is to define an exponentially decreasing term of the form
$C_{0}\exp{\left(\frac{-\Delta t}{\sigma}\right)}$ (or similar), where $C_{0}$
and $\sigma$ are pre-defined constants (Yang et al., 2006, 2009; Yu et al.,
2021; Wei et al., 2014; Yan et al., 2011a; Liu et al., 2020, 2017; Hu et al.,
2014; Nallapati et al., 2004; Huang et al., 2014), although there are other
approaches, such as kernels to perform temporal proximity projections (Yan et
al., 2011a; Wang et al., 2018) or overlap-based measures (Chen and Chen, 2012,
2008). However, we note that the use of a temporal penalty is not always
desired. Some events are continuations of stories that did not have anything
new to report for a long time. For example, the investigation results of a
flight accident might come much after the accident itself has been covered,
leading to temporal gaps in story coverage (Laban and Hearst, 2017; Wei et
al., 2014). Thus, it is necessary to distinguish between continuations and
completely new storylines when the time gap is high enough.

Burstiness and frequency measures and metrics based on these (e.g., energy
values) are other time-based criteria used to identify relevant events and
dates (Chen and Chen, 2008; Yang et al., 2009; Chen and Chen, 2012; Yan et
al., 2011a; Binh Tran et al., 2013; Huang et al., 2013; Wei et al., 2014;
Nguyen et al., 2014; Tran et al., 2015a; Tikhomirov and Dobrov, 2018; Laban
and Hearst, 2017; Yu et al., 2021; Chen et al., 2015). For example, periods
with many publications are likely to contain important events. Alternatively,
a specific event might be reported several times by different outlets.
Finally, other temporal features include the use of specific temporal
expressions or date references in the text (Binh Tran et al., 2013; Tran et
al., 2013, 2015a; Bögel and Gertz, 2015; La Quatra et al., 2021; Liao et al.,
2021; Tannier and Moriceau, 2013) to identify temporal cross-references
between documents.

##  4\. Evaluation Metrics

In this section, we discuss the evaluation approaches for the narrative output
of the extraction methods. In particular, we show the evaluation metrics used
to assess the quality of the extracted narratives. These output metrics are
generally intended to be interpreted by humans, unlike the extraction criteria
which may or may not be easy to interpret. In particular, user-based
evaluation metrics (e.g., task performance or user perception) are an
important subset of output evaluation criteria. The second part of Table 2
provides an overview of the different output evaluation criteria.

###  4.1. Computational Metrics

These metrics seek to evaluate the extracted narrative based on computational
measures of narrative quality. These metrics are usually supervised, requiring
a gold standard data set to be computed.

####  4.1.1. Supervised

We first discuss supervised approaches. In particular, we identified three
broad types of metrics here: traditional information retrieval metrics,
summarization metrics, and ranking metrics.

Traditional IR Metrics Several works—about a third of the reviewed
articles—rely on classical evaluation metrics such as accuracy, precision,
recall, and the $F_{1}$ score (Nallapati et al., 2004; Yang et al., 2006; Lin
et al., 2007; Yang et al., 2009; Khurdiya et al., 2011; Hu et al., 2011;
Tannier and Moriceau, 2013; Huang et al., 2014; Wei et al., 2014; Hu et al.,
2014; Tran et al., 2015a; Bögel and Gertz, 2015; Chen et al., 2015; Wang et
al., 2018; Cai et al., 2019; Duan et al., 2020) taken from traditional
information retrieval and machine learning literature. In particular, these
approaches evaluate the quality of the output by measuring whether events or
their connections were identified correctly. Some methods also use variations
of these basic metrics, such as the mean average precision (Binh Tran et al.,
2013; Nguyen et al., 2014) over multiple dates.

Summarization Metrics Specialized metrics from the summarization domain have
also been used to evaluate narratives in several works—about a third of the
reviewed works use them.

In particular, ROUGE (Recall-Oriented Understudy for Gisting Evaluation)
metrics (Ogawa et al., 2012) have been used to evaluate the output of
narrative extraction methods, mostly in timeline summarization works with a
sentence-level event resolution (Binh Tran et al., 2013; Tran et al., 2013;
Nguyen et al., 2014; Chen et al., 2015; Liao et al., 2021; Yan et al., 2011b;
Li and Li, 2013a; Li et al., 2015; Yu et al., 2021; Huang et al., 2013;
Tikhomirov and Dobrov, 2018; La Quatra et al., 2021), but also in works with a
document-level resolution (Hu et al., 2014; Zhou et al., 2014, 2018; Yuan et
al., 2019). ROUGE metrics include variations such as ROUGE-N (which measures
the overlap of N-grams), ROUGE-L (which measures the longest common
subsequence), ROUGE-W (a weighted version of ROUGE-L that favors consecutive
subsequences), ROUGE-SU (skip-bigram and unigram-based co-occurrence
statistics) and their precision, recall, and $F_{1}$ score variants. The most
common variant is ROUGE-N, which we show in Equation 2.

(2) $\mathsf{ROUGE\text{-}N}=\frac{{\sum}_{s\in R}{\sum}_{\mathsf{gram}_{n}\in
s}\mathsf{Count}_{\mathsf{match}}(gram_{n})}{{\sum}_{s\in
R}{\sum}_{\mathsf{gram}_{n}\in s}\mathsf{Count}(\mathsf{gram}_{n})}$

In Equation 2, $n$ represents the length of the $n$-gram, and $R$ represents
the reference summaries (i.e., the ground truth).
$\mathsf{Count}_{\mathsf{match}}(\mathsf{gram}_{n})$ represents the maximum
number of $n$-grams that co-occur in a candidate summary and the reference
summaries. $\mathsf{Count}_{R}(\mathsf{gram}_{n})$ represents the number of
$n$-grams in the reference summaries.

An alternative is to measure the average summary-to-document content
similarity where the summary is compared against the documents in the data set
using a text similarity measure (e.g., cosine similarity) (Chen and Chen,
2008, 2012).

We note that these metrics are mostly used with linear representations rather
than graph-based models—only three of the reviewed works that extract graphs
use summarization metrics (Chen and Chen, 2008, 2012; Hu et al., 2014). This
contrasts heavily with the case of traditional information retrieval metrics,
where the split was much more balanced between linear (~40%) and graph
representations (~60%). This might be due to the inability of these metrics to
handle complex structures.

Ranking Metrics Other works rely on ranking-based metrics, like those used in
traditional search tasks from information retrieval. For example, Wang et al.
(Wang et al., 2018) use a relevance-based approach to evaluate their event
phase summaries. Liao et al. (Liao et al., 2021) evaluate the ranking
performance of WILSON with the mean reciprocal rank and discounted cumulative
gain (Avramidis, 2013). Cai et al. (Cai et al., 2019) use the normalized
discounted cumulative gain (Yilmaz et al., 2008) to evaluate all their events.

Clustering Metrics Liu et al. (Liu et al., 2017, 2020) used clustering metrics
to evaluate the event nodes—which are represented as clusters of articles—in
their Story Forest method. In particular, they use the homogeneity,
completeness, and V-measure scores (Rosenberg and Hirschberg, 2007). These
metrics require labeled data sets to be computed, thus they are supervised
despite being designed to evaluate unsupervised clustering methods. In
particular, homogeneity is larger when each extracted cluster only contains
members of a single class. In contrast, completeness is maximized when all
members of a true class are in the same cluster. Finally, the V-measure takes
both of these metrics and computes the harmonic mean between them, similar to
how the $F_{1}$ score treats precision and recall in traditional
classification metrics. We note that none of the other events as clusters
methods used these metrics or other similar clustering metrics to evaluate
their models. Instead, they relied on traditional information retrieval
metrics like accuracy, precision, recall, and the $F_{1}$ score.

####  4.1.2. Unsupervised Metrics

We now discuss unsupervised approaches. In general, there are far fewer works
relying on unsupervised metrics to evaluate the final narrative output.

Coherence In general, coherence is not used to evaluate the output narrative
despite being a useful metric during the extraction process. One exception is
Xu et al. (Xu and Tang, 2018), who evaluate their output using a weighted
average of story coherence (based on Jaccard similarity) and story size.

Coverage Xu et al. (Xu and Tang, 2018) evaluate their output by treating
coverage as a structural measure, making the assumption that good coverage of
topics means that the structure of their metro map representation is good.
However, due to the formulation of coverage based on whether the topical
clusters of the data set are covered, it does not explicitly consider the
structure of the output, which makes it inappropriate to evaluate the
structure. In contrast, Bögel et al. (Bögel and Gertz, 2015) use a notion of
coverage based on event connections in a graph (i.e., an article is covered if
there is at least one edge connecting it) that could be treated more as a
structural measure than the topical concept of coverage.

Dispersion Camacho et al. (Camacho Barranco et al., 2019) use the dispersion
coefficient—originally proposed as an evaluation metric for storytelling in
the intelligence analysis domain (Hossain et al., 2011)—to evaluate their
storyline. In particular, the dispersion coefficient is based on the Soergel
distance, although other distance metrics could be used (Rigsby and Barbará,
2018). In particular, dispersion is based on Swanson’s complementary but
disjoint hypothesis (Swanson, 1991)—where articles that have no explicit
common elements yield important inferences or insights when combined. These
insights are not apparent from the separate documents. Furthermore, the
authors propose a new evaluation metric to measure story flow based on
Swanson’s hypothesis called the dispersion coefficient, shown in Equation 3.
We note that this particular version is based on the Soergel distance ($S$),
but any other distance metric between documents could be used in practice.

(3)
$\mathsf{Dispersion}(d_{1},\ldots,d_{n})=1-\frac{1}{n-2}\sum_{i=1}^{n-2}{\sum_{j=i+2}^{n}\mathsf{D}(d_{i},d_{j})},\quad\text{
with }\quad\mathsf{D}(d_{i},d_{j})=\begin{cases}\frac{1}{n+i-j},&\text{if
}\mathsf{S}(d_{i},d_{j})<\theta\\\ 0,&\text{otherwise.}\end{cases}$

Diversity and Redundancy Finally, another alternative is a diversity metric to
ensure proper coverage or low redundancy. In particular, Duan et al. (Duan et
al., 2020) used diversity—based on the average pairwise similarity of
sentences (see Equation 4—to evaluate the performance of their comparative
timeline extraction method.

(4) $\mathsf{Diversity}=1-\frac{1}{|S|^{2}}\sum{s_{i}\in S}{\sum{s_{j}\in
S}{1-\mathsf{CosineSim}(s_{i},s_{j})}}$

###  4.2. User Evaluation Metrics

These metrics seek to evaluate the extracted narrative based on subjective
user measures or task performance measures.

Task-oriented Evaluation Task-oriented metrics require designing a series of
benchmark tasks to measure the number of correct answers, accuracy, how much
time the users take to complete the task or some other measure of correctness
or quality. Few works use task-oriented evaluation metrics: Metro Maps (Shahaf
et al., 2012, 2013a), Information Cartography (Shahaf et al., 2013b, 2015),
and the SToRe system (Lin and Liang, 2006, 2008). These works rely on event-
based representations and all of them evaluate extraction methods as retrieval
tools following a similar approach. In particular, there are micro-knowledge
tasks that measure how the extracted narratives help users retrieve
information faster and macro-knowledge tasks that measure how the extracted
narratives help users understand the big picture.

For micro-knowledge tasks, all works create a series of simple retrieval
questions such that the answers can be easily classified as right or wrong.
For example, retrieving dates, facts, relevant entities or the main event
descriptors. Users are evaluated by measuring how many correct answers (i.e.,
accuracy) they can get in a fixed amount of time and the rate at which they
answer these questions (Shahaf et al., 2012; Lin and Liang, 2006, 2008).
Another metric used at the micro-knowledge level is the ease of navigation,
estimated by the number of documents that users clicked per correct answer