Covariance Message Passing: Recovering What Neighborhood Averaging Smooths Away

Graph neural networks (models that update each node's representation by averaging its neighbors' representations, layer after layer) lose accuracy as they get deeper. This loss is usually called over-smoothing: node representations drift toward a common value. Most fixes, such as skip connections, normalization layers and high-pass filter channels, try to stop that drift. This proposal targets something different. Averaging a neighborhood keeps only its first-order statistic, the mean, and throws away the second-order statistic: how the neighbors' features vary and co-vary. Computer vision faced the same choice between average pooling and bilinear pooling, which pools the outer product of feature vectors and so keeps the covariance between channels. In vision, keeping second-order statistics was what made fine-grained recognition work. We propose a message-passing layer that pools a compressed, mean-centered neighborhood covariance next to the usual mean.

In two sentences: the mean of a node's neighbors is the quantity smoothing preserves, while the spread and co-occurrence of features among those neighbors is the quantity smoothing destroys and heterophilic graphs need. A centered covariance channel, made cheap with Tensor Sketch, captures that information. It also avoids a degree-squared blow-up that we predict will make the existing uncentered bilinear graph aggregator fail at depth.

Core Claim

The closest prior work is the Bilinear Graph Neural Network (Bilinear Graph Neural Network with Neighbor Interactions). It adds pairwise element-wise products between neighbors, computed in linear time with the factorization-machine identity $\sum_{i<j} x_i \odot x_j = \tfrac12[(\sum_i x_i)^2 - \sum_i x_i^2]$. It reports gains of about 1.6% over GCN on two-layer citation models. Rewriting that identity for a node with $n$ neighbors whose features have per-channel mean $\mu$ and variance $\sigma^2$ gives roughly $\tfrac12[n(n-1)\mu^2 - n\sigma^2]$.

That decomposition has two consequences. First, the aggregator is dominated by the squared mean scaled by degree squared, so it carries mostly first-order information. Second, as representations smooth, $\sigma^2$ goes to zero while the $n^2\mu^2$ term remains. This should amplify the "high-degree curse" that Simple and Deep Graph Convolutional Networks proved, in which high-degree nodes collapse fastest. The useful second-order signal is the centered part, and it is also diagonal-only: the element-wise product never sees cross-channel co-occurrence, which is exactly what Bilinear CNN Models for Fine-Grained Visual Recognition showed matters.

Our layer pools, for each node $v$ with neighbors $\mathcal{N}(v)$ and current representations $h_u \in \mathbb{R}^d$,

$$C_v = \frac{1}{|\mathcal{N}(v)|}\sum_{u \in \mathcal{N}(v)} (h_u - \mu_v)(h_u - \mu_v)^\top = \frac{1}{|\mathcal{N}(v)|}\sum_{u} h_u h_u^\top - \mu_v \mu_v^\top,$$

where $\mu_v$ is the neighbor mean. $C_v$ is invariant to any vector added to all neighbors, so it is blind to the component that smoothing preserves. Degree normalization removes the $n^2$ scaling.

We never form $C_v$. Compact Bilinear Pooling computes the count sketch of an outer product as a circular convolution of two sketches using a fast Fourier transform. On CUB-200-2011 it compressed a 262,144-dimensional bilinear feature to 8,192 dimensions with no change in error. Sketching is linear, so the sketch of $C_v$ equals the averaged per-neighbor sketches minus the sketch of $\mu_v\mu_v^\top$. Both pieces can be computed by ordinary message passing at $O(D \log D)$ cost per edge for sketch size $D$. After the signed square-root and $L_2$ normalization used in bilinear CNNs, the sketch is projected and added to the standard update.

Research Program

The program asks one question: when depth stability is already handled, does a second-order neighborhood statistic add something mean aggregation cannot represent? The Oversmoothing Fallacy argues that depth failure mostly comes from the linear transforms and activations, which drive representations toward zero, and not from aggregation. It trained GCNs to 1,024 layers using residual connections and batch normalization. We take this as a constraint on the design.

Our covariance channel is therefore always added on top of a backbone that is already stable at depth. We use two such backbones. One is residual connections plus batch normalization in the Fallacy style. The other is GCNII's initial-residual and identity-mapping update. Under this setup, any gain cannot be credited to simply making depth trainable.

The work has three parts. The first is analysis. We will prove that the uncentered factorization-machine aggregator grows with degree squared under smoothing, while the centered sketch stays bounded. We will also characterize when $C_v$ distinguishes nodes whose neighbor means are identical. The second is the layer, which comes in three variants: uncentered diagonal (a reimplementation of the Bilinear Graph Neural Network inside our backbones), centered diagonal (per-channel neighbor variance), and centered full covariance via Tensor Sketch. The third is measurement. Following Are we measuring oversmoothing in graph neural networks correctly?, we track effective rank and numerical rank of representations at every depth instead of Dirichlet energy. That paper found effective rank correlates with accuracy at 0.91 on average, while Dirichlet energy stayed flat during early accuracy drops. Because high rank is necessary but not sufficient, we report rank alongside accuracy rather than as a target.

