Local-global nested graph kernels using nested complexity traces

Bai, Lu, Cui, Lixin, Rossi, Luca, Xu, Lixiang and Hancock, Edwin R. (2018). Local-global nested graph kernels using nested complexity traces. Pattern Recognition Letters ,

Abstract

In this paper, we propose two novel local-global nested graph kernels, namely the nested aligned kernel and the nested reproducing kernel, drawing on depth-based complexity traces. Both of the nested kernels gauge the nested depth complexity trace through a family of K-layer expansion subgraphs rooted at the centroid vertex, i.e., the vertex with minimum shortest path length variance to the remaining vertices. Specifically, for a pair of graphs, we commence by computing the centroid depth-based complexity traces rooted at the centroid vertices. The first nested kernel is defined by measuring the global alignment kernel, which is based on the dynamic time warping framework, between the complexity traces. Since the required global alignment kernel incorporates the whole spectrum of alignment costs between the complexity traces, this nested kernel can provide rich statistic measures. The second nested kernel, on the other hand, is defined by measuring the basic reproducing kernel between the complexity traces. Since the associated reproducing kernel only requires time complexity O(1), this nested kernel has very low computational complexity. We theoretically show that both of the proposed nested kernels can simultaneously reflect the local and global graph characteristics in terms of the nested complexity traces. Experiments on standard graph datasets abstracted from bioinformatics and computer vision databases demonstrate the effectiveness and efficiency of the proposed graph kernels.

Publication DOI: https://doi.org/10.1016/j.patrec.2018.06.016
Divisions: Engineering & Applied Sciences
Engineering & Applied Sciences > Computer science research group
Engineering & Applied Sciences > Systems analytics research institute (SARI)
Uncontrolled Keywords: Graph kernels,Depth-based complexity traces,Nested kernels
Full Text Link: http://eprints. ... e.ac.uk/131852/
Related URLs: https://www.sci ... 167865518302617 (Publisher URL)
Published Date: 2018-06-19
Authors: Bai, Lu
Cui, Lixin
Rossi, Luca ( 0000-0002-6116-9761)
Xu, Lixiang
Hancock, Edwin R.

Export / Share Citation


Statistics

Additional statistics for this record