從Laplacian矩陣開始，理解GCN

2019 年 11 月 21 日
筆記

文章作者：張寓弛內容來源：作者授權發布出品社區：DataFun 註：想和作者共事的同學，文末有內推資訊哦，歡迎投遞。

先說問題的本質：圖中的每個結點無時無刻不因為鄰居和更遠的點的影響而在改變著自己的狀態直到最終的平衡，關係越親近的鄰居影響越大。

要想理解GCN以及其後面一系列工作的實質，最重要的是理解其中的精髓Laplacian矩陣在幹什麼。知道了Laplacian矩陣在幹什麼後，剩下的只是解法的不同——所謂的Fourier變換隻是將問題從空域變換到頻域去解，所以也有直接在空域解的（例如GraphSage）。

為了讓問題簡單便於理解，先讓我們忘記時域、頻域這些複雜的概念，從一個最簡單的物理學現象——熱傳導出發。

圖（Graph）上的熱傳播模型

眾所周知，沒有外接干預的情況下，熱量從溫度高傳播到溫度低的地方並且不可逆，根據著名的牛頓冷卻定律（Newton Cool's Law），熱量傳遞的速度正比於溫度梯度，直觀上也就是某個地方A溫度高，另外一個B地方溫度低，這兩個地方接觸，那麼溫度高的地方的熱量會以正比於他們倆溫度差的速度從A流向B。

從一維空間開始

我們先建立一個一維的溫度傳播的模型，假設有一個均勻的鐵棒，不同位置溫度不一樣，現在我們刻畫這個鐵棒上面溫度的熱傳播隨著時間變化的關係。預先說明一下，一個連續的鐵棒的熱傳播模型需要列溫度對時間和坐標的偏微分方程來解決，我們不想把問題搞這麼複雜，我們把空間離散化，假設鐵棒是一個一維鏈條，鏈條上每一個單元擁有一致的溫度，溫度在相鄰的不同的單元之間傳播，如下圖：

圖1.一維離散鏈條上的熱傳播

對於第

個單元，它只和

與

兩個單元相鄰，接受它們傳來的熱量（或者向它們傳遞熱量，只是正負號的差異而已），假設它當前的溫度為

，那麼就有：

和單元的比熱容、品質有關是個常數。右邊第一項是下一個單元向本單元的熱量流入導致溫度升高，第二項是本單元向上一個單元的熱量流出導致溫度降低。做一點微小的數學變換可以得到：

注意觀察第二項，它是兩個差分的差分，在離散空間中，相鄰位置的差分推廣到連續空間就是導數，那麼差分的差分，就是二階導數！

所以，我們可以反推出鐵棒這樣的連續一維空間的熱傳導方程就是：

同理，在高維的歐氏空間中，一階導數就推廣到梯度，二階導數就是我們今天討論的主角——拉普拉斯運算元：

其中

這個符號代表的是對各個坐標二階導數的加和，現在的主流寫法也可以寫作

。

綜上所述，我們發現這樣幾個事實：

1、在歐氏空間中，某個點溫度升高的速度正比於該點周圍的溫度分布，用拉普拉斯運算元衡量。

2、拉普拉斯運算元，是二階導數對高維空間的推廣。

那麼，你肯定會問：你扯這麼多有什麼用呢？我還是看不到拉普拉斯運算元和拉普拉斯矩陣還有GCN有半毛錢關係啊？

不要急，目前只是第一步，讓我們把這個熱傳導模型推廣導拓撲空間，你就會發現它們其實刻畫的是同一回事了！

圖(Graph)上熱傳播模型的推廣

現在，我們依然考慮熱傳導模型，只是這個事情不發生在歐氏空間了，發生在一個Graph上面。這個圖上的每個結點（Node）是一個單元，且這個單元只和與這個結點相連的單元，也就是有邊（Edge）連接的單元發生熱交換。例如下圖中，結點1隻和結點0、2、4發生熱交換，更遠的例如結點5的熱量要通過4間接的傳播過來而沒有直接熱交換。

圖2. 圖上的熱傳播

我們假設熱量流動的速度依然滿足牛頓冷卻定律，研究任一結點

