近似最大 k-割

有向

无向

异构节点

异构关系

加权关系

术语表

有向: 有向特性。该算法在有向图上定义良好。
有向: 有向特性。该算法忽略图的方向。
有向: 有向特性。该算法不在有向图上运行。
无向: 无向特性。该算法在无向图上定义良好。
无向: 无向特性。该算法忽略图的无向性。
异构节点: 异构节点完全支持。该算法能够区分不同类型的节点。
异构节点: 异构节点允许。该算法对所有选定的节点进行相似处理，无论其标签如何。
异构关系: 异构关系完全支持。该算法能够区分不同类型的关系。
异构关系: 异构关系允许。该算法对所有选定的关系进行相似处理，无论其类型如何。
加权关系: 加权特性。该算法支持将关系属性用作权重，通过relationshipWeightProperty配置参数指定。
加权关系: 加权特性。该算法将每个关系视为同等重要，并丢弃任何关系权重的值。

简介

图的 k-割是将其节点划分为 k 个不相交社区的任务。例如，对于具有节点 a,b,c,d 的图，一个 2-割可以是社区 {a,b,c} 和 {d}。

最大 k-割是一种 k-割，使得 k-割中不同社区节点之间关系的权重总和最大化。也就是说，最大化 k-割中源节点和目标节点分配给不同社区的关系权重之和的 k-割。假设在上面简单的 a,b,c,d 节点集示例中，我们只有一个关系 b → c，其权重为 1.0。那么我们上面概述的 2-割将不是最大 2-割（割成本为 0.0），而例如社区为 {a,b} 和 {c,d} 的 2-割将是最大 2-割（割成本为 1.0）。

当 k = 2 时，最大 k-割与最大割相同。

此功能处于 Alpha 阶段。有关功能阶段的更多信息，请参阅API 阶段。

应用

寻找图的最大 k-割有几个已知的应用，例如它用于

分析蛋白质相互作用
设计电路 (VLSI) 布局
解决无线通信问题
分析加密货币交易模式
设计计算机网络

近似

在实践中，对于大型图而言，找到最佳割点是不可行的，只能在合理的时间内计算近似值。

GDS 中实现的近似启发式算法是一种并行化的GRASP风格算法，可选地（通过配置）通过可变邻域搜索 (VNS) 进行增强。

有关该算法的串行版本（构造阶段略有不同）的详细信息，当 k = 2 时，请参阅论文中的 GRASP+VNR

Festa 等人，《最大割问题的随机启发式算法》，2002。

要了解上述算法在 k = 2 时与其它算法相比的解决方案质量表现，请参阅论文中的 FES02GV

Dunning 等人，《何时何地效果最佳？对最大割和 QUBO 启发式算法的系统评估》，2018。

由于算法的随机性，除非以单线程（concurrency = 1）运行并使用相同的随机种子（randomSeed = SOME_FIXED_VALUE），否则其结果将不确定。

调优算法参数

有两个重要的算法特定参数，它们允许您权衡解决方案质量和更短的运行时间。

迭代次数

GRASP 风格的算法本质上是迭代的。每次迭代都运行相同的明确定义的步骤来得出解决方案，但每次都使用不同的随机种子，从而产生（很可能）也不同的解决方案。最后，得分最高的解决方案被选为优胜者。

VNS 最大邻域阶数

可变邻域搜索 (VNS) 的工作原理是：在算法迭代中，轻微扰动从先前步骤中获得的局部最优解，然后局部优化这个被扰动的解。在这种情况下，扰动意味着随机地将一些节点从其当前（局部最优）社区移动到另一个社区。

VNS 将依次移动 1,2,…,vnsMaxNeighborhoodOrder 个随机节点，并使用每个结果解尝试找到一个新的、更好的局部最优解。这意味着，虽然使用 VNS 可能会获得更好的解决方案，但它会花费更多时间，此外还需要更多内存来临时存储被扰动的解决方案。

默认情况下，不使用 VNS (vnsMaxNeighborhoodOrder = 0)。要使用它，可以从尝试最大阶数等于 20 开始。

语法

本节介绍在每种执行模式下执行近似最大 k-割算法所使用的语法。我们正在描述命名图语法的变体。要了解有关通用语法变体的更多信息，请参阅语法概述。

示例 1. 每种模式的近似最大 k-割语法

在命名图上以流模式运行近似最大 k-割。

CALL gds.maxkcut.stream(
  graphName: String,
  configuration: Map
) YIELD
  nodeId: Integer,
  communityId: Integer

表 1. 参数
名称	类型	默认值	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
配置	映射	`{}`	是	算法特定和/或图过滤的配置。

表 2. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	`4 ^[1]`	是	运行算法所用的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID，以便更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，则不会记录进度百分比。
k	整数	`2`	是	节点将被划分为的不相交社区的数量。
iterations	整数	`8`	是	算法在返回所有迭代中的最佳解决方案之前将运行的迭代次数。
vnsMaxNeighborhoodOrder	整数	`0（VNS 关闭）`	是	VNS 在扰动解决方案时将交换的最大节点数。
randomSeed	整数	`不适用`	是	一个随机种子，用于计算中的所有随机性。需要 `concurrency = 1`。
relationshipWeightProperty	字符串	`null`	是	如果设置，则给定属性中存储的值在计算期间用作关系权重。如果未设置，则图被视为无权重。
minCommunitySize	整数	`0`	是	只返回社区大小大于或等于给定值的节点。
1. 在 GDS 会话中，默认值为可用处理器数量

