《圖表示學(xué)習(xí)入門(mén)1》中斤寇，討論了為什么要進(jìn)行圖（graph）表示感论，以及兩種解決圖表示問(wèn)題的思路焚鲜。這篇把Node2Vec來(lái)作為線性化思路的一個(gè)典型來(lái)討論垦页。
如果你了解Word2Vec的話雀费，這個(gè)就太簡(jiǎn)單了。
代碼實(shí)現(xiàn)：（https://github.com/leichaocn/graph_representation_learning）

目錄
核心想法
準(zhǔn)備節(jié)點(diǎn)序列
用節(jié)點(diǎn)序列來(lái)訓(xùn)練Node2Vec
指標(biāo)評(píng)價(jià)
總結(jié)
參考文獻(xiàn)

核心想法

回想文本中Word2Vec中抽取單詞Embedding的方式痊焊，是怎么做的盏袄？

1. 準(zhǔn)備句子語(yǔ)料忿峻，用一個(gè)詞預(yù)測(cè)周?chē)~來(lái)組成無(wú)監(jiān)督訓(xùn)練的樣本對(duì)。
2. 用這些樣本來(lái)訓(xùn)練一個(gè)2層的Word2Vec網(wǎng)絡(luò)辕羽，抽出隱層權(quán)重作為Embedding炭菌。

那我們只要準(zhǔn)備好節(jié)點(diǎn)序列，是否也可以用Word2Vec的思路來(lái)抽取節(jié)點(diǎn)Embedding逛漫？

但是我們需要首先給節(jié)點(diǎn)創(chuàng)造一些序列，或者說(shuō)語(yǔ)料“句子”赘艳。

如果清楚了這一點(diǎn)酌毡，我們的想法就大致如下：

1. 準(zhǔn)備節(jié)點(diǎn)序列

   圖（graph）結(jié)構(gòu)中，按照節(jié)點(diǎn)的連接關(guān)系生成節(jié)點(diǎn)序列蕾管，很容易枷踏。然而如果任意生成序列，也會(huì)導(dǎo)致序列的意義壞掉掰曾。正如一個(gè)隨機(jī)生成的文本肯定是糟糕的語(yǔ)料旭蠕，一個(gè)隨意生成的節(jié)點(diǎn)序列也必然糟糕。

   所以旷坦，我們需要針對(duì)每個(gè)節(jié)點(diǎn)掏熬，適度地有中心的產(chǎn)生語(yǔ)料。

2. 用節(jié)點(diǎn)序列來(lái)訓(xùn)練Node2Vec

   以skip-gram（中心詞預(yù)測(cè)周?chē)~）的方式秒梅，生成樣本對(duì)旗芬，來(lái)訓(xùn)練Node2Vec網(wǎng)絡(luò)，最終從隱層權(quán)重中抽取出Embedding捆蜀，自帶一定的相似度信息疮丛。

顯然，這是一種無(wú)監(jiān)督的特征學(xué)習(xí)辆它，只需要利用現(xiàn)成的圖（graph）結(jié)構(gòu)準(zhǔn)備好節(jié)點(diǎn)序列就可以了誊薄。

準(zhǔn)備節(jié)點(diǎn)序列

如我們剛才討論的，我們的節(jié)點(diǎn)序列必須圍繞一些節(jié)點(diǎn)锰茉，稍微帶點(diǎn)”中心思想“呢蔫，而不能瞎走。

BFS與DFS

這是兩種耳熟能詳?shù)某Ｒ?jiàn)做法：

• 廣度優(yōu)先搜索（BFS）

  覆蓋度較好飒筑，但是太局部（local）咐刨。

• 深度優(yōu)先搜索（DFS）

  搜索深度較好，但是太全局（global）扬霜，過(guò)于遠(yuǎn)的鄰居對(duì)表征幫助不大定鸟。

2im1.png

圖1.廣度優(yōu)先搜索與深度優(yōu)先搜索的對(duì)比（source）

然而，這兩種做法都有點(diǎn)極端著瓶，本著中庸之道的精神联予，綜合BFS和DFS，請(qǐng)出我們的主角：帶偏隨機(jī)游走（Biased random walk）。

Biased Random Walk

它相當(dāng)于"插值"BFS和DFS沸久，用兩個(gè)參數(shù)季眷，來(lái)調(diào)節(jié)兩者的比例，命名為Biased卷胯，意在強(qiáng)調(diào)人為引入的這兩個(gè)參數(shù)子刮。

2im2.png

圖2.帶偏隨機(jī)游走的核心思想（source）

