图传播算法(下)

技术专栏

作者:刘忠雨

编辑整理:萝卜兔

上周发布的

《图传播算法(上)》

中讲了关于图传播算法的基本范式和PageRank算法,本文将延续上周的文章,继续讲解剩下的三个算法。

2· HITS

HITS(Hyperlink - Induced Topic Search)另一个典型的图传播算法,其所解决的问题与PageRank算法一样,在一个给定的由网页构成的有向图中,返回高质量的排名结果。与PageRank直接建模重要性排名指标不同的是,HITS更细致的建模了两个衡量指标,包括Authority值和hub值。

Authority:可理解为权威页面,一般包含高质量内容。

hub:可理解为导航页面,指向很多Authority页面。

其经验假设为

被越多的hub页面所指向的页面,内容质量越高。

一个hub页面会尽可能地指向更高质量的内容页面。

很显然,其更新函数可量化为:

虽然HITS算法为每个页面都计算了两个指标,但是最后返回给用户的只是那些Authority值很高的页面。这样看来,HITS的思路只是在迭代过程中,利用hub值这一合理的中间指标来指导Authority值的精确计算,这种思考方式可以很快在后面算法中再次看到。

另外,在迭代过程中,为了保证算法的收敛性,HITS会对Authority值与hub值分别作为均方根归一化。

3·Weisfeiler-Lehman

Weisfeiler-Lehman算法通常被用在解决图的相似性问题上,虽然算法要解决的问题聚焦在Graph层面上,但是其立足点还是在节点上,如果我们能够找到一种衡量节点独立性(unique)的方法,那么我们就可以将图视作一个包含这些独立性节点的集合,两张图的相似性可以转化为两个集合的Jaccard相似度。

何谓节点独立性?其实在前面《浅析图卷积神经网络》中,我们谈到图中的一个节点同时具有attribute和structure的信息,需要同时从这两方面来对节点作Identifaction。很自然地,structure信息还是通过节点的邻居来刻画,Identifaction可以通过hashing来高效判断。如果设Φ(vi)表示节点vi的特征信息(attribute),那么更新函数可量化为:

其中,h是一个哈希函数,理想的性质是满足仅有相同的输入才有相同的输出,这里相当于对每个节点都计算了一个指纹(fingerprint),算法里需要不断地迭代更新上式,直到独立性节点个数不再上升,但实际为了计算效率与效果的综合考虑迭代2~3轮就可以了。

下面举例说明Wisfeiler-Lehman算法

给定两图G和G',其中每个节点都已经打上了标签(实际应用中,有些时候我们并拿不到节点的标签,这时可以对节点都标上“1”这个标签)

要比较G和G'的相似性,我们来看看weisfeiler-lehman算法是怎么做的:

1、aggregate邻居节点的标签得到一个标签的字符串,对字符串进行升序排列。

2、对字符串进行哈希处理,这里生成了一个一一映射的字典,这一步也可以使用其它的字符串哈希函数,只要保证碰撞率尽量小就可以。

3. 将哈希过的值重新赋值给相应的节点

这样第一轮迭代之后,G=,G'=于是利用Jaccard公式就可以计算出G和G`的相似度了,如果需要更严格的对比,可以持续迭代上述过程。

4· RVE2

由于笔者所属行业的关系,所以这里选了一个解决恶意评分场景下问题的算法,文章发表在WSDM2018会议上,名为《RVE2:Fraudulent User Prediction in Rating Platforms》。RVE2也是一个非常典型的图传播算法,其更新公式虽然看上去比较复杂,但是整个思路还是十分符合一般范式的。

首先,我们来把背景问题定义下,给定一个有向的,带有权重的二部图Bipartite Graph G=(U,R,P)。其中,U代表用户集合,P代表商品集合,R表示所有边的集合,边(μ,p)表示用户μ对商品p的一次评分操作,设评分为score(μ,p),score(μ,p)∈[-1,1]。

我们的问题是找到是哪些恶意的用户在进行虚假评分,这里算法分别对用户、商品、评分设计了衡量指标:

User-fairness(用户-公平度),公正的用户会依据商品的质量作出如实的评价,越多的公正用户对商品进行评价,我们就能够确定商品的真实质量指标,F(u) ∈ [0, 1], 1 表示100%公正的用户。

Products-goodness(商品-质量),商品的质量是对商品价值的真实衡量。G(p)∈[-1,+1],“+1”表明商品具有很高的质量,“-1”表明商品比较劣质。

Rating-reliability(评分-可靠度),可靠度指标R(μ,p)∈[0,1],可靠度为0说明用户对商品的评分不可靠,反之则可靠。

刻画了上述三个指标之后,可以总结出下面5条经验假设

质量好的商品得到更高的评分

质量好的商品得到更多可靠的正面评分

可靠的评分在数值上更接近商品的质量

4. 可靠的评分来自公正用户

5. 给出越可靠评分的用户公正度越高

可以发现算法以可靠度为逻辑枢纽去衡量另外两个指标,这与HITS算法里面以hub值去指导Authority值的计算是相通的,只是这里的衡量指标更多,逻辑关系更复杂。

基于上面的5条经验假设,作者设计了下面三个更新公式:

可以看到,上述更新公式会趋向于忽略低可靠度的评分,而加大高可靠度评分的权重。也可证明,更新公式全部符合上述五条经验假设。

作者在论文后面详细阐述了初始化,融合先验异常信息以及怎么在RVE2上面做监督学习的思路,实验部分的效果也十分理想,有兴趣可以去看看原轮文。

总结

这一章我们通过4个算法介绍了图传播算法的一般范式,其核心就在于:

老实说,这样一种解决问题的方法存在很大的门槛,需要系统逻辑式地去思考并量化思维过程,这种能力唯有来源于大量的学习和思考锻炼。当然,如果比较走运,研究的数据有大量的标记集,我们也可以让图卷积等基于 learning 的方法去进行监督学习,让模型自动化地学习出数据内在的规律模式。

参考链接:

http://www.jmlr.org/papers/volume12/shervashidze11a/shervashidze11a.pdf

https://cs.stanford.edu/~srijan/rev2/

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180705A08E6K00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励