菜鳥筆記之《Large-Scale Learnable Graph Convolutional Networks》

本文是發(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的核心原理(詳見另一篇筆記)铃在,如下所示:
X_{x+1} = \sigma(\hat D^{{-}{\frac{1}{2}}} \hat A \hat D^{{-}{\frac{1}{2}}}X_lW_l)

? ? ? ?在該公式中,\hat D是對(duì)角化的節(jié)點(diǎn)度矩陣碍遍,\hat A是加入自環(huán)連接的鄰接矩陣涌穆,W_l是訓(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ù)平均罩锐。而且,\hat D^{{-}{\frac{1}{2}}} \hat A \hat D^{{-}{\frac{1}{2}}}對(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)和取代。公式如下:
e_l^{i,j} = a_l(W_lx_l^i,W_lx_l^j)
a_l^{i,j} = softmax(e_l^{i,j})
? ? ? ?注意力機(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è)構(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罗岖,即
(k/2+1)*4*3
涧至,卷積核從上到下,步長(zhǎng)為1桑包,不做padding南蓬,得到
3*4
的中間結(jié)果,接下來哑了,卷積核
(k/2+1)*5*4
,得到最終
1*5
的特征向量赘方,表征當(dāng)前的橘色節(jié)點(diǎn)特征。

? ? ? ?但是這樣的解決方法是有前提的垒手,每個(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)特征)低維度表示胞皱,\hat D^{{-}{\frac{1}{2}}} \hat A \hat D^{{-}{\frac{1}{2}}}X_0W_0,不經(jīng)過激活函數(shù)邪意,則還是特征表示。同時(shí)反砌,W_0\in R^{C_0\times C_1}X_1\in R^{N\times C_1}雾鬼,并且C_1<C_0實(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)系作者善绎。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末黔漂,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子禀酱,更是在濱河造成了極大的恐慌炬守,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,807評(píng)論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件剂跟,死亡現(xiàn)場(chǎng)離奇詭異减途,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)曹洽,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,284評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門鳍置,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人衣洁,你說我怎么就攤上這事墓捻。” “怎么了坊夫?”我有些...
    開封第一講書人閱讀 169,589評(píng)論 0 363
  • 文/不壞的土叔 我叫張陵砖第,是天一觀的道長(zhǎng)。 經(jīng)常有香客問我环凿,道長(zhǎng)梧兼,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,188評(píng)論 1 300
  • 正文 為了忘掉前任智听,我火速辦了婚禮羽杰,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘到推。我一直安慰自己考赛,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,185評(píng)論 6 398
  • 文/花漫 我一把揭開白布莉测。 她就那樣靜靜地躺著颜骤,像睡著了一般。 火紅的嫁衣襯著肌膚如雪捣卤。 梳的紋絲不亂的頭發(fā)上忍抽,一...
    開封第一講書人閱讀 52,785評(píng)論 1 314
  • 那天八孝,我揣著相機(jī)與錄音,去河邊找鬼鸠项。 笑死干跛,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的祟绊。 我是一名探鬼主播楼入,決...
    沈念sama閱讀 41,220評(píng)論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼久免!你這毒婦竟也來了浅辙?” 一聲冷哼從身側(cè)響起扭弧,我...
    開封第一講書人閱讀 40,167評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤阎姥,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后鸽捻,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體呼巴,經(jīng)...
    沈念sama閱讀 46,698評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,767評(píng)論 3 343
  • 正文 我和宋清朗相戀三年御蒲,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了衣赶。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,912評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡厚满,死狀恐怖府瞄,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情碘箍,我是刑警寧澤遵馆,帶...
    沈念sama閱讀 36,572評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站丰榴,受9級(jí)特大地震影響货邓,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜四濒,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,254評(píng)論 3 336
  • 文/蒙蒙 一换况、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧盗蟆,春花似錦戈二、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,746評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至骨饿,卻和暖如春亏栈,著一層夾襖步出監(jiān)牢的瞬間台腥,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,859評(píng)論 1 274
  • 我被黑心中介騙來泰國(guó)打工绒北, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留黎侈,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,359評(píng)論 3 379
  • 正文 我出身青樓闷游,卻偏偏與公主長(zhǎng)得像峻汉,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子脐往,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,922評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容