Repulsion Without Explosion: Signed Soft-Logic Energies for Deep Graph Propagation

Deep graph neural networks, which update each node by repeatedly averaging its neighbors' features, suffer from over-smoothing: after enough rounds every node looks the same. Recent work reads this as a social phenomenon. Averaging is the classic model of people reaching consensus, and over-smoothing is that consensus. The most direct fix borrowed from sociology adds negative edges, meaning pairs of nodes that should push away from each other the way rivals do. That fix works, but it sits on a knife edge. A Signed Graph Approach to Understanding and Mitigating Oversmoothing proves there is a critical repulsion strength. Below it, features still collapse. Above it, features diverge to infinity.

This note argues that the knife edge comes from how repulsion is written, not from repulsion itself. Suppose "rivals should not end up in the same group" is written as a weighted logical rule over bounded truth values, using the soft logic of hinge-loss Markov random fields. Then the rule is a convex penalty. A deep network whose layers are steps of a solver for that penalty can repel without ever exploding. It converges to a unique fixed point at a rate we can state, and it handles three or more antagonistic groups, the case where classical signed opinion models fail. The proposal builds this propagation layer, proves its stability, and tests whether the signed logical penalty adds accuracy beyond the simpler stabilizers a reviewer would reach for first.

Core Claim

Current signed propagation writes repulsion as something like pushing apart $x_i - x_j$ for a negative pair. This is a concave term in the node features. Minimizing an energy that contains it rewards moving nodes infinitely far apart, which is exactly the explosion side of the critical value. Weighted first-order logic writes the same social idea differently. Each node $i$ holds a vector $y_i$ of soft memberships over $K$ groups (truth values in $[0,1]$ that sum to one). A negative edge grounds the rule $\text{Enemy}(i,j) \wedge \text{In}(i,c) \Rightarrow \neg \text{In}(j,c)$. Under Łukasiewicz logic, the continuous logic used by Hinge-Loss Markov Random Fields and Probabilistic Soft Logic, this rule becomes the hinge $\max(0,\, y_{ic} + y_{jc} - 1)$. That hinge is convex and bounded on the simplex.

We propose the energy

$$E(y) = \sum_i \lambda \lVert y_i - p_i \rVert^2 + \sum_{(i,j)\in \mathcal{E}^+} w^+_{ij} \lVert y_i - y_j \rVert^2 + \sum_{(i,j)\in \mathcal{E}^-} w^-_{ij} \sum_{c=1}^{K} \max(0,\, y_{ic}+y_{jc}-1)^2 .$$

Here $p_i$ is a neural network's prediction for node $i$. The first term is the "stubbornness" anchor of the Friedkin–Johnsen opinion model, with strength $\lambda$. $\mathcal{E}^+$ and $\mathcal{E}^-$ are the positive and negative edges, with weights $w^\pm_{ij}$. Each layer of the proposed network is one projected gradient (or ADMM) step on $E$, with every $y_i$ kept on the simplex. Because $E$ is $2\lambda$-strongly convex and smooth, the iteration contracts toward the unique minimizer by a factor of $1 - \mu/L$ per layer, where $\mu$ and $L$ are the strong-convexity and smoothness constants. This is the standard rate for projected gradient descent on such functions. Depth then stops being a hazard. Layer 300 is simply a better-converged layer 30, and there is no repulsion threshold to tune.

We state one limitation up front. The uniform assignment $y_{ic} = 1/K$ satisfies every negative hinge whenever $K \ge 2$. The negative rules therefore do not prevent collapse by themselves; the anchor does. The testable claim is narrower and more useful. Under a fixed stabilizer (the anchor), bounded convex repulsion adds discriminative power near class boundaries and on heterophilic graphs, and it does so without the instability that unbounded repulsion introduces.

Relation to Prior Work

The motivating line of work treats over-smoothing as opinion consensus. Understanding Oversmoothing in GNNs as Consensus in Opinion Dynamics proves this equivalence. It then keeps features diverse by tuning a nonlinear tanh dynamics near a bifurcation point. Graph Neural Diffusion via Generalized Opinion Dynamics instead anchors nodes to their inputs and adds a regularizer that guarantees convergence. Neither method uses negative ties. Our anchor term is essentially GODNF's stubbornness. What we add is signed repulsion that keeps GODNF's convergence guarantee, which BIMP gives up by working near a tipping point.

The constraining work is the structural-balance approach of Oversmoothing as Loss of Sign and its companion A Signed Graph Approach to Understanding and Mitigating Oversmoothing. They show that normalization and residual connections secretly inject negative edges. They build Structural Balanced Propagation (SBP), which reports roughly 80% accuracy on Cora at 300 layers. SBP also proves the critical-value result that our construction is designed to remove. We keep their sign sources (labels, or feature similarity) so that the comparison isolates the form of the energy.

On the social-dynamics side, Polarization and Fluctuations in Signed Social Networks shows that sign-as-negation dynamics make opinions vanish when there are three or more hostile factions. Its bounded "affine boomerang" model avoids vanishing, but the price is that opinions fluctuate forever. Our simplex formulation reads "enemy" as "not in my group" rather than "opposite of me," so it extends naturally to $K$ factions. Because it descends a convex energy, it yields a unique equilibrium instead of fluctuations. Whether that equilibrium is informative is an empirical question the synthetic experiments below answer.

The method comes from the soft-logic line: hinge-loss potentials and ADMM inference from Hinge-Loss Markov Random Fields and Probabilistic Soft Logic, and end-to-end gradients through the solver from NeuPSL. Probabilistic Soft Logic for Trust Analysis in Social Networks already encodes trust theories such as triadic closure as weighted rules. None of these works studies deep propagation, over-smoothing, or negative-edge repulsion as a stability mechanism. That combination is the new part.

