Graph Neural Networks (GNN / GAT): 解释 GNN 的消息传递框架。

Core Concept: 每层分三步：邻居发消息（message）、聚合（aggregate，置换不变）、更新自身（update）；堆叠 L 层即聚合 L 跳邻域。

数学机理：<strong>消息传递（Message Passing）框架</strong>——把 GNN 的所有变体统一为一个模板，每层对每个节点 v 执行三步：<strong>(1) 消息（message）</strong>——对每条边 (u,v)，用函数 M 从邻居 u 的特征 h_u 与边特征 e_uv 生成消息 m_{u→v}；<strong>(2) 聚合（aggregate）</strong>——把 v 的所有邻居消息聚合为一个向量，用<strong>置换不变</strong>的函数 AGG（sum / mean / max）；<strong>(3) 更新（update）</strong>——用函数 U 结合 v 自身特征 h_v 与聚合结果 m_v，得到新的 h_v。<strong>为什么聚合必须置换不变</strong>——图的邻居集合是<strong>无序</strong>的（节点编号是任意的），故聚合结果不应依赖邻居的排列顺序；sum/mean/max 都满足置换不变（而如'按顺序拼接'则不满足）。<strong>感受野</strong>——堆叠 L 层后，节点 v 的表示聚合了<strong>L 跳</strong>邻域的信息；故 L 层 GNN 可捕捉 L 跳的依赖（类似 CNN 的'感受野随层数增长'）。<strong>表达能力</strong>——Xu 等（GIN）证明：<strong>sum 聚合 + MLP</strong> 的表达能力等价于 <strong>1-WL 图同构测试</strong>（Weisfeiler-Lehman），即'能区分 1-WL 能区分的图'；mean/max 聚合的表达力弱于 sum（mean 无法区分'邻居数量'的差异、max 无法区分'多重性'）。<strong>这一'1-WL 上界'是 GNN 表达力的经典结论</strong>：存在不同的图（如某些正则图）无法被任何消息传递 GNN 区分，需更高阶的机制（如 k-WL、子图 GNN、位置编码）。<strong>读取（readout）</strong>——对图级任务，需把所有节点的表示聚合为图表示（用置换不变的池化）。

深度剖析与工程权衡：① <strong>'1-WL 上界'的实践含义</strong>——消息传递 GNN 无法区分某些结构不同的图（如两个不同结构的 3-正则图）；故在'需要区分复杂结构'的任务（如分子性质预测中的某些异构体）上受限。解法：(a) <strong>加位置/结构编码</strong>（如随机游走位置编码、拉普拉斯特征向量）——把结构信息注入节点特征，绕过 1-WL 限制；(b) <strong>高阶 GNN</strong>（k-WL、子图方法）；(c) <strong>图 Transformer</strong>（用注意力 + 位置编码）。② <strong>聚合函数的选择</strong>——sum 表达力最强（保留多重性）、mean 适合'邻居数不定'的场景、max 适合'关注最显著邻居'；实践中常组合或按任务选。③ <strong>过平滑（over-smoothing）</strong>——层数增加会使所有节点的表示趋于相同（因为反复的邻域平均），故 GNN 通常只有 2~4 层（见后续题）。④ <strong>与 Transformer 的关系</strong>——Transformer 可视为'<strong>全连接图上的注意力 GNN</strong>'（每个 token 与所有 token 相连，聚合用加权和、权重依内容计算）；反之 GNN 可视为'稀疏图 + 固定/学习权重'的注意力。这一统一视角很有价值。⑤ <strong>与 MoE 的类比</strong>——MoE 是'按内容选择专家'、GNN 是'按图结构选择邻居'；都是'稀疏的、结构化的信息聚合'。⑥ <strong>面试要点</strong>——被问'GNN 是什么'，应给出'<strong>message-aggregate-update 三步 + 置换不变聚合 + L 层 = L 跳感受野</strong>'，并主动提到'<strong>sum 聚合 + MLP ≈ 1-WL 上界</strong>'这一经典结论；能说明'Transformer = 全连接图注意力 GNN'是深度理解的标志。