Consensus-Null Initialization for Deep Graph Networks

Deep graph neural networks (GNNs) are networks that update each node by averaging its neighbours' features and then applying a learned linear map. When many such layers are stacked, every node drifts toward the same vector, so the network can no longer tell nodes apart. This failure is called over-smoothing. Recent work has shown that it is partly a failure of training rather than of expressiveness. Weights that avoid the collapse provably exist, but gradient descent started from standard random weights does not find them. Several papers therefore redesign weight initialization using graph structure. All of them adjust only the scale of the random weights, and one of them proves that, for ReLU networks, scale alone cannot stabilize everything at once.

We propose to change the direction of the initial weights instead. In the averaging operator, the collapse toward a common vector always happens along one known node-space direction: the operator's top eigenvector, which for the usual GCN normalization is proportional to the square root of each node's degree. The part of any layer's features that lies along this direction is exactly a rank-one matrix. Its feature-space direction can therefore be removed exactly by choosing the next layer's weight matrix to map it to zero. Consensus-Null Initialization (CNI) computes this "consensus direction" layer by layer during one forward pass on the actual graph. It then initializes each weight matrix with that direction in its null space, rescaled to keep the usual variance. The result is a plain GCN with no normalization layers, no skip connections and no runtime overhead. The question we test is whether starting training away from the consensus mode lets deep vanilla GCNs escape the training trap that has been blamed for their failure.

Core Claim

Write $\tilde{A}$ for the symmetrically normalized adjacency with self-loops. Let $u_1 \propto \tilde{D}^{1/2}\mathbf{1}$ be its top eigenvector, with eigenvalue 1 on a connected graph, where $\tilde{D}$ is the degree matrix. Let $H \in \mathbb{R}^{n \times d}$ be the node features entering a layer. The consensus part of $H$ is exactly

$$u_1 u_1^\top H = u_1 m^\top, \qquad m = H^\top u_1 \in \mathbb{R}^d .$$

So if the layer's weight matrix $W$ satisfies $W^\top m = 0$, then $HW$ has no component along $u_1$. Because $u_1$ is an eigenvector of the symmetric matrix $\tilde{A}$, the subsequent aggregation $\tilde{A}HW$ stays orthogonal to $u_1$. CNI builds each $W_l$ as

$$W_l = c_l \,\big(I - \hat{m}_l \hat{m}_l^\top\big)\, G_l .$$

Here $G_l$ is a standard Gaussian matrix, $\hat{m}_l$ is the unit-normalized consensus direction measured at layer $l$ in the initialization forward pass, and $c_l$ is a scalar chosen by an existing degree-aware rule. Each ReLU reintroduces a consensus component, because its outputs are non-negative. The next weight matrix removes that component again.

The claim has three parts. First, this orientation constraint lies outside the scalar-variance setting of the ReLU trilemma proved in Exploring and Improving Initialization for Deep Graph Neural Networks: A Signal Propagation Perspective. Second, it keeps the effective rank of node representations from collapsing at step zero. Third, and this is the claim that matters, removing the dominant uninformative mode at initialization prevents the backward-oversmoothing trap. In that trap the output layer quickly fits smoothed features and gradients to earlier layers die.

We state the limitation up front. In a linear model, features orthogonal to $u_1$ still decay toward the second eigenvector $u_2$ at rate $\lambda_2^L$, where $\lambda_2$ is the second-largest eigenvalue and $L$ the depth. Collapse is therefore delayed and redirected onto community structure, not abolished. Whether that residual slow collapse matters in practice is an empirical question the experiments answer.

Relation to Prior Work

Four papers supply the setting and constrain the design. The degree-aware Kaiming generalization of Reducing oversmoothing through informed weight initialization in graph neural networks and Informed weight initialization of Graph Neural Networks and its effect on Oversmoothing, called G-Init, scales isotropic Gaussian weights by node degree. It trains 64-layer GCNs, but it needs a hand-tuned degree constant and applies only to the first 80% of layers. On the Initialization of Graph Neural Networks, called Virgo, derives forward and backward variance from path counts at moderate depth. SPoGInit searches per-layer variances by zeroth-order optimization and proves that for ReLU GCNs no scalar variance stabilizes forward signal, backward signal and embedding variation together. That is why it relies on residual networks. Old can be Gold: Better Gradient Flow can Make Vanilla-GCNs Great Again calibrates near-isometric weights to the degree distribution, but its depth results depend on dynamically added skip connections. CNI reuses the scale rules of these methods for $c_l$ and adds what none of them has: a data-dependent constraint on the orientation of the weights' singular vectors.

