Measuring the similarity of graphs with a Gaussian boson sampler

Gaussian boson samplers (GBSs) have initially been proposed as a near-term demonstration of classically intractable quantum computation. We show here that they have a potential practical application: Samples from these devices can be used to construct a feature vector that embeds a graph in Euclidean space, where similarity measures between graphs—so-called graph kernels—can be naturally defined. This is crucial for machine learning with graph-structured data, and we show that the GBS-induced kernel performs remarkably well in classification benchmark tasks. We provide a theoretical motivation for this success, linking the extracted features to the number of $r$ matchings in subgraphs. Our results contribute to a new way of thinking about kernels as a quantum hardware-efficient feature mapping, and lead to a promising application for near-term quantum computing.

Figure 1

Idea of the quantum hardware-induced feature map. The adjacency matrix of a graph gets encoded into the Gaussian state of the light modes by tuning the squeezing and interferometer parameters. The features are defined as the probability of detecting certain classes of photon counting events. To extract the probabilities from the device, a number of samples of photon counting events is generated and the relative frequencies of the different classes determined.

Figure 2

All nonisomorphic graphs up to size $\left|V\right|=6$ and the number of perfect matchings they contain (grey shading scale).

Figure 3

Example of a perfect matching (left) and a two-matching (right). The two-matching is at the same time a perfect matching of the subgraph highlighted in grey.

Figure 4

Coarse-grained probability $p\left(O_{\mathbf{n}}\right)$ where $G$ is a random unweighted graph on ten vertices. We compare the lossless scenario (red) with a lossy case (blue) of $3\mathrm{dB}$ photon loss ($\nu =0.5$ in (12)). The squeezing is the same in both cases and its maximal value is $6.2\mathrm{dB}$. The orbits $O_n$ on the $x$ axis are first ordered according to the total photon number $\left|n\right|$, and then in ascending order of the single-detector photon numbers, i.e. $[0,0,0...],[1,0,0...],[1,1,0...],[2,0,0...],...$. A major tick on the $x$ axis counts 100 orbits. The gaps of the total odd photon numbers for the red curve indicate zero probability which is consistent with the single-mode squeezed states occupying the even subspace of the Hilbert space of Fock states.

Figure 5

Dimensionless histograms of node and edge numbers of graphs in the benchmark data sets to visualize the relative shapes of the class distributions (plotted in different colors). The number of graphs as well as its percentage with respect to the original data are shown below each plot. ${}^{*}$Some classes in Fingerprint were excluded due to insufficient samples of small graphs.

Figure 6

Three measures for feature importance for IMDB-BINARY (top row) and MUTAG (bottom row) using $k=6$ and for $d=0,d=0.25$, and $d=1$. The $3+3$ heat maps consist of three columns each. The leftmost column (gray color map) shows the average of each feature for the two different classes, here labeled $A$ and $B$. The center column shows the coefficients with which each feature contributes to the four first-principal components in the PCA analysis. The third column shows the weights which a perceptron attributes to each feature when trained to classify the target labels.