JP5710539B2 - グラフ生成装置、方法、及びプログラム - Google Patents

Description

本発明は、グラフ生成装置、方法、及びプログラムに係り、特に、グラフを索引構造とする類似探索に使用されるグラフを生成するグラフ生成装置、方法、及びプログラムに関する。

文書、画像、音声音響信号、記号列等の多様で大規模なデータ（被探索オブジェクト集合又は略してオブジェクト集合と呼ぶ）から、与えられたクエリオブジェクトに類似するオブジェクトを高速に見つける探索法に、近傍グラフを索引とする類似探索法（グラフ索引類似探索法と略す）がある。グラフ索引類似探索法に使用されるグラフは、k近傍グラフ（k-nearest neighbor graph又はk-NNグラフと呼ぶ）を基本構造とするグラフが用いられてきた。一般的に、k近傍グラフには、有向グラフ（非特許文献4）と無向グラフがある。無向k近傍グラフを基本構造とするグラフのうち、特に、undirected degree-reduced k-nearest neighbor graph （k-DRグラフ）は、効率的な探索を可能にするグラフである（特許文献1,2、非特許文献1,2）。一方で、グラフを索引とする類似探索法は、探索アルゴリズムとして、複数の初期頂点を用いた貪欲探索（greedy-search, GSと略す）アルゴリズム（multiple starting greedy search algorithm: MSGS algorithm）を用いることで、近似探索法となる（非特許文献3）。近似探索法は、与えられた探索成功確率1-δを達成するように、グラフ構築時に、例えばk近傍グラフが用いられる場合であれば、k-NNグラフ又はk-DRグラフの構造変数kとMSGSアルゴリズムの初期頂点数Lとを決定する。

更に、この近似法は、k-NNやk-DRグラフ以外のグラフにも適用できる汎用法である。前述のグラフ構造変数kは、グラフ中のベイズンサイズを制御する変数であり、グラフのベイズンを推定することで、他のグラフを索引とする場合にも同様の近似法を適用できる。

このように、グラフ索引類似探索法は、与えられた成功確率で、高速に、クエリオブジェクトに最も類似するオブジェクトを見つけることができる。

特許第4774016号公報 特許第4774019号公報

K. Aoyama, K. Saito, T. Yamada, and N. Ueda, "Fast similarity search in small-world networks," Complex Networks: Int. Workshop on Complex Networks, pp. 185-196, Springer, 2009. K. Aoyama, S. Watanabe, H. Sawada, Y. Minami, N. Ueda, and K. Saito, "Fast similarity search on a large speech data set with neighborhood graph indexing," Int. Conf. Acoustics, Speech, Signal Process., pp. 5358-5361, 2010. K. Aoyama, K. Saito, H. Sawada, and N. Ueda, "Fast approximate similarity search based on degree-reduced neighborhood graphs," ACM SIGKDD Conf. Knowledge Discovery and Data Mining, 2011. W. Dong, M. Charikar, and K. Li, "Efficient K-nearest neighbor graph construction for generic similarity measures," Int. World Wide Web Conf. , 2011.

しかしながら、索引であるグラフを構築するために、多大な計算量を必要としていた。これは、グラフ構築時に、予め作成された厳密なk近傍リスト（k-NNリスト）を使用するためである。例えば、n個のオブジェクトから成る距離空間が与えられたとき、k-NNリストを作成するための計算量（距離計算回数で測られる）は、n(n-1)/2であり、計算複雑さは、O(n²)である。この計算量のために、大規模データを対象とした類似探索の索引を構築、変更する際に、多大な時間を要する、という問題があった。

本発明は、上記の問題を解決するためになされたもので、探索成功確率を低下させずに、少ない計算量で、情報探索のために使用されるグラフを生成するグラフ生成装置、方法、及びプログラムを提供することを目的とする。

上記の目的を達成するためにグラフ生成装置は、記憶部に格納されている情報探索集合の情報に対応する頂点における前記頂点間の類似度又は非類似度に基づき頂点間ネットワークを表わすグラフを生成するグラフ生成装置であって、（ａ１）前記情報探索集合の情報に対応する頂点の何れか一つをターゲット頂点として設定すると共に、前記情報探索集合の情報に対応する頂点の少なくとも１つを、初期頂点としてランダムに設定し、（ａ２）前記（ａ１）で設定したターゲット頂点をクエリとして、所定の探索アルゴリズムに従って、前記（ａ１）で設定された前記初期頂点から、前記クエリに類似する頂点を探索し、（ａ３）前記（ａ２）の結果、前記探索結果として得られた頂点が前記ターゲット頂点でない場合に、前記ターゲット頂点に辿り着く頂点集合内の何れか一つの頂点と、前記探索結果として得られた頂点とをリンク結合し、（ａ４）前記（ａ１）から前記（ａ３）の処理を、所定の第１条件が満たされるまで繰り返し、前記（ａ１）から前記（ａ４）の処理を、所定の第２条件が満たされるまで繰り返すことにより、前記グラフを生成し、前記生成したグラフを、前記記憶部に格納するグラフ生成部を含んで構成されている。

本発明に係るグラフ生成方法は、記憶部に格納されている情報探索集合の情報に対応する頂点における前記頂点間の類似度又は非類似度に基づき頂点間ネットワークを表わすグラフを生成するグラフ生成装置におけるグラフ生成方法であって、（ａ１）前記情報探索集合の情報に対応する頂点の何れか一つをターゲット頂点として設定すると共に、前記情報探索集合の情報に対応する頂点の少なくとも１つを、初期頂点としてランダムに設定し、（ａ２）前記（ａ１）で設定したターゲット頂点をクエリとして、所定の探索アルゴリズムに従って、前記（ａ１）で設定された前記初期頂点から、前記クエリに類似する頂点を探索し、（ａ３）前記（ａ２）の結果、前記探索結果として得られた頂点が前記ターゲット頂点でない場合に、前記ターゲット頂点に辿り着く頂点集合内の何れか一つの頂点と、前記探索結果として得られた頂点とをリンク結合し、（ａ４）前記（ａ１）から前記（ａ３）の処理を、所定の第１条件が満たされるまで繰り返し、前記（ａ１）から前記（ａ４）の処理を、所定の第２条件が満たされるまで繰り返すことにより、前記グラフを生成し、前記生成したグラフを、前記記憶部に格納する。

本発明によれば、所定の探索アルゴリズムに従って探索結果として得られた頂点がターゲット頂点でない場合に、ターゲット頂点に辿り着く頂点集合内の何れか一つの頂点と、探索結果として得られた頂点とをリンク結合することを繰り返すことにより、探索成功確率を低下させずに、少ない計算量で、情報探索のために使用されるグラフを生成することができる。

