Response to Reviewer kVA7

We thank the reviewer for the insightful and valuable comments. We respond to each comment as follows and sincerely hope that our rebuttal can properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.

Weakness 1

The term "circuit synthesis" is unclear in EDA and may cause confusion; this paper seems to focus on logic optimization based on related works and experiments.

Thanks for your valuable comments. In our initial draft, we followed previous works [1][2][3][4] in adopting the term "Circuit Synthesis" as a more accessible alternative to "Logic Synthesis" to enhance readability for non-experts in the field." In general, Logic Synthesis consists of three main stages: translation, logic optimization, and technology mapping. As you insightfully mentioned, our work mainly focuses on logic optimization and it is more proper to use logic optimization rather than circuit synthesis. Therefore, to ensure accuracy and clarity, we have replaced "Circuit Synthesis" with "Logic Optimization" in the first revision.

[1]. Wang Z et al. Towards Next-Generation Logic Synthesis: A Scalable Neural Circuit Generation Framework. The Thirty-eighth Annual Conference on Neural Information Processing Systems. 2024.

[2]. Chowdhury, et al. Openabc-d: A large-scale dataset for machine learning guided integrated circuit synthesis. arXiv preprint arXiv:2110.11292, 2021.

[3]. Scarabottolo I, Ansaloni G, Constantinides G A, et al. Approximate logic synthesis: A survey. Proceedings of the IEEE, 2020, 108(12): 2195-2213.

[4]. Buch, et al. Logic synthesis for large pass transistor circuits. 1997 Proceedings of IEEE International Conference on Computer Aided Design (ICCAD). IEEE, 1997: 663-670.

Weakness 2 & Question 3

How are the training dataset labels obtained? When mentioning node-level transformation, does it mean it is effective for the current step of logic optimization or for overall performance? Effectiveness in the current step may not translate to overall performance in logic optimization

The node label $y$ is collected based on the effectiveness of the node-level transformation. If the node-level transformation is effective at the node $**x**$, then $y=1$. Otherwise, $y=0$.

The effectiveness of a node-level transformation is determined by whether the heuristic can optimize the current local subgraph (i.e., reducing the subgraphs nodes). While some locally effective nodes may influence overall optimization performance, others may not. However, the proportion of locally effective nodes that fail to contribute to overall performance is sufficiently small, so labeling these nodes as positive has no significant impact efficiency. Moreover, applying node-level transformations on these nodes will not degrade the final optimization performance. Therefore, it is reasonable and simple to label nodes based on the local effectiveness of the node-level transformations.

Weakness 3.1

The focus of logic optimization should be on time cost and node reduction during the online phase. The offline phase appears more like an ablation study.

Thanks for your valuable comments. Our CMO framework consists of two phases: the offline phase and the online phase. In the offline phase, we formulate the logic optimization (LO) task as a machine learning (ML) problem---learning a model from the training dataset that can accurately predict ineffective nodes on unseen circuits. The offline metric---prediction recall, which serves as a proxy for the online optimization performance---is used to access the generalization capability of the learned models from the ML perspective. In the online phase, the CMO uses the learned model to predict ineffective nodes on unseen circuits and avoid transformations on these nodes to accelerate the X heuristic. The online generalization metrics---runtime and node reduction---are used to evaluate the efficiency and generalization optimization performance of the heuristic X-Mfs2 from th EDA perspective.

In Experiment 1, the offline results are used to show the superior generalization performance of our CMO. In terms of online results, we mainly focus on time cost and node reduction as you suggested. Specifically, We present the online results in Figure 4 and Table 6 in the initial submission. Table 6 is provided in Appendix C.3 due to limited space. For your convenience, we have included Table 6 below. The results show that our CMO significantly outperforms the baselines in terms of efficiency while achieving comparable optimization performance with the GPU-based SOTA methods COG.

Weakness 3.2

Experiments on generalization should be highlighted in the main part of the manuscript.

