By the same authors

From the same journal

From the same journal

Local-global nested graph kernels using nested complexity traces

Research output: Contribution to journalArticlepeer-review

Full text download(s)


Published copy (DOI)



Publication details

JournalPattern Recognition Letters
DateAccepted/In press - 9 Jun 2018
DateE-pub ahead of print (current) - 19 Jun 2018
Number of pages10
Early online date19/06/18
Original languageEnglish


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.

Bibliographical note

© 2018 Published by Elsevier B.V. This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy.

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations