Optimizing Neural Network Representations of Boolean Networks

Authors: Joshua Russell, Ignacio Gavier, Devdhar Patel, Edward Rietman, Hava T Siegelmann
Primary area: optimization
Keywords: Neural Networks, Boolean Networks, Lossless Optimization, Integer Linear Programming, NPN Classification

Abstract:
Neural networks are known to be universal computers for Boolean functions. Recent advancements in hardware have significantly reduced matrix multiplication times, making neural network simulation both fast and efficient. Consequently, functions defined by complex Boolean networks are increasingly viable candidates for simulation through their neural network representation. Prior research has introduced a general method for deriving neural network representations of Boolean networks. However, the resulting neural networks are often suboptimal in terms of the number of neurons and connections, leading to slower simulation performance. Optimizing them while preserving functional equivalence --lossless optimization-- is an NP-hard problem, and current methods only provide lossy solutions. In this paper, we present a deterministic algorithm to optimize such neural networks in terms of neurons and connections while preserving functional equivalence. Moreover, to accelerate the compression of the neural network, we introduce an objective-aware algorithm that exploits representations that are shared among subproblems of the overall optimization. We demonstrate experimentally that we are able to reduce connections and neurons by up to 70% and 60%, respectively, in comparison to state-of-the-art. We also find that our objective-aware algorithm results in consistent speedups in optimization time, achieving up to 34.3x and 5.9x speedup relative to naive and caching solutions, respectively. Our methods are of practical relevance to applications such as high-throughput circuit simulation and placing neurosymbolic systems on the same hardware architecture.

Decision: accept (poster)
Reviewer scores: 5, 6, 8, 8

Reviews and discussion:
<thread>
creation date:
1730618961807

thread_type:
official_review

<thread_object>
creator: reviewer_vak3

<content>
summary:
This paper addresses the challenge of optimizing neural network (NN) representations of Boolean networks (BNs). The authors point out that while NNs can represent Boolean functions, the current state-of-the-art method for deriving these representations often results in suboptimal NNs with a large number of neurons and connections, leading to inefficient simulation. Existing NN compression techniques are either lossy or inapplicable due to the specific nature of the NN-based technology mapping problem.

The paper makes three key contributions. First, it proposes a novel lossless technique for optimizing two-layer NN representations of Boolean functions, focusing on reducing the number of neurons and connections while preserving functional equivalence. This is achieved by formulating the problem as a constrained minimization task and employing a convex relaxation technique to solve it.  Second, the authors introduce an objective-aware optimization algorithm that leverages Negation-Permutation-Negation (NPN) classification. This algorithm exploits shared representations among the two-layer sub-networks to significantly speed up the optimization process, demonstrating a substantial speedup over naive and caching-based solutions. Third, an architecture-aware lossless optimization algorithm is proposed, targeting both unmerged and layer-merged NN architectures. This algorithm determines which sub-NNs should be minimized to achieve overall NN size reduction while optionally maintaining the depth of the layer-merged network, which is critical for latency-sensitive applications. Experimental results on benchmark BNs derived from digital circuits show significant reductions in the size of the resulting NNs, confirming the effectiveness of the proposed optimization techniques.

strengths:
**Originality:** The paper tackles the problem of optimizing NN representations of Boolean networks from a fresh perspective. While NN compression is a well-studied area, the authors identify a specific gap in existing techniques, namely the lack of *lossless* methods applicable to the BN-to-NN mapping problem. They creatively combine ideas from Boolean function classification (NPN) and convex optimization to develop a new approach to address this gap. The concept of leveraging NPN classes to accelerate the optimization by exploiting shared representations among subproblems is particularly original and demonstrates a deep understanding of the underlying structure of the problem. Moreover, the introduction of the *leeway* concept and the architecture-aware algorithm for maintaining depth in layer-merged NNs showcases innovative thinking in adapting the optimization process to different NN architectures.

**Quality:** The paper is technically sound, with rigorous mathematical formulations and proofs supporting the proposed methods. The authors carefully define the necessary concepts and notation, ensuring clarity in their technical exposition. The experimental methodology is well-designed, with appropriate benchmarks and metrics used for evaluation. The comparison against relevant baselines (naive and caching solutions) provides a strong validation of the proposed techniques. The inclusion of additional results and analysis in the appendix further reinforces the quality of the work.

**Clarity:** The paper is generally well-written and organized. The introduction effectively motivates the problem and summarizes the key contributions. The background section provides the necessary context and definitions, though perhaps could benefit from a slightly higher-level motivating example early on for a broader audience.  The use of figures, especially Figure 1, significantly aids in understanding the optimization problem and the proposed approach. The steps of the algorithms are clearly presented, and the results are reported in a concise and informative manner.

