A nested alignment graph kernel through the dynamic time warping framework

Lu Bai, Luca Rossi*, Lixin Cui, Edwin R. Hancock

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, we propose a novel nested alignment graph kernel drawing on depth-based complexity traces and the dynamic time warping framework. Specifically, for a pair of graphs, we commence by computing the depth-based complexity traces rooted at the centroid vertices. The resulting kernel for the graphs is defined by measuring the global alignment kernel, which is developed through the dynamic time warping framework, between the complexity traces. We show that the proposed kernel simultaneously considers the local and global graph characteristics in terms of the complexity traces, but also provides richer statistic measures by incorporating the whole spectrum of alignment costs between these traces. Our experiments demonstrate the effectiveness and efficiency of the proposed kernel.

Original languageEnglish
Title of host publicationGraph-based representations in pattern recognition : 11th IAPR-TC-15 international workshop, GbRPR 2017. Proceedings
EditorsPasquale Foggia, Cheng-Lin Liu, Mario Vento
Place of PublicationCham (CH)
PublisherSpringer
Pages59-69
Number of pages11
ISBN (Electronic)978-3-319-58961-9
ISBN (Print)978-3-319-58960-2
DOIs
Publication statusPublished - 2017
Event11th IAPR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition, GbRPR 2017 - Anacapri, Italy
Duration: 16 May 201718 May 2017

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume10310
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

Workshop11th IAPR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition, GbRPR 2017
CountryItaly
CityAnacapri
Period16/05/1718/05/17

Fingerprint

Dynamic Time Warping
Alignment
Trace
kernel
Graph in graph theory
Statistics
Centroid
Statistic
Framework
Costs
Experiments
Computing
Demonstrate
Experiment

Cite this

Bai, L., Rossi, L., Cui, L., & Hancock, E. R. (2017). A nested alignment graph kernel through the dynamic time warping framework. In P. Foggia, C-L. Liu, & M. Vento (Eds.), Graph-based representations in pattern recognition : 11th IAPR-TC-15 international workshop, GbRPR 2017. Proceedings (pp. 59-69). (Lecture Notes in Computer Science; Vol. 10310). Cham (CH): Springer. https://doi.org/10.1007/978-3-319-58961-9_6
Bai, Lu ; Rossi, Luca ; Cui, Lixin ; Hancock, Edwin R. / A nested alignment graph kernel through the dynamic time warping framework. Graph-based representations in pattern recognition : 11th IAPR-TC-15 international workshop, GbRPR 2017. Proceedings. editor / Pasquale Foggia ; Cheng-Lin Liu ; Mario Vento. Cham (CH) : Springer, 2017. pp. 59-69 (Lecture Notes in Computer Science).
@inproceedings{13e9e5503c7448beac8a26f4ec537eff,
title = "A nested alignment graph kernel through the dynamic time warping framework",
abstract = "In this paper, we propose a novel nested alignment graph kernel drawing on depth-based complexity traces and the dynamic time warping framework. Specifically, for a pair of graphs, we commence by computing the depth-based complexity traces rooted at the centroid vertices. The resulting kernel for the graphs is defined by measuring the global alignment kernel, which is developed through the dynamic time warping framework, between the complexity traces. We show that the proposed kernel simultaneously considers the local and global graph characteristics in terms of the complexity traces, but also provides richer statistic measures by incorporating the whole spectrum of alignment costs between these traces. Our experiments demonstrate the effectiveness and efficiency of the proposed kernel.",
author = "Lu Bai and Luca Rossi and Lixin Cui and Hancock, {Edwin R.}",
year = "2017",
doi = "10.1007/978-3-319-58961-9_6",
language = "English",
isbn = "978-3-319-58960-2",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "59--69",
editor = "Pasquale Foggia and Cheng-Lin Liu and Mario Vento",
booktitle = "Graph-based representations in pattern recognition : 11th IAPR-TC-15 international workshop, GbRPR 2017. Proceedings",
address = "Germany",

}

Bai, L, Rossi, L, Cui, L & Hancock, ER 2017, A nested alignment graph kernel through the dynamic time warping framework. in P Foggia, C-L Liu & M Vento (eds), Graph-based representations in pattern recognition : 11th IAPR-TC-15 international workshop, GbRPR 2017. Proceedings. Lecture Notes in Computer Science, vol. 10310, Springer, Cham (CH), pp. 59-69, 11th IAPR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition, GbRPR 2017 , Anacapri, Italy, 16/05/17. https://doi.org/10.1007/978-3-319-58961-9_6

A nested alignment graph kernel through the dynamic time warping framework. / Bai, Lu; Rossi, Luca; Cui, Lixin; Hancock, Edwin R.

Graph-based representations in pattern recognition : 11th IAPR-TC-15 international workshop, GbRPR 2017. Proceedings. ed. / Pasquale Foggia; Cheng-Lin Liu; Mario Vento. Cham (CH) : Springer, 2017. p. 59-69 (Lecture Notes in Computer Science; Vol. 10310).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - A nested alignment graph kernel through the dynamic time warping framework

AU - Bai, Lu

AU - Rossi, Luca

AU - Cui, Lixin

AU - Hancock, Edwin R.

PY - 2017

Y1 - 2017

N2 - In this paper, we propose a novel nested alignment graph kernel drawing on depth-based complexity traces and the dynamic time warping framework. Specifically, for a pair of graphs, we commence by computing the depth-based complexity traces rooted at the centroid vertices. The resulting kernel for the graphs is defined by measuring the global alignment kernel, which is developed through the dynamic time warping framework, between the complexity traces. We show that the proposed kernel simultaneously considers the local and global graph characteristics in terms of the complexity traces, but also provides richer statistic measures by incorporating the whole spectrum of alignment costs between these traces. Our experiments demonstrate the effectiveness and efficiency of the proposed kernel.

AB - In this paper, we propose a novel nested alignment graph kernel drawing on depth-based complexity traces and the dynamic time warping framework. Specifically, for a pair of graphs, we commence by computing the depth-based complexity traces rooted at the centroid vertices. The resulting kernel for the graphs is defined by measuring the global alignment kernel, which is developed through the dynamic time warping framework, between the complexity traces. We show that the proposed kernel simultaneously considers the local and global graph characteristics in terms of the complexity traces, but also provides richer statistic measures by incorporating the whole spectrum of alignment costs between these traces. Our experiments demonstrate the effectiveness and efficiency of the proposed kernel.

UR - https://link.springer.com/chapter/10.1007%2F978-3-319-58961-9_6

UR - http://www.scopus.com/inward/record.url?scp=85019642275&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-58961-9_6

DO - 10.1007/978-3-319-58961-9_6

M3 - Conference contribution

AN - SCOPUS:85019642275

SN - 978-3-319-58960-2

T3 - Lecture Notes in Computer Science

SP - 59

EP - 69

BT - Graph-based representations in pattern recognition : 11th IAPR-TC-15 international workshop, GbRPR 2017. Proceedings

A2 - Foggia, Pasquale

A2 - Liu, Cheng-Lin

A2 - Vento, Mario

PB - Springer

CY - Cham (CH)

ER -

Bai L, Rossi L, Cui L, Hancock ER. A nested alignment graph kernel through the dynamic time warping framework. In Foggia P, Liu C-L, Vento M, editors, Graph-based representations in pattern recognition : 11th IAPR-TC-15 international workshop, GbRPR 2017. Proceedings. Cham (CH): Springer. 2017. p. 59-69. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-58961-9_6