前沿綜述：關係數據紛繁複雜，如何捕捉其中結構？

來自專欄 人工智慧學習筆記

本文由集智翻譯組整理自https://thegradient.pub

1.圖數據中蘊藏著秘密

事物之間的關聯信息，人類已經積累了很多，但絕大多數人不知道如何利用它們。

社交媒體中的互動和關係網路圖中，蘊含著深意。像WordNet這樣的同義圖表能夠通過計算機視覺，幫助我們更好地理解和識別特定情形下研究對象之間的聯繫。從家譜到分子結構，我們周圍世界中海量的信息都以圖的形式呈現。

儘管普遍存在，圖結構（Graph Structure）在機器學習的應用方面還是經常被忽視。比如「時尚潮流推薦問題」，其目標在於發現特定的能夠形成凝聚趨勢的一些衣服形式，也就是「風格」（style）。通常的做法是從社交媒體抓取圖片並識別這些圖片中的衣服，然後用這些圖片的流行程度代表特定「風格」服裝的流行程度。用這種方式去了解流行樣式風格當然可行，這個模型能夠輕易地通過圖數據獲得優化。比如，我們可以分析用戶社交網路中潮流趨勢，或者提取馬遜購物網站中的「相關聯產品」的集合目錄。

那麼，為什麼結構化的信息經常被忽視呢？因為多數情況下，從這些圖表中提取有效的特徵實在是個巨大的挑戰。

在本文中，我們將探索一些從圖數據中提取有效特徵的新技術。特別地，我們將重點討論那些利用隨機遍歷方法，來量化圖中節點之間的相似性。這些技術主要依靠自然語言處理群體的現有結果。我將建議一些未來的研究途徑，特別是與時變圖形的學習特徵有關。最後，我們將簡要討論圖卷積網路 (GCNs) 的大家族，它提供了一個在圖結構數據上進行機器學習的端到端的解決方案，而無需單獨的中間特徵提取步驟。

這些方法本身就構成了機器學習的一個子領域，但是研究人員和從業者可以從他們感興趣的特定範疇的結構中獲益。

2.基於圖的特徵學習

當我們在圖上進行機器學習的時候，我們通常需要計算一個圖摘要（graph summary），它會將圖中每一個頂點映射為一個實值特徵向量，而該向量則編碼了這個頂點的相鄰頂點的信息，這樣做對於基於圖的機器學習是很有幫助的。 如果兩個頂點具有相似的鄰居(neighborhoods)（這裡的「鄰居」一詞很寬泛，它通常用於捕捉某種局部概念，例如從某一頂點出發，經過1或2跳(hops)的頂點集合都可稱為該頂點的「鄰居」），我們要學習一個函數，將這兩個頂點映射到?

?空間中的兩個相似的特徵向量。

然後圖中的的每一個頂點的特徵向量就可以堆積為一個隱含的特徵矩陣?

?有了頂點的向量化表徵之後，我們就可以在其上運行標準的機器學習演算法了。這是不是很棒啊！

DeepWalk(2014) 和 node2vec(2016) 正是學習上述特徵向量的兩個演算法。下面我們就一起來看一下這兩個演算法是怎麼工作的吧。

2.2 DeepWalk：將隨機遊走看做句子？

DeepWalk演算法[1]背後關鍵的思想是，圖中的隨機遊走(random walks)和句子很像。經驗發現，句子中的單詞和一個真實世界中圖上的隨機遊走均服從冪律分布(power-law distribution)。也就是說，我們可以把這些隨機遊走路徑想像成某種「語言」中的「句子」。

受這種相似性的啟發，DeepWalk使用原本被用於自然語言建模的優化技術來構建圖摘要。在標準的語言模型中，我們通常是給定某個詞的周邊詞，然後來估計該詞出現在一個句子中的概率。另一方面，在DeepWalk演算法中，則是給定某個頂點之前的頂點集合，來去估計該頂點出現在一個隨機遊走過程中的概率。並且和語言模型一樣，我們還試圖去學習頂點?

