Routing Collapse: Why Disentangled Graph Networks Still Over-Smooth When Made Deep

Graph neural networks compute each node's representation by repeatedly averaging it with its neighbors. Stacked many times, this averaging makes all nodes look alike, a failure called over-smoothing. A separate line of work builds "disentangled" graph networks. These split each node's representation into several channels, one per hidden reason two nodes might be connected (coworkers versus classmates, say), and decide edge by edge which channel each neighbor's message goes to. Disentangled models have been reported to resist over-smoothing, but only at about five layers. Nobody has checked what happens at the 32 to 64 layers where the over-smoothing literature actually operates.

We propose that deep disentangled networks fail through a specific feedback loop we call routing collapse. The step that assigns neighbors to channels compares neighbor features by similarity. As depth smooths those features, every neighbor starts to look equally similar in every channel. Assignments then drift toward uniform, all channels end up seeing the same graph, and the model reverts to an ordinary graph network that smooths even faster. If this is right, the fix is not a heavier independence penalty or a global normalization. It is to stop the assignment step from reading smoothed features. We call this anchoring the routing to early-layer features, and we test it against the obvious cheaper and stronger alternatives.

Core Claim

In Disentangled Graph Convolutional Networks (DisenGCN), each layer projects features into $K$ channel subspaces. It then assigns each neighbor $u$ of node $v$ to channels by an iterative soft clustering based on cosine similarity, which the paper shows is an expectation-maximization step for a mixture of von Mises-Fisher distributions. Write $r^{(\ell)}_{vuk}$ for the probability that the edge $(v,u)$ is routed to channel $k$ at layer $\ell$. We track one quantity, the normalized routing entropy:

$$ S^{(\ell)} = \frac{1}{|E|\log K}\sum_{(v,u)\in E}\Big(-\sum_{k=1}^{K} r^{(\ell)}_{vuk}\log r^{(\ell)}_{vuk}\Big), $$

Here $|E|$ is the number of edges. $S^{(\ell)}=1$ means every edge is split evenly across channels, so disentanglement has vanished. $S^{(\ell)}$ near 0 means each edge commits to one factor.

The claim has three parts. First, in deep DisenGCN-style models $S^{(\ell)}$ rises toward 1 with depth. Second, that rise comes before the accuracy drop, and it predicts the drop better than the per-channel effective rank does. Effective rank is a continuous measure of how many independent directions the representations occupy, and it is the collapse diagnostic validated by Are we measuring oversmoothing in graph neural networks correctly?. Third, computing assignments from early-layer features keeps $S^{(\ell)}$ low and keeps accuracy flat out to 64 layers. It does so at a fraction of the cost of the kernel independence penalty used by Independence Promoted Graph Disentangled Networks (IPGDN).

Each part can fail separately. If entropy stays low while accuracy collapses, the loop is wrong, and over-smoothing in these models is ordinary within-channel smoothing.

Relation to Prior Work

Two papers motivate the gap. DisenGCN observed that its routing keeps aggregation sparse within each channel and lets it stack about five layers. IPGDN found that routing alone yields redundant, correlated channels. It added a Hilbert-Schmidt Independence Criterion penalty between channels, a kernel measure of statistical dependence, and argued that this preserves nuance with depth. Neither paper measures the assignments themselves across depth, and neither uses rank metrics. Both stay at shallow-to-moderate depth.

Our hypothesis offers a mechanism for IPGDN's redundancy finding. Correlated channels may be a symptom of uniform routing rather than a cause that needs penalizing.

Factorizable Graph Convolutional Networks (FactorGCN) factorizes the graph once into factor subgraphs and keeps them apart with a discriminator. Because its factorization is not recomputed from smoothed features at each layer, it is a natural control. It should be immune to routing collapse but still exposed to ordinary smoothing within each subgraph.

