标签传播 (Label Propagation)

术语表

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

简介

标签传播算法 (LPA) 是一种用于查找图中社区的快速算法。它仅利用网络结构作为指导来检测这些社区，不需要预定义的目标函数或关于社区的先验信息。

LPA 的工作原理是在整个网络中传播标签，并基于此传播过程形成社区。

该算法背后的直觉是：单个标签可以在连接紧密的节点组中迅速占据主导地位，但在跨越稀疏连接的区域时会遇到困难。标签会被困在连接紧密的节点组内，当算法结束时，拥有相同标签的节点可以被视为同一社区的成员。

算法的工作步骤如下：

每个节点都被初始化为一个唯一的社区标签（标识符）。
这些标签在网络中进行传播。
在每次传播迭代中，每个节点将其标签更新为其邻居中出现次数最多的那个标签。平局情况会以随机但确定性的方式处理。
当每个节点都拥有其邻居中的多数标签时，LPA 达到收敛。
如果达到收敛或用户定义的最大迭代次数，LPA 将停止。

随着标签传播，连接紧密的节点组会迅速就唯一标签达成共识。传播结束时，只会剩下少数几个标签——大多数标签会消失。在收敛时拥有相同社区标签的节点被认为属于同一个社区。

LPA 的一个有趣特性是，可以为节点分配初步标签，以缩小生成的解决方案范围。这意味着它可以用作一种半监督的社区发现方式，即手动挑选一些初始社区。

有关此算法的更多信息，请参阅

运行此算法需要足够的可用内存。在运行之前，建议您阅读内存估计 (Memory Estimation)。

语法

本节涵盖了在每种执行模式下执行标签传播算法所使用的语法。我们描述的是命名图（Named Graph）变体的语法。要了解有关通用语法变体的更多信息，请参阅语法概述。

各模式下的标签传播语法

在流模式（Stream mode）下对命名图运行标签传播。

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

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

表 2. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[1]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
maxIterations	整数	`10`	是	要运行的最大迭代次数。
nodeWeightProperty	字符串	`null`	是	包含节点权重的节点属性名称。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
seedProperty	字符串	`不适用`	是	定义初始数值标签的节点属性名称。
consecutiveIds	布尔值	`false`	是	用于决定组件标识符是否映射到连续 ID 空间的标志（需要额外的内存）。
minCommunitySize	整数	`0`	是	仅返回属于大于或等于给定值的社区的节点。
1. 在 GDS 会话中，默认值为可用处理器的数量。

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

在统计模式（Stats mode）下对命名图运行标签传播。

CALL gds.labelPropagation.stats(
  graphName: String,
  configuration: Map
)
YIELD
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  communityCount: Integer,
  ranIterations: Integer,
  didConverge: Boolean,
  communityDistribution: Map,
  configuration: Map

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

表 5. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[2]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
maxIterations	整数	`10`	是	要运行的最大迭代次数。
nodeWeightProperty	字符串	`null`	是	包含节点权重的节点属性名称。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
seedProperty	字符串	`不适用`	是	定义初始数值标签的节点属性名称。
consecutiveIds	布尔值	`false`	是	用于决定组件标识符是否映射到连续 ID 空间的标志（需要额外的内存）。
2. 在 GDS 会话中，默认值为可用处理器的数量。

表 6. 结果
名称	类型	描述
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算百分位数和社区数量所需的毫秒数。
communityCount	整数	发现的社区数量。
ranIterations	整数	已执行的迭代次数。
didConverge	布尔值	如果算法在提供的最大迭代次数内收敛到稳定的标签分配，则为 True。
communityDistribution	Map	包含社区大小的最小值、最大值、平均值以及 p1, p5, p10, p25, p50, p75, p90, p95, p99 和 p999 百分位数的映射。
配置	Map	用于运行算法的配置。

在变更模式（Mutate mode）下对命名图运行标签传播。

