OpenRaiser/Intern-Atlas huggingface dataset:
Information processing in social networks
Authors: Ming-Syan Chen
Venue: KDD
Year: 2012

In the current social network, a user may have hundreds of friends and find it very time consuming to categorize and tag every friend manually. When a user is going to initiate an activity by issuing a corresponding query, he/she needs to consider the relationship among candidate attendees to find a group of mutually close friends. Meanwhile, he/she also needs to consider the schedule of candidate attendees to find an activity period available for all attendees. It would certainly be desirable if the efficiency of such process is improved. In this talk, information processing in social networks will first be reviewed in three phrases, namely (i) from content to social relationship, (ii) mining on social relationship, and (iii) from social relationship to content organization. In addition, we shall present an effective procedure which helps a user to organize an event with proper attendees with minimum total social distance and commonly available time. Moreover, it is noted that the information retrieved from the social networks is also able to facilitate those user-dependent and human-centric services. In light of this, we shall explore the quality of recommendation through incorporating the notion of social filtering and collaborative filtering. Finally, it is recognized that the cloud computing has offered many new capabilities of storing and processing huge amounts of heterogeneous data in social networks. In view of this, we shall also examine how this paradigm shift will affect the information processing in social networks.
Information propagation game: a tool to acquire humanplaying data for multiplayer influence maximization on social networks
Authors: Hung-Hsuan Chen, Yan-Bin Ciou, Shou-De Lin
Venue: KDD
Year: 2012

With the popularity of online social network services, influence maximization on social networks has drawn much attention in recent years. Most of these studies approximate a greedy based sub-optimal solution by proving the submodular nature of the utility function. Instead of using the analytical techniques, we are interested in solving the diffusion competition and influence maximization problem by a data-driven approach. We propose Information Propagation Game (IPG), a framework that can collect a large number of seed picking strategies for analysis. Through the IPG framework, human players are not only having fun but also helping contributing the seed picking strategies. Preliminary experiment suggests that centrality based heuristics are too simple for seed selection in a multiple player environment.
The contextual focused topic model
Authors: Xu Chen, Mingyuan Zhou, Lawrence Carin
Venue: KDD
Year: 2012

A nonparametric Bayesian contextual focused topic model (cFTM) is proposed. The cFTM infers a sparse ("focused") set of topics for each document, while also leveraging contextual information about the author(s) and document venue. The hierarchical beta process, coupled with a Bernoulli process, is employed to infer the focused set of topics associated with each author and venue; the same construction is also employed to infer those topics associated with a given document that are unusual (termed "random effects"), relative to topics that are inferred as probable for the associated author(s) and venue. To leverage statistical strength and infer latent interrelationships between authors and venues, the Dirichlet process is utilized to cluster authors and venues. The cFTM automatically infers the number of topics needed to represent the corpus, the number of author and venue clusters, and the probabilistic importance of the author, venue and random-effect information on word assignment for a given document. Efficient MCMC inference is presented. Example results and interpretations are presented for two real datasets, demonstrating promising performance, with comparison to other state-of-the-art methods.
CluChunk: clustering large scale user-generated content incorporating chunklet information
Authors: Yu Cheng, Yusheng Xie, Kunpeng Zhang, Ankit Agrawal, Alok N. Choudhary
Venue: KDD
Year: 2012

The exponential rise of online content in the form of blogs, microblogs, forums, and multimedia sharing sites has raised an urgent demand for efficient and high-quality text clustering algorithms for fast navigation and browsing of users based on better document organization. For several kinds of these user-generated content, it is much easier to obtain the input in small sets, where the data in each set belongs to the same class but with unknown class labels. Such data is viewed as weakly-labeled data and the inherent chunklet information is very useful for improving clustering performance. In this paper, we propose a system - CluChunk (clustering chunklet data) to cluster unlabeled web data which incorporates chunklet information. We try to transfer the original feature space by a discriminatively learning linear transformation such that simple unsupervised learning techniques (such as K-Means) in the transformed space can achieve good clustering accuracy. Using larger scale data from some web applications (social media and online forums), we demonstrate that the clustering performance can get significantly improved by: 1)incorporating the inherent weakly-labeled information into the clustering framework; 2)enriching the representation of short text with additional features extracted from the chunklet subset. The proposed approach can be applied to other mining tasks with large scale user-generated content, like product review summarizing and blog content clustering/classification task.
Experience with discovering knowledge by acquiring it
Authors: Paul Compton
Venue: KDD
Year: 2012