The over-smoothing literature constrains and supplies methods. Simple and Deep Graph Convolutional Networks (GCNII) adds a residual connection back to the input features and an identity term on the weights, which reaches 64 layers. It also shows that high-degree nodes converge faster. PairNorm re-centers embeddings and rescales them to preserve total pairwise distance. ContraNorm recasts over-smoothing as representations squeezing into a low-dimensional cone, and pushes them apart with one step of a contrastive uniformity loss. All three treat the graph as a single structure. Their repulsion is isotropic, meaning it pushes all nodes apart equally, which can work against the within-factor clustering that routing depends on.

The frequency-splitting models are the closest multi-channel cousins but split along a different axis. Complete the Missing Half (FB-GNN) adds high-pass "diversification" channels to low-pass averaging. Geometric Scattering Attention Networks (GSAN) mixes band-pass wavelets per node. These models split frequencies, not relation types, and they never decide which edges belong together.

Research Program

The first component is diagnostic. We instrument DisenGCN, IPGDN and FactorGCN at depths 2, 4, 8, 16, 32 and 64. At every layer we record:

  • routing entropy $S^{(\ell)}$, for the two models that route;
  • the effective rank and numerical rank of each channel's representations;
  • the cross-channel effective rank of the concatenated channel means;
  • Dirichlet energy, the standard smoothness measure, kept as the metric the rank paper showed to be misleading.

From these we estimate which quantity's trajectory best predicts the accuracy trajectory. Following the rank paper's protocol, we use Pearson correlation across depths and seeds, plus a lead-lag test of whether the entropy rise precedes the accuracy drop.

We also test a structural prediction that follows from GCNII's degree result. If routing collapse is the driver, high-degree nodes should lose distinct assignments first. That is because their many neighbors' features approach the neighborhood mean fastest.

The second component is the intervention. In anchored routing, the similarity used for assignment at layer $\ell$ is computed from the mixed feature $(1-\gamma)z^{(\ell)}_{u,k}+\gamma z^{(0)}_{u,k}$, where $z^{(\ell)}_{u,k}$ is neighbor $u$'s projection into channel $k$ at layer $\ell$ and $\gamma\in[0,1]$ is a single mixing weight. The messages being aggregated are unchanged. With $\gamma=1$, routing reads only the input-layer projections and costs one similarity computation per layer, with no kernel matrices.

This differs from GCNII's residual in a way that matters for the test. GCNII changes what gets averaged. Anchoring changes only which channel a message goes to. Crossing the two separates "routing collapse" from "feature collapse."

Baselines

The naive reference point is a plain graph convolutional network with no anti-smoothing component at each depth. This anchors the collapse curve. ContraNorm reports roughly 19% Cora accuracy for a vanilla 32-layer graph convolutional network. Below the deep-model baselines, we include plain DisenGCN, IPGDN and FactorGCN as published, extended in depth. At shallow depth on Cora, IPGDN reports 84.1% versus 83.7% for DisenGCN and 81.4% for a graph convolutional network. We found no reported result on Lacuna for any disentangled graph network beyond about five layers, so their deep behavior is exactly what we measure.

The strongest single-structure competitors are GCNII, which reaches 64 layers on Cora, and ContraNorm. ContraNorm reports about 46% on Cora at 32 layers with a graph convolutional backbone, against about 19% without it. The file gives no exact GCNII accuracy number for Cora at 64 layers, so we reproduce it under our protocol.

The decisive competitor is DisenGCN with a GCNII-style initial residual added. This is the one-line fix a reviewer will propose. It also feeds less-smoothed features to the routing step indirectly, so it could plausibly undo routing collapse.

The key ablation is a two-by-two design. One factor is anchored routing on or off. The other is an initial residual on or off. We also sweep $\gamma$, and we run IPGDN's independence penalty with and without anchoring.

All methods use:

  • identical data splits;
  • the same hidden width per channel and the same $K$;
  • the same number of random search trials for learning rate, dropout, weight decay and method-specific coefficients, selected on validation accuracy;
  • ten seeds.

