图表示与邻接矩阵

图 $G = (V, E)$ 用矩阵表示以便神经网络处理。邻接矩阵 $A \in \mathbb{R}^{n \times n}$: $A_{ij} = 1$ 表示节点 $i, j$ 有边(加权图可为任意权重); 度矩阵 $D = \mathrm{diag}(d_1, \ldots, d_n)$ 为对角阵, $d_i = \sum_j A_{ij}$ 是节点 $i$ 的度数。GNN 聚合前先加自环 $\tilde{A} = A + I$ 再对称归一化: $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$, 其元素形式为 $(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2})_{ij} = \frac{\tilde{A}_{ij}}{\sqrt{\tilde{d}_i \tilde{d}_j}}$——既保证传播不改变特征尺度, 又抑制“度大节点主导”(像社交网络大 V 的表示不被自身淹没)。图拉普拉斯 $L = D - A$(归一化 $\mathcal{L} = I - D^{-1/2}AD^{-1/2}$)满足 $x^T L x = \sum_{(i,j)\in E}(x_i - x_j)^2$, 特征值落在 $[0, 2]$, 是谱域 GCN 的出发点。任务分三类: 节点级(节点分类)、边级(链接预测)、图级(图分类/性质预测)。

社交网络、分子性质预测、推荐系统、知识图谱等非欧几里得数据的建模入口; 面试中作为 GNN 系列题的前置基础, 常被要求手写邻接/度矩阵、推导对称归一化的元素形式。

CNN/Transformer 假设规则的网格或序列结构, 无法直接处理任意拓扑的图。邻接矩阵把图结构编码为可参与矩阵乘法的张量; 对称归一化 $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ 使聚合权重与度数成反比(度大节点不被放大、度小节点不被忽略), 同时把特征值限制在有限范围, 保证多层传播数值稳定——这是 GCN/GAT 传播公式的直接基础。

检验攻克程度：针对「图表示与邻接矩阵」专属刷题排雷

做单选排雷题、推导选项机制，答错自动收录进专属错题本。