**Significance:** The paper addresses an important problem with practical implications for various domains. Efficient BN simulation is crucial in areas like circuit verification and design automation. The proposed optimization techniques can lead to substantial reductions in NN size and faster optimization times, making NN-based BN simulation more practical and scalable. Moreover, the connection to neurosymbolic AI highlights the potential of the work for advancing this emerging field. The ability to represent symbolic systems efficiently using NNs could pave the way for new hardware architectures and algorithms that combine the strengths of both symbolic and connectionist AI approaches.  The paper's focus on lossless compression is also significant from a safety and reliability perspective, as it ensures that the optimized NN representation remains functionally equivalent to the original BN.

weaknesses:
1. **Impact of L1 Relaxation:** The authors acknowledge that relaxing the ℓ0-norm objective to ℓ1 might lead to suboptimal solutions. However, the paper lacks a detailed analysis of the extent to which this relaxation affects the quality of the results.  Quantifying the gap between the ℓ0 and ℓ1 solutions for the benchmark BNs, or investigating alternative approximation methods for the ℓ0-norm minimization, would provide a more complete understanding of the trade-offs involved.  Perhaps experiments comparing the optimized NN size obtained with ℓ1 relaxation to theoretical lower bounds achievable with ℓ0 could highlight the potential room for improvement.

2. **Scalability to Larger BNs:** The experimental results suggest that the optimization time can become substantial for large BNs and higher values of K (maximum input size of LUTs).  While the NPN classification algorithm offers speedups compared to caching, the paper does not thoroughly investigate the scalability limitations of the overall method.  Analyzing the runtime complexity as a function of BN size and K, and potentially exploring strategies for further improving the efficiency of the optimization process (e.g., by leveraging parallelism or more sophisticated data structures), would be beneficial.  Consider profiling the algorithms to pinpoint bottlenecks and focus optimization efforts.

3. **Clarity and Accessibility for a Broader Audience:** Although the technical content is generally well-explained, the paper could benefit from a more intuitive and accessible introduction to the problem and its significance. Providing a high-level illustrative example that highlights the practical implications of optimizing NN representations of BNs would engage a broader readership within the ICLR community. While the paper currently focuses on a specialized audience with expertise in Boolean functions, making it more approachable for readers with a general machine learning background would enhance its impact.

questions:
1. **Generalization to other Boolean network domains:** The experimental results focus primarily on digital circuits. Could the authors elaborate on the applicability of their methods to other types of Boolean networks, such as gene regulatory networks or biological networks? Are there any specific adaptations or considerations needed for these domains?  Presenting results on even a small set of non-circuit BNs would greatly bolster the claim of general applicability.

2. **Scalability analysis and potential optimizations:** The optimization time appears to grow considerably with BN size and K. Could the authors provide a more detailed analysis of the computational complexity of their methods?  Are there any potential optimizations or algorithmic improvements that could be explored to enhance scalability, such as parallelization or more efficient data structures? A breakdown of execution time for different stages of the algorithm would help identify bottlenecks

3. **Clarifying the impact of NPN transformations on the number of MMP computations:**  The paper mentions that using NPN classification can reduce the number of MMP computations compared to function caching. However, the precise reduction factor ((2^k)!/2^(k+1)k!) is not immediately intuitive.  Could the authors provide a more detailed explanation of how this reduction is achieved and its significance in practice, perhaps with a concrete example for a small value of k?  It would be especially insightful to directly visualize how many MMP computations are saved for each benchmark circuit.

4.  **Connection to Neurosymbolic AI Implementations:**  The paper mentions the potential of the work for neurosymbolic AI, but the link is somewhat abstract.  Could the authors expand on how specifically the proposed methods could be integrated into neurosymbolic systems? For example, are there specific neurosymbolic architectures or frameworks where these optimized NN representations would be particularly beneficial?  Perhaps a concrete example application scenario, even if hypothetical, could illustrate the potential.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730648074882

thread_type:
official_review

<thread_object>
creator: reviewer_ec2r

