%%\documentclass[11pt]{article}
\documentclass[11pt,twoside]{article}
\usepackage{jair}
\usepackage{theapa}
\usepackage{graphicx}
\usepackage{url}
\usepackage{moreverb}
\usepackage[]{algorithm2e}

\usepackage{rotating}
\usepackage{multirow}

\jairheading{22}{2004}{457-479}{07/04}{12/04}
\ShortHeadings{LexRank: Graph-based Lexical Centrality as Salience 
in Text Summarization}
{Erkan \& Radev}
\firstpageno{457}

\begin{document}

\title{LexRank: Graph-based Lexical Centrality as Salience in Text Summarization}

\author{\name G\"{u}ne\c{s} Erkan \email {gerkan@umich.edu}\\
\addr{Department of EECS\\
University of Michigan, Ann Arbor, MI 48109 USA}\\\\
\name Dragomir R. Radev \email {radev@umich.edu}\\
  \addr {School of Information \& Department of EECS \\
  University of Michigan, Ann Arbor, MI 48109 USA}
}
\maketitle

\begin{abstract}
We introduce a stochastic graph-based method for computing relative
importance of textual units for Natural Language Processing. We test
the technique on the problem of Text Summarization (TS).  Extractive
TS relies on the concept of sentence salience to identify the most
important sentences in a document or set of documents. Salience is
typically defined in terms of the presence of particular important
words or in terms of similarity to a centroid pseudo-sentence. We
consider a new approach, LexRank, for computing sentence importance
based on the concept of eigenvector centrality in a graph
representation of sentences.  In this model, a connectivity matrix
based on intra-sentence cosine similarity is used as the adjacency
matrix of the graph representation of sentences.  Our system, based on
LexRank ranked in first place in more than one task in the recent DUC
2004 evaluation.  In this paper we present a detailed analysis of our
approach and apply it to a larger data set including data from earlier
DUC evaluations.  We discuss several methods to compute centrality
using the similarity graph.  The results show that degree-based
methods (including LexRank) outperform both centroid-based methods and
other systems participating in DUC in most of the cases. Furthermore,
the LexRank with threshold method outperforms the other degree-based
techniques including continuous LexRank. We also show that our
approach is quite insensitive to the noise in the data that may result
from an imperfect topical clustering of documents.
\end{abstract}

\section{Introduction}
In recent years, natural language processing (NLP) has moved to a very
firm mathematical foundation. Many problems in NLP, e.g.,
parsing \cite{Collins97}, word sense disambiguation \cite{Yarowsky95},
and automatic paraphrasing \cite{Barzilay&Lee03} have benefited
significantly by the introduction of robust statistical
techniques. Recently, robust graph-based methods for NLP have also
been gaining a lot of interest, e.g., in word clustering
\cite{Brew&SchulteImWalde02} and prepositional phrase
attachment \cite{Toutanova&al.04}. 

In this paper, we will take graph-based methods in NLP one step
further. We will discuss how random walks on sentence-based graphs can
help in text summarization. We will also briefly discuss how similar
techniques can be applied to other NLP tasks such as named entity
classification, prepositional phrase attachment, and text
classification (e.g., spam recognition).

Text summarization is the process of automatically creating a
compressed version of a given text that provides useful information
for the user.  The information content of a summary depends on user's
needs.  Topic-oriented summaries focus on a user's topic of interest,
and extract the information in the text that is related to the
specified topic.  On the other hand, generic summaries try to cover as
much of the information content as possible, preserving the general
topical organization of the original text.  In this paper, we focus on
multi-document extractive generic text summarization, where the goal
is to produce a summary of multiple documents about the same, but
unspecified topic.

Extractive summarization produces summaries by choosing a subset of
the sentences in the original document(s).  This contrasts with
abstractive summarization, where the information in the text is
rephrased.  Although summaries produced by humans are typically not
extractive, most of the summarization research today is on extractive
summarization.  Purely extractive summaries often give better results
compared to automatic abstractive summaries.  This is due to the fact
that the problems in abstractive summarization, such as semantic
representation, inference and natural language generation, are
relatively harder compared to a data-driven approach such as sentence
extraction.  In fact, truly abstractive summarization has not reached
to a mature stage today.  Existing abstractive summarizers often
depend on an extractive preprocessing component.  The output of the
extractor is cut and pasted, or compressed to produce the abstract of
the text \cite{Witbrock&Mittal99,Jing02-cl,Knight&Marcu00}.  SUMMONS
\cite{Radev&McKeown98} is an example of a multi-document summarizer
which extracts and combines information from multiple sources and
passes this information to a language generation component to produce
the final summary.

Early research on extractive summarization is based on 
simple heuristic features of the sentences such as
their position in the text, the overall frequency
of the words they contain, or some key phrases indicating the 
importance of the sentences 
\cite{baxendale58,edmundson69,luhn58}.
A commonly used measure to assess the importance of the words
in a sentence is the
\emph{inverse document frequency}, or
idf, which is defined by the formula \cite{sparck72statistical}:
\begin{equation}
\textrm{idf}_i = \textrm{log}\Big(\frac{N}{n_i}\Big)
\end{equation}
where 
$N$ is the total number of the documents in a collection, and
$n_i$ is the number of documents in which word $i$ occurs.
For example, the words that are likely to occur
in almost every document (e.g. articles ``a" and ``the")
have idf values close to zero
while rare words (e.g. medical terms, proper nouns)
typically have higher idf values.

More advanced techniques also
consider the relation between sentences
or the discourse structure by using synonyms of the words or
anaphora resolution \cite{Mani&Bloedorn97a,Barzilay&Elhadad99}.
Researchers have also 
tried to integrate machine learning into summarization
as more features have been proposed and
more training data have become available
\cite{Kupiec&al.95,lin99,Osborne02,daumeiii-marcu:2004:EMNLP1}.

Our summarization approach in this paper
is to assess the \emph{centrality}
of each sentence in a cluster and extract the most important
ones to include in the summary.
We investigate different ways of defining
the lexical centrality principle in multi-document summarization,
which measures centrality in terms of lexical properties of the sentences.

In Section~\ref{centroid-based}, we
present centroid-based summarization, 
a well-known method for judging sentence centrality. Then we
introduce three new measures for centrality, Degree, LexRank with
threshold, and continuous LexRank, inspired
from the ``prestige'' concept in social networks. 
We propose a graph representation of a document cluster, where
vertices represent the sentences and edges are defined in terms
of the similarity relation between pairs of sentences.
This representation enables us to make use of several centrality
heuristics defined on graphs.
We compare
our new methods with centroid-based summarization
using a feature-based generic summarization toolkit,
MEAD, and show that our new features outperform Centroid
in most of the cases. Test data for our experiments are
taken from 
2003 and 2004 summarization evaluations of
Document
Understanding Conferences (DUC) 
to compare our system with other state-of-the-art 
summarization systems and human performance as well.

