情報処理学会 第86回全国大会 会期:2024年3月15日~17日

7K-04
グラフ量子化による近似最近傍探索
○増田颯天(東大),塩川浩昭(筑波大),松井勇佑(東大)
グラフデータセットに対する類似グラフの検索は,化合物検索や異常検知など様々な分野で重要なタスクである.類似度指標としてグラフ編集距離(GED)がよく利用されるが,これはNP困難な問題であり計算量が大きいため,高速な近似計算手法が研究されている.
本研究では,グラフを複数の部分グラフに分割した上でグラフ量子化を行う手法を提案する.分割によるGEDの計算量の削減と,量子化による計算結果の再利用により計算の高速化が可能となる.本研究においては分割手法による量子化誤差と検索精度の変化について評価を行った.