DEIM Forum 2019 B7-4

Comparative Timeline Summarization
Yijun DUAN† , Adam JATOWT† , and Masatoshi YOSHIKAWA†† Graduate School of Informatics, Kyoto University36-1 Yoshida-Honmachi, Sakyo-ku, Kyoto, 606-8501 Japan
E-mail: †{yijun,adam}@dl.kuis.kyoto-u.ac.jp, ††yoshikawa@i.kyoto-u.ac.jp
Abstract A significant fraction of documents these days are accounts of historical events. Biographies or descriptions of entity histories such as histories of geographical places or organizations are examples of such timeline
documents. Their content is explicitly or implicitly associated with timestamps indicating occurrence time of described past events. However, the collections of such timeline documents can be quite large and can pose challenge
for readers trying to make sense of them. We introduce in this paper a novel research task, Comparative Timeline
Summarization (CTS), as an effective strategy to discover important similarities and differences in collections oftimeline documents for providing contrastive type of knowledge. We then propose a three-step approach which relies
on a dynamic affinity-preserving mutually reinforced random walk for the CTS task and evaluate it on Wikipedia
categories. The summaries we generate are in the form of timelines consisting of salient and discriminative sentences
ordered chronologically.
Key words Comparative timeline summarization, Affinity-preserving mutually reinforced random walk, Dynamic
ranking

1 Introduction

with the histories of Japanese cities, or they would like toknow how different were the lives of French scientists in theMulti-Document Summarization (MDS) plays an impor-

19th century from those of American scientists at the sametant role in combating the problem of information overload

century. Note that such contrasting knowledge is difficult tocaused by the exponential growth of documents these days,

be manually obtained by users due to relatively large number

especially, ones posted on the Web. Quite many documentsof documents that would have to be analyzed. Another rea-

however contain chronologically ordered content describing

son is the difficulty in judging the significance of encounteredhistories of entities or detailed accounts of past events. Bi-

information by average users.

ographies and history sections of Wikipedia articles are two

Comparative timeline summarization (CTS) is then a so-

examples of such documents in which paragraphs or sen-lution that we propose to provide a condensed and informa-tences are associated with time indicators!JCm1!K denoting thetive timeline summary consisting of major contrasting events

chronological order of discussed events. We call such doc-

chronologically ordered for better understanding of the com-

uments, timeline documents, or, in short, timelines. Tra-

pared sets of timeline documents. Users could benefit fromditional MDS techniques are not suitable for summarizing

this kind of information for a myraid of needs such as gaining

timeline documents, due to their too general assumptions

insights from history, analyzing trends, making better deci-on sentence importance, as shown in [2]. In the recent years,

sions, as well as for educational or entertaining purposes. For

Multi-Timeline-Summarization (MTS) [2], [6] has been intro-

example, for a student who is interested in the comparison

duced to generate the common traits and to capture the com-

between histories of Chinese and Japanese cities, our study

mon temporal patterns within a set of timeline documents.

could greatly facilitate her understanding of these two sets.

Unlike MDS, MTS approaches make explicit use of the temporal character of input timelines.

Straightforward approach to this problem would be toformulate it as a comparative summarization task [7]?[11].

However, sometimes, users would like to compare two col-However, existing comparative summarization models arelections of timeline documents in order to discover common-

not suitable for our scenario, due to the strong temporal

alities and differences between them. For example, they may

character of the input documents in CTS task. Consider-

be interested in the comparison of histories of Chinese cities

ing the unique characteristic of our task, we have to deal
with two problems: (1) First, how to rank important in-!JCm1!K!’Typically, temporal expressions serve as such indicators. They canbe however implicit when time is obvious from context.

formation along the timeline?; (2) Second, how to generatea proper summary at various time scopes, within the time

finding diverse and salient threads in graphs of large doc-

range spanned by the input documents?

ument collections. Recently, differential topic models have

To provide effective summarization method we use the following hypotheses: (1) Timeline documents in the same set

also been explored to measure sentence discriminative capability for comparative summarization [10].

can be divided into latent eras, where sentences within the

2 2 Timeline Summarization

same era tend to be more similar to each other than sentences

