视频地址，课件和笔记可见官网。
主要解决问题：给定一个网络，部分节点有标签，我们如何预测其它节点的标签。
有一篇论文：Semi-Supervised Classification with Graph Convolutional Networks
例子：反欺诈案例，一些节点是欺诈者，一些节点是合法客户，我们怎么找到其它的欺诈者和合法客户。
补充：
图算法应用的任务有：
1、node focused，以节点为主体，预测节点的标签等，比如上面的反欺诈的例子；
2、edge focused，以边为主体，预测边的标签，比如推荐系统中 用户与商品是否发生关联（即用户是否购买商品），对这种关联关系是否发生进行预测；
3、graph focused，以整个图为主题，预测图的标签等，比如化学分子的类别预测，整个化学分子是一副完整的图，其节点是不同的化学原子；
这节课主要讲节点分类的问题，也是目前图算法应用较多的领域，我们熟悉的gcn就是属于解决node focused任务的gnn的变体结构之一。
很多时候半监督和有监督问题的定义界限模棱两可，这里之所以称之为半监督，主要是因为获取的有标签的节点数量非常稀少，所以希望通过半监督的方法来处理，如果有标签节点的数量非常多，其实用有监督也可以。
因为图的特殊性，所以这里的思路是利用网络的相似性来给所有样本进行打标，使用了红绿蓝下面三种方案。
分别是关系分类、迭代分类、信仰传播，先进程度依次递进，下面从最简单的关系分类讲起。
这里距了一个社交网络的例子来说明为什么网络结构存在相关性。
个体行为在网络环境中是相互关联的；
导致相关性的三种主要原因：
1、同质性：个体的不同特征会导致社交过程中的connection，比如相似的年龄、工作、种族、宗教信仰等会导致相似的一批人发生social connections；
2、影响力：可以看到，人的社交关系social connections反过来还会影响到个体的特征，所谓近朱者赤近墨者黑。
3、其它令人困惑的原因来自于环境environment，前面的两种是已知的能够左右人的社交关系和个人特征的重要原因之二，但是实际上还有其它的原因，这里统一归结为环境因素，例如在暴力的环境成长下的儿童成年后可能个人心里会有一定的扭曲，这同样会很重要的影响到他的社交行为和个体特征的形成。
不过大部分时候，前两者足够产生较为强大的网络相关性了，毕竟大部分人不会受到极端的环境的影响。。。
关于同质性和影响力的一些案例（讲了一些关于这类研究很成熟很全面之类的，感觉没什么价值，就不写了）
facebook的社交网络图，注释入原图，很有意思的一张图。
那么我们如何利用这种相关性来预测无标签的节点，上图中米色的节点为无标签的；
如何确定标签，一个naive的思路就是——一丘之貉，你和label X的人相关联则你也可能是label为X的人。下面举了一个例子：在搜索引擎中，有一些恶意网站会大量互相关联从而提高自己在搜索引擎中的排名（早期google的搜索引擎是根据网页的链接数量来排名的貌似，《数学之美》里面有提到过感兴趣的可以看看），后来，pagerank的出现很好的改善了这些问题。
未知样本的标签取决于：
1、这个未知样本O的特征；
2、这个未知样本O的相邻节点；
3、这个未知样本O的相邻节点的特征；
实际上如果仅仅考虑第一个条件就回到了我们传统的机器学习算法的范畴里了；
假设我们存在上面的一个巨大的网络数据，我们用n*n的W（邻接矩阵：使用二维矩阵表示这个网络图，常见的图数据的表示形式之一），假设标签为1，-1，0，分别表示正节点，负节点和无标签节点，我们首先的目标是预测哪些无标签节点可能是正节点；
利用相似性来进行分类的应用包括上述的这些。
马尔可夫假设，节点的标签取决于其邻节点的标签，实施 collective classification（翻译过来叫 集体分类。。）
具体分为三个步骤：
1、有标签样本训练分类器然后对无标签样本进行估计得到伪标签；
2、获取不同节点之间的相关性；
3、通过网络传播这些相关性；
4、不断迭代，直到收敛
首先是local classifier，就是一个标准的机器学习分类问题，不使用到网络的信息，仅仅是基于节点的特征进行分类的，说白了就是一个节点代表一个样本，这个节点的属性就是样本的特征列，然后我们可以使用lr、gbdt之类的算法来求解这个二分类问题。
（这里学生问了一个大部分初学者都会问的问题，貌似我们通过第一步就可以得到一个分类器用于预测无标签的节点，实际上如果节点的特征能够提供足够好的模型来进行预测，我们确实不太需要再深入了，问题是很多时候仅仅使用节点特征训练的模型效果一般甚至比较差，这个时候就要考虑到使用网络信息来对原始特征进行有力的补充或代替。）
然后训练一个relational classifier，使用样本的邻节点的标签和（或）特征来预测这个样本的标签，因为上一步生成了伪标签了所以此时所有节点都有标签了；
最后是实施集体学习，使用relational classifier预测每个节点的标签，这样我们会得到一批新的标签，然后再重新训练relational classifier，一直迭代到相邻节点之间的不一致性最小化（这里后面讲述的实际上是 预测的概率值不在发生变动或者变动很小的时候或者是到达了指定的迭代次数），网络的结构对于最终训练出来的模型的影响是很大的。
例如你在左图训练出来的概率结果会受到中心点标签的重大影响，而右图相对均匀的图结构则互相之间的影响比较平均；
实际上思路非常类似于半监督中的self-training。
这里谈到了精确推断和近似推断的问题，因为上面的步骤看起来不太靠谱，略随意的样子，为什么不进行精确推断，因为精确推断只能适用于极少的条件下，比如上面的例子，标签太少，不可能实施精确推断，除此之后精确推断对于任意结构的网络是一个np-hard的问题，也就是没有精确的解。因此我们使用近似推断来代替精确推断。
好消息是这种近似推断的做法大部分时候运行良好。
回到之前的问题，给定节点属性（特征）和小部分标签，如何预测无标签样本的标签。
下面开始正式介绍第一种方法，relational classifier
基本假设是，节点的预测概率值是其邻节点的预测概率值的加权平均。
对于有标签样本，使用真实标签进行初始化，对于无标签样本，统一0.5初始化（这里学生问了另一个问题可不可以使用别的初始化方案，答案是可以，如果有先验知识对某些标签的把握更大可以赋予更大的初始概率值，只不过使用0.5初始化比较简单而已）；
**
然后不断随机（不一定使用随机更新的策略，但是记住不同的更新策略会影响最终的结果，再在大型的图上，使用随机更新的策略常常就足够好了）更新所有节点的预测概率值直到收敛（预测概率整体不再变化或者变换很小）或者达到指定的最大迭代次数。
这里课件和视频上的不一样，不过显然课件是正确的，因为如果按照原始视频中公式的分母使用Ni即第i个节点的邻节点的数量之和，则默认权重为1，那么和后面的权重项对不上，自相矛盾。
那么这里的思路就很直接了，随机初始化之后，我们不断使用上面的公式对节点的概率值进行更新，直到收敛为止，其中Wij表示节点i和节点j之间的边的权重，以社交网络为例，如果用户i和j之间的互动频繁则权重就更大。
但是这种方法的问题在于：
1、无法保证一定能收敛（就是可能收敛也可能不收敛）（这里讲课的大佬给了一个经验法则，如果不收敛，但是随着时间的推移，不收敛的程度没有变大而是周期性的变动，那么这个时候我们也可以结束迭代）
2、模型仅仅使用的是节点的标签信息，但是没有用到节点的属性信息（特征）；
下面给了一个很详细的过程：
举例子永远是对于初学者来说最快的理解方式之一，这样一看对整个算法的逻辑就非常清楚了。。。
最终，经过5此迭代，预测的结果不再发生变化了，可以发现，最终的结果非常符合人类的直观认知，左侧都是正样本，因为他们看起来属于一个团体结构，右边属于负样本，他们看起来形成了一个小团体，中间的连接点4则无法判断，概率在0.5左右，从人类的理解上来说也是合理的，处于中间比较尴尬的位置。
接着讲了第二种算法，iterative classification。
第一种方案 relational classifiers 仅仅根据标签进行迭代，完全浪费了节点的属性信息，显然如果节点之间的属性非常相似，那么节点的标签也很可能是一样的，所以iterative classification 的思路就是 同时利用节点的属性（特征矩阵）和标签；
其过程是：
1、为每一个节点创建一个向量形式（这里的意思应该是根据每个节点的属性得到一个特征向量）
2、使用分类器对得到的特征矩阵结合标签进行训练；
3、对于一个标签可能拥有许多的邻居，因此我们可以对其邻居的节点进行各类统计指标的计算加入特征中作为衍生特征，例如count计数、mode 求众数、proportion求占比、均值、是否存在的bool特征等；
这里详细介绍了iterative classifiers的整个过程：
首先是bootstrap phase，先使用特征矩阵来训练一个传统的机器学习模型比如svm、knn，然后预测标签，还是伪标签的思路；
然后是iteration phase，进入迭代步骤，对于每一个节点i都重复：
1、更新特征向量ai；
2、重新训练并且预测得到新的标签yi
一直到预测的概率整体不再变化或者变动不大或是达到了最大迭代次数；
同样，收敛也是无法保证的。
（这里补充了一点使用的知识，就是这类迭代的算法怎么去确定其停止条件，一个就是输出的值的收敛，理想状态是输出基本不发生改变，如果始终不收敛就看输出的差值的波动情况，如果是周期性在某个范围内波动而其差值不随迭代次数继续增大则可以选择输出差值较低的结果作为最终的收敛状态；另一个思路就比较简单了，设定最大迭代次数）
具体的例子可见下：
这是一个信息量非常大也非常符合实际场景也非常好理解的案例，比如这里，如果不考虑网络信息单纯从特征上来看，中间的文章和最右边的文章的特征矩阵完全一样，所以如果使用传统的机器学习算法明显这二者的标签肯定都是判定成同一种的，但是实际上二者的标签是不一样的，这个时候我们就要引入额外的特征来帮助模型去判断二者的不同，此时，网络信息就作为一种非常宝贵的特征参与进来。
如果不考虑不同文档之间的关联，这实际上就是一个普通的文本分类问题，w1、w2、w3.。。表示的是文本（网页）中出现的单词，实际上就是一个词袋模型，这里为了简单，仅仅取了3个单词作为共同的词矩阵，然后用KNN，在不考虑网络信息的情况下训练了一个baseline。这里可以看到，在仅仅考虑节点属性（词矩阵）的情况下，4篇文章有一篇分类错了，把B错分成了A。
这里，我们根据网页之间的网络连接关系，从人类逻辑上就可以大致猜测出中间这篇文章的标签应该大概率是B，因为他和另外两篇标签也是B的文章关联非常密切。
所以，现在我们就把网络中的这种关联关系考虑进来，这里考虑进来的方式也很简单，因为上图是一个有向图，所以这里对于每个节点都生成4个 新的特征，假设某个节点Z。则IA指指向节点Z的标签为A的节点的数量，IB同理；OA指的是节点Z指向的标签为A的节点的数量，OB同理；可以看到，实际上就是一个常规的特征衍生的操作，只不过衍生的特征来自于图结构上的关联关系，即网络相似性。
这课件写的真的太详细，非常好理解；
思路很简单，首先，我们在一个有标签的训练集上先训练一个仅使用节点属性（词矩阵、特征矩阵，下面统一用节点属性的称谓）的模型1，然后模型1输出预测标签，根据预测的标签我们得到了上面训练集的样本节点标签，然后这些节点标签的信息都以特征衍生的方式并入原始的节点属性中，最后我们利用新的节点属性（原始的节点属性和基于网络相似性生成的新特征）重新训练一个模型2。
然后在测试集上，我们使用模型1对测试集的标签进行预测，
得到了伪标签之后根据网络相似性得到新的特征并入节点属性，然后使用模型2进行预测，
然后我们就又进入了神奇的迭代过程了：
我们用模型2预测出新的伪标签，然后重新更新标签，那么这个时候我们基于网络相似性衍生的特征也发生了改变，那么我们就用新的数据重新训练一个新的模型2，然后继续使用模型2预测。。。。。循环往复，直到达到迭代停止条件位置；
可以看到，上述过程中，原始的节点属性是不发生变化的，仅仅是基于网络信息得到的特征在不断的发生变化，原ppt写的有一些模糊，不过看到这里就明白了，我之前还之一以为原始特征矩阵也发生变化呢。。。
经过了反复的迭代之后，最终得到了完全正常的结果。
关于iterative classification的应用：虚假评论者的预测。
其实说的就是类似淘宝上刷好评的问题，星级越高的店铺其收入越高，很多时候我们在淘宝京东上也经常碰到刷好评的商家，商品质量不咋地，星级高的一笔；
传统的方法是从 评论者的行为分析和文本分析入手的，行为分析包括了评论者的个人特征，地理位置，登陆时间，会话历史记录；
文本分析包括了最高级best之类的词语使用的次数，大量的自我引用，拼写错误的比率，大量的褒义词等等；
但是这些都很容易被伪造，尤其是文本方面，如今的自然语言模型已经达到了非常恐怖的程度，能够生成很多以假乱真的评论，即使用肉眼去评估也不一定能够有效的辨别；
但是图结构是难以造假的：评论者、评论和商家之间的关联关系是难以改变的，这类人容易在网络结构上聚集成一个个的小团体结构；
问题定义，整个问题以二部图的形式给出，我们要做的就是预测出哪些用户的评分是虚假的，这实际上属于边预测的任务，左右两边的笑脸都是用户user，中间的图形表示商品product，连接的边表示评分，评分在1和-1之间。
我们现在的目标就是找到虚假评分的用户，然后将这些用户剔除，然后我们才能得到商品最真实的用户评分。
基本思想：用户，产品和评分具有内在的质量得分（也就是客观的真实的得分，不受虚假评分的影响）：
§每个用户都有一个 ‘fairness’的得分介于0~1之间
§每个商品都具有一个‘goodness’的评分介于-1~1之间
§每个评分都有一个‘reliability’评分介于0~1之间
¡所有值都是未知的
¡如何同时计算所有节点和边的值？
¡解决方案：迭代分类 iterative classification
这个公式是什么意思呢？假设有一个用户A对于若干个商品一共发了5条评论，则这5条评论的reliability求和之后除以5进行平均，这就得到了这个用户的fairness的得分；
然后是商品的goodness得分的公式，商品的goodness等于每条edge的可信度reliability乘上用户的评分，最后使用这个商品的评论人数进行平均得到最终的goodness得分公式；
最后是对reliability的更新，分为两个部分：
蓝色部分和用户有关，可以看到就是一个gamma1系数*当前用户的fairness，黄色部分比较有意思，衡量的是当前用户的对商品的评分和上一步计算出来的商品的goodness的接近程度。
然后下面又给了一个非常生动具体的例子，这个课件的教学形式真的太好了，把看起来难得概念通过具体得事例非常生动、易于理解得介绍出来了；
这里gamma1和gamma2统一设置成1，也可以改成其它大小的参数，关键看使用者认为用户的可靠性和商品的得分哪一个决定因素的程度更大了。
这种方法的好处是：
1、收敛得到了保证；
2、收敛的次数被证明是具有上限的，也就是一定会收敛；
3、时间复杂度：相对于edges的数量是线性时间复杂度，因为涉及到的都是简单的计算；
效果居然初期的好。。。。额
计算复杂度还低（讨论中提到了这种方法可以收敛到全局最优。。。额，我都没看到这个问题的损失函数的形式。。。）
最后介绍目前最先进的方法：
信仰传播。。。。？
循环信仰传播，Belief Propagation是一种动态编程方法，用于在图模型中解决条件概率查询的问题（没看明白）
迭代过程中，相邻的节点的变量相互“交谈”，传递消息。（wtf）
当达成共识时，计算出最终的信念。（wtf？）
（这里的意思是，还是使用了近似推断的方法，就是通过不停的迭代，当最终的结果进入稳态之后认为任务目标达成，训练结束，得到最终的结果）
任务：计算图中的节点数*
条件：每个节点只能与其邻居进行交互（传递消息）
这个问题貌似看起来挺弱智，但是实际上是这样得，首先，注意途中得一个there’s 1 of me的节点，假设我们目前处于这个节点之上，并且我们只能和前后的邻节点传递信息，
这个时候，我们需要双向，前后两个节点提供position的信息，然后，如上图所示，我们才能计算出整个连接的长度，否则仅仅凭借单向的信息是无法计算的。
接下来来看一种更加复杂的情况：
这里通过这些事例主要是想说明 belief propagation是如何传播的。
然而，普通的 belief propagation 无法处理存在cyclic（循环）的情况，这也很好理解，比如上图我们在两个节点之间又加入一条连线，这个时候就没法计算全部节点的数量了。
这个时候就要用到“loopy belief propagation”
若有收获，就点个赞吧
0 人点赞
