Fast depth-based subgraph kernels for unattributed graphs. (February 2016)

• Record Type: Journal Article
• Authors: Bai, Lu; Hancock, Edwin R.
• Is Part Of: Pattern recognition. Volume 50(2016:Feb.)
• Page Start: 233
• Page End: 245
• Publication Date: 2016-02
• Subjects: Depth-based representations -- Entropy -- Graph kernels -- The Jensen–Shannon divergence -- Graph isomorphism tests; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2015.08.006
• Languages: English
• ISSNs: 0031-3203

Abstract

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.