🧠 IJCAI-20 · 图神经架构搜索开山之作

Graph Neural Architecture Search
用强化学习自动搜索最优图神经网络架构

Gao, Yang · Yang, Hong · Zhang, Peng · Zhou, Chuan · Hu, Yue · CAS · UTS · 蚂蚁集团

IJCAI-20 中科院 · 悉尼科大 · 蚂蚁集团 GitHub: GraphNAS/GraphNAS

📋 论文基本信息

标题Graph Neural Architecture Search
作者Yang Gao, Hong Yang, Peng Zhang, Chuan Zhou, Yue Hu
机构中科院信工所 · UTS · 蚂蚁集团 · 中科院数学与系统科学研究院 · 国科大
发表IJCAI-20 (International Joint Conference on Artificial Intelligence)
代码github.com/GraphNAS/GraphNAS
标签 Graph Neural Network NAS Reinforcement Learning Policy Gradient GNN Architecture Search

We present GraphNAS, a graph neural architecture search method that enables automatic design of the best graph neural architecture based on reinforcement learning. GraphNAS uses a recurrent network to generate variable-length strings describing GNN architectures, and trains it with policy gradient to maximize expected accuracy on a validation set. Experiments show GraphNAS can design architectures rivaling the best human-invented ones, with strong transfer learning performance.

💡 背景与动机：GNN设计为什么需要自动化？

图神经网络（GNN）已经成为分析社交网络、推荐系统、交通预测等非欧几里得数据的强大工具。GCN、GraphSAGE、GAT、APPNP等模型在各自的任务上表现出色，但它们的共同问题是：架构设计严重依赖人工经验和领域知识。

与CNN类似，GNN也有大量需要手动调节的架构参数：

  • 邻居采样策略：一阶？高阶？固定大小？
  • 消息计算函数：gcn？gat？cos？linear？gate？
  • 信息聚合方式：sum？mean？max？mlp？
  • 多头注意力头数：1？4？8？16？
  • 输出维度、激活函数：512+relu？64+elu？

在此之前，NAS（神经架构搜索）已经在CNN和RNN上取得了巨大成功——NAS（Zoph & Le, 2016）用RNN作为控制器生成网络架构描述，用策略梯度最大化验证集准确率。ENAS、DARTS、ProxylessNAS等进一步提升了搜索效率。然而，将NAS引入GNN领域并非简单搬运，因为GNN的搜索空间与CNN有本质区别——它涉及图拓扑特有的采样、消息传递和聚合操作。

⚠ 核心挑战：GNN架构的搜索空间比CNN更复杂：每个算子组合形成 9408L 种可能，仅仅2层就达到 8.8×107 的搜索空间。如何设计合理的搜索空间、如何在有限计算资源下高效搜索，是GraphNAS要解决的核心问题。

🔧 核心方法：GraphNAS框架

GraphNAS的整体框架清晰优雅，分为三个核心组件：搜索空间、控制器（Controller RNN） 和 策略梯度训练。

📌 3.1 搜索空间设计

GraphNAS设计的搜索空间覆盖了主流GNN模型的核心操作算子：

// 搜索空间 M 的四大类算子 // 1️⃣ 邻居采样 (Smpl) —— 选择感受野 采样方式: first_order // 2️⃣ 消息计算 (Func) —— 计算节点间相关性的相关系数 e_uv 相关系数 e_uv: const : e_uv = 1 // 常数 gcn : e_uv = 1/sqrt(d_u * d_v) // 对称归一化 gat : e_uv = LeakyReLU(W_l*h_u + W_r*h_v) // 注意力 cos : e_uv = <W_l*h_u, W_r*h_v> // 余弦相似度 linear : e_uv = tanh(sum(W_l*h_u)) // 线性变换 gate : e_uv = W_a * tanh(W_l*h_u + W_r*h_v) // 门控线性 // 3️⃣ 信息聚合 (Aggr) —— 聚合邻居信息 聚合方式: sum | mean | max | mlp // 4️⃣ 多头与读出 (Read) —— 多头注意力 + 信息融合 Readout: avg (最后一层) | concat (中间层) // 另外：激活函数 σ, 头数 k, 输出维度 d

