本文概覽：

1. 圖卷積背景和基本框架

1.1 圖算法介紹

我們都知道在數據結構中，圖是一種基礎且常用的結構。現實世界中許多場景可以抽象爲一種圖結構，如社交網絡、交通網絡、電商網站中用戶與物品的關係等。

目前提到圖算法一般指：

• 經典數據結構與算法層面的：最小生成樹(Prim, Kruskal, ...)，最短路(Dijkstra, Floyed, ...)，拓撲排序，關鍵路徑等；

• 概率圖模型：涉及圖的表示、推斷和學習；

• 圖神經網絡 （Graph Neural Network, GNN） ：主要包含圖表示學習（Graph Embedding）和圖卷積網絡（Graph Convolutional Network, GCN）。近年來，Graph Embedding和GCN成爲網絡數據分析與應用的熱點研究問題。

1.2 深度學習介紹

深度學習技術爲計算機視覺（人臉識別）、語音識別、自然語言處理、強化學習（AlphaGo）等領域的發展做出了重要的貢獻。深度學習作爲一種如此重要的技術，主要有三個特點：

• 權重分配：訓練過程中有一個權重的分配，形成一個權重矩陣，在模型訓練過程中學習得到權重矩陣；

• 層級結構：網絡中每一層的結果都依賴於上一層網絡，網絡中信息是一層一層往下傳遞；

• 歐幾里得空間數據：網絡輸入的數據是歐幾里得空間數據。

什麼叫歐幾里得空間數據呢？我們在學習數學的過程中經常用一維座標、二維座標、三維座標，甚至是用多維座標來表示數據在哪一個位置上，表現數據之間的“距離”可以很容易在二維座標中體現，表現數據的“立體結構”可以很容易在三維座標中體現，這就是歐幾里得空間數據。例如下圖所示：圖像是一個二維數據，用xy座標就可以表示；語音數據就是一個一維數據，它是一個時間數據，隨着時間的變化有相應的信息；自然語言處理也可以用一個二維座標進行表示；圍棋也是一個二維座標。

1.3 圖結構數據

在深度學習處理的數據類型裏面，大部分數據是能通過歐幾里得空間進行一個轉換，把數據投射到一個座標軸裏。但是在實際生活中，有很多數據不是能簡簡單單通過歐幾里得結構進行表達的。比如在社交網絡裏，我們都會使用微信，人與人之間會通過微信加朋友，我們把每一個人當作節點，人與人之間形成的朋友關係當作邊，這樣就會形成一個圖。在這個圖裏面，沒有任何的距離信息，也沒有任何的空間信息，這是一種非歐幾里得的空間結構信息。那怎麼對這種結構信息進行訓練呢？在以往的深度學習模型中（比如CNNs、RNNs等）無法完成這類數據的學習，所以纔出現了圖卷積技術來解決這類數據的疑難問題。

現實生活中非歐幾里得的數據有哪些呢？比如：

• 剛纔說的社交網絡；

• 還有科學網絡，科學家之間的網絡，寫了一篇論文，論文裏有哪些作者，作者之間互相引用論文就會形成一個很大的引用論文的網絡；

• 通信網絡，所有的無線通信設備、物聯網都是通信網絡；

• 多用戶系統，就是一個系統裏面有很多用戶，上面提到的社交、科學、通信三個網絡都屬於多用戶系統網絡；

• 知識圖譜，也是一個很大的圖結構；

• 分子網絡，分子結構也能構成一個圖；

• 地圖信息，地圖中的每一個購物地點，也可以構成一個圖的結構。

以上提到的這些例子，在深度學習裏面用CNNs和RNNs來處理這些非歐幾里得結構數據效果不是很好，所以我們提出了圖卷積網絡（Graph Convolutional Network，GCN）。

1.4 圖卷積發展歷史

關於圖卷積的發展歷史，我們從兩條線來講。第一條線是“空間域”，也稱爲實域（Spatial methods），第二條線是“頻域”（Spectral methods），頻域和實域可以通過傅里葉變換相互轉化。

