I'm giving a talk tomorrow about a result in computer science which I recently proved. It's a recurrence-transience result on a random process which is related in spirit to a simple random walk. My result works on any bounded degree locally finite graph, and I'd like to discuss the analogy to random walks there as well. Unfortunately, I've never studied random walks on graphs other than lattices. It's easy to define a random walk on an arbitrary locally finite graph (if there are $d$ edges out of $v$ then assign each probability $1/d$). Let's assume a very standard hypothesis: there is a fixed $D<\infty$ s.t. the degree of each vertex is less than $D$. Definitions from Doyle-Snell are given at the bottom of this post.
One thing which is known is Doyle and Snell's Theorem: if $G$ can be drawn in a civilized manner in $\mathbb{R}$ or $\mathbb{R}^2$ then the simple random walk on $G$ is recurrent.
Unfortunately, this leaves the question open for graphs which can't be drawn this way. An exercise in Doyle and Snell asks you to find a graph which can't be drawn this way but which is still recurrent. There is some discussion which says if a graph can be drawn in a civilized manner in $\mathbb{R}^3$ and that we can embed $\mathbb{Z}^3$ into a $k$-fuzz of $G$ then $G$ is transient. The rest of their paper gets heavily into the language of flows and I don't really understand it. It doesn't seem to finish the classification.
What's the current state of knowledge on recurrence vs. transience for random walks on a bounded degree locally finite graph? Has anyone figured this out for graphs other than those studied by the papers mentioned here?
I also found a paper by Carsten Thomassen which basically says if a graph grows slower than $\mathbb{Z}^2$ then it's recurrent (due to Nash-Williams originally) and if it satisfies an isoperimetric inequality slightly stronger than that of $\mathbb{Z}^2$ then it's transient. I don't understand this paper at all, but I'd be curious to know if it covers a larger class of graphs than Doyle and Snell's results do.
EDIT:
As my audience in this talk is going to be all graph theorists, I'm mostly seeking a purely graph theoretic characterization of recurrent graphs. So for me, "infinite resistance from any point to infinity" is not good enough. I'd rather have a criterion which doesn't require me to choose an embedding and set resistances. Perhaps there is no hope of getting such an answer, but Vincent's answer below makes me believe this problem has been studied outside the context of electrical networks.
Also, based on Vincent's comment, I'm making the definitions clearer:
Doyle-Snell page 105: $G$ can be drawn in a civilized manner if its vertices can be embedded into $\mathbb{R}^d$ so that for some $0<s$ and $r< \infty$, the distance between any two points is at least $s$ and the length of each edge is $\leq r$. The drawing of such a graph need not be planar.
For any integer $k$, the $k$-fuzz of $G$ is the graph $G_k$ obtained from $G$ by adding an edge $xy$ if it is possible to go from $x$ to $y$ in at most $k$ steps.
Best Answer
The fundamental result the completely characterizes recurrent/transient graphs is that a graph is recurrent if and only if the effective resistance of the graph, when considered as an electric network where every edge has resistance one, from some/any vertex to infinity is infinite. This is true also when the degrees are unbounded.
Of course, to use this, you need to understand how this resistance is defined and what method there are to show it's finite/infinite. The easiest ways to bound the the resistance from below is finding cutsets, sets which separate some specified vertex from infinity. If you have a disjoint sequence of such cutsets of sizes $a_n$, the effective resistance is at least $\sum_n 1/a_n$, so if this sum is infinite, the graph is recurrent. This is called the Nash-Williams criteria and it's easy to see that graphs growing slower than quadratic satisfy it (in fact, a slightly bigger growth rate is still OK).
In the other direction, one can bound the resistance from above by using flows. This is slightly more involved, I can elaborate later, if there is a demand.