German Title: Erforschung von Graphen-Strukturen: Lernen und Analyse

Preview

PDF, English Download (68MB) | Terms of use

Abstract

Graphs are versatile data structures with great flexibility to represent various kinds of information due to their capability to model relationships between entities. In this work, we explore diverse applications of graphs in machine learning, with a particular focus on spanning trees.

First, we introduce the ``Directed Probabilistic Watershed'' algorithm, a graph-based semi-supervised learning method for classification on directed graphs. This algorithm builds a probability distribution over directed forests to infer the label of a node. It does this by considering the probability of a directed forest connecting the node to one of the given labeled nodes within the same subtree.

Next, building on a similar probabilistic framework, we investigate the node degree distribution in a random spanning tree. We provide analytical expressions for both the expected value and variance of the degree of a node in a spanning tree.

Subsequently, we analyze different node metrics in graphs, focusing on distances computed based on the paths connecting nodes. We frame several popular distance metrics, namely the shortest path distance, the commute cost distance, the minimax distance and the potential distance, as instances of the ``algebraic path problem'', which is a generalization of the shortest path problem. We introduce the ``log-norm'' distance, a node metric that interpolates between the aforementioned metrics. Furthermore, we establish certain conditions that are sufficient and necessary for an algebraic path problem to define a metric across any given graph.

Finally, returning to the study of spanning trees, we focus on the geometrical stability. We introduce the ``central spanning tree,''a parameterized family of spanning trees embedded in Euclidean space. By conducting empirical tests, we showcase its resilience against perturbations such as noise in node coordinates. We formulate the central spanning tree as a minimization problem, establishing connections to other well-known spanning tree problems such as the minimum spanning tree or the Euclidean Steiner tree. Additionally, we explore a variant of the central spanning tree, referred to as ``branched central spanning tree'', that allows for the inclusion of Steiner points. We demonstrate the efficacy of this variant in modeling the skeleton of 3D point clouds representing plants.

Translation of abstract (German)

Graphen sind vielseitige Datenstrukturen, die aufgrund ihrer Fähigkeit, Beziehungen zwischen Entitäten zu modellieren, große Flexibilität bei der Darstellung verschiedener Arten von Informationen bieten. In dieser Arbeit werden verschiedene Anwendungen von Graphen im Bereich des maschinellen Lernens untersucht, wobei ein besonderer Schwerpunkt auf Spannbäumen liegt.

Zuerst stellen wir den ``Directed Probabilistic Watershed'' Algorithmus vor, ein graphenbasiertes, teilüberwachtes Lernverfahren für die Klassifizierung von gerichteten Graphen. Dieser Algorithmus baut eine Wahrscheinlichkeitsverteilung über gerichtete Wälder auf, um das Label eines Knotens abzuleiten. Er tut dies, indem er die Wahrscheinlichkeit eines gerichteten Waldes berücksichtigt, der den Knoten mit einem der gegebenen gelabelten Knoten innerhalb desselben Teilbaums verbindet.

Als Nächstes untersuchen wir, aufbauend auf einem ähnlichen probabilistischen Rahmen, die Knotengradverteilung in einem zufälligen Spannbaum. Wir liefern analytische Ausdrücke sowohl für den Erwartungswert als auch für die Varianz des Grades eines Knotens in einem Spannbaum.

Anschließend analysieren wir verschiedene Knotenmetriken in Graphen, wobei wir uns auf Entfernungen konzentrieren, die auf der Grundlage der Verbindungswege zwischen Kno-ten berechnet werden. Wir betrachten mehrere populäre Distanzmetriken, nämlich die kür-zeste Pfaddistanz, die ``Commute Cost''-Distanz, die Minimax-Distanz und die Potentiality, als Instanzen des algebraischen Pfadproblems, das eine Verallgemeinerung des Problems des kürzesten Pfades ist. Wir führen die ``Log-Norm'' Distanz ein, eine umfassende Knotenmetrik, die zwischen den oben genannten Metriken interpoliert. Darüber hinaus legen wir bestimmte Bedingungen fest, die hinreichend und notwendig sind, damit ein Algebraisches Pfadproblem eine Metrik über einen beliebigen gegebenen Graphen definiert.

Schließlich kehren wir zur Untersuchung von Spannbäumen zurück und konzentrieren uns auf die geometrische Stabilität. Wir stellen den ``zentralen Spannbaum'' vor, eine parame-trisierte Familie von Spannbäumen, die in den euklidischen Raum eingebettet sind. Durch die Durchführung empirischer Tests zeigen wir seine Widerstandsfähigkeit gegenüber Störungen wie Rauschen in den Knotenkoordinaten. Wir formulieren den zentralen Spannbaum als ein Minimierungsproblem und stellen Verbindungen zu anderen bekannten Spannbaumproblemen wie dem minimalen Spannbaum oder dem euklidischen Steiner-Baum her. Zusätzlich untersuchen wir eine Variante des zentralen Spannbaums, den so genannten ``Verzweigten zentralen Spannbaum'', die das Hinzufügen von Steiner-Punkten erlaubt. Wir demonstrieren die Wirksamkeit dieser Variante bei der Modellierung des Skeletts von 3D-Punktwolken, die Pflanzen darstellen.