  We develop a novel method for measuring the similarity between complete
weighted graphs, which are probed by means of discrete-time quantum walks.
Directly probing complete graphs using discrete-time quantum walks is
intractable due to the cost of simulating the quantum walk. We overcome this
problem by extracting a commute-time minimum spanning tree from the complete
weighted graph. The spanning tree is probed by a discrete time quantum walk
which is initialised using a weighted version of the Perron-Frobenius operator.
This naturally encapsulates the edge weight information for the spanning tree
extracted from the original graph. For each pair of complete weighted graphs to
be compared, we simulate a discrete-time quantum walk on each of the
corresponding commute time minimum spanning trees, and then compute the
associated density matrices for the quantum walks. The probability of the walk
visiting each edge of the spanning tree is given by the diagonal elements of
the density matrices. The similarity between each pair of graphs is then
computed using either a) the inner product or b) the negative exponential of
the Jensen-Shannon divergence between the probability distributions. We show
that in both cases the resulting similarity measure is positive definite and
therefore corresponds to a kernel on the graphs. We perform a series of
experiments on publicly available graph datasets from a variety of different
domains, together with time-varying financial networks extracted from data for
the New York Stock Exchange. Our experiments demonstrate the effectiveness of
the proposed similarity measures.
