Time and Space Efficient Discovery of Maximal
Geometric Graphs
Hiroki Arimura1 , Takeaki Uno2 , and Shinichi Shimozono3
1

Hokkaido University, Kita 14-jo, Nishi 9-chome, Sapporo 060-0814, JAPANarim@ist.hokudai.ac.jp
2
National Institute of Informatics, Tokyo 101–8430, JAPAN
uno@nii.jp
3
Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, JAPANsin@ai.kyutech.ac.jp

Abstract. A geometric graph is a labeled graph whose vertices are points

in the 2D plane with an 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 techniquesof 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 outputsensitive 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.
Keywords: geometric graphs, closed graph mining, depth-first search, rightmost expansion, polynomial delay polynomial space enumeration algorithms.

1 Introduction
Background. There has been increasing demands for efficient methods of extracting
useful patterns and rules from weakly structured datasets due to rapid growth of boththe amount and the varieties of nonstandard datasets in scientific, spatial, and relational
domains. Graph mining is one of the most promising approaches to knowledge discovery
from such weakly structured datasets. The following topics have been extensively studied
for the last few years: frequent subgraph mining [6, 12, 17, 27], maximal (closed) subgraphmining [3, 9, 20, 25] and combination with machine learning [21, 28]. See surveys, e.g. [8,24], for the overviews.
The class of geometric graphs. In this paper, we address a graph mining problem
for the class G of geometric graphs. Geometric graphs (geographs, for short) [15] are a
special kind of vertex- and edge-labeled graphs whose vertices have coordinates in the 2D
plane R2 , while labels represent geometric features and their relationships. The matching
relation for geographs is defined through the invariance under a class of geometric transformations, such as translation, rotation, and scaling in the plane, in addition to the usualconstraint for graph isomorphism. We do not consider the mirror projection, but the extension is simple (consider the mirror projection when we compute the canonical form).
Geographs are useful in applications concerned with geometric configurations, e.g., theanalysis of chemical compounds, geographic information systems, and knowledge discovery from vision and image data.
Maximal pattern discovery problem. For the class of geometric graphs, Kuramochi
and Karypis presented an efficient mining algorithm gFSG for the frequent geometricsubgraph mining, based on Apriori-like breadth-first search [15]. However, the frequent
pattern mining poses a problem in that it can easily produce an extremely large numberof solutions, which degrades the performance and the comprehensivity of data mining toa large extent. The maximal subgraph mining problem 4 , on the other hand, asks to find
only all maximal patterns (closed patterns) appearing in a given input geometric graph D,
where a maximal pattern is a geometric graph which is not included in any properly larger
subgraph having the same set of occurrences in D. Since the set M of all maximal patterns
is expected to be much smaller than the set F of all frequent patterns and still contains thecomplete information of D, maximal subgraph mining has some advantages as a compact
representation to frequent subgraph mining.
Difficulties of maximal pattern mining. However, there are a number of difficulties
in maximal subgraph mining for geometric graphs. In general, maximal pattern mining has
a large computational complexity [4, 26]. So far, a number of efficient maximal patternalgorithms have been proposed for sets, sequences, and graphs [3, 9, 20, 22, 25]. Somealgorithms use explicit duplicate detection and maximality test by maintaining a collectionof already discovered patterns. This requires a large amount of memory and delay time,and introduces difficulties in the use of efficient search techniques, e.g., depth-first search.
For these reasons, output-polynomial time computation for the maximal pattern problem isstill a challenge in maximal geometric graphs. Moreover, the invariance under geometrictransformation for geometric graphs adds another difficulty to geometric graph mining. In
fact, no depth-first algorithm has been known to date even for frequent pattern mining.
Main result. The goal of this paper is to develop a time and space efficient algorithm
that can work well in theory and practice for maximal geometric graphs. As our main
result, we present an efficient depth-first search algorithm MaxGeo that, given an input
geometric graph, enumerates all frequent maximal pattern P in M without duplicates inO(m(m + n)||D||2 log ||D||) = O(n8 log n) time per pattern and in O(m) = O(n2 )space, with the maximum number m of occurrences of a pattern other than trivial patterns,
the number n of vertices in the input graph, and the number ||D|| of vertices and edges in
the input graph. This is a polynomial delay and polynomial time algorithm for the maximal
pattern discovery problem for geometric graphs. This is the first result establishing theoutput-sensitive complexity of maximal graph mining for geometric graphs.
Other contributions of this paper. To cope with the difficulties mentioned above, we
devise some new techniques for geometric graph mining.
(1) We define a polynomial time computable canonical code for all geometric graphs in
G, which is invariant under geometric transformations. We give the first polynomial
4