Machines and people have complementary skills in Knowledge Discovery. Automated techniques can process enormous amounts of data to find new relationships, but generally these are represented by fairly simple models. On the other hand people are endlessly inventive in creating models to explain data at hand, but have problems developing consistent overall models to explain all the data that might occur in a domain; and the larger the model, the more difficult it becomes to maintain consistency. Ripple-Down Rules is a technique that has been developed to allow people to make real-time updates to a model whenever they notice some data that the model does not yet explain, while at the same time maintaining consistency. This allows an entire knowledge base to be built while it is already in use by making updates. There are now 100s of Ripple-Down-Rule knowledge bases in use and this paper presents some observations from log files tracking how people build these systems, and also outlines some recent research on how such techniques can be used to add greater specificity to the simpler models developed by automated techniques.
Social sampling
Authors: Anirban Dasgupta, Ravi Kumar, D. Sivakumar
Venue: KDD
Year: 2012

We investigate a class of methods that we call "social sampling," where participants in a poll respond with a summary of their friends' putative responses to the poll. Social sampling leads to a novel trade-off question: the savings in the number of samples(roughly the average degree of the network of participants) vs. the systematic bias in the poll due to the network structure.
Two approaches to understanding when constraints help clustering
Authors: Ian Davidson
Venue: KDD
Year: 2012

Most algorithm work in data mining focuses on designing algorithms to address a learning problem. Here we focus our attention on designing algorithms to determine the ease or difficulty of a problem instance. The area of clustering under constraints has recently received much attention in the data mining community. We can view the constraints as restricting (either directly or indirectly) the search space of a clustering algorithm to just feasible clusterings. However, to our knowledge no work explores methods to count the feasible clusterings or other measures of difficulty nor the importance of these measures. We present two approaches to efficiently characterize the difficulty of satisfying must-link (ML) and cannot-link (CL) constraints: calculating the fractional chromatic polynomial of the constraint graph using LP and approximately counting the number of feasible clusterings using MCMC samplers. We show that these measures are correlated to the classical performance measures of constrained clustering algorithms. From these insights and our algorithms we construct new methods of generating and pruning constraints and empirically demonstrate their usefulness.
Leveraging predictive modeling to reduce signal theft in a multi-service organization environment
Authors: Seymour Douglas
Venue: KDD
Year: 2012

Signal theft can be defined as the interdiction, consumption or usage of carrier signal from a provider's network without payment or payment of an amount less than the level of service consumed. High levels of signal theft can potentially reflect open technical network issues, failure of electronic countermeasures or operational gaps that are estimated to cost the cable industry providers more than $5 billion annually. This session will discuss the business challenges associated with the quantification of signal theft-related losses, outline some of the countermeasures taken by MSOs, and then provide views on the development of predictive models to help identify the potential likelihood of signal theft in a given environment. We will examine the performance of certain machine learning algorithms as well as data challenges associated with both the architecture construction and analytical efforts, and conclude with a lessons-learned discussion and views on future approaches.
Different slopes for different folks: mining for exceptional regression models with cook's distance
Authors: Wouter Duivesteijn, Ad Feelders, Arno J. Knobbe
Venue: KDD
Year: 2012

Exceptional Model Mining (EMM) is an exploratory data analysis technique that can be regarded as a generalization of subgroup discovery. In EMM we look for subgroups of the data for which a model fitted to the subgroup differs substantially from the same model fitted to the entire dataset. In this paper we develop methods to mine for exceptional regression models. We propose a measure for the exceptionality of regression models (Cook's distance), and explore the possibilities to avoid having to fit the regression model to each candidate subgroup. The algorithm is evaluated on a number of real life datasets. These datasets are also used to illustrate the results of the algorithm. We find interesting subgroups with deviating models on datasets from several different domains. We also show that under certain circumstances one can forego fitting regression models on up to 40% of the subgroups, and these 40% are the relatively expensive regression models to compute.
Summarization-based mining bipartite graphs
Authors: Jing Feng, Xiao He, Bettina Konte, Christian Böhm, Claudia Plant
Venue: KDD
Year: 2012

How to extract the truly relevant information from a large relational data set? The answer of this paper is a technique integrating graph summarization, graph clustering, link prediction and the discovery of the hidden structure on the basis of data compression. Our novel algorithm SCMiner (for Summarization-Compression Miner) reduces a large bipartite input graph to a highly compact representation which is very useful for different data mining tasks: 1) Clustering: The compact summary graph contains the truly relevant clusters of both types of nodes of a bipartite graph. 2) Link prediction: The compression scheme of SCMiner reveals suspicious edges which are probably erroneous as well as missing edges, i.e. pairs of nodes which should be connected by an edge. 3) Discovery of the hidden structure: Unlike traditional co-clustering methods, the result of SCMiner is not limited to row- and column-clusters. Besides the clusters, the summary graph also contains the essential relationships between both types of clusters and thus reveals the hidden structure of the data. Extensive experiments on synthetic and real data demonstrate that SCMiner outperforms state-of-the-art techniques for clustering and link prediction. Moreover, SCMiner discovers the hidden structure and reports it in an interpretable way to the user. Based on data compression, our technique does not rely on any input parameters which are difficult to estimate.
Siren: an interactive tool for mining and visualizing geospatial redescriptions
Authors: Esther Galbrun, Pauli Miettinen
Venue: KDD
Year: 2012

