本文已参与「新人创作礼」活动，一同开启创作之路。

本文首发于CSDN。

诸神沉默不语-个人CSDN博文目录 cs224w（图机器学习）2021冬天课程学习笔记调集

@[toc]

YouTube视频观看地址1 视频观看地址2 视频观看地址3

本章主要内容： 咱们的使命是：已知图中一部分节点的标签，用图中节点之间的联系来将标签分配到一切节点上。归于半监督学习使命。 本节课咱们学习message passing办法来完成这一使命。对某一节点的标签进行猜测，需求其本身特征、街坊的标签和特征。 message passing的假定是图中类似的节点之间会存在链接，也便是相邻节点有标签相同的倾向。这种现象能够用homophily（类似节点倾向于调集）、influence（联系会影响节点行为）、confounding（环境影响行为和联系）来解说。

collective classification给一切节点同时猜测标签的概率散布，依据马尔科夫假定（某一点标签仅取决于其街坊的标签）。 local classifier（用节点特征猜测标签）→ relational classifier（用街坊标签 和/或 特征，猜测节点标签）→ collective inference（继续迭代）

本节课讲如下三种collective classification的实现技能：

• relational classification：用街坊标签概率的加权平均值来代表节点标签概率，循环迭代求解
• iterative classification：在练习集上练习用 (节点特征) 和 (节点特征，街坊标签summary $z$) 两种自变量猜测标签的分类器 1\phi_11​ 和 2\phi_22​，在测试集上用 1\phi_11​ 赋予初始标签，循环迭代求解 $z\rightleftharpoons$ 用 2\phi_22​ 从头猜测标签
• belief propagation：在边上传递节点对街坊的标签概率的置信度（belief）的message/estimate，迭代核算边上的message，终究得到节点的belief。有环时可能呈现问题。

1. Message Passing and Node Classification

1. 本章重要问题：给定网络中部分节点的标签，怎样用它们来分配整个网络中节点的标签？（举例：已知网络中有一些欺诈网页，有一些可信网页，怎样找到其他欺诈和可信的网页节点？） 练习数据中一部分有标签，剩下的没标签，这种便是半监督学习¹ 对这个问题的一种处理方式：node embeddings²

   

2. 本章咱们介绍一个处理上述问题的办法³：message passing 运用message passing依据“网络中存在联系correlations”这一直觉，亦即类似节点间存在链接。 message passing是经过链接传递节点的信息，感觉上会比较类似于 PageRank⁴ 将节点的vote经过链接传递到下一节点，可是在这里咱们更新的不再是重要性的分数，而是对节点标签猜测的概率。 核心概念 collective classification：同时将标签分配到网络中的一切节点上。 本章将讲述三种实现技能：
   1. relational classification
   2. iterative classification
   3. belief propagation

      

3. 举例：节点分类 半监督学习问题：给出一部分节点的标签（如图中给出了一部分赤色节点、一部分绿色节点的标签），猜测其他节点的标签

   

4. 网络中存在联系correlations： 类似的行为在网络中会相互相关。 correlation：附近的节点会具有相同标签

   

5. 导致correlation的两种解说⁵： homophily（同质性，趋同性，同类相吸准则）：个别特征影响交际连接 influence：交际连接影响个别特征

   

   1. homophily：类似节点会倾向于交流、相关（物以类聚，人以群分） 在网络研究中得到了许多观察 举例：同领域的研究者更容易树立联系，因为他们参与相同的会议、学术讲演……等活动

      

      Birds of a feather flock together 是句俗话
   2. homophily举例：一个在线交际网络，以人为节点，友谊为边，经过人们的爱好将节点分为多类（用色彩区别）。 从图中能够看出，各种色彩都别离聚在一同，亦即有相同爱好（同色）的人们更有调集在一同的倾向。

      

      图片出处书本PDF版下载地址：D Easley, Kleinberg J . Networks, Crowds, and Markets[M]. Cambridge University Press, 2010.
   3. influence：交际链接会影响个人行为。 举例：用户将喜爱的音乐推荐给朋友。

      

6. 既然知道了网络中联系的影响机制，咱们就期望能够经过网络中的链接联系来辅佐猜测节点标签。 如图举例，咱们期望依据已知的绿色（label 1）和赤色（label 0）节点来猜测灰色（标签不知道）节点的标签。将各节点从 1-9 标示上node-id。

   

