An Investigation into Information Navigation via Diverse Keyword-based Facets M. Atif Qureshi and Derek Greene Insight Centre for Data Analytics, University College Dublin, Ireland {muhammad.qureshi@ucd.ie, derek.greene@ucd.ie} Abstract. In the age of information overload, it is necessary to provide effective information navigation tools that operate over unstructured textual data. Current state-of-the-art methods are limited in terms of providing effective exploration capabilities for various information seeking tasks, especially those arising in do- mains such as online journalism. Here we argue for improvements in faceted search systems, via new strategies for identifying keyword-based facets. Our pro- posed technique utilises a PageRank model operating over the graph of terms appearing in documents, while also employing novel methods for biasing sig- nificant terms and named entities. In addition, we consider the notion of diver- sity within extracted keywords in an effort to maximize coverage over a range of topics. We perform experimental evaluations over issues relevant to the Irish General Elections 2016, demonstrating the superior performance of our proposed technique. 1 Introduction Web 2.0 technologies have enabled online information to grow at an exponential rate, with a sizable form of this information being textual in nature. To a large extent, the textual information is unstructured, leading to what is commonly known as “informa- tion overload” problem for lengthy text documents [5]. Generating effective summaries of these documents can help to minimize the impact of information overload. Recently the research community within text mining has looked into various methods for dealing with this problem [1]. Keyword extraction is one strategy that summarizes important aspects of a document, while enabling the reader to quickly contrast among documents using the selected keywords [2, 16, 18, 24]. Another emerging information-seeking paradigm is one where a user’s information need is vague and exploratory in nature [22]. In these cases, classification of infor- mation nuggets into various facets, commonly known as “faceted search” [20], helps users in this knowledge discovery task. Similar to keyword extraction, faceted search attempts to organize unstructured information into a structure leading to a paradigm of exploratory information seeking [20]. Traditionally, faceted search systems organize document collections into various attributes, and allow the user to navigate along the various organized attributes. Despite sharing a common goal of organizing unstructured text into structured in- formation, to the best of our knowledge keyword extraction and faceted search have not been explored in combination with each other. Previous approaches for faceted search have attempted to extract various facets from within textual metadata [4]1 and tend to limit exploration to useful knowledge hidden within the textual content. Such explo- ration can be particularly helpful for textual data containing a variety of useful topics from which meaningful inferences can be made. Consider for example the case of a journalist wishing to examine the various ways in which news sources are reporting on different issues that are relevant to an on-going election campaign. In such a scenario, faceted search can offer a way to support extensive navigation required by the jour- nalist, and more so if the facets are extracted from within the text appearing in news articles rather than metadata alone. This preliminary study proposes to utilize keywords for the refinement of faceted search thereby leading to exploration of novel informa- tion, and presents as a case-study extraction of keyword-based facets from within news articles. Our approach to keyword extraction models a document as a graph of terms to which we apply biased PageRank followed by maximization of topical coverage through extraction of diverse aspects of a given topic. We demonstrate the effective- ness of keyword-based facets through a system-centric evaluation on a dataset of news articles collected from eight different Irish and international news sources. The remainder of this paper is organized as follows. In Section 2, we provide an overview of related work. In Section 3, we present a detailed explanation of the manner in which we extract diverse keyword-based facets. In Section 4, we present experimental evaluations on various queries applied to the news article dataset to demonstrate the usefulness of our approach. In Section 5, we conclude the paper with a discussion of possible future extensions. 2 Related Work Our work here touches on a number of different fields. In the following we review related work in keyword extraction together with faceted search. We also highlight how our work differs from existing approaches. 2.1 Keyword Extraction Recent years have seen keyword extraction as a dominant technique for summarizing the contents of a text corpus, with numerous applications in various information access tasks such as query expansion, document classification, and document clustering, to name but a few. Due to the differences in the nature of textual documents, generally four document specific factors have influenced keyword extraction techniques: document length, struc- tural consistency of the document, possibility of topic change within the document, and possibility of topic correlation among topics within the document [7]. The longer the document, the more candidate keywords are available (e.g. scientific articles and techni- cal reports compared to news articles and emails). A well structured document contains certain sections (fields) and formatting that can be exploited for keyword extraction, 1 The most popular faceted search interfaces have been deployed on e-commerce sites where the data contains pre-defined attributes (price, genre etc.) from which facets are extracted. such as a scientific paper’s title and abstract [12], and metadata of webpages [25]. Doc- uments such as conversational texts, logs of open-ended meetings generally contain several topics in sequence (as in talking points), and in such type of documents a topi- cal change happens as the discussion moves [11], e.g., first topic can be about cleaning, second can be related to cooking, etc. Documents such as news articles and scientific articles can possess a topical correlation (i.e., interconnected topics) in the entire flow of the article, unlike informal chat. Therefore, in these type of documents the keywords are usually related to one another [18, 21]. Several approaches have been proposed in the literature to address the problem of keyword extraction from a piece of text. However, keyword extraction is generally per- formed in two steps. First a list of candidate keywords are extracted using some heuris- tics, and then each candidate is scored using either a supervised or an unsupervised strategy. A candidate keyword is typically extracted on the basis of n-grams [10, 17], words with specific parts of speech tags (i.e. nouns, verbs, adjectives) [14, 18], noun phrases [23], words other than stopwords [15], and n-grams appearing as Wikipedia articles titles [6]. Scoring each candidate keyword in a supervised strategy is influenced by the selection of different features and by the process of task re-definition. Scoring in an unsupervised strategy is often addressed using graph-based approaches or topic modeling. 2.2 Faceted Search Faceted search has been dominant in commercial applications, with prime examples being e-commerce sites such as those of IBM Websphere and Amazon. Within the aca- demic setting, Flamenco by Hearst [9] is one of earliest faceted search systems which uses rich metadata in a flexible manner to guide the user’s navigational behavior. The traditional definition of facets says that it consists of a “a set of meaningful labels orga- nized in such a way as to reflect the concepts relevant to a domain” [8]. Earlier works however are limited in the sense that properties and dimensions of document collections are used to extract facets and textual data with its inherently unstructured nature cannot be organized properly into facets. This led the research community towards methods for automatic facet extraction through lexical subsumption [3], synsets and hypernym re- lations from WordNet [19], and personalized PageRank on ODP categories [13]. These efforts remain limited to defining concept hierarchies for document collections thereby limiting information discovery to a few broad concepts. We propose to advance faceted search through the utilization of keyword-based facets, and present a prototype of such a system applied to news articles. The system aims to address limitations of current faceted search systems by facilitating navigation at a higher granularity than what is allowed by current systems. To this end, we extract keywords from within retrieved news articles in response to a certain query, while max- imizing the topical coverage and hence, the diversity of extracted keywords. Note that this differs from traditional keyword extraction where the document corpus is static in nature. 3 Methodology In this section, we present an overview of our methodology for the extraction of diverse keywords. We first explain how we utilize biased PageRank for the process of keyword extraction followed by an explanation of our technique to maximize diversity within the extracted keywords. 3.1 Keyword Extraction As mentioned in Section 1, we apply PageRank to the graph of terms appearing in a given document. The effectiveness of graph-based ranking algorithms in Web search applications has encouraged researchers to apply similar models to textual data for natural language processing. TextRank by Mihalcea and Tarau [18] is an example of such a model, and we follow a similar intuition by treating terms within a document as nodes with edges between terms that co-occur. It is significant to note that the existing keyword extraction techniques utilise a static corpus while our computation is of a dy- namic, real-time nature over a set of documents generated in response to a query2 . We list below a number of ways in which our proposed technique differs from TextRank: – We apply the keyword extraction model over a collection of documents instead of using a single document. – We define edge weights between the terms with respect to word distance (as an exponential decay factor) between them, instead of uniform edge weights within a fixed window length. – We use the relevance score of each document in relation to the query to further bias the PageRank node vector (i.e., terms extracted from a each document are biased towards the relevance score). – Lastly, we identify significant terms from the corpus through chi-square test of independence, and further bias the PageRank node vector for these significant terms and named entities in the document collection. We now explain the various steps of our keyword extraction process: 1. We apply cost-effective, time-series-based clustering to the ranked list of docu- ments3 . We cluster the retrieved documents using a single feature which is the cre- ation time-stamp of each document. We argue that sub-topics of similar interests are usually clustered around a specific time window. For example: pre-election, on the election day, and post-election can be three different time windows, clustering various sub-topics around the main topic “elections”. 2. We pick the top retrieved articles, in proportion to the size of each cluster. This reduces the full set of documents to a representative sub-sample of documents prior to the application of PageRank. For example, the volume of documents may be higher around the election dates as opposed to a few months before the elections hence resulting in a larger number of articles for the “election” cluster. 2 Recall from Section 1 and 2 that our main goal is to propose keywords as facets for information navigation in a faceted search system. 3 These are basically the ranked list of documents retrieved in response to a query 3. We apply biased PageRank to the reduced set of documents from the previous step and extract single terms representative of the document collection. To ensure further computational efficiency, we compute the PageRank scores for terms appearing in titles and sub-titles of documents only, which helps reduce the size of the term graph for real-time operation. Finally, we merge single terms identified by biased PageRank to extract bigrams key- words. To achieve this, we add the individual PageRank scores of the co-occurring terms according to their probability of co-occurrence implying that n-grams that co-occur fre- quently within the documents retrieved are highly likely to constitute a keyword. This step utilises the terms in entire document instead of titles and sub-titles alone. 3.2 Maximizing Topical Coverage of Extracted Keywords One potential limitation of utilizing biased PageRank for keyword extraction is the selection of keywords that are redundant in terms of coverage over a range of differ- ent sub-topics. This limits the coverage of diverse topics in response to a given query. We illustrate with an example from the news domain: in response to the query “syria” our algorithm retrieves keywords “syria state”, “syria russian” and “syria government”. which do not cover a wide variety of topics. It is therefore essential to ensure a coverage of a maximum range of diverse topics through the extracted keywords (or facets). We utilize the documents retrieved with a given keyword to measure the “freshness” of a given keyword. Here, freshness is the probability of the number of unique documents that a certain keyword is able to retrieve compared to other keywords (or facets), and this is then multiplied with the PageRank score calculated from Section 3.1. Finally, keywords with highest scores after the application of proposed freshness strategy are extracted as facets. To return to our example query “syria”, our algorithm is now able to retrieve keywords “syria talks”, “syria un” and “syria vote” which are more diverse and maximize the coverage over a range of different sub-topics. News Source No. of Articles Independent 50,309 BBC 35,179 Irish Times 30,919 Irish Examiner 19,258 RTE 18,299 Reuters 17,899 The Journal 12,020 Al Jazeera 2,786 Table 1. Information about news sources and articles in each news source. Algorithm Facets Proposed algorithm independent water, cork water, irish policy TextRank future, charges, system TFxIDF new ireland, ireland new, year ireland Table 2. Top-3 facets by various algorithms for the query “Irish water”. Algorithm Facets Proposed algorithm education secretary, education system, education scheme TextRank system, next, years TFxIDF school education, new school, education schools Table 3. Top-3 facets by various algorithms for the query “education”. Fig. 1. Experimental results for “cumulative return”, “average novelty”, and “f-measure” corre- sponding to the query“Irish water”. Algorithm Facets Proposed algorithm housing minister, housing top, cork council TextRank market, house, year TFxIDF housing dublin, dublin housing, housing crisis Table 4. Top-3 facets by various algorithms for the query “housing”. Fig. 2. Experimental results for “cumulative return”, “average novelty”, and “f-measure” corre- sponding to the query “education”. 4 Experimental Evaluations In this section, we present experimental evaluations over two system-centric measures which demonstrate the strength of our keyword-based facets in a real-time informa- tion retrieval setting. Our dataset comprises news articles extracted from eight different news sources,4 and we show results for three different information access needs. Ta- ble 1 shows detailed statistics about the number of articles from each news source, and they cover a period from 8th July, 2015 to 7th April, 2016. We utilize system-centric 4 The Irish Independent, The Irish Times, The Irish Examiner, RTÉ, The Journal, BBC, Reuters, Al Jazeera. Fig. 3. Experimental results for “cumulative return”, “average novelty”, and “f-measure” corre- sponding to the query “housing’.’ evaluation measures, namely, cumulative return and average novelty. Cumulative re- turn is defined as the coverage of the total number of documents retrieved by all facets relative to the total number of documents returned without using faceted search. Aver- age novelty is the average ratio between the unique documents retrieved at each pair of successive facets. Both measures effectively help us to quantify the various ways in which facets aid the process of information navigation – cumulative return indicates the potential of facets to return as many documents as possible; average novelty indicates the potential of facets to return as many undiscovered documents as possible. We use these measure to compare our proposed approach to two existing competing approaches – TextRank and TFxIDF. In what follows we present experimental results for three important issues of con- cern during Irish General Election 2016, namely “irish water”, “education”, and “hous- ing”. A journalist monitoring various issues surrounding Irish Elections 2016 needs ex- tensive information navigation capabilities for queries issued in response to the above issues. Tables 2, 3 and 4 show the facets returned by our algorithm and the two com- petitors. From these results, it is evident that our algorithm extracts informative facets. As further proof of concept, we utilize the facets returned by the three algorithms to re- trieve more documents and plot “cumulative return” together with “average novelty” for each of the three queries. Figures 1, 2 and 3 show the experimental results for each of these queries; and we also give an overall picture through f-score5 between “cumulative return” and “average novelty”. In the case of the query “Irish Water” as shown in Figure 1, TFxIDF demonstrates higher “cumulative return” but our algorithm fetches new documents at the higher rate as shown by “average novelty”. This implies that TFxIDF is able to retrieve overall more documents through its extracted facets, but these documents are retrieved under general facet terms which are generally not informative or representative of the original query “Irish Water” (refer to the list of top terms in Table 1, and observe the non-informative facets in terms of human intuition for TFxIDF). In the case of the queries “education” and “housing”, our algorithm predominantly outperforms TFxIDF and TextRank. 5 Conclusion and Future Work In this paper we have proposed an approach to utilize keywords for effective informa- tion navigation in faceted search systems. Current approaches to faceted search operate over metadata or hierarchical concepts, and we proposed an improvement over this in the form of keyword-based facets. Our technique made use of a graph-based modeling over terms of a document with the documents being retrieved in response to a query. We used significant terms and named entities to bias PageRank over the graph of terms followed by application of a diversity-aware strategy called “freshness”. Experimental evaluations over issues pertaining to Irish General Elections 2016 showed the superi- ority of our technique. As future work, we aim to present more extensive experimental evaluations, by means of both system-centric and user-centric evaluation measures as applied to feedback coming from a user study. Acknowledgments: This publication has emanated from research conducted with the support of Science Foundation Ireland (SFI) under Grant Number SFI/12/RC/2289. References 1. C. C. Aggarwal and C. Zhai. Mining text data. Springer Science & Business Media, 2012. 2. A. Csomai and R. Mihalcea. Linking educational materials to encyclopedic knowledge. In Proceedings of the 2007 Conference on Artificial Intelligence in Education: Building Tech- nology Rich Learning Contexts That Work, pages 557–559, Amsterdam, The Netherlands, The Netherlands, 2007. IOS Press. 3. W. Dakka, P. G. Ipeirotis, and K. R. Wood. Automatic construction of multifaceted browsing interfaces. In Proceedings of the 14th ACM International Conference on Information and Knowledge Management, CIKM ’05, pages 768–775, Bremen, Germany, 2005. 5 It is simply the harmonic mean between the two measures. 4. D. Dash, J. Rao, N. Megiddo, A. Ailamaki, and G. Lohman. Dynamic faceted search for discovery-driven analysis. In Proceedings of the 17th ACM Conference on Information and Knowledge Management, CIKM ’08, pages 3–12, Napa Valley, California, USA, 2008. 5. R. Feldman and J. Sanger. The text mining handbook: advanced approaches in analyzing unstructured data. Cambridge University Press, 2007. 6. M. Grineva, M. Grinev, and D. Lizorkin. Extracting key terms from noisy and multitheme documents. In Proceedings of the 18th international conference on World wide web, WWW ’09, pages 661–670, Madrid, Spain, 2009. 7. K. S. Hasan and V. Ng. Automatic keyphrase extraction: A survey. In Proceedings of the Association for Computational Linguistics (ACL), ACL 2014, pages 1262–1273, Baltimore, Maryland, USA, 2014. 8. M. Hearst. Design recommendations for hierarchical faceted search interfaces. In ACM SIGIR workshop on faceted search, pages 1–5. Seattle, WA, 2006. 9. M. A. Hearst. Next generation web search: Setting our sites. IEEE Data Eng. Bull., 23(3):38– 48, 2000. 10. A. Hulth. Improved automatic keyword extraction given more linguistic knowledge. In Pro- ceedings of the 2003 Conference on Empirical Methods in Natural Language Processing, EMNLP ’03, pages 216–223, Sapporo, Japan, 2003. Association for Computational Lin- guistics. 11. S. N. Kim and T. Baldwin. Extracting keywords from multi-party live chats. In Proceedings of the 26th Pacific Asia Conference on Language, Information, and Computation, pages 199– 208, Bali, Indonesia, 2012. 12. S. N. Kim, O. Medelyan, M.-Y. Kan, and T. Baldwin. Automatic keyphrase extraction from scientific articles. Language resources and evaluation, 47(3):723–742, 2013. 13. C. Kohlschütter, P.-A. Chirita, and W. Nejdl. Using link analysis to identify aspects in faceted web search. In SIGIR’2006 Faceted Search Workshop, pages 55–59. Seattle, WA, 2006. 14. F. Liu, D. Pennell, F. Liu, and Y. Liu. Unsupervised approaches for automatic keyword ex- traction using meeting transcripts. In Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computa- tional Linguistics, NAACL ’09, pages 620–628, Boulder, Colorado, 2009. 15. Z. Liu, P. Li, Y. Zheng, and M. Sun. Clustering to find exemplar terms for keyphrase extrac- tion. In Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 1 - Volume 1, EMNLP ’09, pages 257–266, Singapore, 2009. 16. Y. Matsuo and M. Ishizuka. Keyword extraction from a single document using word co- occurrence statistical information. International Journal on Artificial Intelligence Tools, 13(01):157–169, 2004. 17. O. Medelyan, E. Frank, and I. H. Witten. Human-competitive tagging using automatic keyphrase extraction. In Proceedings of the 2009 Conference on Empirical Methods in Nat- ural Language Processing: Volume 3 - Volume 3, EMNLP ’09, pages 1318–1327, Singapore, 2009. 18. R. Mihalcea and P. Tarau. Textrank: Bringing order into text. In Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing , EMNLP 2004, pages 404–411, Barcelona, Spain, 2004. 19. E. Stoica, M. A. Hearst, and M. Richardson. Automating creation of hierarchical faceted metadata structures. In HLT-NAACL, pages 244–251, Rochester, New York, USA, 2007. 20. D. Tunkelang. Faceted search. Synthesis lectures on information concepts, retrieval, and services, 1(1):1–80, 2009. 21. P. Turney. Coherent keyphrase extraction via web mining. In Proceedings of the 18th In- ternational Joint Conference on Artificial Intelligence, pages 434–439, Acapulco, Mexico, 2003. 22. R. W. White and R. A. Roth. Exploratory search: beyond the query-response paradigm (synthesis lectures on information concepts, retrieval & services). Morgan and Claypool Publishers, 3, 2009. 23. Y.-f. B. Wu, Q. Li, R. S. Bot, and X. Chen. Domain-specific keyphrase extraction. In Proceedings of the 14th ACM international conference on Information and knowledge man- agement, pages 283–284, Bremen, Germany, 2005. ACM. 24. S. Ye, T.-S. Chua, M.-Y. Kan, and L. Qiu. Document concept lattice for text understanding and summarization. Information Processing & Management, 43(6):1643–1662, 2007. 25. W.-t. Yih, J. Goodman, and V. R. Carvalho. Finding advertising keywords on web pages. In Proceedings of the 15th international conference on World Wide Web, pages 213–222, Edinburgh, Scotland, UK, 2006. ACM.