Mining the space of graph properties.
Existing data mining algorithms on graphs look for nodes satisfying specific properties, such as specific notions of structural similarity or specific measures of link-based importance. While such analyses for predetermined properties can be effective in well-understood domains, sometimes identifying an appropriate property for analysis can be a challenge, and focusing on a single property may neglect other important aspects of the data. In this paper, we develop a foundation for mining the properties themselves. We present a theoretical framework defining the space of graph properties, a variety of mining queries enabled by the framework, techniques to handle the enormous size of the query space, and an experimental system called F-Miner that demonstrates the utility and feasibility of property mining.
Introduction
Graph analyses have been used for a variety of applications
to analyze interrelationships among entities. Some of these
analyses concern standard graph-theoretic properties, such
as the radius of the graph or embedded cliques. Other analyses
yield high-level, subjective information about the data.
For example, the web graph has been analyzed using the
PageRank [20] and HITS [16] algorithms to identify web
pages likely to be deemed "important" by the user. The
citation structure of scientific papers has been analyzed to
find papers related to a given paper [13, 15, 21].
These techniques have in common that they analyze
graph structures for predetermined properties. Although
such analyses can be very effective, coming up with a good
property for analysis is often a challenge, especially when
little is known about the data to begin with. Moreover, by
fixing specific properties for analysis, other important aspects
of the data may be ignored. Therefore the space of
properties itself should be explored.
As a concrete example, consider the simple case of looking
for intuitively "similar" nodes in the graph of Figure 1.
This work was supported by the National Science Foundation under grant
IIS-9817799 and by a Junglee Stanford Graduate Fellowship.
StudentC
Prof1
Prof2
Univ
StudentA
StudentB

Figure

1: Graph example.
One possibility is to conclude that Prof1 and Prof2 are
similar because they are both pointed-to by Univ, as in the
commonly used co-citation metric [21]. Analogously, we
may conclude that StudentB and StudentC are similar
because they are both pointed-to by Prof2. On the
other hand, we may argue that StudentA, StudentB,
and StudentC are all similar because they are pointed-to
by a node that is pointed-to by Univ, as in the recursive
SimRank metric introduced in [13]. Each or all
of these inferences may be valid, depending on the domain
and application. However, current methods require
the user to fix one measure of similarity (e.g., co-citation
or SimRank) and query for nodes found to be similar under
this measure. Ideally, we would like to query simply
for "similar" nodes and get as a result the sets {Prof1,
Prof2}, {StudentB, StudentC}, and {StudentA,
StudentB, StudentC} along with explanations for why
they are similar. This functionality is not supported by any
current system we know of. It is supported by F-Miner, an
implementation of the framework to be presented.
in this paper, we develop a framework for mining "in-
teresting" or "important" graph properties. Essentially, we
treat the space of properties as a domain and perform data
mining on this domain. Our goal is to develop an appropriate
analysis for mining the space of properties, just as
analyses have been developed for mining the graph data
itself. An obvious challenge is in handling the enormous
size of the space of properties, in which even the simplest
data mining operations seem hopelessly infeasible. We develop
techniques that allow computational resources to be
focused on only the most important properties, allowing us
Data Sources
Graph G
(other sources
from which
predicates
can be derived)
p(a, b), q(a, b),
r(a,b), etc.
Extents
Query Types
Predicates
Similarity
Frequent itemsets
Frequent
substructures
Association rules
Explanations
(other queries)
Property Mining Framework

Figure

2: A logical diagram of the property mining framework, as seen by the user.
to implement a practical mining system based on the frame-work

The main contributions of this paper are:
. A theoretical framework that defines the space of
graph properties to be queried.
. Several specific data mining query types enabled by
this framework, offering new capabilities not supported
by existing systems.
. Techniques for dramatically reducing the computational
resources required to answer queries within the
framework.
. A simple and intuitive metric for calculating the "im-
portance" of properties.
. The F-Miner experimental system, an implementation
of the framework presented, demonstrating its utility
and feasibility.
2 Framework for Property Mining
Before we can pose queries on the space of graph proper-
ties, we first have to define precisely what this space is.
. We begin with a labeled directed graph representing
the objects and relationships in the domain we want
to mine. Each edge represents a basic relationship between
two objects.
. We encode properties as formulas in the syntax and
semantics of Datalog [23]. Each property (formula)
is composed of the basic relationships (predicates) in
the domain.
. We consider the set F of all formulas and their extents,
the objects which satisfy the formula. Queries on the
space of properties can be stated as queries on F.
A logical diagram of the framework, as seen by the user, is
shown in Figure 2. The property mining framework itself is
enclosed in the dashed box. The framework enables querying
on properties of the input data (in our case a graph),
from which a set of predicates representing basic relationships
are derived. It is possible to derive predicates from
sources other than graphs, such as the less-than relationship
in a numeric data set, but for concreteness we limit ourselves
in this paper to discussing predicates corresponding
to graph edges. The predicates form the basis of formulas,
and the user's queries posed are on the set of all formulas
and their extents F. Of course, F is only an abstraction
provided to the user; in most cases F would never be materialized
by an implementation. We define F formally in the
next section.
2.1 The Query Space
E) be a labeled directed graph, where E #
for an arbitrary set L of strings serving as edge
labels. For simplicity, we do not consider edge weights,
although they can be added to the framework with slight
modification. The fundamental relationships encoded in
the edges are building blocks for the properties we will
consider. in many domains there is an obvious canonical
representation of the data as a graph, although in some domains
the representation may require some consideration.
As an example, consider the data shown in Figure 3, which
is a small fragment of a survey of members of the Stanford
Database Group. The obvious representation of the data
as a labeled graph is also shown in the figure. Many data
types can readily be modeled as a graph, including data in
relational and XML format.
The next step is to represent properties of the domain
as formulas. We use formulas in the language of Datalog
[23], although arbitrary logic formulas, say of first order
logic, are also possible. Clearly, the more powerful the
logic, the greater the semantic and computational complexity
of the system. Datalog has expressive power far beyond
Home
India
Digital Libraries
Faculty
PhD Student
Thai
Chinese
Indian
Food
Research
Food
Food
Advisor
Sriram
Hector
Position
Home
Position
Food

