Quantum walk inspired algorithm for graph similarity and isomorphism

Large scale complex systems, such as social networks, electrical power grid, database structure, consumption pattern or brain connectivity, are often modeled using network graphs. Valuable insight can be gained by measuring the 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 labeling, 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 labeling. This algorithm is capable of distinguishing between minor structural differences, such as between strongly regular graphs with the same parameters. The algorithm has polynomial complexity, scaling with $O(n^9)$.

The paper is organized as follows. In §II, we introduce graph comparison problems and discuss the properties required for a graph similarity measure. The proposed coin quantum walk algorithm for graph similarity measure computation is described in §III. In §IV, we present computational results on a variety of graphs to illustrate the proposed method. Concluding remarks are in §V.

A. Graph Comparison
Graph similarity measures are based on comparisons made between the structure of graphs.
Comparison metrics are used to define the distance between graphs or a graph similarity index.
Let G 1 (V, E 1 ), G 2 (V, E 2 ) be two graphs defined by a set of vertices V and edge sets E i , i = 1, 2.
Although the concept of similarity between two graphs may be intuitive, differing similarity measures tend to produce different results due to differences in how the structures of the graphs are analyzed. In some applications, a binary answer to whether graphs match or not is insufficient, especially if the input graphs are incomplete or contain noise. For graphs which only match approximately, it is useful to be able to determine a measure of similarity. For example, classification techniques in machine learning match objects that are within a certain tolerance level. It is desired that a similarity algorithm returns a score which indicates a degree of how the structures of two networks differ, while also being able to detect slight changes between them.

B. Classical Graph Comparison Techniques
We first review a few existing classical graph comparison techniques.

Maximum Common Subgraph
Maximum common subgraph techniques involve finding the largest subgraph structure that is common (isomorphic) between the two graphs. If two graphs are isomorphic, their nodes can be relabelled in such a way that they are equivalent (G 1 ∼ = G 2 ). Similarity metrics that utilise this technique define graphs with larger common subgraphs as being more similar. One such distance where n[G] denotes the number of nodes in graph G, and mcs(G 1 , G 2 ) is the maximum common subgraph of G 1 and G 2 . Note that as this metric defines the distance between graphs a smaller value would denote a higher similarity.

Graph Edit Distance
The graph edit distance between two graphs is defined as the number of changes that would be required to make two graphs the same. These changes include relabelling vertices and adding or removing vertices and edges [8]. Additionally, each action can be attributed a weighting to provide variation to the resulting similarity measure. For example, a minimum of four changes would be required to make graph (a) in Figure 1 equivalent to graph (b).

Graph Eigensystems
The eigensystems of graphs can also be utilised to define the distance between two graphs. For example, consider two undirected graphs G 1 and G 2 with adjacency matrices A and B respectively.
Umemyama [14] defines the shortest distance between G 1 and G 2 by minimising: where P is a permutation matrix which represents a map which relates the nodes in G 1 to those in G 2 . This permutation is optimal for the shortest distance, which is found by using the eigen decompositions of A and B.
The algorithm makes comparisons on the pairwise node affinities of graphs. Due to these pairwise comparisons, the graph must have known labelling. A matrix S is constructed, using Equation (4), such that S ij indicates the influence of node i on node j: where I is the identity matrix, D is the diagonal degree matrix (d ii is the degree of node i) and A is the adjacency matrix. The distance and similarity between two graphs is then defined by where d is the Matusita distance between the node affinities. This distance is used in order to boost the graph node affinities, which increases the sensitivity of the metric. The resulting similarity score is in the interval [0, 1].

C. Axioms
The given distance between a pair of graphs relies on the similarity method used. It is not necessarily the case that two metrics will return the same similarity score. The requirements of the similarity metric would also differ between applications. However, Koutra et al. have formalised a set of axioms that graph similarity measures should conform to [7]: A2 Symmetric: sim(G 1 ,G 2 ) = sim(G 2 ,G 1 ).
Another important requirement raised by Koutra et al. is that the algorithm used must be scalable [7]. Many applications require lots of comparisons to be made on large graphs, thus the similarity algorithm must be able to compute comparisons efficiently on large sets.

