Physics-constrained Graph Symbolic Regression

Authors: Ziyu Xiang, Kenna Ashen, Xiaofeng Qian, Xiaoning Qian
Primary area: applications to physical sciences (physics, chemistry, biology, etc.)
Keywords: Symbolic Regression, Physics-constrained, Graph Neural Network, Reinforcement Learning, Monte-Carlo Tree Search, Expression Tree, Automated Feature Engineering, Symbolic Graph

Abstract:
As data-driven scientific discovery increasingly demands explainable over ‘black-box’ machine learning (ML) methods, Symbolic Regression (SR) that derives analytical expressions can help identify key functional dependencies in complex systems. However, traditional SR methods often suffer from (a) inefficient exploration due to their inability to compress the search space of equivalent expressions, and (b) non-physical solutions that violate fundamental physics constraints. We here introduce a symmetric invariant representation of candidate analytical expressions using a Symbolic Graph (SG), on which the Symbolic Graph Neural Network (SGNN) encodes operators, symmetries,   constraints and constant fitting knowledge. We further develop reinforcement learning (RL) algorithms with Monte-Carlo Tree Search (MCTS) on our SGNN for SR. Such a physics-constrained graph symbolic regression (PCGSR) method effectively compresses the search space for efficient SR. Experiments on synthetic and real-world scientific datasets demonstrate the efficiency and accuracy of our PCGSR in discovering underlying expressions and adhering to physical laws, yielding physically meaningful solutions.

Decision: reject
Reviewer scores: 5, 8, 3

Reviews and discussion:
<thread>
creation date:
1730474213255

thread_type:
official_review

<thread_object>
creator: reviewer_4ixr

<content>
summary:
This paper proposes a symmetric invariant data structure, the Symbolic Graph, replacing expression trees in symbolic regressions. It also develops a GNN to encode physics constraints and guide the MCTS algorithm. Numerical experiments on two benchmarks and one synthetic dataset show the performance improvement of the proposed method.

strengths:
1. The presentation, visualization, and the design of real-world experiments.
2. The idea of handling symmetric invariance by a new data structure.

weaknesses:
1. The necessity of GNN. It seems that the proposed symbolic graph(SG) can be viewed as a tree with more branches and special nodes (e.g. summation, directed minus). If this is true, then the SG (with trivial modifications) can also be processed by existing non-graph neural networks designed for expression trees.
2. The necessity of physics-constrained NN. It seems that the NN is self-trained to learn the physics constraints from hand-crafted rules. But If the rules are simple and explicit, then one can bypass the self-training and directly encode the rules into the MCTS process. If the rules are complex or unknown, then how to train the network to learn them?

questions:
1. Why were the NNGP and SPL baselines not compared in the real-world experiment (Table 3)?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730517222116

thread_type:
official_review

<thread_object>
creator: reviewer_er9j

<content>
summary:
•	This paper introduces a new method for Symbolic Regression, termed Graph Symbolic Regression (SGN). The authors propose using a Graph Neural Network (GNN) to represent mathematical expressions as expression graphs (EGs), addressing inefficiencies in traditional symbolic regression by reducing the search space through symmetry and permutation invariances.
•	The authors also incorporate unit-consistency constraints to ensure that resulting expressions are physically meaningful.
•	The method is benchmarked against existing methods using both synthetic datasets and real-world applications.

strengths:
•	By leveraging symmetry and permutation invariances, the proposed GSR method effectively compresses the search space, enabling more efficient exploration of possible expressions.
•	The inclusion of unit-consistency constraints ensures that the expressions produced are physically meaningful.
•	The method is evaluated across diverse datasets and outperforms several existing symbolic regression methods.
•	The application on the DFT dataset is both significant and engaging.

weaknesses:
•	The two main components, permutation invariances and unit-consistency constraints, are conceptually unrelated and could potentially be split into separate papers, each addressing a distinct methodological contribution.
•	The proposed permutation invariances appear to apply only to addition, multiplication, and power operators. How would this method handle trigonometric operators, for instance, with cases like ( \sin(x + \pi/2) = \cos(x) )?
•	Although Figure 2 is clear, it’s unclear how Equation 2 aids the simulation step in MCTS, or how it relates to Equation 6 in the appendix.
•	Previous work, including the original DSR paper, has implemented constraints to eliminate infeasible equations, and some other studies already utilize unit constraints to filter out physically meaningless equations. How does Section 3.4 offer a novel approach here?

