ワイスファイラー・レマングラフ同型性テスト

グラフ理論において、ワイスファイラー・レーマングラフ同型性テストは、 2つのグラフGとHの間に同型性が存在するかどうかを調べるヒューリスティックテストである。^[1]これは色の精製アルゴリズムの一般化であり、 1968年にワイスファイラーとレーマンによって初めて説明された。^{[2]元の定式化はグラフの正規形である}グラフ正規化に基づいているが、色の精製の精神と論理とのつながりに基づいた 組み合わせ的解釈もある。

このテストには複数のバージョン (例: k-WL および k-FWL) があり、文献ではさまざまな名前で呼ばれているため、混乱が生じやすいです。また、Andrey Leman はいくつかの古い記事で「Lehman」と表記されています。

色の改良のすべてのバリエーションは、2 つのグラフGとH を入力として受け取り、それらが異なるか「わかりません」という証明書を出力する片側ヒューリスティックです。つまり、ヒューリスティックがGとH を区別できる場合、それらは間違いなく異なりますが、逆方向は当てはまりません。WL テストのすべてのバリエーション (以下を参照) には、違いが検出されない非同型グラフがあります。これらのグラフは、1-WL/色の改良の 通常のグラフなど、高度に対称的なグラフです。

1 次元グラフ同型性テストは、本質的にはカラー リファインメント アルゴリズムと同じです(違いは非エッジに関係しており、異なる数のノードを持つグラフが非同型であることは明らかであるため、実用上は無関係です)。アルゴリズムは次のように進行します。

初期化すべてのノードは同じ色0で初期化されます

改良2つのノードu、vは、a)以前に異なる色であった場合、またはb) uとvが異なる数のc色の隣接ノード を持つような色cがある場合、異なる色になります。

終了2 つの連続する改良ステップによって誘導されるパーティションが同じである場合、アルゴリズムは終了します。

このアルゴリズムをグラフ同型性テストとして使用するには、2 つの入力グラフGとHに対してアルゴリズムを並列に実行します。つまり、分割時に色を使用して、ある色c (1 回の反復後) が「色 0 の隣接ノードがちょうど 5 つあるノード」を意味するようにします。実際には、これはGとHの非結合グラフに対して色の調整を実行することによって実現されます。次に、両方のグラフの色のヒストグラム (色の調整が安定した後のノードの数を数える) を確認し、それらが異なる場合は、両方のグラフが同型ではないことの証明となります。

このアルゴリズムは、最大でラウンド後に終了します。ここで、は入力グラフのノード数です。これは、各改良ステップで 1 つのパーティションを分割する必要があり、これは最大で各ノードが独自の色を持つまで発生するためです。この反復回数が必要なグラフもありますが、実際には終了までのラウンド数は非常に少ない傾向があります (<10)。 ${\displaystyle n-1}$${\displaystyle n}$

各ステップでのパーティションの改良は、各ノードのラベルと最も近いノードのラベルを処理することによって行われます。したがって、WLtest は、グラフ ニューラル ネットワークにも接続されるメッセージ パッシング アルゴリズムとして見ることができます。

ここで、前述の WL アルゴリズムの 2 つのバリエーションが登場します。k 次元 Weisfeiler-Leman (k-WL) と k 次元 folklore Weisfeiler-Leman アルゴリズム (k-FWL) はどちらも、個々のノードではなく k タプルを操作する上記の 1-WL の拡張です。一見すると、それらの違いは無害に見えますが、k-WL と (k-1)-FWL (k>2 の場合) は同じグラフのペアを区別することが示されています。

入力: グラフ G = (V,E)
# 初期化
${\displaystyle c^{0}({\bar {v}})={\text{ハッシュ}}({\text{type}}({\bar {v}}))}$すべてについてすべてについて（両方の色付けが の同一の分割を誘導する）
まで繰り返す戻る${\displaystyle {\bar {v}}\in V^{k}}$

   ${\displaystyle c_{i}^{\ell }({\bar {v}})=\{\!\{c^{\ell -1}({\bar {w}}):{\bar {w}}\in {\mathcal {N}}_{i}({\bar {v}})\}\!\}}$${\displaystyle {\bar {v}}\in V^{k},i\in [k]}$
   ${\displaystyle c^{\ell }({\bar {v}})={\text{Hash}}(c^{\ell -1}({\bar {v}}),c_{1}^{\ell }({\bar {v}}),\dots ,c_{k}^{\ell }({\bar {v}}))}$
 ${\displaystyle c^{\ell }\equiv c^{\ell -1}}$${\displaystyle V^{k}}$ ${\displaystyle c^{\ell }}$

