一、圖數(shù)據(jù)中蘊(yùn)藏著秘密

事物之間的關(guān)聯(lián)信息，人類已經(jīng)積累了很多，但絕大多數(shù)人不知道如何利用它們。

社交媒體中的互動(dòng)和關(guān)系網(wǎng)絡(luò)圖中，蘊(yùn)含著深意。像WordNet這樣的同義圖表能夠通過(guò)計(jì)算機(jī)視覺(jué)，幫助我們更好地理解和識(shí)別特定情形下研究對(duì)象之間的聯(lián)系。從家譜到分子結(jié)構(gòu)，我們周圍世界中海量的信息都以圖的形式呈現(xiàn)。

盡管普遍存在，圖結(jié)構(gòu)（Graph Structure）在機(jī)器學(xué)習(xí)的應(yīng)用方面還是經(jīng)常被忽視。比如“時(shí)尚潮流推薦問(wèn)題”，其目標(biāo)在于發(fā)現(xiàn)特定的能夠形成凝聚趨勢(shì)的一些衣服形式，也就是“風(fēng)格”（style）。

通常的做法是從社交媒體抓取圖片并識(shí)別這些圖片中的衣服，然后用這些圖片的流行程度代表特定“風(fēng)格”服裝的流行程度。用這種方式去了解流行樣式風(fēng)格當(dāng)然可行，這個(gè)模型能夠輕易地通過(guò)圖數(shù)據(jù)獲得優(yōu)化。比如，我們可以分析用戶社交網(wǎng)絡(luò)中潮流趨勢(shì)，或者提取馬遜購(gòu)物網(wǎng)站中的“相關(guān)聯(lián)產(chǎn)品”的集合目錄。

那么，為什么結(jié)構(gòu)化的信息經(jīng)常被忽視呢？因?yàn)槎鄶?shù)情況下，從這些圖表中提取有效的特征實(shí)在是個(gè)巨大的挑戰(zhàn)。

在本文中，我們將探索一些從圖數(shù)據(jù)中提取有效特征的新技術(shù)。特別地，我們將重點(diǎn)討論那些利用隨機(jī)遍歷方法，來(lái)量化圖中節(jié)點(diǎn)之間的相似性。這些技術(shù)主要依靠自然語(yǔ)言處理群體的現(xiàn)有結(jié)果。

我將建議一些未來(lái)的研究途徑，特別是與時(shí)變圖形的學(xué)習(xí)特征有關(guān)。最后，我們將簡(jiǎn)要討論圖卷積網(wǎng)絡(luò) (GCNs) 的大家族，它提供了一個(gè)在圖結(jié)構(gòu)數(shù)據(jù)上進(jìn)行機(jī)器學(xué)習(xí)的端到端的解決方案，而無(wú)需單獨(dú)的中間特征提取步驟。

這些方法本身就構(gòu)成了機(jī)器學(xué)習(xí)的一個(gè)子領(lǐng)域，但是研究人員和從業(yè)者可以從他們感興趣的特定范疇的結(jié)構(gòu)中獲益。

二、基于圖的特征學(xué)習(xí)

2.1 圖摘要的計(jì)算

當(dāng)我們?cè)趫D上進(jìn)行機(jī)器學(xué)習(xí)的時(shí)候，我們通常需要計(jì)算一個(gè)圖摘要（graph summary），它會(huì)將圖中每一個(gè)頂點(diǎn)映射為一個(gè)實(shí)值特征向量，而該向量則編碼了這個(gè)頂點(diǎn)的相鄰頂點(diǎn)的信息，這樣做對(duì)于基于圖的機(jī)器學(xué)習(xí)是很有幫助的。

如果兩個(gè)頂點(diǎn)具有相似的鄰居(neighborhoods)（這里的“鄰居”一詞很寬泛，它通常用于捕捉某種局部概念，例如從某一頂點(diǎn)出發(fā)，經(jīng)過(guò)1或2跳(hops)的頂點(diǎn)集合都可稱為該頂點(diǎn)的“鄰居”），我們要學(xué)習(xí)一個(gè)函數(shù)，將這兩個(gè)頂點(diǎn)映射到??空間中的兩個(gè)相似的特征向量。

