本章主要内容：
我们的任务是：已知图中一部分节点的标签，用图中节点之间的关系来将标签分配到所有节点上。属于半监督学习任务。
本节课我们学习message passing方法来完成这一任务。对某一节点的标签进行预测，需要其本身特征、邻居的标签和特征。
message passing的假设是图中相似的节点之间会存在链接，也就是相邻节点有标签相同的倾向。这种现象可以用homophily（相似节点倾向于聚集）、influence（关系会影响节点行为）、confounding（环境影响行为和关系）来解释。
collective classification给所有节点同时预测标签的概率分布，基于马尔科夫假设（某一点标签仅取决于其邻居的标签）。
local classifier（用节点特征预测标签）→ relational classifier（用邻居标签 和/或 特征，预测节点标签）→ collective inference（持续迭代）
本节课讲如下三种collective classification的实现技术：
1. Message Passing and Node Classification
- 本章重要问题：给定网络中部分节点的标签，如何用它们来分配整个网络中节点的标签？（举例：已知网络中有一些诈骗网页，有一些可信网页，如何找到其他诈骗和可信的网页节点？）
训练数据中一部分有标签，剩下的没标签，这种就是半监督学习
对这个问题的一种解决方式：node embeddings
- 本章我们介绍一个解决上述问题的方法3：message passing
使用message passing基于“网络中存在关系correlations”这一直觉，亦即相似节点间存在链接。
message passing是通过链接传递节点的信息，感觉上会比较类似于 PageRank4 将节点的vote通过链接传递到下一节点，但是在这里我们更新的不再是重要性的分数，而是对节点标签预测的概率。
核心概念 collective classification：同时将标签分配到网络中的所有节点上。
本章将讲述三种实现技术：
- relational classification
- iterative classification
- belief propagation
- 举例：节点分类
半监督学习问题：给出一部分节点的标签（如图中给出了一部分红色节点、一部分绿色节点的标签），预测其他节点的标签
- 网络中存在关系correlations：
相似的行为在网络中会互相关联。
correlation：相近的节点会具有相同标签
- 导致correlation的两种解释5：
homophily（同质性，趋同性，同类相吸原则）：个体特征影响社交连接
influence：社交连接影响个体特征
- homophily：相似节点会倾向于交流、关联（物以类聚，人以群分）
在网络研究中得到了大量观察
举例：同领域的研究者更容易建立联系，因为他们参加相同的会议、学术演讲……等活动Birds of a feather flock together 是句俗语
- homophily举例：一个在线社交网络，以人为节点，友谊为边，通过人们的兴趣将节点分为多类（用颜色区分）。
从图中可以看出，各种颜色都分别聚在一起，亦即有相同兴趣（同色）的人们更有聚集在一起的倾向。
图片出处书籍PDF版下载地址：D Easley, Kleinberg J . Networks, Crowds, and Markets[M]. Cambridge University Press, 2010.
- influence：社交链接会影响个人行为。
举例：用户将喜欢的音乐推荐给朋友。
- 既然知道了网络中关系的影响机制，我们就希望能够通过网络中的链接关系来辅助预测节点标签。
如图举例，我们希望根据已知的绿色（label 1）和红色（label 0）节点来预测灰色（标签未知）节点的标签。将各节点从 1-9 标注上node-id。
- 解决分类问题的逻辑：
我们已知相似节点会在网络中更加靠近，或者直接相连。
因此根据关联推定guilt-by-association：如果我与具有标签X的节点相连，那么我也很可能具有标签X（基于马尔科夫假设6）
举例：互联网中的恶意/善意网页：恶意网页往往会互相关联，以增加曝光，使其看起来更可靠，并在搜索引擎中提高排名。
预测节点 v vv 的标签需要：
- v的特征
- v邻居的标签
- v邻居的特征
- 半监督学习
- 任务：假设网络中存在homophily，根据一部分已知标签（红/绿）的节点预测剩余节点的标签
- 示例任务：
- 解决方法：collective classification
- 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
- collective classification概述
collective classification分成三步：
- local classifier：分配节点的初始标签（基于节点特征建立标准分类，不使用网络结构信息）
- relational classifier：捕获关系（基于邻居节点的标签 和/或 特征，建立预测节点标签的分类器模型）（应用了网络结构信息）
- collective inference：传播关系（在每个节点上迭代relational classifier，直至邻居间标签的不一致最小化。网络结构影响最终预测结果）
- 对本章后文内容的概述
2. Relational Classification / Probabilistic Relational Classifier
问题：
- 不一定能收敛
- 模型无法使用节点特征信息
- 举例
- 第一轮迭代
- 更新节点3
- 更新节点4
- 更新节点5
- 更新完所有无标签节点
- 第二轮迭代：结束后发现节点9收敛
- 第三轮迭代：结束后发现节点8收敛
- 第四轮迭代
- 收敛后：预测概率>0.5的节点为1，<0.5的为0
3. Iterative Classification
- relational classifiers没有使用节点特征信息，所以我们使用新方法iterative classification。
- iterative classifier的结构
- 计算举例：网页分类问题
节点是网页，链接是超链接，链接有向。节点特征简化设置为2维二元向量。预测网页主题。
可以假设分类器以特征第一个元素作为分类标准，于是对中间节点分类错误。
- 过程举例
- 第二步：在测试集上预测标签
- 迭代直至收敛
- 结束迭代（收敛或达到最大迭代次数），得到最终预测结果
- 对relational classification和iterative classification的总结
4. Loopy Belief Propagation
名字叫loopy是因为loopy BP方法会应用在有很多环的情况下。
- belief propagation是一种动态规划方法，用于回答图中的概率问题（比如节点属于某类的概率）。
邻居节点之间迭代传递信息pass message（如传递相信对方属于某一类的概率），直至达成共识（大家都这么相信），计算最终置信度（也有翻译为信念的）belief。
参考6：问题中节点的状态并不取决于节点本身的belief，而取决于邻居节点的belief。
- message passing
- 例子介绍：
任务：计算图中的节点数（注意，如果图中有环会出现问题，后文会讲有环的情况。在这里不考虑）
限制：每个节点只能与邻居交互（传递信息）
举例：path graph（节点排成一条线）
- 算法
- 定义节点顺序（生成一条路径）
- 基于节点顺序生成边方向，从而决定message passing的顺序
- 按节点顺序，计算其对下一节点的信息（至今数到的节点数），将该信息传递到下一节点
- 每个节点接收邻居信息，更新信息，传递信息
- 将path graph的情况泛化到树上：从叶子节点到根节点传递信息
在树结构上更新置信度：
- Loopy BP Algorithm
从 i ii 传递给 j jj 的信息，取决于 i ii 从邻居处接收的信息。每个邻居给 i ii 对其状态的置信度的信息。
- notation
- Loopy BP Algorithm
- 示例
- 现在我们考虑图中有环的情况，节点没有顺序了。我们采用上述算法，从随机节点开始，沿边更新邻居节点。
- 由于图中有环，来自各子图的信息就不独立了。信息会在圈子里加强（就像PageRank里的spider trap）
- 可能出现的问题：置信度不收敛（如图，信息在环里被加强了）
但是由于现实世界的真实复杂图会更像树，就算有环也会有弱连接，所以还是能用Loopy BPheuristic启发式的
- 置信度传播方法的特点
- 优点
易于编程及同步运算
可泛化到任何形式potentials（如高阶）的图模型上
- 挑战：不一定能收敛（参考6：尤其在闭环多的情况下）（所以会选择少跑几轮……为啥啊？）
- potential functions (parameters) (label-label potential matrix) 需要训练来估计
5. 本章总结
- 学习了如何利用图中的关系来对节点做预测
- 主要技术：
- relational classification
- iterative classification
- loopy belief propagation
