本文已参与「新人创作礼」活动,一起开启掘金创作之路。
本文首发于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 zz) 两种自变量预测标签的分类器 ϕ1phi_1 和 ϕ2phi_2,在测试集上用 ϕ1phi_1 赋予初始标签,循环迭代求解 z⇌zrightleftharpoons 用 ϕ2phi_2 重新预测标签
- belief propagation:在边上传递节点对邻居的标签概率的置信度(belief)的message/estimate,迭代计算边上的message,最终得到节点的belief。有环时可能出现问题。
1. Message Passing and Node Classification
- 本章重要问题:给定网络中部分节点的标签,如何用它们来分配整个网络中节点的标签?(举例:已知网络中有一些诈骗网页,有一些可信网页,如何找到其他诈骗和可信的网页节点?)
训练数据中一部分有标签,剩下的没标签,这种就是半监督学习D Easley, Kleinberg J . Networks, Crowds, and Markets[M]. Cambridge University Press, 2010. - influence:社交链接会影响个人行为。
举例:用户将喜欢的音乐推荐给朋友。
如图举例,我们希望根据已知的绿色(label 1)和红色(label 0)节点来预测灰色(标签未知)节点的标签。将各节点从 1-9 标注上node-id。
![图神经网络学习笔记(七)Message Passing and Node Classification](https://cos.aicmty.com/wp-content/uploads/2023/11/cs224wtjrxx2021djkcxxbj6messagepassingandnodeclassification_48389.jpg)
我们已知相似节点会在网络中更加靠近,或者直接相连。
因此根据关联推定guilt-by-association:如果我与具有标签X的节点相连,那么我也很可能具有标签X(基于马尔科夫假设cs224w 图神经网络 学习笔记(七)Message Passing and Node Classification 信息传播与节点分类_喵木木的博客-CSDN博客 这篇是19年秋版cs224w的笔记
Footnotes
-
显然这是个非常简单粗暴的不严格定义。
我没有详细了解过半监督学习,谷歌了一下感觉如果有需可以参考一下这篇知乎文章:半监督深度学习小结 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… ↩ -
没说为啥迭代次数不能太多,我也不知道为啥 ↩
-
对于这些东西是怎么来的,是来干啥的,还有底下那个Loopy BP的迭代公式,具体是怎么回事,我还没搞懂…… ↩