## 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 language | English |
---|---|

Title of host publication | Image Analysis and Processing – ICIAP 2015 - 18th International Conference, Proceedings |

Editors | Vittorio Murino, Enrico Puppo, Vittorio Murino |

Publisher | Springer Verlag |

Pages | 27-38 |

Number of pages | 12 |

ISBN (Print) | 9783319232300 |

DOIs | |

Publication status | Published - Sept 2015 |

Externally published | Yes |

Event | 18th International Conference on Image Analysis and Processing, ICIAP 2015 - Genoa, Italy Duration: 7 Sept 2015 → 11 Sept 2015 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 9279 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 18th International Conference on Image Analysis and Processing, ICIAP 2015 |
---|---|

Country/Territory | Italy |

City | Genoa |

Period | 7/09/15 → 11/09/15 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science