ここで、 k タプルの近傍は、 の i 番目の位置を交換することによって到達可能なすべての k タプルの集合によって与えられます。 タプルの アトミック タイプは、のすべてのノード ペア間のエッジ情報をエンコードします。たとえば、2 タプルには 2 つのアトミック タイプしかありません。つまり、2 つのノードがエッジを共有するか、共有しないかのどちらかです。グラフに複数の (異なる) エッジ関係または追加のノード機能がある場合、それらのメンバーシップも で表されることに注意してください。 ${\displaystyle {\mathcal {N}}_{i}({\bar {v}})}$${\displaystyle {\bar {v}}}$${\displaystyle {\bar {v}}}$${\displaystyle {\mathcal {N}}_{i}({\bar {v}})=\{(v_{1},\dots ,v_{i-1},w,v_{i+1},\dots ,v_{k}):w\in V\}}$${\displaystyle {\text{type}}({\bar {v}})}$${\displaystyle {\bar {v}}}$${\displaystyle {\text{type}}({\bar {v}})}$

k-WL の重要なアイデアは、近傍の概念を k タプルに拡張し、結果として得られるグラフに対して色の改良を効果的に実行することです。

入力: グラフ G = (V,E)
# 初期化
${\displaystyle c^{0}({\bar {v}})={\text{Hash}}({\text{type}}({\bar {v}})}$) すべてについて すべてについて繰り返し、(両方の色付けが の同一の分割を誘導する)
戻る${\displaystyle {\bar {v}}\in V^{k}}$

  ${\displaystyle c_{w}^{\ell }({\bar {v}})={\big (}c^{\ell -1}({\bar {v}}[1]\!\!\leftarrow \!w),\dots ,c^{\ell -1}({\bar {v}}[k]\!\!\leftarrow \!w){\big )}}$${\displaystyle {\bar {v}}\in V^{k},w\in V}$
  ${\displaystyle c^{\ell }({\bar {v}})={\text{Hash}}{\big (}c^{\ell -1}({\bar {v}}),\{\!\{c_{w}^{\ell }({\bar {v}}):w\in V\}\!\}{\big )}}$
 ${\displaystyle c^{\ell }\equiv c^{\ell -1}}$${\displaystyle V^{k}}$ ${\displaystyle c^{\ell }}$

ここでは、i 番目の位置が に交換されたタプルを示します。 ${\displaystyle {\bar {v}}[i]\!\!\leftarrow \!w}$${\displaystyle {\bar {v}}}$${\displaystyle w}$

k-WL と k-FWL の間には大きな違いが 1 つあることに注意してください。k-FWL は、単一のノード w が k タプルの任意の位置に配置された場合に何が起こるかをチェックし (その後、これらの k タプルの多重集合を計算します)、k-WL は元の k タプルの i 番目のコンポーネントのみを変更したときに得られる多重集合を調べます。次に、新しい色を計算するハッシュでそれらの多重集合をすべて使用します。

k-FWL と (k+1)-WL は同等であることが (論理との関連を通じてのみ) 示されます ( の場合)。両方のアルゴリズムは k に対して指数関数的にスケーリングするため (両方ともすべての k タプルを反復処理します)、k-FWL を使用する方が同等の (k+1)-WL を使用するよりもはるかに効率的です。 ${\displaystyle k\geq 2}$

