Generative AI and the use of large language models (LLMs) are changing the way we work, create, play, and live. As we have witnessed in the past few years, there is significant progress in training LLMs to have a deep understanding of the semantics of language so that such models begin to perform ''reasoning''. (Human) Reasoning is the process of applying logic to derive conclusions based on new or existing information with the goal of finding the truth. Reasoning is a form of high-level human intelligence. There are many types of reasoning: mathematical reasoning, common sense reasoning, temporal reasoning, among others. Multi-hope reasoning with LLM is an emerging capability for LLMs with tens of billions of parameters. Such ''reasoning models'', including Sonnet 3.7, Chat GPT O1, have powered important application areas such as AI4coding, agentic workflow, among others. The first KDD AI Reasoning Day is a special event that we organize in order to increase the awareness of this important research topic for the research community. We bring leaders from industry and academia to present the latest progresses on improving LLM's reasoning capability and enabling reasoning for different application development.

Time series data is now pervasive across domains such as healthcare, finance, entertainment, and transportation, driven by advances in sensing technologies that enable continuous data collection. The resulting increase in data volume and complexity poses significant challenges to traditional analysis methods, calling for the development of advanced, interdisciplinary approaches to temporal data mining. This workshop aims to: (1) identify key challenges in learning from time series data, including irregular sampling, spatiotemporal dependencies, and uncertainty quantification; (2) explore recent advances in algorithmic, statistical, theoretical, and systems-based solutions-ranging from classical methods to emerging techniques involving large language models (LLMs); and (3) foster collaboration by highlighting open problems and novel research directions in time series analysis. Bridging theory and practice, the workshop provides a platform for researchers and practitioners from academia, industry, and government to exchange ideas, discuss technical challenges, and showcase practical applications. Contributions from related areas such as AI, machine learning, data science, and statistics are strongly encouraged.

Getting large language models (LLMs) to perform well on the downstream tasks requires pre-training over trillions of tokens. This typically demands a large number of powerful computational devices in addition to a stable distributed training framework to accelerate the training. The growing number of applications leveraging AI/ML led to a scarcity of the expensive conventional accelerators (such as GPUs), which emphasizes the need for the alternative specialized-accelerators that are scalable and cost-efficient. AWS Trainium is the second-generation machine learning accelerator purposely built for training large deep learning models. However, training LLMs with billions of parameters on AWS Trainium is challenging due to its relatively nascent software ecosystem. In this paper, we showcase HLAT: a family of 7B and 70B decoder-only LLMs pre-trained using 4096 AWS Trainium accelerators over 1.8 trillion tokens. The performance of HLAT is benchmarked against popular open source models including LLaMA and OpenLLaMA, which have been trained on NVIDIA GPUs and Google TPUs, respectively. On various evaluation tasks, we show that HLAT achieves model quality on par with the baselines of similar model size. We also open-source all the training scripts and configurations of HLAT1and share the best practice of using the NeuronX Distributed Training (NxDT), a customized distributed training library for AWS Trainium. Our work demonstrates that AWS Trainium powered by NxDT is able to successfully pre-train state-of-the-art LLM models with high performance and cost-effectiveness.

Large Language Models (LLMs) are revolutionizing the field of code development by leveraging their deep understanding of code patterns, syntax, and semantics to assist developers in various tasks, from code generation and testing to code understanding and documentation. In this survey, accompanying our proposed lecture-style tutorial for KDD 2024, we explore the multifaceted impact of LLMs on the code development, delving into techniques for generating a high-quality code, creating comprehensive test cases, automatically generating documentation, and engaging in an interactive code reasoning. Throughout the survey, we highlight some crucial components surrounding LLMs, including pre-training, fine-tuning, prompt engineering, iterative refinement, agent planning, and hallucination mitigation. We put forward that such ingredients are essential to harness the full potential of these powerful AI models in revolutionizing software engineering and paving the way for a more efficient, effective, and innovative future in code development.

Powerful foundation models, including large language models (LLMs), with Transformer architectures have ushered in a new era of Generative AI across various industries. Industry and research community have witnessed a large number of new applications, based on those foundation models. Such applications include question and answer, customer services, image and video generation, and code completions, among others. However, as the number of model parameters reaches to hundreds of billions, their deployment incurs prohibitive inference costs and high latency in real-world scenarios. As a result, the demand for cost-effective and fast inference using AI accelerators is ever more higher. To this end, our tutorial offers a comprehensive discussion on complementary inference optimization techniques using AI accelerators. Beginning with an overview of basic Transformer architectures and deep learning system frameworks, we deep dive into system optimization techniques for fast and memory-efficient attention computations and discuss how they can be implemented efficiently on AI accelerators. Next, we describe architectural elements that are key for fast transformer inference. Finally, we examine various model compression and fast decoding strategies in the same context.

Time series data has become ubiquitous across various fields such as healthcare, finance, entertainment, and transportation, driven by advancements in sensing technologies that enable continuous monitoring and recording. This growth in data size and complexity presents new challenges for traditional analysis techniques, necessitating the development of advanced, interdisciplinary temporal mining algorithms. The goals of this workshop are to: (1) highlight significant challenges in learning and mining from time series data, such as irregular sampling, spatiotemporal structures, and uncertainty quantification; (2) discuss recent developments in algorithmic, theoretical, statistical, and systems-based approaches for addressing these challenges, including both classical methods and large language models (LLMs); and (3) synergize research efforts by exploring both new and open problems in time series analysis and mining. This workshop will focus on both the theoretical and practical aspects of time series data analysis, providing a platform for researchers and practitioners from academia, government, and industry to discuss potential research directions, critical technical issues, and present solutions for practical applications. Contributions from related fields such as AI, machine learning, data science, and statistics are also included.

There is huge value in making software development more productive with AI. An important component of this vision is the capability to translate natural language to a programming language ("NL2Code") and thus to significantly accelerate the speed at which code is written.

Foundation models such as ChatGPT and GPT-4 have garnered significant interest from both academia and industry due to their emergent capabilities, such as few-shot prompting, multi-step reasoning, instruction following, and model calibration. Such capabilities were previously only attainable with specially designed models, such as those using knowledge graphs, but can now be achieved on a much larger scale with foundation models. As the capabilities of foundation models have increased, so too have their sizes at a rate much faster than Moore's law. For example, the BERT large model was initially released as a 334M model in 2018, and by 2023, the largest GPT-4 models are estimated to range between 200-300B, representing an increase of three orders of magnitude in just five years. The training of foundation models requires massive computing power. For instance, training a BERT model on a single state-of-the-art GPU machine with multi-A100 chips can take several days, while training GPT-3 models on a large multi-instance GPU cluster can take several months to complete the estimated 3 X 1023 flops.

