グラフ同型に関する代表元のグラフを列挙するZDDの構築について

グラフ同型に関する代表元のグラフを列挙する

ZDD

の構築について

ZDD Construction for a Set of Representatives

on Graph Isomorphism

大澤賢悟

1

_中畑裕

1

_湊真一

1∗

Kengo Osawa

1

_{Yu Nakahata}

1

_{Shin-ichi Minato}

1 1

_{京都大学 大学院 情報学研究科}

1

_{Graduate School of Informatics, Kyoto University}

Abstract: A catalog of representatives on graph isomorphism is sometimes useful for checking

graph properties. “nauty” and other software tools are used for generating those catalogs. On the other hand, ZDDs (Zero-suppressed BDDs) are used for efficiently representing and manipulating various sets of graphs. In this paper, we proposed a method of constructing a ZDD for a set of representatives on graph isomorphism, and report some experimental results on our method.

1

はじめに

グラフ同型判定問題とは，与えられた 2 つのグラフ が同型であるか否かを判定する問題である．この問題 はクラス NP に属することは判明しているが，クラス P に属するか，NP 完全に属するかは判明していない． 実用的な例題では多くの場合，比較的短時間で判定で きることが経験的に知られているが，最悪の場合での 計算量は未解決である [1]． グラフの性質検査の際にグラフ同型に関する代表元 グラフのみを列挙したカタログが用いられているが [2]， このためにグラフ同型判定問題は重要な意味を持つ．グ ラフ同型判定問題の難しさのためにこのようなカタロ グの作成が簡単には行えないためである．また，調査 のためにはカタログの扱いやすさや扱えるグラフの種 類の多さは重要な点であると考えられるが，同じく判 定問題の難しさから生成できるカタログの種類も限ら れてしまう．現在は，グラフの同型性判定やグラフ集合 から同型なグラフを除去する際には nauty などのソフ トウェアがよく用いられており，小規模な例題に限れ ば代表元グラフのカタログ生成が現実的に可能である． 一方，ZDD は大規模な組合せ集合を圧縮して効率良 く表現可能なデータ構造であり，その特徴として圧縮 した表現のまま高速に集合演算が行える点が挙げられ る．そのため，ある性質を満たすグラフ集合を ZDD で 表現すれば，代表元グラフの集合を表現した ZDD との 共通集合を求める演算によって，ある性質を満たす代 ∗_{連絡先：京都大学 大学院 情報学研究科}        〒 606-8501 京都市左京区吉田本町        E-mail:[email protected] 表元グラフのカタログを表現する ZDD を作成するこ とが容易に行える．また，代表元グラフの集合を表現 した ZDD は再利用可能であり，組み合わせる ZDD が 変わっても同じように同型グラフの除去が可能である． そこで本稿では，グラフ同型に関する代表元のグラ フを列挙する際に ZDD を用いる手法を提案する．ま た，手法を変化させることによる ZDD サイズの削減 についても検討する．

2

準備

本稿で扱うグラフは重みなしの無向グラフのみとし， 自己閉路と多重辺は許さないとする．グラフ G = (V, E) を，頂点集合 V と辺集合 E ={{u, v} | u, v ∈ V ∧ u ̸= v} の組で表すとする．また，グラフ G の頂点集合，辺 集合をそれぞれ V (G)，E(G) で表し，グラフ G の頂 点の数，辺の数をそれぞれ_{|V (G)|，|E(G)| で表すと} する．

2.1

グラフの同型性

グラフの同型性は以下で定義される [3]． 定義 (グラフの同型性). 2 つのグラフ G = (V, E) と G′ = (V′, E′) に対し，任意の v1, v2 ∈ V について {v1, v2} ∈ E ⇔ {f(v1), f (v2)} ∈ E′ となる全単射写像 f : V → V′ が存在するとき，G と G′ は同型であると いう． 人工知能学会研究会資料 SIG-FPAI-B901-05

この定義における全単射写像 f は頂点の置換である とも言える．この置換写像によってグラフ集合におけ る同値類が構成され，その中の一つを代表元として選 ぶことができる．このようにして選んだグラフを代表 元グラフと呼ぶことにする．本稿で提案する手法では， 代表元グラフの集合を表現する ZDD を構築する際に， 代表元グラフの集合の要素であるグラフに対して頂点 番号の置換を行うが，これによる変換先は元のグラフ と同型なグラフであり，かつ他の要素とは同型でない ため，処理後のグラフ集合も代表元グラフの集合であ る，という性質が保たれる．

