Spectral Clustering Community Detection Algorithm Based on Point-Wise Mutual Information Graph Kernel.

To address the problem that traditional spectral clustering algorithms cannot obtain the complete structural information of networks, this paper proposes a spectral clustering community detection algorithm, PMIK-SC, based on the point-wise mutual information (PMI) graph kernel. The kernel is constructed according to the point-wise mutual information between nodes, which is then used as a proximity matrix to reconstruct the network and obtain the symmetric normalized Laplacian matrix. Finally, the network is partitioned by the eigendecomposition and eigenvector clustering of the Laplacian matrix. In addition, to determine the number of clusters during spectral clustering, this paper proposes a fast algorithm, BI-CNE, for estimating the number of communities. For a specific network, the algorithm first reconstructs the original network and then runs Monte Carlo sampling to estimate the number of communities by Bayesian inference. Experimental results show that the detection speed and accuracy of the algorithm are superior to other existing algorithms for estimating the number of communities. On this basis, the spectral clustering community detection algorithm PMIK-SC also has high accuracy and stability compared with other community detection algorithms and spectral clustering algorithms.

Hybrid localized graph kernel for machine learning energy-related properties of molecules and solids.

Nowadays, the coupling of electronic structure and machine learning techniques serves as a powerful tool to predict chemical and physical properties of a broad range of systems. With the aim of improving the accuracy of predictions, a large number of representations for molecules and solids for machine learning applications has been developed. In this work we propose a novel descriptor based on the notion of molecular graph. While graphs are largely employed in classification problems in cheminformatics or bioinformatics, they are not often used in regression problem, especially of energy-related properties. Our method is based on a local decomposition of atomic environments and on the hybridization of two kernel functions: a graph kernel contribution that describes the chemical pattern and a Coulomb label contribution that encodes finer details of the local geometry. The accuracy of this new kernel method in energy predictions of molecular and condensed phase systems is demonstrated by considering the popular QM7 and BA10 datasets. These examples show that the hybrid localized graph kernel outperforms traditional approaches such as, for example, the smooth overlap of atomic positions and the Coulomb matrices.

A Comprehensive Evaluation of Graph Kernels for Unattributed Graphs.

Graph kernels are of vital importance in the field of graph comparison and classification. However, how to compare and evaluate graph kernels and how to choose an optimal kernel for a practical classification problem remain open problems. In this paper, a comprehensive evaluation framework of graph kernels is proposed for unattributed graph classification. According to the kernel design methods, the whole graph kernel family can be categorized in five different dimensions, and then several representative graph kernels are chosen from these categories to perform the evaluation. With plenty of real-world and synthetic datasets, kernels are compared by many criteria such as classification accuracy, F1 score, runtime cost, scalability and applicability. Finally, quantitative conclusions are discussed based on the analyses of the extensive experimental results. The main contribution of this paper is that a comprehensive evaluation framework of graph kernels is proposed, which is significant for graph-classification applications and the future kernel research.

Enhancing Team Composition in Professional Networks: Problem Definitions and Fast Solutions.

In this paper, we study ways to enhance the composition of teams based on new requirements in a collaborative environment. We focus on recommending team members who can maintain the team's performance by minimizing changes to the team's skills and social structure. Our recommendations are based on computing team-level similarity, which includes skill similarity, structural similarity as well as the synergy between the two. Current heuristic approaches are one-dimensional and not comprehensive, as they consider the two aspects independently. To formalize team-level similarity, we adopt the notion of graph kernel of attributed graphs to encompass the two aspects and their interaction. To tackle the computational challenges, we propose a family of fast algorithms by (a) designing effective pruning strategies, and (b) exploring the smoothness between the existing and the new team structures. Extensive empirical evaluations on real world datasets validate the effectiveness and efficiency of our algorithms.

A graph kernel based on context vectors for extracting drug-drug interactions.

The clinical recognition of drug-drug interactions (DDIs) is a crucial issue for both patient safety and health care cost control. Thus there is an urgent need that DDIs be extracted automatically from biomedical literature by text-mining techniques. Although the top-ranking DDIs systems explore various features of texts, these features can't yet adequately express long and complicated sentences. In this paper, we present an effective graph kernel which makes full use of different types of contexts to identify DDIs from biomedical literature. In our approach, the relations among long-range words, in addition to close-range words, are obtained by the graph representation of a parsed sentence. Context vectors of a vertex, an iterative vectorial representation of all labeled nodes adjacent and nonadjacent to it, adequately capture the direct and indirect substructures' information. Furthermore, the graph kernel considering the distance between context vectors is used to detect DDIs. Experimental results on the DDIExtraction 2013 corpus show that our system achieves the best detection and classification performance (F-score) of DDIs (81.8 and 68.4, respectively). Especially for the Medline-2013 dataset, our system outperforms the top-ranking DDIs systems by F-scores of 10.7 and 12.2 in detection and classification, respectively.