帶偏隨機(jī)游走做法是：

對(duì)一個(gè)圖遍歷num_walks輪；每輪都用圖中全部節(jié)點(diǎn)窑睁，生成一段話挺峡；每句話是一個(gè)節(jié)點(diǎn)開(kāi)頭，為預(yù)定長(zhǎng)度walk_length担钮。

對(duì)每個(gè)節(jié)點(diǎn)橱赠，讀入概率數(shù)據(jù)，進(jìn)行以下1/2步的循環(huán)箫津，直到達(dá)到預(yù)定長(zhǎng)度狭姨。

1.用Alias Method采樣下一個(gè)節(jié)點(diǎn)。

2.采到的那個(gè)節(jié)點(diǎn)加入到節(jié)點(diǎn)序列里苏遥。該節(jié)點(diǎn)切換為當(dāng)前節(jié)點(diǎn)饼拍。
在原始代碼（含鏈接）里，最核心就是下面這兩個(gè)方法：

def node2vec_walk(self, walk_length, start_node):
    '''
    Simulate a random walk starting from start node.
    '''
    G = self.G
    alias_nodes = self.alias_nodes
    alias_edges = self.alias_edges

    walk = [start_node]

    while len(walk) < walk_length:
        cur = walk[-1]
        cur_nbrs = sorted(G.neighbors(cur))
        if len(cur_nbrs) > 0:
            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:
            break

    return walk

def simulate_walks(self, num_walks, walk_length):
    '''
    Repeatedly simulate random walks from each node.
    '''
    G = self.G
    walks = []
    nodes = list(G.nodes())
    print 'Walk iteration:'
    for walk_iter in range(num_walks):
        print str(walk_iter+1), '/', str(num_walks)
        random.shuffle(nodes)
        for node in nodes:
            walks.append(self.node2vec_walk(walk_length=walk_length, start_node=node))

    return walks

simulate_walks（）用來(lái)生成“一篇文章”田炭，對(duì)一個(gè)圖遍歷多輪（可以想成生成了多個(gè)自然段）惕耕，每輪隨機(jī)一下（每輪生成一個(gè)自然段），遍歷所有節(jié)點(diǎn)（每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一句話）诫肠。最終獲得walks司澎，格式為數(shù)組的數(shù)組，可以理解成一篇文章栋豫，每個(gè)自然段是對(duì)圖的一種隨機(jī)解讀挤安，每個(gè)元素都是一句子的開(kāi)頭。多個(gè)自然段可以理解為對(duì)圖結(jié)構(gòu)的一種反復(fù)解讀：）丧鸯。

node2vec_walk（）則是傳入一個(gè)節(jié)點(diǎn)蛤铜，生成一句話（節(jié)點(diǎn)序列）。由于提前把概率設(shè)置并儲(chǔ)存在圖數(shù)據(jù)中丛肢，這里調(diào)用alias_draw（）即可獲得围肥。alias_draw實(shí)現(xiàn)的就是Alias Method采樣方法。對(duì)Alias Method采樣方法有興趣的小伙伴可以進(jìn)一步了解蜂怎。

生成的結(jié)果在圖3中進(jìn)行了舉例穆刻，有助于理解。

可能需要注意：最終生成的序列很有可能有一個(gè)節(jié)點(diǎn)重復(fù)出現(xiàn)多次的情況杠步。

無(wú)論走的方向是往前或往回或平行氢伟，都是隨機(jī)的榜轿，因此很可能會(huì)往前走了又走回來(lái)了。這沒(méi)關(guān)系朵锣，因?yàn)檫@都是由起始節(jié)點(diǎn)及圖（graph）結(jié)構(gòu)造成的谬盐，我們給它多產(chǎn)生一些序列即可，即豐富的“語(yǔ)料”诚些。

用節(jié)點(diǎn)序列來(lái)訓(xùn)練Node2Vec

通過(guò)之前的操作飞傀，我們已經(jīng)準(zhǔn)備好了節(jié)點(diǎn)序列，按照skip-gram思想诬烹，即對(duì)于輸入的句子砸烦，我們用中心詞預(yù)測(cè)周邊詞們；對(duì)于準(zhǔn)備好的節(jié)點(diǎn)序列串椅您，我們也用某個(gè)中心節(jié)點(diǎn)預(yù)測(cè)周邊節(jié)點(diǎn)們。

注意：這里的周邊寡键，指的是節(jié)點(diǎn)序列里某元素的周邊掀泳，而不是圖（graph）的某元素的周邊。用表示基于策略（本文指）生成的序列西轩，節(jié)點(diǎn)的周?chē)?jié)點(diǎn)的集合员舵，如圖3所示。

