From Quantum Graph Computing to Quantum Graph Learning: A Survey

One approach to developing universal quantum computing is adiabatic quantum computing (AQC), which relies on the adiabatic theorem that evaluates the continuous-time evolution of a quantum system. To describe the dynamics of an arbitrary quantum system, a class of Hamiltonians is defined

where $\sigma^{z}$, $\sigma^{x}$ are Pauli matrices. Broadly speaking, Eq. 1 can be viewed as a transverse-field Ising model and such model is QMA-complete Albash and Lidar (2018). The first two terms push the quantum bit (qubit) to be either $|0\rangle$ or $|1\rangle$, whereas the last pushes the state to a superposition. An outside measurement leads to the collapse from superposition to a deterministic state. These foundations give the ability for quantum computers to handle certain problems that can not be efficiently solved classically. To implement such models in a real physical process, quantum annealing (QA) captures the relaxation of the adiabatic conditions and controls the continuous-time evolution at finite temperature and in open environments. Machines performing QA at the hardware level attempt to minimize the energy determined by the Hamiltonian, and the output of an anneal is a low-energy ground state, which consists of an Ising spin for each qubit where the eigenvalues $\{+1,-1\}$ of Pauli matrix $\sigma^{z}$ correspond to the binary constraint of the properties of classical Ising model Ushijima-Mwesigwa et al. (2017). This is closely related to the quadratic unconstrained binary optimization (QUBO) problem - a combinatorial optimization problem that can be applied to many graph theoretical problems.

Many NP-hard problems can be expressed as the minimization of the energy of the Hamiltonian as the form of Eq. 1 e.g. graph partitioning, graph coloring, vertex cover and clique finding Lucas (2014). Therefore, varieties of contributions concentrate on relaxing and reformulating these graph-related combinatorial optimization problems into the QUBO formulation and utilizing QA to quickly approach the exact solution. The method in Chams et al. (1987) converts the graph coloring problem to graph partitioning and employs simulated annealing to screen the better solution of the problem. Different annealing schemes are exploited in Silva et al. (2020). These schemes dominate traditional techniques for certain types of graphs with the cost of long computing time. To transform a set of constraints to the energy minimization problem, penalty terms associated with the constraints should be added to the QUBO quadratic expression Silva et al. (2020). Besides, reduction and approximation are necessary for space efficient. Their work demonstrates that the quantum annealer can more reliably approach the optimal solution and produce better heuristics for graph coloring under specific settings.

Existing quantum hardware can only control a relatively small number of qubits, which is far from the size for large-scale data processing. In addition, it is difficult to fully embed real-world optimization problems on quantum devices as a consequence of poor connectivity between arbitrary couples of qubits. As a result, the qubit connectivity in quantum hardware rarely matches the QUBO form described by the underlying graph structure. To overcome these problems, the authors of Bass et al. (2018) present a heterogeneous algorithm that uses classical co-processing to preprocess the primitive problem and randomly selects a large number of possible solutions, after which the reduced form of the max clique problem corresponding to the largest possible solutions can be encoded into the quantum annealer for accelerating the searching process. In Pelofske et al. (2019), a decomposition alternative divides a big input graph into multiple smaller subgraphs that fit the quantum annealer to further improve the adaptability. Other applications also show the benefits of using Hamiltonian to encode and solve graph related problems including graph isomorphism problem Calude et al. (2017); Ushijima-Mwesigwa et al. (2017) and vertex cover problem Pelofske et al. (2019). Likewise, recent works demonstrate quantum annealing has potential advantages over classical approaches ranging from optimization Brady et al. (2021) to machine learning Nath et al. (2021). However, it is difficult to ensure the final quantum state to be the ground state, meaning that the final solution is probably not optimal. Besides, with the increase of the size of the system and the complexity of the problem, it seems reasonable to expect the annealing time to scale exponentially for problems with exponentially small gaps, especially for NP-hard problems Albash and Marshall (2021).

Another way to represent the topological information of graphs in quantum information is quantum random walks (QRWs). Motivated by the widespread use of classical random walks, QRWs view a graph as a collection of nodes in either real or complex space, among which the correlations between two nodes are indicated by edges. The Walker evolves in a quantum mechanical manner over time by characterizing its initial distribution in terms of the amplitudes of quantum states. Compared with classical random walks, where the stochastic transition matrix determines the random patterns, the randomness of QRWs depends on the reversible unitary translation. No internal information could be obtained until the final states are measured. Readers are referred to Kempe (2003); Venegas-Andraca (2012) for introductions on QRWs. Here, we provide a brief overview of the two types of QRWs with typical progress on solving graph related tasks.

The quantum search algorithm, also known as Grover’s algorithm, is first proposed by Grover (1996) at the theoretical level. This algorithm incorporates a superposition of all possible states related to the problem. Then a unitary operator is used to change the amplitudes of each state while maximizing the amplitudes of the desired state which can be extracted by measuring. It is especially suitable for the application scenarios where a set of specific solutions are searched and retrieved in a huge number of candidates. For the function whose output size is $N$, the quantum search algorithm finds the desired input value by using just $O(\sqrt{N})$ evaluations of the function with high probability. In particular, many graph theoretical problems are NP-hard if not even tougher, and the search space grows exponentially with the problem’s size. It is reasonable to handle these problems in terms of quantum computing power.

