Antagonism Keeps Deep Graph Features Apart but Squeezes Them Flat

Deep graph neural networks average each node's features with its neighbors' features, layer after layer, and after enough layers every node looks the same. This failure is called over-smoothing. A recent and influential fix borrows from the sociology of hostile relationships. It adds "negative edges" between nodes that should differ, so that those nodes push each other apart instead of averaging together. That repulsion keeps deep networks trainable to hundreds of layers. Sociologists who study opinion dynamics on networks with both friendly and hostile ties have a sobering result, though. When many factions push against each other with a single scalar strength, opinions do not settle into many distinct positions. They line up along one axis, with two poles winning, and any remaining factions are crushed toward the middle or left fluctuating there.

We propose that signed message passing inherits this result. Repulsion keeps features far apart, so the usual distance-based smoothness measures look healthy. Yet with three or more classes, repulsion drives the features into a one-dimensional, polarized subspace as depth grows, at a rate set by a single spectral gap that can be computed in advance. If this holds, the 300-layer success of signed propagation is partly an illusion on many-class problems. It also suggests a cheap remedy: equalize the repulsion across the class-contrast directions so that $k$ factions settle at $k-1$ independent positions rather than on one line.

Core Claim

The closest existing work is Structural Balanced Propagation, or SBP, from A Signed Graph Approach to Understanding and Mitigating Oversmoothing. SBP shows that residual connections and normalizations such as PairNorm and ContraNorm act like implicit negative edges. It then places explicit negative edges between differently labeled nodes (Label-SBP) or between nodes with dissimilar features (Feature-SBP). The paper also proves a critical repulsion strength: below it, features smooth out; above it, they blow up. SBP reaches roughly 80% accuracy on Cora at 300 layers, while plain graph convolutional networks fall below 30%. SBP measures health with accuracy and energy-style quantities. It never checks the dimension of the representation, and it assumes the balanced "enemy of my enemy is my friend" structure behaves benignly for any number of classes.

The opinion-dynamics literature says that assumption is fragile. Opinion dynamics and wisdom under out-group discrimination generalizes classic opinion averaging so that agents move against out-group opinions. It proves that stable polarization requires the network to split into exactly two opposed camps, which yields a two-pole and therefore rank-one configuration. Polarization and Fluctuations in Signed Social Networks shows two things for three or more mutually hostile factions. Classical linear signed dynamics drive opinions to zero (the "vanishing opinion" problem). Their bounded repulsive "boomerang" model instead puts two factions at the extremes and leaves the rest fluctuating in between (their Lemma 3.3). Both results describe a scalar opinion space. Our claim is that SBP-style propagation is, mathematically, the same linear signed dynamics run on feature vectors.

Its long-depth behavior is therefore governed by the top eigenvectors of the signed propagation operator $M = I - \eta L^{+} + \eta\beta L^{-}$. Here $L^{+}$ and $L^{-}$ are the Laplacians of the positive and negative edge sets, $\eta$ is a step size, and $\beta$ is the repulsion weight. With $k$ classes connected by negative edges, the directions that separate classes span a subspace of dimension $k-1$. These directions have equal growth rates only when classes are exactly equal in size and negative edges are uniform. Otherwise the leading two eigenvalues $\lambda_1 > \lambda_2$ split, and after $L$ layers the normalized features satisfy

$$ \frac{\sigma_2(H^{(L)})}{\sigma_1(H^{(L)})} \approx \left(\frac{\lambda_2}{\lambda_1}\right)^{L} \cdot \frac{\sigma_2(H^{(0)}_{\perp})}{\sigma_1(H^{(0)}_{\perp})}, $$

where $\sigma_i$ is the $i$-th singular value of the feature matrix and $H^{(0)}_{\perp}$ is the input projected onto the class-contrast subspace. The form is the standard power-iteration rate: each layer multiplies the component along each eigenvector by its eigenvalue.

The consequence is a precise, falsifiable prediction. Effective rank should decay geometrically toward one at a rate we can compute before training from the class sizes and the negative-edge graph. Pairwise feature distances, and with them Dirichlet energy, stay large. Imbalanced, many-class benchmarks such as ogbn-arxiv, with 40 classes, should be hurt most.