questions:
•	Could you clarify the third point in the Weaknesses?
•	Could you also elaborate on the rationale behind the SGNN objective (Equation 5)?
•	A recent paper, Scaling Up Unbiased Search-based Symbolic Regression (IJCAI2024), also proposes graph representations to replace tree structures. Could you compare SGN’s approach with theirs?
•	The literature review on constraint-based methods could be strengthened. The claimed difference between your work and "Deep Symbolic Regression for Physics Guided by Units Constraints: Toward the Automated Discovery of Physical Laws" requires clarification. For example, they use a design constraint to exclude infeasible next-step tokens without using a penalty, which contrasts with your summary.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730709167296

thread_type:
official_review

<thread_object>
creator: reviewer_qfds

<content>
summary:
The paper introduces a symbolic regression method “PCGSR” that improves the symbolic expression search space with a better representation (“symbolic graph”) and imposes constraints to yield physical solutions. Experiments on two SR benchmarks validate the approach of using the symbolic graph representation (with deep RL + MCTS) and experiments on predicting copper lattice energies validate the efficacy of imposing domain knowledge constraints.

strengths:
1. Demonstrates the utility of a good representation (“symbolic graph”) and, to a lesser extent, neural guidance (deep RL + MCTS), in searching for a good symbolic expression.
2. Shows a potentially interesting application (copper lattice energy prediction), though I have reservations regarding the practical interest of this application (see Weakness 3 below).

weaknesses:
1. The method does not fully implement what the method is claimed to implement. In particular, despite physics constraints being the second main selling point of the paper (and in the title of the paper), no systematic way of doing that was given. No physics constraints were imposed in the experiments on the AI-Feynman and Nguyen benchmarks. On the copper crystal benchmark, the only constraints are either very specific to the experiment in question ($f(r) \to \infty$ as $r \to 0^+$), or just reimplement something that already exists (correct dimensions, from AI-Feynman). (By the way, I do not consider trivial mathematical constraints mentioned in the paper like “argument of log is positive” or “energy function must output a scalar” to be “physics constraints”. These are just basic conditions that need to be met for SR to even be possible at all.) See also question 2 below for my doubts on the use of the term “physics constraints” the way the paper used it.
2. Furthermore, incorporating domain knowledge as constraints has already been explored in many ways in the literature. See, for example, a brief review given in Section 1.2 of Fox et al. 2024 [1].
3. The copper crystal benchmark shows PCGSR’s ability to find a formula for the energy of 32 copper atoms in a lattice, after being trained on DFT data from 32 copper atoms in a lattice. Such a formula is not of much practical use since it does not apply to anything other than 32 copper atoms in a lattice, so the experiment is not a good demonstration of the practical applicability of PCGSR. (By contrast, actual computational chemistry methods such as DFT are applicable to materials/molecules in general.) Although the paper does show results of transferability to a copper lattice compressed volumetrically by 50%, this compressed lattice is not something that can physically exist in the real world and is thus not of practical interest either. An experiment that would better showcase PCGSR would be to train on data from a non-trivial class of materials/molecules to discover 1 formula that accurately describes all of them.
4. Another main selling point of the paper is that it addresses the issue where previous methods do not search efficiently because of semantically equivalent expression trees. However, this issue has already been addressed in the literature in many ways—see the brief review given in the introduction section of Huynh et al. 2016 [2].
5. Another main selling point of the paper is its use of neural-guided search (deep RL + MCTS). This idea is also not new. See, e.g., Landajuela et al. 2021 [3].
6. The results in Table 1 are not particularly strong given that PCGSR does not outperform SPL or NGGP with great statistical significance ($1.3\sigma$ and $1.0\sigma$, respectively).

[1] Charles Fox, Neil D Tran, F Nikki Nacion, Samiha Sharlin and Tyler R Josephson, “Incorporating background knowledge in symbolic regression using a computer algebra system.” *Mach. Learn.: Sci. Technol. 5*, 2024.

[2] Quang Nhat Huynh, Hemant Kumar Singh and Tapabrata Ray, “Improving Symbolic Regression through a Semantics-driven Framework.” *IEEE SSCI*, 2016.

[3] Mikel Landajuela, Brenden K. Petersen, Sookyung Kim, Claudio P. Santiago, et al., "Discovering symbolic policies with deep reinforcement learning." *ICML*, 2021.

