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?  Even if you have a compact description of cycles, that doesn't give you a bijection short of ordering them somehow.

Here is a kind of silly example but tell me what bijection you would want:

Both graphs have two vertices and multiple parallel directed edges. The adjacency matrices are

$A_G=\begin{bmatrix} 0 & 1  \\ 4 & 0   \end{bmatrix}$ and $A_H=\begin{bmatrix} 0 & 2 \\ 2 & 0   \end{bmatrix}$ 

Even for very large $k>n$ the powers have the same trace , and are equal when the trace is not zero:

$A_G^k=A_H^k=\begin{bmatrix} 2^k &0  \\ 0 & 2^k   \end{bmatrix}$ for $k$ even. 

For odd $k$ we have $A_G^k=\begin{bmatrix} 0 & 1  \\ 4^k & 0   \end{bmatrix}$ and $A_H^k=\begin{bmatrix} 0 & 2^k \\ 2^k & 0   \end{bmatrix}$ both with trace $0.$

A picture is hardly needed but here is one with edge labels.


[![enter image description here][1]][1]

 If you do not want multiple directed edges with the same head and tail then put a vertex at each letter. Provide a isolated vertex to $H$ so that both have $n=7$ vertices. 


  [1]: https://i.sstatic.net/BUW9z.png