OpenRaiser/Intern-Atlas huggingface dataset:
Driven by Food: Modeling Geographic Choice
Authors: Ravi Kumar, Mohammad Mahdian, Bo Pang, Andrew Tomkins, Sergei Vassilvitskii
Venue: WSDM
Year: 2015

In this work we study the dynamics of geographic choice, i.e., how users choose one from a set of objects in a geographic region. We postulate a model in which an object is selected from a slate of candidates with probability that depends on how far it is (distance) and how many closer alternatives exist (rank). Under a discrete choice formulation, we argue that there exists a factored form in which unknown functions of rank and distance may be combined to produce an accurate estimate of the likelihood that a user will select each alternative. We then learn these hidden functions and show that each can be closely approximated by an appropriately parameterized lognormal, even though the respective marginals look quite different. We give a theoretical justification to support the presence of lognormal distributions.
Distributed Graph Algorithmics: Theory and Practice
Authors: Silvio Lattanzi, Vahab S. Mirrokni
Venue: WSDM
Year: 2015

As a fundamental tool in modeling and analyzing social, and information networks, large-scale graph mining is an important component of any tool set for big data analysis. Processing graphs with hundreds of billions of edges is only possible via developing distributed algorithms under distributed graph mining frameworks such as MapReduce, Pregel, Gigraph, and alike. For these distributed algorithms to work well in practice, we need to take into account several metrics such as the number of rounds of computation and the communication complexity of each round. For example, given the popularity and ease-of-use of MapReduce framework, developing practical algorithms with good theoretical guarantees for basic graph algorithms is a problem of great importance.
The Power of Random Neighbors in Social Networks
Authors: Silvio Lattanzi, Yaron Singer
Venue: WSDM
Year: 2015

The friendship paradox is a sociological phenomenon first discovered by Feld which states that individuals are likely to have fewer friends than their friends do, on average. This phenomenon has become common knowledge, has several interesting applications, and has also been observed in various data sets. In his seminal paper Feld provides an intuitive explanation by showing that in any graph the average degree of edges in the graph is an upper bound on the average degree of nodes. Despite the appeal of this argument, it does not prove the existence of the friendship paradox. In fact, it is easy to construct networks -- even with power law degree distributions -- where the ratio between the average degree of neighbors and the average degree of nodes is high, but all nodes have the exact same degree as their neighbors. Which models, then, explain the friendship paradox? In this paper we give a strong characterization that provides a formal understanding of the friendship paradox. We show that for any power law graph with exponential parameter in (1,3), when every edge is rewired with constant probability, the friendship paradox holds, i.e. there is an asymptotic gap between the average degree of the sample of polylogarithmic size and the average degree of a random set of its neighbors of equal size. To examine this characterization on real data, we performed several experiments on social network data sets that complement our theoretical analysis. We also discuss the applications of our result to influence maximization.
New Directions in Recommender Systems
Authors: Jure Leskovec
Venue: WSDM
Year: 2015

Recommender systems are an integral part of how we experience the Web today and they have become so ubiquitous that we do not even notice them anymore. However, today's recommender systems mostly treat items they recommend as black boxes and primarily focus on extracting correlations and co-counts from user behavior data. In this talk I argue that next generation recommender systems will require deep understanding of items being recommended as well as modeling the relationships between those items. I will present examples how auxiliary data about items (descriptions, reviews, product specifications) can be used to improve recommendations.
Offline Evaluation and Optimization for Interactive Systems
Authors: Lihong Li
Venue: WSDM
Year: 2015

Evaluating and optimizing an interactive system (like search engines, recommender and advertising systems) from historical data against a predefined online metric is challenging, especially when that metric is computed from user feedback such as clicks and payments. The key challenge is counterfactual in nature: we only observe a user's feedback for actions taken by the system, but we do not know what that user would have reacted to a different action. The golden standard to evaluate such metrics of a user-interacting system is online A/B experiments (a.k.a. randomized controlled experiments), which can be expensive in terms of both time and engineering resources. Offline evaluation/optimization (sometimes referred to as off-policy learning in the literature) thus becomes critical, aiming to evaluate the same metrics without running (many) expensive A/B experiments on live users. One approach to offline evaluation is to build a user model that simulates user behavior (clicks, purchases, etc.) under various contexts, and then evaluate metrics of a system with this simulator. While being straightforward and common in practice, the reliability of such model-based approaches relies heavily on how well the user model is built. Furthermore, it is often difficult to know a priori whether a user model is good enough to be trustable.
Toward Predicting the Outcome of an A/B Experiment for Search Relevance
Authors: Lihong Li, Jin Young Kim, Imed Zitouni
Venue: WSDM
Year: 2015

