CS224w图机器学习（九）：Link Analysis- PageRank

慎笃

发布于 2021-09-15 10:27:21

4940

发布于 2021-09-15 10:27:21

文章被收录于专栏：深度学习进阶

前十课内容总结

本文主要介绍CS224W的第十一课，RageRank（很有名，就不赘述了）。

开始本章节内容之前，先对前十课的内容进行总结。前三节课主要讲在图的概念与性质，我们简单总结下这三讲内容所提到的与图相关的概念。

第四课到第十课主要在介绍图的各个方向，图社区、图分割、消息传播、表征学习与图神经网络。

CS224w Lecture 11: Link Analysis- PageRank

上图为CS224W第十一讲的内容框架，如下链接为第十一讲的课程讲义

1 Web as a Graph

我们都知道PageRank是谷歌的网页排名算法。诸多网页构成的网络（Web）可以看作是一张有向图，节点是网页，边是网页之间的超链接。

先深入了解有向图都有哪些重要的知识点。

先引入两个问题： 1）给定节点

，哪些节点可以通过有向路径到达节点

，

， 2）给定节点

，它可以通过有向路径到达哪些节点，

。基于有向图的节点能否通过有向路径到达其他节点，任意有向图可由下面两种子图来表示： 1）强连通图（Strong Connected Component, SCC）：任意节点之间都可以通过有向路径到达； 2）有向无环图（Directed Acyclic Graph, DAG）：图中没有环路，若节点

能通过有向路径到达节点

，那么节点

无法到达节点

。如何寻找节点

的强连通分量呢？取能到达节点

和节点

能到达的节点集合即可，即

。通过深度优先搜索/广度优先搜索都可得到

和

。把

内的边全都反转，可得到

。接下来，我们使用谷歌之前的搜索巨头Altavista在1999年的网页数据（共2.03亿个网页，15亿个超链接），来看下网页有向图是什么样子的。如下图1，网页

能通过超链接访问到的网页数量分布，不难发现两极分化严重，要么极多、要么极少。如下图2，可将2.03亿网页划分为SCC、IN、OUT、TenDrils、Tubes、Disconnected Components等部分。

图1 网页能通过超链接访问到的网页数分布

图2 Altavista网页数据的SCC和DAG

总的来看，上面讲述的内容核心是在传达：网络中的节点不是同等重要的，比如SCC、DAG内的节点重要性存在差异。我们需要通过链接分析（Link Analysis）的相关方法来计算网络节点的重要性。

2 How to organize the web: PageRank

上述已提到不同网页的重要性是不一样的，我们需要的是能够计算网页重要性的手段。

先引入这么一个观点：网页的重要性由它的超链接决定。如果有个超链接从一个重要的网页指向当前网页，那么当前网页的重要性也很高。即重要性高的网页，它的超链接权重也应该更高。如下图所示，网页

的重要性为

，且一共指向三个网页，所以网页

的一跳网页接收的重要性为

，共有两个网页指向网页

，所以网页

的重要性

。即任意网页

的重要性为：

其中网页

为指向网页

的网页集合，

为网页

指向的网页数量（出度）。

我们用有向图的随机邻接矩阵

来表示上述公式，网页

的出度为

，对于所有被网页

所指向的网页

，我们有

。（不难发现矩阵

的列和为1）那么节点重要性计算可用如下矩阵，可参见下图案例辅助理解。

再仔细看上述公式，网页重要性组成的向量

其实是随机邻接矩阵

特征值为1时的特征向量。

除了用特征向量求解，我们还可以用更快速有效的方法：Power iteration 1）初始化节点重要性：

2）迭代：

3）满足条件则停止迭代：

我们现在有了一套计算网页节点重要性的方法，但它存在一些缺陷，接下来我们会更进一步的完善这个方法。

缺陷主要有两点： 1）Dead End：有一些网页没有指向任何网页 2）Spider traps：某些网页的所有指向的网页都是它们内部，计算重要性时这些网页会吸收所有的重要性（他们不指向其他网页，重要性不会流出去，随着迭代次数的增加，这部分网页的重要性会越来越强，直至吸收所有网页的重要性）解决方法：每次迭代时，网页

有

的概率随机选择一个它指向的网页传递重要性，有

的概率随机传给全部网页中。最终网页

的重要性为：

矩阵

（也可称为Google Matrix）也就表示为：

在实践中，

通常取0.8或0.9。

3 Compute PageRank

上一部分已经讲了PageRank的算法详情，这部分主要将实际落地以及落地时需要做的优化。

实际计算过程中的问题： PageRank的实际计算过程：

，当网络中的节点数量很大时，存储

非常耗费内存。解决方法：随机邻接矩阵

通常是稀疏矩阵，Google Matrix

是一个稠密矩阵，稀疏矩阵的存储消耗会好很多，假设每个节点平均有10条链接，矩阵

的存储为

，矩阵

近似于

。所以在实际计算中，通过如下方式进行计算（稠密部分转化为一维向量）：

PageRank计算流程： 1）初始化重要性：

2）计算

3）计算

4）重复2和3，直至收敛

4 Random Walk with Restarts and Personalized PageRank

我们已经足够了解PageRank的详情和落地实现，可按照重要性得分给节点排序。再换一个角度来思考这个问题，我们怎么用PageRank来给用户推荐合适的网页呢？

再给用户做推荐时，网络已经变成了由用户和网页组成的二分图。以下图为例，左边是会议，右边是作者，怎么利用二分图和PageRank算法找到与ICDM最为相关的会议？怎么给作者推荐合适的会议？

解决方案是 Personalized PageRank。在介绍算法之前，先思考下这个问题，如下图所示，在二分图中，节点

和节点

怎么才算有关系？

再思考第二个问题，下面三组节点

，哪组节点的关系最强？

结合上述两个问题，我们不难发现共同的邻居越多，两个节点之间的关系也就越强，这也是Personalized PageRank算法的出发点。我们的问题是找到某节点

的相似节点，Personalized PageRank算法刻画节点相似性的算法逻辑如下：

pin_node = Q
for i in range(n_steps):

    # 随机选择pin_node的邻居节点
    board_node = pin_node.get_random_neighbor()  

    # 再随机选择board_node的邻居节点
    pin_node = board_node.get_random_neighbor()  
    
    # 有一定概率（alpha）从头开始随机游走
    if random() < alpha:
        pin_node = Q