本文是發(fā)表在KDD會(huì)議上的一篇文章抄瓦，以大規(guī)模可學(xué)習(xí)圖卷積神經(jīng)網(wǎng)絡(luò)為研究?jī)?nèi)容，作者來自于華盛頓大學(xué)碴开。在筆者看過的很多graph embedding的論文中，華盛頓大學(xué)出現(xiàn)過很多次博秫，看來在該領(lǐng)域華盛頓大學(xué)很優(yōu)秀呀潦牛。言歸正傳，我將從以下三個(gè)方面挡育，相關(guān)工作巴碗、模型算法、實(shí)驗(yàn)設(shè)計(jì)進(jìn)行總結(jié)闡述即寒。

1. 相關(guān)工作

? ? ? ?眾所周知橡淆，深度學(xué)習(xí)領(lǐng)域，卷積神經(jīng)網(wǎng)絡(luò)CNN功能強(qiáng)大母赵，無論是在圖像識(shí)別逸爵，自然語言處理，機(jī)器翻譯等領(lǐng)域市咽，都有很出彩的表現(xiàn)痊银。大規(guī)模減少權(quán)值參數(shù)的同時(shí)抵蚊，避免了人工特征提取施绎。然而，傳統(tǒng)卷積核是應(yīng)用在網(wǎng)格樣式(grid-like)的數(shù)據(jù)上贞绳，圖片也是由一個(gè)個(gè)規(guī)則的像素矩陣構(gòu)成的谷醉。因此，規(guī)則卷積需要網(wǎng)格化數(shù)據(jù)冈闭。其實(shí)俱尼，網(wǎng)格數(shù)據(jù)在一定程度上，是一種特殊類型的圖數(shù)據(jù)萎攒。

? ? ? ?當(dāng)面對(duì)現(xiàn)實(shí)世界中普遍存在的網(wǎng)絡(luò)結(jié)構(gòu)樣式的圖數(shù)據(jù)時(shí)遇八，由于每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)目不同矛绘，鄰居節(jié)點(diǎn)之間沒有自然的順序關(guān)系，強(qiáng)大的CNN神器要想在graph上發(fā)揮作用刃永，受到嚴(yán)重的限制货矮。圖數(shù)據(jù)的應(yīng)用主要在于節(jié)點(diǎn)分類問題，基于圖中網(wǎng)絡(luò)關(guān)系和節(jié)點(diǎn)自身特征對(duì)節(jié)點(diǎn)進(jìn)行分類預(yù)測(cè)斯够。傳統(tǒng)的方法是進(jìn)行g(shù)raph embedding等操作囚玫，這也是一個(gè)重要的研究領(lǐng)域。

1.1 GCN圖卷積神經(jīng)網(wǎng)絡(luò)

? ? ? ?借鑒譜圖卷積理論读规，圖卷積神經(jīng)網(wǎng)絡(luò)GCN被提出抓督，并且在cora等引文網(wǎng)絡(luò)的數(shù)據(jù)集上取得了顯著的效果。GCN網(wǎng)絡(luò)的層間前向傳播規(guī)則束亏，也是GCN的核心原理（詳見另一篇筆記）铃在，如下所示：

? ? ? ?在該公式中，是對(duì)角化的節(jié)點(diǎn)度矩陣碍遍，是加入自環(huán)連接的鄰接矩陣涌穆，是訓(xùn)練過程中進(jìn)行學(xué)習(xí)的各層參數(shù)。本質(zhì)上講雀久，GCN并不是嚴(yán)格意義上的卷積網(wǎng)咯宿稀，它只是借鑒卷積計(jì)算思想的聚合操作，將節(jié)點(diǎn)的鄰居節(jié)點(diǎn)信息“卷積”到節(jié)點(diǎn)自身赖捌，在此過程中祝沸，鄰居節(jié)點(diǎn)的地位是相等的，簡(jiǎn)而言之越庇，只是做了算數(shù)平均罩锐。而且，對(duì)于一個(gè)特定的網(wǎng)絡(luò)而言卤唉，是固定的涩惑，不可訓(xùn)練的。和CNN通過學(xué)習(xí)局部濾波器權(quán)重桑驱，自動(dòng)提取特征相比遜色不少竭恬。GCN不可訓(xùn)練的聚合操作限制了圖數(shù)據(jù)中CNN的特征提取能力。

