Adaptive Faceted Search on Twitter

Abstract

In the last few years, Twitter has become a powerful tool for publishing and discussing information. Yet, content exploration in Twitter requires substantial e orts and users often have to scan information streams by hand. In this paper, we approach this problem by means of faceted search. We propose strategies for inferring facets and facet values on Twitter by enriching the semantics of individual Twitter messages and present di erent methods, including personalized and context-adaptive methods, for making faceted search on Twitter more e ective.

Keywords

• faceted search
• twitter
• semantic enrichment
• adaptation

1 Introduction

Twitter is a Social Web phenomenon that is attracting interest from people all around the world for a variety of di erent purposes [ 1 ], such as consuming and propagating news [ 2 ], crisis management [ 3 ] or communication with other people [ 4 ]. Over the last few years, Twitter has shown an exponential growth and became the most popular microblogging site with several hundreds of millions of users and more than 50 million Twitter messages (tweets) per day3. Highly active users regularly receive thousands of tweets every day [ 5 ]. This information overload may cause users to get lost in the information network, become demotivated and frustrated. Finding your way around Twitter is indeed not very straightforward due to the lack of a user-friendly browsing option that goes beyond the existing chronologically-ordered clutter option [ 5, 6 ].

Recently, researchers started to study strategies for recommending URLs [ 7 ], news articles [ 8 ] or entire conversations on Twitter [ 9 ]. However, search on Twitter has not been studied extensively yet which motivates, for example, the TREC 2011 track on Microblogs that de nes rst search tasks on Twitter4. In line with the TREC research objectives, we investigate ways to enhance search and content exploration in the microblogosphere by means of faceted search.

Traditional faceted search interfaces allow users to search for items by specifying queries regarding di erent dimensions and properties of the items (facets) [ 10 ]. For example, online stores such as eBay5 or Amazon6 enable end-users to narrow down their search for products by specifying constraints regarding facets such as the price, the category or the producer of a product. In contrast, information on Twitter is rather unstructured. Tweets are short text messages that do not explicitly feature facets. How can facets be extracted from tweets and how can we design appropriate faceted search strategies on Twitter? In this paper, we answer these questions and introduce an adaptive faceted search framework for Twitter. Our main contributions can be summarized as follows.

Semantic Enrichment We present methods for enriching the semantics of tweets by extracting facets (entities and topics) from tweets and related external Web resources.

User and Context Modeling Given the semantically enriched tweets, we propose user and context modeling strategies that identify (current) interests of a given Twitter user and allow for contextualizing the demands of this user. Adaptive Faceted Search We introduce faceted search strategies for content exploration on Twitter and propose methods that adapt to the interests and context of a user. 2

Faceted Search on Twitter

On Twitter, facets describe properties of a Twitter message. For example, persons that are mentioned in a tweet or events a tweet refers to. Oren et al. [ 10 ] formulate the problem of faceted search in RDF terminology. Given an RDF statement (subject; predicate; object), the faceted search engine interprets (i) the subject as the actual resource that should be returned by the engine, (ii) the predicate as the facet type and (iii) the object as the facet value (restriction value). A faceted query (facet-value pair) that is sent to a faceted search engine thus consists of a predicate and an object. We follow this problem formulation proposed by Oren et al. [ 10 ] and interpret tweets as the actual resources the faceted search engine should return. If a tweet (subject) mentions an entity then the type of the entity is considered as facet type (predicate) and the actual identi er of the entity is considered as facet value (object). For example, given a tweet t that refers to the tennis player \Federer", the corresponding URI of the entity (U RIfederer) and the URI of the entity type (U RIperson) are used to describe the tweet by means of an RDF statement: (t; U RIperson; U RIfederer).

