TCS -TR-A-07-26

TCS Technical Report

Time and Space Eﬃcient Discovery of Maximal
Geometric Subgraphs

byHiroki Arimura, Takeaki Uno, Shinichi Shimozono

Division of Computer Science
Report Series A
May 7, 2007

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

arimura@ist.hokudai.ac.jp

Phone:
Fax:+81-011-706-7678+81-011-706-7680

Time and Space Eﬃcient Discovery of Maximal
Geometric Subgraphs

May 7, 2007
Abstract

A geometric graph is a labeled graph whose vertices are points in the 2D plane withisomorphism 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 graphmining has not been considered so far. In this paper, we study the maximal (orclosed) 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-ﬁrst 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 ﬁrst result establishing the output-sensitive complexity ofclosed graph mining for geometric graphs. We also show that the frequent graphmining problem is also solvable in polynomial delay and polynomial time.
Keywords: geometric graphs, closed graph mining, depth-ﬁrst search, rightmost expansion,
polynomial delay polynomial space enumeration algorithms.

0

1

Introduction

Backgrounds. By rapid growth of the amount and the varieties of nonstandard datasetsin scientiﬁc, spatial, and relational domains, there are increasing demands for eﬃcient methods
that extracts useful patterns and rules from weakly structured datasets. Graph mining is oneof the most promising approaches for knowlege discovery from such weakly structured datasets,
and the following topics have been extensively studied for the last years: frequent subgraphmining [6, 11, 16, 26], maximal (closed) subgraph mining [3, 8, 19, 24] and combination withmachine learning [20, 27]. See surveys, e.g. [7, 23], for the overviews.
The class of geometric graphs. In this paper, we study a graph mining problem for theclass G of geometric graphs. Geometric graphs (geographs, for short) [14] are a special kind ofvertex- and edge labeled graphs whose vertices have the coordinates in the 2D plane R2 , while
vertex and edge labels are used for representing geometric features and their relationships ofgeometric objects. The matching relation for geographs is deﬁned through invariant undera class of geometric transformations, such as translation, rotation, and scaling in the planein addition to the usual constraint for graph isomorphism. Geographs are useful in applications concering with geometric conﬁgulations, e.g., analysis 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 eﬀcient mining algorithm gFSG for frequent geometric subgraphmining, based on Apriori-like breadth-ﬁrst search [14]. However, frequent pattern mining has
a problem that it can easily produce an extremely large number of solutions, which degrade
the performance and the comprehensivity of data mining to a large extent. On the otherhands, the maximal subgraph mining problem 1 is the problem of ﬁnding all maximal patterns(closed patterns) appearing in a given input geometric graph D, where a maximal pattern is
any geometric graph isomorphic to a subgraph of D which does not have any properly larger
subgraph having the same set of occurrences in the input database. Since the set M of all
maximal patterns is expected to be much smaller than the set F of all frequent patterns but
still contains the complete information of M, maximal subgraph mining has some advantage
as a compact representation to frequent subgraph mining.
Diﬃculties of maximal pattern mining. However, there are a number of diﬃculties
in maximal subgraph mining for geometric graphs. In general, maximal pattern mining has
a large computational complexity [4, 25]. Although a number of eﬃcient maximal patternalgorithms are proposed so far for sets, sequences, and graphs [3, 8, 19, 21, 24], some algorithms
use explicit duplicate detection and maximality test by maintaining a collection of alreadydiscovered patterns, but this requires large memory and delay time, and makes it diﬃcult touse eﬃcient search techniques, e.g., depth-ﬁrst search. For these reasons, output-polynomial
time computation for the maximal pattern problem is still a challenge in maximal geometricgraphs. Besides this, the invariance under geometric transformation for geometric graphs adds
another diﬃculty to geometric graph mining. Thus, a depth-ﬁrst algorithm is not known so
far even for frequent pattern mininig.
1

Although the maximal pattern discoery is more often called closed pattern discovery, we use the term
“maximal” rather than “closed” in this paper for the consistency with works in computational complexity andalgorithms area [4, 25].

1

