UNIVERSITA’ DEGLI STUDI DELLA CALABRIA
FACOLTA’ DI INGEGNERIA
Corso di Laurea Spec. in Ingegneria Informatica
DATA MINING E SCOPERTA DELLA CONOSCENZA
“Graph Mining”
Prof. G. Manco
Ing. F. Folino
Francesco Gullo
matr. 87675
Anno Accademico 2004/2005
Modello Transazionale
Database di transazioni:
TID
ITEMS
1
Bread, Milk
2
Bread, Diaper, Beer, Eggs
3
Milk, Diaper, Beer, Coke
4
Bread, Milk, Diaper, Beer
5
Bread, Milk, Diaper, Coke
Obiettivo primario:
ricerca di itemset frequenti
Transazione:insieme di items
Itemset: collezione di items
Es. {Bread, Milk, Coke}
{Bread, Milk}
Es:
{Bread, Diaper}
{Diaper, Beer}
Modelli alternativi
In molti ambiti gli oggetti del dataset vengono
rappresentati mediante strutture dati più complesse,
ad es. attraverso grafi.
Transazioni
Items
Relazioni tra items
Ricerca di itemset
fequenti in un dataset
di transazioni
Grafi
Nodi
Archi
Ricerca di sottografi
frequenti in un
dataset di grafi
Applicazioni
•
•
•
•
•
Chimica
Genetica
Web
Reti
…
Definizioni preliminari

Grafo etichettato:
G  (V , E , L, l )
V, insieme di nodi
E, insieme di archi
L, insieme di etichette
l : V  E  L , funzione che assegna etichette a nodi ed archi



Gs=(Vs, Es) è sottografo di G=(V, E)
sse VS  V e ES  E
Gs=(Vs, Es) è sottografo indotto di G=(V, E)
sse VS  V e u, v V (GS ), (u, v)  E (GS )  (u, v)  E (G)
G=(V,E) è connesso
sse esiste un cammino per ogni coppia di nodi  V
Definizioni preliminari

Un isomorfismo è una funzione biunivoca
f : V (G )  V (G) tale che:
u V (G), lG (u )  lG ( f (u ))
(u, v)  E (G), ( f (u ), f (v))  E (G)  lG (u, v)  lG ( f (u ), f (v))



Un automorfismo è un isomorfismo da G a G
Un sottografo-isomorfismo da G a G’ è un
isomorfismo da G a un sottografo di G’
La canonical label di un grafo G=(V,E), cl(G), è un
codice unico (stringa), invariante rispetto
all’ordinamento di nodi e archi del grafo
Isomorfismo
Proprietà:



Struttura topologicamente uguale
Matrici di adiacenza e incidenza
Vertex invariants
Punto cruciale: risoluzione del subgraph
isomorphism problem
Isomorfismo
1
G:
a
b
c
2
d
c
1
H:
2
b
d
a
a
3
a
4
3
4
G e H sono isomorfi (esiste in isomorfismo ‘f’ tra G e H):
4
H:
a
2
b
c
a
1
d
f(1)=4
f(2)=1
f(3)=2
f(4)=3
3
G’ e H’ non sono isomorfi pur avendo lo stesso numero
di nodi e di archi:
G’:
H’:
Canonical Labeling


Comparazione veloce tra grafi e ordinamento
completo e deterministico per insiemi di grafi
Canonical labels usate:



Concatenazione di righe o colonne della matrice di
adiacenza
=> non univoco!
Tra tutte le possibili permutazioni dei nodi, scelta del
codice maggiore o minore
=> |V|! permutazioni
Utilizzo di vertex invariants per il partizionamento in
classi di nodi
=>
m
 ( p !)
i
i 1
permutazioni
Canonical Labeling
Classi:
p0={v1} (label:’a’, degree:3)
p1={v0,v3} (label:’a’, degree:1)
p2={v2} (label:’b’, degree:1)
1! x 2! x 1! = 2 permutazioni
invece di
4! = 24 permutazioni
CL
Definizione del problema
Frequent Subgraph Discovery:

