\documentclass[english]{jnlp_3.6}
\usepackage{jnlpbbl_2.2}
\usepackage[dvipdfmx]{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{url}
\usepackage{hangcaption_jnlp}
%%%%\usepackage{udline}
%%%%\setulminsep{1.2ex}{0.2ex}
%%%%\let\underline=\ul
\allowdisplaybreaks


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% author's definition
\usepackage{paralist}
\usepackage{booktabs}
%%%%\usepackage{graphicx}
%%%%\usepackage{makecell}
%%%%\usepackage{amssymb}
%%%%\usepackage{verbatim}
%%%%\usepackage{color}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\Volume{30}
\Number{1}
\Month{March}
\Year{2023}
%%%%\Issuetitle{Special Issue: XXXXXXXX}

\received{2022}{7}{27}
\revised{2022}{11}{21}
\accepted{2022}{12}{21}

\setcounter{page}{184}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\esubject{General Paper}
\etitle{Joint Learning-based Heterogeneous Graph Attention Network for Timeline Summarization}
\eauthor{Jingyi You\affiref{Author_1} \and Dongyuan Li\affiref{Author_1} \and Hidetaka Kamigaito\affiref{Author_2} \and \\ Kotaro Funakoshi\affiref{Author_1} \and Manabu Okumura\affiref{Author_1}}
\eabstract{
Timeline summarization (TLS) is defined as a task for summarizing events in chronological order, which gives readers a comprehensive understanding of an evolutionary story. Previous studies on the timeline summarization (TLS) task ignored the information interaction between sentences and dates, and adopted pre-defined unlearnable representations for them, which significantly degrade the performance. They also considered date selection and event detection as two independent tasks, which makes it impossible to integrate their advantages and obtain a globally optimal summary. In this paper, we present a \textit{joint learning-based heterogeneous graph attention network for TLS} (Heter\textsc{Tls}), in which date selection and event detection are combined into a unified framework to improve the extraction accuracy and remove redundant sentences simultaneously. Our heterogeneous graph involves multiple types of nodes, the representations of which are iteratively learned across the heterogeneous graph attention layer. We evaluated our model on four datasets, and found that it significantly outperformed the current state-of-the-art baselines with regard to ROUGE scores and date selection metrics.
}
\ekeywords{Timeline Summarization, Heterogeneous Graph Network, Sentence Clustering}

\headauthor{You et al.}
\headtitle{Joint Heterogeneous Graph Attention Network for Timeline Summarization}

\affilabel{Author_1}{}{Tokyo Institute of Technology}
\affilabel{Author_2}{}{Nara Institute of Science and Technology}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\label{sec:intro}

Timeline summarization (TLS) is designed to extract sentences that describe an evolutionary story from a massive amount of web articles with respect to a specific topic in chronological order.
TLS has drawn much attention in recent years \cite{martschat2018temporally,chen2019learning,ghalandari2020examining,born2020dataset,yu2021multitimeline,pasquali2021tlscovid19} since it releases people from burdensome manual creation of summaries and gives readers a faster but comprehensive access to track events from many aspects, such as start and end, causality, and the main protagonists involved. 

Most studies on TLS seek ways to combine two individual subtasks: date selection and event detection. 
Depending on different strategies for them, current methods are generally divided into three categories \cite{ghalandari2020examining}:
\begin{inparaenum}[1)]
    \item {\em direct summarization} approaches \cite{chieu2004query,tran2013predicting,martschat2018temporally,duan2020comparative} directly identify topic-related sentences from a collection of news articles to form a timeline;
    \item {\em date-wise summarization} methods \cite{wang2016low,chen2019learning,ghalandari2020examining,li2021automated,quatra2021summarize} first select salient dates then construct a timeline for each date individually with sentences of the highest score; and
    \item {\em event detection} algorithms \cite{steen2019abstractive,duan2020comparative,ghalandari2020examining,yu2021multitimeline} detect events by clustering sentences from multi-timeline news articles then identify several of the most important events and summarize them separately.
\end{inparaenum}

Although great successes have been achieved in conducting TLS, several issues remain unsolved.
First, current TLS methods mainly adopt statistical hand-designed features to represent dates, e.g., the number of published articles and topic-related sentences in a specific time duration \cite{ghalandari2020examining,yu2021multitimeline}, and employ sentence-BERT \cite{reimers2019sentence} and other pre-defined unchangeable representations for sentences. 
The low-level or unlearnable representations tend to ignore the semantic and temporal information interaction between sentences and dates, which significantly degrades the performance of downstream date selection and event detection tasks.
Secondly, traditional approaches focus on either date selection or event detection.
Although excellent date selection algorithms can pinpoint accurate timeline dates, they usually extract topic-irrelevant sentences as a summary.
While event detection algorithms are capable of avoiding redundant summaries by various clustering strategies, they sometimes capture wrong timeline dates.
To the best of our knowledge, there is no framework that jointly learns the advantages of the above two subtasks to accurately capture salient dates and eliminate topic-irrelevant sentences in a timeline.

To circumvent the above dilemma, we propose to jointly learn date/sentence representations and event detection-based sentence clustering in a heterogeneous graph attention network (HAN) for TLS.
Specifically, we construct a heterogeneous graph with dates, words, and sentences as semantic units to solve the first problem.
In this graph, words act as a bridge between dates and sentences, enabling date nodes to learn different granularities (word- and sentence-level) of semantic information and sentence representations to be complemented with a date-related intra- and cross-sentence message.
As for the second issue, semi-supervised date prediction and event detection-based clustering are integrated into an overall objective, where labeled dates guide and facilitate sentence clustering, and sentence-level clustering information indicating main events improves the accuracy of unlabeled date prediction.
Note that we create a new way beyond the above-mentioned three categories as a \textit{joint end-to-end} approach since we no longer have to handle each subtask step by step.

The contributions of this paper are highlighted as follows:
\begin{itemize}
    \item This study is the first to construct a model for automatic TLS as a HAN that propagates heterogeneous information with different granularities, of {\em date-word-sentence}, to effectively learn flexible and accurate representations for both date and sentence nodes.
    \item Date selection and event detection subtasks are incorporated into an overall objective so that they can be jointly optimized to obtain a globally optimal solution.
    \item We have empirically shown that Heter\textsc{Tls} outperformed all existing competitors on four benchmark datasets. Its effectiveness and robustness were further confirmed via ablation studies and parameter analysis.
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Related Work}
\label{sec:related}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Timeline summarization}
\label{subsec:timeline}