We present SIREN, an interactive tool for mining and visualizing geospatial redescriptions. Redescription mining is a powerful data analysis tool that aims at finding alternative descriptions of the same entities. For example, in biology, an important task is to identify the bioclimatic constraints that allow some species to survive, that is, to describe geographical regions in terms of both the fauna that inhabits them and their bioclimatic conditions.
Visual exploration of collaboration networks based on graph degeneracy
Authors: Christos Giatsidis, Klaus Berberich, Dimitrios M. Thilikos, Michalis Vazirgiannis
Venue: KDD
Year: 2012

We demonstrate a system that supports the visual exploration of collaboration networks. The system leverages the notion of fractional cores introduced in earlier work to rank vertices in a collaboration network and filter vertices' neighborhoods. Fractional cores build on the idea of graph degeneracy as captured by the notion of k-cores in graph theory and extend it to undirected edge-weighted graphs. In a co-authorship network, for instance, the fractional core index of an author intuitively reflects the degree of collaboration with equally or higher-ranked authors. Our system has been deployed on a real-world co-authorship network derived from DBLP, demonstrating that the idea of fractional cores can be applied even to large-scale networks. The system provides an easy-to-use interface to query for the fractional core index of an author, to see who the closest equally or higher-ranked co-authors are, and explore the entire co-authorship network in an incremental manner.
Estimating entity importance via counting set covers
Authors: Aristides Gionis, Theodoros Lappas, Evimaria Terzi
Venue: KDD
Year: 2012

The data-mining literature is rich in problems asking to assess the importance of entities in a given dataset. At a high level, existing work identifies important entities either by ranking or by selection. Ranking methods assign a score to every entity in the population, and then use the assigned scores to create a ranked list. The major shortcoming of such approaches is that they ignore the redundancy between high-ranked entities, which may in fact be very similar or even identical. Therefore, in scenarios where diversity is desirable, such methods perform poorly. Selection methods overcome this drawback by evaluating the importance of a group of entities collectively. To achieve this, they typically adopt a set-cover formulation, which identifies the entities in the minimum set cover as the important ones. However, this dichotomy of entities conceals the fact that, even though an entity may not be in the reported cover, it may still participate in many other optimal or near-optimal solutions. In this paper, we propose a framework that overcomes the above drawbacks by integrating the ranking and selection paradigms. Our approach assigns importance scores to entities based on both the number and the quality of set-cover solutions that they participate. Our algorithmic contribution lies with the design of an efficient algorithm for approximating the number of high-quality set covers that each entity participates. Our methodology applies to a wide range of applications. In a user study and an experimental evaluation on real data, we demonstrate that our framework is efficient and provides useful and intuitive results.
Robust multi-task feature learning
Authors: Pinghua Gong, Jieping Ye, Changshui Zhang
Venue: KDD
Year: 2012

Multi-task learning (MTL) aims to improve the performance of multiple related tasks by exploiting the intrinsic relationships among them. Recently, multi-task feature learning algorithms have received increasing attention and they have been successfully applied to many applications involving high dimensional data. However, they assume that all tasks share a common set of features, which is too restrictive and may not hold in real-world applications, since outlier tasks often exist. In this paper, we propose a Robust Multi-Task Feature Learning algorithm (rMTFL) which simultaneously captures a common set of features among relevant tasks and identifies outlier tasks. Specifically, we decompose the weight (model) matrix for all tasks into two components. We impose the well-known group Lasso penalty on row groups of the first component for capturing the shared features among relevant tasks. To simultaneously identify the outlier tasks, we impose the same group Lasso penalty but on column groups of the second component. We propose to employ the accelerated gradient descent to efficiently solve the optimization problem in rMTFL, and show that the proposed algorithm is scalable to large-size problems. In addition, we provide a detailed theoretical analysis on the proposed rMTFL formulation. Specifically, we present a theoretical bound to measure how well our proposed rMTFL approximates the true evaluation, and provide bounds to measure the error between the estimated weights of rMTFL and the underlying true weights. Moreover, by assuming that the underlying true weights are above the noise level, we present a sound theoretical result to show how to obtain the underlying true shared features and outlier tasks (sparsity patterns). Empirical studies on both synthetic and real-world data demonstrate that our proposed rMTFL is capable of simultaneously capturing shared features among tasks and identifying outlier tasks.
Big data, big business: bridging the gap
Authors: Vivekanand Gopalkrishnan, David M. Steier, Harvey Lewis, James Guszcza
Venue: KDD
Year: 2012

