waashk/dblp huggingface dataset:
algorithms for large, sparse network alignment problems. we propose a new distributed algorithm for sparse variants of the network alignment problem, which occurs in a variety of data mining areas including systems biology, database matching, and computer vision. our algorithm uses a belief propagation heuristic and provides near optimal solutions for this np-hard combinatorial optimization problem. we show that our algorithm is faster and outperforms or ties existing algorithms on synthetic problems, a problem in bioinformatics, and a problem in ontology matching. we also provide a unified framework for studying and comparing all network alignment solvers.
a linear-time graph kernel. the design of a good kernel is fundamental for knowledge discovery from graph-structured data. existing graph kernels exploit only limited information about the graph structures but are still computationally expensive. we propose a novel graph kernel based on the structural characteristics of graphs. the key is to represent node labels as binary arrays and characterize each node using logical operations on the label set of the connected nodes. our kernel has a linear time complexity with respect to the number of nodes times the average number of neighboring nodes in the given graphs. the experimental result shows that the proposed kernel performs comparable and much faster than a state-of-the-art graph kernel for benchmark data sets and shows high scalability for new applications with large graphs.
efficient algorithm for computing link-based similarity in real world networks. similarity calculation has many applications, such as information retrieval, and collaborative filtering, among many others. it has been shown that link-based similarity measure, such as simrank, is very effective in characterizing the object similarities in networks, such as the web, by exploiting the object-to-object relationship. unfortunately, it is prohibitively expensive to compute the link-based similarity in a relatively large graph. in this paper, based on the observation that link-based similarity scores of real world graphs follow the power-law distribution, we propose a new approximate algorithm, namely power-simrank, with guaranteed error bound to efficiently compute link-based similarity measure. we also prove the convergence of the proposed algorithm. extensive experiments conducted on real world datasets and synthetic datasets show that the proposed algorithm outperforms simrank by four-five times in terms of efficiency while the error generated by the approximation is small.
a cost-effective lsh filter for fast pairwise mining. the pairwise mining problem is to discover pairwise objects having measures greater than the user-specified minimum threshold from a collection of objects. it is essential in a large variety of database and data-mining applications. of late, there has been increasing interest in applying a locality-sensitive hashing (lsh) scheme for pairwise mining. lsh-type methods have shown themselves to be simply implementable and capable of achieving significant performance gain in running time over most exact methods. however, the present lsh-type methods still suffer from some bottlenecks, such as ”the curse of threshold”. in this paper, we proposed a novel lshbased method, namely cost-effective lsh filter (ce-lsh for short), for pairwise mining. compared with previous lsh-type methods, it uses a lower fixed number of lsh functions and is thus more cost-effective. substantial experiments evidence that our method gives significant improvement in running time over existing lsh-type methods and some recently reported method based on upper-bound. experimental results also indicate that it scales well even for a relatively low minimum threshold and for a fairly small miss ratio.
spatio-temporal energy based gait recognition. recently there has been lot of interest in using the gait energy image (gei) of human walk sequence for individual recognition. researchers have reported very good recognition rates using both unsupervised and supervised methods for normal walk sequences. however, the performance degrades when there is a variant like change in clothing or carrying a bag. this paper shows that the performance for the variant situations can be improved by constructing the gei with sway alignment instead of upper body alignment, and dynamically selecting just the required number of rows from the bottom of the silhouette as inputs for an unsupervised feature selection approach. the improvement in recognition rates are established with performance testing on a large gait dataset.
active selection of sensor sites in remote sensing applications. in a data-mining approach, a model for estimation of aerosol optical depth (aod) from satellite observations is learned using collocated satellite and ground-based observations. for accurate learning of such a spatio-temporal model, it is important to collect ground-based data from a large number of sites. the objective of this project is to determine appropriate locations for the next set of ground-based data collection sites to maximize accuracy of aod estimation. ideally, a new site should capture the most significant unseen aerosol patterns and should be the least correlated with the previously observed patterns. we propose achieving this aim by selecting the locations on which the existing prediction model is the most uncertain. several criteria were considered for site selection, including uncertainty, spatial diversity, similarity in temporal pattern, and their combination. extensive experiments on globally distributed data over 90 aeronet sites from the years 2005 and 2006 provide strong evidence that sites selected using the proposed algorithms improve the overall aod prediction accuracy at a faster rate than those selected randomly or based on spatial diversity among sites.
finding associations and computing similarity via biased pair sampling. sampling-based methods have previously been proposed for the problem of finding interesting associations in data, even for low-support items. while these methods do not guarantee precise results, they can be vastly more efficient than approaches that rely on exact counting. however, for many similarity measures no such methods have been known. in this paper we show how a wide variety of measures can be supported by a simple biased sampling method. the method also extends to find high-confidence association rules. we demonstrate theoretically that our method is superior to exact methods when the threshold for "interesting similarity/confidence" is above the average pairwise similarity/confidence, and the average support is not too low. our method is particularly good when transactions contain many items. we confirm in experiments on standard association mining benchmarks that this gives a significant speedup on real data sets (sometimes much larger than the theoretical guarantees). reductions in computation time of over an order of magnitude, and significant savings in space, are observed.
filtering and refinement: a two-stage approach for efficient and effective anomaly detection. anomaly detection is an important data mining task. most existing methods treat anomalies as inconsistencies and spend the majority amount of time on modeling normal instances. a recently proposed, sampling-based approach may substantially boost the efficiency in anomaly detection but may also lead to weaker accuracy and robustness. in this study, we propose a two-stage approach to find anomalies in complex datasets with high accuracy as well as low time complexity and space cost. instead of analyzing normal instances, our algorithm first employs an efficient deterministic space partition algorithm to eliminate obvious normal instances and generates a small set of anomaly candidates with a single scan of the dataset. it then checks each candidate with density-based multiple criteria to determine the final results. this two-stage framework also detects anomalies of different notions. our experiments show that this new approach finds anomalies successfully in different conditions and ensures a good balance of efficiency, accuracy, and robustness.
online system problem detection by mining patterns of console logs. we describe a novel application of using data mining and statistical learning methods to automatically monitor and detect abnormal execution traces from console logs in an online setting. different from existing solutions, we use a two stage detection system. the first stage uses frequent pattern mining and distribution estimation techniques to capture the dominant patterns (both frequent sequences and time duration). the second stage use principal component analysis based anomaly detection technique to identify actual problems. using real system data from a 203-node hadoop [1] cluster, we show that we can not only achieve highly accurate and fast problem detection, but also help operators better understand execution patterns in their system.
hierarchical probabilistic segmentation of discrete events. segmentation, the task of splitting a long sequence of discrete symbols into chunks, can provide important information about the nature of the sequence that is understandable to humans. algorithms for segmenting mostly belong to the supervised learning family, where a labeled corpus is available to the algorithm in the learning phase. we are interested, however, in the unsupervised scenario, where the algorithm never sees examples of successful segmentation, but still needs to discover meaningful segments. in this paper we present an unsupervised learning algorithm for segmenting sequences of symbols or categorical events. our algorithm, hierarchical multigram, hierarchically builds a lexicon of segments and computes a maximum likelihood segmentation given the current lexicon. thus, our algorithm is most appropriate to hierarchical sequences, where smaller segments are grouped into larger segments. our probabilistic approach also allows us to suggest conditional entropy as a measurement of the quality of a segmentation in the absence of labeled data. we compare our algorithm to two previous approaches from the unsupervised segmentation literature, showing it to provide superior segmentation over a number of benchmarks. we also compare our algorithm to previous approaches over a segmentation of the unlabeled interactions of a web service and its client.
unified solution to nonnegative data factorization problems. in this paper, we restudy the non-convex data factorization problems (regularized or not, unsupervised or supervised), where the optimization is confined in the \emph{nonnegative} orthant, and provide a \emph{unified} convergency provable solution based on multiplicative nonnegative update rules. this solution is general for optimization problems with block-wisely quadratic objective functions, and thus direct update rules can be derived by skipping over the tedious specific procedure deduction process and algorithmic convergence proof. by taking this unified solution as a general template, we i) re-explain several existing nonnegative data factorization algorithms, ii) develop a variant of nonnegative matrix factorization formulation for handling out-of-sample data, and iii) propose a new nonnegative data factorization algorithm, called correlated co-decomposition (ccd), to simultaneously factorize two feature spaces by exploring the inter-correlated information. experiments on both face recognition and multi-label image annotation tasks demonstrate the wide applicability of the unified solution as well as the effectiveness of two proposed new algorithms.
grape: a graph-based framework for disambiguating people appearances in web search. finding information about people using search engines is one of the most common activities on the web. however, search engines usually return a long list of web pages, which may be relevant to many namesakes, especially given the explosive growth of web data. to address the challenge caused by name ambiguity in web people search, this paper proposes a novel graph-based framework, grape (abbr. a graph-based framework for disambiguating people appearances in web search). in grape, people tag information (e.g., people name, organization, and email address) surrounding the queried people name is extracted from the search results, a graph-based unsupervised algorithm is then developed to cluster the extracted tags, where a new method, cohesion, is introduced to measure the importance of a tag for clustering, and each final cluster of tags represents a unique people entity. experimental results show that our proposed framework outperforms the state-of-the-art web people name disambiguation approaches.
inverse time dependency in convex regularized learning. in the conventional regularized learning, training time increases as the training set expands. recent work on l2 linear svm challenges this common sense by proposing the inverse time dependency on the training set size. in this paper, we first put forward a primal gradient solver (pgs) to effectively solve the convex regularized learning problem. this solver is based on the stochastic gradient descent method and the fenchel conjugate adjustment, employing the well-known online strongly convex optimization algorithm with logarithmic regret. we then theoretically prove the inverse dependency property of our pgs, embracing the previous work of the l2 linear svm as a special case and enable the l_p-norm optimization to run within a bounded sphere, which qualifies more convex loss functions in pgs. we further illustrate this solver in three examples: svm, logistic regression and regularized least square. experimental results substantiate the property of the inverse dependency on training data size.
learning local components to understand large bayesian networks. bayesian networks are known for providing an intuitive and compact representation of probabilistic information and allowing the creation of models over a large and complex domain. bayesian learning and reasoning are nontrivial for a large bayesian network. in parallel, it is a tough job for users (domain experts) to extract accurate information from a large bayesian network due to dimensional difficulty. we define a formulation of local components and propose a clustering algorithm to learn such local components given complete data. the algorithm groups together most inter-relevant attributes in a domain. we evaluate its performance on three benchmark bayesian networks and provide results in support. we further show that the learned components may represent local knowledge more precisely in comparison to the full bayesian networks when working with a small amount of data.
least square incremental linear discriminant analysis. linear discriminant analysis (lda) is a well-known dimension reduction approach, which projects high-dimensional data into a low-dimensional space with the best separation of different classes. in many tasks, the data accumulates over time, and thus incremental lda is more desirable than batch lda. several incremental lda algorithms have been developed and achieved success; however, the eigen-problem involved requires a large computation cost, which hampers the efficiency of these algorithms. in this paper, we propose a new incremental lda algorithm, ls-ilda, based on the least square solution of lda. when new samples are received, ls-ilda incrementally updates the least square solution of lda. our analysis discloses that this algorithm produces the exact least square solution of batch lda, while its computational cost is o(min(n; d) £ d) for one update on dataset containing n instances in d-dimensional space. experimental results show that comparing with state-of-the-art incremental lda algorithms, our proposed ls-ilda achieves high accuracy with low time cost.
resolving identity uncertainty with learned random walks. a pervasive problem in large relational databases is identity uncertainty which occurs when multiple entries in a database refer to the same underlying entity in the world. relational databases exhibit rich graphical structure and are naturally modeled as graphs whose nodes represent entities and whose typed-edges represent relations between them. we propose using random walk models for resolving identity uncertainty since they have proven effective for finding points which are proximately located in a network. because not all types of relations are equally helpful in alleviating identity uncertainty, we develop a supervised approach to learning the usefulness of different database relations from a training set of database entries whose true identities are known. when tested on the task of resolving uncertainty of ambiguously named authors in bibliographical data, the learned random walk models yield performance superior to support vector machines, and to a related spectral clustering method.
binomial matrix factorization for discrete collaborative filtering. matrix factorization (mf) models have proved efficient and well scalable for collaborative filtering (cf) problems. many researchers also present the probabilistic interpretation of mf. they usually assume that the factor vectors of users and items are from normal distributions, and so are the ratings when the user and item factors are given. then they can derive the exact mf algorithm by finding a map estimate of the model parameters. in this paper we suggest a new probabilistic perspective on mf for discrete cf problems. we assume that all ratings are from binomial distributions with different preference parameters instead of the original normal distributions. the new interpretation is more reasonable for discrete cf problems since they only allow several legal discrete rating values. we also present two effective algorithms to learn the new model and make predictions. they are applied to the netflix prize data set and acquire considerably better accuracy than those of mf.
an l-infinity norm visual classifier. we introduce a mathematical framework, based on the l-infinity norm distance metric, to describe human interactions in a visual data mining environment. we use the framework to build a classifier that involves an algebra on hyper-rectangles. our classifier, called visclassifier, generates set-wise rules from simple gestures in an exploratory visual gui. logging these rules allows us to apply our analysis to a new sample or batch of data so that we can assess the predictive power of our visual-processing motivated classifier. the accuracy of this classifier on widely-used benchmark datasets rivals the accuracy of competitive classifiers.
relevant subspace clustering: mining the most interesting non-redundant concepts in high dimensional data. subspace clustering aims at detecting clusters in any subspace projection of a high dimensional space. as the number of possible subspace projections is exponential in the number of dimensions, the result is often tremendously large. recent approaches fail to reduce results to relevant subspace clusters. their results are typically highly redundant, i.e. many clusters are detected multiple times in several projections. in this work, we propose a novel model for relevant subspace clustering (rescu). we present a global optimization which detects the most interesting non-redundant subspace clusters. we prove that computation of this model is np-hard. for rescu, we propose an approximative solution that shows high accuracy with respect to our relevance model. thorough experiments on synthetic and real world data show that rescu successfully reduces the result to manageable sizes. it reliably achieves top clustering quality while competing approaches show greatly varying performance.
parallel pathfinder algorithms for mining structures from graphs. pathfinder networks are increasingly used in data mining for different purposes, like network visualization or knowledge extraction. this novel way of representing graphical data has been proven to give better results than other link reduction algorithms, like minimum spanning networks however, this increase in quality comes with a high computation cost, typically of the order of n^3 or higher, where n is the number of nodes in the graph. while this problem has previously been tackled by using mathematical properties to speed up the algorithm, in this paper, we propose two new algorithms to speed up pathfinder computation based on parallelization techniques to take advantage of the increasingly available multi-core hardware platform. experiments show that both new algorithms are more efficient than the state of the art algorithms; one of them can achieve speed-ups of up to x127 with an average of x23 on recent hardware (2007).
two heads better than one: metric+active learning and its applications for it service classification. large it service providers track service requests and their execution through problem/change tickets. it is important to classify the tickets based on the problem/change description in order to understand service quality and to optimize service processes. however, two challenges exist in solving this classification problem: 1) ticket descriptions from different classes are of highly diverse characteristics, which invalidates most standard distance metrics; 2) it is very expensive to obtain high-quality labeled data. to address these challenges, we develop two seemingly independent methods 1) discriminative neighborhood metric learning (dnml) and 2) active learning with median selection (alms), both of which are, however, based on the same core technique: iterated representative selection. a case study on real it service classification application is presented to demonstrate the effectiveness and efficiency of our proposed methods.
probabilistic similarity query on dimension incomplete data. retrieving similar data has drawn many research efforts in the literature due to its importance in data mining, database and information retrieval. this problem is challenging when the data is incomplete. in previous research, data incompleteness refers to the fact that data values for some dimensions are unknown. however, in many practical applications (e.g., data collection by sensor network under bad environment), not only data values but even data dimension information may also be missing, which will make most similarity query algorithms infeasible. in this work, we propose the novel similarity query problem on dimension incomplete data and adopt a probabilistic framework to model this problem. for this problem, users can give a distance threshold and a probability threshold to specify their retrieval requirements. the distance threshold is used to specify the allowed distance between query and data objects and the probability threshold is used to require that the retrieval results satisfy the distance condition at least with the given probability. instead of enumerating all possible cases to recover the missed dimensions, we propose an efficient approach to speed up the retrieval process by leveraging the inherent relations between query and dimension incomplete data objects. during the query process, we estimate the lower/upper bounds of the probability that the query is satisfied by a given data object, and utilize these bounds to filter irrelevant data objects efficiently. furthermore, a probability triangle inequality is proposed to further speed up query processing. according to our experiments on real data sets, the proposed similarity query method is verified to be effective and efficient on dimension incomplete data.