Can a Discriminator Tell Neighbors Apart? A Two-Sample Test for Over-Smoothing

Deep graph neural networks build a representation for each node by repeatedly averaging the features of its neighbors. The standard worry, called over-smoothing, is that after many rounds of averaging every node looks the same and the network can no longer separate classes. The field cannot yet agree on whether this actually happens or why. The usual gauges disagree with accuracy. One is Dirichlet energy, which sums how different adjacent nodes' vectors are. Another is effective rank, a smooth count of how many independent directions the node-feature matrix spans. On Cora, a 10-layer graph convolutional network loses much of its accuracy while its energy barely moves (Are we measuring oversmoothing in graph neural networks correctly?). Rank tracks accuracy better, but random noise also has full rank. A separate line of work argues that the averaging step is not the culprit at all and that the real problem is ordinary vanishing signal through weights and nonlinearities (The Oversmoothing Fallacy). Without a measurement that distinguishes "collapsed" from "noisy" from "informative," that dispute cannot be settled.

We propose to borrow the one part of generative adversarial networks that is well understood: the discriminator. In a GAN, a classifier is trained to tell real samples from generated ones, and at its optimum it estimates the ratio between the two densities, which makes it a learned two-sample test (Learning in Implicit Generative Models). Our test works as follows. At each layer, a small discriminator sees a node's hidden vector paired with a description of some node's raw input. It must decide whether the pairing is genuine or whether the description was swapped for one taken from a node exactly $r$ hops away. If representations have smoothed over radius $r$, the discriminator cannot tell a node from its $r$-hop neighbors. If representations are noise, it cannot tell either. Only representations that keep node-specific, input-grounded information pass. The result is a per-layer, per-radius profile of how far smoothing has spread. We use it first to settle the measurement question. We then ask whether training against it helps where existing remedies do not.

Core Claim

Over-smoothing should be measured as a loss of distinguishability between a node and its graph neighbors, grounded in the input, not as low energy or low rank. A discriminator trained to separate matched from hop-shuffled pairs estimates this directly. Formally, let $h_v^{\ell}$ be node $v$'s representation at layer $\ell$, and let $c_u$ be a fixed descriptor of node $u$: its raw features concatenated with the mean raw features of its 1-hop neighbors. Train a discriminator $D$ on held-in nodes with label 1 for pairs $(h_v^{\ell}, c_v)$ and label 0 for pairs $(h_v^{\ell}, c_u)$, where $u$ is drawn uniformly from the set of nodes at shortest-path distance exactly $r$ from $v$. With balanced classes, the optimal discriminator satisfies $D/(1-D) = p(h,c)/q_r(h,c)$, so the held-out score

$$I_r^{\ell} = \mathbb{E}_{v}\left[\log \frac{D(h_v^{\ell}, c_v)}{1 - D(h_v^{\ell}, c_v)}\right]$$

estimates the KL divergence between the true pairing and the $r$-hop-shuffled pairing. Here $p$ is the density of matched pairs and $q_r$ is the density of hop-shuffled pairs. Because the estimator comes from a finite-capacity classifier, it is a lower bound in practice. $I_r^{\ell}$ is near zero both when nodes within radius $r$ have collapsed onto each other and when representations carry no information about inputs. It is large only when the representation still says which node it belongs to relative to nearby nodes. Plotting $I_r^{\ell}$ against $r$ and $\ell$ gives a smoothing-radius map. We claim this map predicts accuracy better than energy or rank, and that it is immune to the two known failure cases: normalization layers, which inflate energy, and noise, which inflates rank.

The new element is not "add a discriminator to a GNN." It is the hop-stratified negative distribution, which makes the test specific to graph smoothing, combined with the density-ratio reading, which makes it a calibrated quantity rather than a heuristic score.

Relation to Prior Work

