Decentralized Over-Smoothing Correction by Consensus Tracking

Deep graph neural networks (models in which each node repeatedly averages its neighbors' features) suffer from over-smoothing: after many rounds of averaging, every node's representation collapses toward the same vector. The most principled fixes work by subtracting a single global quantity. Corrected graph convolutions remove the network-wide mean at every layer, and PairNorm removes the mean and also rescales by a network-wide spread. These fixes look trivial on a GPU. They are impossible to apply as written on a physical sensor network, where each device can talk only to its radio neighbors and the whole point is to avoid a central server. A sensor network that needs deep, long-range propagation therefore faces a choice: accept over-smoothing, or rebuild the centralized bottleneck that decentralized processing was meant to remove.

This note proposes a third option. The missing global mean is itself a distributed estimation target. A running consensus tracker, of the kind the sensor-network literature calls consensus plus innovations (each node averages its neighbors' estimates and then adds a correction from its own new data), can estimate it continuously. The tracker piggybacks one extra exchange per layer per time step and warm-starts from the previous time step, so over time it amortizes the many gossip rounds that a one-shot average would need. The work makes two concrete claims. The obvious alternative, running a few gossip rounds per layer, provably destroys the very community-scale signal the correction is meant to keep. The tracked version instead inherits a tracking-capacity limit: it works while the sensed field changes slowly relative to the communication graph's mixing speed and fails in a predictable way beyond that.

Core Claim

Analysis of Corrected Graph Convolutions proves that subtracting the projection onto the all-ones vector, $\tilde A = \frac{1}{d}A - \frac{1}{n}\mathbf{1}\mathbf{1}^\top$, makes depth helpful. Misclassification error falls exponentially per layer down to a noise floor in the contextual stochastic block model (a synthetic graph whose node features are Gaussian clusters aligned with its communities). On Cora, CiteSeer and PubMed, accuracy holds beyond 30 layers while vanilla GCN collapses. PairNorm: Tackling Oversmoothing in GNNs also needs a global centering step and a global Frobenius-norm rescaling. These two papers supply the method we decentralize. Both assume all $n$ node features are visible at once.

The naive decentralized version replaces the global mean with $r$ rounds of neighbor averaging. Let $P$ be the doubly stochastic mixing matrix, a neighbor-averaging matrix whose rows and columns each sum to one. Each node's estimate of the mean of $h$ is then $(P^r h)_i$, and one corrected layer becomes the operator $P - P^r$. Let $v_2$ be the slowest-decaying non-constant direction, the community direction that corrected convolutions are designed to amplify relative to everything else, with eigenvalue $\lambda_2$ under $P$. Along $v_2$ the naive operator has gain

$$\lambda_2 - \lambda_2^{\,r},$$

which follows directly from applying $P - P^r$ to an eigenvector. On large-diameter sensor graphs $\lambda_2$ is close to 1, so this gain is near zero unless $r$ approaches the mixing time, roughly $1/(1-\lambda_2)$ rounds. Cheap per-layer gossip therefore removes the signal along with the mean.

Our alternative keeps, for each layer $l$, a running estimate $\hat m_i^{(l)}(t)$ at node $i$ that is updated once per time step $t$:

$$\hat m_i^{(l)}(t) = \sum_{j \in \mathcal{N}_i} W_{ij}\, \hat m_j^{(l)}(t-1) + \big(h_i^{(l)}(t) - h_i^{(l)}(t-1)\big).$$

Here $W$ is the doubly stochastic weight matrix of the communication graph, $\mathcal{N}_i$ is node $i$'s neighbor set, and $h_i^{(l)}(t)$ is node $i$'s layer-$l$ pre-correction feature. The first term is the consensus term and the second is the innovation, meaning the change in local data. Because $W$ preserves averages, the network-wide average of $\hat m$ equals the true mean of $h^{(l)}$ at all times. The per-node error contracts by the second-largest eigenvalue magnitude $\rho$ of $W$ at each step and is refreshed by feature drift. Summing that geometric series gives a steady-state error of order $\|\Delta h\|/(1-\rho)$. This is the same tracking-capacity trade-off that Consensus+Innovations Distributed Kalman Filter with Optimized Gains identifies for distributed filters, now governing how much of the over-smoothing mode leaks back into a deep GNN. PairNorm's scale is tracked the same way, using the mean squared norm.

Research Program

The first part is analysis. We extend the corrected-convolution argument to imperfect, node-varying mean estimates. The leaked component has two parts. One is common to all nodes and is harmless, since a classifier bias absorbs it. The other varies across nodes and acts as noise injected into the informative subspace. We bound classification error as a function of tracker error, depth, $\lambda_2$ of the data graph and $\rho$ of the communication graph. We then derive the drift rate beyond which the tracked model degrades to vanilla behavior. The theory will be linear, as in the source paper. Its assumptions of balanced classes and linear readout are acknowledged limits, and we test them empirically with ReLU networks and imbalanced classes rather than claim them.

The second part is the system. Weights are trained centrally offline, which is acceptable because the bottleneck at issue is in deployment. Inference is fully decentralized: every layer's message carries the feature vector plus the tracker state. We add channel noise following the additive link-noise model of Performance Analysis of the Consensus-Based Distributed LMS Algorithm, plus random packet drops. Training injects simulated tracker error so the weights are robust to it.

The third part turns the benchmarks into a sensor setting. Static benchmarks become streams by having each node observe noisy, slowly drifting versions of its features over time, with the drift rate as a controlled knob. This is the regime in which the innovation term does real work.

Baselines

The naive reference points are a shallow two-layer GCN run decentrally and a deep vanilla GCN run decentrally. Neither needs global information, and together they show what over-smoothing costs here. They run on the same communication graph, with the same noise and the same hyperparameter search budget as every other method.

The strongest method overall is centralized corrected convolution and centralized PairNorm with exact global statistics, an oracle that a fusion center would provide. On Cora under missing features, where unlabeled nodes have no features at all, PairNorm reports 74.5% accuracy for SGC versus 42.3% for vanilla (PairNorm). For corrected convolutions on Cora, CiteSeer and PubMed, the file reports only that accuracy holds beyond 30 layers, with no exact percentage. We will reproduce both under our splits. Beating this baseline is not the aim. Success means coming within two accuracy points of the oracle at the same depth, while using per-node communication that does not grow with network diameter.

The strongest decentralized competitor is naive per-layer gossip with $r$ rounds. We sweep $r$ and report accuracy against messages per node, so the comparison is at matched communication. The tracker wins if it dominates this accuracy–communication curve, especially on graphs with $\lambda_2$ near 1.

The strongest local anti-oversmoothing method is the filterbank high-pass "diversification" channel of Complete the Missing Half. It reports roughly 10% gains on Texas and Cornell and is fully local by construction. We also include an initial-feature injection baseline, which re-adds each node's input features at every layer. Both are tuned with the same budget.

A deferred-correction baseline exploits the identity that for linear propagation $P^k - \frac{1}{n}\mathbf{1}\mathbf{1}^\top$ needs only one global mean, computed at the end. It isolates whether per-layer correction matters once nonlinearity and channel noise are present. The key ablation swaps the tracker for the oracle mean and for a cold-started tracker, which isolates warm-starting across time as the ingredient that does the work.

Why not just…?

Why not just use a local high-pass channel, which is already decentralized? The filterbank channel subtracts neighbor averages, which suppresses every slowly varying pattern, including the community-scale direction $v_2$. Removing only the constant mode preserves that direction. On homophilic graphs and in the missing-features regime, local high-pass should therefore lose to tracked correction as depth grows. On heterophilic Texas and Cornell, however, high-frequency information is what matters, and the filterbank may win outright. We will report this honestly. A combined model with a tracked low-pass branch plus a local high-pass branch is the natural outcome if both effects appear.

Why not just keep the network shallow? Under PairNorm's missing-features setting, shallow models fall to the 42.3% vanilla level because information must travel far. GwAC shows synchronous shallow models collapsing to random guessing on shortest-path parity at 1,000 nodes. Sensor graphs such as the 300- and 1,000-agent geometric networks in Distributed Sequential Detection have large diameter. The depth-versus-accuracy curves will show directly whether depth pays off in our streams.

Why not just re-inject initial features each layer, the local innovation idea itself? This is a serious threat, because it is local and prevents collapse. Feature injection limits how far information effectively travels, to a horizon set by the injection weight, and it injects nothing for nodes whose features are missing. We test it head-to-head on the missing-features and long-range tasks. If it matches the tracker there, the global-mean machinery is unnecessary and we will say so.

Why not just compress and stream data to a server? That restores the single point of failure and the energy drain on nodes near the hub that CIKF and flood-sensing deployments document. We keep the centralized oracle as the accuracy ceiling and report how much accuracy decentralization costs, rather than pretending the cost is zero.

Proposed Experiments

The first benchmark is the contextual stochastic block model with $n=2{,}000$ nodes, following Analysis of Corrected Graph Convolutions. We vary the communication graph from a ring or lattice ($\lambda_2$ near 1) to an expander, and measure the gain along $v_2$ and the error per layer. The decisive check is whether naive gossip's accuracy tracks the predicted $\lambda_2 - \lambda_2^r$ curve.

The second is Cora, CiteSeer and PubMed under the missing-features protocol and as drifting streams. We report accuracy at depths up to 60, against messages per node and against drift rate. The decisive check is a measured breakdown drift rate that scales with $1-\rho$, as the tracking-capacity bound predicts.

The third is METR-LA and PEMS-BAY, with deep spatial propagation over the sensor graph and decentralized execution. D2STGNN's reported 2.6% MAE gain over prior methods (D2STGNN) serves as a centralized reference; no absolute MAE was found on Lacuna. We also run the 50-agent lattice field from the CIKF testbed to stress unstable dynamics.

Across all settings we measure the fraction of feature energy in the constant mode, which shows directly whether over-smoothing returns, together with accuracy or MAE. We also vary link-noise variance and drop rate. The proposal fails if, at matched communication, the tracker does not beat naive gossip on graphs with $\lambda_2$ near 1, or if initial-feature injection matches it on long-range tasks.