Main result. The goal of this paper is the development of a time and space eﬃcientalgorithm that can work well in theory and practice for maximal geometric graphs. As our
main result, we present an eﬃcient depth-ﬁrst search algorithm MaxGeo that, given an input geometric graph, enumerates all frequent maximal pattern P in M without duplicates inO(mnk 2 ) = O(n5 ) time per pattern and in O(m) = O(n2 ) space, where k = |P | is the size ofpattern being enumerated, m is the maximum number of its occurrences, and n is the input
size. Thus, this is a polynomial delay and polynomial time algorithm for the maximal patterndiscovery problem for geometric graphs. This is the ﬁrst result establishing the output-sensitive
complexity of closed graph mining for geometric graphs.
Other contributions of this paper. To cope with the diﬃculties mentioned above, we
devise some new techniques for geometric graph mining.
(1) We deﬁne a polynomial time computable canonical representation for all geometric graphs
in G, which is invariant under geometric transformations. As bi-product, we give theﬁrst polynomial delay and polynomial space algorithm FreqGeo for frequent geometricsubgraph mining problem.
(2) We introduce the intersection and the closure operations for G. Using these tools, wedeﬁne the tree-shaped search route T for all maximal patterns in G. Combining the closure
expansion [17] and the rightmost expansion [6, 15, 26], we propose a new pattern growthtechnique called the ppc-expansion (preﬁx-preserving closure expansion) for traversing
the search tree T by depth-ﬁrst search.
(3) As a main result, we present a polynomial delay and polynomial space algorithm MaxGeo
based on depth-ﬁrst search over T for the maximal geometric subgraph mining problem.
This is the ﬁrst output polynomial time algorithm for the problem.
Related works. There are closely related researches on 1D and 2D point set matchingalgorithms, e.g. [2], where point sets are simplest kind of geometric graphs. However, since
they mainly study exact and approximate matching of point sets, but not matching, the purpose
is diﬀerent from this work.
A number of eﬃcient maximal pattern mining algorithms are presented for subclasses ofgraph, trees, and sequences, e.g.: general graphs [24], ordered and unordered trees [8], attributetrees [3, 19], and sequences [4, 5, 22]. Some of them have output-sensitive time complexity as
follows. The ﬁrst group deal with mining of “elastic” or “ﬂexible” patterns, where the closure
is not deﬁned. CMTreeMiner [8], BIDE [22], and MaxFlex [5] are essentially output-polynomial
time algorithms for location-based maxmal patterns though it is implicit. They are originallyused as pruning for document-based maximal patterns [5].
The second group deal with mining of “rigid” patterns which have closure-like operations.
LCM [21] proposes ppc-expansion for maximal sets, and then CloATT [3] and MaxMotif [4]generalize it for trees and sequences. They together with this paper are polynomial delay andpolynomial space algorithms.
Some of other maximal pattern miners for complex graph classes, e.g.,CloseGraph [24], adopt
frequent pattern discovery augmented with,e.g., maximality test and the duplicate detection
although it seems diﬃcult to achieve output-polynomial time computability in this approach.
2

y
3.0

5

rotationB

scaling
2.0

2

C

4

7

B

B

3

6

B
B

geometric graph G

1.0translation

1
1.0

B

B

2.0

3.0

B

8
4.0

x

Figure 1: Three basic types of geometricFigure 2: A geometric database D with V =transformarions{1, . . . , 9}, ΣV = ∅, and ΣE = {B, C}
Organization of this paper. In Section 2, we introduce maximal pattern mining forgeometric graphs. In Section 3, we give the canonical representation and frequent patternmining. In Section 4, we develop present polynomial delay and polynomial space algorithm
MaxGeo for maximal pattern mining, and in Section 5, we conclude.

2

Preliminaries

In this section, we prepare basic deﬁnitions and notations for maximal geometric graph mining.
We denote by N and R the set of all natural numbers and real numbers, resp.
2.1

Geometric transformation and congruence.

We brieﬂy prepare basic of plane geometry [10, 12]. In this paper, we consider geometricobjects, such as points, lines, point sets, and polygons, on the two-dimensional Eucledean 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 the 2D plane R2 . In thispaper, we consider the class Tgeo of geometric transformations consisting of three basic typesof geometric transformations, rotation, and scaling, and their combinations. In general, any
geometric transformation T can be represented as a 2D aﬃne transformation T : ~x 7→ A~x + ~t,
where A is a 2 × 2 nonsingular matrix with det(A) 6= 0, and ~t is a 2-vector. Such T is one-toone. In addition, if T ∈ Tgeo then T preserves the angle of two lines and maps an object to asimilar object. It is well-known that any aﬃne transformation can be determined by a set ofthree non-collinear points and their images. For Tgeo , we have the following lemma.
Lemma 1 (determination of unknown transformation) Given two distinct points in theplane ~x1 , ~x2 and the two corresponding points ~x01 , ~x02 , there exists a unique geometric transformation T , 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 ∈ Tgeo , 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 [14] as follows. Let ΣV and ΣE bemutually disjoint sets of vertex labels and edge labels associated with total orders <Σ . In
3what follows, a vertex is always an element of N. A graph is a node and edge-labeled graph
G = (V, E, λ, µ) with a set of vertices V and a set of edges E ⊆ V 2 . Each x ∈ V has a vertex
label λ(x) ∈ ΣV , and each e = xy ∈ E ⊆ V 2 represents an unordered edge {x, y} with anedge 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., |V1 | = |V2 | and there is a bijection φ : V1 → V2 suchthat for every xy ∈ (V1 )2 , xy ∈ E1 iﬀ φ(x)φ(y) ∈ E2 . The mapping φ is called an isomorphismof G1 and G2 .
A geometric graph is a representation of some geometric object by a set of features andtheir relationships on a collection of 2D points.
Deﬁnition 1 (geometric graph) Formally, a geometric graph (or geograph, for short) is a
structure G = (V, E, c, λ, µ), where (V, E, λ, µ) is an underlying graph and c : V → R2 is
a one-to-one function called the coordinate function. Each vertex v ∈ V has the associatedcoordinate c(v) ∈ R2 in the 2D plane as well as its vertex label λ(v). We refer to the components
V, E, c, λ, µ as VG , EG , cG , λG , µG .
We denote by G the class of all geometric graphs over ΣV and ΣE .
Alternative representation for geograhs. Alternatively, a geometric graph can be simply represented as a collection of labeled object G = V ∪ E, where V = { hvi , ~xi , λi i | i =1, . . . , n } ⊆ N × R2 × ΣV . and E = { hei , µi i | i = 1, . . . , m } ⊆ N × N × ΣE . Each hv, ~x, λi ∈ V λis a labeled vertex for a vertex v with c(v) = ~x and λ(v) = λ, and each he, µi is a labeled edge
for an edge e with label µ(e) = µ. A labeled object refers to either a labeled vertex or a labelededge. Let OL = (N × R2 × ΣV ) ∪ (N × N × ΣE ) be a domain of labeled object. We assume thelexicographic order <O L over OL by extending those over N, 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, we extend the notions of isomorphisms and matchings for geographs as in [14]. Let
G1 , G2 ∈ G be any geographs. Then, G1 and G2 are geometrically isomorphic, denoted byG1 ≡ G2 , if there are an isomorphism φ of G1 and G2 and some transformation T ∈ Tgeo suchthat T (c(x)) = c(φ(x)) for every vertex x of G1 . The pair hφ, T i is a geometric isomorphismof G1 and G2 .
Let G = (V, E, c, λ, µ) be a geograph. A geograph H is a geometric subgraph of G, denotedby H ⊆ G, if GH 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, wedeﬁne the matching of geographs in terms of geometric subgraph isomorphism.
Deﬁnition 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 geographically isomorphic to P with a geometric isomorphism hφ, T i. Then, we call the geometric transformation
T a geometric matching function from P to G or an occurrence of P in G.
4

