Graph kernels based on tree patterns for molecules

By Pierre Mahé, Jean-Philippe Vert. 2006

279 citations recorded by the source corpus.

Motivated by chemical applications, we revisit and extend a family of positive definite kernels for graphs based on the detection of common subtrees, initially proposed by Ramon and Gärtner (Proceedings of the first international workshop on mining graphs, trees and sequences, pp. 65–74, 2003). We propose new kernels with a parameter to control the complexity of the subtrees used as features to represent the graphs. This parameter allows to smoothly interpolate between classical graph kernels based on the count of common walks, on the one hand, and kernels that emphasize the detection of large common subtrees, on the other hand. We also propose two modular extensions to this formulation. The first extension increases the number of subtrees that define the feature space, and the second one removes noisy features from the graph representations. We validate experimentally these new kernels on problems of toxicity and anti-cancer activity prediction for small molecules with support vector machines.

Subfields: Computational Theory and Mathematics, Molecular Biology, Spectroscopy

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Molecular Biology

In Spectroscopy

Citations in the corpus

Pre-training Graph Neural Networks with Kernels (2018, positive): “Mahé and Vert [2008] describe a graph kernel based on extracting tree patterns from the graph.”
Propagation kernels: efficient graph kernels from propagated information (2014, background): “2009; Kriege and Mutzel 2012), kernels based on subtree patterns (Mahé and Vert 2009; Ramon and Gärtner 2003), and kernels based on structure propagation (Shervashidze et al.”
Generative Kernels for Tree-Structured Data (2018, background): “On the other side, generative models are typically exploited in the context of graphs to deﬁne non-adaptive kernels, such as in the marginalized kernel approaches [18],[19].”
Matching Node Embeddings for Graph Similarity (2017, methodology): “Graph kernels have been successfully used for comparing graphs in a variety of fields such as Computational Biology (Schölkopf, Tsuda, and Vert 2004), Chemistry (Mahé and Vert 2009), Information Retrieval (Hermansson et al.”
Ordered Decompositional DAG kernels enhancements (2015, methodology): “Mahé and Vert [23] described a graph kernel based on extracting tree patterns from the graph.”
Graph Invariant Kernels (2015, background): “Examples include tree-structured patterns [Ramon and Gärtner, 2003; Mahé and Vert, 2009], paths [Kashima et al.”
Efficient Graph Kernels by Randomization (2012, background): “Graph kernels can be categorized mainly into four classes: graph kernels based on walks [4, 10, 22] and paths [2], graph kernels based on limitedsize subgraphs [7,19], graph kernels based on subtree patterns [13,16], and graph”
Subgraph Matching Kernels for Attributed Graphs (2012, background): “Furthermore tree patters, which are allowed to contain repeated vertices just like random walks, were proposed by Ramon & G¨artner (2003) and later reﬁned by Mah´e & Vert (2009).”
Weisfeiler-Lehman Graph Kernels (2011, background): “…kernels based on walks (Kashima et al., 2003; Gärtner et al., 2003) and paths (Borgwardt and Kriegel, 2005), graph kernels based on limited-size subgraphs (Horváth et al., 2004; Shervashidze et al., 2009), and graph kernels based on subtree patterns (Ramon and Gärtner, 2003; Mahé and Vert, 2009).”
A Degeneracy Framework for Graph Similarity (2018, background): “Furthermore, in the past years, graph classiﬁcation has arisen as an important topic in many domains such as in Computational Biology [Sch¨olkopf et al. , 2004], in Chemistry [Mah´e and Vert, 2009] and in Natural Language Processing [Nikolentzos et al. , 2017a].”
Applied Predictive Modeling (2013, background): “A specialized class of kernel functions, called graph kernels, can directly relate the content of the chemical formula to the model without deriving descriptor variables (Mahé et al. 2005; Mahé and Vert 2009).”
A memory efficient graph kernel (2012, background): “Examples of such substructures are walks [1], paths [2], [3], or subtrees [4], [5].”
Tree-Based Kernel for Graphs With Continuous Attributes (2015, background): “COX2, BZRand DHFR, orginally presented in [20] are datasets of chemical compounds where the target is to predict their toxicity.”
Protein-ligand interaction prediction: an improved chemogenomics approach (2008, background): “, 2005) or on the encoding of various properties of the 3D structure of molecules (Azencott et al., 2007; Mahé et al., 2006).”