# Movie Summarization via Sparse Graph Construction

Pinelopi Papalampidi Frank Keller Mirella Lapata

###### Abstract

We summarize full-length movies by creating shorter videos containing their
most informative scenes. We explore the hypothesis that a summary can be
created by assembling scenes which are _turning points_ (TPs), i.e., key
events in a movie that describe its storyline. We propose a model that
identifies TP scenes by building a sparse movie graph that represents
relations between scenes and is constructed using multimodal information111We
make our data and code publicly available at
https://github.com/ppapalampidi/GraphTP.. According to human judges, the
summaries created by our approach are more informative and complete, and
receive higher ratings, than the outputs of sequence-based models and general-
purpose summarization algorithms. The induced graphs are interpretable,
displaying different topology for different movie genres.

## Introduction

Automatic summarization has received considerable attention due to its
importance for downstream applications. Although current research has
primarily focused on news articles (Grusky, Naaman, and Artzi 2018; Narayan,
Cohen, and Lapata 2018; Liu and Lapata 2019), other application domains
include meetings (Murray et al. 2007), lectures (Fujii, Kitaoka, and Nakagawa
2007), social media (Syed et al. 2018), scientific articles (Teufel and Moens
2002), and narratives ranging from short stories (Goyal, Riloff, and Daumé III
2010; Finlayson 2012) to books (Mihalcea and Ceylan 2007), and movies
(Gorinski and Lapata 2015).

1\. Opportunity
---
Introductory event that occurs after presentation of setting and background of
main characters. (Juno discovers she is pregnant with a child fathered by her
friend and longtime admirer.)
2\. Change of Plans
Main goal of story is defined; action begins to increase. (Juno decides to
give the baby up for adoption.)
3\. Point of No Return
Event that pushes the main characters to fully commit to their goal. (Juno
meets a couple, and agrees to a closed adoption.)
4\. Major Setback
Event where everything falls apart, temporarily or permanently. (Juno watches
the couple’s marriage fall apart.)
5\. Climax
Final event of the main story, moment of resolution and “biggest spoiler”.
(Juno gives birth and spouse from ex-couple claims newborn as single adoptive
mother.)
Figure 1:  Turning points (from the movie “Juno”) and their definitions.

In this work, we aim at summarizing full-length movies by creating shorter
video summaries encapsulating their most informative parts. Aside from
enabling users to skim through movies quickly — Netflix alone has over 148
million subscribers worldwide, with more than 6000–7000 movies, series, and
shows available — movie summarization is an ideal platform for real-world
natural language understanding and the complex inferences associated with it.
Movies are often based on elaborate stories, with non-linear structure and
multiple characters, rendering the application of popular summarization
approaches based on position biases, importance, and diversity problematic
(Jung et al. 2019). Another key challenge in movie summarization lies in the
scarcity of labeled data. For most movies there are no naturally occurring
summaries (trailers aim to attract an audience to a film without revealing
spoilers which a summary will contain), and manually creating these would be a
major undertaking requiring substantial effort to collect, watch, preprocess,
and annotate videos. As a result, the majority of available movie datasets
contain at most a few hundred movies focusing on tasks like Question-Answering
(QA) or the alignment between video clips and captions (Tapaswi et al. 2016;
Xiong et al. 2019; Rohrbach et al. 2015) which are limited to video snippets
rather than entire movies, or restricted to screenplays disregarding the video
(Gorinski and Lapata 2015; Papalampidi et al. 2020).

Following previous work (Gorinski and Lapata 2015), we formalize movie
summarization as the selection of a few important scenes from a movie. We
further assume that important scenes display events which determine the
progression of the movie’s narrative and segment it into thematic sections.
Screenwriting theory (Thompson 1999; Cutting 2016; Hauge 2017) reserves the
term _turning points_ (TPs) for events which have specific functionality
inside a narrative and reveal its storyline. TPs are considered key for making
successful movies whose stories are expected to consist of six basic stages,
defined by five key turning points in the plot. An example of TPs and their
definitions is given in Figure 1. Interestingly, TPs are assumed to be the
same, no matter the movie genre, and occupy the same positions in the story
(e.g., the Opportunity occurs after the first 10% of a 90-minute comedy or a
three-hour epic).

We propose that automatic movie summarization can be reduced to turning point
identification building on earlier work (Lehnert 1981; Lohnert, Black, and
Reiser 1981; Mihalcea and Ceylan 2007) which claims that high level analysis
is necessary for revealing concepts central to a story. Although there exist
several theories of narrative structure (Cutting 2016), we argue that turning
points are ideally suited to summarizing movies for at least three reasons.
Firstly, they are intuitive, and can be identified by naive viewers
(Papalampidi, Keller, and Lapata 2019), so there is hope the process can be
automated. Secondly, TPs have specific definitions and expected positions
which facilitate automatic identification especially in low resource settings
by providing prior knowledge (semantic and positional). Thirdly, they provide
data efficiency, since the summarization problem is re-formulated as a scene-
level classification task and no additional resources are required for
creating the movie summaries over and above those developed for identifying
turning points.

We model TP identification (and by extension summarization) as a supervised
classification task. However, we depart from previous approaches to movie
analysis which mostly focus on interactions between _characters_ (Do, Tran,
and Tran 2018; Tran et al. 2017; Gorinski and Lapata 2015) and model
connections between _events_. Moreover, we discard the simplifying assumption
that a screenplay consists of a _sequence of scenes_ (Gorinski and Lapata
2015; Papalampidi, Keller, and Lapata 2019; Papalampidi et al. 2020) and
instead represent interactions between scenes as a _sparse graph_.
Specifically, we view the screenplay of a movie as a graph whose nodes
correspond to scenes (self-contained events) and edges denote relations
between them which we compute based on their linguistic and audiovisual
similarity. In contrast to previous work on general-purpose summarization that
relies on fully connected graphs (Mihalcea and Tarau 2004; Zheng and Lapata
2019; Wang et al. 2020), we induce sparse graphs by selecting a subset of
nodes as neighbors for a scene; the size of this subset is not set in advance
but learnt as part of the network. Sparse graphs provide better
contextualization for scenes and tend to be more informative, as different
genres present different degrees of connectivity between important events. We
rely on Graph Convolutional Networks (GCNs; Duvenaud et al. 2015; Kearnes et
al. 2016; Kipf and Welling 2017) to encode relevant neighborhood information
in the sparsified graph for every scene which in turn contributes to deciding
whether it acts as a TP and should be included in the summary.

Our contributions can be summarized as follows: (a) we approach movie
summarization directly via TP identification which we argue is a well-defined
and possibly less subjective task; (b) we propose a TP identification model
which relies on sparse graphs and is constructed based on multimodal
information; (c) we find that the induced graphs are meaningful with differing
graph topologies corresponding to different movie genres.

## Related Work

The computational treatment of narratives has assumed various guises in the
literature (Mani 2012; Richards, Finlayson, and Winston 2009). Previous work
has attempted to analyze stories by examining the sequence of events in them
(Schank and Abelson 1975; Chambers and Jurafsky 2009), plot units (McIntyre
and Lapata 2010; Goyal, Riloff, and Daumé III 2010) and their structure
(Lehnert 1981; Rumelhart 1980), or the interactions of characters in the
narrative (Black and Wilensky 1979; Propp 1968; Valls-Vargas, Zhu, and Ontanon
2014; Srivastava, Chaturvedi, and Mitchell 2016).

The summarization of narratives has received less attention, possibly due to
the lack of annotated data for modeling and evaluation. Nevertheless,
Kazantseva and Szpakowicz (2010) summarize short stories as a browsing aids to
help users decide whether a story is interesting to read. Other work (Mihalcea
and Ceylan 2007; Gorinski and Lapata 2015; Tsoneva, Barbieri, and Weda 2007)
focuses on long-form narratives such as books or movies and adopts primarily
unsupervised, graph-based methods. More recently, Papalampidi, Keller, and
Lapata (2019) released TRIPOD, a dataset containing screenplays and TP
annotations and showed that TPs can be automatically identified in movie
narratives. In follow-on work, Papalampidi et al. (2020) further demonstrate
that TPs provide useful information when summarizing episodes from the TV
series CSI. In this work, we consider scenes as the basic summarization units,
and reduce the scene selection task to a TP identification problem.

Work on video understanding has also looked at movies. Existing datasets
(Tapaswi et al. 2016; Rohrbach et al. 2015) do not contain more than a few
hundred movies and focus mostly on _isolated_ video clips rather than _entire_
narratives. For example, Tapaswi, Bauml, and Stiefelhagen (2015) align movie
scenes to book chapters, while Xiong et al. (2019) align movie segments to
descriptions using a graph-based approach. Rohrbach et al. (2015) introduce a
dataset where video clips from movies are aligned to text descriptions in
order to address video captioning. Tapaswi, Bäuml, and Stiefelhagen (2015)
introduce a Question-Answering (QA) dataset based on movies, although the
questions are again restricted to isolated video clips. Frermann, Cohen, and
Lapata (2018) analyze CSI episodes with the aim of modeling how viewers
identify the perpetrator.

