DEIM Forum 2023 2b-6-1

経路を用いた高速なサブグラフ編集距離問合せ
堀内 美聡†

佐々木勇和†

肖

川†

鬼塚

真†

† 大阪大学大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1-5
E-mail: †{horiuchi.misato,sasaki,chuanx,onizuka}@ist.osaka-u.ac.jp
あらまし サブグラフ編集距離 (SED) 問合せは，グラフ間の距離として SED を用いた類似サブグラフ問合せであり，分子構造の分析や，ナレッジグラフの検索，パターン認識など様々な応用に用いられる．SED の計算は NP 困難であるため，実践的に効率的な手法が必要である．本研究は，グラフ上の経路に基づいて検索範囲を効果的に枝刈りし，効率的で高精度な SED 問合せ手法を提案する．提案手法では，クエリグラフと対象グラフの経路を比較することで対象グラフの SED の下限値と上限値を計算し，明らかに検索結果に入らない対象グラフを枝刈りする．さらに，下限値と上限値を用いることで，グラフの SED 計算そのものも高速化する．2 種のグラフデータを用いた評価実験により，提案手法は既存手法と比較して高精度かつ高速な SED 問合せが可能であることを示す．
キーワード グラフデータ処理, 問合せ処理, アルゴリズム, グラフ類似度, サブグラフ編集距離

1 背

景
v1 A

B v2

u1 A

v3 C

D v4

u3 E

B u2

グラフは頂点とそれらを接続する辺により表現されるデータ構造であり，相互に関係する情報をもつデータのモデル化のために利用される．分子グラフや，生物情報科学データ，ウェブ
グラフ，ソーシャルネットワークグラフ [1] など幅広く利用されている．例えば，分子グラフでは，原子を頂点，原子結合を辺で表すことにより分子構造をモデル化できる．

(a) G1(b) G2

図 1: SED の例る．しかし，近似 SED 計算手法は正確な SED を計算出来なサブグラフ編集距離（SED）問合せは，検索対象のグラフといため，範囲検索に適さず，Top-k 検索も正確でない．また，入力のクエリグラフのグラフ間距離に SED を利用するグラフ

SGSimSearch [8] は SED が閾値以下となる対象グラフを抽出

問合せである [2, 3]．SED はクエリグラフに編集操作をして対する検索手法である．しかし，検索範囲の下界を与える検索は

象グラフとサブグラフ同型にするために必要な最少の編集操作できず，Top-k 検索にも適さない．さらに，機械学習に基づく回数であり，編集操作は，頂点および辺に対し，挿入/削除/属手法 [3] は，モデルの学習に時間を要することに加え，モデル

性変更のそれぞれ 3 操作である [4]．SED 問合せは，検索対象の学習に近似 SED 手法を利用しており，さらに機械学習の性のグラフに対し，入力のクエリグラフとの SED が小さい上位

質から正確な SED を計算できない．著者らの知る限り，Top-k

k 件の対象グラフを出力する Top-k 検索と検索範囲内の SED

検索と範囲検索の両方に対して高速かつ高精度な SED 問合せを持つ全ての対象グラフを出力する範囲検索がある．サブグラが可能な既存手法は存在しない．

フマッチングに比べて，エラーやノイズに寛容な検索を行うこ

貢献. そこで本稿では，Top-k 検索と範囲検索の両方で高速かとができ，分子構造 [5]，グラフパターンマイニング [6] などのつ正確な SED 問合せを目的とし，グラフの経路を用いたグラ

様々な分野に活用できる．

フの枝刈りと効率的な SED 計算アルゴリズムによる SED 問SED の例を図 1 に示す．G1 をクエリグラフ，G2 を検索対合せ手法を提案する．提案手法は次の 3 つの要素で構成され象グラフとした場合，v3 のラベルを変更，v4 を削除，v2 と v3

る：(1) 経路の比較による下限値・上限値計算，(2) 問合せの間の枝を削除，v3 と v4 間の枝を削除という 4 つの操作で G1

枝刈り技術，(3) 上限値を更新しながら枝刈りする SED 計算

が G2 のサブグラフ同型となるため，SED(G1 , G2 ) は 4 とな

アルゴリズム．まず，提案手法はクエリグラフと対象グラフ内

る．一方で，G2 をクエリグラフ，G1 を検索対象グラフとしたに存在する経路（節点ラベルのシーケンス）の比較により，小場合，v3 のラベルを変更するのみでサブグラフ同型となるた

さい計算コストで SED の下限値と上限値を算出する．次に，め，SED(G2 , G1 ) は 1 となる．

SED 問合せアルゴリズムでは，経路より求めた SED の下限値

動機. SED は類似サブグラフの検索に有用であるが， NPと上限値を利用して検索対象グラフの枝刈りを行う．最後に，困難であり，素朴に値を求める方法は実用的でない．そのた

SED 計算アルゴリズムでは，下限値と上限値を利用し，効率

め，様々な SED 問合せの高速化技術が開発されている [7]．

的な SED 計算を行う．この際，SED 計算中に上限値を更新しClosure-tree [2] は複数のグラフの情報を集約して構築する木ながら探索することで検索空間を削減する，

構造索引と，近似 SED 計算手法による Top-k 検索手法であ実験では 2 種のグラフデータを用いて Top-k 検索と範囲検索にて提案手法の検索精度と効率性の評価を行う．検索精度のサブグラフマッチングは，クエリグラフに対してサブグラフ

評価実験では， Top-k 検索では nDCG@10 と RMSE ，範囲

同型なグラフを列挙する技術であり，SED 問合せにおいて SED

検索では F 値を比較することで，提案手法が正確な SED を計がゼロの場合の範囲検索と同等である [12]．FG-index [13] は算できることを示す．効率性の評価実験では，検索時間と経路

頻出サブグラフに基づき索引を作成することで高速化する．多抽出時間を比較することで，提案手法が効率的に検索できるこ

数のマッチングが存在するサブグラフはインデックスで高速にとを示す．加えて，既存の近似 SED 計算技術を利用すること処理し，少数のマッチングはそのままサブグラフマッチングをで，高速かつ既存手法以上の高精度で近似 SED を計算できる

実行することで，効率よくサブグラフ同型を抽出する．また，ことを示す．

GADDI [14] は頻出サブグラフに基づく距離を索引にするこ

本稿の構成は次の通りである．まず，2 章で関連研究を示し，とで高速化する．しかし，サブグラフマッチング技術を用いて3 章にて事前知識と問題定義を説明する．4 章に経路に基づく

