GNN

a gentle introduction to graph neural network

對圖神經(jīng)網(wǎng)絡的簡易介紹

神經(jīng)網(wǎng)絡被用在處理圖的結構和性質上面

1、前言

圖這個數(shù)據(jù)結構相對于之前討論的文本（文本是一個序列）、圖片（圖片是一個矩陣），圖相對來說更加復雜一點

上一次機器學習關注圖還是在十幾年前，在社交網(wǎng)絡比較流行的時候，但是過去一些年由于覺得圖數(shù)據(jù)結構做起來比較困難，所以關注點還是在別的地方

過去三年里面，將神經(jīng)網(wǎng)絡應用在圖上這個研究方向逐漸興起

圖是一個很一般化的架構，十幾年前，研究者提出了針對圖的神經(jīng)網(wǎng)絡（圖神經(jīng)網(wǎng)絡，GNN），最近它們在能力和表達上都有增強

圖神經(jīng)網(wǎng)絡的實際應用（starting to，圖神經(jīng)網(wǎng)絡還是一個比較新的領域，在應用上剛起步）

• 藥物的發(fā)現(xiàn)
• 物理模擬
• 虛假新聞檢測
• 車流量的檢測
• 推薦系統(tǒng)

本文旨在探索和解釋現(xiàn)代的圖神經(jīng)網(wǎng)絡

• 什么數(shù)據(jù)可以表示成一張圖
• 圖和別的數(shù)據(jù)有什么不同，為什么要做圖神經(jīng)網(wǎng)絡，而不是使用最簡單的卷積神經(jīng)網(wǎng)絡等
• 構建了一個GNN，看各模塊的具體結構
• 提供了一個GNN的playground

2、什么是圖

圖是用來表示entity（實體）之間的關系

• 實體就是一個點（node，頂點）
• 關系就是一個邊（edge）

下圖展示了圖

• 頂點（node）

• 邊：頂點之間的關系

• U：代表整個圖（全局信息）
• attribute：每個頂點、每條邊和整個圖表示的信息

下圖展示了屬性

• 頂點（黃色）可以用一個embeding（向量）來表示它里面的屬性，一共有六個值，高矮表示值的大小
• 邊（藍色）也可以使用向量來表示，長度可以和頂點不一樣，這里使用的是一個長度為8的向量，即邊中所有的屬性用一個長度為8的向量來表示
• 全局信息（粉色）可以用一個長為5的向量來表示

圖神經(jīng)網(wǎng)絡所關注的重點

• 怎樣把所想要的信息表示成向量
• 這些向量是不是能夠通過數(shù)據(jù)來學到

圖一共有兩種

1、沒有方向的圖

• 沒有方向：兩個點之間相連的邊是沒有方向的
• 例如微信好友

2、有方向的圖

• 例如關注與互關

數(shù)據(jù)是如何表示成圖的

1、如何將圖片表示成一張圖

假設有一張高寬都為244的RGB三通道圖，一般來說會把它表示成一個三個維度的tensor（在輸入卷積神經(jīng)網(wǎng)絡的時候用的是tensor），但是也可以把它當作一個圖，它的每個像素就是一個點，如果兩個像素之間是連接關系的話，就連接一條邊

下圖展示了如何把一張圖片表示成圖

• 左邊表示圖片
• 右邊是表示成的鄰接矩陣
• 左邊圖片中00表示第0列第0行，它與鄰接矩陣中的對應關系入下圖中藍色圓圈所示，這樣就將圖片中的每個像素都映射成了圖上面的點

• 中間的矩陣叫做鄰接矩陣，它的每一行是一個頂點，每一列也是一個頂點，如果第 i 行和第 j 列之間值為1（圖中藍色的點）的話就表示第 i 個結點和第 j 個節(jié)點之間是有邊的，每一個藍色的點表示圖中的一條邊，剩下白色的點表示這些點之間是沒有邊的，所以叫做鄰接矩陣，通常是一個很大的非常稀疏化的矩陣

如何將文本表示成圖？

文本可以認為是一條序列，可以把其中每個詞表示成頂點，那么每個詞和下一個詞之間有一條有向邊（上一個詞和下一個詞之間有一條指向下一個詞的有向邊，在圖上面叫做有向的路）

除了文本和圖片能夠表示成圖之外，現(xiàn)實生活中還有很多數(shù)據(jù)也能表示成圖：

