Quantum walk inspired algorithm for graph similarity and isomorphism
- PDF / 2,048,465 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 14 Downloads / 209 Views
Quantum walk inspired algorithm for graph similarity and isomorphism Callum Schofield1 · Jingbo B. Wang1
· Yuying Li2
Received: 10 January 2019 / Accepted: 10 July 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Large-scale complex systems, such as social networks, electrical power grid, database structure, consumption pattern or brain connectivity, are often modelled using network graphs. Valuable insight can be gained by measuring similarity between network graphs in order to make quantitative comparisons. Since these networks can be very large, scalability and efficiency of the algorithm are key concerns. More importantly, for graphs with unknown labelling, this graph similarity problem requires exponential time to solve using existing algorithms. In this paper, we propose a quantum walk inspired algorithm, which provides a solution to the graph similarity problem without prior knowledge on graph labelling. This algorithm is capable of distinguishing between minor structural differences, such as between strongly regular graphs with the same parameters. The algorithm has a polynomial complexity, scaling with O(n 9 ). Keywords Quantum walks · Graph similarity · Graph isomorphism · Quantum inspired algorithms
1 Introduction Many manmade and natural phenomena are modelled using graphs (networks), which show the interconnections between different elements of the systems. These networks have become crucial components in systems which are used in everyday life, e.g. Google’s web page ranking system or social media networks [1]. In many applications, it is essential to provide some degree of similarity between two graphs. A number of different applications of graph comparisons have arisen in a wide variety of scientific disciplines. Some examples include classification of objects for the purposes of machine learning [2], analysis of protein–protein interaction networks [3], mod-
B
Jingbo B. Wang [email protected]
1
Department of Physics, The University of Western Australia, Perth, Australia
2
Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada 0123456789().: V,-vol
123
281
Page 2 of 19
C. Schofield et al.
elling differences in brain connectivity [4] and comparing large-scale databases [5]. Additionally, these networks may need to be continuously compared for similarities. Examples include identification of faces in images or ensuring computer networks remain secure [6]. Algorithms for making inexact comparisons between graphs with known labelling typically have linear or polynomial complexity, such as the DeltaCon algorithm which has, at worst, complexity O(n 2 ) [7]. However, in many applications we do not have the luxury of knowing how to match the nodes (i.e. nodes are not labelled in correspondence). This significantly increases the complexity of comparison algorithms. The unlabelled graph matching problem takes exponential time to compute; additionally, the unlabelled subgraph matching problem is NP-Complete [8,9]. Due to this, the pr
Data Loading...