Our work is closest to Papalampidi, Keller, and Lapata (2019) in that we also
develop a model for identifying turning points in movies. While they focus
solely on textual analysis, we consider additional modalities such as audio
and video. Moreover, we model screenplays more globally by representing them
as graphs and inferring relationships between scenes. Our graphs are
interpretable and differentially represent the morphology of different genres.
Beyond improving TP prediction, we further argue that narrative structure can
be _directly_ used to create video summaries for movies of any genre. Previous
work (Papalampidi et al. 2020) treats TPs as latent representations with the
aim of enhancing a supervised summarization task. We do not assume
goldstandard video summaries are available, we claim that scenes which contain
TPs can yield good enough proxy summaries.

Figure 2: We construct a fully-connected graph based on pairwise textual and
audiovisual similarity between scenes. The graph is sparsified (by
automatically selecting the $k$ nearest neighbors per scene) and together with
contextualized scene representations is fed to a one-layer GCN.

## Problem Formulation

Let $\mathcal{D}$ denote a screenplay consisting of a sequence of scenes
$\mathcal{D}=\\{s_{1},s_{2},\dots,s_{n}\\}$. We aim at selecting a smaller
subset $\mathcal{D}^{\prime}=\\{s_{i},\dots,s_{k}\\}$ consisting of the most
_informative_ scenes describing the movie’s storyline. Hence, our objective is
to assign a binary label $y_{i}$ to each scene $s_{i}$ denoting whether it is
part of the summary.

Furthermore, we hypothesize that we can construct an informative summary by
identifying TPs directly. As we explained earlier, screenwriting theory (Hauge
2017) postulates that most movie narratives are delineated by five key events
called turning points (see Figure 1). Hence, we re-formulate the summarization
problem as follows: for each scene $s_{i}\in\mathcal{D}$ we assign a binary
label $y_{it}$ denoting whether it represents turning point $t$. Specifically,
we calculate probabilities $p(y_{it}|s_{i},\mathcal{D},\theta)$ quantifying
the extent to which $s_{i}$ acts as the $t^{th}$ TP, where $t\in[1,5]$ (and
$\theta$ are model parameters). During inference, we compose a summary by
selecting $l$ consecutive scenes that lie on the peak of the posterior
distribution
$\operatorname{argmax}\limits_{i=1}^{N}p(y_{it}|s_{i},\mathcal{D},\theta)$ for
each TP.

## A Turning Point Graph Model

### Graph Construction

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ denote a directed screenplay graph
with nodes $\mathcal{V}$ and edges $\mathcal{E}$. $\mathcal{G}$ consists of
$N$ nodes, each corresponding to a scene ($N$ varies with screenplay size;
some screenplays have many short scenes, while others only a few long ones).
We further represent $\mathcal{G}$ by an adjacency matrix
$\mathcal{A}\in\mathcal{R}^{N\times N}$ where entry $a_{ij}$ denotes the
weight of the edge from node $i$ to node $j$. We initially construct a dense
complete graph $\mathcal{G}$ with edge weights representing the probability
$p_{ij}$ of scene $i$ being a neighbor of scene $j$ (see Figure 2(b)). We
estimate $p_{ij}$ as:

$p_{ij}=\dfrac{\exp(e_{ij}/\tau)}{\sum_{t=1}^{T}\exp(e_{tj}/\tau)}$ (1)

where $e_{ij}$ denotes the similarity between scenes $s_{i}$ and $s_{j}$
(explained in the next section), $T$ are TPs (see Figure 1), and $\tau$ is a
temperature parameter.

#### Similarity Computation

There are various ways to compute the similarity $e_{ij}$ between two scenes.
In addition to linguistic information based on the text of the screenplay, we
wish to take advantage of other modalities, such as audio and video.
Audiovisual cues might be relatively superficial; simply on account of two
scenes sounding or seeming alike, it might not be possible to induce which
events are being described and their relations. Nevertheless, we expect
audiovisual information to contribute to the similarity computation by helping
distinguish scenes which refer to the same sub-story or event, e.g., because
they have the same background, the same characters, or similar noises. We thus
express $e_{ij}$ as a composite term based mostly on textual information but
also modulated by audiovisual cues:

$\displaystyle
e_{ij}=u_{ij}\bigg{(}\tanh(W_{i}v_{i}+b_{i})^{\intercal}\tanh(W_{j}v_{j}+b_{j})\bigg{)}+b_{ij}$
(2)

where $W_{i}$ and $W_{j}$ are weight matrices, $v_{i}$ and $v_{j}$ are
_textual_ vectors representing the content of scenes $s_{i}$ and $s_{j}$, and
$u_{ij}$ expresses the _audiovisual_ similarity between $s_{i}$ and $s_{j}$.
If $u_{ij}$ is high, the similarity between two scenes will be accentuated,
but if it is low when textual similarity is high, its influence will be modest
(see Figure 2(a)).

It is relatively straightforward to obtain textual representations for scenes.
The latter contain mostly dialogue (lines the actors speak) as well as
descriptions explaining what the camera sees. We first calculate
representations for the sentences included in a scene via a pre-trained
transformer-based sentence encoder (Cer et al. 2018b). We then obtain
contextualized sentence representations using a BiLSTM equipped with an
attention mechanism. A scene is represented as the weighted sum of the
representations of its sentences.

We also assume that a scene corresponds to a sequence of audio segments
extracted from the movie and a sequence of frames sampled (with a fixed
sampling frequency) from the video. We first non-linearly project the features
of each modality to a lower dimension and obtain scene-level representations
(as the attention-weighted average of the segments/frames in each scene). The
two modalities are combined into a joint representation using late fusion
(Frermann, Cohen, and Lapata 2018; Papasarantopoulos et al. 2019). The
audiovisual similarity $u_{ij}$ (applied in Eq. (2)) between scenes $s_{i}$
and $s_{j}$ is the dot product of their fused representations.

#### Graph Sparsification

Next, we sparsify graph $\mathcal{G}$ (or equivalently, matrix $\mathcal{A}$)
by considering only $k$ neighbors per scene (see Figure 2(d)). Compared to
fully connected graphs, sparse representations are computationally more
efficient and also have shown better classification accuracy (Ozaki et al.
2011; Zhu 2005). Moreover, we hypothesize that sparse graphs are crucial for
our turning point identification task. We anticipate the screenplay graph to
capture high-level differences and similarities between movies which would be
difficult to discern when each scene is connected to every other scene.

The most common way to obtain a sparse graph is to construct a $k$-NN graph by
introducing a threshold on the number of nearest neighbors $k$ (Szummer and
Jaakkola 2003; Goldberg and Zhu 2006; Niu, Ji, and Tan 2005). Specifically, we
create sparse graph $\mathcal{G}^{\prime}$ by selecting the set of neighbors
$\mathcal{P}_{i}$ for each scene $s_{i}$ as follows:

$\displaystyle\mathcal{P}_{i}=\operatorname{argmax}\limits_{j\in[1,N],|\mathcal{P}_{i}|=k}p_{ij}$
(3)

where $p_{ij}$ is calculated as in Eq. (1). After removing for each node the
neighbors not included in the set $\mathcal{P}_{i}$, the new graph
$\mathcal{G}^{\prime}$ contains edges $|\mathcal{E}^{\prime}|\ll|\mathcal{E}|$
which are unweighted.

Instead of a priori deciding on a fixed number of neighbors $k$ for all
scenes, which may cause false neighborhood assumptions, we treat $k$ as a
parameter to be learned as part of the network which computes
$p(y_{it}|s_{i},\mathcal{D})$, the probability of a scene being a TP. Figure
2(c) illustrates this neighborhood selection module. All connections of
$s_{i}\in\mathcal{G}$ serve as input to a non-linear fully-connected layer
which outputs a probability distribution $z_{i}$ over a pre-defined set of
neighborhood sizes $[1,C]$. We then select
$k_{i}=\operatorname{argmax}_{t\in[1,C]}z_{it}$ as the neighborhood size for
scene $s_{i}$ in the sparse graph $\mathcal{G}^{\prime}$.

When deciding on the neighborhood size $k_{i}$ and the set of neighbors
$\mathcal{P}_{i}$ for scene $s_{i}$, we perform discrete choices, which are
not differentiable. We address these discontinuities in our model by utilizing
the Straight-Through Estimator (Bengio, Léonard, and Courville 2013). During
the backward pass we compute the gradients with the Gumbel-softmax
reparametrization trick (Maddison, Mnih, and Teh 2017; Jang, Gu, and Poole
2017). To better approximate the $\operatorname{argmax}$ selections (for $k$
and $\mathcal{P}$) during backpropagation, we also add a low temperature
parameter $\tau=0.1$ (Hinton, Vinyals, and Dean 2015) in the
$\operatorname{softmax}$ function, shown in Eq. (1).

