Parametric Chordal Sparsity for SDP-based Neural Network Verification

Anton Xue, Lars Lindemann, Rajeev Alur

Abstract

Many future technologies rely on neural networks, but verifying the correctness of their behavior remains a major challenge. It is known that neural networks can be fragile in the presence of even small input perturbations, yielding unpredictable outputs. The verification of neural networks is therefore vital to their adoption, and a number of approaches have been proposed in recent years. In this paper we focus on semidefinite programming (SDP) based techniques for neural network verification, which are particularly attractive because they can encode expressive behaviors while ensuring a polynomial time decision. 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. When the size of the neural network grows, however, solving this SDP quickly becomes intractable. Our key observation is that by leveraging chordal sparsity and specific parametrizations of DeepSDP, we can decompose the primary computational bottleneck of DeepSDP -- a large linear matrix inequality (LMI) -- into an equivalent collection of smaller LMIs. Our parametrization admits a tunable parameter, allowing us to trade-off efficiency and accuracy in the verification procedure. We call our formulation Chordal-DeepSDP, and provide experimental evaluation to show that it can: (1) effectively increase accuracy with the tunable parameter and (2) outperform DeepSDP on deeper networks.

Introduction

Verifying that a neural network is "safe"—for instance, ensuring an autonomous vehicle maintains its lane under varying sensor noise—is a critical yet difficult task. Neural networks are non-linear and high-dimensional, often behaving as "black boxes." One promising verification approach is DeepSDP, which employs Semidefinite Programming (SDP) to construct a convex envelope around the network's behavior.

While DeepSDP offers high accuracy, it suffers from severe scalability issues. As networks grow deeper or verification horizons extend, the underlying Linear Matrix Inequality (LMI) becomes a massive computational bottleneck. Standard solvers for these LMIs typically scale cubically ($O(N^3)$), leading to memory exhaustion or impractical runtimes for even moderately sized networks. This paper introduces Chordal-DeepSDP, a framework that exploits "chordal sparsity" to decompose large matrix problems into smaller, overlapping ones, achieving significant speedups without sacrificing mathematical precision.

Methods

The proposed approach utilizes a two-stage optimization strategy to enhance scalability.

Chordal Decomposition

The authors demonstrate that the large matrix in DeepSDP possesses an inherent "chordal" structure. In graph theory, chordal graphs allow for the decomposition of a single large semidefinite constraint into a set of smaller, overlapping constraints. This transformation is mathematically exact, ensuring that the verification results remain identical while the solver processes the problem much faster.

Sparsity patterns of the large Linear Matrix Inequality (LMI) in DeepSDP, illustrating the inherent chordal structure.

Double Decomposition (Chordal-DeepSDP-2)

A further refinement, termed Chordal-DeepSDP-2, identifies internal zeros within the already-decomposed sub-matrices. This allows for a second level of "double" decomposition, further reducing the size of the individual LMIs.

Decomposition of the large LMI into smaller, overlapping sub-matrices (cliques) represented by the red blocks.

Adjacent-Layer Abstractions

To improve accuracy, the framework incorporates tighter bounds between adjacent layers using interval analysis (e.g., from the LiRPA library). Crucially, the authors prove that these additional constraints do not disrupt the chordal sparsity pattern, maintaining the computational efficiency of the decomposition.

Experimental Evaluation

The methods were evaluated on discrete-time dynamical systems, specifically a frictionless cart-pole system. Two network architectures were tested: Cart10 (hidden layers of size 10) and Cart40 (hidden layers of size 40). These networks were "unrolled" over up to 30 time steps to simulate long-term trajectories.

Key Results

  • Scalability: On the Cart10 network, the original DeepSDP failed due to memory limits after only 8 steps. In contrast, Chordal-DeepSDP-2 successfully verified trajectories up to 30 steps for the larger Cart40 network.
  • Performance: The chordal methods outperformed the baseline by orders of magnitude. For Cart10 at 7 steps, the baseline required over 1200 seconds, whereas Chordal-DeepSDP-2 completed the task in approximately 10 seconds.
  • Deep Reach: The ability to verify up to 30 steps represents a significant advancement over standard DeepSDP, which is typically limited to much shorter horizons.
  • Dualization: Preprocessing the problem with Dualization.jl provided additional speedups, likely by optimizing the problem structure for the MOSEK solver's heuristics.

Discussion and Conclusion

A significant insight of this work is the formal proof that DeepSDP's structure is chordal regardless of the specific safety specification (e.g., $L_2$ gain or reachability). This universality allows for flexible "stacking" of various quadratic constraints to tighten verification bounds without breaking the underlying computational advantages.

However, limitations remain. While the method scales effectively with network depth, it still faces challenges with very wide layers. If a single layer contains thousands of neurons, the decomposed sub-matrices remain large, and the cubic scaling bottleneck persists. Future work may explore more complex polynomial optimization, such as Sum-of-Squares, to provide even tighter bounds, and further investigate the interaction between problem formulation and solver heuristics.

Summary updated

Abstract

Many future technologies rely on neural networks, but verifying the correctness of their behavior remains a major challenge. It is known that neural networks can be fragile in the presence of even small input perturbations, yielding unpredictable outputs. The verification of neural networks is therefore vital to their adoption, and a number of approaches have been proposed in recent years. In this paper we focus on semidefinite programming (SDP) based techniques for neural network verification, which are particularly attractive because they can encode expressive behaviors while ensuring a polynomial time decision. 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. When the size of the neural network grows, however, solving this SDP quickly becomes intractable. Our key observation is that by leveraging chordal sparsity and specific parametrizations of DeepSDP, we can decompose the primary computational bottleneck of DeepSDP -- a large linear matrix inequality (LMI) -- into an equivalent collection of smaller LMIs. Our parametrization admits a tunable parameter, allowing us to trade-off efficiency and accuracy in the verification procedure. We call our formulation Chordal-DeepSDP, and provide experimental evaluation to show that it can: (1) effectively increase accuracy with the tunable parameter and (2) outperform DeepSDP on deeper networks.
BibTeX
@article{xue2024parametric,
  author = {Anton Xue and Lars Lindemann and Rajeev Alur},
  title = {{Parametric Chordal Sparsity for SDP-based Neural Network Verification}},
  journal = {Automatica},
  year = {2024},
  doi = {10.1016/j.automatica.2023.111487},
}
Figure