# 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:

In [1]:

- from qci_client import QciClient
- import helpers
- import numpy as np
- import networkx as nx
- import sys, os
- import matplotlib.pyplot as plt
- %matplotlib inline

### 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

In [2]:

- barbell_graph = nx.barbell_graph(8, 2)
- helpers.plot_graph_plain(barbell_graph)

Out [ ]:

<Figure size 1000x800 with 1 Axes>

### 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"`

In [3]:

- # Constraint-objective hyperparameters
- alpha = 5
- beta = 1
- # Num samples
- n_samples = 1
- # Number of partitions
- num_partitions = 2
- # Job and sampler type
- sampler_type = "dirac-1"
- 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

In [4]:

- token="your_token"
- url = "https://api.qci-prod.com"
- q1 = QciClient(api_token=token, url=url)

In [5]:

- graph_file = {"file_name": "gp_example", "file_config": {"graph": {"data": barbell_graph}}}
- file_id = q1.upload_file(file=graph_file)["file_id"]
- job_body = q1.build_job_body(job_type=job_type, graph_file_id=file_id,
- job_tags=["partition", "example", "!"],
- job_params={"device_type": sampler_type,
- "num_samples": n_samples,
- "alpha": alpha,
- "beta": beta,
- "num_partitions": num_partitions})
- res = q1.process_job(job_body=job_body, wait=True)

Out [ ]:

2024-05-08 10:58:19 - Dirac allocation balance = 0 s (unmetered) 2024-05-08 10:58:19 - Job submitted: job_id='663bbd3bd448b017e54f94be' 2024-05-08 10:58:19 - QUEUED 2024-05-08 10:58:22 - RUNNING 2024-05-08 10:59:11 - COMPLETED 2024-05-08 10:59:13 - Dirac allocation balance = 0 s (unmetered)

### 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:

In [6]:

- results = res["results"]
- best_found_solution = results["solutions"][0]
- solution_dict = []
- for i, part in enumerate(best_found_solution):
- solution_dict.append({'class': part, 'id': i})

`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):

In [7]:

- helpers.plot_graph_classes(barbell_graph, solution_dict, num_classes=2)

Out [ ]:

<Figure size 1000x800 with 1 Axes>

## 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.

In [8]:

- random_graph = nx.erdos_renyi_graph(20, 0.3)
- helpers.plot_graph_plain(random_graph)

Out [ ]:

<Figure size 1000x800 with 1 Axes>

### VII. Execute

In [9]:

- # Upload, build, process
- graph_file = {"file_name": "gp_example_2", "file_config": {"graph": {"data": random_graph}}}
- file_id = q1.upload_file(file=graph_file)["file_id"]
- job_body = q1.build_job_body(job_type=job_type, graph_file_id=file_id,
- job_tags=["example2", "partition", "!"],
- job_params={"device_type": sampler_type,
- "num_samples": n_samples,
- "alpha": alpha,
- "beta": beta,
- "num_partitions": num_partitions})
- res = q1.process_job(job_body=job_body, wait=True)

Out [ ]:

2024-05-08 12:01:16 - Dirac allocation balance = 0 s (unmetered) 2024-05-08 12:01:16 - Job submitted: job_id='663bcbfcd448b017e54f94bf' 2024-05-08 12:01:16 - QUEUED 2024-05-08 12:01:19 - RUNNING 2024-05-08 12:02:07 - COMPLETED 2024-05-08 12:02:10 - Dirac allocation balance = 0 s (unmetered)

### VIII. Evaluate solution

In [10]:

- results = res["results"]
- best_found_solution = results["solutions"][0]
- solution_dict = []
- for i, part in enumerate(best_found_solution):
- solution_dict.append({'class': part, 'id': i})

In [11]:

- helpers.plot_graph_classes(random_graph, solution_dict, num_classes=2)

Out [ ]:

<Figure size 1000x800 with 1 Axes>

## 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.