Topological graph kernel on multiple thresholded functional connectivity networks for mild cognitive impairment classification.

Recently, brain connectivity networks have been used for classification of Alzheimer's disease and mild cognitive impairment (MCI) from normal controls (NC). In typical connectivity-networks-based classification approaches, local measures of connectivity networks are first extracted from each region-of-interest as network features, which are then concatenated into a vector for subsequent feature selection and classification. However, some useful structural information of network, especially global topological information, may be lost in this type of approaches. To address this issue, in this article, we propose a connectivity-networks-based classification framework to identify accurately the MCI patients from NC. The core of the proposed method involves the use of a new graph-kernel-based approach to measure directly the topological similarity between connectivity networks. We evaluate our method on functional connectivity networks of 12 MCI and 25 NC subjects. The experimental results show that our proposed method achieves a classification accuracy of 91.9%, a sensitivity of 100.0%, a balanced accuracy of 94.0%, and an area under receiver operating characteristic curve of 0.94, demonstrating a great potential in MCI classification, based on connectivity networks. Further connectivity analysis indicates that the connectivity of the selected brain regions is different between MCI patients and NC, that is, MCI patients show reduced functional connectivity compared with NC, in line with the findings reported in the existing studies.

Graph kernel of brain networks considering functional similarity measures.

As a tool of brain network analysis, the graph kernel is often used to assist the diagnosis of neurodegenerative diseases. It is used to judge whether the subject is sick by measuring the similarity between brain networks. Most of the existing graph kernels calculate the similarity of brain networks based on structural similarity, which can better capture the topology of brain networks, but all ignore the functional information including the lobe, centers, left and right brain to which the brain region belongs and functions of brain regions in brain networks. The functional similarities can help more accurately locate the specific brain regions affected by diseases so that we can focus on measuring the similarity of brain networks. Therefore, a multi-attribute graph kernel for the brain network is proposed, which assigns multiple attributes to nodes in the brain network, and computes the graph kernel of the brain network according to Weisfeiler-Lehman color refinement algorithm. In addition, in order to capture the interaction between multiple brain regions, a multi-attribute hypergraph kernel is proposed, which takes into account the functional and structural similarities as well as the higher-order correlation between the nodes of the brain network. Finally, the experiments are conducted on real data sets and the experimental results show that the proposed methods can significantly improve the performance of neurodegenerative disease diagnosis. Besides, the statistical test shows that the proposed methods are significantly different from compared methods.

Biomedical literature mining: graph kernel-based learning for gene-gene interaction extraction.

The supervised machine learning method is often used for biomedical relationship extraction. The disadvantage is that it requires much time and money to manually establish an annotated dataset. Based on distant supervision, the knowledge base is combined with the corpus, thus, the training corpus can be automatically annotated. As many biomedical databases provide knowledge bases for study with a limited number of annotated corpora, this method is practical in biomedicine. The clinical significance of each patient's genetic makeup can be understood based on the healthcare provider's genetic database. Unfortunately, the lack of previous biomedical relationship extraction studies focuses on gene-gene interaction. The main purpose of this study is to develop extraction methods for gene-gene interactions that can help explain the heritability of human complex diseases. This study referred to the information on gene-gene interactions in the KEGG PATHWAY database, the abstracts in PubMed were adopted to generate the training sample set, and the graph kernel method was adopted to extract gene-gene interactions. The best assessment result was an F1-score of 0.79. Our developed distant supervision method automatically finds sentences through the corpus without manual labeling for extracting gene-gene interactions, which can effectively reduce the time cost for manual annotation data; moreover, the relationship extraction method based on a graph kernel can be successfully applied to extract gene-gene interactions. In this way, the results of this study are expected to help achieve precision medicine.

Bi-level Graph Learning Unveils Prognosis-Relevant Tumor Microenvironment Patterns from Breast Multiplexed Digital Pathology.

