Introducing: A quantum subgraph isomorphism algorithm
By Nicola Mariella¹, Anton Dekusar¹, Steve Flinter², Mehrdad Maleki², Prina Patel³, Ryan Mandelbaum⁴
Some computational tasks seem easy on the surface. For example, if I give you a jumble of dots connected by a random assortment of lines, and then give you a shape and ask you to find it in the image, you’re probably going to do a decent job figuring it out. This example isn’t just a toy problem — solving it could help financial institutions uncover money laundering schemes, for example. But this problem is especially challenging for classical computers to figure out.
In technical terms, we call problems like these subgraph isomorphism problems. The subgraph isomorphism problem has applications wherever we can represent data as a network of nodes, also called vertices, connected by lines we call edges. These applications include graph databases, biochemistry, computer vision, social network analysis, knowledge graph query, and in our case, money laundering. This problem is NP-Complete, meaning we don’t know whether there’s an efficient solution for it, but we do know it ranks among the hardest problems for which we can efficiently check whether a proposed solution is correct. Maybe quantum computers can speed things up.
In our recent paper, we devised a quantum computing algorithm for tackling the subgraph isomorphism problem. This isn’t a common problem for quantum algorithm developers to attempt, due to previous research suggesting that quantum solutions to the problem wouldn’t be practically scalable. However, in our new paper, we present a quantum algorithm that, we think, has the potential for a quantum advantage over the best classical methods in the medium term. You can find a corresponding tutorial linked at the bottom of this blog post.
Of course, we must add the Qiskit blog caveat: It’s still not clear whether quantum computers will be capable of efficiently solving (that is, solving in polynomial time) problems in the NP-Complete complexity class, including this one. Many researchers suspect they will not be able to. Instead, we discuss this algorithm in terms of its ability to outperform classical methods, rather than its ability to efficiently solve an NP-complete problem. You can read more about complexity classes and where quantum computers stack up here.
We carried this work out specifically as a joint effort between IBM Quantum and Mastercard to develop a quantum subgraph isomorphism algorithm that could distinguish between money laundering schemes and legitimate business enterprises. Money laundering disguises illegal sources of money, such as illicit arms sales or contraband smuggling, and criminals may undertake it via fraud or by moving the money to less suspicious assets. Money laundering is a complex activity meant to make transactions look like legitimate ones via several steps: placement, where illegal funds are placed into circulation via legitimate financial institutions, layering, where the source is concealed through layers of legitimate financial institutions, and integration, where the funds are integrated as normal business or personal transactions.
Institutions uncover money laundering schemes by analyzing repeated graphical patterns, or motifs, in a transaction network. This network is an undirected graph, one that consists of a finite sets of nodes and directionless edges connecting them, like towns connected by two-way roads or dots connected by lines. The vertices are used to represent accounts, and the edges are transactions between them. By finding specific patterns associated with money laundering, we can identify the illegal source of the money. Finding these repeated patterns in the network is a subgraph isomorphism problem.
We begin by representing this graph with an “adjacency matrix,” where each column (and row) represents a vertex. We set the matrix elements to 1 if an edge connects the vertices represented by the row and column, or 0 if they do not connect. This matrix offers a natural way to represent permutations of the vertices, by simultaneously permuting the corresponding rows and columns.
Then, we have the subgraph — a subunit of the graph. If you imagine a graph appearing like a rudimentary five-pointed drawing of a house — a square with a triangle on top — then a triangle would be a subgraph of this graph. However, a pentagon would not be a subgraph, even though the outer edges form a five-sided shape, because the house introduces connectivity between the vertices that isn’t included in the pentagon.
For these subgraphs, we can find a subgraph isoporphism, a function that, for every pair of vertices linked by an edge in the subgraph, it maps them to a corresponding pair of vertices on the larger graph while preserving that adjacency matrix. With enough permutations, you can find a subgraph’s adjacency matrix inside the graph’s adjacency matrix.
Devising a quantum algorithm for finding subgraph isomorphsims began by translating the adjacency matrix into something we could implement on a quantum computer — that is, turning it into a unitary operator. We introduced a mapping (we detail the mapping more in the paper and tutorial) which “flattens” the adjacency matrix into a diagonal matrix that serves the same purpose. This flattening is key to our speedup, allowing us to represent graphs with millions of nodes using tens of qubits — providing us only a logarithmic scaling as the size of the matrices increase.
Since we created the above mapping for the adjacency matrix, we also needed to create a mapping for the permutation operation acting on this new matrix. We first defined an operator that applies permutations to our untransformed adjacency matrices — an operator that, when multiplied with our adjacency matrix, swaps corresponding vertices and edges. We then placed this permutation operator acting on the adjacency matrix through the same mapping we used to flatten the adjacency matrix alone.
Creating a unitary operator for permutations of the adjacency matrix allowed us to create a subgraph isomorphism algorithm using VQE. We begin with two graphs, a larger graph A and a smaller B. We used these adjacency matrices, transformed, as part of our ansatz for the VQE algorithm. We interpreted this ansatz as a superposition of permutations. This superposition is tuned using parameters set by a classical optimizer. The output of the circuit we designed is a cost function. We used the classical optimizer to minimize the cost function. The function is minimized when the ansatz implements a permutation, or set of permutations, that produces a perfect match between the subgraph of A and the graph B.
We walk through an example of the algorithm below. We start by obtaining the ansatz from each adjacency matrix as follows, which will return a Qiskit QuantumCircuit we can pass to the constructor of the VQE implementation.
In the above figure, we present the block form of the ansatz circuit where we can appreciate the components. The PermAnsatz blocks are the generators of the superposition of permutations which are controlled by the classical optimizer through the vector of parameters θ (not shown). The QAdj blocks instead correspond to the unitary representation for the adjacency matrices A and B, respectively.
For the next step, we analyze the invocation of the VQE process presented in the code snippet below:
In the initialization, we prepare the classical optimizer SLSQP and the random number generator for generating the starting points. The function trial() is the core of the procedure where the VQE is invoked. In such a function, the initial values for the parameters are randomized at each invocation. This is justified by the fact that the optimization problem is non-convex, so the algorithm potentially converges to a different solution at each execution. The latter fact shows that the overall procedure should be interpreted as a sampling of subgraphs rather than an exact matching.
From the above figure, it should become clear how the algorithm works. The algorithm turns the ansatz into a permutation matrix P such that by acting on A’s adjacency matrix A with P and its transpose, we return subgraph B’s adjacency matrix B as the principle submatrix of the newly-permuted A — the top-leftmost values of the transformed A are B’s adjacency matrix, and we have found the subgraph isomorphism in A that B corresponds to. If we don’t come out with a matrix that contains all of B as A’s top-left elements, then either we started with an ansatz that couldn’t represent any of the permutations corresponding to the solutions, the optimizer got stuck on a local minimum, or there was no subgraph isomorphism for the inputted pair of graphs.
You can see a link to our algorithm and dig deeper into how it works in our GitHub tutorial and in this recent paper. We’re exited to see other community members look more closely at the subgraph isomorphism problem and see what other ways we can improve this algorithm to bolster quantum computers’ ability to tackle it.
Author affiliations:
- IBM Research Europe — Dublin
- Mastercard Ireland
- Mastercard UK
- IBM Quantum
