Boolean-aware Boolean Circuit Classification: A Comprehensive Study on Graph Neural Network
Boolean circuit is a computational graph that consists of the dynamic directed graph structure and static functionality. The commonly used logic optimization and Boolean matching-based transformation can change the behavior of the Boolean circuit for its graph structure and functionality in logic synthesis. The graph structure-based Boolean circuit classification can be grouped into the graph classification task, however, the functionality-based Boolean circuit classification remains an open problem for further research. In this paper, we first define the proposed matching-equivalent class based on its ``Boolean-aware'' property. The Boolean circuits in the proposed class can be transformed into each other. Then, we present a commonly study framework based on graph neural network~(GNN) to analyze the key factors that can affect the Boolean-aware Boolean circuit classification. The empirical experiment results verify the proposed analysis, and it also shows the direction and opportunity to improve the proposed problem. The code and dataset will be released after acceptance.
Code (0)
등록된 구현이 없습니다.
Tasks
ClassificationGraph ClassificationGraph Neural NetworkSimilar Papers 제목 키워드 기반
The Tractability of SHAP-Score-Based Explanations over Deterministic and Decomposable Boolean Circuits
Scores based on Shapley values are widely used for providing explanations to classification results over machine learning models. A prime example of this is the influential SHAP-score, a version of the Shapley value that…
A Circuit Complexity Formulation of Algorithmic Information Theory
Inspired by Solomonoffs theory of inductive inference, we propose a prior based on circuit complexity. There are several advantages to this approach. First, it relies on a complexity measure that does not depend on the c…
Binary ClassificationInductive BiasCertifiable Boolean Reasoning Is Universal
The proliferation of agentic systems has thrust the reasoning capabilities of AI into the forefront of contemporary machine learning. While it is known that there \emph{exist} neural networks which can reason through any…
A Boolean Function-Theoretic Framework for Expressivity in GNNs with Applications to Fair Graph Mining
We propose a novel expressivity framework for Graph Neural Networks (GNNs) grounded in Boolean function theory, enabling a fine-grained analysis of their ability to capture complex subpopulation structures. We introduce …
Sampling and Learning for Boolean Function
In this article, we continue our study on universal learning machine by introducing new tools. We first discuss boolean function and boolean circuit, and we establish one set of tools, namely, fitting extremum and proper…