Weisfeiler-Lehman test及其擴展

• 引言
• • 圖同構(gòu)
  • WL test(Weisfeiler-Lehman test)
  • 一維Weisfeiler-Lehman test的一個例子
  • WL子樹核(WL subtree kernel)
  • 參考文獻

引言

在閱讀GNN相關(guān)論文時，經(jīng)常會碰到一個概念叫做WL test(Weisfeiler-Lehman test)，然而網(wǎng)上對這個概念的相關(guān)介紹卻很少。本人在查閱了一些資料后，將自己對這個概念的理解記錄下來，希望能和大家交流學習。由于本人學識有限，有不妥之處還請大家批評指正。

圖同構(gòu)

在介紹具體的Weisfeiler-Lehman test和Weisfeiler-Lehman算法之前，先對圖同構(gòu)(Graph Isomorphism)的概念進行簡單的回顧。圖同構(gòu)是圖論中用來描述兩個圖在拓撲結(jié)構(gòu)上是否完全等價的一個概念，如果兩個圖$G$和$H$完全等價，我們稱$G$和$H$是同構(gòu)的；否則，$G$和$H$是非同構(gòu)的。顯然，兩個圖$G$和$H$等價的必要條件是：$G$和$H$必須是同階的（$G$和$H$有相同的節(jié)點數(shù)目）。描述兩個圖同構(gòu)的嚴格數(shù)學定義為：兩個簡單圖$G$和$H$是同構(gòu)的，當且僅當存在一個將$G$的節(jié)點$1,...,n$映射到$H$的節(jié)點$1,...,n$的一一對應$\sigma$ ，使得$G$中任意兩個節(jié)點$v_i$和$v_j$相連接，當且僅當$H$中對應的兩個節(jié)點$\sigma (v_i)$和$\sigma (v_j)$相連接。如果$G$和$H$是有向圖，那么同構(gòu)的定義中還進一步要求對于$G$中任意兩個相連的節(jié)點$v_i$和$v_j$，邊$(i,j)$與它在$H$中對應的邊$(\sigma (v_i),\sigma (v_j))$方向相同。類似地可以定義兩個多重圖的同構(gòu)關(guān)系。
關(guān)于圖同構(gòu)的一個具體例子如下，為方便起見，兩圖中對應節(jié)點被染成了相同的顏色：

WL test(Weisfeiler-Lehman test)

判斷兩個圖是否為同構(gòu)的是一個非常困難的問題，目前還沒有一個可以在多項式時間內(nèi)求解的算法。除了一些極端的情況外，WL test是用來判斷兩個圖是否是同構(gòu)的一個有效的方法，它的一維形式“naive vertex refinement”類似于GNN中的鄰居信息聚合。具體操作分為兩步：
（1）聚合當前節(jié)點$v$及當前節(jié)點$v$鄰居節(jié)點的標簽；
（2）用一個哈希函數(shù)將（1）中的聚合結(jié)果映射為一個新的標簽并賦給節(jié)點$v$。
將上述兩個步驟迭代多次，判斷兩個圖$G$和$H$的節(jié)點標簽是否相同，若相同，則認為圖$G$和$H$是同構(gòu)的；否則，$G$和$H$是非同構(gòu)的。如果設$h_i$表示節(jié)點$v_i$的標簽，那么標簽的更新公式可以表示為：
$$h_l^{(t)}(v)=HASH(h_l^{(t?1)}(v),F\{h_l^{(t?1)}|u\in N(v)\})$$
其中，$t$表示迭代次數(shù)，$N(v)$表示圖中節(jié)點$v$的鄰居節(jié)點集合。

一維Weisfeiler-Lehman test的一個例子

給定有標簽的圖$G$和$G^{{}^{\prime }}$:

1.聚合兩圖中每個節(jié)點及其鄰居節(jié)點的標簽，當前節(jié)點自身的標簽和其鄰居節(jié)點標簽之間用逗號隔開，鄰居節(jié)點標簽按升序排列，聚合結(jié)果如下：

2.用定義在多重集上的哈希函數(shù)在1中結(jié)果的基礎上進行計算，得到每個節(jié)點的新的標簽，并將新標簽賦給相應節(jié)點：


如果兩個圖$G$和$H$是同構(gòu)的，則在某次迭代之后，這兩個圖對應節(jié)點的標簽會變成完全相同的。

WL子樹核(WL subtree kernel)

WL子樹核是Shervashidze等人于2011年基于WL test提出的概念，它用來度量兩個圖之間的相似性。子樹核用WL test迭代過程中不同節(jié)點標簽的數(shù)量來作為圖的特征向量。在WL test的第k次迭代過程中，一個節(jié)點的標簽表示以該節(jié)點為根，高為k的一個子樹結(jié)構(gòu)。聽起來有點太抽象了，下面用一個例子來說明：

上圖中左邊的部分表示原始的Graph，右邊表示在經(jīng)過兩次WL test迭代后，以節(jié)點2為根的高為2（這里高的2和兩次迭代相對應）的rooted subtree(根子樹)的結(jié)構(gòu)。除了上圖右邊所示的以節(jié)點2為根的高為2的根子樹結(jié)構(gòu)，以節(jié)點1，3，4為根的子樹結(jié)構(gòu)如下圖所示（涂黑的表示節(jié)點2）：

由于節(jié)點1和節(jié)點4對稱，所以節(jié)點1和節(jié)點4對應的子樹結(jié)構(gòu)是相同的，因此，兩次WL test迭代后形成的不同節(jié)點標簽數(shù)為3。

參考文獻

HOWPOWERFUL AREGRAPHNEURALNETWORKS?

GNN 教程：Weisfeiler-Leman 算法

圖同構(gòu)

總結(jié)

以上是生活随笔為你收集整理的Weisfeiler-Leman test与WL subtree kernel的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。