7. 处理分类问题的逻辑： 咱们已知类似节点会在网络中更加靠近，或许直接相连。 因而依据相关推定guilt-by-association：假如我与具有标签X的节点相连，那么我也很可能具有标签X（依据马尔科夫假定⁶） 举例：互联网中的歹意/好心网页：歹意网页往往会相互相关，以添加曝光，使其看起来更可靠，并在搜索引擎中进步排名。

   

   猜测节点 $v$ 的标签需求：
   1. $v$ 的特征
   2. $v$ 街坊的标签
   3. $v$ 街坊的特征

      

8. 半监督学习
   1. 使命：假定网络中存在homophily，依据一部分已知标签（红/绿）的节点猜测剩下节点的标签

      

   2. 示例使命： $A$：nn的邻接矩阵 Y={0,1}nY=\{0,1\}^nY={0,1}n：标签向量 目标：猜测不知道标签节点归于哪一类

      

9. 处理办法：collective classification
   1. collective classification的运用
      1. Document classification
      2. 词性标示Part of speech tagging
      3. Link prediction
      4. 光学字符识别Optical character recognition
      5. Image/3D data segmentation
      6. 实体解析Entity resolution in sensor networks
      7. 垃圾邮件Spam and fraud detection
   2. collective classification概述 直觉：运用网络中的联系同时对相连节点进行分类 概率结构propabilistic framework⁷ 马尔科夫假定⁸：节点 $v$ 的标签 YvY_vYv​ 取决于其街坊 NvN_vNv​ 的标签：P(Yv)=P(Yv∣Nv)P\left(Y_v\right)=P\left(Y_v|N_v\right)P(Yv​)=P(Yv​∣Nv​)

      

      collective classification分成三步：
      1. local classifier：分配节点的初始标签（依据节点特征树立规范分类，不运用网络结构信息）

         

      2. relational classifier：捕获联系（依据街坊节点的标签 和/或 特征，树立猜测节点标签的分类器模型）（运用了网络结构信息）

         

      3. collective inference：传达联系（在每个节点上迭代relational classifier，直至街坊间标签的不一致最小化。网络结构影响终究猜测结果）

         

10. 问题设置：猜测无标签（灰色）节点 $v$ 的标签 YvY_vYv​。一切节点 $v$ 具有特征向量 fvf_vfv​。部分节点的标签已给出（绿色是1，赤色是0） 使命：求解 P(Yv)P\left(Y_v\right)P(Yv​)

    

11. 对本章后文内容的概述

    

2. Relational Classification / Probabilistic Relational Classifier

1. 根底思维：节点 $v$ 的类概率 YvY_vYv​ 是其街坊类概率的加权平均值。 对有标签节点 $v$，固定 YvY_vYv​ 为实在标签ground-truth label Yv∗Y_v^*Yv∗​。 对无标签节点 $v$，初始化 Yv=0.5Y_v=0.5Yv​=0.5。（参阅⁶，也能够用其他prior） 以随机次序（参阅⁶，不一定要是随机次序，但实证上发现最好是。这个次序会影响结果，尤其对小图而言）更新一切无标签节点，直至收敛或抵达最大迭代次数

   

2. 更新公式：P(Yv=c)=1∑(v,u)∈EAv,u∑(v,u)∈EAv,uP(Yu=c)P\left(Y_v=c\right)=\frac{1}{\sum_{(v,u)\in E}A_{v,u}}\sum\limits_{(v,u)\in E}A_{v,u}P\left(Y_u=c\right)P(Yv​=c)=∑(v,u)∈E​Av,u​1​(v,u)∈E∑​Av,u​P(Yu​=c) 邻接矩阵 Av,uA_{v,u}Av,u​ 能够带权 分母是节点 $v$ 的度数或入度⁹ P(Yv=c)P\left(Y_v=c\right)P(Yv​=c) 是节点 $v$ 标签为 $c$ 的概率
   问题：
   1. 不一定能收敛
   2. 模型无法运用节点特征信息

      