以一层GAT为例，一个完整的架构描述为：

// 1层 GAT: 一阶采样 + gat消息 + sum聚合 + concat读出 + 8头 + 16维 + elu激活 [first_order, gat, sum, concat, 8, 16, elu]

📌 3.2 控制器：用RNN生成架构

GraphNAS使用LSTM/RNN作为控制器（Controller），按序列生成每个算子的选择：

h₀ → → Smpl → → Func → → Aggr → → σ

具体来说，在每个时间步 i，控制器根据前一步的隐藏状态 hi-1 输出一个softmax分布 Pi，然后从中采样得到算子 mi。所有算子依次生成后构成一个完整的架构描述 m1:T。

📌 3.3 策略梯度训练

生成的子模型 m 在目标图 G 上训练并在验证集 D 上评估，验证准确率作为奖励信号 RD(m)。由于奖励不可微，使用REINFORCE算法更新控制器参数：

// REINFORCE 策略梯度更新 ∇J(θ) = Σt E[ ∇log P(mt|mt-1:1; θ) · (R - b) ] // b = 指数移动平均的历史架构奖励（baseline降方差）

子模型的训练与控制器训练完全独立——每次采样出一个架构后，从头训练该模型并使用分类交叉熵loss。为了降低方差，选取验证准确率最高的 K 个候选模型，重复训练 N 次，选最优架构。

✅ 关键设计：控制器 + 独立子模型训练 + REINFORCE + 奖励baseline + Top-K筛选。这个框架将NAS从CNN/RNN领域成功迁移到了GNN领域。

🏗️ 深层架构扩展：如何处理大图和多层？

当架构层数增加时，搜索空间呈指数级爆炸：9408L 种组合。GraphNAS提出了分层独立搜索策略：

📌 独立层设计假设

核心洞察：GNN各层的操作可以近似视为相互独立。因此，可以将搜索空间从整个架构空间降维到每个单层空间，先逐层搜索最优配置，再顺序拼接得到完整架构。

// 3层GNN架构 = 逐层最优的拼接 层1 最优: [first_order, gcn, sum, concat, 1, 16, relu] 层2 最优: [first_order, gat, sum, avg, 8, 16, elu] 层3 最优: [first_order, gat, sum, avg, 4, 32, relu] 最终架构 = 层1 + 层2 + 层3

📌 DAG层结构表示

对于每层的内部结构，GraphNAS使用DAG（有向无环图）来建模。层由输入状态、中间计算节点和输出状态组成：

O₁ → → O₅ Read(ADD)
O₂ → GAT(O₂) → O₅

其中：

  • O1、O2 是输入状态（前一层的输出）
  • O3、O4 是中间计算节点，每个节点包含 Smpl + Func + Aggr
  • O5 = σ(Read([O3, O4])) 是输出状态

可选的12种计算算子包括：identity, zeroize, GAT(1-8头), GCN, Chebnet, Mean SAGE, ARMA, SGC。

📊 实验与结果

基准数据集上的节点分类

84.0%
Cora准确率
72.6%
Citeseer准确率
80.2%
Pubmed准确率

在Cora、Citeseer、Pubmed三个经典引文网络上，GraphNAS搜索出的架构在验证集准确率上均超越了手工设计的GCN、GAT、GraphSAGE等基线模型。尤其在Cora上，GraphNAS设计的架构在保持GAT注意力机制优势的同时，自动选择了最优的头数和隐藏维度配置。

📌 关键发现：GraphNAS搜索出的架构并非简单复刻现有的GCN/GAT——它倾向于选择多头注意力 + 门控机制的组合，而这在之前的人工设计空间中没有被充分探索。

迁移学习能力

>SOTA
MS-CS/MS-Physics
>SOTA
Amazon Computers/Photos
✓ Transfer
Cora→新数据集

