奖金收集斯坦纳树 (Prize-Collecting Steiner Tree)

术语表

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

简介

给定一个图，可以通过选择一组关系来形成一个子树，其约束条件是生成的子图是连通的，且其中任意两个节点之间恰好存在一条路径。根据所选节点/关系的不同，一个图可以有许多可能的子树。

给定一个加权图，其中每个节点都有一个奖金（prize），奖金收集斯坦纳树问题要求找到满足以下条件的子树：

使图中节点的奖金总和最大化。
使关系权重之和与未包含在树中的节点的奖金之和最小化。

这两个约束可以通过简单地将第二个约束从第一个约束中减去，组合成一个单一的极大化问题。

奖金收集斯坦纳树问题是 NP-完全问题，目前尚无有效的精确算法。Neo4j GDS 库实现了文献中一种实用的2-近似算法。这意味着返回的结果至少是最优解的一半。

注意事项

默认情况下，奖金收集斯坦纳树问题仅考虑节点的奖金。然而在某些情况下，考虑关系的奖金也很有用。GDS 实现可以通过以下转换处理关系的奖金：对于权重为 w 且奖金为 p 的关系，建议将其替换为 w' = w - p。这应作为投影内存中图之前的预处理步骤完成。

语法

各模式下的奖金收集斯坦纳树语法

在命名图上以流模式运行算法。

CALL gds.prizeSteinerTree.stream(
  graphName: String,
  configuration: Map
)
YIELD
  nodeId: Integer,
  parentId: Integer,
  weight: Float

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

表 2. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[1]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
prizeProperty	字符串	`不适用`	否	表示节点奖金的节点属性名称。该属性必须是 Double 类型，不能是 Long 类型。
1. 在 GDS 会话中，默认值为可用处理器的数量。

表 3. 结果
名称	类型	描述
nodeId	整数	发现的子树中的节点。
parentId	整数	该节点在树中的父节点；如果它是源节点，则为节点本身。
weight	浮点数	从 parentId 到 nodeId 的关系权重。

在命名图上以统计模式运行算法。

CALL gds.prizeSteinerTree.stats(
  graphName: String,
  configuration: Map
)
YIELD
  effectiveNodeCount: Integer,
  totalWeight: Float,
  sumOfPrizes: Float,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  configuration: Map

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

表 5. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[2]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
prizeProperty	字符串	`不适用`	否	表示节点奖金的节点属性名称。该属性必须是 Double 类型，不能是 Long 类型。
2. 在 GDS 会话中，默认值为可用处理器的数量。

表 6. 结果
名称	类型	描述
effectiveNodeCount	整数	子树中的节点数量。
totalWeight	浮点数	子树中关系权重的总和。
sumOfPrizes	浮点数	子树中节点的奖金总和。
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
配置	Map	用于运行算法的配置。

在命名图上以 mutate 模式运行算法。

CALL gds.prizeSteinerTree.mutate(
  graphName: String,
  configuration: Map
)
YIELD
  effectiveNodeCount: Integer,
  totalWeight: Float,
  sumOfPrizes: Float,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  mutateMillis: Integer,
  relationshipsWritten: Integer,
  configuration: Map

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

表 8. 配置
名称	类型	默认	可选	描述
mutateRelationshipType	字符串	`不适用`	否	用于写入投影图的新关系的关系类型。
mutateProperty	字符串	`不适用`	否	写入权重的 GDS 图中的关系属性。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
prizeProperty	字符串	`不适用`	否	表示节点奖金的节点属性名称。该属性必须是 Double 类型，不能是 Long 类型。

表 9. 结果
名称	类型	描述
effectiveNodeCount	整数	子树中的节点数量。
totalWeight	浮点数	子树中关系权重的总和。
sumOfPrizes	浮点数	子树中节点的奖金总和。
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
mutateMillis	整数	将结果数据写回的毫秒数。
relationshipsWritten	整数	添加到内存图中关系的数量。
配置	Map	用于运行算法的配置。

在命名图上以 write 模式运行算法。

CALL gds.prizeSteinerTree.write(
  graphName: String,
  configuration: Map
)
YIELD
  effectiveNodeCount: Integer,
  totalWeight: Float,
  sumOfPrizes: Float,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  writeMillis: Integer,
  relationshipsWritten: Integer,
  configuration: Map

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

表 11. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[3]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeRelationshipType	字符串	`不适用`	否	用于将计算出的关系持久化到 Neo4j 数据库的关系类型。
writeProperty	字符串	`不适用`	否	写入权重的 Neo4j 数据库中的关系属性。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
prizeProperty	字符串	`不适用`	否	表示节点奖金的节点属性名称。该属性必须是 Double 类型，不能是 Long 类型。
3. 在 GDS 会话中，默认值为可用处理器的数量。

表 12. 结果
名称	类型	描述
effectiveNodeCount	整数	子树中的节点数量。
totalWeight	浮点数	子树中关系权重的总和。
sumOfPrizes	浮点数	子树中节点的奖金总和。
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
writeMillis	整数	将结果数据写回的毫秒数。
relationshipsWritten	整数	写入图中的关系数量。
配置	Map	用于运行算法的配置。

示例

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

这些示例将 Cypher 投影作为规范。原生投影将在未来版本中弃用。

在本节中，我们将展示在具体图上运行奖金收集斯坦纳树算法的示例。目的是说明结果的样子，并为如何在实际环境中使用该算法提供指导。我们将在一个由少量节点按特定模式连接的小型道路网络图上进行演示。示例图如下所示：

以下代码将创建图中描绘的示例图