Timeline Summarization defined as the summarization ofcontained in other eras; (2) A sentence is locally importantsequences of documents (typically, news articles about theif it is similar to many other sentences within the same era,same event) has been actively studied in the recent years.

and is globally important if it frequently appears in different

In [4], Yan et al. propose the evolutionary timeline summa-

eras of the same document set; (3) An important sentence

rization (ETS) to compute evolution timelines consisting ofis semantically dissimilar to the content of the contrastinga series of time-stamped summaries. David et al. [6] present

document set.

a method for discovering biographical structure based on a

To reflect the above hypotheses we rely on a three-step ap-

probabilistic latent variable model. His approach summa-

proach. We first discover latent eras of each compared docu-

rizes timestamped biographies to a set of event classes along

ment set by adopting the widely-used linear text segmenta-

with the typical times when those events occur. Satoko ettion algorithm [16]. We then propose an affinity-preserving

al. [?] present a graph-based algorithm for online summariza-

mutually reinforced random walk (APMRRW) method to ap-

tion of time-series documents. In that work, the authors it-

propriately model the relationship among sentences belong-eratively calculate sentence importance using random walks

ing to different document sets for selecting locally importantand pass important sentences to the next calculation. Abdal-

sentences. Finally, we develop a dynamic ranking model toghani et al. [5] address the problem of identifying important

extract globally important sentences. The dynamic ranking

events in the past, present, and future from semantically-model is also able to flexibly generate a proper summary atannotated large-scale document collections. Tuan et al. [1]various time scopes along the timeline.

present a novel approach for timeline summarization of high-To sum up, we make the following contributions in this

impact events, which uses entities instead of sentences forpaper: (1) We introduce a new research task of comparative

summarizing the events. Recently, Duan et al. [2] have in-timeline summarization. (2) We propose a three-stage ap-

troduced a novel type of summarization task consisting inproach including a novel dynamic affinity-preserving mutu-

generating gists of histories of multiple entities.

ally reinforced random walk model (D-APMRRW) for solv-

To the best of our knowledge, we are the first to work on

ing the above task. The proposed model is flexible overcomparative summarization of timeline documents. Unlike

different granularities of time units. (3) The effectivenessgeneral comparative summarization tasks, we focus on theof our approach is demonstrated by experiments on diverse

temporal characteristics of input documents. Finally, differ-

Wikipedia categories.

ent from timeline summarization tasks, we aim to discover

2 Related Work
2 1 Comparative Summarization
Comparative summarization requires providing short sum-discriminative and constrasting information for comparing
sets of timeline documents.

3 Problem Definition

maries from multiple comparative aspects. Wang et al. [7]We begin by defining the notion of timeline document. A

propose a discriminative sentence selection method based ontimeline document spans over a certain range of time and its

a multivariate normal generative model aiming to extract

sentences are assumed to refer to an event within the timesentences that are best describing the unique characteris-range. Each event is associated with a date, which can betics of each document group. Huang et al. [11] formulate theeither explicitly mentioned in the sentence or could be esti-

task of comparative news summarization as an optimization

mated based on context (e.g., nearby sentences).

problem of selecting sentences to maximize the score of com-

Formally, let DA and DB denote two sets of timeline doc-parative and representative evidences based on an integeruments to be compared. The purpose of comparative time-

linear programming (ILP) model. Ren et al. [8] explicitly

line summarization task is to form two timeline documents

consider contrast, relevance and diversity for summarizing

A
A
B
B
B
SA = {sA
1 , s2 , ..., sm } and SB = {s1 , s2 , ..., sm } consisting

contrastive themes by adopting a hierarchical nonparametricof meaningful sentences summarizing the representative andBayesian model to infer hierarchical relations among topics

contrasting information in input document sets, where sAifor enhancing the diversity of themes. Gillenwater et al. [9]and sB
i are sentences extracted from DA and DB respec-

develop a probabilistic approach to address the problem of

tively, and m denotes the summary size.

Given Θ = (T1 , T2 , ..., Tk ) as a list of k coherent eras, let

4 MethodDΘ denote the inside density of Θ as follows:

In order to compute sentence importance we state the fol-Pklowing assumptions:sl

l=1 alAssumption 1 Most timeline documents can be divided
into eras. An important sentence is then semantically simi-DΘ = Pkl=1

where sl =Pi∈[τbl ,τel ]

P

(2)

l
l 2
j∈[τbl ,τel ] Mij and al = (τe − τb ) re-

fer to the sum of all transformed cosine similarities in a era,lar to the era it belongs to.
Assumption 2 An important sentence is similar to sen-and the squared length of the era, respectively. Then the fi-tences in the same set while dissimilar to sentences in thenal process is to determine the location of the era boundaries.

contrasting set. Especially, it is more important if it is simi-

To initialize the segmentation process, the entire time spanlar to important events in the same set while being dissimilar[t1 , tn ] is placed as one coherent era. Then the C99 algorithm

to important events in the contrast set.

builds up a segmentation into k eras by greedily inserting a

Assumption 3 An important sentence can appear in

new boundary at each step which maximizes DΘ . Given the
discovered latent eras Θ, we compute the preliminary im-

many eras rather than appear in one era.
Based on the above hypotheses, we first focus in Sec. 4 1

portance score of a sentence v as its average similarity withon detecting latent eras of input documents embodying theevents in the same era T (v) which v belongs to as follows:

idea of Assumption 1. We then propose in Sec. 4 2 anImp(v, Tv ) =affinity-preserving random walk model to locally score sen-ranking algorithm which flexibly allows for generating glob-

in the APMRRW model introduced in the next step for se4 2 Affinity-Preserving Mutually Reinforced Ran-

4 1 Eras Detection
We first formulate the problem of eras detection as follows.
Given a document set D and a sequence of atomic time unitsξ = (t1 , t2 , ..., tn ), the task is to select a proper segmentation
Θ containing k eras that divide the entire time span [t1 , tn ],where each era Ti is expressed by two time points representing its beginning date τbi and the ending date τei . Formally,let Θ = (T1 , T2 , ..., Tk ), where Ti = [τbi , τei ]. To detect eras,
we refer to the C99 algorithm [16], which is a linear text segmentation algorithm achieving promising results. The algorithm assumes that sentences within the same era tend to be
more similar to each other compared to sentences containedin other eras. It takes as an input the pairwise cosine similarities between all atomic time unit pairs in order to generate
a similarity matrix M , with entries Mij = Simcosine (ti , tj ).
Since only the relative values are meaningful, C99 transfers
each value of M into the fraction of its neighbors with smaller

X[Mij > Mlk ]dom Walk
In this section we introduce our proposed APMRRW
model for locally scoring sentences, which are assumed tobe similar to sentences in the same set while dissimilar tosentences in the contrasting set, within the same time unit.
We first briefly explain the Affinity-Preserving Random Walk
model, which recently has been reported to achieve the stateof-the-art performance amont the graph-based summarization models [12], and then extend it to the our proposed
APMRRW model for with the comparative summarization
scenario.
4 2. 1 Affinity-Preserving Random Walk
Given a graph G = (V, E) with vertex set V and edge
set E = V 2 , where each edge e = (vi , vj ) ∈ E is associatedwith a weight wij , a random walk on graph G is definedas the discrete-time Markov chain with transition probability matrix P . P is a row-stochastic matrix computed byvalue, where the neighborhood is an r × r block:X

The scores of sentences will be used as their initial scores
lecting locally important sentences.

ally important summary.

Mij =

(3)

v

tences following Assumption 2. Finally, motivated by Assumption 3, we present in Sec. 4 3 the idea of a dynamic

X
1·
Simcosine (v, e)|Tv | e∈T(1)l∈[i−r/2,i+r/2] k∈[j−r/2,j+r/2]

P = D−1 W , where D is a diagonal matrix with entries
P
Dii = vj ∈V wij and W is the adjacency matrix with entries

Wij = wij .

However the traditional random walk suffers from demo-

where the value of the expression in square brackets equals

cratic normalization mechanism [12] from W to P . The prob-

to 1 if the inequality holds, otherwise 0. Each time unit islem here is that the number of salient sentences (which are

now represented by a transformed vector of its cosine sim-

good candidates to be included in the summary) is usually