\section{Sentence Centrality and Centroid-based Summarization}
\label{centroid-based}
Extractive summarization works by choosing a subset
of the sentences in the original documents.
This process can be viewed as identifying the most
\emph{central} sentences in a (multi-document)
cluster that give the necessary and
sufficient amount of information related to the main theme of the cluster.
Centrality of a sentence is often defined in terms of the centrality of
the words that it contains.
A common way of assessing word centrality is to look at the centroid
of the document cluster in a vector space.
The centroid of a cluster is
a pseudo-document which 
consists of words that have tf$\times$idf scores above a predefined
threshold, where tf is the frequency of a word in the cluster, and
idf values are typically computed over a much larger and similar
genre data set.
%%A centroid can also be represented as an $N$-dimensional
%%vector, where $N$ is the number of words in the centroid.
In centroid-based summarization \cite{Radev&al.00},
the sentences that contain more words from the 
centroid
of the
cluster are considered as central
(Algorithm~\ref{alg-centroid}).
This is a measure of how close the sentence is to the centroid of
the cluster.
Centroid-based summarization has given promising results
in the past, and it has resulted in the first
web-based multi-document summarization system\footnote{
\url{http://www.newsinessence.com}} \cite{Radev&al.01h}.

\linesnumbered
\begin{algorithm}
{\scriptsize
%\center
%\SetLine
\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}
\SetKwFunction{Insert}{Insert}
\SetKwFunction{Cosine}{Cosine}
\Input{An array $S$ of $n$ sentences, cosine threshold $t$}
\Output{An array $C$ of Centroid scores}
Hash $WordHash$\;
%%Set $Centroid$\;
Array $C$\;
\CommentSty{/* compute tf$\times${}idf scores for each word */}\\
\For{$i\leftarrow 1$ to n}{
  \ForEach{word $w$ of $S[i]$}{
	$WordHash\{w\}\{\textrm{``tfidf"}\}$ =  $WordHash\{w\}\{\textrm{``tfidf"}\} + idf\{w\}$\;
  }
}
\BlankLine
\CommentSty{/* construct the centroid of the cluster */}\\
\CommentSty{/* by taking the words that are above the threshold*/}\\
\ForEach{word $w$ of $WordHash$}{
   \If {$WordHash\{w\}\{\textrm{``tfidf"}\}>t$} {
	$WordHash\{w\}\{\textrm{``centroid"}\}$ = $WordHash\{w\}\{\textrm{``tfidf"}\}$\;
%%	\Insert{$Centroid$,$w$}\;
   }
   \Else {
	$WordHash\{w\}\{\textrm{``centroid"}\}$ = 0\;
   }
}
\BlankLine
\CommentSty{/* compute the score for each sentence */}\\
\For{$i\leftarrow 1$ to n}{
   $C[i]$ = 0\;
   \ForEach{word $w$ of $S[i]$}{
%%   $C[i]$ =  $C[i]$ + \Cosine{$S[i]$,$Centroid$}\;
   $C[i]$ =  $C[i]$ + $WordHash\{w\}\{\textrm{``centroid"}\}$\;
  }
}
\Return{$C$}\;
}
\caption{Computing Centroid scores.}
\label{alg-centroid}
\end{algorithm}


\section{Centrality-based Sentence Salience}
In this section, we propose several other criteria to assess sentence
salience. All of our approaches are based on the concept
of \emph{prestige}%
\footnote{
``Prestige" and ``centrality" stand for the same concept
with the difference that the former is often
defined for directed graphs whereas the latter is defined
for undirected graphs.}
in social networks, which has also inspired
many ideas in computer networks and information retrieval.
A social network is a mapping of relationships 
between interacting entities (e.g. people, organizations,
computers).
Social networks are represented as graphs, where the nodes
represent the entities and the links represent
the relations between the nodes.

A cluster of documents can be viewed as a network of sentences that
are related to each other.  Some sentences are more similar to each
other while some others may share only a little information with the
rest of the sentences.  We hypothesize that the sentences that are
similar to many of the other sentences in a cluster are more central
(or \emph{salient}) to the topic.  There are two points to clarify in
this definition of centrality. First is how to define similarity
between two sentences. Second is how to compute the overall centrality
of a sentence given its similarity to other sentences.

To define similarity, we use the bag-of-words model to represent each
sentence as an $N$-dimensional vector, where $N$ is the number
of all possible words in the target language.
For each word that occurs in a sentence, the value of the corresponding
dimension in the vector representation of the sentence
is the number of occurrences of the word in the sentence times
the idf of the word.
The similarity between two sentences is then defined by the 
cosine 
between two corresponding vectors:
\begin{equation}
\textrm{idf-modified-cosine}(x,y) = 
\frac{\sum_{w\in{}x,y}
\textrm{tf}_{w,x}\textrm{tf}_{w,y}(\textrm{idf}_w)^2}
{\sqrt{\sum_{x_i\in{}x}(\textrm{tf}_{x_i,x}\textrm{idf}_{x_i})^2} \times
\sqrt{\sum_{y_i\in{}y}(\textrm{tf}_{y_i,y}\textrm{idf}_{y_i})^2}}
%%{||x||\times{}||y||}
\end{equation}
where $\textrm{tf}_{w,s}$ is the number of occurrences of the word
$w$ in the sentence $s$.

A cluster of documents
may be represented by a cosine similarity matrix where each
entry in the matrix is the similarity between the corresponding sentence
pair.
Figure~\ref{cluster} shows a subset of a cluster
used
in DUC 2004, and the corresponding cosine similarity matrix.
Sentence ID d$X$s$Y$
indicates the $Y^{\textrm{th}}$ sentence in the $X^{\textrm{th}}$
document. This matrix can also be represented as a
weighted graph where each edge shows the cosine similarity between
a pair of sentence (Figure~\ref{weighted-graph}).
In the following sections,
we discuss several ways of computing sentence centrality using the cosine
similarity matrix and the corresponding graph representation.

\subsection{Degree Centrality}
In a cluster of related documents, many of the sentences are expected
to be somewhat similar to each other since they are all about the
same topic. This can be seen in Figure~\ref{cluster} where the majority
of the values in the similarity matrix are nonzero. Since we are
interested in \emph{significant} similarities, we can eliminate 
some low values in this matrix by defining a threshold so that
the cluster can be viewed as an (undirected) graph,
where each sentence of the cluster is a node, and
significantly similar sentences are connected to each other.
Figure~\ref{lpr-graph} shows
the graphs that correspond to the adjacency matrices derived
by assuming the pair of sentences that have a similarity above
$0.1, 0.2,$ and $0.3$, respectively,
in Figure~\ref{cluster} are similar to each other. 
Note that there should also be self links for all of the nodes in
the graphs since every sentence is trivially similar to itself.
Although we omit the self links for readability, the arguments
in the following sections assume that they exist.

A simple way of assessing sentence centrality by looking at
the graphs in Figure~\ref{lpr-graph} is to count the number
of similar sentences for each sentence.
We define
\emph{degree centrality} of a sentence
as the degree of the corresponding node in the similarity graph.
As seen in Table~\ref{degree-scores}, the choice of cosine threshold
dramatically influences
the interpretation of centrality. 
Too low thresholds may mistakenly
take weak similarities into consideration while too high thresholds may
lose many of the similarity relations in a cluster.

\begin{figure}[htp]
\scriptsize
\center
\begin{tabular}{|c c l|}
\hline
SNo & ID & Text\\
\hline
1 &d1s1 & Iraqi Vice President Taha Yassin Ramadan announced today, Sunday, \\
&     & that Iraq refuses to back down from its decision to stop cooperating\\
&&      with disarmament inspectors before its demands are met.\\
2 &d2s1 & Iraqi Vice president Taha Yassin Ramadan announced  today, Thursday,\\
&&      that Iraq rejects cooperating with the United Nations except on the\\
&&      issue of lifting the blockade imposed upon it since the year 1990.\\
3&d2s2 & Ramadan told reporters in Baghdad that "Iraq cannot deal positively\\ 
&&      with whoever represents the Security Council unless there was a clear\\
&&      stance on the issue of lifting  the blockade off of it.\\
4&d2s3 & Baghdad had decided late last October to completely cease cooperating\\
&&      with the inspectors of the United Nations Special Commission \\
&&      (UNSCOM), in charge of disarming Iraq's weapons, and whose work \\
&&      became very limited since the fifth of August, and announced it will not \\
&&      resume its cooperation with the Commission even if it were subjected \\
&&	to a military operation.\\
5&d3s1 & The Russian Foreign Minister, Igor Ivanov, warned today, Wednesday \\
&&      against using force against Iraq, which will destroy, according to \\
&&      him, seven years of difficult diplomatic work and will complicate \\ 
&&      the regional situation in the area.\\
6&d3s2 & Ivanov contended that carrying out air strikes against Iraq, who refuses\\
&&      to cooperate with the United Nations inspectors, ``will end  the\\
&&      tremendous work achieved by the international group during the past\\ 
&&      seven years and will complicate the situation in the region.''\\ 
7&d3s3 & Nevertheless, Ivanov stressed that Baghdad must resume working \\
&&       with the Special Commission in charge of disarming the Iraqi \\
&&       weapons of mass destruction (UNSCOM).\\
8&d4s1 & The Special Representative of the United Nations Secretary-General \\
&&      in Baghdad, Prakash Shah, announced today, Wednesday, after \\
&&      meeting with the Iraqi Deputy Prime Minister Tariq Aziz, that Iraq \\
&&      refuses to back down from its decision to cut off cooperation with \\
&&  the disarmament inspectors.\\
9&d5s1 & British Prime Minister Tony Blair said today, Sunday, that the crisis\\
&&      between the international community and Iraq ``did not end'' and that \\
&&      Britain is still ``ready, prepared,  and able to strike Iraq.''\\
10&d5s2 & In a gathering with the press held at the Prime Minister's office, \\
&&      Blair contended that the crisis with Iraq ``will not end until Iraq has\\
&&      absolutely and unconditionally respected its commitments'' towards \\
&&      the United Nations. \\
11&d5s3 & A spokesman for Tony Blair had indicated that the British Prime \\
& &     Minister gave permission to British Air Force Tornado planes stationed \\
& &     in Kuwait to join the aerial  bombardment against Iraq. \\
\hline
\end{tabular}\\

\vspace{.2cm}

\tiny{
\begin{tabular}{c|p{0.2cm}p{0.2cm}p{0.2cm}p{0.2cm}p{0.2cm}p{0.2cm}p{0.2cm}p{0.2cm}p{0.2cm}p{0.2cm}p{0.2cm}}
&1&2&3&4&5&6&7&8&9&10&11\\
\hline
\input{matrix.latex}
\end{tabular}
}
\caption{Intra-sentence cosine similarities in a subset of cluster
  d1003t from DUC 2004.
Source: Agence France Presse (AFP) Arabic Newswire (1998). Manually translated to English.}
\label{cluster}
\end{figure}

\begin{figure}[htp]
\center
\includegraphics[scale=0.75]{dense3}
\caption{Weighted cosine similarity graph for the cluster in Figure~\ref{cluster}.}
\label{weighted-graph}
\end{figure}

\begin{figure}[htp]
\center
\includegraphics[scale=0.6]{lpr_example1.eps}

\vspace{.2cm}
\rule{0.5\linewidth}{.2mm}
\vspace{.2cm}

\includegraphics[scale=0.6]{lpr_example2.eps}

\vspace{.2cm}
\rule{0.5\linewidth}{.2mm}
\vspace{.2cm}

\includegraphics[scale=0.6]{lpr_example3.eps}

\caption{Similarity graphs that correspond to thresholds 0.1, 0.2, and
0.3, respectively, for the cluster
  in Figure~\ref{cluster}.} 
\label{lpr-graph}
\end{figure}

\begin{table}[htp]
\center
\scriptsize
{
\begin{tabular}{c c c c}
ID &  Degree (0.1) & Degree (0.2) & Degree (0.3)\\
\hline
d1s1&5&4&2\\
d2s1&7&4&2\\
d2s2&2&1&1\\
d2s3&6&3&1\\
d3s1&5&2&1\\
d3s2&7&5&1\\
d3s3&2&2&1\\
d4s1&9&6&1\\
d5s1&5&4&2\\
d5s2&6&4&1\\
d5s3&5&2&2
\end{tabular}
}
\caption{Degree centrality scores for the graphs in Figure~\ref{lpr-graph}.
  Sentence d4s1 is the most central
  sentence for thresholds 0.1 and 0.2.}
\label{degree-scores}
\end{table}

\subsection{Eigenvector Centrality and LexRank}
When computing degree centrality, we have treated each edge
as a \emph{vote} to determine the overall centrality value
of each node. This is a totally democratic method where
each vote counts the same.
However, in many types of social networks, not all
of the relationships are considered equally important.
As an example, consider a social
network of people that are connected to each other
with the friendship relation.
The prestige of a person does not only depend on how many
friends he has, but also depends on \emph{who} his
friends are.

The same idea can be applied to extractive summarization as well.
Degree centrality may have a negative 
effect in the quality of the summaries in some cases where 
several unwanted sentences vote for each other and raise their
centrality. As an extreme example, consider a noisy cluster where
all the documents are related to each other, but only one
of them is about a somewhat different topic. 
Obviously, we would not want any of the sentences in the
unrelated document to be included in a generic summary of the
cluster. However, suppose that the
unrelated document contains some sentences that are very
prestigious considering only the votes in that document.
These sentences will get artificially high 
centrality scores by the local votes from a specific set of
sentences.
This situation can be avoided by considering where the votes come
from and taking the centrality of the \emph{voting} nodes into account
in weighting each vote. 
A straightforward way of formulating this idea is to consider every node
having a centrality value and distributing this centrality to its
neighbors.
This formulation can be expressed by the equation
\begin{equation}
p(u) = \sum_{v\in{}adj[u]}\frac{p(v)}{deg(v)}
\label{pagerank1}
\end{equation}
where $p(u)$ is the centrality of node $u$, $adj[u]$ 
is the set of nodes that are adjacent to $u$,
and $deg(v)$ is the degree of the node $v$.
Equivalently, we can write Equation~\ref{pagerank1} in the matrix
notation as
\begin{equation}
\mathbf{p} = \mathbf{B}^\mathrm{T}\mathbf{p}
\label{pagerank2}
\end{equation}
or
\begin{equation}
\mathbf{p}^\mathrm{T}\mathbf{B} = \mathbf{p}^\mathrm{T}
\label{pagerank3}
\end{equation}
where the matrix $\mathbf{B}$ is obtained from the adjacency
matrix of the similarity graph by dividing each element
by the corresponding row sum:
\begin{equation}
\mathbf{B}(i,j) = \frac{\mathbf{A}(i,j)}{\sum_{k}\mathbf{A}(i,k)}
\end{equation}
Note that a row sum is equal to the degree of the corresponding node.
Since every sentence is similar at least to itself, all row sums
are nonzero. 
Equation~\ref{pagerank3} states that $\mathbf{p}^\mathrm{T}$ is the left
eigenvector of the matrix $\mathbf{B}$ with the corresponding
eigenvalue of $1$.
To guarantee that such an eigenvector exists and can be 
uniquely identified and computed,
we need some mathematical foundations.

A \emph{stochastic} matrix, $\mathbf{X}$, is the transition matrix 
of a Markov chain. 
An element $\mathbf{X}(i,j)$ of a stochastic matrix
specifies the transition probability from state $i$ to state $j$
in the corresponding Markov chain. By the probability axioms,
all rows of a stochastic matrix should add up to 1.
$\mathbf{X^n}(i,j)$ gives the probability of reaching from state $i$
to state $j$ in $n$ transitions.
A Markov chain with the stochastic matrix $\mathbf{X}$ 
converges to a stationary distribution if
\begin{equation}
\lim_{n\rightarrow{}\infty}\mathbf{X^n} = \mathbf{1}^\mathrm{T}\mathbf{r}
\end{equation}
where $\mathbf{1}=(1,1,...,1)$, and the vector
$\mathbf{r}$ is called the stationary distribution of the 
Markov chain.
An intuitive interpretation of the stationary distribution can
be understood by the concept of a random walk.
Each element of the
vector $\mathbf{r}$ gives the asymptotic probability
of ending up in the corresponding state in the long run regardless
of the starting state.
A Markov chain is \emph{irreducible} if any state is reachable from
any other state, i.e. for all $i,j$ there exists an $n$ such that
$\mathbf{X^n}(i,j)\neq{}0$. A Markov chain is \emph{aperiodic}
if for all $i$, $gcd\{n:X^n(i,i) > 0\}=1$.
By the Perron-Frobenius theorem \cite{Seneta:81}, an irreducible and
aperiodic Markov chain is guaranteed to converge to a
unique stationary distribution.
If a Markov chain has reducible or periodic components, 
a random walker may get stuck in these components and never
visit the other parts of the graph.

Since the similarity matrix $\mathbf{B}$ in Equation~\ref{pagerank2}
satisfies the properties of a stochastic matrix, we can treat
it as a Markov chain.
The centrality vector $\mathbf{p}$ corresponds to the stationary distribution
of $\mathbf{B}$. 
However, we need to make sure that the
similarity matrix is always irreducible and aperiodic.
%A solution to this problem was proposed by \citeauthor{pagerank}
%\citeyear{pagerank}.
To solve this problem,
\shortciteauthor{pagerank} \citeyear{pagerank} suggest reserving some low
probability for jumping to any node in the graph.
This way the random walker can ``escape" from periodic or
disconnected components, which makes the graph irreducible and
aperiodic.
If we assign a uniform probability for jumping to any
node in the graph, we are left with the following modified version of
Equation~\ref{pagerank1}, which is known as PageRank,
\begin{equation}
p(u) = \frac{d}{N}+{(1-d)}\sum_{v\in{}adj[u]}\frac{p(v)}{deg(v)}
\label{pagerank4}
\end{equation}
where $N$ is the total number of nodes in the graph, and $d$ is
a ``damping factor", which is typically chosen in the interval $[0.1,0.2]$
\cite{brin98anatomy}.
Equation~\ref{pagerank4} can be written in the matrix
form as
\begin{equation}
\mathbf{p} = [d\mathbf{U}+(1-d)\mathbf{B}]^\mathrm{T}\mathbf{p}
\label{pagerank5}
\end{equation}
where $\mathbf{U}$ is a square matrix with all elements being equal
to $1/N$.
The transition kernel $[d\mathbf{U}+(1-d)\mathbf{B}]$
of the resulting Markov chain is a mixture of two kernels
$\mathbf{U}$ and $\mathbf{B}$.
A random walker on this Markov chain chooses one of
the adjacent states of the current state with probability
$1-d$, or jumps to any state in the graph, including the current state,
with probability $d$.
The PageRank formula was first proposed for computing web page prestige,
and still serves as the underlying mechanism behind the Google
search engine.

The convergence property of Markov chains also provides us with
a simple iterative algorithm, called power method,
to compute the stationary distribution (Algorithm~\ref{powermethod}).
The algorithm starts with a uniform distribution.
At each iteration, the eigenvector is updated by multiplying with
the transpose of the stochastic matrix.
Since the Markov chain is irreducible and aperiodic, the algorithm
is guaranteed to terminate.

\linesnumbered
\begin{algorithm}
{\scriptsize
%\center
%\SetLine
\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}
\Input{A stochastic, irreducible and aperiodic matrix $\mathbf{M}$}
\Input{matrix size $N$, error tolerance $\epsilon$}
\Output{eigenvector $\mathbf{p}$}
$\mathbf{p}_0$=$\frac{1}{N}\mathbf{1}$\;
t=0\;
\Repeat{$\delta<\epsilon$}{
	t=t+1\;
	$\mathbf{p}_t$ = $\mathbf{M}^\mathrm{T}\mathbf{p}_{t-1}$\;
	$\delta$ = $||\mathbf{p}_t-\mathbf{p}_{t-1}||$\;
}
\Return{$\mathbf{p}_t$}\;
}
\caption{Power Method for computing the stationary distribution of a Markov chain.}
\label{powermethod}
\end{algorithm}

Unlike the original
PageRank method, the similarity graph for sentences
is undirected since cosine similarity is
a symmetric relation.
However, this does not make any
difference in the computation of the stationary distribution.
We call this new measure of sentence similarity 
\emph{lexical PageRank}, or \emph{LexRank}.
Algorithm~\ref{alg-lpr} summarizes how to compute LexRank scores
for a given set of sentences. 
Note that Degree centrality scores are also computed (in the $Degree$
array) as a side
product of the algorithm.
Table~\ref{lpr-scores} shows the LexRank scores
for the graphs in Figure~\ref{lpr-graph} setting the damping factor
to $0.85$. 
For comparison, Centroid score for each sentence is also
shown in the table. 
All the numbers are normalized so that the highest ranked 
sentence gets the score $1$. 
It is obvious from the figures that
threshold choice affects the LexRank rankings of some
sentences.

\begin{algorithm}
{\scriptsize
%\center
\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}
\SetKwFunction{Insert}{Insert}
\SetKwFunction{idfmodifiedcosine}{idf-modified-cosine}
\SetKwFunction{PowerMethod}{PowerMethod}
MInput{An array $S$ of $n$ sentences, cosine threshold $t$}
\Output{An array $L$ of LexRank scores}
Array $CosineMatrix[n][n]$\;
Array $Degree[n]$\;
Array $L[n]$\;
\For{$i\leftarrow 1$ to n}{
\For{$j\leftarrow 1$ to n}{
	$CosineMatrix[i][j]$ $=$ \idfmodifiedcosine{$S[i]$,$S[j]$}\;
	\If{$CosineMatrix[i][j] > t$}{
		$CosineMatrix[i][j] = 1$\;
		$Degree[i]++$\;
	}
	\Else{$CosineMatrix[i][j] = 0$\;}
}}
\For{$i\leftarrow 1$ to n}{
\For{$j\leftarrow 1$ to n}{
$CosineMatrix[i][j]$ = $CosineMatrix[i][j] / Degree[i]$\;
}}
$L$ $=$ \PowerMethod{$CosineMatrix$,$n$,$\epsilon$}\;
\Return{$L$}\;
}
\caption{Computing LexRank scores.}
\label{alg-lpr}
\end{algorithm}

\begin{table}[htp]
\center
\scriptsize
{
\begin{tabular}{c c c c c}
ID &  LR (0.1) & LR (0.2) & LR (0.3) &  Centroid\\
\hline
d1s1&0.6007&0.6944&1.0000&0.7209\\
d2s1&0.8466&0.7317&1.0000&0.7249\\
d2s2&0.3491&0.6773&1.0000&0.1356\\
d2s3&0.7520&0.6550&1.0000&0.5694\\
d3s1&0.5907&0.4344&1.0000&0.6331\\
d3s2&0.7993&0.8718&1.0000&0.7972\\
d3s3&0.3548&0.4993&1.0000&0.3328\\
d4s1&1.0000&1.0000&1.0000&0.9414\\
d5s1&0.5921&0.7399&1.0000&0.9580\\
d5s2&0.6910&0.6967&1.0000&1.0000\\
d5s3&0.5921&0.4501&1.0000&0.7902
\end{tabular}
}
\caption{LexRank scores for the graphs in Figure~\ref{lpr-graph}.
  All the values are normalized so that the largest value
  of each column is 1.
  Sentence d4s1 is the most central
  page for thresholds 0.1 and 0.2.}
\label{lpr-scores}
\end{table}

\subsection{Continuous LexRank}
The similarity graphs we have constructed to compute Degree centrality 
and LexRank are unweighted.
This is due to the binary discretization we perform on the
cosine matrix using an appropriate threshold. As in all
discretization operations, this means an information loss.
One improvement over LexRank can be obtained by
making use of the \emph{strength} of the similarity
links. 
If we use the cosine values directly to construct the similarity
graph, we usually 
have a much denser but weighted graph (Figure~\ref{weighted-graph}).
We can normalize the row sums of the corresponding transition
matrix so that we have a stochastic matrix.
The resultant equation is a modified version of LexRank for
weighted graphs:
\begin{equation}
p(u) = \frac{d}{N}+{(1-d)}\sum_{v\in{}adj[u]}\frac{\textrm{idf-modified-cosine}(u,v)}{\sum_{z\in{}adj[v]}\textrm{idf-modified-cosine}(z,v)}p(v)
\label{lpr-equation2}
\end{equation}
This way, while computing LexRank for a sentence,
we multiply the LexRank values of the linking sentences by 
the weights of the links.
Weights are normalized by the row sums, and the damping factor $d$ is added
for the convergence of the method.

\subsection{Centrality vs. Centroid}
Graph-based centrality has several advantages over Centroid. 
First of all,
it accounts for information subsumption among sentences.
If the information content of a sentence subsumes another sentence
in a cluster, it is 
naturally preferred to include the one that contains more
information in the summary.
The degree of a node in the cosine similarity graph is an indication
of how much common information the sentence has with other
sentences. Sentence d4s1 in Figure~\ref{cluster} gets the
highest score since it almost subsumes the information in the first two
sentences of the cluster and has some common information with others. 
Another advantage of our proposed approach is that
it prevents unnaturally high idf scores from boosting up the score
of a sentence that is unrelated to the topic. Although the frequency
of the words are taken into account while computing the Centroid score,
a sentence that contains many rare words with high idf values
may get a high Centroid score even if the words do not occur
elsewhere in the cluster.

\section{Experimental Setup}
In this section, we describe the data set, the evaluation metric
and the summarization system we used in our experiments.
\subsection{Data Set and Evaluation Method}
We used DUC 2003 and 2004 data sets in our experiments.
Task 2 of both DUC 2003 and 2004 involve generic summarization
of news documents clusters.
There are a total of 30 clusters in DUC 2003 and 50 clusters in DUC 2004.
In addition to these two tasks, we used two more data sets from Task 4 of
DUC 2004, which involves cross-lingual generic summarization. First set
(Task 4a)
is composed of Arabic-to-English machine translations of 24 news clusters.
Second set (Task 4b)
is the human translations of the same clusters. All data sets
are in English.

For evaluation, we used
the new automatic summary evaluation metric, 
ROUGE\footnote{\url{http://www.isi.edu/~cyl/ROUGE}}, which
was used for the first time in DUC 2004.
ROUGE is a recall-based metric
for fixed-length summaries which is based on n-gram co-occurrence.
It reports separate scores for 1, 2, 3, and 4-gram matching between
the model summaries and the summary to be evaluated.
Among these different
scores,
unigram-based
ROUGE score (ROUGE-1) has been shown to agree with human judgements
most \cite{rouge-naacl}.

There are 10 different human judges for DUC 2003 Task 2; 8 for 
DUC 2004 Task 2; and 4 for DUC 2004 Task 4.
However, a subset of exactly 4 different human judges produced model 
summaries for any given cluster.
ROUGE requires a limit on the length of the summaries to be able to make
a fair evaluation.
To stick with the DUC 2004 specifications and to be
able to compare our system with human summaries and as well as with
other DUC participants, we produced
665-byte summaries for each cluster and computed ROUGE scores against human
summaries. 

\subsection{MEAD Summarization Toolkit}
We implemented our methods inside the
MEAD\footnote{\url{http://www.summarization.com}}
summarization system \cite{Radev&al.01h}. MEAD 
is a publicly available toolkit for extractive multi-document
summarization. Although it comes as a centroid-based
summarization system by default, its feature set can be 
extended to implement any other method.

The MEAD summarizer consists of three components. 
During the first step, {\it the feature extraction}, each
sentence in the input document (or cluster of documents) is converted
into a feature vector using the user-defined features.
Second, the feature vector is converted
to a scalar value using the {\it combiner}.
Combiner outputs a linear combination of the features
by using the predefined feature weights. 
At the last stage known as
the {\it reranker}, the scores for sentences included in related pairs
are adjusted upwards or downwards based on the type of relation
between the sentences in the pair. Reranker penalizes the sentences
that are similar to the sentences already included in the summary so 
that a better information coverage is achieved.

Three default features that come with the MEAD distribution are
Centroid, Position and Length. Position is the normalized value
of the position of a sentence in the document such that the first
sentence of a document gets the maximum Position value of 1, and
the last sentence gets the value 0. Length is not a real feature
score, but
a cutoff value that ignores sentences shorter than the given
threshold. Several rerankers are implemented in MEAD, including
one based on Maximal Marginal Relevance (MMR) \cite{carbonell&goldstein98}
and the default reranker of the system based on
Cross-Sentence Informational Subsumption (CSIS) \cite{Radev00}. All
of our experiments shown in Section~\ref{sec:results} use the CSIS
reranker.

A MEAD policy is a combination of three components: (a) the command
lines for all features, (b) the formula for converting the feature
vector to a scalar, and (c) the command line for the reranker. A
sample policy might be the one shown in
Figure~\ref{fig:mead-policy}. This example indicates the three 
default MEAD features 
(Centroid, Position, LengthCutoff),
and our new LexRank feature used in our experiments.
Our LexRank implementation requires the cosine similarity
threshold, $0.2$ in the example, as an argument.
Each number next to a feature name shows the relative weight
of that feature (except for LengthCutoff where the number 9 indicates
the threshold for selecting a sentence based on the number of
the words in the sentence).
The reranker in the example is a word-based MMR 
reranker with a cosine
similarity threshold, $0.5$.
Finally ``enidf" specifies the idf database file, which is
a precomputed list of idf's for English words.

\begin{figure}
\center
\scriptsize
\begin{boxedverbatim}
feature LexRank LexRank.pl 0.2
Centroid 1 Position 1 LengthCutoff 9 LexRank 1
mmr-reranker-word.pl 0.5 MEAD-cosine enidf
\end{boxedverbatim}
\caption{A sample MEAD policy.}
\label{fig:mead-policy}
\end{figure}

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

The following sections show the results of the experiments we have
performed on the official DUC data sets with different implementations
of similarity graph based centrality.  We have implemented Degree
centrality, LexRank with threshold and continuous LexRank as separate
features in MEAD.  All the feature values are normalized so that the
sentence that has the highest value gets the score $1$, and the
sentence with the lowest value gets the score $0$.  In all of the
runs, we have used Length and Position features of MEAD as supporting
heuristics in addition to our centrality features. Length cutoff value
is set to 9, i.e. all the sentences that have less than 9 words are
discarded.  The weight of the Position feature is fixed to $1$ in all
runs.  Other than these two heuristic features, we used each
centrality feature alone without combining with other centrality
methods to make a better comparison with each other. For each
centrality feature we are experimenting with, we have run 8 different
MEAD features by setting the weight of the corresponding feature to
${0.5,1.0,1.5,2.0,2.5,3.0,5.0,10.0}$, respectively.

\subsection{Effect of Threshold on Degree and LexRank Centrality}
We have demonstrated that very high thresholds may lose almost all of
the information in a similarity matrix (Figure~\ref{lpr-graph}).  To
support our claim, we have run Degree and LexRank centrality with
different thresholds for our data sets.  Figure~\ref{threshold} shows
the effect of threshold for Degree and LexRank centrality on DUC 2004
Task 2 data.  We have experimented with four different thresholds:
$0.1, 0.2, 0.3,$ and $0.4$.  Eight different data points shown for
each threshold correspond to the runs of the same feature with eight
different weights as we have discussed above.  The mean value of the
eight different experiments is shown as a horizontal line.  It is
apparent in the figures that the lowest threshold, $0.1$, produces the
best summaries.  This means that the information loss in higher
thresholds is high enough to result in worse ROUGE scores. The loss in
ROUGE scores as we move from threshold $0.1$ to $0.2$ is more
significant in Degree centrality.

This effect of threshold is an indication
that our new centrality methods actually \emph{work} for extractive 
summarization.
The higher the threshold, the less informative, or even misleading,
similarity graphs we must have. On the extreme point where we have
a very high threshold, we would have no edges in the graph so that
Degree or LexRank centrality would be of no use.

\begin{figure}[htp]
\center
\begin{tabular}{cc}
\includegraphics[scale=0.4]{degreet2.eps} &
\includegraphics[scale=0.4]{lprt2.eps}\\
(a)&(b)
\end{tabular}
\caption{ROUGE-1 scores for (a) Degree centrality
and (b) LexRank centrality  with different thresholds
on DUC 2004 Task 2 data.}
\label{threshold}
\end{figure}

\subsection{Comparison of Centrality Methods}
Table~\ref{results} shows the ROUGE scores for our
experiments on DUC 2003 Task 2, DUC 2004 Task 2, DUC 2004 Task 4a, and
DUC 2004 Task 4b, respectively. 
We show the minimum, the maximum,
and the average ROUGE-1 scores for eight experiments we have run
for each centrality method corresponding to eight different 
feature weights we have mentioned in Section~\ref{sec:results}.
We include Degree and LexRank
experiments only with threshold $0.1$, the best one we have observed.
%`LRwtX' indicates a policy in which LexRank with threshold $0.1$
%is used and the weight of the feature is set to $X$.
%`LRwoX' indicates a LexRank policy without using a threshold with
%feature weight $X$.
%`DegreeX' is similar except that Degree feature is used instead of
%LexRank with threshold $0.1$.
%Finally, `CentX' shows a policy with Centroid weight $X$.
We also include two baselines for each data set.
The first baseline we have used is extracting random sentences from
the cluster. 
We have performed five random runs for each
data set.
The results in the tables are for the median runs.
The second baseline,
shown as `lead-based' in the tables, is using
only the Position feature without any centrality method. This is
tantamount to producing lead-based summaries, which is a widely used
and very challenging baseline in the text summarization community
\cite{brandow&al.95}.

%The results confirm once again that multi-document
%text summarization is a hard task where even human judges hardly agree
%with each other so that there is a relatively small room for improvement
%between baselines
%and the human performances.
%We also show human summary scores, centroid-based summary scores,
%LexRank without using a threshold, and two baselines.

The top scores we have got in all data sets come from our new methods.
All of our three new methods (Degree, LexRank with threshold, and
continuous LexRank) perform significantly better than the baselines in
all data sets.  They also perform better than centroid-based summaries
except for the DUC 2003 data set where the difference between Centroid
and the others is not obvious.  $0.1$ seems to be an appropriate
threshold such that the results seem as successful as using continuous
LexRank.  It is also hard to say that Degree and LexRank are
significantly different from each other. This is an indication that
Degree may already be a good enough measure to assess the centrality
of a node in the similarity graph.  Considering the relatively low
complexity of degree centrality, it still serves as a plausible
alternative when one needs a simple implementation.  Computation of
Degree can be done on the fly as a side product of LexRank just before
the power method is applied on the similarity graph.

To have an idea of the relative success of our methods among other
summarization systems, we have compared our ROUGE scores with other
participants' scores in the same DUC data
sets. Table~\ref{duc03-official} and Table~\ref{duc04-official} show
the official ROUGE-1 scores for top five participants and human
summarizers on DUC 2003 and 2004 data, respectively.  Most of the
LexRank scores we got are better than the second best system in DUC
2003 and worse than the best system.  Best few scores for each method
are always statistically indistinguishable from the best system in the
official evaluations considering the 95\% confidence interval. On all
three DUC 2004 data sets, we achieved a better score than the best
participant in at least one of the policies we tried. On the DUC 2003
data, we achieved several scores that are between the best and the
second best system.

\begin{table}[htp]
\footnotesize{
\begin{tabular}{ll}
\begin{tabular}{|c|c|c|c|}
\hline
&\multicolumn{3}{|c|}{2003 Task2}\\
\cline{2-4}
&min&max&average\\
\hline
Centroid
&0.3523&0.3713&0.3624\\
\hline
Degree (t=0.1)
&0.3566&0.3640&0.3595\\
\hline
LexRank (t=0.1)
&0.3610&0.3726&0.3666\\
\hline
Cont. LexRank
&0.3594&0.3700&0.3646\\
\hline
\end{tabular}
&
\begin{tabular}{|c|c|c|c|}
\hline
&\multicolumn{3}{|c|}{2004 Task2}\\
\cline{2-4}
&min&max&average\\
\hline
Centroid
&0.3580&0.3767&0.3670\\
\hline
Degree (t=0.1)
&0.3590&0.3830&0.3707\\
\hline
LexRank (t=0.1)
&0.3646&0.3808&0.3736\\
\hline
Cont. LexRank
&0.3617&0.3826&0.3758\\
\hline
\end{tabular}\\
{
\begin{tabular}{lrl}
baselines: &random:& 0.3261\\
&lead-based: &0.3575
\end{tabular}
}
&
{
\begin{tabular}{lrl}
baselines: &random:& 0.3238\\
&lead-based: & 0.3686
\end{tabular}
}
\\
\multicolumn{1}{c}{\normalsize{(a)}}&
\multicolumn{1}{c}{\normalsize{(b)}}\\
&\\
&\\
\begin{tabular}{|c|c|c|c|}
\hline
&\multicolumn{3}{|c|}{2004 Task4a}\\
\cline{2-4}
&min&max&average\\
\hline
Centroid
&0.3768&0.3901&0.3826\\
\hline
Degree (t=0.1)
&0.3863&0.4027&0.3928\\
\hline
LexRank (t=0.1)
&0.3931&0.4038&0.3974\\
\hline
Cont. LexRank
&0.3924&0.4002&0.3963\\
\hline
\end{tabular}
&
\begin{tabular}{|c|c|c|c|}
\hline
&\multicolumn{3}{|c|}{2004 Task4b}\\
\cline{2-4}
&min&max&average\\
\hline
Centroid
&0.3760&0.3962&0.4034\\
\hline
Degree (t=0.1)
&0.3801&0.4147&0.4026\\
\hline
LexRank (t=0.1)
&0.3837&0.4167&0.4052\\
\hline
Cont. LexRank
&0.3772&0.4082&0.3966\\
\hline
\end{tabular}
\\
{
\begin{tabular}{lrl}
baselines: &random:& 0.3593\\
&lead-based: &0.3788
\end{tabular}
}
&
{
\begin{tabular}{lrl}
baselines: &random:& 0.3734\\
&lead-based: & 0.3587
\end{tabular}
}\\
\multicolumn{1}{c}{\normalsize{(c)}}&
\multicolumn{1}{c}{\normalsize{(d)}}\\
\end{tabular}
}
\caption{ROUGE-1 scores for different MEAD policies on
DUC 2003 and 2004 data.}
\label{results}
\end{table}

\begin{table}[htp]
\begin{center}
\scriptsize{
\begin{tabular}[t]{|l|cc|}
%%\hline
%%\multicolumn{7}{|c|}{TASK 2}\\
\hline
\multicolumn{3}{|c|}{TASK 2}\\
\hline
{\bf Peer}&{\bf ROUGE-1}&{\bf 95\% Confidence}\\
{\bf Code}&{\bf Score}&{\bf Interval}\\
\hline
\input{duc03.latex.2}
\hline
\end{tabular}
}
\end{center}
\caption{Summary of official ROUGE scores for DUC 2003 Task 2. Peer codes: manual
summaries [A-J] and top five system submissions.
}
\label{duc03-official}
\end{table}

\begin{table}[htp]
\begin{center}
\scriptsize{
\begin{tabular}{lr}
\begin{tabular}[t]{|l|cc|}
%%\hline
%%\multicolumn{7}{|c|}{TASK 2}\\
\hline
\multicolumn{3}{|c|}{TASK 2}\\
\hline
{\bf Peer}&{\bf ROUGE-1}&{\bf 95\% Confidence}\\
{\bf Code}&{\bf Score}&{\bf Interval}\\
\hline
\input{t2.latex.2}
\hline
\end{tabular}
&
\begin{tabular}[t]{|l|cc|}
%%\hline
%%\multicolumn{7}{|c|}{TASK 2}\\
\hline
\multicolumn{3}{|c|}{TASK 4}\\
\hline
{\bf Peer}&{\bf ROUGE-1}&{\bf 95\% Confidence}\\
{\bf Code}&{\bf Score}&{\bf Interval}\\
\hline
Y&0.4445&[0.4230,0.4660]\\
Z&0.4326&[0.4088,0.4565]\\
X&0.4293&[0.4068,0.4517]\\
W&0.4119&[0.3870,0.4368]\\
\hline
\multicolumn{3}{|c|}{Task 4a}\\
\hline
\input{t4a.latex.2}
\hline
\multicolumn{3}{|c|}{Task 4b}\\
\hline
\input{t4b.latex.2}
\hline
\end{tabular}
\end{tabular}
}
\end{center}
\caption{Summary of official ROUGE scores for DUC 2004 Tasks 2 and 4. Peer codes: manual
summaries [A-Z] and top five system submissions.
Systems numbered 144 and 145 are University of Michigan's submission.
144 uses LexRank in combination with Centroid whereas 145 uses Centroid alone.
}
\label{duc04-official}
\end{table}

\begin{table}[htp]
\center
\footnotesize{
\begin{tabular}{ll}
\begin{tabular}{|c|c|c|c|}
\hline
&\multicolumn{3}{|c|}{2003 Task2}\\
\cline{2-4}
&min&max&average\\
\hline
Centroid
&0.3502&0.3689&0.3617\\
\hline
Degree (t=0.1)
&0.3501&0.3650&0.3573\\
\hline
LexRank (t=0.1)
&0.3493&0.3677&0.3603\\
\hline
Cont. LexRank
&0.3564&0.3653&0.3621\\
\hline
\end{tabular}
&
\begin{tabular}{|c|c|c|c|}
\hline
&\multicolumn{3}{|c|}{2004 Task2}\\
\cline{2-4}
&min&max&average\\
\hline
Centroid
&0.3563&0.3732&0.3630\\
\hline
Degree (t=0.1)
&0.3495&0.3762&0.3622\\
\hline
LexRank (t=0.1)
&0.3512&0.3760&0.3663\\
\hline
Cont. LexRank
&0.3465&0.3808&0.3686\\
\hline
\end{tabular}\\
{
\begin{tabular}{lrl}
baselines: &random:& 0.2952\\
&lead-based: &0.3246
\end{tabular}
}
&
{
\begin{tabular}{lrl}
baselines: &random:& 0.3078\\
&lead-based: & 0.3418
\end{tabular}
}
\\
\multicolumn{1}{c}{\normalsize{(a)}}&
\multicolumn{1}{c}{\normalsize{(b)}}\\
&\\
&\\
\begin{tabular}{|c|c|c|c|}
\hline
&\multicolumn{3}{|c|}{2004 Task4a}\\
\cline{2-4}
&min&max&average\\
\hline
Centroid
&0.3706&0.3898&0.3761\\
\hline
Degree (t=0.1)
&0.3874&0.3943&0.3906\\
\hline
LexRank (t=0.1)
&0.3883&0.3992&0.3928\\
\hline
Cont. LexRank
&0.3889&0.3931&0.3908\\
\hline
\end{tabular}
&
\begin{tabular}{|c|c|c|c|}
\hline
&\multicolumn{3}{|c|}{2004 Task4b}\\
\cline{2-4}
&min&max&average\\
\hline
Centroid
&0.3754&0.3942&0.3906\\
\hline
Degree (t=0.1)
&0.3801&0.4090&0.3963\\
\hline
LexRank (t=0.1)
&0.3710&0.4022&0.3911\\
\hline
Cont. LexRank
&0.3700&0.4012&0.3905\\
\hline
\end{tabular}
\\
{
\begin{tabular}{lrl}
baselines: &random:& 0.3315\\
&lead-based: &0.3615
\end{tabular}
}
&
{
\begin{tabular}{lrl}
baselines: &random:& 0.3391\\
&lead-based: & 0.3430
\end{tabular}
}
\\
\multicolumn{1}{c}{\normalsize{(c)}}&
\multicolumn{1}{c}{\normalsize{(d)}}\\
\end{tabular}
}
\caption{ROUGE-1 scores for different MEAD policies on
17\% noisy DUC 2003 and 2004 data.}
\label{noisy}
\end{table}

\subsection{Experiments on Noisy Data}
The graph-based methods we have proposed consider a document cluster as a
whole. The centrality of a sentence is measured by looking
at the overall interaction of the sentence within the cluster rather
than the local value of the sentence in its document.
This is especially critical in generic summarization where
the information unrelated to the main theme of the cluster should
be excluded from the summary.
DUC data sets are perfectly clustered into related
documents by human assessors.
To observe the behavior of our methods on noisy data, 
we have added 2 random documents in each cluster taken from a different
cluster. 
Since originally each cluster contains 10 documents, this means a
$2/12$ (17\%) noise on the data sets.

The results on the noisy data are given in Table~\ref{noisy}.
The picture looks similar to Table~\ref{results} except for
lead-based and random baselines are more significantly
affected by the noise. The performance loss is quite small on
our graph-based centrality methods. A surprising point is that
centroid-based summarization also gives good results although
still worse than the others most of the time. 
This suggests that 17\% noise on the data is not enough to make
significant changes on the centroid of a cluster.

\section{Related Work}
There have been attempts for using graph-based ranking methods in
natural language applications before.  
\shortciteauthor{Salton&al.97} \citeyear{Salton&al.97} made one
of the first attempts of using degree centrality in single document
text summarization.
%Use of degree centrality in text summarization was first introduced
%in \cite{Salton&al.97}.
In the summarization approach of \citeauthor{Salton&al.97},
degree scores are used to extract the important paragraphs of a text.

\citeauthor{Moens99} \citeyear{Moens99} use cosine similarity
between the sentences to cluster a text into 
different topical regions.
A predefined cosine threshold is used to cluster paragraphs
around seed paragraphs (called \emph{medoids}).
Seed paragraphs are determined by maximizing the total
similarity between the seed and the other paragraphs in
a cluster.
The seed paragraphs are then considered as the 
representative descriptions of the corresponding subtopics,
and included in the summary.

\citeauthor{Zha02} \citeyear{Zha02} 
defines a bipartite graph from the set of terms
to the set of sentences.
There is an edge from a term $t$ to a sentence $s$
if $t$ occurs in $s$.
\citeauthor{Zha02} argues that the terms that appear
in many sentences with high salience scores should
have high salience scores, and the sentences
that contain many terms with high salience scores
should also have high salience scores.
This \emph{mutual reinforcement principal} reduces
to a solution for the singular vectors of the
transition matrix of the bipartite graph.

The work presented in this paper started with the 
implementation of LexRank with threshold on unweighted graphs.
This implementation was first used in the DUC 2004 evaluations
which was run in February 2004 and presented in May 2004
\cite{DUC04}.
After the DUC evaluations, a more detailed analysis and more careful
implementation of the method was presented together with a comparison 
against
degree centrality and centroid-based summarization
\shortcite{erkan-radev:2004:EMNLP}. 
Continuous LexRank
on weighted graphs first appeared in the initial version of
this paper submitted in July 2004.
An eigenvector centrality algorithm
on weighted graphs was independently proposed
by \citeauthor{mihalcea-tarau:2004:EMNLP} 
\citeyear{mihalcea-tarau:2004:EMNLP} for single-document
summarization.
\citeauthor{mihalcea:COLING04} \citeyear{mihalcea:COLING04} later
applied PageRank to another problem of
natural language processing, word sense disambiguation.

Unlike our system, the studies mentioned above
do not make use of any heuristic features of the
sentences other than the centrality score.
They do not also deal with the multi-document case.
One of the main problems with multi-document summarization is
the potential duplicate information coming from different documents,
which is less likely to occur in single-document summaries.
We try to avoid the repeated information in the summaries by
using the reranker of the MEAD system.
This problem is also addressed in \citeauthor{Salton&al.97}'s
work.
Instead of using a reranker, they
first segment the text into regions of different subtopics and then 
take at least one representative paragraph with the highest
degree value from each region.

To determine the similarity between two sentences, we have used 
the cosine
similarity metric that is based on word overlap and idf weighting.
However, there are more advanced techniques of assessing
similarity which are often used in the topical clustering of
documents or sentences \shortcite{simfinder,McKeown&al.01d}.
The similarity computation might be improved by incorporating more
features (e.g. synonym overlap, verb/argument structure overlap,
stem overlap) or mechanisms (e.g. coreference resolution,
paraphrasing) into the system.
These improvements are orthogonal to our model in this paper and
can be easily integrated into the similarity relation.

\section{Conclusion}
We have presented a new approach to define sentence salience based on
graph-based centrality scoring of sentences.  Constructing the
similarity graph of sentences provides us with a better view of
\emph{important} sentences compared to the centroid approach, which is
prone to over-generalization of the information in a document cluster.
We have introduced three different methods for computing centrality in
similarity graphs.  The results of applying these methods on
extractive summarization are quite promising. Even the simplest
approach we have taken, degree centrality, is a good enough heuristic
to perform better than lead-based and centroid-based summaries.  In
LexRank, we have tried to make use of more of the information in the
graph, and got even better results in most of the cases.  Lastly, we
have shown that our methods are quite insensitive to noisy data that
often occurs as a result of imperfect topical document clustering
algorithms.

The graph-based representation of the relations between natural
language constructs provides us with many new ways of information
processing with applications to several problems such as document
clustering, word sense disambiguation, prepositional phrase
attachment.  The similarity relation we used to construct the graphs
can be replaced by any mutual information relation between natural
language entities.  We are currently working on using random walks on
bipartite graphs (binary features on the left, objects to be
classified on the right) for semi-supervised classification. For
example, objects can be email messages and a binary feature may be
``does the subject line of this message contain the word {\em
money}''. All objects are linked to the features that apply to them. A
path through the graph can then go from an unlabeled object to a set
of labeled ones going through a sequence of other objects and
features. In traditional supervised or semi-supervised learning, one
could not make effective use of the features solely associated with
unlabeled examples. In this framework, these features serve as
intermediate nodes on a path from unlabeled to labeled nodes. An
eigenvector centrality method can then associate a probability with
each object (labeled or unlabeled). That probability can then in turn
be interpreted as belief in the classification of the object (e.g.,
there is an 87\% per cent chance that this particular email message is
spam). In an active learning setting, one can also choose 
what label to request next from an Oracle given the eigenvector
centrality values of all objects.

\section*{Acknowledgments}
We would like to thank Mark Newman for providing some useful
references for this paper. Thanks also go to Lillian Lee for her very
helpful comments on an earlier version of this paper. Finally, we
would like to thank the members of the CLAIR (Computational
Linguistics And Information Retrieval) group at the University of
Michigan, in particular Siwei Shen, for their assistance with this
project.

This work was partially supported by the National Science Foundation
under grant 0329043 ``Probabilistic and link-based Methods for
Exploiting Very Large Textual Repositories'' administered through the
IDM program. All opinions, findings, conclusions, and recommendations
in this paper are made by the authors and do not necessarily reflect
the views of the National Science Foundation.

\bibliography{refs}
\bibliographystyle{theapa}
\end{document}