2im3.png

圖3.節(jié)點(diǎn)序列及周?chē)?jié)點(diǎn)集合生成示意圖

優(yōu)化目標(biāo)

假設(shè)節(jié)點(diǎn)的one-hot向量為藕畔，在一串序列中马僻，它周?chē)?jié)點(diǎn)one-hot向量為，這些組成的集合為注服。

對(duì)自己周?chē)念A(yù)測(cè)概率韭邓，通過(guò)引入樸素貝葉斯假設(shè)，可以簡(jiǎn)化為：

我們希望這個(gè)盡可能地大溶弟，根據(jù)公式女淑，現(xiàn)在的問(wèn)題是如何求。

這個(gè)好辦辜御，我們只要學(xué)一個(gè)函數(shù)鸭你，輸入，輸出對(duì)節(jié)點(diǎn)的預(yù)測(cè)概率擒权。

而這個(gè)函數(shù)正是我們要訓(xùn)練的神經(jīng)網(wǎng)絡(luò)袱巨。

這下我們就清楚了，可以定義如圖3所示的這個(gè)優(yōu)化目標(biāo)：

2im4.png

圖4.node2vec的學(xué)習(xí)目標(biāo)

神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

下圖中的神經(jīng)網(wǎng)絡(luò)即實(shí)現(xiàn)這個(gè)碳抄，只要輸入一個(gè)樣本愉老，前向傳播一次，從向量的元素中剖效，即可獲得每一個(gè)標(biāo)簽對(duì)應(yīng)的俺夕。

2im5.png

圖5.Node2Vec神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)

在訓(xùn)練中裳凸，將被納入我們的目標(biāo)函數(shù)進(jìn)行尋優(yōu)。

具體的訓(xùn)練涉及細(xì)節(jié)較多劝贸，我們將在Word2Vec中詳細(xì)討論姨谷。

Embedding的獲得

待網(wǎng)絡(luò)訓(xùn)練結(jié)束，只要輸入節(jié)點(diǎn)的one-hot向量映九，前向傳播到隱層梦湘，生成，即為節(jié)點(diǎn)的Embedding件甥。

更簡(jiǎn)便的方式是捌议，由于訓(xùn)練時(shí)都是用one-hot向量訓(xùn)練，其實(shí)引有，只需要把對(duì)應(yīng)里為1的那個(gè)元素瓣颅，所對(duì)應(yīng)的權(quán)重序列拿出來(lái)，即為節(jié)點(diǎn)的Embedding譬正。

這部分宫补，將在Word2Vec中詳細(xì)討論。

指標(biāo)評(píng)價(jià)

由于是無(wú)監(jiān)督訓(xùn)練曾我，同時(shí)獲取的Embedding也只是節(jié)點(diǎn)的特征表示粉怕，因此需要結(jié)合具體項(xiàng)目表現(xiàn)來(lái)對(duì)Node2vec結(jié)果進(jìn)行評(píng)價(jià)。

例如節(jié)點(diǎn)分類項(xiàng)目抒巢，訓(xùn)出Embedding贫贝，再結(jié)合節(jié)點(diǎn)已標(biāo)注的類別標(biāo)簽，訓(xùn)練一個(gè)分類器蛉谜，根據(jù)分類結(jié)果的指標(biāo)對(duì)Embedding進(jìn)行間接評(píng)價(jià)稚晚。需要注意的是，節(jié)點(diǎn)序列生成策略型诚、Node2Vec網(wǎng)絡(luò)的隱層維度蜈彼、分類器的選型和參數(shù)，均影響分類結(jié)果的指標(biāo)俺驶。

總結(jié)

• 通過(guò)合適的策略生成節(jié)點(diǎn)序列幸逆，當(dāng)做訓(xùn)練Node2Vec的“語(yǔ)料”。

• 訓(xùn)練Node2Vec網(wǎng)絡(luò)暮现，即以Word2Vec的思路訓(xùn)練神經(jīng)網(wǎng)絡(luò)还绘，抽出隱層權(quán)重作為對(duì)應(yīng)節(jié)點(diǎn)的Embedding。

參考文獻(xiàn)

[1] Jure Leskovec, 《Graph Representation Learning》

[2] Jure Leskovec, 《Representation Learning on Networks》

http://snap.stanford.edu/proj/embeddings-www/

[3] https://github.com/aditya-grover/node2vec/tree/master/src

（如有錯(cuò)誤及表述不清栖袋，請(qǐng)不吝反饋）