D. Graph Representations
A graph, denoted by G(V, E), consists of a set of vertices (or nodes) V , representing position states, and a set of edges E, denoting connections between vertices. A graph can be described via a n × n adjacency matrix A: Note that for undirected graphs, the adjacency matrix is symmetric (A ij = A ji ). More generally, a real valued weight A ij can be assigned to the edge {i, j} ∈ E. The degree d i of the node i, in an undirected graph is, Since the unlabelled graph matching problem is NP-Complete [8,9], existing solutions to measure graph similarity would take exponential time to compute. Next we propose a coined quantum walk solution.

A. Coined Quantum Walk
Classical random walks, which are stochastic processes, can describe the path of a random walker on a graph. The quantum analogue, quantum walks, describe the time evolution of the probability state of a walker on a graph. Both discrete and continuous time formulations of walks exist, however we will restrict the discussion to the former.
At each time step, a classical walker flips a "coin" to determine which direction to move in next.
Similarly, every step in a quantum walk involves applying a coin operatorĈ, then translating the system according to the coin state via the translation operatorT [15].
Consider an arbitrary graph described by the adjacency matrix A. The coined quantum walk formalism is restricted to undirected graphs. For a graph with n nodes, there are n position states labelled |v x ≡ |x . The degree of each position state |x gives the number of coin states |c . This is equivalent to a walker having d x paths to choose at position |x . Each node has a local coin operatorĈ x , represented by a d x × d x matrix.
As the algorithm must work for graphs with unknown labelling, the coin operator used must not have a bias with respect to the neighboring nodes. This means that the coin operator must be constructed such that it will produce the same result for all combinations of labelled nodes. This constrains each coin to be in the form [12]: where a, b ∈ C. One such unitary operator which keeps the symmetry with respect to its neighboring nodes is the Grover coin: where d is the degree of the corresponding node and δ ij is the Kronecker delta function.
Considering an edge e xy connecting nodes x and y, one formalism of the 1-D quantum walk to a 2-D graph defines the translation operator as the unique mapping from one state to another along where d x,i is the ith neighbour of x. To achieve this, Watrous proposed to label the coin states of each node via the edges connected to it [16]. This allows the system to be represented by the set of nodes x and edges connecting pairs of nodes e xy . The state of the system is then represented in general as where α xy denotes the probability amplitude of the walker at node x transitioning to y, which satisfies the normalization condition such that x,y |α xy | 2 = 1. The translation operator is then defined by shifting the walker along an edge: T |x, e xy = |y, e yx .
The quantum walk is then carried out via repeated application of the coin and then translation operator, such that after t time steps the state of the system is given by: After observation, the probability the walker is at node x is given by: Not knowing the node labelling also requires us to ensure that there is no bias between nodes.
To do this, the initial state is constructed in equal superposition, as in equation (17). For simplicity, the coin states |e xy are denoted as |e xj , where j = 1, . . . , d x , and |e xj is the jth outgoing edge of vertex x. Thus B. Graph Comparison Score The graph isomorphism algorithm developed by Douglas and Wang [12] generates graph comparison scores, an integer value that can be used to make comparisons between graphs. These comparison scores are calculated by comparing the time evolution of quantum walks on the graphs.
In some cases, such as strongly regular graphs with the same parameters, a simple quantum walk is not sufficient to distinguish between their structure. To alleviate this, a phase is added to a number of reference nodes in each graph, which produces a new level of interaction in the walk [12]. This interaction helps break symmetries in the graph.
We adopt a two-node phase addition scheme, chosen as it is the fewest number of reference nodes required to distinguish SRGs [12]. Consider two input graphs, A and B. Let i, j ∈ A and k, l ∈ B be the chosen reference nodes, as in Figure 2. Denote two phases φ, θ. At each step of the walk these phases are applied to the reference nodes: The phase values chosen must be in the range (0, 2π), with φ = θ. The phase values should also be sufficiently different to ensure that each reference node is distinguishable. The similarity measure result is also not entirely independent of the chosen phase values. However, for sensible values of phase the influence is minimal, generally resulting in a range of at worst ±0.05 in similarity score.
Additionally, this is not an issue if the particular application only requires to know the relative similarity between sets of graphs, assuming the phase is kept consistent.
A graph comparison 4-D matrix is constructed by making comparisons between the probability amplitudes of each pair of reference nodes at every step of the walk. To ensure that the complete structure of the graph is explored by the walker, it must complete at least twice as many steps as the diameter of the graph, which is the maximum shortest path between all pairs of nodes in the graph. The graph comparison score is then defined as the sum of the elements in D, where and d xy is the distance between the probability amplitude sets of reference nodes x ∈ A and y ∈ B.
For testing purposes a number of different distance measures have been tried (see §III C for details).
As the labelling of each graph is not known, the probability amplitudes need to be compared for all unique combinations of {i, j, k, l}. If the two nodes match up, or are similar, they are given a low score. The full comparison matrix has n 4 elements, however this can be reduced due to the symmetry in the adjacency matrices. As we are applying the same phase to each pair of reference nodes, and the difference in the response is independent of the phase applied, testing combinations of {j, i} will give the same results as {i, j}. Thus, the number of comparisons necessary can be reduced to with applied random phases θ and φ. The comparisons d ik and d jl are defined between probability vectors prob i ↔ prob k and prob j ↔ prob l respectively. The comparison score is determined by the sum of all unique combinations D ijkl = d ik + d jl .