本発明に係るプログラムは、上記のグラフ生成装置の各手段としてコンピュータを機能させるためのプログラムである。

以上説明したように、本発明のグラフ生成装置、方法、及びプログラムによれば、所定の探索アルゴリズムに従って探索結果として得られた頂点がターゲット頂点でない場合に、ターゲット頂点に辿り着く頂点集合内の何れか一つの頂点と、探索結果として得られた頂点とをリンク結合することを繰り返すことにより、探索成功確率を低下させずに、少ない計算量で、情報探索のために使用されるグラフを生成することができる、という効果が得られる。

グラフ索引類似探索法を説明するための図である。 ＧＳアルゴリズムを説明するための図である。 本発明の第１の実施の形態に係るグラフ生成装置の構成を示す概略図である。 ＦＡＢアルゴリズムを説明するための図である。 ＦＡＢアルゴリズムを説明するための図である。 本発明の第１の実施の形態に係るグラフ生成装置におけるＦＡＢグラフ構築処理ルーチンの内容を示すフローチャートである。 本発明の第２の実施の形態に係るグラフ生成装置のグラフ構築部の構成を示す概略図である。 本発明の第２の実施の形態に係るグラフを生成する方法の流れを説明するための図である。 NN-Descentアルゴリズムを説明するための図である。 本発明の第２にお実施の形態に係るグラフ生成装置のＫ−ＮＮリスト生成処理ルーチンの内容を示すフローチャートである。 本発明の第２にお実施の形態に係るグラフ生成装置のｋ−ＤＲグラフ生成処理ルーチンの内容を示すフローチャートである。 データサイズと距離計算回数との関係を示すグラフである。 繰り返し回数と距離計算回数との関係を示すグラフである。 探索成功率とそのFABグラフを構築するのに要したスキャンレートとの関係を示すグラフである。 探索成功率と探索コストとの関係を示すグラフである。

以下、図面を参照して本発明の実施の形態を詳細に説明する。

＜概要＞
まず、本発明の概要について説明する。

本発明においてグラフの生成に用いる方法は、フォールスアトラクタブリッジング（false-attractor bridging: FABと略す）である。FABアルゴリズムは、ある空間（非類似度が定義されたオブジェクト集合）から作られたグラフの初期状態（オブジェクトを頂点とみなす、リンクのないグラフを含む）が与えられたとき、グラフ内のある頂点に対し、MSGSを実行し、GSアルゴリズムの終了頂点（アトラクタと呼ぶ）と当該グラフ内のある頂点のベイズン（ベイズンとは、グラフ内の辺をGSアルゴリズムで辿り、当該グラフ内のある頂点へ到達する頂点の集合である）内のある頂点とをリンクで連結することにより、グラフにリンクを追加しながら、グラフを成長させるアルゴリズムである。

また、図１を用いて、グラフ索引類似探索法を簡単に説明する。オブジェクト集合（Object set）と非類似度（Dissimilarity）とから成る空間が与えられる。この空間に対し、グラフ構築アルゴリズム（Graph construction algorithm）を適用し、グラフ索引（Graph index）を構築する。特に、グラフとしてランクに基づくk-NNグラフを基本とするグラフを用いる。従来法では、グラフ構築アルゴリズムには、空間から作成された厳密なk-NNリストが与えられる。このリストを参照しながら、各オブジェクトに最も類似するオブジェクトからk個のオブジェクトにリンクを生成し、無向リンクに置換したグラフがk-NNグラフである。このとき、グラフの各頂点（Vertex）は各オブジェクト（Object）に対応し、その関係性（k近傍以内）がリンクで表される。以降、オブジェクトと頂点とは、言葉の意味上、区別なく使用する。また、無向リンク（無向辺）のことを単にリンク（辺）とも呼ぶ。

また、上記特許文献2、上記非特許文献1,2に示されるｋ-DRグラフを構築するアルゴリズム（DRアルゴリズム）も同様にk-NNリストを使用する。

このグラフ上を探索する際に、MSGSアルゴリズムを用いる。これにより近似探索が可能になる。

また、図２（Ａ）〜（Ｃ）を参照しながら、GSアルゴリズムについて述べる。GSアルゴリズムとは、現頂点の隣接頂点のなかで、現頂点よりもクエリに近い頂点があれば、その近い頂点に移動し、近い頂点がなければ終了するというアルゴリズムである。例えば、10個のオブジェクトからユークリッド距離を用いて構築された10頂点からなる2-NNグラフに、クエリqが与えられる。図２（Ａ）は、初期頂点としてｂが選択され、bとqとの距離が計算される。次に、bの隣接頂点a,cとqとの距離が計算され、bよりもｑに近いcを展開頂点とする。ここで展開頂点とは、自らとクエリとの距離が計算されており、隣接頂点とクエリとの距離も計算される（されている）頂点のことである。図２（Ｂ）では、展開頂点cの隣接頂点とクエリとの距離が計算されている。展開頂点が、より近い頂点dに移動する。図２（Ｃ）では、頂点dの隣接頂点とqとの距離が計算される。頂点ｄが最近傍頂点であるから、GSアルゴリズムは終了する。

MSGSアルゴリズムは、初期頂点として複数頂点を用いて各々が独立にGSアルゴリズムを実行し、複数の終了頂点の全て、又はそのうちで最近傍頂点やトップk個などの指定された頂点を返す。

〔第１の実施の形態〕
＜システム構成＞
図３に示すように、第１の実施の形態に係るグラフ生成装置１００は、ＣＰＵと、ＲＡＭと、後述するＦＡＢグラフ構築処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたコンピュータで構成され、機能的には次に示すように構成されている。

グラフ生成装置１００は、探索されるオブジェクト集合の入力を受け付ける入力部１０と、グラフを生成すると共に探索処理を行う演算部２０と、探索結果を出力する出力部３０と、を備えている。

演算部２０は、オブジェクトデータベース２１、グラフ構築部２２、グラフ索引記憶部２３、及び探索処理部２４を備えている。グラフ構築部２２は、グラフ生成部の一例である。

オブジェクトデータベース２１は、入力部１０より入力されたオブジェクトの集合を記憶すると共に、入力部１０より入力された、オブジェクト間の距離（又は類似度又は非類似度）の定義を記憶する。なお、オブジェクト集合が、情報探索集合の一例であり、オブジェクトが、情報の一例である。また、オブジェクトデータベース２１及びグラフ索引記憶部２３は、記憶部の一例である。