?的特徵向量?

?以便估計這個概率。具體來說就是，給定某個分類器，去估計概率?

?我們的目的是，從向量空間?

?中，選擇特徵向量，最大化如下目標：

然而遺憾的是，隨著隨機遊走路徑長度的不斷增加，這個目標是很難處理的。因此DeepWalk論文作者使用給定當前頂點?

?的向量表徵?

?來去預測其附近2w距離的鄰居頂點（註：w為窗口大小），從而重新界定了該問題。（從技術上來講，這是一個不同的優化問題，但是它可以作為之前目標的一個合理且與順序無關的替代目標[2]）換句話說，我們要最大化目標概率：

但是，我們如何在整個隨機遊走空間上最小化該目標呢？其中一個策略如下（請注意, 論文作者另外假設了?

?的條件獨立性）：

• 抽樣一個頂點v，並生成一個隨機遊走序列?

?其中?

• 對該序列中每一個頂點?

?和每一個小於某一步長的?

?在向量空間 F 上，應用梯度下降演算法，最小化損失函數 ?

這個演算法雖然可行，但是也使得最後應用梯度下降演算法的步驟變得尤為複雜，使得至少要更新?

?個參數。這對於數百萬級規模的圖來說，是一個非常嚴重的問題。

為了解決這個問題，DeepWalk的作者使用「分層softmax (hierarchical softmax)」的方法（很抱歉，該方法不在本文介紹範圍內），將該優化問題拆解為一個二分類器的平衡樹(balanced tree of binary classifiers)。使用這些二分類器，可以將最後一步梯度下降演算法的參數更新個數，從?

?減少到?

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

Grover and Leskovec (2016)[3] 將Deepwalk演算法拓展成為node2vec演算法。與deepwalk演算法不一樣，我們不再根據現有的結點運用一階隨機遊走（first-order random walks）選擇下一個節點，node2vec不僅基於現有結點，還會使用現有結點前面的那一個結點，從而使用一系列二階隨機遊走。

我們可以在隨機遊走的每一步通過調節兩個參數值

來確定具體的分布：大概來說，我們可以通過降低p值從而讓隨機遊走偏向「探索」模式；同時，我們也可以通過提高q值讓隨機遊走實現「廣度優先」(breadth-first)模式。

這篇論文的關鍵想法是通過選擇不同模式的二階隨機遊走，我們可以提取到網路圖的不同特性。

為了證明它的必要性，作者們在文中給出了兩種在網路圖上做機器學習通常使用的鄰域類型：（節點顏色代表類別 ）

• 在同質性假設下，由於高度連接的節點在網路圖裡位置相近，因此它們屬於同一個鄰域。

• 在結構性假設下，承擔著相似結構性功能的節點（比如說，網路的所有中心節點）由於他們高階結構性顯著度，它們屬於同一個鄰域。

用兩個參數

作者們提供了一種非常好用的方法在這兩種鄰域類型之間相互轉換。

就像Deepwalk一樣，node2vec的目標函數可以通過抽樣來實現最優化?

採用（p,q）隨機遊走，然後通過梯度下降（gradient descent）來更新F，達到優化的目的。

2.4 時變網路（temporal networks）中的潛在特徵

這些圖摘要技術很有用，但現實世界中很多圖是隨著時間變化的時變網路。比如，社交網路中一個人的朋友圈圖會隨著時間發生擴張或者收縮。我們可以使用node2vec，但是有兩個缺點：

1. 每次隨著圖的改變而運行一個新的node2vec實例很耗算力
2. 其次，難以保證多個node2vec的實例能產生相似的甚至是可比較的Ｆ矩陣

對於第一個問題，有一個解決方法--每次網路改變後不立即運行node2vec，而是直到足夠多的邊發生改變使得原始嵌入的特徵矩陣Ｆ質量下降再運行。

