★ FEATURED ARTICLE 第一次接触图神经网络或者图挖掘相关项目的时候大多数人都会跟我一样先被D^{-1/2} A D^{-1/2}这种式子劝退一波。我当时对着代码里的度矩阵D和邻接矩阵A翻来覆去看了好久才搞明白这两个矩阵到底在干什么。其实图论里那些看起来很高深的概念落地到代码和实际业务里都绕不开最基础的几个东西图本身长什么样邻居怎么定义以及度矩阵、邻接矩阵这两个矩阵到底怎么构建、怎么用。这篇文章我就把这四个基本概念一次性讲透。读完你不仅能看懂常见的图算法和 GCN、GAT 这类图神经网络的输入是在算什么还能直接用 Python 把邻接矩阵和度矩阵打印出来验证。适合刚接触图神经网络的学生、做推荐系统或者知识图谱的工程师以及一切被“图”这个字弄得头疼的人。1. 先把“图”这个东西说清楚它到底在描述什么1.1 图不是你电脑里的图片是一堆点和线的集合做机器学习的人嘴里说的“图”是 Graph而不是 Image。图由两部分组成顶点Vertex 或 Node和边Edge。你可以把顶点理解成一个个对象边表示对象与对象之间的关系。举个例子微信朋友圈的好友关系就是一个典型的无向图你是图里的一个顶点你的好友也是顶点你们之间的好友关系就是一条边。你认识张三那这条边就是双向的不需要考虑方向这叫作无向边。再看微博的关注关系你关注了一个大 V但对方未必关注你这种带方向的关系就是有向边。除了方向和没有方向的区别边还可以带权重。电商平台上用户对商品的下单关系边的权重可以是交易次数或者交易金额。地图导航里的路网图边的权重就是路段的长度或者通行时间。理解了这张图你就知道为什么很多人说图是描述“关系”的自然语言——社交网络、交通网络、分子结构、知识图谱本质上全是图。1.2 不同领域里那些“图”到底有什么共同点相关热词里出现了一堆跟图有关的名词UML 图、ER 图、流程图、类图、SLAM 建图、数字孪生 2D 组态图、瓦片图、因子图优化……看起来五花八门但你要抓住一个核心凡是在描述实体及实体之间关系的数据结构都可以抽象成图。领域里的名字顶点是什么边是什么图的方向社交网络用户好友/关注/点赞无向或有向电商推荐用户、商品、店铺购买、浏览、收藏有向/带权知识图谱实体关系有向UML 类图类继承、实现、依赖有向ER 图实体、属性外键联系无向SLAM 中的因子图机器人位姿、观测值约束关系无向数字孪生 2D 组态设备、传感器控制/数据流有向你会发现无论它叫什么名字底层都是同一个数学模型顶点加边。这也是为什么我强烈建议任何一个做数据处理和算法的人都先掌握图的基础知识。因为把这个抽象模型学会了不管换到什么领域你都能快速迁移。1.3 为什么非要拿矩阵来存图一个问题一个图无非就是一堆点和线为什么做算法的人不直接用列表非要用矩阵原因在于矩阵可以跟线性代数打通。一旦图变成了矩阵你就可以用矩阵乘法、特征分解、求导这些工具来处理它图神经网络能跑起来靠的就是把图转换成矩阵以后再做矩阵运算。邻接矩阵和度矩阵就是其中两个最核心的表示方式。2. 邻居图算法里最常挂在嘴边的词2.1 邻居的准确定义只隔一条边的节点图里的“邻居”跟现实生活里不一样不看你住得近不近只看有没有一条边直接连着。给定一个无向图顶点v的邻居集合记作N(v)就是所有与v之间有一条边直接相连的顶点。举个例子你有四个朋友 A、B、C、D你和 A、B 是直接好友A 和 C 是直接好友那么你的邻居是 A 和 BC 不是你的邻居因为你和 C 中间隔着一个 A。C 是你的二阶邻居也就是说从你出发走两步能到达的节点。这个“走几步能到”的概念在图算法里面特别重要后面讲多层图神经网络的时候会反复用到。2.2 有向图里邻居要分入和出有向图比无向图多了一个方向的问题。在有向图中邻居要区分“我指向谁”和“谁指向我”。关注场景里大 V 的“粉丝邻居”就是所有指向他的节点大 V“关注的邻居”是它指向的节点两者数量可能差得很远。工程上通常把邻居细分成两类出邻居Out-neighbors和入邻居In-neighbors。对于节点v出邻居是从v出发的边所指向的节点集合{u | v-u}入邻居是所有能到达v的节点集合{u | u-v}。这个区分在处理 PageRank、知识图谱关系推理、以及有向图神经网络的时候是绕不过去的关键点。2.3 为什么邻居是图神经网络的起点现在主流图神经网络的两大类方法说白了都是围绕“邻居”在转。一类叫消息传递每个节点不断收集邻居的信息把邻居的特征聚合起来更新自己的特征另一类叫游走采样从一个节点出发沿着边走采出一串邻居序列再喂给序列模型。用生活话来说每个节点就像班级里的一个学生本身有自己的成绩但你最后能考上什么大学很大程度上取决于你周围的同学都在学什么。图神经网络干的事情就是让每个节点反复看自己的邻居在干什么然后调整自己。理解邻居这个概念后面再看 GCN 和 GAT 的代码就不会懵因为它们的公式本质上都是在做邻居信息的加权求和。3. 邻接矩阵把“谁和谁相连”写进一张表里3.1 邻接矩阵的构建规则有边填 1没边填 0邻接矩阵Adjacency Matrix是图的另一种标准表达方式。假设图里有N个顶点邻接矩阵就是一个N x N的方阵用A[i][j]表示顶点i和顶点j之间是否有边。无向图里A[i][j] 1表示i和j相连由于边没有方向所以无向图的邻接矩阵一定是关于对角线对称的A[i][j] A[j][i]。举个例子假如我们有一个 5 个节点的无向图边的集合是{(1,2), (2,3), (3,4), (4,5), (5,1)}也就是 1-2-3-4-5 首尾相接成环。那么邻接矩阵是这样的1 2 3 4 5 1 [0 1 0 0 1] 2 [1 0 1 0 0] 3 [0 1 0 1 0] 4 [0 0 1 0 1] 5 [1 0 0 1 0]第一行第二列是 1说明节点 1 和节点 2 之间有边第一行第三列是 0说明节点 1 和节点 3 之间没有直接边。这个矩阵每一行其实就是在告诉你该节点跟图上所有其他节点的连接情况。3.2 有向图、带权图、自环的邻接矩阵分别怎么处理邻接矩阵不是只有 0 和 1 这种最简单的形式根据图的类型不同里面的数值会有变化。有向图A[i][j]表示是否存在从i指向j的边存在就填 1不存在就 0。有向图的邻接矩阵不一定对称。比如微博关注关系里A 关注了 B 但 B 没关注 A那么A[A][B]1但A[B][A]0。带权图不再满足于填 0 和 1边有权重邻接矩阵里对应位置直接填权重数值。比如A[i][j]3.5表示从i到j的边权重是 3.5。电商场景里这就是交易次数交通场景里就是距离。自环Self-loop如果允许节点自己指向自己那么对角线上的值就不是 0 了。有些图算法会主动给每个节点加上自环相当于把节点自身的特征也加入学习过程。后面讲图卷积的 trick 时会再提到这个操作。3.3 邻接矩阵对比邻接表什么时候用哪个邻接矩阵的最大优点是查询两个节点是否相连非常快直接下标访问A[i][j]就好了而且做矩阵运算非常方便适合 GPU 并行。缺点也很明显存储空间和节点数的平方成正比。一个一万节点的图邻接矩阵就是 1 亿个元素即使全用二进制位表示也要 12.5MB如果图里节点数到了百万级直接存稠密矩阵几乎不可能。所以工程上更常见的是稀疏矩阵存储。Python 里可以用scipy.sparse来存邻接矩阵只记录非零元素的位置和值省内存而且大部分矩阵运算都支持。与之对应的还有邻接表每个节点保存一份邻居列表查询一个节点的所有邻居非常高效但判断两个节点是否相连就需要遍历列表。实际写算法时小图用邻接矩阵大图用邻接表或稀疏矩阵这个选择直接影响性能。4. 度矩阵给每个节点的邻居数量记账4.1 度的定义邻居数量就是度度Degree这个概念跟邻居强相关。无向图中一个顶点的度就是它的邻居个数也就是邻接矩阵里这一行所有非零元素的个数或者这一列因为对称都一样。拿上面的 5 节点环图举例每个节点两边各连一个节点所以每个节点的度都是 2。有一个很有趣的定理叫握手定理所有顶点的度之和等于边数的两倍。原因很简单每条边有两个端点它同时为两个端点的度各贡献了 1。这个定理在检查代码有没有算错时很好用你统计完所有节点的度加起来如果是偶数再对比边数的两倍就能验证数据是否有问题。4.2 有向图里度要分成入度和出度无向图只有一个度有向图要拆成两个入度In-degree和出度Out-degree。入度就是有多少条边指向该节点也就是邻接矩阵中该列的和出度就是该节点有多少条边指向别的节点也就是邻接矩阵中该行的和。入度和出度在不同场景含义差别很大微博大 V 的入度远大于出度因为他被很多人关注但他关注的人很少一个营销号可能出度很大四处关注别人。在做图算法时入度高的节点往往代表着“权威”“热门”出度大的节点往往意味着“活跃”“传播者”。很多中心性指标都会用到这两个值。4.3 度矩阵长什么样只有对角线有值度矩阵Degree Matrix记作D它是一个对角矩阵对角线上每个位置D[i][i]存放节点i的度其他位置全是 0。这是图论里很特殊的一个矩阵——几乎所有信息都集中在对角线上它的作用不是单独描述图而是作为“归一化”的工具跟邻接矩阵搭配使用。举个例子上面那个 5 节点环图每个节点度都是 2度矩阵写出来是1 2 3 4 5 1 [2 0 0 0 0] 2 [0 2 0 0 0] 3 [0 0 2 0 0] 4 [0 0 0 2 0] 5 [0 0 0 0 2]看着简单但它的意义极大。图算法里面经常需要做一些归一化操作比如按度把邻接矩阵的权重摊平这个时候度矩阵就是那个“除数”。4.4 度矩阵和邻接矩阵为什么总是成对出现如果你去翻图神经网络的论文或开源代码会发现D和A通常是绑定在一起的比如最常见的拉普拉斯矩阵L D - A还有图卷积里的表达式D^{-1/2} A D^{-1/2}。它们的搭配不是巧合本质上是要解决同一个问题让信息传递的时候不要被高度节点带偏。一个节点如果有 1000 个邻居和一个只有 3 个邻居的节点如果信息只是简单相加高连接节点会把低连接节点的信息淹没掉。度矩阵在这里扮演的角色就是“归一化系数”——把每个节点的邻居数算出来然后对信息做平均或者缩放让不同度的节点处于一个可比较的尺度上。这一点在下一部分展开讲。5. 从度矩阵和邻接矩阵到图卷积这两个矩阵到底怎么用起来5.1 先看懂拉普拉斯矩阵 L D - A如果你只记住两个矩阵那可能还看不出来它们为什么重要。真正的关键是拉普拉斯矩阵L D - A。这个矩阵把度矩阵和邻接矩阵组合到了一起对角线是每个节点的度非对角线是原来边的负值。仍然拿 5 节点环图来说它的拉普拉斯矩阵长这样1 2 3 4 5 1 [ 2 -1 0 0 -1] 2 [-1 2 -1 0 0] 3 [ 0 -1 2 -1 0] 4 [ 0 0 -1 2 -1] 5 [-1 0 0 -1 2]拉普拉斯矩阵在数学上有个很好的性质它是一个半正定矩阵特征值都是非负的其中最小特征值一定是 0对应的特征向量是全 1 向量。这个性质让它在谱聚类、图信号处理、图卷积里反复出现。直观上你可以把它理解成一个“光滑度”算子它衡量一个信号在图上的变化有多剧烈。如果相邻节点之间特征差异很小L的二次型x^T L x就很小如果差异很大这个值就很大。5.2 为什么归一化要用度矩阵开根号在 GCN图卷积网络里最经典的特征传播公式是H^{(l1)} σ( D^{-1/2} A D^{-1/2} H^{(l)} W^{(l)} )很多人看到D^{-1/2} A D^{-1/2}就懵。为什么不是直接用邻接矩阵 A为什么要用度矩阵开根号先看直接用 A 的问题A 的行和不是 1也就是说一个节点聚合邻居信息时如果邻居很多累加结果会变得非常大特征数值容易爆炸如果节点度很小累加结果又很小更新幅度过小。于是最简单的思路是做对称归一化把每行每列都除以度开根号。拆开来看(D^{-1/2} A D^{-1/2})[i][j]的计算方式是A[i][j] / sqrt( D[i][i] * D[j][j] )如果i和j之间没有边分子为 0如果有边分子是 1无权图分母是两端节点度的乘积再开根号。这样处理的效果是一个连接度很高的节点传递出去的信息会被稀释而低连接度节点的信息会被相对放大整体特征尺度均衡。如果不做这一步常规 GCN 很难收敛训练数轮后梯度大概率会爆炸。顺便提一句有些实现里还会再加一个自环 trick把A变成A I把D也对应更新为D I。这样每个节点在聚合时会把自身特征也算进去相当于让节点不仅看邻居也回头看看自己的旧特征。表里看到的 GCN 开源代码基本都有这两行对矩阵的预处理。5.3 图卷积到底在对这些矩阵做什么把度矩阵和邻接矩阵弄明白以后图卷积就没那么神秘了。它的核心流程可以描述成三步第一步用邻接矩阵找到每个节点的邻居第二步把邻居的特征拿过来按权重求和权重就是邻接矩阵经过归一化之后的值第三步通过一个可学习的权重矩阵W做线性变换再经过激活函数。这就是为什么邻居、邻接矩阵、度矩阵是整套图算法的基础。而近几年出现的自适应图卷积本质上是希望不依赖手工设计的图结构让模型自己去学“节点之间应该连多强的关系”它依然离不开邻接矩阵和度矩阵这套底座。理解了基础再看那些进阶模型会轻松很多。6. 实操用 Python 把邻接矩阵和度矩阵完整算出来6.1 构造一个简单的图说再多理论都不如直接跑一遍代码。我们用networkx和numpy构建一个 6 个节点的无向图边集合模拟一个“朋友关系网”1-2、2-3、3-4、4-5、5-6、2-5、1-3。这样节点之间的度是会变化的方便观察。pip install networkx numpy6.2 用 NetworkX 计算邻接矩阵和度矩阵先看最直接的写法import networkx as nx import numpy as np G nx.Graph() edges [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (2, 5), (1, 3)] G.add_edges_from(edges) # 邻接矩阵 A_nx nx.to_numpy_array(G, nodelistsorted(G.nodes())) print(邻接矩阵 A:) print(A_nx) # 度矩阵 degrees dict(G.degree()) D_nx np.diag([degrees[n] for n in sorted(G.nodes())]) print(度矩阵 D:) print(D_nx)输出结果邻接矩阵 A: [[0. 1. 1. 0. 0. 0.] [1. 0. 1. 0. 1. 0.] [1. 1. 0. 1. 0. 0.] [0. 0. 1. 0. 1. 0.] [0. 1. 0. 1. 0. 1.] [0. 0. 0. 0. 1. 0.]] 度矩阵 D: [[2. 0. 0. 0. 0. 0.] [0. 3. 0. 0. 0. 0.] [0. 0. 3. 0. 0. 0.] [0. 0. 0. 2. 0. 0.] [0. 0. 0. 0. 3. 0.] [0. 0. 0. 0. 0. 1.]]可以看到节点 1 连接了 2 和 3所以度是 2节点 2 连接了 1、3、5所以度是 3。拿矩阵去跟图核对每一行非零元素的个数刚好等于度矩阵对角线的值。6.3 手写一个矩阵乘法的视角验证用 NetworkX 当然方便但为了加深理解我建议你也用纯 NumPy 手算一遍同样的图特别是把 GCN 里用到的对称归一化邻接矩阵也算出来A A_nx D_inv_sqrt np.diag(1.0 / np.sqrt(np.diag(D_nx))) # 防止除零如果某个节点度为 0diag 为 inf这里先忽略该情况 A_hat D_inv_sqrt A D_inv_sqrt print(对称归一化邻接矩阵 D^{-1/2} A D^{-1/2}:) print(np.round(A_hat, 4))输出里A_hat[0][1]的计算方法是A[0][1] / sqrt(D[0][0] * D[1][1])即1 / sqrt(2 * 3) ≈ 0.4082。这个数值描述的是节点 1 和节点 2 之间信息传递的强度两边的度越大这个值越小信息越容易被稀释。6.4 用代码排查一个常见坑在算D_inv_sqrt时如果某个节点是孤立节点度为 01.0 / np.sqrt(0)会出现inf后续矩阵计算就会全错。这种情况在真实数据里非常常见尤其是从大图里截取子图、过滤节点之后。处理办法是加一个安全项把度为 0 的节点对应位置设为 0d_inv_sqrt np.zeros_like(np.diag(D_nx)) nonzero_idx np.diag(D_nx) 0 d_inv_sqrt[nonzero_idx] 1.0 / np.sqrt(np.diag(D_nx)[nonzero_idx]) A_hat d_inv_sqrt A d_inv_sqrt这个细节看起来小但在实际数据流水线上能帮你省掉不少 Debug 时间值得养成习惯。7. 常见问题与排查技巧实录7.1 邻接矩阵的行列约定不一致不同框架、不同论文里对邻接矩阵的行列定义完全可能不一样。有的默认A[i][j]表示从i指向j有的则反过来。尤其是处理有向图时如果从开源代码里拿一个实现第一件事就是打印邻接矩阵的 shape 和浅层数值确认方向约定。否则后面模型学出来的结果可能完全相反。7.2 邻接矩阵内存爆炸怎么办我曾经处理过一个 50 万节点的图如果直接构造500000 x 500000的稠密邻接矩阵内存需要约 1.86TB这显然不现实。解决办法是使用稀疏矩阵。networkx.to_scipy_sparse_matrix(G)能直接生成scipy.sparse格式的邻接矩阵内存占用只跟边数相关而不是节点数平方。在做 GCN 训练时喂给 PyTorch Geometric 或者 DGL 的也应当是稀疏表示。7.3 孤立节点和零度节点怎么处理真实数据集中孤立节点很常见。当一个节点没有任何连边时它的度是 0在按度做归一化时会引发除零问题。解决思路有两个给孤立节点增加自环让度至少为 1或者像上面代码里做的那样用掩码把度为 0 的位置强制设成 0。选择哪种方式取决于业务目标如果只是做特征聚合通常不建议强制把孤立节点排除因为这样会丢失节点自身的特征信息。7.4 自环带来的矩阵变化如果图里已经有自环构建邻接矩阵时对角线就会有值这时再执行“加自环”操作A I会把原来自环权重翻倍。有些 GCN 实现没考虑到这一点导致带自环的输入结果不对。建议在预处理阶段统一约定算法层面需要自环就由预处理统一加上原始数据里自环要么保留并在计算时修正要么提前去掉。7.5 带权图的归一化细节带权图里邻接矩阵的非零值不等于 1而是边的权重。如果直接使用上面的对称归一化公式要先明确权重的含义是相似度还是距离相似度越大表示关系越紧可以直接套公式距离越大反而关系越弱通常需要做一次倒数变换1 / distance再放入邻接矩阵。很多推荐场景踩坑都踩在这里特征算出来完全没效果回头看大概率是权重含义没有对齐。7.6 看到别人的代码里出现 A_hat A I 代表的含义在 GCN 相关的开源代码里经常能看到把A加上单位矩阵I的操作。这个操作不是随便加的它的意思是给每个节点加一条指向自己的边也就是自环。这样在聚合邻居信息时节点会把自身的特征也当作一份“邻居”来加权避免多层传播后自身信息被完全稀释。度矩阵也要对应更新为D I否则归一化系数就不对了。理解这个小细节以后再去看代码里的预处理步骤就会非常顺畅。最后再分享一个小技巧如果你刚开始接触这些概念别直接上手大图和复杂模型先找一个三四节点的玩具图手动把邻接矩阵、度矩阵、拉普拉斯矩阵全部算一遍再用代码验证。这个过程我在带新人时反复推荐每次都能帮他们省下后面大量绕弯路的时间。矩阵符号看起来吓人但真正动手算一遍所有公式的直觉一下就建立起来了。
阅读完成 · 觉得有帮助？
