CS224W-图神经网络 笔记6.1：Message Passing and Node Classification - 节点分类方法简介
CS224W-图神经网络 笔记6.1：Message Passing and Node Classification - 节点分类方法简介
本文总结之日CS224W Winter 2021只更新到了第四节，所以下文会参考2021年课程的PPT并结合2019年秋季课程进行总结以求内容完整
课程主页：CS224W: Machine Learning with Graphs
视频链接：【斯坦?！緾S224W：图机器学习( 中英字幕 | 2019秋)
[toc]
引言
如何在给定一个网络上某些节点的标签，为所有其他无标签的节点分配标签？ 这类任务在现实生活中很常见。本节要介绍的协作分类(Collective Classification)是一种解决方案。
协作分类(Collective Classification)
协作分类(Collective Classification)是一种有效的网络数据分类方法,它利用网络数据中节点间的关联关系，结合部分节点标签和属性，推断未知标签的节点的标签。它是一种半监督的节点分类方法。
ps:其实从经验来看，当有标签节点数量足够时，应当优先考虑有监督的节点分类算法。
1 算法思想
1.1 为什么可以利用关联关系，推断节点标签?
因为，网络中蕴含着相关性信息。
网络环境使得个体行为产生关联。具体相关性原因（形式）有三种：
-
homophily：“物以类聚，人以群分”，有相同性质的节点间可能存在更密切的联系.比如：有相同喜好的人，更倾向于产生联系。
-
influence：“近朱者赤，近墨者黑”，一个个体有可能会受其它个体的影响而具有某种性质。如因为朋友的推荐，也会产生相同的喜好
-
confounding：大环境可能会对个体性质和个体间的联系产生影响?？梢钥醋龇乔傲街衷虻钠渌颉?div id="2cccccccc8" class="image-package">
图片
这三种形式，在现实网络的观察中都得到验证。如种族网络：
1.2 如何利用关联关系，推断节点标签?
Guilt-by-association
(我将其直译为 连累法).如果一个节点连接到具有特定标签的另一个节点，则该节点很可能有相同标签。换句话说：相似的节点通常距离很近或者直接相连。
基于这样的假设可以进行如区分恶意网站识别页等任务。因为通常恶意网页往往会相互链接，以提高知名度，使得看起来可信，以提高在搜索引擎中排名。
课上老师说，Guilt-by-association法要求 网络节点有同质性（homophily）。
如何进行节点分类
具体可利用信息有
但是，如果只使用这些信息，而不使用网络结构属性，那么我们只会在这些特征上训练简单的分类器。为了使我们能够进行集体分类，我们还需要考虑网络拓扑结构。这就是我们要介绍的协作分类（Collective Classification）。
2. 协作分类的步骤
需要以下三个组成部分：
-
local classifier：本地分类器
-
Relational Classifier：关系分类器
-
collective inference：协作推断
2.1 协作分类的种类
它有三种代表性的近似推断的方法，都是迭代型算法。分别：
-
关系分类 relational classification
-
迭代分类 iterative classification
-
信念传播 belief propagation
近似推断有个前提假设——马尔可夫假设（Markov Assumption），即节点
的类别
只取决于它的邻接节点
. 用条件概率表示
%3DP(Y_i%7CN_i))
关于条件概率的精确推断和近似推断
从概率图模型角度看，如果我们将每个节点表示为离散的随机变量，其类成员的联合质量函数为
，则节点的边沿分布为所有其他节点上的
的总和。
- 精确推断（exact inferance） 精确推断 需要是节点数的指数级，是一个np-hard的问题。
- 近似推断（approximate inferance） 通过缩小传播范围（例如，仅邻居）和变量的数量，通过聚合来近似解决推断问题。并且大多数情况下可以取得不错的结果。
总结
各类方法的介绍放在下一节，同时结合具体案例，进一步加深理解，敬请期待。
参考文章
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事?！?“怎么了？”我有些...
文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
CS224W-图神经网络 笔记6.2：Message Passing and Node Classificatio...
本文总结之日CS224W Winter 2021只更新到了第四节，所以下文会参考2021年课程的PPT并结合201...
本文总结之日CS224W Winter 2021只更新到了第四节，所以下文会参考2021年课程的PPT并结合201...
Outline Main question today：给定一个部分节点有标签的网络，如何为网络中的剩余节点分配标...
译者按： 祖师爷Hinton 带领的小组经典之作，深度学习开山祖师 Hinton率领的谷歌团队多次夺冠 ，主力成员...