在2005年的時候Gori等人提出了GCN的基本概念，由於1998的時候CNN剛被提出來，在2005的時候CNN是非常的火熱，科學家並沒有把重心放在GCN的基本概念上。經過十年的發展，提出CNN團隊的科學家Bruna等人發現用現有網絡不能很好的處理非歐幾里得數據，因此提出GCN在頻譜上的應用，把頻譜上原始的實域數據轉化到頻譜上，然後做一個CNN深度學習卷積，發現效果不錯。但是在2015年的時候，是缺乏理論支持的。直到2016年，相關的科學家Defferrard等人提出了一些理論的支持，解釋了GCN爲什麼在分類上有好的結果，因爲科學家從頻譜上論證了GCN的可控性。同時在2016年，Li等人將GCN在實域過程中做了一個簡單的應用，告訴大家GCN有一個很好的分類效果，但是也缺乏理論的解釋。

直到2017年，Kipf & Welling等人的GCN文章橫空出世，他們發現GCN把頻域和實域兩個域的數據通過數學公式的證明可以聯繫起來。之前的工作有一部分是通過頻域來驗證GCN的好壞，還有一部分工作是在實域上做一些嘗試，發現GCN效果不錯。Kipf & Welling等人的文章就解釋了爲什麼GCN效果不錯、GCN爲什麼可以處理實域上的數據，也提出了一些最簡單、最基本的模型。隨着Kipf & Welling等人文章的發表，在2018年的時候GCN受到了廣大科研工作者的重視，然後大家就在這篇文章的基礎上不斷地創新和改進，提出各種各樣的模型。

1.5 圖概念回顧

圖是由若干頂點及邊所構成的圖形，圖中可以無邊，但至少包含一個頂點。

通常使用鄰接矩陣來表示和存儲圖。對於一個含有個頂點的圖，採用一個大小爲的矩陣存儲圖的結構。對於有權圖，可以表示到的邊的權重；如果是無權圖，則可設爲表示存在邊，表示不存在邊，如果兩個頂點有多條邊，則就是邊數之和。因此鄰接矩陣的表示相當的直觀，而且對於查找某一條邊是否存在、權重多少非常快。但其比較浪費空間，對稠密圖來說，會比較適合。

鄰接矩陣 對角線 上元素都是， 上三角矩陣 和 下三角矩陣 以對角線而對稱。在圖的實際應用中，只看上三角或下三角就可以了。

1.6 圖卷積基本框架

圖卷積的核心基本框架包括兩個矩陣：（1）一個是鄰接矩陣，有個節點，矩陣的維度就是；（2）另一個是特徵矩陣，矩陣H的維度爲，其中代表圖中節點的個數，爲每個節點的特徵維度。比如，我們每個人在社交網絡中都是一個節點，但是我們的性別、年齡、籍貫等信息就是我們的特徵。

在圖卷積基本框架中，輸入層輸入的是鄰接矩陣，在隱藏層把特徵矩陣點乘到每一個節點上進行訓練，網絡每次更新都是更新特徵矩陣，圖結構是不變的，經過多次訓練以後，特徵矩陣達到收斂的情況（也就是特徵矩陣中值基本不變），最後再做一個分類，給出概率，判斷圖中節點屬於哪一類。在整個網絡訓練過程中，把節點和特徵做了一個點乘，實現了節點和特徵在社區間的傳遞。

下面，給大家介紹一下GCN的數學概念，主要包含GCN的特徵信息如何跟節點點乘結合在一起，一層一層往下傳遞進行訓練的。

1.7 卷積神經網絡回顧

在卷積神經網絡中，上一層輸出的特徵圖與過濾器進行卷積操作，即輸入項與過濾器之間進行點積運算，然後將結果送入激活函數，就可以得到輸出特徵圖。下圖展示的是過濾器對輸入特徵圖的一次卷積操作，公式如下圖中所示。

1.8 圖卷積

卷積神經網絡的前向傳播公式爲：

圖卷積的前向傳播公式爲：

