Embedding Symbolic Equivalence into Symbolic Regression via Equality Graph (arxiv.org)

Researchers introduced EGG-SR, a framework that embeds equality graphs (e-graphs) into symbolic regression to explicitly capture symbolic equivalence and shrink the effective search space. Many mathematically equivalent expressions (e.g., log(x1^2 x2^3) = log(x1^2)+log(x2^3) = 2log(x1)+3log(x2)) are treated as distinct by existing methods, causing redundant exploration. EGG-SR adds an EGG module that groups equivalent expressions into compact equivalence classes and plugs this representation into multiple symbolic-regression engines: EGG-MCTS (prunes redundant subtree search), EGG-DRL (aggregates rewards across equivalence classes to stabilize learning), and EGG-LLM (enriches feedback prompts with equivalence-aware guidance). Technically, embedding e-graphs yields provable benefits: under mild assumptions it tightens the regret bound for MCTS and reduces variance in the DRL gradient estimator, making search and learning more sample-efficient. Empirically, EGG-SR consistently improves diverse baselines on challenging benchmarks, finding formulas with lower normalized mean squared error than state-of-the-art symbolic regression methods. The approach is broadly applicable to AI-driven scientific discovery where closed-form laws are sought, and the authors provide code to reproduce results.