OpenRaiser/Intern-Atlas huggingface dataset:
Differential identifiability
Authors: Jaewoo Lee, Chris Clifton
Venue: KDD
Year: 2012

A key challenge in privacy-preserving data mining is ensuring that a data mining result does not inherently violate privacy. ε-Differential Privacy appears to provide a solution to this problem. However, there are no clear guidelines on how to set ε to satisfy a privacy policy. We give an alternate formulation, Differential Identifiability, parameterized by the probability of individual identification. This provides the strong privacy guarantees of differential privacy, while letting policy makers set parameters based on the established privacy concept of individual identifiability.
Nine real hard problems we'd like you to solve
Authors: Robin Li
Venue: KDD
Year: 2012

Since 2000, Baidu has set its mission as providing the best way for people to find what they're looking for. Today, the company has become the world's largest Chinese search engine. Everyday, we process billions of search queries and serve hundreds of millions of internet users. The huge volume of online text and multimedia content, as well as user log data, provide us unprecedented opportunities and challenges for further accomplishing our mission. In addition, we have seen several megatrends, cloud computing is becoming a pervasive service infrastructure, mobile internet will surpass traditional internet in user time spend, and social platform has demonstrated its great power. In response to all these opportunities, challenges, and megatrends, we must think ahead on the major technology focuses that may help Baidu to serve our users better. In this talk, I would like to share with the audience the nine areas that are the most important and interesting in my mind. For each of the areas, I will describe the challenges and explain why it is important and interesting. I hope the research community can get excited, and help us provide better services for users.
Interaction and collective intelligence in internet computing
Authors: Deyi Li
Venue: KDD
Year: 2012

Network interconnection, information interoperability, and crowds interaction on the Internet could inspire better computation models than Turing machine, since that human plays an important factor in Internet computing, so that the human-machine and machine-machine interactions have evolved to be the kernel of Internet computing. Internet has not been simply equivalent to a virtual huge computer, or a set of computers. On the Internet, human's behaviors are uncertain, the interactions and influence among people are also uncertain. These uncertainties cannot be described by Turing machine and traditional interaction machine. As a new computation platform, Internet computing requires new theories and methods. By combining topology in mathematics with the field theory in physics, we propose the topological potential approach, which set up a virtual field by the topological space to reflect individual activities, local effects and preferential attachment. This approach can be used to research the emergence of collective intelligence. Here, we introduce three case studies to illustrate the analysis on the collective intelligence on the Internet and discuss some potential applications of the topological potential approach.
Algorithms for mining uncertain graph data
Authors: Jianzhong Li
Venue: KDD
Year: 2012

With the rapid development of advanced data acquisition techniques such as high-throughput biological experiments and wireless sensor networks, large amount of graph-structured data, graph data for short, have been collected in a wide range of applications. Discovering knowledge from graph data has witnessed a number of applications and received a lot of research attentions. Recently, it is observed that uncertainties are inherent in the structures of some graph data. For example, protein-protein interaction (PPI) data can be represented as a graph, where vertices represent proteins, and edges represent PPI's. Due to the limits of PPI detection methods, it is uncertain that a detected PPI exist in practice. Other examples of uncertain graph data include topologies of wireless sensor networks, social networks and so on. Managing and mining such large-scale uncertain graph data is of both theoretical and practical significance. Many solid works have been conducted on uncertain graph mining from the aspects of models, semantics, methodology and algorithms in last few years. A number of research papers on managing and mining uncertain graph data have been published in the database and data mining conferences such as VLDB, ICDE, KDD, CIKM and EDBT. This talk focuses on the data model, semantics, computational complexity and algorithms of uncertain graph mining. In the talk, some typical research work in the field of uncertain graph mining will also be introduced, including frequent subgraph pattern mining, dense subgraph detection, reliable subgraph discovery, and clustering on uncertain graph data.
Similarity search in real world networks
Authors: Cuiping Li
Venue: KDD
Year: 2012

Recently there has been a lot of interest in graph-based analysis. One of the most important aspects of graph-based analysis is to measure similarity between nodes and to do similarity search in a graph. For example, in social networks such as Facebook, system may want to recommend potential friends to a particular user based on connections between users. In custom-product networks such as eBay, one may wish to recommend products to others based on purchases history. In this talk, I will introduce some methods on vertex similarities computations and their applications on similarity search in real world networks.
Multi-domain active learning for text classification
Authors: Lianghao Li, Xiaoming Jin, Sinno Jialin Pan, Jian-Tao Sun
Venue: KDD
Year: 2012