2.2

グラフ同型性判定ソフト nauty

nauty は McKey らにより開発されたグラフ同型性 判定ソフトウェアで，近年広く使われている [4]．nauty は各グラフに対してカノニカルラベルと呼ばれる特徴 量を生成し，その比較によって同型性判定を行う．同 型なグラフに対しては同じカノニカルラベルが生成さ れる． nauty を用いて処理を行うツール群として gtools が 提供されており，その中で geng というツールが提供 されている．geng は，指定された規模の全てのグラフ について，逐次，カノニカルラベルの値を計算し，同 じカノニカルラベルの値が出現していなければ代表元 グラフとして出力し，その値を内部のテーブルに登録 する．これにより，頂点数や最大次数などの条件指定 のもと，それらを満たす代表元グラフのみを列挙する ことができる． 本研究ではこの geng を用いて代表元グラフの集合 を生成する．

2.3

ZDD

ZDD(Zero-suppressed Binary Decision Diagram) は， 湊によって 1993 年に提案された，組合せ集合を効率的 に圧縮して表現できるデータ構造である [5]．ZDD の 各節点には変数が割り当てられており，ある変数の組 合せについて節点に割り当てられた変数が含まれるか どうかをもとに 0-枝と 1-枝を辿ることで，その要素が ZDD の表現する組合せ集合に含まれるかどうかを判定 できる． ZDD は二分決定木に対して，等価な節点の共有と， 1-枝が空集合を指す節点の削除という二つの簡約規則 を適用することで圧縮を行っている．これらのイメー ジを図 1 と図 2 に示す．また，これらの規則は疎な組合 せ集合に対して特に効果的である． ZDD の節点に対 応する変数の順序はこの簡約規則に影響し，同じ組合 1 3 2 1 0 0 0 0 1 1 1 1 1 3 2 0 0 0 1 1 1 図 1: 等価な節点の共有 1 2 0 0 1 1

0

2 0 1 図 2: 1-枝が空集合を指す節点の削除 せ集合を表現する ZDD であっても，その変数順序に よって ZDD 全体の節点数は大きく異なる場合がある． ZDD の特徴として，組合せ集合同士の集合演算，組 合せ集合に含まれる要素数の数え上げ，組合せ集合の要 素のランダムサンプリングなどを容易に行える点が挙 げられる．特に ZDD 同士の集合演算については，ZDD が表現する組合せ集合における集合演算と対応し，こ れらの演算を ZDD のデータ構造を保ったまま実行で きるという特徴がある． 今回 ZDD を用いてグラフ同型に関する代表元の列 挙を行う動機はこの集合演算にあり，ある性質を満た すグラフの集合を表現する ZDD と，本研究で生成す る代表元グラフ集合を表す ZDD との共通集合の演算 を実行することで，特定の性質を満たすグラフ集合に 対してグラフ同型に関する代表元のみを取り出せるよ うになる．また ZDD で圧縮表現することにより，よ り大規模な例題を扱えることや，数え上げやランダム サンプリングが高速化できることが期待される． なお，本研究では ZDD を扱うために Graphillion[6] と呼ぶ Python ライブラリを用いている．

3

代表元のみを列挙する

ZDD

の構

築法

本節では，グラフ同型に関する代表元のみを列挙し たグラフ集合（以下「代表元グラフ集合」と呼ぶ）を ZDD で表現する手法について提案する． まず本手法における方針を説明する．本手法では，代 表元グラフ集合に含まれる要素を一つずつ ZDD に変

換し，これらを ZDD の特徴である集合演算，特にこ こでは和集合を求める演算を行うことにより，求める ZDD を構築する． このとき用いる代表元グラフ集合については，2 節 で説明した nauty を用いたツール geng により生成す る．生成する代表元グラフ集合は，n = 4, . . . , 8 にお ける各頂点数 n ごとの，多重辺や自己ループを含まな い連結グラフのみを含むものとする．geng によって生 成されるグラフ集合のデータでは，各グラフは頂点番 号 2 つの組で表現される辺のリストにより表現されて いる．例えば，3-完全グラフは「0 1 0 2 1 2」と 表現される． また，代表元グラフから ZDD への変換ならびに ZDD における集合演算の実行には Graphillion を用いている． Graphillion では，グラフは geng が生成するデータと同 じく頂点番号の組のリストによって，グラフ集合はグラ フのリストによって与えられる．本手法で Graphillion が生成する ZDD では，節点に対応する変数は代表元 グラフにおける辺の有無を表しており，この変数の順 序は辺に対応する頂点番号の組の辞書順により定めて いる．ただし各グラフにおける辺の有無は完全グラフ を基準として考える．これにより，頂点番号の置換に より代表元グラフ集合の要素における辺の有無が変化 し，最終的な ZDD の節点数が変化することが期待さ れる． 以上の前提の下，三つの手法を提案する．

