Attention That Can Cut Edges: Deep Self-Supervised Learning on Heterogeneous Graphs

Graph neural networks (models that update each node by averaging messages from its neighbors) lose information as they get deeper. After enough rounds of averaging, all node vectors drift toward the same few directions, a failure called over-smoothing. Learned attention does not fix this. Attention lets each node weight its neighbors differently, but a recent proof shows that because softmax attention always gives every edge a strictly positive weight, the graph stays connected and representations still collapse at an exponential rate (Demystifying Oversmoothing in Attention-Based Graph Neural Networks). We propose attention that is allowed to set weights to exactly zero, applied separately within each relation type of a heterogeneous graph (a graph with several kinds of nodes and edges, such as authors, papers and venues). The model is trained without labels, using an objective that forces it to keep the edges it actually needs. Two sentences carry the idea. If attention can cut edges, the connectivity argument behind collapse no longer applies, and the number of pieces the graph is cut into puts a floor under how many independent directions the representations can keep. If the cutting is learned from a self-supervised signal that can only be solved using neighbors, the model keeps useful structure instead of collapsing into a per-node classifier that ignores the graph.

This matters because heterogeneous graphs are exactly where supervision is scarce and depth is useful. Academic, e-commerce and fraud graphs are large, their labels are expensive, and on heterophilic benchmarks the relevant evidence often lies several hops away across node types, where connected nodes tend to have different labels. Existing label-free methods for these graphs are shallow and depend on hand-picked paths. Existing deep heterogeneous models are fully supervised. None of them has been checked with the rank-based collapse measures that actually track accuracy.

Core Claim

The claim is that relation-local sparse attention, trained by masked-neighborhood prediction plus a uniformity penalty, gives deep heterogeneous encoders three properties. First, their effective rank does not decay with depth. Second, frozen-embedding linear probes from these encoders come within a small margin of the best supervised heterogeneous models. Third, the advantage over simpler fixes should be concentrated on heterophilic heterogeneous graphs, where per-edge decisions matter more than per-relation ones.

The mechanism has a simple structure. Let $S^{(\ell)}_r$ be the set of edges of relation $r$ that receive nonzero attention at layer $\ell$. The collapse proof requires the product of attention matrices to act like repeated averaging over a connected graph. Once the union of supports $\cup_r S_r$ splits the graph into $k$ components, repeated averaging can shrink each component to a point but cannot merge components. The representation matrix therefore keeps rank at least $k$, up to what the per-relation transforms add. This yields a measurable prediction that we test directly. We make no claim that high rank is sufficient for accuracy, since white noise has full rank. That limitation is why the objective must also reward predictive use of neighbors.

Positioning Against Prior Work

The motivating evidence comes from three papers. Demystifying Oversmoothing proves collapse for softmax attention on homogeneous graphs and explicitly leaves sparse, thresholded attention unanalyzed; that open case is our starting point. ContraNorm shows that collapse is dimensional, meaning embeddings fall into a narrow cone, and that it can happen while attention maps still look diverse. ContraNorm counters it with a normalization layer derived from one gradient step on a uniformity loss. We use that uniformity loss as a training objective rather than as a layer. Are we measuring oversmoothing correctly? shows that Dirichlet energy, a measure of how much features differ across edges, fails to track accuracy in trained networks, while effective rank does (average Pearson $r = 0.91$). That result fixes our choice of diagnostic.

Two papers supply methods we reuse and extend. MRS-MPNN prevents rank collapse up to 128 layers by artificially splitting a homogeneous graph into degree-ordered relations with separate weights. Heterogeneous graphs come with real relations, so we get that splitting for free and add content-dependent zeros within each relation, which MRS-MPNN lacks. HGT supplies the attention parameterization, conditioning attention on the (source type, edge type, target type) triplet. We keep that parameterization but replace its softmax with a sparse normalizer such as sparsemax or entmax, which can output exact zeros, and we normalize within relations rather than across them.

The closest prior work falls into two groups, and each covers half of our target. On the label-free side, HGIB trains heterogeneous encoders without labels by maximizing agreement across meta-path views. A meta-path is a hand-chosen chain of relation types such as author–paper–author. HGIB beats semi-supervised HAN and GTN on ACM and DBLP, but it uses shallow per-path GCN encoders, never measures rank, and its consensus objective is the kind of pressure that can narrow representations. On the deep-supervised side, HALO, TAGDN and H2G-former all resist over-smoothing on heterogeneous graphs. HALO does this by unrolling an energy with static relation compatibilities, TAGDN with fixed diffusion plus Gaussian type alignment, and H2G-former with supervised cross-type attention and masked label embeddings. All three depend on labels. HALO and TAGDN judge over-smoothing through variance or energy measures that the rank study found unreliable.

FUEL both constrains and motivates the design. It shows that label-free tuning of how much to convolve works across homophily levels, and it does so partly by turning aggregation off on heterophilic graphs. That behavior warns us that an unconstrained sparse gate will learn to cut everything.

Research Program

The work proceeds in three stages. The first stage is purely diagnostic. We measure effective rank and numerical rank layer by layer for HAN, HGT, HALO and TAGDN at depths from 2 to 64 on HGB and on the H2GB suite, next to intra-type variance and Dirichlet energy. The goal is to find out whether these heterogeneous models suffer rank collapse that their own metrics hide. This stage is informative whatever the method results turn out to be.