那麼多少條邊發生改變才可以被認為發生了「顯著」的變化呢？這高度依賴於圖中特殊的邊和隨機遊走中的(p, q)兩個參數。

觀察下面這些圖：

注意到?

?的領域和?

?的鄰域很相似。然而，一條額外的邊把路徑圖?

?轉換成閉環?

?顯著地改變了圖的隨機遊走鄰域。類似這樣，連接網路中的無連接或弱連接部分，起到橋樑作用的邊，相比其它邊更可能對鄰居產生顯著影響。

幸運的是，很多現實世界中的圖，比如社交網路，更傾向於?

?這種類型。網路是高度連接的，增加和刪除節點的某條邊不會對DeepWalk中使用的一階隨機遊走的嵌入產生顯著影響。需要注意的是，一階和二階的隨機遊走差別很大，因此這裡的討論內容對於擴展到node2vec可能並不是必要的。

在某種程度上，第二個問題可以通過連接從多個node2vec實例得出的特徵，然後訓練一個自動編碼器，把這些綜合特徵映射成壓縮的表示。

如何實現時變網路上的可擴展特徵學習呢？對於時變網路，一些工具可以用於圖嵌入的增量更新，比如Abraham et al.(2016)[4]提出的動態頻譜稀釋器。這方面仍然有大量工作需要做，即使是最好的稀釋器也因為速度太慢而難以實際應用於現實世界中的圖，即使存在亞對數演算法，演算法的常量因子也非常大。我相信，結合動態圖分割技術和更新圖摘要矩陣Ｆ對於時變圖的特徵摘要來說或許是一個可行的方法。

另一個可選的方法是泛化node2vec演算法到時變網路，通過添加一個額外的參數λ，影響隨機遊走經過「時變邊界」的概率。有些預測任務中可能有「時變位置」的概念，其中有著相似時間戳的圖的快照是相關的，而其他的或許有更久的依賴關係。

接下來我們開始介紹圖卷積網路，一種最近提出的網路圖上機器學習的方法。

3.圖卷積

Node2vec和DeepWalk的方法都是先生成「語料」然後用於後續的機器學習技術。相比之下，圖卷積（GCN）則是展示了一種端到端的方法進行結構化學習。

GCN嘗試將傳統的卷積神經網路推廣到可變的、無序的結構中。由於圖沒有明確定義的順序，因此節點的排序不應該對GCN產生影響。很顯然，CNN並沒有這個特性，因為隨機交換圖像像素矩陣的行和列，再輸入給CNN必然會改變計算的輸出（通常，用於視覺問題的CNN，在識別圖像中的邊緣或其他局部結構時，其輸入在不同的行列置換下，計算結果並不是一成不變的）。

此外，CNN對像素鄰域的形狀並不是不可知的，換句話說，並沒有明顯的方式可以訓練一個CNN同時接受在正方形和六邊形網格上定義的圖像，即一個內在像素分別具有八個和六個直接鄰居。因此，為了解釋一般圖的動態結構，必須對CNN的激活函數（activation function）進行合理的鬆弛（relaxations）。

很多作者提出了不同的GCN鬆弛（relaxations）方法。其中一篇文章[5]定義了一種和CNN類似的方法，該方法優化了稀疏過濾器，而過濾器在多個尺度上對圖進行聚類操作。這篇文章還提出了CNN的譜近似方法，CNN中多個譜過濾器作用在對應最大特徵值的特徵向量上。另外一篇文章[6]提出了一種和CNN更新具有相同的時間複雜度的GCN更新方案，即對譜過濾器只進行低度的多項式近似。還有一篇文章[7]通過使用多個線性譜過濾器簡化了GCN的公式，這些過濾器可以共同捕捉高階特徵。

這些圖卷積網路公式本身就很有趣，需要更多篇幅來詳細描述。GCN作為之前章節描述的圖處理方法的合理替代方案已經顯示出了前景。GCN的完全可微分的特徵也使得其稀疏過濾器能夠成為端到端學習演算法的一部分。雖然node2vec的偏置超參數(p, q)允許發現更多個性化的特徵，但是GCN的權重矩陣也可以根據提供的訓練數據進行調整。

