Convergence of Invariant Graph Networks
Convergence of Invariant Graph Networks
复制标题
DOI：
--
复制
发表时间：
2022-01
期刊：
影响因子：
--
通讯作者：
Chen Cai;Yusu Wang
中科院分区：
文献类型：
--
作者：
Chen Cai;Yusu Wang
虽然图神经网络的表达能力和过平滑等理论性质近年来得到了广泛的研究，但其收敛性是一个相对较新的研究方向。在本文中，我们研究了一个强大的GNN，不变图网络（IGN）的收敛性从图子采样的图。我们首先证明了稳定的线性层一般$k$-IGN（阶$k$）的基础上一个新的解释线性等变层。在此基础上，我们证明了$k$-IGN在\citet{ruiz 2020 graphon}模型下的收敛性，其中我们访问边权重，但收敛误差是针对graphon输入测量的。在更自然（也更具有挑战性）的\citet{keriven 2020 convergence}设置下，人们只能访问根据边缘概率采样的0-1邻接矩阵，我们首先给出了一个否定的结果，即任何IGN的收敛都是不可能的。然后，我们得到收敛的一个子集的IGN，表示为IGN小，边缘概率估计后。我们证明了IGN-small仍然包含足够丰富的函数类，可以任意很好地近似谱GNNs。最后，我们在各种图子模型上进行实验，以验证我们的说法。
Although theoretical properties such as expressive power and over-smoothing of graph neural networks (GNN) have been extensively studied recently, its convergence property is a relatively new direction. In this paper, we investigate the convergence of one powerful GNN, Invariant Graph Network (IGN) over graphs sampled from graphons. We first prove the stability of linear layers for general $k$-IGN (of order $k$) based on a novel interpretation of linear equivariant layers. Building upon this result, we prove the convergence of $k$-IGN under the model of \citet{ruiz2020graphon}, where we access the edge weight but the convergence error is measured for graphon inputs. Under the more natural (and more challenging) setting of \citet{keriven2020convergence} where one can only access 0-1 adjacency matrix sampled according to edge probability, we first show a negative result that the convergence of any IGN is not possible. We then obtain the convergence of a subset of IGNs, denoted as IGN-small, after the edge probability estimation. We show that IGN-small still contains function class rich enough that can approximate spectral GNNs arbitrarily well. Lastly, we perform experiments on various graphon models to verify our statements.