Thanks for your valuable comments. According to your suggestion, we have revised the experiment section in the first revision (Line 454) by removing the generalization results in Experiment 4 and organizing all the generalization comparison results in Experiment 1 to better emphasize the generalization evaluation in the main part. For your convenience, we summarize the adjusted experiment sections as follows:

• Experiment 1. To demonstrate the superior performance of our CMO in terms of generalization performance and efficiency.
• Experiment 2. To demonstrate that our approach can not only prompt the efficiency of the Mfs2 heuristic but also improve the Quality of Results (QoR).
• Experiment 3. Perform carefully designed ablation studies to provide further insight into CMO.
• Experiment 4. To show the appealing features of CMO in terms of generalization capability per inference efficiency and interpretability.

Weakness 3.3

Experiment 4 should showcase generalization compared to other baselines like COG, but why other SR methods? Is this an ablation study of the SR method used?

We sincerely apologize for the confusion caused by our experiment setting. The five lightweight methods discussed in Experiment 4 are baselines for generalization and efficiency evaluation in Experiment 1, rather than being part of the ablation studies.

Specifically, we have mentioned in 'Evaluation Metrics and Evaluated Methods' that, in the offline and online phase, we compare our CMO with the other five lightweight baselines (Line 372 in the initial submission) to provide a more comprehensive comparison. However, these comparisons were not appropriately placed in the correct section of the Experiment.

To clarify this misunderstanding, we have removed the "High Generalization Performance" section from Experiment 4 and incorporated the comparison results with these lightweight methods into Experiment 1. The updated results for the generalization and online heuristics efficiency comparisons are now presented in Tables 8 and 9 in the Appendix of the first revision. For your convenience, we have included the tables below:

Table 8: We compare our CMO with five lightweight baselines. The results demonstrate that our approach outperforms all of the baselines in terms of generalization capability.

Dear Reviewer kVA7,

We are truly grateful for your kind support and the time you've taken to review and assess our work. Your wiilingness to consider raising the score means a great deal to us and gives us further confidence in the value of our contributions. According to your suggestions, we will retain the revisions in the manuscript to make them clear.

Best,

Authors

Response to Reviewer oLyS

We thank the reviewer for the insightful and valuable comments. We respond to each comment as follows and sincerely hope that our rebuttal can properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.

Weakness 1.

Provide some deeper explanation and theoretical analysis on why combining GNN, MCTS, and symbolic learning leads to better results.

Thanks for your valuable comments. To offer a deeper explanation of why the combination of GNN, MCTS, and symbolic learning leads to improved results, we break the analysis down into the following four steps:

Step 1. We provide a theoretical analysis of how the teacher GNN model addresses the circuit generalization problem in our CS task.

The GNN addresses the circuit generalization problem by designing multi-domain circuit datasets for training and learning domain-invariant information (i.e., inductive bias) from well-constructed subgraphs. Specifically, [1] first discovers that the large distribution shift between different circuits makes it challenging for models trained on training circuits to generalize to the unseen circuits. To address this problem, [1] provides a theorem for the generalization error bound between the average risk $\mathcal{R}(f)$ over all possible target circuit domains and the empirical risk estimation objective $\hat{\mathcal{R}}(f)$ on the training circuit domains. A circuit domain refers to the underlying distribution from which circuits are sampled.

Theorem 1: Under some mild and reasonable assumptions, the following inequality holds with probability at least 1 - $\delta$

$\left(\sup\_{f}\lvert \mathcal{R}(f)-\hat{\mathcal{R}}(f) \rvert \right)^2 \leq \vphantom{\frac{C_4}{M^2}\sum_{k=1}^M\frac{1}{n_k}}\frac{C_1 \log \delta^{-1}+C_2}{M} + \frac{C_3\log 2\delta^{-1}M+C_4\log \delta^{-1}+C_5}{M^2}\sum_{k=1}^M\frac{1}{n_k}$

where $C_1, C_2, C_3, C_4, C_5$ are constants, $M$ is the number of training circuit domains and $n_k$ is the sample size of the $k$-th training circuit domain. In our CS task, the total number of the training samples $n = \sum_{k=1}^M{n_k}$ is a constant. Based on Theorem 1, we derive the following corollary:

Corollary 1: Under the condition $n_k = \frac{n}{M} \text{ for } k = 1, 2, \cdots, M$ and $1 \leq M \leq \frac{C_1\log\delta^{-1}+C_2} {C_3\log2\delta^{-1}} \cdot n$, using domain-wise training circuit datasets (i.e., M > 1) will result in a smaller generalization error bound than just pooling them in one mixed dataset (i.e., M=1). The proof is provided below:

We represent the generalization error bound in Theorem 1 as a function on discrete variable $M$

$

    B(M) = \frac{C_1 \log \delta^{-1}+C_2}{M}+ \frac{C_3\log 2\delta^{-1}M}{n}+\frac{C_4\log \delta^{-1}+C_5}{n}\quad(M \geq 1)\nonumber

$

where $n$ representing the total number of samples is a constant and $M$ denotes the number of domains. To prove the corollary, we just need to prove that $B(1) \geq B(M) \text{ for } M \geq 1$. Consequently, under the condition, we have:

$

    &1 \leq M \leq \frac{C_1\log\delta^{-1}+C_2}{C_3\log2\delta^{-1}} \cdot n \\\\
    \Rightarrow &\frac{C_3\log{2\delta^{-1}}}{n}(1-M) - \frac{C_1\log\delta^{-1}+C_2}{M}(1-M) \geq 0 \\\\
    \Rightarrow&B(1) \geq B(M) \quad (M \geq 1)\nonumber

$

Based on Collary 1, we design a multi-domain circuits datasets to train the GNN model for enhanced generalization capability. In this paper, circuits with similar functionalities, such as arithmetic, control, and memory, are grouped into distinct circuit domains.

Moreover, the GNN model achieves high generalization capability by learning domain-invariant information (i.e., inductive bias). Specifically, [1] observed that the effectiveness of a node-level transformation is closely linked to the local subgraph rooted at the node, regardless of the circuit to which the node belongs. Based on this observation, they proposed extracting subgraphs rooted at individual nodes to generate node embeddings that capture inductive biases. These embeddings are capable of learning domain-invariant representations, thereby enabling the model to generalize effectively to unseen circuits. In this work, we follow [1] to train a GNN model with a strong inductive bias.

Step 2. We empirically show that our GESD framework can enhance different kinds of symbolic learning methods. To evaluate whether GESD can effectively enhance symbolic learning methods, we combine GESD with three different symbolic learning methods. Specifically, we select classical genetic programming-based SR method --- GPLearn [2], a state-of-the-art (SOTA) deep learning-based SR method --- DSR [3], and an MCTS-based SR method --- CMO (ours) as backend symbolic learning methods. The results in Table a show that our GESD significantly improves the generalization performance of all symbolic learning methods on six challenging open-source circuits.

Table a: G-X means combining GNN and the X symbolic learning method. The results demonstrate the effectiveness of our GESD framework can effectively enhance different kinds of symbolic learning methods.

Step 3. We analyze how the symbolic learning method benefits from the GESD framework. Our GESD enhances the generalization capability of the symbolic function by transferring the domain-invariant information (i.e., inductive bias) learned by the graph model into the symbolic function. Specifically, we have shown in Step 1 that the teacher GNN achieves high generalization capability through capturing domain-invariant information from well-constructed circuit subgraphs. To verify whether our GESD effectively incorporates this information into the symbolic searching process, we compute the KL divergence between the soft labels generated by the teacher GNN and the outputs of the learned symbolic functions. The results in Table b demonstrate that our GESD enables the student symbolic learning method to effectively learn and compensate for the missing inductive bias. Therefore, the GESD helps address the circuit symbolic generalization problem.

Table b: We compute the KL divergence between the teacher GNN model and two variants: our CMO and CMO without GESD. The results reveal that the KL divergence between the GNN and CMO is significantly smaller than that between the GNN and CMO without GESD, demonstrating GESD's effectiveness in distilling inductive bias.

