We prove a linear query complexity lower bound for two-sided testing of graph isomorphism in the bounded-degree model.
Specifically, there are constants $d$ and $\varepsilon_0$ such that, for every sufficiently large $n$,
there exists an $n$-vertex graph $H_n$ of maximum degree at most $d$ such that testing isomorphism to $H_n$ requires $\Omega(n)$ queries.

The proof proceeds by a reduction from testing the solvability of a fixed sparse system of linear equations
over $\mathcal{F}_2$. Given a fixed matrix $A$ and an input vector $b$, we associate $b$ with a graph $G_b$
such that $G_b$ is isomorphic to $G_0$ whenever $Ax=b$ has a solution.
We show that each query to the graph can be emulated with at most one query to $b$, and that Hamming distance from
$Im(A)$ translates to the distance of $G_b$ from $G_0$. The main result then follows from a
linear query lower bound for testing the solvability of the underlying (sparse) linear system.