[Feature] Random Walk with Restart terminates the random walk rather than restarting

[hwangyeong]

❓ Questions and Help about Random Walk with Restart

Thanks to the developers for their efforts to provide us with an excellent framework.

The restart random walk module in version 0.4.3, dgl.contrib.sampling.random_walk_with_restart, is not enough to be replaced by dgl.sampling.rand_walk in the current version.

In the current version, the parameter restart_prob means that the walk is "terminated" with a certain probability instead of "restarted".

As the following example shows, the walk is terminated without restarting.

import dgl
import networkx as nx

nxgraph = nx.Graph()
nxgraph.add_edges_from([(0,1), (1,2), (1,3), (2,0), (3,0)])
g1 = dgl.from_networkx(nxgraph)

print(dgl.sampling.random_walk(g1, [0], restart_prob=0.5, length=10))

output: >>> (tensor([[ 0, 2, 0, -1, -1, -1, -1, -1, -1, -1, -1]]), tensor([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]))

This walk is shutting down at 0->2->0. So, what can I do for attaining "restart"?

[BarclayII]

I think dgl.contrib.sampling.random_walk_with_restart also terminates the random walk rather than restarting in the same trace. Your concern is legit though, and I think having real restarts make sense.