<content>
summary:
In this work, the authors present an optimization framework for deriving representations of neural networks of Boolean networks. The overall goal of the proposed framework is to overcome known limitations of current state-of-the-art methodologies that result in suboptimal neural networks, in terms of number of neurons and connections, which hinders their application in real-case scenarios. More specifically, the proposed method introduces a lossless technique for optimizing neurons and connections needed in a two-layer NN representation of a Boolean function. This is achieved by establishing an optimization problem that transforms the pruning of the network architecture into monomial reduction tasks for a given polynomial. The lossless functionality between the Minimized Multilinear Polynomial and the represented Boolean function is achieved by incorporating the heavyside threshold of the NN, with the relaxation of the optimization objective to the $l_1$-norm providing the required convexity. Due to the NP-hard nature of the proposed optimization, the authors introduce an objective-aware optimization, which is based on Negation-Permutation-Negation classification, that constructs subclasses of multilinear polynomial representations for the minimization of the Boolean functions, exploiting the shared representations among them and accelerating the NN optimization process using unique function caching. Finally, the paper provides two alternatives for optimizing the Neural Networks, one that involves all the vertices of the binary networks to the minimization of the multilinear polynomial and another that selects the subset of vertices in such a way that the depth of the resulting layer-merged neural network does not increase. The proposed method achieves significant improvements in contrast to the state-of-the-art approach in terms of optimization speed and the required connections and neurons.

strengths:
The paper is very well organized and written, providing the necessary background as well as the required proofs to support the claims of the authors. The experimental results clearly reflect the contribution of this work.

The proposed method outperforms the current state-of-the-art in terms of decreasing the size of neural networks, which means the number of connections and neurons, while simultaneously preserving the equivalent functionality. The proposed lossless compression, along with the objective-aware optimization, resulting in a faster and more efficient solution than the state-of-the-art.

The paper establishes a novel framework for lossless optimization techniques for neural network representation of boolean networks that can provide further advantages to neurosymbolic AI.

weaknesses:
The proposed method is established in two-layer NN representation without discussing the potential generalization on the (2 + n) layer NN representation and the theoretical limits of the proposed method regarding this potential. Taking into account the non-stochastic nature of the proposed NPN transformation and the required time $O(m2^k) + e$, the proposed algorithm seems quite limited to the 2-layer NN representation. However, a further discussion of this can provide fruitful insights for future work.

Even though the relaxation of the optimization objective provides the required convexity, the problem still remains NP-hard. Indeed, the proposed deterministic solution ensures the lossless functionality of the binary network with the caching solution providing significant acceleration, hindering, however, the scalability of the proposed method in target networks. To this end, I recommend further discussion of the existing stochastic methodologies in the bibliography for lossy solution, studying the accuracy-efficiency tradeoff between deterministic and non-deterministic methodologies. In my opinion, the deterministic linear programing nature of the proposed optimization method should be noted in the abstract of the paper.

questions:
See Weaknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1730662761093

thread_type:
official_review

<thread_object>
creator: reviewer_wkfo

<content>
summary:
This paper presents a new approach to optimizing neural network representations of Boolean networks. The authors propose a technique compressing NNs via minimizing  the MP representation of each Boolean function in the network.

strengths:
* The paper provides a solid theoretical foundation for the proposed approach, such as the equation introduction of new concepts like NPN and detailed analysis of the underlying optimization problem.
* Evaluation looks comprehensive, including various bnchmarks, to demonstrate the effectiveness especialy in reducing network size and improving optimization time. 
* The proposed method looks interesting and novel as it combines multiple techniques including MP-based mapping, NPN equivalence classes and objec-aware optmization, to optimize representations of BNs.

weaknesses:
Please see questions.

questions:
* how well does it scale, as solving integer LP can be more demanding than solving LPs. 
* Computation complexity wiase, how does it compare against SOTAs?
* What's the impat of  NPN equivalence lasses on the optimization process?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730721509295

thread_type:
official_review

<thread_object>
creator: reviewer_vsf5

<content>
summary:
This paper proposes to optimize neural network representations of Boolean networks by improving the efficiency with NPN classification of sub-networks and considering objective in sub-networks during optimization. It achieves up to 5.9x speedup than the caching solution and reduces neurons and connections of final representations by 60% and 70% respectively.

strengths:
This paper proposes to speedup the optimization of neural network representation of Boolean functions and consider architecture constraints. Instead of solving each subproblems independently, the paper finds solutions of each NPN class and exploit shared optimized representations of two-layer sub-networks. The optimization of sub networks is modeled as finding a polynomial with fewer monomials or monomial degrees. In architecture aware lossless optimization part, the level constraints are considered when performing sub-network replacement.

weaknesses:
1. The scientific novelty is limited. NPN classification and level constraints based DAG optimization are common techniques used in logic synthesis tools and neural network compilers. 
2. The k-input LUT technology mapping lacks fair comparison with other traditional DAG optimization methods such as ABC (Boolean DAG optimization tools including technology indepedent and technology dependent optimization) and AI compilers like Google XLA.
3. Only two-layer sub-NN optimization is considered which is relatively too local for better neurons and level optimization.

