Graph Matching

Torsten Gründel

03.11.2006

Überblick

1. Was ist Graph Matching

2. Morphismen1. Allgeimeines

2. Graphisomorphismus

3. Subgraphisomorphismus

4. Eigenschaften

Überblick

3. Kategorien von Matchingmethoden1. Exakte Matchingmethoden

2. Unexaktes Matching1. Matchingkosten

2. Optimale & Suboptimale Inexakte Matchingalgorithmen

3. Matchingmethoden

Überblick

4. Subgraphalgorithmus von Ullmann1. Definitionen

2. Einfacher Aufzählungsalgorithmus

3. Verbesserte Prozedur

5. Zusammenfassung

6. Referenzen

1. Was ist Graph Matching?

Rechenintensive Technik aus den späten 70ern

„Graph Matching ist der Prozess, eine Korrespondenz zwischen Knoten und Kanten zweier Graphen zu finden, die (mehr oder weniger strikte) Bedingungen erfüllt und sicherstellt, dass gleiche Substrukturen eines Graphen auf gleiche Substrukturen des anderen Graphen abgebildet werden.“

Vielfältige Einsatzgebiete:

2D & 3D Bildanalyse Dokumentenverarbeitung Biometrische Identifizierung Bilddatenbanken Videoanalyse Biomedizinische und Biologische Anwendungen

1. Allgemeines

2. Graphisomorphismus

3. Subgraphisomorphismus

4. Eigenschaften

2. Morphismen

2. Morphismen

„Ein Morphismus ist eine Abbildung zwischen zwei mathematischen Objekten des selben Typs, die die grundlegende Struktur der Objekte erhält.“

Hier: Abbildung zwischen den Knoten der Graphen G=(V,E) und G‘=(V‘,E‘), die die Kantenverbindungen erhält.

Definition Graphenhomomorphisus (schwächste Form):

Striktere Form: Graphmonomorphismus

Hier müssen die Knotenabbildungen eindeutig sein

VyxEyfxfEyxVVf , allefür ')(),(,mit ':

2. Morphismen

1. Allgemeines

2. Graphisomorphismus

3. Subgraphisomorphismus

4. Eigenschaften

2.1 Graphisomorphismus

Definition: Ein Graphenisomorphismus ist ein bijektiver Graphenhomomorphismus

zwischen zwei Graphen G=(V,E) und G‘=(V‘,E‘) VyxEyfxfEyxVVf , allefür ')(),(,mit ':

1

4

2

3

5

A D

B

C

E

F(A) = 1

F(B) = 2

F(C) = 3

F(D) = 4

F(E) = 5

A D

B

C

E

2.1 Graphisomorphismus

Definition: Ein Graphenisomorphismus ist ein bijektiver Graphenhomomorphismus

zwischen zwei Graphen G=(V,E) und G‘=(V‘,E‘) VyxEyfxfEyxVVf , allefür ')(),(,mit ':

1

4

2

3

5

A D

B

C

E

A D

B

C

E

F(A) = 2

F(B) = 1

F(C) = 3

F(D) = 5

F(E) = 4

1. Allgemeines

2. Graphisomorphismus

3. Subgraphisomorphismus

4. Eigenschaften

2. Morphismen

2.2 Subgraphisomorphismus

Knoteninduzierter Subgraph: G‘=(V‘,E‘) ist Subgraph von G=(V,E) und

Definition: Ein Subgraphisomorphismus ist ein Graphisomorphismus zwischen

einem Graph G=(V,E) und einem knoteninduzierten Subgraph

eines zweiten Graphen G‘=(V‘,E‘)

','':, EvuVvVuEvu

A

B

C

1

4

2

3

5

F(A) = 1

F(B) = 3

F(C) = 2

A

B

C

1

2

3

2.2 Subgraphisomorphismus

Knoteninduzierter Subgraph: G‘=(V‘,E‘) ist Subgraph von G=(V,E) und