Unlike multi-document summarization (MDS), TLS executes both date selection and summary extraction \cite{zhou2021entity}.
In accordance with different strategies for defining the above two subtasks, available approaches are categorized into three classes, whose major methods are reviewed as follows.

{\em Direct summarization} approaches \cite{allan2001temporal,yan2011timeline,li2013evolutionary,zhao2013timeline,suzuki2014online} treat the task as MDS with time-stamped textual summaries that directly extract topic-related sentences from massive news documents.
\citeA{chieu2004query} rank and extract sentences relevant to a query from a collection of documents and place them along a timeline.
\citeA{yan2011evolutionary} formulate the task as an optimization problem and detect the evolution trajectory via iteratively substituting a subset of sentences for the time-stamped document collection.
\citeA{zhao2013timeline} incorporate users' collective interests in the directly generation of timeline summaries.
As the current state-of-the-art method for direct summarization, revised submodular-function optimization, which is commonly used for MDS, is applied to search for a combination of sentences from an entire document collection to construct a timeline \cite{martschat2018temporally}.

{\em Date-wise summarization} methods \cite{li2021automated} first select dates then extract sentences corresponding to the dates.
\citeA{tran2013predicting,tran2015joint} propose a supervised graphical model for selecting salient dates and tracking events on each date.
In another study, important dates are first selected and then text and image embeddings are jointly learned using a scalable low-rank approximation approach to generate a more readable timeline summary \cite{wang2016low}.

{\em Event detection} algorithms \cite{tran2015balancing,pasquali2019interactive,duan2020comparative} usually cluster news documents to detect events and summarize them individually.
For instance, affinity propagation is adopted to detect major events along a timeline, and a summary for each event is abstractively generated \cite{steen2019abstractive}.
Moreover, \cite{yu2021multitimeline} implement multiple timeline summarization based on affinity propagation to discover and summarize multi-events, and finally generate summaries for important stories.
\citeA{tran2015balancing} first adopt entities to detect high-impact events, while \citeA{pasquali2019interactive} present a tool to detect events by key-phrase extraction algorithms and select relevant temporal periods to each important events.
As far as we know, the idea of learning changeable and interactive representations between sentences and time steps has not been formally proposed yet.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Heterogeneous graph for summarization}

A heterogeneous graph contains different types of nodes and multiple relationships between nodes \cite{xu2020documentlevel,hu2021toward}.
\citeA{wang2020heterogeneous} present a HAN for single or multiple document extractive summarization to enrich cross-sentence relations through additional semantic units.
A latent-topic detection model is integrated into a HAN to provide the graph with document-level features for extractive summarization \cite{cui2020enhancing}.
In another study, \citeA{jia2020neural} leverage a sentence-level redundancy layer into a HAN to remove excessive phrases between extracted sentences.
Although much research has gone into constructing source documents as heterogeneous graphs and using graph attention network-based first-order neighbors during information dissemination, longer-distance heterogeneous paths have not been considered.
Inspired by \citeA{wang2019heterogeneous}, we extended a HAN to the TLS task and developed Heter\textsc{Tls} to learn better node representations for downstream tasks.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Methodology}
\label{sec:method}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Problem definition and preliminaries}
\label{subsec:problem}


Given a collection of news documents $\mathcal{D}$ within $\mathcal{T}$ dates, TLS is to construct a timeline that summarizes the most important events associated with a specific topic.
It mainly consists of two subtasks: date selection and sentence extraction.
Specifically, the former is formulated as predicting a sequence of date labels $\{y_{1},\cdots,y_{\mathcal{T}}|y_{i}\in\{0,1\}\}$, where $y_{i}=1$ represents the $i$-th date is included in the timeline.
We assume the latter one as ranking and extracting sentences from candidates for each selected date.
The number of dates as well as the length of the daily summaries are typically controlled by the user.

Given a graph $\mathcal{G}=\{\mathcal{V},\mathcal{E}\}$ with $\mathcal{V}=V_{d} \cup V_{w} \cup V_{s}$ and $\mathcal{E}=E_{w-d} \cup E_{w-s}$, where $V_{d}$, $V_{w}$, and $V_{s}$ respectively denote a node set for dates, words, and sentences and $E_{w-d}$ and $E_{w-s}$ are a set of undirected edges between word-date and word-sentence.
Specifically, $V_{d}=\{d_{1},\cdots,d_{\mathcal{T}}\}$, $V_{w}=\{w_{1},\cdots,w_{m}\}$, and $V_{s}=\{s_{1},\cdots,s_{n}\}$ correspond to $\mathcal{T}$ dates, $m$ unique words, and $n$ sentences within $\mathcal{D}$.
Inequality $e_{ij} \neq 0$ $(i \in \{1,\cdots,m\},j \in \{1,\cdots,n\})$ of $E_{w-s}$ indicates that the $i$-th word appears in the $j$-th sentence.
$E_{w-d}$ is a real-valued edge weight matrix, where $e_{ij} \neq 0 \: (i \in \{1,\cdots,m\},j \in \{1,\cdots,\mathcal{T}\})$ signifies the $i$-th word appears in the articles published on the $j$-th date.
As Figure~\ref{constructor} shows, sentences and dates are connected with words they contain, and no edge exists between nodes of the same type, e.g., word pairs.
We then define a meta-path and meta-path-based neighbors for the purpose of disseminating information among heterogeneous nodes.

\textit{\textbf{Definition 1}\,\,\,\,} Meta-path $\Phi$ is defined as a path in the form of $v_{1} \stackrel{e_{1}}{\longrightarrow} \cdots \stackrel{e_{q}}{\longrightarrow}v_{q+1}$, which describes a composite edge relation $e = e_{1} \circ \cdots \circ e_{q}$ between nodes $v_{1}$ and $v_{q+1}$, where $\circ$ denotes the composition of relations.

\textit{\textbf{Definition 2}\,\,\,\,} Meta-path-based neighbors $\mathcal{N}_{i}^{\Phi}$ of the $i$-th node are defined as all nodes in a single meta-path $\Phi$. 

