TL;DR
Formal verification of deep neural networks ensures safety against adversarial attacks, but standard Branch and Bound (BaB) algorithms are bottlenecked by how they decide which neuron to split. This paper introduces a Graph Neural Network (GNN) that learns to imitate the high-quality decisions of "strong branching" by directly operating on the target neural network's architecture. The resulting strategy cuts both verification time and the number of branches by roughly 50% across convolutional networks.
What Problem Does This Paper Address?
Deep neural networks are brittle against adversarial perturbations. In safety-critical domains like autonomous driving or healthcare, traditional empirical testing is not enough—we need formal verification that a model will output the correct class for all inputs within a given perturbation radius ($\ell_\infty$ norm ball).
Most state-of-the-art verifiers frame this as a global optimization problem solved via Branch and Bound (BaB). BaB recursively splits the search space into sub-problems (branching) and computes relaxed lower bounds via linear programming (bounding). However, choosing which ambiguous ReLU neuron to split is critical:
- Strong branching evaluates the bound improvement across all candidate splits to pick the best one, yielding tiny search trees but incurring an intractable computational cost at every step.
- Hand-designed heuristics (like gradient scoring or BaBSR) are computationally cheap but suboptimal, often causing the search tree to explode on larger networks.
The challenge is obtaining strong-branching quality at heuristic speed.
Methods
The authors formulate branching as an imitation learning problem using a Graph Neural Network (GNN):
- Neural Network as a Graph: The target neural network is directly cast as the input graph for the GNN. Nodes combine pre- and post-activation ReLU variables, while edges correspond to network weights.
- Forward-Backward Embedding Update Schedule: Instead of simultaneous message passing across all nodes (as in generic MILP bipartite graphs), updates follow a layer-by-layer forward and backward schedule. The forward pass estimates local convex relaxation errors, while the backward pass captures how fixing a neuron impacts downstream layers.
- Hinge-Rank Loss: Candidates are grouped into $M$ bins based on their relative bound improvement, and the GNN is trained using a pairwise hinge-ranking loss to prioritize high-impact splits without over-fitting to minor differences among similar nodes.
- Fail-Safe Mechanism & Online Learning: If the predicted split yields an improvement below a set threshold (0.2), the system falls back to a fast heuristic (BaBSR). When the heuristic outperforms the GNN multiple times, the GNN takes a gradient step online to adapt to the specific property being verified.
Datasets
- CIFAR-10: Robustly trained convolutional models across three architectures:
- Base: 2 convolutional layers, 2 fully connected layers (3,172 ReLUs).
- Wide: Larger convolutional channel counts (6,244 ReLUs).
- Deep: 4 convolutional layers, 2 fully connected layers (6,756 ReLUs).
- Verification properties (467 easy, 773 medium, 426 hard) were selected via binary search over perturbation radius $\epsilon$.
- MNIST: Evaluated on Base, Wide, and Deep models (up to 5,196 ReLUs) to confirm generalization across architectures and datasets.
Key Insights and Ideas
- Architecture-Aware Graph Updates: Generic MILP representations treat all constraints symmetrically. In contrast, leveraging the feedforward structure of neural networks allows the GNN to pass information along the exact mathematical dependency paths of intermediate bound relaxations.
- Vertical Transferability: Generating strong-branching training data is expensive for large networks. Because the forward-backward update rules share parameters layer-by-layer, a GNN trained only on the small Base network generalizes effectively to both Wide and Deep architectures without retraining.
- Horizontal Transferability: Models trained primarily on easy-to-prove properties transfer seamlessly to medium and hard properties.
- Dataset Specificity: While the method transfers across network shapes, cross-dataset transfer fails (a CIFAR-trained model does not transfer to MNIST) because input data distributions and bound dynamics diverge significantly.
Key Results
- ~50% Reduction: On the CIFAR-10 Base network, GNN-Online reduced the average number of branches and overall runtime by over 50% compared to BaBSR (e.g., on Hard properties, solving time fell from 3,128s to 1,369s, and branches dropped from 2,494 to 814).
- Minimal Fallback Reliance: The GNN made over 90% of the branching decisions without triggering the fail-safe heuristic across all models (93.4% on Base, 95.0% on Wide, 96.4% on Deep).
- Negligible Inference Overhead: Evaluating the GNN took 0.02s to 0.08s per decision, which is virtually negligible compared to solving the underlying Linear Programs (1.1s to 9.6s per LP).
- Outperforming Commercial Solvers: On medium-to-large networks, the approach dramatically outperformed MIPplanet (backed by Gurobi), which timed out on most properties for the Wide and Deep models.
Limitations and Future Work
- LP Solving Remains the Bottleneck: While branching decisions became drastically faster and more effective, LP bounding time continues to dominate overall execution.
- Lack of Cross-Dataset Generalization: A model trained on one dataset cannot be deployed zero-shot on an unrelated dataset.
- Future Directions: The authors propose extending GNNs to other BaB stages—specifically predicting fast warm-start values for LP solvers, or creating "lazy verifiers" that use GNN estimates to skip unnecessary LP evaluations.
Summary updated