Three papers motivate the proposal by showing the measurement gap. Are we measuring oversmoothing in graph neural networks correctly? shows energy is misleading and that effective rank correlates with accuracy, while conceding that rank is necessary but not sufficient. Our test adds the missing sufficiency side by requiring input grounding. Backward Oversmoothing shows that gradients reaching early layers collapse to constants, so early layers stay near initialization. That implies representations at those layers may be high-rank but uninformative, which is exactly the case our test is built to detect. The Oversmoothing Fallacy attributes collapse to the weight-plus-nonlinearity step rather than to aggregation, and shows that skip connections with batch normalization train GCNs and GATs to 1,024 layers. It is the paper most likely to contradict us. If it is right, our metric should show $I_r^{\ell}$ dropping across the transformation step and not across the aggregation step. We treat that as a hypothesis to test, not something to argue against.

DrGNN is the closest existing work. It combines depth-decaying residuals with a contrastive loss that pulls connected nodes together and pushes disconnected ones apart. It interprets that loss as an implicit GAN objective, with the GNN acting as generator. We differ in two ways. Our discriminator is an explicit, separately trained network used as a measurement instrument, rather than a fixed loss folded into training. Our negatives are hop-stratified, so the test asks "can you tell me from my $r$-hop neighbors" rather than "are we connected." That is the opposite direction to DrGNN's pull-together term on edges. GraphGAN runs a minimax game between a neighbor generator and an edge discriminator. Its embeddings are lookup tables with no message passing, so it never meets over-smoothing. We reuse only its idea that a discriminator over node pairs is informative about graph structure. DeepDRK is relevant as a cautionary analogue. Its adversarially trained knockoff generators fall into a "copycat" mode where samples copy inputs. The analogous risk for us is a GNN that passes the test by copying raw features and ignoring the graph. We guard against this by comparing to a feature-only MLP, described below.

Research Program

The first stage builds and validates the instrument. The discriminator is a two-layer MLP of fixed width applied to the concatenation of $h_v^{\ell}$ and $c_u$. It is trained on 50% of nodes and scored on the rest. Its capacity, training steps, and learning rate are frozen across all datasets, depths, and architectures, so that differences in $I_r^{\ell}$ reflect the representations rather than the probe. We will check calibration on synthetic stochastic block graphs, where the true mixing radius of an $\ell$-step averaging operator is known. Two failure cases also have known answers. Representations replaced by Gaussian noise should give $I_r^{\ell} \approx 0$ at full rank. Representations set to the class mean should give $I_r^{\ell} \approx 0$ for all $r$ within a community. Capacity sensitivity will be reported by doubling and halving discriminator width.

The second stage uses the instrument to adjudicate the aggregation-versus-transformation dispute. Each layer is split into its aggregation step and its weight-plus-activation step. We measure $I_r$ after each, on vanilla GCN, on GCN with skip connections and batch normalization, and on GCNII, at depths 2 through 64 (and 256 for the skip-plus-BN model). If the drop in distinguishability concentrates in the transformation step, the Fallacy authors are vindicated in a way that energy-based analyses could not show. If it concentrates in aggregation and grows with $r$ in the way a low-pass filter predicts, the classical view survives.

The third stage asks whether the instrument is also a useful training signal. Each intermediate layer gets an auxiliary loss equal to $-I_r^{\ell}$ for a small set of radii, with the discriminator updated alternately as in GAN training. This gives early layers a gradient that does not pass through the final classifier, which directly targets the backward-oversmoothing trap. This stage is deliberately secondary, because several simpler signals could do the same job, as discussed below.

Proposed Experiments

We use the benchmarks in the file. Cora, CiteSeer, and PubMed cover homophilic graphs. Chameleon, Squirrel, Amazon Ratings, Texas, and Wisconsin cover heterophilic graphs, where the radius profile should look qualitatively different because neighbors are often in other classes. ogbn-arxiv from the Open Graph Benchmark tests whether the probe scales with mini-batched neighbor sampling. For the metric study, the primary statistic is the Pearson correlation between each metric and test accuracy across all (architecture, depth, dataset) runs. The secondary statistic is correlation within the subset where normalization or noise is present, which is where energy and rank are known to fail. For the training study, the metric is node-classification test accuracy at fixed depths of 8, 16, 32, and 64, plus the gradient norm reaching layer 1.

Baselines