We denote by M(P, G) ⊆ Tgeo 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 due to the one-to-one
condition of c. Clearly, P matches G iﬀ 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 deﬁne P @ Q.
We can observe that if both of P v Q and Q v P hold then P ≡ Q, that is, P and Q aregeometrically isomorphic. If we take the set G of the equivalence classes of geographs modulo
geometric isomorphisms, then v is a partial order over G.
2.4

Patterns, occurences, 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 Tgeo , we assume without any loss of generalitythat any k-pattern P always has the vertex set VP = {1, . . . , k} and if k ≥ 2 then P has theﬁxed coordinates c(1) = (0, 0) and c(2) = (0, 1) ∈ R2 for its ﬁrst two vertices in the local
Cartesian coordinate. An input geometric database or of size n ≥ 0 is a single geograph D =(V, E, c, λ, µ) ∈ G with |V | = n. D is also called an input geograph. If we receive a collection ofsmall geographs as input, then we merge them into a single graph after appropriately renaming
vertices and their coordinates. Fig. 2 shows an example of an input geometric database D with
V = {1, . . . , 9} over ΣV = ∅, and ΣE = {B, C}.
Let P ∈ G be any k-pattern. Then, the location list of pattern P in D is deﬁned by
the set L(P ) of all geometric transformations that matches P to the input geograph D, i.e.,L(P ) = M(P, D). The frequency of P is |L(P )| ∈ N. Given an integer 0 ≤ σ ≤ n, called aminimum support (or minsup), P is σ-frequent in D if f req(P ) ≥ σ.
Unlike ordinary graphs, the number of distinct matching functions in L(P ) is bounded bypolynomial in the input size.
Lemma 2 For any geograph P , |L(P )| is bounded from above by n2 under Tgeo .
Proof: From Lemma 1, the images ~x01~x02 of just two points ~x1~x2 in the plane are suﬃcient todetermine T(~x1~x2 ; ~x01~x02 ) in Tgeo . Thus, the result follows.
2
Lemma 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.
Deﬁnition 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.

5In other words, P is maximal in D if there is no strictly larger pattern than P that has
the same location list as P . Equivalently, P is maximal iﬀ any addition of a labeled node or alabeled edge to P makes L(P ) strictly smaller than before. We denote by Fσ ⊆ G be the setof all σ-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.
Deﬁnition 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 all frequent maximal geometric patterns P ∈ Mσ appearing in Dwithin G without repetition.
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 in terms of
output-sensitive enumeration algorithms in Section 2.6 as a polynomial delay and polynomial
space algorithm for solving this problem. This goal has been open question for M and evenfor Fσ so far.
We can deﬁne diﬀerent notion of a location list D(P ), called the document list, deﬁned
as the set of input graphs in which a pattern appears, and the maximality based on D(P )in a similar way. Acturally, the location-based maximality is a necessary condition for the
document-based maximality. However, we do not go further in this direction.
2.6

Model of computation

We make the following standard assumptions in computational geometry [18]: For every pointp = (x, y) ∈ E, we assume that its coordinates x and y have inﬁnite precision. Our model ofcomputation is the the random access machine (RAM) model with O(1) unit time arithmetic
1
operations over real numbers as well as the standard functions of analysis ((·) 2 , sin, cos, etc) [1,18].
An enumeration algorithm A is an output-polynomial time algorithm if A ﬁnds all solutions
S ∈ S without duplicates on a given input I in total polynomial time both in the input size
n = ||I|| and the number of output m = |S|. A is a polynomial delay and polynomial spacealgorithm if the delay, which is the maximum computation time between two consecutive
outputs, and the maximum space of A are both bounded by polynomials in n = |D| only. If
A is of polynomial delay then A is also of output-polynomial time.

3

Algorithm for Frequent Pattern Discovery

3.1

Canonical encoding for geographs

In this subsection, we deﬁne a canonical representation of each geograph in G, which is aninvariant under geometric isomorphism in Tgeo . Let P be any k-pattern with VP = {1, . . . , k}.
Recall that the ﬁrst two vertices of P have the ﬁxed coordinates c(1) = (0, 0), c(2) = (0, 1) ∈ R2
in their local 2D plane.
6n−1(r, θ): polar coordinate
For point ynrθ(o, e): reference frame
x for point x
e: orientationo: origin1
local coordinate
for pattern G

