Functional Matching of Logic Subgraphs: Beyond Structural Isomorphism
Authors: Ziyang Zheng
Kezhi Li
Zhengyuan Shi
Qiang Xu
Venue: NeurIPS 2025 poster ()
Keywords: subgraph
circuit
function
Primary area: applications

Abstract: Subgraph matching in logic circuits is foundational for numerous Electronic Design Automation (EDA) applications, including datapath optimization, arithmetic verification, and hardware trojan detection. However, existing techniques rely primarily on structural graph isomorphism and thus fail to identify function-related subgraphs when synthesis transformations substantially alter circuit topology. To overcome this critical limitation, we introduce the concept of functional subgraph matching, a novel approach that identifies whether a given logic function is implicitly present within a larger circuit, irrespective of structural variations induced by synthesis or technology mapping. Specifically, we propose a two-stage multi-modal framework: (1) learning robust functional embeddings across AIG and post-mapping netlists for functional subgraph detection, and (2) identifying fuzzy boundaries using a graph segmentation approach. Evaluations on standard benchmarks (ITC99, OpenABCD, ForgeEDA) demonstrate significant performance improvements over existing structural methods, with average 93.8% accuracy in functional subgraph detection and a dice score of 91.3% in fuzzy boundary identification.

Functional Matching of Logic Subgraphs:
Beyond Structural Isomorphism
Ziyang Zheng Kezhi Li Zhengyuan Shi Qiang Xu
The Chinese University of Hong Kong
(zyzheng23,kzll kzli24, zyzshh21, qru)ecse......eee cuhk. edu.hk
Abstract
Subgraph matching in logic circuits is foundational for numerous Electronic Design Automation (EDA) applications, including datapath optimization, arithmetic verifi- cation, and hardware trojan detection. However, existing techniques rely primarily on structural graph isomorphism and thus fail to identify function-related subgraphs when synthesis transformations substantially alter circuit topology. To overcome this critical limitation, we introduce the concept of functional subgraph matching, novel approach that identifies whether a given logic function implicitly present within a larger circuit, irrespective of structural variations induced by synthesis or technology mapping. Specifically. we propose a two-stage multi-moda. frame- work: (1) learning robust functional embeddings across AIG and post-mapping netlists for functional subgraph detection, and (2) identifying fuzzy boundaries using graph segmentation approach. Evaluations standard benchmarks (ITC99, OpenABCD, ForgeEDA) demonstrate significant performance improvements over existing structural methods, with average 93.8% accuracy in functional subgraph detection and a dice score of 91.3% in fuzzy boundary identification. The source code and implementation details can be found at our repository
Introduction
Subgraph matching-identiffyinn smaller graphs within larger ones-is fundamental task in graph analysis, with pivotal applications spanning social network mining, bioinformatics, and Electronic Design Automation (EDA).
In the context of EDA, subgraph matching involves searching for specific eircuit patterns embedded within larger circuits. This capability directly supports critical tasks such as circuit optimization, verification, and security analyses. For example, verifying complex arithmetic eircuits like multipliers typically requires recognizing embedded small functional units (e.g., half-adders) within larger netlists, enabling algebraic simplifications and correctness proofs [ 22. Similarly, during template-based synthesis, accurately locating predefined subgraphs allows their replacement with highly optimized standard cells, thereby significantly improving power, performance, and area (PPA) metrics [3]. Moreover, subgraph matching also plays essential role in hardware security by enabling the identification of potentially malicious substructures or "hardware trojans"=anomalor"" anomalous subcircuits intentionally embedded to compromise system integrity [5.
Traditionally, subgraph matching in graphs formulated as a structural isomorphism problem: determining whether smaller query graph exactly matches part of larger target graph in terms of node and edge connectivity. This problem extensively studied in general graph theory, and classical approaches rely primarily combinatorial search algorithms [6 7 g). However, subgraph isomorphism is an NP-complete problem and thus often suffers from exponential computational complexity in worst-case scenarios. Recently, deep learning methods have emerged to mitigate this computational cost by embedding graphs into continuous latent spaces, significantly accelerating
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

matching tasks 10
Within the EDA domain, these techniques have been successfully adapted for transistor-level subcireuit identification [[2]
However, structure-based matching methods encounter significant limitations in practical EDA tasks, as circuit topologies frequently undergo substantial transformations during logic synthesis and technology mapping. Equivalent logic functions can thus be realized through widely differing structural implementations, driven by design considerations such as timing performance, power consumption, or silicon area. Consequently, exact structural correspondence rarely persists throughout the design process, even when the underlying logic function remains unchanged. This inherent limitation severely restricts the utility of traditional structural matching techniques, particularly in applications requiring cross-stage queries for example, identifying subgraphs from an abstract mapped netlist.
netlist (like an And-Inverter Graph, or AIG) within synthesized,
Motivated by this critical gap, we introduce approach explicitly designed recognize logic functionality irrespective of structural differences. Specifically, our framework determines whether the logic represented by query subgraph exists implicitly within a candidate graph, independent of structural transformations.
To formalize this, we propose two key concepts: (1) functional subgraph, representing the circuit logic containment relation independent of structure, and (2) fuzzy boundary, minimal graph regions encapsulating the query's logic despite unclear structural boundaries. Consequently, our methodology. termed functional subgraph matching, addresses two sub-tasks: 1. Functional Subgraph Detection: Determining whether the logic function of query graph is implicitly contained within candidate graph; 2. Fuzzy Boundary Identification: Precisely locating the smallest possible region (the fuzzy boundary) in the candidate graph that encapsulates the query's s logic.
To achieve these objectives, we propose a novel two-stage multi-modal framework. In the first stage, we train our model with intra-modal and inter-modal alignment across different graph modalities, enabling robust and cross-stage detection of functional subgraph. In the second stage, we fine-tune model and formulate fuzzy boundary detection as graph segmentation task, moving beyond prior approaches that treated boundary identification as an onput-output classification problem [13] [4]. By leveraging information from nodes located within the true boundaries, segmentation approach significantly enhances performance and continuity of fuzzy boundary prediction.
Our experiments demonstrate the effectiveness of the proposed framework. Evaluations conducted across several widely-used benchmarks, ITC99 [15]. OpenABCD (16) and ForgeEDA [17. show that our approach significantly surpasses traditional structure-based methods. Specifically, our framework achieves an average accuracy 93.8% for functional subgraph detection and attains DICE score of 91.3% for fuzzy boundary detection tasks. In contrast, structure-based baseline methods typically exhibit readomandom performance (accuracy close to 50%) and high variability in precision, recall, and Fl-score, underscoring their limitations in capturing implicit functionality. To further validate our method's robustness and generalizability, we additionally propose three function-awe -wwrre baseline variants by integrating different graph encoders into our framework.
In summary, the contributions of this work include:
Introducing and formally defining the novel concept of functional subgraph matching, clearly distinguishing it from structural isomorphism and functional equivalence.
Developing a two-stage multi-modal embedding framework, leveraging both intra-modal and inter-modal alignments to capture structure-agnostic and function-invarian graph repre- sentations. This allows effective functional subgraph detection across different modalities.
Proposing an innovative approach for fuzzy boundary identification by formulating the task as graph segmentation problem rather than simple input-output classification problem, significantly enhancing boundary continuity and localization accuracy.
2 Preliminaries
2.1 Subgraph Isomorphism Matching
Subgraph isomorphism matching is fundamental problem in graph theory with applications across bioinformatics (18), social network analysis [19) and knowledge graphs 20 21). We first recall the standard definition of subgraph isomorphism in Definition] I
2

---

input
outpur
and
not
adder
multiplier
b
output
outpuut
output
AND
AND
AND
AND
Query:
Candidate 1: (b c)xa
Candidate 2: axb axc
Figure 1: We present the query and candidate graphs. Above: 1-bit adder and multiplier. Below: AIG netlist. The query b is explicitly contained within the candidate (b + x a, making straightforward to identify the exact subgraph the candidate. In contrast, the query b+cis implicitly contained within the candidate a b a X c, which implies no subgraph of b X has the same structure or function as the query graph.
Definition 1 (Subgraph Isomorphism). A graph Q is isomorphic subgraph of G there exists subgraph g' of 9 such that Q is isomorphic to g'.
Then, based on the definition of subgraph isomorphism, the subgraph isomorphism matching task is defined follows: given query graph Q and target graph G. determine if Q is isomorphic to a subgraph of G. Classical approaches combinatorial search algorithms [7] g 6). Its NP-complete nature, however, makes exact matching computationally intensive. More recently, graph-neurdl netwookk- based (GNN-based) methods have been introduced to learn compact graph embeddings that accelerate the matching process ( 10 I In the EDA domain, Li et al. [12] adapt the NeuroMatch architecture 10 to solve subcircuit isomorphism transistor-level netlists.
subgraph isomorphism matching rely primarily on
However, in EDA flow, graphs often represent circuits or computations where structural modifications can preserve the underlying function. Standard subgraph isomorphism struggles with such cases. For instance, as illustrated in Figure model based on Definition I can identify that the structure representing b + is contained within x (b c). but it cannot identify the functional presence of b + within the structurally different but functionally related expression a x b aax.
2.2 Subgraph Equivalence
The limitation of structure-based subgraph matching motivates considering functional properties. Funetion-aware representation learning has emerged pivotal subfield in EDA. Many recent works
emphasize functional equivalence, denoted G, Efunc G2. DeepGate 22 23 24 and DeepCell [25
employ disentanglement to produce separate embeddings for functionality and structure, pretraining across various EDA benchmarks and predict functional similarity with task head. PolarGate (26)
enhances functional embeddings by integrating ambipolar device principles. FGNN (27 28 applies contrastive learning to align circuit embeddings according to functional similarity.
While graph isomorphism requires structural identity, functional equivalence relates graphs based on their input-output behavior. Building on this, we can define notion of subgraph relationship based on function, as shown Definition
Definition (Subgraph Equivalence). A graph Q is an equivalent subgraph of G if there exists subgraph G' of G such that Q unu G'.
3

---

This definition allows for functional matching within existing subgraphs. Some works adopt similar ideas for tasks such as arithmetic block identification [T3] 29 and symbolic reasoning [4 30], which aim to find subgraph with specific functionality rather than structure. Compared to subgraph isomorphism, subgraph equivalence offers more flexibility against local structure modifications. However, Definition still falls short for cases involving global restructuring, As shown in Figure | in the example a x b b+0 a x c, no single subgraph is functionally equivalent to b + c. The function b + is implicitly present but not explicitly represented by a contiguous subgraph.
2.3 Functional Subgraph
To address the limitations of both Definition [ and Definition 2 we introduce the concept of a functional subgraph, which aims identify the implicit containment relation between graphs.
Definition 3 (Functional Subgraph). A graph Q is a functional subgraph of G, denoted Q < G. if there exists a graph g' such that g' f g and Q is isomorphic to a subgraph of g'.
This definition captures the idea that the query's ss function is implicitly contained within the target's function, even if the target's 's structure has undergone functional transformations, and no exact subgraph isomorphic to the query graph can be found in the target graph. By this definition, we know that b + c is a functional subgraph of x b+ X since a x b b a x f fune a x (b + c) and b b+ an isomorphic subgraph of (b + c). Furthermore, Definition 3 encompasses Definition 2 i.e. Definition? i is special case of Definition B as discussed in Proposition (proof in Appendix A).
Proposition 1. If a graph Q is an equivalent subgraph g G, then Q is a functional subgraph of G.
Properties of Functional Subgraph In this paper, we assume that graph obtained by removing some nodes and edges is not functionally equivalent to the original graph, i.e. Vg A 0, G'\ ( Ffunc G.
For example, we consider illegal to directly connect two NOT gates. Therefore, such connections do not appear in our graph structures. In fact, EDA tools such as ABC (31] inherently enforce this constraint. According to Definition functional subgraphs exhibit the following properties:
Reflexivity: For any graph 9, 9 is the functional subgraph of G, i.e. VG, 9 < G.
Functional Equivalence Preservation: If Gi is functional subgraph of 92, then:
-Leet-hhand Side) if G is functionally equivalent to G1, then 9j is functional subgraph of G2, i.e. if 9 x G2 and 9i = Euuee G1. then gi < G2-
(Right-hand Side) if G/ is functionally equivalent to G2, then G1 is a functional subgraph of G/, i.e. if 91 < G2 and G/2 = E/une G2. then 91 x Gz
Transitivity: If 1 is a functional subgraph of G2 and G2 is a functional subgraph of Ga. then Gi is a functional subgraph of G3. i.e. if GI G2 and G2 < Ga. then G1 x G3.
Anti-symmetry: If Gi is a functional subgraph of G2, then G2 is a functional subgraph of G1 if and only if they are functionally equivalent, i.e. G1 < G2 and G2 x G1 and only
G1 = func G2.
For detailed proofs of the above properties, please refer to Appendix A It is worth noting that the subgraph equivalence defined in Definition not satisfy the Transitivity property. This highlights the improved completeness of the functional subgraph in Definition 3
2.4 Task Definition
Based on Definition
3. we define our primary task:
Task #1: Functional Subgraph Detection. Given query graph @ and candidate graph G. determine if Q x g.
While functional subgraph detection is a decision problem (yes/no), it is often desirable to identify which part of the target graph G corresponds to the query function Q. However, as shown Figure [ due to potential functional transformations, identifying an exact boundary in the original graph G that perfectly represents Q can be challenging or impossible. This leads to our second task, which aims to find the smallest region in G that encapsulates the function of Q.

---

Definition 4 (Fuzzy Boundary), Given query graph Q and a candidate graph G = (V, E). subgraph 9 (V*, ,") of where V C and E En (V x V*), is a fuzzy boundary for Q in if:
1. Q g
2. For any proper subgraph H. o (i.e., H 9 and H g* Q *
As illustrated Figure for 9 representing a x + a x c and Q representing b c, the fuzzy boundary G would likely encompass the components corresponding b, the multiplications, and the addition, as this minimal collection is required to functionally contain b++ via transformation. Based Definition 4 we further define another task as:
Task #2: Fuzzy Boundary Identification. Given a query graph Q and candidate graph such that Q < 9, determine for each node in 9, whether it belongs to the fuzzy boundary 9" of Q.
3 Method
3.1
Stage #1: Functional Subgraph Detection
Data Processing
Stagel: Functional Subgraph Detection
Gaig
Gzub
Query Graph
Target Graph
Random drup nodes
Fune &Sttra Subgraph
Geab
Gsta
Gaye
Functienal Subgraphh
Enonder
Function Equivalent
Synthesis
Functional Subgraph
fuig
fpm
B
Gryn
Gpm
Intra-mocal luter-madal Alignment
Mapping
Iener-modal Retrieval
Equivalont
Gysb Gzym
Cross-madal Retrieval
Figure 2: The pipeline of Stage #1. Left: Our data processing pipeline. For given Gaigs first randomly extract a subgraph Gand. Then, we obtain Gayn and 9pm through synthesis and mapping, respectively. Right: Our training pipeline via intra-modal and inter-modal alignments for functional subgraph detection. We first encode the query and target graphs using their respective encoders. Next, perform intra-moda and inter-modal alignment the target graph to obtain function-invarian and pructure-agnostte embeddings. These embeddings are then sent to a task head to determine whether the query graph is contained within the target graph.
Data Processing As illustrated in Figure 2 given an AIG netlist Gaig- first randomly drop nodes while ensuring legality, to obtain the subgraph Grab. Next, we use the ABC tool [3] to generate Geyn by randomly selecting synthesis flow. Importantly, in this step we ensure that Gayn is not isomorphic to Gaig. Finally, we apply the ABC tool again to map Gegn to 9pm using the Skywater Open Source PDK (2). This data processing pipeline ensures that Guig is equivalent to both Gogn and Gpm. Since Grub is an isomorphic subgraph of Gaig. it follows from Definition 3 that Geub is functional subgraph both Gxyn and 9pm- For negative pairs, following the approach Li et al. [1]. we randomly sample Guig. Gayz, and 9pm from other pairs within the same batch. It is important to note that all circuits in this paper have multiple inputs and single output. For more details, please refer to Section and Appendix C
5

---

Data Processing
Stage2: Fuzzy Boundary Identification
Gaig
Opm
Query Graph
Equivalent
M
Engineering
Five
Funational Sohgrph
Randam Deop Nodes
Library
Gzab
Opm
Target Graph
Prokicics
Annotation
Doodd
6pm
Nock:
Einbedding
oppr
Figure 3: The pipeline of Stage #2. Left: Our data processing pipeline. For a given 9pm. we replace each node in 9pm with the AIG implementation according to the functionality in the library. Then, we randomly sample subgraph Soub from Gaig- Finally, we annotate the nodes in 9pm if one of the corresponding AIG nodes still exist in Gzub- Right: Our training pipeline for fuzzy boundary identification via graph segmentation. Given the query graph Goud and the target graph 9pm. we first use EnCaig obtain the graph embedding of Gsub and EnCpm obtain the node embeddings of 9pm- These embeddings are then concatenated and passed to a task head to determine whether a node in 9pm lies within the fuzzy boundary of Gsub-
Retrieval In this paper, we adopt DeepGate2 [22) and DeepCell 225 as backbones for encoding AIG netlists and post-mapping netlists, respectively. Given a query graph Grub. along with positive candidates G Gagg G 9ym and negative candidates Grigo Geyn: pm we first use the AIG encoder Encaig and the PM encoder Encpm for different modalities as follows:
feub EnCuig (Soub), faig Encoig (necig(Geig)
Sayn Encaig (gogn): Spm Encpp (9pm)
Next, we concatenate the embeddings of the query graph and the candidate graphs and feed them into a classification head, a 3-layer MLP:
Jaig MLPP( faigl), Dayn = MLP([fsubr Fsym)), Opm = LMMMPL((fuuu fpm))
Finally, we compute the binary cross-entropy (BCE) loss for each prediction:
Lets =
BC Loss Yaig) BCss (Damn Meym) + BC Loss 3pm)
Function-Invaate Alignment EDA flows such synthesis and mapping modify the circuit structure while preserving functional equivalence. As defined in Definition 3 the functional subgraph relation focuses the functionality of the candidate circuits rather than structure, as they can be transformed into an equivalent circuit with any structure. Furthermore, the Functional Equivalence Preservation property Section 2.3 imply that, if the subgraph relation Q G hold, then if we replace Q or G with another functional equivalent graph, the subgraph relation continues to hold. This invariance the key insight for our alignment: the embeddings of functionally equivalent graphs should be aligned, regardless of their structural variations.
Therefore, learning function-invarian embeddings for equivalent circuits across different stages is crucial for functional subgraph detection. While Goig and Gyym share the same gate types, Goig and 9pm differ significantly in modality, i.e., the gate types in 9pm substantially dissimilar those in Guig- Therefore, we employ both intra-modal and inter-modal alignment techniques to acquire cunction-invarian and structure-and aggnosti embeddings with the InfoNCE loss the anchor and compute the intra-mor modal and inter-modal losses as follows:
33] We select Goiy as
Lintra = Inf InfoNCFFJt Joyn S Linter InffoNCE(J J fmm)
Finally, summarize the losses for stage #1 as:
Lstager Lets + Lintra + Linter

---

3.2 Stage #2: Fuzzy Boundary Identification
Data Processing As illustrated in Figure 3 given in 9pm with the corresponding AIGs from the library to acquire the netlist Gaig. This process yields a mapping function @ that associates the node indices of Goig with those of 9pm- Next, we randomly drop nodes to obtain Goub. which serves as the functional subgraph of both 9pm and Goig- Using the subgraph Gsub- we annotate the nodes in 9pm by mapping the node indices of Gsub to those of 9pm through the function Φb Specifically, for each node in Ssub. if it maps to a node in 9pm. we annotate node as I; otherwise, we annotate it as O. This annotation process strictly follows the fuzzy boundary definition in Definition
netlist Gpms we replace the cells
Cruss-modal Retrieval Given query graph Grub and a target graph 9pm = (Vpm: Epm), we first compute the embedding of Ssub and the node embeddings of 9pm:
Saub = Fnnaigg99nd fpm: Jpm: S fll/ml Encep (9pm)
Next, we use Sauh the query embedding and concatenate it with the node embeddings from 9pm. These concatenated embeddings are then fed into a 3-layer MLP for node classification: ft = MLPP([sabr ffm))) While previous works [33 29 treat this task as an input-output classification problem, we frame it as a graph segmentation task. This approach arises from the observation that nodes near the input-output nodes contribute to identifying fuzzy boundaries and thus should not be simply labeled zero. During training, we optimize the model using cross-entropy loss:
Lstugez
Σ [ys log((:) + (1 y/3 log(1 ú:)l
(1)
4 Experiment
4.1 Experimental Setup
We evaluate our method on three AIG datasets: ITC99 (15), OpenABCD [6], and ForgeEDA [17]. Each metric in Tables and ii reported as the mean + standard deviation over three independent runs. For data processing, we begin by randomly sampling k-hop subgraphs (with ranging from 8 to 12) partition large circuits into smaller circuits. Next, we randomly sample subgraphs from these smaller circuits. For logic synthesis, we use the ABC tool [1 with a randomly selected flow from sre_ srC_FS, src_rss, resyn2rs, and compress2rs. We then apply the VF2 algorithm (6) to verify that the synthesis process has modified the circuit structure. If no modification is detected, we repeat this step until we obtain circuit with different structure. For technology mapping, we invoke ABC with the Skywater Open Source PDK 32). For additional details on the environment, evaluation metrics, and dataset statistics, please refer Appendix C
Table 1: Result of Functional Subgraph Detection(%) (%).
Geub + Gagn
Grub + 9pm
Dataset
Method
Accuracy
Precision
Recall
F1 F1-score
Accuracy
Precision
Recall
F1-score
NeuroMatch
49.8
16.7223.6
33.3247.
22.2231.4
49.8
16.7 16.7 50.0450.0
33.4233.4
ITC99
HGCN
44.5+7.7
35.0+21.2
67.3246.3
45.3230.2
49.540.8
35.7
66.8
44.7231.2
Gamora
50.6+12.8 21.1427.7
33.0446.0
25.4434.
51.7444.
34.0a24.2
40.2
20.2
ABGNN
56.4+9.1
20.8
32.7
25.4435.9
54.145.8
19.0+26.9
33.3
24.2+-3.2
Ours
95.320.1
94.420.2
96.3
95.440.0
93.1
92.3_o.s
94.220.9
93.220.4
OpenABCD
NeuroMatch
44.2
17.3
33.4
22.7
44.94s.4
17.0a25.
33.4
22.5
HGCN
52.543.6
18.0425.5
32.5446.0
23.2=32.8
50.040.0
20.4
33.0.16.7
22.2=31.3
Gamora
50.8
33.7123.9
66.6147.1
14.2.117
49.8
33.2228.5
62.1
43.3
ABGNN
31.115.4
5.213.9
2.6128
3.423.2
41.3140
9.717.6
3.523.2
5.1
Ours
92.310.2
93.7
90.6.0.4
92.110.2
90.8
92.4
88.910.9
90.6
ForgeEDA
NeuroMatch
50.0
16.7+23.0
33.3447.1
22.2+31.4
50.0
76.7.
33.3
22.2=31.4
HGCN
44.0
18.2+22.6
23.1
48.8
18.8
33.5447.0
22.5231.2
Gamora
40.646.3
2.4+1.6
0.7
1.0
48.2+1.5
51.048.2
31.0431.6
28.5
ABGNN
52.343.3
34.6121.5
66.6447.1
45.5+32.2
52.0129
34.41214
66.6 35.4
Ours
96.0
96.8
95.
25.2
96.0zo.1
95.3
95.920.5
94.7 95.320.0
7

---

4.2 Stage #1: Functional Subgraph Detection
We evaluate the performance of proposed method three datasets: ITC99, OpenABCD, and ForgeEDA. Our method is compared against several state-of-the- art models, including Neuro- Match [10] and HGCN [12,, which are designed for isomorphism subgraph matching in general domain and EDA domain respectively, and Gamora [4] and ABGNN [T3] which are designed for reasoning in EDA domain, i.e. for equivalent subgraph matching. Since Gamora and ABGNN focus on boundary detection instead of subgraph matching, we integrate them into the NeuroMatch framework for Stage #1. Further integration of Gamora and ABGNN with our method is discussed in Appendix B The evaluation metrics include accuracy, precision, recall, and Fl-score, computed for two tasks: Saub Seyn and Goub to 9ym.
As shown in Table the results on the ITC99, OpenABCD, and ForgeEDA datasets demonstrate that method significantly outperforms all baseline models. Specifically, for the Sub - Gsyn task, our model achieves an average accuracy of 94.5%, precision of 95.0% 55.0 recall of 94.0%, and F1-score of 94.5%, surpassing all other methods by large margin. Similarly, for the Gsub 9pm task, method also shows superior performance with an accuracy of 93.1%, precision of 93.5% recall of 92. 6%, and F1-score of 93.0%. In contrast, structure-based methods show an accuracy close to 50% and large standard errors in precision, recall, and F1 -score. Such unreliable performance typically arises because these methods indiscriminately predict all pairs as either entirely positive or negative, highlighting their limitations in functional subgraph detection.
4.3 Stage #2: Fuzzy Boundary Identification
Table 2: Result of Fuzzy Boundary Identification %).
ITC99
OpenABCD
ForgeEDA
Method
IoU
DICE
ToU
DICE
IoU
DICE
NeuroMatch
44.2+0.0
61.3+p.0
41.2+0.0
58.3 58.320.0
42.0g0.0
59. 59.1
HGCN
44.110.0
61.210.0
41.210.0
58.310.0
42.020.0
59.2=0.0
Gamora
39.112.8
56.242.9
44.2
61.3
39.5
56.620.6
ABGNN
26.716.2
41.7
37.5...8
54.510.8
31.942.
48.2
Ours
83.0+1.4
90.7
85.
85.220.9
92.0+n.5
83.8
91.220.4
In this stage, we treat Grub as the query and aim to locate its fuzzy boundary within the post-mapping netlist Gpm- Since Gamora and ABGNN are designed for the detection of the input-output boundary, we first apply each to identify the input and output nodes in 9pm. We then perform BFS between inputs and outputs to recover the corresponding fuzzy boundary, and evaluate the result using Intersection-ove--nniie Union (IoU) and DICE score.
repoerr results ITC99, OpenABCD, and ForgeEDA, demonstrating that our model substan- tially outperforms all baselines. Specifically, we achieve an average IoU of 84.0% and Dice score of 91.3%, significantly outperforming all other methods. Structure-based methods (e.g.. NeuroMatch and HGCN) fail to capture functional boundaries and often generate trivial solutions (predicting all nodes boundary nodes), yielding low variance but poor performance. Although Gamora and ABGNN can detect clear block boundaries for specific arithmetic modules, they struggle with the variable, function-drive fuzzy boundaries required here, resulting in significantly lower performance. Further integration of Gamora and ABGNN within our framework is detailed in Appendix
4.4 Ablation Study
We perform ablation study on ITC99 dataset and compare the performance of the ablation settings with our proposed method to evaluate the contribution of various components in method.
Stage #1 without alignment achieves accuracy and FI-scores 94.6% and 94.6% 94.6% on Goub + G task, which are lower than our method's 95.3% and 95.4%. Our model also improves accuracy and F1- score by 1.7% on Grub - 9pm task. These results demonstrate the importance of function-invariant alignment, particularly inter-modal alignment, i.c. aligning 9pm and Gaig.
8

---

Table 3: Ablation Study ITC99 Dataset(
Stage
Stage
Setting
Gavh Gryn
Gaub 7 6pm
Grnb + 6pm
Accuracy
Fl-score
Accuracy Fl-score IoU
DICE
Stage wo. alignment
94.6
94.6
91.4
91.5
Stage #2 stage #1
76.3
86.5
Stage N2 wo. seg.
29.6
45.7
Ours
95.3
95.4
93.1
93.2
83.0
90.7
Stage #2 without Stage #1 shows performance drop, with IoU and DICE scores of 76.3% and 86.5%, compared to our method's improved values of 83.0% and 90.7%. This highlights the crucial role of pretraining knowledge in Stage #1.
Stage #2 without segmentation also shows a significant drop in performance, with IoU and DICE values of 29.6% and 45.7 45.7%, compared to our method's ' improved 83.0% and 90.7%. These results suggest that directly predicting the input-output nodes of the fuzzy boundary is challenging, as varies with different functional transformations and omits the information of nodes in fuzzy boundary.
5
Limitations
While our proposed framework demonstrates strong performance and significant improvements over existing structural approaches, several limitations remain and should be addressed in future research:
Scalability to Large-scale Circuits:
Currently, our method has primarily been evaluated on moderately-sized circuits due to computational resource constraints. Real-world EDA applications often involve extremely large netlists with millions of nodes. Scaling our detection and segmentation approaches to handle such large-scale graphs efficiently is non-trivial. Future research could investi- gate more computationally efficient embedding methods, hierarchical segmentation approaches, or incremental graph processing techniques to enhance scalability.
Our fuzzy boundary identification method presently assumes a single, minimal enclosing region within the target graph. In practical scenarios, multiple occurrences or overlapping functional subgraphs might exist within a single large circuit, compli- cating boundary identification tasks. Extending methodology to effectively handle multiple or overlapping fuzzy boundaries within the same circuit remains an open and challenging direction for further investigation.
Multiple and Overlapping Fuzzy Boundaries:
Single-output Circuit Assumption: The current approach assumes single-output logic circuits. In real-world scenarios, however, most circuits possess multiple outputs and complex internal functional dependencies. The direct applicability of our method to multi-output circuits, particularly when outputs share significant internal logic, remains unexplored. Generalizing the definitions and embedding strategies to model multi-output scenarios could further enhance practical relevance.
Non-trivial Function Assumption: In this paper, we assume that graph obtained by removing some nodes and edges is not functionally equivalent to the original graph, i.c. Vg & G \'gg Ftune G. While EDA tools inherently enforce this constraint, it may limit the generalizability of the functional subgraph in other domains.
By systematically addressing these limitations, subsequent research can extend our approach to broader, more realistic settings, thereby increasing its practical utility EDA domain and beyond.
6 Conclusion
In this paper, we introduce the concept of functional subgraph matching, method to identify implicit logic functions within larger circuits, despite structural variations. We propose a two-stage framework: first, we train models across different modalities with alignment to detect functional subgraphs; second, we fine-tune our model and treat fuzzy boundary identification as a graph segmentation task for precise localization of fuzzy boundary. Evaluations on benchmarks (ITC99, OpenABCD, ForgeEDA) show that our approach outperforms structure-based methods, achieving 93.8% accuracy in functional subgraph detection and a 91.3% DICE score for fuzzy boundary detection.

---

Broader Impact Our method contributes to the advancement of deep learning, particularly in graph-based functional relationship analysis. By improving the detection of functional relationships in complex systems, it has the potential to impact wide range of applications, from circuit design to other domains that rely on graph functionalityy, e.g. molecular and protein graphs.
Acknowledgment This work was supported in part by the Hong Kong Research Grants Council (RGC) under Grant No. 14212422, 14202824, and C6003-24Y.
References
[1] Alireza Mahzoon, Daniel Große, and Rolf Drechsler. Polycleaner: clean your polynomials before backward rewriting to verify million-gate multipliers, In 2018 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages 1-8. IEEE, 2018.
[2] Alireza Mahzoon, Daniel Große, and Rolf Drechsler. Revsca: Using reverse engineering to bring light into backward rewriting for big and dirty multipliers. In Proceedings of the 56th Annual Design Automation Conference 2019, pages 1-6, 2019.
[3] Xing Wei, Yi Diao, Tak-Kei Lam, and Yu-Liang Wu. A universal macro block mapping scheme for arithmetic circuits. In 2015 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 1629-1634. IEEE, 2015.
[4] Travis Meade, Shaojie Zhang. Yier Jin, Zheng Zhao, and David Pan. Gate-level netlist reverse engineering tool set for functionality recovery and malicious logic detection. In International Symposium for Testing and Failure Analysis, volume 81368, pages 342-346. ASM International, 2016.
[5] Haocheng Li, Satwik Patnaik, Abhrajit Sengupta, Haoyu Yang, Johann Knechtel, Bei Yu, Evangeline FY Young. and Ozgur Sinanoglu. Attacking split manufacturing from deep learning perspective. In Proceedings of the 56th Annual Design Automation Conference 2019, pages 6-6, 2019.
[6] Luigi P Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. A (sub) graph isomorphism algorithm for matching large graphs. IEEE transactions on pattern analysis and machine intelligence, 26(10):1367-1377 2004.
[7] Julian R Ullmann. An algorithm for subgraph isomorphism. Journal of the ACM (JACM), 23 (1):31-42, 1976.
[8] Luigi Pietro Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento, et al. An improved algo- rithm for matching large graphs. In 3rd IAPR-TCI5 workshop on graph-based representations in pattern recognition, pages 159-159. Citeseer, 2001.
[9] Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. Simgnn: A neural network approach to fast graph similarity computation. In Proceedings of the twelfth ACM international conference on web search and data mining, pages 384-392, 2019.
[10] Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, Jure Leskovec, et al. Neural subgraph matching. arXiv preprint arXiv:2007.0300 2020.
[11] Rex Ying, Tianyu Fu, Andrew Wang, Jiaxuan You, Yu Wang, and Jure Leskovec, Representation learning for frequent subgraph mining. arXiv preprint arXiv:2402.1 14367, 2024.
[12] Bohao Li, Shizhang Wang, Tinghuan Chen, Qi Sun, and Cheng Zhuo Efficient subgraph matching framework for fast subcircuit identification. In Proceedings of the 2024 ACM/IEEE International Symposium on Machine Learning for CAD, pages 1-7, 2024.
[13] Ziyi Wang, Zhuolun He, Chen Bai, Haoyu Yang, and Bei Yu. Efficient arithmetic block identification with graph learning and network-flow. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 42(8):2591 2022.
10

---

[14] Nan Wu, Yingje Li, Cong Hao, Steve Dai, Cunxi Yu, and Yuan Xie. Gamora: Graph learning based symbolic reasoning for large-scale boolean networks. 2023 60th ACM/IEEE Design Automation Conference (DAC), pages 1-6. IEEF, 2023.
[15] Scott Davidson. Characteristics of the i9'' benchmark circuits. In ITSW, 1999.
[16] Animesh Basak Chowdhury, Benjamin Tan, Ramesh Karri, and Siddharth Garg. Openabe-d:
A large-scale dataset for machine learning guided integrated circuit synthesis. arXiv preprint arXiv:2110. 1 1292, 2021.
[17] Zhengyuan Shi, Zeju Li, Chengyu Ma, Yunhao Zhou, Ziyang Zheng, Jiawei Liu, Hongyang Pan, Lingfeng Zhou, Kezhi Li, Jiaying Zhu, et al. Forgeeda: A comprehensive multimodal dataset for advancing eda. arXiv preprint arXiv:2505.02016 2025.
[18] Vincenzo Bonnici, Rosalba Giugno, Alfredo Pulvirenti, Dennis Shasha, and Alfredo Ferro. A subgraph isomorphism algorithm and its application to biochemical data. BMC bioinformatics, 14:1- 13, 2013.
[19] Wenfei Fan. Graph pattern matching revised for social network analysis. Proceedings of the 15th international conference database theory, pages 8-21, 2012.
[20] Jinha Kim, Hyungyu Shin, Wook-Shin Han, Sungpack Hong, and Hassan Chati. Taming subgraph isomorphism for rdf query processing, arXiv preprint
2015.
[21] Jorge Pérez, Marcelo Arenas, and Claudio Gutierrez. Semantics and complexity of sparql. ACM Transactions on Database Systems (TODS), 34(3):1445, 2009.
[22] Zhengyuan Shi, Hongyang Pan, Sadaf Khan, Min Li, Liu, Junhua Huang, Hui-Ling Zhen, Mingxuan Yuan, Zhufei Chu, and Qiang Xu. Deepgate2: Functionality-awwr aware eircuit repre- sentation learning. In 2023 IEEF/ACM International Conference Computer Aided Design (ICCAD), pages 1-9. IEEE, 2023.
[23] Zhengyuan Shi, Ziyang Zheng, Sadaf Khan, Jianyuan Zhong, Min Li,, and Qiang Xu. Deepgate3: Towards scalable circuit representation learning. arXiv preprint arXiv:2407.1 1095, 2024.
[24] Ziyang Zheng, Shan Huang, Jianyuan Zhong, Zhengyuan Shi, Guohao Dai, Ningyi Xu, and Qiang Xu. Deepgate4: Efficient and effective representation learning for circuit design at scale. arXiv preprint 2rXiv:2502.01681, 2025.
[25] Zhengyuan Shi, Chengyu Ma, Ziyang Zheng, Lingfeng Zhou, Hongyang Pan, Wentao Jiang, Fan Yang, Xiaoyan Yang, Zhufei Chu, and Qiang Xu. Deepcell: Multiview representation learning for post- most-maaping netlists. arXiv preprint arXiv:2502. 200::2262.0066, 2025.
[26] Jiawei Liu, Jianwang Zhai, Mingyu Zhao, Zhe Lin, Bei Yu, and Chuan Shi. Polargate: Breaking the functionality representation bottleneck of and-inverter graph neural network. In 2024 IEEF/ACM International Conference on Computer-Aide Design (ICCAD), 2024.
[27] Ziyi Wang, Chen Bai, Zhuolun He, Guangliang Zhang, Qiang Xu, Tsung-Y Yi Ho, Bei Yu, and Yu Huang. Functionality matters in netlist representation learning. In Proceedings of the 59th ACM/IEE Design Automation Conference, pages 61-66, 2022.
[28) Ziyi Wang, Chen Bai, Zhuolun He, Guangliang Zhang, Qiang Xu, Tsung- Yi Ho, Yu Huang, and Bei Yu. Fgnn2: A powerful pre-training framework for learning the logic functionality of circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2024.
[29] Zhuolun He, Ziyi Wang, Chen Bai, Haoyu Yang, and Bei Yu. Graph learning- based arithmetic block identification. In 202/ IEEF/ACM International Conference On Computer Aided Design (ICCAD), pages 1-8. IEFE, 2021.
[30] Chenhui Deng, Zichao Yue, Cunxi Yu, Gokce Sarar, Ryan Carey, Rajeev Jain, and Zhiru Zhang. Less is more: Hop-wise graph attention for scalable and generalizable learning on circuits. In Proceedings of the 6lst ACM/IEEE Design Automation Conference, pages 1-6, 2024.
11

---

[31]
Robert Brayton and Alan Mishchenko. Abc: An academic industrial verification tool. In CAV 2010, Edinburgh. UK, July 15-19, 2010. Proceedings 22, pages 24-40 Springer, 2010.
[32] Google. Skywater open source pdk. URL htt.lttp////tthbbb.oooo/gggggg/ git
2020.
[33] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint 1x01v 2018.
[34] Vincenzo Carletti, Pasquale Foggia, Alessia Saggese, and Mario Vento. Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with vf3. IEEE transactions on pattern analysis and machine intelligence, 40(4):804-818, 2017.
A Proofs of the Proposed Properties
In this section, we use 11 = G2 to denote that G1 is isomorphic to G2. Also, use G1 Ffune G2 to denote that G1 functional equivalent to Gz. Proposition If a graph Q an equivalent subgraph of 9, then Q is a functional subgraph of g.
Proof. According to the Definition
there exists subgraph G' of g such that Q Funn G'. By
replacing g' with Q, we get G isomorphic to Q. By the Definition
g' U Q which is equivalent to G and a subgraph of G is a functional subgraph of g.
Proposition 3 (Reflexivity). GG, < g.
Proof. G is subgraph of itself, and G fuunc G. By the definition of functional subgraph, it follows that G G.
Proposition 4 (Functional Equivalence Preservation). If is functional subgraph of G2. then:
(Left-hand Side) if 91 & G2 and gi =func Gr, then g $ G2-
(Right-hand Side) if G1 * G2 and G/2 = Fuue G2, then 91 * Gzz
Proof. (Right-hand Side) According to the Definition 3 if 91 is functional subgraph of G2, then
there exist G5 that Gj Ffune G2 and 91 is an isomorphic subgraph of Gj. Since 9 =uue G2 and Gj Stune G2, then Gz Since Z2 fuune Z2 By the Definition 3 Gi a functional subgraph of Gz.
(Left-hand Side) By Definition there exists graph 9 Ffunc G2. such that
G G2
(2)
where Go is a subgraph of S22 Since 91 = G2. it follows that
G1 Fune G2.
By the transitivity of functional equivalence, we then have
G. fume G2 Etunc g[-
Thus, by replacing G2 in g/2 with 9t we obtain new graph
9h ( G2) 9/
(5)
which satisfies
Gy Fuunc Gz.
(6)
From the definition of functional equivalence, we know that G =tunc G2 and that &f is a subgraph of GKr Therefore, it follows that
g x Gz.
Proposition 5 (Transitivity). If & G2 and G2 Gz. then Si G3.
12

---

Proof. By definition, there exists graph 02 ffunc G2, such that
G G1, and 9 a subgraph of G2.
(8)
Since G22 ffunc G2, by Proposition follows that 922 < G3.
Therefore, there exists a graph 9 Ffunc G3, and J2 a subgraph of Gzz. Since 9n a subgraph of L/2 and 3/ is subgraph of gg. follows that 91 is subgraph of G3--
Since 91 = 91. 93 fune 93 and Ø1 is subgraph of g3 by the definition of functional subgraph, we conclude that
G1 x G3.
Proposition 6 (Anti-symmetrry, 91 G2 and G2 + 9n if and only if 91 Efunc G2.
Proof. (=) Since 91 < 92, we have
91 g \g and G2 =fuuc J2-
(10)
Since G2 N G1, we have G & 9 9. By the definition of functional subgraphs, there exists graph 93 such that G3 ftunc Ø2 \. and G2 is subgraph of 93- This implies that G = 93 \ g so we also have
Ø2 fune G3 \g'
(11)
Since G3 fune G/ \ g. follows that
G3 Ug Fuue G2-
(12)
Thus, we have
G3 U Fune G2 tune G3 \g/
(13)
Note that in Section 2.3 functionally equivalent to the original graph, i.c., Vgg * 0, G \ Fuue G. Therefore, we must have g 0. which implies
assume that graph obtained by removing some nodes and edges
91 = G2 \ G2 and G2 Sune G2.
(14)
Thus, we conclude that
91 fune G2.
(15)
(+) If 91 Efune G2, since 91 o 91 and G2 & G2. according to Functional Equivalence Preservation property, follows that 91 * G2 and G2 x 91.
B Additional Experimental Results
B.1 Functional Subgraph Matching
Considering that the encoder our method can be replaced with other backbones, we test our approach with different encoders and propose baselines for the functional subgraph detection task, as shown in Table
B.2 Fuzzy Boundary Identification
We further evaluate these methods on fuzzy boundary identification. The results are shown in Table
Table 5: Result baselines stage #2.
ITC99
OpenABCD
ForgeEDA
Method
IoU
DICE
IoU
DICE
IoU
DICE
Ours+Gamora
82.1
90.2
81.4
89.8
83.6
91.1
OBGNN
82.7
90.5
84.4
91.5
88.4
93.8
Ours
83.0
90.7
85.2
92.0
83.8
91.2
13

---

Table 4: Result of baselines in stage #1.
Goub
Geyn
Gaub
ppm
Dataset
Method
Accuracy
Precision
Recall
Fi-score
Accuracy
Precision
Recall
Fl Fi-score
Ours+Gamora
90.8
91.1
90.4
90.7
86.4
88.6
83.5
86.0
ITC99
OuIS+ABGNN
87.9
83.1
95.1
88.7
88.2
82.8
96.5
89.1
Ours
95.3
94.4
96.3
95.4
93.1
92.3
94.2
93.2
GarsrGamora
90.1
89.6
90.7
90.2
91.0
89.3
93.2
91.2
OpenABCD
OurS+ABGNN
81.7
78.5
87.5
82.7
83.3
78.9
91.1
84.5
Ours
92.3
93.7
90.6
92.1
90.8
92.4
88.9
Ours+Gamort
94.2
94.1
80.6
65.5
77.1
ForgeEDA
OurS+ABGNN
89.7
88.5
91.2
89.8
87.6
88.3
86.8
87.5
Ours
96.0
96.8
95.2
96.0
95.3
95.9
94.7
95.3
B.3 Scalability on Medium-Sized Circuits
we collect a medium-sized graph dataset from ForgeEDA [7
containing circuits with graph sizes
ranging from 100 to 10000 nodes. The statistical information of the medium-sized dataset is shown in Table
Table 6: Statistics of the medium-sized dataset.
Graph Type
Nodes
Edges
Depth
G
192.1 + 320.87
207.16 + 354.01
27.91 + 30.08
Gayn
1396.99 + 1764.63 679.93 + 851.2
1958.84 + 2519.23
66.48 + 99.7
Gpm
1352.96 + 1703.16
21.83 + 32.6
We perform functional subgraph detection this dataset, and the results are shown in Table and 8 Since ABGNN encounters out-of-memory eтror when encoding graphs with deep logic levels, do not report its results on this new dataset. While method still demonstrates state-of-the-an performance, it shows a significant performance drop (from an Fl-score of 55.3% to 81.2%, as shown Table 1). This result highlights the challenge of scaling larger circuits. We hope future work will explore and address this challenge.
Table 7: Functional Subgraph Detection on Gsub +
Genn.
Method
Accuracy
Precision
Recall
F1-score
NeuroMatch
51.223.3
34.6424.5
66.7
45.51322
HGCN
50.0_o.0
16. (6.7423.6
33.31447.
22.24314
Gamora
50.0
40.0+14.1
66.74
44.6431.
Ours
81.540.6
82.741.1
79.841.7
81.240.8
B.4 Comparison with VF3
we evaluate the state-of-the-ar subgraph isomorphic heuristic algorithm VF3 + which consistently achieves 100% precision and 100% recall on standard subgraph isomorphism tasks. Due to time constraints, we sampled circuits with fewer than 50 nodes from the ForgeEDA dataset and applied the VF3 algorithm. The results are shown in Table 9 According to our Definition Functional Subgraph, Q is an isomorphic subgraph of G, then Q is always functional subgraph of G. This is demonstrated by the 100% precision achieved by VF3. However, due to the function-preserving transformation, the explicit structure of Q often disappears, leading to extremely low r0.al)(0.32%)) for VF3. These results highlight the importance of task definition.
14

---

Table 8: Functional Subgraph Detection on Gsub
Gpm-
Method
Accuracy
Precision
Recall
F1-score
NeuroMatch
51.0_1.2
33.94210
66.6447711
44.94318
HGCN
50.0_o.0
16.7 16.7423.6
33.3
22.24314
Gamora
50.0=0.0
33.3+23.6
66.7
44.4+314
Ours
78.9
80.611.6
76.3
78.3
Table 9: Comparison of subgraph isomorphism methods on different tasks.
G Gsyn
Gsub
Gpm
Method
Runtime (s)
Precision
Recall
Fl-score
Precision
Recall
Fl-score
VF3 Ours
480.8
100.0
0.32
0.65
8.0
88.5
91.9
90.2
86.4
94.5
90.3
C Datasets and Implementation Details
Dataset Dataset statistics and splits are shown in Table 10 For dataset split, we first split the training cireuits and test circuits in the source dataset, then cut subgraph for the training circuit and test circuits to generate our small circuit dataset. For ITC99 and OpenABCD, the split follow the previous work [24] For ForgeEDA, randomly select 10% circuits in the dataset as test circuits. For small circuit, we apply Algorithm |
to randomly sample subgraph.
Algorithm Random Sample Subgraph
Input: ndoes edges root Output: nodes V, edges E, root Build adjacency G from & if ra, 1) < 0.5 then
Set the predecessor p E G(r) that maximizes prodCount(P (p)
end if
P + r0nd(0.6, 0.95)
T < p. V.. V < (r), + [1),
E+0
while Q + V < T do
(Q) for all e E (auffle(G[ni]] do if v & V then push(Q, v); V [o]: EU u() end if end for end while return V. E,
Table 10: Dataset Statistics, We report average and standard error with avg. + sld.
Source Dataset
Goat
Gaig
Gzyn
Gpm
Split #Pair
#Node
Depth
#Node
Depth
#Node
Depth
#Node
Depth
train
36592
248
15.0+2.
320
19.1
315-104
19.0as.0
179 6.9410
ITC99
test
5917
218
14.0
282
17.3
278
17.0420
157
6.3
train
54939
155
13.042.
203
16.443.2
198
16.04s.0
108275
5.8
OpenABCD
test
9726
100
13.0
132as4
16.0
128482
15.0+20
69448
5.5
ForgeRDA
train
60183
126+102
13.443..
161
16.6442
156=125
16.244.5
88269
5.8+14
test
7753
127
13.643.3
163
17.043.8
159=120
16.4+.1.
89
5.9
15

---

Environment All experiments are run on an NVIDIA A100 GPU with 64 GB of memory. Models are trained using the Adam optimizer with learning rate of 0.001, batch size of 1024. We train our model in stage#1 for 100 epochs and finetune it in stage#2 for 10 epochs. Training our model on one dataset takes approximately hours. Model architectures follow the configurations specified the original works except that we set the hidden dimension to 128 for all models.
Evaluation Metries For Stage #1, we measure classification performance by accuracy and report precision, recall and fl-score according to the counts of true positives (TP), true negatives (TN), false positives (FP), and false negatives (FN):
TP
TP
Precision
TP FP' Recall
TP + FN
TP TN
x Precision x Recall
Accuracy
TP TN + FP + FN' Fl-score Precision + Recall
For Stage #2, which is similar to a segmentation task, we use Intersection over Union (IoU) and Dice coefficient. Let P be the set of predicted positive nodes and G the set of ground-truth positive nodes:
PPn PPUG|
2|P G
loU
Dice = PP| + G
(16)
D Background
And-Inverter Graph(AIG) In our works, AIG is a directed acyclic graph (DAG) composed of three basic elements: Primary Input(PI), AND gate and NOT gate. For example, simple logic expression -A A B can be build as a DAG with 2 Pls(A and B), one NOT gate and one AND gate. The edges are [(A, NOT), (NOT, AND), (B, AND) Since the out-degree of AND is zero, represents the final output.
Technology Mapping Technology Mapping is function-preserving transformation that converts an AIG into post-mapping (PM) netlist. While the AIG consists of simple logic elements, such as AND and NOT gates, the basic components in PM netlist be more complex, such adders multipliers. As a result, node types can differ significantly between the two forms, and this is why we consider AIG and PM netlists as distinct modalities in this paper.
Logic Synthesis Logic synthesis aims to simplify the structure of an AIG while preserving its functionality. It transforms one AIG into another with a simpler structure. For example, the expression eq1 (A A B) A (A C`) can be simplified to A A B A C. Although eqı and eqe are functional equivalent, egg uses only 2 AND gates compared AND gates eq1-
InfoNCE Loss InfoNCE (Information Noise-Contrastive Estimation) is a contrastive loss used in self-supervised learning. Its goal is to identify a single "positive" sample from set of "negative" samples for given "anchor" sample. It pulls the anchor and positive representations together while pushing the anchor and negatives apart:
exp(sim(q. k+)/T)
LInfONCE log
(17)
Di=o exp( sim ks)/T)
where q is the anchor, h4 is the positive, k; are the negatives, sim is similarity function (like dot product), and is temperature hyperparameter.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We list our contribution in introduction, shown in Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss limitations of our method Section 5 including the Scalability to Large-scale Circuits, Multiple and Overlapping Fuzzy Boundaries and Assumptions.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
17

---

Justification: We proposed 4 properties of functional subgraph in our paper. and the proof can be found in Appendix Guidelines:
We also clairfy our assumption in Section 2.3
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
For dataset processing, we provide the details in Section 4.1 and Appendix C For our models, we first detailed our pipeline in Section [] Futhermore, our used backbones are all opensource and the implementations details can also be found in Section 4. and Appendix [
Justification:
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
18

---

reproducible, they 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
We provide the code and data in supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
public/guides
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ec/geeuuu///oouubniiiii 7/nips cc/ wtc/publiic// cubbiccguuidss gww.///ieeee/eee// Codeeoobiiieseee SanSSuubissss issiionn ssionnoiccyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We specify the experimental details in Section 4.1 and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report I-sigma error bars, i.c. average result with standard error in Table |
and 2
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
19

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The detail about compute resources can be found in Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We make sure research conducted the paper conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss the broader impacts in Section O
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
20

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cite the original paper or website of assets.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
21

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[Yes]
Justification:
We detail our dataset processing flow and model in our paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
22

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy buttps://neure wwwparripp..ccoooeeeeeeeeeec /t/CCooffeeence///2222 for what should or should be described.
23


Reviews:
[{"review_id": "96eaesNq6X", "reviewer": "Reviewer_apyh", "summary": "This paper proposes a functional subgraph matching method for subgraph matching  in EDA, which shifts focus from brittle structural matching to logic-aware functionality—critical for real-world EDA. The proposed method include 2 stages: the first stage trains multimodal embeddings (intra/inter-modal alignment) for cross-stage functional detection, while the second stage formulates boundary identification as graph segmentation (not classification) to improve continuity/accuracy. Experiments EDA benchmarks demonstrates the proposed method significantly outperforms baselines.", "questions": "More discussion about the performance increase would be preferred.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. This paper is well motivated and is easy to follow.\n2. The experiment results is solid and proposed method significantly boosts the DICE score on EDA benchmarks (ITC99, OpenABCD, ForgeEDA), far exceeding structural baselines.\n3. Directly enables cross-stage verification (e.g., from pre-synthesis to post-layout).\n\nWeaknesses\nOverall, I think the novelty of the proposed method is limited in some sense. From my perspective, the key idea of this paper is a combination of subgraph classification, DVAE[1], and CktGNN[2]. Overall, the key concept is to find the functional equivalence rather than structural isomorphism. More discussion about this concern is preferred. \n\n[1] Zhang M, Jiang S, Cui Z, et al. D-vae: A variational autoencoder for directed acyclic graphs[J]. Advances in neural information processing systems, 2019, 32.\n[2] Dong Z, Cao W, Zhang M, et al. CktGNN: Circuit Graph Neural Network for Electronic Design Automation[C]//The Eleventh International Conference on Learning Representations.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for valuable feedback. Here are our answers to the weaknesses and questions.\n\n**Q1: More discussion about the performance increase would be preferred.**\n\nA1: Regarding the performance increase, we provide more detailed discussion below. Overall, we attribute our performance improvement to 3 parts:\n* Task definition\n* Two-stage framework\n* Function learning ability of GNN model\n\n\n**Task Definition** \nTo the best of our knowledge, our work introduces the concept of a functional subgraph for the first time, which differs significantly from subgraph isomorphism and subgraph equivalence, as discussed in Section 2. This difference in definition naturally leads to a different task formulation.\n\nTo further illustrate this, we evaluate the state-of-the-art subgraph isomorphic heuristic algorithm VF3 [1], which consistently achieves 100% precision and 100% recall on standard subgraph isomorphism tasks. Due to time constraints, we sampled circuits with fewer than 50 nodes from the ForgeEDA dataset and applied the VF3 algorithm. The results are shown below:\n\n| Method | Runtime (s) | Precision (sub→syn) | Recall (sub→syn) | F1-score (sub→syn) | Precision (sub→pm) | Recall (sub→pm) | F1-score (sub→pm) |\n|--------|-----------:|--------------------:|-----------------:|-------------------:|-------------------:|----------------:|------------------:|\n| VF3    | 480.8     | 100.0              | 0.32             | 0.65               | –                  | –               | –                 |\n| Ours   | 8.0        | 88.5               | 91.9             | 90.2               | 86.4               | 94.5            | 90.3              |\n\nAccording to our Definition 3 of Functional Subgraph, if $Q$ is an isomorphic subgraph of $G$, then $Q$ is always a functional subgraph of $G$. This is demonstrated by the 100% precision achieved by VF3. However, due to the function-preserving transformation, the explicit structure of $Q$ often disappears, leading to extremely low recall(0.32%) for VF3. These results highlight the importance of task definition. \n\n\n\n\n**Two-Stage Framework**\nTable 4 in Section 4.4 discusses the effectiveness of our proposed alignment, two-stage training and graph segmentation. The results demonstrate the effectiveness of each component in our method.\n\nSpecifically, for fuzzy boundary identification, previous works on targeting arithmetic block identification (Subgraph Equivalence), such as Gamora [2] and ABGNN [3], focus on identifying exact input/output patterns. When identifying a half adder, Gamora, for instance, requires the root of the subgraph to be a XOR gate. However, after function-preserving transformations, such explicit boundaries may disappear (as discussed in Section 2.4), leading to significant performance degradation for these methods.\n\nFurthermore, considering that the graph encoder in our method can be replaced with other backbones, we evaluate our approach using alternative encoders designed for function-related tasks and propose several baselines, as shown in Tables 4 and 5 in Appendix B. The results demonstrate that with our proposed framework, these models gain significant performance improvement, indicating the importance of our proposed two-stage framework.\n\n\n**Function learning ability of GNN model** \nPrior works on subgraph isomorphism mainly focus on designing GNN models to learn structural patterns rather than functional behavior. As a result, these models perform poorly on function-related tasks, as discussed in prior studies [4,5]. \n\nFor function-related method, like Gamora and ABGNN, we integrate these graph encoders into our framework, and the results are as shown in Tables 4 and 5 in Appendix B. Even though with a significant performance improvement, these methods still show a significant performance drop compared to our method, indicating that the GNN architecture also leading to performance gap.\n\n*[1] Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with VF3 - Carletti V., Foggia P., Saggese A., Vento M. - IEEE transactions on pattern analysis and machine intelligence - 2018*\n\n*[2]Wu N, Li Y, Hao C, et al. Gamora: Graph learning based symbolic reasoning for large-scale boolean networks[C]//2023 60th ACM/IEEE Design Automation Conference (DAC). IEEE, 2023: 1-6.*\n\n*[3]Wang Z, He Z, Bai C, et al. Efficient arithmetic block identification with graph learning and network-flow[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 42(8): 2591-2603.*\n\n*[4]Liu J, Zhai J, Zhao M, et al. Polargate: Breaking the functionality representation bottleneck of and-inverter graph neural network[C]//Proceedings of the 43rd IEEE/ACM International Conference on Computer-Aided Design. 2024: 1-9.*\n\n*[5]Zheng Z, Huang S, Zhong J, et al. DeepGate4: Efficient and Effective Representation Learning for Circuit Design at Scale[C]//The Thirteenth International Conference on Learning Representations.*\n\n\n**Q2: Overall, I think the novelty of the proposed method is limited in some sense.... Overall, the key concept is to find the functional equivalence rather than structural isomorphism. More discussion about this concern is preferred.**\n\n\nA2: Thanks for the suggestion from reviewer. We would like to emphasize that the components of our proposed method stem from **the novel insight behind our proposed concept**, which has never been discussed in previous work. Our contribution can be summarized in three points.\n\n\nFirst, to the best of our knowledge, we for the first time introduce and formally define the novel concept of **functional subgraph matching**, clearly distinguishing it from structural isomorphism and functional equivalence. We also want to highlight that the definition itself plays a crucial role. As discussed in Q1, we evaluated the state-of-the-art heuristic for subgraph isomorphism, VF3. The comparison between VF3 and our method clearly highlights how differences in task formulation significantly impact the effectiveness of existing approaches.\n\nSecond, we develop a **two-stage multi-modal** embedding framework, leveraging both intra-modal and inter-modal alignment to capture structure-agnostic and function-invariant graph representations. This allows effective functional subgraph detection across different modalities. While previous works focus on subgraph matching within single modality, we are the first work that explore cross-modal subgraph matching. \n\nWe further propose alignment to acquire structure-agnostic and function-invariant embedding. The insight of alignment comes from the property of our proposed functional subgraph relation. Specifically, let's first go back to the definition of Functional Subgraph:\n\n**Definition(Functional Subgraph)**: A graph $\\mathcal{Q}$ is a functional subgraph of $\\mathcal{G}$, denoted $\\mathcal{Q} \\preccurlyeq \\mathcal{G}$, if there exists a graph $\\mathcal{G}'$ such that $\\mathcal{G}' \\equiv_{func} \\mathcal{G}$ and $\\mathcal{Q}$ is isomorphic to a subgraph of $\\mathcal{G}'$.\n\nAccording to the definition, if $Q\\preccurlyeq G_1$ and $G_1\\equiv_{func}G_2$, then $Q\\preccurlyeq G_2$. This denotes that the subgraph relation is preserved under functional equivalence **on the right-hand side** of the relation $\\preccurlyeq$.\n\nIn addition, we proposed a property, Functional Equivalence Preservation, in Section 2.3. \n\n**Proposition(Functional Equivalence Preservation)**: If $\\mathcal{G}_1$ is a functional subgraph of $\\mathcal{G}_2$, and $\\mathcal{G}'_1$ is functionally equivalent to $\\mathcal{G}_1$, then $\\mathcal{G}'_1$ is a functional subgraph of $\\mathcal{G}_2$.\n\nThis property shows that the subgraph relation is preserved under functional equivalence **on the left-hand side** of the relation $\\preccurlyeq$.\n\nThese two results imply that, if the subgraph relation $Q\\preccurlyeq G$ hold, then if we replace $Q$ or $G$ with another functional equivalent graph, the subgraph relation continues to hold. This invariance is the **key insight** for our alignment: the embeddings of functionally equivalent graphs should be aligned, regardless of their structural variations.\n\nLast, we propose an innovative approach for fuzzy boundary identification by formulating the task as a graph segmentation problem rather than a simple input-output classification problem, significantly enhancing boundary continuity and localization accuracy. This also comes from the insight that the clear boundary disappear after transformation. \n\nAs discussed in Q1, previous works like Gamora and ABGNN, focus on identifying exact input/output patterns. When identifying a half adder, Gamora, for instance, requires the root of the subgraph to be a XOR gate. However, after function-preserving transformations, such explicit boundaries may disappear (as discussed in Section 2.4), leading to significant performance degradation for these methods."}, {"review_id": "GlaQRvZTJ0", "reviewer": "Reviewer_Ytof", "summary": "This paper introduces a novel approach called functional subgraph matching to identify logic subgraphs in circuits based on functionality rather than structural isomorphism, addressing challenges posed by synthesis transformations that alter circuit topology. The proposed two-stage multi-modal framework combines functional embeddings and graph segmentation techniques to detect functional subgraphs and identify fuzzy boundaries with high accuracy. Experimental results on standard benchmarks demonstrate significant improvements over traditional structure-based methods", "questions": "Q1. What are the main computational bottlenecks currently preventing scalability to industry-size netlists, and what concrete modifications would be necessary to handle graphs with millions of nodes?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "S1.  The problem studied in the paper is interesting.\nS2.  A two stage algorithm is proposed to address this problem.\nS3. Experiments are conducted to evaluate the proposed algorithms.\n\n\nW1. As stated in Section 5, results are limited to moderately sized circuits. The methodology's ability to scale to very large circuits (millions of gates) — common in industry — is not empirically demonstrated, and concrete plans for achieving this remain high-level.\nW2. The assumption that any node/edge removal changes the circuit's function may not always hold, especially outside the benchmark datasets or when circuit simplification is possible but not legal in ABC. \nW3. While the definitions are carefully formalized and properties stated, there is a lack of theoretical analysis on complexity, guarantees, or failure modes of the learning-based approach, especially compared to existing exact/approximate subgraph methods in graph ML.", "was_revised": true, "final_justification": "The rebuttal address my concerns on the assumption and theoretical analysis.", "rebuttal": "We thank the reviewer for valuable feedback. Here are our answers to the weaknesses and questions.\n\n**Q1: What are the main computational bottlenecks currently preventing scalability to industry-size netlists?**\n\nA1: In fact, computational complexity is not the primary bottleneck. Prior works have proposed training strategies that enable GNN models to scale to graphs with millions of nodes [1,2]. The real bottleneck lies in the nature of the task itself. When scaling to large circuits, we categorize the tasks into two cases:\n1. The target is a large circuit, and the query is also a large or medium circuit\n2. The target is a large circuit, while the query is a small circuit\n\nFor the first case, the bottleneck arises from the functional diversity of large circuits. A small dataset cannot sufficiently cover the wide range of possible designs, leading to out-of-distribution (OOD) scenarios during testing. For example, a circuit with $n$ input and $1$ output could present up to $2^{2^n}$ different functions, making it extremely difficult to capture all functional variations in very large circuits (e.g., those with millions of gates). \n\nTo explore this setting, we collect a medium-sized graph dataset from ForgeEDA, containing circuits with graph sizes ranging from 100 to 10000 nodes. The statistical information of the medium-sized dataset is shown below. \n\n| |Nodes|Edges|Depth|\n|-|-|-|-|\n|$G_{sub}$|$192.1\\pm320.87$|$207.16\\pm354.01$|$27.91\\pm30.08$|\n|$G_{syn}$|$1396.99\\pm1764.63$|$1958.84\\pm2519.23$|$66.48\\pm99.7$|\n|$G_{pm}$|$679.93\\pm851.2$|$1352.96\\pm1703.16$|$21.83\\pm32.6$|\n\n\n\nWe perform functional subgraph detection on this dataset, and the results are shown in Table 1 and 2. Since ABGNN encounters out-of-memory error when encoding graphs with deep logic levels, we do not report its results on this new dataset.\n\nTable 1. Functional Subgraph Detection on $G_{sub} \\to G_{syn}$\n\n| Method | Accuracy | Precision | Recall | F1-score |\n|-|-|-|-|-|\n| NeuroMatch | $51.2_{\\pm3.3}$ | $34.6_{\\pm24.5}$ | $66.7_{\\pm47.1}$ | $45.5_{\\pm32.2}$ |\n| HGCN | $50.0_{\\pm0.0}$ | $16.7_{\\pm23.6}$ | $33.3_{\\pm47.1}$ | $22.2_{\\pm31.4}$ |\n| Gamora | $50.0_{\\pm0.0}$ | $40.0_{\\pm14.1}$ | $66.7_{\\pm47.1}$ | $44.6_{\\pm31.3}$ |\n| Ours | $81.5_{\\pm0.6}$ | $82.7_{\\pm1.1}$ | $79.8_{\\pm1.7}$ | $81.2_{\\pm0.8}$ |\n\n\n\nTable 2. Functional Subgraph Detection on $G_{sub} \\to G_{pm}$\n\n| Method | Accuracy | Precision | Recall | F1-score |\n|-|-|-|-|-|\n| NeuroMatch | $51.0_{\\pm1.2}$ | $33.9_{\\pm24.0}$ | $66.6_{\\pm47.1}$ | $44.9_{\\pm31.8}$ |\n| HGCN | $50.0_{\\pm0.0}$ | $16.7_{\\pm23.6}$ | $33.3_{\\pm47.1}$ | $22.2_{\\pm31.4}$ |\n| Gamora | $50.0_{\\pm0.0}$ | $33.3_{\\pm23.6}$ | $66.7_{\\pm47.1}$ | $44.4_{\\pm31.4}$ |\n| Ours | $78.9_{\\pm1.0}$ | $80.6_{\\pm1.6}$ | $76.3_{\\pm2.7}$ | $78.3_{\\pm1.3}$ |\n\nWhile our method still demonstrates state-of-the-art performance, it shows a significant performance drop (from an F1-score of 95.3% to 81.2%, as shown in Table 1). This result highlights the challenge of scaling to larger circuits. We hope future work will explore and address this challenge.\n\nFor the second case, the bottleneck stems from the extreme size imbalance between the query and the candidate circuit. A candidate may contain millions of gates, while the query contains only a few hundred. In such scenarios, the query may occupy as little as 0.001% of the candidate, creating a highly imbalanced learning problem. Despite prior works[3] in the object detection domain have proposed various strategies to address this type of imbalance, it remains a significant challenge in the graph domain. \n\nHowever, in practice, when the target circuit is very large, a divide-and-conquer strategy is commonly adopted to transform the small–large retrieval task into multiple small–small retrieval tasks. For example, in the case of large sequential circuits, we can partition the design through flip-flops to get much smaller combinational subcircuits. Similarly, HGCN [4] also divide large candidate circuits into smaller subgraphs for independent retrieval. Specifically, if the query circuit is a k-hop graph, HGCN cuts the candidate circuit into  2k-hop subgraphs for subgraph matching. This approach aligns with the original setting of our work.\n\n\n*[1]Fey M, Lenssen J E, Weichert F, et al. Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings[C]//International conference on machine learning. PMLR, 2021: 3294-3304.*\n\n*[2]Zheng Z, Huang S, Zhong J, et al. DeepGate4: Efficient and Effective Representation Learning for Circuit Design at Scale[C]//The Thirteenth International Conference on Learning Representations.*\n\n*[3] Cheng G, Yuan X, Yao X, et al. Towards large-scale small object detection: Survey and benchmarks[J]. IEEE transactions on pattern analysis and machine intelligence, 2023, 45(11): 13467-13488.*\n\n*[4]Li B, Wang S, Chen T, et al. Efficient subgraph matching \nfor fast subcircuit identification[C]//Proceedings of the 2024 ACM/IEEE International Symposium on Machine Learning for CAD. 2024: 1-7.*\n\n**Q2: The assumption that any node/edge removal changes the circuit's function may not always hold, especially outside the benchmark datasets or when circuit simplification is possible but not legal in ABC.**\n\nA2: We acknowledge that Non-trivial Function Assumption may not always hold in other cases, as discussed in Section 5, and it may limit the generalizability of our proposed functional subgraph and corresponding model to other domains.\n\nThe assumption of a non-trivial function is made because, for example, if we consider a function $f(x)$, adding one NOT gate results in $\\lnot f(x)$, and adding two NOT gate results in $\\lnot \\lnot f(x)$. According to our definition, this leads to the result: $f(x)\\preccurlyeq \\lnot f(x)\\preccurlyeq \\lnot \\lnot f(x) \\equiv_{func} f(x)$, which could cause confusion on definition. \n\nTherefore, theoretically, if there exist trivial function in a circuit, we suggest removing these function since it won't impact the circuit's functionality and the subgraph relation, as discussed in Functional Equivalence Preservation property in Section 2.3. \n\nPractically, a better approach would be to send the circuit to ABC to ensure the assumption holds, and then transform it into a graph structure.\n\nWe also hope the future works could address this limitation by introducing a concept with improved completeness.\n\n**Q3: While the definitions are carefully formalized and properties stated, there is a lack of theoretical analysis on complexity, guarantees, or failure modes of the learning-based approach, especially compared to existing exact/approximate subgraph methods in graph ML.**\n\nA3: We appreciate the reviewer’s recognition of our proposed definition and properties. As our method relies on deep learning, providing formal theoretical analysis on guarantees or failure modes is inherently challenging, which is also a common limitation in the deep learning field. \n\nHowever, we conducted empirical evaluations of runtime and memory usage across different methods. The results are summarized below:\n\n\n\n| | NeuroMatch | HGCN | Gamora | ABGNN | Ours |\n|-|-:|-:|-:|-:|-:|\n| ITC99 runtime(s) | 3.7 | 2.1 | 2.3 | 3.1 | 28.3 |\n| ITC99 memory usage(GB) | 4.0 | 0.7 | 0.4 | 0.4 | 1.1 |\n| ITC99 F1-Score(%) | 22.2 | 45.3 | 25.4 | 25.4 | 95.4 |\n| OpenABCD runtime(s) | 3.9 | 2.4 | 2.4 | 3.3 | 29.3 |\n| OpenABCD memory usage(GB) | 3.3 | 0.6 | 0.4 | 0.4 | 0.9 |\n| OpenABCD F1-Score(%) | 22.7 | 23.2 | 44.8 | 3.4 | 92.1 |\n| ForgeEDA runtime(s) | 4.4 | 2.5 | 2.3 | 3.2 | 36.4 |\n| ForgeEDA memory usage(GB) | 6.9 | 1.2 | 0.8 | 0.7 | 1.8 |\n| ForgeEDA F1-Score(%) | 22.2 | 23.1 | 1.0 | 45.5 | 96.0 |\n\n\nWe further evaluated the runtime on heuristics. For the heuristics, such as VF2[1] and RI[2] algorithm, are costly and can sometimes take unexpectedly long time(hours), even for relatively small queries (of size 20), as discussed in previous works[3]. Therefore, to evaluate heuristics, we sample circuits with less than 50 nodes in Forgeeda dataset, and only apply state-of-the-art heuristic, VF3[4] algorithm. VF3 required 480.8 seconds, while our method took 8 seconds, demonstrating that heuristics can be significantly slower than learning-based approaches.\n\n|Method|Runtime (s)|Precision (sub→syn)|Recall (sub→syn)|F1-score (sub→syn)|Precision (sub→pm)|Recall (sub→pm)|F1-score (sub→pm)|\n|-|-|-|-|-|-|-|-|\n|VF3|480.8|100|0.32|0.65|–|–|–|\n|Ours|8|88.5|91.9|90.2|86.4|94.5|90.3|\n\n\n\n\nWhile our method costs a longer runtime compared to other learning-based approaches, we want to emphasize that **optimizing GNN architecture for the runtime or memory usage is not the focus of this work**. Our primary contribution lies in introducing the novel concept of functional subgraph matching and proposing a method that can effectively identify the functional subgraph, while previous works(even heuristics like VF3) struggle with unreliable performance.\n\n*[1]Cordella L P, Foggia P, Sansone C, et al. A (sub) graph isomorphism algorithm for matching large graphs[J]. IEEE transactions on pattern analysis and machine intelligence, 2004, 26(10): 1367-1372.*\n\n*[2]Bonnici V, Giugno R, Pulvirenti A, et al. A subgraph isomorphism algorithm and its application to biochemical data[J]. BMC bioinformatics, 2013, 14(Suppl 7): S13.*\n\n*[3] Lou Z, You J, Wen C, et al. Neural subgraph matching[J]. arXiv preprint arXiv:2007.03092, 2020.*\n\n*[4]Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with VF3 - Carletti V., Foggia P., Saggese A., Vento M. - IEEE transactions on pattern analysis and machine intelligence - 2018*"}, {"review_id": "T0ghxMLtGg", "reviewer": "Reviewer_WZEu", "summary": "The work is situated in the context of electronic design automation. The task they focus on is subgraph matching: detecting whether/where a query graph is present within a larger target graph. They 1) propose an improved definition of this task that also covers transformations on the target graph, essentially more broadly identifying functionally equivalent subgraphs; and 2) propose a two-stage deep learning framework to solve this problem. The empirical evaluation indicates significant improvement compared to prior work.", "questions": "What part of the framework is causing the strong results compared to the competitors (or why do the competitors perform poorly)? Do I understand correctly that they have not been designed to consider functional subgraphs; only subgraph isomorphism or subgraph equivalence, and that partially explains it? Would the competitors perform as well as your method if there were no transformations and the setting was instead a subgraph isomorphism/subgraph equivalence task?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "**Clarity:**\n\nThe work is well structured and includes clear informative figures that help guide the reading process. On a high level, the contributions are very clear. On a more detailed level, I am not sure I understood the deep learning pipeline. For example, what does \"intra-modal and inter-modal alignment\" mean exactly? Are these just the losses of line 201?. Related, more generally, the work often discusses how, but not the why; which may contribute to a reader not understanding why something works.\n\n\nThe work does assume some familiarity with the field: concepts such as netlist, \"And-Inverter Graph\", and \"technology mapping\" are not introduced. However, even without familiarity it is easy to understand the contributions on a high level. \n\n\n\nFurther comments\n* Figure 3 is never referred to.\n\n* Would be good to define the InfoNCE loss function (in the appendix)\n\n\n\n**Originality:** To the best of my knowledge, the work is very original.\n\n\n**Significance:**\n\nTo work is well motivated. In particular, the proposed new task (identifying functional subgraphs) makes a lot of sense, and the empirical results are very strong.\nThe work, which uses a neural pipeline, is relevant to the conference.\n\n\n**Quality:**\nThe work appears sound and the empirical setting appears thorough, demonstrating strong results. As a limitation, they do only test on smaller circuits, and do not yet consider scaling to large-scale graphs. This is correctly discussed in the limitations section.", "was_revised": true, "final_justification": "I confirm having read the other reviews and thank the authors for the rebuttal.\n\nI remain positive about the work for the previously outlined points, and have slightly increased my confidence.\n\nThe main new idea/insight of the paper (the proposed new task of identifying functional subgraphs) is well motivated and poses a useful contribution to the field. The empirical results are strong (although there are challenges in scaling to much larger graphs) and the work is presented clearly.", "rebuttal": "We thank the reviewer for valuable feedback. Here are our answers to the weaknesses and questions.\n\n**Q1:What part of the framework is causing the strong results compared to the competitors? Would the competitors perform as well as your method if there were no transformations and the setting was instead a subgraph isomorphism/subgraph equivalence task?**\n\nA1: Regarding the performance increasing, we provide a more detailed discussion below. Overall, we attribute the improvement in performance to three parts:\n* Task definition\n* Two-stage framework\n* Function learning ability of GNN model\n\n\n**Task Definition** \nTo the best of our knowledge, our work introduces the concept of a functional subgraph for the first time, which differs significantly from subgraph isomorphism and subgraph equivalence, as discussed in Section 2. This difference in definition naturally leads to a different task formulation.\n\nTo further illustrate this, we evaluate the state-of-the-art subgraph isomorphic heuristic algorithm VF3 [1], which consistently achieves 100% precision and 100% recall on standard subgraph isomorphism tasks. Due to time constraints, we sampled circuits with fewer than 50 nodes from the ForgeEDA dataset and applied the VF3 algorithm. The results are shown below:\n\n|Method|Runtime (s)|Precision (sub→syn)|Recall (sub→syn)|F1-score (sub→syn)|Precision (sub→pm)|Recall (sub→pm)|F1-score (sub→pm)|\n|-|-:|-:|-:|-:|-:|-:|-:|\n|VF3|480.8|100|0.32|0.65|–|–|–|\n|Ours|8|88.5|91.9|90.2|86.4|94.5|90.3|\n\nAccording to our Definition 3 of Functional Subgraph, if $Q$ is an isomorphic subgraph of $G$, then $Q$ is always a functional subgraph of $G$. This is demonstrated by the 100% precision achieved by VF3. However, due to the function-preserving transformation, the explicit structure of $Q$ often disappear, leading to extremely low recall(0.32%) for VF3. This result highlight the importance of task definition. \n\n\n\n\n**Two-Stage Framework**\nTable 4 in Section 4.4 discusses the effectiveness of our proposed alignment, two-stage training and graph segmentation. The results demonstrate the effectiveness of each component in our method.\n\nSpecifically, for fuzzy boundary identification, previous works on targeting arithmetic block identification (Subgraph Equivalence), such as Gamora [2] and ABGNN [3], focus on identifying exact input/output patterns. When identifying a half adder, Gamora, for instance, requires the root of the subgraph to be a XOR gate. However, after function-preserving transformations, such explicit boundaries may disappear (as discussed in Section 2.4), leading to significant performance degradation for these methods.\n\nFurthermore, considering that the graph encoder in our method can be replaced with other backbones, we evaluate our approach using alternative encoders designed for function-related tasks and propose several baselines, as shown in Tables 4 and 5 in Appendix B. The results demonstrate that with our proposed framework, these models gain significant performance improvement, indicating the importance of our proposed two-stage framework.\n\n\n**Function learning ability of GNN model** \nPrior works on subgraph isomorphism mainly focus on designing GNN models to learn structural patterns rather than functional behavior. As a result, these models perform poorly on function-related tasks, as discussed in prior studies [4,5]. \n\nFor function-related method, like Gamora and ABGNN, we have integrate these graph encoder into our framework, and the results are as shown in Tables 4 and 5 in Appendix B. Even though with a significant performance improvement, these method still shows a significant performance drop compared to our method, indicating that the GNN architecture also leading to performance gap.\n\n*[1]Carletti et al., “VF3: Challenging the Time Complexity of Exact Subgraph Isomorphism,” IEEE TPAMI, 2018.*\n\n*[2] Wu et al., “Gamora: Graph Learning-Based Symbolic Reasoning for Large-Scale Boolean Networks,” DAC, 2023.*\n\n*[3] Wang et al., “Efficient Arithmetic Block Identification with Graph Learning and Network-Flow,” IEEE TCAD, 2022.* \n\n*[4] Liu et al., “Polargate: Breaking the Functionality Representation Bottleneck of AND-Inverter Graph Neural Network,” ICCAD, 2024.*\n\n*[5] Zheng et al., “DeepGate4: Efficient and Effective Representation Learning for Circuit Design at Scale,” ICLR, 2025.*\n\n**Q2: The work does assume some familiarity with the field: concepts such as netlist, \"And-Inverter Graph\", and \"technology mapping\" are not introduced.**\n\nA2: Thank you for pointing this out. We will add a section in the Appendix to introduce the background concepts for better clarity. Below is a brief introduction to the key terms used in our work:\n* **And-Inverter Graph(AIG)**: In our works, AIG is a directed acyclic graph (DAG) composed of three basic elements: Primary Input(PI), AND gate and NOT gate. For example, a simple logic expression $\\lnot A\\land B$ can be build as a DAG with 2 PIs(A and B), one NOT gate and one AND gate. The edges are $[(A,NOT), (NOT,AND),(B,AND)]$. Since the out-degree of $AND$ is zero, it represents the final output.\n* **Technology Mapping**: This is a function-preserving transformation that converts an AIG into a post-mapping (PM) netlist. While the AIG consists of simple logic elements, such as AND and NOT gates, the basic components in a PM netlist can be more complex, such as adders or multipliers. As a result, node types can differ significantly between the two forms, and this is why we consider AIG and PM netlists as distinct modalities in this paper.\n* **Logic Synthesis**: Logic synthesis aims to simplify the structure of an AIG while preserving its functionality. It transforms one AIG into another with a simpler structure. For example, the expression $eq_1: (A\\land B)\\land(A\\land C)$ can be simplified to $eq_2:A\\land B \\land C$.  Although $eq_1$ and $eq_2$ are functional equivalent, $eq_2$ uses only 2 AND gates compared to 3 AND gates in $eq_1$.\n\n\n**Q3: What does \"intra-modal and inter-modal alignment\" mean exactly? ... the work often discusses how, but not the why**\n\nA3: As discussed in Q2, we treat AIG and PM netlists as different modalities due to their differing node types. In our work, we consider two types of function-preserving transformations: Logic Synthesis and Technology Mapping. \n\nGiven an AIG $G_{aig}$, we apply Logic Synthesis to obtain $G_{syn}$, and Technology Mapping to obtain the PM netlist $G_{pm}$. All three graphs are functionally equivalent.\n\nWe align the embeddings of these functionally equivalent graphs to ensure that their representations remain the same across transformations. This alignment is performed in two ways:\n\n- **Intra-modal alignment**: Aligning embeddings between graphs within the same modality, i.e. between $G_{aig}$ and $G_{syn}$, both of which are AIGs.\n- **Inter-modal alignment**: Aligning embeddings across different modalities, i.e. between $G_{aig}$ (an AIG) and $G_{pm}$ (a PM netlist).\n\nBefore discussing the details of alignment, we would like to clarify its motivation.\n\n\nLet's first go back to the definition of Functional Subgraph:\n\n**Definition(Functional Subgraph)**: A graph $Q$ is a functional subgraph of $G$, denoted $Q \\preccurlyeq G$, if there exists a graph $G'$ such that $G' \\equiv_{func} G$ and $Q$ is isomorphic to a subgraph of $G'$.\n\nAccording to the definition, if $Q\\preccurlyeq G_1$ and $G_1\\equiv_{func}G_2$, then $Q\\preccurlyeq G_2$. This denotes that the subgraph relation is preserved under functional equivalence **on the right-hand side** of the relation $\\preccurlyeq$.\n    \nIn addition, we proposed a property, Functional Equivalence Preservation, in Section 2.3. \n\n**Proposition(Functional Equivalence Preservation)**: If $G_1$ is a functional subgraph of $G_2$, and $G'_1$ is functionally equivalent to $G_1$, then $G'_1$ is a functional subgraph of $G_2$.\n\nThis property shows that the subgraph relation is preserved under functional equivalence **on the left-hand side** of the relation $\\preccurlyeq$.\n\nThese two results imply that, if the subgraph relation $Q\\preccurlyeq G$ hold, then if we replace $Q$ or $G$ with another functional equivalent graph, the subgraph relation continues to hold. This invariance is the key motivation for our alignment: the embeddings of functionally equivalent graphs should be aligned, regardless of their structural variations.\n\nThe equation in line 201 in our paper shows the details of alignment. Since the modality of PM-netlist is different from AIG, we divide the alignment into two parts: (1)intra-modal alignment: AIG-AIG embedding alignment (2)inter-modal  alignment: AIG-PM embedding alignment.\n\nSpecifically, given embedding $[f_{aig}^+,f_{syn}^+,f_{syn}^-]$, $f_{aig}^+$ and $f_{syn}^+$ are functional equivalent, thus, following the idea of contrastive learning,  we aim to minimize the distance of $f_{aig}^+$ and $f_{syn}^+$. Similarly, $f_{aig}^+$ and $f_{syn}^-$ are functional unequivalent, thus we aim to maximize the distance of $f_{aig}^+$ and $f_{syn}^-$. For $[f_{aig}^+,f_{pm}^+,f_{pm}^-]$, we apply the same contrastive objective.\n\nThis approach allows us to enforce functional similarity in the learned embedding space, which is essential for robust functional subgraph detection across structural transformations.\n\n**Q4: Figure 3 is never referred to. Would be good to define the InfoNCE loss function (in the appendix)**\n\nA4: Thanks for your suggestion. We will revise the final version to refer to Figure 3 in the main text and include a formal definition of the InfoNCE loss function in the appendix for completeness."}, {"review_id": "2Pz4owwCz2", "reviewer": "Reviewer_tTFV", "summary": "The paper presents a novel concept of functional subgraph matching, enabling the identification of implicit logic functions within larger circuits. The proposed two-stage process, which combines intra-modal and inter-modal alignment with graph segmentation for boundary identification, offers a unique perspective on addressing circuit optimization, verification, and security analysis challenges in EDA applications, and has achieved best subgraph matching accuracy in multiple tasks.", "questions": "1. Please list the scale of each evaluated dataset, show the runtime and correpsonding computational cost of each method\n2. Comparing to more different subgraph matching algorithms instead of GNNs\n3. Add more experiments on medium to large graph datasets.", "limitations": "See questions", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper presents a novel concept of functional subgraph matching, enabling the identification of implicit logic functions within larger circuits. The proposed two-stage process, which combines intra-modal and inter-modal alignment with graph segmentation for boundary identification, offers a unique perspective on addressing circuit optimization, verification, and security analysis challenges in EDA applications, and has achieved best subgraph matching accuracy in multiple tasks. \nWeaknesses:\n1. Experiment scale is not enough\n2. subgraph matching application is limited\n3. Experiments comparisons limited to GNNs, but less on other subgraph matching methods.", "was_revised": true, "final_justification": "The author's rebuttal is insightful, and the paper is above the acceptance threshold.", "rebuttal": "We thank the reviewer for valuable feedback. Here are our answers to the weaknesses and questions.\n\n**Q1:Please list the scale of each evaluated dataset, show the runtime and corresponding computational cost of each method**\n\nA1: Thank you for the suggestion. The scale of each evaluated dataset is provided in Table 6 in Appendix. In addition, we report the runtime and GPU memory consumption for each method across all datasets:\n\n| |NeuroMatch|HGCN|Gamora|ABGNN|Ours|\n|-|-:|-:|-:|-:|-:|\n|ITC99 runtime(s)|3.7|2.1|2.3|3.1|28.3|\n|ITC99 memory usage(GB)|4.0|0.7|0.4|0.4|1.1|\n|ITC99 F1-Score(%)|22.2|45.3|25.4|25.4|95.4|\n|OpenABCD runtime(s)|3.9|2.4|2.4|3.3|29.3|\n|OpenABCD memory usage(GB)|3.3|0.6|0.4|0.4|0.9|\n|OpenABCD F1-Score(%)|22.7|23.2|44.8|3.4|92.1|\n|ForgeEDA runtime(s)|4.4|2.5|2.3|3.2|36.4|\n|ForgeEDA memory usage(GB)|6.9|1.2|0.8|0.7|1.8|\n|ForgeEDA F1-Score(%)|22.2|23.1|1.0|45.5|96.0|\n\n\n\nThe runtime and memory usage primarily rely on the GNN architecture. While our method costs a longer runtime compared to other learning-based approaches, we want to emphasize that **optimizing GNN architecture for the runtime or memory usage is not the focus of this work**. Our primary contribution lies in introducing the novel concept of functional subgraph matching and proposing a method that can effectively identify the functional subgraph, while previous works struggle with unreliable performance.\n\n**Q2:Comparing to more different subgraph matching algorithms instead of GNNs**\n\nA2: To the best of our knowledge, we are the first to propose the concept of the functional subgraph and formally define the tasks of functional subgraph detection and fuzzy boundary identification. As a result, **no existing subgraph matching algorithms are directly applicable to functional subgraph matching**. \n\nWe provide a Python-style pseudocode for a naive algorithm based on our definition:\n\n```\ndef functional_subgraph_matching(Q,G):\n    \"\"\"\n    Q:Query graph \n    G: Candidate graph\n    \"\"\"\n    candidate_list = find_all_functional_equivalent_graph(G)\n    for G_prime in candidate_list:\n        if is_subgraph_isomorphic(Q,G_prime):\n            return True\n    return False\n```\nIn this algorithm, `is_subgraph_isomorphic(Q,G)` can be implemented with heuristic algorithm like VF3[1]. However, the key challenge lie in  `find_all_functional_equivalent_graph(G)`. For example, in the case of an n-bit prefix adder, the number of possible designs is  $\\frac{1}{n}\\tbinom{2(n-1)}{n-1}$, which implies that the complexity for find all equivalent graphs is $O(\\frac{4^n}{n^{3/2}})$. Therefore, it's impossible to list all the functional equivalent graph for a circuit, and thus we cannot compare with this naive algorithm. This highlights the necessity of designing heuristic algorithms for this process.\n\nMoreover, directly applying heuristics on structural subgraph isomorphism to functional subgraph matching leads to many failure cases, as discussed in Section 2. We further conducted an empirical study to illustrate this limitation.\n\nTo evaluate heuristics, we sample circuits with less than 50 nodes in ForgeEDA dataset, and only apply the state-of-the-art heuristic algorithms, VF3[1], since other algorithm could be extremely time-costing as discussed in previous works[2]. The result is list below:\n| Method | Runtime (s) | Precision (sub→syn) | Recall (sub→syn) | F1-score (sub→syn) | Precision (sub→pm) | Recall (sub→pm) | F1-score (sub→pm) |\n|-|-:|-:|-:|-:|-:|-:|-:|\n| VF3  | 480.8 | 100 | 0.32 | 0.65 | –   | –   | –    |\n| Ours | 8.0  | 88.5 | 91.9 | 90.2 | 86.4 | 94.5 | 90.3 |\n\nAccording to our Definition 3 of Functional Subgraph, if $Q$ is a isomorphic subgraph of $G$, then $Q$ is always a functional subgraph of $G$. This is demonstrated by the 100% precision achieved by VF3. However, due to the function-preserving transformation, the explicit structure of $Q$ often disappear, leading to extremely low recall(0.32%) for VF3.\n\n*[1] Carletti et al., “VF3: Challenging the Time Complexity of Exact Subgraph Isomorphism,” *IEEE TPAMI*, 2018.*\n\n*[2] Lou et al., “Neural Subgraph Matching,” *arXiv*, 2020.*\n\n**Q3:Experiment scale is not enough. Add more experiments on medium to large graph datasets**\n\n\nA3: Thank you for your suggestion. When scaling to large circuits, we categorize the tasks into two cases:\n1. The target is a large circuit, and the query is also a large or medium circuit\n2. The target is a large circuit, while the query is a small circuit\n\nFor the first case, the bottleneck arises from the functional diversity of large circuits. A small dataset cannot sufficiently cover the wide range of possible designs, leading to out-of-distribution scenarios during testing. For example, a circuit with $n$ input and $1$ output could present up to $2^{2^n}$ different functions, making it extremely difficult to capture all functional variations in very large circuits (e.g., those with millions of gates). \n\nTo explore this setting, we collect a medium-sized graph dataset from ForgeEDA, containing circuits with graph sizes ranging from 100 to 10000 nodes. The statistic information of the medium-sized dataset is shown below. \n\n| |Nodes|Edges|Depth|\n|-|-|-|-|\n|$G_{sub}$|$192.1\\pm320.87$|$207.16\\pm354.01$|$27.91\\pm30.08$|\n|$G_{syn}$|$1396.99\\pm1764.63$|$1958.84\\pm2519.23$|$66.48\\pm99.7$|\n|$G_{pm}$|$679.93\\pm851.2$|$1352.96\\pm1703.16$|$21.83\\pm32.6$|\n\n\nWe perform functional subgraph detection on this dataset, and the results are shown in Table 1 and 2. Since ABGNN encounters out-of-memory error when encoding graphs with deep logic levels, we do not report its results on this new dataset.\n\nTable 1. Functional Subgraph Detection on $G_{sub} \\to G_{syn}$\n\n|Method|Accuracy|Precision|Recall|F1-score|\n|-|-|-|-|-|\n|NeuroMatch|$51.2_{\\pm3.3}$|$34.6_{\\pm24.5}$|$66.7_{\\pm47.1}$|$45.5_{\\pm32.2}$|\n|HGCN|$50.0_{\\pm0.0}$|$16.7_{\\pm23.6}$|$33.3_{\\pm47.1}$|$22.2_{\\pm31.4}$|\n|Gamora|$50.0_{\\pm0.0}$|$40.0_{\\pm14.1}$|$66.7_{\\pm47.1}$|$44.6_{\\pm31.3}$|\n|Ours|$81.5_{\\pm0.6}$|$82.7_{\\pm1.1}$|$79.8_{\\pm1.7}$|$81.2_{\\pm0.8}$|\n\n\n\nTable 2. Functional Subgraph Detection on $G_{sub} \\to G_{pm}$\n\n|Method|Accuracy|Precision|Recall|F1-score|\n|-|-|-|-|-|\n|NeuroMatch|$51.0_{\\pm1.2}$|$33.9_{\\pm24.0}$|$66.6_{\\pm47.1}$|$44.9_{\\pm31.8}$|\n|HGCN|$50.0_{\\pm0.0}$|$16.7_{\\pm23.6}$|$33.3_{\\pm47.1}$|$22.2_{\\pm31.4}$|\n|Gamora|$50.0_{\\pm0.0}$|$33.3_{\\pm23.6}$|$66.7_{\\pm47.1}$|$44.4_{\\pm31.4}$|\n|Ours|$78.9_{\\pm1.0}$|$80.6_{\\pm1.6}$|$76.3_{\\pm2.7}$|$78.3_{\\pm1.3}$|\n\n\nWhile our method still demonstrates SOTA performance, it shows a significant performance drop. This result highlights the challenge of scaling to larger circuits. We hope future work will explore and address this challenge.\n\nFor the second case, the bottleneck stems from the extreme size imbalance between the query and the candidate circuit. A candidate may contain millions of gates, while the query contains only a few hundred, creating a highly imbalanced learning problem. Despite prior works[3] in the object detection domain have proposed various strategies to address this type of imbalance, it remains a significant challenge in the graph domain. \n\nHowever, in practice, when the target circuit is very large, a **divide-and-conquer strategy** is commonly adopted to transform the small–large retrieval task into multiple small–small retrieval tasks. For example, in the case of large sequential circuits, we can partition the design through flip-flops to get much smaller combinational subcircuits. Similarly, if the query circuit is a k-hop graph, HGCN[4] cuts the candidate circuit into  2k-hop subgraphs for subgraph matching. This approach aligns with the original setting of our work.\n\nWe further summarize the scale of datasets used in prior works and our study in the table below. In fact, due to the np-complete nature of subgraph isomorphism, most of methods on subgraph isomorphism works on small datasets. For example, COX2, DD, MSRC_21, FIRSTMMDB, ENZYMES and SYNTHETIC are datasets used in NeuroMatch. 2-hop,3-hop,4-hop and 5-hop are datasets used in HGCN. And the remaining datasets are used in our works.\n\n|Dataset|Target Size (nodes)|Target Depth|Query Size (nodes)|Query Depth|\n|--|--:|--:|--:|--:|\n|COX2|41.6|-|22.4|-|\n|DD|30.0|-|17.8|-|\n|MSRC_21|79.6|-|22.6|-|\n|FIRSTMMDB|30.0|-|17.8|-|\n|ENZYMES|35.7|-|17.4|-|\n|SYNTHETIC|30.2|-|17.5|-|\n|2-hop|-|4|15.65|2|\n|3-hop|-|6|40.5|3|\n|4-hop|-|8|73.1|4|\n|5-hop|-|10|180.5|5|\n|ITC99|315.4|17|248.0|15|\n|OpenABCD|198.1|16|155.0|13|\n|ForgeEDA|156.5|16.4|126.0|13.6|\n\n\n*[1] Fey et al., “GNN-AutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings,” *ICML*, 2021.*\n\n*[2] Zheng et al., “DeepGate4: Efficient and Effective Representation Learning for Circuit Design at Scale,” *ICLR*, 2025.*\n\n*[3] Cheng et al., “Towards Large-Scale Small Object Detection: Survey and Benchmarks,” *IEEE TPAMI*, 2023.*\n \n*[4] Li et al., “Efficient Subgraph Matching for Fast Subcircuit Identification,” *MLCAD*, 2024.*\n\n\n**Q4:subgraph matching application is limited**\n\nA4: We acknowledge the reviewer's concern and would like to emphasize that functional subgraph matching **has broader application on circuit optimization, verification, and security analyses**, as discussed on our Introduction Section. \n\nIn addition to these applications, our proposed functional subgraph can also be applied to other tasks. For example, in the Engineering Change Order (ECO)[1,2], a critical process of hardware development, there are situations circuit designers would need to extract complicated arithmetic circuitry deeply embedded inside a fully optimized flattened netlist without the knowing of module boundary and IO positions. The extracted results can then be used for replacement by more advanced intellectual property (IP) macros.\n\n*[1] Wei et al., “Universal Macro Block Mapping for Arithmetic Circuits,” *DATE*, 2015.*\n\n*[2] Diao et al., “Coupling Reverse Engineering and SAT for Arithmetic Circuit Verification,” *ASP-DAC*, 2016.*"}]

Author rebuttal:

Meta-review: The paper introduces an approach called functional subgraph matching to identify logic subgraphs in circuits based on functionality rather than structural isomorphism. All the reviewers agreed that the problem is well-motivated, the proposed approach is novel, and the empirical evaluations are thorough. Overall, this paper is well written and easy to follow, and the idea of functional subgraph matching is valuable for this community. The authors' rebuttal addressed most of the concerns of reviewers, and all the reviews tend to accept the paper during the reviewer-author discussion phase. Therefore, I recommend this paper to the NeurIPS 2025 conference.
Decision: Accept (poster)