SED 問合せを行う場合，クエリグラフを変更しながら繰り返

SED の下限値と上限値の計算について述べる．さらに，5 章にしサブグラフマッチングを行うことで実現できる．しかし，ク

下限値と上限値によって効率化した SED 問合せを示す．6 章

エリグラフの変更パターン数が指数関数的に増加するため現実にて実験結果を示し，7 章にて本稿をまとめる．

的ではない．

2 関連研究3 事前知識本章では SED 問合せの関連研究として，サブグラフ編集距

本章では事前知識として，グラフ，経路，および SED 問合離 (SED) ，グラフ編集距離 (GED)，サブグラフマッチングにせについて説明する．

ついて述べる．

グラフ. グラフ G を三つ組 (V, E, L) として表現する．V は頂

SED は，グラフの局所的な類似性を表す指標であり，クエ点の集合，E ⊆ V × V は v, v ′ ∈ V を接続する辺 e(v, v ′ ) の集

リグラフに編集操作をして対象グラフのサブグラフ同型にする

合，L は各頂点からラベル集合への単射である．V (G)，E(G)ために必要な最少の編集操作回数である [4]．SED 計算手法は，をそれぞれ G の頂点集合，辺集合とする．v ∈ V に対して L(v)フィルタ–検証アルゴリズムが一般的であり，これはフィルタでは v のラベルである．|V (G)| を頂点の個数とし，|E(G)| を辺

検索範囲を枝刈りし，検証により SED 計算を行う．Closure-の個数とする．また，グラフの集合を G とする．

tree [2] は複数のグラフを一つのグラフにまとめた (union) イ

本稿では，辺ラベル，自己ループ，多重辺のない無向グラフ

ンデックスとマッピング手法による高速な SED 計算手法であを扱う．しかし，提案手法は異なる種類のグラフや，頂点間とる. また，AppSub [7] はスター構造に基づいて下限値と上限値

辺間に類似度を定義する場合にも簡単に拡張可能である．

を求め，枝刈りをする近似 SED 計算手法である．しかし，こ経路. 次に，経路を以下のように定義する．

れらは正確な SED を保証することはできず，また範囲検索にも適していない．SGSimSearch [8] は経路に基づいて下限値を

定義 1 (経路)求め，GrafD-Index [9] は特徴間の距離の索引を作成することる辺を接続する順序で並べた一連の列である．ただし，経路にで高速に検索を行う．しかし，これらは SED が閾値以下となおいて頂点と辺はそれぞれ連続して並ばず，端は必ず頂点である対象グラフを抽出する検索手法であるため，検索範囲の下界

る．経路の頂点数をその経路の長さ n とする．グラフ G が与あるグラフの経路は，頂点とその間に存在すを与える検索や，Top-k 検索に適さない．GREED [3] は機械えられたとき，G に含まれる全ての経路を重複無し集合 P (G)

学習によって SED を学習し高速に SED を計算するという手とし，Pn (G) ⊆ P (G) を長さ n の経路とする．また，経路集合法である．しかし，モデルの学習に時間を要することに加え，から自然数集合への単射 C : P (G) → R とし，P (G) に含まれモデルの学習に近似 SED 手法を利用しており，さらに機械学る経路のラベル列 p ∈ P (G) の個数を C(p, P (G)) とする．

習の性質から正確な SED を計算できない．

GED は，同程度のサイズのグラフの類似性を測るために適した指標で，クエリグラフに編集操作をして対象グラフとグラ

長さ n の経路のラベル列 p ∈ Pn (G) に対し，i <= n 番目のラベ
ルを p[i − 1] とする．

フ同型にするために必要な最少の編集操作回数である．GED のSED 問合せ. SED 問合せは，入力として与えるクエリグラフ

高速な計算手法は活発に研究されており，κ–AT への分解に基とデータベース内のの対象グラフを比較し，クエリグラフと似づく手法 [10]，スター型グラフを利用し近似計算する手法 [7]，た対象グラフを抽出する．グラフの比較のため，頂点の対応づ

機械学習に基づく手法 [11] などが存在する．しかし，クエリ

けを表すマッピングを定義する．まず，グラフの拡張を定義す

グラフと検索対象のグラフサイズの差が大きいと GED の値もる．G が与えられた時，ラベル ϵ の頂点を追加した拡張グラフ

大きくなってしまうなど，類似グラフ検索のために指標としてを G∗ とする．これは，∀v ∈ V (G)/V (G∗ ) に対し L(v) = ϵ がの利用は課題がある．また，対象グラフのあらゆるサブグラフ

成り立つことを意味する．拡張グラフを利用し，マッピングをに対して GED を計算することで SED の計算が可能であるが，以下のように定義する．

GED 計算が高コスト，さらにサブグラフのパターン数は膨大になるため，SED 問合せへの利用は難しい．

定義 2 (マッピング)

グラフ G1 , G2 が与えられたとき，G2の拡張グラフを G∗2 として，マッピングは単射 M : V (G1 ) −→V (G∗2 ) とする．また，V (G1 ) から V (G∗2 ) へ写すマッピングの集合を M(G1 , G2 ) とする．

本稿では SED 問合せを以下のように定義する．

さらに，サブグラフ編集距離を定義するために，サブグラフ
同型を以下のように定義する．
定義 3 (サブグラフ同型)

計算は NP 困難であることが証明されている [7]．

対象グラフの集合 G，クエリグラ

問題定義 (SED 問合せ)

フ Q とする．Top-k 検索では k が与えられたとき，∀G1 ∈ G′ ,グラフ G1 , G2 が与えられたとき，G′2 ⊆ G2 として， ∀v ∈ V (G1 ) に対し L(v) = L(f (v)) が成り立ち，かつ ∀e(v, u) ∈ E(G1 ) に対し e(f (v), f (u)) ∈ E(G′2 ) が成り立つ全単射 f : V (G1 ) → V (G′2 ) が存在するとき，G1 はG2 とサブグラフ同型である．
これらに基づき，サブグラフ編集距離 (SED) を以下のように定義する．

∀G2 ∈ G\G′ に対し SED(Q, G1 ) <= SED(Q, G2 ) を満たす
G′ ⊂ G を抽出する．範囲検索では，検索範囲 [r1 , r2 ] が与えられたとき，∀G1 ∈ G′ に対し r1 <= SED(G1 ) <= r2 ，かつ∀G2 ∈ G\G′ に対し SED(G2 ) < r1 または r2 < SED(G2 )を満たす G′ ⊂ G を抽出する．

