Lower and Upper Bounds for Numbers of Linear Regions of Graph Convolutional Networks
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.