1、图与图学习
1）图的两个基本元素是点和边，是一种统一描述复杂事务的语言，常见的图有社交网络、推荐系统、化学分子结构。
2）图学习: Graph Learning。深度学习中的一个子领域，强调处理的数据对象为图；与一般深度学习的区别：能够方便地处理不规则数据（树、图），同时也可以处理规则数据（如图像）。
3）图学习的应用：
- 节点级别任务：金融诈骗检测（典型的节点分类）、自动驾驶中的3D点云目标检测
- 边级别任务：推荐系统（典型的边预测）
- 图级别任务：气味识别（典型的图分类）、发现“宇宙”
4）图学习是怎么做的：
- 图游走类算法：通过在图上的游走，获得多个节点序列，再利用 Skip Gram 模型训练得到节点表示（下节课内容）
- 图神经网络算法：端到端模型，利用消息传递机制实现。
- 知识图谱嵌入算法：专门用于知识图谱的相关算法。
2、图游走类模型(得到节点表示（Node Embedding）用于下游任务)
1）DeepWalk采样算法
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] # 保存游走路径？
walks_ids = np.arange(0, len(nodes)) # 有多少起始节点
cur_nodes = np.array(nodes) # 所有的起始节点
for l in range(walk_len):
"""选取有下一个节点的路径继续采样，否则结束"""
outdegree = self.outdegree(cur_nodes) # 当前节点出度
walk_mask = (outdegree != 0)
if not np.any(walk_mask):
break
cur_nodes = cur_nodes[walk_mask]
walks_ids = walks_ids[walk_mask]
outdegree = outdegree[walk_mask]
######################################
# 请在此补充代码采样出下一个节点
succ_nodes = self.successor(cur_nodes)
sample_index = np.floor(
np.random.rand(outdegree.shape[0]) * outdegree).astype("int64")
next_nodes = []
for s, ind, walk_id in zip(succ_nodes, sample_index, walks_ids):
walks[walk_id].append(s[ind])
next_nodes.append(s[ind])
######################################
cur_nodes = np.array(next_nodes)
return walks
2）Node2vec采样算法(DeepWalk的改进)
def node2vec_sample(succ, prev_succ, prev_node, p, q):
"""
输入：succ - 当前节点的下一个相邻节点id列表 list (num_neighbors,)
prev_succ - 前一个节点的下一个相邻节点id列表 list (num_neighbors,)
prev_node - 前一个节点id int
p - 控制回到上一节点的概率 float
q - 控制偏向DFS还是BFS float
输出：下一个节点id int
"""
##################################
# 请在此实现node2vec的节点采样函数
succ_len = len(succ)
prev_succ_len = len(prev_succ)
probs=[]
prob_sum = 0
prob = 0
prev_succ_set = np.asarray([])
for i in range(prev_succ_len):
prev_succ_set= np.append(prev_succ_set, prev_succ[i])
for i in range(succ_len):
if succ[i] == prev_node:
prob = 1. / p
elif np.where(prev_succ_set==succ[i]):
prob = 1.
elif np.where(prev_succ_set!=succ[i]):
prob = 1. / q
else:
prob=0
probs.append(prob)
prob_sum += prob
RAND_MAX = 65535
rand_num = float(np.random.randint(0, RAND_MAX+1))/RAND_MAX*prob_sum
sample_succ = 0
for i in range(succ_len):
rand_num -= probs[i]
if rand_num <= 0:
sample_succ = succ[i]
return sample_succ
##################################
return sampled_succ