The adjacency matrix itself is not a graph invariant, because it is not invariant under relabeling of the nodes of the graph. Let $B_{n}$ be the set of symmetric, zero-diagonal, $n\times n$ binary matrices. Then the simple graphs on $[n]=\{1,2,...,n\}$ are in a one-to-one correspondence with the elements of $B_n$: take the adjacency matrix of the graph to get its representative in $B_n$. Permutations of the node labels act as follows: for $\pi\in S_{n}$ and $X=(X_{ij})\in B_{n}$, we have $(\pi\cdot X)_{ij}=X_{\pi^{-1}(i),\pi^{-1}(j)}$. The operations $\langle S_{n},\cdot \rangle$ define an equivalence relation on $B_{n}$; and the elements $[X]$ of the quotient $B_{n}/\langle S_{n},\cdot \rangle$ are the desired graph invariants: $G$ and $H$ are isomorphic if and only if their adjacency matrices satisfy $[A(G)]=[A(H)]$.
The problem becomes one of finding a canonical representative for each element of $B_{n}$, or otherwise testing whether any two elements of $B_{n}$ are in the same equivalence class. For instance, one could choose the lexicographically smallest element of the orbit $S_{n}\cdot X$ as the representative of $[X]$ for each equivalence class. The problem with this approach is that the orbit can have size $n!$. Clearly it can be done; but the open question is whether it can be done efficiently. The equivalence-testing problem is not currently known to be NP-hard (and hence NP-complete, since clearly it is in NP); but neither is any polynomial-time algorithm known.