### Graph Convolutional Networks

We rely on graph convolutional networks (GCNs; Duvenaud et al. 2015; Kearnes
et al. 2016; Kipf and Welling 2017) to induce embeddings representing graph
nodes. Our GCN operates over the sparsified graph $\mathcal{G}^{\prime}$ and
computes a representation for the current scene $s_{i}$ based on the
representation of its neighbors. We only encode information from the scene’s
_immediate_ neighbors and thus consider one layer of
convolution.222Performance deteriorates when stacking GCN layers. Moreover, in
accordance with Kipf and Welling (2017), we add a self-loop to all scenes in
$\mathcal{G}^{\prime}$. This means that the representation of scene $s_{i}$
itself affects the neighborhood representation $t_{i}$:

$\displaystyle t_{i}=f\left(\frac{1}{|P_{i}\cup\\{s_{i}\\}|}\sum_{j\in
P_{i}\cup\\{s_{i}\\}}\left(W_{g}c_{j}+b\right)\right)$ (4)

where $f(.)$ is a non-linear activation function (i.e.,
$\operatorname{ReLU}$), and vectors $c$ represent the _content_ of a scene (in
relation to the overall screenplay and its relative position).

We encode the screenplay as a sequence $v_{1},v_{2},...,v_{N}$ of textual
scene representations with a BiLSTM network and obtain contextualized
representations $c$ by concatenating the hidden layers of the forward
$\overrightarrow{h}$ and backward $\overleftarrow{h}$ LSTM
($c=[\overrightarrow{h};\overleftarrow{h}]$). In other words, graph
convolutions are performed on top of LSTM states (Marcheggiani and Titov
2017). The one-layer GCN only considers information about a scene’s immediate
neighbors, while contextualized scene representations $c$ capture longer-range
relations between scenes. Figure 2(e) illustrates our GCN and the computation
of the neighborhood representations $t$.

Finally, we concatenate the neighborhood representation $t_{i}$ and the
content representation $c_{i}$ to obtain an encoding for each scene $s_{i}$:
$[c_{i};t_{i}]$. This vector is fed to a single neuron that outputs
probabilities $p(y_{it}|s_{i},\mathcal{D})$.

### Model Training

Our description so far has assumed that TP labels are available for screenplay
scenes. However, in practice, such data cannot be easily sourced (due to the
time consuming nature of watching movies, reading screenplays, and identifying
TP locations). The only TP related dataset we are aware of is TRIPOD
(Papalampidi, Keller, and Lapata 2019) which contains TP labels for sentences
(not scenes) contained within movie synopses (not screenplays). For this
reason, we first train a teacher model which takes as input synopses marked
with gold-standard TP sentences and the corresponding screenplays $D$ and
outputs the probability $q(y_{it}|s_{i},D)$ for scene $s_{i}$ to convey the
meaning of the $t^{th}$ TP sentence, where $t\in[1,5]$.

We use the model proposed in Papalampidi, Keller, and Lapata (2019) as teacher
to obtain probability distribution $q(y_{t}|D)$ over screenplay $D$. The TP-
specific posterior distributions produced by the teacher model are used to
train our model which only takes scenes as input. Similarly to knowledge
distillation settings (Ba and Caruana 2014; Hinton, Vinyals, and Dean 2015) we
utilize the KL divergence loss between the teacher posterior distributions
$q(y_{t}|D)$ and the ones computed by our model $p(y_{t}|D)$:

$\displaystyle\mathcal{O}_{t}=\mathcal{D}_{KL}\left(p(y_{t}|D)\middle\|q(y_{t}|D)\right),t\in[1,T]$
(5)

where $T$ is the number of TPs. We further add a second objective to the loss
function in order to control adjacency matrix $S$ and hence the latent graph
$\mathcal{G}^{\prime}$. Intuitively, we want to assign higher probabilities
for scenes to be neighbors in $\mathcal{G}^{\prime}$ if they are also
temporally close in the screenplay. For this reason, we add a focal
regularization term $\mathcal{F}$ to the loss function. Specifically, we
assume a Gaussian distribution $g_{i}$ over the screenplay centered around the
current scene index $i$ and try to keep the probability distribution in matrix
$S$ that corresponds to candidate neighbors for scene $s_{i}$ close to the
prior distribution:
$\mathcal{F}_{i}=\mathcal{D}_{KL}\left(p_{i}\middle\|g_{i}\right)$.333We
disregard $\tau$ (see Eq. (1)) while recalculating probabilities $p_{ij}$,
since we want to directly regulate the $e_{ij}$ values. The loss function now
becomes:

$\displaystyle\mathcal{L}=\frac{1}{T}\sum_{t=1}^{T}\mathcal{O}_{t}+\lambda\frac{1}{N}\sum_{i=1}^{N}\mathcal{F}_{i}$
(6)

where $\lambda$ is a hyperparameter.

## Experimental Setup

| Train | Test
---|---|---
movies | 84 | 38
scenes | 11,320 | 5,830
TP scenes | 1,260 (SS) | 340 (GS)
vocabulary | 37.8k | 28.3k
per movie
scenes | 133.0 (61.1) | 153.4 (54.0)
sentences | 3.0k (0.9) | 2.9k (0.6)
tokens | 23.0k (6.6) | 21.5k (4.0)
video length (secs) | 6.8k (1.1) | 6.9k (1.3)
video frames | 4.2k (3.0) | 3.5k (1.1)
audio segments | 12.0k (10.3) | 9.7k (3.1)
per scene
sentences | 22.2 (31.5) | 19.0 (24.9)
tokens | 173.0 (235.0) | 139.9 (177.5)
sentence tokens | 7.8 (6.0) | 7.4 (6.0)
video length (secs) | 88.1 (152.5) | 81.6 (114.8)
video frames | 29.2 (37.3) | 23.0 (26.3)
audio segments | 82.8 (133.6) | 62.9 (94.0)
Table 1: Statistics of the augmented TRIPOD dataset; means are shown with
standard deviation in brackets. SS: silver-standard labels based on
Papalampidi, Keller, and Lapata (2019), GS: gold-standard labels.

#### Multimodal TRIPOD

We performed experiments on the TRIPOD dataset
444https://github.com/ppapalampidi/TRIPOD (Papalampidi, Keller, and Lapata
2019) originally used for analyzing the narrative structure of movies. We
augmented this dataset by collecting gold-standard annotations for 23 new
movies which we added to the test set. The resulting dataset contains 17,150
scenes from 122 movies, 38 of which have gold-standard scene-level annotations
and were used for evaluation purposes. We also collected the videos and
subtitles for the TRIPOD movies. Table 1 presents the dataset statistics.

#### Data Preprocessing

We used the Universal Sentence Encoder (USE; Cer et al. 2018a) to obtain
sentence-level representations. Following previous work (Tapaswi, Bäuml, and
Stiefelhagen 2015), subtitles (and their timestamps on the movie video) were
aligned to the dialogue parts of the screenplay using Dynamic Time Wrapping
(DTW; Myers and Rabiner 1981). Subsequently, we obtained alignments of
screenplay scenes to video segments. Finally, we segmented the video into
scenes and extracted audiovisual features.

For the visual modality, we first sampled one out of every 50 frames within
each scene. However, the length of a scene can vary from a few seconds to
several minutes. For this reason, in cases where the number of sampled frames
became too big for memory, we lowered the sampling frequency to one frame per
150. We employed ResNeXt-101 (Xie et al. 2016) pre-trained for object
recognition on ImageNet (Deng et al. 2009) to extract a visual representation
per frame. Similarly, for the audio modality, we used YAMNet pre-trained on
the AudioSet-YouTube corpus (Gemmeke et al. 2017) for classifying audio
segments into 521 audio classes (e.g., tools, music, explosion); for each
audio segment contained in the scene, we extracted features from the
penultimate layer.

#### Implementation Details

Following (Papalampidi, Keller, and Lapata 2019), we select $l=3$ consecutive
scenes to represent each TP in the summary. Moreover, we set the maximum size
of neighbors $C$ that can be selected for a scene in graph
$\mathcal{G}^{\prime}$ to 6, since we want to create a sparse and
interpretable graph. Experiments with fixed-sized neighborhoods also showed
that performance dropped when considering neighborhoods over 6 scenes. For
training our model we set the hyperparameter $\lambda$ in Eq. (6) to 10. We
used the Adam algorithm (Kingma and Ba 2014) for optimizing our networks. We
chose an LSTM with 64 neurons for encoding scenes in the screenplay and an
identical one for contextualizing them. We also added a dropout of 0.2. Our
models were developed in PyTorch (Paszke et al. 2019) and PyTorch geometric
(Fey and Lenssen 2019). For analyzing the movie graphs we used NetworkX
(Hagberg, Swart, and S Chult 2008).

