PGL Paddle Graph Learning 关于图计算&图学习的基础知识概览：前置知识点学习 _生活百科

关于图计算&图学习的基础知识概览：前置知识点学习（Paddle Graph Learning (PGL)）欢迎fork本项目原始链接：关于图计算&图学习的基础知识概览：前置知识点学习（Paddle Graph L）https://aistudio.baidu.com/aistudio/projectdetail/4982973?contributionType=1
因为篇幅关系就只放了部分程序在第三章，如有需求可自行fork项目原始链接。
0.1图计算基本概念首先看到百度百科定义：
图计算（Graph Processing）是将数据按照图的方式建模可以获得以往用扁平化的视角很难得到的结果。
图（Graph）是用于表示对象之间关联关系的一种抽象数据结构，使用顶点（Vertex）和边（Edge）进行描述：顶点表示对象，边表示对象之间的关系。可抽象成用图描述的数据即为图数据。图计算，便是以图作为数据模型来表达问题并予以解决的这一过程。以高效解决图计算问题为目标的系统软件称为图计算系统。
大数据时代，数据之间存在关联关系。由于图是表达事物之间复杂关联关系的组织结构，因此现实生活中的诸多应用场景都需要用到图，例如，淘宝用户好友关系图、道路图、电路图、病毒传播网、国家电网、文献网、社交网和知识图谱。
为了从这些数据之间的关联关系中获取有用信息，大量图算法层出不穷。它们通过对大型图数据的迭代处理，获得图数据中隐藏的重要信息。图计算作为下一代人工智能的核心技术，已被广泛应用于医疗、教育、军事、金融等多个领域，并备受各国政府、全球研发机构和巨头公司关注，目前已成为全球科技竞争新的战略制高点。
0.1.1图计算

图可以将各类数据关联起来：将不同来源、不同类型的数据融合到同一个图里进行分析，得到原本独立分析难以发现的结果；
图的表示可以让很多问题处理地更加高效：例如最短路径、连通分量等等，只有用图计算的方式才能予以最高效的解决。然而，图计算具有一些区别于其它类型计算任务的挑战与特点：
随机访问多：图计算围绕图的拓扑结构展开，计算过程会访问边以及关联的两个顶点，但由于实际图数据的稀疏性（通常只有几到几百的平均度数），不可避免地产生了大量随机访问；
计算不规则：实际图数据具有幂律分布的特性，即绝大多数顶点的度数很小，极少部分顶点的度数却很大（例如在线社交网络中明星用户的粉丝），这使得计算任务的划分较为困难，十分容易导致负载不均衡。

0.1.2图计算系统随着图数据规模的不断增长，对图计算能力的要求越来越高，大量专门面向图数据处理的计算系统便是诞生在这样的背景下。
Pregel由Google研发是专用图计算系统的开山之作。Pregel提出了以顶点为中心的编程模型，将图分析过程分析为若干轮计算，每一轮各个顶点独立地执行各自的顶点程序，通过消息传递在顶点之间同步状态。Giraph是Pregel的一个开源实现，Facebook基于Giraph使用200台机器分析万亿边级别的图数据，计算一轮PageRank的用时近4分钟。
GraphLab出自于CMU的实验室，基于共享内存的机制，允许用户使用异步的方式计算以加快某些算法的收敛速度。PowerGraph在GraphLab基础上做了优化，针对实际图数据中顶点度数的幂律分布特性，提出了顶点分割的思想，可以实现更细粒度的数据划分，从而实现更好的负载均衡。其计算模型也被用在后续的图计算系统上，例如GraphX 。
尽管上述的这些图计算系统相比MapReduce、Spark等在性能上已经有了显著的性能提升，但是它们的计算效率依然非常低下，甚至不如精心优化的单线程程序。
Gemini由清华大学计算机系的团队提出，针对已有系统的局限性，提出了以计算为中心的设计理念，通过降低分布式带来的开销并尽可能优化本地计算部分的实现，使得系统能够在具备扩展性的同时不失高效性 [5]。针对图计算的各个特性，Gemini在数据压缩存储、图划分、任务调度、通信模式切换等方面都提出了对应的优化措施，比其他知名图计算系统的最快性能还要快一个数量级。ShenTu沿用并扩展了Gemini的编程和计算模型，能够利用神威·太湖之光整机上千万核的计算资源，高效处理70万亿边的超大规模图数据，入围了2018年戈登·贝尔奖的决赛名单。
除了使用向外扩展的分布式图计算系统来处理规模超出单机内存的图数据，也有一些解决方案通过在单台机器上高效地使用外存来完成大规模图计算任务，其中的代表有GraphChi、X-Stream、FlashGraph、GridGraph、Mosaic等。