Wishlist: value propagation method

[scythetrigger]

What is the feature or improvement you would like to see?

An igraph.Graph method called "value_propagation" that would take four parameters:

• order: (default: topo) method to determine the sorting order in which vertex values are propagated via precedence arcs, which may be a vertex attribute (such as vertical Z coordinate in 3D space)
• discount: (default: 1) the discount rate which is > 0, <= 1
• mode: whether to propagate values along outbound or inbound edges
• weight: (default: unweighted)

Given a vertex ordering, from beginning to end add each vertex value, divided by the number of neighbors then multiplied by the discount factor, to its neighbors' values along the outbound (or inbound) edges. This may also accept a weight parameter that specifies if the vertex value should be distributed unevenly to its neighbors based on the relative weights.

Input: igraph.Graph.value_propagation(order=('topo','vertex_attribute'), discount = 0.05, mode = c('in', 'out'))
Output: array of leaf vertices (vertex IDs), array of leaf vertex weights (signed floats)

Use cases for the feature
Value propagation is a useful heuristic for open-pit mining resource-constrained project scheduling problems. In these problems, blocks are represented by vertices and the precedence relationship between blocks is represented by edges. Values from all blocks beneath the surface are projected onto the surface via precedence edges, from bottom to top. The result is a set of weights for blocks at the surface (i.e., vertices with no outbound edges) that indicate which blocks lead to higher net present value, where the present value is derived from a provided discount factor.

References
igraph forum

[szhorvat]

This needs some clarifications. It will also help to link some real use-cases (not just describe them, but link some references).

• Do you mean that you only do a single pass through vertices?
• Since you mention topological order, do you do this only on DAGs?
• Are you aware of applications which are not on DAGs? If so, which, and what order do they use?
• It's not entirely clear to me whether for a non-DAG it makes a difference if a vertex is updated based on its incoming links, or it updates its neighbours based on its outgoing links. The former seems more intuitive, but it'd be good to know how this is usually done/discussed.
• This should be fairly easy to implement in the high-level interfaces. Have you already done this, and are you requesting this for the C core for performance reasons?

It seems to me that if this is done, it'd be useful to implement a generalized version where one can control how the update to a vertex depends on its neighbours. Then there are performance tradeoffs on the generality of this update function: can the user choose an arbitrary function (unclear if this can be faster than a high-level implementation) or just control the parameters of a fixed function? It'd be good to see a number of applications of such value propagation to be able to decide what level of generality makes sense.

[scythetrigger]

• Do you mean that you only do a single pass through vertices?

  • Yes, only a single pass is done through the vertices.

• Since you mention topological order, do you do this only on DAGs?

  • Yes, only on DAGs.

• Are you aware of applications which are not on DAGs? If so, which, and what order do they use?

  • No, I am not aware of applications not on DAGs

• Have you already done this, and are you requesting this for the C core for performance reasons?

  • Yes, I have already implemented this with python-igraph! I am indeed requesting this for the C core for performance reasons.

• References

  • Embarrassingly, I do not have any references for this. I remember reading (nearly a year ago) about a similar application for an autonomous driving agent that used a value propagation heuristic to make decisions, but that is more describing and less linking. I will have to get back to you on this.