We report wall-clock time and peak memory alongside accuracy.

Anchored routing counts as a success under two conditions. At 32 and 64 layers it must beat the residual-augmented DisenGCN and IPGDN beyond seed variance on the multi-factor benchmarks. It must also match or beat GCNII and ContraNorm on the citation graphs, while costing measurably less than IPGDN.

Why not just…?

Why not just add GCNII's initial residual to DisenGCN? This is the real threat. Because it keeps input information in every layer, it may keep routing sharp as a side effect. The two-by-two ablation settles it. If residual-only DisenGCN keeps $S^{(\ell)}$ low and matches anchored routing, then routing collapse is real but is cured by existing machinery. We would report the diagnosis as the contribution and drop the method claim. If the residual keeps per-channel rank high but entropy still climbs, anchoring is doing distinct work.

Why not just apply PairNorm or ContraNorm inside each channel? These keep each channel's spread or rank high. But high rank does not imply useful structure, as the rank paper notes, since random noise has maximal rank. Uniform repulsion also scatters the within-factor clusters that similarity-based routing needs to make confident assignments. Per-channel ContraNorm is a baseline arm. We predict it raises per-channel effective rank without lowering routing entropy, and that this gap shows up as worse accuracy on the synthetic factor graphs, where ground-truth factors are known.

Why not just keep channels apart with IPGDN's independence penalty? IPGDN shows the penalty reduces redundancy at moderate depth. However, it penalizes correlation between channel outputs, not uniformity of assignments. Channels can be statistically independent while every edge is still split evenly. The kernel computation also scales poorly. We run IPGDN at all depths, with entropy instrumentation and cost measurements. If it controls entropy as well as anchoring at comparable cost, the case for anchoring rests only on simplicity, and we will say so.

Why not just use a fixed factorization like FactorGCN, or a frequency filterbank? A factorization computed once cannot suffer routing collapse. This is why it is our control rather than our answer. FB-GNN and GSAN split frequencies over one graph and never infer relation types. We include FactorGCN with a GCNII residual and FB-GNN as baselines. On the multi-label benchmarks, where DisenGCN reports 10% to 20% relative Micro-F1 and Macro-F1 gains over a graph convolutional network, they test whether adaptive per-layer routing is worth keeping at depth.

Proposed Experiments

We run four groups of experiments.

The first is synthetic graphs with 4 to 10 planted factors, following DisenGCN's construction, on which DisenGCN reports a 12% to 17% Micro-F1 gain over a graph convolutional network. Here we can measure assignment accuracy against ground truth at every layer. This directly tests whether rising entropy corresponds to lost factor recovery.

The second is the multi-label graphs BlogCatalog, PPI and POS, where relation types plausibly matter most. The third is Cora, Citeseer and Pubmed, for comparison with the deep-network literature. These include the setting in which all features are missing, where PairNorm reports 74.5% versus 42.3% for vanilla SGC on Cora; that setting stresses whether routing on input features still works when those features are absent. The fourth is the heterophilic graphs Chameleon and Squirrel, plus OGB-Arxiv for scale. On these, the rank paper reports an average effective-rank–accuracy correlation of 0.91, which gives a reference for how predictive a diagnostic should be.

Three checks decide the outcome. The first: routing entropy must correlate with depth-wise accuracy at least as strongly as per-channel effective rank, and must rise earlier. If not, the routing-collapse hypothesis is rejected. The second: in the two-by-two ablation, anchoring must reduce entropy and improve 32- and 64-layer accuracy beyond what the initial residual alone achieves. The third: on the synthetic graphs, anchored routing must preserve ground-truth factor recovery at 64 layers, where plain DisenGCN is predicted to lose it.

A negative outcome on the first check is still informative. It would establish, with the right metrics, that disentangled networks over-smooth the ordinary way, and that their shallow-depth resistance was a depth artifact.