An edge-based matching kernel through discrete-time quantum walks

Lu Bai, Zhihong Zhang, Peng Ren, Luca Rossi, Edwin R. Hancock

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

Abstract

In this paper, we propose a new edge-based matching kernel for graphs by using discrete-time quantum walks. To this end, we commence by transforming a graph into a directed line graph. The reasons of using the line graph structure are twofold. First, for a graph, its directed line graph is a dual representation and each vertex of the line graph represents a corresponding edge in the original graph. Second, we show that the discrete-time quantum walk can be seen as a walk on the line graph and the state space of the walk is the vertex set of the line graph, i.e., the state space of the walk is the edges of the original graph. As a result, the directed line graph provides an elegant way of developing new edge-based matching kernel based on discrete-time quantum walks. For a pair of graphs, we compute the h-layer depth-based representation for each vertex of their directed line graphs by computing entropic signatures (computed from discrete-time quantum walks on the line graphs) on the family of K-layer expansion subgraphs rooted at the vertex, i.e., we compute the depth-based representations for edges of the original graphs through their directed line graphs. Based on the new representations, we define an edge-based matching method for the pair of graphs by aligning the h-layer depth-based representations computed through the directed line graphs. The new edge-based matching kernel is thus computed by counting the number of matched vertices identified by the matching method on the directed line graphs. Experiments on standard graph datasets demonstrate the effectiveness of our new kernel.
Original languageEnglish
Title of host publicationImage analysis and processing — ICIAP 2015
Subtitle of host publication18th International Conference, Genoa, Italy, September 7-11, 2015, Proceedings
EditorsVittorio Murino, Enrico Puppo
Place of PublicationChem (CH)
PublisherSpringer
Pages27-38
Number of pages10
VolumePart I
ISBN (Electronic)978-3-319-23231-7
ISBN (Print)978-3-319-23230-0
DOIs
Publication statusPublished - 21 Aug 2015
Event18th International Conference on Image Analysis and Processing - Genova, Italy
Duration: 7 Sep 201511 Sep 2015

Publication series

NameLecture notes in computer science
PublisherSpringer
Volume9279
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th International Conference on Image Analysis and Processing
Abbreviated titleICIAP 2015
CountryItaly
CityGenova
Period7/09/1511/09/15

Fingerprint

Directed graphs
Experiments

Bibliographical note

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-23231-7_3

Cite this

Bai, L., Zhang, Z., Ren, P., Rossi, L., & Hancock, E. R. (2015). An edge-based matching kernel through discrete-time quantum walks. In V. Murino, & E. Puppo (Eds.), Image analysis and processing — ICIAP 2015: 18th International Conference, Genoa, Italy, September 7-11, 2015, Proceedings (Vol. Part I, pp. 27-38). (Lecture notes in computer science; Vol. 9279). Chem (CH): Springer. https://doi.org/10.1007/978-3-319-23231-7_3
Bai, Lu ; Zhang, Zhihong ; Ren, Peng ; Rossi, Luca ; Hancock, Edwin R. / An edge-based matching kernel through discrete-time quantum walks. Image analysis and processing — ICIAP 2015: 18th International Conference, Genoa, Italy, September 7-11, 2015, Proceedings. editor / Vittorio Murino ; Enrico Puppo. Vol. Part I Chem (CH) : Springer, 2015. pp. 27-38 (Lecture notes in computer science).
@inproceedings{57b2f1140a78439aa97c27c643e04cd3,
title = "An edge-based matching kernel through discrete-time quantum walks",
abstract = "In this paper, we propose a new edge-based matching kernel for graphs by using discrete-time quantum walks. To this end, we commence by transforming a graph into a directed line graph. The reasons of using the line graph structure are twofold. First, for a graph, its directed line graph is a dual representation and each vertex of the line graph represents a corresponding edge in the original graph. Second, we show that the discrete-time quantum walk can be seen as a walk on the line graph and the state space of the walk is the vertex set of the line graph, i.e., the state space of the walk is the edges of the original graph. As a result, the directed line graph provides an elegant way of developing new edge-based matching kernel based on discrete-time quantum walks. For a pair of graphs, we compute the h-layer depth-based representation for each vertex of their directed line graphs by computing entropic signatures (computed from discrete-time quantum walks on the line graphs) on the family of K-layer expansion subgraphs rooted at the vertex, i.e., we compute the depth-based representations for edges of the original graphs through their directed line graphs. Based on the new representations, we define an edge-based matching method for the pair of graphs by aligning the h-layer depth-based representations computed through the directed line graphs. The new edge-based matching kernel is thus computed by counting the number of matched vertices identified by the matching method on the directed line graphs. Experiments on standard graph datasets demonstrate the effectiveness of our new kernel.",
author = "Lu Bai and Zhihong Zhang and Peng Ren and Luca Rossi and Hancock, {Edwin R.}",
note = "The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-23231-7_3",
year = "2015",
month = "8",
day = "21",
doi = "10.1007/978-3-319-23231-7_3",
language = "English",
isbn = "978-3-319-23230-0",
volume = "Part I",
series = "Lecture notes in computer science",
publisher = "Springer",
pages = "27--38",
editor = "Vittorio Murino and Enrico Puppo",
booktitle = "Image analysis and processing — ICIAP 2015",
address = "Germany",

}