Time series data has become pervasive across domains such as finance, transportation, retail, entertainment, and healthcare. This shift towards continuous monitoring and recording, fueled by advancements in sensing technologies, necessitates the development of new tools and solutions. Despite extensive study, the importance of time series analysis continues to increase. However, modern time series data present challenges to existing techniques, including irregular sampling and spatiotemporal structures. Time series mining research is both challenging and rewarding as it connects diverse disciplines and requires interdisciplinary solutions. The goals of this workshop are to (1) highlight the significant challenges that underpin learning and mining from time series data (e.g., irregular sampling, spatiotemporal structure, uncertainty quantification), (2) discuss recent algorithmic, theoretical, statistical, or systems-based developments for tackling these problems, and (3) to synergize the research activities and discuss both new and open problems in time series analysis and mining. In summary, our workshop will focus on both the theoretical and practical aspects of time series data analysis and will provide a platform for researchers and practitioners from academia and industry to discuss potential research directions and critical technical issues and present solutions to tackle related issues in practical applications. We will invite researchers and practitioners from the related areas of AI, machine learning, data science, statistics, and many others to contribute to this workshop.

Random Walk is a basic algorithm to explore the structure of networks, which can be used in many tasks, such as local community detection and network embedding. Existing random walk methods are based on single networks that contain limited information. In contrast, real data often contain entities with different types or/and from different sources, which are comprehensive and can be better modeled by multiple networks. To take the advantage of rich information in multiple networks and make better inferences on entities, in this study, we propose random walk on multiple networks, RWM. RWM is flexible and supports both multiplex networks and general multiple networks, which may form many-to-many node mappings between networks. RWM sends a random walker on each network to obtain the local proximity (i.e., node visiting probabilities) w.r.t. the starting nodes. Walkers with similar visiting probabilities reinforce each other. We theoretically analyze the convergence properties of RWM. Two approximation methods with theoretical performance guarantees are proposed for efficient computation. We apply RWM in link prediction, network embedding, and local community detection. Comprehensive experiments conducted on both synthetic and real-world datasets demonstrate the effectiveness and efficiency of RWM.

The Sixth International Workshop on Automation in Machine Learning aims to identify opportunities and challenges for automation in machine learning, to provide an opportunity for researchers to discuss best practices for automation in machine learning potentially leading to definition of standards, and to provide a forum for researchers to speak out and debate on different ideas in automation in machine learning. The workshop agenda includes four invited keynote speakers and four accepted paper presentations chosen from a peer review process. The workshop seeks to drive engaging and interactive exchange of thoughts and ideas on AutoML.

Time series data are ubiquitous, and is one of the fastest growing and richest types of data. Recent advances in sensing technologies has resulted in a rapid growth in the size and complexity of time series archives. This demands development of new tools and solutions. The goals of this workshop are to: (1) highlight the significant challenges that underpin learning and mining from time series data (e.g. irregular sampling, spatiotemporal structure, uncertainty quantification), (2) discuss recent algorithmic, theoretical, statistical, or systems-based developments for tackling these problems, and (3) exploring new frontiers in time series analysis and their connections with important topics such as knowledge representation, reasoning, control, and business intelligence. In summary, our workshop will focus on both the theoretical and practical aspects of time series data analysis and will provide a platform for researchers and practitioners from both academia and industry to discuss potential research directions, key technical issues, and present solutions to tackle related issues in practical applications. We will invite researchers and practitioners from the related areas of AI, machine learning, data science, statistics, and many others to contribute to this workshop.

Transfer learning through fine-tuning a pre-trained neural network with an extremely large dataset, such as ImageNet, can significantly improve and accelerate training while the accuracy is frequently bottlenecked by the limited dataset size of the new target task. To solve the problem, some regularization methods, constraining the outer layer weights of the target network using the starting point as references (SPAR), have been studied. In this article, we propose a novel regularized transfer learning framework \operatorname{DELTA} , namely DE ep L earning T ransfer using Feature Map with A ttention . Instead of constraining the weights of neural network, \operatorname{DELTA} aims at preserving the outer layer outputs of the source network. Specifically, in addition to minimizing the empirical loss, \operatorname{DELTA} aligns the outer layer outputs of two networks, through constraining a subset of feature maps that are precisely selected by attention that has been learned in a supervised learning manner. We evaluate \operatorname{DELTA} with the state-of-the-art algorithms, including L^2 and \emph {L}^2\text{-}SP . The experiment results show that our method outperforms these baselines with higher accuracy for new tasks. Code has been made publicly available. 1

Regularization that incorporates the linear combination of empirical loss and explicit regularization terms as the loss function has been frequently used for many machine learning tasks. The explicit regularization term is designed in different types, depending on its applications. While regularized learning often boost the performance with higher accuracy and faster convergence, the regularization would sometimes hurt the empirical loss minimization and lead to poor performance. To deal with such issues in this work, we propose a novel strategy, namely Gr adients O rthogonal D ecomposition ( GrOD ), that improves the training procedure of regularized deep learning. Instead of linearly combining gradients of the two terms, GrOD re-estimates a new direction for iteration that does not hurt the empirical loss minimization while preserving the regularization affects, through orthogonal decomposition. We have performed extensive experiments to use GrOD improving the commonly used algorithms of transfer learning [ 2 ], knowledge distillation [ 3 ], and adversarial learning [ 4 ]. The experiment results based on large datasets, including Caltech 256 [ 5 ], MIT indoor 67 [ 6 ], CIFAR-10 [ 7 ], and ImageNet [ 8 ], show significant improvement made by GrOD for all three algorithms in all cases.

Ensemble learning is a widely used technique to train deep convolutional neural networks (CNNs) for improved robustness and accuracy. While existing algorithms usually first train multiple diversified networks and then assemble these networks as an aggregated classifier, we propose a novel learning paradigm, namely, “In-Network Ensemble” ( INE ) that incorporates the diversity of multiple models through training a SINGLE deep neural network. Specifically, INE segments the outputs of the CNN into multiple independent classifiers, where each classifier is further fine-tuned with better accuracy through a so-called diversified knowledge distillation process . We then aggregate the fine-tuned independent classifiers using an Averaging-and-Softmax operator to obtain the final ensemble classifier. Note that, in the supervised learning settings, INE starts the CNN training from random, while, under the transfer learning settings, it also could start with a pre-trained model to incorporate the knowledge learned from additional datasets. Extensive experiments have been done using eight large-scale real-world datasets, including CIFAR, ImageNet, and Stanford Cars, among others, as well as common deep network architectures such as VGG, ResNet, and Wide ResNet. We have evaluated the method under two tasks: supervised learning and transfer learning. The results show that INE outperforms the state-of-the-art algorithms for deep ensemble learning with improved accuracy.

