算法思想
2021-10-09_17-04.png
参考资料
https://zhuanlan.zhihu.com/p/45167021
代码实现与注解
思路
- 理清successor，outdegree函数的输入输出
- 查看补全函数的返回类型--分析可能的结果--我最初的猜测：这walks应该是多个向量的集合，最后确实也是【[[],..]这样的结构多用于扩充，然后联想需要学习向量，所以想到向量递推的那种向量集合】
- 生成随机采样索引序列集 -- 这个需要匹配采样形状，以及索引阈值--我是参考一个示例修改的，感悟是: 利用随机数0~1，给rand传入指定shape，再乘以一个相同shape的数据，可以得到一个>=0, <=最大出度-1的值，这样就可以用来索引采样了
- 理清上下文变量关系，进行zip打包遍历到一起，然后进行聚合操作即可。
Code
%%writefile userdef_graph.py
from pgl.graph import Graph
import numpy as np
class UserDefGraph(Graph):
def random_walk(self, nodes, walk_len):
"""
输入：nodes - 当前节点id list (batch_size,)
walk_len - 最大路径长度 int
输出：以当前节点为起点得到的路径 list (batch_size, walk_len)
用到的函数
1. self.successor(nodes)
描述：获取当前节点的下一个相邻节点id列表
输入：nodes - list (batch_size,)
输出：succ_nodes - list of list ((num_successors_i,) for i in range(batch_size))
2. self.outdegree(nodes)
描述：获取当前节点的出度
输入：nodes - list (batch_size,)
输出：out_degrees - list (batch_size,)
"""
# 首先获得当前节点列表对应的一个向量
walks = [[node] for node in nodes]
# 游走路径中节点对应id号
walks_ids = np.arange(0, len(nodes))
# 当前节点情况
cur_nodes = np.array(nodes)
# 根据游走长度进行遍历--破出条件：1. range结束；2. outdegree==0【出度为零，没有可继续的节点】
for l in range(walk_len):
"""选取有下一个节点的路径继续采样，否则结束"""
# 计算当前节点的出度--也就是对应有哪些位置的邻近节点
outdegree = self.outdegree(cur_nodes)
# 根据出度来确定掩码--True， False--将出度为0的部分复制为False，反之True
walk_mask = (outdegree != 0)
# 判断是否没有可继续的节点情况--出度为0
if not np.any(walk_mask):
break
# 根据掩码获取可继续前进的节点，作为后边讨论的当前可前行节点
cur_nodes = cur_nodes[walk_mask]
# 获取掩码下，原节点id，组成新的work_ids用于后边讨论，但本身还是作为一个节点的标记，对应这是第几个节点
walks_ids = walks_ids[walk_mask]
# 根据掩码获取相应的不为0的出度--用于后边计算前行的路径
outdegree = outdegree[walk_mask]
# 返回可继续的节点集合 successor 可获取当前节点的下一个相邻节点id列表，
# 那么successor 计算出下一节点的集合后，我们需要从中随机取出一个节点--所以我们要创建随机采样的index_list（索引序列集）
succ_nodes = self.successor(cur_nodes)
# 创建index_list=>为了才到合适的index信息，采用np.floor与np.random,rand()实现：
# eg: np.floor(np.random.rand(outdegree.shape[0]) * outdegree).astype('int64')
# np.random.rand(outdegree.shape[0]): 根据出度集的形状来取得相应形状的随机数--这里体现游走的随机性
# np.random.rand(outdegree.shape[0]) * outdegree：利用生成的随机数与出度集对应元素相乘——这里得到一些列的随机数
# 随机数范围在0~最大出度值--保证路径有效
# np.floor(np.random.rand(outdegree.shape[0]) * outdegree)——实现向下取整，这样就得到了相应游走路径中接下来那个点的索引
sample_index = np.floor(np.random.rand(outdegree.shape[0]) * outdegree).astype('int64')
"""
具体实例：
np.floor(np.random.rand(20) * 3).astype('int64')
result: array([0, 1, 2, 1, 0, 0, 0, 0, 1, 1, 1, 2, 0, 2, 2, 2, 2, 1, 2, 0])
"""
# 知道了随机采样的序列集了，那么接下就是分配新的游走路径了
# 用于后边存放—— 装配有下一个节点的新路径
next_nodes = []
# succ_nodes：相邻节点id列表
# sample_index：对应出度生成的随即索引集
# walks_ids：游走路径中节点对应id号
for s, ind, walk_id in zip(succ_nodes, sample_index, walks_ids):
# 将节点列表、随机采样序列、游走路径中节点对应id号一一对应进行填充
# 为相应节点添加可以继续前行的节点，形成一条路径
walks[walk_id].append(s[ind])# walks=>[[], [], []]是这种形式的
# 同时获取接下来要重新讨论游走时所需的新节点
next_nodes.append(s[ind])
"""
如：从1走到了2，从3走到了7: [[1], [3]]=>[[1, 2], [3, 7]]
next_nodes.append(s[ind])
# 接下来自然就该考虑把新的2, 7 作为下一次游走时讨论出度的节点啦
"""
cur_nodes = np.array(next_nodes) # 将节点转换为np类型，方便一些操作运算--同时保证前后数据类型
# 并且list中，元素本质是对象。如：L = [1, 2, 3]，需要3个指针和三个整数对象，对于数值运算比较浪费内存和CPU
# Numpy提供了ndarray(N-dimensional array object)对象：存储单一数据类型的多维数组。
# 遍历完游走长度的次数，就可以返回得到的随机游走路径啦
return walks
print(np.floor(np.random.rand(20) * 3).astype('int64'))
