# Pattern discovery from graph structured data

CREATED: 200801220758 Speaker: Hiroshi Motoda (AFRL)

** Background

- heuristic: frequenting occurring events are worth paying attention to
- regularity
- concept: something which makes inference more efficient
- inference load = graph size + complexity of concept - #concepts
- repeatedly find frequent subgraphs which minimize inference load, get hierarichal representation
- graphs ** chemical compounds ** social networks ** web ** abstract concept ** important substructures
- approaches ** Apriori based (AGM) ** Graph based induction (GBI) ** Apriori based graph mining
- how to identify isomorphic candidates
- idea: define a canonical form of a graph as the matrix with minimum code
- canonical form(X) = canonical form(Y) => X and Y are isomorphic
- join using adj matrix of k freq subgraphs with common k-1 subgraph to get k+1 candidate graph, need to check that all (k+1)Ck subgraphs are freq
- Application ** analysis of mutagenicity of amino acid compounds ** HIV compounds (min support for active compounds, max support for inactive compounds) ** consumer behavior as directed graph *** Extensions
- taxonomy of labels ** extract least general subgraph of same support ** application: predictive toxicology evaluation data
- 3D information ** application: dopamine compounds ** Graph based induction
- pairwise chunking (contract freq pair into a single node)
- problem: overlapping patterns cannot be found
- extensions ** use beam search ** pseudo chunking (graph size remains the same, still remember structure in chunk) ** find acyclic subgraph/path/tree ** inpattern/outpattern (domain knowledge) ** Pruning
- frequency is monotonic
- X^2/information gain is not monotonic but convex, can help to compute upper bound
- find simple patterns first, best path -> best acyclic graph -> best subgraph
- best = max information gain ** Classification
- use subgraphs to construct decision tree for classification ** Challenges
- efficient graph mining
- produce human understandable results