论文题目Principal Neighbourhood Aggregation for Graph Nets图网的主邻域集结会议NeurIPS 2020摘要图神经网络(GNN)已被证明是针对图结构数据的不同预测任务的有效模型。最近对它们的表达能力的研究主要集中在同构任务和可数特征空间上。我们将这一理论框架扩展到包括连续特征--这些特征经常出现在真实世界的输入域和GNN的隐藏层中--并在此背景下演示了对多个聚集函数的需求。因此我们提出了主体邻域聚合(PNA)这是一种将多个聚集器和度缩放器(推广了和聚集器)相结合的新型体系结构。最后我们通过一个新的基准测试来比较不同模型捕获和利用图结构的能力该基准测试包含来自经典图论的多个任务以及来自真实世界领域的现有基准测试所有这些都证明了我们的模型的优势。通过这项工作我们希望引导GNN的一些研究转向新的聚集方法我们认为这些方法对于寻找强大和健壮的模型是必不可少的。图神经网络的聚合困境与破局之道Principal Neighbourhood Aggregation (PNA) 详解一、论文背景GNN 的表达力瓶颈在哪里图神经网络Graph Neural Networks, GNNs近年来在分子化学、社交网络、计算机视觉等领域取得了显著进展。然而学界对 GNN 的理解存在两个明显的短板缺乏标准化的 benchmark现有评测体系无法有效区分不同模型在理解图结构方面的真实能力。表达力分析局限于离散空间已有的理论工作如 Xu et al. 2018 的 GIN 论文主要研究可数特征空间countable feature space下的同构判别问题而真实世界的节点特征往往是连续的。论文的核心假设是现有 GNN 的聚合层在单层中无法从邻域中提取足够的信息这是限制其表达力和学习能力的根本原因。二、论文指出的核心问题2.1 单一聚合函数的根本缺陷目前主流 GNNGCN、GAT、GIN、MPNN 等几乎都只使用一种聚合方式——mean、sum 或 max。论文通过理论证明和直观示例揭示了这一做法的致命缺陷对于连续特征空间任何单一聚合函数都无法区分所有不同的邻域消息多重集multiset。【论文 Figure 1不同聚合器在连续特征空间下无法区分邻域消息的示例图】如图所示对于两个节点 v它们的邻域节点消息虽然不同但在使用 Mean、Min、Max 或 STD 单个聚合器时各自都存在无法被区分的情况。只有组合使用多种聚合器才能将所有案例区分开来。2.2 现有理论框架的局限性Xu et al. [GIN] 证明了在可数特征空间下sum 聚合是单射injective的因而具有最强表达力。然而这一结论在连续特征空间下不再成立——论文严格证明了 sum 聚合在连续输入下同样无法保证单射性。这一问题在实际应用中尤为重要因为真实世界的观测值如分子的物理化学属性本身带有不确定性天然是连续的GNN 的隐层表示hidden representation也是连续值。三、论文的核心创新点3.1 理论贡献多聚合器必要性的严格证明定理 1所需聚合器数量要区分底层集合为实数 ℝ 的大小为 n 的多重集至少需要 n 个聚合器。证明思路利用了Borsuk-Ulam 定理若仅用 n-1 个连续函数聚合器对 n 维欧氏空间的子集进行映射必然存在两个不同的多重集被映射到同一输出从而无法区分。命题 1多重集的矩作为合法示例多重集的各阶矩均值、方差、偏度、峰度……提供了一组满足上述要求的 n 个聚合器的具体构造。定理 2可数多重集上的单射函数均值聚合与任何关于邻域大小的单射缩放函数的组合可以在有界可数多重集上生成单射函数。这将 Xu et al. 关于 sum 聚合器的结论推广为一个更一般的框架sum 只是均值 × 线性度缩放的特例而任何单射缩放函数均可满足需求。3.2 方法贡献四种互补聚合器PNA 使用以下四种聚合器它们捕捉邻域消息分布的不同统计特性聚合器公式作用均值Mean最常用衡量邻域平均信号最大值Max适合离散任务信用分配外推最小值Min与 Max 互补标准差STD衡量邻域信号的多样性/离散程度此外论文还提出了归一化矩聚合器Normalized Moments通过 n 次根归一化保证数值稳定性可扩展到偏度n3、峰度n4等高阶统计量适用于节点度数较高的场景。3.3 方法贡献度缩放器Degree-based Scalers单纯使用上述聚合器仍然无法区分特征相同但邻域大小不同的节点如 2 个邻居各发来消息 1.0与 4 个邻居各发来消息 1.0mean 结果相同。PNA 引入了度缩放器来解决这一问题它是节点度数的函数对聚合结果进行放大或衰减线性放大即 sum 的等价形式然而 sum 聚合在外推到更大图时泛化性差——每层线性放大最终导致多层后的指数级放大。因此PNA 使用对数缩放其中是在训练集上计算的归一化参数为放大为衰减为恒等变换。对数缩放的直觉很自然在社交网络中拥有 500 万、100 万和 10 万粉丝的节点在线性尺度上差距悬殊但在对数尺度上更能反映它们的影响力梯度。3.4 PNA 的完整架构聚合器 × 缩放器的张量积PNA 将 4 个聚合器mean、max、min、std与 3 个缩放器恒等、放大、衰减进行张量积组合每层共产生12 种操作整体 GNN 层更新公式为其中 M 和 U 为神经网络线性层即可U 将的拼接消息压缩回。【论文 Figure 2PNA 结构示意图展示多聚合器→缩放器→MLP 的流程】这一设计类比于 CNN 的 3×3 卷积核使用 9 个权重而非 1 个是因为每个位置的空间关系不同同理GNN 也应对每个邻居的消息使用多种视角。3.5 架构贡献编码-处理-解码框架论文提出了一种参数高效的encode-process-decode 架构GRU门控循环单元在每层更新函数后使用防止过度平滑有效保留前层信息权重共享除第一层外所有 GNN 层共享参数大幅降低参数量可变深度 M推理时根据输入图的大小动态决定卷积层数适应高方差的图分布。【论文 Figure 3架构示意图展示 GC₁ → GRU → GCₘ × (M-1) → MLP/S2S 的流程】四、评测设计多任务图论 Benchmark为了真正衡量 GNN 对图结构的理解能力论文构建了一个包含多任务的合成 benchmark而非单一任务。4.1 图的生成benchmark 包含 10 种随机图类型Erdős-Rényi、Barabási-Albert、Grid、Caveman、Tree、Ladder、Line、Star、Caterpillar、Lobster每种图拥有不同的拓扑特性图的节点数为 15~50。4.2 六项任务节点级 图级节点级任务3项单源最短路径长度离心率Eccentricity拉普拉斯特征LX其中 L D - A图级任务3项4.图的连通性5.图的直径6.图的谱半径这些任务都基于经典图论算法天然适合 GNN 的消息传递范式。多任务设置的优势在于模型必须同时理解图的多种结构属性并通过参数共享体现对图结构的深层理解。五、实验结果5.1 多任务合成 BenchmarkPNA 全面领先【论文 Figure 4多任务 benchmark 结果(a) 各模型 log₁₀MSE 分布箱线图(b) 各任务平均 log₁₀MSE 详细表格】如图所示PNA 在所有六项任务上均取得最低误差最负的 log₁₀MSE平均得分为-3.13远超排名第二的 MPNN(max) 的 -2.53。关键发现缩放器的贡献不可忽视PNA无缩放器的平均分为 -2.77与完整 PNA 相比差距明显说明度缩放器带来了显著提升。性能提升不来自参数量PNA 参数量仅比其他模型多约 15%。论文在附录 K 中将其他模型参数量提升 30%隐层从 16 扩大到 20结果仍然无法接近 PNA 的性能证明提升是质的而非量的。【论文 Figure 11参数量对比实验PNA8350参数vs 其他模型扩大到20维特征后的对比表格】5.2 外推实验更大图上的泛化性在更大的图上训练 15~25 节点测试 20~50 节点所有模型性能均有下降部分模型出现特征爆炸。但 PNA 在所有图大小上始终保持领先。【论文 Figure 5不同模型在不同大小图上的 log₁₀ MSE 比率折线图】此外在单一聚合器中max 聚合在外推到大图时表现最好与已有研究结论一致。5.3 不同图类型上的分析【论文 Figure 8各模型在 10 种图类型上的平均 log₁₀MSE 表格】PNA 在所有图类型上均优于其他模型但在高直径图如 Line 图上表现相对较弱——这是因为有限层数的消息传递无法覆盖到图的全局这是消息传递框架本身的局限而非 PNA 特有的问题。5.4 真实世界 Benchmark化学与计算机视觉论文在四个真实世界数据集上进行评测数据集任务指标ZINC分子属性预测MAE越低越好MolHIV分子HIV活性分类ROC-AUC越高越好CIFAR10图像分类图结构AccuracyMNIST手写数字图结构Accuracy【论文 Figure 6真实世界 benchmark 完整结果对比表涵盖 ZINC、CIFAR10、MNIST、MolHIV 四个数据集】主要结论化学数据集ZINC、MolHIVPNA 大幅领先所有对比方法。ZINC有边特征MAE 达到0.188优于 GatedGCN 的 0.363 和 MPNN(sum) 的 0.288。MolHIV ROC-AUC 达到79.05%优于 GCN 的 76.06%。这与论文的理论预期一致化学分子图的结构高度多样边特征化学键对图结构影响显著正是 PNA 设计所针对的场景。计算机视觉数据集CIFAR10、MNISTPNA 提升幅度相对有限。原因在于这类数据集将图像转换为规则图每个节点有固定 8 条边图结构对任务的贡献较小MLP 的高基线性能即为佐证。值得注意的是在此场景下PNA 无缩放器版本反而略优于完整版因为恒定的节点度使缩放器变得冗余。5.5 高阶矩消融实验【论文 Figure 7不同数量矩聚合器1阶到5阶与完整 PNA 的消融实验箱线图】随着矩的阶数增加模型的表达能力先升后降增加到约 3 阶时性能最优继续增加会导致优化困难和过拟合。完整 PNA使用 mean、max、min、std 而非纯矩聚合器表现最优且最稳定说明离散聚合器max、min对算法类任务尤为重要。六、总结论文贡献一览维度具体内容理论将 GNN 表达力分析扩展到连续特征空间证明多聚合器的必要性推广 sum 聚合为对数度缩放的一般框架方法提出 PNA4 种统计聚合器 × 3 种度缩放器的组合编码-处理-解码参数高效架构评测构建覆盖 6 项图论任务的多任务 benchmark在合成和真实数据上全面超越 SOTA核心洞见PNA 的成功可以用一句话概括一个节点要真正理解它的邻域不仅需要知道平均信号是什么mean还需要知道极端值max/min、分布的离散程度std以及邻居的数量度缩放器。这四个维度共同构成对邻域分布的完整统计描述。局限性与未来方向在高直径图上表现受限根本原因是消息传递框架的深度约束模型在未见过的图分布上仍有性能下降分布外泛化需进一步研究对于节点度极高的图如社交网络更高阶矩可能带来更多收益值得探索。