Where Deep Heterogeneous Graph Attention Collapses, and a Per-Type Anchor That Stops It

Graph neural networks compute each node's representation by repeatedly averaging information from its neighbors. After a handful of rounds, the representations drift toward one another until nodes can no longer be told apart, a failure called over-smoothing. For ordinary graphs, where every node and edge is the same kind of thing, we now have a fairly clear account of this failure. Attention does not cure it: learned, feature-dependent neighbor weights only slow the collapse. Adding back a fraction of the original input features at every layer, which we call an initial residual, can provably prevent it. None of this analysis covers heterogeneous graphs, whose nodes come in several types (authors, papers, venues) and whose edges come in several relations. These are the graphs where the most practical attention models, such as Simple-HGN and the Heterogeneous Graph Transformer, are actually used. The same models are almost always run at two to four layers, and nobody has checked why.

This note proposes to find out what "collapse" means when node types differ and to test one specific remedy. We think deep heterogeneous attention fails in two ways that current metrics mix together. The first is type washing: different node types lose their distinctness because they are averaged through mixed-type neighborhoods. The second is the familiar within-type class collapse. We propose a per-type initial residual combined with per-type, scale-only normalization, and we argue it blocks both failures even though attention matrices change from layer to layer. Scholkemper et al. identified exactly this case as the one where their guarantees and their normalization fall short. The work produces a theorem that covers time-varying attention, a diagnostic that separates the two failure modes, and a controlled test on the Heterogeneous Graph Benchmark of whether depth helps heterogeneous attention at all once collapse is removed.

Core Claim

Consider a heterogeneous attention network whose attention is computed separately per relation and normalized by a softmax. Its layer-to-layer maps are products of matrices whose rows sum to one and whose sparsity pattern follows the graph structure. The argument of Demystifying Oversmoothing in Attention-Based Graph Neural Networks should carry over largely intact. That paper models attention layers as a system that changes over time, and it proves that softmax attention keeps every edge strictly positive, so representations collapse exponentially.

The new element is that relation-specific projections change what the representations collapse to. In the linearized model, we expect the limit to be a low-dimensional subspace fixed by the schema, meaning one direction per type connected by the relation transforms. It is generally not the single shared vector seen in homogeneous graphs. Plain residuals of the kind Simple-HGN uses slow the approach to this subspace but do not remove it.

The claimed fix is the following layer update:

$$h_i^{(l+1)} = (1-\beta_{t(i)})\, S_{t(i)}\!\Big(\sum_{r}\sum_{j \in \mathcal{N}_r(i)} \alpha_{ij}^{(l)} W_r^{(l)} h_j^{(l)}\Big) + \beta_{t(i)}\, h_i^{(0)}.$$

Here $h_i^{(l)}$ is node $i$'s representation at layer $l$, and $t(i)$ is its type. $\mathcal{N}_r(i)$ is its set of neighbors under relation $r$, $\alpha_{ij}^{(l)}$ is the relation-conditioned attention weight, and $W_r^{(l)}$ is the relation's projection. $\beta_t \in (0,1)$ is a learnable anchor strength per type. $S_t$ divides by the standard deviation computed within type $t$ and does no mean-centering. $h_i^{(0)}$ is the node's input after its type-specific projection.

The theoretical claim is as follows. Take any sequence of row-stochastic attention matrices $A_l$, so that no symmetry or time-invariance is assumed. Suppose also that $(1-\beta)\lVert W_r^{(l)}\rVert < 1$. Then $H^{(L)}$ approaches a weighted sum $\sum_k \beta(1-\beta)^k \,(\text{products of } A \text{ and } W)\, H^{(0)}$. This sum is dominated by $H^{(0)}$ itself, so its rank and its separation between types are bounded below by those of the inputs. The geometric-series form comes from unrolling the affine recursion.

The key difference from prior work is that this guarantee does not depend on the attention matrices being symmetric or fixed across layers. Scholkemper et al. needed both, and they reported weaker results on attention models because those models violate the assumptions.

What Prior Work Establishes and Leaves Open

Two theory papers supply the method and one motivates the gap.

Residual Connections and Normalization Can Provably Prevent Oversmoothing in GNNs proves two results for linearized networks with fixed aggregation. First, initial residuals keep representations within the space generated by the input features. Second, scaling prevents collapse, while mean-centering can erase community structure. We reuse both results. We extend the first to attention that changes over time, and we argue the second matters more for heterogeneous graphs, because one mean computed across all types can blur the distinctions between types.

Residual connections provably mitigate oversmoothing in graph neural networks uses ergodic theory to show that plain residuals lower-bound how fast nodes become similar. It assumes random, independent weights and a fixed aggregation matrix, and it studies only citation graphs. We ask whether its "slowed but not stopped" regime describes Simple-HGN.

Wu et al.'s attention analysis motivates the work. It is homogeneous-only, and it explicitly leaves open how residuals interact with attention dynamics.

On the heterogeneous side, three papers constrain the design:

Both HALO and TAGDN resist over-smoothing, and both do it by giving up feature-dependent neighbor weighting. Our proposal keeps attention and asks what it takes to make attention deep.

The measurement critique in Are we measuring oversmoothing in graph neural networks correctly? shapes the diagnostic. Global similarity metrics do not distinguish harmless agreement within a class from harmful collapse across classes. Heterogeneous graphs add a third factor, collapse across types.

Research Program