Definition: Ein Subgraphisomorphismus ist ein Graphisomorphismus zwischen

einem Graph G=(V,E) und einem knoteninduzierten Subgraph

eines zweiten Graphen G‘=(V‘,E‘)

','':, EvuVvVuEvu

A

B

C

1

4

2

3

5

A

B

C

F(A) = 1

F(B) = 3

F(C) = 4

1. Allgemeines

2. Graphisomorphismus

3. Subgraphisomorphismus

4. Eigenschaften

2. Morphismen

2.5 Eigenschaften

Graphisomorphismus: nicht bewiesen ob in NP

Alle Anderen: NP-Vollständig

Polynomielle Algorithmen für spezielle Graphen existieren

Rechenzeit heute akzeptabel, da Gesteigerte Rechenleistung Graphen in Praxis unterscheiden sich von „Worst Case Graphen“ Knoten- & Kanteneigenschaften reduzieren Suchzeiten

3. Graph Matching Methoden

1. Exaktes Matching

2. Unexaktes Matching1. Matchingkosten

2. Optimale & Suboptimale Inexakte Matchingalgorithmen

3. Matchingmethoden

3.1 Exaktes Graph Matching

Matching anhand vorgestellter Morphismen

Meist werden Bäume verwendet

Suchstrategie (z.B. BFS, DFS) gibt Reihenfolge vor

Grundidee: Partielles Matching (anfangs leer) iterativ um Matchingpaar erweitert

A

B

2

1

{ }

{(A,1)} {(A,2)}

{(A,1),

(B,1)}

{(A,1),

(B,2)}

{(A,2),

(B,1)}

{(A,2),

(B,2)}

1. Exaktes Matching

2. Unexaktes Matching1. Matchingkosten

2. Optimale & Suboptimale Inexakte Matchingalgorithmen

3. Matchingmethoden

3. Graph Matching Methoden

3.2 Unexaktes Matching

Gründe für Unexaktheit:1. Nichtdeterministische Elemente sind enthalten 2. Exaktes Matching ist zu teuer (Rechenzeit)

Matching muss nicht kantenerhaltend sein Bestrafung durch zuweisen von Kosten bei Unterschieden Suche Matching mit minimalen Kosten

Unterscheiden: Optimale Inexakte Matchingalgorithem Suboptimale Matchingalgorithmen

3.2.1 Matchingkosten

Fehlerkorrektur oder Fehlertoleranz Zuweisung von Kosten für jeden Fehler (z.B. fehlender Knoten) Vergleich der Graphen anhand der Kosten

Graphenbearbeitungskosten (GbK) Zuweisung von Kosten für Graphenbearbeitungsoperationen GbK = billigste Sequenz von Operationen zur Transformierung von G in G‘

Graphenbearbeitungsabstand Graphenbearbeitungskosten erfüllen gewisse Bedingungen Operationen zur Transformierung als Maß für den Abstand zwischen Graphen

Graphabstand (nur für Algorithmen in metrischen Räumen) Kostendefinition erfüllt Distanzfunktionseigenschaften Kosten sind Maß für die Ungleichheit von Graphen

3.2.2 Optimale & Suboptimale inexakte Matchingalgorithmen

Optimale Inexakte Matchingalgorithmen Finden immer globales Minimum, also auch exakte Lösung wenn vorhanden Kommt mit Graphschwankungen zurecht Kostenintensiver als Exakte Algorithmen Eignen sich zur Lösung von Problemen wenn exakte Lösung erforderlich aber

Graphschwankungen vorliegen

Suboptimale Matchingalgorithmen Finden lokales Minimum Keine Garantie exakte Lösung zu finden, wenn vorhanden Normalerweise polynomielle Vergleichszeit Eignen sich, wenn Rechenzeit gespart werden soll

3.2.3 Matchingmethoden

