Techniken zum Messen von Ähnlichkeiten zwischen Graphen

• Antragsteller: Gaurav Rattan, Ph.D.
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2018 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 411032549

In diesem Projekt sind wir daran interessiert, einen theoretischen Rahmen für das Messen der Ähnlichkeit zwischen Graphen zu entwickeln. Wir schlagen ein neuartiges Konzept auf der Basis der Anzahl von Graphhomomorphismen vor und unterziehen zugleich bereits bekannte Ansätze für die Graphähnlichkeit einer erneuten Prüfung. Wir glauben, dass die bestehenden Einblicke und Werkzeuge für das Graphisomorphieproblem neue Ansätze für die Graphähnlichkeit liefern können und auch Rückschlüsse in die umgekehrte Richtung möglich sind.Unser erstes Ziel ist die Formulierung und Untersuchung eines neuen Rahmens für das Messen der Ähnlichkeit zwischen Graphen. Wir streben an, Kodierungen für Graphen durch (möglicherweise unendlich-dimensionale) Vektoren zu entwickeln, sodass die Distanz zwischen den Vektoren (bezüglich einer passenden Metrik) ein sinnvolles Maß für die Ähnlichkeit von Graphen liefert. Die naheliegenden Kandidaten für derartige Kodierungen sind beschränkte Homomorphismus-Vektoren HOM_C(G), bei denen wir eine Klasse C von Graphen festlegen und die Anzahlen der Homomorphismen Hom(F,G) für jeden Graphen F in der Klasse C auflisten. In einer passenden Metrik ist der Abstand zwischen den Vektoren HOM_C(G) und HOM_C(H) ein Kandidat für das Ähnlichkeitsmaß. Unsere vorherige Arbeit liefert eine starke mathematische Motivation für die Untersuchung solcher Maße. Unser zweites Ziel ist die Untersuchung der Graphähnlichkeit unter dem Gesichtspunkt der kombinatorischen Optimierung. Die Adjazenzmatrizen zweier Graphen G und H wurden bereits in der Vergangenheit dazu eingesetzt, ein Maß für die Distanz zweier Graphen zu definieren. Wir suchen effiziente Algorithmen um solche Maße für die Ähnlichkeit zu berechnen und zu approximieren. Unsere neue Herangehensweise soll insbesondere die durch unsere vorherige Arbeit nahegelegte Rolle des Spektrums (Eigenwerte und Eigenvektoren) der Eingabegraphen bei dieser Aufgabe herausarbeiten. Dies möchten wir durch die Erforschung und Anpassung bekannter Werkzeuge der konvexen Optimierung für Graphisomorphie erreichen.Die Graphähnlichkeit ist mit einer ausschließlich praktischen Betrachtungsweise bereits ausgiebig in vielen anderen Bereichen wie im maschinellen Lernen und der Datenbanktheorie untersucht worden. Ein wichtiges Ziel unseres Projektes ist die theoretische Erklärung des Erfolgs praktischer und heuristischer Algorithmen in diesen Bereichen. Im Allgemeinen liegen die praktischen Anwendungen unseres Projekts in Fachgebieten, die sich mit durch Graphen strukturierten und relationalen Daten beschäftigen, wie zum Beispiel Mustererkennung, Graphklassifikation und Graph-Mining. Uns interessiert insbesondere das aufstrebende Gebiet der Graphkernel. Letztendlich sind wir auch an effizienten Implementierungen unserer Arbeit interessiert. Dieser Teil des Projekts wird aus einer experimentellen Untersuchung der Ergebnisse bestehen.

• DFG-Verfahren: Sachbeihilfen