By knot, I assume you mean a knot in $S^3$. Typically a knot is encoded as a diagram, which you might think of as a tetravalent planar graph, with some kind of description of undercrossings and overcrossings, say by some kind of labelling of the half edges incident to every vertex. Abstractly, the notion of equivalence is ambient isotopy; combinatorially, in terms of the diagram, there are the three types of Reidemeister moves.

There are other data types used (like self-avoiding cycles in the integer lattice, or triangulations of $S^3$ together with a cycle in its 1-skeleton), but they will all differ essentially from (finite) graphs in the following way: for any given knot type, there will be infinitely many descriptions of it in that data type. So equivalence will not be as "simple" as conjugation by a permutation matrix. Instead, a priori, one must search through an infinite collection of descriptions related by local moves. Improving on this, Lackenby has shown a polynomial bound on the number of Reidemeister moves to recognize an unknot. More generally, given the current state of things, it's entirely possible knot equivalence is in $\mathsf{P}$.