CALL gds.labelPropagation.mutate(
  graphName: String,
  configuration: Map
)
YIELD
  preProcessingMillis: Integer,
  computeMillis: Integer,
  mutateMillis: Integer,
  postProcessingMillis: Integer,
  nodePropertiesWritten: Integer,
  communityCount: Integer,
  ranIterations: Integer,
  didConverge: Boolean,
  communityDistribution: Map,
  configuration: Map

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

表 8. 配置
名称	类型	默认	可选	描述
mutateProperty	字符串	`不适用`	否	GDS 图中写入社区 ID 的节点属性。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
maxIterations	整数	`10`	是	要运行的最大迭代次数。
nodeWeightProperty	字符串	`null`	是	包含节点权重的节点属性名称。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
seedProperty	字符串	`不适用`	是	定义初始数值标签的节点属性名称。
consecutiveIds	布尔值	`false`	是	用于决定组件标识符是否映射到连续 ID 空间的标志（需要额外的内存）。

表 9. 结果
名称	类型	描述
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
mutateMillis	整数	向内存中图添加属性的毫秒数。
postProcessingMillis	整数	计算百分位数和社区数量所需的毫秒数。
nodePropertiesWritten	整数	写入的节点属性数。
communityCount	整数	发现的社区数量。
ranIterations	整数	已执行的迭代次数。
didConverge	布尔值	如果算法在提供的最大迭代次数内收敛到稳定的标签分配，则为 True。
communityDistribution	Map	包含社区大小的最小值、最大值、平均值以及 p1, p5, p10, p25, p50, p75, p90, p95, p99 和 p999 百分位数的映射。
配置	Map	用于运行算法的配置。

在写入模式（Write mode）下对命名图运行标签传播。

CALL gds.labelPropagation.write(
  graphName: String,
  configuration: Map
)
YIELD
  preProcessingMillis: Integer,
  computeMillis: Integer,
  writeMillis: Integer,
  postProcessingMillis: Integer,
  nodePropertiesWritten: Integer,
  communityCount: Integer,
  ranIterations: Integer,
  didConverge: Boolean,
  communityDistribution: Map,
  configuration: Map

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

表 11. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[3]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeProperty	字符串	`不适用`	否	Neo4j 数据库中写入社区 ID 的节点属性。
maxIterations	整数	`10`	是	要运行的最大迭代次数。
nodeWeightProperty	字符串	`null`	是	包含节点权重的节点属性名称。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
seedProperty	字符串	`不适用`	是	定义初始数值标签的节点属性名称。
consecutiveIds	布尔值	`false`	是	用于决定组件标识符是否映射到连续 ID 空间的标志（需要额外的内存）。
minCommunitySize	整数	`0`	是	仅将大小大于或等于给定值的社区的社区 ID 写入 Neo4j。
3. 在 GDS 会话中，默认值为可用处理器的数量。

表 12. 结果
名称	类型	描述
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
writeMillis	整数	将结果数据写回的毫秒数。
postProcessingMillis	整数	计算百分位数和社区数量所需的毫秒数。
nodePropertiesWritten	整数	写入的节点属性数。
communityCount	整数	发现的社区数量。
ranIterations	整数	已执行的迭代次数。
didConverge	布尔值	如果算法在提供的最大迭代次数内收敛到稳定的标签分配，则为 True。
communityDistribution	Map	包含社区大小的最小值、最大值、平均值以及 p1, p5, p10, p25, p50, p75, p90, p95, p99 和 p999 百分位数的映射。
配置	Map	用于运行算法的配置。

示例

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

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

在本节中，我们将展示在具体图表上运行标签传播算法的示例。目的是说明结果的样子，并为如何在实际环境中使用该算法提供指南。我们将在一个包含少数节点并以特定模式连接的小型社交网络图上进行演示。示例图如下所示：

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

