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 采样。

参数:

  • g (DGLGraph) – 图。

  • nodes (Tensor) –

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

    张量的 dtype 必须与图的 ID 类型相同。张量必须与图位于同一设备上，或者当图固定在内存中时（UVA 采样）位于 GPU 上。

  • metapath (list[str 或 tuple of str], 可选) –

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

    与 length 互斥。

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

  • length (int, 可选) –

    随机游走的长度。

    与 metapath 互斥。

    仅当 metapath 为 None 时使用。

  • prob (str, 可选) –

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

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

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

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

  • restart_prob (float 或 Tensor, 可选) –

    在每次转换之前终止当前轨迹的概率。

    如果给定了张量，restart_prob 应该与图位于同一设备上，或者当图固定在内存中时（UVA 采样）位于 GPU 上，并且长度与 metapath 或 length 相同。

  • return_eids (bool, 可选) –

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

    默认值：False。

返回值:

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

  • eids (Tensor, 可选) – 一个 2 维边 ID 张量，形状为 (num_seeds, len(metapath))，如果 metapath 为 None，则形状为 (num_seeds, length)。仅当 return_eids 为 True 时返回。

  • types (Tensor) – 一个 1 维节点类型 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]))

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

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