GNN教程：Weisfeiler-Leman算法！
一、引言
本文為GNN教程的第六篇文章 【Weisfeiler Leman算法】。前面的文章中，我們介紹了GNN的三個(gè)基本模型GCN、GraphSAGE、GAT，分析了經(jīng)典的GCN逐層傳播公式是如何由譜圖卷積推導(dǎo)而來的。GNN模型現(xiàn)在正處于學(xué)術(shù)研究的熱點(diǎn)話題，那么我們不經(jīng)想問，GNN模型到底有多強(qiáng)呢？
我們的目的是分析GNN的表達(dá)能力，我們需要一個(gè)模型作為衡量標(biāo)準(zhǔn)。比如說如果我們想衡量GBDT的分類能力的話，通常情況下我們會(huì)使用同樣的數(shù)據(jù)集，采用不同的分類模型如LR, RF, SVM等做對(duì)比。對(duì)于GNN模型，我們采用的對(duì)比模型叫做Weisfeiler-Leman，其常被用做圖同構(gòu)測(cè)試(Graph Isomorphism Test)，圖同構(gòu)測(cè)試即給定兩個(gè)圖，返回他們的拓?fù)浣Y(jié)構(gòu)是否相同。圖同構(gòu)問題是一個(gè)非常難的問題，目前為止還沒有多項(xiàng)式算法能夠解決它，而Weisfeiler-Leman算法是一個(gè)多項(xiàng)式算法在大多數(shù)case上能夠奏效，所以在這里我們用它來衡量GNN的表達(dá)能力，這篇博文詳細(xì)介紹了Weisfeiler-Leman算法，作為我們分析GNN表達(dá)能力的基礎(chǔ)。
二、Weisfeiler-Leman 算法介紹
2.1 動(dòng)機(jī)
Graph 的相似性問題是指判斷給定兩個(gè) Graph 是否同構(gòu)。如果兩個(gè)圖中對(duì)應(yīng)節(jié)點(diǎn)的特征信息（attribute）和結(jié)構(gòu)信息（structure）都相同，則稱這兩個(gè)圖同構(gòu)。因此我們需要一種高效的計(jì)算方法能夠?qū)⒌奶卣餍畔⒓敖Y(jié)構(gòu)位置信息(鄰居信息)隱射到一個(gè)數(shù)值，我們稱這個(gè)數(shù)值為節(jié)點(diǎn)的ID(Identification)。最后，兩個(gè)圖的相似度問題可以轉(zhuǎn)化為兩個(gè)圖節(jié)點(diǎn)集合ID的 Jaccard 相似度問題。
2.2 Weisfeiler-Leman 算法思路
一般地，圖中的每個(gè)節(jié)點(diǎn)都具有特征（attribute）和結(jié)構(gòu)（structure）兩種信息，需要從這兩方面入手，來計(jì)算幾點(diǎn)ID。很自然地，特征信息（attribute）即節(jié)點(diǎn)自帶的Embedding，而結(jié)構(gòu)信息可以通過節(jié)點(diǎn)的鄰居來刻畫，舉個(gè)例子，如果兩個(gè)節(jié)點(diǎn)Embedding相同，并且他們連接了Embedding完全相同的鄰居，我們是無法區(qū)分這兩個(gè)節(jié)點(diǎn)的，因此這兩個(gè)節(jié)點(diǎn)ID相同。由此，可以想到，我們可以通過 hashing 來高效判斷是否兩個(gè)節(jié)點(diǎn)ID一致。1維的Weisfeiler-Lehman正是這樣做的。如果設(shè)? 表示節(jié)點(diǎn)? 的特征信息（attribute），那么 Weisfeiler-Leman 算法的更新函數(shù)可表示為：
在上式中，表示鄰居Embedding的聚合函數(shù)，可以簡(jiǎn)單的將鄰居Embedding排序后拼接起來(concatenate)。看到這里，有的讀者可能產(chǎn)生了疑問，這個(gè)式子不是和之前GraphSAEG的跟新公式一樣嗎，那是不是意味著GraphSAGE具有和Weisfeiler-Leman算法相同的能力？確實(shí)這個(gè)式子在GraphSAGE中表示鄰居節(jié)點(diǎn)的聚合(比如求和、Pooling等方式)，而在GraphSAGE中是一個(gè)單層的感知機(jī)。這些差別實(shí)際上導(dǎo)致了GraphSAGE并沒有完全的Weisfeiler-Leman算法的能力，在后一篇博文中我們會(huì)詳細(xì)說明它。
下面我們通過一個(gè)形象的例子來說明Weisfeiler-Leman算法具體是如何操作的。
2.3 Weisfeiler-Leman 算法圖形舉例說明
給定兩個(gè)圖和，其中每個(gè)節(jié)點(diǎn)的Embedding為這個(gè)節(jié)點(diǎn)的標(biāo)簽（實(shí)際應(yīng)用中，有些時(shí)候我們并拿不到節(jié)點(diǎn)的標(biāo)簽，這時(shí)可以對(duì)節(jié)點(diǎn)都標(biāo)上一個(gè)相同的標(biāo)簽如"1"，這個(gè)時(shí)候我們將完全用節(jié)點(diǎn)位于圖中的結(jié)構(gòu)信息來區(qū)分節(jié)點(diǎn)，因?yàn)樗麄兊腅mbedding都相同）
如何比較? 和?的相似性問題呢？Weisfeiler-lehman 算法的思路如下：
對(duì)鄰居節(jié)點(diǎn)標(biāo)簽信息進(jìn)行聚合，以獲得一個(gè)帶標(biāo)簽的字符串（整理默認(rèn)采用升序排序的方法進(jìn)行排序）。
第一步的結(jié)果，這里需要注意，圖中利用逗號(hào)將兩部分進(jìn)行分開，第一部分是該節(jié)點(diǎn)的ID，第二部分是該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)ID按升序排序的結(jié)構(gòu)（eg：對(duì)于節(jié)點(diǎn) 5，他的鄰居節(jié)點(diǎn)為2，3，4，所以他的結(jié)果為"5,234"）
為了能夠生成一個(gè)一一對(duì)應(yīng)的字典，我們將每個(gè)節(jié)點(diǎn)的字符串hash處理后得到節(jié)點(diǎn)的新ID。
將哈希處理過的ID重新賦值給相應(yīng)的結(jié)點(diǎn)，以完成第一次迭代。
第一次迭代的結(jié)果為：。這樣即可以獲得圖中每個(gè)節(jié)點(diǎn)ID。接下去，可以采用 Jaccard 公式計(jì)算 和?的相似度。如果兩個(gè)圖同構(gòu)的話，在迭代過程中和將會(huì)相同。
至此Weisfeiler-Leman算法就介紹完了，作為下一篇博文的引文，我們簡(jiǎn)要得分析一下Weisfeiler-Leman算法和GCN逐層更新公式的關(guān)系。
三、Weisfeiler-Leman 算法與 GCN 間的轉(zhuǎn)換
GCN逐層更新公式為：
簡(jiǎn)單來說，GCN的逐層更新公式對(duì)Weisfeiler-Leman算法做了兩點(diǎn)近似：
用單層感知機(jī)近似函數(shù)，上式中即為單層感知機(jī)模型 用加權(quán)平均替代鄰居信息拼接，上式中表示節(jié)點(diǎn)的Embedding聚合到節(jié)點(diǎn)時(shí)需要進(jìn)行的歸一化因子
通過與 Weisfeiler-Lehman 算法的類比，我們可以理解即使是具有隨機(jī)權(quán)重的未經(jīng)訓(xùn)練的 GCN 模型也可以看做是圖中節(jié)點(diǎn)的強(qiáng)大特征提取器。
四、后話
即使GCN、GraphSAGE、GAT和Weifeiler-Leman算法如此之像，但正如我們分析的那樣，他們都做了一些近似，將近似為單層感知機(jī)會(huì)導(dǎo)致一部分的精度損失，因?yàn)閱螌痈兄獧C(jī)不是單射函數(shù)。拼接鄰居方式的近似引入了另一層精度損失，因?yàn)楸热缜蠛?，pooling等鄰居聚合方式可能作用于不同的鄰居集合下而得到相同的結(jié)果，所以不管是哪個(gè)模型，都沒有達(dá)到目前Weisfeiler-Leman算法在圖同構(gòu)問題上的能力。在下一篇博文中我們將會(huì)詳細(xì)分析這些近似方法帶來的損失，并給出如何解決這些問題。
參考資料
[1] SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS
[2] Weisfeiler-Lehman Graph Kernels
[3]《Graph learning》 圖傳播算法（下）
“為沉迷學(xué)習(xí)點(diǎn)贊↓