The first strand is theory.

  • Collapse limit. We will characterize where linearized heterogeneous softmax attention collapses to. The target is a proof that the limit is a subspace fixed by the schema, obtained by adapting Wu et al.'s argument to block-structured, typed products of matrices.
  • Anchoring bound. We will prove the geometric-series lower bound above for per-type anchoring under arbitrary row-stochastic attention.
  • Nonlinearities. We will state what survives once ReLU-type activations are added, following the proximal-step argument HALO uses. Where proofs do not go through, we will report that openly and rely on measurement.

The second strand is a diagnostic applied layer by layer to trained and untrained models. It has three parts:

  • Type distinctness: how accurately a linear classifier can recover a node's type from its hidden representation.
  • Class separation within type: the ratio of between-class to within-class spread, computed on labeled target-type nodes.
  • Effective rank within each type.

Type washing appears as the first number dropping while the others still hold. Class collapse appears as the second number dropping.

The third strand is the model itself: Simple-HGN's attention layer, modified by the update above, trained at depths of 2, 4, 8, 16, 32 and 64 layers.

Baselines

The naive reference point is the best tuned shallow Simple-HGN from Are we really making much progress?, which reports a Macro-F1 of 94.01±0.24 on DBLP. If depth never improves on this, that is itself a finding: it would mean these benchmarks do not need long-range information.

The main competitor is deep Simple-HGN, meaning the same architecture with its plain residuals stacked to matching depth. It is the strongest attention-based heterogeneous model in the file that already contains residuals.

For fixed, non-attention models that resist over-smoothing, we include:

  • HALO. It reports 76.20% accuracy on IMDB against 67.36% for Simple-HGN. We will rerun both on HGB's standard splits, because the HALO paper's protocol may differ from HGB's.
  • TAGDN. No reported result for TAGDN on individual HGB datasets was found on Lacuna.

HAN (IMDB Micro-F1 around 58.5%, ACM clustering NMI 61.56%, from Heterogeneous Graph Attention Network) and HGT serve as reference attention models.

Three ablations isolate the key ingredient:

  • Type-agnostic anchor. One global $\beta$ and a single global scale-only normalization. This is the direct transfer of Scholkemper et al.'s recipe.
  • Per-type centering. Per-type normalization that does center, to test whether mean-centering hurts.
  • Uniform weights. The same anchored model with attention replaced by fixed uniform weights, to test whether dynamic weighting still contributes once depth is stabilized.

All methods get the same HGB splits, the same input features, and the same hyperparameter search budget per method and depth, run over the same number of seeds. Test labels are never used for tuning, which follows the leakage warnings in Lv et al.

To count as beating the baselines, the proposed model must meet two conditions:

  • Its best result at any depth must exceed tuned shallow Simple-HGN by more than the seed standard deviation on at least two node-classification datasets.
  • At 16 or more layers it must keep accuracy within one standard deviation of its own best, while deep Simple-HGN degrades.

Why not just…?

Why not just keep Simple-HGN's plain residuals, which already allow deeper stacking? Chen et al.'s analysis suggests plain residuals slow collapse without stopping it. Scholkemper et al. show that residuals without proper normalization can still drift toward a limit that has forgotten the input. The deep Simple-HGN baseline together with the layer-by-layer diagnostic tests this directly. If Simple-HGN holds up at 32 layers, our premise is wrong, and we will report that.

Why not just add an ordinary initial residual with global normalization, since type-specific input projections already exist? This is the most serious threat. It is possible that per-type anchoring and per-type scaling add nothing beyond the homogeneous recipe. The type-agnostic-anchor ablation settles the question. If the two match on both accuracy and type distinctness, the contribution shrinks to the theorem for time-varying attention and the diagnostic, and we will present it that way. Our specific reason to expect a gap is Scholkemper et al.'s own finding that mean-centering damages structural signal. In heterogeneous graphs a single global mean is dominated by whichever type has the most nodes, as in DBLP.

Why not just skip depth and use one-shot diffusion like TAGDN, or HALO's fixed relation compatibilities? Both models resist smoothing, but their propagation weights ignore node features. As a result they cannot suppress camouflage or noisy edges within a relation, which is the problem adaptive weighting addresses in Spectrum-Constrained and Skip-Enhanced Graph Fraud Detection. The uniform-weights ablation, combined with the edge-noise experiment below, will show whether attention earns its cost. If fixed models match ours under noise, deep attention is not worth pursuing on these benchmarks.

Decisive Experiments

The first test is the depth sweep on HGB node classification (DBLP, IMDB, ACM, Freebase). We report Macro-F1 and Micro-F1 for every method at every depth, alongside the three diagnostic curves. The central prediction is ordered: in deep Simple-HGN, type distinctness decays before class separation within type, and per-type anchoring flattens both curves. If class separation decays first, type washing is not the mechanism.

The second test is controlled edge noise. We inject random edges within a relation, between target nodes of different classes, at increasing rates. This checks whether the anchored attention model degrades more slowly than HALO, TAGDN and the uniform-weight ablation.

The third test is a homogeneous sanity check on Cora. The anchored model reduces to a single type there, and it should reach roughly the 85.9% that Scholkemper et al. report for their stabilized 20-layer model. This matters most for attention layers, where their method was weakest.

The fourth test checks the collapse-limit theorem empirically. For untrained linearized networks we measure the rank of deep representations within each type and compare it to the number of types.