UNIVERSITA DEGLI STUDI DELLA CALABRIA FACOLTA DI INGEGNERIA Corso di Laurea Spec. in Ingegneria...
-
Upload
xaviera-mora -
Category
Documents
-
view
213 -
download
1
Transcript of UNIVERSITA DEGLI STUDI DELLA CALABRIA FACOLTA DI INGEGNERIA Corso di Laurea Spec. in Ingegneria...
UNIVERSITA’ DEGLI STUDI DELLA CALABRIA
FACOLTA’ DI INGEGNERIA
Corso di Laurea Spec. in Ingegneria Informatica
“Graph Mining”
Prof. G. Manco Francesco Gullo Ing. F. Folino matr. 87675
Anno Accademico 2004/2005
DATA MINING E SCOPERTA DELLA CONOSCENZA
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
Transazione:insieme di items
Itemset: collezione di items
Es. {Bread, Milk, Coke}
Obiettivo primario:
ricerca di itemset frequenti
{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 Grafi Items Nodi Relazioni tra items Archi
Ricerca di itemset fequenti in un dataset
di transazioni
Ricerca di sottografi frequenti in un dataset di grafi
Applicazioni
• Chimica• Genetica• Web• Reti• …
Definizioni preliminari
Grafo etichettato: V, insieme di nodiE, insieme di archiL, insieme di etichette , funzione che assegna etichette a nodi ed archi
Gs=(Vs, Es) è sottografo di G=(V, E) sse e
Gs=(Vs, Es) è sottografo indotto di G=(V, E)sse e
G=(V,E) è connesso sse esiste un cammino per ogni coppia di nodi V
LEVl :
),,,( lLEVG
VVS EES
VVS )(),()(),(),(, GEvuGEvuGVvu SS
Definizioni preliminari Un isomorfismo è una funzione biunivoca
tale che:
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
))(),((),()())(),((),(),(
))(()(),(
vfuflvulGEvfufGEvu
uflulGVu
GG
GG
)()(: GVGVf
Isomorfismo
Proprietà: Struttura topologicamente uguale Matrici di adiacenza e incidenza Vertex invariants
Punto cruciale: risoluzione del subgraph isomorphism problem
Isomorfismo
G: H:
G e H sono isomorfi (esiste in isomorfismo ‘f’ tra G e H):
H: f(1)=4f(2)=1
f(3)=2f(4)=3
G’ e H’ non sono isomorfi pur avendo lo stesso numero di nodi e di archi:
G’: H’:
1 2
3 4
1 2
3 4
14
2 3
a
a
a
a
a
a
b
b
b
c
c
c
d d
d
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
=> permutazioni
m
iip
1
)!(
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
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. 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};
Candidate Generation:
join
false test
Frequency Counting
• largamente utilizzato nei modelli market-basket
• schema base per alcuni algoritmi di ricerca di sottografi
Soluzioni proposte
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
Algoritmi analizzati: AGM FSG gSpan FFSM GASTON
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 grafiMatrice di adiacenza:Dato un grafo etichettato , la matrice di
adiacenza X è costituita dai seguenti elementi xij:
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:
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
)),(),(),(( lGLGEGVG
E(G))j,vi;(v
hellbGEjvivhelbnum
ijx
0
)()(),();(
1,...,2,1));(())(( 1 kivlbnumvlbnum ii
AGM: candidate generation1. JOIN
La join avviene tra grafi che differiscono per un unico nodo:
sottomatrice in comune
vettori colonna di dim. (k-1) x 1
elementi non determinati da
Xk e Yk
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
)(minarg)(
XcodeXGNFX
C
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
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
AGM: prestazioniRisultati 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: algoritmofsg(D, σ){
1: F1 ← all frequent 1-subgraphs in D2: F2 ← all frequent 2-subgraphs in D3: k ← 34: while Fk-1≠ Ø do5: Ck ← fsg-gen(Fk-1)6: for each candidate Gk Ck do7: Gk.count ← 08: for each transaction T D do9: if Gk is included in T then10: Gk.count ← Gk.count + 111: Fk ← {Gk E Ck | Gk.count ≥ σ|D|} 12: k ← k + 113: return {F1, F2,…, Fk-2}
}
generazione di tutti i sottografi
frequenti di dimensione 1 e 2
Candidate Generation:
generazione sottografi candidati di dim. k, mediante fusione
dei sottografi frequenti di dim. k-1
Frequency Counting
selezione dei candidati che soddisfano il vincolo di
supporto
FSG: candidate generationLa 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:
(1). Nodo con uguale etichetta:(2). Automorfismi multipli del core
(3). Cores multipli
FSG: candidate generationfsg-gen(Fk){
1: Ck+1 ← Ø2: for each pair of (Gi
k,Gjk) Fk, i ≤ j and cl(Gi
k) ≤ cl(Gjk) do
3: Hk-1 ← { Hk-1| Hk-1 is a core shared by Gik and Gj
k }4: for each core Hk-1 E Hk-1 do5: { Bk+1 is a set of tentative candidates }6: Bk+1 ← fsg-join(Gi
k,Gjk, Hk-1)
7: for each Gjk+1 E Bk+1 do
8: { test if the downward closure property holds }9: flag ← true10: for each edge el Gj
k+1 do11: Hl
k ← Gjk+1- el
12: if Hl k is connected and Hl
k Fk then13: flag ← false14: break15: if flag = true then16: Ck+1 ← Ck+1 U {Gj
k+1}17: return Ck+1
}
generazione di tutti i core condivisi per
ogni coppia di sottografi frequenti
generazione di tutti i possibili candidati
mediante fusione di ogni coppia di sottografi
frequenti, per ogni core condiviso
false test
FSG: candidate generation
fsg-join(G1k, G2
k, 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 do6: Bk+1 ← Bk+1 U {all possible candidates of size k+1
created from a set of e1, e2, Hk-1 and ψ}7: return Bk+1
}
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 labelingIl 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: prestazioniRisultati 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
Motivazione: presenza variabile di pattern regolari |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: 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: prestazioniScalabilità 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: sse oppure
• ordinamento totale: sse oppure
È utilizzato nella definizione del DFS code per un
grafo G a partire da un DFS tree T
GSPAN: DFS codeOrdinamento 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
Relazione padre P = (a0, a1,…,am) figlio C = (a0, a1,…,am, b)
Relazione tra fratelli: ordinamento lessicografico basato sul DFS
code
Lo spazio di ricerca è rappresentato dal DFS code tree
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: algoritmoGraphSet_Projection( ){
}
eliminazione archi e nodi infrequenti dai grafi del dataset GS
generazione di tutti gli archi a partire dall’insieme di
etichette frequenti e salvataggio dei soli
frequenti
salvataggio degli ID di ogni transazione in cui compare l’arco e
DFS ricorsiva nel sottoalbero avente come root l’arco s
riduzione di ogni transazione di GS mediante eliminazione
dell’arco appena analizzato
GSPAN: depth first searchSubgraph_Mining( ){
}
Enumerate(s){
}
pruning
frequency counting
continuazione ricorsiva della DFS per i soli sottografi frequenti
calcolo della frequenza di ogni figlio di s e salvataggio delle
transazioni in cui è presente
calcolo di tutte le occorrenze di s nelle transazioni in cui è contenuto; il subgraph isomorphism problem è
risolto con approccio backtracking
GSPAN: ottimizzazioni
Pruning pre-pruning post-pruning
Minimum DFS code 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: CAMOgni 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: CAMOgni 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-joinLa 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
A matrice inner
B matrice outer
A e B matrici outer
Per evitare ridondanze la join tra due matrici A e B viene
effettuata soltanto se code(A)≥code(B), tranne
che per il caso 3b
FFSM: FFSM-extensionL’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
insieme di tutte le suboptimal CAM del livello superiore
generazione figli mediante FFSM-join
generazione figli mediante FFSM-extension
frequency counting (la versione ottimizzata fa uso di embedding list)
FFSM: embedding list
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!
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
FFSM: embedding listFFSM-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
Paths Free Trees Cyclic Graphs
Ordinamento parziale tra
sottostrutture di un grafo
node refinement
node refinementcycle closing
refinement
Lo spazio di ricerca è partizionato in base alla sottostruttura da considerare:
GASTON: path enumeration(v1e1v2…vn-1en-1vn) Possibili ridondanze dovute
all’orientamento!
comparazione lessicografica tra (v1,e1) e
(vn,en-1)
(v1,e1) > (vn,en-1) => padre: (v2…vn-1en-1vn)
(v1,e1) < (vn,en-1) => padre: (v1e1v2…vn-1)
path simmetrico =>padre:indifferente!
(v1e1v2…vn-1)<(vnen-1vn-1…v2) =>padre:(v1e1v2…vn-1)
(vnen-1vn-1…v2)< (v1e1v2…vn-1) =>padre:(v2…vn-1en-1vn)
(v1,e1)=(vn,en-1)
Definizione univoca del predecessore di ogni path string nell’albero di enumerazione:
GASTON: path enumeration
(v1e1v2…vn-1en-1vn): total simmetry
(v1e1v2…vn-1) : front simmetry
(v2…vn-1en-1vn): back simmetry
Algoritmo di refinement:
0 => stringa simmetrica
-1 => inversa minore
+1 => corrente minore
total simmetry=0 => tutti i refinements possibili
altrimenti, solo determinati (l(v’),l(e’)) possibili
(l(v’),l(e’)) > (l(v1),l(e1))
(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 enumerationpath 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 enumerationL’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. Generazione di un grafo per ogni cycle close
refinement lecito2. Ricostruzione della canonical form (mediante
Nauty normalization) dei grafi generati3. Test di ridondanza mediante confronto con i grafi
già memorizzati nelle strutture hash
GASTON: frequency countingUtilizzo di embedding list, organizzate
efficientemente per salvaguardare lo spazio di memorizzazione:
Ogni riga contiene l’embedding list di
un antenato del grafo in questione
Ogni tupla contiene il riferimento a una
tupla dell’embedding list del padre
Per un node refinement la
tupla è costituita da: t.parent,
t.graph, t.node
Per un cycle closing refinement la
tupla è costituita da: t.parent
Ogni embedding può essere ricostruito
ripercorrendo a ritroso i puntatori t.parent
La frequenza di un candidato è data dal
numero di grafi differenti presenti nell’embedding list
GASTON: frequency countingAd ogni passo dell’algoritmo, oltre all’embedding list della struttura
corrente, viene mantenuto l’intero legs set ad essa relativo
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
insieme di embedding list di ognuna delle possibili sottostrutture ottenibili mediante refinement
dalla struttura corrente
GASTON: algoritmo
costruzione delle sottostrutture figlie
mediante applicazione dei
refinement del legs set L
costruzione del nuovo legs set a seconda
del refinement applicato
chiamata DFS a seconda della sottostruttura
creata
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 RICERCA
CANONICAL LABELING
CANDIDATE GENERATION
TEST DI RIDONDANZA
OTTIM. FREQUENCY COUNTING
AGM BFSMatrice di Adiacenza
APRIORI joinNormalization +
APRIORI false test
-
FSG BFS
Matrice di Adiacenza
(vertex invariants)
APRIORI join(ottimizzata)
CL test + APRIORI false
testTID list
GSPAN DFS DFS code DFS extensionMinimum DFS
testTID list
FFSM DFSMatrice di Adiacenza
FFSM join &FFSM extension
CAM test Embedding list
GASTON
PATH DFS - Node refinement - Embedding list
TREE DFS - Node refinement - Embedding list
GRAPH DFSNauty
normalizationCycle Closing refinement
Nauty norm. hashing test
Embedding list