To prove that a graph neural network (GNN) is robust, a verifier propagates bounds through the network. It tracks, for every neuron, an interval or a pair of linear functions that is guaranteed to contain the neuron's value for every allowed input perturbation. On graphs this repeats a lot of work. In a molecule, the two hydrogens on a methyl group start from identical feature boxes, see identical neighborhoods, and so receive identical bounds layer after layer. Yet the verifier computes and refines each one separately. Lifted inference from probabilistic reasoning has a standard fix for this kind of redundancy: group nodes that behave identically into "supernodes" and compute once per group. The obstacle is that a robustness query looks exactly like the "evidence" that breaks symmetry in lifted inference. Each node gets its own independent perturbation, so the two hydrogens no longer compute the same function. Exact lifting of the network's computation, as done by Lossless Compression of Structured Convolutional Models via Lifting, therefore does not apply.
The observation behind this proposal is that perturbations break symmetry between the functions the nodes compute but leave symmetry between the verifier's abstract states intact. Two nodes with equal input boxes and equitably equivalent neighborhoods get equal bounds even though their concrete values differ. We propose to lift the verifier's abstract states rather than the network. When features are continuous and almost no two boxes are equal, we merge nodes deliberately, giving each group the hull (the smallest enclosing box) of its members' boxes. How much merging the verifier can afford depends on the activation function. A widened interval costs nothing for a ReLU that stays on one side of zero. For sigmoid, tanh or GeLU the cost grows with the square of the interval width. The merge budget and the coarse-to-fine refinement are therefore driven by activation curvature. This is the point where symmetry breaking, graph compression and activation compatibility have to be handled together.
Core Claim
Bound propagation of the CROWN family (linear bounds propagated backward to the input) can be carried out exactly on a quotient graph. The quotient is built from an equitable partition of the nodes, meaning a grouping in which every node in a group has the same number of neighbors in each other group, as produced by Weisfeiler–Leman color refinement. The partition must be computed with the target node, the perturbation pattern and the input boxes all used as initial colors.
Two conditions make this sound for perturbed graphs. First, each supernode is interpreted as a set of independent copies that share one box, not as one shared variable. Second, every member of a group receives the same backward coefficient, which the equitable partition guarantees. Under these conditions, concretizing $|c|\,a_c x_c$ over the group's box gives exactly the sum of the members' individual minima. Because any relaxation that is valid on an interval is also valid on its subintervals, the construction works for any activation whose relaxation depends only on the pre-activation bounds. That includes sigmoid, tanh, GeLU, sine, GenBaB's lookup-table relaxations, and the convex softmax bounds used for attention.
When boxes differ, we replace each group's boxes with their hull. The verifier stays sound but becomes looser. For a twice-differentiable activation $\phi$ on an interval of width $w$, the gap between the chord and the function is at most $\kappa w^2/8$, where $\kappa=\max|\phi''|$ on that interval; this is the standard linear-interpolation error bound. We score the damage from merging group $c$ as
$$ \Delta_c \;=\; |\lambda_c|\,\frac{\kappa_c}{8}\Big(w_{\text{hull},c}^2-\tfrac{1}{|c|}\textstyle\sum_{m\in c} w_m^2\Big), $$
where $\lambda_c$ is the group's backward coefficient toward the specification, $w_{\text{hull},c}$ is the width of the merged interval, and $w_m$ is member $m$'s own width. A refinement loop starts from an over-merged partition and repeatedly splits the groups with the largest $\Delta_c$ until the property is proven or the time budget runs out.
What would be new is threefold: lifting abstract states rather than computations; the independent-copies argument for why this is sound under per-node perturbations; and a curvature-aware rule for how much symmetry to give up.
Relation to Prior Work
Two papers supply the mechanism. Lossless Compression of Structured Convolutional Models via Lifting merges functionally identical sub-computations of GNNs for faster training. It reports up to 10x speedups, but only about 2x on expressive GIN models, and its authors note that guarantees for non-polynomial activations are hard. We borrow its lifting machinery but compress bounds, not values, which removes the need for functional equivalence. Lifted Generalized Dual Decomposition starts from an over-symmetric graph and splits groups whose dual gradients vary a lot, while keeping valid upper bounds throughout. Our $\Delta_c$ applies the same idea to neural bound propagation, with the CROWN coefficients $\lambda_c$ in place of the dual gradients.
Three papers motivate the proposal and also define its closest competitors. Scalable Verification of GNN-based Job Schedulers (vegas) abstracts nodes that share weights within job groups and cuts runtime by 51.2% on 10-job Decima benchmarks. Its abstraction is static, comes from domain structure, and relies on piecewise-linear LP encodings. Ours is computed per query from the perturbation pattern and supports smooth activations. Neuron Similarity-Based Neural Network Verification via Abstraction and Refinement (ARVerifier) merges similar neurons within a layer of a ReLU MLP and un-merges them when a counterexample turns out to be spurious. We merge across graph structure under an equitable-partition constraint, which is what makes the quotient sound without counterexamples. Robustness Verification of Graph Neural Networks Via Lightweight Satisfiability Testing (RobLight) verifies ReLU-style GNNs under edge perturbations exactly, up to 4 layers with hidden size 32. It targets a different perturbation model and uses no symmetry.
On the activation side, Formal Verification for Neural Networks with General Nonlinearities via Branch-and-Bound (GenBaB) and Convex Bounds on the Softmax Function with Applications to Robustness Verification provide the relaxations we plug in. The second also constrains us: tighter softmax bounds raised runtime from about 10s to about 90s per MNIST instance. That cost is exactly what lifting has to pay for on graph attention models.
Two results bound the scope. Liftability of Probabilistic Inference: Upper and Lower Bounds shows that unary evidence keeps inference liftable while binary evidence makes it #P-hard. This predicts that node-feature perturbations (unary) will preserve compression and edge perturbations (binary) will shatter it. We test that prediction rather than assume a fix. Fundamental Limits in Formal Verification of Message-Passing Neural Networks proves that verification over unbounded graphs is undecidable, so we work only on fixed, finite graphs. Optimizing over trained GNNs via symmetry breaking adds symmetry-breaking constraints to a mixed-integer program to avoid relabeled duplicates. It removes symmetry from a search over input graphs, whereas we exploit symmetry in a fixed graph.
Research Program
The first component is a lifted version of CROWN and α-CROWN (CROWN with optimized relaxation slopes) inside the auto-LiRPA / α,β-CROWN stack. Color refinement is initialized with the target node, the perturbation radius per node and the quantized feature box. Optimizable relaxation parameters are shared within each group. We will prove, and check numerically, that with an exact partition the lifted bounds equal the ground bounds up to floating-point error.
The second component is the over-symmetric initialization. We merge nodes by structural color alone and take hulls over feature boxes. The structural partition must remain exactly equitable, because approximate structural merges would break the equal-coefficient argument. Refinement then proceeds by the $\Delta_c$ score, with $\kappa_c$ read off the activation and the current interval. For ReLU we use a separate term that is zero when the hull stays on one side of zero and equals the triangle-relaxation area otherwise.
The third component is the interaction with branch-and-bound, the search that splits a neuron's range and verifies each piece separately. Branching on a hull-merged group is not complete, because members can fall on different sides of the split point. Branching is therefore allowed only after a group has been refined down to members with identical boxes, and only on neurons that are truly shared. Otherwise the loop must choose between un-merging a group and running GenBaB on the ground neurons. We compare $\Delta_c$ against GenBaB's own branching heuristic (bound propagation with shortcuts) as the arbiter of that choice.
The fourth component is the shattering study. We measure the compression ratio (number of groups divided by number of nodes) as the perturbation budget moves from features of a few nodes, to features of all nodes, to edge flips.
Baselines
The naive reference point is ground-level α-CROWN on the target's k-hop receptive field with standard relaxations and no branch-and-bound. It is the cheapest sound verifier, and it shows how much tightness and speed is available at all.
The strongest existing method is ground-level α,β-CROWN with GenBaB, applied to the same receptive field. It is the competition-winning general-nonlinearity verifier and already batches redundant neurons on the GPU. It will run on the same trained models, perturbation sets, GPU and per-instance timeouts (60s and 300s), with GenBaB's default lookup tables and the same α-optimization iteration count as ours. No reported result was found on Lacuna for GenBaB, or any verifier, on smooth-activation GNNs for MUTAG, ENZYMES or Cora. The closest reported figures are 60% verified (versus 4% without branch-and-bound) on a CIFAR-10 4×100 sine network, and 22 of 23 ML4ACOPF instances, both from Formal Verification for Neural Networks with General Nonlinearities via Branch-and-Bound. We will establish the GNN numbers ourselves. Beating this baseline means certifying strictly more instances at equal wall-clock time on at least the molecular benchmarks, or the same number in at most half the time.
On Decima we also compare against vegas-style static node abstraction, whose reported runtime reduction is 51.2% on 10-job benchmarks. To make that comparison fair we use the authors' ReLU setting, and we additionally run a sigmoid-retrained variant where its LP encoding no longer applies directly.
For edge perturbations on Cora and MUTAG, the reference is RobLight, reported to be more than an order of magnitude faster than GNNev and SCIP-MPNN. No per-dataset numbers are reported in the file. We expect to lose to RobLight in that regime, as the shattering prediction says.
Three ablations isolate the key ingredients. The first uses an exact partition only, with no hull merging, which measures how much real box-symmetry exists. The second uses hull merging with fixed feature bins and no refinement, which plays the role of quantization. The third keeps refinement but scores groups by hull width alone, without curvature or coefficient weighting. If the third matches the full $\Delta_c$ rule, the activation-aware part of the claim fails.
Why not just…?
Why not just run GenBaB on the ground graph and let GPU batching absorb the redundancy? This is the real threat. Bound propagation is massively parallel, so duplicated neurons cost little per pass. Lifting helps only where cost grows faster than linearly: the backward pass over intermediate bounds scales roughly with the square of the neuron count, the number of α parameters shrinks, and branch-and-bound otherwise branches separately on each copy of an equivalent unstable neuron. Even so, on Cora, where sparse binary features make most boxes unique, we may get little or no gain. The matched-time comparison will settle this per dataset, and we will report a loss if that is what happens.
Why not just quantize features and then apply exact lifting? Quantizing the inputs of the verified network changes the network, so a certificate for the quantized model says nothing about the original. Quantization done soundly is exactly our fixed-bin hull ablation. The question is whether curvature-guided refinement beats a fixed grid, and that ablation answers it directly.
Why not just use vegas's node abstraction or ARVerifier's neuron merging? vegas abstracts according to the scheduler's job structure, not the query, and is ReLU/LP-bound. ARVerifier merges by similarity within single layers and repairs mistakes with counterexamples. Neither guarantees that merged nodes receive equal backward coefficients, which is what keeps our quotient sound without counterexample checks. We run both under identical budgets, ReLU-restricted where they require it.
Proposed Experiments
We will train GCN, GIN and GAT models with ReLU, sigmoid, tanh and GeLU activations, plus softmax attention for GAT. Datasets are MUTAG and ENZYMES for graph classification, Cora and CiteSeer for node classification, and Decima on TPC-H traces. Perturbations are L∞ balls on node features, applied either to all nodes or to a random 10% of them. Metrics are certified accuracy at fixed timeouts, wall-clock time, compression ratio, and the bound gap relative to ground α-CROWN.
The decisive checks are four. First, exact-partition lifted bounds must match ground bounds numerically, and no lifted certificate may be broken by a PGD attack. Second, on MUTAG, where one-hot atom features give real box-symmetry, lifting must beat ground GenBaB at matched time. If it does not even there, the idea fails. Third, the advantage of curvature-weighted refinement over width-only refinement should be close to zero for ReLU and grow for sigmoid and tanh. That pattern would confirm that activation choice governs how much symmetry the verifier can afford. Fourth, the compression ratio should stay roughly flat as feature-perturbation coverage grows and collapse toward one group per node under edge flips. This would reproduce the unary-versus-binary evidence dichotomy for neural verification. The collapse would also mark low-rank edge-evidence approximation, in the spirit of On the Complexity and Approximation of Binary Evidence in Lifted Inference, as the natural follow-up rather than something this work claims.
References
- Lossless Compression of Structured Convolutional Models via Lifting
- Lifted Generalized Dual Decomposition
- Scalable Verification of GNN-based Job Schedulers
- Neuron Similarity-Based Neural Network Verification via Abstraction and Refinement
- Robustness Verification of Graph Neural Networks Via Lightweight Satisfiability Testing
- Formal Verification for Neural Networks with General Nonlinearities via Branch-and-Bound
- Convex Bounds on the Softmax Function with Applications to Robustness Verification
- Liftability of Probabilistic Inference: Upper and Lower Bounds
- Fundamental Limits in Formal Verification of Message-Passing Neural Networks
- Optimizing over trained GNNs via symmetry breaking
- On the Complexity and Approximation of Binary Evidence in Lifted Inference