signed

QiShunwang

“诚信为本、客户至上”

cs224w(图机器学习)2021冬季课程学习笔记4 Link Analysis: PageRank (Graph as Matrix)

2021/6/3 13:52:33   来源:

诸神缄默不语-个人CSDN博文目录
cs224w(图机器学习)2021冬季课程学习笔记集合

文章目录

  • 1. Graph as Matrix
  • 2. PageRank / the Google Algorithm
    • 2.1 PageRank: The "Flow" Model
    • 2.2 PageRank: Matrix Formulation
    • 2.3 Connection to Random Walk
    • 2.4 Eigenvector Formulation
  • 3. PageRank: How to solve?
  • 4. Random Walk with Restarts & Personalized PageRank
  • 5. Matrix Factorization and Node Embeddings
  • 6. 本章总结
  • 7. 文中及脚注未提及的其他参考资料

本节课slides的下载地址
YouTube视频观看地址1 视频观看地址2 视频观看地址3 视频观看地址4


本章主要内容

将图视为矩阵(邻接矩阵)的形式,以线性代数的角度来学习PageRank1、随机游走和图嵌入。

PageRank是一种衡量网络中节点重要性的指标,主要思想是如果一个节点被很多重要节点指向,那么该节点也很重要。
可以从flow model / 线性方程组、power iteration(矩阵视角)、web surfer随机游走三种角度来看PageRank。
求解PageRank的方法:power iteration。
在求解PageRank的过程中会遇到spider traps和dead ends的问题,可以通过random teleport解决。
M / G 是随机游走的概率转移矩阵。

Personalized PageRank和Random Walk with Restarts(可用于衡量图中节点间相似性,如应用于推荐问题):主要区别在于teleport sets。

节点嵌入问题可以视作矩阵分解问题。


1. Graph as Matrix

  1. 本节课研究矩阵角度的图分析和学习。
  2. 这里的矩阵就是指邻接矩阵。
  3. 将图视为矩阵形式,可以通过随机游走的方式定义节点重要性(即PageRank),通过矩阵分解matrix factorization (MF)来获取节点嵌入,将其他节点嵌入(如node2vec)也视作MF。

2. PageRank / the Google Algorithm

  1. PageRank是谷歌搜索用的算法,用于对网页的重要性进行排序。在搜索引擎应用中,可以对网页重要性进行排序,从而辅助搜索引擎结果的网页排名。
  2. 在现实世界中,将整个互联网视作图:将网页视作节点,将网页间的超链接视作边
    在这里插入图片描述
    有一些问题会影响我们如何定义节点(但是本节课暂时不考虑这些问题):
    1. Dynamic pages created on the fly2
    2. dark matter:不可达(如有密码等)的database generated pages
  3. 一个网页之间互相链接的情况的示例:在这里插入图片描述
    老一点的网页超链接都是navigational纯导航到其他页面的,当代的很多链接则是transactional用于执行发布、评论、点赞、购买等功能事务的。本课程中主要仅考虑那种网页之间互相链接的情况。
  4. 将网页看作有向图,以链接指向作为边的方向(这个网页/节点能直接跳转到的网页就作为其下一个节点successor):在这里插入图片描述
  5. 其他可表现为有向图形式的信息网络示例:论文引用,百科全书中词条间的互相引用在这里插入图片描述
  6. 在图中,我们想要定义节点的重要性importance,通过网络图链接结构来为网页按重要性分级rank。以下将介绍3种用以计算图中节点重要性的方法:
    1. PageRank
    2. Personalized PageRank (PPR)
    3. Random Walk with Restarts (RWR)
  7. 衡量节点重要性:认为一个节点的链接越多,那么这个节点越重要。
    有向图有in-coming links和out-going links两种情况。可以想象,in-links比较不容易造假,比较靠谱,所以用in-links来衡量一个节点的重要性。可以认为一个网页链接到下一网页,相当于对该网页重要性投了票(vote)。所以我们认为一个节点的in-links越多,那么这个节点越重要。
    同时,我们认为来自更重要节点的in-links,在比较重要性时的权重vote更大。
    这就成了一个递归recursive的问题——要计算一个节点的重要性就要先计算其predecessors的重要性,计算这些predecessors的重要性又要先计算它们predecessors的重要性……

2.1 PageRank: The “Flow” Model

  1. 链接权重与其source page的重要性成正比例
  2. 如果网页 i i i 的重要性是 r i r_i ri,有 d i d_i di 个out-links,那么每个边的权重就是 r i / d i r_i/d_i ri/di
  3. 网页 j j j 的重要性 r j r_j rj 是其in-links上权重的总和在这里插入图片描述
  4. 从而得到对节点 j j j 的级别 r j r_j rj 的定义: r j = ∑ i → j r i d i r_j=\sum\limits_{i\rightarrow j}\frac{r_i}{d_i} rj=ijdiri d i d_i di 是节点 i i i 的出度)
  5. 以这个1839年的网络为例:在这里插入图片描述我们就可以得到这样的"flow" equations:
    r y = r y / 2 + r a / 2 r_y=r_y/2+r_a/2 ry=ry/2+ra/2
    r a = r y / 2 + r m r_a=r_y/2+r_m ra=ry/2+rm
    r m = r a / 2 r_m=r_a/2 rm=ra/2
  6. 在直觉上我们好像可以用高斯消元法Gaussian elimination来解这个线性方程组,但这种方法不scalable。所以我们寻找更scalable的矩阵形式解法。