It is shown in Dürr et al. (2006) that quantum search algorithm decreases the query complexity further for certain graph problems including spanning tree, connectivity, strong connectivity and single source shortest path. In Hillery et al. (2010), the search is performed by quantum random walks to find the marked clique of a complete graph. A novel quantum search architecture Černỳ (1993) is developed to solve the travelling salesman problem (TSP). However, Greenwood (2001) points out this scheme does not mean quantum computers can solve arbitrary NP-hard problems in polynomial time since the number of qubits to represent the superposition states is astronomical. An efficient quantum approach proposed by Srinivasan et al. (2018) combines the quantum phase estimation algorithm Kitaev (1996) with the quantum search algorithm to solve the TSP. It provides a quadratic speedup over the classical brute force method. A breakthrough to achieve quantum speedups for TSP and several NP-hard problems presented by Ambainis et al. (2019) integrates Grover’s algorithm with classical dynamic programming. Despite the fact that quantum search has the potential to solve various complex graph related problems, developing a quantum algorithm that promises to be faster than the best classical algorithm remains difficult, as classical techniques do not always rely on exhaustive search.

By representing the graph’s edges and connected nodes as low-dimensional vectors that preserve global properties of the graph, the subsequent graph analytics tasks can be easily addressed by employing mature machine learning algorithms Goyal and Ferrara (2018). Here we introduce the factorization based approaches and discuss their pros and cons.

Matrix Factorization based Approaches There are a variety of graph learning approaches that represent the correlations between nodes by factorizing the matrix that contains the graph information to obtain the embedding. Different tasks require the factorization of matrices with different properties. Graph Laplacian eigenmaps Belkin and Niyogi (2001) constructs a low-dimensional representation for each node while keeping the smoothness of the distinctness of connected nodes. To circumvent the loss of local topology information, a Cauchy graph embedding method developed by Luo et al. (2011) is employed to preserve the similarity relationships of the original graph data, and introduce a more effective objective function to emphasize the similarity efficacy. However, the factorization of the matrix of the graph with massive nodes often requires huge computing resources. Ahmed et al. (2013) proposes a factorization technique that relies on graph partitioning to enhance scalability.

Random Walk based Approaches Random walk statistics is widely used to capture the graph properties. The latent representation of the node that captures the local structure information is condensed into the low-dimensional feature vector by performing a diffusing process. DeepWalk Perozzi et al. (2014) generates the training data in terms of compressing the graph structure into a text like corpus using random walk, and trains the graph learner to maximize the occurrence probability of neighbors in the walk. Node2vec Grover and Leskovec (2016) employs biased random walk to make a trade-off between breadth-first (BFS) and depth-first (DFS) graph searches, resulting in higher-quality and more informative embeddings than DeepWalk. Qiu et al. (2018) shows that many random walk based approaches also perform implicit matrix factorization, since the requirement of the specific adjacent matrix or Laplacian matrix before performing learning. Most of these methods are inherently transductive.

Inspired by the kernel methods which utilize a linear classifier to solve non-linear problems, graph kernel methods have been widely used for graph-level tasks, e.g., classification and clustering. They directly compare the structures of the subgraphs by defining a user-specific similarity metric or a meaningful distance measurement on graphs. In contrast to the factorization based approaches representing the graph information as low-dimensional vectors, graph kernel methods characterize graph features implicitly in a high dimensional space. It involves performing pairwise comparisons between local substructures centered at every node.

Most early graph kernel works belong to the family of R-convolution kernels Haussler (1999). More recently, Tian et al. (2019) shows a kernel-based framework to produce hidden representations of nodes, bridging the gap between graph kernel methods and graph neural networks. Chen et al. (2020) combines the message passing mechanism with the graph kernel and constructs a convolutional kernel network to represent the graph effectively. The high computational complexity of graph kernel methods suppresses their applicability. While it is still valuable to study the theoretical framework behind the graph learning approaches using graph kernel methods due to their inherent transparency and interpretability.

For graph learning, Graph neural networks (GNNs) are a type of deep learning method for extracting the pattern of graph structural data, which dominate the literature.

Recurrent Graph Neural Networks The initial trial of the GNNs is recurrent graph neural networks whose foundations relate to the information diffusion mechanism. In the prototype Scarselli et al. (2008) of recurrent graph neural networks, the node hidden embedding is updated by the adjacent neighbors. This process continues until a stable equilibrium is reached. A gated recurrent unit (GRU) is used as a recurrent function in a gated graph neural network (GGNN) Li et al. (2016), restricting the recurrence to a few steps.

Convolutional Graph Neural Networks A number of convolutional graph neural networks can be categorized into a general framework named Message Passing Neural Network (MPNN) Gilmer et al. (2017). The forward pass of these models has two phases - an aggregation phase and an update phase - that run iteratively to let information propagate further. The aggregation phase serves to detect (multiple) patterns in multiple sub-regions of the input graph, while the update phase generally consists of pooing functions that collapse the hidden features of interrelated sub-regions into a new vector representation. Some studies perform graph convolution operation building upon the signal processing on graphs Shuman et al. (2013).

