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

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

1. Graph as Matrix


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


2. PageRank / the Google Algorithm


  1. PageRank是谷歌搜索用的算法,用于对网页的重要性进行排序。在搜索引擎应用中,可以对网页重要性进行排序,从而辅助搜索引擎结果的网页排名。


  1. 在现实世界中,将整个互联网视作图:将网页视作节点,将网页间的超链接视作边

image.png

有一些问题会影响我们如何定义节点(但是本节课暂时不考虑这些问题):

  • Dynamic pages created on the fly2
  • dark matter:不可达(如有密码等)的database generated pages


  1. 一个网页之间互相链接的情况的示例:

image.png

老一点的网页超链接都是navigational纯导航到其他页面的,当代的很多链接则是transactional用于执行发布、评论、点赞、购买等功能事务的。本课程中主要仅考虑那种网页之间互相链接的情况。


  1. 将网页看作有向图,以链接指向作为边的方向(这个网页/节点能直接跳转到的网页就作为其下一个节点successor):

image.png


  1. 其他可表现为有向图形式的信息网络示例:论文引用,百科全书中词条间的互相引用

image.png


  1. 在图中,我们想要定义节点的重要性importance,通过网络图链接结构来为网页按重要性分级rank。以下将介绍3种用以计算图中节点重要性的方法:
  • PageRank
  • Personalized PageRank (PPR)
  • Random Walk with Restarts (RWR)


  1. 衡量节点重要性:认为一个节点的链接越多,那么这个节点越重要。

有向图有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

image.png

image.png


2.2 PageRank: Matrix Formulation

image.png

image.png

 

2.3 Connection to Random Walk

image.png

image.png

这种做法将PageRank与随机游走概念进行了联合


2.4 Eigenvector Formulation

  1. 无向图的邻接矩阵的特征向量是节点特征eigenvector centrality,而PageRank定义在有向图的随机邻接矩阵上。

image.png

image.png

image.png


limit极限

limiting distribution极限分布7

相当于是random surfer一直随机游走,直至收敛,到达稳定状态。

这个M的叠乘可以让人联想到Katz index叠乘邻接矩阵A8。

相比高斯消元法,power iteration是一种scalable的求解PageRank方法。

2022.6.25补:值得一提的是,我看了TextRank的paper,发现TextRank求接近极限的方法是用一个threshold,改变量小于threshold就认为convergence了。我感觉这个逻辑有点像是梯度下降,虽然理论上是可以抵达至少局部最优点的,但是实践上也是要么限定最大迭代次数要么给定threshold(一般是前者吧)……之类的


  1. PageRank总结

image.png


3. PageRank: How to solve?


image.png

image.png

image.png

image.png


  1. power iteration示例:

image.png

image.png


  1. PageRank的问题及其解决方案

image.png

image.png


  • spider trap:所有出边都在一个节点组内,会吸收所有重要性

image.png

random surfer会在圈子里打转,出不去


  • dead end:没有出边,造成重要性泄露

image.png

random surfer无处可去,迷路重要性直接跳崖……


  • image.png

image.png


  • dead ends解决方案:random jumps or teleports

从dead-ends出发的web surfer随机跳到任意网页(相当于从dead end出发,向所有节点连了一条边)

image.png


  • spider-traps在数学上不是个问题,但是无法得到我们想要的PageRank结果;因此要在有限步内跳出spider traps。

dead-ends在数学上就是问题(其随机邻接矩阵列和不为0,初始假设直接不成立),因此要直接调整随机邻接矩阵,让web surfer无路可走时可以直接teleport。

image.png


  • image.png

image.png


  • image.png

image.png

注意:在本节课中random walk只是一种直觉假设,我们没有真的模拟random walk

2022.4.22更新:有人问我了,我都快忘光了,凭记忆补充一下这一部分的公式推导过程:

image.png


  • random teleports举例:

image.png

M是个spider trap,所以加上random teleport links

G也是一个转移概率矩阵

image.png


  • PageRank结果示例
  • PageRank求解部分总结:
  1. 用power iteration方法求解 r = G ⋅ r \mathbf{r}=G\cdot\mathbf{r}r=G⋅r (G是随机邻接矩阵)
  2. 用random uniform teleporation解决dead-ends和spider-traps问题

image.png


4. Random Walk with Restarts & Personalized PageRank


  1. 举例:推荐问题(一个由user和item两种节点组成的bipartite graph)

image.png


  1. Bipartite User-Item Graph