The tumor microenvironment is widely recognized for its central role in driving cancer progression and influencing prognostic outcomes. Despite extensive research efforts dedicated to characterizing this complex and heterogeneous environment, considerable challenges persist. In this study, we introduce a data-driven approach for identifying patterns of cell organizations in the tumor microenvironment that are associated with patient prognoses. Our methodology relies on the construction of a bi-level graph model: (i) a cellular graph, which models the intricate tumor microenvironment, and (ii) a population graph that captures inter-patient similarities, given their respective cellular graphs, by means of a soft Weisfeiler-Lehman subtree kernel. This systematic integration of information across different scales enables us to identify patient subgroups exhibiting unique prognoses while unveiling tumor microenvironment patterns that characterize them. We demonstrate our approach in a cohort of breast cancer patients, where the identified tumor microenvironment patterns result in a risk stratification system that provides complementary, new information with respect to alternative standards. Our results, which are validated in a completely independent cohort, allow for new insights into the prognostic implications of the breast tumor microenvironment, and this methodology could be applied to other cancer types more generally.

PyGTED: Python Application for Computing Graph Traversal Edit Distance.

Graph Traversal Edit Distance (GTED) is a measure of distance (or dissimilarity) between two graphs introduced. This measure is based on the minimum edit distance between two strings formed by the edge labels of respective Eulerian traversals of the two graphs. GTED was motivated by and provides the first mathematical formalism for sequence coassembly and de novo variation detection in bioinformatics. Many problems in applied machine learning deal with graphs (also called networks), including social networks, security, web data mining, protein function prediction, and genome informatics. The kernel paradigm beautifully decouples the learning algorithm from the underlying geometric space, which renders graph kernels important for the aforementioned applications. In this article, we introduce a tool, PyGTED to compute GTED. It implements the algorithm based on the polynomial time algorithm devised for it by the authors. Informally, the GTED is the minimum edit distance between two strings formed by the edge labels of respective Eulerian traversals of the two graphs.

Graph Traversal Edit Distance and Extensions.

Many problems in applied machine learning deal with graphs (also called networks), including social networks, security, web data mining, protein function prediction, and genome informatics. The kernel paradigm beautifully decouples the learning algorithm from the underlying geometric space, which renders graph kernels important for the aforementioned applications. In this article, we give a new graph kernel, which we call graph traversal edit distance (GTED). We introduce the GTED problem and give the first polynomial time algorithm for it. Informally, the GTED is the minimum edit distance between two strings formed by the edge labels of respective Eulerian traversals of the two graphs. Also, GTED is motivated by and provides the first mathematical formalism for sequence co-assembly and de novo variation detection in bioinformatics. We demonstrate that GTED admits a polynomial time algorithm using a linear program in the graph product space that is guaranteed to yield an integer solution. To the best of our knowledge, this is the first approach to this problem. We also give a linear programming relaxation algorithm for a lower bound on GTED. We use GTED as a graph kernel and evaluate it by computing the accuracy of a support vector machine (SVM) classifier on a few data sets in the literature. Our results suggest that our kernel outperforms many of the common graph kernels in the tested data sets. As a second set of experiments, we successfully cluster viral genomes using GTED on their assembly graphs obtained from de novo assembly of next-generation sequencing reads.

Graph Classification of Molecules Using Force Field Atom and Bond Types.

Classification of the biological activities of chemical substances is important for developing new medicines efficiently. Various machine learning methods are often employed to screen large libraries of compounds and predict the activities of new substances by training the molecular structure-activity relationships. One such method is graph classification, in which a molecular structure can be represented in terms of a labeled graph with nodes that correspond to atoms and edges that correspond to the bonds between these atoms. In a conventional graph definition, atomic symbols and bond orders are employed as node and edge labels, respectively. In this study, we developed new graph definitions using the assignment of atom and bond types in the force fields of molecular dynamics methods as node and edge labels, respectively. We found that these graph definitions improved the accuracies of activity classifications for chemical substances using graph kernels with support vector machines and deep neural networks. The higher accuracies obtained using our proposed definitions can enhance the development of the materials informatics using graph-based machine learning methods.

iScore: An MPI supported software for ranking protein-protein docking models based on a random walk graph kernel and support vector machines.

