OpenRaiser/Intern-Atlas huggingface dataset:
Compression-aware I/O performance analysis for big data clustering
Authors: Zhenghua Xue, Geng Shen, Jianhui Li, Qian Xu, Yang Zhang, Jing Shao
Venue: KDD
Year: 2012

As the data volume increases, I/O bottleneck has become a great challenge for data analysis. Data compression can alleviate the bottleneck effectively. Taking K-means algorithm as an example, this paper proposes a compression-aware performance improvement model for big-data clustering. The model quantitatively analyzes the effect of a variety of factors related to compression during the entire computational process. We perform clustering experiments on 10 dimensional data with up to 1.114 TB in size on a cluster computer with hundreds of computing cores. The measurement validates that using compression contributes significantly to improving the I/O performance, and confirms our theoretical analysis empirically. Furthermore, the proposed model can effectively determine when and how to use compression to improve I/O performance for big-data analysis.
Incrementally optimized decision tree for noisy big data
Authors: Yang Hang, Simon Fong
Venue: KDD
Year: 2012

How to extract meaningful information from big data has been a popular open problem. Decision tree, which has a high degree of knowledge interpretation, has been favored in many real world applications. However noisy values commonly exist in high-speed data streams, e.g. real-time online data feeds that are prone to interference. When processing big data, it is hard to implement pre-processing and sampling in full batches. To solve this tradeoff, this paper proposes a new incremental decision tree algorithm so called incrementally optimized very fast decision tree (iOVFDT). The experiment evaluates the proposed algorithm in comparison to existing methods under noisy data streams environment. Result shows iOVFDT has outperformance on the aspects of higher accuracy and smaller model size.
Circle-based recommendation in online social networks
Authors: Xiwang Yang, Harald Steck, Yong Liu
Venue: KDD
Year: 2012

Online social network information promises to increase recommendation accuracy beyond the capabilities of purely rating/feedback-driven recommender systems (RS). As to better serve users' activities across different domains, many online social networks now support a new feature of "Friends Circles", which refines the domain-oblivious "Friends" concept. RS should also benefit from domain-specific "Trust Circles". Intuitively, a user may trust different subsets of friends regarding different domains. Unfortunately, in most existing multi-category rating datasets, a user's social connections from all categories are mixed together. This paper presents an effort to develop circle-based RS. We focus on inferring category-specific social trust circles from available rating data combined with social network data. We outline several variants of weighting friends within circles based on their inferred expertise levels. Through experiments on publicly available data, we demonstrate that the proposed circle-based recommendation models can better utilize user's social trust information, resulting in increased recommendation accuracy.
USpan: an efficient algorithm for mining high utility sequential patterns
Authors: Junfu Yin, Zhigang Zheng, Longbing Cao
Venue: KDD
Year: 2012

Sequential pattern mining plays an important role in many applications, such as bioinformatics and consumer behavior analysis. However, the classic frequency-based framework often leads to many patterns being identified, most of which are not informative enough for business decision-making. In frequent pattern mining, a recent effort has been to incorporate utility into the pattern selection framework, so that high utility (frequent or infrequent) patterns are mined which address typical business concerns such as dollar value associated with each pattern. In this paper, we incorporate utility into sequential pattern mining, and a generic framework for high utility sequence mining is defined. An efficient algorithm, USpan, is presented to mine for high utility sequential patterns. In USpan, we introduce the lexicographic quantitative sequence tree to extract the complete set of high utility sequences and design concatenation mechanisms for calculating the utility of a node and its children with two effective pruning strategies. Substantial experiments on both synthetic and real datasets show that USpan efficiently identifies high utility sequences from large scale data with very low minimum utility.
Transductive multi-label ensemble classification for protein function prediction
Authors: Guo-Xian Yu, Carlotta Domeniconi, Huzefa Rangwala, Guoji Zhang, Zhiwen Yu
Venue: KDD
Year: 2012

Advances in biotechnology have made available multitudes of heterogeneous proteomic and genomic data. Integrating these heterogeneous data sources, to automatically infer the function of proteins, is a fundamental challenge in computational biology. Several approaches represent each data source with a kernel (similarity) function. The resulting kernels are then integrated to determine a composite kernel, which is used for developing a function prediction model. Proteins are also found to have multiple roles and functions. As such, several approaches cast the protein function prediction problem within a multi-label learning framework. In our work we develop an approach that takes advantage of several unlabeled proteins, along with multiple data sources and multiple functions of proteins. We develop a graph-based transductive multi-label classifier (TMC) that is evaluated on a composite kernel, and also propose a method for data integration using the ensemble framework, called transductive multi-label ensemble classifier (TMEC). The TMEC approach trains a graph-based multi-label classifier for each individual kernel, and then combines the predictions of the individual models. Our contribution is the use of a bi-relational directed graph that captures relationships between pairs of proteins, between pairs of functions, and between proteins and functions. We evaluate the ability of TMC and TMEC to predict the functions of proteins by using two yeast datasets. We show that our approach performs better than recently proposed protein function prediction methods on composite and multiple kernels.
Query-driven discovery of semantically similar substructures in heterogeneous networks
Authors: Xiao Yu, Yizhou Sun, Peixiang Zhao, Jiawei Han
Venue: KDD
Year: 2012

