Data Mining:

Concepts and Techniques

Chapter 9

Graph mining: Part I

Graph Pattern Mining

Jiawei Han and Micheline Kamber Department of Computer Science University of Illinois at Urbana-Champaign www.cs.uiuc.edu/~hanj
2006 Jiawei Han and Micheline Kamber. All rights reserved.
1

Graph Mining

Graph Pattern Mining

Mining Frequent Subgraph Patterns

Impact on Graph Search I: Graph Indexing

Impact on Graph Search II: Graph Similarity Search

Constrained Graph Pattern Mining

Graph Classification Graph Clustering Summary

2

Why Graph Mining?

Graphs are ubiquitous

Chemical compounds (Cheminformatics) Protein structures, biological pathways/networks (Bioinformactics) Program control flow, traffic flow, and workflow analysis

XML databases, Web, and social network analysis

Graph is a general model

Trees, lattices, sequences, and items are degenerated graphs

Diversity of graphs

Directed vs. undirected, labeled vs. unlabeled (edges & vertices), weighted, with angles & geometry (topological vs. 2-D/3-D)

Complexity of algorithms: many problems are of high complexity

3

Graph, Graph, Everywhere

from H. Jeong et al Nature 411, 41 (2001)

Aspirin

Yeast protein interaction network

Internet

Co-author network

Graph Pattern Mining

Frequent subgraphs

A (sub)graph is frequent if its support (occurrence

frequency) in a given dataset is no less than a minimum support threshold

Applications of graph pattern mining

Mining biochemical structures

Program control flow analysis

Mining XML structures or Web communities Building blocks for graph classification, clustering, compression, comparison, and correlation analysis
5

Example: Frequent Subgraphs

GRAPH DATASET

(A)
FREQUENT PATTERNS (MIN SUPPORT IS 2)

(B)

(C)

(1)

(2)

EXAMPLE (II)
GRAPH DATASET

FREQUENT PATTERNS (MIN SUPPORT IS 2)

Graph Mining Algorithms

Incomplete beam search Greedy (Subdue)

Inductive logic programming (WARMR)

Graph theory-based approaches

Apriori-based approach
Pattern-growth approach

SUBDUE (Holder et al. KDD94)

Start with single vertices

Expand best substructures with a new edge

Limit the number of best substructures

Substructures are evaluated based on their ability to compress input graphs

Using minimum description length (DL) Best substructure S in graph G minimizes: DL(S) + DL(G\S)

Terminate until no new substructure is discovered

9

WARMR (Dehaspe et al. KDD98)

Graphs are represented by Datalog facts

atomel(C, A1, c), bond (C, A1, A2, BT),

atomel(C, A2, c) : a carbon atom bound to a

carbon atom with bond type BT

WARMR: the first general purpose ILP system

Level-wise search
Simulate Apriori for frequent pattern discovery

10

Frequent Subgraph Mining Approaches

Apriori-based approach AGM/AcGM: Inokuchi, et al. (PKDD00) FSG: Kuramochi and Karypis (ICDM01) # PATH : Vanetik and Gudes (ICDM02, ICDM04) FFSM: Huan, et al. (ICDM03) Pattern growth approach MoFa, Borgelt and Berthold (ICDM02) gSpan: Yan and Han (ICDM02) Gaston: Nijssen and Kok (KDD04)
11

Properties of Graph Mining Algorithms

Search order breadth vs. depth Generation of candidate subgraphs apriori vs. pattern growth Elimination of duplicate subgraphs passive vs. active Support calculation embedding store or not Discover order of patterns path tree graph
12

Apriori-Based Approach
k-edge
(k+1)-edge

G1 G G G

G2
Gn

JOIN
13

Apriori-Based, Breadth-First Search

Methodology: breadth-search, joining two graphs

AGM (Inokuchi, et al. PKDD00) generates new graphs with one more node

FSG (Kuramochi and Karypis ICDM01) generates new graphs with one more edge
14

PATH (Vanetik and Gudes ICDM02, 04)

Apriori-based approach Building blocks: edge-disjoint path

construct frequent paths construct frequent graphs with 2 edge-disjoint paths construct graphs with k+1 edge-disjoint paths from graphs with k edge-disjoint paths repeat

A graph with 3 edge-disjoint paths

15

FFSM (Huan, et al. ICDM03)

