上篇談到了deepwalk,整體流程就是按均勻分布從當(dāng)前節(jié)點(diǎn)走到下一個(gè)節(jié)點(diǎn),從而采樣到一條條“句子”,但是這樣采樣方式一定是對(duì)的嗎?邊上是否有權(quán)重影響呢?走回頭路的概率也是等于選擇其他鄰居節(jié)點(diǎn)的.為了使得walk的更合理,node2vec這篇論文給了一個(gè)通用的“游走”框架.同樣是通過(guò)游走產(chǎn)生句子,然后通過(guò)w2v產(chǎn)出向量.

DOTA：大有可為的GNN：DeepWalk

Node2vec

BFS和DFS大家再熟悉不過(guò),node2vec就是結(jié)合了這兩種方式進(jìn)行采樣.為什么要結(jié)合這兩種方式呢?因?yàn)閷?duì)于圖而言,我們希望每個(gè)節(jié)點(diǎn)最終學(xué)到的向量既表達(dá)了同質(zhì)關(guān)系也表達(dá)了拓?fù)潢P(guān)系.比如上圖中u和S1是相似的,因?yàn)樗麄冎g空間上相近.又比如u和S6是相似的,雖然u和S6之間距離較遠(yuǎn),但是因?yàn)閡和S6周圍都圍繞了4個(gè)節(jié)點(diǎn),所以他們從拓?fù)渖峡词穷愃频?所以如何才能讓學(xué)到的向量能表達(dá)這種信息呢?node2vec就提出了一種隨機(jī)游走的框架,如下圖:

每個(gè)邊都有權(quán)重,當(dāng)前節(jié)點(diǎn)的所有邊權(quán)重歸一化后就是當(dāng)前節(jié)點(diǎn)到其他節(jié)點(diǎn)的概率.從上圖中我們可以看到,一共有3種類型的邊權(quán)重,第一種是<v,t>表示當(dāng)前節(jié)點(diǎn)v和上一個(gè)節(jié)點(diǎn)之間的邊權(quán)重為1/p,第二種是<v,x1>表示當(dāng)前節(jié)點(diǎn)和臨接上一個(gè)節(jié)點(diǎn)t的邊權(quán)重為1,第三種就是<v, other>表示與其他節(jié)點(diǎn)的邊權(quán)重為1/q.聰明的煉丹師已經(jīng)發(fā)現(xiàn),只要p=q=1,就是deepwalk.通過(guò)這種框架,如果p在0~1表示算法偏向于走回頭路,如果p>1則算法偏向于遠(yuǎn)離上一個(gè)節(jié)點(diǎn).同理如果q在0~1之間,則算法偏向于選擇遠(yuǎn)離t,否則傾向于接近t.整個(gè)算法表示如下所示:

雖然有了一個(gè)通用框架是好事,但是我們需要調(diào)的參數(shù)也多了,我們看看實(shí)驗(yàn)中調(diào)了哪些參數(shù),如下所示:

我們可以發(fā)現(xiàn),參數(shù)對(duì)F1-score的影響較大,因此要用的煉丹師們要耐心去調(diào).從實(shí)驗(yàn)結(jié)果來(lái)看,node2vec也表現(xiàn)較優(yōu).

代碼

這里代碼相較于deepwalk要稍微復(fù)雜一些,圖用networkx進(jìn)行構(gòu)建,構(gòu)建過(guò)程不再贅述.

# 核心代碼 # 先由這個(gè)函數(shù)得到計(jì)算好的邊權(quán)重 def preprocess_transition_probs(self):''' Preprocessing of transition probabilities for guiding the random walks. '''G = self.Gis_directed = self.is_directedalias_nodes = {}for node in G.nodes():unnormalized_probs = [G[node][nbr]['weight'] for nbr in sorted(G.neighbors(node))]norm_const = sum(unnormalized_probs)normalized_probs = [float(u_prob)/norm_const for u_prob in unnormalized_probs]alias_nodes[node] = alias_setup(normalized_probs)alias_edges = {}triads = {}if is_directed:for edge in G.edges():alias_edges[edge] = self.get_alias_edge(edge[0], edge[1])else:for edge in G.edges():alias_edges[edge] = self.get_alias_edge(edge[0], edge[1])alias_edges[(edge[1], edge[0])] = self.get_alias_edge(edge[1], edge[0])self.alias_nodes = alias_nodesself.alias_edges = alias_edges# 再由這個(gè)函數(shù)找到路徑 def node2vec_walk(self, walk_length, start_node):''' Simulate a random walk starting from start node. start_node 起點(diǎn) walk_length 要走的步數(shù) '''G = self.Galias_nodes = self.alias_nodesalias_edges = self.alias_edgeswalk = [start_node]while len(walk) < walk_length:cur = walk[-1]cur_nbrs = sorted(G.neighbors(cur))if len(cur_nbrs) > 0:# 如果是root,則沒(méi)有上一個(gè)節(jié)點(diǎn)# 兩種情況下計(jì)算概率的方式不同if len(walk) == 1:walk.append(cur_nbrs[alias_draw(alias_nodes[cur][0], alias_nodes[cur][1])])else:prev = walk[-2]next = cur_nbrs[alias_draw(alias_edges[(prev, cur)][0], alias_edges[(prev, cur)][1])]walk.append(next)else:breakreturn walk

與50位技術(shù)專家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的从Deepwalk到Node2vec的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。