1.2 GATs圖注意力機(jī)制

? ? ? ?注意力機(jī)制需要在節(jié)點(diǎn)和其鄰居節(jié)點(diǎn)間進(jìn)行額外操作熬的，也會(huì)帶來存儲(chǔ)和計(jì)算資源的消耗問題痊硕。GCN中的算數(shù)平均聚合用特征向量加權(quán)和取代。公式如下：


? ? ? ?注意力機(jī)制之前沒有接觸過押框，會(huì)作為一篇筆記進(jìn)行專門總結(jié)岔绸，到時(shí)候這部分再更新。

2. 模型算法

? ? ? ?本文的算法創(chuàng)新點(diǎn)主要在于以下兩個(gè)方面，可學(xué)習(xí)的圖卷積層和針對(duì)大圖的子圖訓(xùn)練策略盒揉。
? ? ? ?為了充分利用CNN的規(guī)則卷積核進(jìn)行空間平移從而自動(dòng)提取特征的優(yōu)點(diǎn)晋被，需要將網(wǎng)絡(luò)結(jié)構(gòu)的圖數(shù)據(jù)轉(zhuǎn)化為網(wǎng)格數(shù)據(jù)。首先要解決的兩個(gè)問題是節(jié)點(diǎn)鄰居數(shù)標(biāo)準(zhǔn)化和鄰居節(jié)點(diǎn)順序的選擇刚盈。本文作者是這樣進(jìn)行解決的墨微，如圖所示：

fig1 網(wǎng)格數(shù)據(jù)構(gòu)建

? ? ? ?但是這樣的解決方法是有前提的垒手，每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)個(gè)數(shù)足夠多（保證基本大于k且基本均勻蒜焊，對(duì)于非常稀疏的大量孤立節(jié)點(diǎn)存在的網(wǎng)絡(luò),k取得值很小，鄰居節(jié)點(diǎn)間特征傳播沒有意義）科贬。一般對(duì)CNN來講，深度卷積的效果可能更好一點(diǎn)，但是榜掌，GCN的層數(shù)一般是2-3層优妙，層數(shù)過高，會(huì)造成過擬合憎账。

? ? ? ?結(jié)合圖卷積網(wǎng)絡(luò)套硼，構(gòu)造可學(xué)習(xí)的圖卷積，在DCNN之前增加了一個(gè)圖嵌入層（graph embedding）,將高維圖數(shù)據(jù)（節(jié)點(diǎn)特征）低維度表示胞皱，,不經(jīng)過激活函數(shù)邪意，則還是特征表示。同時(shí)反砌，和雾鬼，并且實(shí)現(xiàn)了節(jié)點(diǎn)特征從高維空間降低維空間的映射。

? ? ? ?大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)的子圖訓(xùn)練宴树，借鑒隨機(jī)抽樣策菜，裁剪補(bǔ)丁的思想，通過裁剪大圖獲得用于訓(xùn)練的小圖酒贬。子圖選擇算法我們通過下圖直觀理解又憨，算法步驟如下：

 1.隨機(jī)采樣，得到初始節(jié)點(diǎn)（圖中三個(gè)橘色節(jié)點(diǎn)）
 2.廣度優(yōu)先搜索锭吨，為子圖迭代擴(kuò)充鄰居節(jié)點(diǎn)
 3.$N_m$每次迭代可置不同值（第一次5個(gè)藍(lán)色節(jié)點(diǎn)蠢莺，第二次7個(gè)一藍(lán)色節(jié)點(diǎn)為中心綠色鄰居節(jié)點(diǎn)）
 4.初始節(jié)點(diǎn)和迭代搜索到的節(jié)點(diǎn)，總共15個(gè)節(jié)點(diǎn)零如，作為訓(xùn)練的子圖樣本

