{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Graph Partitioning\n", "\n", "### Definition\n", "\n", "We are given an undirected graph with vertex set $V$ and edge set $E$.\n", "\n", "Our aim is to partition the graph into two equally-sized subgraphs connected by the minimal number of edges.\n", "\n", "\n", "### Applications\n", "\n", "The Graph Partitioning problem comes up in computations on graphs. One can parallelise these computations by performing them on subgraphs of the original graph and then concatenate the final solutions with minimal adjustments. The problem also has applications in biological, social and transportation networks, Very Large Scale Integration (VLSI), Image Processing.\n", "\n", "### Path to solving the problem\n", "\n", "Graph Partitioning is a minimization problem and its cost function can be cast to an Ising problem through its respective Hamiltonian (see the [Introduction](./introduction_combinatorial_optimization_myqlm.ipynb) and a [reference](https://arxiv.org/abs/1302.5843)),\n", "\n", "$$ \\displaystyle \\large\n", "H = A \\displaystyle \\left(\\textstyle\\sum\\limits_{i=1}^{N} s_{i} \\right) ^2 + B\\textstyle\\sum\\limits_{uv \\in E} \\frac{1 - s_u s_v}{2}\n", "$$\n", "\n", "where $A$ and $B$ are positive constants, $v, u \\in V$, $N$ is the number of vertices and $s_i$ is a spin variable, which is $1$ if vertex $i$ is in the one partition and $-1$ if it is in the other. For a valid encoding, the constants $A$ and $B$ need to obey the relation \n", "\n", "$$\n", "\\frac{A}{B} \\geq \\frac{\\min(2\\Delta, N)}{8}\n", "$$\n", "\n", "where $\\Delta$ is the maximum degree of a vertex in the graph. Otherwise, if the rule is not followed, the spin configuration for the lowest energy $H$ may not correspond to the best solution of our Graph Partitioning problem or even to a valid one. At the same time, it should not be overspecified either, i.e. the left side being much bigger than the right side. If the ratio $\\frac{A}{B}$ is too large, this would cause a large energy separation in $H$, impeding our solution approach.\n", "\n", "The myQLM allows us to encode a problem in this Hamiltonian form by using the `GraphPartitioning` class. This class should be provided with a graph, as well as the $A$ and $B$ constants. We can then create a job from the problem and send it to a Simulated Annealer (SA) wrapped with a Quantum Processing Unit (QPU) interface. The SA will minimize the Hamiltonian, hence we find the solution to our problem.\n", "\n", "In fact, the QLM contains an even more powerful solver $-$ Simulated Quantum Annealing (SQA). This quantum annealer has been tested on numerous benchmarks for the NP problems supported and produces results with a quality usually exceeding $98\\%$. More details can be found in the [documentation](https://myqlm.github.io/advanced_combinatorial_optimization.html#simulated-quantum-annealing-benchmarking-and-performance).\n", "\n", "### Quantum resources\n", "\n", "To represent the problem as Ising, myQLM would need $N$ spins (one for each vertex)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Example problem\n", "\n", "Imagine that we are given a graph with $10$ vertices and $18$ edges, as shown below (left). In this case, finding the partitioning may be straightforward. We would only need to remove two edges $-$ one between nodes $1$ and $2$ and another one between nodes $7$ and $8$ (right).\n", "\n", "

\n", "\n", "Let us now describe how one can reach this answer using tools from the QLM. \n", "Furthermore, the approach will be applicable to finding the Graph Partitioning of any graph !\n", "\n", "We will start by specifying the graph using `networkx` and by choosing the constants $A$ and $B$ such that the problem is correctly encoded." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import networkx as nx\n", "import numpy as np\n", "import matplotlib.pyplot as plt\n", "\n", "# Specify the graph \n", "# First example\n", "graph = nx.Graph()\n", "graph.add_nodes_from(np.arange(10))\n", "graph.add_edges_from([(0, 1), (0, 4), (0, 6), (1, 2), (1, 4), \n", " (1, 7), (2, 3), (2, 5), (2, 8), (3, 5), \n", " (3, 9), (4, 6), (4, 7), (5, 8), (5, 9), \n", " (6, 7), (7, 8), (8, 9)])\n", "\n", "# # Second example\n", "# graph = nx.gnm_random_graph(30, 80)\n", "\n", "# Impose constraints for the right encoding\n", "B = 1\n", "A = B + 0.1\n", "\n", "# Draw the graph\n", "nodes_positions = nx.spring_layout(graph, iterations=len(graph.nodes())*60)\n", "plt.figure(figsize=(10, 6))\n", "nx.draw_networkx(graph, \n", " pos=nodes_positions, \n", " node_color='#4EEA6A', \n", " node_size=440, \n", " font_size=14)\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The `GraphPartitioning` class can now be called with this graph as an input and with the constants $A$ and $B$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from qat.opt import GraphPartitioning\n", "\n", "graph_partitioning_problem = GraphPartitioning(graph, A, B=B)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Solution" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Resolution of the problem using a BatchGenerator\n", "\n", "A high level solver of the GraphPartitioning problem is available in the QLM under the form of a BatchGenerator called `GraphPartitioningGenerator`.\n", "It is designed as simple interface to solve the problem on an input graph, while hiding the complexities of the underlying\n", "algorithms.\n", "\n", "The different resolution methods that can be selected are \"qaoa\" (for QAOA Circuit Generation), \"annealing\" (for\n", "Simulated Quantum Annealing), and \"schedule\" (for Analog Quantum Scheduler Generation). A user-interpretable result is\n", "returned from the job execution, where the two resulting partitions of the nodes and the number of edges cut can be retrieved\n", "from the subsets and cost attribute respectively. A display method is also provided by the result object to visualize the\n", "partitioning of the graph.\n", "\n", "An example of using the batch generator to generate a quantum annealing job and executing it with SimulatedAnnealing is provided below." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from qat.generators import GraphPartitioningGenerator\n", "from qat.qpus import SimulatedAnnealing\n", "from qat.core import Variable\n", "\n", "# 1. Extract parameters for SA\n", "problem_parameters_dict = graph_partitioning_problem.get_best_parameters()\n", "n_steps = problem_parameters_dict[\"n_steps\"]\n", "temp_max = problem_parameters_dict[\"temp_max\"]\n", "temp_min = problem_parameters_dict[\"temp_min\"]\n", "\n", "# 2. Create a temperature schedule and a QPU\n", "tmax = 1.0\n", "t = Variable(\"t\", float)\n", "temp_t = temp_min * (t / tmax) + temp_max * (1 - t / tmax)\n", "\n", "graph_partitioning_application = GraphPartitioningGenerator(job_type=\"annealing\") | SimulatedAnnealing(temp_t=temp_t, n_steps=n_steps)\n", "combinatorial_result = graph_partitioning_application.execute(graph, A, B)\n", "\n", "print(\"The nodes in the first subgraph are\", combinatorial_result.subsets[0])\n", "print(\"The nodes in the second subgraph are\", combinatorial_result.subsets[1])\n", "\n", "combinatorial_result.display(with_figure=True, figsize=(10, 6), node_size=440, font_size=14, pos=nodes_positions)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Simulated Annealing\n", "\n", "If we want to solve the problem with SA straight, we can still do so via the following steps:\n", "\n", "1. Extract some fine-tuned parameters for GraphPartitioning (found for SQA) which are needed for the temperature schedule.\n", "\n", "\n", "2. Create the temperature schedule using the `t` time variable (instance of the class `Variable`) and thus the `SimulatedAnnealing` QPU.\n", "\n", "\n", "3. Create a job from the problem by calling the `to_job()` method and send it to the QPU.\n", "\n", "\n", "4. Extract the `Result` and present the solution spin configuration.\n", "\n", "\n", "5. Draw the respective nodes of each subgraph.\n", "\n", "Each spin from the solution configuration corresponds to a node from the graph at the same position. Note that if the numbering of the input nodes starts from $1$ and not from $0$, one still needs to look at the $0$th spin to extract information for this first node, numbered as $1$.\n", "\n", "When a spin has the value of $1$ or $-1$, this means that the respective node belongs to the one or the other subgraph. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from qat.qpus import SimulatedAnnealing\n", "from qat.simulated_annealing import integer_to_spins\n", "from qat.core import Variable\n", "\n", "# 1. Extract parameters for SA\n", "problem_parameters_dict = graph_partitioning_problem.get_best_parameters()\n", "n_steps = problem_parameters_dict[\"n_steps\"]\n", "temp_max = problem_parameters_dict[\"temp_max\"]\n", "temp_min = problem_parameters_dict[\"temp_min\"]\n", "\n", "# 2. Create a temperature schedule and a QPU\n", "tmax = 1.0\n", "t = Variable(\"t\", float)\n", "temp_t = temp_min * (t / tmax) + temp_max * (1 - t / tmax)\n", "sa_qpu = SimulatedAnnealing(temp_t=temp_t, n_steps=n_steps)\n", "\n", "# 3. Create a job and send it to the QPU\n", "problem_job = graph_partitioning_problem.to_job(tmax=tmax)\n", "problem_result = sa_qpu.submit(problem_job)\n", "\n", "# 4. Extract and print the solution configuration\n", "state = problem_result.raw_data[0].state.int # raw_data is a list of Samples - one per computation\n", "solution_configuration = integer_to_spins(state, len(graph.nodes()))\n", "print(\"Solution configuration: \\n\" + str(solution_configuration) + \"\\n\")\n", "\n", "# 5. Show nodes of subgraphs\n", "indices_spin_1 = np.where(solution_configuration == 1)[0]\n", "print(\"The nodes in the first subgraph:\\n\" + str(indices_spin_1) + \"\\n\")\n", "\n", "indices_spin_minus_1 = np.where(solution_configuration == -1)[0]\n", "print(\"The nodes in the second subgraph:\\n\" + str(indices_spin_minus_1))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Solution analysis\n", "\n", "There are a few checks we can perform to decide how well the partitioning went.\n", "\n", "Obviously, we would want the subgraphs to have the same size or as close as possible. However, if the initial graph is too big, visual inspection of the subgraphs may not help. It is therefore more convenient to extract and compare the size of the subgraphs." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "number_of_numbers_being_equal_to_1 = len (indices_spin_1)\n", "number_of_numbers_being_equal_to_minus_1 = len(graph.nodes()) - number_of_numbers_being_equal_to_1\n", "print(\"Number of nodes in one of the subgraphs:\\n\" + str(number_of_numbers_being_equal_to_1))\n", "print(\"Number of nodes in the other subgraph:\\n\" + str(number_of_numbers_being_equal_to_minus_1))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let us also count and show the connecting edges $-$ this is what we want to minimize. For our initial example, they should be $2$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "connecting_edges_list = []\n", "for (u, v) in graph.edges():\n", " if solution_configuration[u] * solution_configuration[v] ==(-1):\n", " connecting_edges_list.append([u, v])\n", "print(\"The number of connecting edges is \" + \"\\033[1m\" + \n", " str(len(connecting_edges_list)) + \"\\033[0;0m\" + \n", " \" and these edges are:\\n\" + str(connecting_edges_list))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Of course, as long as the graph is not too big, we can also visually examine how good the partition is." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "plt.figure(figsize=(10, 6))\n", "node_size = 440\n", "font_size = 14\n", "nx.draw_networkx(graph, \n", " pos=nodes_positions, \n", " nodelist=indices_spin_1.tolist(), \n", " node_color='#FFE033', \n", " node_size=node_size, \n", " font_size=font_size)\n", "\n", "nx.draw_networkx(graph, \n", " pos=nodes_positions, \n", " nodelist=indices_spin_minus_1.tolist(), \n", " node_color='#7B9BF2', \n", " node_size=node_size, \n", " font_size=font_size)\n", "\n", "nx.draw_networkx_edges(graph, pos=nodes_positions)\n", "plt.show()" ] } ], "metadata": { "authors": [ "Grigori Matein" ], "documentation-tags": { "icon": [ "share-android", ":material-outlined:`mobiledata_off;3em`", "workflow" ], "level": "advanced", "other-icon-me": [ "heading", "arrow-both", "strikethrough", "git-branch" ] }, "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.16" } }, "nbformat": 4, "nbformat_minor": 4 }