OpenRaiser/Intern-Atlas huggingface dataset:
Overlapping decomposition for causal graphical modeling
Authors: Lei Han, Guojie Song, Gao Cong, Kunqing Xie
Venue: KDD
Year: 2012

Causal graphical models are developed to detect the dependence relationships between random variables and provide intuitive explanations for the relationships in complex systems. Most of existing work focuses on learning a single graphical model for all the variables. However, a single graphical model cannot accurately characterize the complicated causal relationships for a relatively large graph. In this paper, we propose the problem of estimating an overlapping decomposition for Gaussian graphical models of a large scale to generate overlapping sub-graphical models. Specifically, we formulate an objective function for the overlapping decomposition problem and propose an approximate algorithm for it. A key theory of the algorithm is that the problem of solving a κ+1 node graphical model can be reduced to the problem of solving a one-step regularization based on a solved κ node graphical model. Based on this theory, a greedy expansion algorithm is proposed to generate the overlapping subgraphs. We evaluate the effectiveness of our model on both synthetic datasets and real traffic dataset, and the experimental results show the superiority of our method.
Stream-dashboard: a framework for mining, tracking and validating clusters in a data stream
Authors: Basheer Hawwash, Olfa Nasraoui
Venue: KDD
Year: 2012

Clustering data streams is a challenging problem that has received significant attention in the recent decade. In this paper, we address the hitherto inadequately addressed challenge of managing the output of stream clustering. This task comprises the continuous cluster model validation, monitoring, trend and change detection, and summarization of the cluster mining output. For this purpose, we propose a complete framework to mine, track and validate the clusters in a data stream. The proposed framework keeps track of each discovered cluster model of the stream through time, while quantifying, modeling and summarizing the cluster evolution trends, and storing a summary of the cluster models and the evolution trends only at milestones corresponding to the occurrence of significant changes. Our experiments demonstrate the accuracy of the proposed framework in tracking cluster evolution over time, while generating a concise summary of the evolution trends over the lifetime of the stream.
A kernel fused perceptron for the online classification of large-scale data
Authors: Huijun He, Mingmin Chi, Wenqiang Zhang
Venue: KDD
Year: 2012

To solve online nonlinear problems, usually, a set of misclassified observed examples (defined as support set) should be stored in the internal memory for computing kernel values. With the increase of a large scale of training data, computing all the kernel values is expensive and also can lead to an out-of-memory problem. In the paper, a fusion strategy is proposed to compress the size of support set for online learning and the fused kernel can best represent the current instance and its nearest one in the support set in the previous time. The proposed algorithm is based on Perceptron-like method, and thus it is called as Fuseptron. Different from the most recently proposed nonlinear online algorithms, the internal memory can be bounded in Fuseptron and the mistake bound is also derived. Experiments carried out on one synthetic and four real large-scale datasets validate the effectiveness and efficiency of Fuseptron compared to the state-of-the-art algorithms.
RolX: structural role extraction & mining in large graphs
Authors: Keith Henderson, Brian Gallagher, Tina Eliassi-Rad, Hanghang Tong, Sugato Basu, Leman Akoglu, Danai Koutra, Christos Faloutsos, Lei Li
Venue: KDD
Year: 2012

Given a network, intuitively two nodes belong to the same role if they have similar structural behavior. Roles should be automatically determined from the data, and could be, for example, "clique-members," "periphery-nodes," etc. Roles enable numerous novel and useful network-mining tasks, such as sense-making, searching for similar nodes, and node classification. This paper addresses the question: Given a graph, how can we automatically discover roles for nodes? We propose RolX (Role eXtraction), a scalable (linear in the number of edges), unsupervised learning approach for automatically extracting structural roles from general network data. We demonstrate the effectiveness of RolX on several network-mining tasks: from exploratory data analysis to network transfer learning. Moreover, we compare network role discovery with network community discovery. We highlight fundamental differences between the two (e.g., roles generalize across disconnected networks, communities do not); and show that the two approaches are complimentary in nature.
Detecting changes of clustering structures using normalized maximum likelihood coding
Authors: So Hirai, Kenji Yamanishi
Venue: KDD
Year: 2012

We are concerned with the issue of detecting changes of clustering structures from multivariate time series. From the viewpoint of the minimum description length(MDL) principle, we propose an algorithm that tracks changes of clustering structures so that the sum of the code-length for data and that for clustering changes is minimum. Here we employ a Gaussian mixture model(GMM) as representation of clustering, and compute the code-length for data sequences using the normalized maximum likelihood (NML) coding. The proposed algorithm enables us to deal with clustering dynamics including merging, splitting, emergence, disappearance of clusters from a unifying view of the MDL principle. We empirically demonstrate using artificial data sets that our proposed method is able to detect cluster changes significantly more accurately than an existing statistical-test based method and AIC/BIC-based methods. We further use real customers' transaction data sets to demonstrate the validity of our algorithm in market analysis. We show that it is able to detect changes of customer groups, which correspond to changes of real market environments.
Online feature selection for mining big data
Authors: Steven C. H. Hoi, Jialei Wang, Peilin Zhao, Rong Jin
Venue: KDD
Year: 2012

