Graph neural networks build a node's representation by repeatedly averaging it with its neighbors' representations. Stack enough of these averaging layers and every node ends up looking the same, a failure called over-smoothing. A common hope was that attention would fix this. Attention here means learning a separate weight for each neighbor instead of using a fixed weight set by node degree. That hope has been disproved. Demystifying Oversmoothing in Attention-Based Graph Neural Networks shows that attention weights produced by a softmax are always strictly positive. Every edge therefore keeps leaking information, and representations still collapse exponentially to a single vector; attention only slows the collapse. The existing remedies are partial. One cuts edges and can disconnect sparse graphs. Another adds back the node's own input features at every layer, which keeps nodes distinct but in practice limits how far information travels.
We propose to let neighbor weights be negative, and to decide their sign from the nodes' raw input attributes (their text, features, or descriptors) rather than from the drifting hidden states. If two connected nodes' raw attributes disagree, the edge pushes their representations apart; if they agree, it pulls them together. A signed averaging operator no longer has "everyone equal" as a stable state, so the collapse argument of Wu et al. no longer applies. Because no edge is ever removed, sparse graphs stay connected. The sharpest prediction concerns how many distinct sign patterns, or attention heads, a deep model needs. Each head can preserve at most one two-way split of the nodes at infinite depth, so separating $C$ classes should require roughly $\lceil \log_2 C \rceil$ heads. That count is a cheap scalar analogue of the stalk-dimension condition in sheaf diffusion, and it can be tested directly.
Core Claim
We make two claims. First, anchoring per-edge signed weights on raw attributes gives deep message passing a non-collapsing limit that standard softmax attention cannot reach, without pruning and without block-matrix machinery. Second, the information that survives at depth is bounded and predictable. A known result from the signed-consensus literature says that a single signed operator whose sign pattern splits the nodes into two mutually opposed camps converges to a "bipolar" state, where the two camps hold opposite vectors, instead of to one shared vector. This bipolar state keeps exactly one bit per node. With $K$ heads, each head with its own attribute-derived sign pattern, a deep model keeps up to $K$ bits. Its accuracy at large depth should therefore saturate once $2^K \ge C$, where $C$ is the number of classes.
The mechanism is simple to write down. Let $x_i$ be node $i$'s raw attribute vector and $h_i^{(\ell)}$ its hidden state at layer $\ell$. For head $k$, the edge weight is
$$w^{k}_{ij} = s_k(x_i, x_j)\,\exp\big(a_k(h_i^{(\ell)}, h_j^{(\ell)})\big), \qquad h_i^{(\ell+1)} = \sigma\Big(\textstyle\sum_k W_k \sum_{j \in \mathcal{N}_i} \frac{w^k_{ij}}{\sum_{m}|w^k_{im}|}\, h_j^{(\ell)}\Big).$$
Here $s_k \in [-1,1]$ is a small learned function of the raw attributes only, shared across all layers. It sets the sign and the confidence of each edge. The term $a_k$ is an ordinary attention score on hidden states, and it can only rescale an edge's weight, never flip its sign. Dividing by the sum of absolute weights keeps each row's influence bounded, so the operator cannot blow up.
Because the sign pattern is fixed by $x$ and does not change with depth, the layer-by-layer product of operators has a stable sign structure. We can then extend the inhomogeneous-product analysis of Wu et al. instead of starting from scratch.
How This Differs From Closest Work
Several papers motivate the proposal by documenting the gap. Wu et al. prove that positive attention collapses, but they offer no architecture; they explicitly name non-softmax weighting as open, and that is what we build. DYNAMO-GAT prunes attention edges between nodes whose hidden states become too correlated, and it reaches 128 layers. Its authors report severe degradation on very sparse graphs, where pruning disconnects nodes. We keep every edge and turn disagreeing edges into repulsive ones. We also decide disagreement from raw attributes, not from noise-perturbed hidden states that can drift away from the input.
Three lines of work supply ideas we reuse or contrast against. DRGCN learns how much of each node's input to re-inject at each layer, but its neighbor aggregation stays isotropic or standard softmax attention. In our model, by contrast, the raw attributes shape the neighbor weights themselves. Neural Sheaf Diffusion learns linear maps on edges that can sharpen features. It proves that separating $C$ classes needs per-node vector spaces of dimension at least $C/2$, at the cost of a $|V|d \times |V|d$ block operator. Our head-count prediction is a scalar, logarithmic counterpart that we expect to be weaker but far cheaper. Multi-Track Message Passing prevents mixing across classes by running one copy of the graph per category, with memory linear in the number of tracks and a dependence on early pseudo-labels. Our heads play a similar role with $\log_2 C$ rather than $C$ copies and no pseudo-labels.
On the attribute side, CARL and ARNM-DAE2A keep attribute and structure channels apart so that dense topology cannot wash out attributes. Both, however, use shallow models or random walks. We take their lesson that attributes need a protected route into the model, and we apply it to the edge weights of deep networks. ALaGCN gates a node's whole neighborhood on or off. We act per edge and allow signs.
One constraint shapes the evaluation. Are we measuring oversmoothing in graph neural networks correctly? warns that Dirichlet energy and mean distance between representations can mistake harmless compression for collapse. We therefore report accuracy and the effective rank of the representations, not energy alone. A second constraint comes from Revisiting Over-smoothing in Graph Neural Networks: forcing representations apart with PairNorm hurt performance. That is a warning that artificial separation can backfire. Our repulsion is local, restricted to edges with attribute disagreement, rather than global, and the ablations test whether that difference matters.
Research Program
The theory step extends Wu et al.'s framework to row-normalized signed operators with a fixed sign pattern. The goal is to characterize the limit of the product of these operators. We expect a bipolar limit when a head's attribute-induced sign graph splits into two opposed camps, and decay to zero when it does not. From this we will state the head-count condition.
We will also analyze degree effects. Simple and Deep Graph Convolutional Networks shows that high-degree nodes collapse faster. Under absolute-value normalization, high-degree nodes average over more signed terms, so their updates may cancel out. We will test whether this happens.
Practically, $s_k$ is a two-layer network on the difference and product of $x_i$ and $x_j$. It is trained end to end, with a sparsity penalty that pushes most edges to be clearly positive. For text-attributed graphs, $x$ is a frozen text-encoder embedding. This keeps the cost linear in the number of edges, with $K$ small.
Baselines
The naive reference points are a two-layer GCN and an MLP that uses attributes only. Both run with the same features, splits, and tuning budget. The MLP matters because if attributes alone match deep models, depth is not buying anything.
The strongest initial-residual competitor is DRGAT from DRGCN, which reports 76.33% accuracy on ogbn-arxiv and 87.5% on Cora at 64 layers. Its sibling GCNII is the static version of the same idea. These are the main threat, because re-injecting inputs already prevents collapse. We rerun both with official hyperparameter grids and give every model the same number of trials. Beating them means matching their homophilic accuracy while clearly exceeding them where information must travel far.
For heterophily we compare against Multi-Track Message Passing, which reports 92.10% on Texas, 90.20% on Wisconsin, and 86.4% on Cora. We also compare against Neural Sheaf Diffusion; the file gives its relative standing but no exact numbers. On Chameleon the reference is GSAN at 61.2%. On large graphs it is DYNAMO-GAT at 75.3% on ogbn-products. For these we will judge success by being within noise on accuracy while using much less memory than the multi-track model or sheaf diffusion.
Three ablations isolate the key ingredient. In the first, signs come from hidden states instead of raw attributes. In the second, weights are attribute-anchored but forced positive, which is just attention with an attribute prior. In the third, we vary $K$ to test the head-count prediction.
Why not just…?
Why not just use an initial residual like GCNII or DRGAT? This is the real threat. Re-injecting inputs provably keeps nodes distinct, and DRGCN's 87.5% at 64 layers on Cora is strong. But a residual keeps nodes distinct by anchoring them to their own input, which effectively shortens the distance information travels. That predicts residual models will be fine on Cora and fail on tasks that need far-away information. The Tree-NeighborsMatch depth sweep decides this. The file contains no reported GCNII or DRGCN result on Tree-NeighborsMatch, so we will run them ourselves. If GCNII matches us there, our contribution shrinks to a theoretical one, and we will say so.
Why not just prune dissimilar-attribute edges once before training? Static rewiring is cheap. It inherits DYNAMO-GAT's reported failure mode, however: on sparse graphs, removing edges isolates nodes. Repulsive edges keep a path open while still separating the nodes they connect. We test this directly by sparsifying Cora and CiteSeer to controlled average degrees and comparing pruning against signing.
Why not just learn signed weights from hidden states? This is the first ablation. Our hypothesis is that signs computed from hidden states change from layer to layer, which removes the fixed sign pattern the analysis relies on, and that the signs themselves blur as states smooth. If this variant matches the anchored version, the attribute-anchoring claim fails.
Why not just stay shallow? On small homophilic citation graphs, shallow models already win, as DSGNN found. We do not contest that. The claim concerns long-range and label-scarce regimes. Cora with 1% labels, where ALaGCN reports 73.3% against GCN's 59.2%, and Tree-NeighborsMatch, where GCN and GAT fail beyond depth 5, are where depth should matter.
Proposed Experiments
The datasets are Cora, CiteSeer, and PubMed, plus Cora at a 1% label rate; Texas, Wisconsin, Cornell, and Chameleon for heterophily; ogbn-arxiv and ogbn-products for scale; and Tree-NeighborsMatch for long-range information. We sweep depth over 2, 8, 32, 64, and 128 layers and report accuracy and effective rank of the representations, with at least five seeds.
The first decisive check is the head-count law. On datasets with $C$ classes, accuracy at 128 layers should plateau once $K \ge \lceil \log_2 C \rceil$; for ogbn-arxiv, with 40 classes, that is 6 heads. If accuracy keeps rising well past that point, or plateaus well before it, the theory does not describe the model.
The second check is the sparse-graph comparison against pruning. The third is the Tree-NeighborsMatch comparison against residual baselines.
Together these three results determine whether attribute-anchored signs are a real addition or an elaborate restatement of the initial residual.
References
- Demystifying Oversmoothing in Attention-Based Graph Neural Networks
- A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
- DRGCN: Dynamic Evolving Initial Residual for Deep Graph Convolutional Networks
- Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs
- Multi-Track Message Passing: Tackling Oversmoothing and Oversquashing in Graph Learning via Preventing Heterophily Mixing
- CARL: Content-Aware Representation Learning for Heterogeneous Networks.
- An attribute-enhanced relationship-aware neighborhood matching model with dual attention
- When Do GNNs Work: Understanding and Improving Neighborhood Aggregation
- Are we measuring oversmoothing in graph neural networks correctly?
- Revisiting Over-smoothing in Graph Neural Networks
- Simple and Deep Graph Convolutional Networks
- Geometric Scattering Attention Networks