Equality Graphs and Symbolic Regression: A Perfect Match?

F. Olivetti de Franca, Federal University of ABC
G. Kronberger, University of Applied Sciences Upper Austria (FH OÖ)

Let's do science!

• Specify a hypothesis.
• Collect data through experiments.
• Describe the measurements with a mathematical function.
• Replicate.

Symbolic Regression

• Search for parametric functions on the form describing the observation.

Some Challenges

• Easy to generate overparameterized functions
• Search space is not smooth
• There can be multiple equally good solutions

The solution

• e-graphs and equality saturation can help with all these!!

Overparameterization

Fabricio Olivetti de Franca and Gabriel Kronberger. 2023. Reducing Overparameterization of Symbolic Regression Models with Equality Saturation. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '23). Association for Computing Machinery, New York, NY, USA, 1064–1072. https://doi.org/10.1145/3583131.3590346

Overparameterized models

Symbolic Regression algorithms are prone to overparametrization:

• The parameters can assume different values for the same data
• Numerical issues and slow convergence of optimization
• Larger search space for memetic approaches
• Interpretation is hindered

Research Questions

• Is overparametrization really a problem?
• Can EqSat help to reduce overparametrization in SR?
  • How well does it compare with simpler alternatives? (e.g., Sympy)
• Does EqSat always reduce to the optimal number of parameters?
• How fast is EqSat?

Method

• First we run different SR algorithms on two benchmark datasets.
• Then we applied hegg, SymPy, and a combination of both in the resulting expressions.
• We compared the ratio of decrease in number of parameters.
• The cost function assigned a value for every parameter and a value of for any other symbol.

Set of Rules

Set of Rules

How much can EqSat help?

Is it fast?

Sometimes the set of rules induced some exponential growth of the e-graph...

SRTree: a library for symreg with tree representation

• Haskell library with convenient functions to handle expression trees
• Integrated e-graph and equality saturation, based on hegg and egg

Conveniences

• Convenient fields for the main structure: sorted list of e-classes by fitness, unevaluated e-classes, e-classes that must be refited, height of the best expression of each e-class, information about parameters
• Convenient functions: getter and setter for some of the fields, conversion to an from tree repr., get all possible expressions from one id, get top e-classes within range or given conditions

Avoiding exponential growth

• Stop eq-sat if it reaches an upper limit of e-classes
• Apply the matching rules only if it will merge e-classes (i.e., no new e-class created) (optional)
• Height increase limit (optional)
• This reduced the frequency in which eq-sat induced exponential growth while keeping the final results reasonable for SR.

Navigating the Search space

Fabricio Olivetti de França and Gabriel Kronberger. 2025. Improving Genetic Programming for Symbolic Regression with Equality Graphs. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '25). Association for Computing Machinery, New York, NY, USA, 989–998. https://doi.org/10.1145/3712256.3726383

Neutrality

• Neutral perturbations: navigability despite selective pressure.

• Bloating introduces new patterns without impacting the fitness.

• New opportunities to find better solutions later.

• 
  

Neutrality

This has other implications:

• waste of evaluation budget
• waste of generations in the same neutral region

Ideally we would be able to:

• detect neutral zones
• generate the neutral perturbations
• create a escape pod from those regions

EGGP (E-Graph Genetic Programming)

Key differences to GP:

• whole search history is kept in memory
• modified crossover and mutation to skip the neutral region

E-Graph Mutation

• The green boxes are expressions that were previously evaluated.
• After mutating to , detect revisitation.
• Replace the root with any other operator that creates something new ( ).

E-Graph Crossover

• First parent and crossover point .
• Second parent with the choices of .
• Replacing the red part with either will generate something new.

Critical Difference diagram of the average ranks of the tested methods calculated by the average MSE over the 30 runs of each dataset

Results: Model Size

CD diagram of the ranks calculated over average model size.

Exploring the probable hypotheses

Fabricio Olivetti de França and Gabriel Kronberger. 2025. REGGression: an Interactive and Agnostic Tool for the Exploration of Symbolic Regression Models. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '25). Association for Computing Machinery, New York, NY, USA, 4–12. https://doi.org/10.1145/3712256.3726385

rression: Playground for e-graphs and equality saturation in SR

• Database storing multiple models using e-graphs.
• Pattern matching ability.
• Building blocks explorations.
• Modularity detection.
• Import expressions from:
  • Operon
  • PySR
  • GOMEA
  • etc.
• Pandas DataFrame.

More info at https://github.com/folivetti/reggression

Let's fit!

• Nonlinear relationship.
• The training set is insufficient to guarantee an unique global optima.

In any case, the purpose here is to show how we can use rression to explore alternative models.