ilarity with each other unit. The goal of the above matrix

far less than the number of bad candidate sentences given

transformation is to enhance the contrast between different

the summary length limit. Under the democratic normal-

eras.

ization of P = D−1 W , a random surfer is highly likely tovisit another neighboring bad candidate sentence when it issimilarly. We then perform a two-layer affinity-preserving

currently at a bad sentence given their high similarity. Suchmutually reinforced random walk to propagate the node

process can intrinsically suppress the effect of good candi-

scores based on internal importance propagation within thedates as well as amplify the adverse effect of bad sentences.

same layer and external mutual reinforcement between dif-

To make good and bad vertices more distinguishable,

ferent layers as follows:

affinity-preserving random walk has been proposed [14].
With a new normalization technique, it is able to preserveT
xt+1= (1 − α) · x0A + α · PAA
PAB xtBA(5)

the original affinity relations between vertices. Given a graphT
xt+1= (1 − α) · x0B + α · PBBPBA xtA
B(6)′

G = (V, E), an augmented graph G is constructed by adding
an absorbing vertex v0 to G. An affinity-preserving random′

walk on graph G is defined as the discrete-time Markov

For numerical computation of the saliency scores, we caniteratively run the above two equations until convergence.

chain with transition probability matrix P , where P is for-Here, xtA and xtB denote respectively the scores of the sen-mulated as [14]:tence set VA and of the sentence set VB at the t-th iteration,
which integrates the initial score and the score including

P =

T

1

0

e − v/||W ||1

W/||W ||1!

within- and between-layer propagation. The initial impor-(4)tance scores x0A and x0B of the two sets are ones computed

Here, 0 and e are 1 × |V | vectors with all elements 0 and
1, respectively.

v = [D11 , D22 , ..., D|V ||V | ]T contains thetotal weights coming from each vertex. The affinity matrix W is normalized by its first norm (equal in value tomaxi=1,2,...|V | v[i], or maxi=1,2,...|V | Dii ). During the affinitypreserving random walk, the surfer can not walk out of theabsorbing vertex once it reaches there. On the other hand,
it is less likely for the surfer at good sentences than bad sentences to walk into the absorbing vertex. Note that to ensure
a good characterization of the sentence ranking distribution′

on graph G , we turn to the quasi-stationary distribution
x [13], [14] as the distribution of unabsorbed random walkers, which is defined as xi = P rob(X = vi |X =| v0 ), and X
4 2. 2 Affinity-Preserving Mutually Reinforced Random
Given two input sets of timeline documents DA
weconstruct

In order to guarantee the convergence of the iterative form,xA and xB are normalized after each iteration.
4 3 Dynamic Ranking Algorithm
We now present the idea of a dynamic ranking frameworkfor generating globally important sentences, which are assumed to be locally important in many time units. A comparative summary S̃ can be generated for any period when
it is required. In each atomic time unit t, a two-layer graphwhose vertices correspond to the sentences of the two compared document sets within t is constructed, and the aforelocally rank the sentences. Then the sentence ranked by
APMRRW is reranked by the commonly used MMR algo-

Walk (APMRRW)
DB ,scores sum to 1. In this paper, we empirically set α = 0.85
as 0.85 is a commonly used value of the damping factor [15].

mentioned APMRRW algorithm is applied to the graph torepresents the position of random walker.

andby Eq. (3) in Sec. 4 1 after normalization such that theatwo-layer

graph

G̃

=

(VA , VB , v0A , v0B , EAA , EBB , EAB ), where VA and VB denotethe sets of sentences contained in DA and DB respectively,
while v0A and v0B denote the absorbing vertex in each layer.
EAA , EBB and EAB correspond to the edge sets reflecting
the relation between sentences in VA , the relation between
sentences in VB , and the relation between sentences in VA

rithm [18] to avoid redundancy in a summary, by providing
penalty corresponding to the similarity between a newly extracted sentences and the already extracted sentences. Basedon the ranking score, top m sentences (m is the pre-definedsummary length introduced in Sec. 3) are selected as thesummary at the time unit t, and will be passed over to thenext time unit as past information. Then a new graph consisting of both the previous summary and sentences in a newunit is constructed and the same procedure is applied. In

