GCN（圖卷積）

神經(jīng)網(wǎng)絡(luò)在過去的十年里取得了巨大的成功橡疼，然而早期的神經(jīng)網(wǎng)絡(luò)變體只能使用規(guī)則結(jié)構(gòu)的數(shù)據(jù)或歐幾里得數(shù)據(jù)(Euclidean data)來實現(xiàn)晓折，而現(xiàn)實世界中的大量數(shù)據(jù)具有底層的非歐幾里得(Non-Euclidean)圖結(jié)構(gòu)(Graph structures)骨稿。圖神經(jīng)網(wǎng)絡(luò)(Graph Neural Networks)的出現(xiàn)解決了圖數(shù)據(jù)結(jié)構(gòu)的不規(guī)則性(Non-Regularity)問題翔曲，而圖卷積網(wǎng)絡(luò) (GCN)就是最基本的圖神經(jīng)網(wǎng)絡(luò)變體之一抖韩。在這篇文章中我們將由淺入深的介紹GCN的實現(xiàn)原理败玉。

圖 - Graph

由于圖(Graph)的獨特功能可以捕獲數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系敌土，它被廣泛應(yīng)用于各種領(lǐng)域，從社交網(wǎng)絡(luò)分析运翼，生物信息學(xué)到計算機視覺返干，許多現(xiàn)實生活中的問題都可以用圖來表示，這里列舉了2021年最熱門的一些圖神經(jīng)網(wǎng)絡(luò)的應(yīng)用, 感興趣的可以了解一下南蹂。

什么是圖犬金，數(shù)據(jù)如何通過圖來表示？

圖(Graph)包含著節(jié)點(node)信息六剥，邊(edge)信息晚顷，全局(global)信息，是一種數(shù)據(jù)結(jié)構(gòu)疗疟，它可以表示一組或多組對象以及對象之間的關(guān)系和連接(connection)该默。圖1給出了幾個可以用圖(Graph)表示信息的例子，圖1中紅色的圖(Graph)可以看作是一個社交網(wǎng)絡(luò)的表示策彤，其中人物(Peter, Mary...)可以看作是圖的節(jié)點(Node)栓袖，人物之間的關(guān)系(friend, brothers...)可以看作是圖的邊(Edge)，而全局信息可以是這個社交網(wǎng)絡(luò)涉及的人數(shù)或者關(guān)系的類型數(shù)量店诗。這些信息集合在一起裹刮，形成了一個圖(Graph)。而我們的圖神經(jīng)網(wǎng)絡(luò)就是基于這樣的一張圖實現(xiàn)的庞瘸，通過不斷學(xué)習(xí)圖的信息來完成任務(wù)捧弃。

圖1. 使用Graph來表示實際問題的例子 [1]

什么樣的問題或任務(wù)需要用到圖(Graph)數(shù)據(jù)結(jié)構(gòu)?

我們已經(jīng)知道如何用圖來表示信息了，接下來我們需要知道要使用這些圖數(shù)據(jù)來做什么類型的預(yù)測任務(wù)。當前基于圖實現(xiàn)的預(yù)測主要分為以下幾類：

節(jié)點分類(Node classification): 預(yù)測給定節(jié)點的類型以及屬性违霞，一個標簽對應(yīng)一個節(jié)點
關(guān)聯(lián)預(yù)測(Link prediction): 預(yù)測兩個節(jié)點是否連通以及節(jié)點之間的連接關(guān)系
社區(qū)檢測(Community detection): 識別連接緊密的節(jié)點集群, 揭示網(wǎng)絡(luò)聚集行為
網(wǎng)絡(luò)相似性(Network similarity): 兩個(子)網(wǎng)絡(luò)的相似程度
圖級任務(wù)(Graph-level task): 預(yù)測整個圖的屬性嘴办，一個標簽對應(yīng)一個圖

當前應(yīng)用比較多的是關(guān)聯(lián)預(yù)測(Link prediction)，也叫做鏈路預(yù)測买鸽。在推薦系統(tǒng)的構(gòu)建中常常用到它涧郊。關(guān)聯(lián)預(yù)測也經(jīng)常在社交網(wǎng)絡(luò)中用于向用戶推薦朋友，除此之外它也經(jīng)常被用來預(yù)測犯罪關(guān)聯(lián)眼五。

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

要想理解GCN妆艘，我們首先需要了解和學(xué)習(xí)GNN相關(guān)的一些基礎(chǔ)和原理，因為GCN實際上是基于GNN做了一些改變弹砚。文章的開頭我們提到很多神經(jīng)網(wǎng)絡(luò)如CNN面向的圖像數(shù)據(jù)和RNN面向的文本數(shù)據(jù)的格式都是固定的双仍。因此面對本身結(jié)構(gòu)、彼此關(guān)系都不固定的節(jié)點特征桌吃，我們必須要借助圖結(jié)構(gòu)來表征它們的聯(lián)系。而GNN面向的輸入對象就是這些結(jié)構(gòu)不規(guī)則苞轿、不固定的數(shù)據(jù)結(jié)構(gòu)茅诱。