Represent graphs using canonical adjacency matrix (CAM) Join two CAMs or extend a CAM to generate a new graph Store the embeddings of CAMs All of the embeddings of a pattern in the database Can derive the embeddings of newly generated CAMs
16

Pattern Growth Method

(k+2)-edge (k+1)-edge

G1
k-edge

G2

duplicate graph

Gn

17

MoFa (Borgelt and Berthold ICDM02)

Extend graphs by adding a new edge

Store embeddings of discovered frequent graphs

Fast support calculation Also used in other later developed algorithms such as FFSM and GASTON

Expensive Memory usage Local structural pruning

18

GSPAN (Yan and Han ICDM02)

Right-Most Extension

Theorem: Completeness

The Enumeration of Graphs using Right-most Extension is COMPLETE

19

DFS Code

Flatten a graph into a sequence using depth first search 0 1 2 4 e0: (0,1) e1: (1,2)

e2: (2,0)
e3: (2,3) e4: (3,1) e5: (2,4)
20

DFS Lexicographic Order

Let Z be the set of DFS codes of all graphs. Two DFS codes a and b have the relation a<=b (DFS Lexicographic Order in Z) if and only if one of the following conditions is true. Let a = (x0, x1, , xn) and b = (y0, y1, , yn), (i) (ii) if there exists t, 0<= t <= min(m,n), xk=yk for all k, s.t. k<t, and xt < yt xk=yk for all k, s.t. 0<= k<= m and m <= n.

21

DFS Code Extension

Let a be the minimum DFS code of a graph G and b be a non-minimum DFS code of G. For any DFS code d generated from b by one right-most extension,
(i)

(ii)
(iii)

d is not a minimum DFS code, min_dfs(d) cannot be extended from b, and min_dfs(d) is either less than a or can be extended from a.

THEOREM [ RIGHT-EXTENSION ] The DFS code of a graph extended from a Non-minimum DFS code is NOT MINIMUM

22

GASTON (Nijssen and Kok KDD04)

Extend graphs directly

Store embeddings
Separate the discovery of different types of graphs

path tree graph

Simple structures are easier to mine and duplication detection is much simpler

23

Graph Pattern Explosion Problem

If a graph is frequent, all of its subgraphs are

frequent the Apriori property

An n-edge frequent graph may have 2n

subgraphs

Among 422 chemical compounds which are

confirmed to be active in an AIDS antiviral

screen dataset, there are 1,000,000 frequent

graph patterns if the minimum support is 5%

24

Closed Frequent Graphs

Motivation: Handling graph pattern explosion problem Closed frequent graph A frequent graph G is closed if there exists no supergraph of G that carries the same support as G If some of Gs subgraphs have the same support, it is unnecessary to output these subgraphs (nonclosed graphs) Lossless compression: still ensures that the mining result is complete
25

CLOSEGRAPH

(Yan & Han, KDD03)

A Pattern-Growth Approach
(k+1)-edge

G1
k-edge

At what condition, can we stop searching their children i.e., early termination? If G and G are frequent, G is a subgraph of G. If in any part of the graph in the dataset where G occurs, G also occurs, then we need not grow G, since none of Gs children will be closed except those of G.
26

G2

Gn

Handling Tricky Exception Cases

a
c

b d

a
c

(pattern 1)

(graph 1)

d (graph 2)

a c d

(pattern 2)

27

Experimental Result

The AIDS antiviral screen compound dataset

from NCI/NIH

The dataset contains 43,905 chemical

compounds

Among these 43,905 compounds, 423 of them belongs to CA, 1081 are of CM, and the remaining are in class CI

28

Discovered Patterns

20%

10%

5%
29

Performance (1): Run Time

Run time per pattern (msec)

Minimum support (in %)

30

Performance (2): Memory Usage

Memory usage (GB)

Minimum support (in %)

31

Number of Patterns: Frequent vs. Closed

CA
Number of patterns
1.0E+06 1.0E+05 1.0E+04 1.0E+03 1.0E+02 0.05 0.06 0.07 0.08 0.1
32

frequent graphs closed frequent graphs

Minimum support

Runtime: Frequent vs. Closed

CA
Run time (sec)
10000 1000 100 10 1 0.05
FSG Gspan CloseGraph

Minimum support

0.06

0.07

0.08

0.1
33

Do the Odds Beat the Curse of Complexity?