C. Distance Metric
We compare the probability amplitudes at the reference nodes using a variety of distance measures. In the following, we denote the set of probability amplitudes of reference node i as prob i with input graphs G 1 and G 2 , where {i, j} ∈ G 1 and {k, l} ∈ G 2 . The first measure is used by Douglas and Wang in their graph isomorphism algorithm [12].
1. Euclidean distance with threshold: The thresholding method is useful in the graph isomorphism case, where we require a sensitive metric to determine whether two graphs are isomorphic. However, graph similarity is not a binary problem and we lose significant information regarding the differences between the two graphs when thresholding the results. Thus, removing thresholding from the graph isomorphism algorithm would likely improve the graph similarity performance (while possibly reducing its effectiveness at determining graph isomorphism for extreme cases such as SRGs). In addition to the Euclidean distance, two other metrics have been tried in an attempt to increase the sensitivity of the algorithm. The Euclidean distance squared metric boosts the distance between each pair of probability vectors by squaring the Euclidean distance between them. The Matusita distance metric boosts the probability vectors before the comparison is made. The precise definitions for these three metrics are given below.

nSteps .
As the sum of the probabilities at each time step must equal one, the Euclidean difference between the probability amplitude of two nodes would be in the range [0, 1]. A value of 0 would denote the probability of finding the walker at both reference nodes as being the same at all time steps. Thus, the distance between the two sets of probability vectors corresponding to a pair of reference nodes would be in the range [0, nSteps]. As we do not want the similarity metric to be dependent on the number of steps the walker takes, the distance is normalised with respect to nSteps. Since D ijkl is given by the sum of the distance between two pairs of reference nodes, it is in the range [0, 2].

D. Similarity Metric
Consider the comparison between two input graphs, A and B, with a graph comparison score D AB . This score will be finite and non-zero, regardless of the input graphs. In order to be consistent with the identity axiom (A1), we need to compare D AB with the resulting comparison score assuming A was isomorphic to B. This is determined by calculating the comparison score between A and an isomorphic permutation of A (denote this A , and the resulting comparison score D AA ). Similarly the comparison score D BB is calculated. If D AB is equivalent to both D AA and D BB , the input graphs are said to be isomorphic [12].
The distance between the input graphs (A and B) is then defined to be the normalised difference between D AB and the corresponding isomorphic comparison scores, i.e.: while the similarity metric is given by: We summarize the proposed coin quantum walk graph similarity measure computation in Algorithm 1. of reference nodes must be tested, thus the algorithm which calculates three comparison scores scales with O 3n 8 (n − 1) 2 = O(n 9 ). Thus, assuming that each operation has O(1) complexity, this algorithm has polynomial time complexity.

