dgl.sampling.random_walk

dgl.sampling.random_walk(g, nodes, *, metapath=None, length=None, prob=None, restart_prob=None, return_eids=False)[source]

Generate random walk traces from an array of starting nodes based on the given metapath.

Each starting node will have one trace generated, which

  1. Start from the given node and set t to 0.

  2. Pick and traverse along edge type metapath[t] from the current node.

  3. If no edge can be found, halt. Otherwise, increment t and go to step 2.

To generate multiple traces for a single node, you can specify the same node multiple times.

The returned traces all have length len(metapath) + 1, where the first node is the starting node itself.

If a random walk stops in advance, DGL pads the trace with -1 to have the same length.

This function supports the graph on GPU and UVA sampling.

Parameters:

  • g (DGLGraph) – The graph.

  • nodes (Tensor) –

    Node ID tensor from which the random walk traces starts.

    The tensor must have the same dtype as the ID type of the graph. The tensor must be on the same device as the graph or on the GPU when the graph is pinned (UVA sampling).

  • metapath (list[str or tuple of str], optional) –

    Metapath, specified as a list of edge types.

    Mutually exclusive with length.

    If omitted, DGL assumes that g only has one node & edge type. In this case, the argument length specifies the length of random walk traces.

  • length (int, optional) –

    Length of random walks.

    Mutually exclusive with metapath.

    Only used when metapath is None.

  • prob (str, optional) –

    The name of the edge feature tensor on the graph storing the (unnormalized) probabilities associated with each edge for choosing the next node.

    The feature tensor must be non-negative and the sum of the probabilities must be positive for the outbound edges of all nodes (although they don’t have to sum up to one). The result will be undefined otherwise.

    The feature tensor must be on the same device as the graph.

    If omitted, DGL assumes that the neighbors are picked uniformly.

  • restart_prob (float or Tensor, optional) –

    Probability to terminate the current trace before each transition.

    If a tensor is given, restart_prob should be on the same device as the graph or on the GPU when the graph is pinned (UVA sampling), and have the same length as metapath or length.

  • return_eids (bool, optional) –

    If True, additionally return the edge IDs traversed.

    Default: False.

Returns:

  • traces (Tensor) – A 2-dimensional node ID tensor with shape (num_seeds, len(metapath) + 1) or (num_seeds, length + 1) if metapath is None.

  • eids (Tensor, optional) – A 2-dimensional edge ID tensor with shape (num_seeds, len(metapath)) or (num_seeds, length) if metapath is None. Only returned if return_eids is True.

  • types (Tensor) – A 1-dimensional node type ID tensor with shape (len(metapath) + 1) or (length + 1). The type IDs match the ones in the original graph g.

Examples

The following creates a homogeneous graph: >>> g1 = dgl.graph(([0, 1, 1, 2, 3], [1, 2, 3, 0, 0]))

Normal random walk:

>>> dgl.sampling.random_walk(g1, [0, 1, 2, 0], length=4)
(tensor([[0, 1, 2, 0, 1],
         [1, 3, 0, 1, 3],
         [2, 0, 1, 3, 0],
         [0, 1, 2, 0, 1]]), tensor([0, 0, 0, 0, 0]))

Or returning edge IDs:

>>> dgl.sampling.random_walk(g1, [0, 1, 2, 0], length=4, return_eids=True)
(tensor([[0, 1, 2, 0, 1],
         [1, 3, 0, 1, 2],
         [2, 0, 1, 3, 0],
         [0, 1, 3, 0, 1]]),
 tensor([[0, 1, 3, 0],
         [2, 4, 0, 1],
         [3, 0, 2, 4],
         [0, 2, 4, 0]]),
 tensor([0, 0, 0, 0, 0]))

The first tensor indicates the random walk path for each seed node. The j-th element in the second tensor indicates the node type ID of the j-th node in every path. In this case, it is returning all 0.

Random walk with restart:

>>> dgl.sampling.random_walk_with_restart(g1, [0, 1, 2, 0], length=4, restart_prob=0.5)
(tensor([[ 0, -1, -1, -1, -1],
         [ 1,  3,  0, -1, -1],
         [ 2, -1, -1, -1, -1],
         [ 0, -1, -1, -1, -1]]), tensor([0, 0, 0, 0, 0]))

Non-uniform random walk:

>>> g1.edata['p'] = torch.FloatTensor([1, 0, 1, 1, 1])     # disallow going from 1 to 2
>>> dgl.sampling.random_walk(g1, [0, 1, 2, 0], length=4, prob='p')
(tensor([[0, 1, 3, 0, 1],
         [1, 3, 0, 1, 3],
         [2, 0, 1, 3, 0],
         [0, 1, 3, 0, 1]]), tensor([0, 0, 0, 0, 0]))

Metapath-based random walk:

>>> g2 = dgl.heterograph({
...     ('user', 'follow', 'user'): ([0, 1, 1, 2, 3], [1, 2, 3, 0, 0]),
...     ('user', 'view', 'item'): ([0, 0, 1, 2, 3, 3], [0, 1, 1, 2, 2, 1]),
...     ('item', 'viewed-by', 'user'): ([0, 1, 1, 2, 2, 1], [0, 0, 1, 2, 3, 3])
>>> dgl.sampling.random_walk(
...     g2, [0, 1, 2, 0], metapath=['follow', 'view', 'viewed-by'] * 2)
(tensor([[0, 1, 1, 1, 2, 2, 3],
         [1, 3, 1, 1, 2, 2, 2],
         [2, 0, 1, 1, 3, 1, 1],
         [0, 1, 1, 0, 1, 1, 3]]), tensor([0, 0, 1, 0, 0, 1, 0]))

Metapath-based random walk, with restarts only on items (i.e. after traversing a β€œview” relationship):

>>> dgl.sampling.random_walk(
...     g2, [0, 1, 2, 0], metapath=['follow', 'view', 'viewed-by'] * 2,
...     restart_prob=torch.FloatTensor([0, 0.5, 0, 0, 0.5, 0]))
(tensor([[ 0,  1, -1, -1, -1, -1, -1],
         [ 1,  3,  1,  0,  1,  1,  0],
         [ 2,  0,  1,  1,  3,  2,  2],
         [ 0,  1,  1,  3,  0,  0,  0]]), tensor([0, 0, 1, 0, 0, 1, 0]))