Potentially exponential number of frequent patterns The worst case complexty vs. the expected probability 4 Ex.: Suppose Walmart has 10 kinds of products -4 The chance to pick up one product 10 -40 The chance to pick up a particular set of 10 products: 10 What is the chance this particular set of 10 products to be frequent 103 times in 109 transactions? Have we solved the NP-hard problem of subgraph isomorphism testing? No. But the real graphs in bio/chemistry is not so bad A carbon has only 4 bounds and most proteins in a network have distinct labels
34

Graph Mining

Graph Pattern Mining

Mining Frequent Subgraph Patterns

Impact on Graph Search I: Graph Indexing

Impact on Graph Search II: Graph Similarity Search

Constrained Graph Pattern Mining

Graph Classification Graph Clustering Summary

35

Graph Search

Querying graph databases: Given a graph database and a query graph, find all the graphs containing this query graph

query graph

graph database

36

Scalability Issue

Sequential scan

Disk I/Os
Subgraph isomorphism testing DayLight: Daylight.com (commercial) GraphGrep: Dennis Shasha, et al. PODS'02

An indexing mechanism is needed

Grace: Srinath Srinivasa, et al. ICDE'03

37

Indexing Strategy
Query graph (Q) Graph (G) If graph G contains query graph Q, G should contain any substructure of Q Substructure Remarks Index substructures of a query graph to prune graphs that do not contain these substructures
38

Indexing Framework

Two steps in processing graph queries

Step 1. Index Construction Enumerate structures in the graph database, build an inverted index between structures and graphs Step 2. Query Processing Enumerate structures in the query graph Calculate the candidate graphs containing these structures Prune the false positive answers by performing subgraph isomorphism test
39

Cost Analysis
QUERY RESPONSE TIME

Tindex
fetch index

Cq

Tio Tisomorphis m _ testing

number of candidates

REMARK: make |Cq| as small as possible

40

Path-based Approach
GRAPH DATABASE

(a) PATHS

(b)

(c)

0-length: C, O, N, S 1-length: C-C, C-O, C-N, C-S, N-N, S-O 2-length: C-C-C, C-O-C, C-N-C, ... 3-length: ...

Built an inverted index between paths and graphs

41

Path-based Approach (cont.)

QUERY GRAPH

0-edge: SC={a, b, c}, SN={a, b, c} 1-edge: SC-C={a, b, c}, SC-N={a, b, c} 2-edge: SC-N-C = {a, b}, Intersect these sets, we obtain the candidate answers - graph (a) and graph (b) - which may contain this query graph.

42

Problems: Path-based Approach

GRAPH DATABASE

(a) QUERY GRAPH

(b)

(c)

Only graph (c) contains this query graph. However, if we only index paths: C, C-C, C-C-C, C-C-C-C, we cannot prune graph (a) and (b).

43

gIndex: Indexing Graphs by Data Mining

Our methodology on graph index:

Identify frequent structures in the database, the frequent structures are subgraphs that appear quite often in the graph database
Prune redundant frequent structures to maintain a small set of discriminative structures Create an inverted index between discriminative frequent structures and graphs in the database
44

IDEAS: Indexing with Two Constraints

discriminative

(~103)

frequent

(~105)

structure

(>106)

45

Why Discriminative Subgraphs?

Sample database

(a)

(b)

(c)

All graphs contain structures: C, C-C, C-C-C Why bother indexing these redundant frequent structures? Only index structures that provide more information than existing structures
46

Discriminative Structures

Pinpoint the most useful frequent structures Given a set of structures f1 , f 2 , f n and a new structure x , we measure the extra indexing power provided by x ,

P x f1 , f 2 , f n , f i

x.

When P is small enough, x is a discriminative structure and should be included in the index Index discriminative frequent structures only Reduce the index size by an order of magnitude
47

Why Frequent Structures?

We cannot index (or even search) all of substructures Large structures will likely be indexed well by their substructures Size-increasing support threshold
support minimum support threshold

size
48

Experimental Setting

The AIDS antiviral screen compound dataset from

NCI/NIH, containing 43,905 chemical compounds

Query graphs are randomly extracted from the

dataset

GraphGrep: maximum length (edges) of paths is set at 10 gIndex: maximum size (edges) of structures is set at 10
49

Experiments: Index Size

1.4E+05 1.2E+05

# OF FEATURES

Path Frequent Structure Discriminative Frequent Structure

1.0E+05 8.0E+04 6.0E+04 4.0E+04 2.0E+04 0.0E+00

1k

2k

4k

8k

16k

DATABASE SIZE
50

Experiments: Answer Set Size