Baselines

The naive reference point is the same residual-plus-batch-normalization GCN and the same GCNII backbone without any second-order channel. Both use identical hidden size, depth grid (2, 4, 8, 16, 32, 64), splits, optimizer and a matched hyperparameter search budget. Beating this reference means the covariance variant improves accuracy at matched depth, averaged over seeds, by more than the seed-to-seed spread. On homophilic citation graphs it must at least not lose accuracy.

The strongest deep, heterophily-aware competitor in the file is Ordered GNN (Ordered GNN). It splits the embedding into blocks tied to tree depth and merges them with a learned ordered gate. It reports 89.10% accuracy on Cora at 64 layers, against 52% for GCN, and 62.44% on Squirrel. We will rerun it from its published configuration on our splits and also quote its reported numbers. Beating it means matching it on Cora at 64 layers and exceeding it on Squirrel, Chameleon and Actor.

The most direct competitor on the mechanism is the Bilinear Graph Neural Network itself, run from its official code at github.com/zhuhm1996/bgnn and also inside our deep backbones. The file reports only an average 1.6% gain over GCN and no per-dataset figure, so we will reproduce it rather than quote it. Our prediction is concrete: its accuracy should fall with depth faster than the centered variant, and the fall should be concentrated in high-degree nodes.

Two further baselines represent the anti-smoothing tradition. Filterbank GNN (Complete the Missing Half) adds a learned high-pass channel and reports roughly 10% over GCN on Texas and Cornell. The file gives no absolute value, so there is no reported result found on Lacuna for its exact accuracy. PairNorm (PairNorm) is a parameter-free normalization. It reports 74.5% against 42.3% for plain SGC on Cora when all unlabeled nodes lack features. Both are given the same tuning budget.

The ablation that isolates the key ingredient is the three-way comparison between uncentered diagonal, centered diagonal and centered full covariance. Two further controls address sketch size: a random projection of matched output dimension, and a sketch size sweep from 256 to 8,192. These separate the effect of second-order structure from the effect of extra parameters.

Why not just…?

Why not just use residual connections and batch normalization? The Fallacy paper shows these alone make very deep GCNs trainable, and we accept that result. That is why they are our backbone, not our competitor. Their result addresses whether depth can be trained. It does not address whether a mean aggregator can represent neighborhood dispersion. If the covariance channel adds nothing on top of that backbone, our claim fails, and the depth-curve comparison will show it directly.

Why not just precompute neighborhood variance features once and feed them to an MLP or a shallow GNN? This is the most serious threat. If second-order statistics of the input features carry all the benefit, nothing needs to happen inside message passing. We will build this baseline explicitly: full sketched covariances at hops 1 to 3, computed on raw features and concatenated. If it matches the full layer, we will report that the contribution is a feature-engineering result rather than an architectural one. The architectural claim survives only if recomputing covariance on learned, layer-wise representations wins on heterophilic graphs, where learned features differ most from raw ones.

Why not just add a per-channel variance aggregator or a high-pass channel? Filterbank GNN's high-pass channel is a first-order difference between a node and its neighbor mean. A variance aggregator is our centered diagonal ablation. Both can be strong. The case for full covariance rests on cross-channel co-occurrence, the signal behind the bilinear CNN results. The synthetic experiment below is built so that diagonal statistics provably carry no class signal. On real data, if centered diagonal matches centered full, we will say the Tensor Sketch is unnecessary.

Proposed Experiments

The first decisive check is synthetic. We generate stochastic block graphs in which every class has identical neighbor-feature means and identical per-channel variances, and classes differ only in the sign of the correlation between two feature channels among neighbors. In this setting, mean aggregation, Filterbank GNN, PairNorm and diagonal variance aggregators should all sit at chance. Only the full covariance channel should separate the classes. Failure here would falsify the mechanism.

The second check uses the real benchmarks in the file: Cora, Citeseer and Pubmed for homophily; Texas, Cornell, Wisconsin, Squirrel, Chameleon and Actor for heterophily; and ogbn-arxiv for scale. For each, we plot accuracy and effective rank across depths 2 to 64, with ten seeds and the standard splits. Accuracy is also stratified by degree quartile, to test the predicted high-degree failure of the uncentered aggregator.

The third check is cost. We report wall-clock time and memory per epoch against the Bilinear Graph Neural Network and GCNII on ogbn-arxiv, at sketch sizes 256 to 8,192.

The overall outcome we expect is modest but specific. On homophilic graphs, results should roughly tie. On heterophilic graphs at depth, the centered full covariance variant should gain, while the uncentered variant degrades in its high-degree nodes. The precomputed-feature baseline decides whether the gain belongs inside message passing at all.