For the metric study, the do-nothing reference is Dirichlet energy, computed exactly as in Are we measuring oversmoothing in graph neural networks correctly?. The strongest existing competitor is effective rank from the same paper, which reports a Pearson correlation with accuracy "averaging 0.91" across architectures. Our metric must exceed that average on the same datasets and architectures. More importantly, it must keep a high correlation in the noise-injected and normalized runs, where we expect rank to break. Matching 0.91 overall while losing in those runs would count as failure. We also run a per-layer linear label probe: a logistic regression from $h_v^{\ell}$ to class labels, trained with the same node split and budget as our discriminator. It is the obvious supervised competitor. The key ablation replaces hop-stratified negatives with uniformly random negatives, keeping everything else fixed. If the uniform version predicts accuracy just as well, the graph-specific part of the idea adds nothing.

For the training study, the do-nothing reference is a vanilla GCN at the same depth. The skip-plus-batch-norm GCN from The Oversmoothing Fallacy is the simplest strong competitor. The strongest reported deep model in the file is DrGNN, which reports "~80% accuracy at 64 layers" on Cora versus "~32%" for standard GCN. WeightRep reports gains of 5.50% and 55.12% over 4- and 8-layer GCN on Cora. GCNII has no exact accuracy figure in the file, only that its best Cora model has 64 layers; we will rerun it.

Two further baselines isolate what the discriminator contributes. The first is a non-adversarial rank regularizer: a penalty on the variance and covariance of each layer's node matrix, which pushes toward high rank directly. The second is deep supervision: a label head at every layer. All models get the same splits, the same 64-layer depth, and the same hyperparameter search of 50 trials per method on validation accuracy, with five seeds. Beating DrGNN means exceeding its 64-layer Cora accuracy by more than seed variance, and doing so on at least the heterophilic datasets as well. Matching but not beating the rank regularizer or deep supervision would mean the adversarial training signal is unnecessary.

Why not just…?

Why not just use effective rank with a noise check? Rank already correlates with accuracy at 0.91 on average, and one could add a separate test for noise. But "is this noise" is exactly the hard question. Partially noisy, partially collapsed representations are the realistic case under backward oversmoothing (Backward Oversmoothing), because early layers stay near random initialization. Rank cannot say how much of the spanned space is input-grounded. Our noise-injection experiments mix noise into real representations at controlled fractions, which gives rank and our score a direct head-to-head comparison.

Why not just probe for labels at each layer? A label probe is a real threat for predicting accuracy, since it nearly measures accuracy itself. It needs labels, though, and it cannot localize smoothing to a radius or to the aggregation versus transformation step. We report it anyway. If it dominates our metric on correlation, we will say so and claim only the diagnostic uses.

Why not just use skip connections and batch normalization and declare over-smoothing solved? The Oversmoothing Fallacy shows these train to 1,024 layers, and this may well match any auxiliary loss we add. That outcome would not sink the proposal's main claim, which is about measurement. The layer-dissection study is designed to explain why skip-plus-BN works, and the training study treats skip-plus-BN as the bar to clear.

Why not just use DrGNN's contrastive loss, which is already an implicit GAN? DrGNN's loss uses fixed edge and non-edge pairs and pulls neighbors together. It is a training objective, not a held-out estimator, so it cannot audit other architectures. For training, the uniform-negative ablation and the rank-regularizer baseline test whether an adaptive, hop-stratified discriminator adds anything over a fixed loss. If it does not, we will drop the adversarial training stage and keep the instrument.

Decisive Checks

Three results would settle the proposal. First, under controlled noise injection, effective rank stays near maximal while $I_r^{\ell}$ and accuracy fall together. Second, across all runs including normalized ones, $I_r^{\ell}$ correlates with accuracy above the 0.91 rank average, and the hop-stratified version beats the uniform-negative ablation. Third, the layer dissection gives an unambiguous answer about whether distinguishability is lost in aggregation or in transformation. Consistent with The Oversmoothing Fallacy, we will also check that a feature-only MLP does not score as high as deep GNNs at small $r$. Such a score would mean the test rewards copying inputs rather than graph-aware representations.