Figure 1(a) illustrates how we envision the corresponding faceted search interface that allows users to formulate faceted queries. Given a list of facet values which are grouped around facet types such as locations, persons and events, users can select facet-value pairs such as (U RIevent; U RIwimbeldon) to re ne their current query (see top right in Fig. 1(a): (U RIperson; U RIfederer), (U RIsportsgame; U RItennis)). A faceted query thus may consist of several facetvalue pairs. Only those tweets that match all facet-value constraints will be returned to the user. The ranking of the tweets that match a faceted query is a research problem of its own and could be solved by exploiting the popularity of tweets { e.g. measured via the number of re-tweets or via the popularity of the user who published the tweet (cf. [ 11 ]). The core challenge of the faceted search interface is to support the facet-value selection as good as possible. Hence, the !"#$%&'() *+""*#) ,-./)*0") !"#$% 1$--"'*) 2$"-3) -.#/,/0)) 12/$3)

Faceted Search Engine

Semantic Enrichment facet extraction linkage User and Context Modeling profile generation relation learning Adaptive Faceted Search facet ranking query suggestion !"#$%&'%()*%+,+) )"'44 )#"8 " 3 / )*7 1"./ 156" ! ))%*#1566""$9 !"##$%&'("$#)*' 0$1$#$#' B$%%2,' +$,"-&,*' ./'0$1$#$#'1$-23$#,'4%5&6$#'7%124%' 8$-,'92%':5#'62,':4%,'6;<*==>55/ /' ?/'0$1$#$#'@A'B5'82%%2%>'C&4#&D' 849#2%E4F'G$-H$#'02>6&'I4JE'6;/ /' K/'7,'0$1$#$#',L-'14L%>':5#M$#' <#5:$,,25%4-'&$%%2,'<-4)$#'G2#E4'/ /' N/'+5>$#'0$1$#$#'3,'O#%4"1'!-$M$%&' K#1'+5"%1*'82MP-$15%'?Q.Q'R'6&/ /' S/  0$1$#$#F'TU5E532J'4%1'+5112JE'

#$4J6'&62#1'#5"%1'6;<*==P2&/-)=:/ /' V/  8$#$')5"',"#<#2,$1'96$%'

0$1$#$#'-5,&'&6$'W/C/'@<$%X*Y$,/ /' Z/  02#,&'M4U5#'&5"#%4M$%&'4[$#'&6$'

@H'5<$%/'0$1$#$#'4%1'TU5E532J'/ /' \/  865'&62%E,'&64&'+5>$#'0$1$#$#'2,' (a) Faceted search interface (b) Faceted search architecture facet-value pairs that are presented in the faceted search interface (see left in Figure 1(a)) have to be ranked so that users can quickly narrow down the search result lists until they nd the tweets they are interested in. Therefore, the facet ranking problem can be de ned as follows.

De nition 1 (Facet Ranking Problem). Given the current query Fquery, which is a set of facet-value pairs (predicate; object) 2 Fquery, the hit list H of resources that match the current query, a set of candidate facet-value pairs (predicate; object) 2 F and a user u, who is searching for a resource t via the faceted search interface, the core challenge of the faceted search engine is to rank the facet-value pairs F . Those pairs should appear at the top of the ranking that restrict the hit list H so that u can retrieve t with the least possible e ort. The e ort, which u has to invest to narrow down the search result list H, can be measured by click and scroll operations (e.g. the number of facet-value pair selections). Our goal is to provide a faceted search interface that minimizes the e ort a user has to invest in retrieving the tweets in which the user is interested in. Query suggestions and ranking facet-value pairs according to the current demands of a user are therefore essential and will be discussed in the next section. 2.1

Architecture for Adaptive Faceted Search on Twitter Semantic Enrichment The semantic enrichment layer aims to extract facets from tweets and generate RDF statements that describe the facet-value pairs which are associated with a Twitter message. In particular, each tweet is processed to identify entities (facet values) that are mentioned in the message. We therefore make use of the OpenCalais API7, which allows for the extraction of 39 di erent types of entities (facet types) including persons, organizations, countries, cities and events. As Twitter messages are limited to 140 characters, the extraction of entities from tweets is a non-trivial problem. Thus, we introduced a set of strategies that link tweets with external Web resources (news 7 http://www.opencalais.com/ articles) and propagate the semantics extracted from these resources to the related tweets, which is explained in detail in [ 8 ]. For example, given a tweet \This is great http://bit.ly/2fRds1t", we extract entities from the referenced resource (http://bit.ly/2fRds1t) and attach the extracted entities to the tweet. User and Context Modeling In order to adapt the facet ranking to the people who are using the faceted search engine, we propose user modeling and context modeling strategies. The user modeling strategies model the interests of the users in certain facet values (entities and topics). We therefore exploit the tweets that have been published (including re-tweets) by a user. In future work, we also plan to consider click-through data from the faceted search engine. Context modeling covers mining of new knowledge from the Twitter data. We therefore propose relation learning strategies that exploit co-occurrence of entities in Twitter messages to infer typed relationships between entities [ 12 ]. Adaptive Faceted Search Based on the semantically enriched tweets, the learnt relationships between entities extracted from tweets and the user pro les generated by the user modeling layer, the adaptive faceted search layer solves the actual facet ranking problem. It provides methods that adapt the facetvalue pair ranking to the given context and user. Furthermore, it provides query suggestions by exploiting the relations learnt from the Twitter messages. Given the current facet query, which is a list of facet-value pairs where each value refers to an entity, we can exploit relationships between entities in order to identify entities that are related to those entities that occur in the current facet query. We leave the analysis of such query suggestions for future work. Instead, we focus on the facet ranking problem and propose di erent strategies for ranking facet-value pairs in the next subsection. 2.2

Adaptive Faceted Search and Facet Ranking Strategies Non-Personalized Facet Ranking A lightweight approach is to rank the facet-value pairs (p; e) 2 F based on their occurrence frequency in the current hit list H, the set of tweets that match the current query (cf. De nition 1): rankfrequency((p; e); H) = jH(p;e)j (1) jH(p;e)j is the number of (remaining) tweets that contain the facet-value pair (p; e) that can be applied to further lter the given hit list H. By ranking those facets that appear in most of the tweets, rankfrequency minimizes the risk of ltering out relevant tweets but might increase the e ort a user has to invest to narrow down search results.

Context-adaptive Facet Ranking The context-adaptive strategy exploits relationships between entities (facet values) to produce the facet ranking. A relationship is therefore de ned as follows: De nition 2 (Relationship). Given two entities e1 and e2, a relationship between these entities is described via a tuple rel(e1; e2; type; tstart; tend; w), where type labels the relationship, tstart and tend specify the temporal validity of the relationship and w 2 [0::1] is a weighting score that allows for specifying the strength of the relationship.

The higher the weighting score w the stronger the relationship between e1 and e2. We use co-occurrence frequency as weighting scheme. Hence, given the enriched tweets, we count the number of tweets both entities (e1 and e2) are associated with. The context-adaptive facet ranking strategy ranks the facetvalue pairs (p; e) 2 F according to w(ei; e), where ei is a facet value that is already part of the given query: (pi; ei) 2 Fquery (cf. De nition 1): rankrelation((p; e); Fquery) = X w(ei; e)j(p; ei) 2 Fquery (2) i

Hence, the context-sensitive strategy can only be applied in situations where the user has already made one selection, so that jFqueryj > 0.

Personalized Facet Ranking The personalized facet ranking strategy adapts the facet ranking to a given user pro le that is generated by the user modeling layer depicted in Figure 1(b). User pro les conform to the following model and specify a user's interest into a speci c facet value (entity).

De nition 3 (User Pro le). The pro le of a user u 2 U is a set of weighted entities where with respect to the given user u for an entity e 2 E its weight w(u; e) is computed by a certain function w.

P (u) = f(e; w(u; e))je 2 E; u 2 U g Here, E and U denote the set of entities and users respectively.

Given the set of facet-value pairs (p; e) 2 F (see De nition 1), the personalized facet ranking strategy utilizes the weight w(u; e) in P (u) to rank the facet-value pairs:

By combining the above three strategies it is possible to generate further facet ranking methods. A combination of two strategies can be realized by building the weighted average computed for a given facet-value pair (p; e) (e.g. rankcombined = rank ((p; e)) + (1 ) rank ((p; e)), where 2 [0::1]). 3

Preliminary Analysis and Future Work

In this paper, we explored strategies for faceted search on Twitter. We presented a framework that enriches the semantics of Twitter messages in order to generate facets that describe the content of tweets (e.g. persons, locations, organizations). To do so, we extracted entities both from tweets and linked external Web resources. Our analysis based on a large Twitter dataset8 showed that the exploitation of links for enriching tweets is necessary to better support faceted search on Twitter, due to the obvious increase in the number of facet values when tweets are enriched with entities of related news articles. We proposed an adaptive faceted search engine with di erent strategies for ranking facets including methods that adapt to the actual context and user. The context-adaptive method exploits relationships between facet values (entities) that we learn from 8 We make our dataset publicly available at http://wis.ewi.tudelft.nl/umap2011/ rankpersonalized((p; e); P (u)) = w(u; e) if w(u; e) 2 P (u) 0 otherwise (3) tweets and linked news articles [ 12 ]. Our strategy discovers relationships between persons/groups (including organizations) and events (including political, sports and entertainment) with high precision of 0.92 and 0.87 regarding P@10 and P@20. Our analysis indicates that these relationships can be used to suggest and rank facets that are related to the current context (the current faceted query) with high precision.

Furthermore, the personalized facet ranking requires a user pro le P (u) in order to adapt the facet ranking to the preferences of the user. In [ 8 ], we showed that our user modeling strategies, which are based on semantic enrichment of tweets, outperform other strategies such as hashtag-based approaches signi cantly for recommending news articles. In future work, we will analyze the applicability of those user modeling strategies for our adaptive faceted search engine. In our evaluation, we will measure the e ect of our facet ranking strategies (i) in the context of an automatic experiment as proposed by Koren et al. [ 13 ] and (ii) in practice by enabling real users to experiment with our adaptive faceted search interface for Twitter.

References

1. Java , A. , Song , X. , Finin , T. , Tseng , B. : Why we twitter: understanding microblogging usage and communities . In: WebKDD/SNA-KDD, ACM ( 2007 ) 56 { 65

2. Kwak , H. , Lee , C. , Park , H., Moon, S. : What is Twitter, a social network or a news media? In: WWW, ACM ( 2010 ) 591 { 600

3. Hughes , A.L. , Palen , L. : Twitter Adoption and Use in Mass Convergence and Emergency Events . In: ISCRAM, iscram.org ( 2009 )

4. Zhao , D. , Rosson , M.B. : How and why people Twitter: the role that micro-blogging plays in informal communication at work . In: GROUP, ACM ( 2009 ) 243 { 252

5. Bernstein , M. , Kairam , S. , Suh , B. , Hong , L. , Chi , E.H.: A torrent of tweets: managing information overload in online social streams . In: CHI Workshop on Microblogging ( 2010 )

6. Owens , J.W. , Lenz , K. , Speagle , S. : Trick or Tweet: How Usable is Twitter for First-Time Users? Usability News 11 ( 2009 )

7. Chen , J. , Nairn , R. , Nelson , L. , Bernstein , M. , Chi , E.: Short and tweet: experiments on recommending content from information streams . In: CHI , ACM ( 2010 ) 1185 { 1194

8. Abel , F. , Gao , Q. , Houben , G.J. , Tao , K. : Analyzing User Modeling on Twitter for Personalized News Recommendations . In: UMAP, Springer ( 2011 )

9. Chen , J. , Nairn , R. , Chi , E.H. : Speak Little and Well: Recommending Conversations in Online Social Streams . In: CHI, ACM ( 2011 )

10. Oren , E. , Delbru , R. , Decker , S. : Extending faceted navigation for RDF data . In: ISWC , Springer ( 2006 ) 559 { 572

11. Weng , J. , Lim , E.P. , Jiang , J. , He , Q. : TwitterRank: nding topic-sensitive in uential Twitterers . In: WSDM, ACM ( 2010 ) 261 { 270

12. Celik , I. , Abel , F. , Houben , G.-J.: Learning Semantic Relationships between Entities in Twitter . In: ICWE, Springer ( 2011 )

13. Koren , J. , Zhang, Y. , Liu , X. : Personalized interactive faceted search . In: WWW, ACM ( 2008 ) 477 { 486