下圖所示是一個香料分子的示意圖

• 左圖是一個分子的圖片，由一些原子通過一些作用力連接在一起
• 每一個原子可以表示成圖里面的頂點，如下圖右圖所示，如果原子之間是相連的就可以連成一條邊

下圖所示是一個咖啡因的分子圖

• 同上，圖也能夠把整個分子的結構完整地表達出來

下圖是《奧賽德》劇中所有人物之間的交互圖（關系網(wǎng)絡）

• 在這個劇中任何人物如果在一個場景中同時出現(xiàn)的話，就會將其演繹成一條邊
• 處在邊緣的人物可能就是跟其他人交互比較少

下圖是空手道俱樂部的社交網(wǎng)絡圖

• 該俱樂部中有兩個老師，每個老師會跟一些同學比賽，然后可以把每一個老師跟每一個同學做過比賽的情況放在一起，這樣也會得到一個社交網(wǎng)絡圖

還有比較常見的就是引用圖

• 假設一篇文章引用了另一篇文章的話，就從當前文章出發(fā)連一條邊到另外一篇文章（這是一條有向邊，不代表會相互引用，通常來說，很少會有兩篇文章相互引用，一般是現(xiàn)在的文章引用之前的文章）

在實際中圖的大小情況如下表所示

• grapgh表示圖的個數(shù)
• node表示頂點數(shù)
• edge表示邊的個數(shù)
• mean表示平均每個點所連接的邊的數(shù)量
• min表示圖中一個頂點所連接的邊的數(shù)量的最小值
• max表示圖中一個頂點所連接的邊的數(shù)量的最大值
• 每一行就是一張圖
• 第一行是一個空手道俱樂部的社交網(wǎng)絡圖

在圖上面可以提出什么樣的問題？

圖層面的

下圖左邊是一些原始的圖，任務是要找出哪些圖中含有兩個圓環(huán)（給定一張圖，然后對圖進行分類）：

• 這里是一個很簡單的問題，不需要使用到機器學習，只需要使用簡單的編程，沿著圖遍歷一下就可以的
• 對于復雜一點的任務，可以借助圖神經(jīng)網(wǎng)絡

頂點層面的

下圖是上述空手道俱樂部的社交關系圖，假如某一天兩個老師不合決裂了，所有的學生要對這兩個老師進行站隊（站在某一個老師那邊）

邊層面的

如下圖所示，給定一張圖片，先通過語義分割及那個圖片中的人物、背景拿出來之后，然后判斷人物之間的關系（頂點已經(jīng)有了，需要判斷頂點之間的邊的屬性）

• 給定一個圖，然后把邊的屬性預測出來

總的來說就是三類問題

• 對整個圖進行識別
• 對頂點的屬性進行判斷
• 對邊的屬性進行判斷

機器學習用在圖上會有怎樣的挑戰(zhàn)？

雖然標題是機器學習，但是實際上講的是神經(jīng)網(wǎng)絡

將神經(jīng)網(wǎng)路用在圖上面最核心的問題是：如何表示圖使得它能夠和神經(jīng)網(wǎng)絡兼容

圖上面有四種信息

• 頂點的屬性
• 邊的屬性
• 全局信息
• 連接性：每條邊到底連接的是哪兩個點

前三個比較容易，因為都能夠使用向量來進行表示，神經(jīng)網(wǎng)絡對向量是友好的，問題在于如何表示連接性

連接性可以用鄰接矩陣來表示

• 如果有n個頂點的話，鄰接矩陣就是n*n的矩陣，其中如果兩個頂點直接相連的話值就為1，否則為0，這樣就能得到一個方形的矩陣

但是用鄰接矩陣來表示連接性的話也存在很多問題

• 鄰接矩陣可能會非常大：按照正常的存放可能存不下，由于它是一個稀疏矩陣，可以用稀疏矩陣的形式來進行存儲，使得它至少在存儲上是可行的。但是如果處理稀疏矩陣的話，高效地處理稀疏矩陣比較困難，特別是將稀疏矩陣用在GPU上面，一直是一個比較難的問題
• 鄰接矩陣其實將任何行或者列的順序交換都不會影響，視覺上可能是不一樣的，但是其實表示的是同一種東西，這就意味著如果設計一個神經(jīng)網(wǎng)絡不管使用哪種順序，放進神經(jīng)網(wǎng)絡之后都應該保證最后的結果是一樣的（因為不同的順序的鄰接矩陣其實表示的是同一張圖），有點類似于化學中的同分異構體