and VB , respectively.
We then compute affinity metrics WAA , WBB , WAB and
WBA . Let WAA = [wvA ,vA ]|VA |×|VA | , where affinity wvA ,vA
i

i

j

j

is from Simcosine (viA , vjA ). We define WBB , WAB and WBA
in a similar way, where wvA ,vB = 1 − Simcosine (viA , vjB ),ijthis way, the summarization process works dynamically anda comparative summary of input article sets can be generated
for any given period within the entire time span if necessary.

5 Experiments

reflecting the dissimilarity between vertices viA and vjB .
Next, affinity metrics WAA , WBB , WAB and WBA are normalized to transition metrics PAA , PBB , PAB and PBA ,,respectively without hurting the affinity information. Let
PAA = WAA /||WAA ||1 , and WBB , WAB , WBA are computed

5 1 Datasets
We test our methods on diverse Wikipedia categories.
Since our research problem is non-trivial and unexplored,
hence to make the evaluation more feasible, we selected fromexisting Wikipedia categories and lists of moderate size, withrepresentative and discriminative sentences and (2) write awhich all the annotators were quite familiar. In particular,

300-word summary of the selected text.

we perform experiments on generating the comparative sum-

5 4 Analyzed Methods

mary of histories of 3 pairs of Wikipedia categories including

We list below all the analyzed methods as follows. We pre-location categories (Japanese cities vs. Chinese cities, de-pare D-APMRRW for the overall process as described in Sec.

noted as L1 and L2 ), organization categories (western teams

4. We test D-APMRRW* for the model that only considersof The National Basketball Association (NBA) league inthe steps in Sec. 4 2 and in Sec. 4 3, thus skipping the era

North America vs. eastern teams of NBA, denoted as O1

detection in Sec. 4 1. Similarly, we test D-MRRW and APM-

and O2 ) and person categories (Japanese Prime Ministers

RRW for the models that skip the affinity-preserving in Sec.

till the end of WW2 vs. Japanese Prime Ministers after

4 2, and the dynamic ranking in Sec. 4 3, respectively. To

WW2, denoted as P1 and P2 ), respectively. For preparing

assess the effectiveness of D-APMRRW, our baselines also

the documents, the history of each entity is extracted from

include recent related work. For comparative summariza-

the ”History” section in the corresponding Wikipedia arti-

tion models (denoted as CS models), we use the discrimina-cle. To capture historical events, we collect all sentences

tive sentence selection model (DSS, [7]) and the integer lin-along with a single date following related works [2], [6], [25]ear programming model (ILP, [11]) as baselines. For timeline

using SUTime [22]. The basic statistics about our datasets

summarization methods (denoted as TS models), we test theare shown in Tab. 1.

exemplar-based Markov random walk model (E-MRW, [2]),exemplar-based HITS model (E-HITS, [2]), and the online

Table 1 Summary of datasets
Dataset
L1
L2
O1
O2
P1
P2

Category
Japanese Cities
Chinese Cities
Western NBA Teams
Eastern NBA Teams
Japanese PMs (pre WW2)
Japanese PMs (post WW2)

# Docs
532
357
15
15
32
30

# Sentences
22,045
6,444
3,755
3,701
2,338
1,715

graph-based model (OGM, [?]). We also consider two popular multi-document summarization methods (denoted as
MDS models): (1) LexRank [20] that ranks sentences via aMarkov random walk strategy and (2) ClusterCMRW [19]which scores sentences by a clustering-based approach.
5 5 Evaluation Metrics

