waashk/dblp huggingface dataset:
constraint-based pattern mining in dynamic graphs. dynamic graphs are used to represent relationships between entities that evolve over time. meaningful patterns in such structured data must capture strong interactions and their evolution over time. in social networks, such patterns can be seen as dynamic community structures, i.e., sets of individuals who strongly and repeatedly interact. in this paper, we propose a constraint-based mining approach to uncover evolving patterns. we propose to mine dense and isolated subgraphs defined by two user-parameterized constraints. the temporal evolution of such patterns is captured by associating a temporal event type to each identified subgraph. we consider five basic temporal events: the formation, dissolution, growth, diminution and stability of subgraphs from one time stamp to the next. we propose an algorithm that finds such subgraphs in a time series of graphs processed incrementally. the extraction is feasible due to efficient patterns and data pruning strategies. we demonstrate the applicability of our method on several real-world dynamic graphs and extract meaningful evolving communities.
rule ensembles for multi-target regression. methods for learning decision rules are being successfully applied to many problem domains, especially where understanding and interpretation of the learned model is necessary. in many real life problems, we would like to predict multiple related (nominal or numeric) target attributes simultaneously. methods for learning rules that predict multiple targets at once already exist, but are unfortunately based on the covering algorithm, which is not very well suited for regression problems. a better solution for regression problems may be a rule ensemble approach that transcribes an ensemble of decision trees into a large collection of rules. an optimization procedure is then used for selecting the best (and much smaller) subset of these rules, and to determine their weights. using the rule ensembles approach we have developed a new system for learning rule ensembles for multi-target regression problems. the newly developed method was extensively evaluated and the results show that the accuracy of multi-target regression rule ensembles is better than the accuracy of multi-target regression trees, but somewhat worse than the accuracy of multi-target random forests. the rules are significantly more concise than random forests, and it is also possible to create very small rule sets that are still comparable in accuracy to single regression trees.
semi-naive exploitation of one-dependence estimators. it is well known that the key of bayesian classifier learning is to balance the two important issues, that is, the exploration of attribute dependencies in high orders for ensuring a sufficient flexibility in approximating the ground-truth dependencies, and the exploration of low orders for ensuring a stable probability estimate from limited training samples. by allowing one-order attribute dependencies, one-dependence estimators (odes) have been shown to be able to approximate the ground-truth attribute dependencies whilst keeping the effectiveness of probability estimation, and therefore leading to excellent performance. in previous studies, however, odes were exploited in simple ways, such as by averaging, for classification. in this paper, we propose a semi-naive exploitation of odes that fits a function of odes to pursue higher-order attribute dependencies. extensive experiments show that the proposed snode approach can achieve better performance than many state-of-the-art bayesian classifiers.
trbagg: a simple transfer learning method and its application to personalization in collaborative tagging. the aim of transfer learning is to improve prediction accuracy on a target task by exploiting the training examples for tasks that are related to the target one. transfer learning has received more attention in recent years, because this technique is considered to be helpful in reducing the cost of labeling. in this paper, we propose a very simple approach to transfer learning: trbagg, which is the extension of bagging. trbagg is composed of two stages: many weak classifiers are first generated as in standard bagging, and these classifiers are then filtered based on their usefulness for the target task. this simplicity makes it easy to work reasonably well without severe tuning of learning parameters. further, our algorithm equips an algorithmic scheme to avoid negative transfer. we applied trbagg to personalized tag prediction tasks for social bookmarks our approach has several convenient characteristics for this task such as adaptation to multiple tasks with low computational cost.
an effective approach to inverse frequent set mining. the inverse frequent set mining problem is the problem of computing a database on which a given collection of itemsets must emerge to be frequent. earlier studies focused on investigating computational and approximability properties of this problem. in this paper, we face it under the pragmatic perspective of defining heuristic solution approaches that are effective and scalable in real scenarios. in particular, a general formulation of the problem is considered where minimum and maximum support constraints can be defined on each itemset, and where no bound is given beforehand on the size of the resulting output database. within this setting, an algorithm is proposed that always satisfies the maximum support constraints, but which treats minimum support constraints as soft ones that are enforced as long as possible. a thorough experimentation evidences that minimum support constraints are hardly violated in practice, and that such negligible degradation in accuracy (which is unavoidable due to the theoretical intractability of the problem) is compensated by very good scaling performances.
explore/exploit schemes for web content optimization. we propose novel multi-armed bandit (explore/exploit) schemes to maximize total clicks on a content module published regularly on yahoo! intuitively, one can ``explore'' each candidate item by displaying it to a small fraction of user visits to estimate the item's click-through rate (ctr), and then ``exploit'' high ctr items in order to maximize clicks. while bandit methods that seek to find the optimal trade-off between explore and exploit have been studied for decades, existing solutions are not satisfactory for web content publishing applications where dynamic set of items with short lifetimes, delayed feedback and non-stationary reward (ctr) distributions are typical. in this paper, we develop a bayesian solution and extend several existing schemes to our setting. through extensive evaluation with nine bandit schemes, we show that our bayesian solution is uniformly better in several scenarios. we also study the empirical characteristics of our schemes and provide useful insights on the strengths and weaknesses of each. finally, we validate our results with a ``side-by-side'' comparison of schemes through live experiments conducted on a random sample of real user visits to yahoo!
a tree-based framework for difference summarization. understanding the differences between two datasets is a fundamental data mining question and is also ubiquitously important across many real world scientific applications. in this paper, we propose a tree-based framework to provide a parsimonious explanation of the difference between two distributions based on rigorous two-sample statistical test. we develop two efficient approaches. the first one is a dynamic programming approach that finds a minimal number of data subsets that describe the difference between two data sets. the second one is a greedy approach that approximates the dynamic programming approach. we employ the well-known friedman's mst (minimal spanning tree) statistics for two-sample statistical tests in our summarization tree construction, and develop novel techniques to speedup its computational procedure. we performed a detailed experimental evaluation on both real and synthetic datasets and demonstrated the effectiveness of our tree-summarization approach.
effective criterion functions for efficient agglomerative clustering on very large networks. as the agglomerative clustering algorithm is widely used in data mining, image processing, bioinformatics and pattern recognition. it has attracted great interests from both academical and industrial communities. however, existing studies neglect the decisive factor of the efficiency of the agglomerative clustering algorithm for large complex networks and usually use criterion functions which lead to inefficiency. in this paper, we propose three effective criterion functions for improving performance of agglomerative clustering algorithm. we note that clustering efficiency is determined by two factors: a) the number of neighbors of two merged clusters in each merge step; b) the number of neighbors shared by the two clusters. based on these observations, we propose a framework for designing criterion functions in order to efficiently find clusters in very large networks. we devise three criterion functions that can effectively control the number of neighbors of clusters, and they can efficiently produce high-quality clusters. we have implemented our method and compared with existing studies on real networks, and our method outperforms state-of-the-art approaches significantly on large networks.
itopicmodel: information network-integrated topic modeling. document networks, i.e., networks associated with text information, are becoming increasingly popular due to the ubiquity of web documents, blogs, and various kinds of online data. in this paper, we propose a novel topic modeling framework for document networks, which builds a unified generative topic model that is able to consider both text and structure information for documents. a graphical model is proposed to describe the generative model. on the top layer of this graphical model, we define a novel multivariate markov random field for topic distribution random variables for each document, to model the dependency relationships among documents over the network structure. on the bottom layer, we follow the traditional topic model to model the generation of text for each document. a joint distribution function for both the text and structure of the documents is thus provided. a solution to estimate this topic model is given, by maximizing the log-likelihood of the joint probability. some important practical issues in real applications are also discussed, including how to decide the topic number and how to choose a good network structure. we apply the model on two real datasets, dblp and cora, and the experiments show that this model is more effective in comparison with the state-of-the-art topic modeling algorithms.
feature selection in the tensor product feature space. classifying objects that are sampled jointly from two or more domains has many applications. the tensor product feature space is useful for modeling interactions between feature sets in different domains but feature selection in the tensor product feature space is challenging. conventional feature selection methods ignore the structure of the feature space and may not provide the optimal results. in this paper we propose methods for selecting features in the original feature spaces of different domains. we obtained sparsity through two approaches, one using integer quadratic programming and another using l1-norm regularization. experimental studies on biological data sets validate our approach.
topic distributions over links on web. it is well known that web users create links with different intentions. however, a key question, which is not well studied, is how to categorize the links and how to quantify the strength of the influence of a web page on another if there is a link between the two linked web pages. in this paper, we focus on the problem of link semantics analysis, and propose a novel supervised learning approach to build a model, based on a training link-labeled and link-weighted graph where a link-label represents the category of a link and a link-weight represents the influence of one web page on the other in a link. based on the model built, we categorize links and quantify the influence of web pages on the others in a large graph in the same application domain. we discuss our proposed approach, namely pairwise restricted boltzmann machines (prbms), and conduct extensive experimental studies to demonstrate the effectiveness of our approach using large real datasets.
semi-supervised sequence labeling with self-learned features. typical information extraction (ie) systems can be seen as tasks assigning labels to words in a natural language sequence. the performance is restricted by the availability of labeled words. to tackle this issue, we propose a semi-supervised approach to improve the sequence labeling procedure in ie through a class of algorithms with {\em self-learned features} (slf). a supervised classifier can be trained with annotated text sequences and used to classify each word in a large set of unannotated sentences. by averaging predicted labels over all cases in the unlabeled corpus, slf training builds class label distribution patterns for each word (or word attribute) in the dictionary and re-trains the current model iteratively adding these distributions as extra word {\em features}. basic slf models how likely a word could be assigned to target class types. several extensions are proposed, such as learning words' class boundary distributions. slf exhibits robust and scalable behaviour and is easy to tune. we applied this approach on four classical ie tasks: named entity recognition (german and english), part-of-speech tagging (english) and one gene name recognition corpus. experimental results show effective improvements over the supervised baselines on all tasks. in addition, when compared with the closely related self-training idea, this approach shows favorable advantages.
evaluating statistical tests for within-network classifiers of relational data. recently a number of modeling techniques have been developed for data mining and machine learning in relational and network domains where the instances are not independent and identically distributed (i.i.d.). these methods specifically exploit the statistical dependencies among instances in order to improve classification accuracy. however, there has been little focus on how these same dependencies affect our ability to draw accurate conclusions about the performance of the models. more specifically, the complex link structure and attribute dependencies in network data violate the assumptions of many conventional statistical tests and make it difficult to use these tests to assess the models in an unbiased manner. in this work, we examine the task of within-network classification and the question of whether two algorithms will learn models which will result in significantly different levels of performance. we show that the commonly-used form of evaluation (paired t-test on overlapping network samples) can result in an unacceptable level of type i error. furthermore we show that type i error increases as (1) the correlation among instances increases and (2) the size of the evaluation set increases (i.e., the proportion of labeled nodes in the network decreases). we propose a method for network cross-validation that combined with paired t-tests produces more acceptable levels of type i error while still providing reasonable levels of statistical power (i.e., type ii error).
cofkm: a centralized method for multiple-view clustering. this paper deals with clustering for multi-view data, i.e. objects described by several sets of variables or proximity matrices. many important domains or applications such as information retrieval, biology, chemistry and marketing are concerned by this problematic. the aim of this data mining research field is to search for clustering patterns that perform a consensus between the patterns from different views. this requires to merge information from each view by performing a fusion process that identifies the agreement between the views and solves the conflicts. various fusion strategies can be applied, occurring either before, after or during the clustering process. we draw our inspiration from the existing algorithms based on a centralized strategy. we propose a fuzzy clustering approach that generalizes the three fusion strategies and outperforms the main existing multi-view clustering algorithm both on synthetic and real datasets.
interaction-based clustering of multivariate time series. in this paper, we present a novel approach to clustering multivariate time series. in contrast to previous approaches, we base our cluster notion on the interactions between the univariate time series within a data object. our objective is to assign objects with a similar intrinsic interaction pattern to a common cluster. to formalize this idea, we define a cluster by a set of mathematical models describing the cluster-specific interaction pattern. in addition, we propose interaction k-means (ikm), an efficient algorithm for partitioning clustering of multivariate time series. the cluster-specific interaction patterns detected by ikm provide valuable information for interpretation of the cluster content. an extensive experimental evaluation on synthetic and real world data demonstrates the effectiveness and efficiency of our approach.
convex non-negative matrix factorization in the wild. non-negative matrix factorization (nmf) has recently received a lot of attention in data mining, information retrieval, and computer vision. it factorizes a non-negative input matrix v into two non-negative matrix factors v = wh such that w describes "clusters" of the datasets. analyzing genotypes, social networks, or images, it can be beneficial to ensure v to contain meaningful ``cluster centroids'', i.e., to restrict w to be convex combinations of data points. but how can we run this convex nmf in the wild, i.e., given millions of data points? triggered by the simple observation that each data point is a convex combination of vertices of the data convex hull, we propose to restrict w further to be vertices of the convex hull. the benefits of this convex-hull nmf approach are twofold. first, the expected size of the convex hull of the candidate set typically grows much slower than the data set. second, distance preserving low-dimensional embeddings allow one to compute candidate vertices efficiently. our extensive experimental evaluation shows that convex-hull nmf compares favorably to convex nmf for large data sets both in terms of speed and reconstruction quality. moreover, we show that our method can easily be applied to large-scale, real-world data sets, in our case consisting of 1.6 million images respectively 160 million votes on world of warcraft guilds.
a walk from 2-norm svm to 1-norm svm. this paper studies how useful the standard 2-norm regularized svm is in approximating the 1-norm svm problem. to this end, we examine a general method that is based on iteratively re-weighting the features and solving a 2-norm optimization problem. the convergence rate of this method is unknown. previous work indicates that it might require an excessive number of iterations. we study how well we can do with just a small number of iterations. in theory the convergence rate is fast, except for coordinates of the current solution that are close to zero. our empirical experiments confirm this. in many problems with irrelevant features, already one iteration is often enough to produce accuracy as good as or better than that of the 1-norm svm. hence, it seems that in these problems we do not need to converge to the 1-norm svm solution near zero values. the benefit of this approach is that we can build something similar to the 1-norm regularized solver based on any 2-norm regularized solver. this is quick to implement and the solution inherits the good qualities of the solver such as scalability and stability.
flownet: flow-based approach for efficient analysis of complex biological networks. biological networks having complex connectivity have been widely studied recently. by characterizing their inherent and structural behaviors in a topological perspective, these studies have attempted to discover hidden knowledge in the systems. however, even though various algorithms with graph-theoretical modeling have provided fundamentals in the network analysis, the availability of practical approaches to efficiently handle the complexity has been limited. in this paper, we present a novel flow-based approach, called flownet, to efficiently analyze large-sized, complex networks. our approach is based on the functional influence model that quantifies the influence of a biological component on another. we introduce a dynamic flow simulation algorithm to generate a flow pattern which is a unique characteristic for each component. the set of patterns can be used in identifying functional modules (i.e., clustering). the proposed flow simulation algorithm runs very efficiently in sparse networks. since our approach uses a weighted network as an input, we also discuss supervised and unsupervised weighting schemes for unweighted biological networks. as experimental results in real applications to the yeast protein interaction network, we demonstrate that our approach outperforms previous graph clustering methods with respect to accuracy.
discriminative mixed-membership models. although mixed-membership models have achieved great success in unsupervised learning, they have not been widely applied to classification problems. in this paper, we propose a family of discriminative mixed-membership models for classification by combining unsupervised mixed-membership models with multi-class logistic regression. in particular, we propose two variants respectively applicable to text classification based on latent dirichlet allocation and usual feature vector classification based on mixed-membership naive bayes models. the proposed models allow the number of components in the mixed membership to be different from the number of classes. we propose two variational inference based algorithms for learning the models, including a fast variational inference which is substantially more efficient than mean-field variational approximation. through extensive experiments on uci and text classification benchmark datasets, we show that the models are competitive with the state of the art, and can discover components not explicitly captured by the class labels.
bayesian overlapping subspace clustering. given a data matrix, the problem of finding dense/uniform sub-blocks in the matrix is becoming important in several applications. the problem is inherently combinatorial since the uniform sub-blocks may involve arbitrary subsets of rows and columns and may even be overlapping. while there are a few existing methods based on co-clustering or subspace clustering, they typically rely on local search heuristics and in general do not have a systematic model for such data. we present a bayesian overlapping subspace clustering (bosc) model which is a hierarchical generative model for matrices with potentially overlapping uniform sub-block structures. the bosc model can also handle matrices with missing entries. we propose an em-style algorithm based on approximate inference using gibbs sampling and parameter estimation using coordinate descent for the bosc model. through experiments on both simulated and real datasets, we demonstrate that the proposed algorithm outperforms the state-of-the-art.