月別アーカイブ: 2018年10月

似ているgraphを探す方法

ある与えられたグラフに対して,全く同じ形をしているグラフを探す問題をグラフ同型判定問題という.数学の分野で同型という言葉が出てくるときは,一見同じようには見えない場合でも,見方(例えば記号の付け方)などを変えることで同じにできるような場合にそう呼ぶことが多い.この場合の同型も同じような意味合いである.グラフには大きく分けて有向グラフなのか無効グラフなのかという違いがあるが,ここでは話を簡単にするため無向グラフに限定する.実は,多くの実問題で計算量や問題設定の緩和を図るために有向グラフを無向グラフにすることは比較的ありふれた話である.したがって,以下の話は必ずしも有向グラフでは無駄というわけではない.

グラフの同型判定問題や,もしくはより難しい問題である,あるグラフの中に探したいグラフを一部として含むかどうかを探す部分グラフ同型判定問題はNPであることはわかっているものの,NP困難であるかどうかはわかっていない(Web上の記事によってNP完全だったりNP困難であったり,もしくはどちらかわかっていないと書かれていたり,実際のところどうなのかわからない).どちらにせよ,この問題を解くことが今の所容易ではないことは変わらない.多くの文脈(例えば化学式の検索など)で,このグラフ同型性判定問題を解決したいと考えられており,多くのアルゴリズムが今までに提案されてきた.

さて,私が今回,扱いたいのはこのグラフ同型性判定問題ではなく,より曖昧とした問題,すなわち2つのグラフの類似度を知りたいという問題である.

不完全マッチング(inexact matching)

今回扱いたいのは不完全マッチング(inexact matching)である.実はこの単語,論文中に出てきた表現であり,私の知る限り日本語訳を見たことがない.inexact matchingは直訳すれば不正確マッチングだが,不正確は日本語の意味合いを考えると,誤解を招きかねない.完全マッチングという別の用語はあるものの,不完全という用語がおそらく今回の意味ではピッタリのように感じられるので,ここでは便宜上,不完全マッチングと呼ぶことにする.

さて,不完全マッチングとは要するに,与えられた2つのグラフは同型ではないのだが,微妙に似ており,その上で2つのグラフ間の最も妥当なノードもしくはエッジの対応付けはどのようなものかという問題である.この対応付けがわかると,2つのグラフの間の距離のような概念まで導入することができ,一昔に流行ったSVNではカーネル法に帰着できると分類問題に帰着可能になるため,このグラフ間の距離を求めることにはビッグデータなどの応用も含めて,一定の需要があるらしいのだ.さて,不完全マッチングでは,この妥当な対応付けというところが味噌で,不完全マッチングを提供するアルゴリズムによって,妥当の意味が違ってくる.一番多く使われているのは,グラフ編集距離(graph edit distance)と呼ばれるものを用いるやり方である.これは文字列に対する編集距離に概念としては近い.グラフのノードもしくはエッジの追加や削除などを行って,片方のグラフをもう片方のグラフに近づけたときに,最も少ない手数で対応付けられたときのコストをもって,2つのグラフの距離とする.また,このときに対応付けられたノードもしくはエッジが今回の場合の答えになるというものだ.しかし,この最も最短のグラフ編集の手順を探す問題はNP困難であることが知られている.最も高速に厳密解を得る方法としては,A*アルゴリズムを用いる方法があるが,この方法ではたかだか15ノード程度が求められる関の山で,それ以上となると手も足も出ない.そこで,これまでに提案されたアルゴリズムでは,近似的にこの問題を解く方法が模索されてきた.

もう一つのこの問題の考え方は,2つのグラフのノード,エッジ同士の対応付に関する適応関数を定義し,その適応関数が最大となるような割当を探す問題に帰着させる方法である.この方法では,予め2つのグラフ間のノードもしくはエッジを対応付けした際の利益のようなものを設定しておく.例えば,グラフA, Bについて,Aの1番めのノードとBの2番めのノードを対応付けたら,10点だとか,Aの2番めとBの2番め同士なら5点みたいな感じである.その上で,すべてのノードとエッジを対応付けたあとのすべての適応値の合計が最大となるように対応付けを行ったときの対応をマッチングの結果とするのである.

上記の2つのやり方,すなわち
1. グラフの編集距離を最小とするやり方
2. グラフの各要素の対応付で最も適応関数の値が最大となるものを探すやり方
の2つは,本質的に違う問題のように感じられるだろうが,実はどちらについても二次割当問題(QAP)というNP困難な問題に帰着できることが知られている.したがって,結局の所,この問題を解くことはQAPを如何に高速に解くかという話になる.

手っ取り早く最新の結果を使いたい人へ

本当は,このあとにこの問題がどうして二次割当問題に帰着可能で,過去の研究ではいかにしてこれを解こうとしているのかを説明しようと思ったのだが,今回も例に漏れず面倒になってきたので,すでにあるライブラリだけ紹介して終わりにする.余裕があれば,そのあたりの話も追記したい.調べた感じでは,次の3つのgithubの実装が役立ちそうだ.
– https://github.com/bgauzere/graph-lib
– http://www.f-zhou.com/gm_code.html
– https://github.com/egbertbouman/fgm-cpp
上記の内,2つはC++で実装されており,残りの一つはMatlabだ.特にこれらは割と最近の結果(2017年)のものまで含まれており,その論文によれば500ノードくらいまではぼちぼち動くらしいので,それなりに使い物になるのではないかと思う.

内容についてどう思いますか?
  • いいね (2)
  • だめ (0)