首页 > 编程语言 >GraphBLAS图的稀疏表示详解

GraphBLAS图的稀疏表示详解

来源：互联网 2026-07-22 08:04:03

图采用邻接矩阵表示，但实际存储使用稀疏格式如坐标格式、压缩行格式、压缩列格式，仅记录非零元素。GraphBLAS框架自动选择最优格式，并引入按行位图，随机查询时间复杂度为常数，适用于半稠密场景，平衡了存储与查询效率。

先装好工具：执行 python -m pip install python-graphblas 就行。

1 邻接矩阵表示图

先来看最直观的表示方法——邻接矩阵。假设有4个节点（0、1、2、3）构成的有向图，如下图所示：

长期稳定更新的攒劲资源： >>>点此立即查看<<<

邻接矩阵的行代表出边，列代表入边。比如看第2行（节点2），它指向节点0和节点3；再看第3列（节点3），这一列有3个1，说明入度为3，分别来自节点1、2、3（节点3自身也有自环）。这样理解起来非常直观。

用代码构造一个numpy数组来表示这个矩阵：

 复制代码import numpy as npA = np.array([
    [0, 1, 1, 0],
    [1, 1, 0, 1],
    [1, 0, 0, 1],
    [0, 0, 1, 1]
], dtype=np.int32)

概念上邻接矩阵很好理解，但问题在于：如果直接用二维稠密数组存储，那效率低得吓人。举个实际场景——100万用户的社交网络，平均每人关注100人，如果全用稠密矩阵，会是什么结果？看下面这张图对比一下：

2 稀疏存储表示图：

所以，实际用的是稀疏存储——只记录非零元素的坐标和值。GraphBLAS内部基于稀疏数据结构，具体用哪种格式，框架会自动选择最合适的。

2.1 COO/CSR/CSC

通常，我们从COO（三元组）格式开始构建数据，但内部计算时默认会转为CSR格式。你不需要手动指定，框架会智能选择。下面用python-graphblas演示一下COO构建：

 复制代码import graphblas as gb# COO 三元组 
row = [0, 0, 1, 1, 1, 2, 2, 3, 3] 
col = [1, 2, 0, 1, 3, 0, 3, 2, 3] 
val = [1]*9 
# 构建矩阵（默认 CSR） 
A = gb.Matrix.from_coo(row, col, val, nrows=4, ncols=4) #  
# 默认就是 CSR 格式
print(A)

如果你想看看三种格式的内部存储细节，可以用scipy的稀疏矩阵来对比一下。下面这段代码演示了COO、CSR和CSC的构造和输出，注意CSC是按列索引记录非零坐标：

 复制代码import numpy as npfrom scipy.sparse import coo_matrix, csr_matrix# 1. 准备 COO 格式的数据row = np.array([0, 0, 1, 1, 1, 2, 2, 3, 3])col = np.array([1, 2, 0, 1, 3, 0, 3, 2, 3])data = np.array([1, 1, 1, 1, 1, 1, 1, 1, 1])  # 2. 构建 COO 矩阵（构建阶段）
coo = coo_matrix((data, (row, col)), shape=(4, 4))
  # 3. 转换为 CSR 格式（计算阶段，这会自动完成压缩）
csr = coo.tocsr()# 查看结果
print(csr.toarray())    # 输出: [[0 1 0] [0 0 1] [0 0 0]]
print(csr.indptr)       # 输出: [0 2 5 7 9]  (行索引被压缩了)
print(csr.indices)      # 输出: [1 2 0 1 3 0 3 2 3]
print(csr.data)         # 输出: [1 1 1 1 1 1 1 1 1]
#4. 转换为 CSC 格式（计算阶段，这会自动完成压缩）
csc = coo.tocsc()
print(csc.toarray())
print(csc.indptr)       # 输出: [0 2 4 6 9]  (列索引被压缩了)
print(csc.indices)      # 输出: [1 2 0 1 0 3 1 2 3]
print(csc.data)         # 输出: [1 1 1 1 1 1 1 1 1]

2.2 3种表达方式说明

GraphBLAS图的稀疏表示详解

2.3 和稠密的规模对比

场景：100万用户关注关系，平均每人关注100人。下面两张图直观展示了稀疏存储与稠密存储的巨大差异：

3 介于稀疏和稠密之间的bitmapr，bitmapc

除了CSR等，GraphBLAS 7.0以上版本还引入了一种介于稀疏和稠密之间的格式——bitmapr（Bitmap by Row，按行位图）。它的思路是：每行用一个0/1位图标记所有列，1的位置就是非零元素。构造逻辑如下：

GraphBLAS图的稀疏表示详解

bitmapc 与 bitmapr 逻辑一致，只是按列进行位图标记。

3.1 bitmapr和CSR对比

BitmapR的核心优势是：随机查询 A[i, j] 是 O(1) 的（直接读位图），而CSR需要 O(log k) 的二分查找。对于半稠密场景，这个优势非常明显。

GraphBLAS图的稀疏表示详解

3.2 什么时候用 BitmapR？

条件	推荐格式
每行非零数 / ncols < 10%	CSR
每行非零数 / ncols ≈ 20%~6%	BitmapR
每行非零数 / ncols > 80%	FullR（稠密）
大量全空行	HyperCSR