5 2 Experimental Settings
In this study, we experimentally set the summary size to be
20 sentences. For era detection (Sec. 4 1), we let the numberof eras for the location and organization datasets to be 10,
and for the person datasets to be 5 following [2]. The time
unit is empirically set to 1 year (see Sec. 5 7). In this study
we adopt the widely-used Skip-gram model [24] to represent
terms and sentences. We obtain the distributed vector representations of each word by training the Skip-gram modelon the entire English Wikipedia from 2016 using the gensim
Python library [23]. The vector representation of a sentence
is a TF-IDF weighted combination of the vectors of terms.
The number of dimensions of word vectors is experimentally
set to 200.
5 3 Reference Summary
To assess the quality of generated summaries by different
test methods, three human judges manually annotated theexperimental datasets. After reading the content of two compared document sets, the annotators were asked to write up
to 300-words long!JCm2!Kreference summary for each document
set that will help in grasping the contrastive content of input
document collections. In particular, we pool the summaries
created by all the analyzed methods, then the following instructions were given to the annotators: (1) select all theWe evaluate all the models using ROUGE-1.5.5 toolkit [17].
The ROUGE is a widely used metric which has been officially adopted by DUC for automatic summarization evaluation. It measures summary quality by counting overlapping
units between the candidate summary and the reference summary [17]. In the experiment, we report the f-measure values of ROUGE-1, ROUGE-2, ROUGE-L, ROUGE-W and
ROUGE-SU, which are based on overlapping unigrams, bigrams, longest common subsequence (LCS), weighted LCS
and skip-bigrams plus unigrams, respectively. The higher the
ROUGE scores are, the more similar the machine-generated
summary and the reference summary are, and thus the more
effective the summarization approach is.
5 6 Results and Discussion
Tab. 2 shows the performance of summaries generated by
all the methods in terms of ROUGE scores. From the results, we make the following observations. (1) D-APMRRW
model exhibits the best performance in terms of all metrics.

In addition, our proposed D-APMRRW model, D-

APMRRW* model and D-MRRW model all achieve higher
ROUGE scores than compared recent works, which proves
the summarization effectiveness of the proposed models. (2)D-APMRRW model, which considers the overall process as
described in Sec. 4, outperform all its variants. More concretely, D-APMRRW shows a 27.2%, 27.4% and 326.7% in-!JCm2!K!’The average length of an English sentence is around 15 words [7], so
we choose 300 as the number of words for the summary size of 20 sentences.

crease in terms of average ROUGE score compared to D-

APMRRW*, D-MRRW and APMRRW, respectively. Hence,card sentences whose dates are implicitly associated. Such

we conclude that the proposed assumptions all help to en-

temporal information should also be estimated and utilized,

hance the performance of salient sentence extraction, andfor example, by using approaches similar to [21]. Third, ourthat dynamic ranking (Sec. 4 3) offers a more significant per-models produce summaries in which each event is in the form

formance increase than era detection (Sec. 4 1) and affinityof a sentence from a particular timeline document. The sen-preservation (Sec. 4 2). This observation implies that glob-

tence representation may however contain too specific details

ally important sentences are better candidates than locallywhich might be true only for the instance from which theimporant sentences to be included in the summary.

given sentence has been extracted. To improve the readabil-

2, it can also be observed that the exist-

ity of generated summary, one would need to incorporate

ing methods perform relatively poorly. For multi-document

abstractive summarization strategies or generalization pro-summarization methods, the plausible reason can be thatcedures.

From Tab.

they tend to select very general sentences similar to manyother sentences in the same document set, while such sen-

6 Conclusions and Future Worktences may not have enough discrimination nor may interest

This work approaches the problem of a special kind ofannotators. Contrastingly, the comparative summarization

summarization task - comparative timeline summarization

methods focus more on discovering sentences delivering set-

(CTS). The special character of our proposed summarization

specific information, which prevents them from embodying

allows capturing important comparative aspects of evolution-

historic significance. Finally, regarding the timeline summa-

ary trajactories hidden in two sets of timeline documents.

rization methods, although they aim to discovering salient

Users can benefit from such novel task for needs including

temporal information, they suffer from similar drawbacks ofgaining insights from history, analyzing trends, as well as

multi-document summarization methods.

for educational or entertaining purposes. To address the in-

5 7 Additional Analysis

troduced problem we develop a three-step approach which

We further investigate the influence of the value of α inconsists of era detection, an affinity-preservining mutually

Eq. (5) and Eq. (6) as well as the value of time unit in dy-

