Detailansicht
Efficient and expressive graph learning
Franka Regina Bause
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Doktoratsstudium der technischen Wissenschaften Informatik
Betreuer*in
Nils Morten Kriege
DOI
10.25365/thesis.79028
URN
urn:nbn:at:at-ubw:1-23019.74513.793772-2
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Graphen dienen als vielseitige Darstellungen für reale und auch abstrakte Objekte in vielen Anwendungsbereichen, zum Beispiel in der Analyse von sozialen Netzwerken, dem Gesundheitswesen und bei der Erkennung von betrügerischen Aktivitäten. Aufgaben im Graphlernen, die von der Klassifikation von Knoten und der Vorhersage von Kanten, bis hin zur Klassifikation von Graphen reichen, werden immer häufiger. Mit zunehmender Menge an Daten, ist die Skalierbarkeit von Graphlernmethoden entscheidend geworden. Außerdem stellt die Expressivität, die die Fähigkeit einer Methode misst, Paare von nicht-isomorphen Graphen zu unterscheiden, immer noch eine grundlegende Herausforderung im Graphlernen dar. Ziel dieser Arbeit ist es, Graphlernverfahren voranzutreiben, indem die Skalierbarkeit erhöht, Ähnlichkeitsmaße verbessert und die Beschränkungen von derzeitigen Methoden in Bezug auf die Expressivität untersucht werden. Da Ähnlichkeitsmaße für Graphen typischerweise auf Ähnlichkeitsmaßen für Knoten beruhen, untersuchen und entwickeln wir Methoden, um die Nachbarschaft von Knoten genauer zu erfassen. Insbesondere konzentrieren wir uns auf die Approximation der Grapheditierdistanz zur effizienten Suche in Graphdatenbanken. Durch die Verwendung einer bestehenden unteren Schranke für die Grapheditierdistanz in Kombination mit einem metrischen Index in einem Filter-Verifikations-Framework ermöglichen wir die Suche in großen Graphdatenbanken. Wir schlagen neue untere Schranken vor, die in den l1-Raum eingebettet werden können, um als noch effizientere erste Filter zu dienen. Wir entwickeln kompakte Bäume, die Knotennachbarschaften ohne Redundanz kodieren. Durch die Verwendung der Distanz dieser Bäume als zugrundeliegende Kostenfunktion beim Bipartite Graph Matching zur Approximation der Grapheditierdistanz, kann ein besserer Kompromiss zwischen Laufzeit und Approximationsgüte erreicht werden. Um eine feingliedrigere Knotenähnlichkeit zu erhalten, entwerfen wir eine graduellere Version des Weisfeiler-Leman-Algorithmus, die langsamer zur stabilen Färbung konvergiert. Die sich daraus ergebende Ähnlichkeitsfunktion verbessert die Genauigkeit bei der Approximation der Grapheditierdistanz und in Graphkernen erheblich. Das Message Passing in Graphneuronalennetzen kann als neuronale Version des Weisfeiler-Leman-Algorithmus gesehen werden. Wir entwickeln Message Passing auf kompakten Bäume, die Knotennachbarschaften ohne Informationsredundanz darstellen. Diese Art von Redundanz wurde mit Oversquashing in Verbindung gebracht. Außerdem verringern wir die Berechnungsredundanz, indem wir isomorphe Teilstrukturen im Berechnungsgraphen zusammenführen. Wir gehen also auf beide Arten von Redundanz ein, die in Graphneuronalennetzen vorkommen. Zusätzlich entwickeln wir eine linear-zeit Graphtransformation, die es dem Weisfeiler-Leman-Algorithmus ermöglicht, zwei beliebige nicht-isomorphe außerplanare Graphen zu unterscheiden. Dies ist besonders wichtig für Moleküldaten, da die meisten Moleküle als außerplanare Graphen dargestellt werden können. Die Expressivität von Graphneuronalennetzen in Bezug auf den Weisfeiler-Leman-Algorithmus wurde ausgiebig untersucht, aber die Expressivität für bestimmte Graphklassen wurde noch nicht umfassend erforscht. In dieser Arbeit entwickeln wir Graphlernverfahren weiter, indem wir einen besseren Kompromiss zwischen Effizienz und Genauigkeit bei der Approximation der Grapheditierdistanz finden, wobei wir uns besonders auf die genauere Darstellung von Knotennachbarschaften konzentrieren. Außerdem wenden wir unsere Erkenntnisse auf Graphneuronalenetze an, um expressivere Modelle zu entwickeln.
Abstract
(Englisch)
Graphs are versatile representations for real-world objects and abstract entities in many applications, such as social network analysis, healthcare, and fraud detection. Graph learning tasks, ranging from node classification and link prediction to graph classification and regression, have become more and more prevalent. With increasing data, scalability has become crucial for graph learning methods. Additionally, expressivity, which measures the ability of a method to distinguish pairs of non-isomorphic graphs, still poses a fundamental challenge in graph learning. This thesis aims to advance graph learning techniques by enhancing scalability, improving similarity measures, and addressing expressivity limitations in current methods. Since graph similarity measures typically rely on similarity measures for nodes, we investigate and develop methods to capture the neighborhood of nodes more accurately. Specifically, we focus on efficiently approximating the graph edit distance for search in graph databases. Using an existing lower bound for the graph edit distance in combination with a metric index in a filter-verification framework, we make searching in large graph databases possible. We propose novel lower bounds that can be embedded into l1 space to be used as an even more efficient first filter. Using the distance between pruned unfolding trees as the underlying cost function in bipartite graph matching to approximate the graph edit distance, an improved trade-off between running time and approximation accuracy can be achieved. To gain a more fine-grained vertex similarity measure, we propose a more gradual version of the Weisfeiler-Leman algorithm that converges to the stable coloring more slowly. The resulting similarity measure significantly improves the accuracy of graph edit distance approximations and graph kernels. Message passing neural networks can be seen as a neural version of the Weisfeiler-Leman algorithm. We develop message passing on pruned unfolding trees that represent node neighborhoods without information redundancy. This type of redundancy has been linked to oversquashing. We mitigate computational redundancy, by merging isomorphic substructures in the computational graph. Therefore, we address both types of redundancy present in graph neural networks. Furthermore, we propose a linear-time graph transformation that enables the Weisfeiler-Leman algorithm to distinguish any two non-isomorphic outerplanar graphs. This is especially relevant for molecular data, as most molecules can be represented as outerplanar graphs. The expressivity of message passing neural networks in relation to the Weisfeiler-Leman algorithm has been studied extensively, but expressivity on specific graph classes has not yet been widely investigated. In this thesis we advance graph learning by finding a better trade-off between efficiency and accuracy in approximating the graph edit distance, specifically focusing on accurate representations of node neighborhoods. Furthermore, we apply our representations to graph neural networks to develop more expressive models.
Schlagwörter
Schlagwörter
(Deutsch)
Graphlernen Graphen Maschinelles Lernen Grapheditierdistanz
Schlagwörter
(Englisch)
Machine Learning Graphs Graph Neural Networks Graph Edit Distance Graph Learning
Autor*innen
Franka Regina Bause
Haupttitel (Englisch)
Efficient and expressive graph learning
Publikationsjahr
2025
Umfangsangabe
x, 164 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*innen
Bastian Grossenbacher-Rieck ,
Yllka Velaj
Klassifikation
54 Informatik > 54.00 Informatik. Allgemeines
AC Nummer
AC17611400
Utheses ID
75390
Studienkennzahl
UA | 786 | 880 | |