，它的溫度隨著時間的變化可以用下式來刻畫：

其中

是這個圖的鄰接矩陣（Adjacency Matrix），定義非常直觀：對於這個矩陣中的每一個元素

，如果結點

和

相鄰，那麼

，否則

。在這裡，我們只討論簡單情況：

1、這張圖是無向圖，

和

相鄰那麼

和

也相鄰，所以

，這是個對稱陣。

2、結點自己到自己沒有迴環邊，也就是

對角線上元素都是

。

所以不難理解上面這個公式恰好表示了只有相鄰的邊才能和本結點發生熱交換且熱量輸入（輸出）正比於溫度差。

我們不妨用乘法分配律稍微對上式做一個推導：

先看右邊括弧裡面第一項，

代表對這個頂點求度（degree），一個頂點的度被定義為這個頂點有多少條邊連接出去，很顯然，根據鄰接矩陣的定義，第一項的求和正是在計算頂點

的度。

再看右邊括弧裡面的第二項，這可以認為是鄰接矩陣的第

行對所有頂點的溫度組成的向量做了個內積。

為什麼要作上述變化呢，我們只看一個點的溫度不太好看出來，我們把所有點的溫度寫成向量形式再描述上述關係就一目了然了。首先可以寫成這樣：

然後我們定義向量

，那麼就有：

其中

稱為度矩陣，只有對角線上有值，且這個值表示對應的頂點度的大小。整理整理，我們得到：

回顧剛才在連續歐氏空間的那個微分方程：

二者具有一樣的形式！我們來對比一下二者之間的關係：

相同點：刻畫空間溫度分布隨時間的變化，且這個變化滿足一個相同形式的微分方程。
不同點：前者刻畫拓撲空間有限結點，用向量

刻畫當前狀態，單位時間狀態的變化正比於線性變換

運算元作用在狀態

上。後者刻畫歐氏空間的連續分布，用函數

來刻畫當前狀態，單位時間狀態變化正比於拉普拉斯運算元

作用在狀態

上。

不難發現，這就是同一種變換、同一種關係在不同空間上面的體現，實質上是一回事！

於是我們自然而然，可以把連續空間中的熱傳導，推廣到圖（Graph）上面去，我們把圖上面和歐氏空間地位相同變換，以矩陣形式體現的

叫做拉普拉斯（Laplacian）矩陣。看，這正是原始形式的拉普拉斯矩陣

需要多嘴一句的是，本文開頭所說的離散鏈條上的熱傳導，如果你把鏈條看成一個圖，結點從左到右編號1，2，3…的話，也可以用圖的熱傳導方程刻畫，此時

除了頭尾兩個結點是1其他值都是2，

的主對角線上下兩條線上值是1，其他地方是0。

推廣到GCN

現在問題已經很明朗了，只要你給定了一個空間，給定了空間中存在一種東西可以在這個空間上流動，兩鄰點之間流動的強度正比於它們之間的狀態差異，那麼何止是熱量可以在這個空間流動，任何東西都可以！

自然而然，假設在圖中各個結點流動的東西不是熱量，而是特徵（Feature），而是消息（Message），那麼問題自然而然就被推廣到了GCN。所以GCN的實質是什麼，是在一張Graph Network中特徵（Feature）和消息（Message）中的流動和傳播！這個傳播最原始的形態就是狀態的變化正比於相應空間（這裡是Graph空間）拉普拉斯運算元作用在當前的狀態。

抓住了這個實質，剩下的問題就是怎麼去更加好的建模和解決這個問題。

建模方面就衍生出了各種不同的演算法，你可以在這個問題上面複雜化這個模型，不一定要遵從牛頓冷卻定律，你可以引入核函數、引入神經網路等方法把模型建得更非線性更能刻畫複雜關係。

解決方面，因為很多問題在頻域解決更加好算，你可以通過Fourier變換把空域問題轉化為頻域問題，解完了再變換回來，於是便有了所有Fourier變換中的那些故事。

扯了這麼多，總結一下，問題的本質就是：

