A nested alignment graph kernel through the dynamic time warping framework

Lu Bai; Luca Rossi; Lixin Cui; Edwin R. Hancock

doi:10.1007/978-3-319-58961-9_6

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/Published conference output › Conference publication

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 language	English
Title of host publication	Graph-based representations in pattern recognition : 11th IAPR-TC-15 international workshop, GbRPR 2017. Proceedings
Editors	Pasquale Foggia, Cheng-Lin Liu, Mario Vento
Place of Publication	Cham (CH)
Publisher	Springer
Pages	59-69
Number of pages	11
ISBN (Electronic)	978-3-319-58961-9
ISBN (Print)	978-3-319-58960-2
DOIs	https://doi.org/10.1007/978-3-319-58961-9_6
Publication status	Published - 2017
Event	11th IAPR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition, GbRPR 2017 - Anacapri, Italy Duration: 16 May 2017 → 18 May 2017

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	10310
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	11th IAPR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition, GbRPR 2017
Country/Territory	Italy
City	Anacapri
Period	16/05/17 → 18/05/17

Access to Document

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

Nested alignment graph kernel through the dynamic time warping frameworkAccepted author manuscript, 106 KB

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). Springer. https://doi.org/10.1007/978-3-319-58961-9_6

@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",

note = "11th IAPR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition, GbRPR 2017 ; Conference date: 16-05-2017 Through 18-05-2017",

}

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 et al.
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/Published conference output › Conference publication

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 publication

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)

T2 - 11th IAPR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition, GbRPR 2017

Y2 - 16 May 2017 through 18 May 2017

ER -

Bai L, Rossi L, Cui L, Hancock ER. A nested alignment graph kernel through the dynamic time warping framework. In Foggia P, Liu CL, 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). Epub 2017 May 10. doi: 10.1007/978-3-319-58961-9_6

A nested alignment graph kernel through the dynamic time warping framework

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Adaptive feature selection based on the most informative graph-based features

Measuring vertex centrality using the Holevo quantity

Cite this