圖卷積神經(jīng)網(wǎng)絡(luò)的數(shù)學(xué)原理詳解——筆記（更新中）

原講解視頻地址鬼譬，本篇是對(duì)該視頻的筆記细层。感謝視頻UP的講解墩划，受益頗多蜂桶！

如果我們只知道一個(gè)模型是怎么做的寝姿，卻不知道它為何這樣做交排，對(duì)于我們做科研的人來(lái)說(shuō)是遠(yuǎn)遠(yuǎn)不夠的。我們必須知其然并且知其所以然饵筑，才能夠在現(xiàn)有的模型基礎(chǔ)上提出自己的想法和改進(jìn)埃篓。

目錄?1.GCN基礎(chǔ) 2.譜圖理論 3.傅里葉變換 4.GCN

1.GCN基礎(chǔ)

1.1 同樣都是“圖”，Graph與Image有什么聯(lián)系與區(qū)別呢根资？

Image是Graph在歐式空間中的一種特例架专。Graph是相較于Image來(lái)說(shuō)更加廣義的一種拓?fù)浣Y(jié)構(gòu)。Graph由點(diǎn)和邊組成它可以表示任意的事物與事物之間的關(guān)系玄帕。而Image是表示在歐式空間中的事物與事物之間的關(guān)系部脚。我們可以根據(jù)Image來(lái)構(gòu)建對(duì)應(yīng)的Graph，將每一個(gè)像素作為節(jié)點(diǎn)桨仿，像素之間的關(guān)系作為邊睛低。

圖一兩種不同的Image—>Graph表示方法

現(xiàn)實(shí)生活中能夠建圖的場(chǎng)景非常之多，社交關(guān)系服傍，詞匯搜索等等钱雷。

1.2 什么是圖神經(jīng)網(wǎng)絡(luò)？

圖神經(jīng)網(wǎng)絡(luò)就是專(zhuān)門(mén)用來(lái)處理圖數(shù)據(jù)的神經(jīng)網(wǎng)絡(luò)架構(gòu)吹零。具體來(lái)說(shuō)罩抗，會(huì)給定圖的每個(gè)鄰接矩陣和節(jié)點(diǎn)特征，通過(guò)將這兩個(gè)輸入進(jìn)行某種圖上的映射灿椅。從而得到每個(gè)節(jié)點(diǎn)下一層的特征套蒂。

圖神經(jīng)網(wǎng)絡(luò)的聚合模式：

$GNN: H^{(l+1)} = f(A,H^l)$

合理性：比如社交網(wǎng)絡(luò)中我們想要獲得某一個(gè)用戶的特征钞支，可以搜集與他相近的人的特征，他們會(huì)具有一定的相關(guān)性操刀。（近朱者赤烁挟，近墨者黑）

許多GNN相關(guān)的模型其實(shí)都是在設(shè)計(jì)函數(shù)“f”

1.3 GCN模型？

這里我們只討論簡(jiǎn)單無(wú)向圖（圖無(wú)自環(huán)骨坑、無(wú)重邊撼嗓，邊無(wú)方向）

$GCN:H^{l+1}=\sigma (\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}H^l\theta )$

公式中的 $\hat{A}$ 是鄰接矩陣+單位矩陣，相當(dāng)于給每一個(gè)節(jié)點(diǎn)添加一個(gè)自環(huán)欢唾。 $\hat{D}$ 是對(duì)角陣+單位陣且警。表示添加自環(huán)后每一個(gè)節(jié)點(diǎn)的度值。 $D$ 代表了每一個(gè)節(jié)點(diǎn)的度的值礁遣。對(duì)于對(duì)角陣求冪斑芜，只要對(duì)對(duì)角線上的每一個(gè)元素求冪即可。

例：

$\begin {bmatrix}4&0&0\\0&1&0\\0&0&1\end{bmatrix}^{-\frac{1}{2}}=\begin {bmatrix}4^{-\frac{1}{2}}&0&0\\0&1^{-\frac{1}{2}}&0\\0&0&1^{-\frac{1}{2}}\end{bmatrix} =\begin {bmatrix}\frac{1}{2}&0&0\\0&1&0\\0&0&1\end{bmatrix}$

$\theta$ 是可訓(xùn)練的參數(shù)祟霍，是對(duì)輸入的feature進(jìn)行線性變換杏头。 $\sigma$ 是非線性的激活函數(shù)。

