Fact: Let $G$ be an $n$-vertex undirected graph and $(X_s)_{s\in \mathbb N}$ a stationary random walk on $G$. Then for every $s\in \mathbb{N}$, $ \mathbb{E}[d_G(X_s,X_0)^2] \le C s \log n $, for some universal constant $C>0$. Here $d_G$ is the shortest path metric on $G$.

This fact is a corollary of a theorem of Naor, Peres, Schramm, and Sheffield [https://arxiv.org/abs/math/0410422] stating that $\ell_p$, $p\ge 2$ has Markov type 2 with constant $O(\sqrt{p})$.

I'm looking for a "pure" probabilistic and/or combinatorial (and preferably, simple) proof of this fact, that in particular does not use Banach space notions such as smoothness.