Business analytics, occupying the intersection of the worlds of management science, computer science and statistical science, is a potent force for innovation in both the private and public sectors. The successes of business analytics in strategy, process optimization and competitive advantage has led to data being increasingly recognized as a valuable asset in many organizations. In recent years, thanks to a dramatic increase in the volume, variety and velocity of data, the loosely defined concept of "Big Data" has emerged as a topic of discussion in its own right -- with different viewpoints in both the business and technical worlds. From our perspective, it is important for discussions of "Big Data" to start from a well-defined business goal, and remain moored to fundamental principles of both cost/benefit analysis as well as core statistical science. This note discusses some business case considerations for analytics projects involving "Big Data", and proposes key questions that businesses should ask. With practical lessons from Big Data deployments in business, we also pose a number of research challenges that may be addressed to enable the business analytics community bring best data analytic practices when confronted with massive data sets.
Multi-view clustering using mixture models in subspace projections
Authors: Stephan Günnemann, Ines Färber, Thomas Seidl
Venue: KDD
Year: 2012

Detecting multiple clustering solutions is an emerging research field. While data is often multi-faceted in its very nature, traditional clustering methods are restricted to find just a single grouping. To overcome this limitation, methods aiming at the detection of alternative and multiple clustering solutions have been proposed. In this work, we present a Bayesian framework to tackle the problem of multi-view clustering. We provide multiple generalizations of the data by using multiple mixture models. Each mixture describes a specific view on the data by using a mixture of Beta distributions in subspace projections. Since a mixture summarizes the clusters located in similar subspace projections, each view highlights specific aspects of the data. In addition, our model handles overlapping views, where the mixture components compete against each other in the data generation process. For efficiently learning the distributions, we propose the algorithm MVGen that exploits the ICM principle and uses Bayesian model selection to trade-off the cluster model's complexity against its goodness of fit. With experiments on various real-world data sets, we demonstrate the high potential of MVGen to detect multiple, overlapping clustering views in subspace projections of the data.
Subspace correlation clustering: finding locally correlated dimensions in subspace projections of the data
Authors: Stephan Günnemann, Ines Färber, Kittipat Virochsiri, Thomas Seidl
Venue: KDD
Year: 2012

The necessity to analyze subspace projections of complex data is a well-known fact in the clustering community. While the full space may be obfuscated by overlapping patterns and irrelevant dimensions, only certain subspaces are able to reveal the clustering structure. Subspace clustering discards irrelevant dimensions and allows objects to belong to multiple, overlapping clusters due to individual subspace projections for each set of objects. As we will demonstrate, the observations, which originate the need to consider subspace projections for traditional clustering, also apply for the task of correlation analysis.
Factoring past exposure in display advertising targeting
Authors: Neha Gupta, Abhimanyu Das, Sandeep Pandey, Vijay K. Narayanan
Venue: KDD
Year: 2012

Online advertising is becoming more and more performance oriented where the decision to show an advertisement to a user is made based on the user's propensity to respond to the ad in a positive manner, (e.g., purchasing a product, subscribing to an email list). The user response depends on how well the ad campaign matches to the user's interest, as well as the amount of user's past exposure to the campaign - a factor shown to be impactful in controlled experimental studies. Past exposure builds brand-awareness and familiarity with the user, which in turn leads to a higher propensity of the user to buy/convert on the ad impression. In this paper we propose a model of the user response to an ad campaign as a function of both the interest match and the past exposure, where the interest match is estimated using historical search/browse activities of the user.
Discriminative clustering for market segmentation
Authors: Peter Haider, Luca Chiarandini, Ulf Brefeld
Venue: KDD
Year: 2012

We study discriminative clustering for market segmentation tasks. The underlying problem setting resembles discriminative clustering, however, existing approaches focus on the prediction of univariate cluster labels. By contrast, market segments encode complex (future) behavior of the individuals which cannot be represented by a single variable. In this paper, we generalize discriminative clustering to structured and complex output variables that can be represented as graphical models. We devise two novel methods to jointly learn the classifier and the clustering using alternating optimization and collapsed inference, respectively. The two approaches jointly learn a discriminative segmentation of the input space and a generative output prediction model for each segment. We evaluate our methods on segmenting user navigation sequences from Yahoo! News. The proposed collapsed algorithm is observed to outperform baseline approaches such as mixture of experts. We showcase exemplary projections of the resulting segments to display the interpretability of the solutions.