Input:
D={G1,…,Gn}, dataset di n grafi etichettati
non orientati
 σ, supporto minimo (0<σ<1)


Obiettivo:
Trovare tutti i sottografi non orientati e
connessi presenti in almeno σxn grafi del
dataset D
Algoritmo Apriori
• largamente utilizzato nei modelli market-basket
• schema base per alcuni algoritmi di ricerca di
sottografi
Candidate Generation:
1. L1= {items frequenti};
2. for(k = 1; Lk≠∅; k++) do begin
3.
Ck+1= candidati generati da Lk;
4.
for each transazione t in D
5.
join
Frequency Counting
false test
incrementa il supporto dei candidati in Ck+1
contenuti in t;
6.
Lk+1= candidati in Ck+1 con supporto ≥ min_support;
7. return {L1 ,…, Ln};
Soluzioni proposte
Algoritmi analizzati:





AGM
FSG
gSpan
FFSM
GASTON
Parametri di performances:




|D|: dimensione del dataset
|T|: dimensione media transazioni
|N|: numero di etichette
σ : supporto minimo
Studi sperimentali:

dataset reali


Chemical Compound Dataset (NTP, DTP, PTE ecc.)
dataset sintetici


Parametri: |D|, |T|, |N|, |L|, |I|
D10kN4I10T20L200
AGM: caratteristiche




Basato sull’algoritmo Apriori
Incremento della dimensione dei sottografi
frequenti mediante aggiunta di un nodo alla
volta
La ricerca è di sottografi indotti frequenti
Si basa sulla rappresentazione dei grafi
mediante matrici di adiacenza
AGM: rappresentazione di grafi
Matrice di adiacenza:
Dato un grafo etichettato G  (V (G ), E (G ), L(G ), l ) , la matrice di adiacenza X
è costituita dai seguenti elementi xij:
num(lb );eh (vi ,v j )E (G ) lb l (eh )
x 
ij
0;(vi ,v j )E(G)
dove num(lb) è un intero arbitrariamente assegnato all’etichetta lb
Matrice di adiacenza vertex-sorted:
La matrice di adiacenza Xk di un grafo G(Xk) di dimensione k è vertex-sorted
se:
num(lb(vi ))  num(lb(vi 1 )); i  1,2,..., k  1
Codice della matrice di adiacenza:
Il codice di una matrice di adiacenza Xk, code(Xk), è dato dalla stringa
risultante dalla concatenazione degli elementi sulle colonne del triangolo
superiore della matrice stessa
AGM: candidate generation
1. JOIN
La join avviene tra grafi che differiscono per un unico nodo:
elementi non
vettori
sottomatrice
colonnainda
di
determinati
dim.
comune
X(k-1)
eY x1
k
k
Per evitare ridondanze, la join tra Xk e Yk viene fatta
soltanto se code(Xk) ≤ code(Yk)
=>matrice vertex sorted in ‘normal form’
=>di ogni singolo grafo generato vengono calcolate e
memorizzate tutte le normal form ad esso relative
AGM: candidate generation
2. ELIMINAZIONE CANDIDATI INFREQUENTI
L’eliminazione di sottografi infrequenti consta di tre passi:
•costruzione delle sottomatrici
(mediante eliminazione di un nodo per volta)
•normalization delle sottomatrici ottenute
(approccio bottom-up)
•verifica di frequenza, mediante ricerca di matching
con l’insieme dei candidati di dim. inferiore
AGM: frequency counting
Poiché dello stesso grafo sono presenti più rappresentazioni, il
frequency counting deve prevedere la somma dei contributi
associati alla singola normal form
=>meccanismo di indicizzazione basato su canonical form
X C  arg min code( X )
X NF ( G )
Frequency Counting:
•calcolo della canonical form di ogni candidato
(approccio bottom-up)
•calcolo delle normal forms dei k-subgraph
indotti di ogni transazione
•calcolo della frequenza
AGM: prestazioni
Risultati su dataset sintetici:
AGM: prestazioni
Risultati:




