Fast depth-based subgraph kernels for unattributed graphs. (February 2016) - Bai, Lu; Hancock, Edwin R.
Abstract: In this paper, we investigate two fast subgraph kernels based on a depth-based representation of graph-structure. Both methods gauge depth information through a family of K -layer expansion subgraphs rooted at a vertex[1] . The first method commences by computing a centroid-based complexity trace for each graph, using a depth-based representation rooted at the centroid vertex that has minimum shortest path length variance to the remaining vertices[2] . This subgraph kernel is computed by measuring the Jensen–Shannon divergence between centroid-based complexity entropy traces. The second method, on the other hand, computes a depth-based representation around each vertex in turn. The corresponding subgraph kernel is computed using isomorphisms tests to compare the depth-based representation rooted at each vertex in turn. For graphs with n vertices, the time complexities for the two new kernels are O ( n 2 ) and O ( n 3 ), in contrast to O ( n 6 ) for the classic Gärtner graph kernel[3] . Key to achieving this efficiency is that we compute the required Shannon entropy of the random walk for our kernels with O ( n 2 ) operations. This computational strategy enables our subgraph kernels to easily scale up to graphs of reasonably large sizes and thus overcome the size limits arising in state-of-the-art graph kernels. Experiments on standard bioinformatics and computer vision graph datasets demonstrate the effectiveness and efficiency of our new subgraph kernels. Abstract : Highlights: We investigate two fast subgraph kernels based on a depth-based representation. Our kernels gauge depth information rooted at a vertex for a graph. The time complexities for the two kernels are O ( n 2 ) and O ( n 3 ) . We evaluate the performance of our subgraph kernels on standard graph datasets. We demonstrate the effectiveness of the proposed subgraph kernels.