## Results

Our experiments were designed to answer three questions: (1) Is the proposed
graph-based model better at identifying TPs compared to less structure-aware
variants? (2) To what extent are graphs and multimodal information helpful?
and (3) Are the summaries produced by automatically identified TPs meaningful?

#### Which Model Identifies TPs Best

Table 2 addresses our first question. We perform 5-fold cross-validation over
38 gold-standard movies to obtain a test-development split and evaluate model
performance in terms of three metrics: Total Agreement (TA), i.e., the
percentage of TP scenes that are correctly identified, Partial Agreement (PA),
i.e., the percentage of TP events for which at least one gold-standard scene
is identified, and Distance ($D$), i.e., the minimum distance in number of
scenes between the predicted and gold-standard set of scenes for a given TP,
normalized by the screenplay length (see Appendix for a more detailed
definition of the evaluation metrics). We consider TA and PA as our main
evaluation metrics as they measure the percentage of exact TP matches.
However, apart from identifying important events, when producing a summary it
is also important to display events from all parts of the movie in order to
accurately describe its storyline. For this reason, we also employ the
distance $D$ metric which quantifies how well distributed the identified TP
events are in the movie. Hence, a disproprionately large $D$ suggests that the
model fails to even predict the correct sections of a movie where TPs might be
located let alone the TPs themselves.

|  TA $\uparrow$ |  PA $\uparrow$ |  D $\downarrow$
---|---|---|---
Random (evenly distributed) | 4.82 | 6.95 | 12.35
Theory position | 4.41 | 6.32 | 11.03
Distribution position | 5.59 | 7.37 | 10.74
TextRank | 6.18 | 10.00 | 17.77
|  \+ audiovisual
---
6.18 | 10.00 | 18.90
SceneSum | 4.41 | 7.89 | 16.86
|  \+ audiovisual
---
6.76 | 11.05 | 18.93
| TAM
---
7.94 | 9.47 | 9.42
|  \+ audiovisual
---
7.36 | 10.00 | 10.01
| GraphTP
---
6.76 | 10.00 | 9.62
|  \+ audiovisual
---
9.12 | 12.63 | 9.77
Table 2: Five-fold crossvalidation. Total Agreement (TA), Partial Agreement
(PA), and mean distance $D$.

The first block in the table compares our graph-based TP identification model
(henceforth GraphTP) against the following baselines: a random selection of a
sequence of three scenes from five evenly segmented sections of the movie
(reported mean of five runs); the selection of a sequence of three scenes that
lie on the expected position of each TP event according to screenwriting
theory (Hauge 2017); and the selection of a sequence of three scenes based on
the position of gold-standard TPs in the synopses of the TRIPOD training set.
The second block includes the performance of two unsupervised summarization
models: TextRank (Mihalcea and Tarau 2004) with neural input representations
(Zheng and Lapata 2019)555We also experimented with directed TextRank (Zheng
and Lapata 2019), but these results were poor and are omitted for the sake of
brevity. and SceneSum (Papalampidi et al. 2020; Gorinski and Lapata 2015), a
variant of TextRank that takes the characters participating in each scene into
account. Finally, we report results for the Topic-Aware Model (TAM;
Papalampidi et al. 2020); TAM is sequence-based supervised model which employs
a sliding context window and computes the similarity between sequential
contexts. We discuss implementation details for comparison systems in the
Appendix. We also report the performance of a multimodal variant for all
comparison systems (+audiovisual). For the unsupervised models, we add scene-
level features as extra weights to the pairwise similarity calculation between
scenes similarly to GraphTP. For TAM, we add audiovisual information via early
fusion; we concatenate the scene-level vectors from all modalities (i.e.,
text, vision, audio).

The unsupervised summarization models (TextRank, SceneSum) have competitive
performance in terms of TA and PA, but significantly higher average distance
D. This suggests that they do not select events from all parts of a story but
favor specific sections. For the supervised models (TAM and GraphTP), the
average D is in general lower, which means that they are able to adapt to the
positional bias and select events from all parts of a movie. Moreover, both
models seem to benefit from multimodal information (see TA and PA metrics).
Finally, GraphTP seems to perform best, by correctly identifying a higher
number of gold-standard TP events (based on both TA and PA metrics), whereas D
is comparable for TAM and GraphTP.

|  |  TA $\uparrow$
---
|  PA $\uparrow$
---
|  D $\downarrow$
---
| Fully connected graph
---
5.00 | 7.37 | 9.73
| Content
---
5.59 | 7.37 | 9.98
| Neighborhood & position
---
9.71 | 13.16 | 10.98
| GraphTP
---
6.76 | 10.00 | 9.62
|  \+ vision
---
6.18 | 7.89 | 9.84
|  \+ audio
---
7.06 | 8.95 | 10.38
|  \+ audiovisual
---
9.12 | 12.63 | 9.77
Table 3: GraphTP variants. Total Agreement (TA), Partial Agreement (PA), and mean distance D. | SceneSum | TAM | GraphTP | Gold
---|---|---|---|---
TP1 | 28 | 28 | 64 | 66
TP2 | 36 | 54 | 64 | 62
TP3 | 38 | 18 | 44 | 54
TP4 | 26 | 34 | 52 | 56
TP5 | 8 | 16 | 24 | 48
Mean | 27 | 30 | 50 | 57
Rating | 2.63 | 2.68 | 3.02 | 3.58
Table 4:  Human evaluation; proportion of TPs found in video summaries (shown
as percentages) and average ratings attributed to each system (ratings vary
from 1 to 5, with 5 being best). All pairwise differences are significant
($p<0.05$, using a $\chi^{2}$ test).

#### Which Information Matters

Table 3 answers our second question by presenting an ablation study on
GraphTP. We observe that the performance of a similar model which uses a
fully-connected graph drops across metrics. This is also the case when we do
not take into account a graph or any other form of interaction between scenes
(i.e., only content). We also test the model’s performance when we remove the
content representation and keep only the neighborhood interactions together
with a vector that simply encodes the position of a scene in the screenplay
(as a one-hot vector). This model may not be able to adapt to the positional
bias as well (higher D), but is able to predict TPs with higher accuracy (high
TA and PA). Finally, we find that audio and visual information boost model
performance in combination but not individually.

#### How Good Are the Summaries

We now answer our last question by evaluating the video summaries produced by
our model. We conducted a human evaluation experiment using the videos created
for 10 movies of the test set. We produced summaries based on the gold scene-
level annotations (Gold), SceneSum, TAM, and GraphTP (see Appendix). For all
systems we used model variants which consider audiovisual information except
for SceneSum. Inclusion of audiovisual information for this model yields
overly long summaries (in the excess of 30 minutes) for most movies. All other
systems produce 15 minutes long summaries on average.

TP1TP2TP3TP4TP5$0.4$$0.6$$0.8$Comedy/RomanceThriller/MysteryActionDrama/Other
Figure 3: Average node connectivity per TP across movie genres (GraphTP
(+audiovisual), test set.)

Our study was conducted on Amazon Mechanical Turk (AMT). Crowdworkers first
read a short summary of the movie (i.e., an abridged version of the Wikipedia
plot synopsis). Subsequently, they were asked to watch a video summary and
answer five questions each pertaining to a specific TP event (described in the
textual summary). AMT workers answered with ‘Yes’ if they were certain it was
present in the video, ‘No’ if the event was absent, and ‘Unsure’ otherwise.
Finally, we asked AMT workers to provide an overall rating from 1 to 5, with 5
being the most informative summary. Workers were asked to take into account
the questions answered previously, but also consider the overall quality of
the summary (i.e., how compressed it was, whether it contained redundant
events, and the overall information provided). We asked 5 different workers to
evaluate each movie summary. Instructions and example questions are in the
Appendix.

Table 4 shows the proportion of ‘Yes’ answers (per TP and overall mean) and
the average system rating.666We omit ’Unsure’ from Table 4, since it only
accounts for 4.1% of the answers. Perhaps unsurprisingly gold summaries are
the most informative. Some key events might still be absent due to errors in
the automatic alignment between the screenplay scenes and the video. GraphTP
is the second best system overall (and across TPs), while SceneSum and TAM
have similar ratings. GraphTP manages to create more informative and diverse
summaries, presenting important events from all parts of the story.

#### What Do the Graphs Mean

