TCS-TR-A-07-26

Date: Mon May 7 22:01:47 2007

Title: Time and Space Efficient Discovery of Maximal Geometric Subgraphs

Authors: H. Arimura, T. Uno, S. Shimozono

Contact:

First name: Hiroki
Last name: Arimura
Address: Division of Computer Science Graduate School of Information Science and Technology Hokkaido University
Email: arim@ist.hokudai.ac.jp

Abstract. A geometric graph is a labeled graph whose vertices are points in the 2D plane with isomorphism invariant under geometric transformations such as translation, rotation, and scaling. While Kuramochi and Karypis (ICDM2002) extensively studied the frequent pattern mining problem for geometric subgraphs, the maximal graph mining has not been considered so far. In this paper, we study the maximal (or closed) graph mining problem for the general class of geometric graphs in the 2D plane by extending the framework of Kuramochi and Karypis. Combining techniques of canonical encoding and a depth-first search tree for the class of maximal patterns, we present a polynomial delay and polynomial space algorithm, MaxGeo, that enumerates all maximal subgraphs in a given input geometric graph without duplicates. This is the first result establishing the output-sensitive complexity of closed graph mining for geometric graphs. We also show that the frequent graph mining problem is also solvable in polynomial delay and polynomial time.