0
字幕組雙語原文：【GCN】圖卷積網(wǎng)絡(GCN)入門詳解
英語原文：Graph Convolutional Networks (GCN)
在這篇文章中，我們將仔細研究一個名為GCN的著名圖神經(jīng)網(wǎng)絡。首先，我們先直觀的了解一下它的工作原理，然后再深入了解它背后的數(shù)學原理。
許多問題的本質(zhì)上都是圖。在我們的世界里，我們看到很多數(shù)據(jù)都是圖，比如分子、社交網(wǎng)絡、論文引用網(wǎng)絡。
圖的例子。(圖片來自[1])
節(jié)點分類：預測特定節(jié)點的類型。
鏈接預測：預測兩個節(jié)點是否有聯(lián)系
社區(qū)檢測：識別密集聯(lián)系的節(jié)點群落。
網(wǎng)絡相似性：兩個(子)網(wǎng)絡的相似性有多大？
在圖中，我們有節(jié)點特征（代表節(jié)點的數(shù)據(jù)）和圖的結構（表示節(jié)點如何連接）。
對于節(jié)點來說，我們可以很容易地得到每個節(jié)點的數(shù)據(jù)。但是當涉及到圖的結構時，要從中提取有用的信息就不是一件容易的事情了。例如，如果2個節(jié)點彼此距離很近，我們是否應該將它們與其他對節(jié)點區(qū)別對待呢？高低度節(jié)點又該如何處理呢？其實，對于每一項具體的工作，僅僅是特征工程，即把圖結構轉(zhuǎn)換為我們的特征，就會消耗大量的時間和精力。
圖上的特征工程。(圖片來自[1])
如果能以某種方式同時得到圖的節(jié)點特征和結構信息作為輸入，讓機器自己去判斷哪些信息是有用的，那就更好了。
這也是為什么我們需要圖表示學習的原因。
我們希望圖能夠自己學習 "特征工程"。(圖片來自[1])
論文：基于圖神經(jīng)網(wǎng)絡的半監(jiān)督分類（2017）[3]
GCN是一種卷積神經(jīng)網(wǎng)絡，它可以直接在圖上工作，并利用圖的結構信息。
它解決的是對圖（如引文網(wǎng)絡）中的節(jié)點（如文檔）進行分類的問題，其中僅有一小部分節(jié)點有標簽（半監(jiān)督學習）。
在Graphs上進行半監(jiān)督學習的例子。有些節(jié)點沒有標簽（未知節(jié)點）。
就像"卷積"這個名字所指代的那樣，這個想法來自于圖像，之后引進到圖（Graphs）中。然而，當圖像有固定的結構時，圖（Graphs）就復雜得多。
從圖像到圖形的卷積思想。 (圖片來自[1])
GCN的基本思路：對于每個節(jié)點，我們從它的所有鄰居節(jié)點處獲取其特征信息，當然也包括它自身的特征。假設我們使用average()函數(shù)。我們將對所有的節(jié)點進行同樣的操作。最后，我們將這些計算得到的平均值輸入到神經(jīng)網(wǎng)絡中。
在下圖中，我們有一個引文網(wǎng)絡的簡單實例。其中每個節(jié)點代表一篇研究論文，同時邊代表的是引文。我們在這里有一個預處理步驟。在這里我們不使用原始論文作為特征，而是將論文轉(zhuǎn)換成向量（通過使用NLP嵌入，例如tf-idf）。NLP嵌入，例如TF-IDF)。
讓我們考慮下綠色節(jié)點。首先，我們得到它的所有鄰居的特征值，包括自身節(jié)點，接著取平均值。最后通過神經(jīng)網(wǎng)絡返回一個結果向量并將此作為最終結果。
GCN的主要思想。我們以綠色節(jié)點為例。首先，我們?nèi)∑渌朽従庸?jié)點的平均值，包括自身節(jié)點。然后，將平均值通過神經(jīng)網(wǎng)絡。請注意，在GCN中，我們僅僅使用一個全連接層。在這個例子中，我們得到2維向量作為輸出（全連接層的2個節(jié)點）。
在實際操作中，我們可以使用比average函數(shù)更復雜的聚合函數(shù)。我們還可以將更多的層疊加在一起，以獲得更深的GCN。其中每一層的輸出會被視為下一層的輸入。
2層GCN的例子：第一層的輸出是第二層的輸入。同樣，注意GCN中的神經(jīng)網(wǎng)絡僅僅是一個全連接層（圖片來自[2]）。
讓我們認真從數(shù)學角度看看它到底是如何起作用的。
首先，我們需要一些注解
我們考慮圖G，如下圖所示。
從圖G中，我們有一個鄰接矩陣A和一個度矩陣D。同時我們也有特征矩陣X。
那么我們怎樣才能從鄰居節(jié)點處得到每一個節(jié)點的特征值呢？解決方法就在于A和X的相乘。
看看鄰接矩陣的第一行，我們看到節(jié)點A與節(jié)點E之間有連接，得到的矩陣第一行就是與A相連接的E節(jié)點的特征向量（如下圖）。同理，得到的矩陣的第二行是D和E的特征向量之和，通過這個方法，我們可以得到所有鄰居節(jié)點的向量之和。
計算 "和向量矩陣 "AX的第一行。
這里還有一些需要改進的地方。
我們忽略了節(jié)點本身的特征。例如，計算得到的矩陣的第一行也應該包含節(jié)點A的特征。
我們不需要使用sum()函數(shù)，而是需要取平均值，甚至更好的鄰居節(jié)點特征向量的加權平均值。那我們?yōu)槭裁床皇褂胹um()函數(shù)呢？原因是在使用sum()函數(shù)時，度大的節(jié)點很可能會生成的大的v向量，而度低的節(jié)點往往會得到小的聚集向量，這可能會在以后造成梯度爆炸或梯度消失（例如，使用sigmoid時）。此外，神經(jīng)網(wǎng)絡似乎對輸入數(shù)據(jù)的規(guī)模很敏感。因此，我們需要對這些向量進行歸一化，以擺脫可能出現(xiàn)的問題。
在問題（1）中，我們可以通過在A中增加一個單位矩陣I來解決，得到一個新的鄰接矩陣?。
取lambda=1（使得節(jié)點本身的特征和鄰居一樣重要），我們就有?=A+I，注意，我們可以把lambda當做一個可訓練的參數(shù)，但現(xiàn)在只要把lambda賦值為1就可以了，即使在論文中，lambda也只是簡單的賦值為1。
通過給每個節(jié)點增加一個自循環(huán)，我們得到新的鄰接矩陣
對于問題(2): 對于矩陣縮放，我們通常將矩陣乘以對角線矩陣。在當前的情況下，我們要取聚合特征的平均值，或者從數(shù)學角度上說，要根據(jù)節(jié)點度數(shù)對聚合向量矩陣?X進行縮放。直覺告訴我們這里用來縮放的對角矩陣是和度矩陣D?有關的東西（為什么是D?，而不是D？因為我們考慮的是新鄰接矩陣? 的度矩陣D?，而不再是A了）。
現(xiàn)在的問題變成了我們要如何對和向量進行縮放/歸一化？換句話說：
我們?nèi)绾螌⑧従拥男畔鬟f給特定節(jié)點？我們從我們的老朋友average開始。在這種情況下，D?的逆矩陣（即，D?^{-1}）就會用起作用?；旧?，D?的逆矩陣中的每個元素都是對角矩陣D中相應項的倒數(shù)。
例如，節(jié)點A的度數(shù)為2，所以我們將節(jié)點A的聚合向量乘以1/2，而節(jié)點E的度數(shù)為5，我們應該將E的聚合向量乘以1/5，以此類推。
因此，通過D?取反和X的乘法，我們可以取所有鄰居節(jié)點的特征向量（包括自身節(jié)點）的平均值。
到目前為止一切都很好。但是你可能會問加權平均()怎么樣？直覺上，如果我們對高低度的節(jié)點區(qū)別對待，應該會更好。
但我們只是按行縮放，但忽略了對應的列（虛線框）。
為列增加一個新的縮放器。
新的縮放方法給我們提供了 "加權 "的平均值。我們在這里做的是給低度的節(jié)點加更多的權重，以減少高度節(jié)點的影響。這個加權平均的想法是，我們假設低度節(jié)點會對鄰居節(jié)點產(chǎn)生更大的影響，而高度節(jié)點則會產(chǎn)生較低的影響，因為它們的影響力分散在太多的鄰居節(jié)點上。
在節(jié)點B處聚合鄰接節(jié)點特征時，我們?yōu)楣?jié)點B本身分配最大的權重（度數(shù)為3），為節(jié)點E分配最小的權重（度數(shù)為5）。
因為我們歸一化了兩次，所以將"-1 "改為"-1/2"
例如，我們有一個多分類問題，有10個類，F(xiàn) 被設置為10。在第2層有了10個維度的向量后，我們將這些向量通過一個softmax函數(shù)進行預測。
Loss函數(shù)的計算方法很簡單，就是通過對所有有標簽的例子的交叉熵誤差來計算，其中Y_{l}是有標簽的節(jié)點的集合。
層數(shù)是指節(jié)點特征能夠傳輸?shù)淖钸h距離。例如，在1層的GCN中，每個節(jié)點只能從其鄰居那里獲得信息。每個節(jié)點收集信息的過程是獨立進行的，對所有節(jié)點來說都是在同一時間進行的。
當在第一層的基礎上再疊加一層時，我們重復收集信息的過程，但這一次，鄰居節(jié)點已經(jīng)有了自己的鄰居的信息（來自上一步）。這使得層數(shù)成為每個節(jié)點可以走的最大跳步。所以，這取決于我們認為一個節(jié)點應該從網(wǎng)絡中獲取多遠的信息，我們可以為#layers設置一個合適的數(shù)字。但同樣，在圖中，通常我們不希望走得太遠。設置為6-7跳，我們就幾乎可以得到整個圖，但是這就使得聚合的意義不大。
例： 收集目標節(jié)點 i 的兩層信息的過程
在論文中，作者還分別對淺層和深層的GCN進行了一些實驗。在下圖中，我們可以看到，使用2層或3層的模型可以得到最好的結果。此外，對于深層的GCN（超過7層），反而往往得到不好的性能（虛線藍色）。一種解決方案是借助隱藏層之間的殘余連接（紫色線）。
不同層數(shù)#的性能。圖片來自論文[3]
GCNs用于圖上的半監(jiān)督學習。
GCNs同時使用節(jié)點特征和結構進行訓練
GCN的主要思想是取所有鄰居節(jié)點特征（包括自身節(jié)點）的加權平均值。度低的節(jié)點獲得更大的權重。之后，我們將得到的特征向量通過神經(jīng)網(wǎng)絡進行訓練。
我們可以堆疊更多的層數(shù)來使GCN更深?？紤]深度GCNs的殘差連接。通常，我們會選擇2層或3層的GCN。
數(shù)學筆記：當看到對角線矩陣時，要想到矩陣縮放。
這里有一個使用StellarGraph庫的GCN演示[5]。該倉庫還提供了許多其他GNN的算法。
論文作者的說明
該框架目前僅限于無向圖（加權或不加權）。但是，可以通過將原始有向圖表示為一個無向的兩端圖，并增加代表原始圖中邊的節(jié)點，來處理有向邊和邊特征。
對于GCN，我們似乎可以同時利用節(jié)點特征和圖的結構。然而，如果圖中的邊有不同的類型呢？我們是否應該對每種關系進行不同的處理？在這種情況下如何聚合鄰居節(jié)點？最近有哪些先進的方法？
在圖專題的下一篇文章中，我們將研究一些更復雜的方法。
如何處理邊的不同關系（兄弟、朋友、......）？
[1] Excellent slides on Graph Representation Learning by Jure Leskovec (Stanford): https://drive.google.com/file/d/1By3udbOt10moIcSEgUQ0TR9twQX9Aq0G/view?usp=sharing
[2] Video Graph Convolutional Networks (GCNs) made simple: https://www.youtube.com/watch?v=2KRAOZIULzw
[3] Paper Semi-supervised Classification with Graph Convolutional Networks (2017): https://arxiv.org/pdf/1609.02907.pdf
[4] GCN source code: https://github.com/tkipf/gcn
[5] Demo with StellarGraph library: https://stellargraph.readthedocs.io/en/stable/demos/node-classification/gcn-node-classification.html
雷鋒字幕組是一個由AI愛好者組成的翻譯團隊，匯聚五五多位志愿者的力量，分享最新的海外AI資訊，交流關于人工智能技術領域的行業(yè)轉(zhuǎn)變與技術創(chuàng)新的見解。
團隊成員有大數(shù)據(jù)專家，算法工程師，圖像處理工程師，產(chǎn)品經(jīng)理，產(chǎn)品運營，IT咨詢?nèi)耍谛熒?；志愿者們來自IBM，AVL，Adobe，阿里，百度等知名企業(yè)，北大，清華，港大，中科院，南卡羅萊納大學，早稻田大學等海內(nèi)外高校研究所。
如果，你也是位熱愛分享的AI愛好者。歡迎與雷鋒字幕組一起，學習新知，分享成長。
雷峰網(wǎng)版權文章，未經(jīng)授權禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
