本研究課題では、グラフパターンクラスの設計手法とグラフパターンの多項式時間学習アルゴリズムを開発し、主として次の2つの結果を得た。
(1) 現実に最もよく現れるグラフ構造は木構造である。我々は、辺縮約に基づくグラフ構造の新しいパターン表現「木縮約パターン」を提案し、そのクラスが正データから多項式時間機械学習可能となる条件を示した。さらに、計算困難性・近似困難性についても議論し、木縮約パターンの限界を明らかにした。
(2) グラフ文法の一つである形式グラフ体系(FGS)に対して、高い表現力と高速な機械学習を両立させるグラフパターンクラスが形式グラフ体系のクラスとの関連で議論できることを示した。