Andamento atteso al variare dei parametri
caratteristici
Scaling lineare al variare della dim. del dataset
Complessità minore per grafi orientati (frequenza
minore dei sottografi)
Su dataset NTP (National Toxicology Program):
PC 400MHz 128MB => 40 min con σ=20%
8 gg con σ=10%
AGM: conclusioni

Vantaggi:




Semplicità di implementazione
Pruning in base alla frequenza
Prestazioni discrete per dataset piccoli e supporti
grandi
Svantaggi:




La ricerca è di soli sottografi indotti
Estrema ridondanza: ad ogni passo vengono
mantenute e calcolate tutte le normal form di
ogni singolo candidato
Operazioni di join, normalization e ricostruzione
canonical form molto costose
Prestazioni scadenti per dimensioni medio-elevate
(8gg per |D|=100.000 e minsup=10%)
FSG: caratteristiche




Basato sull’algoritmo Apriori
Incremento della dimensione dei sottografi
frequenti mediante aggiunta di un arco alla
volta
Ottimizzazioni per candidate generation e
frequency counting
Utilizzo di canonical labeling
FSG: algoritmo
fsg(D, σ)
generazione di tutti i
sottografi
{
frequenti di
1: F1 ← all frequent 1-subgraphs in D
dimensione 1 e 2
2
2: F ← all frequent 2-subgraphs in D
Candidate
Generation:
3: k ← 3
Frequency
Counting
k-1
4: while F ≠ Ø do
generazione sottografi
candidati di dim. k,
5:
Ck ← fsg-gen(Fk-1)
mediante fusione dei
k
k
6:
for each candidate G  C do
sottografi frequenti
k
di dim. k-1
7:
G .count ← 0
8:
for each transaction T  D do
9:
if Gk is included in T then
10:
Gk.count ← Gk.count + 1
11: Fk ← {Gk E Ck | Gk.count ≥ σ|D|}
12: k ← k + 1
13: return {F1, F2,…, Fk-2}
selezione dei candidati che
}
soddisfano il vincolo di supporto
FSG: candidate generation
La join avviene tra sottografi di dim. k che condividono lo stesso
(k-1)-subgraph (core)
il risultato potrebbe non essere un unico (k+1)-subgraph:
(3). Cores multipli
(2). Automorfismi multipli del core
(1). Nodo con uguale etichetta:
FSG: candidate generation
fsg-gen(Fk)
{
}
1: Ck+1 ← Ø
2: for each pair of (Gik,Gjk)  Fk, i ≤ j and cl(Gik) ≤ cl(Gjk) do
3:
Hk-1 ← { Hk-1| Hk-1 is a core shared by Gik and Gjk }
4:
for each core Hk-1 E Hk-1 do
5:
{ Bk+1 is a set of tentative candidates }
6:
Bk+1 ← fsg-join(Gik,Gjk, Hk-1)
7:
for each Gjk+1 E Bk+1 do
8:
{ test if the downward closure property holds }
9:
flag ← true
10:
for each edge el  Gjk+1 do
11:
Hl k ← Gjk+1- el
12:
if Hl k is connected and Hl k Fk then
13:
flag ← false
generazione
tutti i
14:
break
generazione
di tutti di
i possibili
core condivisi
per
15:
if flag = true then
candidati
mediante
coppia
di di
fusione ogni
di ogni
coppia
16:
Ck+1 ← Ck+1 U {Gjk+1}
sottografi
frequenti
false
test
sottografi
frequenti,
per
17: return Ck+1
ogni core condiviso
FSG: candidate generation
fsg-join(G1k, G2k, Hk-1)
{
1: e1 ← the edge appears only in G1k, not in Hk-1
2: e2 ← the edge appears only in G2k, not in Hk-1
3: M ← generate all automorphisms of Hk-1
4: Bk+1 = Ø
5: for each automorphism ψ  M do
6:
Bk+1 ← Bk+1 U {all possible candidates of size k+1
}
7: return Bk+1
created from a set of e1, e2, Hk-1 and ψ}
generazione dei candidati (max. 2)
per ogni automorfismo del core
FSG: candidate generation
3 steps computazionalmente costosi:



generazione cores (e automorfismi)
join
eliminazione candidati infrequenti
Ottimizzazioni:




ogni k-subgraph frequente mantiene le canonical
label dei suoi (k-1)-subgraph frequenti
Inverted indexing scheme
caching degli automorfismi dei cores precedenti
uso di canonical labeling per la verifica di
ridondanze e sottografi infrequenti (test veloci e
ricerca binaria)
FSG: frequency counting
Ad ogni passo, nxmk subgraph isomorphism problem
(n=|D|, mk=# di candidati al passo k)
Il costo computazionale è ridotto dall’uso di transaction
identifier (TID) lists:



ogni sottografo frequente mantiene la lista di
TID delle transazioni nelle quali è contenuto
per il calcolo della frequenza di un (k+1)subgraph si considera l’intersezione delle liste di
TID dei suoi k-subgraph frequenti
se la dim. della lista è minore del supporto
minimo, il candidato viene scartato, altrimenti
viene valutata la frequenza sulle sole transazioni
della lista
FSG: canonical labeling
Il canonical labeling rappresenta un punto critico
dell’algoritmo.
Viene massicciamente impiegato in:
• Test di ridondanza (candidati già generati
durante la join)
• False test per la verifica di sottografi frequenti
Per questioni di efficienza, l’algoritmo di CL
utilizzato fa uso di vertex invariants,
prevedendone tre versioni differenti:
• Partition ordering
• Neighbor list
• Iterative partitioning
FSG: prestazioni
Risultati su dataset PTE (Predictive Toxicology Evaluation
Challenge):
• 3 ordini di grandezza
tra le versioni + e –
ottimizzate
• Inverted index: 2-4
• Partition ordering: 5-15
• Neighbor list: 2 ordini
di grandezza
• Iterative partitioning: 1
ordine di grandezza
• Tempi
notevolmente
inferiori di quelli di AGM
FSG: prestazioni
Risultati su dataset sintetici:

Sensibilità alla struttura del grafo (|D|, |L|
costanti; |T|, |I|, |N| variabili; σ=2%)

|T| e |I| grandi => grande varianza


|N| grande => complessità minore



Motivazione: automorfismi in candidate generation,
subgraph isomorphism in frequency counting e CL
Valore di regime in relazione ai valori di |T| e |I|
|T| grande => complessità maggiore



Motivazione: presenza variabile di pattern regolari
Motivazione: frequency counting e CL
Crescita più lenta se |N| grande
|I| grande => complessità maggiore



Motivazione: candidate generation e CL
Crescita più lenta se |N| grande e/o |T| piccolo
Influenza indiretta di σ e |T|
FSG: prestazioni
Scalabilità
sulla dimensione del dataset
Analisi
al variare di |D| e |T| => scalabilità lineare
FSG: conclusioni

Vantaggi:




Ricerca di sottografi generali
Numerose ottimizzazioni
Prestazioni molto superiori ad AGM
Svantaggi:


Candidate generation comunque costosa
nonostante ottimizzazioni (false test e join
ridondante)
Complessità spaziale elevata (a causa di BFS)
GSPAN: caratteristiche


Depth-first search invece di breadth-first
search
Incremento della dimensione dei sottografi
frequenti mediante aggiunta di un arco alla
volta

Lo spazio di ricerca è un albero
gerarchicamente basato sul DFS code

Join sostituita dalla meno onerosa
extension e false test eliminato
GSPAN: DFS code
• DFS tree
• DFS subscripting
• Rightmost vertex e rightmost path
• Forward edge set :
• Backward edge set :
GSPAN: DFS code
Ordinamenti tra archi e1=(vi1,vj1), e2=(vi2,vj2):
• ordinamento forward:
sse j1<j2
• ordinamento backward:
sse i1<i2 oppure i1=i2 Λ
j1<j2
• ordinamento forward-backward:
oppure
• ordinamento totale:
È utilizzato nella definizione
del DFS code per un
grafo G a partire da un
DFS tree T
sse
oppure
sse
GSPAN: DFS code
Ordinamento lessicografico DFS:
Dati Z={code(G,T)|T è un DFS tree di G}
α=code(Gα ,Tα)=(a0,a1,…,am), β=code(Gβ ,Tβ)=(b0,b1,…,bn)
Eα,f,Eα,b, Eβ,f,Eβ,b, forward edge set e backward edge set per Tα e Tβ
at=(ia,ja,lia,l(ia,ja),lja) e bt=(ib,jb,lib,l(ib,jb),ljb)
α ≤ β sse:
Il minimum DFS code di un grafo G è il DFS code minimo in base
all’ordinamento lessicografico DFS e costituisce la canonical label di G
GSPAN: spazio di ricerca
Lo spazio di ricerca è rappresentato dal DFS code tree
Relazione padre P = (a0, a1,…,am)
figlio C = (a0, a1,…,am, b)
Relazione tra fratelli: ordinamento
lessicografico basato sul DFS
code
pruning
L’operazione di extension per
la costruzione dei figli di
ogni nodo consta
nell’aggiunta di archi per i
soli nodi del rightmost
path
GSPAN: spazio di ricerca
Teoremi:
DFS Code Tree Covering
DFS Code Growth
DFS Code Pruning
Il DFS code tree contiene i
minimum DFS code di
tutti i grafi (completa
enumerazione)
Il minimum DFS code di un
grafo G, durante la DFS,
è incontrato prima di
qualsiasi altro DFS code
non minimum
rappresentante G
La discendenza di un nodo
con DFS code non
minimum non darà vita
ad alcun nodo con DFS
code minimum
GSPAN: algoritmo
GraphSet_Projection(
{
)
generazione di
tutti
eliminazione
archi
e gli
nodi
archi
a
partire
infrequenti dai grafi
dall’insieme
di etichette
del dataset
GS
frequenti e salvataggio
dei soli frequenti
}
salvataggio degli ID di
DFS
ricorsiva
nel di in
ogni
transazione
riduzione di ogni
transazione
sottoalbero
aventel’arco
come e
cui eliminazione
compare
GS mediante
root l’arco
s
dell’arco appena
analizzato
GSPAN: depth first search
Subgraph_Mining(
{
)
pruning
frequency
counting
}
Enumerate(s)
{
}
continuazione ricorsiva
calcolo
tutte
le occorrenze
di
della
DFS
per i di
soli
calcolodi
della
frequenza
ogni
s nelle
transazioni
in cui è
sottografi
frequenti
figlio
di s e salvataggio
contenuto;
il subgraph
delle
transazioni
in cui è
isomorphism
problem
è
presente
risolto con approccio
backtracking
GSPAN: ottimizzazioni

Pruning



Minimum DFS code



pre-pruning
post-pruning
generazione di tutti i DFS code (automorfismi)
confronti parziali
Children generation


prima del counting (possibilità di frequenza 0)
durante il counting (frequenza almeno pari ad 1)
GSPAN: prestazioni
Risultati su dataset sintetici:




Complessità 6-30 volte inferiore di FSG (su
vari dataset generati)
Meno sensibile di FSG a valori piccoli del
parametro |N| (numero di etichette)
Comportamento molto buono su grafi grandi
e densi (15-45 volte migliore di FSG)
Scalabilità lineare nella dimensione del
dataset
Risultati su dataset PTE:


Speedup tra gSpan e FSG molto elevato
(sottostrutture ad albero e poche etichette
agli archi)
Computazione successful anche per supporti
molto piccoli (1.5%)
GSPAN: conclusioni

Vantaggi:






Join in candidate generation sostituita da
extension (minore complessità e ridondanze)
Eliminazione di false test in candidate generation
Complessità spaziale ridotta (grazie a DFS)
Riduzione delle transazioni del dataset ad ogni
macropasso
Prestazioni in generale superiori ad FSG
Svantaggi:


Necessità di pruning test per la possibilità di DFS
code duplicati
La risoluzione di subgraph isomorphism problems
anche se in quantità ridotta è comunque presente
FFSM: caratteristiche




Depth-first search
Incremento della dimensione dei sottografi
frequenti mediante aggiunta di un arco alla
volta
Lo spazio di ricerca è un albero
gerarchicamente basato sulle suboptimal
CAM
Operazioni efficienti di join e extension per
la generazione dei figli di ogni nodo
dell’albero di ricerca
FFSM: CAM
Ogni grafo viene rappresentato mediante la
propria matrice di adiacenza:
Codice di una matrice di
adiacenza M (code(M))
Canonical Form
(CF)
Canonical Adjacency Matrix
(CAM)
Concatenazione delle
righe del triangolo
inferiore della
matrice M
Massimo tra tutti i
possibili codici
(ordinamento
lessicografico)
Matrice di adiacenza
che dà origine alla CF
FFSM: CAM
code(M1)=“axbxyb0yyb” ≥ code(M2)=“axb0ybxyyb”
≥ code(M3)=“bybyyb0xxa”
FFSM: CAM
Ogni codice stabilisce un ordinamento tra
gli archi del grafo in questione
Maximal Proper Submatrix: matrice
ottenuta dall’eliminazione dell’ultimo
arco nell’ordinamento
CF di un grafo è
sempre ≥ della
CF di un suo
sottografo
Maximal proper
submatrix di una
CAM rappresenta
un sottografo
connesso
Maximal proper
submatrix di
una CAM è
CAM
FFSM: CAM tree
Il CAM tree di un grafo G
contiene tutte le CAM dei
sottografi connessi di G
• la root è la matrice vuota
• ogni nodo è un sottografo
distinto di G, rappresentato
dalla sua CAM
• il padre di un nodo è dato dalla
maximal proper submatrix del
nodo stesso
FFSM: CAM tree
La generazione del CAM tree per un grafo G
viene effettuata applicando ad ogni nodo
operazioni efficienti di join e extension:
FFSM-join e FFSM-extension
Caratteristiche:



FFSM-join genera ogni distinta CAM una volta
sola
FFSM-join genera al massimo due CAM
FFSM-extension genera tutte le CAM mediante
aggiunta di un arco in un unico punto
Sostanziale riduzione di candidati ridondanti!
FFSM: FFSM-join
La join tra due matrici A(mxm) e B(nxn) che condividono la
stessa maximal proper submatrix consta di tre casi:
A e B matrici inner
Per evitare Aridondanze
la join
matrice inner
tra due matrici A e B viene
B matrice outer
effettuata soltanto se
code(A)≥code(B), tranne
che per il caso 3b
A e B matrici outer
FFSM: FFSM-extension
L’extension viene effettuata considerando un unico punto di
scelta: viene aggiunto un arco all’ultimo nodo del grafo in
considerazione verso un ulteriore nodo aggiuntivo.
versione non
ottimizzata!
FFSM: spazio di ricerca
Il CAM tree è un albero non
completo
Per garantire la completezza
c’è bisogno di operazioni di
join tra CAM e suboptimal
CAM
Suboptimal CAM tree
Matrici rappresentanti
sottografi validi ottenute a
partire da suboptimal CAM
FFSM: algoritmo
generazione figli mediante
generazione
figli mediante
FFSM-extension
FFSM-join
insieme di tutte le suboptimal
CAM del livello superiore
frequency counting (la
versione ottimizzata fa
uso di embedding list)
FFSM: embedding list
Embedding di una
matrice di adiacenza
A in un grafo G
Matching di nodi tra A e un
sottografo di G
(subgraph isomorphism)
Embedding set di A
Insieme di tutti gli embedding
di A in un dataset D
Il proprio embedding set viene mantenuto da ogni nodo e
trasmesso ai figli durante le operazioni di join ed extension
La frequenza di un sottografo nel dataset è pari al numero di grafi
differenti presenti nel proprio embedding set
=> nessun subgraph isomorphism problem da risolvere!
FFSM: embedding list
FFSM-join:
A=join{P,Q}




OA, OP, OQ embedding set di A, P, Q rispettivamente
1): OA = OP ∩ OQ
2): OA = {L | L = u1,…,un-1,un, L є OQ, L’ = u1,…,un-1 є OP}
3a): OA = OP ∩ OQ
3b): OA = {L | L = u1,…,un, L’ = u1,…,un-2,un-1 є OP, L’’ = u1,…,un-2,un є OQ}
FFSM-extension:
riduzione dei
possibili nodi
da considerare
FFSM: prestazioni
Risultati su
dataset reali:
PTE
 DTP AIDS (CA)
 DTP AIDS (CM)