如果說既想要存儲高效，又想要排序不影響最終結果的話，文中提出了一種存儲方法，如下圖所示

• 圖中一共有8個頂點，7條邊
• 每個點的屬性使用的是一個標量來表示（也可以換成向量，并不影響）
• 每一條邊也是用一個標量來表示的（也可以換成向量，并不影響）
• 全局的信息也是用一個標量來進行表示的（也可以換成向量，并不影響）
• 鄰接列表：長度和邊數(shù)一樣，第 i 項表示第 i 條邊連接的兩個頂點
• 存儲高效：這樣在存儲上，只把邊和所有屬性存儲下來
• 與順序無關：可以把邊的順序任意打亂，只要把連接列表的順序也進行相應的變化就可以了。同理。也可以將頂點的順序全部打亂，只要將鄰接列表中的數(shù)字做相應 的更新就可以了
• 所以這樣存儲即使存儲高效的，也是與順序無關的

3、圖神經(jīng)網(wǎng)絡

圖神經(jīng)網(wǎng)絡的定義

GNN是對圖上所有的屬性（包括頂點、邊和全局上下文）進行的可以優(yōu)化的變換，這個變換能夠保持住圖的對稱信息（對稱信息指的是將頂點進行另外一種排序信息之后，整個結果不會發(fā)生改變）

message passing（信息傳遞神經(jīng)網(wǎng)絡，GNN也可以用別的神經(jīng)網(wǎng)絡來進行描述，這個地方用的是信息傳遞的框架）

GNN的輸入是圖，輸出也是圖，它會對頂點、邊和全局的向量進行變換，但是不會改變圖的連接性（頂點和邊的連接信息在進入圖神經(jīng)網(wǎng)絡之后是不會改變的）

構造一個最簡單的GNN

如下圖所示，對于頂點向量、邊向量和全局向量分別構造MLP（多層感知機），MLP的輸入大小和輸出大小相同，取決于輸入的向量

• fUn表示全局向量的MLP
• fVn表示頂點的MLP
• fEn表示邊的MLP
• 這三個MLP組成了GNN的層。這個層的輸入是圖，輸出還是圖，如下圖所示，它的作用是：對于頂點的向量、邊的向量和全局的向量分別找到對應的MLP，然后將它們放進去得到它們的輸出，作為其對應的更新，圖進去再出來之后的屬性都是被更新過的，但是整個圖的結構沒有發(fā)生變化（只對屬性集變化，但是不改變圖的結構）

• 因為MLP是對每個向量獨自作用的而不會考慮所有的連接信息，所以不管對整個頂點做任何排序信息都不會改變結果
• 所以這個最簡單的層就滿足了之前的兩個要求，也可以將這些層疊加在一起構造成比較深的GNN

最后一層的輸出怎樣得到想要的預測值？

首先考慮最簡單的情況：已知頂點向量，對每個頂點做預測

和一般的神經(jīng)網(wǎng)絡沒有太多區(qū)別，因為頂點已經(jīng)表示成向量了，然后要對它做預測的話，比如前述的空手到俱樂部的問題，其實就是一個簡單的二分類問題

• 每個學生已經(jīng)有了對應的向量表示
• 在后面加一個輸出為2的全連接層，然后再加一個softmax就能得到輸出了

如果是做n類的話，就加一個輸出大小是n的全連接層，然后再加一個softmax就能得到多類輸出了

做回歸的話就是單輸出就行了

如下圖所示，給定最后一層的輸出是一個圖，然后對于每一個頂點進入到全連接層，然后得到輸出，這樣就會對頂點作分類

• 注意：和之前一樣，不管有多少個頂點，只有一個全連接層（所有的頂點將會共享一個全連接層里面的參數(shù)）。在之前的GNN層里面，不管圖有多大，一層里面也就是3個MLP，所有的頂點、邊共享一個MLP，全局就一個就不用共享了

再考慮一個稍微復雜一點的情況

還是對頂點做預測，但是頂點并沒有表示成向量

pooling（匯聚）：和CNN中的pooling其實沒有太多本質上的區(qū)別

假設某個點沒有自己的向量，如何得到它的向量并做預測？

