If $G$ and $H$ are isomorphic then a bijection between them does what you want (Though I could assure you that two graphs are isomorphic, be telling the truth, and yet it could be hard to find a bijection.) You seem to be interested in the situation that $G$ and $H$ are $n$ vertex graphs which are not isomorphic yet $(A_g)^k$ and ($A_H)^k$ have equal trace for all $1 \leq k \leq n.$ 

Do you have examples? Do you have examples that don't differ by an obvious switch?  The bijection might be some thing like "triangles $ABC$ and $BCA$ in $G$ correspond , respectively, to triangles $PQR$ and $STU$ in $H$." So no connection to the structures of the graphs. Note that the trace counts directed cycles $ABC$, $BCA$ and $CAB$ separately. Change $BCA$ to $ABD$ above if you want to treat those three as the same cycle. Here I intend the $P,Q,R,S,T,U$ are $6$ distinct vertices of $H.$

If you said $1 \leq k \leq n-1$ I could give examples. I will in a moment.

A cheap answer is: Order the edges in each graph, Represent each $k$-cycle by its sequence of edges and list the the cycles of each graph according to dictionary order. Then map the ith $k$-cycle of $G$ to the $i$th of $H.$

That might have the undesirable feature I mentioned, but maybe that is unavoidable.

Here is a kind of silly example: Both graphs will have three vertices and and all edges are loops. The adjacency matrix of of $G$ is diagonal with entries $1,5,6$ while that of $H$ has diagonal $2,3,7$.

Both have $62$ $2$-cycles: 

 - In $G$ they are $AA$ once, $BB$ $25$ times (say all ordered pairs of two edges drawn from the $5$ loops on $B$) and $CC$ $36$ times.

 - In $H$ once has $PP$,$QQ$ and $RR$ $4$,$9$ and $49$ times respectively. 

So what would you want for your bijection? That example could be modified to replace each vertex with $j$ loops by a $2j+1$ point graph consisting of $j$ directed triangles all sharing one common vertex. The counts would agree for directed cycles of lengths $3,6$ and also for $k=1,2,4,5$ (those counts being $0$.)