上周发布的《图传播算法（上）》中讲了关于图传播算法的基本范式和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={6、6、8、10、11、13}，G'={6，7，9，10，12，13}于是利用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/
想要学习和探讨图学习相关内容的小伙伴可以关注我们的微信公众号geetest_jy，还可以添加我们的技术助理geetest1024，进入技术交流群和作者以及众多技术小伙伴探讨问题！