Active learning has been proven to be effective in reducing labeling efforts for supervised learning. However, existing active learning work has mainly focused on training models for a single domain. In practical applications, it is common to simultaneously train classifiers for multiple domains. For example, some merchant web sites (like Amazon.com) may need a set of classifiers to predict the sentiment polarity of product reviews collected from various domains (e.g., electronics, books, shoes). Though different domains have their own unique features, they may share some common latent features. If we apply active learning on each domain separately, some data instances selected from different domains may contain duplicate knowledge due to the common features. Therefore, how to choose the data from multiple domains to label is crucial to further reducing the human labeling efforts in multi-domain learning. In this paper, we propose a novel multi-domain active learning framework to jointly select data instances from all domains with duplicate information considered. In our solution, a shared subspace is first learned to represent common latent features of different domains. By considering the common and the domain-specific features together, the model loss reduction induced by each data instance can be decomposed into a common part and a domain-specific part. In this way, the duplicate information across domains can be encoded into the common part of model loss reduction and taken into account when querying. We compare our method with the state-of-the-art active learning approaches on several text classification tasks: sentiment classification, newsgroup classification and email spam filtering. The experiment results show that our method reduces the human labeling efforts by 33.2%, 42.9% and 68.7% on the three tasks, respectively.
EvaPlanner: an evacuation planner with social-based flocking kinetics
Authors: Cheng-Te Li, Shou-De Lin
Venue: KDD
Year: 2012

This paper demonstrates a system that exploits graph mining, social network analysis, and agent-based crowd simulation techniques to investigate the evacuation dynamics during fire emergency. We create a novel evacuation planning system, EvaPlanner, to deal with three tasks. First, the system identifies the preferable locations to establish the exits to facilitate efficient evacuation from the dangerous areas. Second, it determines the most effective positions to place the emergency signs such that panic crowd can quickly find the exits. Third, it faithfully simulates the evacuation dynamics of crowd considering not only the individual movement kinetics but also the social connections between people. EvaPlanner provides a flexible experimental platform for investigating the evacuation dynamics under a variety of settings, and can further be utilized for animation and movie production. In addition, it can serve as a tool to assist architects address the safety concern during the planning phase. The demo system can be found in the link: http://mslab.csie.ntu.edu.tw/evaplanner/
Fast bregman divergence NMF using taylor expansion and coordinate descent
Authors: Liangda Li, Guy Lebanon, Haesun Park
Venue: KDD
Year: 2012

Non-negative matrix factorization (NMF) provides a lower rank approximation of a matrix. Due to nonnegativity imposed on the factors, it gives a latent structure that is often more physically meaningful than other lower rank approximations such as singular value decomposition (SVD). Most of the algorithms proposed in literature for NMF have been based on minimizing the Frobenius norm. This is partly due to the fact that the minimization problem based on the Frobenius norm provides much more flexibility in algebraic manipulation than other divergences. In this paper we propose a fast NMF algorithm that is applicable to general Bregman divergences. Through Taylor series expansion of the Bregman divergences, we reveal a relationship between Bregman divergences and Euclidean distance. This key relationship provides a new direction for NMF algorithms with general Bregman divergences when combined with the scalar block coordinate descent method. The proposed algorithm generalizes several recently proposed methods for computation of NMF with Bregman divergences and is computationally faster than existing alternatives. We demonstrate the effectiveness of our approach with experiments conducted on artificial as well as real world data.
Towards social user profiling: unified and discriminative influence model for inferring home locations
Authors: Rui Li, Shengjie Wang, Hongbo Deng, Rui Wang, Kevin Chen-Chuan Chang
Venue: KDD
Year: 2012

Users' locations are important to many applications such as targeted advertisement and news recommendation. In this paper, we focus on the problem of profiling users' home locations in the context of social network (Twitter). The problem is nontrivial, because signals, which may help to identify a user's location, are scarce and noisy. We propose a unified discriminative influence model, named as UDI, to solve the problem. To overcome the challenge of scarce signals, UDI integrates signals observed from both social network (friends) and user-centric data (tweets) in a unified probabilistic framework. To overcome the challenge of noisy signals, UDI captures how likely a user connects to a signal with respect to 1) the distance between the user and the signal, and 2) the influence scope of the signal. Based on the model, we develop local and global location prediction methods. The experiments on a large scale data set show that our methods improve the state-of-the-art methods by 13%, and achieve the best performance.
Mining event periodicity from incomplete observations
Authors: Zhenhui Li, Jingjing Wang, Jiawei Han
Venue: KDD
Year: 2012

Advanced technology in GPS and sensors enables us to track physical events, such as human movements and facility usage. Periodicity analysis from the recorded data is an important data mining task which provides useful insights into the physical events and enables us to report outliers and predict future behaviors. To mine periodicity in an event, we have to face real-world challenges of inherently complicated periodic behaviors and imperfect data collection problem. Specifically, the hidden temporal periodic behaviors could be oscillating and noisy, and the observations of the event could be incomplete.
Experiences and lessons in developing industry-strength machine learning and data mining software
Authors: Chih-Jen Lin
Venue: KDD
Year: 2012