然后圖中的的每一個(gè)頂點(diǎn)的特征向量就可以堆積為一個(gè)隱含的特征矩陣??。有了頂點(diǎn)的向量化表征之后，我們就可以在其上運(yùn)行標(biāo)準(zhǔn)的機(jī)器學(xué)習(xí)算法了。這是不是很棒啊！

DeepWalk(2014)和node2vec(2016)正是學(xué)習(xí)上述特征向量的兩個(gè)算法。下面我們就一起來(lái)看一下這兩個(gè)算法是怎么工作的吧。

2.2 DeepWalk：將隨機(jī)游走看做句子？

DeepWalk算法[1]背后關(guān)鍵的思想是，圖中的隨機(jī)游走(random walks)和句子很像。經(jīng)驗(yàn)發(fā)現(xiàn)，句子中的單詞和一個(gè)真實(shí)世界中圖上的隨機(jī)游走均服從冪律分布(power-law distribution)。也就是說(shuō)，我們可以把這些隨機(jī)游走路徑想象成某種“語(yǔ)言”中的“句子”。

受這種相似性的啟發(fā)，DeepWalk使用原本被用于自然語(yǔ)言建模的優(yōu)化技術(shù)來(lái)構(gòu)建圖摘要。在標(biāo)準(zhǔn)的語(yǔ)言模型中，我們通常是給定某個(gè)詞的周邊詞，然后來(lái)估計(jì)該詞出現(xiàn)在一個(gè)句子中的概率。

另一方面，在DeepWalk算法中，則是給定某個(gè)頂點(diǎn)之前的頂點(diǎn)集合，來(lái)去估計(jì)該頂點(diǎn)出現(xiàn)在一個(gè)隨機(jī)游走過(guò)程中的概率。并且和語(yǔ)言模型一樣，我們還試圖去學(xué)習(xí)頂點(diǎn)??的特征向量??，以便估計(jì)這個(gè)概率。具體來(lái)說(shuō)就是，給定某個(gè)分類器，去估計(jì)概率??。我們的目的是，從向量空間??中，選擇特征向量，最大化如下目標(biāo)：

?

然而遺憾的是，隨著隨機(jī)游走路徑長(zhǎng)度的不斷增加，這個(gè)目標(biāo)是很難處理的。因此DeepWalk論文作者使用給定當(dāng)前頂點(diǎn)??的向量表征??，來(lái)去預(yù)測(cè)其附近2w距離的鄰居頂點(diǎn)（注：w為窗口大?。?，從而重新界定了該問(wèn)題。（從技術(shù)上來(lái)講，這是一個(gè)不同的優(yōu)化問(wèn)題，但是它可以作為之前目標(biāo)的一個(gè)合理且與順序無(wú)關(guān)的替代目標(biāo)[2]）換句話說(shuō)，我們要最大化目標(biāo)概率：

?

但是，我們?nèi)绾卧谡麄€(gè)隨機(jī)游走空間上最小化（譯者：最小化？不是最大化嗎？）該目標(biāo)呢？其中一個(gè)策略如下（請(qǐng)注意, 論文作者另外假設(shè)了??的條件獨(dú)立性）：

抽樣一個(gè)頂點(diǎn)v，并生成一個(gè)隨機(jī)游走序列??，其中??。

對(duì)該序列中每一個(gè)頂點(diǎn)??和每一個(gè)小于某一步長(zhǎng)的??，在向量空間 F 上，應(yīng)用梯度下降算法，最小化損失函數(shù)???。

這個(gè)算法雖然可行，但是也使得最后應(yīng)用梯度下降算法的步驟變得尤為復(fù)雜，使得至少要更新??個(gè)參數(shù)。這對(duì)于數(shù)百萬(wàn)級(jí)規(guī)模的圖來(lái)說(shuō)，是一個(gè)非常嚴(yán)重的問(wèn)題。