結構化學習已經被應用到生物化學領域，文章[8]提供了一種端到端的和全微分的神經網路來預測基於稀疏原子結構的蛋白質-配體親和力。另一篇論文[9]用GCN解決了藥物發現問題，並引入了一個虛擬的「超級節點」，該虛擬的「超級節點」通過有向邊連接到候選藥物圖中的每個節點，以便得到圖特徵。

GCN也已經成功應用在知識圖[10]的鏈接預測和實體分類等方面。最近出現的結構化學習的成功和快速的研究在未來幾年還會有更多。也許我們很快就會看到利用關係結構如知識圖的GCN網路來提高計算機視覺中物體檢測的性能，也或許，通過結構化學習方法能夠加速蛋白質摺疊模擬，從而大大降低原子度低的三維蛋白質的維度等等。這些應用幾乎可以肯定將會出現（如果尚未發布的話），這當然使得結構化學習成為一個令人興奮的領域。

4.參考文獻

[1]Rami Al-Rfou "DeepWalk: Online Learning of Social Representations[J] knowledge discovery and data mining, 2014: 701-710."

https://arxiv.org/abs/1403.6652

[2]Tomas Mikolov "Efficient Estimation of Word Representations in Vector Space[J] arXiv: Computation and Language, 2013."

https://arxiv.org/abs/1301.3781

[3]Aditya Grover，Jure Leskovec "node2vec: Scalable Feature Learning for Networks[J] knowledge discovery and data mining, 2016: 855-864."

https://cs.stanford.edu/people/jure/pubs/node2vec-kdd16.pdf

[4]Abraham et al."On Fully Dynamic Graph Sparsifiers.[F] New Jersey, USA, 2016, pp. 335-344."

https://ieeexplore.ieee.org/abstract/document/7782947/

[5]Bruna, Joan, et al. "Spectral networks and locally connected networks on graphs. arXiv:1312.6203"

https://arxiv.org/abs/1312.6203

[6]Defferrard, Micha?l, Xavier Bresson, and Pierre Vandergheynst. "Convolutional neural networks on graphs with fast localized spectral filtering. arXiv:1606.09375 [cs.LG]"

https://arxiv.org/abs/1606.09375

[7]Kipf, Thomas N., and Max Welling. "Semi-supervised classification with graph convolutional networks. arXiv:1609.02907 [cs.LG]"

https://arxiv.org/abs/1609.02907

[8]Gomes, Joseph, et al. "Atomic convolutional networks for predicting protein-ligand binding affinity. arXiv:1703.10603 [cs.LG]"

https://arxiv.org/abs/1703.10603

[9]Li, Junying, Deng Cai, and Xiaofei He. "Learning Graph-Level Representation for Drug Discovery. arXiv:1709.03741 [cs.LG]"

https://arxiv.org/abs/1709.03741

[10]Schlichtkrull, Michael, et al. "Modeling Relational Data with Graph Convolutional Networks. arXiv:1703.06103 [stat.ML]"

https://arxiv.org/abs/1703.06103

翻譯：王昕哲薛亞飛張洪彭智勇辛茹月

審校：龔力

編輯：集智小風

推薦閱讀

文獻綜述：人工智慧如何影響社會經濟

論文解讀：複雜網路的多尺度動態嵌入技術

學術動態：幾何深度學習前沿

大數據會暴露你的社會階層嗎？

2017年人工智慧與深度學習-年度大事件

《探尋宇宙的智能，解密同步的奧秘》

加入集智，一起複雜！集智俱樂部團隊招新啦！

全息計算打造「公司大腦」；簡單規則驅動複雜系統

解讀冪律與無標度網路 | 網路科學入門

http://weixin.qq.com/r/NDsxKXDEti3JrTRK924m (二維碼自動識別)