Statistical and Machine Learning Approaches for Network Analysis

8.5 Tree-Pattern Graph Kernels

Tree-based graph kernels [55] compare subtrees of graphs.

8.5.1 Definition

Let G = (V, E) be a graph and let T = (W, F), be a rooted directed tree. A tree pattern of G with respect to T consists of vertices such that

(8.14)

Each vertex in the tree is assigned a vertex in the graph such that edges and labels match. The need not be distinct, as long as vertices assigned to sibling vertices in T are distinct (Fig. 8.3). The tree pattern counting functionψ(G, T) returns the number of times the tree pattern T occurs in the graph G, that is, the number of distinct tuples that are tree patterns of T in G.

Figure 8.3 Tree patterns. Shown are the annotated graph of acetic acid (a) and a tree pattern contained in it (b). Numbers indicate assigned vertices. Note that ...