图表示与邻接矩阵

图 $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 传播公式的直接基础。

写出邻接矩阵 $A$ 与度矩阵 $D$ 的定义($A_{ij}$, $d_i = \sum_j A_{ij}$), 自环 $\tilde{A} = A + I$ 为什么是 GNN 的必要操作?

推导对称归一化 $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ 的元素形式 $\frac{\tilde{A}_{ij}}{\sqrt{\tilde{d}_i \tilde{d}_j}}$, 并解释它为什么能避免度大节点主导聚合结果。

图拉普拉斯 $L = D - A$ 与归一化拉普拉斯 $\mathcal{L} = I - D^{-1/2}AD^{-1/2}$ 的性质: 二次型 $x^T L x = \sum_{(i,j)}(x_i - x_j)^2$ 与特征值范围 $[0, 2]$ 的含义。

图任务的三大层级(节点级/边级/图级)各举一例, 各自的预测目标与常用 loss 形式是什么?

如何扩展基本矩阵表示: 加权图、有向图(非对称 $A$)、异质图(多类型边)以及超大图的邻接矩阵稀疏存储?