4tour for pattern G

2

3

Figure 3: The local frame and reference frame for a pattern∑

Deﬁning a tour. Let ~o = ~x∈c(P ) be the centroid (the center ) of P . For each start point~x ∈ c(P ), we consider the polar coordinate system for P that has the center ~o and the zero
orientation vector ~i = ~x − ~o (See Fig. 3). Then, the tour for P w.r.t. ~x is the increasing
list Tour(P, ~x) = (~x1 (= ~x), . . . , ~xk ) ⊆ R2 of all k points in P in the increasing angle-distanceorder around ~o in the polar coordinate (Fig. 3). That is, Tour(P, ~x) is obtained by sorting thepoints ~y ∈ c(P ) ﬁrst in angle(~y − ~o, ~x − ~o) and then in dist(~y , ~o) in O(k log k) time. Clearly,
there are exactly k distinct Tour(P, ~x) depending on the choice of the starting point ~x. For
π = Tour(P, ~x) and each ~y ∈ π, let ordπ (~y ) is the order of ~y appearing in π, that is, ordπ (~y ) = i
if ~y = ~xi .
Alternative representation for geographs. Next, we deﬁne a sequential representation
for the labeled object representation of geograph P in Sec. 2.2 as follows. For π = Tour(P, ~x),
we deﬁne the set Labπ (P ) ⊆ OL of labeled objects for P as follows:(i) First, let Labπ (P ) = ∅.
(ii) For every x ∈ VP of P , add hordπ (x), c(x), λ(x)i ∈ N × R2 × ΣV into Lab.
(iii) For every xy ∈ VP , add hordπ (x0 )ordπ (y 0 ), c(x0 )c(y 0 ), µ(xy)i ∈ N × N × ΣE into Lab. If xy
is directed, then ordπ (xy) = ordπ (x) ordπ (y) ∈ N2 . If xy is undirected, i.e., it represents{xy, yx}, then x0 y 0 is the lexcographically larger one of xy and yx ∈ N2 .
Then, the sequential encoding for P w.r.t. a tour π, denoted by eπ (P ), is the increasing listeπ (P ) = ho1 , l1 i#ho2 , l2 i# · · · #ho` , l` i of labeled objects hoi , li i separated with a special delimitor# for some ` ≥ 0. This list is obtained in O(k 2 ) time by sorting the elements of Labπ (P ) in theincreasing order w.r.t. the total order <OL over labeled objects.
3.1.1 Canonical Encoding. Now, we deﬁne the canonical encoding for P , denoted
cano e(P ), by the lexcographically ﬁrst sequential encoding of P one among all encodings of
P for possible choices of starting point ~x ∈ c(P ):cano e(P ) = min { eπ (P ) | π = Tour(P, ~x) for some ~x ∈ c(P ) }.
<lex,OL

Theorem 4 (characterization of canonical encoding) For any P, Q ∈ G of size k ≥ 0,cano e(P ) = cano e(Q) iﬀ P ≡ Q under Tgeo .
We can compute in O(k 2 log k) time.
The main purpose of cano e(P ) is for assigning
By using cano e(P ), we deﬁne the total order <cano e(P ) over the components of P as
follows: For any labeled objects ξ, ξ 0 ∈ P , we deﬁne ξ <cano e(P ) ξ 0 iﬀ ξ appears at an earlier
position than ξ 0 in cano e(P ). The tail of P is deﬁned by tail(P ) = max<cano e(P ) P , i.e.,
the last element of the canonical encoding cano e(P ) as a sequence.
7

Elimination Ordering:
1: Given an labeled object representation of geograph P ;2: i = 1; j = 1; P1 = P ;3: while Pi 6= ∅ do
4:ho, li = tail(Pi ) based on the canonical encoding cano e(Pi );5:
if L(Pi − {ho, li}) 6= L(Pi ) then χi = ho, li and i = i + 1;
6:
Pi+1 = Pi − {ho, li}; ξj = ho, li and j = j + 1;
7: end while
8: return elimseq(P ) = (ξk , . . . , ξ1 ) and critseq(P ) = (χj , . . . , χ1 );Figure 4: The procedure for computing the perfect elimination and the perfect criticalelimination sequences elimseq(P ) and critseq(P ) for a geometric graph P
3.2

Perfect elimination sequences

Before studying the enumeration or generation of each pattern, we consider the reverse processof the enumeration, the decomposition of a given geograph. Let P ∈ G be any k-geograph.
We deﬁne the sequences elimseq(P ) = (ξk , . . . , ξ1 ) ∈ OL∗ and critseq(P ) = (χj , . . . , χ1 ) =(ξσ(j) , . . . , ξσ(1) ) ∈ OL∗ by the procedure Elimination Ordering in Fig. 4. They are called theperfect elimination sequence and the perfect critical elimination sequence, resp. Note that theelimination sequence (ξk , . . . , ξ1 ) for P is not the mere reverse of cano e(P ) since the i-th
element ξi is selected based on the canonical form of the current geograph Pi not on that of
the initial graph P = Pk .
Lemma 5 For any P, Q ∈ G, P ≡ Q under Tgeo iﬀ elimseq(P ) = elimseq(Q).
In the next Sec. 3.3, we study the application of elimseq(P ) to frequent geograph mining. In Sec. 4.3, we consider critseq(P ) for maximal pattern enumeration.
3.3