Figure~\ref{overview} exhibits an overview of Heter\textsc{Tls}, which consists of three main components: (a) {\em graph constructor and initializer}, (b) {\em heterogeneous graph encoder with sentence clustering constraint}, and (c) {\em timeline summary extractor}.
Each component is introduced subsequently in detail in the following subsections.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 1
\begin{figure}[t]
\begin{center}
\includegraphics{30-1ia7f1.pdf}
\end{center}
\hangcaption{Model overview. Heter\textsc{Tls} consists of three chief components: (a) graph constructor and initializer, (b) heterogeneous graph encoder with sentence clustering constraint, and (c) timeline summary extractor. We first construct heterogeneous network for date, sentence, and word nodes with two initialization strategies. We then extract meta-paths and iteratively update node representations via HAN under nuclear norm constraint on sentence nodes. Finally, we predict unlabeled date nodes and extract sentences from candidate clusters.}
\label{overview}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Graph constructor and initializer}
\label{subsec:initializer}


Let $\textbf{X}_{d} \in \mathbb{R}^{\mathcal{T} \times r_{d}}$, $\textbf{X}_{w} \in \mathbb{R}^{m \times r_{w}}$, and $\textbf{X}_{s} \in \mathbb{R}^{n \times r_{s}}$ respectively denote input feature matrices for date, word, and sentence nodes, where $r_{d}$, $r_{w}$, and $r_{s}$ are dimensions of date representations, word embeddings, and sentence representations.
Especially, we initialize the $j$-th sentence node in Figure~\ref{constructor} by concatenating its local n-gram feature $p_{j}$ and sentence-level global feature $q_{j}$ as $X_{s_{j}}=[p_{j};q_{j}]$.
Feature $p_{j}$ is captured by a convolutional neural network (CNN) \cite{lecun1998gradient} with different kernel sizes, and $q_{j}$ is gripped by a bidirectional long short-term memory (Bi-LSTM) \cite{hochreiter1997long}.
Considering the success of transformer-based pre-trained models, we also provide another initialization strategy: using BERT \cite{devlin2019bert} and sentence-BERT \cite{reimers2019sentence} as word and sentence encoders.
Date nodes take the average-pooling of their connected sentences as initialization for both aforementioned strategies.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 2
\begin{figure}[t]
\begin{center}
\includegraphics{30-1ia7f2.pdf}
\end{center}
\hangcaption{(a) Graph constructor and initializer. We construct a heterogeneous network for date, sentence, and word nodes with two initialization strategies.}
\label{constructor}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

To leverage the saliency of relationships between heterogeneous nodes, we propose term frequency-inverse sentence frequency (TF-ISF) and term frequency-inverse date frequency (TF-I\textsc{Date}F) weights to initialize edges in $E_{w-s}$ and $E_{d-w}$, which can distinguish the importance of each word in different sentences or dates.
Specifically, TF is the number of occurrences of $w_{i}$ in $s_{j}$ or $d_{t}$, and ISF/I\textsc{Date}F is determined by dividing the total number of sentences or dates in $\mathcal{D}$ by the number of sentences or dates containing $w_{i}$, which can be calculated as
\begin{align}
    \label{tf} \mathit{TF}_{i,j}&=\frac{n_{i,j}}{\sum\nolimits_{k}n_{k,j}},\\
    \label{isf} \mathit{ISF}_i&=\log\frac{|S|}{|\{j:w_i \in s_j\}|},\\
    \label{idf} \mathit{I\textsc{Date}F}_i&=\log\frac{|D|}{|\{j:w_i \in d_j\}|},
\end{align}
where $n_{i,j}$ indicates the number of occurrences of word $w_{i}$ in sentence $s_{j}$ (for edges in $E_{w-s}$) or date $d_{j}$ (for edges in $E_{d-w}$), and the denominator of Equation~\ref{tf} is the sum of the number of occurrences of all words in $s_{j}$ or $d_{j}$.
In Equations~\ref{isf} and \ref{idf}, $|S|$ and $|D|$ respectively denote the total number of sentences and dates in the corpus, and $|\{j:w_i \in s_j\}|$ and $|\{j:w_i \in d_j\}|$ are the numbers of sentences or dates where term $w_{i}$ appears.

Intuitively, some words, e.g., articles such as {\em ``the''} and {\em ``a''}, appear in many sentences and dates, while other words, e.g., {\em ``Harry Potter''}, are not so frequent.
Therefore, words with lower ISF/I\textsc{Date}F values are less important and usually have no specific meaning, so that they can be omitted without confusing the main idea.
Conversely, words with higher ISF/I\textsc{Date}F values might be important and indicate salient information or the topic of the article.
This assumption allows Heter\textsc{Tls} to distinguish key points from non-key points.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Heterogeneous graph encoder with sentence clustering constraint}
\label{subsec:heterogeneous}

As Figure~\ref{encoder} illustrates, we first iteratively update node representations via meta-paths in hierarchical heterogeneous graph attention layers. 
We then introduce how we constrain sentence representations to reserve a low-rank-based clustering structure, which helps sentence nodes learn better event-related information.
Finally, the semi-supervised date classification and sentence clustering structure are jointly learned in an overall objective.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 3
\begin{figure}[t]
\begin{center}
\includegraphics{30-1ia7f3.pdf}
\end{center}
\hangcaption{(b) Heterogeneous graph encoder with sentence clustering constraint. We extract meta-paths and iteratively update node representations via HAN under nuclear norm constraint on sentence nodes.}
\label{encoder}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Heterogeneous graph attention layer}

Node representations are updated by hierarchical structured-heterogeneous graph attention layers, where the node-level attention layer ensures information propagation and aggregation in a single meta-path, while the semantic-level one is committed to merging messages from multiple meta-paths.
Specifically, referring to $\textbf{h}_{i}$ as the hidden state of the $i$-th node, the node-level attention layer is calculated as
\begin{align}
    e_{ij}^{\Phi}&=LeakyReLU(\textbf{W}_{a}[\textbf{W}_{\phi_{i}}\textbf{h}_{i};\textbf{W}_{\phi_{j}}\textbf{h}_{j}]),\\
    \alpha_{ij}^{\Phi}&=\frac{exp(e_{ij}^{\Phi})}{\sum_{l\in \mathcal{N}_{i}^{\Phi}}exp(e_{il}^{\Phi})},\\
    \textbf{z}_{i}^{\Phi}&=\sigma (\sum_{j \in \mathcal{N}_{i}^{\Phi}} \alpha_{ij}^{\Phi}\textbf{W}_{\phi_{j}}\textbf{h}_{j}),
