个性化 PageRank¶
本文介绍个性化 PageRank (Personalized Page Rank, PPR) 算法，并演示如何用 GQL 实现该算法。
算法介绍¶
PPR 算法是 PageRank 算法的一个变种，它基于个性化偏好计算页面的重要性。与传统的 PageRank 将所有页面一视同仁不同，PPR 允许用户指定一组他们感兴趣的页面，算法会优先考虑这些页面进行排名。
某页面的 PPR 分数由一个随机用户从个性化页面集出发，通过链接跳转到达该页面的可能性决定。计算页面 PPR 分数的公式如下：
\[
PPR(i) = (1 - d) \cdot v(i) + d \cdot \sum_{j \in In(i)} \frac{PPR(j)}{Out(j)}
\]
其中：
PPR(i)：页面i的 PPR 分数。d：阻尼因子，表示用户从当前页面跳转到其他页面的概率。取值范围：[0, 1)。v(i)：代表对页面i的偏好程度的向量。取值越高表示偏好越高。通常，对个性化集合中的页面，取值为1；而对其他页面，则取值为0。In(i)：链接到页面i的页面集合。Out(j)：页面j的出链数量。
数据模型¶
为了用 GQL 实现 PPR 算法，将基于以下数据模型来创建图类型：
- 页面被抽象为人，由类型为
Person的点表示。 - 页面之间的链接被抽象为人与人之间的关系，由类型为
Knows的边表示。
该图类型的完整定义，请参见准备图数据。
过程实现¶
为了计算图中点的 PPR 分数，将创建一个过程来实现 PPR 算法。
该过程的完整定义，请参见创建过程。下文将介绍该过程的关键组成部分及其工作原理。
该过程接受以下参数：
source_pks：个性化集合中的点的 ID 列表。damping：阻尼因子。max_iter：最大迭代次数。eps：收敛阈值。如果某次迭代中 PPR 分数的总变化小于该阈值，则停止迭代。
此外，在过程内部定义了以下变量：
| 变量名 | 变量类型 | 描述 |
|---|---|---|
start_set |
活动集变量 | 每次迭代中正在处理的点的集合。 |
total_set |
活动集变量 | 所有迭代中处理过的点的集合。 |
cur_iter |
原始值变量 | 当前迭代次数。 |
delta |
全局 SumAgg 聚合值变量 | 在每次迭代中点的 PPR 分数的总变化量。用于判断是否停止迭代。 |
topk_score |
全局 TopKAgg 聚合值变量 | PPR 分数最高的前 K 个点。 |
pk_set |
全局 SetAgg 聚合值变量 | 个性化集合中点的 ID 集合。 |
current_score |
点绑定 SumAgg 聚合值变量 | 每个点在当前迭代的 PPR 分数。 |
next_score |
点绑定 SumAgg 聚合值变量 | 每个点在下一迭代的 PPR 分数。 |
out_edge |
点绑定 SumAgg 聚合值变量 | 每个点的出边数量。 |
is_source |
点绑定 OrAgg 聚合值变量 | 代表点是否在个性化集合中的标记。 |
result_file |
文件变量 | 存储前 K 个点的 PPR 分数的文件。 |
以下步骤概述了该过程的逻辑：
- 将每个点的
out_edge初始化为其出边数量。 - 将
pk_set初始化为参数source_pks提供的个性化集合中的点的 ID。 - 将
start_set初始化为个性化集合中的点，并将它们的current_score设置为1.0，is_source设置为true。同时，也将total_set初始化为这些点。 - 开始迭代过程以更新 PPR 分数。若当前迭代次数超过最大迭代次数（由
max_iter指定）或达到收敛阈值（由eps指定），就停止迭代：- 将
delta重置为0.0。 - 对于
start_set中的点的每条边，将目标点的next_score设置为起始点的current_score除以其out_edge。 - 将所有目标点添加到
start_set中。 - 对
start_set中的每个点，执行以下操作：- 按照以下规则更新其
next_score：- 若该点在个性化集合中，将其
next_score设置为1.0 - damping + damping * next_score。 - 否则，将其
next_score设置为damping * next_score。
- 若该点在个性化集合中，将其
- 计算其
next_score与current_score之间的绝对差值并累加至delta。 - 准备下一次迭代，将其
current_score设置为next_score，并将next_score重置为0.0。
- 按照以下规则更新其
- 将
start_set中的点添加到total_set中。 - 迭代次数
cur_iter加1。 - 输出
delta的值以便监控。
- 将
- 在最后一次迭代结束后，将
topk_score初始化为total_set中current_score最高的前 20 个点。 - 把
topk_score中的结果导出到result_file指定的文件中。 - 将以下结果作为输出参数返回：
node_id：topk_score中点的 ID。score：该点的 PPR 分数，保留五位小数。
操作步骤¶
在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按准备算法示例数据确认操作位置和目录挂载。
1. 准备图数据¶
-
创建一个与数据模型匹配的图类型。
''' CREATE GRAPH TYPE IF NOT EXISTS pagerank_graph_type AS { NODE Person (LABEL Person {id INT PRIMARY KEY, name STRING}), EDGE Knows (Person)-[LABEL Knows {MULTIEDGE KEY()}]->(Person) } ''' -
下载以下 CSV 文件，保留文件名，保存到部署目录下的
examples/algorithms/ppr/：- pagerank_node.csv：点数据。
- pagerank_edge.csv：边数据。
查看 CSV 内容
pagerank_node.csvu_id,u_name 1,Alice 2,Bob 3,Charlie 4,Davidpagerank_edge.csvsrc_id,dst_id 1,2 2,3 1,4 3,4 4,2 -
基于图类型创建一个临时图，并将数据文件加载到临时图中。
CREATE TEMPORARY GRAPH IF NOT EXISTS #ppr_graph TYPED pagerank_graph_type''' USE #ppr_graph IMPORT INTO GRAPH { NODE (v@Person {id: u_id, name: u_name}) FROM DATAFILE { PATH: "file:///examples/algorithms/ppr/pagerank_node.csv", FORMAT: "CSV", DELIMITER: ',' }, EDGE (id: src_id)-[e@Knows{}]->(id: dst_id) FROM DATAFILE { PATH: "file:///examples/algorithms/ppr/pagerank_edge.csv", FORMAT: "CSV", DELIMITER: ',' } } '''导入成功后，在控制台执行以下查询核对点数：
''' USE #ppr_graph MATCH (n) RETURN count(n) AS node_count '''node_count应为4。点数不符时，先按文件问题排查检查文件和导入结果。
2. 创建过程¶
创建实现 PPR 算法的过程。关于该过程的更多信息，请参见过程实现。
'''
CREATE OR REPLACE PROCEDURE pers_pagerank(source_pks LIST<INT>, damping DOUBLE, max_iter INT, eps DOUBLE) RETURNS (node_id INT, score DOUBLE) AS {
VALUE start_set ACTIVE_SET
VALUE total_set ACTIVE_SET
VALUE cur_iter = 0
VALUE delta SumAgg<DOUBLE> = 1.0
VALUE topk_score TopKAgg<20, score DOUBLE DESC, node_id INT DESC>
VALUE pk_set SetAgg<INT>
NODE VALUE current_score SumAgg<DOUBLE> = 0.0
NODE VALUE next_score SumAgg<DOUBLE> = 0.0
NODE VALUE out_edge SumAgg<INT64> = 0
NODE VALUE is_source OrAgg = false
FILE result_file {vid INT64, score DOUBLE} = DATAFILE {PATH:"file:///examples/algorithms/ppr/output", FORMAT:"CSV", INCLUDE_HEADER: true}
MATCH (s)-[e]->(t)
PER PATH {
SET s.@out_edge += 1
}
SET @pk_set = source_pks
MATCH (s@Person)
WHERE @pk_set.contains_key(s.id)
FINALLY {
SET start_set = s
}
MATCH (s)
WHERE s IN start_set
PER NODE (s) {
SET s.@current_score = 1.0
SET s.@is_source = true
}
FINALLY {
SET total_set = s
}
WHILE cur_iter < max_iter AND @delta > eps THEN {
SET @delta = 0.0
MATCH (s)-[e]->(t)
WHERE s IN start_set
PER PATH {
SET t.@next_score += s.@current_score / s.@out_edge
}
FINALLY {
SET start_set |= t
}
MATCH (s)
WHERE s IN start_set
PER NODE (s) {
IF s.@is_source = true THEN {
SET s.@next_score = 1.0 - damping + damping * s.@next_score
} ELSE {
SET s.@next_score = damping * s.@next_score
}
SET @delta += abs(s.@next_score - s.@current_score)
SET s.@current_score = s.@next_score
SET s.@next_score = 0.0
}
FINALLY {
SET total_set |= s
}
SET cur_iter = cur_iter + 1
LOG_INFO("delta == ", @delta)
}
MATCH (a)
WHERE a IN total_set
PER NODE (a) {
SET @topk_score += RECORD{score:a.@current_score, node_id:a.id}
}
FOR r IN @topk_score
EXPORT r.node_id AS vid, round(r.score, 5) AS score INTO result_file
FOR r IN @topk_score
RETURN r.node_id, round(r.score, 5)
}
'''
3. 调用过程¶
调用过程来计算 PPR 分数。以下示例将个性化集合中的点设置为 ID 为1和2的点，阻尼因子设置为0.85、最大迭代次数设置为10，收敛阈值设置为0.001。
USE #ppr_graph CALL pers_pagerank([1,2],0.85, 10, 0.001) RETURN *
此过程在控制台返回结果表，同时将结果导出为 CSV 文件。
返回：
+---------+---------+
| node_id | score |
+---------+---------+
| 2 | 0.66672 |
| 3 | 0.65038 |
| 4 | 0.5329 |
| 1 | 0.15 |
+---------+---------+
执行日志示例
Log:
2025-10-11T09:17:37.900499 INFO - delta == 2.55
2025-10-11T09:17:37.909048 INFO - delta == 0.7225
2025-10-11T09:17:37.918101 INFO - delta == 0.614125
2025-10-11T09:17:37.927305 INFO - delta == 0.522006
2025-10-11T09:17:37.936807 INFO - delta == 0.443705
2025-10-11T09:17:37.944857 INFO - delta == 0.37715
2025-10-11T09:17:37.953506 INFO - delta == 0.320577
2025-10-11T09:17:37.962312 INFO - delta == 0.272491
2025-10-11T09:17:37.970650 INFO - delta == 0.231617
2025-10-11T09:17:37.978231 INFO - delta == 0.196874
在宿主机的部署目录下，打开examples/algorithms/ppr/output/中的 CSV 文件。示例内容如下：
"vid","score"
2,0.66672
3,0.65038
4,0.5329
1,0.15
将结果写入图中
如果希望将个性化 PageRank 结果持久化到图，请参见 EXPORT：
- 先将 PPR 输出字段导出到表变量（通常为
vid、score）。 - 若写入远程图，先
table_split(...)分批，再通过nebula_exec执行批量USE + INSERT。
目标图类型需与输出模型匹配，例如为点增加ppr_score属性。