贵州省住房建设部网站中国手机网站

当前位置： 首页 > news >正文

贵州省住房建设部网站,中国手机网站,自己有网站想制作个程序,网络及it维护外包这里写目录标题一、Deepwalk1.1 预备知识1.2 Deepwalk介绍1.3 Embedding1.4 word2Vec 词向量#xff0c;词嵌入1.5 random Walk随机游走1.6 DeepWalk 核心代码Random WalkWord2vecDeepWalk应用1.7 DeepWalk优缺点二、Node2Vec2.1 图嵌入2.2 Node2Vec优化目标顶点序列采样策略2… 这里写目录标题一、Deepwalk1.1 预备知识1.2 Deepwalk介绍1.3 Embedding1.4 word2Vec 词向量词嵌入1.5 random Walk随机游走1.6 DeepWalk 核心代码Random WalkWord2vecDeepWalk应用1.7 DeepWalk优缺点二、Node2Vec2.1 图嵌入2.2 Node2Vec优化目标顶点序列采样策略2.3 理论上的实现2.4 Node2Vec代码实现学习算法node2vec核心代码node2vecWalk构造采样表node2vec应用2.5 Node2Vec与DeepWalk相比的优点与特点2.6 Node2Vec的优缺点参考文献一、Deepwalk 1.1 预备知识 机器学习深度学习基础语言模型word2vec 1.2 Deepwalk介绍 DeepWalk的思想类似word2vec使用图中节点与节点的共现关系来学习节点的向量表示。那么关键的问题就是如何来描述节点与节点的共现关系DeepWalk给出的方法是使用随机游走(RandomWalk)的方式在图中进行节点采样。 DeepwalkDeepwalkDeepwalk将graphgraphgraph的每一个节点编码为一个DDD维向量(Embedding)(无监督学习) Embedding中隐式包含了GraphGraphGraph中的社群连接结构信息可用于后续节点分类等下游任务监督学习 Deepwalk通过套用随机游走(Random walk generation)将图像转化为D维向量 1.3 Embedding 我们需要将图转化为计算机了解的向量所以我们需要使用embedding 1.4 word2Vec 词向量词嵌入 word2vec通过语料库中的句子序列来描述词与词的共现关系进而学习到词语的向量表示。 主要有两种方法 CBOW用边缘词去预测中心词 Skip-gram用输入的中心词去预测周围词 1.5 random Walk随机游走 RandomWalk是一种可重复访问已访问节点的深度优先遍历算法。给定当前访问起始节点从其邻居中随机采样节点作为下一个访问节点重复此过程直到访问序列长度满足预设条件。 获取足够数量的节点访问序列后使用skip-gram model 进行向量学习。 具体见[Datawhale][CS224W]图机器学习(四) 1.6 DeepWalk 核心代码 DeepWalk算法主要包括两个步骤第一步为随机游走采样节点序列第二步为使用skip-gram modelword2vec学习表达向量。 ①构建同构网络从网络中的每个节点开始分别进行Random Walk 采样得到局部相关联的训练数据 ②对采样数据进行SkipGram训练将离散的网络节点表示成向量化最大化节点共现使用Hierarchical Softmax来做超大规模分类的分类器 Random Walk 我们可以通过并行的方式加速路径采样在采用多进程进行加速时相比于开一个进程池让每次外层循环启动一个进程我们采用固定为每个进程分配指定数量的num_walks的方式这样可以最大限度减少进程频繁创建与销毁的时间开销。 deepwalk_walk方法对应上一节伪代码中第6行_simulate_walks对应伪代码中第3行开始的外层循环。最后的Parallel为多进程并行时的任务分配操作。 def deepwalk_walk(self, walk_length, start_node):walk [start_node]while len(walk) walk_length:cur walk[-1]cur_nbrs list(self.G.neighbors(cur))if len(cur_nbrs) 0:walk.append(random.choice(cur_nbrs))else:breakreturn walkdef _simulate_walks(self, nodes, num_walks, walk_length,):walks []for _ in range(num_walks):random.shuffle(nodes)for v in nodes: walks.append(self.deepwalk_walk(alk_lengthwalk_length, start_nodev))return walksresults Parallel(n_jobsworkers, verboseverbose, )(delayed(self._simulate_walks)(nodes, num, walk_length) for num inpartition_num(num_walks, workers))walks list(itertools.chain(*results))Word2vec 这里就偷个懒直接用gensim里的Word2Vec了。 from gensim.models import Word2Vec w2v_model Word2Vec(walks,sg1,hs1)DeepWalk应用 G nx.read_edgelist(../data/wiki/Wiki_edgelist.txt,create_usingnx.DiGraph(),nodetypeNone,data[(weight,int)])model DeepWalk(G,walk_length10,num_walks80,workers1) model.train(window_size5,iter3) embeddings model.get_embeddings()evaluate_embeddings(embeddings) plot_embeddings(embeddings)1.7 DeepWalk优缺点 优点 首个将深度学习和自然语言处理的思想用于图机器学习在系数标注节点分类场景下嵌入性能卓越 缺点 均匀随机游走没有偏向的游走方向Node2Vec需要大量随机游走序列训练基于随机游走管中窥豹。距离较远的两个节点无法相互影响。看不到全图信息。图神经网络无监督仅编码图的连接信息没有利用节点的属性特征没有真正用到神经网络和深度学习
二、Node2Vec 2.1 图嵌入 将数据转化为D维连续稠密的向量包含了原来的节点的多种信息 2.2 Node2Vec 优化目标 设 f(u)f(u)f(u)是将顶点 uuu 映射为embedding向量的映射函数,对于图中每个顶点uuu定义 Ns(u)N_s(u)Ns​(u) 为通过采样策略 SSS采样出的顶点 uuu的近邻顶点集合。 node2vec优化的目标是给定每个顶点条件下令其近邻顶点如何定义近邻顶点很重要出现的概率最大。 maxf∑u∈VlogPr(Ns(U)∣f(u))maxf\sum{u\in V}log Pr(N_s(U)|f(u))maxf​∑u∈V​logPr(Ns​(U)∣f(u)) 为了将上述最优化问题可解文章提出两个假设 条件独立性假设 假设给定源顶点下其近邻顶点出现的概率与近邻集合中其余顶点无关。 Pr(Ns(u)∣f(u))∏ni∣f(u)Pr(ni∣f(u))Pr(Ns(u)|f(u))\prod{n_i|f(u)}Pr(n_i|f(u))Pr(Ns​(u)∣f(u))∏ni​∣f(u)​Pr(ni​∣f(u)) 特征空间对称性假设 这里是说一个顶点作为源顶点和作为近邻顶点的时候共享同一套embedding向量。(对比LINE中的2阶相似度一个顶点作为源点和近邻点的时候是拥有不同的embedding向量的) 在这个假设下上述条件概率公式可表示为 Pr(ni∣f(u))expf(ni)⋅f(u)∑v∈Vexpf(v)⋅f(u)Pr(n_i|f(u)){expf(ni)\cdot f(u)}\over{\sum{v\in V}expf(v)\cdot f(u)}∑v∈V​expf(v)⋅f(u)Pr(ni​∣f(u))expf(ni​)⋅f(u)​ 根据以上两个假设条件最终的目标函数表示为 由于归一化因子 的计算代价高所以采用负采样技术优化。 顶点序列采样策略 node2vec依然采用随机游走的方式获取顶点的近邻序列不同的是node2vec采用的是一种有偏的随机游走。 给定当前顶点 v 访问下一个顶点 x 的概率为 πvx\pi{vx}πvx​ 是顶点 v 和顶点 x 之间的未归一化转移概率 Z 是归一化常数。 node2vec引入两个超参数 p 和 q 来控制随机游走的策略假设当前随机游走经过边 (t,v) 到达顶点 v设 ωvx\omega{vx}ωvx​ 是顶点 v 和 x 之间的边权 dtxd{tx}dtx​为顶点 t 和顶点 x 之间的最短路径距离。 下面讨论超参数 p 和 q 对游走策略的影响 Return parameter,p 参数p控制重复访问刚刚访问过的顶点的概率。 注意到p仅作用于 dtxd{tx}dtx​0 的情况而dtxd_{tx}dtx​0 表示顶点 x 就是访问当前顶点 v 之前刚刚访问过的顶点。 那么若 p 较高则访问刚刚访问过的顶点的概率会变低反之变高。 In-out papameter,q q 控制着游走是向外还是向内若 q1 随机游走倾向于访问和 t 接近的顶点(偏向BFS)。若 q1 倾向于访问远离 t 的顶点(偏向DFS)。 下面的图描述的是当从 t 访问到 v 时决定下一个访问顶点时每个顶点对应的 α\alphaα 。 设定p,q进行有偏随机游走 q节点小时更愿意进行BFS,p节点小时更愿意进行DFS 2.3 理论上的实现 2.4 Node2Vec代码实现 学习算法 采样完顶点序列后剩下的步骤就和deepwalk一样了用word2vec去学习顶点的embedding向量。 值得注意的是node2vecWalk中不再是随机抽取邻接点而是按概率抽取node2vec采用了Alias算法进行顶点采样。 Alias Method:时间复杂度O(1)的离散采样方法125 赞同 · 23 评论文章 node2vec核心代码 node2vecWalk 通过上面的伪代码可以看到node2vec和deepwalk非常类似主要区别在于顶点序列的采样策略不同所以这里我们主要关注node2vecWalk的实现。 由于采样时需要考虑前面2步访问过的顶点所以当访问序列中只有1个顶点时直接使用当前顶点和邻居顶点之间的边权作为采样依据。 当序列多余2个顶点时使用文章提到的有偏采样。 def node2vec_walk(self, walk_length, start_node):G self.G alias_nodes self.alias_nodes alias_edges self.alias_edgeswalk [start_node]while len(walk) walk_length: cur walk[-1] cur_nbrs list(G.neighbors(cur)) if len(cur_nbrs) 0: if len(walk) 1: walk.append(cur_nbrs[alias_sample(alias_nodes[cur][0], alias_nodes[cur][1])]) else: prev walk[-2] edge (prev, cur) next_node cur_nbrs[alias_sample(alias_edges[edge][0],alias_edges[edge][1])] walk.append(next_node) else: breakreturn walk构造采样表 preprocess_transition_probs分别生成alias_nodes和alias_edgesalias_nodes存储着在每个顶点时决定下一次访问其邻接点时需要的alias表不考虑当前顶点之前访问的顶点。alias_edges存储着在前一个访问顶点为 t 当前顶点为 v 时决定下一次访问哪个邻接点时需要的alias表。 get_alias_edge方法返回的是在上一次访问顶点 t 当前访问顶点为 v 时到下一个顶点 x 的未归一化转移概率
def get_alias_edge(self, t, v):G self.G p self.p q self.qunnormalized_probs [] for x in G.neighbors(v): weight G[v][x].get(weight, 1.0)# w_vx if x t:# d_tx 0 unnormalized_probs.append(weight/p) elif G.has_edge(x, t):# d_tx 1 unnormalized_probs.append(weight) else:# d_tx 2 unnormalized_probs.append(weight/q) norm_const sum(unnormalized_probs) normalized_probs [float(u_prob)/norm_const for u_prob in unnormalized_probs]return create_alias_table(normalized_probs)def preprocess_transition_probs(self):G self.Galias_nodes {} for node in G.nodes(): unnormalized_probs [G[node][nbr].get(weight, 1.0) for nbr in G.neighbors(node)] norm_const sum(unnormalized_probs) normalized_probs [float(u_prob)/norm_const for u_prob in unnormalized_probs] alias_nodes[node] create_alias_table(normalized_probs)alias_edges {}for edge in G.edges(): alias_edges[edge] self.get_alias_edge(edge[0], edge[1])self.alias_nodes alias_nodes self.alias_edges alias_edgesreturnnode2vec应用 使用node2vec在wiki数据集上进行节点分类任务和可视化任务。 wiki数据集包含 2,405 个网页和17,981条网页之间的链接关系以及每个网页的所属类别。 通过简单的超参搜索这里使用p0.25,q4的设置。 G nx.read_edgelist(../data/wiki/Wiki_edgelist.txt,create_usingnx.DiGraph(),nodetypeNone,data[(weight,int)])model Node2Vec(G,walk_length10,num_walks80,p0.25,q4,workers1) model.train(window_size5,iter3)
embeddings model.get_embeddings()evaluate_embeddings(embeddings) plot_embeddings(embeddings)2.5 Node2Vec与DeepWalk相比的优点与特点 优点 Node2Vec解决图嵌入问题将图中的每个节点映射为一个向量嵌入向量嵌入包含了节点的语义信息相邻社群和功能角色语义相似的节点向量嵌入的距离也近。向量嵌入用于后续的分类聚类link Predictin推荐等任务。 特点 在DeepWalk完全随机游走的基础上Node2Vec增加p,q参数实现有偏随机游走。不同的p,q组合对应了不同的探索范围和节点语义。DFS深度优先探索相邻的节点向量嵌入距离相近BFS广度优先探索相同功能角色的节点向量嵌入距离相近。DeepWalk时Node2Vec在p1,q1的特例
2.6 Node2Vec的优缺点 优点 首次通过调节p,q值实现了有偏随机游走探索节点社群功能等不同属性首次将节点分类用于Link Prediction可解释性可扩展性好性能卓越 缺点 需要大量随机游走序列训练距离较远的两个界定啊无法直接相互影响。看不到全图信息。图神经网络无监督仅编码图的连接信息没有利用节点的属性特征图卷积没有真正用到神经网络和深度学习
参考文献 [1] 斯坦福CS224W图机器学习、图神经网络、知识图谱【同济子豪兄】 [2] 【Graph Embedding】DeepWalk算法原理实现和应用 [3] 【Graph Embedding】node2vec算法原理实现和应用