We further analyzed the graphs induced by our model, in particular their
connectivity. Figure 3 shows the average node connectivity per TP (i.e.,
minimum number of nodes that need to be removed to separate the remaining
nodes into isolated subgraphs) for the movies in the test set. For this
analysis, graphs were pruned to nodes which act as TPs and their immediate
neighbors and movies were grouped in four broad genre categories
(comedy/romance, thriller/mystery, action and drama/other). We find that
thrillers and mysteries correspond to more disconnected graphs followed by
dramas, while comedies, romance and especially action movies display more
connected graphs. This is intuitive, since comedies and action movies tend to
follow predictable storylines, while thrillers often contain surprising events
which break screenwriting conventions. Moreover, for comedies and dramas the
introductory events (i.e., first two TPs) are the central ones in the graph
and connectivity decreases as the story unfolds and unexpected events take
place. We see the opposite trend for thrillers and action movies. Initial
events present lower connectivity, while the last ones are now central when
crucial information is revealed justifying earlier actions (e.g., see the last
two TPs which correspond to ‘major setback’ and ‘climax’). A similar picture
emerges when visualizing the graphs (see Figure 4). “Die Hard”, a conventional
action movie, has a clear storyline and seems more connected, while ”American
Beauty”, a drama with several flashbacks, contains several disconnected
subgraphs (see Appendix for more illustrations).

Die Hard | American Beauty
---|---
|
Figure 4: Examples of graphs produced by GraphTP (+audiovisual) for two movies
from the test set. Nodes (in color) are scenes which act as TPs and their
immediate neighbors (in gray).

## Conclusions

In this paper we demonstrate that TP identification can be used directly for
summarizing movies. We propose GraphTP, a model that operates over sparse
graphs relying on multimodal information. Summaries created by GraphTP are
preferred by humans in contrast to general summarization algorithms and
sequence-based models. In the future, we will explore ways to further exploit
the graph structure and definitions of TPs in order to produce personalized
summaries.

## Acknowledgments

We thank the anonymous reviewers for their feedback. We gratefully acknowledge
the support of the European Research Council (Lapata; award 681760,
“Translating Multiple Modalities into Text”) and of the Leverhulme Trust
(Keller; award IAF-2017-019).

