Gradient step in a graph and average of a function Suppose that you have a function $f$ on the nodes $V$ of a graph. For a node $x$, define de node $\phi_fx$ to be the neighbor of $x$ such that the $f(y)-f(x)$ has the highest positive value and $\phi_fx = x$ if $f(y)-f(x)<0$  for all $y$. So $\phi_f$ is following the gradient for one step. Let $d_x$ be the degree of the node $x$. Is it true that if $x$ is random uniform
$$
\mathbb{E}_x [d_{\phi_fx} f(\phi_fx)] \geq \mathbb{E}_x [d_{x}f(x)]
$$
Of course climbing the gradient increases $f$ but the degree term messes things up a bit.

It is false in general. Take the graph $K_{1,3}=(\{v\}\cup \{u_1,u_2,u_3\}, E)$ and the function with values $f(v)=1$ and $f(u_i)=2$. And we have $d_v=3$ and $d_{u_i}=1$. Then
$$\sum_{x\in V}d_x f(x) = 9$$
$$\sum_{x\in V}d_{\phi_f x} f(\phi_f x)=8.$$