FFSM: prestazioni
Risultati su
dataset sintetici:
σ variabile
 |T| variabile
 |N| variabile

FFSM: conclusioni

Vantaggi:





Candidate generation molto efficiente grazie alle
operazioni di FFSM-join e FFSM-extension
(massiccia diminuzione di ridondanze)
Nessuna risoluzione di subgraph isomorphism
problem nel frequency counting
Complessità spaziale ridotta (grazie a DFS)
Prestazioni in generale superiori rispetto a gSpan
Svantaggi:


Canonical labeling semplice ma costoso
Necessità di CAM test per ogni matrice, ad ogni
livello
GASTON: caratteristiche


Mining differenziato per differenti
sottostrutture (cammini, alberi, grafi)
Operazioni efficienti per l’enumerazione
delle singole sottostrutture

Depth-first search

Utilizzo di embedding list
GASTON: spazio di ricerca
Lo spazio di ricerca è
partizionato in base alla
sottostruttura da
considerare:



Paths
Free Trees
Cyclic Graphs
cycle closing
refinement
Ordinamento parziale
tra sottostrutture
di un grafo
node refinement
node refinement
GASTON: path enumeration
(v1e1v2…vn-1en-1vn)
Possibili ridondanze dovute all’orientamento!
Definizione univoca del predecessore di ogni path string
nell’albero di enumerazione:
(v1,e1) > (vn,en-1) => padre: (v2…vn-1en-1vn)
comparazione
lessicografica
tra (v1,e1) e
(vn,en-1)
(v1,e1) < (vn,en-1) => padre: (v1e1v2…vn-1)
path simmetrico
=>padre:indifferente!
(v1,e1)=(vn,en-1)
(v1e1v2…vn-1)<(vnen-1vn-1…v2)
=>padre:(v1e1v2…vn-1)
(vnen-1vn-1…v2)< (v1e1v2…vn-1)
=>padre:(v2…vn-1en-1vn)
GASTON: path enumeration
Algoritmo di refinement:
(v1e1v2…vn-1en-1vn): total simmetry
(v1e1v2…vn-1)
: front simmetry
(v2…vn-1en-1vn): back simmetry
0 => stringa simmetrica
-1 => inversa minore
+1 => corrente minore
total simmetry=0 => tutti i refinements possibili
(l(v’),l(e’)) > (l(v1),l(e1))
altrimenti, solo determinati (l(v’),l(e’)) possibili
(l(v’),l(e’)) = (l(v1),l(e1)),
se back simmetry ≥ 0
total simmetry e front simmetry sono propagate da padre in figlio
in tempo costante, back simmetry in tempo lineare
GASTON: free tree enumeration
path P di lunghezza massima in un free tree T: P={v1,…vm}
m dispari => centred tree
m pari => bicentred tree
Free tree enumeration:
•
path corrispondenti alla backbone
• free tree con la stessa backbone
• backbone constraints
enumerazione univoca e completa!
GASTON: graph enumeration
L’enumeration di grafi ha luogo considerando
unicamente cycle closing refinements, senza che ciò
infici la completezza dell’albero di ricerca
Utilizzo di Nauty normalization per il labeling dei grafi
Hashing dei grafi generati ad ogni passo
Il processo di enumeration per grafi consta di tre passi:
1.
2.
3.
Generazione di un grafo per ogni cycle close
refinement lecito
Ricostruzione della canonical form (mediante
Nauty normalization) dei grafi generati
Test di ridondanza mediante confronto con i grafi
già memorizzati nelle strutture hash
GASTON: frequency counting
Utilizzo di embedding list, organizzate efficientemente
per salvaguardare lo spazio di memorizzazione:
Per
un contiene
node
Ogni
riga
La
frequenza
di un
Ogni
Per
un
embedding
cycle
closing
puòil
Ogni
tupla
contiene
refinement
la
tupla
l’embedding
list
di
candidato
è data
dal
refinement
essere
ricostruito
la
tupla
riferimento
a
una
è
costituita
da:
antenato
del i
numero
di agrafi
ripercorrendo
èun
costituita
ritroso
da:
tupla
dell’embedding
t.parent,
t.graph,
grafo
in questione
differenti
presenti
puntatori
t.parent
listt.parent
del
padre
t.node
nell’embedding list
GASTON: frequency counting
Ad ogni passo dell’algoritmo, oltre all’embedding list della struttura
corrente, viene mantenuto l’intero legs set ad essa relativo
insieme di embedding list
di ognuna delle possibili
sottostrutture ottenibili
mediante refinement dalla
struttura corrente
In particolare, oltre alle legs relative a
refinement leciti, viene tenuta traccia anche di
tutte le altre (tranne che per l’enumerazione
dei free tree). Ciò consente alle operazioni di
join e extension di generare correttamente
l’embedding list delle strutture
successivamente generate
GASTON: algoritmo
chiamata DFS a
costruzione
delle
seconda
della
costruzione
del
nuovo
sottostrutture
figlie
sottostruttura
legs
set
a
seconda
mediantecreata
applicazione
del
refinement
dei refinement del
applicato
legs
set L
GASTON: prestazioni
Risultati su
artificial tree
datasets
GASTON: prestazioni
Risultati su
dataset reali:
DTP AIDS
 DTP HTCLS
 DTP

