dgl.sampling

dgl.sampling 包含用于通过随机游走、邻居采样等从图中采样的运算符和实用程序。它们通常与 dgl.dataloading 包中的 DataLoader 一起使用。

Random walk 随机游走

random_walk

根据给定的元路径，从起始节点数组生成随机行走轨迹。
每个开始节点都将生成一个轨迹，该轨迹
1. 从给定节点开始，将 t 设置为0。
2. 从当前节点沿着边类型 metapath[t] 拾取和遍历。
3. 如果找不到边，则停止。否则，递增 t 并转到步骤2。
要为单个节点生成多个轨迹，可以多次指定同一节点。
返回的跟踪都具有长度 len(metapath) + 1 ，其中第一个节点是起始节点本身。
如果随机游走提前停止，DGL会用-1填充轨迹，使其具有相同的长度。
此函数支持GPU上的图形和UVA采样。

Usage:dgl.sampling.random_walk(g, nodes, *, metapath=None, length=None, prob=None, restart_prob=None, return_eids=False)

Parameters:

• g (DGLGraph) – 输入图。
• nodes (tensor) – 起始节点。随机游走轨迹开始的节点ID张量。张量必须与图的ID类型具有相同的dtype。张量必须与图形位于同一设备上，或者在图形固定时位于GPU上（UVA采样）。
• metapath (list[str or tuple of str], optional) – 元路径。元路径，指定为边类型的列表。与 length 互斥。如果省略，DGL假设 g 只有一个节点和边类型。在这种情况下，参数 length 指定随机游走轨迹的长度。
• length (int, optional) 随机游走的长度。与 metapath 互斥。 仅在 metapath 为“None”时使用。
• prob (str, optional) 图上的边特征张量的名称，存储与每条边相关联的（未归一化的）概率，用于选择下一个节点。特征张量必须是非负的，并且所有节点的出站边缘的概率之和必须为正（尽管它们的总和不必为1）。否则结果将是未定义的。特征张量必须与图形位于同一设备上。如果忽略，DGL假定均匀拾取相邻对象。
• restart_prob (float or Tensor, optional) 在每次转换之前终止当前跟踪的概率。如果给定了张量，则 restart_prob 应该与图形位于同一设备上，或者在图形固定（UVA采样）时位于GPU上，并且与 metapath 或 length 具有相同的长度。
• return_eids (bool, optional) 如果为True，则另外返回遍历的边ID。Default: False.

Returns:

• traces（Tensor）-二维节点ID张量，形状为 (num_seeds, len(metapath) + 1) 或 (num_seeds, length + 1) （如果 metapath 为None）。
• eids（Tensor，可选）-二维边ID张量，形状为 (num_seeds, len(metapath)) 或 (num_seeds, length) （如果 metapath 为None）。只有在 return_eids 为True时才返回。
• types（Tensor）-一维节点类型ID张量，形状为 (len(metapath) + 1) 或 (length + 1) 。类型ID与原始图 g 中的类型ID匹配。

Examples:
下面的代码创建了一个同构图：> 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]))

或返回边缘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]))

node2vec_random_walk

基于node 2 vec模型，从起始节点数组生成随机游走轨迹。
返回的轨迹都具有长度 walk_length + 1 ，其中第一个节点是起始节点本身。
请注意，如果随机游走提前停止，DGL会用-1填充迹线，使其具有相同的长度。

Usage:dgl.sampling.node2vec_random_walk(g, nodes, p, q, walk_length, prob=None, return_eids=False)

Parameters:

• g (DGLGraph) 该图必须在CPU上。注意，node 2 vec只支持同构图。
• nodes (Tensor) 随机游走轨迹开始的节点ID张量。张量必须在CPU上，并且必须具有与图的ID类型相同的dtype。
• p (float) 在遍历中立即重新访问节点的可能性。
• q (float) 在广度优先策略和深度优先策略之间进行插值的控制参数。
• walk_length (int) 随机游走的长度。
• prob (str, optional) 图上的边特征张量的名称，存储与每条边相关联的（未归一化的）概率，用于选择下一个节点。特征张量必须是非负的，并且所有节点的出站边缘的概率之和必须为正（尽管它们的总和不必为1）。否则结果将是未定义的。如果忽略，DGL假定均匀拾取相邻对象。
• return_eids (bool, optional) 如果为True，则另外返回遍历的边ID。Default: False.

Returns:

• traces (Tensor) 形状为 (num_seeds, walk_length + 1) 的二维节点ID张量。
• eids (Tensor, optional) 一个二维边ID张量，形状为 (num_seeds, length) 。只有在 return_eids 为True时才返回。

Examples:

>>> g1 = dgl.graph(([0, 1, 1, 2, 3], [1, 2, 3, 0, 0]))
>>> dgl.sampling.node2vec_random_walk(g1, [0, 1, 2, 0], 1, 1, walk_length=4)
tensor([[0, 1, 3, 0, 1],
        [1, 2, 0, 1, 3],
        [2, 0, 1, 3, 0],
        [0, 1, 2, 0, 1]])

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

pack_traces

Neighbor sampling 邻域抽样法

Negative sampling 负采样