\end{align}
where $\textbf{W}_{a}$, $\textbf{W}_{\phi_{i}}$, and $\textbf{W}_{\phi_{j}}$ are trainable parameters, $\textbf{z}_{i}^{\Phi}$ is the representation of the $i$-th node learned from the node-level attention layer by $\Phi$, $\alpha_{ij}^{\Phi}$ measures the importance of the $j$-th node to the $i$-th node via $\Phi$, $\mathcal{N}_{i}^{\Phi}$ contains all nodes in single meta-path $\Phi$. 
With $K$ denotes the number of multi-heads, we also apply the multi-headed attention as
\begin{equation}
\textbf{z}_{i}^{\Phi}=\mathop{\Vert}\limits_{k=1}^{K} \sigma (\sum_{j \in \mathcal{N}_{i}^{\Phi}} \alpha_{ij}^{\Phi,k}\textbf{W}_{\phi_{j}}^{k}\textbf{h}_{j}).
\end{equation}

Afterwards, the semantic-level attention layer fuses all the meta-paths information for the $i$-th node. 
We extract meta-paths $\hat{\Phi}_{d_{1 \sim 3}}$=\{date-word, date-word-date, date-word-sent\} for date nodes, $\hat{\Phi}_{w_{1 \sim 2}}$=\{word-sent, word-date\} for word nodes, and $\hat{\Phi}_{s_{1 \sim 3}}$=\{sent-word, sent-word-sent, sent-word-date\} for sentence nodes (Figure~\ref{encoder}), while long-distance meta-paths are discarded due to their very limited impact on our model.
With the assumption that the $i$-th node has $P$ meta-paths as $\{\Phi_{1},\cdots,\Phi_{P}\}$, the representation of the $i$-th node is updated as
\begin{align}
    w_{\Phi_{p}}&=\frac{1}{|\mathcal{V}|}\sum_{i \in \mathcal{V}} \textbf{q}^{T}tanh(\textbf{W} \textbf{z}_{i}^{\Phi_{p}}+\textbf{b}),\\
    \beta_{\Phi_{p}}&=\frac{exp(w_{\Phi_{p}})}{\sum_{l=1}^{P} exp(w_{\Phi_{l}})},\\
    \textbf{z}_{i}&=\sum\limits_{p=1}^{P} \beta_{\Phi_{p}} \textbf{z}_{i}^{\Phi_{p}},
\end{align}
where $\textbf{q}$, $\textbf{W}$, and $\textbf{b}$ are learnable parameters and $\beta_{\Phi_{p}}$ represents the importance of the $p$-th meta-path for the final embedding of the $i$-th node.

In the same manner described by \citeA{wang2020heterogeneous}, to avoid gradient vanishing after certain iterations, a residual connection and position-wise feed-forward network (FFN) layer with two linear transformations \cite{vaswani2017attention} are added after the semantic-level attention layer.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Iterative update:} 
We alternately update each type of node to realize information propagation and aggregation in our heterogeneous graph to transmit messages.
The updating process for the $t$-th iteration is measured as
\begin{align}
\label{eq7} Z_{w_{1\sim 2}}^{t+1}&=NLevel(H_{d}^{t},H_{s}^{t},H_{w}^{t}),\\ 
\label{eq8} H_{w}^{t+1}&=FFN(SLevel(Z_{w_{1 \sim 2}}^{t+1})+H_{w}^{t}),\\
\label{eq9} Z_{d_{1\sim 3}}^{t+1}&=NLevel(H_{d}^{t},H_{s}^{t},H_{w}^{t+1}),\\ 
\label{eq10} H_{d}^{t+1}&=FFN(SLevel(Z_{d_{1 \sim 3}}^{t+1})+H_{d}^{t}),\\
\label{eq11} Z_{s_{1\sim3}}^{t+1}&=NLevel(H_{d}^{t+1},H_{s}^{t},H_{w}^{t+1}),\\ 
\label{eq12} H_{s}^{t+1}&=FFN(SLevel(Z_{s_{1 \sim 3}}^{t+1})+H_{s}^{t}),
\end{align}
where $NLevel$ and $SLevel$ respectively indicate node-level and semantic-level attention layers, while $Z^t$ and $H^{t}$ are the interim node representation and the stacked hidden state of a certain type of node at the $t$-th timestep.
Equations \ref{eq8}, \ref{eq10}, and \ref{eq12} represent the residual connection and FFN layer.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Sentence clustering constraint}

Detecting main events from $\mathcal{D}$ can effectively reduce the redundancy when generating summaries.
Current TLS methods \cite{yu2021multitimeline} identify major events by applying K-means directly to sentence representation matrix $H_{s}$, which has two limitations.
First, K-means is sensitive to initialization and outliers, resulting in unstable outputs \cite{ding2007adaptive}.
Furthermore, traditional hard clustering methods cannot be trained and incorporated into the proposed model since they adopt unsupervised learning.
Therefore, the clustering performance is undesirable due to the independence of sentence representation learning and sentence clustering.
In our Heter\textsc{Tls}, these two sub-tasks are jointly learned to combine their advantages into a uniform framework.
However, traditional hard clustering methods cannot be trained and incorporated into the proposed model since they adopt unsupervised learning.
\citeA{nie2017learning} paves the way to realize our joint learning model by transforming the clustering task into a nuclear norm-based regularization, which constrains the sentence representations to have a low-rank diagonal clustering structure as shown in Figure \ref{extractor}.
To introduce the theoretical basis behind the clustering structure learning of $H_{s}$, the following theorem is first introduced:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 4
\begin{figure}[b]
\begin{center}
\includegraphics{30-1ia7f4.pdf}
\end{center}
\hangcaption{(c) Timeline summary extractor. We predict unlabeled date nodes and extract sentences from candidate clusters in the end.}
\label{extractor}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\textit{\textbf{Theorem 1}\,\,\,\,} \cite{chung1997spectral} The multiplicity of eigenvalue $0$ of the normalized Laplacian matrix of $H_{s}$ is equal to the number of clusters in $H_{s}$.

Theorem 1 implies that the block-diagonal clustering structure learning can be converted into a matrix rank problem, i.e., calculating a nuclear norm \cite{haeffele2020structured}, which is formulated as
\begin{equation}
    \mathcal{L}_{\mathit{cluster}}=\|H_{s}\|_{*},
\end{equation}
where $\|H_{s}\|_{*}$ is defined as the sum of the $k$ smallest eigenvalues, i.e., $\sum_{i=n-k}^{n}\sigma_{i}(H_{s})$ with $\sigma_{i}(H_{s})$ as the $i$-th smallest eigenvalue \cite{piao2019double}.
When $\|H_{s}\|_{*}$ is set to $0$, $k$-connected clusters in $H_{s}$ can be obtained by reorganizing its columns or rows and converting it into a block-diagonal form with $k$ blocks (as shown in Figure~\ref{extractor}).
We also determine parameter $k$ by the elbow method \cite{bholowalia2014ebk}.
Sentences with clustering structure help us capture event-related summaries and remove redundancy in the final timeline.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Joint learning framework}

