Natural Label Noise Is Smooth on the Graph, and Deep GNNs Should Be Tested That Way

Graph neural networks (GNNs) are models that predict a node's label by repeatedly averaging information from its neighbors. Researchers measure their robustness to wrong labels mostly by flipping training labels at random. Real annotation mistakes are not random in this way. They cluster on ambiguous nodes, and on a graph, ambiguous nodes tend to sit next to each other: along community boundaries, inside topical overlaps, among products that resemble one another. Our claim is that this clustering is the main thing synthetic graph label noise gets wrong, and that it has a predictable consequence once networks get deep. Neighbor averaging is a smoothing filter. Smoothing cancels errors that are scattered independently across nodes, but it preserves and spreads errors that are themselves smooth over the graph. So the standard advice about depth and about methods that prevent over-smoothing (the collapse of all node representations toward one vector as layers are stacked) may be right for synthetic noise and wrong for natural noise.

The project has three parts. First, we measure the "graph frequency" of a noise process, meaning how smoothly the error pattern varies across edges, for both synthetic and realistic noise. Second, we test whether that one property explains why deep models and anti-over-smoothing methods behave differently under the two. Third, we build a cheap synthetic noise generator matched on this property, and we check whether it reproduces the method rankings that expensive, LLM-simulated human noise produces. If the account holds, robustness benchmarks for deep GNNs can be repaired with a single calibrated knob instead of an LLM annotation pass per dataset.

Core Claim

Let $e \in \{0,1\}^n$ mark which of the $n$ nodes carry a wrong label. Let $L$ be the normalized graph Laplacian, with eigenvalues $\lambda_i \in [0,2]$ and eigenvectors $u_i$, and let $\hat e_i = u_i^\top e$ be the components of the error pattern in that basis. For a linear propagation operator $P = I - L$ applied $K$ times, the error energy that survives is

$$ \|P^K e\|^2 = \sum_i (1-\lambda_i)^{2K}\, \hat e_i^{\,2}. $$

The equation says that low-frequency error components (small $\lambda_i$, smooth across edges) survive many rounds of averaging, and high-frequency components are suppressed at a geometric rate. This is a statement about the linear part of message passing, not a theorem about trained nonlinear GNNs, which is why it needs to be tested. Uniform label flips are spread close to evenly across the spectrum, so depth averages much of them away. We hypothesize that natural noise puts disproportionate energy at low $\lambda$.

The summary statistic we use is the normalized smoothness of the error pattern, $S(e) = e^\top L e / \mathbb{E}_\pi[\pi(e)^\top L \pi(e)]$, where $\pi$ randomly permutes which nodes are corrupted. $S<1$ means errors cluster along edges. We also keep the full spectral profile. The concrete predictions are as follows. Under realistic noise, accuracy should degrade more with depth than under uniform noise at the same rate. Methods that restore high-frequency signal should help less, or hurt. The gap between synthetic and natural results should shrink when the synthetic noise is given the natural noise's spectrum.

Grounding in Prior Work

The motivating evidence comes from two label-noise benchmarks. Delving into Instance-Dependent Label Noise in Graph Data (BeGIN) uses GPT-4o-mini to read node text and simulate human annotation errors. It finds this noise far more damaging than class-dependent flips at equal rates. It also finds that GraphSAGE, which keeps a node's own features separate from its neighbors', is the most robust backbone. However, it evaluates only two-layer models and does not ask why the LLM noise hurts more. NoisyGL documents a "telephone effect", in which corrupted labels spread through edges into clean neighborhoods. It finds that systematic pair noise is worse than uniform noise and that edge cleaning beats loss correction. It too uses shallow backbones and class-dependent noise only. We contribute a mechanism that predicts when the telephone effect is strongest, namely when the noise is spatially smooth, and we take the question to depth.

The textual robustness literature supplies the general lesson. Synthetic and Natural Noise Both Break Neural Machine Translation and Training on Synthetic Noise Improves Robustness to Natural Noise in Machine Translation show that training on synthetic perturbations transfers only partially to natural ones, and that better-matched generators narrow the gap. NeuSpell improves transfer by encoding real error structure such as keyboard adjacency. Our generator is the graph analogue. We keep the generator simple, but we match the one structural property we argue matters.