對于一張輸入的圖(Graph)，節(jié)點信息搬卒，邊的信息瑟俭，整張圖的全局信息都可以被編碼成特征向量，這些特征可以被GNN提取然后用于分類等任務(wù)契邀，所以實際上GNN依然會像CNN那樣做提取特征的工作摆寄，只是方式不同。

鄰接矩陣(Adjacency Matrix)

對于圖神經(jīng)網(wǎng)絡(luò)來說坯门，鄰接矩陣是非常重要的一個概念微饥。它可以將圖的連通性形象的表示出來，節(jié)點與節(jié)點之間是否有邊相連接古戴，通過這個矩陣我們就可以知道欠橘。那么鄰接矩陣一般怎么生成呢？

以下圖(圖2)為例现恼，我們將原始圖像(Image)視為具有圖像通道的矩形網(wǎng)格(圖2中最左)肃续。在圖問題中，我們可以將圖像(Image)看作是具有規(guī)則結(jié)構(gòu)的圖(Graph)的另一種方式叉袍，其中每個像素代表一個節(jié)點始锚，并通過邊緣連接到相鄰像素(圖2中最右)。每個非邊界像素恰好有 8 個鄰居喳逛，每個節(jié)點存儲的信息是一個 3 維向量瞧捌，表示該像素的 RGB 值。最終我們就會得到最右邊的圖(Graph)艺配。需要注意的是察郁，一般問題中生成的圖(Graph)不會是如此規(guī)則的衍慎。有了Graph之后我們就知道了所有節(jié)點的連接關(guān)系，我們就可以生成圖2中間的鄰接矩陣皮钠。鄰接矩陣的大小取決于節(jié)點的個數(shù)稳捆，N個節(jié)點，鄰接矩陣就是N x N的大小麦轰。如果節(jié)點間有一條邊相連乔夯，那么對應(yīng)的矩陣里的格子就是藍色，不相連就是白色款侵，一般用1和0表示末荐，1就是相連，0是不相連新锈。

圖2. 鄰接矩陣 [2]

聚合操作 & 特征更新

GNN的輸入一般是所有節(jié)點的起始特征向量和表示節(jié)點間連接關(guān)系的鄰接矩陣甲脏。聚合操作和節(jié)點特征更新是圖神經(jīng)網(wǎng)絡(luò)的核心操作。以圖3為例妹笆，我們首先考慮A節(jié)點块请，聚合操作會將當前節(jié)點A的鄰居節(jié)點信息乘以系數(shù)聚合起來加到節(jié)點A身上作為A節(jié)點信息的補足信息，當作一次節(jié)點A的特征更新拳缠。對圖中的每個節(jié)點進行聚合操作墩新，更新所有圖節(jié)點的特征。通過不斷交換鄰域信息來更新節(jié)點特征窟坐，直到達到穩(wěn)定均衡佣盒，此時所有節(jié)點的特征向量都包含了其鄰居節(jié)點的信息肆氓，然后我們就能利用這些信息來進行聚類、節(jié)點分類、鏈接預(yù)測等等爸黄。不同的GNN有不同的聚合函數(shù)糊昙，可根據(jù)任務(wù)的不同自由選擇轴捎，這里舉的只是一個很簡單的例子废亭，重點是要明白我們需要用到什么信息需要做什么操作，做這些操作的目的是什么懒豹。一次圖節(jié)點聚合操作和權(quán)重學(xué)習(xí)芙盘，可以理解為一層神經(jīng)網(wǎng)絡(luò)，后面再重復(fù)進行聚合脸秽、加權(quán)儒老，就是多層迭代了。一般GNN只要3~5層就可以學(xué)習(xí)到足夠的信息记餐，所以訓(xùn)練GNN對算力要求很低驮樊。注意， GNN 不會更新和改變輸入圖(Input Graph)的結(jié)構(gòu)和連通性，所以我們可以用與輸入圖相同的鄰接矩陣和相同數(shù)量的特征向量來描述 GNN 的輸出圖(Output Graph)囚衔，輸出的圖只是更新了每個節(jié)點的特征挖腰。

圖3. GNN原理

圖卷積網(wǎng)絡(luò) (GCN)

論文地址: Semi-Supervised Classification with Graph Convolutional Networks
上一段我們介紹了GNN的原理，實際上在GCN中我們也同樣需要進行聚合操作和特征更新练湿，也同樣需要用到鄰接矩陣猴仑，那么GCN和GNN有什么不一樣呢？圖3中我們知道在聚合鄰居信息時需要給鄰居的信息乘上一個系數(shù)再進行相加肥哎，GNN中這些系數(shù)(a, b, c...)的設(shè)定是沒有規(guī)則的辽俗，是初始隨機設(shè)定然后在訓(xùn)練過程中不斷學(xué)習(xí)的。但是GCN提出解決了a,b,c這些系數(shù)的設(shè)定問題篡诽，下面我們來看一下GCN的基本思路崖飘。

