OpenRaiser/Intern-Atlas huggingface dataset:
Everyone's an influencer: quantifying influence on twitter
Authors: Eytan Bakshy, Jake M. Hofman, Winter A. Mason, Duncan J. Watts
Venue: WSDM
Year: 2011

In this paper we investigate the attributes and relative influence of 1.6M Twitter users by tracking 74 million diffusion events that took place on the Twitter follower graph over a two month interval in 2009. Unsurprisingly, we find that the largest cascades tend to be generated by users who have been influential in the past and who have a large number of followers. We also find that URLs that were rated more interesting and/or elicited more positive feelings by workers on Mechanical Turk were more likely to spread. In spite of these intuitive results, however, we find that predictions of which particular user or URL will generate large cascades are relatively unreliable. We conclude, therefore, that word-of-mouth diffusion can only be harnessed reliably by targeting large numbers of potential influencers, thereby capturing average effects. Finally, we consider a family of hypothetical marketing strategies, defined by the relative cost of identifying versus compensating potential "influencers." We find that although under some circumstances, the most influential users are also the most cost-effective, under a wide range of plausible assumptions the most cost-effective performance can be realized using "ordinary influencers"---individuals who exert average or even less-than-average influence.
Quality-biased ranking of web documents
Authors: Michael Bendersky, W. Bruce Croft, Yanlei Diao
Venue: WSDM
Year: 2011

Many existing retrieval approaches do not take into account the content quality of the retrieved documents, although link-based measures such as PageRank are commonly used as a form of document prior. In this paper, we present the quality-biased ranking method that promotes documents containing high-quality content, and penalizes low-quality documents. The quality of the document content can be determined by its readability, layout and ease-of-navigation, among other factors. Accordingly, instead of using a single estimate for document quality, we consider multiple content-based features that are directly integrated into a state-of-the-art retrieval method. These content-based features are easy to compute, store and retrieve, even for large web col-lections. We use several query sets and web collections to empirically evaluate the performance of our quality-biased retrieval method. In each case, our method consistently im-proves by a large margin the retrieval performance of text-based and link-based retrieval methods that do not take into account the quality of the document content.
Document assignment in multi-site search engines
Authors: Ulf Brefeld, Berkant Barla Cambazoglu, Flavio Paiva Junqueira
Venue: WSDM
Year: 2011

Assigning documents accurately to sites is critical for the performance of multi-site Web search engines. In such settings, sites crawl only documents they index and forward queries to obtain best-matching documents from other sites. Inaccurate assignments may lead to inefficiencies when crawling Web pages or processing user queries. In this work, we propose a machine-learned document assignment strategy that uses the locality of document views in search results to decide upon assignments. We evaluate the performance of our strategy using various document features extracted from a large Web collection. Our experimental setup uses query logs from a number of search front-ends spread across different geographic locations and uses these logs to learn the document access patterns. We compare our technique against baselines such as region- and language-based document assignment and observe that our technique achieves substantial performance improvements with respect to recall. With our technique, we are able to obtain a small query forwarding rate (0.04) requiring roughly 45% less replication of documents compared to replicating all documents across all sites.
Introduction to display advertising: a half-day tutorial
Authors: Andrei Z. Broder, Vanja Josifovski, Jayavel Shanmugasundaram
Venue: WSDM
Year: 2011

Display advertising is one of the two major advertising channels on the web (in addition to search advertising). Display advertising on the Web is usually done by graphical ads placed on the publishers' Web pages. There is no explicit user query, and the ad selection is performed based on the page where the ad is placed (contextual targeting) or user's past activities (behavioral targeting). In both cases, sophisticated text analysis and learning algorithms are needed to provide relevant ads to the user. In this tutorial we will overview the display advertising marketplace, and technologies that power the display advertising platforms.
OOLAM: an opinion oriented link analysis model for influence persona discovery
Authors: Keke Cai, Shenghua Bao, Zi Yang, Jie Tang, Rui Ma, Li Zhang, Zhong Su
Venue: WSDM
Year: 2011

Social influence is a complex and subtle force that governs the dynamics of social networks. In the past years, a lot of research work has been conducted to understand the spread patterns of social influence. However, most of approaches assume that influence exists between users with active social interactions, but ignore the question of what kind of influence happens between them. As such one interesting and also fundamental question is raised here: "in a social network, could the social connection reflect users'influence from both positive and negative aspects?". To this end, an Opinion Oriented Link Analysis Model (OOLAM) is proposed in this paper to characterize users' influence personae in order to exhibit their distinguishing influence ability in the social network. In particular, three types of influence personae are generalized and the problem of influence persona discovery is formally defined. Within the OOLAM model, two factors, i.e., opinion consistency and opinion creditability, are defined to capture the persona information from public opinion perspective. Extensive experimental studies have been performed to demonstrate the effectiveness of the proposed approach on influence persona analysis using real web data sets.
User modeling for web applications
Authors: David Carmel, Vanja Josifovski, Yoelle Maarek
Venue: WSDM
Year: 2011

