Certified Rank: Tracking How Edge Uncertainty Compounds Into Over-Smoothing

Graph neural networks build each node's representation by repeatedly averaging it with its neighbors' representations. After enough rounds, every node looks alike. This failure is called over-smoothing. It is worst on graphs where linked nodes often belong to different classes, which is the "heterophilic" setting. A large share of recent fixes boil down to deciding, edge by edge, whether to pass a message, block it, or flip its sign. They make that decision with a single number per edge. That number cannot tell apart two very different situations: an edge we have good reason to distrust, and an edge we simply know nothing about. Fuzzy and interval graph theory has long modeled edges as ranges of plausible strength rather than points, but almost none of that work has reached deep graph learning.

This note proposes to carry an interval of plausible signed strengths on every edge through every layer of a network, using differentiable interval arithmetic. The network then outputs two things: a central embedding, and a radius that bounds how far the embedding could move under any edge realization consistent with the intervals. That pair yields a quantity no current over-smoothing measure provides: a certified rank, meaning a lower bound on the dimensionality the representation keeps no matter how the uncertain edges resolve. The note asks two questions. Does certified rank predict accuracy collapse with depth better than the rank metrics computed on a single embedding? Does training to keep it high beat the strongest edge-calibration and heterophily methods on leak-free benchmarks?

Core Claim

Prior work treats edge uncertainty as something to resolve before propagation. It either estimates a weight and commits to it, or blocks the edge. The claim here is that uncertainty should instead be propagated, and over-smoothing measured on the worst case it permits.

The motivation comes from three findings. Better Not to Propagate proved, on contextual stochastic block models, that propagating wrongly signed edges spreads class information into noise faster than plain smoothing does. It responds with an expectation-maximization calibration that ends in a hard choice per edge: signed propagation or zero weight. Are we measuring oversmoothing correctly? showed that over-smoothing in trained networks is a collapse in matrix rank, not in Dirichlet energy. Its effective rank correlates with accuracy at an average Pearson coefficient of 0.91. The same paper notes that high rank is necessary but not sufficient, since random noise also has full rank.

These two findings connect. A representation that keeps high rank only because uncertain edges inject arbitrary directions has the "noise rank" that paper warns about. Certified rank discounts exactly that contribution, because it subtracts the volume that uncertain edges could account for.

The relational-modeling literature supplies the edge object. Cubic fuzzy graphs pair an interval of membership with a point likelihood. They also show that deleting an edge can change global connectedness (the Wiener index) non-monotonically, which is a structural argument against hard pruning. Vague influence graphs make an edge's agreement and disagreement memberships depend on its endpoint vertices. We borrow both ideas. Each edge gets an interval, and that interval is built from its endpoints' predictive uncertainty. We do not borrow these papers' combinatorial indices (domination numbers, Wiener indices), which have only been computed on toy networks.

Research Program

Building the edge intervals. For edge $(i,j)$, we train a small ensemble of feature-only models, which never see the graph. Each member gives a probability that $i$ and $j$ share a class. The lowest and highest of these probabilities, mapped to the signed range $[-1,1]$, form the edge interval $[a^-_{ij}, a^+_{ij}]$. A confident pair yields a narrow interval near $+1$ or $-1$. An ambiguous pair yields a wide one. This follows the vertex-to-edge influence idea: an edge is only as certain as its endpoints. Unlike Choi et al., we do not threshold the interval into a decision.

Interval message passing. We write the interval adjacency in center–radius form: center $A_c = (A^+ + A^-)/2$ and radius $A_r = (A^+ - A^-)/2$. We write node embeddings at layer $l$ as center $C^{(l)}$ and nonnegative radius $R^{(l)}$. Standard interval arithmetic then gives

$$ C^{(l+1)} = \phi\!\left(A_c C^{(l)} W^{(l)}\right),\qquad R^{(l+1)} = \left(|A_c| R^{(l)} + A_r |C^{(l)}| + A_r R^{(l)}\right)|W^{(l)}|, $$

where $W^{(l)}$ is the channel-mixing matrix, $|\cdot|$ is the entrywise absolute value, and $\phi$ is a 1-Lipschitz activation such as ReLU. Because $\phi$ is 1-Lipschitz, the radius stays a valid bound after the activation.

Every operation is continuous and differentiable almost everywhere. This avoids the non-continuous order-based aggregator of IV-GNN, whose instability its authors acknowledge. IV-GNN also handles only interval node features, never interval edges, and never studies depth. We add residual and ego-separated variants of the update. Understanding convolution on graphs via energies proves residual connections are needed to reach high-frequency, sharpening behavior. Ego separation is the simple fix that Platonov et al. found dominant on clean benchmarks.

Certified rank. Any embedding $H$ consistent with the edge intervals differs from $C$ entrywise by at most $R$. Therefore $\|H - C\|_2 \le \|R\|_F$. Weyl's inequality then gives

$$ \sigma_k(H) \;\ge\; \sigma_k(C) - \|R\|_F \quad \text{for every such } H, $$

where $\sigma_k$ denotes the $k$-th singular value. We define certified numerical rank as the number of singular values of $C$ that exceed $\|R\|_F$. We define a scale-invariant certified effective rank by computing effective rank on the clipped spectrum $\max(\sigma_k(C) - \|R\|_F, 0)$, after normalizing by $\|C\|_F$. The normalization follows Zhang et al.'s argument for scale-invariant measures.

