We investigate the equivalence of Sobolev inequalities and the conjunction of Gaussian upper heat kernel bounds and volume doubling on large scales on graphs. For the normalizing measure, we obtain their equivalence up to constants by imposing comparability of small balls and the vertex degree at their centers. If arbitrary measures are considered, we incorporate a new local regularity condition. Furthermore, new correction functions for the Gaussian, doubling, and Sobolev dimension are introduced. For the Gaussian and doubling, the variable correction functions always tend to one at infinity. Moreover, the variable Sobolev dimension can be related to the doubling dimension and the vertex degree growth.