2.2 PageRank: Matrix Formulation

  1. 建立随机邻接矩阵stochastic adjacency matrix M:网页 j j j d j d_j dj 条out-links,如果 j → i j\rightarrow i ji M i j = 1 d j M_{ij}=\frac{1}{d_j} Mij=dj1
    M是列随机矩阵column stochastic matrix(列和为1)3
    M的第 j j j 列可以视作 j j j 在邻居节点上的概率分布
    在这里插入图片描述
  2. rank vector r r r: 每个网页 i i i 的重要性得分 r i r_i ri
    ∑ i r i = 1 \sum_i\mathbf{r}_i=1 iri=1(所以 r r r 也可被视为是网络中所有节点的概率分布)
  3. flow equations可以被写成: r = M ⋅ r \mathbf{r}=M\cdot \mathbf{r} r=Mr
    回忆一下原公式: r j = ∑ i → j r i d i r_j=\sum\limits_{i\rightarrow j}\frac{r_i}{d_i} rj=ijdiri(其实感觉从这个公式推到上个公式应该还是比较直觉的, M M M 的第 j j j 行被指向的节点对应的列的元素就是 1 / d i 1/d_i 1/di,该列对应的是 r i \mathbf{r}_i ri,加总起来就得到上个公式)
  4. flow equation和矩阵对比的举例:在这里插入图片描述

2.3 Connection to Random Walk

  1. 假想一个web surfer的随机游走过程,在 t 时间在网页 i i i 上,在 t+1 时间从 i i i 的out-links中随机选一条游走。如此重复过程。
    向量 p ( t ) \mathbf{p}(t) p(t) 的第 i i i 个坐标是 t 时间web surfer在网页 i i i 的概率,因此向量 p ( t ) \mathbf{p}(t) p(t) 是网页间的概率分布向量。在这里插入图片描述
  2. 平稳分布stationary distribution
    p ( t + 1 ) = M ⋅ p ( t ) \mathbf{p}(t+1)=M\cdot \mathbf{p}(t) p(t+1)=Mp(t)(M是web surfer的转移概率,这个公式的逻辑感觉和 r = M ⋅ r \mathbf{r}=M\cdot \mathbf{r} r=Mr 其实类似)
    如果达到这种条件,即下一时刻的概率分布向量与上一时刻的相同: p ( t + 1 ) = M ⋅ p ( t ) = p ( t ) \mathbf{p}(t+1)=M\cdot \mathbf{p}(t)=\mathbf{p}(t) p(t+1)=Mp(t)=p(t) p ( t ) \mathbf{p}(t) p(t) 是随机游走的stationary distribution
    r = M ⋅ r \mathbf{r}=M\cdot \mathbf{r} r=Mr,所以 r \mathbf{r} r 是随机游走的stationary distribution在这里插入图片描述这种做法将PageRank与随机游走概念进行了联合

2.4 Eigenvector Formulation

  1. 无向图的邻接矩阵的特征向量是节点特征eigenvector centrality4,而PageRank定义在有向图的随机邻接矩阵上。在这里插入图片描述
  2. 1 ⋅ r = M ⋅ r 1\cdot\mathbf{r}=M\cdot\mathbf{r} 1r=Mr
    rank vector r \mathbf{r} r 是随机邻接矩阵M的特征向量,对应特征值为1。
    从任一向量 u \mathbf{u} u 开始,极限 M ( M ( . . . M ( M u ) ) ) M(M(...M(M\mathbf{u}))) M(M(...M(Mu))) 是web surfer的长期分布,PageRank=极限分布=M的principal eigenvector5
    根据这个思路,我们就能找到PageRank的求解方式:power iteration在这里插入图片描述
    limit极限
    limiting distribution极限分布
    6
    相当于是random surfer一直随机游走,直至收敛,到达稳定状态。
    这个M的叠乘可以让人联想到Katz index叠乘邻接矩阵A7
    相比高斯消元法,power iteration是一种scalable的求解PageRank方法。
  3. PageRank总结
    1. 通过网络链接结构衡量图中节点的重要性
    2. 用随机邻接矩阵M建立web surfer随机游走模型
    3. PageRank解方程: r = M ⋅ r \mathbf{r}=M\cdot \mathbf{r} r=Mr
      r \mathbf{r} r 可被视作M的principle eigenvector,也可被视作图中随机游走的stationary distribution

3. PageRank: How to solve?

对每个节点赋初始PageRank
迭代:重复计算每个节点的PageRank: r j t + 1 = ∑ i → j r i ( t ) d i r_j^{t+1}=\sum\limits_{i\rightarrow j}\frac{r_i^{(t)}