OpenRaiser/Intern-Atlas huggingface dataset:
Efficient entity resolution for large heterogeneous information spaces
Authors: George Papadakis, Ekaterini Ioannou, Claudia Niederée, Peter Fankhauser
Venue: WSDM
Year: 2011

We have recently witnessed an enormous growth in the volume of structured and semi-structured data sets available on the Web. An important prerequisite for using and combining such data sets is the detection and merge of information that describes the same real-world entities, a task known as Entity Resolution. To make this quadratic task efficient, blocking techniques are typically employed. However, the high dynamics, loose schema binding, and heterogeneity of (semi-)structured data, impose new challenges to entity resolution. Existing blocking approaches become inapplicable because they rely on the homogeneity of the considered data and a-priory known schemata. In this paper, we introduce a novel approach for entity resolution, scaling it up for large, noisy, and heterogeneous information spaces. It combines an attribute-agnostic mechanism for building blocks with intelligent block processing techniques that boost blocks with high expected utility, propagate knowledge about identified matches, and preempt the resolution process when it gets too expensive. Our extensive evaluation on real-world, large, heterogeneous data sets verifies that the suggested approach is both effective and efficient.
A probabilistic approach for learning folksonomies from structured data
Authors: Anon Plangprasopchok, Kristina Lerman, Lise Getoor
Venue: WSDM
Year: 2011

Learning structured representations has emerged as an important problem in many domains, including document and Web data mining, bioinformatics, and image analysis. One approach to learning complex structures is to integrate many smaller, incomplete and noisy structure fragments. In this work, we present an unsupervised probabilistic approach that extends affinity propagation [7] to combine the small ontological fragments into a collection of integrated, consistent, and larger folksonomies. This is a challenging task because the method must aggregate similar structures while avoiding structural inconsistencies and handling noise. We validate the approach on a real-world social media dataset, comprised of shallow personal hierarchies specified by many individual users, collected from the photosharing website Flickr. Our empirical results show that our proposed approach is able to construct deeper and denser structures, compared to an approach using only the standard affinity propagation algorithm. Additionally, the approach yields better overall integration quality than a state-of-the-art approach based on incremental relational clustering.
eBay: an E-commerce marketplace as a complex network
Authors: Zeqian Shen, Neel Sundaresan
Venue: WSDM
Year: 2011

Commerce networks involve buying and selling activities among individuals or organizations. As the growing of the Internet and e-commerce, it brings opportunities for obtaining real world online commerce networks, which are magnitude larger than before. Getting a deeper understanding of e-commerce networks, such as the eBay marketplace, in terms of what structure they have, what kind of interactions they afford, what trust and reputation measures exist, and how they evolve has tremendous value in suggesting business opportunities and building effective user applications. In this paper, we modeled the eBay network as a complex network. We analyzed the macroscopic shape of the network using degree distribution and the bow-tie model. Networks of different eBay categories are also compared. The results suggest that the categories vary from collector networks to retail networks. We also studied the local structures of the networks using motif profiling. Finally, patterns of preferential connections are visually analyzed using Auroral diagrams.
Linking online news and social media
Authors: Manos Tsagkias, Maarten de Rijke, Wouter Weerkamp
Venue: WSDM
Year: 2011

Much of what is discussed in social media is inspired by events in the news and, vice versa, social media provide us with a handle on the impact of news events. We address the following linking task: given a news article, find social media utterances that implicitly reference it. We follow a three-step approach: we derive multiple query models from a given source news article, which are then used to retrieve utterances from a target social media index, resulting in multiple ranked lists that we then merge using data fusion techniques. Query models are created by exploiting the structure of the source article and by using explicitly linked social media utterances that discuss the source article. To combat query drift resulting from the large volume of text, either in the source news article itself or in social media utterances explicitly linked to it, we introduce a graph-based method for selecting discriminative terms. For our experimental evaluation, we use data from Twitter, Digg, Delicious, the New York Times Community, Wikipedia, and the blogosphere to generate query models. We show that different query models, based on different data sources, provide complementary information and manage to retrieve different social media utterances from our target index. As a consequence, data fusion methods manage to significantly boost retrieval performance over individual approaches. Our graph-based term selection method is shown to help improve both effectiveness and efficiency.
Scalable clustering of news search results
Authors: Srinivas Vadrevu, Choon Hui Teo, Suju Rajan, Kunal Punera, Byron Dom, Alexander J. Smola, Yi Chang, Zhaohui Zheng
Venue: WSDM
Year: 2011