表 3. 结果
名称	类型	描述
nodeId	整数	节点 ID。
communityId	整数	社区 ID。

在命名图上以变异模式运行近似最大 k-割。

CALL gds.maxkcut.mutate(
  graphName: String,
  configuration: Map
) YIELD
  cutCost: Float,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  mutateMillis: Integer,
  nodePropertiesWritten: Integer,
  configuration: Map

表 4. 参数
名称	类型	默认值	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
配置	映射	`{}`	是	算法特定和/或图过滤的配置。

表 5. 配置
名称	类型	默认值	可选	描述
mutateProperty	字符串	`不适用`	否	GDS 图中用于写入近似最大 k-割的节点属性。
nodeLabels	字符串列表	`['*']`	是	使用给定节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定关系类型过滤命名图。
concurrency	整数	`4`	是	运行算法所用的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID，以便更轻松地跟踪算法的进度。
k	整数	`2`	是	节点将被划分为的不相交社区的数量。
iterations	整数	`8`	是	算法在返回所有迭代中的最佳解决方案之前将运行的迭代次数。
vnsMaxNeighborhoodOrder	整数	`0（VNS 关闭）`	是	VNS 在扰动解决方案时将交换的最大节点数。
randomSeed	整数	`不适用`	是	一个随机种子，用于计算中的所有随机性。需要 `concurrency = 1`。
relationshipWeightProperty	字符串	`null`	是	如果设置，则给定属性中存储的值在计算期间用作关系权重。如果未设置，则图被视为无权重。

表 6. 结果
名称	类型	描述
cutCost	浮点数	连接不同社区节点的全部关系权重之和。
preProcessingMillis	整数	数据预处理的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算统计数据的毫秒数。
mutateMillis	整数	向投影图添加属性的毫秒数。
nodePropertiesWritten	整数	添加到投影图的属性数量。
配置	映射	运行算法所使用的配置。

示例

以下所有示例都应在空数据库中运行。

这些示例以Cypher 投影为准。原生投影将在未来的版本中弃用。

在本节中，我们将展示在具体图上运行近似最大 k-割算法的示例。目的是说明结果如何，并提供在实际环境中如何使用该算法的指南。我们将在一个小型的比特币交易图上进行此操作，该图由少量以特定模式连接的节点组成。

以下 Cypher 语句将在 Neo4j 数据库中创建示例图

CREATE
  (alice:Person {name: 'Alice'}),
  (bridget:Person {name: 'Bridget'}),
  (charles:Person {name: 'Charles'}),
  (doug:Person {name: 'Doug'}),
  (eric:Person {name: 'Eric'}),
  (fiona:Person {name: 'Fiona'}),
  (george:Person {name: 'George'}),
  (alice)-[:TRANSACTION {value: 81.0}]->(bridget),
  (alice)-[:TRANSACTION {value: 7.0}]->(doug),
  (bridget)-[:TRANSACTION {value: 1.0}]->(doug),
  (bridget)-[:TRANSACTION {value: 1.0}]->(eric),
  (bridget)-[:TRANSACTION {value: 1.0}]->(fiona),
  (bridget)-[:TRANSACTION {value: 1.0}]->(george),
  (charles)-[:TRANSACTION {value: 45.0}]->(bridget),
  (charles)-[:TRANSACTION {value: 3.0}]->(eric),
  (doug)-[:TRANSACTION {value: 3.0}]->(charles),
  (doug)-[:TRANSACTION {value: 1.0}]->(bridget),
  (eric)-[:TRANSACTION {value: 1.0}]->(bridget),
  (fiona)-[:TRANSACTION {value: 3.0}]->(alice),
  (fiona)-[:TRANSACTION {value: 1.0}]->(bridget),
  (george)-[:TRANSACTION {value: 1.0}]->(bridget),
  (george)-[:TRANSACTION {value: 4.0}]->(charles)

有了 Neo4j 中的图，我们现在可以将其投影到图目录中，以准备算法执行。我们使用 Cypher 投影来完成此操作，目标是 Person 节点和 TRANSACTION 关系。

以下语句将投影一个图并将其存储在图目录中，名称为 'myGraph'。

MATCH (source:Person)-[r:TRANSACTION]->(target:Person)
RETURN gds.graph.project(
  'myGraph',
  source,
  target,
  { relationshipProperties: r { .value } }
)

内存估算

首先，我们将使用 estimate 过程估算运行算法的成本。这可以在任何执行模式下完成。在此示例中，我们将使用 mutate 模式。估算算法有助于了解在图上运行算法对内存的影响。当您稍后实际在其中一种执行模式下运行算法时，系统将执行估算。如果估算显示执行极有可能超出其内存限制，则将禁止执行。要了解更多信息，请参阅自动估算和执行阻止。