# アルゴリズム WLpairs 
# 入力: 同型性をテストする 2 つのグラフ G と H 
# 出力: G と H の証明書とそれらが一致するかどうか
U  =  combineTwo ( G ,  H ) 
glabels  =  initializeLabels ( U )   # すべてのノードが同じラベル 0 を取得する辞書
labels  =  {}   # ノードとその近傍のラベルの文字列から整数への変換を提供する辞書
newLabel  =  1 
done  =  False 
while  not ( done ): 
    glabelsNew  =  {}   # 次のステップのラベルの辞書をセットアップします
    for  node  in  U : 
        label  =  str ( glabels [ node ])  +  str ([ glabels [ x ]  for  x  in  neighbors  of  node ] . sort ()) 
        if  not ( label  in  labels ):   # ノードとその近傍からのラベルの組み合わせが初めて検出されます
            labels [ label ]  =  newLabel   # ラベルの文字列を省略ラベルとして新しい番号に割り当てます
            newLabel  +=  1   # 新しい省略ラベルを割り当てるためのカウンターを増やす
        glabelsNew [ node ]  =  labels [ label ] 
    if  ( glabels内の異なるラベルの数 ) == ( glabelsNew内の異なるラベルの数): done = True else : glabels = glabelsNew . copy () certificateG = UのG部分のソートされたラベルからのGの証明書certificateH =ソートされたラベルからのHの証明書           
          
    
          
             
          UのH 部分if certificateG == certificateH : test = True else : test = False​​​  
   
      

      

ここに、最初の例の説明を含む 実際のPythonコードを示します。

g5_00  =  { 0 :  { 1 ,  2 ,  4 },  1 :  { 0 ,  2 },  2 :  { 0 ,  1 ,  3 },  3 :  { 2 ,  4 },  4 :  { 0 ,  3 }} 
g5_01  =  { 0 :  { 3 ,  4 },  1 :  { 2 ,  3 ,  4 },  2 :  { 1 ,  3 },  3 :  { 0 ,  1 ,  2 },  4 :  { 0 ,  1 }} 
g5_02  =  { 0 :  { 1 ,  2 ,  4 },  1 :  { 0 ,  3 },  2 :  { 0 ,  3 },  3 :  { 1 ,  2 ,  4 },  4 :  { 0 ,  3 }}


def  combineTwo ( g1 ,  g2 ) : 
    g  =  { 
    } n  =  len ( g1 ) 
    for  node  in  g1 : 
        s  =  set ( ) 
        for  neighbor  in  g1 [ node ] 
            : s.add ( neighbor ) g [ node ] = s.copy ( ) for node in g2 : s = set ( ) for neighbor in g2 [ node ] : s.add ( neighbor + n ) g [ node + n ] = s.copy ( ) return g
          
       
          
           
              
            
     


g  =  combineTwo ( g5_00 ,  g5_02 ) 
labels  =  {} 
glabels  =  {} 
for  i  in  range ( len ( g )): 
    glabels [ i ]  =  0 
glabelsCount  =  1 
newlabel  =  1

done  =  False 、
そうでない場合 ( done ): glabelsNew = {} glabelsCountNew = 0 for node in g : label = str ( glabels [ node ]) s2 = [] for neighbor in g [ node ]: s2 . append ( glabels [ neighbor ]) s2 . sort () for i in range ( len ( s2 )): label += "_" + str ( s2 [ i ]) if not ( label in labels ): labels [ label ] = newlabel newlabel += 1 glabelsCountNew += 1 glabelsNew [ node ] = labels [ label ] if glabelsCount == glabelsCountNew : done = True else : glabelsCount = glabelsCountNew glabels = glabelsNew . copy () print ( glabels ) 
      
      
       
          
          
           
            
        
           
                
            
              
              
              
          
       
          
    
          
          


g0labels  =  [] 
iが範囲内( len ( g0 ) )の場合:  g0labels . append ( glabels [ i ]) g0labels . sort () certificate0 = "" iが範囲内( len ( g0 ) ) の場合: certificate0 += str ( g0labels [ i ]) + "_" g1labels = [] iが範囲内( len ( g1 ) )の場合: g1labels . append ( glabels [ i + len ( g0 )]) g1labels . sort () certificate1 = "" i が範囲内( len ( g1 ) )の場合: certificate1 += str ( g1labels [ i ]) + "_"  
    

  
   
        
  
   
      

  
   
        

if  certificate0  ==  certificate1 : 
    test  =  True 
else : 
    test  =  False 
print ( "証明書 0:" ,  certificate0 ) 
print ( "証明書 1:" ,  certificate1 ) 
print ( "テスト結果:" ,  test )

最初の3つの例は、次数5のグラフの例です^。[3]

