Equality graph-assisted symbolic regression

In symbolic regression (SR), genetic programming (GP) is a popular search algorithm that delivers state-of-the-art results in terms of accuracy. Its success relies on the concept of neutrality, which induces large plateaus that the search can safely navigate to more promising regions. Navigating these plateaus, while necessary, requires the computation of redundant expressions, up to 60% of the total number of evaluations, as noted in a recent study. The equality graph (e-graph) structure can compactly store and group equivalent expressions, enabling us to verify if a given expression and its variations were already visited by the search, thus enabling us to avoid unnecessary computation. We propose a new search algorithm for SR called SymRegg that revolves around the e-graph structure, following simple steps: perturb solutions sampled from a selection of expressions stored in the e-graph and insert previously unvisited expressions, as well as their equivalent forms, into the e-graph. We show that SymRegg is capable of improving the efficiency of the search, maintaining consistently accurate results across different datasets with a minimalist set of hyperparameters. This article is part of the discussion meeting issue 'Symbolic regression in the physical sciences'.