Heterogeneous information networks that contain multiple types of objects and links are ubiquitous in the real world, such as bibliographic networks, cyber-physical networks, and social media networks. Although researchers have studied various data mining tasks in information networks, interactive query-based network exploration techniques have not been addressed systematically, which, in fact, are highly desirable for exploring large-scale information networks.
BC-PDM: data mining, social network analysis and text mining system based on cloud computing
Authors: Le Yu, Jian Zheng, Wei Chong Shen, Bin Wu, Bai Wang, Long Qian, Bo Ren Zhang
Venue: KDD
Year: 2012

Telecom BI(Business Intelligence) system consists of a set of application programs and technologies for gathering, storing, analyzing and providing access to data, which contribute to manage business information and make decision precisely. However, traditional analysis algorithms meet new challenges as the continued exponential growth in both the volume and the complexity of telecom data. With the Cloud Computing development, some parallel data analysis systems have been emerging. However, existing systems have rarely comprehensive function, either providing data analysis service or providing social network analysis. We need a comprehensive tool to store and analysis large scale data efficiently. In response to the challenge, the SaaS (Software-as-a-Service) BI system, BC-PDM (Big Cloud-Parallel Data Mining), are proposed. BC-PDM supports parallel ETL process, statistical analysis, data mining, text mining and social network analysis which are based on Hadoop. This demo introduces three tasks: business recommendation, customer community detection and user preference classification by employing a real telecom data set. Experimental results show BC-PDM is very efficient and effective for intelligence data analysis.
A parallel graph partitioning algorithm to speed up the large-scale distributed graph mining
Authors: Zengfeng Zeng, Bin Wu, Haoyu Wang
Venue: KDD
Year: 2012

For the large-scale distributed graph mining, the graph is distributed over a cluster of nodes, thus performing computations on the distributed graph is expensive when large amount of data have to be moved between different computers. A good partitioning of distributed graph is needed to reduce the communication between computers and scale a system up. Existing graph partitioning algorithms incur high computation and communication cost when applied on large distributed graphs. A efficient and scalable partitioning algorithm is crucial for large-scale distributed graph mining.
A new challenge of information processing under the 21st century
Authors: Bo Zhang
Venue: KDD
Year: 2012

In web era, we are confronted with a huge amount of raw data and a tremendous change of man-machine interaction modes. We have to deal with the content (semantics) of data rather than their form alone. Traditional information processing approaches face a new challenge since they cannot deal with the semantic meaning or content of information. But humans can handle such a problem easily. So it's needed a new information processing strategy that correlated with the content of information by learning some mechanisms from human beings. Therefore, we need (1) a set of robust detectors for detecting semantically meaningful features such as boundaries, shapes, etc. in images, words, sentences, etc. in text, and (2) a set of methods that can effectively analyze and exploit the information structures that encode the content of information. During the past 40 years the probability theory has made a great progress. It has provided a set of mathematical tools for representing and analyzing information structures. In the talk we will discuss what difficulty we face, what we can do, and how we should do in the content-based information processing.
Keyword-propagation-based information enriching and noise removal for web news videos
Authors: Jun Zhang, Xiaoming Fan, Jianyong Wang, Lizhu Zhou
Venue: KDD
Year: 2012

The volume of Web videos have increased sharply through the past several years because of the evolvement of Web video sites.Enhanced algorithms on retrieval, classification and TDT (abbreviation of Topic Detection and Tracking) can bring lots of convenience to Web users as well as release tedious work from the administrators. Nevertheless, due to the the insufficiency of annotation keywords and the gap between video features and semantic concepts, it is still far away from satisfactory to implement them based on initial keywords and visual features. In this paper we utilize a keyword propagation algorithm based on manifold structure to enrich the keyword information and remove the noise for videos. Both text similarity and temporal similarity are employed to explore the relationship between any pair of videos and to construct the propagation model. We explore three applications, i.e., TDT, Retrieval and Classification based on a Web news video dataset obtained from a famous online video-distributing website, YouKu, and evaluate our approach. Experimental results demonstrate that they achieve satisfactory performance and always outperform the baseline methods.
Mining discriminative components with low-rank and sparsity constraints for face recognition
Authors: Qiang Zhang, Baoxin Li
Venue: KDD
Year: 2012