140 120 100 80 60 40 20 0
4 8 12 16

# OF CANDIDATES

GraphGrep gIndex Actual Match

20

24

QUERY SIZE

51

Experiments: Incremental Maintenance

80 70 60 50 40 30 20

2K

4K
From scratch

6k

8k
Incremental

10k

Frequent structures are stable to database updating Index can be built based on a small portion of a graph database, but be used for the whole database

Alternative Graph Indexing Methods

Graph-structure-based indexing and similarity search Structure-based index methods, e.g., g-Index, S-path index Use index to search for similar graph/network structures Substructure indexing Key problem: What substructures as indexing features? gIndex [Yan, Yu & Han, SIGMOD04]: Find frequent and discriminative subgraphs (by graph-pattern mining) S-path [Zhao & Han, VLDB10]: Use decomposed shortest paths as basic indexing features

53

Why S-Path as Indexing Features?

Neighborhood signatures of vertices are built to maintain indexing features: Effective search space pruning ability Processing (Query Decomposition): Decompose the query graph into a set of indexed shortest paths in S-Path

Network

Query

A global lookup table

Neighborhood signature of v3

Graph Mining

Graph Pattern Mining

Mining Frequent Subgraph Patterns

Impact on Graph Search I: Graph Indexing

Impact on Graph Search II: Graph Similarity Search

Constrained Graph Pattern Mining

Graph Classification Graph Clustering Summary

55

Structure Similarity Search

CHEMICAL COMPOUNDS

(a) caffeine

(b) diurobromine

(c) viagra

QUERY GRAPH

56

Some Straightforward Methods

Method1: Directly compute the similarity between the

graphs in the DB and the query graph

Sequential scan Subgraph similarity computation

Method 2: Form a set of subgraph queries from the original query graph and use the exact subgraph search

Costly: If we allow 3 edges to be missed in a 20-edge

query graph, it may generate 1,140 subgraphs

57

Index: Precise vs. Approximate Search

Precise Search

Use frequent patterns as indexing features

Select features in the database space based on their selectivity

Build the index

Hard to build indices covering similar subgraphs explosive number of subgraphs in databases Idea: (1) keep the index structure

Approximate Search

(2) select features in the query space

58

Substructure Similarity Measure

Query relaxation measure The number of edges that can be relabeled or missed; but the position of these edges are not fixed
QUERY GRAPH

59

Substructure Similarity Measure

Feature-based similarity measure

Each graph is represented as a feature vector X = {x1, x2, , xn}

Similarity is defined by the distance of their corresponding vectors Advantages

Easy to index
Fast

Rough measure
60

Intuition: Feature-Based Similarity Search

Graph (G1) Query (Q) If graph G contains the major part of a query graph Q, G should share a number of common features with Q Given a relaxation ratio, calculate the maximal number of features that can be missed !

Graph (G2)

Substructure

At least one of them should be contained

61

Feature-Graph Matrix
graphs in database G1 f1 0 0 G2 1 1 G3 0 0 G4 1 0 G5 1 1

features

f2

f3
f4 f5

1
1 0

0
0 0

1
0 1

1
0 1

1
1 0

Assume a query graph has 5 features and at most 2 features to miss due to the relaxation threshold
62

Edge RelaxationFeature Misses

If we allow k edges to be relaxed, J is the maximum number of features to be hit by k edgesit becomes the maximum coverage problem
NP-complete

A greedy algorithm exists J greedy

1 1 k

We design a heuristic to refine the bound of feature misses

63

Query Processing Framework

Three steps in processing approximate graph queries

Step 1. Index Construction Select small structures as features in a graph database, and build the featuregraph matrix between the features and the graphs in the database

64

Framework (cont.)
Step 2. Feature Miss Estimation Determine the indexed features belonging to the query graph Calculate the upper bound of the number of features that can be missed for an approximate matching, denoted by J On the query graph, not the graph database

65

Framework (cont.)

Step 3. Query Processing

Use the feature-graph matrix to calculate the difference in the number of features between graph G and query Q, FG FQ If FG FQ > J, discard G. The remaining graphs constitute a candidate answer set
66

Performance Study

Database Chemical compounds of Anti-Aids Drug from NCI/NIH, randomly select 10,000 compounds Query Randomly select 30 graphs with 16 and 20 edges as query graphs Competitive algorithms Grafil: Graph Filterour algorithm Edge: use edges only All: use all the features
67

Comparison of the Three Algorithms

