Local vs average behavior on inhomogeneous structures: Recurrence on the average and a further extension of Mermin-Wagner theorem on graphs