Verifying safety of neural networks from topological perspectives

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

TL;DR

This paper introduces a novel approach to neural network (NN) safety verification by leveraging topological properties like homeomorphisms and open maps. By proving that the boundary of an output set is determined solely by the boundary of the input set, the authors demonstrate that we can ignore the "interior" of input sets during reachability analysis, significantly reducing computational costs and the "wrapping effect" that plagues traditional verification methods.

What Problem Does This Paper Address?

As neural networks are increasingly deployed in safety-critical systems like autonomous vehicles, we need rigorous guarantees that they won't produce "unsafe" outputs. This is typically handled via reachability analysis: given a set of possible inputs, what is the set of all possible outputs?

The challenge is that NNs are high-dimensional and non-linear, making exact reachability computation nearly impossible. Researchers usually rely on over-approximation—calculating a "box" or "polytope" that is guaranteed to contain all possible outputs. However, these approximations suffer from the wrapping effect, where errors accumulate layer-by-layer, eventually producing a result so conservative (large) that it’s useless for safety verification. While partitioning the input set into smaller pieces helps, it leads to an exponential explosion in the number of subsets to check.

Methods

The authors shift the focus from "calculating everything" to "calculating only the edges" by exploiting two topological properties:

  1. Homeomorphism: A property of certain NNs (like Neural ODEs and i-ResNets) where the mapping is a continuous bijection with a continuous inverse. Crucially, a homeomorphism maps the boundary of an input set exactly to the boundary of the output set.
  2. Open Maps: A less strict property where the network maps open sets to open sets. The authors prove that "trapezoidal" NNs—those where the number of neurons in each layer is non-increasing and weight matrices are full rank—act as open maps. In these cases, the boundary of the output set must originate from the boundary of the input set.

The Algorithms: * Algorithm 1 (Invertible NNs): If the NN is a homeomorphism, the method extracts only the boundary of the input set and performs reachability analysis on it. If the boundary's output is safe, the interior is guaranteed to be safe. * Algorithm 2 (General NNs): For networks that aren't globally invertible, the authors identify "local" subsets where the homeomorphism property holds. They then "abandon" the interiors of these subsets, focusing computation only on the remaining regions and boundaries.

Datasets

The paper evaluates the method using several benchmark neural network structures rather than standard image datasets:

  • Neural ODEs: A nonlinear 2D spiral and a 12D controlled cartpole model.
  • Invertible NNs: Fully connected networks with Sigmoid activations (N3 and N4).
  • General Feedforward NNs: A series of "trapezoidal" networks (N6 through N11) with varying depths and widths (up to 80 neurons per layer) to test scalability and the open map property.

Key Insights and Ideas

  • Boundary Sufficiency: The "aha moment" is the realization that if your network is topologically well-behaved, the interior of your input set is redundant for safety verification. You only need to know where the "envelope" of the set ends up.
  • Taming the Wrapping Effect: By only propagating the boundary, the volume of the set being over-approximated is much smaller. This leads to significantly tighter bounds than traditional "entire-set" methods.
  • The Prevalence of Open Maps: Most classification NNs naturally decrease in dimension (e.g., from 784 pixels to 10 classes). The authors show these "trapezoidal" structures are naturally suited for open-map-based verification, making their topological approach broadly applicable.

Key Results

  • Efficiency Gains: In a Neural ODE example (N1), the set-boundary method reduced computation time by 72.2% compared to analyzing the entire input set.
  • Partitioning Reduction: For one safety property, the standard method required dividing the input into 10,000 subsets to verify safety. The boundary-based method achieved the same result with only 400 partitions.
  • Tighter Bounds: When compared against standard tools like IBP (Interval Bound Propagation) and DeepZ, the boundary-based approach produced reachable sets that were 3% to 40% tighter.
  • Comparison with Verisig 2.0: On smaller networks, the proposed method reduced the over-approximated reachable set size by 20% to 80% while often requiring lower polynomial orders for the Taylor models used in the analysis.

Limitations and Future Work

  • Jacobian Complexity: Identifying homeomorphisms requires checking if the Jacobian determinant is non-zero. The current method uses interval arithmetic for this, which the authors admit is "coarse" and can be computationally expensive for very large networks.
  • Structural Constraints: The "open map" benefits are currently most clear for trapezoidal (non-increasing dimension) networks. Extending this to architectures with "bottlenecks" or expanding layers (like some autoencoders) remains a challenge.
  • Future Directions: The authors plan to develop more efficient, parallelized techniques for Jacobian calculation and integrate their boundary-analysis framework into existing state-of-the-art verification toolboxes.

Summary updated

Abstract

Highlights•To the best of our knowledge, this is the first work using topological properties of NNs to tackle the safety verification problems of neural networks.•The proposed set-boundary based method controls the wrapping effect of existing reachability analysis methods for the safety verification of NNs.•Based on homeomorphisms or open maps, the computation burdens of safety verification problems can be reduced for NNs featuring these properties.•This work might on its own open future directions on digging into more insightful properties of facilitating reachability computations of NNs.
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