Past work considered date selection and sentence clustering-based event detection as independent tasks. 
In Heter\textsc{Tls}, they are jointly trained to combine their advantages into an overall objective: 
\begin{equation}\label{overall_loss}
    \mathcal{L}=\mathcal{L}_{\mathit{classify}}+\lambda \mathcal{L}_{\mathit{cluster}},
\end{equation}
where $\mathcal{L}_{\mathit{classify}}$ minimizes the cross-entropy over all labeled date nodes between the ground-truth during training, and $\lambda$ serves as a weighted coefficient to balance $\mathcal{L}_{\mathit{classify}}$ with $\mathcal{L}_{\mathit{cluster}}$.
Equation~\ref{overall_loss} can be optimized via stochastic gradient descent (SGD) \cite{zinkevich2010parallelized} in an end-to-end manner.

Our date classification is trained in a transductive learning-based semi-supervised manner.
We iterate all node representations in the heterogeneous graph simultaneously with $50\%$ labeled date nodes ($40\%$ for training and $10\%$ for verification) and $50\%$ unlabeled date nodes as the test set.
The joint learning model is able to effectively find event-based candidate clusters (see Figure~\ref{extractor}), thereby save much running time and improve the accuracy of TLS.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Timeline summary extractor}
\label{subsec:extractor}

With $l$ selected dates and their corresponding representations $\{\textbf{h}_{d_{1}},\cdots,\textbf{h}_{d_{l}}\}$, we represent the $k$ clusters as $\{\textbf{h}_{c_{1}},\cdots,\textbf{h}_{c_{k}}\}$ by averaging sentence representations inside that cluster.
As shown in Figure~\ref{extractor}, candidate clusters for the $t$-th selected date are determined by calculating the cosine similarity between the date representation with all cluster representations as $cos(\textbf{h}_{d_{t}},\textbf{h}_{c_{j}}) (j\in \{1,\cdots, k\}$).
If the cosine similarity is larger than the pre-defined threshold $\delta$ (see Section~\ref{subsec:parameters}), the corresponding cluster is considered as a candidate for the date.
Finally, we apply CENTROID-OPT \cite{gholipour2017revisiting} as a sentence ranking algorithm within a cluster and summarize each date individually by selecting one sentence per cluster with the highest ranking score.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Experiments}\label{sec:experiments}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Datasets}\label{subsec:datasets}

We carried out our experiments on the four most widely used benchmark datasets, i.e., 17 Timelines (T17) \cite{tran2013predicting}, Crisis \cite{tran2015timeline}, Entities \cite{ghalandari2020examining}, and CovidTLS \cite{quatra2021summarize}.
All contain human-written timelines concerning certain topics, the source news articles of which are retrieved from the web at a given point in time.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{T17}
The 17 Timelines (T17) dataset \cite{tran2013predicting} is the first publicly-accessed and the most widely-used benchmark dataset for TLS.
17 different timeline summaries from 9 different famous topics (e.g. ``BP Oil Spill'', ``Influenza H1N1'' and ``Arab Spring''), were collected from popular news agencies such as CNN, BBC, NBCnews, etc.
Only those timelines with explicit timestamps (including day, month, and year) were considered.
For each source articles and timeline summary pairs, the topic served as a query and time filter option to retrieve and retain top 400 news articles from the news agency that published during a specific time span.
At the end, by using duplication removal, a total number of 4,650 news articles were reserved in the collection.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Crisis}
Crisis\footnote{\url{https://drive.google.com/drive/folders/1gDAF5QZyCWnF_hYKbxIzOyjT6MSkbQXu}} collects event data related to long-term armed conflicts happened in North Africa, including stories about Egypt Revolution, Syria War, Yemen Crisis and Libya War.
25 timeline summaries acted as ground-truth, which were manually created by professional journalists and collected from the most popular news agencies, including the BBC, CNN, and Reuters.
The corresponding source articles were retrieved from Google by simulating users searching for articles relevant to the timelines of the aforementioned new stories.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Entities}
Entities\footnote{\url{https://github.com/complementizer/news-tls}} contains timeline data for entities rather than events.
Specifically, it consists of 47 different timelines ranging over an equal number of topics and decades of time duration.
Most of the covered topics are related to life-spanning events of famous people, while the remaining ones are related to business companies and no-profit organizations.
The ground-truth timelines were first obtained from CNN Fast Facts, where several hundred timelines are grouped in categories, e.g., ``people'' or ``disasters''.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{CovidTLS}
The newly released CovidTLS dataset\footnote{\url{https://github.com/MorenoLaQuatra/SDF-TLS}} describes the outbreak and evolution of the Covid-19 pandemic since the beginning of 2020.
As it is undoubtedly one of the most concerned worldwide events and affects all aspects of people's lives and work, it has been reported by an unprecedented amount and variety of news articles.
The whole corpus was crawled from well-known English-written journals, while it is annotated with a ground-truth timeline retrieved from a public, authoritative website.
With peculiar characteristics, the whole dataset has just one, complex topic (i.e., the outbreak Covid-19 pandemic) reported by over 26 thousands news articles.
The number of candidate dates in CovidTLS is one order of magnitude higher than those of all the existing topics.

Using these datasets makes it possible to comprehensively verify the effectiveness and generalization of Heter\textsc{Tls} because both the number of topics and their time spans are completely different.
Specifically, the Entities dataset contains dozens of topics and spans decades of news articles per topic, while the others involve only a few topics within two years.
The basic statistics are summarized in Table~\ref{dataset_statistics}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 1
\begin{table}[t]
\input{07table01.tex}
\end{center}
\hangcaption{Basic dataset statistics. Avg. X demonstrates average X for each topic, and Timelines refers to number of ground-truths in each dataset.}
\label{dataset_statistics}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Evaluation metrics}
\label{subsec:metrics}

Following \citeA{yu2021multitimeline}, the quality of model-generated timelines obtained in the experiments were evaluated on the basis of the ROUGE metric and its widely-used variants as follows:


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Concatenation-based ROUGE F1} Similar to conventional ROUGE, it compares a concatenated system summary with its corresponding ground-truth by referring only to the textual overlap while ignoring all time stamps of the timeline \cite{yan2011evolutionary,nguyen2014ranking,wang2016low}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Alignment-based ROUGE F1} On the basis of the above concatenation metric, it linearly penalizes the ROUGE score by the distance of date alignments to texts \cite{Martschat2017improving}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Date selection F1} It only measures how well the model selects dates contained in the ground-truth \cite{martschat2018temporally}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Experimental settings}
\label{subsec:settings}