reinforced random walk model and a dynamic ranking pro-namic ranking, as shown in Fig. 1. We first test the α withincess. The effectiveness of our models has been demonstrated

the range [0, 1] and with a step of 0.1. We can see from theby the experiments on 3 pairs of Wikipedia category datasets

figure that the value of α has an effect on the performance ofusing ROUGE toolkit.

summarization. In this paper, we empirically set α = 0.85 as

In future, we plan to conduct evaluation on diverse types of0.85 is a commonly used value of the damping factor [15]. In

timeline documents as well as incorporate abstractive sum-

additon, the length of time unit is set in the range [1,10] withmarization strategies for increasing the readability of the gen-a step of 1 year. When time unit is larger than 1, the sys-erated summaries. We will also extract and utilize temporaltem achieves worse performance due to the plausible reason

information in input text more thoroughly using an approachthat many good candidate sentences are discarded duringof [21].

the dynamic ranking, as we enlarge the candidate sentences
set while keeping the summary size fixed per local scoring.
In general, we can see that both α and time unit need to befine-tuned to achieve an optimal performance.
5 8 Limitations
This work has several limitations that we need to acknowledge. First, while we assume that many timeline documents
can be divided into latent eras (e.g., dynasties in histories
of cities), there may exist timelines which are not following
such hypothesis. In such case our approach will fail in segmenting the whole time span of input documents, as wellas initializing the importance of each candidate text unit.
Moreover, most existing works involving linear text segmentation [2], [16], [26] rely on a pre-defined number of eras, while
the number of latent eras should be automatically decided
based on the input documents. Second, although we makeuse of sentences whose dates are explicitly mentioned, we dis-

7 Acknowledgements
This research has been supported by JSPS KAKENHI
grants (18H03243, 17H01828, 18K19841).
References[1] Tran, T.A., Nieder ee, C., Kanhabua, N., Gadiraju, U.,
Anand, A.: Balancing nov- elty and salience: Adaptive
learning to rank entities for timeline summarization of highimpact events. In: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. pp. 12011210. ACM (2015)[2] Duan, Y., Jatowt, A., Tanaka, K.: Discovering typical histories of entities by multi- timeline summarization. In: Proceedings of the 28th ACM Conference on Hypertext andSocial Media. pp. 105114. ACM (2017)[3] Suzuki, S., Kobayashi, I.: On-line summarization of timeseries documents using a graph-based algorithm. In: Proceedings of the 28th Pacific Asia Conference on Language,
Information and Computing (2014)[4] Yan, R., Wan, X., Otterbacher, J., Kong, L., Li, X., Zhang,Y.: Evolutionary time- line summarization: a balanced op-

Table 2 Overall performance comparison of all methods using ROUGE scores.
Type

Acronym

ROUGE-1

ROUGE-2

ROUGE-L

ROUGE-W

ROUGE-SUCS models

DSS
ILP

0.050
0.090

0.007
0.023

0.050
0.089

0.012
0.020

0.002
0.008

MDS models

LexRank
ClusterCRMW

0.159
0.178

0.045
0.053

0.156
0.175

0.032
0.037

0.020
0.024

TS models

E-MRW
E-HITS
OGM

0.184
0.105
0.182

0.104
0.031
0.103

0.181
0.104
0.180

0.036
0.022
0.033

0.023
0.006
0.022

Proposed models

APMRRW
D-MRRW
D-APMRRW*
D-APMRRW

0.080
0.218
0.209
0.258

0.022
0.163
0.188
0.251

0.079
0.217
0.208
0.258

0.017
0.045
0.041
0.049

0.003
0.029
0.027
0.040

Figure 1 Performance of D-APMRRW w.r.t. α (left) and time unit (right).

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