Users have taken a more and more central role in the Web. Their role is both explicit, as they become more savvy, they have more expectations, and new interactive features keep appearing, and implicit, as their actions are monitored at various levels of granularity for various needs from live traffic evaluation for usage data mining to improve ranking, spelling etc. In a few years, most Web applications will have the ability to successfully adapt to both the explicit and implicit needs and tastes of their users. Such adaptation requires the ability to model the user's personal goals, interests, preferences and knowledge, and to apply this model while users interact with various applications. While adaptive applications that are based on user modeling have attracted the attention of multiple communities, from AI to UI, there is no forum that specifically focuses on user modeling and adaptive applications in the Web domain.
Crowdsourcing for search and data mining
Authors: Vitor R. Carvalho, Matthew Lease, Emine Yilmaz
Venue: WSDM
Year: 2011

The advent of crowdsourcing is revolutionizing data annotation, evaluation, and other traditionally manual-labor intensive processes by dramatically reducing the time, cost, and effort involved. This in turn is driving a disruptive shift in search and data mining methodology in areas such as:
Let web spammers expose themselves
Authors: Zhicong Cheng, Bin Gao, Congkai Sun, Yanbing Jiang, Tie-Yan Liu
Venue: WSDM
Year: 2011

This paper is concerned with mining link spams (e.g., link farm and link exchange) from search engine optimization (SEO) forums. To provide quality services, it is critical for search engines to address web spam. Several techniques such as TrustRank, BadRank, and SpamRank have been proposed for this purpose. Most of these methods try to downgrade the effects of the spam websites by identifying specific link patterns of them. However, spam websites have appeared to be more and more similar to normal or even good websites in their link structures, by reforming their spam techniques. As a result, it is very challenging to automatically detect link spams from the Web graph. In this paper, we propose a different approach, which detects link spams by looking at how web spammers make link spam happen. We find that web spammers usually ally with each other, and SEO forum is one of the major means for them to form the alliance. We therefore propose mining suspicious link spams directly from the posts in the SEO forums. However, the task is non-trivial because there are also other information and even noises contained in these posts, in addition to useful clues of link spam. To tackle the challenges, we first extract all the URLs contained in the posts of the SEO forums. Second, we extract features for the URLs from their relationships with forum users (potential spammers) and from their link structure in the web graph. Third, we build a semi-supervised learning framework to calculate the spam scores for the URLs, which encodes several heuristics such as spam websites usually linking to each other, and good websites seldom linking to spam websites. We tested our approach on seven major SEO forums. A lot of spam websites were identified, a significant proportion of which cannot be detected by conventional anti-spam methods. It indicates that the proposed approach can be a good complement of existing anti-spam techniques.
Optimizing two-dimensional search results presentation
Authors: Flavio Chierichetti, Ravi Kumar, Prabhakar Raghavan
Venue: WSDM
Year: 2011

Classic search engine results are presented as an ordered list of documents and the problem of presentation trivially reduces to ordering documents by their scores. This is because users scan a list presentation from top to bottom. This leads to natural list optimization measures such as the discounted cumulative gain (DCG) and the rank-biased precision (RBP).
A comparative analysis of cascade measures for novelty and diversity
Authors: Charles L. A. Clarke, Nick Craswell, Ian Soboroff, Azin Ashkan
Venue: WSDM
Year: 2011

Traditional editorial effectiveness measures, such as nDCG, remain standard for Web search evaluation. Unfortunately, these traditional measures can inappropriately reward redundant information and can fail to reflect the broad range of user needs that can underlie a Web query. To address these deficiencies, several researchers have recently proposed effectiveness measures for novelty and diversity. Many of these measures are based on simple cascade models of user behavior, which operate by considering the relationship between successive elements of a result list. The properties of these measures are still poorly understood, and it is not clear from prior research that they work as intended. In this paper we examine the properties and performance of cascade measures with the goal of validating them as tools for measuring effectiveness. We explore their commonalities and differences, placing them in a unified framework; we discuss their theoretical difficulties and limitations, and compare the measures experimentally, contrasting them against traditional measures and against other approaches to measuring novelty. Data collected by the TREC 2009 Web Track is used as the basis for our experimental comparison. Our results indicate that these measures reward systems that achieve an balance between novelty and overall precision in their result lists, as intended. Nonetheless, other measures provide insights not captured by the cascade measures, and we suggest that future evaluation efforts continue to report a variety of measures.
Enhanced email spam filtering through combining similarity graphs
Authors: Anirban Dasgupta, Maxim Gurevich, Kunal Punera
Venue: WSDM
Year: 2011