Computational docking is a promising tool to model three-dimensional (3D) structures of protein-protein complexes, which provides fundamental insights of protein functions in the cellular life. Singling out near-native models from the huge pool of generated docking models (referred to as the scoring problem) remains as a major challenge in computational docking. We recently published iScore, a novel graph kernel based scoring function. iScore ranks docking models based on their interface graph similarities to the training interface graph set. iScore uses a support vector machine approach with random-walk graph kernels to classify and rank protein-protein interfaces. Here, we present the software for iScore. The software provides executable scripts that fully automate the computational workflow. In addition, the creation and analysis of the interface graph can be distributed across different processes using Message Passing interface (MPI) and can be offloaded to GPUs thanks to dedicated CUDA kernels.

Graph kernels combined with the neural network on protein classification.

At present, most of the researches on protein classification are based on graph kernels. The essence of graph kernels is to extract the substructure and use the similarity of substructures as the kernel values. In this paper, we propose a novel graph kernel named vertex-edge similarity kernel (VES kernel) based on mixed matrix, the innovation point of which is taking the adjacency matrix of the graph as the sample vector of each vertex and calculating kernel values by finding the most similar vertex pair of two graphs. In addition, we combine the novel kernel with the neural network and the experimental results show that the combination is better than the existing advanced methods.

A novel graph kernel on chemical compound classification.

Considering the classification of compounds as a nonlinear problem, the use of kernel methods is a good choice. Graph kernels provide a nice framework combining machine learning methods with graph theory, whereas the essence of graph kernels is to compare the substructures of two graphs, how to extract the substructures is a question. In this paper, we propose a novel graph kernel based on matrix named the local block kernel, which can compare the similarity of partial substructures that contain any number of vertexes. The paper finally tests the efficacy of this novel graph kernel in comparison with a number of published mainstream methods and results with two datasets: NCI1 and NCI109 for the convenience of comparison.

Subnetwork mining on functional connectivity network for classification of minimal hepatic encephalopathy.

Hepatic encephalopathy (HE), as a complication of cirrhosis, is a serious brain disease, which may lead to death. Accurate diagnosis of HE and its intermediate stage, i.e., minimal HE (MHE), is very important for possibly early diagnosis and treatment. Brain connectivity network, as a simple representation of brain interaction, has been widely used for the brain disease (e.g., HE and MHE) analysis. However, those studies mainly focus on finding disease-related abnormal connectivity between brain regions, although a large number of studies have indicated that some brain diseases are usually related to local structure of brain connectivity network (i.e., subnetwork), rather than solely on some single brain regions or connectivities. Also, mining such disease-related subnetwork is a challenging task because of the complexity of brain network. To address this problem, we proposed a novel frequent-subnetwork-based method to mine disease-related subnetworks for MHE classification. Specifically, we first mine frequent subnetworks from both groups, i.e., MHE patients and non-HE (NHE) patients, respectively. Then we used the graph-kernel based method to select the most discriminative subnetworks for subsequent classification. We evaluate our proposed method on a MHE dataset with 77 cirrhosis patients, including 38 MHE patients and 39 NHE patients. The results demonstrate that our proposed method can not only obtain the improved classification performance in comparison with state-of-the-art network-based methods, but also identify disease-related subnetworks which can help us better understand the pathology of the brain diseases.

Classification of Alzheimer's Disease, Mild Cognitive Impairment, and Normal Controls With Subnetwork Selection and Graph Kernel Principal Component Analysis Based on Minimum Spanning Tree Brain Functional Network.

Effective and accurate diagnosis of Alzheimer's disease (AD), as well as its early stage (mild cognitive impairment, MCI), has attracted more and more attention recently. Researchers have constructed threshold brain function networks and extracted various features for the classification of brain diseases. However, in the construction of the brain function network, the selection of threshold is very important, and the unreasonable setting will seriously affect the final classification results. To address this issue, in this paper, we propose a minimum spanning tree (MST) classification framework to identify Alzheimer's disease (AD), MCI, and normal controls (NCs). The proposed method mainly uses the MST method, graph-based Substructure Pattern mining (gSpan), and graph kernel Principal Component Analysis (graph kernel PCA). Specifically, MST is used to construct the brain functional connectivity network; gSpan, to extract features; and subnetwork selection and graph kernel PCA, to select features. Finally, the support vector machine is used to perform classification. We evaluate our method on MST brain functional networks of 21 AD, 25 MCI, and 22 NC subjects. The experimental results show that our proposed method achieves classification accuracy of 98.3, 91.3, and 77.3%, for MCI vs. NC, AD vs. NC, and AD vs. MCI, respectively. The results show our proposed method can achieve significantly improved classification performance compared to other state-of-the-art methods.