Research Program

The first component is analysis. We prove existence and uniqueness of the minimizer, the per-layer contraction rate, and boundedness of every intermediate representation. We also derive when the fixed point differs from the unsigned anchored fixed point, which is essentially personalized-PageRank smoothing of $p$. The expectation is that the two differ exactly where anchored smoothing places $y_{ic} + y_{jc} > 1$ across a negative edge. That condition is a concrete, checkable signature of what the negative rules contribute.

The second component is the layer itself. It is a differentiable unrolled solver placed after a shallow encoder and trained end to end through the solver, as in NeuPSL. Rule weights $w^\pm$ are either learned per rule template or fixed. Two optional rule templates, structural balance ($\text{Enemy} \wedge \text{Enemy} \Rightarrow \text{Friend}$) and triadic closure, are added as soft rules that refine uncertain signs. They are evaluated separately so that they cannot hide the core effect.

The third component is a stress test on synthetic contextual stochastic block models with $K = 2$ to $8$ factions and controlled homophily. On these graphs we measure accuracy against the number of factions, alongside SBP.

Baselines

The naive reference is a plain graph convolutional network trained at each depth. The file reports it at 41.35% on Cornell (Understanding Oversmoothing in GNNs as Consensus in Opinion Dynamics) and 60.00% on Texas (Graph Neural Diffusion via Generalized Opinion Dynamics).

The strongest existing competitor is SBP, because it already uses negative edges to fight over-smoothing and reaches roughly 80% on Cora at 300 layers while other baselines fall below 30% (A Signed Graph Approach to Understanding and Mitigating Oversmoothing). We run Label-SBP and Feature-SBP with exactly the same positive and negative edge sets we feed our energy, on the same splits, and under the same hyperparameter search budget. Beating SBP means matching its accuracy at shallow depth and exceeding it at depths of 64 and above, or under label scarcity. It also means showing that SBP's accuracy is sensitive to its repulsion scale while ours is flat across $w^-$ values spanning two orders of magnitude.

We also run three other opinion-dynamics methods with their published configurations re-tuned under our budget. GODNF is reported at 93.93% on Texas and represents the anchor-only approach. BIMP is reported at 77.13% on Cornell and represents the near-bifurcation approach. PairNorm is reported at 74.5% on Cora with fully missing features on unlabeled nodes, against 42.3% for plain SGC (PairNorm). For APPNP and GCNII, following Residual connections provably mitigate oversmoothing, no reported result was found on Lacuna for these benchmarks, so we run them ourselves.

The ablations isolate the key ingredient. The first drops all negative potentials, which leaves anchored smoothing. The second replaces the hinge with quadratic repulsion inside the same solver, which recreates the SBP critical-value regime. The third runs SBP with its features clamped through tanh, which bounds features without making the energy convex.

Why not just…?

Why not just clamp or squash SBP's features to stop the explosion? This is the most serious threat, since BIMP already uses tanh. Bounding the features alone leaves a concave energy. Such an energy can have many equilibria and drive features to the corners of the bounded region, with no convergence rate. The clamped-SBP ablation settles the question. If it matches our accuracy and stability across depth and across repulsion scales, then convexity is not what matters, and we would report that.

Why not just anchor to the inputs, as APPNP and GODNF do? Anchoring already prevents collapse, and our energy relies on it for exactly that. The question is whether the negative rules add anything. The no-negative-potentials ablation measures this directly. We expect the gap to appear on Texas, Cornell, Wisconsin, Squirrel and Amazon-ratings, and on the many-faction synthetic graphs, not on Cora. If the gap is near zero everywhere, the signed component should be abandoned.

Why not just use NeuPSL as it stands? NeuPSL already runs a soft-logic solver on top of a neural network over Cora and Citeseer. Our layer is NeuPSL's machinery with a specific signed rule set, unrolled to arbitrary depth. We therefore include NeuPSL with its usual positive-only citation rules as a baseline. The claim under test is that the negative rules, together with the depth analysis, are the new part, not the solver.

Why not just feed pseudo-labels from a shallow network into Label-SBP? This baseline would rescue Label-SBP when labels are sparse. We run it with the same sign edges we give our method, so any remaining difference comes from the energy form rather than from the sign source.

Proposed Experiments

Datasets and protocol. We evaluate node classification on Cora, Citeseer and PubMed (homophilic), on Texas, Cornell, Wisconsin, Squirrel and Amazon-ratings (heterophilic), and on ogbn-arxiv for scale. We use depths 2, 8, 32, 64, 128 and 300, and repeat the Cora and Citeseer runs in the missing-feature setting where PairNorm reports its numbers. Beyond accuracy, we log Dirichlet energy (a measure of how different neighboring representations are), the maximum feature norm, and the per-layer distance to the solver's fixed point.

Decisive check 1: sensitivity to repulsion strength. We sweep the negative weight $w^-$ over two orders of magnitude for our method, SBP, and clamped SBP. Our theory predicts flat accuracy and bounded norms for our method, and a collapse-or-explode curve for SBP.

Decisive check 2: number of factions. On the synthetic block models, sign-as-negation methods should degrade as $K$ grows, while the simplex rule should not.

Decisive check 3: where the negative rules act. Our accuracy gain over the no-negative ablation should concentrate on nodes whose negative edges violate the hinge under anchored smoothing, the signature derived in the analysis. If the gain is spread uniformly across nodes, the mechanism proposed here is not what is producing it.