3. 举例
   1. 初始化：迭代次序便是node-id的次序。有标签节点赋原标签，无标签节点赋0（PYv=P(Yv=1)P_{Y_v}=P\left(Y_v=1\right)PYv​​=P(Yv​=1)）

      

   2. 第一轮迭代
      1. 更新节点3

         

      2. 更新节点4

         

      3. 更新节点5

         

      4. 更新完一切无标签节点

         

   3. 第二轮迭代：结束后发现节点9收敛

      

   4. 第三轮迭代：结束后发现节点8收敛

      

   5. 第四轮迭代

      

   6. 收敛后：猜测概率>0.5的节点为1，<0.5的为0

      

3. Iterative Classification

1. relational classifiers没有运用节点特征信息，所以咱们运用新办法iterative classification。 iterative classification主思路：依据节点特征及街坊节点标签对节点进行分类

   

2. iterative classification的办法：练习两个分类器： 1(fv)\phi_1\left(f_v\right)1​(fv​) 依据节点特征向量 fvf_vfv​ 猜测节点标签 2(fv,zv)\phi_2\left(f_v,z_v\right)2​(fv​,zv​) 依据节点特征向量 fvf_vfv​ 和街坊节点标签summary zvz_vzv​ 猜测节点标签

   

3. 核算summary zvz_vzv​ zvz_vzv​ 是个向量，能够是街坊标签的直方图（各标签数目或份额），街坊标签中呈现次数最多的标签，街坊标签的类数

   

4. iterative classifier的结构
   1. 第一步：依据节点特征树立分类器 在练习集上练习如下分类器（能够用线性分类器、神经网络等算法）：
      1. 1(fv)\phi_1\left(f_v\right)1​(fv​) 依据 fvf_vfv​ 猜测 YvY_vYv​
      2. 2(fv,zv)\phi_2\left(f_v,z_v\right)2​(fv​,zv​) 依据 fvf_vfv​ 和 zvz_vzv​（$v$ 街坊标签的summary）猜测 YvY_vYv​
   2. 第二步：迭代至收敛 在测试集上，用 1\phi_11​ 猜测标签，依据 1\phi_11​ 核算出的标签核算 zvz_vzv​ 并用 2\phi_22​ 猜测标签 对每个节点重复迭代核算 zvz_vzv​、用 2\phi_22​ 猜测标签这个进程，直至收敛或抵达最大迭代次数（10, 50, 100……这样，不能太多¹⁰） 留意：模型不一定能收敛

      

5. 核算举例：网页分类问题 节点是网页，链接是超链接，链接有向。节点特征简化设置为2维二元向量。猜测网页主题。

   

   1. 依据节点特征练习分类器（1\phi_11​）：

      

      能够假定分类器以特征第一个元素作为分类规范，所以对中心节点分类错误。
   2. 依据 1\phi_11​ 得到的结果，核算 zvz_vzv​。 此处设置 zvz_vzv​ 为四维向量，四个元素别离为指向该节点的节点中标签为0和1的数目、该节点指向的节点中标签为0和1的数目。 在这一步运用了网络结构信息。

      

6. 进程举例
   1. 第一步：在练习集上练习 1\phi_11​ 和 2\phi_22​

      

   2. 第二步：在测试集上猜测标签
      1. 用 1\phi_11​ 猜测 YvY_vYv​

         

      2. 循环迭代：
         1. 用 YvY_vYv​ 核算 zvz_vzv​

            

         2. 用 2\phi_22​ 猜测标签

            

         3. 迭代直至收敛

            

      3. 结束迭代（收敛或到达最大迭代次数），得到终究猜测结果

         

7. 对relational classification和iterative classification的总结

   

4. Loopy Belief Propagation

名字叫loopy是因为loopy BP办法会运用在有许多环的情况下。

1. belief propagation是一种动态规划办法，用于答复图中的概率问题（比如节点归于某类的概率）。 街坊节点之间迭代传递信息pass message（如传递信任对方归于某一类的概率），直至达到共识（大家都这么信任），核算终究置信度（也有翻译为信念的）belief。 参阅⁶：问题中节点的状况并不取决于节点本身的belief，而取决于街坊节点的belief。

   

