邻接矩阵 Adjacency Matrix 压缩稀疏矩阵 CSR/CSC 邻接链表 Adjacency List Tree 基于 CSR 的变种 PCSR 和 VCSR PCSR VCSR CSR++ 小结 延伸阅读 图算法中的图操作 AIGC 小课堂 参考文献
插入一个点 插入一个边 删除一个边 删除一个点的全部邻边 找到一个点的全部邻边 找到一个点的另一个邻点 全图扫描 获取一个点的入度或者出度
Match (src)-[friend * 2..4]->(fof)
WHERE src.age > 30
RETURN fof
对于这样一个问题可以直接对应右边的矩阵操作：
其中，n=|V|，m=|E|。
优化上，批量操作（CPU Cache/SSD block）可以线性增加性能，例如 O(n) 可以降低到 O(n/B)，但不影响定量分析。
由于绝大多数图结构是极其稀疏的，因此简单用邻接矩阵来表示图结构，其内存会有夸张的浪费。更为严重的是，当有多种边类型时，每种边类型各需要一个邻接矩阵。这使得裸用矩阵在实际情况中只能处理很小数据量的场景。当然，对于现代服务器动辄几百 G 的内存，如果只有几亿点边的数据量，像是 twitter2010，这并不会是很严重的问题。但大多数情况下，条件允许的话，大家还是希望找到一些更加经济的结构。
压缩稀疏矩阵是一种非常流行和紧凑的图结构表示方式，大多数图计算系统都采用 CSR。
这里简单介绍一下 CSR 的结构：
对于点 IDx，取邻居 ID 就是 F[N[x]] 到 F[N[x+1]-1]。
例如，查找点 ID2 的邻居，对应为 F[N[2]] 到 F[N[2+1]-1]，对应到上图也即 1 6 8。查找点 ID7 的邻居，对应为 F[N[7]] 到 F[N[7+1]-1]，也就是 2 和 4。
另外，CSR 记录的仅是出边的信息，如果要考虑入边就使用 CSC，其原理是类似的。
CSR 的空间占用是 O(|V|+|E|)，在空间节省和顺序查找上是极其高效的。但在大量插入时，压缩稀疏矩阵和邻接矩阵一样，需要重新开辟空间，效率很低。所以，它适合于计算密集场景但不适合增改频繁的场景。
CSR 还有一个显著的优点是可以快速获取每个点的出入度，只要计算 N[x+1]-N[x]，这在判断一些点是否为超级节点时很方便。如果不是稀疏矩阵的话，通常会用另外一个单独的结构来记录出入度。
此外，CSR 不容易实现并发修改，其每次插入都需要对两个矢量进行位移，这并不高效。
这里推荐两个相关的开源项目，可以进一步了解下 CSR 的使用：
https://github.com/DrTimothyAldenDavis/GraphBLAS https://github.com/GraphBLAS/LAGraph
和基于矩阵的方式不同，邻接链表 AL 空间上有优势，但对于边的读写上会略微慢一点（指针在内存中不能连续移动）。AL 的做法是把邻边（出边）用 list 或者有序 list 的方式串连起来。由此延伸的一个变种是邻边从 list 改为 array。
AL 相比 CSR 通常不能直接获得点的出入度，可以通过可以单独维护一个字段实现该功能。
此外，邻接表并不需要 ID 连续排布，对于频繁增删点的场景特别友好。AL 对于并发修改的支持也更友好，天然在点级别有并行度。当然，对于超级节点，直接用 list 的方式，还是会有些性能的问题要考虑；优化上可能会进一步改造成 Blocked list 的方式，可以带来更好的数据局部性和细颗粒度。
由于 ID 不用严格连续排布，AL 的一个常见变种就是 Tree。
在这种结构中，一个点和其所有的邻边被建模成了 key-value，key 是点 ID，value 是所有邻边的编码。Key 通过 Tree 的方式组织在一起。这里的树可以是 B-Tree 等各变种 Tree。虽然本文没有讨论图属性，但 value 中也是可以存放 value。
为了控制访问颗粒度，每个叶子通常会被限定为固定的大小（页）。这就是在数据库类系统里面最常见的办法 B-tree。为了增改方便，也可以把每页的 in-place update 改成 Copy-On-Write 的方式；一个典型的代表就是 LLAMA[2]，但这种多版本的读取通常会需要更多的空间，并且当有大量累积修改时，需要定期的多版本合并以降低跨快照读。某种程度上，它和 LSM-Tree 的思路有些接近。
由于 CSR 在空间和读性能上有很大的优势，但在插入时的耗时和空间上都很弱，因此本节几个变种的主要目的都是为了改善其弱项，大体思路都是分块和 buffer。
在 CSR 的边矢量进行增删时可以注意到，主要耗时是在对于矢量的元素位移上。因此，一个直观的思路是预留一些插入空白位，在删除时也不立刻回收这些空白。
而分块思想，是指将一些局部数据放在同一个分块内，例如 Tree 中每个 page 就是一种分块的方式。与此对应的是，buffer 空白之间的连续区域。
PCSR [3]的基本思想是：对于点矢量，其元素从一个值改为对应边矢量中对应邻边位置的 <起点,终点>。而对于边矢量，在这些分块所对应边界放置哨兵 sentinel，上图中的 S，上图的 “-” 对应预留插入位置留空。
事实上，原文中，对于边矢量，其本质是实现为一个 B-Tree，本文先简化成一个 Array。
可以看到，PCSR 的预留位置多少都是需要重平衡，不能过多也不能不足。特别是大批量增删时，对预留位置的处理会是一个较重的操作。
此外，如果把 PMA 的 B-Tree 以及需要 rebalance 的本质考虑进去，其和前述 Tree 方式的区别并不是很大。
VCSR[4]主要是对 PCSR 的一个改进，其朴素思想是 PCSR 的留空是均匀的，而大多数图结构的出入度，是存在 20-80 这样的幂率特征，而 PCSR 的一个主要痛点是频繁的 rebalance。VCSR 的做法是为每个分块预留空间正比于其分块内的点的数量，即：边矢量中，一个分块内，如果点的数量多，就多预留一些空位。在直觉上，点数量多时，其分块对应的边插入会更多一些，这样可以减少 rebalance 的频率。
事实上，CSR++[5]在设计上其实更接近一种 AL/Tree 的变种，而不是 CSR。它主要有三个方面的优化：
第一，对于 Vertex Array 再分段，将一个大的 Array 拆成多段，这样可以有更细的读写颗粒度。通过 段 ID + 点 ID 来定位每个点和其邻边。第二，Vertex Array 中每个元素，除了记录点 ID 之外，对于邻边数量很少的点，直接把邻居 ID 也对齐地塞 inline 进去。
对于大多数的点，其邻边就不需要单独的 Edge Array 来存储了。
可以看到这种方式在图比较稀疏的时候，对于 CPU Cache 扫描是很友好的。
第三，对于每个点的邻边，采用copy-on-write、标记删除等常见的优化办法，构建成类似 std::vector 结构。
最后，由于在图查询、图存储和图计算不同场景下，对于图结构的读写扫描和生命周期都有些不同的要求，不同的数据结构也有不同的优劣。
当然，本文只是讨论了图结构可以放在内存中的情况。当不得不把部分数据放在硬盘上时，问题就完全不同了。当然本文也没有讨论不同 CPU 对于不同距离内存的性能差异 NUMA，或者跨进程通信带来的影响。
最后，我们来了解下在图计算/图算法上的图操作。
图算法中的图操作
度中心性通过节点的度数，即关联的边数来刻画节点的受欢迎程度，这将会要求找到一个点的所有邻边。 接近中心性，通过计算每个节点到全图其他所有节点的路径和来刻画节点与其他所有节点的关系密切程度，这将会要求进行全图扫描，查找点和图中所有点的路径信息。 介数中心性，则用于衡量一个顶点出现在其他任意两个顶点对之间最短路径上的次数，从而来刻画节点的重要性，这将会要求进行全图扫描，找到一个点和它的邻点及路径信息
倘若是下图这种图结构：
B 链接到 C，D 链接到 B 和 C，A 点的值计算的方式如下：
这里的 2、1、3，分别是 B 点对外链接的 2 条边，C 点对外链接的 1 条边，D 点对外链接的 3 条边。
换句话说，算法将根据每个页面连出总数平分该页面的 PR 值，并将其加到其所指向的页面：
最后，所有这些 PR 值被换算成百分比形式再乘上一个修正系数。
由于“没有向外链接的网页”传递出去的 PR 值会是0，这时候如果递归的话，会导致指向它的页面的 PR 值的计算结果同样为零，所以 PageRank 会赋给每个页面一个最小值。
因此，一个页面的 PR 值直接取决于指向它的的页面。如果在最初给每个网页一个随机且非零的 PR 值，经过重复计算，这些页面的 PR 值会趋向于某个定值，也就是处于收敛的状态，即最终结果。
简单来说，大多数迭代图计算模型都是基于“找到一个点的全部邻边”、“找到一个点的另一个邻点”操作。
在 AIGC 小课堂部分，我们会用 NebulaGraph 接入的 aibot 来讲解下文中的部分概念。你如果对 chatgpt 或者是 aibot 有兴趣，可以来 https://discuss.nebula-graph.com.cn/ 向 aibot 提出你的要求。
Athanassoulis, M., Kester, M. S., Maas, L. M., et al. (2016). Designing Access Methods: The RUM Conjecture. In EDBT (pp. 461-466). Macko, P., Marathe, V. J., Margo, D. W., et al. (2015). Llama: Efficient Graph Analytics Using Large Multiversioned Arrays. In 2015 IEEE 31st International Conference on Data Engineering (pp. 363-374). IEEE. Wheatman, B., & Xu, H. (2018). Packed Compressed Sparse Row: A Dynamic Graph Representation. In 2018 IEEE High Performance Extreme Computing Conference (HPEC) (pp. 1-7). IEEE. Islam, A. A. R., Dai, D., & Cheng, D. (2022). VCSR: Mutable CSR Graph Format Using Vertex-Centric Packed Memory Array. In 2022 22nd IEEE International Symposium on Cluster, Cloud and Internet Computing (CCGrid) (pp. 71-80). IEEE. Firmli, S., Trigonakis, V., Lozi, J. P., et al. (2020). CSR++: A Fast, Scalable, Update-Friendly Graph Data Structure. In 24th International Conference on Principles of Distributed Systems (OPODIS'20).
点击【阅读原文】即刻畅享 NebulaGraph Desktop，Windows 和 macOS 用户安装图数据库的绿色通道，10s 拉起搞定海量数据的图服务~🥳
想要来交流图数据库技术吗？关注公众号后发送“加群”，NebulaGraph 迷人小姐姐拉你进群~
🙋♂️ 喜欢本文的话，来个分享、👍 赞、在看
谢谢~
