Graph Neural Networks Learn to Group Related Logic Functions

Two digital circuits can look different while implementing Boolean functions related by simple changes to their inputs and output. Recognizing these relationships helps circuit-design tools reuse optimized logic. A new preprint explores whether a graph neural network can learn to find those transformations without exhaustively searching the possibilities.

Finding families of logic functions

Boolean functions map combinations of binary inputs to a binary output. Two functions are NPN-equivalent if one can become the other by negating inputs, permuting their order, or negating the output. Negation flips zero to one and one to zero.

This relationship matters in logic synthesis: instead of storing optimized implementations for every function separately, a tool can organize them into equivalence classes and reuse a representative implementation.

The search space grows rapidly. For an n-input function, there are 2^(n+1) × n! possible NPN transformations. Truth tables, which explicitly list outputs for every input combination, also grow exponentially. Exact methods can prune the search, but larger functions remain challenging.

Chengdi Cao, Hanyu Wang, Wan-Hsuan Lin and Jason Cong at UCLA propose GNN-NPN, a learning-based heuristic that predicts promising transformations from circuit graphs.

Predict transformations, not answers

The central design choice is to have the neural network predict an action rather than an equivalence label or a new function. Its outputs specify which inputs to negate, how to reorder them, and whether to negate the output.

Every such action stays within the original function’s NPN-equivalence class. A poor prediction may fail to reach the desired representative, but it cannot transform the function into a member of an unrelated class. That guarantee does not make canonicalization exact: equivalent functions can still end up with different representatives and remain unnecessarily separated.

The target representative is the function whose truth table has the smallest lexicographic value within its class—effectively, the smallest value under a fixed ordering of truth-table bits.

GNN-NPN represents circuits using AND-Inverter Graphs, built from AND operations and inversions. Its neural network passes information both forward and backward through the graph, using different parameters for different node types and propagation directions. Separate prediction heads handle input negation, output negation and input ordering.

Making different graphs easier to compare

A complication is that the same function can have different graph structures. For example, grouping a three-input AND operation in different ways produces different trees despite identical functionality.

The authors address this with graph rewriting. One procedure merges compatible chains of AND gates into larger nodes, exposing symmetries obscured by the original structure. Another replaces local circuit fragments with functionally equivalent alternatives chosen to reduce structural ambiguity and shorten propagation paths.

The main training approach uses reinforcement learning, rewarding transformations that reduce the truth table’s lexicographic value. After prediction, conventional flip-swap or sifting heuristics refine the result. Multiple candidate actions can be sampled from one network inference, although each candidate still requires subsequent processing.

What the experiments show

Training used randomly generated six-input circuit graphs. On a separate evaluation set of 1,000 random six-input functions, the reinforcement-trained model with rewriting reached the exact canonical representative directly in 20.95% of cases. Sifting post-processing raised that figure to 79.70%, illustrating how much the complete workflow relies on refinement.

For practical classification, the researchers extracted subcircuits with six to 16 inputs from 20 EPFL benchmark circuits. With 16 sampled actions and sifting, GNN-NPN matched the exact methods’ class counts at six and eight inputs. At 12 inputs, it produced 26,512 groups, compared with 26,495 for the exact method that finished. At 16 inputs, it produced 38,939 groups, fewer than the reported heuristic baselines; both exact methods exceeded the ten-hour timeout.

These are grouping results, not direct measurements of improved circuit quality. Runtime also remains consequential: the reported 16-input workload required about 2,130 seconds for model inference alone, the dominant processing stage, and approximately 9.3 GB of CPU memory.

Better matching is not yet better optimization

The authors’ initial attempt to exploit the improved matching for circuit replacement delivered limited gains, with results similar to sifting. They also explicitly note that generalization beyond EPFL-derived subcircuits has not been verified.

The demonstrated contribution is therefore a promising heuristic for finding related logic functions—not an exact classifier or a demonstrated breakthrough in end-to-end circuit optimization.