Figure

3: Sample data and its graph representation.
what we can hope to support in practice. As we shall see,
even the very restricted subset of Datalog that we use allows
functionality well beyond what existing systems can
support. We will define the syntax and semantics of our
formula language as we go along.
The constants (or objects) of the logic are the nodes in
G (i.e., objects of the domain), while predicates correspond
to edges (i.e., relationships of the domain). We consider
of the form:
L, A is the head variable, and
each # i , # i is either a variable or a constant (object). We
use capital letters to denote variables, lowercase letters to
denote constants, and Greek letters to denote either. Each
predicate p(#) corresponds to the existence of an edge
with label p between its two arguments: predicate p(u, v),
for u, v # V , is true if and only if the edge #u, v, p#
exists in G. in the example of Figure 3, the predicate
Food(Sriram, Indian) is true. A formula f is satisfied
by the satisfying assignment a, a function that maps variables
to constants, if all the predicates in f are true when
all variables X in f have been replaced by a(X). in a for-
mula, at least one of the arguments of each predicate must
be a variable, for otherwise the predicate would have a constant
truth value. Two formulas that are identical except
for variables names and predicate ordering are considered
identical.
The most important aspect of a formula f is its extent,
denoted E(f). It is the set of all objects v for which there
exists a satisfying assignment a such that
call that A is always the head variable). Intuitively, each
formula specifies a "property" of the domain, and the extent
of the formula is the set of objects which satisfy the
property. For example, the formula
encodes the property "being the advisor of someone who
likes Chinese food", and its extent is {Hector}.
We define the set F = {(f, E(f)) | f is a formula} of all
formulas and their extents as the space in the context of
which we pose our queries. A fragment of F is shown in

Figure

2 as a relation. Of course, F is infinite, and is not
meant to be computed. It serves only as the logical relation
over which queries are posed.
2.2 Sample Query Types
There are many interesting data mining operations one can
perform over F, and many common notions in data mining,
such as the frequent itemsets computation [3], have analogues
in the space of formulas. Here are some examples:
. Object similarity. Two or more objects can be considered
similar if they satisfy "many" formulas in
common. in contrast to previous approaches, now
similarity can be computed based on multiple aspects
(as in the example of Section 1), with the system automatically
identifying the more "important" aspects
(Section 4).
Furthermore, similarity can be explained. Rather than
simply returning a score, the formula(s) which contributed
to the score can be returned as an explanation
of the results.
Finally, "find more" queries can be supported. Given a
set of objects U presumed to be similar in some ways,
we can query for objects similar to objects in U in the
same ways that objects in U are similar to one another.
The objects returned are those which occur frequently
in the formulas satisfied by members of U .
These features are supported in the F-Miner system
(Section 5).
. Frequent itemsets. We can run a frequent itemsets
computation on the set of all extents, identifying those
sets U # V for which U is a subset of "many" extents.
Each subset U represents a group of objects having "a
lot" in common. For example, in the survey data to be
discussed in Section 5, the set of all professors may be
a frequent itemset because they all have advisees and
have written many papers.
. Frequent substructures. Many graph structures correspond
to formulas, and vice versa. We can find frequent
substructures in the graph by finding formulas
which have large extents. For example, the formula
corresponds to a path of length 3 (with edge labels e).
If the extent of f is large, the graph contains many
paths of length 3.
. Association rules. We can look for association rules
of the form f =# g, where f and g are formulas
whose extents have "a lot" of overlap. The rule says
that objects which satisfy f also satisfy g, or at least
with a high probability.
. Explanations. Given a set of objects U , we can "ex-
plain" what the objects in U have in common with
one another by considering the formulas they satisfy
in common. This functionality is demonstrated in F-
Miner (Section 5).
These are but some examples of the kinds of queries that
can be posed on F. We use the examples as motivation
for some of the techniques we develop, but it is important
to remember that these queries are end-applications of the
framework, which itself consists only of the logical relation
F. Other queries are possible in the framework and some
may be more application-specific. in contrast to traditional
data mining, the queries here generally focus on the properties
themselves, rather than the objects which satisfy the
properties.
As a reminder, it is not possible (nor necessary) to materialize
F in order to query it. Rather, once a specific
application has been determined (e.g., finding similar ob-
jects), we can solve the end-to-end problem without explicitly
constructing F.
2.3 Challenges
There are two major technical challenges to answering
queries within our framework. The first is in dealing with
the enormous size of the query space. We develop techniques
to handle this problem in Section 3. The second
challenge is in determining the "importance" of formulas.
This is a major component of property mining: just as we
look for important (interesting) objects in traditional data
mining, here we look for important properties. Moreover,
identifying important formulas is intertwined with reducing
the space considered, since we would like as much as
possible to restrict ourselves to considering only the most
important formulas. Computing importance of formulas is
discussed in Section 4.
Building Blocks Approach
The query space F is infinite, and it is impossible to consider
all formulas in F. Instead, we want to focus as much
FOXSports.com
MLB.com
ESPN.comm

