At one point in (1), the complex-weighted counting graph homomorphism dichotomy theorem for any finite domain size, Cai, Chen, and Lu only prove the existence of a polynomial-time reduction between two counting problems via polynomial interpolation. I don't know of any practical value for such an algorithm.
See Section 4 of the arXiv version. The lemma in question is Lemma 4.1, called the "First Pinning Lemma".
One way to make this proof constructive is to prove the complex-weighted version of a result of Lovasz, namely:
For all $G$, $Z_H(G, w, i) = Z_H(G, w, j)$ iff there exists an automorphism $f$ of $G$ such that $f(i) = j$.
Here, $w$ is a vertex in $H$, $i$ and $j$ are vertices in $G$, and $Z_H(G, w, i)$ is the sum over all complex-weighted graph homomorphisms from $G$ to $H$ with the added restriction that $i$ must be mapped to $w$.
(1) Jin-Yi Cai, Xi Chen and Pinyan Lu, Graph Homomorphisms with Complex Values: A Dichotomy Theorem (arXiv) (ICALP 2010)