In this paper, we present a system for clustering the search results of a news search engine. The news search interface includes the relevant news articles to a given query organized in terms of related news stories. Here each cluster corresponds to a news story and the news articles are clustered into stories. We present a system that clusters the search results of a news search system in a fast and scalable manner. The clustering system is organized into three components including offline clustering, incremental clustering and realtime clustering. We propose novel techniques for clustering the search results in realtime. The experimental results with large collections of news documents reveal that our system is both scalable and also achieves good accuracy in clustering the news search results.
On the selection of tags for tag clouds
Authors: Petros Venetis, Georgia Koutrika, Hector Garcia-Molina
Venue: WSDM
Year: 2011

We examine the creation of a tag cloud for exploring and understanding a set of objects (e.g., web pages, documents). In the first part of our work, we present a formal system model for reasoning about tag clouds. We then present metrics that capture the structural properties of a tag cloud, and we briefly present a set of tag selection algorithms that are used in current sites (e.g., del.icio.us, Flickr, Technorati) or that have been described in recent work. In order to evaluate the results of these algorithms, we devise a novel synthetic user model. This user model is specifically tailored for tag cloud evaluation and assumes an "ideal" user. We evaluate the algorithms under this user model, as well as the model itself, using two datasets: CourseRank (a Stanford social tool containing information about courses) and del.icio.us (a social bookmarking site). The results yield insights as to when and why certain selection schemes work best.
Action prediction and identification from mining temporal user behaviors
Authors: Dakan Wang, Gang Wang, Xiaofeng Ke, Weizhu Chen
Venue: WSDM
Year: 2011

Predicting user's action provides many monetization opportunities to web service providers. If a user's future action can be predicted and identified correctly in time or in advance, we cannot only satisfy user's current need, but also facilitate and simplify user's future online activities. Traditional works on user behavior modeling such as implicit feedback or personalization mainly investigate on users' immediate, short-term or aggregate behaviors. Hence, it is difficult to understand the diversity in temporal user behavior and predict user's future action. In this paper, we consider a forecasting problem of temporal user behavior modeling. Our first objective is able to capture relevant users that will perform an action. The second objective is able to identify whether a user has finished the action, even when the action happened offline. We propose an ensemble algorithm to achieve both objectives. The experiment compares several implementation methods and demonstrates the temporal user behavior modeling using the ensemble algorithm significantly outperforms other methods.
Who uses web search for what: and how
Authors: Ingmar Weber, Alejandro Jaimes
Venue: WSDM
Year: 2011

We analyze a large query log of 2.3 million anonymous registered users from a web-scale U.S. search engine in order to jointly analyze their on-line behavior in terms of who they might be (demographics), what they search for (query topics), and how they search (session analysis). We examine basic demographics from registration information provided by the users, augmented with U.S. census data, analyze basic session statistics, classify queries into types (navigational, informational, transactional) based on click entropy, classify queries into topic categories, and cluster users based on the queries they issued. We then examine the resulting clusters in terms of demographics and search behavior. Our analysis of the data suggests that there are important differences in search behavior across different demographic groups in terms of the topics they search for, and how they search (e.g., white conservatives are those likely to have voted republican, mostly white males, who search for business, home, and gardening related topics; Baby Boomers tend to be primarily interested in Finance and a large fraction of their sessions consist of simple navigational queries related to online banking, etc.). Finally, we examine regional search differences, which seem to correlate with differences in local industries (e.g., gambling related queries are highest in Las Vegas and lowest in Salt Lake City; searches related to actors are about three times higher in L.A. than in any other region).
Normalizing web product attributes and discovering domain ontology with minimal effort
Authors: Tak-Lam Wong, Lidong Bing, Wai Lam
Venue: WSDM
Year: 2011

We have developed a framework aiming at normalizing product attributes from Web pages collected from different Web sites without the need of labeled training examples. It can deal with pages composed of different layout format and content in an unsupervised manner. As a result, it can handle a variety of different domains with minimal effort. Our model is based on a generative probabilistic graphical model incorporated with Hidden Markov Models (HMM) considering both attribute names and attribute values to extract and normalize text fragments from Web pages in a unified manner. Dirichlet Process is employed to handle the unlimited number of attributes in a domain. An unsupervised inference method is proposed to predict the unobservable variables. We have also developed a method to automatically construct a domain ontology using the normalized product attributes which are the output of the inference on the graphical model. We have conducted extensive experiments and compared with existing works using prouct Web pages collected from real-world Web sites in three different domains to demonstrate the effectiveness of our framework.
Evaluating the visual quality of web pages using a computational aesthetic approach
Authors: Ou Wu, Yunfei Chen, Bing Li, Weiming Hu
Venue: WSDM
Year: 2011

