Coherent Edge Cuts for Deep Graph Attention

Graph neural networks compute each node's representation by repeatedly averaging information from its neighbors. Stack many such layers and every node in a connected region ends up with nearly the same vector. This failure is called over-smoothing, and it is the main reason deep graph networks underperform shallow ones. Graph attention, which learns a separate weight for each neighbor, was long expected to fix this by learning to ignore bad neighbors. Demystifying Oversmoothing in Attention-Based Graph Neural Networks proved it cannot. Softmax weights are always strictly positive, so attention never disconnects the graph, and node features still collapse exponentially fast toward a single shared vector within each connected component. The obvious response is to let attention layers delete edges outright, using a differentiable sampler of discrete on/off edge decisions.

We argue that deleting edges is necessary but not sufficient, and that what matters is which edges are cut consistently across layers. Collapse is driven by the product of many layers' mixing matrices. Suppose each layer cuts a different random-looking subset of edges, as DropEdge or independently sampled gates do. Information still leaks along the union of the surviving edges, and features still collapse, only more slowly. Suppose instead the cuts are coherent, meaning the same edges are removed at every layer. Then features converge to one vector per surviving component. That limit is harmless, and even desirable, if each component contains a single class. We propose to build attention layers with learned hard edge gates, to tie those gates across depth with a coherence penalty, and to show both theoretically and empirically that coherence, not sparsity alone, decides whether deep attention collapses.

Core Claim

The claim has three parts.

First, take any deep attention network whose per-layer edge supports change from layer to layer. Its features collapse to rank one on every component of the union of supports taken over windows of layers. We plan to state and prove this extension of the Wu et al. analysis, which covers only the fixed-support case.

Second, a learned gate shared across layers, trained end to end, turns this union graph into a partition of the nodes. Deep features then converge to per-component means rather than a single global mean.

Third, if the gates are trained against the task loss, the components become label-consistent. Depth then stops hurting, and on graphs with misleading edges it can help.

The second and third parts are what separate this work from existing pruning and sparsification methods. The first part is what turns it into a falsifiable prediction. Independent per-layer cuts should still collapse. Coherent cuts should not.

Research Program

Gated attention layer. We keep standard attention scores $e_{ij}$, computed as in Graph Attention Networks, which scores each neighbor with a small network over the concatenated pair of node features. We multiply each score by a binary gate $z^{(\ell)}_{ij}\in\{0,1\}$ before normalizing:

$$\tilde\alpha^{(\ell)}_{ij}=\frac{z^{(\ell)}_{ij}\exp(e^{(\ell)}_{ij})}{\sum_{k\in\mathcal N_i\cup\{i\}} z^{(\ell)}_{ik}\exp(e^{(\ell)}_{ik})}.$$

Here $\ell$ indexes layers, $\mathcal N_i$ is the neighbor set of node $i$, and self-loops are never gated so every row stays well defined.

The gates are drawn from a hard-concrete relaxation, a Gumbel-noise trick that yields exact zeros and ones in the forward pass while passing smooth gradients backward. The gate logit is $\phi^{(\ell)}_{ij}=\phi_{ij}+\delta^{(\ell)}_{ij}$. The term $\phi_{ij}$ is shared across all layers and computed from the endpoint features of the input. The term $\delta^{(\ell)}_{ij}$ is a per-layer deviation.

Coherence penalty. This penalty is the new ingredient. It charges each edge the gap between its probability of being active in any layer and its probability of being active in every layer. The penalty is zero exactly when cuts are consistent across depth. A sweep over its weight interpolates between independent per-layer gating, which behaves like learned DropEdge, and a single static learned cut. At test time we threshold the gates deterministically.

Prior methods we reuse. The relaxation itself is not new. Discrete Graph Structure Learning for Forecasting Multiple Time Series learns one static Gumbel-sampled graph for forecasting. Graph Information Bottleneck samples neighbor subsets with categorical and Bernoulli relaxations in two-layer GAT backbones for adversarial robustness. NodeFormer puts a kernelized Gumbel-Softmax inside all-pair attention for scalability. Gumbel-MPNN rewires graphs with Gumbel-Softmax against oversquashing and heterophily, using degree and label-consistency regularizers. None of these four studies depth beyond standard sizes or measures collapse, and none asks how the sampled supports relate across layers. We take their estimator and change the question.

Closest competitor. DYNAMO-GAT does prune attention edges to reach 128 layers. It decides which edges to cut with a fixed anti-Hebbian rule, cutting edges between nodes whose noise-perturbed features are highly correlated, rather than learning gates from the loss. Its authors report that it fails on sparse graphs, where pruning disconnects nodes. Our method differs on both counts: its gates are trained by the task loss, and its coherence analysis predicts which cuts are safe.

Analysis. Alongside the method we will measure two things layer by layer. One is Dirichlet energy, the sum over edges of squared feature differences, as in Dirichlet Energy Constrained Learning for Deep Graph Neural Networks. The other is distance to the per-component rank-one subspace. Are we measuring oversmoothing in graph neural networks correctly? questions energy-only metrics, so we report both and take the rank-based one as primary. We also record the components of the learned union graph and their label purity. Purity is the quantity the theory says should predict deep accuracy.

