ShareGate: Learning to Match Functional Subgraph With Shared Logic

Functional subgraph matching identifies circuit regions that implement the same Boolean functions as query patterns, supporting datapath optimization, arithmetic verification, and hardware Trojan analysis. Logic synthesis creates shared intermediate expressions, so functional regions overlap and gates serve multiple operations. This shared logic interferes with learned recognition: neighborhood aggregation mixes operation cues at shared gates, leaving gate classes ambiguous. To address this, we propose ShareGate, a framework that recovers and certifies arithmetic cores in post-synthesis netlists with shared logic. Within ShareGate, a graph neural network proposes a candidate region for each gate from per-gate descriptors. Verification-driven refinement accepts a region only when its simulated response reproduces a fixed reference model on every pattern in the budget. A scheduler orders the checks. Thus, a class label changes only through a passing functional test, and the accepted region carries that test as a certificate. We formalize the task as functional subgraph matching with shared logic. Each gate is assigned one of five classes (adder, multiplier, subtractor, comparator, and control), so arithmetic regions are labeled together with their embedded comparison and control logic. Experiments on 21 netlists with embedded arithmetic cores from EPFL, ISCAS-85, and ITC-99 show that ShareGate recovers and certifies all three arithmetic cores in every case at all four injection levels, reaching certified results 6.0 to 34.5 times faster than the fastest baseline. As a diagnostic of the recognition stage, the gate-level field reaches 92.3% accuracy at the deepest level, versus 76.8% for the strongest baseline.