CREATE
  (alice:User {name: 'Alice', posts: 4, seed_label: 52}),
  (bridget:User {name: 'Bridget', posts: 13, seed_label: 21}),
  (charles:User {name: 'Charles', posts: 55, seed_label: 43}),
  (doug:User {name: 'Doug', posts: 5, seed_label: 21}),
  (mark:User {name: 'Mark', posts: 7, seed_label: 19}),
  (michael:User {name: 'Michael', posts: 15, seed_label: 52}),

  (alice)-[:FOLLOW {weight: 1}]->(bridget),
  (alice)-[:FOLLOW {weight: 10}]->(charles),
  (mark)-[:FOLLOW {weight: 1}]->(doug),
  (bridget)-[:FOLLOW {weight: 1}]->(michael),
  (doug)-[:FOLLOW {weight: 1}]->(mark),
  (michael)-[:FOLLOW {weight: 1}]->(alice),
  (alice)-[:FOLLOW {weight: 1}]->(michael),
  (bridget)-[:FOLLOW {weight: 1}]->(alice),
  (michael)-[:FOLLOW {weight: 1}]->(bridget),
  (charles)-[:FOLLOW {weight: 1}]->(doug)

该图代表六个用户，其中一些人互相关注。除了 name 属性外，每个用户还有一个 seed_label 属性。seed_label 属性代表图中用于为节点植入标签的值。例如，这可以是之前运行标签传播算法的结果。此外，每个关系都有一个权重属性。

以下语句将使用 Cypher 投影来投影一个图，并将其以“myGraph”的名称存储在图目录中。

MATCH (source:User)-[r:FOLLOW]->(target:User)
RETURN gds.graph.project(
  'myGraph',
  source,
  target,
  {
    sourceNodeProperties: source { .posts, .seed_label },
    targetNodeProperties: target { .posts, .seed_label },
    relationshipProperties: r { .weight }
  }
)

在接下来的示例中，我们将演示在此图上使用标签传播算法的过程。

内存估算

首先，我们将使用 estimate 过程估算运行算法的成本。这可以在任何执行模式下完成。在这个例子中我们将使用 write 模式。估算算法有助于了解在您的图上运行该算法将产生的内存影响。当您随后在其中一种执行模式下真正运行算法时，系统将执行一次估算。如果估算显示执行超出其内存限制的可能性非常高，则禁止执行。要阅读更多关于此的内容，请参阅自动估算和执行阻塞。

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

以下内容将估算以写入模式运行算法所需的内存要求：

CALL gds.labelPropagation.write.estimate('myGraph', { writeProperty: 'community' })
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 13. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
6	10	1592	1592	“1592 字节”

流模式 (Stream)

在 stream 执行模式下，算法返回每个节点的社区 ID。这使我们能够直接检查结果或在 Cypher 中对其进行后处理，而不会产生任何副作用。例如，我们可以对结果进行排序，以查看属于同一社区的节点并排显示。

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

以下命令将运行算法并流式传输结果

CALL gds.labelPropagation.stream('myGraph')
YIELD nodeId, communityId AS Community
RETURN gds.util.asNode(nodeId).name AS Name, Community
ORDER BY Community, Name

表 14. 结果
名称	社区
"Alice"	0
“Bridget”	0
“Michael”	0
“Charles”	4
“Doug”	4
“Mark”	4

在上面的示例中，我们可以看到我们的图有两个社区，每个社区包含三个节点。算法的默认行为是运行 unweighted（无权重），即不使用 node 或 relationship 权重。weighted（加权）选项将在加权部分演示。

统计模式 (Stats)

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

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

以下语句将以 stats 模式运行该算法：

CALL gds.labelPropagation.stats('myGraph')
YIELD communityCount, ranIterations, didConverge

表 15. 结果
communityCount	ranIterations	didConverge
2	3	true

正如我们在上面的示例中所看到的，该算法发现了两个社区并在三次迭代中收敛。请注意，我们运行的是 unweighted（无权重）算法。

变更模式 (Mutate)

mutate 执行模式扩展了 stats 模式，并带有一个重要的副作用：用包含该节点社区 ID 的新节点属性更新命名图。新属性的名称通过必需的配置参数 mutateProperty 指定。结果是一个摘要行，类似于 stats，但带有额外的指标。mutate 模式在多个算法协同使用时特别有用。

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

以下代码将运行算法并回写结果：

CALL gds.labelPropagation.mutate('myGraph', { mutateProperty: 'community' })
YIELD communityCount, ranIterations, didConverge

