OpenRaiser/Intern-Atlas huggingface dataset:
Coherent closed quasi-clique discovery from large dense graph databases
Authors: Zhiping Zeng, Jianyong Wang, Lizhu Zhou, George Karypis
Venue: KDD
Year: 2006

Frequent coherent subgraphs can provide valuable knowledge about the underlying internal structure of a graph database, and mining frequently occurring coherent subgraphs from large dense graph databases has been witnessed several applications and received considerable attention in the graph mining community recently. In this paper, we study how to efficiently mine the complete set of coherent closed quasi-cliques from large dense graph databases, which is an especially challenging task due to the downward-closure property no longer holds. By fully exploring some properties of quasi-cliques, we propose several novel optimization techniques, which can prune the unpromising and redundant sub-search spaces effectively. Meanwhile, we devise an efficient closure checking scheme to facilitate the discovery of only closed quasi-cliques. We also develop a coherent closed quasi-clique mining algorithm, <B>Cocain</B>1 Thorough performance study shows that Cocain is very efficient and scalable for large dense graph databases.
Attack detection in time series for recommender systems
Authors: Sheng Zhang, Amit Chakrabarti, James Ford, Fillia Makedon
Venue: KDD
Year: 2006

Recent research has identified significant vulnerabilities in automated recommendation systems. Shilling attacks, in which attackers introduce biased ratings in order to influence future recommendations, have been shown to be effective against collaborative filtering algorithms. We postulate that the distribution of item ratings in time can reveal the presence of a wide range of shilling attacks. To construct a time series of ratings for an item, we use a window size of k to group consecutive ratings for the item into disjoint windows and compute the sample average and sample entropy in each window. We show that observing the time series of these two features can expose attack events given reasonable assumptions about their duration. If the number of attack profiles is known, an optimal window size can be derived theoretically in order to best detect the rating distribution changes caused by attacks. For practical applications where the number of attacks is unknown, we propose a heuristic algorithm that adaptively changes the window size. Our experimental results show that monitoring rating distributions in a time series is an effective approach for detecting shilling attacks. 1.
Identifying bridging rules between conceptual clusters
Authors: Shichao Zhang, Feng Chen, Xindong Wu, Chengqi Zhang
Venue: KDD
Year: 2006

A bridging rule in this paper has its antecedent and action from different conceptual clusters. We first design two algorithms for mining bridging rules between clusters in a database, and then propose two non-linear metrics for measuring the interestingness of bridging rules. Bridging rules can be distinct from association rules (or frequent itemsets). This is because (1) bridging rules can be generated by infrequent itemsets that are pruned in association rule mining; and (2) bridging rules are measured by the importance that includes the distance between two conceptual clusters, whereas frequent itemsets are measured by only the support.
Mining progressive confident rules
Authors: Minghua Zhang, Wynne Hsu, Mong-Li Lee
Venue: KDD
Year: 2006

Many real world objects have states that change over time. By tracking the state sequences of these objects, we can study their behavior and take preventive measures before they reach some undesirable states. In this paper, we propose a new kind of pattern called progressive confident rules to describe sequences of states with an increasing confidence that lead to a particular end state. We give a formal definition of progressive confident rules and their concise set. We devise pruning strategies to reduce the enormous search space. Experiment result shows that the proposed algorithm is efficient and scalable. We also demonstrate the application of progressive confident rules in classification.
Linear prediction models with graph regularization for web-page categorization
Authors: Tong Zhang, Alexandrin Popescul, Byron Dom
Venue: KDD
Year: 2006

We present a risk minimization formulation for learning from both text and graph structures which is motivated by the problem of collective inference for hypertext document categorization. The method is based on graph regularization formulated as a well-formed convex optimization problem. We present numerical algorithms for our formulation, and show that such combination of local text features and link information can lead to improved predictive accuracy.
Event detection from evolution of click-through data
Authors: Qiankun Zhao, Tie-Yan Liu, Sourav S. Bhowmick, Wei-Ying Ma
Venue: KDD
Year: 2006

