Graph Partitioning on Dirac

Device: Dirac-1

Introduction

One area of study from graph theory is the graph partitioning problem. For these problems, we define the goal on a conceptual level rather than mathematically. The goal being that given a graph, a collection of edges and nodes, to divide the graph into $k$ roughly equal partitions such that the fewest number of edges are shared between the partition. Note that we focus on two-way partitions here, but arbitrary numbers of partitions can be constructed by applying such a scheme repeatedly. Since our software provides an automatic tool to solve this problem, we will not discuss the detailed QUBO formulation that is constructed behind the scenes. The method our code uses is described in this paper, where the basic strategy is to minimize the number of edges between communities under the constraint that they are the same size. Underneath, the code is using the QLCBO formalism, with the minimization of edges between the partitions as the objective, and equal sizes as the constraint. Graph partitioning is used in a range of applications. In this demo, we aim to execute and plot the optimal split of two small graph instances achieved via Qatalyst graph partitioning solver. Using Dirac-1, we specifically focus on partitioning into two partitions.

Importance

The problem of graph partitioning is often related to (and a step toward solving) the more general problem of community detection, which has the goal of understanding the underlying structure, rather than just finding a partition which is optimal in some sense. Graphs, which formally consist of nodes connected by edges, arise in a wide variety of settings. A fundamental reason for the importance of graphs is the importance of pairwise relationships between different entities. For example, in social contexts, whether a pair of people get along is fundamental to group cohesion. Communication also tends to be pairwise. For example, whether devices can directly communicate is usually naturally represented as a graph. Pairwise correlations tend to be very important in statistical analysis, and graph partitioning is a natural problem to consider in many graph settings. The goal is to separate highly connected groups of similar sizes which are less connected between each other. Taking a social example again, if edges represent some level of familiarity, then a graph partition could represent a division into friend groups, for example.

Applications

Although the social context is an intuitive context to explain the graph partitioning problem, directly applying graph partitioning can be met with mixed results, likely because many of these situations include factors that are not directly incorporated in the structure of the graph. There are, however, many important applications where this algorithmic approach is useful. One very important application is VLSI circuit design. Here the goal is to decompose a larger system into subsystems that can be treated separately to make engineering simpler. For such an approach to work well, high-quality partitions are desired where interactions between subsystems are minimized. This division can be performed for a number of purposes. For example, it can be used to physically separate the packaging of components, to simplify modeling and emulation, or to aid in design of underlying software that will be used with the device. Partitioning meshes for simulations on supercomputers is also an important application. In these cases, the goal is to roughly equally divide effort between worker nodes while minimizing communication (which would be represented by weighted graph edges in a graph partitioning problem).

Objective

Partition a graph into $k$ equal size disjoint collections of nodes, while minimizing the number of inter-partition edges (we focus on $k=2$ in this tutorial).

For example, the figure below is an illustration of the Zachary Karate Club social interactions and the partition found using DWave's quantum annealing device.

Qatalyst

I. Imports

Required and complementary imports:

II. Problem formulation

Example problem 1 - an undirected barbell graph instance (formulated via NetworkX):

• 8 nodes per cluster
• 2 nodes connected by edges between the clusters

III. Client request parameters

• alpha, beta: hyperparameters for weighted importance of objective (alpha) versus constraint (beta)
• n_samples: number of samples (size of distribution to collect)
• num_partitions: number of partitions
• sampler_type: "eqc1" or "csample"
• job_type: "graph-partitioning"

IV. Instantiate client, pass job parameters, and execute

• Requirement: QciClient client token
• Preliminary: Use upload_file() of QciClient class instance to upload the problem and retrieve file_id
• Next: Pass file_id, alongside the above parameters, to request body call, build_job_body() of QciClient class
• Last: Execute job with process_job() of QciClient class instance

V. Evaluate solution

In this example, we use our imported helpers package to map and plot our solution. We map the returned solution in res to a list of dicts, as shown below, where:

• 'class': partition index
• 'id': node index:

helpers utilizes its plot_graph_classes() method to loop through the array of dict elements, place each 'id' in one of k solution arrays, where k is the number of partitions, and then plot the array set using networkx.draw_networkx_nodes() (with a designated color set):

Rinse and Repeat

VI. Different graph instance: A random graph instance

Example problem 2:

• Random graph with low-density
• We'll use the same job parameters used in the barbell graph instance.

VII. Execute

VIII. Evaluate solution

Results Summary

We've shown the use of Qatalyst's QciClient class for instantiating and sending a job request for executing graph partitioning on two graph instances. User graph instances are expected to be problem specific, and the "graph-partitioning" job type of the job body should be specified to implement graph partitioning optimization for the input graph instance passed to upload_file() (of the QciClient class instance). Last, we showed that the returned solutions are amenable to the NetworkX draw_networkx_graph() method, which was executed via the imported helpers package, for plotting the graph solution of the input problem instance.

Conclusion

In this tutorial, we have shown how to perform graph partitioning based on quadratic linearly constrained binary optimization (QLCBO) formulation using QCi’s software. A useful next step would be to look at one of the tutorials which uses this formulation more explicitly, listed here. A related graph problem that shares some of these properties is max-cut, which is a graph problem that has a complementary goal of two divisions that are highly connected to the nodes in the other division and may be a good tutorial to read after this one. Of course, another option is to start using our device to solve some of your own optimization problems.