TL;DR
This paper introduces a novel machine learning boosting approach to convert the neurons of a neural network—represented as Linear Threshold Functions (LTFs)—into compact Aligned Binary Decision Diagrams (ABDDs) for formal verification. By eliminating the need to search through an exponential number of variable orderings ($n!$), this method generates smaller Boolean expressions much faster, particularly when the network's neurons exhibit large classification margins.
What Problem Does This Paper Address?
Formal verification is crucial for ensuring that neural networks (NNs) are safe and robust against adversarial attacks. One promising strategy is to translate a neural network into an equivalent Boolean expression (such as a Binary Decision Diagram, or BDD). Once converted, researchers can leverage decades of highly optimized hardware and circuit verification tools to prove network properties.
However, a major bottleneck lies in converting individual neurons—which function as Linear Threshold Functions (LTFs)—into BDDs. Existing exact methods require finding an optimal variable ordering out of $n!$ possibilities to prevent the BDD size from exploding exponentially. Choosing a good ordering is notoriously difficult and computationally prohibitive, severely limiting the scalability of neural network verification.
Methods
The authors tackle this bottleneck by introducing a top-down, greedy boosting algorithm that constructs a specific variant of a BDD called an Aligned BDD (ABDD).
Unlike standard BDDs or Ordered BDDs (OBDDs), an ABDD enforces a strict structural constraint: all nodes at the exact same depth must be labeled with the same variable.
The construction pipeline works as follows:
- The Boosting Framework: Inspired by classic top-down decision tree learning (specifically the work of Mansour and McAllester), the algorithm builds the ABDD layer-by-layer.
- Split Step: At each layer, the algorithm selects a single variable (a base classifier) that maximizes an information-theoretic criterion based on a newly introduced variant balanced distribution ($\hat{d}$).
- Merge Step: To keep the diagram compact, the algorithm merges similar nodes within the same layer using a mathematical structure called a $(\delta, \lambda)$-net.
- Circuit Conversion: Once the ABDDs are built for each neuron, they are wired together according to the network's topology to form a massive $(\lor, \land, \neg)$-circuit, which can then be compiled into a Sentential Decision Diagram (SDD) for final robustness verification.
Datasets
The authors evaluated their approach using the USPS digits dataset, a standard benchmark consisting of $16 \times 16$ binary pixel images of handwritten digits. They focused on the binary classification task of distinguishing between the digits 0 and 1. This data was used to train 10 different Convolutional Neural Networks (CNNs) containing two convolutional layers and one fully connected layer, which served as the verification targets.
Key Insights and Ideas
- The Power of Alignment: Intuitively, forcing every node at a given depth to use the exact same variable seems like a restriction that would yield larger diagrams. Surprisingly, the authors found the opposite: this alignment makes the node-merging process drastically more effective in practice, resulting in much smaller final diagrams.
- Margin-Driven Complexity: The size of the generated ABDD is theoretically bounded by the margin ($\rho$) of the LTF. If a neuron classifies its training samples with a wide margin, the algorithm guarantees a small BDD size ($O(\frac{n^2}{\rho^4}\ln{\frac{1}ρ})$), completely bypassing the need to search through $n!$ variable orderings.
- Accelerated Entropy Reduction: During the top-down construction, once node merging begins, the total entropy of the ABDD drops at a significantly faster rate than standard BDD approaches.
Key Results
- Fewer Gates: In evaluations across 10 different CNN architectures, the proposed method consistently generated circuits with far fewer gates than competing techniques. For example, on the first network configuration (ID 1), the authors' method required only 3,737 gates, compared to 5,536 gates for the baseline OBDD method (Shi.1) and over 48,000 gates for alternative precision-based methods (Shi.2).
- Faster Verification: Because the resulting Boolean circuits were significantly more compact, the time required to run Sample-based Robustness (SR) verification algorithms was substantially reduced.
Limitations and Future Work
While the boosting approach successfully avoids the $n!$ variable ordering search, its time complexity still scales with $2^n$ because it evaluates all possible instances of the LTF. As a result, this method is currently restricted to smaller input dimensions or networks with small localized receptive fields (like the $3 \times 3$ convolutions tested).
For future work, the authors aim to extend this boosting framework to handle more complex, non-binary, and larger-scale neural network architectures.
Summary updated