有关 estimate 的更多详细信息，请参阅内存估算。

以下将估算运行算法所需的内存

CALL gds.maxkcut.mutate.estimate('myGraph', {mutateProperty: 'community'})
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 7. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
7	15	488	488	"488 字节"

变异

mutate 执行模式扩展了 stats 模式，并带有一个重要的副作用：用包含该节点近似最大 k-割的新节点属性更新命名图。新属性的名称使用强制配置参数 mutateProperty 指定。结果是一个单一的摘要行，类似于 stats，但带有一些额外的指标。当多个算法结合使用时，mutate 模式特别有用。

有关 mutate 模式的更多详细信息，请参阅变异。

以下将在 mutate 模式下运行算法

CALL gds.maxkcut.mutate('myGraph', {mutateProperty: 'community'})
YIELD cutCost, nodePropertiesWritten

表 8. 结果
cutCost	nodePropertiesWritten
13.0	7

我们可以看到，当不考虑关系权重时，我们得出了一个成本为 13.0 的两（因为我们没有覆盖默认的 k = 2）社区割。总成本由这里的 cutCost 列表示。这是我们希望尽可能高的值。此外，图 'myGraph' 现在具有一个节点属性 community，用于存储每个节点所属的社区。

要检查每个节点属于哪个社区，我们可以流式传输节点属性。

流式节点属性

CALL gds.graph.nodeProperty.stream('myGraph', 'community')
YIELD nodeId, propertyValue
RETURN gds.util.asNode(nodeId).name as name, propertyValue AS community

表 9. 结果
名称	社区
"Alice"	0
"Bridget"	0
"Charles"	0
"Doug"	1
"Eric"	1
"Fiona"	1
"George"	1

查看我们的图拓扑，我们可以看到社区 1 的节点之间没有关系，而社区 0 的节点之间有两条关系，即 Alice → Bridget 和 Charles → Bridget。然而，由于 Bridget 和社区 1 的节点之间总共有八条关系，而且我们的图是无权重的，将 Bridget 分配给社区 1 不会产生更高总权重的割。因此，由于连接不同社区节点的数量大大超过连接同一社区节点的数量，这似乎是一个很好的解决方案。事实上，这就是该图的最大 2-割。

由于近似最大 k-割算法固有的随机性（除非 concurrency = 1 且 randomSeed 固定），再次运行可能会产生不同的解决方案。对于我们的情况，获得逆解也是同样合理的，即当我们的社区 0 节点映射到社区 1 而不是社区 0 时，反之亦然。但请注意，对于该解决方案，割成本将保持不变。

带关系权重的变异

在此示例中，我们将探讨添加关系权重如何影响我们的解决方案。

以下将在 mutate 模式下再次运行算法，将我们的节点划分为两个社区

CALL gds.maxkcut.mutate(
   'myGraph',
   {
        relationshipWeightProperty: 'value',
        mutateProperty: 'weightedCommunity'
    }
)
YIELD cutCost, nodePropertiesWritten

表 10. 结果
cutCost	nodePropertiesWritten
146.0	7

由于我们的 TRANSACTION 关系上的 value 属性都至少为 1.0，并且有几个值更大，因此在加权情况下我们获得更高成本的割并不奇怪。

现在让我们流式传输节点属性，再次检查节点社区分布。

流式节点属性

CALL gds.graph.nodeProperty.stream('myGraph', 'weightedCommunity')
YIELD nodeId, propertyValue
RETURN gds.util.asNode(nodeId).name as name, propertyValue AS weightedCommunity

表 11. 结果
名称	weightedCommunity
"Alice"	0
"Bridget"	1
"Charles"	0
"Doug"	1
"Eric"	1
"Fiona"	1
"George"	1

将此结果与无权重情况的结果进行比较，我们可以看到 Bridget 已移至另一个社区，但输出其他方面相同。确实，通过查看我们的图，这很有道理。Bridget 通过八个关系连接到社区 1 的节点，但这些关系的权重都是 1.0。尽管 Bridget 只连接到两个社区 0 的节点，但这些关系的权重分别为 81.0 和 45.0。将 Bridget 移回社区 0 会降低总割成本，即 81.0 + 45.0 - 8 * 1.0 = 118.0。因此，Bridget 现在在社区 1 中是合理的。事实上，这是加权情况下的最大 2-割。

流

在 stream 执行模式下，算法返回每个节点的近似最大 k-割。这允许我们直接检查结果或在 Cypher 中进行后处理，而没有任何副作用。

有关 stream 模式的更多详细信息，请参阅流。

以下将使用默认配置参数在 stream 模式下运行算法

CALL gds.maxkcut.stream('myGraph')
YIELD nodeId, communityId
RETURN gds.util.asNode(nodeId).name AS name, communityId

表 12. 结果
名称	communityId
"Alice"	0
"Bridget"	0
"Charles"	0
"Doug"	1
"Eric"	1
"Fiona"	1
"George"	1

我们可以看到结果符合预期，与无权重变异示例中的结果相同。