Although the maximal pattern discovery is more often called closed pattern discovery, we use theterm “maximal” rather than “closed” in this paper for the consistency with works in computational
complexity and algorithms area [4, 26].

delay and polynomial space algorithm FreqGeo for the frequent geometric subgraphmining problem as a bi-product.
(2) We introduce the intersection and the closure operation for G. Using these tools, wedefine the tree-shaped search route T for all maximal patterns in G. We propose a newpattern growth technique arising from reverse search and closure extension [18] fortraversing the search route R by depth-first search.
Related works. There have been closely related researches on 1D and 2D point set
matching algorithms, e.g. [2], where point sets are the simplest kind of geometric graphs.
However, since they have mainly studied exact and approximate matching of point sets,
the purpose is different from this work.
A number of efficient maximal pattern mining algorithms have been presented for
subclasses of graph, trees, and sequences, e.g., general graphs [25], ordered and unordered
trees [9], attribute trees [3, 20], and sequences [4, 5, 23]. Some of them have output-sensitive
time complexity as follows. The first group deal with the mining of “elastic” or “flexible”
patterns, where the closure is not defined. CMTreeMiner [9], BIDE [23], and MaxFlex [5]are essentially output-polynomial time algorithms for location-based maximal patterns
though it is implicit. They are originally used as pruning for document-based maximal
patterns [5].
The second group deal with the mining of “rigid” patterns which have closure-like
operations. LCM [22] proposes ppc-extension for maximal sets, and then CloATT [3] andMaxMotif [4] generalize it for trees and sequences. They together with this paper arepolynomial delay and polynomial space algorithms.
Some of the other maximal pattern miners for complex graph classes, e.g.,CloseGraph [25],adopt frequent pattern discovery augmented with,e.g., maximality test and duplicate detection although output-polynomial time computability seems difficult to achieve with thisapproach.
Organization of this paper. Section 2 introduces the maximal pattern mining forgeometric graphs. Section 3 gives the canonical code and the frequent pattern mining.
In Section 4, we present polynomial delay and polynomial space algorithm MaxGeo for
maximal pattern mining, and in Section 5, we conclude.

2 Preliminaries
We prepare basic definitions and notations for maximal geometric graph mining. We denote by N and R the set of all natural numbers and the set of all real numbers, resp.
2.1 Geometric transformation and congruence.
We briefly prepare basic of plane geometry [11, 13]. In this paper, we consider geometricobjects, such as points, lines, point sets, and polygons, on the two-dimensional Euclidean
space E = R2 , also called the 2D plane. A geometric transformation T is any mapping
T : R2 → R2 , which transforms geometric objects into other geometric objects in the2D plane R2 . In this paper, we consider the class Trgeo called rigid transformations ofgeometric transformations consisting of three basic types of geometric transformations:rotation, scaling, and their combinations. In general, any geometric transformation T ∈Trgeo can be represented as a 2D affine transformation T : x 7→ Ax+t, where A is a 2×2

y
3.0

5

rotationB

scaling
2.0

2

C

4

7

B

B

3

6

B
B

geometric graph G

translation

1.0

1
1.0

Fig. 1. Three basic types of geometric transformations

B

B

2.0

3.0

B

8
4.0