可以把跟這個點連接的那些邊和全局的向量拿出來，就會拿出五個向量，如下圖所示

• 箭頭表示對應的向量
• 中間的值是一個全局向量，所以沒有寫出來
• 將5個向量全部加起來，就會得到代表這一個點的向量（這里假設所有的頂點、邊和全局向量的維度是一樣的，如果不一樣的話則需要做投影）
• 最后加上一個全連接層就能得到輸出了，如下圖所示

• 上圖表示只有邊的向量En，沒有頂點的向量Vn，通過匯聚層（從邊到頂點），每個頂點都會得到自己的向量
• 最后進入到頂點之間共享的輸出層就能得到頂點的輸出了

同理，假設沒有邊的向量只有頂點的向量但是想對每個邊做預測的情況如下圖所示

• 可以把頂點的向量匯聚到邊上（一條邊連接兩個頂點，可以把這兩個頂點加起來，也可以加上全局向量），得到對應的邊的向量
• 然后進入邊向量的輸出層（所有的邊共享一個輸出層），最后得到邊的輸出

最后假設沒有全局的向量，但是有頂點的向量然后對整個圖做預測的情況

• 可以把所有頂點向量加起來，得到對應的全局向量
• 然后進入全局的輸出層，輸出層會得到全局的輸出

綜上所述，不管缺乏哪一類的屬性，都可以通過匯聚操作得到所缺失的屬性的向量，最后得到預測值

總結上面的內(nèi)容，就能得到一個簡單的GNN，如下圖所示，

• 給定一個輸入圖，首先進入一系列的GNN層（每個層里面有三個MLP，對應三種不同的屬性），會得到一個保持整個圖結構的輸出（但是里面所有的屬性已經(jīng)進行了更新）
• 最后根據(jù)所要預測的屬性添加合適的輸出層
• 但如果缺失信息的話可以加入合適的匯聚層就可以完成預測了
• 這是最簡單的情況。雖然這個情況很簡單，但是有很大局限性，主要的問題在于在GNN塊中并沒有使用圖的結構信息（對每個屬性做變換的時候，僅僅是每個屬性進入自己對應的MLP，并沒有體現(xiàn)出三者之間的相互聯(lián)系的連接信息），導致并沒有合理地把整個圖的信息更新到屬性里面，以至于最后的結果并不能夠特別充分利用圖的信息

如何對上述問題進行改進使得能夠將圖的信息盡早放進去

信息傳遞，工作原理如下圖所示

• 首先將上圖中橙色實心頂點的向量和它的鄰居的兩個頂點的向量加在一起得到一個匯聚的向量
• 再將這個匯聚的向量放進MLP得到該頂點向量的更新
• 其他頂點的操作同理（拿到每個頂點本身的向量以及它鄰居的向量加到一起，最后得到進入MLP之前的匯聚向量）
• 聚合步
• 更新步
• 這是一個最簡單形式的信息傳遞
• 這個跟標準的圖片上的卷積有點類似，等價于在圖片上做卷積，但是卷積核窗口里面每個窗口的權重是要相同的（因為在卷積里面其實是每一個頂點和它鄰居頂點的向量會做加權和，權重來自于卷積窗口），這里沒有加權和，只是加，所以權重應該是一樣的，但是通道還是保留了（卷積中有多輸入通道和多輸出通道，對應信息傳遞過程中MLP還是保留了），所以和卷積操作有點類似，但是還是有區(qū)別
• GNN層也可以通過堆疊來完成整個圖的長距離信息傳遞過程

下圖表示一個頂點，頂點之間通過距離為1的鄰居（一近鄰）將它的信息傳遞過來，就 ρ 從 v 到 v 的匯聚過程，這也是最簡單的信息傳遞的過程

再復雜一點，之前考慮過，假設確實某種屬性，可以從別的屬性匯聚過來，以彌補這個屬性，同理，不需要等到最后一層在進行匯聚，可以在較早的時候在邊和頂點之間匯聚信息

下圖展示了如何將頂點的信息傳遞給邊，然后再把邊的信息傳遞給頂點