Since each topic has at least one ground-truth timeline, we considered each timeline independently if multiple ground-truths exist, and the final evaluation results were obtained by averaging scores over all timelines. 
We split training/verification/test sets in accordance with the percentages of 40\%/10\%/50\% mentioned to Section~\ref{subsec:ratio}.
Moreover, all experiments for a dataset were subject to leave-one-out cross-validation, and significant differences were determined by bootstrap test \cite{dror2018hitchhiker} with $p$-value of 0.005.

For our heterogeneous network, the vocabulary size was limited to $50,000$ and tokens were initialized with $400$-dimensional GloVe embeddings \cite{pennington2014glove}.
We truncated an input document to a maximum length of $40$ sentences and removed $10\%$ of vocabulary with the lowest TF-I\textsc{Date}F values to eliminate noise.
Date/sentence nodes and edge features individually included $r_{d}=r_{s}=128$ and $40$-dimensional vectors for initialization. 
We set the learning rate and regularization hyper parameter $\lambda$ to $5e-4$ and $1.5$, respectively.
Each HAN layer had $8$ heads and $64$-dimensional hidden size.
The inner hidden size of the FFN layer was set to $512$.
The number of iterations and the maximum number of epochs were set to $3$ and $15$ respectively.
An early stop was carried out when the validation loss did not descend for three continuous epochs.
We trained all baselines as well as Heter\textsc{Tls} on a single Titan RTX GPU.

Since it is a difficult problem to correctly extract the chronological order of events from time stamped-free texts, we therefore attempt to only attach dates to the sentences extracted from news articles.
We assume that the first date expression detected in a sentence $s$ is the date of the event mentioned in $s$.
We further craft simple rules to detect date expressions in sentences and resolve them to absolute dates using the date of the article as a reference.
For example, with ``today'' parsed as the publication date of the article, ``September'' and ``Sunday'' indicate the last September and Sunday before the article date.
In the case that no date expression is detected in the entire sentences $s$, $date(s)$ is taken to be the publication date of the article containing $s$.
Although this assumption is frequently incorrect in document types such as biographies, literary writings, or historical texts, we find it is reasonable for news articles.
News, by definition, reports up-to-date events.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Baselines}
\label{subsec:baselines}

The following excellent baselines were used for comparison and to demonstrate the effectiveness of Heter\textsc{Tls}:
\textit{direct summarization} including CHIEU \cite{chieu2004query} and MARTSCHAT \cite{martschat2018temporally}; \textit{date-wise summarization} such as TRAN \cite{tran2013predicting}, DATEWISE \cite{ghalandari2020examining}, and SDF \cite{quatra2021summarize}; and \textit{event detection} method DASG \cite{liu2021unsupervised}.
We additionally follow \citeA{ghalandari2020examining} to obtain full oracle by first selecting the correct dates and then constructing a summary for each date by optimizing the ROUGE to the ground-truth summaries.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 2
\begin{table}[b]
\input{07table02.tex}
\hangcaption{Concatenation- and alignment-based ROUGE-1/2 F1-scores for T17 and Crisis datasets. Best results among model-generated timelines are marked in bold. Symbol \dag\, indicates that our results significantly surpass all baselines using bootstrap test with $p<0.005$.} 
\label{rouge1}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 3
\begin{table}[t]
\input{07table03.tex}
\hangcaption{Concatenation- and alignment-based ROUGE-1/2 F1-scores for Entities and CovidTLS datasets. Best results among model-generated timelines are marked in bold. Symbol \dag\, indicates that our results significantly surpass all baselines using bootstrap test with $p<0.005$.} 
\label{rouge2}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 4
\begin{table}[t]
\input{07table04.tex}
\hangcaption{Date F1-scores on T17, Crisis, Entities, and CovidTLS datasets. Bold-faced characters and \dag\, indicate best results and significant improvements over all baselines.} 
\label{date_f1}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Results and Discussion}\label{sec:results}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Performance of Heter\textsc{Tls}}
\label{subsec:performance}

According to Tables \ref{rouge1}, \ref{rouge2}, and \ref{date_f1}, Heter\textsc{Tls} outperformed all baselines in terms of all metrics, achieving state-of-the-art performance.
Considering that DASG ignores date information, we excluded it from the Date F1 experiment.
We noticed that Heter\textsc{Tls} with pre-trained initial node representations surpassed Heter\textsc{Tls} only on Crisis and CovidTLS datasets.
This indicates that BERT and sentence-BERT models require larger downstream datasets (Crisis or CovidTLS datasets) to escape from the local optimum through massive iteration processes, while CNN- and Bi-LSTM-based initialization can better capture the characteristics of small-scale datasets (T17 and Entities datasets) and reach the globally optimal solution in a few epochs.
We are convinced that the lightweight Heter\textsc{Tls} is more effective for small-scale datasets while Heter\textsc{Tls} initialized using pre-trained language models attains better results on large-scale datasets.

We consider three possible reasons for the excellent performance of Heter\textsc{Tls}.
First, the HAN is configured to learn word-level/sentence-level semantic features for date representations.
Compared with hand-designed statistical low-level features, these features are much more distinguishable, so they improve the accuracy of date selection.
Second, regarding the improvement of ROUGE scores, the introduction of low-rank-based regularization helps sentence representations learn a diagonal clustering structure, which enables Heter\textsc{Tls} to effectively capture the topic-related events and informative sentences, so as to remove the redundant information from extracted sentences.
Third, building connections between dates and sentences through the bridge of words can help both select salient dates and prepare for candidate sentences dynamically.
Especially, date selection and sentence clustering-based event detection are jointly learned and optimized to obtain a globally optimal solution.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Ablation study}
\label{subsec:ablation}

We investigated the contribution of each module to Heter\textsc{Tls} via ablation studies using each dataset. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Heter\textsc{Tls}-HAN}
To verify the interaction within heterogeneous connections, we show the ablation performance in Table~\ref{rouge1}, \ref{rouge2}, and \ref{date_f1} by removing the iterative updating strategy with HAN and simply using unlearnable semantic features with nuclear norm constraint.
We suspect that the HAN layer plays a critical role in facilitating date selection with semantic messages and providing sentence nodes with temporal clustering information, which cannot be replaced with fixed features.
Meta-paths also provide abundant iterative patterns to pass semantic and temporal information, so that nodes can communicate with others from more aspects. 
Specifically, node-level meta-path-based iterative updating provides sentence clustering with date labels, and cross- and intra-sentence relations.

