标签传播算法（LPA）¶
本文介绍标签传播算法（Label Propagation Algorithm, LPA），并演示如何用 GQL 实现该算法。
算法介绍¶
标签传播算法（LPA）是一种用于图中社区检测的算法。它通过基于邻居点的标签在网络中传播标签并形成社区。算法开始时，每个点被分配一个唯一的标签，并根据其邻居中最频繁的标签迭代更新点的标签。
该算法的工作原理是标签通常会在高度连接的点群体内部传播和保留，而难以跨越稀疏连接的区域。随着标签的传播，只有少数标签会保留下来，而大多数标签会消失，直到收敛。最终，具有相同标签的点被分组为一个社区。
标签传播算法的关键步骤如下：
- 开始时，每个点具有一个唯一的标签。
- 标签在网络中传播。
- 在每次迭代中，点将其标签更新为其邻居中最频繁的标签。
- 该过程重复进行，直到没有标签变化或达到所设定最大迭代次数。
- 最终输出每个点的社区标签，表示图中检测到的社区。
有关标签传播算法的更多信息，请参见标签传播算法。
数据模型¶
为了用 GQL 实现标签传播算法，将基于以下数据模型来创建图类型：
- 人员表示为类型为
Person的点。每个点分配有一个由唯一的id表示的初始标签。 - 人员之间的关系编码为类型为
Knows的边。这些边将点连接起来并作为标签传播的通道，使标签能够在网络中扩散。
有关图类型的完整定义，请参见准备图数据。
过程实现¶
为了基于邻居中最频繁的标签找到点的社区标签，创建了一个过程来实现标签传播算法。
该过程将Knows边视为无向边，并使用活动集变量跟踪标签发生变化的点。每轮只对这些点的邻居重新计算标签，减少图逐渐收敛时的边扫描。重新计算时仍统计待处理点的全部邻居的标签，而不只是标签发生变化的邻居；标签选择和更新规则与全量扫描版本一致。
有关过程的完整定义，请参见创建过程。以下部分描述了该过程的关键要素及其工作原理。
该过程接收以下输入参数：
max_iter：最大迭代次数。
此外，在过程内部定义了以下变量：
| 变量 | 类型 | 说明 |
|---|---|---|
node_label |
点绑定 SumAgg 聚合值变量 | 每个点的标签。 |
node_count |
点绑定 SumAgg 聚合值变量 | 上次更新点标签时，该标签在邻居中的出现次数。初始值为0，用于比较是否更新标签。 |
label_count_map |
点绑定 MapAgg 聚合值变量 | 用于统计点邻居中每个标签出现次数的映射。 |
changed |
点绑定 OrAgg 聚合值变量 | 点的标签是否在本轮发生变化。每次重新计算该点后覆盖此标记。 |
changed_set |
活动集变量 | 上一轮标签发生变化的点集合。初始包含所有点，之后每轮替换为本轮标签发生变化的点。 |
recompute_set |
活动集变量 | 本轮需要重新计算标签的点集合，即changed_set中点的邻居。 |
result_file |
文件变量 | 保存最终点标签的文件，包括点 ID 及其最终社区标签。 |
new_active |
全局 OrAgg 聚合值变量 | 全局布尔标记，表示本轮是否发生更新；决定是否继续迭代。 |
iter |
原始值变量 | 算法执行后迭代的次数。 |
cur_iter |
原始值变量 | 遍历label_count_list时使用的索引。 |
label_count_list |
原始值变量（记录列表） | 读取label_count_map得到的标签计数列表，每条记录的_0为标签、_1为出现次数。 |
did_change |
原始值变量（布尔值） | 本次重新计算是否更新了点的标签，用于覆盖changed。 |
以下步骤概述了该过程的逻辑：
- 初始化每个点的
node_label为其自身 ID，并将所有点加入changed_set，以启动第一轮计算。 - 当
new_active为true且当前迭代次数小于最大迭代次数（由max_iter指定）时重复执行：- 将
new_active设为false，并增加迭代计数器。 - 确定待重算点：从
changed_set中的点出发，将其邻居收集到recompute_set，覆盖上一轮的集合。 - 重新计算标签：对于
recompute_set中的每个点t，将其全部邻居s的标签聚合到t的label_count_map中。从label_count_list选出出现次数最多的标签；次数相同时选择值最大的标签。仅当候选标签与当前标签不同且其计数大于node_count，或计数等于node_count且候选标签值更大时，更新点的标签和node_count，并将new_active设为true。用did_change覆盖该点的changed标记，然后清空标签计数映射。 - 更新变化点集合：从
recompute_set中筛选changed为true的点，用这些点替换changed_set，供下一轮使用。
- 将
- 收敛后或达到最大迭代次数后，将每个点的 ID 和最终对应的社区标签 ID 导出到
result_file。
没有邻居的孤立点不会进入recompute_set，其最终标签保留为自身 ID。
操作步骤¶
在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按准备算法示例数据确认操作位置和目录挂载。
1. 准备图数据¶
-
创建与数据模型匹配的图类型：
''' CREATE GRAPH TYPE IF NOT EXISTS lpa_graph_type AS { NODE Person (LABEL Person {id INT PRIMARY KEY}), EDGE Knows (Person)-[LABEL Knows {MULTIEDGE KEY ()}]->(Person) } ''' -
下载以下 CSV 文件，保留文件名，保存到部署目录下的
examples/algorithms/lpa/：- lpa_node.csv：点数据。
- lpa_edge.csv：边数据。
查看 CSV 内容
lpa_node.csvid 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33lpa_edge.csvsrc,dst 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,10 0,11 0,12 0,13 0,17 0,19 0,21 0,31 1,2 1,3 1,7 1,13 1,17 1,19 1,21 1,30 2,3 2,7 2,8 2,9 2,13 2,27 2,28 2,32 3,7 3,12 3,13 4,6 4,10 5,6 5,10 5,16 6,16 8,30 8,32 8,33 9,33 13,33 14,32 14,33 15,32 15,33 18,32 18,33 19,33 20,32 20,33 22,32 22,33 23,25 23,27 23,29 23,32 23,33 24,25 24,27 24,31 25,31 26,29 26,33 27,33 28,31 28,33 29,32 29,33 30,32 30,33 31,32 31,33 32,33 -
基于图类型创建一个临时图，并将数据文件加载到临时图中。
CREATE TEMPORARY GRAPH IF NOT EXISTS #lpa_graph TYPED lpa_graph_type''' USE #lpa_graph IMPORT INTO GRAPH { NODE (v@Person {id: id}) FROM DATAFILE { PATH: "file:///examples/algorithms/lpa/lpa_node.csv", FORMAT: "CSV", DELIMITER: ',' }, EDGE (id: src)-[e@Knows{}]->(id: dst) FROM DATAFILE { PATH: "file:///examples/algorithms/lpa/lpa_edge.csv", FORMAT: "CSV", DELIMITER: ',' } } '''导入成功后，在控制台执行以下查询核对点数：
''' USE #lpa_graph MATCH (n) RETURN count(n) AS node_count '''node_count应为34。点数不符时，先按文件问题排查检查文件和导入结果。
2. 创建过程¶
创建实现标签传播算法的过程。关于该过程的更多信息，请参见过程实现。
'''
CREATE OR REPLACE PROCEDURE lpa (max_iter INT) RETURNS () AS {
NODE VALUE node_label SumAgg<INT> = 0
NODE VALUE node_count SumAgg<INT> = 0
NODE VALUE label_count_map MapAgg<INT, SumAgg<INT>>
NODE VALUE changed OrAgg = false
FILE result_file {id INT, label_id INT}= DATAFILE {
PATH: "file:///examples/algorithms/lpa/output",
FORMAT: "CSV"
}
VALUE new_active OrAgg = true
VALUE iter = 0
VALUE changed_set ACTIVE_SET
VALUE recompute_set ACTIVE_SET
MATCH (a@Person)
PER NODE (a) {
SET a.@node_label = a.id
}
FINALLY {
SET changed_set = a
}
WHILE @new_active AND iter < max_iter THEN {
SET @new_active = false
SET iter = iter + 1
// P1：收集上一轮标签发生变化的点的邻居
MATCH (c@Person)-[@Knows]-(t@Person)
WHERE c IN changed_set
FINALLY {
SET recompute_set = t
}
// P2：统计 recompute_set 中各点的全部邻居标签
MATCH (t@Person)-[@Knows]-(s@Person)
WHERE t IN recompute_set
PER PATH {
SET t.@label_count_map += TUPLE(s.@node_label, 1)
}
PER NODE (t) {
VALUE max_count INT = 0
VALUE max_label INT = -1
VALUE cur_iter = 0
VALUE did_change = false
VALUE label_count_list = t.@label_count_map
WHILE cur_iter < length(label_count_list) THEN {
VALUE val = label_count_list[cur_iter]
IF val._1 > max_count OR val._1 = max_count AND val._0 > max_label THEN {
SET max_count = val._1
SET max_label = val._0
}
SET cur_iter = cur_iter + 1
}
IF max_label <> -1 AND (max_count > t.@node_count AND max_label <> t.@node_label
OR max_count = t.@node_count AND max_label > t.@node_label
) THEN {
SET @new_active += true
SET t.@node_count = max_count
SET t.@node_label = max_label
SET did_change = true
}
SET t.@changed = did_change
SET t.@label_count_map.clear()
}
// P3：仅保留本轮标签发生变化的点
MATCH (t@Person)
WHERE t IN recompute_set AND t.@changed = true
FINALLY {
SET changed_set = t
}
}
MATCH (a@Person)
PER NODE (a) {
EXPORT a.id, a.@node_label INTO result_file
}
}
'''
3. 调用过程¶
调用该过程计算每个点最终的社区标签。以下示例将最大迭代次数设置为10。
USE #lpa_graph CALL lpa(10) FINISH
此调用将结果写入 CSV，控制台不返回结果表。
在宿主机的部署目录下，打开examples/algorithms/lpa/output/中的 CSV 文件。示例内容如下：
"id","label_id"
0,33
1,33
2,33
3,33
4,31
5,31
6,31
7,33
8,33
9,33
10,31
11,33
12,33
13,33
14,33
15,33
16,31
17,33
18,33
19,33
20,33
21,33
22,33
23,33
24,33
25,33
26,33
27,33
28,33
29,33
30,33
31,33
32,33
33,33
id代表点的初始标签，label_id代表点最终的社区标签。
将结果写入图中
如果希望将 LPA 结果持久化到图，请参见 EXPORT 并按 LPA 输出做字段映射：
- 先将 LPA 输出字段导出到表变量（通常为
id、label_id）。 - 若写入远程图，使用
table_split(...)分批，再通过nebula_exec批量执行USE + INSERT。
建议在目标图类型中增加社区字段，例如在Person上增加community_id属性。