Current Web mining explores useful and valuable information (content) online for users. However, there is scant research on the overall visual aspect of Web pages, even though visual elements such as aesthetics significantly influence user experience. A beautiful and well-laid out Web page greatly facilitates users' accessing and enhances browsing experiences.We use "visual quality (VisQ)" to denote the aesthetics of Web pages. In this paper, a computational aesthetics approach is proposed to learn the evaluation model for the visual quality of Web pages. First, a Web page layout extraction algorithm (V-LBE) is introduced to partition a Web page into major layout blocks. Then, regarding a Web page as a semi-structured image, features (e.g., layout,visual complexity, colorfulness) known to significantly affect the visual quality of a Web page are extracted to construct a feature vector. We present a multi-cost-sensitive learning for visual quality classification and a multi-value regression for visual quality score assignment. Our experiments compare the extracted features and conclude that the Web page's layout visual features (LV) and text visual features (TV) are the primary affecting factors toward Web page's visual quality. The performance of the learned visual quality classifier is close to some persons'. The learned regression function also achieves promising results.
CMAP: effective fusion of quality and relevance for multi-criteria recommendation
Authors: Xin Xin, Michael R. Lyu, Irwin King
Venue: WSDM
Year: 2011

The research issue of recommender systems has been treated as a classical regression problem over the decades and has obtained a great success. In the next generation of recommender systems, multi-criteria recommendation has been predicted as an important direction. Different from traditional recommender systems that aim particularly at recommending high-quality items evaluated by users' ratings, inmulti-criteria recommendation, quality only serves as one criterion, and many other criteria such as relevance, coverage, and diversity should be simultaneously optimized. Although recently there is work investigating each single criterion, there is rarely any literature that reports how each single criterion impacts each other and how to combine them in real applications. Thus in this paper, we study the relationship of two criteria, quality and relevance, as a preliminary work in multi-criteria recommendation. We first give qualitative and quantitative analysis of competitive quality-based and relevance-based algorithms in these two criteria to show that both algorithms cannot work well in the opposite criteria. Then we propose an integrated metric and finally investigate how to combine previous work together into an unified model. In the combination, we introduce a Continuous-time MArkov Process (CMAP) algorithm for ranking, which enables principled and natural integration with features derived from both quality-based and relevance-based algorithms. Through experimental verification, the combined methods can significantly outperform either single quality-based or relevance-based algorithms in the integrated metric and the CMAP model outperforms traditional combination methods by around 3%. Its linear complexity with respect to the number of users and items leads to satisfactory performance, as demonstrated by the around 7-hour computational time for over 480k users and almost 20k items.
Learning similarity function for rare queries
Authors: Jingfang Xu, Gu Xu
Venue: WSDM
Year: 2011

The key element of many query processing tasks can be formalized as calculation of similarities between queries. These include query suggestion, query reformulation, and query expansion. Although many methods have been proposed for query similarity calculation, they could perform poorly on rare queries. As far as we know, there was no previous work particularly about rare query similarity calculation, and this paper tries to study this problem. Specifically, we address three problems. Firstly, we define an n-gram space to represent queries with their own content and a similarity function to measure the similarities between queries. Secondly, we propose learning the similarity function by leveraging the training data derived from user behavior data. This is formalized as an optimization problem and a metric learning approach is employed to solve it efficiently. Finally, we exploit locality sensitive hashing for efficient retrieval of similar queries from a large query repository. We experimentally verified the effectiveness of the proposed approach by showing that our method can indeed enhance the accuracy of query similarity calculation for rare queries and efficiently retrieve similar queries. As an application, we also experimentally demonstrated that the similar queries found by our method can significantly improve search relevance.
Strength of social influence in trust networks in product review sites
Authors: Ching-man Au Yeung, Tomoharu Iwata
Venue: WSDM
Year: 2011

Some popular product review sites such as Epinions allow users to establish a trust network among themselves, indicating who they trust in providing product reviews and ratings. While trust relations have been found to be useful in generating personalised recommendations, the relations between trust and product ratings has so far been overlooked. In this paper, we examine large datasets collected from Epinions and Ciao, two popular product review sites. We discover that in general users who trust each other tend to have smaller differences in their ratings as time passes, giving support to the theories of homophily and social influence. However, we also discover that this does not hold true across all trusted users. A trust relation does not guarantee that two users have similar preferences, implying that personalised recommendations based on trust relations do not necessarily produce more accurate predictions. We propose a method to estimate the strengths of trust relations so as to estimate the true influence among the trusted users. Our method extends the popular matrix factorisation technique for collaborative filtering, which allow us to generate more accurate rating predictions at the same time. We also show that the estimated strengths of trust relations correlate with the similarity among the users. Our work contributes to the understanding of the interplay between trust relations and product ratings, and suggests that trust networks may serve as a more general socialising venue than only an indication of similarity in user preferences.
A two-view learning approach for image tag ranking
Authors: Jinfeng Zhuang, Steven C. H. Hoi
Venue: WSDM
Year: 2011