更有趣的是：将在Cora上搜索到的最优架构，直接迁移到其他数据集（MS-CS学术合作网络、Amazon产品网络）时，依然取得了超越SOTA的表现。这表明GraphNAS找到的架构具有跨数据集的泛化能力，而不仅仅是过拟合到特定数据集。

✅ 迁移学习的启示：一个好的GNN架构设计包含某种"通用设计模式"——注意力机制、跳跃连接、聚合函数的选择，这些设计规律可以跨数据集迁移。

搜索效率对比

GraphNAS设定搜索深度为2层（搜索空间 8.8×107），在大图上使用分层的独立搜索策略避免指数爆炸。搜索过程在大约几小时到一两天内完成（取决于图规模），与手工调参的时间成本相比具有显著优势。

// 搜索空间规模估算 1层组合数: 9408 2层组合数: 9408² ≈ 8.85 × 10⁷ L层组合数: 9408L ← 需要分层搜索策略 // 分层搜索策略 层数 > 2 时，将搜索空间分解为 L 个单层子问题 每层最优结果顺序拼接

代码已开源在 GitHub，为后续GNAS研究提供了重要的基准平台。

🌊 历史影响与后续发展

GraphNAS是第一篇将NAS系统性地引入GNN领域的工作，其IJCAI-20的发表标志着图神经架构搜索（GNAS）这一子领域的正式确立。后续工作在其基础上取得了重要进展：

2020 · GraphNAS (IJCAI-20)
用强化学习自动搜索GNN架构，定义GNAS问题框架和搜索空间。
2020 · DARTS变体 (Auto-GNN)
基于可微搜索方法（DARTS）的GNN架构搜索，大幅提升搜索效率。
2021 · GNAS综述论文
多个综述系统总结GNAS方法，包括RL-based、进化-based、可微-based三类。
2024-2025 · GNAS-LLM
用大语言模型代替RL控制器来搜索GNN架构，仅需15轮迭代即可找到最优架构。
📌 值得注意：这篇论文的第三作者张鹏（Peng Zhang）来自蚂蚁集团，中科院背景——这在GNAS-LLM等后续工作中也有持续的研究贡献。20年从RL-based GNAS到24-25年的LLM-based GNAS，这条研究路线的演进非常清晰。
✅ 学术贡献总结：
1. 首次将NAS引入GNN领域，定义了GNAS的问题框架
2. 设计了覆盖主流GNN操作子的通用搜索空间
3. 提出了分层搜索策略解决深层GNN的搜索爆炸问题
4. 实验证明自动搜索的架构可超越人工设计，且具有迁移能力

🎯 对AI研究生的启示

对于从事图神经网络或自动化机器学习研究的同学，这篇论文有几个值得深思的设计哲学：

  • 跨领域移植要思考差异：GraphNAS并非简单套用NAS到GNN——它针对GNN特有的采样-消息-聚合三层结构设计了专门的搜索空间。如果只是把CNN的NAS拿来用而不做适配，效果会大打折扣。这提醒我们：方法论迁移时，一定要深入理解目标领域的具体操作语义。
  • 搜索空间设计决定上限：无论控制器多强，如果搜索空间没有覆盖好的架构，永远搜不出好结果。GraphNAS的搜索空间涵盖了GCN、GAT、GraphSAGE等6种相关函数和多种聚合方式——这是一个高质量的搜索空间封装。
  • 好的研究问题=现有热门领域+未被满足的需求：NAS在CNN/RNN上成功，GNN正在快速发展——但GNN架构设计还需要大量手工和领域知识。这两者的结合点就是GraphNAS的研究空间。对于研究生选题，这种交叉地带往往产出高质量工作。
  • 效率问题总是伴随扩展性出现：当架构加深时搜索空间指数爆炸，GraphNAS提出了

总的来说，GraphNAS是一篇简洁、清晰、开创性的工作。它的影响力不仅在于提出了一种搜索方法，更在于定义了GNAS这个研究方向，为后续大量工作提供了基准和起点。对于想要进入图神经网络或AutoML领域的同学，这是一篇值得精读的基础文献。