Research map / Graph learning / Graph self-supervised learning
Functional Matching of Logic Subgraphs: Beyond Structural Isomorphism
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces functional subgraph matching for logic circuits, detecting whether a query logic function is implicitly contained in a circuit across AIG and post-mapping netlists, plus fuzzy boundary identification via graph segmentation.
Problem
Subgraph matching in logic circuits relies on structural isomorphism, which fails to find function-related subgraphs once synthesis and technology mapping change circuit topology.
Approach
Defines functional subgraphs (containment up to functional equivalence) and uses a two-stage multi-modal framework: DeepGate2 (AIG) and DeepCell (post-mapping) encoders aligned with intra- and inter-modal InfoNCE losses for detection, then a fine-tuned node-segmentation head to localize fuzzy boundaries.
Key results
- Functional subgraph detection reaches about 95.3% accuracy on ITC99 (G_sub to G_syn) and 93.1% on G_sub to G_pm, while structural baselines sit near 50%.
- Fuzzy boundary identification achieves an average DICE of 91.3% and IoU of 84.0% across the three datasets, versus at most about 61% DICE for baselines.
- Ablation shows removing segmentation drops ITC99 DICE from 90.7% to 45.7%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use functional subgraph matching instead of structural matching | Functional subgraph detection · ITC99, OpenABCD, and ForgeEDA: Gsub → Gsyn and Gsub → Gpm | accuracy | Helped |
| Use graph segmentation for fuzzy boundary identification | Fuzzy boundary identification · ITC99, OpenABCD, and ForgeEDA | DICE | Helped |
| Add intra-modal and inter-modal alignment (ablation) | Stage #1 functional subgraph detection · ITC99: Gsub → Gsyn | accuracy: 94.6 -> 95.3 | Helped |
| Add intra-modal and inter-modal alignment (ablation) | Stage #1 functional subgraph detection · ITC99: Gsub → Gpm | accuracy: 91.4 -> 93.1 | Helped |
| Add Stage #1 pretraining (ablation) | Stage #2 fuzzy boundary identification · ITC99: Gsub → Gpm | IoU: 76.3 -> 83.0 | Helped |
| Add Stage #1 pretraining (ablation) | Stage #2 fuzzy boundary identification · ITC99: Gsub → Gpm | DICE: 86.5 -> 90.7 | Helped |
| Use graph segmentation instead of input-output node prediction (ablation) | Stage #2 fuzzy boundary identification · ITC99: Gsub → Gpm | IoU: 29.6 -> 83.0 | Helped |
| Use graph segmentation instead of input-output node prediction (ablation) | Stage #2 fuzzy boundary identification · ITC99: Gsub → Gpm | DICE: 45.7 -> 90.7 | Helped |
| Use the method on medium-sized circuits rather than the reported small-circuit setting | Functional subgraph detection · ForgeEDA medium-sized circuits: Gsub → Gsyn | F1-score: 95.3% to 81.2% | Hurt |
| Use Ours+Gamora or Ours+ABGNN instead of Ours | Stage #1 functional subgraph detection · ITC99, OpenABCD, and ForgeEDA | accuracy | Hurt |
| Use Ours+ABGNN instead of Ours | Fuzzy boundary identification · ForgeEDA | DICE: 91.2 -> 93.8 | Helped |
Surprising findings
- Structure-based baselines (NeuroMatch, HGCN) predict nearly all pairs as one class, yielding near-random accuracy.
- VF3 achieves 100% precision but only 0.32% recall on functional subgraph detection because functional transformations remove the explicit structure.
Limitations
- Performance drops substantially on medium-sized circuits (F1 about 81% on G_sub to G_syn and 78% on G_sub to G_pm).
- Assumes single-output circuits and a single minimal fuzzy boundary per query.
- Assumes removing nodes always changes the function (non-trivial function assumption).
Experimental setup
Datasets: ITC99 OpenABCD ForgeEDA
Benchmarks: ITC99 OpenABCD ForgeEDA
Metrics: accuracy precision recall F1-score IoU DICE
Baselines: NeuroMatch HGCN Gamora ABGNN VF3
Builds on: NeuroMatch DeepGate2 DeepCell InfoNCE
Closest papers by meaning
- A Circuit Domain Generalization Framework for Efficient Logic Synthesis in Chip Design (ICML 2024 · similarity 0.85)
- CircuitFusion: Multimodal Circuit Representation Learning for Agile Chip Design (ICLR 2025 · similarity 0.85)
- Circuit Representation Learning with Masked Gate Modeling and Verilog-AIG Alignment (ICLR 2025 · similarity 0.85)
- CircuitSense: A Hierarchical Circuit System Benchmark Bridging Visual Comprehension and Symbolic Reasoning in Engineering Design Process (ICLR 2026 · similarity 0.84)
- AnalogToBi: Device-Level Analog Circuit Topology Generation via Bipartite Graph and Grammar Guided Decoding (NeurIPS 2026 · similarity 0.84)
- Rethinking Circuit Completeness in Language Models: AND, OR, and ADDER Gates (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.