Over the last decade Email Spam has evolved from being just an irritant to users to being truly dangerous. This has led web-mail providers and academic researchers to dedicate considerable resources towards tackling this problem [9, 21, 22, 24, 26]. However, we argue that some aspects of the spam filtering problem are not handled appropriately in existing work. Principal among these are adversarial spammer efforts -- spammers routinely tune their spam emails to bypass spam-filters, and contaminate ground truth via fake HAM/SPAM votes -- and the scale and sparsity of the problem, which essentially precludes learning with a very large set of parameters.
Batch query processing for web search engines
Authors: Shuai Ding, Josh Attenberg, Ricardo Baeza-Yates, Torsten Suel
Venue: WSDM
Year: 2011

Large web search engines are now processing billions of queries per day. Most of these queries are interactive in nature, requiring a response in fractions of a second. However, there are also a number of important scenarios where large batches of queries are submitted for various web mining and system optimization tasks that do not require an immediate response. Given the significant cost of executing search queries over billions of web pages, it is a natural question to ask if such batches of queries can be more efficiently executed than interactive queries.
Multi-dimensional search result diversification
Authors: Zhicheng Dou, Sha Hu, Kun Chen, Ruihua Song, Ji-Rong Wen
Venue: WSDM
Year: 2011

Most existing search result diversification algorithms diversify search results in terms of a specific dimension. In this paper, we argue that search results should be diversified in a multi-dimensional way, as queries are usually ambiguous at different levels and dimensions. We first explore mining subtopics from four types of data sources, including anchor texts, query logs, search result clusters, and web sites. Then we propose a general framework that explicitly diversifies search results based on multiple dimensions of subtopics. It balances the relevance of documents with respect to the query and the novelty of documents by measuring the coverage of subtopics. Experimental results on the TREC 2009 Web track dataset indicate that combining multiple types of subtopics do help better understand user intents. By incorporating multiple types of subtopics, our models improve the diversity of search results over the sole use of one of them, and outperform two state-of-the-art models.
A combined topical/non-topical approach to identifying web sites for children
Authors: Carsten Eickhoff, Pavel Serdyukov, Arjen P. de Vries
Venue: WSDM
Year: 2011

Today children interact more and more frequently with information services. Especially in on-line scenarios there is a great amount of content that is not suitable for their age group. Due to the growing importance and ubiquity of the Internet in today's world, denying children any unsupervised Web access is often not possible. This work presents an automatic way of distinguishing web pages for children from those for adults in order to improve child-appropriate web search engine performance. A range of 80 different features based on findings from cognitive sciences and children's psychology are discussed and evaluated. We conducted a large scale user study on the suitability of web sites and give detailed information about the insights gained. Finally a comparison to traditional web classification methods as well as human annotator performance reveals that our automatic classifier can reach a performance close to that of human agreement.
Mining billion-node graphs: patterns, generators and tools
Authors: Christos Faloutsos
Venue: WSDM
Year: 2011

What do graphs look like? How do they evolve over time? How to handle a graph with a billion nodes? We present a comprehensive list of static and temporal laws, and some recent observations on real graphs (like, e.g., "eigenSpokes"). For generators, we describe some recent ones, which naturally match all of the known properties of real graphs. Finally, for tools, we present "oddBall" for discovering anomalies and patterns, as well as an overview of the PEGASUS system which is designed for handling Billion-node graphs, running on top of the "hadoop" system.
Learning website hierarchies for keyword enrichment in contextual advertising
Authors: Pavan Kumar GM, Krishna P. Leela, Mehul Parsana, Sachin Garg
Venue: WSDM
Year: 2011

In Contextual advertising, textual ads relevant to the content in a webpage are embedded in the page. Content keywords are extracted offline by crawling webpages and then stored in an index for fast serving. Given a page, ad selection involves index lookup, computing similarity between the keywords of the page and those of candidate ads and returning the top-k scoring ads. In this approach, ad relevance can suffer in two scenarios. First, since page-ad similarity is computed using keywords extracted only from that particular page, a few non pertinent keywords can skew ad selection. Second, requesting page may not be present in the index but we still need to serve relevant ads.
Exploiting statistical and relational information on the web and in social media
Authors: Lise Getoor, Lilyana Mihalkova
Venue: WSDM
Year: 2011

