Verifying Safety of Neural Networks from Topological Perspectives

Zhen Liang, Dejin Ren, Bai Xue, Ji Wang, Wenjing Yang, Wanwei Liu

Introduction

As neural networks (NNs) are increasingly deployed in safety-critical domains such as autonomous driving and robotics, the need for formal safety guarantees becomes paramount. A primary technique for providing these guarantees is reachability analysis, which seeks to determine the set of all possible outputs given a set of potential inputs. However, the high-dimensional, non-linear nature of NNs makes exact reachability computation intractable.

Traditional methods rely on over-approximation, calculating geometric containers (like boxes or polytopes) that encompass all possible outputs. These methods frequently suffer from the wrapping effect, where approximation errors accumulate across layers, leading to overly conservative bounds that are often too large to be useful for safety verification. While partitioning input sets can improve precision, it often results in an exponential increase in computational complexity.

Topological Foundations for Reachability

This research introduces a novel paradigm by shifting the focus from the entire input set to its boundary. This approach leverages two key topological properties:

  1. Homeomorphism: In certain architectures like Neural ODEs and i-ResNets, the mapping is a continuous bijection with a continuous inverse. A crucial property of homeomorphisms is that they map the boundary of an input set precisely to the boundary of the output set.
  2. Open Maps: A broader class of mappings where open sets are mapped to open sets. The authors demonstrate that "trapezoidal" NNs—those with non-increasing layer widths and full-rank weight matrices—function as open maps. For these networks, the boundary of the output set must originate from the boundary of the input set.
Comparison of non-homeomorphic, homeomorphic, and open maps.

By exploiting these properties, the authors propose two primary algorithms. For invertible NNs (homeomorphisms), reachability analysis is performed solely on the input boundary. If the boundary's output is safe, the entire interior is guaranteed safe. For general NNs, the method identifies local regions where the homeomorphism property holds, allowing the algorithm to "abandon" the interiors of these subsets and focus computation on the remaining boundaries.

Evaluation and Key Results

The proposed framework was evaluated across various benchmarks, including Neural ODEs (e.g., a 12D controlled cartpole) and several "trapezoidal" feedforward networks.

The topological approach demonstrated significant improvements over state-of-the-art methods:

  • Efficiency: In a Neural ODE example, analyzing only the set boundary reduced computation time by 72.2%.
  • Precision: The boundary-based method produced reachable sets that were 3% to 40% tighter than those generated by standard tools like Interval Bound Propagation (IBP) and DeepZ.
  • Scalability: For specific safety properties, the standard partitioning method required 10,000 subsets, whereas the boundary-based approach achieved verification with only 400 partitions.
Visualization of reachable sets and their over-approximations. (a) shows the true reachable set and its boundary; (b) shows various bounding boxes; (c) overlays these to demonstrate the tightness of the boundary-based approach.

Conclusion and Future Directions

By proving that the interior of a topologically well-behaved input set is redundant for safety verification, this work provides a powerful tool for taming the wrapping effect. While currently most effective for trapezoidal architectures, future work aims to extend these benefits to more complex structures, such as those with bottlenecks. Additionally, the authors plan to optimize Jacobian calculations—currently a computational bottleneck for large networks—to further enhance the scalability of this topological verification framework.

Summary updated

BibTeX
@article{liang2024verifying,
  author = {Zhen Liang and Dejin Ren and Bai Xue and Ji Wang and Wenjing Yang and Wanwei Liu},
  title = {{Verifying Safety of Neural Networks from Topological Perspectives}},
  journal = {Sci. Comput. Program.},
  year = {2024},
  doi = {10.1016/j.scico.2024.103121},
}
Figure