## References

  * Ba and Caruana (2014) Ba, J.; and Caruana, R. 2014.  Do Deep Nets Really Need to be Deep?  In _Proceedings of the Advances in NeurIPS_.
  * Bengio, Léonard, and Courville (2013) Bengio, Y.; Léonard, N.; and Courville, A. 2013.  Estimating or propagating gradients through stochastic neurons for conditional computation.  _arXiv preprint arXiv:1308.3432_ .
  * Black and Wilensky (1979) Black, J. B.; and Wilensky, R. 1979.  An evaluation of story grammars.  _Cognitive science_ 3(3): 213–229.
  * Cer et al. (2018a) Cer, D.; Yang, Y.; Kong, S.-y.; Hua, N.; Limtiaco, N.; John, R. S.; Constant, N.; Guajardo-Cespedes, M.; Yuan, S.; Tar, C.; et al. 2018a.  Universal sentence encoder.  _arXiv preprint arXiv:1803.11175_ .
  * Cer et al. (2018b) Cer, D.; Yang, Y.; Kong, S.-y.; Hua, N.; Limtiaco, N.; St. John, R.; Constant, N.; Guajardo-Cespedes, M.; Yuan, S.; Tar, C.; Strope, B.; and Kurzweil, R. 2018b.  Universal Sentence Encoder for English.  In _Proceedings of the 2018 Conference on EMNLP: System Demonstrations_.
  * Chambers and Jurafsky (2009) Chambers, N.; and Jurafsky, D. 2009.  Unsupervised Learning of Narrative Schemas and their Participants.  In _Proceedings of the 47th Annual Meeting of ACL and the 4th IJCNLP_.
  * Cutting (2016) Cutting, J. E. 2016.  Narrative theory and the dynamics of popular movies.  _Psychonomic bulletin & review_ 23(6).
  * Deng et al. (2009) Deng, J.; Dong, W.; Socher, R.; Li, L.-J.; Li, K.; and Fei-Fei, L. 2009.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on CVPR_ , 248–255. Ieee.
  * Do, Tran, and Tran (2018) Do, T. T. H.; Tran, Q. H. B.; and Tran, Q. D. 2018.  Movie indexing and summarization using social network techniques.  _Vietnam Journal of Computer Science_ 5(2): 157–164.
  * Duvenaud et al. (2015) Duvenaud, D. K.; Maclaurin, D.; Iparraguirre, J.; Bombarell, R.; Hirzel, T.; Aspuru-Guzik, A.; and Adams, R. P. 2015.  Convolutional networks on graphs for learning molecular fingerprints.  In _Advances in NeurIPS_ , 2224–2232.
  * Fey and Lenssen (2019) Fey, M.; and Lenssen, J. E. 2019.  Fast Graph Representation Learning with PyTorch Geometric.  In _ICLR Workshop on Representation Learning on Graphs and Manifolds_.
  * Finlayson (2012) Finlayson, M. A. 2012.  _Learning Narrative Structure from Annotated Folktales_.  Ph.D. thesis, MIT.
  * Frermann, Cohen, and Lapata (2018) Frermann, L.; Cohen, S. B.; and Lapata, M. 2018.  Whodunnit? Crime Drama as a Case for Natural Language Understanding.  _TACL_ 6\.
  * Fujii, Kitaoka, and Nakagawa (2007) Fujii, Y.; Kitaoka, N.; and Nakagawa, S. 2007.  Automatic extraction of cue phrases for important sentences in lecture speech and automatic lecture speech summarization.  In _INTERSPEECH_.
  * Gemmeke et al. (2017) Gemmeke, J. F.; Ellis, D. P.; Freedman, D.; Jansen, A.; Lawrence, W.; Moore, R. C.; Plakal, M.; and Ritter, M. 2017.  Audio set: An ontology and human-labeled dataset for audio events.  In _2017 IEEE ICASSP_ , 776–780. IEEE.
  * Goldberg and Zhu (2006) Goldberg, A.; and Zhu, X. 2006.  Seeing stars when there aren’t many stars: Graph-based semi-supervised learning for sentiment categorization.  In _Proceedings of TextGraphs: the First Workshop on Graph Based Methods for NLP_.
  * Gorinski and Lapata (2015) Gorinski, P. J.; and Lapata, M. 2015.  Movie Script Summarization as Graph-based Scene Extraction.  In _Proceedings of the 2015 Conference of NAACL-HLT_.
  * Goyal, Riloff, and Daumé III (2010) Goyal, A.; Riloff, E.; and Daumé III, H. 2010.  Automatically producing plot unit representations for narrative text.  In _Proceedings of the 2010 Conference on EMNLP_ , 77–86.
  * Grusky, Naaman, and Artzi (2018) Grusky, M.; Naaman, M.; and Artzi, Y. 2018.  NEWSROOM: A Dataset of 1.3 Million Summaries with Diverse Extractive Strategies.  In _Proceedings of the 16th Annual Conference of NAACL-HLT_.
  * Hagberg, Swart, and S Chult (2008) Hagberg, A.; Swart, P.; and S Chult, D. 2008.  Exploring network structure, dynamics, and function using NetworkX.  Technical report.
  * Hauge (2017) Hauge, M. 2017.  _Storytelling Made Easy: Persuade and Transform Your Audiences, Buyers, and Clients – Simply, Quickly, and Profitably_.  Indie Books International.
  * Hinton, Vinyals, and Dean (2015) Hinton, G.; Vinyals, O.; and Dean, J. 2015.  Distilling the knowledge in a neural network.  _arXiv preprint arXiv:1503.02531_ .
  * Jang, Gu, and Poole (2017) Jang, E.; Gu, S.; and Poole, B. 2017.  Categorical Reparametrization with Gumble-Softmax.  In _ICLR_.
  * Jung et al. (2019) Jung, T.; Kang, D.; Mentch, L.; and Hovy, E. 2019.  Earlier Isn’t Always Better: Sub-aspect Analysis on Corpus and System Biases in Summarization.  _arXiv preprint arXiv:1908.11723_ .
  * Kazantseva and Szpakowicz (2010) Kazantseva, A.; and Szpakowicz, S. 2010.  Summarizing Short Stories.  _Computational Linguistics_ 36(1).
  * Kearnes et al. (2016) Kearnes, S.; McCloskey, K.; Berndl, M.; Pande, V.; and Riley, P. 2016.  Molecular graph convolutions: moving beyond fingerprints.  _Journal of computer-aided molecular design_ 30(8): 595–608.
  * Kingma and Ba (2014) Kingma, D. P.; and Ba, J. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ .
  * Kipf and Welling (2017) Kipf, T. N.; and Welling, M. 2017.  Semi-Supervised Classification with Graph Convolutional Networks.  In _ICLR_.
  * Lehnert (1981) Lehnert, W. G. 1981.  Plot Units and Narrative Summarization.  _Cognitive Science_ 5(4): 293–331.
  * Liu and Lapata (2019) Liu, Y.; and Lapata, M. 2019.  Hierarchical Transformers for Multi-Document Summarization.  In _Proceedings of the 57th Annual Meeting of ACL_.
  * Lohnert, Black, and Reiser (1981) Lohnert, W. G.; Black, J. B.; and Reiser, B. J. 1981.  Summarizing narratives.  In _Proceedings of the 7th international joint conference on Artificial intelligence-Volume 1_ , 184–189.
  * Maddison, Mnih, and Teh (2017) Maddison, C. J.; Mnih, A.; and Teh, Y. W. 2017.  The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables.  In _5th ICLR_. OpenReview.net.
  * Mani (2012) Mani, I. 2012.  _Computational Modeling of Narative_.  Synthesis Lectures on Human Language Technologies. Morgan and Claypool Publishers.
  * Marcheggiani and Titov (2017) Marcheggiani, D.; and Titov, I. 2017.  Encoding Sentences with Graph Convolutional Networks for Semantic Role Labeling.  In _Proceedings of the 2017 Conference on EMNLP_.
  * McInnes et al. (2018) McInnes, L.; Healy, J.; Saul, N.; and Großberger, L. 2018.  UMAP: Uniform Manifold Approximation and Projection.  _Journal of Open Source Software_ 3(29): 861.
  * McIntyre and Lapata (2010) McIntyre, N.; and Lapata, M. 2010.  Plot Induction and Evolutionary Search for Story Generation.  In _Proceedings of the 48th Annual Meeting of ACL_.
  * Mihalcea and Ceylan (2007) Mihalcea, R.; and Ceylan, H. 2007.  Explorations in Automatic Book Summarization.  In _Proceedings of the 2007 Joint Conference on EMNLP and CoNLL_.
  * Mihalcea and Tarau (2004) Mihalcea, R.; and Tarau, P. 2004.  Textrank: Bringing order into text.  In _Proceedings of the 2004 conference of EMNLP_.
  * Murray et al. (2007) Murray, G.; Hsueh, P.-Y.; Tucker, S.; Kilgour, J.; Carletta, J.; Moore, J. D.; and Renals, S. 2007.  Automatic segmentation and summarization of meeting speech.  In _Proceedings of NAACL-HLT_ , 9–10.
  * Myers and Rabiner (1981) Myers, C. S.; and Rabiner, L. R. 1981.  A comparative study of several dynamic time-warping algorithms for connected-word recognition.  _Bell System Technical Journal_ 60(7).
  * Narayan, Cohen, and Lapata (2018) Narayan, S.; Cohen, S. B.; and Lapata, M. 2018.  Don’t Give Me the Details, Just the Summary! Topic-Aware Convolutional Neural Networks for Extreme Summarization.  In _Proceedings of the 2018 Conference on EMNLP_.
  * Niu, Ji, and Tan (2005) Niu, Z.-Y.; Ji, D.-H.; and Tan, C. L. 2005.  Word Sense Disambiguation Using Label Propagation Based Semi-Supervised Learning.  In _Proceedings of the 43rd Annual Meeting of ACL_.
  * Ozaki et al. (2011) Ozaki, K.; Shimbo, M.; Komachi, M.; and Matsumoto, Y. 2011.  Using the mutual k-nearest neighbor graphs for semi-supervised classification on natural language data.  In _Proceedings of the fifteenth conference of CoNLL_ , 154–162.
  * Papalampidi et al. (2020) Papalampidi, P.; Keller, F.; Frermann, L.; and Lapata, M. 2020.  Screenplay Summarization Using Latent Narrative Structure.  In _Proceedings of the 58th Annual Meeting of ACL_.
  * Papalampidi, Keller, and Lapata (2019) Papalampidi, P.; Keller, F.; and Lapata, M. 2019.  Movie Plot Analysis via Turning Point Identification.  In _Proceedings of the 2019 Conference on EMNLP and the 9th IJCNLP_.
  * Papasarantopoulos et al. (2019) Papasarantopoulos, N.; Frermann, L.; Lapata, M.; and Cohen, S. B. 2019.  Partners in Crime: Multi-view Sequential Inference for Movie Understanding.  In _Proceedings of the 2019 Conference on EMNLP and the 9th IJCNLP_.
  * Paszke et al. (2019) Paszke, A.; Gross, S.; Massa, F.; Lerer, A.; Bradbury, J.; Chanan, G.; Killeen, T.; Lin, Z.; Gimelshein, N.; Antiga, L.; et al. 2019.  PyTorch: An imperative style, high-performance deep learning library.  In _Advances in NeurIPS_ , 8024–8035.
  * Propp (1968) Propp, V. I. 1968.  _Morphology of the Folktale_.  University of Texas.
  * Richards, Finlayson, and Winston (2009) Richards, W.; Finlayson, M. A.; and Winston, P. H. 2009.  Advancing Computational Models of Narrative.  Technical Report 63:2009, MIT Computer Science and Atrificial Intelligence Laboratory.
  * Rohrbach et al. (2015) Rohrbach, A.; Rohrbach, M.; Tandon, N.; and Schiele, B. 2015.  A dataset for movie description.  In _Proceedings of the IEEE conference on CVPR_.
  * Rumelhart (1980) Rumelhart, D. E. 1980.  On evaluating story grammars.  _Cognitive Science_ 4(3): 313–316.
  * Schank and Abelson (1975) Schank, R. C.; and Abelson, R. P. 1975.  Scripts, Plans, and Knowledge.  In _Proceedings of the 4th International Joint Conference on Artificial Intelligence_ , 151–157. Tblisi, USSR.
  * Srivastava, Chaturvedi, and Mitchell (2016) Srivastava, S.; Chaturvedi, S.; and Mitchell, T. 2016.  Inferring Interpersonal Relations in Narrative Summaries.  In _Proceedings of the 13th AAAI Conference_.
  * Syed et al. (2018) Syed, S.; Völske, M.; Potthast, M.; Lipka, N.; Stein, B.; and Schütze, H. 2018.  Task Proposal: The TL; DR Challenge.  In _Proceedings of the 11th International Conference on Natural Language Generation_ , 318–321.
  * Szummer and Jaakkola (2003) Szummer, M.; and Jaakkola, T. S. 2003.  Information Regularization with Partially Labeled Data.  In Becker, S.; Thrun, S.; and Obermayer, K., eds., _Advances in NeurIPS 15_.
  * Tapaswi, Bäuml, and Stiefelhagen (2015) Tapaswi, M.; Bäuml, M.; and Stiefelhagen, R. 2015.  Aligning plot synopses to videos for story-based retrieval.  _International Journal of Multimedia Information Retrieval_ 4(1).
  * Tapaswi, Bauml, and Stiefelhagen (2015) Tapaswi, M.; Bauml, M.; and Stiefelhagen, R. 2015.  Book2movie: Aligning video scenes with book chapters.  In _Proceedings of the IEEE Conference on CVPR_ , 1827–1835.
  * Tapaswi et al. (2016) Tapaswi, M.; Zhu, Y.; Stiefelhagen, R.; Torralba, A.; Urtasun, R.; and Fidler, S. 2016.  Movieqa: Understanding stories in movies through question-answering.  In _Proceedings of the IEEE conference on CVPR_.
  * Teufel and Moens (2002) Teufel, S.; and Moens, M. 2002.  Articles Summarizing Scientific Articles: Experiments with Relevance and Rhetorical Status.  _Computational Linguistics_ 28(4).
  * Thompson (1999) Thompson, K. 1999.  _Storytelling in the new Hollywood: Understanding classical narrative technique_.  Harvard University Press.
  * Tran et al. (2017) Tran, Q. D.; Hwang, D.; Lee, O.-J.; and Jung, J. E. 2017.  Exploiting character networks for movie summarization.  _Multimedia Tools and Applications_ 76(8): 10357–10369.
  * Tsoneva, Barbieri, and Weda (2007) Tsoneva, T.; Barbieri, M.; and Weda, H. 2007.  Automated summarization of narrative video on a semantic level.  In _ICSC_.
  * Valls-Vargas, Zhu, and Ontanon (2014) Valls-Vargas, J.; Zhu, J.; and Ontanon, S. 2014.  Toward automatic role identification in unannotated folk tales.  In _Proceedings of the 10th AAAI Conference_ , 188–194.
  * Wang et al. (2020) Wang, D.; Liu, P.; Zheng, Y.; Qiu, X.; and Huang, X. 2020.  Heterogeneous Graph Neural Networks for Extractive Document Summarization.  In _Proceedings of the 58th Annual Meeting of ACL_.
  * Xie et al. (2016) Xie, S.; Girshick, R.; Dollár, P.; Tu, Z.; and He, K. 2016.  Aggregated Residual Transformations for Deep Neural Networks.  _arXiv preprint arXiv:1611.05431_ .
  * Xiong et al. (2019) Xiong, Y.; Huang, Q.; Guo, L.; Zhou, H.; Zhou, B.; and Lin, D. 2019.  A Graph-Based Framework to Bridge Movies and Synopses.  In _Proceedings of the IEEE ICCV_ , 4592–4601.
  * Zheng and Lapata (2019) Zheng, H.; and Lapata, M. 2019.  Sentence Centrality Revisited for Unsupervised Summarization.  _arXiv preprint arXiv:1906.03508_ .
  * Zhu (2005) Zhu, X. 2005.  _Semi-supervised Learning with Graphs_.  Ph.D. thesis, Carnegie Mellon University.

