Standard Graph Neural Networks (GNNs) are often designed by stacking layers of neighborhood aggregation, feature transformations, and non-linear activation functions (like ReLU). While this mirrors the architecture of deep convolutional neural networks used in computer vision, a growing body of research suggests that for many graph-based tasks, the non-linearities are not only redundant but can actively hinder performance and efficiency.
Linearized Graph Convolutional Networks (LGCNs) simplify this architecture by removing non-linear activations and collapsing multiple layers into a single linear operation. This shift prioritizes the structural information of the graph—the "where" nodes are connected—over the complex "what" of deep feature transformations.
The Redundancy of Non-linearity
In traditional deep learning, non-linearities allow networks to approximate complex functions. However, in graph representation learning, the primary signal often comes from the graph structure itself. Xiangnan He and colleagues demonstrated this in LightGCN, showing that for recommendation tasks, removing feature transformations and non-linear activations actually improved accuracy by up to 16%.
The intuition is that graph convolution acts primarily as a low-pass filter, smoothing features across neighboring nodes. As Amauri H Souza notes in Improving Graph Variational Autoencoders with Multi-Hop Simple Convolutions, this filtering captures the essential signals in homophilic graphs (where similar nodes connect). When the signal is dominated by this structural smoothing, the added complexity of non-linear layers often leads to overfitting rather than better representation.
Collapsing the Computational Graph
The most significant practical advantage of linearization is the ability to "collapse" the network. In a standard $K$-layer GNN, the model must perform neighborhood aggregation and non-linear transformations $K$ times during every training step.
By removing the non-linearities, the operation becomes a series of linear matrix multiplications: $$H = A(A(...(AXW_1)W_2...)W_K)$$ Because matrix multiplication is associative, all the graph adjacency matrices ($A$) can be pre-computed into a single power matrix ($A^K$), and all the weight matrices ($W$) can be collapsed into a single learnable transformation.
As Kunze Wang explains in the context of text classification, this allows the expensive graph propagation step to be moved to a one-time pre-processing stage. This leads to massive efficiency gains; for instance, Zhiyuan Liu showed that training-free models using this principle can be up to 5,000x faster than traditional GNNs while maintaining competitive accuracy.
Theoretical Tractability and Machine Unlearning
Linearization transforms GNNs from "black boxes" into mathematically tractable systems. This is particularly crucial for Machine Unlearning—the requirement to remove a specific node's influence from a trained model for privacy reasons.
In a non-linear GNN, deleting one node has a cascading, unpredictable effect on the weights. However, in a linearized model, the relationship between input features and weights is transparent. Weilin Cong and Mehrdad Mahdavi leveraged this in PROJECTOR, which unlearns data by simply projecting model weights onto a subspace independent of the deleted data. Similarly, Chao Pan and Eli Chien introduced certified graph unlearning, using the convex loss surfaces of linearized models to provide theoretical guarantees that data has been forgotten.
Robustness to Over-smoothing and Heterophily
Deep GNNs often suffer from "over-smoothing," where node representations become indistinguishable after too many layers of aggregation. Linearized models provide a cleaner way to handle depth. By decoupling the depth of propagation from the depth of the learnable parameters, researchers can use high-order aggregations without the numerical instability of deep non-linear stacks.
This robustness extends to heterophily (where connected nodes are different). Jiong Zhu and the team behind H2GCN found that removing non-linearities between aggregation steps allows the model to better preserve the distinct signals from different neighborhood hops. Furthermore, Huayi Tang demonstrated that linearization reduces the model's Lipschitz constant, leading to tighter generalization bounds and explaining why these simpler models often outperform complex ones in transductive settings.
Summary of Intuition
The success of linearized GNNs suggests that the "neural" part of Graph Neural Networks is often less important than the "graph" part. By treating graph convolution as a fixed, linear signal-processing step:
- Efficiency is maximized by pre-computing structural propagation.
- Generalization is improved by reducing over-parameterization and avoiding spurious non-linear patterns.
- Reliability is gained through closed-form solutions and predictable weight updates, enabling advanced features like certified unlearning.