However, sentence nodes initialized by CNN and Bi-LSTM layers help capture local and global sentence relationships, which has been proved predominant with regard to the extractive summarization task \cite{wang2020heterogeneous}.
Furthermore, the nuclear norm constraint can effectively reduce the redundancy between selected summary sentences.
The above two components ensure the promising performance of the ablation model.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Heter\textsc{Tls}-joint learning}
Based on the assumption that the remarkable improvement of \linebreak
Heter\textsc{Tls} compared with baselines is due to jointly training node representations and clustering regularization, we show the performance in a separate learning pattern.
Date representations are first learned using a HAN to predict which date should be selected to form a timeline.
We then cluster sentence nodes in the graph to produce center cluster representations, which will be used to calculate the similarity with the selected date representations and rank timeline candidates.
The final step of joint learning and separate learning are the same where one sentence per cluster is placed along a chronological order.

From the last block in the Tables, implementing the subtasks individually degrades the performance to a great extent. 
We consider that in the joint learning framework of Heter\textsc{Tls}, vertices learn more discriminative features under the guidance and constraint of sentence clustering and in turn improve clustering accuracy, which cannot be imitated by separate learning.
This result further indicates the superiority of Heter\textsc{Tls}, implying that the combination of node representations and clustering structure is promising for identifying salient dates and sentence candidates simultaneously.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Running time}
\label{subsec:running}

We conducted an investigation of running time with all models being trained on the same device and show the results in Figure~\ref{runningtime}.
Heter\textsc{Tls} ran up to an order of magnitude faster than most baselines, while it achieved comparable running efficiency to the current fastest baseline DATEWISE (2020).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 5
\begin{figure}[b]
\begin{center}
\includegraphics{30-1ia7f5.pdf}
\end{center}
\caption{Comparison of running time of current state-of-the-art models and Heter\textsc{Tls}}
\label{runningtime}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The following two reasons may explain the efficiency of Heter\textsc{Tls}.
\begin{inparaenum}[1)]
    \item Accurate node initialization enables the model to converge to a globally optimal solution in less than eight epochs. Since transductive semi-supervised learning requires fewer labeled date nodes, it can simplify the scale of the training model and reduce the training time caused by parameter updates. 
    \item Previous methods rank all candidates by measuring informativeness, redundancy, coherence, and diversity \cite{yan2011evolutionary}. In contrast, our strategy reduces the time complexity by only measuring the similarity between date and cluster representations to select candidate clusters that exceed a pre-defined threshold. It can thus extract the most informative sentence in each candidate cluster as a summary without consuming time on the multi-index optimization problem. 
\end{inparaenum}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Impact of parameters}
\label{subsec:parameters}

There are two essential hyper parameters in our experiments: $\lambda$ is adopted to balance the importance between $\mathcal{L}_{\mathit{classify}}$ and $\mathcal{L}_{\mathit{cluster}}$ in Equation~\ref{overall_loss}, and $\delta$ acts as a threshold to decide the most related clusters for selected dates (Figure~\ref{extractor}).
Several sets of $\lambda$ and $\delta$ were tested in terms of AR1-F and AR2-F, and a general overview is give in Figure~\ref{parameters}.
Heter\textsc{Tls} performed the best when $\lambda=1.5$ and $\delta=0.6$ on T17 dataset, while $\lambda \in [2.0,2.5]$ and $\delta \in [0.5,0.55]$ on Crisis, Entities, and CovidTLS datasets.
It is explicit that a larger $\delta$ works better.
A plausible reason is that a relatively high threshold can effectively filter irrelevant clusters and reduce the redundancy of generated timelines.
However, the gradual changes in histograms indicate that our method rarely fails to converge as parameters vary because it is robust and insensitive to parameters.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 6
\begin{figure}[b]
\begin{center}
\includegraphics{30-1ia7f6.pdf}
\end{center}
\caption{Impact of parameters}
\label{parameters}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Ratio of labeled dates}
\label{subsec:ratio}

Current GNNs are generally divided into two categories, one is transductive and the other is inductive-based method.
The transductive GNNs are provided with only a certain percentage of ground-truth labels to train the model and further predict other labels.
We therefore evaluate the clustering accuracy based on the scale of the given ground-truth date labels and show the trends in Figure~\ref{dataratio}, from which it is clearly observed that our model achieved promising Macro-F1 scores for date classification on test sets when the ratio of labeled dates was set to $40$ or $50\%$ in the training phase. 
The performance of classification before the turning points increases rapidly as the ratio of labeled date nodes increases, while it becomes stable after those points.
Therefore, we can reasonably believe that our HAN-based transductive learning earns high-quality date classification even with small-scale labeled data, so it can be effectively applied to real TLS tasks.
Specifically, Heter\textsc{Tls} learns word-level/sentence-level semantic features implied in a small amount of labeled dates, which can help predict critical time stamps that should be preserved in timelines.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 7
\begin{figure}[t]
\begin{center}
\includegraphics{30-1ia7f7.pdf}
\end{center}
\caption{Ratio of labeled date nodes on training set vs. corresponding accuracy on test set}
\label{dataratio}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Consecutive dates and redundancy}\label{subsec:consecutive}

The proportions of consecutive dates in chronologically ordered model-generated timelines and ground-truth timelines were experimentally measured according to \citeA{ghalandari2020examining}.
Automatically constructed timelines often contain a high amount of multiple adjacent dates, while this is not the case in ground-truth timelines.
News articles and sentences published on adjacent dates tend to refer to the same story, especially in a long-time-span dataset such as Entities.

Combining with Table~\ref{dataset_statistics}, Table~\ref{consecutive_dates} reveals that because the time duration of Entities dataset is the longest, up to 12 years, the proportion of adjacent dates is the lowest among all datasets.
Therefore, we legitimately believe that the trend of adjacent date proportion is the same as that of redundancy.
The results in Table~\ref{consecutive_dates} indicate that Heter\textsc{Tls} is the closest to the ground-truth, thereby proving its ability to predict salient dates.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 5
\begin{table}[t]
\input{07table05.tex}
\hangcaption{Proportions of consecutive dates of timelines produced with different methods and ground-truths}
\label{consecutive_dates}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Case study}

