近似最大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	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	算法特定和/或图过滤的配置。

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

表 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	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	算法特定和/或图过滤的配置。

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

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

示例

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

这些示例使用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中创建图后，我们现在可以将其投影到图目录中，以便为算法执行做好准备。我们使用针对Person节点和TRANSACTION关系的Cypher投影来执行此操作。

以下语句将投影一个图并将其存储在图目录中，名称为“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

我们可以看到，当未考虑关系权重时，我们得出了一个分成两个（因为我们没有覆盖默认的k = 2）成本为13.0的社区的割。总成本在此处由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. 结果
name	community
"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时，反之亦然。但是请注意，对于该解决方案，割的成本将保持不变。

带关系权重的变异

在本例中，我们将了解添加关系权重如何影响我们的解决方案。

以下将在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. 结果
name	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. 结果
name	communityId
"Alice"	0
"Bridget"	0
"Charles"	0
"Doug"	1
"Eric"	1
"Fiona"	1
"George"	1

我们可以看到结果是我们期望的，即与mutate unweighted示例中相同。