• 首先通過ρ（V to E）把頂點的向量傳遞給邊（把每個邊連接的頂點信息加到邊的向量中，假設維度不一樣的話，會先做投影，投影到同樣的維度然后再加進去，這樣邊就拿到了頂點的信息）
• 同樣可以每個頂點可以把連接它的邊的信息也加到自己上面，同樣維度不同的話，可以先做投影（這里如果維度不一樣的話，會做兩次投影），維度一樣的可以直接相加
• 另外也可以將它contact在一起，也就是并在一起（類似于矩陣的拼接操作）
• 這樣就完成了頂點到邊的傳遞、邊到頂點的傳遞之后，再進入到各自的MLP做更新
• 這里是先把頂點的信息傳遞給邊做更新，然后再把更新過信息的邊的信息匯聚到頂點再做更新，如下圖左圖所示。如果反過來的話會得到不一樣的結論如下圖右圖所示

• 之前頂點和邊之間不交換任何信息，各自進行更新，所以誰先進行更新不影響
• 但是現(xiàn)在先更新頂點還是先更新邊會導致不一樣的結果，目前來說還沒有一致的結論說說先更新誰比較好，只是說這兩種會導致不一樣的結果
• 其實可以交替更新，如下圖所示：同時頂點匯聚到邊然后邊匯聚到頂點，匯聚之后先不要相加，然后再回來一次，就相當于兩邊的信息都有了，等價于兩個信息同時匯聚，最終向量可能會寬一點，這樣就不用擔心到底是先做誰的匯聚了

全局信息相關

之前有一個問題：因為每次只去看自己的鄰居，假設圖比較大而且連接沒那么緊密的時候，會導致信息從一個點傳遞到一個很遠的點需要走很長的步

解決方案：加入master node（或者叫context vector），這個點是虛擬的點，可以跟所有的頂點相連，也可以跟所有的邊相連（這里在圖上面不好說，因為一個頂點是沒辦法跟邊相連的，在這里是一個抽象的概念），它其實就是U，U跟所有的V里面的東西是相連的，跟E里面所有的東西也是相連的，所以如果想要把頂點的信息匯聚給邊的時候，也會把U匯聚過來，因為U跟邊是相連的（同理，匯聚頂點的時候，也會把U和它相連的E連過來），最后自己更新U的時候，會把所有的頂點信息和邊的信息都拿過來，最后完成匯聚再做更新

到此，這三類屬性都學到了對應的向量，而且這些向量在早期就已經(jīng)進行了大量的信息傳遞，最后在做預測的時候就可以只用本身的向量，也可以把相鄰的那些邊的向量也拿過來，甚至是把跟他相鄰的那些頂點的向量也拿過來，以及全局向量，也就是說不僅使用本身的向量，還可以將別的跟本身相關的東西都拿過來一起做預測

• 對于來自于不同類別的屬性，可以加在一起，合并在一起也可以。有一點像注意力機制（attention就是說將當前query的頂點和跟他相近的東西都拿過來，可以直接用圖的信息將這些相近的向量拿過來，這樣就完成了基于消息傳遞的圖神經(jīng)網(wǎng)絡的工作）

4、實驗

這部分是一個GNN的playgrround，作者吧GNN的訓練程序嵌入到了javascript里面，然后做了一個比較小的分子圖的預測數(shù)據(jù)集，使得可以調(diào)節(jié)圖神經(jīng)網(wǎng)絡里面不同的超參數(shù)，來觀察實際的訓練效果（整個過程是在瀏覽器中運行的，不需要安裝任何額外的程序）

可調(diào)節(jié)的超參數(shù)：

• 圖神經(jīng)網(wǎng)絡的層數(shù)：1層～4層
• 匯聚操作的方式：mean（每個向量按元素做平均，對應卷積神經(jīng)網(wǎng)絡中的average pooling）、sum（每個向量按元素求和，求和在卷積神經(jīng)網(wǎng)絡中用的不多）、max（每個向量按元素取最大值，對應卷積神經(jīng)網(wǎng)絡中的max pooling）
• 頂點的size：25、50、100（也可以取消勾選不學）
• 邊的size：5、10、20（也可以取消勾選不學）
• 全局向量的size：25、50、100（也可以取消勾選不學）

每次改變一個超參數(shù)，它就會重新對數(shù)據(jù)進行一次訓練，訓練使用的是50個epoch，訓練完之后會顯示auc（越大越好），每次可以調(diào)節(jié)不超參數(shù)得到不一樣的結果

下圖右側是對所有數(shù)據(jù)點的預測，