Laying the egg

We can create an initial e-graph for this dataset using eggp:

from eggp import EGGP
import pandas as pd

reg = EGGP(gen=200, nPop=200, maxSize=25, \
      nonterminals="add,sub,mul,div,log,power,sin,cos,abs,sqrt", \
      simplify=True, optRepeat=2, optIter=20, folds=2,  \
      dumpTo="vlad.egg")
reg.fit(x_sel, y_sel)

Some observations

• The non-terminal set is large to generate many different alternative models.
• We could possibly find better models with proper settings.
• The maximum size is larger than the true equation.

We are saving the final e-graph into the file named vlad.egg so we can explore it after the search.

Hatching the egg

Now, let's load the e-graph into rression:

from reggression import Reggression
egg = Reggression(dataset="vlad.csv", loadFrom="vlad.egg")

Top-N models, the third one will surprise you!

If we look at the top-5 models, we can see small variations of the top performing with similar fitness (negative MSE) values.

egg.top(5)[["Latex", "Fitness", "Size"]]

Behave!

Some of these functions behave similarly while others display a different behavior when looking outside of the training region:

Filter and plot!

We can retrieve top expressions filtering by size:

model_top(egg.top(n=10, filters=["size <= 10"]), n, x, y)

Rich Gets Richer

Let us investigate the distribution of tokens from the top 1000 generated expressions.:

egg.distributionOfTokens(top=1000)

Is tough being exponential!

Sine and cosine are ranked next, while the exponential is rarely used and particularly with a worse average fitness than the other tokens.

The reason for this could be that fitting parameters inside an exponential function can be tricky depending on the initial values.

Let's check it out!

We can verify that by plotting the top 5 expressions with the pattern with the command:

egg.top(n=n, pattern="exp(v0)*v1")

and as we can see, still not a very good fit, as expected.

With a little help from my friends

We can try our luck with another SR method, such as Operon [4], and insert the obtained expressions into the e-graph:

from pyoperon.sklearn import SymbolicRegressor
regOp = SymbolicRegressor(objectives=['mse','length'], max_length=20, \
       allowed_symbols='add,sub,mul,div,square,sin,cos,exp,log,sqrt,abs,constant,variable')
regOp.fit(x_sel, y_sel)
f = open("equations.operon", "w")
for eq in regOp.pareto_front_:
  eqstr = regOp.get_model_string(eq['tree'])
  fitness = -eq['mean_squared_error']
  print(f"{eqstr},{fitness},{fitness}", file=f)
f.close()
egg.importFromCSV("equations.operon")

Top-5 with Operon

Still no luck! But we didn't make things easy for SR anyway!

Let's cheat!

We can insert the ground-truth expression to see whether the parameter optimization is capable of converging to the true parameters and if the fitness is better than what we have.

egg.insert("exp(x0/t0)*(x0^3)*(cos(x0)*(sin(x0)^2)-t1)")

It's all the same, no matter where you are

We can also use rression to check whether two or more expressions are equivalent. Let's say we want to see whether and are the same.

First, we create an empty e-graph:

newegg = Reggression(dataset="vlad.csv", loss="MSE")

They are different after all

Next, we add both expressions while storing their e-class ids:

eid1 = egg.insert("(x0 + 3)**2 - 9").Id.values[0]
eid2 = egg.insert("x0*(x0 + 6)").Id.values[0]
print(eid1, eid2)
> 6, 9

Initially, their ids are going to be different, since until now they are distinct to each other as far as the e-graph is concerned.

Or maybe not...

Now, the main idea is that we run equality saturation to produce all the equivalent forms of each one of these expressions following a set of rules, such as:

If the set of rules are sufficient to produce at least one common expression departing from the first and from the second expressions, they will eventually be merged, and their e-class id will become the same.

Equality Saturation for You!

We can run some iterations of equality saturation using the command:

egg.eqsat(5)

And, now, their ids should be the same!

print("Id of the first equation: \n", egg.report(eid1).loc[0:1, ["Info", "Training"]])
print("Id of the second equation: \n", egg.report(eid2).loc[0:1, ["Info", "Training"]])
> Id of the first equation: 16
> Id of the second equation: 16

Multiverse

After running equality saturation, we can also retrieve a sample of the equivalent expressions for that e-class id:

egg.getNExpressions(eid1, 10)

Leading to:

Structural Similarity

We can also measure the similarity between two expressions by measuring the percentage of shared e-classes ids.

Code and Resources

Python library and CLI

pip install eggp
pip install reggression
pip install symregg

https://github.com/folivetti/eggp
https://github.com/folivetti/reggression
https://github.com/folivetti/symregg