We would like to show the quality of timelines generated by Heter\textsc{Tls} through a case study.
The topic \textit{Steve Jobs} is taken from Entities dataset with the time duration from 2003-04-28 to 2011-08-24.
Figure~\ref{example1} shows parts of the ground-truth timeline of certain dates, while \ref{example2} lists the Heter\textsc{Tls}-generated timeline with similar period coverage as the ground-truth.
We manually colored some keywords to illustrate consistent contents in both timeline summaries.
The examples demonstrate different levels of detail in describing particular events.
Readers can concretely judge our model by precise dates (marked in red) and subjects (marked in orange).
The following three advantages of Heter\textsc{Tls} are explicit by comparing it with the ground-truth:
\begin{itemize}
    \item The semi-supervised date prediction component of Heter\textsc{Tls} can accurately position \linebreak
	salient dates as the ground-truth, which is the very principle for extracting TLS sentences.
    \item Our model can capture the major object of each event or topic well (marked in orange) in a daily summary. For example, the subject of the ground-truth on 2003-04-28 is \textit{Apple launches}, and Heter\textsc{Tls} also generates the same phrase as the subject. On 2009-06-29, \textit{Steve Dowling announces} and \textit{Steve Dowling said} serve as subjects in the ground-truth and model-generated summary, respectively.
    \item Although Heter\textsc{Tls} generates timelines in an extractive manner, the generated summaries are short and accurate. Current extractive methods always adopt greedy or beam search to extract an uncertain number of sentences as timelines, which greatly increases redundancy. We use clustering-based constraints and intra-class extraction to ensure that Heter\textsc{Tls} generates short but accurate sentences. 
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 8
\begin{figure}[t]
\begin{center}
\includegraphics{30-1ia7f8.pdf}
\end{center}
\caption{Parts of a ground-truth timeline summary on the topic of \textit{Steve Jobs} from Entities dataset.}
\label{example1}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

However, even though the Heter\textsc{Tls} model produces satisfactory performance for timeline summarization, there is still scope for improvement.
Hence, we investigate the above cases further, where even the well-trained model goes wrong.
To start with, we observe some interesting cases for which the model does not generate the desired gold summary due to the fact that some information in the gold summary is actually not present in any of the source documents.
Since our Heter\textsc{Tls} is literally an extractive summarization model, it lacks the ability to generate new words or phrases.

Another genre of erroneous summaries, which we detect while experimenting with the Entities dataset, comes from lacking clear contextualization and topic delimitation.
Figure~\ref{example2} 2010-01-27 presents one such example, where the model should summarize information about ``the iPad'', but as the source document includes references to ``the Mac, the iPad, the iPod'', the model lost attention and mixed up information about the functions and devices in one summary.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 9
\begin{figure}[t]
\begin{center}
\includegraphics{30-1ia7f9.pdf}
\end{center}
\hangcaption{Partial model-generated timeline summary on the topic of \textit{Steve Jobs} from Entities dataset produced by Heter\textsc{Tls}.}
\label{example2}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusion}

We addressed several fundamental problems concerning TLS and proposed a joint learning model called Heter\textsc{Tls}, which trains a HAN by utilizing clustering structure learning-based event detection.
The proposed model facilitates node representations with information of different semantic units.
Meanwhile, the sentence representations with clustering structure are rich in date- and semantic-level features, which significantly reduce redundancy and improve clustering accuracy.
Experimental results, including those of the ablation studies of each part of the overall architecture, demonstrated the effectiveness of Heter\textsc{Tls}.
However, most of the generated timelines are still far from oracle timeline extractors and leave large gaps for improvements.
Potential future directions include a more principled use of our proposed heuristic for detecting content relevant to specific dates, the use of abstractive techniques, more effective treatment of the redundancy challenge, and extending the new dataset with multiple sources.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\acknowledgment

The authors would like to gratefully acknowledge the reviewers for their time and valuable comments.
This paper is an extended version of the paper \cite{you2022joint} accepted for publication at the Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL 2022).
This extended version contains the following changes:
\begin{itemize}
\item[\textbullet] More baseline models and detailed information about datasets were introduced and discussed in Section~\ref{sec:related} and Section~\ref{sec:experiments}.
\item[\textbullet] More experiments and discussions of our proposal on a newly released large-scale corpus and the impact of parameters were also included in Section~\ref{sec:results} to show our method is effective in a practical setting. They were in the appendix of the original paper.
\item[\textbullet] Detailed initialization of edges was demonstrated in Section~\ref{sec:method}, and we also specifically described how to attach date labels for sentences in Section~\ref{sec:experiments}.
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{jnlpbbl_1.7}
\bibliography{07refs}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{biography}

\bioauthor[:]{Jingyi You}{%
She is currently a Ph.D. candidate at Department of Information and Communications Engineering, Tokyo Institute of Technology.
Before that, she received M.E. from Tokyo Institute of Technology in 2020 and B.E. from Dalian University of Technology in 2018.
Her research interests include natural language processing and machine learning, particularly graph neural networks.
}

\bioauthor[:]{Dongyuan Li}{%
He is currently a Ph.D. candidate at Department of Information and Communications Engineering, Tokyo Institute of Technology.
Before that, he received M.E. from Xidian University in 2021 and B.E. from Dalian University of Technology in 2018.
His current research interests are in natural language processing with a specific focus on text infilling.
}

\bioauthor[:]{Hidetaka Kamigaito}{%
He received his Ph.D. from Tokyo Institute of Technology, and is currently an associate professor in Nara Institute of Science and Technology.
He worked as an assistant professor at Institute of Innovative Research, Tokyo Institute of Technology.
His current research interests are in natural language processing with a specific focus on document-level text processing.
}

\bioauthor[:]{Kotaro Funakoshi}{%
He received his Ph.D. from Tokyo Institute of Technology.
He worked as a program-specific associate professor at Kyoto University, and currently is an associate professor at Institute of Innovative Research, Tokyo Institute of Technology.
His current research interests include natural language processing.
}

\bioauthor[:]{Manabu Okumura}{%
Manabu Okumura was born in 1962.
He received B.E., M.E., and Dr. Eng. from Tokyo Institute of Technology in 1984, 1986, and 1989 respectively.
He was an assistant at the Department of Computer Science, Tokyo Institute of Technology from 1989 to 1992, and an associate professor at the School of Information Science, Japan Advanced Institute of Science and Technology from 1992 to 2000.
He is currently a professor at Institute of Innovative Research, Tokyo Institute of Technology.
His research interests include natural language processing, especially text summarization, computer-assisted language learning, sentiment analysis, and text data mining.
}
\end{biography}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\biodate


\end{document}

