图计算之PersonalPageRank算法

图
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

4. 引申 PPR

PPR 全名个性化 PageRank, 定义如下:

和 PageRank(PR) 的思路类似, 先从一个点触发, 以某个概率α往下一个出点随机遍历(1-α概率回到自身), 多轮迭代后, 整个图的遍历概率分布会趋于收敛/稳定, 那么此时每个点的概率值就是起始点对它们的感兴趣程度 (推荐优先级)

与 PageRank 最大的区别在于, 为了保证随机遍历过程中访问节点的概率能体现出起点的偏好, 它有 1 - α 的概率会回到自身, PageRank 里是没有这样的设定的, 并且个性化 Rank 只允许从给定点开始遍历 (PageRank 中可随机点开始)

二分图: 这里引入了一个图论里的抽象概念, 简单说就是一个图划分为两个子图, 这两个子图内部的点没有直连的边, 但是两个子图之间的点有直连边.

介绍了基本概念, 下面来正式认识它

0x02. Personal Pagerank

了解了 PageRank 之后, 个性化 PR 就比较好理解了, 它是一个特定条件限制的 PageRank, 我这里举个具体例子方便快速理解 , Personal Rank 算法典型场景是用于推荐应用中，根据某个点现有的出边，推荐具有相近 / 相同关系的其他点， 比如根据某个人的阅读记录 / 习惯，向它推荐其他可能感兴趣的书，或潜在的书友，举例如下:

  1. 假设给定 1 个 Person 点 是 tom, 它喜欢 a,b,c,d,e 5 本书，我们的想给 tom 推荐一些书友，以及一些书，最容易的想法就是看看还有哪些人喜欢过这些书 (共同兴趣)
  2. 那么此时，需要有其它的 Person 点比如 neo, 他喜欢 b,d,f 3 本书，以及 jay, 它喜欢 c,d,e,g 4 本书，lee 它喜欢 a,d,e,f 4 本书
  3. 由于 tom 已经看过的书不需要重复推荐，所以返回结果里应该期望推荐有共同喜好的其他书友看过，但 tom 没看过的书，比如推荐 “f” 和 “g” 书，且优先级 f > g
  4. 此时再计算 tom 的个性化 rank 值，就会返回排序后 TopN 推荐的 书友 + 书 的结果了 (如果只需要推荐的书，选择 OTHER_LABEL 即可)

然后 OLAP 下的实现, 也是以单机+PageRank 作为参考, 先来看看单机版的 PPR 实现思路 (注: 这里面没有最小收敛精度)

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);
       }
   }

OLAP 版详见 stargraph 仓库里的代码, 社区暂时没直接引入. 有需求再说, 其实 PPR 算法从描述可看出一般是不需要用于全图 OLAP 的

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
  6. 个性化推荐召回算法 — Personal Rank - Zhihu