對比圖卷積網絡與卷積神經網絡的前向傳播公式可以發現，圖卷積網絡加入了鄰接矩陣的信息。如下圖所示，計算更新紅點，就是以它周邊相鄰的四個點來更新它自己，不需要把不相鄰的節點信息更新過來。

上面的公式接着往下推導就是，鄰接矩陣點乘特徵矩陣再點乘權重矩陣，經過激活函數然後更新到下一層的特徵矩陣中，直到基本沒有變化的時候，就可以停止更新。

在上述步驟中會有幾個問題：

• 如果只用鄰接矩陣的話，由於鄰接矩陣中節點自身沒有環，對角線上的元素都爲，在訓練的過程中不能考慮自身的信息；

• 鄰接矩陣沒有歸一化，可能導致度大的節點，具有更大的特徵值，影響特徵提取，模型收斂。

爲了解決以上問題，進行了拉普拉斯的變化，對上式做進一步改進。爲圖的度矩陣，爲圖的鄰接矩陣，進行的操作，解決對角線的問題，使訓練中涵蓋了自身節點的信息。公式如下：

然後再解決歸一化的處理，下面兩個式子都是拉普拉斯歸一化處理：

歸一化處理的主要目的是，希望這些特徵值更加均勻化，不需要特別大的特徵值，導致最終影響特徵提取和模型訓練。大部分會選擇第一個式子作爲歸一化處理，因爲它訓練出來的矩陣是對稱的，另外矩陣的每一列相加的值爲。

1.9 圖卷積的演示

上圖中一共有六個節點，鄰接矩陣中節點和節點有邊，相應位置值爲，節點和節點也有邊，相應位置爲。度矩陣就是隻有對角線有值，該值是對應節點有多少條邊，節點有兩條邊，節點有三條邊。度矩陣減去鄰接矩陣就變成了拉普拉斯矩陣了。然後，在下式中對度矩陣求逆開根號，然後乘以拉普拉斯矩陣，最後不斷的更新。

在這個例子中，沒有給定，我們隨機出一個，它是一個的矩陣，也是一個隨機出的矩陣。在GCN的卷積過程中，權重不像CNN中那麼重要，很多時候我們在做GCN卷積的時候，權重就是隨機產生的。經過多次循環訓練，得到一個收斂的情況，特徵矩陣就是這樣的值。然後在求中每一列的最大值，再進行列數的分類，我們可以發現第、、、個節點分類是，第、個節點分類是。GCN可以很好地把圖的結構，分成了兩類，、、這三個節點在圖論裏面是全連接圖，那這三個節點很相似；第、節點都有三條邊，所以把也分到了、、對應的類別中；和自然而然就沒有和其他節點關係那麼密切，就把和分到另一類中。

這個例子中想給大家突出兩點，第一點就是隨機產生了特徵矩陣，依據圖的拓撲結構，就能得到一個很好的分類效果；第二點就是通過這個例子把抽象的理論具體化，大家就能看懂這個矩陣是怎麼計算的。

圖卷積的核心就是更新這個公式，那麼在圖卷積的應用和開發過程中兩個核心的創新是特徵矩陣和鄰接矩陣。

1.10 圖卷積：邊信息嵌入

在圖的拓撲結構中，有時邊是有權重的，如果這個權重值單單放在鄰接矩陣中（也就是權重信息放在點裏），僅僅有鄰接矩陣的乘積並不能突顯出邊的信息。如果要把邊的信息考慮進圖卷積中，我們可以把圓圖轉爲線圖。如下圖所示，圓圖有、、三個點，邊是、、，轉換後就是把邊看成點，點看成邊。因爲邊裏面也有特徵信息，這個時候進行兩次的圖卷積的迭代和循環，能很好的把邊的信息整合進去了。訓練的過程是一樣的，重要的是如何把圓圖轉換成線圖。這樣做的優勢是把邊的信息考慮進去，支持稀疏矩陣的計算，從多角度考慮（即考慮了邊，又考慮了點）。條件的侷限性是，由於邊轉成點，點轉成邊這樣計算的複雜度還是挺大的，現階段是隻能處理小數據。