questions:
1. Please provide comparison with traditional DAG optimization methods for a fair comparison.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732482510093

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response to the Reviewers

comment:
We sincerely thank the reviewers for their comprehensive evaluation of our submission, their insightful suggestions, and their contributions to enhancing the overall quality of our work. Moreover, we are encouraged by the positive feedback from the reviewers in the initial review, particularly regarding several key aspects:

**1) Theoretical contributions.** *The paper provides a solid theoretical foundation […] and detailed analysis of the underlying optimization problem (**Reviewer Wkfo**). The paper is technically sound, with rigorous mathematical formulations and proofs supporting the proposed methods (**Reviewer vaK3**).*

**2) Novelty.** *The paper tackles the problem of optimizing NN representations of Boolean networks from a fresh perspective (**Reviewer vaK3**). The authors identify a specific gap in existing techniques […]. They creatively combine ideas from Boolean function classification (NPN) and convex optimization to develop a new approach to address this gap (**Reviewer vaK3**). The concept of leveraging NPN classes to accelerate the optimization by exploiting shared representations among subproblems is particularly original (**Reviewer vaK3**). The paper establishes a novel framework for lossless optimization techniques for neural network representation of Boolean networks (**Reviewer eC2r**).*

**3) Broader impacts.** *The paper addresses an important problem with practical implications for various domains (**Reviewer vaK3**). The experimental results clearly reflect the contribution of this work (**Reviewer eC2r**). The connection to neurosymbolic AI highlights the potential of the work for advancing this emerging field (**Reviewer vaK3**).*

**4) Presentation.** *The paper is very well organized and written, providing the necessary background as well as the required proofs to support the claims of the authors (**Reviewer eC2r**). The paper is generally well-written and organized (**Reviewer vaK3**). The steps of the algorithms are clearly presented, and the results are reported in a concise and informative manner (**Reviewer vaK3**).*

We also appreciate the insightful and perceptive questions posed by the Reviewers. We have carefully considered each comment and hope that our responses below adequately address the Reviewers’ concerns.

---

The changelog below summarizes the revisions that have been made to the PDF submission.

- **Appendix C (MMP Representation)**
    1. We have expanded Remark C.2 to discuss in detail the time complexity for obtaining an MMP representation of a BF, the significance of the $\ell_1$-relaxation on running time, and why we do not consider a relaxation to a linear program over the reals.
    2. We have included a new Subsection C.1, which addresses the topic of solution suboptimality due to the $\ell_1$-relaxation of MMP problems.
- **Appendix D (Architecture-Aware Lossless Optimization)**
    1. We have added a new Remark D.6 on the space complexity of ``optMaintainDepth``.
- **Appendix E (NPN Classification Algorithm)**
    1. We have significantly expanded Subsection E.4 on the NPN classification algorithm, providing a thorough analysis of time and space complexity in comparison to the baselines.
    2. We have included a new Subsection E.5, which relates our NPN classification algorithm to existing NPN classification techniques in logic synthesis, and discusses important considerations behind our proposed algorithm.
- **Appendix F (Digital Circuits and Automata used in Experiments)**
    1. We have expanded this section to highlight the applicability of our optimization techniques to arbitrary Boolean network domains.
    2. In particular, we added a Boolean network construction for deterministic finite automata, as well as the specifications for two automata we present extended experimental results on.
- **Appendix G (Extended Results)**
    1. In Section G.2, we present new results on optimizing NN representations of BNs that encode deterministic finite automata. We summarize our findings in the text.
- **Appendix I (Broader Impacts)**
    1. We have extended this section to include an example application scenario for a neurosymbolic AI system that could utilize a homogeneous computing architecture. We explain the significance of the proposed optimization methods for such a system.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes a new and interesting method for optimizing neural network representations of Boolean networks. 

Strengths: 

1. The paper identifies a unique gap in existing network compression methods,  and proposes a lossless technique for optimizing a two-layer NN representation of a Boolean function. The introduction of NPN to exploit shared representations is particularly interesting. 

2. The paper is theoretically solid. Moreover, it provided extensive experimental evaluations. 

3. The paper is well-written. It is clear, well-structured.  

Weaknesses:

One weakness is about the generalization. The proposed techniques focus on two-layer NNs. Extending the discussion to multi-layer NNs or other types of Boolean networks, such as biological or regulatory networks, would strengthen the claims of general applicability. 

Overall, this submission is technically sound, addresses a significant problem, and demonstrates very good experimental results. I would like to recommend acceptance.