Fig. 2. A geometric database D with V{1, . . . , 8}, ΣV = ∅, and ΣE = {B, C}x=nonsingular matrix with det(A) 6= 0, and t is a 2-vector. Such T is one-to-one and onto.
In addition, if T ∈ Trgeo then T preserves the angle between two lines. It is well-known
that any affine transformation can be determined by a set of three non-collinear points andtheir images. For Trgeo , we have the following lemma.
Lemma 1 (determination of unknown transformation). Given two distinct points inthe plane x1 , x2 and the two corresponding points x01 , x02 , there exists a unique rigid
transformation T in Trgeo , denoted by T(x1 x2 ; x01 x02 ), such that T (xi ) = x0i for every
i = 1, 2.
T(x1 x2 ; x01 x02 ) is computable in O(1) time. The above lemma is crucial in the following discussion. For any geometric object O and T ∈ Trgeo , we denote the image of O
via T by T (O). The inverse image of O via T is T −1 (O).
2.2 Geometric graphs
We introduce the class of geometric graphs according to [15] as follows. Let ΣV and ΣE bemutually disjoint sets of vertex labels and edge labels associated with total orders <Σ onΣV ∪ΣE . In what follows, a vertex is always an element of N. A graph is a vertex and edgelabeled graph G = (V, E, λ, µ) with a set V of vertices and a set E ⊆ V 2 of edges. Eachx ∈ V has a vertex label λ(x) ∈ ΣV , and each e = xy ∈ E ⊆ V 2 represents an unorderededge {x, y} with an edge label µ(e) ∈ ΣE . Two graphs Gi = (Vi , Ei , λi , µi ) (i = 1, 2)
are isomorphic if they are topologically identical to each other, i.e., there is a bijection
φ : V1 → V2 such that (i) λ1 (x) = λ2 (φ(x)), (ii) for every xy ∈ (V1 )2 , xy ∈ E1 iff
φ(x)φ(y) ∈ E2 , and (iii) for any xy ∈ E1 , µ1 (xy) = µ2 (φ(x)φ(y)). The mapping φ iscalled an isomorphism of G1 and G2 .
A geometric graph is a representation of some geometric object by a set of features
and their relationships on a collection of 2D points.
Definition 1 (geometric graph). Formally, a geometric graph (or geograph, for short)
is a structure G = (V, E, c, λ, µ), where (V, E, λ, µ) is an underlying labeled graph andc : V → R2 is a one-to-one mapping called the coordinate function. Each vertex v ∈ V
has the associated coordinate c(v) ∈ R2 in the 2D plane as well as its vertex label λ(v).
We refer to the components V, E, c, λ and µ of G as VG , EG , cG , λG and µG .
We here assume that no two vertices or edges have the same coordinates, i.e., for
any two vertices v and u, c(v) 6= c(v). We note that even if there are vertices mappedon the same points, we can shrink them into a vertex. This for all such vertices takes
O(|VG | log |VG |) time. We denote by G the class of all geometric graphs over ΣV and ΣE .