3.1

単純構築法

本小節での提案手法は，geng によって出力された代 表元グラフの頂点番号付けをそのまま用いて ZDD を 構築する手法である． 具体的には，次の手順によりグラフ集合を表現する ZDD を構築する： 1. 代表元グラフ集合 Grを geng を用いて生成する． 2. 求めるグラフ集合 fi ははじめ，空集合を表す ZDD とする． 3. Gr から要素を一つ選び，そのまま ZDD に変換 する．この ZDD を fr とする． 4. fiと frの和集合演算を Graphillion を用いて行 い，その結果を新たな fi とする． 5. Gr の全ての要素に対して一回ずつ手順 3. と 4. を行い，最後に出力された fi が求める ZDD と なる． 構築のイメージは図 3 のようになる．

∪

∪

図 3: 単純構築法のイメージ図. ここで，和集合演算については，Graphillion 内でグ ラフ集合を表す変数を準備し，add() メソッドを用い て頂点番号の組のリストで表現されるグラフを加えれ ば良い．この操作により，和集合演算後のグラフ集合 が ZDD として構築される．

3.2

ZDD サイズの削減を目指す手法

本小節では単純構築法をもとに，ZDD サイズの削減 を目標として新たに二つの手法を提案する．ただし，こ こで言う ZDD のサイズはそのノード数，つまり節点 の数を指すこととする． 一斉順序付け法 一つ目の提案手法は，geng によって 出力された代表元グラフの集合に対し，全ての要素に同 じ頂点番号の置換を施して ZDD を構築する手法である． 本手法において ZDD 構築のために用いる Graphillion では，ZDD 構築処理に用いる辺の順序を固定してお り，そのため辺リストを表現するための頂点番号の変 化によって構築結果の ZDD のサイズが変動すること が期待できる． 一斉順序付け法では，次の手順によりグラフ集合を 表現する ZDD を構築する： 1. 代表元グラフ集合 Grを geng を用いて生成する． 2. 求めるグラフ集合 fi ははじめ，空集合を表す ZDD とする． 3. 頂点番号の置換 π を一つ決定する． 4. Gr から要素を一つ選び（grとする），頂点番号 の置換（π(gr)）を行った後，そのグラフを ZDD に変換する．この ZDD を fr とする． 5. fi と frの和集合演算を Graphillion を用いて行 い，その結果を新たな fi とする． 6. Gr の全ての要素に対して一回ずつ手順 4. と 5. を行い，最後に出力された fi が求める ZDD と なる．

構築のイメージは図 4 のようになる．

∪

∪

図 4: 一斉順序付け法のイメージ図. 本手法では，ZDD 構築の際に用いる置換は一つだけ であるが，置換 π は n! 通りあるため，全組合せを試 し，その時の最小ノード数について調査した．また，参 考のために最大ノード数についても調査した． 個別順序付け法 二つ目の提案手法は，和集合演算 を行う際，ZDD に新たに加える代表元グラフに置換の 全組み合わせを施したものを生成し，並列に演算を行っ た上で演算後の ZDD のサイズが最小となるような置 換のみを採用する手法である． 個別順序付け法では，次の手順によりグラフ集合を 表現する ZDD を構築する： 1. 代表元グラフ集合 Grを geng を用いて生成する． 2. 求めるグラフ集合 fi ははじめ，空集合を表す ZDD とする． 3. Gr から要素を一つ選び，頂点番号の置換全通 り（π1, . . . , πn!）を用いて置換を行ったグラフを ZDD に変換する．これらの ZDD を f1, . . . , fn! とする． 4. fi と fp (p = 1, . . . , n!) の和集合をとる演算を， 全ての p に対して Graphillion を用いて並列に 行い，その結果の ZDD である fip のサイズが最 小となるようなものを採用する．採用した ZDD を新たな fi とする． 5. Gr の全ての要素に対して一回ずつ手順 3. と 4. を行い，最後に出力された fi が求める ZDD と なる． 構築のイメージは図 5 のようになる． ここで手順 4. においてサイズが最小となるようなも のが複数あった際の方針として，頂点番号 0, 1, 2, . . . を置換する時に辞書順で小さい置換（0, 1, 2, . . . に最 も近いもの）を選ぶ方針 (A) と，辞書順で大きい置換