Why This Is the Right Measurement Lens

Are we measuring oversmoothing in graph neural networks correctly? shows that Dirichlet energy can stay flat while trained networks lose accuracy by layer 10. That energy is a sum of squared feature differences across edges. The paper proposes scale-invariant rank measures instead: numerical rank $\|X\|_F^2/\|X\|_2^2$, and effective rank, an entropy of the normalized singular values. Effective rank correlates with accuracy at an average Pearson coefficient of 0.91. We reuse these diagnostics unchanged, so they supply our method of measurement.

That same paper constrains us. High rank is necessary but not sufficient, since white noise has full rank. So we never claim rank alone; every rank result is paired with accuracy. We restrict our remedy to the class-contrast subspace rather than inflating all directions.

Research Program

The first part is analysis. We will compute the spectrum of $M$ restricted to the class-contrast subspace for Label-SBP and Feature-SBP on each benchmark, using a few Lanczos iterations on the sparse operator. We will then derive the predicted per-layer rank-decay rate $\lambda_2/\lambda_1$ and the predicted depth at which effective rank falls below two.

We extend the linear analysis to two settings. The first adds an initial-residual "stubbornness" term, as in the Friedkin–Johnsen opinion model, where each agent stays partly anchored to an innate belief. The signed version, Friedkin-Johnsen Model for Opinion Dynamics on Signed Graphs, shows that the equilibrium is a resolvent rather than a power. This changes the decay from geometric to a fixed attenuation ratio $(1-\alpha\lambda_2)/(1-\alpha\lambda_1)$ type, which we will make exact. The second setting adds a ReLU between layers. This is where the theory of Implicit Graph Neural Diffusion Based on Constrained Dirichlet Energy Minimization admits linear guarantees stop. For it we rely on measurement, and we check whether clipping produces the "neutral" collapse that Eger predicts for hard opposition.

The second part is the remedy, which we call isotropic repulsion. At each layer, the repulsive term acts on the top-$(k-1)$ eigenspace of $L^{-}$ with its eigenvalues replaced by a common value $\bar\lambda$, placed at SBP's critical strength. All class-contrast directions then grow at the same rate, and the $k$ factions settle at the vertices of a simplex instead of on a line.

The eigenspace is computed once for Label-SBP. For Feature-SBP it is recomputed every few epochs by warm-started Lanczos, at a cost of $O(|E^{-}|k)$ per refresh, which stays linear in the number of negative edges.

A cheaper intermediate step simply reweights negative edges by inverse class-pair size. That removes the imbalance-driven split exactly for Label-SBP but not for noisy Feature-SBP edges. We test it as its own rung, because it may be all that is needed.

The social-science reading is direct. Scalar antagonism one-dimensionalizes a multi-faction society into a single left–right axis. Giving each hostile pair its own direction of disagreement is what lets many factions coexist without vanishing or oscillating.

Baselines

The naive reference point is a plain graph convolutional network and an unmodified SBP run at depths 2, 4, 8, 16, 32, 64, 128 and 300, reporting accuracy and effective rank per depth. The accuracy figure to beat comes from SBP itself: about 80% on Cora at 300 layers, versus under 30% for deep graph convolutional baselines, as reported in A Signed Graph Approach to Understanding and Mitigating Oversmoothing. For ogbn-arxiv, no reported SBP accuracy was found on Lacuna, only that its second version avoided quadratic memory. We will therefore establish that number ourselves under the authors' settings.

SBP is the strongest competitor because it is the only method that already uses negative edges against over-smoothing at extreme depth. It also beat ten normalization baselines by about 3 points on homophilic graphs and 5 points on heterophilic graphs. We run Label-SBP and Feature-SBP with the published splits, the same hidden width as our method, and an identical hyperparameter search budget (same number of trials over learning rate, weight decay and repulsion strength). We use the same seeds throughout.

For heterophilic graphs we add DIGNN as a strong implicit-depth competitor. DIGNN computes the network's output as the fixed point of a constrained diffusion, which gives an effectively infinite receptive field without stacking layers. It reports improving Chameleon accuracy from 68.42% to 79.89% in Implicit Graph Neural Diffusion Based on Constrained Dirichlet Energy Minimization. We run it with its released configuration plus the same tuning budget.

