Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspective

Rongzhe Wei, Haoteng Yin, Junteng Jia, Austin R. Benson, Pan Li

The Mystery of Non-Linearity in GNNs

In the world of Graph Neural Networks (GNNs), non-linearity is usually touted as the primary source of the model's "expressive power." However, empirical researchers have consistently noticed a puzzling trend: for node classification tasks, simple models that use linear propagation (like SGC) or only apply non-linearity to initial features (like APPNP) often match or even beat deep, non-linear architectures.

Until now, there has been a lack of rigorous theory explaining this phenomenon. We didn't know exactly when non-linear propagation—the exchange of features between neighbors—is necessary, and why it sometimes fails to provide a performance boost. This paper seeks to bridge that gap by examining GNNs through the lens of statistical Bayesian inference.

A Bayesian Approach to Graph Learning

The authors use the Contextual Stochastic Block Model (CSBM) as their theoretical foundation. In a CSBM, nodes belong to specific classes, and edges are formed based on those classes (exhibiting either homophily or heterophily). Crucially, each node also has an associated attribute vector (feature) sampled from a class-conditioned distribution.

The core of their approach relies on Maximum-a-Posteriori (MAP) estimation. They pose a fundamental question: "If we know the statistical process that generated this graph and its features, what is the mathematically optimal way to predict a node's label?"

By deriving the MAP estimator, they made a striking discovery: the optimal classifier naturally takes the exact form of a GNN layer. Specifically, it involves:

  1. A (potentially non-linear) transformation of node attributes.
  2. A ReLU-activated aggregation of features from neighbors.

They then compare this "Optimal Nonlinear" model against a "Baseline Linear" model using Signal-to-Noise Ratio (SNR) analysis to quantify misclassification errors across different regimes of information.

Key Insights and Ideas

The Bayesian Justification for ReLU

The most surprising "aha moment" of the paper is that the ReLU activation—a staple of modern deep learning—emerges naturally from the mathematics of Bayesian inference on graphs. It isn't just a convenient heuristic; it is part of the theoretically optimal way to combine a node's own data with its neighbors' data.

The optimal aggregation function naturally takes a ReLU-like shape.

The Information Threshold

The paper proves that if node attributes are "weak" (low informativeness), linear propagation is essentially just as good as non-linear propagation. Non-linearity only provides a significant, order-level advantage when node attributes are "sufficiently informative."

ReLU as a Filter

In the "informative" regime, the ReLU function acts as a critical safeguard. It prevents the model from becoming overconfident based on noisy neighbor attributes, effectively filtering the true signal from the graph structure.

Robustness to Distribution Shift

The authors also found that non-linearity provides better transferability. If the distribution of node attributes changes between training and testing, a non-linear model handles the shift much better than a linear one, provided the attributes remain informative.

Empirical Validation and Key Results

The study validates its theory using both synthetic CSBM graphs (to precisely control the "informativeness" of node attributes versus graph structure) and real-world citation networks (PubMed, Cora, and CiteSeer). To test their theory on real data, they replaced the original bag-of-words features with controlled Gaussian and Laplacian distributions to vary the level of attributed information.

Accuracy comparison on real-world datasets with varying attributed information.
  • The Theoretical Punchline (Theorem 2): When attribute information is limited ($O(1)$), the performance gap between linear and non-linear models is negligible. When attributes are sufficient ($\omega(1)$), the non-linear model's error rate can be significantly smaller.
  • Empirical Match: In experiments on Cora, PubMed, and CiteSeer, the accuracy curves for linear and non-linear models are nearly identical when features are noisy. As the features become cleaner and more informative, a clear gap opens up where the non-linear MAP-based model takes the lead.
  • Heterophily: The theory holds up even in "heterophilic" settings (where nodes with different labels tend to connect). Linear propagation still performs competitively there unless the node features are exceptionally strong.

Limitations and Future Work

While the paper provides a rigorous theoretical foundation, it notes a few constraints:

  • Local Scope: The analysis primarily focuses on 1-hop neighbors to keep the MAP estimation mathematically tractable. Real GNNs often use multiple layers to capture multi-hop information.
  • Model Assumptions: The theory relies on the CSBM. While the authors argue this generalizes to the "Natural Exponential Family" of distributions, real-world data distributions can be far more complex and non-parametric.
  • Depth vs. Non-linearity: The paper focuses on the type of non-linearity in propagation rather than the depth of the network. Exploring how these Bayesian insights apply to very deep GNNs—which often suffer from over-smoothing—is a logical and exciting next step for the field.

Summary updated

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 has been observed in practice over their linear counterparts. Previous works provide very few understandings of this phenomenon. In this work, we resort to Bayesian learning to give an in-depth investigation of 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, the 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 explains previous empirical observations. A similar argument is derived 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. Our code is available at <https://github.com/Graph-COM/Bayesian_inference_based_GNN.git>.
BibTeX
@inproceedings{wei2022understanding,
  author = {Rongzhe Wei and Haoteng Yin and Junteng Jia and Austin R. Benson and Pan Li},
  title = {{Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspective}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=Xt9smkoTgQf},
}
Figure