A standard approach to estimating online click-based metrics of a ranking function is to run it in a controlled experiment on live users. While reliable and popular in practice, configuring and running an online experiment is cumbersome and time-intensive. In this work, inspired by recent successes of offline evaluation techniques for recommender systems, we study an alternative that uses historical search log to reliably predict online click-based metrics of a \emph{new} ranking function, without actually running it on live users. To tackle novel challenges encountered in Web search, variations of the basic techniques are proposed. The first is to take advantage of diversified behavior of a search engine over a long period of time to simulate randomized data collection, so that our approach can be used at very low cost. The second is to replace exact matching (of recommended items in previous work) by \emph{fuzzy} matching (of search result pages) to increase data efficiency, via a better trade-off of bias and variance. Extensive experimental results based on large-scale real search data from a major commercial search engine in the US market demonstrate our approach is promising and has potential for wide use in Web search.
On Integrating Network and Community Discovery
Authors: Jialu Liu, Charu C. Aggarwal, Jiawei Han
Venue: WSDM
Year: 2015

The problem of community detection has recently been studied widely in the context of the web and social media networks. Most algorithms for community detection assume that the entire network is available for online analysis. In practice, this is not really true, because only restricted portions of the network may be available at any given time for analysis. Many social networks such as Facebook have privacy constraints, which do not allow the discovery of the entire structure of the social network. Even in the case of more open networks such as Twitter, it may often be challenging to crawl the entire network from a practical perspective. For many other scenarios such as adversarial networks, the discovery of the entire network may itself be a costly task, and only a small portion of the network may be discovered at any given time. Therefore, it can be useful to investigate whether network mining algorithms can integrate the network discovery process tightly into the mining process, so that the best results are achieved for particular constraints on discovery costs. In this context, we will discuss algorithms for integrating community detection with network discovery. We will tightly integrate with the cost of actually discovering a network with the community detection process, so that the two processes can support each other and are performed in a mutually cohesive way. We present experimental results illustrating the advantages of the approach.
Topics, Tasks & Beyond: Learning Representations for Personalization
Authors: Rishabh Mehrotra
Venue: WSDM
Year: 2015

Accurate understanding of a user's interests, preferences and behaviours is possibly one of the most critical research challenges faced while developing personalized systems for behavior targeting and information access. We intend to develop comprehensive latent variable models for web search personalization which jointly models user's topical interests along with user's click based relevance preferences while at the same time taking into account user's intended search tasks along with information about other similar users. We further augment this model by incorporating topic-level relevance parameters, which, to the best of our knowledge, is the first attempt at modeling result ranking preferences at the topic level. Additionally, we intend to explore the possibility of modeling users in terms of the search tasks they perform thereby coupling users' topical interests with their search task behavior to learn user representations. Finally, we wish to evaluate the proposition of extending user representations to hierarchical structures as an alternative to existing flat representations. The evaluation of these alternative approaches for user modeling is based on their performance on a variety of tasks such as collaborative query recommendations, user cohort modeling and search result personalization. This proposal provides the motivation to pursue these research directions, summarizes key research problems being targeted, glances through potential ways of tackling these research challenges and highlights some initial results obtained.
Optimal Space-time Tradeoffs for Inverted Indexes
Authors: Giuseppe Ottaviano, Nicola Tonellotto, Rossano Venturini
Venue: WSDM
Year: 2015

Inverted indexes are usually represented by dividing posting lists into constant-sized blocks and representing them with an encoder for sequences of integers. Different encoders yield a different point in the space-time trade-off curve, with the fastest being several times larger than the most space-efficient. An important design decision for an index is thus the choice of the fastest encoding method such that the index fits in the available memory. However, a better usage of the space budget could be obtained by using faster encoders for frequently accessed blocks, and more space-efficient ones those that are rarely accessed. To perform this choice optimally, we introduce a linear time algorithm that, given a query distribution and a set of encoders, selects the best encoder for each index block to obtain the lowest expected query processing time respecting a given space constraint. To demonstrate the effectiveness of this approach we perform an extensive experimental analysis, which shows that our algorithm produces indexes which are significantly faster than single-encoder indexes under several query processing strategies, while respecting the same space constraints.
On Tag Recommendation for Expertise Profiling: A Case Study in the Scientific Domain
Authors: Isac S. Ribeiro, Rodrygo L. T. Santos, Marcos André Gonçalves, Alberto H. F. Laender
Venue: WSDM
Year: 2015