4 経路に基づく下限値と上限値計算
本章では経路に基づいて SED の下限値と上限値の導出方法

定義 4 (サブグラフ編集距離 (SED))

グラフ G1 , G2 が与えについて述べる．

られたとき，G1 と G2 のサブグラフ編集距離 SED(G1 , G2 ) は，

G1 に編集操作を行なって G2 のサブグラフ同型にするために

4. 1 経路を利用した下限値の導出
経路を利用した下限値の導出について説明する．提案手法は，必要な編集操作の最少回数である．
ラベル ϵ にマッピングする頂点の編集操作は削除，それ以外のラベルの頂点のうちマッピング先と異なるラベルの頂点の編集操作はラベル変更となる．また，マッピング前に存在する辺がマッピング先では存在しない場合，編集操作は辺の削除となる．通常，編集距離は頂点の追加および辺の追加とラベル変更を含むが， SED において頂点と辺を追加する操作を行うこと

長さ 1, 2 のクエリグラフにあるが対象グラフにない経路に基づ
いて SED の下限値を求める．
グ ラ フ G1 , G2 に つ い て ， SED の 下 限 値 を LB (G1 , G2 )と 表 す．ま た ，長 さ n 以 下 の 経 路 の 情 報 か ら 導 出 す る と
き ，LB n (G1 , G2 ) と す る ．こ れ は ∀0 <= i <= n に対し，
LB i (G1 , G2 ) <
LB
(G
,
G
)
を満たす．
1
2
=
経路を利用した下限値は下記の定理により求める．

はない．また，本稿では辺ラベル無しのグラフを扱うため，辺ラベル変更は無視する．上記の定義より，グラフ G1 , G2 が与定理 1えられたとき，v ∈ V (G1 ), u ∈ V (G2 ) として，き，下記が成り立つ．

δ(v, u) =クエリグラフ G1 および検索対象 G2 が与えられたとSED(G1 , G2 ) >=1

L(v) =| L(u)

0otherwise∑+∑max (0, C(p, P1 (G1 ))−C(p, P1 (G2 )))p∈P1 (G1 )max (0, C3 − C(p, P2 (G2 )))p∈P2 (G1 )とする，また，辺の削除を v1 , v2 ∈ V (G1 ), u1 , u2 ∈ V (G2 ) と
して，

C1

=

min(C(p[0], P1 (G1 )), C(p[1], P1 (G1 )))/2,

C2=

min(C(p[0], P1 (G2 )), C(p[1], P1 (G2 )))/2, C3 = min(min(C1 , C2 ),δ(e(v1 , v2 ), e(u1 , u2 ))(1)1 e(v1 , v2 ) ∈ E(G1 ) かつ e(u1 , u2 ) ∈/ E(G2 )=0 otherwiseとする．このとき，マッピング M ∈ M(G1 , G2 ) において G1
が G2 のサブグラフ同型になるために必要なグラフの編集操作

C(p, P2 (G1 ))) である．
証明: まず，頂点数 |V (G1 )| > |V (G2 )| であるとき，明らかに|V (G1 )| − |V (G2 )| 個の頂点はラベル ϵ の頂点にマッピングする．同様に，辺数 |E(G1 )| > |E(G2 )| であるとき，明らかに|E(G1 )| − |E(G2 )| 個の辺はラベル ϵ の頂点にマッピングする．
すると，式 (2), (3) より，回数を編集距離 d(G1 , G2 , M ) とする． SED(G1 , G2 ) は G1 がG2 のサブグラフ同型になるために必要な最少の編集操作回数であるから，SED(G1 , G2 ) は以下である．

∑

d(G1 , G2 , M ) =+ max(0, |E(G1 )| − |E(G2 )|)δ(v, M (v))

である．この右辺を LB 1 (G1 , G2 ) とする．次に，長さ 1 の経v∈V (G1 )+∑路に注目する．p ∈ P1 (G1 ) はそれぞれ G1 に含まれるラベル

δ(e(v, u), e(M (v), M (u))) (2)e(v,u)∈E(G1 )SED(G1 , G2 ) =min

SED(G1 , G2 ) >= max(0, |V (G1 )| − |V (G2 )|)M ∈M(G1 ,G2 )d(G1 , G2 , M )(3)

なお，一般的に SED(G1 , G2 ) =| SED(G2 , G1 ) である．SEDを意味する．このとき，p ∈ P1 (G1 ) に対し，C(p, P1 (G1 )) >∑C(p, P1 (G2 )) ならば， v∈V (G1 ) δ(v, M (v)) >= C(p, P1 (G1 ))−C(p, P1 (G2 )) である．したがって，式 (2) より，SED(G1 , G2 ) >=C(p, P1 (G1 )) − C(p, P1 (G2 )) である．これは，編集操作においては，頂点の削除とラベル変更の回数の和に対応する．また，∑C(p, P1 (G1 )) <= C(p, P1 (G2 )) ならば v∈V (G1 ) δ(v, M (v)) >=0 であるので，式 (2) より，SED(G1 , G2 ) >0である．これ=らのことから，以下が成り立ち，この右辺を LB 1 (G1 , G2 ) とする．

∑
SED(G1 , G2 ) >max (0, C(p, P1 (G1 ))−C(p, P1 (G2 )))=1
2
SED(G1 , G2 ) <= min(UB n (G1 , G2 ), UB n (G1 , G2 ))(4)n は G1 と G2 の両方に含まれる経路の最大長となる．
∑
証明: まず，経路を利用しないとき， v∈V (G1 ) δ(v, M (v)) <=∑<|V (G1 )| か つδ(e(v,
u),
e(M
(v),
M
(u)))
=
e(v,u)∈E(G1 )|E(G1 )| である．したがって，式 (2) より以下が成り立つ．
UB 0 (G1 , G2 ) = |V (G1 )| + |E(G1 )|p∈P1 (G1 )