timization framework via iterative substitution. In: Proceedings of the 34th international ACM SIGIR conference
on Research and development in Information Retrieval. pp.
745754. ACM (2011)
Abujabal, A., Berberich, K.: Important events in the past,present, and future. In: Proceedings of the 24th International Conference on World Wide Web. pp. 13151320.
WWW !G
15 Companion, ACM, New York, NY, USA (2015).
Bamman, D., Smith, N.A.: Unsupervised discovery of biographical structure from text. Transactions of the Association for Computational Linguistics 2, 363376 (2014)
Wang, D., Zhu, S., Li, T., Gong, Y.: Comparative document summarization via discriminative sentence selection.
TKDD 6(3), 12 (2012)
Ren, Z., de Rijke, M.: Summarizing contrastive themes
via hierarchical non- parametric processes. In: SIGIR. pp.
93102. ACM (2015)
Gillenwater, J., Kulesza, A., Taskar, B.: Discovering
diverse and salient threads in document collections. In:
EMNLP. pp. 710720. Association for Computational Linguistics (2012)
He, L., Li, W., Zhuge, H.: Exploring differential topic models for comparative summarization of scientific papers. In:
COLING. pp. 10281038 (2016)
Huang, X., Wan, X., Xiao, J.: Comparative news summarization using linear pro- gramming. In: Proceedings of the49th Annual Meeting of the Association for Computational
Linguistics: Human Language Technologies: Short PapersVolume 2. pp. 648653. Association for Computational Linguistics (2011)
Wang, K., Liu, T., Sui, Z., Chang, B.: Affinity-preserving
random walk for multi- document summarization. In: Proceedings of the 2017 Conference on Empirical Methods in
Natural Language Processing. pp. 210220 (2017)
Darroch, J.N., Seneta, E.: On quasi-stationary distributions

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

in absorbing discrete- time finite markov chains. Journal ofApplied Probability 2(1), 88100 (1965)
Cho, M., Lee, J., Lee, K.M.: Reweighted random walks
for graph matching. In: European conference on Computer
vision. pp. 492505. Springer (2010)
Brin,S.,Page,L.:Reprint of The anatomy of a large-scale hypertextual web search engine. Computer networks 56(18),38253833 (2012)
Choi, F.Y.: Advances in domain independent linear text
segmentation. In: Pro- ceedings of the 1st North American
chapter of the Association for Computational Linguistics
conference. pp. 2633. Association for Computational Linguistics (2000)
Lin, C.Y., Hovy, E.: Automatic evaluation of summaries
using n-gram co- occurrence statistics. In: Proceedings ofthe 2003 Conference of the North Ameri- can Chapter ofthe Association for Computational Linguistics on Human
Language Technology-Volume 1. pp. 7178. Association for
Computational Linguistics (2003)
Carbonell, J., Goldstein, J.: The use of mmr, diversitybased reranking for reorder- ing documents and producing
summaries. In: SIGIR. pp. 335336. ACM (1998)
Wan, X., Yang, J.: Multi-document summarization using
cluster-based link anal- ysis. In: Proceedings of the 31stannual international ACM SIGIR conference on Researchand development in information retrieval. pp. 299306. ACM(2008)
Erkan, G., Radev, D.R.: Lexrank: Graph-based lexical centrality as salience in text summarization. Journal of artificial
intelligence research 22, 457479 (2004)
Jatowt, A., Au Yeung, C.M., Tanaka, K.: Estimating document fo- cus time. In: Proceedings of the 22Nd ACM International Conference on Information Knowledge Management. pp. 22732278. CIKM !G
13, ACM, New York, NY, USA(2013).

[22] Chang, A.X., Manning, C.D.: Sutime: A library for recognizing and normalizing time expressions. In: Lrec. vol. 2012,
pp. 37353740 (2012)[23] eh urek, R., Sojka, P.: Software Framework for Topic
Modelling with Large Corpora. In: Proceedings of the
LREC 2010 Workshop on New Chal- lenges for NLP
Frameworks. pp. 4550. ELRA, Valletta, Malta (May 2010),
http://is.muni.cz/publication/884893/en[24] Mikolov, T., Chen, K., Corrado, G., Dean, J.: Efficient estimation of word repre- sentations in vector space. arXiv
preprint arXiv:1301.3781 (2013)[25] Bamman, D., Smith, N.A.: Unsupervised discovery of biographical structure from text. Transactions of the Association for Computational Linguistics 2, 363376 (2014)[26] Alsudais, A., Tchalian, H.: Corpus periodization framework
to periodize a tempo- rally ordered text corpus (2016)