waashk/dblp huggingface dataset:
topic dynamics: an alternative model of bursts in streams of topics. for some time there has been increasing interest in the problem of monitoring the occurrence of topics in a stream of events, such as a stream of news articles. this has led to different models of bursts in these streams, i.e., periods of elevated occurrence of events. today there are several burst definitions and detection algorithms, and their differences can produce very different results in topic streams. these definitions also share a fundamental problem: they define bursts in terms of an arrival rate. this approach is limiting; other stream dimensions can matter. we reconsider the idea of bursts from the standpoint of a simple kind of physics. instead of focusing on arrival rates, we reconstruct bursts as a dynamic phenomenon, using kinetics concepts from physics -- mass and velocity -- and derive momentum, acceleration, and force from these. we refer to the result as topic dynamics, permitting a hierarchical, expressive model of bursts as intervals of increasing momentum. as a sample application, we present a topic dynamics model for the large pubmed/medline database of biomedical publications, using the mesh (medical subject heading) topic hierarchy. we show our model is able to detect bursts for mesh terms accurately as well as efficiently.
community-based greedy algorithm for mining top-k influential nodes in mobile social networks. with the proliferation of mobile devices and wireless technologies, mobile social network systems are increasingly available. a mobile social network plays an essential role as the spread of information and influence in the form of "word-of-mouth". it is a fundamental issue to find a subset of influential individuals in a mobile social network such that targeting them initially (e.g. to adopt a new product) will maximize the spread of the influence (further adoptions of the new product). the problem of finding the most influential nodes is unfortunately np-hard. it has been shown that a greedy algorithm with provable approximation guarantees can give good approximation; however, it is computationally expensive, if not prohibitive, to run the greedy algorithm on a large mobile network. in this paper we propose a new algorithm called community-based greedy algorithm for mining top-k influential nodes. the proposed algorithm encompasses two components: 1) an algorithm for detecting communities in a social network by taking into account information diffusion; and 2) a dynamic programming algorithm for selecting communities to find influential nodes. we also provide provable approximation guarantees for our algorithm. empirical studies on a large real-world mobile social network show that our algorithm is more than an order of magnitudes faster than the state-of-the-art greedy algorithm for finding top-k influential nodes and the error of our approximate algorithm is small.
data mining with differential privacy. we consider the problem of data mining with formal privacy guarantees, given a data access interface based on the differential privacy framework. differential privacy requires that computations be insensitive to changes in any particular individual's record, thereby restricting data leaks through the results. the privacy preserving interface ensures unconditionally safe access to the data and does not require from the data miner any expertise in privacy. however, as we show in the paper, a naive utilization of the interface to construct privacy preserving data mining algorithms could lead to inferior data mining results. we address this problem by considering the privacy and the algorithmic requirements simultaneously, focusing on decision tree induction as a sample application. the privacy mechanism has a profound effect on the performance of the methods chosen by the data miner. we demonstrate that this choice could make the difference between an accurate classifier and a completely useless one. moreover, an improved algorithm can achieve the same level of accuracy and privacy as the naive implementation but with an order of magnitude fewer learning samples.
discovery of significant emerging trends. we describe a system that monitors social and mainstream media to determine shifts in what people are thinking about a product or company. we process over 100,000 news articles, blog posts, review sites, and tweets a day for mentions of items (e.g., products) of interest, extract phrases that are mentioned near them, and determine which of the phrases are of greatest possible interest to, for example, brand managers. case studies show a good ability to rapidly pinpoint emerging subjects buried deep in large volumes of data and then highlight those that are rising or falling in significance as they relate to the firms interests. the tool and algorithm improves the signal-to-noise ratio and pinpoints precisely the opportunities and risks that matter most to communications professionals and their organizations.
mining advisor-advisee relationships from research publication networks. information network contains abundant knowledge about relationships among people or entities. unfortunately, such kind of knowledge is often hidden in a network where different kinds of relationships are not explicitly categorized. for example, in a research publication network, the advisor-advisee relationships among researchers are hidden in the coauthor network. discovery of those relationships can benefit many interesting applications such as expert finding and research community analysis. in this paper, we take a computer science bibliographic network as an example, to analyze the roles of authors and to discover the likely advisor-advisee relationships. in particular, we propose a time-constrained probabilistic factor graph model (tpfg), which takes a research publication network as input and models the advisor-advisee relationship mining problem using a jointly likelihood objective function. we further design an efficient learning algorithm to optimize the objective function. based on that our model suggests and ranks probable advisors for every author. experimental results show that the proposed approach infer advisor-advisee relationships efficiently and achieves a state-of-the-art accuracy (80-90%). we also apply the discovered advisor-advisee relationships to bole search, a specific expert finding task and empirical study shows that the search performance can be effectively improved (+4.09% by ndcg@5).
suggesting friends using the implicit social graph. although users of online communication tools rarely categorize their contacts into groups such as "family", "co-workers", or "jogging buddies", they nonetheless implicitly cluster contacts, by virtue of their interactions with them, forming implicit groups. in this paper, we describe the implicit social graph which is formed by users' interactions with contacts and groups of contacts, and which is distinct from explicit social graphs in which users explicitly add other individuals as their "friends". we introduce an interaction-based metric for estimating a user's affinity to his contacts and groups. we then describe a novel friend suggestion algorithm that uses a user's implicit social graph to generate a friend group, given a small seed set of contacts which the user has already labeled as friends. we show experimental results that demonstrate the importance of both implicit group relationships and interaction-based affinity ranking in suggesting friends. finally, we discuss two applications of the friend suggest algorithm that have been released as gmail labs features.
data winnowing. massive quantities of digital data are being collected in every aspect of modern life. examples include personal photos and videos, biological and medical images and recordings from sensor arrays. to transform these massive data streams into useful information we use a sequence of "winnowing" stages. each step reduces the size of the data by an order of magnitude; extracting the wheat form the chaff. in this talk i will describe this approach in a variety of contexts, ranging from the analysis of genetic pathways in fruit-fly embryos and c-elegans worms to counting birds and helping elderly people living alone keep in touch with their family and caregivers.
scalable similarity search with optimized kernel hashing. scalable similarity search is the core of many large scale learning or data mining applications. recently, many research results demonstrate that one promising approach is creating compact and efficient hash codes that preserve data similarity. by efficient, we refer to the low correlation (and thus low redundancy) among generated codes. however, most existing hash methods are designed only for vector data. in this paper, we develop a new hashing algorithm to create efficient codes for large scale data of general formats with any kernel function, including kernels on vectors, graphs, sequences, sets and so on. starting with the idea analogous to spectral hashing, novel formulations and solutions are proposed such that a kernel based hash function can be explicitly represented and optimized, and directly applied to compute compact hash codes for new samples of general formats. moreover, we incorporate efficient techniques, such as nystrom approximation, to further reduce time and space complexity for indexing and search, making our algorithm scalable to huge data sets. another important advantage of our method is the ability to handle diverse types of similarities according to actual task requirements, including both feature similarities and semantic similarities like label consistency. we evaluate our method using both vector and non-vector data sets at a large scale up to 1 million samples. our comprehensive results show the proposed method outperforms several state-of-the-art approaches for all the tasks, with a significant gain for most tasks.
scalable influence maximization for prevalent viral marketing in large-scale social networks. influence maximization, defined by kempe, kleinberg, and tardos (2003), is the problem of finding a small set of seed nodes in a social network that maximizes the spread of influence under certain influence cascade models. the scalability of influence maximization is a key factor for enabling prevalent viral marketing in large-scale online social networks. prior solutions, such as the greedy algorithm of kempe et al. (2003) and its improvements are slow and not scalable, while other heuristic algorithms do not provide consistently good performance on influence spreads. in this paper, we design a new heuristic algorithm that is easily scalable to millions of nodes and edges in our experiments. our algorithm has a simple tunable parameter for users to control the balance between the running time and the influence spread of the algorithm. our results from extensive simulations on several real-world and synthetic networks demonstrate that our algorithm is currently the best scalable solution to the influence maximization problem: (a) our algorithm scales beyond million-sized graphs where the greedy algorithm becomes infeasible, and (b) in all size ranges, our algorithm performs consistently well in influence spread --- it is always among the best algorithms, and in most cases it significantly outperforms all other scalable heuristics to as much as 100%--260% increase in influence spread.
overlapping experiment infrastructure: more, better, faster experimentation. at google, experimentation is practically a mantra; we evaluate almost every change that potentially affects what our users experience. such changes include not only obvious user-visible changes such as modifications to a user interface, but also more subtle changes such as different machine learning algorithms that might affect ranking or content selection. our insatiable appetite for experimentation has led us to tackle the problems of how to run more experiments, how to run experiments that produce better decisions, and how to run them faster. in this paper, we describe google's overlapping experiment infrastructure that is a key component to solving these problems. in addition, because an experiment infrastructure alone is insufficient, we also discuss the associated tools and educational processes required to use it effectively. we conclude by describing trends that show the success of this overall experimental environment. while the paper specifically describes the experiment system and experimental processes we have in place at google, we believe they can be generalized and applied by any entity interested in using experimentation to improve search engines and other web applications.
unsupervised feature selection for multi-cluster data. in many data analysis tasks, one is often confronted with very high dimensional data. feature selection techniques are designed to find the relevant feature subset of the original features which can facilitate clustering, classification and retrieval. in this paper, we consider the feature selection problem in unsupervised learning scenario, which is particularly difficult due to the absence of class labels that would guide the search for relevant information. the feature selection problem is essentially a combinatorial optimization problem which is computationally expensive. traditional unsupervised feature selection methods address this issue by selecting the top ranked features based on certain scores computed independently for each feature. these approaches neglect the possible correlation between different features and thus can not produce an optimal feature subset. inspired from the recent developments on manifold learning and l1-regularized models for subset selection, we propose in this paper a new approach, called multi-cluster feature selection (mcfs), for unsupervised feature selection. specifically, we select those features such that the multi-cluster structure of the data can be best preserved. the corresponding optimization problem can be efficiently solved since it only involves a sparse eigen-problem and a l1-regularized least squares problem. extensive experimental results over various real-life data sets have demonstrated the superiority of the proposed algorithm.
online discovery and maintenance of time series motifs. the detection of repeated subsequences, time series motifs, is a problem which has been shown to have great utility for several higher-level data mining algorithms, including classification, clustering, segmentation, forecasting, and rule discovery. in recent years there has been significant research effort spent on efficiently discovering these motifs in static offline databases. however, for many domains, the inherent streaming nature of time series demands online discovery and maintenance of time series motifs. in this paper, we develop the first online motif discovery algorithm which monitors and maintains motifs exactly in real time over the most recent history of a stream. our algorithm has a worst-case update time which is linear to the window size and is extendible to maintain more complex pattern structures. in contrast, the current offline algorithms either need significant update time or require very costly pre-processing steps which online algorithms simply cannot afford. our core ideas allow useful extensions of our algorithm to deal with arbitrary data rates and discovering multidimensional motifs. we demonstrate the utility of our algorithms with a variety of case studies in the domains of robotics, acoustic monitoring and online compression.
a hierarchical information theoretic technique for the discovery of non linear alternative clusterings. discovery of alternative clusterings is an important method for exploring complex datasets. it provides the capability for the user to view clustering behaviour from different perspectives and thus explore new hypotheses. however, current algorithms for alternative clustering have focused mainly on linear scenarios and may not perform as desired for datasets containing clusters with non linear shapes. our goal in this paper is to address this challenge of non linearity. in particular, we propose a novel algorithm to uncover an alternative clustering that is distinctively different from an existing, reference clustering. our technique is information theory based and aims to ensure alternative clustering quality by maximizing the mutual information between clustering labels and data observations, whilst at the same time ensuring alternative clustering distinctiveness by minimizing the information sharing between the two clusterings. we perform experiments to assess our method against a large range of alternative clustering algorithms in the literature. we show our technique's performance is generally better for non-linear scenarios and furthermore, is highly competitive even for simpler, linear scenarios.
the quantification of advertising: (+ lessons from building businesses based on large scale data mining). as electronic communication, media and commerce increasingly permeate every aspect of modern life, real-time personalization of consumer experience through data-mining becomes practical. effective classification, prediction and change modeling of consumer interests, behaviors and purchasing habits using machine learning and statistical methods drives efficiency, insights and consumer relevance that were never before possible. the internet has brought on a rapid evolution in advertising. everything about behavior on the internet can be quantified and responses to behavior can occur in real time. this dynamic interaction with the user has created opportunities to better understand the way in which individuals move from awareness of a product to considering a purchase, through to intent and ultimately a sale for the marketer. when a marketer can answer the question 'did those tv ads cause consumers to switch shampoo brands?' they can model behavior change and adjust marketing strategies accordingly. underpinning this shift in how the world's trillion dollar marketing budget is spent is transactional data on an unprecedented scale, creating new challenges for software that must interpret this stream and make real time decisions tens, even hundreds of thousands of times every second. i will explore advances in modeling media consumption, advertising response and the real-time evaluation of media opportunities through reference to quantcast, a business launched in september 2006 which today interprets in excess of 10 billion new digital media consumption records every day. we will examine the challenges of applying machine learning to non-search advertising and in doing so explore the creation of business environments - organization, infrastructure, tools, processes (and costs considerations) - in which scientists can quickly develop new petabyte scale algorithmic approaches, migrate them rapidly to real-time production and deliver fully customized experiences for marketers, publishers and consumers alike.
the new iris data: modular data generators. in this paper we introduce a modular, highly flexible, open-source environment for data generation. using an existing graphical data flow tool, the user can combine various types of modules for numeric and categorical data generators. additional functionality is added via the data processing framework in which the generator modules are embedded. the resulting data flows can be used to document, deploy, and reuse the resulting data generators. we describe the overall environment and individual modules and demonstrate how they can be used for the generation of a sample, complex customer/product database with corresponding shopping basket data, including various artifacts and outliers.
an efficient algorithm for a class of fused lasso problems. the fused lasso penalty enforces sparsity in both the coefficients and their successive differences, which is desirable for applications with features ordered in some meaningful way. the resulting problem is, however, challenging to solve, as the fused lasso penalty is both non-smooth and non-separable. existing algorithms have high computational complexity and do not scale to large-size problems. in this paper, we propose an efficient fused lasso algorithm (efla) for optimizing this class of problems. one key building block in the proposed efla is the fused lasso signal approximator (flsa). to efficiently solve flsa, we propose to reformulate it as the problem of finding an "appropriate" subgradient of the fused penalty at the minimizer, and develop a subgradient finding algorithm (sfa). we further design a restart technique to accelerate the convergence of sfa, by exploiting the special "structures" of both the original and the reformulated flsa problems. our empirical evaluations show that, both sfa and efla significantly outperform existing solvers. we also demonstrate several applications of the fused lasso.
mining positive and negative patterns for relevance feature discovery. it is a big challenge to guarantee the quality of discovered relevance features in text documents for describing user preferences because of the large number of terms, patterns, and noise. most existing popular text mining and classification methods have adopted term-based approaches. however, they have all suffered from the problems of polysemy and synonymy. over the years, people have often held the hypothesis that pattern-based methods should perform better than term-based ones in describing user preferences, but many experiments do not support this hypothesis. the innovative technique presented in paper makes a breakthrough for this difficulty. this technique discovers both positive and negative patterns in text documents as higher level features in order to accurately weight low-level features (terms) based on their specificity and their distributions in the higher level features. substantial experiments using this technique on reuters corpus volume 1 and trec topics show that the proposed approach significantly outperforms both the state-of-the-art term-based methods underpinned by okapi bm25, rocchio or support vector machine and pattern based methods on precision, recall and f measures.
ensemble pruning via individual contribution ordering. an ensemble is a set of learned models that make decisions collectively. although an ensemble is usually more accurate than a single learner, existing ensemble methods often tend to construct unnecessarily large ensembles, which increases the memory consumption and computational cost. ensemble pruning tackles this problem by selecting a subset of ensemble members to form subensembles that are subject to less resource consumption and response time with accuracy that is similar to or better than the original ensemble. in this paper, we analyze the accuracy/diversity trade-off and prove that classifiers that are more accurate and make more predictions in the minority group are more important for subensemble construction. based on the gained insights, a heuristic metric that considers both accuracy and diversity is proposed to explicitly evaluate each individual classifier's contribution to the whole ensemble. by incorporating ensemble members in decreasing order of their contributions, subensembles are formed such that users can select the top $p$ percent of ensemble members, depending on their resource availability and tolerable waiting time, for predictions. experimental results on 26 uci data sets show that subensembles formed by the proposed epic (ensemble pruning via individual contribution ordering) algorithm outperform the original ensemble and a state-of-the-art ensemble pruning method, orientation ordering (oo).