Conventional keyphrase extraction algorithms are applied to a fixed corpus of lengthy documents where keyphrases distinguish documents from each other. However, with the emergence of social networks and microblogs, the nature of such documents has changed. Documents are now of short length and evolve topics which require specific algorithms to capture all features. In this paper, we propose a hypergraphbased ranking algorithm that models all the features in a random walk approach. Our random walk approach uses weights of both hyperedges and vertices to model short documents' temporal and social features, as well as discriminative weights for word features respectively, while measuring the centrality of words in the hypergraph. We empirically test the effectiveness of our approach in two different data sets of short documents and show that our approach has an improvement of 14% to 25% in precision over the closest baseline in a Twitter data set and 10% to 27% in the Opinosis data set.
I.2.7 [ARTIFICIAL INTELLIGENCE]: Natural Language Processing—Text analysis
Short text messages are ubiquitous nowadays in social networks and across the web. Regardless of the length limitation, the size restriction did not limit the popularity of PCeorpmyirsisgihont tco m20ak1e4 dhieglidtalbyorahuatrhdocro(sp)i/eoswonfearl(ls)o;r cpoaprtyionfgthpiserwmoitrktefdor poenrlsyonfoarl oprricvlaatsesraonodmaucsaediesmgircanptuedrpwositehso.ut fee provided that copies are nPoutbmliashdeedoradsipstarirbtuotefdthfoer#prMofiticorrocpoomstms2e0rc1i4al Wadovraknsthaogpe apnrdoctheeadticnogpsi,es baveaariltahbislenotice anadstCheEfUulRlcVitoatli-o1n14o1n (thhet tfirpst:/p/acgeeu.rT-owsco.oprygo/tVhoelr-w1i1se4,1)to online republish, to post on servers or to redistribute to lists, requires prior specific p#eMrmicisrsoiponosatnsd2/0o1r4a, fAeep.ril 7th, 2014, Seoul, Korea.
Copyright 20XX ACM X-XXXXX-XX-X/XX/XX ...$15.00. social interaction through such messages. Twitter, for instance, has more than 200 million active users each month1. Such high popularity necessitates ranking systems capable of measuring the importance of keywords and keyphrases within such limited length to facilitate search, indexing, and detecting trends. By finding salient terms, tasks such as summarization and text visualization become feasible. However, the dynamic nature of social microblogs makes ranking a non-trivial task.
Microblogs have a dynamically changing content that needs specially designed algorithms for keyphrase extraction. Descriptive keyphrases are keyphrases that signify topics in a document and help differentiate it from other documents in the corpus. However, the social aspects and evolution of topics in a social media genre make it rather difficult to find keyphrases. Most keyphrase extraction algorithms do not account for the temporal and social attributes when finding keyphrases since they are designed for static documents corpora. Therefore, a number of interesting research questions arise in social microblogs where topics change frequently. If the content is dynamically changing, then can we rely on conventional keyphrases extraction approaches? How can we account for the temporal and social attributes in social media for keyphrase extraction?
In this article, we present a hypergraph-based algorithm, called HG-Rank, that is capable of modeling temporal and social aspects in addition to discriminative weights. A hypergraph is a generalization of graphs were edges have a set of vertices (called hyperedges) instead of two nodes. We define a lexical hypergraph where vertices are distinct words and hyperedges are short documents that contain the words. We model the temporal and social attributes of documents as hyperedge weights to reflect the attributes over the document’s keywords, and we model discriminative term weights as vertex weights to give the model the ability of recognizing topical terms. We design a weighted random walk over the hypergraph to measure the centrality of keywords taken into account all the aforementioned features.
To rank vertices in a hypergraph, we generalize a
probabilistic random walk suitable for a weighted hypergraph
structure. The surfer considers the weights of both
vertices and hyperedges for transitioning. The intuition is that
the surfer will prefer words that has the following
properties. The words belong to a recent document, and they
exist in a document that has attracted social users, for
in1https://twitter.com/twitter/status/281051652235087872
keyphrase ranking over hypergraphs based on Zhou et al.[
Let HG(V, E) be a hypergraph with the vertex set V and the set of hyperedges E. A hyperedge e is a subset of V where ∪e∈E e = V . Let HG(V, E, w) be a weighted hypergraph where w : E → R+ is the hyperedge weight. A hyperedge e is said to be incident with v when v ∈ e. A hypergraph has an incidence matrix H ∈ R|V |×|E| as follows: The vertex and hyperedge degree are defined as follows: h(v, e) = (1 if v ∈ e
0 if v ∈/ e d(v) =
X w(e)h(v, e) δ(e) =
X h(v, e) = |e| e∈E v∈V stance re-tweet in Twitter. Additionally, the surfer will prefer topically discriminative words capable of finding accurate keyphrases.
The contribution of this paper can be summarized as follows: • We propose a new hypergraph approach to jointly model temporal and social features within the hypergraph structure. This model is capable of recognizing the importance of time and social features that are important in a dynamic genre. • The hypergraph-based HG-Rank algorithm is the first graph-based approach for keyphrase extraction that considers the high-order relation between words instead of a pair-wise relation as in conventional graphbased keyphrase extraction. • We evaluate our approach with two different data sets Twitter and Opinosis. We show the effect of each dimension on the task of keyphrase extraction.
The rest of the paper is organized as follows. A discussion of the related work is in Section 2. We define the hypergraph notation needed for explaining the proposed approach in Section 3. The proposed approach will be thoroughly explained in Section 4. Section 5 will describe the data and experimental results. The paper conclusion is in Section 6. 2.
Our work is related to three different research areas, namely: temporal and social aspects for keyphrase extraction, graphbased keyphrase extraction, and hypergraphs. This work bridges such areas for the task of keyphrase extraction in a unified framework.
The emergence of social networks has motivated researchers
to examine the inclusion of temporal and social dimensions
into search [
A number of graph-based keyphrase extraction approaches
have been proposed. TextRank[
Hypergraph random walks have been proposed in [
De and Dv are the diagonal matrices representing the degrees of hyperedges and vertices, respectively. We is the diagonal matrix with the hyperedge weights. 4.
The HG-Rank model captures keyphrases using a hypergraph structure where it is possible to inherently model social and temporal features. These features are embedded as a hyperedge weight that represents a specific short document. In essence, we model each short text document di as a bag-of-words model with distinct keywords di = {k1, k2, ..., ks}. A collection of documents Di = {d1, d2, ..., dn} is then represented as a lexical hypergraph in the following manner. We represent each short document as a hyperedge, and each keyword as a distinct vertex.
In this section, we will describe the HG-Rank algorithm in more depth. First, the calculation and insertion of the temporal and social attributes is going to be explained. Second, the vertex weights will be explained. Third, we will define the random walk ranking approach on the lexical hypergraph to rank keywords. Finally, we will discuss our approach on extracting keyphrases. 4.1
Temporal attributes in a dynamic genre as a
microblogging social network or news trends is an important
dimension to understand evolving topics and keyphrases. We
measure the temporal effect as a ranking function for short
documents. The more recent the document, the higher the
temporal rank will be. Similar to [
Rtime(di) = Q(c−yi)/24 (4) Where c and yi denote the current time and the document di publication time, respectively. (c − yi) is the time interval between current and publication time in hours. We divide by 24 to show the difference of publication time and current time in number of days. Q is a decay rate parameter with values 0 < Q < 1. Moreover, the Q value is inversely proportional to favoring recent documents. When Q is closer to 0, the ranking favors very recent documents over old ones. On the other hand, when Q is closer to 1, the ranking is less focused on new documents. In our experiments, we set Q to 0.5.
For the social effect, we measure the social dimension of documents as a ranking function. The more popular or shared the document, the higher the social rank will be. For example in Twitter, tweets that are re-tweeted frequently should be more important than a tweet without re-tweets. This is similar to other social networks with the ”like” feature as in Facebook or product reviews. We calculate the social ranking as follows:
Rsocial(di) =
si + 1 Pe se + 1 (5) Where si is the counter of social feature (counts of re-tweet or likes) for document di. Pe se is the sum of all social features across all documents (total number of re-tweets for example). Moreover, we added one smoothing to avoid canceling out documents with no social attributes.
Now we tie both temporal and social features together in one ranking function as follows: w(di) = λRsocial(di) + (1 − λ)Rtime(di) (6) λ is a smoothing parameter with 0 < λ < 1 to trade off the effect of temporal aspects and social aspects. We experimented with different values for λ which will be discussed in the experiment section. The final documents rank w(di) will be embedded in the hypergraph as a hyperedge weight to reflect documents’ importance over keywords. The intuition behind embedding temporal and social features in the ranking scheme is that they are essential for capturing keyphrases in a dynamic genre. In a dynamic genre, as in Twitter, the content rapidly changes with time. Hence, the keyphrases tend to change as well. Conventional keyphrase extraction algorithms do not consider the time dimension in finding keyphrases which make them insufficient for the task. Moreover, the social aspect is important to capture keyphrases of trendy topics that social network users find interesting. An interesting topic in social media will more likely be searched compared to other topics which makes it important to find its keyphrases. We will discuss vertex weights in the next section. 4.2
Graph-based approaches base the ranking on the relational structure of co-occurring words. Such ranking is great on capturing the semantic relation between words. However, there is no evidence that graph-based ranking approaches are able to capture discriminative words. To enhance the hypergraph-based ranking algorithm, we use a discriminative weighting scheme tf-idf as vertex weights before we start the random walk. This injection of tf-idf weights will add a discriminative perspective for calculating the rank though a random walk approach. However, when applied to short text documents, tf-idf fails to capture descriptive terms due to sparsity of features (short length). To circumvent the sparsity problem, we aggregate short documents to a virtual larger ones and then calculate tf-idf scores. A larger virtual document δ is the concatenation of smaller documents d which is δt = {d1 + d2 + ... + dn}. In Section 5.3, different approaches for aggregation are described in more depth. We measure the normalized tf-idf over the larger documents being the set of D = {δ1, δ2, ..., δn}. The tf-idf is measured as follows: w(vi)tf-idf = tf (vi)
Nw · log
N df (vi) (7) Where tf (vi) as the term frequency on the document δ and Nw is sum of all words occurrences in document δ for normalization. N is the number of documents in the larger document set D, and df (vi) is the number of larger documents in D that contain the term vi. We will discuss the hypergraph ranking algorithm HG-Rank in detail in the next section. 4.3
To rank vertices in a hypergraph, we generalize a random walk process for hypergraphs. A random walk process is the transitioning between vertices in a graph by starting at a given vertex and moving to another neighboring vertex after each discrete time step t. We can imagine vertices as a set of states {s1, s2, ..., sn} and the transitioning to be a finite Markov chain M over these states. The transition probability calculated as P (u, v) = P rob(st+1 = v|st = u) which means that the chain M will be at v at time t + 1 given that it was observed at u at time t. The Markov chain herein is homogeneous which means that the transition probability is independent of time t. Note that for any vertex u we have Pv P (u, v) = 1. Since M is homogeneous with probabilities computed over only a single transition, we can then define a transition matrix P ∈ R|V |×|V | for all moves. The transition matrix P captures the transition between vertices which shows the behavior of a surfer randomly moving between vertices according to such probabilities. Next we will show how we define the random walk in hypergraphs.
In simple graphs2, the random walk process is clear by simply choosing an edge with a probability to a destination vertex. However, it is not the case in hypergraphs where the structure of the graph is substantially different demanding a more general walk. For instance, in a hypergraph, a hyperedge could have more than two end-point vertices δ(e) ≥ 2. To generalize the random walk process in hypergraphs, we model the walk as the transition between two vertices that are incident to each other in a hyperedge instead of a normal edge. In essence, the random walk is seen to be a two-step process, instead of one, which is the following: the random surfer first chooses a hyperedge e incident with the current vertex u. Then the surfer picks a destination vertex v within the chosen hyperedge satisfying the following u, v ∈ e. The 2By simple graphs, we mean graphs (not hypergraphs) with edges that are unique pair of vertices. Not to be confused with simple vs. multigraph random walk in hypergraph is said to be more general since the random walk in a normal graph is a special case where there is only a single destination vertex v associated with a given normal edge incident with u where in a hypergraph we can have more vertices to choose from. The hypergraph random walk process can be defined as a Markov chain where the vertex set is the state set of the chain similar to a normal graph. At each time step t the surfer moves in the incident hyperedge to another vertex.
In this paper, we try to seek a general definition of a random walk in a weighted hypergraph where not only hyperedges have weights, but vertices as well. In such a case, the random walk process is extended to leverage both hyperedges’ and vertices’ weights. We define the vertex’s weight across all incident hyperedges to be a feature vector ~vw = {w(ve1), w(ve2), ..., w(vd(v))} (8) Where we have a different vertex’s weight for every hyperedge e that contain vertex v. We describe the proposed random walk process as the following. Starting from a vertex u, the surfer chooses a hyperedge e incident with u proportional to the hyperedge weight w(e). Then, the surfer, also chooses a vertex v proportional to the vertex weight within the hyperedge where we consider the weight in the current hyperedge only. Let us define a weighted hypergraph incident matrix Hw ∈ R|V |×|E| where we have the following: hw(v, e) = (w(ve) if v ∈ e 0
if v ∈/ e δ(ew) =
X hw(v, e) v∈V
Therefore, we redefine the hyperedge degree to be as follows: (9) (10) (11) We can now calculate the transition matrix P as follows: P (u, v) = e∈E X w(e) P h(u, e)
hw(v, e) eˆ∈E(u) w(eˆ) Pvˆ∈e hw(vˆ, e) Or in matrix notation:
P = Dv−1HWeDv−e1HwT
Where hw(v, e) is the weight of the destination vertex v in hyperedge e. Dv is the diagonal matrix of the weighted degree of vertices as in formula 2. We is the diagonal matrix of the hyperedge weights. Dve is the diagonal matrix for weighted degree of hyperedges as in formula 10. Note that the transition matrix P is stochastic where we have every row sums to 1.
After calculating the transition matrix P , we now explain the stationary distribution π of a random walk. The stationary distribution can be calculated by starting with initial column vector ~v0 ∈ R|V |×1 with equal probabilities 1/|V | summing to 1. We first multiply the transition matrix P T (where P T is a column stochastic matrix for clarity) by the initial column vector ~v0 yielding ~v1 = P T ~v0. Then, we iterate until the vector ~v stops changing. The reason of multiplying the probability distribution vector ~v by the transition matrix P T gives us the next step distribution ~x = P T ~v can be explained as follows. Let xi be the probability of being at the current vertex i. Then we have the following: xi = Pj pij vj where vj being the probability of the surfer being at node j previously, and pij is the probability of moving from j to i.
The probability distribution vector ~v stops changing after
n steps if the random walk is ergodic. A random walk is
ergodic when the following conditions are met: 1) the chain
is irreducible, for any two states si, sj ∈ M they must
satisfy P (si, sj ) > 0. Also, 2) the chain is aperiodic, where the
greatest common divisor of every state {t : Pt(si, si) > 0}
is 1. To guarantee irreducibility and aperiodicity, we use
the PageRank algorithm [
~v(i+1) = αP T ~v(i) + (1 − α)~e/n (12) The damping factor α is set to 0.85. n is the number of nodes in the graph. ~e ∈ Rn×1 is a vector of all elements being 1. αP T ~v means that the random walker will choose to go with one of the incident hyperedges. (1 − α)~e/n represents a vector of an introductory probabilities with each entry being (1 − α)/n to teleport the random walk to a new node. 4.4
We tag keywords with their Part of Speech (POS) tags.
Then, we extract keyphrases that are noun phrases since it
has been shown that most keyphrases annotated by human
happen to be noun phrases[
R(ph) = X R(ki) ki∈ph (13) However, such approach will be biased towards longer phrases. To overcome such bias, we normalized based on the length of the keyphrase as follows:
R(ph) = Pki∈ph R(ki) (14) n Where n is the keyphrase length. Moreover, we removed phrases that cross over syntactic boundaries as they cannot be a comprehensible keyphrase. We also removed any keyphrase that appears less than f times. We experimented with different values of f and found out that f = 5 shows the best keyphrases in our data. Next we will describe the experimental design in depth and all comparisons. 5.
This section explains the experimental setup for the hypergraph ranking framework HG-Rank. The effectiveness of our approach is demonstrated by conducting several experiments comparing our method to different baselines. First, the data sets used in this experiment are explained thoroughly. Second, the necessary preprocessing steps are illustrated in detail. Third, the experimental setup is laid out. Fourth, the experimental results and discussion of results are discussed and examined. 5.1
We used two different data sets that contain only short
text documents. The characteristics of the two data sets are
explained as the following:
• Twitter. We collected a corpus of tweets which
contains 80,231 tweet posts. We collected tweets in the
time frame from April 1, 2013 to April 30, 2013. We
filter out all non-Latin characters tweets. Afterwards, we
deleted any non-English tweets by classifying a tweet
to be non-English if there is less than 5 English words.
Moreover, we discarded any tweet with less than 3
words as it does not show any topic relevance.
Moreover, the corpus contains 19,613 hashtags in total.
• Opinosis. We used a public short reviews data set
called Opinosis3 collected by Ganesan et al.[
Preprocessing is an essential step in text mining tasks
in general. In extracting keyphrases, the preprocessing is
needed to measure the salient scores accurately. The amount
of preprocessing differs significantly depending on the genre
of the corpus. In a social microblogging environment as
in Twitter, the preprocessing step is of a vital importance.
The challenge with colloquial textual content is an enormous
obstacle in performing keyphrase extraction with Twitter
posts. For instance, tweets can have misspelled words, strange
capitalization, and wrong punctuations. For more detail we
refer the reader to Eisenstein’s survey on languages in social
media [
We first removed any URL links from tweets since we are focusing on the textual content. Moreover, we also removed emoticons and smileys since they do not have any topical relevance. Also, Twitter’s special characters and usernames were removed as in the preceding hashtag sign # and usernames with @username. Tweets that start with the @username are generally considered replies and have a conversational nature more than topical nature. Therefore, we have removed any tweet that starts with @username to focus on topical tweets only. Another challenge is the usage of Internet phrasal abbreviation such as LOL (laugh out loud), ikr (I know right). We leverage the Internet Slang5 dictionary in an effort to transform the text to standard English. All the aforementioned techniques can help improve the accuracy of the POS tagger. 3http://kavita-ganesan.com/opinosis-opinion-dataset 4www.mturk.com 5http://www.noslang.com/dictionary/full/
Syntactical tagging, as in POS, for conversational content
found on tweets can be very difficult. Most standard
taggers fail to correctly tag colloquial text. For instance, the
misuse of capitalization can make the tagger incorrectly tag
nouns or verbs as a proper noun simply because the token
is out of the vocabulary OOV. To tackle such difficulties,
we have leveraged a state-of-the-art POS tagger6 designed
specifically for tweets [
The final step of preprocessing was to remove all stopwords from tweets since they do not have any topical influence. Punctuations were removed as well. Moreover, all capitalized tokens were converted to lower case. We lastly stemmed the tokens to get an accurate feature measure of words. We used the Porter stemmer7 to stem our corpus.
For the Opinosis data set, we removed stopwords, punctuations, and stemmed the text. We also convert the tokens to lower case. 5.3
In this section, we will describe the experimental setup that was used for both data sets to compare our model with other baselines. First, we will describe the setup used for the Twitter data set. Then, we will explain the setup for the Opinosis review data.
Since there is no apparent golden labels to test against
with tweets, we designed an empirical experiment to test
keyphrase extraction in tweets. The experiment can be
designed into different steps 1) Identify major topics in
documents (tweets). 2) Test if any top ranked phrase represents
a major topic in documents. The intuition behind the
approach is the fact that phrases are descriptive of a document
if they explain an important topic within that document.
Given that keyphrases describe the major topics in a
document, we will leverage a statistical topic model known as
latent Dirichlet allocation (LDA)[
LDA is a generative statistical model that helps finding a set of unobserved groups using some observed sets. When applied to text, the observed sets are words in documents where the unobserved groups (latent) are topics of co-occurring words. By finding the mixture of topics using statistical inference as in Gibbes sampling, we get two posterior distribution P (w|k) the probability of words under each topic, and P (k|d) the probability of topics under each document. We first start by assigning each word to a K topic. Then, for each word w in each document d, we resample the 6http://www.ark.cs.cmu.edu/TweetNLP/ 7http://tartarus.org/martin/PorterStemmer/ ● LDA Agg
Normal LDA ● 5 ● 6
Number of Topics
Where P (wi|ks) is the probability of the word wi being
assigned topic ks from all documents. P (ks|d) is the
probability of words in the document d that are assigned to topic
ks. However, when applied to short length documents as
in tweets, a new challenge arises since there is not enough
observed sets (words) in each document to infer latent
topics. Therefore, we remodel the documents structure to
improve LDA in our data and get meaningful topics. Given
a collection of tweets Ti = {τ1, τ2, ..., τn}, there is an
abundant number of hashtags Hi = {h1, h2, ..., hn} appearing in
tweets. Instead of treating each tweet as a document, we
aggregate tweets using hashtags to form a large virtual
document for each hashtag dh = {τ1h+τ2h+...+τnh} where each
dh is a concatenation of tweets. Therefore, the documents
set will be defined as Dh = {dh1, dh2, ..., dhn} containing all
words from a large group of tweets for each document. After
enhancing the document representation, we can apply LDA
to learn topics and their posterior ranking more efficiently.
In Figure 1, we show a significant improvement in perplexity
for the two LDA approaches with short documents and
aggregated documents. In Table 1, we show the top 10 ranked
word for |K| = 5. Similar approaches for improving LDA in
short text documents are found in [
To test the hypergraph ranking, we would need to have a reference set that summarize topics within each dh document. The idea is to use a search engine by using the top words, from LDA, for each topic as a query. We used Google to generate the result snippets by setting the search at the same duration as the tweets which is April, 2013. Once the search snippets (top 50 snippet) for each topic is collected, we store them. Then we assign each document to its major topics only. For instance, any topic that is higher than P (k|d) = 0.5 is considered a major topic and is then chosen. Those search results collected from the major topics are considered references. We, then, search for keyphrases in those topical references. If a keyphrase is included in a snippet of any major topic, we consider it a hit, otherwise it is a miss.
For the Opinosis review data, we compared the extracted keyphrases from short review documents with the golden summaries provided with the data set. We consider a keyphrase correct if it appears in any short golden summary. There is approximately 5 golden summaries for each topic. Due to the short length of documents, we only used bigrams for evaluation.
A number of different baseline algorithms are implemented
and used to test the validity of the proposed approach:
• tf-idf each post is a document, and each topic
collection is a reference corpus.
• TextRank[
To compare all the baselines used in this experiment, we quantitatively measure their performance using a precision evaluation metric. We compare them to the golden labels defined in the previous section. Specifically, we consider the keyphrase to be correct if it appears in the golden set. Precision helps identify the accuracy of the extracted results. Since we are evaluating a ranking system, we measure precision at the top 10, 15, and 20 ranked keyphrases. Precision is measured as follows:
P recision =
(16) Social and Temporal Parameter ● 20 ● 25 Where Kcorrect is the number of correctly extracted keyphrase, and Kextracted is the total number of extracted keyphrase. In the following, we will discuss the experimental results with balancing social and temporal attributes and how it affect the ranking. Then, we will describe the improvements HG-Rank has over other approaches.
However, precision only considers how many correctly
extracted keyphrases within the result regardless of the
order within the top list of extracted keyphrases. Therefore,
we also measure the Binary Preference Measure Bpref [
r∈R Bpref = 1 X 1 − |n ranked higher than r|
R R (17) where R is the number of correct keywords within extracted keywords in a method, and where r is a correct keyword and n is incorrect keyword.
To examine the effect of social and temporal attributes when combined into the hypergraph ranking scheme, we experimented with different values for λ in formula 6. By varying the value of λ, we can analyze the tradeoff between the two attributes in precision. Figure 2 shows the different λ values experimented with. The best value for λ is 0.5 which means equal contribution of temporal and social features in our data. It is interesting to notice that when λ = 1, meaning only social attributes were taken into the ranking, the performance deteriorates considerably. It could mean that popular content is not necessary of a topical value to the corpus. However, more experiments are needed to widen our understanding of what the best features are for topical keyphrase extraction in a dynamic genre as Twitter. Next, we move on to describe the full evaluation of both data sets.
To evaluate the ranking performance for all baselines, we performed the evaluation measure for both data sets as the following. For Twitter, we first build the lexical hypergraph for each hashtag topic corpus dh = {τ1h + τ2h + ... + τnh}. We chose the top 5 frequent topical hashtags and performed keyphrase extraction separately. We measured the precision and Bpref for each topic. In table 2, we show the average precision from all topics. Table 4 shows the average Bpref for the Twitter data. In the Opinosis review data set, we build .10 ● λ = 0
λ = 0.5 ● λλ == 10.8 the lexical hypergraph for each topic. Since there is no meta data with the reviews as time or social features, we regard the hyperedge weight to be 1 for all short documents to test the hypergraph ranking only. We chose 3 topics mentioned early to quantitatively measure the improvements. We show the average precision of three topics in table 3, and average Bpref in table 5.
In the Twitter data, the proposed hypergraph-based
approach HG-Rank out performed all other baselines.
Specifically, HG-Rank improved the results in the top 10 results
over closest baseline, NE-Rank, by 14% and 7%
improvements using precision and Bpref, respectively. The
improvement shows the importance of modeling the high-order
cooccurring relationship using a lexical hypergraph compared
to modeling just a pair of words for graph edges. Moreover,
the temporally-aware ranking HG-Rank showed
improvement over other temporal-aware approaches as in
TimedTextRank[
For the Opinosis data, HG-Rank showed improvement over all baselines as well. Improvements in the top 10 over the second best baseline, NE-Rank, were 10% in precision and 14% in Bpref. Moreover, similar improvements were found in the top 15 and top 20 keyphrases. Even though no hyperedge weights were used for this data set as in temporal and social attributes, the hypergraph model has shown to increase both precision and Bpref scores which shows the robustness of the proposed model in modeling high-order co-occurrence relation between words.
In this paper, we have proposed a hypergraph-based ranking algorithm suitable for short text documents in social media genre. We modeled distinct keywords as vertices and their short documents as hyperedges in a lexical hypergraph. Moreover, we jointly modeled temporal and social features in the hypergraph to adapt keyphrase extraction with the dynamic nature of social media. Additionally, we supplemented the hypergraph with discriminative weights in the vertices to enhance the random walk approach. Then we proposed a new probabilistic random walk that considers both vertices and hyperedges weights over hypergraph. We have leveraged a state-of-the-art POS tagger for Twitter data to capture syntactic tags accurately from the noisy text. We demonstrated the effectiveness of our hypergraph approach over two data sets which showed promising results.
In the future work, we plan to extend the approach to a streaming algorithm where the hypergraph can be updated periodically.