子圖生成算法

? ? ? ? 綜上所述浪秘，本文提出的模型算法流程應(yīng)該是這樣子滴：

圖數(shù)據(jù)節(jié)點(diǎn)分類處理流程

? ? ? ?如圖所示，圖數(shù)據(jù)的研究埠况，無論是節(jié)點(diǎn)分類還是鏈路預(yù)測(cè)等應(yīng)用耸携，歸根結(jié)底，都是由其本質(zhì)特征決定的辕翰，即相較于傳統(tǒng)的一維數(shù)據(jù)夺衍、圖像數(shù)據(jù)、文本數(shù)據(jù)喜命，圖數(shù)據(jù)不僅具有節(jié)點(diǎn)甚至邊的自身特征沟沙，還有節(jié)點(diǎn)間的網(wǎng)絡(luò)關(guān)系。不同于graph-embedding常用的node2vec先做特征衍生壁榕，再跑機(jī)器學(xué)習(xí)模型的做法矛紫，圖深度學(xué)習(xí)將特征提取和模型訓(xùn)練合并進(jìn)行。子圖選擇算法尤其適用于具有若干社區(qū)牌里，社區(qū)間聯(lián)系稀疏颊咬，社區(qū)內(nèi)關(guān)系緊密的情況 务甥。GCN在本文模型中僅僅作為embedding降維的工具，這個(gè)工作node2vec也可以進(jìn)行喳篇，不過時(shí)間效率可能不及GCN敞临。最關(guān)鍵的步驟就是黃色部分，實(shí)現(xiàn)了非歐到歐式空間的網(wǎng)格化抽象轉(zhuǎn)化麸澜，以及鄰居節(jié)點(diǎn)的統(tǒng)一有序排列挺尿。為直接應(yīng)用CNN的可行性提供基礎(chǔ)。這樣做還有一個(gè)好處炊邦，我們知道圖深度學(xué)習(xí)编矾，按照目前GCN的做法，隱藏層只有兩到三層馁害，層數(shù)增加之后窄俏，帶來的過擬合現(xiàn)象，同時(shí)蜗细，GCN隱藏層的作用本質(zhì)上是將鄰居節(jié)點(diǎn)信息卷積到當(dāng)前節(jié)點(diǎn)上裆操，隨著隱藏層加深，所有節(jié)點(diǎn)會(huì)最終被同質(zhì)化為同一個(gè)節(jié)點(diǎn)炉媒，使得模型退化踪区，即圖深度學(xué)習(xí)并不“深”。但是按照本文的做法吊骤，最后用傳統(tǒng)卷積神經(jīng)網(wǎng)絡(luò)做缎岗，相當(dāng)于一個(gè)標(biāo)準(zhǔn)的一維卷積問題(1d-cnn)，原理上講白粉，不存在上述這個(gè)問題传泊，設(shè)計(jì)深層模型應(yīng)該沒有問題。這里僅是筆者猜測(cè)鸭巴，沒有做實(shí)驗(yàn)論證眷细，以后有時(shí)間補(bǔ)上。

3.實(shí)驗(yàn)設(shè)計(jì)

? ? ? ?本文的實(shí)驗(yàn)數(shù)據(jù)集如下圖所示鹃祖，采用經(jīng)典的引用網(wǎng)絡(luò)數(shù)據(jù)集Cora溪椎，Ci'te'se'r以及Pubmed，前兩個(gè)數(shù)據(jù)集節(jié)點(diǎn)數(shù)只有兩三千恬口，特征維數(shù)上千校读，這種情況一般是embedding之后表示學(xué)習(xí)的結(jié)果，比如Cora的特征就是文本數(shù)據(jù)關(guān)鍵詞one-hot編碼后的結(jié)果祖能，文中指出是bag-of-word文檔表示后得到的特征向量歉秫。從Degree一列可以看出，網(wǎng)絡(luò)中節(jié)點(diǎn)的度數(shù)不低养铸，平均或最高（由于論文作者沒有闡述該列含義雁芙，此處為筆者猜測(cè)）節(jié)點(diǎn)度數(shù)4-6個(gè)轧膘，網(wǎng)絡(luò)不是特別稀疏。