Alternative representation for geographs. Alternatively, a geometric graph can be
simply represented as a collection of labeled objects G = V ∪E, where V = {hxi , λi i | i =1, . . . , n } ⊆ R2 × ΣV , and E = { hei , µi i | i = 1, . . . , m } ⊆ R2 × R2 × ΣE . Each hx, λi
is a labeled vertex for a vertex v with c(v) = x and λ(v) = λ, and each hc(v), c(u), µi is
a labeled edge for an edge e = vu with label µ(e) = µ. A labeled object refers to either alabeled vertex or a labeled edge. Let OL = (R2 × ΣV ) ∪ (R2 × R2 × ΣE ) be a domain oflabeled objects. We assume the lexicographic order <OL over OL by extending those overN, R2 , ΣV and ΣE . Since the correspondence between G and G is obvious, we will often
use both representations interchangeably. For instance, we may write G ∪ {hv, x, λi} or
G \ {he, µi}. Since c is one-to-one, we may also write x ∈ G instead of x ∈ c(VG ).
2.3 Geometric isomorphism and matching
Now, let us extend the notions of isomorphisms and matchings for geographs as in [15]. Let
G1 , G2 ∈ G be any geographs. Then, G1 and G2 are geometrically isomorphic, denotedby G1 ≡ G2 , if there are an isomorphism φ of G1 and G2 and a transformation T ∈ Trgeosuch that T (c(x)) = c(φ(x)) for every vertex x of G1 . The pair hφ, T i is a geometricisomorphism of G1 and G2 .
Let G = (V, E, c, λ, µ) be a geograph. A geograph H is a geometric subgraph of G,
denoted by H ⊆ G, if H is a substructure of G, that is, (i) VH ⊆ V and EH ⊆ E hold,and (ii) mappings λH , µH , and cH are the restrictions of λ, µ, and c, respectively, on VH .
Now, we define the matching of geographs in terms of geometric subgraph isomorphism.
Definition 2 (geometric matching). A geograph P geometrically matches a geograph G(or, P matches G) if there exists some geometric subgraph H of G that is geographicallyisomorphic to P with a geometric isomorphism hφ, T i. Then, we call the rigid transformation T a geometric matching function from P to G or an occurrence of P in G.
We denote by M(P, G) ⊆ Trgeo the set of all geometric matching functions from P to
G. We omit φ from hφ, T i above because if P matches G then, there is at most one vertex
v = φ(u) ∈ VG of G such that c(v) = T (c(u)) for each u ∈ VP of P . Clearly, P matches
G iff M(P, G) 6= ∅. If P matches G then we write P v G and say P occurs in G or P
appears in G. If P v Q and Q 6v P then we define P @ Q. We can observe that if bothP v Q and Q v P hold then P ≡ Q, that is, P and Q are geometrically isomorphic. If wetake the set G of the equivalence classes of geographs modulo geometric isomorphisms,
then v is a partial order over G.
2.4 Patterns, occurrences, and frequencies
Let k ≥ 0 be a nonnegative integer. A k-pattern (or k-geograph) is any geograph P ∈ Gwith k vertices. From the invariance under Trgeo , we assume without any loss of generality that if P is a k-pattern then VP = {1, . . . , k}, and if k ≥ 2 then P has the fixed
coordinates c(1) = (0, 0) and c(2) = (0, 1) ∈ R2 for its first two vertices in the local
Cartesian coordinate. An input geometric database of size n ≥ 0 is a single geograph
D = (V, E, c, λ, µ) ∈ G with |V | = n. We denote |V | + |E|, which is the total sizeof D, by ||D||. D is also called an input geograph. Fig. 2 shows an example of an input
geometric database D with V = {1, . . . , 8} over ΣV = ∅, and ΣE = {B, C}.
Let P ∈ G be any k-pattern. Then, the location list of pattern P in D is defined by
the set L(P ) of all rigid transformations that matches P to the input geograph D, i.e.,L(P ) = M(P, D). The frequency of P is |L(P )| ∈ N. For an integer 0 ≤ σ ≤ n, called aminimum support (or minsup), P is σ-frequent in D if its frequency is no less than σ.
Unlike ordinary graphs, the number of distinct matching functions in L(P ) is boundedby polynomial in the input size.
Lemma 2. For any geograph P , |L(P )| is no greater than n2 under Trgeo .
Proof. From Lemma 1, the images x01 x02 of just two points x1 x2 in the plane are sufficient
to determine T(x1 x2 ; x01 x02 ) in Trgeo . Thus, the result follows.
tuLemma 3 (monotonicity). Let P, Q be any geographs. (i) If P ≡ Q then L(P ) = L(Q).
(ii) If P v Q then L(P ) ⊇ L(Q). (iii) If P v Q then |L(P )| ≥ |L(Q)|.
2.5 Maximal pattern discovery
From the monotonicity of the location list and the frequency in Lemma 3, it is natural toconsider maximal subgraphs in terms of v preserving their location lists as follows.
Definition 3 (maximal geometric patterns). A geometric pattern P ∈ G is said to be
maximal in an input geograph T if there is no other geometric pattern Q ∈ G such that (i)P @ Q and (ii) L(P ) = L(Q) hold.
In other words, P is maximal in D if there is no pattern strictly larger than P thathas the same location list as P ’s. Equivalently, P is maximal iff any addition of a labeled
object to P makes L(P ) strictly smaller than before. We denote by Fσ ⊆ G be the set ofall σ-frequent geometric patterns in D, and by M ⊆ G be the set of all maximal geometricpatterns in D under T. The set of all σ-frequent maximal patterns is Mσ = M ∩ Fσ .
Now, we state our data mining problem as follows.
Definition 4 (maximal pattern enumeration problem). The maximal geometric pattern
enumeration problem is, given an input geograph D ∈ G of size n and a minimum support
1 ≤ σ ≤ n, to enumerate every frequent maximal geometric pattern P ∈ Mσ appearing
in D without outputting no isomorphic two.
Our goal is to devise a light-weight and high-throughput mining algorithm for enumerating all maximal patterns appearing in a given input geograph. This is paraphrased interms of output-sensitive enumeration algorithms in Section 2.6 as a polynomial delay andpolynomial space algorithm for solving this problem. This goal has been an open question
for M and even for Fσ so far.
We can define a different notion of location list D(P ), called the document list, definedas the set of input graphs in which a pattern appears, and maximality based on D(P ) in asimilar way. Actually, location-based maximality is a necessary condition for documentbased maximality. However, we do not go further in this direction.
2.6 Model of computation
We make the following standard assumptions in computational geometry [19]: For every
point p = (x, y) ∈ E, we assume that its coordinates x and y have infinite precision.
Our model of computation is the random access machine (RAM) model with O(1) unit
time arithmetic operations over real numbers as well as the standard functions of analysis
1((·) 2 , sin, cos, etc) [1, 19].

An enumeration algorithm A is an output-polynomial time algorithm if A finds all
solutions S ∈ S without duplicates on a given input I in total polynomial time both in
the input size and the output size. A is polynomial delay if the delay, which is the maximum computation time between two consecutive outputs, is bounded by polynomials in
the input size. If A is polynomial delay, then A is also output-polynomial time. A is apolynomial space algorithm if the maximum space A uses is bounded by a polynomial in
the input size.