Building expertise profiles is a crucial step towards identifying experts in different knowledge areas. However, summarizing the topics of expertise of a given individual is a challenging task, primarily due to the semi-structured and heterogeneous nature of the documentary evidence available for this task. In this paper, we investigate the suitability of tag recommendation as a mechanism to produce effective expertise profiles. In particular, we perform a large-scale user study with academic experts from different knowledge areas to assess the effectiveness of multiple supervised and unsupervised tag recommendation approaches as well as multiple sources of textual evidence. Our analysis reveals that traditional content-based tag recommenders perform well at identifying expertise-oriented tags, with article keywords being a particularly effective source of evidence across profiles in different knowledge areas and with various levels of sparsity. Moreover, by combining multiple recommenders and sources of evidence as learning signals, we further demonstrate the effectiveness of tag recommendation for expertise profiling.
Sentiment-Specific Representation Learning for Document-Level Sentiment Analysis
Authors: Duyu Tang
Venue: WSDM
Year: 2015

In this paper, we propose a representation learning research framework for document-level sentiment analysis. Given a document as the input, document-level sentiment analysis aims to automatically classify its sentiment/opinion (such as thumbs up or thumbs down) based on the textural information. Despite the success of feature engineering in many previous studies, the hand-coded features do not well capture the semantics of texts. In this research, we argue that learning sentiment-specific semantic representations of documents is crucial for document-level sentiment analysis. We decompose the document semantics into four cascaded constitutes: (1) word representation, (2) sentence structure, (3) sentence composition and (4) document composition. Specifically, we learn sentiment-specific word representations, which simultaneously encode the contexts of words and the sentiment supervisions of texts into the continuous representation space. According to the principle of compositionality, we learn sentiment-specific sentence structures and sentence-level composition functions to produce the representation of each sentence based on the representations of the words it contains. The semantic representations of documents are obtained through document composition, which leverages the sentiment-sensitive discourse relations and sentence representations.
Back to the Past: Supporting Interpretations of Forgotten Stories by Time-aware Re-Contextualization
Authors: Nam Khanh Tran, Andrea Ceroni, Nattiya Kanhabua, Claudia Niederée
Venue: WSDM
Year: 2015

Fully understanding an older news article requires context knowledge from the time of article creation. Finding information about such context is a tedious and time-consuming task, which distracts the reader. Simple contextualization via Wikification is not sufficient here. The retrieved context information has to be time-aware, concise (not full Wikipages) and focused on the coherence of the article topic. In this paper, we present an approach for time-aware recontextualization, which takes those requirements into account in order to improve reading experience. For this purpose, we propose (1) different query formulation methods for retrieving contextualization candidates and (2) ranking methods taking into account topical and temporal relevance as well as complementarity with respect to the original text. We evaluate our proposed approaches through extensive experiments using real-world datasets and ground-truth consisting of over 9,400 article/context pairs. To this end, our experimental results show that our approaches retrieve contextualization information for older articles from the New York Times Archive with high precision and outperform baselines significantly.
FLAME: A Probabilistic Model Combining Aspect Based Opinion Mining and Collaborative Filtering
Authors: Yao Wu, Martin Ester
Venue: WSDM
Year: 2015

Aspect-based opinion mining from online reviews has attracted a lot of attention recently. Given a set of reviews, the main task of aspect-based opinion mining is to extract major aspects of the items and to infer the latent aspect ratings from each review. However, users may have different preferences which might lead to different opinions on the same aspect of an item. Even if fine-grained aspect rating analysis is provided for each review, it is still difficult for a user to judge whether a specific aspect of an item meets his own expectation. In this paper, we study the problem of estimating personalized sentiment polarities on different aspects of the items. We propose a unified probabilistic model called Factorized Latent Aspect ModEl (FLAME), which combines the advantages of collaborative filtering and aspect based opinion mining. FLAME learns users' personalized preferences on different aspects from their past reviews, and predicts users' aspect ratings on new items by collective intelligence. Experiments on two online review datasets show that FLAME outperforms state-of-the-art methods on the tasks of aspect identification and aspect rating prediction.
Concept Graph Learning from Educational Data
Authors: Yiming Yang, Hanxiao Liu, Jaime G. Carbonell, Wanli Ma
Venue: WSDM
Year: 2015

This paper addresses an open challenge in educational data mining, i.e., the problem of using observed prerequisite relations among courses to learn a directed universal concept graph, and using the induced graph to predict unobserved prerequisite relations among a broader range of courses. This is particularly useful to induce prerequisite relations among courses from different providers (universities, MOOCs, etc.). We propose a new framework for inference within and across two graphs---at the course level and at the induced concept level---which we call Concept Graph Learning (CGL). In the training phase, our system projects the course-level links onto the concept space to induce directed concept links; in the testing phase, the concept links are used to predict (unobserved) prerequisite links for test-set courses within the same institution or across institutions. The dual mappings enable our system to perform an interlingua-style transfer learning, e.g. treating the concept graph as the interlingua, and inducing prerequisite links in a transferable manner across different universities. Experiments on our newly collected data sets of courses from MIT, Caltech, Princeton and CMU show promising results, including the viability of CGL for transfer learning.
The 2nd workshop on Vertical Search Relevance at WSDM 2015
Authors: Dawei Yin, Chih-Chieh Hung, Rui Li, Yi Chang
Venue: WSDM
Year: 2015