Most studies of online learning require accessing all the attributes/features of training instances. Such a classical setting is not always appropriate for real-world applications when data instances are of high dimensionality or the access to it is expensive to acquire the full set of attributes/features. To address this limitation, we investigate the problem of Online Feature Selection (OFS) in which the online learner is only allowed to maintain a classifier involved a small and fixed number of features. The key challenge of Online Feature Selection is how to make accurate prediction using a small and fixed number of active features. This is in contrast to the classical setup of online learning where all the features are active and can be used for prediction. We address this challenge by studying sparsity regularization and truncation techniques. Specifically, we present an effective algorithm to solve the problem, give the theoretical analysis, and evaluate the empirical performance of the proposed algorithms for online feature selection on several public datasets. We also demonstrate the application of our online feature selection technique to tackle real-world problems of big data mining, which is significantly more scalable than some well-known batch feature selection algorithms. The encouraging results of our experiments validate the efficacy and efficiency of the proposed techniques for large-scale applications.
Maximizing return and minimizing cost with the right decision management systems
Authors: Rich Holada
Venue: KDD
Year: 2012

The ability to achieve operational efficiency, product leadership, and customer intimacy still eludes many organizations due, in large part, to the chaos of business. Inconsistent prioritization and decision making; poor visibility between systems; processes that are not well controlled; and individual front-line decisions that seem small but, in totality, have a huge impact make it difficult for organizations to link strategy to execution and back. During this presentation, we will demonstrate how automating and optimizing decisions (operational efficiency) with business rules and predictive models enables better data driven results across the enterprise, and how this is implemented at the point of impact (customer intimacy) to transform an organization and support market leadership.
Developing data mining applications
Authors: Geoff Holmes
Venue: KDD
Year: 2012

In this talk I will review several real-world applications developed at the University of Waikato over the past 15 years. These include the use of near infrared spectroscopy coupled with data mining as an alternate laboratory technique for predicting compound concentrations in soil and plant samples, and the analysis of gas chromatography mass spectrometry (GCMS) data, a technique used to determine in environmental applications, for example, the petroleum content in soil and water samples. I will then briefly discuss how experience with these applications has led to the development of an open-source framework for application development.
Accelerated singular value thresholding for matrix completion
Authors: Yao Hu, Debing Zhang, Jun Liu, Jieping Ye, Xiaofei He
Venue: KDD
Year: 2012

Recovering a large matrix from a small subset of its entries is a challenging problem arising in many real world applications, such as recommender system and image in-painting. These problems can be formulated as a general matrix completion problem. The Singular Value Thresholding (SVT) algorithm is a simple and efficient first-order matrix completion method to recover the missing values when the original data matrix is of low rank. SVT has been applied successfully in many applications. However, SVT is computationally expensive when the size of the data matrix is large, which significantly limits its applicability. In this paper, we propose an Accelerated Singular Value Thresholding (ASVT) algorithm which improves the convergence rate from O(1/N) for SVT to O(1/N2), where N is the number of iterations during optimization. Specifically, the dual problem of the nuclear norm minimization problem is derived and an adaptive line search scheme is introduced to solve this dual problem. Consequently, the optimal solution of the primary problem can be readily obtained from that of the dual problem. We have conducted a series of experiments on a synthetic dataset, a distance matrix dataset and a large movie rating dataset. The experimental results have demonstrated the efficiency and effectiveness of the proposed algorithm.
SPF-GMKL: generalized multiple kernel learning with a million kernels
Authors: Ashesh Jain, S. V. N. Vishwanathan, Manik Varma
Venue: KDD
Year: 2012

Multiple Kernel Learning (MKL) aims to learn the kernel in an SVM from training data. Many MKL formulations have been proposed and some have proved effective in certain applications. Nevertheless, as MKL is a nascent field, many more formulations need to be developed to generalize across domains and meet the challenges of real world applications. However, each MKL formulation typically necessitates the development of a specialized optimization algorithm. The lack of an efficient, general purpose optimizer capable of handling a wide range of formulations presents a significant challenge to those looking to take MKL out of the lab and into the real world.
A simple methodology for soft cost-sensitive classification
Authors: Te-Kang Jan, Da-Wei Wang, Chi-Hung Lin, Hsuan-Tien Lin
Venue: KDD
Year: 2012

