Two Boolean functions are considered NPN equivalent if one can be transformed into the other by negating inputs, permuting inputs, or negating the output. Efficient NPN classification is valuable in fields such as logic synthesis, quantum computing, and information theory. However, exact NPN classification demands exhaustive enumeration of all possible input permutations and negations. Its complexity grows exponentially, making it impractical for larger functions with more inputs. In this paper, we introduce the first learning-based formulation for NPN classification by recasting it as NPN action prediction. Our method represents Boolean functions as AND-Inverter Graphs (AIGs) and applies a bidirectional heterogeneous graph neural network to predict input negations, output negation, and input permutations. To mitigate the non-canonicity of logic networks, we further introduce graph rewriting techniques that reduce structural ambiguity and recover useful symmetries before prediction. Experimental results show that NPN action prediction is learnable, that the resulting canonicalization quality improves over heuristic baselines, and that on practical benchmarks our method approaches exact methods on tractable cases while scaling to functions with up to 16 inputs.
Figures & tables
Figure 1. Overview of the proposed GNN-NPN Workflow. At its core, our approach employs an NPN action predictor (introduced in Section 4 ) that takes AIG as input and produces an NPN action. We demonstrate in Section 3 that this model can be utilized to perform NPN canonicalization for a given function and consequently, perform NPN classification. Additionally, we propose graph rewriting algorithms (detailed in Section 5 ) to enhance the symmetry in AIG representations.
Figure 2. Structural ambiguity (a, b) and resolution (c) via node merging.
p %
q %
π % (Pairwise)
π % (Exact)
r
f^direct %
f^Flip−swap %
f^Sifting %
Training Algorithm
Supervised
87.7%
96.9%
71.07%
4.20%
0.2232
22.30%
60.78%
74.66%
GRPO
77.69%
95.62%
72.12%
5.70%
0.2290
19.59%
60.78%
76.49%
GRPO + Rewriting
77.47%
95.83%
72.31%
5.71%
0.2773
20.95%
60.78%
79.70%
GNN Architecture Ablations
Uni-directional
47.63%
68.28%
50.39%
0.12%
0.1962
0.12%
47.50%
63.78%
Table 1. Evaluation of NPN action prediction for different training algorithms and GNN architecture variants. The columns from left to right are: the accuracy of prediction for input negation p , output negation q , input permutation π (pairwise and exact), reward (defined in Equation 16 ) achieved by the predicted action, and the ratio of canonical representative f^ achieved directly and with flip-swap and sifting post-processing, respectively. The architecture ablations use GRPO with graph rewriting.
Figure 3. Comparison of canonicalization gaps using different post-processing, temperature τ , and number of trials.
Method
Note
6-bit
8-bit
10-bit
12-bit
14-bit
16-bit
None
Number of functions
403672
370269
360215
354395
339435
334501
kitty ( Soeken et al., 2018 )
Flip-swap ( Huang et al., 2013 )
2028
10507
20950
31717
40537
46774
Sifting ( Huang et al., 2013 )
1828
10301
20573
31088
39578
45344
ABC testnpn ( Brayton and Mishchenko, 2010 )
-A 0 (uniquify)
12847
30099
39942
55349
63054
66993
-A 1 (exact)
1253
7829
timeout
timeout
timeout
timeout
-A 2
2151
10640
21849
36470
45594
50070
Table 2. Performance of NPN classification, quantified by number of NPN equivalent classes reduced from subcircuits of the EPFL Combinatorial Benchmark Suite ( Amarú et al., 2015 ) , the smaller the better. The timeout is 10 hours. The best results are in bold.
We propose a new algorithm for compiling Bayesian network classifier (BNC) into class formulas. Class formulas are logical formulas that represent a classifier's input-output behavior, and are crucial in the recent line of work that uses logical reasoning to explain the decisions made by classifiers. Compared to prior work on compiling class formulas of BNCs, our proposed algorithm is not restricted to binary classifiers, shows significant improvement in compilation time, and outputs class formulas as negation normal form (NNF) circuits that are OR-decomposable, which is an important property when computing explanations of classifiers.
Yaofang Zhang, Adnan Darwiche
Department of Computer Science University of California, Los Angeles
Traditional neural networks have an impressive classification performance, but what they learn cannot be inspected, verified or extracted. Neural Logic Networks on the other hand have an interpretable structure that enables them to learn a logical mechanism relating the inputs and outputs with AND and OR operations. We generalize these networks with NOT operations and biases that take into account unobserved data and develop a rigorous logical and probabilistic modeling in terms of concept combinations to motivate their use. We also propose a novel factorized IF-THEN rule structure for the model as well as a modified learning algorithm. Our method improves the state-of-the-art in Boolean networks discovery and is able to learn relevant, interpretable rules in tabular classification, notably on examples from the medical and industrial fields where interpretability has tangible value.
Vincent Perreault, Katsumi Inoue, Richard Labib +1
Department of Mathematics and Industrial Engineering Polytechnique Montréal · National Institute of Informatics, Tokyo
Graph learning on neuromorphic substrates requires an explicit spiking realization of neighborhood aggregation, supporting control and classification. We propose DeNA-SGN, which combines fixed OR and tie-inclusive Majority aggregation of binary node features with a learned signed-weight threshold classifier. A degree-dependent inhibitory construction implements Majority through shared control neurons, enabling a complete circuit compilation into SuperNeuroMAT. Across seven datasets and 41 mapped classifiers, native simulation matches the exported ANN on every evaluated class decision and output-spike pattern. On the new confirmatory Amazon Photo dataset, DeNA-SGN achieves 83.93+-0.93% current-readout accuracy and 71.61+-2.22% strict output-spike accuracy; Wiki-CS reaches 75.99+-0.54% over 20 public masks. In the matched Cora study, we achieve 74.90+-2.67% on current-readout and 68.57+-2.94% strict spike accuracy. Complete circuit and activity accounting supports analytical energy comparisons and identifies the cost of clocking inactive neurons in large deployments. Current argmax is decoded on the host, and energy is modeled rather than measured on hardware. These findings establish a reproducible route to useful graph classification with decision-matched spiking execution and explicit implementation costs.
Sanjay Das, Xi Zhang, Emily Herron +1
The authors are with Oak Ridge National Laboratory, Oak Ridge, TN, USA.