Dear Reviewer oLys,

We are truly grateful for your kind support and the time you've taken to review and assess our work. Your willingness to consider raising the score means a great deal to us and gives us further confidence in the value of our contributions.

We would like to gently remind you that ICLR's scoring system does not include a score of 7, and the next available score above 6 is 8. In other AI conferences such as NeurIPS and ICML, a score of 7 typically corresponds to an "accept", which is equivalent to a score of 8 at ICLR. Therefore, if our responses have adequately addressed your concerns, we sincerely hope you might consider raising the score to 8 (accept) within the available range. We summarize our responses below.

• Theoretical and empirical analysis of combining GNN, MCTS, and symbolic learning. We provide both theoretical and empirical evidence to justify the integration of GNN, MCTS, and symbolic learning in our method. Theoretically, we demonstrate that leveraging multi-domain circuit training datasets significantly reduces the generalization error bound of the teacher GNN model. Empirically, we show that the Graph Enhanced Symbolic Discovery (GESD) framework, which combines the teacher GNN with a student symbolic learning model, enhances the generalization ability of the symbolic function by transferring domain-invariant knowledge (i.e., inductive bias) from the graph model to the symbolic function. Additionally, our experiments highlight the superior performance of MCTS over classical symbolic learning methods in terms of both generalization capability and training efficiency. These analyses illustrate the rationale for integrating GNN, MCTS, and symbolic learning. Moreover, this combination enables our method to discover a generalizable, lightweight, and interpretable symbolic function.

• Some of the writings can be improved. We sincerely appreciate your valuable feedback on improving the clarity of our writing. We have carefully revised the unclear statements in the revised version.

• Technical errors. We sincerely appreciate you for pointing out the technical errors and we have carefully addressed and corrected in the revised version.

• More circuit dataset descriptions and graph visualization. We have included detailed statistics for circuits from two open-source and one industrial benchmark in Tables 11–14 of the rebuttal. Additionally, we added graph visualizations in the revised version under Appendix D.4 (Line 910, Figure 7) titled "Visualization of the Circuit Graph."

Once again, thank you for your constructive suggestions and for considering our work so thoughtfully. Your feedback has been instrumental in helping us improve!

Best,

Authors

Response to Reviewer s1pC

We thank the reviewer for the insightful and valuable comments. We respond to each comment as follows and sincerely hope that our rebuttal can properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.

Weakness 1.

The link between the two methods in sections 4.1 and 4.2 needs to be further elucidated, and it is not currently possible to visualize in the text the specific interrelationships between the two methods.

Thanks for your valuable comments. The relationship between the two approaches described in Sections 4.1 and 4.2 is as follows: The GESD framework discussed in Section 4.2 is the detailed description of the structural and semantic function learning component outlined in Figure 2 of Section 4.1 . To provide clearer clarification of the connection between Sections 4.1 and 4.2, we have updated Figure 2 by changing the label 'semantic/structural function learning' to 'GESD for semantic/structural function learning.' Additionally, we added a textual description in Section 4.1 of the first revision (line 241) to explain how GESD works in our CMO framework. For your convenience, we have included the relevant supplementary content from Section 4.1 below.

GESD for Symbolic Function Learning After decomposing the init feature into structural and semantic components, we collect structural data $\mathcal{D}\_{str} = \lbrace**x**\_i^{str}, y_i\rbrace_{i=1}^N$ and semantic data $\mathcal{D}\_{sem} = \lbrace**x**\_i^{sem}, y_i\rbrace_{i=1}^N$, where $**x**\_i^{str}$ refers to structural node feature and $**x**\_i^{sem}$ refers to semantic node feature. To capture structural information, we employ our Graph Enhanced Symbolic Discovery (GESD) framework to learn a mathematical symbolic function $f^{str}: \mathbf{R}^{d} \to \mathbf{R}$ (see Section 4.2), as the values of structural features can be approximated as continuous data, making them suitable for continuous mathematical symbolic regression. In contrast, learning mathematical functions for semantic information is challenging due to the discrete and binary nature of both feature values and labels. Thus, to capture semantic information, we formulate the semantic function as a Boolean symbolic learning problem, i.e., employing our GESD framework to learn a boolean function $f^{sem}: \mathbf{B}^{d} \to \mathbf{B}$ (see Section 4.2) that can accurately identify the effective nodes, where $\mathbf{B} = \lbrace 0,1 \rbrace$ denotes the boolean feature domain.