Figure

4: Graph example.
of our computational resources as possible on the most important
formulas. This poses a dilemma, since one of the
goals of our mining is to identify these important formulas!
At a high level, our solution is to construct formulas
from basic building blocks called pseudopredicates. We
analyze these building blocks for importance instead of analyzing
the actual formulas. This allows us to determine the
importance of the formulas that can be constructed from the
building blocks, so that only the most important formulas
are ever created. Hence much of the mining actually takes
place in the space of pseudopredicates. Our approach can
be broken into 3 steps:
1. A set of pseudopredicates is computed to serve as basic
building blocks for formulas.
2. Importance scores are computed for the pseudopredi-
cates, identifying those from which important formulas
can be constructed.
3. Important formulas are constructed from the pseudo-
predicates.
in this section we present steps (1) and (3). Step (2) is
presented in Section 4.
3.1 Example
We motivate our approach using an example. Consider the
top half of the structure shown in Figure 4, a hypothetical
fragment of the web graph. The web pages u 1 , . , u k all
point to FOXSports.com, so they satisfy the formula
where e is taken to be the label of every edge in the (un-
labeled) graph. FOXSports.com in turn points to base-
ball's MLB.com, so FOXSports.com satisfies the formul

Finally,
It seems redundant to record this fact, however, since it follows
immediately from the facts that u i , for all 1 # i # k,
satisfies formula (1) and that FOXSports.com satisfies
formula (2). More generally, for any formula g satisfied by
FOXSports.com, each u i points to a node that satisfies
g. That is, u i satisfies the formula
where g(B) is g with head variable A replaced by a variable
not appearing already in g. 1
Now we consider the entire Figure 4, where v 1 , . , v m
all point to the sports site ESPN.com. Since ESPN.com
points to MLB.com, u 1 , . , u k and v 1 , . , v m are all related
by their common satisfaction of formula (3), a consequence
of the fact that the u i 's and v j 's all point to either
FOXSports.com or ESPN.com. We record this by saying
that u i 's and v j 's satisfy the pseudoformula
3.2 Pseudopredicates and Pseudoformulas
A pseudopredicate is a predicate that may have as an
argument a nonempty set of objects, as well as vari-
ables. It is a generalization of a regular predicate, which
can be thought of as the special case when the only
set-arguments of a pseudopredicate are singleton sets.
We have already seen one example of a pseudopredicate
in Section 3.1, e(A, {FOXSports.com,ESPN.com}),
which represents the property of pointing to either
FOXSports.com or ESPN.com. We define a pseudo-
formula as a formula consisting of pseudopredicates, and
define the extent of a pseudoformula f as the set of objects
v for which there exists a satisfying assignment a for f such
that assigns each set-argument to one of
its members. For example, the extent of the pseudoformula
is
Note that the set of formulas can be thought of as a sub-set
of the set of pseudoformulas, since we can replace each
constant argument v by {v} to get a pseudoformula having
the same semantics. Conversely, some pseudoformulas can
be converted to formulas: if all set-arguments of a pseudo-
formula f are either singleton sets or the set of all objects
has the same semantics as the formula f # which
is a copy of f except with singleton objects replaced by
their sole members, and each set-argument V replaced by
a dangling variable not appearing anywhere else in f # .
3.3 Chaining Pseudoformulas
We take the set of basic building blocks to be (P, E(P)), the
set of all head pseudopredicates P and their extents E(P).
1 Technically, we do not allow formulas within formulas, so g's predicates
must be substituted explicitly into h with appropriate variable renaming