我們有張圖，圖上每個結點刻畫一個實體，物理學場景下這個實體是某個有溫度的單元，它的狀態是溫度，廣告和推薦的場景下這個實體是一個user，一個item，一個ad，它的狀態是一個embedding的向量。
相鄰的結點具有比不相鄰結點更密切的關係，物理學場景下，這個關係是空間上的臨近、接觸，廣告和推薦場景下這個是一種邏輯上的關係，例如用戶購買、點擊item，item掛載ad。
結點可以傳播熱量/消息到鄰居，使得相鄰的結點在溫度/特徵上面更接近。

本質上，這是一種Message Passing，是一種Induction，卷積、傅立葉都是表象和解法。

最後再補充說明幾點事實：

熱/消息傳導方程的數值可迭代求解性（機器學習上的可操作性）

我們可以把原方程寫成這樣：

機器學習中，時間是離散的，也就是左邊對時間的求導變成了離散的一步步迭代。好在這個方程天生似乎就是上帝為了我們能夠迭代求解而設計的。右邊用拉普拉斯運算元作用一次到全局的狀態上，就能把狀態更新一步！

實際解決的過程中，可以發揮機器學習搬磚工懂得舉一反三的優良精神，首先，不一定要全局操作，我們可以batchify操作一部分結點，大家輪著來，其次，我們可以只考察這個點的一階和二階鄰居對當前點作Message Passing，這個思想就是對拉普拉斯運算元作特徵分解，然後只取低階的向量，因為矩陣的譜上面能量一般具有長尾效應，頭幾個特徵值dominate幾乎所有能量。

Laplacian運算元的另一個性質

Laplacian矩陣/運算元不僅表現的是一種二階導數的運算，另一方面，它表現了一種加和性，這個從圖上熱/消息傳播方程最原始的形態就能一目了然：

可見，每個結點每個時刻的狀態變化，就是所有鄰居對本結點差異的總和，也就是所有的鄰居把message pass過來，然後再Aggregate一下，這正是GraphSage等空域演算法的關鍵步驟Aggregate思想的濫觴。

在實際建模中，我們的Aggregate不一定是加和，作為一個熟練的機器學習搬磚工，我們懂得可以把Aggregate推廣成各種操作例如Sum Pooling，例如LSTM，例如Attention，以求刷效果，發paper 🙂

兩種空間下的Fourier分解/ 特徵分解對比（卷積為什麼能從歐氏空間推廣到Graph空間）

最後，因為有以上分析作基礎，我們可以解釋一下傅立葉變換是怎麼推廣到圖空間的。

首先，在歐氏空間上，迭代求解的核心運算元

運算元的特徵函數是：

，因為：

其次，在圖空間上，對應地位的

對應的不是特徵函數，而是它的特徵值和特徵向量，分別對應上面的

和

。

唯一的區別是，

是定義內積為函數積分的空間上的一組基，有無窮多個，當然這無窮多個是完備的。而

的特徵空間是有限維的，因為

的對稱性和半正定性，所有特徵值都是實數且特徵向量都是實向量，特徵空間維度等於圖中的結點數也就是

的階。

注意，實對稱矩陣的特徵空間的所有基能夠張出整個線性空間且它們兩兩正交，所以無論是拉普拉斯運算元

還是拉普拉斯矩陣

，它們的特徵空間是一個滿秩且基兩兩正交的空間，所以把歐氏空間的

推廣到圖空間的

的這一組特徵向量。正是同一個關係（Message Passing），同一種變換，在不同空間下的體現罷了！

拉普拉斯矩陣還有另外兩個變種，本質上就是用度對周圍鄰居的影響做了不同的歸一化策略，具體可參考wikipedia：

https://en.wikipedia.org/wiki/Laplacian_matrix

故事還沒有結束，讓我們來探討點更有意思的事情～

宇宙熱寂說、恆溫熱源和半監督學習

感謝你饒有興緻能夠繼續聽我絮叨完。乍看這個標題，你一定認為我在扯淡，前面兩個概念和後面一個八竿子打不著。不用著急，且聽我慢慢道來，as the saying goes：因果有差距，聯想來搭橋～

