Is it possible formalise a general procedure that evaluates the nth application of a rule to any graph? ie the graph equivalent of what the Binet Formula is to the Fibonacci sequence.
Finding an analytical solution to this would greatly reduce the overall computational cost of the project. I have found examples of pairs of certain rules and graphs that have a defined nth term formula, (though they are quite contrived) so perhaps it might not be impossible to find a general procedure.
I think a general procedure would be directly in conflict with the computational irreducibility principle.
It is possible to compute what you are suggesting (essentially, products of the rule with itself). In fact, we have this prototype function (it's not documented, but there are some examples), which allows you to do that.
The problem, however, is that in general, you would get multiple rules as a result of such a product. Each of the rules would also be typically larger than the original, so it does not help with optimization. And yes, this is a direct consequence of computation irreducibility.