3 Algorithm for Frequent Pattern Discovery
3.1 Canonical encoding for geographs
In this subsection, to properly handle the geometric isomorphism among the isomorphic
patterns, we introduce the canonical code for geometric patterns, which is invariant undertransformations in Trgeo . Let P be any k-pattern with VP = {1, . . . , k}. Recall that thefirst two vertices of P have the fixed coordinates c(1) = (0, 0), c(2) = (0, 1) ∈ R2 in theirlocal 2D plane.
Defining
a code Suppose that the vertex set VP of P has at least two vertices. LetP
o = ( v∈VP c(v))/|VP | be the centroid (the center) of the vertices in P , which is theaverages of x-coordinates and y-coordinates of all vertices in P . We choose a point x ∈P, x 6= o having the minimum Euclidean distance to o called the base point. Denote by Q
the pattern obtained by transforming P in a polar coordinate system such that o is mapped
to the origin and x is mapped to (0, 1), where the first element of the coordinates gives
the angle. We define the coordinate of the origin by (0, 0). Let O = V Q ∪ {hc(v), c(u) −c(v), µuv i, hc(u), c(v) − c(u), µuv i | uv ∈ EQ }. Then, the code Code(P, x) of P is
defined by the elements of O sorted in lexicographic order.
Clearly, there are at most k distinct Code(P, x) depending on the choice of the basepoint x. Then, the canonical code Code∗ (P ) for pattern P is defined by the lexicographically minimum code among the codes of P . A pattern P is said to be canonical if (i) it
has no vertex, (ii) it has one vertex at (0, 0), or (iii) its vertices are indexed in the order of
its canonical code.
Theorem 1 (characterization of canonical code). For any P, Q ∈ G of size k ≥ 0,
Code∗ (P ) = Code∗ (Q) iff P ≡ Q under Trgeo .
A code can be computed in O(k 2 log k) time for any k-pattern P and base point x,
then the code for another base point is obtained by shifting it. Hence, we can computethe canonical code of P in O(k 2 log k) time. The purpose of the canonical code and thecanonical pattern is to define a representative pattern among the geometric isomorphic
patterns. Thus, our task is to enumerate all σ-frequent canonical patterns.
3.2 Perfect elimination sequences
Before studying enumeration or generation of each pattern, we consider the reverse processof enumeration, the decomposition of a given geograph. Let P ∈ G be any k-geograph.
We define perfect elimination sequence by the sequence elimseq(P ) = (ξk , . . . , ξ1 ) ∈OL∗ obtained by the procedure Elimination Ordering in Fig. 3. Note that the elimination
sequence (ξk , . . . , ξ1 ) for P is not identical to the reverse of the canonical code Code∗ (P )since the i-th element ξi is selected based on the canonical code of the current geographPi not with the order defined on the initial graph P = Pk .

Elimination Ordering(P )1: i = 1; j = 1; P1 = P ;2: while Pi 6= ∅ do
3:ho, li = tail(Pi ) based on the canonical code Code∗ (Pi );4:
Pi+1 = Pi − {ho, li}; ξj = ho, li and j = j + 1;
5: end while
6: return elimseq(P ) = (ξk , . . . , ξ1 );Fig. 3. Procedure for computing perfect elimination elimseq(P ) for geometric graph P

FreqGeo(σ : minsup, D : input database)
1: call Expand FG(∅, σ, D);
Expand FG(P, σ, D)
1: if |L(P )| < σ then return else output P as a frequent subgraph;
2: for each missing object ξ do
3:
Q = P ∪ {ξ};4:if ξ is the last of Code∗ (Q) then call Expand FG(Q, σ, D);
5: end forFig. 4. Polynomial delay and polynomial space algorithm for the frequent geometric subgraph enumeration problem

3.3 Algorithm for Frequent Pattern Discovery
Fig. 4 shows the algorithm FreqGeo for the frequent geometric subgraph discovery. Starting from the empty graph ∅, FreqGeo searches Fσ from smaller to larger by growing P
with adding new labeled objects one by one. To avoid duplicates, FreqGeo adds a labeled object ξ to the current pattern P only when ξ is the last object in the canonical code
Code∗ (P ∪ ξ) of P ∪ ξ. It corresponds to that any pattern P is generated in the reverse
order of the elimination sequence. Thereby any pattern Q = P ∪ ξ is generated exactly
once only from the pattern Q \ ξ where ξ is the last object in Code∗ (Q). This ensures thateach σ frequent pattern is output exactly once.
There are infinitely many candidates for the possible labeled object in Line 2 of Fig. 4.
From the next lemma, we can avoid such a blind search by only focusing on missing
objects for P , which is either labeled vertex or edge ξ such that L(P ) ⊇ L(P ∪ {ξ}) 6= ∅holds. From Lemmas 1 and 3, we have the next lemma.
Lemma 4 (missing labeled objects). Let P be a pattern with nonempty L(P ) in D. Any
missing object ξ = ho, li for P is the inverse image of some labeled vertex or labeled edge
π via T for some matching T ∈ L(P ), i.e., ξ = T −1 (π) for some π ∈ D.
From Lemma 4 above, we know that there are at most O(|L(P )|·||D||) = O(|V |2 (|V |+|E|)) missing objects. Thus, Line 2 can be done in polynomial time. By using the technique called occurrence deliver described in [3–5, 22], we can compute the frequencies ofP ∪ {ξ} for all missing objects for P in O(|V |2 (|V | + |E|) log |V |) time. Therefore, theaverage computation time for each output pattern is O(|V |2 (|V | + |E|)k 2 log |V |), where
k is the maximum size of σ-frequent pattern. Combining the above, we have the following
theorem.

