In traditional deep learning, non-linear activation functions (like ReLU) are the lifeblood of expressivity. Without them, a multi-layer neural network collapses into a single linear transformation. When Graph Convolutional Networks (GCNs) were introduced, they naturally inherited this design, interleaving neighborhood feature aggregation with non-linear activations at every layer.
However, a core insight from recent graph representation learning research reveals a surprising truth: in many graph domains, these intermediate non-linearities are not only redundant but can actively harm performance. By stripping away non-linear activations and collapsing successive weight matrices, linearized graph convolution decouples feature propagation from parameter learning. This architectural shift yields massive computational speedups and unlocks deep theoretical insights into how graph neural networks actually process information.
Collapsing the Architecture
To understand why linearized graph convolution works, let us look at the mechanics of a standard $K$-layer GCN. At each layer, the network performs two steps: it averages the feature vectors of a node's neighbors (propagation) and then multiplies the result by a learnable weight matrix before applying a non-linear activation function $\sigma$:
$$H^{(k+1)} = \sigma \left( \tilde{A} H^{(k)} W^{(k)} \right)$$
where $\tilde{A}$ is the normalized adjacency matrix with self-loops, and $W^{(k)}$ is the weight matrix for layer $k$.
If we remove the non-linear activation function $\sigma$, the equation for a $K$-layer network simplifies to a chain of matrix multiplications:
$$H^{(K)} = \tilde{A} \left( \tilde{A} \dots \left( \tilde{A} X W^{(0)} \right) \dots W^{(K-2)} \right) W^{(K-1)}$$
Because matrix multiplication is associative, we can rearrange this expression. We can group all the graph propagation steps together and all the weight matrices together:
$$H^{(K)} = \left( \tilde{A}^K X \right) \left( W^{(0)} W^{(1)} \dots W^{(K-1)} \right)$$
We can now collapse the product of the weight matrices into a single, unified weight matrix $\Theta = W^{(0)} W^{(1)} \dots W^{(K-1)}$. The entire multi-layer network reduces to:
$$\hat{Y} = \text{softmax} \left( \tilde{A}^K X \Theta \right)$$
As demonstrated by Felix Wu et al. in Simplifying Graph Convolutional Networks, this formulation—known as Simple Graph Convolution (SGC)—fundamentally changes the computational paradigm. Because the term $\tilde{A}^K X$ contains no learnable parameters, it can be completely precomputed as a fixed preprocessing step. Once this feature smoothing is done, training the GCN reduces to a standard linear or logistic regression loop, removing the graph structure entirely from the iterative optimization process and accelerating training by orders of magnitude.
Standard GCN:
[Input X] -> [Propagate] -> [ReLU] -> [Weight W1] -> [Propagate] -> [ReLU] -> [Weight W2] -> Output
Linearized GCN (SGC):
[Input X] -> [Propagate K Times (Precomputed)] -> [Single Weight Matrix Θ] -> Output
Graph Propagation as a Low-Pass Filter
Why does this drastic simplification maintain high accuracy across standard benchmarks? The intuition lies in spectral graph theory.
Neighborhood aggregation is fundamentally a localized averaging operation. In the graph frequency domain, averaging features with neighbors acts as a low-pass filter. It smooths out high-frequency noise and ensures that connected nodes share similar representations (reflecting the principle of homophily). As Amauri H Souza et al. note in Improving Graph Variational Autoencoders with Multi-Hop Simple Convolutions, this low-pass filtering captures the essential structural signals required for tasks like link prediction without needing complex non-linear feature engineering.
In fact, interleaving non-linearities with propagation steps can cause numerical issues. In deep GCNs, repeated non-linear transformations combined with neighborhood averaging often lead to over-smoothing, where all node representations collapse into a uniform vector, rendering them indistinguishable.
By linearizing the architecture, we can separate the structural diffusion process from the model's parameter depth. Yifei Wang et al. exploit this in Dissecting the Diffusion Process in Linear Graph Convolutional Networks by decoupling the number of propagation steps ($K$) from the total diffusion time ($T$). This allows the network to aggregate information from wide structural neighborhoods without suffering from the representation degradation typical of deep, non-linear architectures.
The Power of Convexity
Beyond raw training speed, removing non-linear activations transforms the optimization landscape of graph neural networks from a complex, non-convex surface into a well-behaved convex optimization problem. This mathematical tractability unlocks capabilities that are computationally intractable in deep networks.
Certified Graph Unlearning
With increasing demands for data privacy, systems must support the "right to be forgotten"—allowing users to request that their data (nodes, edges, or features) be erased from a trained model. In deep neural networks, guaranteeing that a data point's influence is entirely gone typically requires retraining the model from scratch.
In Certified Graph Unlearning, Chao Pan et al. leverage the convex loss surface of linearized graph models. Because the optimization space is stable and predictable, the authors can compute an exact weight update step using a generalized Newton step combined with noise injection. This allows the model to instantly and provably "forget" specific graph elements with rigorous theoretical privacy guarantees, bypassing the need for expensive retraining.
Exact Influence Functions
Understanding model interpretability or identifying adversarial vulnerabilities requires knowing exactly how much a specific training element influenced a given prediction. In non-convex deep models, calculating this requires loose approximations.
Linearization removes this barrier. Zizhang Chen et al. demonstrate in Characterizing the Influence of Graph Elements that the linear structure of SGC allows for the derivation of exact, closed-form influence functions. Practitioners can mathematically trace how removing a specific node or edge shifts the optimal parameter weights, facilitating rapid data cleaning and robustness verification.
Preserving Structural Signals
In many specialized graph tasks, such as collaborative filtering or link prediction, nodes are initially represented by arbitrary ID embeddings that lack inherent semantic meaning. In these scenarios, passing embeddings through heavy, non-linear feature transformation matrices can distort the underlying structural signals.
Weishuo Ma demonstrates this effect in Reconsidering the Performance of GAE in Link Prediction, showing that linear message passing preserves critical topological properties—such as common neighbor counts—far better than non-linear layers. This allows simple dot-product decoders to reconstruct graph topology with higher fidelity.
Taking this to its logical conclusion, Lisi Qarkaxhija et al. show in Link Prediction with Untrained Message Passing Layers that stripping message-passing layers of all trainable parameters and non-linearities often improves generalization. By freezing the propagation component and relying purely on the graph's inherent geometry, the model avoids overfitting, proving that the structural graph alignment itself is often doing the heavy lifting.