Baumsuche Heuristische Abschätzung der Matchingkosten für verbleibende Knoten Entfernen von unfruchtbaren Pfaden anhand Abschätzungen

Kontinuierliche Optimierung Grundidee:

1. Graphmatching umwandeln in kontinuierliches, nichtlineares OP

2. Anwendung eines Optimierungsalgorithmus um Lösung zu finden

3. Rücktransformierung in Graphmatching Domäne Polynomielle Rechenzeit (mit kleinem Exponenten) bzgl. Graphgröße

Spektralmethoden Benutzt Eigenschaft, dass

212121, GEVGEVGEWGEWisomorphGG

4. Ullmanns Subgraphalgorithmus

1. Allgemeines

2. Einfacher Aufzählalgorithmus

3. Verbesserte Version

4. Eigenschaften

4.1 Allgemeines

Wahrscheinlich bekanntester Graphmatching Algorithmus

Anwendbar für Subgraphisomorphismus Graphisomorphismen Graphmonomorphismen MCS Maximum Clique

Exakter DFS Baumsuchalgorithmus

Findet Subgraphisomorphismen zwischen zwei Graphen und

EVG , EVG ,

1. Allgemeines

2. Einfacher Aufzählalgorithmus

3. Verbesserte Version

4. Eigenschaften

4. Ullmanns Subgraphalgorithmus

4.2 Einfacher Aufzählungsalgorithmus

Benutzen Matrizen der Form: Einträge bestehen aus 0 und 1 Genau eine 1 in jeder Reihe Nicht mehr als eine 1 pro Spalte

Matrizen dienen Zur Permutation von Adjazenzmatrizen

p

p

VpundVp

Permutationsmatrix

Falls , dann korrespondiert der j-te Knoten in zu dem i-ten Knoten in

TBMMcC ij ''

1ijm G

G

4.2 Einfacher Aufzählungsalgorithmus (Beispiel Permutation)

0010

0100

0001

'M

0010

0010

1101

0010

B1

2

3

4

2

1

3

C

011

100

100

100

100

011

100

0010

0100

0001

0010

0010

1101

0010

0010

0100

0001

0010

0100

0001

4.2 Einfacher Aufzählungsalgorithmus

Vergleiche Resultierenden Graph mit

Isomorphismus vorhanden falls

Erstellung einer Startmatrix mit

Generierung aller mit durch systematisches umändern von 1en in 0en

Baum von Matrizen mit Terminierungsebene

11,

1

1

ijij caji

pj

pi

G

sonst , 0

von Knotensten -i des Grad dem von Knotensten -j des Gradder falls , 10 GGmij

0M

'M 11 0' ijij mm

p

4.2 Einfacher Aufzählungsalgorithmus (Generierung Startmatrix)

G G

0010

0010

1101

0010

1

2

3

4

21

3

0010

1111

1111

011

100

100

sonst , 0

on Grad dem von Gradder falls , 10 ijij

vvvm

A B

0M

Step 1: Initialisieren der Variablen, starten bei Initialmatrix und erster Zeile. Alle Spalten wurden noch nicht verwendetStep 2: Gibt es in aktueller Reihe eine 1, deren Spalte noch nicht verwendet wurde? Wenn ja, dann verwende diese SpalteStep 3: Suche ersten verwendbaren Spalteneintrag mit 1 und setze alle anderen Einträge der Zeile auf 0Step 4: Falls Terminierungslevel erreicht, dann überprüfe ob Isomorphismus vorhandenStep 5: Überprüfe, ob es einen Eintrag weiter rechts in Matrix gibt, der 1 ist und verwendet werden kannStep 6: Speichere welche Zeile verwendet wurde und erhöhe die Zeilenanzahl um 1Step 7: Backtracking

4.2 Einfacher Aufzählungsalgorithmus (Der Algorithmus)

Step 4Step 6Step 7Step 5

0010

1111

0001

0010

1111

0100

0010

1111

1000

0010

1111