##  Appendix A Evaluation Metrics

For evaluating TP identification, we use three different metrics, Total
Agreement (TA), Partial Agreement (PA) and Distance $D$, as suggested in
Papalampidi, Keller, and Lapata (2019). TA is the percentage of TP scenes that
are correctly identified, i.e.:

$\displaystyle TA=\frac{1}{T\cdot L}\sum_{i=1}^{T\cdot L}{\frac{|S_{i}\cap
G_{i}|}{|S_{i}\cup G_{i}|}}$ (7)

where $S_{i}$ is the set of scenes selected as representative for a specific
TP event in a movie, $G_{i}$ is the ground-truth set of scenes representing
this TP event, $T$ is the number of TP events (i.e., 5) and $L$ is the number
of movies contained in the test set.

PA is the percentage of TP events for which at least one ground-truth TP scene
is identified, i.e.:

$\displaystyle PA=\frac{1}{T\cdot L}\sum_{i=1}^{T\cdot L}{\left[S_{i}\cap
G_{i}\neq\emptyset\right]}$ (8)

Finally, $D$ is the average distance between all pairs of predicted TP scenes
$S_{i}$ and ground-truth TP scenes $G_{i}$ with respect to the screenplay
length (i.e., number of screenplay scenes). Formally:

$\displaystyle d[S_{i},G_{i}]=\frac{1}{N}\min_{(s\in S_{i},g\in G_{i})}|s-g|$
(9) $\displaystyle D=\frac{1}{T\cdot L}\sum_{i=1}^{T\cdot L}{d[S_{i},G_{i}]}$
(10)

where $d[S_{i},G_{i}]$ is the minimum distance between two sets $S_{i}$ and
$G_{i}$ corresponding to the same TP event in a movie.

Intuitively, the TA and PA metrics measure the percentage of exact matches on
TP identification. However, since we seek to identify a very small number of
scenes (i.e., 2–3 on average) in the screenplay as representative of a
specific event, the number of exact matches is expected to be low. For this
reason, we also evaluate model performance based on the $D$ metric. $D$ gives
us an estimate on how well distributed the identified TP events are in the
movie. Moreover, a large average $D$ indicates that a model is not able to
predict the correct section in the movie where TP event is located and hence,
such a performance is considered poor.

| Category
---
| Movies
---
| Comedy/Romance
---
’Juno’, ’The Back-up Plan’, ’The Breakfast Club’, ’500 Days of Summer’,
’Crazy, Stupid, Love’, ’Easy A’, ’Marley & Me’, ’No Strings Attached’
| Thriller/Mystery
---
’Arbitrage’, ’Panic Room’, ’The Shining’, ’One Eight Seven’, ’Black Swan’,
’Gothika’, ’Heat’, ’House of 1000 Corpses’, ’Sleepy Hollow’, ’The Talented Mr.
Ripley’, ’The Thing’
| Action
---
’Die Hard’, ’Soldier’, ’The Crying Game’, ’Total Recall’, ’2012’, ’From Russia
with Love’, ’American Gangster’, ’Collateral Damage’,’Oblivion’
| Drama/Other
---
’Moon’, ’Slumdog Millionaire’, ’The Last Temptation of Christ’, ’Unforgiven’,
’American Beauty’, ’Jane Eyre’, ’The Majestic’, ’A Walk to Remember’
Table 5: Movies from test set divided in four broad categories based on their genre. | Movie
---
| Summary
---
| Questions
---
| Arbitrage
---
|  Sixty-year-old magnate Robert Miller manages a hedge fund with his daughter
Brooke and is about to sell it for a handsome profit. However, unbeknownst to
his daughter and most of his other employees, he has cooked his company’s
books in order to cover an investment loss and avoid being arrested for fraud.
One night, while driving with his mistress Julie Cote, he begins to doze off
and crashes; Julie is killed. Miller covers up Julie’s death with Jimmy’s
help. The next day, he is questioned by police detective Bryer. Bryer is keen
on arresting Miller for manslaughter and begins to put the pieces together.
Jimmy is arrested and placed before a grand jury but still refuses to admit to
helping Miller. The case against Jimmy is dismissed and the detective is
ordered not to go near him. Miller’s wife tries to blackmail him with a
separation agreement getting rid of his wealth. In the final scene, Miller
addresses a banquet honoring him for his successful business, with his wife at
his side and his daughter introducing him to the audience but their false
embrace on the stage signifies that he has lost the respect and admiration of
his daughter.
---
|  1\. Did the video summary show the accident and Julie’s death?
---
2\. Did the video summary show Bryer’s suspicions towards Miller?
3\. Did the video summary show Jimmy’s arrest and the police’s efforts to get
Jimmy to admit helping Miller?
4\. Did the video summary show that Miller’s wife blackmailed him?
5\. Did the video summary show Miller give a speech about his successful
business with his family on his side in the end?
| The Back-up Plan
---
|  Zoe has given up on finding the man of her dreams and decided to become a
single mother and undergoes artificial insemination. The same day she meets
Stan when they both try to hail the same taxi. After running into each other
twice more, Stan asks Zoe on a date. At the end of the date Stan asks her to
come to his farm during the weekend and Zoe finds out that she is pregnant. In
the farm Zoe tells Stan that she is pregnant and he is confused and angry at
first. However, Stan decides he still wants to be with her and they reconcile.
After many misunderstandings and comedic revelations, Zoe and Stan are walking
into the Market when they run into Stan’s ex-girlfriend. Due to Stan’s remark
that the twins are not his, Zoe believes that he is not ready to become a
father to them, and breaks off the relationship. At her grandmother’s wedding,
Zoe’s water breaks and on the way to the hospital they make a pit stop at the
Market. Zoe apologizes to Stan and they begin to work things out. He pulls out
a penny, that he kept from their first acquaintance, and Zoe promises to trust
him more.
---
|  1\. Did the video summary show Zoe and Stan’s first encounter in a taxi?
---
2\. Did the video summary show Zoe discover that she is pregnant?
3\. Did the video summary show Stan’s commitment to Zoe after finding out that
she is pregnant?
4\. Did the video summary show Zoe and Stan’s break up?
5\. Did the video summary show the final reconciliation between Stan and Zoe?
| Juno
---
|  Sixteen-year-old Minnesota high-schooler Juno MacGuff discovers she is
pregnant with a child fathered by her friend and longtime admirer, Paulie
Bleeker. She initially considers an abortion, but finally decides to give the
baby up for adoption. Juno meets a couple, Mark and Vanessa Loring, in their
expensive home and agrees to a closed adoption. After some time, where Juno
gets to know the couple better and not long before her baby is due, she is
again visiting Mark when their interaction becomes emotional. A few moments
later, she watches the Loring marriage fall apart, then drives away and breaks
down in tears by the side of the road. Not long after, Juno goes into labor
and is rushed to the hospital, where she gives birth to a baby boy. Vanessa
comes to the hospital where she joyfully claims the newborn boy as a single
adoptive mother.
---
|  1\. Did the video summary show Juno discover that she is pregnant?
---
2\. Did the video summary show Juno’s decision to give the baby up for
adoption?
3\. Did the video summary show Juno’s first visit to Mark and Vanessa’s house?
4\. Did the video summary show Mark and Vanessa’s breakup?
5\. Did the video summary show Vanessa adopt Juno’s baby as a single mother in
the end?
Table 6: Examples of movies used for human evaluation. We present a short text summary per movie based on Wikipedia and the questions we asked for evaluating the information contained in each video summary. Different colors in the summary correspond to different TPs (i.e., TP1, TP2, TP3, TP4, TP5). The Wedding Date | Easy A | Marley & Me
---|---|---
|  |
Die Hard | Total Recall | From Russia With Love
|  |
Figure 5: Examples of graphs produced by GraphTP (+audiovisual) for movies from the test set. Nodes (in color) are scenes which act as TPs and their immediate neighbors (in gray). Genre category per row: comedy/romance, action. All graphs are dense and present high connectivity.  Panic Room | The Thing | Black Swan
---|---|---
|  |
American Beauty | Jane Eyre | Slumdog Millionaire
|  |
Figure 6: Examples of graphs produced by GraphTP (+audiovisual) for movies
from the test set. Nodes (in color) are scenes which act as TPs and their
immediate neighbors (in gray). Genre category per row: thriller/mystery,
drama/other. The graphs here present low connectivity containing several
disconnected subgraphs.  Figure 7: Analysis of the graphs for the movies of
the test set with regard to their scores in Rotten Tomatoes. We computed
various metrics, such as node connectivity, diameter and triadic closure, that
describe each movie graph. Next, we performed dimensionality reduction using
UMAP and visualize all movies in two dimensions. A small distance between
movies in the figure indicates structural similarity between their graphs.
Regarding the scores, rotten are the movies with a score lower than 60%,
otherwise they are fresh.

