图算法入门
以下摘自“亿展宏图 第一篇|两张图入门图算法（By 赵扬）2021 年 06 月 18 日”
“凡两个物体接触，必会产生转移现象” ——罗卡定律。
引子
在老牌 TVB 剧《法证先锋》中，法 证部的高 sir（欧阳震华饰）经常说的一句话：“凡两个物体接触，必会产生转移现象”。这就是罗卡定律，指的是：在犯罪现场调查中，行为人（犯罪嫌疑人）必然会带走一些东西，亦会留下一些东西。即现场必会留下微量迹证。而在 eBay 支付风控部门，我们也时时刻刻扮演着侦探的角色，与“不法分子”进行斗智斗勇。图算法(Graph Algorithm)作为侦探的好帮手，可以帮我们通过图深度学习的算法快速定位人与人以及人与物之间的微妙联系，用于抓住企图利用平台而做的不良行为。
本篇将从图算法的介绍、应用和演化过程三个方面带领大家入门图算法。
一、什么是图
根据维基百科的官方定义：图(Graph)用于表示物件与物件之间的关系，是图论的基本研究对象。图是由一些小圆点（称为定点或者节点）和连接这些圆点的直线或者曲线（称为边）组成。从定义中可以看出，图就是点和边的集合，研究图就是对点和边的研究。为了便于大家理解，我们以下面三张图为例：
- 社交图：人为节点，社交关系/方式为边；
- 知识图谱：知识为节点，知识点间的关系/联系为边；
- 化学里面的分子图：原子为节点，键为边。
二、图算法的应用
上大学期间，有些人可能会开始“堕落”、不学无术，对所学专业缺乏兴趣。其中一个很重要的原因就是他们内心没有找到这些课程对他以后工作或者生活的用处。我一直认为，只有知道了这个“物”能为我们“所用”之后，我们才会更有耐心和兴趣去一步一步学习研究。这也是我为什么前两篇要优先介绍图算法应用而不是纯算法公式的原因。图算法在业界的应用有搜索推荐、分类、聚类、异常检测、传染病传播分析等等，我们逐一介绍一下。
1. 搜索推荐
通常的搜索推荐的算法无外乎从海量数据中先通过粗排找到相似的物品，然后通过用户反馈数据（比如点击量等数据）进行有监督的精排进行推荐。如果想要提升效果，肯定需要是引入了更多的对结果准确性有帮助的信息，而图算法的加入就是加入了点和边等等的结构相关的重要信息。
比如在 Pinterest 网站的搜索排序中，他们就引入了基于图的算法，因为用户会自己会建立自己的收藏商品集合，比如所有的洋娃娃在一个收藏夹里面，这样无形中就建立了点和边的信息，每个点就是物品，如果两个物品在一个收藏夹里面，他们之间 就会有连边，更大概率是同一类物品。引入这种结构在某些场景下会大幅度提升算法效果。
普通的搜索会根据图片信息，错误地返回一些纹理颜色类似但并不是同类型的物品，如下图的第一行所示，比如灯具等等。而基于图的算法结果（如下图第二行所示）在某些场景下会明显较好。不少大公司目前在搜索中也都慢慢地开始逐步引入图算法得到的一些特征，进而提升搜索准确性。
此图摘自斯坦福大学图算法课程
2. 分类
如维基百科需要识别文章是否是假的/谎报文章(hoax article)，这就需要分类模型算法。通常解决这类问题的思路是用各种自然语言处理(NLP)的模型，通过文字上的不同进行分类。但是如果仔细看维基百科里文章结构性的分析，你会发现文章的联系图结构其实就是最核心的分类特征。根据维基百科分析师的研究发现，真实的文章会更互相耦合，如下图所示：
此图摘自斯坦福大学图算法课程
根据结构的不同，就可以建立图模型进行分类预测。效果如下：
此图摘自斯坦福大学图算法课程
根据以上数据显示：随机标记(Random)的准确率在 50%，非专业人工标记(Human)的准确率在 66%，而图算法(Network)的准确性可以达到 86%！可见图算法在某些特定的分类应用中的优越性。
3. 聚类
业界有各种各样的图聚类算法，这里就先不赘述了。其中需要注意的是：图聚类算法和普通的 K-means、层次聚类算法、密度聚类算法等各类传统算法的不同点。纯图聚类算法更多考虑的是图的结构，即边的结构，而不是传统聚类算法里面点和点之间的相似性。
4. 异常检测
此图摘自斯坦福大学图算法课程
比如你有一个大的物理计算机集群，你可以通过图算法找到集群中各个机器，也就是各个节点之间的联系，并构造边，这样你就构造出来一张大图。当某些节点发生问题的时候，通过应用图算法便可以检测并定位到集群相关的节点问题。
5. 传染病传播分析
此图摘自斯坦福大学图算法课程
新冠来临之后，每个人的停留轨迹和与他人的联系就天然的形成了图，可以应用 各种图的算法。比如上图就是用户(Usr)和停留的地方(Place)之间的连边图，我们可以轻松找到与潜在危险用户有联系的人。另外，还有一类学术专家在研究传染病的传染速率模型，经典的是 SIR(Susceptible, Infectious, Recovered)模型，会通过统计模型来模拟易感染人群，感染人群和治愈人群之间的关系和相关系数。
此图摘自维基百科
三、图算法的演化
在真正学习某一方向的算法时，不仅仅需要了解当前最流行和高级的的算法细节，更需要的是总结这个领域整个算法体系的历史演化并了解各个主要分支。假如你想到了一个优化创新的方向，但这其实是前人早就研究过并认为已经是行不通的方向，那么这个方向的研究其实是低效研究。理清体系的演化过程就可以很好地避免这种“无用功”。
只有了解了图算法的形成，发展和演化的整个过程，对于图的应用才会有更好的掌控能力。下面是笔者根据个人理解总结的两张图，以便梳理整个图算法的演进过程，如有理解不到位的地方，也希望大家指正，共同加深理解。
首先，第一张图如下图所示：
让我们先换位思考一下，假如说先辈们从来没有研究过任何 图算法，你就是第一个开始研究图算法这个领域的人，你会一上来就研究各种图模型吗？不！你会先加深对于图算法这个领域的理解，做一些统计量，使自己对于这一门学科有更好的掌控力。
这就是第一部分： 测量(Measure)。
学术专家们定义了很多指标来描述一个图结果，比如说图的度分布，即每个点有几个边。比如一个点连有 3 条边，这个点的度就是 3。对于每个点我们可以进行度的分布统计，就形成了度分布的统计量，用来衡量一个图的边的稠密程度等。
有了一些统计量之后，人们开始试图建立一些统计模型，这个时候假设条件就是我们的好帮手，当加入一些假设条件后，问题就会变得简单很多，并可以从理论上抽象出模型来，这就到了第二个阶段： 网络结构模型(Model Network Structure)。人们研究了各种宏观统计模型，比如经典的 random graph 模型和小世界模型。
再之后，宏观的模型研究一番后，人们发现不太容易应用这些模型，因为这些模型有了过多的假设，使得它很难解决实际的业界问题，所以大家又回到微观领域，也就到了第三阶段探索一个图中的子图或者某种模式(Subgraph / pattern Detection)。如下图所示的 ESU 算法等这类算法就很好地帮助我们 ebay 风控团队在海量交易里面找到某种特定的洗钱或者盗号模式。
在宏观微观都研究的差不多后，此时大家对于 图已经有了相对深刻的了解，这个时候就更想研究用图算法来解决更常见的问题，比如对于图里面的人进行归类，并找到其中的共性来界定点和点之间的关系。这就是第四阶段： 探寻共性(Detect Community)。
这一类的算法主要分成没有节点重合的基于模块化进行优化的 louvain 图聚类算法，以及允许有节点重合的 AGM 算法等等。这一块有很多学术研究者都在研究。有兴趣的读者可以查阅相关算法细节，因为篇幅问题，我这里不再赘述了。
以上四个阶段就构成了我所做的第一张图。
有了聚类之后，科学家们自然而然的就会自然延伸到分类的问题。最容易想到的分类方法就是通过周围 信息传递(Message Passing) 的方式来划分，比如我发现了一个高风险用户，那他周围跟他有联系（边）的人的风险度都会相应提高，如果某个人和好几个高风险用户都有联系，那么他大概率也是有风险的。这个假设通常情况下在实际应用数据中就已经有很好的表现了。在图分类算法中就有了 LPA 标签传播算法(label propagation algorithm)这个经典算法。
研究了一段时间这种分类算法之后，大家发现很多之前很好用的算法难以用在图上，因为图和其他已经成熟的算法有很大的区别。”图“的点和边结构在其他现成的好算法很难用上。这个时候，就有一帮聪明人开始思考了，我们能不能把图结构转化成我们熟悉的领域呢？这就是**节点嵌入(Node Embedding)**观念提出的原因。
通过 Random Walk 或者 Node2Vec 等算法，我们就能去掉边的束缚，给每个点一个向量表达。这个向量表达其实是边结构的一种映射和体现。有了每个点的向量表达，我们之前的各种聚类、分类算法就可以直接应用上了。把不熟悉的问题转化成为了我们熟悉的问题，也为后续深度学习的引入打好了基础。
随着深度学习算法的发展，graph 算法迎来了它的里程碑的时刻——**图神经网络(GNN)**算法的提出。GNN 算法可以用深度学习方法来对点进行预测随之而来的还有 GraphSage 和 GAT 等算法，这些算法被应用在各个领域中，针对不同的领域，有意想不到的好效果。
有了分类预测模型之后，借鉴可以用来自动生成文本文字的循环神经网络(RNN)算法，有一波学者开始研究图的生成(Graph Generation)。GraphRNN 就像 RNN 在语音文字生成中的应用一样，可以自动形成 graph，这一类算法在药品的研究中有很多应用。
到此就形成了第五到第八个阶段的演进过程，如下图所示：
以上叙述的 8 个阶段（两张图）基本上概括了图算法的大致发展过程。
任何事务的发展都是有因有果的，以上的发展演进不一定是按照这个时间顺序，但是这是笔者在学术研究逻辑上对于这一块理论方向的梳理，大致可以串起这个领域里面大部分的算法，各个应用都可以映射到这个演进图里，方 便大家对于整个领域算法的掌控。比如，想找子图，就可以用 ESU，想分类或者聚类就可以用到相应的 GAT 或 Louvain 等算法，还可以慢慢积累各种算法细节，并进行效果比对。
总结
图算法是一个非常有趣的领域，图算法的应用也越来越广泛。希望通过本篇文章，大家能对图算法有一个初步的了解，并能在以后的学习和工作中更好地应用图算法。