Story Embedding: Learning Distributed Representations of Stories based on Character Networks (Extended Abstract)

1 Introduction

Various studies have been conducted to represent stories with a computational model. Most of the studies [Callaway and Lester, 2002; Mani, 2012; Jung et al., 2017] concentrated on what happened in stories (i.e., events). To convey the meanings of events, they have proposed representations that cover vast and detail information, such as actors in the events (characters), behaviors of the characters, purposes of the characters, consequences of the behaviors, causality between the events, and so on. This information was annotated using graphs [Purdy and Riedl, 2016] or markup languages [Mani, 2016].

Another approach is character networks, which are dynamic social networks of characters that appeared in the stories [Lee and Jung, 2019a; Labatut and Bost, 2019]. The character network is not comparable with the event-based models in terms of semantic-richness. Since the character network represents only the existence and frequency of interactions between the characters, this model cannot handle the exact meanings of the interactions or events. However, previous studies have shown that extracting character networks from narrative multimedia is much easier than composing the event-based models [Lee and Jung, 2019a]. Also, they exhibited that information in the character network is enough for a few practical applications: classifying characters [Weng et al., 2009; Park et al., 2012; Tran and Jung, 2015], summarizing [Tran et al., 2017; Bost et al., 2019], and recommending [Lee and Jung, 2019b] narrative multimedia. Since a story is a series of events and interactions between characters describe the events [McKee, 1997], we can assume the content of the events from tendencies of the interactions.

* This is an extended abstract of an article "Story Embedding: Learning Distributed Representations of Stories based on Character Networks" published in [Lee and Jung, 2020].

† Corresponding Author.

However, the above two models have a common limitation. They are graphical data representations, which aim to represent a single narrative work. Thus, these models have difficulties in comparing a story with another story. Although our previous studies [Lee and Jung, 2018; Lee and Jung, 2019b] attempted to estimate the similarity between stories, they commonly used hand-crafted and heuristic features. One of them [Lee and Jung, 2018] used cohesion of communities in character networks. Another one [Lee and Jung, 2019b] analyzed locations of major events in stories.

Since these hand-crafted features are designed for particular media or tasks, they are not much reusable in other applications or studies. For example, the number of characters and major events is different from kinds of media. TV series or epic novels will contain far more characters and major events than movies. This difference will affect both the communitybased and event-based similarity estimation.

This study aims to learn task-agnostic and mediaindependent representations of stories by embedding character networks. The existing studies have already shown that structural features of character networks are effective for analyzing stories [Labatut and Bost, 2019]. Therefore, we apply unsupervised graph embedding techniques to embed character networks.

To focus on the structural features, we discover substructures from character networks using the WL (WeisfeilerLehman) relabeling process [Shervashidze et al., 2011]. Then, with Doc2Vec [Le and Mikolov, 2014], we represent a story by predicting which substructures appear in its character network. We propose two story embedding models that consider time-sequential features of stories and not.

2 Preliminaries

This section presents the fundamental concepts and assumptions in this study. The existing studies [Lee and Jung, 2019a] represented the time-sequential features of stories by defining character networks as dynamic social networks. The nodes and edges of the character network are characters and interactions between the characters, respectively. Weights on the edges are interaction frequencies between characters. The character network is defined as follows;

Definition 1 (Character Network [Lee and Jung, 2019a]). Suppose that n is the number of characters that appeared in a narrative work, Cα, and Cα consists of L scenes from sα,1 to sα,L. When N(sα,l) indicates a character network on sα,l, N(sα,l) can be described as a matrix ∈ Rn×n . Each element of N(sα,l) denotes interaction frequency between two characters from sα,1 to sα,l. This can be formulated as:

where ai,j indicates the proximity of ci to cj when ci is the i-th character in Cα.

In this study, we extract the character network from movie scripts. Characters were identified by their names, scenes were segmented using scene headings, and ai,j was measured by the number of dialogues that ci spoke to cj.

The character network represents interactions between characters. Since the interactions are designed to describe events in scenes, we can roughly estimate the meanings of events by analyzing the interactions. For example, in 'The Godfather' (1972), interaction frequencies of 'Michael Corleone' for his family members became larger according to running time. This change reflects that 'Michael Corleone' turned from normal people to a mafia boss. Therefore, we assume that vector representations of character network structures reflect the content of corresponding stories. We call the vector representations 'story vectors.' This is defined as follows;