A. Sample Random Graphs
A variety of different random graph models have been utilised to test the algorithm against the graph similarity axioms and properties. Additionally, this will determine whether the algorithm has a bias towards certain graph structures. All random graphs used for testing have been generated using Mathematica. Graphs referred to as "Random graphs" are generated using a uniform distribution (the probability density function of vertex degree is uniform). These graphs will be denoted as R(n, e), where n is the number of nodes and e is the number of edges in the graph.
Other sets of graphs used to test the graph similarity algorithms are detailed below.

Erdős-Rènyi Graphs
Random graph theory was pioneered by P. Erdős and A. Rènyi in 1959. Erdős-Rènyi graphs are constructed by choosing whether or not to add an edge connecting every pair of nodes using probability p [17,18]. The choice for each edge is independent to all other connections. Erdős-Rènyi random graphs will be denoted using ER(n, p) where n is the number of nodes and p is the probability that any two nodes are connected. These graphs have been used in practice to describe and analyse complex topological networks, such as modelling epidemics as a dynamical computational networks [19].

Scale-Free Graphs
Albert et al. first discovered the scale-free nature of networks which model the topology of the world-wide web (WWW) in 1999. These networks follow a power law degree distribution where the probability P (k) of a node connecting with k other nodes scales with P (k) ∼ k −γ for some constant γ [20,21]. Such networks maintain this power law distribution regardless of the number of nodes. This scale-free property was subsequently found in other networks describing real world systems, such as cellular protein-protein interactions [22,23], brain activity [24], and interaction in social networks [25].
Scale-free networks are constructed by starting with a small graph and repeatedly adding nodes.
Each new node added is connected to m other nodes already in the network. This scheme provides preferential attachment, as nodes will be more likely connected to nodes with high connectivity [26]. Scale-free graphs will be denoted SF (n, m), where each new node added is connected to m other nodes and the total number of nodes in the network is given by n.

Strongly Regular Graphs
A k-regular graph with n nodes is said to be strongly regular if all adjacent nodes have λ common neighbours and all non-adjacent nodes have µ common neighbours [27]. Due to this structure, it is difficult to distinguish between SRGs with the same parameters (n, k, λ, µ). This provides a good benchmark to test for isomorphism to ensure a similarity measure correctly distinguishes between similar graph structures. Strongly regular graphs with parameters (n, k, λ, µ) will be denoted SRG(n, k, λ, µ).

B. Isomorphism and Identity Testing
The identity axiom (A1) is a key property of the graph similarity metric. It is expected that the algorithm will output "1" when the two input graphs are the same. As mentioned above, SRGs with the same parameters (n, k, λ, µ) are difficult to distinguish, which make them a good baseline for testing the algorithm. These tests are used to confirm the similarity measure can correctly distinguish whether a pair of graphs differ in any way.   Table I gives the resulting similarity score when comparing a number of different SRGs from the same family. These same graphs have also been compared to themselves, all returning a similarity of 1. Thus, the algorithm successfully reproduces the identity axiom for these SRGs. Note that it is also expected that as the number of nodes increases, the similarity score will increase.

C. Graph Similarity Testing
To test the graph similarity metric, we make comparisons between an input graph and a modified copy of this graph. Changes are made by randomly removing edges from the original graph. The graph similarity score is expected to decrease as edges are removed. Figure 7 demonstrate this trend for a variety of input graphs. For each number of edges removed, a statistical ensemble of graphs were generated for comparison. The variation in each of these sets of comparison scores would be due to the variations in structure created by removing different edges. The comparison score for each set is averaged, given by the solid lines in the plots. As we are more interested in how the similarity metric responds to small changes in graph structure, for each data set, we use a smaller step size at the beginning when removing edges.
As each input graph is generated with respect to the original graph, we can match the nodes between the graphs. This allows us to compare our algorithm with a classical graph similarity technique, such as DeltaCon. Note that we did not conduct this comparison with DeltaCon for SRGs in the previous section, due to the exponential time required by DeltaCon to match the nodes between the comparison graphs. Results are shown for thresholding (blue), Euclidean distance (orange), Euclidean distance squared (green), Matusita distance (red) and DeltaCon (purple). Solid lines denote average score (cont.).

