(57)【要約】      （修正有）【課題】データグラフの中からクエリグラフと同型な部分を探索するサブグラフマッチング処理を高速化する探索装置、探索方法および探索プログラムを提供する。【解決手段】探索装置１が、ラベルが付与された頂点と、隣接する頂点間を接続するエッジとで構成されるグラフのうち、検索対象のデータのグラフであるデータグラフから、検索に使用されるクエリのグラフであるクエリグラフと同型な部分を探索する際に、パターン抽出部１３ｂが、該探索の過程において発生する探索の失敗に基づいて、クエリグラフの頂点とデータグラフの頂点との組み合わせの集合を、探索の失敗の要因を表す失敗パターンとして抽出し、探索部１３ｃが、パターン抽出部１３ｂにより抽出された失敗パターンと合致する探索の状態を枝刈りして、データグラフからクエリグラフと同型な部分を探索する。【選択図】図７
2019101610.tif 000002
【特許請求の範囲】
【請求項１】
ラベルが付与された頂点と、隣接する頂点間を接続するエッジとで構成されるグラフのうち、検索対象のデータのグラフであるデータグラフから、検索に使用されるクエリのグラフであるクエリグラフと同型な部分を探索する際に、該探索の過程において発生する探索の失敗に基づいて、クエリグラフの頂点とデータグラフの頂点との組み合わせの集合を、探索の失敗の要因を表す失敗パターンとして抽出するパターン抽出部と、
前記パターン抽出部により抽出された前記失敗パターンと合致する探索の状態を枝刈りして、前記データグラフから前記クエリグラフと同型な部分を探索する探索部と、
を備えることを特徴とする探索装置。
【請求項２】
前記データグラフの各頂点と隣接する頂点とのラベルの組み合わせに基づいて、前記クエリグラフの頂点と一致し得る前記データグラフの頂点に隣接する頂点のうち、前記クエリグラフの頂点に隣接する頂点と一致し得る該データグラフの頂点を、前記データグラフの各頂点に対応する候補頂点として抽出する頂点抽出部をさらに備え、
前記パターン抽出部は、抽出された前記候補頂点を用いて前記失敗パターンを抽出することを特徴とする請求項１に記載の探索装置。
【請求項３】
頂点と、隣接する頂点間を接続するラベルが付与されたエッジとで構成されるグラフのうち、検索対象のデータのグラフであるデータグラフから、検索に使用されるクエリのグラフであるクエリグラフと同型な部分を探索する際に、該探索の過程において発生する探索の失敗に基づいて、クエリグラフの頂点とデータグラフの頂点との組み合わせの集合を、探索の失敗の要因を表す失敗パターンとして抽出するパターン抽出部と、
前記パターン抽出部により抽出された前記失敗パターンと合致する探索の状態を枝刈りして、前記データグラフから前記クエリグラフと同型な部分を探索する探索部と、
を備えることを特徴とする探索装置。
【請求項４】
前記パターン抽出部は、前記失敗パターンをハッシュテーブルとして記憶部に記録し、
前記探索部は、該記憶部を参照して前記失敗パターンと合致する探索の状態を枝刈りして、前記データグラフから前記クエリグラフと同型な部分を探索することを特徴とする請求項１〜３のいずれか１項に記載の探索装置。
【請求項５】
探索装置で実行される探索方法であって、
ラベルが付与された頂点と、隣接する頂点間を接続するエッジとで構成されるグラフのうち、検索対象のデータのグラフであるデータグラフから、検索に使用されるクエリのグラフであるクエリグラフと同型な部分を探索する際に、該探索の過程において発生する探索の失敗に基づいて、クエリグラフの頂点とデータグラフの頂点との組み合わせの集合を、探索の失敗の要因を表す失敗パターンとして抽出するパターン抽出工程と、
前記パターン抽出工程において抽出された前記失敗パターンと合致する探索の状態を枝刈りして、前記データグラフから前記クエリグラフと同型な部分を探索する探索工程と、
を含むことを特徴とする探索方法。
【請求項６】
ラベルが付与された頂点と、隣接する頂点間を接続するエッジとで構成されるグラフのうち、検索対象のデータのグラフであるデータグラフから、検索に使用されるクエリのグラフであるクエリグラフと同型な部分を探索する際に、該探索の過程において発生する探索の失敗に基づいて、クエリグラフの頂点とデータグラフの頂点との組み合わせの集合を、探索の失敗の要因を表す失敗パターンとして抽出するパターン抽出ステップと、
前記パターン抽出ステップにおいて抽出された前記失敗パターンと合致する探索の状態を枝刈りして、前記データグラフから前記クエリグラフと同型な部分を探索する探索ステップと、
をコンピュータに実行させることを特徴とする探索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、探索装置、探索方法および探索プログラムに関する。
【背景技術】
【０００２】
グラフ構造の中からクエリとして与えられた特定の部分構造すなわちサブグラフを発見する問題は、サブグラフマッチングと呼ばれる。従来、サブグラフマッチングでは、バックトラッキングと呼ばれる探索アルゴリズムに基づいて探索されていた（非特許文献１，２参照）。バックトラッキングでは、クエリグラフＱおよびデータグラフＧを入力として、データグラフＧに含まれる全てのクエリグラフＱの埋め込みが報告される。その際、クエリグラフＱの頂点の割り当て先となり得るデータグラフＧの候補頂点が抽出され、クエリグラフＱの頂点の割り当て先を候補頂点の中から変更しながら選択して埋め込みを探索することにより、埋め込みが列挙される。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Huahai  He，Ambuj  K.  Singh，“Graphs-at-a-time:  Query  Language  and  Access  Methods  for  Graph  Databases”，Proceedings  of  the  2008  ACM  SIGMOD  International  Conference  on  Management  of  Data，SIG-MOD  '08，2008年，pp.405-418
【非特許文献２】Jinsoo  Lee，Wook-Shin  Han，Romans  Kasperovics，Jeong-Hoon  Lee，“An  In-depth  Comparison  of  Subgraph  Isomorphism  Algorithms  in  Graph  Databases”，Proceedings  of  the  39th  international  conference  on  Very  Large  Data  Bases，2012年，pp.133-144
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来のバックトラッキングによれば、探索対象であるデータグラフＧ中の埋め込みが存在しない部分に対しても、網羅的に探索を行うために、長い処理時間を要していた。そのため、例えば、グラフデータ向けに設計されたデータベースであるグラフデータベースに対する、サブグラフマッチングとして記述されるクエリを用いた対話的な作業や、グラフデータベースに依存するサービスの提供が困難な場合があった。また、グラフに対してサブグラフマッチングを用いて、例えば、特定のサブグラフの出現回数をグラフの特徴量として利用するデータマイニングを行う際に、現実的な時間で完了できない場合があった。
【０００５】
本発明は、上記に鑑みてなされたものであって、データグラフの中からクエリグラフと同型な部分を探索するサブグラフマッチング処理を高速化することを目的とする。
【課題を解決するための手段】
【０００６】
上述した課題を解決し、目的を達成するために、本発明に係る探索装置は、ラベルが付与された頂点と、隣接する頂点間を接続するエッジとで構成されるグラフのうち、検索対象のデータのグラフであるデータグラフから、検索に使用されるクエリのグラフであるクエリグラフと同型な部分を探索する際に、該探索の過程において発生する探索の失敗に基づいて、クエリグラフの頂点とデータグラフの頂点との組み合わせの集合を、探索の失敗の要因を表す失敗パターンとして抽出するパターン抽出部と、前記パターン抽出部により抽出された前記失敗パターンと合致する探索の状態を枝刈りして、前記データグラフから前記クエリグラフと同型な部分を探索する探索部と、を備えることを特徴とする。
【発明の効果】
【０００７】
本発明によれば、データグラフの中からクエリグラフと同型な部分を探索するサブグラフマッチング処理を高速化することができる。
【図面の簡単な説明】
【０００８】
【図１】図１は、サブグラフマッチングに関する定義を示す図である。
【図２】図２は、再帰関数の処理手順を示すフローチャートである。
【図３】図３は、サブグラフマッチング処理を説明するための説明図である。
【図４】図４は、サブグラフマッチング処理を説明するための説明図である。
【図５】図５は、本実施形態の探索装置の処理概要を説明するための説明図である。
【図６】図６は、本実施形態の探索装置の処理概要を説明するための説明図である。
【図７】図７は、本実施形態の探索装置の概略構成を示す模式図である。
【図８】図８は、本実施形態の探索装置による探索処理に関する定義および定理を示す図である。
【図９】図９は、本実施形態の探索装置による探索処理に関する定理を示す図である。
【図１０】図１０は、本実施形態の探索装置による探索処理に関する定理を示す図である。
【図１１】図１１は、本実施形態の探索装置による探索処理に関する定理を示す図である。
【図１２】図１２は、本実施形態の探索処理手順を示すフローチャートである。
【図１３】図１３は、他の実施形態の探索処理を説明するための説明図である。
【図１４】図１４は、探索プログラムを実行するコンピュータを例示する図である。
【発明を実施するための形態】
【０００９】
以下、図面を参照して、本発明の一実施形態を詳細に説明する。なお、この実施形態により本発明が限定されるものではない。また、図面の記載において、同一部分には同一の符号を付して示している。
【００１０】
［従来のサブグラフマッチング処理］
まず、従来のサブグラフマッチング処理について説明する。以下の説明において、頂点がラベルを持つ無向グラフＧ＝（ＶＧ，ＥＧ，Σ，ｌ）を処理の対象とする。以下、Ｇをデータグラフと記す。ここで、ＶＧは頂点の集合、ＥＧ⊆ＶＧ×ＶＧはエッジの集合、Σはラベルの集合、ｌは頂点とラベルとを対応させる関数を示す。同様に、クエリグラフＱ＝（ＶＱ，ＥＱ，Σ，ｌ）を処理の対象とする。クエリグラフの頂点は、ｕ１，ｕ２，…，ｕ｜ＶＱ｜というように、番号付けされているものとする。
【００１１】
また、サブグラフマッチングとは、データグラフＧとクエリグラフＱとが与えられたときに、サブグラフ同型である部分への埋め込みＭを列挙する問題と定義する。
【００１２】
ここで、図１を参照して、サブグラフマッチングについて説明する。図１は、サブグラフマッチングに関する定義を示す図である。以下の説明において、図１の定義１に示すように、埋め込みを集合として表現する。サブグラフマッチングでは、クエリグラフの頂点（以下、クエリ頂点と記す。）から、データグラフの頂点（以下、データ頂点と記す。）への埋め込みＭ∈ＶＱ×ＶＧを探索する。
【００１３】
また、探索の過程において、図１の定義２に示す部分埋め込み、すなわち、一部のクエリ頂点についてのみ、データ頂点が割り当てられた埋め込みを考える必要がある。なお、本実施形態において、定義域がＶＱ全体であるような埋め込みを完全な埋め込みと記す場合がある。
【００１４】
また、次式（１）〜（３）に示す３つの制約を満たす埋め込みＭ：ＶＱ→ＶＧを定義できるときに、ＱはＧに対してサブグラフ同型であるものする。
【００１５】
【数１】
2019101610.tif 000003
【００１６】
【数２】
2019101610.tif 000004
【００１７】
【数３】
2019101610.tif 000005
【００１８】
従来のサブグラフマッチング処理の主流は、バックトラッキングに基づく探索アルゴリズムである。上記したとおり、バックトラッキングは、主に、候補頂点の抽出と、埋め込みの列挙との２つの処理を含む。
【００１９】
まず、候補頂点の抽出において、候補頂点すなわち各クエリ頂点の割り当て先となり得るデータ頂点の集合Ｃ［ｕｉ］⊆ＶＧが抽出される。ｕｉがデータ頂点ｖに割り当て可能か否かは、例えば、次式（４）〜(６)を用いて判定される（非特許文献１参照）。つまり、次式（４）〜（６）の全てを満たす場合に、ｕｉがｖに割り当て可能と判定される。
【００２０】
【数４】
2019101610.tif 000006
【００２１】
【数５】
2019101610.tif 000007
【００２２】
【数６】
2019101610.tif 000008
【００２３】
上記式（４）では、まず、ラベルの一致が確認される。従って、Ｃ［ｕｉ］に含まれるデータ頂点は、ラベル制約を満たす。また、上記式（５）にて次数が比較され、上記式（６）にて隣接頂点のラベルごとに隣接頂点数が比較される。これらの条件では、ｖにｕｉ以上の数の隣接頂点がなければ、ｕｉの隣接頂点をｖの隣接頂点に割り当てることができないことが利用されている。このように、確認が容易な条件により、割り当て不可能なクエリ頂点とデータ頂点との組み合わせを除外して、以降の探索を高速化している。
【００２４】
次に、図２を参照して、埋め込みの列挙について説明する。埋め込みの列挙では、再帰関数Ｓｅａｒｃｈが呼び出され実行される。図２は、再帰関数の処理手順を示すフローチャートである。図２に示すフローチャートでは、まず、Ｓｅａｒｃｈ（φ）が呼び出される。ただし、φは空集合を表す。再帰関数Ｓｅａｒｃｈ（Ｐ）は、部分埋め込みＰを引数として受け取り、まず、Ｐが完全な埋め込みであるか否かが確認される（ステップＳ１００）。すなわち、ｋ＝｜Ｐ｜として、ｋ＝｜ＶＱ｜であるか否かが確認される。Ｐが完全な埋め込みである場合（ステップＳ１００，Ｙｅｓ）、Ｐは埋め込みとして報告され（ステップＳ１８０）、処理は関数の呼び出し元に戻る。
【００２５】
一方、Ｐが完全な埋め込みではない場合（ステップＳ１００，Ｎｏ）、ステップＳ１１０に処理が進む。ステップＳ１１０の処理では、クエリ頂点ｕｋ＋１がデータ頂点ｖに割り当てられる。その際、ｖをＣ［ｕｉ］から選択することによりラベル制約が満たされることになる。同時に、ｖは、既にＰに含まれるクエリ頂点と、データ頂点に関してエッジ制約が満たされなければならない。具体的には、次式（７）に示すエッジ制約を満たすｖ∈Ｃ［ｕｉ］が選択される。
【００２６】
【数７】
2019101610.tif 000009
【００２７】
次に、Ｐに（ｕｋ＋１，ｖ）の割り当てが追加された部分埋め込みＰ＋が作成され、Ｐ＋について単射制約が確認される（ステップＳ１２０）。Ｐ＋が単射であれば（ステップＳ１２０，Ｙｅｓ）、Ｐ＋を引数として再帰関数Ｓｅａｒｃｈ（Ｐ＋）が再帰呼び出しされる（ステップＳ１４０）。一方、Ｐ＋が単射でなければ（ステップＳ１２０，Ｎｏ）、再帰関数Ｓｅａｒｃｈ（Ｐ＋）は再帰呼び出しされず、呼び出し元に戻る（ステップＳ１５０）。
【００２８】
次に、図３および図４を参照して、従来のサブグラフマッチング処理を具体的に説明する。図３および図４は、サブグラフマッチング処理について説明するための説明図である。従来のサブグラフマッチング処理では、まず、上記式（４）〜（６）を用いて、候補頂点集合が抽出される。図３に示す例では、Ｃ［ｕ1］＝｛ｖ１｝，Ｃ［ｕ２］＝｛ｖ２，…，ｖ５｝，Ｃ［ｕ３］＝｛ｖ６，…，ｖ９｝，Ｃ［ｕ４］＝｛ｖ１，ｖ１０｝が抽出される。
【００２９】
この場合に、図４に示すバックトラッキングの探索木に従って、Ｃ［ｕ1］＝｛ｖ１｝であることから、最初にｕ１がｖ１に割り当てられる。またここでは、ｕ２以降については、頂点番号の昇順に探索する場合について考える。すなわち、Ｃ［ｕ２］からｖ２が選択され、Ｃ［ｕ３］からｖ６が選択され、Ｃ［ｕ４］からｖ１０が選択される。この場合に、全てのクエリ頂点がデータ頂点に割り当てられるので、｛（ｕ１，ｖ１），（ｕ２、ｖ２），（ｕ３，ｖ６），（ｕ４，ｖ１０）｝が埋め込みとして報告される。
【００３０】
さらに、他の埋め込みが探索される。ｕ２の割り当て先の選択に戻り、ｕ２がｖ３に割り当てられ、ｕ３がｖ７に割り当てられる。この場合に、ｖ７に隣接するｕ４の候補頂点ｖ１には、既にｕ１が割り当てられており、単射制約の違反となるため、ｕ４をｖ１に割り当てることができない。ｖ７の隣接頂点には、他にｕ４の候補頂点が存在しないため、探索失敗となる。
【００３１】
ｕ３の残りの候補頂点ｖ８、ｖ９についても、同様に、ｕ４をｖ１に割り当てることができず、探索失敗となる。また、ｕ２の割り当て先の選択に戻り、ｕ２がｖ４に割り当てられた場合、およびｕ２がｖ５に割り当てられた場合にも、同様に、探索失敗となる。以上の処理により、全ての候補頂点について探索が行われたことになり、探索が終了する。
【００３２】
このように、従来のサブグラフマッチング処理は、クエリ頂点の割り当て先を変更しながら再帰呼び出しを繰り返すバックトラッキングに基づいて実行されている。
【００３３】
［探索装置の処理概要］
次に、図５および図６を参照して、本実施形態に係る探索装置の処理概要を説明する。本実施形態の探索装置は、図３に示した例において、上記の従来のサブグラフマッチング処理と同様に、まず、｛（ｕ１，ｖ１），（ｕ２、ｖ２），（ｕ３，ｖ６），（ｕ４，ｖ１０）｝を埋め込みとして報告する。
【００３４】
次に、探索装置は、バックトラッキングによってｕ２をｖ３に割り当て、ｕ３をｖ７に割り当てて探索失敗となった場合に、失敗パターンとして記録する。すなわち、「ｕ１のｖ１への割り当てと、ｕ３のｖ７への割り当てとを同時に行うと、探索に失敗する」ということを失敗パターンとして抽出して記録しておく。同様に、ｕ３をｖ８またはｖ９に割り当てて探索失敗となった場合にも、「ｕ１のｖ１への割り当てと、ｕ３のｖ８（またはｖ９）への割り当てとを同時に行うと、探索に失敗する」ということを失敗パターンとして抽出して記録しておく。
【００３５】
また、探索装置が、ｕ２の割り当て先をｖ４に変更した場合に、ｕ３を隣接頂点ｖ７，ｖ８，ｖ９に割り当てた部分埋め込みは、いずれも記録済みの失敗パターンに合致する。従って、ｕ３を候補頂点に割り当てた部分埋め込みを作成することなく、探索失敗になることがわかる。ｕ２の割り当て先をｖ５に変更した場合についても、同様に、探索失敗になることがわかる。
【００３６】
このように、本実施形態の探索装置によれば、図５に示す探索木のように、図４に示した従来のサブグラフマッチングの探索木と比較して、探索空間が減少する。すなわち、従来は、図４に示したように、ｕ２をｖ３，ｖ４，ｖ５のいずれかに割り当てるような埋め込みが存在しないにもかかわらず、それぞれｕ３をｖ７，ｖ８，ｖ９に割り当てて探索していた。つまり、従来は、ある部分埋め込みＰについて、Ｐ⊂Ｍであるような完全な埋め込みＭが存在しない場合にも、バックトラッキングによる探索を行っていた。本実施形態の探索装置は、このような埋め込みの発見に至らない探索の枝刈りを行う。したがって、本実施形態の探索装置によれば、高速なサブグラフマッチングが可能となる。
【００３７】
また、図６のフローチャートに示すように、本実施形態の探索装置による埋め込みの列挙の処理は、図２に示した従来のサブグラフマッチング処理における再帰関数の処理手順と、ステップＳ１３０、Ｓ１６０〜Ｓ１７０が異なる。すなわち、図６に示すように、本実施形態の探索装置においては、失敗パターンが抽出されて記録される（ステップＳ１６０〜Ｓ１７０）。具体的には、再帰関数Ｓｅａｒｃｈ（Ｐ＋）の再帰呼び出しにおいて埋め込みが一つも報告されなかった場合に（ステップＳ１６０，Ｙｅｓ）、Ｐから失敗パターンが抽出され記録される（ステップＳ１７０）。埋め込みが報告された場合には（ステップＳ１６０，Ｎｏ）、処理は関数の呼び出し元に戻る。
【００３８】
また、抽出された失敗パターンと照合される（ステップＳ１３０）。具体的には、作成された部分埋め込みＰ＋が記録されている失敗パターンのいずれにも合致しない場合に（ステップＳ１３０，Ｙｅｓ）、再帰関数Ｓｅａｒｃｈ（Ｐ＋）が再帰呼び出しされる（ステップＳ１４０）。Ｐ＋がいずれかの失敗パターンに合致した場合には（ステップＳ１３０，Ｎｏ）、ステップＳ１５０に処理が進む。その他の処理は図２に示した従来のサブグラフマッチング処理と同様であるので、説明を省略する。
【００３９】
［探索装置の構成］
次に、図７を参照して、本実施形態に係る探索装置の概略構成を説明する。図７に示すように、本実施形態に係る探索装置１は、ワークステーションやパソコン等の汎用コンピュータで実現され、入力部１１と出力部１２と制御部１３と記憶部１４とを備える。探索装置１は、後述する探索処理を実行して、失敗パターンの枝刈りを行いながら、サブグラフマッチング処理を行う。
【００４０】
入力部１１は、キーボードやマウス等の入力デバイスを用いて実現され、操作者による入力操作に対応して、制御部１３に対して各種指示情報を入力する。また、本実施形態において、入力部１１は、後述する探索処理の対象のデータグラフＧおよびクエリグラフＱを含むグラフデータを受け付けて制御部１３に入力する。
【００４１】
出力部１２は、液晶ディスプレイなどの表示装置、プリンター等の印刷装置、情報通信装置等によって実現され、例えば、後述する探索処理の処理結果であるサブグラフマッチング結果等を操作者に対して出力する。
【００４２】
また、探索装置１は、図示しない通信制御部を備える。通信制御部は、ＮＩＣ（Network  Interface  Card）等で実現され、ＬＡＮ（Local  Area  Network）やインターネットなどの電気通信回線を介したサーバ等の外部の装置と制御部１３との通信を制御する。例えば、上記のグラフデータは、通信制御部を介して外部の装置から受け付けてもよい。また、サブグラフマッチング結果は、通信制御部を介して外部の装置に出力されてもよい。
【００４３】
記憶部１４は、ＲＡＭ（Random  Access  Memory）、フラッシュメモリ（Flash  Memory）等の半導体メモリ素子、または、ハードディスク、光ディスク等の記憶装置によって実現される。記憶部には、探索装置１を動作させる処理プログラムや、処理プログラムの実行中に使用されるデータなどが予め記憶され、あるいは処理の都度一時的に記憶される。例えば、後述する探索処理において、抽出された失敗パターンが記録される。この記憶部１４は、通信制御部を介して制御部１３と通信する構成でもよい。
【００４４】
制御部１３は、ＣＰＵ（Central  Processing  Unit）等の演算処理装置がメモリに記憶された処理プログラムを実行することにより、図３に例示するように、頂点抽出部１３ａ、パターン抽出部１３ｂ、および探索部１３ｃとして機能する。なお、制御部１３は、後述する探索処理が実現されるならば、これらの機能部とは異なる機能単位で構成されていてもよい。
【００４５】
また、本実施形態において、制御部１３は複数ＣＰＵコアで実現されてもよい。これにより、バックトラッキングの各枝に対応する処理や、後述する探索処理における各データグラフの頂点に関する処理を、複数のＣＰＵによる並行処理で行うことが可能となる。
【００４６】
具体的には、制御部１３は、ラベルが付与された頂点と、隣接する頂点間を接続するエッジとで構成されるグラフのうち、検索対象のデータのグラフであるデータグラフから、検索に使用されるクエリのグラフであるクエリグラフと一致する部分を探索する際に、以下の探索処理を実行する。
【００４７】
すなわち、頂点抽出部１３ａは、データグラフの各頂点と隣接する頂点とのラベルの組み合わせに基づいて、クエリグラフの頂点と一致し得るデータグラフの頂点に隣接する頂点のうち、クエリグラフの頂点に隣接する頂点と一致し得る該データグラフの頂点を、データグラフの各頂点に対応する候補頂点として抽出する。具体的には、頂点抽出部１３ａは、従来のバックトラッキング処理と同様に、上記式（４）〜（６）を満たす候補頂点を抽出する。
【００４８】
また、パターン抽出部１３ｂは、探索の過程において発生する探索の失敗に基づいて、クエリグラフの頂点とデータグラフの頂点との組み合わせの集合を、探索の失敗の要因を表す失敗パターンとして抽出する。具体的には、パターン抽出部１３ｂは、以下に説明するように、抽出された候補頂点を用いて失敗パターンを抽出する。
【００４９】
また、探索部１３ｃは、パターン抽出部１３ｂにより抽出された失敗パターンと合致する探索の状態を枝刈りして、データグラフからクエリグラフと同型な部分を探索する。
【００５０】
ここで、図８は、本実施形態の探索装置による探索処理に関する定義および定理を示す図である。以下に説明する探索処理において、図８に示す定義および定理が適用される。すなわち、図８の定義３に示すように、失敗パターンが定義される。また、図８の定義４に示すように、パターンの合致が定義される。また、図８の定理１に示すように、失敗パターンの判定が定義される。
【００５１】
パターン抽出部１３ｂは、図６に示したように、探索が失敗した場合に部分埋め込みから失敗パターンを抽出する（ステップＳ１７０）。パターン抽出部１３ｂは、より多くの部分埋め込みに合致してより効果的に探索の枝刈りを行うため、より一般化された失敗パターンを抽出することが望ましい。すなわち、失敗パターンＤに含まれる、クエリ頂点とデータ頂点との組み合わせの数｜Ｄ｜が小さいことが望ましい。そこで、パターン抽出部１３ｂは、探索失敗であることがわかった部分埋め込みＰから、クエリ頂点とデータ頂点との組み合わせの一部を抽出して失敗パターンＤを作成する。したがって、作成される失敗パターンＤは、抽出元の部分埋め込みをＰとしたときにその部分集合となるため、次式（８）を満たす。
【００５２】
【数８】
2019101610.tif 000010
【００５３】
失敗パターンは、探索失敗の原因に基づいて作成される。探索失敗の原因は、図６に示したように、エッジ制約を満たす候補頂点がないこと（ステップＳ１１０）、Ｐに新しい割り当てを追加して作成したＰ＋がいずれも失敗であること（ステップＳ１２０〜Ｓ１４０）の２つに大別される。
【００５４】
まず、エッジ制約を満たす候補頂点がない場合の失敗パターンの抽出方法について説明する。図６のステップＳ１１０の処理対象である上記式（７）を満たす候補頂点ｖの集合をＣＰ［ｕｉ］とすると、次式（９）が成立する。
【００５５】
【数９】
2019101610.tif 000011
【００５６】
ここで、図９は、本実施形態の探索装置による探索処理に関する定理を示す図である。クエリ頂点ｕ１に対応する候補頂点がない状態は、空集合であるようなＣＰ［ｕｉ］によって表される。また、まだデータ頂点が割り当てられていないクエリ頂点の候補頂点がなくなった場合に、探索失敗となる。換言すると、図９の定理２に示すように、式（１０）が成立する。
【００５７】
さらに、ＣＰ［ｕｉ］が空集合である場合について、図９に示す定理３が成立する。
【００５８】
つまり、エッジ制約により候補頂点がなくなった場合に、ＣＰ［ｕｉ］が空集合となるｕｉが存在する。その場合のｉについて、Ｄｉ⊆ＰかつＤｅａｄ（Ｄｉ）であるようなＤｉが存在し、上記式（８）を満たす。そこで、パターン抽出部１３ｂは、ＣＰ［ｕｉ］が空集合であるような任意のＤｉを失敗パターンとして登録する。
【００５９】
次に、Ｐ＋がいずれも失敗である場合の失敗パターンの抽出方法について説明する。ここで、図１０は、本実施形態の探索装置による探索処理に関する定理を示す図である。Ｐ＋がいずれも失敗である場合に、図１０に示す定理４および定理５が成立する。すなわち、Ｐ＋がいずれも失敗である場合について、定理４の式（１３）が成立することから、式（１５）に示す失敗パターンの集合を定義できる。この場合の失敗パターンについて、定理５の式（１６）が成立する。したがって、パターン抽出部１３ｂは、式（１６）を用いて作成した失敗パターンを登録する。
【００６０】
次に、定理４の式（１５）に示した失敗パターンの集合を得るために、Ｐ＋からＤ＋を抽出する方法について説明する。Ｐ＋が失敗となる原因は、図６に示したように、Ｐ＋が単射でないこと（ステップＳ１２０）、Ｐ＋がいずれかの失敗パターンに合致すること（ステップＳ１３０）、再帰呼び出しした再帰関数が探索失敗となること（ステップＳ１４０）の３つである。このうち、Ｐ＋がいずれかの失敗パターンに合致する場合については、失敗パターンが既に抽出され記録されている。また、再帰呼び出しした再帰関数が探索失敗となる場合は、再帰関数内で失敗パターンの抽出と記録とが行われる。したがって、パターン抽出部１３ｂは、Ｐ＋が単射でない場合にのみ、新たに失敗パターンの抽出を行う。
【００６１】
部分埋め込みＰ＋が単射でないこと、すなわち、同じデータ頂点に複数のクエリ頂点が割り当てられることによる失敗は、図１１に示す定理６および定理７のように表される。すなわち、Ｐ＋が単射でない場合について、定理６の式（１８）が成立する。また、式（１９）のＤｉ＋は、定理７の式（２０）に示すように、それ自体が失敗パターンとなっている。
【００６２】
なお、この探索アルゴリズムでは、再帰関数Ｓｅａｒｃｈには単射であることが確認された部分埋め込みが引き渡されている（ステップＳ１２０）。そのため、Ｐ＋が単射でないことは、最後に追加されたｕｋと、もう一つの他のクエリ頂点とが同じデータ頂点に割り当てられたことに起因する。したがって、Ｐ＋が単射でないならば、｜Ｄｋ＋｜＝２である。この場合に、パターン抽出部１３ｂは、Ｄｋ＋をＰ＋から抽出した失敗パターンとする。
【００６３】
［探索処理］
次に、図１２を参照して、探索装置１の探索処理について説明する。図１２は、本実施形態の探索処理手順を示すフローチャートである。図１２のフローチャートは、図６に示したフローチャートに、失敗パターンを抽出するための処理が追加されたものである。ただし、失敗パターンの集合は、関数Ｓｅａｒｃｈのスコープ外で定義された大域変数であり、空集合で初期化されているものとする。
【００６４】
この探索処理では、パターン抽出部１３ｂが、上記の定理３，５，７に基づいて失敗パターンＤを作成し、作成したＤを失敗パターン集合へ追加する。また、パターン抽出部１３ｂは、関数Ｓｅａｒｃｈの戻り値としてＰから抽出された失敗パターンを返す。ただし、パターン抽出部１３ｂは、引数Ｐを含む埋め込みが発見された場合には空集合を返す。
【００６５】
まず、図２に示した従来のサブグラフマッチング処理と同様に、探索部１３ｃは、Ｐが完全な埋め込みであるか否かを確認する（ステップＳ１００）。完全な埋め込みである場合には（ステップＳ１００，Ｙｅｓ）、探索部１３ｃは、Ｐを埋め込みとして報告する（ステップＳ１８０）。また、Ｐは失敗ではないので、探索部１３ｃは、Ｐから抽出された失敗パターンＤを空集合とする（ステップＳ１６１）。
【００６６】
完全な埋め込みでなかった場合には（ステップＳ１００，Ｎｏ）、探索部１３ｃは、Ｐが図９に示した定理２に基づく失敗であるか否かを確認する（ステップＳ１６３）。失敗の場合には（ステップＳ１６３，Ｙｅｓ）、パターン抽出部１３ｂは、図９に示した定理３に基づいて失敗パターンを抽出する（ステップＳ１６４）。失敗でない場合には（ステップＳ１６３，Ｎｏ）、探索部１３ｃが、Ｐに新しい割り当てを追加したＰ＋について処理を進める。
【００６７】
すなわち、探索部１３ｃは、まず、Ｐ＋のそれぞれから抽出された失敗パターンＤ＋の集合を空集合で初期化する（ステップＳ１６５）。次に、探索部１３ｃは、エッジ制約を満たす頂点ｖ∈ＣＰ［ｕｋ＋１］について、ループを実行する（ステップＳ１１０）。すなわち、探索部１３ｃは、Ｐ＋を作成し（ステップＳ１２１）、それが単射であるか否かを確認する（ステップＳ１２２）。ここで、Ｐは単射であるので、Ｐ＋が単射でないことは、ｖ∈ｖａｌ（Ｐ）であるか否かによって確認できる。
【００６８】
単射でない場合に（ステップＳ１２２，Ｙｅｓ）、パターン抽出部１３ｂが、図１１に示した定理７に基づいて失敗パターンを失敗パターンの集合に追加する（ステップＳ１３１）。単射である場合に（ステップＳ１２２，Ｎｏ）、探索部１３ｃは、Ｐ＋が失敗パターンの集合に記録された失敗パターンに合致するか否かを確認する（ステップＳ１３２）。
【００６９】
合致する失敗パターンＤ＋が存在する場合には（ステップＳ１３２，Ｙｅｓ）、このＤ＋はＰから抽出された失敗パターンであるので、パターン抽出部１３ｂは、このＤ＋を失敗パターンの集合に追加する（ステップＳ１３３）。合致する失敗パターンがなければ（ステップＳ１３２，Ｎｏ）、探索部１３ｃは、Ｓｅａｒｃｈ（Ｐ＋）を再帰呼び出しし、戻り値をＤ＋に代入する（ステップＳ１４１）。また、探索部１３ｃは、戻り値Ｄ＋を失敗パターンの集合に追加する（ステップＳ１４２）。
【００７０】
以上の処理を、全てのｖ∈ＣＰ［ｕｋ＋１］について実行したら、探索部１３ｃは、Ｐ＋の中に成功したものが存在したか否かを確認する。関数Ｓｅａｒｃｈは、探索に成功した場合に空集合を返すので、成功したものがあればステップＳ１４２の処理で空集合が追加されている。したがって、探索部１３ｃは、失敗パターンの集合が空集合を含むか否かを確認する（ステップＳ１６６）。
【００７１】
失敗パターンの集合が空集合を含む場合に（ステップＳ１６６，Ｙｅｓ）、Ｐを含む完全な埋め込みが存在することを意味するので、探索部１３ｃは、失敗パターンＤを空集合とする（ステップＳ１６７）。失敗パターンの集合が空集合を含まない場合には（ステップＳ１６６，Ｎｏ）、Ｐは探索失敗であるので、パターン抽出部１３ｂは、図１０に示した定理５に基づいて抽出した失敗パターンをＤに代入する（ステップＳ１６８）。
【００７２】
以上の処理の後に、Ｄが空集合でない場合、すなわち、Ｐが失敗であった場合に（ステップＳ１６９，Ｙｅｓ）、パターン抽出部１３ｂは、Ｄを失敗パターンの集合に追加する（ステップＳ１７０）。これにより、またはＤが空集合であった場合に（ステップＳ１６９，Ｎｏ）、関数Ｓｅａｒｃｈは、Ｄを返却して呼び出し元へ戻る。
【００７３】
以上、説明したように、本実施形態の探索装置１は、ラベルが付与された頂点と、隣接する頂点間を接続するエッジとで構成されるグラフのうち、検索対象のデータのグラフであるデータグラフから、検索に使用されるクエリのグラフであるクエリグラフと同型な部分を探索する。その際に、パターン抽出部１３ｂが、探索の過程において発生する探索の失敗に基づいて、クエリグラフの頂点とデータグラフの頂点との組み合わせの集合を、探索の失敗の要因を表す失敗パターンとして抽出する。また、探索部１３ｃが、パターン抽出部１３ｂにより抽出された失敗パターンと合致する探索の状態を枝刈りして、データグラフからクエリグラフと同型な部分を探索する。
【００７４】
これにより、データグラフの中からクエリグラフを含むものを探索するサブグラフマッチング処理を高速化することが可能となる。したがって、例えば、グラフデータ向けに設計されたデータベースであるグラフデータベースに対する、サブグラフマッチングとして記述されるクエリを用いた対話的な作業や、グラフデータベースに依存するサービスを容易に提供できる。また、グラフに対してサブグラフマッチングを用いて、例えば、特定のサブグラフの出現回数をグラフの特徴量として利用するデータマイニングを行う場合に、現実的な時間で完了できる。
【００７５】
なお、ラベルがエッジに付与された場合にも適用できる。すなわち、探索装置１は、頂点と、隣接する頂点間を接続するラベルが付与されたエッジとで構成されるグラフのうち、検索対象のデータのグラフであるデータグラフから、検索に使用されるクエリのグラフであるクエリグラフと同型な部分を探索してもよい。この場合に、パターン抽出部１３ｂは、探索の過程において発生する探索の失敗に基づいて、クエリグラフの頂点とデータグラフの頂点との組み合わせの集合を、探索の失敗の要因を表す失敗パターンとして抽出する。これにより、探索処理を適用できる範囲が拡大する。
【００７６】
［他の実施形態］
上記実施形態において、探索装置１は、失敗パターンの集合の中から部分埋め込みに合致する失敗パターンを探索している（図１２のステップＳ１３２）が、これに限定されない。図１３は、他の実施形態の探索処理を説明するための説明図である。集合の中から特定の条件を満たす要素を探索する作業は、一つ一つの要素を確認する方法では要素の数に比例した処理時間を要し、処理時間が増大する。また、集合に追加される失敗パターンが膨大な数になり得るため、記憶装置に全ての情報を記録できないおそれがある。
【００７７】
そこで、図１３に示すように、失敗パターンをハッシュテーブルによって保持してもよい。この場合に、探索装置１は、部分埋め込みＰに最後に追加した割り当て（ｕｋ，Ｐ［ｕｋ］）と、Ｐから抽出された失敗パターンとを対応付けて記憶部１４に保持する。
【００７８】
これにより、図１２のステップＳ１３２の処理で確認される失敗パターンが一つになるため、処理時間が短縮される。また、ステップＳ１７０の処理において、ハッシュテーブルの値が上書きされ、古い値は保持されないため、記録される失敗パターンの数が減少する。存在し得るクエリ頂点とデータ頂点との組み合わせは、最大でも｜ＶＱ｜｜ＶＧ｜通りである。保持される失敗パターンの数はこれ以下の数となるため、抽出された失敗パターンの全てを保持した場合と比較して、圧倒的に少なくなる。したがって、限られた記憶装置を用いても探索処理を実行することが可能となる。
【００７９】
［プログラム］
上記実施形態に係る探索装置１が実行する処理をコンピュータが実行可能な言語で記述したプログラムを作成することもできる。一実施形態として、探索装置１は、パッケージソフトウェアやオンラインソフトウェアとして上記の探索処理を実行する探索プログラムを所望のコンピュータにインストールさせることによって実装できる。例えば、上記の探索プログラムを情報処理装置に実行させることにより、情報処理装置を探索装置１として機能させることができる。ここで言う情報処理装置には、デスクトップ型またはノート型のパーソナルコンピュータが含まれる。また、その他にも、情報処理装置にはスマートフォン、携帯電話機やＰＨＳ（Personal  Handyphone  System）などの移動体通信端末、さらには、ＰＤＡ（Personal  Digital  Assistants）などのスレート端末などがその範疇に含まれる。また、ユーザが使用する端末装置をクライアントとし、当該クライアントに上記の探索処理に関するサービスを提供するサーバ装置として実装することもできる。例えば、探索装置１は、グラフデータを入力とし、サブグラフマッチング結果を出力する探索処理サービスを提供するサーバ装置として実装される。この場合、探索装置１は、Ｗｅｂサーバとして実装することとしてもよいし、アウトソーシングによって上記の探索処理に関するサービスを提供するクラウドとして実装することとしてもかまわない。以下に、探索装置１と同様の機能を実現する探索プログラムを実行するコンピュータの一例を説明する。
【００８０】
図１４は、探索プログラムを実行するコンピュータの一例を示す図である。コンピュータ１０００は、例えば、メモリ１０１０と、ＣＰＵ１０２０と、ハードディスクドライブインタフェース１０３０と、ディスクドライブインタフェース１０４０と、シリアルポートインタフェース１０５０と、ビデオアダプタ１０６０と、ネットワークインタフェース１０７０とを有する。これらの各部は、バス１０８０によって接続される。
【００８１】
メモリ１０１０は、ＲＯＭ（Read  Only  Memory）１０１１およびＲＡＭ１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０３１に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１０４１に接続される。ディスクドライブ１０４１には、例えば、磁気ディスクや光ディスク等の着脱可能な記憶媒体が挿入される。シリアルポートインタフェース１０５０には、例えば、マウス１０５１およびキーボード１０５２が接続される。ビデオアダプタ１０６０には、例えば、ディスプレイ１０６１が接続される。
【００８２】
ここで、ハードディスクドライブ１０３１は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３およびプログラムデータ１０９４を記憶する。上記実施形態で説明した各テーブルは、例えばハードディスクドライブ１０３１やメモリ１０１０に記憶される。
【００８３】
また、探索プログラムは、例えば、コンピュータ１０００によって実行される指令が記述されたプログラムモジュール１０９３として、ハードディスクドライブ１０３１に記憶される。具体的には、上記実施形態で説明した探索装置１が実行する各処理が記述されたプログラムモジュール１０９３が、ハードディスクドライブ１０３１に記憶される。
【００８４】
また、探索プログラムによる情報処理に用いられるデータは、プログラムデータ１０９４として、例えば、ハードディスクドライブ１０３１に記憶される。そして、ＣＰＵ１０２０が、ハードディスクドライブ１０３１に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して、上述した各手順を実行する。
【００８５】
なお、探索プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０３１に記憶される場合に限られず、例えば、着脱可能な記憶媒体に記憶されて、ディスクドライブ１０４１等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、探索プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ＬＡＮやＷＡＮ（Wide  Area  Network）等のネットワークを介して接続された他のコンピュータに記憶され、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【００８６】
以上、本発明者によってなされた発明を適用した実施形態について説明したが、本実施形態による本発明の開示の一部をなす記述および図面により本発明は限定されることはない。すなわち、本実施形態に基づいて当業者等によりなされる他の実施形態、実施例および運用技術等は全て本発明の範疇に含まれる。
【符号の説明】
【００８７】
１  探索装置
１１  入力部
１２  出力部
１３  制御部
１３ａ  頂点抽出部
１３ｂ  パターン抽出部
１３ｃ  探索部
１４  記憶部
【図１】
2019101610.tif 000012
【図２】
2019101610.tif 000013
【図３】
2019101610.tif 000014
【図４】
2019101610.tif 000015
【図５】
2019101610.tif 000016
【図６】
2019101610.tif 000017
【図７】
2019101610.tif 000018
【図８】
2019101610.tif 000019
【図９】
2019101610.tif 000020
【図１０】
2019101610.tif 000021
【図１１】
2019101610.tif 000022
【図１２】
2019101610.tif 000023
【図１３】
2019101610.tif 000024
【図１４】
2019101610.tif 000025