Traditionally academic machine learning and data mining researchers focus on proposing new algorithms. The task of implementing these methods is often left to companies that are developing software packages. However, the gap between the two sides has caused some problems. First, the practical deployment of new algorithms still involves some challenging issues that need to be studied by researchers. Second, without further investigation after publishing their papers, researchers have neither the opportunity to work with real problems nor see how their methods are used. We discuss the experiences in developing two machine learning packages LIBSVM and LIBLINEAR, that are widely used in both academia and industry. We demonstrate that the interaction with users leads us to identify some important research problems. For example, the decision to study and then support multi-class SVM was essential in the early stage of developing LIBSVM. The birth of LIBLINEAR was driven by the need to classify large-scale documents in Internet companies. For fast training of large-scale problems, we had to create new algorithms other than those used in LIBSVM for kernel SVM. We present some practical use of LIBLINEAR for Internet applications. Finally, we give lessons learned and future perspectives for developing industry-strength machine learning and data mining software.
Stratified k-means clustering over a deep web data source
Authors: Tantan Liu, Gagan Agrawal
Venue: KDD
Year: 2012

This paper focuses on the problem of clustering data from a {\em hidden} or a deep web data source. A key characteristic of deep web data sources is that data can only be accessed through the limited query interface they support. Because the underlying data set cannot be accessed directly, data mining must be performed based on sampling of the datasets. The samples, in turn, can only be obtained by querying the deep web databases with specific inputs.
Event-based social networks: linking the online and offline social worlds
Authors: Xingjie Liu, Qi He, Yuanyuan Tian, Wang-Chien Lee, John McPherson, Jiawei Han
Venue: KDD
Year: 2012

Newly emerged event-based online social services, such as Meetup and Plancast, have experienced increased popularity and rapid growth. From these services, we observed a new type of social network - event-based social network (EBSN). An EBSN does not only contain online social interactions as in other conventional online social networks, but also includes valuable offline social interactions captured in offline activities. By analyzing real data collected from Meetup, we investigated EBSN properties and discovered many unique and interesting characteristics, such as heavy-tailed degree distributions and strong locality of social interactions.
Automatic taxonomy construction from keywords
Authors: Xueqing Liu, Yangqiu Song, Shixia Liu, Haixun Wang
Venue: KDD
Year: 2012

Taxonomies, especially the ones in specific domains, are becoming indispensable to a growing number of applications. State-of-the-art approaches assume there exists a text corpus to accurately characterize the domain of interest, and that a taxonomy can be derived from the text corpus using information extraction techniques. In reality, neither assumption is valid, especially for highly focused or fast-changing domains. In this paper, we study a challenging problem: Deriving a taxonomy from a set of keyword phrases. A solution can benefit many real life applications because i) keywords give users the flexibility and ease to characterize a specific domain; and ii) in many applications, such as online advertisements, the domain of interest is already represented by a set of keywords. However, it is impossible to create a taxonomy out of a keyword set itself. We argue that additional knowledge and contexts are needed. To this end, we first use a general purpose knowledgebase and keyword search to supply the required knowledge and context. Then we develop a Bayesian approach to build a hierarchical taxonomy for a given set of keywords. We reduce the complexity of previous hierarchical clustering approaches from O(n2 log n) to O(n log n), so that we can derive a domain specific taxonomy from one million keyword phrases in less than an hour. Finally, we conduct comprehensive large scale experiments to show the effectiveness and efficiency of our approach. A real life example of building an insurance-related query taxonomy illustrates the usefulness of our approach for specific domains.
AssocExplorer: an association rule visualization system for exploratory data analysis
Authors: Guimei Liu, Andre Suchitra, Haojun Zhang, Mengling Feng, See-Kiong Ng, Limsoon Wong
Venue: KDD
Year: 2012

We present a system called AssocExplorer to support exploratory data analysis via association rule visualization and exploration. AssocExplorer is designed by following the visual information-seeking mantra: overview first, zoom and filter, then details on demand. It effectively uses coloring to deliver information so that users can easily detect things that are interesting to them. If users find a rule interesting, they can explore related rules for further analysis, which allows users to find interesting phenomenon that are difficult to detect when rules are examined separately. Our system also allows users to compare rules and inspect rules with similar item composition but different statistics so that the key factors that contribute to the difference can be isolated.
Accelerating minor allele frequency computation with graphics processors
Authors: Mian Lu, Jiuxin Zhao, Qiong Luo, Bingqiang Wang
Venue: KDD
Year: 2012

