1. Graph as Matrix
- 本节课研究矩阵角度的图分析和学习。
- 这里的矩阵就是指邻接矩阵。
- 将图视为矩阵形式，可以通过随机游走的方式定义节点重要性（即PageRank），通过矩阵分解matrix factorization (MF)来获取节点嵌入，将其他节点嵌入（如node2vec）也视作MF。
2. PageRank / the Google Algorithm
- PageRank是谷歌搜索用的算法，用于对网页的重要性进行排序。在搜索引擎应用中，可以对网页重要性进行排序，从而辅助搜索引擎结果的网页排名。
- 在现实世界中，将整个互联网视作图：将网页视作节点，将网页间的超链接视作边
有一些问题会影响我们如何定义节点（但是本节课暂时不考虑这些问题）：
- Dynamic pages created on the fly2
- dark matter：不可达（如有密码等）的database generated pages
- 一个网页之间互相链接的情况的示例：
老一点的网页超链接都是navigational纯导航到其他页面的，当代的很多链接则是transactional用于执行发布、评论、点赞、购买等功能事务的。本课程中主要仅考虑那种网页之间互相链接的情况。
- 将网页看作有向图，以链接指向作为边的方向（这个网页/节点能直接跳转到的网页就作为其下一个节点successor）：
- 其他可表现为有向图形式的信息网络示例：论文引用，百科全书中词条间的互相引用
- 在图中，我们想要定义节点的重要性importance，通过网络图链接结构来为网页按重要性分级rank。以下将介绍3种用以计算图中节点重要性的方法：
- PageRank
- Personalized PageRank (PPR)
- Random Walk with Restarts (RWR)
- 衡量节点重要性：认为一个节点的链接越多，那么这个节点越重要。
有向图有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
2.2 PageRank: Matrix Formulation
2.3 Connection to Random Walk
这种做法将PageRank与随机游走概念进行了联合
2.4 Eigenvector Formulation
- 无向图的邻接矩阵的特征向量是节点特征eigenvector centrality，而PageRank定义在有向图的随机邻接矩阵上。
limit极限
limiting distribution极限分布7
相当于是random surfer一直随机游走，直至收敛，到达稳定状态。
这个M的叠乘可以让人联想到Katz index叠乘邻接矩阵A8。
相比高斯消元法，power iteration是一种scalable的求解PageRank方法。
2022.6.25补：值得一提的是，我看了TextRank的paper，发现TextRank求接近极限的方法是用一个threshold，改变量小于threshold就认为convergence了。我感觉这个逻辑有点像是梯度下降，虽然理论上是可以抵达至少局部最优点的，但是实践上也是要么限定最大迭代次数要么给定threshold（一般是前者吧）……之类的
- PageRank总结
3. PageRank: How to solve?
- power iteration示例：
- PageRank的问题及其解决方案
- spider trap：所有出边都在一个节点组内，会吸收所有重要性
random surfer会在圈子里打转，出不去
- dead end：没有出边，造成重要性泄露
random surfer无处可去，迷路重要性直接跳崖……
- dead ends解决方案：random jumps or teleports
从dead-ends出发的web surfer随机跳到任意网页（相当于从dead end出发，向所有节点连了一条边）
- spider-traps在数学上不是个问题，但是无法得到我们想要的PageRank结果；因此要在有限步内跳出spider traps。
dead-ends在数学上就是问题（其随机邻接矩阵列和不为0，初始假设直接不成立），因此要直接调整随机邻接矩阵，让web surfer无路可走时可以直接teleport。
注意：在本节课中random walk只是一种直觉假设，我们没有真的模拟random walk
2022.4.22更新：有人问我了，我都快忘光了，凭记忆补充一下这一部分的公式推导过程：
- random teleports举例：
M是个spider trap，所以加上random teleport links
G也是一个转移概率矩阵
- PageRank结果示例
- PageRank求解部分总结：
- 用power iteration方法求解 r = G ⋅ r \mathbf{r}=G\cdot\mathbf{r}r=G⋅r （G是随机邻接矩阵）
- 用random uniform teleporation解决dead-ends和spider-traps问题
4. Random Walk with Restarts & Personalized PageRank
- 举例：推荐问题（一个由user和item两种节点组成的bipartite graph）
- Bipartite User-Item Graph
求解目标：图节点间相似性（针对与item Q交互的user，应该给他推荐什么别的item？）
可以直觉地想到，如果item Q和P都与相似user进行过交互，我们就应该推荐Q
但是我们如何量化这个相似性呢？
- 衡量节点相似性的问题
A A’比B B’近可以因为它们之间距离较短；但是A A’和C C’距离相等，C C’却有着共同用户，这又如何比较呢？如果引入shared neighbors作为标准，D D’和C C’有相同的share neighbors，但是D D’的共同用户之间的相似性却很低，这又如何衡量呢？
PageRank, PPR和RWR是同一种算法，只在teleport set上有区别
- Random Walks
每个节点都有重要性，在其边上均匀分布，传播到邻居节点。
对 query_nodes 模拟随机游走：
- 随机游走到一个邻居，记录走到这个节点的次数（visit count）
- 以 alpha 概率从 query_nodes 中某点重启
- 结束随机游走后，visit count最高的节点就与 query_nodes 具体最高的相似性（直觉上这就是 query_nodes 最容易走到、最近的点了）
- 以 Q 作为示例：
算法伪代码（从item随机游走到另一个item，记录visit_count；以一定概率返回query_nodes）：
结果示例：
在示例中是模拟的random walk，但其实也可以用power iteration的方式来做
- RWR的优点在于，这种相似性度量方式考虑到了网络的如下复杂情况：
- multiple connections
- multiple paths
- direct and indirect connections
- degree of the node
- 对不同PageRank变体的总结
- 总结
5. Matrix Factorization and Node Embeddings
- 回忆上一章9讲到的embedding lookup的encoder
- 矩阵分解问题：基于random walk定义的相似性（这部分公式我完全没看懂，以后有缘看论文）
DeepWalk和node2vec有基于random walk定义的更复杂的节点相似性，但还是可以视作矩阵分解问题，不过矩阵变得更复杂了。（相当于是把上面的A给换了）
DeepWalk：
albeit尽管
v o l ( G ) 是2倍的边数
node2vec的更复杂
- 通过矩阵分解和随机游走进行节点嵌入的限制
- 无法获取不在训练集中的节点嵌入，每次新增节点都要对全部数据集重新计算嵌入
（PageRank也可视作一维的节点嵌入）
- 无法捕获结构相似性：比如图中节点1和节点11在结构上很相似，但是节点嵌入会差别很大（随机游走走不过去）
（如果跑匿名随机游走的话，倒是能捕获到结构相似性）
- 无法使用节点、边和图上的特征信息
- 如何解决这些问题：Deep Representation Learning and Graph Neural Networks（后期讲解。我也将继续撰写相应笔记）
6. 本章总结