Multiple kernels learning-based biological entity relationship extraction method.

BACKGROUND: Automatic extracting protein entity interaction information from biomedical literature can help to build protein relation network and design new drugs. There are more than 20 million literature abstracts included in MEDLINE, which is the most authoritative textual database in the field of biomedicine, and follow an exponential growth over time. This frantic expansion of the biomedical literature can often be difficult to absorb or manually analyze. Thus efficient and automated search engines are necessary to efficiently explore the biomedical literature using text mining techniques. RESULTS: The P, R, and F value of tag graph method in Aimed corpus are 50.82, 69.76, and 58.61%, respectively. The P, R, and F value of tag graph kernel method in other four evaluation corpuses are 2-5% higher than that of all-paths graph kernel. And The P, R and F value of feature kernel and tag graph kernel fuse methods is 53.43, 71.62 and 61.30%, respectively. The P, R and F value of feature kernel and tag graph kernel fuse methods is 55.47, 70.29 and 60.37%, respectively. It indicated that the performance of the two kinds of kernel fusion methods is better than that of simple kernel. CONCLUSION: In comparison with the all-paths graph kernel method, the tag graph kernel method is superior in terms of overall performance. Experiments show that the performance of the multi-kernels method is better than that of the three separate single-kernel method and the dual-mutually fused kernel method used hereof in five corpus sets.

Structural graph-based morphometry: A multiscale searchlight framework based on sulcal pits.

Studying the topography of the cortex has proved valuable in order to characterize populations of subjects. In particular, the recent interest towards the deepest parts of the cortical sulci - the so-called sulcal pits - has opened new avenues in that regard. In this paper, we introduce the first fully automatic brain morphometry method based on the study of the spatial organization of sulcal pits - Structural Graph-Based Morphometry (SGBM). Our framework uses attributed graphs to model local patterns of sulcal pits, and further relies on three original contributions. First, a graph kernel is defined to provide a new similarity measure between pit-graphs, with few parameters that can be efficiently estimated from the data. Secondly, we present the first searchlight scheme dedicated to brain morphometry, yielding dense information maps covering the full cortical surface. Finally, a multi-scale inference strategy is designed to jointly analyze the searchlight information maps obtained at different spatial scales. We demonstrate the effectiveness of our framework by studying gender differences and cortical asymmetries: we show that SGBM can both localize informative regions and estimate their spatial scales, while providing results which are consistent with the literature. Thanks to the modular design of our kernel and the vast array of available kernel methods, SGBM can easily be extended to include a more detailed description of the sulcal patterns and solve different statistical problems. Therefore, we suggest that our SGBM framework should be useful for both reaching a better understanding of the normal brain and defining imaging biomarkers in clinical settings.

Network-based classification of ADHD patients using discriminative subnetwork selection and graph kernel PCA.

BACKGROUND: Attention Deficit Hyperactivity Disorder (ADHD) is one of the most prevalent behavioral disorders in childhood and adolescence. Recently, network-based diagnosis of ADHD has attracted great attentions due to the fact that ADHD disease is related to not only individual brain regions but also the connections among them, while existing methods are hard to discover disorder patterns related with several brain regions. NEW METHOD: To overcome this drawback, a discriminative subnetwork selection method is proposed to directly mine those frequent and discriminative subnetworks from the whole brain networks of ADHD and normal control (NC) groups. Then, the graph kernel principal component (PCA) is applied to extract features from those discriminative subnetworks. Finally, support vector machine (SVM) is adopted for classification of ADHD and NC subjects. RESULTS: We evaluate the performances of our proposed method using the ADHD200 dataset, which contains 118 ADHD patients and 98 normal controls. The experimental results show that our proposed method can achieve a very high accuracy of 94.91% for ADHD vs. NC classification. Moreover, our proposed method can also discover the discriminative subnetworks as well as the discriminative brain regions, which are helpful for enhancing our understanding of ADHD disease. COMPARISON WITH EXISTING METHOD(S): The accuracy of our proposed method is 9.20% higher than those of the state-of-the-art methods. CONCLUSIONS: A lot of experiments in ADHD200 dataset show that, our proposed method can improve the performance significantly comparing to the state-of-the-art methods.