The ablations isolate the key ingredient, equal growth across contrast directions. One is SBP with inverse class-size edge reweighting. Another is isotropic repulsion applied to a random $(k-1)$-dimensional subspace instead of the class-contrast one, which controls for "any rank boost helps." A third is SBP plus a stubbornness initial residual.

Beating the baselines means two things. Our method must match SBP within noise on the few-class benchmarks where SBP is strong. It must also exceed SBP's accuracy at depth 64 and above on ogbn-arxiv and on imbalanced many-class synthetic graphs, by a margin larger than three seed standard deviations, while holding effective rank near $k-1$.

Why not just…?

Why not just use ContraNorm or PairNorm, which already fight collapse? SBP proves these normalizations are implicit negative edges, so they should inherit the same spectral split. ContraNorm-style whitening spreads mass over all directions, including ones unrelated to class structure. That is exactly the high-rank-but-useless regime Zhang and colleagues warn about. We include both in the depth sweep. If ContraNorm holds rank and accuracy as well as isotropic repulsion on ogbn-arxiv, our remedy adds nothing and the contribution reduces to the diagnosis.

Why not just add an initial residual, as in APPNP or SGDNET's restart step? This is the most serious threat. Mixing in a fraction of the input features at every step, as Signed Graph Diffusion Network does with its restart probability, keeps the input's rank alive. It could make the rank decay irrelevant in practice. Our analysis predicts it bounds the decay rather than removing it, leaving the minor contrast directions attenuated by a fixed factor. The SBP-plus-residual ablation settles the question. If it closes the gap on imbalanced many-class graphs, we will report that the residual suffices and recommend it.

Why not just reweight negative edges by class size? For Label-SBP this may fix the problem completely, and we would count that as a positive, practical outcome. It cannot equalize the spectrum when negative edges come from noisy feature similarity, as in Feature-SBP, or from partial labels. The Feature-SBP comparison shows whether the eigenspace step earns its cost.

Why not just stay shallow and inject multi-hop proximity, as in hpGAT? Shallow models sidestep depth but do not answer whether signed deep propagation is sound. They also cannot express parity reasoning over multiple hops, such as "enemy of my enemy," which Signed Graph Convolutional Network found needs at least two sign-aware hops. We report a two-layer graph convolutional network as the shallow ceiling. If no deep method beats it on a dataset, we say so.

Proposed Experiments

The decisive check uses contextual stochastic block models, synthetic graphs whose node features and edges are both generated from planted classes. This benchmark family was already used by SBP. We vary the number of classes $k \in \{2,3,5,10\}$ and the class-size imbalance ratio from 1 to 10. Before training, we compute $\lambda_2/\lambda_1$ for each configuration. We then measure effective rank of SBP features against depth.

The hypothesis is confirmed if three things hold. The log effective rank minus one should decay linearly in depth with slope within 20% of $\log(\lambda_2/\lambda_1)$. Two-class graphs should show no accuracy loss. Accuracy should fall in step with rank as $k$ and imbalance grow. It is refuted if SBP's effective rank stays near $k-1$ at depth 128 under strong imbalance.

On real data we run the same depth sweep on Cora, CiteSeer and PubMed. These have few classes and moderate imbalance, so we predict small effects. We run it on ogbn-arxiv, where 40 imbalanced classes lead us to predict a large effect. We also run it on the heterophilic Squirrel, Chameleon and Amazon-ratings. In every case we report accuracy, numerical rank, effective rank and Dirichlet energy side by side, to show directly whether energy stays high while rank collapses.

The secondary social check uses the unlabeled signed networks BitcoinAlpha, BitcoinOTC, Slashdot and Epinions. There we measure the effective rank of SGDNET and SGCN embeddings against diffusion depth on link-sign prediction. The reference is Signed Laplacian Graph Neural Networks, which reports a link-sign AUC-P of 95.08% on BitcoinAlpha. These real hostile-tie graphs are known to violate balance, so they test whether the one-axis collapse appears outside class-label-induced signs.

The whole study succeeds as science even if the remedy is unnecessary. A confirmed, pre-computable rank-decay law tells practitioners when signed propagation is safe. A refutation tells them the sociological worry does not transfer.