Algorithm for Frequent Pattern Discovery

In Fig. 5, we show an algorithm FreqGeo for frequent geometric subgraph discovery. Startingfrom the emptygraph ∅, FreqGeo searches Fσ from smaller to larger by growing P with adding
new labeled object ξi one by one in the reverse order of the elimination sequence for P . Since{ξi }i = P holds, we know that at least FreqGeo is complete for Fσ . The key of the algorithm isthe test for the elimination ordering at Line 4 of Fig. 5. From Lemma 5, we know that distinct
elimination sequence results distinct patterns.
There are inﬁnitely many candidates for possible labeled object at Line 2 of Fig. 5. From
the next lemma, we can avoid such a blind search by focusing only on missing labeled objects
for P , which is either labeled vertex or edge ξ such that L(P ) ⊇ L(P ∪ {ξ}) 6= ∅ holds. From
Lemma 1 and Lemma 3, we have the next lemma.
Lemma 6 (missing labeled objects) Let P be a pattern with nonempty L(P ) in D. Any
missing object ξ = ho, li for P is the inverse images of some labeled vertex or labeled edge π
via T for some matching T ∈ L(P ), that is, ξ = T −1 (π) for some π ∈ D.

8

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 possible labeled object ho, li do
3:
Q = P ∪ {ho, li};4:
if ho, li 6= tail(Q) then return;5:
call Expand FG(Q, σ, D);
6: end for
Figure 5: A polynomial delay and polynomial space algorithm for the frequent geometric subgraph enumeration problem
From Lemma 6 above, we know that there are at most O(|L(P )| · ||D||) = O(n4 ) missing
objects. Thus, Line 2 can be done in polynomial time. Combining the above discussion, we
have the following theorem.
Theorem 7 (frequent geograph enumeration) The algorithm FreqGeo in Fig. 5 enumerates all σ-frequent geometric subgraphs in a given input database D ∈ G in polynomial delay
and polynomial space in the total input size n = ||D||.

4

Algorithm for Maximal Pattern Discovery

In this section, we present an eﬃcient 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

In Fig. 6, we show our algorithm MaxGeo for enumerating all σ-frequent maximal geometricpatterns in Mσ using backtracking. The key of the algorithm is a tree-like search route T =T(Mσ ) for Mσ implicitly deﬁned over Mσ . Then, Starting at the root of the search tree T, thealgorithm MaxGeo searches T jumping from a smaller maximal pattern to a larger one in thedepth-ﬁrst manner. Each jump is performed by expanding each maximal pattern in polynomial
time using a procedure called the ppc-expansion deﬁned in the following subsections. To
properly handle the geometric isomorphism among the isomorphic patterns, we introduce thecanonical encoding for geometric patterns.
4.2Intersection 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 maximal geograph G ∈ G w.r.t. ⊆ such that G ⊆ Gi forevery i = 1, 2. The next lemma states that MCGS is unique for geographs, while they are notunique for ordinary graphs.
Lemma 8 (intersection geometric subgraph G1 ∩ G2 ) There exists the unique maximallycommon geometric subgraph of two geographs G1 and G2 . It is given by the intersection geograph G1 ∩ G2 = (V12 , E12 , λ12 , µ12 , c12 ) ∈ G deﬁned below:
9

Algorithm MaxGeo: (D : input geograph, σ : minsup)
task: ﬁnding all σ-frequent maximal patterns of Mσ in D.
1: ⊥ = Clo(∅);//The bottom maximal geograph
2: Call the recursive procedure Expand MaxGeo(⊥, 0, σ, D);
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 6
4:
Q = Clo(P ∪ { ξ });//Cond.(i) of Def.7
5:
if ( ξ ≤cano e(Q) π ) then return;//Cond.(ii) of Def.7
6:
if ( (∃τ ∈ Q − P ) τ <cano e(Q) ξ ) then return;//Cond.(iii) of Def.7
7:
call Expand MaxGeo(Q, ξ, σ, D);//Recursive call for children
8: endfor
Figure 6: A polynomial delay and polynomial space algorithm MaxGeo for the maximal geometric subgraph enumeration problem• V12 = {1, . . . , k} for some k ≥ 0.
• For every ~x ∈ R2 , ~x ∈ V12 iﬀ ~x ∈ c(V1 ) ∩ c(V2 ) and λ1 (~x) = λ2 (~x).
• For every ~x~y ∈ R2 × R2 , ~x ∈ E12 iﬀ c(E1 ) ∩ c(E2 ) and µ1 (~x~y ) = µ2 (~x~y ).
where Pi = (Vi , Ei , λi , µi , ci ) for i = 1, 2. Furthermore, G1 ∩ G2 is computable in O(||G1 || +||G2 ||) time, where ||Gi || = |Vi | + |Ei |.
Proof: By the construction, V12 and E12 are the largest sets satisfying the above conditions.
It follows from this that that G1 ∩ G2 is the unique MCGS for both G1 and G2 .
2
The intersection operation ∩ is reﬂexive, commutative, and associative over G. For a set
G = {G1 , . . . , Gm } of geographs, we deﬁne ∩G = G1 ∩ G2 ∩ · · · ∩ Gm . We can see that thesize and the computation time of ∩G are bounded by O(||G||). Some literatures [13] give theintersection of labeled graphs or ﬁrst-order models based on the cross product of two structures.
However, their iterative applications causes exponentially large intersection unlike ∩G above.
Gariiga et al.[9] discuss related issues.
Now, we deﬁne the closure operation for G.
Deﬁnition 5 (closure operator for geographs) Let P ∈ G be geograph of size ≥ 2. Then,the closure of P in D is deﬁne by the geograph Clo(P ):Clo(P ) =∩{ T −1 (D) | T ∈ L(P ) }.