CREATE (a:Place {id: 'A', prize: 5.0}),
       (b:Place {id: 'B', prize: 20.0}),
       (c:Place {id: 'C',prize: 11.0}),
       (d:Place {id: 'D',prize: 10.0}),
       (e:Place {id: 'E',prize: 8.0}),
       (f:Place {id: 'F',prize: 1.0}),
       (a)-[:LINK {cost:10}]->(f),
       (a)-[:LINK {cost:3}]->(b),
       (a)-[:LINK {cost:7}]->(e),
       (b)-[:LINK {cost:1}]->(c),
       (c)-[:LINK {cost:4}]->(d),
       (c)-[:LINK {cost:6}]->(e),
       (f)-[:LINK {cost:3}]->(d);

以下代码将投影并存储一个命名图

MATCH (source:Place)-[r:LINK]->(target:Place)
RETURN gds.graph.project(
  'graph',
  source,
  target,
{
    sourceNodeProperties: source { .prize },
    targetNodeProperties: target { .prize },
    relationshipProperties: r { .cost }
  },
  { undirectedRelationshipTypes: ['*'] }
)

内存估算

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

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

以下代码将估算以 stream 模式运行该算法所需的内存：

CALL gds.prizeSteinerTree.stream.estimate('graph', {
  relationshipWeightProperty: 'cost',
  prizeProperty: 'prize'
})
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory
RETURN nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 13. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
6	14	3897	561616	"[3897 Bytes ... 548 KiB]"

Stream

在 stream 执行模式下，算法返回每个关系的权重。这允许我们直接检查结果或在 Cypher 中进行后处理，而不会产生任何副作用。

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

以下代码将以 stream 模式运行奖金收集斯坦纳树算法，并返回每个有效节点的结果。

CALL gds.prizeSteinerTree.stream('graph', {
  relationshipWeightProperty: 'cost',
  prizeProperty: 'prize'
})
YIELD nodeId,parentId, weight
RETURN gds.util.asNode(nodeId).id AS node, gds.util.asNode(parentId).id AS parent,weight
ORDER BY node

表 14. 结果
节点	parent	weight
"A"	"B"	3.0
"B"	"C"	1.0
"D"	"C"	4.0
"E"	"C"	6.0

该算法找到了包含 A、B、C、D 和 E 的树。节点 F 被跳过，因为它的奖金非常低，将其与其它节点连接会产生较差的解。

统计信息 (Stats)

在 stats 执行模式下，算法返回包含算法结果摘要的单行数据。此执行模式没有任何副作用。它对于通过检查 computeMillis 返回项来评估算法性能非常有用。在下面的示例中，我们将省略返回的计时信息。该过程的完整签名可以在语法部分中找到。

有关 stats 模式的更多详细信息，请参阅统计。

以下代码将以 stats 模式运行奖金收集斯坦纳树算法并返回其统计信息。

CALL gds.prizeSteinerTree.stats('graph', {
  relationshipWeightProperty: 'cost',
  prizeProperty: 'prize'
})
YIELD effectiveNodeCount, totalWeight, sumOfPrizes
RETURN effectiveNodeCount, totalWeight, sumOfPrizes

表 15. 结果
effectiveNodeCount	totalWeight	sumOfPrizes
5	14.0	54.0

stats 模式为我们提供了连通树中关系权重的总和（为 14.0），以及节点 A、B、C、D 和 E 的奖金总和（为 54.0）。

Mutate

mutate 执行模式扩展了 stats 模式，具有一个重要的副作用：使用包含该关系权重的新关系属性更新命名图。新属性的名称通过强制配置参数 mutateProperty 指定。结果是单行摘要，类似于 stats，但包含一些额外的指标。当多个算法结合使用时，mutate 模式特别有用。

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

以下代码将以 mutate 模式运行奖金收集斯坦纳树算法并返回其统计信息。

CALL gds.prizeSteinerTree.mutate('graph', {
  relationshipWeightProperty: 'cost',
  prizeProperty: 'prize',
  mutateProperty: 'weight',
  mutateRelationshipType: 'STEINER'
})
YIELD effectiveNodeCount, totalWeight, sumOfPrizes, relationshipsWritten
RETURN effectiveNodeCount, totalWeight, sumOfPrizes, relationshipsWritten

表 16. 结果
effectiveNodeCount	totalWeight	sumOfPrizes	relationshipsWritten
5	14.0	54.0	4

mutate 模式使用名为 STEINER 的新关系类型更新内存中的 graph，并带有单个属性 weight。从 relationshipsWritten 列中，我们可以看到添加了恰好四种这样的关系。它们连接了斯坦纳树中的节点，其属性即为每个连接的成本。

即使输入图是无向的，写回图的关系也始终是有向的。它们按固定的树顺序从 parent 指向 node。

Write

write 执行模式扩展了 stats 模式，具有一个重要的副作用：将每个关系的权重作为属性写入 Neo4j 数据库。新属性的名称通过强制配置参数 writeProperty 指定。结果是单行摘要，类似于 stats，但包含一些额外的指标。write 模式允许直接将结果持久化到数据库中。

有关 write 模式的更多详细信息，请参阅写入。

以下代码将以 write 模式运行奖金收集斯坦纳树算法并返回其统计信息。

CALL gds.prizeSteinerTree.write('graph', {
  relationshipWeightProperty: 'cost',
  prizeProperty: 'prize',
  writeProperty: 'weight',
  writeRelationshipType: 'STEINER'
})
YIELD effectiveNodeCount, totalWeight, sumOfPrizes, relationshipsWritten
RETURN effectiveNodeCount, totalWeight, sumOfPrizes, relationshipsWritten

表 17. 结果
effectiveNodeCount	totalWeight	sumOfPrizes	relationshipsWritten
5	14.0	54.0	4

此查询将四种类型为 STEINER、属性为 weight 的新关系写回数据库。

写回的关系始终是有向的，即使输入图是无向的。它们按固定的树顺序从 parent 指向 node。