近似最大 k-割 (Approximate Maximum k-cut)

术语表

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

简介

图的 k-割是指将其节点分配到 k 个互不相交的社区中。例如，对于包含节点 a,b,c,d 的图，一个 2-割可以是社区 {a,b,c} 和 {d}。

最大 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-割与最大割 (Maximum Cut) 相同。

应用场景

寻找图的最大 k-割有多种已知应用，例如用于：

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

近似算法

在实践中，对于大型图，寻找最佳割在计算上是不可行的，只能在合理时间内计算出一个近似解。

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

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

Festa et al. Randomized Heuristics for the Max-Cut Problem, 2002.

要了解当 k = 2 时该算法在解质量方面与其他算法的对比表现，请参阅论文中的 FES02GV：

Dunning et al. What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO, 2018.

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

调优算法参数

有两个重要的算法特定参数，允许你在解质量和运行时间之间进行权衡。

迭代次数 (Iterations)

GRASP 风格的算法本质上是迭代的。每次迭代都执行定义明确的相同步骤来推导解，但每次都使用不同的随机种子，从而（极有可能）得到不同的解。最后，选择得分最高的解作为获胜者。

VNS 最大邻域阶数

变邻域搜索 (VNS) 的工作原理是：对算法每次迭代中推导出的局部最优解进行轻微扰动，然后对扰动后的解进行局部优化。此处的“扰动”是指随机将一些节点从当前的（局部最优）社区移动到另一个社区。

VNS 将依次移动 1,2,…,vnsMaxNeighborhoodOrder 个随机节点，并尝试利用每个结果解寻找更好的局部最优解。这意味着，虽然使用 VNS 可能推导出更好的解，但这会花费更多时间，并且需要更多的内存来临时存储扰动后的解。

默认情况下，不使用 VNS (vnsMaxNeighborhoodOrder = 0)。要使用它，从最大阶数为 20 开始尝试是一个不错的选择。

语法

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

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

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

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

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

表 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。

在命名图上以变异模式 (mutate mode) 运行近似最大 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	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

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

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

示例

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

这些示例将 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 Bytes"

变异模式 (Mutate)

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)

在 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

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