求解目标:图节点间相似性(针对与item Q交互的user,应该给他推荐什么别的item?)

可以直觉地想到,如果item Q和P都与相似user进行过交互,我们就应该推荐Q

image.png

但是我们如何量化这个相似性呢?

image.png


  1. 衡量节点相似性的问题

image.png

A A’比B B’近可以因为它们之间距离较短;但是A A’和C C’距离相等,C C’却有着共同用户,这又如何比较呢?如果引入shared neighbors作为标准,D D’和C C’有相同的share neighbors,但是D D’的共同用户之间的相似性却很低,这又如何衡量呢?


image.png

image.png

PageRank, PPR和RWR是同一种算法,只在teleport set上有区别


  1. Random Walks

每个节点都有重要性,在其边上均匀分布,传播到邻居节点。

对 query_nodes 模拟随机游走:

  • 随机游走到一个邻居,记录走到这个节点的次数(visit count)
  • 以 alpha 概率从 query_nodes 中某点重启
  • 结束随机游走后,visit count最高的节点就与 query_nodes 具体最高的相似性(直觉上这就是 query_nodes 最容易走到、最近的点了)

image.png


  1. 以 Q 作为示例:

image.png

算法伪代码(从item随机游走到另一个item,记录visit_count;以一定概率返回query_nodes):

image.png

结果示例:

image.png

在示例中是模拟的random walk,但其实也可以用power iteration的方式来做


  1. RWR的优点在于,这种相似性度量方式考虑到了网络的如下复杂情况:
  • multiple connections
  • multiple paths
  • direct and indirect connections
  • degree of the node

image.png


  1. 对不同PageRank变体的总结

image.png


  1. 总结

image.png


5. Matrix Factorization and Node Embeddings


  1. 回忆上一章9讲到的embedding lookup的encoder

image.png

image.png

image.png

image.png



  1. 矩阵分解问题:基于random walk定义的相似性(这部分公式我完全没看懂,以后有缘看论文)

DeepWalk和node2vec有基于random walk定义的更复杂的节点相似性,但还是可以视作矩阵分解问题,不过矩阵变得更复杂了。(相当于是把上面的A给换了)


DeepWalk:

image.png

albeit尽管

v o l ( G ) 是2倍的边数


node2vec的更复杂


  1. 通过矩阵分解和随机游走进行节点嵌入的限制
  • 无法获取不在训练集中的节点嵌入,每次新增节点都要对全部数据集重新计算嵌入

image.png

(PageRank也可视作一维的节点嵌入)


  • 无法捕获结构相似性:比如图中节点1和节点11在结构上很相似,但是节点嵌入会差别很大(随机游走走不过去)

image.png

(如果跑匿名随机游走的话,倒是能捕获到结构相似性)


  • 无法使用节点、边和图上的特征信息

image.png


  • 如何解决这些问题:Deep Representation Learning and Graph Neural Networks(后期讲解。我也将继续撰写相应笔记)


6. 本章总结


image.png

目录
打赏
0
0
0
0
20
分享
相关文章
模型预测笔记(三):通过交叉验证网格搜索机器学习的最优参数
本文介绍了网格搜索(Grid Search)在机器学习中用于优化模型超参数的方法,包括定义超参数范围、创建参数网格、选择评估指标、构建模型和交叉验证策略、执行网格搜索、选择最佳超参数组合,并使用这些参数重新训练模型。文中还讨论了GridSearchCV的参数和不同机器学习问题适用的评分指标。最后提供了使用决策树分类器进行网格搜索的Python代码示例。
257 1
机器学习笔记(一) 感知机算法 之 原理篇
机器学习笔记(一) 感知机算法 之 原理篇
【机器学习】图神经网络:深度解析图神经网络的基本构成和原理以及关键技术
【机器学习】图神经网络:深度解析图神经网络的基本构成和原理以及关键技术
1558 2
技术心得记录:机器学习笔记之聚类算法层次聚类HierarchicalClustering
技术心得记录:机器学习笔记之聚类算法层次聚类HierarchicalClustering
80 0
图机器学习入门:基本概念介绍
图机器学习是机器学习的分支,专注于处理图形结构数据,其中节点代表实体,边表示实体间关系。本文介绍了图的基本概念,如无向图与有向图,以及图的性质,如节点度、邻接矩阵。此外,还讨论了加权图、自循环、多重图、双部图、异构图、平面图和循环图。图在描述数据关系和特征方面具有灵活性,为机器学习算法提供了丰富的结构信息。
231 0

热门文章

最新文章