為了解決這個(gè)問(wèn)題，DeepWalk的作者使用“分層softmax (hierarchical softmax)”的方法（很抱歉，該方法不在本文介紹范圍內(nèi)），將該優(yōu)化問(wèn)題拆解為一個(gè)二分類器的平衡樹(shù)(balanced tree of binary classifiers)。使用這些二分類器，可以將最后一步梯度下降算法的參數(shù)更新個(gè)數(shù)，從??減少到??。

Deepwalk算法示意圖

2.3 Node2vec：泛化到不同類型的鄰域

Grover and Leskovec (2016)[3]將Deepwalk算法拓展成為node2vec算法。與deepwalk算法不一樣，我們不再根據(jù)現(xiàn)有的結(jié)點(diǎn)運(yùn)用一階隨機(jī)游走（first-order random walks）選擇下一個(gè)節(jié)點(diǎn)，node2vec不僅基于現(xiàn)有結(jié)點(diǎn)，還會(huì)使用現(xiàn)有結(jié)點(diǎn)前面的那一個(gè)結(jié)點(diǎn)，從而使用一系列二階隨機(jī)游走。

我們可以在隨機(jī)游走的每一步通過(guò)調(diào)節(jié)兩個(gè)參數(shù)值??來(lái)確定具體的分布：大概來(lái)說(shuō)，我們可以通過(guò)降低p值從而讓隨機(jī)游走偏向“探索”模式；同時(shí)，我們也可以通過(guò)提高q值讓隨機(jī)游走實(shí)現(xiàn)“廣度優(yōu)先”(breadth-first)模式。

這篇論文的關(guān)鍵想法是通過(guò)選擇不同模式的二階隨機(jī)游走，我們可以提取到網(wǎng)絡(luò)圖的不同特性。

為了證明它的必要性，作者們?cè)谖闹薪o出了兩種在網(wǎng)絡(luò)圖上做機(jī)器學(xué)習(xí)通常使用的鄰域類型：（節(jié)點(diǎn)顏色代表類別）

在同質(zhì)性假設(shè)下，由于高度連接的節(jié)點(diǎn)在網(wǎng)絡(luò)圖里位置相近，因此它們屬于同一個(gè)鄰域。

?

在結(jié)構(gòu)性假設(shè)下，承擔(dān)著相似結(jié)構(gòu)性功能的節(jié)點(diǎn)（比如說(shuō)，網(wǎng)絡(luò)的所有中心節(jié)點(diǎn)）由于他們高階結(jié)構(gòu)性顯著度，它們屬于同一個(gè)鄰域。

?

用兩個(gè)參數(shù)??, 作者們提供了一種非常好用的方法在這兩種鄰域類型之間相互轉(zhuǎn)換。

就像Deepwalk一樣，node2vec的目標(biāo)函數(shù)可以通過(guò)抽樣來(lái)實(shí)現(xiàn)最優(yōu)化??，采用（p,q）隨機(jī)游走，然后通過(guò)梯度下降（gradient descent）來(lái)更新F，達(dá)到優(yōu)化的目的。

2.4 時(shí)變網(wǎng)絡(luò)（temporal networks）中的潛在特征

這些圖摘要技術(shù)很有用，但現(xiàn)實(shí)世界中很多圖是隨著時(shí)間變化的時(shí)變網(wǎng)絡(luò)。比如，社交網(wǎng)絡(luò)中一個(gè)人的朋友圈圖會(huì)隨著時(shí)間發(fā)生擴(kuò)張或者收縮。我們可以使用node2vec，但是有兩個(gè)缺點(diǎn)：

每次隨著圖的改變而運(yùn)行一個(gè)新的node2vec實(shí)例很耗算力

其次，難以保證多個(gè)node2vec的實(shí)例能產(chǎn)生相似的甚至是可比較的Ｆ矩陣

對(duì)于第一個(gè)問(wèn)題，有一個(gè)解決方法--每次網(wǎng)絡(luò)改變后不立即運(yùn)行node2vec，而是直到足夠多的邊發(fā)生改變使得原始嵌入的特征矩陣Ｆ質(zhì)量下降再運(yùn)行。

