图计算之PageRank相关算法

(Updated: )
图
pagerank, pregel, 图计算

图计算的框架简单介绍完后, 上手最典型的例子就是 PageRank (网页排名) 的算法运用, 这篇还会介绍它的衍生算法, 包括带权版, 个性化 PageRank, Article Rank等.

0x00. 前言

在接触 PageRank (后简称PR)本身之前, 需要知道学习大部分图算法都需要从两个方面了解:

  • 一是这个算法是什么意思, 有什么作用
  • 另一个是这个算法对应在图论中的数学定义 / 公式

为了方便理解, 我这记录一般侧重前者, 对数学定义/抽象给出参考链接, 感兴趣的同学可以细究. (图论可从 wiki 里简单了解一下), 然后

1. 历史背景

之所以要单独说一下 PR 的历史, 是因为它对 Google/互联网的影响的确太大了, 可以说是 90 年代里程碑式的论文, 虽然许多人包括我在内(之前)并没有读过 PR 原 paper, 但也早已听闻过它的大名. 它和 2003 年左右 Google 丢出的分布式三马车有类似的影响力, 所以不妨简单了解一下~

大家都对 Google 是做搜索引擎出身, 成为了世界上最大的搜索引擎厂商耳熟能详, 但是可能对搜索引擎的发展史了解甚少:

  1. 最早的时候,

The Anatomy of a Large-Scale Hypertextual Web Search Engine, 这是原论文的全名, PageRank 是论文中提到的具体计算方式, 其中 Page 是由作者 Larry Page 的名字提取得来, 正好也可有网页/页面的含义, 所以它可称作佩奇排名 / 网页排名算法.

文章由 Google 的两位创始人联手发表, 主要的目的是为了分析海量的网页并应用在搜索引擎的排名上的问题. PageRank 就是论文提出的一个利用网络的拓扑结构来计算排名的方式, 论文里大部分内容提到了具体搜索引擎系统的设计实现, 并不是本文重点, 就不细提了

要注意的是实际实现的 PR 算法, 大多数是在原文基础上做了改变和改进 (XxxRank) 的, 多少都有些出入 (应用场景同样)

2. PageRank

那么言归正传, PageRank 到底是如何快速对所有网页进行排名打分的呢, 它有两大实现方式: 简单版 VS 完整版, 然后还有许多变形版就暂且不提, 总之理解它的核心原理即可, 具体实现差异不大.

graph TD

subgraph Example 1
b-->a
c-->a
d-->a
end


subgraph Example 2
a2(a)-->b2(b)-->c2(c)-->d2(d)-->a2
end

subgraph Example 3
b1(b)--> a1(a)
b1(b)--> c1(c)
c1(c)--> a1(a)
d1(d)-->a1
d1(d)-->b1
d1(d)-->c1
end

结合上面给的 3 个图例, 先看一下简单版做法: (参考 Wikipedia)

  1. 把所有网页/网站当做一个顶点, 外链/指向其他网站的当成边, 那么就天然构成了一个图.

  2. 每个点(网页)都有一个给定且相同的初始 PR 权重 (一般 0~1之间), 假设初始为 0.25, 下面看几个图例:

    • Eg1: 假设有 4 个网页 a, b, c, d, 如果 b, c, d 有且只有一个边(外链)指向 a, 那么 a 的最终权重为 PR(a) = PR(b) + PR(c) + PR(d) = 0.75, 其他三个点无人指向则为 0.
    • Eg2: 假设 4 个网页是单环指向, 那么每个点的 PR 值都相同为 0.25
    • Eg3: 再看复杂一点的情况, 此时 b, c, d 三点都指向了多个外链, 那么它计算权重的时候就需要除以外链数, 相当于稀释了投票权重, 那么PR(a) = PR(b)/2 + PR(c)/1 + PR(d)/3 = 0.25/2 + 0.25 + 0.25/3 , 其他点同理, d 没有入边为0

  3. 那么通过这几个例子可以很简单的推出一个递推公式: PR(a) = PR(n1)/D(n1) + PR(n2)/D(n2) + …PR(n)/D(n), 这里 D(n) 就是每个点的出边数, 那么当一个点的出边为 0 时, 它的 PR 值算作是 0 , 就会引出大问题

  4. 怎么算呢? 由此引入了一个修正/阻尼系数 d(damping)

  5. 也就是说图中每个点的 PR 值, 是由它所有的入边的权重和来组成, 要注意这里结果要乘以一个修正系数 d (它后面再说), 并且为了