2. message passing
   1. 比如介绍： 使命：核算图中的节点数（留意，假如图中有环会呈现问题，后文会讲有环的情况。在这里不考虑） 约束：每个节点只能与街坊交互（传递信息）
      举例：path graph（节点排成一条线）

      

   2. 算法
      1. 定义节点次序（生成一条路径）
      2. 依据节点次序生成边方向，然后决议message passing的次序
      3. 按节点次序，核算其对下一节点的信息（至今数到的节点数），将该信息传递到下一节点

         

   3. 每个节点接纳街坊信息，更新信息，传递信息

      

3. 将path graph的情况泛化到树上：从叶子节点到根节点传递信息

   

   在树结构上更新置信度：

   

   

4. Loopy BP Algorithm 从 $i$ 传递给 $j$ 的信息，取决于 $i$ 从街坊处接纳的信息。每个街坊给 $i$ 对其状况的置信度的信息。

   

5. notation¹¹
   1. label-label potential matrix \psi：节点及其街坊间的dependency (Yi,Yj)\psi\left(Y_i,Y_j\right)(Yi​,Yj​)：节点 $i$ 是节点 $j$ 的街坊，已知 $i$ 归于类 YiY_iYi​，(Yi,Yj)\psi\left(Y_i,Y_j\right)(Yi​,Yj​) 与 $j$ 归于类 YjY_jYj​ 的概率成份额。
   2. prior belief \phi：(Yi)\phi\left(Y_i\right)(Yi​) 与节点 $i$ 归于类 YiY_iYi​ 的概率成份额。
   3. mi→j(Yj)m_{i\rightarrow j}\left(Y_j\right)mi→j​(Yj​)：$i$ 对 $j$ 归于类 YjY_jYj​ 的message/estimate
   4. $\mathcal{L}$：一切类/标签的调集

      

6. Loopy BP Algorithm
   1. 将一切信息初始化为1
   2. 对每个节点重复：mi→j(Yj)=∑Yi∈L(Yi,Yj)i(Yi)∏k∈Ni\jmk→i(Yi),∀Yj∈Lm_{i\rightarrow j}\left(Y_j\right)=\sum_{Y_i\in \mathcal{L}}\psi\left(Y_i,Y_j\right)\phi_i\left(Y_i\right)\prod\limits_{k\in N_i\backslash j}m_{k\rightarrow i}\left(Y_i\right),\ \forall Y_j\in \mathcal{L}mi→j​(Yj​)=∑Yi​∈L​(Yi​,Yj​)i​(Yi​)k∈Ni​\j∏​mk→i​(Yi​),∀Yj​∈L

      

      蓝框里边那个反斜杠指除了j
   3. 收敛后，核算 bi(Yi)=b_i\left(Y_i\right)=bi​(Yi​)= 节点 $i$ 归于类 YiY_iYi​ 的置信度 bi(Yi)=i(Yi)∏j∈Nimk→i(Yi)b_i\left(Y_i\right)=\phi_i\left(Y_i\right)\prod_{j\in N_i}m_{k\rightarrow i}\left(Y_i\right)bi​(Yi​)=i​(Yi​)∏j∈Ni​​mk→i​(Yi​)

      

7. 示例
   1. 现在咱们考虑图中有环的情况，节点没有次序了。咱们采用上述算法，从随机节点开端，沿边更新街坊节点。

      

   2. 因为图中有环，来自各子图的信息就不独立了。信息会在圈子里加强（就像PageRank里的spider trap）

      

8. 可能呈现的问题：置信度不收敛（如图，信息在环里被加强了） 可是因为实际国际的实在复杂图会更像树，就算有环也会有弱连接，所以仍是能用Loopy BP

   

   heuristic启发式的
   

   

9. 置信度传达办法的特点
   1. 优点
      1. 易于编程及同步运算
      2. 可泛化到任何形式potentials¹²（如高阶）的图模型上
   2. 应战：不一定能收敛（参阅⁶：尤其在闭环多的情况下）（所以会选择少跑几轮……为啥啊？）
   3. potential¹² functions (parameters) (label-label potential matrix) 需求练习来估量

      

5. 本章总结

1. 学习了怎样利用图中的联系来对节点做猜测
2. 主要技能：
   1. relational classification
   2. iterative classification
   3. loopy belief propagation

