A GNN screener that narrows the search space for an exact subgraph matcher, plus a measurement of whether that actually helps. On ISCAS-scale netlists, it doesn't.
This is a reproduction and stress-test of Seo et al., Target Circuit Matching in Large-Scale Netlists Using GNN-Based Region Prediction (arXiv:2507.19518). The idea: train a graph neural network to predict where a target logic gate lives in a transistor-level netlist, then run exact subgraph isomorphism (VF3) only on the flagged regions.
The pipeline runs end to end. Output is sound — VF3 confirms every candidate, so nothing false gets emitted — though completeness depends on the screener, which is empirical, not proven. Recall came out at 100% on the cases I measured.
The more interesting half of this repo is the benchmarking. I set out to show that learned pruning beats a fast exact matcher, and it doesn't, at least not at this scale. The numbers and the commands that produce them are below.
A transistor-level SPICE netlist is a flat sea of MOSFETs and wires. Gate extraction recovers the logic design from it: figuring out that these twelve transistors are an AOI33D0BWP, those four are an inverter, and so on until every transistor is accounted for.
That's subgraph isomorphism — for each cell in a standard cell library, find every occurrence of its transistor topology in the circuit graph. NP-complete in general, and the graphs aren't small: S38417, the largest benchmark here, has 30,656 transistors.
The classical answer is an exact matcher like VF3. The proposed improvement is to put a learned screener in front of it. Less ground to cover, less time spent. This repo implements both and checks.
inference.py (exact extraction) |
find_gate.py (targeted search) |
|
|---|---|---|
| Question | Find every gate in the netlist | Find every instance of one gate |
| Method | VF3 matches the whole library at once; GNN annotates each hit with a confidence score | GNN screens every transistor neighbourhood against one target; VF3 confirms the flagged regions |
| Output | Complete gate-level netlist | Verilog listing of that gate's instances |
| Correctness | 100% coverage, clean partition | 100% recall and precision on the target |
Time on S38417 |
0.62 s | ~7.8 s (GPU) for one gate |
Both are correct. Which one is faster, and against what baseline, is the subject of the investigation section.
pip install -r requirements.txt # torch, torch-geometric, networkx, PyYAML, ...
chmod +x vf3_cpp/build/prog # the VF3 binary needs the execute bitA CUDA GPU is optional but strongly recommended for find_gate.py.
python src/find_gate.py \
--circuit S38417 \
--gate XNR4D0BWP \
--device cuda \
--gpu-extract \
--baseline============================================================
S38417 · find all 'XNR4D0BWP' · threshold 0.5 · cuda
============================================================
Search space : 983/30656 transistors kept (3.2% of chip)
GNN seeds : 288 regions flagged (K=4)
Instances : 2 found -> S38417_XNR4D0BWP.v
--------------------------------------------------------
GNN screen (cuda) : 7.7842 s
breakdown: reachability 0.42s edges_encode 6.81s seed_expand 0.33s
VF3 confirm (carved sub-circuit) : 0.0041 s
Total : 7.7883 s
--------------------------------------------------------
Recall (vs full VF3) : 2/2 (100%)
Precision : 2/2 (100%)
--------------------------------------------------------
Baseline: plain VF3 for 'XNR4D0BWP' over whole chip : 9.0737 s
Speedup vs baseline : 1.2x
============================================================
Result lands in outputs/S38417_XNR4D0BWP.v:
// XNR4D0BWP instances found in S38417
// 2 instance(s)
// MATCH XNR4D0BWP M28478 M28461 M28460 M28459 ... M28477
// MATCH XNR4D0BWP M28568 M28551 M28550 M28549 ... M28567To see what gates a circuit contains, rarest first — rare gates prune best:
grep "// MATCH" data/vf3_out/S38417.v | awk '{print $3}' | sort | uniq -c | sort -n | headpython src/inference.py --circuit C432 # -> outputs/C432.v| Flag | Meaning |
|---|---|
--gate G |
Target cell type (required) |
--threshold τ |
Screener keep-threshold, default 0.5. Lower means more recall and a larger search space |
--device {auto,cuda,cpu} |
Where the model runs |
--gpu-extract |
Region extraction as sparse-tensor ops on the GPU. Recommended; see the engineering section |
--workers N |
CPU processes for extraction, used only without --gpu-extract |
--baseline |
Also time plain VF3 for this gate over the whole chip and print the head-to-head |
├── src/
│ ├── parser.py SPICE (.sp) → heterogeneous graph JSON
│ ├── extractor.py VF3 ground truth + K-hop dataset construction
│ ├── model.py CircuitFilterGNN — target-conditioned R-GCN
│ ├── data_loader.py Dataset / splits
│ ├── train.py Training loop (early stopping, LR plateau)
│ ├── inference.py Full extraction: VF3 finds all gates, GNN annotates
│ ├── inference_prune.py Whole-library screening (used for the Wall 1 measurement)
│ └── find_gate.py Targeted search: GNN screens, VF3 confirms
├── vf3_cpp/ VF3 exact matcher (parallel C++) + cell libraries
├── data/
│ ├── raw/ 28 ISCAS-85/89 SPICE netlists (C17 … S38417)
│ ├── parsed/ Cached graph JSON
│ └── vf3_out/ Ground-truth gate-level Verilog from full-library VF3
├── checkpoints/ Trained model (best_model.pt)
├── configs/config.yaml Hyperparameters
└── outputs/ Generated Verilog
Netlist to graph (parser.py). A SPICE netlist becomes a heterogeneous directed graph. Nodes are transistors and nets, typed one-hot over VDD, GND, signal, PMOS, NMOS. Edges encode which terminal connects to which net — gate, source, drain — so the graph carries the electrical role of each connection rather than bare adjacency. Signal nets also get reverse edges. 22 relation types total. This typed encoding is what lets the model separate an AOI from an OAI with identical transistor counts.
Ground truth (extractor.py). VF3 runs with the full cell library and produces the true gate-level netlist per circuit, cached in data/vf3_out/. Each match names the transistors constituting each gate; those become positive training regions.
Training data. For each positive instance, the K-hop neighbourhood around one of its transistors is extracted, with K chosen per gate from its own radius. Four negative types:
| Negative | What it teaches |
|---|---|
random |
Arbitrary regions aren't gates |
partial |
Part of a gate is not the gate |
mutation |
A gate with a perturbed edge is not the gate |
others |
A different gate type is not this gate |
partial and others are the ones that matter. They force the model to tell a real AOI22 from a fragment of an AOI32.
The model (model.py). CircuitFilterGNN, a target-conditioned R-GCN: 2 layers, 128 hidden channels, 22 relations, 8 bases (basis decomposition keeps the parameter count manageable across relations), 221,409 parameters. The candidate region and the target gate go through the same encoder; the two embeddings are concatenated and scored by an MLP to give P(region contains target gate).
Conditioning on the target is the design choice that matters. One model handles any gate in the library, including gates it was never trained to output, because the gate's topology is an input rather than a class label.
Inference, two modes. inference.py runs VF3 over the full library and has the GNN attach a confidence p_hat to each hit. The GNN is an annotator here; remove it and the gates are the same.
find_gate.py is the actual contribution:
circuit + one target gate
│
┌─────────▼──────────┐
│ 1. GNN SCREEN │ score the K-hop region around every transistor
│ (GPU) │ keep those scoring ≥ τ → "seeds"
└─────────┬──────────┘
┌─────────▼──────────┐
│ 2. EXPAND & CARVE │ grow each seed to its whole cell (through signal
│ │ nets, not power rails); emit a reduced .sp
└─────────┬──────────┘
┌─────────▼──────────┐
│ 3. VF3 CONFIRM │ exact match, single-cell library, on the carved
│ │ sub-circuit only
└─────────┬──────────┘
▼
Verilog + metrics
The screener can be wrong in one direction only. Anything it flags spuriously gets rejected by VF3; anything it misses is gone. The GNN buys speed and can cost recall, never precision.
Short version: not here. Getting to that answer took dismantling the hypothesis three times.
Setup for everything below: S38417 (30,656 transistors, 4,805 gates, ~55 cell types) and C432 (532 transistors, 91 gates). Exact-matcher numbers come from the VF3 binary in this repo, run on a laptop CPU under WSL. GNN screen times are from an RTX 4050 Laptop GPU. Single runs, not averaged.
Full-library VF3 over the whole chip:
./vf3_cpp/build/prog -l vf3_cpp/examples/lib/libs38417.sp -s data/raw/S38417.sp -o /tmp/full.v
grep -E "Runtime|Instances|Coverage" /tmp/full.v// Runtime: 0.624 s
// Instances: 4805
// Coverage: 30656/30656 (100.00%)
0.62 seconds for the entire chip at 100% coverage. VF3 is fast because it matches the whole library together, using tiered deletion: large gates are found first and their transistors deleted, so the graph shrinks before the smaller gates are searched.
That mechanism explains everything that follows.
The obvious design is to screen for any gate and hand the flagged regions to VF3. It fails immediately, and the coverage line above says why: 100% of transistors already belong to some gate. Ask "where are the gates" and the answer is "everywhere." Measured on C432, whole-library screening keeps 532/532 transistors. Zero pruned.
A screener only saves work when there's something to throw away.
If "where is any gate" is unprunable, narrow the question to "where is this specific gate." Most of a chip genuinely isn't any particular rare gate, and that's real empty space. It's also the task the source paper addresses — target circuit matching — so the pivot is back toward the paper, not away from it.
But splitting a library-wide problem into per-gate problems has two costs that need measuring before claiming anything.
Measured with VF3 alone, no ML involved, so the model can't be blamed. Full library once, versus each of the 27 cell types separately with the results unioned, on C432:
| Gates found | Precision | Transistor claims | |
|---|---|---|---|
| Full library, together | 91 | 100% | 532 / 532 = 1.00× (clean partition) |
| Gate-by-gate, combined | 140 | 65% | 780 / 532 = 1.47× (overlaps) |
A phantom AN4D0BWP claims transistors m295, m296 that belong to a CKND0BWP inverter. A phantom AOI22D0BWP claims eight transistors of a real AOI32D0BWP.
The cause is that a piece of a large gate can look exactly like a small gate. VF3 prevents this by deleting transistors as it matches them. Split the library and the safeguard is gone; what comes out isn't a valid netlist but a set of overlapping, contradictory claims.
This also answers the obvious question of why I don't just run the GNN across every gate and compare to full VF3. The gate-by-gate answer is wrong before speed is even on the table.
Tiered deletion is also where VF3's speed comes from. Remove it — run one cell type against the full chip — and matching falls apart. On S38417:
| Single-cell VF3 run | Time |
|---|---|
one inverter (CKND0BWP) |
105.7 s |
one AOI211D0BWP |
22.7 s |
one XNR4D0BWP |
20.3 s |
one NR2D0BWP |
12.6 s |
Extrapolating the mean of those four across ~55 cell types gives roughly 2,000 s, about 35 minutes, against 0.62 s for the same library run together. Call it a 3,000× penalty for splitting the work. The extrapolation is from four samples and the per-cell spread is wide, so treat the exact figure loosely; the order of magnitude is not in doubt.
So the comparison I originally wanted — screener over all gates versus full VF3 — is dead twice over. The result would be incorrect (Wall 2) and the baseline it needs to beat is thousands of times faster (Wall 3).
Restrict the claim to what the method is for — one rare gate in a large netlist — and it delivers. A single gate can't double-claim against itself, so correctness holds.
S38417, target XNR4D0BWP, 2 instances among 30,656 transistors:
| Metric | Result |
|---|---|
| Search space kept | 983 / 30,656 = 3.2% |
| Recall | 2/2 = 100% |
| Precision | 2/2 = 100% |
| VF3 confirm on carved circuit | 0.004 s, down from ~20 s |
| GNN screen (RTX 4050) | 7.8 s |
| Total | 7.8 s vs single-cell VF3 9.1 s, so 1.2× faster |
The pruning mechanism works. The screener narrows a 30k-transistor hunt to 3% of the chip, loses nothing, and the exact confirm becomes free.
1.2× is a win over the wrong opponent.
That 9.1 s baseline is single-cell VF3, the crippled configuration from Wall 3. Nobody would run it. What a real user runs is full-library VF3: 0.62 s for every gate in the chip, from which the XNR4 instances are a grep away.
| Approach | Time | What you get |
|---|---|---|
| Full-library VF3, then filter | 0.62 s | Every gate, including all XNR4s |
| GNN screen + VF3 confirm | 7.8 s | Only the XNR4s |
| Single-cell VF3 (the flattering baseline) | 9.1 s | Only the XNR4s |
Full VF3 is ~12× faster than this method and returns strictly more information. A hierarchical matcher is reported faster still, ~0.024 s, though I didn't reproduce that number myself.
The root cause is that the screener has a fixed cost. It has to look at the whole chip once no matter what the target is. On these netlists that fixed cost — 8 s, or maybe 2 s with the optimisation noted below — is larger than the entire matching problem it's trying to accelerate. Paying 8 s to skip 0.6 s of work is not a trade that can be tuned into a win.
Learned pruning can only pay off when the exact matcher is itself the bottleneck: when matching takes seconds to minutes, so that skipping 97% of it saves more than the screener costs. On ISCAS-scale netlists that regime doesn't exist. Exact matching is too fast to be worth accelerating.
That's a negative result. It's here in the middle of the README rather than in a footnote because it's what the evidence supports.
Most of the work went into getting the screener from unusable to merely uncompetitive, and the profiling is the part I'd want to read in someone else's repo.
The screen builds and encodes a K-hop region around every one of 30,656 transistors. The naive version calls PyTorch Geometric's k_hop_subgraph once per transistor:
| Implementation | Screen time (S38417) | Why |
|---|---|---|
k_hop_subgraph per transistor, threaded |
275 s (CPU) / 48–62 s | Each call rescans all 195k edges to return a ~21-node neighbourhood. 30k full-graph scans |
| Neighbour-list BFS, tensors per region | 62 s | Graph walk fixed; 30k separate torch.tensor() constructions now dominate |
| Pure-Python BFS, tensors batched per chunk | 80 s (bfs_logic 49 s) |
Tensor cost gone; the Python graph walk is now the wall, and the GPU sits idle |
| Multiprocess BFS across CPU cores | sub-linear gain | VF3 is parallel C++. Racing it on the CPU is a losing game |
Sparse-tensor extraction on GPU (--gpu-extract) |
7.8 s | No Python graph walk at all |
The final version drops CPU traversal entirely:
- Reachability via sparse matrix powers. Build adjacency
Aas a sparse tensor plus a sparse[N × C]indicator of the C candidate centres. Multiply K times withtorch.sparse.mm(A, reach); the non-zeros of the result are the K-hop neighbourhoods of every centre, computed simultaneously on the GPU. 0.42 s for all 30,656 regions. - Induced edges via vectorised gather +
searchsorted. For every node in every region, gather out-edges through a CSR-style pointer, then keep only those whose target lies in the same region — a binary search over sorted(region, node)keys. No loops. - Chunking around the power rails.
VDDandGNDappear in nearly every region and have out-degree ≈25,000. Expanding their edges globally before filtering allocates 12.4 GB and OOMs. Chunking edge construction by region bounds the intermediate.
Each rewrite was verified bit-exact against the reference k_hop_subgraph implementation: max absolute difference 0.00e+00 across all embeddings at K = 2, 3, 4. No speed was bought with silent approximation.
One inefficiency remains. Because the power rails touch nearly everything, edges_encode still generates and discards a lot of candidate edges. Special-casing VDD/GND — intersecting them against each small region instead of expanding their 25k edges — should bring the screen to roughly 2 s. Not implemented.
| Architecture | Target-conditioned R-GCN, 2 layers, 128 hidden, 22 relations, 8 bases |
| Parameters | 221,409 |
| Training set | 25 circuits, 94 gate types → 11,107 positives + 27,832 negatives (38,939 regions) |
| Optimiser | Adam, lr 1e-3, weight decay 1e-4, grad-clip 1.0 |
| Schedule | ReduceLROnPlateau on val-F1, early stopping (patience 60) |
| Best checkpoint | epoch 285 |
Validation at the selected checkpoint: recall 0.955, precision 0.677, F1 0.792, accuracy 0.855.
Recall is the metric that matters and it's deliberately optimised for. A missed region is a gate lost permanently, because VF3 never looks there. False positives only cost a little confirm time and get eliminated downstream. With VF3 as backstop, 0.955 recall is the right operating point, and it's why end-to-end recall on the targeted-search task comes out at 100%.
The precision of 0.677 reflects the hard negatives: separating a real gate from a fragment of a larger gate, or from a structurally similar different gate, across 94 cell types. It isn't comparable to the source paper's numbers, which use easier randomly-sampled negatives.
chmod +x vf3_cpp/build/prog
# The bar: full-library VF3, whole chip (0.62 s, 4805 gates, 100% coverage)
./vf3_cpp/build/prog -l vf3_cpp/examples/lib/libs38417.sp -s data/raw/S38417.sp -o /tmp/full.v
grep -E "Runtime|Instances|Coverage" /tmp/full.v
# Wall 1: whole-library screening prunes nothing
python src/inference_prune.py --circuit C432 --threshold 0.7 # keeps 532/532
# Wall 2: gate-by-gate double-counts (VF3 alone, no ML)
# full library -> 91 gates, 1.00x claims
# gate-by-gate -> 140 gates, 65% precision, 1.47x claims
# Wall 3: single-cell VF3 is slow (build a one-cell library, run it on the full chip)
# What works: single rare-gate targeted search
python src/find_gate.py --circuit S38417 --gate XNR4D0BWP --device cuda --gpu-extract --baseline
# Full extraction (the practical path)
python src/inference.py --circuit S38417Provenance: exact-matcher timings (0.62 s full-library, 12.6–105.7 s single-cell, the 91-vs-140 double-counting result) were measured with the VF3 binary in this repo. GNN screen timings (7.8 s, 3.2% pruning, 100% recall and precision) come from an RTX 4050 Laptop GPU. The hierarchical-matcher figure of 0.024 s is quoted from a collaborator's benchmark table and was not independently reproduced. All timings are single runs; I haven't characterised variance.
- The method does not beat full-library VF3 at this scale. That's the headline finding.
- Timings are hardware-dependent and unrepeated. Screen on a laptop GPU, matcher on a laptop CPU under WSL, one run each. Absolute numbers will move. The ratio — screener fixed cost far exceeding total matching cost — is structural, not an artefact of the hardware.
- Only rare targets prune well. Common gates prune poorly. Inverters, at 4,585 instances, retain 75% of the chip and suffer low single-cell precision (47%), because a simple pattern occurs inside many larger gates.
- The GNN alone is a ~0.68-precision predictor. Exactness of the output depends entirely on VF3 confirming every candidate. That's by design, but it shouldn't be read as the GNN being accurate on its own.
.voutput is a match list, not fully elaborated structural Verilog with pin-to-net bindings.- Untested above 30k transistors. Every conclusion is scoped to ISCAS-85/89 — which means the regime where this method could plausibly win is exactly the one not yet measured.
- The 100% end-to-end recall is empirical. VF3 guarantees no false positives. Nothing guarantees the screener didn't miss a region on a circuit I haven't run.
The decisive experiment is whether the crossover exists at all. Learned pruning only wins when exact matching is slow, and exact matching is only slow on much larger designs. So:
- Scale up to hundreds of thousands or millions of gates: the large EPFL benchmarks (
multiplier,divisor,hypotenuse, ~214k AND-nodes), ITC'99 (b18,b19), or an industrial netlist. These ship as gate-level Verilog/BLIF and would need technology mapping and expansion to transistor level first. - Benchmark against the strongest available matchers, full-library VF3 and the hierarchical matcher, across many target gates and with repeated runs.
- Characterise the crossover. At what netlist size, and for what target rarity, does the screener's fixed cost become worth paying? That curve is the actual scientific contribution, and it may well show the crossover is unreachable — which would be just as useful an answer.
Smaller items: the VDD/GND special case (8 s → ~2 s), fully structural Verilog with pin bindings, and a sweep of the keep-threshold τ to trace the recall/pruning trade-off.
Method reproduced: Seo, Seo, Lee, Kim, Shin, Sung, Park. Target Circuit Matching in Large-Scale Netlists Using GNN-Based Region Prediction. arXiv:2507.19518, 2025.
Exact matcher: Carletti, Foggia, Saggese, Vento. Introducing VF3: A New Algorithm for Subgraph Isomorphism. GbRPR 2017. Parallel C++ implementation vendored in vf3_cpp/.
Benchmarks: ISCAS-85 and ISCAS-89 circuits.
MIT License. © 2026 usuallyarnav.