Earlier suggestions to align weights with the Laplacian spectrum are dimensionally confused. Laplacian eigenvectors live in node space and weights act in feature space. The rank-one identity above is the exact bridge between the two, which is why we align to $m$ and not to the eigenvectors themselves.

Three papers motivate the mechanism. Graph Neural Networks (with Proper Weights) Can Escape Oversmoothing proves that collapse-avoiding weights exist and maintains them with an input-dependent reparameterization during training, tested only to 8 layers. CNI asks whether placing the weights in such a configuration once, at step zero, is enough. Backward Oversmoothing: why is it hard to train deep Graph Neural Networks? shows that gradients are smoothed like activations. It also shows that a fast-converging output layer strands hidden layers at high-loss stationary points, and it notes that initialization might steer around this without proposing a scheme. We supply one and measure the trap directly. Are we measuring oversmoothing in graph neural networks correctly? shows that numerical rank collapses to one for non-negative weights, and that Dirichlet energy misses collapse that effective rank catches. Effective rank averages 0.91 Pearson correlation with accuracy. We adopt its rank metrics as primary diagnostics. CNI weights are necessarily of mixed sign, so the non-negativity condition of its theorem is violated by construction.

Research Program

The method itself is small. It needs one closed-form $u_1$ per connected component, one forward pass to read off each $m_l$, one projection per layer, and one rescaling. The research is about establishing what this single intervention does and does not buy.

We first verify the forward effect at initialization. For vanilla ReLU GCNs of depth 2 to 64, we track the energy fraction in the $u_1$ component, the effective rank and numerical rank of each layer's output, and Dirichlet energy for contrast. We do this under Xavier, Kaiming, G-Init, Virgo and CNI.

We then test the backward claim on contextual stochastic block models, which are synthetic graphs with controllable community strength, following the setup of the backward-oversmoothing paper. We log, per layer and per step, the gradient norm and the output-layer loss. The trap has a clear signature: output-layer gradients near zero while training loss stays high and hidden weights barely move. We check whether CNI removes that signature and whether the benefit persists after the weights drift from their initial null-space property. To measure the drift, we track $\|W_l^\top \hat{m}_l(t)\|$ over training, where $\hat{m}_l(t)$ is the consensus direction at step $t$.

Two practical issues need handling. Disconnected graphs such as CiteSeer have one consensus direction per component. The default removes the direction of the giant component, and an ablation removes the span of the $k$ largest components' directions. For attention models, where aggregation is row-stochastic and asymmetric, the relevant direction becomes the dominant eigenvector of the attention matrix at initialization, obtained by power iteration. We treat this as an extension evaluated on GAT only after the GCN results are in.

Baselines

The naive reference points are vanilla GCNs with Xavier and Kaiming initialization at matched depth. These collapse badly. Informed weight initialization of Graph Neural Networks and its effect on Oversmoothing reports them dropping to "around 13-26%" on Cora at 64 layers.

The strongest same-architecture competitor is G-Init. It is the only prior method that trains a vanilla GCN, with no skips and no normalization, to 64 layers by initialization alone. It reports 69.24% accuracy on Cora at 64 layers (Reducing oversmoothing through informed weight initialization in graph neural networks) and 71.66% on ogbn-arxiv at 32 layers (Informed weight initialization of Graph Neural Networks and its effect on Oversmoothing). Beating it means CNI, using G-Init's own scale as $c_l$, exceeds these numbers at the same depth on our reproduced splits. It must also exceed our reproduction of G-Init by more than the seed standard deviation over ten seeds.

Virgo and the isometric initialization of Old can be Gold, run without its dynamic skips, are run the same way to cover the other scale rules. SPoGInit is run on vanilla GCN, where its paper predicts failure, and on ResGCN. On ResGCN its reported result is 71.3% on ogbn-arxiv at 64 layers against 16.5% for Xavier (Exploring and Improving Initialization for Deep Graph Neural Networks: A Signal Propagation Perspective). For that architecture we test whether CNI on a plain GCN matches it, and whether CNI inside ResGCN improves on it. The isometric initialization with dynamic skips reports 72.28% on ogbn-arxiv, which serves as the architecture-modifying ceiling.

For fairness, all methods share the same splits, hidden width, optimizer, number of epochs and tuning budget. The tuning grid covers learning rate, weight decay and dropout, and is identical for every initializer. G-Init's degree constant gets its own small grid, since its authors tune it.

