图传播算法（下）

技术专栏

作者：刘忠雨

编辑整理：萝卜兔

上周发布的

《图传播算法（上）》

中讲了关于图传播算法的基本范式和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/