Abstract
Formal verification of neural networks is essential for their deployment in safety-critical areas. Many available formal verification methods have been shown to be instances of a unified Branch and Bound (BaB) formulation. We propose a novel framework for designing an effective branching strategy for BaB. Specifically, we learn a graph neural network (GNN) to imitate the strong branching heuristic behaviour. Our framework differs from previous methods for learning to branch in two main aspects. Firstly, our framework directly treats the neural network we want to verify as a graph input for the GNN. Secondly, we develop an intuitive forward and backward embedding update schedule. Empirically, our framework achieves roughly 50% reduction in both the number of branches and the time required for verification on various convolutional networks when compared to the best available hand-designed branching strategy. In addition, we show that our GNN model enjoys both horizontal and vertical transferability. Horizontally, the model trained on easy properties performs well on properties of increased difficulty levels. Vertically, the model trained on small neural networks achieves similar performance on large neural networks.
Introduction
As neural networks are increasingly deployed in safety-critical systems like autonomous driving and healthcare, formal guarantees of robustness are becoming a necessity. Formal verification aims to provide these guarantees, ensuring that a network will not fail under adversarial pressure.
Most state-of-the-art verification tools utilize a Branch and Bound (BaB) framework. BaB recursively partitions the search space (branching) and calculates bounds on the network's output for those spaces (bounding). The efficiency of this process depends heavily on the branching strategy—the logic used to decide which neuron to split next. Currently, practitioners face a trade-off: "Strong Branching" provides high-quality decisions but is computationally expensive, while hand-designed heuristics are fast but often lead to an exponential increase in the number of branches required to solve a problem.
Methodology
The proposed framework uses Graph Neural Networks (GNNs) to learn a branching policy that imitates strong branching at a fraction of the computational cost. Key technical innovations include:
The Network as a Graph
Unlike generic "learning to branch" approaches that use abstract features, this framework treats the target neural network directly as the graph input for the GNN. This allows the model to leverage the specific structural properties and learned weights of the architecture being verified.
Forward and Backward Update Schedule
To update node embeddings effectively, the GNN mimics the natural forward and backward passes of a neural network. This schedule captures how a relaxation at a specific neuron propagates through subsequent and preceding layers, allowing the GNN to understand the global impact of a local branching decision on the final output bounds.
Training and Robustness
The model is trained using a Hinge Rank Loss, which focuses on correctly ordering potential branching candidates based on their predicted improvement to the global bound. To ensure reliability, the system includes a "fail-safe" mechanism that reverts to a standard heuristic if the GNN's predictions are deemed poor, alongside an online learning component for fine-tuning on difficult properties.
Experimental Results
The researchers evaluated the framework on MNIST and CIFAR-10 networks across various architectures (Base, Wide, Deep) and difficulty levels.
Efficiency and Performance
On CIFAR-10, the GNN framework achieved a 50% reduction in both the number of branches and total verification time compared to BaBSR, the leading hand-designed heuristic. Furthermore, it consistently outperformed MIPplanet, a method utilizing the commercial Gurobi solver, particularly as problem difficulty increased.
Transferability
A key finding is the model's vertical transferability: a GNN trained on small networks performs effectively on much larger networks. This is crucial because generating training data (strong branching) for large networks is computationally prohibitive. Additionally, the model exhibits horizontal transferability, where training on "easy" properties generalizes well to "hard" ones.
Conclusion and Future Work
While the GNN-based branching strategy significantly accelerates verification, some limitations remain. The model's performance is currently dataset-specific; for instance, a model trained on CIFAR-10 does not transfer well to MNIST. Furthermore, the "bounding" step remains a significant computational bottleneck. Future research may explore using GNNs to optimize the Linear Programs (LPs) used in bounding or developing "lazy verifiers" that prioritize LP solving based on GNN predictions.
Summary updated