Nonparametric Teaching for Graph Property Learners¶

会议: ICML2025
arXiv: 2505.14170
代码: 项目主页
领域: 优化 / 图学习
关键词: 非参数教学, 图卷积网络, 训练效率, 图神经切线核, 贪心样本选择

一句话总结¶

提出 GraNT 范式，将非参数教学理论拓展到图属性学习场景，通过贪心选择"预测偏差最大"的图样本子集来加速 GCN 训练，在保持泛化性能的同时将训练时间缩减 30%–47%。

研究背景与动机¶

核心问题: 图卷积网络 (GCN) 学习图到属性的隐式映射 $f^*: \mathbb{G} \mapsto \mathcal{Y}$ 代价高昂，尤其在大规模图（百万节点、数十万分子图）上训练开销巨大。
已有方案不足: 已有的训练加速方法（归一化、图分解、惰性更新等）多从网络架构/工程角度出发，缺乏系统的理论框架；已有的非参数教学理论仅适用于规则特征数据（如 MLP + 坐标→信号），未考虑输入的图结构信息。
理论鸿沟: GCN 在参数空间做梯度下降，而非参数教学在函数空间做泛函梯度下降，两者之间存在 gap——邻接矩阵 $\mathbf{A}$ 的特征聚合如何影响参数梯度、动态 GNTK 能否收敛到泛函梯度中的结构感知核，尚未被回答。
本文动机: 系统分析图结构对参数梯度的影响，证明 GCN 的参数梯度下降演化与泛函梯度下降一致，从而将非参数教学理论合法地引入图属性学习，用贪心教学算法提升训练效率。

方法详解¶

整体框架: Graph Neural Teaching (GraNT)¶

GraNT 引入一个 teacher-learner 范式： 1. 目标映射 $f^*$ 由一组稠密的图-属性对实现； 2. Teacher 每轮从训练集 $\{(\mathbf{G}_i, \mathbf{y}_i)\}_N$ 中贪心选出子集 $\{G_i\}_m^*$（$m \leq N$）； 3. Learner（GCN）仅在被选子集上做参数梯度下降更新。

关键设计 1: 结构感知参数梯度分析¶

论文采用灵活 GCN 公式，将不同卷积阶的聚合特征分别赋权：

\[\mathbf{X}^{(\ell)} = \sigma\!\left(\mathbf{A}^{[\kappa_\ell]} \operatorname{diag}(\mathbf{X}^{(\ell-1)}; \kappa_\ell) \cdot \mathbf{W}^{(\ell)}\right)\]

其中 $\mathbf{A}^{[\kappa]} = [\mathbf{I}, \mathbf{A}, \dots, \mathbf{A}^{\kappa-1}]$ 将不同阶邻居聚合拼接。论文解析推导了两层 GCN 输出对各层权重的梯度表达式（Eq. 13, 17），发现： - 参数梯度不依赖图的节点数 $n$，仅依赖特征维度和卷积阶数； - 当卷积阶 $\kappa=1$ 时退化为 MLP 梯度，说明本文是 MLP 非参数教学的推广。

关键设计 2: GCN 演化与泛函梯度的一致性¶

将参数更新转化为 GCN 在函数空间的演化：

\[\frac{\partial f_{\theta^t}}{\partial t} = -\frac{\eta}{N} \sum_i \frac{\partial \mathcal{L}}{\partial f_{\theta^t}(\mathbf{G}_i)} \cdot K_{\theta^t}(\mathbf{G}_i, \cdot) + o(\cdot)\]

其中 $K_{\theta^t}(\mathbf{G}, \mathbf{G}') = \langle \frac{\partial f_{\theta^t}(\mathbf{G})}{\partial \theta^t}, \frac{\partial f_{\theta^t}(\mathbf{G}')}{\partial \theta^t} \rangle$ 为动态图神经切线核 (GNTK)。

定理 5 (核心理论结果): 对凸损失 $\mathcal{L}$，动态 GNTK 逐点收敛到结构感知的 canonical kernel： $$\lim_{t\to\infty} K_{\theta^t}(\mathbf{G}_i, \cdot) = K(\mathbf{G}_i, \cdot)$$

这首次证明了 GCN 参数梯度下降的演化与非参数教学中泛函梯度下降一致。

关键设计 3: 贪心教学选择策略¶

基于 Proposition 6（充分损失下降保证），GraNT 选择 GCN 预测偏差最大的图：