1.11 半監督圖分類

舉個半監督圖分類的例子。下圖中有一個圖，我們設定黑色圓圈的點已經知道分類了，其它的點並不知道它們的分類，那我們如何進行一個分類呢？在這個過程中，我們用了一個損失函數：

其中，是已分類的節點集合，是分類矩陣，是GCN輸出的結果。

有了半監督圖分類的損失函數後，我們來看一下如何用代碼實現。下圖展示了部分核心代碼。

我們在來看一下，實驗的結果。從下圖中，可以看到GCN把未分類的點分的很開。

1.12 圖卷積：科學家網絡

我們在看一個科學家網絡的例子。在科學家網絡中，我們每寫一篇論文都有題目，互相引用論文就會形成一個關係，任務是給你這些論文的題目，想預測一下論文的類別，比如這篇論文是屬於物理、化學還是數學。如下圖展示，只用到了兩層GCN，用GCN的方法比之前的結果有很大的提高。

2. 基於知識圖譜的圖卷積

2.1 知識圖譜

下圖展示了關於知識圖譜的三個例子。來看一下第一個例子，關於國家我們能想到中國、美國、日本等。中國有哪些屬性呢？中國的面積是平方公里，人口有億，中國的首都是北京等。就是我們在搜索一個關鍵詞的時候，它相應出來的一些東西就會形成知識圖譜。比如我搜索中國，可能出現美國、日本、英國等。在知識圖譜中，我們可以認爲圖中節點是國家、中國、北京這些是實體，邊就是實體間的關係，比如中國和國家有什麼關係，特徵就是實體的性質。

2.2 圖卷積：知識圖譜

我們現在的數據有：用戶，比如我們現在聽課的千多個人都是用戶；我們有一些實體，比如電影、書籍、音樂、食物等；還有用戶對哪些電影感興趣、喜歡看哪些書籍等，就是用戶與實體有聯繫，比如Microstrong對教父這個電影很感興趣，那麼；關係的話，就是每個實體之間會有一個關係，電影到教父會有一條邊；最後還有一個特徵矩陣。圖卷積的公式如下圖所示。

我們現在把實體的關係嵌入到圖中，那怎麼把實體推薦給用戶呢？我們針對每個用戶在新建一個圖，就是用戶對實體之間關係的重要性。就是把實體矩陣變成一個有權重的矩陣，然後每一個用戶有一個鄰接矩陣，然後針對每一個用戶的鄰接矩陣進行訓練。上圖中的圓圈三就是簡單基本的圖卷積過程。上圖中的圓圈四就是做了一個標籤順滑的過程。

標籤順滑現在在CNN中也是用的很多，爲了在訓練過程中提高模型的精度，做了一個標籤順滑。舉例，以前在訓練深度模型的時候，隨着訓練的不斷迭代，模型對訓練的結果更加自信，它認爲一個動物是貓、或者是狗，模型能很自信的確認這個動物是貓或是狗，它的預測值是實值或者。但是在訓練過程中由於模型過於自信，可能會導致更多的誤差，當我們把改成,改成，調整一下標籤順滑的值，最後模型預測的結果會更加的好。基本我們現在做的大部分深度神經模型，都會用到標籤順滑這樣的技術。

上圖第一個圓圈是：新建了一個知識圖譜。第二個圓圈是：用戶對每一個實體感興趣的東西，新建一個權重的矩陣。第三個圓圈是：對第二個圓圈的圖進行圖卷積。第四個圓圈是：在GCN中運用標籤順滑的技術。損失函數定義爲：

其中，是圖卷積的損失函數，是標籤順滑正則。