Two ablations isolate the key ingredient, which is the direction. The first projects out a random unit vector instead of $\hat{m}_l$, with identical rescaling. This controls for the mere loss of one weight dimension. The second replaces the degree-weighted $u_1$ with the uniform vector $\mathbf{1}/\sqrt{n}$, which is what node-space mean-centering removes. A third variant keeps the projection enforced throughout training as a reparameterization. This tells us whether initialization alone suffices or whether CNI must become a layer to work.

Why not just…?

Why not just use PairNorm or BatchNorm, which already subtract the mean across nodes? This is the most serious alternative, because node-space centering removes nearly the same component. The differences are that it uses the uniform mean rather than the degree-weighted eigenvector, and that it acts at every layer throughout training rather than once. PairNorm: Tackling Oversmoothing in GNNs reports 74.5% versus 42.3% for vanilla SGC on Cora with all unlabeled node features missing. Its authors also concede it does not always raise peak accuracy on feature-rich graphs, and WeightRep reports beating it across benchmarks. We will not argue past this. We run PairNorm, PairNorm-SI and BatchNorm on vanilla GCN at every depth, including the missing-feature setting. The uniform-mean ablation and the persistent-projection variant show whether degree weighting matters and whether anything beyond step zero is needed. If PairNorm matches CNI at depth, the honest conclusion is that initialization adds only the convenience of an unmodified architecture, and we will report it that way.

Why not just add residual connections? Skips help, but they do not make initialization irrelevant: SPoGInit's paper reports a 64-layer ResGCN with Xavier collapsing to 16.5% on ogbn-arxiv. Skips also change the architecture and its memory profile, whereas the question here is what a vanilla GCN can do. We include ResGCN with Xavier, with SPoGInit and with CNI, so the reader can see whether CNI's effect is additive to skips or redundant with them.

Why not just raise the ReLU slope? REDUCING OVERSMOOTHING IN GRAPH NEURAL NETWORKS BY CHANGING THE ACTIVATION FUNCTION reports 73.47% on Cora at depth 19 in the cold-start setting, but acknowledges that large slopes can make gradients explode. A slope changes scale, not direction. It therefore compensates for variance shrinkage, but the consensus mode still dominates. We run slope-2 GCN alone and combined with CNI. The prediction is that the two are complementary: slope fixes magnitude and CNI fixes orientation. If slope alone matches CNI in effective rank and accuracy, the orientation story is wrong.

Why not just slow down or zero-initialize the output layer, since the backward trap starts there? This is a cheap and plausible fix for the trap in Backward Oversmoothing: why is it hard to train deep Graph Neural Networks?. It delays the output layer's convergence, but it does not change what that layer eventually fits, which is still smoothed features. We run a reduced output-layer learning rate at 0.1× and 0.01× and a zero-initialized readout, each alone and with CNI. If they alone recover G-Init-plus-CNI accuracy on the block models and on Cora at 64 layers, then the trap is a timing problem rather than a representation problem. That would substantially weaken our claim.

Why not just let SPoGInit search harder? SPoGInit's own theorem says scalar variance cannot solve the problem for vanilla ReLU GCNs, and its search space contains no orientation. Our vanilla-GCN SPoGInit run tests this directly.

Proposed Experiments

Node classification uses Cora, CiteSeer, PubMed, CoauthorCS and ogbn-arxiv at depths 2, 4, 8, 16, 32 and 64 with vanilla GCN. Chameleon, Squirrel and Actor check that removing the consensus mode does not hurt heterophilic graphs, where degree-weighted means might carry signal; no reported result was found on Lacuna for initialization methods on these. We also use the missing-feature setting of PairNorm on Cora, and contextual stochastic block models for the mechanism study. Metrics are test accuracy over ten seeds, effective rank and numerical rank per layer at initialization and at convergence, the $u_1$ energy fraction, per-layer gradient norms, and wall-clock time for the initialization pass.

Four checks decide the outcome. First, CNI on a vanilla 64-layer GCN must beat reproduced G-Init on Cora and CoauthorCS, and the random-direction ablation must not. If the random direction also helps, the effect is not about consensus. Second, effective rank at initialization must predict final accuracy across initializers at 64 layers. This extends the rank paper's correlation from trained networks to step zero, and failure would mean rank at initialization is the wrong target. Third, on the block models CNI must remove the backward-trap signature rather than merely delay it. Fourth, the comparison against PairNorm and against the output-layer learning-rate fix must show a gap. If neither gap exists, we report CNI as an architecture-free equivalent of centering rather than a new mechanism.