表 16. 结果
communityCount	ranIterations	didConverge
2	3	true

返回的结果与 stats 示例中的相同。此外，图 'myGraph' 现在拥有一个节点属性 community，其中存储了每个节点的社区 ID。要了解如何检查内存中图的新模式，请参阅列出图。

写入模式 (Write)

write 执行模式扩展了 stats 模式，并带有一个重要的副作用：将每个节点的社区 ID 作为属性写入 Neo4j 数据库。新属性的名称通过必需的配置参数 writeProperty 指定。结果是一个摘要行，类似于 stats，但带有额外的指标。write 模式允许直接将结果持久化到数据库中。

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

以下代码将运行算法并回写结果：

CALL gds.labelPropagation.write('myGraph', { writeProperty: 'community' })
YIELD communityCount, ranIterations, didConverge

表 17. 结果
communityCount	ranIterations	didConverge
2	3	true

返回的结果与 stats 示例中的相同。此外，所有六个节点现在在 Neo4j 数据库中都有一个新的 community 属性，其中包含该节点的社区 ID。

加权 (Weighted)

当我们投影 myGraph 时，我们也投影了关系属性 weight。为了告知算法将此属性视为关系权重，我们必须将 relationshipWeightProperty 配置参数设置为 weight。

以下代码将在加权关系的图上运行算法并流式传输结果：

CALL gds.labelPropagation.stream('myGraph', { relationshipWeightProperty: 'weight' })
YIELD nodeId, communityId AS Community
RETURN gds.util.asNode(nodeId).name AS Name, Community
ORDER BY Community, Name

表 18. 结果
名称	社区
“Bridget”	0
“Michael”	0
"Alice"	4
“Charles”	4
“Doug”	4
“Mark”	4

与算法的无权重运行相比，我们仍然有两个社区，但它们分别包含两个和四个节点。使用加权关系，节点 Alice 和 Charles 现在处于同一个社区，因为它们之间有强连接。

加权节点

通过 nodeWeightProperty 键指定节点权重，我们还可以控制节点社区对其邻居的影响。在计算特定社区的权重时，该节点属性将乘以该节点关系的权重。

以下代码将在加权节点的图上运行算法并流式传输结果：

CALL gds.labelPropagation.stream('myGraph', { nodeWeightProperty: 'posts' })
YIELD nodeId, communityId AS Community
RETURN gds.util.asNode(nodeId).name AS Name, Community
ORDER BY Community, Name

表 19. 结果
名称	社区
"Alice"	4
“Charles”	4
“Doug”	4
“Mark”	4
“Bridget”	5
“Michael”	5

我们使用了 stream 模式来演示如何使用权重运行算法，这些配置参数适用于算法的所有模式。

植入社区 (Seeded communities)

在算法计算开始时，每个节点都被初始化为一个唯一的标签，并且标签在网络中传播。

通过设置 seedProperty 配置参数，可以提供一组初始标签。当我们投影 myGraph 时，我们也投影了节点属性 seed_label。我们可以将此节点属性用作 seedProperty。

算法首先检查节点是否分配了种子标签。如果没有种子标签，算法会为节点分配一个新的唯一标签。使用这组初步标签，它随后按顺序将每个节点的标签更新为新标签，即在标签传播的每次迭代中其邻居中最频繁的标签。

consecutiveIds 配置选项不能与 seedProperty 结合使用，以便保留植入的值。

以下代码将使用预定义的标签运行算法：

CALL gds.labelPropagation.stream('myGraph', { seedProperty: 'seed_label' })
YIELD nodeId, communityId AS Community
RETURN gds.util.asNode(nodeId).name AS Name, Community
ORDER BY Community, Name

表 20. 结果
名称	社区
“Charles”	19
“Doug”	19
“Mark”	19
"Alice"	52
“Bridget”	52
“Michael”	52

正如我们所见，社区是基于 seed_label 属性的，具体来说，19 来自节点 Mark，52 来自 Alice。

我们使用了 stream 模式来演示使用 seedProperty 运行算法，此配置参数适用于算法的所有模式。