The computation of minor allele frequency (MAF) is at the core of a Genome-Wide Association Study (GWAS). Due to the high computation intensity and high precision requirement, so far the scale of MAF computation analysis is up to hundreds of individuals. To enable the computation for thousands of individuals, we have developed GAMA, a high performance MAF computation program with GPU acceleration. Specifically, we design a parallel reduction algorithm that matches the GPU's data-parallel architecture. To implement the new algorithm efficiently on the GPU, we utilize the fast, on-chip local memory shared within each GPU multiprocessor effectively. To avoid user-level thread synchronization, we exploit the GPU thread-warp based scheduling. Furthermore, we address the floating point underflow issue through a logarithm transformation. As a result, GAMA enables MAF computation for up to a thousand individuals for the first time. On a server equipped with an NVIDIA Tesla C2070 GPU and two Intel Xeon E5520 2.27 GHz CPUs, GAMA outperforms a state-of-the-art single-threaded MAF computation tool and our optimized parallel implementation (16-threaded) on the CPU by around 47 and 3.5 times, respectively.
Semantic search and a new moore's law effect in knowledge engineering
Authors: Wei-Ying Ma
Venue: KDD
Year: 2012

In history, the Moore's law effect has been used to describe phenomena of exponential improvement in technology when it has a virtuous cycle that makes technology improvement proportional to technology itself. For example, chip performance had doubled every 18-24 months because better processors support the development of better layout tools that support the development of even better processors. I will describe a new Moore's law effect that is being created in knowledge engineering and is driven by the self-reinforcing nature of three trends and technical advancements: big data, machine learning, and Internet economics. I will explain how we can take advantage of this new effect to develop a new generation of semantic and knowledge-based search engines. Specifically, my presentation will cover the following three areas:
Subscriber classification within telecom networks utilizing big data technologies and machine learning
Authors: Jonathan Magnusson, Tor Kvernvik
Venue: KDD
Year: 2012

This paper describes a scalable solution for identifying influential subscribers in for example telecom networks. The solution estimates one weighted value of influence out of several Social Network Analysis(SNA) metrics. The novel method for aggregation of several metrics utilizes machine learning to train models. A prototype solution has been implemented on a Hadoop platform to support scalability and to reduce hard ware cost by enabling the usage of commodity computers. The SNA algorithms have been adapted to efficiently execute on the MapReduce distributed platform. The prototype solution has been tested on a Hadoop cluster. The tests have verified that the solution can scale to support networks with millions of subscribers. Both real data from a telecom network operator with 2.4 million subscribers and synthetic data for networks up to 100 million subscribers have been used to verify the scalability and accuracy of the solution. The correlation between metrics have been analyzed to identify the information gain from each metric.
Fast mining and forecasting of complex time-stamped events
Authors: Yasuko Matsubara, Yasushi Sakurai, Christos Faloutsos, Tomoharu Iwata, Masatoshi Yoshikawa
Venue: KDD
Year: 2012

Given huge collections of time-evolving events such as web-click logs, which consist of multiple attributes (e.g., URL, userID, times- tamp), how do we find patterns and trends? How do we go about capturing daily patterns and forecasting future events? We need two properties: (a) effectiveness, that is, the patterns should help us understand the data, discover groups, and enable forecasting, and (b) scalability, that is, the method should be linear with the data size. We introduce TriMine, which performs three-way mining for all three attributes, namely, URLs, users, and time. Specifically TriMine discovers hidden topics, groups of URLs, and groups of users, simultaneously. Thanks to its concise but effective summarization, it makes it possible to accomplish the most challenging and important task, namely, to forecast future events. Extensive experiments on real datasets demonstrate that TriMine discovers meaningful topics and makes long-range forecasts, which are notoriously difficult to achieve. In fact, TriMine consistently outperforms the best state-of-the-art existing methods in terms of accuracy and execution speed (up to 74x faster).
Linear support vector machines via dual cached loops
Authors: Shin Matsushima, S. V. N. Vishwanathan, Alexander J. Smola
Venue: KDD
Year: 2012

Modern computer hardware offers an elaborate hierarchy of storage subsystems with different speeds, capacities, and costs associated with them. Furthermore, processors are now inherently parallel offering the execution of several diverse threads simultaneously. This paper proposes StreamSVM, the first algorithm for training linear Support Vector Machines (SVMs) which takes advantage of these properties by integrating caching with optimization. StreamSVM works by performing updates in the dual, thus obviating the need to rebalance frequently visited examples. Furthermore we trade off file I/O with data expansion on the fly by generating features on demand. This significantly increases throughput. Experiments show that StreamSVM outperforms other linear SVM solvers, including the award winning work of [38], by orders of magnitude and produces more accurate solutions within a shorter amount of time.