This paper introduces a novel image decomposition approach for an ensemble of correlated images, using low-rank and sparsity constraints. Each image is decomposed as a combination of three components: one common component, one condition component, which is assumed to be a low-rank matrix, and a sparse residual. For a set of face images of Nsubjects, the decomposition finds N common components, one for each subject, K low-rank components, each capturing a different global condition of the set (e.g., different illumination conditions), and a sparse residual for each input image. Through this decomposition, the proposed approach recovers a clean face image (the common component) for each subject and discovers the conditions (the condition components and the sparse residuals) of the images in the set. The set of N+K images containing only the common and the low-rank components form a compact and discriminative representation for the original images. We design a classifier using only these N+K images. Experiments on commonly-used face data sets demonstrate the effectiveness of the approach for face recognition through comparing with the leading state-of-the-art in the literature. The experiments further show good accuracy in classifying the condition of an input image, suggesting that the components from the proposed decomposition indeed capture physically meaningful features of the input.
Parallel rough set based knowledge acquisition using MapReduce from big data
Authors: Junbo Zhang, Tianrui Li, Yi Pan
Venue: KDD
Year: 2012

Nowadays, with the volume of data growing at an unprecedented rate, big data mining and knowledge discovery have become a new challenge. Rough set theory for knowledge acquisition has been successfully applied in data mining. The recently introduced MapReduce technique has received much attention from both scientific community and industry for its applicability in big data analysis. To mine knowledge from big data, we present parallel rough set based methods for knowledge acquisition using MapReduce in this paper. Comprehensive experimental evaluation on large data sets shows that the proposed parallel methods can effectively process big data.
Harnessing the wisdom of the crowds for accurate web page clipping
Authors: Lei Zhang, Linpeng Tang, Ping Luo, Enhong Chen, Limei Jiao, Min Wang, Guiquan Liu
Venue: KDD
Year: 2012

Clipping Web pages, namely extracting the informative clips (areas) from Web pages, has many applications, such as Web printing and e-reading on small handheld devices. Although many existing methods attempt to address this task, most of them can either work only on certain types of Web pages (e.g., news- and blog-like web pages), or perform semi-automatically where extra user efforts are required in adjusting the outputs. The problem of clipping any types of Web pages accurately in a totally automatic way remains pretty much open. To this end in this study we harness the wisdom of the crowds to provide accurate recommendation of informative clips on any given Web pages. Specifically, we leverage the knowledge on how previous users clip similar Web pages, and this knowledge repository can be represented as a transaction database where each transaction contains the clips selected by a user on a certain Web page. Then, we formulate a new pattern mining problem, mining top-1 qualified pattern, on transaction database for this recommendation. Here, the recommendation considers not only the pattern support but also the pattern occupancy (proposed in this work). High support requires that patterns appear frequently in the database, while high occupancy requires that patterns occupy a large portion of the transactions they appear in. Thus, it leads to both precise and complete recommendation. Additionally, we explore the properties on occupancy to further prune the search space for high-efficient pattern mining. Finally, we show the effectiveness of the proposed algorithm on a human-labeled ground truth dataset consisting of 2000 web pages from 100 major Web sites, and demonstrate its efficiency on large synthetic datasets.
A system for extracting top-K lists from the web
Authors: Zhixian Zhang, Kenny Qili Zhu, Haixun Wang
Venue: KDD
Year: 2012

List data is an important source of structured data on the web. This paper is concerned with "top-k" pages, which are web pages that describe a list of k instances of a particular topic or concept. Examples include "the 10 tallest persons in the world" and "the 50 hits of 2010 you don't want to miss". Compared to normal web list data, "top-k" lists contain richer information and are easier to understand. Therefore the extraction of such lists can help enrich existing knowledge bases about general concepts, or act as a preprocessing step to produce facts for a fact answering engine. We present an efficient system that extracts the target lists from web pages with high accuracy. We have used the system to process up to 160 million, or 1/10 of a high-frequency web snapshot from Bing, and obtained over 140,000 lists with 90.4% precision.
ComSoc: adaptive transfer of user behaviors over composite social network
Authors: Erheng Zhong, Wei Fan, Junwei Wang, Lei Xiao, Yong Li
Venue: KDD
Year: 2012