Bai, L, Zhang, Z, Ren, P, Rossi, L & Hancock, ER 2015, An edge-based matching kernel through discrete-time quantum walks. in V Murino & E Puppo (eds), Image analysis and processing — ICIAP 2015: 18th International Conference, Genoa, Italy, September 7-11, 2015, Proceedings. vol. Part I, Lecture notes in computer science, vol. 9279, Springer, Chem (CH), pp. 27-38, 18th International Conference on Image Analysis and Processing, Genova, Italy, 7/09/15. https://doi.org/10.1007/978-3-319-23231-7_3

An edge-based matching kernel through discrete-time quantum walks. / Bai, Lu; Zhang, Zhihong; Ren, Peng; Rossi, Luca; Hancock, Edwin R.

Image analysis and processing — ICIAP 2015: 18th International Conference, Genoa, Italy, September 7-11, 2015, Proceedings. ed. / Vittorio Murino; Enrico Puppo. Vol. Part I Chem (CH) : Springer, 2015. p. 27-38 (Lecture notes in computer science; Vol. 9279).

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

TY - GEN

T1 - An edge-based matching kernel through discrete-time quantum walks

AU - Bai, Lu

AU - Zhang, Zhihong

AU - Ren, Peng

AU - Rossi, Luca

AU - Hancock, Edwin R.

N1 - The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-23231-7_3

PY - 2015/8/21

Y1 - 2015/8/21

N2 - In this paper, we propose a new edge-based matching kernel for graphs by using discrete-time quantum walks. To this end, we commence by transforming a graph into a directed line graph. The reasons of using the line graph structure are twofold. First, for a graph, its directed line graph is a dual representation and each vertex of the line graph represents a corresponding edge in the original graph. Second, we show that the discrete-time quantum walk can be seen as a walk on the line graph and the state space of the walk is the vertex set of the line graph, i.e., the state space of the walk is the edges of the original graph. As a result, the directed line graph provides an elegant way of developing new edge-based matching kernel based on discrete-time quantum walks. For a pair of graphs, we compute the h-layer depth-based representation for each vertex of their directed line graphs by computing entropic signatures (computed from discrete-time quantum walks on the line graphs) on the family of K-layer expansion subgraphs rooted at the vertex, i.e., we compute the depth-based representations for edges of the original graphs through their directed line graphs. Based on the new representations, we define an edge-based matching method for the pair of graphs by aligning the h-layer depth-based representations computed through the directed line graphs. The new edge-based matching kernel is thus computed by counting the number of matched vertices identified by the matching method on the directed line graphs. Experiments on standard graph datasets demonstrate the effectiveness of our new kernel.

AB - In this paper, we propose a new edge-based matching kernel for graphs by using discrete-time quantum walks. To this end, we commence by transforming a graph into a directed line graph. The reasons of using the line graph structure are twofold. First, for a graph, its directed line graph is a dual representation and each vertex of the line graph represents a corresponding edge in the original graph. Second, we show that the discrete-time quantum walk can be seen as a walk on the line graph and the state space of the walk is the vertex set of the line graph, i.e., the state space of the walk is the edges of the original graph. As a result, the directed line graph provides an elegant way of developing new edge-based matching kernel based on discrete-time quantum walks. For a pair of graphs, we compute the h-layer depth-based representation for each vertex of their directed line graphs by computing entropic signatures (computed from discrete-time quantum walks on the line graphs) on the family of K-layer expansion subgraphs rooted at the vertex, i.e., we compute the depth-based representations for edges of the original graphs through their directed line graphs. Based on the new representations, we define an edge-based matching method for the pair of graphs by aligning the h-layer depth-based representations computed through the directed line graphs. The new edge-based matching kernel is thus computed by counting the number of matched vertices identified by the matching method on the directed line graphs. Experiments on standard graph datasets demonstrate the effectiveness of our new kernel.

U2 - 10.1007/978-3-319-23231-7_3

DO - 10.1007/978-3-319-23231-7_3

M3 - Conference contribution

SN - 978-3-319-23230-0

VL - Part I

T3 - Lecture notes in computer science

SP - 27

EP - 38

BT - Image analysis and processing — ICIAP 2015

A2 - Murino, Vittorio

A2 - Puppo, Enrico

PB - Springer

CY - Chem (CH)

ER -

Bai L, Zhang Z, Ren P, Rossi L, Hancock ER. An edge-based matching kernel through discrete-time quantum walks. In Murino V, Puppo E, editors, Image analysis and processing — ICIAP 2015: 18th International Conference, Genoa, Italy, September 7-11, 2015, Proceedings. Vol. Part I. Chem (CH): Springer. 2015. p. 27-38. (Lecture notes in computer science). https://doi.org/10.1007/978-3-319-23231-7_3