第一次接触图的度矩阵和邻接矩阵时我一度很困惑——明明画出来的图已经那么直观为什么还要转成矩阵后来才想明白一个关键问题所有可以规模化计算的东西都必须先变成数值结构。图论里的一切算法从最基础的BFS/DFS到图神经网络的消息传递归根结底都在操作这些矩阵。这篇文章不打算堆砌公式而是想从“图”“邻居”“度矩阵”“邻接矩阵”这四个最朴素的概念出发把它们的来龙去脉、数学形式、代码实现、以及在真实工程和深度学习里的落地点讲清楚。你要是在学图计算、图神经网络或者只是工作中第一次遇到带“图”的项目都可以拿这篇文章当一份入门口径。1. 图的数学定义从“画出来的图”到“可计算的图”1.1 为什么需要形式化定义我们平时说的“图”在计算机和数学领域指的是Graph不是Image。它由两部分组成顶点集合 V以及边集合 E。一个图记作 G (V, E)。顶点就是“点”在社交网络里是一个个用户边就是“连线”表示用户之间有关注、好友、互动等关系。这里的核心是一张图最终要被计算机处理就必须用结构化的方式描述“谁和谁连着”。很多初学者会混淆“邻居”“连通”“可达”这些概念。比如A和B直接相连B和C直接相连那么A到C是可达的但A的邻居只有BC不是A的邻居。这个区分在后面特别重要尤其在做图神经网络时邻居决定了聚合信息的范围。形式化定义的作用在于一旦我们把图写成 G (V, E)就可以继续把它翻译成邻接矩阵、度矩阵等一系列数值对象然后交给算法去跑。这一步看似多余实际上决定了后面所有计算能否进行。没有人会真的在程序里“画”一张图。1.2 有向、无向、加权三种常见变体图的形态决定了矩阵的写法。无向图中边 (u, v) 和 (v, u) 是同一回事表示关系是双向的比如微信好友关系有向图则区分方向比如微博的关注关系A关注B不代表B关注A加权图给每条边赋予权重比如交通网络里的距离或通行时间。我建议把这三类图在建模初期就分清楚因为它们对应的邻接矩阵形式完全不同。简单总结如下图的类型边的表达邻接矩阵的特点典型场景无向图(u, v) 无方向对称矩阵 A_ij A_ji好友关系、分子结构有向图(u, v) 有方向非对称矩阵关注关系、PageRank加权图(u, v, w) 带权重矩阵元素为权重而非0/1路径规划、推荐系统还有一个经常被忽略的细节是自环和重边。自环就是节点自己连自己在邻接矩阵里体现为对角线元素为1重边是两点之间存在多条边在简单图里通常合并为一条但如果是多重图邻接矩阵的计数方式也要调整。实际工程中如果从业务数据直接构造图经常会出现重复边需要先去重再计算矩阵。1.3 稀疏图与稠密图真正影响后续所有选择的分水岭“稀疏”和“稠密”不是一个绝对概念而是相对顶点数而言。假设有 n 个顶点最多可能存在的边数是 n(n-1)/2无向简单图当边的数量 m 远小于这个上限时就叫稀疏图接近上限就叫稠密图。这个区分为什么重要因为邻接矩阵的空间复杂度是 O(n²)对于一万个顶点矩阵有一亿个元素如果每个元素用8字节的float存就是800MB直接内存爆炸。如果是稀疏图我们就应该用邻接表、CSR等稀疏存储方式而不是老老实实建一个完整的二维矩阵。我见过不少新手在学图神经网络时拿一个几千节点的数据集用np.zeros((n, n))硬建邻接矩阵数据量一大立刻卡死。这不是代码能力问题是对稀疏性缺乏概念。所以后面讲邻接矩阵我会先讲完整矩阵的构造逻辑再讲工程里如何处理大图。2. 邻居图上的“关系圈”到底怎么算2.1 邻居的精确定义与开放/闭合邻居在无向图中节点 u 的邻居 N(u) 定义是与 u 直接通过一条边相连的节点集合即 N(u) {v | (u, v) ∈ E}。在有向图中又分为出邻居u 指向的节点和入邻居指向 u 的节点。更进阶一点的概念是“开放邻居”和“闭合邻居”。开放邻居就是上面定义的那个集合 N(u)不包含 u 自己闭合邻居则加上节点自身记为 N[u] N(u) ∪ {u}。这个区分在实现图神经网络聚合时会直接用上。为什么要把“自身”也算进去因为很多图的传播算法比如GCN的经典版本在每一层更新节点表示时希望同时保留节点自己的特征又聚合邻居的特征。如果只聚合邻居当前节点自己的信息反而丢掉了会导致特征退化。所以要么把自环加进邻接矩阵要么显式使用闭合邻居的概念。2.2 用邻居理解采样、消息传递和子图邻居概念是图算法里最基础也最核心的“局部结构”。从邻居出发可以扩展出很多操作K-hop邻居从节点出发走K步能到达的节点集合用来定义感受野。子图提取从目标节点开始不断向外扩展邻居集合得到局部子图。邻居采样对于度数很高的节点不会把所有邻居都拿来聚合而是采样固定数量的邻居这在GraphSAGE等算法里很常见。以GraphSAGE为例它每一步聚合的是“采样后的邻居节点”而不是全部邻居。原因很实际社交网络里有些大V有百万级粉丝如果把所有邻居都纳入计算一个batch的显存需求会高到无法接受。这种对邻居集合的主动截断是基于邻居概念最典型的工程化改造。2.3 实操用NetworkX计算每个节点的邻居NetworkX是Python里最常用的图分析库适合中小规模图。下面是计算邻居的标准操作import networkx as nx G nx.Graph() G.add_edges_from([(0, 1), (0, 2), (1, 2), (2, 3)]) print(节点2的邻居:, list(G.neighbors(2))) # 输出: 节点2的邻居: [0, 1, 3] print(节点0的度:, G.degree(0)) # 输出: 节点0的度: 2这段代码里G.neighbors(2)返回的是一个迭代器需要用list()转成列表。注意对于无向图neighbors返回的是所有通过一条边相连的节点不区分方向。对于有向图NetworkX里分别有G.successors(u)和G.predecessors(u)来获取出邻居和入邻居用错了会得到完全不同的结果。我在实际项目里发现一个高频问题很多人在保存图数据时只保存边列表以为加载进来就万事大吉。结果一查某个节点的邻居发现节点索引对不上。这时务必要检查节点标签是否从0开始连续编号如果不是用nx.convert_node_labels_to_integers(G)做一次重映射否则后面的邻接矩阵行列顺序会乱。3. 邻接矩阵把边变成数字之后一切开始加速3.1 邻接矩阵的构造规则与自环处理邻接矩阵 A 是一个 n×n 的方阵规则很简单如果存在从 i 到 j 的边A_ij 1否则 A_ij 0。对于加权图A_ij w_ij。对于无向图因为边是双向的A 是对称矩阵A_ij A_ji。自环的处理在实际工程里很容易踩坑。一个最典型场景是把原始邻接矩阵直接用于图神经网络却完全没加自环。这时候节点自身的信息在聚合时只取决于自身的更新权重不会显式出现在邻居聚合里。PyTorch Geometric 里的GCNConv默认会在torch_geometric.utils中处理自环但如果你手写传播过程就必须自己加常见的做法是A_tilde A np.eye(n)如果图本身有自环就要小心重复计数的问题最好在构造时明确约定对角线元素是1表示有自环0表示没有不要混着来。3.2 无向图的对称性以及为什么它如此重要无向图的邻接矩阵一定是对称矩阵A A^T。这个性质在理论推导和工程实现里都极其重要。从理论上看对称矩阵一定有完备的正交特征向量系特征值是实数。这是谱图理论Spectral Graph Theory的基石图拉普拉斯矩阵的谱分解、GCN里用的特征分解、谱聚类里的特征向量计算全都依赖这个性质。如果图是有向的邻接矩阵不对称谱分析就复杂得多。从工程上看对称性意味着我们可以只存储矩阵的上三角或下三角部分节省近一半空间。实际Graph框架中比如DGL、PyG都会假设你传入的是无向图或已处理为对称形式如果不小心传了非对称矩阵消息传递的方向就会出错训练结果莫名其妙地变差。3.3 存储选择当邻接矩阵变得又大又空顶点数 n 1万时邻接矩阵有1亿个元素但其实大部分是0。现实中大多数图是稀疏图所以矩阵的存储方式直接决定了你的项目能跑到多大的规模。我整理一下常用的几种存储形态存储方式访问随机边遍历邻居空间复杂度使用场景密集二维矩阵O(1)O(n)O(n²)小图、教学演示邻接表O(k)O(k)O(m n)中等规模图、BFS/DFSCSRO(log k)O(k)O(m n)大规模稀疏图、图神经网络COOO(log k)O(k)O(m n)快速构建矩阵、内存友好其中CSRCompressed Sparse Row是工业界和大规模图计算系统的默认选择。它的核心思想是建一个长度为 n1 的行偏移数组indptr一个长度为 m 的列索引数组indices再加上一个长度为 m 的数据数组data这样整张图的邻接信息就压缩成三个数组。PyTorch Geometric 和 DGL 内部都采用类似CSR的布局。3.4 代码示例邻接矩阵的四条读写通道先来看用NumPy构造一个简单无向图的邻接矩阵import numpy as np n 4 edges [(0, 1), (0, 2), (1, 2), (2, 3)] A np.zeros((n, n), dtypefloat) for i, j in edges: A[i, j] 1 A[j, i] 1 # 无向图需要反向填充 print(A) # [[0. 1. 1. 0.] # [1. 0. 1. 0.] # [1. 1. 0. 1.] # [0. 0. 1. 0.]]这段代码做了两次填充是因为无向图的对称性要求。如果只填一次后面的特征传播会变成单向的非常多文章里的复现代码就在这个细节上翻车。再看用SciPy的稀疏矩阵存储from scipy.sparse import coo_matrix, csr_matrix row [0, 0, 1, 1, 2, 2, 2, 3] col [1, 2, 0, 2, 0, 1, 3, 2] data [1, 1, 1, 1, 1, 1, 1, 1] A_coo coo_matrix((data, (row, col)), shape(n, n)) A_csr A_coo.tocsr() print(A_csr.toarray())COO格式的优点是构建方便直接传入三个数组即可缺点是查询和矩阵运算效率不如CSR。所以实际流程往往是先COO构建再转CSR用于计算。这个“先COO后CSR”的两步法在PyG、DGL构建图数据时也是标准流程。4. 度矩阵一个看似简单却贯穿图计算全局的对角矩阵4.1 度的定义以及度矩阵 D diag(A·1) 的计算节点的度指的是与该节点直接相连的边的数量。在无向图中度 d_i Σ_j A_ij也就是说把邻接矩阵第 i 行全部加起来。度矩阵 D 是一个对角矩阵对角线上的元素就是各个节点的度非对角元素为0。用代码表达特别简洁D np.zeros((n, n)) for i in range(n): D[i, i] A[i, :].sum()更向量化的写法是用矩阵乘以全1向量D np.diag(A np.ones(n))如果你习惯用np.diag要注意A np.ones(n)得到的是一个一维数组每个元素是每行的和正好是每个节点的度。在有向图中行和是出度列和是入度度矩阵就可以进一步拆分为 D_out 和 D_in。很多推荐算法里的PersonalRank、以及知识图谱嵌入里的传播都会用到这种拆分。4.2 度矩阵为什么重要从随机游走到归一化度矩阵看似只是一个统计量但它实际上承担着“归一化”的重任。想想随机游走如果一个人从 u 节点出发随机选择一条边走到邻居那么走到每个邻居的概率应该是 1/d(u)。用矩阵表示转移概率矩阵是 P D^{-1} A它的每一行和为1这才是一个合法的概率矩阵。在PageRank算法里这个 D^{-1} A 构成了网页跳转的基础在DeepWalk、Node2Vec等图嵌入方法中随机游走使用的也是这个矩阵。如果没有度矩阵做归一化直接拿邻接矩阵去模拟传播边的数量差异会主导整个过程高度数节点的影响会无限放大低度数节点的特征被淹没。到图神经网络这里度矩阵的作用进一步变成“对称归一化”。经典GCN使用的传播矩阵是A_norm D^{-1/2} A D^{-1/2}这个形式既做了行的归一化也做了列的归一化保持了矩阵的对称性。从直觉上理解它按照两端的度对每条边进行折中避免一个“超级节点”因为邻居太多而主导整体信号。4.3 拉普拉斯矩阵 L D - A 和图的第一道门槛度矩阵最经典的搭档是拉普拉斯矩阵 L D - A。这张矩阵在谱图理论里是核心研究对象它的二次型满足x^T L x Σ_{(i,j)∈E} (x_i - x_j)^2这个式子说明拉普拉斯矩阵度量了一个信号可以理解为节点上的数值特征沿着边产生的变化。变化越小信号越平滑。这个想法被直接用于图信号处理和图半监督学习比如标签传播算法就可以理解为在图上最小化这种变化。对称归一化的拉普拉斯矩阵更常用L_sym I - D^{-1/2} A D^{-1/2}GCN论文里用的其实就是这个矩阵的变体。很多人在读论文时会被一堆拉普拉斯变体绕晕但只要抓住一个核心逻辑就不会乱邻接矩阵告诉你哪两个节点有关系度矩阵告诉你每个节点关系的数量两者组合出来的拉普拉斯矩阵则告诉你图上的“变化量”和“平滑程度”。4.4 孤立节点的除零问题经验教训度矩阵最坑的地方是孤立节点的度是0。如果直接计算 D^{-1}对角度是0的位置就会出现除零问题产生NaN。我在第一次写GCN代码时就因为这个导致loss变成NaN排查了很久才发现是孤立节点的问题。解决方案有三种按推荐顺序排列给邻接矩阵加自环A_tilde A I这样每个节点至少度数为1D_tilde 就不会有0。计算逆时手动指定零度位置d_inv np.where(d 0, 1.0 / d, 0)。在度上加极小值d 1e-8但这种方法会影响数值精度只适合极大规模的近似计算。实际工程中第一种方法最常用它还有一个额外好处让节点在消息传递时保留自身特征一举两得。5. 从矩阵到消息传递邻接矩阵与度矩阵如何撑起图神经网络5.1 GCN 的传播公式拆解现在我们把基础概念串起来看一个真实场景图卷积网络GCN。GCN每一层的传播公式是H^{(l1)} σ( Â H^{(l)} W^{(l)} )其中 Â 是在加了自环之后的归一化邻接矩阵Â D_tilde^{-1/2} A_tilde D_tilde^{-1/2}A_tilde A ID_tilde diag(Σ_j A_tilde_ij)这里的 H^{(l)} 是节点在第 l 层的特征矩阵每一行是一个节点W^{(l)} 是可学习的权重矩阵。这个公式表面上是矩阵乘法实际上做了一件很直观的事每个节点的新特征 自身特征和邻居特征按照度进行加权的平均再经过一个线性变换和非线性激活。用矩阵乘法实现邻居聚合是理解GCN的关键A_tilde H^{(l)} 相当于把每个节点的邻居特征求和而两边乘上 D_tilde^{-1/2} 是对节点及其邻居的度做归一化。度越大的节点在聚合时被稀释得越厉害防止它天然占优势。5.2 对称归一化 D^{-1/2} A D^{-1/2} 的来龙去脉有人会问为什么是 D^{-1/2} 而不是 D^{-1}这里有一个很直观的理由。如果用 D^{-1} A得到的是“行归一化”的传播矩阵它保证每一行和为1像随机游走。但它是非对称的从 j 传到 i 的权重是 1/d(j)而这个权重在反向传播时会有偏差。GCN想要的是一个对称的归一化保证计算出来的拉普拉斯矩阵特征值是实数在数值优化上更稳定。D^{-1/2} A D^{-1/2} 的每一项实际上可以拆开看Â_ij A_ij / sqrt(d_i * d_j)也就是说一条边连接的两个节点如果两端都度很高那么这条边对两端的影响就会被压缩如果一端度很低那么这条边对低度节点的影响会相对放大。这比单纯的行归一化更平衡。我在手动实现GCN层时最常犯的错是忘记 D 用的是加自环后的度矩阵。你想想A_tilde A I那么 D_tilde 的对角线也变了必须重新计算。如果还用原始 D归一化就错了模型效果会很差。5.3 多层传播时度矩阵的意义GCN堆叠K层时每一层都在重复“聚合邻居信息”的操作。第一层聚合的是直接邻居1-hop第二层聚合的是第一层的结果所以每个节点间接看到了两步之内的信息2-hop。这就是感受野的概念K层GCN每个节点的感受野是K-hop邻居。需要注意这种堆叠和直接计算 A^K 有着本质区别。A^K 的每个元素表示两个节点之间长度为K的路径数量数字会随K指数增长容易数值溢出而且路径数量并不能准确表达“多层语义”。GCN选择把特征矩阵 H 和权重 W 在每一层重新组合让模型自己学习在每一层应该提取什么信息而不是简单地把路径计数堆上去。度矩阵在这个过程中依然在起作用每一层的 Â 都是一样的它持续地给低度节点更多的“注意力权重”给高度节点更多“稀释”。这种归一化是所有后续图模型构建稳定的基石。5.4 一个可以直接跑的最小GCN例子为了验证前面这些概念下面给一个不依赖PyTorch Geometric的最小GCN实现用NumPy完成一次前向传播import numpy as np def gcn_layer(A, H, W): n A.shape[0] A_tilde A np.eye(n) d A_tilde.sum(axis1) d_inv_sqrt np.diag(np.power(d, -0.5)) A_norm d_inv_sqrt A_tilde d_inv_sqrt return np.tanh(A_norm H W) # 构造4个节点每个节点2维特征 A np.array([ [0, 1, 1, 0], [1, 0, 1, 0], [1, 1, 0, 1], [0, 0, 1, 0], ], dtypefloat) H np.array([ [0.1, 0.2], [0.3, 0.4], [0.5, 0.6], [0.7, 0.8], ]) W np.random.randn(2, 2) out gcn_layer(A, H, W) print(out)这段代码的核心就四步加自环、计算度矩阵、对称归一化、矩阵乘法。你会发现和前面讲的邻接矩阵、度矩阵的概念完全对应。如果你能手动实现这一层再去看PyG里的GCNConv源码就会觉得非常清晰。6. 规模、性能与更广的图计算图景6.1 当图变大稀疏存储和分布式图计算当网络规模到百万级、亿级节点时邻接矩阵和度矩阵的“教科书写法”不再适用。以1亿节点为例即使只用CSR存储每条边需要存储两个整数列索引和数据如果边数也是10亿单机内存依然会非常紧张。工业界解决大图计算通常有几条路线一是图数据库Neo4j、JanusGraph适合事务型查询二是分布式图计算框架Spark GraphX、Pregel适合离线批处理三是面向图神经网络的框架PyG、DGL它们将图划分成子图分批加载到GPU配合邻接矩阵的稀疏格式进行计算。在这个阶段度矩阵依然没有缺席。DGL和PyG在分布式训练时都会预计算节点的度信息用于采样和归一化。你可以把它理解为无论图多大归一化步骤只要做一次之后所有层共用这是度矩阵成为“基础设施”的原因。6.2 邻接表、CSR等存储格式的比较前面表格里提过存储格式这里再展开讲一下工程选型。如果你只是做算法验证用NetworkX和SciPy的CSR就够了。你的数据加载时间是分钟级矩阵运算可以在CPU上完成不需要过度设计。如果你要训练图神经网络尤其GPU训练数据格式主流是PyG的Data对象和DGL的DGLGraph。两者都把边表示为COO或CSR的索引数组PyG默认使用edge_index形状是[2, num_edges]两行分别是源节点和目标节点。首次接触时很容易忘记邻接矩阵是对称的但edge_index在无向图中需要显式包含双向边否则消息传递是单向的。一个小建议在建图的时候把边的去重和双向补充一次做完再做度计算避免后续每个环节都重复处理边缘情况。6.3 从基础概念到复杂问题因子图、SLAM建图与更多图的基础概念能延伸到的领域远比想象中广。SLAM建图本质上就是在维护一个图结构机器人位姿是节点位姿之间的约束是边求解过程等价于在图上做优化。因子图优化Factor Graph Optimization里每个因子连接若干节点共享函数定义在连接的节点上这个概念与邻接矩阵中的非零元位置如出一辙。知识图谱也是一张巨大的有向图实体是节点关系是边图神经网络通过邻居聚合来学习实体表示。另一个容易被忽视的场景是ER图实体关系图数据库建模时每个表是一个实体外键关系是边把ER图转成邻接矩阵辅助分析表间依赖在大数据血缘管理里非常实用。我的个人体会是图的魅力不在于定义本身而在于一旦你把数据抽象成图邻接矩阵和度矩阵就会自动告诉你这个系统中“谁和谁关联”以及“关联得有多紧密”。这种抽象能力是图算法跨越推荐、搜索、机器人、数据库等众多领域的底层原因。最后分享一个在实战中反复用到的技巧遇到任何可以建模成图的问题不要急着上复杂模型先把图画出来再用代码把邻接矩阵和度矩阵算一遍确认它们和你的直觉一致。这一步能避免后面90%的结构性错误也是我见过的最有效的排错手段。