首先，我們先了解一些關(guān)于GCN的數(shù)學(xué)概念：

圖4. GCN相關(guān)數(shù)學(xué)概念

圖中提到的矩陣都是重要的GCN輸入杈女，我們需要用它們來提取節(jié)點的特征然后做聚合和更新朱浴。其中度矩陣我們還沒有解釋，它實際上表示了每個節(jié)點鄰居的數(shù)量达椰，有多少度數(shù)也就是有多少個節(jié)點與它相連赊琳。例如A節(jié)點只有一個鄰居，那么它的度就是1砰碴，相應(yīng)矩陣上的值就是1，度矩陣只有對角線上有值板丽。

接下來呈枉，我們需要理解A矩陣和X矩陣相乘的含義，因為它們的相乘代表了GCN的聚合操作埃碱。以圖5為例猖辫，觀察鄰接矩陣的第一行，我們看到節(jié)點 A 與 E 有一個連接砚殿。相乘之后啃憎，結(jié)果矩陣的第一行是 E 的特征向量。同樣似炎，結(jié)果矩陣的第二行是 D 和 E 的特征向量之和辛萍。通過將A和X相乘，我們可以得到所有鄰居向量的和羡藐。

圖5. 通過矩陣相乘聚合鄰居信息

但如果只是簡單的這樣做來得到鄰居信息的聚合贩毕，會出現(xiàn)兩個問題：

我們沒有包含節(jié)點本身的特征。結(jié)果矩陣也應(yīng)該包含節(jié)點本身的特征仆嗦。
我們需要取平均值或者鄰居的特征向量的加權(quán)平均值辉阶，而不是 sum() 函數(shù)把這些信息全部加起來。原因是在使用 sum() 函數(shù)時，度數(shù)高的節(jié)點可能會對度數(shù)低的節(jié)點的更新有很大的影響谆甜，而實際上如果一個度數(shù)低的節(jié)點在特征更新的過程中加入了全部的度數(shù)高的節(jié)點信息垃僚，這是不合理的(圖6)。此外规辱，神經(jīng)網(wǎng)絡(luò)對輸入數(shù)據(jù)的規(guī)模很敏感谆棺。因此，我們需要對這些向量進行歸一化以消除潛在問題按摘。

圖6

對于第一個問題：

圖7. 添加單位矩陣來加入節(jié)點自己的信息

對于第二個問題

圖7

圖8

我們現(xiàn)在得到的就是加權(quán)平均值包券，我們這里做的是對度數(shù)低的節(jié)點增加權(quán)重，減少度數(shù)高的節(jié)點的影響炫贤。這種加權(quán)平均的想法是溅固，我們假設(shè)低度節(jié)點對其鄰居產(chǎn)生更大的影響，而高度節(jié)點產(chǎn)生的影響較小兰珍，因為它們將影響分散在太多的鄰居身上侍郭。到這一步，歸一化已經(jīng)算完成了掠河，但在論文中作者最后提出的歸一化公式其實是對D開了根號并在A兩側(cè)都進行了相乘(圖10)亮元。但在實際情況的代碼中，用到的歸一化還是( $D^-1$ A)比較多唠摹，因為實驗發(fā)現(xiàn)其實用哪種歸一化公式爆捞，性能的差別不會太大。

圖9

最后我們來看一下GCN的公式

圖10. GCN公式

這里的?實際上已經(jīng)是歸一化之后的?了勾拉，也就是說 $?=D^{-1}A$ 煮甥。同樣的，一次聚合更新操作代表GCN的一層藕赞。層數(shù)是節(jié)點特征可以行進的最遠距離成肘。例如，使用 1 層 GCN斧蜕，每個節(jié)點只能從其鄰居那里獲取信息双霍。收集信息過程獨立進行，所有節(jié)點同時進行批销。當在第一層之上堆疊另一層時洒闸，我們重復(fù)收集信息過程，但這一次风钻，鄰居已經(jīng)有了關(guān)于他們自己鄰居的信息（來自上一步）顷蟀。因此，根據(jù)我們認為節(jié)點應(yīng)該從網(wǎng)絡(luò)中獲取信息的程度骡技，我們可以為設(shè)置相應(yīng)的層數(shù)鸣个。但一般通過 6-7 層羞反，我們幾乎可以得到了整個圖，這使得聚合變得不那么有意義囤萤。因為節(jié)點每更新一次昼窗，感受野就變大一些，如果網(wǎng)絡(luò)太深涛舍，那么每個節(jié)點就會受無關(guān)節(jié)點的影響澄惊，效果反而下降。

參考文獻:
[1] Graph Convolutional Networks (GCN)
[2] A Gentle Introduction to Graph Neural Networks
[3] GNN的理解與研究