Accurate prediction of user behaviors is important for many social media applications, including social marketing, personalization and recommendation, etc. A major challenge lies in that, the available behavior data or interactions between users and items in a given social network are usually very limited and sparse (e.g., >= 99.9% empty). Many previous works model user behavior from only historical user logs. We observe that many people are members of several social networks in the same time, such as Facebook, Twitter and Tencent's QQ. Importantly, their behaviors and interests in different networks influence one another. This gives us an opportunity to leverage the knowledge of user behaviors in different networks, in order to alleviate the data sparsity problem, and enhance the predictive performance of user modeling. Combining different networks "simply and naively" does not work well. Instead, we formulate the problem to model multiple networks as "composite network knowledge transfer". We first select the most suitable networks inside a composite social network via a hierarchical Bayesian model, parameterized for individual users, and then build topic models for user behavior prediction using both the relationships in the selected networks and related behavior data. To handle big data, we have implemented the algorithm using Map/Reduce. We demonstrate that the proposed composite network-based user behavior model significantly improve the predictive accuracy over a number of existing approaches on several real world applications, such as a very large social-networking dataset from Tencent Inc.
Community discovery and profiling with social messages
Authors: Wenjun Zhou, Hongxia Jin, Yan Liu
Venue: KDD
Year: 2012

Discovering communities from social media and collaboration systems has been of great interest in recent years. Existing work show prospects of modeling contents and social links, aiming at discovering social communities, whose definition varies by application. We believe that a community depends not only on the group of people who actively participate, but also the topics they communicate about or collaborate on. This is especially true for workplace email communications. Within an organization, it is not uncommon that employees multifunction, and groups of employees collaborate on multiple projects at the same time. In this paper, we aim to automatically discovering and profiling users' communities by taking into account both the contacts and the topics. More specifically, we propose a community profiling model called COCOMP, where the communities labels are latent, and each social document corresponds to an information sharing activity among the most probable community members regarding the most relevant community issues. Experiment results on several social communication datasets, including emails and Twitter messages, demonstrate that the model can discover users' communities effectively, and provide concrete semantics.
Adversarial support vector machine learning
Authors: Yan Zhou, Murat Kantarcioglu, Bhavani Thuraisingham, Bowei Xi
Venue: KDD
Year: 2012

Many learning tasks such as spam filtering and credit card fraud detection face an active adversary that tries to avoid detection. For learning problems that deal with an active adversary, it is important to model the adversary's attack strategy and develop robust learning models to mitigate the attack. These are the two objectives of this paper. We consider two attack models: a free-range attack model that permits arbitrary data corruption and a restrained attack model that anticipates more realistic attacks that a reasonable adversary would devise under penalties. We then develop optimal SVM learning strategies against the two attack models. The learning algorithms minimize the hinge loss while assuming the adversary is modifying data to maximize the loss. Experiments are performed on both artificial and real data sets. We demonstrate that optimal solutions may be overly pessimistic when the actual attacks are much weaker than expected. More important, we demonstrate that it is possible to develop a much more resilient SVM learning model while making loose assumptions on the data corruption models. When derived under the restrained attack model, our optimal SVM learning strategy provides more robust overall performance under a wide range of attack parameters.
Social media data analysis for revealing collective behaviors
Authors: Aoying Zhou, Weining Qian, Haixin Ma
Venue: KDD
Year: 2012

Along with the development of Web 2.0 applications, social media services has attracted many users and become their hands-on toolkits for recording life, sharing ideas, and social networking. Though social media services are essentially web or mobile applications and services, they combine user-generated content and social networks together, so that information can be created, transmitted, transformed, and consumed in the cyberspace. Thus, social media somehow could be regarded as a kind of sensor to the real life of its users. In general, the data from social media is of low quality. Pieces of information in social media are usually short, with informal presentation, and in some specific context that is highly related to the physical world. Therefore, it is challenging to extract semantics from social media data. However, we argue that given sufficient social media data, users' collective behaviors could be sensed, studied, and even predicted in a certain circumstance. Our study is conducted on data from two services, i.e. Twitter, and Sina Weibo, the most popular microblogging services all over the world and in China, respectively. Collective behaviors are actions of a large amount of various people, which are neither conforming nor deviant. Various collective behaviors are studied in the context of social media. Our studies show that there are various information flow patterns in social media, some of which are similar to traditional media such as newspapers, while others are embedded deep in the social network structure. The evolution of hotspots is highly affected by external stimulation, the social network structure, and individual user's activities. Furthermore, social media tends to be immune to some repeated similar external stimulations. Last but not the least, there is considerable difference in users' behavior between Twitter and Sina Weibo.