##  Appendix B Comparison Systems

Except for GraphTP, we evaluate the performance of the general summarization
algorithm TextRank, its character-based version SceneSum specific to
narratives and a sequence-based TP identification model, namely TAM.

###  TextRank

For TextRank, we consider a screenplay graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, with nodes $\mathcal{V}$ representing
the scenes and edges $\mathcal{E}$ the similarity between scenes, similarly
with GraphTP. We compute the textual scene representations $s$ and the
similarity $e_{ij}$ between all pairs of scenes $s_{i},s_{j}$ as described in
Papalampidi et al. (2020). Finally, for each scene $s_{i}$ we compute a
centrality score:

$\displaystyle\textit{centrality}(s_{i})=\lambda_{1}\sum_{j<i}e_{ij}+\lambda_{2}\sum_{j>i}e_{ij}$
(11)

where $\lambda_{1}=\lambda_{2}=0.5$. We use the undirected version of
TextRank, since when considering different values for $\lambda_{1}$ and
$\lambda_{2}$ (Zheng and Lapata 2019; Papalampidi et al. 2020), only an
isolated part of the movie receives high centrality scores. Finally, we select
the five scenes with the highest centrality scores and sequentially assign
them to each TP. In accordance with GraphTP, each TP is again represented by
three consecutive scenes (the currently selected scene and its immediate
neighbors in the screenplay).

For the multimodal version of TextRank we again compute the audiovisual
similarity $u_{ij}$ between all pairs of scenes $s_{i},s_{j}$, as for GraphTP.
The only difference here is that we do not use trainable layers to project the
audio and visual representations for the segments and frames, respectively and
we do not consider attention weights when combining different representations,
since TextRank is an unsupervised algorithm with no training signal. Finally,
we again combine textual $e_{ij}$ and audiovisual $u_{ij}$ similarities via
multiplication. The combined similarity score is now used in Eq. (11).

###  SceneSum

SceneSum shares the same architecture with TextRank. However, it also
considers the characters participating in each scene as initially suggested by
Gorinski and Lapata (2015) and later adopted by Papalampidi et al. (2020).

Our implementation of SceneSum follows Papalampidi et al. (2020). For each
scene $s_{i}$ we calculate a character-related importance score $c_{i}$:

$\displaystyle c_{i}=\frac{\sum_{c\in C}\ [c\in C_{i}\ \cup\
\textit{main}(C)]}{\sum_{c\in C}\ [c\in C_{i}]}$ (12)

where $C_{i}$ is the set of all characters participating in scene $s_{i}$, $C$
is the set of all characters participating in the movie and $\textit{main}(C)$
are all the main characters. Gorinski and Lapata (2015) retrieve the main
characters in a movie by constructing a social network depicting all
interactions between characters and select the most central ones as the
protagonists. We follow a simpler approach and consider as main characters the
ones that are mentioned in the respective Wikipedia synopsis. We add the
importance scores $c_{i}$ and $c_{j}$ for scenes $s_{i}$ and $s_{j}$ to the
similarity score $e_{ij}$ –or the combined multimodal score $u_{ij}*e_{ij}$–
in Eq. (11) via summation (Papalampidi et al. 2020).

### Topic-Aware Model (TAM)

TAM is originally proposed by Papalampidi, Keller, and Lapata (2019) for
identifying scenes in a screenplay that describe a synopsis sentence marked as
TP. Later, Papalampidi et al. (2020) modified TAM to only consider screenplay
scenes –no synopsis information– for predicting TP events. In this work, we
use the later modification of TAM with the same implementation details. TAM
operates over a sequence of contextualized scene representations derived from
a BiLSTM over the whole screenplay. In order to better capture interactions
between scenes TAM considers a sliding context window of fixed length and
computes the similarity of a current scene with a previous and next context
representation. The hypotheses for TAM are that (1) TPs act as boundaries
between sections and hence a plunge in the similarity computation should be
noticed close to a TP and (2) the screenplay presents a sequence of events; no
entanglement between stories and events is taken into account. For the
multimodal version of TAM, we compute audio and visual representations for
each scene as for GraphTP. Next, we combine the different modalities for the
scene via concatenation.

##  Appendix C Implementation Details

GraphTP has 467.1K trainable parameters when using only textual information
and 797.2K when adding the audiovisual features. Similarly, text-only TAM has
401.2K and multi-modal TAM has 731.7K trainable parameters. We trained models
on a single GPU (GeForce GTX 1080). The average runtime is 20 minutes for
training the text-only models and 3 hours for the multi-modal ones.

##  Appendix D Human Evaluation

For the human evaluation experiment in Amazon Mechanical Turk (AMT), we
created textual summaries describing a movie’s storyline from beginning to
end. Specifically, we produced a shorter version of the Wikipedia plot
synopsis for each movie keeping only essential information. Next, we colored
differently the text in the summary that corresponded to each TP in order to
clearly demonstrate the important events in the movie.

We asked AMT workers to first read this textual summary paying extra attention
to the descriptions in colored text. Next, they watched an automatically
produced video summary for the movie and were asked to answer to five
questions. Each question examined whether a specific TP event was presented in
the video summary. Examples of the summaries given to the AMT workers
alongside with the corresponding questions are presented in Table 6. Finally,
we asked them to provide us with an overall rating for the video summary. In
this point, we asked workers to take into account the questions answered
previously, but also consider the quality of the summary (i.e., how condensed
the summary was, whether it contained redundant events, overall information
provided). The rating scale was 1 to 5, with 5 being the most informative and
least redundant.

##  Appendix E Graph Analysis

Our evaluation set contains 38 movies annotated with gold-standard scene-level
TP labels. During the analysis of the movie graphs, we divide the movies of
the test set into four broad categories based on their genre: comedy/romance,
thriller/mystery, action and drama/other. In Table 5, we present how these
movies are categories into genres. When a movie is characterised by more than
one genres, we categorize it only in its main category.

As described in Section 6, we create pruned graphs for each movie that contain
only the nodes that act as TPs and their immediate neighbors. We consider
these pruned graphs as a graphical description of a movie’s storyline
containing only the most important events and their semantic connections. In
Figures 5 and 6 we present examples of such graphs for various movies of the
test set. Figure 5 contains movies belonging to the comedy/romance and action
genre categories per row, respectively. Similarly, Figure 6 presents
illustrations of graphs for thriller/mystery and drama/other movies per row.
We can empirically observe that comedies and action movies (Figure 5) tend to
present denser graphs in comparison with thrillers and dramas (Figure 6) which
contain several disconnected subgraphs.

Except for each movie’s genre, we also consider the quality of the movie when
analyzing its graph. Specifically, we hypothesize that movies with high
ratings (e.g. according to Rotten Tomatoes777https://www.rottentomatoes.com/)
often have less predictable and distinctive storylines and hence would present
a different graph topology in comparison with those of poorly rated movies. In
order to test this hypothesis, we first analyze the graph topology using
several metrics from graph theory. Specifically, as when examining the graphs
with regard to different genres, we again consider the average node
connectivity and the node connectivity per TP. However, we now also compute
four extra metrics: the TP pairwise node connectivity (i.e., the average node
connectivity when considering only the nodes that act as TPs in order to
directly measure the degree of connectivity between TP events), the number of
disconnected components presented in the graph, its diameter (i.e., the
greatest distance between any pair of nodes) and the triadic closure (i.e.,
tendency of edges to form triangles). Next, we perform dimensionality
reduction using UMAP (McInnes et al. 2018) in order to project the movies of
the test set to two dimensions and visualize them.

We present the visualization of the movies in two dimensions in Figure 7.
Movies are colored differently depending on the score that they received in
Rotten Tomatoes (i.e. movies with a score equal or higher than 60% are
considered fresh (green star), otherwise rotten (red circle)). Although movies
are not perfectly divided into clusters according to their score category, we
observe that there is a tendency for movies with high scores to concentrate in
the upper right side of the figure, whereas a lot of poorly rated movies are
located in the leftmost, down side. This suggests that although each movie has
a unique storyline, and hence graph, the way that important events are
connected plays a significant role to the quality of the movie. Notably, a lot
of well-known unconventional movies with out-of-the-box storylines are located
in the ”fresh” cluster in the figure: e.g., ”American Beauty”, ”Black Swan”,
”The Thing’, ”Moon”.