在 DWave Quantum Annealer 上运行离散二次模型的图划分

量子退火器是一类可以帮助解决NP-hard和NP-complete问题的量子计算机。下面是一个对社交网络、推荐系统等具有实际意义的例子。

图是由一组由边连接的节点组成的数据结构。图无处不在:它们可以代表朋友之间的网络，工厂和商店之间的联系，机场，等等。在许多可以应用于图的操作中，以提取有用的信息(这本身就是一个巨大的兔子洞)，可能最明显的一个是划分，即根据一些相似性或距离标准将N个节点划分为K组。其主要思想是，一旦确定了组，属于给定组的节点之间的关系要比属于其他组的节点之间的关系更紧密。

一种完善的聚类方法称为无监督k均值聚类方法，该方法将每个观测值分配到具有最近质心的聚类中(即聚类的多维平均值)。该算法的一个通用实现可以在scikit-learn python库中找到。

然而，K-means并不是故事的结尾。这篇文章中讨论的方法是基于一种称为二次无约束二元优化 (QUBO) 的优化方法，由于它与 Ising 能量函数的联系，是解决量子绝热退火器 NP 难题的主要方法，反过来 描述了这种计算机背后的物理原理。在 QUBO 公式中，问题由一组二元变量 q_i（例如 0 或 1、-1 或 1）、恒定权重 C 的方阵和我们希望最小化的目标（成本、损失）函数来描述 找到最优的 q_i：

在图划分方面，权重C_ij是预先计算的，例如它们表示TF-IDF文档嵌入之间的地理距离或余弦相似度。q_i是在最小化过程中找到的，表示解。通常我们需要处理退化解，也就是不同的q_i集合同样能使y最小化。

这些讨论的一个关键部分是“不受约束”这个词。不受约束意味着目标函数不受约束。举个例子，一个约束条件是(q_i - 1)²=1。Glover等人的QUBO模型指南中有一长串例子。无约束意味着必须在原始方程中加入一项来包含约束，乘以一个常数拉格朗日乘子β，例如，y ' = y + β*(x - 1)²。问题是，y '的最终方程必须仍然是一个QUBO方程，这样约束就可以在更新的权值矩阵C '的定义中被重新约束。

要在 QUBO 术语中设置图分区问题，第一步是确定二进制变量代表什么。在这种情况下，一种常见的方法是将 K 个二进制变量分配给每个节点，并将它们解释为一个独热向量，也就是说，如果第 i 个节点的第 j 位为 1，其他所有位均为 0 ，则节点被分配到集群（j+1）。

 Node | q_i0 | q_i1 | q_i2 |
  1   |  0   |  1   |  0   |
  2   |  1   |  0   |  0   |
  3   |  0   |  1   |  0   |
  4   |  0   |  0   |  1   |

首先，我们需要定义要最小化的目标函数。在一种常见的方法中，结果是不同集群之间的简单连接数。我们不会限制集群内连接的数量。这只是通过询问一对节点 i 和 j 来实现的，它们都必须属于集群 k 或不属于集群 k，这是一个异或逻辑门。在 QUBO 世界中，XOR 门的等价物有点棘手。我们想要最小化由两个变量 q_ik 和 q_jk 构造的数量。它们的和是 2 或 0，它们的乘积是 0 或 1。因此，下面的组合满足要求：

 y = q_ik + q_jk - 2 * q_ik * q_jk
 
 q_ik | q_jk | sum | -2*prod | y
   0  |   0  |  0  |     0   | 0
   1  |   0  |  1  |     0   | 1
   0  |   1  |  1  |     0   | 1
   1  |   1  |  2  |    -2   | 0

然后，我们需要定义约束。

首先，我们希望 K 个集群是平衡的，即每个集群必须包含相似数量的节点，大致等于 N/K。

其次，如果我们正在处理二元二次模型设置，我们需要进一步的约束以确保在 q 个变量中，只有 1 设置为 1，所有其他设置为 0。对于每个节点 i，该约束只是 ?_j q_ij = 1。然而，这也是本文的重点，DWave 在他们的软件中引入了一项新功能，可以将此类情况作为离散类索引（例如红色、绿色或蓝色）而不是二进制来处理。有趣的是，这种模型的求解器是混合型的，这意味着它利用量子计算来改进对目标函数最小值的经典搜索。根据他们的说法：

这个混合求解器可以接受多达 5,000 个离散变量的问题，每个变量可以表示多达 10,000 个值的集合，以及总共 20 亿个线性加二次偏差

因此，总体目标函数 + 约束如下所示：

这个表达式可以被扩展然后简化以将线性项（在某个时间涉及一个 C_ii * q_i）与二次项（乘积 C_ij * q_i * q_j）分开，这是一种繁琐但需要定义权重矩阵 C 系数的操作 . 有兴趣的读者可以在 DWave 源代码上找到有关此示例的更多详细信息（https://github.com/dwave-examples/graph-partitioning-dqm）。

作为一个实际用例，我使用了 Zachary 的空手道俱乐部图，这是一个大学空手道俱乐部的社交网络，在 Wayne W. Zachary 的论文“An Information Flow Model for Conflict and Fission in Small Groups”中有所描述。这个由 34 个人组成的小型网络的结构可在 NetworkX python 库中找到。成对成员之间的联系代表了俱乐部之外的互动，他们最终分成了 2 个独立的小组。为了展示如何从 networkx 读取图形结构，然后使用 DWave 海洋库对其进行分析，我们将可能的子组数量增加到 2 以上。

完整的代码可以在我的 GitHub 存储库中找到。简而言之，以下是解决问题所必需的一系列操作：

 import networkx as nx
 import dimod
 from dwave.system import LeapHybridDQMSampler
 
 ...
 
 dqm = dimod.DiscreteQuadraticModel()
 num_nodes = G.number_of_nodes()
 
 for i in G.nodes:
     dqm.add_variable(num_partitions, label=i)
 
 for i in G.nodes:
     linear_term = ...
     dqm.set_linear(i, linear_term)
 
 # Quadratic term for node pairs that do *not* share edges
 for p0, p1 in nx.non_edges(G):
     quadratic_term = ...
     dqm.set_quadratic(p0, p1, {(c, c): quadratic_term for c in range(num_partitions)})
 
 # Quadratic term for node pairs which have edges between them
 for p0, p1 in G.edges:
     quadratic_term = ...
     dqm.set_quadratic(p0, p1, {(c, c): quadratic_term for c in range(num_partitions)})
 
 # solve!
 sampler = LeapHybridDQMSampler()
 sampleset = sampler.sample_dqm(dqm, label='Example - Graph Partitioning DQM')
 
 # do something with the lowest-energy solution:
 sample = sampleset.first.sample

如果一切正常，它应该是这样的：

然后，您可以打开一个终端窗口并键入命令 python karate.py 。输出将显示为一个名为 graph_partitioning_result.png 的新 .png 文件，对于 K=4 集群，它看起来应该类似于此文件：

总而言之，图分区是一个突出的问题，有许多不同的可能解决方法。QUBO 方法已经存在了一段时间（另请参阅 Ushijima-Mwesigwa 等人的这篇不错的论文），但在我看来，由于必须处理集群变量的方式，尤其是由于缺乏 在某些情况下唯一分配。通过使用具有离散二次模型的混合方法，可以很好地解决这个问题，该模型允许用户通过利用经典计算和基于量子计算之间的相互作用来解决大型问题。

作者：Riccardo Di Sipio

原文地址：https://towardsdatascience.com/graph-partitioning-with-discrete-quadratic-model-running-on-dwave-quantum-annealer-6c2e821d646e