图计算学习

矫情吗；* 2022-02-26 19:00 243阅读 0赞

# 图计算学习 #

本文总结自[AMiner《图计算研究报告》][AMiner]

## 概述 ##

### 图计算定义 ###

图（Graph）是一种重要的数据结构，它由节点  V V V（或称为顶点，即个体） ，与边  E E E（即个体之间的联系）构成，我们一般将图表示为  G （ V ， E ） G（V，E） G（V，E） 。图数据的典型例子有网页链接关系、社交网络、商品推荐等。

图计算系统中最基础的数据结构由顶点  V V V（或节点）、边  E E E、权重  D D D 这三因素组成，即 G = ( V ， E ， D ) G=(V，E，D) G=(V，E，D)，其中  V V V 为顶点（vertex）， E E E 为边（edge）， D D D 为权重（data）。

### 图计算的特征 ###

图数据结构很好地表达了数据之间的关联性， 关联性计算是大数据计算的核心——通过获得数据的关联性， 可以从噪音很多的海量数据中抽取有用的信息。 图计算技术解决了传统的计算模式下关联查询的效率低、 成本高的问题，在问题域中对关系进行了完整的刻画，并且具有丰富、高效和敏捷的数据分析能力，其特征有如下三点：

*  基于图抽象的数据模型
    
    图计算系统将图结构化数据表示为属性图，它将用户定义的属性与每个顶点和边缘相关联。属性可以包括元数据（例如，用户简档和时间戳）和程序状态（例如顶点的PageRank或相关的亲和度）。源自社交网络和网络图等自然现象的属性图通常具有高度偏斜的幂律度分布和比顶点更多的边数。
 *  图数据模型并行抽象
    
    图的经典算法中，从PageRank到潜在因子分析算法都是基于相邻顶点和边的属性迭代地变换顶点属性，这种迭代局部变换的常见模式形成了图并行抽象的基础。在图并行抽象中，用户定义的顶点程序同时为每个顶点实现，并通过消息（例如Pregel）或共享状态（例如PowerGraph）与相邻顶点程序交互。每个顶点程序都可以读取和修改其顶点属性，在某些情况下可以读取和修改相邻的顶点属性。
 *  图模型系统优化
    
    对图数据模型进行抽象和对稀疏图模型结构进行限制，使一系列重要的系统得到了优化。比如 GraphLab 的 GAS 模型更偏向共享内存风格，允许用户的自定义函数访问当前顶点的整个邻域，可抽象成 Gather、Apply 和 Scatter 三个阶段。GAS模式的设计主要是为了适应点分割的图存储模式， 从而避免 Pregel 模型对于邻域很多的顶点、 需要处理的消息非常庞大时会发生的假死或崩溃问题。

## 常用技术 ##

### 图算法 ###

*  遍历算法
    
    图的遍历的复杂性主要表现在以下四个方面：
    
    1.  在图结构中，没有一个明显的首结点，图中任意一个顶点都可作为第一个被访问的结点，所以要提供首结点。
    2.  在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点，以访问图中其余的连通分量。
    3.  在图结构中， 可能有回路存在， 那么一个顶点被访问之后， 有可能沿回路又回到该顶点， 在访问之前， 需要判断结点是否已经被访问过。
    4.  在图结构中，一个顶点可以和其它多个顶点相连， 当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。
 *  社区发现（Community Detection）
    
    社区发现算法是用来发现网络中的社区结构，也可以看做是一种聚类算法。 社区发现算法可以用来发现社交网络中三角形的个数（圈子），可以分析出哪些圈子更稳固，关系更紧密，用来衡量社群耦合关系的紧密程度。从一个人的社交圈子里面可以看出，三角形个数越多，说明他的社交关系越稳固、紧密。
 *  PageRank
    
    PageRank源自搜索引擎，用来解决链接分析中网页排名的问题。它是搜索引擎里面非常重要的图算法，可用来对网页做排序。
 *  最短路径
    
    最短路径用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