那么多少條邊發(fā)生改變才可以被認(rèn)為發(fā)生了“顯著”的變化呢？這高度依賴于圖中特殊的邊和隨機(jī)游走中的(p, q)兩個(gè)參數(shù)。

觀察下面這些圖：

?

注意到??的領(lǐng)域和??的鄰域很相似。然而，一條額外的邊把路徑圖??轉(zhuǎn)換成閉環(huán)??，顯著地改變了圖的隨機(jī)游走鄰域。類似這樣，連接網(wǎng)絡(luò)中的無(wú)連接或弱連接部分，起到橋梁作用的邊，相比其它邊更可能對(duì)鄰居產(chǎn)生顯著影響。

幸運(yùn)的是，很多現(xiàn)實(shí)世界中的圖，比如社交網(wǎng)絡(luò)，更傾向于??這種類型。網(wǎng)絡(luò)是高度連接的，增加和刪除節(jié)點(diǎn)的某條邊不會(huì)對(duì)DeepWalk中使用的一階隨機(jī)游走的嵌入產(chǎn)生顯著影響。需要注意的是，一階和二階的隨機(jī)游走差別很大，因此這里的討論內(nèi)容對(duì)于擴(kuò)展到node2vec可能并不是必要的。

在某種程度上，第二個(gè)問(wèn)題可以通過(guò)連接從多個(gè)node2vec實(shí)例得出的特征，然后訓(xùn)練一個(gè)自動(dòng)編碼器，把這些綜合特征映射成壓縮的表示。

如何實(shí)現(xiàn)時(shí)變網(wǎng)絡(luò)上的可擴(kuò)展特征學(xué)習(xí)呢？對(duì)于時(shí)變網(wǎng)絡(luò)，一些工具可以用于圖嵌入的增量更新，比如Abraham et al.(2016)[4]提出的動(dòng)態(tài)頻譜稀釋器。

這方面仍然有大量工作需要做，即使是最好的稀釋器也因?yàn)樗俣忍y以實(shí)際應(yīng)用于現(xiàn)實(shí)世界中的圖，即使存在亞對(duì)數(shù)算法，算法的常量因子也非常大。我相信，結(jié)合動(dòng)態(tài)圖分割技術(shù)和更新圖摘要矩陣Ｆ對(duì)于時(shí)變圖的特征摘要來(lái)說(shuō)或許是一個(gè)可行的方法。

另一個(gè)可選的方法是泛化node2vec算法到時(shí)變網(wǎng)絡(luò)，通過(guò)添加一個(gè)額外的參數(shù)λ，影響隨機(jī)游走經(jīng)過(guò)“時(shí)變邊界”的概率。有些預(yù)測(cè)任務(wù)中可能有“時(shí)變位置”的概念，其中有著相似時(shí)間戳的圖的快照是相關(guān)的，而其他的或許有更久的依賴關(guān)系。

接下來(lái)我們開(kāi)始介紹圖卷積網(wǎng)絡(luò)，一種最近提出的網(wǎng)絡(luò)圖上機(jī)器學(xué)習(xí)的方法。

三、圖卷積

Node2vec和DeepWalk的方法都是先生成“語(yǔ)料”然后用于后續(xù)的機(jī)器學(xué)習(xí)技術(shù)。相比之下，圖卷積（GCN）則是展示了一種端到端的方法進(jìn)行結(jié)構(gòu)化學(xué)習(xí)。

圖卷積

GCN嘗試將傳統(tǒng)的卷積神經(jīng)網(wǎng)絡(luò)推廣到可變的、無(wú)序的結(jié)構(gòu)中。由于圖沒(méi)有明確定義的順序，因此節(jié)點(diǎn)的排序不應(yīng)該對(duì)GCN產(chǎn)生影響。很顯然，CNN并沒(méi)有這個(gè)特性，因?yàn)殡S機(jī)交換圖像像素矩陣的行和列，再輸入給CNN必然會(huì)改變計(jì)算的輸出（通常，用于視覺(jué)問(wèn)題的CNN，在識(shí)別圖像中的邊緣或其他局部結(jié)構(gòu)時(shí)，其輸入在不同的行列置換下，計(jì)算結(jié)果并不是一成不變的）。