• 真實值的顏色用邊框表示，預測值用實心里面的顏色表示
• 邊框有兩個顏色，一個是紅色，一個是藍色，表示兩類
• 里面填的東西是預測值
• 如果邊框和實心都是紅色或者藍色的話，則預測是正確的，否則的話就是錯誤的
• 這里是對每個分子圖的向量投影到二維之后可視化的效果

• 左邊可以做預測，實時地對給定的圖做預測
• 可以對圖進行改變，可以多連一點邊出來或者改變某一個節(jié)點的原子
• 改變之后可以實時觀察預測值是多少然后在整個數(shù)據(jù)點上長什么樣子

超參數(shù)比較難調(diào)，作者給出了很多超參數(shù)對最后精度的影響

下圖表示的是模型可以學習參數(shù)的大小和最后測試的auc之間的關系

• 每一個點就是一個特定的超參數(shù)在模型訓練之后得到的結果，所以一個點就是一個模型
• x軸是參數(shù)的個數(shù)
• y軸表示auc，auc越高越好
• 整體來說，模型參數(shù)變高的時候，模型的auc的上限是上漲的，就算模型很大，參數(shù)也得調(diào)的比較好，不然也可能達不到很好的效果（也可能跟小模型具有一樣的效果）

具體每一個超參數(shù)對整個模型的影響

1、每一個屬性向量的長度（頂點、邊、全局），如下圖

• 每一個向量有三個可選的地方，對每一個特定的長度，變換別的參數(shù)之后平均下來的auc如上圖所示
• 圖中中間的橫線表示的是一個中值，矩形表示25%和75%的quantile（分位數(shù)），就是說在這個上面只有25%的點比這條線要高，只有25%的點比這條線要低，垂線的最頂端表示最大值，垂線的最底端表示最小值（具體含義可以看概率論中的箱線圖）
• 中值應該越高越好
• 整個圖形也不希望特別長，越長表示越敏感，越短表示越穩(wěn)定
  ?

  46:55

  ?
• 對于頂點來說，從25到50，中值向上升了一點，但是整體來看，敏感度沒有太大的變化，整體來說50比25要好一點
• 對于邊來說也是稍微大一點好一些
• 全局值的話也是稍微大一點好一些
• 整體來說都不是特別明顯，這些點的方差比較大

下圖展示的是不同的層數(shù)對精度的影響

• 左圖中x軸表示可以學習的參數(shù)個數(shù)，y軸是測試的精度
• 右圖是一個boxplot（箱線圖）
• 紅色表示1層GNN層
• 藍色表示2層GNN層
• 綠色表示3層GNN層
• 紫色表示4層GNN層
• 當層數(shù)越低的時候，可學習的參數(shù)就越少
• 從精度上看，左圖好像是耦合在一起的，但是從箱線圖來看，當層數(shù)增加的時候，中值還是在增加，但是方差還是挺大的，所以在左圖中看起來是耦合的
• 可以將層數(shù)調(diào)高一點，但是也的將剩下的參數(shù)調(diào)的夠好才行

下圖展示的是不同的聚合操作（求和、求平均、取max）對精度的影響

• 基本上可以發(fā)現(xiàn)沒什么區(qū)別，從箱線圖可以發(fā)現(xiàn)這三個幾乎是等價的，在這個數(shù)據(jù)集上，隨便用哪一個都行，對結果的影響不是很大

下圖展示的是在哪些屬性之間傳遞信息對精度的影響

• 綠色表示不傳遞任何信息，也就是最簡單的GNN，沒有任何消息傳遞，從箱線圖中可以看到它的精度是最差的，中值、方差都比較小
• 箱線圖的最右邊表示在頂點、邊、全局之間都傳遞信息，所有能傳遞信息的都進行傳遞，它的中值是最高的，但是如果參數(shù)沒調(diào)好，下面有三個out layer，如下圖所示

• 箱線圖中倒數(shù)第二個表示在頂點和全局之間傳遞信息，而沒有用邊，效果也是不錯的，這就意味著邊（也就是連接原子之間的那些鍵）在傳遞信息上的幫助并不是很大
• 但是傳遞的信息越少，基本上就是效果越差

總的來說，GNN對超參數(shù)還是比較敏感的，能調(diào)的超參數(shù)也很多

• GNN的層數(shù)
• 每一個屬性的大小
• 匯聚的操作方式
• 信息的傳遞方式

上述因素都對參數(shù)傳遞造成了很大的影響

