### Abstract

One of the most fundamental problem that we face in the graph domain is that of establishing the similarity, or alternatively the distance, between graphs. In this paper, we address the problem of measuring the similarity between attributed graphs. In particular, we propose a novel way to measure the similarity through the evolution of a continuous-time quantum walk. Given a pair of graphs, we create a derived structure whose degree of symmetry is maximum when the original graphs are isomorphic, and where a subset of the edges is labeled with the similarity between the respective nodes. With this compositional structure to hand, we compute the density operators of the quantum systems representing the evolution of two suitably defined quantum walks. We define the similarity between the two original graphs as the quantum Jensen-Shannon divergence between these two density operators, and then we show how to build a novel kernel on attributed graphs based on the proposed similarity measure. We perform an extensive experimental evaluation both on synthetic and real-world data, which shows the effectiveness the proposed approach.

Original language | English |
---|---|

Title of host publication | Similarity-Based Pattern Recognition |

Subtitle of host publication | second international workshop, SIMBAD 2013, York, UK, July 3-5, 2013. Proceedings |

Editors | Edwin Hancock, Marcello Pelillo |

Place of Publication | Berlin (DE) |

Publisher | Springer |

Pages | 204-218 |

Number of pages | 15 |

ISBN (Electronic) | 978-3-642-39140-8 |

ISBN (Print) | 978-3-642-39139-2 |

DOIs | |

Publication status | Published - 2013 |

Event | 2nd international workshop on Similarity-Based pattern Analysis and Recognition - York, United Kingdom Duration: 3 Jul 2013 → 5 Jul 2013 |

### Publication series

Name | Lecture notes in computer science |
---|---|

Publisher | Springer |

Volume | 7953 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Workshop

Workshop | 2nd international workshop on Similarity-Based pattern Analysis and Recognition |
---|---|

Abbreviated title | SIMBAD 2013 |

Country | United Kingdom |

City | York |

Period | 3/07/13 → 5/07/13 |

### Fingerprint

### Keywords

- continuous-time quantum walk
- graph kernels
- graph similarity
- quantum Jensen-Shannon divergence

### Cite this

*Similarity-Based Pattern Recognition: second international workshop, SIMBAD 2013, York, UK, July 3-5, 2013. Proceedings*(pp. 204-218). (Lecture notes in computer science; Vol. 7953). Berlin (DE): Springer. https://doi.org/10.1007/978-3-642-39140-8_14

}

*Similarity-Based Pattern Recognition: second international workshop, SIMBAD 2013, York, UK, July 3-5, 2013. Proceedings.*Lecture notes in computer science, vol. 7953, Springer, Berlin (DE), pp. 204-218, 2nd international workshop on Similarity-Based pattern Analysis and Recognition, York, United Kingdom, 3/07/13. https://doi.org/10.1007/978-3-642-39140-8_14

**Attributed graph similarity from the quantum Jensen-Shannon divergence.** / Rossi, Luca; Torsello, Andrea; Hancock, Edwin R.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Attributed graph similarity from the quantum Jensen-Shannon divergence

AU - Rossi, Luca

AU - Torsello, Andrea

AU - Hancock, Edwin R.

PY - 2013

Y1 - 2013

N2 - One of the most fundamental problem that we face in the graph domain is that of establishing the similarity, or alternatively the distance, between graphs. In this paper, we address the problem of measuring the similarity between attributed graphs. In particular, we propose a novel way to measure the similarity through the evolution of a continuous-time quantum walk. Given a pair of graphs, we create a derived structure whose degree of symmetry is maximum when the original graphs are isomorphic, and where a subset of the edges is labeled with the similarity between the respective nodes. With this compositional structure to hand, we compute the density operators of the quantum systems representing the evolution of two suitably defined quantum walks. We define the similarity between the two original graphs as the quantum Jensen-Shannon divergence between these two density operators, and then we show how to build a novel kernel on attributed graphs based on the proposed similarity measure. We perform an extensive experimental evaluation both on synthetic and real-world data, which shows the effectiveness the proposed approach.

AB - One of the most fundamental problem that we face in the graph domain is that of establishing the similarity, or alternatively the distance, between graphs. In this paper, we address the problem of measuring the similarity between attributed graphs. In particular, we propose a novel way to measure the similarity through the evolution of a continuous-time quantum walk. Given a pair of graphs, we create a derived structure whose degree of symmetry is maximum when the original graphs are isomorphic, and where a subset of the edges is labeled with the similarity between the respective nodes. With this compositional structure to hand, we compute the density operators of the quantum systems representing the evolution of two suitably defined quantum walks. We define the similarity between the two original graphs as the quantum Jensen-Shannon divergence between these two density operators, and then we show how to build a novel kernel on attributed graphs based on the proposed similarity measure. We perform an extensive experimental evaluation both on synthetic and real-world data, which shows the effectiveness the proposed approach.

KW - continuous-time quantum walk

KW - graph kernels

KW - graph similarity

KW - quantum Jensen-Shannon divergence

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

UR - http://link.springer.com/chapter/10.1007%2F978-3-642-39140-8_14

U2 - 10.1007/978-3-642-39140-8_14

DO - 10.1007/978-3-642-39140-8_14

M3 - Conference contribution

AN - SCOPUS:84879866511

SN - 978-3-642-39139-2

T3 - Lecture notes in computer science

SP - 204

EP - 218

BT - Similarity-Based Pattern Recognition

A2 - Hancock, Edwin

A2 - Pelillo, Marcello

PB - Springer

CY - Berlin (DE)

ER -