Algorithm MaxGeo: (D : input geograph, σ : minsup)
1: ⊥ = Clo(∅);
2: call Expand MaxGeo(⊥, σ, D);//The bottom maximal geograph

Algorithm Expand MaxGeo(P, σ, D)
1: if P is not σ-frequent then return;//Frequency test
2: else output P as a σ-frequent maximal geograph;
3: for each missing labeled object ξ = ho, `i do//Lemma 4
4:
Q = Clo(P ∪ { ξ });5:
if ( P(Q) ≡ P ) then6:call Expand MaxGeo(Q, σ, D);//Recursive call for children
7: endfor
Fig. 5. A polynomial delay and polynomial space algorithm MaxGeo for the
maximal geometric subgraph enumeration problem
Theorem 2 (frequent geograph enumeration). The algorithm FreqGeo in Fig. 4 enumerates all σ-frequent geometric graphs in a given input database D ∈ G in polynomial
delay and polynomial space in the total input size.

4 Algorithm for Maximal Pattern Discovery
In this section, we present an efficient algorithm MaxGeo for the maximal pattern enumeration problem for the class of geographs that runs in polynomial delay and polynomial
space in the input size.
4.1 Outline of the algorithm
Fig. 5 shows our algorithm MaxGeo for enumerating all σ-frequent maximal geometricpatterns in Mσ using backtracking. The key to the algorithm is a tree-like search route
R = R(Mσ ) implicitly defined over Mσ . Then, starting at the root of the search route
R, MaxGeo searches R by jumping from a smaller maximal pattern to a larger one in a
depth-first manner. Each jump is done by expanding each maximal pattern in polynomial
time, thus the algorithm is polynomial delay.
4.2 Intersection and closure operations for geographs
Let G1 and G2 be two geographs with VG1 ∩ VG2 6= ∅. The maximally common geometricsubgraph (MCGS) of G1 and G2 is a geograph which is represented by labeled objects
common to both G1 and G2 . MCGS is unique for geographs, while they are not uniquefor ordinary graphs.
The intersection operation ∩ is reflexive, commutative, and associative over G. For a set
G = {G1 , . . . , Gm } of geographs, we define ∩G = G1 ∩ G2 ∩ · · · ∩ Gm . We can see thatthe computation time for ∩G are bounded by O(||G|| log ||G||). Some literatures [14]give an intersection of labeled graphs or first-order models in a different way which isbased on the cross product of two structures. However, their iterative applications causes

exponentially large intersections unlike ∩G above. Gariiga et al.[10] discussed related
issues.
Now, let us define the closure operation for G.
Definition 5 (closure operator for geographs). Let P ∈ G be a geograph of size ≥ 2.
Then, the closure of P in D is defined by the geograph Clo(P ):\Clo(P ) = { T −1 (D) | T ∈ L(P ) }.
Theorem 3 (correctness of closure operation). Let P be a geograph of size ≥ 2 and D
be an input database. Then, Clo(P ) is the unique, maximal geograph w.r.t. v satisfying
L(Clo(P )) = L(P ).
Proof. We give a sketch of the proof. Let T ∈ Trgeo be any rigid transformation. Then, we
can see that P matches D via T iff P is a geometric subgraph of the inverse image of D
via T , i.e., P ⊆ T −1 (D). Thus, taking the intersection of the inverse image T −1 (D) forall matching T of P , we obtain the unique maximal subgraph having L(P ).
tuLemma 5. For any geographs P, Q ∈ G, the following properties hold:(i) P v Clo(P ). (ii) L(Clo(P )) ≡ L(P ). (iii) Clo(P ) ≡ Clo(Clo(P )).
(iv) P v Q iff L(P ) ⊇ L(Q) for any maximal P, Q ∈ M.
(v) Clo(P ) is the unique, smallest maximal geograph containing P .
(vi) For the empty graph ∅, ⊥ = Clo(∅) is the smallest element of M.
Theorem 4 (characterization of maximal geographs). Let D be an input geograph andP ∈ G be any geograph. Then, P is maximal in D iff Clo(P ) ≡ P .
4.3 Defining the tree-shaped search route
In this subsection, we define a tree-like search route R = (Mσ , P, ⊥) for the depth-firstsearch of all maximal geographs based on a so-called parent function.
Let Q ∈ M be a maximal pattern of vertices at least two such that Q 6= ⊥. For any
labeled object ξ ∈ Q, define the ξ-prefix of Q as the pattern Q[ξ] which is the collectionof the labeled objects prior to ξ in Code∗ (Q). Then, the core index core i(Q) of Q is
the labeled object ξ such that L(Q[ξ 0 ]) 6= L(Q) holds for any ξ 0 prior to ξ in Code∗ (Q).
We can show that if Q 6= ⊥ then core i(Q) is always defined.
Q[core i(Q)] ⊆ Q is the shortest prefix of Q satisfying L(Q[ξ]) = L(Q). Moreover,
if we remove core i(Q) from the prefix Q[core i(Q)], then we have a properly shorter
prefix, and then the location list changes. Now, we define the parent function P that gives
the predecessor of Q.
Definition 6 (parent function P). The parent of any maximal pattern Q ∈ M (Q 6= ⊥)is defined by P(Q) = Clo(Q[ξ] \ {ξ}), where ξ = core i(Q) is the core index of Q.
Lemma 6. P(Q) is (i) always defined, (ii) unique, and (iii) a maximal pattern in M. Moreover, P satisfies that (iv) P(Q) ⊂ Q, (v) | P(Q) | < | Q |, and (vi) L(P(Q)) ⊃ L(Q).
Now, we define the search route for Mσ as a rooted directed graph R(Mσ ) = (Mσ , P, ⊥),where Mσ is the vertex set, P is the set of reverse edges, and ⊥ is the root. For the searchroute, we have the following theorem.
Theorem 5 (reverse search property). For every σ, the search route R(Mσ ) is a spanning tree with the root ⊥ over all the maximal patterns in Mσ .

4.4 A polynomial space polynomial delay algorithm
The remaining thing is to show how we can efficiently traverse the search route R(Mσ )starting from ⊥. However, this is not a straightforward task since R(Mσ ) only has thereverse edges. To cope with this difficulty, we introduce the technique so called reverse
search [7] and the closure extension [18].
Lemma 7. For maximal patterns Q and P , P is the parent of Q only if Q ≡ clo(P ∪ ξ)
holds for a missing object ξ for P .
Proof. Suppose that P is the parent of Q, and ξ 0 is the labeled object preceding and next
to core i(Q) in the canonical code of Q. ξ 0 is included in P , since P = Clo(Q[ξ 0 ]).
Since L(Q) is a collection of T ∈ L(Q[ξ 0 ]) satisfying that T −1 (D) includes core i(Q),together with L(Q[ξ 0 ]) = L(P ), L(P ∪ {ξ}) = L(Q[ξ 0 ] ∪ {ξ}) = L(Q). Thus thestatement holds.
tu
The operation of adding a labeled object and taking its closure is called closure extension. Lemma 7 states that any maximal geometric pattern can be obtained by applying to⊥ closure extensions repeatedly.
From Lemma 7, we can see that to find all children of a pattern P , we have to examine the closure extension for all missing objects for P . Clearly, a closure extension
Q = Clo(P ∪ ξ) of P is a child of P if its parent is P . Since the parent of Q can beobtained by computing its canonical code, we can check whether a closure extension is achild or not in O(k 2 logk) time where k is the number of labeled objects in Q. Since thecomputation of clo(Q) takes O(|L(Q)| × ||D|| log ||D||) time, we obtain the following
theorem.
Theorem 6 (correctness and complexity of MaxGeo). Given an input geograph D withvertex set V and a minimum support threshold σ > 0, the algorithm M AX G EO in Fig. 5
enumerates all σ-frequent maximal geographs in O((m||D||)×((m+n)||D|| log ||D||)) =O(m(m + n)||D||2 log |D|) per maximal geograph with O(||D||) space, where m =O(n2 ) is the maximum size of the location lists.
If σ is not too small, then the number of missing objects to examine will consequently
be small, such as O(n), decreasing the computation time will be short. This is expectedin practical computation. Moreover, in practice, usually almost all (maximal) patterns to
be output have small frequencies close to σ, thus the computation time for the closure
operation is rather short. According to the computational experiments in [4, 22], practicalcomputation time is very short in such cases.
Corollary 1. The maximal geograph enumeration problem is solvable in polynomial delay and polynomial space.

5 Conclusion
We presented a polynomial delay and polynomial space algorithm that discovers all maximal geographs in a given geometric configuration without duplicates. As future works, we
intend to implement and evaluate the experimental performance of the algorithm. Dealing
with the input of many geographs and document occurrence is a straightforward work.

Dealing with polygons is also straightforward, by using sophisticated labels to identify
edges of polygons as a group. Extensions with approximation and constraints, with applications to image processing and geographic information systems, are other future problems.

References
1. Aho, A. V., Hopcroft, J. E., Ullman, J. D., Data Structures and Algorithms, 1983.
2. T. Akutsu, H. Tamaki, T. Tokuyama, Distribution of distances and triangles in a point set andalgorithms for computing the largest common point sets, Discr. & Comp. Geom., 20(3), 307–
331, 1998.
3. H. Arimura, T. Uno, An output-polynomial time algorithm for mining frequent closed attributetrees, In Proc. ILP’05, LNAI 3625, 1–19, August 2005.
4. H. Arimura, T. Uno, A polynomial space and polynomial delay algorithm for enumeration of
maximal motifs in a sequence, In Proc. ISAAC’05, LNCS, 2005.
5. H. Arimura, T. Uno, Effcient algorithms for mining maximal flexible patterns in texts and sequences, TCS-TR-A-06-20, DCS, Hokkaido Univeristy, 2006. (submitting)
6. T. Asai, K. Abe, S. Kawasoe, H. Arimura, H. Sakamoto, and S. Arikawa. Efficient substructure
discovery from large semi-structured data. In Proc. SDM’02, 2002.
7. D. Avis and K. Fukuda, Reverse search for enumeration, Discrete App. Math., 65 21–46, 1996.
8. Y. Chi, R. R. Muntz, S. Nijssen, J. N. Kok, Frequent subtree mining – An overview, Fundam. Inform., 66, 1–2, 161–198, 2005.
9. Y. Chi, Y. Yang, Y. Xia, and R. R. Muntz, CMTreeMiner: mining both closed and maximal
frequent subtrees, In Proc. PAKDD’04, 2004.
10. G. C. Garriga, R. Khardon, L. De Raedt, On mining closed sets in multi-relational data, In
Proc. IJCAI 2007, 804–809, 2007.
11. C. Guerra, Vision and image processing algorithms, Algorithms and Theory of Computation
Handbook, Chapter 22, 22-1–22-23, CRC Press, 1999.
12. A. Inokuchi, T. Washio, H. Motoda, An apriori-based algorithm for mining frequent substructures from graph data, In Proc. PKDD’00, 13–23, LNAI 1910, 2000.
13. A. Jain, Fundamentals of Digital Image Processing, Prentice-Hall, 1986.
14. R. Khardon, Learning function-free horn expressions, Machine Learning 37(3), 241–275, 1999.
15. M. Kuramochi, G. Karypis, Discovering frequent geometric subgraphs, In Proc. IEEE
ICDM’02, 258–265, 2002.
16. S. Nakano, Efficient generation of plane trees, Information Processing Letters, 84, 167–172,
Elsevier,2002.
17. S. Nijssen, J. N. Kok, Effcient discovery of frequent unordered trees, In Proc. MGTS’03, 2003.
18. N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal, Discovering frequent closed itemsets for association rules, In Proc. ICDT’99, 398–416, 1999.
19. F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction, Springer, 1985.
20. A. Termier, M.-C. Rousset, M. Sebag, D RYADE: a new approach for discovering closed frequent
trees in heterogeneous tree databases, In Proc. ICMD’04, 2004.
21. K. Tsuda, T. Kudo, Clustering graphs by weighted substructure mining, Proc. ICML 2006, 953–
960, 2006.
22. T. Uno, T. Asai, Y. Uchida, H. Arimura, An efficient algorithm for enumerating closed patterns
in transaction databases, In Proc. DS’04, LNAI 3245, 16–30, 2004.
23. J. Wang, J. Han, BIDE: Efficient Mining of Frequent Closed Sequences, In Proc. IEEE
ICDE’04, 79–90, 2004.
24. T. Washio, H. Motoda, State of the art of graph-based data mining, SIGKDD Explor., 5, 1, 59–
68, 2003.
25. X. Yan, J. Han, CloseGraph: mining closed frequent graph patterns In Proc. KDD’03, 2003.
26. G. Yang, The complexity of mining maximal frequent itemsets and maximal frequent patterns,
In Proc. KDD’04, 344–353, 2004.
27. M. J. Zaki, Efficiently mining frequent trees in a forest, In Proc. KDD’02, 71–80, 2002.
28. M. J. Zaki, C. C. Aggarwal, XRules: an effective structural classifier for XML data, In
Proc. KDD’03, 316–325, 2003.