Graph-based Symbolic Regression with Invariance and Constraint Encoding
Ziyu Xiang, Kenna Ashen, Xiaofeng Qian, Xiaoning Qian
Symbolic regression (SR) offers interpretable over `black-box' solutions by providing analytical expressions, enabling the identification of key functional dependencies in complex systems. In this paper, we identify two key limiting factors in existing SR methods: (a) redundant representations arising from the inability to capture expression equivalences and higher-order operand relations, which breaks permutation invariance and limits encoder effectiveness; and (b) sparse rewards caused by incomplete incorporation of constraints evaluated on full expressions (e.g. constant fitting for unit consistency and/or physical law verification) during the sampling process. To address these challenges, we propose an efficient graph-based SR method, **GSR**, which preserves the permutation invariance by encoding expression equivalences and higher-order structural features on an expression graph (EG), and mitigates reward sparsity via employing hybrid neural-guided Monte-Carlo tree search (hnMCTS) for complete constraint integration and improved exploration-exploitation trade-off. Experiments on synthetic and real-world scientific datasets demonstrate the efficiency and accuracy of GSR in discovering underlying expressions and adhering to physical laws, offering practical solutions for scientific discovery.