PageRank介绍

PageRank是一种由搜索引擎根据网页之间相互的超链接计算的技术，用于评估网页链接的质量和数量，名字来源于Google公司创始人Larry Page。PageRank的值（Pagerank Value）从0到10，PV值越高表示网页越受欢迎。值得注意的是，PV值的定义类似于地震里氏级数，通常PV值达到0.4就能说明网站非常受欢迎。

基本思想

对于某个网页A来说，该网页PV的计算基于以下两个基本假设：

1. 数量假设：在Web图模型中，如果一个页面节点接收到的其他网页指向的入链数量越多，那么这个页面越重要。
2. 质量假设：指向A的入链质量不同，质量高的页面会通过链接向其他页面传递更多的权重，越是质量高的页面指向A，页面A越重要。

基于上述假设，初始页面被赋予相同的PV，通过迭代计算来更新每个页面的PV，直到收敛。

基本算法

假设某一时刻网页A，B，C的链接情况如下图所示，网页A中存在到网页B，C的链接，网页B存在到网页C的链接，网页C存在到网页A的链接。

PageRank就是已知上述拓扑的前提下，判断三个网页的重要性。

Naive PageRank算法

根据数量与质量假设，初始的网页PV可以被初始化为

$$PV(A) = PV(C)$$ $$PV(B) = \frac{PV(A)}{2}$$ $$PV(C) = \frac{PV(A)}{2} + PV(B)$$

计算可得

$$PV(A) = PV(c) = 2 \times PV(B)$$

可以将上述计算过程改写为矩阵运算的形式，迭代更新PV。

修正PageRank公式

由于存在一些出链为0的网页（Web图中节点的出度为0）可能导致迭代结果为0，因此需要对算法进行修正。 两种修正方法如下所示：

• 网页通过链接传递的重要性乘以一个在0和1之间的阻尼系数d：

  $$PV(A) = (1-d) + d\sum_{i=1}^{m}\frac{PR(T^i)}{C(T^i)}$$

  上式中\(T^i\)表示存在到A的链接的网页。\(C(T^i)\)是网页\(T^i\)中的存在链接的数量。\(d\)是阻尼系数，一般定义为用户随机点击链接的概率，常值取0.85。\(1-d\)表示不考虑入站链接的情况下随机进入一个网页的概率。

• 进一步的对\(1-d\)进行量化：

  $$PV(A) = \frac{(1-d)}{N} + d\sum_{i=1}^{m}\frac{PR(T^i)}{C(T^i)}$$

  \(N\)是Web图中节点的总数（网页的总数）。

Personalized PageRank算法

PersonalPageRank算法模拟用户通过点击链接随机访问图中结点的行为计算稳定状态下各节点得到的随机访问概率。迭代公式如下：

$$PV(A) = (1-d)r^i + d\sum_{i=1}^{m}\frac{PR(T^i)}{C(T^i)}$$

当\(i = u\)时，\(r^i = 1\)。否则\(r^i = 0\)。\(u\)表示推荐的目标用户，计算结果就是所有顶点相对于顶点\(u\)的相关度。

利用DGL完成PageRank算法

PageRank可以看作是图上的节点更新算法，符合MessagePassing的框架，可以利用Deep Graph Library（DGL）来完成，详情参考DGL Toturials。

后续工作

解读ICLR 2019 post paper：

Predict then Propagate: Graph Neural Networks meet Personalized PageRank

---

• Next
  Graph Neural Networks Meet Personalized PageRank解读与思考