做公众号模板的网站,钟楼做网站,网站没有ftp 怎么推广,简单学校网站模板免费下载Message passing and node classification本文主要解决的问题#xff1a;给定一个网络#xff0c; 其中部分节点有label#xff0c; 如何能将其他的节点分配对应的节点label呢#xff1f; #xff08;在生活中有很多这样的例子#xff0c; 比如通过交互行为来判断用户是否…Message passing and node classification本文主要解决的问题给定一个网络 其中部分节点有label 如何能将其他的节点分配对应的节点label呢 在生活中有很多这样的例子 比如通过交互行为来判断用户是否是薅羊毛党直觉上来说会考虑网络节点间彼此的连接关系 本文中会学习的模型是collective classification这其中会涉及到三类具体的方法Relational classificationIterative classificationBelief propagationRelational classificationCorrelations Exists In Network网络中的节点的行为是corrlated 具体表现为三种Homophily有相同性质的节点可能有更多的网络联系如有相同音乐爱好的人更容易在相同的论坛版块Influence一个节点的特征可能会受其他节点的影响如假如我向我的朋友推荐我感兴趣的音乐专辑 朋友中的一些很有可能变成和我一样对这些音乐专辑感兴趣的人Confounding环境能够对节点的特征和节点间的联系产生影响Classification with network dataMotivation相似的节点通常在网络中彼此相连或连接比较紧密 而”Guilt-by-association“关联推定就是考虑这部分信息来对网络中节点类型进行推断 所以网络中节点类型的判断主要通过以下三个来源的特征本身节点的特征节点相连邻居的label节点相连邻居的特征Guilt-by-associationGuilt-by-association的问题比较好定义如下图给定Graph以及少量有label的节点如何将剩余的节点标注为对应label要求网络有同质性 对该问题进行数学建模给定邻接矩阵W大小为n*n, 以及Y为节点对应label1为positive节点-1位negative节点 0位unlabeled节点预测unlabeled的节点中postive的概率。 这里做马尔科夫假设节点的label类型仅取决于相连节点的label类型Collective classification 通常包括三个步骤local classifier仅考虑节点特征信息进行分类Relational Classifier考虑节点邻居的特征和类别信息collective inference将Relational Classifier应用到每一个节点上直到整个网络的”inconsistency“最小化Probabilistic Relational ClassifierProbabilistic Relational Classifier 基本思路简单将每个节点类别的概率是其相邻节点的加权平均具体过程如下对于有标签的数据将节点的类表标注为label对于没有标签的数据将其类随机初始化然后按照随机顺序进行邻接节点类别加权直到整个网络收敛或者达到最大迭代次数其中 是指节点i与节点j的连接权重。这个模型存在两个问题不能保证模型一定收敛该模型并没有使用到节点的特征信息 如上图对初始化后的节点 按label邻接节点来进行加权计算得到节点类型概率直到收敛经过5轮迭代之后 Iterative ClassifierIterative Classifier即加上节点特征后的迭代过程主要包括两个过程Bootstrap Phase将节点i用其特征表示使用local classifier 去计算每个节点的label概率Iteration Phase重复针对网络中每个节点更新节点特征以及按local classifier对该节点进行分类直到label稳定视频教程中举了一个使用Iterative Classifier通过考虑网络结构信息来做fake review detection的 建议大家可以详细看看论文 REV2_Fraudulent_User_Prediction_in_Rating_PlatformsCollective ClassificationBelief Propagation是一个动态规划过程 通过节点间passing message的手段 主要用于解决图当中条件概率的问题。Message Passing举个例子来解释message passing的过程给定任务统计图当中所有节点的数量 其中每个节点只能与它的邻居节点来交互 如上图每一个节点会监听来自于它邻居的信息然后更新信息并将其向前传递, 如下图标红圈的节点仅能接受到incoming messages2 nodes before you;3 nodes behind you 在稍微更复杂的tree型的graph来展示 Loopy Belief Propagation为了讲清楚 这里做一个基础的定义Label-Label potential matrix 表示节点i是类别 的条件下其邻接节点 j 为类别 的概率;prior belief 表示节点i为类别 的先验概率 :节点i预测其邻接节点j为状态 上面其实很好理解该公式考虑节点i为 的先验概率ψ,且根据类似于状态转移矩阵来得到节点j为 同时考虑所有邻居节点传递的信息 , 随机顺序迭代直到最终状态稳定 得到节点i为类别Y_{i}Yi的概率 考虑到节点在做message passing时其实没办法判断是否有cycle 所以LBP在遇到cycles时会粗在一些问题如下图这里稍稍有一些不明白如果有理解的欢迎评论区讨论 LBP的优缺点如下优点实现简单极易并行化普适性强适用所有图模型挑战无法保证收敛尤其是在用很多闭合的连接势函数需要魔性训练训练学习是基于梯度优化的方法在训练过程中可能存在手链问题Summary本文基于cs224w学习整理而来在本文中主要介绍了在node classification经典的三类处理方法Relational classification、Iterative Classifier、Collective Classification 介绍了经典的解决方案如Probabilistic Relational Classifier、Message Passing 文章中有若干案例因为时间问题未整理需要详细了解的建议学习本章教程以及相关paper node classification是经典的graph的问题在很多反欺诈案例中有应用。