Stochastic Gradient Langevin Dynamics (SGLD) have been widely used for Bayesian sampling from certain probability distributions, incorporating derivatives of the log-posterior. With the derivative evaluation of the log-posterior distribution, SGLD methods generate samples from the distribution through performing as a thermostats dynamics that traverses over gradient flows of the log-posterior with certainly controllable perturbation. Even when the density is not known, existing solutions still can first learn the kernel density models from the given datasets, then produce new samples using the SGLD over the kernel density derivatives. In this work, instead of exploring new samples from kernel spaces, a novel SGLD sampler, namely, Randomized Measurement Langevin Dynamics (RMLD) is proposed to sample the high-dimensional sparse representations from the spectral domain of a given dataset. Specifically, given a random measurement matrix for sparse coding, RMLD first derives a novel likelihood evaluator of the probability distribution from the loss function of LASSO, then samples from the high-dimensional distribution using stochastic Langevin dynamics with derivatives of the logarithm likelihood and Metropolis–Hastings sampling. In addition, new samples in low-dimensional measuring spaces can be regenerated using the sampled high-dimensional vectors and the measurement matrix. The algorithm analysis shows that RMLD indeed projects a given dataset into a high-dimensional Gaussian distribution with Laplacian prior, then draw new sparse representation from the dataset through performing SGLD over the distribution. Extensive experiments have been conducted to evaluate the proposed algorithm using real-world datasets. The performance comparisons on three real-world applications demonstrate the superior performance of RMLD beyond baseline methods.

Graph similarity search under the graph edit distance constraint has received considerable attention in many applications, such as bioinformatics, data mining, pattern recognition and social networks. Existing methods for this problem have limited scalability because of the huge amount of memory they consume when handling very large graph databases with tens of millions of graphs. In this article, we present a succinct index that incorporates succinct data structures and hybrid encoding to achieve improved query time performance with minimal space usage. Specifically, the space usage of our index requires only 5-15 percent of the previous state-of-the-art indexing size while at the same time achieving several times acceleration in query time on the tested data. We also improve the query performance by augmenting the global filter with range searching, which allows us to perform similarity search in a reduced region. In addition, we propose two effective lower bounds together with a boosting technique to obtain the smallest possible candidate set. Extensive experiments demonstrate that our proposed approach is superior both in space and filtering to the state-of-the-art approaches. To the best of our knowledge, our index is the first in-memory index for this problem that successfully scales to cope with the large dataset of 25 million chemical structure graphs from the PubChem dataset. The source code is available online.

Local community detection for a given set of query nodes attracts much research attention recently. The query nodes play essential roles in the detection effectiveness. Existing methods perform well when a query node is from the target community core region. However, they struggle with the query-bias issue and especially perform unsatisfactorily when the query nodes come from different communities or when certain query nodes are from communities overlapping region or community boundary region. To address above issues, we consider from a new angle, to replace these original “intractable” query nodes with new detection-friendly query nodes. In this paper, we propose an effective ATP (Amplified Topology Potential) algorithm to detect core nodes of the target communities w.r.t. original query nodes. For one query node, ATP first builds a query-oriented topology potential field around the query node by aggregating random walk with restart scores. Then it amplifies the topology potential value to make core nodes of target communities easily distinguished. Graph-size-independent fast approximation strategies are also proposed together with sound theoretical foundations. Extensive experiments on four real networks using ten state-of-the-art local community detection methods verify the improvement in detection effectiveness and efficiency by the replacing strategy for the tough query cases.

Local community detection aims to find a set of densely-connected nodes containing given query nodes. Most existing local community detection methods are designed for a single network. However, a single network can be noisy and incomplete. Multiple networks are more informative in real-world applications. There are multiple types of nodes and multiple types of node proximities. Complementary information from different networks helps to improve detection accuracy. In this paper, we propose a novel RWM (Random Walk in Multiple networks) model to find relevant local communities in all networks for a given query node set from one network. RWM sends a random walker in each network to obtain the local proximity w.r.t. the query nodes (i.e., node visiting probabilities).

Sparse Discriminant Analysis (SDA) has been widely used to improve the performance of classical Fisher’s Linear Discriminant Analysis in supervised metric learning, feature selection, and classification. With the increasing needs of distributed data collection, storage, and processing, enabling the Sparse Discriminant Learning to embrace the multi-party distributed computing environments becomes an emerging research topic. This article proposes a novel multi-party SDA algorithm, which can learn SDA models effectively without sharing any raw data and basic statistics among machines. The proposed algorithm (1) leverages the direct estimation of SDA to derive a distributed loss function for the discriminant learning, (2) parameterizes the distributed loss function with local/global estimates through bootstrapping, and (3) approximates a global estimation of linear discriminant projection vector by optimizing the “distributed bootstrapping loss function” with gossip-based stochastic gradient descent. Experimental results on both synthetic and real-world benchmark datasets show that our algorithm can compete with the aggregated SDA with similar performance, and significantly outperforms the most recent distributed SDA in terms of accuracy and F1-score.

Federated machine learning systems have been widely used to facilitate the joint data analytics across the distributed datasets owned by the different parties that do not trust each others. In this paper, we proposed a novel Gradient Boosting Machines (GBM) framework SecureGBM built-up with a multi-party computation model based on semi-homomorphic encryption, where every involved party can jointly obtain a shared Gradient Boosting machines model while protecting their own data from the potential privacy leakage and inferential identification. More specific, our work focused on a specific “dualparty” secure learning scenario based on two parties — both party own an unique view (i.e., attributes or features) to the sample group of samples while only one party owns the labels. In such scenario, feature and label data are not allowed to share with others.To achieve the above goal, we firstly extent — LightGBM — a well known implementation of tree-based GBM through covering its key operations for training and inference with SEAL homomorphic encryption schemes. However, the performance of such re-implementation is significantly bottle-necked by the explosive inflation of the communication payloads, based on ciphertexts subject to the increasing length of plaintexts. In this way, we then proposed to use stochastic approximation techniques to reduced the communication payloads while accelerating the overall training procedure in a statistical manner. Our experiments using the real-world data showed that SecureGBM can well secure the communication and computation of LightGBM training and inference procedures for the both parties while only losing less than 3% AUC, using the same number of iterations for gradient boosting, on a wide range of benchmark datasets. More specific, compared to LightGBM, the proposed SecureGBM would slowdown with $3\mathrm{x} \sim 64\mathrm{x}$ time consumption per iteration in the training procedure, while SecureGBM becomes more and more efficient when the scale of the training dataset increases (i.e., the larger training set, the lower slowdown ratio).