# The offline training algorithm
def training(D, f_GNN):
    """
    Input: 
        Training dataset D
        The trained GNN model f_GNN
    Output: 
        Semantic function f_sem, Structural function f_str
    """

    # Step 1: Separate the initial dataset into structural and semantic data
    D_str = extract_structural_data(D)  # Extract structural data from D
    D_sem = extract_semantic_data(D)    # Extract semantic data from D

    # Step 2: Learn the structural function using GESD
    f_str = GESD(D_str, f_GNN)

    # Step 3: Learn the semantic function using GESD
    f_sem = GESD(D_sem, f_GNN)

    return f_str, f_sem

# The GESD algorithm
def GESD(D, f_GNN)
    """

    Input:
        The structural/semantic training dataset D
        The trained GNN model f_GNN
    Output:
        Optimal function f*
    """

    for episode in range(num_episodes):  # Repeat for each episode
        # Selection phase
        s_t = []  # Initialize state as empty
        t = 0  # Initialize step counter
        while is_expandable(s_t) and t < t_max:
            a_t_plus_1 = select_action_with_uct(s_t)  # Select action using UCT
            s_next, NT = take_action(s_t, a_t_plus_1)  # Perform action and observe next state
            s_t = s_next  # Update state
            mark_as_visited(s_t)  # Mark state as visited
            t += 1  # Increment step counter

        # Expansion phase
        a = select_unvisited_action(s_t)  # Randomly select an unvisited action
        s_next = take_action_randomly(s_t, a)  # Perform action and observe next state
        s_t = s_next  # Update state
        mark_as_visited(s_t)  # Mark state as visited
        t += 1  # Increment step counter

        # Simulation phase
        for _ in range(num_simulations):  # Run multiple simulations
            s_sim = s_t  # Fix the starting point
            t_sim = t  # Initialize simulation step counter
            while not is_terminal(s_sim) and t_sim < t_max:
                a_sim = select_random_action(s_sim)  # Randomly select an action
                s_next_sim = take_action_randomly(s_sim, a_sim)  # Perform action
                s_sim = s_next_sim  # Update state
                t_sim += 1  # Increment simulation step counter

            if forms_complete_expression_tree(s_sim):  # Check if expression tree is complete
                f = project_function(s_sim)  # Project function
                y_pred = f(D.x)  # Calculate function prediction
                z_pred = f_GNN(D.x)  # Calculate GNN prediction
                reward = calculate_reward(
                    y_pred, D.y, z_pred, lambda_param, eta
                )  # Compute reward

        # Backpropagation phase
        backpropagate_simulation_results(s_t, reward)  # Propagate simulation results and update counts

    return f*  # Return the optimal function

# The online scores calculation algorithm
def inference_process(D_test, f_str, f_sem):
    """
    Input:
        test_dataset D_test
        structural_function f_str
        semantic_function f_sem
    Output:
        scores s: final scores for all nodes in the test dataset
    """

    # Step 1: Separate the initial dataset into structural and semantic data
    D_str = extract_structural_data(D_test)  # Extract structural data from D
    D_sem = extract_semantic_data(D_test)    # Extract semantic data from D

    # Step 2: Calculate structural and semantic scores
    s_str = [
        f_str(x_str) for x_str, _ in D_str
    ]
    semantic_scores = [
        f_sem(x_sem) for x_sem, _ in D_sem
    ]

    # Step 3: Calculate the weight as the median of structural scores
    w = median(s_str)

    # Step 4: Calculate final scores
    s = [
        s_str^i + weight * s_sem^i
        for s_str, s_sem in zip(s_str, s_sem)
    ]

    return final_scores