questions:
1. The introduction of deep RL with the SGNN feels quite costly to me. What do the tradeoffs look like for the accuracy gains from the SGNN vs. the extra computational costs incurred? Or are these costs balanced out by the gains from the extra guidance from the SGNN in the later parts of the training? Table 2 shows # of evaluations as a cost metric, but that doesn’t take into account the forward and backward passes of the SGNN, so I wonder what the wall-clock time looks like with vs. without the SGNN?
2. The paper frequently mentions that the SGNN encodes physics constraints, but what people typically think of as “physics constraints” are a lot more involved than the ones considered. For example, I think of time/spatial symmetry and conservation of energy/momentum etc. Do you have a systematic way to incorporate constraints likes these in PCGSR?
3. It would be nice to contextualize the results in Table 3. What is the typical MAE in DFT calculations? What is typically the accuracy needed for an energy calculation to be practically useful?
4. What do the costs look like in Table 1 (e.g. # evaluations, wall-clock time)? Although the max # evaluations (500k) and the time limit (24hrs) were the same for all methods compared, it could be that, on easy tasks, PCGSR takes longer than the baselines. It would be helpful to see a breakdown over cost, e.g., the recovery rate when the time limit is 2, 4, 6, 12, 24 hours.

Corrections:
1. Abstract line 1: “explainable” -> “explainability”
2. Line 118: $f \subset Q$ – I don’t think “$f$ is a subset of $Q$” is the intended meaning here?
3. Lines 230 & 239: “We” -> “we”. Line 321: “we” -> “We”
4. Lines 421–424 (about Pauli’s exclusion principle): There’s a misunderstanding of Pauli’s exclusion principle here. The phenomenon described in lines 421–424 is just electrostatic repulsion (Coulomb’s law) and has nothing to do with Pauli’s exclusion principle. Pauli’s exclusion principle states that two fermions cannot be in the same quantum state. As an example, electrons in an atom cannot occupy the same quantum state; as a result, because each electron has two spin states, every atomic orbital can hold at most two electrons, resulting in the structure that we see in the periodic table (2 elements in row 1, 8 elements in row 2, etc.).

Suggestions:
1. Given my criticisms of the paper, the following reworked story would be more convincing to me: "We show that using a graph neural network to predict next actions in neural-guided MCTS outperforms previous approaches to neural-guided search for SR." That's it--nothing about the symbolic graph (Weakness 4) or physics constraints (Weaknesses 1-3).
</content>
</thread_object>

</thread>
<thread>
creation date:
1732292333184

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Author Rebuttal

comment:
We thank the reviewers for their time and efforts to provide thoughtful feedback. Below, we address the common questions and concerns regarding the physics constraints, clarifying the rationale and significance of SGNN to incorporate them to provide a clearer understanding of our model formulation and solution.

The "physics-constrained" method in our work refers to the SGNN mechanism learning the encoding of priors for hand-crafted constraints, rather than introducing new physics-specific constraints. We clarify key aspects below:

**1) Systematic Implementation to incorporate different constraints**
We classify constraints into two categories:  
- **Pre-constraints**: Simple constraints testable during token sampling, such as mathematical rules or general symbolic regression (SR) constraints (Section 3.4).  
- **Post-constraints**: Complex constraints requiring a complete expression for evaluation (e.g., $f(r \rightarrow 0) = \infty$ in Section 5.2).

**Strategies for incorporating constraints**:  
- **Pre-constraints**: During token sampling, we zero out probabilities of actions violating constraints, preventing invalid expressions.  
- **Post-constraints**: After generating a complete expression, we penalize invalid outputs with zero rewards.

This flexible strategy allows users to define customized constraints and assign them based on these categories.

**2) Rationale Behind SGNN**
Post-constraints cannot be directly encoded as pre-constraints to prevent invalid expressions during sampling, due to the requirement of full expression for testing, leading to sparse rewards in search spaces with complex constraints (e.g., Section 5). This challenge particularly affects sampling methods including naive Monte-Carlo Tree Search (MCTS) or Genetic Programming (GP), which fail to learn from constraint violations for certain training horizons (random simulation in MCTS, and random crossover and mutation in GP).

To address this, we propose **SGNN-guided MCTS** (Section 3.3):  
- SGNN is trained (Eq. 5) to predict priors (Eq. 2), making it possible to integrate post-constraint priors into pre-constraint strategies.  
- This mechanism enables SGNN to:  
  - Leverage post-constraint insights during the MCTS simulation token sampling phase. 
  - Discover hidden constraints and promote promising candidates.  
  - Alleviate the issues due to reward sparsity and improve search efficiency.

