Implicit Graph Neural Networks
https://proceedings.neurips.cc/paper/2020/file/8b5c8441a8ff8e151b191c53c1842a38-Paper.pdf
摘要
图神经网络(GNN)是广泛使用的深度学习模型,可从图结构数据中学习有意义的表示。
由于底层循环结构的有限性,当前的GNN方法可能难以捕获底层图的长程依赖关系。
为了克服这个困难,我们提出了一种称为隐式图神经网络(IGNN)的图学习框架,其中的预测是基于关于隐式定义的“状态”的不动点平衡方程的解。
我们使用Perron-Frobenius理论得出框架适定的充分条件。
利用隐式微分,我们导出了一种可行的投影梯度法来训练框架。
在广泛的任务上进行的实验表明,IGNN 能够持续捕获远程依赖关系,并且性能优于最新的GNN模型。
文章贡献
在这项工作中,我们提出了隐式图神经网络(IGNN)框架,以解决循环GNN的评估和训练问题。
我们首先通过基于Perron-Frobenius理论的严格数学框架来分析图神经网络(Berman and Plemmons,1994),以建立收敛的一般适定性条件。
我们证明大多数现有分析都是我们结果的特例。
在训练方面,我们提出了一种投影梯度法来有效地训练 IGNN,其中我们利用隐式微分方法来获得精确的梯度,并在易处理的凸集上使用投影来保证适定性。
我们表明,以前的递归图神经网络梯度方法可以解释为IGNN的近似值。
此外,我们将IGNN扩展到异构网络的情形。
最后,我们与现有方法进行了全面的比较,并证明了我们的方法可以有效地捕获远程依赖关系,并且在各种任务上均优于最新的GNN模型。
IGNN
注
- 不动点方程 (2b) 可以视为将图卷积执行无限次后的收敛状态
- W , b Ω , f Θ W, b_{\Omega},f_{\Theta} W,bΩ,fΘ 是待学习的
- 对于任意的 ϕ , W \phi, W ϕ,W,给定输入 U U U,不动点可能不唯一
- 作者给出了保证不动点唯一的充分条件:
- 充分条件实际上是对
W
W
W 的一个约束条件,但是由于 PF特征值 是个非凸函数,进一步把它改成更严格的对无穷诱导范数
∥
W
∥
∞
\|W\|_{\infty}
∥W∥∞ 的约束,然后用投影梯度法来求解带约束的优化问题
- Perron-Frobenius 定理
每个非负方阵 M M M 都有一个实的非负特征值,该值在 M M M 的所有特征值中具有最大的模. M M M 的该非负特征值称为 Perron-Frobenius 特征值