我們再來說一下，GCN的基本訓練過程。上圖中（a）表示，沒有考慮知識圖譜的結構，藍色的點是用戶感興趣的實體；粉色的點是用戶沒有觀察到，但是比較感興趣的點；灰色的點也是用戶沒有觀察到的點，但是是用戶不感興趣的點。現在我們的目的是通過訓練把粉色的點推薦給用戶，讓用戶進行選擇，灰色的點不推薦給用戶。（b）表示，經過第一層GCN的訓練把虛線上的兩個粉色點推薦出來了。（c）表示，經過第二層GCN的訓練把虛線上的三個粉色點推薦給用戶了。有誤差的情況下，把用戶不感興趣的灰色點也推薦給用戶了。（d）圖是針對其他用戶，上面講的（a）、（b）、（c）是對用戶來說，（d）是針對用戶，針對用戶模型訓練出來的結果並不適用。（e）表示，加了標籤順滑以後，模型推薦出的點更加精準。

2.3 標籤順滑

我們來了解一下標籤順滑正則的函數。標籤順滑一共有三步：能量方程、最小值、交叉熵。能量方程中，就是用戶對這個實體是否感興趣，感興趣這個值爲，不感興趣這個值爲。進行一個能量方程的處理，把相同的label給去掉，不同的label保留下來。然後取最小值，最後做一個交叉熵。交叉熵裏面用到了KL距離函數，它表示兩個概率分佈越相似，值越小。

2.4 知識圖譜：僞代碼

2.5 知識圖譜：結果演示

上圖展示了圖卷積在知識圖譜上應用在推薦方面的一個例子， 可以看到GCN相比其它推薦算法，還是有一定的結果上提升的。

上圖從準確度、速度和效果上展示了，GCN在知識圖譜上的顯著提高。

3. 研究方向

3.1 圖卷積：人體姿勢識別

人體的每一個關節點相當於圖中的節點，骨骼相當於圖的邊。人體就是一個很好的圖，聚類性也有，並且做每個動作，關節點的位置也是不一樣的，這就可以很好的構建一個聚類性的圖，然後進行訓練。

如下圖所示，輸入了一個視頻信號，視頻信號上有時間序列，每一個時間序列上就是一張圖片。針對每一張圖片，我們可以構建骨骼圖，然後通過時間順序找到每一個節點的位置把它們連接起來，然後就變成了一張大的圖，把這個大的圖放到GCN裏面進行訓練，最後到一個分類器裏面，預測分類結果。下圖的分類結果是跑步。

我們來看一下，GCN在人體姿勢識別上的結果。

3.2 圖卷積：超圖

超圖是圖的一個基本概念。如下圖所示，有八個點，把每個點選出來，可以有很多種的排列組合。我們選一個點，那總共有八個點可選擇，就有八種排列組合。我們選兩個點，比如、，那、會構成一個子圖。所以超圖就是在有個節點情況下，進行排列組合的問題。

3.3 圖構建

圖構建問題就是，給一大堆數據，我們不知道數據之間有沒有關係，我們怎麼新建這幅圖。新建完這幅圖後，把圖放到GCN裏面訓練，然後進行分類。

我們來看一個上圖中左下角所展示的例子，一共有五個分子的運動圖，分子之間是否有連續，分子之間位置和邊的聯繫也不清楚，我們需要新建一個圖，然後預測分子軌跡下一步動作。

上圖中右上角所展示的例子，人體的動作，在每一幀新建圖的過程中，圖是以哪個節點爲重心進行構建。比如，是以右手爲重心還是以左手爲重心。

3.4 子圖嵌入

圖裏面經常會考慮單個點，那我們把下圖中的三個點考慮成一個點，放到GCN裏面，結果會如何呢？這也是現在非常火的研究方向。

4. 場景應用

4.1 用戶推薦系統

淘寶、Google、Facebook等公司在搜索和推薦過程中都用到了GCN的技術。

4.2 輿情監控和控制

各個國家和各個機構都非常需要輿情監控和控制，判斷真消息和假消息，以及追蹤消息的來源。GCN在輿情監控和控制中也是一個非常好的技術。

4.3 自動駕駛

每一部車子都有車載系統，車載系統都需要聯網，這樣就構建了一個非常大的圖，也就可以應用GCN技術在圖裏進行推薦和用戶篩選。這也是未來在物聯網方面非常火的一個方向。

5. 總結

本文提到的所有知識點大部分來源於以下論文：

