dgl.sampling.random_walk

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

根据给定的元路径，从起始节点数组中生成随机游走轨迹。

每个起始节点将生成一个跟踪，该跟踪

  1. 从给定的节点开始，并将 t 设置为 0。

  2. 从当前节点选择并沿着边类型 metapath[t] 遍历。

  3. 如果没有找到边，则停止。否则，增加 t 并转到步骤2。

要为单个节点生成多个轨迹，您可以多次指定相同的节点。

返回的轨迹长度均为 len(metapath) + 1，其中第一个节点是起始节点本身。

如果随机游走提前停止，DGL 会用 -1 填充轨迹以保持相同的长度。

此函数支持在GPU和UVA采样上的图形。

Parameters:

  • g (DGLGraph) – 图。

  • nodes (Tensor) –

    随机游走轨迹开始的节点ID张量。

    该张量必须与图的ID类型具有相同的数据类型。 该张量必须与图位于同一设备上，或者 当图被固定时（UVA采样）位于GPU上。

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

    元路径，指定为边类型的列表。

    与 length 互斥。

    如果省略，DGL 假设 g 只有一个节点和边类型。在这种情况下，参数 length 指定随机游走轨迹的长度。

  • length (int, optional) –

    随机游走的长度。

    与 metapath 互斥。

    仅在 metapath 为 None 时使用。

  • prob (str, optional) –

    图上存储的边特征张量的名称，该张量包含与每条边相关的（未归一化的）概率，用于选择下一个节点。

    特征张量必须是非负的，并且所有节点的出边的概率之和必须为正（尽管它们不必总和为一）。否则，结果将是未定义的。

    特征张量必须与图位于同一设备上。

    如果省略，DGL 假设邻居是均匀选择的。

  • restart_prob (float 或 Tensor, 可选) –

    在每次转换之前终止当前跟踪的概率。

    如果给定一个张量，restart_prob 应该与图在同一设备上， 或者在图被固定时在 GPU 上（UVA 采样）， 并且与 metapath 或 length 具有相同的长度。

  • return_eids (bool, optional) –

    如果为True，则额外返回遍历的边ID。

    默认值：False。

Returns:

  • traces (Tensor) – 一个二维节点ID张量，形状为 (num_seeds, len(metapath) + 1) 或 (num_seeds, length + 1) 如果 metapath 为 None。

  • eids (Tensor, optional) – 一个二维边ID张量，形状为 (num_seeds, len(metapath)) 或 (num_seeds, length) 如果 metapath 为 None。仅在 return_eids 为 True 时返回。

  • types (Tensor) – 一个一维节点类型ID张量，形状为 (len(metapath) + 1) 或 (length + 1)。 类型ID与原始图 g 中的类型ID匹配。

示例

以下创建一个同构图： >>> g1 = dgl.graph(([0, 1, 1, 2, 3], [1, 2, 3, 0, 0]))

正态随机游走：

>>> 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]))

或者返回边的ID：

>>> 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]))

第一个张量表示每个种子节点的随机游走路径。 第二个张量中的第j个元素表示每条路径中第j个节点的节点类型ID。 在这种情况下，它返回所有0。

带重启的随机游走：

>>> 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]))

非均匀随机游走：

>>> 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]))

基于元路径的随机游走：

>>> 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]))

基于元路径的随机游走，仅在项目上重新启动（即在遍历“查看”关系后）：

>>> 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]))