图预处理的目的：
- 提高计算速度
- 图规模太大，内存资源受限
图预处理方法：
软件层面：
图存储方法
边集数组（点少的稀疏图）
CSR：压缩稀疏行 和 CSC：压缩稀疏列（压缩稀疏矩阵）Accelerating SpMM Kernel with Cache-First Edge Sampling for Graph Neural Networks.
邻接立方体 Cambricon-Ｇ（挖掘图的局部性，有效提升数据重用率，降低片外访存带宽需求）
- 图采样 综述 Sampling methods for efficient training of graph convolutional networks: A survey
- 点采样
- 边采样
- 图分割
- 对于服从幂律分布power-law的图数据，某些结点的边可能特别多，如果执行点分割会造成大量边的缺失以及边的负载不均匀；而边分割可以处理这类问题。 Graph edge partitioning via neighborhood heuristic.
- 点分割：将图划分为几个包含差不多相等的顶点个数的部分，并且这些部分之间的边数目尽可能地小。
- METIS 多层级分割，大规模图效率低，幂律分布图效果不好。
- Random Hash Pregel 将结点通过一个给定的哈希函数映射到不同的分割子图中，高效但是随机化，造成划分后子图内结点点的局部性很难得到维持，被切掉的边会非常多。
- Linear Deterministic Greedy partitioning (LDG) 在分割的时候将邻居结点放置在一起，以减少edge-cut。它采用贪心算法将一个结点放置在包含其邻居最多的子图中，同时保证每个子图的结点负载均衡。Streaming graph partitioning for large distributed graphs.
- Fennel 相对于LDG对子图中结点数量要求进行了松弛。
- GAP（Generalizable Approximate Partitioning） 基于图神经网络的点分割算法.
- p-way PowerGraph（证明切点法比切边法能提高一个数量级的图计算性能）
- 边分割
- NE（neighbor expansion） 对于一个节点，期望他的所有邻居边都被分配到一个子图中。需要总览全局，提前计算每个结点的邻居集合，对于每次分配边都要动态改变核心集和候选集，以及边集。对于大图来说内存消耗大。 Graph edge partitioning via neighborhood heuristic.
- Degree Based Hashing (DBH) 通过判断结点的度信息来切分结点分配边。融合了度信息和随机哈希的特征，高效且保持了局部性。 Distributed power-law graph computing: Theoretical and empirical analysis.
- HDRF 观察所有子图的信息将边分配到其度最大的结点所在子图上。
- 混合图分割
- hybrid-cut PowerLyra（出入度高的顶点采用切点法反之出入度低的顶点采用切边法）
- 热数据缓存策略
- 由于实际场景中图大部分符合幂律分布，使得一些hub节点被频繁的采样到，那这部分节点的特征就会被频繁的访问到。对于这部分节点以及其1-hop的neighbor以及其特征，AliGraph选择静态的缓存在所有机器节点上。
- 消除图的稀疏性
- 消除图中的冗余边 GraphACT
- 基于窗口滑动收缩的稀疏性消除机制 HyGCN
- 硬件层面：
- 图数据结构重组：
- 在表示图结构的传统邻接列表基础上,对图数据进行向量化和对齐处理，实现更加高效的数据片外访存。 FPGAN
- 图数据重排序：
- 在数据分割的基础上,通过将邻居节点进行分组和序号重排,使得邻居节点能够分布在同一个分块中,提升图数据的局部性及片上数据的重用率。Stochastic training of graph convolutional networks with variance reduction.
- 根据当前工作子图的顶点出度，对顶点进行排序，并按照顶点出度从小到大的顺序依次将顶点数据缓存入 GPU 内存中，直至完全缓存或达到分配的缓存空间上限，提高重用率。PaGraph
- 图数据结构重组：
若有收获，就点个赞吧
0 人点赞