• Knowledge Graph Convolutional Networks for Recommender Systems；

• Knowledge Graph Convolutional Networks for Recommender Systems with Label Smoothness Regularization；

• Graph Convolutional Neural Networks for Web-Scale Recommender Systems；

• Modeling Relational Data with Graph Convolutional Networks；

• SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS；

• COMPOSITION-BASED MULTI-RELATIONAL GRAPH CONVOLUTIONAL NETWORKS；

• Neural Relational Inference for Interacting Systems；

• Graph Convolutional Networks for Text Classification；

最後，給大家補充一下關於機器學習、深度學習的一些頂會知識：

• 機器學習、深度學習偏理論的頂會：NIPS、ICML、ICLR。

• 計算機視覺方向的頂會：CVPR、ECCV、ICCV。

6. Reference

本文是Microstrong在觀看楊棟在B站上講解的直播課程《基於知識圖譜和圖卷積神經網絡的應用和開發》的筆記。直播地址：https://live.bilibili.com/11869202 。貪心科技官網已上線公開課回放，地址：https://www.greedyai.com/course/139 。

【1】概率圖模型（PGM）有必要系統地學習一下嗎？- 知乎 https://www.zhihu.com/question/23255632

【2】【Graph Embedding】DeepWalk：算法原理，實現和應用 - 淺夢的文章 - 知乎 https://zhuanlan.zhihu.com/p/56380812

【3】【NLP系列直播】 圖卷積神經網絡,BERT,知識圖譜,對話生成，貪心學院，地址：https://www.bilibili.com/video/BV1bK4y1t7Pw?p=1

【4】基於知識圖譜和圖卷積神經網絡的應用和開發，地址：https://www.bilibili.com/video/BV1ni4y1s7F6?from=search&seid=1051972300125641379

【5】貪心學院公開課-基於知識圖譜和圖卷積神經網絡的應用和開發-楊棟，地址：https://www.bilibili.com/video/BV1HK411s7zp?from=search&seid=3179677231592653459

【6】圖神經網絡在線研討會2020丨圖表示學習和圖神經網絡的最新理論進展和應用探索，地址：https://www.bilibili.com/video/bv1zp4y117bB/

【7】圖表示學習極簡教程 - 他們都叫我0號的文章 - 知乎 https://zhuanlan.zhihu.com/p/112295277

【8】圖卷積網絡(GCN)的譜分析 - 他們都叫我0號的文章 - 知乎 https://zhuanlan.zhihu.com/p/124727955

【9】淺析圖卷積神經網絡 - GEETEST極驗的文章 - 知乎 https://zhuanlan.zhihu.com/p/37091549 

推薦閱讀

文本自動摘要任務的“不完全”心得總結番外篇——submodular函數優化

Node2Vec 論文+代碼筆記

模型壓縮實踐收尾篇——模型蒸餾以及其他一些技巧實踐小結

中文命名實體識別工具（NER）哪家強？

學自然語言處理，其實更應該學好英語

斯坦福大學NLP組Python深度學習自然語言處理工具Stanza試用

太讚了！Springer面向公衆開放電子書籍，附65本數學、編程、機器學習、深度學習、數據挖掘、數據科學等書籍鏈接及打包下載

數學之美中盛讚的 Michael Collins 教授，他的NLP課程要不要收藏？

自動作詩機&藏頭詩生成器：五言、七言、絕句、律詩全了

模型壓縮實踐系列之——bert-of-theseus，一個非常親民的bert壓縮方法

這門斯坦福大學自然語言處理經典入門課，我放到B站了

關於AINLP

AINLP 是一個有趣有AI的自然語言處理社區，專注於 AI、NLP、機器學習、深度學習、推薦算法等相關技術的分享，主題包括文本摘要、智能問答、聊天機器人、機器翻譯、自動生成、知識圖譜、預訓練模型、推薦系統、計算廣告、招聘信息、求職經驗分享等，歡迎關注！加技術交流羣請添加AINLPer(id：ainlper)，備註工作/研究方向+加羣目的。

閱讀至此了，點個在看吧 :point_down: