Syntactic vs Semantic Linear Abstraction and Refinement of Neural Networks

Calvin Chau, Jan Kretínský, Stefanie Mohr

Abstract

Modern neural networks are often significantly over-parameterized, leading to challenges in formal verification and interpretability. This paper introduces LiNNA (Linear Neural Network Abstraction), a framework that reduces network size by representing groups of neurons as linear combinations of a smaller basis set. Unlike previous methods that rely on one-to-one neuron clustering, LiNNA leverages linear relationships to achieve higher compression rates while maintaining accuracy. We explore both syntactic and semantic abstraction methods and introduce an abstraction-refinement loop to handle counterexamples. Our results across MNIST, FashionMNIST, and CIFAR-10 demonstrate that LiNNA outperforms existing state-of-the-art abstraction techniques in both scalability and precision.

1. Introduction

The rapid advancement of deep learning has led to the deployment of increasingly large and complex neural networks. However, this over-parameterization creates a "state-space explosion" that makes formal verification—proving a network's safety or robustness—computationally expensive. Furthermore, the internal logic of these "black box" models remains largely opaque to human observers.

Existing abstraction techniques typically attempt to simplify networks by clustering similar neurons and replacing them with a single representative. While useful, these methods are often too rigid; if a group of neurons does not share a near-identical profile, the resulting abstraction suffers from significant error. This paper proposes LiNNA, a framework that moves beyond simple replacement to a more flexible, linear-based abstraction model.

2. The LiNNA Framework

LiNNA operates by identifying a subset of neurons, termed the basis, which can effectively approximate the behavior of an entire layer. The process consists of three primary phases:

2.1 Finding the Basis

The framework offers two distinct strategies for basis selection:

  • Greedy Algorithm: An iterative approach that removes neurons which contribute the least to projection error. While highly accurate, it is computationally intensive.
  • Variance-based Heuristic: A faster alternative that selects neurons with the highest activation variance, under the assumption that high-variance neurons encode the most critical information.

2.2 Determining Coefficients

Once the basis is established, every other neuron in the layer is expressed as a linear combination of the basis neurons. This is achieved through either Orthogonal Projection (minimizing the L2 distance) or Linear Programming (minimizing the L1 distance).

2.3 Neuron Replacement and Weight Redistribution

The final step involves redistributing the outgoing weights of the original neurons to the basis neurons according to the calculated linear coefficients. This ensures that the overall influence of the layer on subsequent layers is preserved as closely as possible.

3. Syntactic vs. Semantic Abstraction

A key contribution of this work is the distinction between two abstraction paradigms:

  • Syntactic Abstraction: This approach compares neurons based solely on their structural properties, specifically their incoming weight vectors. It is data-independent but may miss functional similarities.
  • Semantic Abstraction: This approach evaluates neurons based on their actual activation values across a sample dataset. By observing how neurons behave in practice, semantic abstraction typically yields much tighter and more accurate models.

4. Abstraction-Refinement

To ensure the reliability of the abstracted network, we implement an Abstraction-Refinement loop. If the reduced network produces a counterexample (e.g., a misclassification that the original network handled correctly), the system can selectively "un-abstract" or restore specific neurons. This allows for an aggressive initial reduction (e.g., 90%) followed by targeted refinement to regain necessary precision.

5. Experimental Evaluation

We evaluated LiNNA on three standard benchmarks: MNIST, FashionMNIST, and CIFAR-10. The test architectures included feedforward networks with 3 to 11 hidden layers and varying widths (50 to 2500 neurons per layer).

5.1 Key Findings

  • Superior Compression: LiNNA consistently outperformed state-of-the-art methods like DeepAbstract. On MNIST, the framework maintained stable accuracy even after a 60% reduction in neuron count.
  • Scalability: In larger networks (400+ neurons per layer), LiNNA achieved up to 80% reduction without significant performance degradation, whereas traditional bisimulation-based methods failed beyond 55%.
  • Efficiency: The combination of the variance-based heuristic and orthogonal projection allows for abstractions to be generated in seconds, offering a 100x speedup over linear programming-based approaches.
  • Theoretical Soundness: We provide a mathematical upper bound (Theorem 1) on the error introduced by the abstraction. While the theoretical bound is conservative, empirical evidence shows that the actual error on unseen data remains remarkably low.

6. Conclusion and Future Work

LiNNA demonstrates that linear abstraction is a powerful tool for reducing the complexity of neural networks without sacrificing functional integrity. While the method is highly effective for MNIST and FashionMNIST, the sharper accuracy drop observed on CIFAR-10 suggests that more complex features may require non-linear abstraction mappings.

Future research will focus on extending LiNNA to more diverse architectures, such as Convolutional Neural Networks (CNNs) and Transformers, and integrating the framework directly with formal verifiers to quantify the resulting speedups in safety proofs.

Summary updated

BibTeX
@inproceedings{chau2023syntactic,
  author = {Calvin Chau and Jan Kretínský and Stefanie Mohr},
  title = {{Syntactic vs Semantic Linear Abstraction and Refinement of Neural Networks}},
  booktitle = {ATVA},
  year = {2023},
  doi = {10.1007/978-3-031-45329-8\_19},
}
Figure