Attributed graph similarity from the quantum Jensen-Shannon divergence

Luca Rossi, Andrea Torsello, Edwin R. Hancock

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

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 languageEnglish
Title of host publicationSimilarity-Based Pattern Recognition
Subtitle of host publicationsecond international workshop, SIMBAD 2013, York, UK, July 3-5, 2013. Proceedings
EditorsEdwin Hancock, Marcello Pelillo
Place of PublicationBerlin (DE)
PublisherSpringer
Pages204-218
Number of pages15
ISBN (Electronic)978-3-642-39140-8
ISBN (Print)978-3-642-39139-2
DOIs
Publication statusPublished - 2013
Event2nd international workshop on Similarity-Based pattern Analysis and Recognition - York, United Kingdom
Duration: 3 Jul 20135 Jul 2013

Publication series

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

Workshop

Workshop2nd international workshop on Similarity-Based pattern Analysis and Recognition
Abbreviated titleSIMBAD 2013
CountryUnited Kingdom
CityYork
Period3/07/135/07/13

Keywords

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

Fingerprint Dive into the research topics of 'Attributed graph similarity from the quantum Jensen-Shannon divergence'. Together they form a unique fingerprint.

  • Cite this

    Rossi, L., Torsello, A., & Hancock, E. R. (2013). Attributed graph similarity from the quantum Jensen-Shannon divergence. In E. Hancock, & M. Pelillo (Eds.), 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). Springer. https://doi.org/10.1007/978-3-642-39140-8_14