Many real-world data mining applications need varying cost for different types of classification errors and thus call for cost-sensitive classification algorithms. Existing algorithms for cost-sensitive classification are successful in terms of minimizing the cost, but can result in a high error rate as the trade-off. The high error rate holds back the practical use of those algorithms. In this paper, we propose a novel cost-sensitive classification methodology that takes both the cost and the error rate into account. The methodology, called soft cost-sensitive classification, is established from a multicriteria optimization problem of the cost and the error rate, and can be viewed as regularizing cost-sensitive classification with the error rate. The simple methodology allows immediate improvements of existing cost-sensitive classification algorithms. Experiments on the benchmark and the real-world data sets show that our proposed methodology indeed achieves lower test error rates and similar (sometimes lower) test costs than existing cost-sensitive classification algorithms.
Parallel field ranking
Authors: Ming Ji, Binbin Lin, Xiaofei He, Deng Cai, Jiawei Han
Venue: KDD
Year: 2012

Recently, ranking data with respect to the intrinsic geometric structure (manifold ranking) has received considerable attentions, with encouraging performance in many applications in pattern recognition, information retrieval and recommendation systems. Most of the existing manifold ranking methods focus on learning a ranking function that varies smoothly along the data manifold. However, beyond smoothness, a desirable ranking function should vary monotonically along the geodesics of the data manifold, such that the ranking order along the geodesics is preserved. In this paper, we aim to learn a ranking function that varies linearly and therefore monotonically along the geodesics of the data manifold. Recent theoretical work shows that the gradient field of a linear function on the manifold has to be a parallel vector field. Therefore, we propose a novel ranking algorithm on the data manifolds, called Parallel Field Ranking. Specifically, we try to learn a ranking function and a vector field simultaneously. We require the vector field to be close to the gradient field of the ranking function, and the vector field to be as parallel as possible. Moreover, we require the value of the ranking function at the query point to be the highest, and then decrease linearly along the manifold. Experimental results on both synthetic data and real data demonstrate the effectiveness of our proposed algorithm.
A sparsity-inducing formulation for evolutionary co-clustering
Authors: Shuiwang Ji, Wenlu Zhang, Jun Liu
Venue: KDD
Year: 2012

Traditional co-clustering methods identify block structures from static data matrices. However, the data matrices in many applications are dynamic; that is, they evolve smoothly over time. Consequently, the hidden block structures embedded into the matrices are also expected to vary smoothly along the temporal dimension. It is therefore desirable to encourage smoothness between the block structures identified from temporally adjacent data matrices. In this paper, we propose an evolutionary co-clustering formulation for identifying co-cluster structures from time-varying data. The proposed formulation encourages smoothness between temporally adjacent blocks by employing the fused Lasso type of regularization. Our formulation is very flexible and allows for imposing smoothness constraints over only one dimension of the data matrices, thereby enabling its applicability to a large variety of settings. The optimization problem for the proposed formulation is non-convex, non-smooth, and non-separable. We develop an iterative procedure to compute the solution. Each step of the iterative procedure involves a convex, but non-smooth and non-separable problem. We propose to solve this problem in its dual form, which is convex and smooth. This leads to a simple gradient descent algorithm for computing the dual optimal solution. We evaluate the proposed formulation using the Allen Developing Mouse Brain Atlas data. Results show that our formulation consistently outperforms methods without the temporal smoothness constraints.
Divide-and-conquer and statistical inference for big data
Authors: Michael I. Jordan
Venue: KDD
Year: 2012

I present some recent work on statistical inference for Big Data. Divide-and-conquer is a natural computational paradigm for approaching Big Data problems, particularly given recent developments in distributed and parallel computing, but some interesting challenges arise when applying divide-and-conquer algorithms to statistical inference problems. One interesting issue is that of obtaining confidence intervals in massive datasets.
Testing the significance of spatio-temporal teleconnection patterns
Authors: Jaya Kawale, Snigdhansu Chatterjee, Dominick Ormsby, Karsten Steinhaeuser, Stefan Liess, Vipin Kumar
Venue: KDD
Year: 2012

Dipoles represent long distance connections between the pressure anomalies of two distant regions that are negatively correlated with each other. Such dipoles have proven important for understanding and explaining the variability in climate in many regions of the world, e.g., the El Nino climate phenomenon is known to be responsible for precipitation and temperature anomalies over large parts of the world. Systematic approaches for dipole detection generate a large number of candidate dipoles, but there exists no method to evaluate the significance of the candidate teleconnections. In this paper, we present a novel method for testing the statistical significance of the class of spatio-temporal teleconnection patterns called as dipoles. One of the most important challenges in addressing significance testing in a spatio-temporal context is how to address the spatial and temporal dependencies that show up as high autocorrelation. We present a novel approach that uses the wild bootstrap to capture the spatio-temporal dependencies, in the special use case of teleconnections in climate data. Our approach to find the statistical significance takes into account the autocorrelation, the seasonality and the trend in the time series over a period of time. This framework is applicable to other problems in spatio-temporal data mining to assess the significance of the patterns.
Experiments in social computation: (and the data they generate)
Authors: Michael J. Kearns
Venue: KDD
Year: 2012

For a number of years we have been conducting controlled human-subject experiments in distributed social computation in networks with only limited and local communication. These experiments cast a number of traditional computational, economic and sociological problems (including graph coloring, consensus, independent set, networked bargaining, biased voting and network formation) as games of strategic interaction in which subjects have financial incentives to collectively "compute" global solutions. I will overview and summarize the many behavioral findings from this line of experimentation. I will give particular emphasis to the novel data the experiments have generated, and the analyses this data has permitted, including quantitative studies of subject "personality" traits such as stubbornness, altruism, and patience, and whether those traits seem helpful or harmful to individual and collective performance.
GeoSearch: georeferenced video retrieval system
Authors: Youngwoo Kim, Jinha Kim, Hwanjo Yu
Venue: KDD
Year: 2012

Conventional video search systems, to find relevant videos, rely on textual data such as video titles, annotations, and text around the video. Nowadays, video recording devices such as ameras, smartphones and car blackboxes are equipped with GPS sensors and able to capture videos with spatiotemporal information such as time, location and camera direction. We call such videos georeferenced videos. This paper presents a georeferenced video retrieval system, geosearch, which efficiently retrieves videos containing a certain point or range in the map. To enable a fast search of georeferenced videos, geosearch adopts a novel data structure MBTR (Minimum Bounding Tilted Rectangle) in the leaf nodes of R-Tree. New algorithms are developed to build MBTRs from georeferenced videos and to efficiently process point and range queries on MBTRs. We demonstrate our system on real georeferenced videos, and show that, compared to previous methods, geosearch substantially reduces the index size and also improves the search speed for georeferenced video data. Our online demo is available at "http://dm.hwanjoyu.org/geosearch".
Building an engine for big data
Authors: Masaru Kitsuregawa
Venue: KDD
Year: 2012

IT program in Japan to build powerful engine for big data was launched. Quite recently the initial version is commercialized. This presentation will give a brief overview of the project. Also some of the potential applications will be introduced.
Efficient evaluation of large sequence kernels
Authors: Pavel P. Kuksa, Vladimir Pavlovic
Venue: KDD
Year: 2012

Classification of sequences drawn from a finite alphabet using a family of string kernels with inexact matching (e.g., spectrum or mismatch) has shown great success in machine learning. However, selection of optimal mismatch kernels for a particular task is severely limited by inability to compute such kernels for long substrings (k-mers) with potentially many mismatches (m). In this work we introduce a new method that allows us to exactly evaluate kernels for large k, m and arbitrary alphabet size. The task can be accomplished by first solving the more tractable problem for small alphabets, and then trivially generalizing to any alphabet using a small linear system of equations. This makes it possible to explore a larger set of kernels with a wide range of kernel parameters, opening a possibility to better model selection and improved performance of the string kernels. To investigate the utility of large (k,m) string kernels, we consider several sequence classification problems, including protein remote homology detection, fold prediction, and music classification. Our results show that increased k-mer lengths with larger substitutions can improve classification performance.
Navigating information facets on twitter (NIF-T)
Authors: Shamanth Kumar, Fred Morstatter, Grant Marshall, Huan Liu, Ullas Nambiar
Venue: KDD
Year: 2012

Recent years have seen an exponential increase in the number of users of social media sites. As the number of users of these sites continues to grow at an extraordinary rate, the amount of data produced follows in magnitude. With this deluge of social media data, the need for comprehensive tools to analyze user interactions is ever increasing. In this paper, we present a novel tool, Navigating Information Facets on Twitter (NIF-T), which helps users to explore data generated on social media sites. Using the three dimensions or facets: time, location, and topic as an example of the many possible facets, we enable the users to explore large social media datasets. With the help of a large corpus of tweets collected from the Occupy Wall Street movement on the Twitter platform we show how our system can be used to identify important aspects of the event along these facets.
Efficient and domain-invariant competitor mining
Authors: Theodoros Lappas, George Valkanas, Dimitrios Gunopulos
Venue: KDD
Year: 2012

In any competitive business, success is based on the ability to make an item more appealing to customers than the competition. A number of questions arise in the context of this task: how do we formalize and quantify the competitiveness relationship between two items? Who are the true competitors of a given item? What are the features of an item that most affect its competitiveness? Despite the impact and relevance of this problem to many domains, only a limited amount of work has been devoted toward an effective solution. In this paper, we present a formal definition of the competitiveness between two items. We present efficient methods for evaluating competitiveness in large datasets and address the natural problem of finding the top-k competitors of a given item. Our methodology is evaluated against strong baselines via a user study and experiments on multiple datasets from different domains.