链接分析：PageRank算法

​ 这一节的内容主要从矩阵的角度来进行图的分析和学习，我们可以将互联网看成一张巨大的图，里面的网页就是图中的一个个节点，而网页可以通过超链接可以跳转到别的网页，称为链接link，可以把这种关系作为图中的有向边，因此互联网中的网页构成一张大而稀疏的有向图，可以用一个邻接矩阵来表示。类似的结构有论文引用图等等。

​ 但是图中每个节点并不都是同等重要的，可以通过一系列链接分析的方法来分析出不同节点的重要性，一般认为一个网站如果有很多链接，那么它往往就比较重要。而出链接和入链接又是两种不同的链接，又应该有不同的考虑。PageRank算法认为被重要的网页指向的网页也往往更重要。

PageRank算法模型

节点的权重

​ 我们可以在网络图中定义是一个节点的出度，而节点的权重就可以表示为： 我们可以将这种表示形式矩阵化，用一个矩阵M来表示各个节点之间的权重关系，那么根据上面的定义可以得知： 这个矩阵M每一列的和都是1，我们可以用一个向量r来表示每个网页的重要程度，那么就有：

图中的随机游走

​ 在任何一个时间t时假设访问到了网页i中，下一个时刻t+1则访问i指向的其中一个网页j，这样就构成了一次随机游走，用向量来表示t时刻每个网页被访问到的概率，那么这样一来就有： 我们发现矩阵的权重向量r也可以表示随机游走的分布情况，进一步我们发现r其实就是矩阵M的特征向量，因此PageRank实际上就是矩阵M最大的的特征向量，我们一般用幂法可以得到矩阵M的最大特征向量。

如何求解PageRank

  • 可以给pagerank赋予一定的初始值，然后通过公式不断迭代直到r的变化小于一定的阈值之后才结束，得到最终的pagerank的结果，这种方法也就是幂法，求出的结果实际上是M的特征之中范数最大的那一个

  • 问题在于：

    • 有一些页面时dead end，没有跳转到其他网页的链接，这可能会导致“泄漏”
    • Spider-Trap问题：所有的外部链接都在一个组内，即随机游走会陷入一个循环中
    • 这些情况都会导致上述计算方法最后不收敛，因此要想办法解决这个问题

  • 解决方法：

    • 对于dead end问题，可以重新调整矩阵M中的内容：

      image-20210323203140803

    • 对于Spider-Trap问题，可以在每次做选择的过程中以一定的概率跳转到随机的网页中去，这样就可以从循环中跳出来

  • Google矩阵上面的spider-trap问题的迭代形式

个性化的PageRank

  • 通过几个特定的节点来衡量所有节点的rank，可以用带restart的随机游走高效计算，这是考虑到了不同用户之间的浏览偏好往往不同，不能用全局的所有节点作为衡量标准，这样一来可以实现个性化的推荐

消息传递和节点分类

  • 这一节内容主要关注对于一个给定的网络结构，一些节点已经做好了标注，那么我们如何对图中的剩余节点进行标准，就比如一张图中已知部分节点是可疑的，另一部分节点是可信的，那么我们应该如何判定剩下那些没有标注的节点是否可信呢？
    • 这类任务被称为半监督的节点分类问题
    • 之前已经介绍了节点嵌入的方法可以识别相似的节点，而这一节主要介绍的方法是消息传递
  • 一般我们认为网络中的关系是具有相关性的，也就是说相似的节点会互相连接，并且相近的节点可能属于相同的类型
    • 同质性Homophily：指的就是相同或者类似的节点个体会和其他的节点相互连接
    • 影响：网络中的连接关系可能会影响到单个节点，即节点可能会被与之相互连接的节点给带偏
  • 这样的半监督学习经常被用在：
    • 文本分类
    • 语音标记
    • 连接预测
    • 光学字符识别
    • 图像和3D分割
    • 节点异常检测
  • 这一节内容将主要介绍三种实现上述半监督图学习的技术：
    • 关系分类Relational classification
    • 可迭代分类Iterative classification
    • 信任传播Belief propagation

关系分类

​ 关系分类的基本想法：节点v的类概率是一个节点附近节点的类别的加权平均(这里我们只考虑二分类问题，正反类别的标签分别用1和0来表示)，而对于已经有标记的节点v，其可以直接设置成其真实类别，而对于没有标记的节点可以将其初始化为，然后对所有的节点进行类似于加权平均的更新知道收敛或者达到最大迭代次数上限。

  • 其中A表示每条边的权重
  • 问题在于：收敛是没有保证的，并且模型没有用到节点的特征信息

迭代分类

​ 相比于关系分类，迭代分类会使用节点v的一系列特征构成的特征向量和邻近节点的标签，而这种分类方式需要训练两个分类器：

  • 通过节点的特征来预测节点的标签

  • 通过特征向量和邻近节点的标记来共同预测节点的标签

    ​ 训练两个分类器只是第一阶段，第二阶段需要进行迭代训练直到结果收敛或者训练结束，但是结果是否收敛依然没有保证。

举例：网页分类

  • 首先训练一个基于二维特征向量的分类器，用邻近节点(区分出和入节点)的特征向量作为
  • 然后按照步骤训练出两个分类器，然后用测试集来测试分类器的效果，并对关系特征和标签进行更新
  • 进行迭代更新，直到收敛或者达到次数上限

协作分类：信任传播机制

​ 信任传播机制是一种动态规划算法，通过一个节点和节点之间互相“通信”和传递消息的迭代过程，当节点直接达到共识的时候就可以计算出最后的结果

一个简单的消息传播的例子

​ 举一个简单的例子来说明消息传递的作用，比如我们需要在一个图中计算节点总数，并且每个节点只能和与之相邻的节点之间进行通信，简单的消息传递算法的实现如下：

  • 定义节点的顺序形成一条完整的路径
  • 每次向下一个节点来传播当前统计到的节点个数，最后一个节点要发送出去的数据就是结果
  • 这样的算法也可以在树状的结构中进行，区别就是要从叶节点将信息汇总到根节点

循环消息传递算法

​ 加入一个节点i指向j，那么i将会给j传递消息，而传递什么消息需要根据i从指向i的节点中获得的信息来决定，循环消息传递算法中定义了这样几个关键的变量：

  • 标签势能矩阵，表示对于一个节点j，如果给定它的邻居节点i属于类别时，节点j属于类别的概率

  • 先验信任 表示节点i属于类别的概率

  • i向j传递的消息可以记成，这表示i估计j的最终类型是在循环消息传递算法中，传递的消息可以表示为：

  • 这种计算方式的意思是，如果i预测j的最终标签是，那么就需要考虑节点i所有可能的标签，并且对于每一个标签计算节点i收到的信息是节点i属于类别进行求和，我们可以记

    • 是先验概率和所有从邻居节点收到消息的和的乘积

  • 如果我们遇到的图是有环的，那么这样一来节点就不存在一个确定的顺序，但我们依然可以用上述算法来计算信任的传播。当有顺序的时候可以从任意一个节点开始，然后依次更新其邻居节点的信息，但是当图有环的时候，从不同的子图中获得的信息就不是独立的了，这个时候信任传递依然可以使用，但是会出现循环传递的情况，可能会导致不收敛的情况，但是在实际操作中，这个算法依然比较好用

image-20210325161712112