Statistical and Machine Learning Approaches for Network Analysis

8.6 Cyclic Pattern Kernels

Cyclic pattern graph kernels [31,32] are based on the idea of mapping graphs to sets of cyclic and tree pattern strings that are compared using the intersection kernel.

8.6.1 Definition

A subgraph is a simple cycle if it is connected and each vertex has degree 2. Let S(G) denote the set of simple cycles in a graph G. An edge not belonging to a simple cycle is a bridge. We denote the subgraph of all bridges in G, which is a forest, by (Fig. 8.4). Let π be a mapping, computable in polynomial time, from the set of labeled simple cycles and trees to label strings that is injective modulo isomorphism. Note that such a mapping can always be constructed [31], [72]. The sets of cyclic and tree patterns are given by and . The cyclic pattern kernel is given by

(8.18)

where denotes the intersection kernel.

Figure 8.4 Cyclic and tree patterns of the molecular structure graph of indeglitazar. Shown are vertices belonging to simple cycles (shaded) and to bridges (white). ...