WLpair は「G0」と「G1」で 3 ラウンドを実行します。証明書が一致するため、テストは成功します。

WLpair は 'G0' と 'G2' で 4 ラウンドかかります。証明書が一致しないため、テストは失敗します。実際、'G0' には長さ 5 のサイクルがありますが、'G2' にはサイクルがないため、'G0' と 'G2' は同型ではありません。

WLpair は 'G1' と 'G2' で 4 ラウンドかかります。証明書が一致しないため、テストは失敗します。前の 2 つのインスタンスから、すでにわかっています。 ${\displaystyle G_{1}\cong G_{0}\not \cong G_{2}}$

確かに、G0とG1は同型です。同型はどれも、コンポーネント、つまりラベルを尊重しなければなりません。これは、グラフ同型問題のカーネル化に使用できます。ラベルを尊重する頂点のマップのすべてが同型になるわけではないことに注意してください。とをそれぞれで与えられるマップとします。が同型ではないのに対し、は同型を構成します。 ${\displaystyle \varphi :G_{0}\rightarrow G_{1}}$${\displaystyle \psi :G_{0}\rightarrow G_{1}}$${\displaystyle \varphi (a)=D,\varphi (b)=C,\varphi (c)=B,\varphi (d)=E,\varphi (e)=A}$${\displaystyle \psi (a)=B,\psi (b)=C,\psi (c)=D,\psi (d)=E,\psi (e)=A}$${\displaystyle \varphi }$${\displaystyle \psi }$

WLpair をG0とG2に適用すると、G0に対して証明書7_7_8_9_9が取得されます。しかし、同型のG1 は、 WLpair をG1とG2に適用すると、証明書7_7_8_8_9を取得します。これは、ノードでの WLtest の実行順序に依存するラベルに関する現象を示しています。ラベルの一意性を維持する別の再ラベル付け方法を見つけるか (これはかなり技術的になります)、再ラベル付けを完全にスキップしてラベル文字列を保持するか (証明書の長さが大幅に増加します)、バリアント WLpair で行ったように、テストされた 2 つのグラフの和集合に WLtest を適用します。G1 と G2 に対して WLtest を個別に実行すると異なる証明書を取得できますが、WLpair では同じ証明書を取得することに注意してください。

次の例は、正則グラフに関するものです。WLtest は同じ次数の正則グラフを区別できませんが、^{[4] : 31} WLpair は同じ次数であっても次数が異なる正則グラフを区別できます。実際、WLtest は、次数 8 のこれらの例に見られるように、1 ラウンド後に終了します。これらの例はすべて 3 正則ですが、最後の 1 つは 5 正則です。

4 つのグラフはすべて、ペアワイズ非同型です。G8_00には 2 つの接続コンポーネントがありますが、他にはありません。G8_03は5 正則ですが、その他は 3 正則です。G8_01には 3 サイクルがありませんが、G8_02 には3 サイクルがあります。

WLpairが区別できない2つの非同型グラフの別の例を次に示します。^[5]

ワイスファイラー・レマン検定の理論はグラフニューラルネットワークに適用されます。

非線形データの機械学習では、カーネルを使用してデータを高次元の特徴空間で表現し、その後にサポートベクターマシンなどの線形手法を適用します。グラフとして表現されたデータは、多くの場合非線形に動作します。グラフカーネルは、そのようなグラフベースの非線形データを前処理して、後続の学習方法を簡素化する方法です。このようなグラフカーネルは、ワイスファイラー・レマン検定を部分的に実行し、その時点までに構築されたパーティションを処理することで構築できます。^[6]これらのワイスファイラー・レマングラフカーネルは、発表後の10年間でかなりの研究を集めました。^[1]これらは、GraKeLなどのグラフカーネル専用のライブラリにも実装されています。^[7]

グラフカーネルなどの機械学習のコンテキストにおける人工ニューラルネットワークのカーネルは、複雑性理論の分野におけるNP困難問題の例などの高複雑性の問題を解決するための計算コストを削減するためのヒューリスティックアルゴリズムに適用されるカーネルと混同しないように注意してください。前述のように、ワイスファイラー・レマン検定は後者のコンテキストにも適用できます。

• グラフ同型性
• グラフニューラルネットワーク