  We consider continuous time simple random walks with arbitrary speed measure
$\theta$ on infinite weighted graphs. Write $p_t(x,y)$ for the heat kernel of
this process. Given on-diagonal upper bounds for the heat kernel at two points
$x_1,x_2$, we obtain a Gaussian upper bound for $p_t(x_1,x_2)$. The distance
function which appears in this estimate is not in general the graph metric, but
a new metric which is adapted to the random walk. Long-range non-Gaussian
bounds in this new metric are also established. Applications to heat kernel
bounds for various models of random walks in random environments are discussed.
