3
$\begingroup$

I have a certain finite (but huge and without an apparent pattern, so that only numerical studies seem feasible) graph $G = (V,E)$, and a function $f: V \rightarrow \mathbb{R}$. On each edge $e = (u,v)$ with endpoints $u, v \in V$, we assign an orientation so that we go from $u$ to $v$ if $f(u) > f(v)$. Define the ``potential'' of $e$ to be $f(u) - f(v)$.

Now pick a random (uniformly if you will) point in $V$, and continue walking down along the edges of the greatest potential until one reaches a local minimum, i.e. a vertex without an edge starting from it. I am intending a graph-theory analogue of the gradient descent method on a function $F: \mathbb{R}^n \rightarrow \mathbb{R}$ (see https://en.wikipedia.org/wiki/Gradient_descent).

My computer experiments suggest that some local minima are reached way more often than others. I wish to predict how attractive a given local minimum is by studying $f$ around that minimum. For instance, in the case of gradient descent, one can look at the Hessian (of course it's wrong in general, but in case our function $F$ is computationally cumbersome even for a computer, wouldn't it be a reasonable first guess). So my question is, in other words, does there exist an analogue of this Hessian in the graph-theory context?

Or is there a better way of thinking about this? Instances where a similar problem has been discussed? I feel some people should think about the size of basins of attractions on graphs, but my literature search hasn't been so fruitful.

$\endgroup$
2
  • $\begingroup$ I don't know of any such concept. Do you want to take the actual spatial coordinates $u$ into account? Then then "potential" divided by the distance $u-v$ would be an approximation to the directional derivative and in this sense you could cook up approximations of higher order derivatives. But probably that's not what you want. There is, however, the graph Laplacian… $\endgroup$
    – Dirk
    May 11, 2016 at 11:05
  • $\begingroup$ @Dirk Yes, the discrete Laplacian is probably the closest to the Hessian you can have on graphs. But if you multiply it to $f=(f(v))_{v\in V}$, you get a new vector in $\mathbb R^V$ whose smallest entry does not necessarily correspond to a global minimum: think of a star with $f(leaf_1)=100$, $f(leaf_2)=-1$ and $f\equiv 0$ elsewhere. $\endgroup$ May 12, 2016 at 13:39

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.