5、相關技術

這部分討論了一些跟GNN相關的技術話題

除了上文中提到的圖，其實還有很多別的圖，如下圖所示

• 左圖是一個multi graph：頂點之間可以有多條邊，比如左圖中相同頂點之間不同顏色的邊表示不同種類的邊（紅色的無相邊、綠色的有相邊）
• 右圖表示圖可能是分層的：其中有一些頂點可以能是一個子圖（hypernode）
• 不同的圖結構會對神經(jīng)網(wǎng)絡做信息匯聚的時候產(chǎn)生影響

怎樣對圖進行采樣和做batch？

假設有很多層的時候，最后一層的頂點就算只看它的一近鄰，最后頂點由于有很多層消息傳遞，所以它實際上是能看到一個很大的圖，在圖連通性足夠的情況下，最后這個頂點有可能會看到整個圖的信息

在計算梯度的時候，需要把整個forward中所有的中間變量存下來，如果最后一層的頂點想要看整個圖的話，意味著在算梯度的時候需要把整個圖的中間結果都存下來，就導致計算量大到無法承受，因此就需要對圖進行采樣

• 在圖中每次采樣一個小圖出來，在這個小圖上做信息的匯聚，這樣算梯度的時候就只需要將小圖上的中間結果記錄下來就行了

采樣方法

• 左圖表示隨機采樣一些點，然后將這些點最近的鄰居找出來
• 左圖中采樣了4個黃色的點，然后把它們的鄰居（紅色點）找了出來，在做計算的時候，只在這個子圖上做計算，通過控制每次采樣的點的數(shù)量，可以防止采樣的子圖過大，以保證內(nèi)存能夠將所有的中間變量存下來
• 右圖表示隨機游走采樣：從某個一個頂點開始，然后隨機在圖中找到一條邊，然后沿著這條邊走到下一個頂點，按照這種方式在圖中隨機游走
• 可以通過規(guī)定隨機游走的步數(shù)，來得到子圖

• 左下角的圖表示以上兩種方式的結合：先隨即走三步，然后把這三步每個點的鄰居找出來

• 右下角的圖表示取一個頂點，然后將它的一近鄰、二近鄰、三近鄰往前走k步做一個寬度遍歷，然后把所得到的子圖拿出來

以上四種采樣方法，具體哪一種使用效果比較好，取決于整個圖的樣子

如何做batch？

從性能上考慮，不希望對每一個頂點逐步逐步更新，這樣每一步的計算量太小，不利于并行，希望是像別的神經(jīng)網(wǎng)絡一樣，將小樣本做成小批量，這樣來對大的矩陣或者tensor做運算

• 這里存在一個問題：每一個頂點的鄰居的個數(shù)是不一樣的，如何將這些頂點的鄰居通過合并變成一個規(guī)則的張量是一個具有挑戰(zhàn)性的問題

inductive biases

任何一個神經(jīng)網(wǎng)絡，或者說任何一個機器學習的模型中都存在假設

• 卷積神經(jīng)網(wǎng)絡假設的是空間變換的不變性
• 循環(huán)神經(jīng)網(wǎng)絡假設的是時序的延續(xù)性
• 圖神經(jīng)網(wǎng)絡假設的是：保持了圖的對稱性（不管怎樣交換頂點的順序，GNN對圖的作用都是保持不變的）

不同匯聚操作的比較

匯聚操作包括求和、求平均或者求max，但是其實沒有一種是特別理想的

• 左圖表示max不能區(qū)分這兩個網(wǎng)絡
• 右圖表示max和mean不能區(qū)分這兩個網(wǎng)絡
• 因此沒有一個聚合操作是比另外一個更好的，也就是說，在實際中，這三個聚合操作都差不多，所以在實際應用中，應該具體分析哪一種更加適合

GCN作為子圖的函數(shù)近似

GCN是graph convolutional network（圖卷積神經(jīng)網(wǎng)絡），就是上面提到的那個帶匯聚操作的圖神經(jīng)網(wǎng)絡

• GCN如果有k個層，每一層都是看一個它的鄰居的話，就等價于在卷積神經(jīng)網(wǎng)絡里面有k層3*3的卷積。如果是這樣的話，每一個最后一層看到的頂點是一個大小為k的子圖（最遠的頂點距離當前這個點的距離是k，因為每經(jīng)過一層就相當于往前看了一步），這樣的話可以認為每個點都是看以自己為中心往前走k步的子圖的信息的匯聚
• 所以從一定程度上來說，GCN可以認為是：n個以自己為中心往前走k步的子圖，最后求embeding