Sparse graphs. The failure DYNAMO-GAT reports becomes, in our framing, a measurable cost: nodes that end up isolated degrade to a per-node feature-only classifier. We will report the fraction of isolated test nodes and whether gates learn to avoid isolating them. We deliberately do not add shortcut edges, to keep the mechanism clean. Combining cuts with additions in the style of Gumbel-MPNN is a follow-up only if isolation proves costly.

Baselines

Naive references. The do-nothing reference is a standard GAT at matched depths of 2, 8, 16, 32, 64 and 128 layers, using identical hidden size, optimizer and tuning budget. We also run a feature-only MLP. On heterophilic graphs, cutting nearly all edges reduces our model to an MLP, so the MLP is the floor any cutting method must beat to show that the kept edges matter. For context, Dirichlet Energy Constrained Learning for Deep Graph Neural Networks reports GCN accuracy on Cora falling "from 82.5% to 21.9%" beyond 16 layers.

DYNAMO-GAT. DYNAMO-GAT is the strongest direct competitor. It is the only cited method that prunes attention edges to train 128-layer models, and it reports 75.3% accuracy on ogbn-products against 73.9% for G2GAT, plus an accuracy-per-GFLOPS ratio of 137.53 against GAT's 35.11 on Cora. The file has no absolute Cora accuracy reported for it on Lacuna. We will rerun it with its released settings on our splits and give it the same hyperparameter search budget as our method. Beating it means higher accuracy at depth 64 and 128 on at least the heterophilic and sparse graphs, at comparable FLOPs.

GCNII. Simple and Deep Graph Convolutional Networks is the strongest depth-robust method that does not rely on topology. It mixes a fraction of the input features back in at every layer and pushes layer weights toward the identity, and it reaches its best performance at 64 layers. It also improves Wisconsin accuracy by over 12% relative to APPNP. We run it, along with EGNN, which Dirichlet Energy Constrained Learning for Deep Graph Neural Networks reports 3.1% above GCNII at 32 layers on ogbn-arxiv, under the same budget.

Learned DropEdge. DropEdge randomly deletes edges each epoch and reports a 13.5% gain for a 64-layer GCN on Citeseer. We apply it to GAT with its drop rate tuned. Our own independent-gate variant, with the coherence weight set to zero, is effectively a learned DropEdge.

Ablations isolating coherence. The key ablations hold the gate network, gate density and everything else fixed and vary only coherence. The comparisons are coherence weight zero, intermediate values, and a fully shared gate. A separate two-stage ablation thresholds the attention of a trained shallow GAT, then trains a deep GAT on the fixed pruned graph. This tests whether end-to-end learning of the cut matters at all.

Why not just…?

Why not just use sparse attention such as sparsemax, which already outputs exact zeros? Sparsemax replaces softmax with a projection onto the probability simplex, so many weights come out exactly zero. This is the most serious threat, because it defeats Lemma 2 of Demystifying Oversmoothing in Attention-Based Graph Neural Networks with no sampling. Our prediction is that per-layer sparse supports still collapse on their union graph. We will test this directly by running sparsemax-GAT and entmax-GAT at depth and measuring union-graph components. If sparsemax plus our coherence penalty applied to its supports matches our sampler, we will report that the contribution is the coherence principle rather than the sampler, which is still a meaningful result.

Why not just use DropEdge? DropEdge provably slows convergence to the smoothed subspace, but its cuts are independent across epochs and layers. Under our analysis the union graph stays connected, so it delays collapse without preventing it. Learn Beneficial Noise as Graph Augmentation also argues that random edge dropping disrupts important structure. The coherence-zero ablation and tuned DropEdge-GAT at 128 layers settle the question: if either avoids collapse as well as coherent gating, our central claim is wrong.

Why not just add initial residuals and ignore topology? Mixing the input back in at every layer, as GCNII does, keeps features from vanishing at any graph. On homophilic citation graphs it may well match our method, and we expect it to. The question is whether learned cuts add value on top of it. We therefore also run our gates inside GCNII. A gain on heterophilic graphs (Wisconsin, Cornell, Texas, Chameleon, Roman-Empire) or under adversarially perturbed structure on Pubmed, where Graph Information Bottleneck shows learned edge sampling helps, would show that topology still matters. No gain would mean residuals are enough, and we would say so.

Proposed Experiments

We use homophilic citation graphs (Cora, Citeseer, Pubmed) and heterophilic graphs (Wisconsin, Cornell, Texas, Chameleon, Actor, Roman-Empire). For scale we add ogbn-arxiv and ogbn-products, with standard Open Graph Benchmark splits from Open Graph Benchmark. Depth runs from 2 to 128 layers with ten seeds per configuration.

The first decisive check is the collapse curve: distance to the per-component rank-one subspace versus depth, plotted for GAT, sparsemax-GAT, DropEdge-GAT, independent gates and coherent gates. The theory predicts that only coherent gating plateaus away from zero.

The second check tests the mechanism. Across all runs, union-graph component purity measured at depth 64 should predict test accuracy better than gate density does.

The third check is the practical one. Coherent gating should match or beat DYNAMO-GAT and GCNII at depth 64 and 128 on heterophilic and sparse graphs, report its isolated-node fraction, and on Pubmed with structural perturbations beat a GIB-style two-layer gated GAT once depth is added.

If coherent and independent gating give indistinguishable collapse curves, the proposal fails cleanly and informatively.