A head pseudopredicate is a pseudopredicate whose two
arguments are the head variable A and a set-argument S #
V . These pseudopredicates can be treated as 1-predicate
pseudoformulas. in the coming sections, we will talk about
extents of head pseudopredicates as though they were 1-
predicate pseudoformulas, and omit the "head" qualification
when the meaning is clear.
From this base set of head pseudopredicates we can
compose a large class of more complex pseudoformulas
and thus formulas, which as noted before are a subset of
pseudoformulas. The two composition steps are conjoining
and chaining.
Conjoining two formulas f and g creates a new formula
h whose predicates are a conjunction of the predicates in f
and g, with appropriate renaming of non-head variables to
avoid conflict. For example:
Chaining is a formalization of the example in Section
3.1 of deriving formula h from f and g. Suppose we
have a 1-predicate pseudoformula f(A) :- p(A, S). Then
for any pseudoformula g whose extent is a superset of S,
any object satisfying f also satisfies the pseudoformula
We say that h is the result of
chaining f and g. in the general case, if S appears as
a set-argument in f , and S # E(g i ) for some formulas
then we can derive a new formula h by chaining
f with g 1 , . , g k on S, as follows:
. Let h be f with S replaced by a new variable X not
appearing in f .
. For append to h all predicates of g i , with
non-head variables in g i renamed so as not to conflict
with those already appearing in h, and with head variable
A in g i renamed to X .
Note that the resulting h has an extent E(h) that is a super-set
of E(f). Moreover, if
A key concept here is that an object-set S # V , when
it occurs as a set-argument in a pseudoformula, represents
the set of pseudoformulas satisfied by all members of S.
Pseudoformulas (and formulas) are thus partitioned into
classes according to their extents. in computation, we deal
with the set of object-sets (seen as both extents and set-
arguments), with each object-set representing a class of for-
mulas. There are 2 n such sets, which although large is at
least finite.
Through chaining and conjoining, the base set of pseu-
dopredicates P can be used to construct more complex
pseudoformulas and formulas. For a formula f , let G(f)
be the undirected, unlabeled graph corresponding to f :
. The nodes of G are the variables and constants appearing
in f , except that all instances of a constant in f are
treated as different nodes.
. For every predicate p(#) in f there is a corresponding
edge between # and # in G, so that p 1
(A, X) and
(A, X) would yield two edges between A and X .
Then we can state the following theorem about the formulas
that can be constructed.
Theorem. If G(f) is a tree, then f can be constructed by
chaining and conjoining pseudoformulas, starting from P.
The theorem says that we can construct all formulas corresponding
to tree structures. in general, formulas that are
not tree-structured cannot be constructed; however, it is important
to note that this does not mean the input graph must
be tree-structured. A stronger version of this theorem is
stated and proven in Section 3.4.
3.4 Computing a Working Subset of P
The set P has size O(2 n
|L|), which, although much smaller
than that of the set of all formulas (which is infinite), is
still enormous. in practice, we have to restrict ourselves
to using only a subset of P, at the cost of restricting the
set of formulas that can be constructed. Ideally, we would
use only the most important pseudopredicates as building
blocks, from which the most important formulas can be
constructed. But we cannot tell which pseudopredicates are
important in advance, so we start with an initial set of pseu-
dopredicates P 1 as seed, then iteratively expand (or refine)
the set of pseudopredicates included.
We maintain a series of head pseudopredicates and their
extents Each P i is the set of pseudo-
predicates created on iteration i, and E(P i ) is the set of their
extents. We compute
each iteration i + 1. Their successive unions:
are the working (trimmed) sets of basic building blocks.
We take P 1 to be the set of all head pseudopredicates
whose set-argument is a singleton set or the set of all ob-
jects. On each iteration, we consider the extents of the
pseudopredicates already created, as well as the extents' in-
tersections, and create new pseudopredicates having these
sets as set-arguments. More precisely, given that we have
we perform the following steps on iteration
. Compute I i , the intersection-closure of E(P i ) (i.e., the
smallest set such that E(P i
. Compute
Each successive iteration considers formulas corresponding
to trees one level deeper. This idea is formalized by the
following theorem.
Theorem. A formula f whose corresponding graph G(f)
is a tree of depth at most k from A can be constructed by
chaining and conjoining pseudoformulas starting from P k .
Note that the sole formula with a G(f) depth of 0 is the
trivial formula f(A) :- p(A, A), which we do not consider.
Proof. The proof is by induction on the depth of G(f). As
the base case, the set of formulas with depth 1 is exactly
the base set Now assume that the theorem is true
for some k # 1, and suppose that G(f) is a tree of depth
starting from A. Each child of A is the root of a sub-tree
having depth at most k. Consider those subtrees T i
that have depth at least 1 (i.e., not constants and dangling
variables). By the inductive hypothesis, the formula g i corresponding
to each subtree T i can be constructed from
after we rename the root variable of each subtree (and other
instances in the subtree) to A (note that A cannot appear in
the subtree already since G(f) is acyclic).
We want to show that there is a pseudopredicate
First let us
assume that g i has only one head predicate, p(A, #) (anal-
ogous arguments can be made for p(#, A)). There are two
cases:
1. # is a constant. in this case, all other predicates of g i ,
if any, are irrelevant, and E(p(A, S #
2. # is a variable. Then p(A, #) was added to g i through
chaining, of a predicate p(A, S # P k and g # i
, for
some formulas g # 1 , . ,
. Since g i is the product of
chaining
E(g
in either case E(p(A, S # E(g i ), and E(p(A, S #
E(P k ). Now if g i has more than one head predicate, we
can apply the same argument as above on each of its head
predicates to derive a corresponding p(A, S #
for each of
its head predicates. Since I k is the intersection-closure of
E(P k ), the set S
predicates with set-argument S i are
in P k+1 and thus P k+1 .
We are finally ready to construct f from P i+1 . Let f # be
the formula which has, for each head predicate p(A, #) in f
(and analogously for predicates p(#, A)), a head predicate
of the form:
. p(A, #) if # is a constant or dangling variable
. is a variable which is the root of some
corresponding to formula g i
can be constructed by conjoining predicates in
f is the chain of f # and g 1 , . , g k on set-
arguments
It follows immediately from the theorem that in the limit
corresponding to tree structures
can be constructed from P# (and hence P, a superset
of P# ), from which follows the weaker version of the the-
orem, as stated in Section 3.3.
The larger the k, the more formulas can be constructed,
at the cost of using more computational resources. in the
F-Miner system, we found that accounts for a wide
range of interesting formulas while having very manageable
resource requirements (Section 5).
There are many ways the set P k can be further pruned
or tailored for the class of formulas suitable for a specific
application. First, instead of taking I to be the intersection-
closure of E(P i ) in the iterative step 1, we can simply
take I to be E(P i ), or take I to be the (first-level) intersection
of elements of E(P i ). Thus conjunctions of pseudofor-
mulas are only formed when their extents are equal. Sec-
ond, those pseudopredicates in P k and those sets in E(P k )
deemed unimportant (Section 4) can be pruned away after
each iteration. By keeping only a fixed number of the most
important pseudopredicates and their extents, we can limit
the growth of (P k , E(P k )), while still allowing important
formulas corresponding to deep tree structures to be considered

Computing Importance
in Section 3 we established a set of head pseudopredicates
and their extents (P, E(P)) as building blocks for formu-
las. Formulas can be constructed from P through conjoining
and chaining. Because P is usually extremely large, we
showed how to iteratively compute a manageable subset P k
of P.
The next step is to construct important formulas from
We first analyze (P k , E(P k )) as to the importance of
the formulas that can be constructed. The problem of computing
importance on formulas becomes that of computing
importance on sets (representing classes of formulas satisfied
by these sets) and pseudopredicates. Just as in traditional
data mining we look for interesting objects satisfying
some predefined property, we now mine the space of properties
for interesting properties satisfying some predefined
notion. 2 Accordingly, the development of a good measure
2 Now, we might mine the space of notions-on-properties to identify
the important notions, but obviously this just pushes the same problem up
a level. Instead, we settle for mining the space of properties using some
predefined notions. Note this does not mean that we are back to where we
started, since we can now mine for (first-level) properties instead of just
atomic objects. Extension to mining higher-level properties (i.e., properties
of properties) is a possible direction for future work.
of importance for properties is fairly ad-hoc, although we
try as much as possible to develop upon known principles.
The ranking techniques presented in this section are largely
based on empirical experimentation. We present these techniques
only as a concrete, viable example. in practice, the
computation of importance should be specialized to the application

4.1 Ranking Head Pseudopredicates and Sets
We start with some fundamental notions of importance for
head pseudopredicates (simply "predicates" in the rest of
this section), and then let the analysis compute importance
based on these notions. We borrow a technique from the
field of web search. The PageRank [20] and HITS [16]
algorithms have been used to analyze web pages for importance
to aid in web search. The idea behind PageRank is
that a web page is important if it is pointed-to by important
web pages. Similarly, the HITS algorithm identifies good
hub pages and good authority pages recursively: good hubs
are those which point to good authorities, and good authorities
are those pointed-to by good hubs. Good authorities
are regarded as important pages. Common to these two algorithms
is their recursive, mutually-reinforcing definition
of importance, and the iterative computation method (cor-
responding to an eigenvector computation).
in the same spirit, we develop an iterative algorithm for
ranking the importance of sets and pseudopredicates. And
analogous to the definition of hubs and authorities in HITS,
we say that:
. A pseudopredicate is important if its set-argument is
important.
. A set is important if it satisfies important pseudopred-
icates.
Thus, the basic notions from which we derive importance
are satisfaction of pseudopredicates (for sets), and importance
of the set-argument (for pseudopredicates).
To compute importance scores, this intuition must be
formalized mathematically. We take importance scores to
be in the interval [0, 1], with importance scores for all pseu-
dopredicates summing to 1, and importance scores for all
extents of pseudopredicates summing to 1. For S # E(P k ),
we define P k (S) to be the set of predicates satisfied by S:
As a basis, we start with the core equations
for predicates, which says that the importance I(p) of a
predicate p is the importance of its set-argument arg(p),
and
which says that the importance of a set S has two compo-
nents: (1) a small inherent importance c
(in our experiments
we used and (2) the sum of the importances
of the predicates p satisfied by S. This "recursive"
equation is analogous to that used for PageRank [20].
These two core equations provide a good starting point
in capturing the recursive intuition presented, but more specific
details of the analysis should be incorporated.
First, instead of summing over the set of all predicates
satisfied by S, we should sum only over those
that are not subsumed by another predicate satisfied by
S. We say that a pseudopredicate p(A, S) subsumes another
pseudopredicate , in which case
E(p(A, Intuitively, p(A, S) specifies
a property more specific than that specified by p(A, S # ).
For example, in Figure 4, if we already know that v 1 satisfies
e(A, ESPN.com), it is pointless to also record that v 1
satisfies e(A, {FOXSports.com , ESPN.com}).
Another aspect that can be improved is when S # E(p),
but S is only a small fraction of the objects in E(p). Then
I(p)'s contribution to I(S) should be weighed lower than
to I(S # ), where E(p). For example, in Figure 4, we
have
so e(A, ESPN.com)'s contribution to the importance of a
set should be smaller than to that of S
Thus we consider the term
which assigns weights according to the relative sizes of
S and E(p), as compared with other sets S # satisfying p.
For both data sets in our experiments we used w 1 (x,
y
3 , which we found to work well empirically.
We may also attribute more importance to those sets that
satisfy many pseudopredicates independently of the importance
of the pseudopredicates. Let
be the number of predicates satisfied by S, weighted by a
function w 2 (x). in our experiments, we found w 2
x10 to work well empirically.
The equations we used in our experiments for scoring
predicates and sets are:
|E|
#(S, p)I(p) (5)
As with the HITS equations, equations (4) and (5) can
be solved by iterating to a fixed-point. On each itera-
tion, the scores are normalized so that # p
1. For equation (5), the set P k (S) must be
precomputed for each S, which in general is an expensive
operation. One way to alleviate the problem is to set
when it is below a certain threshold t,
in which case we need not check whether S # E(p) at all.
in our experiments, we used sped up the
computation with no noticeable effect on quality of results.
Note that an appropriate choice of equations is in general
dependent on the data set and query type. However,
we have found the above equations to work well on the two
data sets and two query types we tried. Also note that inherent
importances can be assigned nonuniformly to bias the
results when there are sets we know apriori to be impor-
tant. This is analogous to biasing web pages nonuniformly
in PageRank to enable a personalized web search [9, 14].
4.2 Selective Construction of Pseudopredicates
The importance rankings for the base set of pseudopredi-
cates and their extents (P k , E(P k )) tell us the importance
of the formulas that can be constructed. Using the chaining
procedure as described in Section 3.3, it is straightforward
to construct formulas from P k . However, many queries,
such as those in Section 2.2, are computed based on the
importance scores of the extents, while the actual formulas
serve only as an explanation to the user. Thus an exhaustive
construction of all constructable formulas is usually not
necessary (nor feasible). Instead, we want to construct only
the most appropriate formulas, taking into account not only
the computed importance of the formulas but such human
aspects as the formulas' brevity, comprehensibility, and va-
riety. Here we present the chaining operation from Section
3.3 as a procedure that allows us to take these factors into
account.
We define the function chain(f), which takes a pseud-
oformula f as argument and returns the result f # of chaining
f with some pseudopredicates. The result is a pseudo-
formula whose graph G(f # ) is one level deeper than f :
. Start off with f # set equal to f .
. For each pseudopredicate (not just head pseudopredi-
cates) p in f # having a non-singleton set-argument:
1. Let S be the set-argument of p, and let P (S) #
be a set of pseudopredicates satisfied by
S.
2. Replace S in p by a new variable X not appearing
anywhere in f # .
3. For each p # P (S), append p # to f # with head
variable A of p # replaced by X .
. Return f # .
The function P (S) can be adjusted, based on the computed
importance of the pseudopredicates (and human factors,
etc.), to suit the specific query types and end application.
As a general rule, it should consist of the m most important
pseudopredicates satisfied by S. Most of the variability
is in choosing m properly so as to produce informative
formulas while minimizing complexity for the sake of user
intelligibility. Specific rules for choosing m in the F-Miner
system are discussed in Section 5.
Each call to chain results in a more complex formula.
in theory, we could chain some formulas indefinitely,
since the same set may be chained over and over again in
a cycle. in practice, users will want formulas to be simple,
so a maximum-depth or cycle-detection stopping criterion
will be used anyway.
As an example, consider the pseudoformula
which represents the property of "being the home of Glen
or Beverly". If Glen and Beverly both like either
Chinese or Indian food, then the formula may be expanded
(through one call to chain) to
which represents the property of "being the home of someone
who likes Chinese or Indian food". Finally, this
formula may be expanded to
if Jennifer likes Chinese and Indian food.
5 The F-Miner Experimental System
Based on the framework and algorithms presented in the
previous sections, we have implemented an experimental
system, F-Miner, that supports some of the data mining
queries discussed in Section 2.2. Specifically, F-Miner
supports the following two query types on arbitrary input
graphs:
. Similarity. Given a set of input objects, return a
ranked list of objects similar to members of that set
in the same ways the objects in the set are similar to
one another. For example, given two professors in the
research group data described below, F-Miner returns
a third professor.
. Explanation. Given a set of input objects, return formulas
"explaining" what the objects have in common.
This function can be used to explain the answers returned
in the similarity queries.
For efficiency, the user may assign types to each object
to minimize redundant comparisons by the system. For ex-
ample, a university would never be considered as an argument
to an Advisor predicate between two people. Types
4.72: MS Student)
2.08:
Most similar objects:
[input]: 79.5
Jing: 20.2
Glen: 13.8
Chris: 13.5
Beverly: 13.4
Brian: 10.1

Figure

5: Results for query "Steve".
help to speed up the implementation without having any effect
on semantics.
The exact parameters used in F-Miner are given in Section
5.3.
5.1 First Data Set: Database Group Survey
We ran F-Miner on two data sets. The first is based on
a survey of Stanford University's Database Group, along
with publication data from the Database Group's publication
server [1]. The data is modeled as a graph where nodes
represent all entities that participate in relationships, such
as people, food types, and publications. The edges represent
relationships, including those that denote food pref-
erences, advisors, undergraduate institution, home coun-
try, research interests, and authorship for publications. The
graph consists of 1725 nodes and 3552 edges.
When the system is first run, the set of basic building
blocks precomputed as described in Section
3.4. A prompt is then presented to the user where a list of
objects can be entered as a query for both similarity and
explanation. The precomputation takes less than a minute,
and each query returns in milliseconds.
We begin with a simple single-object query for
"Steve". The results of the query are shown in Figure 5.
Scores in the query results for this data set have been scaled
legibility. The top portion of the output shows
the most important formulas (as determined by the system)
satisfied by the input. We find that Steve is a Masters stu-
dent, and that his advisor is Jennifer. We chose to list
these as separate formulas, although they can be printed as
a single conjunctive formula instead. Among the properties
satisfied by Steve, including the foods he likes and where
he went as an undergrad, these two are found to be the
most important by the algorithm. The importance scores
are listed next to the formulas. The bottom portion of the
output lists the 5 objects most similar to Steve, along with
their similarity scores. The similarity score s(x) for an object
x is the weighted sum of the importance scores of the
extents satisfied by both x and Steve:
where w 1 is the same weighting function used in Section
7.72:
Most similar objects:
[input]: 107
John: 72.4
Brian: 66.2
Jing: 65.9
Glen:
Wang: 59.9

Figure

3.89:
1.67:
Most similar objects:
[input]: 34.0
Chris: 32.0
Taher: 29.1
John: 26.0
Wang: 26.0
Calvin: 25.4

Figure

7: Results for "Glen, Qi".
4.1. The self-similarity s(Steve) is given as a reference
(listed as [input]) for comparison. in effect, the program
finds those people who have "a lot" in common with
Steve, taking into account the numerous properties they
may share. The top match is Jing, whom we know to be
the only other Masters student in the group. The following
are two of Jennifer's other students. The next match,
Beverly, is neither a Masters student nor Jennifer's
student.
To find out why Beverly is listed, we can type in
"Steve, Beverly" as a new query. The results are
shown in Figure 6. We find that Beverly and Steve
both went to Stanford as undergrads and are from California
originally. Note that these attributes were not regarded
by the program to be Steve's most important attributes,
but they are the most important of those attributes he shares
with Beverly. Appropriately, the top matches returned
are other students who went to Stanford as undergrads, followed
by other students from California.
The next example illustrates more complex formulas for
the query "Glen, Qi". The results are in Figure 7. Comparing
the absolute magnitudes of the formula scores with
those for the query "Steve, Beverly", we see that there
is relatively little in common between Glen and Qi. The
first formula says that the two people both went to schools
that Jeff's students tend to go as undergrads. The second
formula is analogous. The two students do not share advisors
or other preferences, and these formulas are the best
connection between them.
Of course, we can also query on objects other than peo-
ple. The query results for "UC Berkeley, Stanford"
are shown in Figure 8. The formula identifies these as
148:
Most similar objects:
[input]: 543
Cal Poly: 223
IIT Madras: 217
MIT: 153
IIT Bombay: 137
University of Colorado: 137

Figure

8: Results for "UC Berkeley, Stanford".
Most similar objects:
user-2244: 21.8
user-500: 21.8
user-297: 21.7
user-1081: 21.7
user-2353: 21.7

Figure

9: Results for "user-8, user-9, user-10".
schools that tend to be attended by people from California.
This is indeed the most intuitive result that can be inferred
from the data. 3
5.2 Second Data Set: Club Nexus
To test F-Miner on a larger data set, we used data from
Nexus [2], which contains various personal information
about 2469 Stanford students. Attributes used include
the student's academic standing, major, and a list of Club
Nexus members he knows. The data is modeled in F-Miner
analogously to the Database Group survey data. The resulting
graph has 2852 nodes and 74197 edges. The precomputation
step, which needs to be done only once, takes about
3 hours, and each query at the prompt takes about 2 sec-
onds. (Note that our system has not yet been optimized
or tuned for scalability.) Sample results for the random
queries "user-8, user-9, user-10" and "user-7,
user-98, user-178" are shown in Figure 9 and Figure
10, respectively. Scores in the query results for this data set
have been scaled by
The results in Figure 9 say that the input students are
related because they are all males, they all know someone
who knows and is known by user-178, and they all know
someone who knows user-898. The results in Figure 10
say that the students are related because they are all undergraduates
and are known by a person who majors in international
relations. These kinds of connections are found by
3 Note that the Undergrad, Home, and Advisor relationships tend
to be favored over, say, Food because each person has a unique choice for
these attributes, whereas he usually has multiple food preferences. This
is an effect of the # function (Section 4.1), which causes a preference
for a particular food to be deemphasized when the person has other food
preferences.
Most similar objects:
[input]: 6.45
user-1503: 6.41
user-188: 6.41
user-1854: 6.41
user-304: 6.40
user-1735: 6.40

Figure

10: Results for "user-7, user-98,
user-178".
the system for most random groups of people.
5.3 Implementation Details
Our experiments were run on a 2.4GHz Pentium with 1GB
of RAM using Java SDK 1.4.1. The code is written entirely
in Java, unoptimized and without native methods. The core
of the F-Miner system is implemented based on the techniques
presented in the previous sections. The same parameter
settings were used for both data sets. We used
deriving the basic building blocks (P k , E(P k )),
and ranked pseudopredicates using 10 steps of the fixed-point
iteration process. in computing E(P k+1 ), we used
omitting the intersection step for speed, and
found this to have little effect on the results (conjunctions
were already accounted for).
A proper setting of m for P (S), as discussed in Section
4.2, is largely a user-interface issue. We have developed a
heuristic to determine m. Let p i be the i-th
ranked predicate in order of decreasing importance. We
take m to be the minimum of 10, the smallest i such that
cates are trivial compared to those already included), and
the smallest i such that # 1#j#i I(p j
(i.e., when at least 90% of pseudopredicates have been accounted
for). We have found this heuristic to work well in
most cases, providing the results illustrated in the previous
figures.
6 Related Work
Our framework most resembles that of inductive databases
[11], which are based on the inductive logic programming
framework [19]. in inductive databases, rules (e.g.,
association rules) about database objects are treated as first-class
objects of the database, so that queries (e.g., in SQL)
may be posed on rules as well as objects. For example, in
the MolFea [10] system for molecular databases, one can
query for "all structures (represented by formulas) occurring
as substructures in more than
While our framework also supports such queries (Section
2.2), it further develops the treatment of formulas as first-class
objects by considering the interrelationships between
formulas and objects and among formulas themselves. This
development is manifested in two key features of F-Miner:
the relationships between objects and formulas are used to
support similarity queries, and the relationships among formulas
are analyzed in the recursive computation of importance

Along similar lines, the traditional association rules of
market basket analysis are generalized in the WARMR system
[6, 7] to association rules on Prolog formulas (similar
to our Datalog formulas) evaluated on a relational database.
The goal is to find association rules of the form f =# g
where f and g are formulas. As discussed in Section 2.2,
this extension of association rule mining can be formulated
as a query type in our framework.
The traditional data mining problem of finding frequent
itemsets in market basket data [3] has also been extended to
graph structures [12, 17, 18, 24, 25]. The focus in graphs
is on finding frequent substructures, the graph equivalent
of frequent itemsets. Again, such queries are but one instance
of the query types supported in our framework, as
discussed in Section 2.2.
Other instances of property mining have been studied in
specific contexts. One is the problem of identifying "pat-
terns and relations" in the unstructured text of web pages,
e.g., [5, 22]. Patterns are essentially regular-expressions
and correspond to the formulas of this paper; relations correspond
to extents. The sets of patterns and relations are expanded
iteratively starting from a small initial set of known
relations. The process can be seen roughly as an extension
of the frequent itemsets problem in our framework:
frequent itemsets are used to discover additional frequent
itemsets.
Other graph mining algorithms to compute similarity of
nodes based on graph structure include co-citation [21] and
its generalization SimRank [13]. Again, similarity is but
one application for our framework, and advantages of the
similarity computation enabled by our framework over specific
measures of similarity were noted in Section 2.2.
A particular feature of F-Miner is the ability to relate
nodes in a graph through relationships beyond just a single
edge, as in the query of Figure 7. This feature was also exhibited
in the proximity search of [8], which finds nodes in a
graph that are nearby in terms of graph distance. However,
there is no mechanism in [8] for explaining query results,
one of the strengths of our approach. A system was presented
in [4] that, given keywords matching tuples across
different tables in a relational database, returns a tree denoting
the schema relating the matching tuples, where the
edges of the tree are foreign-key relationships. The tree
serves to explain how the tuples are related. However, these
tree structures lack the expressive power of our formulas,
and there is no ranking of explanations.
As discussed in Section 4.1, the recursive notion of importance
of pseudopredicates is analogous to the notion of
importance computed by the PageRank [20] and HITS [16]
algorithms for web pages.
The syntax and semantics of the formulas used in our
framework are borrowed from the logic-programming language
7 Conclusion
The main contributions of this paper are summarized as follows

. We presented a framework under which data mining
queries can be posed on graph properties. We showed
that many common notions in data mining have analogues
in the space of formulas that can be formulated
as query types in our framework.
. We developed techniques to deal with the enormous
size of the query space. Our basic building blocks
approach partitions properties into classes, bypassing
the prohibitive process of analyzing each property individually

. We defined a general measure of importance for properties
by treating properties as first-class objects and
applying known techniques. The measure was a vital
component of the experimental system.
. We implemented the F-Miner experimental system
supporting queries under the property mining frame-work
that are not supported by existing systems.
Our experiments to date have been with relatively small
data sets. Much work is yet to be done in algorithms,
approximations, tuning, and optimizations if we wish to
scale to the largest data sets, such as the web. Nonethe-
less, many modest-sized data sets with acceptable precomputation
and query response times pose interesting applications
for our framework already, such as the examples in
our experiments. With the proliferation of XML and other
easy means of expressing and interlinking data, we expect
in the near future to see numerous graph-structured datasets
amenable to property mining.
The intent of this paper is mainly to provide a foundation
for the mining of (graph) properties. The emphasis has
been on demonstrating the utility and feasibility of this new
kind of data mining. We have only scratched the surface in
terms of theory, algorithms, implementation, and applica-
tions; many aspects are open for further research.



--R

http://dbpubs.
http://clubnexus.
Fast algorithms for mining association rules.

Extracting patterns and relations from the World Wide Web.
Discovery of Relational Association Rules
Bart Goethals and Jan Van den Bussche.
Suresh Venkatasub- ramanian

The molecular feature miner MolFea.
A database perspective on knowledge discovery.
An apriori-based algorithm for mining frequent substructures from graph data
SimRank: A measure of structural-context similarity
Scaling personalized web search.
Bibliographic coupling between scientific papers.
Authoritative sources in a hyperlinked en- vironment
An efficient algorithm for discovering frequent subgraphs.
Surnjani Djoko Lawrence B.
Inductive logic pro- gramming: Theory and methods
The PageRank citation ranking: Bringing order to the Web.

Mining the web for re- lations
Principles of Database and Knowledge-Base Systems

Efficiently mining trees in a forest.
--TR
Principles of database and knowledge-base systems, Vol. I
A database perspective on knowledge discovery
Authoritative sources in a hyperlinked environment
Mining the Web for relations
Topic-sensitive PageRank
An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data
Proximity Search in Databases
Fast Algorithms for Mining Association Rules in Large Databases
Relational Association Rules
Efficiently mining frequent trees in a forest
SimRank
Scaling personalized web search
gSpan
Keyword Searching and Browsing in Databases using BANKS

--CTR
Bart Goethals , Eveline Hoekx , Jan Van den Bussche, Mining tree queries in a graph, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
Jian Pei , Daxin Jiang , Aidong Zhang, On mining cross-graph quasi-cliques, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
data mining;graph mining