∪

∪

図 5: 個別順序付け法のイメージ図. （n, n− 1, n − 2, . . . に最も近いもの）を選ぶ方針 (B) の二通りについて調査した． 本手法では代表元グラフを ZDD に加えていく際に n! 通りの置換全てに対し和集合演算を行うため，頂点 数が大きくなるほど計算に時間がかかることが予想さ れる．

4

実験と評価

本節では前節で提案した三つの手法を用いて実際に ZDD を構築した際の結果を述べ，それについて考察す る．本実験には MacOS 10.13 High Sierra，1.8 GHz Intel Core i5，メモリ 8GB の計算機を用いた．

4.1

ZDD のサイズに関する考察

三つの手法により構築した ZDD のサイズをまとめ た結果を表 1 に示す．比較のために，各頂点数におけ る代表元グラフ集合の要素全てのグラフにおける辺の 数の総和を掲載した．これは組合せ集合で表現した際 の変数リテラルの数に相当し，ZDD で表現したことに よる圧縮率の評価に用いる．ここで圧縮率は (ZDD の ノード数)/(辺の総数) によって与える．また一斉順序 付け法については参考のため，そのノード数が最大と なる場合の結果についても掲載した．頂点数 8 の場合 については，単純構築法を除き今回の手法においては ZDD を構築できなかった． geng の出力した代表元グラフ集合を用いる単純構築 法においては，その圧縮率は頂点数 4 で 48 ％，頂点数 8 で約 3.1 ％となっており，頂点数が多くなるに従いそ の圧縮率も小さくなっている． 単純構築法の結果と一斉順序付け法の結果を比較す ると，一斉順序付け法における最小ノード数はいずれ も単純構築法による結果より小さくなっており，ZDD サイズの削減効果が見られた．しかし，圧縮率の変化 は頂点数が大きくなるほど少なくなっており，特に頂

点数 7 の場合において約 0.094 ％となっているため，圧 縮率の変化で見ると一斉順序付け法は効果的な手法で はないと考えられる．他方，一斉順序付け法における 最大ノード数は単純構築法の結果より大きく，特に頂 点数が 7 の場合においてはノード数が 1.5 倍以上になっ ており，本研究における提案手法では頂点番号の置換 が ZDD のサイズに大きく影響すると言える． 次に単純構築法と個別順序付け法の結果を比較する と，個別順序付け法ではどちらの方針においてもノー ド数は少なくなっており，こちらも ZDD サイズの削減 効果が見られた．しかし，こちらの手法でも頂点数が 大きくなるほど圧縮率の変化は少なくなっている．方 針 (B) において頂点数 7 の時，ノード数は単純構築法 の場合と比べて約 82 ％に減少したが，圧縮率の変化は 約 1.3 ％であるため，この手法も圧縮率変化で見ると 効果的な手法であるとは言い難い． 次に個別順序付け法の方針による結果の差異に注目 すると，採用した方針は頂点順序に対して対称である にも関わらず，その結果は辞書順で大きい置換を選ぶ 方針 (B) を採用した方がノード数が少なくなる結果と なっている．この理由については，同じ組合せ集合を 表現するものであってもその変数順序によってノード 数が大きく変化することがあるという ZDD の特徴， Graphillion 内部での演算処理に用いられる頂点順序が 2 節で述べた方法で決定されていること，また geng は 代表元グラフ集合の生成に nauty を用いており，その 結果生成される代表元グラフ集合に出現する辺の分布 に何らかの傾向があること，の三点によるものだと考 えられる． 今回検証した中で ZDD のノード数を最も削減でき た個別順序付け法 (B) の手法における圧縮率変化は頂 点数 7 で約 1.3 ％であり，geng の出力する頂点順序付 けによるものとの差は小さいと言える．そのため，本 手法を用いる利点は，圧縮率や ZDD のノード数を削 減できる点よりは，ランダムサンプリングや集合演算 が容易に行えるといった ZDD の特徴を活かせるデー タに変換できた点が挙げられるだろう．

4.2