10000

# of candidates

1000

Grafil Edge All

100

10 1 2 3 4

edge relaxation
68

Summary: Graph Pattern Mining

Graph mining has wide applications

Frequent and closed subgraph mining methods

gSpan and CloseGraph: pattern-growth depth-first search approach

Graph indexing techniques

Frequent and discriminative subgraphs are high-quality indexing features

Indexing and feature-based matching

Similarity search in graph databases

Constraint-based graph pattern mining

References (1)

T. Asai, et al. Efficient substructure discovery from large semi-structured data, SDM'02 C. Borgelt and M. R. Berthold, Mining molecular fragments: Finding relevant substructures of molecules, ICDM'02 M. Deshpande, M. Kuramochi, and G. Karypis, Frequent Sub-structure Based Approaches for Classifying Chemical Compounds, ICDM 2003 M. Deshpande, M. Kuramochi, and G. Karypis. Automated approaches for classifying structures, BIOKDD'02 L. Dehaspe, H. Toivonen, and R. King. Finding frequent substructures in chemical compounds, KDD'98 C. Faloutsos, K. McCurley, and A. Tomkins, Fast Discovery of 'Connection Subgraphs, KDD'04 L. Holder, D. Cook, and S. Djoko. Substructure discovery in the subdue system, KDD'94 J. Huan, W. Wang, D. Bandyopadhyay, J. Snoeyink, J. Prins, and A. Tropsha. Mining spatial motifs from protein structure graphs, RECOMB04 J. Huan, W. Wang, and J. Prins. Efficient mining of frequent subgraph in the presence of isomorphism, ICDM'03 H. Hu, X. Yan, Yu, J. Han and X. J. Zhou, Mining Coherent Dense Subgraphs across Massive Biological Networks for Functional Discovery, ISMB'05 A. Inokuchi, T. Washio, and H. Motoda. An apriori-based algorithm for mining frequent substructures from graph data, PKDD'00 C. James, D. Weininger, and J. Delany. Daylight Theory Manual Daylight Version 4.82. Daylight Chemical Information Systems, Inc., 2003. G. Jeh, and J. Widom, Mining the Space of Graph Properties, KDD'04 M. Koyuturk, A. Grama, and W. Szpankowski. An efficient algorithm for detecting frequent subgraphs in biological networks, Bioinformatics, 20:I200--I207, 2004.

References (2)

M. Kuramochi and G. Karypis. Frequent subgraph discovery, ICDM'01 M. Kuramochi and G. Karypis, GREW: A Scalable Frequent Subgraph Discovery Algorithm, ICDM04 B. McKay. Practical graph isomorphism. Congressus Numerantium, 30:45--87, 1981. S. Nijssen and J. Kok. A quickstart in frequent structure mining can make a difference. KDD'04 J. Prins, J. Yang, J. Huan, and W. Wang. Spin: Mining maximal frequent subgraphs from graph databases. KDD'04 D. Shasha, J. T.-L. Wang, and R. Giugno. Algorithmics and applications of tree and graph searching, PODS'02 J. R. Ullmann. An algorithm for subgraph isomorphism, J. ACM, 23:31--42, 1976. N. Vanetik, E. Gudes, and S. E. Shimony. Computing frequent graph patterns from semistructured data, ICDM'02 C. Wang, W. Wang, J. Pei, Y. Zhu, and B. Shi. Scalable mining of large disk-base graph databases, KDD'04 T. Washio and H. Motoda, State of the art of graph-based data mining, SIGKDD Explorations, 5:59-68, 2003 X. Yan and J. Han, gSpan: Graph-Based Substructure Pattern Mining, ICDM'02 X. Yan and J. Han, CloseGraph: Mining Closed Frequent Graph Patterns, KDD'03 X. Yan, P. S. Yu, and J. Han, Graph Indexing: A Frequent Structure-based Approach, SIGMOD'04 X. Yan, X. J. Zhou, and J. Han, Mining Closed Relational Graphs with Connectivity Constraints, KDD'05 X. Yan, P. S. Yu, and J. Han, Substructure Similarity Search in Graph Databases, SIGMOD'05 X. Yan, F. Zhu, J. Han, and P. S. Yu, Searching Substructures with Superimposed Distance, ICDE'06 M. J. Zaki. Efficiently mining frequent trees in a forest, KDD'02 P. Zhao and J. Han, On Graph Query Optimization in Large Networks", VLDB'10