Previous efforts on event detection from the web have focused primarily on web content and structure data ignoring the rich collection of web log data. In this paper, we propose the first approach to detect events from the click-through data, which is the log data of web search engines. The intuition behind event detection from click-through data is that such data is often event-driven and each event can be represented as a set ofquery-page pairs that are not only semantically similar but also have similar evolution pattern over time. Given the click-through data, in our proposed approach, we first segment it into a sequence of bipartite graphs based on theuser-defined time granularity. Next, the sequence of bipartite graphs is represented as a vector-based graph, which records the semantic and evolutionary relationships between queries and pages. After that, the vector-based graph is transformed into its dual graph, where each node is a query-page pair that will be used to represent real world events. Then, the problem of event detection is equivalent to the problem of clustering the dual graph of the vector-based graph. The clustering process is based on a two-phase graph cut algorithm. In the first phase, query-page pairs are clustered based on thesemantic-based similarity such that each cluster in the result corresponds to a specific topic. In the second phase, query-page pairs related to the same topic are further clustered based on the evolution pattern-based similarity such that each cluster is expected to represent a specific event under the specific topic. Experiments with real click-through data collected from a commercial web search engine show that the proposed approach produces high quality results.
Opportunity map: identifying causes of failure - a deployed data mining system
Authors: Kaidi Zhao, Bing Liu, Jeffrey Benkler, Weimin Xiao
Venue: KDD
Year: 2006

In this paper, we report a deployed data mining application system for Motorola. Originally, its intended use was for identifying causes of cellular phone failures, but it has been found to be useful for many other engineering data sets as well. For this report, the case study is a dataset containing cellular phone call records. This data set is like any dataset used in classification applications, i.e., with a set of attributes which can be continuous or discrete, and a discrete class attribute. In our application, the classes are normally ended calls, calls which failed to setup, and calls which failed while in progress. However, the task is not to predict any failure, but to identify possible causes that resulted in failures. Then, engineering efforts may focus on improvements that can be made to the phones. In the course of the project, various classification techniques, e.g., decision trees, naïve Bayesian classification and SVM were tried. However, the results were unsatisfactory. After several demonstrations and interaction with domain experts, we finally designed and implemented an effective approach to perform the task. The final system is based on class association rules, general impressions and visualization. The system has been deployed and is in regular use at Motorola. In this paper, we first describe our experiences with some existing classification systems and discuss why they are not suitable for the task. We then present our techniques. As an illustration, we show several visualization screens in the case study, which reveal some important knowledge. Due to confidentiality, we will not give specifics but only present a general discussion about the results.
BLOSOM: a framework for mining arbitrary boolean expressions
Authors: Lizhuang Zhao, Mohammed J. Zaki, Naren Ramakrishnan
Venue: KDD
Year: 2006

We introduce a novel framework, called BLOSOM, for mining (frequent) boolean expressions over binary-valued datasets. We organize the space of boolean expressions into four categories: pure conjunctions, pure disjunctions, conjunction of disjunctions, and disjunction of conjunctions. We focus on mining the simplest expressions the minimal generators for each class. We also propose a closure operator for each class that yields closed boolean expressions. BLOSOM efficiently mines frequent boolean expressions by utilizing a number of methodical pruning techniques. Experiments showcase the behavior of BLOSOM, and an application study on a real dataset is also given.
Estimating rates of rare events at multiple resolutions
Authors: Deepak Agarwal, Andrei Z. Broder, Deepayan Chakrabarti, Dejan Diklic, Vanja Josifovski, Mayssam Sayyadian
Venue: KDD
Year: 2007

We consider the problem of estimating occurrence rates of rare eventsfor extremely sparse data, using pre-existing hierarchies to perform inference at multiple resolutions. In particular, we focus on the problem of estimating click rates for (webpage, advertisement) pairs (called impressions) where both the pages and the ads are classified into hierarchies that capture broad contextual information at different levels of granularity. Typically the click rates are low and the coverage of the hierarchies is sparse. To overcome these difficulties we devise a sampling method whereby we analyze aspecially chosen sample of pages in the training set, and then estimate click rates using a two-stage model. The first stage imputes the number of (webpage, ad) pairs at all resolutions of the hierarchy to adjust for the sampling bias. The second stage estimates clickrates at all resolutions after incorporating correlations among sibling nodes through a tree-structured Markov model. Both models are scalable and suited to large scale data mining applications. On a real-world dataset consisting of 1/2 billion impressions, we demonstrate that even with 95% negative (non-clicked) events in the training set, our method can effectively discriminate extremely rare events in terms of their click propensity.
Predictive discrete latent factor models for large scale dyadic data
Authors: Deepak Agarwal, Srujana Merugu
Venue: KDD
Year: 2007

We propose a novel statistical method to predict large scale dyadic response variables in the presence of covariate information. Our approach simultaneously incorporates the effect of covariates and estimates local structure that is induced by interactions among the dyads through a discrete latent factor model. The discovered latent factors provide a redictive model that is both accurate and interpretable. We illustrate our method by working in a framework of generalized linear models, which include commonly used regression techniques like linear regression, logistic regression and Poisson regression as special cases. We also provide scalable generalized EM-based algorithms for model fitting using both "hard" and "soft" cluster assignments. We demonstrate the generality and efficacy of our approach through large scale simulation studies and analysis of datasets obtained from certain real-world movie recommendation and internet advertising applications.
Xproj: a framework for projected structural clustering of xml documents
Authors: Charu C. Aggarwal, Na Ta, Jianyong Wang, Jianhua Feng, Mohammed Javeed Zaki
Venue: KDD
Year: 2007

XML has become a popular method of data representation both on the web and in databases in recent years. One of the reasons for the popularity of XML has been its ability to encode structural information about data records. However, this structural characteristic of data sets also makes it a challenging problem for a variety of data mining problems. One such problem is that of clustering, in which the structural aspects of the data result in a high implicit dimensionality of the data representation. As a result, it becomes more difficult to cluster the data in a meaningful way. In this paper, we propose an effective clustering algorithm for XML data which uses substructures of the documents in order to gain insights about the important underlying structures. We propose new ways of using multiple sub-structuralinformation in XML documents to evaluate the quality of intermediate cluster solutions, and guide the algorithms to a final solution which reflects the true structural behavior in individual partitions. We test the algorithm on a variety of real and synthetic data sets.
Calculating latent demand in the long tail
Authors: Chris Anderson
Venue: KDD
Year: 2007

An analytical framework for using powerlaw theory to estimate market size for niche products and consumer groups.
Show me the money!: deriving the pricing power of product features by mining consumer reviews
Authors: Nikolay Archak, Anindya Ghose, Panagiotis G. Ipeirotis
Venue: KDD
Year: 2007

The increasing pervasiveness of the Internet has dramatically changed the way that consumers shop for goods. Consumer-generated product reviews have become a valuable source of information for customers, who read the reviews and decide whether to buy the product based on the information provided. In this paper, we use techniques that decompose the reviews into segments that evaluate the individual characteristics of a product (e.g., image quality and battery life for a digital camera). Then, as a major contribution of this paper, we adapt methods from the econometrics literature, specifically the hedonic regression concept, to estimate: (a) the weight that customers place on each individual product feature, (b) the implicit evaluation score that customers assign to each feature, and (c) how these evaluations affect the revenue for a given product. Towards this goal, we develop a novel hybrid technique combining text mining and econometrics that models consumer product reviews as elements in a tensor product of feature and evaluation spaces. We then impute the quantitative impact of consumer reviews on product demand as a linear functional from this tensor product space. We demonstrate how to use a low-dimension approximation of this functional to significantly reduce the number of model parameters, while still providing good experimental results. We evaluate our technique using a data set from Amazon.com consisting of sales data and the related consumer reviews posted over a 15-month period for 242 products. Our experimental evaluation shows that we can extract actionable business intelligence from the data and better understand the customer preferences and actions. We also show that the textual portion of the reviews can improve product sales prediction compared to a baseline technique that simply relies on numeric data.
An event-based framework for characterizing the evolutionary behavior of interaction graphs
Authors: Sitaram Asur, Srinivasan Parthasarathy, Duygu Ucar
Venue: KDD
Year: 2007

Interaction graphs are ubiquitous in many fields such as bioinformatics, sociology and physical sciences. There have been many studies in the literature targeted at studying and mining these graphs. However, almost all of them have studied these graphs from a static point of view. The study of the evolution of these graphs over time can provide tremendous insight on the behavior of entities, communities and the flow of information among them. In this work, we present an event-based characterization of critical behavioral patterns for temporally varying interaction graphs. We use non-overlapping snapshots of interaction graphs and develop a framework for capturing and identifying interesting events from them. We use these events to characterize complex behavioral patterns of individuals and communities over time. We demonstrate the application of behavioral patterns for the purposes of modeling evolution, link prediction and influence maximization. Finally, we present a diffusion model for evolving networks, based on our framework.
Content-based document routing and index partitioning for scalable similarity-based searches in a large corpus
Authors: Deepavali Bhagwat, Kave Eshghi, Pankaj Mehra
Venue: KDD
Year: 2007

We present a document routing and index partitioning scheme for scalable similarity-based search of documents in a large corpus. We consider the case when similarity-based search is performed by finding documents that have features in common with the query document. While it is possible to store all the features of all the documents in one index, this suffers from obvious scalability problems. Our approach is to partition the feature index into multiple smaller partitions that can be hosted on separate servers, enabling scalable and parallel search execution. When a document is ingested into the repository, a small number of partitions are chosen to store the features of the document. To perform similarity-based search, also, only a small number of partitions are queried. Our approach is stateless and incremental. The decision as to which partitions the features of the document should be routed to (for storing at ingestion time, and for similarity based search at query time) is solely based on the features of the document.
Support feature machine for classification of abnormal brain activity
Authors: Wanpracha Art Chaovalitwongse, Ya-Ju Fan, Rajesh C. Sachdeo
Venue: KDD
Year: 2007

