【论文解读】GCN论文总结
本次要總結(jié)和分享的是ICLR2017的關(guān)于GCN方面的代表作之一論文：SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS，論文鏈接為 paper[1]，參考的實(shí)現(xiàn)代碼為pygcn[2]
文章目錄
先導(dǎo)知識
論文動機(jī)
模型
切比雪夫逼近卷積核函數(shù)
圖上的快速近似卷積
半監(jiān)督節(jié)點(diǎn)分類
實(shí)驗(yàn)
核心代碼分析
個人總結(jié)
先導(dǎo)知識
在讀這篇論文之前，需要對先導(dǎo)論文 Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering 有著深入的理解，否則里面數(shù)學(xué)推導(dǎo)會讓人感到迷茫。關(guān)于該先導(dǎo)論文，之前的博文已經(jīng)對其推導(dǎo)過程進(jìn)行了詳細(xì)分析，Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering[3]，
GCN論文閱讀總結(jié)
感興趣可以一看，因?yàn)槠鋽?shù)學(xué)推導(dǎo)過程比較復(fù)雜，下面進(jìn)行下簡單梳理：
回顧卷積定義
在維基百科里，可以得到卷積操作的定義： 為 的卷積
離散形式
連續(xù)形式
用傅里葉變換來表示卷積
表示傅里葉變換， 傅里葉逆變換
也即是：即對于函數(shù) 與 兩者的卷積是其函數(shù)傅立葉變換乘積的逆變換
在graph上的卷積形式推導(dǎo)過程
上式中的 表示卷積核函數(shù)（帶參數(shù)）， 表示是graph的鄰接矩陣 的拉普拉斯矩陣 的特征向量
由此得到圖上的卷積形式：
其中 為激活函數(shù)， 就是卷積核，注意 為拉普拉斯矩陣 特征值組成的對角矩陣，所以 也是對角的
推導(dǎo)可得卷積核函數(shù) 如下：
繼續(xù)推導(dǎo)可得：
上式中 為graph的鄰接矩陣A的拉普拉斯矩陣， 為卷積核參數(shù)。
切比雪夫逼近卷積核
其中 表示切比雪夫多項(xiàng)式， 表示模型需要學(xué)習(xí)的參數(shù)， 表示re-scaled的 特征值對角矩陣，進(jìn)行這個shift變換的原因是Chebyshev多項(xiàng)式的輸入要在 之間，因此 ?( 為 的最大特征值）
由此可以進(jìn)行遞推逼近：
熟悉了上述推導(dǎo)過程，那么對于本文要總結(jié)的論文理解起來就簡單多了。
論文動機(jī)
考慮對圖（如論文引用網(wǎng)絡(luò)）中的節(jié)點(diǎn)（如文檔）進(jìn)行分類的問題，其中僅有一小部分節(jié)點(diǎn)帶有l(wèi)abel信息。這個問題可以被定義為基于圖的半監(jiān)督學(xué)習(xí)，其中標(biāo)簽信息通過某種形式的基于圖的顯式正則化在圖上進(jìn)行平滑，比如在損失函數(shù)上加上拉普拉斯正則項(xiàng)，但是這種做法的前提假設(shè)是：在圖中相鄰連接的節(jié)點(diǎn)可能擁有相似的標(biāo)簽信息，這種假設(shè)可能會限制建模能力，因?yàn)閳D中的邊不一定連接擁有相似的節(jié)點(diǎn)，但可能包含額外的信息。
本論文所提方法，能直接對graph進(jìn)行編碼，避免了正則平滑， 作用在圖的鄰接矩陣上進(jìn)行有監(jiān)督學(xué)習(xí)，并且能學(xué)習(xí)到每個節(jié)點(diǎn)的embedding向量。
本論文受上面所提到的先導(dǎo)論文啟發(fā)，限制切比雪夫多項(xiàng)式 ，提出了一種可在圖上進(jìn)行快速卷積的模型，并且提出了 ，在數(shù)學(xué)上進(jìn)行了推導(dǎo)，證明了該模型的合理性；同時展示了這種基于圖的神經(jīng)網(wǎng)絡(luò)模型如何進(jìn)行半監(jiān)督的分類。
模型
該部分直接在先導(dǎo)知識基礎(chǔ)上進(jìn)行數(shù)學(xué)公式的推導(dǎo)，最終得到本論文所提的模型。
切比雪夫逼近卷積核函數(shù)
在先導(dǎo)知識中，卷積核可等于
則有：
圖上的快速近似卷積
在切比雪夫逼近卷積核函數(shù)時，本論文中限制其切比雪夫項(xiàng)數(shù) ，同時進(jìn)一步近似 ，則可得：
可以看出上述公式是一種線性的變換。
在 Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering[4] 中，分析過，切比雪夫的項(xiàng)數(shù)就是就是圖卷積的感受野，而這里限制了項(xiàng)數(shù) K= 1，相當(dāng)于只做了所謂的 first-order approximation，每個節(jié)點(diǎn)考慮其一階鄰居對他的影響。
這樣做有一些好處的，比如能夠緩解局部鄰域結(jié)構(gòu)的過度擬合問題，同時這種分層線性的計算方式，允許我們構(gòu)建更深層次的模型，可以提高建模能力，比如當(dāng)疊加兩層的卷積時，相當(dāng)于每個節(jié)點(diǎn)可以把 2-hops 鄰居的特征加以聚合。這樣就避免了k=1時只能考慮一階鄰居的影響了。
進(jìn)一步的，為了限制模型參數(shù)，降低每層的計算等，令 ，則有：
的特征值在 范圍來，當(dāng)網(wǎng)絡(luò)疊加更多層時，容易出現(xiàn)梯度消散/爆炸的問題。論文中提出了 ，即：
注意：從數(shù)學(xué)公式的推導(dǎo)上看在 的基礎(chǔ)上處理是合理的，同時從分析上看也是合理的，因?yàn)猷徑泳仃? 對角線為0，在卷積時，每個節(jié)點(diǎn)只能聚合其相鄰節(jié)點(diǎn)特征，卻忽略了自身特征，因此加上 本身也是有必要的。這種 的操作可理解為 ，也即增加自循環(huán)。
這種 操作，保證了結(jié)果的對稱性，同時做到了近似歸一化。，針對不同的數(shù)據(jù)集， 取值不一樣，
因此卷積過程可表達(dá)為如下：
上式中 ， 為樣本數(shù)量， 為輸入通道數(shù)（也就是每個節(jié)點(diǎn)的特征向量維度）， 為卷積核參數(shù)矩陣， 為卷積后的矩陣。
上式可以形象的以下圖表示：
半監(jiān)督節(jié)點(diǎn)分類
上圖中 表示每個輸入節(jié)點(diǎn)的特征向量維度， 表示卷積后的feature_maps個數(shù)，多層疊加時，最后一層F為類別個數(shù)。
上面我們得到：
這里記：，這一步可以在預(yù)處理階段計算好，疊加兩層卷積，則可以得：
上式中， ， 為樣本數(shù)量， 為輸入通道數(shù)（也就是每個節(jié)點(diǎn)的特征向量維度），， 為 輸入層到隱藏層的參數(shù)矩陣，是模型需要學(xué)習(xí)的，有 個 ， 為隱藏層到輸出層的參數(shù)矩陣，是模型需要進(jìn)行學(xué)習(xí)的。卷積結(jié)果為 ，F可理解為類別個數(shù)。
上述公式中是以row-wise進(jìn)行softmax， 可理解為屬于某個類別的logits， 可理解為屬于所有類別的logits。則模型的損失函數(shù)可表示為如下：
上式其實(shí)就是多分類上的cross entropy loss，中 為帶標(biāo)簽的節(jié)點(diǎn)數(shù)量。注意第二項(xiàng)是在 上計算。
通過上面的推導(dǎo)分析，我們可以得到本論文圖卷積的數(shù)學(xué)公式如下：上式中 表示卷積的隱藏層個數(shù)（疊加層數(shù)，可聚合節(jié)點(diǎn)本身與其 的節(jié)點(diǎn)特征，可理解卷積感受野）， 表示第 層的隱藏層輸出，剛開始 ， 表示模型需要學(xué)習(xí)的參數(shù)矩陣。注意在疊加多層時， 是不變的。單從這個公式來看，本論文所提的圖上的卷積方式其實(shí)很簡單的。
實(shí)驗(yàn)
數(shù)據(jù)集：論文中用到了上述四個數(shù)據(jù)集，上表中展示了每個數(shù)據(jù)集的節(jié)點(diǎn)數(shù)量、邊的數(shù)量、類別數(shù)、特征維度、帶標(biāo)簽節(jié)點(diǎn)占比。
以Citation network（Citeseer,Cora,Pubmed）舉例，該網(wǎng)絡(luò)是大量文檔組成，以文檔為節(jié)點(diǎn)，以是否有"引用“來連邊。其中每個節(jié)點(diǎn)的原始輸入特征有詞袋特征來定義獲得，每個節(jié)點(diǎn)都有唯一所屬的類別（class label)。由此構(gòu)成了一張圖。
實(shí)驗(yàn)的一些參數(shù)等設(shè)置，這里就不詳敘述了。
實(shí)驗(yàn)結(jié)果：上圖的實(shí)驗(yàn)中，評價指標(biāo)為節(jié)點(diǎn)分類的ACC，加粗的GCN(this paper) 為論文中的所提的有兩層疊加的圖卷積網(wǎng)絡(luò)，GCN(rand，splits) 與GCN(this paper) 網(wǎng)絡(luò)結(jié)構(gòu)一樣，只不過數(shù)據(jù)集劃分上不一樣而已。由上圖可以看出，本論文提出的GCN網(wǎng)絡(luò)分類效果最好。
除此之外，論文中還和以往的一些GCN網(wǎng)絡(luò)進(jìn)行了對比實(shí)驗(yàn)：
在這里插入圖片描述顯然也是本論文中所提的帶有Renormalization trick的GCN效果最好。
核心代碼分析
拋開一系列的數(shù)學(xué)推導(dǎo)不管，其實(shí)本論文所提的圖卷積方法可用數(shù)學(xué)公式表示如下：
初始時：，而 始終是不變的，可以提前計算好。因此代碼實(shí)現(xiàn)起來其實(shí)非常簡單了。
代碼參考的是pygcn[5]
開源代碼中使用的數(shù)據(jù)集是Cora dataset，關(guān)于文檔引用的數(shù)據(jù)集，文檔定義為圖中的節(jié)點(diǎn)，文檔間是否有引用關(guān)系定義為邊。由詞袋特征作為節(jié)點(diǎn)初始特征，任務(wù)是對節(jié)點(diǎn)進(jìn)行分類。
pygcn/data/cora/ 下有兩個文本文件
cora.cites 每行格式如：ID of cited paper \t ID of citing paper
cora.content 每行格式如：paper_id ?word_attributes class_label
加載上述兩個文件，進(jìn)行構(gòu)圖，得到歸一化后的鄰接矩陣、提取節(jié)點(diǎn)特征、label等
def?load_data(path="../data/cora/",?dataset="cora"):"""Load?citation?network?dataset?(cora?only?for?now)"""print('Loading?{}?dataset...'.format(dataset))idx_features_labels?=?np.genfromtxt("{}{}.content".format(path,?dataset),dtype=np.dtype(str))features?=?sp.csr_matrix(idx_features_labels[:,?1:-1],?dtype=np.float32)labels?=?encode_onehot(idx_features_labels[:,?-1])#?build?graphidx?=?np.array(idx_features_labels[:,?0],?dtype=np.int32)##?獲得每個paper_id在cora.content中所在的行數(shù)idx_map?=?{j:?i?for?i,?j?in?enumerate(idx)}?edges_unordered?=?np.genfromtxt("{}{}.cites".format(path,?dataset),dtype=np.int32)##?將有連接的一對節(jié)點(diǎn)(paper_id在cora.content的行數(shù)）作為一行，生成一個np.arrayedges?=?np.array(list(map(idx_map.get,?edges_unordered.flatten())),dtype=np.int32).reshape(edges_unordered.shape)##?鄰接矩陣A，有邊為1，反之為0adj?=?sp.coo_matrix((np.ones(edges.shape[0]),?(edges[:,?0],?edges[:,?1])),shape=(labels.shape[0],?labels.shape[0]),dtype=np.float32)#?將有向邊變成對稱的無向邊adj?=?adj?+?adj.T.multiply(adj.T?>?adj)?-?adj.multiply(adj.T?>?adj)##?歸一化features?=?normalize(features)adj?=?normalize(adj?+?sp.eye(adj.shape[0]))idx_train?=?range(140)idx_val?=?range(200,?500)idx_test?=?range(500,?1500)features?=?torch.FloatTensor(np.array(features.todense()))labels?=?torch.LongTensor(np.where(labels)[1])adj?=?sparse_mx_to_torch_sparse_tensor(adj)idx_train?=?torch.LongTensor(idx_train)idx_val?=?torch.LongTensor(idx_val)idx_test?=?torch.LongTensor(idx_test)return?adj,?features,?labels,?idx_train,?idx_val,?idx_testdef?normalize(mx):"""Row-normalize?sparse?matrix"""rowsum?=?np.array(mx.sum(1))r_inv?=?np.power(rowsum,?-1).flatten()r_inv[np.isinf(r_inv)]?=?0.r_mat_inv?=?sp.diags(r_inv)mx?=?r_mat_inv.dot(mx)return?mx顯然上述的鄰居矩陣的歸一化為這種形式：，而非 。矩陣的歸一化有多種，在上面的實(shí)驗(yàn)分析部分也做了不同歸一化的對比。因此在實(shí)際實(shí)驗(yàn)中，可進(jìn)行嘗試，選擇效果較好的一種。
class?GCN(nn.Module):def?__init__(self,?nfeat,?nhid,?nclass,?dropout):super(GCN,?self).__init__()self.gc1?=?GraphConvolution(nfeat,?nhid)self.gc2?=?GraphConvolution(nhid,?nclass)self.dropout?=?dropoutdef?forward(self,?x,?adj):x?=?F.relu(self.gc1(x,?adj))x?=?F.dropout(x,?self.dropout,?training=self.training)x?=?self.gc2(x,?adj)return?F.log_softmax(x,?dim=1)上述的GCN代碼就很簡單的，就是疊加了兩層卷積的網(wǎng)絡(luò)，在實(shí)際訓(xùn)練時，網(wǎng)絡(luò)的輸入是 和歸一化后的鄰接矩陣 ，具體可再看這個卷積是怎么做的，代碼如下：
class?GraphConvolution(Module):"""Simple?GCN?layer,?similar?to?https://arxiv.org/abs/1609.02907"""def?__init__(self,?in_features,?out_features,?bias=True):super(GraphConvolution,?self).__init__()self.in_features?=?in_featuresself.out_features?=?out_featuresself.weight?=?Parameter(torch.FloatTensor(in_features,?out_features))if?bias:self.bias?=?Parameter(torch.FloatTensor(out_features))else:self.register_parameter('bias',?None)self.reset_parameters()def?reset_parameters(self):stdv?=?1.?/?math.sqrt(self.weight.size(1))self.weight.data.uniform_(-stdv,?stdv)if?self.bias?is?not?None:self.bias.data.uniform_(-stdv,?stdv)def?forward(self,?input,?adj):support?=?torch.mm(input,?self.weight)output?=?torch.spmm(adj,?support)if?self.bias?is?not?None:return?output?+?self.biaselse:return?outputdef?__repr__(self):return?self.__class__.__name__?+?'?('?\+?str(self.in_features)?+?'?->?'?\+?str(self.out_features)?+?')'上面代碼主要看forward部分即可，顯然實(shí)現(xiàn)的就是 操作而已。
個人總結(jié)
本論文模型上的創(chuàng)新點(diǎn)主要有：?提出了在圖上的快速卷積的模型（K=1)，第二是提出了renormalization_trick
在限制K=1時，大大限制了模型參數(shù)數(shù)量，同時可實(shí)現(xiàn)多層的疊加，當(dāng)疊加l層時，可聚合節(jié)點(diǎn)自身及其l-hops的節(jié)點(diǎn)特征。疊加層數(shù)越大，卷積感受野越大。
拋去繁雜的數(shù)學(xué)公式推導(dǎo)，感性理解本論文所提出的快速卷積，其實(shí)非常簡單：
參考資料
[1]
paper: https://arxiv.org/pdf/1609.02907.pdf
[2]pygcn: https://github.com/tkipf/pygcn
[3]Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering: https://blog.csdn.net/Mr_tyting/article/details/108916787
[4]Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering: https://blog.csdn.net/Mr_tyting/article/details/108916787
[5]pygcn: https://github.com/tkipf/pygcn
往期精彩回顧適合初學(xué)者入門人工智能的路線及資料下載機(jī)器學(xué)習(xí)及深度學(xué)習(xí)筆記等資料打印機(jī)器學(xué)習(xí)在線手冊深度學(xué)習(xí)筆記專輯《統(tǒng)計學(xué)習(xí)方法》的代碼復(fù)現(xiàn)專輯 AI基礎(chǔ)下載機(jī)器學(xué)習(xí)的數(shù)學(xué)基礎(chǔ)專輯溫州大學(xué)《機(jī)器學(xué)習(xí)課程》視頻 本站qq群851320808，加入微信群請掃碼：
總結(jié)
以上是生活随笔為你收集整理的【论文解读】GCN论文总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： win7系统5分钟就会自动注销的解决教程
- 下一篇： Win7性能信息和工具在哪打开