將點和邊做對偶

圖論：可以把點變成邊、邊變成點，鄰接關系表示保持不變，這種變換在GNN上也可以使用

圖卷積和矩陣乘法的關系（如何高效實現(xiàn)整個圖神經(jīng)網(wǎng)絡的關鍵點）

在圖上做卷積或者做random work，等價于將它的鄰接矩陣拿出來做矩陣乘法

• page rank就是在一個很大的圖上面隨機游走，將鄰接矩陣和一個向量不斷地做乘法

graph attention network

在圖上做匯聚的時候是每個頂點和它鄰接的頂點的權重加起來，但是如果是做卷積的話是做加權和，同理，在圖上也可以做加權和，但是需要注意卷積的權重是跟位置相關的（每個3*3的窗口固定的點上有固定的權重），而對于圖來說不需要有位置信息（因為每個頂點的鄰居個數(shù)不變，而且鄰居是可以隨意打亂順序的，權重對位置信息是不敏感的）,所以可以用注意力機制，權重取決于兩個頂點向量之間的關系，而不是頂點的位置，在使用attention之后，可以給每個頂點一個權重，再按這個權重加起來就得到了一個graph attention network

圖的可解釋性

在圖上面訓練了一個模型之后，怎么理解它學到的東西

可以將子圖中的信息抓取出來，看它到底學到的是什么信息

generative modeling

圖神經(jīng)網(wǎng)絡是不改變圖的結構的，如果想要生成圖，怎樣對圖的拓撲結構進行有效的建模，提出了一些算法

6、評論

寫作

• 首先介紹了什么是圖（圖的屬性（頂點、邊、全局）應該用向量來表示），然后介紹了現(xiàn)實生活中的數(shù)據(jù)如何表示成圖，怎樣對圖（頂點、邊、整個圖）做預測，機器學習的算法用到圖上的時候有一些怎樣的挑戰(zhàn)
• 然后開始講GNN：首先對GNN下定義（GNN就是對屬性做變換，但是不改變圖的結構），然后給了一個最簡單的例子（用三個全連接層對每個屬性單獨做變換，再加一個輸出層來做預測），再介紹如何解決數(shù)據(jù)的缺失問題（聚合操作來彌補缺失的屬性）
• 然后開始介紹什么是真正意義上的GNN，在每一層中通過匯聚操作將整個信息傳遞過來（每個頂點去看它鄰接頂點的信息，以及看它鄰接邊的信息或者是全局信息），在每個層中如果能夠充分地匯聚圖上的信息，GNN就能很有效地對整個圖的結構進行發(fā)掘
• 接下來是實驗部分：對不同的超參數(shù)在數(shù)據(jù)集上得出了很多結果，然后總結了每個超參數(shù)對結果的影響
• 最后對GNN相關的問題進行了展開
• 這個文章的特點是圖很漂亮，制作精美，而且基本上都是交互圖（交互圖可以把很多信息都放進去，使得圖既不是很臟，讀者又能通過圖獲得很多東西）

缺點

• 圖既是優(yōu)點也是缺點，這種交互圖制作非常困難，導致寫作門檻比較高
• 作者可以避免用公式和代碼來對一個問題進行描述，而是大量地使用圖和文字。有時候使用公式其實更加簡潔準確，代碼可以體現(xiàn)出很多細節(jié)上的東西，最好能結合公式、代碼、圖多維度描寫
• 最后一節(jié)寬度的展開有一點畫蛇添足，前面已經(jīng)講得很好了，但是后面又做了展開，每一個展開并沒有講清楚細節(jié)

圖神經(jīng)網(wǎng)絡

• 圖是一個非常強大的工具，基本上所有的數(shù)據(jù)都能夠表示成圖，但也存在問題：在圖上進行優(yōu)化非常困難，因為圖是稀疏架構，每個結構都是動態(tài)結構，使得計算比較困難
• 圖神經(jīng)網(wǎng)絡對超參數(shù)是非常敏感的
• 上述兩個原因導致圖神經(jīng)網(wǎng)絡的門檻比較高，在工業(yè)上的應用依然比較少

本文完成的是一個介紹性的工作

----end----