It is worth trying classical estimates for relational JOIN (i.e. for multiplication) and for recursive JOIN (i.e. for Kleene-star) combined with e-graphs to find the best plan. They can be obtained from `https://pure.tue.nl/ws/portalfiles/portal/341762557/20241031_Mulder_hf.pdf, from https://github.com/chernishev/Database-Engines-Course/tree/master/Lecture%203, slide 40.
These estimates can be calculated by maintaining two vectors, one reduced by rows, and the other one reduced by columns for adjacency matrix for each label. It is worth mentioning that these vectors should be estimated for each subtree and it can be non-trivial for non-leaf vertices.