先說問題的本質：圖中的每個結點無時無刻不因為鄰居和更遠的點的影響而在改變著自己的狀態直到最終的平衡，關系越親近的鄰居影響越大，
要想理解GCN以及其后面一系列作業的實質，最重要的是理解其中的精髓Laplacian矩陣在干什么，知道了Laplacian矩陣在干什么后，剩下的只是解法的不同——所謂的Fourier變換只是將問題從空域變換到頻域去解，所以也有直接在空域解的（例如GraphSage），為了讓問題簡單便于理解，先讓我們忘記時域、頻域這些復雜的概念，從一個最簡單的物理學現象——熱傳匯出發，
圖（Graph）上的熱傳播模型
眾所周知，沒有外接干預的情況下，熱量從溫度高傳播到溫度低的地方并且不可逆，根據著名的牛頓冷卻定律（Newton Cool's Law），熱量傳遞的速度正比于溫度梯度，直觀上也就是某個地方A溫度高，另外一個B地方溫度低，這兩個地方接觸，那么溫度高的地方的熱量會以正比于他們倆溫度差的速度從A流向B，
從一維空間開始
我們先建立一個一維的溫度傳播的模型，假設有一個均勻的鐵棒，不同位置溫度不一樣，現在我們刻畫這個鐵棒上面溫度的熱傳播隨著時間變化的關系，預先說明一下，一個連續的鐵棒的熱傳播模型需要列溫度對時間和坐標的偏微分方程來解決，我們不想把問題搞這么復雜，我們把空間離散化，假設鐵棒是一個一維鏈條，鏈條上每一個單元擁有一致的溫度，溫度在相鄰的不同的單元之間傳播，如下圖：
對于第i 個單元，它只和 i-1 與 i+1 兩個單元相鄰，接受它們傳來的熱量（或者向它們傳遞熱量，只是正負號的差異而已），假設它當前的溫度為Φi，那么就有：
k和單元的比熱容、質量有關是個常數，右邊第一項是下一個單元向本單元的熱量流入導致溫度升高，第二項是本單元向上一個單元的熱量流出導致溫度降低，做一點微小的數學變換可以得到：
注意觀察第二項，它是兩個差分的差分，在離散空間中，相鄰位置的差分推廣到連續空間就是導數，那么差分的差分，就是二階導數！
所以，我們可以反推出鐵棒這樣的連續一維空間的熱傳導方程就是：
同理，在高維的歐氏空間中，一階導數就推廣到梯度，二階導數就是我們今天討論的主角——拉普拉斯算子
其中 Δ 這個符號代表的是對各個坐標二階導數的加和，現在的主流寫法也可以寫作 Δ2 ，綜上所述，我們發現這樣幾個事實：1、在歐氏空間中，某個點溫度升高的速度正比于該點周圍的溫度分布，用拉普拉斯算子衡量，2、拉普拉斯算子，是二階導數對高維空間的推廣，那么，你肯定會問：你扯這么多有什么用呢？我還是看不到拉普拉斯算子和拉普拉斯矩陣還有GCN有半毛錢關系啊？不要急，目前只是第一步，讓我們把這個熱傳導模型推廣導拓撲空間，你就會發現它們其實刻畫的是同一回事了！
圖(Graph)上熱傳播模型的推廣
現在，我們依然考慮熱傳導模型，只是這個事情不發生在歐氏空間了，發生在一個Graph上面，這個圖上的每個結點（Node）是一個單元，且這個單元只和與這個結點相連的單元，也就是有邊（Edge）連接的單元發生熱交換，例如下圖中，結點1只和結點0、2、4發生熱交換，更遠的例如結點5的熱量要通過4間接的傳播過來而沒有直接熱交換，
我們假設熱量流動的速度依然滿足牛頓冷卻定律，研究任一結點，它的溫度隨著時間的變化可以用下式來刻畫：
其中 A 是這個圖的鄰接矩陣（Adjacency Matrix），定義非常直觀： 對于這個矩陣中的每一個元素 Aij ，如果結點 i 和 j 相鄰，那么Aij =1 ，否則 Aij =0 ，在這里，我們只討論簡單情況：
1、這張圖是無向圖，i 和 j 相鄰那么 j 和 i 也相鄰，所以 Aij = Aji 這是個對稱陣，
2、結點自己到自己沒有回環邊，也就是 A 對角線上元素都是 0 ，
所以不難理解上面這個公式恰好表示了只有相鄰的邊才能和本結點發生熱交換且熱量輸入（輸出）正比于溫度差，我們不妨用乘法分配律稍微對上式做一個推導：
先看右邊括號里面第一項， deg( ) 代表對這個頂點求度（degree），一個頂點的度被定義為這個頂點有多少條邊連接出去，很顯然，根據鄰接矩陣的定義，第一項的求和正是在計算頂點 i 的度，
再看右邊括號里面的第二項，這可以認為是鄰接矩陣的第i 行對所有頂點的溫度組成的向量做了個內積，
為什么要作上述變化呢，我們只看一個點的溫度不太好看出來，我們把所有點的溫度寫成向量形式再描述上述關系就一目了然了，首先可以寫成這樣：
然后我們定義向量:
那么就有：
D被稱為度矩陣，只有對角線上有值，且這個值表示對應的頂點度的大小，整理整理，我們得到：
回顧剛才在連續歐氏空間的那個微分方程：
二者具有一樣的形式！我們來對比一下二者之間的關系：
- 相同點：刻畫空間溫度分布隨時間的變化，且這個變化滿足一個相同形式的微分方程，
- 不同點：前者刻畫拓撲空間有限結點，用向量 Φ 來刻畫當前狀態，單位時間狀態的變化正比于線性變換 -L 算子作用在狀態 Φ 上，后者刻畫歐氏空間的連續分布，用函式 Φ(x, t) 來刻畫當前狀態，單位時間狀態變化正比于拉普拉斯算子 Δ 作用在狀態 Φ上，
不難發現，這就是同一種變換、同一種關系在不同空間上面的體現，實質上是一回事！
于是我們自然而然，可以把連續空間中的熱傳導，推廣到圖（Graph）上面去，我們把圖上面和歐氏空間地位相同變換，以矩陣形式體現的 L 叫做拉普拉斯（Laplacian）矩陣，看，這正是 @superbrother 答案中所述的原始形式的拉普拉斯矩陣 L=D-A ，
需要多嘴一句的是，本文開頭所說的離散鏈條上的熱傳導，如果你把鏈條看成一個圖，結點從左到右編號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空間）
最后，因為有以上分析作基礎，我們可以解釋一下傅立葉變換是怎么推廣到圖空間的，
https://en.wikipedia.org/wiki/Laplacian_matrix
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/18180.html
標籤：其他
下一篇：全球失明的主要原因之一是什么？