Beyond Linear: A Theoretical and Empirical Analysis of Nonlinear GNNs for Community Detection

Abstract. Many theoretical results are known about graph neural networks (GNNs) in terms of expressivity and performance. However, there is less theory on how the statistical graph structure affects the ability of GNNs to classify nodes in a community detection task. While some recent works have analyzed the performance of linear GNNs in a theoretically rigorous way, performance analysis of nonlinear models leaves much to be desired. In this study, we analyze nonlinear, two-layer GNNs in the context of community detection in generalized contextual stochastic block models (cSBMs). First, we rigorously derive the generalization accuracy of simple one- and two-layer linear models. We then prove that inducing certain symmetries on graph models lowers their cross entropy when the graph structure obeys similar symmetries. After the theoretical analysis, we empirically compare the accuracy of a variety of GNN architectures (graph attention network, graph convolutional network, GPS, GraphSAGE, and Graph Transformers) on cSBMs while varying feature separation, topological class separation, the number of classes, and degree-correction. While these experiments partially validate the theory, their main purpose is to explore regimes beyond the scope of our theoretical results. We also compare their accuracy to a baseline neural network that ignores the graph structure and a baseline spectral graph model that ignores the feature information. Finally, we develop a novel technique for projecting real data to a cSBM and demonstrate experimentally that the various GNN architectures, in the two layer case, perform better on the projected data than the original real data. These experiments suggest that the presence of higher-order structure in real data may hurt the performance of GNNs and that there may be a discrepancy between GNN theory and performance.