### 图数据计算模型 ###

图计算模型即针对图数据和图计算特点设计的计算模型，一般应用于图计算系统中。与传统计算模型相比，图计算模型主要针对解决以下问题：

1.  图计算的频繁迭代带来的读写数据等待和通信开销大的问题；
2.  图算法对节点和边的邻居信息的计算依赖问题；
3.  图数据的复杂结构使得图算法难以实现分布不均匀的分块上并行计算的问题。

![屏幕快照 2019-03-27 09.52.38.png][2019-03-27 09.52.38.png]

*  节点中心计算模型
    
    将图算法细粒度划分为每个节点上的计算操作,节点中心模型将频繁迭代的全局计算转换成多次超步运算,且所有节点独立的并行执行计算操作,数据间的依赖关系仅催在于两个相邻超步之间
    
     *  同步节点计算模型
        
        将节点分为活跃和不活跃两种状态,节点接收到消息后进行计算,否则置为不活跃状态
     *  异步节点中心计算模型
        
        计算节点选择性的读取邻居节点的消息并进行计算,根据每个节点可异步读取和更新的关联边和邻居节点的范围又有三种一致性方案.
     *  GAS(gather、apply、scatter)节点计算模型
        
        沿用同步节点中心计算模型中超步的概念,通过划分大都数节点在单个计算节点内实现并行计算
 *  边中心计算模型
    
    将图算法的迭代计算转换为可在边列表上顺序执行,避免了随机读写数据对内存资源的高要求.
 *  路径中心计算模型
    
    将图数据组织为前向边遍历树和后向边遍历树，从而将图计算转换为在树上的迭代计算
 *  子图计算模型
    
    将图算法转换为多个子图上的迭代运算，减少了计算时的通信开销和迭代操作次数

![无标题.png][.png]

### 图计算系统 ###

![1.png][]

*  单机内存图处理系统
    
    Ligra、Galois、GraphMat、Polymer
 *  单机外存图处理系统
    
    GraphChi、X-Stream、VENUS、GridGraph
 *  分布式内存图处理系统
    
    Pregel、Giraph、GraphLab、PowerGraph、GraphX、Gemin
 *  分布式外存图处理系统
    
    Chaos
 *  面向机器学习的分布式图计算系统
    
    TuX 2 ^2 2

### 图计算中的关键技术 ###

*  异构计算平台
 *  通信模型
 *  执行模型
    
     *  同步执行
     *  异步执行
 *  图的划分
 *  负载均衡
 *  容错

### 技术挑战 ###

*  局部性差
 *  数据及图结构驱动的计算
 *  图数据的非结构化特性
 *  高访存/计算比

### 高引论文 ###

*  Pregel: a system for large-scale graph processing
 *  Distributed GraphLab: a framework for machine learning and data mining in the cloud
 *  PowerGraph: distributed graph-parallel computation on natural graphs
 *  GraphLab: A New Framework For Parallel Machine Learning.
 *  GraphChi: large-scale graph computation on just a PC
 *  Graphx: Graph processing in a distributed dataflow framework
 *  X-Stream: edge-centric graph processing using streaming partitions
 *  Ligra: a lightweight graph processing framework for shared memory
 *  PowerLyra: differentiated graph computation and partitioning on skewed graphs
 *  GridGraph: Large-Scale Graph Processing on a Single Machine Using 2-Level Hierarchical Partitioning

[AMiner]: https://www.aminer.cn/research_report/5c75eb54d1ea9ca237c9c204?download=true&pathname=GraphComputing.pdf
[2019-03-27 09.52.38.png]: https://i.loli.net/2019/03/27/5c9ad77e5dfe7.png
[.png]: https://i.loli.net/2019/03/29/5c9de23b875ad.png
[1.png]: https://i.loli.net/2019/03/29/5c9de771a7e63.png