The over-smoothing literature supplies both the methods under test and a constraint on measurement. PairNorm keeps total pairwise distance between node representations fixed. Complete the Missing Half and Scattering GCN add high-pass channels. Multi-Track Message Passing routes messages along category-specific tracks inferred from pseudo-labels. Each method was designed and evaluated on clean labels, under the implicit assumption that high-frequency content is signal. MTGCN depends on pseudo-labels in a way that clustered noise could systematically corrupt. Are we measuring oversmoothing correctly? constrains our diagnostics. It shows that Dirichlet energy misses collapse in trained networks, whereas effective rank tracks accuracy with an average correlation of 0.91. It also warns that high rank can simply mean noise. We therefore report effective rank alongside accuracy and never read high rank as health.

Finally, Shedding Light on Random Dropping and Oversmoothing shows that DropEdge works mainly as a training regularizer and does little against over-smoothing at test time. It also introduces Learn2Drop, which learns a message mask at test time. Neither paper evaluates under label noise, and that is the condition we add.

Research Program

The first step is measurement. On the text-attributed graphs where BeGIN provides LLM-simulated noise (History, Children, Photo, Product-s, WikiCS, Cora-ML), we compute $S(e)$ and the spectral profile of $e$ for several noise processes. These are uniform flips, NoisyGL-style pair flips, BeGIN's algorithmic instance-dependent variants (topology-, feature-, and confidence-based), and BeGIN's LLM noise, all at matched rates. On the heterophilic graphs (Texas, Wisconsin, Cornell, Washington), we measure only the algorithmic variants. We expect them to show a weaker or reversed pattern, because smoothing on heterophilic graphs mixes across classes.

The second step is a depth sweep. We train GCN, GraphSAGE, and GAT at 2, 4, 8, 16, 32, and 64 layers under every noise process. Each depth is run plain and with PairNorm, a diversification high-pass channel, DropEdge, Learn2Drop, and MTGCN. We log test accuracy on clean labels and the effective rank of each layer's features. We also log a measure of noise propagation: the accuracy on clean training-neighborhood nodes that are $k$ hops from a corrupted node.

The third step builds the generator. We sample a latent field $z = (I + \alpha L)^{-1} g$ from Gaussian noise $g$. We flip the top-$r$ fraction of nodes by $z$. Each flipped label's new class is drawn from a class-confusion matrix, either uniform or one estimated from data. The parameter $\alpha$ sets how smooth the corruption is, and $\alpha = 0$ recovers uniform placement. We fit $\alpha$ on one graph to match the LLM noise's $S(e)$. Then we test whether the same $\alpha$, or an $\alpha$ predicted from feature-space ambiguity alone, transfers to other graphs. Transfer matters, because only then can the generator stand in for natural noise on graphs that have no text.

Baselines

The naive reference point is a shallow backbone with no defense, trained on the same noisy labels. The strongest shallow number in the file is GraphSAGE on History, which BeGIN reports at 83.2% accuracy clean and 66.5% under LLM noise (BeGIN). We rerun this exact configuration as a sanity check before any deep experiment. A deep model that cannot beat its own two-layer version under natural noise is itself an informative result, and the depth sweep reports it directly.

The strongest anti-over-smoothing competitors are Learn2Drop and MTGCN, because each preserves accuracy at large depth on clean labels. Learn2Drop is reported at 69.3% accuracy with a 64-layer GCN on Cora (Shedding Light on Random Dropping). MTGCN is reported at 86.4% on Cora, along with 92.10% on Texas and 90.20% on Wisconsin, all on clean labels (Multi-Track Message Passing). We found no reported result on Lacuna for any deep GNN or anti-over-smoothing method under LLM-simulated label noise. That gap is exactly what we fill. PairNorm, DropEdge, and the diversification channel join them as cheaper anti-over-smoothing defenses. On the noise-robustness side, we include the graph-specific methods NoisyGL found strongest, NRGNN and RTGNN, at two layers and at the deepest depth where they train stably. NoisyGL reports that NRGNN and PIGNN stay well above vanilla GCN on DBLP at 30% uniform noise. We will check whether that ordering survives smooth noise.