如果你仔細的思考，你會本文常掛在嘴邊的熱力學傳導模型有個宿命論的結論：假設這個圖是個連通圖，每個結點到任一其他結點都有路可走，那麼這樣的事情肯定會發生：如果一個結點溫度高於周圍鄰居，那麼它的熱量會持續流出到鄰居，此間它自己的熱量流失，溫度就會降低，直到它和周圍鄰居一樣，最終所有結點都達到一個平衡的、一樣的溫度。

我想說的是，你的猜想非常正確而且能夠經過嚴格的數學證明，只要解上面這個方程（並不難）就能驗證你的結論。

問題的本質在於，我們之前所討論的熱傳導場景是一個孤立系統的無源場景，每一個結點的熱量都有一個初始稟賦，沒有外界干預它、給它熱量，它每傳給周圍一些熱量，自己就要減少，伴隨自身溫度的降低。那麼根據能量守恆定律，整個系統的能量是定值，並且隨著熱傳導，系統的熱量被均勻分配到每個參與其中的結點。這正是熱力學第一定律和熱力學第二定律在這張圖上的完美體現。這也是這張圖上的「宇宙熱寂說」，這個孤立的小宇宙，最終處處溫度一樣，平衡狀態下沒有熱量的流動。

Wikipedia[1]對無源系統有個動態圖模擬，能夠增加直觀認識，盜圖放在這裡：

無源系統最終出現「宇宙熱寂」現象，所有點平衡態溫度趨同，圖片來自wikipedia [1]

如果我們在這張圖上引入一個東西叫做恆溫熱源，事情就會發生改變。所謂恆溫熱源，就是這樣一個存在，系統中有些點開了外掛，它們接著系統外面的某些「供熱中心」，使得它們溫度能夠保持不變。這樣，這些結點能夠源源不斷的去從比它溫度高的鄰居接受熱量，向溫度比它低的鄰居釋放熱量，每當有熱量的增補和損失，「供熱中心」便抽走或者補足多餘或者損失的熱量，使得這個結點溫度不發生變化。

那麼最終的平衡的結果不是無源情況下所有結點溫度不一樣，而是整個圖中，高溫熱源不斷供熱給周圍的鄰居，熱量傳向遠方，低溫熱源不斷持續吸收鄰居和遠方的熱量，最終狀態下每條邊熱量穩恆流動（不一定為0），流量不再變化，每個結點都達到終態的某個固有溫度。這個溫度具體是多少，取決於整張圖上面恆溫熱源的溫度和它們的分布。

恆溫熱源的存在，正是我們跨向半監督學習的橋樑。

我們把問題向廣告和推薦場景去類比，在這個場景下，某些結點有著明確的label，例如某個廣告被點擊，某個廣告的ctr是多少，某個item被收藏，這些帶著label的結點有著相對的確定性——它們可以被看作是這個結點的溫度，這些有標籤的結點正是恆溫熱源。那麼，這些圖的其他參與者，那些等待被我們預測的結點正是這張圖的無源部分，它們被動的接受著那些或近或遠的恆溫熱源傳遞來的Feature，改變著自己的Feature，從而影響自己的label。

讓我們做個類比：

溫度好比 label 是狀態量
恆溫熱源好比有明確 label的結點，它們把自己的Feature傳遞給鄰居，讓鄰居的Feature與自己趨同從而讓鄰居有和自己相似的label
結點的熱能就是Feature，無標籤的、被預測的結點的Feature被有明確label的結點的Feature傳遞並且影響最終改變自己

需要說明的一點是，無論是有源還是無源，當有新的結點接入已經平衡的系統，系統的平衡被打破，新的結點最終接受已有結點和恆溫熱源的傳遞直到達到新的平衡。所以我們可以不斷的用現有的圖去預測我們未見過的結點的性質，演化和滾大這個系統。

如果關注有源情況下的熱傳導方程定量分析，可以看wikipedia這一條：

這裡不是我們的重點，就不再贅述了。最後，我們討論一下優化的過程，以期待發現什麼。

Heat equation – Wikipedia關於優化過程和優化結果的討論

https://en.wikipedia.org/wiki/Heat_equation

