A review of heterogeneous data mining for brain disorder identification <s> Subgraph pattern mining <s> This paper proposes a novel approach named AGM to efficiently mine the association rules among the frequently appearing substructures in a given graph data set. A graph transaction is represented by an adjacency matrix, and the frequent patterns appearing in the matrices are mined through the extended algorithm of the basket analysis. Its performance has been evaluated for the artificial simulation data and the carcinogenesis data of Oxford University and NTP. Its high efficiency has been confirmed for the size of a real-world problem. <s> BIB001 </s> A review of heterogeneous data mining for brain disorder identification <s> Subgraph pattern mining <s> As data mining techniques are being increasingly applied to non-traditional domains, existing approaches for finding frequent itemsets cannot be used as they cannot model the requirement of these domains. An alternate way of modeling the objects in these data sets is to use graphs. Within that model, the problem of finding frequent patterns becomes that of discovering subgraphs that occur frequently over the entire set of graphs.The authors present a computationally efficient algorithm for finding all frequent subgraphs in large graph databases. We evaluated the performance of the algorithm by experiments with synthetic datasets as well as a chemical compound dataset. The empirical results show that our algorithm scales linearly with the number of input transactions and it is able to discover frequent subgraphs from a set of graph transactions reasonably fast, even though we have to deal with computationally hard problems such as canonical labeling of graphs and subgraph isomorphism which are not necessary for traditional frequent itemset discovery. <s> BIB002 </s> A review of heterogeneous data mining for brain disorder identification <s> Subgraph pattern mining <s> We investigate new approaches for frequent graph-based pattern mining in graph datasets and propose a novel algorithm called gSpan (graph-based substructure pattern mining), which discovers frequent substructures without candidate generation. gSpan builds a new lexicographic order among graphs, and maps each graph to a unique minimum DFS code as its canonical label. Based on this lexicographic order gSpan adopts the depth-first search strategy to mine frequent connected subgraphs efficiently. Our performance study shows that gSpan substantially outperforms previous algorithms, sometimes by an order of magnitude. <s> BIB003 </s> A review of heterogeneous data mining for brain disorder identification <s> Subgraph pattern mining <s> We present an algorithm to find fragments in a set of molecules that help to discriminate between different classes of for instance, activity in a drug discovery context. Instead of carrying out a brute-force search, our method generates fragments by embedding them in all appropriate molecules in parallel and prunes the search tree based on a local order of the atoms and bonds, which results in substantially faster search by eliminating the need for frequent, computationally expensive reembeddings and by suppressing redundant search. We prove the usefulness of our algorithm by demonstrating the discovery of activity-related groups of chemical compounds in the well-known National Cancer Institute's HIV-screening dataset. <s> BIB004 </s> A review of heterogeneous data mining for brain disorder identification <s> Subgraph pattern mining <s> 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. <s> BIB005 </s> A review of heterogeneous data mining for brain disorder identification <s> Subgraph pattern mining <s> Given a database, structure mining algorithms search for substructures that satisfy constraints such as minimum frequency, minimum confidence, minimum interest and maximum frequency. Examples of substructures include graphs, trees and paths. For these substructures many mining algorithms have been proposed. In order to make graph mining more efficient, we investigate the use of the "quickstart principle", which is based on the fact that these classes of structures are contained in each other, thus allowing for the development of structure mining algorithms that split the search into steps of increasing complexity. We introduce the GrAph/Sequence/Tree extractiON ( Gaston ) algorithm that implements this idea by searching first for frequent paths, then frequent free trees and finally cyclic graphs. We investigate two alternatives for computing the frequency of structures and present experimental results to relate these alternatives. <s> BIB006 </s> A review of heterogeneous data mining for brain disorder identification <s> Subgraph pattern mining <s> With ever-increasing amounts of graph data from disparate sources, there has been a strong need for exploiting significant graph patterns with user-specified objective functions. Most objective functions are not antimonotonic, which could fail all of frequency-centric graph mining algorithms. In this paper, we give the first comprehensive study on general mining method aiming to find most significant patterns directly. Our new mining framework, called LEAP (Descending Leap Mine), is developed to exploit the correlation between structural similarity and significance similarity in a way that the most significant pattern could be identified quickly by searching dissimilar graph patterns. Two novel concepts, structural leap search and frequency descending mining, are proposed to support leap search in graph pattern space. Our new mining method revealed that the widely adopted branch-and-bound search in data mining literature is indeed not the best, thus sketching a new picture on scalable graph pattern discovery. Empirical results show that LEAP achieves orders of magnitude speedup in comparison with the state-of-the-art method. Furthermore, graph classifiers built on mined patterns outperform the up-to-date graph kernel method in terms of efficiency and accuracy, demonstrating the high promise of such patterns. <s> BIB007 </s> A review of heterogeneous data mining for brain disorder identification <s> Subgraph pattern mining <s> Bug localization has attracted a lot of attention recently. Most existing methods focus on pinpointing a single statement or function call which is very likely to contain bugs. Although such methods could be very accurate, it is usually very hard for developers to understand the context of the bug, given each bug location in isolation. In this study, we propose to model software executions with graphs at two levels of granularity: methods and basic blocks. An individual node represents a method or basic block and an edge represents a method call, method return or transition (at the method or basic block granularity). Given a set of graphs of correct and faulty executions, we propose to extract the most discriminative subgraphs which contrast the program flow of correct and faulty executions. The extracted subgraphs not only pinpoint the bug, but also provide an informative context for understanding and fixing the bug. Different from traditional graph mining which mines a very large set of frequent subgraphs, we formulate subgraph mining as an optimization problem and directly generate the most discriminative subgraph with a recently proposed graph mining algorithm LEAP. We further extend it to generate a ranked list of top-k discriminative subgraphs representing distinct locations which may contain bugs. Experimental results and case studies show that our proposed method is both effective and efficient to mine discriminative subgraphs for bug localization and context identification. <s> BIB008 </s> A review of heterogeneous data mining for brain disorder identification <s> Subgraph pattern mining <s> Graph classification is an increasingly important step in numerous application domains, such as function prediction of molecules and proteins, computerised scene analysis, and anomaly detection in program flows. Among the various approaches proposed in the literature, graph classification based on frequent subgraphs is a popular branch: Graphs are represented as (usually binary) vectors, with components indicating whether a graph contains a particular subgraph that is frequent across the dataset. On large graphs, however, one faces the enormous problem that the number of these frequent subgraphs may grow exponentially with the size of the graphs, but only few of them possess enough discriminative power to make them useful for graph classification. Efficient and discriminative feature selection among frequent subgraphs is hence a key challenge for graph mining. In this article, we propose an approach to feature selection on frequent subgraphs, called CORK, that combines two central advantages. First, it optimizes a submodular quality criterion, which means that we can yield a near-optimal solution using greedy feature selection. Second, our submodular quality function criterion can be integrated into gSpan, the state-of-the-art tool for frequent subgraph mining, and help to prune the search space for discriminative frequent subgraphs even during frequent subgraph mining. <s> BIB009 </s> A review of heterogeneous data mining for brain disorder identification <s> Subgraph pattern mining <s> Graphs are being increasingly used to model a wide range of scientific data. Such widespread usage of graphs has generated considerable interest in mining patterns from graph databases. While an array of techniques exists to mine frequent patterns, we still lack a scalable approach to mine statistically significant patterns, specifically patterns with low p-values, that occur at low frequencies. We propose a highly scalable technique, called GraphSig, to mine significant subgraphs from large graph databases. We convert each graph into a set of feature vectors where each vector represents a region within the graph. Domain knowledge is used to select a meaningful feature set. Prior probabilities of features are computed empirically to evaluate statistical significance of patterns in the feature space. Following analysis in the feature space, only a small portion of the exponential search space is accessed for further analysis. This enables the use of existing frequent subgraph mining techniques to mine significant patterns in a scalable manner even when they are infrequent. Extensive experiments are carried out on the proposed techniques, and empirical results demonstrate that GraphSig is effective and efficient for mining significant patterns. To further demonstrate the power of significant patterns, we develop a classifier using patterns mined by GraphSig. Experimental results show that the proposed classifier achieves superior performance, both in terms of quality and computation cost, over state-of-the-art classifiers. <s> BIB010 </s> A review of heterogeneous data mining for brain disorder identification <s> Subgraph pattern mining <s> Subgraph patterns are widely used in graph classification, but their effectiveness is often hampered by large number of patterns or lack of discrimination power among individual patterns. We introduce a novel classification method based on pattern co-occurrence to derive graph classification rules. Our method employs a pattern exploration order such that the complementary discriminative patterns are examined first. Patterns are grouped into co-occurrence rules during the pattern exploration, leading to an integrated process of pattern mining and classifier learning. By taking advantage of co-occurrence information, our method can generate strong features by assembling weak features. Unlike previous methods that invoke the pattern mining process repeatedly, our method only performs pattern mining once. In addition, our method produces a more interpretable classifier and shows better or competitive classification effectiveness in terms of accuracy and execution time. <s> BIB011 </s> A review of heterogeneous data mining for brain disorder identification <s> Subgraph pattern mining <s> Discriminative subgraphs are widely used to define the feature space for graph classification in large graph databases. Several scalable approaches have been proposed to mine discriminative subgraphs. However, their intensive computation needs prevent them from mining large databases. We propose an efficient method GAIA for mining discriminative subgraphs for graph classification in large databases. Our method employs a novel subgraph encoding approach to support an arbitrary subgraph pattern exploration order and explores the subgraph pattern space in a process resembling biological evolution. In this manner, GAIA is able to find discriminative subgraph patterns much faster than other algorithms. Additionally, we take advantage of parallel computing to further improve the quality of resulting patterns. In the end, we employ sequential coverage to generate association rules as graph classifiers using patterns mined by GAIA. Extensive experiments have been performed to analyze the performance of GAIA and to compare it with two other state-of-the-art approaches. GAIA outperforms the other approaches both in terms of classification accuracy and runtime efficiency. <s> BIB012 </s> A review of heterogeneous data mining for brain disorder identification <s> Subgraph pattern mining <s> A graph models complex structural relationships among objects, and has been prevalently used in a wide range of applications. Building an automated graph classification model becomes very important for predicting unknown graphs or understanding complex structures between different classes. The graph classification framework being widely used consists of two steps, namely, feature selection and classification. The key issue is how to select important subgraph features from a graph database with a large number of graphs including positive graphs and negative graphs. Given the features selected, a generic classification approach can be used to build a classification model. In this paper, we focus on feature selection. We identify two main issues with the most widely used feature selection approach which is based on a discriminative score to select frequent subgraph features, and introduce a new diversified discriminative score to select features that have a higher diversity. We analyze the properties of the newly proposed diversified discriminative score, and conducted extensive performance studies to demonstrate that such a diversified discriminative score makes positive/negative graphs separable and leads to a higher classification accuracy. <s> BIB013 </s> A review of heterogeneous data mining for brain disorder identification <s> Subgraph pattern mining <s> Mining discriminative features for graph data has attracted much attention in recent years due to its important role in constructing graph classifiers, generating graph indices, etc. Most measurement of interestingness of discriminative subgraph features are defined on certain graphs, where the structure of graph objects are certain, and the binary edges within each graph represent the "presence" of linkages among the nodes. In many real-world applications, however, the linkage structure of the graphs is inherently uncertain. Therefore, existing measurements of interestingness based upon certain graphs are unable to capture the structural uncertainty in these applications effectively. In this paper, we study the problem of discriminative subgraph feature selection from uncertain graphs. This problem is challenging and different from conventional subgraph mining problems because both the structure of the graph objects and the discrimination score of each subgraph feature are uncertain. To address these challenges, we propose a novel discriminative subgraph feature selection method, DUG, which can find discriminative subgraph features in uncertain graphs based upon different statistical measures including expectation, median, mode and phi-probability. We first compute the probability distribution of the discrimination scores for each subgraph feature based on dynamic programming. Then a branch-and-bound algorithm is proposed to search for discriminative subgraphs efficiently. Extensive experiments on various neuroimaging applications (i.e., Alzheimer's Disease, ADHD and HIV) have been performed to analyze the gain in performance by taking into account structural uncertainties in identifying discriminative subgraph features for graph classification. <s> BIB014 </s> A review of heterogeneous data mining for brain disorder identification <s> Subgraph pattern mining <s> Following the recent advances in neuroimaging technology, the research on brain network analysis becomes an emerging area in data mining community. Brain network data pose many unique challenges for data mining research. For example, in brain networks, the nodes (i.e., the brain regions) and edges (i.e., relationships between brain regions) are usually not given, but should be derived from the neuroimaging data. The network structure can be very noisy and uncertain. Therefore, innovative methods are required for brain network analysis. Many research efforts have been devoted to this area. They have achieved great success in various applications, such as brain network extraction, graph mining, neuroimaging data analysis. In this paper, we review some recent data mining methods which are used in the literature for mining brain network data. <s> BIB015 </s> A review of heterogeneous data mining for brain disorder identification <s> Subgraph pattern mining <s> Using sophisticated graph-theoretical analyses, modern magnetic resonance imaging techniques have allowed us to model the human brain as a brain connectivity network or a graph. In a brain network, the nodes of the network correspond to a set of brain regions and the link or edges correspond to the functional or structural connectivity between these regions. The linkage structure in brain networks can encode valuable information about the organizational properties of the human brain as a whole. However, the complexity of such linkage information raises major challenges in the era of big data in brain informatics. Conventional approaches on brain networks primarily focus on local patterns within select brain regions or pairwise connectivity between regions. By contrast, in this study, we proposed a graph mining framework based on state-of-the-art data mining techniques. Using a statistical test based on the G-test, we validated this framework in a sample of euthymic bipolar I subjects, and identified abnormal subgraph patterns in the rsfMRI networks of these subjects relative to healthy controls. <s> BIB016 </s> A review of heterogeneous data mining for brain disorder identification <s> Subgraph pattern mining <s> Mining discriminative subgraph patterns from graph data has attracted great interest in recent years. It has a wide variety of applications in disease diagnosis, neuroimaging, etc. Most research on subgraph mining focuses on the graph representation alone. However, in many real-world applications, the side information is available along with the graph data. For example, for neurological disorder identification, in addition to the brain networks derived from neuroimaging data, hundreds of clinical, immunologic, serologic and cognitive measures may also be documented for each subject. These measures compose multiple side views encoding a tremendous amount of supplemental information for diagnostic purposes, yet are often ignored. In this paper, we study the problem of discriminative subgraph selection using multiple side views and propose a novel solution to find an optimal set of subgraph features for graph classification by exploring a plurality of side views. We derive a feature evaluation criterion, named gSide, to estimate the usefulness of subgraph patterns based upon side views. Then we develop a branch-and-bound algorithm, called gMSV, to efficiently search for optimal subgraph features by integrating the subgraph mining process and the procedure of discriminative feature selection. Empirical studies on graph classification tasks for neurological disorders using brain networks demonstrate that subgraph patterns selected by the multi-side-view guided subgraph selection approach can effectively boost graph classification performances and are relevant to disease diagnosis. <s> BIB017
In brain network analysis, the ideal patterns we want to mine from the data should take care of both local and global graph topological information. Graph kernel methods seem promising, which, however, are not interpretable. Subgraph patterns are more suitable for brain networks, which can simultaneously model the network connectivity patterns around the nodes and capture the changes in local area BIB015 . A subgraph pattern, in a brain network, represents a collection of brain regions and their connections. For example, as shown in Fig. 2 , three brain regions should work collaboratively for normal people and the absence of any connection between them can result in Alzheimer's disease in different degrees. Therefore, it is valuable to understand which connections collectively play a significant role in disease mechanism by finding discriminative subgraph patterns in brain networks. Mining subgraph patterns from graph data has been extensively studied by many researchers BIB012 BIB008 BIB009 BIB007 . In general, a variety of filtering criteria are proposed. A typical evaluation criterion is frequency, which aims at searching for frequently appearing subgraph features in a graph dataset satisfying a prespecified threshold. Most of the frequent subgraph mining approaches are unsupervised. For example, Yan and Han develop a depth-first search algorithm: gSpan BIB003 . This algorithm builds a lexicographic order among graphs, and maps each graph to a unique minimum DFS code as its canonical label. Based on this lexicographic order, gSpan adopts the depth-first search strategy to mine frequent connected subgraphs efficiently. Many other approaches for frequent subgraph mining have also been proposed, e.g., AGM BIB001 , FSG BIB002 , MoFa BIB004 , FFSM BIB005 , and Gaston BIB006 . Moreover, the problem of supervised subgraph mining has been studied in recent work which examines how to improve the efficiency of searching the discriminative subgraph patterns for graph classification. Yan et al. introduce two concepts structural leap search and frequency-descending mining, and propose LEAP BIB007 which is one of the first work in discriminative subgraph mining. Thoma et al. propose CORK which can yield a near-optimal solution using greedy feature selection BIB009 . Ranu and Singh propose a scalable approach, called GraphSig, that is capable of mining discriminative subgraphs with a lowfrequency threshold BIB010 . Jin et al. propose COM which takes into account the co-occurrences of subgraph patterns, thereby facilitating the mining process BIB011 . Jin et al. further propose an evolutionary computation method, called GAIA, to mine discriminative subgraph patterns using a randomized searching strategy BIB012 . Zhu et al. design a diversified discrimination score based on the log ratio which can reduce the overlap between selected features by considering the embedding overlaps in the graphs BIB013 . Conventional graph mining approaches are best suited for binary edges, where the structure of graph objects is deterministic, and the binary edges represent the presence of linkages between the nodes BIB015 . In fMRI brain network data, however, there are inherently weighted edges in the graph linkage structure, as shown in Fig. 3 (left) . A straightforward solution is to threshold weighted networks to yield binary networks. However, such simplification will result in great loss of information. Ideal data mining methods for brain network analysis should be able to overcome these methodological problems by generalizing the network edges to positive and negative weighted cases, e.g., probabilistic weights in fMRI brain networks and integral weights in DTI brain networks. Definition 5 A weighted graph is represented as e G ¼ ðV; E; pÞ, where V ¼ fv 1 ; . . .; v n v g is the set of vertices, and E V Â V is the set of nondeterministic edges. p : E ! ð0; 1 is a function that assigns a probability of existence to each edge in E. fMRI brain networks can be modeled as weighted graphs where each edge e 2 E is associated with a probability p(e) indicating the likelihood of whether this edge should exist or not BIB016 BIB014 . It is assumed that p(e) of different edges in a weighted graph are independent from each other. Therefore, by enumerating the possible existence of all edges in a weighted graph, we can obtain a set of binary graphs. For example, in Fig. 3 (right) , consider the three red nodes and links between them as a weighted graph. There are 2 3 ¼ 8 binary graphs that can be implied with different probabilities. For a weighted graph e G, the probability of e G containing a subgraph feature G 0 is defined as the probability that a binary graph G implied by e G contains subgraph G 0 . Kong et al. propose a discriminative subgraph feature selection method based on dynamic programming to compute the probability distribution of the discrimination scores for each subgraph pattern within a set of weighted graphs BIB014 . For brain network analysis, usually we only have a small number of graph instances BIB014 . In these applications, the graph view alone is not sufficient for mining important subgraphs. Fortunately, the side information is available along with the graph data for brain disorder identification. For example, in neurological studies, hundreds of clinical, immunologic, serologic, and cognitive measures may be available for each subject, apart from brain networks. These measures compose multiple side views which contain a tremendous amount of supplemental information for diagnostic purposes. It is desirable to extract valuable information from a plurality of side views to guide the process of subgraph mining in brain networks. A discriminative subgraph pattern effective algorithm for discriminative subgraph selection using multiple side views as guidance BIB017 . Side information consistency is first validated via statistical hypothesis testing which suggests that the similarity of side view features between instances with the same label should have higher probability to be larger than that with different labels. Based on such observations, it is assumed that the similarity/distance between instances in the space of subgraph features should be consistent with that in the space of a side view. That is to say, if two instances are similar in the space of a side view, they should also be close to each other in the space of subgraph features. Therefore the target is to minimize the distance between subgraph features of each pair of similar instances in each side view BIB017 . In contrast to existing subgraph mining approaches that focus on the graph view alone, the proposed method can explore multiple vector-based side views to find an optimal set of subgraph features for graph classification. For graph classification, brain network analysis approaches can generally be put into three groups: (1) extracting some local measures (e.g., clustering coefficient) to train a standard vector-based classifier; (2) directly adopting graph kernels for classification; and (3) finding discriminative subgraph patterns. Different types of methods model the connectivity embedded in brain networks in different ways.