Weisfeiler-Lehman 算法

• Weisfeiler-Lehman(WL)算法
• • The Weisfeiler-Lehman Test of Isomorphism
  • The General Weisfeiler-Lehman Kernels
  • • 1.The Weisfeiler-Lehman Kernel Framework
    • 2.The Weisfeiler-Lehman Subtree Kernel
    • • 多圖上計算The Weisfeiler-Lehman Subtree Kernel
      • THE RAMON-GARTNER SUBTREE KERNEL
    • 3.The Weisfeiler-Lehman Edge Kernel
    • 4.The Weisfeiler-Lehman Shortest Path Kernel

Weisfeiler-Lehman(WL)算法

The Weisfeiler-Lehman Test of Isomorphism

• 圖核使用來自$Weisfeiler?Lehman$同構檢驗的概念，更具體地講是其一維變體，也稱為“樸素頂點修飾”
• 該算法的關鍵思想是通過對相鄰節點的節點標簽排序后的集合來擴展節點標簽，并將這些擴展后的標簽壓縮為新的短標簽
• $alphabet$ $\Sigma$必須足夠大才能使$f$具內射性。 對于兩個圖，$|\Sigma |=2n$個滿足條件。

• $（a）$網絡中每個節點有一個$label$，如圖中的彩色的$1，2，3，4，5$
• $（b）$標簽擴展：做一階廣度優先搜索，即只遍歷自己的鄰居。比如在圖$（a）$網絡$G$中原$(5)$號節點，變成$(5,234)$，這是因為原$（5）$節點的一階鄰居有$2，3和4$
• $（c）$標簽壓縮：僅僅只是把擴展標簽映射成一個新標簽，如 $5,234=>13$
• $（d）$壓縮標簽替換擴展標簽
• $（e）$數標簽：比如在$G$網絡中，含有$1$號標簽$2$個，那么第一個數字就是$2$。這些標簽的個數作為整個網絡的新特征

算法：
假設要測試同構的兩張圖為$G$和$G’$，那么在結點$v$的第$i$次迭代里，算法都分別做了四步處理：標簽復合集定義、復合集排序、標簽壓縮和重標簽

• $WLtest$的復雜度是$O(hm)$，其中h為$iteration$次數，$m$是一次$iteration$里$multiset$的個數

一維的$Weisfeiler?Lehman$如下所示：


穩定后，統計兩張圖的$label$的分布，如果分布相同，則一般認為兩張圖時同構的。

注意：我們可以發現，$WLtest$方法的步驟和$GNNs$具有異曲同工之妙，都是通過不斷聚合鄰居信息，得到節點的新表示，這也是為什么$Kipf$在$2017$年$GCN$的論文中單獨討論和$GCN$和$WLtest$關系的原因。而正是這種統一性，才使得本文能以 $WLtest$ 為基礎來分析$GNNs$框架。

The General Weisfeiler-Lehman Kernels

1.The Weisfeiler-Lehman Kernel Framework

• $Weisfeiler?Lehmanalgorithm$ 對圖$G$和$G^{\prime }$的結點進行重標簽時，只有當兩個結點$v$和$v^{\prime }$有相同的標簽復合集，它們生成的新標簽才一樣。
• 因此，我們可以認為對所有圖進行標簽壓縮和重標簽時，標簽映射函數$f$都是一樣的，定義為$r((V,E,l_i))=(V,E,l_{(i+1)})$，其中，$V$是圖$G$的結點集，$E$是圖$G$的邊集，$l_i$和$l_{(i+1)}$分別是$Weisfeiler?Lehmanalgorithm$ 在第$i$次和第$i+1$次迭代時生成的標簽集。
  
  $G_0$是原始圖，$G_1=r(G_0)$是第一次重新貼標產生的圖，依此類推.
  
  
  性質
• 1.半正定矩陣的行列式是非負的。
• 2.兩個半正定矩陣的和是半正定的。
• 3.$G_i=r?G_{(i?1)}=(r^2)?G_{(i?2)}=....=(r^i)?G_0=(r^i)?G$
  證明
  
  
  **請注意，**可以將非負實權重${\alpha }_i$放在$k(G_i，G_i^{\prime })，i=0,1,...,h$上，以獲得更一般的$Weisfeiler?Lehman$核定義：
  
  

2.The Weisfeiler-Lehman Subtree Kernel

$c_i(G，{\sigma }_{ij})$是圖形$G$中字母${\sigma }_{ij}$的出現次數。

也就是說，Weisfeiler-Lehman子樹內核在兩個圖中計數共同的原始標簽和壓縮標簽

• 假設基本內核$k$是一個函數，用于計算兩個圖中的匹配節點標簽對：

多圖上計算The Weisfeiler-Lehman Subtree Kernel

算法：

• 在$N$個圖和$h$次迭代的情況下，$\Sigma$大小為$Nn(h+1)$。
  
  
  舉例：
  
  
  

THE RAMON-GARTNER SUBTREE KERNEL

具有子樹高度$h$的$Ramon?Gartner$子樹內核通過迭代比較它們的鄰域來比較圖$G=(V,E,l)$和$G_0=(V_0,E_0,l)$中的所有節點對：



$M(v，v^{\prime })$是$v$和$v^{\prime }$鄰域的子集的精確匹配集合。$M(v，v^{\prime })$的每個元素$R$是來自$v\in V$和$v_0\in V_0$的鄰域的一組節點對，因此每對中的節點具有相同的標記，并且不包含多于一對的節點。 因此，從直觀上講，$k_{RG}$迭代地考慮來自$G$的節點$v$和來自$G_0$的$v_0$的鄰居之間兩個相同標記節點的所有匹配$M(v，v^{\prime })$。 使參數${\lambda }_v$和${\lambda }_{v^{\prime }}$等于單個參數λ會導致每個模式加權$\lambda$，并提高到模式中節點數的冪。

LINK TO THE WEISFEILER-LEHMAN SUBTREE KERNEL

3.The Weisfeiler-Lehman Edge Kernel

$TheWeisfeiler?Lehmanedgekernel$ 是$theWeisfeiler?Lehmankernelframework$的另一個實例。 對于具有未加權邊的圖，我們考慮對兩個圖中具有相同標記的端點（事件節點）的匹配邊對進行計數的基本內核。 換句話說，基本內核定義為

其中${\phi }_E(G)$是對$(a，b)$，$a,b\in \Sigma$的出現次數的向量，它們表示$G$中邊的端點的有序標簽. $(a，b)$和$(a_0，b_0)$分別表示邊$e$和$e_0$的端點的有序標簽，以及$Dirackernel$的$\delta ，k_E$可以等效地表示為${\sum }_{e\in E}{\sum }_{e_0\in E^{\prime }}\delta (a，a_0)\delta (b，b_0)$。如果邊緣通過分配權重的函數$w$加權，則基本核$k_E$可以定義為${\sum }_{e\in E}{\sum }_{e_0\in E^{\prime }}\delta (a，a_0)\delta (b，b_0)k_w(w(e)，w((e_0))$ ,其中$k_w$是比較邊緣權重的內核。

4.The Weisfeiler-Lehman Shortest Path Kernel

在這里，我們使用節點標記的最短路徑內核作為基礎內核。

Weisfeiler-Lehman Graph Kernels

https://github.com/BorgwardtLab/GraphKernels

https://static.aminer.cn/misc/pdf/20190419.pdf
https://github.com/ysig/GraKeL

總結

以上是生活随笔為你收集整理的Weisfeiler-Lehman(WL)算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。