簡(jiǎn)單理解GCN在做什么：對(duì)圖的鄰接矩陣加了一個(gè)自環(huán)沸呐，做了對(duì)稱(chēng)歸一化大州。然后用得到的結(jié)果對(duì)輸入的特征進(jìn)行聚合。每個(gè)節(jié)點(diǎn)都聚合到了自己和周邊節(jié)點(diǎn)加權(quán)求和的feature信息垂谢。

2. 譜圖理論

2.1 什么是譜圖理論？

研究與圖的鄰接矩陣相關(guān)的一些性質(zhì)的領(lǐng)域疮茄。將線性代數(shù)研究矩陣性質(zhì)限定在了研究圖的鄰接矩陣的范圍內(nèi)滥朱。譜圖理論是線性代數(shù)的子領(lǐng)域。

2.2 回顧：線性代數(shù)相關(guān)知識(shí)

（1）特征值與特征向量

對(duì)于一個(gè)矩陣 $A$ 力试，如果有 $A\overrightarrow{x}=\lambda \overrightarrow{x}$ 其中 $\lambda$ 為標(biāo)量徙邻、 $|\overrightarrow{x}|\neq0$ 。就稱(chēng) $\overrightarrow{x}$ 是 $A$ 的特征向量畸裳， $\lambda$ 是A的特征值缰犁。

（2）定理

如果一個(gè)矩陣是一個(gè)實(shí)對(duì)稱(chēng)陣，那么它一定有N個(gè)特征值怖糊，對(duì)應(yīng)著N個(gè)互相正交的特征向量帅容。

$A=U\Lambda U^T$ ，其中 $UU^T=I$ 伍伤， $\lambda$ 除了對(duì)角線上以外其他元素都是0并徘。對(duì)角線上的元素都是一個(gè)特征值。

（3）半正定矩陣

半正定矩陣就是所有的特征值都大于等于0扰魂。

（4）二次型

給定一個(gè)矩陣A麦乞，左乘x轉(zhuǎn)置蕴茴，右乘x。 $\overrightarrow{x}^TA\overrightarrow{x}$ 就稱(chēng)為向量x對(duì)矩陣A的二次型姐直。

（5）瑞利熵

瑞利熵就是一個(gè)向量關(guān)于矩陣A的二次型與這個(gè)向量關(guān)于單位矩陣的二次型的比值 $\frac{\overrightarrow{x}^TA\overrightarrow{x}}{\overrightarrow{x}^T\overrightarrow{x}}$ 倦淀。

為什么需要研究瑞利熵：因?yàn)槠渑c矩陣的特征值有著密切的聯(lián)系。如我們假定 $\overrightarrow{x}$ 是矩陣A的一個(gè)特征向量声畏，那么瑞利熵就是矩陣對(duì)應(yīng)的特征值撞叽。

證明如下：

$\frac{\overrightarrow{x}^TA\overrightarrow{x}}{\overrightarrow{x}^T\overrightarrow{x}}=\frac{\overrightarrow{x}^T(\lambda\overrightarrow{x})}{\overrightarrow{x}^T\overrightarrow{x}} =\frac{\lambda(\overrightarrow{x}^T\overrightarrow{x})}{\overrightarrow{x}^T\overrightarrow{x}} = \lambda$

因此瑞利熵是我們研究特征值的重要手段。

2.3 譜圖理論基礎(chǔ)

（1） $L$ 與 $L_{sym}$ （重要）

$L$ 是圖的拉普拉斯矩陣砰识， $L=D-A$ 能扒。

$L_{sym}$ 是拉普拉斯矩陣的對(duì)稱(chēng)規(guī)范化， $L_{sym}=D^{-\frac{1}{2}}LD^{-\frac{1}{2}}$ 辫狼。

$L$ 與 $L_{sym}$ 都是實(shí)對(duì)稱(chēng)陣初斑。因此他們都有N個(gè)特征值和N個(gè)互相正交的特征向量∨虼Γ可以分解為上述的 $U\Lambda U^T$ 的形式见秤。且這兩個(gè)矩陣都是半正定的，其特征值都是大于等于0的真椿。

證明：（通過(guò)瑞利熵）

如果我們能夠證明對(duì)于任何的一個(gè)向量都有 $\frac{\overrightarrow{x}^TL\overrightarrow{x}}{\overrightarrow{x}^T\overrightarrow{x}}\geq 0$ 鹃答，那么當(dāng) $\overrightarrow{x}$ 是特征向量，也即當(dāng)L是特征值是也成立突硝。

首先测摔，分母部分肯定是恒大于等于0的，因?yàn)樗窍蛄縳的模長(zhǎng)的形式解恰。所以我們只需要證明分子恒大于0即可锋八。

