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

本文首发于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$) 两种自变量预测标签的分类器 ${\varphi }_1$ 和 ${\varphi }_2$，在测试集上用 ${\varphi }_1$ 赋予初始标签，循环迭代求解 $z\rightleftharpoons$ 用 ${\varphi }_2$ 重新预测标签
• belief propagation：在边上传递节点对邻居的标签概率的置信度（belief）的message/estimate，迭代计算边上的message，最终得到节点的belief。有环时可能出现问题。

1. Message Passing and Node Classification

1. 本章重要问题：给定网络中部分节点的标签，如何用它们来分配整个网络中节点的标签？（举例：已知网络中有一些诈骗网页，有一些可信网页，如何找到其他诈骗和可信的网页节点？）
   训练数据中一部分有标签，剩下的没标签，这种就是半监督学习^{D Easley, Kleinberg J . Networks, Crowds, and Markets[M]. Cambridge University Press, 2010.}
2. influence：社交链接会影响个人行为。
   举例：用户将喜欢的音乐推荐给朋友。

既然知道了网络中关系的影响机制，我们就希望能够通过网络中的链接关系来辅助预测节点标签。
如图举例，我们希望根据已知的绿色（label 1）和红色（label 0）节点来预测灰色（标签未知）节点的标签。将各节点从 1-9 标注上node-id。

Footnotes

1. 显然这是个非常简单粗暴的不严格定义。
   我没有详细了解过半监督学习，谷歌了一下感觉如果有需可以参考一下这篇知乎文章：半监督深度学习小结 cs224w（图机器学习）2021冬季课程学习笔记3: Node Embeddings
   但是我其实没搞懂为什么说节点嵌入可以解决这个……半监督学习问题？这里的意思是说节点嵌入将节点表示为结构化向量，然后用结构化的半监督学习模型来解决这个问题吗？此外我上网查了一下，还看到有说node2vec是一种半监督学习的算法（它不是没标签吗，谁监督的啊？）…… 相异构想_百度百科）……
   什么玩意儿？
   为便理解，我就认为是说message passing是解决该半监督学习问题的一种方法了。 cs224w（图机器学习）2021冬季课程学习笔记4 Link Analysis: PageRank (Graph as Matrix) Message Passing and Node Classification 机器学习中的概率框架 理解Markov假设 – ybdesire – 博客园
   ②条件独立 – 维基百科，自由的百科全书
   ③MarkovModels马尔科夫模型读书笔记_辛明辉的专栏-CSDN博客
   ④Markov property – Wikipedia
   ⑤Causal Markov condition – Wikipedia 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… ↩

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

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

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