**3) Comparison with Related Work**
We appreciate the reviewer QFds’s reference to Fox et al. 2024. However, our focus differs:  
- **Existing works**: Propose new constraints or methods to incorporate them via hand-crafted priors or penalty functions.  
- **Our work**: Tackles reward sparsity caused by post-constraints, introducing SGNN to self-learned priors that leverage post-constraint knowledge during sampling, improving exploration efficiency.

By integrating SGNN-guided strategies, our approach significantly enhances search performance in complex constraint environments.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733019591008

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of Manuscript Revisions

comment:
We extend our sincere gratitude to all reviewers for their constructive feedback, which has greatly helped us enhance the quality of our presentation and experiments. Based on the reviewers' questions, suggestions, and our responses, we have made the following revisions to the manuscript:

- **Revised Abstract and Introduction (Constraints Section)**  
  - Replaced all references to *"physics constraints"* with *"constraints"* to emphasize the generalizability of SGNN's encoding.  
  - Highlighted *"physics constraints"* as a special case relevant to sparse reward scenarios and real-world significance.  
  - Updated the review of physics constraints incorporation for better accuracy.

- **Revised "Constraints Incorporation" Section**  
  - Introduced the concepts of *Pre-constraints* and *Post-constraints* along with their respective incorporation strategies.  
  - Elaborated on the rationale behind SGNN's role in encoding *Post-constraints*.  
  - Listed *physics constraints* as specific examples of post-constraints.  

- **Added "Cost Effectiveness" Section**  
  - Provided a detailed explanation of SGNN's role in reducing computational costs.  
  - Discussed SGNN balancing the trade-off between exploration and exploitation compared to prior methods.  

- **Updated "Experimental" Section (Table 1)**  
  - Included DSR as an additional pure Deep-RL baseline.  
  - Added running efficiency metrics for all models to provide a more comprehensive comparison across different SR methods.  

- **Updated "Experimental" Section (Table 2)**  
  - Renamed ablation models for improved clarity (e.g., *MCTS-1* → *MCTS-SG*, *MCTS-2* → *MCTS-GNN*, *MCTS-3* → *MCTS*). The missing Recovery Rate in Table 2 (previously noted in the Rebuttal to Reviewer QFDS[3/4]) will be recovered in our final version.  
  - Included the running time for each model and added an efficiency analysis section to highlight PCGSR's cost-effectiveness.  
  - Clarified the equation selection strategy in Appendix Section C.3.  

- **Updated "Application" Section**  
  - Renamed the model in Table 3 from *MCTS* to *MCTS-GNN* for consistency with Table 2.  
  - Updated the *"Pauli's Exclusion Principle"* to *"Electrostatic Repulsion"* for better accuracy. Added the physics constraints explanations in Appendix Section D.5.
  - Included practical applications of PCGSR's solution in Appendix Section D.2.  
  - Added the physical significance of the compressed copper dataset in Appendix Section D.7.  

We hope these revisions improve the clarity and comprehension of our contributions. Once again, we thank the reviewers for their prompt responses and insightful suggestions. Your feedback has been invaluable in refining our work.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733168153901

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Follow-Up

comment:
We sincerely thank all the reviewers for their time and effort during the discussion period. We have carefully addressed all the concerns and questions raised in the reviews by providing detailed clarifications, additional analyses, new experimental results, and a thoroughly revised manuscript. These revisions, we believe, have significantly enhanced the quality and clarity of our work.  

We would greatly appreciate any further feedback the reviewers may have regarding our latest responses and the updated manuscript. If there are any remaining questions or concerns, we are eager to address them promptly.  

Once again, we extend our gratitude to all the reviewers for their insightful feedback and constructive suggestions throughout this process.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces "Graph Symbolic Regression" (SGN), which replaces traditional expression trees with a Symbolic Graph and employs a Graph Neural Network (GNN) to guide the Monte Carlo Tree Search (MCTS) algorithm. Experiments on benchmark datasets, synthetic data, and real-world applications demonstrate the effectiveness of the proposed method. 

However, two reviewers have recommended rejection, and the authors' rebuttal does not fully address their concerns. First, the novelty of the approach is unclear, as it builds on well-established methods without offering a substantial new contribution. Second, the experiments are unconvincing, with insufficient datasets and scenarios to fully evaluate the robustness of the method.

In conclusion, I do not recommend accepting this paper in its current form.