1111

0010

1111

0010

0010

0100

0001

0010

0010

0001

0010

1000

0001

0010

0100

0001

0010

1000

0001

0010

0001

0010

0010

1000

0010

0010

0100

0010

0010

0001

0100

0010

0010

0100

0010

1000

0100

0010

0001

0100

0010

1000

0100

0010

0001

1000

0010

0010

1000

0010

0100

1000

0010

0001

1000

0010

0100

1000

4.2 Einfacher Aufzählungsalgorithmus (Beispiel)

Step 1Step 2Step 3

1

3

2

21

3

1

3

22

3

1

3

1

24

3

1

3

2

1

0010

0100

0001

0010

1000

0001

0010

0001

0100

0010

1000

0100

0010

0001

1000

0010

0100

1000

4

3

41

3

1

011

100

100

Vergleiche mit A

011

100

100

jeweils '' sBerechnete TBMMcC ij

4.2 Einfacher Aufzählungsalgorithmus (Beispiel)

4.3 Verbesserte Prozedur

Wenn für alle Isomorphismen M‘ unter M gilt dann setze

Neue Bedingung:

Iteratives Testen bis keine 1 in 0 umgewandelt wird

1yv

iv

2xv 2yv

jv

1xv

11 aufgematcht

11yjxyixji bmyaxvv

pypx

10' ijij mm0ijm

4.3 Verbesserte Prozedur (Der Algorithmus)

Step 1: Variablen aufsetzenStep 2 - 4: Nachbarn des i-ten

Knoten suchen

Step 5: nächster MatrixeintragStep 6: Überprüfe ob

Matrixeintrag 0 ist

Step 7: Überprüfe ob Nachbar

des i-ten Knotens auf

einen Knoten gemappt

werden kann.

Step 8: Setze Eintrag auf 0Step 9: Nächster Matrixeintrag

und nächster Knoten j

Step 10: Fehler,

nächster Knoten i,

neuer Durchlauf

oder Erfolg

4.3 Verbesserte Prozedur (Anwendung)

Verbesserung durch Anwendung von

0010

1111

1111

011

100

100

0010

0010

1101

0010

11

1yjxyix bmya

py

A B0M

i = 1 j = 1 sc = 1000 lst = 3 h = 1

i = 1 j = 1 sc = 1000 lst = 3 h = 1 x = 3

i = 1 j = 1 sc = 1000 lst = 3 h = 2 x = 3

4.3 Verbesserte Prozedur (Anwendung)

i = 1 j = 1 sc = 1000 lst = 3

0010

1111

1111

011

100

100

0010

0010

1101

0010

A B0M

Step 1,2,3,4,5Step 6Step 7

0010

1111

1101

4.3 Verbesserte Prozedur (Anwendung)

0010

1111

1111

011

100

100

0010

0010

1101

0010

A B0M

Step 6Step 7Step 9 i = 1 j = 2 sc = 0100 lst = 3 h = 2 x = 3

i = 1 j = 2 sc = 0100 lst = 3 h = 1 x = 3

Step 8

4.3 Verbesserte Prozedur (Adaptierter Suchalgorithmus)

0010

1101

0001

0010

1101

0100

0010

1101

1000

0010

1101

1101

0010

0100

0001

0010

1000

0001

0010

0100

0001

0010

1000

0001

0010

0001

0100

0010

1000

0100

0010

0001

0100

0010

1000

0100

0010

0001

1000

0010

0100

1000

0010

0001

1000

0010

0100

1000

4.2 Verbesserte Prozedur (Beispiel)

Step 1Step 2Step 3Step 4Step 6Step 7Step 5

5. Zusammenfassung

Rechenintensiv, aber akzeptabel

Verschiedene Arten von Matching und Methoden

Vielfältige Anwendungsgebiete und Methoden (>170 Referenzen im zweiten Paper)

Für uns besonders RDF-Matching interessant

Referenzen