waashk/dblp huggingface dataset:
slider: mining correlated motifs in protein-protein interaction networks. correlated motif mining (cmm) is the problem to find overrepresented pairs of patterns, called motif pairs, in interacting protein sequences. algorithmic solutions for cmm thereby provide a computational method for predicting binding sites for protein interaction. in this paper, we adopt a motif-driven approach where the support of candidate motif pairs is evaluated in the network. we experimentally establish the superiority of the chi-square-based support measure over other support measures. furthermore, we obtain that cmm is an np-hard problem for a large class of support measures (including chi-square) and reformulate the search for correlated motifs as a combinatorial optimization problem. we then present the method slider which uses local search with a neighborhood function based on sliding motifs and employs the chi-square-based support measure. we show that slider outperforms existing motif-driven cmm methods and scales to large protein-protein interaction networks.
ring: an integrated method for frequent representative subgraph mining. we propose a novel representative based subgraph mining model. a series of standards and methods are proposed to select invariants. patterns are mapped into invariant vectors in a multidimensional space. to find qualified patterns, only a subset of frequent patterns is generated as representatives, such that every frequent pattern is close to one of the representative patterns while representative patterns are distant from each other. we devise the ring algorithm, integrating the representative selection into the pattern mining process. meanwhile, we use r-trees to assist this mining process. last but not least, a large number of real and synthetic datasets are employed for the empirical study, which show the benefits of the representative model and the efficiency of the ring algorithm.
extended boolean matrix decomposition. with the vast increase in collection and storage of data, the problem of data summarization is most critical for effective data management. since much of this data is categorical in nature, it can be viewed in terms of a boolean matrix. boolean matrix decomposition (bmd) has been used to provide concise and interpretable representations of boolean data sets. a boolean matrix can be expressed as a product of two boolean matrices, where the first matrix represents a set of meaningful concepts, and the second describes how the observed data can be expressed as combinations of those concepts. typically, the combination is only in terms of the set union. in other words, a successful boolean matrix decomposition gives a set of concepts and shows how every column of the input data can be expressed as a union of some subset of those concepts. however, this way of modeling only incompletely represents real data semantics. essentially, it ignores a critical component -- the set difference operation: a column can be expressed as the combination of union of certain concepts as well as the exclusion of other concepts. this has two significant benefits. first, the total number of concepts required to describe the data may itself be reduced. second, a more succinct summarization may be found for every column. in this paper, we propose the extended boolean matrix decomposition (ebmd) problem, which aims to factor boolean matrices using both the set union and set difference operations. we study several variants of the problem, show that they are np-hard, and propose efficient heuristics to solve them. extensive experimental results demonstrate the power of ebmd.
stacked gaussian process learning. triggered by a market relevant application that involves making joint predictions of pedestrian and public transit flows in urban areas, we address the question of how to utilize hidden common cause relations among variables of interest in order to improve performance in the two related regression tasks. specifically, we propose stacked gaussian process learning, a meta-learning scheme in which a base gaussian process is enhanced by adding the posterior covariance functions of other related tasks to its covariance function in a stage-wise optimization. the idea is that the stacked posterior covariances encode the hidden common causes among variables of interest that are shared across the related regression tasks. stacked gaussian process learning is efficient, capable of capturing shared common causes, and can be implemented with any kind of standard gaussian process regression model such as sparse approximations and relational variants. our experimental results on real-world data from the market relevant application show that stacked gaussian processes learning can significantly improve prediction performance of a standard gaussian process.
permutation tests for studying classifier performance. we explore the framework of permutation-based p-values for assessing the behavior of the classification error. in this paper we study two simple permutation tests. the first test estimates the null distribution by permuting the labels in the data; this has been used extensively in classification problems in computational biology. the second test produces permutations of the features within classes, inspired by restricted randomization techniques traditionally used in statistics. we study the properties of these tests and present an extensive empirical evaluation on real and synthetic data. our analysis shows that studying the classification error via permutation tests is effective; in particular, the restricted permutation test clearly reveals whether the classifier exploits the interdependency between the features in the data.
on k-means cluster preservation using quantization schemes. this work examines under what conditions compression methodologies can retain the outcome of clustering operations. we focus on the popular k-means clustering algorithm and we demonstrate how a properly constructed compression scheme based on post-clustering quantization is capable of maintaining the global cluster structure. our analytical derivations indicate that a 1-bit moment preserving quantizer per cluster is sufficient to retain the original data clusters. merits of the proposed compression technique include: a) reduced storage requirements with clustering guarantees, b) data privacy on the original values, and c) shape preservation for data visualization purposes. we evaluate quantization scheme on various high-dimensional datasets, including 1-dimensional and 2-dimensional time-series (shape datasets) and demonstrate the cluster preservation property. we also compare with previously proposed simplification techniques in the time-series area and show significant improvements both on the clustering and shape preservation of the compressed datasets.
redistricting using heuristic-based polygonal clustering. redistricting is the process of dividing a geographic area into districts or zones. this process has been considered in the past as a problem that is computationally too complex for an automated system to be developed that can produce unbiased plans. in this paper we present a novel method for redistricting a geographic area using a heuristic-based approach for polygonal spatial clustering. while clustering geospatial polygons several complex issues need to be addressed – such as: removing order dependency, clustering all polygons assuming no outliers, and strategically utilizing domain knowledge to guide the clustering process. in order to address these special needs, we have developed the constrained polygonal spatial clustering (cpsc) algorithm that holistically integrates do-main knowledge in the form of cluster-level and instance-level constraints and uses heuristic functions to grow clusters. in order to illustrate the usefulness of our algorithm we have applied it to the problem of formation of unbiased congressional districts. furthermore, we compare and contrast our algorithm with two other approaches proposed in the literature for redistricting, namely – graph partitioning and simulated annealing.
non-sparse multiple kernel learning for fisher discriminant analysis. we consider the problem of learning a linear combination of pre-specified kernel matrices in the fisher discriminant analysis setting. existing methods for such a task impose an $\ell_1$ norm regularisation on the kernel weights, which produces sparse solution but may lead to loss of information. in this paper, we propose to use $\ell_2$ norm regularisation instead. the resulting learning problem is formulated as a semi-infinite program and can be solved efficiently. through experiments on both synthetic data and a very challenging object recognition benchmark, the relative advantages of the proposed method and its $\ell_1$ counterpart are demonstrated, and insights are gained as to how the choice of regularisation norm should be made.
learning the shared subspace for multi-task clustering and transductive transfer classification. there are many clustering tasks which are closely related in the real world, e.g. clustering the web pages of different universities. however, existing clustering approaches neglect the underlying relation and treat these clustering tasks either individually or simply together. in this paper, we will study a novel clustering paradigm, namely multi-task clustering, which performs multiple related clustering tasks together and utilizes the relation of these tasks to enhance the clustering performance. we aim to learn a subspace shared by all the tasks, through which the knowledge of the tasks can be transferred to each other. the objective of our approach consists of two parts: (1) within-task clustering: clustering the data of each task in its input space individually; and (2) cross-task clustering: simultaneous learning the shared subspace and clustering the data of all the tasks together. we will show that it can be solved by alternating minimization, and its convergence is theoretically guaranteed. furthermore, we will show that given the labels of one task, our multi-task clustering method can be extended to transductive transfer classification (a.k.a. cross-domain classification, domain adaption). experiments on several cross-domain text data sets demonstrate that the proposed multi-task clustering outperforms traditional single-task clustering methods greatly. and the transductive transfer classification method is comparable to or even better than several existing transductive transfer classification approaches.
large scale relation acquisition using class dependent patterns. this paper proposes a minimally supervised method for acquiring high-level semantic relations such as causality and prevention from the web. our method learns linguistic patterns that express causality such as “x gave rise to y”, and uses them to extract causal noun pairs like (global warming, malaria epidemic) from sentences like “global warming gave rise to a new malaria epidemic”. the novelty of our method lies in the use of semantic word classes acquired by large scale clustering for learning class dependent patterns. we demonstrate the effectiveness of this class based approach on three large-scale relation mining tasks from 50 million japanese web pages. in two of these tasks we obtained more than 30,000 relation instances with over 80% precision, outperforming a state-of-the-art system by a large margin.
global slope change synopses for measurement maps. quality control using scalar quality measures is standard practice in manufacturing. however, there are also quality measures that are determined at a large number of positions on a product, since the spatial distribution is important. we denote such a mapping of local coordinates on the product to values of a measure as a measurement map. in this paper, we examine how measurement maps can be clustered according to a novel notion of similarity—mapscape similarity—that considers the overall course of the measure on the map. we present a class of synopses called global slope change that uses the profile of the measure along several lines from a reference point to different points on the borders to represent a measurement map. we conduct an evaluation of global slope change using a real-world data set from manufacturing and demonstrate its superiority over other synopses.
maximum margin clustering on data manifolds. clustering is one of the most fundamental and important problems in computer vision and pattern recognition communities. maximum margin clustering(mmc) is a recently proposed clustering technique which has shown promising experimental results. the main theme behind mmc is to extend the standard maximum margin principle in support vector machine (svm) to the unsupervised scenario. this paper will consider the problem of maximum margin clustering on data manifolds. specifically, we propose an approach called manifold regularized maximum margin clustering (mrmmc) which combines both the maximum margin data discrimination and data manifold information in a unified clustering objective and propose an efficient algorithm to solve it. finally the experimental results on several real world data sets are presented to show the effectiveness of our method.
clustering with multiple graphs. in graph-based learning models, entities are often represented as vertices in an undirected graph with weighted edges describing the relationships between entities. in many real-world applications, however, entities are often associated with relations of different types and/or from different sources, which can be well captured by multiple undirected graphs over the same set of vertices. how to exploit such multiple sources of information to make better inferences on entities remains an interesting open problem. in this paper, we focus on the problem of clustering the vertices based on multiple graphs in both unsupervised and semi-supervised settings. as one of our contributions, we propose linked matrix factorization (lmf) as a novel way of fusing information from multiple graph sources. in lmf, each graph is approximated by matrix factorization with a graph-specific factor and a factor common to all graphs, where the common factor provides features for all vertices. experiments on siam journal data show that (1) we can improve the clustering accuracy through fusing multiple sources of information with several models, and (2) lmf yields superior or competitive results compared to other graph-based clustering methods.
fast online training of ramp loss support vector machines. a fast online algorithm onlinesvmr for training ramp-loss support vector machines (svmrs) is proposed. it finds the optimal svmr for t+1 training examples using svmr built on t previous examples. the algorithm retains the karush–kuhn–tucker conditions on all previously observed examples. this is achieved by an smo-style incremental learning and decremental unlearning under the concave-convex procedure framework. further speedup of training time could be achieved by dropping the requirement of optimality. a variant, called onlineasvmr, is a greedy approach that approximately optimizes the svmr objective function and is suitable for online active learning. the proposed algorithms were comprehensively evaluated on 9 large benchmark data sets. the results demonstrate that onlinesvmr (1) has the similar computational cost as its offline counterpart; (2) outperforms idsvm, its competing online algorithm that uses hinge-loss, in terms of accuracy, model sparsity and training time. the experiments on online active learning show that for a fixed number of label queries onlineasvmr (1) achieves consistently better accuracy than queryall and competitive accuracy to greedy approach; (2) outperforms the active learning version of idsvm.
finding time series motifs in disk-resident data. time series motifs are sets of very similar subsequences of a long time series. they are of interest in their own right, and are also used as inputs in several higher-level data mining algorithms including classification, clustering, rule-discovery and summarization. in spite of extensive research in recent years, finding exact time series motifs in massive databases is an open problem. previous efforts either found approximate motifs or considered relatively small datasets residing in main memory. in this work, we describe for the first time a disk-aware algorithm to find exact time series motifs in multi-gigabyte databases which contain on the order of tens of millions of time series. we have evaluated our algorithm on datasets from diverse areas including medicine, anthropology, computer networking and image processing and show that we can find interesting and meaningful motifs in datasets that are many orders of magnitude larger than anything considered before.
a fully automated method for discovering community structures in high dimensional data. identifying modules, or natural communities, in large complex networks is fundamental in many fields, including social sciences, biological sciences and engineering. recently several methods have been developed to automatically identify communities from complex networks by optimizing the modularity function. the advantage of this type of approaches is that the algorithm does not require any parameter to be tuned. however, the modularity-based methods for community discovery assume that the network structure is given explicitly and is correct. in addition, these methods work best if the network is unweighted and/or sparse. in reality, networks are often not directly defined, or may be given as an affinity matrix. in the first case, each node of the network is defined as a point in a high dimensional space and different networks can be obtained with different network construction methods, resulting in different community structures. in the second case, an affinity matrix may define a dense weighted graph, for which modularity-based methods do not perform well. in this work, we propose a very simple algorithm to automatically identify community structures from these two types of data. our approach utilizes a k-nearest-neighbor network construction method to capture the topology embedded in high dimensional data, and applies a modularity-based algorithm to identify the optimal community structure. a key to our approach is that the network construction is incorporated with the community identification process and is totally parameter-free. furthermore, our method can suggest appropriate pre-processing / normalization of the data to improve the results of community identification. we tested our methods on several synthetic and real data sets, and evaluated its performance by internal or external accuracy indices. compared with several existing approaches, our method is not only fully automatic, but also has the best accuracy overall.
a contrast pattern based clustering quality index for categorical data. since clustering is unsupervised and highly explorative, clustering validation (i.e. assessing the quality of clustering solutions) has been an important and long standing research problem. existing validity measures have significant shortcomings. this paper proposes a novel contrast pattern based clustering quality index (cpcq) for categorical data, by utilizing the quality and diversity of the contrast patterns (cps) which contrast the clusters in clusterings. high quality cps can characterize clusters and discriminate them against each other. experiments show that the cpcq index (1) can recognize that expert-determined classes are the best clusters for many datasets from the uci repository; (2) does not give inappropriate preference to larger number of clusters; (3) does not require a user to provide a distance function.
discovering contexts and contextual outliers using random walks in graphs. the identifying of contextual outliers allows the discovery of anomalous behavior that other forms of outlier detection cannot find. what may appear to be normal behavior with respect to the entire data set can be shown to be anomalous by subsetting the data according to specific spatial or temporal context. however, in many real-world applications, we may not have sufficient a priori contextual information to discover these contextual outliers. this paper addresses the problem by proposing a probabilistic approach based on random walks, which can simultaneously explore meaningful contexts and score contextual outliers therein. our approach has several advantages including producing outlier scores which can be interpreted as stationary expectations and their calculation in closed form in polynomial time. in addition, we show that point outlier detection using the stationary distribution is a special case of our approach. it allows us to find both global and contextual outliers simultaneously and to create a meaningful ranked list consisting of both types of outliers. this is a major departure from existing work where an algorithm typically identifies one type of outlier. the effectiveness of our method is justified by empirical results on real data sets, with comparison to related work.
extracting output metadata from scientific deep web data sources. increasingly, many data sources appear as online databases, hidden behind query forms, thus forming the deep web. the popularity of this new medium for data dissemination is leading to new problems in data integration. particularly, to enable data integration from multiple deep web data sources, one needs to obtain the metadata for each of the data sources. obtaining the metadata, particularly, the output schema, can be very challenging. this is because, given an input query, many deep web data sources only return a subset of the output schema attributes, i.e, the ones that have a non-null value for the corresponding input. in this paper, we propose two approaches, which are the sampling model approach and the mixture model approach, respectively, to efficiently obtain an approximately complete set of output schema attributes from a deep web data source. our experiments show while each of the above two approaches has limitations, a hybrid strategy, where we combine the two approaches, achieves high recall with good precision for most data sources.
connecting sparsely distributed similar bloggers. the nature of the blogosphere determines that the majority of bloggers are only connected with a small number of fellow bloggers, and similar bloggers can be largely disconnected from each other. aggregating them allows for cost-effective personalized services, targeted marketing, and exploration of new business opportunities. as most bloggers have only a small number of adjacent bloggers, the problem of aggregating similar bloggers presents challenges that demand novel algorithms of connecting the non-adjacent due to the fragmented distributions of bloggers. in this work, we define the problem, delineate its challenges, and present an approach that uses innovative ways to employ contextual information and collective wisdom to aggregate similar bloggers. a real-world blog directory is used for experiments. we demonstrate the efficacy of our approach, report findings, and discuss related issues and future work.