Theorem 9 (correctness of the closure operation) Let P be a geograph of size ≥ 2 andD be an input database. Then, Clo(P ) is the unique, maximal geograph w.r.t. v satifying
L(Clo(P )) = L(P ).

10

Proof: We give a sketch of the proof. Let T ∈ Tgeo be any geometric tansformation. Then,
we can see that P matches D via T iﬀ P is a direct geometric subgraph (substructure) of theinverse image of D via T , i.e., P ⊆ T −1 (D). Thus, taking the intersection of the inverse image
T −1 (D) for all matching T of P , we obtain the unique maximal subgraph having L(P ).
2
Lemma 10 For any geographs P, Q ∈ G, the following properties hold:(i) P ⊆ Clo(P ). (ii) L(Clo(P )) = L(P ). (iii) Clo(P ) = Clo(Clo(P )).
(iv) P ⊆ Q iﬀ L(P ) ⊇ L(Q) for any maximal P, Q ∈ M.
(v) Clo(P ) is the unique, smallest maximal point set containing P .
(vi) For the empty graph ∅, ⊥ = Clo(∅) is the smallest element of M.
Theorem 11 (characterization of maximal geographs) Let D be an input geograph andP ∈ G be any geograph. Then, P is maximal in D iﬀ Clo(P ) = P .
4.3

Deﬁning the tree-shaped search route

In this subsection, we deﬁne a tree-like search route T = (Mσ , P, ⊥) for the depth-ﬁrst searchof all maximal geographs based on a so-called parent function. By inspecting the procedure
for elimination sequences in Fig. 4 carefully, we obtain the following deﬁnitions.
Let Q ∈ M be a maximal pattern such that Q 6= ⊥. Suppose we have the canonical encoding
cano e(Q) and the associated total ordering <cano e(Q) over the elements of Q. For any elementξ ∈ Q, deﬁne the ξ-preﬁx of Q as the pattern Q[ξ] with Q[ξ] = { π ∈ Q | π ≤cano e(Q) ξ }.
Then, the core index of Q iscore i(Q) =max≤cano e(Q){ ξ ∈ Q | L(Q[ξ]) = L(Q) }.

We can show that if Q 6= ⊥ then core i(Q) is always deﬁned. We assume that core i(⊥) = 0
for a special labeled object 0 such that 0 < ξ for any ξ ∈ OL.
Q[core i(Q)] ⊆ Q is a shortest preﬁx of Q satisfying L(Q[ξ]) = L(Q). Moreover, if weremove core i(Q) from the preﬁx Q[core i(Q)], then we have the properly shorter preﬁx, andthen the location list changed. Now, we deﬁne the parent function P that gives the predecessorof Q in terms of its perfect critical elimination sequence.
Deﬁnition 6 (parent function P) The parent of any maximal pattern Q ∈ M (Q 6= ⊥) isdeﬁned by P(Q) = Clo(Q[ξ] − {ξ}), where ξ = core i(Q) is the core index of Q.
Lemma 12 P(Q) is (i) always deﬁned, (ii) unique, (iii) is a maximal pattern in M. Moreover,P satisﬁes that (iv) P(Q) ⊂ Q, (v) | P(Q) | < | Q |, and (vi) L(P(Q)) ⊃ L(Q).
The parent P(Q) corresponds to the maximum critical object in Q in critseq(Q). Now,
we deﬁne the search graph for Mσ as a rooted directed graph T(Mσ ) = (Mσ , P, ⊥), where Mσ
is the vertex set, P is the set of reverse edges, and ⊥ is the root. Then, the unique path fromeach maximal pattern Q to ⊥ spells out critseq(Q).
Theorem 13 (reverse search property) For every σ, the search graph T(Mσ ) is a spanning
tree with the root ⊥ over all the maximal patterns in Mσ .
11

4.4

A polynomial space polynomial delay algorithm