Definition 2 (Story Vector). Let Φ(Cα) be a story vector of Cα. Closer locations of Φ(Cα) and Φ(Cβ) indicate that N (Cα) and N (Cβ) have more similar structures. We suppose that when Cα and Cβ contain similar stories, N (Cα) and N (Cβ) are structurally similar. This is formulated as:

where k (·, ·) indicates a kernel function.

3 Story Embedding

This section presents methods of how we apply the graph structure embedding methods to character networks in consideration of narrative characteristics.

3.1 Social Roles of Characters

Various substructures are used for embedding structural features of graphs, such as subgraphs, subtrees, meta-paths, and so on. This study employs subgraphs and uses the WL relabeling process to discover the subgraphs. The WL relabeling describes local structures around each node in multiple scales. Character networks are relatively smaller than ordinary social networks, and communities of characters are placed around the protagonists [McKee, 1997]. Therefore, the subgraphs, which represent structures around nodes with specific ranges, are appropriate for embedding character networks.

The WL relabeling considers only adjacency between nodes. However, interaction frequencies between characters are as important as the existence of interactions. For example, a character has interactions with both the protagonist and antagonist. Which one is closer to the character than the other is significant for determining the character's role. Thus, as shown in Fig. 1, we modified the WL relabeling process to cover the proximity information. We call this modification 'proximity-aware WL relabeling.'

In character networks, all nodes are intrinsic. To apply the WL relabeling, we should assign labels on the characters and interactions. We cluster the characters and interactions into three categories according to their centrality and weights, respectively [Weng et al., 2009; Park et al., 2012; Tran and Jung, 2015]. As shown in Fig. 1 (a) and (b), characters are clustered into main (M), minor (m), and extra (e) characters. Also, interactions are clustered into high (H), meddle (M), and low (L) proximity. We use the k-means clustering method with three initial centroids: maximum, median, and minimum. Additionally, a character with the highest centrality is labeled as the protagonist (P).

Then, as shown in Fig. 1 (c), we describe subgraphs rooted in each character by using labels of adjacent characters and interactions. We assign the description on the character as a new label. In practice, we make a list by combining labels of adjacent characters and interactions (e.g., MH,mH, eH for ci in Fig. 1). We sort the list, put a label of the character at first, and apply the hash function for the list. By iterating the description and relabeling, labels of characters represent broader structures. Initial labels (P, M, m, and e) are subgraphs on degree 0. Each iteration makes subgraphs on degree d + 1 using subgraphs on degree d.

A subgraph represents the interactions of a character at a scale. Since we can conjecture the character's role from the interactions, we call the subgraph 'social role.' This is defined as follows;

Definition 3 (Social Role). Let c(d) i,l be a social role of ci on sα,l at a degree d ∈ [0,D]. c(d) i,l is expressed by one-hop connectivity of ci at degree d - 1. This is formulated as:

where H(d-1) i,l , M(d-1) i,l , and L(d-1) i,l indicate sets of social roles rooted in neighborhoods of ci at degree d - 1. These sets include neighborhoods that receive high, medium, and low proximity from ci, respectively.

In this study, we use Doc2Vec [Le and Mikolov, 2014] for embedding character networks. Doc2Vec trains vector representations by predicting occurrences of words in fixed-size windows. However, in graphs, the number of neighboring nodes is not constant. Narayanan et al. [2016] have proposed radial neighborhoods that define neighborhoods of a subgraph as subgraphs rooted in neighboring nodes on adjacent degrees. Since social roles also have temporal adjacency, we extend radial neighborhoods to temporal-radial neighborhoods as subgraphs rooted in neighboring nodes on adjacent degrees and scenes. This can be formulated as:

where N (·) indicates neighborhood sets of nodes or subgraphs, and ∆L and ∆D are window sizes for scenes and degrees, which are commonly 1 in this study.

3.2 Learning Representations of Stories

We embed character networks using which social roles occur in the character networks. In other words, stories are represented by which types of characters appear in the stories. For learning the occurrences, we propose two models: (i) flow-oriented Story2Vec (Story2Vec-F) and (ii) denouementoriented Story2Vec (Story2Vec-D).

Since stories are time-sequential, Story2Vec-F learns changes in social roles according to narrative time. Using the PV-DM (distributed memory model of paragraph vector) method in Doc2Vec, we predict co-occurrence probability between social roles in the temporal-radial neighborhoods. We estimate the co-occurrence probability of a social role given stories and neighboring social roles. As with the negative sampling [Mikolov et al., 2013], the estimation is conducted by applying the sigmoid function to inner products between vector representations of the case and condition. Since Story2Vec-F has multiple conditions, we make a representative vector of the conditions by averaging vectors for the conditions. This is formulated as:

where σ(·) indicates the sigmoid function, and ΦN (·) denotes a representative vector of conditions.

Therefore, an objective function of Story2Vec-F maximizes the co-occurrence probability of occurred social roles given stories and neighborhoods and minimizes the probability of the other social roles. This can be formulated as:

where Sb is an arbitrary social role, and ∑ indicates the arithmetic mean operator. However, we cannot examine all social roles; 37,631 social roles were in 142 movies. Thus, we use the negative sampling to reduce computational loads for the negative samples. The second term of Eq. 6 is estimated as:

where Pn (S) ∝ U(S) 34 indicates a noise distribution of social roles, which is proportional to their unigram distribution. The first term is as with Eq. 5. The vector representations are updated by the gradient of the objective function for the representations.

Climaxes and denouements of stories have more influence on user impressions than the other parts [McKee, 1997]. Story2Vec-D concentrates on structures of character networks at last. Using the PV-DBOW (distributed bag-ofwords version of the paragraph vector) method in Doc2Vec, Story2Vec-D predicts occurrence probability of social roles in only N(Cα) = N(sα,L). The method for predicting the occurrence probability is similar to Story2Vec-F. A difference is that Story2Vec-D has only one condition, stories. This can be formulated as:

An objective function of Story2Vec-D maximizes the occurrence probability of social roles that appeared in N(sα,L) and minimizes the probability of the others. This can be formulated as:

where S (sα,L) indicates a set of social roles discovered from N(sα,L). The second term of the objective function is estimated by the same method with Eq. 7, due to the negative sampling.

We integrate the above two models by conducting the models alternately. First, Story2Vec-F predicts all social roles in a story and updates their representations. Then, Story2Vec-D also conducts the prediction and update for social roles in the last scene. We call the combined model 'unified Story2Vec (Story2Vec-U).' Fig. 2 presents the results of the Story2VecUmodel for real movies.

4 Evaluation

We evaluated the proposed model by comparing its accuracy for estimating similarity between stories with the genre similarity. Similarity between Cα and Cβ was measured by a multiplication of cosine similarity and inverse of Euclidean distance between Φ (Cα) and Φ (Cβ). The similarity estimation is conducted for 142 real movies 1 . The genre similarity is calculated by applying the Jaccard index on genre sets of movies, which were annotated in IMDB 2 . Character networks were composed by CharNet-Extractor 3 by analyzing movie scripts collected from IMSDb 4 . As ground truth, we asked 50 human evaluators to annotate similarity between the movies through a web application 5 . The accuracy of the estimated similarity was measured by absolute errors for the annotated one.

Fig. 3 presents experimental results. The proposed models exhibited better performance than the genre similarity. The genre is the most widely-used taxonomy of narrative multimedia and mostly annotated by domain experts. This result underpins the effectiveness of the proposed models. Among the three proposed models, Story2Vec-D performed the highest accuracy. Climaxes and denouements of stories might have more influence on user impressions than the development of stories. Story2Vec-U outperformed only Story2VecF. The method for combining the dynamic and static approaches was useful, but not enough. Alternately conducting the two models might give too many learning opportunities to Story2Vec-F, comparing with Story2Vec-D.

1 https://github.com/O-JounLee/Story2Vec

2 https://www.imdb.com/

3 https://github.com/O-JounLee/CharNet-Extractor

4 https://www.imsdb.com/

5 http://recsys.cau.ac.kr:8084/movies/

5 Conclusion and Future Research

This study has proposed models for learning representations of stories by embedding character networks. Story2VecF/D reflect dynamic and static features, respectively, and Story2Vec-U combines the two approaches. Among the three, Story2Vec-D had the highest accuracy. Story2Vec-U improved the variance of the standalone cases but hindered the accuracy of Story2Vec-D. We should find a better method for integrating the dynamic and static approaches. This study also has the following research directions.

• Stories can be defined in various granularity levels, not only in a narrative work. Lee et al. [2020] partially solved this issue using the hierarchical representation learning, but still insufficient.
• Narrative multimedia have other physical features, excluding stories. We need a multi-modal representation learning method to cover both features.

Acknowledgments

This research was supported by the MSIT (Ministry of Science and ICT), Korea, under the ICT Consilience Creative program (IITP-2019-2011-1-00783) supervised by the IITP (Institute for Information & communications Technology Planning & Evaluation). Also, this work was supported by the Ministry of Education of the Republic of Korea and the National Research Foundation of Korea (NRF2020R1A2B5B01002207).