论文标题
图形卷积网络线性区域数量的下限和上限
Lower and Upper Bounds for Numbers of Linear Regions of Graph Convolutional Networks
论文作者
论文摘要
随着图形神经网络在过去五年中获得冠军，对GNN表征表征的研究引起了很多关注。线性区域的数量已被认为是通过分段线性激活的神经网络表达性的良好度量。在本文中，我们介绍了具有一层和多层场景的经典图形卷积网络（GCN）线性区域数量的一些估计。特别是，我们获得了一层GCN的最大线性区域的最佳上限，以及多层GCN的上和下限。模拟估计表明，线性区域的真实最大数量可能更接近我们估计的下限。这些结果表明，多层GCN的线性区域的数量通常大于每个参数的一层GCN。这表明，更深的GCN比浅GCN具有更高的表现力。
The research for characterizing GNN expressiveness attracts much attention as graph neural networks achieve a champion in the last five years. The number of linear regions has been considered a good measure for the expressivity of neural networks with piecewise linear activation. In this paper, we present some estimates for the number of linear regions of the classic graph convolutional networks (GCNs) with one layer and multiple-layer scenarios. In particular, we obtain an optimal upper bound for the maximum number of linear regions for one-layer GCNs, and the upper and lower bounds for multi-layer GCNs. The simulated estimate shows that the true maximum number of linear regions is possibly closer to our estimated lower bound. These results imply that the number of linear regions of multi-layer GCNs is exponentially greater than one-layer GCNs per parameter in general. This suggests that deeper GCNs have more expressivity than shallow GCNs.