我們定義 $G_{(i,j)}$ ，它只有在第i行的第i列和第j行的第j列才為1护盈，在第i行的第j列與第j行的第i列都是-1挟纱，其他位置都是0。

為什么構(gòu)造 $G_{(i,j)}$ 腐宋，因?yàn)樗亩涡头浅Ｓ刑攸c(diǎn)紊服，對(duì)于向量x，關(guān)于 $G_{(i,j)}$ 的二次型為：

$\overrightarrow{x}^TG_{(i,j)}\overrightarrow{x} = \overrightarrow{x}^T \begin {bmatrix}0\\\vdots\\x_i-x_j\\ \vdots\\x_j-x_i\\\vdots\\0\end{bmatrix} =x_i(x_i-x_j) + x_j(x_j-x_i) = (x_i-x_j)^2$

所以 $G_{(i,j)}$ 非常有特點(diǎn)胸竞，它的二次型就相當(dāng)于對(duì)x的第i個(gè)點(diǎn)和第j個(gè)點(diǎn)的坐標(biāo)位置做差求平方欺嗤。

拉普拉斯矩陣 $L=D-A=\sum_{(i,j)\in E}G_{(i,j)}$ ,因此L的二次型為：

$\overrightarrow{x}^T L\overrightarrow{x}=\overrightarrow{x}^T(\sum G_{(i,j)})\overrightarrow{x}=\sum\overrightarrow{x}^TG_{(i,j)}\overrightarrow{x}=\sum(x_i-x_j)^2\geq 0$

$\overrightarrow{x}^T L_{sym}\overrightarrow{x}= \overrightarrow{x}^T D^{-\frac{1}{2}}LD^{-\frac{1}{2}}\overrightarrow{x}=(\overrightarrow{x}^T D^{-\frac{1}{2}})L(D^{-\frac{1}{2}}\overrightarrow{x}) = \sum(\frac{x_i}{\sqrt {d_i}}-\frac{x_j}{\sqrt {d_j}})^2 \geq0$

也就是將上式中的 $x_i$ 與 $x_j$ 換成了規(guī)范化后的 $x_i$ 與 $x_j$ 。

一個(gè)更加強(qiáng)的性質(zhì)： $L_{sym}$ 不僅 $\geq0$ 而且 $\in [0,2]$ 卫枝。

證明：（與上述證明類(lèi)似）

我們定義 $G_{(i,j)}^{pos}$ 剂府，它在第i行的第i列和第j行的第j列，第i行的第j列和第j行的第i列都為1剃盾，其他位置為0腺占。

可得 $G_{(i,j)}^{pos}$ 的二次型： $\overrightarrow{x}^TG_{(i,j)}^{pos}\overrightarrow{x} = (x_i+x_j)^2$ 淤袜。

定義 $L^{pos}=D+A = \sum_{(i,j)\in E}G_{(i,j)}^{pos}$ 。

可得 $L^{pos}$ 的二次型： $\overrightarrow{x}^TL^{pos}\overrightarrow{x} = \sum(x_i+x_j)^2 \geq0$ 衰伯。

同理铡羡，定義 $L_{sym}^{pos}=D^{-\frac{1}{2}}L^{pos}D^{-\frac{1}{2}}$ 。

可得 $L_{sym}^{pos}$ 的二次型： $\overrightarrow{x}^TL_{sym}^{pos}\overrightarrow{x} = \sum(\frac{x_i}{\sqrt {d_i}}+\frac{x_j}{\sqrt {d_j}})^2 \geq0$

由 $L_{sym}^{pos}=D^{-\frac{1}{2}}(D+A)D^{-\frac{1}{2}}=I+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$

可得 $\overrightarrow{x}^TL_{sym}^{pos}\overrightarrow{x} =\overrightarrow{x}^T(I+D^{-\frac{1}{2}}AD^{-\frac{1}{2}} )\overrightarrow{x} \geq0$

$\overrightarrow{x}^T\overrightarrow{x}+\overrightarrow{x}^T(D^{-\frac{1}{2}}AD^{-\frac{1}{2}} )\overrightarrow{x} \geq0$

$\overrightarrow{x}^T\overrightarrow{x}\geq-\overrightarrow{x}^T(D^{-\frac{1}{2}}AD^{-\frac{1}{2}} )\overrightarrow{x}$

$2\overrightarrow{x}^T\overrightarrow{x}\geq \overrightarrow{x}^T\overrightarrow{x}-\overrightarrow{x}^T(D^{-\frac{1}{2}}AD^{-\frac{1}{2}} )\overrightarrow{x}$