此外，CNN對(duì)像素鄰域的形狀并不是不可知的，換句話說(shuō)，并沒(méi)有明顯的方式可以訓(xùn)練一個(gè)CNN同時(shí)接受在正方形和六邊形網(wǎng)格上定義的圖像，即一個(gè)內(nèi)在像素分別具有八個(gè)和六個(gè)直接鄰居。因此，為了解釋一般圖的動(dòng)態(tài)結(jié)構(gòu)，必須對(duì)CNN的激活函數(shù)（activation function）進(jìn)行合理的松弛（relaxations）。

很多作者提出了不同的GCN松弛（relaxations）方法。其中一篇文章[5]定義了一種和CNN類似的方法，該方法優(yōu)化了稀疏過(guò)濾器，而過(guò)濾器在多個(gè)尺度上對(duì)圖進(jìn)行聚類操作。這篇文章還提出了CNN的譜近似方法，CNN中多個(gè)譜過(guò)濾器作用在對(duì)應(yīng)最大特征值的特征向量上。

另外一篇文章[6]提出了一種和CNN更新具有相同的時(shí)間復(fù)雜度的GCN更新方案，即對(duì)譜過(guò)濾器只進(jìn)行低度的多項(xiàng)式近似。還有一篇文章[7]通過(guò)使用多個(gè)線性譜過(guò)濾器簡(jiǎn)化了GCN的公式，這些過(guò)濾器可以共同捕捉高階特征。

這些圖卷積網(wǎng)絡(luò)公式本身就很有趣，需要更多篇幅來(lái)詳細(xì)描述。GCN作為之前章節(jié)描述的圖處理方法的合理替代方案已經(jīng)顯示出了前景。GCN的完全可微分的特征也使得其稀疏過(guò)濾器能夠成為端到端學(xué)習(xí)算法的一部分。雖然node2vec的偏置超參數(shù)(p, q)允許發(fā)現(xiàn)更多個(gè)性化的特征，但是GCN的權(quán)重矩陣也可以根據(jù)提供的訓(xùn)練數(shù)據(jù)進(jìn)行調(diào)整。

結(jié)構(gòu)化學(xué)習(xí)已經(jīng)被應(yīng)用到生物化學(xué)領(lǐng)域，文章[8]提供了一種端到端的和全微分的神經(jīng)網(wǎng)絡(luò)來(lái)預(yù)測(cè)基于稀疏原子結(jié)構(gòu)的蛋白質(zhì)-配體親和力。另一篇論文[9]用GCN解決了藥物發(fā)現(xiàn)問(wèn)題，并引入了一個(gè)虛擬的“超級(jí)節(jié)點(diǎn)”，該虛擬的“超級(jí)節(jié)點(diǎn)”通過(guò)有向邊連接到候選藥物圖中的每個(gè)節(jié)點(diǎn)，以便得到圖特征。

GCN也已經(jīng)成功應(yīng)用在知識(shí)圖[10]的鏈接預(yù)測(cè)和實(shí)體分類等方面。最近出現(xiàn)的結(jié)構(gòu)化學(xué)習(xí)的成功和快速的研究在未來(lái)幾年還會(huì)有更多。

也許我們很快就會(huì)看到利用關(guān)系結(jié)構(gòu)如知識(shí)圖的GCN網(wǎng)絡(luò)來(lái)提高計(jì)算機(jī)視覺(jué)中物體檢測(cè)的性能，也或許，通過(guò)結(jié)構(gòu)化學(xué)習(xí)方法能夠加速蛋白質(zhì)折疊模擬，從而大大降低原子度低的三維蛋白質(zhì)的維度等等。這些應(yīng)用幾乎可以肯定將會(huì)出現(xiàn)（如果尚未發(fā)布的話），這當(dāng)然使得結(jié)構(gòu)化學(xué)習(xí)成為一個(gè)令人興奮的領(lǐng)域。