区块链技术博客
www.b2bchain.cn

详解Graph-Embedding之Line

这篇文章主要介绍了详解Graph-Embedding之Line的讲解,通过具体代码实例进行21042 讲解,并且分析了详解Graph-Embedding之Line的详细步骤与相关技巧,需要的朋友可以参考下https://www.b2bchain.cn/?p=21042

本文实例讲述了2、树莓派设置连接WiFi,开启VNC等等的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7039.html。具体如下:

网易的几篇关于GAT和GCN的模型改造有点难,准备先拿其用过的Graph Embedding作为入门练手。

目录

前言

算法详解


前言

原文链接:Line -GraphEmbedding

本来想从DeepWalk写起的,感觉最近事情有点多,这个方法又有点简单,就不想写了,具体可以看以下几个链接:一言以蔽之,采用深度遍历的方法,进行随机游走,得到许多句子作为训练库,然后使用skip-gram学习表示向量,这个表示向量就是embedding。

DeepWalk:DeepWalk;生动解释;通俗理解;代码讲解

下面步入正题,Line,同样一言以蔽之,使用广度遍历的方法,同时学习first-order和second-order两个相似度,用这两个相似度来做embedding。first-oredr相似度是指与节点相邻的节点与其相似(相似的含义是指embedding后的空间维度内这两个节点相近),second-order相似度是指与某节点具有相同neighbors的节点相似,如下图所示:6和7相似是因为直接相连及具有较大的weights(first),5和6相似是因为二者具有相同的邻居(second)。最后将这个两个相似度concat起来作为最后表示。

Line的适用范围:据作者所说是all in。但存在两个局限,第一不能很好处理新加入节点(尤其是这个新加入结点与其他结点没有关系的时候);第二,不能很好处理多阶相似度(没有考虑neighbor的neighbors)

详解Graph-Embedding之Line

先验知识:在进入正题之前,有几个先验知识必不可少,不然会一知半解,KL散度(用于衡量两个分布之间的相似程度),Alias Method(按照给定的概率分布进行采样,原文中防止梯度爆炸),负采样(随机选取一些负样本而非全部的负样本优化计算)

算法详解

优化目标一:使得embedding后的一阶相似度与真实共现的概率分布相同,即下面两个公式的KL散度(公式3)尽量的小:

详解Graph-Embedding之Line

详解Graph-Embedding之Line

详解Graph-Embedding之Line

# KL散度计算公式 def line_loss(y_true, y_pred):     return -K.mean(K.log(K.sigmoid(y_true*y_pred)))

优化目标二:使得embedding后的二阶相似度与真实条件概率分布相同(即在给定i下出现j的概率),即下面两个公式的KL散度尽量的小(这个λ代表节点的重要程度,可以通过PageRank事先得到),为了统一形式,化为第4个公式:

详解Graph-Embedding之Line

详解Graph-Embedding之Line

详解Graph-Embedding之Line

详解Graph-Embedding之Line

创新点1:由于在优化目标2中需要计算条件概率,会导致算法复杂程度显著增加,就使用了负采样(简单来说我们仅采集几个中心词对应的负样本对目标函数进行训练)的方法,加快模型训练速度。

详解Graph-Embedding之Line

def get_negatives(all_contexts, sampling_weights, K):     all_negatives, neg_candidates, i = [], [], 0     population = list(range(len(sampling_weights)))     for contexts in all_contexts:         negatives = []         while len(negatives) < len(contexts) * K:             if i == len(neg_candidates):                 # 根据每个词的权重(sampling_weights)随机生成k个词的索引作为噪声词。                 # 为了高效计算,可以将k设得稍大一点                 i, neg_candidates = 0, random.choices(                     population, sampling_weights, k=int(1e5))             neg, i = neg_candidates[i], i + 1             # 噪声词不能是背景词             if neg not in set(contexts):                 negatives.append(neg)         all_negatives.append(negatives)     return all_negatives  sampling_weights = [counter[w]**0.75 for w in idx_to_token] all_negatives = get_negatives(all_contexts, sampling_weights, 5)

创新点2:无论是优化目标1还是优化目标2,都有一个w直接乘在目标函数上,这会导致梯度爆炸现象(假如这个weights很大),作者一开始想将所有的带权边变成N*1(比如w为5,我就变成5个w为1的边),但这样存储消耗太大,作者就使用了Edge Sampling,只Sample出一部分带权边进行梯度下降(当然需要保证Sample的概率分布与原分布近似,也就是Alias Method。)

def _gen_sampling_table(self): # 顶点采样和负采样的采样表制作     # create sampling table for vertex     power = 0.75     numNodes = self.node_size     node_degree = np.zeros(numNodes)  # out degree     node2idx = self.node2idx      for edge in self.graph.edges():         node_degree[node2idx[edge[0]]                     ] += self.graph[edge[0]][edge[1]].get('weight', 1.0)      total_sum = sum([math.pow(node_degree[i], power)                         for i in range(numNodes)])     norm_prob = [float(math.pow(node_degree[j], power)) /                     total_sum for j in range(numNodes)]     # 主要就是为了计算某个节点出现的概率     self.node_accept, self.node_alias = create_alias_table(norm_prob)      # create sampling table for edge     numEdges = self.graph.number_of_edges()     total_sum = sum([self.graph[edge[0]][edge[1]].get('weight', 1.0)                         for edge in self.graph.edges()])     norm_prob = [self.graph[edge[0]][edge[1]].get('weight', 1.0) *                     numEdges / total_sum for edge in self.graph.edges()]      self.edge_accept, self.edge_alias = create_alias_table(norm_prob)
import numpy as np  def create_alias_table(area_ratio):     """     # 其实这里就是维护两个队列,使得采样符合原概率分布     :param area_ratio: sum(area_ratio)=1     :return: accept,alias     """     l = len(area_ratio)     accept, alias = [0] * l, [0] * l     small, large = [], []     area_ratio_ = np.array(area_ratio) * l     for i, prob in enumerate(area_ratio_):         if prob < 1.0:             small.append(i)         else:             large.append(i)      while small and large:         small_idx, large_idx = small.pop(), large.pop()         accept[small_idx] = area_ratio_[small_idx]         alias[small_idx] = large_idx         area_ratio_[large_idx] = area_ratio_[large_idx] -              (1 - area_ratio_[small_idx])         if area_ratio_[large_idx] < 1.0:             small.append(large_idx)         else:             large.append(large_idx)      while large:         large_idx = large.pop()         accept[large_idx] = 1     while small:         small_idx = small.pop()         accept[small_idx] = 1      return accept, alias  def alias_sample(accept, alias):     """     :param accept:     :param alias:     :return: sample index     """     N = len(accept)     i = int(np.random.random()*N)     r = np.random.random()     if r < accept[i]:         return i     else:         return alias[i]

 

本文转自互联网,侵权联系删除详解Graph-Embedding之Line

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 详解Graph-Embedding之Line
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们