那么简单版的问题是什么呢, 容易出现特殊情况, 比如如果一个站点的外链也是自己, 出现了自指向的边, 按照原本的模型就是自己给自己打分了,

完整版的代表就是引入了一个随机访问者 (random surfer) 的概念, 不再给每个点初始以相同的权重, 而是模拟一个人在浏览器随机的进行网页访问, 具体如下:

那么上述这种引入一个所谓 random surfer 的做法, 其实就是一种典型的随机游走模型, 炼金里的新名词概念挺多, 本质倒是并不复杂, 理解含义就好.

Dangling: 它是 “悬空/悬挂” 的意思, 它是英文单词 dangle 的 ing 形式 (并不是拼音 ~), dangling website 代表没有外链的页面, 也就是图中出度为 0 的点

3. 优缺点

PR 的优点很明显, 实现和理解都很简单, 缺点主要在于新页面的权值通常比旧站点低的多 (参考自 wiki)

PR 是中心性算法里最出名的一个,

PS: Neo4j 有出一本图算法介绍的书, 觉得对入门图计算还是有很大帮助的, 网上不少资料也是从这摘取的, 可直接阅读官方 PDF

0x02. Personal Pagerank

单机实现已经在 hugegraph server 了, 先来看看单机版的实现思路 (注: 这里面没有最小收敛精度)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
public Map<Id, Double> personalRank(Id source, String label,
                                    WithLabel withLabel) {
       // 0. 返回的是一个 ranks 的映射, 存储着推荐的点和对应的权值 (起始点权重为1)
       Map<Id, Double> ranks = newMap();
       ranks.put(source, 1.0);

       Id labelId = this.graph().edgeLabel(label).id();
       Directions dir = this.getStartDirection(source, label);

       // 1. 根据游走的方向, 新增一个游走集合
       Set<Id> outSeeds = newIdSet();
       Set<Id> inSeeds = newIdSet();
       if (dir == Directions.OUT) {
           outSeeds.add(source);
       } else {
           inSeeds.add(source);
       }

       // 2. 根据最大遍历深度, 重复执行权值计算, 并更新最后的 ranks 列表 (完成后就得到了所有推荐点)
       Set<Id> rootAdjacencies = newIdSet();
       for (long i = 0; i < this.maxDepth; i++) {
           Map<Id, Double> newRanks = this.calcNewRanks(outSeeds, inSeeds,
                                                        labelId, ranks);
           ranks = this.compensateRoot(source, newRanks);
           if (i == 0) { // 把自己加入排除列表. 不过为啥在这做? 在循环外似乎更好?
               rootAdjacencies.addAll(ranks.keySet());
           }
       }

       // 3.1 移除起点的一度邻居 (不重复推荐)
       removeAll(ranks, rootAdjacencies);
       // 3.2 移除不符合条件的 label 点
       if (withLabel == WithLabel.SAME_LABEL) {
           removeAll(ranks, dir == Directions.OUT ? inSeeds : outSeeds);
       } else if (withLabel == WithLabel.OTHER_LABEL) {
           removeAll(ranks, dir == Directions.OUT ? outSeeds : inSeeds);
       }
       return ranks;
   }

   // 计算 ppr 的核心, 如何从一个起点开始, 不断的计算
   private Map<Id, Double> calcNewRanks(Set<Id> outSeeds, Set<Id> inSeeds,
                                        Id label, Map<Id, Double> ranks) {
       Map<Id, Double> newRanks = newMap();
       // 定义一个通用的计算函数, 后续方便 in 或 out 的集合复用
       BiFunction<Set<Id>, Directions, Set<Id>> neighborIncrRanks;
       neighborIncrRanks = (seeds, dir) -> {
           Set<Id> tmpSeeds = newIdSet();
           for (Id seed : seeds) {
               Double oldRank = ranks.get(seed);
               // 取出当前集合的邻居(出点), 第一轮取出起点的全部, 第二轮就是 source+1度邻居,
               Iterator<Id> iter = this.adjacentVertices(seed, dir, label,
                                                         this.degree);
               List<Id> neighbors = IteratorUtils.list(iter);

               long degree = neighbors.size();
               if (degree == 0L) { // 孤点, 为何值不是固定的?
                   newRanks.put(seed, oldRank);
                   continue;
               }
               // 
               double incrRank = oldRank * this.alpha / degree;

               // Collect all neighbors increment
               for (Id neighbor : neighbors) {
                   tmpSeeds.add(neighbor);
                   // Assign an initial value when firstly update neighbor rank
                   double rank = newRanks.getOrDefault(neighbor, 0.0);
                   newRanks.put(neighbor, rank + incrRank);
               }
           }
           return tmpSeeds;
       };

       // 这里为啥 inSeeds 是 out 方向? 反了么还是理解没对
       Set<Id> tmpInSeeds = neighborIncrRanks.apply(outSeeds, Directions.OUT);
       Set<Id> tmpOutSeeds = neighborIncrRanks.apply(inSeeds, Directions.IN);

       outSeeds.addAll(tmpOutSeeds);
       inSeeds.addAll(tmpInSeeds);
       return newRanks;
   }

   private Map<Id, Double> compensateRoot(Id root, Map<Id, Double> newRanks) {
       double rank = newRanks.getOrDefault(root, 0.0);
       rank += (1 - this.alpha);
       newRanks.put(root, rank);
       return newRanks;
   }

   private Directions getStartDirection(Id source, String label) {
       // 通过起始顶点和传入的 label 来判断方向, 也就是从 source 相连的边里确认方向
       HugeVertex vertex = (HugeVertex) graph().vertices(source).next();
       VertexLabel vertexLabel = vertex.schemaLabel();
       EdgeLabel edgeLabel = this.graph().edgeLabel(label);
       Id sourceLabel = edgeLabel.sourceLabel();
       Id targetLabel = edgeLabel.targetLabel();

       E.checkArgument(edgeLabel.linkWithLabel(vertexLabel.id()),
                       "The vertex '%s' doesn't link with edge label '%s'",
                       source, label);
       E.checkArgument(!sourceLabel.equals(targetLabel),
                       "The edge label for personal rank must " +
                       "link different vertex labels");
       if (sourceLabel.equals(vertexLabel.id())) {
           return Directions.OUT;
       } else {
           assert targetLabel.equals(vertexLabel.id());
           return Directions.IN;
       }
   }

   private static void removeAll(Map<Id, Double> map, Set<Id> keys) {
       for (Id key : keys) {
           map.remove(key);
       }
   }

0x0n. 其他

随着现在炼金的兴起, 可能不少同学接触到 PR 是从类似“马尔可夫”, “无监督学习”, “随机游走”等术语/概念里衍生听到的, 这里给一些参考, 但是暂不详细介绍了

参考资料:

  1. PageRank - Wikipedia
  2. The Anatomy of a Large-Scale Hypertextual Web Search Engine (PR paper) - Google
  3. Graph Algorithm - Chapter5.5 PageRank - Neo4j - ORelly
  4. neo4j/graph-data-science-pr
  5. Massively Parallel Algorithms for Personalized PageRank - pvldb 14