2017年2月26日日曜日

Canonical Labelling by Nauty

はじめに


 先のページで、論文「Learning Convolutional Neural Networks for Graphs」の紹介を行った。その中で、Canonical Labellingを行う際に、Nautyというツール(ライブラリ)を用いていた。ここでは、Nautyの提供するC言語インタフェースを用いて、Canonical Labellingを行う手順を示す。

Nautyのインストール


 ここからソースをダウンロードする。コンパイル手順はソースに含まれるREADMEに書いてある。 上の処理が終わると、ディレクトリnauty26r7の直下に実行ファイル、オブジェクトファイル、ソースファイル、ユーザガイドが混在する状態になる。上の例では、--prefixを指定してあるが、ディレクトリに含まれるmakefileにはinstall命令が記述されていない(後で気づいた)。make installできないので、実行ファイル等を手で適当な場所にコピーする必要がある。ユーザガイドはオンラインでも見ることができる。

開発環境

  1. Xcode Version 8.2.1 (C++ Language Dialect: C++14)
  2. boost library
  3. cpplinq

サンプル1


 最初に、ユーザガイドのp4の冒頭にある下図を取り上げる。
図1
図1の上段2つのグラフは同型(isomorphic)であるが、頂点の隣接関係は異なっている。これらを2つをcanonizeすると、頂点の隣接関係の等しい2つのグラフを得ることができる(図1の下段)。2つの同型のグラフは、canonical labellingにより、頂点の隣接関係の等しいグラフになる。言い換えれば、canonical labellingを用いれば、2つのグラフが同型であるか否かを判定することができるのである。この判定を、NautyのC言語インタフェースを用いて実装したものを以下に示す。 上の出力を検討してみる。最初に、図1左側のグラフについて(図2)。
図2
108行目でdensenautyを呼び出した後、配列labに以下の値が設定される。 これは以下を表現している。 すなわち、図2の上段の元のグラフの頂点番号3は0に、6は1に置き換えることを意味する(他の頂点についても同様)。配列relabelling1は分かり易いように表現方法を変えただけの値である。 これは を意味する。すなわち、元グラフの頂点番号0を6に、1を5に置き換える(他の頂点も同様)。図1右側の2つのグラフについても同じように解釈すれば良い。結局、図1下段の2つのグラフが得られたことになる(図3)。
図3
これら2つのグラフを見ると、頂点{5,1,4,0}の位置は異なるが、全頂点の隣接関係は全く同じである。これを確認しているのが148行目である。

サンプル2


 次にユーザガイドのp5冒頭にある図を考える(図4)。
図4
グラフの形はサンプル1と同じであるが、partitioning(coloring)が導入されている。頂点が色分けされている場合、同じ色に属する頂点についてcanonical labellingが実行される(サンプル1は全ての頂点が同じ色を持つと解釈される)。実装例は以下の通り。 9行目で色分けを行うことをNautyに伝えている。実際に色分けを行なっているのは、31,32行目と58,59行目である。Nautyでは色分けを2つの配列lab,ptnを用いて表現する。図4左側の2つのグラフの色分けは以下の2つの配列で記述される。 labには頂点番号が任意の順番で格納される。この格納順にptnで色の分離位置を表現する。0の場合そこが色の境界である。0以外の値のとき同じ色である。すなわち、{0,2}と{1,3,4,5,6,7}に色分けされることになる。図4では前者は黒、後者は白で描かれている。図4右側の2つのグラフの色分け(58,59行目)も同様である。densenautyの呼び出し(39,66行目)の後のlabにはcanonize後のラベルが格納され、この解釈方法はサンプル1と同じである。canonize後に得るグラフは図4の下段である。これら2つのグラフの頂点の隣接関係は異なる。これを確認しているのが80行目である。最後に、headerファイルとmain関数を示す。

論文「Learning Convolutional Neural Networks for Graphs」への適用


 論文「Learning Convolutional Neural Networks for Graphs」では、最初に、betweenness centralityやWLアルゴリズムにより頂点のラベル付けを行なった。そして、同じラベルを持つ頂点が存在する場合、この縮退を解くためにNautyを用いている。同じラベル値を持つ頂点を同じ色を持つ頂点と解釈し、Nautyを適用すれば良いだろう。 

0 件のコメント:

コメントを投稿