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

0.2 图关键技术0.2.1 图数据的组织由于实际图的稀疏性，图计算系统通常使用稀疏矩阵的存储方法来表示图数据，其中最常用的两种是CSR（Compressed Sparse Row）和CSC（Compressed Sparse Column），分别按行（列）存储每行（列）非零元所在列（行），每一行则（列）对应了一个顶点的出边（入边）。
0.2.2图数据的划分将一个大图划分为若干较小的子图，是很多图计算系统都会使用的扩展处理规模的方法；此外，图划分还能增强数据的局部性，从而降低访存的随机性，提升系统效率。对于分布式图计算系统而言，图划分有两个目标：

每个子图的规模尽可能相近，获得较为均衡的负载。
不同子图之间的依赖（例如跨子图的边）尽可能少，降低机器间的通信开销。

图划分有按照顶点划分和按照边划分两种方式，它们各有优劣：

顶点划分将每个顶点邻接的边都放在一台机器上，因此计算的局部性更好，但是可能由于度数的幂律分布导致负载不均衡。
边划分能够最大程度地改善负载不均衡的问题，但是需要将每个顶点分成若干副本分布于不同机器上，因此会引入额外的同步/空间开销。

所有的类Pregel系统采用的均为顶点划分的方式，而PowerGraph/GraphX采用的是边划分的方式。Gemini采用了基于顶点划分的方法来避免引入过大的分布式开销；但是在计算模式上却借鉴了边划分的思想，将每个顶点的计算分布到多台机器上分别进行，并尽可能让每台机器上的计算量接近，从而消解顶点划分可能导致的负载不均衡问题。
0.2.3顶点程序的调度在以顶点为中心的图计算模型中，每个顶点程序可以并行地予以调度。大部分图计算系统采用基于BSP模型的同步调度方式，将计算过程分为若干超步（每个超步通常对应一轮迭代），每个超步内所有顶点程序独立并行地执行，结束后进行全局同步。顶点程序可能产生发送给其它顶点的消息，而通信过程通常与计算过程分离。
同步调度容易产生的问题是：

一旦发生负载不均衡，那么最慢的计算单元会拖慢整体的进度。
某些算法可能在同步调度模型下不收敛。

为此，部分图计算系统提供了异步调度的选项，让各个顶点程序的执行可以更自由，例如：每个顶点程序可以设定优先级，让优先级高的顶点程序能以更高的频率执行，从而更快地收敛。然而，异步调度在系统设计上引入了更多的复杂度，例如数据一致性的维护，消息的聚合等等，很多情况下的效率并不理想。因此，大多数图计算系统采用的还是同步的调度方式；少数支持异步计算的系统也默认使用同步方式进行调度。
0.2.4 计算与通信模式图计算系统使用的通信模式主要分为两种，推动（Push）和拉?。≒ull）：

推动模式下每个顶点沿着边向邻居顶点传递消息，邻居顶点根据收到的消息更新自身的状态。所有的类Pregel系统采用的几乎都是这种计算和通信模式。
拉取模式通常将顶点分为主副本和镜像副本，通信发生在每个顶点的两类副本之间而非每条边连接的两个顶点之间。GraphLab、PowerGraph、GraphX等采用的均为这种模式。

除了通信的模式有所区别，推动和拉取在计算上也有不同的权衡：

推动模式可能产生数据竞争，需要使用锁或原子操作来保证状态的更新是正确的。
拉取模式尽管没有竞争的问题，但是可能产生额外的数据访问。

Gemini则将两种模式融合起来，根据每一轮迭代参与计算的具体情况，自适应地选择更适合的模式。
0.3 图计算应用0.3.1 网页排序将网页作为顶点，网页之间的超链接作为边，整个互联网可以建模成一个非常巨大的图（十万亿级边）。搜索引擎在返回结果时，除了需要考虑网页内容与关键词的相关程度，还需要考虑网页本身的质量。
PageRank是最早Google用于对网页进行排序的算法，通过将链接看成投票来指示网页的重要程度。PageRank的计算过程并不复杂：在首轮迭代开始前，所有顶点将自己的PageRank值设为1；每轮迭代中，每个顶点向所有邻居贡献自己当前PageRank值除以出边数作为投票，然后将收到的所有来自邻居的投票累加起来作为新的PageRank值；如此往复，直到所有顶点的PageRank值在相邻两轮之间的变化达到某个阈值为止。
0.3.2 社区发现社交网络也是一种典型的图数据：顶点表示人，边表示人际关系；更广义的社交网络可以将与人有关的实体也纳入进来，例如手机、地址、公司等。社区发现是社交网络分析的一个经典应用：将图分成若干社区，每个社区内部的顶点之间具有相比社区外部更紧密的连接关系。社区发现有非常广泛的用途，在金融风控、国家安全、公共卫生等大量场景都有相关的应用。