さ ら に ，長 さ 2 の 経 路 に 注 目 す る ．経 路 p ∈ P2 (Q)に つ い て ，頂 点 を p[0], p[1] と す る ．長 さ 2 の 経 路 は 2
つ の 経 路 に 複 数 個 頂 点 を 持 つ た め ，必 ず 頂 点 の 個 数 以
下 で あ る ．ま た ，両 方 の 頂 点 が 同 じ ラ ベ ル で あ る 経 路の み で あ る と き ，こ の 経 路 の 個 数 は 最 少 で あ る ．よっ
1 (G1 ))て ， C((p[0],P2<= C((p[0], P1 (G1 )),= C((p, P2 (G1 )) <C((p[1],P1 (G1 )) <= C((p[1], P1 (G1 )) である．
= C((p, P2 (G1 )) <2

ここで，G1 , G2 のグラフに含まれる頂点数に基づいて辺を追加すると形成しうる最大の経路数をそれぞれ C1 , C2 とす
ると，それぞれ C1 = min(C(p[0],P1 (G12)),C(p[1],P1 (G1 ))) , C2 =min(C(p[0],P1 (G2 )),C(p[1],P1 (G2 )))である．片方の頂点を長さ 1 の2(5)次に，長さ 1 の経路に注目する．このとき，p ∈ P1 (G1 ) に対し，ラベル列の共通数は min(C(p, P1 (G1 )) > C(p, P1 (G2 )))∑個 で あ る ．す る と ， v∈V (G1 ) δ(v, M (v)) >= |V (G1 )| −min(C(p, P1 (G1 )) > C(p, P1 (G2 ))) である．したがって，式(2) より，SED(G1 , G2 ) <= |V (G1 )| + |E(G1 )| − C(p, P1 (G2 ))である．これは，編集操作においては，削除やラベル変更を行
わない頂点数に対応する．これらのことから，以下が成り立つ．

UB 1 (G1 , G2 ) <= UB 0 (G1 , G2 )∑−min(C(p, P1 (G1 )), C(p, P1 (G2 )))p∈P1 (G1 )経路とみなすと，これが G の経路にも含まれる場合，この p は次に，長さ n > 1 の経路に注目する．このとき，p ∈ Pn (G1 ) にもう一方の頂点のと辺を削除するよりも，辺を削除する方が編集対し，C(p, Pn (G1 )) > 0, C(p, Pn (G1 )) > 0 を満たす p が存在∑するとき， v∈V (G1 ) δ(v, M (v)) >= |V (G1 )|−n であり，さらに∑<e(v,u)∈E(G1 ) δ(e(v, u), e(M (v), M (u))) = |E(G1 )| − (n − 1)

操作回数が小さくなるので，実際の G1 の経路数 C(p, P2 (G1 ))を考慮して，辺の削除回数は C1 , C2 と実際の経路数の差

max(0, min(min(C1 , C2 ), C(p, P2 (G1 ))) − C(p, P2 (G2 ))) であである．これらのことから，以下が成り立つ．

る．これらをまとめると，LB 2 (G1 , G2 ) は以下となる．

UB n (G1 , G2 ) <= UB 0 (G1 , G2 ) − n − (n − 1)min(C(p[0], P1 (G1 )), C(p[1], P1 (G1 )))2
min(C(p[0], P1 (G2 )), C(p[1], P1 (G2 )))C2 =2C3 = min (min(C1 , C2 ), C(p, P2 (G1 )))C1 == UB 0 (G1 , G2 ) − (2n + 1)
また，同じラベルを持たない経路集合 P ′ (G1 ) ⊂ P (G1 ) について，これらの経路は互いの編集操作に関わらない．よって以下が成り立つ．

LB 2 (G1 , G2 ) = LB 1 (G1 , G2 )∑+max (0, C3 − C(p, P2 (G2 )))上限値はこれらをいずれも満たすため，より小さい上限値を

UB n (G1 , G2 ) とすることができる．

4. 2 経路を利用した上限値の導出
経路を利用した下限値の導出について説明する．提案手法は，
長さ 1 以上のクエリグラフと対象グラフに共通する経路に基づ
いて SED の上限値を求める．
グラフ G1 , G2 が与えられた時，SED の上限値を UB (G1 , G2 )と表す．また，長さ n 以下の経路の情報から導出できるとき，
特に UB n (G1 , G2 ) とする．

□

ここで，長さ n > 1 の経路から上限値を導出する際，提案
手法では経路の個数は考慮しない．これは，複数個数の経路がループを構成する場合が存在するためである．

4. 3 経 路 抽 出
提案手法は対象グラフの経路を保持することで SED 計算に活用する．各対象グラフの n 以下の長さの経路集合を持ち，幅経路を利用した上限値は下記の定理により求める．
クエリグラフ G1 および検索対象 G2 が与えられたとき，以下が成り立つ．

優先探索，または深さ優先探索手順で抽出する．
（ 1 ） 長さ 1 の経路を求め，これを以降の経路の始点とする．
これは頂点集合に相当する．
（ 2 ） 長さ m > 0 の経路について，終点の隣接頂点まで経UB 1n (G1 , G2 ) = |V (G1 )| + |E(G1 )|∑−min(C(p, P1 (G1 )), C(p, P1 (G2 )))UB 2n (G1 , G2 ) = UB 0 (G1 , G2 ) −(2i + 1)i□p∈P1 (G1 )

∑

′
0<
= i<
=n p∈P (G1 )p∈P2 (G1 )

定理 2

∑

UB n (G1 , G2 ) = UB 0 (G1 , G2 ) −

∑

∑

′
0<
=n p∈P (G1 )= i<
i

路を延長し，これを新たな終点とする．これにより長さ m + 1の経路を求める．
この経路抽出の時間計算量は以下の定理のようになる．

(2i − 1)定理 3

グ ラ フ 集 合 G の 平 均 頂 点 数 を |V |, 平 均 隣 接 頂 点

数を |VN |，経路の最大経路長を n とすると，時間計算量はが成り立つ時，この G は明らかに検索結果に含まれない．よっO(|G||V ||VN |て，このような対象グラフ G を枝刈りする．

n−1) である．

証明: あるグラフ G ∈ G について，まず n = 1 のとき，経路集

5. 3 SED 計算

合は頂点集合となるため，計算量は O(|V |) である．次に，n > 1

SED 計算では，マッピングごとの編集距離とそのマッピンのとき，長さ n の経路は，長さ n − 1 の経路にさらに隣接頂点をグを拡張したマッピングの下限をインクリメンタルに求めなが追加することで求められる．よって経路長 n の計算量を On とら，SED の上限値を更新し，さらに下限と比較による探索す

すると，平均隣接頂点数 |VN | を用いて On = On−1 |VN | である．

る頂点の組み合わせの枝刈りで，効率的に SED 計算を行う．

以上より n > 0 に対し 1 つのグラフの計算量は O(|V ||VN |であるので，時間計算量は O(|G||V ||VN |n−1 ) である.

n−1

)

□

実グラフは疎なグラフであることが多く，隣接頂点数 |VN | は|V | よりも非常に小さいのが一般的である．そのため，経路情報の抽出は高速に実行可能である．

5 SED 問合せ

マッピングごとの編集距離・下限値と SED の上限値の更新.
提案手法は，上限値を更新しながら SED 計算することで，より枝刈りの効果を高める．以下で，マッピングごとの編集距離と下限値の計算と，編集距離を利用した SED の上限値更新について説明する．
まず，マッピング M に加えて頂点 v ∈ V (Q)，u ∈ V (G)をマッピングした時の下限値 LBcur (Q, G, M ′ ) を計算する．

本章では SED 問合せのアルゴリズムについて述べる．まず，∀v ∈ V ′ (Q) ⊂ V (Q) に 対 し ∀M (v) ∈/ V ′ (G) ⊂ V (G)5. 1 節で SED 問合せフレームワークを述べ，その後，5. 2 節が 成 り 立 ち ，さ ら に ∀e(u, u′ ) ∈ E ′ (Q) ⊂ E(Q) に 対 しで Top-k 検索，範囲検索に適した枝刈りを行う SED 問合せア∀e(M (u), M (u′ )) ∈/ E ′ (G) ⊂ E(G) が成り立つとき，式 (2)ルゴリズムを述べる．さらに，5. 3 節で上限値を更新しながらより，枝刈りに活用する SED 計算アルゴリズムを述べる．

5. 1 問合せフレームワーク

LBcur (Q, G, M ′ ) = LBcur (Q, G, M ) + |V ′ (Q)| + |E ′ (Q)|が成り立つ．次に，グラフ Q と G のマッピング M につい

SED 問合せは SED の下限値と上限値を用いながら検索対象て，∀v ∈ V ′ (Q) ⊂ V (Q) に対し ∀M (v) ∈ V ′ (G) ⊂ V (G)とするグラフを枝刈りし，枝刈りできなかったグラフの SED

が 成 り 立 ち ，さ ら に ∀e(u, u′ ) ∈ E ′ (Q) ⊂ E(Q) に 対 しを計算するフィルタリング–検証アルゴリズムに基づいたフレー∀e(M (u), M (u′ )) ∈ E ′ (G) ⊂ E(G) が成り立つとき，式 (2)

ムワークにて実行する．主な流れは以下の通りである．

より，（ 1 ） グラフサイズ昇順に SED の上限値，下限値を求める（ 2 ） SED の上限値と下限値を利用して対象グラフを枝刈りする（ 3 ） SED の上限値の更新とマッピングごとの下限値と比較による枝刈りを行いながら SED を計算する
提案手法は，Top-k 検索と範囲検索とそれぞれの SED 計算

d(Q, G, M ) = |V (Q)| + |E(Q)| − |V ′ (Q)| − |E ′ (Q)|が成り立つ．
さらに，式 (3) より，SED(Q, G) <= d(Q, G, M ) である．よって，上限値 UB (Q, G) を min(UB (Q, G), d(Q, G, M )) で更新
する．

を， SED の下限値と上限値を活用して効率化する．

SED 計算の枝刈り. 提案手法は，SED の上限値と下限値を利

5. 2 検索アルゴリズム

用し，明らかに SED 計算に不要なマッピングの枝刈り，または問合せ結果に明らかに入るもしくは入らない対象グラフの

Top-k 検索. Top-k 検索では，暫定の k 番目の SED の値を枝刈りに利用し，クエリグラフとの SED が低い上位 k 個の対象グラフを効率的に求める．k 個以上の対象グラフの SED が計算済みのとき，暫定の k 番目の SED(Q, G) を SED k とすると，LB (Q, G) > SED k が成り立つならば，この G は明らかに出力に含まれない．したがって，このような対象グラフ G を枝刈りする．さらに，グラフサイズ昇順で SED 計算することで，高速に k 個のグラフの SED を求めることで，この枝刈りの効
果を高める．

SED 計算を終了する．
まず，以下の場合は，M (v) = M ′ (v), ∀v ∈ V (G′1 ) を満たす

M ∈ M(G1 , G2 ) の SED 計算を枝刈りする．
枝刈り条件 1: d(Qi , Gi , Mi ) > UB (Q, G) を満たす場合．このとき，明らかに SED(Q, G) =| d(Q, G, M ) である．
枝刈り条件 2: Top-k 検索にて d(Q, G, Mi ) > SED k ，範囲検索にて d(Q, G, Mi ) > r2 を満たす場合．このとき，G 明らかに検索結果に入らない．
さらに，以下の場合は，対象グラフの SED 計算を終了する．

範囲検索. 範囲検索では，検索範囲と SED の上限値・下限値を終了条件 1: M ∈ M(Q, G) について d(Q, G, M ) = LB (Q, G)

比較して枝刈りに利用し， SED が検索範囲内である対象グラフを満たす場合．このとき，必ず最小の編集距離であるので，を効率的に求める．まず，r1 <= LB (Q, G) かつ UB (Q, G) <= r2

SED(Q, G, M ) = LB (Q, G) である．
終了条件 2: LB (Q, G) >= r2 を満た= r1 のとき，d(Q, G, M ) <が成り立つ時，r1 <= SED(Q, G) <= r2 が成り立つ．したがって，
この G は必ず検索結果に含まれるので， SED 計算無しで検索

す M が存在する場合．このとき，r1 <= r2 が成= SED(Q, G) <結果に含める．次に，UB (Q, G) <= LB (Q, G)= r1 または r2 <り立ち，G は明らかに検索結果に含まれる．

終了条件 3: LB (Q, G) < r1 のとき，d(Q, G, M ) < r1 を満た

Algorithm 1: SED 計算アルゴリズム

す M が存在する場合．このとき，SED(Q, G) < r1 が成り立
ち，G は明らかに検索結果に含まれない．
これらの枝刈りと終了条件により SED 計算を高速に実行することができる．

1
2
3

SED 計算アルゴリズム. クエリグラフ Q が与えられたとき，対象グラフ G の SED を以下の手順で求める．

4（ 1 ） 暫定のマッピングを M とする．マッピングしていないある頂点 v ∈ V (Q) に対し，マッピングしていない頂点u ∈ V (G) について，頂点 v および u のラベルが一致するかを調べる．一致するならば Cvm (v, u) = 1, Cvu (v, u) = 0 しないな
らば Cvm (v, u) = 0, Cvu (v, u) = 1 とする．

56V ′ (Q) ←− {u ∈ V (V )|M (u) =| N ull};V ′ (G) ←− {v ∈ V (G)|M (u) =| v ∀u ∈ V (Q)};′
9 foreach u ∈ V (Q) do
10
foreach v ∈ V (G) s.t. v ∈/ M do11
if d(Q, G, M ) = LB (Q, G) then12
return;7813（ 2 ） 頂点 v に対し，クエリグラフの頂点のうちすでにマッピングしている頂点 ∀v ′ ∈ V ′ (Q) s.t. e(v, v ′ ) ∈ E ′ (Q) ⊂ E(Q)

14
15
16

について，L(u) =| ϵ のとき，e(u, M (v )) ∈ E(G) を満たす辺17の個数 Cem (v, u)，満たさない辺の個数 Ceu (v, u) を計算する．

19

L(u) =| ϵ のとき， Cem (v, u) = 0, Ceu (v, u) = |E ′ (Q)| とする．

21′（ 3 ） u を v の マッピ ン グ と し た 場 合 の 編 集 距 離′d(Q, G, M ) = d(Q, G, M ) − Cvm (v, u) − Cem (v, u) が上限値′

UB (Q, G) より小さいとき，UB (Q, G) = d(Q, G, M ) で更新
する．

input : Query graph Q, a target graphs G, lower bound LB (Q, G),
upper bound UB (Q, G)
output: SED(Q, G)
LBcur ←− 0;d ←− |V (Q)| + |E(Q)|;
Return CalcSED(N ull, N ull, LB(Q, G), UB (Q, G), LBcur , d);input : current vertex uu ∈ V (Q), vv ∈ V (G), lower bound
LB(Q, G), upper bound UB (Q, G), LBcur , doutput: SED(Q, G)
procedure CalcSED
if uu is Null thenM (uu) ←- vv

18

20

22
23
24
25
26
27

m
u
Calculating Cv(v, u), Cv(v, u), Cem (v, u), Ceu (v, u);u
LBcur ← LBcur + Cv
(v, u) + Ceu (v, u);md ← d − Cv(v, u) − Cem (v, u));UB (Q, G) ← min(UB (Q, G), d);
if LBcur > min(SED(Q, G), UB (Q, G)) thencontinue;

if isCandidate(Q, G, M ′ ) thenSED(Q, G) ← min(SED(Q, G), d);CalcSED(u, v, LB(Q, G), UB (Q, G), LBcur , d);uCalculating Cv(v, u), Ceu (v, u);u
LBcur ← LBcur + Cv
(v, u) + Ceu (v, u);Matched(u, );
if LBcur > min(SED(Q, G), UB (Q, G)) thenbreak;

Return SED(Q, G);（ 4 ） u を v の マッピ ン グ と し た 場 合 の 編 集 距 離d(Q, G, M ′ ) = d′ (Q, G, M ) + Cvm (v, u) + Cem (v, u) が上限値
UB (Q, G) より小さいとき，UB (Q, G) = d(Q, G, M ′ ) で更新

ムは C++ を利用して実装・実行した．

する．

6. 1 実 験 設 定

疑似コード: アルゴリズム 1 に SED 計算アルゴリズムを示

データセット. データセットは， 分子構造データの AIDS [15],す．擬似コードにおいては，マッピングの編集距離と下限値をBZR [16] を利用する．クエリはデータセットの対象グラフのサそれぞれ (.Q, G, M )，LBcur (Q, G, M ) とし，それぞれインクリ

ブグラフから，頂点数 5 の条件下でランダムに生成した．表 1

メンタルに求める．3 行目に示すように，最初に与える uu, vvにデータセットの詳細を示す．

は Null とする．また， SED の下限値を LB (Q, G)，上限値をUB (Q, G) は経路を用いて算出した値を与える． 6 行目で頂点
uu を vv のマッピングとする．9–26 行目で，マッピングの編
集距離と下限値を求め，SED の上限値を更新しながら，枝刈りする．isCandidate(Q, G, M ′ ) は Top-k 検索と範囲検索それぞれの枝刈り判定を行う．11, 12 行目で，SED の下限と一致する編集距離を見つけた場合にその値を SED の値として返す．

13–19 行目で，マッピングの編集距離を計算し，上限値を更新
した後，枝刈りを行うか判定する．20 行目でより小さい編集
距離で SED の値を更新し，21 行目で，再帰的にこの関数を呼び，次の頂点のマッピングを行う．22–26 行目で，u がラベル

ϵ の頂点とマッピングする場合，すなわち対象グラフの頂点とマッピングしない場合に，LBcur (Q, G, M ) の更新，マッチ処理と，枝刈り判定を行う．

6 実

験

比較手法. 比較手法として，SED 問合せの厳密解および近似解をを計算する手法を用いる．厳密解を計算する手法として，素朴な手法 Naive (exact), Ctree (exact) [2], さらに，4. 3 で述
べた経路索引を利用し，5 節で述べた提案 SED 計算アルゴリ
ズムを適用する提案手法 Ours (exact) を用いる．Naive (exact)
は SED 計算には Cvm (v, u) のみ考慮する簡単な枝刈りを適用
し，全ての対象グラフの SED を計算する手法である．
近似解を計算する手法では，Ctree で使用される近似 SED
計算手法を利用する． 近似 SED 計算は，クエリの頂点に対し，対象グラフのまだマッピングしていない頂点の中からラベルが一致する頂点を選び，マッピングする手法である．それぞれ Naive (approx), Ctree (approx), Ours (approx) と表記する．

Ours では最大経路長 n を 5 とする．また，Ctree は Top-k
検索に特化しているため，範囲検索の実験では，検索範囲の上界よりも索引利用で導出した下限値が小さいときに枝刈りする
技術を適用した．

本章では，提案手法の有用性の確認のため，Top-k 検索と範評価方法. それぞれの比較手法で Top-k 検索と範囲検索の検索

囲検索それぞれにおける検索効率，精度を評価する．実験は時間と精度を評価する．Top-k 検索においては，k = 10 とし，AMD EPYC 7542 32-Core Processor， 2TB メモリを搭載し範囲検索においては，対象グラフ数に対する正解の出力個数のた Ubuntu 18.04.6 LTS サーバ上で実行し，全てのアルゴリズ

割合が 10% となる検索範囲とする．検索精度では，Top-k 検索表 1: データセット
名前

AIDS
BZR

グラフ数 平均頂点数

表 2: 平均検索時間．15 日以内に 50 クエリが終了しなかった

平均辺数

合計ラベル種類数

対象グラフ

1811

14.02

14.50

27

クエリグラフ

50

5.00

4.18

7

405

35.75

38.36

10

対象グラフ
クエリグラフ

50

5.00

4.00

場合 DNF とする．
Top-10 検索

手法

AIDS

範囲検索

BZR

Naive 22027.67 1239.92

6

exact

AIDS

BZR

22027.67 1239.92

Ctree

DNF

DNF

DNF

DNF

は nDCG@10 [17] と RMSE, 範囲検索では Recall, Precision,

Ours

0.07

0.02

1.63

0.58

F1 の平均値で評価する．nDCG@10，Recall, Precision, およ

Naive

0.16

0.05

0.16

0.05

び F1 の値の範囲は [0, 1] であり， 大きい値が高精度であるこ

approx Ctree

0.15

0.03

0.15

0.01

とを意味する．RMSE は小さい値が高精度であることを示す．

Ours

0.13

0.06

0.16

0.05

評価実験結果を示す．

6. 2. 1 検 索 時 間

Search time [sec]提案手法の検索時間と精度および経路抽出の時間とサイズの

1×106
100000

表 2 に Top-10 検索と範囲検索の検索時間を示す．結果よ10000

Naive (exact)
Naive (approx)
Ctree (approx)
Ours (exact)
Ours (approx)

1000
100
10
1

せ終了のために多くの SED 計算が必要となる．これにより，

AIDS, BZR では Ours (exact) は Ours (approx) よりも高速である．また，範囲検索においても Ours (exact) は Naive (exact)
に対し大幅に検索時間を削減し，近似手法の Naive (approx),

10
1

0.01
0.001
Query

Query

(a) AIDS(b) BZR

図 2: Top-10 検索時間
1×106

Search time [sec]100000
10000

1×106

Naive (exact)
Naive (approx)
Ctree (approx)
Ours (exact)
Ours (approx)

100000
10000
Search time [sec]

確な SED 計算により早期に SED10 = 0 となることによって(approx) は正確に SED 計算できず，SED10 = 0 による問合

100

0.01

そのものは近似手法のほうが高速であるものの，提案手法は正対象グラフを大幅に枝刈りしているためである．一方で，Ours

Naive (exact)
Naive (approx)
Ctree (approx)
Ours (exact)
Ours (approx)

1000

0.1

であり，特に近似手法よりも高速である．これは，SED 計算

問合せが終了し，5 節で述べた枝刈りによって SED 計算する

10000

0.1

0.001

り，Ours (exact) は Top-10 検索では比較手法の中で最も高速

1×106100000
Search time [sec]6. 2 実 験 結 果

1000
100
10
1

1000
100
10
1
0.1

0.1
0.01

Naive (exact)
Naive (approx)
Ctree (approx)
Ours (exact)
Ours (approx)

0.01
Query

0.001

(a) AIDS

Query(b) BZR

図 3: 範囲検索時間

Ctree (approx), Ours (approx) と同等に高速な検索時間となっ似手法よりも高速である．これは 5 節で述べた検索範囲に特化た．これは，提案手法は経路の比較による下限値と上限値計算

した枝刈りで多くの対象グラフを枝刈りしたためである．
6. 2. 2 検 索 精 度が高速であり，さらに下限値と上限値による SED 計算手法が効
果的に枝刈りを行うためである．Ctree (exact) は Naive (exact)

表 3 は Top-10 検索における近似手法の検索精度を示す．

よりも時間を要し，実行が終了しない．これは，グラフ索引を

exact の手法は正確な SED を算出するため， nDCG@10 は 1,

近似なしで計算すると，計算コストが大きいためである．した

RMSE は 0 となる．結果より， いずれの近似手法も同程度でがって，Ctree が利用するグラフ索引は，正確な SED 計算に不あり，Naive はわずかに nDCG@10 が小さく，さらに Ctree は適である．一方で，提案手法は経路から高速に上限値と下限値

Naive, Ours と比べて両方のデータセットでわずかに RMSE がを計算できるため，正確な SED 計算を高速に計算可能である．

大きい．これは，近似計算では正しい SED を求められず，上

図 2, 3 にそれぞれ Top-10 検索，範囲検索の詳細を示す．そ位から同立の SED となった対象グラフが偶然上位 10 番目以

れぞれのプロットは，クエリの検索時間を昇順に並べた検索時内に入る/入らないによって，出力結果が異なったためである．

間を示す．左端が最も検索時間が短いクエリの検索時間，右端

さらに，BZR データセットでは， AIDS データセットと比べが最も検索時間が長いクエリの検索時間を表す．AIDS, BZRていずれの手法も nDCG@10 は高く Top-k の精度は高いが，について，Ours (exact) は Ctree (approx) と比べて，同順位の一方で RMSE も大きく正確な SED の値が計算できていない．

クエリにおいてそれぞれ最大 5.5 倍，7.2 倍高速な検索時間とBZR データセットの方が正解の SED が 0 であるものが多く，なった．これは，上述のように，提案手法はグラフサイズ昇順

SED の値が実際と大きく異なっても BZR では上位 k 個を正による計算で高速に SED を 10 個以上計算し，SED10 = 0 に解で埋めることができるためである．

よる問合せ終了によって多くの対象グラフを枝刈りするためで

表 4 に範囲検索における近似手法の検索精度を示す．結果よある．また，範囲検索では，Ours (exact) は Naive (exact) に比り，Ours は Naive と同等に正確である．一方で Ctree は BZR

べて大幅に検索時間を削減し，いずれのクエリにおいても実践にてわずかに精度が低い．これは，近似計算による下限値と検的な時間で実行可能である．これは，上限値を更新しながら効索範囲を比較するために，検索範囲内の SED となる対象グラ

果的に枝刈りする SED 計算によって，SED 計算回数が多い場

フを誤って枝刈りするためである．これらの結果は，提案手法

合でも効率的であるためである．加えて，一部のクエリでは近は索引利用によって精度を低下させず，正確な SED を計算で

謝辞 本研究は JST さきがけ JPMJPR18UD および JSPS 科

表 3: 近似手法の Top-10 検索精度手法

研費 JP20H00583 の支援によって行われた．ここに記して謝

AIDS

BZR

nDCG@10 RMSEnDCG@10 RMSE

Naive

0.81

0.25

1.00

1.47

Ctree

0.83

0.31

1.00

1.85

Ours

0.83

0.25

1.00

1.47

意を表す．

文

表 4: 近似手法の範囲検索精度
手法

AIDS

BZR

Recall Precision

F1

Recall Precision

F1

Naive

0.33

0.45

0.14

0.04

0.02

0.02

Ctree

0.33

0.45

0.14

0.03

0.01

0.01

Ours

0.33

0.45

0.14

0.04

0.02

0.02

表 5: 構築時間
構築時間 [秒]索引サイズ [KB]

AIDS BZR

AIDS

BZR

Ctree

27.3

17.1

231.6

178.6

Ours

7.1

4.8

3165.31573.5

手法

きることを示している．さらに，6. 2 節より，提案手法は高速かつ高精度に実践的な SED 問合せ手法である．

6. 2. 3 構 築 時 間
最後に，提案手法の経路抽出と Ctree の索引構築を計算時間とサイズの観点から比較する．表 5 に Ours の経路抽出時間と経路情報のサイズと Ctree の索引構築時間と索引のサイズを示
す．結果より，構築について Ours は Ctree の 3 倍程度高速である．これは，グラフに基づく索引よりも経路抽出は計算量が小さく，さらに Ctree は木構造を構築するためである．また，サイズは，経路を保持する Ours はグラフを索引する Ctree より大きい．これは，Ours では構造体で経路を表現しており，多くのポインタと構造体を使っている一方で，Ctree は中間の頂点に保持するグラフをシンプルな配列を利用して保持するためである．しかし，最大でも 3MB 程度であり，これは小規模な計算機でも十分に機能する．したがって，提案手法の経路情報は，
高速かつ現実的な空間コストで構築可能である．

7 おわりに本稿では，グラフの経路構築と検索および SED 計算アルゴ
リズムにおける枝刈りによる，効率的で高精度な SED 問合せを提案した．本手法では，対象グラフの SED の上限値と下限値を計算することで，計算対象を枝刈りし，さらにグラフのSED 計算そのものも高速化した．実験では，提案手法は高速かつ正確に SED 問合せであり，有用であることを示した．
今後の展望としては，経路以外の索引による上限値と下限値の導出と，それらを利用する検索と SED 計算のアルゴリズムのさらなる改良で，より効率的な検索を目指す．また，提案手法では Top-k 検索においてグラフサイズを考慮した計算順であるが，対象グラフ数などの特徴に応じた計算順により，より効率的な検索を目指す．

献[1] Diane J. Cook and eds Lawrence B. Holder. Mining graphdata. 2006.
[2] Huahai He and Ambuj K Singh. Closure-tree: An index
structure for graph queries. In Proceedings of the ICDE,
pp. 38–38, 2006.
[3] Rishabh Ranjan, Siddharth Grover, Sourav Medya,
Venkatesan Chakaravarthy, Yogish Sabharwal, and Sayan
Ranu. Greed: A neural framework for learning graph distance functions. In Advances in Neural Information Processing Systems, 2022.
[4] Bruno T Messmer and Horst Bunke. A new algorithm forerror-tolerant subgraph isomorphism detection. Proceedingsof the TPAMI, Vol. 20, No. 5, pp. 493–504, 1998.
[5] Aravind Sankar, Sayan Ranu, and Karthik Raman. Predicting novel metabolic pathways through subgraph mining.
Bioinformatics, Vol. 33, No. 24, pp. 3955–3963, 2017.
[6] Arlei Silva, Wagner Meira Jr, and Mohammed J Zaki.
Mining attribute-structure correlated patterns in large attributed graphs. arXiv preprint arXiv:1201.6568, 2012.
[7] Zhiping Zeng, Anthony KH Tung, Jianyong Wang, Jianhua
Feng, and Lizhu Zhou. Comparing stars: On approximating
graph edit distance. VLDB Endowment, Vol. 2, No. 1, pp.
25–36, 2009.
[8] Xiang Zhao, Chuan Xiao, Xuemin Lin, Wei Wang, andYoshiharu Ishikawa. Eﬃcient processing of graph similarity
queries with edit distance constraints. The VLDB Journal,
Vol. 22, No. 6, pp. 727–752, 2013.
[9] Haichuan Shang, Xuemin Lin, Ying Zhang, Jeﬀrey Xu Yu,
and Wei Wang. Connected substructure similarity search.
In Proceedings of the ACM SIGMOD, pp. 903–914, 2010.
[10] Guoren Wang, Bin Wang, Xiaochun Yang, and Ge Yu. Efﬁciently indexing large sparse graphs for similarity search.
IEEE Transactions on Knowledge and Data Engineering,Vol. 24, No. 3, pp. 440–451, 2010.
[11] Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou
Sun, and Wei Wang. Simgnn: A neural network approach
to fast graph similarity computation. In Proceedings of the
ACM WSDM, pp. 384–392, 2019.
[12] Juris Hartmanis. Computers and intractability: a guide to
the theory of np-completeness (michael r. garey and davids. johnson). Siam Review, Vol. 24, No. 1, p. 90, 1982.
[13] James Cheng, Yiping Ke, Wilfred Ng, and An Lu. Fgindex: towards veriﬁcation-free query processing on graphdatabases. In Proceedings of the ACM SIGMOD, pp. 857–
872, 2007.
[14] Shijie Zhang, Shirong Li, and Jiong Yang. Gaddi: distanceindex based subgraph matching in biological networks. In
Proceedings of the EDBT, pp. 192–203, 2009.
[15] Kaspar Riesen and Horst Bunke. Iam graph database repository for graph based pattern recognition and machine learning. In Proceedings of the SPR and the SSPR, Vol. 5342,
pp. 287–297, 2008.
[16] Jeﬀrey J Sutherland, Lee A O’brien, and Donald F Weaver.
Spline-ﬁtting with a genetic algorithm: A method for developing classiﬁcation structure- activity relationships. Journal of chemical information and computer sciences, Vol. 43,
No. 6, pp. 1906–1915, 2003.
[17] Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt
Deeds, Nicole Hamilton, and Greg Hullender. Learning torank using gradient descent. In Proceedings of the ICML,
pp. 89–96, 2005.