Abstract
Graph neural networks (GNNs) have shown superiority in many prediction tasks over graphs due to their impressive capability of capturing nonlinear relations in graph-structured data. However, for node classification tasks, often, only marginal improvement of GNNs over their linear counterparts has been observed. Previous works provide very few understandings of this phenomenon. In this work, we resort to Bayesian learning to deeply investigate the functions of non-linearity in GNNs for node classification tasks. Given a graph generated from the statistical model CSBM, we observe that the max-a-posterior estimation of a node label given its own and neighbors' attributes consists of two types of non-linearity, a possibly non-linear transformation of node attributes and a ReLU-activated feature aggregation from neighbors. The latter surprisingly matches the type of non-linearity used in many GNN models. By further imposing Gaussian assumption on node attributes, we prove that the superiority of those ReLU activations is only significant when the node attributes are far more informative than the graph structure, which nicely matches many previous empirical observations. A similar argument can be achieved when there is a distribution shift of node attributes between the training and testing datasets. Finally, we verify our theory on both synthetic and real-world networks.
Introduction
In the development of Graph Neural Networks (GNNs), a persistent paradox has emerged: while models like Graph Convolutional Networks (GCN) and Graph Attention Networks (GAT) are celebrated for their non-linear expressive power, empirical evidence often suggests that simple linear propagation models—such as Simplifying Graph Convolutional (SGC) networks—perform comparably on standard benchmarks. This observation raises a fundamental question: When and why does non-linearity actually provide a performance benefit in node classification?
While previous theoretical frameworks have focused on "expressive power" (e.g., the 1-WL test), expressiveness does not necessarily equate to generalization or accuracy in classification tasks. This paper addresses this gap by applying Bayesian inference to a statistical graph model, providing a rigorous characterization of the role of non-linearity.
The Bayesian Framework: CSBM and MAP Estimation
To analyze GNN behavior, the authors utilize the Contextual Stochastic Block Model (CSBM). In this generative model, both the graph structure (edges) and node attributes are conditioned on latent community labels. By deriving the Maximum-a-Posteriori (MAP) estimator—the mathematically optimal method for predicting a node's label given its features and its neighbors' features—the study reveals a striking connection to modern GNN architectures.
The derived MAP estimator consists of two primary components:
- A transformation of the node's own attributes.
- A ReLU-activated aggregation of neighbor information.
Remarkably, this suggests that the ReLU activation commonly used in GNNs is not merely a heuristic but is, in fact, the optimal non-linearity for filtering information from a node's neighborhood under the CSBM framework. The ReLU function acts as a gate, preventing "noisy" or irrelevant neighbor signals from contaminating the classification signal.
The Informativeness Threshold
The core contribution of this work is the identification of the "Informativeness Threshold" using Signal-to-Noise Ratio (SNR) analysis. The authors compare the SNR of the classification boundary for linear versus non-linear models across different regimes of attribute informativeness.
1. Limited Attributed Information Regime
When node attributes are weak or noisy (low SNR), the performance gap between non-linear and linear models is negligible. In this regime, the graph structure provides the primary signal, and the complex non-linear transformations do not offer a statistically significant advantage over linear aggregation.
2. Sufficient Attributed Information Regime
As node attributes become more informative (high SNR), the advantage of non-linearity becomes pronounced. Theorem 2 of the paper quantifies this, showing that non-linear models achieve "order-level superiority" over linear baselines once attributes reach a certain level of distinctiveness. This explains why GNNs often only marginally outperform linear models on benchmarks where features are sparse or low-quality.
Robustness and Transferability
Beyond raw accuracy, the paper explores how non-linearity affects model robustness. The authors prove that non-linear models (specifically those utilizing ReLU) exhibit superior transferability. In scenarios where there is a distribution shift in node attributes between training and testing datasets, non-linear models are significantly more robust than their linear counterparts, provided the attributes remain informative. This suggests that non-linearity helps the model learn a more resilient decision boundary that generalizes better across varying data distributions.
Empirical Validation
The theoretical findings were validated through extensive experiments on both synthetic and real-world datasets:
- Synthetic Data: Using CSBM-generated graphs, the authors controlled parameters such as edge probability and attribute means. The results mirrored the theory: as the distance between attribute means increased, the accuracy gap between the non-linear MAP-based model and linear baselines widened.
- Real-World Data: On the Cora, CiteSeer, and PubMed citation networks, the authors manipulated attribute informativeness by replacing original features with controlled Gaussian or Laplace attributes. The experiments confirmed that the "ReLU advantage" only kicks in once the attribute signal is sufficiently strong.
- Distribution Shifts: Perturbation tests demonstrated that the error ratio for non-linear models remained significantly lower than for linear models as the intensity of distribution shifts increased.
Conclusion
This research provides a critical "reality check" for GNN design. It demonstrates that the utility of non-linearity is intrinsically linked to the quality of node attributes. If node features are uninformative, complex non-linear architectures are unlikely to provide significant gains over simpler linear models. However, when features are rich, ReLU-based non-linearity performs an essential role in optimal Bayesian filtering, enhancing both accuracy and robustness to distribution shifts. This work paves the way for more informed architecture selection based on the statistical properties of the underlying graph data.
Summary updated