waashk/dblp huggingface dataset:
semi-supervised feature selection for graph classification. the problem of graph classification has attracted great interest in the last decade. current research on graph classification assumes the existence of large amounts of labeled training graphs. however, in many applications, the labels of graph data are very expensive or difficult to obtain, while there are often copious amounts of unlabeled graph data available. in this paper, we study the problem of semi-supervised feature selection for graph classification and propose a novel solution, called gssc, to efficiently search for optimal subgraph features with labeled and unlabeled graphs. different from existing feature selection methods in vector spaces which assume the feature set is given, we perform semi-supervised feature selection for graph data in a progressive way together with the subgraph feature mining process. we derive a feature evaluation criterion, named gsemi, to estimate the usefulness of subgraph features based upon both labeled and unlabeled graphs. then we propose a branch-and-bound algorithm to efficiently search for optimal subgraph features by judiciously pruning the subgraph search space. empirical studies on several real-world tasks demonstrate that our semi-supervised feature selection approach can effectively boost graph classification performances with semi-supervised feature selection and is very efficient by pruning the subgraph search space using both labeled and unlabeled graphs.
estimating rates of rare events with multiple hierarchies through scalable log-linear models. we consider the problem of estimating rates of rare events for high dimensional, multivariate categorical data where several dimensions are hierarchical. such problems are routine in several data mining applications including computational advertising, our main focus in this paper. we propose lmmh, a novel log-linear modeling method that scales to massive data applications with billions of training records and several million potential predictors in a map-reduce framework. our method exploits correlations in aggregates observed at multiple resolutions when working with multiple hierarchies; stable estimates at coarser resolution provide informative prior information to improve estimates at finer resolutions. other than prediction accuracy and scalability, our method has an inbuilt variable screening procedure based on a "spike and slab prior" that provides parsimony by removing non-informative predictors without hurting predictive accuracy. we perform large scale experiments on data from real computational advertising applications and illustrate our approach on datasets with several billion records and hundreds of millions of predictors. extensive comparisons with other benchmark methods show significant improvements in prediction accuracy.
towards mobility-based clustering. identifying hot spots of moving vehicles in an urban area is essential to many smart city applications. the practical research on hot spots in smart city presents many unique features, such as highly mobile environments, supremely limited size of sample objects, and the non-uniform, biased samples. all these features have raised new challenges that make the traditional density-based clustering algorithms fail to capture the real clustering property of objects, making the results less meaningful. in this paper we propose a novel, non-density-based approach called mobility-based clustering. the key idea is that sample objects are employed as "sensors" to perceive the vehicle crowdedness in nearby areas using their instant mobility, rather than the "object representatives". as such the mobility of samples is naturally incorporated. several key factors beyond the vehicle crowdedness have been identified and techniques to compensate these effects are proposed. we evaluate the performance of mobility-based clustering based on real traffic situations. experimental results show that using 0.3% of vehicles as the samples, mobility-based clustering can accurately identify hot spots which can hardly be obtained by the latest representative algorithm umicro.
connecting the dots between news articles. the process of extracting useful knowledge from large datasets has become one of the most pressing problems in today's society. the problem spans entire sectors, from scientists to intelligence analysts and web users, all of whom are constantly struggling to keep up with the larger and larger amounts of content published every day. with this much data, it is often easy to miss the big picture. in this paper, we investigate methods for automatically connecting the dots -- providing a structured, easy way to navigate within a new topic and discover hidden connections. we focus on the news domain: given two news articles, our system automatically finds a coherent chain linking them together. for example, it can recover the chain of events starting with the decline of home prices (january 2007), and ending with the ongoing health-care debate. we formalize the characteristics of a good chain and provide an efficient algorithm (with theoretical guarantees) to connect two fixed endpoints. we incorporate user feedback into our framework, allowing the stories to be refined and personalized. finally, we evaluate our algorithm over real news data. our user studies demonstrate the algorithm's effectiveness in helping users understanding the news.
tropical cyclone event sequence similarity search via dimensionality reduction and metric learning. the earth observing system data and information system (eosdis) is a comprehensive data and information system which archives, manages, and distributes earth science data from the eos spacecrafts. one non-existent capability in the eosdis is the retrieval of satellite sensor data based on weather events (such as tropical cyclones) similarity query output. in this paper, we propose a framework to solve the similarity search problem given user-defined instance-level constraints for tropical cyclone events, represented by arbitrary length multidimensional spatio-temporal data sequences. a critical component for such a problem is the similarity/metric function to compare the data sequences. we describe a novel longest common subsequence (lcss) parameter learning approach driven by nonlinear dimensionality reduction and distance metric learning. intuitively, arbitrary length multidimensional data sequences are projected into a fixed dimensional manifold for lcss parameter learning. similarity search is achieved through consensus among the (similar) instance-level constraints based on ranking orders computed using the lcss-based similarity measure. experimental results using a combination of synthetic and real tropical cyclone event data sequences are presented to demonstrate the feasibility of our parameter learning approach and its robustness to variability in the instance constraints. we, then, use a similarity query example on real tropical cyclone event data sequences from 2000 to 2008 to discuss (i) a problem of scientific interest, and (ii) challenges and issues related to the weather event similarity search problem.
finding effectors in social networks. assume a network (v,e) where a subset of the nodes in v are active. we consider the problem of selecting a set of k active nodes that best explain the observed activation state, under a given information-propagation model. we call these nodes effectors. we formally define the k-effectors problem and study its complexity for different types of graphs. we show that for arbitrary graphs the problem is not only np-hard to solve optimally, but also np-hard to approximate. we also show that, for some special cases, the problem can be solved optimally in polynomial time using a dynamic-programming algorithm. to the best of our knowledge, this is the first work to consider the k-effectors problem in networks. we experimentally evaluate our algorithms using the dblp co-authorship graph, where we search for effectors of topics that appear in research papers.
document clustering via dirichlet process mixture model with feature selection. one essential issue of document clustering is to estimate the appropriate number of clusters for a document collection to which documents should be partitioned. in this paper, we propose a novel approach, namely dpmfs, to address this issue. the proposed approach is designed 1) to group documents into a set of clusters while the number of document clusters is determined by the dirichlet process mixture model automatically; 2) to identify the discriminative words and separate them from irrelevant noise words via stochastic search variable selection technique. we explore the performance of our proposed approach on both a synthetic dataset and several realistic document datasets. the comparison between our proposed approach and stage-of-the-art document clustering approaches indicates that our approach is robust and effective for document clustering.
privacy-preserving outsourcing support vector machines with random transformation. outsourcing the training of support vector machines (svm) to external service providers benefits the data owner who is not familiar with the techniques of the svm or has limited computing resources. in outsourcing, the data privacy is a critical issue for some legal or commercial reasons since there may be sensitive information contained in the data. existing privacy-preserving svm works are either not applicable to outsourcing or weak in security. in this paper, we propose a scheme for privacy-preserving outsourcing the training of the svm without disclosing the actual content of the data to the service provider. in the proposed scheme, the data sent to the service provider is perturbed by a random transformation, and the service provider trains the svm for the data owner from the perturbed data. the proposed scheme is stronger in security than existing techniques, and incurs very little redundant communication and computation cost.
beyond heuristics: learning to classify vulnerabilities and predict exploits. the security demands on modern system administration are enormous and getting worse. chief among these demands, administrators must monitor the continual ongoing disclosure of software vulnerabilities that have the potential to compromise their systems in some way. such vulnerabilities include buffer overflow errors, improperly validated inputs, and other unanticipated attack modalities. in 2008, over 7,400 new vulnerabilities were disclosed--well over 100 per week. while no enterprise is affected by all of these disclosures, administrators commonly face many outstanding vulnerabilities across the software systems they manage. vulnerabilities can be addressed by patches, reconfigurations, and other workarounds; however, these actions may incur down-time or unforeseen side-effects. thus, a key question for systems administrators is which vulnerabilities to prioritize. from publicly available databases that document past vulnerabilities, we show how to train classifiers that predict whether and how soon a vulnerability is likely to be exploited. as input, our classifiers operate on high dimensional feature vectors that we extract from the text fields, time stamps, cross references, and other entries in existing vulnerability disclosure reports. compared to current industry-standard heuristics based on expert knowledge and static formulas, our classifiers predict much more accurately whether and how soon individual vulnerabilities are likely to be exploited.
up-growth: an efficient algorithm for high utility itemset mining. mining high utility itemsets from a transactional database refers to the discovery of itemsets with high utility like profits. although a number of relevant approaches have been proposed in recent years, they incur the problem of producing a large number of candidate itemsets for high utility itemsets. such a large number of candidate itemsets degrades the mining performance in terms of execution time and space requirement. the situation may become worse when the database contains lots of long transactions or long high utility itemsets. in this paper, we propose an efficient algorithm, namely up-growth (utility pattern growth), for mining high utility itemsets with a set of techniques for pruning candidate itemsets. the information of high utility itemsets is maintained in a special data structure named up-tree (utility pattern tree) such that the candidate itemsets can be generated efficiently with only two scans of the database. the performance of up-growth was evaluated in comparison with the state-of-the-art algorithms on different types of datasets. the experimental results show that up-growth not only reduces the number of candidates effectively but also outperforms other algorithms substantially in terms of execution time, especially when the database contains lots of long transactions.
flexible constrained spectral clustering. constrained clustering has been well-studied for algorithms like k-means and hierarchical agglomerative clustering. however, how to encode constraints into spectral clustering remains a developing area. in this paper, we propose a flexible and generalized framework for constrained spectral clustering. in contrast to some previous efforts that implicitly encode must-link and cannot-link constraints by modifying the graph laplacian or the resultant eigenspace, we present a more natural and principled formulation, which preserves the original graph laplacian and explicitly encodes the constraints. our method offers several practical advantages: it can encode the degree of belief (weight) in must-link and cannot-link constraints; it guarantees to lower-bound how well the given constraints are satisfied using a user-specified threshold; and it can be solved deterministically in polynomial time through generalized eigendecomposition. furthermore, by inheriting the objective function from spectral clustering and explicitly encoding the constraints, much of the existing analysis of spectral clustering techniques is still valid. consequently our work can be posed as a natural extension to unconstrained spectral clustering and be interpreted as finding the normalized min-cut of a labeled graph. we validate the effectiveness of our approach by empirical results on real-world data sets, with applications to constrained image segmentation and clustering benchmark data sets with both binary and degree-of-belief constraints.
gls-sod: a generalized local statistical approach for spatial outlier detection. local based approach is a major category of methods for spatial outlier detection (sod). currently, there is a lack of systematic analysis on the statistical properties of this framework. for example, most methods assume identical and independent normal distributions (i.i.d. normal) for the calculated local differences, but no justifications for this critical assumption have been presented. the methods' detection performance on geostatistic data with linear or nonlinear trend is also not well studied. in addition, there is a lack of theoretical connections and empirical comparisons between local and global based sod approaches. this paper discusses all these fundamental issues under the proposed generalized local statistical (gls) framework. furthermore, robust estimation and outlier detection methods are designed for the new gls model. extensive simulations demonstrated that the sod method based on the gls model significantly outperformed all existing approaches when the spatial data exhibits a linear or nonlinear trend.
divrank: the interplay of prestige and diversity in information networks. information networks are widely used to characterize the relationships between data items such as text documents. many important retrieval and mining tasks rely on ranking the data items based on their centrality or prestige in the network. beyond prestige, diversity has been recognized as a crucial objective in ranking, aiming at providing a non-redundant and high coverage piece of information in the top ranked results. nevertheless, existing network-based ranking approaches either disregard the concern of diversity, or handle it with non-optimized heuristics, usually based on greedy vertex selection. we propose a novel ranking algorithm, divrank, based on a reinforced random walk in an information network. this model automatically balances the prestige and the diversity of the top ranked vertices in a principled way. divrank not only has a clear optimization explanation, but also well connects to classical models in mathematics and network science. we evaluate divrank using empirical experiments on three different networks as well as a text summarization task. divrank outperforms existing network-based ranking methods in terms of enhancing diversity in prestige.
mass estimation and its applications. this paper introduces mass estimation--a base modelling mechanism in data mining. it provides the theoretical basis of mass and an efficient method to estimate mass. we show that it solves problems very effectively in tasks such as information retrieval, regression and anomaly detection. the models, which use mass in these three tasks, perform at least as good as and often better than a total of eight state-of-the-art methods in terms of task-specific performance measures. in addition, mass estimation has constant time and space complexities.
unsupervised transfer classification: application to text categorization. we study the problem of building the classification model for a target class in the absence of any labeled training example for that class. to address this difficult learning problem, we extend the idea of transfer learning by assuming that the following side information is available: (i) a collection of labeled examples belonging to other classes in the problem domain, called the auxiliary classes; (ii) the class information including the prior of the target class and the correlation between the target class and the auxiliary classes. our goal is to construct the classification model for the target class by leveraging the above data and information. we refer to this learning problem as unsupervised transfer classification. our framework is based on the generalized maximum entropy model that is effective in transferring the label information of the auxiliary classes to the target class. a theoretical analysis shows that under certain assumption, the classification model obtained by the proposed approach converges to the optimal model when it is learned from the labeled examples for the target class. empirical study on text categorization over four different data sets verifies the effectiveness of the proposed approach.
parallel simrank computation on large graphs with iterative aggregation. 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 in a graph. simrank is a simple and influential measure of this kind, based on a solid graph theoretical model. however, existing methods on simrank computation suffer from two limitations: 1) the computing cost can be very high in practice; and 2) they can only be applied on static graphs. in this paper, we exploit the inherent parallelism and high memory bandwidth of graphics processing units (gpu) to accelerate the computation of simrank on large graphs. furthermore, based on the observation that simrank is essentially a first-order markov chain, we propose to utilize the iterative aggregation techniques for uncoupling markov chains to compute simrank scores in parallel for large graphs. the iterative aggregation method can be applied on dynamic graphs. moreover, it can handle not only the link-updating problem but also the node-updating problem. extensive experiments on synthetic and real data sets verify that the proposed methods are efficient and effective.
detecting abnormal coupled sequences and sequence changes in group-based manipulative trading behaviors. in capital market surveillance, an emerging trend is that a group of hidden manipulators collaborate with each other to manipulate three trading sequences: buy-orders, sell-orders and trades, through carefully arranging their prices, volumes and time, in order to mislead other investors, affect the instrument movement, and thus maximize personal benefits. if the focus is on only one of the above three sequences in attempting to analyze such hidden group based behavior, or if they are merged into one sequence as per an investor, the coupling relationships among them indicated through trading actions and their prices/volumes/times would be missing, and the resulting findings would have a high probability of mismatching the genuine fact in business. therefore, typical sequence analysis approaches, which mainly identify patterns on a single sequence, cannot be used here. this paper addresses a novel topic, namely coupled behavior analysis in hidden groups. in particular, we propose a coupled hidden markov models (hmm)-based approach to detect abnormal group-based trading behaviors. the resulting models cater for (1) multiple sequences from a group of people, (2) interactions among them, (3) sequence item properties, and (4) significant change among coupled sequences. we demonstrate our approach in detecting abnormal manipulative trading behaviors on orderbook-level stock data. the results are evaluated against alerts generated by the exchange's surveillance system from both technical and computational perspectives. it shows that the proposed coupled and adaptive hmms outperform a standard hmm only modeling any single sequence, or the hmm combining multiple single sequences, without considering the coupling relationship. further work on coupled behavior analysis, including coupled sequence/event analysis, hidden group analysis and behavior dynamics are very critical.
mining top-k frequent items in a data stream with flexible sliding windows. we study the problem of finding the k most frequent items in a stream of items for the recently proposed max-frequency measure. based on the properties of an item, the max-frequency of an item is counted over a sliding window of which the length changes dynamically. besides being parameterless, this way of measuring the support of items was shown to have the advantage of a faster detection of bursts in a stream, especially if the set of items is heterogeneous. the algorithm that was proposed for maintaining all frequent items, however, scales poorly when the number of items becomes large. therefore, in this paper we propose, instead of reporting all frequent items, to only mine the top-k most frequent ones. first we prove that in order to solve this problem exactly, we still need a prohibitive amount of memory (at least linear in the number of items). yet, under some reasonable conditions, we show both theoretically and empirically that a memory-efficient algorithm exists. a prototype of this algorithm is implemented and we present its performance w.r.t. memory-efficiency on real-life data and in controlled experiments with synthetic data.