グラフ構築部２２は、オブジェクトデータベース２１に記憶されたオブジェクト集合及びオブジェクト間の距離の定義に基づいて、オブジェクト集合を探索するためのグラフを生成する。

グラフ索引記憶部２３は、グラフ構築部２２によって生成されたグラフを索引として記憶する。

探索処理部２４は、グラフ索引記憶部２３に記憶されたグラフを索引として用いて、入力部１０より入力されたクエリオブジェクトに類似するオブジェクトを、オブジェクトデータベース２１に記憶されたオブジェクト集合の中から探索する。探索結果として得られるオブジェクトは、出力部３０により、ユーザに対して出力される。

次に、本実施の形態においてグラフを構築する原理について説明する。本実施の形態では、ＦＡＢアルゴリズムを用いて、グラフを構築する。

図４（Ａ）〜（Ｃ）にFABアルゴリズムの概念図を示す。ある空間χ=(X,D)が与えられる。ここで、Xはオブジェクト集合、Dはオブジェクト集合の要素であるオブジェクト間に定義された非類似度とし、D(x,y)と記載した場合は、オブジェクト（又は頂点）xからオブジェクト(頂点)yへの非類似度を表す。χが距離空間である場合は、非類似度は距離であり、D(x,y)=D(y,x)である。

ある頂点x∈Xに対して、ある初期頂点集合X0⊆Xを選択する。頂点xをクエリ（Query: q）とし、x=q、X0を用いて、後述するMSGSアルゴリズムを実行する。このとき、qに最も類似するオブジェクト、即ち、qから最も近い頂点（Target: ターゲット x*(q)）はq自身であり、初期頂点集合のうちのいくつかからスタートしたGSアルゴリズムはターゲットに辿りつくかも知れない。また、他のGSアルゴリズムはターゲットに辿りつかず、終了する。