數(shù)據(jù)集

? ? ? ?我們注意到却特，在實(shí)驗(yàn)設(shè)置的時(shí)候扶供，有Transductive和Inductive之分筛圆，Transductive是轉(zhuǎn)化學(xué)習(xí)裂明，是指在訓(xùn)練過程中，無標(biāo)簽節(jié)點(diǎn)的網(wǎng)絡(luò)結(jié)構(gòu)和特征向量是已知的太援，是一個(gè)半監(jiān)督學(xué)習(xí)的過程闽晦；Inductive是歸納學(xué)習(xí)，是指訓(xùn)練過程中提岔，測(cè)試樣本是不存在的仙蛉，包括待測(cè)節(jié)點(diǎn)的特征向量和網(wǎng)絡(luò)結(jié)構(gòu)，這篇文章的PPI數(shù)據(jù)集就屬于這種情況碱蒙，作者在切分訓(xùn)練集驗(yàn)證集測(cè)試集時(shí)荠瘪，直接按照子圖切分的，也就是說測(cè)試過程是在一個(gè)新的圖上進(jìn)行的赛惩。之前看的一篇文章《Revisiting Semi-Supervised Learning with Graph Embedding》中就這兩個(gè)問題進(jìn)行了一些描述哀墓，等下次再寫，這里不贅述了喷兼。個(gè)人感覺篮绰，Inductive和動(dòng)態(tài)網(wǎng)絡(luò)的節(jié)點(diǎn)分類問題還不太一樣，動(dòng)態(tài)網(wǎng)絡(luò)是指網(wǎng)絡(luò)中節(jié)點(diǎn)可以隨時(shí)進(jìn)出季惯，這部分動(dòng)態(tài)進(jìn)出的節(jié)點(diǎn)并不是孤立的一個(gè)子圖吠各，所以不能把這部分工作當(dāng)作是動(dòng)態(tài)檢測(cè)的參考案例。
? ? ? ?Transductive部分的三個(gè)數(shù)據(jù)集都采用了GCN作為embedding層進(jìn)行降維勉抓，然后各自分別堆疊2贾漏，1，1層LGCLs(就是網(wǎng)格化接1d-cnn)藕筋，最后用全連接分類器做預(yù)測(cè)纵散。對(duì)于Inductive，作者采用子圖方式訓(xùn)練念逞，網(wǎng)絡(luò)結(jié)構(gòu)基本不變困食。主要是embedding,k,dropout,L2正則化的參數(shù)設(shè)置上，根據(jù)問題規(guī)模進(jìn)行相應(yīng)調(diào)整翎承。

Inductive實(shí)驗(yàn)結(jié)果

? ? ? ?作者還對(duì)網(wǎng)格化過程的模型中硕盹，k值選擇的科學(xué)性進(jìn)行研究，經(jīng)過實(shí)驗(yàn)叨咖，他認(rèn)為k的選擇應(yīng)當(dāng)比平均節(jié)點(diǎn)度數(shù)大一點(diǎn)（由此我們推出前文數(shù)據(jù)集表格中的degree是指圖的平均節(jié)點(diǎn)度數(shù)）瘩例。但具體值仍然需要是通過實(shí)驗(yàn)來選擇啊胶。

不同k值選擇的表現(xiàn)

? ? ? ?好了，就說到這里了垛贤，第一次寫論文筆記焰坪，一些不到位的地方，歡迎大家批評(píng)指正聘惦。

作者原創(chuàng)某饰，歡迎交流，如需轉(zhuǎn)載請(qǐng)先聯(lián)系作者善绎。