As the web information exponentially grows and the needs of users become more specific, traditional general web search engines are not able to perfectly satisfy the nowadays user requirement. Vertical search engines have emerged in various domains, which more focus on specific segments of online content, including local, shopping, medical information, travel search, etc. Vertical search engines start attracting more attention while relevance ranking in different vertical search engines is becoming the key technology. In addition, vertical search results are often slotted into general Web search results. Hence, designing effective ranking functions for vertical search has become practically important to improve users' experience in both web search and vertical search. The workshop bring together researchers from IR, ML, NLP, and other areas of computer and information science, who are working on or interested in this area. It provides a forum for the researchers to identify the issues and the challenges, to share their latest research results, to express a diverse range of opinions about this topic, and to discuss future directions.
Learning About Health and Medicine from Internet Data
Authors: Elad Yom-Tov, Ingemar Johansson Cox, Vasileios Lampos
Venue: WSDM
Year: 2015

Surveys show that around 70% of US Internet users consult the Internet when they require medical information. People seek this information using both traditional search engines and via social media. The information created using the search process offers an unprecedented opportunity for applications to monitor and improve the quality of life of people with a variety of medical conditions. In recent years, research in this area has addressed public-health questions such as the effect of media on development of anorexia, developed tools for measuring influenza rates and assessing drug safety, and examined the effects of health information on individual wellbeing. This tutorial will show how Internet data can facilitate medical research, providing an overview of the state-of-the-art in this area. During the tutorial we will discuss the information which can be gleaned from a variety of Internet data sources, including social media, search engines, and specialized medical websites. We will provide an overview of analysis methods used in recent literature, and show how results can be evaluated using publicly-available health information and online experimentation. Finally, we will discuss ethical and privacy issues and possible technological solutions. This tutorial is intended for researchers of user generated content who are interested in applying their knowledge to improve health and medicine.
HIA'15: Heterogeneous Information Access Workshop at WSDM 2015
Authors: Ke Zhou, Roger Jie Luo, Djoerd Hiemstra, Joemon M. Jose
Venue: WSDM
Year: 2015

The HIA'15 workshop aims to bring together information retrieval practitioners from industry and academic researchers concerned with heterogeneous information access and search federation. We would like to create a forum to encourage discussion and exchange of ideas on heterogeneous information access in different contexts. To facilitate the discussion, we encourage submissions on ideas and results from different aspects of heterogeneous information access including aggregated search, composite retrieval, personal search, structured search, etc. Another objective of the workshop is to encourage submissions with novel ideas (e.g. new applications) on heterogeneous information access and potential future directions of this area.
Boosting Search with Deep Understanding of Contents and Users
Authors: Kaihua Zhu
Venue: WSDM
Year: 2015

Recent years have witnessed dramatic changes in how people interact with search engines. Search engines are expected to be more intelligent in understanding users' intention and fulfilling users' needs with direct answers rather than raw information. Furthermore, search engines are expected to be equipped with recommendation and dialogue capabilities, making the interaction with users more natural and smoother. In this talk, I will introduce Baidu's work on how to make some of them come true through the deep understanding of users, queries and web pages, and discuss challenges behind these technologies.
Leveraging In-Batch Annotation Bias for Crowdsourced Active Learning
Authors: Honglei Zhuang, Joel Young
Venue: WSDM
Year: 2015

Data annotation bias is found in many situations. Often it can be ignored as just another component of the noise floor. However, it is especially prevalent in crowdsourcing tasks and must be actively managed. Annotation bias on single data items has been studied with regard to data difficulty, annotator bias, etc., while annotation bias on batches of multiple data items simultaneously presented to annotators has not been studied. In this paper, we verify the existence of "in-batch annotation bias" between data items in the same batch. We propose a factor graph based batch annotation model to quantitatively capture the in-batch annotation bias, and measure the bias during a crowdsourcing annotation process of inappropriate comments in LinkedIn. We discover that annotators tend to make polarized annotations for the entire batch of data items in our task. We further leverage the batch annotation model to propose a novel batch active learning algorithm. We test the algorithm on a real crowdsourcing platform and find that it outperforms in-batch bias naïve algorithms.