Similar to the classical graph kernel methods, quantum kernels (QK) on graphs aim to decompose the graph into substructures and compare the similarity between each pair of substructures specified in terms of their quantum representations. The Quantum Jensen–Shannon Graph Kernel (QJSK) Bai et al. (2015) infers the graph properties using the density matrix description constructed by CT-QRWs. The authors develop an aligned version of the QJSK to preserve the permutation invariance and more correspondence information between pairs of nodes in the graph. Additionally, they generalize their ideas by probing the graph structure using the DT-QRWs Bai et al. (2017). In Schuld et al. (2020), the authors present the potential of encoding the graph information in the quantum Hilbert space using the derivation of Gaussian Boson Samplers Kernel (GBSK). The information of all possible subgraphs can be obtained by sampling instead of counting the appearance of specific substructures classically. A specific kernel encoding the feature of all subgraphs (SFGK) Kishi et al. (2021) investigates how to utilize the power of quantum superposition to encode every subgraph into a feature space. The major disadvantage of their model is that the similarity between the superposition states is hard to estimate, thereby limiting the model capacity. The Hamiltonian encoding approach is further exploited in the Quantum Evolution Kernel (QEK) Henry et al. (2021) to represent the topology of the input graph. A particular graph kernel generated by performing the quantum evolution followed by a carefully chosen observable is able to characterize graphs in a real quantum computer.

Most classic graph learning techniques are motivated by graph-free models such as kernel methods and CNNs. New generalizations and definitions of important operations have been developed to handle the complexity of graph data Wu et al. (2020). As a result, some studies use quantum computing to efficiently duplicate procedures resulting from classic graph learning. It seems to be essential to build effective embedding approaches that encode the classical data into their quantum representations while keeping as much of the original information as possible Huang et al. (2021); Schuld (2021). Besides, the embedding phase contributes the most nonlinear transformations Schuld and Killoran (2019) and is the basis of the quantum speed-ups claimed by many quantum machine learning algorithms Biamonte et al. (2017). Therefore, new methods should be developed to handle embedding efficacy. For learning on graphs, the permutation invariance of node orderings should be also carefully considered when transforming original graphs into their quantum expressions. The shallow circuit learning method is a kind of quantum algorithm based on the current noisy intermediate-scale quantum (NISQ) devices, which encodes the original data into their quantum representations and approximates the objective function by adjusting the learnable gate circuit parameters Schuld (2021). Generally the shallow circuit can be divided into two parts where the embedding circuit is responsible for encoding the data into quantum Hilbert space and the following parameterized processing circuit is used to extract hidden features from the feature space.

Verdon et al. (2019) introduces a quantum graph neural network (QGNN) that treats the interaction of qubits as the nodes connected by edges. The entire graph thereby can be expressed by a quadratic Hamiltonian, which implies that we can think about quantum circuits with graph-theoretic properties. Their numerical results limited to small-scale experiments show several potential applications such as spectral clustering and graph isomorphism classification. While more recently, it has been successfully applied to graphs with node features in Zheng et al. (2021); Ai et al. (2022). However, their methods suffer the computational cost as a result of quantum tomography, resulting in the massive resource overhead. Mernyei et al. (2021) constructs an equivalent quantum graph circuit (EQGC) whose topology preserves permutation invariance of the input graph. But the number of the qubits scales linearly with the number of nodes, and the prediction accuracy closely depends on the fidelity of the measurements. An alternative approach devised by Beer et al. (2021) uses qubits as neurons to characterize the graph as quantum states. They design a quantum neural network (QNN) trained on a well-designed loss evaluated by the fidelity of quantum representations of connected nodes.

While GNNs represent state-of-the-art classical machine learning for a range of benchmark tasks on graphs, there is no clear proof of quantum advantages for tasks on classical graph-related datasets in extant quantum neural networks. Therefore, some experts pin their hopes on developing approaches that combine the expressiveness of the classical learning methods with the power of quantum modules to improve the performance of existing models. A hierarchical neural network based on QRWs (QWNN) is developed by Dernbach et al. (2018) with a series of coins. The different setting of coins allows the quantum walks to behave differently in terms of extracting various properties of graphs. A classical diffusion process is employed to intersperse the information along with the composite form of position distribution generated by different quantum walks. Another quantum information propagation approach presented by Bai et al. (2021) captures the multi-scale node features by employing the mixing matrix of CT-QRWs instead of directly using the adjacency matrix. QRWs are employed to select the more relevant neighbors of the center node to achieve a more efficient information diffusion process in the quantum subgraph convolutional neural network (QSCNN) Zhang et al. (2019). Chen et al. (2021) develops a composite model (QGCNN) to perform convolutional and pooling operations on graphs in which the parameterized quantum circuit tailed by the fully connected neural network is used to approximate the learning function. A hybrid GNN (HQGNN) is applied for particle track reconstruction Tüysüz et al. (2021), consisting of variational circuits to improve expressiveness.