OSSERVAZIONE:
Nei vari esperimenti, il 90%
circa delle sottostrutture
frequenti scoperte
risultavano essere free tree…
=> l’applicazione del quickstart principle
porta notevoli benefici!
GASTON: conclusioni

Vantaggi:






Mining molto efficiente di sottostrutture
particolari, sfruttato anche nel mining di grafi
generali
Nessuna risoluzione di subgraph isomorphism
problem grazie alle embedding list
Labeling molto efficiente (Nauty normalisation)
Complessità spaziale ridotta (grazie a DFS e
all’efficiente organizzazione delle embedding list)
Prestazioni in generale superiori rispetto a tutti
gli altri algoritmi di graph mining analizzati
Svantaggi:

Test di ridondanza necessario, anche se efficiente
ed effettuato per le sole sottostrutture a grafo
CONCLUSIONI
TIPO
CANONICAL
RICERCA LABELING
CANDIDATE
GENERATION
OTTIM.
TEST DI
FREQUENCY
RIDONDANZA
COUNTING
APRIORI join
Normalization +
APRIORI false
test
-
BFS
Matrice di
Adiacenza
(vertex
invariants)
APRIORI join
(ottimizzata)
CL test +
APRIORI false
test
TID list
GSPAN
DFS
DFS code
DFS extension
Minimum DFS
test
TID list
FFSM
DFS
Matrice di
Adiacenza
FFSM join &
FFSM extension
CAM test
Embedding list
PATH
DFS
-
Node refinement
-
Embedding list
TREE
DFS
-
Node refinement
-
Embedding list
GRAPH
DFS
Nauty
normalization
Cycle Closing
refinement
Nauty norm.
hashing test
Embedding list
BFS
Matrice di
Adiacenza
FSG
AGM
GASTON