Training objective. The objective is cross-entropy on the center plus a hinge penalty. The penalty pushes the margin $\sigma_k(C) - \|R\|_F$ above zero for $k$ up to the number of classes.

The analysis claim. The radius grows multiplicatively with depth, in proportion to $A_r$. The depth at which certified rank falls below the class count should mark where accuracy collapses. That point should come earlier and more sharply than plain effective rank indicates on heterophilic graphs.

Baselines

The naive reference point is a standard graph convolutional network (GCN) and graph attention network (GAT), plus a graph-agnostic ResNet on node features. Platonov et al. found that many specialized heterophily models fail to beat that ResNet, so any gain must clear it first.

The strongest simple competitor is GCN and GAT with ego–neighbor separation and residuals, as in Platonov et al.. These variants took 13 of the top 15 spots on the filtered heterophily suite. Our model uses the same backbone, so any gain is attributable to the intervals.

The closest existing method is the calibrated GPRGNN* of Better Not to Propagate. It reports an 8.47% accuracy gain over GPRGNN on Actor and a 6.62% gain on Squirrel. Squirrel is a duplicated dataset, so we rerun this method on the clean suite.

The strongest broad competitors are two published methods. The first is CMGNN from Understanding and Enhancing Message Passing via Compatibility Matrix, which reports an average rank of 1.3 across 20 baselines on heterophilic subsets. We run it through its official CMGNN codebase. The second is Cooperative Sheaf Neural Networks, reported as top performer on 6 of 7 Platonov datasets. I found no reported result on Lacuna for per-dataset absolute accuracies of CSNN or CMGNN on roman-empire or minesweeper. We therefore reproduce both rather than quote them. We also include the residual gradient-flow GCN from the energies paper, which reports about 84% on Texas against 60% for GCN.

The key ablations isolate the interval.

  • Center-only: set $R \equiv 0$, which is equivalent to midpoint weights, with the identical ensemble and backbone.
  • Monte Carlo edges: sample edge weights uniformly within the intervals at each step.
  • Scalar gate: a GAT-style gate that receives the interval's mean and width as inputs.
  • No rank penalty: train without the hinge term.

All methods share the same splits and the same depth grid from 2 to 64 layers. Each gets an equal hyperparameter search budget of 100 random configurations under the same GPU-hour cap. The ensemble's training cost is counted in our model's budget.

Beating the baselines means two things. First, mean accuracy (ROC-AUC where the benchmark specifies it) must exceed the best of ego-separated GCN/GAT, CMGNN, CSNN, and GPRGNN* on at least four of the seven clean heterophilic datasets, by more than one standard deviation over ten splits. Second, the interval model's accuracy must degrade measurably less across the depth sweep.

Why not just…?

Why not just separate ego and neighbor embeddings? This is the most serious threat on accuracy alone, given Platonov et al.'s results. Ego separation protects a node's own identity at each layer. It does nothing about which incoming neighbor messages are trustworthy. Our model uses ego separation as its backbone, so the comparison is clean: if intervals add nothing on top of it, the center-only ablation will tie the full model.

Why not just add residual connections? Residuals let the network enter the sharpening regime, as the energies paper proves. But they repel along all edges alike. Choi et al. show that repulsion along mis-signed edges destroys class separation. The depth sweep on contextual stochastic block models with controlled edge-sign noise tests this directly. It shows whether residual models degrade with noise rate while certified-rank training does not.

Why not just use a scalar confidence weight, or sample edges? This is a real threat. A scalar gate given the interval's width, or Monte Carlo sampling (essentially uncertainty-aware DropEdge), may capture most of the value. The difference is that both optimize average-case behavior, whereas the radius bounds the worst case in a single deterministic pass. If the scalar-gate and Monte Carlo ablations match the full model in accuracy, we will narrow the contribution to the diagnostic. The question then becomes whether certified rank predicts collapse better than effective rank does.

Why not just ignore the graph with an MLP? On some clean heterophily sets this is competitive, according to Platonov et al. But CMGNN reports a 17% gain over baselines on Snap-Patents when relational patterns are weighted well. Our ResNet baseline makes the comparison explicit on every dataset.

Proposed Experiments

We first run a controlled study on contextual stochastic block models. We sweep homophily and an injected edge-sign error rate and train each model at depths from 2 to 64. We record accuracy, plain effective rank, numerical rank, and certified rank. The decisive check is correlation strength between each measure and accuracy across all runs. Zhang et al.'s 0.91 average for effective rank is the bar. We expect certified rank to exceed it specifically in high-noise, heterophilic cells, and to tie it under homophily, where intervals are narrow.

We then repeat the measurement on Cora, Citeseer, and Pubmed. We train on the leak-free suite: roman-empire, amazon-ratings, minesweeper, tolokers, questions, chameleon-filtered, and squirrel-filtered. Following the gap Platonov's audit exposed, we report GPRGNN* there for the first time.

Two outcomes would falsify the proposal. The first is center-only matching the full model on both accuracy and depth robustness. The second is certified rank correlating with accuracy no better than effective rank. Either result would show that uncertainty does not need to be propagated and that calibrated point weights suffice.