\[\{\mathbf{G}_i\}_m^* = \arg\max_{\{\mathbf{G}_i\}_m \subseteq \{\mathbf{G}_i\}_N} \| [f_\theta(\mathbf{G}_i) - f^*(\mathbf{G}_i)]_m \|_2\]

两种实现变体： - GraNT (B): 选择平均偏差最大的 batch； - GraNT (S): 从每个 batch 中按比例选偏差最大的单个图，重组为新 batch。

节点级任务需要对节点数归一化：选择 $\|f_\theta(\mathbf{G}_i) - f^*(\mathbf{G}_i)\|_2 / n_i$ 最大的图。

实验关键数据¶

主实验: 训练时间与测试性能 (Table 1)¶

数据集	任务	无GraNT时间(s)	GraNT(B)时间(s)	加速比	性能保持
QM9	图级回归	9654.81	6392.26	-33.79%	MAE 0.0051 不变
ZINC	图级回归	33033.82	20935.24	-36.62%	MAE 0.0048 不变
ogbg-molhiv	图级分类	2163.50	1457.39	-32.64%	ROC-AUC 0.7572→0.7676↑
ogbg-molpcba	图级分类	130191.26	80465.06	-38.19%	AP 0.3270→0.3358↑
gen-reg	节点级回归	3344.78	2308.97	-30.97%	MAE 0.0007 不变
gen-cls	节点级分类	11662.25	6145.72	-47.30%	ROC-AUC 0.9150→0.9157↑

与 SOTA 方法对比¶

QM9 对比 Active Learning 方法 (Table 2):

方法	时间(s)	MAE
AL-3DGraph (默认设置)	12601.77	0.1682
GraNT (B)	6392.26	0.0051

GraNT 时间减半且 MAE 降低两个数量级。

ogbg-molhiv 对比高效 GNN 方法 (Table 3):

方法	时间(s)	ROC-AUC
GCN	2888.80	0.7385
GDeR-PNA	5088.88	0.7616
GraNT (B)	1457.39	0.7676
GraNT (S)	1597.69	0.7705

消融与发现¶

GraNT (B) vs GraNT (S): (B) 更快（省去 batch 拆分重组开销），两者性能相当；(S) 在部分分类任务上 ROC-AUC 略高。
收敛速度: 验证集 loss/MAE 曲线显示 GraNT 跨度约为 baseline 的 2/3，下降速率更快。
不平衡标签影响: ogbg-molhiv 和 gen-cls 的 ROC-AUC 曲线因标签不平衡呈锯齿状，但 GraNT 持续优于 baseline。
无限宽 vs 有限宽: 论文考虑实际有限宽 GCN 下的动态 GNTK，而非理想无限宽假设。

亮点与洞察¶

理论贡献突出: 首次证明了 GCN 参数梯度下降与泛函梯度下降的一致性（Theorem 5），将非参数教学理论从规则数据推广到图结构数据。
选择策略极简高效: 贪心策略仅需比较预测偏差大小，无需计算核范数，额外开销极小。
效果全面: 覆盖图级/节点级 × 回归/分类四种场景，六个数据集一致有效，加速 30%–47%。
理论完备: 从结构感知梯度分析 → GNTK 收敛性 → 充分损失下降保证，形成完整理论链条。
与 MLP 非参数教学的优雅统一: 卷积阶 $\kappa=1$ 时完美退化为 MLP 教学。

局限与展望¶

仅验证 GCN: 未扩展到 GAT、GIN 等其他图神经网络，作者在结论中也承认这是未来工作。
选择比例 $m/N$ 的敏感性: 论文未详细分析选择比例如何影响加速比与性能的权衡。
节点级实验仅用合成数据: gen-reg/gen-cls 由 graphon 生成，缺乏真实大规模节点级 benchmark（如 ogbn-*）。
理论依赖凸损失假设: Theorem 5 和 Proposition 6 都要求凸损失，实际中交叉熵等损失关于 $f_\theta$ 的凸性需仔细对待。
动态 GNTK 收敛速度: 论文证明了极限收敛但未给出收敛速率，有限训练步数下的近似精度未知。

评分¶

新颖性: ⭐⭐⭐⭐ (首次将非参数教学拓展至图属性学习，理论贡献扎实)
实验充分度: ⭐⭐⭐⭐ (六个数据集四种任务，但节点级缺真实 benchmark)
写作质量: ⭐⭐⭐⭐ (理论推导完整，动机清晰，符号稍重)
价值: ⭐⭐⭐⭐ (30%–47% 加速 + 理论框架，对图学习训练效率有启发)