The remaining thing is to show how we can eﬃciently traverse the search tree T(Mσ ) startingfrom the ⊥. However, this is not a straightforward task since T(Mσ ) only has the reverse
edges. To cope with this diﬃculty, we introduce the notion of the preﬁx-preserving closure
expansion by combining the rightmost expansion [6, 15, 24, 26] and the closure extension [17].
For discussions on closure expansion, see Sec. B of appendix.
Preﬁx-preserving closure extension for geographs. For a maximal pattern Q 6= ⊥ andits predecessor P(Q), we can show from the deﬁnition of P and Lemma 10 that if ξ = core i(Q)then π ∈ Q[ξ] iﬀ π ∈ Q for all π ∈ Q such that π <core i(Q) ξ, that is ξ-preﬁx other than ξitself is preserved by the application of P.
Deﬁnition 7 (ppc-expansion) Let P and Q be any patterns such that Q 6= ⊥. Supposethat P is maximal in D. Q is a preﬁx-preserving closure expansion (ppc-expansion) of P if Q
satisﬁes the following conditions (i) – (iii):(i) Q = Clo(P ∪ {ξ}) for some labeled object ξ = ho, li ∈ OL, called a key.
(ii) The key ξ satisﬁes: core i(P ) <cano e(Q) ξ.
(iii) There is no element τ ∈ Q − P such that: τ <cano e(Q) ξ.
Theorem 14 (correctness of ppc-expansion) Let P and Q be any maximal patterns suchthat Q 6= ⊥. P = P(Q) holds iﬀ Q = Clo(P ∪ {ξ}) is a ppc-expansion of P with some labeled
object ξ ∈ OL. In this case, ξ = core i(Q) always holds. Furthermore, if two ppc-extension
have mutually distinct keys then the resulting ppc-extensions are also mutually distinct.
The correctness and the time and space complexity. Based on Theorem 14, we canshow the correctness and the time and space complexity of our algorithm MaxGeo in Fig. 6
based on the ppc-extension. Now, we show the main theorem of this paper.
Theorem 15 (correctness and complexity of MaxGeo) Given a minimum support parameter 1 ≤ σ ≤ n and an input geograph D of length n, the algorithm MaxGeo in Fig. 6 enumerates all σ-frequent maximal geograph P of Mσ in O(mnk 2 ) = O(n5 ) delay per maximal
geograph and using O(km) space, where k is the maximum size of patterns and m = O(n2 ) is
the maxmum size of the location lists.
Overall, the algorithm MaxGeo runs in O(n5 ) time in the size of input geograph n. If the
maximum size k of maximal geographs is bounded by a (small) constant, the algorithm runsin O(mn) per pattern P and will be fast when m = |L(P )| is not large.
Corollary 16 The maximal geograph enumeration problem is solvable in polynomial delay andpolynomial space.

12

5Conclusion

In this paper, we presented a polynomial delay and polynomial space algorithm that discover
all maximal geographs in a given geometric conﬁgulations without duplicates. As future works,
we are working on implementation and experimental evaluation of the algorithm. 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 and algorithms 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
attribute trees, In Proc. ILP’05, LNAI 3625, 1–19, August 2005.
[4] H. Arimura, T. Uno, A polynomial space and polynomial delay algorithm for enumerationof maximal motifs in a sequence, In Proc. ISAAC’05, LNCS, 2005.
[5] H. Arimura, T. Uno, Eﬀcient algorithms for mining maximal ﬂexible patterns in texts andsequences, TCS-TR-A-06-20, DCS, Hokkaido Univeristy, 2006. (submitting)[6] T. Asai, K. Abe, S. Kawasoe, H. Arimura, H. Sakamoto, and S. Arikawa. Eﬃcient substructure discovery from large semi-structured data. In Proc. SDM’02, 2002.
[7] Y. Chi, R. R. Muntz, S. Nijssen, J. N. Kok, Frequent subtree mining – An overview,
Fundam. Inform., 66, 1–2, 161–198, 2005.
[8] Y. Chi, Y. Yang, Y. Xia, and R. R. Muntz, CMTreeMiner: mining both closed andmaximal frequent subtrees, In Proc. PAKDD’04, 2004.
[9] G. C. Garriga, R. Khardon, L. De Raedt, On mining closed sets in multi-relational data,
In Proc. IJCAI 2007, 804–809, 2007.
[10] C. Guerra, Vision and image processing algorithms, Algorithms and Theory of Computation Handbook, Chapter 22, 22-1–22-23, CRC Press, 1999.
[11] 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.
[12] A. Jain, Fundamentals of Digital Image Processing, Prentice-Hall, 1986.
[13] R. Khardon, Learning function-free horn expressions, Machine Learning 37(3), 241–275,
1999.
[14] M. Kuramochi, G. Karypis, Discovering frequent geometric subgraphs, In Proc. IEEE
ICDM’02, 258–265, 2002.
[15] S. Nakano, Eﬃcient generation of plane trees, Information Processing Letters, 84, 167–172,
Elsevier,2002.
[16] S. Nijssen, J. N. Kok, Eﬀcient discovery of frequent unordered trees, In Proc. MGTS’03,
2003.
13

[17] N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal, Discovering frequent closed itemsets for
association rules, In Proc. ICDT’99, 398–416, 1999.
[18] F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction, Springer,
1985.
[19] A. Termier, M.-C. Rousset, M. Sebag, Dryade: a new approach for discovering closed
frequent trees in heterogeneous tree databases, In Proc. ICMD’04, 2004.
[20] K. Tsuda, T. Kudo, Clustering graphs by weighted substructure mining, Proc. ICML
2006, 953–960, 2006.
[21] T. Uno, T. Asai, Y. Uchida, H. Arimura, An eﬃcient algorithm for enumerating closed
patterns in transaction databases, In Proc. DS’04, LNAI 3245, 16–30, 2004.
[22] J. Wang, J. Han, BIDE: Eﬃcient Mining of Frequent Closed Sequences, In Proc. IEEE
ICDE’04, 79–90, 2004.
[23] T. Washio, H. Motoda, State of the art of graph-based data mining, SIGKDD Explor., 5,
1, 59–68, 2003.
[24] X. Yan, J. Han, CloseGraph: mining closed frequent graph patterns In Proc. KDD’03,
2003.
[25] G. Yang, The complexity of mining maximal frequent itemsets and maximal frequent
patterns, In Proc. KDD’04, 344–353, 2004.
[26] M. J. Zaki, Eﬃciently mining frequent trees in a forest, In Proc. KDD’02, 71–80, 2002.
[27] M. J. Zaki, C. C. Aggarwal, XRules: an eﬀective structural classiﬁer for XML data, In
Proc. KDD’03, 316–325, 2003.

