text: Deep learning models have achieved huge success in numerous fields, such as computer vision and natural language processing. However, unlike such fields, it is hard to apply traditional deep learning models on the graph data due to the node-orderless' property. Normally, we use an adjacent matrix to represent a graph, but an artificial and random node-order will be cast on the graphs, which renders the performance of deep models extremely erratic and not robust. In order to eliminate the unnecessary node-order constraint, in this paper, we propose a novel model named Isomorphic Neural Network (IsoNN), which learns the graph representation by extracting its isomorphic features via the graph matching between input graph and templates. IsoNN has two main components: graph isomorphic feature extraction component and classification component. The graph isomorphic feature extraction component utilizes a set of subgraph templates as the kernel variables to learn the possible subgraph patterns existing in the input graph and then computes the isomorphic features. A set of permutation matrices is used in the component to break the node-order brought by the matrix representation. To further lower down the computational cost and identify the optimal subgraph patterns, IsoNN adopts two min-pooling layers to find the optimal matching. The first min-pooling layer aims at finding the best permutation matrix, whereas the second one is used to determine the best templates for the input graph data. Three fully-connected layers are used as the classification component in IsoNN. Extensive experiments are conducted on real-world datasets, and the experimental results demonstrate both the effectiveness and efficiency of IsoNN.
  @cite_30: 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 φ-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., Alzheimers 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.
  @cite_33: 
  @cite_32: Recent studies have demonstrated that biomarkers from multiple modalities contain complementary information for the diagnosis of Alzheimer's disease AD and its prodromal stage mild cognitive impairment MCI. In order to fuse data from multiple modalities, most previous approaches calculate a mixed kernel or a similarity matrix by linearly combining kernels or similarities from multiple modalities. However, the complementary information from multi-modal data are not necessarily linearly related. In addition, this linear combination is also sensitive to the weights assigned to each modality. In this paper, we propose a nonlinear graph fusion method to efficiently exploit the complementarity in the multi-modal data for the classification of AD. Specifically, a graph is first constructed for each modality individually. Afterwards, a single unified graph is obtained via a nonlinear combination of the graphs in an iterative cross diffusion process. Using the unified graphs, we achieved classification accuracies of 91.8 between AD subjects and normal controls NC, 79.5 between MCI subjects and NC and 60.2 in a three-way classification, which are competitive with state-of-the-art results.
  @cite_24: 
  @cite_27: We present diffusion-convolutional neural networks (DCNNs), a new model for graph-structured data. Through the introduction of a diffusion-convolution operation, we show how diffusion-based representations can be learned from graph-structured data and used as an effective basis for node classification. DCNNs have several attractive qualities, including a latent representation for graphical data that is invariant under isomorphism, as well as polynomial-time prediction and learning that can be represented as tensor operations and efficiently implemented on a GPU. Through several experiments with real structured datasets, we demonstrate that DCNNs are able to outperform probabilistic relational models and kernel-on-graph methods at relational node classification tasks.
  @cite_2: 
  @cite_5: Graph classification is a problem with practical applications in many different domains. To solve this problem, one usually calculates certain graph statistics (i.e., graph features) that help discriminate between graphs of different classes. When calculating such features, most existing approaches process the entire graph. In a graphlet-based approach, for instance, the entire graph is processed to get the total count of different graphlets or subgraphs. In many real-world applications, however, graphs can be noisy with discriminative patterns confined to certain regions in the graph only. In this work, we study the problem of attention-based graph classification. The use of attention allows us to focus on small but informative parts of the graph, avoiding noise in the rest of the graph. We present a novel RNN model, called the Graph Attention Model (GAM), that processes only a portion of the graph by adaptively selecting a sequence of "informative" nodes. Experimental results on multiple real-world datasets show that the proposed method is competitive against various well-known methods in graph classification even though our method is limited to only a portion of the graph.
  @cite_31: 
  @cite_16: Graph mining methods enumerate frequently appearing subgraph patterns, which can be used as features for subsequent classification or regression. However, frequent patterns are not necessarily informative for the given learning problem. We propose a mathematical programming boosting method (gBoost) that progressively collects informative patterns. Compared to AdaBoost, gBoost can build the prediction rule with fewer iterations. To apply the boosting method to graph data, a branch-and-bound pattern search algorithm is developed based on the DFS code tree. The constructed search space is reused in later iterations to minimize the computation time. Our method can learn more efficiently than the simpler method based on frequent substructure mining, because the output labels are used as an extra information source for pruning the search space. Furthermore, by engineering the mathematical program, a wide range of machine learning problems can be solved without modifying the pattern search algorithm.
summary: Graph classification is an important problem with many practical applications. Data like social networks, chemical compounds, brain networks can be represented as graphs naturally and they can have applications such as community detection @cite_31 , anti-cancer activity identification @cite_30 @cite_2 and Alzheimer's patients diagnosis @cite_32 @cite_33 respectively. Traditionally, researchers mine the subgraphs by DFS or BFS @cite_16 @cite_24 , and use them as the features. With the rapid development of deep learning (DL), many works are done based on DL methods. GAM builds the model by RNN with self-attention mechanism @cite_5 . DCNN extend CNN to general graph-structured data by introducing a ‘diffusion-convolution’ operation @cite_27 .