The second stage builds the encoder. Each layer contains one attention head per relation, parameterized by the relation triplet as in HGT. Each head uses a sparse normalizer with a learnable temperature, so it can produce exact zeros. Its output passes through a relation-specific linear map, and the relation outputs are summed with a residual connection.

The training objective has two parts. The first is masked-neighborhood prediction: we hide a node's own input features and ask a type-specific decoder to reconstruct them from the encoder output. That output can only carry information about the hidden features through retained edges, so cutting every edge cannot solve the task. The second is a uniformity penalty,

$$\mathcal{L} = \sum_{v \in M} \| g_{\tau(v)}(z_v) - x_v \|^2 + \lambda \log \sum_{i,j \in B} \exp(-t\|z_i - z_j\|^2).$$

Here $M$ is the set of masked nodes, $z_v$ is node $v$'s final embedding, $g_{\tau(v)}$ is a decoder for $v$'s node type, $x_v$ is the hidden input feature vector, $B$ is a sampled mini-batch (which keeps the pairwise term tractable), $t$ is a temperature, and $\lambda$ weights the uniformity term. Node types without input features use learned embeddings and are excluded from $M$.

The third stage tests the rank-floor prediction. We count the connected components of the learned support at each depth and check whether effective rank stays at or above that count. We also check whether the learned cuts line up with label boundaries on heterophilic graphs, using labels only after training.

Baselines

The naive reference point is the same deep HGT-parameterized encoder with ordinary softmax attention, trained on the identical objective. It tells us what collapse looks like when nothing is done. We report it at every depth, with probe accuracy and effective rank side by side.

The strongest label-free competitor on homophilic heterogeneous graphs is HGIB (Heterogeneous Graph Information Bottleneck). It reports clustering NMI of 70.55 on ACM, against 41.09 for DGI, and Micro-F1 of 96.20% on DBLP with 60% training data, against 95.31% for GTN and 93.70% for HAN. We rerun HGIB with its meta-paths on our splits and use its published numbers as a sanity check. Beating it means matching or exceeding it on DBLP and ACM without any meta-paths.

The strongest supervised references define what parity means. On HGB IMDB, HALO (Descent Steps of a Relation-Aware Energy) reports 76.20% accuracy against 67.36% for Simple-HGN. On H2GB oag-cs, H2G-former (When Heterophily Meets Heterogeneity) reports 28.47% accuracy against 22.51% for HGT. For the other H2GB datasets there is no reported per-dataset result found on Lacuna, so we rerun H2G-former ourselves. We count parity as a linear probe on frozen embeddings landing within two accuracy points of the supervised model on the same split. On HGB IMDB, that means at least 74.2% against HALO.

TAGDN (TAGDN) represents static deep diffusion. We run it supervised, and also with our objective in place of labels, so that the comparison separates the propagation rule from the training signal.

Two ablations isolate the key ingredient. The first replaces sparse per-edge attention with one learned scalar gate per relation and layer, a FUEL-style dial applied to relations, while keeping the relation-specific maps. The second keeps sparse attention but normalizes it jointly across relations, as HGT does.

For fairness, every method receives the same splits, the same embedding width, a tuning budget of equal GPU-hours with the same random-search size, and the same linear-probe protocol for every label-free model.

Why not just…?

Why not just add ContraNorm layers to HGT and train with a standard contrastive loss? This is the most direct combination, and it may well work on the homophilic graphs ACM and DBLP. ContraNorm spreads embeddings apart, but it does not change which nodes exchange information. Under softmax attention the graph stays connected, so on heterophilic graphs, repulsion has to fight constant mixing across label boundaries. We run this exact variant at matched depth. If it matches our method on the H2GB datasets as well, the claim that edge-cutting matters is wrong, and we would report that.

Why not just stay shallow, as HGIB does? On ACM and DBLP, two layers may be enough, and depth may add nothing. The case for depth rests on heterophilic heterogeneous graphs, where TAGDN finds gains up to 40 diffusion steps and H2G-former needs multi-hop masks. Our depth sweep reports probe accuracy against depth for every method. If the best accuracy is always reached at depth two or three, the argument from depth fails. The rank diagnostics from the first stage would still be useful on their own.

Why not just use static diffusion like TAGDN with a self-supervised loss? Static diffusion avoids stacking collapse, but it spreads information uniformly across edges, which H2GB shows hurts under heterophily. TAGDN's type alignment also assumes unimodal Gaussian features. We include the self-supervised TAGDN variant described in the baselines, so this question is settled on the same data.

Why not just learn one gate per relation instead of per edge? This is the real threat. Real relation types already provide the splitting that protects MRS-MPNN's rank, and a per-relation dial is what FUEL does globally. We predict that per-relation gates close most of the gap on HGB but fall short on H2GB, because heterophily there varies within a relation, not only between relations. If the gated ablation matches the full model everywhere, we will present the simpler gated model as the result, and per-edge sparsity will have been shown unnecessary.

Decisive Checks

Three results would decide the proposal. First, at 32 and 64 layers, effective rank for the sparse model should stay flat and at or above the learned component count, while the softmax reference decays; if it decays anyway, the mechanism is wrong. Second, the gap to the per-relation gated ablation should be positive on H2GB and near zero on HGB; a uniform gap or no gap would each mean the heterophily explanation is wrong. Third, linear-probe accuracy should reach the parity thresholds defined in the baselines. As an honesty check, the fraction of retained edges should stay well above zero. A model that cuts nearly all edges and still scores well would be an MLP in disguise, and would show that the graph was not being used.