V. DISCUSSION AND CONCLUSION
It is clear from Figure 7 that thresholding the distances does not provide sufficient sensitivity in the comparison measure. The comparison score remains at approximately 0.9 until a sudden drop to 0. As such, this distance metric would likely only be suitable for distinguishing between significantly different graphs. The other distance measures all give a gradual decrease in similarity score, decreasing faster for the larger number of changes (denoted as C). This is in contrast to the DeltaCon measure, which is more sensitive for small C and begins to plateau as C increases.
These two profiles likely represent different approaches to the graph similarity concept. The coined quantum walk metric gives results which are possibly more intuitive, as the graph structure is not likely to change significantly for small C (at least not for Erdős-Rènyi graphs) so the similarity should gradually decrease until there are no more edges to be deleted. However, DeltaCon suggests that making a few changes has a greater influence on the graph structure with respect to the previous set than for large C. Whether this model is better than our quantum walk inspired model would depend on how the similarity between graphs is defined and the application requirements.
There is also a clear divide between Matusita and Euclidean distance measures, with the Matusita distance giving the least sensitive response. This metric boosts the difference in probabilities, which would increase the comparison score between graphs. However, this does not translate to a greater sensitivity in the similarity comparison, likely due to the boosted score being counteracted by the normalisation process. The Euclidean measures give roughly the same response as the Matusita measure for small C, but becomes more sensitive as C increases. The Euclidean square measure has greater sensitivity, but at the cost of having a greater variation. This suggests that this measure is either more sensitive to graph structure changes or less accurate. Due to the fact that DeltaCon is relatively consistent, it is more likely the latter. The square metric could be useful if the application requires sensitivity to small change in graph structure only, otherwise the Euclidean measure is likely more suitable.
Overall, the coined quantum walk algorithm does not provide very good sensitivity for small C; however, this could be attributed to these changes resulting in little difference in overall graph structure leading to a very similar score. In some cases, such as Figure 7e, the similarity score is relatively constant for a large range of C (in this case, 10 to 50 changes). The algorithm however is able to distinguish very similar graphs from less similar graphs. This would be useful in applications which do not require a high sensitivity for small C, such as in machine learning or pattern recognition tasks. It could also be used to aid other processes, such as a preprocessing step to filter out comparisons which are significantly different, while another algorithm (which may have a greater time complexity) is used for a finer sensitivity.
The coined quantum walk algorithm successfully satisfies the three axioms described by Koutra et al. The identity algorithm has been shown to work for all investigated distance measures using the two reference node scheme. The second axiom is also fulfilled due to the algorithm design, as the input graph order has no effect on the final result. For two graphs with decreasing similarity, the graph comparison score will increase as a reduced number of reference node combinations provide a similar response. As two graphs tend towards being completely different (i.e. a complete graph compared with an empty graph), the comparison score will tend towards O(n 4 ). As this comparison score is likely much greater than the normalisation between each individual graph, the similarity between the graphs would become negligible. This has been confirmed by comparing complete and empty graphs, which return similarity scores of order O(10 −18 ), which is within precision error. The axiom is also substantiated by the results in Figure 7, as the similarity score tends to zero as C increases. This can be compared to the classical DeltaCon algorithm, which plateaus at some similarity score.
In conclusion, this paper proposes a quantum walk inspired algorithm designed to compute graph similarity measures in polynomial time with complexity O(n 9 ). The algorithm is capable of determining minor changes to significantly similar graph structure, such as determining isomorphism in strongly regular graphs. The algorithm also satisfies the axioms outlined by Koutra et al. [7]. It is worth noting though that the proposed quantum walk model only works for undirected graphs. Consequently, the proposed algorithm to compute graph similarity measure naturally has this restriction as well. Alternative quantum walk models would need to be explored to develop an algorithm that is compatible for directed graphs.

VI. ACKNOWLEDGEMENTS
This work was supported by resources provided by The Pawsey Supercomputing Centre with funding from the Australian Government and the Government of Western Australia. YL acknowledges funding from the National Sciences and Engineering Research Council of Canada.