Source: https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/ppr/
Documentation version: v5.3.2

# 个性化 PageRank

本文介绍个性化 PageRank (Personalized Page Rank, PPR) 算法，并演示如何用 GQL 实现该算法。

## 算法介绍

PPR 算法是 [PageRank](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/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`的边表示。

该图类型的完整定义，请参见[准备图数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/ppr/#1_prepare_graph_data)。

## 过程实现[]()

为了计算图中点的 PPR 分数，将创建一个[过程](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/procedures/create/)来实现 PPR 算法。

该过程的完整定义，请参见[创建过程](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/ppr/#2_create_a_procedure)。下文将介绍该过程的关键组成部分及其工作原理。

该过程接受以下参数：

- `source_pks`：个性化集合中的点的 ID 列表。
- `damping`：阻尼因子。
- `max_iter`：最大迭代次数。
- `eps`：收敛阈值。如果某次迭代中 PPR 分数的总变化小于该阈值，则停止迭代。

此外，在过程内部定义了以下变量：

 | 变量名 | 变量类型 | 描述
 | `start_set` | [活动集变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/active-set-variable/) | 每次迭代中正在处理的点的集合。
 | `total_set` | [活动集变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/active-set-variable/) | 所有迭代中处理过的点的集合。
 | `cur_iter` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 当前迭代次数。
 | `delta` | 全局 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 在每次迭代中点的 PPR 分数的总变化量。用于判断是否停止迭代。
 | `topk_score` | 全局 [TopKAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/topk_agg/) | PPR 分数最高的前 K 个点。
 | `pk_set` | 全局 [SetAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/set_agg/) | 个性化集合中点的 ID 集合。
 | `current_score` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每个点在当前迭代的 PPR 分数。
 | `next_score` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每个点在下一迭代的 PPR 分数。
 | `out_edge` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每个点的出边数量。
 | `is_source` | 点绑定 [OrAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/or_agg/) | 代表点是否在个性化集合中的标记。
 | `result_file` | [文件变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/file-variable/) | 存储前 K 个点的 PPR 分数的文件。

以下步骤概述了该过程的逻辑：

1. 将每个点的`out_edge`初始化为其出边数量。
2. 将`pk_set`初始化为参数`source_pks`提供的个性化集合中的点的 ID。
3. 将`start_set`初始化为个性化集合中的点，并将它们的`current_score`设置为`1.0`，`is_source`设置为`true`。同时，也将`total_set`初始化为这些点。
4. 开始迭代过程以更新 PPR 分数。若当前迭代次数超过最大迭代次数（由`max_iter`指定）或达到收敛阈值（由`eps`指定），就停止迭代：

  1. 将`delta`重置为`0.0`。
  2. 对于`start_set`中的点的每条边，将目标点的`next_score`设置为起始点的`current_score`除以其`out_edge`。
  3. 将所有目标点添加到`start_set`中。
  4. 对`start_set`中的每个点，执行以下操作：

    1. 按照以下规则更新其`next_score`：

      - 若该点在个性化集合中，将其`next_score`设置为`1.0 - damping + damping * next_score`。
      - 否则，将其`next_score`设置为`damping * next_score`。

    2. 计算其`next_score`与`current_score`之间的绝对差值并累加至`delta`。
    3. 准备下一次迭代，将其`current_score`设置为`next_score`，并将`next_score`重置为`0.0`。

  5. 将`start_set`中的点添加到`total_set`中。
  6. 迭代次数`cur_iter`加`1`。
  7. 输出`delta`的值以便监控。

5. 在最后一次迭代结束后，将`topk_score`初始化为`total_set`中`current_score`最高的前 20 个点。
6. 把`topk_score`中的结果导出到`result_file`指定的文件中。
7. 将以下结果作为输出参数返回：

  - `node_id`：`topk_score`中点的 ID。
  - `score`：该点的 PPR 分数，保留五位小数。

## 操作步骤

在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按[准备算法示例数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/)确认操作位置和目录挂载。

### 1. 准备图数据[]()

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)
}
'''

````

2. 

下载以下 CSV 文件，保留文件名，保存到部署目录下的`examples/algorithms/ppr/`：

  - [pagerank_node.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/ppr/pagerank_node.csv)：点数据。
  - [pagerank_edge.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/ppr/pagerank_edge.csv)：边数据。

查看 CSV 内容

pagerank_node.csv

````
u_id,u_name
1,Alice
2,Bob
3,Charlie
4,David

````

pagerank_edge.csv

````
src_id,dst_id
1,2
2,3
1,4
3,4
4,2

````

3. 

基于图类型创建一个临时图，并将数据文件加载到临时图中。

````
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`。点数不符时，先按[文件问题排查](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting)检查文件和导入结果。

### 2. 创建过程[]()

创建实现 PPR 算法的过程。关于该过程的更多信息，请参见[过程实现](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/ppr/#procedure_implement)。

````
'''
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](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/in-out/export/)：

- 先将 PPR 输出字段导出到表变量（通常为`vid`、`score`）。
- 若写入远程图，先`table_split(...)`分批，再通过`nebula_exec`执行批量`USE + INSERT`。

目标图类型需与输出模型匹配，例如为点增加`ppr_score`属性。