從物理和從機器學習角度去看拉普拉斯熱傳導微分方程註定是不一樣的。

從物理學角度去研究它，更多的是在搞明白邊界條件和初始條件的情況下，探索和了解後續狀態的演化過程。

而機器學習更多關心的是結果，畢竟我們要的是最終的參數和特徵，用來使用和預測結果。然而，關注一些過程方面的東西，能夠幫助我們更加深入的建立起原始熱傳導和前沿的GNN演算法的聯繫。

我們並不靠解這個微分方程得到狀態和時間的顯式關係來獲得對過程的認知，這個對我們當下討論的話題意義不大，想了解怎麼解可以看[1]，做法大概就是以所有特徵向量為基展開狀態向量，然後就能像解決簡單常微分方程的辦法積個分解出來，是一個exponential的形式。我們用另外一個方式來認知這個過程。

為求簡單，我們研究上文所說的原始的無源熱傳導方程：

為了好解，我們把時間也離散化，微分變差分近似是這樣：

所以自然：

這實質上是一個機器學習，或者優化問題中常見的樣子：

只是狀態的變化量從梯度運算元（可能還有動量、歷史狀態、Hessian矩陣、正則化操作等等，這裡不贅述）作用於loss function變成了拉普拉斯運算元作用於當前狀態。

我們這回先不整體的考察狀態向量

的演化，倒退到早些時候所說的每個結點

的狀態

的變化，有：

到這裡已經很明了了，每個結點的下一個狀態，是當前狀態的常數倍（第一項），和所有鄰居的加和（第二項）的融合。

我們來看看GraphSage核心演算法的過程，會發現原理上二者的驚人相似性：

GraphSage演算法[3]，截自原論文

看最裡面的循環節，就是迭代過程，核心兩步：

1、Aggregate鄰居結點的狀態，作為鄰居結點的一個「和」狀態。

2、將這個「和」狀態和當前結點的狀態通過Concat操作和帶非線性激活的全連接層融合到一起更新當前結點的狀態。

原文中的配圖很好的解釋了這個過程：

GraphSage演算法[3]取樣和Aggregate過程

GraphSage這個過程和原始的熱傳導過程是這麼的相似，我們可以發現：

1、原始的熱傳導用所有直接相鄰的鄰居的簡單加和作為鄰居「和」狀態，GraphSage用一個Aggregator作用於所有取樣鄰居（可以是二階）得到「和」狀態。本質是Aggregate，只是後者更加非線性，建模能力更強。

2、原始的熱傳導把鄰居「和」狀態和當前結點狀態簡單加權疊加作為融合態，GraphSage使用Concat操作加上神經網路非線性融合一把。本質是把鄰居的「和」和本地的現有狀態糅合得到本地新狀態，依然只是後者更加非線性，建模能力更強。

3、原始熱傳導使用所有一階鄰居。GraphSage會取樣鄰居，因為實際上鄰居可能很多全部算很慢，同時它還會取樣高階鄰居。本質是主動融合幾何上相近的單元。這裡可能存在一個隱患，在高度非線性下，對周圍鄰居的取樣的Aggregate是不是對周圍所有鄰居的Aggregate的無偏估計，本人知識有限，有待進一步考證。

所有的所有，還是「相鄰」、「疊加」與「融合」三個關鍵詞，只是解法更新、迭代、升級了。

理解了Laplacian變換和圖上的熱傳播的關係，搞明白了Message Passing和有源無源狀態下的均衡狀態，再去看浩如煙海的paper和高票答案，相信你一定會有更深刻的理解！祝你好運～

原文鏈接：

https://www.zhihu.com/question/54504471/answer/630639025

參考文獻

[1] Laplacian matrix

https://en.wikipedia.org/wiki/Laplacian_matrix

[2] Cannon J R. The one-dimensional heat equation[M]. Cambridge University Press, 1984.

[3] Hamilton W, Ying Z, Leskovec J. Inductive representation learning on large graphs[C]//Advances in Neural Information Processing Systems. 2017: 1024-1034.

[4] Heat equation – Wikipedia

https://en.wikipedia.org/wiki/Heat_equation