Transfer learning have been frequently used to improve deep neural network training through incorporating weights of pre-trained networks as the starting-point of optimization for regularization. While deep transfer learning can usually boost the performance with better accuracy and faster convergence, transferring weights from inappropriate networks hurts training procedure and may lead to even lower accuracy. In this paper, we consider deep transfer learning as minimizing a linear combination of empirical loss and regularizer based on pre-trained weights, where the regularizer would restrict the training procedure from lowering the empirical loss, with conflicted descent directions (e.g., derivatives). Following the view, we propose a novel strategy making regularization-based Deep Transfer learning Never Hurt (DTNH) that, for each iteration of training procedure, computes the derivatives of the two terms separately, then re-estimates a new descent direction that does not hurt the empirical loss minimization while preserving the regularization affects from the pre-trained weights. Extensive experiments have been done using common transfer learning regularizers, such as L2-SP and knowledge distillation, on top of a wide range of deep transfer learning benchmarks including Caltech, MIT indoor 67, CIFAR-10 and ImageNet. The empirical results show that the proposed descent direction estimation strategy DTNH can always improve the performance of deep transfer learning tasks based on all above regularizers, even when transferring pre-trained weights from inappropriate networks. All in all, DTNH strategy can improve state-of-the-art regularizers in all cases with 0.1%-7% higher accuracy in all experiments.

We investigate the relationship between conditional independence (CI) x ⫫ y | Z and the independence of two residuals x −E( x | Z )⫫ y −E( y | Z ), where x and y are two random variables and Z is a set of random variables. We show that if x , y , and Z are generated by following linear structural equation models and all external influences follow joint Gaussian distribution, then x ⫫ y | Z if and only if x −E( x | Z )⫫ y −E( y | Z ). That is, the test of x ⫫ y | Z can be relaxed to a simpler unconditional independence test of x −E( x | Z )⫫ y −E( y | Z ). Furthermore, testing x −E( x | Z )⫫ y −E( y | Z ) can be simplified by testing x −E( x | Z )⫫ y or y −E( y | Z )⫫ x . On the other side, if all these external influences follow non-Gaussian distributions and the model satisfies structural faithfulness condition, then we have x ⫫ y | Z ⇔ x −E( x | Z )⫫ y −E( y | Z ). We apply the results above to the causal discovery problem, where the causal directions are generally determined by a set of V -structures and their consistent propagations, so CI test-based methods can return a set of Markov equivalence classes. We show that in the linear non-Gaussian context, in many cases x −E( x | Z )⫫ z or y −E( y | Z )⫫ z (∀ z ∈ Z and Z is a minimal d -separator) is satisfied when x −E( x | Z )⫫ y −E( y | Z ), which implies z causes x (or y ) if z directly connects to x (or y ). Therefore, we conclude that CIs have useful information for distinguishing Markov equivalence classes. In summary, comparing with the existing discretization-based and kernel-based CI testing methods, the proposed method provides a simpler way to measure CI, which needs only one unconditional independence test and two regression operations. When being applied to causal discovery, it can find more causal relationships, which is extensively validated by experiments.

Multi-task Multi-view (MTMV) learning has recently undergone noticeable development for dealing with heterogeneous data. To exploit information from both related tasks and related views, a common strategy is to model task relatedness and view consistency separately. The drawback of this strategy is that it did not consider the interactions between tasks and views. To remedy this, we propose a novel method, racBFA, by adding rank constraints to asymmetric bilinear factor analyzers (aBFA). We then adapt racBFA to our MTMV learning problem and design a new MTMV learning algorithm, racMTMV. We evaluated racMTMV on 3 real-world data sets. The experimental results demonstrated the effectiveness of our proposed method.

In this paper, we study the problem of MTMV learning in a lifelong learning framework. Lifelong machine learning, like human lifelong learning, learns multiple tasks over time. Lifelong multi-task multi-view (Lifelong MTMV) learning is a new data mining and machine learning problem where new tasks and/or new views may come in anytime during the learning process. Our goal is to efficiently learn a model for a new task or new view by selectively transferring knowledge learned from previous tasks or views. To this end, we propose a latent space lifelong MTMV (lslMTMV) learning method to exploit task relatedness and information from multiple views. In this new method, we map views to a shared latent space and then learn a decision function in the latent space. Our new method supports knowledge sharing among multiple views and knowledge transfer from existing tasks to a new learning task naturally. We have evaluated our method using 3 real-world data sets. The experimental study results demonstrate that the classification accuracy of our algorithm is close or superior to state-of-the-art offline MTMV learning algorithms while the time needed to train such models is orders of magnitude less.

Developing transparent predictive analytics has attracted significant research attention recently. There have been multiple theories on how to model learning transparency but none of them aims to understand the internal and often complicated modeling processes. In this paper we adopt a contemporary philosophical concept called "constructivism", which is a theory regarding how human learns. We hypothesize that a critical aspect of transparent machine learning is to "reveal" model construction with two key process: (1) the assimilation process where we enhance our existing learning models and (2) the accommodation process where we create new learning models. With this intuition we propose a new learning paradigm, constructivism learning, using a Bayesian nonparametric model to dynamically handle the creation of new learning tasks. Our empirical study on both synthetic and real data sets demonstrate that the new learning algorithm is capable of delivering higher quality models (as compared to base lines and state-of-the-art) and at the same time increasing the transparency of the learning process.

Mahalanobis distance metric learning becomes an especially challenging problem as the dimension of the feature space p is scaled upwards. The number of parameters to optimize grows with space complexity of order O (p 2), making storage infeasible, interpretability poor, and causing the model to have a high tendency to overfit. Additionally, optimization while maintaining feasibility of the solution becomes prohibitively expensive, requiring a projection onto the positive semi-definite cone after every iteration. In addition to the obvious space and computational challenges, vanilla distance metric learning is unable to model complex and multi-modal trends in the data. Inspired by the recent resurgence of Frank-Wolfe style optimization, we propose a new method for sparse compositional local Mahalanobis distance metric learning. Our proposed technique learns a set of distance metrics which are composed of local and global components. We capture local interactions in the feature space, while ensuring that all metrics share a global component, which may act as a regularizer. We optimize our model using an alternating pairwise Frank-Wolfe style algorithm. This serves a dual purpose, we can control the sparsity of our solution, and altogether avoid any expensive projection operations. Finally, we conduct an empirical evaluation of our method with the current state of the art and present the results on five datasets from varying domains.

Automatic social circle detection in ego-networks is a fundamentally important task for social network analysis. So far, most studies focused on how to detect overlapping circles or how to detect based on both network structure and node profiles. This paper asks an orthogonal research question: how to detect circles by leveraging multiple views of the network structure? As a first step, we crawl ego networks from Twitter and model them by six views, including user relationships, user interactions, and user content. We then apply both standard and our modified multi-view spectral clustering techniques to detect circles on these ego-networks. By extensive automatic and manual evaluations, we deliver two major findings: first, multi-view clustering techniques detect better circles than single-view clustering methods; second, our modified clustering technique which presumes sparse networks are incomplete detects better circles than the standard clustering technique which ignores such potential incompleteness. In particular, the second finding makes us conjecture a direct application of standard clustering on potentially incomplete networks may yield biased results. We lightly investigate this issue by deriving a bias upper bound that integrates theories of spectral clustering and matrix perturbation, and discussing how the bound may be affected by several network characteristics.

We investigate a new direction of multi-task multi-view learning where we have data sets with multiple tasks, multiple views and multiple labels. We call this problem a multi-task multi-view multi-label learning problem or MTVL learning for short. There is a wide application of MTVL leaning where examples include Internet of Things, brain science, and document classification. In designing effective MTVL learning algorithms, we hypothesize that a key component is to "disentangle" interactions among tasks, views, and labels, or the Ütask-view-label interactions. For that purpose we have developed an adaptive-basis multilinear analyzers(aptMLFA) that utilizes a loading tensor to modulate interactions among multiple latent factors. With aptMLFA we designed a new MTVL learning algorithm, aptMTVL, and evaluated its performance on 3 real-world data sets. The experimental results demonstrated the effectiveness of our proposed method as compared to the state-of-the-art MTVL learning algorithm.

Co-training, a popular semi-supervised learning technique, is severely limited as it applicable only to datasets which have a natural division of the feature space into two or more distinct views. In this paper, we investigate techniques to apply co-training to single-view data sets. We develop a view learning technique which takes a single view dataset and learns multiple views. These learned views balance the available discriminatory information in the dataset, while still meeting Blum's co-training criteria. In addition, we constrain the views such that pairs of learned view embedding functions exhibit sparsity in a complementary pattern, which aid in increasing diversity. Finally, we demonstrate the efficacy of our approach via experimental means on several real-world datasets from different domains.

Next generation sequencing technologies generate normous amount of short reads, which poses a significant computational challenge for short read alignment. Furthermore, because of sequence polymorphisms in a population, repetitive sequences, and sequencing errors, there still exist difficulties in correctly aligning all reads. We propose a space-efficient compressed suffix array-based method for short read alignment (CS2A) whose space achieves the high-order empirical entropy of the input string. Unlike BWA that uses two bits to represent a nucleotide, suitable for constant-sized alphabets, our encoding scheme can be applied to the string with any alphabet set. In addition, we present approximate pattern matching on compressed suffix array (CSA) for short read alignment. Our CS2A supports both mismatch and gapped alignments for single-end and paired-end reads mapping, being capable of efficiently aligning short sequencing reads to genome sequences. The experimental results show that CS2A can compete with the popular aligners in memory usage and mapping accuracy. The source code is available online.

Lifelong multitask learning is a multitask learning framework in which a learning agent faces the tasks that need to be learnt in an online manner. Lifelong multitask learning framework may be applied to a variety of applications such as image annotation, robotics, automated machines etc, and hence, may prove to be a highly promising direction for further investigation. However, the lifelong learning framework comes with its own baggage of challenges. The biggest challenge is the fact that the characteristics of the future tasks which might be encountered by the learning agents are entirely unknown. If all the tasks are assumed to be related, there may be a risk of training from unrelated task resulting in negative transfer of information. To overcome this problem, both batch and online multitask learning algorithms learn task relationships. However, due to the unknown nature of the future tasks, learning the task relationships is also difficult in lifelong multitask learning. In this paper, we propose learning functions to model the task relationships as it is computationally cheaper in an online setting. More specifically, we learn partition functions in the task space to divide the tasks into cluster. Our major contribution is to present a global formulation to learn both the task partitions and the parameters. We provide a supervised learning framework to estimate both the partition function and the model. The current method has been implemented and compared against other leading lifelong learning algorithms using several real world datasets, and we show that the current method has a superior performance.

In semi-supervised multi-view learning, unlabeled sample complexity (u.s.c.) specifies the size of unlabeled training sample that guarantees a desired learning error. In this paper, we improve the state-of-art u.s.c. from O(1/ε) to O(log 1/ε) for small error ε, under mild conditions. To obtain the improved result, as a primary step we prove a connection between the generalization error of a classifier and its incompatibility, which measures the fitness between the classifier and the sample distribution. We then prove that with a sufficiently large unlabeled sample, one is able to find classifiers with low incompatibility. Combining the two observations, we manage to prove a probably approximately correct (PAC) style learning bound for semi-supervised multi-view learning. We empirically verified our theory by designing two proof-of-concept multi-view learning algorithms, one based on active view sensing and the other based on online co-regularization, with real-world data sets.

With the development of information technology, online social networks grow dramatically. They now play a significant role in people's social life, especially for the younger generation. While huge amount of information is available in online social networks, privacy concerns arise. Among various privacy protection proposals, the notions of privacy as control and information boundary have been introduced. Commercial social networking sites have adopted the concept to implement mechanisms such as Google circles and Facebook custom lists. However, the functions are not widely accepted by the users, partly because it is tedious and labor-intensive to manually assign friends into circles.

Boosting is a highly effective algorithm that produces a linear combination of weak classifiers (a.k.a. base learners) to obtain high-quality classification models. In this article, we propose a generalized logit boost algorithm in which base learners have structural relationships in the functional space. Although such relationships are generic, our work is particularly motivated by the emerging topic of pattern-based classification for semistructured data including graphs. Toward an efficient incorporation of the structure information, we have designed a general model in which we use an undirected graph to capture the relationship of subgraph-based base learners. In our method, we employ bothL1and Laplacian-basedL2regularization to logit boosting to achieve model sparsity and smoothness in the functional space spanned by the base learners. We have derived efficient optimization algorithms based on coordinate descent for the new boosting formulation and theoretically prove that it exhibits a natural grouping effect for nearby spatial or overlapping base learners and that the resulting estimator is consistent. Additionally, motivated by the connection between logit boosting and logistic regression, we extend our structured sparse regularization framework to logistic regression for vectorial data in which features are structured. Using comprehensive experimental study and comparing our work with the state-of-the-art, we have demonstrated the effectiveness of the proposed learning method.

Data set curation in cheminformatics is largely ignored, and many publications do not provide the specific chemical structures used in their experiments. Access to chemical structures is vital for experiment reproducibility and comparison of competing methods. To address this limitation, the KU Chemical Biology Database (KUChemBio) has established a collection of 69 data sets for computational chemical biology experiments. Data sets fall into several categories including ADME, toxicity, binding affinity, solubility, melting points, and others. Chemical structures in SDF or Smiles format are provided along with binary or real valued activity labels. Data sets have been consolidated from other online repositories and content from recent publications has been added as well. KUChemBio is located at http://bcf.ku.edu/kuchembio.

Multitask learning has been thoroughly proven to improve the generalization performance given a set of related tasks. Most multitask learning algorithm assume that all tasks are related. However, if all the tasks are not related, negative transfer of information occurs amongst the tasks, and the performance of traditional multitask learning algorithm worsens. Thus, we design an algorithm that simultaneously groups the related tasks and trains only the related task together. There are different approaches to train the related tasks in multi-task learning based on which information is shared across the tasks. These approaches either assume that the parameters of each of the tasks are situated close together, or assume that there is a common underlying latent space in the features of the tasks that is related. Most multi-task learning algorithm use either regularization method or matrix-variate priors. In our algorithm, the related tasks are tied together by a set of common features selected by each tasks. Thus, to train the related tasks together, we use spike and slab prior to select a common set of features for the related tasks, and a mixture of gaussians prior to select the set of related tasks. For validation, the developed algorithm is tested on toxicity prediction and hand written digit recognition data sets. The results show a significant improvement over multitask learning with feature selection for larger number of tasks. Further, the developed algorithm is also compared against another state of the art algorithm that similarly groups the related tasks together and proven to be better and more accurate.

Determining anomalies in data streams that are collected and transformed from various types of networks has recently attracted significant research interest. Principal component analysis (PCA) has been extensively applied to detecting anomalies in network data streams. However, none of existing PCA-based approaches addresses the problem of identifying the sources that contribute most to the observed anomaly, or anomaly localization. In this paper, we propose novel sparse PCA methods to perform anomaly detection and localization for network data streams. Our key observation is that we can localize anomalies by identifying a sparse low-dimensional space that captures the abnormal events in data streams. To better capture the sources of anomalies, we incorporate the structure information of the network stream data in our anomaly localization framework. Furthermore, we extend our joint sparse PCA framework with multidimensional Karhunen Loève Expansion that considers both spatial and temporal domains of data streams to stabilize localization performance. We have performed comprehensive experimental studies of the proposed methods and have compared our methods with the state-of-the-art using three real-world data sets from different application domains. Our experimental studies demonstrate the utility of the proposed methods.

Non-stationary Dynamic Bayesian Networks (Non-stationary DBNs) are widely used to model the temporal changes of directed dependency structures from multivariate time series data. However, the existing change-points based non-stationary DBNs methods have several drawbacks including excessive computational cost, and low convergence speed. In this paper we proposed a novel non-stationary DBNs method. Our method is based on the perfect simulation model. We applied this approach for network structure inference from synthetic data and biological microarray gene expression data and compared it with other two state-of-the-art non-stationary DBNs methods. The experimental results demonstrated that our method outperformed two other state-of-the-art methods in both computational cost and structure prediction accuracy. The further sensitivity analysis showed that once converged our model is robust to large parameter ranges, which reduces the uncertainty of the model behavior.

Multi-view semi-supervised learning methods try to exploit the combination of multiple views along with large amounts of unlabeled data in order to learn better predictive functions when limited labeled data is available. However, lack of complete view data limits the applicability of multi-view semi-supervised learning to real world data. Commonly, one data view is readily and cheaply available, but additionally views may be costly or only available in some cases. This work aims to make multi-view semi-supervised learning approaches more applicable to real world data specifically by addressing the issue of missing views.

In many real-world applications, it is becoming common to have data extracted from multiple diverse sources, known as "multi-view" data. Multi-view learning (MVL) has been widely studied in many applications, but existing MVL methods learn a single task individually. In this paper, we study a new direction of multi-view learning where there are multiple related tasks with multi-view data (i.e. multi-view multi-task learning, or MVMT Learning). In our MVMT learning methods, we learn a linear mapping for each view in each task. In a single task, we use co-regularization to obtain functions that are in-agreement with each other on the unlabeled samples and achieve low classification errors on the labeled samples simultaneously. Cross different tasks, additional regularization functions are utilized to ensure the functions that we learn in each view are similar. We also developed two extensions of the MVMT learning algorithm. One extension handles missing views and the other handles non-uniformly related tasks. Experimental studies on three real-world data sets demonstrate that our MVMT methods significantly outperform the existing state-of-the-art methods.

Effectively utilizing readily available auxiliary data to improve predictive performance on new modeling tasks is a key problem in data mining. In this research, the goal is to transfer knowledge between sources of data, particularly when ground-truth information for the new modeling task is scarce or is expensive to collect where leveraging any auxiliary sources of data becomes a necessity. Toward seamless knowledge transfer among tasks, effective representation of the data is a critical but yet not fully explored research area for the data engineer and data miner. Here, we present a technique based on the idea of sparse coding, which essentially attempts to find an embedding for the data by assigning feature values based on subspace cluster membership. We modify the idea of sparse coding by focusing the identification of shared clusters between data when source and target data may have different distributions. In our paper, we point out cases where a direct application of sparse coding will lead to a failure of knowledge transfer. We then present the details of our extension to sparse coding, by incorporating distribution distance estimates for the embedded data, and show that the proposed algorithm can overcome the shortcomings of the sparse coding algorithm on synthetic data and achieve improved predictive performance on a real world chemical toxicity transfer learning task.

Information Flow Studies analyze the principles and mechanisms of social information distribution and is an essential research topic in social networks. Traditional approaches are primarily based on the social network graph topology. However, topology itself can not accurately reflect the user interests or activities. In this paper, we adopt a "microeconomics" approach to study social information diffusion and aim to answer the question that how social information flow and socialization behaviors are related to content similarity and user interests. In particular, we study content-based social activity prediction, i.e., to predict a user's response (e.g. comment or like) to their friends' postings (e.g. blogs) w.r.t. message content. In our solution, we cast the social behavior prediction problem as a multi-task learning problem, in which each task corresponds to a user. We have designed a novel multi-task learning algorithm that is specifically designed for learning information flow in social networks. In our model, we apply l1 and Tikhonov regularization to obtain a sparse and smooth model in a linear multi-task learning framework. Using comprehensive experimental study, we have demonstrated the effectiveness of the proposed learning method.

Effectively utilizing readily available auxiliary data to improve predictive performance on new modeling tasks is a key problem in data mining. In this research the goal is to transfer knowledge between sources of data, particularly when ground truth information for the new modeling task is scarce or is expensive to collect where leveraging any auxiliary sources of data becomes a necessity. Towards seamless knowledge transfer among tasks, effective representation of the data is a critical but yet not fully explored research area for the data engineer and data miner. Here we present a technique based on the idea of sparse coding, which essentially attempts to find an embedding for the data by assigning feature values based on subspace cluster membership. We modify the idea of sparse coding by focusing the identification of shared clusters between data when source and target data may have different distributions. In our paper, we point out cases where a direct application of sparse coding will lead to a failure of knowledge transfer. We then present the details of our extension to sparse coding, by incorporating distribution distance estimates for the embedded data, and show that the proposed algorithm can overcome the shortcomings of the sparse coding algorithm on synthetic data and achieve improved predictive performance on a real world chemical toxicity transfer learning task.

Multi-task Learning (MTL) aims to enhance the generalization performance of supervised regression or classification by learning multiple related tasks simultaneously. In this paper, we aim to extend the current MTL techniques to high dimensional data sets with structured input and structured output (SISO), where the SI means the input features are structured and the SO means the tasks are structured. We investigate a completely ignored problem in MTL with SISO data: the interaction of structured feature selection and task relationship modeling. We hypothesize that combining the structure information of features and task relationship inference enables us to build more accurate MTL models. Based on the hypothesis, we have designed an efficient learning algorithm, in which we utilize a task covariance matrix related to the model parameters to capture the task relationship. In addition, we design a regularization formulation for incorporating the structure of features in MTL. We have developed an efficient iterative optimization algorithm to solve the corresponding optimization problem. Our algorithm is based on the accelerated first order gradient method in conjunction with the projected gradient scheme. Using two real-world data sets, the experimental results demonstrate the utility of the proposed learning methods.

Determining anomalies in data streams that are collected and transformed from various types of networks has recently attracted significant research interest. Principal Component Analysis (PCA) has been extensively applied to detecting anomalies in network data streams. However, none of existing PCA based approaches addresses the problem of identifying the sources that contribute most to the observed anomaly, or anomaly localization. In this paper, we propose novel sparse PCA methods to perform anomaly detection and localization for network data streams. Our key observation is that we can localize anomalies by identifying a sparse low dimensional space that captures the abnormal events in data streams. To better capture the sources of anomalies, we incorporate the structure information of the network stream data in our anomaly localization framework. We have performed comprehensive experimental studies of the proposed methods, and have compared our methods with the state-ofthe-art using three real-world data sets from different application domains. Our experimental studies demonstrate the utility of the proposed methods.

In the standard formalization of supervised learning problems, a datum is represented as a vector of features without prior knowledge about relationships among features. However, for many real world problems, we have such prior knowledge about structure relationships among features. For instance, in Microarray analysis where the genes are features, the genes form biological pathways. Such prior knowledge should be incorporated to build a more accurate and interpretable model, especially in applications with high dimensionality and low sample sizes. Towards an efficient incorporation of the structure relationships, we have designed a classification model where we use an undirected graph to capture the relationship of features. In our method, we combine both L1 norm and Laplacian based L2 norm regularization with logistic regression. In this approach, we enforce model sparsity and smoothness among features to identify a small subset of grouped features. We have derived efficient optimization algorithms based on coordinate decent for the new formulation. Using comprehensive experimental study, we have demonstrated the effectiveness of the proposed learning methods.

In United State several universities and research institutes including the national health institute (NIH) recently started programs aiming for drug discovery. With the initiatives, huge volumes of data have been collected and shared with public free of charge. Those initiatives provide an unprecedented opportunity for data miner and machine learner to study knowledge discovery problems associated with drug design. In this tutorial, the presenter will review the knowledge discovery and management needs in the drug discovery process. Latest methodology development, primarily those from data mining, machine learning, and statistical learning will be discussed.

Boosting is a very successful classification algorithm that produces a linear combination of "weak" classifiers (a.k.a. base learners) to obtain high quality classification models. In this paper we propose a new boosting algorithm where base learners have structure relationships in the functional space. Though such relationships are generic, our work is particularly motivated by the emerging topic of pattern based classification for semi-structured data including graphs. Towards an efficient incorporation of the structure information, we have designed a general model where we use an undirected graph to capture the relationship of subgraph-based base learners. In our method, we combine both L1 norm and Laplacian based L2 norm penalty with Logit loss function of Logit Boost. In this approach, we enforce model sparsity and smoothness in the functional space spanned by the basis functions. We have derived efficient optimization algorithms based on coordinate decent for the new boosting formulation and theoretically prove that it exhibits a natural grouping effect for nearby spatial or overlapping features. Using comprehensive experimental study, we have demonstrated the effectiveness of the proposed learning methods.

Features in many real world applications such as Cheminformatics, Bioinformatics and Information Retrieval have complex internal structure. For example, frequent patterns mined from graph data are graphs. Such graph features have different number of nodes and edges and usually overlap with each other. In conventional data mining and machine learning applications, the internal structure of features are usually ignored. In this paper we consider a supervised learning problem where the features of the data set have intrinsic complexity, and we further assume that the feature intrinsic complexity may be measured by a kernel function. We hypothesize that by regularizing model parameters using the information of feature complexity, we can construct simple yet high quality model that captures the intrinsic structure of the data. Towards the end of testing this hypothesis, we focus on a regression task and have designed an algorithm that incorporate the feature complexity in the learning process, using a kernel matrix weighted L2 norm for regularization, to obtain improved regression performance over conventional learning methods that does not consider the additional information of the feature. We have tested our algorithm using 5 different real-world data sets and have demonstrate the effectiveness of our method.

Recently there has been increasing interest in the problem of transfer learning, in which the typical assumption that training and testing data are drawn from identical distributions is relaxed. We specifically address the problem of transductive transfer learning in which we have access to labeled training data and unlabeled testing data potentially drawn from different, yet related distributions, and the goal is to leverage the labeled training data to learn a classifier to correctly predict data from the testing distribution.

Structured data including sets, sequences, trees and graphs, pose significant challenges to fundamental aspects of data management such as efficient storage, indexing, and similarity search. With the fast accumulation of graph databases, similarity search in graph databases has emerged as an important research topic. Graph similarity search has applications in a wide range of domains including cheminformatics, bioinformatics, sensor network management, social network management, and XML documents, among others.Most of the current graph indexing methods focus on subgraph query processing, i.e. determining the set of database graphs that contains the query graph and hence do not directly support similarity search. In data mining and machine learning, various graph kernel functions have been designed to capture the intrinsic similarity of graphs. Though successful in constructing accurate predictive and classification models for supervised learning, graph kernel functions have (i) high computational complexity and (ii) non-trivial difficulty to be indexed in a graph database.Our objective is to bridge graph kernel function and similarity search in graph databases by proposing (i) a novel kernel-based similarity measurement and (ii) an efficient indexing structure for graph data management. Our method of similarity measurement builds upon local features extracted from each node and their neighboring nodes in graphs. A hash table is utilized to support efficient storage and fast search of the extracted local features. Using the hash table, a graph kernel function is defined to capture the intrinsic similarity of graphs and for fast similarity query processing. We have implemented our method, which we have named G-hash, and have demonstrated its utility on large chemical graph databases. Our results show that the G-hash method achieves state-of-the-art performance for k-nearest neighbor (k-NN) classification. Most importantly, the new similarity measurement and the index structure is scalable to large database with smaller indexing size, faster indexing construction time, and faster query processing time as compared to state-of-the-art indexing methods such as C-tree, gIndex, and GraphGrep.

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.

Data with intrinsic feature relationships are becoming abundant in many applications including bioinformatics and sensor network analysis. In this paper we consider a classification problem where there is a fixed and known binary relation defined on the features of a set of multivariate random variables. We formalize such a problem as an aligned graph classification problem. By incorporating this feature relationship in the learning process we aim to obtain improved classification performance over conventional learning that does not consider the additional information of the feature relationship. To incorporate the feature relationship, we extend logistic regression and use a regularization term that includes the normalized Laplacian of the graph, similar to the L2 regularization, deriving a modified optimization problem and solution. We demonstrate the effectiveness of our method and compare it to other methods using simulated and real data sets.

With the development of highly efficient graph data collection technology in many application fields, classification of graph data emerges as an important topic in the data mining and machine learning community. Towards building highly accurate classification models for graph data, here we present an efficient graph feature selection method. In our method, we use frequent subgraphs as features for graph classification. Different from existing methods, we consider the spatial distribution of the subgraph features in the graph data and select those ones that have consistent spatial location.

We introduce a novel method of indexing graph databases in order to facilitate subgraph isomorphism and similarity queries. The index is comprised of two major data structures. The primary structure is a directed acyclic graph which contains a node for each of the unique, induced subgraphs of the database graphs. The secondary structure is a hash table which cross-indexes each subgraph for fast isomorphic lookup. In order to create a hash key independent of isomorphism, we utilize a code-based canonical representation of adjacency matrices, which we have further refined to improve computation speed. We validate the concept by demonstrating its effectiveness in answering queries for two practical datasets. Our experiments show that for subgraph isomorphism queries, our method outperforms existing methods by more than an order of magnitude.

High throughput biotechnologies have enabled scientists to collect a large number of genetic and phenotypic attributes for a large collection of samples. Computationalmethods are in need to analyze these data for discovering genotype-phenotype associations and inferring possible phenotypes from genotypic attributes. In this paper, we study the problem of on demand phenotype ranking. Given a query sample, for which only its genetic information is available, we want to predict the possible phenotypes it may have, ranked in descending order of their likelihood. This problem is challenging since genotype-phenotype databases are updated often and explicitly mine and maintain all patterns is impractical. We propose an on-demand ranking algorithm that uses a modified pattern-based subspace clustering algorithm to effectively identify the subspaces where these relevant clusters may reside. Using this algorithm, we can compute the clusters and their prediction significance for any phenotypes on the fly. Our experiments demonstrate the efficiency and effectiveness of our algorithm.

We present a novel application of graph database mining to identify tertiary motifs in RNA structures. In our method, we abstract an RNA molecule as a labeled graph and use a frequent subgraph mining technique to derive tertiary motifs. By applying our technique to ribosome RNA and transfer RNA, we have identified known RNA tertiary motifs such as the ribose zipper and U-turn, plus candidates for novel tertiary motifs. Finally, we suggest an iterative multiple structure alignment algorithm to classify tertiary motifs and generate consensus motifs.

One fundamental challenge for mining recurring subgraphs from semi-structured data sets is the overwhelming abundance of such patterns. In large graph databases, the total number of frequent subgraphs can become too large to allow a full enumeration using reasonable computational resources. In this paper, we propose a new algorithm that mines only maximal frequent subgraphs, i.e. subgraphs that are not a part of any other frequent subgraphs. This may exponentially decrease the size of the output set in the best case; in our experiments on practical data sets, mining maximal frequent subgraphs reduces the total number of mined patterns by two to three orders of magnitude.Our method first mines all frequent trees from a general graph database and then reconstructs all maximal subgraphs from the mined trees. Using two chemical structure benchmarks and a set of synthetic graph data sets, we demonstrate that, in addition to decreasing the output size, our algorithm can achieve a five-fold speed up over the current state-of-the-art subgraph mining algorithms.

Frequent subgraph mining is an active research topic in the data mining community. A graph is a general model to represent data and has been used in many domains like cheminformatics and bioinformatics. Mining patterns from graph databases is challenging since graph related operations, such as subgraph testing, generally have higher time complexity than the corresponding operations on itemsets, sequences, and trees, which have been studied extensively. We propose a novel frequent subgraph mining algorithm: FFSM, which employs a vertical search scheme within an algebraic graph framework we have developed to reduce the number of redundant candidates proposed. Our empirical study on synthetic and real datasets demonstrates that FFSM achieves a substantial performance gain over the current start-of-the-art subgraph mining algorithm gSpan.