For fairness, every method gets the same splits, the same noisy label draws (five seeds per noise process), and the same hyperparameter budget. Hyperparameters are selected on a validation set carrying the same noise as training, because clean validation labels would be unavailable in practice. Every method also runs on the same hardware.

For the generator, the baselines are uniform, pair, and BeGIN's algorithmic instance-dependent noise. The key ablation is "placement-shuffled natural noise". We take the LLM noisy labels and keep each true class's confusion counts exactly. We then randomly reassign which nodes within that class receive the flips. This leaves the class-level noise statistics untouched and destroys only the spatial structure. The spectral generator "wins" if two conditions hold. Its Spearman correlation between method rankings under the generator and method rankings under LLM noise must exceed that of every baseline generator, across depths and datasets. And it must predict the LLM-noise accuracy drop at each depth to within the seed-to-seed spread.

Why not just…?

Why not just use BeGIN's LLM noise at depth and skip the spectral story? That gives a benchmark but no explanation, and it only exists for graphs with text and a paid annotation pass. If the depth sweep under LLM noise showed the predicted pattern while the shuffled ablation did not, we would know what makes the noise harmful. We could then generate it on any graph. If the shuffled ablation behaves like the real LLM noise, the spectral account is wrong, and we would report that.

Why not just use BeGIN's feature- or topology-based instance-dependent noise as the realistic generator? This is the real threat. Those generators target boundary and outlier nodes, which are likely already spatially clustered, so they may already have low $S(e)$. We include them as generators in the ranking-fidelity test and measure their spectra. If one of them matches LLM noise as well as our field-based sampler, the honest conclusion is that the explanation holds and the existing generator suffices. The contribution then shrinks to the mechanism and the depth findings. The advantage we expect for our sampler is that $\alpha$ can be calibrated and transferred. We test that claim directly, and we drop it if it fails.

Why not just use pair noise, which NoisyGL already found more destructive? Pair noise changes which wrong class is chosen, not where the errors land. The shuffled ablation separates the two effects, because it keeps natural class confusions while randomizing placement. If shuffled natural noise is as damaging at depth as the real thing, then class confusion rather than spatial smoothness is the driver, and our claim fails.

Why not just keep models shallow? Under natural noise this may turn out to be the right recommendation, and the depth sweep will say so plainly. Shallow models are not a general answer, though. PairNorm reports 74.5% versus 42.3% for vanilla SGC on Cora when unlabeled nodes lack features, a case where deeper propagation is needed. MTGCN's Tree-NeighborsMatch results show shallow models failing beyond depth 5. Our goal is to tell practitioners how noise structure should change the depth choice, not to argue for depth.

Why not just apply Co-teaching or loss correction? NoisyGL found that general label-noise methods give little benefit on graphs, because errors spread across edges. Smooth noise should make this worse: the small-loss samples Co-teaching trusts will include whole consistent clusters of wrong labels. We run Co-teaching using the public implementation as a secondary baseline to confirm this.

Decisive Checks

Three outcomes would settle the claim. First, LLM noise must have measurably lower $S(e)$ than uniform noise on the BeGIN text graphs. If it does not, the project stops there with a negative result. Second, the accuracy-versus-depth curve under LLM noise must fall faster than under uniform noise, and the placement-shuffled version must follow the uniform curve rather than the LLM curve. Third, the relative benefit of PairNorm and the high-pass channel over a plain deep GCN must shrink or reverse under LLM noise compared with uniform noise. This would show up together with effective rank staying high while accuracy falls, which would confirm that rank cannot separate preserved signal from preserved noise.

If all three hold and the fitted $\alpha$ transfers across at least most of the six text graphs, we will release the generator as a drop-in replacement for uniform flips in deep GNN robustness evaluation.