Affiliations: Tokyo Research Laboratory IBM Japan 1623-14,
Shimotsuruma, Yamato, Kanagawa, 242-8502, Japan. inokuchi@jp.ibm.com | The Institute of Scientific and Industrial Research
Osaka University 8-1, Mihogaoka, Ibaraki, Osaka, 567-0047, Japan.
washio@ar.sanken.osaka-u.ac.jp; motoda@ar.sanken.osaka-u.ac.jp
Abstract: The derivation of frequent subgraphs from a dataset of labeled
graphs has high computational complexity because the hard problems of
isomorphism and subgraph isomorphism have to be solved as part of this
derivation. To deal with this computational complexity, all previous approaches
have focused on one particular kind of graph. In this paper, we propose an
approach to conduct a complete search for various classes of frequent subgraphs
in a massive dataset of labeled graphs within a practical time. The power of
our approach comes from the algebraic representation of graphs, its associated
operations and well-organized bias constraints to limit the search space
efficiently. The performance has been evaluated using real world datasets, and
the high scalability and flexibility of our approach have been confirmed with
respect to the amount of data and the computation time.
