What equivalence relation does this algorithm produce for an cyclic directed graph with labeled edges?
For graph isomorphism, there are many heuristics that work in well in practice on most graphs.  You could try adapting any of them to your setting.

Here's one example of a simple heuristic that might often work well in practice (but with no guarantees on worst-case performance).  Let $f_0:V \to \mathbb{N}$ be the original values of the graph, so $f_0(v)$ is the value on vertex $v$.  Now construct a new set of values $f_1:V \to \mathbb{N}$ from $f_0$, as follows.  For each vertex $v$, apply your two-step algorithm to get a description for $f$ using breadth-first search---but crucially, stop the breadth-first search after depth 1.  Take the resulting description, hash it with any hash function, and use the resulting hash as $f_1(v)$.  You can do this again, and construct $f_2$ from $f_1$ (note that we are now ignoring the original values on the nodes, and using the values from $f_1$, when computing $f_2$), and then construct $f_3$ from $f_2$, and so on. Do this for a few steps, say 100 steps.  Each iteration can be done in $O(n)$ time, so the total running time will be $O(n)$ to compute all of the values $f_{100}$.

Now we have a nice property: if $f_i(v_1) \ne f_i(v_2)$, then $v_1$ is not equivalent to $v_2$.  Thus, if $f_{100}(v)$ is a singleton ($v$ is the only vertex with that value; i.e., there does not exist $w$ such that $f_{100}(v)=f_{100}(w)$), then there is no need to compute a full description for your $v$.  We can apply your full algorithm to compute a full description for only the vertices $v$ whose value appears multiple times in $f_{100}$.  Heuristically, for most graphs, there probably won't be many of them.  Thus, you won't have to compute the full description for many vertices, and you might avoid quadratic running time.

There are degenerate graphs where this might fall apart, and where the running time becomes quadratic, but for "most" graphs, hopefully this won't happen.