Proof that locality is sufficient in showing two graphs are isomorphic
This method fails on regular graphs. For example, it fails on the following two graphs: the hexagon, and two disconnected triangles.

More generally, if you continue to explore neighbors' neighbors and so on, you get the 1-dimensional Weisfeiler–Lehman method. If you start with $k$-tuples of vertices, you get the $k$-dimensional Weisfeiler–Lehman method. Cai, Fürer and Immerman proved in An optimal lower bound on the number of variables for graph identification that there exist non-isomorphic graphs on $n$ vertices which fail to be distinguished by the $k$-dimensional Weisfeiler–Lehman method unless $k = \Omega(n)$. Since the running time of the method in the worst case is asymptotically $n^{k+1}$, this shows that the Weisfeiler–Lehman method doesn't yield a subexponential time algorithm for graph isomorphism.

For more on the Weisfeiler–Lehman method, check a paper of Douglas, or the recent work of Neuen and Schweitzer.