Tags of social images play a central role for text-based social image retrieval and browsing tasks. However, the original tags annotated by web users could be noisy, irrelevant, and often incomplete for describing the image contents, which may severely deteriorate the performance of text-based image retrieval models. In this paper, we aim to overcome the challenge of social tag ranking for a corpus of social images with rich user-generated tags by proposing a novel two-view learning approach. It can effectively exploit both textual and visual contents of social images to discover the complicated relationship between tags and images. Unlike the conventional learning approaches that usually assume some parametric models, our method is completely data-driven and makes no assumption of the underlying models, making the proposed solution practically more effective. We formally formulate our method as an optimization task and present an efficient algorithm to solve it. To evaluate the efficacy of our method, we conducted an extensive set of experiments by applying our technique to both text-based social image retrieval and automatic image annotation tasks, in which encouraging results showed that the proposed method is more effective than the conventional approaches.
Sponsored search auctions with conflict constraints
Authors: Panagiotis Papadimitriou, Hector Garcia-Molina
Venue: WSDM
Year: 2012

In sponsored search auctions advertisers compete for ad slots in the search engine results page, by bidding on keywords of interest. To improve advertiser expressiveness, we augment the bidding process with conflict constraints. With such constraints, advertisers can condition their bids on the non-appearance of certain undesired ads on the results page. We study the complexity of the allocation problem in these augmented SSA and we introduce an algorithm that can efficiently allocate the ad slots to advertisers. We evaluate the algorithm run time in simulated conflict scenarios and we study the implications of the conflict constraints on search engine revenue. Our results show that the allocation problem can be solved within few tens of milliseconds and that the adoption of conflict constraints can potentially increase search engine revenue.
Mining, searching and exploiting collaboratively generated content on the web
Authors: Eugene Agichtein, Evgeniy Gabrilovich
Venue: WSDM
Year: 2012

Proliferation of ubiquitous access to the Internet enables millions of Web users to collaborate online on a variety of activities. Many of these activities result in the construction of large repositories of knowledge, either as their primary aim (e.g., Wikipedia) or as a by-product (e.g., Yahoo! Answers). In this tutorial, we will discuss organizing and exploiting Collaboratively Generated Content (CGC) for information organization and retrieval. Specifically, we intend to cover two complementary areas of the problem: (1) using such content as a powerful enabling resource for knowledge-enriched, intelligent representations and new information retrieval algorithms, and (2) development of supporting technologies for extracting, filtering, and organizing collaboratively created content.
Scalable inference in latent variable models
Authors: Amr Ahmed, Mohamed Aly, Joseph Gonzalez, Shravan M. Narayanamurthy, Alexander J. Smola
Venue: WSDM
Year: 2012

Latent variable techniques are pivotal in tasks ranging from predicting user click patterns and targeting ads to organizing the news and managing user generated content. Latent variable techniques like topic modeling, clustering, and subspace estimation provide substantial insight into the latent structure of complex data with little or no external guidance making them ideal for reasoning about large-scale, rapidly evolving datasets. Unfortunately, due to the data dependencies and global state introduced by latent variables and the iterative nature of latent variable inference, latent-variable techniques are often prohibitively expensive to apply to large-scale, streaming datasets. In this paper we present a scalable parallel framework for efficient inference in latent variable models over streaming web-scale data. Our framework addresses three key challenges: 1) synchronizing the global state which includes global latent variables (e.g., cluster centers and dictionaries); 2) efficiently storing and retrieving the large local state which includes the data-points and their corresponding latent variables (e.g., cluster membership); and 3) sequentially incorporating streaming data (e.g., the news). We address these challenges by introducing: 1) a novel delta-based aggregation system with a bandwidth-efficient communication protocol; 2) schedule-aware out-of-core storage; and 3) approximate forward sampling to rapidly incorporate new data. We demonstrate state-of-the-art performance of our framework by easily tackling datasets two orders of magnitude larger than those addressed by the current state-of-the-art. Furthermore, we provide an optimized and easily customizable open-source implementation of the framework1.