$2\overrightarrow{x}^T\overrightarrow{x}\geq \overrightarrow{x}^T(I-D^{-\frac{1}{2}}AD^{-\frac{1}{2}} )\overrightarrow{x}$

$2\overrightarrow{x}^T\overrightarrow{x}\geq \overrightarrow{x}^TD^{-\frac{1}{2}}(D-A)D^{-\frac{1}{2}} \overrightarrow{x}$

$2\overrightarrow{x}^T\overrightarrow{x}\geq \overrightarrow{x}^TL_{sym}\overrightarrow{x}$

$2\geq \frac{\overrightarrow{x}^TL_{sym}\overrightarrow{x}} {\overrightarrow{x}^T\overrightarrow{x}}$

由上述證明我們得出 $L_{sym}$ 的瑞利熵是 $\leq2$ 的意鲸。因此 $L_{sym}$ 的特征值也是恒 $\leq2$ 的烦周。

3. 傅里葉變換

傅里葉變換其實(shí)就是“去研究同一個(gè)事物在不同的域之間不同的視角”是怎樣的，以及在不同的域之間進(jìn)行變換怎顾。

最后編輯于：2021.08.27 21:55:32

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末读慎，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子槐雾，更是在濱河造成了極大的恐慌夭委，老刑警劉巖，帶你破解...
沈念sama閱讀 211,884評(píng)論 6贊 492
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件募强，死亡現(xiàn)場(chǎng)離奇詭異株灸，居然都是意外死亡，警方通過(guò)查閱死者的電腦和手機(jī)擎值，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,347評(píng)論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)慌烧，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人鸠儿，你說(shuō)我怎么就攤上這事屹蚊。” “怎么了进每？”我有些...
開(kāi)封第一講書(shū)人閱讀 157,435評(píng)論 0贊 348
道士緝兇錄：失蹤的賣(mài)姜人
文/不壞的土叔我叫張陵淑翼，是天一觀的道長(zhǎng)。經(jīng)常有香客問(wèn)我品追，道長(zhǎng)，這世上最難降的妖魔是什么冯丙？我笑而不...
開(kāi)封第一講書(shū)人閱讀 56,509評(píng)論 1贊 284
?港島之戀（遺憾婚禮）
正文為了忘掉前任肉瓦，我火速辦了婚禮，結(jié)果婚禮上胃惜，老公的妹妹穿的比我還像新娘泞莉。我一直安慰自己，他們只是感情好船殉，可當(dāng)我...
茶點(diǎn)故事閱讀 65,611評(píng)論 6贊 386
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布鲫趁。她就那樣靜靜地躺著，像睡著了一般利虫。火紅的嫁衣襯著肌膚如雪挨厚。梳的紋絲不亂的頭發(fā)上堡僻，一...
開(kāi)封第一講書(shū)人閱讀 49,837評(píng)論 1贊 290
城市分裂傳說(shuō)
那天，我揣著相機(jī)與錄音疫剃，去河邊找鬼钉疫。笑死，一個(gè)胖子當(dāng)著我的面吹牛巢价，可吹牛的內(nèi)容都是我干的牲阁。我是一名探鬼主播，決...
沈念sama閱讀 38,987評(píng)論 3贊 408
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼壤躲，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼想罕！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起囱挑，我...
開(kāi)封第一講書(shū)人閱讀 37,730評(píng)論 0贊 267
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤赁还，失蹤者是張志新（化名）和其女友劉穎，沒(méi)想到半個(gè)月后棉胀，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體法瑟，經(jīng)...
沈念sama閱讀 44,194評(píng)論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,525評(píng)論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年唁奢，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了霎挟。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 38,664評(píng)論 1贊 340
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡麻掸，死狀恐怖酥夭，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情脊奋，我是刑警寧澤熬北，帶...
沈念sama閱讀 34,334評(píng)論 4贊 330
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站诚隙，受9級(jí)特大地震影響讶隐，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜久又，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,944評(píng)論 3贊 313
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一巫延、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧地消，春花似錦炉峰、人聲如沸。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 30,764評(píng)論 0贊 21
一樁弒父案疼阔，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)。三九已至，卻和暖如春婆廊，著一層夾襖步出監(jiān)牢的瞬間迅细，已是汗流浹背。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 31,997評(píng)論 1贊 266
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工否彩，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留疯攒，地道東北人。一個(gè)月前我還...
沈念sama閱讀 46,389評(píng)論 2贊 360
代替公主和親
正文我出身青樓列荔，卻偏偏與公主長(zhǎng)得像敬尺，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子贴浙，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,554評(píng)論 2贊 349