14

Note: The contents of this appendix is not included in the submission draft and can beignored.

A

Appendix: Basics in geometry

In this paper, we consider points and geometric objects on the two-dimensional Eucledean
space (or the plane, for short) E.
Throughout this paper, we ﬁx the Cartesian coordinate system for E. Each point p~ in theplane E is represented by a pair of real numbers p~ = (~p.x, p~.y) = (x, y) ∈ R2 , where x and y
are called the x- and the y-coordinates of p, resp. A point ~x is also regarded as a vector in R2
as well. Let ~ex = (1, 0) and ~ey = (0, 1) be a pair of the orthogonal unit vectors for x-axis andy-axis. Therefore, our Cartesian coordinate system is speciﬁed by the axes ψ = (~ex , ~ey ). For
1vectors ~x = (x, y) ∈ R2 , the norm or the length of ~x is deﬁned by ||~x|| = (x2 + y 2 ) 2 ≥ 0.
Let ~x1 , ~x2 ∈ R2 be two points in R2 . Then, the distance of ~x1 and ~x2 is deﬁned by ||~x1 −~x2 ||.
The line segment between ~x1 and ~x2 is denoted by ~x1~x2 . The angle of two line segments ~s1
and ~s2 is denoted by angle(~s1 , ~s2 ). We denote the scalar product of vector ~x ∈ R2 with c ∈ R
by c ~x, and the addition of two vectors ~x, ~y by ~x + ~y . The product of a 2 × 2 matrix A and a
2-vector ~x is denoted by A~x. Then, the determinant of A is written det(A). If det(A) 6= 0, A
is called non-singlar and always has its inverse A−1 .
In this paper, we consider three basic types of geometric transformations, translation M ,rotation R, and scaling S deﬁned as follows for any vector ~x ∈ R2 :( )t
M : ~x 7→ ~x + 1 ,
t2

)

(

cos θ sin θ
R : ~x 7→~x,− sin θ cos θ(s
S : ~x 7→
0

)

0
~x,
s

where (t1 , t2 ) is called a displacement, 0 ≤ θ < 2π is a rotaion angle (in clockwise), and s > 0
is a scaling factor of the transformations.
In general, any geometric transformation T can be represented as a 2D aﬃne transformation
T : ~x 7→ A~x +~t, where A is a 2×2 nonsingular matrix with det(A) 6= 0, and ~t is a 2-vector. Such
T is is one-to-one, and any transformation can be determined a set of three non-collinear points
and their images. An aﬃne transformation T ∈ Taﬃne has the following nice properties: it maps
parallel lines to parallel lines, is one-to-one and preserved the coordinates detemined by three
non-collinear points. Also, any transformation can be determined a set of three non-collinear
points and their images.

B

Discussion: Critical perfect elimination sequences andapplication to maximal pattern enumeration

Given a k-pattern Q, its perfect critical elimination sequence critseq(Q) = (χj , . . . , χ1 ),discussed in Sec. 3.2, is uniquely determined by the procedure Elimination Ordering shown in
Fig. 4. The next lemma says that the critical elimination sequence has the complete informationon the original pattern Q as expected.
Lemma 17 For any Q ∈ G, Clo(critseq(Q)) = Q.
15

ClosureMain(σ : minsup, D : input database)
1: global: P ool = ∅;2: call ClosureExpansion(⊥ = Clo(∅), σ, D);
ClosureExpansion(P, σ, D)
1: global: P ool; //A pool of already discovered patterns
2: if |L(P )| < σ then return
3: else if P 6∈ P ool then4:
output P as a frequent maximal subgraph; P ool = P ool ∪ {P };5: for each possible labeled object ho, li do
6:
Q = Clo(P ∪ {ho, li});7:
call ClosureExpansion(Q, σ, D);
8: end for
Figure 7: An output-polynomial time algorithm for enumerating all frequent-maximal
patterns without duplicates. This algorithm is neither of polynomial delay or polynomial space.
Proof: To see this, suppose we reverse the elimination process of Elimination Ordering by
the following procedure: STEP 1: Q = ∅; STEP 2: for i = j downto 1 do Q = Clo(Q ∪ {χi });STEP 3: return Q; Then, this process ﬁnally reaches the original k-pattern Q. Since we canshow that this iterative process is equivalent to Clo(critseq(Q)), the proof is completed. 2
From the above arguments, we can show that any maximal pattern Q can be generated froma properly smaller maximal pattern, say P , and some labeled object ξ by iterativelly applying
the operation Q = Clo(P ∪ {ξ}) called the closure extension [17]. In Fig. 7, we present a
recursive algorithm ClosureMain for the frequent maximal geograph enumeration problem.
Proposition 18 ClosureMain is an output-polynomial time algorithm for the frequent maximal
geograph enumeration problem, but neither a polynomial delay or polynomial space algorithm.
To avoid duplication, ClosureMain has to use explicit maximality test at Line 3 of Fig. 7 bymaintaining a possibly exponentially large pool P ool of discovered patterns. Unfortunately,
however, ClosureMain may visit an identical maximal pattern possibly exponentially manytimes in the worst case through distinct search route. Therefore, we conclude that ClosureMainis neither polynomial delay or polynomial space. In the next subsection, we will show how to
improve this approach.

16