6. 其他文中未提及的参阅资料

1. cs224w 图神经网络 学习笔记（七）Message Passing and Node Classification 信息传达与节点分类_喵木木的博客-CSDN博客 这篇是19年秋版cs224w的笔记
2. CS224W 图机器学习 自学笔记7 – Node Classification – 知乎 同上

Footnotes

1. 显然这是个十分简略粗暴的不严厉定义。 我没有详细了解过半监督学习，谷歌了一下感觉假如有需能够参阅一下这篇知乎文章：半监督深度学习小结 ↩

2. 节点嵌入相关的常识可参阅我之前写的Lecture 3笔记：cs224w（图机器学习）2021冬天课程学习笔记3: Node Embeddings 可是我其实没搞懂为什么说节点嵌入能够处理这个……半监督学习问题？这里的意思是说节点嵌入将节点表示为结构化向量，然后用结构化的半监督学习模型来处理这个问题吗？此外我上网查了一下，还看到有说node2vec是一种半监督学习的算法（它不是没标签吗，谁监督的啊？）…… ↩

3. PPT中说message passing是一个alternative framework。 alternative framework是什么玩意？我本来还以为只是字面解说，百度了一下发现这是个叫什么相异设想的学术概念，是教育理论上把学生由感性认识得出的偏离科学现象本质和科学概念的了解与主意（相异设想_百度百科）…… 什么玩意儿？ 为便了解，我就以为是说message passing是处理该半监督学习问题的一种办法了。 ↩

4. PageRank相关的常识可参阅我之前写的Lecture 4笔记：cs224w（图机器学习）2021冬天课程学习笔记4 Link Analysis: PageRank (Graph as Matrix) ↩

5. 参阅⁶，除homophily和influence外还有confounding

   

   节点展现出类似性。例如环境影响咱们的许多维度，说什么语言、听什么歌、有什么政治倾向等。 ↩

6. 官方课程笔记本章部分：Message Passing and Node Classification ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

7. 这又是什么玩意儿啊……横竖我的了解便是，collective classification也是算的某一节点归于某一类的概率。 看到知乎上有篇文章，放了许多论文，显然我还没看，放这以供参阅：机器学习中的概率结构 ↩

8. 马尔科夫假定，我看了一下，如同大意是以为下一时间的概率只受上一时间的状况影响。然后依据这一点能够写出状况转移矩阵A（Aij=P(qt=j∣qt−1=i)A_{ij}=P\left(q_t=j|q_{t-1}=i\right)Aij​=P(qt​=j∣qt−1​=i)）。 其他还没研究。横竖在本课程中直接了解正文那个公式就够用的了，再看其他，未免太尴尬我小小的脑瓜了。 参阅资料（尽管说是参阅资料可是我彻底没有看懂。哎这已经是我的日常了，我什么时候才干变成文献吞吐如流水的大佬呀！）： ①了解Markov假定 – ybdesire – 博客园 ②条件独立 – 维基百科，自由的百科全书 ③MarkovModels马尔科夫模型读书笔记_辛明辉的专栏-CSDN博客 ④Markov property – Wikipedia ⑤Causal Markov condition – Wikipedia ↩

9. 这部分是这样的，假如是无向图就没什么问题，可是假如是有向图！这个公式不便是聚合以 $v$ 为source的街坊吗？那这个分母应该是 $v$ 的出度啊…… 但问题在于既然是聚合街坊节点信息，那就不应该只考虑出度或许入度啊，又不像PageRank说明晰便是算指向节点的街坊的vote。这部分我简略谷歌了一下，没找到。横竖本文给的比如是无向图的，以后如有需求再仔细看吧…… 参阅资料： Wang, Xi & Sukthankar, Gita. (2013). Multi-label relational neighbor classification using social context features. 464-472. 10.1145/2487575.2487610. 上一论文的KDD PPT：2013 KDD conference presentation–“Multi-Label Relational Neighbor Cl… ↩

10. 没说为啥迭代次数不能太多，我也不知道为啥 ↩

11. 对于这些东西是怎样来的，是来干啥的，还有底下那个Loopy BP的迭代公式，详细是怎样回事，我还没搞懂…… ↩

12. potential到底是个什么玩意…… ↩ ↩²