本文是發(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)行解決的墨微,如圖所示:
? ? ? ?第一次看到這個(gè)構(gòu)建過程,覺得既簡(jiǎn)單又巧妙扁掸,該例子不僅蘊(yùn)含著最大化降采樣原理翘县,還有1d卷積核的應(yīng)用,這里k取4谴分,k是一個(gè)超參數(shù)锈麸,k的選取很重要,一般k 的選擇牺蹄,考慮節(jié)點(diǎn)的平均度數(shù)以及分類任務(wù)的復(fù)雜性忘伞。在三個(gè)特征維度上選擇每一維選最大的四個(gè)值進(jìn)行組合,所以這里的節(jié)點(diǎn)并不是真是鄰居節(jié)點(diǎn)特征沙兰,是經(jīng)過加工之后的氓奈,有max-pooling的感覺,不僅解決了樹木標(biāo)準(zhǔn)化為4們還按照大小順序排好序鼎天。節(jié)點(diǎn)特征向量是三維舀奶,視為三個(gè)通道channel,由于只有一個(gè)橘色節(jié)點(diǎn)斋射,因此batch_size為1育勺,卷積核kennel對(duì)應(yīng)的也是三通道,filter個(gè)數(shù)是4罗岖,即
? ? ? ?但是這樣的解決方法是有前提的垒手,每個(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)分類還是鏈路預(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í)驗(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)整翎承。
? ? ? ?作者還對(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)來選擇啊胶。
? ? ? ?好了,就說到這里了垛贤,第一次寫論文筆記焰坪,一些不到位的地方,歡迎大家批評(píng)指正聘惦。
作者原創(chuàng)某饰,歡迎交流,如需轉(zhuǎn)載請(qǐng)先聯(lián)系作者善绎。