Running a graph neural network on encrypted data means paying for every multiplication with a scarce resource. Under homomorphic encryption (a scheme that lets a server compute on ciphertexts without decrypting them), each multiplication uses up one "level" of a fixed budget. When the budget runs out, the server must either run a very slow refresh step or start with much larger keys that slow down every operation. Current private graph inference systems cope by staying shallow, using two-layer graph convolutional networks, and by deleting activation layers outright. That approach has a hidden cost. A graph network with no activations between its neighbor-averaging steps is exactly the setting in which node representations blur into one indistinguishable vector, a failure called over-smoothing. Separately, the plaintext graph literature has found that the cure for over-smoothing is a particular kind of activation, odd and non-monotone, such as $\sin$ or $\tanh$. Under encryption, these are about the most expensive functions one can choose.
This note proposes that the property that actually stops over-smoothing is not "being $\tanh$." It is a local shape: positive slope at zero and a stabilizing negative cubic term. The simplest polynomial with that shape, $\phi(x) = x - \alpha x^3$, costs only two multiplicative levels to evaluate. If that is right, it changes how a private graph network should be designed. With a fixed encryption depth budget, the designer has to decide how many levels go to graph propagation (more hops of context) and how many go to nonlinearity (keeping nodes distinguishable). The cheapest odd cubic may make deep encrypted propagation useful rather than self-defeating. We would build this, test the theory behind it against the even quadratics that private inference currently prefers, and measure accuracy, smoothing and encrypted cost together on standard node-classification benchmarks.
Core Claim
Beyond ReLU: Bifurcation, Oversmoothing, and Topological Priors shows that monotone activations such as ReLU make message passing contractive, with a single stable collapsed state. Odd activations whose expansion begins $x - \alpha x^3$ instead produce a pitchfork bifurcation: the collapsed state loses stability and stable, non-uniform states appear. With $\sin$ or $\tanh$ and a matched initialization, Dirichlet energy stays healthy to 64 layers on Cora. Dirichlet energy is the summed squared difference between neighboring node embeddings, so it falls to zero exactly when nodes become indistinguishable. Those activations are transcendental. Under homomorphic encryption they need polynomial approximations of degree roughly 7 to 15, or garbled-circuit evaluation with heavy communication, as profiled by Characterizing and Optimizing End-to-End Systems for Private Inference.
Our claim is that the truncated cubic itself, with its scale folded into the preceding weight matrix so the scaling is free, keeps the bifurcation behavior. It does so at a fixed cost of two levels: one to square, one to multiply. A second claim concerns the activations private inference already uses. The pure square $x^2$, used in xMLP, has zero slope at zero. That makes the collapsed state super-attracting, so square activations should speed up over-smoothing rather than prevent it.
The trainable quadratics $ax^2+bx+c$ searched by PASNet are a genuinely open case. Their linear coefficient can destabilize zero, but they produce a one-sided, transcritical exchange of stability rather than a symmetric pitchfork. We do not assume this fails. We test it, because if it works it is the cheaper answer at one level per activation.
Research Program
The first component is analytical. We will extend the linearized stability analysis of the Beyond ReLU paper to polynomial maps $H \mapsto \phi(\tilde{A} H W)$, where $\tilde{A}$ is the normalized adjacency matrix, $H$ the node embeddings and $W$ a layer's weights. The aim is to characterize, for $\phi$ in three families ($x^2$, $ax^2+bx+c$, and $x-\alpha x^3$), three things: whether the uniform state is stable, where non-uniform fixed points lie, and how large their basins are.
The cubic has a real weakness here. Unlike $\tanh$, it is unbounded, and its iteration diverges once activations leave a window of order $1/\sqrt{\alpha}$. Encryption schemes such as CKKS also need values to stay within a known range. We will therefore derive the admissible input window. We will enforce it with the random-matrix initialization of the Beyond ReLU paper together with a range penalty during training, and we will report the worst-case activation magnitude observed on held-out graphs. This range question is the most likely way the idea fails, and we treat it as a first-class result.
The second component is the depth-budget model. Under the topology-encrypted setting of Penguin, each propagation hop is a ciphertext-ciphertext product and costs one level. Each weight multiplication costs one level unless it is fused with the hop. A cubic activation costs two levels and a quadratic costs one. Given a total budget $D$ that avoids bootstrapping at a chosen ring size, we will enumerate architectures that split $D$ between hops and activations. These include linear stacks in the style of CryptoGCN's activation pruning, interleaved cubic layers, and sparse placement of cubic layers every $m$ hops. We will measure accuracy and energy across these splits.
We also run the public-topology setting of CryptoGCN, where hops are plaintext-ciphertext products. In that setting propagation can be precomputed, which sets up the strongest competitor, discussed below.
The third component is the encrypted implementation. It reuses Penguin's two-dimensional packing and interleaved assembly for the propagation steps. Cubic activations act slot-wise, so they need no rotations, and the packing layout carries over unchanged. That property is a reason to prefer the cubic over the filterbank and rotated-basis methods: those add parallel channels that Penguin's layout does not handle. They are Complete the Missing Half, which adds a high-pass diversification channel, and UniFilter, which rotates polynomial bases by a homophily-dependent angle.
Baselines
The naive reference is the two-layer graph convolutional network as accelerated by Penguin, which protects both features and topology. The file reports a 10.62× speedup on Cora, 0.24 s amortized per-node latency and 128-bit security for Penguin. It contains no reported Penguin accuracy for Cora, Citeseer or Pubmed, so we will retrain and report it ourselves under the same splits. Beating this reference means higher accuracy at the same security level, particularly on the heterophilous graphs, with latency within a stated factor that we will report rather than hide.
The second baseline is CryptoGCN-style activation pruning applied to deeper stacks. CryptoGCN reports a 77.4% reduction in homomorphic operation count with 1% to 1.5% accuracy loss on NTU-RGB+D, using shallow models only. We run it at the same depth budgets as our models on the same graphs. We will also measure Dirichlet energy, which CryptoGCN never did. To beat it, interleaved cubics must keep higher energy and higher accuracy at equal total depth.
The plaintext upper bound is Beyond ReLU with $\sin$ or $\tanh$ and its initialization. Under encryption we implement it with the lowest-degree Chebyshev approximation that holds its plaintext accuracy, and we count levels honestly. The file reports stable accuracy to 64 layers on Cora and the best average rank across 12 datasets, but no numeric accuracies, so we reproduce it. We also include UniFilter in plaintext as the accuracy reference on Chameleon and Squirrel. The file reports gains of +1.03% and +6.38% over prior methods there, but no absolute numbers.
The key ablation holds depth, initialization and training fixed and changes only the activation: $x^2$, trained $ax^2+bx+c$, and $x-\alpha x^3$. A second ablation toggles the bifurcation-aware initialization on and off.
Why not just…?
Why not just keep the network at two layers? On homophilous citation graphs this may be enough, and we expect a two-layer model to be close to our method on Cora. That is a fair outcome to report. The case for depth rests on heterophilous and long-range settings. There, UniFilter's gains come from higher-order propagation, and Advection-Diffusion on Graphs points out that two-hop receptive fields cannot capture distant dependencies. The comparison on Chameleon, Squirrel, Texas and Wisconsin decides whether depth is worth its levels.
Why not just precompute a polynomial filter and run a square-activation MLP afterward? When the topology is public, the whole propagation $\sum_k \gamma_k \tilde{A}^k$ can be collapsed into one plaintext matrix. Here $\gamma_k$ are learned coefficients on each hop power, chosen as in UniFilter or a fixed diffusion, and the collapsed filter costs one level. A shallow MLP with $x^2$ activations would then follow it. This is a real threat, and we include it as a baseline. Its weakness is density: $\tilde{A}^k$ fills in as $k$ grows, which removes the sparsity that CryptoGCN's adjacency-aware packing and Penguin's layout rely on to avoid rotations. We will measure rotation counts and latency directly. In the encrypted-topology setting the matrix cannot be precomputed at all, and that is the regime our claim targets. If the precomputed filter matches our method on both accuracy and latency in the public-topology setting, we will say so and narrow the claim to encrypted topology.
Why not just approximate $\tanh$ with a higher-degree polynomial? This is the faithful port of Beyond ReLU and may be the most accurate option. Each activation then costs roughly three to four levels instead of two, so at a fixed budget it allows fewer hops or forces a larger ring. The depth-budget sweep compares the two at equal levels. That comparison is the clean test of whether truncating to the cubic gives up anything.
Why not just use trained quadratics, which cost one level? If the transcritical mechanism in $ax^2+bx+c$ keeps Dirichlet energy as well as the odd cubic does, the quadratic wins on cost and our cubic proposal is unnecessary. The activation ablation answers this directly. We consider it the most important single result. xMLP's report of "information compounding" with square activations suggests the quadratic will be fragile at depth, but that evidence comes from vision networks and is not decisive for graphs.
Proposed Experiments and Decisive Checks
We train on Cora, Citeseer and Pubmed, the heterophilous Chameleon, Squirrel, Actor, Texas and Wisconsin graphs, and the synthetic Erdős–Rényi, Barabási–Albert and Watts–Strogatz graphs used by Beyond ReLU to check the theory's predicted bifurcation thresholds. Depths range from 2 to 32 propagation hops.
The metrics are test accuracy, Dirichlet energy, and center-neighbor cosine similarity. We report several smoothing measures because Are we measuring oversmoothing in graph neural networks correctly? cautions against relying on one. We also report the maximum activation magnitude, along with multiplicative depth, ring size, rotation count, latency and memory under CKKS at 128-bit security. Every method gets the same hyperparameter search budget.
The first decisive check is whether the cubic keeps non-collapsing energy on the synthetic graphs at the threshold the theory predicts, and whether $x^2$ collapses faster than a linear stack. If the cubic collapses, or diverges outside its admissible window, the central claim fails. The second check is whether, at equal level budget on heterophilous graphs, deep stacks with interleaved cubic activations beat both the pruned linear stacks and the degree-matched $\tanh$ approximation. The third check is whether the encrypted-topology results hold on Pubmed. That is the setting where Penguin already notes its latency is high, and where our latency will show whether deeper encrypted propagation is practical or only a plaintext curiosity.
References
- Beyond ReLU: Bifurcation, Oversmoothing, and Topological Priors
- Characterizing and Optimizing End-to-End Systems for Private Inference
- xMLP: Revolutionizing Private Inference with Exclusive Square Activation
- PASNet: Polynomial Architecture Search Framework for Two-party Computation-based Secure Neural Network Deployment
- Penguin: Parallel-Packed Homomorphic Encryption for Fast Graph Convolutional Network Inference
- CryptoGCN: Fast and Scalable Homomorphically Encrypted Graph Convolutional Network Inference
- Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Networks
- How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over-smoothing, and Over-squashing
- Advection-Diffusion on Graphs: A Bakry-Emery Laplacian for Spectral Graph Neural Networks
- Are we measuring oversmoothing in graph neural networks correctly?