In this study, a novel multidimensional time series classification technique, namely support feature machine (SFM), is proposed. SFM is inspired by the optimization model of support vector machine and the nearest neighbor rule to incorporate both spatial and temporal of the multi-dimensional time series data. This paper also describes an application of SFM for detecting abnormal brain activity. Epilepsy is a case in point in this study. In epilepsy studies, electroencephalograms (EEGs), acquired in multidimensional time series format, have been traditionally used as a gold-standard tool for capturing the electrical changes in the brain. From multi-dimensional EEG time series data, SFM was used to identify seizure pre-cursors and detect seizure susceptibility (pre-seizure) periods. The empirical results showed that SFM achieved over 80% correct classification of per-seizure EEG on average in 10 patients using 5-fold cross validation. The proposed optimization model of SFM is very compact and scalable, and can be implemented as an online algorithm. The outcome of this study suggests that it is possible to construct a computerized algorithm used to detect seizure pre-cursors and warn of impending seizures through EEG classification.
Cross-language information retrieval using PARAFAC2
Authors: Peter A. Chew, Brett W. Bader, Tamara G. Kolda, Ahmed Abdelali
Venue: KDD
Year: 2007

A standard approach to cross-language information retrieval (CLIR) uses Latent Semantic Analysis (LSA) in conjunction with a multilingual parallel aligned corpus. This approach has been shown to be successful in identifying similar documents across languages - or more precisely, retrieving the most similar document in one language to a query in another language. However, the approach has severe drawbacks when applied to a related task, that of clustering documents "language-independently", so that documents about similar topics end up closest to one another in the semantic space regardless of their language. The problem is that documents are generally more similar to other documents in the same language than they are to documents in a different language, but on the same topic. As a result, when using multilingual LSA, documents will in practice cluster by language, not by topic.
Structural and temporal analysis of the blogosphere through community factorization
Authors: Yun Chi, Shenghuo Zhu, Xiaodan Song, Jun&apos, ichi Tatemura, Belle L. Tseng
Venue: KDD
Year: 2007

The blogosphere has unique structural and temporal properties since blogs are typically used as communication media among human individuals. In this paper, we propose a novel technique that captures the structure and temporal dynamics of blog communities. In our framework, a community is a set of blogs that communicate with each other triggered by some events (such as a news article). The community is represented by its structure and temporal dynamics: a community graph indicates how often one blog communicates with another, and a community intensity indicates the activity level of the community that varies over time. Our method, community factorization, extracts such communities from the blogosphere, where the communication among blogs is observed as a set of subgraphs (i.e., threads of discussion). This community extraction is formulated as a factorization problem in the framework of constrained optimization, in which the objective is to best explain the observed interactions in the blogosphere over time. We further provide a scalable algorithm for computing solutions to the constrained optimization problems. Extensive experimental studies on both synthetic and real blog data demonstrate that our technique is able to discover meaningful communities that are not detectable by traditional methods.
Discovering the hidden structure of house prices with a non-parametric latent manifold model
Authors: Sumit Chopra, Trivikraman Thampy, John Leahy, Andrew Caplin, Yann LeCun
Venue: KDD
Year: 2007

In many regression problems, the variable to be predicted depends not only on a sample-specific feature vector, but also on an unknown (latent) manifold that must satisfy known constraints. An example is house prices, which depend on the characteristics of the house, and on the desirability of the neighborhood, which is not directly measurable. The proposed method comprises two trainable components. The first one is a parametric model that predicts the "intrinsic" price of the house from its description. The second one is a smooth, non-parametric model of the latent "desirability" manifold. The predicted price of a house is the product of its intrinsic price and desirability. The two components are trained simultaneously using a deterministic form of the EM algorithm. The model was trained on a large dataset of houses from Los Angeles county. It produces better predictions than pure parametric and non-parametric models. It also produces useful estimates of the desirability surface at each location.
Stochastic processes and temporal data mining
Authors: Paul Cotofrei, Kilian Stoffel
Venue: KDD
Year: 2007

This article tries to give an answer to a fundamental question intemporal data mining: "Under what conditions a temporal rule extracted from up-to-date temporal data keeps its confidence/support for future data". A possible solution is given by using, on the one hand, a temporal logic formalism which allows the definition of the main notions (event, temporal rule, support, confidence) in a formal way and, on the other hand, the stochastic limit theory. Under this probabilistic temporal framework, the equivalence between the existence of the support of a temporal rule and the law of large numbers is systematically analyzed.