ZDD の構築時間に関する考察

ZDD を構築するプログラムの実行時間を計測した 結果を表 2 に示す．それぞれ time コマンドを用いて ZDD を生成するプログラムの実行時間を求めている が，括弧付きでない数字については 10 回の実行時間の 平均を，括弧付きの数字はプログラムの実行時間を一 度だけ計測したものを掲載した．ここで一斉順序付け 法に関しては，頂点番号の置換の全通りを試した際に かかった時間を掲載した．また表中の T.O. は 30 分以 内に処理が終了しなかったものである． 単純構築法の実行時間は頂点数 8 までは 1 秒以内で あるのに対し，ZDD のサイズ削減のために提案した手 法については，実行時間が大きく増加した．これは頂 点番号の置換が n! 通りあること，また和集合演算を 行う代表元グラフの個数自体も増えていくため，それ らの効果によるものだと考えられる．一斉順序付け法 も個別順序付け法も和集合演算を行う回数はおおよそ (代表元グラフの数)× n! 回であるが，個別順序付け法 に時間がかかるのは，和集合演算で用いる置換を選択 する際に，構築した ZDD を毎回ファイルに書き出し， その行数でサイズを計測したからであると考えられる． 一斉順序付け法では途中の ZDD サイズの比較のため に書き出しを行う必要がないために時間が短くなった と考えられる．

5

おわりに

本研究では，nauty と geng を用いて列挙された代表 元グラフ集合から ZDD を構築する手法の提案と，手 法の違いによる ZDD サイズの変化についての調査を 行った．結果として，規模の制約はあるものの代表元 グラフ集合を表すデータを ZDD に変換することがで きた．また，その構築時に頂点番号の置換を行うこと により ZDD のサイズを削減することができたが，圧 縮率変化については大きく減少したわけではなかった． 今後は，サイズ削減率と圧縮率を上げる手法やさら に大規模な代表元グラフ集合に対する ZDD 構築手法 の調査，ZDD による表現の利点を生かせる応用の調 査，geng が出力する代表元グラフ集合がどのような性 質を持つかについてのさらに詳しい調査，また，nauty や geng と本手法を組み合わせ，代表元に制約や傾向 を持たせたような代表元グラフ集合の ZDD 生成を行 う手法の調査などを課題としたい．

謝辞

様々な助言をいただいた京都大学大学院 情報学研究 科 通信情報システム専攻 湊研究室の皆様に深く感謝 いたします． 本研究の一部は JSPS 科研費基盤 (S) 15H05711 の 助成による．

参考文献

[1] Fortin, S.: The Graph Isomorphism Problem,

表 1: 実験結果 頂点数 代表元グラフ 辺の総数 ZDD のノード数 の数 単純構築法 一斉 (最小) 一斉 (最大) 個別 (A) 個別 (B) 4 6 25 12 8 13 10 7 5 21 130 37 27 43 34 24 6 112 951 127 108 169 107 94 7 853 9552 628 619 970 531 507 8 11117 160220 5030 - - - -表 2: 実行時間 頂点数 代表元グラフ 辺の総数 実行時間 (秒) の数 単純構築法 一斉順序付け 個別 (A) 個別 (B) 4 6 25 0.206 0.302 0.585 0.591 5 21 130 0.207 0.781 6.83 6.79 6 112 951 0.216 8.54 (253) (251) 7 853 9552 0.254 (310) T.O. T.O.

8 11117 160220 0.948 T.O. T.O. T.O.

[2] Brinkmann G., Coolsaet K., Goedgebeur J., Melot H.:House of Graphs: A database of in-teresting graphs, Discrete Applied Mathematics, Volume 161, Issues 12, pp.311–314 (2013) [3] R. ディーステル著, 根上生也, 太田克弘訳『グラ

フ理論』, シュプリンガー・フェアラーク東京, p.3 (2000)

[4] McKay, B.D., Piperno, A.: Practical Graph Iso-morphism, II, Journal of Symbolic Computation, 60, pp.94–112 (2014)

[5] Minato, S. I.: Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems,

30th ACM/IEEE Design Automation Confer-ence, pp.272–277 (1993)

[6] Inoue, T., Iwashita, H., Kawahara, J., Minato, S. I.: Graphillion: Software Library Designed for Very Large Sets of Labeled Graphs, International

Journal on Software Tools for Technology Trans-fer, vol.18, issue 1, pp.57–66, (2016)