Chordal sparsity for SDP-based neural network verification

Anton Xue, Lars Lindemann, Rajeev Alur

TL;DR

This paper introduces Chordal-DeepSDP, a novel method that leverages "chordal sparsity" to significantly speed up the verification of neural networks using semidefinite programming (SDP). By decomposing large, computationally expensive SDP problems into smaller, manageable ones, this approach makes verifying complex neural networks more practical without sacrificing accuracy.

What Problem Does This Paper Address?

Verifying the safety and correctness of neural networks is crucial for their adoption in safety-critical applications like autonomous driving. Neural networks can be notoriously opaque and sensitive to small input changes, making traditional testing insufficient. Semidefinite programming (SDP) offers a powerful way to express complex verification constraints, but its scalability has been a major bottleneck, especially for larger networks. The DeepSDP framework, while effective, becomes computationally intractable as network size increases. This paper tackles this scalability challenge head-on.

Methods

The core innovation is the application of chordal sparsity to the SDP formulation of neural network verification. The authors build upon the DeepSDP framework, which uses quadratic constraints to abstract neural network components. They identify that the large Linear Matrix Inequality (LMI) constraint in DeepSDP possesses a specific sparsity pattern that can be exploited.

  1. Chordal-DeepSDP: The paper first proves that the DeepSDP problem inherently admits a "chordal sparse decomposition." This means the large LMI can be rewritten as an equivalent set of smaller LMIs. This decomposition is proven to be identically expressive as the original DeepSDP, meaning no accuracy is lost.
  2. Chordal-DeepSDP-2: A further level of decomposition is introduced by analyzing the structure of the chordal extension. This "double decomposition" further breaks down the smaller LMIs, leading to even greater computational gains.
  3. Adjacent-Layer Abstractions: The authors also show how to incorporate additional, more precise abstractions for activation functions (beyond the basic sector-bounded ones) without altering the chordal sparsity structure. This allows for tighter bounds and improved verification accuracy.

Datasets

The paper uses synthetic datasets generated from simulating closed-loop dynamical systems, specifically the cart-pole dynamics. They train neural networks of varying sizes (e.g., Cart40, Cart10) to model these dynamics over multiple time steps (t=1 to t=30). These networks are used to evaluate the scalability and accuracy of their proposed methods.

Key Insights and Ideas

  • Chordal Sparsity is Inherent: The paper formally proves that the sparsity pattern in DeepSDP is amenable to chordal decomposition, a property that was previously conjectured or assumed for specific cases.
  • Decomposition = Scalability: The core insight is that by exploiting this chordal sparsity, a large, intractable SDP can be broken down into a collection of smaller, more manageable SDPs, drastically improving computational efficiency.
  • No Accuracy Loss: Crucially, the proposed Chordal-DeepSDP and Chordal-DeepSDP-2 methods are proven to be equivalent to the original DeepSDP, meaning they offer the same verification guarantees.
  • Flexibility in Abstractions: The framework is shown to be flexible, allowing for the incorporation of various activation function abstractions (like bounded-nonlinearity QCs) without compromising the benefits of chordal decomposition.

Key Results

  • Significant Speedup: Numerical experiments show that Chordal-DeepSDP and Chordal-DeepSDP-2 significantly outperform the original DeepSDP in terms of runtime. For instance, for deeper networks (Cart10(t)), Chordal-DeepSDP and Chordal-DeepSDP-2 are orders of magnitude faster than DeepSDP.
  • Handling Larger Networks: DeepSDP often runs out of memory for moderately sized networks (e.g., Cart40(3)), while the proposed methods can handle much deeper and more complex network simulations.
  • Improved Accuracy with Abstractions: Using adjacent-layer abstractions in conjunction with chordal decomposition leads to tighter bounds for verification tasks, such as bounding the L2 gain of the system.
  • Dualization.jl Boost: Preprocessing DeepSDP with the Dualization.jl package also yielded substantial speedups, sometimes exceeding 10x, though the authors note this is a surprising phenomenon.

Limitations and Future Work

  • Wide Layers: The current decomposition method does not effectively decompose very wide layers. While this is not an issue for the deep, unrolled dynamical systems used in experiments, it could be a limitation for networks with very wide individual layers.
  • Newer Abstractions: The paper suggests exploring more advanced activation abstractions beyond sector-bounded inequalities to further improve verification accuracy.
  • Polynomial Optimization: The authors point to polynomial optimization (e.g., sum-of-squares) as a promising direction for more expressive verification, but note that these methods currently rely on large SDPs, highlighting the continued importance of sparsity exploitation.
  • Equivalence of Chordal-DeepSDP-2: While experiments suggest equivalence, the formal proof that Chordal-DeepSDP-2 is equivalent to Chordal-DeepSDP (not just that it implies feasibility) is left as a conjecture.

Summary updated

Abstract

Neural networks are central to many emerging technologies, but verifying their correctness remains a major challenge. It is known that network outputs can be sensitive and fragile to even small input perturbations, thereby increasing the risk of unpredictable and undesirable behavior. Fast and accurate verification of neural networks is therefore critical to their widespread adoption, and in recent years, various methods have been developed as a response to this problem. In this paper, we focus on improving semidefinite programming (SDP) based techniques for neural network verification. Such techniques offer the power of expressing complex geometric constraints while retaining a convex problem formulation, but scalability remains a major issue in practice. Our starting point is the DeepSDP framework proposed by Fazlyab et al., which uses quadratic constraints to abstract the verification problem into a large-scale SDP. However, solving this SDP quickly becomes intractable when the network grows. Our key observation is that by leveraging chordal sparsity, we can decompose the primary computational bottleneck of DeepSDP -- a large linear matrix inequality (LMI) -- into an equivalent collection of smaller LMIs. We call our chordally sparse optimization program Chordal-DeepSDP and prove that its construction is identically expressive as that of DeepSDP. Moreover, we show that additional analysis of Chordal-DeepSDP allows us to further rewrite its collection of LMIs in a second level of decomposition that we call Chordal-DeepSDP-2 -- which results in another significant computational gain. Finally, we provide numerical experiments on real networks of learned cart-pole dynamics, showcasing the computational advantage of Chordal-DeepSDP and Chordal-DeepSDP-2 over DeepSDP.
BibTeX
@article{xue2024chordal,
  author = {Anton Xue and Lars Lindemann and Rajeev Alur},
  title = {{Chordal sparsity for SDP-based neural network verification}},
  journal = {Automatica},
  year = {2024},
  doi = {10.1016/j.automatica.2023.111487},
}
Figure