The popularity of Web 2.0, characterized by a proliferation of social media sites, and Web 3.0, with more richly semantically annotated objects and relationships, brings to light a variety of important prediction, ranking, and extraction tasks. The input to these tasks is often best seen as a (noisy) multi-relational graph, such as the click graph, defined by user interactions with Web sites; and the social graph, defined by friendships and affiliations on social media sites.This tutorial will provide an overview of statistical relational learning and inference techniques, motivating and illustrating them using web and social media applications. We will start by briefly surveying some of the sources of statistical and relational information on the web and in social media and will then dedicate most of the tutorial time to an introduction to representations and techniques for learning and reasoning with multi-relational information, viewing them through the lens of web and social media domains. We will end with a discussion of current trends and related fields, such as privacy in social networks.
Adaptive bootstrapping of recommender systems using decision trees
Authors: Nadav Golbandi, Yehuda Koren, Ronny Lempel
Venue: WSDM
Year: 2011

Recommender systems perform much better on users for which they have more information. This gives rise to a problem of satisfying users new to a system. The problem is even more acute considering that some of these hard to profile new users judge the unfamiliar system by its ability to immediately provide them with satisfying recommendations, and may quickly abandon the system when disappointed. Rapid profiling of new users by a recommender system is often achieved through a bootstrapping process - a kind of an initial interview - that elicits users to provide their opinions on certain carefully chosen items or categories. The elicitation process becomes particularly effective when adapted to users' responses, making best use of users' time by dynamically modifying the questions to improve the evolving profile. In particular, we advocate a specialized version of decision trees as the most appropriate tool for this task. We detail an efficient tree learning algorithm, specifically tailored to the unique properties of the problem. Several extensions to the tree construction are also introduced, which enhance the efficiency and utility of the method. We implemented our methods within a movie recommendation service. The experimental study delivered encouraging results, with the tree-based bootstrapping process significantly outperforming previous approaches.
Large-scale hierarchical text classification without labelled data
Authors: Viet Ha-Thuc, Jean-Michel Renders
Venue: WSDM
Year: 2011

The traditional machine learning approaches for text classification often require labelled data for learning classifiers. However, when applied to large-scale classification involving thousands of categories, creating such labelled data is extremely expensive since typically the data is manually labelled by humans. Motivated by this, we propose a novel approach for large-scale hierarchical text classification which does not require any labelled data. We explore a perspective where the meaning of a category is not defined by human-labelled documents, but by its description and more importantly its relationships with other categories (e.g. its ascendants and descendants). Specifically, we take advantage of the ontological knowledge in all phases of the whole process, namely when retrieving pseudo-labelled documents, when iteratively training the category models and when categorizing test documents. Our experiments based on a taxonomy containing 1131 categories and widely adopted in the news industry as a standard for the NewsML framework demonstrate the effectiveness of our approach in these phases both qualitatively and quantitatively. In particular, we emphasize that just by taking the simple ontological knowledge defined in the category hierarchy, we could automatically build a large-scale hierarchical classifier with reasonable performance of 67% in terms of the hierarchy-based F-1 measure.
Query suggestion for E-commerce sites
Authors: Mohammad Al Hasan, Nish Parikh, Gyanit Singh, Neel Sundaresan
Venue: WSDM
Year: 2011

Query suggestion module is an integral part of every search engine. It helps search engine users narrow or broaden their searches. Published work on query suggestion methods has mainly focused on the web domain. But, the module is also popular in the domain of e-commerce for product search. In this paper, we discuss query suggestion and its methodologies in the context of e-commerce search engines. We show that dynamic inventory combined with long and sparse tail of query distribution poses unique challenges to build a query suggestion method for an e-commerce marketplace. We compare and contrast the design of a query suggestion system for web search engines and e-commerce search engines. Further, we discuss interesting measures to quantify the effectiveness of our query suggestion methodologies. We also describe the learning gained from exposing our query suggestion module to a vibrant community of millions of users.
Inferring search behaviors using partially observable markov model with duration (POMD)
Authors: Yin He, Kuansan Wang
Venue: WSDM
Year: 2011

This paper presents Partially Observable Markov model with Duration (POMD), a statistical method that addresses the challenge of understanding sophisticated user behaviors from the search log in which some user actions, such as reading and skipping search results, cannot be observed and recorded. POMD utilizes not only the positional but also the temporal information of the clicks in the log. In this work, we treat the user engagements with a search engine as a Markov process, and model the unobservable engagements as hidden states. POMD differs from the traditional hidden Markov model (HMM) in that not all the hidden state transitions emit observable events, and that the duration of staying in each state is explicitly factored into the core statistical model. To address the training and decoding issues emerged as the results of the variations, we propose an iterative two-stage training algorithm and a greedy segmental decoding algorithm respectively. We validate the proposed algorithm with two sets of experiments. First, we show that the search behavioral patterns inferred by POMD match well with those reported in the eye tracking experiments. Secondly, through a series of A/B comparison experiments, we demonstrate that POMD can distinguish the ranking qualities of different search engine configurations much better than the patterns inferred by the model proposed in the previous work. Both of the experimental results suggest that POMD can provide a statistical and quantitative way to understand the sophisticated search behaviors by simply mining the search logs.