ここで、ある頂点xに対するGSアルゴリズムが終了する頂点を頂点xのアトラクタと呼ぶ。また、頂点xが自明な場合は省略して、単に、アトラクタと呼ぶ。アトラクタには、真のアトラクタ（true attractor: TA）と偽のアトラクタ（false attractor: FA）がある。TAとはターゲットのことである。グラフΓにクエリqが与えられたとき、TAに辿りつく頂点集合を、クエリq、ターゲットx*(q)のベイズン（Basin(q,x*(q);Γ）と呼び、FAに辿りつく頂点集合を、q, FAのフォールスベイズンと呼ぶ。FABアルゴリズムとは、フォールスアトラクタのうちの少なくとも1つとベイズンのうちの少なくとも1つの頂点とをリンクで連結するアルゴリズムである。

図４（Ａ）は、グラフ上の頂点をクエリとした場合、即ちq=x*(q)の場合のベイズンと、フォールスアトラクタ及びフォールスベイズンとを表した図である。図４（Ｂ）は、フォールスアトラクタの１つとベイズンの要素である頂点の１つとをリンク結合した（ブリッジングした）場合の図（図中、Bridgeで表されるリンクを生成）である。このリンク結合によりベイズンは、元のベイズンとリンク結合されたフォールスアトラクタのフォールスベイズンとの集合和（合併集合）になる。ベイズンサイズが大きくなることは、上記の非特許文献３に記載の近似アルゴリズムから分かるように、探索成功率を向上させる。図４（Ｃ）は、フォールスアトラクタのうち、ターゲットから最も近いもの（図中、closestと表現）を選び、ベイズンの要素の１つであるターゲットに直接リンク結合した場合の図である。このようなリンク結合の他に、最大フォールスベイズンを有すると推定されたフォールスアトラクタとベイズン内の頂点又はターゲット自体とをリンク結合する方法などもある。

ここで、MSGSアルゴリズムについて説明する。MSGSアルゴリズムとは、multiple starting greedy search algorithmであり、上記の非特許文献3で提案されたアルゴリズムであり、greedy search algorithm with multiple initial vertices（複数初期頂点を有する貪欲探索法）とも呼ぶ。グラフ上の貪欲探索（greedy search: GSと略す）法は、クエリ頂点が与えられたとき、以下の（１）〜（３）の手続きを実行する。

（１）ある初期頂点（starting vertex, initial vertex）x0を選択し、クエリ頂点qとの非類似度（又は距離）Ｄ(q,x0)を計算する。初期頂点を展開頂点とする。展開頂点とは、その頂点と隣接頂点とについて、クエリ頂点との非類似度が計算された（または、今計算するところの）頂点のことである。

（２）展開頂点の隣接頂点（リンクで接続された頂点）とクエリ頂点との非類似度を計算する。

（３）Ｄ(q,x0)より小さい値を持つ隣接頂点がなければ、終了する。Ｄ(q,x0)より小さい値を持つ隣接頂点があれば、その頂点を展開頂点yとし、上記（２）の手続きに戻る。

但し、上記（１）、（２）のクエリ頂点と隣接頂点との非類似度計算においては、本実施の形態では全ての隣接頂点と非類似度計算を行って、その中で最小値をもつ頂点を次の展開頂点とした。この代わりに、現在の展開頂点とクエリとの非類似度よりも小さい非類似度を示す頂点が見つかったとき、直ちにその頂点を展開頂点としてもよい。

MSGSアルゴリズムは、複数の初期頂点の各々からGSアルゴリズムを実行するアルゴリズムである。本実施の形態では、初期頂点を複数設けているが、初期頂点が1つであっても構わない。また、FABアルゴリズムの中で使用される場合は、FABアルゴリズムの実行時に、アルゴリズムの進行に従って、動的に頂点数を変えても良い。例えば、ある程度の頂点数を保つ、又は、開始時から徐々に少なくする、という頂点選択法が好ましい。

また、本実施の形態では、MSGSアルゴリズムを用いたが、MSGSアルゴリズム以外の他の方法も採用可能であり、例えば、最良優先探索法などにより複数のアトラクタを抽出することもできる。

図５（Ａ）〜（Ｃ）に具体例を挙げる。１２個の頂点にユークリッド距離が定義された空間が与えられ、リンクが図５（Ａ）のように張られている。頂点gをクエリとする。このとき、ベイズンは、{ g, a, b, c, f, h }の6つの頂点からなる集合である。また、全頂点を初期頂点としたMSGSアルゴリズムを実行すると、図５（Ｂ）のように、３つのフォールスアトラクタを抽出できる。フォールスアトラクタ集合は、{e, i, m}である。頂点eのフォールスベイズンは{d,e}、頂点iのフォールスベイズンは{i,j,k}、頂点mのフォールスベイズンは{m}である。今、ターゲットとターゲットから最近傍のフォールスアトラクタとを連結するFABアルゴリズムを採用すると、図５（Ｃ）に示すように、ベイズンは、{ g, a, b, c, f, h }∪{d,e}であり、ベイズンサイズは2だけ大きくなる。

FABアルゴリズムの一例では、この１つのターゲット頂点に対する操作を、グラフ内の全頂点に対して実行する。FABアルゴリズムが繰り返されることによって、ベイズンサイズは大きくなり、MSGSアルゴリズムによる探索成功率は向上する。

探索処理部２４は、グラフ索引記憶部２３に記憶されたグラフを索引として用い、入力されたクエリに類似するオブジェクトを探索する。このとき、オブジェクト集合から、複数の初期頂点がランダムに設定され、ＭＳＧＳアルゴリズムによって、各初期頂点について１つずつ最近傍となるオブジェクト（クエリに最も類似するオブジェクト）が、探索結果として得られる。そして、各初期頂点について得られた最近傍オブジェクトの集合が、出力部３０により出力される。

＜グラフ生成装置の動作＞
次に、本実施の形態に係るグラフ生成装置１００の作用について説明する。まず、オブジェクト集合及びオブジェクト間の非類似度の定義が入力部１０を介してグラフ生成装置１００に入力されると、オブジェクト集合及びオブジェクト間の非類似度の定義が、オブジェクトデータベース２１に格納される。そして、グラフ生成装置１００において、図６に示すＦＡＢグラフ構築処理ルーチンが実行される。

まず、ステップＳ１０１において、オブジェクトデータベース２１からオブジェクト集合を取得すると共に、グラフの初期状態として、ベースグラフを設定する。本実施の形態では、オブジェクト集合の各々を頂点とみなすリンクのないグラフを、ベースグラフとして設定する。

そして、ステップＳ１０２において、繰り返し回数を示す変数ｉｔｅｒに初期値１を設定する。次のステップＳ１０４では、オブジェクト集合に対応する全頂点から、ターゲットとなる頂点を１つだけ設定すると共に、オブジェクト集合に対応する全頂点から、複数の初期頂点をランダムに設定する。

ステップＳ１０５において、上記ステップＳ１０４で設定した初期頂点の各々から、ＧＳアルゴリズムに従って、上記ステップＳ１０４で設定されたターゲットの頂点に類似する頂点を探索する処理を行う。これによって、初期頂点の各々に対してアトラクタが得られる。

そして、ステップＳ１０６において、上記ステップＳ１０５で得られたアトラクタと、ターゲットの頂点とを比較して、フォールスアトラクタがあるか否かを判定する。全てのアトラクタが、ターゲットの頂点と一致する場合には、後述するステップＳ１０８へ移行する。一方、少なくとも１つのアトラクタが、ターゲットの頂点と一致しない場合には、ステップＳ１０７で、グラフに対して、フォールスアトラクタのうちの何れか１つと、ターゲットの頂点のベイジン内の頂点とを結合するリンクを追加する。

ステップＳ１０８では、全ての頂点をターゲットとして上記ステップＳ１０４〜ステップＳ１０７の処理を実行したか否かを判定する。ターゲットして設定していない頂点が存在する場合には、上記ステップＳ１０４へ戻り、当該頂点をターゲットとして設定する。一方、全ての頂点をターゲットとして上記ステップＳ１０４〜ステップＳ１０７の処理を実行した場合には、ステップＳ１０９へ移行する。

そして、ステップＳ１０９において、繰り返し終了条件を満足したか否かを判定する。繰り返し終了条件は、例えば、繰り返し変数ｉｔｅｒが、予め決めておいた繰り返し回数になったことである。繰り返し終了条件を満足していない場合には、ステップＳ１１０において、変数ｉｔｅｒを１インクリメントして、上記ステップＳ１０４へ戻る。一方、繰り返し終了条件を満足する場合には、ステップＳ１１１において、最終的に得られたグラフを、ＦＡＢグラフ（FABアルゴリズムで構築したグラフのことをFABグラフと呼ぶ）としてグラフ索引記憶部２３に格納して、ＦＡＢグラフ構築処理ルーチンを終了する。

そして、クエリオブジェクトが入力部１０を介してグラフ生成装置１００に入力されると、グラフ生成装置１００の探索処理部２４によって、グラフ索引記憶部２３に記憶されたグラフを索引として用い、入力されたクエリオブジェクトに類似するオブジェクトを探索し、探索結果として得られるオブジェクトを、出力部３０により出力する。

〔第２の実施の形態〕
＜システム構成＞
次に、第２の実施の形態について説明する。なお、第１の実施の形態と同様の構成となる部分については、同一符号を付して説明を省略する。

第２の実施の形態では、ベースグラフを生成してから、ＦＡＢアルゴリズムを適用している点が、第１の実施の形態と異なっている。

第２の実施の形態に係るグラフ生成装置１００のグラフ構築部２２は、図７に示すように、Ｋ−ＮＮリスト生成部２２１、ｋ−ＤＲグラフ構築部２２２、及びＦＡＢグラフ構築部２２３を備えている。

第２の実施の形態における、グラフを生成する手続き全体を図８に示す。本実施の形態では、近似Ｋ−ＮＮリストを利用する。効率的に近似Ｋ−ＮＮリストを作成するアルゴリズムにNN-Descentアルゴリズムがある（非特許文献4）。NN-Descentアルゴリズムは、オブジェクト集合のサイズ（又は、データサイズ）に対して適切なKを選択したとき、経験的に厳密なＫ−ＮＮリストに対するリコールが高い近似Ｋ−ＮＮリストを作成する。適切なKはデータサイズが大きくなるほど、データの固有次元（intrinsic dimensionality）が高くなるほど、大きくなる。NN-Descentアルゴリズムの計算量は、データサイズn、リスト変数Kに対して、O(K^1.5〜1.8n^1.1)であることが経験的に分かっている。

本実施の形態では、小さいKを用いるNN-Descentアルゴリズムにより、与えられた空間から近似Ｋ−ＮＮリストを作成し、このリストを参照するDRアルゴリズムにより、k-DRグラフを構築する。

このk-DRグラフを、FABアルゴリズムの初期状態であるベースグラフとして用いる。FABアルゴリズムを繰り返すことにより、所定の探索成功率を満たすFABグラフを構築する。

Ｋ−ＮＮリスト生成部２２１は、オブジェクトデータベース２１に記憶されたオブジェクト集合及びオブジェクト間の距離の定義に基づいて、NN-Descentアルゴリズム（非特許文献４）に従って、オブジェクト集合の各オブジェクトについて、K近傍を求めた近似Ｋ−ＮＮリストを生成する。

非特許文献4に示されるようにNN-Descentアルゴリズムには、基本形（basic）と完全形(full)とがある。ここでは、簡単のために基本形について図９を用いて説明する。完全形も同様に利用することができる。ある空間が与えられたとき、NN-Descentアルゴリズムは、この空間の各頂点に対するK近傍を求めた近似Ｋ−ＮＮリストを作成する問題を解く。

NN-Descentアルゴリズムは、空間の各頂点が、Kアウトエッジ(out-edge)を有するランダムグラフを作成する。ここで、ある1つの頂点に着目し、説明を進める。ある頂点xのアウトエッジで接続されたK個の隣接頂点y1,y2,…,、及びその隣接頂点（アウトエッジ接続とインエッジ接続との両方を含む、即ち、リンクを無向リンクとみなしたときの隣接頂点）zの各々と、頂点xとの距離（一般的には非類似度であるが、簡単のために距離で説明する）を計算し（図９（Ａ）参照）、最も近い頂点からK個の頂点を選択し、次にリンクを張る候補頂点y’とする（図９（Ｂ）参照）。

この操作を全ての頂点に順次実行する。全ての頂点に対する実行が終了した時点で、各頂点のリンクを候補頂点y’へ張り替える。この操作を、全ての頂点に対するK個の隣接頂点が変わらなくなるまで繰り返す。全ての頂点のK個の隣接頂点が不変になったとき、アルゴリズムは終了し、各頂点に対してＫ近傍（最も近い隣接頂点からＫ個の隣接頂点）を格納した近似Ｋ−ＮＮリストが生成される。

Ｋ−ＤＲグラフ構築部２２２は、NN-Descentアルゴリズムで作成した厳密ではない近似Ｋ−ＮＮリストを用いて、K-DRグラフを作成する。手続きは、上記図８に示すように、NN-DescentアルゴリズムとDRアルゴリズムとをシリアル接続した構成になる。DRアルゴリズムは、上記の非特許文献1,2に記載されているアルゴリズムと同様である。

ＦＡＢグラフ構築部２２３は、DRアルゴリズムで作成したＫ−ＤＲグラフをベースグラフとして、ＦＡＢアルゴリズムに従ってリンクを追加することを繰り返し、ＦＡＢグラフを生成する。

＜グラフ生成装置の動作＞
次に、本実施の形態に係るグラフ生成装置１００の作用について説明する。まず、オブジェクト集合及びオブジェクト間の非類似度の定義が入力部１０を介してグラフ生成装置１００に入力されると、オブジェクト集合及びオブジェクト間の非類似度の定義が、オブジェクトデータベース２１に格納される。そして、グラフ生成装置１００において、図１０に示すＫ−ＮＮリスト生成処理ルーチンが実行される。

まず、ステップＳ２０１で、オブジェクトデータベース２１からオブジェクト集合を取得すると共に、オブジェクト集合の各々のオブジェクトを頂点として、各頂点ｘについて、Ｋ個の隣接頂点をランダムにサンプリングして決定する。

そして、ステップＳ２０２において、処理対象の頂点ｘを設定する。ステップＳ２０３において、頂点ｘのＫ個の隣接頂点、及び当該Ｋ個の隣接頂点の隣接頂点の各々について、頂点ｘとの距離を計算する。ステップＳ２０４では、頂点ｘのＫ個の隣接頂点、及び当該Ｋ個の隣接頂点の隣接頂点から、最も近い頂点からＫ個の頂点を選択し、候補頂点とする。

そして、ステップＳ２０５において、全ての頂点に対して、上記ステップＳ２０２〜Ｓ２０４の処理を実行したか否かを判定する。上記ステップＳ２０２〜Ｓ２０４の処理を実行していない頂点が存在する場合には、上記ステップＳ２０２へ戻り、当該頂点を、処理対象の頂点ｘとして設定する。一方、全ての頂点に対して、上記ステップＳ２０２〜Ｓ２０４の処理を実行した場合には、ステップＳ２０６へ移行する。

ステップＳ２０６では、各頂点ｘについて、上記ステップＳ２０４で得られた候補頂点へリンク結合されるように、リンクを張り替える。ステップＳ２０７では、上記ステップＳ２０６の処理により変化があったか否かを判定する。上記ステップＳ２０６においてリンクの張り替えがあり変化があった場合には、上記ステップＳ２０２へ戻る。一方、上記ステップＳ２０６においてリンクの張り替えがなく、変化がなかった場合には、ステップＳ２０８へ移行する。

ステップＳ２０８では、各頂点について得られたＫ個の隣接頂点を格納した近似Ｋ−ＮＮリストを生成して、処理ルーチンを終了する。

そして、グラフ生成装置１００において、図１１に示すｋ−ＤＲグラフ生成処理ルーチンが実行される。

まず、ステップＳ２１１において、上記で生成された近似Ｋ−ＮＮリストに基づいて、オブジェクト集合中におけるすべての頂点ｘに対する１−ＤＲグラフΓ（ｘ）を求める。１−ＤＲグラフΓ（ｘ）は、以下の（１）式で示される要素である。

ここで、Ｎ１（ｘ）は、任意の頂点ｘに対して、最も非類似度が小さい頂点である。

すなわち、頂点ｘ（ｘ∈Ｘ、Ｘはオブジェクト集合）との非類似度が最も小さい近傍頂点Ｎ１（ｘ）を、オブジェクト集合中から求め、この近傍頂点Ｎ１（ｘ）との間に無向リンクを生成する。

そして、任意の頂点ｘに対する１−ＤＲグラフΓ（ｘ）を抽出する。

次に、ステップＳ２１２において、出次数ｋ（以下、適宜ｋと記載）を２に設定する（ｋ←２）。ステップＳ２１３では、ｋが予め設定してある値ｎと等しいか否かを判定する。ｎは、グラフ生成のパラメータであり、Ｋ以下である。

上記ステップＳ２１３の結果、ｋがｎと等しい場合、ステップＳ２１４において、取得した各頂点ｘに対するｋ−ＤＲグラフΓ（ｘ）を、ｋ−ＤＲグラフとしてメモリ（図示省略）に記憶する。

一方、上記ステップＳ２１３の結果、ｋがｎと等しくない場合、ステップＳ２１５において、近似Ｋ−ＮＮリストに基づいて、頂点ｘに対する近傍頂点集合Ｎｋ（ｘ）および近傍頂点集合Ｎｋ−１（ｘ）を求める。

そして、ステップＳ２１６において、求めた近傍頂点集合Ｎｋ（ｘ）と、近傍頂点集合Ｎｋ−１（ｘ）との差集合である頂点ｙを求める（ｙ＝Ｎｋ（ｘ）−Ｎｋ−１（ｘ））。すなわち、頂点ｘからｋ番目に非類似度の小さい頂点ｙを、オブジェクト集合に対応する頂点の中から抽出する。

そして、ステップＳ２１７において、ＧＳアルゴリズムに従って、頂点ｙを初期頂点とし、頂点ｘをクエリとして、頂点ｘに類似する頂点ｘ＊を探索する。ステップＳ２１８では、上記ステップＳ２１７におけるＧＳアルゴリズムに基づく探索処理の結果、出力された頂点ｘ＊が、頂点ｘと等しい（ｘ＝ｘ＊）か否かを判定する。すなわち、ＤＲグラフΓにおいて、頂点ｘおよび頂点ｙに対してＧＳアルゴリズムによる探索処理を行うことをＧＳ（ｘ，ｙ，Γ）で表すと、ステップＳ２１８は、ｘ＝ＧＳ（ｘ，ｙ，Γ）が、真であるか否かを判定することになる。

上記ステップＳ２１８の結果、頂点ｘ＊が、頂点ｘと等しい場合、ステップＳ２２１へ移行する。すなわち、新たなリンクを生成しない。

上記ステップＳ２１８の結果、頂点ｘ＊が、頂点ｘと等しくない場合、ステップＳ２１９において、以下の（２）式を満たす要素ｚを求める。すなわち、近傍頂点集合Ｎｋ−１（ｘ）と、要素ｘとの和集合のうちで、最も頂点ｙとの非類似度が小さい頂点ｚを求める。

そして、ステップＳ２２０において、以下の（３）式を実行することによって、頂点ｚと頂点ｙとの間に新しいリンクを生成する。

すなわち、頂点ｚを頂点ｙに対する（ｋ−１）−ＤＲグラフΓ（ｙ）に加え、頂点ｙを頂点ｚに対する（ｋ−１）−ＤＲグラフΓ（ｚ）に加えることで、頂点ｙと頂点ｚとの間に、無向リンクを生成する。これにより、頂点ｙと、頂点ｘに直接的にリンク結合している頂点ｘ以外の頂点ｚとを、直接的にリンク結合する。

そして、ステップＳ２２１において、オブジェクト集合に対応するすべての頂点ｘに対して、上記ステップＳ２１５からステップＳ２２１の処理を行ったか否かを判定する。

上記ステップＳ２２１の結果、すべての頂点ｘに対して、処理を行っていない場合、新たな頂点ｘを取得し、ステップＳ２１５の処理へ戻る。

一方、上記ステップＳ２２１の結果、すべての頂点ｘに対して、処理を行った場合、ステップＳ２２２において、ｋを１だけインクリメントして、上記ステップＳ２１３の処理へ戻る。

この時点におけるグラフΓ（ｘ）は、ステップＳ２１９およびステップＳ２２０の処理の実行の有無にかかわらずｋ−ＤＲグラフとする。

そして、グラフ生成装置１００において、上記図６に示すＦＡＢグラフ構築処理ルーチンが実行される。このとき、上記ステップＳ１０１では、ベースグラフとして、上記で生成されたｋ−ＤＲグラフが設定される。

＜実験例＞
次に、上記第２の実施の形態で提案したグラフ生成方法を、大規模文書データに適用し、有効性を確認した。大規模文書データから成る空間は、The New York Times（登録商標）の記事（文書）からtf-idfに基づき作成された高次元スパースベクトルを特徴ベクトルとし、特徴ベクトル間にはコサイン類似度が定義された空間である。オブジェクト集合として、1,285,944件、116,905件、11,691件、1,170件の記事から抽出された特徴ベクトル集合（各々、1-M-size データ、100-K-size データ、10-K-size データ、1-K-size データと呼ぶ）を用いた。上記図８に示すように、まず初めにK=20に設定したNN-Descentアルゴリズムで20-NNリストを作成した。次に、20-NNリストを用いてDRアルゴリズムで、20-DRグラフを構築した。

この20-DRグラフをFABアルゴリズムのベースグラフとして用い、MSGSアルゴリズムのL_B個の初期頂点をシンプルランダムサンプリングで選び、FABアルゴリズムを10回繰り返し、FABグラフを構築した。

図１２、１３は、L_B=20に設定し実験した結果である。

図１２は、横軸にデータサイズ、縦軸にグラフ構築のために要した距離計算回数を表している。距離計算回数は、ベースグラフを基に、1回目の繰り返し（図中iter1）、2回目の繰り返し（図中 iter2）、3回目の繰り返し（図中 iter3）の各繰り返し時の計算回数を表している。この図から、計算量が概ねO(n^1.1〜1.2)であることが分かる。但し、nはデータサイズを表す。これは、非常に小さい計算量でグラフ構築に成功していることを表している。

図１３は、繰り返し回数に対する距離計算回数を表している。図中、上から順に、1-M-size, 100-K-size, 10-K-size, 1-K-sizeデータの結果を表す。全てのデータサイズにおいて、繰り返し回数に対する距離計算回数の増加は小さいことがわかる。これは、NN-DescentアルゴリズムがKに関してO(K^1.5〜1.8)の計算量であったのとは、対照的であり、繰り返しに対しても良好な性質があるといえる。

次に、低計算量で構築したFABグラフが探索に対しても有効であること示す。実験には、1-M-sizeデータから構築されたFABグラフ用いた。初期頂点数LsをLｓ=32に設定し、その初期頂点を無作為に選択したMSGSアルゴリズムを、12,989個の異なるクエリに対して実行した。探索性能としては、探索成功率を用いた。探索成功率とは、MSGSアルゴリズムを実行した結果、少なくとも1つのGS試行がターゲットに辿り着いた探索試行の回数の全試行回数に対する比である。図１４は、探索成功率とそのFABグラフを構築するのに要したスキャンレートとの関係を表す図である。ここで、スキャンレートとは、実際に要した距離計算回数（# similarity calculations）の力任せ法（brute-force method, linear scan method）で要する距離計算回数に対する比であり、与えられる空間が距離空間である場合は、以下の式で表される。

Scan rate = (# similarity calculations )/{n(n-1)/2}

参考のために、K-DRグラフを索引構造とした場合の性能も図中（ＤＲと表記）に表示している。図中のL_Bは、FABアルゴリズムのための初期頂点数であり、1，10，20，50,100の場合の性能を、FABアルゴリズムの繰り返し回数の昇順に（iter1, iter2, …）記載している。上記図１４から、1回目のFABアルゴリズムで構築したFABグラフにより、探索成功率が大幅に向上していることが分かる。このように、僅かな計算コストで構築したFABグラフであっても、探索性能が著しく向上した。

最後に、探索性能（探索成功率と探索コスト）に関し、FABグラフを用いた場合とK-DRグラフを用いた場合とを比較した結果を、図１５に示す。FABグラフを用いた場合の探索コストは、K-DRグラフを用いた場合に比べて、同一の探索成功率であって、探索成功率が0.8以下の小さい領域で僅かに高い。しかしながら、探索成功率が0.9以上の高い領域においては、K-DRグラフを用いた場合を外挿した値とほぼ同等であった。

以上説明したように、上記の実施の形態に係るグラフ生成装置によれば、選択された初期頂点から貪欲探索アルゴリズムに従って探索結果として得られた頂点がターゲット頂点でない場合に、ターゲット頂点に辿り着くベイズン内の何れか一つの頂点と、探索結果として得られた頂点とをリンク結合するＦＡＢアルゴリズムを繰り返し実行することにより、探索成功確率を低下させずに、少ない計算量で、情報探索のために使用されるＦＡＢグラフを生成することができる。

また、厳密なk-NNリストを作成することなく、経験的に計算量O(n^1.1)でグラフ索引を構築できるため、計算量を大幅に低減できる。このため、グラフ索引類似探索法を大規模データに容易に適用できる。

なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。

例えば、オブジェクト集合の空間において、非類似度ではなく、類似度を定義するようにしてもよい。

また、近似Ｋ−ＮＮリストを、NN-Descentアルゴリズムに従って生成する場合を例に説明したが、これに限定されるものではなく、他のアルゴリズムに従って、厳密でない近似Ｋ−ＮＮリストを生成するようにしてもよい。

また、FABアルゴリズムでは、グラフ内の全頂点の各々をターゲット頂点として実行する場合を例に説明したが、これに限定されるものではない。グラフ内の頂点の部分集合の各々をターゲット頂点として、ＦＡＢアルゴリズムを実行してもよい。この場合には、ＦＡＢアルゴリズムの繰り返し毎に、ターゲットとする頂点の部分集合を変えても良い。例えば、ｉｔｅｒ＝１のときは、偶数番号が付された頂点の各々をターゲット頂点として、ＦＡＢアルゴリズムを実行し、ｉｔｅｒ＝２のときは、奇数番号が付された頂点の各々をターゲット頂点として、ＦＡＢアルゴリズムを実行するようにしてもよい。

上述のグラフ生成装置は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。

また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。

１０ 入力部
２０ 演算部
２１ オブジェクトデータベース
２２ グラフ構築部
２３ グラフ索引記憶部
２４ 探索処理部
３０ 出力部
１００ グラフ生成装置
２２１ Ｋ−ＮＮリスト生成部
２２２ ｋ−ＤＲグラフ構築部
２２３ ＦＡＢグラフ構築部

Claims (7)

1. 記憶部に格納されている情報探索集合の情報に対応する頂点における前記頂点間の類似度又は非類似度に基づき頂点間ネットワークを表わすグラフを生成するグラフ生成装置であって、
   （ａ１）前記情報探索集合の情報に対応する頂点の何れか一つをターゲット頂点として設定すると共に、前記情報探索集合の情報に対応する頂点の少なくとも１つを、初期頂点としてランダムに設定し、
   （ａ２）前記（ａ１）で設定したターゲット頂点をクエリとして、所定の探索アルゴリズムに従って、前記（ａ１）で設定された前記初期頂点から、前記クエリに類似する頂点を探索し、
   （ａ３）前記（ａ２）の結果、前記探索結果として得られた頂点が前記ターゲット頂点でない場合に、前記ターゲット頂点に辿り着く頂点集合内の何れか一つの頂点と、前記探索結果として得られた頂点とをリンク結合し、
   （ａ４）前記（ａ１）から前記（ａ３）の処理を、所定の第１条件が満たされるまで繰り返し、
   前記（ａ１）から前記（ａ４）の処理を、所定の第２条件が満たされるまで繰り返すことにより、前記グラフを生成し、前記生成したグラフを、前記記憶部に格納するグラフ生成部
   を含むグラフ生成装置。
2. 前記（ａ１）の処理は、前記情報探索集合の情報に対応する頂点の何れか一つをターゲット頂点として設定すると共に、前記情報探索集合の情報に対応する頂点のうちの複数の頂点を、前記初期頂点としてランダムに設定し、
   前記（ａ２）の処理は、所定の探索アルゴリズムに従って、前記（ａ１）で設定された前記複数の初期頂点の各々から、前記クエリに類似する頂点を各々探索し、
   前記（ａ３）の処理は、前記探索結果として得られた頂点が前記ターゲット頂点でない場合に、前記ターゲット頂点と、前記探索結果として得られた前記ターゲット頂点でない頂点のうち、前記ターゲット頂点と最も類似する頂点とをリンク結合する請求項１記載のグラフ生成装置。
3. Ｋ−ＮＮリストを生成するＫ−ＮＮリスト生成部と、前記Ｋ−ＮＮリストに基づいて、ベースグラフを生成するベースグラフ生成部とを更に含み、
   前記Ｋ−ＮＮリスト生成部は、
   （ｂ１）前記情報探索集合の情報に対応する頂点の各々に対して、前記情報探索集合の情報に対応する頂点からランダムにＫ個の頂点を選択し、前記頂点を、前記Ｋ個の頂点の各々とリンク結合し、
   （ｂ２）前記情報探索集合の情報に対応する頂点の各々に対して、前記頂点とリンク結合された前記Ｋ個の頂点と、前記Ｋ個の頂点の各々とリンク結合された頂点とから、前記頂点と類似するＫ個の頂点を選択し、
   （ｂ３）前記情報探索集合の情報に対応する頂点の各々に対して、前記頂点と前記（ｂ２）で選択された前記Ｋ個の頂点とがリンク結合されるようにリンクを張り替え、
   前記（ｂ２）から前記（ｂ３）の処理を、前記リンクの張り替えがなくなるまで繰り返すことにより、前記情報探索集合の情報に対応する頂点の各々に対する前記類似するＫ個の頂点が格納された前記Ｋ−ＮＮリストを生成し、
   前記ベースグラフ生成部は、
   （ｃ１）前記Ｋ−ＮＮリストに基づいて、前記情報探索集合の情報に対応する頂点それぞれを、前記情報探索集合の前記頂点のうちの最も類似する頂点とリンク結合し、
   （ｃ２）前記情報探索集合の情報に対応する各頂点から、前記情報探索集合の任意の前記頂点である第１の頂点を抽出し、前記Ｋ−ＮＮリストに基づいて、当該第１の頂点からｋ番目（ただし、ｋは１より大きい整数）に類似する頂点である第２の頂点を、前記情報探索集合の情報に対応する各頂点から抽出し、
   （ｃ３）前記第２の頂点を初期頂点とし、前記第１の頂点をクエリとして、貪欲探索アルゴリズムに従って、前記初期頂点から、前記クエリに類似する頂点を探索し、
   （ｃ４）前記（ｃ３）の結果、探索結果として得られた頂点が、前記第１の頂点でない場合に、当該第１の頂点と前記第２の頂点とを、直接的、または、当該１の頂点及び前記第２の頂点以外の頂点を介することにより間接的にリンク結合し、
   前記（ｃ２）から前記（ｃ４）の処理を、前記情報探索集合の前記頂点それぞれを前記第１の頂点として繰り返すことを、ｋが２からＫ以下である所定の値になるまで繰り返すことにより、頂点間ネットワークを表わすベースグラフを生成し、
   前記グラフ生成部は、前記生成されたベースグラフを用いて、前記グラフを生成する
   請求項１又は２記載のグラフ生成装置。
4. 記憶部に格納されている情報探索集合の情報に対応する頂点における前記頂点間の類似度又は非類似度に基づき頂点間ネットワークを表わすグラフを生成するグラフ生成装置におけるグラフ生成方法であって、
   （ａ１）前記情報探索集合の情報に対応する頂点の何れか一つをターゲット頂点として設定すると共に、前記情報探索集合の情報に対応する頂点の少なくとも１つを、初期頂点としてランダムに設定し、
   （ａ２）前記（ａ１）で設定したターゲット頂点をクエリとして、所定の探索アルゴリズムに従って、前記（ａ１）で設定された前記初期頂点から、前記クエリに類似する頂点を探索し、
   （ａ３）前記（ａ２）の結果、前記探索結果として得られた頂点が前記ターゲット頂点でない場合に、前記ターゲット頂点に辿り着く頂点集合内の何れか一つの頂点と、前記探索結果として得られた頂点とをリンク結合し、
   （ａ４）前記（ａ１）から前記（ａ３）の処理を、所定の第１条件が満たされるまで繰り返し、
   前記（ａ１）から前記（ａ４）の処理を、所定の第２条件が満たされるまで繰り返すことにより、前記グラフを生成し、前記生成したグラフを、前記記憶部に格納する
   グラフ生成方法。
5. 前記（ａ１）のステップは、前記情報探索集合の情報に対応する頂点の何れか一つをターゲット頂点として設定すると共に、前記情報探索集合の情報に対応する頂点のうちの複数の頂点を、前記初期頂点としてランダムに設定し、
   前記（ａ２）のステップは、所定の探索アルゴリズムに従って、前記（ａ１）で設定された前記複数の初期頂点の各々から、前記クエリに類似する頂点を各々探索し、
   前記（ａ３）のステップは、前記探索結果として得られた頂点が前記ターゲット頂点でない場合に、前記ターゲット頂点と、前記探索結果として得られた前記ターゲット頂点でない頂点のうち、前記ターゲット頂点と最も類似する頂点とをリンク結合する請求項４記載のグラフ生成方法。
6. 前記グラフ生成装置は、Ｋ−ＮＮリストを生成するＫ−ＮＮリスト生成部と、前記Ｋ−ＮＮリストに基づいて、ベースグラフを生成するベースグラフ生成部とを更に含み、
   前記Ｋ−ＮＮリスト生成部は、
   （ｂ１）前記情報探索集合の情報に対応する頂点の各々に対して、前記情報探索集合の情報に対応する頂点からランダムにＫ個の頂点を選択し、前記頂点を、前記Ｋ個の頂点の各々とリンク結合し、
   （ｂ２）前記情報探索集合の情報に対応する頂点の各々に対して、前記頂点とリンク結合された前記Ｋ個の頂点と、前記Ｋ個の頂点の各々とリンク結合された頂点とから、前記頂点と類似するＫ個の頂点を選択し、
   （ｂ３）前記情報探索集合の情報に対応する頂点の各々に対して、前記頂点と前記（ｂ２）で選択された前記Ｋ個の頂点とがリンク結合されるようにリンクを張り替え、
   前記（ｂ２）から前記（ｂ３）の処理を、前記リンクの張り替えがなくなるまで繰り返すことにより、前記情報探索集合の情報に対応する頂点の各々に対する前記類似するＫ個の頂点が格納された前記Ｋ−ＮＮリストを生成し、
   前記ベースグラフ生成部は、
   （ｃ１）前記Ｋ−ＮＮリストに基づいて、前記情報探索集合の情報に対応する頂点それぞれを、前記情報探索集合の前記頂点のうちの最も類似する頂点とリンク結合し、
   （ｃ２）前記情報探索集合の情報に対応する各頂点から、前記情報探索集合の任意の前記頂点である第１の頂点を抽出し、前記Ｋ−ＮＮリストに基づいて、当該第１の頂点からｋ番目（ただし、ｋは１より大きい整数）に類似する頂点である第２の頂点を、前記情報探索集合の情報に対応する各頂点から抽出し、
   （ｃ３）前記第２の頂点を初期頂点とし、前記第１の頂点をクエリとして、貪欲探索アルゴリズムに従って、前記初期頂点から、前記クエリに類似する頂点を探索し、
   （ｃ４）前記（ｃ３）の結果、探索結果として得られた頂点が、前記第１の頂点でない場合に、当該第１の頂点と前記第２の頂点とを、直接的、または、当該１の頂点及び前記第２の頂点以外の頂点を介することにより間接的にリンク結合し、
   前記（ｃ２）から前記（ｃ４）の処理を、前記情報探索集合の前記頂点それぞれを前記第１の頂点として繰り返すことを、ｋが２からＫ以下である所定の値になるまで繰り返すことにより、頂点間ネットワークを表わすベースグラフを生成し、
   前記生成されたベースグラフを用いて、前記（ａ１）から前記（ａ４）の処理を、所定条件が満たされるまで繰り返すことにより、前記グラフを生成する
   請求項４又は５記載のグラフ生成方法。
7. 請求項１〜請求項３の何れか１項に記載のグラフ生成装置を構成する各手段として、コンピュータを機能させることを特徴とするプログラム。